在 2023 年結(jié)束的國(guó)際學(xué)術(shù)會(huì)議 AIBT 2023 上，Ratidar Technologies LLC 宣讀了一篇基于公平性的排序?qū)W習(xí)算法，并且獲得了該會(huì)議的最佳論文報(bào)告獎(jiǎng)。該算法的名字是斯奇拉姆排序 (Skellam Rank)，充分利用了統(tǒng)計(jì)學(xué)中的原理，結(jié)合 Pairwise Ranking 和矩陣分解，同時(shí)解決了推薦系統(tǒng)中的準(zhǔn)確率和公平性的問題。因?yàn)橥扑]系統(tǒng)中的排序?qū)W習(xí)的原創(chuàng)算法很少，外加斯奇拉姆排序算法性能優(yōu)異，因此在會(huì)議上獲得了研究獎(jiǎng)項(xiàng)。下面我們來介紹斯奇拉姆算法的基本原理：

我們首先回憶一下泊松分布：

泊松分布的參數(shù)  的計(jì)算公式如下：

兩個(gè)泊松變量的差值是斯奇拉姆分布：

在公式中，我們有：

函數(shù)  叫做第一類貝塞爾函數(shù)。

有了這些最基本的統(tǒng)計(jì)學(xué)中的概念，下面讓我們來構(gòu)建一個(gè) Pairwise Ranking 的排序?qū)W習(xí)推薦系統(tǒng)吧！

我們首先認(rèn)為用戶給物品的打分是個(gè)泊松分布的概念。也就是說，用戶物品評(píng)分值服從以下概率分布：

之所以我們可以把用戶給物品打分的過程描述為泊松過程，是因?yàn)橛脩粑锲吩u(píng)分存在馬太效應(yīng)，也就是說評(píng)分越高的用戶，打分的人越多，以至于我們可以用某個(gè)物品的評(píng)分的人的數(shù)量來近似該物品的評(píng)分的分布。給某個(gè)物品打分的人數(shù)服從什么隨機(jī)過程呢？自然而然的，我們就會(huì)想到泊松過程。因?yàn)橛脩艚o物品打分的概率和該物品有多少人打分的概率相近，我們自然也就可以用泊松過程來近似用戶給物品打分的這一過程了。

我們下面把泊松過程的參數(shù)用樣本數(shù)據(jù)的統(tǒng)計(jì)量替代，得到下面的公式：

我們下面定義 Pariwise Ranking 的最大似然函數(shù)公式。眾所周知，所謂 Pairwise Ranking 指的是我們利用最大似然函數(shù)求解模型參數(shù)，使得模型能夠最大程度保持?jǐn)?shù)據(jù)樣本中已知的排序?qū)Φ年P(guān)系：

因?yàn)楣街械?R 是泊松分布，所以它們的差值，就是斯奇拉姆分布，也就是說：

其中變量 E 是按照如下方式定義的：

我們把斯奇拉姆分布的公式帶入最大似然函數(shù)的損失函數(shù) L ，得到了如下公式：

在變量 E 中出現(xiàn)的用戶評(píng)分值 R ，我們利用矩陣分解的方式進(jìn)行求解。將矩陣分解中的參數(shù)用戶特征向量 U 和物品特征向量 V 作為待求解變量：

這里我們先回顧一下矩陣分解的概念。矩陣分解的概念是在 2010 年左右的時(shí)候提出的推薦系統(tǒng)算法，該算法可以說是歷史上最成功的推薦系統(tǒng)算法之一。時(shí)至今日，仍然有大量的推薦系統(tǒng)公司利用矩陣分解算法作為線上系統(tǒng)的 baseline，而時(shí)下大熱的經(jīng)典推薦算法 DeepFM 中的重要組件 Factorization Machine，也是推薦系統(tǒng)算法中的矩陣分解算法后續(xù)的改進(jìn)版本，和矩陣分解有千絲萬縷的聯(lián)系。矩陣分解算法有個(gè)里程碑論文，是 2007 年的 Probabilistic Matrix Factorization，作者利用統(tǒng)計(jì)學(xué)習(xí)模型對(duì)矩陣分解這個(gè)線性代數(shù)中的概念重新建模，使得矩陣分解第一次有了扎實(shí)的數(shù)學(xué)理論基礎(chǔ)。

矩陣分解的基本概念，是利用向量的點(diǎn)乘，在對(duì)用戶評(píng)分矩陣進(jìn)行降維的同時(shí)高效的預(yù)測(cè)未知的用戶評(píng)分。矩陣分解的損失函數(shù)如下：

矩陣分解算法有許多的變種，比如上海交大提出的 SVDFeature，把向量 U 和 V 用線性組合的形式進(jìn)行建模，使得矩陣分解的問題變成了特征工程的問題。SVDFeature 也是矩陣分解領(lǐng)域的里程碑論文。矩陣分解可以被應(yīng)用在 Pairwise Ranking 中用以取代未知的用戶評(píng)分，從而達(dá)到建模的目的，經(jīng)典的應(yīng)用案例包括 Bayesian Pairwise Ranking 中的 BPR-MF 算法，而斯奇拉姆排序算法就是借鑒了同樣的思路。

