Главная   О компании   Разработки   АТ.Трейдинг  


АТ.Поиск   Сервисы   Форум

Жадные алгоритмы в Яндексе.

Илья Зябрев, Олег Пожарков, 06.03.2010



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

О применении жадных алгоритмов в построении функции ранжирования было рассказано Павлом Карповичем на Российской летней школе по информационному поиску (RuSSIR) 12 сентября 2009 года. Видео доклада:

Презентация доклада: «Greedy function optimization in learning to rank». Для самых пытливых будут полезны статьи Джерома Фридмана: "Stochastic Gradient Boosting." и "Greedy Function Approximation: A Gradient Boosting Machine.".

Начнем с методологической особенности обучающего метода. Любой поисковый алгоритм можно оценить с точки зрения качества его работы. Для этого существуют различные численные метрики (в частности, в докладе Карповича упоминаются MAP, DCG, nDCG). Как правило, чем выше полученная алгоритмом оценка, тем лучше он работает. Поэтому поисковые сервисы заинтересованы в получении таких алгоритмов, оценки качества которых будут максимальны.

В основе поисковых алгоритмов обычно лежит функция релевантности, которая, по сути, оценивает соответствие того или иного документа запросу: чем выше ее значение, тем сильнее это соответствие. Т.е. функция релевантности (fr) - это функция от двух аргументов: запрос (q) и документ (d).

Как работает поисковый алгоритм? Пусть имеется множество документов d1,d2,...dn, среди которых нам требуется найти те, которые дают лучший ответ на некоторый запрос q. Для каждого документа вычисляется его функция релевантности fr(q,di). Ранжируя d по убыванию значения fr(q,d) мы имеем на первых местах полученного списка документы, наиболее соответствующие запросу с точки зрения поискового алгоритма. Именно эти документы образуют ТОП выдачи поисковой системы

Для того, чтобы оценить качество алгоритма ранжирования, используются тестовые выборки документов и запросов. Для каждого тестового запроса производится ранжирование и оцениваются релевантности документов, попавших в некоторый ТОП. Очень важный момент - следует четко различать понятия «функции релевантности» (fr(q,d)) и «релевантности» (rel(q,d)), выставленной асессором. «Функция релевантности» - это оценка, вычисленная поисковым алгоритмом, на основе каких-либо характеристик документа, а «релевантность» - это оценка, обычно выставленная асессором, оценивающим качество работы алгоритма. Естественно если оценки «выставленные» алгоритмом и асессором будут совпадать, то такой алгоритм будет оптимальным, т.к. упомянутые выше численные метрики для таких алгоритмов будут максимальны. Но на практике этого не происходит, и поэтому постоянно ведутся работы по оптимизации поисковых алгоритмов, т.е. получению таких алгоритмов, численные метрики качества которых будут оптимальны.

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

(rel(q,d)-fr(q,d))2,

где rel(q,d)-«истинная» релевантность документа d, относительно запроса q (та, что выставляется асессором)
fr(q,d)-функция релевантности документа d, относительно запроса q (та, что «выставляется» алгоритмом)

Сумма квадратов разностей по всем тестовым парам запрос-документ (q,d) – есть критерий качества алгоритма, который необходимо минимизировать. Нулевое значение этого критерия будет соответствовать случаю, когда оценки релевантности алгоритма и асессора совпадают по всем тестовым данным.

Решение задачи, т.е. поиск функции релевантности fr(q,d) выполняется в виде регрессии, т.е. функции вида:

fr(q,d)=a1h1(q,d)+a2h2(q,d)+...+anhn(q,d),

где а - константы, h(q,d)-некоторые функции, которые являются представителями семейства «слабых алгоритмов обучения» (в оригинале «weak leaners»). Этому семейству ниже будет уделено внимание, которого они заслуживают, т.к. именно в них заключаются некоторые важные особенности работы ранжирующего алгоритма.
n-это число слагаемых, которое по утверждениям Яндекса измеряется как минимум тысячами.

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

Начало математической части.

Итак, постановка задачи поиска функции релевантности в виде регрессии и использование квадрата разности в качестве критерия «близости», позволяет использовать для ее решения простые оптимизационные методы, в частности градиентные. Немного о сути градиентных методов:

