LSH(SimHash) で recall(適合率) を見積もりたい - 木曜不足
英単語タイピングゲーム iVoca で「おすすめブック」機能をリリースしました。 ブック(単語帳)の画面に、そのブックと似ていて、同じユーザが学習しているブックを自動的に表示します。 英検の単語を集めたブックには英検の、しかもだいたい同じレベルのものを、TOEIC には TOEIC、イタリア語にはイタリア語、ドイツ語にはドイツ語、と ちゃんとおすすめできています。 外国語以外にも 古文の単語を集めたブックには古文、アメリカ合衆国の５０州を覚えるブックには世界の首都や都道府県を覚えるブックをおすすめしてくれます。 学びたいブックを見つけやすくなった iVoca をこれからもよろしくお願いします。 以上、よそいきモード終わり。 今回の類似ブック探索には、ソーシャルブックマーク界隈で噂の LSH(Locality Sensitive Hashing)、特に余弦類似度を用いた SimHash を採
コサイン距離ベースのLSHをRubyで - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
参考文献:Web+DB press vol.49 レコメンド特集のPart3など。 アルゴリズムの概要 詳細(特に数学的な)はぐぐれ。 モチベーションとしては、高次元における近傍点探索を高速で行いたい。まじめにやるとどう工夫しても計算量がすごいことになるので、近似で。 どうするかというと、「距離が近いと同じような値になるハッシュ関数」を使う。あるベクトルの近傍を求めたい場合、そのベクトルのハッシュと同じ(もしくは近い)値のハッシュを持つベクトルをテーブルから引いてきて返す。計算量がどうなるかはややこしいけど、とりあえず全部探すよりは速い。 で、どういう関数をハッシュとするのか。これは距離の定義によって異なる。ハミング距離、コサイン距離、ユークリッド距離などにはそういった関数の存在が知られている。 コサイン距離の場合、ランダムなベクトルをいくつか用意して、入力されたベクトルがそれらと似ている
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
