Monday, December 31, 2007

How they won the Netflix Progress Prize 2007?

上個月(2007/11/13),Netflix 宣佈今年度的 Netflix 獎金賽 (想了解什麼是 Netflix Prize,請看說明1說明2)年度成就獎,由 AT&T 實驗室三位研究員( Bob Bell, Yehuda Koren, and Chris Volinsky )組成的 BellKor (原本叫 KorBell) 勝出。

在決定成績的10月1日,BellKor 當天的分數是 0.8712,三個月後,12月31日的最後成績是 0.8700,比當初確定得獎時的成績還略有小進,下圖是 Netflix Leaderboard 到現在(台北時間2007年12月31日)為止的排行。

BellKor在團隊首頁,公佈了幾份文件,說明他們所使用的策略,以及分析資料的心得與感想。簡而言之,他們使用 Collaborative Filtering 技術,並且有不少演算法上的改進與創見,這些研究上的成果,有些在今年度的 ICDM 07KDD 07 兩個學術研討會中發表。如果想閱讀這幾份文件,請參閱說明,點選文件超連結下載文件:

依照" Chasing $1,000,000: How We Won The Netflix Progress Prize"和"The BellKor solution to the Netflix Prize"這兩篇文章的說法,他們使用了 nearest neighbor methods 和 latent factors models 技術,以線性方式綜合 107 種預測預算數值,得到最終運算結果。這是以工筆的手法,畫長江萬里圖,功夫精深令人咋舌,我們只能說聲佩服佩服,對這三位學者獻上誠摯的賀忱。

研究推薦系統的學者 Daniel Lemire 看了 BellKor 的文章,在他的部落格中發表了他對於BellKor 參賽策略的理解 - How to win the Netflix $1,000,000 prize?。在文章中,他分析作者群研究資料時得到的觀察結果,以及在開發參賽程式時,實驗過程中得到的心得, Daniel 並以精要文字,說明了這些研究心得:

Here are some principles I take away from their work:

  • Singular Value Decomposition is useful to get overall trends.
  • Nearest-neighbor methods are better at picking up strong interactions inside small sets of related movies.
  • Nearest-neighbor methods should discard uninformative neighbors.
  • If you discard ratings and focus on who rated which movie, you seem to get useful predictors complementing the rating-based predictors.
  • Regularization is important (they use ridge regression) as expected.
今年度的成績已經成定局,但是所有的參賽者距離摘冠( RMSE <= 0.8563)仍然有一段長路要走 (it's a long way off)。其他的參賽者,想必不會束手讓 BellKor 獨走,最精彩的變化可能還沒有出現咧 , you ain't seen anything yet ...

雖然這場競賽的不僅提昇 Netflix 的知名度(當然是指在美國市場),也在學界掀起相當程度的關注(KDD 2007 有 Netflix Workshop 就是明證),但是也有些不同的聲音改進意見,值得我們關注和思考。

提到對於 Netflix Prize 的Tom Slee 今年七月在 The Nerflix Prize: 300 Days Later 表達的觀點,絕對不應被忽略。他在文章裡以將這個競賽的規則解釋得相當清楚(比我看過其他任何文件都清楚明白),然後解釋為什麼均方根誤差(RMSE: root mean square error)不是一個好的評比標準,他還在文章中以圖表說明 10% 的 RMSE 差異,在提供更好消費者服務這件事上是沒有意義的。

年度成就獎金公佈之後,作者(Tom Slee)在今年12月25日,對文章內容作了相當大幅度的增補,不過基本上,他還是認為 Netflix Prize 不能說服他真的達到集合眾人智慧(WISDOM OF CROWDS - 這是推薦系統研究者普遍相信的價值觀,推薦系統的精神是集合大眾的智慧,最終讓商家能找出提供更佳服務的方法)讓服務升級的目標。在文章最後,他的聲明是這麼說的:
I'm no futurist, but I see little evidence from the first 300 days of the Netflix Prize that recommender systems are the magic ingredient that will reveal the wisdom of crowds.
對於競賽辦法,以及競賽本質的質疑,固然值得我們思考。在 Collaborative Filtering 領域的研究方法以及研究成果,也有學者指出值得我們重視的盲點。

曾經是 Amazon 推薦系統開發者的 Greg Linden ,也是一個相當活躍的部落客,他在恭喜今年度得獎者之餘,提出對 overfiting 問題的警告 -
This work is impressive and BellKor deserves kudos for winning the prize, but I have to say that I feel a little queasy reading this paper. It strikes me that this type of ensemble method is difficult to explain, hard to understand why it works, and likely will be subject to overfitting.
有一個場景 ,許多台灣(這個問題應該不是台灣獨有的)的研究生們應該深有體悟,為了要讓學位論文裡的數據好看,熬夜琢磨著如何更改演算法和程式,讓演算法的輸出,在那一千零一組 static data 上,能得到最佳的效果。這107個預測模型的計算,也某種程度反應了這種「精神」,overfitting or overoptimized ,這是個值得思考的問題。

Daniel Lemire 從另外一個切入點,說明為什麼只使用一組靜態資料是不夠的,他認為『推薦系統不會影響使用者想對哪些產品評分,也不會影響評分的結果』的假設是有必要修正的, 因此他提出了一個還沒有被證實的假設 -

people's preferences are often constructed in the process of elicitation

我個人是相信這個假設的,但是要如何證實這件事並不容易,Daniel 自己也說他還不知道如何模擬電子商務網站的用戶行為,如果有人想出怎麼作,請和他聯絡:
If someone out there know how to simulate users (something I do not know how to do), please get in touch! I have no idea how to do sane user modelling and I need help!
雖然這不是件容易的工作,但是 Daniel 的態度坦率磊落,令人大生好感。這個問題還有另外一個意義,我們可以發現網際網路的生態,將漸漸影響研究和出版的操作模式,雖然不是劇烈( radical changes 是不可能的 )的改變,但這種變化,是值得我們放在心上,繼續觀察的。

延伸閱讀:
後記:
今年花了不少時間閱讀推薦系統的資料,以及關注 Netflix 大賽的動態,為了有始有終,我決定在 2007 年的最後一天,把 Netflix Prize 的狀況,作個階段性的總結。明年開始,我仍然會持續關注推薦系統的發展,但不會再聚焦在 Netflix Prize 上,而會把焦點延伸到更一般性的主題上。

No comments:

Post a Comment

如果我的心是一朵蓮花

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