「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
生年月日から年齢を計算する簡単な計算式：ITpro
私の個人ブログに掲載したら好評でしたので、こちらでもご紹介してみます。 最近知ったんですが、生年月日から年齢を計算する簡単な計算式というのがあるそうです。 (今日の日付-誕生日)/10000の小数点以下切捨て。 PHPで書くと echo (int)((20070823 - 19850101)/10000); Perlで書くと print int ((20070823 - 19850101)/10000); JAVAで書くと System.out.println( (int)((20070823 - 19850101)/10000) ); という感じになります。 日本の法律を確認してみました。誕生日の前日が終了する瞬間（すなわち誕生日をむかえる午前0時00分の直前）に1歳を加えることになる。ただしうるう年など、年によって期間を定めた場合において最後の月に応当する日がないときは、その月の末日を
ナップサック問題について整理 - yasuhisa's blog
どういうときに何ができるのかについて。この辺見ながら。 問題定義品物がN個あったとする。品物iには価値と体積が与えられている。は1のとき品物iを取る、0のときに取らないということを表すバイナリ変数であるとする。持って行ける品物の総体積がbまでであるとすると、ナップサック問題は以下の最適化問題として定式化される。 最大化: 制約: かつ これを真面目に列挙して解こうとするとO(2^N)となって多項式時間では解けない。の部分をという風に連続緩和してやれば解は閉じた形で書き表すことができる(でソートしてやって、でかい順に詰めていく。最後のやつは入る分だけ詰める)。 動的計画法ここで、体積とbを「整数」であると仮定する。を体積yの中に詰める品物の候補をに限定したときに得られる最大の価値と定義する。すると元の問題の最適解はがfeasibleのときに達成される。こういう定義をすると、動的計画法かと検討
A*アルゴリズムについて整理 - yasuhisa's blog
辞書を参考にしながら。NAISTのI期辺りでやったはずなんだが、かなりすっ飛んでいる。 デジタル人工知能学事典 [CD-ROM付] 作者: 人工知能学会出版社/メーカー: 共立出版発売日: 2008/05/16メディア: 単行本購入: 1人 クリック: 6回この商品を含むブログ (6件) を見る A*アルゴリズムとは?グラフ探索アルゴリズムの一つ。「開始ノードから現在位置に至るまでのコスト」と「現在位置からゴールまでの推定コスト」の2つのコストを用いてadmissibleな条件(後述)の元でコストが最小であるような経路を効率的に見つけることができるアルゴリズムである。1960年代に開発されたアルゴリズムであるが、50年経った今でもばしばし使われている。 現在いるノードをp、開始ノードからpまでの最小コストをg(p)、pからゴールまでの最小コストをh(p)と書くとすればpを経由して開始ノード
LDA入門
IBIS 2021 https://ibisml.org/ibis2021/ における最適輸送についてのチュートリアルスライドです。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https://speakerdeck.com/joisino/zui-shi-shu-song-ru-men 最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-
画像処理におけるアルゴリズム
ここでは各画像処理におけるアルゴリズムを簡単に解説する。 2値化 明るさ調整 色成分の抽出 色反転 コントラスト調整 切り出し ガンマ補正 グレイスケール化 増色 画像枠付加 鏡像反転 ノイズ除去 輪郭抽出 輪郭追跡 拡大縮小 任意角回転 セピア調化 ぼかし 2値化 指定画像を白と黒の2階調の画像に変換する処理であり、本研究で作成した2値化処理は単一手動閾値方式、P-タイル法、また、誤差分散法およびその拡張型である Floyd&Steinberg 型誤差分散、Jarvice,Judice&Ninke 型誤差分散の5つである。 次にそれぞれのアルゴリズムについて解説する。 単一手動閾値方式 指定された色深度を基準として、その値より入力画素の色深度値が明るければ白、暗ければ黒色として2値化する。下の式を用いている。 このとき、出力画像は初期状態で黒色となるので、入力画像の画素値が閾値以
日本発の「Topcoderトレーニング講座」は最強最速アルゴリズマーへの最短経路
アプリケーションプラネットは2月5日から、日本発となる「Topcoderトレーニング講座」を開設する。講師は「最強最速アルゴリズマー養成講座」の著者としても知られる高橋直大氏。これにより、優秀なアルゴリズマーたちが活躍できる場が日本でも生まれるかもしれない。 高橋直大――彼を形容する言葉は幾つかあるが、ITmediaの読者であれば、「アルゴリズマー」という言葉が最も彼をよく表していると知っているかもしれない。ITmediaの超人気連載「最強最速アルゴリズマー養成講座」の筆者が彼だからだ。 Microsoftが全世界の学生を対象に毎年開催している技術コンテスト「Imagine Cup」の2008年度大会で、当時まだ成人になったばかりの彼は、アルゴリズム部門に日本代表として参加、並みいる強豪を押さえて世界第3位に入賞し、その非凡な才能を世に知らしめた。 その後、慶應義塾大学環境情報学部に通う傍
アルゴリズマーのそだてかた - chokudaiのブログ
日本発の「Topcoderトレーニング講座」は最強最速アルゴリズマーへの最短経路 こんな記事も出して貰えたところですし、凄く簡単に、自分の中での教育論みたいな部分を少し話してみようかと思います。 ある物事を習得するのに必要なのは何か？という話をした時に、僕が絶対に必要だと思っているのは、「すげぇ！！」ってなることだと思っています。当然だとは思いますが、せっかくなので具体例を見ていきましょう。 Wikipediaにおける、動的計画法の記事を見ると、このようになっています。 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法である。分割統治法がトップダウン的な手法であるのに対し、
遺伝的アルゴリズムの紹介 - 人工知能に関する断創録
2001年の勉強会で発表した遺伝的アルゴリズムの紹介資料です。HDDをあさってたら見つけたので一応記録。ほんのさわりです。最近の研究ではどこまで進展したんでしょうね？遺伝的アルゴリズムって複雑系と人工生命の文脈で捕らえるのが面白いのに、研究だとただの探索アルゴリズムになっちゃうのが悲しかった。 はじめに 遺伝的アルゴリズム（Genetic Algorithm:GA）とは、生物進化（自然選択、突然変異）から着想を得た汎用的な探索手法です。探索というのは、たくさんの解の候補がある中から、最も良い解を探すことです。つまり、GAとは解の候補から最もよいものを探すのが目的と考えられます。 歴史的背景 GAは、1975年、Hollandによって初めて導入されました。当時は、「なぜ進化のような何十億年もかかるプロセスの真似をするのか？」という反応が多かったらしいです。しかし、その後のGoldbergの研
第12回 検索アルゴリズムを分析してみよう！（6）YahooとGoogleが提携 | gihyo.jp
この連載もいよいよ最終回となりました。今回はYahooとGoogleの検索アルゴリズムの違いや、ビッグキーワードとスモールキーワードにおける違いを取り上げます。 YahooとGoogleが提携 YahooとGoogleの違いを話そうと思っていたところへビッグニュースが発表されましたね。2010年7月27日、GoogleがYahooに検索エンジンのライセンスを供与すると発表されました。現在、急ピッチで移行作業が行われており年内にもYahooの検索結果が変わる可能性があります。最終的にどのような形になるのか、まだはっきりしたことはわかりませんが、いずれにせよGoogleの検索結果がベースとなり、そこにYahoo独自の味付けがなされるようです。 これまで国内のSEO業界において、検索アルゴリズムの話題はYahooが中心でした。それはYahoo検索の利用者がGoogleよりも多いことに加え、Yah
「どうぶつしょうぎ」の完全解析
田中哲朗 女流棋士の北尾まどか初段によって考案されたボードゲー ム「どうぶつしょうぎ」の初期局面 から(相手のライオンを取れる時は必ず取るという条件で)到達可能な局面すべ てを求め，後退解析(retrograde analysis)により，すべての局面の「勝ち」/ 「引き分け」/「負け」と双方最善を尽くした時の手数を求めるプログラムを作成 しました． ゲーム情報学研究会での発表について 2009年6月26日に開催された第22回ゲーム情報学研究会で発表した際の資料と，プレゼンテーション資料を置きます． なお，資料の図5に誤りがあります．正しい図は， となります． プログラム dobutsu-src.tar.gzを展開すると，dobutsuというディレクトリができます．その下のMakefileを適当に修正してmakeするといくつかの実行ファイルができます．以下に簡単な説明を書きます make
ナイーブベイズを用いたテキスト分類 - 人工知能に関する断想録
今までPRMLを読んで実装を続けてきましたが、10章からは難しくて歯が立たなくなってきたのでここらで少し具体的な応用に目を向けてみようと思います。機械学習の応用先としては画像の方が結果を見ていて面白いんですが、当面は自然言語処理を取り上げます。そんなわけで一番始めの応用は機械学習と自然言語処理の接点として非常に重要なテキスト分類（Text Classification, Text Categorization）の技法たちを試していきたいと思います。テキスト分類は文書分類（Document Classification）という呼び方もあります。テキストと文書は同じ意味です。最初なので自分の知識の整理と入門者への紹介のためにちょっと丁寧にまとめてみました。 テキスト分類とは テキスト分類とは、与えられた文書（Webページとか）をあらかじめ与えられたいくつかのカテゴリ（クラス）に自動分類するタス
動画で見る最新CG研究特集 | Security.GS Magazine
maaaaakunです。 僕はコンピュータフラフィクスを主な研究対象とする研究室に所属しています。 そこで今回は最新のCG研究の中から僕がすごい！と思ったものを独断と偏見で紹介します。 詳しい内容は。。。理解してません！！難しいよ！なので動画付きです。見て楽しみましょう。 （CG系で最高峰の学会であるSIGGRAPHに採択されている論文の内、過去3年分くらいから選びました。） ①PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing ・これは、画像中の選択領域と似た領域を探す、高速な手法について述べてあります。高速化すると何が良いかというと、インタラクティブに操作できるようになる、といったことが挙げられます。 建物を違和感なく増やしたり、形を変形できたりします。すごい。。。
学習アルゴリズムの学習曲線 - yasuhisa's blog
パーセプトロンの収束定理くらいまでかな?と思っていたらあんまり知らないような内容まであってびっくりした。アルゴリズムに対する学習曲線というものを導入し、統計力学の手法を使って解析する。次元数と例題数を無限大に飛ばすと0に行くんだが、問題はそのスピード。もちろん早いほうがいい。 バッチでやった場合の最小二乗法とか最尤推定に対する学習曲線はになるらしいが(ここでTはサンプル数)、パーセプトロンなどに対してこいつがどうなるか考える。(もう解き方とか覚えていない)微分方程式とパラメータにガウシアンを仮定してあげると解が閉じた形で出てくる(のでなかなかびびる)。解はということで、バッチより大分遅いことが分かる。パーセプトロンは間違ったときの情報しか使っていないから、正解したときの情報も使ってあげましょうという考え方がヘブ学習。そういえば、@tkf君とかが前再帰的なニューラルネットワークとかやっていた
やねうら王 公式サイト
本サイトのメインコンテンツ やねうら王 — 棋力的にトップ集団の将棋ソフトに比肩する将棋ソフト やねうら王オープンソースプロジェクト — やねうら王miniから最新のやねうら王までのソースコードと思考エンジン本体 ふかうら王 — Deep Learningを採用した新しい時代の将棋ソフト たけわらべ — 利きだけを理解している新しい感覚の将棋ソフト Stockfish完全解析 — コンピューターチェスの強豪ソフトStockfishの完全解析 将棋電王戦 — 株式会社ドワンゴ主催の将棋電王戦。やねうら王は４年連続出場 コンピューター将棋全般 — コンピューター将棋全般の話題 プロコン — CODEVSなどプログラミングコンテストの話題 なお、この記事のここから下には新着記事が表示されています。
記憶制限準ニュートン法、最適化手法の相互の関連性、そして私が感じたこと - yasuhisa's blog
授業を聞いててなかなか興奮したので、これまでのおさらいとともにメモメモ。 ニュートン法ニュートン法は目的関数を2次で近似したものだったが、目的関数が2次でないと、ヘッセ行列が正定値行列になるとは限らず、ニュートン方向が降下方向になる保証がない。なので、実用上は、降下方向になるような他のアルゴリズムで動かしながら、最適解の近くにきたなーと判断すれば、ニュートン法に切り変えるということがされていたりするらしい(局所二次収束性を持っているから、最適解の近くだと収束が非常に速い)。 準ニュートン法準ニュートン法は、ニュートン法の欠点である「降下方向になるか分からない」という欠点をどうにかしよう、という考えのもと作られたアルゴリズム。目的関数の勾配方向になるようなベクトルを作り出してやる。そのときに、勾配をテーラー展開によって近似し、ヘッセ行列の近似を計算できるようにした*1。このときに、セカント条
3日で作る高速特定物体認識システム (3) SURFの抽出 - 人工知能に関する断創録
3日で作る高速特定物体認識システム (2) SIFT特徴量の抽出（2009/10/24）の続きです。あっ、3日経っちゃいました。 今回は、SIFTとは別の局所特徴量であるSURF（Speeded Up Robust Features）を抽出してみます。SURFのFはFeaturesなのでSURF特徴量とは言わないのかな？SIFTとは抽出方法は違いますが、画像からキーポイントと特徴ベクトルを抽出する点では同じです。抽出速度はSIFTより数倍高速だそうですが、精度は多少落ちるとのこと。リアルタイム処理したいときはこっちのほうがよさそうです。また、OpenCVにもすでに実装されています。SURFの詳しいアルゴリズムは後で論文を読むとしてとりあえず試してみます。 画像からSURFを抽出する 以下のプログラムは、画像からSURFを抽出して特徴点を描画し、特徴量をファイルへ格納するプログラムです。この
ディリクレ過程とディリクレ過程混合モデル - yasuhisa's blog
多項分布とディリクレ分布NLP関係、特に言語モデルなどでは多項分布がよく使われる(N個のデータがあったときに、Aに1つ、Bに3つ…というような感じ)。言語モデルを作るときにはゼロ頻度問題が常に問題となるので、多項分布のパラメータを最尤推定で求めたものを使っては危険。なので、バックオフをするなど、discountingをするのが普通である。この問題をベイズ流に解決しようとすると、事前分布を置くということになる。多項分布の共役事前分布はディリクレ分布となっていて、ここに二つの分布の関係性が出てくる(see also PRML2章)。 通常のパラメトリックベイズモデルにおける混合モデルベイズ推定では、なんでも確率変数と考えて事前分布をおいたりできることから、パラメータの分布、その事前分布というのを考えることができた。ここで、一歩高い視点から見てみることにしよう。どういうことをやるかというと、「確
3日で作る高速特定物体認識システム (2) SIFT特徴量の抽出 - 人工知能に関する断創録
3日で作る高速特定物体認識システム (1) 物体認識とは（2009/10/18）の続きです。 今回は、画像からSIFT (Scale-Invariant Feature Transform) という局所特徴量を抽出するところを作ってみようと思います。 SIFT特徴量の抽出 まずは、局所特徴量の代表ともいえるSIFTを試してみます。OpenCVにはSIFTを抽出する関数がなかったのでRob Hess氏がC言語で実装したライブラリを試してみます。内部でOpenCVを使っているので事前にOpenCVのインストールが必要です。実装はOpenCV 1.1でされているみたいですが、2.0でもちょっと手直しすると動きました。Rob Hess氏のホームページからSIFT Feature Detectorのzip版を落とします。 （注）Hess氏のサイトが更新されたようで現在はGitHub上のOpenSIF
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室