ハエの嗅覚回路に倣ったハッシュの優位と、データの内在次元
座標の本数を16倍にしても優位は動かず、同じデータの内在次元を32倍にすると4.6分の1になった
同日に公開した調査ノートで、このハッシュの優位が縮むのは埋め込みの幅によると述べた。幅だけを動かせる人工データで測り直したところ、座標の本数を64から1024まで16倍に広げても優位は8.2倍から7.7倍にしか動かず、同じ設定で内在次元を16から512まで32倍にすると13.2倍から2.9倍に下がった。優位を決めているのは座標の本数ではなく、データが実際に広がっている次元である。前のノートの結論のうち「幅による」の部分を訂正する。
| 方法 | 潜在ベクトルを k 次元の標準正規分布から引き、直交行列で D 次元へ移す。直交変換は内積を保つので、D をいくつにしても正解の近傍集合は同一である。この上で四つの走査を行った。k と D を揃えて動かす走査、k を64に固定して D だけ動かす走査、D を512に固定して k だけ動かす走査、そして四つ目は二つ目と同じ条件で、ハエ側の細胞数と一細胞あたりの受け取り本数を実際の動物の値に固定した走査である。データ5万件、質問1,000件、16ビット、上位100件、乱数の種3つ。 |
|---|---|
| 結果 | 座標の本数だけを16倍にすると優位は8.24倍から7.65倍。内在次元だけを32倍にすると13.20倍から2.89倍。細胞数と受け取り本数を動物の値に固定すると、座標を16倍にしても優位は8.26倍から9.91倍へ上がる。 |
| 知見 | 優位を決めるのは内在次元である。座標の本数は、細胞数と受け取り本数が入力の幅に比例して増えるという実装上の規則を通してしか効かない。その規則を実際の動物の値に固定すると、座標の本数の効果は消える。 |
| 限界 | 人工データは等方な正規分布であり、実際の埋め込みが持つ異方性や台の形は入れていない。内在次元は潜在の次元数として与えており、実データの内在次元は測っていないので、GloVe と COCO のどちらがどれだけ複雑かは本調査からは言えない。ビット数は16のみ、近傍は上位100件のみを試した。 |
背景
Dasgupta、Stevens、Navlakha は2017年、ショウジョウバエの嗅覚回路を近傍探索の算法として読み解いた。50本の投射ニューロンが2,000個のケニオン細胞へ広がり、各ケニオン細胞は投射のうち約6本を受け取り、抑制によって上位5%だけが残る。次元を落とさずに広げること、射影行列が疎で二値であること、勝者総取りで疎な符号を作ることの三点が、古典的な局所性鋭敏ハッシュと違う。論文は同じ符号長でこの手続きが局所性鋭敏ハッシュより優れると報告した。
同日に公開した調査ノートで、この優位を当時と同じ種類の埋め込みと対照学習で作られた埋め込みで測り直した。512次元の埋め込みでは優位が縮み、同じ埋め込みを100次元に落とすと戻った。そこから「縮むのは埋め込みの時代によるのではなく幅による」と述べた。
この結論には穴がある。実在の埋め込みを縮めると、座標の本数のほかに変わるものがある。主成分分析による縮約は分散を上位の方向へ集める。乱択射影は縮めるほど精度そのものを壊す。幅が単独で動いた場面が一度も無かった。
対象と方法
人工データにすると、この交絡を完全に外せる。潜在ベクトル z を k 次元の標準正規分布から引き、列が正規直交な行列 U で D 次元へ移して x = Uz とする。直交変換は内積を保つので、任意の2点のコサイン類似度は潜在のものとまったく等しい。つまり D をいくつにしても、正解の近傍集合は同一である。データの幾何は変わらず、それを書き表す座標の本数だけが変わる。
この作り方には検算が組み込まれている。局所性鋭敏ハッシュは密なガウス行列で射影するので回転に不変であり、D だけが変わるときにその精度は動いてはならない。動いたなら測定装置のほうが壊れており、他のどの数字にも意味が無い。一方でハエ側の手続きは座標軸に沿って標本を取るので回転に不変ではなく、動いてよい。
四つの走査を行った。
| 走査 | 動かすもの |
|---|---|
| 1 | k と D を揃えて動かす |
| 2 | k を64に固定し、D だけ動かす |
| 3 | D を512に固定し、k だけ動かす |
| 4 | 2と同じ。ただし細胞数を2,000、一細胞あたりの受け取り本数を6に固定する |
四つ目の走査には理由がある。公開されている算法では、ケニオン細胞の数が入力の幅の20倍、一細胞が受け取る本数が入力の幅の0.1倍と定められている。どちらも入力の幅に比例する。したがって幅を走査すると、データだけでなく算法の大きさまで同時に走査してしまう。実際の動物では細胞数も受け取り本数も固定の値なので、そちらに合わせた条件を別に置いた。
データベース5万件、質問1,000件、符号長16ビット、正解はコサイン類似度の上位100件、乱数の種は3つ。評価は平均適合率。
結果
検算は通った。走査2で局所性鋭敏ハッシュの平均適合率が振れた幅は、平均の8.6%である。回転不変性から期待される通り、動いていない。
座標の本数だけを動かした走査2では、優位はほとんど動かない。
| 座標の本数 | 内在次元 | ハエ／局所性鋭敏 |
|---|---|---|
| 64 | 64 | 8.24倍 |
| 128 | 64 | 10.06倍 |
| 256 | 64 | 9.59倍 |
| 512 | 64 | 9.76倍 |
| 1024 | 64 | 7.65倍 |
16倍に広げて8.24倍から7.65倍であり、単調でもない。これに対し、座標の本数を512に固定して内在次元だけを動かした走査3では、優位は単調に下がる。
| 座標の本数 | 内在次元 | ハエ／局所性鋭敏 |
|---|---|---|
| 512 | 16 | 13.20倍 |
| 512 | 32 | 13.14倍 |
| 512 | 64 | 9.76倍 |
| 512 | 128 | 5.88倍 |
| 512 | 256 | 3.45倍 |
| 512 | 512 | 2.89倍 |
内在次元を32倍にすると優位は4.6分の1になる。走査1で両方を一緒に動かしたときに見えた低下は、この走査3とほぼ同じ形をしている。
走査4では、細胞数と受け取り本数を動物の値に固定したまま座標の本数を16倍にした。
| 座標の本数 | 内在次元 | ハエ／局所性鋭敏 |
|---|---|---|
| 64 | 64 | 8.26倍 |
| 128 | 64 | 9.08倍 |
| 256 | 64 | 9.87倍 |
| 512 | 64 | 10.59倍 |
| 1024 | 64 | 9.91倍 |
下がらない。むしろ上がる。座標の本数が効くように見えた分は、細胞数と受け取り本数が幅に比例して増えるという実装上の規則から来ている。
考察
前のノートの「幅による」は、二つの別のものを一語にまとめていた。座標の本数と、データが実際に広がっている次元である。実在の埋め込みでは両者を分けられない。主成分分析で512次元を100次元に落とせば、座標の本数も内在次元も同時に落ちる。乱択射影でも同じことが起きる。だから前のノートの観測は、内在次元の説明とも矛盾しない。
方向としての結論、すなわち「縮むのは埋め込みが作られた時代によるのではなく次元による」は変わらない。変わるのはどの次元かである。近年の埋め込みが512次元や1024次元を普通に使うという事実は、それ自体では優位を縮めない。縮めているのは、それらの埋め込みが表している内容が、2014年の単語ベクトルより複雑であることのほうである。
なぜ内在次元が効くのかは本調査では決めていない。上位5%だけを残す勝者総取りは、広がった空間の中でどの細胞が勝つかという順序に依存する。内在次元が上がると近傍のコサイン類似度の分布が詰まり、順序が壊れやすくなる。局所性鋭敏ハッシュの符号も同じ理由で悪くなるが、実測では16ビットのハエ側の落ち方のほうが緩い。この非対称の由来は測っていない。
限界
人工データは等方な正規分布である。実在の埋め込みは等方ではなく、台の形も違う。異方性を入れたときに同じことが起きるかは測っていない。
内在次元は潜在の次元数として与えたものであり、実データについて推定していない。したがって GloVe と COCO のどちらがどれだけ複雑なのかは、本調査からは言えない。前のノートの観測が内在次元で説明できるという主張は、この点で間接的なままである。
符号長は16ビットのみ、正解は上位100件のみを試した。ビット数を変えたときに四つの走査の形が保たれるかは分からない。
訂正について
本調査は、同日に公開した「ハエの嗅覚回路に倣ったハッシュの優位と、埋め込みの幅」の結論の一部を、著者自身の追加計算によって訂正するものである。前のノートは取り下げず、訂正の事実を当該ノートに残した。
参考文献
- 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.
- 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.
4件とも、著者名・掲載誌・巻号・頁を Crossref の登録記録と照合した。