?PaperWeekly 原創 ·?作者 |?蘇劍林

單位?|?追一科技

研究方向?|?NLP、神經網絡

今天我們來學習 Johnson-Lindenstrauss 引理，由于名字比較長，下面都簡稱“JL 引理”。

個人認為，JL 引理是每一個計算機科學的同學都必須了解的神奇結論之一，它是一個關于降維的著名的結果，它也是高維空間中眾多反直覺的“維度災難”現象的經典例子之一。可以說，JL 引理是機器學習中各種降維、Hash 等技術的理論基礎，此外，在現代機器學習中，JL 引理也為我們理解、調試模型維度等相關參數提供了重要的理論支撐。

對數的維度

JL 引理，可以非常通俗地表達為：

通俗版 JL 引理：塞下 個向量，只需要 維空間。

具體來說，JL 引理說的是，不管這 個向量原來是多少維的，我們都可以將它們降到 ，并將相對距離的誤差控制在一定范圍內。可以想象，這是一個非常強、非常反直覺、非常實用的結論，比如我們要做向量檢索，原本的向量維度可能非常大，這樣全量檢索一次的成本也非常大，而 JL 引理告訴我們，可以將它們變換到 維，并且檢索效果近似不變，這簡直就是“天上掉餡餅”的好事！

可能讀者會有疑問：這么強的結論，那么對應的降維方法會不會特別復雜？答案是剛剛相反，降維過程僅僅用到隨機線性投影！甚至有評價說，JL 引理是一個“證明比理解更容易的結論”，也就是說，從數學上證明它還真不算特別困難，但如何直觀地理解這個反直覺的結論，反而是不那么容易的。

無獨有偶，我們之前其實就介紹過兩個反直覺的結果：在文章《n 維空間下兩個隨機向量的夾角分布》[1] 中，我們就介紹過“高維空間中任意兩個向量幾乎都是垂直的”，這顯然與二維、三維空間的結果差距甚遠；在文章《從幾何視角來理解模型參數的初始化策略》[2] 中，這個結果進一步升級為“從 采樣出來的 矩陣幾乎是一個正交矩陣”，這更與我們一直理解的“正交性是非常苛刻的（要求轉置等于逆）”有嚴重出入。

但事實上，這兩個結論不僅對，而且還跟 JL 引理直接相關。可以說，JL 引理可以看成是它們的細化和應用。所以，我們需要先用更定量的語言來刻畫這兩個結論，比如“幾乎垂直”，那垂直的概率究竟有多少，比如“近似正交”，那誤差究竟有多大。

概率不等式

為此，我們需要一些概率知識，其中最主要是“馬爾可夫不等式”：

馬爾可夫不等式：如果 是非負隨機變量，，那么

注意該不等式并沒有對 所服從的分布有其他特別的限制，只要求隨機變量的取值空間是非負的（或者等價地，負的 的概率恒為 0），證明其實非常簡單：

馬爾可夫不等式要求隨機變量是非負的，但我們平時要處理的隨機變量不一定是非負的，所以通常需要變換一下才能用。比如 不是非負的，但 是非負的，于是利用馬爾可夫不等式有：

這就是“切比雪夫不等式”。

另外一個經典技巧稱為“Cramér-Chernoff方法”，也是我們后面主要利用到的方法，它通過指數函數將隨機變量變成非負的：對于任意 ，我們有

所以利用馬爾可夫不等式有

最左端是跟 無關的，但是最右端有一個 ，而這不等式是對于任意 都成立的。所以理論上，我們可以找到使得最右端最小的 ，以獲得最高的估計精度：

引理的引理

現在，我們可以引入如下結果，它是 JL 引理的引理，甚至可以說，它是本文一切結論的理論基礎：

單位模引理：設 是獨立重復采樣自 的向量， 是給定常數，那么我們有：

該引理告訴我們，當 足夠大的時候， 的模長明顯偏離 1 的概率是非常小的（給定 后，將以 的指數形式遞減至 0），所以從 采樣出來的 維向量將會非常接近單位向量。

它的證明正是用到“Cramér-Chernoff方法”：首先 意味著 或 ，我們需要分別進行推導，不失一般性，先推導 的概率，根據 Cramér-Chernoff 方法，有：

將 u 寫成分量形式 ，其中每個分量都是獨立的，分布均為?，那么我們有：

而 ，所以：

右端的極小值在 取到，推導過程就留給讀者了，然后代入得到：

其中 的證明也留給讀者了。類似地，我們可以對 的概率進行推導，結果為：

其中可證 ，所以上式沿用了 的不等關系。現在兩式相加，我們得到 。證畢。

從“單位模引理”出發，我們可以證明“正交性引理”：

正交性引理：設 是獨立重復采樣自 的兩個向量，是給定常數，那么我們有：

