Skip to main content

[paper阅读] 分解机(二)

因子分解机(FM

上个部分,我们介绍了FMs提出的背景和简介。这个部分将介绍因子分解机。作者们详细介绍了模型等式,然后简要介绍了如何将FMs应用到一些预测任务中。

因子分解机模型

模型等式:度为d=2的因子分解机的模型等式定义如下:

\hat{y}(x) := \omega_0 + \sum_{i=1}^{n}{\omega_ix_i}+\sum_{i=1}^{j=i+1}{\langle v_i,v_j \rangle x_ix_j} 公式1

其中,需要估计的模型参数为:

\omega_0\in R, \omega\in R^n, v\in R^{n\times k} 公式2

其中,\langle \cdot , \cdot \rangle表示两个长度为k的向量的点积。

\langle v_i, v_j \rangle := \sum_{f=1}^{k}{v_{i,f}\cdot v_{j,f}} 公式3

V中的行v_i表示k个因素的第i个变量。k\in N^+_0是一个超参,定义了分解机的维度。

一个双向的FM(度为d=2)获得了变量之间所有单一的和成对的交互:
\omega_0 为全局的偏好
\omega_i 为第i个变量的重要性
\hat{\omega}_{i,j} := \langle v_i, v_j \rangle 是第i个变量和第j个变量之间的交互。在这里,作者没有针对每个交互使用一个自己的模型参数\omega_{i,j}\in R,而是通过因子分解对交互进行建模。之后作者会介绍,这是在数据稀疏的情况下,能得到一个高质量的、高阶交互(d\ge 2)的参数估计的关键点。

可表达性:众所周知,对于任何正定矩阵W,在给定一个足够大的k的情况下,总会存在一个矩阵V使得W=V\cdot V^T。这表明如果k足够大的话,FM可以表示任何交互矩阵W。但是,在比较稀疏的情况下,应该要选择一个比较小的k,因为没有足够多的数据来估计复杂的交互W。在数据稀疏的情况下,控制k的大小,利用FM的可表达性可以带来更好的泛化,从而提高交互度量。

稀疏情况下的参数估计:在稀疏的背景下,通常没有足够的数据来直接、独立地估计变量之间的交互。即使在这样的背景下,因子分解机也可以很好地估计交互;因为FM可以通过对交互参数进行因子分解来打破它们之间的独立性。通常说来,这就意味着一次交互的数据也会帮助估计相关交互的参数。


1 从示例1的事务中创建的一个稀疏的实值特征向量x示例。每一行表示一个特征向量x^{(i)}和它对应的目标y^{(i)}。前4列(蓝色)表示活跃用户的标识向量;接着4列(红色)表示活跃物品的标识变量;接着5列(黄色)表示额外的隐式标识)例如,用户评过分的其它电影;1个特征(绿色)表示这个月中的时间;最后的5列(棕色)表示在活跃的电影之前用户评过分的最后一个电影;最后1列是目标——在这里是评分。

继续使用图1中的数据作示例。假设希望估计Alice(A)Star Trek(ST)之间的交互来预测目标y(在这里被称为rating)。很明显,在训练数据中没有变量x_Ax_{ST}都为非0的案例x,因此,如果是通过直接的估计的话,将会得到一个没有交互的结果(\omega_{A,ST}=0)。但是通过使用因子化的交互参数\langle v_A, v_{ST} \rangle,在这种情况下,依然可以估计该交互。首先,BobCharlie有相似的因子向量v_Bv_C用于预测,因为他们在Star Warsv_{SW})上有相似的交互,也就是说,\langle v_B, v_{SW} \rangle\langle v_C, v_{SW} \rangle 必须相似。Alicev_A)与Charliev_C)将会有不同的因子向量,因为ta们对TitanicStar Wars用于预测的因子有不同的交互。其次,Star TrekStar Wars的因子向量中有可能有一个相似,因为Bob对这两部电影的预测y有相似的交互。总的说来,这就意味着AliceStar Trek特征向量的点积(例如,交互)与AliceStar Wars的点积相似——这也是符合逻辑的。

计算:接下来,作者们还介绍了如何从计算的角度来使得FMs可应用。公式1的直接钱箱计算复杂度为O(kn^2),因为需要计算所有成对的交互。但是,通过重新构造,可以将其复杂度降低到线性运行时间。
Lemma 3.1:因子分解机的模型等式(公式1)可以在线性时间O(kn)内计算完毕。
证明:基于成对交互的因子化,因此没有模型参数直接依赖于两个变量(例如,索引(i,j)的参数)。因此。成对的交互可以被重构为:

\sum_{i=1}^{n}{\sum_{j=i+1}^{n}\langle v_i, v_j \rangle x_ix_j}
=\frac{1}{2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{\langle v_i, v_j \rangle x_ix_j}-\frac{1}{2}{\sum_{i=1}^{n}{\langle v_i, v_i\rangle x_ix_i}}}
=\frac{1}{2}{(\sum_{i=1}^{n}{\sum_{j=1}^{n}{\sum_{f=1}^{k}{v_{i,f}v_{j,f}x_ix_j}}}-\sum_{i=1}^{n}{\sum_{j=1}^{k}{v_{i,f}v_{i,f}x_ix_i}})}
=\frac{1}{2}{\sum_{f=1}^{k}{((\sum_{i=1}^n{v_{i,f}x_i})(\sum_{j=1}^n{v_{j,f}x_j})-\sum_{i=1}^n{x_{i,f}^2x_i^2})}}
=\frac{1}{2}\sum_{f=1}^k({\sum_{i=1}^n{v_{i,f}x_i}}^2-\sum_{i=1}^n{v_{i,f}^2x_i^2})

