← Четвёртое измерение
Содержание
  1. 01 Что такое измерение
  2. 02 Флатландия
  3. 03 Проекции
  4. 04 Вращение
  5. 05 Сечения
  6. 06 Правильные многоячейники
  7. 07 Гиперсфера
  8. 08 Большие размерности
  9. 09 Где живут измерения
  10. 10 История
  11. 11 Как нарисована витрина
EN

Глава 08 · 18 мин

Странная геометрия больших размерностей

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

До сих пор мы поднимались на одну ступень — из трёх измерений в четыре. Теперь шагнём сразу далеко: $n = 10$, $100$, $1000$. Ничего экзотического в этом нет: любая таблица с тысячей столбцов уже задаёт точки тысячемерного пространства, и именно в таких пространствах работают статистика и нейросети. Но геометрия там устроена так, что интуиция, выращенная в трёх измерениях, ошибается почти во всём. Хорошая новость: формулы продолжают работать, и каждое «чудо» этой главы доказывается в несколько строк.

Апельсин, который весь — кожура

Начнём с простого вопроса. Возьмём апельсин радиусом 5 см с кожурой толщиной 5 мм. Какая доля его объёма приходится на кожуру? Кожура — это слой между радиусами $4{,}5$ и $5$ см, а объём шара пропорционален кубу радиуса. Доля мякоти равна $(4{,}5/5)^3 = 0{,}9^3 = 0{,}729$, значит, на кожуру приходится $27{,}1\,\%$. Теперь представим тот же апельсин в $n$ измерениях.

Теорема

Доля объёма $n$-мерного шара радиуса $R$, лежащая на расстоянии не больше $\varepsilon R$ от его поверхности, равна $$1 - (1-\varepsilon)^n \;\ge\; 1 - e^{-\varepsilon n}.$$ При любом фиксированном $\varepsilon > 0$ она стремится к единице с ростом $n$.

Если растянуть фигуру в $n$-мерном пространстве в $k$ раз, каждая координата умножится на $k$, а объём — на $k^n$: так происходит с каждым маленьким кубиком, из которых можно сложить тело. Поэтому $V_n(r) = r^n\,V_n(1)$. Слой у поверхности — это шар радиуса $R$ без шара радиуса $(1-\varepsilon)R$, и его доля равна $1 - (1-\varepsilon)^n$. Неравенство следует из $1 - \varepsilon \le e^{-\varepsilon}$: кривая $e^{-x}$ выпукла и лежит над своей касательной $1 - x$ в точке $0$. ∎

Вот как это выглядит в цифрах:

размерностькожура в 1/10 радиусакожура в 1/100 радиуса
327,1 %3,0 %
1065,1 %9,6 %
3095,8 %26,0 %
10099,997 %63,4 %
1000$100\,\% - 1{,}7\cdot 10^{-44}\,\%$99,996 %

Стомерный апельсин — это практически одна кожура, а у тысячемерного почти весь объём лежит даже в слое толщиной в сотую долю радиуса. Для случайной точки, выбранной равномерно в шаре, это означает: она почти наверняка находится у самой поверхности. Среднее расстояние от центра до такой точки равно $n/(n+1)$ радиуса, для $n = 1000$ это $0{,}999$.

Заодно вспомним, что сам шар в больших размерностях «худеет». Объём единичного шара растёт до $n = 5$ (там он около $5{,}26$), а потом стремится к нулю — это разобрано в главе о гиперсфере. Шар, вписанный в единичный куб, в десяти измерениях занимает около $0{,}25\,\%$ объёма куба, а в ста — меньше $10^{-69}$.

Попробуйте

Поставьте толщину кожуры $0{,}01$ и тяните размерность вправо: около $n = 69$ половина объёма уходит в слой толщиной в процент радиуса. Точки на картинке — настоящие случайные точки $n$-мерного шара. Каждая нарисована на своём расстоянии от центра и на своей высоте $x_1$, поэтому картинка честная, хотя и плоская.

И весь — у экватора

Теперь странность посильнее. Проведём через центр шара «экватор» — гиперплоскость $x_1 = 0$ — и спросим, какая доля объёма лежит в тонкой полосе $|x_1| < \delta$ около неё.