Пусть имеется функция от нескольких переменных f(x1,x2,...xN), ее градиентом называется вектор составленный из частных производных, т.е. конструкция вида:

(df/dx1, df/dx2,...,df/dxN)

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

(-df/dx1, -df/dx2,...,-df/dxN)

Направление известно, необходимо сделать по нему шаг. Длина шага при этом определяется значением некоторой константы a. «Движение по направлению, указываемому градиентом» c длиной шага а заключается в следующем. Градиент задает направление, т.е. каждая координата вектора есть абсолютное значение приращения соответствующей переменной, а константа а – есть множитель этого приращения. Т.е. движение по градиенту можно описать формулой (x1,x2,...,xN)= (x1,x2,...,xN)+a(df/dx1, df/dx2,...,df/dxN) или, если расписать по координатам:

x1=x1+a*df/dx1
x2=x2+a*df/dx2
........
xN=xN+a*df/dxN

Значение константы а в зависимости от метода выбирается по-разному. Так, шаг за шагом производится движение к максимуму (минимуму) функции f. Если экстремум найден, то в этой точке градиент будет равен нулю (т.е. все его координаты равны нулю). Обычно точное положение экстремума не ищут и останавливаются в точке, где градиент достаточно близок к нулю.

В нашем случае необходимо минимизировать «сумму квадратов разности», чтобы получить значения функции релевантности как можно ближе к «истинным» значениям релевантности.

L(rel,fr)=(rel(q1,d1)-fr(q1,d1))2+(rel(q1,d2)-fr(q1,d2))2+...+(rel(qM,dN)-fr(qM,dN))2

Суммирование производится по всем парам запрос-документ обучающей выборки, для которых заданы значения «истинных» релевантностей. N - число документов, M - число запросов обучающей выборки.

Рассмотрим шаги алгоритма построения оптимальной функции релевантности.Перед первым шагом функция релевантности еще не существует, т.е. можно записать, что fr0=0 (0 в индексе означает номер шага, на котором получена эта функция).

Для текущего шага k:

Вычисляется градиент L(rel,fr), причем функция релевантности, полученная на предыдущем шаге для каждой пары запрос-документ frk-1(q,d), является аргументом функции L, т.е. градиент принимает вид:

gk=(dL/dfrk-1(q1,d1), dL/dfrk-1(q1,d2),.. dL/dfrk-1(qM,dN))

На первом шаге градиент имеет вид g1=(-2rel(q1,d1), -2rel(q1,d2),..., -2rel(qM,dN)).

Полученный градиент указывает нам направление, двигаясь по которому мы придем к минимуму функции L. Для того, чтобы сделать шаг по этому направлению, нужно найти такую функцию hk(q,d), которая будет как можно ближе к полученному градиенту. В общем случае мы не можем получить функцию, которая во всех своих точках будет совпадать с градиентом, поэтому берется функция, которая как можно лучше соответствует направлению, указываемому градиентом. По сути hk(q,d) – является функциональным приближением градиента на шаге k. Для ее поиска решается задача минимизации выражения:

(gk(q1,d1)-bhk(q1,d1))2+(gk(q1,d2)-bhk(q1,d2))2+...+(g(qM,dN)-bhk(qM,dN))2,

где b-некоторая константа. В результате получаем такую функцию hk(q,d) и константу b, что функция bhk(q,d) на всех парах (q,d) будет как можно ближе к градиенту. Константа b-нужна лишь как решение подзадачи поиска функции hk и в дальнейшем она никак не используется.

Итак, направление движения известно, оно задается функцией hk(q,d). Для того, чтобы сделать шаг, нужно определить его величину ak. Значение выбирается так, чтобы минимизировать значение выражения:

(rel(q1,d1)-(frk-1+akhk(q1,d1)))2+(rel(q1,d2)-(frk-1+akhk(q1,d2)))2+...+(rel(qM,dN)-(frk-1+akhk(qM,dN)))2

Это довольно простая задача, т.к. оптимизируется лишь один параметр ak и методов ее решения большое множество.

