ハエの嗅覚回路に倣ったハッシュの優位と、埋め込みの幅
2017年の優位は512次元の埋め込みで縮むが、同じ埋め込みを100次元に落とすと戻る
Dasgupta らが2017年に報告した、ショウジョウバエの嗅覚回路に倣ったハッシュが局所性鋭敏ハッシュより近傍探索に優れるという結果を、当時と同じ種類の埋め込み（GloVe 100次元）と、対照学習で作られた埋め込み（COCO 512次元）で測り直した。同じビット数での平均適合率の比は、GloVe で3.1倍から19.7倍、COCO で1.4倍から2.9倍だった。COCO を100次元に落とすと、比は1.9倍から17.8倍に戻った。優位が縮んだのは埋め込みの時代によるのではなく、幅による。
| 方法 | ハエのハッシュと、正規乱数の射影の符号をとる局所性鋭敏ハッシュを自前で実装し、同じビット数で比べた。正解は厳密なコサイン類似度の上位100件、データベース50,000本、問い合わせ1,000本、種2つ。次に COCO の埋め込みを主成分分析と乱択射影の二通りで32から256次元に落とし、同じ比較を繰り返した。 |
|---|---|
| 結果 | GloVe 100次元での比は8ビットで19.7倍、128ビットで3.1倍。COCO 512次元では2.7倍と1.4倍。COCO を主成分分析で100次元にすると、16ビットでの比が2.2倍から11.2倍に上がり、GloVe の12.9倍に近づいた。 |
| 知見 | 2026年9月13日訂正。縮むのは座標の本数によるのではなく、データの内在次元による。人工データで座標の本数だけを16倍にしても優位は動かなかった。訂正の内容は「ハエの嗅覚回路に倣ったハッシュの優位と、データの内在次元」にある。以下は訂正前の記述。幅が広いほど、ハエのハッシュの優位は縮む。近年の埋め込みが512次元以上を普通に使うため、時代の差に見えていた。ノルムを揃えた対照は数字が桁まで一致した。三つの手続きがすべて正のスカラー倍に不変なので、原理的に何も測れない対照だった。 |
| 限界 | 曲線は単調でなく、二通りの縮約は中ほどで食い違う。乱択射影は狭めるほど精度そのものを壊す。データセットは二つだけで、2023年以降の文章の埋め込みモデルには直接当てていない。 |
訂正
2026年9月13日。本ノートの結論のうち、優位が縮む原因を埋め込みの幅としたところを訂正する。幅だけを動かせる人工データで測り直したところ、座標の本数を16倍に広げても優位はほとんど動かず、同じ設定で内在次元を32倍にすると4.6分の1になった。原因は座標の本数ではなく内在次元である。実在の埋め込みを縮めると両方が同時に落ちるため、本ノートの観測そのものは変わらない。訂正の詳細は「ハエの嗅覚回路に倣ったハッシュの優位と、データの内在次元」にある。
背景
Dasgupta、Stevens、Navlakha は2017年、ショウジョウバエの嗅覚回路を近傍探索のアルゴリズムとして読み、局所性鋭敏ハッシュより優れると報告した。ハエの回路は三つの点で普通と違う。投射が次元を減らすのではなく増やすこと、投射行列が密な正規乱数ではなく疎な二値であること、そして抑制によって強く反応した数パーセントの細胞だけを残すことである。ハエでは50個の投射ニューロンから約2,000個のケニオン細胞へ約40倍に広げ、各細胞はそのうち約6本を受け、上位5%だけが発火する。
この結果には系譜がある。Ryali らは2020年にこの回路を教師なしの学習に広げ、Liang らは2021年に単語の埋め込みを学習させた。Figueroa らは2025年、複素数の重みで語順を入れた。Li らは2024年、ベクトル集合の探索にこの回路を使っている。
ただし、2017年の評価に使われた埋め込みは SIFT、GloVe、MNIST である。いずれも対照学習で作られた埋め込みより前のものであり、幅は100前後だった。今の埋め込みは幅が512から数千あり、明示的な学習目標によって球面上に広がるよう作られている。ハエのハッシュの優位が、そうした埋め込みでも残るかは、調べた限り報告が見当たらなかった。Li らは all-MiniLM-L6-v2 までを使っている。本調査はその一点を測ったものである。
対象と方法
ハエのハッシュと局所性鋭敏ハッシュを自前で実装した。Liang らの公開実装は、学習済みモデルの書庫が壊れた状態で配布されており、Python 3.11 で読み込めないことを実機で確かめた。これは公開リポジトリで既に報告され、未解決のままである。
- ハエのハッシュ。各ベクトルからその平均を引き、入力の幅 d の20倍の細胞を用意する。各細胞は入力のうち10%を無作為に選んで足す。値の大きい順に決めた個数の細胞だけを1とし、残りを0とする。1の個数をビット数と数える。
- 局所性鋭敏ハッシュ。正規乱数の密な射影の符号をとる。Charikar が2002年に示した方式で、2017年の論文が比較対象にしたものと同じである。
正解は、同じデータベースに対する厳密なコサイン類似度の上位100件とした。評価は上位100件での平均適合率で、ハッシュの近さでデータベースを並べたときに正解がどれだけ上位に集まるかを測る。比較する二つのデータセットは次の通りである。
| データセット | 幅 | 出どころ |
|---|---|---|
| GloVe | 100 | ann-benchmarks の glove-100-angular |
| COCO-T2I | 512 | 対照学習で作られた画像と文の埋め込み。str-encoders の配布物 |
データベースは各50,000本、問い合わせは1,000本、種は2つ、ビット数は8、16、32、64、128である。
次に、幅だけを動かす実験をした。COCO の埋め込みを32、64、100、128、256次元に落とし、同じ比較を16ビットで繰り返した。縮約は二通り行った。主成分分析は分散の大きい方向を残し、乱択射影は正規乱数の行列を掛けるだけで方向を選ばない。両方を使ったのは、主成分分析が幅を減らすと同時に分散を集中させるため、幅の効果と分散の効果を分けるためである。GloVe も同じ方法で32と64次元に落とした。
ノルムのばらつきが原因かを見るために、GloVe の全ベクトルを単位長に揃えた条件も作った。
結果
時代の違う埋め込みでの比
ハエのハッシュの平均適合率を局所性鋭敏ハッシュのそれで割った比である。
| ビット | GloVe 100次元 | COCO 512次元 |
|---|---|---|
| 8 | 19.67 | 2.72 |
| 16 | 12.88 | 2.22 |
| 32 | 7.63 | 2.93 |
| 64 | 4.83 | 2.03 |
| 128 | 3.11 | 1.43 |
2017年の主張は、当時と同じ種類の埋め込みでは再現する。対照学習で作られた埋め込みでは、優位は残るが大きく縮む。
幅だけを動かしたときの比
16ビットでの比である。
| 幅 | COCO 主成分分析 | COCO 乱択射影 | GloVe |
|---|---|---|---|
| 32 | 5.53 | 6.22 | 5.27 |
| 64 | 6.70 | 5.80 | 9.64 |
| 100 | 11.18 | 6.51 | 12.88 |
| 128 | 3.72 | 3.69 | - |
| 256 | 3.54 | 5.65 | - |
| 512 | 2.22 | 2.22 | - |
COCO を100次元に落とすと、比は主成分分析で11.18倍、乱択射影で6.51倍になり、GloVe 100次元の12.88倍に近づく。ビット数を変えても同じで、主成分分析で100次元にした COCO は8ビットで17.77倍、128ビットで1.87倍だった。
ノルムを揃えた対照
GloVe を単位長に揃えた条件の数字は、元データと桁まで完全に一致した。五つのビット数すべてで、19.67、12.88、7.63、4.83、3.11である。
考察
優位が縮んだ原因は、埋め込みの時代ではなく幅にある。対照学習で作られた埋め込みも、100次元に落とせば2017年と同じ程度の優位を示す。近年の埋め込みが512次元以上を普通に使うため、時代の差に見えていた。
幅が効く理由は、ハエのハッシュの作りにある。各細胞は入力の10%を足し合わせる。幅が100なら10本、512なら51本である。足す本数が増えるほど各細胞の値は正規分布に近づき、疎な二値射影と密な正規乱数射影の違いが薄れる。上位だけを残す操作の利点も、幅が広いほど薄まる。この説明は本調査の数字と矛盾しないが、本調査が検証したものではない。
ノルムを揃えた対照については、数字が一致したことをまず記しておく。一致は当然だった。ハエのハッシュは中心化した線形写像の上位を残す操作で、局所性鋭敏ハッシュは線形写像の符号で、正解はコサイン類似度である。三つとも、ベクトルを正の定数倍しても変わらない。この対照は、原理的に何も測れない。数字が一致したことは実装が正しいことの確認にはなるが、ノルムが効いていないことの証拠にはならない。測れない対照を作ってしまった記録として残す。
限界
- 曲線は綺麗ではない。主成分分析と乱択射影は64次元と256次元で食い違い、どちらも単調でない。幅のほうがましな説明だ、というところまでで、法則を測ったわけではない。
- 乱択射影は狭めるほど近傍探索の精度そのものを壊す。その条件での比は、劣った手法どうしの比である。
- データセットは二つだけで、それぞれ一つの埋め込みモデルである。2023年以降の文章の埋め込みモデルには直接当てていない。
- 幅が効く仕組みの説明は仮説である。幅以外を固定できる人工データで測り直していない。
参考文献
- S. Dasgupta, C. F. Stevens, and S. Navlakha (2017). A neural algorithm for a fundamental computing problem. Science 358(6364), 793-796.
- M. S. Charikar (2002). Similarity estimation techniques from rounding algorithms. Proceedings of the 34th ACM Symposium on Theory of Computing, 380-388.
- C. K. Ryali, J. J. Hopfield, L. Grinberg, and D. Krotov (2020). Bio-Inspired Hashing for Unsupervised Similarity Search. ICML 2020, 8739-8750. arXiv:2001.04907
- Y. Liang, C. K. Ryali, B. Hoover, L. Grinberg, S. Navlakha, M. J. Zaki, and D. Krotov (2021). Can a Fruit Fly Learn Word Embeddings? ICLR 2021. arXiv:2101.06887
- A. Figueroa, J. Westerhoff, G. Atefi, D. Fast, B. Winter, F. A. Gers, A. Löser, and W. Nejdl (2025). Comply: Learning Sentences with Complex Weights inspired by Fruit Fly Olfaction. NICE 2025. arXiv:2502.01706
- Y. Li, S. Wang, Z. Chen, S. Chen, and Z. Peng (2024). Approximate Vector Set Search Inspired by Fly Olfactory Neural System. arXiv:2412.03301
- J. Pennington, R. Socher, and C. D. Manning (2014). GloVe: Global Vectors for Word Representation. EMNLP 2014, 1532-1543.
- M. Aumüller, E. Bernhardsson, and A. Faithfull (2020). ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87, 101374.
- F. Carrara. str-encoders, release v0.1.3, coco-t2i-512-angular. GitHub.
Dasgupta ら2017、Charikar 2002、Pennington ら2014、Aumüller ら2020の4件は、著者名・掲載誌・巻号・頁を Crossref の登録記録と照合した。arXiv の4件と配布物1件は照合していない。