Мы фанаты машинного обучения. Часть 1.

Чем отличаются «бумажные» индексы в книгах от поисковых машин в интернете? Почему обычно поиск работает быстро, но не всегда находит то, что нужно? Можно ли вмешиваться в поиск «вручную»? Что поисковые машины знают о семейном положении пользователей? Наконец, можно ли научить робота разбираться в яблоках? Все это «Лента.ру» попыталась выяснить у Андрея Стыскина, главы отдела ранжирования «Яндекса».

«Лента.ру»: Вы не против, если я начну с азов? Правильно ли я понимаю, что поисковая машина устроена как индекс в книге, где каждому слову соответствует перечисление тех страниц, на которых оно содержится?

Андрей Стыскин: Да, это одна из базовых структур для поиска, хотя и не единственная. Такой индекс (он называется инвертированным) содержит идентификатор слова и перечисление документов, в которых он содержится. В нем же указаны словопозиции, то есть места, в которых в данном документе слово встречается. Знание о словопозиции очень важно для поиска: одно дело — когда слово встречается мельком в одном из абзацев, другое дело — когда оно содержится в заголовке документа.

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

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

Кстати говоря, в индексе записаны не сами слова, а леммы, то есть их основные грамматические формы. Например, если в документе написано «Мой дядя самых честных правил», слово «честных» будет записано как «честный», а рядом будет указан код грамматической формы. Таким образом, базовый лингвистический анализ проводится уже на этапе составления индекса, а не во время поиска.

Получается, что если мы ищем отдельное слово, то результат поиска уже записан в индексе. А если их два или больше? Например, слова «дядя» и «правило» в индексе представлены как отдельные сущности и никак друг с другом не связаны. Как поисковая машина находит те документы, в которых встречаются они оба? Неужели перебирает все подряд?

Во-первых, не все документы надо перебирать. Представьте себе список всех проиндексированных документов по идентификаторам: № 1, 2, 3 и так далее. Этот список обычно отсортирован по степени «полезности» страниц (это называют прюнинг от английского слова pruning). И вот, если само слово «правило» встречается в документе N100, а вместе со словом «дядя» — в N1000, то документы с 1 по 999 можно просто пропустить.

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

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

Среди факторов ранжирования, конечно же, не только количество искомых слов в документе, но и посещаемость сайта, страницы, ссылки на документ, предпочтения пользователей по конкретным запросам.

Для того чтобы это использовать, у нас имеется уже другой индекс — по вероятности перехода на сайты по популярным пользовательским интентам (от английского слова intent — «намерение»), то есть в зависимости от того, что пользователь хочет сделать.

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

Такой список классов популярных интентов составляется вручную?

Нет, конечно, нет. Мы создаем этот список на основании анализа логов поведения пользователя. «Яндекс» получает в день около 200 миллионов запросов, по каждому из которых пользователь кликает — опять-таки в среднем — на два сайта. Логи со всеми запросами мы какое-то время храним в большом кластере, сейчас там что-то вроде восьми петабайт данных.

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

А вы можете отследить, нашел я то, что мне нужно, или просто закрыл сайт?

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

Информацию о переходах вы как получаете?

От браузеров прежде всего. В общем, нам нравится, как работают наши модели предсказания, но точно узнать, нашел ли пользователь то, что ему нужно, совсем не просто.

Как организован процесс улучшения поиска?

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

Далее в дело вступает созданная нами система машинного обучения «Матрикснет». Она ищет некие неочевидные зависимости между разными факторами страницы и тем, насколько асессоры считают ее релевантной определенному запросу.

Для того чтобы объяснить, как она работает, у нас есть следующая рабочая аналогия. Допустим, нам нужно научить робота отличать вкусные яблоки от невкусных. Сам по себе робот не различает вкусы и не может справиться с такой задачей, однако мы можем попросить специального человека разделить тестовый набор яблок на вкусную и невкусную кучки. Имея такие кучки, робот может связать вкус яблок с теми или иными посторонними качествами, например, с цветом кожуры или размером. «Матрикснет» для пар запрос-URL как раз выполняет такую операцию — ищет неочевидные свойства страниц, которые достоверно влияют на ее релевантность относительно определенного запроса.

Вообще говоря, подобное машинное обучение впервые стали использовать в поисковых системах еще в 2000 году, однако «Матрикснет» имеет определенные важные преимущества перед аналогами. Он, например, гораздо более устойчив к так называемому переобучению. Это ахиллесова пята многих систем машинного обучения, она проявляется в том, что системы на малых выборках находят всякие бессмысленные зависимости — например, между релевантностью и цветом шрифта.

Следующие части: