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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
{{Задание|Allegra|Константин Воронцов|8 января 2010}}
{{Задание|Allegra|Константин Воронцов|8 января 2010}}
-
'''Проклятие размерности''' — проблема, связанная с увеличением количества данных в связи с ростом размерности пространства.
+
'''Проклятие размерности''' — проблема, связанная с увеличением количества данных из-за роста размерности пространства.
Термин "проклятие размерности" был введен Ричардом Беллманом в 1961 году.
Термин "проклятие размерности" был введен Ричардом Беллманом в 1961 году.
-
==Проблемы==
 
Проблема "проклятия размерности" часто возникает в машинном обучении, например, при применении [[метод ближайших соседей|метода ближайших соседей]].
Проблема "проклятия размерности" часто возникает в машинном обучении, например, при применении [[метод ближайших соседей|метода ближайших соседей]].
-
С ростом размерности пространства увеличивается количество параметров, описывающих систему (например, координаты).
+
==Проблемы==
 +
 
 +
"Проклятие размерности" особенно явно проявляется при работе со сложными системами, которые описываются большим числом параметров.
Это влечет за собой следующие трудности:
Это влечет за собой следующие трудности:
Строка 21: Строка 22:
Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже 10<sup>20</sup> точек. То есть, по сравнению с одномерным пространством, требуется в 10<sup>18</sup> раз больше точек.
Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже 10<sup>20</sup> точек. То есть, по сравнению с одномерным пространством, требуется в 10<sup>18</sup> раз больше точек.
-
"Проклятие размерности" особенно явно проявляется при работе со сложными системами, которые описываются большим числом параметров.
+
Поэтому, например, использование переборных алгоритмов становится неэффективным при возрастании размерности системы.
==Способы борьбы с "проклятием размерности"==
==Способы борьбы с "проклятием размерности"==

Версия 00:20, 5 января 2010

Данная статья является непроверенным учебным заданием.
Студент: Участник: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.

Ссылки

Личные инструменты