Этот алгоритм ранжирования поисковой системой Яндекс выложен здесь.

Это алгоритм ранжирования выдачи поисковой системы Яндекс под названием Снежинск.

 

Оптимизация «жадных» функций – обучение ранжированию

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

Содержание

 1. Ранжирование в поисковых системах

  • Критерии оценки
  • Характеристическая модель ранжирования
  • Обучение ранжированию. Задачи оптимизации (списочный, точечный, парный подходы).

2. Точечный подход. Аппроксимирование усиленных алгоритмов и «жадной» функции.

3. Изменение MatrixNet

4. Списочный подход. Аппроксимирование комплексных критериев оценки (DCG, nDCG).

Ранжирование поисковой системы.

 

Основная цель: ранжирование документов по степени соответствия поисковому запросу.

Как выполнить ранжирование?

 

Исходные условия:

  • Множество поисковых запросов Q = {q1, .. qn}.
  •  Множество документов, соответствующих каждому из условий q Є Q.

q > {d1, d2, …}

  • Оценки релевантности для каждой пары (запрос, документ) – в нашей модели это вещественные числа rel(q, d) Є [0, 1]

 

Критерии оценки

 

Оценка для ранжирования будет средним значением критериев оценки по множеству поисковых запросов Q:

Пример критериев оценки EvMeas:

  • Точность-10 – процент документов с оценкой релевантности более нуля в топ-10
  • MAP – средняя точность

где k – количество документов с положительной оценкой релевантности, соответствующей запросу q, nr(i) – позиция i-го документа с оценкой релевантности выше нуля.

  • DCG – дисконтированный прирост

где Nq – суммарное количество документов в ранжируемом списке, relj – оценка релевантности для документа на позиции j.

  • nDCG – нормализированный дисконтированный прирост

  • Каждая пара (запрос, документ) описывается как вектор признаков (характеристик):

(q, d) > (f1(q, d), f2(q, d), ..)

  • Поисковое ранжирование – сортировка по значению «функции релевантности». Функция релевантности – это комбинация признаков (характеристик):

fr(q, d) = 3.14 • log7(f9(q, d)) + ef66(q,d)+…

Задачи оптимизации

Как получить хорошую функцию релевантности?

 

Создать опознавательное (обучаемое?) множество примеров Pl – множество пар (q, d) с оценкой релевантности rel(q, d).

Используйте обучение (накопление опытов, опознание?) для создания методов ранжирования для получения fr.

 

Задачи оптимизации (списочный подход)

  • Требуется решить прямую задачу оптимизации:

где F – множество возможных ранжирующих функций,

Ql – множество различных запросов в опознавательном множестве Pl

Сложность решения: большинство способов оценки – не непрерывные функции.

Задачи оптимизации (точечный подход)

  • Упростить задачу оптимизации до задачи регрессии и минимизировать сумму функций потерь:

где L(fr(q, d), rel(q, d)) – функции потерь,

F – множество возможных функций ранжирования.

Примеры функций потерь:

Задачи оптимизации (парный подход)

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

 

  • упорядоченная пара документов (d1, d2) (соответствующая запросу q) принадлежит классу тогда и только тогда, когда rel(q, d1) > rel(q, d2).
  • упорядоченная пара документов (d1, d2) (соответствующая запросу q) принадлежит классу тогда и только тогда, когда rel(q, d1) ? rel(q, d2).

Усиленные алгоритмы и аппроксимация «жадной» функции

Мы решим следующую задачу регрессии:

Будем искать функцию релевантности в следующем виде:

Функция релевантности будет линейной комбинацией функций hk(q, d), функции hk(q, d) принадлежат простой семье H (семейству слабого обучения).

Сконструируем финальную функцию итерациями. На каждой итерации мы будем добавлять к нашей функции релевантности дополнительное ограничение ?khk(q, d):

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

Задача может быть решена непосредственно для квадратичной функции потерь и простого класса H, но решить это для других функций потерь может быть сложно.

Зададим дополнительное условие ?khk(q, d) в три шага:

  • Градиентная аппроксимация. Считать релевантную функцию fr как вектор значений, проиндексированных опознавательными примерами. Взять градиент для функции ошибок:

  • Выбор слабого обучения (с точностью до константы). Найти функцию hk(q, d), наиболее коррелирующее с функцией g решением следующей оптимизационной задачи:

  • Выбор ?k. Найти значение ?k из однопараметрической оптимизационной задачи:

Выбор слабого обучения

Пусть класс слабого обучения H будет множеством функций-деревьев принятия решений:

Это пример тройной функции-дерева принятия решений. Функция разделяет пространство признаков на 3 вершины по условиям в форме fj(q, d) > ? (fj – пространство признаков, ? – граница разделения). У нее есть постоянное значение для вектора признаков на одной вершине.

Выбор слабого обучения (значения функции)

Семья слабого обучения будет шестирной (например, const-уровневый) функцией-деревом принятия решений. Постараемся решить следующее:

Предположим, что мы знаем древовидную структуру слабого обучения h(q, d) – знаем условия разделения и уровни. Мы должны найти «константные значения уровней». Оптимизационная задача сужается до обычной регрессионной задачи:

где ind(q, d) – номер вершины, содержащей вектор признаков для пар (q, d) (ind(q, d) Є {1, …, 6}.

Выбор слабого обучения (древовидная структура)

Выбор «жадного» дерева:

  • bestTree = функция-константа (одновершинное дерево),
  •  «Жадное» разделение. Постараться, разделяя вершины betsTree ,найти наилучшее разделение:

Предположим, у нас есть множество констант возможных границ разделения. Число возможных разделений ограничено значением:

#{вершины} #{признаки} #{границы разделения}

  • Повторить предыдущий шаг.

 

 

MatrixNet (сеть матриц)

Множество слабых обучений – полные деревья принятия решений с глубиной k и количеством вершин 2k.

  • Константное число вершин (константная глубина).
  •  Одинаковые условия разделения на одном уровне:

Нет необходимости в сложной структуре: глубина важнее.

Команда

Время

последнего аплоада

 количество испытаний

Последний результат

(общественная экспертиза)

 Финальный результат

Аппроксимация комплексных критериев оценки (DCG)

Смена ранжирования на ранжирование по параметру вероятности. Аппроксимация DCG для запроса q, множество документов {d1,…dn} и функция ранжирования ft(q, d):

(r – все перестановки множества документов)

P(fr, r) – вероятность получить ранжирование r в модели Luce-Plackett.

DCG(r) – балы DCG для перестановки r.

Модель Luce-Plackett

У нас есть множество документов {d1,…dn} и соответствующее ему множество {fr(q, d1), …, fr(q, dn)}.

Процесс ранжирования выборки в модели Luce-Plackett:

  • Выбрать документ для первой позиции. Вероятность выбора документа di равна . Предположим, мы выбрали документ dx.
  • Выбрать документ для второй позиции. Вероятность выбора документа di равна .
  •  …

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

- некоторая перестановка {d1,…dn}

Вывод:  Для того, что бы сайт появился в ТОП Выдачи поисковой системы Яндекс, придется потрудиться!  Сайты теперь требуется раскручивать только самыми естесственными методами!