Сколько глаз у человека? Два.

А в сфере машинного обучения модели умеют видеть любую сразу тысячей или миллионами глаз. Мы живем в 3-х мерном пространстве(3D), и видим 2-х мерную картину мира. Модель, в свою очередь, обитает в цифровом пространстве. Она может видеть ваши 2D фото, 3D модель в Blender сразу со всех сторон и спокойно построить параллелепипед в 15D. 

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

Мы отлично ориентируемся в двух измерениях, немного хуже в трех, а дальше - ВСЁ. 
То, что вышло за пределы привычного куба, перестает быть геометрией в нашем земном понимании. 

Тем не менее нам приходится анализировать результаты работы моделей, для принятия соответствующих решений. Как это делать? Для этого многомерное пространство приходится каким-то образом «свернуть» в обычную плоскость, сохранив как можно больше информации о взаимном расположении точек.

Для этой задачи разработаны специальные алгоритмы. Самыми известными из них сегодня стали t-SNE и UMAP. Несмотря на схожий результат в виде разноцветной двумерной карты, внутри они основаны на разных математических идеях. 

---

В чём идея алгоритмов снижения размеренности?

Свести данные из 50 измерений всего к двум–трём — задача непростая.

Для этого алгоритмы снижения размерности решают задачу преобразования исходного набора данных, заданного в пространстве высокой размерности , в новый набор точек той же мощности, но уже в пространстве меньшей размерности ().

Вопрос в том, какие свойства исходных данных сохранить при проекции. Очевидно, что при сокращение количества измерений мы теряем часть информации. PCA старается сохранить общую дисперсию данных и работает линейно. t-SNE сильнее держится за локальные соседства. UMAP пытается удержать и локальную, и более глобальную структуру.

---

Почему PCA недостаточно?

Представим: собрали данные о площади квартиры и стоимости аренды у тысячи объявлений. Их можно нанести на 2D-график и посмотреть, как они распределены.

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

Допустим, хотим представить эти двумерные данные на одной оси. Один способ — спроецировать их на самую большую главную компоненту (ось красной стрелки). Получается итоговый одномерный график выборки.

У вас может возникнуть вопрос. Почему бы просто не спроецировать данные на горизонтальную ось? Если вернуться к исходному распределению, кажется, что проекция на эту ось даёт очень похожий результат.

Но так делать не стоит. Почему?

Сменим датасет. Теперь у нас средний чек и число заказов в месяц у клиентов интернет-магазина.

На графике клиенты образуют три отдельных кластера (сегменты A, B и C). Если проецировать вдоль оси X, видны только два кластера — два разных сегмента слились в низкоразмерном представлении.

То же самое с другой осью.

А если проецировать на главную компоненту? На этот раз все три кластера в низкоразмерном представлении сохраняются.

Такое представление намного лучше отражает особенность исходных данных, чем простые проекции на координатные оси.

Как это считается?

Первым шагом PCA — считаем ковариационную матрицу датасета. Чтобы получить ковариационную матрицу, сначала  нужно посчитать среднее по каждой переменной и вычесть его из каждой точки.

Затем умножаем транспонированную центрированную матрицу на саму себя и делим на n-1. 

Для 2D получается аккуратная матрица 2×2 — это и есть ковариационная матрица.

Второй шаг — найти собственные векторы ковариационной матрицы. Собственные векторы сортируют по убыванию собственных значений. Векторы с наибольшими собственными значениями и есть главные компоненты.

В конце строят матрицу проекции данных на эти компоненты. Ведро воды… и PCA готов.

У PCA много преимуществ перед более сложными методами. Главное - он опирается только на базовую линейную алгебру и поэтому легко вычисляется. По сложности PCA линеен по числу выборок, время растёт пропорционально размеру датасета.

Однако PCA плохо работает с нелинейными данными, потому что опирается на линейные проекции. Пример — данные в форме спирали. PCA не умеет эффективно разделить такие точки на отдельные кластера. Проблема не в направлении проекции, а в том, что операция линейная, а данные — нет.

