Поисковый алгоритм Яндекс «Палех»

2-го ноября 2016 года Яндекс анонсировал поисковый алгоритм «Палех», основанный на нейронных сетях.

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

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

Искусственный интеллект или машинное обучение?

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

Эпоха наивного поиска
Сначала был просто поиск слов — инвертированный индекс. Потом страниц стало слишком много, их стало нужно ранжировать. Начали учитываться разные усложнения — частота слов, tf-idf.

Эпоха ссылок
Потом страниц стало слишком много на любую тему, произошёл важный прорыв — начали учитывать ссылки, появился PageRank.

Эпоха машинного обучения
Интернет стал коммерчески важным, и появилось много жуликов, пытающихся обмануть простые алгоритмы, существовавшие в то время. Произошёл второй важный прорыв — поисковики начали использовать свои знания о поведении пользователей, чтобы понимать, какие страницы хорошие, а какие — нет.
На этом этапе человеческого разума перестало хватать на то, чтобы придумывать, как ранжировать документы. Произошёл следующий переход — поисковики стали активно использовать машинное обучение.
Один из лучших алгоритмов машинного обучения изобрели в Яндексе — это Матрикснет.
Можно сказать, что ранжированию помогает коллективный разум пользователей и «мудрость толпы».
Информация о сайтах и поведении людей преобразуется во множество факторов, каждый из которых используется Матрикснетом для построения формулы ранжирования. Фактически, формулу ранжирования пишет машина (получалось около 300 мегабайт).
Но у «классического» машинного обучения есть предел: оно работает только там, где очень много данных.
Небольшой пример. Миллионы пользователей вводят запрос [вконтакте], чтобы найти один и тот же сайт. В данном случае их поведение является настолько сильным сигналом, что поиск не заставляет людей смотреть на выдачу, а подсказывает адрес сразу при вводе запроса. Но люди сложнее, и хотят от поиска всё больше.

Сейчас уже до 40% всех запросов уникальны, то есть не повторяются хотя бы дважды – в течение всего периода наблюдений. Это значит, что у поиска нет данных о поведении пользователей в достаточном количестве, и Матрикснет лишается ценных факторов. Такие запросы в Яндексе называют «длинным хвостом», поскольку (все вместе) они составляют существенную долю обращений к поиску.

Эпоха искусственного интеллекта
Компьютеры становятся быстрее и данных становится больше, поэтому назрела необходимость использовать нейронные сети.
На основе технологий нейронных сетей основан машинный интеллект (или искусственный интеллект). Он основан потому, что нейронные сети построены по образу нейронов в нашем мозге и пытаются эмулировать работу некоторых его частей.
Машинный интеллект гораздо лучше старых методов справляется с задачами, которые могут делать люди: например, распознаванием речи или образов на изображениях.
Так каким образом это может помочь поиску?
Как правило, низкочастотные и уникальные запросы довольно сложны для поиска и найти качественный ответ по ним заметно труднее.
Как это сделать?
У Яндекс нет подсказок от пользователей (какой документ лучше, а какой — хуже), поэтому для решения поисковой задачи нужно научиться лучше понимать смысловое соответствие между двумя текстами: запросом и документом.

Итак, искусственные нейросети – это один из методов машинного обучения. Нейронные сети показывают впечатляющие результаты в области анализа естественной информации — звука и образов. Это происходит уже несколько лет. Но почему их до сих пор не так активно применяли в поиске? Простой ответ — потому что говорить о смысле намного сложнее, чем об образе на картинке, или о том, как превратить звуки в расшифрованные слова.
Тем не менее, в поиске смыслов, искусственный интеллект действительно стал приходить из той области, где он уже давно является лидирующим — из поиска по картинкам.

Несколько слов о том, как это работает в поиске по картинкам.
Вы берёте изображение и с помощью нейронных сетей преобразуете его в вектор в N-мерном пространстве.
Берете запрос (который может быть как в текстовом виде, так и в виде другой картинки) и делаете с ним то же самое. А потом сравниваете эти векторы.
Чем ближе векторы друг к другу, тем больше картинка соответствует запросу и, соответственно, если это работает в картинках, почему не применить эту логику в web-поиске?

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

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

DSSM
В 2013 году исследователи из Microsoft Research описали свой подход, который получил название Deep Structured Semantic Model.
На вход модели подаются тексты запросов и заголовков. Для уменьшения размеров модели, над ними производится операция, которую авторы называют word hashing. К тексту добавляются маркеры начала и конца, после чего он разбивается на буквенные триграммы. Например, для запроса [палех] мы получим триграммы [па, але, лех, ех].
Поскольку количество разных триграмм ограничено, то мы можем представить текст запроса в виде вектора размером в несколько десятков тысяч элементов (размер нашего алфавита в 3 степени). Соответствующие триграммам запроса элементы вектора будут равны 1, остальные — 0.
По сути, мы отмечаем вхождение триграмм из текста в словарь, состоящий из всех известных триграмм.
Если сравнить такие векторы, то можно узнать только о наличии одинаковых триграмм в запросе и заголовке, что не представляет особого интереса. Поэтому теперь их надо преобразовать в другие векторы, которые уже будут иметь нужные нам свойства семантической близости.
После входного слоя, расположено несколько скрытых слоёв как для запроса, так и для заголовка.
Последний слой размером в 128 элементов и служит вектором, который используется для сравнения.
Выходом модели является результат скалярного умножения последних векторов заголовка и запроса (если быть совсем точным, то вычисляется косинус угла между векторами).
Модель обучается таким образом, чтобы для положительны обучающих примеров выходное значение было большим, а для отрицательных — маленьким. Иначе говоря, сравнивая векторы последнего слоя, мы можем вычислить ошибку предсказания и модифицировать модель таким образом, чтобы ошибка уменьшилась.

