Теория вероятностей

Вероятность в высоких размерностях

В пространстве размерности 1000 два случайных вектора почти ортогональны с вероятностью, стремящейся к 1. Расстояние между ними сосредоточено вблизи $\sqrt{2d}$. Это «проклятие размерности» - и одновременно подарок: лемма Джонсона-Линденштрауса позволяет сжать 1000 векторов в $\mathbb{R}^{10000}$ до $\mathbb{R}^{100}$ с сохранением расстояний.

Locality-sensitive hashing (LSH): случайные проекции в $\mathbb{R}^k$ с малым $k$ приближённо сохраняют евклидовы расстояния - основа алгоритмов approximate nearest neighbor (Faiss, ScaNN) для поиска похожих изображений и текстов.
Word2Vec и BERT: эмбеддинги слов живут в $\mathbb{R}^{768}$ или $\mathbb{R}^{1536}$. Концентрация нормы означает, что косинусное сходство надёжно различает близкие и далёкие векторы - без него семантический поиск был бы ненадёжен.
Случайные матрицы в нейросетях (random features, sketching): теорема JL позволяет заменить дорогие матричные операции случайными проекциями с гарантированными приближениями.

Цели урока

Доказывать концентрацию нормы и почти ортогональность в высоких размерностях
Формулировать и применять лемму Джонсона-Линденштрауса для снижения размерности
Объяснять проклятие размерности и его влияние на алгоритмы машинного обучения

Предварительные знания

Гауссовское распределение и хи-квадрат распределение
Концентрация меры: неравенства Маркова и Чебышёва
Сингулярное разложение (SVD) и PCA

Концентрация нормы в $\mathbb{R}^d$

Если $X = (X_1, \ldots, X_d)$ с i.i.d. $X_i \sim \mathcal{N}(0,1)$, то $\|X\|_2^2 = \sum X_i^2 \sim \chi^2_d$ с $\mathbb{E}[\|X\|_2^2] = d$ и $\mathrm{Var}(\|X\|_2^2) = 2d$. По ЦПТ $\|X\|_2/\sqrt{d} \to 1$ почти наверное при $d \to \infty$. Точнее: $P(|\|X\|_2 - \sqrt{d}| > t) \leq 2e^{-t^2/4}$ - хвосты убывают экспоненциально. Следствие: объём единичного шара $V_d \sim (2\pi e/d)^{d/2}/\sqrt{\pi d}$ стремится к нулю - почти весь объём на поверхности.

Лемма Джонсона-Линденштрауса (1984): для любого набора $n$ точек в $\mathbb{R}^d$ и $\varepsilon > 0$ существует линейное отображение $f: \mathbb{R}^d \to \mathbb{R}^k$ с $k = O(\log n / \varepsilon^2)$ такое, что $(1-\varepsilon)\|u-v\|^2 \leq \|f(u)-f(v)\|^2 \leq (1+\varepsilon)\|u-v\|^2$. Случайная матрица Гаусса или матрица Рэдемахера реализует такое отображение с высокой вероятностью. Размерность $k$ зависит от числа точек, но не от исходной размерности $d$.

JL-лемма сохраняет евклидовы расстояния, но не обязательно сохраняет другие структуры: углы, линейные зависимости, разреженность. Для задач, где важны не расстояния, а направления или линейные структуры (например, PCA), случайные проекции могут быть неподходящими без дополнительного анализа.

Проклятие размерности и концентрация на оболочке

Ричард Беллман в 1957 году ввёл термин «проклятие размерности» для задач оптимального управления, столкнувшись с тем, что объём гиперкуба растёт экспоненциально по $n$. Сегодня поиск ближайших соседей по 1000 признакам в индустрии (рекомендательные системы Netflix, эмбеддинги OpenAI размерности 1536) сталкивается с тем же эффектом: объём единичного шара $V_n = \pi^{n/2}/\Gamma(n/2+1)$ убывает к нулю при $n \to \infty$, а $V_{100} \approx 10^{-40}$ - для случайной точки куба $[-1,1]^{100}$ вероятность попасть в шар равна $10^{-40}$.