Существует гипотеза многообразий (manifold hypothesis), согласно которой реальные данные занимают лишь небольшую область пространства высокой размерности. Несмотря на то что вектора могут состоять из 1536 координат, число независимых факторов, определяющих положение объектов, обычно значительно меньше.

Взгляните на картинку:

Данные лежат в 3D пространстве, но очевидно что эти данные можно практически без потерь сжать до 2D и получить что-то подобное:

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

А поскольку PCA ищет линейную проекцию, он не учитывает нелинейную геометрию данных. Так же не сохраняются локальные окрестности. В результате всего этого точки, являвшиеся ближайшими соседями в исходном пространстве, могут оказаться удаленными друг от друга после проецирования, а объекты из разных областей многообразия, наоборот, могут искусственно сблизиться.

Для задач анализа данных этого часто оказывается недостаточно.

Возникает закономерный вопрос: если сохранить все расстояния невозможно, что именно следует сохранять в первую очередь? Ответ на этот вопрос и стал отправной точкой для создания t-SNE. 

---

t-SNE. Почему локальная структура важнее глобальных расстояний?

Оригинальная работа t-SNE (t-distributed Stochastic Neighbor Embedding) была опубликована Лоренсом ван дер Маатеном и Джеффри Хинтоном в 2008 году. Несмотря на то что алгоритму уже почти два десятилетия, он по-прежнему остается одним из самых популярных методов визуализации данных.

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

В работе On the Surprising Behavior of Distance Metrics in High Dimensional Space (Aggarwal, Hinneburg, Keim, 2001) показано, что по мере роста размерности различия между расстояниями до ближайших и наиболее удаленных соседей постепенно уменьшаются. Иными словами, пространство становится все менее контрастным. Большинство объектов оказываются расположенными примерно на одинаковом расстоянии друг от друга.

Это означает, что значения расстояний становятся менее информативными. Зато сохраняется гораздо более устойчивая характеристика – локальное окружение точки. То есть ближайшие соседи объекта обычно остаются его ближайшими соседями. Из этого наблюдения и родилась идея алгоритма SNE (Stochastic Neighbor Embedding). Авторы предложили сохранять отношения ближайшего соседства. Позднее эта идея и развилась в алгоритм t-SNE.

От расстояний к вероятностям

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

При этом вероятности являются условными, поэтому в общем случае не равно . 
Ключевой особенностью является параметр . В отличие от обычного гауссовского ядра, его значение подбирается отдельно для каждой точки. Этот параметр задаёт, как быстро вероятность падает с расстоянием. Благодаря этому в плотных областях пространства локальная окрестность получается небольшой, а в разреженных автоматически расширяется.

Что делает perplexity?

Масштаб локальной окрестности задается параметром perplexity, который часто ошибочно называют количеством ближайших соседей. На самом деле он определяет эффективный размер локального окружения, который алгоритм стремится учитывать при построении распределения вероятностей. Иными словами perplexity помогает выбрать правильный σ — ширину гауссиан в высокоразмерном пространстве.

Формально perplexity определяется через энтропию Шеннона:

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

Perplexity — очень важный параметр SNE/t-SNE. В попытках найти оптимальное значение приходится пробовать разные значения, пока визуализация не понравится. Обычно берут от 5 до 50 и меньше числа точек. На практике:

• малая perplexity подчёркивает локальные кластеры (при совсем крошечных значениях картинка часто шумная, структура почти не читается)

• большая сильнее собирает точки в более глобальную картину и кластеры обычно становятся размытее.

Почему t-SNE хорошо разделяет кластеры?

После построения распределения вероятностей в исходном пространстве алгоритм создает аналогичное распределение уже на плоскости и минимизирует дивергенцию Кульбака-Лейблера

Несимметричность KL-дивергенции играет здесь важную, даже можно сказать принципиальную роль. Если две точки были соседями в исходном пространстве, но после проецирования оказались далеко друг от друга, функция потерь резко возрастает. Напротив, случайное сближение двух изначально удаленных объектов штрафуется значительно слабее. 

