重磅 | eBay提出强大的轻量级推荐算法——洛伦兹因子分解机

供稿 |  eBay Search Science Team

作者 | 徐粲然

编辑 | 顾欣怡

本文2770字，预计阅读时间9分钟

摘要

推荐系统和点击率预测要求必须对用户行为的特征交互进行建模。近几年来，随着深度学习的发展，新兴的深度模型（例如DeepFM, xDeepFM和Deep & Cross)层出不穷，这也使得算力、模型容量和精度三者之间的权衡变得非常重要。 针对这类问题，eBay的研究员提出了一种被称作洛伦兹因子分解机的模型，曾发表于今年2月在纽约举行的AI顶级会议AAAI会议上。 该方法不再使用深度模型的结构，但可以达到深度模型的准确率，而且能极大降低模型的参数量和训练时间。

一、导言

电商网站通过推荐系统和点击率预测向用户提供商品信息推荐和广告位排名。随着技术的发展，推荐系统会根据用户的兴趣进行个性化调整。如图1所示，通过对用户行为数据、商品属性数据的收集，系统将返回给用户感兴趣的商品。

图1: 个性化推荐系统的示意图

在大数据时代，大规模的推荐系统和点击率预测面临的最大挑战，就是 绝大多数能过捕获的特征都是离散型的，因此导致模型的特征空间极度稀疏。 在这种情况下，因子分解机(FM)提出用向量内积表示的二阶特征交互来进行建模。最近几年，越来越多的研究者考虑用高阶的特征交互或者利用深度学习方法来提高特征交互的表征能力。其中最有代表性的例子是 DeepFM ，它在传统的FM之上加入了多层MLP来达到学习深层表征的目的。

而在本研究中，我们重新检查了向量内积作为特征交互基础结构的利弊。2017年，Hsieh等人 [1] 曾经提出 用欧式空间的度量代替内积 是更合理的选择，原因是利用内积会导致直觉上的距离违背欧式空间中的三角不等式，亦即一个三角形的两条边的线段长度和大于第三条边的线段长度。这项工作揭示了研究特征交互需要考虑几何意义，我们的工作也沿用了这一思想。

与Hsieh的角度不同，我们利用了双曲几何当中的洛伦兹距离可以违背三角不等式的特殊性质。具体来说，我们利用双曲空间中的A和B两点与原点形成的三角形是否违背三角不等式来构造A和B两点间特征交互。

这样做的好处有两个：一是双曲空间的表达能力强于欧式空间；二是这样构造的特征交互可以学习到精细的相互作用结构，能直接用于计算最终分数，无须叠加神经网络。实验结果证明，我们的模型不仅可以得到超越深度学习的准确率，还可以降低 80%左右 的模型参数和 70%左右 的训练时间。

二、三角不等式的意义

首先来补充一点数学背景知识。双曲几何是旨在研究具有恒定负曲率的非欧几里得空间。让我们来定义一下双曲空间上的洛伦兹内积，即对于两点u，v , 有：

由于其负曲率，双曲几何与欧几里得几何相比，具有非常不同的性质。首先，在双曲空间中，圆的周长和面积随半径的增长而指数级增长；而在欧几里得空间中，圆的周长和面积的增长速度与线性和二次函数的增长速度相反。因此，在双曲空间中，半径相同的上界值在双曲空间中嵌入的容量要比欧几里得空间中的大得多。其次，三角不等式与上述定义的洛伦兹距离的三角不等式可以被违反。这个特性使我们能够用不等式的符号来描述双曲空间中各点之间的关系。

正如Hsieh等人(2017)提出的 协同 度量学习 (collaborative metric learning)，学习嵌入空间中的距离而不是内积，有利于得到一个精细化的嵌入空间，它不仅可以捕捉到商品-用户交互的表示，而且可以捕捉到商品-商品和用户-用户距离的表示。从本质上说，所谓的协同度量学习受惠于三角不等式的约束，从而有更好的几何表达。与协同度量学习的方法相比，我们认为，两点之间的特征交互可以通过洛伦兹距离的三角形不等式的符号来学习，而不是使用距离本身。从形式上看，我们的目标函数可以写成：

其中0=（1，0，…，0），是双曲空间的原点。在上面的公式中，分子可以理解为x和y与原点构成的三角形的三角不等式，而分母用于标度目标函数，使得目标函数的区间被限制在 -0.5 到 2 之间，如图2所示。目标函数标度之后的另一个好处是，它可以避免维度灾难。因此我们并不需要对其调节正则项。

图2: 当特征维度为2时，用标度后的三角不等式与协同度量学习的目标函数在双曲空间的区别

三、模型的细节和训练

