Чем отличаются «бумажные» индексы в книгах от поисковых машин в интернете? Почему обычно поиск работает быстро, но не всегда находит то, что нужно? Можно ли вмешиваться в поиск «вручную»? Что поисковые машины знают о семейном положении пользователей? Наконец, можно ли научить робота разбираться в яблоках? Все это «Лента.ру» попыталась выяснить у Андрея Стыскина, главы отдела ранжирования «Яндекса».
«Лента.ру»: Вы не против, если я начну с азов? Правильно ли я понимаю, что поисковая машина устроена как индекс в книге, где каждому слову соответствует перечисление тех страниц, на которых оно содержится?
Андрей Стыскин: Да, это одна из базовых структур для поиска, хотя и не единственная. Такой индекс (он называется инвертированным) содержит идентификатор слова и перечисление документов, в которых он содержится. В нем же указаны словопозиции, то есть места, в которых в данном документе слово встречается. Знание о словопозиции очень важно для поиска: одно дело — когда слово встречается мельком в одном из абзацев, другое дело — когда оно содержится в заголовке документа.
Как устроен этот индекс? В книге это просто слово с перечнем страниц, некоторые из них выделяют курсивом или жирным шрифтом.
Индекс — это слово и все словопозиции во всех документах, где оно встречается. Каждая словопозиция кодируется 64 битами, в них зашифрован ID документа (в нашем поисковом индексе только русских документов более 5 миллиардов, еще в два раза больше — на других языках), зона, в которой встречается это слово, номер предложения, номер слова в предложении и несколько служебных битов.
Кстати говоря, в индексе записаны не сами слова, а леммы, то есть их основные грамматические формы. Например, если в документе написано «Мой дядя самых честных правил», слово «честных» будет записано как «честный», а рядом будет указан код грамматической формы. Таким образом, базовый лингвистический анализ проводится уже на этапе составления индекса, а не во время поиска.
Получается, что если мы ищем отдельное слово, то результат поиска уже записан в индексе. А если их два или больше? Например, слова «дядя» и «правило» в индексе представлены как отдельные сущности и никак друг с другом не связаны. Как поисковая машина находит те документы, в которых встречаются они оба? Неужели перебирает все подряд?
Во-первых, не все документы надо перебирать. Представьте себе список всех проиндексированных документов по идентификаторам: № 1, 2, 3 и так далее. Этот список обычно отсортирован по степени «полезности» страниц (это называют прюнинг от английского слова pruning). И вот, если само слово «правило» встречается в документе N100, а вместе со словом «дядя» — в N1000, то документы с 1 по 999 можно просто пропустить.
Во-вторых, находить пересечения страниц не так уж и сложно. Мы сравниваем записи в индексе для слов «дядя» и «правило» и находим общие номера документов. Как правило, на первую страницу попадают только документы, которые находятся ближе к началу списка документов, отсортированных по прюнингу, поэтому до конца искать все пересечения не обязательно.
После того как эти первые пересечения найдены, нужно их ранжировать, или отсортировать, то есть расположить в таком порядке, чтобы более релевантные оказались выше, чем менее релевантные для данного конкретного запроса. От того, как производится ранжирование, собственно, и зависит качество поиска. Когда мы формируем ответ на запрос, для ранжирования результатов используются самые разные факторы. Сейчас у «Яндекса» таких факторов около восьми сотен, и далеко не все они берутся из инвертированного индекса.
Среди факторов ранжирования, конечно же, не только количество искомых слов в документе, но и посещаемость сайта, страницы, ссылки на документ, предпочтения пользователей по конкретным запросам.
Для того чтобы это использовать, у нас имеется уже другой индекс — по вероятности перехода на сайты по популярным пользовательским интентам (от английского слова intent — «намерение»), то есть в зависимости от того, что пользователь хочет сделать.
Например, по одним запросам пользователь хочет с большей вероятностью увидеть энциклопедическую информацию, по другим — мультимедийный контент, по третьим — сделать покупку.
Такой список классов популярных интентов составляется вручную?
Нет, конечно, нет. Мы создаем этот список на основании анализа логов поведения пользователя. «Яндекс» получает в день около 200 миллионов запросов, по каждому из которых пользователь кликает — опять-таки в среднем — на два сайта. Логи со всеми запросами мы какое-то время храним в большом кластере, сейчас там что-то вроде восьми петабайт данных.
Андрей Стыскин
Андрей работает в «Яндексе» с 2007 года, в настоящее время возглавляет отдел ранжирования. Закончил Московский инженерно-физический институт.
Вообще говоря, при наличии этих данных можно тестировать самые разные модели поведения пользователя. Например, не очень показательно, если на сайт просто часто переходят по данному запросу — это может говорить о том, что на этом сайте текст (который видит пользователь в поисковой выдаче) и заголовок удачно составлен. Другое дело, как дальше пользователь взаимодействует с этим сайтом и поисковой выдачей — по этим вещам уже можно судить, нашел ли он там то, что искал.
А вы можете отследить, нашел я то, что мне нужно, или просто закрыл сайт?
Это сама по себе нетривиальная задача, и, кроме того, оценка успешности ее решения всегда очень субъективна. У нас есть некоторые модели, которые пытаются на основании графа переходов пользователя понять, нашел ли он то, что ему нужно.
Информацию о переходах вы как получаете?
От браузеров прежде всего. В общем, нам нравится, как работают наши модели предсказания, но точно узнать, нашел ли пользователь то, что ему нужно, совсем не просто.
Как организован процесс улучшения поиска?
У нас есть текущая формула ранжирования результатов, данные о предпочтениях пользователей, есть специальные люди — асессоры, задачей которых является оценка релевантности. Именно они помогают измерить, какое у нас абсолютное качество поиска сейчас и как оно изменится, если мы в формулу ранжирования введем новую поправку.
Далее в дело вступает созданная нами система машинного обучения «Матрикснет». Она ищет некие неочевидные зависимости между разными факторами страницы и тем, насколько асессоры считают ее релевантной определенному запросу.
Для того чтобы объяснить, как она работает, у нас есть следующая рабочая аналогия. Допустим, нам нужно научить робота отличать вкусные яблоки от невкусных. Сам по себе робот не различает вкусы и не может справиться с такой задачей, однако мы можем попросить специального человека разделить тестовый набор яблок на вкусную и невкусную кучки. Имея такие кучки, робот может связать вкус яблок с теми или иными посторонними качествами, например, с цветом кожуры или размером. «Матрикснет» для пар запрос-URL как раз выполняет такую операцию — ищет неочевидные свойства страниц, которые достоверно влияют на ее релевантность относительно определенного запроса.
Вообще говоря, подобное машинное обучение впервые стали использовать в поисковых системах еще в 2000 году, однако «Матрикснет» имеет определенные важные преимущества перед аналогами. Он, например, гораздо более устойчив к так называемому переобучению. Это ахиллесова пята многих систем машинного обучения, она проявляется в том, что системы на малых выборках находят всякие бессмысленные зависимости — например, между релевантностью и цветом шрифта.
Допустим, система машинного обучения получила некую небессмысленную зависимость, позволяющую улучшить релевантность запроса по оценке асессоров. Что происходит дальше?
Мы выкатываем это изменение в общей формуле ранжирования на части пользователей и смотрим на их реакцию. Делается это по методике, которую мы сами не так давно разработали, FML (friendly machine learning). Упрощенно говоря, делается это следующим образом: берутся два результата ранжирования, по старой (C) и по новой формуле (Н), и перемешиваются по очереди — примерно так же, как отбираются футбольные команды в дворовом футболе. Получаются два варианта «смеси»: С1, Н1, С2, Н2, ... и Н1, С1, Н2, С2, ... где С1 — первый URL по старой формуле, Н1 — первый URL по новой формуле, С2 — второй URL по старой формуле и так далее. Какая «смесь» демонстрируется пользователю, определяется случайно. А далее мы фактически имеем дело с голосованием пользователей за ту или иную систему ранжирования, о котором они сами не знают. При этом мы, конечно, проводим статистический анализ и видим, значимо ли улучшение или нет. Потом эти улучшения вносятся в формулу. В год таких поправок мы вносим где-то около сотни, по несколько штук каждые две недели.
Какие из последних поправок в формулу вы можете привести в пример?
Самые последние я, к сожалению, не могу назвать, потому что мы их еще не анонсировали. Но вот из недавних, например: мы научились для запросов класса «смотреть онлайн» оценивать вероятность того, что пользователь действительно что-то посмотрел на данной странице. Для видеохостингов — узнавать, сколько процентов данного ролика просмотрел пользователь, прежде чем закрыть вкладку. Понятно ведь, что если ролик не стали смотреть, значит он не очень соответствовал ожиданиям.
Поправки в вашу формулу ранжирования недавно пыталось внести и государство. Я имею в виду последние предложения Минкульта, от которых оно уже вроде бы отказалось. Такие пожелания поднимать в поисковой выдаче правильные с чьей-то точки зрения ресурсы вообще реализуемы?
Вообще не реализуемы. У нас же машинное обучение, оно, как зеркало, отражает именно то, что хотят найти пользователи. Мы фанаты машинного обучения, мы вообще никогда не вмешиваемся в поиск «вручную».
Если вы не вмешиваетесь в поиск и у вас есть такая замечательная автоматическая методика проверки качества поиска, то зачем вообще использовать ручные оценки асессоров?
На это есть по крайней мере две причины. Во-первых, люди врут. Они могут искать, скажем, реферат по истории, а переходить при этом на порносайты — это же интереснее. Во-вторых, врут авторы сайтов. Они могут создавать видимость того, что на сайте есть какой-то контент, а на самом деле его там нет. Ведь по сниппету, тому окошечку с фрагментом сайта, который выдает поисковая машина, понять, подходящий ли это сайт, не всегда возможно. Пользователь перешел на сайт, потратил там какое-то время. А нашел он там то, что нужно, или нет — мы не знаем и можем только об этом догадываться.
Еще одна важная проблема при оценке качества — редкие запросы, на которые нет статистики, так называемый длинный хвост. Их на самом деле очень много — из всех запросов около 30-40 процентов приходятся на те, что никто никогда еще не задавал. Поэтому без живых асессоров невозможно понять, насколько качественно работает поиск.
Асессоры оценивают странички выдачи поисковой машины или отдельные URL?
Ни то, ни другое — они оценивают пары запрос-URL, причем в запросе подшита информация о географии пользователя, и эта информация учитывается в оценке. Потому что, условно, релевантный для Екатеринбурга сайт по запросу «ресторан суши» будет нерелевантным для Новосибирска, и наоборот.
Чтобы измерить качество поиска, мы пропускаем случайную выборку запросов через асессоров, которые оценивают пары запрос-URL, выставляя им оценки: «витальный», «важный», «релевантный» или «нерелевантный». Каждой из оценок соответствует некая вероятность того, что человек найдет на этом сайте то, что ему нужно.
И какая страница будет витальной по запросу «погода»? «Яндекс.Погода»?
Нет. На самом деле для такого рода запроса витального URL нет. Под витальным подразумевается страница сети «ВКонтакте» в ответ на запрос «вконтакте». Или соответствующая статья с описанием хоботного млекопитающего на запрос «слон статья из википедии». Витальный URL — это тот, у которого нет разумных альтернативных вариантов, когда совершенно понятно, куда хочет попасть пользователь. На запрос «погода» полезных URL может быть несколько, это и «Гисметео», и «Яндекс.Погода», и несколько других сайтов, каждый из которых получает одинаковую оценку. При оценке сайтов мы ни в коем случае не отдаем предпочтение собственным сервисам.
Что происходит после того, как асессоры оценили релевантность запроса-URL?
Имея ранжированную страницу с результатами поиска, где все URL оценены асессорами, мы оцениваем качество поиска с помощью специальной метрики pfound. Она вычисляет вероятность того, что человек нашел то, что искал на странице выдачи, суммируя такие вероятности для разных URL — каждой из четырех оценок асессора присвоена своя вероятность полезности. При этом в ходе суммирования мы учитываем, что вероятность полезности этой строки нужно умножать на вероятность того, что ее вообще прочитают. То, что нужно пользователю, может найтись в предыдущей строчке, кроме того, он может просто устать и прекратить чтение списка. В общем, получается такая формула суммирования вероятностей, которая и позволяет нам оценивать качество поиска — как своего, так и конкурентов.
Здесь: pRel — релевантность i-того документа (вероятность того, что пользователь найдет ответ в этом документе). pLook — вероятность просмотра i-того документа в выдаче.
Формула pfound оценивает вероятность найти нужную информацию на странице выдачи поисковой машины, суммируя вероятности по отдельным URL.
Итак, с одной стороны, мы имеем метрику для оценки качества поиска, с другой стороны, имеем систему машинного обучения, которая пытается максимизировать эту метрику. Чем больше оцененных запросов мы будем направлять в «Матрикснет», тем лучше будет работать поиск.
Эта метрика, насколько я понимаю, специфична именно для конкретного запроса. А человек ведь не мыслит запросами, он мыслит задачами. Существуют ли способы измерить, нашел ли человек то, что искал, независимо от запроса?
На нашем сленге эта метрика называется «счастье пользователя». Да, такие опыты мы делаем. Выглядит это так: человеку ставят задачу, скажем, найти героев Куликовской битвы. Он может задавать любые запросы, переформулировать их, читать какую-то новую информацию, снова переформулировать запросы. В какой-то момент он находит то, что нужно, и записывает ответ. Мы со своей стороны пытаемся минимизировать то время, которое человек на это потратил.
Все эксперименты, которые мы проводили, говорят о том, что метрика счастья очень хорошо коррелирует с метрикой pfound. То есть пользователь, конечно, ведет себя сложнее, чем подразумевает модель pfound, но данных настолько много, что вся эта сложность усредняется.
Хорошо, а как же тогда персонализация? Если pfound построена на оценках асессоров, каких-то неизвестных мне людей, то как вы можете оценить качество персонализированной выдачи?
Правильно, pfound и нельзя для этого использовать. Но вы же помните, у нас есть метод смешивания разных результатов ранжирования. Если мы вносим в формулу новые, связанные с персонализацией факторы, их эффективность можно проверить именно таким образом.
Допустим, вы любите слушать музыку на одном сайте, а я — на другом. В персонализованной выдаче, когда вы вводите название песни, то получаете ее на том сайте, который любите вы, а я — на том, который люблю я. Результаты выдачи разные, но в обоих в формулу входит предыдущая история посещений страниц. Результаты поиска с учетом и без учета истории можно смешать и посмотреть, какой из них больше нравится пользователям. Опыт показывает, что обычно очень нравится. Особенно это видно на таких классах поисковых задач, когда человек хочет сделать какое-либо действие на привычном сайте, то есть, например, купить что-то, скачать, поиграть в онлайн-игру. То есть если человек привык смотреть кино на определенном сайте, то он очень хорошо находит его в десятке. Когда поисковая машина начинает такие результаты лично для него поднимать в выдаче, он отлично на это реагирует, быстрее находит то, что ему нужно. А другой любит другой хостинг и находит именно его.
Как выглядит пользователь для «Яндекса»? Это просто набор запросов, посещенных сайтов и тому подобного или же это что-то вроде «мужчина от 20 до 30, неженатый, любящий котиков»?
На самом деле и то, и другое. Что касается социальной демографии, то для нее была разработана технология «Крипта». Она основана на том же машинном обучении «Матрикснет», о котором мы говорили ранее. В качестве обучающей выборки использовались поисковые запросы миллиона людей из «Моего круга», где мы знаем пол и возраст человека и эти данные с большой вероятностью соответствуют действительности.
«Крипта» анализирует поисковые запросы и на их основе составляет «социальный потрет» пользователя. Анализ построен на той же системе машинного обучения «Матрикснет», что используется и в совершенствовании ранжирования.
Блог «Яндекса» на Habrahabr.ru
«Крипта» позволяет с неплохим результатом предсказывать пол и возраст человека, и это важно для рекламы, где она и используется. Но каким-то чудесным образом вся эта социальная демография не очень помогает ранжированию. История запросов оказывается здесь гораздо важнее. Она во много раз больше говорит о том, что человек сейчас хочет, чем его пол и возраст.
Очень показательные примеры мы видели с путешествиями. Если, например, человек некоторое время ищет слова «Турция», «Тунис», то потом машина понимает, что при запросе «Мадагаскар» он имеет в виду не фильм, а остров. Все потому, что словам из запроса сопоставляются некие категории в дереве «Матрикснета». С этой точки зрения пользователь «Яндекса» выглядит как разреженное пространство из слов запроса, категорий сайтов, которые он посещал.
Вы недавно запустили технологию так называемой мгновенной персонализации, когда история запросов влияет на ранжирование в пределах одной сессии. Вообще, как соотносится ширина временного окна с релевантностью?
Точно мы этого не знаем, но, по нашим оценкам, 30 процентов профита от персонализации дает учет «длинной» истории поиска, а 70 процентов —учет короткой истории, в пределах одного дня.
Вообще, в исторической перспективе, как менялось качество поиска, если посмотреть на большие времена, скажем, на 10 лет. Были ли в нем, например, всплески, связанные с введением новых технологий?
Качество поиска в человеческом понимании этого словосочетания и у нас, и в мире постоянно растет. Но это плавный рост, никаких особенных всплесков в нем нет. Связано это с тем, что качество прежде всего зависит от наличия в интернете той информации, которую ищет пользователь. Интернет растет, информации становится больше, вместе с ним растет и качество. Я думаю, за последние пять лет даже без учета улучшения технологии поиска значительно выросла вероятность того, что ответ на вопрос пользователя найдется в интернете. Качество самого алгоритма работы поисковых машин тоже растет. У кого-то быстрее, у кого-то чуть медленнее. Но у нас быстрее (смеется).
А нет ли тут эффекта вычерпывания: с каждым разом простых способов улучшения качества поиска становится все меньше и меньше.
Модели, конечно, стали гораздо более сложными, и то, что раньше нам казалось чем-то из ряда вон, сейчас делают стажеры на полставки. Тем не менее каким-то чудесным образом темп роста удается выдерживать. Мы постоянно вносим новые факторы и одновременно с этим совершенствуем систему машинного обучения. Сочетание того и другого дает постоянный рост — с 2011 года, например, качество поиска росло вообще почти линейно. В 2009 году было исключение, заметный скачок, связанный с внедрением «Матрикснета».
Интересы пользователей поисковиков склонны меняться: зимой их интересует «мороз», а летом — «жара».
Google Trends
Если смотреть на большие времена, то надо понимать, что и само понимание качества поиска и качества ранжирования сильно меняется.
То есть факторы ранжирования, которые вы находите, имеют весьма ограниченный срок годности?
Конечно. Например, существуют поисковые оптимизаторы, люди, которые пытаются обмануть поисковую машину и поднять определенный URL в выдаче. У нас есть целый отдел для борьбы с таким явлением. Возьмите хваленый алгоритм pagerank, анализирующий граф ссылок на страницах. Когда оптимизаторы поняли, как он работает, сеть стала просто забита ссылками, и сейчас pagerank не имеет практически никакого смысла.
Но главное — что мир меняется, потребности людей сильно меняются. Хорошее ранжирование по сложной формуле образца 2013 года будет плохим для пользователя образца 2005 года. Достаточно сравнить то, как в последние годы поменялись запросы вроде «приложения для телефона». Пользователи меняются, им нужно разное, поэтому и ранжирование будет разным.