作者 | 汪昊
審校 | 重樓
推薦系統(tǒng)自誕生以來廣受關(guān)注，尤其是互聯(lián)網(wǎng)領(lǐng)域，推薦系統(tǒng)已經(jīng)成為了給企業(yè)下金蛋的白鵝。我們來算一筆賬，假設(shè)我們公司推薦產(chǎn)品的日 PV 是500 萬，推薦系統(tǒng)讓用戶點(diǎn)擊率提升了1%, 也就是一天增加了5 萬 PV。Google Ads 的CPC 均價(jià)是2 美元。這樣算來，推薦系統(tǒng)每天給該網(wǎng)站節(jié)省了10 萬美元的獲客費(fèi)用，一年下來就是3650 萬美元。這真的是一筆非常龐大的數(shù)字，可見大型網(wǎng)站/ App 對推薦系統(tǒng)趨之若鶩是有原因的。
推薦系統(tǒng)自引入國內(nèi)之后，許多工程師喜歡把推薦系統(tǒng)劃分為召回-排序等階段。其實(shí)所謂的召回，指的就是利用算法或規(guī)則先給執(zhí)行推薦算法的數(shù)據(jù)篩選出一個(gè)子集合，然后再進(jìn)入算法執(zhí)行的下一個(gè)階段。作者在互聯(lián)網(wǎng)大廠的時(shí)候，曾經(jīng)先用協(xié)同過濾做召回，然后用排序?qū)W習(xí)（Bayesian Personalized Ranking / Collaborative Less is More Filtering）做排序，取得了不錯(cuò)的結(jié)果。
召回的策略千千萬，也許有人要問：有沒有什么召回策略是最優(yōu)的？我們有沒有辦法通過最優(yōu)化理論計(jì)算出最優(yōu)的召回策略？答案是肯定的。Ratidar Technologies LLC 在國際學(xué)術(shù)會議 CAIBDA 2022 上宣讀了一篇題為Kernel-CF: Collaborative filtering done right with social network analysis and kernel smoothing 的論文，介紹了如何利用數(shù)據(jù)可視化算法和非參數(shù)統(tǒng)計(jì)方法計(jì)算推薦系統(tǒng)最優(yōu)召回策略。我們下面詳細(xì)的介紹相關(guān)內(nèi)容：
首先，我們介紹一下什么是 ForceAtlas-2 算法。ForceAtlas-2 發(fā)表于 PLoS 的2014 年的論文。論文題目是ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software. 這篇論文講述了如何借用物理學(xué)中的概念，實(shí)現(xiàn)對于復(fù)雜網(wǎng)絡(luò)的可視化。相關(guān)算法已經(jīng)集成在了常用的社交網(wǎng)絡(luò)分析軟件Gephi 中。
ForceAtlas-2 認(rèn)為一個(gè)社交網(wǎng)絡(luò)中，點(diǎn)與點(diǎn)之間的相互作用有兩種：吸引力和排斥力。其中吸引力定義如下：
而排斥力定義如下：
其中 d 是距離函數(shù)，而deg 是視圖中節(jié)點(diǎn)的度。通過觀察，我們得知，距離越近，吸引力越小；距離越遠(yuǎn)，吸引力越大。節(jié)點(diǎn)的度越大，排斥力越大；節(jié)點(diǎn)之間的距離越遠(yuǎn)，排斥力越小。ForceAtlas-2 通過在社交網(wǎng)絡(luò)中模擬這兩種力的相互作用，把復(fù)雜的社交網(wǎng)絡(luò)在二維空間簡單漂亮的展現(xiàn)了出來。
下面我們進(jìn)入正題。我們來討論怎樣給協(xié)同過濾算法設(shè)計(jì)最優(yōu)召回策略。我們這里拿基于用戶的協(xié)同過濾做例子。基于物品的協(xié)同過濾算法模型的分析與此類似。基于用戶的協(xié)同過濾算法的公式如下：
基于用戶的協(xié)同過濾的基本思想是根據(jù)與用戶相似的用戶的喜好列表給當(dāng)前用戶推薦他所沒有見過的物品。這里面存在一個(gè)問題：我們該選擇哪些與用戶相似的用戶進(jìn)行計(jì)算？是所有用戶嗎？還是有個(gè)最優(yōu)的召回策略？這就是 Kernel-CF 算法將要討論的問題。Kernel-CF 算法的論文下載地址在這里：https://arxiv.org/ftp/arxiv/papers/2303/2303.04561.pdf 。下面我們針對這個(gè)算法展開介紹。
我們首先計(jì)算出所用用戶對之間的相似性，然后把相似矩陣轉(zhuǎn)換為距離矩陣，利用ForceAtlas-2 將距離矩陣映射到二維空間。我們發(fā)現(xiàn)，在新的社交網(wǎng)絡(luò)中，基于用戶的協(xié)同過濾其實(shí)就是非參數(shù)統(tǒng)計(jì)學(xué)中的 Nadaraya-Watson 核回歸問題，而我們要做的就是計(jì)算最優(yōu)核半徑。而這是一個(gè)學(xué)者已經(jīng)通過 plug-in 方法解決了的問題。在一維Nadaraya-Watson 核回歸中，最優(yōu)核半徑的計(jì)算方法如下：
現(xiàn)在我們考慮二維的情況（我們有X 軸和 Y 軸兩個(gè)方向上的變量）：
其中：
我們看到，我們利用 plug-in 方法，完美的解決了協(xié)同過濾中的最優(yōu)召回問題。下圖是一張基于 ForceAtlas-2 降維之后的協(xié)同過濾輸入數(shù)據(jù)（LDOS-CoMoDa 數(shù)據(jù)集）的部分展示，可以看到最優(yōu)召回策略可以節(jié)省大量的計(jì)算資源：
現(xiàn)在還剩下一個(gè)問題，那就是在上述利用 Plug-in 方法求解協(xié)同過濾算法最優(yōu)召回的過程中存在著一些未知量，需要通過統(tǒng)計(jì)的方式進(jìn)行近似，比如r 和 f。r 函數(shù)的定義如下：
r 可以通過一般形式的最小二乘法進(jìn)行近似。我們做了如下假定：
我們定義f 為數(shù)據(jù)造成的概率分布。我們通過概率密度估計(jì)來估計(jì)f :
其中 H 通過如下方式進(jìn)行估計(jì)：
其中
是協(xié)方差矩陣。綜合我們在上面討論的結(jié)果，我們得到如下算法流程（偽代碼）：
本文詳細(xì)介紹了如何利用信息可視化和非參數(shù)統(tǒng)計(jì)方法計(jì)算協(xié)同過濾中最優(yōu)召回的問題。算法中雖然公式推導(dǎo)復(fù)雜，但是整體流程可實(shí)現(xiàn)性較強(qiáng)。一旦讀者熟悉了文章中算法的細(xì)節(jié)，就能很好的完成算法的實(shí)現(xiàn)工作。這個(gè)算法的名字叫做 Kernel-CF，一方面是因?yàn)槔昧撕嘶貧w的知識，另外一方面是因?yàn)閱栴}解決對象是協(xié)同過濾。
Kernel-CF 算法告訴我們在解決實(shí)際的機(jī)器學(xué)習(xí)問題中，應(yīng)該集思廣益，博覽群書，充分利用其他領(lǐng)域的學(xué)科知識，就可以綜合起來解決推薦系統(tǒng)中的老大難問題。非參數(shù)統(tǒng)計(jì)是統(tǒng)計(jì)學(xué)專業(yè)高年級學(xué)生或者統(tǒng)計(jì)學(xué)研究生所學(xué)的內(nèi)容。作為算法工程師，相關(guān)的知識平日里可能接觸不到，但是這不妨礙我們經(jīng)常去圖書館借閱（中國國家圖書館有數(shù)百萬持卡用戶）或者購買書籍閱讀。扎實(shí)的數(shù)學(xué)功底，能夠給我們的算法工作插上騰飛的翅膀，翻越一座又一座的高山峻嶺。
作者簡介
汪昊，前 Funplus 人工智能實(shí)驗(yàn)室負(fù)責(zé)人/創(chuàng)業(yè)公司CTO。曾在 ThoughtWorks、豆瓣、百度、新浪等公司擔(dān)任技術(shù)和技術(shù)高管職務(wù)。在互聯(lián)網(wǎng)公司和金融科技、游戲等公司任職 13 年，對于人工智能、計(jì)算機(jī)圖形學(xué)和區(qū)塊鏈等領(lǐng)域有著深刻的見解和豐富的經(jīng)驗(yàn)。在國際學(xué)術(shù)會議和期刊發(fā)表論文 42 篇，獲得IEEE SMI 2008 最佳論文獎(jiǎng)、ICBDT 2020 / IEEE ICISCAE 2021 / AIBT 2023 / ICSIM 2024最佳論文報(bào)告獎(jiǎng)。
