双曲因子分解机*

2020-04-15王玮皓陈松灿

计算机与生活 2020年4期

王玮皓，陈松灿+

1.南京航空航天大学计算机科学与技术学院，南京 211106

2.模式分析与机器智能工业和信息化部重点实验室，南京 211106

1 引言

在信息过载时代，推荐系统是互联网应用中不可或缺的算法。推荐系统根据用户资料、购买记录、商品属性，以及时间、地点、天气等上下文信息，为用户推荐合适的产品或服务。从方法角度分类，推荐系统可以分为基于协同过滤的推荐、基于内容的推荐和两者的混合方法。

推荐场景下，特征间的交互蕴含了重要信息，例如，一个用户同时喜欢导演史蒂文·斯皮尔伯格和演员汤姆·汉克斯，那他很可能喜欢电影《拯救大兵瑞恩》。因子分解机（factorization machine，FM）[1]是近年发展出的一种有效的推荐系统模型，能够捕捉输入特征间的这种二阶交互关系。相比对率回归等线性模型，FM 本质上是二阶非线性模型，它将二阶系数表示成欧氏空间中对应嵌入向量的内积，提升了模型的泛化能力，能发现训练时未同时出现的两特征间的交互关系。FM 的输入特征通常为图1 的形式，是多个特征域的组合；输出该特征组合下，用户对商品的点击率或评分等。结合不同的损失函数，FM 可以处理分类、回归、排序等多种问题。其简单的特征工程、优越的性能、线性时间复杂度，使其自提出以来即被广泛应用于大规模商业化的推荐系统。近年来对FM 的改进层出不穷，典型的如HOFM（higher-order factorization machines）[2]借助ANOVA（analysis of variance）核将二阶FM 显式地推广至高阶，DeepFM[3]、Wide&Deep[4]通过多层神经网络隐式地建模高阶特征交互。但这些方法大量增加了模型参数，带来优化困难和过拟合风险。另外，盲目地捕捉特征之间的高阶交互会带来大量无用信息，反而可能降低模型性能。AFM（attentional factorization machines）[5]引入注意力机制对不同的特征交互项赋予不同的重要性权重，但FM 中特征嵌入向量的内积已包含了此信息，因此这一改进的作用并不显著。此外，推荐系统中用户、商品等对象的交互呈幂律分布，即热门商品和活跃用户非常少。FM 将特征嵌入到欧氏空间，但平坦的欧氏空间不具有刻画幂律分布和层次结构的能力，很大程度上限制了模型的表示能力。

Fig.1 Input feature of FM图1 FM 的输入特征

双曲空间（hyperbolic space）是一种拥有负常曲率的黎曼流形空间。出于双曲空间的几何性质，它可被视为一种连续化的树结构，近年来许多工作表明，相比平坦的欧氏空间，双曲空间更适合于有着隐含层次结构的对象的嵌入表示。Krioukov 等人[6]在双曲空间中研究了复杂网络的结构；Nickel 和Kiela[7]首次在双曲空间对词汇进行低维嵌入，结果表明双曲空间能够捕捉词汇概念之间的层次结构；Tay等人[8]将问题和回答嵌入到双曲空间中，进行智能问答；Vinh等人[9]提出的双曲空间矩阵分解方法（HyperMF）首次将用户和商品嵌入到双曲空间中，发现了用户和商品间同样存在层次结构。总的来说，如果将一组具有层次结构的对象嵌入到双曲空间，那么对象间的相似性将由它们的双曲距离决定，而层次结构则由对象到原点的距离（或称之为双曲范数）决定[10]。如图2（a）所示，在双曲空间中考察物种概念，那么“哺乳动物”这样高层次的概念相对于“人类”和“猿”等具体物种，更靠近双曲空间的原点，即双曲范数较小；而这三个概念强相关，因此它们距离上相近。再如，“蜥蜴”和“人类”都是具体的物种，它们到原点的距离相等，但两者差异较大，因而彼此距离较远。推荐系统中，用户、商品、属性等特征本身可视为一个大规模的、符合幂律分布的异构网络，具有层次结构。因此本文尝试将这些特征嵌入到双曲空间中，并以特征之间的双曲距离衡量两个特征的交互关系，进而导出了双曲因子分解机（hyperbolic factorization machine，HFM）。

Fig.2 Hyperbolic space图2 双曲空间

本文主要贡献包括：

（1）提出了基于双曲空间距离度量的因子分解机HFM，推广了FM；

（2）针对两种不同的双曲空间模型，提供了相应的基于黎曼梯度下降的优化方法；

（3）在人工和真实数据集上的实验结果表明，相比FM，HFM 不仅有效提升了性能，更重要的是能发现特征间隐含的层次关系，从而更具解释性。

2 双曲空间

针对双曲空间，目前已有多种数学模型可刻画，如庞加莱模型、双曲面模型、克莱因模型等。这些模型本质上等价，但侧重点各异。庞加莱模型在可视化嵌入对象的层次结构时相对清晰，而双曲面模型避免了计算距离时的数值不稳定。下面为完整起见，将分别加以介绍。

2.1 庞加莱模型

庞加莱模型（Poincaré model）[7]Pn=(Bn,gp) 是一个黎曼流形，其中Bn={x∈ℝn:||x||＜1}是开的n维单位球，‖· ‖ 表示欧氏空间的L2 范数。是其黎曼度量张量，ge表示欧氏空间的度量张量。庞加莱球Bn中任意两点的测地线是一段正交于Bn边界的圆弧（如图2（b））。P 上的测地线距离函数，即该模型下任意两点u,v∈Bn的双曲空间距离为：

从上式中易得出双曲空间的一些性质，如：（1）双曲空间中u、v两点的距离随u和v的范数平滑地变化，且距离函数可微；（2）欧氏距离保持不变时，两点的双曲距离随靠近单位球边界的程度指数级增加；（3）一个点与原点的双曲距离，随该点靠近单位球边界的程度指数级增加。

2.2 双曲面模型

双曲面模型又称洛伦兹模型（Lorentz model）[10]。设u,v∈ℝn+1，定义洛伦兹标量积：

则双曲面模型表示的n维双曲空间可以写成Ln=(Hn,gl)，其中是双曲面的上半叶，gl(x)=diag(-1,1,…,1)是黎曼度量张量。注意到双曲面上任一点x∈Hn满足：

因此该流形的维度为n。L 上任意两点u,v∈Hn的测地线距离为：

本质上庞加莱模型和双曲面模型等价，但由于庞加莱模型在可视化时更方便，可以通过变换p:Hn→Pn，将双曲面模型中的点映射到庞加莱模型中：

3 双曲因子分解机

3.1 因子分解机

假设输入特征是p维向量x∈ℝp，则二次多项式回归模型的表达式为：

与二阶多项式不同的是，FM 对二次系数wij进行了分解，即为每一维特征分量学习了一个欧氏空间上的嵌入向量vi，并以嵌入之间的内积作为刻画特征二阶交互xixj的二次系数，即：

其中，wb∈ℝ 是偏置，wi∈ℝ 是线性项系数。这样，FM 一方面减少了模型参数数量，减轻过拟合风险；另一方面，可以发现在训练时未出现的特征交互，提高了泛化能力。

3.2 双曲因子分解机

Vinh 等人[9]将用户和商品嵌入到庞加莱双曲空间模型中，发现了用户和商品间隐含的层次结构。例如，热门商品被很多用户购买，那么该商品与很多用户存在连接关系，作为一个中心节点，它将被嵌入到双曲空间的原点附近，这样它几乎与所有用户的双曲距离都相对较近。

考虑图3 所示的数据集，用户和商品之间的连线表示用户对商品感兴趣，商品和品牌之间的连线表示商品属于该品牌，给定（用户，商品，品牌）的特征组合（如图1 的特征输入形式），推荐系统需要判断用户是否对这件商品感兴趣。不难发现特征间存在连接关系，即特征之间可构成一个异构网络[11]，而FM中的二阶交互系数可视为这一异构网络上的边权。事实上，这样的异构图存在着层次结构，例如四件商品都属于“品牌X”，那么特征“品牌X”就是这些商品的中心节点。双曲空间适合于具有层次结构对象的嵌入，将双曲几何引入推荐系统可以增强模型的表示能力，这就为提出双曲因子分解机（HFM）提供了动机。为每一维特征xi学习一个双曲空间中的嵌入向量vi，将HFM 定义为：

