#RecSys09 話題： what's on recommender researchers' mind?

這幾天推薦系統界的年度盛事之一 ACM Recommender System 2009 正在美國紐約市舉行， 會後必然會有許多學養俱佳的學者和產業分析師和大家分享見聞以及會中眾人關注的話題，想儘快知道 what's up; what's hot 的讀者可以在推特上關注 #RecSys09 這個 hashtag 。

如果想更快知道究竟今年有哪些熱門話題，就來看看在 University College Dublin 教書的 Barry Smyth 為大家製作的標籤雲，看起來 Netflix 還是大熱門的 buzzword 啊！

Er....Netflix Prize goes to...?

上個月這個時候，Netflix Prize 主辦單位宣佈餐賽團隊 BellKor's Pragmatic Chaos 提出的演算法比Cinematch 改進百分之十，是第一個跨過門檻的隊伍，其他參賽者有最後30天的時間爭取最後的奪冠機會(In accord with the Rules, teams have thirty (30) days, until July 26, 2009 18:42:37 UTC, to make submissions that will be considered for this Prize. )。

原本以為最終結果應該是 BPC 的囊中物，應該不會有什麼懸念，但就在時間截止之前，另外一個隊伍 Ensemble 宣稱他們也跨過門檻(Breaking - Netflix Prize, we’ve got a winner, and it’s Greek! (updated))，甚至一度自行宣佈他們勝過原本的領先者，是最終的贏家(下圖是目前Leaderboard公佈的成績)。不過，一位自稱 An Insider 的網友在這篇文章之後留言，解釋他們可能誤解了規則，BPC 在 Test Set 的成績較優，才是最終的贏家(自稱 Just a guy in garage 的 Gavin Potter 很快的在個人部落格撰文解釋為什麼 BPC 才是贏家)。

Netflix Prize Leaderboard via kwout

到目前為止， Netflix 仍然沒有正式宣佈誰是最後的贏家，只是宣佈停止收件，並且說有兩個隊伍通過門檻。

As of July 26, 2009 18:42:37 UTC, we have stopped gathering submissions for the Netflix Prize contest. There are submissions from two teams that meet the minimum requirements for the Grand Prize. We are contacting the lead team and we will report, as soon as possible, when and if we have a verified winner for the Grand Prize.

補充：

不管誰贏得這個比賽， Daniel Lemire 說的好，充份鼓勵各種創意和多元化的發展，才是學術發展的正確方向：

Both teams broke the 10% barrier by using a diverse coalition, by merging several different ideas. As Peter Turney recently stated:

There are no whole-truths, but we can get by reasonably well with a large number of half-truths.

I am now more convinced than ever that science needs diverse explanations, techniques and opinions. We should actively reward creativity. Science is not merely about truth-seeking.

Netflix Prize goes to BellKor's Pragmatic Chaos?

今天早上 Daniel Lemire 指出 BellKor's Pragmatic Chaos (BPC) 團隊宣佈他們已經贏得本次 Netflix Prize 大獎。線上 CD/DVD 租賃公司 Netflix 在 2006 年 10 月，宣佈舉辦一個推薦系統競賽，優勝者的獎金是一百萬美元，優勝條件是參賽者提出的演算法必須比 Netflix 公司目前線上使用的推薦系統Cinematch 準確10%。

BellKor's Pragmatic Chaos 在他們的網頁上宣佈，他們已經達到 10.05% 的成果，所以他們贏得本次大獎賽。

June 26, 2009: Today our team submitted our solution to the Netflix Prize, resulting in a score of .8558, which corresponds to an improvement over Netflix Cinematch algorithm of 10.05%. This is the first submission in the competition to break the 10% barrier and sets off a 30 day period where all competitors are invited to submit their best and final solutions.

此刻 Netflix Prize Leaderboard 也顯示 BPC 在 2009-06-26 18:42:37 提出的成果已經達到 10% 門檻值：

Netflix Prize: View Leaderboard via kwout

Update 1:

RWW 隨後也報導了這個消息， Marshall Kirkpatrick 執筆的 They Did It! One Team Reports Success in the $1m Netflix Prize 文中簡述比賽的背景，並且引用紐約時報的專文 If You Liked This, You’re Sure to Love That 談到所謂正確預測用戶的喜好，不見得是萬靈丹。下一代的推薦系統，還有很長的路要走。

Update 2:

真正的推薦系統行家人Greg Linden 顯然知道更多內情，他不僅說明 BPC 是由四個團隊合併合成，還提醒大家一件事，別的團隊有一個月的緩衝時間逆轉局勢：Other teams have 30 days to beat it, but, no matter what happens, the $1M prize will be claimed in the next month。

不論最後結局如何，恭喜得勝的團隊，Congratulations to the winners!

Question: Netflix Prize within months?

獲得2008年度 Netflix Progress Prize 的團隊 BellKor in BigChaos 在今年一月初，又提交一次成果，這回他們把成績從 RMSE 0.8616 推進到 RMSE 0.8598，距離得獎所需的標準 0.8563 又推進一大步。

Netflix Prize: Leaderboard (Jan 23, 2009) via kwout

雅虎的資深研究員 John Langford 在閱讀 BellKor in Chaos 釋出的文件(1，2)後，在他的個人部落格 Machine Learning (Theory) 指出也許距離獎金揭曉的時間不遠了，他同時指出該團隊演算法包含了 stochastic gradient descent, ensemble prediction, and targeting residuals 各領域的技術，並且指出他們在 2008 年間將演算法參數化的努力。他同時意味深長的說，或許- the right parameterization might very well succeed - 正確的參數就能將大獎抱走呢！

Several aspects of solutions are taken for granted including stochastic gradient descent, ensemble prediction, and targeting residuals (a form of boosting). Relatively to last year, it appears that many approaches have added parameterizations, especially for the purpose of modeling through time.

當然，John Langford 也在他的短文裡，提出了他的疑慮：One fear is that the progress is asymptoting on the wrong side of the 10% threshold，可是他也承認從去年底到今年一月的進步的的確令人印象深刻 。

不過我個人比較好奇的是這些演算法，能不能作適當的改變後，應用到其他的產品，或許參數化正是往這個方向努力的指標之一，但是我對 overfitting 這件事仍然有點疑慮。雖然還沒有時間深入研讀相關文件，但在 John Langford 的部落格留言區以及 Netflix 網站的論壇裡有讀者討論到 overfitting 的問題，雖然有人認為這個比賽已經在各方面取得平衡(請參考這裡)，不需擔心 overfitting，但是我個人仍然存疑。

或許 - Time will tell。

It's all about "Sorting out demand"

2月底，Wired 雜誌報導一位神秘的 Netflix Prize 參賽者"Just a guy in a garage"的個人專訪，及令人驚訝的技術策略。

Just a guy 是一位退休的管理顧問 - Gavin Potter，有別於大部分參賽者所採取的策略（傳統的資訊科學或統計方式的技術策略可參考筆者寫的2007年度獎金得主 BellKor 的技術說明），他以 behavioral economics 的理論為基礎，佐以產業界經驗為輔，去年十一月參加比賽後，只花了一個月就衝到前十名，目前（2008/03/07）排行第八。

Wired 雜誌挖掘出 Just a guy 的身份，比較分析大部份參賽者策略與 Gavin Potter 方案的不同之處，並且指出一個令人期待的方向：心理學家與資訊科技工作者共同合作開發推薦系統。

Gavin Potter 在接受訪問時說 "The 20th century was about sorting out supply, The 21st is going to be about sorting out demand." 而 Wired 雜誌編輯「畫龍點睛」地為這句話下了註腳：- The Internet makes everything available, but mere availbility is meaningless if the products remain unknown to potential buyers。

文章很長，不方便摘譯，請到 Wired 網站閱讀原文 - This Psychologist Might Outsmart the Math Brains Competing for the Netflix Prize。

推薦系統的分類（2008 Edition）

去年下半年我寫了一系列文章介紹推薦系統（Recommender System）的運作和各方面的影響，在檢視 FeedBurner 的點閱資料之後，發現推薦系統的分類是去年被點閱次數最多的文章。

但是重新審視這篇文章，發現有許多含混不清，甚至有些文字可能會產生誤導，不禁大為赧然，冷汗直流。趁著08年開春，重新改寫這篇文章，希望能讓推薦系統的輪廓更清楚具體，更易於理解，也少一些錯誤。

在Netflix Prize 滿週年了這篇文章裡我介紹了一個數學模型，以量化（消費者以數字表達喜好商品的程度）消費者行為的切入角度，描述推薦系統的運作機制。

