Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

  • Допустим, нам надо восстановить вероятностное распределение простейшей бинарной случайной величины, и с точностью, достаточной для поставленных целей, это можно сделать по выборке из измерений или наблюдений. Тогда для восстановления вероятностного распределения вектора из бинарных случайных величин с той же точностью потребуется выборка из измерений, что часто оказывается неприемлемым по материальным затратам или времени. А -мерный вектор бинарных величин имеет возможных значений и попытки прямолинейного восстановления его распределения по экспериментальной выборке бесперспективны.
  • В комбинаторике перебор вариантов на современных компьютерах также невозможен. Поэтому точные решения для NP-трудных и более сложных задач путём перебора можно искать только в случае, когда размер исходных данных исчисляется несколькими десятками вершин графа, требований, приборов и т. п. То, что некоторые игры с полной информацией, например шахматы, по сей день представляют интерес, есть следствие ПР.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Нетрудно убедиться, что, если задать любое положительное , то доля объёма многомерного куба или шара в -окрестности границы стремится к 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 года.
Эта страница в последний раз была отредактирована 27 октября 2023 в 15:06.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).