第3章 LSHと超並列SIMD演算による高速化数理（実装極限）¶

本章では、数千規模の音声ファイル群に対する総当りの等価性判定において立ちはだかる、\(O(M^2)\) の計算量爆発を打破するためのアルゴリズム論、およびハードウェアの演算器を極限まで駆動するためのプログラマティックな最適化手法を解説する。 LSHによる次元削減の数理、浮動小数点演算を \(O(1)\) の「整数ビット演算」へと射影するSimHash定理、そしてSIMDループアンロールがレイテンシの物理的限界をいかに突破するかを証明する。

Note

本章における主要な略称・用語

LSH: 局所性鋭敏型ハッシュ (Locality-Sensitive Hashing)
SIMD: Single Instruction, Multiple Data
POPCNT: Population Count (立っているビット数を数える命令)
XOR: 排他的論理和

3.1 次元削減と近傍探索の数理的定式化¶

対象となるすべての音声ファイルの集合を \(\mathcal{S} = \{ \mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_M \}\) とする（\(M\) は数千規模）。各 \(\mathbf{x}_i \in \mathbb{R}^N\) は高次元の特徴量ベクトルである。

定義 3.1 (LSHファミリ)¶

距離空間 \((\mathcal{S}, d)\) において、ハッシュ関数の族 \(\mathcal{H} = \{ h : \mathcal{S} \to U \}\) が Locality Sensitive であるとは、任意の \(\mathbf{x}, \mathbf{y} \in \mathcal{S}\) に対して、距離 \(d(\mathbf{x}, \mathbf{y})\) が小さい（類似している）ほど、ハッシュ値が衝突する確率 \(\Pr[h(\mathbf{x}) = h(\mathbf{y})]\) が高くなる性質を持つことと定義する。

3.2 課題：ペアワイズ比較における \(O(M^2)\) の次元の呪い¶

\(M\) 個の音声ファイル群から重複ペアを見つけるためには、素朴な実装（全探索）ではすべての組み合わせについて第4章のピアソン相関係数を計算しなければならない。必要な比較回数 \(C\) は以下の組み合わせ論的計算式となる。

\[\begin{aligned}C &= \binom{M}{2} \\&= \frac{M(M - 1)}{2} \\&= O(M^2) \quad \cdots (3.1)\end{aligned}\]

\(M = 30,000\) 個の場合、比較回数は約4.5億回に達する。仮に1回の比較（浮動小数点演算と SIMD 処理）が \(10\ \mu\text{s}\) だったとしても、全体で約4,500秒（1時間以上）を要し、リアルタイムパイプラインとしては完全に破綻する。この \(O(M^2 \cdot N)\) の壁を突破するには、「比較対象を絞り込むこと」と「比較演算そのものを軽量化すること」の2つのアプローチが不可避である。

3.3 定理の提示：SimHashによるコサイン類似度のビット射影 (Proof)¶

浮動小数点ベクトル同士の内積（コサイン類似度）計算を、圧倒的に軽量な「整数ビット演算」に射影する数学的ハックを導入する。

Important

定理 3.1 (CharikarのSimHash定理とランダム超平面) \(\mathbb{R}^N\) 空間において、平均が \(0\) になるように正規化された2つのベクトル \(\mathbf{x}, \mathbf{y}\) を考える。この空間を原点を通るランダムな超平面で二分し、ベクトルがどちらの側にあるかで \(0\) または \(1\) のビットを割り当てる関数 \(h(\mathbf{v}) = \text{sgn}(\mathbf{v})\) を定義する。このとき、2つのベクトルのなす角 \(\theta\) は、それらの符号ビットが異なる確率に完全に線形比例する。

\[\Pr[h(\mathbf{x}) \neq h(\mathbf{y})] = \frac{\theta}{\pi} \quad \cdots (3.2)\]

Note

証明の概要と導出

