Locality Sensitive Hashing(LSH)とは、ベクトルとして表現されたデーターの集合を入力として、それらの２点間の距離を保存したまま、ハミング距離に基づく文字列の集合に射影する技術です。コサイン距離[1]、ユーグリッド距離[2]に基づくものや、機械学習法を応用した、semantic hashing[3], spectral hashing[4], kernelized LSH[5], その他[6][7][8]、現在までに多くの手法が提案されています。この背景には、Googleが、昔に提案されたLSHが、ニュース記事の推薦システムで使えることを示した[9]のきっかけに、現在、推薦システム、画像検索、文章のクラスタリング[10]など、色々なシステムや研究の場面で利用されています。 理論的な収束の保証があるという意味で、オリジナルのコサイン距離ベース[1]の手法が良いのです

bayonを使って画像からbag-of-keypointsを求める - のんびり読書日記の記事を読んで、クラスタリングを行う際の入力データを作るために文献[1]にある方法が利用できると思って実験してみた。 局所特徴量を持ったデータの取扱い 画像データの分類などを行う際にSIFTのような画像中の特徴点(keypoint)を抽出するということがよく行われる。 例えばSIFTを用いる場合は各keypointは128次元のベクトルとなり、画像ごとにいくつかのkeypointが抽出される。ここで抽出されるkeypointの数は画像ごとに異なる。このため、画像間の類似性を比較するのは困難である。 これに対するアプローチとしては一つは画像中の特徴点同士の全対比較を行う、もしくはマッチングをとるという方法が挙げられるがこれは計算量が非常に大きい。 別の方法としてヒストグラムを利用するという方法がある。これ

WEB+DB press vol.49にレコメンド特集の記事をtkngさんと書きました。 内容は最初は、協調フィルタリングやコンテンツマッチの簡単な話から、特徴量をどのように表すか、大規模データをどのように処理するかにいき、特異値分解などの低ランク行列分解によるレコメンドやRestricted Boltzmann Machineといった最近のnetflix prizeの上位の手法など、かなり突っ込んだ議論もしてます。 個人的には三章でLocality Sensitive Hash(LSH)について扱っているあたりがお勧めです。 レコメンドの内部の問題を極言すると、データというのは疎な高次元の数値ベクトル（数百万次元とか）で表され、クエリでベクトルが与えられた時、これと似たようなベクトルを探してこいという問題になります。”似たような”を数学的にいえば、クエリのベクトルとの内積（各ベクトルは長

最近simhashの実装を行っていて、データの次元が高いとsimhashを計算するのに必要なランダムなベクトルをメモリ上に乗らないという事態が生じたのでad hocな方法で回避していたけど、論文[1]をよく見直すとほぼ同じ方法でより計算コストが少ない方法が紹介してあったので少し解説を行ってみる。ちなみに以下の解説では低次元のビットベクトルに縮約した後にハミング距離が近いものをどうやって探索するかについては述べないです、それに関しては[1],[2]を参照してください。 ちなみに自分が実装したのは各ビットごとに次元に対するハッシュ関数を定義して計算する方法でした。この方法だと以下で開設する手法よりもf倍の回数ハッシュ関数を計算する必要があるので実行時間が割とかかる。 解説 simhash[3](文献によってはLSHと呼ぶこともある[2])は次元削減の手法の一つで、高次元のデータを低次元のビット

参考文献:Web+DB press vol.49 レコメンド特集のPart3など。 アルゴリズムの概要 詳細(特に数学的な)はぐぐれ。 モチベーションとしては、高次元における近傍点探索を高速で行いたい。まじめにやるとどう工夫しても計算量がすごいことになるので、近似で。 どうするかというと、「距離が近いと同じような値になるハッシュ関数」を使う。あるベクトルの近傍を求めたい場合、そのベクトルのハッシュと同じ(もしくは近い)値のハッシュを持つベクトルをテーブルから引いてきて返す。計算量がどうなるかはややこしいけど、とりあえず全部探すよりは速い。 で、どういう関数をハッシュとするのか。これは距離の定義によって異なる。ハミング距離、コサイン距離、ユークリッド距離などにはそういった関数の存在が知られている。 コサイン距離の場合、ランダムなベクトルをいくつか用意して、入力されたベクトルがそれらと似ている

はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28

楽天テクノロジーカンファレンスには行かれなかったのだが、大規模分散処理フレームワークの設計、実装が進行中 -- 楽天版MapReduce・HadoopはRubyを活用などを読むと、けっこうおもしろそうだったのだな、と分かる。 楽天技術研究所がどういう位置づけなのかは分からないが、こういう基盤技術の開発を支援しているというのは評価していいと思う。(車輪の再発明という気がしないでもないが) 個人的な興味としては楽天が大規模データに対してどういうことをしているかということなのだが、記事を見るといろいろ書いてある。 計算モデルがシンプルでも規模が巨大になるとまったく別の問題が生まれてくる。処理すべき情報量が爆発的に増加しているからだ。 例えば協調フィルタリングではユーザーを縦軸に、商品アイテムを横軸にした購買履歴マトリックスについて計算処理を行う必要があるが、あまりに量が多く、素直に実装すると「2

2. ( 最 ) 近傍点探索 ( Nearest Neighbor Search) とは いわゆる、特徴空間内での類似データ探索 二種類の問題が考えられる 定義 ℜ d 空間上の点集合 P が与えられた場合 最近傍点探索 クエリ点 q に対し、 p∈P で、 ||p-q|| を最小とする点 p を求める問題 r- 近傍点探索 クエリ点 q に対し、 p∈P で、 ||p-q||<r となる点 p を ( 存在するのならば ) 列挙する問題 3. 近傍点探索問題 近傍点探索アルゴリズムは、以下のようなタスクにおいて利用される インスタンスベース学習(k-近傍法) クラスタリング データセグメンテーション データベース検索 最短経路木探索(Minimum Spanning Tree) データ圧縮 類似データ検索 4. 近傍点探索アルゴリズム 最も単純なものは、クエリ点 q と、 p∈P の点全

WEB+DB PRESS Vol.49 作者: arton,桑田誠,角田直行,和田卓人,伊藤直也,西田圭介,岡野原大輔,縣俊貴,大塚知洋,nanto_vi,徳永拓之,山本陽平,田中洋一郎,下岡秀幸,ミック,武者晶紀,高林哲,小飼弾,はまちや2,WEB+DB PRESS編集部出版社/メーカー: 技術評論社発売日: 2009/02/23メディア: 大型本購入: 10人 クリック: 373回この商品を含むブログ (45件) を見る Web+DB Pressのレコメンド特集に載っていたLocality Sensitive Hashを試してみました。あまりよく理解できてないので間違っているかもしれませんが、せっかくなのでブログに書いておきます。 作成したコードは以下に置いてあります。 http://github.com/mjmania/mining/blob/991a855fc378d831a057

久々のエントリです。 Locality Sensitive Hashing を perl で使うためのモジュールを書いてみました。Algorithm::LSHと名付けました。 先ほどDeveloper ReleaseとしてCPANにあげましたが、反映されるまで時間かかるので、興味ある方はcodereposからみてください。 Algorithm::LSH CPAN: http://search.cpan.org/~miki/Algorithm-LSH/ coderepos: http://coderepos.org/share/browser/lang/perl/Algorithm-LSH 超アルファバージョンな状態ですが、そのうちgithubにもupする予定。 そうそう、そう言えば WEB+DB PRESS Vol.49 にレコメンドエンジンの特集があって、その中に偶然にもLocality

飛行船通信 飛行船通信MLの主催者(few01)が気になった事を記録するWIKI トップページページ一覧メンバー編集 060108 Locality-Sensitive Hashingの実装が一段落 最終更新： few01 2006年01月11日(水) 00:43:46履歴 Tweet 昨年末からプログラミングを始めたLSH: Locality-Sensitive Hashingの開発がやっと一段落した。今日の昼に何とか動くようになった。まだ細かなバグ修正や、処理速度の向上は必要だろうが、大きな山はこえた。 LSHというのはハッシュテーブルの一種である。 ハッシュテーブルというのは、ハッシュ関数を使った索引のことだ。 2006/1/10 ミスを修正 ハッシュ関数とは ハッシュ関数h()というのは、入力の値 x に対して、h(x) の値が、 近い x の場合にぶつかりにくく 一定の範囲に収ま