Лема Джонсона-Лінденштрауса

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Лема Джонсона — Лінденштрауса (англ. Johnson–Lindenstrauss lemma) твердить, що набір точок у багатовимірному просторі може бути вбудований у простір значно меншого виміру таким чином, що відстані між точками збережуться майже без викривлень. Відповідні проекції можуть бути ортогональними. Лема названа на честь Вільяма Б. Джонсона та Джорама Лінденштрауса[1].

Лема є основою алгоритмів стиснення зображень, машинного навчання. Значна частина даних, що зберігаються та обробляються на комп'ютерах, зокрема текст і зображення, може бути представлена ​​у вигляді точок у просторі, однак основні алгоритми роботи з такими даними, як правило, швидко втрачають продуктивність по мірі збільшення розмірності. Тому бажано зменшити розмірність даних таким чином, щоб зберегти відповідну структуру. Лема Джонсона – Лінденштраусса - класичний результат у цій сфері.

Формулювання[ред. | ред. код]

Нехай . Тоді для любої множини из точок в і  існує лінійне відображення таке, що

для усіх .

Випадкова ортогональна проєкція на -вимірний підпростір задовольняє вимозі.

Один з доказів леми заснований на властивості концентрації міри.

Альтернативне формулювання[ред. | ред. код]

Спорідненою лемою є лема Джонсона — Лінденштрауса про розподіл. Ця дистрибутивна лема стверджує, що для любого 0 < ε, δ < 1/2 і позитивного цілого числа d існує розподіл Rk × d, з якого вилучається матриця A так, що для k = O(ε−2log(1/δ)) і для любого вектора одиничної довжини xRd справедливе твердження[2]

Відповідні матриці A отримали назву матриць Джонсона — Лінденштрауса (англ. JL matrices). По суті, дана лема характеризує точність апроксимації матричною проєкцією багатовимірного розподілу.

Зв'язок дистрибутивної версії леми з її еквівалентом можливо отримати, якщо задати і для якоїсь пари u,v в X.

Швидке перетворення Джонсона — Лінденштрауса[ред. | ред. код]

Можливість отримання проекцій меншої розмірності є дуже важливим результатом зазначених лем, однак необхідно, щоб такі проекції можна було отримати за мінімальний час. Операція множення матриці A на вектор x, що фігурує в дистрибутивній лемі, займає час O(kd). Тому були проведені дослідження щодо отримання розподілів, для яких матрично-векторний добуток може бути обчислено швидше, ніж за час O(kd).

Зокрема, Ейлоном і Бернаром Шазелем в 2006 р. було запропоновано швидке перетворення Джонсона — Лінденштрауса (ШПДЛ), яке дозволило виконати матрично-векторний добуток за час для любої константи .[3]

Особливий випадок становлять тензорні випадкові проекції, для яких вектор одиничної довжини x має тензорну структуру, і JL-матриці A можуть бути виражені через торцевий добуток кількох матриць з однаковою кількістю незалежних рядків.

Тензорні проєкції багатовимірних просторів[ред. | ред. код]

Для представлення тензорних проєкцій, що використовуються в ШПДЛ в багатовимірному випадку, у вигляді комбінації двох JL-матриць, може бути використано торцевий добуток (англ. face-splitting product), запропонований в 1996 р. Слюсарем В.І.[4][5][6][7][8][9].

Розглянемо дві JL-матриці проєкцій багатовимірного простору: и . Їх торцевий добуток[4][5][6][7][8] має вид:

JL-матриці, що визначені у такий спосіб, мають менше випадкових біт і можуть швидко перемножуватися на вектори тензорної структури завдяки тотожності[6]:

,

де - поелементний добуток Адамара.

Перехід від матриці A до торцевого добутку дозволяє оперувати матрицями меншого розміру. У цьому контексті ідея торцевого добутку була використана в 2010[10] для вирішення завдання диференційної приватності (англ. differential privacy). Крім того, аналогічні обчислення були задіяні для ефективної реалізації ядрових методів машинного навчання та в інших алгоритмах лінійної алгебри[11].

В 2020 р. було показано, що для створення проекцій малої розмірності в торцевому добутку досить використовувати будь-які матриці з випадковими незалежними рядками, однак більш сильні гарантії досягнення малих спотворень проекцій багатовимірних просторів можуть бути досягнуті за допомогою дійсних гаусових матриць Джонсона-Лінденштрауса[12].

Якщо матриці є незалежними або гаусовими матрицями, то комбінована матриця задовольняє лемі Джонсона-Лінденштрауса про розподіл, якщо кількість строк становить не менше

[12].

Для великих дистрибутивна лема Джонсона-Лінденштрауса виконується строго, при цьому нижня границя величини викривлень апроксимації має експоненціальну залежність [12]. Пропонуються альтернативні конструкції JL-матриць, щоб обійти це обмеження[12].

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Johnson, William B.; Lindenstrauss, Joram (1984). «Conference in modern analysis and probability (New Haven, Conn., 1982)». У Beals, Richard; Beck, Anatole; Bellow, Alexandra та ін.. Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics. 26. Providence, RI: American Mathematical Society. pp. 189–206. doi:10.1090/conm/026/737400. ISBN 0-8218-5030-X. 
  2. Johnson, William B.; Lindenstrauss, Joram (1984). «Conference in modern analysis and probability (New Haven, Conn., 1982)». У Beals, Richard; Beck, Anatole; Bellow, Alexandra та ін.. Conference in modern analysis and probability (New Haven, Conn., 1982). Contemporary Mathematics. 26. Providence, RI: American Mathematical Society. pp. 189–206. doi:10.1090/conm/026/737400. ISBN 0-8218-5030-X. https://archive.org/details/conferenceinmode0000conf/page/189. 
  3. Ailon, Nir; Chazelle, Bernard (2006). «Proceedings of the 38th Annual ACM Symposium on Theory of Computing». Proceedings of the 38th Annual ACM Symposium on Theory of Computing. New York: ACM Press. pp. 557–563. doi:10.1145/1132516.1132597. ISBN 1-59593-134-1. 
  4. а б Slyusar, V. I. (December 27, 1996). End products in matrices in radar applications.. Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50–53. 
  5. а б Slyusar, V. I. (1997-05-20). Analytical model of the digital antenna array on a basis of face-splitting matrix products.. Proc. ICATT-97, Kyiv: 108–109. 
  6. а б в Slyusar, V. I. (1997-09-15). New operations of matrices product for applications of radars. Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73–74. 
  7. а б Slyusar, V. I. (March 13, 1998). A Family of Face Products of Matrices and its Properties. Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379–384. doi:10.1007/BF02733426. 
  8. а б Slyusar, V. I. (2003). Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels. Radioelectronics and Communications Systems 46 (10): 9–17. 
  9. Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics - Theory and Methods, 38:19, P. 3501 [1]
  10. Kasiviswanathan, Shiva Prasad, et al. "The price of privately releasing contingency tables and the spectra of random matrices with correlated rows." Proceedings of the forty-second ACM symposium on Theory of computing. 2010.
  11. Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Theoretical Computer Science 10.1-2 (2014): 1-157.
  12. а б в г Ahle, Thomas; Kapralov, Michael; Knudsen, Jakob; Pagh, Rasmus; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020). Oblivious Sketching of High-Degree Polynomial Kernels ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery. doi:10.1137/1.9781611975994.9. 

Джерела[ред. | ред. код]