如何減低排名計算的偏誤

本文的閱讀等級:中級

讀者朋友是否曾有類似下面這種挫折經驗?你各方面學業表現都比室友優秀,平日不但罩他作業,考前還幫他複習。一回,你們兩人同時報名參加研究所推甄入學,結果他老兄正取,你卻落得備取。這是因為審查委員不公正?還是他們老眼昏花?也許是,也許不是。你不幸落敗的真正原因很可能是排名計算偏誤造成的!

 
考慮這個問題情境。一家科技公司計畫招募一名研發人員,人力資源部門從眾多人選過濾出履歷最佳的五位應徵者進入最後的面試階段。該公司非常重視此次招募作業,因此委派三名資深經理擔任評審委員,他們的任務是要決定徵才的優先排名。

 
下表顯示三位評審給予應徵者的評分,三位評審委員以 A,B,C 代表,五位應徵者則以1,2,3,4,5 編號。最簡單也是最常見的評比排名方式是將每個應徵者的得分加總,再以其平均得分排序,如表的最右欄所示,排序結果為:2=4>5>1>3。

e68e92e5908d1

五位應徵者得分

這種平均分排名法有兩個明顯的缺點:

  • 無法避免相同平均分數發生的情況 (如 2 號和 4 號應徵者),平分時必須以其他方式打破僵局。
  • 評審給出評分的變異有所差異,造成每位評審對於排名結果有著不同的影響力。評分範圍較廣的評審 (如 A) 比起評分範圍較窄的評審 (如 C) 具有較強的主導力量。譬如,排名第三的 5 號應徵者,在評審 B 和 C 的眼中其實是名列最優等第。

為了改善第二個缺點,我們可以引用類似球類比賽累積得分的辦法。想像三位評審的評等代表三次循環賽的結果,在 A 場賽事中,1 號 (70 分) 負 2 號 (80 分),勝 3 號 (50 分),負 4 號 (90 分),勝 5 號 (60 分)。我們設定勝者得 1 分,平手得 1/2 分,負者得 0 分,下表 A 第一列表示 1 號應徵者和其他四位應徵者競賽後的得分,第二列則表示 2 號應徵者的得分,以此類推。同樣地,B 場賽事和 C 場賽事得分也可以計算出來。

e68e92e5908d2

五位應徵者的累計得分

將 A,B,C 三場賽事的得分相加可得到下表,加總後的積分如最右欄所示,按此累積得分的徵才次序為:2>5>4>3>1。這個新排名與平均分數排名的最大差異是 4 號和 5 號應徵者的排序對調,而且 1 號和 3 號應徵者的排序也對調。

e68e92e5908d3

五位應徵者的加總得分

這個累積得分排名法仍然不能避免相同分數的情況發生,此外,僅以勝/負/平手這三種狀態來比較兩應徵者的差異有些失準。譬如,在 A 場賽事中,1號應徵者擊敗了 3 號和 5 號,但是 5 號對手的實力超過 3 號對手,1 號應徵者理應從打敗 5 號獲得相較打敗 3 號更高的分數才合理,也就是說得分應當根據對手的實力來加權。

 
我們引入符號以便利說明,設五位應徵者的實力分別以非負數 S_1S_2S_3S_4S_5表示,令應徵者的實力正比於由擊敗的對手等級所累計得到的加權積分,1 號應徵者的實力可計算如下:

\displaystyle S_{1}=\frac{1}{\lambda}(1.5S_{3}+0.5S_{4}+S_{5})

其中 \lambda>0 為常數,其他四位應徵者的實力為

\begin{aligned}\displaystyle S_{2}&=\frac{1}{\lambda}(3S_{1}+2.5S_{3}+1.5S_{4}+1.5S_{5})\\  S_{3}&=\frac{1}{\lambda}(1.5S_{1}+0.5S_{2}+S_{4}+0.5S_{5})\\  S_{4}&=\frac{1}{\lambda}(2.5S_{1}+1.5S_{2}+2S_{3}+S_{5})\\  S_{5}&=\frac{1}{\lambda}(2S_{1}+1.5S_{2}+2.5S_{3}+2S_{4})\end{aligned}

將上式寫為矩陣乘法 M\mathbf{x}=\lambda\mathbf{x},其中

M=\begin{bmatrix}  0 & 0 & 1.5 & 0.5 & 1 \\  3 & 0 & 2.5 & 1.5 & 1.5 \\  1.5 & 0.5 & 0 & 1 & 0.5 \\  2.5 & 1.5 & 2 & 0 & 1 \\  2 & 1.5 & 2.5 & 2 & 0  \end{bmatrix}

\mathbf{x}=\begin{bmatrix}  S_{1}&S_{2}&S_{3}&S_{4}&S_{5}  \end{bmatrix}^T。這指出應徵者實力值所構成的向量 \mathbf{x} 即為矩陣 M 的特徵向量。

 
問題是矩陣 M 可能有 5 個特徵向量,究竟要選哪一個?幸好 M 有一些特殊性質:M 的每一個元皆不為負,而且 M 是不可約 (irreducible)。將矩陣 M 的非零元以 1 取代,視此矩陣為包含 5 個頂點的有向圖 (directed graph) 之鄰接矩陣,不可約是指任兩個頂點總是存在連接路徑。當不可約的矩陣其每個元都不為負值時,Perron-Frobenius 定理確定下面兩件事 (見“特殊矩陣 (21):非負矩陣”):

  • 存在一個實特徵值 r,對於任何其他特徵值 \lambda,滿足\vert\lambda\vert\le r
  • 對應特徵值 r 的特徵向量中的每個元皆不為負數。

換句話說,我們可以放心的採用對應最大特徵值的特徵向量。將上述矩陣 M 的特徵值解出,分別是:5.215-1.408+0.765i-1.408-0.765i-0.942-1.458。注意特徵值的總和為 0,此事實可由 \mathrm{trace}(M)=0 加以確認。對應最大特徵值 5.215 的特徵向量為

\begin{bmatrix}  0.232\\  0.564\\  0.268\\  0.485\\  0.566  \end{bmatrix}

 
加權累積得分排名法根據應徵者實力分析產生的徵才次序為: 5>2>4>3>1,與未加權的累積得分排名相比,5 號應徵者反而以極其微小的差距超越 2 號應徵者。分析其原因發現:在 A 場賽事中, 5 號應徵者曾敗給三位對手,但在 B,C 兩場賽事中,5 號應徵者都成功地擊敗或打平其他參賽者,包括實力堅強的 2 號對手。

 
加權累積得分排名法的優點在於有效消除因評審成績變異不同而造成的偏誤,此法將對手實力反應於個人實力的計算上,因此更能呈現彼此的差異;另外,此法出現相同得分的機率很低。加權累積得分排名法的缺點是一般大眾不太容易理解,還需要使用軟體程式來解特徵方程式,也因此阻礙其普及性。現實是絕大多數人仍然執意採用平均分排名,要叫他們破除「平均=公平」這個的迷思可說是不可能的任務。

廣告
本篇發表於 線性代數專欄, 圖論, 應用之道 並標籤為 , , , 。將永久鏈結加入書籤。

5 Responses to 如何減低排名計算的偏誤

  1. question 說道:

    你好,有很多特征值,但是那个“选哪一个好呢”这个问题还是没有回答啊?为什么最大的特征值好呢?

  2. ccjou 說道:

    推論結果僅顯示 \mathbf{x} 要滿足特徵方程 M\mathbf{x}=\lambda\mathbf{x}\lambda>0\mathbf{x} 的各元皆為正數。當然,滿足上述條件的特徵向量可能不止一個。

    這裡是數學和實際應用的分界。在現實應用中,我們希望總能得到一個解,而且存在可靠的演算法求得該解。最大特徵值符合這兩項要求。首先,Perron-Frobenius 定理保證了對應最大特徵值的特徵向量的每個元皆為正數。再來,Power 法很容易算出對應最大特徵值的特徵向量。
    http://en.wikipedia.org/wiki/Power_iteration

    理想上,我們應該從眾多解中選擇一個"最佳解",在此最佳的意義可能是指矩陣 M 在受擾動情況下(代表評審的失誤),最不敏感的特徵向量(表示最強健可信)。不過,特徵向量的敏感度由對應的特徵值敏感度與數值相近的特徵值共同決定,對應最大特徵值的特徵向量未必是最不敏感的特徵向量。

  3. question 說道:

    thanks,Perron-Frobenius 定理真是很有用。你的网站能把很多东西讲的很“容易”真的很不简单啊。非常感谢!
    此外,我想问一个题外话,是否有系统的资料把这些东西都过一遍呢?Perron-Frobenius 定理,Power Iteration,Pagerank等算法都是成熟应用了吧。可是我看过大陆的一本线代教材和那本Elementary Linear Algebra(Ron Larson),可是都没有讲到这些啊。您的这些东西都是看paper总结来的呢,还是有系统的书介绍这些知识?
    thanks!

  4. ccjou 說道:

    Perron-Frobenius 定理是較艱深的矩陣分析理論,Power 算法則屬於數值線性代數(矩陣計算),一般線性代數教科書不會討論這些內容,印象中好像也沒見過哪本書有系統的介紹這些知識。不過,我發現這幾年線性代數的某些方法和技術,例如奇異值分解、矩陣的數值計算,和圖論相關的矩陣理論,都有越來越多的實際應用。可能過一陣子,真會看到討論這些主題的專書出版。

  5. ccjou 說道:

    我先前的回覆不全然正確,幸好及時發覺,以免錯誤訊息四處傳播。

    Perron-Frobenius 定理說:

    n\times n 階矩陣 A=[a_{ij}] 為非負矩陣,亦即對於任意 i,ja_{ij}\ge 0,若 A 是不可約化矩陣,則有以下性質:

    (1) 譜半徑 (spectral radius) r>0r=\mathrm{max}_i\vert\lambda_i\vert,也就是絕對值最大的特徵值為一正數。

    (2) \lambda=r 的特徵空間維度等於 1,換句話說,只有一個特徵向量。這很好,我們不必擔心要選擇那個特徵向量,我們稱此特徵向量為 Perron 向量。

    (3) 除了 Perron 向量之外,對應其他特徵值 \lambda\neq r 的特徵向量都不會是非負向量(即每個元都大於或等於零)。

    根據這個性質,只有 Perron 向量滿足我們的要求。所以,選擇 Perron 向量還是屬於數學範疇。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s