KDD2020最佳論文學習：On Sampled Metrics for Item Recommendation

一囤耳、簡介

項目推薦任務需要根據(jù)上下文對大型項目目錄進行排序启泣，使用取決于相關項目位置的排名度量指標來評估項目推薦算法。為了加快度量的計算思杯，最近的工作經(jīng)常使用抽樣的度量，其中僅對較小的一組隨機項和相關項進行排名挠进。該論文對抽樣指標進行了更詳細的調(diào)查智蝠，結(jié)果表明它們與確切指標的性能不一致。另外奈梳，實驗結(jié)果表明抽樣規(guī)模越小杈湾，指標之間的差異就越小，而且對于非常小的抽樣規(guī)模攘须，所有指標都會塌陷為AUC指標漆撞。所以該論文提出了一種改進的抽樣評價指標來提高評價質(zhì)量。

二、主要評價指標

該論文主要研究的評價指標包括：AUC浮驳、Prec悍汛、Recall、AP以及NDCG至会。在之前的學習中已經(jīng)詳細了解了這些評價指標离咐，具體內(nèi)容可參考原文鏈接。目前大部分文獻采用的簡化過后的指標奉件，假設只有一個正樣本宵蛀，即 $|R|=1$ ，然后基于這個正樣本采樣若干個負樣本县貌，以此來進行排序术陶，看最終該正樣本排在了什么位置。各個指標可簡化為： $AUC(r)_n=\frac{n-r}{n-1}$ $Prec(r)_k=\delta(r\leq k)\frac{1}{k}$ $Recall(r)_k=\delta(r\leq k)$ $AP(r)_k=\delta(r\leq k)\frac{1}{ r }$ $NDCG(r)_k=\delta(r\leq k)\frac{1}{log_2( r+1)}$

三煤痕、期望指標

用替換重復抽樣過程m次梧宫，并計算某項排名較高的頻率，相當于二項分布摆碉。換句話說塘匣，從抽樣過程中獲得的排名 $\widetilde{r}$ 服從二項分布 $B(m,\frac{r-1}{n-1})+1$ 。如果沒有成功獲得更高排名的項目巷帝，則排名保持為1馆铁，如果所有m個樣本均成功，則排名為m +1锅睛。在此分布下埠巨，指標的期望值為： $E[M(\widetilde r)]=\sum_{i=1}^{m+1}{p(\widetilde r=i)M(i)}$ 該論文將上式應用于特定指標，分析了抽樣指標现拒。

AUC是排名的線性函數(shù)辣垒，則通過期望的線性和 $\widetilde{r}$ 遵循二項分布的事實，可以得到：

AUC

這意味著通過抽樣產(chǎn)生的AUC測量是精確AUC的無偏估計印蔬。因為AUC也可以定義為一個隨機的相關項目排在一個隨機的不相關項目之上的期望勋桶。因此，AUC是抽樣下的一致指標侥猬。這一結(jié)果也適用于任何抽樣分布例驹，比如超幾何分布的抽樣-即不替換的均勻抽樣愈诚。

對于精確率和召回率：

Recall

這種分析適用于任何抽樣分布替久，包括超幾何分布。

對于采樣平均精度的期望值宪萄，分為兩種情況：如果 $r=1$ 瞧预，那么 $\widetilde{r}=1$ 屎债，并且采樣的度量總是等于1仅政。如果 $r>1$ ，則 $p(j<r)>0$ 且

該部分驗證了除過AUC之外的盆驹，抽樣指標與確切指標的性能不一致圆丹。

四、修正指標

排序的無偏估計量
第一種方法是基于一個簡單的觀察躯喇，通常使用的抽樣度量是將精確度量M應用于觀察到的排序 $\widetilde{r}$ 辫封，即 $\hat{M}(\widetilde{r}) = M(\widetilde{r})$ 。但 $\widetilde{r}$ 是真實秩 $r$ 的一個很差的估計廉丽，總是低估它倦微。相反，可以不在觀察到的等級 $\widetilde{r}$ 上而是在 $r$ 的無偏估計量上測量度量雅倒。如果我們讓 $p=\frac{r-1}{n-1}$ 璃诀，那么p的無偏估計量由 $\frac{\widetilde{r}-1}{m}$ 給出弧可，因此 $r=1+(n-1)p$ 的無偏估計量由 $\hat{r}=1+\frac{(n-1)(\widetilde{r}-1)}{m}$ 給出蔑匣。則得出以下正確的度量標準： $\hat{M}(\widetilde{r})=M(1+\frac{(n-1)(\widetilde{r}-1)}{m})$ 由于排序估計在 $[1,n]$ 中是實數(shù)，而原來的度量M只定義在自然數(shù)上棕诵，可以對排序估計進行四舍五入裁良，也可以使用線性插值等方法對M進行擴展。