【人工智能基础】稀疏化的因子分解机（南京航空航天大学：郭少成，陈松灿）.pdf_大学文库

第12卷第6期智能系统学报 Vol.12 No.6 2017年12月 CAAI Transactions on Intelligent Systems Dec.2017 D0:10.11992/tis.201706030 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20171109.1250.008.html 稀疏化的因子分解机郭少成，陈松灿 (南京航空航天大学计算机科学与技术学院，江苏南京210016) 摘要：因子分解机（简称为FM)是最近被提出的一种特殊的二阶线性模型，不同于一般的二阶模型，FM对二阶项系数进行了分解，这种特殊的结构使得M特别适用于高维且稀疏的数据。虽然FM在推荐系统领域已获得了应用，但FM本身并未显式考虑变量的稀疏性，特别当变量中包含结构稀疏信息时。因此，FM的二阶特征结构使其特征选择时应当满足这样一种性质，即涉及同一个特征的线性项和二阶项要么同时被选要么同时不被选，当该特征是噪音时，应当同时不被选，而当该特征是重要变量时，应当同时被选。考虑到这种结构特性，本文提出了一种基于稀疏组Lasso的因子分解机(SGL-FM).通过添加稀疏组Lsso的正则项，不仅实现了组间稀疏，还实现了组内稀疏。从另一个角度看，组内稀疏也相当于对因子分解的维度k进行了控制，使其能根据数据的不同而自适应地调整维度 k。实验结果表明，本文提出的方法在保证了相当精度甚至更优精度的情况下，获得了比FM更稀疏的模型。关键词：因子分解机：稀疏；稀疏组Lsso;特征选择；推荐系统中图分类号：TP391文献标志码：A文章编号：1673-4785(2017)06-0816-07 中文引用格式：郭少成，陈松灿.稀疏化的因子分解机.智能系统学报，2017,12(6：816-822 英文引用格式：GUO Shaocheng,CHEN Songcan..Sparsified factorization machineJ.CAAI transactions on intelligent systems,, 2017,12(6):816-822. Sparsified factorization machine GUO Shaocheng,CHEN Songcan (College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China) Abstract:Factorization machine(FM)is a recently proposed second-order linear model.One of its main advantages is that the interactions within it are factorized,making it suitable for data with high dimensionality and high sparsity Though FM has been applied in recommender systems,it fails to consider the sparsity of variables explicitly,especially when the variable contains information on structural sparsity.Therefore,the process of feature selection should meet the following requirements:the linear terms and second-order terms that share the same feature should be included or ex- cluded at the same time;when the feature is noise,both should be excluded,otherwise,both should be included.Based on the sparse structure described above,this paper proposes a sparse group lasso-based factorization machine(SGL- FM).By adding sparse group lasso to the loss function,SGL-FM not only achieves sparsity between groups but also within groups.From another point of view,sparsity within groups can be seen as a method of controlling the dimension- ality of the factorization;therefore,SGL-FM chooses the best k automatically when faced with datasets with different properties.The experimental results show that by applying the proposed method,under conditions of excellent precision, a model with more sparsity than FM was obtained. Keywords:factorization machine;sparsity;sparse group lasso;feature selection;recommender systems 线性回归模型因为其较好的泛化性能及相对简机器学习中一类最基本的方法。虽然上述线性模单快速的求解方法而受到广泛关注，并已成为统计型在现实中有广泛应用。但只有当问题的输入呈线收稿日期：2017-06-09.网络出版日期：2017-11-09. 性关系时，它才会有较好的效果。另一方面，线性基金项目：国家自然科学基金项目(61472186). 通信作者：陈松灿.E-mail:s.chen@nuaa.edu.cn, 模型本身缺乏对输人变量间关系的探索机制。由此

DOI: 10.11992/tis.201706030 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20171109.1250.008.html 稀疏化的因子分解机郭少成，陈松灿（南京航空航天大学计算机科学与技术学院，江苏南京 210016）摘要：因子分解机 (简称为 FM) 是最近被提出的一种特殊的二阶线性模型，不同于一般的二阶模型，FM 对二阶项系数进行了分解，这种特殊的结构使得 FM 特别适用于高维且稀疏的数据。虽然 FM 在推荐系统领域已获得了应用，但 FM 本身并未显式考虑变量的稀疏性，特别当变量中包含结构稀疏信息时。因此，FM 的二阶特征结构使其特征选择时应当满足这样一种性质，即涉及同一个特征的线性项和二阶项要么同时被选要么同时不被选，当该特征是噪音时，应当同时不被选，而当该特征是重要变量时，应当同时被选。考虑到这种结构特性，本文提出了一种基于稀疏组 Lasso 的因子分解机 (SGL-FM)，通过添加稀疏组 Lasso 的正则项，不仅实现了组间稀疏，还实现了组内稀疏。从另一个角度看，组内稀疏也相当于对因子分解的维度 k 进行了控制，使其能根据数据的不同而自适应地调整维度 k。实验结果表明，本文提出的方法在保证了相当精度甚至更优精度的情况下，获得了比 FM 更稀疏的模型。关键词：因子分解机；稀疏；稀疏组 Lasso；特征选择；推荐系统中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2017)06−0816−07 中文引用格式：郭少成, 陈松灿. 稀疏化的因子分解机[J]. 智能系统学报, 2017, 12(6): 816–822. 英文引用格式：GUO Shaocheng, CHEN Songcan. Sparsified factorization machine[J]. CAAI transactions on intelligent systems, 2017, 12(6): 816–822. Sparsified factorization machine GUO Shaocheng，CHEN Songcan (College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China) Abstract: Factorization machine (FM) is a recently proposed second-order linear model. One of its main advantages is that the interactions within it are factorized, making it suitable for data with high dimensionality and high sparsity. Though FM has been applied in recommender systems, it fails to consider the sparsity of variables explicitly, especially when the variable contains information on structural sparsity. Therefore, the process of feature selection should meet the following requirements: the linear terms and second-order terms that share the same feature should be included or excluded at the same time; when the feature is noise, both should be excluded, otherwise, both should be included. Based on the sparse structure described above, this paper proposes a sparse group lasso-based factorization machine (SGLFM). By adding sparse group lasso to the loss function, SGL-FM not only achieves sparsity between groups but also within groups. From another point of view, sparsity within groups can be seen as a method of controlling the dimensionality of the factorization; therefore, SGL-FM chooses the best k automatically when faced with datasets with different properties. The experimental results show that by applying the proposed method, under conditions of excellent precision, a model with more sparsity than FM was obtained. Keywords: factorization machine; sparsity; sparse group lasso; feature selection; recommender systems 线性回归模型因为其较好的泛化性能及相对简单快速的求解方法而受到广泛关注，并已成为统计机器学习中一类最基本的方法[1]。虽然上述线性模型在现实中有广泛应用。但只有当问题的输入呈线性关系时，它才会有较好的效果。另一方面，线性模型本身缺乏对输入变量间关系的探索机制。由此收稿日期：2017−06−09. 网络出版日期：2017−11−09. 基金项目：国家自然科学基金项目（61472186）. 通信作者：陈松灿. E-mail：s.chen@nuaa.edu.cn. 第 12 卷第 6 期智能系统学报 Vol.12 No.6 2017 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2017

