英単語タイピングゲーム iVoca で「おすすめブック」機能をリリースしました。
ブック(単語帳)の画面に、そのブックと似ていて、同じユーザが学習しているブックを自動的に表示します。
英検の単語を集めたブックには英検の、しかもだいたい同じレベルのものを、TOEIC には TOEIC、イタリア語にはイタリア語、ドイツ語にはドイツ語、と ちゃんとおすすめできています。
外国語以外にも 古文の単語を集めたブックには古文、アメリカ合衆国の５０州を覚えるブックには世界の首都や都道府県を覚えるブックをおすすめしてくれます。
学びたいブックを見つけやすくなった iVoca をこれからもよろしくお願いします。
以上、よそいきモード終わり。
今回の類似ブック探索には、ソーシャルブックマーク界隈で噂の LSH(Locality Sensitive Hashing)、特に余弦類似度を用いた SimHash を採用。
LSH を実サービスに投入して使い物になるかどうか、というあたりを確認してみたかった、というのが最大の動機。*1
LSH は、乱暴に一言で説明すると、ハッシュ関数(入力値の射影)を「似ている値は同じ値になりやすいように」定めることで、射影先(離散＆ずっと少ない次元)での探索に落とし込むというもの。
SimHash の場合はハミングコードに落ちるので、計算量がうんと小さくなる。はず。
ここで射影先のハミングコードの探索を高速に行う必要があるのだが、岡野原さんの「SBMの推薦アルゴリズム」でも紹介されている、「ランダムシャッフル＆ソート」を用いる方法 では満足する結果が得られなかった。
recall(再現率＝適した対象のうち、探索結果に含まれる割合) が非常に悪いのだ。
「ランダムシャッフル＆ソート」の細かい内容については上述の資料や原論文*2をご参照いただきたいが、この方式の問題点は「ハミング距離≦ｎ のコードを網羅させたい」といった制御が実質出来ないため、recall が見積もれないこと。
recall をあげるためには、射影先の次元(ビット数)を減らしたり、シャッフル回数を増やしたり、ソート後の採用範囲を広げたり、という調整も一応出来るが、そうすると precision(適合率＝探索結果の内、適した対象が含まれる割合) が非常に悪くなったり、同じところばかり探すという無駄な処理が増えたりする。
「１回のクエリーに、ビットのランダムシャッフル＆ソートを何十回〜何千回もするの！？」*3という部分も受け入れられない。
パターン認識でよくやる「探索結果を投票に用いて、最多の候補を画像などの認識結果とする」ために用いるのであれば、precision をある程度確保しつつ十分な件数を探索できればいいだろうから「ランダムシャッフル＆ソート」でもよいかもしれない。
が、iVoca の「おすすめブック」のように、探索結果をそのまま見せる場合は recall 重要なので、このままでは厳しい。
仕方ないので SimHash をあきらめて、Lp ノルムを使った別の LSH である p-stable を試してみよう……。
p-stable の論文*4 を読み、試しに実装していて、「これ、SimHash でもそのまま使えるんじゃあないの？」と気付く。
これにより iVoca では SimHash を使って、90% を超える recall を実現できた。
以下はその方式を簡単に説明。
ハッシュ関数の作り方は、通常の SimHash と全く同様にランダムベクトルを用いる。
ただしハッシュ関数を複数個用意する。
ここでは K ビットのハッシュ関数の族 {h_1, ……, h_L} を考える( K と L の決め方は後述)。
あらかじめ、全アイテムのハッシュ値 { (h_1(x),……,h_L(x)) | x∈X } を計算しておく。
クエリー点 y に対し、１つ以上のハッシュ関数について h_j(x) = h_j(y) となる x 全体を探索結果とする(記号で書くと ∪_j { x∈X | h_j(x) = h_j(y) } )。
シャッフルもソートも要らないので、実装はとても簡単だ。
このとき recall をどうやって見積もる＆ K と L をどうやって決めるか？
SimHash で２つの点が同じビットに射影される確率は、「ランダムベクトルの定める超平面の同じ側にある」確率と一致することから、p = 1-θ/π であることがわかる(θは x と y のなす角)。
ここから「K ビットのハッシュ値が一致する確率」は p^K 、「 L 個のハッシュ値の１つ以上が一致する確率」は 1 - ( 1 - p^K )^L となる。
よって、例えば「正解」を「余弦類似度が 0.9 以上」とおくと、p = 1 - (arccos 0.9)/π = 0.8564 を用いて、各 K, L ごとの「余弦類似度が 0.9 の点が探索結果に含まれる確率」、つまり recall を以下のように見積もることが出来る(縦が L 、横が K。赤は 0.7 以上)。
同じく、「不正解」を「余弦類似度が 0.6 以下」などおき、「余弦類似度が 0.6 の点が探索結果に含まれる確率」も計算しておく(赤は 0.2 以下)。
ここから、入力点の分布を仮定するなどすれば precision も見積もることができるだろうが、そこまでしなくても、この値が小さいほど precision がよくなることは自明だろう。
つまり、上の表の値が必要な recall を超えていて、下の表の値が十分小さい (K, L) のうち、手頃なもの(例えば K=9, L=5)を選べばよい(計算量は K*L に比例)。
また、「ハッシュ一致」ではなく「ハミング距離１以下(=ハッシュ探索を K+1 回行う)」にすれば、確率を同様に計算すればわかるとおり、空間計算量を抑えつつ recall を上げることが出来る。
問題点は、「正解」となる余弦類似度の閾値が小さめ(感覚的には 0.7 以下くらいから)の場合に、recall を上げようとすると precision があまり確保できない(探索結果にノイズが多くなる)こと。
といっても、これはそもそも SimHash がそういうケースを苦手としているため(ヒント： arccos のグラフ形状)。
逆に言えば、そういうモデルで SimHash を使うのは適していないかもしれないので、気をつけるべき、とか、SimHash を使いたいなら余弦類似度が最低でも 0.7 以上を「正解」と出来るようにモデルを定めるべき、と言えるかもしれない。
*1:そもそも iVoca の現在のブック数だと線形探索でも間に合う、というのは内緒。そのうち１００倍とか１０００倍になるからいいんだ……
*2:Ravichandran D., Pantel P., Hovy E., "Randomized algorithms and NLP: using locality sensitive hash function for high speed noun clustering", 2005
*3:ランダムではなく恣意的にシャッフルさせることで回数を減らしたり、ソートをせずに済む方法を考えたり、といった工夫はいくつか試せるものの
*4:Datar M., Immorlica N., Indyk P., Mirrokni V S., "Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry", 2004
