Factorization Machines 因式分解机

Factorization Machines 因式分解机原理

• Factorization Machines 因式分解机原理
  • • 1. 概述
    • 2. FM优势
    • 3. 2维-FM
      • 3.1 模型
      • 3.2 二维-FM计算复杂度
      • 3.2 二维-FM的梯度计算
    • 4. FM应用

1. 概述

在使用线性模型，例如LR模型时，特征工程是很大一块工作，有时为了产生较好的效果需要人工进行一些特征的二维或者三维交叉。FM（Factorization machines）提供了一种思路可以自动进行特征交叉，同时能够处理非常稀疏数据，线性时间复杂度，计算简单。

由于FM实现简单效果非常好，而且应用范围非常广，FM是近期非常火的技术，在比赛或者大公司都非常常见。

2. FM优势

FM能够解决的问题及优点1：

• FM能够解决分类和回归问题
• FM能够代替SVD、SVD++等进行矩阵分解
• FM可以处理非常稀疏数据，此时SVM等模型会失效
• FM线性时间复杂度，计算简单
• FM可表示性较强，FM将模型参数表示为K维向量，向量之间可以交叉运算，即使两个交叉特征没有对应训练数据，也能表示出权重。

3. 2维-FM

先回顾一下线性回归模型，其建模时采用的函数是：

y^(x)=ω0+ω1x1+ω2x2+⋯+ωnxn=ω0+∑i=1nωixi(1) $$\begin{array}{}\text{(1)}& \begin{array}{rl}\hat{y}(\mathrm{x})& ={\omega }_0+{\omega }_1{x}_1+{\omega }_2{x}_2+\cdots +{\omega }_n{x}_n\\ & ={\omega }_0+\underset{i=1}{\overset{n}{\sum }}{\omega }_i{x}_i\end{array}\end{array}$$

从方程中可以看出各特征分量 xi $x_i$ 和 xj (i≠j) $x_j(i\ne j)$ 之间是相互孤立的，该模型仅考虑单个的特征分量，没有考虑特征分量之间的相互关系。

在 (1) $(1)$的基础上改写为：

y^(x)=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1nωijxixj(1)(2) $$\begin{array}{}\text{(2)}& \begin{array}{}\text{(1)}& \hat{y}(\mathrm{x})={\omega }_0+\underset{i=1}{\overset{n}{\sum }}{\omega }_i{x}_i+\underset{i=1}{\overset{n-1}{\sum }}\underset{j=i+1}{\overset{n}{\sum }}{\omega }_{ij}{x}_i{x}_j\end{array}\end{array}$$

这样也将任意两个不同的特征向量之间的关系也考虑进来了。

但是，有一个问题就是，在稀疏数据中这种直接在 xixj $x_i{x}_j$前面配上一个系数 ωij ${\omega }_{ij}$的方式会有很大的缺陷。因为对于观察样本中未出现过交互的特征分量，不能对相应的参数进行估计2。

一定要注意的是，在高度稀疏数据场景中，由于数据量的不足，样本中出现未交互的特征分量是很普遍的。

为了克服这个缺陷，我们在(2)中的系数 ωij ${\omega }_{ij}$上做文章，将其换成另外一种形式。针对每个维度的特征分量 xi $x_i$，引入辅助向量：

vi=(vi1,vi2,⋯,vik)T∈Rk,  i=1,2,⋯,n $${\mathrm{v}}_i=(v_{i1},v_{i2},\cdots ,v_{ik}{)}^T\in R^k,i=1,2,\cdots ,n$$

其中 k $k$ 为超参数，将(2)中的 ωij ${\omega }_{ij}$ 改写为：

ω^ij=viTvj:=∑l=1kvilxjl $${\hat{\omega }}_{ij}={{\mathrm{v}}_i}^T{\mathrm{v}}_j:=\underset{l=1}{\overset{k}{\sum }}{v}_{il}{x}_{jl}$$

如此，我们可以获得FM的二维模型。

3.1 模型

对于2次特征交叉的FM模型可以表示为3：

y(x)=w0+∑i=1n(wixi)+∑i=1n−1∑j=i+1n(<vi,vj>xixj)(3) $$\begin{array}{}\text{(3)}& y(x)=w_0+\underset{i=1}{\overset{n}{\sum }}(w_i{x}_i)+\underset{i=1}{\overset{n-1}{\sum }}\underset{j=i+1}{\overset{n}{\sum }}(<v_i,v_j>x_i{x}_j)\end{array}$$

其中模型参数有 w0 $w_0$ 为截距， wi $w_i$ 为一维特征权重， vi $v_i$ 为每一维度特征的分布式表示，也即 w0 $w_0$ 为整体偏置量， W $W$ 对特征向量的每个分量的强度进行建模， V $V$ 对特征向量中任意两个分量之间的关系进行建模。

