Поисковая технология «Спектр»

Доклад был представлен Андреем Плаховым на конференции YaC 2011, которая состоялась 19 сентября 2011 года в московском Центре Международной Торговли.

Для 53% людей ЯК – это животное, для 27% — самолет, для 20% — Яндекс.Каталог. Откуда эти данные известны, и какое значение они имеют для ранжирования Яндекса?

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

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

Как можно улучшить поиск, ведь все простые и сложные вещи уже сделаны? Что такое хороший поиск? Наивный подход: человек, задав свой запрос, должен найти в ТОПе как можно больше правильных результатов. Чтобы это формализовать, довольно давно была придумана стандартная мера информационного поиска – Discounted Cumulative Gain (DCG) – линейно взвешенная релевантность отдельных результатов.

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

Именно это и есть основа для основной метрики Яндекса, которая уже несколько лет используется и называется pFound. MatrixNet, который был внедрен несколько лет назад, отлично строит выдачу, максимизирующую pFound.

В чем же проблема, что хочется улучшить? Эта метрика никак не учитывает, что эти вероятности pRel вовсе не независимы: если мы возьмем 10 результатов и подставим в эту форму, то увидим, что pFound будет очень большой, а никакого нормального человека такая выдача не устроит. Есть отдельный класс запросов, для которых это особенно плохо. Например «МГУ». Не совсем понятно, что хочет найти человек, который ищет «МГУ»: то ли он хочет найти условия приемных экзаменов, то ли список сайтов отдельных факультетов, историю создания, фото главного здания или что-то еще.

Итак, что же такое «Спектр». Это метод, используемый поиском Яндекса на неоднозначных запросах: «МГУ», «Иоанн Павел II», «Черепахи», «Аспирин», «Ягуар». Он запущен в конце 2010 года и работает на 15-20% запросов к Яндексу. Какую метрику мы теперь повышаем, чего мы хотим этим добиться?

Метрика качества: wide pFound.

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

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

Представим себе, что все результаты в десятке отвечают только на один из интентов. Тогда в сумме справа только одно из чисел pFound не нулевое и соответственно вся эта сумма не может быть выше, чем какое-либо wi , что при условии наличия многих интентов не очень хорошо.

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

Но не все так просто. Не все уточнения являются «потребностями», и потому отличаются не только весами, как модели wide pFound – по некоторым из них нужно показывать совсем другие ответы, по-другому строить выдачу. То есть нужно найти способ отбирать правильные расширения, а неправильные не учитывать. Поэтому все-таки придется понимать, о чем люди спрашивают, что это за объект, что про него важно, а что – нет.

Мы сосредотачиваемся на запросах, в которых говорится об объектах из категорий, во-первых, важных для людей, а во-вторых, понятных для нас самих. Они покрывают довольно значимый процент потока запросов, те самые 15-20%, на которых «Спектр» работает. Эти запросы могут быть про фильмы, музыку, людей, лекарства, товары, автомобили, гаджеты.

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

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

Хорошие новости: что вообще происходит, и как мы видим, положительное или отрицательное влияние внедренной технологии. Например, когда внедрили «Спектр», увидели, что стало меньше популярных запросов без кликов и CTR отдельных запросов вырос. Это означает, что эти изменения, в целом, людям нравятся.

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

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

Журналист, новостной редактор, работает на сайте с 2009 года. Специализация: интернет-маркетинг, SEO, поисковые системы, обзоры профильных мероприятий, отраслевые новости рунета. Языки: румынский, испанский. Кредо: Арфы нет, возьмите бубен.