Проклятие размерности и no free lunch

В высокой размерности объём растёт быстрее числа наблюдений. Сетка взрывается, соседние точки отдаляются, а шар занимает исчезающую долю куба. Методы спасает не магия оптимизатора, а предположение, что реальные данные имеют структуру.

Десять делений на каждой оси

Для одной температуры диапазон можно разбить на десять интервалов и собрать наблюдения в каждом. Для двух признаков понадобится $10^2=100$ клеток, для шести — миллион, для двадцати — $10^{20}$:

$$N_{\text{cells}}=m^d.$$

Если удвоить разрешение каждой координаты, число клеток растёт в $2^d$ раз. При фиксированном наборе данных большинство клеток пустеет. Локальная оценка, которая опирается на соседей в малом кубике, перестаёт видеть соседей.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Шар исчезает внутри куба

Объём единичного $d$-мерного шара

$$V_d=\frac{\pi^{d/2}}{\Gamma(d/2+1)}$$

сначала растёт, затем быстро стремится к нулю. Куб $[-1,1]^d$ имеет объём $2^d$, поэтому доля вписанного шара

$$\frac{V_d}{2^d}$$

исчезает ещё быстрее. Большая часть объёма куба лежит около углов, далеко от центра.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Расстояния становятся похожими

Для независимых координат расстояние

$$\|X-Y\|_2^2=\sum_{j=1}^d(X_j-Y_j)^2$$

складывает много вкладов. Сумма концентрируется около среднего: абсолютный разброс растёт как $\sqrt d$, а среднее как $d$, поэтому относительный разброс убывает. Ближайший и дальний сосед оказываются похожими по расстоянию.

Это не означает, что все точки буквально равноудалены. Оно означает, что контраст расстояний слабеет при независимом шуме во многих координатах. k-NN начинает голосовать по соседям, которые не очень локальны.

Нормировка масштаба обязательна: один признак в рублях способен захватить евклидово расстояние. Но стандартизация не удаляет сотни нерелевантных координат; каждая всё равно добавляет шумовой квадрат.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Лаборатория объёма

Увеличивайте $d$ при фиксированном числе точек и наблюдайте долю шара, число клеток и контраст расстояний. Затем включите только две информативные координаты, остальные сделайте шумовыми. k-NN ухудшится, хотя полезный сигнал не изменился. Отключение шумовых признаков вернёт геометрию.

Как структура спасает

Реальные изображения имеют миллионы пикселей, но не заполняют весь куб возможных цветов. Естественные фотографии лежат около сложного низкоразмерного множества: соседние пиксели связаны, объекты имеют края и текстуры. Свёрточная сеть использует локальность и повторяемость шаблонов.

Разреженность предполагает, что важны лишь немногие признаки. Ridge и lasso из урока 51 кодируют малую норму или разреженность. Низкий ранг предполагает, что матрица объектов описывается несколькими скрытыми факторами. Kernel и базисные функции задают осмысленную меру близости.

Структура уменьшает эффективную, а не обязательно исходную размерность. Сто координат, лежащих почти на двумерной поверхности, могут требовать объём как для 2D, если алгоритм умеет найти поверхность.

PCA как поиск направлений разброса

После центрирования PCA выбирает ортонормированные направления с максимальной дисперсией. Первые $k$ компонент минимизируют средний квадрат ошибки линейного восстановления. Это сжатие без меток.

Большая дисперсия не всегда означает полезность для класса. Малый диагностический сигнал может жить в направлении с малой общей вариативностью. Поэтому число компонент выбирают относительно задачи, а pipeline PCA обучают только на train.

Проекция создаёт собственный гиперпараметр $k$. Если перебрать десятки значений и выбрать лучшее по той же validation, уменьшение размерности не освобождает от цены выбора модели. Полезно одновременно показывать долю объяснённой дисперсии, качество задачи и устойчивость компонент между выборками. Высокая explained variance говорит о восстановлении $x$, а не обязательно о сохранении $y$.

Случайная проекция сохраняет расстояния приближённо

Лемма Джонсона–Линденштраусса говорит: конечный набор $n$ точек можно случайно спроецировать в размерность порядка $k=O(\log n/\varepsilon^2)$, сохранив попарные расстояния с относительной ошибкой около $\varepsilon$. Требуемая $k$ зависит логарифмически от числа точек, а не от исходных миллионов координат.

Это не бесплатное снятие проклятия: теорема сохраняет геометрию уже наблюдаемого конечного облака, но не обещает сохранить редкий предсказательный признак или структуру будущего сдвига. Случайная проекция полезна как быстрый baseline и контроль того, насколько алгоритму нужна специальная предметная карта.

No free lunch

Без предположений нельзя создать алгоритм, лучший на всех возможных зависимостях. Если метки произвольно назначены каждой точке огромного куба, предсказать новую точку невозможно до её наблюдения. Обобщение возникает потому, что мы считаем близкие или структурно похожие объекты связанными.

No free lunch не запрещает обучение; он требует назвать inductive bias. Линейная модель верит в линейность признаков, дерево — в осевые разбиения, CNN — в локальные шаблоны, регуляризация — в простые веса. Выбор bias опирается на задачу и проверяется по истинному риску.

Геномные признаки

У исследования могут быть 500 пациентов и 20 000 экспрессий генов. Обычная ковариационная матрица вырождена, ближайшие соседи нестабильны, а число случайных корреляций огромно. Нельзя сначала выбрать гены по всей таблице, а потом cross-validate: метки validation уже участвовали в отборе.

Pipeline внутри каждого train-fold выполняет нормировку, фильтрацию или lasso, затем обучение. Стабильность выбранных генов по fold важнее одного списка. Предметные пути генов могут дать групповые признаки и уменьшить эффективную размерность.

Размерность и вычисления

Высокая $d$ увеличивает память и стоимость градиента, но вычислительная проблема не равна статистической. Можно быстро умножить разреженный вектор из миллиона координат и всё равно не иметь достаточно данных для произвольной функции. И наоборот, сложная исходная запись может сжиматься устойчивым предобученным представлением.

Проклятие размерности сообщает, где спрятано предположение: в выборе признаков, архитектуре, регуляризации, manifold или инвариантности. Если алгоритм работает в огромном пространстве, он обязательно использует какую-то структуру, даже если автор её не назвал.

Расстояния в булевом кубе

Возьмём два независимых бинарных вектора длины $d$. В каждой координате они различаются с вероятностью $1/2$, поэтому Hamming distance имеет распределение $\operatorname{Bin}(d,1/2)$. Его среднее равно $d/2$, а стандартное отклонение — $\sqrt d/2$.

При $d=10$ среднее расстояние $5$, стандартное отклонение около $1{,}58$: соседи и далёкие объекты заметно различаются. При $d=1000$ получаем $500\pm15{,}8$. После деления на $d$ почти все расстояния сжимаются около $0{,}5$; интервал трёх стандартных отклонений занимает примерно от $0{,}453$ до $0{,}547$. Обычный nearest neighbors с равными весами координат теряет контраст.

Спасение возможно, если метка зависит, например, лишь от первых двадцати битов. Тогда расстояние по этим координатам содержит сигнал, а остальные $980$ добавляют шум. Отбор признаков или обученная метрика должны выполняться внутри train-fold: иначе validation подскажет, какие биты удобны. Проклятие возникает не от длинной записи само по себе, а от попытки считать все направления одинаково содержательными.

Задачи