Просто о сложном. Матрикснет — новое качество поиска Яндекса

07.04.2010

Качество поиска

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

Вот так работает поиск:

Так работает поиск

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

Когда пользователь смотрит на найденные результаты, у него возникает ощущение — ему нашли и показали примерно то, что он хотел, или примерно не то. Это ощущение и описывает качество поиска с точки зрения пользователя — то есть насколько полезны оказались найденные результаты. У разных людей — разные ощущения, и их не всегда можно сформулировать четко. Для улучшения качества поиска нужно измерять и учитывать все эти ощущения в совокупности.

Упорядочивание результатов поиска в соответствии с запросом пользователя называется ранжированием. Именно ранжирование определяет качество поиска — то есть качество ответа на вопрос, заданный в поисковой строке.

Машинное обучение

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

Задача научить машину обучаться существует не только в поисковых технологиях. Без машинного обучения невозможно, например, распознавать рукописный текст или речь. Термин «машинное обучение» появился еще в 50-х годах. Этот термин обозначает попытку научить компьютер решать задачи, которые легко даются человеку, но формализовать путь их решения сложно. В результате машинного обучения компьютер может демонстрировать поведение, которое в него не было явно заложено.

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

Разные типы факторов ранжирования:

Разные типы факторов ранжирования

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

На примере это выглядит так. Допустим, мы хотим научить машину выбирать самые вкусные яблоки. Асессоры в этом случае получают ящик яблок, пробуют их все и раскладывают на две кучи, вкусные - в одну, невкусные — в другую. Из разных яблок составляется обучающая выборка. Машина пробовать яблоки не может, но она может проанализировать их свойства. Например — какого они размера, какого цвета, сколько сахара содержат, твердые или мягкие, с листиком или без. На обучающей выборке машина учится выбирать самые вкусные яблоки — с оптимальным сочетанием размера, цвета, кислоты и твердости. При этом могут возникать какие-то ошибки. Например, поскольку машина ничего не знает про червяков, среди выбранных яблок могут оказаться червивые. Чтобы ошибок было меньше, нужно учитывать больше признаков яблок.

Матрикснет

Машинное обучение применяется в поисковых технологиях с начала 2000-х годов. Разные поисковые системы используют разные модели. Одна из проблем, которые возникают при машинном обучении — переобучение. Переобучившаяся машина похожа на студента, который перезанимался — например, прочитал очень много книжек перед экзаменом по психологии. Он мало общается с живыми людьми и пытается объяснить простые поступки слишком сложными моделями поведения. И из-за этого поведение друзей для него всегда неожиданно.

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

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

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

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

Изменение одного параметра в разных формулах ранжирования:

Изменение одного параметра в разных формулах ранжирования

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

Ранжирование

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

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

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

Примерно так устроено ранжирование:

Примерно так устроено ранжирование