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

Материал из MachineLearning.

Перейти к: навигация, поиск
Данная статья является непроверенным учебным заданием.
Студент: Участник:Allegra
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Проклятие размерности — проблема, связанная с увеличением количества данных из-за роста размерности пространства. Термин "проклятие размерности" был введен Ричардом Беллманом в 1961 году.

Проблема "проклятия размерности" часто возникает в машинном обучении, например, при применении метода ближайших соседей.

Содержание

Проблемы

"Проклятие размерности" особенно явно проявляется при работе со сложными системами, которые описываются большим числом параметров.

Это влечет за собой следующие трудности:

  • Трудоемкость вычислений
  • Необходимость хранения огромного количества данных
  • Увеличение доли шумов

Пример

Рассмотрим единичный интервал [0,1]. 100 равномерно разбросанных точек будет достаточно, чтобы покрыть этот интервал с частотой не менее 0,01.

Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже 1020 точек. То есть, по сравнению с одномерным пространством, требуется в 1018 раз больше точек.

Поэтому, например, использование переборных алгоритмов становится неэффективным при возрастании размерности системы.

Способы борьбы с "проклятием размерности"

Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности.

На этой идее, например, основан метод главных компонент.

Литература

  • Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
  • Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.
  • Beyer, K. 1999. When Is "Nearest Neighbor" Meaningful? Int. Conf. on Database Theory.
  • Powell, Warren B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, ISBN 0470171553.

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D0%BA%D0%BB%D1%8F%D1%82%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8»
Личные инструменты