Learning to Hash! 最新 Locality sensitive hashing 事情 - 武蔵野日記
高速に類似度計算をしたい場合、典型的に使われるのは Locality sensitive hashing (LSH)という技術であり、元々距離が近いインスタンス同士はハッシュ値が近くなるようにハッシュ関数を作ることで高速に類似度を計算したりできるというお話なのだが、最近 Semantic hashing や Spectral hashing、また Kernelized LSH という手法が登場して盛り上がりつつあるところ、同じグループの人がもっといいのを出しました、ということらしい。ちなみに情報推薦とか画像検索とか大規模クラスタリングとか、いろいろな分野で高速な類似度計算の応用例がある。 そういうわけで、今日は manab-ki くんが Brian Kulis and Trevor Darrell. "Learning to Hash with Binary Reconstructive
Locality Sensitive Hashing
【論文】M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni, Locality-Sensitive Hashing Scheme Based on p-Stable Distributions, Proceedings of the twentieth annual symposium on Computational geometry, 2004. Overview Locality Sensitive Hashing(以下LSH，局所性鋭敏型ハッシュ)は高次元データを次元圧縮するための手法で，圧縮したデータによるハッシュテーブルを作成して，効率的に近似的最近傍探索を行うための手法です．基本的なアイディアとしては高次元空間内での距離が近い2つのベクトルが，ハッシュテーブルにおいて高確率で同じバケットに入るように確率的な処理を行うと
レコメンド, LSH, Spectral Hashing - DO++
WEB+DB press vol.49にレコメンド特集の記事をtkngさんと書きました。 内容は最初は、協調フィルタリングやコンテンツマッチの簡単な話から、特徴量をどのように表すか、大規模データをどのように処理するかにいき、特異値分解などの低ランク行列分解によるレコメンドやRestricted Boltzmann Machineといった最近のnetflix prizeの上位の手法など、かなり突っ込んだ議論もしてます。 個人的には三章でLocality Sensitive Hash(LSH)について扱っているあたりがお勧めです。 レコメンドの内部の問題を極言すると、データというのは疎な高次元の数値ベクトル（数百万次元とか）で表され、クエリでベクトルが与えられた時、これと似たようなベクトルを探してこいという問題になります。”似たような”を数学的にいえば、クエリのベクトルとの内積（各ベクトルは長
最近のバイナリハッシングをいくつかJavaで実装してみた - rubyu's blog
去年の終わりから、バイナリハッシングを使った近似近傍検索をいろいろ調べていたのですが、ぼちぼち一段落したので、ひと通りまとめておきます。 バイナリハッシングとは。 個の 次元の点からなるデータセット で、元空間での近傍点を、類似したバイナリコードに関連づける技術。 要するに、実数ベクトルの検索をマトモにやるには、最近のデータは膨大すぎるのでお手上げ。なので、元空間での距離をなるべく保ったまま、バイナリコードに落としましょう。 そうすると、バイナリ一致か、1ビット違うか、2ビット違うか...と、捜索していくにしても、元空間のデータでやるより高速で、しかもストレージ容量を削減できるというわけです。 その ビットのバイナリコード を作るために、 個のハッシュ関数が使われる。 ハッシュ関数は と定義される。ここで、 はデータセット。 は射影ベクトル。 は閾値。 線形写像ベースのハッシングはシンプル
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
b-Bit Minwise Hashing
PFI Seminar 2012/03/15 カーネルとハッシュの機械学習
