Подробное объяснение классической модели машины факторизации FM в области рекомендательных систем.

В предыдущей статье мы проанализировали известную статью Facebook GBDT+LR, хотя эта статья получила широкое признание в отрасли, в конце концов, GBDT уже является старой моделью. Сегодня мы собираемся представитьБольше используется в промышленностиМодель, которая родилась в 2010 году, автором оригинала является Штеффен Рендл. Хотя он родился раньше, он более динамичен и имеет различные версии. То, что мы сегодня анализируем, — это самая классическая оригинальная статья 2010 года.

Когда дело доходит до алгоритмической модели рекомендации и рекламы, обойти FM почти сложно, это очень сильная модель.Теория проста, вывод строг, реализация проста, а эффект хороший.. Даже сейчас он все еще используется крупными производителями и даже является основной моделью на некоторых небольших заводах. У нас еще могут быть сомнения до того, как мы впервые прочитаем ее, но я верю, что после ее прочтения у нас обязательно появится новое понимание.

Опять же, это длинная статья, и я надеюсь, что вы терпеливо дочитаете ее до конца.

Введение

Полное название ФМFactorization Machines, перевод представляет собой машину факторизации.Такой перевод очень сложно произносить, и его нельзя использовать как бога или форму, поэтому мы обычно не переводим его как FM-модель для краткости.

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

Помимо SVM, модель FM имеет очевидные преимущества по сравнению с другими моделями факторизации, такими как SVD, PITF и FPMC. Эти модели часто предназначены только для конкретной сцены или определенного набора данных, и их схемы обучения и оптимизации настраиваются в соответствии с этой сценой.Модель FM не нуждается в настройке для достижения таких же хороших результатов., который может быть легко применен к различным задачам прогнозирования.

На самом деле, это резюме не имеет особого смысла, оно в основном предназначено для того, чтобы похвастаться FM. Однако то, что сказал автор, правда.По сравнению с перечисленными им моделями, FM действительно лучше.

Подводя итог, преимущества модели FM заключаются в следующем:

Параметры модели FM поддерживают очень разреженные функции, в то время как такие модели, как SVM, не поддерживают.
Временная сложность FM $O(n)$ , и может напрямую оптимизировать параметры исходной задачи, не полагаясь на опорные векторы и не преобразовывая ее в решение двойной задачи.
FM — это универсальная модель, которую можно применять к любым сценариям с реальными числами, другие модели не могут

В статье показаны преимущества FM-модели в начале и дается достаточно преимуществ, а затем проводится углубленный анализ FM-модели, чтобы каждый мог понять, как эти преимущества получены и как она работает.

Разреженная сцена

В сценариях контролируемого обучения наиболее распространенной задачей является предсказание цели T по вектору x. Если Т — действительное число, то это регрессионная модель, а если Т — константа для класса, то это классификационная модель.

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

Например, предположим, что мы используем вектор $x_i$ представляет вектор признаков элемента i, $x_j$ Представляет вектор признаков продукта j, затем мы можем объединить эти два вектора в качестве входных данных для предсказания классификации.Результат классификации указывает, находится ли элемент i перед элементом j или наоборот.. Таким образом, мы можем напрямую получить отношение ранжирования между элементами с помощью нескольких прогнозов вместо сортировки по баллу. Это позволяет проводить обучение только с положительными образцами. Плюсы и минусы модельных продуктов, непосредственно обученных по этому методу, называются обучением для ранжирования в отрасли.

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

мы используем $m(x)$ Представляет количество ненулевых элементов в векторе x, используя $\bar{m}_D$ Представляет среднее количество ненулевых элементов всех выборок x. В большинстве реальных сценариев данных мы можем получить $\bar{m}_D \ll n$ , где n — размер объекта.

пример реальной сцены

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

Очевидно, что большой блок слева на приведенном выше рисунке — это характеристика, а цель y справа представляет результат предсказания, то есть оценку, которую пользователь может дать фильму. Всего имеется 5 возможностей [1, 2, 3, 4, 5], что означает, что это проблема множественной классификации.

Далее, давайте посмотрим на функции.Функции имеют в общей сложности 5 частей, из которых синяя часть представляет собой горячую часть пользователя. Тогда длина этого массива должна быть количеством пользователей, только измерение, представляющее текущего пользователя, равно 1, а остальные равны 0.

