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