Проклятие размерности
Материал из 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
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Проклятие размерности— проблема, связанная с увеличением количества данных в связи с ростом размерности пространства. Термин "проклятие размерности" был введен Ричардом Беллманом в 1961 году.
Содержание |
Проблемы
Проблема "проклятия размерности" часто возникает в машинном обучении, например, при применении метода ближайших соседей.
С ростом размерности пространства увеличивается количество параметров, описывающих систему (например, координаты).
Это влечет за собой следующие трудности:
- Трудоемкость вычислений
- Необходимость хранения огромного количества данных
- Увеличение доли шумов
Пример
Рассмотрим единичный интервал . 100 равномерно разбросанных точек будет достаточно, чтобы покрыть этот интервал с частотой не менее 0,01.
Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже точек. То есть по сравнению с одномерным пространством, требуется в
раз больше точек.
"Проклятие размерности" особенно проявляется при работе со сложными системами, которые описываются большим числом параметров.
Способы борьбы с "проклятием размерности"
Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности.
На этой идее, например, основан метод главных компонент.
Литература
- Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
- Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.