Проклятие размерности
Материал из 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.
