Kernel-CF：推荐系统的最优召回策略

推荐系统自诞生以来广受关注，尤其是互联网领域，推荐系统已经成为了给企业下金蛋的白鹅。我们来算一笔账，假设我们公司推荐产品的日 PV 是500 万，推荐系统让用户点击率提升了1%, 也就是一天增加了5 万 PV。Google Ads 的CPC 均价是2 美元。这样算来，推荐系统每天给该网站节省了10 万美元的获客费用，一年下来就是3650 万美元。这真的是一笔非常庞大的数字，可见大型网站/ App 对推荐系统趋之若鹜是有原因的。

推荐系统自引入国内之后，许多工程师喜欢把推荐系统划分为召回-排序等阶段。其实所谓的召回，指的就是利用算法或规则先给执行推荐算法的数据筛选出一个子集合，然后再进入算法执行的下一个阶段。作者在互联网大厂的时候，曾经先用协同过滤做召回，然后用排序学习（Bayesian Personalized Ranking / Collaborative Less is More Filtering）做排序，取得了不错的结果。

召回的策略千千万，也许有人要问：有没有什么召回策略是最优的？我们有没有办法通过最优化理论计算出最优的召回策略？答案是肯定的。Ratidar Technologies LLC 在国际学术会议 CAIBDA 2022 上宣读了一篇题为Kernel-CF: Collaborative filtering done right with social network analysis and kernel smoothing 的论文，介绍了如何利用数据可视化算法和非参数统计方法计算推荐系统最优召回策略。我们下面详细的介绍相关内容：

首先，我们介绍一下什么是 ForceAtlas-2 算法。ForceAtlas-2 发表于 PLoS 的2014 年的论文。论文题目是ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software. 这篇论文讲述了如何借用物理学中的概念，实现对于复杂网络的可视化。相关算法已经集成在了常用的社交网络分析软件Gephi 中。

ForceAtlas-2 认为一个社交网络中，点与点之间的相互作用有两种：吸引力和排斥力。其中吸引力定义如下：

而排斥力定义如下：

其中 d 是距离函数，而deg 是视图中节点的度。通过观察，我们得知，距离越近，吸引力越小；距离越远，吸引力越大。节点的度越大，排斥力越大；节点之间的距离越远，排斥力越小。ForceAtlas-2 通过在社交网络中模拟这两种力的相互作用，把复杂的社交网络在二维空间简单漂亮的展现了出来。

下面我们进入正题。我们来讨论怎样给协同过滤算法设计最优召回策略。我们这里拿基于用户的协同过滤做例子。基于物品的协同过滤算法模型的分析与此类似。基于用户的协同过滤算法的公式如下：

基于用户的协同过滤的基本思想是根据与用户相似的用户的喜好列表给当前用户推荐他所没有见过的物品。这里面存在一个问题：我们该选择哪些与用户相似的用户进行计算？是所有用户吗？还是有个最优的召回策略？这就是 Kernel-CF 算法将要讨论的问题。Kernel-CF 算法的论文下载地址在这里：https://arxiv.org/ftp/arxiv/papers/2303/2303.04561.pdf 。下面我们针对这个算法展开介绍。

我们首先计算出所用用户对之间的相似性，然后把相似矩阵转换为距离矩阵，利用ForceAtlas-2 将距离矩阵映射到二维空间。我们发现，在新的社交网络中，基于用户的协同过滤其实就是非参数统计学中的 Nadaraya-Watson 核回归问题，而我们要做的就是计算最优核半径。而这是一个学者已经通过 plug-in 方法解决了的问题。在一维Nadaraya-Watson 核回归中，最优核半径的计算方法如下：

现在我们考虑二维的情况（我们有X 轴和 Y 轴两个方向上的变量）：

其中：

我们看到，我们利用 plug-in 方法，完美的解决了协同过滤中的最优召回问题。下图是一张基于 ForceAtlas-2 降维之后的协同过滤输入数据（LDOS-CoMoDa 数据集）的部分展示，可以看到最优召回策略可以节省大量的计算资源：

现在还剩下一个问题，那就是在上述利用 Plug-in 方法求解协同过滤算法最优召回的过程中存在着一些未知量，需要通过统计的方式进行近似，比如r 和 f。r 函数的定义如下：

r 可以通过一般形式的最小二乘法进行近似。我们做了如下假定：

我们定义f 为数据造成的概率分布。我们通过概率密度估计来估计f :

其中 H 通过如下方式进行估计：

其中 是协方差矩阵。综合我们在上面讨论的结果，我们得到如下算法流程（伪代码）：

本文详细介绍了如何利用信息可视化和非参数统计方法计算协同过滤中最优召回的问题。算法中虽然公式推导复杂，但是整体流程可实现性较强。一旦读者熟悉了文章中算法的细节，就能很好的完成算法的实现工作。这个算法的名字叫做 Kernel-CF，一方面是因为利用了核回归的知识，另外一方面是因为问题解决对象是协同过滤。

Kernel-CF 算法告诉我们在解决实际的机器学习问题中，应该集思广益，博览群书，充分利用其他领域的学科知识，就可以综合起来解决推荐系统中的老大难问题。非参数统计是统计学专业高年级学生或者统计学研究生所学的内容。作为算法工程师，相关的知识平日里可能接触不到，但是这不妨碍我们经常去图书馆借阅（中国国家图书馆有数百万持卡用户）或者购买书籍阅读。扎实的数学功底，能够给我们的算法工作插上腾飞的翅膀，翻越一座又一座的高山峻岭。

作者简介

汪昊，前 Funplus 人工智能实验室负责人/创业公司CTO。曾在 ThoughtWorks、豆瓣、百度、新浪等公司担任技术和技术高管职务。在互联网公司和金融科技、游戏等公司任职 13 年，对于人工智能、计算机图形学和区块链等领域有着深刻的见解和丰富的经验。在国际学术会议和期刊发表论文 42 篇，获得IEEE SMI 2008 最佳论文奖、ICBDT 2020 / IEEE ICISCAE 2021 / AIBT 2023 / ICSIM 2024最佳论文报告奖。