(論文メモ) Evaluating the Impact of Coder Errors on Active Learning / ACL-HLT 2011
木曜日, 6月 23rd, 2011ACL-HLT 2011 から面白そうな論文2件目。
出典情報: P11-1010: Qixia Jiang; Maosong Sun, Semi-Supervised SimHash for Efficient Document Similarity Search, ACL-HLT 2011
MinHashじゃなくてSimHashなんてものがあったのね。
前置き
N次元特徴ベクトルとして表現することで対象間の類似度を求める
機械学習の多くがそうですが、何かを解析しようと思った場合にはその対象をN次元の特徴ベクトルとして表現することが多いです。どのようにベクトル化したら良いのかは腕の見せ所ですが、適切なベクトル化が実現できるなら、後はそのベクトル同士がどのぐらい似ているか（距離が近いか、角度が近いか、大きさが近いか、etc.）といった問題に落とし込むことができます。同一ベクトル空間に存在する（同じ土俵にいる）なら、その空間上でどのぐらい似ているかを計算（類似検索や近傍探索など）することで「関連商品」とか「類似画像」とかを求めやすくなるわけですね（＊注1）。そのベクトル間類似度を図る指標にはJaccard係数やTanimoto係数等の様々な方法が提案されています。
計算コストを抑えるために擬似的な類似度を高速に求める
ここではそれらを用いて類似度を測れるということが分かっている場合の話（もし図れないのなら適切な類似度を測れる指標自体を考える所からやる必要がある）。ちゃんと図れるんだけど、検索エンジン等の大規模なデータ集合に対して計算する必要がある場合、その計算量が馬鹿にならず事実上そのままでは使えません。それを擬似的に高速に求めましょうというのがMinHashです。MinHashを更に改良した話もこのブログに紹介されていますね。
局所的に鋭敏に反応するハッシュ関数群を用いる手法: LSH
今回この論文タイトルにでている SimHash も基本はハッシュ関数を使ったもので、別名 LSH (Locality Sensitive Hash) とも呼ばれているらしい。正確にはLSHの一例がSimHashということらしい。先に紹介したMinHashもLSHの一例。いずれにせよLSHなら聞いたことあるよー（＊注2）。（SimHashってなんだろうと気になって選んだのでこの時点で興味が半分薄れてしまった）
SimHash(LSH)は、「類似度の高い特徴ベクトル同士は同じハッシュ値になりやすい」ように設計されたハッシュ関数を使うことで「最近傍探索」することで類似度計算を近似しましょうというもの。LSHで良く耳にする実装例としてLikelike（リケリケ、と呼ぶらしい）があります。一種のクラスタリングともみなせるけどかなり特殊で、「同じハッシュ値になるものは似ている事例」にはなりやすいけど、所詮ハッシュ値なので「ハッシュ値」そのものには意味が無く、「近いハッシュ値」に該当する事例が似ているかどうかは相関が無い(はず)のがちょっと残念。（クラスタリングなら各クラスタからの距離を計算することでどのぐらい似ているかの指標を計算することもできる）
論文タイトルには「Semi-Supervised SimHash」とあるので、完全に自動化した手法ではなく、例えば先の能動学習のような形で半自動的にSimHashする手法を提案するというのが趣旨なのかなと想像。LSH良く分からないけど。
アブスト読む限りでは「教師無しLSHは性能が十分じゃない。かといって教師ありLSHでも類似ドキュメントを検出するには十分ではない（ハッシュ値が近いからと言って似ているという話にはならないので、同じハッシュ値にならないと類似ドキュメントとして検出できない）。そこで、類似データが同じハッシュ値となりやすいように事前に重み調整してやることで精度改善を目指す」みたいなことを提案しているらしい。
なんとなく大枠は分かったし、これ以上はLSH/SimHash自体をちゃんと勉強してからじゃないと理解し難そうなので、今回はここまで。
＊注1: 適切に特徴ベクトルそのものを(半)自動生成することはできないのだろうか。
＊注2: 上記注1に関連して、「ランダムにハッシュ関数を大量生成して特徴ベクトルそのものを自動生成するために利用できないかなー」とか考えてるのだけど、どうなんだろう。既に作られてる特徴ベクトルから有益な特徴空間に圧縮するという話ではなくて、ベクトル化される前の生データ（文章だったり写真だったり音声だったり）から自動生成させたい。