При использовании обычного гауссовского распределения возникает еще одна проблема –crowding problem (Суть проблемы в том, что в пространстве высокой размерности «места» гораздо больше, поэтому при снижении размерности умеренно удаленные друг от друга точки вынуждены скапливаться в центре одной плотной кучи, теряя разделение на кластеры).

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

Для решения этой проблемы авторы заменили гауссово распределение в двумерном пространстве на t-распределение (Стьюдента) с одной степенью свободы:

Благодаря свойствам t-распределения даже умеренно удаленные точки продолжают заметно влиять на функцию потерь.

Это усиливает взаимное отталкивание различных групп объектов, устраняет эффект «скучивания» и в целом делает кластеры на итоговой карте значительно более различимыми.

В результате t-SNE отлично сохраняет локальную структуру данных. Объекты, являющиеся соседями в исходном пространстве, с высокой вероятностью останутся соседями и после проецирования. 

Стоит сказать, что расстояния между кластерами в t-SNE нельзя толковать буквально, ведь алгоритм оптимизирует лишь сохранение локальных соседств. Глобальная геометрия данных может сильно отличаться от реальной. Этот недостаток впоследствии стал одним из причин появления UMAP. Его авторы попытались сохранить и локальные связи, и глобальную структуру.

---

UMAP: сохранение структуры многообразия

Наконец переходим к UMAP (Uniform Manifold Approximation and Projection). Алгоритм, предложенный Лиландом Макиннесом, Джоном Хили и Джеймсом Мелвиллом в 2018 году, опирается на гипотезу многообразия (Manifold Hypothesis), мы уже рассмотрели её выше.

Эта гипотеза подтверждается практическими наблюдениями. Несмотря на то что объекты описываются сотнями или тысячами координат, их взаимное расположение обычно определяется значительно меньшим числом скрытых факторов. В результате данные занимают лишь небольшую область пространства высокой размерности, образуя низкоразмерное многообразие со сложной нелинейной геометрией. Построение приближенной модели этого многообразия и лежит в основе UMAP.

Построение локальной геометрии

В двух словах. UMAP похож на t-SNE, но часто быстрее и лучше сохраняет глобальную структуру, не забывая про локальные связи. 

Ядро похоже на t-SNE. Нам также важно расстояние до соседей каждой высокоразмерной точки и низкоразмерное представление, где эти расстояния примерно совпадают. Но вместо гауссиан и вероятностей используются графы для обоих пространств.

Первый этап работы UMAP – построение графа ближайших соседей (k-nearest neighbors graph). Для каждой точки находятся ближайших соседей, после чего каждой связи назначается вес, отражающий силу локальной близости.

Это выглядит примерно так:

Иногда даже так:

Такой граф помогает сохранить локальную структуру в балансе с глобальной. Но граф всё ещё высокоразмерный — его нужно сжать в 2D.

Как и у t-SNE, есть шаг оптимизации. UMAP старается сохранить связи из высокоразмерного графа, но не через распределения вероятностей и KL, а через идеи из топологии и кросс-энтропией.

Как UMAP считает ближайших соседей?

1. Точки уже лежат в многомерном пространстве признаков. Для каждой точки алгоритм ищет соседей по выбранной метрике расстояния

2. Связь задаётся через k ближайших соседей (n_neighbors). У каждой точки  берут её ближайших объектов и проводят к ним направленные рёбра .
   
   Радиус при этом всё же есть, но он локальный. Представьте его как расстояние до k-го соседа. Так у всех точек получается примерно одинаковое число соседей, несмотря на разную плотность данных. 

3. Связи делают взвешенными. Сила (вероятность) связи падает по мере роста радиуса. Точка в центре сильнее связана с ближайшими соседями и слабее — с более дальними.

