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

Проклятие размерности (ПР) — термин, используемый в отношении ряда свойств многомерных пространств и комбинаторных задач. В первую очередь это касается экспоненциального роста необходимых экспериментальных данных в зависимости от размерности пространства при решении задач вероятностно-статистического распознавания образов, машинного обучения, классификации и дискриминантного анализа. Также это касается экспоненциального роста числа вариантов в комбинаторных задачах в зависимости от размера исходных данных, что приводит к соответствующему росту сложности переборных алгоритмов. «Проклятие» действует и на непрерывные оптимизационные методы в силу усложнения многомерной целевой функции. В более широком смысле термин применяется по отношению ко всем «неудобным» или необычным свойствам многомерных пространств и к трудностям их исследования. В комбинаторике чаще имеют в виду не размерность пространства, а размер исходных данных. В частности, в задачах теории Рамсея было бы точнее говорить о ’’’проклятии размера’’’ исходных данных даже в случае задач минимальной размерности — числа параметров, определяющих задачу. Впервые термин ввел Ричард Беллман применительно к общей задаче динамического программирования^[1][2]. Это выражение продолжает употребляться в работах по технической кибернетике, машинному обучению и анализу сложных систем, в том числе, в заголовках научных статей^[3].

Типичные примеры

• Допустим, нам надо восстановить вероятностное распределение простейшей бинарной случайной величины, и с точностью, достаточной для поставленных целей, это можно сделать по выборке из ${\displaystyle 200=2\cdot 100}$ измерений или наблюдений. Тогда для восстановления вероятностного распределения вектора из ${\displaystyle 10}$ бинарных случайных величин с той же точностью потребуется выборка из ${\displaystyle 2^{10}\cdot 100>10^{5}}$ измерений, что часто оказывается неприемлемым по материальным затратам или времени. А ${\displaystyle 100}$-мерный вектор бинарных величин имеет ${\displaystyle 2^{100}>10^{30}}$ возможных значений и попытки прямолинейного восстановления его распределения по экспериментальной выборке бесперспективны.
• В комбинаторике перебор ${\displaystyle 2^{100}}$ вариантов на современных компьютерах также невозможен. Поэтому точные решения для NP-трудных и более сложных задач путём перебора можно искать только в случае, когда размер исходных данных исчисляется несколькими десятками вершин графа, требований, приборов и т. п. То, что некоторые игры с полной информацией, например шахматы, по сей день представляют интерес, есть следствие ПР.

В задачах распознавания

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

1. Возможна ситуация, когда распределение вектора взаимозависимых случайных величин сосредоточено в подпространстве меньшей размерности, то есть вектор может быть хорошо приближен линейной функцией меньшего числа переменных. В этом случае метод главных компонент позволяет снизить размерность. Далее поставленные задачи распознавания (дискриминации) могут решаться уже в пространстве малой размерности.
2. Возможна ситуация, когда случайные величины исследуемых векторов независимы или, что более реально, слабо взаимозависимы. В этом случае можно восстановить одномерные распределения случайных величин и построить многомерные распределения как их произведения. Далее, используя ту же обучающую выборку в режиме скользящего экзамена можно восстановить одномерное распределение отношения функций правдоподобия дифференцируемых классов, что устраняет смещения, связанные с взаимозависимостью в решающем правиле.

Обычно для анализа многомерных данных предлагают использовать метрический метод ближайшего соседа^{[4] [5]}. Достоинство метода состоит в том, что формально он может применяться к выборкам любого объёма независимо от размерности векторов. Но принципиально прикладная проблема ПР состоит в том, что в ограниченной выборке данных недостаточно информации об объекте, описываемом большим числом значимых параметров. И если это описание является действительно сложным и многомерным, а для решения задачи требуется анализ всего комплекса параметров, то проблема оказывается трудной и не решается общими методами.

Задачи оптимизации

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

• В дискретных переборных задачах оптимизации время работы алгоритмов можно сократить с помощью метода ветвей и границ и приближённых эвристических алгоритмов (смотри Приближенная схема полиномиального времени).
• В оптимизационном методе градиентного спуска для некоторых целевых функций многих переменных существенно повышает эффективность метод оврагов.^[6]

