Ищем и выпрямляем многообразия

Шаг 1

Итак, мы поняли, что данные часто лежат на искривлённой поверхности, но как найти эту поверхность?

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

Разберёмся по шагам:

Шаг 1. Отбрасываем глобальные линейки

Первая и главная идея: мы перестаём верить в глобальные евклидовы расстояния

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

Мы можем измерить расстояние по прямой между носом и затылком человека, но это не будет соответствовать расстоянию, которое пройдёт фломастер, чтобы нарисовать “по лицу” линию между ними.

Получается, сейчас нужно понять, как идти по поверхности.

Шаг 2. Смотрим на локальных соседей

Хотя глобально поверхность изогнута, локально она почти плоская, поэтому в исходном пространстве, если две точки очень близко друг к другу, они, скорее всего, являются соседями и на поверхности.

Соединим такие близкие точки условным маршрутом.

Получается условная паутина (граф), который показывает маршруты между точками

То есть, если мы хотим понять расстояние от Москвы до Нью-Йорка, нам нужно считать расстояния просто до близких городов и “шагать” через них маленькими шажками.

Полученная ломаная будет очень близка к тому, как если бы мы шли по земле.

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

Эта сетка и есть полученный граф.

Шаг 3. Всё, что осталось — разложить на плоскости (плоском пространстве)

Этот шаг делиться на две части:

Понять какая размерность нам нужна
Понять как это всё выпрямить

Шаг 2

Сначала поймём, как понять, какая нам нужна размерность.

Когда мы работали с линейными моделями мы оценивали размерность нужного пространства через размер сингулярных чисел после применения алгоритма SVD.

Но в данном случае его глобальное использование может не дать нужного ответа

Многообразие может быть устроено таким образом, что попытка линейного сжатия потребует 20 измерений, а само многообразие имеет размерность 3.

И SVD покажет как раз 20, а не нужные нам 3.

Первая идея состоит в локальности.

Мы помним, что локально многообразие похоже на плоское пространство.

Получается, SVD можно использовать локально на нескольких точках (только в малой окрестности) и таким образом оценить примерную нужную размерность.

Более математический и глобальный способ - использовать на руку проклятье размерности.

Идея: в d-мерном пространстве число точек внутри шара радиуса r растёт как $r^d$ .

Про это мы говорили два урока назад.

Попробуем оценить посчитать это количество для каждого r.

$C(r) = \frac{l(r)}{N(N - 1)}$

где $l(r)$ - количество пар точек в маленьком шарике радиуса r.

$N(N - 1)$ - количество пар точек. Мы на него делим, чтобы получить число от 0 до 1.

При маленьких r у C(r) будет очень похоже на $r^d$ .

Поэтому, размерность можно вычислить по формуле:

$d = \frac{\log{C(r)}}{log(r)}$ при очень малых r

Шаг 3

Теперь нужно перенести точки с полученного графа на пространство полученной размерности.

Поговорим об одном конкретном алгоритме.

Главная идея тут - использовать условные “пружины”, которые будут сами двигать точки так, как нам нужно.

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

Теперь “свяжем” эти точки “пружинами” той длины, какое у них было расстояние на поверхности.

Эти пружины будут приближать или отдалять эти точки так, чтобы расстояния были максимально похожи на нужные нам.

Сначала располагаем как-то точки на плоском пространстве и точки сами начинают отталкиваться и притягиваться друг от друга, пока мы не получим нужную точность.

Запишем в формулах нашу идею

Пусть $D_{ij}$ - расстояние между точками i и j на графе

Тогда:

E = \sum_{i, j}{(||x_i - x_j|| - D_{ij})^2}

Общая энергия наших пружин.

Задача сводится к тому, чтобы минимизировать эту энергию.

На каждую точку будет действовать сила:

$F_i = \sum_{j}F_{ij}$

Где $F_{ij}$ - сила, полученная от одной точки, и считаемая по формуле:

$F_{ij} = k \left( D_{ij} - \|x_i - x_j\| \right) \frac{x_i - x_j}{\|x_i - x_j\|}$

Может выглядеть страшно, но тут всё проще, чем кажется.

Справа после скобки стоит вектор единичной длины в направлении от точки i к точке j, он показывает, в каком направлении действует сила.

k - просто коэффициент, то, насколько сильно мы хотим двигать точки после каждого шага

В скобках разность между нужным расстоянием и тем, которое мы сейчас имеем

Новые координаты точки это старые плюс сила.

Это не самый популярный вариант переноса, но самый наглядный. Он помогает понять идею: точки притягиваются и отталкиваются так, чтобы расстояния на плоскости были похожи на расстояния на графе.

Шаг 4

Разобранный только что подход не всегда работает хорошо

Поверхности можно разделить на два типа:

Замкнутые
Незамкнутые и бесконечные

Незамкнутые - это те, у которых есть “граница” меньшей на 1 размерности, чем сама поверхность

Например, если взять полусферу, то у неё есть граница, которая образует окружность

Бесконечные поверхности это те, которые уходят в бесконечность (как бы это ни было тавтологично).

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

В какой-то момент можно просто отрезать поверхность плоскостью (или в больших размерностях подпространством) и получить незамкнутую поверхность.

Главная их особенность, что практически всегда перенести граф с них на плоское пространство достаточно несложно

Например, тот же “эллиптический параболоид”, который я показывал пару шагов назад - бесконечная поверхность

Немного поигравшись с расстояниями можно граф с него переложить на плоскость, практически сохранив расстояния (точно сохранить именно с ним не получится, но получится достаточно хорошо)

Но замкнутые поверхности (например, сфера или тор) лишены такой привилегии

Взять даже сферу

Если на ней построить граф, окажется, что переложить его на плоскость, сохранив расстояния проблематично

Где-то придётся сделать как бы “разрез”, после которого часть расстояний сохранится, а часть нет

Немалая часть дорог сохранится, но те точки, которые были рядом до разреза, могут оказаться далеко после него

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

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

На следующем видео показана визуализация построения графа на поверхности и переноса его на плоскость

Интересно, что для того, чтобы её сделать я использовал библиотеку для машинного обучения scikit-learn

Ищем и выпрямляем многообразия

Шаг 1

Шаг 2

Шаг 3

Шаг 4

Шаг 5