其中，dh(vi,vj)是特征嵌入向量vi和vj的双曲距离，dh可取作庞加莱模型的距离度量式或双曲面模型的距离度量式。分别将基于庞加莱模型和双曲面模型的HFM 记为P-HFM 和L-HFM。m(·)称为匹配函数，通过匹配函数可以控制交互系数的符号。m(·)可为对数函数、等值映射、取相反数或线性变换等，实验发现m(·)取线性变换最佳，即：

其中，β,c∈ℝ 是可训练的标量参数。

Fig.3 Heterogeneous network of users,items and brand图3 用户、商品和品牌特征构成的异构网络

3.3 目标函数与黎曼梯度下降

推荐系统中，浏览、收藏、购买等隐式反馈远远多于评分等显式反馈，且隐式反馈更易获取，因此选取基于隐式反馈的贝叶斯个性化排序（Bayesian personalized ranking，BPR）[12]作为模型的目标函数。BPR是一种排序损失函数，给定用户u，用户访问过的商品i和另一个由负采样得到的商品j构成的三元组(i,j,k)，其优化目标是最大化用户u喜欢商品i更甚于商品j的似然概率P(i≻u j)。若HFM 对(u,i)组合特征的输出为，对(u,j) 组合特征的输出为，则，σ表示Sigmoid 函数。最终目标函数为：

采用Adam[13]算法对目标函数进行优化。由于HFM 中特征分量的嵌入vi是双曲空间中的模型参数，因此优化时需要进行黎曼梯度下降（Riemannian gradient descent，RSGD）[14]。RSGD 可分解为三个步骤：（1）计算关于vi的欧氏梯度∇El(vi)；（2）将其转换为黎曼梯度∇Rl(vi)；（3）根据黎曼梯度更新嵌入向量。

庞加莱模型中[7]，将欧氏梯度转换为黎曼梯度只需乘上一个标量，即：

更新步骤为：

双曲面模型的RSGD[10]相对复杂一些，首先将欧氏梯度转换到黎曼梯度。

然后进行参数更新：

其中，hr=η∇Rl(vi)，η为学习率。

需要注意的是，Adam 实质上是根据训练过程中各参数梯度的累积，对各参数的学习率乘上自适应的修正系数。因此，根据式（6）或式（8）对vi的梯度进行转换后，利用黎曼梯度更新这些参数学习率的修正系数，最后再按式（7）或式（9）进行更新。

迭代更新直至损失收敛，迭代时每一步的具体更新流程如算法1 所示。

算法1 双曲因子分解机的Adam 优化算法

4 实验与分析

4.1 数据集及其划分

在人工数据集和公开的真实数据集上进行了实验：

（1）人工数据集如图3 所示，详细含义已在3.2 节介绍过。

（2）Amazon 数据集[15]包含电商网站上大量的购买记录和商品的类目信息，使用了其中Sports、Toys、Automotive、Office 共4 个子集。如表1 用户平均访问数、商品平均访问数两列所示，该数据集的用户-商品交互高度稀疏，能够检验模型在稀疏数据上的性能。

（3）GoogleLocal 数据集[16]包含了美国各州用户前往商铺消费的记录，以及商铺的经营类型和经纬度信息，使用了Texas、California、Florida共3 个子集。

本节中“商品”指物品或商铺，“访问”指购买或消费行为。对于真实数据集，忽略访问次数小于5 次的商品和用户后，相关统计信息如表1 所示。将每个用户的访问记录按时间排序，然后将每个用户最后访问的商品划入测试集，前一个商品划入验证集，其余作为训练集。

4.2 实验结果与分析

基于PyTorch 实现了P-HFM 和L-HFM（代码见https://github.com/heygrain/hfm），以及四种对比方法FM[1]、DeepFM[3]、AFM[5]和HyperMF[9]。对于DeepFM的深度网络部分，为防止参数过多造成过拟合，设置两个隐层单元数分别为32 和16，并按原文使用批归一化（batch normalization）[17]和dropout[18]；对于AFM，设置注意力网络隐层单元数为嵌入维数的一半，并按原文使用dropout；对于双曲空间上的模型HyperMF、P-HFM、L-HFM，为双曲空间嵌入向量单独设定了学习率。

