第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 的研究，如 Math￾ieu 等 [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 < vi , vj > 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·