稀疏化的因子分解机

郭少成，陈松灿

线性回归模型因为其较好的泛化性能及相对简单快速的求解方法而受到广泛关注，并已成为统计机器学习中一类最基本的方法[1]。虽然上述线性模型在现实中有广泛应用。但只有当问题的输入呈线性关系时，它才会有较好的效果。另一方面，线性模型本身缺乏对输入变量间关系的探索机制。由此自然地转向考虑含有二阶交叉项的线性模型(此处线性相对参数而言)。含有二阶交叉项的线性模型考虑了输入特征间的相互关系。因此，当输入数据的特征间呈非线性关系，特别是二次关系时，其性能优于一般的线性模型。

推荐系统近年来广受关注[2]，广义上的推荐系统就是给用户推荐物品的系统，它还可具体到一些特定领域，如音乐、书籍等。推荐系统的主要任务是根据用户的历史行为记录去预测用户未来可能会购买的物品。从本质上说就是探索用户与用户间以及用户与物品间的关系，也就是变量与变量间的关系。针对推荐系统，最近S. Rendle等[3]提出了一个新的二阶交叉项模型：因子分解机(FM)。在FM中，每个变量xi都对应着一个在隐空间的k维的向量vi, xi和xj的交叉项系数等于xi和xj的内积，当输入数据非常稀疏时，一般的二阶交叉模型无法学习到有效的交叉项系数。而FM分解了交叉项系数，这个特性使得FM能学习到数据中隐藏的变量间相互关系[3-4]。因此，FM特别适用于稀疏数据。

虽然对交叉项系数进行分解能显著提升模型性能，但当k(因子分解维度)较大时，FM模型包含大量参数，为了避免过拟合，常常需要对目标函数添加正则化项。一种常用的正则化方法是添加范数。但是，对于高维数据，我们希望选出那些最具判别性的特征。通常的做法是向目标损失函数添加能够诱导稀疏解的正则化项，通过优化正则化的目标函数来获得稀疏解。比如在线性回归中，向目标函数添加范数的正则项[5]，不仅能防止过拟合，还能起到特征选择的作用。虽然，范数能获得稀疏解，但是，这种稀疏并不包含结构信息。在FM中，其特征应当满足这样一种性质，即涉及同一个特征的线性项和二阶项要么同时被选要么同时不被选，当该特征是噪音时，应当同时不被选，而当该特征是重要变量时，应当同时被选。而范数不能利用此先验结构信息。

Group Lasso(GL) 是 M.Yuan 等[6]基于 Lasso 提出的用于对组变量进行特征选择的方法，与Lasso不同的是，GL能同时选择或者不选组内的所有变量。首先根据先验知识将变量按照相关性划分为不同组，从聚类角度看就是将同类变量划分为同组，不同类变量划分为不同组。在FM中，将关于特征xi的线性项系数ωi和其在隐空间的特征表示向量vi分在同组中，这样，GL就能保证当xi是噪音时，ωi和vi同时不选，反之，则同时选择。虽然GL能实现这种结构稀疏，但是，对于选中的组，并不是所有特征都是有用的。因此，GL的使用有非常大限制，有必要继续选择组内重要的特征。

Simon等[7]在GL的基础上提出了基于Sparse Group Lasso（SGL）的线性回归模型。与GL相同的是它们都对变量进行分组，与GL不同的是,SGL在GL的基础上，继续选择组内重要特征。 因此，SGL能同时实现组间稀疏和组内稀疏, 而GL只实现了组间稀疏。SGL结合了Lasso和GL的优点，当待求变量存在结构稀疏信息时，仅使用Lasso会丢失结构信息，而仅使用GL又会导致求得冗余的解。基于上述事实，SGL既保留了GL的结构信息，又具有Lasso的高效特征选择的能力。