雖然以數學模型來定義（或者說描述）研究對象的特性與運作方式，是許多學者很喜歡用的手法，但是這樣的方式對於一般的讀者而言，畢竟缺少了點人味兒。接下來，我們試著理清「推薦系統是怎麼運作的」、「究竟有多少種推薦系統」，讓推薦系統這個東西更具體一點，更有人味一點。

所以，本文我要談談推薦系統的分類（Taxonomy）。

消費者的角度：Personalization, Social, Item, Hybrid....

ReadWrite/Web 的專欄作者Alex Iksold 在07年初發表的 The Art, Science and Business of Recommendation Enginesn Engines 裡，以消費者使用服務的觀察角度，將推薦系統分為四類：個人化推薦、同儕式推薦、產品導向推薦以及綜合前述三種技術的綜合推薦。這種分類方式，和學術界以使用資料的方式為切入角度的分類法，有令人驚訝的對應關係。

The main approaches fall into the following categories:

• Personalized recommendation - recommend things based on the individual's past behavior
• Social recommendation - recommend things based on the past behavior of similar users
• Item recommendation - recommend things based on the thing itself
• A combination of the three approaches above

這篇文章有簡體中譯版，有興趣的讀者，可以到譯言去找這篇文章來看，文章的標題是「网站推荐机制中的艺术、科学与商务问题」。Beyond Search 也有關於這篇文章的精彩說明，建議大家也可以看看 Beyond Search 的文章（可惜這個部落格好一陣子沒有新作了）。

學術界的分類

每種分類方式，都有各自的思考邏輯與侷限，也都可能有模糊和不能明確區分的盲點，不同的分類方式之間，也未必有清楚明確的對應關係，這是這無礙於我們對事物本質的理解，重點在於弄清楚分類的思考邏輯與切入方式。

在這裡，我們用一種直覺的方式，以研究者切入推薦系統研究的歷史進程，來看推薦系統的分類與演化，個人覺得是個不錯的閱讀策略。

當研究者和企業經營者開始進行推薦系統的開發研究時，首先看手上有多少資源可以使用，所以先嘗試從消費者的個人資料和過去的消費紀錄，推估消費者對於不同產品的反應，做出推薦系統的先驅產品。

這種方式，過去的學者叫做 Content-based approach 推薦策略， Alex 將之稱呼為個人化推薦。因為是以消費者個人的資料作為推理基礎，稱做個人化推薦並無不當，不過相較於今日用戶在網路上能見到的各式花俏的個人化服務，此處所謂的個人化，可能會讓用戶有點失望，略嫌陽春了點（grin）。

(典型的 content-based recommendation - Amazon.com has new recommendations for you based on items you purchased or told us you own. )

Content-based 策略的優點是直覺、易於理解，但是缺點也很明顯。因為這種策略用白話來說，就是蒐集一大堆關鍵字（關鍵字當然越多越好），然後以資料挖掘（Data Mining）技術在關鍵字中間找出關係（大家是不是嗅到一點關聯法則的味道了？）。

有時候，有些與消費者有關的敏感資料，是很難蒐集到的，尤其在日益重視消費者隱私的今日，這是一個很麻煩的議題。其次，以這種策略建立的系統在遇到新會員、新產品項目時，就無所適從了，道理很簡單，沒有見過的關鍵字，系統不可能知道怎麼辦的（有人叫這種狀況 cold start）。

所以研究人員嘗試將視野放到所有會員、產品的資料庫，彙總眾人的消費習慣，得到預估的數學模型，作為推薦系統的基礎，這樣的策略，被研究者稱為 Collaborative filtering（簡稱 CF） ，因為是運用眾人的消費習慣做推理基礎，不是用個人（individual）的資料作為推薦引擎的燃料，所以用 collaborative 這個字眼。

不過 CF 的設計策略，又有兩種不同的切入角度，第一種是分析整體用戶資料，用各種計算方式找出計算不同消費者「背景」、「品味」、「行為」是否相似的數學模型，針對特定消費者，我們找出與之「相似的消費者」，使用這些背景「相似度」的用戶的行為，來預測特定消費者面對不同產品的喜好。過去研究者稱呼這種作法是 User based CF，這就是 Alex 所稱的 Social Recommendation 。

有一點要特別提醒諸君，此 social 和現在甚囂塵上的 social network 不一樣，千萬不要誤會了。我們到目前為止，所討論的推薦機制，基礎是量化後的銷售資料和消費者背景資料，不是基於交談、互動等等真正意義上的社群行為。雖然因為 Digg 和 Del.icio.us 服務的崛起，讓 Social Filtering 這個研究課題也走進舞台，步入聚光燈下，但是目前的研究成果，與 CF 領域的成熟度還是不能相比的。

(上圖左方是 Anobii 的例子，以產品特性去找出類似產品，典型的 Item-Based Approach ，右邊則是典型的 User-Based Approach ， 這個作法的典型呈現就像這個範例 - 其他購買 XXX 產品的顧客，都買了 YYY，所以我們向您推薦 YYY)

CF 的第二種策略，和第一種很相似，只是轉個角度，從產品的相似度切入，這就是 Alex所稱呼的 Item recommendation，學者則稱呼這種方式叫做 Item-based CF。著名的 Amazon.com ，就自行開發了 Item-to-Item 模式的演算法（請參考拙作[1,2]的介紹），作為其推薦系統的核心構成元件之一。這是目前在業界很受歡迎的策略，因為使用者的資料可能很難取得，但是產品販賣者應該擁有完整而詳細（這是我們對賣方的基本假設，如果賣東西的人，手邊沒有足夠好的產品資料，那就沒戲了）的產品資料，所以用 item-based 策略分析交易（transaction）資料和產品規格資料，可以玩出不少花樣。這是 Amazon 的選擇，也是得到 2007 年 Netflix Prize 年度獎金的 BellKor 團隊的選擇。

如上圖所示，CF 的兩個策略，分別從用戶和產品兩個角度切入

不論是以消費者個人歷史資料為計算基礎，或者以眾人的口味來推斷個人的喜好，都有其侷限，所以不論是學界還是產業界，都嘗試將以上的技術結合在一起，這就是 Alex Iksold 所說的 Combination of three approaches above，學界一般稱呼這種作法為 hybrid approach。我們在 Alex 的文章裡可以看到，Amazon 既運用了 Personalization （content-based）的技術，也使用了 Items Recommendation ( Item-based collaborative filtering)，這就是一個典型的綜合（hybrid）式推薦系統。

以上的脈絡其實很清楚，從消費者個人的資料入手，發現不足後，然後開發運用所有消費者資料的方法，繼而整合之前所開發的技術，這就是所謂的綜合（hybrid）策略。 Alex Iksold 的說明，用一般（非技術背景）讀者更易理解的文字，說明推薦系統的運作和分類，將這個思考脈絡，作了更佳的包裝。

如我在上文的說明，分類方式並不是唯一的， Beyond Search 的作者，以演算法的角度，作了更細的分類。2007年五月/六月份的 IEEE Intelligent Systems 雜誌，Guest Editor 做的導言，和另外一篇文章 Comparing Recommendation Strategies in a Commercial Context ，也有不同的分類陳述，精神大致相同，但是都有微小差異。總之，掌握自己的理解脈絡是最重要的。

演算法有多重要

不管如何分類，我們知道演算法（Algorithm）是推薦系統的核心，但是演算法如何能保證推薦系統的成功？

Collaborative Filtering 的模型裡，最困難的是相似度（Similarity Measure）的計算，能夠精確有效的計算產品間或消費者之間的相似程度，才能保障接下來的預測和推理是有效的。眾多學者為了克服這個挑戰，應用來自不同領域的數學背景知識，開發出許多相似度函數模型。但是有了這些精緻而複雜的數學公式，是否就能建設一個有效的推薦系統。

相似度的計算，其基礎不僅在於數學功力的精深，因為數學模型的目的是用建構出來的數字「逼近」現實發生的狀況，必然有其不足和限制。真正影響這個函數表現的，還是在於「事實」的根據 ─ 原始資料庫的品質。因此，有幾個關鍵問題是我們所必須關心的，比如說：

• 資料庫的資料是如何收集的？
• 資料的深度和廣度如何？
• 內容的正確性和時效性如何評估？如何保障？
• 每個欄位的意義為何？
• 是否有人能精確解讀為何這些欄位能描述消費者（或是產品）的特性？
• 很多產品有不同的包裝版本，甚至同樣的版本，也可能在資料庫裡有兩筆以上資料（想像一下書籍的普及版、精裝本、典藏版, etc），我們如何知道這些都是同一個產品？（這在業界叫做 item authority）
  
