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

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

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

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

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

Формула короткая, а последствия драматические. Удвоим разрешение каждой оси — число клеток вырастет в

$$\frac{(2m)^d}{m^d}=2^d$$

раз: в десяти измерениях это тысяча, в тридцати — миллиард. Наоборот, если мы хотим держать в каждой клетке фиксированное среднее число точек $\bar n$, то выборка обязана расти как

$$n=\bar n\,m^d,$$

то есть экспоненциально по размерности. Именно это, а не какая-то мистика, и называют проклятием размерности.

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

Термин придумал Беллман, решая задачи динамического программирования: таблица значений функции по состоянию системы росла у него как $m^d$, и никакая ЭВМ пятидесятых годов не могла её вместить. Мы встретимся с тем же явлением в статистике, в геометрии и в вычислениях, и каждый раз оно будет иметь одно и то же лицо — экспоненту.

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

Геометрия высокой размерности устроена не так, как подсказывает бумага. Объём единичного шара

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

сначала растёт: $V_1=2$, $V_2=\pi\approx3{,}14$, $V_3=4\pi/3\approx4{,}19$. Он достигает максимума при $d=5$, где $V_5\approx5{,}264$, а дальше падает — и падает стремительно: $V_{20}\approx0{,}0258$. Шар радиуса единица в двадцати измерениях занимает меньше трёх сотых кубической единицы объёма.

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

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

При $d=2$ это $\pi/4\approx0{,}785$: круг занимает почти четыре пятых квадрата. При $d=3$ — уже $\pi/6\approx0{,}524$. При $d=10$ остаётся $2{,}49\cdot10^{-3}$, при $d=20$ — $2{,}46\cdot10^{-8}$, а при $d=50$ — $1{,}54\cdot10^{-28}$. Практически весь объём куба лежит вне вписанного шара, то есть в углах, куда наша двумерная интуиция не заглядывает.

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

Полезно запомнить простой факт: расстояние от центра куба $[-1,1]^d$ до середины грани всегда равно единице, а до угла —

$$\sqrt{\underbrace{1+1+\dots+1}_{d}}=\sqrt d.$$

В двадцати измерениях углы в $\sqrt{20}\approx4{,}47$ раза дальше от центра, чем грани. Куб перестаёт быть похожим на кубик и становится колючим ежом с $2^{20}\approx10^6$ шипами.

Почти весь объём — в тонкой корке

Возьмём теперь сам шар и спросим, где внутри него лежит объём. Доля объёма, попадающая внутрь радиуса $1-\varepsilon$, равна

$$\frac{V_d(1-\varepsilon)^d}{V_d}=(1-\varepsilon)^d,$$

а во внешнюю корку толщиной $\varepsilon$ попадает

$$1-(1-\varepsilon)^d\xrightarrow[d\to\infty]{}1 .$$

При $\varepsilon=0{,}1$: в $d=10$ в корке уже $65{,}1\%$ объёма, в $d=20$ — $87{,}8\%$, в $d=50$ — $99{,}5\%$. Апельсин в пятидесяти измерениях — это почти одна кожура. То же самое верно и для гауссова облака: точки не толпятся у центра, а живут в тонком сферическом слое радиуса примерно $\sqrt d$.

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

Теперь главное для машинного обучения следствие. Пусть координаты независимы; квадрат евклидова расстояния

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

есть сумма $d$ независимых одинаково распределённых слагаемых. По закону больших чисел из урока 41 она концентрируется около своего среднего:

$$\mathbb E\|X-Y\|_2^2=d\,\mu,\qquad \operatorname{sd}\|X-Y\|_2^2=\sqrt d\,\tau,$$

то есть среднее растёт как $d$, а разброс — только как $\sqrt d$. Относительный разброс убывает:

$$\frac{\operatorname{sd}}{\mathbb E}=\frac{\tau}{\mu\sqrt d}\to0 .$$

Отсюда и знаменитый эффект: отношение расстояния до ближайшего соседа к расстоянию до самого дальнего стремится к единице,

$$\frac{\min_i\|q-X_i\|}{\max_i\|q-X_i\|}\xrightarrow[d\to\infty]{}1 .$$

Измерим это честно. Возьмём $500$ точек из стандартного гауссова распределения и посчитаем контраст

$$\text{contrast}=\frac{\max_i\|q-X_i\|-\min_i\|q-X_i\|}{\min_i\|q-X_i\|}.$$

При $d=2$ получается $25{,}54$: дальний сосед в двадцать шесть с половиной раз дальше ближнего. При $d=20$ — уже $1{,}89$, при $d=200$ — $0{,}366$, при $d=2000$ — $0{,}087$. Все точки становятся почти равноудалёнными, и слово «ближайший» теряет содержание.

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

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

Реальные цифры против перемешанных

