UMAP
Uniform Manifold Approximation and Projection (UMAP) — алгоритм машинного обучения, выполняющий нелинейное снижение размерности[1].
История создания и описание
UMAP был создан Лилендом Макиннесом совместно с его коллегами из Таттского института. Целью было получить алгоритм, похожий на t-SNE[2], но с более сильным математическим обоснованием[3].
При снижении размерности UMAP сначала выполняет построение взвешенного графа, соединяя ребрами только те объекты, которые являются ближайшими соседями. Множество из ребер графа — это нечёткое множество с функцией принадлежности, она определяется как вероятность существования ребра между двумя вершинами. Затем алгоритм создает граф в низкоразмерном пространстве и приближает его к исходному, минимизируя сумму дивергенций Кульбака-Лейблера[a] для каждого ребра из множеств[4][5].
Алгоритм UMAP используется в различных областях науки: биоинформатика, материаловедение, машинное обучение[6].
Принцип работы алгоритма
На обработку алгоритму поступает выборка из [math]\displaystyle{ n }[/math] объектов: [math]\displaystyle{ X = \{x_1, \; \ldots, \; x_n\} }[/math]. UMAP рассчитывает расстояние между объектами по заданной метрике и для каждого объекта [math]\displaystyle{ x_i }[/math] определяет список из его [math]\displaystyle{ k }[/math] ближайших соседей: [math]\displaystyle{ T = \{t_1, \; \ldots, \; t_k\} }[/math].
Помимо этого, для каждого объекта рассчитывается расстояние до его ближайшего соседа: [math]\displaystyle{ \rho_i = \min_{t \, \in \, T} d(x_i, t) }[/math]. А также величина [math]\displaystyle{ \sigma_i }[/math], заданная уравнением:
- [math]\displaystyle{ \sum_{t \, \in \, T} \exp\left(-\frac{d(x_i, t) - \rho_i}{\sigma_i}\right) = \log_2 k }[/math].
Далее алгоритм выполняет построение взвешенного ориентированного графа, в котором ребра соединяют каждый объект с его соседями. Вес ребра от [math]\displaystyle{ x_i }[/math] объекта до его [math]\displaystyle{ t_j }[/math] соседа рассчитывается следующим образом:
- [math]\displaystyle{ w(x_i \rightarrow t_j) = \exp\left(-\frac{d(x_i, t_j) - \rho_i}{\sigma_i}\right) }[/math]
Полученная ранее [math]\displaystyle{ \sigma_i }[/math] нормирует сумму весов для каждого объекта к заданному числу [math]\displaystyle{ \log_2 k }[/math].
Так как UMAP строит взвешенный ориентированный граф, то между вершинами могут существовать два ребра с разными весами. Вес ребра интерпретируется как вероятность существования данного ребра от одного объекта к другому. Исходя из этого, ребра между двумя вершинами объединяются в одно с весом, равным вероятности существования хотя бы одного ребра:
- [math]\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) }[/math].
Таким образом, алгоритм получает взвешенный неориентированный граф[7].
Множество ребер [math]\displaystyle{ E }[/math] такого графа является нечетким множеством из случайных величин Бернулли. Алгоритм создает новый граф в низкоразмерном пространстве и приближает множество его ребер к исходному. Для этого он минимизирует сумму дивергенций Кульбака-Лейблера для каждого ребра [math]\displaystyle{ e }[/math] из исходного и нового нечетких множеств:
- [math]\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} }[/math][8],
- [math]\displaystyle{ w_h(e) }[/math] — функция принадлежности нечеткого множества из ребёр в высокоразмерном пространстве,
- [math]\displaystyle{ w_l(e) }[/math] — функция принадлежности нечеткого множества из ребёр в низкоразмерном пространстве.
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.
Примечания
- ↑ Etienne Becht, 2018, с. 1.
- ↑ Duoduo Wu, 2019.
- ↑ PyData Ann Arbor Meetup. PyData Ann Arbor: Leland McInnes, PCA, t-SNE, and UMAP: Modern Approaches to Dimension Reduction (англ.) (12 июня 2018). Дата обращения: 28 июня 2019. Архивировано 9 ноября 2020 года.
- ↑ Leland McInnes, 2018, с. 11—12.
- ↑ Jakob Hansen. UMAP (англ.) (недоступная ссылка). Personal plog (4 мая 2018). Дата обращения: 28 июня 2019. Архивировано 26 августа 2019 года.
- ↑ Ceshine Lee. UMAP on RAPIDS (15x Speedup) (англ.) (PDF). Medium (30 марта 2019). Дата обращения: 28 июня 2019. Архивировано 26 августа 2019 года.
- ↑ Leland McInnes, 2018, с. 13.
- ↑ Leland McInnes, 2018, с. 16—17.
- ↑ Авторы называют данную величину кросс-энтропией нечетких множеств, fuzzy set cross entropy
Ссылки
- Авторская презентация алгоритма
- Авторский туториал и преимущества UMAP
- Примеры работ в UMAP: 1 и 2
- Обзор алгоритма
- Принцип работы алгоритма и примеры