第6期郭少成，等：稀硫化的因子分解机 ·817· 自然地转向考虑含有二阶交叉项的线性模型（此处 Simon等m在GL的基础上提出了基于Sparse 线性相对参数而言)。含有二阶交叉项的线性模型 Group Lasso(SGL)的线性回归模型。与GL相同的考虑了输入特征间的相互关系。因此，当输入数据是它们都对变量进行分组，与GL不同的是，的特征间呈非线性关系，特别是二次关系时，其性 SGL在GL的基础上，继续选择组内重要特征。因能优于一般的线性模型。此，SGL能同时实现组间稀疏和组内稀疏，而GL只推荐系统近年来广受关注)，广义上的推荐系实现了组间稀疏。SGL结合了Lasso和GL的优统就是给用户推荐物品的系统，它还可具体到一些点，当待求变量存在结构稀疏信息时，仅使用特定领域，如音乐、书籍等。推荐系统的主要任务 Lasso会丢失结构信息，而仅使用GL又会导致求得是根据用户的历史行为记录去预测用户未来可能会冗余的解。基于上述事实，SGL既保留了GL的结购买的物品。从本质上说就是探索用户与用户间以构信息，又具有Lasso的高效特征选择的能力。及用户与物品间的关系，也就是变量与变量间的关从另一角度看，当输入的数据非常稀疏而k选系。针对推荐系统，最近S.Rendle等提出了一个择较大值时，FM容易过拟合。此时，SGL的组内稀新的二阶交叉项模型：因子分解机(FM)。在FM中，疏能通过特征选择控制k的大小。而且，不同的特每个变量x,都对应着一个在隐空间的k维的向量征由于重要程度的不同，其对应的分解向量ⅴ的维 x,和x的交叉项系数等于x,和x的内积，当输入度也应当不同，所以，组内稀疏在一定程度上通过数据非常稀疏时，一般的二阶交叉模型无法学习到特征选择对不同维度特征自适应了最优的k值。有效的交叉项系数。而FM分解了交叉项系数，这当前虽然已有一些关于FM的研究，如Math- 个特性使得FM能学习到数据中隐藏的变量间相互 ieu等在FM的基础上进一步提出了高阶因子分关系B。因此，FM特别适用于稀疏数据。解机（阶数≥3），MLi等提出了分布式的FM以及虽然对交叉项系数进行分解能显著提升模型性 W-SCHN等o提出了针对二类分类问题的FM的能，但当（因子分解维度）较大时，FM模型包含大优化算法并将其并行化。但是，它们并没有探索FM 量参数，为了避免过拟合，常常需要对目标函数添的稀疏化机制。本文首次针对FM的二阶特征结构加正则化项。一种常用的正则化方法是添加范数。但是，对于高维数据，我们希望选出那些最具提出了SGL-FM,而且，本文的方法也可以直接推广判别性的特征。通常的做法是向目标损失函数添加到高阶的FM中以探索高阶FM的稀疏化机制。能够诱导稀疏解的正则化项，通过优化正则化的目 1因子分解机标函数来获得稀疏解。比如在线性回归中，向目标函数添加(，范数的正则项阿，不仅能防止过拟合，还 1.1目标函数能起到特征选择的作用。虽然，(，范数能获得稀疏 FM的基本模型如下：解，但是，这种稀疏并不包含结构信息。在FM中，其特征应当满足这样一种性质，即涉及同一个特征 x)=o (1) 的线性项和二阶项要么同时被选要么同时不被选，式(1)也可变形为当该特征是噪音时，应当同时不被选，而当该特征是重要变量时，应当同时被选。而（范数不能利用了-7☒+0 (x)= 此先验结构信息。 =1行 Group Lasso(GL)是M.Yuan等基于Lasso提 FM的目标函数如下：出的用于对组变量进行特征选择的方法，与 argmin >y)+allolk2+lVlle2 (3) Lasso不同的是，GL能同时选择或者不选组内的所有变量。首先根据先验知识将变量按照相关性划分式中：，)表示第i个样本的损失，是预测的标为不同组，从聚类角度看就是将同类变量划分为同号值，y,是样本的真实标记，和2均为控制模型复组，不同类变量划分为不同组。在FM中，将关于特杂度的超参数。FM用于回归问题时通常采用最小征x,的线性项系数)，和其在隐空间的特征表示向平方损失函数，因此有量”，分在同组中，这样，GL就能保证当x,是噪音 ,y)=(-y)2 (4) 时，，和y同时不选，反之，则同时选择。虽然 1.2 优化方法 GL能实现这种结构稀疏，但是，对于选中的组，并目前已经有多种基于迭代的优化算法被提出用不是所有特征都是有用的。因此，GL的使用有非于优化FM,如MCMC,ALS等。其中最常用的是常大限制，有必要继续选择组内重要的特征。随机梯度下降法(SGD),即每次随机选取一个样本

