[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_A$$和$$x_{ST}$$都为非0的案例x,因此,如果是通过直接的估计的话,将会得到一个没有交互的结果($$\omega_{A,ST}=0$$)。但是通过使用因子化的交互参数$$\langle v_A, v_{ST} \rangle$$,在这种情况下,依然可以估计该交互。首先,BobCharlie有相似的因子向量$$v_B$$和$$v_C$$用于预测,因为他们在Star Wars($$v_{SW}$$)上有相似的交互,也就是说,$$\langle v_B, v_{SW} \rangle$$ 和 $$\langle v_C, v_{SW} \rangle$$ 必须相似。Alice($$v_A$$)与Charlie($$v_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$$,$$\omega$$和$$V$$)——例如: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}}$$, 如果$$\theta$$为$$v_{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与其它模型进行对比,并且介绍实验情况和进行总结,敬请期待!

打赏

mickey

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