Предлагаем ознакомиться с документом, ссылку на который представители Яндекса выложили в своем блоге тут (переработка архитектуры ранжирования), при анонсе нового алгоритма ранжирования под названием "Снежинск"
«Жадная» аппроксимация функции и усиленные алгоритмы хорошо подходят для решения практических задач машинного обучения. Мы опишем широко известные усиленные алгоритмы и их модификации, которые используются для решения задач обучения ранжирования.
Ранжирование в поисковых системах
Критерии оценки
Характеристическая модель ранжирования
Обучениеранжированию. Задачи оптимизации (списочный, точечный, парный подходы).
Точечный подход. Аппроксимирование усиленных алгоритмов и «жадной» функции.
Изменение MatrixNet
Списочныйподход. Аппроксимирование комплексных критериев оценки (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 , найти наилучшее разделение:
Предположим, у нас есть множество констант возможных границ разделения. Число возможных разделений ограничено значением:
#{вершины} #{признаки} #{границы разделения}
Повторить предыдущий шаг.
Множество слабых обучений - полные деревья принятия решений с глубиной k и количеством вершин 2k.
Константное число вершин (константная глубина).
Одинаковые условия разделения на одном уровне:
Нет необходимости в сложной структуре: глубина важнее.
Команда
Время последнего аплоада
Количество испытаний
Последний результат (общественная экспертиза)
Финальный результат
Смена ранжирования на ранжирование по параметру вероятности. Аппроксимация DCG для запроса q, множество документов {d1,…dn} и функция ранжирования ft(q, d):
(r - все перестановки множества документов)
P(fr, r) - вероятность получить ранжирование r в модели Luce-Plackett.
DCG(r) - балы DCG для перестановки r.
У нас есть множество документов {d1,…dn} и соответствующее ему множество {fr(q, d1), …, fr(q, dn)}.
Процесс ранжирования выборки в модели Luce-Plackett:
Выбрать документ для первой позиции. Вероятность выбора документа di равна . Предположим, мы выбрали документ dx.
Выбрать документ для второй позиции. Вероятность выбора документа di равна .
…
info@msa.by