Т.е. на шаге k мы получаем функцию релевантности вида frk(q,d)=frk-1(q,d)+akhk(q,d) или frk(q,d)= a1h1(q,d)+ a2h2(q,d)+...+akhk(q,d).

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

Теперь перейдем к самому сложному вопросу - алгоритму поиска «слабых обучающих алгоритмов» или функций hk(q,d). Эти функции ищутся в виде дерева решений. Рассмотрим, что такое дерево решений на сильно упрощенном примере.

Пусть мы имеем сложную функцию y(x), вид которой определить затруднительно и огромный набор обучающих данных yi=f(xi), i=1..N. N-достаточно большое число. Нам нужно найти функцию H(x), которая будет как можно ближе к f(x). В случае если известен вид функции, то задача тривиальна: просто подобрать коэффициенты уравнения. Для этого существует множество методов. Но что делать, если вид функции не известен и сама по себе функция сложная. Например, нам известны следующие пары (х,у) для некоторой функции:

Тогда график функции имеет вид (если просто соединить известные точки линиями, а мы так и сделаем, т.к. информации о том, как ведет себя функция между известными значениями, нам недоступна):

У нас стоит задача по известным значениям получить такую функцию H(X), которая была бы как можно ближе к исходной. Обычно такая задача называется аппроксимацией, а функция, которая получается в результате – регрессией.

Критерием «близости» регрессии к исходным (или можно сказать обучающим) данным обычно выступает сумма квадратов разностей yi и H(xi) по всем возможным значениям x.

Чем меньше значение критерия К, тем ближе регрессия к обучающим данным. Нулевое значение К соответствует полному совпадению y и H(x).

На первом шаге строим самое грубое приближение функции, равное среднему значению У по всей обучающей выборке:

График функции:

В дереве решений наше текущее положение соответствует его корню, и дерево на данной стадии имеет вид:

Значение критерия при этом равно:

Делаем следующий шаг. Разбиваем исходные данные на две непересекающиеся области. Условием для разбиения выступает неравенство x < a1. Если условие для некоторых х выполняется, то соответствующие пары (х,у) объединяются в первую область (левая ветвь дерева решений), если не выполняется – во вторую (правая ветвь дерева решений). Для каждой области также, как и на предыдущем шаге, вычисляются средние значения по всем значениям у принадлежащим ей. а1 выбирается так, чтобы значение критерия на текущем шаге было минимально возможным (методов такого выбора куча, начиная от простого перебора). В нашем случае а1=4
В первую область у нас попадают х=6, х=8 и соответствующие им у=11, у=7.
Во вторую область х=2, х=4 и у=5 и у=2.
Тогда для первой области усредненное значение равно:

Для второй:

Регрессия на текущем шаге имеет вид:

Т.е. функция Н1(X) для всех х больших а1 будет равна С1, и С2 для всех остальных значений х.

На дереве решений функция теперь имеет вид:

Каждой ветви соответствует своя область из тех, на которые мы разбили исходные данные.

Т.е., если нам нужно вычислить значение функции при некотором х, например при х=3, то проверяем выполнение условия х>a1. Оно не выполняется, поэтому спускаемся по правой ветви и получаем значение функции Н(3)=С2.

Значение критерия на этом шаге:

Как видно он значительно уменьшился.

На графике регрессия теперь выглядит так:

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

Для левого узла условием ветвления будет x>a2, где а2=6, для правого узла – х>a3, а3=2.
Т.е. с учетом предыдущего ветвления мы имеем 4 области:
Первая: a2<х, в нее попадает х=8 и у=7.
Вторая: a1Третья: а3Четвертая х<=a3, в нее попадает х=2 и у=5.

Тогда для каждой области среднее значение равно:

Регрессия имеет вид:

А дерево решений теперь выглядит так:

Т.е. теперь вычисляя Н(х=3) мы проверяем два условия: х>6, нет спускаемся вправо, х>2, да спускаемся влево. Значение функции Н(3)=С5.

Значение критерия на этом шаге равно:

Мы достигли минимума, т.е. построение дерева окончено.

График регрессии выглядит так:

Отметим важные моменты.

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

