« January 2009 | Main | March 2009 »

2009.02.25

レコメンド, LSH, Spectral Hashing

WEB+DB press vol.49にレコメンド特集の記事をtkngさんと書きました。

内容は最初は、協調フィルタリングやコンテンツマッチの簡単な話から、特徴量をどのように表すか、大規模データをどのように処理するかにいき、特異値分解などの低ランク行列分解によるレコメンドやRestricted Boltzmann Machineといった最近のnetflix prizeの上位の手法など、かなり突っ込んだ議論もしてます。

個人的には三章でLocality Sensitive Hash(LSH)について扱っているあたりがお勧めです。

レコメンドの内部の問題を極言すると、データというのは疎な高次元の数値ベクトル(数百万次元とか)で表され、クエリでベクトルが与えられた時、これと似たようなベクトルを探してこいという問題になります。”似たような”を数学的にいえば、クエリのベクトルとの内積(各ベクトルは長さ1に正規化されているとする)が最大となるようなベクトルを探して来いという問題になります。

この問題は結構厄介な問題で、近似無で解くには、索引(たとえばkd-treeや最新のcover tree)を作っても高次元の場合にはうまくいかないことが知られています。

これを近似有で高速に解こうというのがLSHを使った近傍検索です。LSHでは、高次元ベクトルを20~60bit程度のベクトルに写像するのですが、通常のhash関数はランダムに飛ばすのに対し、LSHは写像した先で内積をとっても、元のベクトルで内積をとったのと同じようになることが保障されているような関数になってます。似たベクトル同士は飛ばした先でも似たままで、似てないベクトル同士は飛ばした先でも似てないままです。

短いbitにさえ落してしまえば問題は簡単になります。例えば1回の内積の演算は数回のbit演算で解けますし、bit毎の転置ファイルなどいろんな索引を作って適当に枝狩りしながら探索するのも容易になります。

本ではLSHの作り方やその原理などを説明していたりするので興味のある方はみてみてください。

高度な話になってしまうため、本では書けなかったのですが、今LSHではSpectral Hashingが面白いです。
Y. Weiss, et. al. "Spectral Hashing", NIPS 2008 pdf

Spectral Hashingではよい写像を求める問題を制約付の最適化問題に帰着して解いています。制約それぞれは元の距離を保存する、各位置のbitは相関がない、写像後の符号では0と1が同程度出現するとかいったものに対応しています。この最適化問題はグラフ分割問題と同じでありNP完全ですが、緩和させて主成分分析をちょっと変更したものでとけます。

論文では8000万枚の画像tinyimagesを実験として使ってhashして似た画像を見つける例がのっていますが、ここまででかくなると、人の能力を超えている感じがしていいですね。

| | Comments (48) | TrackBack (1)

2009.02.14

宣伝

3月には国内の発表が連続してあります。
興味のある方は聞きに来てください。

- 言語処理学会年次大会 2009 @鳥取 (3/2~3/5) link

3月のはじめには毎年恒例の言語処理学会の年次大会が鳥取であります。
私は、任意(長さも自由)の部分文字列を特徴関数として使って文書情報を表して、その情報を利用してクラスタリングして、特徴的なフレーズで文書をまとめあげようというタスクを考えてやってみましたので、その発表をします。何か面白いデモがそれまでに作れればいいが

- 情報理工学系研究科・R2P/IST 1周年記念シンポジウム@東大本郷 (3/9) link

学生ベンチャーと博士課程を3年経験してどうだったかという話をします。この日記では、仕事のことはあまりふれませんでしたが、もうかれこれ3年以上、私はエネルギーの大部分をプリファードインフラストラクチャーという会社に注いで、純粋な開発から営業やらマネジメントからいろいろなことを経験してきました。私は研究者の卵として、研究の最先端も追っかけているのですが、そういう立場からみて、会社での仕事の中では、どのような問題に直面して、面白いことがあったかを短い時間ですが話せたらと思います。

- 人工知能基本問題研究会 SIG-FPAI 73@学習院大 (3/13-3/14)link
招待講演で、大規模データを利用した自然言語処理や機械学習について話します。具体的には最近のL1正則化学習のサーベイやら、オンライン学習やら、私が好きな簡潔データ構造とか拡張接尾辞配列などを利用して一見解けなさそうな計算量の問題(たとえば任意の部分文字列を特徴として文書を表しての文書分類)が実は効率的に解けるとかを話したいと思います

- 日本音響学会2009年春季研究発表会@東工大大岡山 (3/17 ~ 3/19) link
音響学会という、私の今までの分野と違うところで発表します。発表内容は階層木言語モデルというもので、最大エントロピー言語モデルと同じように任意の特徴が利用できながら、、学習・推定を劇的に高速化するために単語の分類問題を再帰的な二分問題にして、各問題のところでエントロピーモデルを使うというものです。スムージングができたり未知語があってもロバストに推定できて、いいことたくさんあるねという話を音声認識というタスクで測りましたという話です。

花粉がもう飛んでるので厳しいです。

| | Comments (7) | TrackBack (0)

« January 2009 | Main | March 2009 »