Теорема

Если точка $x$ выбрана равномерно в единичном $n$-мерном шаре, то $\mathbb{E}[x_1^2] = \dfrac{1}{n+2}$, и поэтому $$P\bigl(|x_1| \ge \delta\bigr) \le \frac{1}{(n+2)\,\delta^2}.$$

Сначала найдём $\mathbb{E}|x|^2$. Доля шара внутри радиуса $r$ равна $r^n$ (это предыдущая теорема), значит, плотность распределения $|x|$ равна $n r^{n-1}$ и $\mathbb{E}|x|^2 = \int_0^1 r^2 \cdot n r^{n-1}\,dr = \frac{n}{n+2}$. Шар не меняется при перестановке осей, поэтому все $\mathbb{E}[x_i^2]$ одинаковы, а в сумме они дают $\mathbb{E}|x|^2$. Отсюда $\mathbb{E}[x_1^2] = \frac{1}{n+2}$. Неравенство — это неравенство Маркова для неотрицательной величины $x_1^2$: $P(x_1^2 \ge \delta^2) \le \mathbb{E}[x_1^2]/\delta^2$. ∎

Оценка грубая, на деле хвост убывает как $e^{-n\delta^2/2}$. В тысячемерном шаре в полосе $|x_1| < 0{,}1$ лежит $99{,}85\,\%$ объёма. Но экватор можно провести перпендикулярно любому направлению. Получается, что почти весь шар одновременно лежит у поверхности и у каждого из своих экваторов.

Противоречия здесь нет. Типичная точка шара имеет длину около 1, но каждая её координата порядка $\pm 1/\sqrt{n}$: длина «размазана» по тысяче координат, и ни одна из них не бывает большой. У экватора оказываются не какие-то особые точки, а почти все. Это явление называют концентрацией меры. На сфере его описал Поль Леви в 1920-х годах, а в 1970-х Виталий Мильман сделал его рабочим инструментом геометрии многомерных пространств.

Попробуйте

В виджете выше переключитесь на «Экватор». При $n = 3$ полоса $|x_1| < 0{,}1$ содержит 15 % объёма, при $n = 100$ — уже 69 %, при $n = 1000$ — почти всё. Точки сбиваются одновременно к краю и к горизонтали.

Колючий куб

С кубом происходит то же, только нагляднее. У единичного куба $[0,1]^n$ диагональ равна $\sqrt{n}$: в десяти измерениях $3{,}16$, в ста — 10. Угол между диагональю и ребром находится из $\cos\varphi = 1/\sqrt{n}$: в 3D это $54{,}7°$, в 100D уже $84{,}3°$ — диагональ почти перпендикулярна всем рёбрам сразу. От центра куба до грани $1/2$, до вершины $\sqrt{n}/2$, и вершин $2^n$. Типичная же точка куба удалена от центра примерно на $\sqrt{n/12}$: в 100D это $2{,}9$ — далеко за вписанным шаром радиуса $1/2$ и далеко от вершин. Многомерный куб больше похож на ежа, чем на кубик: узкие «иголки» уходят к вершинам.

Самая эффектная иллюстрация — задача о шарах в углах. Возьмём куб $[-2, 2]^n$ и поставим в каждый его угол единичный шар с центром в точке $(\pm 1, \pm 1, \dots, \pm 1)$. Всего шаров $2^n$; каждый касается $n$ граней куба и $n$ соседних шаров. В середину положим шар, касающийся их всех.

Теорема

Радиус центрального шара равен $\sqrt{n} - 1$. При $n \le 8$ шар лежит строго внутри куба, при $n = 9$ касается его граней, а при $n \ge 10$ выходит за пределы куба, хотя по-прежнему «зажат» между угловыми шарами.

Центр углового шара $(1, 1, \dots, 1)$ удалён от начала координат на $\sqrt{1 + 1 + \dots + 1} = \sqrt{n}$. Центральный шар касается углового, если сумма радиусов равна расстоянию между центрами: $r + 1 = \sqrt{n}$, откуда $r = \sqrt{n} - 1$. По симметрии то же верно для всех $2^n$ угловых шаров. Ближайшие к центру точки границы куба — центры граней, например $(2, 0, \dots, 0)$, до них расстояние 2. Центральный шар остаётся внутри куба, пока $\sqrt{n} - 1 \le 2$, то есть $n \le 9$, причём при $n = 9$ достигается равенство. При $n = 10$ радиус $\sqrt{10} - 1 \approx 2{,}16 > 2$. ∎

