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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{Задание|Allegra|Константин Воронцов|8 января 2010}})
Строка 1: Строка 1:
{{Задание|Allegra|Константин Воронцов|8 января 2010}}
{{Задание|Allegra|Константин Воронцов|8 января 2010}}
 +
 +
'''Проклятие размерности'''— проблема, связанная с увеличением количества данных в связи с ростом размерности пространства.
 +
Термин "проклятие размерности" был введен Ричардом Беллманом в 1961 году.
 +
 +
==Проблемы==
 +
Проблема "проклятия размерности" часто возникает в машинном обучении, например, при применении [[метод ближайших соседей|метода ближайших соседей]].
 +
 +
С ростом размерности пространства увеличивается количество параметров, описывающих систему (например, координаты).
 +
 +
Это влечет за собой следующие трудности:
 +
 +
* Трудоемкость вычислений
 +
* Необходимость хранения огромного количества данных
 +
* Увеличение доли шумов
 +
 +
==Пример==
 +
 +
Рассмотрим единичный интервал <tex>\[0,1\]</tex>. 100 равномерно разбросанных точек будет достаточно, чтобы покрыть этот интервал с частотой не менее 0,01.
 +
 +
Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже <tex>10^{20}</tex> точек. То есть по сравнению с одномерным пространством, требуется в <tex>10^{18}</tex> раз больше точек.
 +
 +
"Проклятие размерности" особенно проявляется при работе со сложными системами, которые описываются большим числом параметров.
 +
 +
==Способы борьбы с "проклятием размерности"==
 +
 +
Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности.
 +
 +
На этой идее, например, основан [[метод главных компонент]].
 +
 +
==Литература==
 +
 +
*Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
 +
 +
*Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.
 +
 +
==Ссылки==
 +
 +
*[http://www.chemie.uzh.ch/seminars/one_by_one/seminars/files/sparse_grids.pdf www.chemie.uzh.ch/seminars/one_by_one/seminars/files/sparse_grids.pdf]
 +
 +
*[http://www.galaxy.gmu.edu/ACAS/ACAS00-02/ACAS02ShortCourse/ACASCourse10.pdf www.galaxy.gmu.edu/ACAS/ACAS00-02/ACAS02ShortCourse/ACASCourse10.pdf]
 +
 +
[[Категория:Классификация]]
 +
[[Категория:Машинное обучение]]

Версия 23:57, 4 января 2010

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

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

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


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

Содержание

Проблемы

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

С ростом размерности пространства увеличивается количество параметров, описывающих систему (например, координаты).

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

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

Пример

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

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

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

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

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

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

Литература

  • Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
  • Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.

Ссылки

Источник — «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»
Личные инструменты