В Яндекс тоже активно исследуются модели на основе искусственных нейронных сетей, поэтому заинтересовались моделью DSSM.
Характерное свойство алгоритмов, описываемых в научной литературе, состоит в том, что они не всегда работают «из коробки». «Академический» исследователь и исследователь из индустрии находятся в существенно разных условиях.
В качестве отправной точки (baseline), с которой автор научной публикации сравнивает своё решение, должен выступать какой-то общеизвестный алгоритм — так обеспечивается воспроизводимость результатов.
Исследователи берут результаты ранее опубликованного подхода, и показывают, как их можно превзойти. Например, авторы оригинального DSSM сравнивают свою модель по метрике NDCG с алгоритмами BM25 и LSA.
В случае с прикладным исследователем, который занимается качеством поиска в реальной поисковой машине, отправной точкой служит не один конкретный алгоритм, а всё ранжирование в целом.
Цель разработчика Яндекс состоит не в том, чтобы обогнать BM25, а в том, чтобы добиться улучшения на фоне всего множества ранее внедренных факторов и моделей. Таким образом, baseline для исследователя в Яндекс чрезвычайно высок, и многие алгоритмы, обладающие научной новизной и показывающие хорошие результаты при «академическом» подходе, оказываются бесполезными на практике, поскольку не позволяют реально улучшить качество поиска.

В случае с DSSM в Яндекс столкнулись с этой же проблемой. В практических экспериментальных условиях точная реализация модели из статьи показала скромные результаты. Потребовался ряд существенных «доработок напильником», прежде чем в Яндекс смогли получить результаты, интересные с практической точки зрения.

Об основных модификациях оригинальной модели, чтобы сделать её более мощной.

В оригинальной модели DSSM входной слой представляет собой множество буквенных триграмм. Его размер равен 30000.
У подхода на основе триграмм есть несколько преимуществ:
во-первых, их относительно мало, поэтому работа с ними не требует больших ресурсов;
во-вторых, их применение упрощает выявление опечаток и ошибок в словах.
Однако, эксперименты показали, что представление текстов в виде «мешка» триграмм заметно снижает выразительную силу сети, поэтому в Яндекс радикально увеличили размер входного слоя, включив в него, помимо буквенных триграмм, ещё около 2 миллионов слов и словосочетаний. Таким образом, в Яндекс представляют тексты запроса и заголовка в виде совместного «мешка» слов, словесных биграмм и буквенных триграмм, а использование большого входного слоя приводит к увеличению размеров модели, длительности обучения и требует существенно больших вычислительных ресурсов.

Как нейронная сеть боролась сама с собой и научилась на своих ошибках

Обучение исходного DSSM состоит в демонстрации сети большого количества положительных и отрицательных примеров. Эти примеры берутся из поисковой выдачи (судя по всему, для этого использовался поисковик Bing).
Положительными примерами служат заголовки кликнутых документов выдачи, отрицательными — заголовки документов, по которым не было клика.
У этого подхода есть определённые недостатки. Например, отсутствие клика далеко не всегда свидетельствует о том, что документ нерелевантен. Справедливо и обратное утверждение — наличие клика не гарантирует релевантности документа.
По сути, обучаясь описанным в исходной статье образом, алгоритм стремится предсказывать аттрактивность заголовков при условии того, что они будут присутствовать в выдаче. Это, конечно, неплохо, но имеет достаточно косвенное отношение к главной цели — научиться понимать семантическую близость.

Во время экспериментов в Яндекс обнаружили, что результат можно заметно улучшить, если использовать другую стратегию выбора отрицательных примеров.
Для достижения цели хорошими отрицательными примерами являются такие документы, которые гарантированно нерелевантны запросу, но при этом помогают нейронной сети лучше понимать смыслы слов. Откуда их взять?
Сначала, в качестве отрицательного примера, возьмём заголовок случайного документа. Например, для запроса [палехская роспись] случайным заголовком может быть «Правила дорожного движения 2016 РФ».
Разумеется, полностью исключить то, что случайно выбранный из миллиардов документ будет релевантен запросу, нельзя, но вероятность этого настолько мала, что ей можно пренебречь. Таким образом мы можем очень легко получать большое количество отрицательных примеров.
Казалось бы, теперь мы можем научить сеть тому, чему хочется отличать хорошие документы, которые интересуют пользователей, от документов, не имеющих к запросу никакого отношения.
К сожалению, обученная на таких примерах модель оказалась довольно слабой. Нейронная сеть – штука умная, и всегда найдет способ упростить себе работу. В данном случае, она просто начала выискивать одинаковые слова в запросах и заголовках: есть — хорошая пара, нет — плохая. Но это Яндекс и сам умеет делать. Важно – чтобы сеть научилась различать неочевидные закономерности.

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

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