Правый график рисунка 60.3 — важнейший в этом уроке, поэтому проговорим его медленно. Мы берём реальный набор digits из sklearn: 1797 рукописных цифр, каждая — картинка $8\times8$, то есть точка в $\mathbb R^{64}$. Считаем средний контраст расстояний от случайной цифры до всех остальных: получается $3{,}22$. Теория для 64 независимых координат обещала бы около единицы.

Теперь проведём операцию, которая ничего не меняет в отдельных признаках, но уничтожает связи между ними: внутри каждого из 64 столбцов случайно перемешаем значения по объектам. Гистограмма яркости каждого пикселя останется той же, среднее и дисперсия каждой координаты не изменятся — исчезнет только согласованность. Контраст падает до $0{,}90$:

$$3{,}22\ \xrightarrow[\ \text{перемешали столбцы}\ ]{}\ 0{,}90 .$$

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

Как это ломает k-NN: реальный опыт

Проверим цену лишних координат на настоящей задаче. Набор breast_cancer из sklearn: $n=569$ пациенток, $d=30$ честных признаков, измеренных по изображению биопсии, и бинарная метка. Метод $k$ ближайших соседей ($k=15$) со стандартизацией внутри пайплайна даёт по пятиблочной кросс-валидации точность $96{,}1\%$.

Теперь начнём приписывать к таблице чистый шум — независимые нормальные столбцы, никак не связанные с меткой. Мы не удаляем информацию: все тридцать исходных признаков на месте. Мы только добавляем координаты.

$$\begin{aligned} &+0\ \text{шумовых}:&&96{,}1\%,\\ &+100\ \text{шумовых}:&&93{,}2\%,\\ &+1000\ \text{шумовых}:&&84{,}4\%. \end{aligned}$$

Почти двенадцать процентных пунктов точности мы потеряли, ничего полезного не убрав. Причина видна из формулы для квадрата расстояния: если сигнал живёт в нескольких координатах и даёт вклад $S$, а $m$ шумовых координат добавляют по $\sigma^2$ каждая, то

$$\mathbb E\|x-x'\|^2=\underbrace{S}_{\text{сигнал}}+m\,\sigma^2,$$

и доля полезного вклада равна $S/(S+m\sigma^2)\to0$. Соседство начинает определяться шумом.

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

Насколько силён этот соблазн, легко измерить. Отберём на всей таблице (с метками!) тридцать признаков с наибольшей $F$-статистикой. Среди выбранных окажется пять чисто шумовых столбцов — они просто случайно оказались похожими на метку среди тысячи кандидатов. Это уже знакомая нам из урока 43 проблема множественной проверки: при тысяче испытаний редкое событие перестаёт быть редким.

Пик Хьюза: когда лишний признак вредит

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

Мы воспроизвели этот пик на реальных данных: к тем же тридцати честным признакам добавили двести шумовых, обучались всего по сорока пациенткам и добавляли признаки в порядке убывания их индивидуальной силы. Точность растёт с $89{,}3\%$ на одном признаке до максимума $92{,}3\%$ на двадцати, а затем неуклонно падает до $85{,}3\%$ на всех $230$. Это ровно кривая смещение—вариативность из урока 33, только по оси «число признаков».

Лаборатория размерности

Сигнал в этой лаборатории всегда живёт ровно в двух координатах: классы раздвинуты по первой оси и слабее по второй. Всё остальное — независимый шум, одинаковый для обоих классов. Двигая ползунок размерности, следите за тремя величинами одновременно: гистограмма расстояний слева сжимается в иглу, доля шара в кубе в показаниях падает на десятки порядков, а красная кривая точности $k$-NN уходит вниз. Затем переключитесь на «только 2 информативные»: данные не изменились ни на йоту, мы не добавили ни одного нового наблюдения — но точность возвращается к зелёной линии. Разрыв между красной кривой и зелёной линией и есть цена, которую платит алгоритм за право считать все направления одинаково важными.

Мильман: концентрация меры вместо проклятия

Русская математическая школа посмотрела на ту же экспоненту с другой стороны и превратила проклятие в инструмент. Виталий Давидович Мильман, работавший в шестидесятые-семидесятые годы в Харькове, дал в 1971 году новое доказательство теоремы Дворецкого — через явление концентрации меры. Суть в следующем: если $f$ — липшицева функция на сфере $S^{d-1}$ с константой $L$, то для равномерной меры

$$\mathbb P\bigl\{|f-\operatorname{med}f|>t\bigr\}\le 2\exp\!\left(-\frac{c\,d\,t^2}{L^2}\right).$$

Читается это так: всякая не слишком резкая функция многих переменных почти постоянна. Отклонение от медианы больше $t$ имеет вероятность, экспоненциально малую по $d$. Именно отсюда и слабеющий контраст расстояний (расстояние — липшицева функция координат), и тонкая корка шара, и устойчивость средних.

