UMAP

Uniform Manifold Approximation and Projection (UMAP) — алгоритм машинного обучения, выполняющий нелинейное снижение размерностиШаблон:Sfn.

История создания и описание

UMAP был создан Лилендом Макиннесом совместно с его коллегами из Таттского института. Целью было получить алгоритм, похожий на t-SNEШаблон:Sfn, но с более сильным математическим обоснованием.

При снижении размерности UMAP сначала выполняет построение взвешенного графа, соединяя ребрами только те объекты, которые являются ближайшими соседями. Множество из ребер графа — это нечёткое множество с функцией принадлежности, она определяется как вероятность существования ребра между двумя вершинами. Затем алгоритм создает граф в низкоразмерном пространстве и приближает его к исходному, минимизируя сумму дивергенций Кульбака-ЛейблераШаблон:Efn для каждого ребра из множествШаблон:Sfn.

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

Принцип работы алгоритма

На обработку алгоритму поступает выборка из $n$ объектов: $X=\{x_1,\dots ,x_n\}$. UMAP рассчитывает расстояние между объектами по заданной метрике и для каждого объекта $x_i$ определяет список из его $k$ ближайших соседей: $T=\{t_1,\dots ,t_k\}$.

Помимо этого, для каждого объекта рассчитывается расстояние до его ближайшего соседа: ${\rho }_i=\underset{t\in T}{\min }d(x_i,t)$. А также величина ${\sigma }_i$, заданная уравнением:

$\sum _{t\in T}\exp (-\frac{d(x_i,t)-{\rho }_i}{{\sigma }_i})={\log }_{2}k$.

Далее алгоритм выполняет построение взвешенного ориентированного графа, в котором ребра соединяют каждый объект с его соседями. Вес ребра от $x_i$ объекта до его $t_j$ соседа рассчитывается следующим образом:

$w(x_i\to t_j)=\exp (-\frac{d(x_i,t_j)-{\rho }_i}{{\sigma }_i})$

Полученная ранее ${\sigma }_i$ нормирует сумму весов для каждого объекта к заданному числу ${\log }_{2}k$.

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

$w(x_i,x_j)=w(x_i\to x_j)+w(x_j\to x_i)-w(x_i\to x_j)\cdot w(x_j\to x_i)$.

Таким образом, алгоритм получает взвешенный неориентированный графШаблон:Sfn.

Множество ребер $E$ такого графа является нечетким множеством из случайных величин Бернулли. Алгоритм создает новый граф в низкоразмерном пространстве и приближает множество его ребер к исходному. Для этого он минимизирует сумму дивергенций Кульбака-Лейблера для каждого ребра $e$ из исходного и нового нечетких множеств:

$\sum _{e\in E}{w}_h(e)\log \frac{w_h(e)}{w_l(e)}+(1-w_h(e))\log \left(\frac{1-w_h(e)}{1-w_l(e)}\right)\to \underset{w_l}{\min }$Шаблон:Sfn,

$w_h(e)$ — функция принадлежности нечеткого множества из ребёр в высокоразмерном пространстве,

$w_l(e)$ — функция принадлежности нечеткого множества из ребёр в низкоразмерном пространстве.

UMAP решает задачу минимизации с помощью стохастического градиентного спуска. Полученное множество из ребер определяет новое расположение объектов и, соответственно, низкоразмерное отображение исходного пространства.

Программное обеспечение

• Руководство по установке библиотеки
• Применение в языке R

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Авторская презентация алгоритма
• Авторский туториал и преимущества UMAP
• Примеры работ в UMAP: 1 и 2
• Обзор алгоритма
• Принцип работы алгоритма и примеры