[Система рекомендаций] Модель прогнозирования CTR (1): LR+GBDT

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

1. Определение CTR

Оценка CTR может быть абстрагирована как проблема бинарной классификации. Задача, которую он решает, заключается в следующем: при наличии запроса и объявления, соответствующего запросу, предсказать вероятность получения клика после показа объявления. Ярлык можно получить из фактических данных о доставке. В исторических результатах доставки запись о клике помечена как 1, а реальный остаток помечен как 0.

ctr_1

На рисунке выше схематически представлена запись данных обучения/тестирования в модели оценки рейтинга кликов. В поле слева перечислены характеристики, соответствующие этой записи данных, включая пользователя (теги пользователя), контекст (дата, город, рекламный обмен, домен, ...), рекламодателя (идентификатор объявления), объявление (размер объявления) и другие. связанные особенности. В тренировочной записи, если запись наконец-то щелкнула, она записывается как 1, в противном случае записывается как 0; при прогнозировании локтя нам нужно предсказать вероятность нажатия на эту запись, то есть CTR (Click-Through Rate). ).

2. LR+GBDT

Эта модель представлена Facebook в их статье 2014 года для решения проблемы комбинации функций модели LR с помощью модели GBDT. Идея очень проста.Разработка функций разделена на две части.Одна часть функций используется для обучения модели GBDT.Номер конечного узла каждого дерева модели GBDT используется как новая функция,добавляемая к исходной набор функций, а затем модель LR используется для обучения окончательной модели. Основным ориентиром для оценки CTR до этой модели была логистическая регрессия (LR).

2.1 LR

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

Структура модели: $f\left ( x \right )=w_0+\sum_{i=1}^{n}w_ix_i,y=sigmoid(f(x))$

целевая функция: $J(w)=-\frac{1}{m}\sum_{i=1}^{m}(y^i\log f_w(x^i)+(1-y^i) \log(1-f_w(x^i)))$

Преимущество:

Модель проста и имеет определенную степень интерпретируемости.
низкая вычислительная сложность времени
Инжиниринг можно массово распараллелить

недостаточный:

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

2.2 GBDT

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

Полное название GBDT — дерево решений с повышением градиента. Сначала обучите начальное дерево решений как $f_{t-1}(x)$ , функция потерь $L(y,f_{t-1}(x))$ , то текущий целевой номер итерации находит обучаемый дерево регрессии CART $h_t(x)$ , пусть функция проигрыша этого раунда $L(y,f_{t}(x))=L(y,f_{t-1}(x)+h_t(x))$ минимум. То есть дерево решений, найденное в этой итерации, должно минимизировать потери выборки. И окончательный результат прогноза — это сумма значений прогноза всех деревьев.

Алгоритм повышения дерева

Повышенное дерево инициализируется первым $f_0(x)=0$ ,
за $m=1,2,...,M$
1. тогда остаток $r_{mi}=y_i-f_{m-1}(x),i=1,2,...,N$
2. подходят остатки $r_{mi}$ Изучая дерево регрессии, получаем $h_m(x)$
3. возобновить $f_m(x)=f_{m-1}(x)+h_m(x)$
получить усиленное дерево для задачи регрессии $f_M(x)=\sum_{m=1}^{M}h_m(x)$

Предположим, что сильный ученик, полученный на предыдущей итерации, $f_{t-1}(x)$ , функция потерь $L(y,f_{t-1}(x))$ , то целевое число этого раунда итераций находит слабого ученика $h_t(x)$ Свести к минимуму потери в этом раунде

\arg \min L(y,f_t(x))=\arg \min L(y,f_{t-1}(x)+h_t(x))

При использовании квадрата разницы в качестве функции потерь

L(y,f_{t-1}(x)+h_t(x))\\=(y-f_{t-1}(x)-h_t(x))^2\\=(r-h_t(x))^2

здесь $r$ Это остаток, поэтому повышающему дереву нужно просто подогнать остаток текущей модели, чтобы достичь цели минимизации функции потерь.