自然地转向考虑含有二阶交叉项的线性模型 (此处线性相对参数而言)。含有二阶交叉项的线性模型考虑了输入特征间的相互关系。因此，当输入数据的特征间呈非线性关系，特别是二次关系时，其性能优于一般的线性模型。推荐系统近年来广受关注[2] ，广义上的推荐系统就是给用户推荐物品的系统，它还可具体到一些特定领域，如音乐、书籍等。推荐系统的主要任务是根据用户的历史行为记录去预测用户未来可能会购买的物品。从本质上说就是探索用户与用户间以及用户与物品间的关系，也就是变量与变量间的关系。针对推荐系统，最近 S. Rendle 等 [3]提出了一个新的二阶交叉项模型：因子分解机 (FM)。在 FM 中，每个变量 xi 都对应着一个在隐空间的 k 维的向量 vi , xi 和 xj 的交叉项系数等于 xi 和 xj 的内积，当输入数据非常稀疏时，一般的二阶交叉模型无法学习到有效的交叉项系数。而 FM 分解了交叉项系数，这个特性使得 FM 能学习到数据中隐藏的变量间相互关系[3-4]。因此，FM 特别适用于稀疏数据。 ℓ2 ℓ1 ℓ1 ℓ1 虽然对交叉项系数进行分解能显著提升模型性能，但当 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 相同的是它们都对变量进行分组，与 G L 不同的是 , 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 的基本模型如下： yˆ(x) = ω0 + ∑p i=1 ωixi + ∑p i=1 ∑p j=i+1 xixj (1) 式 (1) 也可变形为 yˆ(x) = ω0 + ∑p i=1 ωixi + 1 2 ∑k f=1 ((∑p i=1 vi, f xi) 2 − ∑p i=1 vi, f 2 xi 2 ) (2) FM 的目标函数如下： argmin ω,V ∑n i=1 ℓ(ˆyi , yi)+λ1 ||ω||2 2 +λ2 ||V||F 2 (3) ℓ(ˆyi , yi) yˆi λ1 λ2 式中：表示第 i 个样本的损失，是预测的标号值，yi 是样本的真实标记，和均为控制模型复杂度的超参数。FM 用于回归问题时通常采用最小平方损失函数，因此有 ℓ(ˆyi , yi) = (ˆyi −yi) 2 (4) 1.2 优化方法目前已经有多种基于迭代的优化算法被提出用于优化 FM，如 MCMC, ALS[12]等。其中最常用的是随机梯度下降法（SGD），即每次随机选取一个样本第 6 期郭少成，等：稀疏化的因子分解机 ·817·

