UMAP

Перейти к навигацииПерейти к поиску

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

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

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

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

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

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

На обработку алгоритму поступает выборка из объектов: . UMAP рассчитывает расстояние между объектами по заданной метрике и для каждого объекта определяет список из его ближайших соседей: .

Помимо этого, для каждого объекта рассчитывается расстояние до его ближайшего соседа: . А также величина , заданная уравнением:

.

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

Полученная ранее нормирует сумму весов для каждого объекта к заданному числу .

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

.

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

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

[8],
 — функция принадлежности нечеткого множества из ребёр в высокоразмерном пространстве,
 — функция принадлежности нечеткого множества из ребёр в низкоразмерном пространстве.

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

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

Литература

Примечания

  1. Etienne Becht, 2018, с. 1.
  2. Duoduo Wu, 2019.
  3. 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 года.
  4. Leland McInnes, 2018, с. 11—12.
  5. Jakob Hansen. UMAP (англ.). Personal plog (4 мая 2018). Дата обращения: 28 июня 2019. Архивировано из оригинала 26 августа 2019 года.
  6. Ceshine Lee. UMAP on RAPIDS (15x Speedup) (англ.) (PDF). Medium (30 марта 2019). Дата обращения: 28 июня 2019. Архивировано 26 августа 2019 года.
  7. Leland McInnes, 2018, с. 13.
  8. Leland McInnes, 2018, с. 16—17.
  1. Авторы называют данную величину кросс-энтропией нечетких множеств, fuzzy set cross entropy

Ссылки