約翰遜-林登斯特勞斯定理
約翰遜-林登斯特勞斯定理(Johnson–Lindenstrauss theorem),又稱約翰遜-林登斯特勞斯引理(Johnson–Lindenstrauss lemma),是由William Johnson和Joram Lindenstrauss於1984年提出的一個關於降維的著名定理[1],在現代機器學習,尤其是壓縮感知、降維、形狀分析和分佈學習等領域中有很重要的應用[2][3][4][5]。
這個定理告訴我們,一個高維空間中的點集,可以被線性地鑲嵌到低維空間中,同時其空間結構只遭受比較小的形變[6]。約翰遜-林登斯特勞斯定理的證明,還說明了如何用隨機投影法明確地求出這個變換,所用的算法只需要隨機多項式時間[7]。當然,降維不是免費的:如果要求形變很少的話,代價是被嵌入的低維空間維數不能很低;反之亦然,如果要求將點集嵌入很低維的空間,那麼就不能很好地控制結構形變的程度。
因為能將維數下降到樣本量的對數階,更兼所用的變換是線性的、顯式的還可以被快速計算,約翰遜-林登斯特勞斯定理是一個力度非常強的結論。
定理陳述
[編輯]對任何給定的以及維歐幾里德空間中的個點,對於任意滿足條件的正整數,存在一個線性映射,將這個點,從(維數可能很高的空間)中映射到(低維空間)中,同時「基本上」保持了點集成員兩兩之間的距離,即:對於任意兩個點,都有
更進一步地,這個線性映射還可以在隨機多項式時間內求出[7]。
直觀理解
[編輯]約翰遜-林登斯特勞斯定理揭示了一些關於降維映射深刻事實,其中一些還是違反簡單直覺的[8]。因此,要想直觀地理解這個定理,對初學者來說,可能比從數學式子上讀懂證明還要難(反而此定理的證明只用到了比較簡單的關於投影的隨機誤差不等式[9])。舉例來說,定理的結論表明,度量形變程度的誤差參數以及低維空間的維數這兩個度量降維水準的關鍵量,均與原始數據所在的空間維數或者原始的個點具體為何種空間結構無關,這是很不平凡的[9]。
最優性
[編輯]約翰遜-林登斯特勞斯定理是不能被本質性地改進的[10],即:給定任意正整數和誤差參數,存在某個以及中的個點,這個點集「難以降維」——也就是說,對任何一個滿足「基本保持點距」要求(即:要對任意成立)的線性映射,它用來鑲嵌高維數據的那個低維空間(即),至少必須具有
這麼多的維數[11]。
證明提要
[編輯]定理可以用高年級大學生容易理解的方法證明[7][12],其思路是證明如下事實:多次獨立地重複進行隨機投影的試驗,每次試驗中隨機抽取的投影都有至少的概率符合定理中對映射全部的要求(顯然,驗證任何一個是否符合這些要求只需時間),因此只要重複該獨立實驗次就能以逼近100%的概率產生至少一個符合要求的映射。
參考文獻
[編輯]- ^ Johnson, William B; Lindenstrauss, Joram. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics. 1984, 26 (1): 189-206.
- ^ Devdatt Dubhashi. Johnson-Lindenstrauss, Concentration and applications to Support Vector Machines and Kernels (PDF). simons.berkeley.edu. [2018-11-13]. (原始內容存檔 (PDF)於2020-10-27).
- ^ Suresh Venkat. When to use the Johnson-Lindenstrauss lemma over SVD?. cstheory.stackexchange.com. [2018-11-13]. (原始內容存檔於2020-11-25).
- ^ Krahmer, Felix; Ward, Rachel. New and improved Johnson--Lindenstrauss embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis. 2011, 43 (3): 1269--1281.
- ^ Akselrod-Ballin, Ayelet; Bock, Davi and Reid, R Clay and Warfield, Simon K. Accelerating image registration with the Johnson--Lindenstrauss lemma: application to imaging 3-D neural ultrastructure with electron microscopy. IEEE transactions on medical imaging. 2011, 30 (7): 1427--1438.
- ^ Paul Beame. CSE 522: Sublinear (and Streaming) Algorithms Spring 2014 Lecture 10: Johnson-Lindenstrauss Lemmas (PDF). courses.cs.washington.edu. [2018-11-13]. (原始內容存檔 (PDF)於2017-04-01).
- ^ 7.0 7.1 7.2 Dasgupta, Sanjoy; Gupta, Anupam. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithms. 2003, 22 (1): 60--65.
- ^ Sariel Har-Peled. The Johnson-Lindenstrauss Lemma (PDF). sarielhp.org. [2018-11-13].
- ^ 9.0 9.1 Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge University Press. 2018-08-01 [2018-11-13]. ISBN 9781108415194.
- ^ Alon, Noga. Problems and results in extremal combinatorics—I. Discrete Mathematics. 2003, 273 (1-3): 31--53.
- ^ Larsen, Kasper Green; Nelson, Jelani. Optimality of the johnson-lindenstrauss lemma. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE: 633––638. 2017.
- ^ Michael Mahoney. CS369M: Algorithms for Modern Massive Data Set Analysis Lecture 1: The Johnson-Lindenstrauss Lemma (PDF). cs.stanford.edu. [2018-11-13]. (原始內容存檔 (PDF)於2015-12-13).