·818 智能系统学报第12卷计算损失函数关于变量的梯度，之后用梯度更新待然也可利用次梯度的方法迭代。但是，直接利用次求变量，如此迭代便可优化目标函数。梯度迭代很少能使变量达到不可微点山，也即很少假设0为所有待求参数的集合，而0表示©的分会得到含有零元素的解向量，而在很多情况下零点量，0可以是oo、0,或者V,则在第什1时刻的更新才是目标函数的局部最小点。从另一个角度看，稀公式为疏解能够体现目标变量的结构信息。使用次梯度优 1=f-n06x0,W+2a0 (5) 化方法得到的结果相悖于我们期望的稀疏结果。所式中：1是学习率，表示每次梯度更新的步长。对于以，本文引入了前向后向切分算法(forward back- ward splitting,.FOBOS)u来优化该问题。最小平方损失函数有： 2.2.1 FOBOS算法 a6o2=206xo-yo (6) 80 a0 FOBOS是一种基于迭代优化的算法框架，主要将式(2)对各个参数求导可得：用来求解含有正则项的目标函数的优化问题，特别 0 1,0=0 是一些不可微的正则项如：(1、(2、1(Group Lasso)、 ) Xi,0=w (7) C等，相比于直接用次梯度计算，使用FOBOS算 x,(∑=1'H-xy 0= 法得到的模型具有更好的预测性能和更符合问题先基于式(5)(7)，即可根据给定的样本计算损失验的稀疏结构山。函数关于变量的梯度。假设待求目标函数由两部分组成：f(ω)+（ω）， 2基于SGL的因子分解机其中f(w)一般为损失函数，本文中损失函数为最小平方损失，第2项r()是关于目标变量w的正则 2.1目标函数项。其每次迭代过程分2步本文通过对损失函数添加SGL的正则项以期 =w-mg (9) 望得到含有结构稀疏性质的解向量，SGL-FM的目标函数如下 @argmin 2+) (10) 式中：g为在1时刻损失函数f(ω)关于权重的梯度， w.V :为1时刻的学习率，+是在式(10)迭代中正则项式中：将0，和，(1≤i≤p)分为一组，共分为p组，其前的系数，在具体算法实现中，通常设置4=，。中[ω，儿，表示同时选择或同时不选，和y,实现步骤1)等价于标准的无正则项梯度下降过程，式了组间稀疏。[ω，表示对选中的，和y,进一 (10)中结果是在第一步结果w+基础上进行了微步进行特征选择，实现了组内稀疏，而组内稀疏也调，一方面希望新的结果尽可能靠近第一步的结相当于对各个维度自适应选择最优k值。值得注意果，另一方面还需要尽可能最小化(w)。的是，(2、（范数均非光滑，且损失函数非凸。因此， 2.2.2利用FOBOS算法求解SGL-FM 目标函数非凸非光滑，而FM的目标函数非凸但光根据FOBOS算法，首先将SGL-FM的目标函滑，因此，优化式(8)具有更大的挑战，不能照搬数分为两部分： FM的优化方法。在下一节中，我们给出优化该目 fwo,ω，)+(w+V (11) 标函数的有效算法。实验结果也表明，该算法能有效收敛。式(8)还包括了另外两个稀疏化模型，当假设输入一个新的样本（化，y),根据式 =0时，目标函数只有（项，简记该模型为L1- FM。当d2=0时，目标函数仅有Group Lasso项，简 (⑤)(7)、式(9)可知FOBOS算法的第1步更新公式为记该模型为GL-FM。 w。=d6-m26ro)-) 2.2优化方法 w,+号=w,-.20(x旧)-y)x 因为L1-FM和GL-FM均为SGL-FM的特例， =-2x旧)-x(②1Ψ-x) 给出SGL-FM的优化方法后，LI-FM和GL-FM的 (12) 优化方法可以直接得到，因此本文仅关注$GL- 式中1≤i≤p且1≤f≤k。 FM的优化。FM可以使用SGD算法优化，但是在设'=nd,2'=d2,:=wPeR+，则 SGL-FM中，由于2范数和C1范数在零点不可微，虽 FOBOS算法的第2步等价于优化以下问题：

计算损失函数关于变量的梯度，之后用梯度更新待求变量，如此迭代便可优化目标函数。假设 Θ 为所有待求参数的集合，而 θ 表示 Θ 的分量，θ 可以是 ω0、ωi 或者 Vij，则在第 t+1 时刻的更新公式为 θ t+1 = θ t −η( ∂ ∂θt ℓ(ˆy(xi |Θ t ), yi)+2λθt ) (5) 式中：η 是学习率，表示每次梯度更新的步长。对于最小平方损失函数有: ∂ℓ(ˆy(xi |Θ), yi) ∂θ = 2(ˆy(xi |Θ)−yi) ∂yˆ(xi |Θ) ∂θ (6) 将式 (2) 对各个参数求导可得[12] ： ∂ ∂θ yˆ(x) =    1, θ = ω0 xi , θ = ωi xi( ∑ j=1 xjvj, f − xivi, f), θ = vi, f (7) 基于式 (5)~(7), 即可根据给定的样本计算损失函数关于变量的梯度。 2 基于 SGL 的因子分解机 2.1 目标函数本文通过对损失函数添加 SGL 的正则项以期望得到含有结构稀疏性质的解向量, SGL-FM 的目标函数如下: argmin ω,V ∑n i=1 ℓ(ˆyi , yi)+λ1 ∑p i=1 ωi vi 2 +λ2 ∑p i=1 ωi vi 1 (8) vi(1 ⩽ i ⩽ p) [ωi vi] T 2 [ωi vi] T 1 ℓ2、ℓ1 式中：将 ωi 和分为一组，共分为 p 组，其中表示同时选择或同时不选 ωi 和 vi，实现了组间稀疏。表示对选中的 ωi 和 vi 进一步进行特征选择，实现了组内稀疏，而组内稀疏也相当于对各个维度自适应选择最优 k 值。值得注意的是，范数均非光滑，且损失函数非凸。因此，目标函数非凸非光滑，而 FM 的目标函数非凸但光滑，因此，优化式 (8) 具有更大的挑战, 不能照搬 FM 的优化方法。在下一节中，我们给出优化该目标函数的有效算法。实验结果也表明，该算法能有效收敛。 λ1 = 0 ℓ1 λ2 = 0 式 ( 8 ) 还包括了另外两个稀疏化模型，当时，目标函数只有项，简记该模型为 L1- FM。当时，目标函数仅有 Group Lasso 项，简记该模型为 GL-FM。 2.2 优化方法 ℓ2 ℓ1 因为 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 算法 ℓ1 ℓ2、1 ℓ∞ FOBOS 是一种基于迭代优化的算法框架，主要用来求解含有正则项的目标函数的优化问题，特别是一些不可微的正则项如: 、（Group Lasso）、等 [11] ，相比于直接用次梯度计算，使用 FOBOS 算法得到的模型具有更好的预测性能和更符合问题先验的稀疏结构[11]。 f(ω)+r(ω) f(ω) r(ω) 假设待求目标函数由两部分组成： , 其中一般为损失函数，本文中损失函数为最小平方损失，第 2 项是关于目标变量 ω 的正则项。其每次迭代过程分 2 步: ω t+ 1 2 = ω t −ηtg t f (9) ω t = argminω { 1 2 ω−ω t+ 1 2 2 +ηt+ 1 2 r(ω) } (10) f(ω) ηt ηt+ 1 2 ηt+ 1 2 = ηt ωt+ 1 2 r(ω) 式中：gf t 为在 t 时刻损失函数关于权重的梯度, 为 t 时刻的学习率，是在式 (10) 迭代中正则项前的系数，在具体算法实现中，通常设置。步骤 1）等价于标准的无正则项梯度下降过程，式 (10) 中结果是在第一步结果基础上进行了微调，一方面希望新的结果尽可能靠近第一步的结果，另一方面还需要尽可能最小化。 2.2.2 利用 FOBOS 算法求解 SGL-FM 根据 FOBOS 算法，首先将 SGL-FM 的目标函数分为两部分: f(ω0,ω,V)+r(ω+V) (11) f(ω0 ,ω,V) = ∑n i=1 ℓ(ˆyi , yi) r(ω+V) = λ1 ∑p i=1 ωi vi 2 + λ2 ∑p i=1 ωi vi 1 (x, y) 式中：且。假设输入一个新的样本，根据式 (5)~(7)、式 (9) 可知 FOBOS 算法的第 1 步更新公式为    ω t+ 1 2 0 = ω t 0 −ηt · 2(ˆy(x|Θ)−y) ωi t+ 1 2 = ωi t −ηt · 2(ˆy(x|Θ)−y)· xi v t+ 1 2 i, f = v t i, j −ηt · 2(ˆy(x|Θ)−y)· xi( ∑ j=1 xjvj, f − xivi, f) (12) 式中 1 ⩽ i ⩽ p 且 1 ⩽ f ⩽ k。 λ1 ′ = ηtλ1 λ2 ′ = ηtλ2 θ t i = [ωt i v t i ] T ∈ R 设 k+1 , , , 则 FOBOS 算法的第 2 步等价于优化以下问题： ·818· 智能系统学报第 12 卷

第6期郭少成，等：稀硫化的因子分解机 ·819· =agmn吃9-产+9儿+七19) (13) 求解含有树结构信息的正则化问题。本文中的 SGL是其中一种特例。如图1所示，SGL的结构可式中：1≤i≤p。文献11]中给出了当正则项分别为、21、时相应的求解算法，但是当正则项为以表示成p棵树，每棵树的根节点包含了第i维特 SGL时，文献[11]并没有给出其求解算法，而且直接征的一阶系数，和其在隐空间的特征表示向量，将(，2的解法推广到SGL是非平凡的。子节点分别是其各个分量，SGL相当于对树的每个 Liu等在文献[13]中提出了一种有效算法用于节点都添加了(2范数的约束。 [2] V2.2 图1树结构的SGL Fig.1 SGL can be represented as tree structures 由文献[13]，我们在算法1中直接给出了优化上进行了实验，数据的基本信息如表1所示，其中式(13)的具体流程。并在算法2中给出了利用 Movielens的两个数据均为电影评分数据，Last.fm FOBOS算法优化SGL-FM的完整流程。为音乐推荐数据，所有数据均采用One-Hot-Encod- 算法1树结构正则项的优化算法 ig编码方式。本文将所有数据均划分70%作为训输入Step1的输出8*，(1≤i≤p),入'，2'；练集，30%作为测试集。输出更新后的参数6=[w,(1≤i≤p)o 表1实验数据 1)fori=1:pdo Table 1 Experimental datasets 2)0,=0* 数据库样本数数据维度(user+item) 3)for j=1:k+1 Movielens 100k 100000 2625=943+1682 4)if (1[ll2)then]=0 Movielens 1m 1000209 9940=6040+3900 5)else ,[j]= a,[-2' 18 .a,[] Last.fm 109750 22272=12523+9749 6)end if 7)end for 实验不仅对比了SGL-FM、FM、L1-FM和GL 8)if llell'then 0=0 FM等方法。还加入了线性模型Lasso和一般的二阶回归模型(SEC-REG)作为基准对比方法。 9)else 0;= (Il0:lk2-' 所有方法的超参数均采用3折交叉验证选取。 10)end if FM、Lasso以及SEC-REG的所有正则化参数均从 11)end for {0.00001,0.0001,0.001,0.01,0.1,1}中选取，而算法2用于求解SGL-FM的FOBOS算法 SGL-FM、L1-FM和GL-FM的超参数均从{10,10，输入训练数据，正则项参数入1,2： 10,10}中选取输出Oo,w∈RP及V∈RPt。实验以均方根误差(RMSE)作为评价准则，其 I)fork仁l:num_epoch%迭代次数计算公式为 2)随机排列所有训练样本 3)fori=1:num_samples%遍历所有样本 RMSE -y)2 4)取出样本x 5)根据式(12)执行随机梯度下降式中：n为测试样本数，y,分别为第i个样本的预 6)根据算法1优化式(13) 测标号和真实标号。实验也比较了各个模型所得系 7)end for 8)end for 数的稀疏度，稀疏度的计算方式为 sparsity=是 3实验与分析 na 式中：n。表示线性项系数w∈RP和二阶项系数矩阵 3.1实验设置与实验数据 V∈Rxt中所有分量的个数，即m。=pk+1):n表示这为了验证算法的性能，在3个推荐系统数据集些分量中零元素个数

θ t i = argmin θi { 1 2 θi −θ t+ 1 2 i 2 +λ ′ 1 ∥θi∥2 +λ2 ′ ∥θi∥1 } (13) 1 ⩽ i ⩽ p ℓ1 ℓ2,1 ℓ∞ ℓ1 ℓ2,1 式中：。文献[11]中给出了当正则项分别为、、时相应的求解算法，但是当正则项为 SGL 时，文献[11]并没有给出其求解算法，而且直接将 , 的解法推广到 SGL 是非平凡的。 Liu 等在文献[13]中提出了一种有效算法用于 ℓ2 求解含有树结构信息的正则化问题。本文中的 SGL 是其中一种特例。如图 1 所示，SGL 的结构可以表示成 p 棵树，每棵树的根节点包含了第 i 维特征的一阶系数 ωi 和其在隐空间的特征表示向量 vi，子节点分别是其各个分量，SGL 相当于对树的每个节点都添加了范数的约束。由文献[13]，我们在算法 1 中直接给出了优化式 (13) 的具体流程。并在算法 2 中给出了利用 FOBOS 算法优化 SGL-FM 的完整流程。算法 1 树结构正则项的优化算法 θ t+ 1 2 i ,(1 ⩽ i ⩽ p) λ1 ′ , λ2 输入 ′ Step 1 的输出，； θ t i = [ωt i , v t i ] T 输出更新后的参数 (1 ⩽ i ⩽ p)。 1) for i = 1: p do θi = θ t+ 1 2 2) i 3) for j = 1: k+1 |θi[j]| ⩽ λ2 ′ 4) if ( ) then θi[j] = 0 θi[j] = ( |θi[j]| −λ2 ′ |θi[j]| ) 5) else · θi[j] 6) end if 7) end for ∥θi∥2 ⩽ λ1 ′ 8) if then θi = 0 θi = ( ||θi ||2 −λ1 ′ ||θi ||2 ) 9) else · θi 10) end if 11) end for 算法 2 用于求解 SGL-FM 的 FOBOS 算法输入训练数据，正则项参数 λ1, λ2； ω ∈ R p V ∈ R 输出 ω p×k 0 , 及。 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% 作为测试集。实验不仅对比了 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）作为评价准则，其计算公式为 RMSE = vt 1 n ∑n i=1 (ˆyi −yi) 2 yˆi 式中：n 为测试样本数， , yi分别为第 i 个样本的预测标号和真实标号。实验也比较了各个模型所得系数的稀疏度，稀疏度的计算方式为 sparsity = nz na ω ∈ R p V ∈ R p×k na = p(k+1) 式中：na 表示线性项系数和二阶项系数矩阵中所有分量的个数，即；nz 表示这些分量中零元素个数。 [ω1 v1 ] ω1 v1, 1 v1, 2 Ă v1, k Ă [ω2 v2 ] ω2 v2, 1 v2, 2 Ă v2, k [ωp vp ] ωp vp, 1 vp, 2 Ă vp, k 图 1 树结构的 SGL Fig. 1 SGL can be represented as tree structures 表 1 实验数据 Table 1 Experimental datasets 数据库样本数数据维度(user + item) Movielens 100k 100 000 2 625=943+1 682 Movielens 1m 1 000 209 9 940=6 040+3 900 Last.fm 109 750 22 272=12 523+9 749 第 6 期郭少成，等：稀疏化的因子分解机 ·819·