该等式只有与kn相关的线性复杂度,即:其计算为O(kn)

更多地,在稀疏的背景下,x中的大多数元素都是0(即:m(x)非常小),因此,只需要计算非0元素的和。因此,在稀疏的应用中,因子分解机的计算为O(k\bar{m}_D),例如,对于典型的推荐系统中,像矩阵分解方法中,\bar{m}_D=2

因子分解机作为预测器

因子分解机可以被应用于大量预测任务。包括:
回归\hat{y}(x)可以被直接使用为预测器,优化原则是D上的最小二乘积
二进制分类器:会使用\hat{y}(x)sign,并且使用hinge loss或者logit loss作为优化目标
排序:通过\hat{y}(x)的评分对向量x进行排序,通过使用一个成对的分类损失对实例向量的实例对((x^{(a),x^{(b)}})\in D)进行优化

在所有这些情况下,通常会在优化目标中添加一些正则化参数例如L2来避免过拟合。

训练因子分解机

正如上面的介绍的,FMs有一个闭合的模型等式,并且可以在线性时间内计算。因此,可以通过梯度下降方法来计算FMs的模型参数(\omega_0\omegaV)——例如:SGDStochastic Gradient Descent,随机梯度下降法),可以使用一系列损失,例如squarelogit或者hinge loss。矩阵分解模型的梯度为:

\frac{\delta}{\delta \theta}{\hat{y}(x)}=1, 如果\theta\omega_0
\frac{\delta}{\delta \theta}{\hat{y}(x)}=x_i, 如果\theta\omega_i
\frac{\delta}{\delta \theta}{\hat{y}(x)}=x_i\sum_{j=1}^n{v_{j,f}{x_j-v_{i,f}x_i^2}}, 如果\thetav_{i,f} 公式4

\sum_{j=1}^n{v_{j,f}x_j}独立于i,因此可以提前计算(例如,当计算\hat{y}(x)时)。一般说来不,每个梯度可以在常数时间O(1)内计算完毕。因此,对于一个案例(x,y)的所有参数的一次更新可以在O(kn)的时间内完成,或者在稀疏的情况下为O(km(x))

作者们提供了一个通用的实现,LIBFM,使用SGD,并且同时支持元素的和成对的损失。

d方向的因子分解机

上面描述的2向的FM可以被简单地泛化到一个d向的FM中:

\hat{y}(x) := \omega_0+\sum_{i=1}^n{\omega_ix_i}
+\sum_{l=1}^{d}{\sum_{i_1=1}^n\cdots\sum_{i_l=i_{l-1}+1}^n(\prod_{j=1}^l{x_{i_j}})(\sum_{f=1}^{k_l}{\prod_{j=1}^l{v_{i_j,f}^{(l)}}})} 公式5

首先,\omega\omega_{u,u}^{(2)}表示的是相同的概念,因此,可以删除其中一个(例如,\omega_{u,u}^{(2)})。因此,模型等式与线性的情况相同,就多了一个额外的用户-物品交互omega_{u,i}^{(2)}。在典型的协同过滤问题中,对于每一个交互参数\omega_{u,i}^{(2)},一般在训练数据中最多只有一个观察(u,i),而对于训练数据中对于案例(u’,i’)一般没有任何观察。例如,在图1中,对于交互(AliceTitanic)只有一个观察,而对于交互(AliceStar Trek)没有交互。这就意味着对于所有测试示例(u,i)中的交互参数\omega_{u,i}^{(2)}的最大边缘解决方案是0(例如,\omega_{A,ST}^{(2)}=0)。而由于多项式SVM无法使用双向交互用来预测测试示例,因此,多项式SVM只依赖于用户和物品偏好,因此无法提供比线性SVM更好的估计。

对于SVMs,估计高阶的交互不仅仅在协同过滤中出问题,也会在数据非常稀疏的所有场景下出现问题。因为,针对一个成对的交互(i,j)对参数\omega_{i,j}^{(2)}进行可靠的估计,必须要有足够的示例x\in D,其中x_i \ne 0\land x_j \ne 0。一旦x_i=0或者x_j=0,那么x就无法用于估计参数\omega_{i,j}^{(2)}。总的说来,如果数据太稀疏的话,例如(i,j)只有少量,甚至没有示例时,SVMs可能会失败。

小结

  • SVMs的紧密参数化要求交互的直接观察,而在稀疏的设定一般无法提供。但是FMs的参数即使是在非常稀疏的情况下也可以很好地估计
  • FMs可以直接进行训练,非线性的SVMs一般双向学习。
  • FMs的模型等式独立于训练数据。而SVMs的预测则依赖于部分训练数据(支持向量)。

本周内容就先到这儿啦~下周将会把FMs与其它模型进行对比,并且介绍实验情况和进行总结,敬请期待!

打赏
微信扫一扫支付
微信logo微信扫一扫, 打赏作者吧~

mickey

记录生活,写给几十年后的自己。