Friday, January 25, 2008

如何評估推薦系統(一)

這是很多年前的舊文了,最近有些網友找到這篇文章,於是有了一些很有意思的對話,我記錄在下面兩篇文章,如果您有興趣,也歡迎看看這些簡短的記錄,批評指教。謝謝。


-----

任何工作,包括學術研究與商業專案,都必須有衡量成績好壞的客觀標準(metrics),我們才能據以評估工作的品質以及判斷優缺點,並進而找出改進的方向。

我們剛接觸一個新的研究對象時,或許因為缺少標的物的相關知識(所以我們才要研究呀);也可能因為缺乏經驗,不知該觀察紀錄那些資料,常常不能找到理想的計算方式與評估標準。但是隨著我們對於研究對象的所知愈來愈豐富,數學計算的工具與實體的測量工具越來越方便好用,評估量尺的可用性與實用性也隨之進化,能提供我們更多研究(或者是商業上的決策)上的輔助。

學術界開始推薦系統的研究始自上世紀90年代初,這十餘年來(今年是 2008年,自九零年代至今,接近二十年了),經過許多學者的精心灌溉,發展出許多有用(且有趣)的演算法,也發展出許多評估推薦系統的計算方式。

因為電子商務的發展,推薦系統的重要性,已經廣受經營者與研究者的肯定。因此評估推薦系統時,從商業上的基本面來考慮,就是最實用的評估標準了。換言之,我們要問的是「推薦系統」的預測有多精準?建議是否有用?提昇營業效益多少

經過學者的努力,目前廣泛被使用的評估工具有兩大類,第一類考量的是推薦系統的正確性(Accuracy),也就是計算推薦系統的預測與消費者行為的誤差有多大,誤差愈小,推薦系統的精準度愈高。

(推薦系統評估方式的分類:Accuracy and Usefulness)

正確性的評估,還可以再細分為 Prediction Accuracy 和 Decision-Support Accuracy ,前者以 MAE (Maximum Absolute Error)、RMSE (Root Mean Square Error)等常用的統計工具,計算推薦系統對消費者喜好的預測與消費者實際的喜好間的誤差平均值;而後者則以 Reversal Rate 、Precision-Recall 或 ROC curve 為主要工具。。

Prediction Accuracy 指標很容易理解,計算方式也不複雜,Netflix Prize 競賽,就是以 Prediction Accuracy 作為評定得獎與否的依據,根據競賽辦法,得獎者演算法的 RMSE 數值,需要比 Netflix 公司目前使用的推薦系統 Cinematch 低(愈低愈好)百分之十,才能獲得百萬大獎。

(MAE .vs. RMSE)

但是這種指標的缺點也正是失之於簡單,過度簡化事實。考慮一個一到十分的評分系統,試看2與36與7以及8與9 這三個例子,這三個例子的差距都是1,在計算 MAE 或 RMSE 時,結果是相同的。從實際消費行為分析來看,第一個例子的兩個數字表示預測和實際都是不會購買商品,第三個例子則是預測與實際都顯示將會購買商品,但是第二個例子中 6與7的差距代表的意義可能是從「不考慮」到「可能會買商品」。

這表示:兩個 MAE 相同的系統,實際表現的差距可能很大。所以學者開始嘗試用 Reversal Rate 、Precision-Recall 或 Receiver Operating Characteristic 之類的指標,希望能將預測值與實際購買決策(買或不買)間的關聯更精確的表達出來,這就是所謂的 Decision-Support Accuracy。

Reversal Rate 的計算方式很簡單,首先選擇 High 和 Low 兩個基準數值,然後比較推薦預測與消費者所給的評分,如果消費者的評分大過 High 這個參考基準,但是推薦系統的預測是小於 Low ,我們叫這種情況是 High Reversal ;反之,則稱這種情況為 Low Reversal 。計算 Reversal Rate 可以反映這個系統產生的預測的準確程度。

Precision-Recall 的計算則是源自資訊擷取(Information Retrieval)理論,定義如下圖。在計算之前,我們要先定義什麼樣的評分是 relevant (7-10),以及何者是 irrelevant (1-6),為了計算方便,retrieved items 定義為所有物品的集合。

(Precision and Recall 的定義)

ROC (這裡沒有談政治,不要太敏感喔)是 receiver operating characteristics 的縮寫,如同 Precision-Recall 一樣,ROC 是從別的領域借鑒而來的,最早 ROC 是應用於訊號處理領域,目的是在於評估一個過濾器(information filtering system)區分訊號(signal)與雜訊(noise)的能力。

分析 ROC 曲線之前,首先要定義所謂好壞標準(relevant/irrelevant)的界線(threshold),如同計算 Precision-Recall 時一樣,relevant/ irrelevant 的定義方式是二元的,與 Reversal Rate 使用高、低( High、Low) 兩個參考數值的作法不同。有了 relevant/irrelevant 的定義之後,我們就可以做出有四個元素的 confusion matrix (消費者判定 relevant/irrelevant ,和推薦系統預測 relevant/irrelevant,剛好是四種組合)。

(資料來源: An Introduction to ROC Analysis

在繪製 ROC 平面時,我們只需要使用 FP ( false positive)和 TP(true positive)兩個數據, 比對每個物品的推薦預測與消費者的實際反應,我們可以得到 FP 和 TP 在所有物品中的比率(TPR and FPR),因此 FPR 和 TPR 的範圍是從 0 到 1 之間。

將 FPR 當作二維平面的 X 軸,TPR 當作 Y 軸,某個推薦系統的 (fpr, tpr)就是 ROC 平面中的(x,y),因此我們可以很容易地將這個點在座標平面上標示出來。如果改變 relevant/irrelevant 的界線(threshold)數值的定義,就可以得到很多組 (x,y) 數值,將這些點標出來,我們可以在平面中畫出一條曲線,這就是所謂的 ROC 曲線 (ROC Curve)。

分析 ROC 曲線敏感度的方法,就是計算曲線下的面積 (AUC:area under curve), AUC 愈大,表示系統能夠挑出愈多的好的品項,接受較少的不良品項。

已經有學者證明,大部分狀況下, 計算 ROC 和 Precision-Recall 時,會得到相同的 confusion matrix ,而且從其中一個曲線,可以推演出另外一種曲線的狀況。不過 PR 比較適合資料分佈高度不平均(highly-skewed)的情況,因此在實務上,演算法設計與系統評估方式的規劃,要視資料特性作修正。

推薦系統的預測準確度,當然是評估推薦系統的重要指標,但是「準確度」不是唯一的量尺,如果推薦系統所產生的預測與推薦和暢銷名單(best seller)一樣,固然 accuracy 的績效可以得到高分,但是我們只需要一份銷售排行榜就好了,何必大費周章地研究、開發推薦系統。所以另外一個量尺,「有效性」就格外值得我們留意了。

去年我在談推薦系統與長尾的時候曾經提到,推薦系統研究的開路先鋒 Paul Resnick 授, 曾經評論 discoveryreinforcement 是推薦系統最重要的兩個目的:
There are actually two effects that we should expect from recommenders. One is discovery-- once one person discovers an item, some other people with similar tastes who would not have found that item do find it. The other is reinforcement-- an item that many people have sampled will be more likely to get recommended.
本文所分析的各項 accuracy 指標,都是檢驗推薦系統在 reinforcement 方面的績效,下次我們將聚焦在 discovery 上,看看評估推薦系統的另外一個量尺-usefulness。

參考資料:

[1] T. Fawcett, "An introduction to roc analysis," Pattern Recognition Letters, vol. 27, no. 8, pp. 861-874, June 2006. [Online]. Available: http://portal.acm.org/citation.cfm?id=1159475

[2] J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. T. Riedl, "Evaluating collaborative filtering recommender systems," ACM Trans. Inf. Syst., vol. 22, no. 1, pp. 5-53, January 2004. [Online]. Available: http://portal.acm.org/citation.cfm?id=963772

[3] B. M. Sarwar, J. A. Konstan, A. Borchers, J. Herlocker, B. Miller, and J. Riedl, "Using filtering agents to improve prediction quality in the grouplens research collaborative filtering system," in CSCW '98: Proceedings of the 1998 ACM conference on Computer supported cooperative work. New York, NY, USA: ACM, 1998, pp. 345-354. [Online]. Available: http://portal.acm.org/citation.cfm?id=289509

No comments:

Post a Comment

如果我的心是一朵蓮花

~ 林徽因 · 馬雁散文集 · 蓮燈 ~ 馬雁 在她的散文《高貴一種,有詩為證》裡,提到「十多年前,還不知道林女士的八卦及成就前,在期刊上讀到別人引用的《蓮燈》」 覺得非常喜歡,比之卞之琳、徐志摩,別說是毫不遜色,簡直是勝出一籌。前面的韻腳和平仄的處理顯然高於戴...