Проклятие размерностей – одна из крупнейших проблем Машинного обучения (Machine Learning), которая гласит: чем выше размерность, тем более разреженны данные. Иными словами, по мере роста количества признаков объем данных, которые нам нужно обобщить, растет экспоненциально.
Пример. Легко поймать гусеницу, движущуюся в трубе (1 размер). Собаку сложнее поймать, если она бегает по самолету (два измерения). Гораздо труднее охотиться на птиц, у которых теперь есть дополнительное измерение, в которое они могут перемещаться. Если мы представим призраков существами из более высоких измерений, их будет еще труднее поймать.
Еще пример. Предположим, у нас есть две точки на прямой, 0 и 1. Эти две точки находятся на расстоянии друг от друга, равном единице:
Теперь мы вводим вторую ось Y – второе измерение. Положение точек определяется теперь списком из двух чисел – (0,0) и (1,1). Расстояние между точками теперь подсчитывается с помощью Евклидова расстояния (Euclidian Distance). Помните извечный школьный способ вычисления гипотенузы – теорему Пифагора? Сумма квадратов длин катетов равна квадрату длины гипотенузы. Евклидово расстояние и вычисляется с помощью этого правила:
В двумерном пространстве наши точки выглядят следующим образом:
Расстояние увеличилось, и вместо 1 равно теперь примерно 1,41! В трехмерном пространстве две точки будут на расстоянии √3. К тому времени, когда мы достигнем 10-мерного пространства, две точки будут находиться на расстоянии более 3 целых (≈3,16) друг от друга. Посмотрите, как элегантно @residentmario иллюстрирует этот принцип с помощью Matplotlib:
Машинное обучение
Чтобы получить статистически обоснованный и надежный результат, экспоненциально наращивают количество данных, необходимых для подтверждения результата. Процесс часто базируется на обнаружении областей, в которых Наблюдения (Observation) образуют Кластеры (Cluster) со схожими свойствами. Однако в данных большой размерности все объекты кажутся разреженными и непохожими во многих отношениях, что мешает эффективно применять такие стратегии.
Если дистанционные метрики используются в наборе данных со слишком большим количеством измерений, все наблюдения (Observation) становятся примерно равноудаленными друг от друга. К примеру, метод K-средних (K-Means) использует меру расстояния для количественной оценки сходства между наблюдениями. Если все расстояния примерно равны, тогда все наблюдения кажутся одинаково похожими (или одинаково разными), и никакие значимые кластеры не могут быть сформированы.
Объем пространства увеличивается с невероятной скоростью относительно количества измерений. Даже 10 измерений могут стать "проклятием".Короче говоря, по мере роста числа измерений, Евклидово расстояние между точкой и ее ближайшим соседом, а также дальним соседом изменяется неочевидным образом.
Ноутбук, не требующий дополнительной настройки на момент написания статьи, можно скачать здесь.
Понравилась статья? Поддержите нас, поделившись статьей в социальных сетях и подписавшись на канал. И попробуйте наши курсы по Машинному обучению на Udemy.