Вопросы здесь задают «Я»

Основная задача поисковика – быстро получить точный ответ на вопрос пользователя. Люди привыкли обращаться к поисковой строке по любому поводу, игнорируя правила русского языка и здравый смысл. Неудивительно, что самая наукоемкая часть системы – именно многоуровневая обработка пользовательского запроса. Руководитель службы быстрых и интерактивных ответов Поиска Яндекса Алексей Шаграев рассказывает, как поисковик устроен изнутри и каким образом ему удается оперативно отвечать на любые, даже самые странные, неочевидные и причудливо сформулированные вопросы. Этой статьей N + 1 открывает серию совместных материалов с Яндексом о технологиях, которые стоят за работой поиска в интернете.

Человек вводит в поисковую строку запрос и жмет на кнопку «найти». Меньше чем через секунду он видит перед собой результат работы системы: набор документов, который должен помочь ему получить нужную информацию.

Что произошло за эти доли секунды

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

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

Ответ на любой вопрос

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

Логика проста. Чем больше документов, тем вероятнее обнаружится что-то релевантное пользовательскому запросу. Впрочем, собирая документы, приходится соблюдать некоторые ограничения. Например, Яндекс индексирует только те документы, которые указаны создателями сайтов как «разрешенные для скачивания» либо доступные по последовательности ссылок, ведущих с главной страницы ресурса. Современные поисковые системы хранят сотни миллиардов документов.

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

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

Слова и «термы»

Любой запрос состоит из слов. Несколько слов подряд называются «контактной n-граммой». Это может быть отдельное слово («униграмма»), два слова подряд («биграмма») или любое другое количество слов. Когда они располагаются произвольным образом, а не следуют друг за другом, «n-грамма» называется неконтактной. Каждый запрос разбивается системой на подобные слова или последовательности слов — так называемые термы.

Для некоторых термов лучшие документы обнаруживаются и запасаются в соответствующей поисковой базе заранее. Например, Яндекс хранит документы, наиболее релевантные термам «сколько», «времени сейчас», «сколько в Москве». Таким образом, для каждого терма запоминается небольшое количество лучших документов. В результате первая стадия ранжирования становится значительно проще с точки зрения вычислений. Система выделяет термы запроса, обращается к хранилищу, где уже хранятся лучшие документы, и в дальнейшем работает только с их объединением.

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

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

Вектора и семантика

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

Для обработки текстов метод векторных представлений применяется с 2013 года, когда была написана знаменитая программа word2vec. Идея заключается в том, что каждому отдельному слову сопоставляется некоторый вектор, то есть последовательность чисел с определенной семантикой. При этом сопоставления подбираются таким образом, чтобы семантика слов обретала геометрическую интерпретацию. Слова с похожим смыслом получают близкие векторные представления (то есть располагаются «близко» в пространстве) и наоборот, не похожие по смыслу слова получают отличные друг от друга представления.

При определенном способе обучения отношения между словами точно так же обретают геометрическое выражение. Например, вектор разницы между векторными представлениями слов «король» и «принц» оказывается близок вектору разницы между словами «королева» и «принцесса». Аналогичным образом определенные векторные сдвиги могут описывать изменение рода и числа слов и так далее.

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

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

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

Векторные представления можно попытаться обучить таким образом, чтобы векторы запросов оказались близки к векторам документов, на которые пользователи кликают, и не были близки к тем, которые кликов не собирают совсем. Оказалось, что такая модель «знает» много всего интересного о связях между словами. Разработчики не закладывали в нее структурированной информации: она все выучила самостоятельно. Например, модель «знает», что имя исполнителя тесно связано с названием его песен, а описание фильма – с его названием. Это позволяет искать фильмы и песни через поисковую строку.

Факторы ранжирования

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

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

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

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

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

Распределенные системы

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

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

На самых ранних этапах ранжирования количество документов сильно ограничивается, поэтому и количество запросов (походов за данными) для них сокращается. Благодаря этому данные можно хранить на твердотельных накопителях (SSD), а не держать в оперативной памяти. Таким образом, поисковая база способна хранить значительно больше документов. Именно ограничения на ранних стадиях ранжирования потребовали внедрения векторных представлений и нейронных сетей, которые позволяют строить легкие для вычислений и при этом очень точные модели.

Контуры скорости

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

Эта база хранится и обрабатывается совсем по-другому, нежели обыкновенная. Ее надо часто обновлять и быстро обеспечивать поиск. Яндекс умеет обрабатывать свежие документы общей формулой ранжирования. Иначе говоря, никакого дополнительного смешивания для свежести не существует. Базовая формула понимает, что произошло некое событие. Следовательно, в поисковую выдачу необходимо добавить свежие документы.

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

***

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

Формирование поисковой выдачи – один из важнейших этапов работы поисковой системы и весьма нетривиальная задача. Решая, как распределить документы внутри выдачи, современные поисковики прибегают к помощи машинного обучения, а именно counter-factual reasoning и counter-factual learning.

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

,