Все указанные методы борьбы не решают проблему ПР кардинально и эффективны только в частных случаях.

В теории Рамсея

Хотя задачи теории Рамсея обычно допускают многомерные обобщения, они являются трудными даже при минимальных размерностях и небольших размерах исходных данных.

• В частности не известно число Рамсея R(5,5) − минимальный размер группы людей, в которой обязательно найдётся группа из 5 человек либо попарно знакомых, либо попарно незнакомых друг с другом. Пал Эрдёш заметил, что в случае крайней необходимости человечество могло бы решить эту задачу, сосредоточив на ней лучшие умы и вычислительные мощности. Но определение числа R(6,6) современному человечеству не под силу^[7].
• Гипотеза Секереша — Эрдёша о многоугольниках, которая одновременно является задачей комбинаторной геометрии и задачей теории Рамсея, также не доказана по сей день даже в исходной двумерной постановке задачи.

В комбинаторной геометрии

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

• Наиболее ярким примером является проблема Нелсона — Эрдёша — Хадвигера о хроматическом числе метрических пространств. На сегодняшний день (2013 г.) это число не известно даже для евклидова пространства размерности 2. Известно только, что хроматическое число плоскости находится в отрезке [5,7]^[8]. С другой стороны для этой задачи удалось доказать экспоненциальный порядок роста хроматического числа при больших размерностях пространства.
• Другой трудной задачей является проблема Борсука. Гипотеза Борсука на сегодняшний день доказана для пространств размерности не больше 3 и опровергнута для пространств размерности не менее 65. Таким образом, вопрос остаётся нерешённым для большого отрезка размерностей пространств. В этой задаче не доказан даже предполагаемый экспоненциальный рост необходимого числа частей разбиения.

Некоторые «необычные» свойства многомерных пространств

• Нетрудно убедиться, что, если задать любое положительное ${\displaystyle \varepsilon }$, то доля объёма многомерного куба или шара в ${\displaystyle \varepsilon }$-окрестности границы стремится к 1 при неограниченном увеличении размерности. Таким образом, в многомерных телах большая часть объёма находится «рядом» с границей. Поэтому точки даже больших экспериментальных выборок, как правило, являются граничными — лежат либо на выпуклой оболочке множества, либо близко от неё.
• Согласно ЦПТ, вероятность, что два случайных вектора будут нормальны, в пределах любой наперёд заданной положительной ошибки, стремится к 1 с ростом размерности пространства.

Примечания

1. Richard Ernest Bellman; Rand Corporation. Dynamic programming (неопр.). — Princeton University Press, 1957. — ISBN 978-0-691-07951-6.,
   Republished: Richard Ernest Bellman. Dynamic Programming (неопр.). — Courier Dover Publications, 2003. — ISBN 978-0-486-42809-3.
2. Richard Ernest Bellman. Adaptive control processes: a guided tour (англ.). — Princeton University Press, 1961.
3. Powell, Warren B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, ISBN 0-470-17155-3.
4. Marimont, R.B.; Shapiro, M.B. Nearest Neighbour Searches and the Curse of Dimensionality (англ.) // IMA J Appl Math^[англ.] : journal. — 1979. — Vol. 24, no. 1. — P. 59—70. — doi:10.1093/imamat/24.1.59. Архивировано 12 февраля 2014 года.
5. Radovanović, Miloš; Nanopoulos, Alexandros; Ivanović, Mirjana. Hubs in space: Popular nearest neighbors in high-dimensional data (англ.) // Journal of Machine Learning Research : journal. — 2010. — Vol. 11. — P. 2487—2531. Архивировано 17 июля 2019 года.
6. НОУ ИНТУИТ | Лекция | Метод наискорейшего спуска. Метод Давидона – Флетчера – Пауэлла. Проблема оврагов. Проблема многоэкстремальности  (неопр.). Дата обращения: 26 апреля 2022. Архивировано 27 декабря 2016 года.
7. Joel H. Spencer (1994), Ten Lectures on the Probabilistic Method, SIAM, p. 4, ISBN 978-0-89871-325-1
8. Aubrey D.N.J. DE Grey. The chromatic number of the plane is at least 5 // math.CO. — 2018. Архивировано 12 июля 2018 года.