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


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

MatrixNet для «чайников».

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



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

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

Презентация доклада: «Greedy function optimization in learning to rank».

Итак, MatrixNet - это метод получения функций семейства «слабых алгоритмов обучения» (в оригинале «weak leaners»), которые в докладе Павла Карповича обозначаются как hk(q,d). Так как мы дали себе зарок не использовать каких-либо формул, то сам алгоритм получения функций hk(q,d) оставим за рамками данной статьи. Здесь же рассмотрим то, что получается на выходе этого алгоритма: функцию hk(q,d), которая задана деревом решений.

Что такое функция, заданная деревом решений? Рассмотрим в качестве простого примера конструкцию, представленную на рисунке 1.


Рисунок 1. Функция одного аргумента, заданная деревом решений.

Каждый узел дерева (жирная черная точка) содержит условие ветвления. Например, самый верхний узел (именуемый корнем дерева), содержит условие x<4. Если значение х, для которого мы хотим определить значение функции действительно меньше 4, то мы спускаемся вниз по левой ветви, т.е. в узел с условием x<2. Из этого узла мы также продолжаем движение вниз, пока не достигнем узла, в котором нет разветвления и вместо условия в нем записано искомое значение функции. Определим по дереву значение функции для х=1:

Начинаем из корня дерева, условие x<4 выполняется? Да. Следовательно, спускаемся по левой ветке.
Условие x<2 выполняется? Да. Опять спускаемся по левой ветке.
Текущий узел конечный, и значение функции в нем равно 1, следовательно f(1)=1.

Повторим операцию для х=2. x<4, да. Идем по левой ветке. х<2, нет. Идем по правой ветке. Значение функции f(2)=2.

Аналогично получаем f(3)=2, f(4)=3, f(5)=3, f(6)=4, f(7)=4, ..., f(10000)=4.

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

  • Она кусочно-постоянная. Т.е. на некоторых интервалах при изменении х, значение самой функции не меняется. Например, при 2<=х<4 (т.е. при х от 2 до 3,999999999....) f(x)=2
  • При переходе х через условие ветвления, функция меняется скачком. Например, f(3,9999999)=2, f(4)=3.
Для наглядности построим график этой функции (рисунок 2.):


Рисунок 2. График функции, заданной деревом решений.

Теперь усложним пример и рассмотрим функцию от двух переменных f(x1,x2) (рисунок 3.):


Рисунок 3. Функция двух аргументов, заданная деревом решений.

Вычислим значение функции для х1=1 х2=1.
Начинаем из корня дерева, условие x1<3 выполняется? Да. Следовательно, спускаемся по левой ветке.
Условие x2<2 выполняется? Да. Опять спускаемся по левой ветке.
Текущий узел конечный, и значение функции в нем равно 1, следовательно f(1,1)=1.
Повторим операцию для х1=2, х2=2. x1<3, да. Идем по левой ветке. х2<2, нет. Идем по правой ветке. Значение функции f(2,2)=2.
Аналогично получаем f(3,1)=3, f(3,2)=4, f(3,3)=4 и т.д.

Теперь рассмотрим пример с hk(q,d). Главное отличие дерева для этой функции от рассмотренных выше в том, что условиями ветвления выступают не аргументы функции (q-запрос, d-документ), а некоторые функции от них f1(q,d), f2(q,d), именуемые признаками документа или свойствами (в оригинале features). В качестве признаков могут выступать: количество точных вхождений запроса в документ, количество точных вхождений в заголовок документа, количество вхождений лемм слов запроса в документ, длина документа и т.д. В общем все то, что Яндекс считает свойствами документа, а также комбинации этих свойств (например произведения). Рассмотрим простенькое дерево для функции h(q,d). (рисунок 4):


Рисунок 4. Пример простейшего дерева для функции h(q,d).

В нашем примере f1(q,d) – TF – число вхождений лемм слов запроса в документ, f2(q,d) – отношение числа вхождений леммы в заголовок документа к длине заголовка, f3(q,d)- отношение числа вхождений леммы в теги H1-H6 к длине текста включенного в эти теги.

Пусть некоторый документ d при запросе q имеет следующие свойства: f1(q,d)=5, f2(q,d)=1 f3(q,d)=0,2. Найдем значение функции h(q,d) для этого документа:
f1(q,d)<10, да. Спускаемся по левой ветви.
f2(q,d)<0,5, нет. Спускаемся по правой ветви.
f3(q,d)<0,2, да. Спускаемся по левой ветви.
Результат h(q,d)=3.

Реальные деревья решений, полученные при помощи алгоритма MatrixNet, обладают следующими свойствами:

  • Глубина (т.е. число горизонтальных уровней или число ветвлений) дерева – число ограниченное. По некоторым данным это ограничение равно 10, т.е. на нижнем (10-м) уровне имеется 210 – узлов соответствующих значениям фунции h(q,d). По другим данным – глубина деревьев равна 6.
  • На каждом уровне ветвление происходит по одному и тому же условию (собственно, только такие примеры мы и рассматривали). Т.е. всего в каждой функции может использоваться не более 10-ти (или 6-ти) признаков документа.

Эти два условия и являются особенностью метода MatrixNet, в отличие от того же TreeNet. Согласно заявлениям представителей Яндекса, MatrixNet зарекомендовал себя лучше, чем TreeNet.

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

Для пояснения этого эффекта рассмотрим два документа d1 и d2, запрос один и тот же q. Каждый из документов имеет следующие признаки первый: f1(q,d1)=2, f2(q,d1)=0,1 f3(q,d1)=0,1, второй: f1(q,d2)=9, f2(q,d2)=0,4 f3(q,d2)=0,2. Определим значения h(q,d), дерево решений которой представлено на рисунке 4, для этих двух документов: h(q,d1)=1, h(q,d2)=1. Как видно, значения признаков отличаются довольно сильно, а значения функции h(q,d) у документов одинаковое.

Обратная сторона этой медали, документы с незначительно отличающимися свойствами могут иметь сильно отличающиеся значения функций hk. Опять рассмотрим два документа с признаками: f1(q,d1)=9, f2(q,d1)=0,4 f3(q,d1)=0,2, второй: f1(q,d2)=10, f2(q,d2)=0,5 f3(q,d2)=0,3. Значения функции h для документов равны h(q,d1)=1, h(q,d2)=8. Разница между значениями признаков у документов незначительна (существенно меньше, чем в предыдущем примере), при этом значения функции h(q,d) отличаются очень сильно.

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



Нравится


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

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


 

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

Design: af@altertrader.com