Среди сотен случайных заголовков в Яндекс выбирали такой, который текущая нейросеть считала наилучшим. Но, так как этот заголовок всё равно случайный, с высокой вероятностью он не соответствует запросу. И именно такие заголовки экспериментаторы стали использовать в качестве отрицательных примеров.
Другими словами, можно показать сети лучшие из случайных заголовков, обучить её, найти новые лучшие случайные заголовки, снова показать сети и так далее.
Раз за разом повторяя данную процедуру, экспериментаторы видели, как заметно улучшается качество модели, и всё чаще лучшие из случайных пар становились похожи на настоящие положительные примеры. И в итоге – проблема была решена.
Подобная схема обучения в научной литературе обычно называется hard negative mining.
Следует также отметить, что, схожие по идее, решения получили широкое распространение в научном сообществе для генерации реалистично выглядящих изображений, подобный класс моделей получил название Generative Adversarial Networks.

В качестве положительных примеров исследователи из Microsoft Research использовались клики по документам. Однако, как уже было сказано, это достаточно ненадежный сигнал о смысловом соответствии заголовка запросу.
В конце концов, задача состоит не в том, чтобы поднять в поисковой выдаче самые посещаемые сайты, а в том, чтобы найти действительно полезную информацию. Поэтому в Яндекс пробовали, в качестве цели обучения, использовать другие характеристики поведения пользователя. Например, одна из моделей предсказывала, останется ли пользователь на сайте или уйдет. Другая – насколько долго он задержится на сайте.
Как оказалось, можно заметно улучшить результаты, если оптимизировать такую целевую метрику, которая свидетельствует о том, что пользователь нашёл то, что ему было нужно.

Так что нам дает это на практике?

Если сравнить поведение нейронной модели Яндекс и простого текстового фактора, основанного на соответствии слов запроса и текста — это алгоритм BM25, который удобно использовать – как базовый уровень.
В качестве примера возьмем запрос [келлская книга] и посмотрим, какое значение принимают факторы на разных заголовках. Для контроля добавим в список заголовков явно нерелевантный результат.

Все факторы в Яндекс нормируются в интервал [0;1]. Ожидается, что BM25 имеет высокие значения для заголовков, которые содержат слова запроса. И предсказуемо, что этот фактор получает нулевое значение на заголовках, не имеющих общих слов с запросом.
Если обратить внимание на то, как ведет себя нейронная модель, то она одинаково хорошо распознаёт связь запроса как с русскоязычным заголовком релевантной страницы из Википедии, так и с заголовком статьи на английском языке! Кроме того, кажется, что модель «увидела» связь запроса с заголовком, в котором не упоминается келлская книга, но есть близкое по смыслу словосочетание («ирландские евангелия»). Значение же модели для нерелевантного заголовка существенно ниже.

Если посмотреть, как будут себя вести наши факторы, если переформулировать запрос, не меняя его смысла: [евангелие из келлса], то для BM25 переформулировка запроса превратилась в настоящую катастрофу — фактор стал нулевым на релевантных заголовках, а модель Яндекс демонстрирует отличную устойчивость к переформулировке: релевантные заголовки по-прежнему имеют высокое значение фактора, а нерелевантный заголовок — низкое. Кажется, что именно такое поведение мы и ожидали от штуки, которая претендует на способность «понимать» семантику текста.
Итак, нейронная модель оказалась способна высоко оценить заголовок с правильным ответом, несмотря на полное отсутствие общих слов с запросом. Более того, стало очевидным то, что заголовки, не отвечающие на запрос, но всё же связанные с ним по смыслу, получают достаточно высокое значение фактора (как будто модель Яндекс «прочитала» рассказ Брэдбери и «знает», что это именно о нём идёт речь в запросе).

И что дальше?

Специалисты Яндекс находятся в самом начале интересного пути. Судя по всему, нейронные сети имеют отличный потенциал для улучшения ранжирования. Уже понятны основные направления, которые нуждаются в активном развитии. Например, очевидно, что заголовок содержит неполную информацию о документе, и хорошо бы научиться строить модель по полному тексту (как оказалось, это не совсем тривиальная задача).
Далее, можно представить себе модели, имеющие существенно более сложную архитектуру, нежели DSSM и есть основания предполагать, что таким образом Яндекс сможет лучше обрабатывать некоторые конструкции естественных языков.
Долгосрочную цель специалисты Яндекс видят в создании моделей, способных «понимать» семантическое соответствие запросов и документов на уровне, сравнимом с уровнем человека.

Статья основана на материалах Яндекс о том, как работает новый поисковый алгоритм «Палех»