Обучение алгоритму ранжирования и метрикам оценки

Ранжирование — это основной метод рекомендаций, поиска и рекламы, а LTR — контролируемый алгоритм машинного обучения, специализирующийся на задачах ранжирования. Таким образом, LTR по-прежнему является традиционной парадигмой обработки машинного обучения, построения функций, целей обучения, моделей обучения и прогнозирования. LTR обычно делится на три типа: PointWise, PairWise и ListWise. Эти три алгоритма не являются конкретными алгоритмами, а тремя дизайнерскими идеями.Основные различия заключаются в функции потерь, методе маркировки меток и методе оптимизации.

1. PointWise

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

Логика обработки следующая:

PointWise

Детали реализации

Формат обучающих данных - тройки: $(q_i,d_j,y_{ij})$ ,Этикетка $y_{ij}$ — это 2 числа, указывающие на корреляцию/нерелевантность. Обучите модель бинарной классификации или модель регрессии, чтобы она соответствовала напрямую $y_{ij}$ . Функция потерь: функция потерь модели классификации может использовать перекрестную энтропию, а функция потерь модели регрессии может использовать среднеквадратичную ошибку (MSE). Этап прогнозирования; оценка используется непосредственно в качестве ранжирования.

Проблемы с PointWise

PointWise учитывает только корреляцию между запросом и отдельным документом. $sim_{q,d}$ ,Не учитывает взаимосвязь между документами-кандидатами. Поскольку цель, которую мы преследуем, состоит в том, чтобы отсортировать результаты-кандидаты, мы на самом деле хотим вычислитьотносительная оценка, Используйте напрямую $sim_{q,d}$ Сортировка по размеру часто не так точна. Фактически $sim_{q,d}$ Только вероятности точности, а не истинные вероятности относительного порядка.
PointWise не учитывает различия между документами, соответствующими одному и тому же запросу.внутренние зависимости. Это время приводит к следующим проблемам: 1. Выборки во входном пространстве не синхронизируются независимо (IID), что нарушает основные предположения машинного обучения. 2. Когда разные запросы имеют разное количество документов, в общих потерях легко доминируют те группы запросов с большим количеством документов (данные для обучения).
Проблема сортировки фокусируется на точности topk, поэтому в настройку функции потерь необходимо добавить информацию о сортировке относительного положения.

2. PairWise

Основная идея PairWise состоит в том, чтобы сравнивать образцы попарно, строить частично упорядоченные пары документов и узнавать порядок из сравнения. Как показывает анализ в PointWise, для запроса нам нужен правильный порядок извлеченных результатов, а не показатель корреляции между извлеченными результатами и запросом. PairWise надеется получить правильный порядок целого путем правильной оценки порядка пары документов. Например, правильный порядок: «A>B>C», PairWise делает вывод «A>B>C», изучая взаимосвязь между «A>B», «B>C» и «A>C».

Логика обработки следующая: 此处输入图片的描述

Детали реализации

Формат обучающих данных $(q_i,d^+_i,d^-_i)$ , — положительный и отрицательный примеры запроса. Также известен как: (якорь, положительный, отрицательный). PairWise на самом деле является идеей метрического обучения, чтобы напрямую узнать их относительные расстояния, независимо от фактических значений. Функция потери: существует около двух видов, 1: Введите рейтинговый проигрыш пары: $L(r_0,r_1,y)=yd(r_0-r_1)+(1-y) max(0,margin-d(r_0-r_1))$ Значение y равно 0 или 1. 2: Введите потерю триплета или контрастную потерю триплета: $L(r_a,r_p,r_n)=max(0,margin+d(r_a,r_p)-d(r_a,r_n))$ Этап прогнозирования; как и в случае с PointWise, оценка используется непосредственно в качестве ранжирования.

Проблемы с PairWise

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

3. ListWise

И PointWise, и PairWise напрямую узнают, связана ли каждая выборка или связь между двумя положительными и отрицательными выборками, что больше похоже на идею метрического обучения.Оба пытаются вывести результат глобального ранжирования посредством выборочного обучения.Эта идея есть. являются принципиальными недостатками. Основная идея ListWise заключается в том, чтобы попытаться напрямую оптимизировать индикаторы сортировки, такие как NDCG, чтобы получить наилучшие результаты сортировки.

Детали реализации

