重磅！协同过滤算法被证明存无通常失误！

介绍系统算法能够给公司带来渺小的流量，并且大幅度的缩小营销费用。环球上最早的介绍系统来自施乐公司，David Goldberg 等人在 1992 年发明了基于用户的协同过滤算法。几年之后，又有人发明了基于东西的协同过滤算法。在 21 世纪初期，矩阵合成算法被发明以前，协同过滤算法不时在介绍系统畛域占据着主导位置。时至今天，协同过滤算法依然被许多公司用作介绍系统的 baseline 算法，广为盛行。

但是在 2024 年 5 月举办的 CCCE 国内学术会议上，钻研人员宣布了一篇题为 Collaborative Filtering is Wrong and Here is Why 的论文，指出协同过滤算法存无通常失误，因此是失误的算法。本文带读者一探这篇文章的终究，宿愿对大家日后的技术上班有所协助。

作者首先计算出协同过滤算法中用户-用户对之间的相似性，而后转换为距离，应用保距离算法将高维空间的用户向量（由用户给东西的打分形成）降维至 2 维平面。而后证明了上方 2 个引理：

引理1 ：一切的用户向量散布在半径为 1 的圆圈内

证明：给定一个用户向量用户 i，协同过滤算法自动相似性取值在 [0.0, 1.0] 范围内，转换为距离之后距离数值取值依然在 [0.0, 1.0] 范围内，也就是说，一切的用户向量都在以用户 i 位置中心，半径为 1.0 的圆圈内。

引理2 ：一切的用户向量等价于半径为 0.5 的圆圈

证明：首先，用户向量汇合中最大的距离是 1.0，因此一切的用户向量都散布在半径为 0.5 的圆内。其次，每个用户都有距离为1.0 的向量，因此，假设用户向量在圆的外部，和它距离为 1.0 的点将只能存在于圆的外部， 矛盾。而每个用户在定义域内都有与它距离在 0 和 1 之间的一切点，因此用户向量和半径为 0.5 的圆圈是逐一对应的相关。

上方咱们引见一个关键的拓扑学定理：Poincare-Hopf 度数定理：

在一个紧致、有向的流形上定义的向量场的奇点的度等于流形的欧拉示性数。

二维平面中半径为 0.5 的圆圈是一个紧致、有向的流形。咱们如今在这个降维之后的用户向量定义域上结构一个向量场：假定有 N 个用户，那么在每一个用户 i 上，定义 N-1 个向量（sim(i,j)-C, sim(i,j)-C），其中 j 为 N-1 个用户中的恣意用户，C 为给定常数。咱们发现这些向量都与直线 y = x 平行，因此除非 C= 0.0 或许 C=1.0，咱们都可以把向量场中的零点构形成鞍点。依据 Poincare-Hopf 度数定理，这个向量场中零点的个数，不论 C 取什么值，只和圆圈的欧拉示性数有关。换言之，介绍系统定义域中，相似度等于某个常数的用户对的个数，只和圆圈的欧拉示性数有关，这显然在事实环球中是不成立的。

由于协同过滤的数据有关性，造成了协同过滤实用于各个不同的场景。但是，正由于协同过滤的数据有关性，才说明了它是一个失误的算法。

CCCE 的这篇论文从通常上颠覆了协同过滤算法，给了介绍系统的通常基础繁重的一击。宿愿本文能给读者带来对相关畛域不一样的思索：除了拼命的优化算法的效果，咱们还应该仔细思索算法的通常基础。

汪昊，前达评奇智董事长兼开创人。在 ThoughtWorks、豆瓣、百度和趣加等公司有超越 13 年的技术和技术治理阅历。成功上线过包含豆瓣小组介绍、豆瓣机器学习算法库、联想电商介绍、网易段子、趣加游戏礼包介绍等10余款科技产品。在国内学术会议和期刊宣布论文 44 篇，取得最佳论文奖 1次（IEEE SMI 2008）、最佳论文报告奖4次（ICBDT 2020、IEEE ICISCAE 2021、AIBT 2023、ICSIM 2024）。2006 年ACM/ICPC 北美落基山区域赛金牌。