По дороге встречаются и другие курьёзы. В четырёх измерениях $r = \sqrt{4} - 1 = 1$: центральный шар ровно такой же, как угловые. А если сравнить объёмы, вычисление показывает, что начиная с $n = 1206$ центральный шар, который должен был ютиться в щели между угловыми, имеет больший объём, чем весь куб $[-2,2]^n$.

Как нарисовать это при $n > 3$? Можно честно разрезать фигуру плоскостью. Режим «Сечение» показывает плоскость, проходящую через центр, ось $x_1$ и диагональное направление $(0, 1, \dots, 1)$. В ней куб выглядит прямоугольником $4 \times 4\sqrt{n-1}$ — он вытягивается вдоль диагонали. Ровно четыре угловых шара имеют центры в этой плоскости (у них $x_2 = \dots = x_n$) и высекают на ней единичные круги, а все остальные проходят мимо: ближайший из них удалён от плоскости на $2\sqrt{(n-2)/(n-1)} > 1$. Центральный шар высекает круг радиуса $\sqrt{n} - 1$, и при $n \ge 10$ видно, как он вылезает из прямоугольника через боковые стороны.

Попробуйте

При $n = 3$ покрутите кубик: розовый шар в середине едва виден между восемью голубыми. Потом переключитесь на «Сечение» и тяните размерность: при $n = 4$ все круги равны, при $n = 9$ розовый касается сторон, при $n = 10$ выходит наружу.

Всё почти перпендикулярно

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

Теорема

Пусть $u$ и $v$ — независимые случайные единичные векторы в $\mathbb{R}^n$, равномерно распределённые по сфере, и $\theta$ — угол между ними. Тогда $$\mathbb{E}[\cos\theta] = 0,\quad \mathbb{E}[\cos^2\theta] = \frac{1}{n}.$$ Поэтому $\cos\theta$ отклоняется от нуля в среднем на $1/\sqrt{n}$, а угол близок к $90°$ с разбросом около $1/\sqrt{n}$ радиан, то есть $57{,}3°/\sqrt{n}$.

Распределение $v$ не меняется при поворотах, поэтому можно повернуть всё так, чтобы $u$ стал вектором $e_1 = (1, 0, \dots, 0)$. Тогда $\cos\theta = \langle u, v\rangle = v_1$. Замена $v \to -v$ не меняет распределения, поэтому $\mathbb{E}[v_1] = 0$. Далее, $v_1^2 + v_2^2 + \dots + v_n^2 = 1$ всегда, а по симметрии все $\mathbb{E}[v_i^2]$ равны. Значит, каждое из них равно $1/n$. Наконец, при малом $\cos\theta$ угол $\theta \approx \pi/2 - \cos\theta$, поэтому разброс угла примерно равен разбросу косинуса. ∎

Для $n = 1000$ это $90° \pm 1{,}8°$. Хвосты здесь, как и у экватора, гауссовы: $P(|\cos\theta| \ge \varepsilon) \le 2e^{-n\varepsilon^2/2}$. Отсюда удивительное следствие. Строго перпендикулярных направлений в $\mathbb{R}^n$ не больше $n$, а почти перпендикулярных (с $|\cos\theta| < \varepsilon$) можно набрать экспоненциально много по $n$ — достаточно брать их наугад.

Похоже ведут себя расстояния. Возьмём две случайные точки $x, y$ единичного куба. Для каждой координаты $\mathbb{E}(x_i - y_i)^2 = \operatorname{Var}x_i + \operatorname{Var}y_i$, а дисперсия величины, равномерно распределённой на $[0, 1]$, равна $1/12$. Поэтому $\mathbb{E}(x_i - y_i)^2 = 1/6$ и $$\mathbb{E}\,|x - y|^2 = \frac{n}{6}.$$ Если досчитать до четвёртых моментов, выйдет, что дисперсия $|x-y|^2$ равна $7n/180$, а само расстояние равно $\sqrt{n/6}$ плюс-минус примерно $0{,}24$ — независимо от $n$. В тысячемерном кубе расстояние между двумя случайными точками почти всегда около $12{,}9 \pm 0{,}24$: все точки почти одинаково далеки друг от друга.

