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

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

Предварительный опрос населения показал что:

• 53% считают ЯК – это животное
• 27% - самолет
• 20% - Яндекс.Каталог

Какое значение эти данные имеют для ранжирования Яндекса?

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

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

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

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

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

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

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