从另一角度看，当输入的数据非常稀疏而k选择较大值时，FM容易过拟合。此时，SGL的组内稀疏能通过特征选择控制k的大小。而且，不同的特征由于重要程度的不同，其对应的分解向量v的维度也应当不同，所以，组内稀疏在一定程度上通过特征选择对不同维度特征自适应了最优的k值。

当前虽然已有一些关于FM的研究，如Mathieu等[8]在FM的基础上进一步提出了高阶因子分解机(阶数≥3)，M. Li等[9]提出了分布式的FM以及W-S CHIN等[10]提出了针对二类分类问题的FM的优化算法并将其并行化。但是，它们并没有探索FM的稀疏化机制。本文首次针对FM的二阶特征结构提出了SGL-FM，而且，本文的方法也可以直接推广到高阶的FM中以探索高阶FM的稀疏化机制。

1 因子分解机

1.1 目标函数

FM的基本模型如下：

式(1)也可变形为

FM的目标函数如下：

1.2 优化方法

目前已经有多种基于迭代的优化算法被提出用于优化FM，如MCMC, ALS[12]等。其中最常用的是随机梯度下降法（SGD），即每次随机选取一个样本计算损失函数关于变量的梯度，之后用梯度更新待求变量，如此迭代便可优化目标函数。

式中：η是学习率，表示每次梯度更新的步长。对于最小平方损失函数有:

将式(2)对各个参数求导可得[12]：

基于式(5)～(7), 即可根据给定的样本计算损失函数关于变量的梯度。

2 基于SGL的因子分解机

2.1 目标函数

本文通过对损失函数添加SGL的正则项以期望得到含有结构稀疏性质的解向量, SGL-FM的目标函数如下:

式中：将ωi和分为一组，共分为p组，其中表示同时选择或同时不选ωi和vi，实现了组间稀疏。表示对选中的ωi和vi进一步进行特征选择，实现了组内稀疏，而组内稀疏也相当于对各个维度自适应选择最优k值。值得注意的是，范数均非光滑，且损失函数非凸。因此，目标函数非凸非光滑，而FM的目标函数非凸但光滑，因此，优化式(8)具有更大的挑战, 不能照搬FM的优化方法。在下一节中，我们给出优化该目标函数的有效算法。实验结果也表明，该算法能有效收敛。

2.2 优化方法

因为L1-FM和GL-FM均为SGL-FM的特例，给出SGL-FM的优化方法后，L1-FM和GL-FM的优化方法可以直接得到，因此本文仅关注SGLFM的优化。FM可以使用SGD算法优化，但是在SGL-FM中，由于范数和范数在零点不可微，虽然也可利用次梯度的方法迭代。但是，直接利用次梯度迭代很少能使变量达到不可微点[11]，也即很少会得到含有零元素的解向量，而在很多情况下零点才是目标函数的局部最小点。从另一个角度看，稀疏解能够体现目标变量的结构信息。使用次梯度优化方法得到的结果相悖于我们期望的稀疏结果。所以，本文引入了前向后向切分算法(forward backward splitting, FOBOS)[11]来优化该问题。

2.2.1 FOBOS算法

FOBOS是一种基于迭代优化的算法框架，主要用来求解含有正则项的目标函数的优化问题，特别是一些不可微的正则项如:、（Group Lasso）、等[11]，相比于直接用次梯度计算，使用FOBOS算法得到的模型具有更好的预测性能和更符合问题先验的稀疏结构[11]。

式中：gft为在t时刻损失函数关于权重的梯度,为t时刻的学习率，是在式(10)迭代中正则项前的系数，在具体算法实现中，通常设置。步骤1）等价于标准的无正则项梯度下降过程，式(10)中结果是在第一步结果基础上进行了微调，一方面希望新的结果尽可能靠近第一步的结果，另一方面还需要尽可能最小化。

2.2.2 利用FOBOS算法求解SGL-FM

根据FOBOS算法，首先将SGL-FM的目标函数分为两部分:

Liu等在文献[13]中提出了一种有效算法用于求解含有树结构信息的正则化问题。本文中的SGL是其中一种特例。如图1所示，SGL的结构可以表示成p棵树，每棵树的根节点包含了第i维特征的一阶系数ωi和其在隐空间的特征表示向量vi，子节点分别是其各个分量，SGL相当于对树的每个节点都添加了范数的约束。

图1 树结构的SGLFig. 1 SGL can be represented as tree structures

由文献[13]，我们在算法1中直接给出了优化式(13)的具体流程。并在算法2中给出了利用FOBOS算法优化SGL-FM的完整流程。

算法1 树结构正则项的优化算法

1) for i = 1: p do

3) for j = 1: k+1

6) end if

7) end for

10) end if

11) end for

算法2 用于求解SGL-FM的FOBOS算法

1) for k=1:num_epoch %迭代次数

2) 随机排列所有训练样本

3) for i = 1:num_samples %遍历所有样本

4) 取出样本xi

5) 根据式(12)执行随机梯度下降

6) 根据算法1优化式(13)

7) end for

8) end for

3 实验与分析

3.1 实验设置与实验数据

为了验证算法的性能，在3个推荐系统数据集上进行了实验，数据的基本信息如表1所示，其中Movielens的两个数据均为电影评分数据, Last.fm为音乐推荐数据，所有数据均采用One-Hot-Encoding编码方式。本文将所有数据均划分70%作为训练集，30%作为测试集。

表1 实验数据Table 1 Experimental datasets

实验不仅对比了SGL-FM、FM、L1-FM和GLFM等方法。还加入了线性模型Lasso和一般的二阶回归模型（SEC-REG）作为基准对比方法。

所有方法的超参数均采用3折交叉验证选取。FM、Lasso以及SEC-REG的所有正则化参数均从{0.000 01, 0.000 1, 0.001, 0.01, 0.1, 1}中选取，而SGL-FM、L1-FM和GL-FM的超参数均从{10-6, 10-5,10-4, 10-3}中选取。

实验以均方根误差（RMSE）作为评价准则，其计算公式为

式中：na表示线性项系数和二阶项系数矩阵中所有分量的个数，即；nz表示这些分量中零元素个数。

3.2 性能与稀疏度分析

图2～4 分别比较了各个算法在3个数据集上的RMSE和稀疏度随着k的变化趋势，可以看出，线性模型Lasso由于未探索变量间的关系，因此效果较差。而由于数据过于稀疏，二阶模型SECREG的精度也差于因子分解机类算法。

图2 Movielens 100 k实验结果Fig. 2 Results on movielens 100 k

图3 Movielens 1 m实验结果Fig. 3 Fig 2. results on movielens 1 m

图4 Last.fm实验结果Fig. 4 Results on last.fm

比较SGL-FM与FM，可以看出在Movie-lens数据集上SGL-FM的稀疏度最高达到了20%，虽然FM有更多的参数，但是SGL-FM的性能与FM的性能非常接近，说明SGL-FM能进行有效的特征选择。在Last.fm数据上，当k＞100时, SGL-FM的稀疏度达到了25%～30%, 虽然SGL-FM的参数更少，但是其性能要优于稀疏度等于0的FM，说明由于数据各个特征的分布不同，不同特征有各自最优的k值，SGL-FM通过特征选择为各个维度自适应了最佳的k值，去除了冗余的组内特征。图5 给出了在Last.fm数据集上，当k=100时，SGL-FM求出的特征表示向量所自适应的k值分布，从图中可以看出，对于Last.fm数据，大部分特征的k值分布在50～70之间，从图5中也可以看出，当k=60时，FM的效果最好，大于60时，FM的效果开始变差，这是因为参数过多，FM发生了过拟合。比较SGL-FM与GL-FM，SGL-FM由于既实现了组内稀疏又实现了组间稀疏，因此其性能优于只实现了组间稀疏的GL-FM。从稀疏度变化中也可以看出，相比于GL包含了太多的冗余组内特征，SGL能进一步地对组内特征做特征选择，从而不仅提高稀疏度，更能提高模型的性能。比较SGL-FM与L1-FM，由于L1-FM不包含结构信息且对所有特征无差别选择，因此，虽然L1-FM有更高的稀疏度，但是其性能比SGL-FM差。

