Факторизационные машины в PyTorch

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

Обычно они представляют из себя матрицу пользователи-сущности, ячейки которой заполнены (а чаще всего не заполнены) некоторым числом — индикатором силы связи между данным пользователем и данный чущностью. Этот индикатор может быть выражен количеством просмотров, покупок, кликов и т.д. Задача, таким образом, состоит в том, чтобы заполнить пустующие ячейки.

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

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

Здесь, однако, необходимо помнить один нюанс, заключающийся в способе кодирования категориальных переменных для линейных моделей. Как я писал ранее, такие признаки принято кодировать методом one-hot encoding или dummy encoding, т.е. создавая для каждой категории отдельный признак (или каждой кроме одной, используемой в качестве опорной, как во втором случае). Фиктивные (dummy) признаки, порождённые одной категорией принято называть полем (field).

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

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

Стандарный способ моделирования взимодействий между парами признаков — это из перемножение их между собой. Например, если при построении регрессионной модели, моделирующей влияния дохода и пола на уровень счастья ( $happiness=bias + x_1\cdot income + x_2\cdot sex + error$ ) мы предполагаем, что для мужчин и женщин параметры зависимости могут различаться (например, рост дохода у мучщин делает их более счастливыми, чем такой же рост дохода у женщин), то для проверки этой гипотезы нужно включить в модель новый фактор, состоящий из их произведения, и проверить его значимость. Итоговое уравнение примет вид $happiness=bias + x_1\cdot income + x_2\cdot sex + x_3\cdot sex\cdot income + error.$ В общем виде уравнение будет выглядеть следующим образом: $y=w_0 + \sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n}\sum_{j=i+1}^{n}w_{ij}x_ix_j.$

Итак, поскольку мы хотим проследить взаиомдействие каждого пользователя с каждой сущностью, нам придётся перемножить все признаки одного поля со всеми признаками другого, получив новые признаки, кодирующие эффект взаимодействия, или, как его ещё назвают, мультипликативный эффект:

В таком подходе, однако, есть одна сложность — исследователью необходимо самостоятельно генерировать новые признаки, для чего необходимо или экспертное знание комбинации признаков, мультипликативный эффект между которыми значимо улучшит модель, или время и память на перебор всех возможных пар (а иногда и троек) и подсчёт их весов, что затруднительно, если количество признаков превышает несколько тысяч штук (а оно наверняка будет превыщать из-за способа кодирования). Поскольку число сочетаний из $n$ объектов по $k$ рассчитывается по формуле $C_n^k=\frac{n!}{(n-k)!\cdot k!}$ , то для модели второго порядка количество параметров будет составлять $\frac{n(n − 1)}{2} + n + 1$ , т.е. число весов $w_{i,j}$ растет намного быстрее числа базовых признаков, и при уже при сравнительно небольшом количестве пользователей и сущностей работать с такой моделью становится невозможно. К тому же данные могут быть сильно разрежены, что означает отсутствие информации о взаимодействии многих пар признаков и трудности в подборе весов для мультипликативных эффектов.

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

Именно так и работают факторизационные машины — они моделируют эффекты взаимодействия между всеми признаками, но не напрямую перемножая их, а обучая для каждого признака вектор низкой размерности и производя скалярное произведение векторов. Итоговая формула выглядит следующим образом: $y=w_0 + \sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n}\sum_{j=i+1}^{n}\langle v_i,v_j\rangle x_ix_j.$

Как видно, эта формула имеет одно отличие от предыдущей — веса $w_{ij}$ для мультипликативых эффектов признаков $i$ и $j$ заменены скалярным произведением соответствующих им векторов $v_i$ и $v_j$ . Эти вектора имеют размерность $k$ , т.е. $v_i=(u_{i1},u_{i2}\dots u_{ik})$ , и чем больше размерность — более глубокие взаимодействия выучит модель, но также затратит на это больше времени и с большей вероятностью переобучится. В остальном же это обычная регрессионная модель, которую мы подробно разобрали ранее.