• 為什麼我們要關心這些或那些欄位？
• 那些資料欄位對我們沒有意義，不需關注？

所以，要建設一個成功的推薦系統，最重要的前提，是確定我們有一個有效的、有意義的資料庫，還要有一個（或一組）真正懂得產業 know-how 和資料庫技術的專家，才能正確、有效的運用我們已知的演算法，將之效用發揮到最大。而這一點，恰是許多產業界專案失敗的真正原因？

Google 的研發部門主管（Director, R&D），也是人工智慧領域的大師級學者 ─ Peter Norvig ，有回演講提到這個議題，他的看法是 Worry about the data before you worry about the algorithm。

Rather than argue about whether this algorithm is better than that algorithm, all you have to do is get ten times more training data. A..........

Worry about the data first before you worry about the algorithm.

請容許我如此解讀，優秀的演算法，需要大量資料（大陸那邊習慣說海量數據）來澆灌，離開真實世界的演算法，終究如鏡花水月，作不得真。所以成功的推薦系統，成功的基礎是充足、有效的資料，和真正懂得產業門道的分析師。

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日）為止的排行。

Netflix Prize: View Leaderboard via kwout

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

• Chasing $1,000,000: How We Won The Netflix Progress Prize. ASA Statistical and Computing Graphics Newsletter. Volume 18, Number 2.

• Lessons from the Netflix Prize Challenge. SIGKDD Explorations, Volume 9, Issue 2.

• The BellKor Solution to the Netflix Prize. This is the document which lays out our overall strategy - as was required in the rules of the competition in order to claim the Progress Prize.

• Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights. ICDM 2007.

• Improved Neighborhood Based Collaborative Filtering. KDD 2007 Netflix Competition Workshop.

• Modelling relationships at Multiple Scales to Improve Accuracy of Large Recommender Systems. KDD 2007 .

依照" 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 是不可能的 ）的改變，但這種變化，是值得我們放在心上，繼續觀察的。

延伸閱讀：

• 推薦系統： You 帶來了什麼?
• 維基百科怎麼說 Netflix Prize
  
• Netflix Prize 滿週年了
  
• 推薦系統的分類
• 推薦系統與長尾
  
• 從 Google 的訂閱推薦談起
  

後記：

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

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 SIGKDD 和 Netflix 共同舉辦的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)，和延伸的想法。

延伸閱讀：

• 推薦系統： You 帶來了什麼?
• 推薦系統的分類
• 推薦系統與長尾
  
• How they won the Netflix Progress Prize 2007?

Netflix recommender prize

如何提升現有客戶對企業營收的貢獻度，是所有行銷人員的最大挑戰之一。尤其是線上零售商（online retailer），必須盡一切力量，將客戶盡可能留在自己的網站，促使客戶購買更多產品，畢竟在線上世界每個商家的距離只是 one click away 而已。

所以企業主如何將手中擁有的客戶資料，轉換成有用的資訊，是需要行銷和資訊科技兩個專業共同合作的重大課題，這個研究課題就是所謂的推薦系統 (recommender)。

網路上，最常被人稱道、引用的 recommender 範例，首推網路書店 Amazon.com 和線上光碟租售服務的 Netflix 。 對於 IT 建設投資一向大手筆的 Amazon ，還為該公司自行開發的演算法申請專利，IEEE Internet Computing 雜誌在 2003 年，刊出了一篇由 Amazon員工撰寫的文章，簡介Item-to-Item Collaborative Filtering 演算法和設計背景。

Netflix 公司在去年十月宣布舉行一個 recommender競賽，廣邀天下英雄，以現在 Netflix 正上線使用中的推薦系統為競爭標的，目標是改善推薦系統的準確度，參賽者必須至少要比現行系統準確10%才能獲得 1百萬美元的獎金。根據紐約時報的報導，目前共有來自150個國家的18,000個團隊參加這場競賽。報導中中指出，現在的領先者來自匈牙利(Hungary)。

這個競賽是個很有趣的點子，顯而易見地，提升 Netflix 在線上世界與學府的知名度只是件小事；更有意義的是，這是一個廣邀世界各地研究者參加的大型腦力激盪，不僅推動了這個領域的研究，Netflix 的研發和行銷單位必然從世界各地來的企畫書學到許多，若干時日後，不知道我們會看到什麼樣的招數在江湖上出現。

不知道有沒有台灣的團隊參加這個競賽？