ゴクロの浜本です。ネットカフェでコードを書くのが好きです。
前回のエントリーでも触れられていますが、SmartNewsはホットな話題をユーザにお届けするために、常時、膨大な数のツイートおよびURLをクロールしています。こうして収集した記事に対し、様々な分析が施されますが、その中でも重要な処理の1つに、記事の類似度判定があります。内容の似通った記事をインデックスから発見し、グループ化する処理です。
毎秒、大量の新着記事が到着することから、この類似度判定は高速に実行する必要があります。また、インデックスを全てメモリに載せているので、類似度判定を実現する際の空間効率も要求されます。
今回は、SmartNewsが高速かつ省スペースな類似度判定のために使用しているb-Bit MinHashと呼ばれる手法を紹介します。2年前に、PFIの岡野原さんが非常に分かりやすい解説記事を書かれており、本エントリーはこの記事を参考にさせていただきました。
SmartNewsにおける類似度判定の必要性
そもそも、なぜSmartNewsで記事の類似度判定をする必要があるのでしょうか。インターネットでは、以下に挙げるような事情により、内容の類似または重複した記事が頻繁に発生しています。
同一の事象を複数のメディアが報じる場合
特に発表報道においては、表現に違いはあっても主旨としては同じ記事を、各メディアが別々に配信することになります。同一記事が複数のメディアで配信される場合
元の記事がポータルサイトなどにも配信されることがあります。記事のURLがバリエーションを持つ場合
アクセス解析目的等で、?ref=twitterのようなパラメータ付きで記事が配信されることがあります。この場合、パラメータの無いcanonicalなURLとパラメータ付きのURLが別々に検出されますが、内容は同一です。このようにして、ユニークなURLを持っていても内容の変わらない記事が複数収集されたときに、それをそのままSmartNewsに表示すると、ユーザの満足度が下がってしまいます。そこで、SmartNewsでは記事の類似度判定を行い、似通った記事間では最も正統と見なされるものだけを表示するよう工夫しています（「正統性」の評価については、今回のトピックとは全く別の議論になりますので、またの機会に書ければと思います）。
Jaccard係数
2つの文書があるとき、単語の共起を見ることで、文書の類似度を測ることができます。有名な共起尺度にJaccard係数があり、次のように定義されます。$$ J(A,B) = \frac{|A \cap B|}{|A \cup B|} $$
例えば、
A:「巨人・中井、左膝靭帯損傷し登録抹消」 B:「中井、左膝痛め登録抹消へ『歩行に問題はない』も…」
という2つの文書から、それぞれ
A: {巨人, 中井, 左膝, 靭帯, 損傷, 登録, 抹消} B: {中井, 左膝, 登録, 抹消, 歩行, 問題}
と単語を取り出したとします。このとき、AとBのJaccard係数は
AかつBに存在する単語数: |{中井, 左膝, 登録, 抹消}| = 4 AまたはBに存在する単語数: |{巨人, 中井, 左膝, 靭帯, 損傷, 登録, 抹消, 歩行, 問題}| = 9
であることから、4/9 = 0.4444… と求められます。
MinHash
文書数が増えてくると、Jaccard係数を毎回計算するのはあまりにも時間がかかり、現実的ではありません。そこで考案された手法の1つがMinHashです。MinHashでは、まず値域が十分に広いハッシュ関数を用意します（SmartNewsではMurmurHash3を使っています）。
続いて、文書中の各単語にハッシュ関数を適用し、最小のハッシュ値を求めます。先ほどの例のAでいえば、hash(巨人), hash(中井), …, hash(抹消)のうち最小値を見つけます。このとき、Aにおける最小ハッシュ値とBにおける最小ハッシュ値が一致する確率は、AとBのJaccard係数に等しくなります（本エントリーでは理由の説明を省きます。なぜ？と思った方は、岡野原さんの解説を参照してください）。
そこで、ランダムなハッシュ関数をk個用意し、各文書につきk個ずつ最小ハッシュ値を保存しておけば、k回の比較を行って一致した回数をもとにJaccard係数を推定できるというのがMinHashの原理です。当然、kを大きくとれば、計算コストも増えますが、より誤差の少ない推定ができるようになります。
b-Bit MinHash (b-Bit Minwise Hashing)
MinHashで最小ハッシュ値を保存するとき、そのビット数を節約することを考えます。例えば、64ビットのハッシュ関数を採用した場合に、最下位1ビットだけを保存することを考えます。これなら、kを64倍にしてもメモリ消費量は変わりません。ただし、1ビット値は最初から50％の確率で衝突するので、単に一致した回数をkで割っただけでは、真のJaccard係数が0の場合でも0.5くらいの推定値が出てきてしまいます。そこで、衝突確率の分を考慮した補正をかけることで、真のJaccard係数の推定を行います。これがb-Bit MinHashです。リンク先の論文によれば、b=1を採用すると、b=64のときに比べて、同じ推定精度を達成するために必要な記憶領域が、最低でも21.3倍改善するとのことです。
ハッシュ値一致数の高速計算
SmartNewsでは、b=1, k=128としてb-Bit MinHashを採用しています。ハッシュ関数としては、先に述べたMurmurHash3の最下位1ビットを使っています。ここからJaccard係数を推定するとき、普通に考えると128回の比較が必要になるのですが、ビット演算を使えばこれを劇的に高速化できます。
まず、記事Aのビット列と記事Bのビット列のXORをとります。これで、一致するビットはリセットされ、不一致のビットだけが立った状態になります。
続いて、このビット列のハミング重み（1の個数、popcountとも呼ばれる）を数えます。といっても、1ビットずつ数えるのではなく、効率的に計算する実装が確立されているので、それを利用します。例えば、Javaの場合は標準APIのLong.bitCount()やInteger.bitCount()を使うだけです。参考に、JDKからソースを引用します。
public static int bitCount(long i) {
i = i - ((i >>> 1) & 0x5555555555555555L);
i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
i = i + (i >>> 8);
i = i + (i >>> 16);
i = i + (i >>> 32);
return (int)i & 0x7f;
}
public static int bitCount(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
こうして得られたハミング重みはハッシュ値の不一致数に等しいので、これをビット長（SmartNewsの場合は128）から引くことで、一致数を高速に求められます。