[paper阅读]因子分解机(三)

前两周主要介绍了因子分解机的背景模型的具体介绍.本周将继续介绍因子分解机,主要将因子分解机和支持向量机以及因子分解模型进行了对比…最后给出了结论和后续工作.

FMs VS. SVMs

SVM模型

SVM的模型[6]等式可以表示为:转换后的输入x和模型参数$$w:\hat{y}(x)=(\phi(x),w)$$的点积,其中,$$\phi$$是从特征空间$$R^n$$映射到一个更复杂空间$$F$$的映射.映射$$\phi$$与核相关:

$$K: R^n \times R^n \rightarrow R, K(x,z) = \langle \phi(x), \phi(z)\rangle$$

接下来,作者们还通过分析SVMs的原问题形式来讨论FMsSVMs的关系.

在实践中,SVMs通过对偶的形式解决,而映射$$\phi$$不会显式运行.但是,原问题和对偶问题有相同的解决方案,所以关于原问题的讨论对对偶形式也同样适用.

1)线性核:最简单的核是线性核-$$K_l(x,z):=1+\langle x,z \rangle$$,对应的映射为$$\phi(x) := (1,x_1,…x_n)$$.因此,线性SVM的模型等式可以被重写为:

$$\hat{y}(x) = \omega_0 + \sum_{i=1}^n \omega_i x_i, \omega_0 \in R, w\in R^n$$ 公式1

很显然,线性SVM(等式1)与度为$$d=1$$的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)}}})}$$

2)多项式核: 多项式核可以让SVM对变量之间更高的交互进行建模,$$K_l(x,z):={(\langle x,z \rangle + 1)}^d$$,例如,$$d=2$$时对应下面的映射:

$$\phi(x):=(1,\sqrt2 x_1,…,\sqrt2 x_n, x_1^2, … , x_n^2,\sqrt2x_1x_2,…,\sqrt 2x_1x_n,\sqrt2x_2x_3,…,\sqrt2 x_{n-1}x_n$$ 公式2

因此,多项式SVMs的模型等式可以重写为:

$$\hat{y}(x)=\omega_0 + \sqrt2 \sum_{i=1}^n \omega_i x_i + \sum_{i=1}^n {w_{i,i}}^{(2)}x_i^2 + \sqrt2 \sum_{i=1}^n {\sum_{j=i+1}^n \omega_{i,j}^{(2)}x_ix_j}$$ 公式3

其中,模型参数为:
$$\omega_0\in R, w\in R^n, W^{(2)} \in R^{n\times n}$$(对称矩阵)

FM与多项式SVM(公式3)相比,当度为$$d=2$$时,两种方法都能对所有嵌套的交互进行建模.SVMsFMs的主要区别是参数化:SVMs的所有交互参数$$\omega_{i,j}$$都是完全独立的,例如,$$\omega_{i,j}$$和$$\omega_{i,l}$$.与之相反,FMs的交互参数都是因子化的,因此:$$\langle v_i, v_j \rangle$$ 和$$\langle v_i, v_l \rangle$$相互依赖,因为它们有交叉和共享参数(在这里为$$v_i$$).

稀疏条件下的参数估计

接下来,作者们将会解释为什么在非常稀疏的情况下,线性核多项式SVMs表现不好.作者们将会使用协同过滤中的用户-物品标识变量(图1示例中的前两个组(蓝色和红色))来解释.在这里,特征变量非常稀疏,只有两个元素非0(活跃用户u和活跃物品i).


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

1).线性SVM:对于这种类型的数据x,线性SVM模型(等式1)等价于:

$$\hat{y}(x)=\omega_0+\omega_u+\omega_i$$ 公式4

因为只有当$$j=u$$或者$$j=i$$时,$$x_j=1$$.这个模型对应最基础的协同过滤模型之一:只考虑用户和物品偏好.由于这个模型特别简单,即使在稀疏的情况下也能很好地进行估计.然而,实验的预测质量一般很低.(结果如图2所示)


