譯者 | 汪昊
審校 | 重樓
推薦系統(tǒng)算法能夠給公司帶來(lái)巨大的流量，并且大幅度的減少營(yíng)銷費(fèi)用。世界上最早的推薦系統(tǒng)來(lái)自施樂(lè)公司，David Goldberg 等人在 1992 年發(fā)明了基于用戶的協(xié)同過(guò)濾算法。幾年之后，又有人發(fā)明了基于物品的協(xié)同過(guò)濾算法。在 21 世紀(jì)初期，矩陣分解算法被發(fā)明以前，協(xié)同過(guò)濾算法一直在推薦系統(tǒng)領(lǐng)域占據(jù)著主導(dǎo)地位。時(shí)至今日，協(xié)同過(guò)濾算法仍然被許多公司用作推薦系統(tǒng)的 baseline 算法，廣為流行。
然而在 2024 年 5 月舉行的 CCCE 國(guó)際學(xué)術(shù)會(huì)議上，研究人員發(fā)表了一篇題為 Collaborative Filtering is Wrong and Here is Why 的論文，指出協(xié)同過(guò)濾算法存在理論錯(cuò)誤，因此是錯(cuò)誤的算法。本文帶讀者一探這篇文章的究竟，希望對(duì)大家日后的技術(shù)工作有所幫助。
作者首先計(jì)算出協(xié)同過(guò)濾算法中用戶-用戶對(duì)之間的相似性，然后轉(zhuǎn)換為距離，利用保距離算法將高維空間的用戶向量（由用戶給物品的打分構(gòu)成）降維至 2 維平面。然后證明了下面 2 個(gè)引理：
引理1 ：所有的用戶向量分布在半徑為 1 的圓圈內(nèi)
證明：給定一個(gè)用戶向量用戶 i，協(xié)同過(guò)濾算法默認(rèn)相似性取值在 [0.0, 1.0] 范圍內(nèi)，轉(zhuǎn)換為距離之后距離數(shù)值取值仍然在 [0.0, 1.0] 范圍內(nèi)，也就是說(shuō)，所有的用戶向量都在以用戶 i 位置中心，半徑為 1.0 的圓圈內(nèi)。
引理2 ：所有的用戶向量等價(jià)于半徑為 0.5 的圓圈
證明：首先，用戶向量集合中最大的距離是 1.0，因此所有的用戶向量都分布在半徑為 0.5 的圓內(nèi)。其次，每個(gè)用戶都有距離為1.0 的向量，因此，如果用戶向量在圓的內(nèi)部，和它距離為 1.0 的點(diǎn)將只能存在于圓的外部，出現(xiàn)矛盾。而每個(gè)用戶在定義域內(nèi)都有與它距離在 0 和 1 之間的所有點(diǎn)，因此用戶向量和半徑為 0.5 的圓圈是一一對(duì)應(yīng)的關(guān)系。
下面我們介紹一個(gè)重要的拓?fù)鋵W(xué)定理：Poincare-Hopf 度數(shù)定理：
Poincare-Hopf 度數(shù)定理：在一個(gè)緊致、有向的流形上定義的向量場(chǎng)的奇點(diǎn)的度等于流形的歐拉示性數(shù)。
二維平面中半徑為 0.5 的圓圈是一個(gè)緊致、有向的流形。我們現(xiàn)在在這個(gè)降維之后的用戶向量定義域上構(gòu)造一個(gè)向量場(chǎng)：假設(shè)有 N 個(gè)用戶，那么在每一個(gè)用戶 i 上，定義 N-1 個(gè)向量（sim(i,j)-C, sim(i,j)-C），其中 j 為 N-1 個(gè)用戶中的任意用戶，C 為給定常數(shù)。我們發(fā)現(xiàn)這些向量都與直線 y = x 平行，因此除非 C= 0.0 或者 C=1.0，我們都可以把向量場(chǎng)中的零點(diǎn)構(gòu)造成鞍點(diǎn)。根據(jù) Poincare-Hopf 度數(shù)定理，這個(gè)向量場(chǎng)中零點(diǎn)的個(gè)數(shù)，不論 C 取什么值，只和圓圈的歐拉示性數(shù)有關(guān)。換言之，推薦系統(tǒng)定義域中，相似度等于某個(gè)常數(shù)的用戶對(duì)的個(gè)數(shù)，只和圓圈的歐拉示性數(shù)有關(guān)，這顯然在現(xiàn)實(shí)世界中是不成立的。
因?yàn)閰f(xié)同過(guò)濾的數(shù)據(jù)無(wú)關(guān)性，導(dǎo)致了協(xié)同過(guò)濾適用于各個(gè)不同的場(chǎng)景。然而，正因?yàn)閰f(xié)同過(guò)濾的數(shù)據(jù)無(wú)關(guān)性，才說(shuō)明了它是一個(gè)錯(cuò)誤的算法。
CCCE 的這篇論文從理論上推翻了協(xié)同過(guò)濾算法，給了推薦系統(tǒng)的理論基礎(chǔ)沉重的一擊。希望本文能給讀者帶來(lái)對(duì)相關(guān)領(lǐng)域不一樣的思考：除了拼命的提升算法的效果，我們還應(yīng)該認(rèn)真思考算法的理論基礎(chǔ)。
譯者介紹
汪昊，前達(dá)評(píng)奇智董事長(zhǎng)兼創(chuàng)始人。在 ThoughtWorks、豆瓣、百度和趣加等公司有超過(guò) 13 年的技術(shù)和技術(shù)管理經(jīng)驗(yàn)。成功上線過(guò)包括豆瓣小組推薦、豆瓣機(jī)器學(xué)習(xí)算法庫(kù)、聯(lián)想電商推薦、網(wǎng)易段子、趣加游戲禮包推薦等10余款科技產(chǎn)品。在國(guó)際學(xué)術(shù)會(huì)議和期刊發(fā)表論文 44 篇，獲得最佳論文獎(jiǎng) 1次（IEEE SMI 2008）、最佳論文報(bào)告獎(jiǎng)4次（ICBDT 2020、IEEE ICISCAE 2021、AIBT 2023、ICSIM 2024）。2006 年ACM/ICPC 北美落基山區(qū)域賽金牌。