4. Гарантия ближайшего соседа (local connectivity). В высокой размерности расстояния часто сжимаются. До 1-го и до 10-го соседа разница может быть крошечной, и без поправки часть точек почти ни с кем не связывается. Поэтому UMAP требует локальной связности, чтобы у каждой точки вес до ближайшего соседа равен 1.
   Технически из расстояний вычитают — расстояние до ближайшего соседа — и только потом считают экспоненциальный спад. В формуле ниже это как раз сдвиг на , ближайший сосед оказывается на нулевом расстоянии в локальной метрике и получает максимальный вес. Остальные веса считаются от расстояния сверх этого минимума.

В работе вес ребра определяется формула, похожей на t-SNE:

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

Про формулу веса

Такое определение веса позволяет учитывать неоднородную плотность данных. В плотных областях граф строится на небольших расстояниях, а в разреженных локальная окрестность автоматически расширяется. Благодаря этому UMAP устойчиво работает на выборках, с сильно различающейся плотностью распределения объектов. 

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

В топологическом анализе данных пространство собирают из простых блоков — симплексов: 0-симплекс — точка, 1-симплекс — ребро, 2-симплекс — треугольник, и так далее. Набор таких блоков с правилами склейки по граням называют симплициальным комплексом (или simplicial set).

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

То же фокус повторяют для каждой точки.Картины локальных окрестностей направленные и могут не совпадать (). Чтобы остался один вес на пару вершин, граф симметризуют (веса в [0, 1]) — вероятностное объединение двух направленных связей:

Оптимизация двумерного представления

После построения топологической модели UMAP создает аналогичный граф уже в двумерном пространстве и минимизирует функцию потерь, основанную на бинарной кросс-энтропии

По смыслу эта функция состоит из двух независимых частей.

• Первая заставляет алгоритм сохранять реальные связи между соседними точками. Если две вершины соединены в графе высокой размерности, они должны остаться соседями и после проецирования.

• Вторая часть штрафует за появление ложных соседств между объектами, которые в исходном пространстве никак не были связаны. Кстати, этот член отсутствует в KL-дивергенции, используемой t-SNE.

Эта деталь делает расположение кластеров на карте UMAP лучше отражающей первоначальную структуру данных. Это подтверждается экспериментами, описанными в оригинальной статье McInnes et al.  Авторы протестировали UMAP на нескольких синтетических и реальных наборах данных. По сравнению с t-SNE и ещё несколькими другими алгоритмами UMAP в большинстве экспериментов лучше сохранял и локальную структуру данных и взаимное расположение крупных кластеров. Особенно заметным это было на наборах с нелинейной геометрией.

Почему UMAP масштабируется лучше?

Еще одним преимуществом UMAP является вычислительная эффективность. PCA и UMAP хорошо масштабируются на большие датасеты. t-SNE дороже по вычислениям и для очень больших данных часто не лучший выбор.

Для поиска ближайших соседей используется приближенный алгоритм NN-Descent, а оптимизация выполняется стохастическим градиентным спуском с negative sampling, аналогично методам обучения представлений данных, таким как Word2Vec.
Благодаря этому UMAP способен работать с наборами данных, содержащими миллионы объектов, сохраняя приемлемое время обучения (практически O(n)) и умеренное потребление памяти (O(n) при фиксированном числе ближайших соседей).

Еще одним преимуществом UMAP является возможность выполнять out-of-sample embedding – проецирование новых объектов в уже построенное низкоразмерное пространство. И самое главное без повторного обучения модели. Благодаря этому алгоритм хорошо подходит для систем, в которых данные поступают непрерывно.

---

t-SNE и UMAP: какой алгоритм выбрать?

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

Главная цель t-SNE – максимально точно сохранить локальное соседство. Алгоритм строит вероятностную модель ближайших соседей и минимизирует KL-дивергенцию между распределениями в исходном и двумерном пространствах. Такая постановка задачи делает его очень чувствительным к локальной структуре данных, благодаря чему t-SNE часто формирует очень выразительные и хорошо разделенные кластеры.