Повышение градиента

в $t$ круглый $i$ Функция потерь выборок - это когда выбрана квадратичная функция потерь.

-\left [\frac{\partial L(y,f(x_i))}{\partial f(x_i)} \right ]_{f(x)=f_{t-1}(x)}=y-f(x_i)

В это время будет обнаружено, что отрицательный градиент GBDT является остатком, который также является остаточным приближением алгоритма подъемного дерева, предложенного Фридманом, с использованием отрицательного градиента функции потерь. Модель регрессии GBDT должна соответствовать остаткам,

Алгоритм регрессии GBDT

Обучающие образцы $T={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)}$ , максимальное количество итераций T, функция потерь L

Инициализируйте слабого ученика: $f_0(x)=\arg \min _c\sum _{i=1}^{N}L(y_i,c)$
правильно $t=1,2,...,T$ имеют:

1) Для каждого образца $i=1,2,...,m$ , вычисляет отрицательный градиент (остаток)

$r_{ti}=-\left [\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right ]_{f(x)=f_{t-1}(x)}$
1. Остаток, полученный на предыдущем шаге, используется как новое истинное значение выборки, и данные $(x_i,r_{ti}), i=1,2,..m$ Сопоставьте дерево регрессии CART, чтобы получить первое $t$ дерево регрессии $f_{t} (x)$ Соответствующая ему площадь листового узла равна $R_{tj}, j =1,2,..., J$ . в $J$ — количество листовых узлов дерева регрессии t.
2. на площадь листа $j=1,2,...,J$ Рассчитать наилучший вариант
$c_{tj}=\arg \min _c\sum_{x_i \in R_{tj}}L(y_i,f_{t-1}(x_i)+c)$
1. Обновление сильного ученика
$f_t(x)=f_{t-1}(x)+\sum_{j=1}^{J}c_{tj}I(x \in R_{tj})$
стать сильным учеником $f(x)$ выражение
$f_t(x)=f_{T}(x)=f_0(x)+\sum _{t=1}^{T}\sum_{j=1}^{J}c_{tj}I(x \in R_{tj})$

Алгоритм классификации GBDT

Идея алгоритма классификации и алгоритма регрессии одинакова, но вывод выборки не является непрерывным значением, поэтому ошибка вывода категории не может быть подобрана непосредственно из типа вывода. Тогда функция потерь, используемая в алгоритме классификации, имеет видЭкспоненциальная функция потерьифункция потерь логарифмического правдоподобия. Последний используется во второй классификации (вторая классификация в модели GBDT+LR).

L(y,f(x))=log(1+\exp(-yf(x)))

Тогда ошибка отрицательного градиента равна

r_{ti}=-\left [\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right ]_{f(x)=f_{t-1}(x)}=\frac{y_i}{1+\exp(y_if(x_i))}

Затем для сгенерированного дерева решений наилучшее значение аппроксимации отрицательного градиента каждого конечного узла равно

c_tj=\arg \min \sum_{x_i \in R_{tj}}\log(1+\exp(-y_i(f_(t-1)+c)))

Приведенные выше подогнанные значения оптимизированы с помощью приближений вместо

c_{tj}=\frac{\sum _{x_i \in R_{tj}}r_{ti}}{\sum _{x_i \in R_{tj}}|r_{ti}|(1-|r_{ti}|)}

Бинарная классификация GBDT и процедуры регрессии такие же, за исключением расчета отрицательных градиентов и линейного поиска наилучшего отрицательного градиента, подходящего для листовых узлов.

параметры тренировки

Самые основные тренировочные параметры GBDT:

скорость обучения
количество итераций (n_trees)
глубина одного дерева (max_depth)

преимущество

