company_banner

Граф знаний в Поиске: построение из нескольких источников



    Я хочу рассказать о том, что такое граф знаний и об одном из способов его построения из нескольких тематических источников.

    Большое количество запросов в поиске содержат единственную сущность — объект, про который спрашивает пользователь. Это могут быть запросы про каких-то людей, фильмы, сериалы, музыкальные или географические объекты. Когда пользователь задает такой запрос, в выдаче ему можно показать дополнительную информационную карточку в надежде, что информация в карточке будет интересна пользователю. Карточки украшают выдачу и повышают ее наглядность. С помощью информационных карточек мы даём человеку понять, что он пользуется интеллектуальным сервисом, потому что поисковая система поняла, что он имел в виду, о каком именно объекте спрашивал. Более того, эту интеллектуальность можно расширить, отвечая на запрос пользователя прямо на странице выдачи. Например, в ответ на «что посмотреть в Праге» мы можем сразу показать достопримечательности этого города.

    Бывают случаи, когда пользователь хочет узнать что-то о каком-то объекте, но совершенно ничего о нём не знает, кроме факта его существования. Или пользователь хочет продолжить исследования по какой-то теме. Специально для этого случая в карточке показывается то, чем известен этот объект, а также возможные варианты для продолжения исследования в блоке «cмотрите также».

    Граф знаний


    В основе всех этих семантических технологий лежит граф знаний — это граф, узлами которого являются объекты реального мира, а переходами — типизированные отношения между объектами (например, отношение для места рождения отличается от отношения даты рождения). Пример маленького графа знаний показан на рис. 1.


    Рис. 1. Пример графа знаний

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

    Таблица. 1. Статистика по открытым графам знаний

    Граф знаний Количество записей Количество объектов Частота обновления
    Freebase Более 3 миллиардов 49 миллионов Не обновляется
    Викиданные 748 миллионов 18 миллионов Раз в неделю (инкрементально — раз в сутки)
    DBpedia 411 миллиона 4 миллиона Последнее обновление в августе 2019

    Проблема открытых графов заключается в том, что не все сферы знаний освещены достаточно глубоко. Например, российские сериалы. Они не очень популярны во всем мире, но нам особенно дороги, потому что пользователи спрашивают про них. Это значит, что мы должны найти какую-то информацию об этих сериалах и принести её на SERP (Search Engine Result Page). Вторая проблема — это довольно редкие обновления. А ведь когда случается какое-то событие, мы хотим как можно скорее принести эту информацию и показать её на страницах с результатами поиска.

    Существует как минимум три возможных решения этих проблем.

    Первое: ничего не делать, смириться, закрыть на это глаза и продолжать жить. Второе: аккуратно вручную добавлять информацию в открытые графы знаний, а потом пользоваться данными оттуда. И третий вариант: автоматически слить с графом знания из какого-то тематического источника. Для тех же фильмов и сериалов таких источников довольно много: КиноПоиск, IMDb, Кино Mail.ru. Причем в графах знаний, как правило, у объектов присутствуют ссылки на популярные тематические ресурсы.

    Мы начали реализовывать третий подход. Прежде, чем приступать к решению этой задачи, нужно подготовиться. Дело в том, что данные в источниках представлены в разных форматах. Например, в Викиданных — это JSON, в КиноПоиске — HTML. Их нужно сконвертировать в одинаковый формат. Мы конвертируем в N-Triples, потому что его удобно обрабатывать параллельно, а в данном случае это действительно важно, так как мы работаем с большими данными. Разжатый JSON-дамп Викиданных занимает около 720 Гб, а HTML-страницы КиноПоиска 230 Гб, поэтому почти все задачи решаются на кластере с помощью парадигмы MapReduce.

    Склейка дублей


    Одной из самых сложных задач при слиянии графов знаний является склейка дублей. Например, у нас есть графы и два каких-то объекта в них, которые являются одним объектом реального мира. Мы хотим в нашем результирующем графе склеить их вместе так, чтобы это был один объект в графе знаний. Решение, которое мы придумали с самого начала, довольно простое. Давайте мы возьмем и склеим все объекты, у которых одинаковые имена. Так мы узнали, что существует, как минимум, два известных человека с именем Брэд Питт, чуть менее сорока фильмов и сериалов под названием «Мост», и примерно столько же Иванов Ивановых про которых есть статья на Википедии.

    Очевидно, что такой простой подход не работает, требуется что-то посложнее. И тогда мы придумали решение из трёх частей. Первая часть — это генератор кандидатов для связывания. Вторая — классификатор, который пытается ответить на вопрос, нужно ли склеивать между собой пару объектов. И третья — это дополнительный шаг склейки: мы доклеиваем то, что не получилось по каким-то причинам склеить на предыдущем шаге.

    Генератор нужен для того, чтобы сократить количество кандидатов для связывания (пытаться связать каждый объект с каждым слишком дорого). Поэтому мы ограничиваемся лишь небольшим множеством кандидатов и после запускаем классификатор только для этого небольшого множества. Основная идея заключается в том, что имена объектов, которые могут быть связаны, должны каким-то образом быть похожи. Мы решили начать с полного совпадения подстрок, но с возможностью перестановки слов. Это значит, что если у двух объектов порядок слов в имени не совпадает (например, имя и фамилия человека перепутаны местами), они всё равно будут сопоставлены. Мы используем как русские имена, так и оригинальные иностранные. Также мы используем прозвища, псевдонимы и синонимы объектов, которые мы собрали из перенаправлений Википедии.

    Прежде чем обучать модель, неплохо бы откуда-то получить данные. Нам повезло, всё необходимое уже было в открытых графах знаний. Например, в Викиданных чуть менее 200 тыс. объектов, ссылок на фильмы и сериалы КиноПоиска, и чуть менее 100 тыс. ссылок на персон КиноПоиска. На этих данных мы и будем обучаться.

    В основе всех признаков лежит идея, что один и тот же объект в двух графах должен иметь схожий контекст. Похожая идея используются при решении задачи Entity Linking. Причем под контекстом в графе подразумеваются не соседние объекты к данному объекту, а их строковые описания. Более формально контекстом объекта в графе будут считаться все смежные ему строки, а также имена инцидентных ему объектов и типы. На рис. 2 строки, которые принадлежат контексту этого объекта, выделены жирным.


    Рис. 2. Контекст объекта

    Работать со строками можно несколькими способами. Во-первых, считать совпадение строк, сопоставляя их целиком, то есть учитывая только полное совпадение. Во-вторых, можем пользоваться строкой как мешком слов, разбить строку на слова и пожертвовать порядком. Мы используем оба подхода.

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

    Возьмём два объекта: Лионель Месси (Lionel Messi) и Лайонел Ричи (Lionel Richie), табл. 2.

    Таблица. 2. Некоторые отношения для объектов «Лионель Месси» и «Лайонел Ричи».

    Имя отношения Лионель Месси Лайонел Ричи
    name «Lionel Messi» «Lionel Richie»
    birthday «June 24, 1987» «June 20, 1949»
    football_club «FC Barcelona»

    Имена не совпадают целиком, поэтому полное совпадение в имени будет равно нулю. Но количество совпадений слов в имени равно 1, потому что оригинальное имя «Lionel» совпадает у обоих объектов. Коэффициент Жаккара (отношение размера пересечения к размеру объединения) для имени будет равен 0.2:

    $J(Messi, Richie) = \frac{\left |«Lionel» \right |}{\left |«Лионель», «Месси», «Lionel», «Messi», «Richie» \right |}$


    Мы не сразу поняли, что если у какого-то объекта не хватает нужного отношения, то не имеет смысла торопиться и записывать в этот признак нуль, лучше записать Missing value. Ведь когда мы добавляем к большому графу какой-то тематический граф, в нём часто отсутствуют какие-то отношения, и нужно иметь возможность различать случаи, когда в двух отношениях ничего не совпало, и когда у какого-то из объектов просто не хватает нужного отношения. Следуя этой логике количество совпавших слов для отношения «football_club» будет равно Missing value. Количество полных совпадений строк по всем отношениям равно нулю, а количество совпавших слов — два («Lionel» и «June»).

    Рейтинг лучших признаков, используемых моделью показан на рис. 3.


    Рис. 3. Самые важные из используемых признаков

    Лучшим признаком у нашей модели считается суммарное относительное совпадение слов. За этим сложным названием скрывается сумма коэффициентов Жаккара по всем отношениям. Интересно, что если вообще выбросить всё машинное обучение из этой задачи и оставить более-менее адекватную отсечку по значению этого признака, то качество модели по $F_{1}$-мере упадет всего на 20 %. Если взять признаки, которые описаны выше, обучить на них XGBoost из коробки, 250 деревьев высотой 4, то мы получим довольно неплохие метрики.

    Таблица. 3. Метрики качества модель на тестовых данных.

    Имя метрики Значение
    Точность (precision) 0.961531
    Полнота (recall) 0.963220
    $F_{1}$ 0.962375
    AUC 0.999589

    Но есть проблема: на этих метриках не видно некоторых объектов, которые мы не склеиваем. Это так называемые «большие объекты» у которых много отношений. Города, страны, род занятий — это те объекты, которые связаны с большим количеством других объектов. На рис. 4 показано, как это может выглядеть на SERP. Кажется, что все довольно безобидно:


    Рис. 4. Проблема «больших» объектов

    У нас в карточке есть дубли. Казалось бы, ничего страшного, но на самом деле проблема намного глубже, страдает согласованность данных. Так происходит потому, что в наших обучающих данных совсем нет подобных объектов. Здесь нужно применить другой подход, использовать большое количество отношений этих объектов себе во благо. На рис. 5 показана схема такого подхода. Пусть есть два объекта X и Y, которые связал классификатор. Эти объекты принадлежат разным графам и каждый объект связан с какими-то другими объектами в своем графе. Объект X связан с объектами A, B, C с помощью отношений $r_{1}$, $r_{2}$, $r_{3}$, а объект Y с объектами D, E и F c помощью отношений $r_{1}$, $r_{2}$ и $r_{4}$. Но теперь нам известно, что объекты X и Y на самом деле являются одним объектом реального мира.


    Рис. 5. Дополнительная склейка

    Давайте выдвинем две гипотезы:

    • $H_{1}: P(D | A) = p = P(D | ¬A)$ — объект $D$ никак не связан и встречается независимо от объекта $A$.
    • $H_{2}: P(D | A) = p_{1}\neq p_{2} = P(D | ¬A)$ — какая-то зависимость между $D$ и $A$ всё-таки есть.

    Тогда мы сможем применить Likelihood-ratio тест и принять одну из двух гипотез. Таким образом у нас получится склеить большие объекты.

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

    Заключение


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

    Надеюсь, что было интересно почитать немного о том, как это все работает изнутри. Если остались какие-то непонятные моменты, пожалуйста, задавайте вопросы, попробую на них ответить.
    Mail.ru Group
    Строим Интернет

    Похожие публикации

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

      0
      А вообще такие графы всегда являются собственностью компаний, или есть свободные базы данных которые можно скачать?
        +1
        Как правило поисковые компании неохотно делятся (или не делятся совсем) своими графами. Но некоторые предоставляют API, для доступа к данным, например, Google. Есть и свободные графы знаний, которые может скачать любой желающий. В статье упоминаются некоторые из них. Например, Freebase, Wikidata и DBpedia.
        +1

        А сколько «объектов» и «записей» у вас? И как вы их храните?


        Объясните еще, пожалуйста, как вы считали количества записей и количества объектов в «открытых графах знаний», или дайте ссылки туда, откуда вы эти цифры взяли. У меня другие цифры получаются / находятся.


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




        Для тех, кому эти темы интересны, в Telegram есть по ним пара групп:


        Wikidata (группа закрытая, ссылка может меняться, актуальная всегда есть в шапке этой страницы);
        Linked Data Russia (группа открытая, но ведите себя скромно, пожалуйста).

          +1
          А сколько «объектов» и «записей» у вас? И как вы их храните?

          Сейчас в нашем графе 71 521 402 объектов (но это вместе со служебными объектами, например, с теми, которые представляют собой сложные отношения) и 1 899 142 069 записей (триплов).

          Все данные хранятся и обрабатываются в самописном хранилище. Если коротко, то все элементы триплов хэшируются и почти вся работа производится с хэшами, кроме самого конца, когда нам необходимо получить строковое представление данных. Хэшированные триплы хранятся в отсортированном виде. Хранилище поддерживает только простые запросы, вида: вернуть все элементы в указанном диапазоне, где диапазоны задаются в виде хэшей spo-троек, где пропуски могут быть только в правой части (например: (s, *, *), (s, p, *), (s, p, o)). Вся более сложная логика реализована поверх запросов такого типа. Все данные хранятся в памяти.

          Объясните еще, пожалуйста, как вы считали количества записей и количества объектов в «открытых графах знаний», или дайте ссылки туда, откуда вы эти цифры взяли. У меня другие цифры получаются / находятся.

          Статистика в таблице дана скорее для понимания объемов данных, с которыми приходится работать. Данные про объемы графов взяты из публикации Färber M., Rettinger A. Which Knowledge Graph Is Best for Me? //arXiv preprint arXiv:1809.11099. – 2018. Не исключаю, что за время, которое прошло с ее публикации что-то могло сильно поменяться.
            +1

            Понял, спасибо большое!


            Про число «записей» и «объектов» написал авторам. Самый большой вопрос по Викиданным. Если верить этой таблице (а не верить ей нет оснований, и результаты подтверждаются пересчетом), то указанное для Викиданных число триплетов было достигнуто летом 2019 года. Число Q-сущностей было в это время в четыре раза больше указанного. При этом статья была опубликована осенью 2018.

          0
          А вы пытались склеить граф wikidata и dbpedia. Сколько объектов удалось объединить? Ваш инструмент реализован? И есть ли он в открытом доступе?
            0
            А вы пытались склеить граф wikidata и dbpedia.

            Нет, пока не пытались. На мой взгляд это интересная исследовательсая задача, которой можно попробовать заняться.

            Ваш инструмент реализован? И есть ли он в открытом доступе?

            Да, инструмент реализован и активно используется. К сожалению, в открытом доступе его пока нет.
              +1

              А чего тут склеивать? Все уже давно склеено. Linked Data все-таки.


              • В Викиданных есть так называемые sitelinks. При наличии ссылки на страницу английской Википедии восстановить связь с сущностью DBpedia можно тривиально.
              • Обратно, в DBpedia сущности связаны с сущностями Викиданных через owl:sameAs. Уж разобрать-то ссылку «Wikidata Item» в левой колонке страницы Википедии DBpedia Extraction Framework умеет.

              На DBpedia даже есть именованный граф <http://www.wikidata.org>. Когда-то вообще даже был ресурс wikidata.dbpedia.org.

                0

                Спасибо за ответ. Но мне интересна процедура автоматического отождествления объектов разных графов.

              0
              Вообще-то то, что автор назвал «Граф знаний», на деле является Графом Семантических Связей — ГСС, что далеко не тождественно друг-другу.
              Граф Знаний пытаются сформировать давно, но проблема заключается в неразработанности машинного формата «Знаний».
              С появлением реального Графа Знаний появится и СИИ — Сильный Искусственный Интеллект, способный к мыслительной деятельности.
              А так, в целом, зачётная статья.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое