Factorization Machines

FM算法是一种能够降低特征工程复杂性的模型，它能够处理高维稀疏数据。特征被分为一阶以及二阶交互，一阶项是原始特征的线性组合，二阶项则是特征对之间的交互。FM算法通过将输入数据映射到一个稠密向量空间中来处理高维稀疏数据，然后在该向量空间上进行计算,从而解决了传统的LR以及SVM等模型在处理高维稀疏数据时遇到的困难。

1.1 FM模型的损失函数

假设我们有一个输入的样本 $x$ , 包含了 $n$ 个特征，我们将其为 $x = x_{1}, x_{2}, \dots, x_{n}$ ，以及对应的标签 $y \in 0, 1$ ，其中每个特征一阶权重被表示为 $w_{i}$ , 且每一个特征值有一个对应的稠密向量 $v_{i} \in R^{k}$ 。FM算法的目标是学习这组权重参数 $w = w_{0}, w_{1}, \dots, w_{n}, v_{1}, \dots, v_{n}$ 来最小化预测误差。其损失函数定义如下：

\hat{y} (x) := w_{0} + \sum_{i}^{n} w_{i} x_{i} + \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} ⟨ v_{i} \cdot v_{j} ⟩ x_{i} x_{j} (1)

原始的计算代价为 $O (k n^{2})$ . 如果我们希望将计算的代价降低到 $O (k n)$ ，可以利用类似 $a b = \frac{1}{2} [(a + b)^{2} - (a^{2} + b^{2})]$ 的思路来对上面的式子中的最后一项进行变换，得到下面的式子：

\hat{y} (x) := w_{0} + \sum_{i}^{n} w_{i} x_{i} + \frac{1}{2} \sum_{f = 1}^{k} [(\sum_{i = 1}^{n} v_{i, f} x_{i})^{2} - \sum_{i = 1}^{n} v_{i, f}^{2} x_{i}^{2}] (2)

其中 $k$ 是每一个特征的dim的值（在AlphaFM的实现中，使用的是8）， $n$ 是整个算法所使用的特征的总数（这个值通常比较大，有可能达到几百万或者上亿）

1.2 FM模型的推理(召回场景)

上面的公式很好地诠释了损失函数，但如果我们要把FM模型用在推荐系统的召回阶段，我们如何才能做到快速召回大量的Items? 我们需要把召回看做是一个用户向量 $V_{u_{j}}$ 跟物品向量 $V_{i_{k}}$ 的匹配问题：为一个用户找到大量的推荐物品，本质是为 $V_{u_{j}}$ 找到最相似的一组 $V_{i_{k}}$ ,其中 $k \in 1, 2, \dots, N_{i}$ ，其中 $N_{i}$ 是物品的总数。

我们将公式 $(1)$ 中各计算项按照所属关系，可以拆分为用户和物品两大类别，这些项可以分为如下的三情况：

用户特征及其内部的交叉特征
物品特征以及内部的交叉特征
用户和物品之间的交叉特征

所以我们可以将这个匹配公式定义成如下的样子：

\begin{aligned} 匹 配 度 & = \sum I t e m 特 征 一 阶 权 重 项 + \sum I t e m 特 征 内 部 交 叉 项 + \sum U s e r 特 征 一 阶 权 重 项 + \sum U s e r 特 征 内 部 交 叉 项 + \sum U s e r 特 征 \times i t e m 特 征 \end{aligned}

由于User特征一阶权重以及User特征内部交叉对于对于所有要召回的item都是相等的, 因此直接去掉, 所以上面的公式可以写作：

\begin{aligned} 匹 配 度 & = \sum I t e m 特 征 一 阶 权 重 项 + \sum I t e m 特 征 内 部 交 叉 + \sum U s e r 特 征 \times i t e m 特 征 \\ = \sum_{i = 1}^{N_{i}} w_{i} x_{i} + \sum_{i = 1}^{N_{i}} \sum_{j = i + 1}^{N_{i}} ⟨ v_{i} \cdot v_{j} ⟩ x_{i} x_{j} + \sum_{i = 1}^{N_{u}} \sum_{j = 1}^{N_{i}} ⟨ v_{i} \cdot v_{j} ⟩ x_{i} x_{j} \\ = ⟨ 1, \sum_{i = 1}^{N_{u}} v_{i} x_{i} ⟩ \cdot ⟨ \sum_{i = 1}^{N_{i}} x_{i} w_{i} + \sum_{j = 1}^{N_{i}} \sum_{k = j + 1}^{N_{i}} ⟨ v_{j} \cdot v_{k} ⟩ x_{j} x_{k}, \sum_{j = 1}^{N_{i}} v_{j} x_{j} ⟩ \\ \overset{d e f}{=} E_{u s e r} \cdot E_{i t e m} \end{aligned}

其中， $N_{u}, N_{i}$ 分别表示属于User特征和属于Item特征的数量。

注意到在上面的式子中，我们已经在最后将匹配度写成了向量的内积形式。第一个向量 $E_{user}$ 表示用户的向量；第二个向量 $E_{item}$ 是表示item的向量。

\begin{aligned} E_{user} & = ⟨ 1, \sum_{i = 1}^{N_{u}} v_{i} x_{i} ⟩ \\ E_{item} & = ⟨ \sum_{i = 1}^{N_{i}} x_{i} w_{i} + \sum_{j = 1}^{N_{i}} \sum_{k = j + 1}^{N_{i}} ⟨ v_{j} \cdot v_{k} ⟩ x_{j} x_{k}, \sum_{j = 1}^{N_{i}} v_{j} x_{j} ⟩ \end{aligned}

其中, $E_{i t e m}$ 可以在模型训练完成后，计算并存储到向量数据库；而 $E_{user}$ 则在用户发起推荐请求的时候，根据用户信息以及当前上下文动态计算得到。

所谓召回，实际上是计算

\begin{array}{r} \underset{π \in Ω}{a r g m a x} \sum_{j = 1}^{T o p_{k}} E_{k}^{U} \cdot E_{π (j)}^{I} \end{array}

其中 $Ω$ 是Item所有可能排序的集合， $π$ 是其中一种排序； $π (j)$ 表示在这个排序下的第 $j$ 个位置对应的Item的序号; $E_{k}^{U}$ 和 $E_{j}^{I}$ 分别代表用户 $k$ 以及物品 $j$ 所对应的向量 (分别跟前面对应的 $E_{u s e r}$ 以及 $E_{i t e m}$ 类似); $T o p_{k}$ 是需要召回的物品数量。