Русская Википедия:UMAP
Uniform Manifold Approximation and Projection (UMAP) — алгоритм машинного обучения, выполняющий нелинейное снижение размерностиШаблон:Sfn.
История создания и описание
UMAP был создан Лилендом Макиннесом совместно с его коллегами из Таттского института. Целью было получить алгоритм, похожий на t-SNEШаблон:Sfn, но с более сильным математическим обоснованием[1].
При снижении размерности UMAP сначала выполняет построение взвешенного графа, соединяя ребрами только те объекты, которые являются ближайшими соседями. Множество из ребер графа — это нечёткое множество с функцией принадлежности, она определяется как вероятность существования ребра между двумя вершинами. Затем алгоритм создает граф в низкоразмерном пространстве и приближает его к исходному, минимизируя сумму дивергенций Кульбака-ЛейблераШаблон:Efn для каждого ребра из множествШаблон:Sfn[2].
Алгоритм UMAP используется в различных областях науки: биоинформатика, материаловедение, машинное обучение[3].
Принцип работы алгоритма
На обработку алгоритму поступает выборка из <math>n</math> объектов: <math>X = \{x_1, \; \ldots, \; x_n\}</math>. UMAP рассчитывает расстояние между объектами по заданной метрике и для каждого объекта <math>x_i</math> определяет список из его <math>k</math> ближайших соседей: <math>T = \{t_1, \; \ldots, \; t_k\}</math>.
Помимо этого, для каждого объекта рассчитывается расстояние до его ближайшего соседа: <math>\rho_i = \min_{t \, \in \, T} d(x_i, t)</math>. А также величина <math>\sigma_i</math>, заданная уравнением:
- <math>\sum_{t \, \in \, T} \exp\left(-\frac{d(x_i, t) - \rho_i}{\sigma_i}\right) = \log_2 k</math>.
Далее алгоритм выполняет построение взвешенного ориентированного графа, в котором ребра соединяют каждый объект с его соседями. Вес ребра от <math>x_i</math> объекта до его <math>t_j</math> соседа рассчитывается следующим образом:
- <math>w(x_i \rightarrow t_j) = \exp\left(-\frac{d(x_i, t_j) - \rho_i}{\sigma_i}\right)</math>
Полученная ранее <math>\sigma_i</math> нормирует сумму весов для каждого объекта к заданному числу <math>\log_2 k</math>.
Так как UMAP строит взвешенный ориентированный граф, то между вершинами могут существовать два ребра с разными весами. Вес ребра интерпретируется как вероятность существования данного ребра от одного объекта к другому. Исходя из этого, ребра между двумя вершинами объединяются в одно с весом, равным вероятности существования хотя бы одного ребра:
- <math>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>.
Таким образом, алгоритм получает взвешенный неориентированный графШаблон:Sfn.
Множество ребер <math>E</math> такого графа является нечетким множеством из случайных величин Бернулли. Алгоритм создает новый граф в низкоразмерном пространстве и приближает множество его ребер к исходному. Для этого он минимизирует сумму дивергенций Кульбака-Лейблера для каждого ребра <math>e</math> из исходного и нового нечетких множеств:
- <math>\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>Шаблон:Sfn,
- <math>w_h(e)</math> — функция принадлежности нечеткого множества из ребёр в высокоразмерном пространстве,
- <math>w_l(e)</math> — функция принадлежности нечеткого множества из ребёр в низкоразмерном пространстве.
UMAP решает задачу минимизации с помощью стохастического градиентного спуска. Полученное множество из ребер определяет новое расположение объектов и, соответственно, низкоразмерное отображение исходного пространства.
Программное обеспечение
- Руководство по установке библиотеки
- Применение в языке R
Литература
Примечания
Шаблон:Примечания Шаблон:Комментарии
Ссылки
- Авторская презентация алгоритма
- Авторский туториал и преимущества UMAP
- Примеры работ в UMAP: 1 и 2
- Обзор алгоритма
- Принцип работы алгоритма и примеры
