数百万件の文書の中から、いま読んでいる記事と「ほとんど中身が同じ重複ページ」をどう見つければよいでしょうか。あるいは、数千万枚の画像データベースから、目の前の1枚に「見た目がそっくりな画像」をどう引けばよいでしょうか。素朴にやるなら、クエリを全件と1つずつ比べる総当たりです。1件の比較が速くても、件数が $N$ あれば $O(N)$ かかり、$N$ が億のオーダーになると1回の検索すら現実的な時間で終わりません。
ここで効いてくるのが「似たものは、わざわざ全部比べなくても、最初から近くにまとめておけばいい」という発想です。普通のハッシュは「同じものは同じ場所、少しでも違えばまったく別の場所」に飛ばします。これは重複の排除には便利ですが、「似ているけれど少し違うもの」を近くに置いてはくれません。LSH（Locality Sensitive Hashing、局所性鋭敏ハッシュ）は、この常識をひっくり返します。近いものほど同じバケツ（ハッシュ値）に落ちやすく、遠いものほど別のバケツに落ちやすいハッシュをわざと設計するのです。すると、クエリと同じバケツに入っている少数の候補だけを精査すればよくなり、全件走査が一気に「ほんの数%の走査」に縮みます。
LSHが活きる場面は驚くほど広く、たとえば次のようなものです。
- 文書重複検出（near-duplicate detection）：Webクロールで集めた大量のページから、コピーやわずかな改変の重複を検出する。検索エンジンの索引づくりで実際に使われてきた古典的応用です。
- 画像・埋め込みの近傍検索：画像やテキストをベクトルに変換（埋め込み）したうえで、「見た目／意味が近いもの」を高速に引く。レコメンド、画像検索、ベクトルデータベースの内部などで使われます。
本記事では、LSHの心臓部である「衝突確率が距離の単調関数になるハッシュ族」という考え方を、ランダム超平面を使う SimHash（Charikar 2002）を主役に据えて組み立てます。SimHashの衝突確率がぴったり $1-\theta/\pi$（$\theta$ はベクトルのなす角）になることを導出し、それを AND/OR増幅でS字曲線に整形して「似たものだけ急に拾う」装置に変える理屈を追います。最後にSimHashをスクラッチ実装し、衝突確率が理論曲線に一致すること、増幅後のS字、そして全探索に対する recall と 走査削減率 を実測して、近似最近傍探索が本当に速く・正しく動くことを確認します。
本記事の内容
- 「似たものを同じバケツに」というLSHの直感と、$(r_1,r_2,p_1,p_2)$-sensitive族の定義
- SimHash（ランダム超平面）の衝突確率 $P[h(x)=h(y)]=1-\theta/\pi$ の導出
- AND/OR増幅で衝突確率を $1-(1-p^k)^L$ のS字に整形する理論
- JL補題（ランダム射影で距離が保たれる）との関係
- SimHashのスクラッチ実装と、衝突確率・S字・recall@k・走査削減率の実測
前提・関連記事
この記事は「ベクトルの近さをどう測るか」「埋め込みの近傍検索をどう速くするか」という流れの上にあります。下記を先に読んでおくと、距離・コサイン類似度の感覚と、近似最近傍探索が解こうとしている問題がつかめます。
なぜハッシュで近傍が引けるのか
普通のハッシュテーブルを思い出しましょう。キー（たとえば文字列）をハッシュ関数 $h$ に通すと、整数のバケツ番号が出てきます。理想的なハッシュは「衝突をできるだけ避ける」ように作られていて、入力が1文字でも違えば出力はまったく無関係な値に飛びます。だからこそ、辞書検索やキャッシュで「完全一致」を $O(1)$ で引けるわけです。
ところが、私たちが本当にやりたいのは完全一致ではありません。「だいたい同じ」「そっくり」を引きたいのです。ここで、もし「入力が近いほど、同じバケツに落ちやすい」ハッシュがあったらどうなるでしょうか。クエリ $q$ をハッシュして、同じバケツに入っている要素だけを取り出せば、それらは「$q$ に近い可能性が高い候補」になります。あとはその少数の候補だけを実際の距離で精査すればよい。全件 $N$ を見ずに、バケツの中の数件だけを見ればいいのです。
上の図がLSHのいちばんの直感です。2次元平面に点群を置き、原点を通る3本の「ランダムな超平面（2次元では直線）」を引きました。各点について「それぞれの超平面のどちら側にいるか」を符号ビット（0/1）で表し、3本ぶんを並べた符号がその点の ハッシュ値 です。同じ符号（同じ色）になった点が同じバケツに入ります。注目すべきは、近くに固まっている点ほど、どの超平面でも同じ側に来やすく、同じ色になりやすいという点です。遠く離れた点どうしは、どこかの超平面で反対側に分かれてしまい、別のバケツに落ちます。これが「近いものほど衝突しやすい」ハッシュの正体です。
つまりLSHでは、ハッシュの衝突は避けるべき事故ではなく、わざと起こしたいご褒美です。問題は「どうやって近いものほど衝突するハッシュを作るか」「衝突確率を距離とどう結びつけるか」です。まずはこの『衝突しやすさ』をきちんと定義するところから始めましょう。
局所性鋭敏ハッシュ族の定義：(r1, r2, p1, p2)-sensitive
LSHの理論的な土台は、Indyk と Motwani が1998年に与えた 局所性鋭敏ハッシュ族（LSH family） の定義です。いきなり記号を並べる前に、言葉で言ってしまいましょう。私たちが欲しいのは、「近い2点はかなりの確率で同じバケツに、遠い2点はめったに同じバケツに入らない」ハッシュ関数の集まりです。ハッシュ関数を1つに固定するのではなく、ランダムに1つ選ぶ、という点が鍵になります。
距離関数を $d(\cdot,\cdot)$ とします。近さの基準として2つの半径 $r_1 < r_2$ を決め、衝突確率の基準として2つの確率 $p_1 > p_2$ を決めます。ハッシュ関数の族 $\mathcal{H}$ が $(r_1, r_2, p_1, p_2)$-sensitive であるとは、$\mathcal{H}$ からランダムに $h$ を1つ選んだとき、次の2条件が成り立つことをいいます。
$$ \begin{equation} \begin{aligned} d(x,y) \le r_1 &\;\Rightarrow\; \Pr_{h\sim\mathcal{H}}[\,h(x)=h(y)\,] \ge p_1 \\ d(x,y) \ge r_2 &\;\Rightarrow\; \Pr_{h\sim\mathcal{H}}[\,h(x)=h(y)\,] \le p_2 \end{aligned} \end{equation} $$
1行目は「近い（距離が $r_1$ 以下）なら、少なくとも確率 $p_1$ で衝突する」。2行目は「遠い（距離が $r_2$ 以上）なら、衝突するのはせいぜい確率 $p_2$ まで」という意味です。$p_1 > p_2$ なので、近い方が確実に衝突しやすいという非自明な性質が保証されています。$r_1$ と $r_2$ のあいだ（中間距離）については何も保証しません。そこはグレーゾーンとして割り切るのです。
この図は、横軸を2点間の距離、縦軸を衝突確率（正確には後で作る増幅後の「候補に入る確率」）として、$(r_1, r_2, p_1, p_2)$ の関係を描いたものです。距離が $r_1$ 以下の左端では確率がほぼ1（$p_1$ が高い）、距離が $r_2$ 以上の右側では確率がほぼ0（$p_2$ が低い）になっています。$r_1$ と $r_2$ にはさまれた黄色い帯が「保証なしの中間帯」です。LSHの良し悪しは、$p_1$ と $p_2$ の 比 がどれだけ大きいか、言い換えれば「この曲線をどれだけ急な崖にできるか」で決まります。崖が急なほど、近いものと遠いものをはっきり選り分けられます。
定義はわかりました。では、この性質を実際に満たすハッシュをどう作るのでしょうか。コサイン類似度（角度）に対して鮮やかに機能するのが、ランダム超平面を使うSimHashです。
SimHash：ランダム超平面で符号を取る
SimHash（Charikar 2002）の作り方は拍子抜けするほど単純です。$d$ 次元空間にベクトル $\bm{x}$ があるとき、ランダムな法線ベクトル $\bm{r}$（各成分を標準正規分布から独立に引く）を用意し、内積の符号を取ります。
$$ \begin{equation} h_{\bm{r}}(\bm{x}) = \operatorname{sign}(\bm{r}\cdot\bm{x}) = \begin{cases} 1 & (\bm{r}\cdot\bm{x} \ge 0) \\ 0 & (\bm{r}\cdot\bm{x} < 0) \end{cases} \end{equation} $$
$\bm{r}\cdot\bm{x}=0$ は原点を通る超平面で、$\bm{r}$ はその法線です。$h_{\bm{r}}(\bm{x})$ は「$\bm{x}$ がこの超平面のどちら側にいるか」をたった1ビットで表しています。ハッシュ族 $\mathcal{H}$ とは、$\bm{r}$ をランダムに選ぶことで得られる関数の集まりにほかなりません。
このハッシュが近さを反映するのは、図1で見たとおり「近い2点は同じ側に来やすい」からです。これを確率の言葉できちんと言うと、2つのベクトル $\bm{x}, \bm{y}$ が1枚のランダム超平面で別々の側に分かれてしまう確率は、2つのなす角 $\theta$ に比例する、という美しい事実になります。次の節でこれを導出します。
その前に、1枚の超平面が「近い／遠い」をどう扱うかを実験で見ておきましょう。
左は互いに近い2ベクトル（なす角が小さい）、右は離れた2ベクトル（なす角が大きい）です。それぞれに対して、ランダムな超平面をたくさん引き、2点が反対側に分断される割合を数えました。左の小さい角度では分断率が小さく（=同じ側＝衝突しやすい）、右の大きい角度では分断率が大きい（=別バケツになりやすい）ことが見て取れます。しかも、その分断率はどちらも理論値 $\theta/\pi$ にぴたりと一致しています。角度こそが衝突しやすさを決める——これがSimHashの核心です。なぜ $\theta/\pi$ になるのか、いよいよ導出しましょう。
衝突確率 1 − θ/π の導出
ここでのゴールは、1枚のランダム超平面に対して、$\bm{x}$ と $\bm{y}$ が同じ側に来る確率（=衝突確率）が $1-\theta/\pi$ になることを示すことです。$\theta$ は $\bm{x}$ と $\bm{y}$ のなす角です。
まず問題を整理します。法線ベクトル $\bm{r}$ の各成分を独立に標準正規分布 $\mathcal{N}(0,1)$ から引きました。多変量正規分布のこの取り方には、とても都合のよい性質があります。それは 回転対称性 です。標準正規ベクトルの向き $\bm{r}/\|\bm{r}\|$ は、単位球面上で完全に一様に分布します。どの方向も特別扱いされません。
$\bm{x}$ と $\bm{y}$ が「別々の側」に分かれるのは、超平面（法線 $\bm{r}$）が2点のあいだに割り込むときです。符号は $\bm{r}\cdot\bm{x}$ と $\bm{r}\cdot\bm{y}$ で決まるので、内積の値そのものより $\bm{r}$ の向き だけが効きます。さらに、$\bm{x}$ と $\bm{y}$ が張る2次元平面に $\bm{r}$ を射影した成分だけが符号を左右します（その平面に直交する成分は両方の内積に同じだけ効くわけではなく、実は符号の境界は2次元平面内の向きで決まります）。そこで問題は、「$\bm{x}, \bm{y}$ を含む平面の中で、ランダムな方向 $\bm{u}$（一様）を引いたとき、$\bm{x}$ と $\bm{y}$ がその方向に対して反対符号になる確率はいくらか」 に帰着します。
2次元平面内で考えます。$\bm{x}$ と $\bm{y}$ のなす角は $\theta$ です。ランダムな単位方向 $\bm{u}$（角度 $\phi$ が $[0, 2\pi)$ で一様）に対し、$\bm{x}$ の符号は「$\bm{u}$ が $\bm{x}$ から見て上半面か下半面か」で決まります。$\bm{u}$ に直交する直線（=超平面と平面の交線）が $\bm{x}$ と $\bm{y}$ のあいだを通るとき、2点は分断されます。$\bm{x}$ と $\bm{y}$ のあいだの角度幅は $\theta$、その反対側にも同じ幅 $\theta$ の領域があります。交線の向きが $2\pi$ のうちこの $2\theta$ ぶんに入ると分断が起きます。したがって分断確率は
$$ \Pr[\text{分断}] = \frac{2\theta}{2\pi} = \frac{\theta}{\pi} $$
となります。衝突（同じ側）はその余事象なので、
$$ \begin{equation} \Pr_{\bm{r}}[\,h_{\bm{r}}(\bm{x}) = h_{\bm{r}}(\bm{y})\,] = 1 – \frac{\theta}{\pi} \end{equation} $$
が得られます。導出を言葉でたどり直すと、(1) ランダム法線の向きは一様、(2) 符号を分けるかどうかは平面内の向きだけで決まる、(3) 分断が起きる向きの幅は全体 $2\pi$ のうち $2\theta$、だから分断確率は $\theta/\pi$、衝突確率はその余事象で $1-\theta/\pi$、という3ステップです。
この式は驚くほどきれいな性質を持ちます。$\theta=0$（同じ向き）なら衝突確率は1（必ず同じバケツ）、$\theta=\pi/2$（直交）なら $1-1/2=0.5$、$\theta=\pi$（真逆）なら0（必ず別バケツ）。衝突確率が角度の単調減少関数になっており、まさに $(r_1, r_2, p_1, p_2)$-sensitive の条件を、角度を距離とみなして満たしています。
それでは、この理論式を実装で検証します。$d$ 次元でたくさんのランダム超平面を引き、与えた角度ごとに衝突割合を数えてみましょう。
import numpy as np
def simhash_signature(X, planes):
"""X:(N,d), planes:(k,d)。各点をk個の符号ビット(0/1)に。h_r(x)=sign(r·x)。"""
proj = X @ planes.T # (N,k) 各超平面への射影
return (proj >= 0).astype(np.int8)
rng = np.random.default_rng(0)
d, K = 50, 20000
planes = rng.normal(0, 1, (K, d)) # K枚のランダム超平面
thetas = np.linspace(0.01, np.pi-0.01, 25)
x = np.zeros(d); x[0] = 1.0
emp = []
for th in thetas:
y = np.zeros(d); y[0] = np.cos(th); y[1] = np.sin(th) # xとなす角θのy
hx = (planes @ x >= 0)
hy = (planes @ y >= 0)
emp.append(np.mean(hx == hy)) # 衝突=同じ符号の割合
emp = np.array(emp)
theory = 1 - thetas/np.pi
print("最大誤差 :", round(float(np.max(np.abs(emp - theory))), 5))
このコードを実行すると、最大誤差は約 0.0038（超平面の枚数を増やせばさらに小さくなる、純粋なサンプリング誤差）でした。つまり実測の衝突割合は理論式 $1-\theta/\pi$ にほぼ完全に乗っています。
青い直線が理論 $1-\theta/\pi$、橙の点が実測です。25個の角度すべてで点が直線にぴたりと乗っており、$\theta=0$ で確率1、$\theta=\pi/2$（90度）で0.5、$\theta=\pi$（180度）で0という、導出どおりの振る舞いが確認できます。理論と実測が一致したことで、SimHashが本当に「角度＝近さ」を衝突確率に変換していることが裏づけられました。
角度の代わりにコサイン類似度で見ると、もっと直感的になります。
横軸をコサイン類似度 $\cos\theta$、縦軸を1枚あたり衝突確率 $p=1-\theta/\pi$ に取り直したものです。$\cos\theta=1$（そっくり）で衝突確率が最大、$\cos\theta=0$（直交、無関係）でちょうど0.5、$\cos\theta=-1$（正反対）で0という、単調増加のなめらかな曲線になります。似ているほど同じバケツに入りやすいという、私たちが最初に欲しかった性質が、たった1ビットのハッシュで実現できているのです。
ただし、1枚の超平面だけだと衝突確率の差が緩やかすぎます。直交していても0.5で衝突するし、かなり似ていても0.8止まり。これでは「似たものだけ拾う」には甘すぎます。そこで複数のハッシュを組み合わせて、この曲線を急な崖に整形します。それが増幅です。
AND/OR増幅：衝突確率をS字に整形する
1枚あたりの衝突確率を $p$ とします（$p=1-\theta/\pi$）。これを材料に、より切れ味の鋭い検出器を作りましょう。道具は2つだけ、AND構成 と OR構成 です。
AND構成は、$k$ 個の独立なハッシュを連結して1つのキーにします。$k$ 個すべてが一致して初めて「衝突」とみなします。各ハッシュが独立に確率 $p$ で一致するので、$k$ 個すべて一致する確率は
$$ \begin{equation} p_{\text{AND}} = p^k \end{equation} $$
です。$p<1$ なら $p^k$ は $p$ より小さくなり、$k$ を大きくするほど急速に小さくなります。つまりANDは 衝突の基準を厳しくする 操作で、少しでも似ていない相手を切り捨てます（偽陽性＝遠いのに衝突、を減らす）。
$k$ を大きくするほど曲線が右下に押し込まれ、$p$ が1に近い（=とても似ている）相手しか衝突しなくなる様子が見えます。$k=16$ では、$p=0.9$ くらいに似ていても衝突確率は $0.9^{16}\approx0.19$ まで落ちます。ANDは強力ですが、やりすぎると「本当は近いのに取りこぼす」副作用（偽陰性）が出ます。それを救うのがORです。
OR構成は、$L$ 個の独立なハッシュテーブルを用意し、そのうちどれか1つでも衝突すれば候補とみなすやり方です。1テーブルあたりの衝突確率を $q$ とすると、$L$ 個すべてで衝突しない確率は $(1-q)^L$ なので、少なくとも1つで衝突する（=候補に入る）確率は
$$ \begin{equation} p_{\text{OR}} = 1 – (1-q)^L \end{equation} $$
です。$L$ を大きくするほど $1-(1-q)^L$ は1に近づきます。ORは 取りこぼしを減らす 操作で、再現率（recall）を上げます。
$L$ を増やすほど曲線が左上に持ち上がり、$q$ が小さくても（=そこそこの類似でも）どれかのテーブルで拾えるようになります。ANDは確率を押し下げ、ORは押し上げる。この2つを組み合わせるのがLSHの設計の妙です。
実用のLSHは、$L$ 個のテーブルを作り、各テーブルのキーを $k$ 個のハッシュのANDで作ります。すると、1テーブルでの衝突確率は $p^k$、それが $L$ 個のうちどれかで起きればよいので、最終的に「候補に入る確率」は
$$ \begin{equation} P_{\text{cand}}(p) = 1 – (1 – p^k)^L \end{equation} $$
となります。これがLSHの 増幅後の衝突確率 で、$p$ の関数として S字（シグモイド状）の崖 を描きます。導出の流れをもう一度たどると、(1) $k$ 個のANDで1テーブルの衝突を $p^k$ に厳しくし、(2) $L$ 個のテーブルのORで $1-(1-p^k)^L$ に取りこぼしを救う、という2段重ねです。
赤い破線が増幅なし（$k=L=1$、ただの直線 $p$）です。$k$ と $L$ を増やしていくと、曲線がだんだん急なS字になり、ある類似度を境に「ほとんど0」から「ほとんど1」へ一気に立ち上がるのが分かります。$k=12, L=40$ では、類似度が低い領域はほぼ完全に切り捨て、高い領域だけを急に拾い上げる、理想的な崖になっています。この崖の立ち上がり位置（しきい値）は $k$ で、崖の手前での拾いやすさは $L$ で調整できます。S字の変曲点はおおよそ $p^k \approx 1/L$、すなわち $p \approx (1/L)^{1/k}$ のあたりに来ます。$k$ を上げると崖が右（より厳しい類似度）へ動き、$L$ を上げると崖が全体的に持ち上がります。
S字の急峻さを定量化する指標が、LSH族の $\rho$ 値 です。$\rho = \dfrac{\log(1/p_1)}{\log(1/p_2)}$ と定義され、$\rho$ が小さい族ほど良い崖（近いものと遠いものをはっきり分ける）を作れます。SimHashのような良いLSH族では、$N$ 件のデータに対する近似最近傍探索が $O(N^\rho)$ 時間（$\rho<1$）でできることが、Indyk–Motwaniの枠組みから保証されます。全件 $O(N)$ より確実に速い、というのがLSHの理論的な約束です。
S字をどう作るかは分かりました。では、このS字の「崖の手前」と「崖の向こう」を距離で言い表すと、ちょうど $(r_1, r_2, p_1, p_2)$-sensitive の定義に戻ります。先ほどの図8のS字は、まさにこの増幅後の $P_{\text{cand}}$ を距離軸で描いたものでした。近い距離（$r_1$ 以下）では $P_{\text{cand}} \ge p_1$、遠い距離（$r_2$ 以上）では $P_{\text{cand}} \le p_2$。増幅とは、$(r_1,r_2,p_1,p_2)$ の比 $p_1/p_2$ を人為的に引き伸ばす操作だったのです。
理論がそろったので、実際にLSH索引を組み立てて、全探索とどれだけ違うかを測ってみましょう。
SimHashのスクラッチ実装：L個のテーブル × 各k個のハッシュ
ここまでの理論をそのままコードに落とします。索引づくりは「$L$ 個のテーブルを用意し、各テーブルで $k$ 枚のランダム超平面を引き、全データ点の $k$ ビット符号を1つの整数キーにまとめてバケツに振り分ける」だけです。
import numpy as np
def simhash_signature(X, planes):
proj = X @ planes.T
return (proj >= 0).astype(np.int8)
def build_lsh(X, k, L, seed=0):
"""L個のテーブル。各テーブルはk枚の超平面でkビット符号→整数キー→バケツ。"""
rng = np.random.default_rng(seed)
N, d = X.shape
tables = []
for _ in range(L):
planes = rng.normal(0, 1, (k, d)) # k枚のランダム超平面
sig = simhash_signature(X, planes) # (N,k) のビット
keys = sig.dot(1 << np.arange(k)[::-1]) # kビットを1つの整数に
buckets = {}
for idx, key in enumerate(keys):
buckets.setdefault(int(key), []).append(idx)
tables.append((planes, buckets))
return tables
def lsh_query(q, tables, k):
"""qと同じバケツに入る候補集合(全テーブルの和=OR)。"""
cand = set()
for planes, buckets in tables:
bit = (planes @ q >= 0).astype(np.int8)
key = int(bit.dot(1 << np.arange(k)[::-1]))
cand.update(buckets.get(key, [])) # どれかのテーブルで衝突=候補
return cand
設計のポイントは2つです。第一に、各テーブルのキーは $k$ ビットのANDになっている（$k$ ビットすべて一致しないと同じバケツに入らない）こと。第二に、クエリ時は $L$ 個のテーブルを横断して候補を 和集合（OR）で集めること。つまり、このコードの中に $1-(1-p^k)^L$ という増幅がそのまま埋め込まれています。
クエリは、同じバケツの候補だけを集め、その候補に対してだけ本物の距離（ここではコサイン類似度）を計算して上位を返します。全件を見ないのが速さの源です。では、合成データで全探索と比べてみましょう。
def cosine_topk(X, q, kk=10):
sims = X @ q / ((np.linalg.norm(X, axis=1) * np.linalg.norm(q)) + 1e-12)
return set(np.argsort(-sims)[:kk])
rng = np.random.default_rng(42)
N, d = 4000, 64
centers = rng.normal(0, 1, (20, d)) # 20個のクラスタ中心
X = centers[rng.integers(0, 20, N)] + 0.35*rng.normal(0, 1, (N, d))
Q = X[rng.choice(N, 80, replace=False)] + 0.05*rng.normal(0, 1, (80, d)) # 近傍クエリ
truth = [cosine_topk(X, q, 10) for q in Q] # 全探索の正解top10
for k, L in [(8,1),(8,4),(8,8),(8,16),(12,8),(12,20),(16,20),(16,40)]:
tables = build_lsh(X, k, L, seed=1)
recs, scans = [], []
for q, tr in zip(Q, truth):
cand = lsh_query(q, tables, k)
if cand:
cl = np.array(sorted(cand))
sims = X[cl] @ q / ((np.linalg.norm(X[cl], axis=1)*np.linalg.norm(q)) + 1e-12)
got = set(cl[np.argsort(-sims)[:10]]) # 候補だけで再ランキング
else:
got = set()
recs.append(len(got & tr) / 10.0) # recall@10
scans.append(len(cand)) # 走査した候補数
print(f"k={k:2d} L={L:2d} recall@10={np.mean(recs):.3f} 走査率={np.mean(scans)/N:.3f}")
実行すると、次のような結果になります（seed固定なので再現します）。
k= 8 L= 1 recall@10=0.441 走査率=0.021
k= 8 L= 4 recall@10=0.854 走査率=0.055
k= 8 L= 8 recall@10=0.969 走査率=0.083
k= 8 L=16 recall@10=0.999 走査率=0.109
k=12 L= 8 recall@10=0.824 走査率=0.037
k=12 L=20 recall@10=0.975 走査率=0.050
k=16 L=20 recall@10=0.910 走査率=0.039
k=16 L=40 recall@10=0.982 走査率=0.047
ここで recall@10 は「全探索の正解top10のうち、LSHが取り出せた割合」、走査率 は「距離計算した候補数 ÷ 全件数」です。走査率が小さいほど速く、recallが高いほど正確です。理論どおり、$L$ を増やすと recall が上がる（OR増幅）一方で走査率も上がる、というトレードオフがはっきり読み取れます。$k=8, L=16$ では recall がほぼ1.0なのに、走査したのは全体の約11%だけ。$k=12, L=20$ なら走査率5%で recall 0.975 と、全件のわずか5%を見るだけで正解の97.5%を回収できています。
左の図は $k=8$ を固定して $L$ を変えたときの recall（緑）と走査率（橙）です。$L$ を増やすと両方とも上がり、再現率と計算量がトレードオフの関係にあることが分かります。右の散布図は全構成について「走査率（横、小さいほど速い）」対「recall（縦、高いほど正確）」を打ったものです。左上に行くほど良い（速くて正確）。$k$ を大きく取りつつ $L$ で補うと、同じ recall をより小さい走査率で達成できる構成が見つかります。これが「$k$ で崖を厳しくし、$L$ で取りこぼしを救う」というS字設計の実利です。
代表的な構成での「どれだけサボれたか」を可視化しておきましょう。
全探索は全件（100%）に対して距離計算するのに対し、$k=12, L=20$ のLSHは全体の 5.0% だけを精査し、それで recall@10 = 0.975 を達成しています。残りの95%はそもそもバケツが違うので一度も触りません。データが大きくなるほど、この「触らずに済む割合」がそのまま高速化に直結します。近似最近傍探索が、精度をほとんど落とさずに走査を桁で削れることが、実測で確認できました。
ここまでは角度（コサイン類似度）に対するSimHashでした。LSHはほかの距離にも作れます。代表として、ユークリッド距離（L2）用のハッシュを見ておきましょう。
p-stable分布によるL2用LSH
コサイン類似度ではなく ユークリッド距離 L2 で近傍を引きたいときは、Datar らが2004年に提案した p-stable分布によるLSH を使います。アイデアはSimHashと地続きで、「ランダムに射影してから量子化する」というものです。
ランダムな射影ベクトル $\bm{a}$（各成分を正規分布から引く）と、$[0,w)$ 一様乱数のオフセット $b$、そして帯の幅 $w$ を使い、
$$ \begin{equation} h_{\bm{a},b}(\bm{x}) = \left\lfloor \frac{\bm{a}\cdot\bm{x} + b}{w} \right\rfloor \end{equation} $$
とします。$\bm{a}\cdot\bm{x}$ は $\bm{x}$ を1次元に射影した値で、それを幅 $w$ の帯（バケツ）に切り分け、同じ帯に落ちた点を同じバケツとみなします。
ランダムな射影方向 $\bm{a}$（赤矢印）に沿って空間を幅 $w$ の縞模様に区切り、同じ縞に入った点を同じ色（同じバケツ）にしています。近い点ほど同じ縞に入りやすく、遠い点ほど別の縞に分かれます。
なぜ正規分布を使うとL2距離に効くのか。鍵は 安定分布（stable distribution） という性質です。正規分布は「2-stable分布」と呼ばれ、次の性質を持ちます。$\bm{a}$ が標準正規ベクトルのとき、射影差 $\bm{a}\cdot(\bm{x}-\bm{y})$ は、平均0・標準偏差が $\|\bm{x}-\bm{y}\|_2$ に比例する正規分布に従います。
$$ \bm{a}\cdot(\bm{x}-\bm{y}) \sim \mathcal{N}\!\left(0,\; \|\bm{x}-\bm{y}\|_2^2\right) $$
つまり、1次元に射影した後の差の散らばりが、元のL2距離をそのまま反映します。距離が近い2点は射影差も小さいので同じ帯（バケツ）に入りやすく、遠い2点は射影差が大きいので別の帯に分かれやすい。こうして $(r_1, r_2, p_1, p_2)$-sensitive がL2距離に対して成立します。SimHashが「角度を符号で測った」のに対し、p-stable LSHは「距離を量子化された射影で測る」わけです。帯の幅 $w$ が増幅パラメータ $k$ と並ぶ調整つまみになります。
射影が距離を保つ、というこの性質は、もっと一般的で有名な定理 —— JL補題 —— の特別な場合と見ることができます。最後に、LSHの土台にあるこの定理を押さえておきましょう。
JL補題：ランダム射影は距離をほぼ保つ
SimHashもp-stable LSHも、根っこには「高次元のベクトルを、ランダムな方向に射影しても、距離関係はだいたい保たれる」という事実があります。これを精密に述べたのが Johnson–Lindenstrauss（JL）補題 です。
JL補題のステートメントは次のとおりです。任意の $0<\varepsilon<1$ と、$d$ 次元空間内の $N$ 点に対して、目標次元
$$ \begin{equation} k = O\!\left(\frac{\log N}{\varepsilon^2}\right) \end{equation} $$
を取れば、適切なランダム線形写像 $f:\mathbb{R}^d \to \mathbb{R}^k$ が存在して、すべての点対 $\bm{x}, \bm{y}$ について
$$ \begin{equation} (1-\varepsilon)\,\|\bm{x}-\bm{y}\|^2 \le \|f(\bm{x})-f(\bm{y})\|^2 \le (1+\varepsilon)\,\|\bm{x}-\bm{y}\|^2 \end{equation} $$
が高い確率で成り立ちます。注目すべきは、必要な次元 $k$ が 元の次元 $d$ に一切依存せず、点の数 $N$ の対数だけで決まる点です。$N$ が100万でも、$\varepsilon$ をそこそこに取れば、数百次元程度に圧縮しても距離が $\pm\varepsilon$ の範囲で保たれます。$f$ は具体的には「各成分を正規分布から引いたランダム行列で射影し、$1/\sqrt{k}$ でスケールする」だけで作れます。
これがLSHにとって何を意味するか。LSHは「近さ＝距離」を衝突確率に翻訳する仕組みでした。JL補題は「ランダム射影が距離を壊さない」ことを保証するので、ランダムな超平面や射影で次元を落としても、近いものは近いままであり、衝突確率の議論が崩れない、という土台を与えます。SimHashの各超平面も、p-stableの各射影も、JL補題が支える「距離を保つランダム射影」の一種なのです。
実際に距離が保たれるか、実験で見てみましょう。
import numpy as np
rng = np.random.default_rng(7)
d, N = 500, 300
X = rng.normal(0, 1, (N, d)) # 500次元の点群
i = rng.integers(0, N, 1500); j = rng.integers(0, N, 1500)
mask = i != j; i, j = i[mask], j[mask]
orig = np.linalg.norm(X[i] - X[j], axis=1) # 元の距離
for kk in [20, 50, 150]:
R = rng.normal(0, 1, (d, kk)) / np.sqrt(kk) # JLスケーリング付きランダム射影
Y = X @ R # k次元へ圧縮
proj = np.linalg.norm(Y[i] - Y[j], axis=1)
ratio = proj / orig
print(f"k={kk:3d}: 距離比の平均={ratio.mean():.3f} 標準偏差={ratio.std():.3f}")
実行すると、距離比（射影後距離 ÷ 元距離）の平均はどの $k$ でもほぼ1.0で、$k$ を大きくするほど標準偏差が小さく（=保存が鋭く）なります。500次元を50次元に落としても、距離比は1付近に集中したままです。
左は距離比のヒストグラムで、どの $k$ でも1（赤の破線）の周りに山ができ、$k$ が大きいほど鋭く尖ります。右は元の距離（500次元）と射影後の距離（50次元）の散布図で、点が対角線 $y=x$ にきれいに乗っています。たった50次元への圧縮でも、500次元での距離関係がほぼそのまま保たれていることが見て取れます。これがLSHの近似が「壊れない」ことの理論的な裏づけです。次元の呪いに苦しむ高次元の近傍探索が、ランダム射影とハッシュで現実的になる根拠が、この一枚に詰まっています。
JL補題まで来たことで、LSHを支える理論の柱が一通りそろいました。SimHashの衝突確率、AND/ORによるS字整形、$(r_1,r_2,p_1,p_2)$-sensitive、p-stableによるL2拡張、そしてランダム射影の距離保存。最後に全体を振り返ります。
まとめ
本記事では、LSH（局所性鋭敏ハッシュ）を、衝突確率の導出を主役に据えてスクラッチ実装まで組み上げました。
- LSHの直感：普通のハッシュと逆に、近いものほど同じバケツに落ちやすいハッシュをわざと作る。同じバケツの少数候補だけを精査すれば、全件走査が数%の走査に縮む。
- $(r_1,r_2,p_1,p_2)$-sensitive族：近距離（$r_1$ 以下）は確率 $p_1$ 以上で衝突、遠距離（$r_2$ 以上）は確率 $p_2$ 以下でしか衝突しない、という保証。$p_1/p_2$ の比が大きいほど良い族。
- SimHashの衝突確率：ランダム超平面の符号を取るだけで、$P[h(\bm{x})=h(\bm{y})] = 1-\theta/\pi$。回転対称性から3ステップで導け、実測ともぴたり一致した。
- AND/OR増幅：$k$ 個のANDで衝突を $p^k$ に厳しくし、$L$ 個のテーブルのORで $1-(1-p^k)^L$ に取りこぼしを救う。これが衝突確率をS字の崖に整形し、$\rho<1$ の高速探索を生む。
- L2用のp-stable LSH と JL補題：正規分布の安定性で射影差がL2距離を反映し、ランダム射影が距離をほぼ保つ（次元は $O(\log N/\varepsilon^2)$ で十分）。LSHの近似が壊れない土台になっている。
実装では、$k=12, L=20$ のSimHash索引が、全体のわずか5%だけを精査して recall@10 = 0.975 を達成しました。精度をほぼ落とさず、走査を桁で削る——これがハッシュ型近似最近傍探索の威力です。
LSHはハッシュ型のANN（近似最近傍探索）の代表ですが、近傍探索には別系統の強力な手法もあります。グラフをたどる HNSW、ベクトルを粗く量子化して圧縮する 積量子化（Product Quantization） などです。これらは精度・速度・メモリのトレードオフが異なり、実務ではデータ規模や次元に応じて使い分けます。次のステップとして、近似最近傍探索の全体像と、それを支えるベクトルデータベースの仕組みを押さえる以下の記事も参考にしてください。
参考文献
- P. Indyk and R. Motwani. “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.” STOC 1998.
- M. S. Charikar. “Similarity Estimation Techniques from Rounding Algorithms.”（SimHash）STOC 2002.
- M. Datar, N. Immorlica, P. Indyk, V. S. Mirrokni. “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions.” SoCG 2004.
- W. B. Johnson and J. Lindenstrauss. “Extensions of Lipschitz mappings into a Hilbert space.”（JL補題）1984.