Использование метода Монте-Карло для визуализации поведения наблюдений с очень большим количеством признаков.
Подумайте о наборе данных, состоящем из некоторого количества наблюдений, каждое из которых имеет N признаков. Если вы преобразуете все функции в числовое представление, вы можете сказать, что каждое наблюдение является точкой в N-мерном пространстве.
Когда N низкое, отношения между точками такие, какие вы интуитивно ожидаете. Но иногда N становится очень большим — это может случиться, например, если вы создаете много признаков с помощью одноразового кодирования и т. д. При очень больших значениях N наблюдения ведут себя так, как если бы они были разреженными, или как если бы расстояния между ними как-то больше, чем вы ожидаете.
Явление реальное. По мере того, как число измерений N растет, а все остальное остается прежним, N-объем, содержащий ваши наблюдения, действительно в некотором смысле увеличивается (или, по крайней мере, увеличивается число степеней свободы), и евклидовы расстояния между наблюдениями также увеличиваются. . Группа точек действительно становится более разреженной. Это геометрическая основа проклятия размерности. Эти изменения повлияют на поведение моделей и методов, применяемых к набору данных.
Многое может пойти не так, если количество функций очень велико. Наличие большего количества функций, чем наблюдений, является типичной установкой для переобучения моделей при обучении. Любой поиск методом грубой силы в таком пространстве (например, GridSearch) становится менее эффективным — вам нужно больше попыток, чтобы покрыть те же пределы линейного интервала. Слабый эффект влияет на любые модели, основанные на расстоянии или близости: поскольку количество измерений возрастает до очень больших значений, если вы рассматриваете какую-либо точку в своих наблюдениях, все остальные точки кажутся далекими и каким-то образом почти равноудалены — поскольку эти модели полагаются на расстояние, чтобы выполнить свою работу, выравнивание различий в расстоянии усложняет их работу. Например. кластеризация не работает, если все точки кажутся почти равноудаленными.
По всем этим и многим другим причинам были созданы такие методы, как PCA, LDA и т. д. — в попытке отойти от специфической геометрии пространств с очень многими измерениями и сократить набор данных до нескольких измерений. соответствует фактической информации, содержащейся в нем.
Интуитивно понять истинную величину этого явления сложно, а пространства с более чем тремя измерениями крайне сложно визуализировать, поэтому давайте проведем несколько простых 2D-визуализаций, чтобы помочь нашей интуиции. Причина, по которой размерность может стать проблемой, имеет геометрическую основу, и именно ее мы здесь и представим. Если вы не видели этого раньше, результаты могут вас удивить — геометрия многомерных пространств гораздо сложнее, чем может подсказать типичная интуиция.
Объем
Рассмотрим квадрат размера 1 с центром в начале координат. В квадрат вы вписываете круг.
Это установка в 2-х измерениях. Теперь подумайте в общем, N-мерном случае. В трех измерениях у вас есть сфера, вписанная в куб. Кроме того, у вас есть N-сфера, вписанная в N-куб, что является наиболее общим способом выразить это. Для простоты мы будем называть эти объекты «сферой» и «кубом», независимо от того, сколько у них измерений.
Объем куба фиксирован, он всегда равен 1. Вопрос в следующем: при изменении числа измерений N что происходит с объемом сферы?
Ответим на вопрос экспериментально, используя метод Монте-Карло. Мы будем генерировать очень большое количество точек, распределенных равномерно, но случайным образом внутри куба. Для каждой точки вычисляем ее расстояние до начала координат — если это расстояние меньше 0,5 (радиус сферы), то точка находится внутри сферы.
Если мы разделим количество точек внутри сферы на общее количество точек, это приблизит отношение объема сферы к объему куба. Поскольку объем куба равен 1, отношение будет равно объему сферы. Аппроксимация становится лучше, когда общее количество точек велико.
Другими словами, отношение inside_points / total_points будет аппроксимировать объем сферы.
Код довольно прост. Поскольку нам нужно много точек, следует избегать явных циклов. Мы могли бы использовать NumPy, но он использует только процессор и является однопоточным, поэтому он будет медленным. Возможные альтернативы: CuPy (GPU), Jax (CPU/GPU), PyTorch (CPU/GPU) и т. д. Мы будем использовать PyTorch — но код NumPy будет выглядеть почти идентично.
Если следовать вложенным операторам torch, мы генерируем 100 миллионов случайных точек, вычисляем их расстояния до начала координат, подсчитываем точки внутри сферы и делим количество точек на общее количество точек. В конечном итоге массив ratio будет содержать объем сферы в разном количестве измерений.
Настраиваемые параметры установлены для графического процессора с 24 ГБ памяти — настройте их, если ваше железо отличается.
device = torch.device("cuda:0" if torch.cuda.is_available() else "cpu")
# force CPU
# device = 'cpu'
# reduce d_max if too many ratio values are 0.0
d_max = 22
# reduce n if you run out of memory
n = 10**8
ratio = np.zeros(d_max)
for d in tqdm(range(d_max, 0, -1)):
torch.manual_seed(0)
# combine large tensor statements for better memory allocation
ratio[d - 1] = (
torch.sum(
torch.sqrt(
torch.sum(torch.pow(torch.rand((n, d), device=device) - 0.5, 2), dim=1)
)
<= 0.5
).item()
/ n
)
# clean up memory
torch.cuda.empty_cache()
Давайте визуализируем результаты:
N=1 тривиально: и «сфера», и «куб» являются просто линейными отрезками, и они равны, поэтому «объем» «сферы» равен 1. Для N=2 и N=3 вы должны вспомните результаты школьной геометрии и обратите внимание, что эта симуляция очень близка к точным значениям.
Но по мере увеличения N происходит нечто весьма драматичное: объем сферы камнем падает. Она уже близка к 0, когда N=10, и падает ниже точности с плавающей запятой этого моделирования вскоре после N=20 или около того. После этой точки код вычисляет объем сферы равным 0,0 (это просто приближение).
>>> print(list(ratio)) [1.0, 0.78548005, 0.52364381, 0.30841056, 0.16450286, 0.08075666, 0.03688062, 0.015852, 0.00645304, 0.00249584, 0.00092725, 0.00032921, 0.00011305, 3.766e-05, 1.14e-05, 3.29e-06, 9.9e-07, 2.8e-07, 8e-08, 3e-08, 2e-08, 0.0]
Одна интерпретация: при больших значениях N почти весь объем куба располагается в углах. Центральная область, содержащая сферу, становится незначительной по сравнению с ней. В многомерных пространствах углы становятся очень важными. Большая часть объема «мигрирует» в углы. Это происходит очень быстро по мере роста N.
Другой способ взглянуть на это: сфера — это «окрестность» начала. По мере увеличения N точки просто исчезают из этой окрестности. Происхождение на самом деле не такое уж особенное, поэтому то, что происходит с его окрестностями, должно происходить со всеми окрестностями повсюду. Само понятие «окрестности» претерпевает большие изменения. Окрестности пустеют вместе с подъемом Н.
Я провел эту симуляцию впервые несколько лет назад и отчетливо помню, насколько шокирующим был этот результат — как быстро объем сферических пикирующих бомб становится равным 0 по мере увеличения N. Проверив код и не найдя в нем ошибок, моя реакция была такой: сохранить работу, заблокировать экран, выйти на улицу, прогуляться и подумать о том, что вы только что видели. :)
Линейное расстояние
Давайте вычислим диагональ куба как функцию от N. Это тривиально, поскольку диагональ буквально равна sqrt(N), поэтому код слишком прост, чтобы включать его сюда. И вот результаты:
Опять же, для N=2 и N=3 вы должны распознать результаты из геометрии (диагональ квадрата и нормального 3-куба). Но с увеличением N увеличивается и диагональ, и ее рост ничем не ограничен.
Это может показаться очень нелогичным, но даже если размер ребра куба остается постоянным (и равным 1), его диагональ может увеличиваться сколь угодно большой по мере увеличения N. Уже при N=1000 длина диагонали составляет около 32 Теоретически, если ребро куба равно 1 метру, будет пространство с очень многими измерениями, где диагональ куба будет иметь длину 1 километр.
Несмотря на то, что расстояние вдоль края остается прежним, диагональ просто продолжает неограниченно увеличиваться вместе с количеством измерений.
Каждый раз, когда в пространство добавляется новое измерение, появляется больше ребер, граней и т. д., конфигурация угловой области становится более сложной, имеющей больше степеней свободы, а диагональ становится немного длиннее.
Расстояния между наблюдениями
Как насчет расстояний между наблюдениями или точками? Допустим, мы генерируем фиксированное количество случайных точек, а затем вычисляем среднее расстояние между любыми двумя точками и среднее расстояние до ближайшего соседа любой точки. Все точки всегда содержатся в кубе. Что происходит со средними расстояниями при увеличении N? Давайте запустим еще одну симуляцию.
Обратите внимание на консервативный подход к управлению памятью. Это важно, так как используемые здесь структуры данных достаточно велики.
n_points_d = 10**3
# how many pairs of points are there
dist_count = n_points_d * (n_points_d - 1) / 2
# we use the full pair-wise matrix of distances,
# so each distance will be counted twice
dist_count = 2 * dist_count
d_max = d_max_diag
avg_dist = np.zeros(d_max)
avg_dist_nn = np.zeros(d_max)
for d in tqdm(range(d_max, 0, -1)):
torch.manual_seed(0)
# generate random points
point_coordinates = torch.rand((n_points_d, d), device=device)
# compute differences of point coordinates on all axes
coord_diffs = point_coordinates.unsqueeze(1) - point_coordinates
del point_coordinates
# square the coordinate differences
diffs_squared = torch.pow(coord_diffs, 2)
del coord_diffs
# compute distances between any 2 points
distances_full = torch.sqrt(torch.sum(diffs_squared, dim=2))
del diffs_squared
# compute average distance between points
avg_dist[d - 1] = torch.sum(distances_full).item() / dist_count
# compute distances to nearest neighbors
distances_full[distances_full == 0.0] = np.sqrt(d) + 1
distances_nn, _ = torch.min(distances_full, dim=0)
del distances_full
# compute average distance to nearest neighbors
avg_dist_nn[d - 1] = torch.mean(distances_nn).item()
del distances_nn
torch.cuda.empty_cache()
Здесь мы используем гораздо меньше точек (всего 1000), потому что размер основных структур данных увеличивается с N^2, поэтому у нас очень быстро закончится память, если мы сгенерируем слишком много точек. Даже в этом случае приблизительные результаты должны быть достаточно близки к фактическим значениям.
Это среднее расстояние между любыми двумя точками из 1000 в зависимости от N:
При малых значениях N среднее расстояние составляет что-то вроде 0,5 или 1. Но с увеличением N среднее расстояние начинает расти, и при N=2000 оно уже близко к 18. Увеличение существенное.
Это среднее расстояние до ближайшего соседа в зависимости от N:
Увеличение здесь еще более резкое, так как значения совсем крошечные, когда N меньше 10, а точки скучены вместе в низкоразмерном пространстве. При больших значениях N среднее расстояние до ближайшего соседа фактически приближается к среднему расстоянию между любыми двумя точками — иными словами, в измерениях доминирует пустота в непосредственной близости.
Вот почему мы сказали в начале, что точки становятся почти равноудаленными в многомерных пространствах — средние расстояния и кратчайшие расстояния становятся почти одинаковыми. Здесь у вас есть доказательство этого из симуляции и интуиция силы явления.
По мере увеличения числа измерений N все точки удаляются друг от друга, даже если их координаты заключены в один и тот же узкий диапазон (-0,5, +0,5). Группа точек фактически становится все более и более разреженной, просто создавая больше измерений. Увеличение охватывает пару порядков, когда размеры увеличиваются с нескольких единиц до нескольких тысяч. Это очень большое увеличение.
Выводы
Проклятие размерности — реальное явление, имеющее основу в геометрии N-мерных пространств.
При прочих равных, по мере увеличения количества измерений (или признаков) точки (или наблюдения) быстро удаляются друг от друга. Там фактически больше места, хотя линейные интервалы вдоль осей одинаковы. Все окрестности пустеют, и каждая точка оказывается в одиночестве в многомерном пространстве.
Это должно дать некоторую интуицию в отношении того факта, что некоторые методы (кластеризация, различные модели и т. д.) ведут себя по-разному при существенном изменении количества признаков. Несколько наблюдений в сочетании с большим количеством признаков могут привести к субоптимальным результатам — и хотя проклятие размерности — не единственная причина этого, оно может быть одной из причин.
Вообще говоря, количество наблюдений должно «поспевать» за количеством признаков — точные правила здесь зависят от многих факторов.
По крайней мере, эта статья должна предоставить интуитивно понятный обзор свойств многомерных пространств, которые трудно визуализировать. Некоторые тенденции поразительно сильны, и теперь вы должны иметь представление о том, насколько они сильны.
Весь код, используемый в этой статье, находится здесь:
Все изображения, используемые в этой статье, созданы автором (см. ссылку на код выше).
