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


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

Моделирование алгоритма текстового ранжирования Яндекса при помощи MatrixNet.

Илья Зябрев, Олег Пожарков, Ирина Пожаркова, доклад на конференции PROOFSEO 30.06.2010



Видео доклада:

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

Основные особенности поисковых алгоритмов Яндекса, основанных на методе MatrixNet.

Для начала определим, что такое MatrixNet и каково его место в обучении функции релевантности. В жадном алгоритме оптимизации, используемом Яндексом, функции релевантности документа d относительно запроса q выглядит следующим образом:

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

MatrixNet это метод получения функций семейства «слабых алгоритмов обучения» (или «weak leaners»), которые в формуле (1) обозначаются как hk(q,d). Алгоритм получения функций hk(q,d) в виду его сложности оставим за рамками данного доклада. Нужно только заметить, что количество функций hk(q,d) достаточно большое, десятки тысяч. Коэффициенты ak – малые величины. Теоретически возможны варианты, когда младшие аk достаточно большие, но практика показала, что это не так. И аk могут быть меньше нуля, т.е. некоторые слагаемые дают отрицательный вклад в релевантность. Обучение проходит на базе оцененных пар (запрос, документ), число которых скорее всего уже больше 5 миллионов. Для понимания особенностей работы ранжирования Яндекса гораздо большую ценность представляет то, что получается на выходе этого алгоритма: функции hk(q,d), которые заданы деревьями решений.

Что такое функция заданная деревом решений.

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

Рисунок 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. График функции, заданной деревом решений.

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

Рисунок 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. Пример простейшего дерева для функции h(q,d).

В нашем примере f1(q,d) – количество вхождений лемм слов запроса в тег body, f2(q,d) – плотность лемм запроса в теге body, f3(q,d)- количество вхождений лемм запроса в заголовок документа. Следует заметить, что в наших примерах значения функций возрастают слева на право. Это сделано для простоты восприятия, на самом деле они могут быть перемешаны как угодно. Так же уточним, что все условия ветвления взяты наобум и не следует воспринимать их, как руководство к действию.

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

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

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

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

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

Таблица 1. Значение функции h(q,d) для разных параметров.
ПараметрДокумент 1Документ 2Документ 3
f1 – кол-во ключа в body1910
f2 – плотность в body0.5%4,9%5%
f3 – кол-во в title023
h(q,d)118

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

Корреляционные методы исследования ранжирующих алгоритмов.

В одном из наших докладов [1] была рассмотрена простая технология исследования влияния различных факторов на ранжирование Яндекса при помощи парного корреляционного анализа. Суть методики заключается в том, что для различных числовых метрик (свойств) документа строятся ранговые коэффициенты парной корреляции, которые позволяют оценить статистическую связь между исследуемым признаком документа и его положением в топе поисковой системы: чем выше коэффициент корреляции, тем сильнее связь.

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

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

Например, в нашем докладе [1], посвященном статистическим методам анализа алгоритмов поисковых систем, различные элементарные метрики имели довольно высокий коэффициент парной корреляции применительно к алгоритму Яндекса, действующего на момент проводимого исследования (октябрь 2009 года) (Таблица 2). С запуском Снежинска (первой версии ранжирующего алгоритма, построенного при помощи MatrixNet) коэффициенты корреляции сильно ухудшились (Таблица 3).

Таблица 2. Коэффициенты корреляции для различных свойств до запуска Снежинска.
Параметр12345678
гонор-0,523-0,495-0,644-0,484-0,673-0,549-0,497-0,097
банальность-0,3890,181-0,6380,173-0,6920,195-0,1840,083
клюв-0,712-0,249-0,654-0,246-0,674-0,250-0,241-0,046
зло-0,6280,318-0,6600,317-0,7070,3450,290-0,551
струпья-0,679-0,694-0,759-0,650-0,783-0,765-0,669-0,095
маньяк-0,417-0,635-0,738-0,601-0,861-0,687-0,694-0,322
подзатыльник-0,676-0,635-0,748-0,657-0,826-0,684-0,640-0,095
традиции-0,604-0,578-0,785-0,629-0,818-0,629-0,581-0,467
ученый-0,736-0,539-0,784-0,533-0,850-0,543-0,537-0,371
выдумка-0,405-0,660-0,827-0,667-0,905-0,713-0,698-0,582

Таблица 3. Коэффициенты корреляции для различных свойств после запуска Снежинска.
Запрос12345678
гонор-0,234-0,210-0,289-0,196-0,286-0,196-0,204-0,038
банальность-0,1570,074-0,2710,067-0,2920,076-0,0780,031
клюв-0,282-0,097-0,246-0,106-0,275-0,094-0,109-0,019
зло-0,2830,131-0,2560,126-0,2630,1420,127-0,220
струпья-0,306-0,255-0,286-0,260-0,347-0,293-0,267-0,039
маньяк-0,151-0,254-0,329-0,249-0,346-0,305-0,308-0,133
подзатыльник-0,300-0,229-0,318-0,268-0,344-0,249-0,277-0,035
традиции-0,217-0,241-0,326-0,281-0,346-0,246-0,213-0,173
ученый-0,334-0,218-0,313-0,201-0,322-0,198-0,242-0,133
выдумка-0,146-0,273-0,366-0,259-0,347-0,258-0,316-0,220

Использование множественного корреляционного анализа, который позволяет исследовать одновременное влияние групп факторов, дает положительные результаты. Но это тема для отдельной статьи.

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

Исследование поисковых алгоритмов Яндекса при помощи MatrixNet.

