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

Шаблон:Машинне навчання Лема Джонсона — Лінденштрауса (Шаблон:Lang-en) твердить, що набір точок у багатовимірному просторі може бути вбудований у простір значно меншого виміру таким чином, що відстані між точками збережуться майже без викривлень. Відповідні проєкції можуть бути ортогональними. Лема названа на честь Вільяма Б. Джонсона та Джорама Лінденштрауса.

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

Формулювання

Нехай $0<\epsilon <1$. Тоді для любої множини $X$ из $n$ точок в ${ℝ}^N$ і  $m>\frac{8\cdot \ln n}{{\epsilon }^2}$ існує лінійне відображення $f:{ℝ}^N\to {ℝ}^m$ таке, що

$(1-\epsilon )\cdot \Vert u-v{\Vert }^2\le \Vert f(u)-f(v){\Vert }^2\le (1+\epsilon )\cdot \Vert u-v{\Vert }^2$

для усіх $u,v\in X$.

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

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

Про доведення

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

Альтернативне формулювання

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

$P(|\Vert Ax{\Vert }_2^2-1|>\epsilon )<\delta$

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

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

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

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

Зокрема, Ейлоном і Бернаром Шазелем в 2006 р. було запропоновано швидке перетворення Джонсона — Лінденштрауса (ШПДЛ), яке дозволило виконати матрично-векторний добуток за час $d\log d+k^{2+\gamma }$ для любої константи $\gamma >0$.

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

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

Для представлення тензорних проєкцій, що використовуються в ШПДЛ в багатовимірному випадку, у вигляді комбінації двох JL-матриць, може бути використано торцевий добуток (Шаблон:Lang-en), запропонований в 1996 р. Слюсарем В. І..

Розглянемо дві JL-матриці проєкцій багатовимірного простору: $C\in {ℝ}^{3\times 3}$ и $D\in {ℝ}^{3\times 3}$. Їх торцевий добуток $C\bullet D$ має вид:

$C\bullet D=\left[\begin{array}{c}{C}_1\otimes D_1\\ C_2\otimes D_2\\ C_3\otimes D_3\end{array}\right].$

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

$(𝐂\bullet 𝐃)(x\otimes y)=𝐂x\circ 𝐃y=\left[\begin{array}{c}(𝐂x{)}_1(𝐃y{)}_1\\ (𝐂x{)}_2(𝐃y{)}_2\\ ⋮\end{array}\right]$,

де $\circ$ — поелементний добуток Адамара.

Перехід від матриці A до торцевого добутку дозволяє оперувати матрицями меншого розміру. У цьому контексті ідея торцевого добутку була використана в 2010 для вирішення завдання диференційної приватності (Шаблон:Lang-en). Крім того, аналогічні обчислення були задіяні для ефективної реалізації ядрових методів машинного навчання та в інших алгоритмах лінійної алгебри.

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

Якщо матриці $C_1,C_2,\dots ,C_c$ є незалежними $\pm 1$ або гаусовими матрицями, то комбінована матриця $C_1\bullet \dots \bullet C_c$ задовольняє лемі Джонсона-Лінденштрауса про розподіл, якщо кількість строк становить не менше

$O({ϵ}^{-2}\log 1/\delta +{ϵ}^{-1}(\frac{1}{c}\log 1/\delta {)}^c)$.

Для великих $ϵ$ дистрибутивна лема Джонсона-Лінденштрауса виконується строго, при цьому нижня границя величини викривлень апроксимації має експоненціальну залежність $(\log 1/\delta {)}^c$. Пропонуються альтернативні конструкції JL-матриць, щоб обійти це обмеження.

Див. також

• Тензорний скетч

Джерела

• Шаблон:Citation. Journal version of a paper previously appearing at PODC 2001.
• Шаблон:Citation.
• Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), «On fiber diameters of continuous maps Шаблон:Webarchive».