Перегляд вихідного коду сторінки Лема Джонсона — Лінденштрауса

{{Машинне навчання}}
'''Лема Джонсона&nbsp;— Лінденштрауса''' ({{lang-en|Johnson–Lindenstrauss lemma}}) твердить, що набір точок у багатовимірному просторі може бути вбудований у простір значно меншого виміру таким чином, що відстані між точками збережуться майже без викривлень. Відповідні проєкції можуть бути ортогональними. Лема названа на честь Вільяма Б. Джонсона та Джорама Лінденштрауса<ref>{{cite encyclopedia
 | last1 = Johnson | first1 = William B. | last2 = Lindenstrauss | first2 = Joram 
 | contribution = Extensions of Lipschitz mappings into a Hilbert space
 | doi = 10.1090/conm/026/737400
 | location = Providence, RI
 | mr = 737400
 | pages = 189–206
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Conference in modern analysis and probability (New Haven, Conn., 1982)
 | volume = 26
 | year = 1984
 | editor1-last = Beals | editor1-first = Richard
 | editor2-last = Beck | editor2-first = Anatole
 | editor3-last = Bellow | editor3-first = Alexandra
 |display-editors = 3 | editor4-last = Hajian | editor4-first = Arshag
 | isbn = 0-8218-5030-X }}
</ref>.

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

== Формулювання ==
Нехай <math>0 < \varepsilon < 1</math>.
Тоді для любої множини <math>X</math> из <math>n</math> точок в <math>\mathbb R^N</math> і&nbsp; <math>m > \tfrac{8\cdot \ln n}{\varepsilon^2}</math> існує лінійне відображення <math>f: \mathbb{R}^N \rightarrow \mathbb{R}^m</math> таке, що
: <math>(1-\varepsilon)\cdot \|u-v\|^2 \leq \|f(u) - f(v)\|^2 \leq (1+\varepsilon)\cdot \|u-v\|^2</math>
для усіх <math>u,v \in X</math>.

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

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

== Про доведення ==
Одне з доведень ґрунується на властивості [[Концентрація міри|концентрації міри]].