Мильмановский взгляд перестраивает мышление. Экспонента $e^{-cdt^2}$ — та же самая экспонента, что делала сетку невозможной, но теперь она работает на нас: чем выше размерность, тем надёжнее ведут себя усреднённые величины. Из этого растут концентрационные неравенства, оценки обобщающей способности и современный анализ случайных матриц. Проклятие и благословение — две проекции одного факта.

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

Реальное изображение $256\times256$ в цвете — точка в $\mathbb R^{196\,608}$. Если бы фотографии заполняли этот куб равномерно, случайный набор пикселей выглядел бы как осмысленный снимок; но случайная картинка — всегда «снег». Естественные изображения лежат вблизи сложного маломерного множества: соседние пиксели связаны, у объектов есть края, текстуры повторяются.

Перечислим типы структуры, которые мы уже встречали в курсе, и то, какое предположение каждый из них вносит:

$$\begin{aligned} &\textbf{разреженность:}&&\|w\|_0\ \text{мало}\ \Rightarrow\ \text{lasso, отбор признаков};\\ &\textbf{малая норма:}&&\|w\|_2\ \text{мало}\ \Rightarrow\ \text{ridge};\\ &\textbf{низкий ранг:}&&X\approx UV^\top\ \Rightarrow\ \text{PCA, эмбеддинги};\\ &\textbf{многообразие:}&&x=g(z),\ z\in\mathbb R^k,\ k\ll d;\\ &\textbf{инвариантность:}&&f(Tx)=f(x)\ \Rightarrow\ \text{свёртки, аугментации}. \end{aligned}$$

Штрафы $L_1$ и $L_2$ мы разбирали в уроке 51, низкий ранг и скрытые факторы — в уроке 38, нелинейное многообразие и автокодировщик — в уроке 35, а осмысленный словарь признаков $\phi(x)$ — в уроке 50. Все они делают одно и то же: уменьшают эффективную размерность, оставляя исходную прежней.

PCA и эффективная размерность реальных цифр

Померим эффективную размерность там, где мы её уже видели. У набора digits $d=64$ признака. Главные компоненты (метод из урока 38) дают накопленную объяснённую дисперсию

$$R(k)=\frac{\sum_{j\le k}\lambda_j}{\sum_{j\le 64}\lambda_j},$$

и цифры получаются такие: $80\%$ дисперсии умещаются в $13$ компонентах, $90\%$ — в $21$, $95\%$ — в $29$, $99\%$ — в $41$. Первые две компоненты дают $28{,}5\%$, первые десять — $73{,}8\%$.

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

Здесь нужна оговорка, без которой PCA превращается в суеверие. Большая дисперсия не означает полезности для метки. Диагностический сигнал вполне может жить в направлении с малой общей вариативностью, и тогда «сжатие до 95% дисперсии» его просто выбросит. Высокая объяснённая дисперсия говорит о восстановлении $x$, а не о сохранении $y$.

Случайная проекция и лемма Джонсона–Линденштраусса

Есть удивительный результат, который говорит: чтобы сохранить геометрию конечного облака точек, знать структуру не обязательно — достаточно случайности. Лемма Джонсона–Линденштраусса (1984) утверждает, что для $n$ точек и $\varepsilon\in(0,1)$ найдётся отображение в размерность

$$k=O\!\left(\frac{\log n}{\varepsilon^2}\right),$$

сохраняющее все попарные расстояния с относительной точностью $\varepsilon$:

$$(1-\varepsilon)\|x_i-x_j\|^2\le\|f(x_i)-f(x_j)\|^2\le(1+\varepsilon)\|x_i-x_j\|^2 .$$

Причём $f$ можно взять линейным и случайным: $f(x)=\frac{1}{\sqrt k}Rx$, где элементы $R$ независимы и нормальны. Обратите внимание: требуемая $k$ зависит только от числа точек, логарифмически, и никак не от исходной размерности.

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

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

No free lunch: проклятие как требование назвать предположение

Почему без предположений нельзя обойтись в принципе? Представим, что метки расставлены по всем точкам огромного куба произвольно. Тогда, увидев обучающую выборку, мы не знаем о новой точке ровно ничего: любое её значение согласуется с данными. Число различных функций из $\{0,1\}^d$ в $\{0,1\}$ равно

$$2^{2^d},$$

и при $d=20$ это $2^{1\,048\,576}$ — число, рядом с которым количество атомов во Вселенной выглядит опечаткой. Никакая выборка такое множество не сузит.