Слева — углы между случайными векторами. Пунктир — точная плотность, пропорциональная $\sin^{n-2}\theta$: при $n = 2$ она ровная, при $n = 3$ это синусоида, дальше — всё более узкий пик. Справа — расстояния, делённые на $\sqrt{n}$, с пиком у $1/\sqrt{6} \approx 0{,}408$. Внизу справа — отношение $(\max - \min)/\min$ для расстояний от одной случайной точки до двухсот других. На плоскости оно порядка десятков: ближайший сосед гораздо ближе самого дальнего. В тысяче измерений оно около $0{,}1$: ближайший и самый дальний отличаются на десять процентов.

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

Термин «проклятие размерности» ввёл Ричард Беллман в книге «Динамическое программирование» (1957). Он имел в виду самое прямое следствие: сетка с 10 узлами по каждой оси содержит $10^n$ узлов. Для $n = 10$ это десять миллиардов, для $n = 100$ — больше, чем атомов в наблюдаемой Вселенной (их оценивают примерно в $10^{80}$). Перебрать все варианты, построить таблицу, заполнить пространство примерами — в больших размерностях всё это невозможно.

Второе следствие тоньше: исчезает само понятие «окрестности». Пусть данные равномерно рассыпаны по единичному кубу, и мы хотим взять вокруг точки маленький кубик, в который попадёт 1 % данных. Его ребро должно быть $0{,}01^{1/n}$: на плоскости это $0{,}1$, в 10D уже $0{,}63$, в 100D — $0{,}955$. «Локальная» окрестность охватывает почти весь диапазон каждой координаты. А раз все расстояния почти равны, то и «ближайший сосед» теряет смысл. Это строго показали Бейер, Голдстейн, Рамакришнан и Шафт (1999): если относительный разброс расстояний стремится к нулю, то $(\max - \min)/\min \to 0$.

Почему же тогда машинное обучение вообще работает? Потому что реальные данные не рассыпаны по пространству равномерно. Фотографии лиц, тексты, звуки занимают крошечную часть своего пространства и обычно сосредоточены около множеств гораздо меньшей размерности. Всё сказанное выше относится к «типичным» точкам, а реальные данные нетипичны — в этом их ценность.

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

У концентрации есть и полезная сторона. Раз длина случайной проекции почти не колеблется, облако точек можно сжать в пространство гораздо меньшей размерности, почти не исказив расстояний. Это доказали Уильям Джонсон и Йорам Линденштраус в 1984 году.

Теорема

Пусть $0 < \varepsilon < 1$ и даны $N$ точек в $\mathbb{R}^n$. Если $$k \ge \frac{4\ln N}{\varepsilon^2/2 - \varepsilon^3/3},$$ то существует линейное отображение $f\colon \mathbb{R}^n \to \mathbb{R}^k$, при котором для любых двух точек $u, v$ набора расстояние $d = |u - v|$ и расстояние $d' = |f(u) - f(v)|$ между их образами связаны неравенствами $$(1-\varepsilon)\,d^2 \le d'^2 \le (1+\varepsilon)\,d^2 .$$

Возьмём случайную матрицу $A$ размером $k \times n$ с независимыми нормальными элементами дисперсии $1/k$. Для одного фиксированного вектора $x$ величина $|Ax|^2/|x|^2$ — среднее $k$ независимых квадратов стандартных нормальных величин. Её ожидание равно 1, а вероятность отклониться больше чем на $\varepsilon$ не превосходит $2e^{-k(\varepsilon^2/2 - \varepsilon^3/3)/2}$; при указанном $k$ это не больше $2/N^2$. Пар точек меньше $N^2/2$, поэтому вероятность, что исказится хоть одна пара, меньше единицы. Значит, подходящая матрица существует, и случайная годится с положительной вероятностью. Этот короткий вариант доказательства дали Дасгупта и Гупта (2003). ∎