Осталось решить один вопрос — как за линейное время подобрать эти вектора, ведь из вышележащего уравнения это не ясно. К счастью, Steffen Rendle, автор алгоритма, решил эту проблему, упростив его до следующего вида (полный вывод смотрите в статье [1] на стр. 3): $\frac{1}{2} \sum_{l=1}^k \big ((\sum_{i=1}^d v_{i, l} x_i)^2 - \sum_{i=1}^d v_{i, l}^2 x_i^2).$

В PyTorch модель факторизационных машин зависывается следующим образом:

import torch
import torch.nn as nn

class FM(nn.Module):
    def __init__(self, features_num=None, k=2):
        super().__init__()
        self.V = nn.Parameter(torch.randn(features_num, k), requires_grad=True)
        torch.nn.init.xavier_uniform_(self.V.data)
        self.linear = nn.Linear(features_num, 1)

    def forward(self, X):
        out_1 = ((X @ self.V) ** 2).sum(1, keepdim=True)
        out_2 = ((X ** 2) @ (self.V ** 2)).sum(1, keepdim=True)

        out_interaction = (out_1 - out_2) / 2
        out_linear = self.linear(X)
        return out_interaction + out_linear

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

Давайте попробуем применить записанную нами модель к данным и сравним результаты её работы с результатами работы имплементации факторизационных машин из библиотеки fastFM. Для этого используем функцию, которая генерирует данные о взаиодействии пользователей с сущностями в формате one-hot encoding и континуальную целевую переменную — пусть это будет рейтинг. Пусть количество пользователей будет 100, а количество сущностей — 50.

from fastFM.datasets import make_user_item_regression
from sklearn.model_selection import train_test_split

X, y, _ = make_user_item_regression(n_user=100, n_item=50)
X_train, X_test, y_train, y_test = train_test_split(X, y)

Применим модель факторизационных машин из библиотеки fastFM и посчитаем $R^2$ . Параметр rank задаёт размерность векторов $V$ , коэффициенты регуляризации для параметров $w$ и $V$ убираем в 0, т.к. в нашей модели это не реализовано. Метод подбора весов — Alternating Least Square (ALS).

from fastFM import als
from sklearn.metrics import r2_score

fm = als.FMRegression(n_iter=100, rank=2, l2_reg_w=0, l2_reg_V=0)
fm.fit(X_train, y_train)
y_pred = fm.predict(X_test)
r2_score(y_test, y_pred)

0.9962615535305582

Довольно неплохо. Попробуем применить нашу модель.

from torch import optim

X_train_tensor, y_train_tensor = torch.from_numpy(X_train.toarray()), torch.from_numpy(y_train.reshape(-1, 1))

model = FM(X_train.shape[1])
criterion = nn.MSELoss() 
optimizer = optim.SGD(model.parameters(), lr=0.1)

for epoch in range(500):
    optimizer.zero_grad()
    predictions = model(X_train_tensor.float())
    loss = criterion(predictions, y_train_tensor.float())
    # get gradients
    loss.backward()
    # update parameters
    optimizer.step()
    
X_test_tensor = torch.from_numpy(X_test.toarray())
predictions = model(X_test_tensor.float())
r2_score(y_test, predictions.squeeze().detach().numpy())

0.9791448199912682

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

Итак, Steffen Rendle красиво и эффективно решил проблему моделирования большого числа эффектов взаимодействия, и факторизационные машины быстро обрели популярность в задаче построения рекомендательных систем. Но самое главное, что заложенные в них идеи были подхвачены другими исследователями, что привело к появлению множества модификаций оригинального алгоритма. Одним из самых успешных примеров этого семейства моделей являются field-aware factorization machines [2], которые были созданы в процессе участия в соревнованиях по машинному обучению и при всей своей простоте обеспечили своим авторам несколько побед. О них мы поговорим в следующий раз.

Самостоятельное задание

Попробуйте реализовать в нашей модели возможность L1 и L2 регуляризации.

Факторизационные машины в PyTorch

Самостоятельное задание

Литература

Комментарии