譯者 | 汪昊
審校 | 重樓
推薦系統算法能夠給公司帶來巨大的流量，并且大幅度的減少營銷費用。世界上最早的推薦系統來自施樂公司，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 度數定理：
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 北美落基山區域賽金牌。