2 在非常稀疏的情况时,预测双向变量交互时,SVMs失败,而FMs成功的结果

2).多项式SVM:通过使用多项式核,SVM可以获取高阶的交互(在这里,表示用户和物品之间的).在稀疏的情况下($$m(x)=2$$),SVMs的模型等式等价于:
$$\hat{y}(x)=\omega_0+\sqrt2(\omega_u+\omega_i)+\omega_{u,u}^2+\omega_{i,i}^2+\sqrt2{\omega_{u,i}}^{(2)}$$

首先,$$\omega_u$$和$$\omega_{u,u}^{(2)}$$表示的意思相同–可以删除其中一个(例如,$$\omega_{u,u}^{(2)}$$).那么现在模型等式等价于线性的情况,但是多加了一个用户-物品的交互$${\omega_{u,i}}^{(2)}$$.在典型的协同过滤(CF)问题中,对于每个交互参数$${\omega_{u,i}}^{(2)}$$,在训练数据中至多只有一个观察–$$(u,i)$$,而对于测试数据中的数据$$(u’,i’)$$,一般在训练数据中没有任何观察.例如,在图1的示例中,每个交互(AliceTitanic)至多只有1个观察,而对于交互(AliceStar Trek)则没有任何观察.这就意味着对于所有测试实例,$$(u,i)$$的交互参数$${\omega_{u,i}}^{(2)}$$最大边缘解决方案为0.(例如,$${\omega_{A,ST}}^{(2)}=0$$).因此,多项式SVMs无法利用任何双向的交互用于预测测试示例,因此,多项式SVM只能依赖用户和物品偏好,无法提供优于线性SVM的更好估计.

对于SVMs,估计高阶的交互不仅仅只是在CF中的一个问题,也是在所有特别稀疏场景下的问题.因为,对于一个成对的交互$$(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 VS. 其它因子分解模型

目前有许多因子分解模型,从用于分类变量的m维关系的标准模型(例如,MFPARAFAC)到用于特定数据和任务的特殊模型(例如,SVD++PITFFPMC).接下来,作者们还介绍了FM如何只通过核实的输入数据(例如,特征向量x)来模拟这些模型.

矩阵和张量因子分解

MF(Matrix Factorization,矩阵分解)是被研究最多的因子分解模型之一[7,8,2].它将两个严格变量之间的关系进行分解(例如,UI).解决严格变量问题的标准方法是对UI的每个级别定义一个二进制标识变量,例如图1中的第一个(蓝色)和第二个(红色)组:

$$n:=|U\cup I|, x_j := \delta (j=i\lor j=u)$$ 公式4

为了简短表示,作者们将$$x$$中的元素(例如$$x_j$$)以及参数都通过数字(例如,$$j\in \{1,…,n\}$$)和分类级别(例如,$$j\in(U\cup I)$$)表示.这就意味着假定了一个从数字到分类级别的双向映射.

一个FM使用该特征向量x等同于矩阵分解模型[2],因为$$x_j$$是对$$u$$和$$i$$而言的非0元素,因此,所有其它偏好和交互维:

$$\hat{y}(x)=\omega_0 + \omega_u + \omega_i + \langle v_u, v_i \rangle$$ 公式5

通过使用相同的参数,可以将问题扩展到超过两个分类标量中,FMs包括一个嵌套并行因子分析模型(PARAFAC)[1].

SVD++

对于评分预测的任务(例如,回归),Koren等人[2]将矩阵分解模型改进为SVD++模型.FM可以通过使用下面的输入数据$$x$$(类似于图1中的前3组)来模拟这个模型:

$$n:=|U\cup I \cup L|$$
$$x_j=1, 如果 j=i \lor j=u$$
$$ x_j=\frac{1}{\sqrt{|N_u|}}, 如果 j\in N_u$$
$$x_j=0 其它$$

其中,$$N_u$$是用户评过分的所有电影集合.
为了区分$$N_u$$和$$I$$之间的元素,它们通过一个双向函数进行转化:$$\omega : I \rightarrow L$$映射到一个空间$$L$$,其中$$L\cap I = \emptyset.$$

一个FM($$d=2$$)将会使用该数据进行计算:

$$\hat{y}(x)=\omega_0+\omega_u+\omega_i+\langle v_u,v_i \rangle +\frac{1}{\sqrt{|N_u|}}\sum_{l\in N_u}{\langle v_i, v_l \rangle}$$
$$+\frac{1}{\sqrt{|N_u|}}{\sum_{l\in N_u}}({w_l+\langle v_u, v_l \rangle + \frac{1}{\sqrt{|N_u|}}}\sum_{l’\in N_u, l’>l}{\langle v_l, v_l’ \rangle})$$ 公式6

其中,第一个部分完全等价于SVD++模型.但是FM还包括了一些用户和电影$$N_u$$之间的其它交互以及电影$$N_u$$的基础影响和$$N_u$$中的电影对之间的交互.

PITF用于标签推荐

标签预测的问题被定义为:针对一个给定的用户和物品组合对标签进行排序.这就意味着:这里有三个分类领域,包括:用户$$U$$,物品$$I$$以及标签$$T$$.在ECML/PKDD关于标签推荐的探索比赛中,一个机遇对成对交互进行因子分解的模型(PITF)实现了最佳效果.作者们在论文中展示了FM如何模拟这个模型.在使用二进制指示变量的因子分解机中,针对活跃用户$$u$$/物品$$i$$和标签$$t$$可以定义下面的模型:

$$n:=|U\cup I \cup T|, x_j:=\delta(j=i \lor j = u \lor j =t)$$
$$\Rightarrow \hat{y}(x)=\omega_0 + \omega_u + \omega_i + \omega_t + \langle v_u, v_i \rangle + \langle v_u, v_t \rangle + \langle v_i, v_t \rangle$$ 公式7

该模型用于在相同的用户/物品组合$$(u,i)$$针对两个标签$$t_A$$和$$t_B$$之间进行排序[3],优化和预测都在示例$$(u,i,t_A)$$和$$(u,i,t_B)$$之间分数的差别上进行(类似于[5,3]).因此,通过使用成对排序的优化,FM模型等价于:

$$\hat{y}(x) := \omega_t + \langle v_u, v_t \rangle + \langle v_i, v_t \rangle$$ 公式8

现在,原始的PITF模型[3]和使用二进制标识(公式8)的FM模型基本相同了.唯一的区别在于:

  • FM模型针对t有一个偏好变量$$\omega_t$$
  • FM中,对于$$(u,t)-$$和$$(i,t)-$$之间的交互针对标签($$v_t$$)生成的因子分解参数是共享的,而原始的PITF模型中这些参数是相互独立的.

除了上面的理论分析,图3通过实验展示了两个模型针对该任务都实现了可比较的预测质量.


3 FMECML/PKDD探索挑战2009的优胜模型PITF模型的推荐质量.横轴表示模型参数的数目.

FPMC(Factorized Personalized Markov Chains, 因子分解的个性化马尔科夫链)

FPMC模型[4]试图在一个在线的商店中基于用户$$u$$的最后一次购买(第$$t-1$$次)对产品进行排序.

没有只是通过特征生成,因子分解机$$(d=2)$$有相似的行为:

$$n:=|U\cup I \cup L|$$
$$x_j=1, 如果 j=i \lor j=u$$
$$ x_j=\frac{1}{\sqrt{|B_{t-1}^u|}}, 如果 j\in B_{t-1}^u$$
$$x_j=0 其它$$

其中,$$B_{t}^u\subseteq L$$为一个用户$$u$$在时间$$t$$购买过的所有物品集合(筐)(具体情况可以查阅[4]).接着:

$$\hat{y}(x)=\omega_0+\omega_u+\omega_i+\langle v_u,v_i \rangle +\frac{1}{\sqrt{|B_{t-1}^u|}}\sum_{l\in B_{t-1}^u}{\langle v_i, v_l \rangle}$$
$$+\frac{1}{\sqrt{|B_{t-1}^u|}}{\sum_{l\in B_{t-1}^u}}({w_l+\langle v_u, v_l \rangle + \frac{1}{\sqrt{|N_u|}}}\sum_{l’\in B_{t-1}^u, l’>l}{\langle v_l, v_l’ \rangle})$$ 公式9

类似于标签推荐,该模型针对排序(在这里,指的是排序物品i)进行使用和排序,因此,在预测和优化准则[4]中,只会使用$$(u,i_A,t)$$和$$(u,i_B,t)$$之间的评分差异.因此,所有不依赖于i的其它参数可以弱化,因此,FM的模型等式等价于:

$$\hat{y}(x)=\omega_i+\langle v_u,v_i \rangle +\frac{1}{\sqrt{|B_{t-1}^u|}}\sum_{l\in B_{t-1}^u}{\langle v_i, v_l \rangle}$$ 公式10

现在,我们可以发现原始的FPMC模型[4]FM模型基本上相同,除了在额外的物品偏好$$\omega_i$$上有些不同,以及FM模型中同时在$$(u,i)-$$和$$(i,l)-$$中物品中的因子分解参数的共享.

总结

  • 类似于PARAFAX或者MF这种标准的因子分解模型并不像因子分解机一样是一个通用的预测模型.相反地,FM要求特征向量分割成$$m$$个部分,并且每个部分中只有一个元素是$$1$$,其它的均为$$0$$.
  • 还有许多为了单一的任务而设计的特定因子分解模型.上面作者们也展示了因子分解机可以只通过特征提取来模拟很多最成功的因子分解模型(包括,MF,PARAFAC,SVD++,PITF,FPMC). 这使得FM可以很容易地运用于实践.

结论和未来工作

在本文中,作者们介绍了因子分解机.FMsSVMs的优点和因子分解模型的有点结合在一起.

SVMs不同,
FM可以在非常稀疏的情况下估计参数
– 模型等式是线性的,并且只依赖于模型参数
– 因此,它们可以直接在原问题上进行优化

FMs的可表示性可以与多项式SVMs有一定的可比性.与类似于PARAFAC的张量因子分解模型不同,FMs是一个可以解决任何实值向量的通用预测工具.此外,只需要通过在输入特征向量中使用核实的标识,FMs等价于或者类似于与只针对特定任务的特定先进模型,包括MF,SVD++,PITFFPMC等.

参考文献

[1] R. A. Harshman, “Foundations of the parafac procedure: models and conditions for an ’exploratory’ multimodal factor analysis.” UCLA Working Papers in Phonetics, pp. 1–84, 1970.
[2] Y. Koren, “Factorization meets the neighborhood: a multifaceted collaborative filtering model,” in KDD ’08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM, 2008, pp. 426–434.
[3] S. Rendle and L. Schmidt-Thieme, “Pairwise interaction tensor factorization for personalized tag recommendation,” in WSDM ’10: Proceedings of the third ACM international conference on Web search and data mining . New York, NY, USA: ACM, 2010, pp. 81–90.
[4] S. Rendle, C. Freudenthaler, and L. Schmidt-Thieme, “Factorizing personalized markov chains for next-basket recommendation,” in WWW ’10: Proceedings of the 19th international conference on World wide web. New York, NY, USA: ACM, 2010, pp. 811–820.
[5] T. Joachims, “Optimizing search engines using clickthrough data,” in KDD ’02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM, 2002, pp. 133–142.
[6] V. N. Vapnik, The nature of statistical learning theory. New York, NY, USA: Springer-Verlag New York, Inc., 1995.
[7] N. Srebro, J. D. M. Rennie, and T. S. Jaakola, “Maximum-margin matrix factorization,” in Advances in Neural Information Processing Systems 17. MIT Press, 2005, pp. 1329–1336.
[8] R. Salakhutdinov and A. Mnih, “Bayesian probabilistic matrix factorization using Markov chain Monte Carlo,” in Proceedings of the International Conference on Machine Learning, vol. 25, 2008.

打赏

mickey

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