Геометрическая природа проблемы

Термин предложил американский математик Ричард Беллман в 1957 году, когда исследовал задачи динамического программирования и оптимизации. Суть явления кроется в фундаментальном свойстве геометрии многомерных пространств. При добавлении каждого нового измерения объем пространства растет экспоненциально, а плотность имеющихся данных стремительно падает к нулю.

Если для покрытия отрезка единичной длины с шагом в одну десятую требуется всего десять точек, то для аналогичного покрытия единичного квадрата нужно уже сто точек. В трехмерном кубе потребуется тысяча точек, а в пространстве из ста признаков понадобится число с сотней нулей. На практике обучающая выборка всегда ограничена сотнями, тысячами или миллионами строк. В многомерном пространстве эти точки оказываются изолированными друг от друга на огромных расстояниях, образуя пустоту.

Второе критическое свойство многомерных пространств связано с концентрацией расстояний. По мере роста числа измерений евклидово расстояние между любой случайной парой точек начинает выравниваться. Разница между дистанцией до ближайшего соседа и дистанцией до самого дальнего соседа стремится к нулю относительно общего расстояния. Алгоритмы, опирающиеся на метрики близости объектов, практически теряют способность различать соседей.

Последствия для моделей машинного обучения

Метрические алгоритмы страдают первыми. Метод k-ближайших соседей kNN полностью теряет предсказательную силу, поскольку концепция близости перестает работать. Любая тестовая точка оказывается примерно на одинаковом удалении от всех обучающих примеров, из-за чего классификация превращается в случайное угадывание.

Линейные модели и нейросети сталкиваются с жестким переобучением. Число настраиваемых весов растет пропорционально количеству входных признаков или квадратично для полносвязных слоев. Когда параметров становится больше, чем независимых наблюдений, модель запоминает случайный шум и специфические конфигурации обучающей выборки вместо поиска общих закономерностей. Ошибка на обучении стремится к нулю, а на валидации катастрофически растет.

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

Базовые стратегии борьбы с размерностью

В арсенале инженера машинного обучения есть два принципиально разных направления работы с раздутыми признаковыми пространствами. Первое направление сохраняет исходную природу признаков путем отсева лишнего, второе создает новые компактные координаты.

  • Отбор признаков через фильтрацию по дисперсии, корреляции с целевой переменной или показателю взаимной информации
  • Оберточные методы вроде рекурсивного исключения признаков RFE, оценивающие качество базовой модели на разных подмножествах столбцов
  • Встроенная регуляризация L1 Lasso, которая зануляет коэффициенты перед неинформативными переменными прямо во время обучения линейной модели
  • Проекция данных в пространство меньшей размерности с объединением скоррелированных признаков в синтетические компоненты

Метод главных компонент PCA

Метод главных компонент Principal Component Analysis относится к линейным алгоритмам снижения размерности без учителя. Математический аппарат PCA опирается на сингулярное разложение матриц или расчет собственных векторов ковариационной матрицы данных.

Алгоритм находит такое ортогональное направление в многомерном пространстве, вдоль которого дисперсия данных максимальна. Это направление становится первой главной компонентой. Затем строится второе направление, перпендикулярное первому, с максимальной оставшейся дисперсией. Процесс повторяется до достижения исходного числа измерений. После этого исследователь оставляет только первые k компонент, которые суммарно описывают, например, 90 или 95 процентов исходной вариативности.

Нелинейные методы: t-SNE и UMAP

Линейные методы вроде PCA бессильны, если данные лежат на сложном искривленном многообразии, свернутом в виде швейцарского рулета. Проекция такого многообразия на плоскость склеит между собой отдаленные слои. Для выявления нелинейных взаимосвязей разработаны вероятностные и топологические подходы.

Как устроен алгоритм t-SNE

Алгоритм t-distributed Stochastic Neighbor Embedding переводит евклидовы расстояния между точками в исходном пространстве в условные вероятности сходства с помощью нормального распределения Гаусса. Чем ближе точки, тем выше вероятность их соседства. Затем в пространстве низкой размерности, обычно двумерном или трехмерном, создается такое же вероятностное распределение, но с использованием распределения Стьюдента с одной степенью свободы.

Тяжелые хвосты распределения Стьюдента решают проблему скучивания данных, позволяя точкам из разных кластеров отталкиваться друг от друга. Алгоритм минимизирует дивергенцию Кульбака — Лейблера между двумя распределениями методом градиентного спуска. Метод t-SNE превосходно визуализирует кластеры в задачах анализа текстов, биоинформатики и распознавания изображений, однако не сохраняет глобальные расстояния между далекими группами и требует больших вычислительных затрат.

Альтернатива в виде UMAP

Uniform Manifold Approximation and Projection опирается на строгий аппарат римановой геометрии и алгебраической топологии. Метод UMAP работает значительно быстрее классического t-SNE, масштабируется на выборки из миллионов объектов и заметно лучше удерживает глобальную структуру данных при сжатии.

Частые вопросы

Можно ли использовать t-SNE для подготовки признаков перед обучением модели?

Обычно t-SNE используют только для визуализации и исследовательского анализа. Алгоритм не создает математической функции отображения для новых точек, поэтому спроецировать тестовую выборку без полного повторного пересчета всей матрицы невозможно. Для генерации признаков лучше подходят PCA, UMAP или автоэнкодеры.

Чем автоэнкодер отличается от классического PCA?

Линейный автоэнкодер без функций активации эквивалентен методу главных компонент. Добавление нелинейных слоев в нейросеть позволяет автоэнкодеру сжимать данные со сложной структурой взаимосвязей, превосходя классический PCA по сохранению полезной информации.

Как понять, что модель пострадала именно от проклятия размерности?

Главный признак заключается в резком разрыве между идеальным качеством на обучении и низкими метриками на тестовых данных при наличии сотен колонок. Также подозрение вызывает падение точности метрических алгоритмов при добавлении новых непроверенных признаков.

Сколько наблюдений должно приходиться на один признак?

В статистике и классическом машинном обучении ориентируются на эмпирическое правило одного к десяти. На каждый входной параметр желательно иметь как минимум десять независимых строк обучающей выборки для уверенной оценки коэффициентов.