Красная часть представляет фильм, который также является горячим для фильма и имеет ту же логику, что и горячий для пользователя. Размер, представляющий текущий фильм, равен 1, а остальные — 0.

После этого идет желтая часть, которая представляет поведение предыдущего пользователя при оценке фильмов, а размер также является количеством фильмов. Любой фильм, который был оценен пользователем, имеет оценку выше 0, и никакая оценка не равна 0. Логика подсчета баллов такова.1 разделить на количество фильмов, просмотренных пользователями. Например, в первой строке первый пользователь оценил первые три фильма, поэтому каждая часть первых трех фильмов $\frac{1}{3}$ счет.

Зеленая часть является только одномерной и представляет время, когда пользователь прокомментировал фильм. Метод расчета заключается в использовании самой ранней даты в записи в качестве базы (здесь январь 2009 г.) и увеличении на 1 каждый последующий месяц. Например, 5 в 2009 году можно преобразовать в 5.

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

Мы предполагаем, что количество пользователей равно U, а количество фильмов равно M, тогда окончательная размерность всей функции должна быть U+3M+1. Даже нишевый веб-сайт рейтинга фильмов имеет как минимум миллион пользователей, а в сочетании с количеством фильмов это, очевидно, очень большое число. иТолько некоторые из этих измерений имеют смысл, а остальные 0.

Для такой разреженной матрицы признаков общая модель трудно гарантировать эффект. Почему модель FM должна оставаться в стороне? Далее давайте рассмотрим принцип работы модели FM.

Принцип FM-модели

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

$Y = W^TX = w_0 + \sum_{i=1}^n w_i x_i$

то есть $W = (w_0, w_1, w_2, \cdots, w_n)$ , W — такой n+1-мерный вектор, а X — матрица признаков размера n x m. Здесь n — размер признака, а m — количество выборок. Поэтому мы также часто пишем это как $Y=XW$ , как ни напишешь, форма одна и та же.

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

Когда мы биномиально объединяем признаки, мы получаем следующую формулу:

$\hat{y}=w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^{n-1}\sum_{j=i+1}^n w_{ij}x_ix_j$

здесь $x_i$ и $x_j$ Представлять два разных значения признаков соответственно.Для n-мерных признаков такая комбинация должна иметь в общей сложности $C_n^2$ виды, это значение $\frac{n(n-1)}{2}$ , а значит нам нужно одинаковое количество весовых параметров. Но есть небольшая проблема, как мы уже говорили ранее, потому что функции могут быть очень разреженными, в результате чего n очень велико, например миллионы, здесьВеличина признака попарной комбинации признаков примерно равна квадрату n., то полученное количество параметров является астрономическим числом. Подумайте, сколько обучающих выборок нам нужно, чтобы обеспечить полную сходимость для модели с десятками миллиардов или более пространств параметров? Это невообразимо.

В этом случае необходима целевая оптимизация. Это то, чем известен FM,Он не только вводит пересечение признаков, но также решает проблему сложности и параметров модели., это действительно здорово.

Способ, которым FM решает эту проблему, очень прост: он больше не просто устанавливает параметры для пары признаков после пересечения, а задает метод расчета параметров признаков. Модель FM вводит новую матрицу V, которая представляет собой двумерную матрицу размера n x k. Здесь k — это устанавливаемый нами параметр, который обычно не очень велик, например, 16, 32 и так далее. Для каждого измерения i функции мы можем найти $v_i$ , который представляет собой вектор длины k.

Таким образом, мы можем использовать $v_i$ и $v_j$ чтобы рассчитать приведенную выше формулу $w_{ij}$ :

$w_{ij} = v_i^Tv_j$

То есть мыИспользование внутреннего произведения векторов для вычисления коэффициентов перекрестного признака, по сравнению с оригиналом $O(n^2)$ С точки зрения параметров величины мы уменьшаем величину параметров до n x k. Поскольку k является постоянным значением, можно видеть, что наше количество параметров равно $O(n)$ . Таким образом, мы уменьшаем количество параметров на порядок.

С матрицей V только что полученную формулу можно переписать как:

