WWW 2020 | 内存压缩两个量级!中国科大与微软联合推出轻量高效推荐系统

2020-04-27 | 作者:连徳富、刘政、练建勋、谢幸

编者按:在推荐模型的计算和存储开销都越来越大的今天,我们如何构筑轻量级推荐系统来使搜索变得更高效呢?中国科学技术大学青年教师、铸星学者连德富老师在微软亚洲研究院访问期间,与社会计算组研究员们合作探索了针对內积函数设计神经网络的方法,来实现轻量而高效的推荐系统。该研究成果发表在了 WWW 2020上。


随着深度学习的发展,推荐模型的计算和存储开销越来越大。在实际推荐场景中,物品数量巨大,复杂的推荐模型难以实现即时推荐。为此,实际推荐系统一般分为两个阶段:一个是搜索效率高的召回阶段,一个是推荐精度高的精排阶段。召回阶段利用近似搜索算法快速找出候选物品,精排阶段利用复杂模型对候选物品进行精准排序。

然而,近似搜索算法一般基于欧式距离,不同于复杂推荐算法常用的排序函数,比如內积、余弦相似度等,可能会导致推荐准确度受较大影响。此外,对推荐算法的分析发现,用户和物品的表示向量占据模型参数的很大部分,从而,对表示向量的压缩也能实现推荐模型的大幅压缩。

围绕这两个方面的问题,下面来介绍针对內积函数设计神经网络来实现轻量级的推荐系统。

主要思想

本研究的主要思想是用多个有限向量集合来组合表示物品,与传统的向量量化研究类似。具体而言,如图1所示,假设有 D 个不同的向量集合(D=4),每个集合称为码书,每个集合中有 K 个向量(K=4),每个向量成为码字。在为每个物品从每个集合中找到最相似的向量之后,再将这 D 个最相似的向量组合表示物品。在存储时,只需要存储这些向量的索引,比如图中的物品 i_1,D 个码书中向量索引分别为3,2,1,0,这些索引只需要一个比特的整数,这便使得物品向量表示的存储空间可以大量压缩。

具体而言, 每个物品在每个集合的 K 个向量中最相似的向量索引只需要用 log(K) 比特来存储,那么每个物品最终只需要 Dlog(K) 比特存储,相比于 p 维实数向量表示需要的 32p 比特要少很多(D 远小于 p)。通过这种组合式表达,我们发现物品的存储空间可以减少96%以上。在计算用户对物品的得分时,预先计算好用户对每个码书中所有码字的得分,然后通过查表的方式找出与物品最相似的码字的得分,将 D 个码字得分求和后即为用户对物品的得分。因此,用户对物品的得分计算可以被显著加速。

图1:搜索和存储效率的示意图

主要挑战

要实现这种轻量级的组合向量表示,简单而直接的方法是两阶段法,即先学习物品的表示向量,然后再利用乘积量化或者加性量化获得组合表示。因为该研究针对內积函数来学习表示向量。向量內积不满足非负、三角不等式等特性,并非是距离度量,与乘积量化或者加性量化基于的欧式距离不同,从而导致这种方式获得的向量组合表示可能不适合用于针对向量內积的高效推荐。

为此,本研究的目标是设计端到端的优化学习算法。算法设计面临三个重要挑战。第一,如何利用神经网络表达可微的码字选择操作;第二,如何实现码书的多样化;第三,如何设计合适的优化目标。

提出方案

可微码字选择

在主要思想部分,我们介绍到要为每个物品在每个码书中选择最相似的码字。那么,首先需要定义相似度。由于不再基于距离度量,相似度用神经网络函数来表示,比如可以是內积、双线性函数等。给定物品向量和码字,该神经网络输入它们间的相似度,在每个码书中找到最相似码字对应最大化操作。由于最大化操作并不可微,便可以通过带温度的 softmax 函数来近似[5]。当温度趋于0时,便对应了最大化操作。为此,我们可以在前向计算时利用最大化操作,而反向传播时便用 softmax,从而实现码字的可微选择。具体如图2所示。

