WangYu::Space

Study, think, create, and grow. Teach yourself and teach others.

论文阅读 - Factorization Machines

分类：机器学习标签： 推荐系统创建时间：2019-09-05 00:00:00

本文为阅读论文 Factorization Machines 时记下的笔记。

线性模型

线性模型，如 logistics regression 仅学习到输入特征的权重，无法利用组合特征。可以将特征彼此相乘，给线性模型引入非线性特征。如下式所示：

y^(x):=w0+∑i=1nwixi⏟线性回归+∑i=1n∑j=i+1nwijxixj⏟交叉项（组合特征）\hat{y}(x) := \underbrace {w_0 + \sum_{i=1}^{n} w_i x_i }_{\text{线性回归}} + \underbrace {\sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{ij} x_i x_j}_{\text{交叉项（组合特征）}}

如果输入特征 xx 的维度 ∣x∣=n\vert x \vert = n，整个模型的参数量为 1+n+n21 + n + n^2。上式中交叉项 xixjx_ix_j 的系数 wijw_{ij} 需要依赖特征 xix_i 和 xjx_j 来训练得出。当输入向量 xx 很稀疏的时候。比如 xx 是使用 bag-of-word 表示的文档。当特征 xix_i 和 xjx_j 没有同时出现时，wijw_{ij} 就得不到训练。因此对于数据稀疏的场景，交叉项的参数矩阵 w\mathbf{w} 得不到充分训练。

FM

FM (Factorization Machine) 的思想是将组合特征的参数 w\mathbf{w} 进行矩阵分解，即 w=vTv\mathbf{w} = \mathbf{v}^T \mathbf{v}。如此以来 w\mathbf{w} 可以由一个较小的句子 v\mathbf{v} 来表示。其中 wij=vi⋅vj\mathbf{w}_{ij}=\mathbf{v}_i·\mathbf{v}_j，即组合特征 xixjx_ix_j 的系数由为特征对应的隐向量 vi\mathbf{v}_i 和 vj\mathbf{v}_j 的内积。

FM 模型就可以表示为：

y^(x):=w0+∑i=1nwixi+∑i=1n∑j=i+1n⟨vi,vj⟩xixj\hat{y}(\mathbf{x}) := w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j

其中尖括号表示两个向量内积：

⟨vi,vj⟩:=∑f=1kvi,f⋅vj,f\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle :=\sum_{f=1}^{k} v_{i, f} \cdot v_{j, f}

如果隐向量 vi\mathbf{v}_i 的维度为 kk，输入特征 xx 维度为 nn，上面式子中第二项的时间复杂度是 O(kn2)O(kn^2)。不过这一项在计算的时候可以进行化简：

∑i=1n∑j=i+1n⟨vi,vj⟩xixj=12∑f=1k((∑i=1nvi,fxi)2−∑i=1nvi,f2xi2)\sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j = \frac{1}{2} \sum_{f=1}^k \left(\left( \sum_{i=1}^n v_{i, f} x_i \right)^2 - \sum_{i=1}^n v_{i, f}^2 x_i^2 \right)

下面是证明过程：

证明过程不难理解，注意下面几点：

FM 特点

从参数量上来看，FM 模型将组合特征的参数量大幅下降，从 n∗(n−1)/2n * (n-1) / 2 降到 n∗kn * k。

另外，采用类似于矩阵分解的策略，交叉项系数 wij\mathbf{w}_{ij} 原本只能通过 xix_i 和 xjx_j 训练得出，如果这两个特征没有同时出现过，则得出的 wij\mathbf{w}_{ij} 无意义。在 FM 模型中 wij\mathbf{w}_{ij} 由 vi\mathbf{v}_i 和 vj\mathbf{v}_j 内积得来，而 vi\mathbf{v}_i 可以通过任何包含特征 xix_i 的实例进行学习。对于样本中不存在的特征组合，FM 也能进行泛化。

FM 训练

如果用 FM 做回归，可使用 MSE 作为损失函数。用于分类，就使用 logit loss，然后使用 SGD 训练即可。梯度计算如下：

∂∂θy^(x)={1, if θ is w0xi, if θ is wixi∑j=1nvj,fxj−vi,fxi2, if θ is vi,f\frac{\partial}{\partial \theta} \hat{y}(\mathbf{x})=\left\{\begin{array}{ll}{1,} & {\text { if } \theta \text { is } w_{0}} \\ {x_{i},} & {\text { if } \theta \text { is } w_{i}} \\ {x_{i} \sum_{j=1}^{n} v_{j, f} x_{j}-v_{i, f} x_{i}^{2},} & {\text { if } \theta \text { is } v_{i, f}}\end{array}\right.

FM 和 SVMs 的比较

使用多项式核的 SVMs 的模型可以写成下面这样：

y^(x)=w0+2∑i=1nwixi+∑i=1nwi,i(2)xi2+2∑i=1n∑j=i+1nwi,j(2)xixj\begin{aligned} \hat{y}(\mathrm{x})=w_{0}+\sqrt{2} \sum_{i=1}^{n} w_{i} x_{i} &+\sum_{i=1}^{n} w_{i, i}^{(2)} x_{i}^{2} \\ &+\sqrt{2} \sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{i, j}^{(2)} x_{i} x_{j} \end{aligned}

这里 SVMs 和 FM 用到的特征完全一样，唯一的区别就是交叉项的系数。因为 SVMs 中交叉项系数 wij\mathbf{w}_{ij} 依赖 xix_i 和 xjx_j 学习出来，SVM 不能用在数据稀疏的场景下。而 FM 可以使用极度稀疏的数据来学习参数。

总结

当数据很稀疏时，组合特征的参数难以学习到，FM 使用基于矩阵分解的策略，组合特征的系数依然能够有效估计，而且可泛化到未观察到的组合特征。

评论 （评论内容仅博主可见，不会公开显示）