$\hat{y} = w_0 + \sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=1}^nv_i^T v_jx_i, x_j$

Мы можем легко узнать, что, когда параметр k достаточно велик, мы можем гарантировать $W = V\cdot V^T$ учредил. так что мыВведенную матрицу параметров V можно рассматривать как факторизацию матрицы W, что также является источником названия FM. Конечно, в сценариях практического применения нам не нужно задавать очень большое значение K, потому что матрица признаков часто бывает очень разреженной, у нас может не хватить выборок для обучения такого большого количества параметров, иОграничение K также может в определенной степени улучшить обобщающую способность FM-модели..

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

Есть два способа понять этот подход. Один из них, как я только что сказал, Мы также можем хорошо рассчитать коэффициенты для некоторых разреженных комбинаций. Другой способ понимания -На самом деле это способ встраивания, который сопоставляет идентификатор с вектором. Таким образом, промышленность также использует FM для встраивания.

оптимизация сложности

Далее, давайте рассмотрим еще один очень важный аспект — оптимизацию сложности FM-модели. Давайте посмотрим на приведенную выше формулу, нетрудно найти, что текущая вычислительная сложность для прогнозирования выборки равна $O(kn^2)$ .

Как мы уже говорили ранее, n — относительно большое число, поэтому, очевидно, $n^2$ Уровневые расчеты для нас также неприемлемы. Так что его тоже надо оптимизировать, а оптимизация тут очень простая, можноВывод непосредственно через деформацию математической формулыполучить.

$\hat{y} = w_0 + \sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=1}^nv_i^T v_jx_i, x_j$

Это его исходная формула.Для этой формулы сложность первых двух пунктов равна $O(n)$ , мы можем игнорировать его и сосредоточиться на последнем элементе. Все, что нам нужно сделать, это упростить этот термин, преобразовав математическую формулу:

\begin{aligned} \sum_{i=1}^n\sum_{j=i+1}^n v_i^T v_j x_i x_j &= \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n v_i^Tv_jx_i x_j - \frac{1}{2}\sum_{i=1}^nv_i^Tv_jx_ix_j\\ &=\frac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n\sum_{f=1}^kv_{i, f}v_{j, f}x_ix_j-\sum_{i=1}^n\sum_{f=1}^kv_{i,f}v_{i,f}x_ix_i)\\ &=\frac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i, f}x_i)(\sum_{j=1}^nv_{j, f}x_j)-\sum_{i=1}^nv_{i,f}^2x_i^2)\\ &=\frac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i,f}x_i)^2 - \sum_{i=1}^nv_{i, f}^2 x_i^2) \end{aligned}

Чтобы кратко объяснить этот процесс вывода, я думаю, что каждый должен быть в состоянии понять первую строку, а вторую строку также легко понять. $v_i^Tv_j$ Расширение векторного внутреннего продукта. Переход из второй строки в третью понять нетрудно, вот три $\Sigma$ , мы извлекли самое сокровенное $\Sigma$ , потому что это сумма конечного члена,Мы меняем порядок и это не влияет на результат. После извлечения общего множителя получается два квадрата членов. Мы можем заметить, что вычислительная сложность этих двух квадратных членов равна $O(n)$ , плюс внешний слой $O(k)$ Сложность , общая сложность $O(kn)$ .

На этом оптимизация прогнозов модели FM завершена.

обучение модели

Еще раз посмотрим на процесс обучения модели, запишем исходную формулу после деформации:

$\hat{y}=w_0 + \sum_{i=1}^n w_i x_i + \frac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i, f}x_i)^2 - \sum_{i=1}^nv_{i, f}^2x_i^2)$

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

Мы можем разделить параметры на три части, первая часть естественно $w_0$ , $\frac{\partial\hat{y}}{\partial w_0}=1$ . Вторая часть $\sum_{i=1}^nw_ix_i$ , для каждого из $w_i$ Допустим, его коэффициент $x_i$ . Поскольку выборка фиксирована, мы хотим рассматривать собственные значения выборки как постоянные. так $\frac{\partial \hat{y}}{\partial w_i}=x_i$ . Последняя часть $\frac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i, f}x_i)^2 - \sum_{i=1}^nv_{i, f}^2x_i^2)$ Выглядит намного сложнее, но на самом деле частную производную найти несложно.Сначала уточним, что оптимизируемыми параметрами здесь являются $v_{i, f}$ , поэтому мы можем игнорировать самый внешний слой $\sum_{f=1}^k$ , непосредственно вывод в скобках, результат $\frac{\partial \hat{y}}{\partial v_{i, f}}=x_i\sum_{j=1}^n v_{j, f}x_j -v_{i,f}x_i^2)$

