Что такое «проклятие размерности»?

Многие алгоритмы обработки данных трактуют набор информации об объекте (набор значений "признаков") как вектор в многомерном пространстве. Размерность данного пространства соответствует количеству различных признаков, описывающих объект.

Размерность варьируется от задачи к задаче:

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

В чуть более сложных случаях, мы можем использовать десятки или даже сотни признаков. К примеру, когда оцениваем вероятность того, что человек вернёт взятый в банке кредит. В таком случае, нам может быть полезна информация о размере кредита, о доходе, возрасте, поле, семейному статусе клиента (и проч.).

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

Каждое из изображений имеет какой-то размер (разрешение) в пикселях. К примеру, Full HD имеет размер 1920 на 1080 пикселей. Общее количество пикселей - 1920 * 1080 ~ 2'000'000. Два миллиона пикселей, каждый из которых содержит определённое количество значений. Для простоты допустим, что в каждом из пикселей у нас хранится только одно значение. В любом случае, размерность пространства на порядки превышает описанные выше ситуации.

(Если интересно, можете прикинуть порядок размерности пространства, в котором располагаются десятиминутные 4K 60 FPS ролики)

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

В качестве примера, можно привести метод K Nearest Neighbors (KNN). Суть его заключается в том, что при предсказании для некого x0 используются "ответы" для ранее увиденных объектов x1, x2...xK, "похожих" на x0. Для оценки сходства используются различные метрики: L1, L2, cosine distance... Не буду углубляться в математику, Вы можете сделать это самостоятельно. Вернусь к сути.

Ниже прикреплены три изображения:

Алгоритм KNN предположит, что на третьем изображении - суслик, а не хомяк. Причина - второе изображение сильнее похоже на третье, чем первое: на втором и третьем преобладает жёлтоватый цвет, тогда как на первом немалую часть занимает зелёный цвет. Однако понятно, что если сконцентрировать внимание на самом животном, а не фоне, на третьем изображении скорее всего изображён хомяк (то же животное, что и на первом изображении, если абстрагироваться от наших знаний).

В данном случае, проявлением проклятия размерности было то, что алгоритм уделил слишком много внимания малополезным признакам. Вариантов проклятий размерности довольно много, и основывается оно на том, что многомерное пространство довольно странно и контр-интуитивно. Рекомендую всем заинтересованным ознакомиться с первой главой данной книги.