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

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

(Различия между версиями)
Перейти к: навигация, поиск
 
(3 промежуточные версии не показаны)
Строка 1: Строка 1:
{{Задание|Allegra|Константин Воронцов|8 января 2010}}
{{Задание|Allegra|Константин Воронцов|8 января 2010}}
-
'''Проклятие размерности''' — проблема, связанная с увеличением количества данных из-за роста размерности пространства.
+
'''Проклятие размерности''' — проблема, связанная с экспоненциальным возрастанием количества данных из-за увеличения размерности пространства.
-
Термин "проклятие размерности" был введен Ричардом Беллманом в 1961 году.
+
Термин «проклятие размерности» был введен Ричардом Беллманом в 1961 году.
-
Проблема "проклятия размерности" часто возникает в машинном обучении, например, при применении [[метод ближайших соседей|метода ближайших соседей]].
+
Проблема «проклятия размерности» часто возникает в машинном обучении, например, при применении [[метод ближайших соседей|метода ближайших соседей]] и [[метод парзеновского окна|метода парзеновского окна]].
==Проблемы==
==Проблемы==
-
"Проклятие размерности" особенно явно проявляется при работе со сложными системами, которые описываются большим числом параметров.
+
«Проклятие размерности» особенно явно проявляется при работе со сложными системами, которые описываются большим числом параметров.
Это влечет за собой следующие трудности:
Это влечет за собой следующие трудности:
Строка 15: Строка 15:
* Необходимость хранения огромного количества данных
* Необходимость хранения огромного количества данных
* Увеличение доли шумов
* Увеличение доли шумов
-
 
+
* В [[линейный классификатор|линейных классификаторах]] увеличение числа признаков ведет к проблемам [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]].
 +
* В [[метрический классификатор|метрических классификаторах]] расстояния обычно вычисляются как средний модуль разностей по всем признакам. Согласно [[Закон больших чисел|Закону Больших Чисел]], сумма n слагаемых стремится в некоторому фиксированному пределу при n→∞. Таким образом, расстояния во всех парах объектов стремятся к одному и тому же значению, а значит, становятся неинформативными.
==Пример==
==Пример==
Строка 24: Строка 25:
Поэтому, например, использование переборных алгоритмов становится неэффективным при возрастании размерности системы.
Поэтому, например, использование переборных алгоритмов становится неэффективным при возрастании размерности системы.
-
==Способы борьбы с "проклятием размерности"==
+
==Способы устранения «проклятия размерности»==
Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности.
Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности.
На этой идее, например, основан [[метод главных компонент]].
На этой идее, например, основан [[метод главных компонент]].
 +
 +
Также можно осуществлять [[отбор признаков]] и использовать [[алгоритм вычисления оценок]].
==Литература==
==Литература==
Строка 35: Строка 38:
*Bellman, R.E. 1961. Adaptive Control Processes. 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.
==Ссылки==
==Ссылки==

Текущая версия

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

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

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


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

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

Содержание

Проблемы

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

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

  • Трудоемкость вычислений
  • Необходимость хранения огромного количества данных
  • Увеличение доли шумов
  • В линейных классификаторах увеличение числа признаков ведет к проблемам мультиколлинеарности и переобучения.
  • В метрических классификаторах расстояния обычно вычисляются как средний модуль разностей по всем признакам. Согласно Закону Больших Чисел, сумма n слагаемых стремится в некоторому фиксированному пределу при n→∞. Таким образом, расстояния во всех парах объектов стремятся к одному и тому же значению, а значит, становятся неинформативными.

Пример

Рассмотрим единичный интервал [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.

Ссылки

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