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

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних[en] АвтоМН Асоціативні правила Семантичний аналіз[en] Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик[en] Навчання онтологій[en] Мультимодальне навчання[en]
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання[en] AdaBoost[en] Дерева рішень MARS[en] CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH[en] CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього[en]
Знижування розмірності Факторний аналіз Метод незалежних компонент[en] Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад[en] Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників[en]
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс[en]
Штучна нейронна мережа Автокодувальник Когнітивні обчислення[en] Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа[en] Мемтранзистор Електрохімічна ПДД[en] (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе[en]
Навчання з людьми Активне навчання (машинне навчання)[en] Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися[en]
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання[en] Регуляризація LASSO[en] Тихонова Еластично-сіткова[en] Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання[en]
Місця машинного навчання ECML PKDD[en] NeurIPS[en] ICML[en] ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту[en] Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання[en]
п о р

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

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

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

${\displaystyle (1-\varepsilon )\cdot \|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\cdot \|u-v\|^{2}}$

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

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

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

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

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

${\displaystyle P(|\Vert Ax\Vert _{2}^{2}-1|>\varepsilon )<\delta }$

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

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

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

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

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

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

Розглянемо дві JL-матриці проєкцій багатовимірного простору: ${\displaystyle {C}\in \mathbb {R} ^{3\times 3}}$ и ${\displaystyle {D}\in \mathbb {R} ^{3\times 3}}$. Їх торцевий добуток ${\displaystyle {C}\bullet {D}}$^{[4][5][6][7][8]} має вид:

${\displaystyle {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].}$

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

${\displaystyle (\mathbf {C} \bullet \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]}$,

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

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

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

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

${\displaystyle O(\epsilon ^{-2}\log 1/\delta +\epsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$^[12].

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

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

• Achlioptas, Dimitris (2003), Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, 66 (4): 671—687, doi:10.1016/S0022-0000(03)00025-4. Journal version of a paper previously appearing at PODC 2001.
• Dasgupta, Sanjoy; Gupta, Anupam (2003), An elementary proof of a theorem of Johnson and Lindenstrauss (PDF), Random Structures & Algorithms, 22 (1): 60—65, doi:10.1002/rsa.10073, архів оригіналу (PDF) за 5 серпня 2012, процитовано 31 липня 2020 {{citation}}: Cite має пустий невідомий параметр: |13= (довідка).
• Landweber, Peter; Lazar, Emanuel; Patel, Neel (2015), «On fiber diameters of continuous maps [Архівовано 10 вересня 2016 у Wayback Machine.]».