Во-вторых, мы построили дерево до конца, т.е. в каждом узле последнего уровня у нас находится одно из исходных значений у, и поэтому мы добились абсолютного совпадения регрессии с обучающими данными (значение критерия равно нулю). Но у нас было всего 4 обучающих значения, а если бы их был миллион? Тогда дерево имело бы log(1000000,2) ~20 уровней, и 219-1~500 000 условий для ветвления, для каждого из которых нужно было бы искать оптимальную границу а. Чтобы избежать этого, можно задать допустимое значение критерия, при достижении которого построение дерева прекращается или ограничить глубину дерева.

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

Теперь перейдем к конкретике, а именно к построению hk(q,d).

Для каждой пары запрос-документ определено множество свойств: f1(q,d), f2(q,d),...,fn(q,d), n-согласно заявлениям Яндекса несколько сотен (или больше). К этим свойствам могут относиться различные частотные метрики (например, число точных вхождений запроса в текст документа, его заголовок и т.д.), метрики, основанные на анкор-файле документа (например, логарифм количества ссылок на документ, % ссылок, содержащих точное вхождение запроса и т.д.), метрики, основанные на статических свойствах документа или сайта в целом (пэйджранк, возраст документа, возраст сайта, «еще с сайта» и т.д.), а также комбинации этих метрик (например попарные произведения). В сущности, эти свойства выступают, по сути, аргументами каждой из hk(q,d), что означает, что условия ветвления в каждом из узлов определяются на основе fi(q,d). Если в примере выше условия ветвления выглядели как x>a1, х>a2, то здесь они имеют вид f3(q,d)>a1, f100(q,d)>a2 и т.д.

Приведем пример расчета для функции заданной деревом:

Для некоторой пары запрос-документ (q,d) вычисляем значение свойства документа f3(q,d) и проверяем выполнение условия заданного в корне дерева f3(q,d)>a1. Допустим, что условие выполняется, тогда спускаемся по левой ветви, помеченной как «да». Проверяем выполнение следующего условия f100(q,d)>a2, пусть оно не выполняется, тогда спускаемся по ветви помеченной «нет», т.е. по правой и приходим в узел со значением Н2. Т.е. для оцениваемой пары (q,d) значение функции h будет равно H2.

Для алгоритма именуемого MatrixNet имеют место следующие особенности:

  • Глубина дерева ограничивается. По некоторым, слегка противоречивым данным это ограничение равно 6 или 10. Это означает, что каждая функция hk(q,d) имеет 210=1024 или 26= 64 значений.
  • На каждом уровне ветвление осуществляется только по одному условию, т.е. в формировании каждой функции участвует не более 9 (5) признаков fi.

Конец матчасти.

Теперь перейдем к особенностям алгоритма, которые существенны с точки зрения СЕО-оптимизатора, пытающегося максимизировать функцию релевантности своих сайтов.

Во-первых, это кусочно-постоянный характер функций hk(q,d), которая в совокупности с ограниченной глубиной дерева может дать следующий эффект. Документы с незначительно отличающимися значениями свойств могут восприниматься алгоритмом как равнозначные. При этом один документ может быть «чуть более» релевантным относительно другого, однако значение функции релевантности у них будет одинаковым. Для наглядной демонстрации этого вернемся к простейшему примеру, где мы разбирали построение функции, заданной четырьмя парами значений и в итоге значения функции при х=2 и х=3 оказались равны.

Обратная сторона этой медали, документы с незначительно отличающимися свойствами могут иметь сильно отличающиеся значения функций hk. В примере этой ситуации соответствуют значения функции H(3)=2 и H(4)=11. Хотя в целом такие скачки сглаживаются большим числом функций слагаемых hk(q,d).

Во-вторых, это непрямая зависимость функций от свойств документа, которая делает поведение функции релевантности в зависимости от fi(q,d) достаточно сложно предсказуемым с точки зрения внешнего анализа. Это отчасти подтверждается данными приведенными в статье «Статистические методы исследования алгоритмов текстового ранжирования поисковых систем».

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



Нравится


Поисковые исследования:

Алгоритмы ранжирования Яндекса:


 

Copyright AlterTrader Research Ltd. 2004-2017.
All Rights Reserved.

Design: af@altertrader.com