Блог

Многорукие бандиты ранжируют результаты поиска Яндекса

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

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

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

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

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

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

Это приводит нас к двум различным ранжирующим стратегиям: обменную, предназначенную, на каждом шаге для улучшения ранга текущей поисковой цепочки, и, исследовательскую, позволяющую собрать больше оценок со стороны пользователей для страниц с низким рангом, правда ценой ухудшения качества поиска по целому ряду запросов. Что особенно важно - достичь оптимального взаимодействия между этими двумя стратегиями, которые максимизирует совокупное качество серии последовательных запросов к поисковой системе. Мы назовем эту задачу OLREE (Online Learning to Rank with Exploration and Exploitation, Онлайн Обучение Ранжированию с Перестановкой и Исследованием). Это является частным случаем известной задачи об исследовании-перестановке, наиболее правильно сформулированной в вероятностной модели многоруких бандитов (SMAB). Эта задача известна в такой постановке: игрок стоит перед рядом одноруких автоматов в казино, и задача такого автомата - оценить вероятность выдачи выигрышной комбинации на основе поведения игрока (он переходит от одного к другому и исследует их, дёргая рычаги один за другим). На каждом таком переходе, алгоритм такого автомата балансирует между полностью перестановочном и полностью исследовательским поведением игрока.

Авторы этого подхода исследовали наиболее многообещающий подход к решению задач, стоящих перед обучаемой поисковой системой в терминах вероятностной модели многоруких бандитов (SMAB).

И вот краткая выжимка того, что у них получилось:



- они назвали это Алгоритм Многоруких Бандитов (как адаптацию SMAB).

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

Все подобные правила, с которыми проводились эксперименты, основаны на Клико-Зависимой Модели (DCM), успешно применяемой в изучении задачи однорукого автомата для ранжирования результатов вэб-поиска. Для того чтобы заменить DCM другой моделью, учитывающей клики, нужно определиться с каким-то правилом, основанном именно на кликах. Наиболее продвинутые модели основаны на каскадных гипотезах. Всегда подразумевается, что успешные клики напрямую учитываются поисковой машиной, а исследовательские - нет, как это и бывает на практике. Алгоритм ничего не может получать из прерванных сессий поиска (без кликов), не только потому что они не могут быть объяснены на основе DCM в случае реального пользователя, но и потому что причины его отказов как правило, не известны.

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

Есть и противоположный подход, например, Radlinski и др. (ICML ’08, pages 784–791, New York, NY, USA, 2008) использовали выделенный экземпляр алгоритма однорукого бандита для каждой позиции в поисковой выдаче, то есть принимали во внимание только обратную связь с пользователем при клике на документ. Хотя это позволило им увеличить разнообразие SERP'a, это не может быть хорошим решением в нашем случае. Нам показалось рациональным распространить оценки пользователей на все документы в поисковой цепочке по запросу. Для этого и использовался SMAB, в том виде, как это показано выше.

Следует отметить, что при тестировании этого подхода на реальных поисковых цепочках, проведенное в течение двух недель в ноябре 2013, для случайно выбранных результатов поиска (порядка 0.003% всего объема), удалось разнообразить SERP и получить для него стабильную выдачу в течение 10 дней после запуска этого обучающего алгоритма.

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

Этот материал - попытка краткой выжимки публикации, представленной Яндексом на конференции в Италии "Gathering Additional Feedback on Search Results by Multi-Armed Bandits with Respect to Production Ranking" by Aleksandr Vorobev, Damien Lefortier, Gleb Gusev, and Pavel Serdyukov.