Blog
年が明けてもう一ヶ月経ちましたね．岡野原です．
今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）．
今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかってきました．
こうした特徴ベクトルは数万から数億次元と非常に高次元でありますが，1の割合が非常に少ない疎なベクトルです．このベクトルは1が立っている位置の集合で表すことができます．例えば1010001という特徴ベクトルは1番目と3番目と7番目のビットが1なので，{1, 3, 7}という集合で表すことができます．以降ではバイナリベクトルと，集合表現を適宜使いわけて特徴ベクトルを表すことにします．
今回解きたい問題は，まず大量データがそれぞれ特徴ベクトルに変換されているとします．そして，クエリの特徴ベクトルqが与えられた時にqと似ているDB中の特徴ベクトルをいかに速く求めるかです．似ているかどうかの尺度は基本的には共通の位置に1が立っている個数が多ければ似ているという考えでよさそうですが，それだと，全部の位置に1が立っているベクトルがどれとも近くなってしまいます．ですので，元々1が立っている個数で割ってあげればよさそうです．この考えに基づくのがJaccard係数（またはresemblance）です．
Jaccard係数: \(sim(v, q) = |v \cap q| / |v \cup q|\)
両方のビットが完全に一致するのであれば1となり，そうでない場合は0以上1未満の値をとります．
他に有名な例としては，コサイン類似度があります．これは二つのベクトルの間の角度で近さを測ります．
コサイン類似度: \(cos(v, q) = |v \cap q| / \sqrt{|v||q|} \)
割る値が違いますが、どちらの類似度を利用しても多くのタスクでは違いはさほど無いです．今回は前者のJaccarad係数を考えることにします．
クエリとDB中全ての特徴ベクトルの間のJaccard係数を求めるにはDBのサイズが非常に大きいと困難になってきます．DB中の要素数が数千万とか数百億とかそういうオーダーを処理する機会も珍しくはありません．
これに対してあらかじめDBに対して索引を構築して計算を高速化をしようとするのは自然な考えです．転置ファイルを構築したりLocality Sensitive Hashを構築する方法などが提案されていました．
今回紹介するMinHashは，こうした方法の一つです．大きな長所として特徴ベクトルの次元数が前もって分からない場合（加算無限）でも高速に動くこと，索引構築が各要素毎に独立に実行でき並列化が用意であること，そして索引自体が非常にコンパクトに保存できることが上げられます．
MinHashのアイディアは非常に単純です．はじめに，適当なハッシュ関数hを用意します．（ハッシュ関数の値域は十分に大きく，衝突しないとします）．次にv中の各値をハッシュ関数を利用し，ハッシュ値\(h(a_1), h(a_2), \ldots\)をもとめます．最後に，これらのハッシュ値の最小値\(\min \{ h(a) | a \in v \} \)を記録します．
さて，ランダムにハッシュ関数をとってきた時，二つの集合v, wのハッシュ関数による最小値が一致する確率 はどのようになるでしょうか．これが実はJaccard係数に一致します．
\(sim(v, w) = P(\min \{ h(a) | a \in v \} = \min \{ h(b) | b \in w \} ) \)．
これが成り立つ理由を説明するのは例がいいということで，v={2,5,7,9}, w={1,2,4,7,10}の場合を考えてみます．まず\(v \cup w = \{1, 2, 4, 5, 7, 9, 10 \}, v \cap w = \{ 2, 7 \}\)です．ハッシュ関数の値を利用してこれらの値をソートすることは，これらの要素をランダムにシャッフルすることと同じです．そして，最小の値というのは，シャッフルした結果先頭に来た値のことをさします．さて，二つの要素のハッシュ値の最小値は一致するということはv, wの要素をそれぞれランダムシャッフルして{1, 2, 4, 5, 7, 9, 10}の順序をばらばらにした後に，先頭に{2,7}が来る場合です．これは2/7でJaccard係数そのものです．
この性質を利用することで，二つのベクトルのJaccard係数は，ランダムなハッシュ関数による最小値が一致しているかどうかの確率により求められます．
この確率を経験確率より推定するために，k個のハッシュ関数を用意し，それぞれk個の最小値\(m_1, m_2, \ldots, m_k\)を求めておき，これらが何個一致したかを求め，それをkで割った値をJaccard推定量にします．
真のJaccarad係数がRの時，この推定量のバイアスは0であり，分散は\(R(1-R)/k\)です．
MinHashの特徴は，元々の特徴量の次元数がわからなくても動く点です．しかも完全に分散して動かすことができます．ハッシュ関数だけ共有してもっていればそれぞれのマシンで独立して最小値を求めていくことができます．
元々はウェブクローラーの同一ページ判定に利用されていました．ページ中に出現する固定長の部分文字列全部に対してハッシュを求めてその最小値を記録しておき，それを利用して既に収集済みのウェブページと一致するかどうかを調べます．CRCなどと違って完全に一致していなくてもほとんど同じ場合（例えば広告枠だけが違うとかタイムスタンプだけ違うとか）でも同じページを見つけられるのが大きな違いです．
b-bit Minwise Hashing
さきほどまでの話は90年代後半頃までに確立されていましたが，近年，様々なデータが特徴ベクトルで表され，類似特徴ベクトルを高速に求める要望が高まるにつれ，MinHashに基づく方法もさらに進化をとげてきました．
一つの方法が b-bit Minwise Hasing[2][3]です．MinHashではハッシュ値が衝突しないようにハッシュ値の値域を大きめにとっていました．しかし，最小値しか記録しないとはいえ、これはサイズを多く必要とします．例えば一つの特徴ベクトルに対し64bitの最小値を10個記録すると80byte必要です．これが1億要素あると8GB必要で，メモリ上で処理するのはちょっと厳しくなります．
そこで，ハッシュ値の値域を小さくすることを考えます．例えば1ビットしか使わずハッシュ値に0, 1しか使わないことも考えられます．しかし，ハッシュ値の値域を小さくすると，今度はハッシュ値が衝突するようになって，さきほどのJaccard係数の導出に利用していた式が成り立たなくなります．でも，その分ハッシュ関数の量は増やすことができるかもしれません．
ハッシュ値にb bitだけ（b=1,2など）利用した場合にどのようにJaccard係数を求めることができるかというのをこういう計算が昔から得意なLiさんらが求めてくれました（導出は楽しいがやばい）．詳しい式は[2][3]を参照してください．式自体は長いですが，閉じた式なので式の通り実装すれば動いてくれます．基本的には，最小値が一致する確率に，ハッシュ関数が衝突して一致する確率の分が含まれるので，その分をさし引いたものが真に共通要素のハッシュ関数が最小値になる確率になります．それさえ求まればJaccard係数を導出することができます．
彼らの実験の一つではニュース100万記事中で（殆んど）同じ記事を同定するタスクにおいて，32bit使った場合と比較し，b-bitHash（b=1,2,4)では同じ精度を達成するのに1/10～1/20の容量しか必要しないということを報告しています．
b-bit Hashでは容量自体は減るのですが一つの要素自体に使うハッシュ関数の数は増えるので計算量はそのままだと増えてしまいます．それに対してもさまざまな実装上の改良も提案されています．例えばb=1の場合は，二つのハッシュ値が一致する個数は，ビットの値が一致する個数＝XORをとってpopcountなので高速に求めることができます．このあたりはSSEやGPGPUなどを利用しての高速化も可能そうです．
[1] “Fast subtree kernels on graphs.”, N. Shervashidze and K. M. Borgwardt. Proc. of NIPS 2010
[2], “b-Bit Minwise Hashing”, Ping Li, Arnd Christian Konig”, WWW 2010
[3] “b-Bit Minwise Hashing for Estimating Three-Way Similarities”, Ping Li, Arnd Christian Konig and Wenhao Gui, NIPS 2010
Tag