該引理告訴我們，當 足夠大的時候， 的內積明顯偏離 0 的概率是非常小的（給定 后，將以 的指數形式遞減至 0），所以從 采樣出來的兩個 維向量將會非常接近正交。而結合“單位模引理”，我們就得到“從 采樣出來的 矩陣幾乎是一個正交矩陣”的結論了。

有了“單位模引理”鋪墊，它的證明不算難。我們知道如果 ，那么 ，所以根據“單位模引理”的證明，我們有：

注意 和 兩式相加后可以得出 ，所以：

同理可證 ，兩者結合就得到“正交性引理”。

證明的過程

現在我們就可以著手證明 JL 引理了，下面是它的數學表述：

數學版 JL 引理：給定 個向量 和 ，而隨機矩陣 獨立重復采樣自 ， 是給定常數，那么至少有 的概率，使得對于所有的 ，都成立：

引理告訴我們，不管原來的向量維數 是多少，只需要 的維度，我們就可以容納下 個向量，使得它們相對距離的偏離都不超過 。而且 JL 引理還告訴我們降維方法：只需要從 隨機采樣一個 的矩陣 ，然后變換 就有 的可能性達到目的。真可謂是簡單實用了。

證明過程也是“單位模引理”的直接應用。首先，如果 是給定的單位向量，而 獨立重復采樣自 ，那么 的每個分量都獨立地服從 。證明也并不難，根據定義每個分量 ，由于 相互獨立，所以 顯然相互獨立，并且由于 ，正態隨機變量和的分布依然是正態分布，所以 服從正態分布，其均值為 ，其方差則為 。

所以，說白了， 相當于從 獨立重復采樣出來的 維向量。現在代入 ，利用“單位模引理”，得到：

此結果對于任意 都成立，那么遍歷所有的 的組合，我們得到至少有一項 的概率不超過：

或者反過來說，對于任意 ，都成立 （等價于（16））的概率不小于：

代入 ，可以得到：

至此，證明已經完成。

上面的 JL 引理中保持的是歐氏距離近似不變，很多時候我們檢索用的是內積（比如余弦相似度）而不是歐氏距離。對此，我們有：

內積版 JL 引理：給定 個單位向量 和 ，而隨機矩陣 獨立重復采樣自 ， 是給定常數，那么至少有 的概率，使得對于所有的 ，都成立：

證明很簡單，模仿“正交性引理”的證明即可。根據 JL 引理的證明，我們可以得到在相同的條件下，至少有 的概率同時滿足對于任意 有：

將第一乘上 -1 得到：

然后加到第二式得到：

注意到 是單位向量，所以上式等價于 。

極度的充分

動手去推過一次 JL 引理證明的同學應該能感覺到，JL 引理的結論中之所以能夠出現 ，本質上是因為“單位模引理”中的概率項 是指數衰減的，而我們可以放寬這個衰減速度，讓其變成多項式衰減，從而出現了 。

總的來說，JL 引理告訴我們，以誤差 塞下 個向量，只需要 維的空間，至于 前面的常數是多少，其實不大重要。因為事實上 JL 引理是一個非常充分的條件，實際情況中條件往往更加寬松。比如，在 JL 引理的證明中如果我們將條件改為 ，那么式（16）成立的概率就不小于：

注意 雖然小，但終究是大于 0 的，所以此時依然是存在 使得（16）成立，只不過尋找 的成本更大罷了（每次命中的概率只有 ），而如果我們只關心存在性，那么這也夠了。

而且，JL 引理只考慮了在隨機線性投影下的降維，就已經得到 了，如果是其他更精細的降維，比如基于 SVD 的降維，是有可能得到更好的結果的（前面的系數更小）；如果非線性的降維方法也考慮進去，那么結果又能變得更優了。所以說，不需要太關心 前面的常數是多少，我們只需要知道 的量級，如果真要用到它，通常還需要根據實際情況確定前面的常數，而不是調用理論結果。

且待下回續

在這篇文章中，我們介紹了 Johnson–Lindenstrauss 引理（JL 引理），它是關于降維的一個重要而奇妙的結論，是高維空間的不同尋常之處的重要體現之一。它告訴我們“只需要 維空間就可以塞下 個向量”，使得原本高維空間中的檢索問題可以降低到 維空間中。

本文主要討論了 JL 引理的相關理論證明細節，下一篇文章我們則嘗試應用它來理解一些機器學習問題，敬請期待。

參考文獻

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

[2] https://kexue.fm/archives/7180

特別鳴謝

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

更多閱讀

#投 稿?通 道#

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

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

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

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

📝?稿件基本要求：

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

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

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

📬?投稿通道：

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

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

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

△長按添加PaperWeekly小編

🔍

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

進入知乎首頁搜索「PaperWeekly」

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

·

總結

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

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