Blog
はじめまして伊藤です。１月から PFI で働いてます。
今回は関連事例の抽出技術についてお話しします。関連事例の抽出は推薦（レコメンド）サービス等で利用される技術です。ここで事例は扱う対象によって異なります。対象が文書集合であれば、事例は文書を表しますし、E-コマースサービスのログデータであれば、サービスを利用するユーザを表します。
関連事例の抽出技術はデータマイニング分野を含め多くの分野で盛んに研究がなされていて、関連文献をリストアップするだけでも大変です。私は学生時代からずっと推薦技術に関する研究をしてきたのですが、卒業後もその年々の重要そうな（自分が興味が持てる）論文を選んで勉強してます。では推薦関係で調査しておくべき会議とはどのようなものがあるでしょうか。私の場合以下の会議で受理された論文をチェックしています（他におすすめがあれば、お知らせいただけると幸いです）。
データベース分野
- VLDB, ICDE
データマイニング分野
- KDD, ICDM, CIKM, PKDD, SIAM Data Mining
人工知能 / 機械学習分野
- AAAI, NIPS, ICML
検索分野
- SIGIR
重要な手法は上記の会議の論文では提案されていなくても、多くは参考文献として紹介されているためだいたい時代についてゆけます。
こんな方法でサーベイをしていてすばらしいと感じた推薦手法の一つに Locality Sensitive Hashing (LSH) があります (残念ながら上記の会議リストに入っていません)。
Indyk Piotr and Motwani Rajeev. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In: Proc. of Symposium on Theory of Computing. 1998.
LSH は各事例にハッシュ関数を適用するという単純な手法で、その単純さから高速に動作します。さらに MapReduce 上での実装も簡単で、億単位の事例に対応できます。自分も Hadoop 上で動作する実装を作ってみて検証しましたが、期待通り非常に高速に動作しました。
では LSH は銀の弾丸なのでしょうか？ 残念ながら違うと感じています。LSH はパラメタの値をきつめに設定すると全く関連する事例が抽出できなかったり、逆にパラメタを緩めるとあまり関連しない事例が大量に抽出されすぎてしまうことがあります。
そこで注目しているのが空間木を利用する手法です。空間木は古くから研究されている分野で、その名の通り空間を木で表現した上で、距離の近い事例を抽出するのに利用します。現在までに R-Tree, KD-Tree 等々、数多くの空間木が提案されています。その中に以下で紹介する Spill-Tree という手法も存在します。以下 Spill-Tree に関する論文です。
Ting Liu, Andrew Moore, Alexander Gray and Ke Yang. An Investigation of Practical Approximate Nearest Neighbor Algorithms. NIPS. 2004.
この Spill-Tree は Metric-Tree の簡単な拡張です。 Metric-Tree では入力空間を最もうまく分けることができる超平面で空間を再起的に分割します。超平面の選択はいくつか方法がありますが、高速に行う手法が既に提案されています。
たとえば以下の図ではデータセットを超平面で二つの部分空間に分割しています。本来は分割された部分空間をさらに別の超平面で再起的に分割して一定の深さを持つ木を生成します（木の深さをパラメタとして与えます）。
この分割された空間を走査して関連する事例を抽出することを考えます。通常関連する事例を見つけたい事例が分割面のどちらかにあるかをたどるだけで、関連する事例が抽出できます。しかし事例が分割された空間の近くにある場合に問題が発生します。例えば図の点Aの関連する事例を抽出することを考えると、同一の葉ノードに最も関連する事例の一つである B が存在しません。その結果得られる関連事例の Recall が低下する恐れがあります。この問題に対応するために、木の走査をバックトラッキングしながらおこなうことが考えられるのですが、Spill-Tree はこの問題のシンプルな解決法を提供します。
Spill-Tree は Metric-Tree と同様に空間を分離するのですが、分離される部分空間が重複（オーバーラップ）します。例えば、先の例で Spill-Tree を作成すると以下の図のようになります。
では先ほどと同じように利用した事例 A の関連事例を抽出することを考えます。このとき Spill-Tree では分離平面の近傍にある事例 B は両方の部分木に存在する点が重要です。 事例 B は A が属す部分空間 (小ノード) にも存在するため、バックトラックすることなくAの関連事例として抽出できます。
この Spill-Tree を MapReduce 上で動作させて、さらに大規模データに対応できるように拡張した手法が存在します。
Ting Liu, Rosenberg, C. and Rowley, H.A. Clustering Billions of Images with Large Scale Nearest Neighbor Search. Applications of Computer Vision. 2007.
この論文の手法でははじめに入力データの一部をランダムに生成して上位の木を作り、その後各Hadoopインスタンス上で部分木を生成します。せっかく勉強したので近いうちに Hadoop 上で実装して LSH と比較してみようと考えています。
Tag