第6期郭少成，等：稀硫化的因子分解机 ·821· 择。在Last.fm数据上，当>l00时，SGL-FM的稀 1.105 .x FM test FM train 疏度达到了25%~30%，虽然SGL-FM的参数更少 1.05 SGL-FM test -e-SGL-FM train L1-FM test -L1-FM train 但是其性能要优于稀疏度等于0的FM,说明由于 1.00 L21-FM test L21-FM train 数据各个特征的分布不同，不同特征有各自最优的 05 色6锅都8装20 k值，SGL-FM通过特征选择为各个维度自适应了联0.90 最佳的k值，去除了冗余的组内特征。图5给出了在Last.fm数据集上，当k=100时，SGL-FM求出的 0.80 特征表示向量.(1≤i≤p)所自适应的k值分布，从图 0.75 中可以看出，对于Last.fm数据，大部分特征的k值 0.70 0 50 100150200250300 分布在50~70之间，从图5中也可以看出，当=60 迭代次数 (a)Movielens 100 k.=10 时，FM的效果最好，大于60时，FM的效果开始变 0.30 差，这是因为参数过多，FM发生了过拟合。比较 0.25 SGL-FM与GL-FM,SGL-FM由于既实现了组内稀 0.20 丝各麻书含产含老书馆解含林容必唐套唐在色确称秋疏又实现了组间稀疏，因此其性能优于只实现了组 x FM test SGL-FM test 间稀疏的GL-FM。从稀疏度变化中也可以看出，相 0.15 -A L1-FM test -L21-FM test 比于GL包含了太多的冗余组内特征，SGL能进一 0.10 女5mi 步地对组内特征做特征选择，从而不仅提高稀疏 LI-FM train -L21-FM train 度，更能提高模型的性能。比较SGL-FM与L1- 0.05 X长nW米关长 FM,由于L1-FM不包含结构信息且对所有特征无 0 50 100150200250300 差别选择，因此，虽然L1-FM有更高的稀疏度，但是迭代次数 (b)Last.fm.=80 其性能比SGL-FM差。 0.30 图6各算法训练和测试RMSE随着迭代次数的变化 Fig.6 The training RMSE and testing RMSE w.r.t the it- 0.25 eration times 0.20 4结束语 0.15 考虑到因子分解机特殊的二阶特征结构，本文结合了GL和Lasso的优点，提出了基于Sparse 0.10 Group Lasso的因子分解机。同时，作为SGL-FM 0.05 的特例，我们还导出了L1-FM和GL-FM。不同于一般的二阶模型和一般的FM,SGL-FM的目标函 040 60 80 100 120 数非凸且非光滑，本文引入了FOBOS算法来优化 SGL-FM自适应的K值大小该问题。SGL-FM不仅获得了比FM更稀疏的解，图5SGL-FM在Last.fm上自适应的k值分布节省了内存空间，更能通过去除噪音特征，从而提 Fig.5 The distribution of k selected by SGL-FM 升性能，实验结果也证明了这一点。 3.3收敛性分析当采用随机梯度优化这种算法时，算法的收敛参考文献：性是常常需要考虑的问题，由于FM的特殊性，其目 [1]RAO C R,TOUTENBURG H.Linear models[M].New 标函数关于待求参数非凸)，原始文献[3]中并没有 York:Springer,1995:3-18 给出收敛性证明，但是实验结果表明，FM是收敛 [2]ADOMAVICIUS G,TUZHILIN A.Context-aware recom- 的，图6给出了本文提出的算法和FM在两个数据 mender systems[M].US:Springer,2015:191-226 [3]RENDLE S.Factorization machines[C]//IEEE 10th Interna- 集上的迭代过程，可以看出，所有算法均稳定收 tional Conference on Data Mining.Sydney,Australia,2010: 敛。而且本文提出的SGL-FM,L1-FM以及GL- 995-1000. FM具有更快的收敛速率，这是由于SGL-FM等去 [4]RENDLE S.Learning recommender systems with adaptive 除了噪音的干扰，因而收敛更快。 regularization[Cl//Proceedings of the fifth ACM internation-

