Компания
342,44
рейтинг
26 марта 2013 в 13:06

Разработка → Ранжирование в Яндексе: как поставить машинное обучение на поток (пост #1)

Сегодня мы начинаем публиковать серию постов о машинном обучении и его месте в Яндексе, а также инструментах, которые избавили разработчиков поисковой системы от рутинных действий и помогли сфокусироваться на главном — изобретении новых подходов к улучшению поиска. Основное внимание мы уделим применению этих средств для улучшения формулы релевантности, и более широко — для качества ранжирования.

image
Наша отрасль устроена так, что качеством поиска нужно заниматься постоянно. Во-первых, поисковые компании конкурируют между собой, а любое улучшение быстро приводит к изменению доли рынка каждой. Во-вторых, поисковые оптимизаторы стараются найти слабые места в алгоритмах, чтобы поднимать в результатах поиска даже те сайты, которые менее релевантны запросам людей. В-третьих, привычки пользователей меняются. Например, за последние несколько лет длина среднего поискового запроса выросла с 1,5 до 3 слов.

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

Даже самая простая идея, которая может его улучшить, должна проделать сложный многошаговый путь от обсуждения в кругу коллег до запуска готового решения. И чем более автоматизированным (а значит быстрым и простым для разработчика) будет этот путь, тем быстрее пользователи смогут воспользоваться этим улучшением и тем чаще Яндекс сможет запускать такие нововведения.

Возможно, вы уже читали о платформе распределённых вычислений Yet Another MapReduce (YAMR), библиотеке машинного обучения Матрикснет и основном алгоритме обучения формулы ранжирования. Теперь мы решили рассказать и о фреймворке FML (friendly machine learning — «машинное обучение с человеческим лицом»). Он стал следующим шагом в автоматизации и упрощении работы наших коллег — поставил работу с машинным обучением на поток. Вместе FML и Матрикснет являются частями одного решения — технологии машинного обучения Яндекса.

Рассказывать о FML достаточно сложно, а сделать это мы хотим обстоятельно. Поэтому разобьём наш рассказ на несколько постов:

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

  2. Подбор формулы ранжирования. Вы узнаете о том, как FML стал конвейером по подбору формул (да-да, их много!), чтобы оперативно учитывать большой объём асессорских оценок и новых факторов при минимальном участии человека. А также о созданном в Яндексе кластере на GPU-процессорах, который вполне может войти в сотню самых мощных суперкомпьютеров в мире.
    Разработка новых факторов и оценка их эффективности. Как правило, публикации в сфере машинного обучения уделяют основное внимание самому процессу подбора формул, а разработку новых факторов обходят стороной. Однако сколько бы замечательной ни была технология машинного обучения, без хороших факторов ничего не получится. В Яндексе существует даже отдельная группа разработчиков, занятая исключительно их созданием. Здесь речь пойдёт о том, из чего состоит технологический цикл, в результате которого появляются новые факторы, и каким образом FML помогает оценить пользу от внедрения и себестоимость каждого из них.

  3. Мониторинг качества уже внедрённых факторов. Интернет постоянно меняется. И вполне возможно, что факторы, которые ещё несколько лет назад очень помогли поднять качество, на сегодняшний день утратили свою ценность и впустую расходуют вычислительные ресурсы. Поэтому мы расскажем о том, как FML поддерживает постоянную эволюцию, в которой слабые факторы погибают и уступают место сильным.
    Конвейер распределённых вычислений. Машинное обучение — лишь одна из задач, которые хорошо решает FML. Более широко его применяют для того, чтобы упростить работу с распределёными вычислениями на кластере в несколько тысяч серверов над большим массивом данных, меняющимся во времени. На сегодняшний день около 70% вычислений в разработке Яндекс.Поиска находится под управлением FML.
    Области применения и сравнение с аналогами. FML используется в Яндексе для машинного обучения целым рядом команд и для решения далёких от поиска задач. Мы полагаем, что наша разработка может пригодиться и коллегам по отрасли, имеющим дело с задачами машинного обучения, да и просто с расчётами на больших объёмах данных. Мы обозначим круг задач, для решения которых FML может оказаться полезным и за пределами Яндекса, и сравним его с аналогами, доступными на рынке. Мы также расскажем, как применение FML в CERN может открыть дорогу Нобелевской премии.


Что такое ранжирование и какую задачу оно решает


image
После того как поисковая система приняла запрос пользователя и нашла все подходящие страницы, она должна упорядочить их по принципу наибольшего соответствия запросу. Алгоритм, выполняющий эту работу, и называется функцией ранжирования (в СМИ её иногда называют формулой релевантности). Именно в том, чтобы выделить наиболее важные из найденных страниц и определить «правильный» порядок их выдачи, и заключается задача ранжирования. Его улучшение — первое и главное место, где используются FML и Матрикснет.

Когда-то давно в Яндексе функция ранжирования выражалась одной единственной формулой, подобранной вручную. Её размер растёт экспоненциально (на графике шкала Y — логарифмическая).
image

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

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

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

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

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

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

Почему стандартные методики неприменимы в ранжировании
Однако, даже собрав достаточное число оценок и рассчитав для каждой пары (запрос + документ) набор факторов, построить ранжирующую функцию стандартными методами оптимизации не так просто. Основная сложность возникает из-за кусочно-постоянной природы целевых метрик ранжирования (nDCG, pFound и т.п.). Это свойство не позволяет использовать здесь, например, известные градиентные методы, которые требуют дифференцируемости функции, которую мы оптимизируем.
Существует отдельная научная область, посвященная метрикам ранжирования и их оптимизации — Learning to Rank (обучение ранжированию). А в Яндексе есть специальная группа, которая занимается реализацией и совершенствованием различных методов решения этого достаточно узкого, но очень важного для поиска класса оптимизационных задач.

Итак, функция ранжирования строится по набору факторов и по обучающим данным, подготовленным экспертами. Её построением и занимается машинное обучение — в случае Яндекса библиотека Матрикснет. В следующих постах мы расскажем о том, откуда берутся поисковые факторы, и как всё это связано с FML.
Автор: @yurkennis
Яндекс
рейтинг 342,44

Комментарии (53)

  • +12
    Давненько я не видел новых сайтов в топе по коммерческим запросам. «Машинное обучение»?
  • 0
    Денис, можешь написать, сколько у вас факторов и оценок?

    как на счет актуализации оценок — сколько времени «живут» оценки — перепроверяете ли вы их все, как часто переоцениваете один и тот же запрос, чтобы оценить новые сайты?

    разделяете ли вы как-то оценки на заслуживающие больше доверия (например, перепроверенные старшими асессорами, или по которым не было разногласий между асессорами) и менее?
    • +1
      Денис, можешь написать, сколько у вас факторов и оценок?
      Могу назвать порядок цифр.
      Факторов — порядка тысячи.
      Оценок — миллионы :-)

      как на счет актуализации оценок — сколько времени «живут» оценки — перепроверяете ли вы их все, как часто переоцениваете один и тот же запрос, чтобы оценить новые сайты?

      Да, перепроверяем; да, переоцениваем. Регулярность зависит от частотности запроса.

      разделяете ли вы как-то оценки на заслуживающие больше доверия (например, перепроверенные старшими асессорами, или по которым не было разногласий между асессорами) и менее?
      Мы с этим экспериментируем.
  • 0
    Почему удовлетворенность результатами конечными пользователями не оценивается?
    Может стоит на небольшой выборке тестировать вопросы, по удовлетворенности посещенными сайтами и почему они вернулись к поиску?
    Ведь асессоры это специалисты, но глаз замыливается.

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

    Спасибо в любом случае за попытку показать, как все это работает!
    • +1
      Почему удовлетворенность результатами конечными пользователями не оценивается?
      Может стоит на небольшой выборке тестировать вопросы, по удовлетворенности посещенными сайтами и почему они вернулись к поиску?
      Удовлетворённость пользователей оценивается — с помощью пользовательских метрик. Немного подробней об этом планируем рассказать во втором посте.

      Кстати и что касается консервации топа, в некоторых тематиках он уже 3 года стабилен (топ-10), а это значит, что получается совпали результаты по формуле обычной + машинному обучению + выбору асессоров?
      О каких тематиках идёт речь, например?
  • +1
    Может ли асессор «подсматривать» в поисковики и выставлять оценки не согласно качеству документов, а на основе выдачи поисковиков?

    Например, если документ по данному запросу нигде не находится — асессор ставит плохую оценку.
    Если в Яндексе — отличную, если в Гугле — хорошую.

    Каковы механизмы защиты от такого недобросовестного поведения асессоров?
    • +1
      В момент оценки асессор не знает о том, какие системы оценивает. Да ему и не до этого, среднее время оценки — меньше минуты. За это время посмотреть какая система отдала урл — нереально.
      • 0
        Правильно ли я понимаю, что работа асессора оплачивается за каждую оценку и ему выгодно оценить как можно больше?

        Асессор — это человек работающий в офисе или «на удаленке»?
        • +3
          Если кратко — асессору выгодно делать много качественных оценок. Трудовые отношения с асессором — извините, тут совсем офтопик.
          • 0
            Возможно я ошибаюсь, но общее качество поиска может зависеть от нескольких крупных составляющих.

            Например, как это может быть.

            1) Алгоритм машинного обучения — пусть он работает на 99 процентов от идеального алгоритма
            2) Правильное множество факторов — пусть текущее множество работает на 60 процентов от некоторого воображаемого идеального множества факторов
            3) Оценки асессоров — пусть асессоры дают оценки, которые хуже на 40 процентов от «идеальных асессоров»

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

            В каком-то смысле, хотелось бы в новых Ваших публикациях затронуть проблемы поиска новых факторов и мониторинга асессоров. Это просто пожелание. Возможно, это не узкие места. Тогда забейте.

            За ссылки на Russir и ECIR спасибо, поизучаю.

            • 0
              Давайте мы опубликуем оставшиеся два поста, а по итогу посмотрим, какие из ваших вопросов остались без ответа — годится?
    • 0
      Этим механизмам посвящены немалое число научных и практических работ. Были интересные тьюториалы на RUSSIR из Яндекса года три назад, а сейчас идет конференция ECIR2013 в Digital October, наверняка там тоже есть работы по этой теме
  • +1
    А можно уточнение по картинке — 10^12 и 10^8 это какие документы имеются ввиду: известные URL'ы / скаченные / заиндексированные / потенциально искомые или еще что-то?
    • +1
      Цифры, разумеется, условные — лишь показывают разницу порядков на разных этапах.

      Если же углубляться в смысл картинки:
      — где 10^12 — подразумевались скорее известные УРЛы
      — где 10^8 — грубая прикидка документов, найденных по короткому, простому запросу
  • –1
    Самое забавное, что килобайтная формула в 2007-ом искала лучше, чем этот ваш 40мб матрикснет.
    Ну я понимаю, что рунет с тех пор изменился и вырос, но это именно вы, яндекс, вырастили его таким — забитым на 99% говносайтами разной степени «монетизации» с ворованным/генеренным/авторерайченым контентом.
    Однако самое веселое то, что по коммерческим запросам именно яндекс даёт наилучшие результаты, правда в графе «директ». На результаты нормального поиска по таким зарпосам уже многие внимания просто не обращают. Сколько там байт в формуле ранжирования директа, 7?:)
    • 0
      Не туда написал.
  • 0
    Если матрикснет — это библиотека машинного обучения, интересно знать какую долю от всех запросов рассматривают ассесоры?
    • 0
      В тексте уже звучала цифра:
      В ранжировании эксперты определяют порядок, в котором нужно показывать документы по конкретным запросам. Таких запросов десятки тысяч.

      В процентах, разумеется, это ничтожная доля — потому что уникальных запросов пользователи задают несопоставимо больше.
      • 0
        Уточнить для понимания важно следующее: оценненные запросы ранжируются не по оценкам, отнюдь. Оценки используются только для тренировки, как неизвестных запросов, так и оцененных
    • 0
      Илья добавил важное уточнение: habrahabr.ru/company/yandex/blog/174213/#comment_6057001
  • 0
    В тексте уже звучала цифра:
    В ранжировании эксперты определяют порядок, в котором нужно показывать документы по конкретным запросам. Таких запросов десятки тысяч.
    В процентах, разумеется, это ничтожная доля — потому что уникальных запросов пользователи задают несопоставимо больше.
  • 0
    Мы обозначим круг задач, для решения которых FML может оказаться полезным и за пределами Яндекса, и сравним его с аналогами, доступными на рынке.

    Единичные проекты сотрудничества (как с CERN)? Лицензирование? Опенсорс?
    • 0
      Мы готовы обсуждать формы сотрудничества — пишите на адрес anaderi@yandex-team.ru

      Выпускать в опенсорс не планируем.
  • 0
    Это все прекрасно, но Вам в Яндексе стоит серьезно задуматься о ранжировании дублированного контента в выдаче.
    Наглядный пример мы совсем недавно отправляли в службу поддержки:
    Воры контента сделали точную копию сайта, а именно скопировали весь текстовый контент (несколько десятков тысяч уникальных авторских статей). И мало того, что сайт копипастеров отлично индексируется, так по большей части низкочастотных запросов (фраза из статей) они вылезли выше чем оригинал. Сайту вору уже больше года.
    Поддержка отписывается что Яндекс это зеркало рунета и бла бла бла, но проблему это не решает. Кто угодно может сделать копию ЛЮБОГО сайта, с большей вероятностью появится в поиске и навредить честным людям.
    Ах да, инструмент «Оригинальные тексты» не помогает.

    При всей моей любви к вашей ПС, ваши коллеги из гугла по крайней мере реагируют на такие запросы и убивают дублирующий контент.
    • +1
      А как доказать, кто появился раньше, кто оригинал? То, что на вас раньше кто-то ссылался? Существует неимоверное количество продажных сайтов, и целые их сети для подъёма рейтинга ресурсов за счёт ссылок на них и т.п. А с помощью инструмента «Оригинальные тексты» могут удалить и вас.
      Почему вы вообще считаете, что это работа поисковика разбирать, кто из вас оригинал? Если ваши тексты являются интеллектуальной собственностью, и вы обладаете авторским правом на неё, почему бы вам не решить вопрос в судебном порядке?
      Если вы хотите, чтобы копии не было в поисковиках, вам нужно будет также обращаться и в остальные, зачастую не менее популярные поисковики, а они, насколько я понимаю, далеко не так открыты к людям, как наш любимый Яндекс.
      • 0
        Вопрос часто не в том, кто первый, а в том, что бан и пессимизация накладываются на источник контента, а не на вора. Т.е. в логике банов вопрос «кто был первый, а кто неинтересный дубль недостойный выдачи» очень даже легко решается, причем автоматом и сплеча. А в ранжировании значит трудно решить?
        • +1
          Обсуждаемый вопрос — очень сложная, неразрешенная проблема. На данный момент научное сообщество «тренируется» на соц. сетях в выявлении источников трендов/истории ретвитов. 3 или 4 работы на эту тему были на последнем WSDM. Однако, повторюсь, хорошего, применимого на практике решения пока в природе не существует (как минимум не известно авторам данной статьи). Тем не менее, проблема и боль, которая стоит за подобными сообщениями понятна и как только будет найдено хорошее решение оно будет внедрено.
        • 0
          Раньше для доказательства авторства рукописей достаточно было отправить копию себе заказным письмом до востребования. Возможно, сейчас можно применить платную индексацию на archive.org. И по большому счёту совершенно не задача поисковиков снижать рейтинг копий, а ваша задача следить за копиями, и оперативно пользоваться каким-то механизмом борьбы с источником.

          Например, если на ваш сайт, первый в поисковой выдаче по запросу «Быстрое похудание» будет вести только поисковик, а на другой сайт, вашу копию, тысяча ссылок с блогов и ресурсов из Яндекс.Каталога, то даже если вы докажете, что вы — оригинал, то поможете Яндексу вычислить «продажные» блоги и ресурсы, существующие ради SEO. Но это много, много ручного ресурса.
    • 0
      Добрый день. Не могли бы Вы сообщить адрес сайта? Можно личным сообщением.
  • +4
    Привет оптимизаторам :)!
    • +1
      А не оптимизаторам, а владельцам сайтов? Создание «сайта, интересного посетителю» — интересного профессионального уникального контента — дорогое удовольствие, которое часто не окупается, если траффик идет только с Директа и Гугла, а органический поиск забанил. Например Матрикснет недавно забанил лучший украинский интернет-магазин в своей нише, в результате ошибки в алгоритмах (по словам Платона). Три недели вне поисковой выдачи старый уважаемый магазин терпит убытки. Оптимизиторы-спаммеры-дорвейщики это все хорошо, но Яндекс и Гугл это естественные монополисты от которых зависят судьбы людей в бизнесе и многим тут не до веселых шуток. А ложная сработка руками не убирается так просто и анализ «почему так случилось» может идти неделю. Это ж вам не простая формула, а искусственный интеллект…
      • 0
        Любая классификация (в том числе определение заспамленности или «взрослости» контента) — вероятностная задача, в которой есть полнота и точность (которые никогда не достигают точных 100%).

        Поэтому ситуации вроде ошибочной пессимизации или пропадания были и будут всегда. Мы следим за цифрами в среднем по всему множеству сайтов, и в случае значительных ухудшений ситуации в целом — откатываем алгоритм к предыдущей версии. Заниматься ручным исправлением ситуации с отдельными сайтами по жалобам — с точки зрения пользовательского счастья менее эффективно, чем решать более общую проблему, приведшую к жалобе. А мы работаем прежде всего на пользовательское счастье.
    • +1
      Хорошая статья
      главное — не из рубрики «Превед оптимизаторам!» :)
      ждем продолжение
  • +4
    Пост похож на вкусную затравку, но ничего интересного в статье, а также никаких интересных подробностей по ссылкам на YAMR и Матрикснет.
    Что за СМИ такие, которые называют ранжирование релевантностью, и что за формула, выросшая в 2000 раз за 6 лет — не раскрыто.
    Раз уж решили рассказать, интересно в первую очередь услышать об алгоритмах, используемых для ранжирования тех самых 10^8 найденных документов, сравнения с известными алгоритмами кластеризации; про хранение этих данных и использование их в оперативных запросах; про кеширование результатов.
    На очередной пост наподобии поста про новые нескучные обои возможности Я.Браузера время тратить не хотелось бы.
    • 0
      Начинали они скорее всего с BM25
    • +1
      Статья, как и ее продолжение, не про поисковую систему в целом, а про то как создавать и улучшать одну единственную ее часть — формулу ранжирования. При этом, мы хотим сосредоточиться не на том, какие конкретно скрипты и с какими параметрами запускать, чтобы сделать так же, а на более общих проблемах с которыми мы столкнулись. В частности речь идет о создании экосистемы разработки вокруг задачи ранжирования, что является довольно сложной задачей, если разработкой занимается более 2-х человек.

      Кстати, какого рода сравнение алгоритмов обучения ранжированию с алгоритмами кластеразации вы просите?
      • 0
        Про скрипты вопроса и не было. А что такое формула в принципе не очень понятно, а формула же, занимающая 40КБ, о которой написано в топике — и подавно.
        Было бы интересно про ранжирование, а не экосистему.

        Про сравнение имелось в виду, используете ли вы K-means для первичного отбора, но теперь я понимаю, что это за пределами топика.
        • +1
          K-means не применим в рантайме, так как стучит минимум кубом и вообще не всегда сходится. Более того, в рантайме очень редко используется кластеризация вообще.

          Формула — это набор действий над факторами (числами, характеризующими набор пользователь/запрос/документ), результатом работы которых является число, определяющее порядок ранжирования. Примерами действий могут быть такие: сложить, сравнить с порогом, домножить, заменить и т.п. Мы исходим из того, что размер формулы отражает рост количества этих действий, так как в процессе формат изменяеся не слишком сильно.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Эта статья — отличное начинание, не откладывайте в долгий ящик продолжение, очень интересно будет почитать про оценку удовлетворённости результатами поиска, про пользовательские метрики (как формируются, какие из них используются, а какие нет и почему).
  • +1
    Кластер на GPU вещь хорошая, математику формулах ранжирования быстро считает. Для своего маленького поисковичка тоже 2 видеокарты использую.
  • 0
    Человек-асессор в каждом конкретном случае знает, почему он поставил ту или иную оценку.
    Обучаемый алгоритм — не знает, потому что:
    — все машинные самообучаемые системы на данный момент — «чёрные ящики»,
    — индивидуальные оценки так или иначе обобщаются, но не обобщаются их причины.
    Такой «ослеплённый» алгоритм не в состоянии обработать крайние случаи (причём мы не можем заранее знать, какие именно), и очень слаб в эвристике.
    Однако философская суть поиска — искать то, что еще не известно. А это и есть эвристика и и крайние случаи. Получается, ваш подход к организации ранжирования противоречит сути самого поиска.
    Или я ошибся в логике?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка