?PaperWeekly 原創(chuàng) ·?作者 | 蘇劍林

單位 | 追一科技

研究方向 | NLP、神經網絡

上一篇文章中，我們比較詳細地介紹了 Johnson-Lindenstrauss 引理（JL 引理）的理論推導，這一篇我們來關注它的應用。

作為一個內容上本身就跟降維相關的結論，JL 引理最基本的自然就是作為一個降維方法來用。但除了這個直接應用外，很多看似不相關的算法，比如局部敏感哈希（LSH）、隨機 SVD 等，本質上也依賴于 JL 引理。此外，對于機器學習模型來說，JL 引理通常還能為我們的維度選擇提供一些理論解釋。

降維的工具

JL 引理提供了一個非常簡單直接的“隨機投影”降維思路：

給定 個向量 ，如果想要將它降到 維，那么只需要從 中采樣一個 矩陣 ，然后 就是降維后的結果。

這個思路簡單快速是毋庸置疑的，讀者隨之而來的疑問就是：它跟 PCA、t-SNE 等降維方法相比效果如何？

其實，正如“存在就是合理的”，更復雜的 PCA、t-SNE 等方法既然還沒有被淘汰，那就說明它肯定有比隨機投影更好的地方。事實上，JL 引理的隨機投影只是提供了一種非常基本的降維方法，顯示出哪怕在這么簡單的方法之后，降維后的維度也只需要 ，它更多的是一個理論證明。

所以，真要追求降維精度的話，多數情況下 PCA、t-SNE 等這些專門的降維方法，效果肯定是要比隨機投影要好的。而且上一篇文章中我們也提過，JL 引理是一個非常充分的條件，它得到的 甚至 都只是非常充分的界，比如取 的話，就有 了，基本沒有實用價值。而換用 PCA、t-SNE 等更精準的降維方法，可以放寬這個要求，即在更小的維度下達到更好的效果。

局部的哈希

局部敏感哈希（Locality-Sensitive Hashing，LSH），是近似查找某種度量下的最鄰近元素的一種方案。通常來說，我們很少將 LSH 與 JL 引理聯(lián)系起來，但筆者認為，LSH 的哈希函數選擇上，其實跟 JL 引理也是緊密相關的。簡單來說，LSH 就是一個將向量二值化的算法，并且二值化之后的向量能近似保持度量不變。常見的一種方案是通過隨機投影來（近似）保持 cos 值的不變性。

具體來說，根據 JL 引理，我們從 中采樣一個 矩陣 ，那么對于任意 ，都有 。當然，隨機投影還不是 LSH 的全部，我們留意到，經過 的投影后， 的正負分布情況是比較均勻的，所以我們進一步做近似

即每個元素我們根據正負號二值化為 ，這就實現了向量的二值化，并且保持了余弦值近似不變。有了二值化向量后，我們可以建索引、分通等，以加快檢索速度，這些就不細說了。

總之，在 LSH 過程中，關鍵的一步也是隨機投影，這一步本身與 JL 引理也是緊密相關的。當然，二值化通常會比較明顯地犧牲精度，所以根據實際場景的不同，我們并不總是“降維”，即 n 并不會總是小于 m，有時候我們可能還會選擇 。相關的討論讀者可以參考筆者之前寫的《一個二值化詞向量模型，是怎么跟果蠅搭上關系的？》[1] 。

隨機的分解

矩陣分解是解決許多機器學習問題的強大工具，而奇異值分解（SVD）則是其中的典型方法之一。然而，當矩陣比較大的時候，計算精確的 SVD 分解成本相當大，而實際場景中，待分解矩陣雖然大，但往往也是低秩的，計算精確的 SVD 分解也沒有必要。這時候，“隨機 SVD 分解”便派上用場了。

設待分解矩陣為 ， 都比較大。根據 JL 引理，我們可以選擇比較小的 ，使得從 中采樣出來 矩陣 依然能比較高精度地滿足 （近似正交矩陣），從而 。這樣，我們可以只對 矩陣 做 SVD 分解，得到 ，那么

就得到了原始矩陣 的一個近似 SVD 分解。注意，上述 還只是近似正交矩陣，我們可以通過 QR 分解（或施密特正交化）使得它變成嚴格正交，這是一個小細節(jié)。在整個過程中，JL 引理所告訴我們的是 k 可以選得比較小，以至于對 做 SVD 是比較低成本的，但總體精度也不會太差。

詞向量維度

我們說 JL 引理的通俗理解是“塞下 個向量只需要 維空間”，那么回到詞向量維度選擇問題上，也就是說如果詞表大小為 ，那么詞向量維度是 就夠了。