Теорема о бесплатном обеде не запрещает обучение — она требует назвать inductive bias, встроенное предположение. Линейная модель верит в линейность по признакам (урок 49), дерево — в осевые разбиения, свёрточная сеть — в локальность и трансляционную эквивариантность, регуляризация — в простоту весов, метод соседей — в гладкость по выбранной метрике. Обобщение, которое мы измеряем истинным риском из урока 58, возникает не из данных самих по себе, а из союза данных и предположения.

Геномные признаки: где проклятие встречается каждый день

Классическая ситуация современной биологии: 500 пациентов и 20 000 уровней экспрессии генов, то есть $d\gg n$. Здесь всё описанное происходит сразу. Выборочная ковариационная матрица размера $20\,000\times20\,000$ по 500 наблюдениям обязательно вырождена: её ранг не превосходит $n-1=499$, так что не менее $19\,501$ собственного значения равны нулю точно:

$$\operatorname{rank}\widehat\Sigma\le n-1\ll d .$$

Обратить такую матрицу нельзя, классические формулы регрессии и расстояние Махаланобиса неприменимы без регуляризации. Случайных корреляций тоже море: при $20\,000$ проверках на уровне $0{,}05$ около тысячи генов окажутся «значимы» просто так. Мы уже видели этот механизм на игрушечном масштабе — среди тысячи шумовых столбцов пять пробрались в тридцатку лучших.

Правильный протокол выглядит так. Внутри каждого обучающего блока кросс-валидации: стандартизация, отбор или $L_1$-регуляризация, обучение. Затем — оценка на отложенном блоке, который ни в чём из этого не участвовал. Отдельно стоит смотреть на стабильность списка генов между блоками: если при смене блока список меняется целиком, вы описали шум, каким бы приличным ни было среднее качество. А предметные знания (сигнальные пути, семейства генов) позволяют объединять признаки в группы и уменьшать эффективную размерность до того, как начнётся статистика.

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

Двоичный случай позволяет увидеть концентрацию совсем без интегралов. Возьмём два независимых случайных вектора из $\{0,1\}^d$. В каждой координате они различаются с вероятностью $1/2$, поэтому расстояние Хэмминга имеет биномиальное распределение:

$$H\sim\operatorname{Bin}\!\left(d,\tfrac12\right),\qquad \mathbb EH=\frac d2,\qquad \operatorname{sd}H=\frac{\sqrt d}{2}.$$

При $d=10$: среднее $5$, стандартное отклонение $\approx1{,}58$ — соседи и далёкие объекты различаются заметно. При $d=1000$: среднее $500$, стандартное отклонение $15{,}81$. Поделим на $d$, чтобы получить долю различающихся битов:

$$\frac Hd\approx\frac12\pm\frac{3}{2\sqrt d},$$

и трёхсигмовый интервал при $d=1000$ занимает всего от $0{,}4526$ до $0{,}5474$. Все объекты различаются примерно наполовину — ровно то, что мы видели у гауссовых точек.

И тот же самый сюжет со спасением. Если метка зависит только от первых двадцати битов, то расстояние по ним содержит весь сигнал, а остальные $980$ добавляют шум с ожидаемым вкладом $490$ против максимум $20$. Проклятие возникает не от длинной записи как таковой, а от попытки считать все направления одинаково содержательными.

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

Полезно развести две разные трудности, которые часто путают. Умножить разреженный вектор из миллиона координат на матрицу — вопрос вычислительный, и он решается: стоимость линейной операции растёт как число ненулей, а не как $m^d$. Собрать достаточно данных, чтобы восстановить произвольную функцию миллиона переменных, — вопрос статистический, и он не решается никаким железом:

$$\text{вычисления}\sim O(nd),\qquad \text{данные для произвольной }f\sim m^d .$$

Первое линейно, второе экспоненциально. Поэтому современные модели с миллиардами параметров вовсе не опровергают проклятие: они работают потому, что предположения (локальность, разделяемые веса, предобученные представления) делают эффективную размерность задачи умеренной. И наоборот, короткая запись объекта не гарантирует лёгкости, если зависимость от неё произвольна.

Что стоит унести с собой

Проклятие размерности — не запрет, а диагностический инструмент. Оно безошибочно указывает, где в решении спрятано предположение, и заставляет назвать его вслух: словарь признаков (урок 50), штраф за сложность (урок 51), архитектура, метрика, многообразие, инвариантность. Три числа этого урока стоит помнить наизусть: доля вписанного шара в двадцати измерениях — $2{,}46\cdot10^{-8}$; контраст расстояний у настоящих цифр — $3{,}22$ против $0{,}90$ у тех же цифр с перемешанными столбцами; точность $k$-NN на реальной медицинской задаче — $96{,}1\%$ до и $84{,}4\%$ после добавления тысячи бессмысленных координат, причём отбор внутри пайплайна возвращает $94{,}9\%$. Первое — про геометрию, второе — про структуру, третье — про дисциплину. Вместе они и составляют содержание урока.

Задачи