让人惊叹的Johnson-Lindenstrauss引理:理论篇
?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引理:理论篇的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 国六玉柴YCY30170马力缸径是多少?
- 下一篇: 从三角不等式到Margin Softma