为展示HFM 的表示能力和有效性，在图3 的人工数据集上进行了特征嵌入分析，为方便起见，这里取匹配函数m(dh)=-dh。图3 表示用户A、B都喜欢商品1、2，而用户C、D都喜欢商品3、4，且商品1～4都属于“品牌X”。训练P-HFM 至收敛时，特征在双曲空间中的嵌入如图4（a），具有明显的层次结构：商品1～4 都属于“品牌X”，因此“品牌X”靠近双曲空间的原点，与其他所有特征嵌入的双曲距离都较小；用户A与B都喜欢商品1 和2，因而这4 个特征的嵌入聚在一起；同样地，用户C、D和商品3、4 也聚在一起。图4（b）展示了Florida 数据集上的训练结果，为清晰起见，只显示了验证集样本的特征嵌入，同时未画出经纬度特征的嵌入，发现店铺经营类型作为高层级概念被嵌入到原点附近。以上两例充分说明了HFM 能捕捉特征间的交互和层次结构。

Table 1 Statistics of datasets表1 数据集的统计信息

在真实数据集上进行实验时，针对所有模型，Amazon 的4 个数据集的特征嵌入维数设为30，GoogleLocal 的3 个数据集的特征嵌入维数设为10，其他超参数在验证集上用网格搜索的方式确定。

在测试集上使用命中率（hit ratio）HR@k评价模型，即对测试集中每个用户随机采样99 个负样本商品，并与该用户实际访问的商品一同输入模型进行预测，按模型输出值从大到小排序，若该用户实际访问商品排在前k则称为命中，HR@k表示测试集的命中比例。表2 为k=5 的实验结果，表3 为k=10 的实验结果，星号表示本文提出的方法。

可以发现，L-HFM 在大多数情形下表现最优，个别数据集上为次优。P-HFM 的表现较L-HFM 稍有欠缺，原因是庞加莱模型的距离函数式中分母可能接近0，导致数值计算不稳定。

与FM 相比，L-HFM 和P-HFM 的可学习参数数量几乎一致，而L-HFM 性能更优，说明双曲空间更适合推荐场景下的特征嵌入。对于DeepFM，尽管控制了深度网络的参数数量，过拟合仍无法避免，究其原因，一方面DeepFM 可能适合更大规模的数据，另一方面盲目引入高阶交互带来了大量无用信息。对于AFM，由于FM 的二次项系数已包含特征交互的重要性程度，因此再引入注意力机制赋予其重要性权重，带来的性能提升有限。

与同样采用双曲距离度量的HyperMF 相比，PHFM 可视为HyperMF 的推广，即当输入特征为用户ID 和商品ID 的one-hot 编码，且wb=0,w1=w2=…=wp=0 时，P-HFM 退化为HyperMF。注意到在稀疏的Amazon 数据集上，HyperMF 的性能远远低于HFM，甚至低于FM，这是因为HyperMF 使用矩阵分解的方式学习商品和用户在双曲空间中的嵌入，只能利用有限的、稀疏的协同信息，无法利用商品特征、用户资料、上下文等补充信息。而HFM 既利用了双曲空间的优势，又继承了FM 处理其他特征的便捷性，可以将其他信息囊括到输入特征中，而无需改造模型本身，有效提高了用户-商品交互十分稀疏情形下的模型性能。

4.3 参数敏感性分析

Fig.4 Learned feature embeddings图4 学到的特征嵌入

Table 2 Results on test set with respect to HR@5表2 测试集上的HR@5 指标

Table 3 Results on test set with respect to HR@10表3 测试集上的HR@10 指标

嵌入维数是HFM的重要超参数，在Office和Automotive 数据集上考察嵌入维数对模型性能的影响，其他数据集上结果类似。图5 绘制了随嵌入维数的增加，模型性能的变化。可以看出，模型性能对于嵌入维数不敏感。当嵌入维数足够大时，增加嵌入维数不再提升模型性能。

5 结束语

考虑到推荐系统中用户、商品、属性等特征间存在层次结构，以及双曲空间适合于具有层次结构对象的嵌入表示，本文在FM 的基础上，提出了基于双曲空间距离度量的HFM，以特征间的双曲距离评估其二阶交互，并针对庞加莱和双曲面两种双曲空间模型，提供了相应的黎曼梯度下降优化算法。实验结果表明，在等量参数的情形下，HFM 获得了比FM更好的性能，更重要的是能发现特征间隐含的层次结构，提供了部分可解释性。