UMAP решает немного другую задачу. Вместо вероятностей соседства он восстанавливает топологическую структуру данных в виде графа ближайших соседей, а затем минимизирует бинарную кросс-энтропию между графами высокой и низкой размерности. Благодаря тому что функция потерь одновременно штрафует как разрыв существующих связей, так и появление ложных, алгоритм обычно лучше сохраняет взаимное расположение крупных групп объектов.

Эта разница хорошо заметна на практике. Если построить визуализацию одного и того же набора эмбеддингов двумя алгоритмами, t-SNE чаще покажет более контрастные кластеры. UMAP, напротив, чаще сохраняет плавные переходы между ними и дает более устойчивое представление о глобальной организации данных.

С практической точки зрения t-SNE и UMAP скорее дополняют друг друга, чем конкурируют. Во многих исследованиях сначала строят карту UMAP, чтобы получить представление об общей структуре данных, а затем используют t-SNE для детального анализа отдельных областей пространства.

---

Встречают по одежке. Как не ошибиться в интерпретации

Наконец переходим к очень важному разделу статьи.

После снижения размерности очень легко забыть, что перед нами не сами данные, а их двумерная модель. И t-SNE, и UMAP неизбежно искажают исходную геометрию пространства, просто делают это по-разному. Поэтому любые выводы по полученной карте должны учитывать ограничения алгоритма.

За последние годы накопилось достаточно практического опыта использования этих методов, а наиболее известный разбор типичных ошибок был опубликован в статье How to Use t-SNE Effectively (Wattenberg, Viégas, Johnson, Distill, 2016). Многие из этих рекомендаций остаются актуальными и для UMAP.

Не интерпретируйте расстояния между кластерами буквально

Это самая распространенная ошибка при работе с t-SNE. Поскольку алгоритм оптимизирует сохранение локальных соседств, взаимное расположение удаленных кластеров практически не контролируется. Два кластера могут оказаться рядом просто потому, что это облегчает минимизацию функции потерь, а не потому, что соответствующие объекты действительно близки в исходном пространстве.

Для UMAP ситуация лучше, но тем не менее даже в этом случае расстояния на плоскости не являются точной копией расстояний в исходном пространстве. Их следует рассматривать как качественную, а не количественную характеристику.

Поэтому по одной лишь визуализации нельзя делать выводы вроде «кластер A в два раза ближе к кластеру B, чем к кластеру C». Ни t-SNE, ни UMAP не предназначены для подобных измерений.

Размер кластера ничего не говорит о количестве объектов

Еще одна ошибка возникает из-за того, что человеческое восприятие автоматически связывает площадь объекта с его численностью. На самом деле алгоритмы снижения размерности не сохраняют плотность распределения точек.

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

Один и тот же датасет может выглядеть совершенно по-разному

Ни t-SNE, ни UMAP не являются полностью детерминированными алгоритмами. Их результат зависит как от случайной инициализации, так и от выбранных параметров.
Для t-SNE главную роль играет perplexity, определяющий масштаб локального соседства. Для UMAP аналогичную функцию выполняет параметр n_neighbors, а степень компактности кластеров дополнительно регулируется параметром min_dist.
Изменение этих параметров способно заметно изменить итоговую картину.

Один и тот же набор эмбеддингов может выглядеть как единый кластер, как несколько независимых групп или как сложная иерархическая структура. Полезно гонять несколько конфигураций. Можете попробывать интерактивно на сайте Understanding UMAP.

Поэтому авторы статьи How to Use t-SNE Effectively рекомендуют не делать выводов по единственной визуализации. Хорошей практикой считается построение нескольких карт с различными параметрами и проверка того, какие закономерности остаются устойчивыми во всех экспериментах.

---

Заключение

Красивую визуализацию получить несложно. Гораздо сложнее  правильно ее интерпретировать. Поэтому важно понимать, какие свойства данных сохраняет алгоритм, а какими жертвует. В случае t-SNE и UMAP эти различия напрямую влияют на то, что мы увидим на графике и какие выводы сможем из него сделать.

Спасибо за прочтения! Не забудьте оценить статью и написать комментарий)