10 ноября Яндекс анонсировал новый поисковый алгоритм – «Снежинск». Алгоритм основан на методах, описанных в презентации доклада Яндекса «Greedy function optimization in learning to rank» на RuSSIR-2009. Презентация содержит много математики, которая понятна не всем оптимизаторам, и в этой статье я попробую кратко описать ситуацию со «Снежинском» более простыми словами.
Итак, задача Яндекса - найти такую функцию ранжирования, которая по любому запросу находит самые релевантные этому запросу ответы и выдает их пользователю в правильном порядке, по убыванию релевантности. Построить такую функцию ранжирования вручную не реально, как показала мировая практика, поэтому построение идет автоматически – функция каким-то образом обучается на заранее подготовленных данных. Для обучения «Снежинска» выбран жадный (greedy) алгоритм, особенности работы которого для оптимизатора не важны. Следует только отметить, что такое обучение теперь проходит очень быстро, даже на большом объеме данных относительно большинства других обучающих методов.
Рассмотрим сам процесс обучения. Строится обучающая выборка из пар «запрос-документ», каждой такой паре присваивается значение релевантности. В презентации Яндекса говорится, что это значение из интервала [0..1], но это не принципиально. Такое значение релевантности можно условно назвать «истинной» релевантностью. Как считают эти «истинные» релевантности яндексоиды – не суть важно. Например, самый простой способ получить «истинную» релевантность документа запросу – взять значение релевантности из текущей выдачи Яндекса, работающей по алгоритму «Арзамас». Но, скорее всего, она имеет другие корни, т.к. в противном случае выдача «Снежинска» мало отличалась бы от выдачи «Арзамаса», по крайней мере на обучающих запросах.
Любая функция ранжирования для запроса и документа должна выдать свое значение релевантности документа запросу. И задача обучения – подогнать параметры функции ранжирования так, чтобы выдаваемые функцией значения релевантности были как можно ближе к значениям «истинной» релевантности для всех пар «запрос-документ» из обучающего множества.
Для этого яндексоиды в «Снежинске» предложили такой подход: функция ранжирования строится как сумма очень большого числа других функций с некоторыми коэффициентами:
F = a1*f1 + a2*f2 + … + an*fn
Яндексоиды объявили, что n – несколько тысяч. Обучение в данном случае – это подгонка коэффициентов a1…an. Важными для оптимизатора в данном случае являются не столько коэффициенты ak (о них ниже), сколько сам вид функций fk.
В презентации Яндекса можно найти такой пример для функции F:
F = 3:14*log7(f9(q; d)) + ef66(q;d) + …
Из примера видно, что функции немного «странные». В этом и заключается одна из «фишек» метода – в набор функций включают абсолютно дикие экземпляры, важно, что этих функций очень много. Какой-то логики в этих функциях вообще крайне мало, важно, что любая из них вносит не очень большой вклад в общее значение релевантности. Например, для пары «запрос-документ» число прямых вхождений запроса в текст документа или в анкор-файл документа могут быть параметром в сотнях функций. Это говорит о том, что реальный вклад таких прямых вхождений для конкретного документа вычислить очень сложно даже разработчику алгоритма, тем более, что коэффициенты ak могут меняться после каждого обучения, да хоть и 10 раз в день.
Т.е. определить степень влияния например стат. веса отдельного документа на его место в топе по конкретному запросу – не тривиальная математическая задача даже для Сегаловича, Садовского и Расковалова вместе взятых. И это для отдельного документа, что уж говорить о выдаче в целом. Таким образом, все утверждения сео-аналитиков о том, что в «Снежинске» рулит «траст»|биржи|старые каталоги|возраст домена|статьи|текст документа и т.д. не имеют под собой оснований. Все теперь гораздо сложнее и просчитать влияние отдельных параметров документа на выдачу практически невозможно.
Пути решения проблемы теоретически есть. Для этого нужно создать свою большую обучающую выборку наборов «запрос-документ» и обучать ее на выдаче «Снежинска» на своем большом наборе функций. Такие функции будут, конечно же, сильно отличаться от функций из формулы ранжирования Яндекса, но это не критичный момент, при достаточном объеме обучающего множества задача имеет решения.
И еще несколько слов о перспективах «Снежинска» для Яндекса. В целом такой алгоритм обучения дает вполне приемлемые результаты, но это в целом, дьявол как всегда кроется в деталях. Наверняка есть большое количество запросов, выдача по которым оставляет желать лучшего. Проблема решается добавлением новых пар «запрос-документ» в обучающее множество и новой подгонкой коэффициентов. Если подгонка не дает приемлемого решения, добавляется кучка новых «странных» функций в формулу и обучение начинается снова. В итоге возможны варианты, когда несколько тысяч параметров вырастут со временем до нескольких десятков тысяч, причем вполне вероятна ситуация, когда ни какие танцы с бубном уже не дают улучшения релевантности. Время покажет, на сколько дееспособен такой подход к обучению.
В заключении стоит отметить любопытные свойства коэффициентов ak в формуле ранжирования. Так как на них не накладывается никаких ограничений, то они вполне могут быть отрицательными. То есть какие-то слагаемые в функции ранжирования могут давать отрицательный вклад в релевантность. Для примера положим, что для каждого значения тИЦ в формуле ранжирования есть функция, параметром которой будет количество ссылок на документ именно с этим значением тИЦ. И вполне может оказаться, что, скажем, у функции от тИЦ=375 вклад отрицательный. Не зависимо от качества доноров и прочих факторов. 
Как я понял сейчас алгоритм основан на нейросетевой технологии:
-по сотням или тысячам критериев оцениваются сайты на соот. тем или иным запросам
-выявляются пары релевантные пары: страница-запрос
-которые попадают в обучающую выборку (назовем их эталоны или эксперты)
-на основе этих сайтов экспертов строится вся выдача (по сути это прогнозирование)
-таким образом им не надо писать ф-ию определения релевантности, после обучения нейронной сети они получают несколько готовых ф-ий ранжирования документов
-после чего выбирается из всего множества полученных функций одна с минимальными потерями
-для нее рассчитываются потери (насколько я понимаю - это вероятность или величина ошибки ранжирования)
-на след. итерациях уменьшаются потери и т.д.
Все понятно? Пока в выдаче доры, австралийские сайты, спам, думаю, подкрутят.
Реклама в бомжеленте.
Помогите детям!
[http://bo33.ru/314_snezhinsk-iskusstvennyj-intellekt-ryadom/]