多样化码书

如果 D 个不同码书的差异性很小,用多个码书来组合表示物品就意义不大。考虑极端情况,如果 D 个码书是完全一样的,那么物品从 D 个码书中选择出来的最相似码字是一样的,从而导致用 D 个最相似码字来组合表示物品向量与其中任意一个最相似码字来表示并无不同。为了实现多样化的码书学习,我们提出了循环残差量化的学习方法。特别地,每次利用残差向量从码书中选择最相似码字。比如,在第一次用物品向量自身;第二次用物品向量减去第一次选择的码字;第 t 次用物品向量减去前 t-1 次选择的码字和。具体如图2所示。

图2:框架图

优化目标

我们通过循环残差量化模块实现物品向量的组合向量表示。结合用户向量和物品的组合向量表示的內积便可以预测用户对物品的偏好得分估计。基于预测得分,可以通过优化推荐系统的损失函数来实现码书和相似性函数的端到端学习。不过只基于推荐系统目标函数[6]来学习是困难的,因为物品向量很难学习好。当物品向量质量很低的时候,码书的选择可能会出错,导致码书的学习出现问题。为此,我们提出了三种蒸馏损失。第一,保证物品向量在量化前后不能差别太大;第二,保证用户对物品的偏好得分估计在量化前后不能差别太大;第三,保证用户推荐列表的顺序不能有很大变动。

实验分析

我们在 CiteULike、Gowalla、Amazon、MovieLens 10M 四个数据集上进行了验证,实验证明我们提出的算法显著优于乘积量化 OPQ[2]、残差量化 RVQ[3] 等二阶段法和 DCMF[4] 算法、KDE[5] 算法等直接学习法。在没有精排的情况下,NDCG 的平均精度损失不超过4%,而在精排情况下,NDCG 精度损失几乎可以忽略不计。物品向量在量化前后的存储开销比值(压缩比)高达25。在保证精度损失可以忽略的情况下,精确推荐的加速比高达25以上。

图3:和基准算法的对比

图4:压缩比和加速比和精度损失关系

结语

本文针对內积提出了面向高效推荐的轻量级推荐系统设计,其有效性通过四个推荐数据集进行了验证。该方案尚处于初步阶段,第一,循环残差量化的计算效率较低,肯定存在其他生成多样化码书的高效方法;第二,提出排序蒸馏损失的作用非常有限,但是保序(特别是 topk 推荐的保序)对于推荐系统来说是非常重要的;第三,目前方案主要针对內积设计,针对一般的神经网络函数进行设计也是重要的研究方向。

更多细节可参考论文:http://staff.ustc.edu.cn/~liandefu/paper/lightrec.pdf

参考文献

[1] Defu Lian, Haoyu Wang, Zheng Liu, Jianxun Lian, Enhong Chen and Xing Xie. LightRec: a Memory and Search-Efficient Recommender System. The 29th Web Conference (WWW 2020), Taipei, China, April, 2020

[2] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized product quantization. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, 4 (2014), 744–755.

[3] Yongjian Chen, Tao Guan, and ChengWang. 2010. Approximate nearest neighbor search by residual vector quantization. Sensors 10, 12 (2010), 11259–11273.

[4] Defu Lian, Xing Xie, and Enhong Chen. 2019. Discrete Matrix Factorization and Extension for Fast Item Recommendation. IEEE Transactions on Knowledge and Data Engineering (2019). https://doi.org/10.1109/TKDE.2019.2951386

[5] Ting Chen, Martin Renqiang Min, and Yizhou Sun. 2018. Learning K-way D-dimensional Discrete Codes for Compact Embedding Representations. In International Conference on Machine Learning. 853–862.

[6] Defu Lian, Qi Liu, Enhong Chen. Personalized Ranking with Importance Sampling. The 29th Web Conference (WWW 2020), Taipei, China, April, 2020