Владимирский Бомж

Снежинск: искусственный интеллект рядом

Источник

10 ноября Яндекс анонсировал новый поисковый алгоритм – «Снежинск». Алгоритм основан на методах, описанных в презентации доклада Яндекса «Greedy function optimization in learning to rank» на RuSSIR-2009. Презентация содержит много математики, которая понятна не всем оптимизаторам, и в этой статье я попробую кратко описать ситуацию со «Снежинском» более простыми словами.

Итак, задача Яндекса - найти такую функцию ранжирования, которая по любому запросу находит самые релевантные этому запросу ответы и выдает их пользователю в правильном порядке, по убыванию релевантности. Построить такую функцию ранжирования вручную не реально, как показала мировая практика, поэтому построение идет автоматически – функция каким-то образом обучается на заранее подготовленных данных. Для обучения «Снежинска» выбран жадный (greedy) алгоритм, особенности работы которого для оптимизатора не важны. Следует только отметить, что такое обучение теперь проходит очень быстро, даже на большом объеме данных относительно большинства других обучающих методов.

Рассмотрим сам процесс обучения. Строится обучающая выборка из пар «запрос-документ», каждой такой паре присваивается значение релевантности. В презентации Яндекса говорится, что это значение из интервала [0..1], но это не принципиально. Такое значение релевантности можно условно назвать «истинной» релевантностью. Как считают эти «истинные» релевантности яндексоиды – не суть важно. Например, самый простой способ получить «истинную» релевантность документа запросу – взять значение релевантности из текущей выдачи Яндекса, работающей по алгоритму «Арзамас». Но, скорее всего, она имеет другие корни, т.к. в противном случае выдача «Снежинска» мало отличалась бы от выдачи «Арзамаса», по крайней мере на обучающих запросах.

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

Для этого яндексоиды в «Снежинске» предложили такой подход: функция ранжирования строится как сумма очень большого числа других функций с некоторыми коэффициентами:

F = a₁*f₁ + a₂*f₂ + … + a_n*f_n

Яндексоиды объявили, что n – несколько тысяч. Обучение в данном случае – это подгонка коэффициентов a₁…a_n. Важными для оптимизатора в данном случае являются не столько коэффициенты a_k (о них ниже), сколько сам вид функций f_k.

В презентации Яндекса можно найти такой пример для функции F:

F = 3:14*log₇(f₉(q; d)) + e^f₆₆(q;d) + …

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

Т.е. определить степень влияния например стат. веса отдельного документа на его место в топе по конкретному запросу – не тривиальная математическая задача даже для Сегаловича, Садовского и Расковалова вместе взятых. И это для отдельного документа, что уж говорить о выдаче в целом. Таким образом, все утверждения сео-аналитиков о том, что в «Снежинске» рулит «траст»|биржи|старые каталоги|возраст домена|статьи|текст документа и т.д. не имеют под собой оснований. Все теперь гораздо сложнее и просчитать влияние отдельных параметров документа на выдачу практически невозможно.

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

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

В заключении стоит отметить любопытные свойства коэффициентов a_k в формуле ранжирования. Так как на них не накладывается никаких ограничений, то они вполне могут быть отрицательными. То есть какие-то слагаемые в функции ранжирования могут давать отрицательный вклад в релевантность. Для примера положим, что для каждого значения тИЦ в формуле ранжирования есть функция, параметром которой будет количество ссылок на документ именно с этим значением тИЦ. И вполне может оказаться, что, скажем, у функции от тИЦ=375 вклад отрицательный. Не зависимо от качества доноров и прочих факторов.

Источник 2.

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

Все понятно? Пока в выдаче доры, австралийские сайты, спам, думаю, подкрутят.

Категории Яндекс алгоритмы | Комментарии (11)

11 комментариев(ия) в “Снежинск: искусственный интеллект рядом”

1. getalifejerk Says:
   ноября 17, 2009 at 18:56

   >> Все понятно?
   Ничего непонятно =)
   Теория одно, а практика - другое. Как минимум потому что в выдаче такой дибилизм. И как следствие на практике этот алгоритм будет существенно отличаться от теоретического, так как его сильно подкрутят.

2. Gena Says:
   ноября 17, 2009 at 19:07

   Всё понятно. Только пару замечаний:

   1. Есть параметры, о которых сторонний человек не узнает. Поэтому в нашей построенной функции будут белые пятна в любом случае.

   2. Вычисление самой функции по данным Яндекса - будет очень сложная и дорогая операция.

   Непонятно, зачем нам знать функцию и коэффициенты?

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

3. Вадим Says:
   ноября 17, 2009 at 21:03

   Понятно, но не всё.

   Как я понимаю, у них нейронная сеть будет с “учителем”… Но кто будет им? Сегодняшняя выдача с дорами и прочим бредом? Наверное, они для начала возьмут её, а потом Платоны будут её потихоньку очищать, обучая нейронную сеть.

4. Курский бомж Says:
   ноября 17, 2009 at 21:37

   Жесть просто… я думал что знаю математику до этого поста))))

   “на основе этих сайтов экспертов строится вся выдача” - вот это не понял совсем… каким образом из обучающей выборки строится вся выдача?

5. Genux Says:
   ноября 17, 2009 at 23:04

   я сегодня анализировал первые результаты данного алгоритма. Это капец. Алгоритм не просто сырой, а совершенно недоработанный. В ближайшие 2-3 недели стоить ждать значительной коррективы алгоритма.

6. Владимирский Бомж Says:
   ноября 17, 2009 at 23:08

   Даже хз, как это комментировать. Но в принципе понятно - дело ясное что дело темное.

7. HenzO Says:
   ноября 18, 2009 at 2:48

   гавнище этот ваш снежинск, все ВЧ продвигаемые сапой попадали с топа на 15+ позиции

8. Weron Says:
   ноября 18, 2009 at 15:06

   Чем мудрить с алгоритмами, сделали бы уже давно редирект на Гугл и люди бы находили все что им нужно без проблем

9. SpYeR Says:
   ноября 18, 2009 at 17:55

   Т.е. теперь с каждым апом выдача сама по себе будет всё лучше и лучше?

10. Александр Says:
    ноября 20, 2009 at 23:04

    Алгоритм действительно сырой. У меня на одном сайте посещаемость увеличилась на 170% ^__^

11. Березниковский Бомж Says:
    ноября 26, 2009 at 9:56

    Вот читаю, читаю, читаю…
    В голове складывается мозаика из кусочков.
    Картина становится все четче и четче. И тут… Случается что то что ломает всю мозаику нахрен.
    А за пост спасибо. Это еще один элемент.

Оставить комментарий