- この記事は、CyberAgent エンジニア Advent Calendar 2014の21日目の記事です。
- 20日目は@kakerukaeruさんのエンジニアの僕が三軒茶屋で写真を存分に使ってmcrouterでした。
- 22日目は@ogaclejapanさんです。
21日目は、秋葉原ラボの@k66dangoが担当します。 入社の頃から、上司にキラキラデータサイエンティストと呼ばれていますが、 キラキラする気配もセクシーになる気配もありません。
今回は、Mitzenmacheら[1]が提案したOdd Sketchesについて紹介をします。 Odd Sketchesは、集合の類似度を表すJaccard係数の推定手法の一つで、「集合の類似度合い」を推定する方法です。 これに対して、HyperLogLogという「集合の異なり度合い」を推定する方法があります。これに関しては、 18日目の記事で@sitotkfmさんが「Spark StreamingでHyperLogLogを実装してみた」という記事を書いています。
弊社では、さまざまな場面で類似度判定を行なっています。 たとえば、似ているユーザを推薦するケースやブログのコピーコンテンツを抽出するケースなどです。 こうしたケースでは、以下の２つのことが重要です。
- 高速に類似度判定を行なうこと
- 類似度の高いアイテムを推定する精度を重視すること
1点目について、データが大規模になると計算時間をいかに削減するかが重要になります。たとえば、アメーバブログでは一日当たり約数十万件のブログ記事が投稿されているので、ある記事の似ている記事を見つけるのに、単純にJaccard係数を計算しているとかなり時間がかかってしまいます。 2点目について、現場の要求として多いのは、似ているものを抽出するタスクです。よく似ているもの同士のJaccard係数の推定精度が高いと、似ているユーザの上位10件をリストアップすることや、コピーコンテンツを特定することに役立ちます。
そこで、今回は上記2点の要件を満たすOdd Sketchesを利用したJaccard係数の推定方法について紹介したいと思います。 これは2014年のWWWでベストペーパーに選ばれた論文です。
異なるハッシュ関数をk個用意して、それぞれの最小値が何個一致したかを求めます。 そして、一致した個数をkで割った値がJaccard係数の推定量となります。 しかし、この方法ではハッシュ値をそのまま保存するので、空間効率がいいとは言えません。 たとえば32bitのハッシュ値を採用する場合、データサイズは32 * k bitとなります。 推定値の精度を向上させるにはkの数を増やす必要がありますが、データ量が多くなると 記憶容量の限界にあっという間に到達してしまうかもしれません。
上記の問題を克服する手段として、2010年にLinら[2]が提案したb-bit minwise hashingが有名です。 この手法は、ハッシュ値の最小値の最下位b bitだけ保存するので、空間効率がかなり改善されます。 たとえば、最下位1 bitのみ保存するなら、データサイズは1 * k bitで済みます。 Linら[2]は、「似ているニュース記事を特定する」という実験を行って、min hashと比較して どれだけ空間効率が改善するかを実証しています。 たとえば、1-bit minwise hashingを利用すると、 32bitと同程度の精度を達成するのに、空間効率が10.7倍改善するとのことです。
上記の手法を用いることでデータ容量を減らすことができますが、真のJaccard係数が１に近いとき、推定の精度が悪化することが知られています。 これは、Jaccard係数が高いと、２つの集合のsketchがほとんど同じになり、sketchの違いを表現できなくなってしまうためです。 上記の問題を克服するために、Mitzenmacheら[1]は sketchの共通部分の論理的排他和を求め、異なっている部分を抜き出す手法を提案しました。
Odd Sketchesを用いると下記のようにJaccard係数を推定できます。ここで、nはsketchの大きさを表し、kはハッシュ関数の個数を表しています。また、odd(S)は集合Sのodd sketchを意味しています。
上記の式で、|odd(S_1)△odd(S_2)|の部分で、２つの集合がどれだけ異なっているかを表現しています。
それでは、Odd Skethはb-bit minwise hashingと比較して、どのくらい精度が向上するのでしょうか？ 下記の図（[1]のfigure 4）は、平均平方誤差の対数値のマイナス値を表しています。つまり、値が大きいほど真の値との誤差が小さいということです。Odd Sketchとb-bit minwise hashing(b=1,2,4)を比較をしたとき、真のJaccard係数が0.80を超えると、Odd Sketchの方が誤差が小さくなることがわかります。
次に、Odd Sketchを求めるアルゴリズムを紹介します。
- k-MinHashにより、元の集合Ωから要素をk個選択し、sketch Sを作成する
- 0で初期化した、大きさnのベクトルsを準備する
- MinHashで利用したハッシュ関数とは異なるハッシュ関数hを用いて、ベクトルsのh(x)番目のビットを反転（x\inS）する。
- 3の処理をSの全要素に対して行なう。
サンプルコードは著者のサイトに掲載されています。
真のJaccard係数Jが0.75以上のとき、Odd Sketchによる推定値の平均平方誤差がどれくらいか計算してみます。 簡単化のために、以下のような3つの単語集合を用意します。
1. ["さかい", "水炊き", "焼肉", "ゆうじ", "ハツ", "鶏ガラ", "登録", "雑炊"]
2. ["さかい", "水炊き", "焼肉", "ゆうじ", "ハツ", "鶏ガラ", "登録", "テール"]
3. ["さかい", "水炊き", "焼肉", "ゆうじ", "ハツ", "鶏ガラ", "登録", "テール", "雑炊"]
それぞれ真の値と、推定値は以下のようになります。
| Pair | True | Estimation |
|---|---|---|
| 1-2 | 0.777 | 0.760 |
| 1-3 | 0.88 | 0.904 |
| 2-3 | 0.88 | 0.853 |
平均平方誤差（対数値のマイナスをとったもの）を求めると、7.409になりました。 上記の図を見ると、真のJaccard係数が0.75のとき、だいたい7くらいなので同じくらいな数値になりました。 （本来なら、論文と同じようにb-Bit Minwise Hashingを使って比較をしたかったのですが...）
Odd Sketchesを利用したJaccard係数の推定方法を紹介しました。 この手法を利用すれば、既存の手法と比較して類似度の高いアイテムを抽出する精度を向上できそうです。
弊社では、類似しているデータを特定する際に、ハミング距離やMPJoinなど他の手法も利用していますので、 Odd Sketchesとこうした手法の比較・検証を行ないたいと考えています。
- [1]Mitzenmacher, Michael, Rasmus Pagh, and Ninh Pham. "Efficient estimation for high similarities using odd sketches." Proceedings of the 23rd international conference on World wide web. International World Wide Web Conferences Steering Committee, 2014.
- [2]Li, Ping, and Christian König. "b-Bit minwise hashing." Proceedings of the 19th international conference on World wide web. ACM, 2010.