Алгоритм MatrixNet предназначен для того, чтобы по известным релевантностям и свойствам документов относительно запросов создать ранжирующую функцию. Аргументами такой функции являются значения свойств документов, значением функции – их релевантности. Наша цель – построить свою функцию текстовой релевантности, и нашем случае ситуация похожая. Естественно, мы не знаем абсолютных значений релевантностей документов из топов выдачи Яндекса и тех их свойств, которые учитываются при ранжировании. Однако, согласно местам сайтов в выдаче, мы можем определить их относительные релевантности: чем выше сайт в топе, тем выше его релевантность. А что касается числовых характеристик документов, то их мы можем выделить на свое усмотрение столько, сколько понадобится. Функция, построенная при помощи MatrixNet на основе известного топа и выделенных нами свойств, будет по своей сути моделью ранжирующего алгоритма Яндекса, позволяющей эффективно решать исследовательские задачи.

Выделим основные этапы создания модели:

  • Создается подборка запросов, максимально исключающая влияние ссылочного фактора. Например, запросы из непопулярных слов или запросы, задающие поиск по одному сайту. Чем больше различных запросов используется для проведения анализа, тем выше будет адекватность построенной модели.
  • Подбираются свойства (числовые характеристики) документов, которые предположительно влияют на ранжирование сайтов. Обычно это делается на основе проведенных предварительных наблюдений или возникающих в процессе исследования поисковых систем гипотез. Далее, для каждого сайта из топа Яндекса по выбранным запросам вычисляются значения каждого из свойств.
  • Синтезируется ранжирующая функция по жадному алгоритму на основе MatrixNet.

Для более качественного построения модели необходимо большая обучающая выборка запросов и документов, а также большое число различных метрик. В нашем случае выборка делалась совместно с аналитическим отделом сервиса ROOKEE. Мы проанализировали 1100 запросов и около 22 000 документов, исключая из исследований сайты с влиянием ссылочных факторов, как внешних, так и внутренних. 1000 запросов было использовано для обучения модели, 100 запросов – для проверки качества полученной ранжирующей функции.

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

Приведем самые существенные с точки зрения влияния на итоговую функцию (по результатам моделирования) метрики:

  • TF(L,d) – вхождение леммы L в документ d
  • CF(L) – число вхождений леммы L в коллекцию
  • D – общее количество документов в коллекции
  • DocLen(d) – длина документа d
  • Сумма производится по всем лемма запроса q

  • L1+L2-пара лемм из запроса
  • TF(L1+L2,d) – вхождение пары лемм в документ

  • Суммирование производится по всем леммам запроса, присутствующим в документе.
  • Nmiss –число лемм запроса, отсутствующих в документе

  • TF(q,d) –вхождение запроса q целиком в документ d

Метрики W1-W5 были предложены Андреем Гулиным, Михаилом Масловым и Ильей Сегаловичем в [2].

  • DF(L) – количество документов коллекции, в которых встречается лемма L
  • ADL – средняя длина документа коллекции

Метрика W6 - классическая BM25 ([3]).

  • P(L,d) – позиция леммы L в документе d.
  • LMD(p, L, d) – расстояние от позиции p до ближайшей слева леммы L в документе d.
  • RMD(p, L, d) – расстояние от позиции p до ближайшей справа леммы L в документе d.

Метрика W7 была предложена Александром Сафроновым в [4].

  • Pr – предложение документа d.
  • |Pr| - длина предложения Pr.
  • ICLF(L,v) – обратная условная частота леммы [5].
  • CLF(L,v) – число документов коллекции, в которое лемма L входит v раз.

  • %CLF – число документов коллекции, в которых лемма L имеет плотность v.

Метрики применяются к различным областям документа, размеченным тегами: title, body, h1-h6, a и т.д., а также к информационной области документа и к началу документа.

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

Заключение.

В заключении опишем возможности рассмотренного подхода.

Во-первых, это исследование влияния различных свойств документа на его положение в топе. Имея модель ранжирующего алгоритма, можно, меняя параметры документа, исследовать изменение его релевантности. Например, для исследования некоторого признака F1 из запроса для некоторого документа фиксируем все параметры кроме F1, значение которого меняем в достаточно большом диапазоне. В результате получим некоторую зависимость «релевантности» документа от F1 слова из запроса. А для исследования характера зависимости можно использовать обычный парный корреляционный анализ. Если поменять один параметр, не изменяя другие, невозможно (например, внутренняя частота леммы слова TF), то в таком случае применим множественный корреляционный анализ, который учитывает изменения связанных с TF факторов.

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

Построенную модель мы оценили при помощи парного корреляционного анализа, где в качестве единственного фактора влияющего на ранжирование выступала наша функция релевантности. Результаты анализа представлены в таблице 4.

Таблица 4. Результаты корреляционного анализа построенной модели
ЗапросРанговый коэффициент парной корреляции
гонор-0,987
банальность-0,988
клюв-0,992
зло-1
струпья-0,979
маньяк-0,987
подзатыльник-0,994
традиции-0,979
ученый-0,988
выдумка-0,996

Полученные коэффициенты, по модулю близкие к 1, говорят о достаточно сильной связи между построенной нами моделью и ранжированием Яндекса.

Литература:

1. Статистические методы исследования алгоритмов текстового ранжирования поисковых систем. Илья Зябрев, Олег Пожарков. 2009.
2. Алгоритм текстового ранжирования Яндекса на РОМИП-2006. Андрей Гулин, Михаил Маслов, Илья Сегалович. 2006.
3. The Probabilistic Relevance Model: BM25 and beyond. Stephen Robertson, Hugo Zaragoza. 2007.
4. HeadHunter на РОМИП-2009 Александр Сафронов. 2009.
5. Спектральное оценивание лексических единиц в задачах лингвистического моделирования. Илья Зябрев, Олег Пожарков. 2009.



Нравится


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

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


 

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

Design: af@altertrader.com