Проклятие размерностей (Curse of Dimensionality)

Проклятие размерностей – одна из крупнейших проблем Машинного обучения (Machine Learning), которая гласит: чем выше размерность, тем более разреженны данные. Иными словами, по мере роста количества признаков объем данных, которые нам нужно обобщить, растет экспоненциально.

Пример. Легко поймать гусеницу, движущуюся в трубе (1 размер). Собаку сложнее поймать, если она бегает по самолету (два измерения). Гораздо труднее охотиться на птиц, у которых теперь есть дополнительное измерение, в которое они могут перемещаться. Если мы представим призраков существами из более высоких измерений, их будет еще труднее поймать.

Еще пример. Предположим, у нас есть две точки на прямой, 0 и 1. Эти две точки находятся на расстоянии друг от друга, равном единице:

Теперь мы вводим вторую ось Y – второе измерение. Положение точек определяется теперь списком из двух чисел – (0,0) и (1,1). Расстояние между точками теперь подсчитывается с помощью Евклидова расстояния. Помните извечный школьный способ вычисления гипотенузы – теорему Пифагора? Сумма квадратов длин катетов равна квадрату длины гипотенузы. Евклидово расстояние и вычисляется с помощью этого правила:

$$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} = \sqrt{(1 - 0)^2 + (1 - 0)^2} = \sqrt{2} ≈ 1,414, где$$
$$d\space{–}\space{расстояние}\space{между}\space{точками,}$$
$$x_1,\space{x_2}\space{–}\space{координаты}\space{точек}\space{по}\space{оси}\space{X,}$$
$$y_1,\space{y_2}\space{–}\space{координаты}\space{точек}\space{по}\space{оси}\space{Y.}$$

В двумерном пространстве наши точки выглядят следующим образом:

Расстояние увеличилось, и вместо 1 равно теперь примерно 1,41! В трехмерном пространстве две точки будут на расстоянии √3. К тому времени, когда мы достигнем 10-мерного пространства, две точки будут находиться на расстоянии более 3 целых (≈3,16) друг от друга. Посмотрите, как элегантно @residentmario иллюстрирует этот принцип с помощью Matplotlib:

import matplotlib.pyplot as plt
import numpy as np

plt.style.use('fivethirtyeight') # Стиль графика

plt.figure(figsize = (12, 6)) # Размер полотна
plt.title("Евклидово расстояние для $[0]^{1 x n}$ и $[1]^{1 x n}$, если $n \in \{1, \ldots, 10\}$") 
plt.xlabel('$n$')
plt.ylabel('$|| x - y ||_2$')
plt.plot(range(1, 10), np.sqrt(range(1, 10)))

Машинное обучение

Чтобы получить статистически обоснованный и надежный результат, экспоненциально наращивают количество данных, необходимых для подтверждения результата. Процесс часто базируется на обнаружении областей, в которых Наблюдения (Observation) образуют Кластеры (Cluster) со схожими свойствами. Однако в данных большой размерности все объекты кажутся разреженными и непохожими во многих отношениях, что мешает эффективно применять такие стратегии.

Если дистанционные метрики, такие как Евклидово расстояние (Euclidean Distance), используются в наборе данных со слишком большим количеством измерений, все наблюдения (Observation) становятся примерно равноудаленными друг от друга. К примеру, метод K-средних (K-Means) использует меру расстояния для количественной оценки сходства между наблюдениями. Если все расстояния примерно равны, тогда все наблюдения кажутся одинаково похожими (или одинаково разными), и никакие значимые кластеры не могут быть сформированы.

Объем пространства увеличивается с невероятной скоростью относительно количества измерений. Даже 10 измерений могут стать "проклятием".
Короче говоря, по мере роста числа измерений, Евклидово расстояние между точкой и ее ближайшим соседом, а также дальним соседом изменяется неочевидным образом.

Ноутбук, не требующий дополнительной настройки на момент написания статьи, можно скачать здесь.

Фото: @eprouzet