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

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

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

Проблемы

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

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

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

Пример

Рассмотрим единичный интервал [0,1]. 100 равномерно разбросанных точек будет достаточно, чтобы покрыть этот интервал с частотой не менее 0,01.

Теперь рассмотрим 10-мерный куб. Для достижения той же степени покрытия потребуется уже 10²⁰ точек. То есть, по сравнению с одномерным пространством, требуется в 10¹⁸ раз больше точек.

Поэтому, например, использование переборных алгоритмов становится неэффективным при возрастании размерности системы.

Способы устранения «проклятия размерности»

Основная идея при решении проблемы — понизить размерность пространства, а именно спроецировать данные на подпространство меньшей размерности.

На этой идее, например, основан метод главных компонент.

Также можно осуществлять отбор признаков и использовать алгоритм вычисления оценок.

Ссылки

machinelearning