vi(1 ⩽ i ⩽ p) 择。在 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 差。 3.3 收敛性分析当采用随机梯度优化这种算法时，算法的收敛性是常常需要考虑的问题，由于 FM 的特殊性，其目标函数关于待求参数非凸[3] ，原始文献[3]中并没有给出收敛性证明，但是实验结果表明，FM 是收敛的，图 6 给出了本文提出的算法和 FM 在两个数据集上的迭代过程，可以看出，所有算法均稳定收敛。而且本文提出的 SGL-FM，L1-FM 以及 GLFM 具有更快的收敛速率，这是由于 SGL-FM 等去除了噪音的干扰，因而收敛更快。 4 结束语考虑到因子分解机特殊的二阶特征结构，本文结合了 GL 和 Lasso 的优点，提出了基于 Sparse Group Lasso 的因子分解机。同时，作为 SGL-FM 的特例，我们还导出了 L1-FM 和 GL-FM。不同于一般的二阶模型和一般的 FM，SGL-FM 的目标函数非凸且非光滑，本文引入了 FOBOS 算法来优化该问题。SGL-FM 不仅获得了比 FM 更稀疏的解，节省了内存空间，更能通过去除噪音特征，从而提升性能，实验结果也证明了这一点。参考文献： RAO C R, TOUTENBURG H. Linear models[M]. New York: Springer, 1995: 3–18. [1] ADOMAVICIUS G, TUZHILIN A. Context-aware recommender systems[M]. US: Springer, 2015: 191–226. [2] RENDLE S. Factorization machines[C]//IEEE 10th International Conference on Data Mining. Sydney, Australia, 2010: 995–1000. [3] RENDLE S. Learning recommender systems with adaptive regularization[C]//Proceedings of the fifth ACM internation- [4] 40 60 80 100 120 0 0.05 0.10 0.15 0.20 0.25 0.30 SGL-FM 㜖䔮Ꮐ⮰ K ը๓ᄻ 䶽⢳ը 图 5 SGL-FM 在 Last.fm 上自适应的 k 值分布 Fig. 5 The distribution of k selected by SGL-FM ౳᫥ᵥ䄛ጚ ౳᫥ᵥ䄛ጚ 0.05 0.10 0.15 0.20 0.25 0.30 (a) Movielens 100 k, k=10 0 100 50 150 200 250 300 0.70 0.75 0.80 0.85 0.90 0.95 1.00 1.05 1.10 FM test SGL-FM test L1-FM test L21-FM test FM train SGL-FM train L1-FM train L21-FM train FM test SGL-FM test L1-FM test L21-FM test FM train SGL-FM train L1-FM train L21-FM train 䔙Џ⁍᪜ (b) Last.fm, k=80 0 100 50 150 200 250 300 䔙Џ⁍᪜ 图 6 各算法训练和测试 RMSE 随着迭代次数的变化 Fig. 6 The training RMSE and testing RMSE w.r.t the iteration times 第 6 期郭少成，等：稀疏化的因子分解机 ·821·