图5 SGL-FM在Last.fm上自适应的k值分布Fig. 5 The distribution of k selected by SGL-FM

3.3 收敛性分析

当采用随机梯度优化这种算法时，算法的收敛性是常常需要考虑的问题，由于FM的特殊性，其目标函数关于待求参数非凸[3]，原始文献[3]中并没有给出收敛性证明，但是实验结果表明，FM是收敛的，图6给出了本文提出的算法和FM在两个数据集上的迭代过程，可以看出，所有算法均稳定收敛。而且本文提出的SGL-FM，L1-FM以及GLFM具有更快的收敛速率，这是由于SGL-FM等去除了噪音的干扰，因而收敛更快。

图6 各算法训练和测试RMSE随着迭代次数的变化Fig. 6 The training RMSE and testing RMSE w.r.t the iteration times

4 结束语

考虑到因子分解机特殊的二阶特征结构，本文结合了GL和Lasso的优点，提出了基于Sparse Group Lasso的因子分解机。同时，作为SGL-FM的特例，我们还导出了L1-FM和GL-FM。不同于一般的二阶模型和一般的FM，SGL-FM的目标函数非凸且非光滑，本文引入了FOBOS算法来优化该问题。SGL-FM不仅获得了比FM更稀疏的解，节省了内存空间，更能通过去除噪音特征，从而提升性能，实验结果也证明了这一点。

[1]RAO C R, TOUTENBURG H. Linear models[M]. New York: Springer, 1995: 3–18.

[2]ADOMAVICIUS G, TUZHILIN A. Context-aware recommender systems[M]. US: Springer, 2015: 191–226.

[3]RENDLE S. Factorization machines[C]//IEEE 10th International Conference on Data Mining. Sydney, Australia, 2010:995–1000.

[4]RENDLE S. Learning recommender systems with adaptive regularization[C]//Proceedings of the fifth ACM internation-al conference on Web search and data mining. Seattle, USA,2012: 133–142.

[5]TIBSHIRANI R. Regression shrinkage and selection via the lasso[J]. Journal of the royal statistical society, Series B(Methodological), 1996, 73(3): 267–288.

[6]YUAN M, LIN Y. Model selection and estimation in regression with grouped variables[J]. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2006,68(1): 49–67.

[7]SIMON N, FRIEDMAN J, HASTIE T, et al. A sparse-group lasso[J]. Journal of computational and graphical statistics,2013, 22(2): 231–245.

[8]BLONDEL M, FUJINO A, UEDA N, et al. Higher-order factorization machines[C]//Advances in Neural Information Processing Systems. Barcelona, Spain 2016: 3351–3359.

[9]LI M, LIU Z, SMOLA A J, et al. DiFacto: distributed factorization machines[C]//Proceedings of the Ninth ACM International Conference on Web Search and Data Mining. San Francisco, USA, 2016: 377–386.

[10]CHIN W S, YUAN B, YANG M Y, et al. An efficient alternating newton method for learning factorization machines[R].NTU:NTU,2016.

[11]DUCHI J, SINGER Y. Efficient online and batch learning using forward backward splitting[J]. Journal of Machine Learning Research, 2009, 10(12): 2899–2934.

[12]RENDLE S. Factorization machines with libfm[J]. ACM transactions on intelligent systems and technolog, 2012,3(3): 57.

[13]LIU J, YE J. Moreau-Yosida regularization for grouped tree structure learning[C]//Advances in Neural Information Processing Systems. Vancouver, Canada, 2010: 1459–1467.