Пуанкаре: Вложения для изучения иерархических представлений

Maximilian Nickel, Douwe Kiela

Facebook AI Research, 2017

https://arxiv.org/pdf/1705.08039.pdf

О чем статья

Благодаря трудам Миколова и многих других талантливых учёных в ML активно используется подход построения embedding-ов, то есть отображения каких-либо сущностей в Евклидово векторное пространство(word2vec, seq2vec, node2vec и т.д.).

Однако во многих областях приходится иметь дело с данными, внутренняя структура которых представляет собой не-Евклидово пространство. Например, проблемы возникают с иерархическими данными, которые нужно представить в виде таких embedding-ов, что для каждого узла иерархии расстояние до родителя должно быть меньше, чем расстояние до других потомков этого родителя. Делать отображения таких данных в Евклидово пространство может быть крайне неэффективным(требовать большого количества измерений и т.д.).
Авторы данной статьи предлагают решить проблему представления структур объектов с потенциальными внутренними иерархиями, отображая объекты в гиперболическое пространство.

Такое отображение даёт сразу несколько преимуществ:

• вместе со смысловой близостью объектов модель также выявляет внутреннюю иерархию

• модель становится более ёмкой(требуется меньшее количество измерений для формирования осмысленных embedding-ов)

• модель более устойчива к переобучению

Суть идеи авторов

Гиперболическое пространство- это геометрическое пространство, в котором нарушается пятый постулат Евклида, гласящий, что через точку, не лежащую на прямой можно провести одну прямую, не пересекающуюся с исходной. У этого пространства отрицательная кривизна, сумма углов треугольника меньше 180 градусов. Примерами таких пространств могут выступать псевдосфера и гиперболоид. Стоит отметить, что в гиперболических пространствах вместо понятия прямой используется понятие геодезической, т.е. линии, отмечающей наиболее короткий путь между двумя точками.

На гиперболоиде можно проиллюстрировать нарушение пятого постулата Евклида. Через точку M проведены две геодезические d_1 и d_2 не пересекающие геодезическую D.

В качестве модели гиперболического пространства авторы взяли шар Пуанкаре.

В простейшем двумерном случае он называется диском Пуанкаре и выглядит, как круг единичного радиуса на плоскости без своей границы. Геодезическими являются либо прямые линии, проходящие через центр круга; либо линии произвольных окружностей, пересекающих границу диска под прямым углом. На следующем рисунке, выделено несколько различных геодезических.

На диске задан Риманов метрический тензор

Здесь ||*|| - это Евклидова норма, x - точка на диске, g^E - Евклидов метрический тензор, то есть просто единичная матрица.

Также задано расстояние между любыми точками u, v на диске

Здесь arcosh визуально имеет следующий вид

Из формулы расстояния видно, что при приближении одной из точек к границе диска расстояние между точками будет становиться бесконечно большим. Таким образом, периметр диска представляет собой множество бесконечно-удалённых точек. Близко к центру же, напротив, расстояния между точками становятся небольшими.

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

Здесь коричневым обозначена геодезическая на гиперболоиде, а красным - её проекция, геодезическая на диске Пуанкаре.

Давайте теперь увидим, как так получается, что диск Пуанкаре отлично вмещает в себя древесные структуры. Допустим, мы имеем дело с деревом, у которого фактор ветвления b. То есть на L-ом уровне это дерево должно иметь

вершин.

Также оно должно иметь

вершин суммарно на всех уровнях не больше L-ого.

Если при этом мы хотим обеспечить такие естественные свойства дерева, как превалирование попарных расстояний между “сестринскими” вершинами над расстояниями до их предка, то придётся под каждую вершину выделять определенную область, суммарная мера таких областей может расти также как количество вершин, то есть экспоненциально.
Если мы будем размещать вершины L-ого уровня на окружностях радиуса

в гиперболическом пространстве, а предыдущие вершины внутри данных окружностей, то все уместится, потому что, в отличие от Евклидова пространства, где длина окружности и площадь круга растут полиномиально относительно радиуса, в гиперболическом пространстве и длина и площадь растут экспоненциально. На следующем рисунке представлено схематично, как можно разместить вершины дерева на диске Пуанкаре. Примечательно тут то, что все рёбра можно считать равными.

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

Несмотря на то, что уже просто диск Пуанкаре обладает такой колоссальной ёмкостью, на практике часто используют его многомерную версию, шар Пуанкаре, потому что, во-первых, может сосуществовать несколько независимых иерархий одних и тех же объектов; во-вторых, это добавляет степеней свободы при обучении.

Помимо модели шара Пуанкаре существует большое количество других моделей гиперболических пространств, но авторы использовали именно эту из-за простоты ограничений на оптимизируемые параметры embedding-ов (нужно просто убеждаться, что их Евклидова норма не больше единицы, чтобы они оставались внутри диска), а также благодаря тому, что данная модель является конформной(углы в Евклидовом пространстве и в гиперболическом совпадают).

Эти факторы делают алгоритм обучения очень простым:

1. Задаёмся каким-нибудь функционалом
2. Вычисляем Евклидовый градиент от этого функционала
3. Переводим Евклидов градиент в Риманов(углы сохраняются, а вот длины нет, но всё решается с помощью простейшего инвертирования скалярного метрического тензора)
4. Производим градиентный спуск/подъём.

Алгоритм тестировался на датасете WordNet, оптимизируемый функционал был следующий

Здесь D – множество пар гипероним-гипоним (причём порядок в паре недетерминированный), N(u) – отрицательные примеры, включающие и сам элемент u.

Алгоритм тестировался в нескольких режимах, в первом (режим Reconstruction) ему давались все данные, и потом тестировались адекватности соотношения расстояний между различными парами лемм(использовались метрики средней позиции(Rank) и mean-average precision в отранжированном ряде); во втором (Link Prediction) при обучении модели не показывали пары из тестового множества, метрики были те же самые.

Гиперболические embedding-и показали себя лучше своих Евклидовых аналогов как в плане метрик, так и в плане требуемой размерности пространства(требуется гораздо меньшая размерность для достижения нормального качества).

Так выглядят embedding-и лемм WordNet-а после сходимости(здесь для наглядности приведены только млекопитающие). Можно видеть, что иерархия была восстановлена(ближе к центру обобщенные понятия, дальше — их частности).

Также алгоритм тестировался на других задачах, к примеру, отображении социального графа учёных, где он также хорошо себя показал.

Моё мнение

Статья, хоть и представляет нестандартный подход к проблеме, является сравнительно не новой и множество известных учёных развили эту идею.
Поэтому вместо своего мнения я лучше перечислю несколько статей для дальнейшего изучения:

• можно строить различные классификаторы в гиперболическом пространстве, в том числе аналог SVM https://arxiv.org/pdf/1806.00437.pdf
• Более того можно строить гиперболические глубокие нейронные сети https://arxiv.org/abs/2101.04562

• Также естественной идеей является подгонка коэффициентов кривизны под задачу или использование комбинации пространств различной кривизны https://openreview.net/pdf?id=HJxeWnCcF7
• Помимо всего прочего есть статья, описывающая trade-off-ы подобного подхода https://arxiv.org/pdf/1804.03329.pdf
• Есть также примеры использования в рекомендациях в комбинации с вариационным автокодировщиком https://arxiv.org/abs/2008.06716

Источник: m.vk.com

Комментарии: