在某些情況下，我們需要度量兩個排序列表的距離，或者說相似程度。比如，在信息檢索領域，我們可能需要計算在某個查詢條件下系統給出的文檔的排序列表與一個預先定義好的「完美」排序列表的接近程度。或者我們可能需要比較不同搜索引擎的結果。又或者，在推薦系統中，我們需要監控某次演算法迭代（A/B測試）中，新演算法針對某個用戶給出的推薦列表與舊演算法給出的推薦列表的差異程度，以便決定是否要觸發自動報警。

在信息檢索領域，我們常用MAP、MRR、NDCG來評估排序演算法的好壞，然而這些指標依賴人工標註的query與document的相關性檔位（relevance level）。當沒有此標註數據，或者我們要評估的排序列表跟相關性無關，並且我們剛好有一個待比較的基準列表時，該如何評估它們之間的距離呢？how to measure the similarity between two rank list?

定義這樣一個排序列表之間比較的指標，我們期待它能滿足以下幾個方面：

  • 豐富度（Richness）
    • 能夠支持元素加權、位置加權等
    • Support element weights, position weights, etc.
  • 簡潔性（Simplicity）
    • 易於理解
    • Be simple to understand
  • 普適性（Generalization）
    • 也能支持不考慮權重的情況
    • Collapse to a natural metric with no weights are present
    • Should behave similar to other approaches
    • Allows us to select a metric best suited to the problem
  • 滿足距離定義的基本屬性（Satisfy Basic Properties）
    • Scale free, invariant under relabeling, triangle inequality...

排序列表距離度量大致可以分為兩大類方法: (1) 基於排序之間的相互關係（Ranked Correlation）；(2) 基於集合的度量（Set Based Measure）。

一、Rank Correlation

基於Rank correlation的距離度量方法本質上是量化任意兩個不同元素在兩個待比較的排序列表中的相對位置，例如，兩者保持相同順序的概率等。

1. 肯德爾等級相關係數（Kendall Tau）

我們可以用逆序對數量來量化兩個排序列表的不一致程度。

設 A 為一個有 n 個數字的有序集 (n>1)，其中所有數字各不相同。如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則 這個有序對稱為 A 的一個逆序對，也稱作逆序數。

逆序數有時候也叫做肯德爾等級相關係數。直接用逆序數來度量量列表之間的距離有個問題，就是不同長度的列表scale不一致。然而，多數情況下，我們希望用一個統一的量綱來度量列表距離。

圖1. Kendall Tau

現在我們常把肯德爾等級相關係數定義為統一量綱的版本，即兩個列表正序對的概率減去逆序對的概率，比如，計算元素A在列表1中排在元素B前面，那麼在列表2中元素A依然排在元素B前面的概率，具體值可以通過下面的公式計算：

au = P(C)-P(D)=frac{C}{N}-frac{D}{N}=frac{C-D}{N}

其中， N 是總的元素對數量，當列表有 n 個元素時， N=frac{1}{2}n(n-1) ； C 是在兩個列表中相對順序保持一致的元素對數量； D 是在兩個列表中相對順序不一致的元素對數量。

有時候列表中元素的重要性是不同的，交換兩個重要的元素之間的相對位置比交換兩個不那麼重要的元素之間的相對位置影響要大很多。那麼，如何在度量列表排序相似度的時候，考慮元素的權重呢？

一種方法是把權重為 w 的元素理解為有 w 個權重為1的元素連在一起構成一個整體，如下圖：

圖2. Weighted Kendall Tau

2. Spearmans Footrule

Spearmans Footrule是兩個排序列表之間的絕對距離，類似於文本編輯距離，度量把一個列表修改為另一個列表最少需要移動各個元素的距離的總和。

例如，假設A=[1,2,3];B=[2,1,3],則A和B的Footrule距離為 d_{AB}=|1-2|+|2-1|+|3-3|=2 。

Footrule距離可以理解為在 n 為空間上把其中一個點沿著坐標軸的方向移動到另外一個點最少需要移動的距離之和。

圖3. Spearman&#39;s Footrule

Spearmans Footrule距離度量也可以考慮元素權重，可以參考與Kendall Tau一致的方法。

圖4. Weighted Spearman&#39;s Footrule

二、Set Based Measure

基於集合的方法通過在計算兩個不同排序列表在不同深度時對應集合的交集大小來計算排序列表的相似度。假設我們有兩個列表：

A: [a, b, c, d, e] B: [b, a, c, d, e]

依次計算它們前k個元素組成的兩個集合的交集，以及交集大小相對於當前深度的比例。

一旦計算出不同深度的交集比例後，我們就可以通過交集比例的分佈來量化兩個列表的相似程度，最簡單的方式就是直接計算交集比例的平均值。在上面的例子中，當列表長度為5時，列表A和B的相似度為 4/5=0.8。

一般情況下，排序越靠前的位置的元素的權重越高。比如搜索引擎的結果，我們一般只關注排在最前面的文檔的相對順序，而排在後面的文檔一般不太關注。在中國互聯網公司實力排行榜上我們通常也只會關注那些Top的公司的相對順序，而不太關心幾百名之後的公司如何排名。因此，我們希望在比較兩個排序列表的相似性時，能夠考慮不同位置的元素的權重，尤其是關注top元素的相對位置權重。

假設我們另外有一列表C: [a, b, c, e, d]，與列表A比較後發現，列表C是通過交換列表A的最好兩個元素的位置得到的；而列表B是通過交換列表A的前2個元素的位置得到的。基於Set Based Measure，我們發現列表C與列表A的相似度為(1+1+1+0.75+1)/5=0.95，大於列表B與列表A的相似度（0.8），這正是我們所期望的。

綜上，Set Based Measure天然帶有top-weighteness屬性。

  • RBO(Rank Biased Overlap)

Rank Biased Overlap 距離度量方法進一步拓展了上述Set Based的方法。上述Naive的Set Based Measure方法計算出的距離是沒有上界的，隨著列表長度的不斷增加，有可能距離值會無窮大。為瞭解決這個問題，RBO給每個深度的交集比例定義了一個權重係數，最後計算結果時是加權和，而不是原來的平均值。

當然，不是任意的權重值分佈都能保證距離收斂。RBO選擇了幾何序列來保證這一點，具體地，RBO在無限長度的列表上計算兩個排序列表的步驟如下：

假設 S 和 T 為兩個無限長度的排序列表， S_i 為列表 S 的第 i 個元素， S_{c:d}={ S_i : c leq i leq d } 表示列表中從位置 c 到位置 d 的所有元素組成的集合。在深度為 d 時，列表 S 和 T 的交集為：

I_d=S_{1:d} cap T_{1:d}

交集的元素個數稱之為列表 S 和 T 在深度為 d 時的交疊（overlap），該overlap相對於深度 d 的比值稱之為列表 S 和 T 的一致度（agreement）。

A_d=frac{|I_d|}{d}=frac{|S_{1:d} cap T_{1:d}|}{d}

之前介紹的Naive Set Based Measure實際上是在計算平均交疊，即 AO(S,T,k)=frac{1}{k} sum_{d=1}^{k} A_d ，其中 k 是需要計算的深度。

RBO不再簡單地計算平均交疊，而是給每個深度的一致度一個權重 w_d ，再計算加權和: SIM(S,T,w)=sum_{d=1}^{infty} w_d cdot A_d

定義權重 w_d=(1-p)cdot p^{d-1} ，則 sum_d w_d = 1 ，因為當 0<P> 時，幾何級數 <img src= 收斂到 frac{1}{1-p} ，即

sum_{d=1}^{infty} p^{d-1} = frac{1}{1-p}

根據定義， A_d 是小於1的，則有 0 leq SIM leq sum_d w_d < 1 。

至此，RBO距離度量方法可以定義為：

RBO(S,T,p)=(1-p)sum_{d=1}^{infty}p^{d-1} cdot A_d

其中 p 是一個可以預先定下來的參數。可以看到RBO指標是有界的，值在0~1的範圍之間，並且RBO指標還帶有top-weighteness屬性。

RBO指標有很好的性質，非常適合用來度量兩個排序列表的相似度，強烈推薦！

參考資料

  1. Comparing Ranked List
  2. A Similarity Measure for Indefinite Rankings
  3. Rank Correlation and Distance Between Rankings
  4. 信息檢索評價指標(nDCG,MRR,MAP)
  5. Generalized Distances Between Rankings - Stanford CS Theory
  6. A New Weighted Spearmans Footrule as A Measure of The Distance Between Two Rankings

推薦閱讀：

相關文章