Когда мы объединяем эти три, мы получаем:

$\begin{equation} \frac{\partial \hat{y}}{\partial \theta}=\left\{ \begin{aligned} & 1, & if \;\theta\;is\;w_0 \\& x_i, & if\; \theta\;is\;w_i \\ & x_i\sum_{j=1}^n v_{j, f}x_j -v_{i,f}x_i^2) & if\;\theta\;is\;v_{i,f} \end{aligned} \right. \end{equation}$

в $\sum_{j=1}^nv_{j,f}x_j$ и я независимы, поэтому его можно вычислить заранее, так что для всех членов параметра мы можем $O(1)$ Рассчитайте их градиенты во времени. Поскольку величина всех наших параметров равна $O(kn)$ , а это значит, что мы можем $O(kn)$ Градиентный спуск обновляется по всем параметрам во времени.

Расширение до измерения d

Модель FM, которую мы только что представили, фокусируется на случае пересечения двумерных объектов, если мы хотимЕго также можно расширить до d измерений.Случай пересечения признаков. Таким образом, наши функции могут соответствовать любому $\tilde{d} (1\leq\tilde{d}\leq d)$ Взаимосвязи пересечений размерных признаков.

Следуя формуле только что, мы можем написать уравнение, которое расширяет модель ФМ до d измерений:

$\hat{y}=w_0 + \sum_{i=1}^nw_ix_i + \sum_{l=2}^d\sum_{i=1}^n\cdots\sum_{i_l=i_{l-1}+1}^n(\Pi_{j=1}^lx_{i_j})(\sum_{f=1}^{k_l}\Pi_{j=1}^lv_{i_j,f}^{(l)})$

Первые два легко понять, давайте сосредоточимся на третьем. Третий элемент содержит перекрестный признак от 2-мерного к d-мерному.Возьмем в качестве примера d=3, тогда этот элемент должен содержать двумерные перекрестные элементы и трехмерные перекрестные элементы, которые должны быть такими:

$\sum_{i=1}^{n-1}\sum_{j=i+1}^nx_ix_j(\sum_{t=1}^kv_{i,t}v_{j,t})+\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\sum_{l=j+1}^nx_ix_jx_l(\sum_{t=1}^k v_{i,t}v_{j, t}v_{l, t})$

эта формулаОбщая форма та же, что и раньше, мы можем легко проанализировать, что его сложность $O(kn^d)$ . Когда d=2, мы оптимизируем его сложность до $O(kn)$ , а когда d>2, хорошего метода оптимизации не существует, а пересечение тройных признаков часто бессмысленно и слишком разрежено, поэтому мы обычно используем только случай d = 2.

Код

Приведенного выше абзаца достаточно, чтобы все поняли и знали, что такое есть, но на самом деле это мало что значит. В конце статьи также сравниваются эффекты ФМ и некоторых других классических моделей, таких как СВД, СВМ и т. д., что не представляет большой ценности, т.к.Сейчас почти никто не использует эти модели напрямую в рекомендательном поле. Наконец, я опубликую модель FM, которую я реализовал с помощью фреймворков pytorch и TensorFlow соответственно, для справки.

Pytorch

import torch
from torch import nn

ndim = len(feature_names)
k = 4

class FM(nn.Module):
    def __init__(self, dim, k):
        super(FM, self).__init__()
        self.dim = dim
        self.k = k
        self.w = nn.Linear(self.dim, 1, bias=True)
        # 初始化V矩阵
        self.v = nn.Parameter(torch.rand(self.dim, self.k) / 100)
        
    def forward(self, x):
        linear = self.w(x)
        # 二次项
        quadradic = 0.5 * torch.sum(torch.pow(torch.mm(x, self.v), 2) - torch.mm(torch.pow(x, 2), torch.pow(self.v, 2)))
        # 套一层sigmoid转成分类模型，也可以不加，就是回归模型
        return torch.sigmoid(linear + quadradic)
    
    
