FM算法原文。


论文背景

  2010 IEEE International Conference on Data Mining
  Steffen Rendle
  Department of Reasoning for Intelligence
  The Institute of Scientific and Industrial Research Osaka University, Japan
谷歌学术被引用次数1396(截至2020年12月14日)
  论文关键词:factorization machine; sparse data; tensor factorization; support vector machine
  PDF

Introduction 引言

  FM优点:
 1. FM能在很稀疏的数据上进行参数估计,但SVM不行。
 2. FM是线性复杂度,不需要类似于SVM中的支持向量。
 3. FM是通用预测方法,适用于任何特征向量。其它的因子分解方法都受限于特定的输入。(对比biased MF, SVD++, PITF和FPMC)

Prediction under sparsity 稀疏情况下的预测

feature x
feature x

Factorization machines(FM) 因子分解机

Factorization machine model 因子分解机模型

  degree d = 2
$$\hat{y}(x):=w_0 + \sum_{i=1}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>x_ix_j$$
  其中$w_0∈R$,$w∈R^n$,$V∈R^{n×k}$,<·,·>表示点乘。
$$<v_i,v_j>:=\sum_{f=1}^kv_{i,f}·v_{j,f}$$
  V中的$v_i$描述k个因素中的第i个变量。$Ks∈N_0^+$是定义因子分解的维度的超参数。
  2-way FM捕捉所有变量的单个和成对交互:
  $w_0$是全局偏置,$w_i$模拟了第i个变量的程度。
  $\hat{w}_{i,j}:=<v_i, v_j>$模拟了第i和第j个变量间的交互。这个在高阶交互时(d > 2)高质量估计的关键。
  时间复杂度O($kn^2$),因为所有的交互对都要被计算。但可以变形使之化为O(kn)。

Factorization machines as predictors FM作为预测器

  可用于回归、二分类和排序问题。

Learning factorization machines FM学习策略

  使用随机梯度下降(SGD)来学习。

d-way factorization machine 多维FM

  同时2-way FM可以拓展为d-way。

Summary 总结

  FM优点:
  1. 在高稀疏下可估计特征交互,尤其是不可观测的交互。
  2. 预测和学习的时间复杂度是线性的。使SGD优化可行,并允许多种损失函数优化。

FMs vs. SVMs 因子分解机对比支持向量机

SVM model 支持向量机模型

  SVM等式$$\hat{y}(x) = <\Phi(x), w>$$
  其中$\Phi$是从空间$R^n$到F的映射。$\Phi$和下式的核相关:
$$K:R^n × R^n → R, K(x, z) = <\Phi(x), \Phi(z)>$$
1) 线性核
  $K_l(x, z) = 1 + <x, z>$,对应$\Phi(x) := (1, x_1, … , x_n)$
  SVM等式为
$$\hat{y}(x) = w_0 + \sum^n_{i=1}w_ix_i, w_0∈R, w∈R^n$$
  这等价于FM中d = 1的情况。

2) 多项式核
  多项式核使SVM能模拟变量间的高阶交互。
$K(x, z) := (<x, z> + 1)^d$,对于d = 2有
$\Phi(x) := (1, \sqrt{2}x_1, … , \sqrt{2}x_n, x_1^2, … , x_n^2, \sqrt{2} x_1x_2, … , \sqrt{2}x_1x_n, \sqrt{2}x_2x_3, … , \sqrt{2}x_{n-1}x_n$
  SVM等式为
$$\hat{y}(x) = w_0 + \sqrt{2}\sum^n_{i=1}w_ix_i + \sum^n_{i = 1}w_{i,i}^{(2)}x_i^2 + \sqrt{2}\sum^n_{i=1}\sum^n_{j=i+1}w_{i,j}^{(2)}x_ix_j$$
  其中$w_0∈R, w∈R^n, w^(2)∈R^{n×n}$。
  d = 2时,FM和SVM的区别在于SVM中$w_{i,j}$是完全独立的,而FM中参数是因子分解的,所以<v_i, v_j>依赖于彼此。

Parameter Estimation Under Sparsity 在稀疏情况下的参数估计

  举例:使用协同过滤(上图中蓝色和红色部分数据)。
1) 线性SVM
$$\hat{y}(x) = w_0 + w_u + w_i$$
  只有j = u 或 j = i时$x_j$ = 1,即只有用户和物品偏好被选中时才有用。由于模型简单,在稀疏情况也能进不错的参数估计,但预测质量低。
2) 多项式SVM
$$\hat{y}(x) = w_0 + \sqrt{2}(w_u + w_i) + w_{u,u}^{(2)} + w_{i,i}^{(2)} + \sqrt{2}w_{u,i}^{(2)}$$
  $w_u$和$w_{u,u}^{(2)}$是一样的。该等式除了一个额外的$w_{u,i}$,等价于线性SVM。在训练集中,对于每一个$w_{u,i}$最多只有一条记录,在测试集中通常没有。因此,2-way的SVM效果也不比线性SVM好。

Summary 总结

1) SVM需要直接观测交互数据,但稀疏数据集经常没有。FM参数可以在系数情况下进行不错的参数估计。
2) FM可以一开始就直接学习,但非线性SVM需要成对学习。
3) FM是独立于训练集的,SVM的预测是基于部分训练数据的。

FMs VS. Other Factorization Models 其它因子分解方法对比

  改写FM公式形式,分别与Matrix and Tensor Factorization矩阵和张量分解、SVD++、PITF for Tag Recommendation、Factorized Personalized Markov Chains(FPMC)方法对比,FM改写后性能与这些方法实现效果类似。

Summary 总结

1) 标准因子分解模型(比如PARAFAC或者MF)不像FM一样是通用预测模型。
2) 修改特征提取部分,FM可以模拟在特定任务下的成功模型(比如MF,PARAFAC,SVD++,PITF,FPMC)。

Conclusion and Future Work 总结和展望

  与SVM对比,
1) 在数据稀疏情况下,FM可以进行参数估计。
2) 模型时间复杂度是线性的,并且只依赖于模型参数。
3) 从最开始就能直接优化。