Формат ввода образца - запрос и все его документы-кандидаты. Как указано: $q_i$ , и его документ кандидата и теги: $C(d_{i1},..,d_{im})$ , $Y(y_{i1},..,y_{im})$ . Этикетка $Y$ Значение — это порядок, в котором представлены все документы-кандидаты. Например, набор кандидатов $\{a,d,c,b,e\}$ , если он находится в естественном порядке, его соответствующая метка $\{5,2,3,4,1\}$ . Обучите модель с помощью различных алгоритмов ListWise. Этап прогнозирования; сортировка по баллам.

ListWise имеет три основные идеи:

Первый связан с мерой

Этот метод предназначен для прямой оптимизации показателей, таких как NDCG. Этот метод является типичным «идеальным очень полным, реальность очень системным», потому что ранжирующие показатели, такие как NDCG, MAP и AUC, являются «непрерывными» в математической форме и «недифференцируемыми» (Non-Different). Дифференцируемое), исходя из этой реальности, обычно есть три решения: Первый способ: найти «непрерывную» и «дифференцируемую» суррогатную функцию, аппроксимирующую показатель NDCG, и оптимизировать NDCG, оптимизируя эту суррогатную функцию. Репрезентативные алгоритмы: SoftRank и AppRank. Второй способ: попытаться математически написать «границу» для таких индикаторов, как NDCG, а затем оптимизировать эту «границу». Например, если получена верхняя граница, то NDCG можно оптимизировать, минимизируя эту верхнюю границу. Репрезентативные алгоритмы: SVM-MAP и SVM-NDCG. Третий метод: алгоритм прямой оптимизации, может использоваться для работы с «прерывистыми» и «недифференцируемыми» индикаторами, подобными NDCG. Репрезентативные алгоритмы: AdaRank и RankGP. 2. Второй не связан с мерой. Этот метод заключается в попытке восстановить порядок в соответствии с известным оптимальным порядком, а затем измерить разрыв между ними, то есть оптимизировать модель, чтобы попытаться уменьшить этот разрыв, например, используя дивергенцию KL в качестве убытка. Репрезентативные алгоритмы: ListNet и ListMLE 3. Третий алгоритм, комбинация ListWise и PairWise Основной целью этого типа метода по-прежнему является оптимизация индекса ранжирования класса NDCG и разработка альтернативной целевой функции.После получения альтернативной функции процесс оптимизации и расчета напрямую обрабатывается определенным методом PairWise. Репрезентативные алгоритмы: LambdaRank и LambdaMART.

Плюсы и минусы ListWise
1. Во многих сценариях сложно построить обучающие данные.
2. Поскольку необходимо рассчитать потери при сортировке, вычислительная сложность обычно выше.
3. На основе достаточных и качественных данных ListWise часто работает лучше, чем PairWise и PointWise, путем непосредственного изучения и оптимизации целевой задачи, то есть сортировки.

4. Общие показатели оценки

nDCG

Объяснение о nDCG

Mean Average Precision(MAP)

В задаче сортировки каждый запрос будет иметь отсортированный список. Как следует из названия, MAP — это среднее значение AP для всех запросов в тестовом наборе.Давайте сначала посмотрим на AP:

$AP(\pi,l)=\frac{\sum^m_{k=1}{P@k*I_{\{ l_{\pi^{-1}(k)}=1\}}}}{m_1}$

в, $\pi$ Указывает список элементов, то есть список результатов отправки. m представляет общее количество списков результатов, $m_1$ Указывает количество элементов, связанных с запросом в списке результатов. $I_{\{l_{\pi^{-1}(k)}=1\}}$ , указывающий, является ли метка в позиции k релевантной, 1 означает релевантную, 0 означает нерелевантную. $P@k$ Это точность топк: $P@k(\pi,l)=\frac{\sum_{t<=k}{I_{\{ l_{\pi^{-1}(k)}=1\}}}}{k}$

Еще одна фигура очень ясна: map.png-176.4kB

Код:

def _ap(ranked_list, ground_truth):
    # ranked_list: 结果列表,如['a', 'b', 'd', 'c', 'e']
    # ground_truth: 相关的item列表，如 ['a', 'd']
    hits = 0
    sum_precs = 0
    for n, item in enumerate(ranked_list):
        if item in ground_truth:
            hits += 1
            sum_precs += hits / (n + 1.0)
    return sum_precs / max(1.0, len(ground_truth))

Ссылаться на

Метрики оценки поиска — NDCG