昨年末からプログラミングを始めたLSH: Locality-Sensitive Hashingの開発がやっと一段落した。今日の昼に何とか動くようになった。まだ細かなバグ修正や、処理速度の向上は必要だろうが、大きな山はこえた。
2006/1/10 ミスを修正
ハッシュ関数とは
ハッシュ関数h()というのは、入力の値 x に対して、h(x) の値が、
y=h(x)とする。xには0以上100,000,000以下の整数が入ってくるとしよう。
例えば、yの値域を0以上100以下の整数とする(一定の範囲に収める)。
h(x)=[x/1000000]（100000で割って少数切り捨て）とすると、確かに0から100の間に収まる。しかし、0から1000000までの値は全部0になってしまう。こういうのは、ぶつかりやすいという。
もう少しましなのが、y=x%97（素数97で割った余り）である。これだとx=0,1,2,3,4...が、それぞれy=0,1,2,3...になる。ばらばらな値になる。
とりあえずの条件はこんなものだが、何に使うか（目的）によって、別の条件が加わってくる。
Wikipediaのハッシュ関数の解説
暗号通信に使うハッシュ関数
例えば、現代におけるハッシュ関数の最大の利用目的は暗号通信だ。MD5とか聞いた事無いかな。その場合は、
パスワードが"aho"だったとしよう。入力したパスワードが正しいかどうかを調べるためには、コンピュータの方に"aho"というのを用意しておいて、直接比べるのが一番単純だ。
しかし、そうするとコンピュータの中に"aho"というのが、そのまま残ってしまう。もしこのコンピュータのデータが盗まれたりしたら、パスワードが漏れてしまう。
そこでahoをハッシュ関数で変換した結果を、コンピュータに残しておくことにする。例えば h("aho") = 34129というような感じだ。コンピュータの中には34129しか残っていない。
パスワードをチェックする時には、入力された文字列をハッシュ関数で変換した値と、コンピュータの中に保存されている34129を比べればパスワードチェックができる。
検索に使うハッシュ関数
ハッシュテーブルというのは、このハッシュ関数を使った索引だ、というのは上に書いた。索引というのは、検索をすばやく行うための工夫だ。
分厚い本などは巻末に索引がついてて、特定の言葉が本のどこにあるのかを捜しやすくなっている。辞書しかり。
探したい情報をxとすると、ハッシュテーブルのh(x)の場所に、xの在り処が書かれている。
例えばx="livedoor Wiki"として、h(x)=34129だとすると、ハッシュテーブルの34129番目に、"livedoor Wiki"の在り処が書かれている。
yの値を、一定の範囲に収めることができるので、例えば、さまざまな種類の色んな情報を、一定のメモリ内の領域や、一定のハードディスク内の領域におさめることができる。
索引の作り方には、もうそれこそ一杯方法がある。データベース関連の研究会なんかでは、それこそ論文誌が全部索引の作り方で占められているぐらいだ。それでも毎月新しい索引が提案される。
世の中データベースだらけで、データベース無しでは動かない世界になってしまっているので、有用な索引作成手法は金になる。
索引としての、ハッシュテーブルの良いところは、適切なハッシュ関数があれば、探したい情報に一発でアクセスできる、という点だ。例えば、ツリー型の索引だと、ツリーをたどって行く時間がかかるが、ハッシュは一発だ。
しかし世の中そう甘くない。
「衝突」がおきるからだ。xは、それこそ膨大なバリエーションなのに対して、y (=h(x))は小さな領域におさめる必要があるので、当然ながら、違うxなのに、h(x)が同じになってしまう場合がある。これが衝突（コリジョン）だ。
衝突がおきた時の回避方法は極めて原始的で、次のどちらかを使う。
1の方法は、「衝突しちゃったか、ま、いいや隣にいれちゃえ」で、2の方法は「衝突しちゃったか、ま、いいや一緒に入れとけ」だ。
隣に入れちゃうと、どんどん隣が埋まってゆくので、本来入れるべきものが後ろ後ろに押しやられてしまう。これが始終起きると、もうハッシュテーブルの中はしっちゃかめっちゃかになる。一緒に入れておくと、一緒に入れた中から探す手間が増えてしまう。全部のデータが、一つの付属テーブルに入ってしまったら、もう索引の用はなしていない。
上の方で、適切なハッシュ関数、といったのは、この衝突がおきにくい関数という意味だ。
不適切なハッシュ関数の代表は、同じようなハッシュ値ばかり出す関数だ。理想的にはハッシュテーブルを満遍なく使って欲しい。
ところが、どういう入力値(x)が来るかは事前に予測できないから、最適なハッシュ関数というのはわからない。ま、そこそこ良いハッシュ関数というのがあるから、皆それを使う。
LSH: Locality-Sensitive Hashingとは
LSHでのハッシュ関数やハッシュテーブルは、上述したような通常のハッシュテーブルとは、ずいぶん違う。
LSHの目的は、似たようなものを高速に探し出す、ということにある。（普通のハッシュテーブルは同じものを高速に探し出す。）
こういうのを類似検索とか、近傍探索とかいう。類似検索や近傍探索のニーズは、これまたすごく多い。似たような文、似たような写真、似たような音楽、似たようなビデオ、を探す。
類似検索に良く使われるのはツリー型の索引だ。いろんなツリーが提案されている。LSHの良さは、そういったツリー型の索引に比べて速いということだ。その意味で、上述したハッシュ関数の良さをそのまま引き継いでいる。
しかし悪い点も同じく引き継いでいて、衝突がおきやすいとちっとも速くない。その衝突回避のメカニズムが良くできている。
LSHはIndykさんというスタンフォードの研究者が提案した方法だ。たぶん以下は彼の博士論文だろうと思う。すごく優秀な研究者だなぁ。
VLDBというデータベースで最も有名な国際会議の一つで、その良さげな実装方法が提案されたのをうけて、色々な人が使っている。
この名前の並びからすると、Motwaniさんというのが教授かな。Gionisさんというのは、同じ研究室の人だろうな。この実装は、すごく良くできているのだが、LSHの原理からすると少し後退している。それはマンハッタン距離での近傍探索になっている点だ。
点(x1, y1)と点(x2, y2)の距離は、点の間を線で結んて、その線分の長さ、つまりユークリッド距離
マンハッタン距離というのは、縦横にしか動けないとした場合の道のりを表す。つまり
データ同士の近さを計るのには、もちろん色んな尺度がある。マンハッタン距離も重要な一つで、利用範囲は広い。でもユークリッド距離の方が、より普通に使われる。
安定分布を使ったLSHの最新バージョン
Indykさんは、その後MITに移って助教授になっている。そこで書いた論文が以下だ。
Datarさんというのは学生さんかな？ずいぶん優秀な学生さんだ。先生も優秀なら生徒も優秀、さすがMITだな。
こちらではユークリッド距離も使えるようにバージョンアップした実装が書かれている。そのために使っているのが、安定分布(p-stable distribution)だ。
Wikipediaの安定分布の解説
ユークリッド距離を使うためには、特性指数が2の安定分布である「正規分布」を使う。正規分布はおなじみだな。
さて、その手順は、次のようなものだ。
ちょっとわかりにくいかな。以下に大雑把に説明することにしよう。
LSH v2の大雑把な説明
近い値を探すのがLSHの目的なのだが、相手にするデータには、色んなものが来るので、近さ、というのを計算するのはけっこう大変だ。
一番簡単な方法は、登録されているデータすべてとの距離を計算して、近いものを見つけるという方法だが、これはデータ数が多くなると、それに応じてどんどん時間がかかるようになる。
１００個ぐらいならいいけれど、扱うデータが１００万個とかなると、もう大変。計算機はたしかに速くなったけど、扱うデータの数もどんどん多くなっている。
そこで考えられる素朴な方法が
LSHの基本的な考え方もこれである。
例えば、碁盤の上に碁石をちらばらせたような状況を考えてみよう。
新しい碁石を左手前の星のあたりに置いたとして、近いものを探すのに右端を見たりはしない。左手前の付近で探す。
だから、左奥、右奥、左手前、右手前の四つのグループに分けておいて、探したい場所の付近のグループだけを捜せば、探す手間が四分の一になる。
１０Ｘ１０分割しておけば1/100になる。
まぁ碁盤のように２次元なら、これでもいい。ところが１０００次元となると、こうはいかない。分割した領域の数が膨大になってしまうのだ。各次元を１０分割したとして１０の１０００乗！。
１０００次元なんて必要なのか、という人もいるかもしれないが、白黒写真：横１００画素、縦１００画素だと10000次元になる。画素をそのまま使うというのは類似検索ではあまり使わないが、例としてあげた。
領域に番号をつけて、それをハッシュテーブルに格納するという方法も考えられる。新しいxが入ってきたら、それの属する領域の番号に対応するハッシュ値のところを探す、という方法だ。
ところが、３次元ぐらいならこれでもいいのだが、高次元になると実はあまり簡単でなくなる。それは隣の領域の数が増えてしまうからだ。
この隣の数の計算は簡単で次元数がnだとすると3^n - 1となる。n=100で500,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000ぐらい。近くを探したいのに、近くの数が膨大になってしまうので、探せなくなってしまうのだ。
LSHでは、
例えば1000次元のデータも、10次元ぐらいに押し込めてしまう。
「押し込める」ってのがハッシュらしいところだ。
３次元を２次元に押し込めるのは、箱に物を詰めて、それをギューッと潰して煎餅みたいにするのを想像してもらうといい。潰し方で色んな煎餅ができる。初代ターミネーターはプレス機で潰されて、どういう煎餅になったろうか。
潰し方で、できる模様は変わる。縦に潰すか、横に潰すか、斜めに潰すか。
そして潰し方がどうあれ、点と点との、もともとの距離の情報はある程度失われてしまう。潰す方向に直交する距離は保存されるが、潰す方向と平行な距離はゼロになる。
LSHでは、潰し方を変えて複数枚の煎餅を作る。その煎餅の数がLだ。
そして煎餅の上での距離が近いものを探す。煎餅が何枚かあれば、その中に本当に近いものが含まれているだろう。
しかし煎餅の作り方が上手でないと、上手く見つからないことになる。
例えば、まっすぐ上から潰したものと、ほんの少しだけ斜めに傾いで潰した煎餅の二枚からだと、うまくない。なぜなら、ほとんど同じ煎餅ができてしまうからだ。
例えば、まっすぐ上から潰したものと、真横から潰したものと、真正面から奥に向って潰した煎餅の三枚があれば、それぞれの煎餅はずいぶん違ってくるから、近くが見つかる可能性がずいぶん高くなる。
LSHでは、正規分布に従う独立なランダムな値を使って、多様な押しつぶし方を用意する。
すると、
正確には論文を読んでいただくしかないが、大雑把にはこれで良い。
「ばらける」というところがミソだ。必ず距離が保存されるのは、もちろん不可能だ。
潰しているのだから（次元を減らしているのだから、）ある程度は距離は捨象される。でも、それは確率的には、正規分布の範囲内で保存される、ということだ。
だから、まぁ煎餅を何枚か用意しておけば、どれかにはある程度の確率で入っていることが保証できる。
潰す先の次元をk, 煎餅の枚数をLとすると、Lが大きくなれば、近くが見つかる可能性はぐっと高まる。kを増やすとデータが少数のグループに分割されるので、探す手間は少なくなる。しかしLを増やすと、煎餅へのアクセス回数が増えて遅くなるし、kを増やすと発見できる可能性が減る上に、ハッシュ計算の回数が増える。見つけたい確率に応じてkやLを設定することになる。
LSHの論文の偉いところは、このあたりの確率と個数との数学的な関連を明確に示しているところだ。
LSH v2の実装は？
さて、上述の論文には「実装は簡単」と書かれていた。
「結論として、検索時間は多量のデータ数や大規模次元に関係なく一定だし、その上シンプルで、実装も簡単である。」とでも言うところか。
たしかに考え方は、すごくシンプルだ。だから実装も簡単に済むだろうと踏んでいた。まぁ、彼の言うことを信じたわけだが。
メモリ上だけで動作するLSHは、あっという間にできた。拍子抜けするくらい簡単にできたので、確かに簡単だ、と思った。
がしかし、メモリ上だけだと多量のデータや、高次元を扱えない。メモリが、あっという間に一杯になってしまうからだ。だからハードディスクを使うようにしなければならない。
で、昔、別のインデクシングエンジンを作った時もそれなりに苦労したが、今回も結局そこで時間をたくさん使ってしまった。
ハードディスクとメモリのデータのやり取りを効率的に行うには、キャッシングが重要になる。これが思いのほかバグを作りやすい。
まぁ、でも久しぶりに夢中になってコーディングしたなぁ。面白かった。
結局２０００行ぐらいになった。もっとシンプルにできるだろうと思う。途中で大きくは２回リファクタリングした。リファクタリングというのは、設計を見直して作り直す、ということだ。今回は腰をすえて開発をしたので、リファクタリングなどという事ができたが、いつもなら無理だな。
今、このwikiを入力しているLet's Note R3で動かしているが、そこそこのスピードが出ているので嬉しい。さて、本来の研究に一歩前進だ。
ここまでは他人の褌（ふんどし）である。
- LSHというのはハッシュテーブルの一種である。
- ハッシュテーブルというのは、ハッシュ関数を使った索引のことだ。
2006/1/10 ミスを修正
ハッシュ関数とは 
ハッシュ関数h()というのは、入力の値 x に対して、h(x) の値が、
- 近い x の場合にぶつかりにくく
- 一定の範囲に収まる
y=h(x)とする。xには0以上100,000,000以下の整数が入ってくるとしよう。
例えば、yの値域を0以上100以下の整数とする(一定の範囲に収める)。
h(x)=[x/1000000]（100000で割って少数切り捨て）とすると、確かに0から100の間に収まる。しかし、0から1000000までの値は全部0になってしまう。こういうのは、ぶつかりやすいという。
もう少しましなのが、y=x%97（素数97で割った余り）である。これだとx=0,1,2,3,4...が、それぞれy=0,1,2,3...になる。ばらばらな値になる。
とりあえずの条件はこんなものだが、何に使うか（目的）によって、別の条件が加わってくる。
Wikipediaのハッシュ関数の解説
暗号通信に使うハッシュ関数
例えば、現代におけるハッシュ関数の最大の利用目的は暗号通信だ。MD5とか聞いた事無いかな。その場合は、
- ハッシュ値(y)から、もとのxの推測が極めて困難
パスワードが"aho"だったとしよう。入力したパスワードが正しいかどうかを調べるためには、コンピュータの方に"aho"というのを用意しておいて、直接比べるのが一番単純だ。
しかし、そうするとコンピュータの中に"aho"というのが、そのまま残ってしまう。もしこのコンピュータのデータが盗まれたりしたら、パスワードが漏れてしまう。
そこでahoをハッシュ関数で変換した結果を、コンピュータに残しておくことにする。例えば h("aho") = 34129というような感じだ。コンピュータの中には34129しか残っていない。
パスワードをチェックする時には、入力された文字列をハッシュ関数で変換した値と、コンピュータの中に保存されている34129を比べればパスワードチェックができる。
検索に使うハッシュ関数
ハッシュテーブルというのは、このハッシュ関数を使った索引だ、というのは上に書いた。索引というのは、検索をすばやく行うための工夫だ。
分厚い本などは巻末に索引がついてて、特定の言葉が本のどこにあるのかを捜しやすくなっている。辞書しかり。
探したい情報をxとすると、ハッシュテーブルのh(x)の場所に、xの在り処が書かれている。
例えばx="livedoor Wiki"として、h(x)=34129だとすると、ハッシュテーブルの34129番目に、"livedoor Wiki"の在り処が書かれている。
yの値を、一定の範囲に収めることができるので、例えば、さまざまな種類の色んな情報を、一定のメモリ内の領域や、一定のハードディスク内の領域におさめることができる。
索引の作り方には、もうそれこそ一杯方法がある。データベース関連の研究会なんかでは、それこそ論文誌が全部索引の作り方で占められているぐらいだ。それでも毎月新しい索引が提案される。
世の中データベースだらけで、データベース無しでは動かない世界になってしまっているので、有用な索引作成手法は金になる。
索引としての、ハッシュテーブルの良いところは、適切なハッシュ関数があれば、探したい情報に一発でアクセスできる、という点だ。例えば、ツリー型の索引だと、ツリーをたどって行く時間がかかるが、ハッシュは一発だ。
しかし世の中そう甘くない。
「衝突」がおきるからだ。xは、それこそ膨大なバリエーションなのに対して、y (=h(x))は小さな領域におさめる必要があるので、当然ながら、違うxなのに、h(x)が同じになってしまう場合がある。これが衝突（コリジョン）だ。
衝突がおきた時の回避方法は極めて原始的で、次のどちらかを使う。
- ハッシュ値を+1する
- ハッシュテーブルに付属テーブルをくっつけて、そこに複数格納する
1の方法は、「衝突しちゃったか、ま、いいや隣にいれちゃえ」で、2の方法は「衝突しちゃったか、ま、いいや一緒に入れとけ」だ。
隣に入れちゃうと、どんどん隣が埋まってゆくので、本来入れるべきものが後ろ後ろに押しやられてしまう。これが始終起きると、もうハッシュテーブルの中はしっちゃかめっちゃかになる。一緒に入れておくと、一緒に入れた中から探す手間が増えてしまう。全部のデータが、一つの付属テーブルに入ってしまったら、もう索引の用はなしていない。
上の方で、適切なハッシュ関数、といったのは、この衝突がおきにくい関数という意味だ。
不適切なハッシュ関数の代表は、同じようなハッシュ値ばかり出す関数だ。理想的にはハッシュテーブルを満遍なく使って欲しい。
ところが、どういう入力値(x)が来るかは事前に予測できないから、最適なハッシュ関数というのはわからない。ま、そこそこ良いハッシュ関数というのがあるから、皆それを使う。
LSH: Locality-Sensitive Hashingとは
LSHでのハッシュ関数やハッシュテーブルは、上述したような通常のハッシュテーブルとは、ずいぶん違う。
LSHの目的は、似たようなものを高速に探し出す、ということにある。（普通のハッシュテーブルは同じものを高速に探し出す。）
こういうのを類似検索とか、近傍探索とかいう。類似検索や近傍探索のニーズは、これまたすごく多い。似たような文、似たような写真、似たような音楽、似たようなビデオ、を探す。
類似検索に良く使われるのはツリー型の索引だ。いろんなツリーが提案されている。LSHの良さは、そういったツリー型の索引に比べて速いということだ。その意味で、上述したハッシュ関数の良さをそのまま引き継いでいる。
しかし悪い点も同じく引き継いでいて、衝突がおきやすいとちっとも速くない。その衝突回避のメカニズムが良くできている。
LSHはIndykさんというスタンフォードの研究者が提案した方法だ。たぶん以下は彼の博士論文だろうと思う。すごく優秀な研究者だなぁ。
Indyk, Motwani. "Approximate nearest neighbor: towards removing the curse of dimensionality". STOC'98, section 4.2
VLDBというデータベースで最も有名な国際会議の一つで、その良さげな実装方法が提案されたのをうけて、色々な人が使っている。
Aristides Gionis, P. Indyk, R. Motwani, “Similarity Search in High Dimensions via Hashing”, Proceedings of the 25th VLDB Conference,pp.518-528,1999
この名前の並びからすると、Motwaniさんというのが教授かな。Gionisさんというのは、同じ研究室の人だろうな。この実装は、すごく良くできているのだが、LSHの原理からすると少し後退している。それはマンハッタン距離での近傍探索になっている点だ。
点(x1, y1)と点(x2, y2)の距離は、点の間を線で結んて、その線分の長さ、つまりユークリッド距離
sqrt((x1-x2)^2 + (y1-y2)^2)を使う。
マンハッタン距離というのは、縦横にしか動けないとした場合の道のりを表す。つまり
|x1-x2| + |y1-y2|となる。
データ同士の近さを計るのには、もちろん色んな尺度がある。マンハッタン距離も重要な一つで、利用範囲は広い。でもユークリッド距離の方が、より普通に使われる。
安定分布を使ったLSHの最新バージョン
Indykさんは、その後MITに移って助教授になっている。そこで書いた論文が以下だ。
M. Datar, P. Indyk, N. Immorlica and V. Mirrokni, "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions", (In Proceedings of the Symposium on Computational Geometry, 2004).
Datarさんというのは学生さんかな？ずいぶん優秀な学生さんだ。先生も優秀なら生徒も優秀、さすがMITだな。
こちらではユークリッド距離も使えるようにバージョンアップした実装が書かれている。そのために使っているのが、安定分布(p-stable distribution)だ。
Wikipediaの安定分布の解説
ユークリッド距離を使うためには、特性指数が2の安定分布である「正規分布」を使う。正規分布はおなじみだな。
さて、その手順は、次のようなものだ。
- 正規分布に従う独立な値を要素として持つベクトルaを、k個用意する
- k個のaと、オリジナルのデータxの内積を計算すると、k個の内積値が得られる
- k個の内積値を要素とするベクトルgができる
- gをハッシュ値とするハッシュテーブルを作る
- 同様の方法で、k個のaの組をL個用意し、gをL個作って、それぞれハッシュテーブルを作る
- xの値が似ていると、同じようなgができるので、L個のgに対応するところに近い値が格納されている
ちょっとわかりにくいかな。以下に大雑把に説明することにしよう。
LSH v2の大雑把な説明
近い値を探すのがLSHの目的なのだが、相手にするデータには、色んなものが来るので、近さ、というのを計算するのはけっこう大変だ。
一番簡単な方法は、登録されているデータすべてとの距離を計算して、近いものを見つけるという方法だが、これはデータ数が多くなると、それに応じてどんどん時間がかかるようになる。
１００個ぐらいならいいけれど、扱うデータが１００万個とかなると、もう大変。計算機はたしかに速くなったけど、扱うデータの数もどんどん多くなっている。
そこで考えられる素朴な方法が
- 近いものをあらかじめ集めておく
LSHの基本的な考え方もこれである。
例えば、碁盤の上に碁石をちらばらせたような状況を考えてみよう。
新しい碁石を左手前の星のあたりに置いたとして、近いものを探すのに右端を見たりはしない。左手前の付近で探す。
だから、左奥、右奥、左手前、右手前の四つのグループに分けておいて、探したい場所の付近のグループだけを捜せば、探す手間が四分の一になる。
１０Ｘ１０分割しておけば1/100になる。
まぁ碁盤のように２次元なら、これでもいい。ところが１０００次元となると、こうはいかない。分割した領域の数が膨大になってしまうのだ。各次元を１０分割したとして１０の１０００乗！。
１０００次元なんて必要なのか、という人もいるかもしれないが、白黒写真：横１００画素、縦１００画素だと10000次元になる。画素をそのまま使うというのは類似検索ではあまり使わないが、例としてあげた。
領域に番号をつけて、それをハッシュテーブルに格納するという方法も考えられる。新しいxが入ってきたら、それの属する領域の番号に対応するハッシュ値のところを探す、という方法だ。
ところが、３次元ぐらいならこれでもいいのだが、高次元になると実はあまり簡単でなくなる。それは隣の領域の数が増えてしまうからだ。
- １次元での隣、というのは、右と左の２つ。
- ２次元での隣は、右、左と上、下、それと斜めの四箇所、合計８箇所
- ３次元での隣は、２７箇所もある
この隣の数の計算は簡単で次元数がnだとすると3^n - 1となる。n=100で500,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000ぐらい。近くを探したいのに、近くの数が膨大になってしまうので、探せなくなってしまうのだ。
LSHでは、
- データを小さな空間に閉じ込める
例えば1000次元のデータも、10次元ぐらいに押し込めてしまう。
「押し込める」ってのがハッシュらしいところだ。
３次元を２次元に押し込めるのは、箱に物を詰めて、それをギューッと潰して煎餅みたいにするのを想像してもらうといい。潰し方で色んな煎餅ができる。初代ターミネーターはプレス機で潰されて、どういう煎餅になったろうか。
潰し方で、できる模様は変わる。縦に潰すか、横に潰すか、斜めに潰すか。
そして潰し方がどうあれ、点と点との、もともとの距離の情報はある程度失われてしまう。潰す方向に直交する距離は保存されるが、潰す方向と平行な距離はゼロになる。
LSHでは、潰し方を変えて複数枚の煎餅を作る。その煎餅の数がLだ。
そして煎餅の上での距離が近いものを探す。煎餅が何枚かあれば、その中に本当に近いものが含まれているだろう。
しかし煎餅の作り方が上手でないと、上手く見つからないことになる。
例えば、まっすぐ上から潰したものと、ほんの少しだけ斜めに傾いで潰した煎餅の二枚からだと、うまくない。なぜなら、ほとんど同じ煎餅ができてしまうからだ。
例えば、まっすぐ上から潰したものと、真横から潰したものと、真正面から奥に向って潰した煎餅の三枚があれば、それぞれの煎餅はずいぶん違ってくるから、近くが見つかる可能性がずいぶん高くなる。
LSHでは、正規分布に従う独立なランダムな値を使って、多様な押しつぶし方を用意する。
すると、
- オリジナルの空間での距離が、正規分布に従って、ばらけはするが、押しつぶした先にも反映される。
正確には論文を読んでいただくしかないが、大雑把にはこれで良い。
「ばらける」というところがミソだ。必ず距離が保存されるのは、もちろん不可能だ。
潰しているのだから（次元を減らしているのだから、）ある程度は距離は捨象される。でも、それは確率的には、正規分布の範囲内で保存される、ということだ。
だから、まぁ煎餅を何枚か用意しておけば、どれかにはある程度の確率で入っていることが保証できる。
潰す先の次元をk, 煎餅の枚数をLとすると、Lが大きくなれば、近くが見つかる可能性はぐっと高まる。kを増やすとデータが少数のグループに分割されるので、探す手間は少なくなる。しかしLを増やすと、煎餅へのアクセス回数が増えて遅くなるし、kを増やすと発見できる可能性が減る上に、ハッシュ計算の回数が増える。見つけたい確率に応じてkやLを設定することになる。
LSHの論文の偉いところは、このあたりの確率と個数との数学的な関連を明確に示しているところだ。
LSH v2の実装は？
さて、上述の論文には「実装は簡単」と書かれていた。
Consequently, the resulting query time bound is free of large factors and is simple and easy to implement.
「結論として、検索時間は多量のデータ数や大規模次元に関係なく一定だし、その上シンプルで、実装も簡単である。」とでも言うところか。
たしかに考え方は、すごくシンプルだ。だから実装も簡単に済むだろうと踏んでいた。まぁ、彼の言うことを信じたわけだが。
メモリ上だけで動作するLSHは、あっという間にできた。拍子抜けするくらい簡単にできたので、確かに簡単だ、と思った。
がしかし、メモリ上だけだと多量のデータや、高次元を扱えない。メモリが、あっという間に一杯になってしまうからだ。だからハードディスクを使うようにしなければならない。
で、昔、別のインデクシングエンジンを作った時もそれなりに苦労したが、今回も結局そこで時間をたくさん使ってしまった。
ハードディスクとメモリのデータのやり取りを効率的に行うには、キャッシングが重要になる。これが思いのほかバグを作りやすい。
まぁ、でも久しぶりに夢中になってコーディングしたなぁ。面白かった。
結局２０００行ぐらいになった。もっとシンプルにできるだろうと思う。途中で大きくは２回リファクタリングした。リファクタリングというのは、設計を見直して作り直す、ということだ。今回は腰をすえて開発をしたので、リファクタリングなどという事ができたが、いつもなら無理だな。
今、このwikiを入力しているLet's Note R3で動かしているが、そこそこのスピードが出ているので嬉しい。さて、本来の研究に一歩前進だ。
ここまでは他人の褌（ふんどし）である。
コメントをかく