al conference on Web search and data mining. Seattle, USA, 2012: 133–142. TIBSHIRANI R. Regression shrinkage and selection via the lasso[J]. Journal of the royal statistical society, Series B (Methodological), 1996, 73(3): 267–288. [5] 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. [6] SIMON N, FRIEDMAN J, HASTIE T, et al. A sparse-group lasso[J]. Journal of computational and graphical statistics, 2013, 22(2): 231–245. [7] BLONDEL M, FUJINO A, UEDA N, et al. Higher-order factorization machines[C]//Advances in Neural Information Processing Systems. Barcelona, Spain 2016: 3351–3359. [8] 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. [9] CHIN W S, YUAN B, YANG M Y, et al. An efficient alternating newton method for learning factorization machines [R].NTU:NTU,2016. [10] [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. RENDLE S. Factorization machines with libfm[J]. ACM transactions on intelligent systems and technolog, 2012, 3(3): 57. [12] LIU J, YE J. Moreau-Yosida regularization for grouped tree structure learning[C]//Advances in Neural Information Processing Systems. Vancouver, Canada, 2010: 1459– 1467. [13] 作者简介：郭少成，男，1993 年生，硕士研究生，主要研究方向为机器学习、模式识别。陈松灿，男，1962 年生，教授，博士生导师，博士，中国人工智能学会机器学习专委会主任，CCF 高级会员，主要研究方向为模式识别、机器学习、神经计算。在国际主流期刊和顶级会议上发表多篇学术论文并多次获奖。 ·822· 智能系统学报第 12 卷