Я. Гудфеллоу, И. Бенджио, А. Курвилль

5.11.1. Проклятие размерности
Многие алгоритмы машинного обучения резко усложняются, когда размерность дан-
ных велика. Это явление называется 
проклятием размерности
. Особенно неприятно, 
что количество возможных конфигураций множества переменных возрастает экспо-
ненциально с увеличением числа переменных.
Проклятие размерности возникает в разных разделах информатики, но особенно 
часто в машинном обучении.
Один из аспектов проклятия размерности связан со статистикой. На рис. 5.9 видно, 
что статистическая проблема возникает из-за того, что число возможных конфигура-
ций 
x
гораздо больше, чем число обучающих примеров. Чтобы разобраться, в чем тут 
дело, рассмотрим пространство входов, организованное в виде сетки, как на рисунке. 
Пространство низкой размерности можно описать небольшим числом ячеек сетки, 
по большей части занятых данными. При обобщении на новый пример мы обычно 
можем сказать, что делать, просто исследовав обучающие примеры, находящиеся 
в той же ячейке, что и новый. Например, в качестве оценки плотности вероятности 
в некоторой точке 
x
мы можем просто вернуть число обучающих примеров в том же 

---

142 

 
Основы машинного обучения 
единичном объеме, что и 
x
, поделенное на общее число обучающих примеров. Чтобы 
классифицировать пример, мы возвращаем класс большинства обучающих примеров 
в той же ячейке. В случае регрессии мы можем усреднить значения, наблюдавшиеся 
для примеров в этой ячейке. Но как быть с ячейками, для которых мы не видели ни 
одного примера? Поскольку в пространстве высокой размерности количество кон-
фигураций огромно – гораздо больше числа примеров, – в большинстве ячеек сетки 
обучающих примеров нет. И как можно сказать что-то осмысленное о новых конфи-
гурациях? В большинстве традиционных алгоритмов машинного обучения прос то 
предполагается, что выход в новой точке должен быть примерно таким же, как в бли-
жайшей обучающей точке.
Рис. 5.9 

С увеличением размерности данных (слева направо) коли-
чество представляющих интерес конфигураций растет экспоненциально. 
(
Слева
) В одномерном случае имеется одна переменная, и для нее всего 
10 интересных областей. При достаточном числе примеров, попадающих 
в каждую область (на рисунке область соответствует одной клетке), от ал-
горитма обучения легко добиться правильного обобщения. Самый прямо-
линейный способ – оценить значение метки в каждой области с возможной 
интерполяцией между соседними областями). (
В центре
) В двумерном слу-
чае уже труднее различить 10 разных значений каждой переменной. Нам 
приходится учитывать 10
×
10 = 100 областей, и, чтобы их все покрыть, нуж-
но, по крайней мере, столько же примеров. (
Справа
) В трехмерном случае 
число областей возрастает до 103 = 1000, и соответственно растет число 
примеров. Если имеется d измерений и нужно различать v значений вдоль 
каждой оси, то потребуется 
O
(
v
d
)
областей и примеров. Это и есть прокля-
тие размерности. Рисунок любезно предоставил Николас Чападос