UMAP

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

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

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

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

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

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

∑ t ∈ T exp ⁡ ( − d ( x i , t ) − ρ i σ i ) = log 2 ⁡ k {\displaystyle \sum _{t\,\in \,T}\exp \left(-{\frac {d(x_{i},t)-\rho _{i}}{\sigma _{i}}}\right)=\log _{2}k} .

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

w ( x i → t j ) = exp ⁡ ( − d ( x i , t j ) − ρ i σ i ) {\displaystyle w(x_{i}\rightarrow t_{j})=\exp \left(-{\frac {d(x_{i},t_{j})-\rho _{i}}{\sigma _{i}}}\right)}

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

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

w ( x i , x j ) = w ( x i → x j ) + w ( x j → x i ) − w ( x i → x j ) ⋅ w ( x j → x i ) {\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})} .

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

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

∑ e ∈ E w h ( e ) log ⁡ w h ( e ) w l ( e ) + ( 1 − w h ( e ) ) log ⁡ ( 1 − w h ( e ) 1 − w l ( e ) ) → min w l {\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}}} ^[8],

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

w l ( 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. Comparison Between UMAP and t-SNE for Multiplex-Immunofluorescence Derived Single-Cell Data from Tissue Sections (англ.) // bioRxiv. — 2019. — 15 February. — doi:10.1101/549659.
• Etienne Becht, Charles-Antoine Dutertre, Immanuel W.H. Kwok, Lai Guan Ng, Florent Ginhoux, Evan W. Newell. Evaluation of UMAP as an alternative to t-SNE for single-cell data (англ.) // bioRxiv. — 2018. — 28 June. — doi:10.1101/298430.
• Leland McInnes, John Healy, James Melville. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (англ.) // arXiv. — 2018. — 7 December.

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