转载

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通过分解来打破了交互之间的依赖性, 减少了参数. 下图是一个用于预测用户对电影打分的数据集:

Factorization Machine

易知$(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.

正文到此结束