fm = FM(ndim, k)
loss_fn = nn.BCELoss()
optimizer = torch.optim.SGD(fm.parameters(), lr=0.005, weight_decay=0.001)
iteration = 0
epochs = 10

for epoch in range(epochs):
    fm.train()
    for X, y in data_iter:
        output = fm(X)
        l = loss_fn(output.squeeze(dim=1), y)
        optimizer.zero_grad()
        l.backward()
        optimizer.step()
        iteration += 1        
        if iteration % 200 == 199:
            with torch.no_grad():
                fm.eval()
                output = fm(X_eva_tensor)
                l = loss_fn(output.squeeze(dim=1), y_eva_tensor)
                acc = ((torch.round(output).long() == y_eva_tensor.view(-1, 1).long()).sum().float().item()) / 1024
                print('Epoch: {}, iteration: {}, loss: {}, acc: {}'.format(epoch, iteration, l.item(), acc))
            fm.train()

TensorFlow

import tensorflow as tf
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score, roc_auc_score
import numpy as np


class FactorizationMachine:

    def __init__(self, n_dim=1, k=4, learning_rate=0.05, epochs=8):
        self._learning_rate = learning_rate
        self._n_dim = n_dim
        self._k = k
        self._epochs = epochs
        self.sess = tf.Session()
        self.x_input = tf.placeholder(shape=[None, self._n_dim], dtype=tf.float32)
        self.y_input = tf.placeholder(shape=[None, 1], dtype=tf.float32)
        # 初始化W和V
        self.w = tf.Variable(tf.truncated_normal(shape=[self._n_dim, 1], dtype=tf.float32))
        self.V = tf.Variable(tf.truncated_normal(shape=[self._n_dim, self._k], dtype=tf.float32))
        self.b = tf.Variable(tf.truncated_normal(shape=[1, 1]))
        self.linear = tf.add(self.b, tf.matmul(self.x_input, self.w))
        self.quadratic = 1/2 * tf.reduce_sum(tf.square(tf.matmul(self.x_input, self.V)) - tf.matmul(tf.square(self.x_input), tf.square(self.V)), axis=1, keepdims=True)
        self.y_out = self.linear + self.quadratic
        self.y_pred = tf.round(tf.sigmoid(self.y_out))
        self.loss = tf.reduce_mean(tf.nn.sigmoid_cross_entropy_with_logits(logits=self.y_out, labels=self.y_input))
        self.train_op = tf.train.GradientDescentOptimizer(self._learning_rate).minimize(self.loss)
        self.accuracy = tf.reduce_mean(tf.cast(tf.equal(self.y_pred, self.y_input), tf.float32))
        init = tf.global_variables_initializer()
        self.sess.run(init)

    def train(self, X, Y, iterations=1000, batch_size=16, validation_size=0.1):
        x_train, x_test, y_train, y_test = train_test_split(X, Y, test_size=validation_size)
        for epoch in range(self._epochs):
            for i in range(iterations):
                rand_idx = np.random.choice(x_train.shape[0], size=batch_size)
                rand_x = x_train[rand_idx]
                rand_y = y_train[rand_idx]
                self.sess.run(self.train_op, feed_dict={self.x_input: rand_x, self.y_input: rand_y})
                if i % 100 == 99:
                    loss = self.sess.run(self.loss, feed_dict={self.x_input: x_test, self.y_input: y_test})
                    acc = self.sess.run(self.accuracy, feed_dict={self.x_input: x_test, self.y_input: y_test})
                    print('epoch = {}, iteration ={}, loss = {}, accuracy ={}'.format(epoch, i, loss, acc))

    def predict(self, x):
        return self.sess.run(self.y_pred, feed_dict={self.x_input: x})

Примечание. Версия 1.0, используемая кодом TensorFlow.

Статья FM была проанализирована здесь, а также приведена реализация кода. Но это не конец, и в продолжении есть несколько обновленных версий FM. Например, AFM, FFM, PFM и т. д. Об этих документах мы будем знакомить вас с ними один за другим в дальнейшем.

Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)

Оригинальная ссылка, обратите внимание