忍者ブログ
研究室生活のメモ・・・だった過去の遺産。移転先→http://negimochix2.blogspot.com/
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

ここ10日間研究室にとまったおかげで,
LSHとその周辺についていろいろとわかった.
ネットサーフィンならぬ文献サーフィンをしていたので,
一度ここで整理しておく.

Locality-Sensitive Hashing
LSHは近似最近傍探索(Approximate Nearest Neighbor)アルゴリズムの一つ.

近似最近傍探索とは,簡単に言うとクエリqから半径(1+ε)内にある点vを探索すること.
つまり,半径(1+ε)の点のうち,どれか1つでも探索できればおk.
言葉の意味そのままに最近傍探索(Nearest Neighbor)の条件を少し緩くした探索といえる.
(実は,特徴ベクトルの次元がd=2の場合なら,ボロノイ図を使えば近似最近傍探索ができる)

LSHはハッシュ関数を用いた確率的探索で近似最近傍探索を解く.
そう,実はハッシュ関数を用いるということ以上に確率的探索ということに大きな意味がある.(これが自分にとってはかなりやっかいな問題)
LSHでは,クエリqと近傍(半径(1+ε)以内)にある点ではハッシュ値が一致する確率が高く,
クエリqと遠い位置にある点ではハッシュ値が一致する確率が低くなる
ようなハッシュ関数を定める.
各点の特徴ベクトルを入力として,ハッシュ関数から得られたハッシュ値に対し,
ハッシュ値が等しいものを同じバケットに格納する.
これにより,近傍にある(可能性の高い)データ同士の集合が生成される.
クエリqが含まれるバケットを探索することで,近似最近傍探索が実現される.

以上よりLSHメリット・デメリットは以下のようになる.
メリット:
・2点間の距離を算出をしない → 高速な探索が可能
・クエリの数,つーかクエリの有無に関係なく近傍探索のコストは同じ.

デメリット:
・確率的探索 → 精度に問題
・精度に限界がある

2つ目のメリットはでかい.
バケット=クラスタと考えれば,ある意味LSH自体がクラスタリングをしているといっても過言ではない.
でも,実際にはバケット=クラスタとすることができない.
それは,バケットがあくまでも確率的に可能性が高いとしか言えないから.
うーん,なんとも歯がゆい感じ.

そもそも,なぜ確率に頼るのか.
それは,ハッシュを使っているから.
この考え方だと,ハッシュ値が一致したものしか同じバケットに格納されない.
だから,確率的に変動させておかないと,まったく同じ特徴ベクトルのものしか格納されないことになる.

最初に提案されたのは,
"Approximate Nearest Neighbors : Towards Removing the Curse of Dimensionality"(P.Indyk et al, 1998)
でも,LSHは全体の手法の一部としか紹介されおらず,
具体的なハッシュ関数の定義が書いていない.
というか,実験すらしてないΣ(゚д゚)
なので,理論だけ.
ときどき,(A.Gionis et al, 1999)をrefしてる文献があったけど,
それは正確ではない.
そっちは,具体的にハッシュ関数を定めたやつ.(最初,どっちがどっちだかわからずこまった)

LSHのハッシュ関数
LSHでは特徴ベクトルをどんな距離空間で比較するかによってハッシュ関数を定める.
自分が確認したの以下のようなもの.
L1距離(Hamming Space)
定義・証明:
"Similarity Search in High Dimensions via Hashing"(A.Gionis et al, 1999)

Lp距離
安定分布を用いることでLp空間に対応.
定義・証明:
"Locality-Sensitive Hashing Scheme Based on p-Stable Distributions"(M.Datar et al, 2005)

Jaccard係数
Min-wise Independent Family(最小値独立変換族)に属する順列(Permutation)を用いることでJaccard係数に対応.
のちにMinHashと呼ばれたりする.
理論の元:
"Syntactic clustering of the Web"(A.Z.Border et al, 1997)
Min-wise Independent Familyの定義等:
"Min-wise Independent Permutations"(A.Z.Border et al, 1998)
Min-wise Independent Familyからハッシュ関数への証明:
"A small approximately min-wise independent family of hash functions"(P.Indyk, 1999)

Cosine尺度(Earth Mover Distance:EMD)
定義・証明:
"Similarity Estimation Techniques from Rounding Algorithms"(M.S.Charikar, 2002)



PR
この記事にコメントする
お名前
タイトル
メールアドレス
URL
コメント
パスワード   Vodafone絵文字 i-mode絵文字 Ezweb絵文字
この記事へのトラックバック
この記事にトラックバックする:
Infomation
くさもち 【中の人】
・くさもち
・ボカロ廃大学院生
・βからのニコ厨
・もちろん非リア充
・ミクZ4 第二期個人スポンサー

【メール】
・negimochi.tabetai(゚Д゚)gmail.com
(゚Д゚)→@

【その他やってるもの】
Twitter

・これは痛いピアプロ
・過去の遺産smart.fm

【作ったもの】
・製作に参加したDTX GDPメインサイト
で,実際に作ったIRページ
カレンダー
01 2020/02 03
S M T W T F S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
Heartsnative
『Heartsnative/MOSAIC.WAV×鶴田加茂 feat.初音ミク』応援中!
VOCALOID Ranking Watcher
新曲は常にチェックすべし。
真・フルみっくすプレイヤー
おすすめ記事
jubeat ripples
今更やってみる