В $\mathbb{R}^{100}$ какова доля объёма единичного шара, лежащая в оболочке толщиной $0.05$ у поверхности?

$P(\|X\| > 0.95) = 1 - 0.95^{100} \approx 1 - 0.0059 \approx 0.994$. Более 99% объёма сосредоточено в тонкой оболочке толщиной всего 5% радиуса.

Концентрация нормы гауссовского вектора

Если $X = (X_1, \dots, X_n)$ с независимыми $X_i \sim N(0,1)$, то $\|X\|^2 \sim \chi^2_n$ имеет среднее $n$ и дисперсию $2n$. По закону больших чисел Колмогорова $\|X\|/\sqrt{n} \to 1$ почти наверное. Этот факт лежит в основе инициализации He и Xavier в нейросетях, где веса масштабируются как $1/\sqrt{n}$, чтобы сохранить дисперсию активаций при $n = 1024$ нейронов в слое.

Пусть $X \sim N(0, I_{1000})$. Чему примерно равно $\|X\|$?

$E[\|X\|^2] = n = 1000$, поэтому $\|X\| \approx \sqrt{1000} \approx 31.6$. Отклонение порядка $O(1)$ - гауссовская концентрация.

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

Уильям Джонсон и Йорам Линденштраусс в 1984 году доказали: $n$ точек из $\mathbb{R}^d$ можно вложить в $\mathbb{R}^k$ с $k = O(\log n / \varepsilon^2)$ так, чтобы все попарные расстояния сохранялись с точностью $(1\pm\varepsilon)$. Алгоритмы LSH (Locality-Sensitive Hashing), используемые в Spotify и Pinterest для поиска похожих треков и изображений среди $10^9$ кандидатов, опираются именно на это сжатие.

По лемме Джонсона-Линденштраусса для вложения $n = e^{10} \approx 22000$ точек с $\varepsilon = 0.1$ требуется размерность порядка:

$k = O(\log n / \varepsilon^2) = O(10/0.01) = O(1000)$. Не зависит от исходной $d$.

Проклятие размерности в k-NN

В размерности $d=1$: ближайший сосед в выборке из $n$ точек ожидается в расстоянии $\sim 1/n$. В размерности $d$: нужно $n \sim (1/\varepsilon)^d$ точек для покрытия с разрешением $\varepsilon$. При $d=100$ и $n=10^6$: разрешение $\varepsilon \sim 10^{6/100} \approx 1.15$ - фактически 0 покрытие. Метрика медленно убывает: $d_\mathrm{max}/d_\mathrm{min} \to 1$ при $d \to \infty$ при случайных точках - различить ближнего и дальнего соседа становится невозможно.

Итоги

В высоких размерностях нормы концентрируются, случайные векторы почти ортогональны, объём сосредоточен на поверхности сферы.
JL-лемма: $n$ точек в любой размерности вкладываются в $O(\log n)$ измерений с $(1\pm\varepsilon)$-искажением расстояний.
Это основа всех алгоритмов случайного снижения размерности.

Связь с другими темами

Концентрация меры (prob-22) - общий принцип, объясняющий как концентрацию нормы, так и экспоненциальные хвосты JL. Статистическое обучение (prob-26) использует размерность $k$ из JL как «эффективную размерность» гипотезного класса. Случайные матрицы - объект матричной теории вероятностей с богатой собственной теорией.

Prob 22 — связан
Prob 26 — связан

Вопросы для размышления

Лемма JL утверждает $k = O(\log n / \varepsilon^2)$. Что происходит при $\varepsilon \to 0$: можно ли сохранить расстояния точно за счёт большей размерности $k$?
Есть ли нижняя граница на $k$, гарантирующая, что нельзя обойтись меньшим числом измерений?

Связанные уроки

la-15-svd