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