本章我们将展示如何利用前一章中所提及的数学 工具 来构造洛伦兹因子分解机（LorentzFM)。和绝大多数的模型类似，我们的目标是将原始稀疏特征映射到低维空间，但模型架构将更加简单，如图3所示。模型可以分解为以下两个部分：

洛伦兹嵌入层

三角池化层

图3：洛伦兹因子分解机的结构

（点击可查看大图）

输入端的稀疏特征进入模型之后，会首先通过洛伦兹嵌入层得到其在双曲空间的表征。这些表征是定义在洛伦兹度规下的向量。之后，这些向量会通过我们在上一章介绍的标度三角不等式计算一个标量。最后，我们对所有的特征得到的标量求和得到模型的输出分数：

这个分数可以理解为，每一个特征分量之间总体违背三角不等式的程度。它的几何意义与距离或者余弦相似度有本质不同。双曲几何中的三角不等式与洛伦兹流形的因果律有关，这里我们就不详细展开了，有兴趣的同学可以参考文末的参考文献 [2] 深入阅读。

对于推荐系统而言，我们实际收集到的数据往往只有正样本，所以需要对每一个正样本做充分的负采样。对于点击率预测来说，展示给用户的广告被点击与否可以看作正负样本的标签。无论哪种情况，我们都可以利用交叉熵作为目标函数：

其中 是第i个样本的为正样本的概率， ，而 是真实的标签。模型的参数 是通过黎曼随机梯度下降 [3] 进行优化的。

四、实验

为了证明LorentzFM的表现，我们在四个真实数据上做了实验。他们分别是 MovieLens , KKBox ， Steam 和 Avazu ，其中前三个数据集是推荐系统的数据，而Avazu是广告点击率预测的数据。对于推荐系统的数据，我们对每个训练正样本进行负采样，并且用MRR，HR@10和NDCG作为指标。对于点击率预测数据，我们使用ROC曲线的AUC和Logloss作为指标。

我们对比的基线方法包括：FM [4] ，NFM [5] ，DeepFM [6] ，xDeepFM [7] 和DCN [8] 。其中最后四种都是基于FM层之上的深度神经网络。最终得到的对比实验结果如表1所示：

表1：对维度为10的对比实验

（点击可查看大图）

可以看到，除了MovieLens，LorentzFM都得到了最优的实验结果。

图4：在测试集上不同的模型随着特征维度增加的变化

（点击可查看大图）

之前我们也提到，LorentzFM可以避免维度灾难，不需要调正则化系数。在图4中，我们对比了在Steam数据集上逐渐增加特征的维度所得到的模型表现。 可以看到，LorentzFM是随着特征维度的增加逐渐变得更好的， 但是对于其他模型来说，增加特征维度提高的空间不大，甚至有可能造成反作用。

另外需要注意的是，LorentzFM不使用任何深度神经网络。因此，我们比较了每个模型在表1中得到最优表现时模型的参数和训练时间，其结果归纳在表2当中。

表2：不同模型的训练参数和训练时间

（点击可查看大图）

可以看到，LorentzFM在达到可观的实验表现的同时，所需要的训练参数和训练时间和基于深度神经网络的方法相比都大为减少。

五、总结

我们提出的洛伦兹因子分解机模型是一种有效的轻量级模型，它的几何意义是双曲空间当中的三角不等式。通过运用这个模型，可以极大地提高推荐系统和点击率预测的表现，同时降低模型参数和训练时间。

参考文献

[1] Hsieh, C.; Yang, L.; Cui, Y.; Lin, T.; Belongie, S. J.; and Es-trin, D. Collaborative metric learning. In Proceedings of the 26th International Conference on World Wide Web,WWW 2017, 193–201.

[2] Gallaway, G. Notes on Lorentzian causality.

[3] Nickel, M., and Kiela, D.  Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, 3776–3785.

[4] Rendle, S.  2010.  Factorization machines.  In ICDM 2010,The 10th IEEE International Conference on Data Mining,2010, 995–1000.

[5] He, X., and Chua, T.  2017.  Neural factorization machines for sparse predictive analytics.  InProceedings of the 40thInternational ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2017, 355–364.

[6] Guo, H.; Tang, R.; Ye, Y.; Li, Z.; and He, X. Deepfm:A factorization-machine based neural network for CTR prediction. InProceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI 2017, 1725–1731.

[7] Lian, J.; Zhou, X.; Zhang, F.; Chen, Z.; Xie, X.; and Sun,G.  xdeepfm: Combining explicit and implicit feature interactions for recommender systems.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowl-edge Discovery & Data Mining, KDD 2018, 1754–1763.

[8] Wang, R.; Fu, B.; Fu, G.; and Wang, M. Deep & cross network for ad click predictions. In Proceedings of the ADKDD’17, 12:1–12:7.