我們用隨機(jī)梯度下降對(duì)斯奇拉姆排序算法進(jìn)行求解。因?yàn)殡S機(jī)梯度下降在求解過程中，可以對(duì)損失函數(shù)進(jìn)行大量的簡(jiǎn)化從而達(dá)到求解的目的，我們的損失函數(shù)變成了下面的公式：

利用隨機(jī)梯度下降對(duì)未知參數(shù) U 和 V 進(jìn)行求解，我們得到了迭代公式如下：

其中：

另外有：

其中：

對(duì)于未知參數(shù)變量 V 的求解類似，我們有如下公式：

其中：

另外有：

其中：

整個(gè)算法的流程，我們用如下的偽代碼進(jìn)行展示：

為了驗(yàn)證算法的有效性，論文作者在 MovieLens 1 Million Dataset 和 LDOS-CoMoDa Dataset 上進(jìn)行了測(cè)試。第一個(gè)數(shù)據(jù)集包含了 6040 個(gè)用戶和 3706 部電影的評(píng)分，整個(gè)評(píng)分?jǐn)?shù)據(jù)集大概有 100 萬評(píng)分?jǐn)?shù)據(jù)，是推薦系統(tǒng)領(lǐng)域最知名的評(píng)分?jǐn)?shù)據(jù)集合之一。第二個(gè)數(shù)據(jù)集合來自斯洛文尼亞，是網(wǎng)上不多見的基于場(chǎng)景的推薦系統(tǒng)數(shù)據(jù)集合。該數(shù)據(jù)集合包含了 121 個(gè)用戶和 1232 部電影的評(píng)分。作者將斯奇拉姆排序和另外 9 種推薦系統(tǒng)算法進(jìn)行了對(duì)比，主要測(cè)評(píng)指標(biāo)為 MAE （Mean Absolute Error，用來測(cè)試準(zhǔn)確性）和 Degree of Matthew Effect （主要用來測(cè)試公平性）：

圖 1. MovieLens 1 Million Dataset (MAE 指標(biāo))

圖 2. MovieLens 1 Million Dataset (Degree of Matthew Effect 指標(biāo))

通過圖 1 和圖 2 ，我們發(fā)現(xiàn)斯奇拉姆排序在 MAE 這一項(xiàng)指標(biāo)上表現(xiàn)優(yōu)異，但在 Grid Search 的整個(gè)實(shí)驗(yàn)過程中，無法一直保證性能優(yōu)于其他算法。但是在圖 2 中，我們發(fā)現(xiàn)斯奇拉姆排序在公平性指標(biāo)上一騎絕塵，遙遙領(lǐng)先于另外 9 種推薦系統(tǒng)算法。

下面我們看一下該算法在 LDOS-CoMoDa 數(shù)據(jù)集合上的表現(xiàn)：

圖 3. LDOS-CoMoDa Dataset (MAE 指標(biāo))

圖 4. LDOS-CoMoDa Dataset (Degree of Matthew Effect 指標(biāo))

通過圖3和圖4，我們了解到斯奇拉姆排序在公平性指標(biāo)上一騎絕塵，在準(zhǔn)確性指標(biāo)上表現(xiàn)優(yōu)異。結(jié)論和上一個(gè)實(shí)驗(yàn)類似。

斯奇拉姆排序結(jié)合了泊松分布、矩陣分解和 Pairwise Ranking 等概念，是一個(gè)不可多得的推薦系統(tǒng)排序?qū)W習(xí)算法。在技術(shù)領(lǐng)域，掌握排序?qū)W習(xí)技術(shù)的人只占掌握深度學(xué)習(xí)的人的人數(shù)的1/6，因此排序?qū)W習(xí)屬于稀缺技術(shù)。而能夠在推薦系統(tǒng)領(lǐng)域發(fā)明原創(chuàng)性排序?qū)W習(xí)的人才更是少之又少。排序?qū)W習(xí)算法，把人們從評(píng)分預(yù)測(cè)的狹隘視角中解放了出來，讓人們意識(shí)到最重要的事情是順序，而不是分值?；诠叫缘呐判?qū)W習(xí)，目前在信息檢索領(lǐng)域中大火，特別是 SIGIR 等頂會(huì)，非常歡迎基于公平性的推薦系統(tǒng)的論文，希望能夠得到讀者們的關(guān)注。

作者簡(jiǎn)介

汪昊，前 Funplus 人工智能實(shí)驗(yàn)室負(fù)責(zé)人。曾在 ThoughtWorks、豆瓣、百度、新浪等公司擔(dān)任技術(shù)和技術(shù)高管職務(wù)。在互聯(lián)網(wǎng)公司和金融科技、游戲等公司任職 12 年，對(duì)于人工智能、計(jì)算機(jī)圖形學(xué)和區(qū)塊鏈等領(lǐng)域有著深刻的見解和豐富的經(jīng)驗(yàn)。在國(guó)際學(xué)術(shù)會(huì)議和期刊發(fā)表論文 42 篇，獲得IEEE SMI 2008 最佳論文獎(jiǎng)、ICBDT 2020 / IEEE ICISCAE 2021 / AIBT 2023 最佳論文報(bào)告獎(jiǎng)。