2つのベクトル \(\mathbf{x}, \mathbf{y}\) によって張られる2次元平面を考える。原点を通るランダムな超平面は、この2次元平面上ではランダムな直線として現れる。この直線が \(\mathbf{x}\) と \(\mathbf{y}\) の間を通過する場合にのみ、両者の符号ビット \(h(\mathbf{x})\) と \(h(\mathbf{y})\) は異なる値をとるとる。全角度は \(2\pi\) であり、直線がベクトル間を通過する角度の範囲は両側合わせて \(2\theta\) である。したがって、その確率は \(\frac{2\theta}{2\pi} = \frac{\theta}{\pi}\) となる。コサイン類似度は \(\cos(\theta)\) であるため、符号ビットの不一致確率（ハミング距離）を測定するだけで、元の浮動小数点空間におけるコサイン類似度を数学的に推定できることが示された。\(\blacksquare\)

3.4 実装への射影：ビットパッキングと POPCNT ハック¶

定理 3.1 の強烈な恩恵は、浮動小数点数の重い配列演算を、1つの巨大な整数へのビット詰め込み、**「XOR演算」へ変換できる点にある。これはメモリやCPUサイクルを極限まで切り詰めたファミコン時代のハックに酷似している。

空間の圧縮（ビットパッキング）¶

64次元の特徴量ベクトルの符号（正なら 1、負なら 0）を、C#における単一の64ビット整数の各ビット位置にシフト演算と論理和を用いてパッキングする（シグネチャ化）。これにより、ベクトルデータは数キロバイトの配列から、わずか 8 バイトの ulong 値1つへと圧縮される。

XOR と POPCNT による \(O(1)\) 距離計算¶

2つのシグネチャ A と B の非類似度（ハミング距離）は、XOR を取ることで「ビットが異なる箇所のみ 1 が立つ整数」を作り出し、その 1 の数を数えることで得られる。

// 【疑似コード】ビットパッキングとPOPCNTによる超高速類似度判定
public bool IsSimilar_SimHash(ulong signatureA, ulong signatureB) {
    // 1. XOR演算で、符号が異なるビット位置のみを 1 にする
    ulong diff = signatureA ^ signatureB;

    // 2. ハードウェア命令 (POPCNT) を直接駆動し、立っているビット数を1クロックで数える
    // この関数はコンパイル時に x86_64 の popcnt 命令などに展開される
    int hammingDistance = System.Numerics.BitOperations.PopCount(diff);

    // 64ビット中、ビットの違いが一定の閾値(例: 4ビット以下)なら類似と判定
    return hammingDistance <= 4;
}

この実装により、64個の浮動小数点数の差の二乗和に本来なら数多のクロックとメモリアクセスが必要だが、CPUの XOR 命令と POPCNT 命令のわずか2クロック（実質的な時間計算量 \(O(1)\)）へと短縮される。このハックにより、事前フィルタリングの速度は数十倍に跳ね上がり、\(O(M^2)\) の呪縛は実用上完全に無力化される。

3.5 バケツ分割と同値類構築への接続¶

上記で得られた64ビットのシグネチャ ulong は、そのままLSHのハッシュ値としても機能する。

バケティング: シグネチャが完全に一致する（ハミング距離 0）ファイル群は同じバケツに \(O(1)\) で分割され、後続の厳密な波形比較（第4章・第5章）へと送られる。
近傍探索: ハミング距離が 1、2 程度の微小な差を持つバケツ同士も、上記の PopCount ハックによって極めて高速に隣接判定され、類似ペアとして抽出される。

3.6 実装極限におけるパイプライン最適化 (Loop Unrolling)¶

最後に残ったバケツ内の厳密な波形比較においても、ハードウェアの物理的極限を引き出す最適化が行われる。

SIMDレジスタを用いたアキュムレータ処理において、単一の変数に結果を累積し続けると、CPUのパイプラインにおいて「前の演算が終わるまで次の演算が待機する」データ依存性ストールが発生する。本システムでは、[GenerateSimdBatchUnroll] というカスタム属性を用いてコンパイル時にループをアンロールし、独立した 4 個のアキュムレータへ交互に命令を発行する。これにより、最新CPUの「アウト・オブ・オーダー実行」が誘発され、レイテンシの壁を越えた理論上の最大スループットが達成される。

3.7 参考文献 (References)¶

Charikar, M. S. (2002). "Similarity estimation techniques from rounding algorithms". Proceedings of the 34th annual ACM symposium on Theory of computing (STOC '02).
Indyk, P., & Motwani, R. (1998). "Approximate nearest neighbors: towards removing the curse of dimensionality". Proceedings of the 30th annual ACM symposium on Theory of computing (STOC '98).