Thursday, October 4, 2007

Netflix Prize 滿週年了

Netflix Prize 滿一年了。

提供線上租賃光碟服務的 Netflix,在去年十月(October 2, 2006)設立了一個推薦系統 (Recommender) 的競賽,鼓勵全世界的研究團隊,以 Netflix 目前使用中的推薦系統 Cinematch 為競爭標的,比 Cinematch 推薦績效高過10% 的團隊,將獲得一百萬美元的獎勵。這個比賽將持續到 2011 年(比賽時間從 2006年10月2日到2011年10月2日),依照競賽規定,除了冠軍之外,每年度還有五萬美元的進步獎(Progress Prize)。

提到推薦系統 (Recommender) ,網路書店亞瑪遜(Amazon 現在可能要稱為百貨公司比較恰當了)和 Netflix,一直是最為大家稱道的兩個模範生。這兩家公司,都有自己的演算法研發團隊,Amazon 在演算法方面的投資一向驚人,他們還高調的寫文章在學術期刊談由亞瑪遜員工自行開發的演算法,並且為演算法申請專利(補充:有部落格作者認為 Amazon 使用的技術就是 Association Rules ,我想是個誤會, Amazon 目前的推薦系統,應該是以上面所介紹在 IEEE Internet Computing 發表的 Item-based 演算法為核心,Amazon 當然用了不只一種技術,不過以 Amazon 目前系統的複雜和成熟程度,不是關連法則一種技術可以做到的,所以兩者之間畫等號是不恰當的)。

Netflix 也有自己的研發團隊,持續改善他們的推薦系統,雖然 Netflix 沒有在台灣地區推展業務,在台灣的知名度可能不高,不過如果用 BLOCKBUSTER(百視達) 的網際網路版本來介紹 Netflix ,我想大家對於 Netflix 的業務內容就會有概念的多了。

Netflix Prize 的消息傳出之後,在學術界和技術評論文章作者圈裡,激發出不少迴響與火花,紐約時報的專欄作者 David Leonhardt 撰文形容這個舉動是需要創意嗎?發獎金吧;有些部落格的作者(比如說 Greg Linden),定期追蹤這個比賽的進度;也有人從競賽的評分方式著手,批評這個比賽是象徵意義大於實質意義。

(補充: Greg Linden 是上面提到的 演算法 ─ Amazon.com recommendations: item-to-item collaborative filtering ─ 的共同作者之一,Greg 於1997-2002 間在 Amazon 任職,負責開發推薦系統)

筆者最關心的,則是參加比賽團隊的背景(有沒有華人參加?有沒有台灣的團隊),這些團隊參加比賽所提出的研究成果,是不是會影響,甚至豐富這個研究領域的出版。今年上半年,筆者嘗試從這個獎金專屬網站leaderboard,找到各個團隊的背景,以及各團隊成員的出版文獻。但是 leaderboard 所能找到的資料,都是為了參加比賽所做的寥寥數行自我介紹,幾乎找不到有用的資料,只好悻悻然的放棄。

今年下半年, Greg Linden 的部落格,提供了更深入的追蹤資料,找資料的過程總算漸入佳境;才舉行過不久的KDD 2007,由 ACM SIGKDDNetflix 共同舉辦的Workshop,發表了不少和這次競賽有關的論文,終於讓我解惑,滿足了我的好奇心。

在剛開始動筆 文章介紹 Netflix Prize 時,就已發願繼續寫一系列的延伸報導,從 Recommender 的研究動機與背景談起,將自己的唸書心得,以及在產業界所見所聞引發的某些想法,都包羅進來。但是前一陣子,恰好有些私事,又要準備參加考試,所以收集資料和動筆的腳步在前幾個星期放慢下來。

直到前兩天,原先佔用大部分可用時間的某些負擔,終於告一段落,決定重新整理原先的筆記。但是今天用 Bloglines 看文章(有資訊收集癖好的我每天必做的功課)時,在某個部落格的文章見到 Read/WriteWeb 在年初就已經發表了非常深入的報導。

Read/WriteWeb 在今年一月(January 16, 2007)發表由 Alex Iskold 寫作的文章 - The Art, Science and Business of Recommendation Engines,這篇文章不僅用流暢的文字說明產品推薦 (Recommender)機制之所以重要的原因,同時還介紹了目前實際商業運轉的推薦系統有哪些不同的作法,而且以圖文並茂的方式,以實例說明介紹推薦系統與消費者互動的運作。文章內容深入淺出,而且有豐富的圖片做輔助,對於非技術背景的讀者,是篇不可多得的好文章。對於推薦機制的背景有興趣的讀者,千萬不要錯過這篇文章;以迅速翻譯網際網路相關文章著稱的大陸網站譯言,在今年二月份就把這篇文章翻成中文,如果不想看太多英文字,可以試試這個版本

