УДК 004

Векторизация графов знаний с использованием моделей перехода на основе расстояния

Ветров Владислав Сергеевич – аспирант Финансового университета при правительстве РФ.

Аннотация: В современном мире одним из наиболее важных представлений структурированной информации является граф знаний. Его квантизация и исследование является одним из наиболее перспективных направлений в области анализа данных и развития искусственного интеллекта.

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

Ключевые слова: граф знаний, вектор, матрица, оптимизация, гиперплоскость, проекция.

Введение

Графы знаний (далее ГЗ) стали одним из ключевых ресурсов для развития машинного обучения и искусственного интеллекта, включая такие задачи, как создание вопросно-ответных систем, систем рекомендаций, поиска и создания знания и т. д. В последние годы появилось несколько крупных ГЗ, таких как Freebase и DBpedia, NELL, Wikidata и др. Данные графы были созданы путем машинного извлечения структурированной информации из различной текстовой информации в интернете и ручного обогащения этих данных.

Несмотря на то, что крупный ГЗ содержат миллиарды фактоидов-троек, структурированные знания до сих пор составляют малый процент от «абсолютного» знания и, вероятно, содержат множество различных ошибок и противоречий.

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

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

Среди задач по восстановлению графов встречаются такие как, прогнозирование хвостовой сущности при наличии головной и отношения -   прогнозирование отношения - и, наконец, прогнозирования головной сущности -  В процессе решения задач был создан целый класс успешных моделей перехода на основе расстояния, включая TransE, TransH, TransR, TransT и т. д. Эти модели направлены на создание наиболее точных векторных представлений для сущностей и отношений по принципу , то есть переходит в с помощью .

Обзор основных алгоритмов векторизации ГЗ c помощью перехода на основе расстояния

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

TransE определяется как отрицательное расстояние между  и , т.е.

Несмотря на свою простоту и эффективность, TransE имеет недостатки при работе с отношениями по типу «1 к N», «N к 1» и «N к N». К примеру, можно рассмотреть отношение типа «1 к N». Если брать в рассмотрение отношение r,

 такое, что выполняется  , TransE форсирует условие  для всех , и следовательно . Это означает, что, например, при использовании TransE для векторизации двух троек (Эльдар Рязанов, режиссер, Служебный роман) и (Эльдар Рязанов, режиссер, Ирония судьбы, или С легким паром!) по условиям TransE должны будут выполняться два условия: Эльдар Рязанов + режиссер = Служебный роман и Эльдар Рязанов + режиссер = Ирония судьбы, или С легким паром!. Из этого можно вывести, что «Ирония судьбы, или С легким паром!» и «Служебный роман» являются одной и той же сущностью в векторном представлении TransE. Аналогичные недостатки существуют для отношений типа «N к 1» и «N к N».

Рисунок 1. Иллюстрация работы алгоритма TransE.

Такая модель как TransH продолжает и модернизирует идеи TransE. Для решения вышеперечисленных проблем модель вводит понятие гиперплоскостей в разрезе отношений, не сущностей. TransH моделирует объекты снова как векторы, но каждое отношение  как вектор r на гиперплоскости, где  - вектор нормали. Беря в рассмотрение фактоид , представления сущностей  и  являются сначала проецируется на гиперплоскость:

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

Это аналогично той функции, что используется в TransE. Вводя механизм создания проекций на гиперплоскости, зависящих от отношения, TransH позволяет сущностям иметь разные роли в зависимости от отношения.

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

Здесь - матрица проекции из пространства сущностей в пространство отношений . Затем функция оценки определяется как,

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

Затем эти две проекционные матрицы наносятся на голову объект  и хвостовой объект  соответственно, чтобы получить их проекции, т.е.

TransT развивает идеи предшественников и вводит понятие типов сущностей в задачу векторизации базы данных на основе графов. Цель модели - получить векторные представления сущностей и отношений, которые максимизируют вероятность предсказания по всем существующим фактоидам-тройкам.

Согласно теореме Байеса,  можно рассматривать как апостериорную вероятность, и ее корреляция с априорной вероятностью определяется как,

Заключение

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

Данные модели предлагают не только различные подходы к векторизации графов знаний, но и возможности для добавления новой информации, например, типов. Не смотря на то, что у некоторых моделей могут быть сложности с обработкой определенных кейсов, например отношений по типу «1 к N» у TransE, или высокая алгоритмическая сложность у TransH, данные методы являются одними из наиболее интуитивных и точных алгортимов для векторизации, доступных на сегодня.

Список литературы

1. C. Николенко, А. Кадурин, Е. Архангельская, Глубокое обучение. – СПб.: Питер, 2018. – 281 стр.
2. Hongyun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang, A Comphensive Survey of Graph Embedding: Problems, Techniques and Applications, arXiv: 1709.07604.Конец формы
3. Quan Wang, Zhendong Mao, Bin Wang, and Li Guo, Knowledge Graph Embedding: A Survey of Approaches and Applications, IEEE Transactions on Knowledge and Data Engineering (Volume: 29, Issue: 12, Dec. 1 2017), pp 2724 – 2743.
4. Shiheng Ma, Jianhui Ding, Weijia Jia, Kun Wang, and Minyi Guo, TransT: Type-Based Multiple Embedding Repsentations for Knowledge Graph Completion, ECML PKDD 2017: Machine Learning and Knowledge Discovery in Databases, pp 717-733.