非常讓人驚震的是，在筆者之前的文章《最小熵原理（六）：詞向量的維度應該怎么選擇？》

其結果與 JL 引理所給出的 如出一轍！上述公式是基于熵的思想進行估計的，與 JL 引理的出發(fā)點幾乎沒有交集之處，但竟然殊途同歸地得到了 。

而且，不僅僅是主體 ，我們還看到，基于熵的估計，我們還把 前面的系數 8.33 也計算出來了，并且以往的實驗經驗還顯示， 這個結果還是挺符合經驗的，雖然未必是最優(yōu)，但至少范圍上差不遠。這是不是可以反過來說，我們可以通過熵來比較精確地估計具體問題下 前面的系數？

多頭注意力

關于 Attention 機制，常見的面試題就是“為什么要多頭？”、“head_size 為 768 的單頭注意力，跟 head_size 為 64 的 12 頭注意力有什么區(qū)別？”等，也就是說，像 BERT 這樣的 Attention模型，為什么要先把 head_size 降低到 64 再做內積？64 真的夠了嗎？

這個問題本質上來說 Attention 機制是否足以擬合任何概率模式的問題。具體來說，Attention 的計算公式為：

其中 ，所謂“夠不夠”，就是指對于任意給定的概率矩陣 ，上述定義的 是否都能很好地逼近它？

看到 的定義，不知道有沒有讀者覺得熟悉的？如果我們拋開 Attention 的背景，將 分別視為兩個“詞向量”，那么 的定義跟 Skip Gram 模型一模一樣！也就是說，單純看 Attention 矩陣的計算公式，它跟 Skip Gram 模型本質上是一樣的，所以 Attention 的 head_size 選擇，本質上也就是詞向量的維度選擇。

讓我們再來捋一捋過程。我們要回答的是“head_size多少才夠”的問題，這變成了“ 能否逼近任意概率矩陣 ”的問題，也就是說，對于給定 ，我們是否能找到一組 ，使得 與 足夠近似，這個問題跟 Skip Gram 詞向量模型的維度選擇是數學等價的。

因此，詞向量維度選擇的結果，也就可以用于 Attention 的 head_size 選擇，只不過詞表大小變成了序列長度，即 ，常見的預訓練長度是 ，代入計算約等于 52，同樣非常讓人震驚，跟常見的 head_size=64 確實相差無幾！所以，64 真的夠了，再大也不會有明顯提升，倒不如將多出來的計算量用來增加 head 的數目～

（注：相關討論還可以參考文獻《On the Expressive Power of Self-Attention Matrices》[2]。）

又到了小結

本文主要介紹了 Johnson-Lindenstrauss 引理（JL 引理）的幾個直接或間接的應用，可以看到，從降維、哈希的方法，到詞向量維度、Attention 的頭大小等，多多少少都與 JL 引理有所關聯(lián)，這進一步顯示了 JL 引理的適用范圍之廣。

參考文獻

[1] https://kexue.fm/archives/8159

[2] https://arxiv.org/abs/2106.03764

特別鳴謝

感謝 TCCI 天橋腦科學研究院對于 PaperWeekly 的支持。TCCI 關注大腦探知、大腦功能和大腦健康。

更多閱讀

#投 稿?通 道#

?讓你的文字被更多人看到?

如何才能讓更多的優(yōu)質內容以更短路徑到達讀者群體，縮短讀者尋找優(yōu)質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發(fā)出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優(yōu)質內容，可以是最新論文解讀，也可以是學術熱點剖析、科研心得或競賽經驗講解等。我們的目的只有一個，讓知識真正流動起來。

📝?稿件基本要求：

? 文章確系個人原創(chuàng)作品，未曾在公開渠道發(fā)表，如為其他平臺已發(fā)表或待發(fā)表的文章，請明確標注?

? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發(fā)送，要求圖片清晰，無版權問題

? PaperWeekly 尊重原作者署名權，并將為每篇被采納的原創(chuàng)首發(fā)稿件，提供業(yè)內具有競爭力稿酬，具體依據文章閱讀量和文章質量階梯制結算

📬?投稿通道：

? 投稿郵箱：hr@paperweekly.site?

? 來稿請備注即時聯(lián)系方式（微信），以便我們在稿件選用的第一時間聯(lián)系作者

? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿

△長按添加PaperWeekly小編

🔍

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

·

總結

以上是生活随笔為你收集整理的​让人惊叹的Johnson-Lindenstrauss引理：应用篇的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。