Alex Iskold 的文章,很成功的把推薦機制的背景交代清楚,我不需要再 reinventing the wheels (我不大可能比 Alex 做得更好 - grin)。因此筆者嘗試從技術的角度,勾勒出推薦系統至今的研究方向,和未來的挑戰。並從這個角度的分析繼續延伸,試圖找出成功的資料探勘專案,最起碼的成功要素。

推薦系統的研究,可以上溯到1990年代初期,經過十幾年的努力,推薦系統已經變成資料探勘領域裡獨立的研究分支,在2005年有學者發表一篇推薦系統領域的回顧文章 - Toward the Next Generation Recommenders: a survey of the state-of-the-art and possible extensions,作者用一個簡潔的數學模型的定義,完整描述推薦系統的運作。

根據這個模型,推薦系統的工作方式很簡單,一是預測:使用由研究者事先定義的數學模式,計算消費者對於不同產品的喜好度;二是推薦,經營者根據前述的計算結果,再參酌企業的經營限制與目標,執行「推薦」或其他相關的行銷活動,以達到經營的目標。

個人認為,這個模型特別值得注意的重點有兩個,第一是這個模型要求各項數據必須充分量化,才能以函數的方式描述運算邏輯,並製作計算的程式,計算的結果,也是以量化方式,表示推薦強度。其次,個人認為這個模型裡最重要的一點,就是把消費者的反饋加入模型,這個因素的加入,改變了推薦系統所要解決問題的範圍,和解決問題的方式。這樣的模型,讓推薦系統在技術上的需求,跨越了單一工具類型的演算法,比如說關連法則(association rules)、決策樹(decision tree),而是以更豐富、多樣的數學工具來達成目標。

(請見上圖,Amazon 會員以1-5顆星的評等方式,輸入他(她)對商品的喜好程度,這就是將消費者的反饋以量化方式儲存、建模的最佳範例)

曾經在網路書店亞瑪遜(Amazon)購書的消費者,對於它的評價系統(上圖就是推薦系統請使用者對產品評分的畫面),應該都印象深刻。被 Alex Iskold 稱為 King of Recommendation 的亞瑪遜,結合消費者的個人背景資料、消費紀錄,以及將消費者對於產品好惡反應量化的數據,設計他們的推薦系統。亞瑪遜的作法,就是這個推薦系統模型的最佳體現。

用亞瑪遜的創辦人 Jeff Bezos 自己的話來說明亞瑪遜對推薦系統的理念,是最清楚不過了:
Our vision is that if we have 20 million customers, we should have 20 million stores.
以書籍為例,推薦系統嘗試解決的問題是可能是這樣的:我知道客戶買了魔戒龍槍系列的小說,客戶會不會喜歡東方色彩的蜀山劍俠傳?喜不喜歡獅子、女巫與魔衣櫥?若我向他推薦J. K. Rowling (哈利波特的作者)寫的系列小說,成功機率多高?

更複雜的問題可能是這樣的:客戶買了魔戒,而且在書評系統裡,給這本書很高的評價,滿分十分,他給九分,那麼如果我們推出限量收藏版,推薦他購買的機會高不高?如果是推薦他購買哈利波特,預估他的反應是什麼?

有了推薦系統,企業主先計算特定消費者對各項產品喜好的傾向,從而決定促銷標的和手段。這就是我們看到的網路書店模範生─亞瑪遜─的運作方式。用最淺白的話來說,推薦系統根據消費者的交易記錄、商品的內容、消費者對於產品的滿意度資料,預測消費者對於各種產品的接受度,經營者根據預測的結果,做相應的行銷安排,將所有資源用在最可能有產值的地方 (這是賣方 supply-side 的觀點,那買方的觀點是怎麼樣的呢?)。

回到技術問題的角度,推薦系統的演算法不是由單一的技術構成。不同產業的產品性質差異可能很大,不同的業者對於資料精粗程度的掌握也不同,因此推薦系統的演算法使用來自各領域的技術,不同的研究者所偏好的數學工具也可能不同,更豐富了工具的複雜度。

因此,不論是關連法則(association rules),還是叢集(clustering)、決策樹(decision tree),都可能是某個推薦系統的構成元件之一,一個完備、有用的推薦系統,定是眾多研究領域的綜合成果的展現。

真正商業化的推薦系統,除了計算預估值的數學模式之外,還會加入其他商業、行銷領域的理論元素,每個企業的行銷目標與理念,必然有各自的想法與堅持,將這些理念融入推薦系統的運作,才是完整的推薦機制。而後者,已經超越了演算法的層次,不是單純購買運算資源(computing resources)或設計演算法(algorithms)可以克竟全功的,畢竟那已經超越 CIO 處理的層次,也不是本文所探討的課題了。

今天先談到這裡,下回再談推薦系統的分類(taxonomy),和延伸的想法。

延伸閱讀:

No comments:

Post a Comment

如果我的心是一朵蓮花

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