次元が高い場合に関してのsimhashの計算

論文 IR

最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介してあったので少し解説を行ってみる。ちなみに以下の解説では低次元のビットベクトルに縮約した後にハミング距離が近いものをどうやって探索するかについては述べないです、それに関しては[1],[2]を参照してください。

ちなみに自分が実装したのは各ビットごとに次元に対するハッシュ関数を定義して計算する方法でした。この方法だと以下で開設する手法よりもf倍の回数ハッシュ関数を計算する必要があるので実行時間が割とかかる。

解説

simhash[3](文献によってはLSHと呼ぶこともある[2])は次元削減の手法の一つで、高次元のデータを低次元のビットベクトル([1]では64bitとしている)に変換する手法である。

この手法の応用例としては大量の文章データからの関連文章の検索、webのクロール時に重複したページに関してインデックスへの格納を行わないなどがある。

いまD次元のベクトルxをf次元のビットベクトルにsimhashを用いて次元削減を行うことを考える。

  1. 初期化処理としてf個のD次元のランダムなベクトルr_i(i = 1...f)を生成する
  2. xとr_iの内積を生成する
  3. 内積の値の符号により定まるビットベクトルBを返す
    • B_i = > 0のとき1，otherwise 0

ここで，D次元のベクトルx，yをsimhashを用いてハッシュ化したものをv，wとするとxとyのコサイン類似度が近ければvとwのハミング距離が近くなるという性質がある。なぜそうなるかに関しては文献[2]，[3]を参照されたい。

この方法の欠点としてはDが非常に大きいときにはf個のD次元のランダムなベクトルを生成するコストが大きいという点がある。
これを解決する方法が文献[1]では紹介されている。

  1. xの各次元iに対して適切なハッシュ関数hを用いることによってf bitのハッシュ値を生成できるものとする。
  2. f次元のベクトルVの値を0で初期化する
  3. for i \in xの非ゼロな次元
    1. H = h(i)
    2. for j \in (0..f)
      • H[j]が1ならV[j] += x[i]とする、そうでなければV[j] -= x[i]
  4. 最終的にVの各要素の正負によりsimhashの値を生成する。

例えばD=3、f=2のときに次元0が10，次元1が01，次元2が11とハッシュ化されたとする。またx=(3.0 , 2.0 , 4.0)とする。このときにVの値は

V[0] = 3.0 - 2.0 + 4.0 = 7.0
V[1] = - 3.0 + 2.0 + 4.0 = 3.0

でsimhashの値は11となる。

これはr_iとして

(1.0 , -1.0 , 1.0)
(-1.0 , 1.0 , 1.0)

を選択しているのと同じである。

この方法の利点としては各次元に関するハッシュ関数が与えられれば実際にランダムなベクトルを生成しなくてもsimhashが計算できるという点である。このためDが大きい場合でもメモリの追加の使用量を抑えることが可能となる。

参考文献

  • [1] Gurmeet Singh Manku ，Arvind Jain， and Anish Das Sarma． "Detecting near-duplicates for web crawling"， Proceedings of the 16th international conference on World Wide Web, 2007．
  • [2] Deepak Ravichandran ， Patrick Pantel， and Eduard Hovy． "Randomized algorithms and NLP: using locality sensitive hash function for high speed noun clustering"， Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics，2005．
  • [3] Moses S. Charikar．"Similarity estimation techniques from rounding algorithms"，Proceedings of the thiry-fourth annual ACM symposium on Theory of computing，2002．