== Альтернативне формулювання ==
Спорідненою лемою є лема Джонсона&nbsp;— Лінденштрауса про розподіл. Ця дистрибутивна лема стверджує, що для любого 0&nbsp;<&nbsp;''ε'', ''δ''&nbsp;<&nbsp;1/2 і позитивного цілого числа ''d'' існує розподіл '''R'''<sup>''k'' × ''d''</sup>, з якого вилучається матриця ''A'' так, що для ''k'' = ''O''(''ε''<sup>−2</sup>log(1/''δ'')) і для любого вектора одиничної довжини ''x'' ∈ '''R'''<sup>''d''</sup> справедливе твердження<ref>{{cite encyclopedia
 | last1 = Johnson
 | first1 = William B.
 | last2 = Lindenstrauss
 | first2 = Joram
 | contribution = Extensions of Lipschitz mappings into a Hilbert space
 | doi = 10.1090/conm/026/737400
 | location = Providence, RI
 | mr = 737400
 | pages = [https://archive.org/details/conferenceinmode0000conf/page/189 189–206]
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Conference in modern analysis and probability (New Haven, Conn., 1982)
 | volume = 26
 | year = 1984
 | editor1-last = Beals
 | editor1-first = Richard
 | editor2-last = Beck
 | editor2-first = Anatole
 | editor3-last = Bellow
 | editor3-first = Alexandra
 | display-editors = 3
 | editor4-last = Hajian
 | editor4-first = Arshag
 | isbn = 0-8218-5030-X
 | url-access = registration
 | url = https://archive.org/details/conferenceinmode0000conf/page/189
 }}
</ref>
: <math> P(|\Vert Ax\Vert_2^2-1|>\varepsilon)<\delta</math>

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

Зв'язок дистрибутивної версії леми з її еквівалентом можливо отримати, якщо задати <math>x = (u-v)/\|u-v\|_2</math> і <math>\delta < 1/n^2</math> для якоїсь пари ''u'',''v'' в ''X''.

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

Зокрема, Ейлоном <!--({{lang-en|Ailon}})--> і Бернаром Шазелем <!--({{lang-en|Bernard Chazelle}})--> в 2006&nbsp;р. було запропоновано ''швидке перетворення Джонсона&nbsp;— Лінденштрауса (ШПДЛ)'', яке дозволило виконати матрично-векторний добуток за час <math>d\log d + k^{2+\gamma}</math> для любої константи <math>\gamma>0</math>.<!--{{lang-en|''Fast Johnson Lindenstrauss Transform'' (FJLT)}}--><ref>{{cite encyclopedia
 | last1 = Ailon | first1 = Nir | last2 = Chazelle | first2 = Bernard
 | chapter = Approximate nearest neighbors and the fast Johnson–Lindenstrauss transform
 | title = Proceedings of the 38th Annual ACM Symposium on Theory of Computing
 | year = 2006
 | mr = 2277181
 | doi = 10.1145/1132516.1132597
 | pages = 557–563
 | publisher = ACM Press
 | location = New York
 | isbn = 1-59593-134-1}}
</ref>

Особливий випадок становлять тензорні випадкові проєкції, для яких вектор одиничної довжини ''x'' має тензорну структуру, і JL-матриці ''A'' можуть бути виражені через [[Добуток_Хатрі-Рао#Торцевий добуток|торцевий добуток]] кількох матриць з однаковою кількістю незалежних рядків.

== Тензорні проєкції багатовимірних просторів ==

Для представлення тензорних проєкцій, що використовуються в ШПДЛ в багатовимірному випадку, у вигляді комбінації двох JL-матриць, може бути використано [[Добуток_Хатрі-Рао#Торцевий добуток|торцевий добуток]] ({{lang-en|face-splitting product}}), запропонований в 1996&nbsp;р. [[Слюсар Вадим Іванович|Слюсарем В. І.]]<ref name=slyusar>{{Cite journal|last=Slyusar|first=V. I.|date=27 грудня 1996|title=End products in matrices in radar applications.|url=http://slyusar.kiev.ua/en/IZV_1998_3.pdf|journal=Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3|pages=50–53|accessdate=31 липня 2020|archive-date=27 липня 2020|archive-url=https://web.archive.org/web/20200727055858/http://slyusar.kiev.ua/en/IZV_1998_3.pdf}}</ref><ref name=slyusar1>{{Cite journal|last=Slyusar|first=V. I.|date=1997-05-20|title=Analytical model of the digital antenna array on a basis of face-splitting matrix products.|url=http://slyusar.kiev.ua/ICATT97.pdf|journal=Proc. ICATT-97, Kyiv|pages=108–109|accessdate=31 липня 2020|archive-date=25 січня 2020|archive-url=https://web.archive.org/web/20200125134216/http://slyusar.kiev.ua/ICATT97.pdf}}</ref><ref name="DIPED">{{Cite journal|last=Slyusar|first=V. I.|date=1997-09-15|title=New operations of matrices product for applications of radars|url=http://slyusar.kiev.ua/DIPED_1997.pdf|journal=Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.|pages=73–74|accessdate=31 липня 2020|archive-date=25 січня 2020|archive-url=https://web.archive.org/web/20200125144223/http://slyusar.kiev.ua/DIPED_1997.pdf}}</ref><ref name=slyusar2>{{Cite journal|last=Slyusar|first=V. I.|date=13 березня 1998|title=A Family of Face Products of Matrices and its Properties|url=http://slyusar.kiev.ua/FACE.pdf|journal=Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999.|volume=35|issue=3|pages=379–384|doi=10.1007/BF02733426|accessdate=31 липня 2020|archive-date=25 січня 2020|archive-url=https://web.archive.org/web/20200125144927/http://slyusar.kiev.ua/FACE.pdf}}</ref><ref name=general>{{Cite journal|last=Slyusar|first=V. I.|date=2003|title=Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels|url=http://slyusar.kiev.ua/en/IZV_2003_10.pdf|journal=Radioelectronics and Communications Systems|volume=46|issue=10|pages=9–17|accessdate=31 липня 2020|archive-date=20 вересня 2020|archive-url=https://web.archive.org/web/20200920194237/http://slyusar.kiev.ua/en/IZV_2003_10.pdf}}</ref><ref name= "Fortiana">Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics&nbsp;— Theory and Methods, 38:19, P. 3501 [http://dx.doi.org/10.1080/03610920802592860] {{Webarchive|url=https://web.archive.org/web/20210426020635/https://www.tandfonline.com/doi/abs/10.1080/03610920802592860 |date=26 квітня 2021 }}</ref>.
 
Розглянемо дві JL-матриці проєкцій багатовимірного простору: <math>{C}\in\mathbb R^{3\times 3}</math> и <math>{D}\in\mathbb R^{3\times 3}</math>.
Їх торцевий добуток <math>{C}\bullet {D}</math><ref name=slyusar /><ref name=slyusar1 /><ref name="DIPED" /><ref name=slyusar2 /><ref name=general /> має вид:
: <math>
{C} \bullet {D}
= 
\left[
\begin{array} { c }
{C}_1 \otimes {D}_1\\\hline 
{C}_2 \otimes {D}_2\\\hline
{C}_3 \otimes {D}_3\\
\end{array}
\right].
</math>

JL-матриці, що визначені у такий спосіб, мають менше випадкових біт і можуть швидко перемножуватися на вектори тензорної структури завдяки тотожності<ref name="DIPED" />:
 
: <math>(\mathbf{C} \bull \mathbf{D})(x\otimes y) = \mathbf{C}x \circ \mathbf{D} y
= \left[
\begin{array} { c }
(\mathbf{C}x)_1 (\mathbf{D} y)_1 \\
(\mathbf{C}x)_2 (\mathbf{D} y)_2 \\
\vdots
\end{array}\right]
</math>,
 
де <math>\circ</math>&nbsp;— поелементний [[добуток Адамара]].

Перехід від матриці ''A'' до торцевого добутку дозволяє оперувати матрицями меншого розміру. У цьому контексті ідея [[Добуток_Хатрі-Рао#Торцевий добуток|торцевого добутку]] була використана в 2010<ref>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.</ref> для вирішення завдання [[Диференційна приватність|диференційної приватності]] ({{lang-en|differential privacy}}). Крім того, аналогічні обчислення були задіяні для ефективної реалізації [[Ядрові методи|ядрових методів]] машинного навчання та в інших алгоритмах лінійної алгебри<ref name="woodruff">Woodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1-157.</ref>.

В 2020&nbsp;р. було показано, що для створення проєкцій малої розмірності в [[Добуток_Хатрі-Рао#Торцевий добуток|торцевому добутку]] досить використовувати будь-які матриці з випадковими незалежними рядками, однак більш сильні гарантії досягнення малих спотворень проєкцій багатовимірних просторів можуть бути досягнуті за допомогою дійсних гаусових матриць Джонсона-Лінденштрауса<ref name="highdeg">{{cite conference
| title = Oblivious Sketching of High-Degree Polynomial Kernels
| first1 = Thomas
| last1 = Ahle
| first2 = Michael
| last2 = Kapralov
| first3 = Jakob
| last3 = Knudsen
| first4 = Rasmus
| last4 = Pagh
| first5 = Ameya
| last5 = Velingker
| first6 = David
| last6 = Woodruff
| first7 = Amir
| last7 = Zandieh
| date = 2020
| publisher = Association for Computing Machinery
| conference = ACM-SIAM Symposium on Discrete Algorithms
|doi = 10.1137/1.9781611975994.9}}</ref>.

Якщо матриці <math>C_1, C_2, \dots, C_c</math> є незалежними <math>\pm1</math> або гаусовими матрицями, то комбінована матриця <math>C_1 \bullet  \dots \bullet C_c</math> задовольняє лемі Джонсона-Лінденштрауса про розподіл, якщо кількість строк становить не менше
: <math>O(\epsilon^{-2}\log1/\delta + \epsilon^{-1}(\tfrac1c\log1/\delta)^c)</math><ref name="highdeg" />.

Для великих <math>\epsilon</math> дистрибутивна лема Джонсона-Лінденштрауса виконується строго, при цьому нижня границя величини викривлень апроксимації має експоненціальну залежність
<math>(\log1/\delta)^c</math><ref name="highdeg" />.
Пропонуються альтернативні конструкції JL-матриць, щоб обійти це обмеження<ref name="highdeg" />.

== Див. також ==
* [[Тензорний скетч]]

== Примітки ==
{{reflist|2}}

== Джерела ==
* {{Citation|title=Database-friendly random projections: Johnson-Lindenstrauss with binary coins|year=2003|last=Achlioptas|first=Dimitris|journal=Journal of Computer and System Sciences|volume=66|issue=4|pages=671–687|doi=10.1016/S0022-0000(03)00025-4}}. Journal version of a paper previously appearing at PODC 2001.
* {{Citation|title=An elementary proof of a theorem of Johnson and Lindenstrauss|year=2003|last1=Dasgupta|last2=Gupta|first1=Sanjoy|first2=Anupam|url=http://cseweb.ucsd.edu/~dasgupta/papers/jl.pdf|journal=Random Structures & Algorithms|volume=22|issue=1|pages=60–65|doi=10.1002/rsa.10073|13=|accessdate=31 липня 2020|archive-date=5 серпня 2012|archive-url=https://web.archive.org/web/20120805002518/http://cseweb.ucsd.edu/~dasgupta/papers/jl.pdf}}.
* Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), «[http://www.seas.upenn.edu/~mlazar/fibers.pdf On fiber diameters of continuous maps] {{Webarchive|url=https://web.archive.org/web/20160910133339/http://www.seas.upenn.edu/~mlazar/fibers.pdf |date=10 вересня 2016 }}».

{{Бібліоінформація}}
{{Штучний інтелект}}
[[Категорія:Обробка інформації]]
[[Категорія:Прикладна математика]]
[[Категорія:Зниження розмірності| ]]
[[Категорія:Обчислювальні галузі досліджень]]
[[Категорія:Штучний інтелект]]
[[Категорія:Машинне навчання]]