论文笔记之Factorization Machines

Factorization Machines

文中指出了FM的优点：
•FM可以在数据稀疏的情况下完成参数估计。
•FM的复杂度是线性的。
•FM可以对任何实值特征向量处理，非常general。

Factorization Machine Model

对于degree d=2的FM模型，等式如下：

vi表示第i个变量的k个factor构成的向量，k是一个超参数，定义了因子分解的维度。
2-way FM(d=2)捕捉了所有的变量单独信息和变量两两的交互信息。w0是global bias，wi是第i个变量的权重，wˆi,j = <vi,vj>表示第i个和第j个变量交互的权重。

Expressiveness

对于任意的正定矩阵W(nn)，存在一个矩阵V(nk)，在k足够大的情况下，有W = V•V^t。
W为变量间的交互矩阵，V为变量的隐向量矩阵。这说明了只要k足够大，FM可以表达任意的交互矩阵W。然而在数据稀疏的情况下，通常k被设置的比较小，因为没有足够的数据来估计很复杂的交互矩阵W。通过约束k的大小，使得模型有更好的泛化能力，并且在数据稀疏的情况下也能表现良好。

数据的一个例子如上图，可以看到特征向量中包含了用户信息与物品信息，离散信息(one-hot)与连续信息(数值)。
在POLY2中，比如要预测A对ST的评分，在上面的数据中没有A和ST都不为0的训练数据，这会导致wA,ST = 0(这里要强调对特征两两交互的理解，如果一个one-hot是5维的，这样算5个特征，在FM中对应5个隐向量)。在FM中，A的隐向量可以通过A与其他物品的交互过程学习到，ST同理，于是<vA,vST>不为0。

Computation

直接计算式(1)的复杂度为O(kn^2)，因为所有特征要两两交互。通过等式的变换，可以在线性时间O(kn)完成计算。

Factorization Machines as Predictors

•回归问题：yˆ(x)直接用来预测，loss function可以用最小均方误差。
•二分类：hinge loss或者logit loss。(一般加个sigmoid，loss function选交叉熵)
•排序：向量x由yˆ(x)的大小排序，loss由两个向量组成pairwise的pairwise classification loss定义。
为了防止过拟合，可以加上L2正则。

Learning Factorization Machines

Learning用SGD，梯度如下：

d-way Factorization Machine