non-Negative Matrix Factorization (NMF) - naoyaのはてなダイアリー
以前に Latent Semantic Indexing (LSI) や HITS 絡みで SVD や主成分分析について少し書きました。 http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing http://d.hatena.ne.jp/naoya/20090301/hits LSI では SVD を使って単語文書行列を分解し、低階数近似を行います。これにより、似たような次元をまとめたりといった効果が得られるのでした。自分の考察では HITS も同様のことを行っているという認識でした。 さて、集合知プログラミングを読んでいたら、第10章で "non-Negative Matrix Factorization" (非負値行列因子分解, 以下NMF) という手法が出てきました。NMF も SVD や主成分分析に同じく行列を分解
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」：最強最速アルゴリズマー養成講座（1/3 ページ） 典型的なアルゴリズムをたくさん知っている人間が最強か――？ いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。 アルゴリズマー養成講座と銘打ってスタートした本連載。もしかすると読者の方の興味は、はやりのアルゴリズムや汎用的なアルゴリズムを知ることにあるのかもしれません。しかし、今回は、いわゆる「典型的なアルゴリズム」を用いずに進めていきたいと思います。 なぜ典型的なアルゴリズムを用いないのか。それは、典型的なアルゴリズムばかりを先に覚え、それだけでTopCoderなどを戦っていこうとした場合、それに少しでもそぐわない問題が出た場合に、まったく太刀打ちできなくなってしまう
類似画像検索システムを作ろう - 人工知能に関する断創録
C++版のOpenCVを使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのスクリプトはPythonを使ってますが、PerlでもRubyでも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。GoogleやYahoo!のイメージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエリに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、最新のサーベイ論文（Datta,2008）を読むと1990年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます
ぜひ押さえておきたいコンピューターサイエンスの教科書
僕はバイオインフォマティクスという生物と情報の融合分野で研究を行っています。東大の理学部情報科学科にいた頃は同僚のマニアックな知識に驚かされたものですが、そのような計算機専門の世界から一歩外に出ると、それが非常に希有な環境だったことに気が付きました。外の世界では、メモリとディスクの違いから、オートマトン、計算量の概念など、コンピューターサイエンスの基礎知識はあまり知られていませんでした。コンピューターサイエンスを学び始めたばかりの生物系の人と話をしているうちに、僕が学部時代に受けた教育のうち、彼らに欠けている知識についても具体的にわかるようになってきました。 バイオインフォマティクスに限らず、今後コンピュータを専門としていない人がコンピューターサイエンスについて学ぶ機会はますます多くなると思われます。そこで、これからコンピューターサイエンスを学ぼうとする人の手助けとなるように、基礎となる参
Yaneu Labs --- コンピュータ将棋プログラムをLISPで書く
*[hatefu:labs.yaneu.com/20090905/] コンピュータ将棋プログラムをLISPで書く 「コンピュータ将棋プログラムをLISPで書く」と言うとコンピュータ将棋開発関係者にすら完全にネタかと思われているのが実状ではあるが、私はこれを機にその誤解を解いておきたい。 ここでは、私がC#で書いたLISPエンジンのソースを公開し、これが実際にコンピュータ将棋プログラムの開発において非常に有効であることを示す。 * YaneLisp version 1.10 今回の記事はあまりに長文なので最後まで読む前に眠くなる人のために、まず始めに私が実装したLISPのバイナリとソースを配布しておく。ライセンスはNYSLとする。 勢いに任せて実装したので、かなり雑な作りだが、必要ならばC#側で関数を追加するなりすればいいと思う。このLISPの製作に要した時間は丸2日ぐらい。 # YaneL
オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 プログラムの実行時間 業務としてプログラミングをされている方には釈迦に説法かもしれませんが、プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。そしてこれは、TopCoderなどのコンテストでプログラムを組む際にもよく当てはまります。通常、こうしたことは感覚的に理解している方がほとんどだと思いますが、具体的にどれくらいのループを回すと何秒掛かる、といった基準を持っている人は少ないのではないでしょうか？ 非常に基本的なことですが、プログラムの実行時間に関して再確認しておきたいと思います。 TopCoderの制限に関して TopCoderでは、実行時間およびメモリ使
γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
Googleのページランクにも使われているマルコフ連鎖を利用して文章を要約、もしくは意味不明にする「マルコフ連鎖ジェネレーター」
かの有名な検索エンジン「Google」にはページランクという概念がありますが、そのページランクを支える理論の一つがこの「マルコフ連鎖」というもの。さまざまなジャンルに応用されていることでも有名で、人工知能ならぬ「人工無能（いわゆるチャットボット、会話ボットなど）」にも使われることがあります。 で、このマルコフ連鎖を利用して文章を要約、もしくは意味不明にしてくれるのが「マルコフ連鎖ジェネレーター」というわけです。 詳細は以下から。 マルコフ連鎖ジェネレーター http://itog.sakura.ne.jp/markov/ 意味不明モードか要約モードのいずれかを選び、文章を貼り付けて「ジェネレート」をクリックするだけです 吉野家コピペの場合、こうなりました。 そんな事より１５０円だよ、ちょいと問いたいだけちゃうんです。女子供は、お前、１５０円やるから店員に来てあるんです。もう見てない、１５０
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
マルコフ連鎖で日本語をもっともらしく要約する - ザリガニが見ていた...。
そもそも、マルコフ連鎖とは何なのか？全く聞いたこともなかった。そして、文章を要約するのはとっても高度なことだと思っていて、自分のレベルではその方法を、今まで思い付きもしなかった。 しかし、以下のようなシンプルなRubyコードでそれが出来てしまうと知った時、目から鱗である...。一体、何がどうなっているのだ？コードを追いながら、マルコフ連鎖を利用するという発想の素晴らしさを知った！ 作業環境 MacBook OSX 10.5.7 ruby 1.8.6 (2008-08-11 patchlevel 287) [universal-darwin9.0] mecab utf8環境でインストール済み マルコフ連鎖に出逢う rssを流し読みしていると、以下の日記に目が止まった。（素晴らしい情報に感謝です！） MeCabを使ってマルコフ連鎖 一体何が出来るコードなのか、日記を読んだだけではピンと来なかっ
Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
ネットワークプログラムのI/O戦略 - sdyuki-devel
図解求む。 以下「プロトコル処理」と「メッセージ処理」を分けて扱っているが、この差が顕著に出るのは全文検索エンジンや非同期ジョブサーバーなど、小さなメッセージで重い処理をするタイプ。ストリーム指向のプロトコルの場合は「プロトコル処理」を「ストリーム処理」に置き換えるといいかもしれない。 シングルスレッド･イベント駆動 コネクションN：スレッド１。epoll/kqueue/select を１つ使ってイベントループを作る。 マルチコアCPUでスケールしないので、サーバーでは今時このモデルは流行らない。 クライアントで非同期なメッセージングをやりたい場合はこのモデルを使える： サーバーにメッセージを送信 イベントハンドラを登録；このときイベントハンドラのポインタを取っておく イベントハンドラ->フラグ がONになるまでイベントループを回す イベントハンドラ->結果 を返す １コネクション１スレッ
GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ
GT Nitro: Car Game Drag Raceは、典型的なカーゲームではありません。これはスピード、パワー、スキル全開のカーレースゲームです。ブレーキは忘れて、これはドラッグレース、ベイビー！古典的なクラシックから未来的なビーストまで、最もクールで速い車とカーレースできます。スティックシフトをマスターし、ニトロを賢く使って競争を打ち破る必要があります。このカーレースゲームはそのリアルな物理学と素晴らしいグラフィックスであなたの心を爆発させます。これまでプレイしたことのないようなものです。 GT Nitroは、リフレックスとタイミングを試すカーレースゲームです。正しい瞬間にギアをシフトし、ガスを思い切り踏む必要があります。また、大物たちと競いつつ、車のチューニングとアップグレードも行わなければなりません。世界中で最高のドライバーと車とカーレースに挑むことになり、ドラッグレースの王冠
アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー
アルゴリズムイントロダクションの輪講で、第24章の単一始点最短路問題を担当しました。発表に使った資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/090622_shortest_paths.ppt SlideShare はこちら。フォントの関係でグラフが崩れたりしているので、ppt で参照した方が見やすいかと思います。 Introduction to Algorithms#24 Shortest-Paths ProblemView more OpenOffice presentations from Naoya Ito. 単一始点最短路問題は、重み付き有向グラフの最短路木を求める問題です。各頂点に最短路重みを記録するのですが、はじめに各頂点の重みを∞として、「緩和」と呼ばれる操作により徐々に頂点の重みを最短路重みに近づけていく、というの
軽量データクラスタリングツールbayon - mixi engineer blog
逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
OpenGLの基礎
OpenGLは，3次元グラフィクスプログラミングにつかわれる標準的なライブラリです． ライブラリとは，プログラムの部品セットであるといえます． ライブラリを利用することで，自分で0から書かなくても， ライブラリが提供する部品を組み合わせることでプログラムを作成することができます． ここでは，OpenGLの基礎を説明します． OpenGLの概要 Ruby/OpenGL OpenGLプログラムの基本的な構造 イベント，コールバック，イベントループ 2次元図形の描画 図形プリミティブ 属性 2次元ビューの設定 ビューポート OpenGLの概要 OpenGLは，3次元グラフィクスプログラミングにつかわれる標準的なライブラリで，SGI(Silicon Graphics, Inc.)がGLという同社のコンピュータ専用のグラフィクスライブラリをもとに開発したものです． OpenGL以外でよく用いられる3
大都会の夜景をコンピューターによって完全自動で描画するムービー
ハリウッド映画のCGシーンは何人ものCGアーティストが、高価な機材を何台も使って手作業で作成されるために、予算が高騰している要因の1つにもなっているほどですが、これらのCGにも勝るとも劣らない大都会の夜景をどこにでもあるコンピューター1台だけで生成してみた人がいます。 手作業でテクスチャーを描いたり、グラフィックボードに搭載されているピクセルシェーダーのように、外部のプログラムを用いて特殊な効果を与えるなどの手間をかけることなく、内部のプログラムが自動で生成するポリゴンとテクスチャのみを用いて壮大な夜景が生成されています。いかに単純な仕掛けで人間の目をだましてものすごい映像を作り出すか、よいヒントになるかもしれません。 詳細は以下。 Twenty Sided >> Blog Archive >> Procedural City, Part 1: Introduction このプログラムはS
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
