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

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

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

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

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

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

На обработку алгоритму поступает выборка из ${\displaystyle n}$ объектов: ${\displaystyle X=\{x_{1},\;\ldots ,\;x_{n}\}}$ . UMAP рассчитывает расстояние между объектами по заданной метрике и для каждого объекта ${\displaystyle x_{i}}$ определяет список из его ${\displaystyle k}$ ближайших соседей: ${\displaystyle T=\{t_{1},\;\ldots ,\;t_{k}\}}$ .

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

${\displaystyle \sum _{t\,\in \,T}\exp \left(-{\frac {d(x_{i},t)-\rho _{i}}{\sigma _{i}}}\right)=\log _{2}k}$ .

Далее алгоритм выполняет построение взвешенного ориентированного графа , в котором ребра соединяют каждый объект с его соседями. Вес ребра от ${\displaystyle x_{i}}$ объекта до его ${\displaystyle t_{j}}$ соседа рассчитывается следующим образом:

${\displaystyle w(x_{i}\rightarrow t_{j})=\exp \left(-{\frac {d(x_{i},t_{j})-\rho _{i}}{\sigma _{i}}}\right)}$

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

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

${\displaystyle w(x_{i},x_{j})=w(x_{i}\rightarrow x_{j})+w(x_{j}\rightarrow x_{i})-w(x_{i}\rightarrow x_{j})\cdot w(x_{j}\rightarrow x_{i})}$ .

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

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

${\displaystyle \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)\rightarrow \min _{w_{l}}}$ ,

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

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

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

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

• по установке библиотеки
• в языке R

Литература

• Duoduo Wu, Joe Yeong Poh Sheng, Grace Tan Su-En, Marion Chevrier, Josh Loh Jie Hua, Tony Lim Kiat Hon, Jinmiao Chen. (англ.) // bioRxiv. — 2019. — 15 February. — doi : .
• Etienne Becht, Charles-Antoine Dutertre, Immanuel W.H. Kwok, Lai Guan Ng, Florent Ginhoux, Evan W. Newell. (англ.) // bioRxiv. — 2018. — 28 June. — doi : .
• Leland McInnes, John Healy, James Melville. (англ.) // arXiv. — 2018. — 7 December.

Примечания

Ссылки

• алгоритма
• и преимущества UMAP
• Примеры работ в UMAP: и
• алгоритма и примеры