Factorization Machine

Factorization Machine Model

如果仅考虑两个样本间的交互, 则factorization machine的公式为:

$\hat{y}(\mathbf{x}):=w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<\mathbf{v}_i, \mathbf{v}_j>x_ix_j$

其中的参数为

$w_0 \in \mathcal{R}, \mathbf{w}\in\mathbb{R}^n,\mathbf{V}\in\mathbb{R}^{n\times k}\tag{1}$

$\mathbf{v_i}$是样本$i$的向量表示, 维度为$k$, 两个向量的点积越大, 表示这两个样本越相似.

2路FM(2-way FM)捕获了样本自身以及样本之间的交互, 详解如下

$w_0$是全局偏置

$w_i$是第$i$个样本的强度

$\hat{w}_{i,j}:=<\mathbf{v}_i, \mathbf{v}_j>$代表第$i$个样本和第$j$个样本的交互. 与其为每个样本对都设置一个参数$w_{i,j}$, FM模型将其分解成两个向量之间的乘积.

通常来说, 对于任一正定矩阵$\mathbf{W}$,  只要$k$充分大, 都可以找到一个矩阵$\mathbf{V}$使得 $\mathbf{W}= \mathbf{V} \cdot \mathbf{V}^t$. 然而如果数据比较稀疏, 因为数据量不够估计复杂的交互矩阵$\mathbf{W}$, 通常需要选择小一点的$k$. 而FM把这种交互分解后, 会学习的更好, 因为FM通过分解来打破了交互之间的依赖性, 减少了参数. 下图是一个用于预测用户对电影打分的数据集:

易知$(1)$式的计算复杂度为$\mathit{O}(kn^2)$, 但是其可以做如下化简:

$\sum_{i=1}^n\sum_{j=i+1}^n<\mathbf{v}_i, \mathbf{v}_j>x_ix_j$

$=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n<\mathbf{v}_i,\mathbf{v}_j>x_ix_j - \frac{1}{2}\sum_{i=1^n}<\mathbf{v}_i, \mathbf{v}_j>x_ix_j$

$=\frac{1}{2}\left(\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\right)$

$=\frac{1}{2}\sum_{f=1}^k\left(\left(\sum_{i=1}^nv_{i, f}x_i\right)\left(\sum_{j=1}^nv_{j,f}x_j\right) - \sum_{i=1}^nv_{i, f}^2x_i^2\right)$

$=\frac{1}{2}\sum_{f=1}^k\left(\left(\sum_{i=1}^nv_{i, f}x_i\right)^2 -\sum_{i=1}^nv_{i, f}^2x_i^2\right)$

根据上述化简, $(1)$式的计算复杂度可以变为$\mathit{O}(kn)$

FM可以用作回归, 二分类以及排序. 为了防止过拟合, 最好添加$\mathcal{L}_2$正则化项.

• 回归  直接使用MSE作为Loss
• 二分类 使用hinge loss或者logit loss.
• 排序 对样本对$(\mathbf{x}^{(a)}, \mathbf{x}^{(b)})$进行优化, 使用pairwise的分类loss

模型学习

FM的参数$(w_o, \mathbf{w}, \mathbf{V})$可以通过梯度下降方法来学习, 比如SGD. 

$\frac{\partial}{\partial \theta}=\begin{cases} 1 & if \hspace{2 pt}\theta \hspace{2 pt}is \hspace{2 pt}w_0 \\ x_i, & if \hspace{2 pt}\theta \hspace{2 pt}is \hspace{2 pt}w_i \\ x_i\sum_{j=1}^nv_{j, f}x_j - v_{i, f}x_i^2, & if \hspace{2 pt}\theta \hspace{2 pt}is\hspace{2 pt} v_{i, f}\end{cases}$

其中$\sum_{j=1}^nv_{j, f}x_j$独立于$i$, 可以提前计算. 所以所有的梯度都可以在$\mathit{O}(1)$时间内计算得到, 而每个样本的参数更新可以在$\mathit{O}(kn)$内完成.

2路FM可以扩展到k路:

$\hat{y}(x):=w_0 + \sum_{i=1}^nw_ix_i + \sum_{l=2}^d\sum_{i_1=1}^n\dots\sum_{i_l=i_{l-1}+1}^n\left(\prod_{j=1}^lx_{i_{j}}\right) \left(\sum_{f=1}^{k_l}\prod_{j=1}^lv_{i_j, f}^{(l)}\right)$

参考文献:

[1]. Factorization Machines. Steffen Rendle. ICDM 2010.