Главное в формуле — то, чего в ней нет: $k$ не зависит от исходной размерности $n$. Миллион точек из пространства размерности $10^9$ можно уложить в несколько тысяч измерений: при $\varepsilon = 0{,}2$ формула даёт $k \approx 3200$, при $\varepsilon = 0{,}1$ — около $11\,800$. Константы в формуле осторожные, но сам порядок $\varepsilon^{-2}\log N$ улучшить нельзя: Ларсен и Нельсон в 2017 году доказали, что он оптимален. Случайные проекции по этому рецепту используют для быстрого поиска похожих объектов и в численной линейной алгебре.

Эмбеддинги: смысл как направление

Самое массовое применение многомерной геометрии сегодня — эмбеддинги, векторные представления слов, текстов и картинок. Модель превращает объект в список из сотен или тысяч чисел, и сходство объектов становится геометрией. Несколько конкретных размеров. Модель word2vec, обученная в Google на новостных текстах (Миколов и соавторы, 2013), даёт 300-мерные векторы для трёх миллионов слов и фраз. Скрытые векторы модели BERT-base 768-мерные, BERT-large — 1024-мерные. Современные модели для поиска по текстам выдают, например, 1536 или 3072 числа.

Сходство обычно меряют косинусом угла: $$\cos\theta = \frac{\langle a, b\rangle}{|a|\,|b|}.$$ Длина вектора часто отражает побочные свойства (например, частоту слова), а направление — смысл. Здесь и пригождается всё, что было выше. У двух случайных направлений в 768 измерениях косинус порядка $\pm 1/\sqrt{768} \approx \pm 0{,}036$, так что косинус $0{,}5$ — далеко не случайность. Знаменитый пример «король − мужчина + женщина ≈ королева» из работ Миколова тоже про направления: разность векторов кодирует отношение.

Две оговорки, чтобы не переоценить картину. Во-первых, реальные эмбеддинги не изотропны: у многих моделей векторы занимают узкий конус (это показал, в частности, Этаярадж в 2019 году), поэтому даже у несвязанных текстов косинус бывает заметно больше нуля. Абсолютные пороги вроде «сходство выше 0,8» нельзя переносить с модели на модель; надёжнее сравнивать, какой из вариантов ближе. Во-вторых, из-за концентрации расстояний точный поиск ближайших соседей плохо ускоряется: деревья поиска, которые прекрасно работают на плоскости, в сотнях измерений вырождаются почти в перебор. Поэтому в векторных базах данных используют приближённый поиск — например, графы HNSW (Малков и Яшунин, 2016), — жертвуя малой долей точности ради скорости.

Упаковки шаров и контактные числа

Контактное число — это наибольшее число одинаковых непересекающихся шаров, которые могут одновременно касаться такого же центрального шара. На прямой это 2, на плоскости 6: шесть монет вокруг седьмой. В трёх измерениях 12 шаров вокруг одного ставятся легко, и между ними остаётся столько свободного места, что их можно передвигать. Не влезет ли тринадцатый? В 1694 году в Кембридже этот вопрос обсуждали Исаак Ньютон и астроном Дэвид Грегори. По традиции считается, что Ньютон отвечал «12», а Грегори — «13»; запись Грегори, правда, допускает разные прочтения. Строгое доказательство, что ответ 12, дали Курт Шютте и Бартель ван дер Варден только в 1953 году, а короткий набросок — Джон Лич в 1956-м.

В четырёх измерениях ответ 24: шары ставятся в вершины 24-ячейника (его можно покрутить на витрине). Доказал это Олег Мусин: препринт появился в 2003 году, статья вышла в Annals of Mathematics в 2008-м. Дальше — чудо. В восьми измерениях контактное число равно 240, в двадцати четырёх — 196 560; эти значения в 1979 году независимо доказали Эндрю Одлыжко с Нилом Слоаном и Владимир Левенштейн. Расположения шаров там единственны и задаются исключительными решётками: $E_8$ и решёткой Лича. А в пятимерном пространстве ответ до сих пор неизвестен: он где-то между 40 и 44. Точно контактные числа известны только в размерностях 1, 2, 3, 4, 8 и 24. Нижние оценки в других размерностях продолжают улучшать: в 2024 году Генри Кон и Аньци Ли продвинулись в размерностях 17–21, а в 2025–2026 годах к поиску подключились и программы с ИИ.