Процесс создания дерева можно представить какАвтоматически выполнять многомерную комбинацию функций. Весь путь от корневого узла до конечного узла (множественные суждения о собственных значениях) может окончательно определить прогнозируемое значение дерева.непрерывные функцииДля обработки GBDT может разделить критический порог, например, если он больше 0,027, перейти к левому поддереву, а если он меньше или равен 0,027 (или значению по умолчанию), перейти к правому поддереву, что позволяет избежать проблема ручной дискретизации. Это позволяет очень легко решить логистическую регрессию тамАвтоматически обнаруживайте функции и создавайте эффективные комбинацииЭто также является преимуществом GBDT.

недостаток

Массивные функции класса id не могут быть эффективно сохранены

2.3 GBDT+LR

Поскольку самому LR необходимо выполнять множество ручных скрещиваний признаков, GBDT может автоматизировать скрининг и комбинирование признаков для формирования новых дискретных векторов признаков. Итак, соедините эти две модели, используйте GBDT для фильтрации и объединения исходных признаков, а затем выведите их в модель LR для классификации, которая является известной моделью GBDT+LR.

gbdt_lr

Как показано на рисунке выше, во время обучения процесс построения дерева GBDT эквивалентен автоматическому объединению признаков и дискретизации, и тогда путь от корневого узла к конечному узлу можно рассматривать как комбинацию признаков различных признаков. может быть представлено уникальным образом и передано в LR как дискретная функция для обработкисреднее образование. Пример изображения выше $x$ В качестве входной выборки он проходит через левое и правое деревья классификации GBDT и попадает на листовые узлы двух деревьев соответственно.Каждый листовой узел соответствует одномерному признаку LR, а затем все признаки LR, соответствующие образцу получаются путем обхода дерева. Например, два параллельных дерева будут сгенерированы отдельно. $[0,1,0]$ и $[1,0]$ , а затем они объединяются как $[0,1,0,1,0]$ Затем введите данные в приведенную ниже модель LR, чтобы завершить классификацию.

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

ключевой момент:

Дискретный вектор, полученный после объединения признаков с помощью GBDT, используется в качестве входных данных логистической регрессии вместе с исходными признаками обучающих данных, а не только с дискретными признаками.
Причина использования ансамбля для построения дерева заключается в том, что выразительная способность одного дерева слаба, чего недостаточно для выражения нескольких комбинаций отличительных признаков, а выразительная способность нескольких деревьев сильнее. Каждое дерево GBDT изучает оставшиеся недостатки предыдущего дерева и определяет, сколько деревьев будет сгенерировано за столько итераций.
RF также представляет собой несколько деревьев, но было доказано, что эффект не так хорош, как GBDT. И дерево перед GBDT, разделение признаков в основном отражает признак, который отличает большинство выборок; последнее дерево в основном отражает несколько выборок с большой остаточной ошибкой после прохождения через первые N деревьев. Целесообразнее выбрать признаки, дискриминационные в целом, а затем выбрать признаки, дискриминационные для нескольких выборок, что также должно быть причиной использования GBDT.
В прогнозировании CRT GBDT обычно строит два типа деревьев (один для функций без идентификатора, а другой для функций с идентификатором). Функции AD и ID являются очень важными функциями в прогнозировании CTR. Невозможно построить дерево как функцию, поэтому рассмотрите возможность построения дерева GBDT для каждого AD и ID.
1. Дерево типов без идентификаторов: не создавайте деревья с детализированными идентификаторами. Этот тип дерева используется в качестве основы. Даже если реклама и рекламодатели с меньшим охватом все еще могут использовать этот тип дерева для получения отличительных признаков и комбинаций признаков.
2. Дерево классов идентификаторов: создайте дерево классов с подробными идентификаторами, чтобы найти хорошо раскрытые идентификаторы, соответствующие отличительным функциям и комбинациям функций.

использованная литература

blog.CSDN.net/rock_have/Aretti…
blog.CSDN.net/Oh Lane Goes Down/Аретти…
blog.CSDN.net/Я боюсь роутера 110/Ах...
zhuanlan.zhihu.com/p/35465875