其中特征交叉权重计算为:

<vi,vj>=∑f=1kvi,fvj,f(3.1) $$\begin{array}{}\text{(3.1)}& <v_i,v_j>=\underset{f=1}{\overset{k}{\sum }}{v}_{i,f}{v}_{j,f}\end{array}$$

3.2 二维-FM计算复杂度

如果对式子(1)直接进行计算，那么其复杂度是 O(kn2) $O(k{n}^2)$，但是我们可以通过简单的数学变换将其转化为 O(kn) $O(kn)$，由于前面两项的计算复杂度都是 O(kn) $O(kn)$，所以我们只需要对第三项进行处理4：

∑i=1n∑j=i+1n(<vi,vj>xixj)=12∑i=1n∑j=1n(<vi,vj>xixj)−12∑i=1n<vi,vi>xixi=12(∑i=1n∑j=1n∑f=1k(vi,fvjfxixj)−∑i=1n∑f=1k(vi,fvi,fxixi))=12∑f=1k((∑i=1nvi,fxi)(∑j=1nvj,fxj)−∑i=1nv2i,fx2i)=12∑f=1k((∑i=1nvi,fxi)2−∑i=1nv2i,fx2i)(2)(3)(4)(5)(2) $$\begin{array}{}\text{(2)}& \begin{array}{}\text{(2)}& \underset{i=1}{\overset{n}{\sum }}\underset{j=i+1}{\overset{n}{\sum }}(<v_i,v_j>x_i{x}_j)& =\frac{1}{2}\underset{i=1}{\overset{n}{\sum }}\underset{j=1}{\overset{n}{\sum }}(<v_i,v_j>x_i{x}_j)-\frac{1}{2}\underset{i=1}{\overset{n}{\sum }}<v_i,v_i>x_i{x}_i\text{(3)}& & =\frac{1}{2}(\underset{i=1}{\overset{n}{\sum }}\underset{j=1}{\overset{n}{\sum }}\underset{f=1}{\overset{k}{\sum }}(v_{i,f}{v}_{j_f}{x}_i{x}_j)-\underset{i=1}{\overset{n}{\sum }}\underset{f=1}{\overset{k}{\sum }}(v_{i,f}{v}_{i,f}{x}_i{x}_i))\text{(4)}& & =\frac{1}{2}\underset{f=1}{\overset{k}{\sum }}((\underset{i=1}{\overset{n}{\sum }}{v}_{i,f}{x}_i)(\underset{j=1}{\overset{n}{\sum }}{v}_{j,f}{x}_j)-\underset{i=1}{\overset{n}{\sum }}{v}_{i,f}^2{x}_i^2)\text{(5)}& & =\frac{1}{2}\underset{f=1}{\overset{k}{\sum }}((\underset{i=1}{\overset{n}{\sum }}{v}_{i,f}{x}_i{)}^2-\underset{i=1}{\overset{n}{\sum }}{v}_{i,f}^2{x}_i^2)\end{array}\end{array}$$

相当于特征分布式表示中每一维度和特征进行求和平方和平方求和相减。

3.2 二维-FM的梯度计算

采用SGD进行模型计算 :

∂∂θy(x)=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪1,xi,xi∑j=1nvj,fxj−vi,fx2i,if θ is ω0if θ is ωiif θ is νi,f(3) $$\begin{array}{}\text{(3)}& \frac{\mathrm{\partial }}{\mathrm{\partial }\theta }y(x)=\{\begin{array}{ll}1,& \mathrm{i}\mathrm{f}\theta \mathrm{i}\mathrm{s}{\omega }_0\\ x_i,& \mathrm{i}\mathrm{f}\theta \mathrm{i}\mathrm{s}{\omega }_i\\ x_i\underset{j=1}{\overset{n}{\sum }}{v}_{j,f}{x}_j-v_{i,f}{x}_i^2,& \mathrm{i}\mathrm{f}\theta \mathrm{i}\mathrm{s}{\nu }_{i,f}\end{array}\end{array}$$

基于随机梯度的方式求解5：

4. FM应用

在很多应用中，FM可以取代常用模型并且能够取得不错效果，例如

• FM - SVM，能够处理稀疏特征
• FM - MF
• FM - SVD++
• FM - PITF
• FM - FPMC

具体可以参考论文介绍。

---

1. 【每周一文】Factorization Machines ↩
2. Factorization Machines. S Rendle ↩
3. Factorization Machines. S Rendle ↩
4. Factorization Machines（因子分解机） ↩
5. Factorization Machines with libFM. S Rendle ↩