Близкая задача — о плотнейшей упаковке: какую наибольшую долю пространства можно заполнить одинаковыми непересекающимися шарами.

размерностьконтактное числоплотнейшая упаковкаплотность
26шестиугольная$\pi/\sqrt{12} \approx 0{,}907$
312как у пирамиды апельсинов (гипотеза Кеплера; Хейлс, 1998–2005)$\pi/\sqrt{18} \approx 0{,}740$
424не доказано
8240решётка $E_8$ (Вязовская, 2016)$\pi^4/384 \approx 0{,}254$
24196 560решётка Лича (Кон, Кумар, Миллер, Радченко, Вязовская, 2016)$\pi^{12}/12! \approx 0{,}0019$

Гипотезу Кеплера о трёхмерной упаковке доказал Томас Хейлс: доказательство объявлено в 1998 году, опубликовано в 2005-м, а полная компьютерная проверка (проект Flyspeck) завершена в 2014-м. Доказательства для 8 и 24 измерений оказались гораздо короче. В марте 2016 года Марина Вязовская доказала, что $E_8$ даёт плотнейшую упаковку в восьми измерениях, и через неделю вместе с Коном, Кумаром, Миллером и Радченко перенесла метод на 24 измерения. Ключом стала специальная функция, построенная из модулярных форм, — та самая «волшебная» функция, существование которой предполагали Кон и Элкис. В 2022 году Вязовская получила за эту работу Филдсовскую медаль. В 2026 году оба доказательства были полностью формализованы в системе проверки доказательств Lean.

Обратите внимание на столбец плотности: она быстро падает. Это та же история, что с шаром, вписанным в куб: шары в больших размерностях «тощие», и между ними неизбежно остаётся почти всё пространство. Эти задачи не только красивы. Кодирование сообщений для передачи по каналу с шумом — та же упаковка: каждое сообщение — точка многомерного пространства, шум сдвигает её в пределах маленького шара, и шары разных сообщений не должны пересекаться. Такую геометрическую картину предложил Клод Шеннон в 1949 году.

Главное

В больших размерностях почти всё сосредоточено: объём шара — у поверхности и у любого экватора, углы между случайными векторами — около $90°$, расстояния между случайными точками — около одного значения. Это мешает (проклятие размерности), но и помогает: случайные проекции сохраняют расстояния, а направления эмбеддингов хорошо различимы.

Итоги

  • Объём $n$-мерного шара в слое толщиной $\varepsilon$ у поверхности составляет $1-(1-\varepsilon)^n$; при больших $n$ шар — почти одна кожура.
  • Для случайной точки шара $\mathbb{E}[x_1^2] = 1/(n+2)$, поэтому почти весь объём лежит и у любого экватора.
  • В кубе $[-2,2]^n$ шар между $2^n$ угловыми шарами имеет радиус $\sqrt{n}-1$ и при $n \ge 10$ выходит за грани куба.
  • Для случайных единичных векторов $\mathbb{E}[\cos^2\theta] = 1/n$: угол между ними — $90°$ с разбросом $57{,}3°/\sqrt{n}$. Расстояние между случайными точками куба близко к $\sqrt{n/6}$ с разбросом около $0{,}24$.
  • Проклятие размерности: сетки растут как $10^n$, окрестности перестают быть локальными, ближайший сосед теряет смысл.
  • Лемма Джонсона — Линденштрауса: $N$ точек можно линейно отобразить в $O(\varepsilon^{-2}\log N)$ измерений, исказив квадраты расстояний не больше чем в $1 \pm \varepsilon$ раз.
  • Контактные числа известны точно лишь в размерностях 1, 2, 3, 4, 8 и 24; плотнейшие упаковки доказаны в размерностях 2, 3, 8 и 24.

Дальше — где живут измерения: пространство-время, конфигурации роботов, цвет, данные и дополнительные измерения физиков.

Источники