User Modeling? 一切都是假的！

Datalligence: Profiling your Customers! via kwout

Size Matters - 機器學習的分散式和平行處理議題

從John Langford的個人部落格看到這個消息：由 Ron Bekkerman (LinkedIn)，John Langford (Yahoo! Research)和 Misha Bilenko（Microsoft Research）共同編輯的 Scaling up Machine Learning 將在今年底出版。而且他們將在 KDD 2011 以這本書為基礎發表 Scaling Up Machine Learning 的 Tutorial。

依照 John Langford 的介紹：

This tutorial focuses on providing an integrated overview of state-of-the-art platforms and algorithm choices. These span a range of hardware options (from FPGAs and GPUs to multi-core systems and commodity clusters), programming frameworks (including CUDA, MPI, MapReduce, and DryadLINQ), and learning settings (e.g., semi-supervised and online learning). The tutorial is example-driven, covering a number of popular algorithms (e.g., boosted trees, spectral clustering, belief propagation) and diverse applications (e.g., speech recognition and object recognition in vision).

不在現場的我，是沒有機會親聆這場盛會啦，不過稍微瞄了下簡報檔，覺得這本書裡面的題材都蠻有意思的，比如說下面第一個圖提到克服隱私權疑慮的嘗試，和第二個圖 Tree Ensembles 的說明。

期待這本書的上市，不過看到價格實在是讓人有點遲疑啊，哈哈！

失之毫釐是不是謬以千里

在西班牙電信公司 Telefonica 研究院 工作的學者 Xavier Amatriain，前幾天在網誌上發表了一篇文章 Recommender Systems: We're doing it (all) wrong ，談到研究推薦系統的學者和開發者，在使用數據時，務必要注意數據的性質。

很多人使用 Likert Scale 做評分（Ratings）的量表基礎，比如說像「非常不喜歡、喜歡、無所謂、不喜歡、非常不喜歡」這樣的評分表就極爲常見，但是 Xavier 提醒我們 Likert Scale 的數據是 ordinal data ，這種數據僅僅表達次序關係，但是兩兩評分之間未必是 equidistant 的。若用這樣的數據計算距離（計算距離是相似性的基礎），其結果可能是失真的，循此邏輯推演下去，計算推薦系統準確率的指標 RMSE 的意義也可能失準。

從數學的角度來看，誤用定義當然是極爲嚴重的基本功的失誤，但是若從實務上考量，把 Likert 式評分當做 internal data，對推薦系統的成果究竟影響又多大，實在不好說 。不過，看來在這一點上不察，誤把馮京當馬涼的研究人員和開發人員可能不少哦！

Xavier Amatriain 寫這篇文章，是受 Judy Robertson 在 Blog@ACM 上的文章 We're Doing It Wrong 所啓發。Judy 在文中提到 2010 ACM Conference on Human Factors in Computing Systems  有學者發表研究 前一年會議中發表論文《Powerful and consistent analysis of Likert-type rating scales 》，爬梳學者使用的數據和統計工具，發現驚人的事實，原文是這樣的：

Kaptein, Nass, & Markopoulos (2010) published a paper in CHI last year found that in the previous year's CHI proceedings, 45% of the papers reported on likert type data but only 8% used non-parametric stats to do the analysis. 95% reported on small sample sizes (under 50 people). This is statistically problematic even if it gets past reviewers!

使用 Likert Scale 作爲實驗分析方法的學者竟然約略達到五成，Judy 在文章下半部提出她對此現象原因的觀察和建議，我對統計是大外行，只能點頭諾諾。但最抓住我眼球的句子是“95% reports on small sample size”這句，產業界鮮少有人信服學界真能做出「有用」的東西，確實有點道理，怨不得人。


[參考資料]
Kaptein, M., Nass, C., Markopoulos, P. (2010) Powerful and consistent analysis of Likert-type rating scales. In Proceedings CHI 2010, ACM, New York, NY, 2391-2394. DOI= http://doi.acm.org/10.1145/1753326.1753686

How recommender researchers test their algorithm and make the system smarter?

FastCompany 今日介紹 RichRelevance 首席科學家 Darren Vengroff想出一個讓研究人員測試推薦系統演算法的方法，其實這個點子很簡單，將真實世界的資料包裝成一個黑箱，讓研究者上傳程式，使用這個機制測試演算法的好壞。

There are many holy grails in online commerce, but one that has frustrated C-level executives and engineers alike is how to produce better recommendation algorithms. Produce better recommendations, and you’ll sell more stuff.
Historically, however, there has been one major structural impediment to making significant breakthroughs on this front. But the Chief Scientist at RichRelevance, which provides personalization solutions for the likes of Walmart, Sears, and Overstock.com, may just have fixed that. 

First, however, the impediment: The people who are likely to produce breakthroughs--the really smart smarty-pants in the math departments of the world’s universities--don’t have access to large bodies of real-world data. And without real-world data, they can come up with as many hypotheses and new types of math as they like, but they’ll never really know if it actually works in the real world. It’s like trying to learn how to serve without tennis balls. You can swing as much as you like, but until you actually hit a real-live ball, you can never be sure if your swing would actually place a ball in the serve box. 

For their part, the people who have real-world data--the Amazons and eBays of the world--can’t share it with the researchers for reasons of customer privacy. “Even if we anonymize it, we’re handcuffed because we can’t give out data that can be reasonably be used to reconstruct who someone really is,” the Chief Scientist, Darren Vengroff, tells Fast Company.

Vengroff, however, has come up with a novel solution: He’s created a “black box” of sorts with real-world data that researchers can use to run experiments on. Researchers won’t be able to look at the data, but they will be able to dump their algorithms in and have the box spit out results, which the researchers can then use to refine their hypotheses. 

It’s a simple idea, but it wasn’t really possible to execute until the advent of the cloud. Now researchers from any part of the globe will be able to use the system to run experiments. (In principle, of course--in practice, a committee will vet proposals and choose which ones will actually run.) 

Vengroff, who once worked as a Principal Engineer at Amazon, says he got the idea for the project while attending a computing conference last fall. “In one of the sessions, there were three consecutive papers in a row where about two-thirds of the way through, I was really excited about what was being presented, and then they went down a different path than I thought they were going to go,” he says. “I realized if they only knew what the real-live data, that I look at every day, says, they wouldn’t have gone that way. They would have gone the right way and gotten to a much better solution.”

“Seeing these brilliant ideas get misapplied because of a very reasonable assumption about how shoppers might shop, but happens not to be true in the empirical data--I realized we’ve got to find a way to have this not happen anymore.” 

The system, which is in beta right now, will launch next month at conference in Palo Alto. Says Vengroff: “We’ve got a significant new path that we think is really going to change things.”
E.B. Boyd is FastCompany.com’s Silicon Valley reporter. Follow me on Twitter, or email me.

via fastcompany.com

Posted via email from imrchen's posterous

比開發推薦系統更好的賺錢方法

上周末，資訊科技和財經類媒體紛紛報導，Paul Allen (微軟的共同創辦人，地球上最有錢的人之一），控告（起訴書）各大網路及資訊廠商侵犯了他所投資公司 Interval Research 所擁有的專利，被告苦主包括：Aol, Apple, eBay, Facebook, Google, Netflix, Office Depot, Officemax, Staples, Yahoo, and YouTube，有人說除了微軟之外，所有人都是他的標的。

依照 Wired 的報導，其中兩個專利和推薦系統有關，一個專利是根據消費者這正在閱覽的頁面來決定向用戶推薦物品，另一個則是根據讀者正在閱讀文章的內容和超連接，向讀者推薦新聞故事。

Forbes 的專欄作者 Lee Gomes 對這則新聞的反應很直接：

This is yet another example of the cynical use of the American legal system to extort money out of successful companies — in the name of protecting innovation and innovators. Shame on Paul Allen for being part of it.

顯然 Paul Allen 瞄準的對象口袋深度都很夠，這齣戲的劇本很簡單，一個有錢人，伸手到其他有錢人的口袋撈錢。我不知道保羅大哥，除了賺更多錢之外還有什麼其他不可告人的深意，層次不到，無法揣測超級有錢人的心意。不過這時候回頭看看 Wired 1999 年底的文章Think Tanked，滋味很特別。

Resys 諸君，有沒有人想去念個法律學位呢！？

Daniel Lemier's advice on How to Write Good Papers

Daniel Lemire 是我很敬佩的一位學者，他在推薦系統領域知名度相當高，而且是學術界投入部落格書寫的先行者之一。他的部落格並不局限於推薦系統議題，還涉及演算法和資訊科學理論的基礎問題，他還不時以自身的經驗提供出如何做研究、寫論文的建議，文章品質都很棒。昨日 Daniel Lemire 在 SlideShare 放上他針對研究生演講（talk?）如何撰寫論文的簡報，看了簡報，我只有一個想法，我實在是太混了。

Write good papers

View more presentations from Daniel Lemire.

Resys China 電子雜誌創刊號面世了

文棟兄和Resys群組裡諸位同學的心血結晶 - Resys China 電子雜誌創刊號 - 面世了，套用文棟在發刊介紹的一段話，現在網路閱讀越來越傾向於淺閱讀，希望這份人工精編的內容能給大家帶來一些思考和收穫。我相信會的！

Resys China 创刊号(按此連結可下載文件)

View more documents from gu wendong.

FANS AND EXPERTS OF RECOMMENDER SYSTEM IN TWITTER (by Geeksensor)

推薦系統高手 xlvector （用大陸的說法應該是大牛人）收集了三百萬則推特訊息，開發了在推特上尋找相關專家的系統 Geeksensor (原本叫做 twithunter)，並且用他收集的資料製作了一個標籤雲（Yes, Yet Another Cloud），不才在下敝人我，不巧也在這朵雲裡面，咳。

Francisco Martin #RecSys09 Industry Keynote Summary

推薦系統界的年度盛事之一 ACM Recommender System 2009 剛剛落幕（October 22-25），Strands 的創辦人 Francisco J Martin 在會中以業界人士身份受邀發表的演說 (Industry Ketnote) : Top 10 Lessons Learned Developing, Deploying, and Operating Real-World Recommender Systems 中有許多值得大家思考的內容，Neal Lathia (MobBlog) 將 Martin 博士的演說，以推特(Twitter)筆法，整理成十則簡明的摘要：

Lesson 1 – Make sure a recommender is really needed! Do you have lots of recommendable items? Many diverse customers?… also think Return-on-Investment… a more sophisticated recommender may not deliver a better ROI.

Lesson 2 – Make sure the recommendations make strategic sense. Is the best recommendation for the customer also the best for the business? What is the difference between a good and useful recommendation? Good recommendations .vs. useful recs; Obvious recommendations may not be useful; risky recs may deliver better long-term value (所有系統都是為企業需求而生，切記切記)

Lesson 3 - Choose the right partner! Select the right rec vendor vs hire some #recsys09 students. If you are a big company the best you can do is to organize a contest （為什麼不直接明說 Netflix ？LOL）

Lesson 4 – Forget about cold-start problems (!) …. just be creative. The internet has the data you need (somewhere…) （記住那句老話：We are limited only by our imigination）

Lesson 5 – Get the right balance between data and algorithms. 70% of the success of a #recsys is on the data, the other 30% on the algorithm （這個問題我們已經討論很多次了, Worry about the data before you worry about the algorithm）

Lesson 6 – Finding correlated items is easy but deciding what, how, and when to present to the user is hard… or don't just recommend for the sake of it. Remember user attention is a scarce and valuable resource. Use it wisely! … don't make a recommendations to a customer who is just about to pay for items at the checkout! User interface should get at least 50% of your attention.

Lesson 7 – Don't waste time computing nearest neighbours (use social connections)… just mine the social graph. Might miss useful connections??

Lesson 8 – Don't wait to scale (6, 7, 8, 9 顯然都是實務上的經驗談）

Lesson 9 – Choose the right feedback mechanism. Stars vs thumbs …. the YouTube problem. More research on implicit and other feedback mechanisms is needed. The perfect rating system is no rating system! … focus on the interface. Seems to me this is one of the gaps in current research… algorithms > data > interface

Lesson 10 – Measure Everything! … business control and analytics is a big opportunity here. （不僅要評量預測準不準，企業流程裡每個環節都要有評估機制，這是有真正創業、經營體驗的人的心得）

Keynote Takeaway – Think about application context; Focus on interface as much as algorithms; Be creative with start-up data. … the UI needs to get the lion’s share of the effort (50%) compared to algorithms (5%) , knowledge (20%), analytics (25%)

對於最後的 Takeaway，每個讀者或許都有自己的看法，畢竟要量化各因素在系統開發過程中的比重實在不容易，最後只能是被迫給出一組表達自己“經驗值”的數字。UI 的重要性當然毋庸置疑，只是 UI 為什麼是演算法的十倍？聰明的你（妳），想必有一套自己的想法！

#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 啊！

關於 user-based 和 item-based 算法的思考

半夜被地震閙醒，起床上網瞎晃，看到十一假期間xlvector兄仍然勤奮不輟思考 user-based 和 item-based 演算法對於輸出多様化的比較，大為佩服，特記錄于後：

(此刻鄙人凖備爬上床睡回龍覺)

前一段时间和wendong聊天，他提到userbased算法的结果多样性不如itembased算法。对此，我觉得有几个问题

1) 我们知道所谓多样性，是指推荐结果两两都不怎么相似，从而不同的相似度度量其实产生不同的多样性度量。

2)常用的相似度有两种，一种是基于content的，一种是基于collaborative filtering的，那么根据我的实验，在这两种相似度的度量下，userbased的结果多样性都好于itembased的算法

3)但我觉得还是存在一种相似度，而这个相似度对应的多样性在item-based的方法下比较好

不知道大家对这个问题怎么看，在实际系统中userbased和itembased谁能产生多样的结果？

Share and Enjoy:

Related posts:

1. my solutions of github contest – item based KNN
2. An improved item-based KNN predictor
3. Recommendation Systems: An Interview with Satnam Alag
4. 到目前为止的进度

via xlvector.cn

後記：
請參閱鄭昀今日的《基于Google Reader发展起来的个性化推荐系统之三大问题》，這纔是專業手筆。

Posted via web from imrchen's posterous

關於 Noise 的隨想與牢騷

看到推特(twitter.com)裡一段關於推薦系統的對話很有意思，所以順著這個思路「胡思亂想」了一下，於是順手寫下這些發散的不成系統又有些矛盾的東西：

首先，做系統的人始終要面對一個嚴峻課題，消費者做任何舉動都不需要向系統解釋他(她)的意圖，所以系統從數據裡找出的推論模型，只能有限度的猜測他(她)的下一個行動。人是會變的，許多論文裡總是提到消費者可能因為年齡(人生進入不同階段)而改變喜好的例子，日常生活裡我們也常看到因為消費者因為送禮(比如親戚朋友生日)而改變平常消費習慣的情形，至於因為有新的興趣或業務需求，消費內容與歷史紀錄大相逕庭更是司空見慣的事情。像這樣的消費方式，要怎樣才算(或不算)是噪訊(noise)呢？系統又從何判斷那些數據應該重視，那些應該忽略？

還有我們也常聽說把帳號借給朋友使用的情形，系統要怎樣才能判斷出如此 diversified 的消費習慣不是消費者人格分裂使然？ (至於所謂 diversity ，則是推薦系統主動推薦與平日消費習慣不同的品項，期望能造成意外之喜，則是另外一個課題了！)

當然若某種消費內容逐漸增多，演算法必然會有所反應，逐漸調整模型。這應是 @hendgm 所說，若次數多了就不再是噪訊的道理吧。

這篇純粹是灌水的牢騷文，請讀者諸君萬莫深究。

豆辦解決圖書版本問題的方法

不論是實體的零售店面，或是電子商務網站，都會遇到一個很複雜也很惱人的產品管理問題：item authority。

這個現象解釋起來很簡單，很多產品有不同的包裝版本（想像一下書籍的普及版、精裝本、典藏版, 等等），甚至同樣的版本，也可能在資料庫裡有兩筆以上資料（仍然以書籍做例子，想像一下同一本書的一刷、二刷），我們如何知道這些不同的商品其實都是同一個產品？Greg Linden 也曾經以 YouTube 為例，撰文 YouTube cries out for item authority 說明 item authority問題對服務提供者造成的困擾以及挑戰。

這對推薦系統的設計者，是個很「有趣」，也很艱鉅的挑戰！海峽兩岸間最大的書籍收藏網站-豆辦，當然也遇到這個問題，豆辦日誌昨日(2009/08/24)宣佈《豆瓣读书即将解决版本问题》，他們的解決方案，可以稱為用戶「自己動手，豐衣足食」吧：

豆瓣图书会将同一作品的不同版本归纳起来，展示在一个单独页面里。这个页面可以由书虫们来添加和编辑。如果你确切地知道06年上海译文出版社的《在路上》是01年漓江出版社的《在路上》的另一个版本，你可以添加；如果发现某个版本是指鹿为马，你可以报错。贡献者的信息会在版本页面被永久标记。

随着豆瓣数据库里的版本数据的完善，豆瓣猜的智商也将大大提高，再也不会推荐同一作品不同版本的书给你了；有些已经绝版不再出售的图书页面（比如 86年版的《傲慢与偏见》），会有最近新版的价格帮助购买（比如06年的《傲慢与偏见》有售）；对于多达十几种版本的图书，版本页面还会显示各自的收藏人数和评分，帮助大家比较版本的好坏。

推薦系統不是只能賣書

網友 xlvector (他是 Netflix Prize 中達成 10% 的兩個團隊之一 Ensemble 成員) 在 Resys 討論群組 提到一篇微軟研究院發表的研究報告 DebugAdvisor: A Recommender System for Debug，這篇報告的主題是如何使用推薦系統技術幫助程式設計師執行除錯工作，DebugAdviser 則是他們的成果。

因為我找到的 PDF 連結是壞的，還沒有機會看到全文，所以只能從摘要想像大概。不過，這的確是個有趣的想法，推薦系統不僅在 attention economy 大環境裡協助企業主攫取客戶注意力，還能協助程式設計師更好的完成他的工作(assignment)，看來 "We're limited only by our imagination" 這句話真是一點都沒錯。

DebugAdvisor: A Recommender System for Debugging

In large software development projects, when a programmer is assigned a bug to fix, she typically spends a lot of time searching (in an ad-hoc manner) for instances from the past where similar bugs have been debugged, analyzed and resolved. Systematic search tools that allow the programmer to express the context of the current bug, and search through diverse data repositories associated with large projects can greatly improve the productivity of debugging. This paper presents the design, implementation and experience from such a search tool called DebugAdvisor.

The context of a bug includes all the information a programmer has about the bug, including natural language text, textual rendering of core dumps, debugger output etc.

Our key insight is to allow the programmer to collate this entire context as a query to search for related information. Thus, DebugAdvisor allows the programmer to search using a fat query, which could be kilobytes of structured and unstructured data describing the contextual information for the current bug. Information retrieval in the presence of fat queries and variegated data repositories, all of which contain a mix of structured and unstructured data is a challenging problem. We present novel ideas to solve this problem.

We have deployed DebugAdvisor to over 100 users inside Microsoft. In addition to standard metrics such as precision and recall, we present extensive qualitative and quantitative feedback from our users.

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。

Netflix Progress Prize for 2008 宣布了

Netflix Prize 官方網站在12月10日宣布，今年（2008）的年度成就獎頒給 BellKor in BigChaos.

It is our great honor to announce the winner of the Netflix Progress Prize for 2008 as team BellKor in BigChaos for their verified just-in-time submission on Sept 30 at 21:17:40 UTC achieving a 9.44% improvement over Cinematch. We congratulate the team of Yehuda Koren, Robert Bell and Chris Volinsky of AT&T Research Labs combined with Andreas Töscher and Michael Jahrer of Commendo Research for their superb work integrating many significant techniques to achieve this result.

In accord with the Rules the team has prepared a system description consisting of two papers, which we both make public below. We will be awarding the Prize in a presentation at the Netflix offices in Los Gatos on December 17, 2008 at 4pm. Andreas Töscher and Michael Jahrer will present a public talk at that time about their Prize algorithm. We will post a video of that presentation via the Forum.

BellKor 團隊在網站上提供該團隊所發表與本次競賽有關的論文，供有興趣的讀者下載參考：

The BellKor 2008 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.

Factorization Meets the Neighborhood: a Multifaceted Collaborative Filtering Model. KDD 2008..

Recent Progress in Collaborative Filtering. RecSys 2008

Factor in the Neighbors: Scalable and Accurate Collaborative Filtering. submitted

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 .

Reading List: Diversity in Recommenders

Daniel Lemire 在上個月整理他認為與推薦系統的多元推薦輸出（diversity of recommendation lists）有關的文獻，有些讀者在留言裡也提出他們的建議。初步過濾之後，我把自己感興趣的文章，用 CiteULike 和 Refworks 的輸出功能，製作IEEE 格式書目如後，作為備忘查考之用：

[1] C. Clarke, M. Kolla, G. Cormack, O. Vechtomova, A. Ashkan, S. Büttcher and I. Mackinnon, "Novelty and diversity in information retrieval evaluation," in SIGIR '08: Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2008, pp. 659-666.

[2] D. Fleder and K. Hosanagar, "Blockbuster Culture's Next Rise or Fall: The Impact of Recommender Systems on Sales Diversity," SSRN eLibrary, 2008.

[3] D. Fleder and K. Hosanagar, "Recommender systems and their impact on sales diversity," in EC '07: Proceedings of the 8th ACM Conference on Electronic Commerce, 2007, pp. 192-199.

[4] L. Iaquinta, M. de Gemmis, P. Lops, G. Semeraro, M. Filannino and P. Molino, "Introducing Serendipity in a Content-Based Recommender System," Hybrid Intelligent Systems, 2008. HIS '08. Eighth International Conference on, pp. 168-173, 2008.

[5] Q. Le and A. Smola, "Direct Optimization of Ranking Measures," Apr 2007. [Online]. Available: http://arxiv.org/abs/0704.3359.

[6] D. Lemire, S. Downes and S. Paquet, "Diversity in open social networks," 2008.

[7] L. Mcginty and B. Smyth, "On the Role of Diversity in Conversational Recommender Systems," 2003.

[8] S. Mcnee, J. Riedl and J. Konstan, "Being accurate is not enough: How accuracy metrics have hurt recommender systems," in CHI '06: CHI '06 Extended Abstracts on Human Factors in Computing Systems, 2006, pp. 1097-1101.

[9] K. Swearingen and R. Sinha, "Beyond algorithms: An HCI perspective on recommender systems," 2001.

[10] Y. Xu and H. Yin, "Novelty and topicality in interactive information retrieval," J. Am. Soc. Inf. Sci. Technol., vol. 59, pp. 201-215, 2008.

[11] C. Zhai, W. Cohen and J. Lafferty, "Beyond independent relevance: Methods and evaluation metrics for subtopic retrieval," in SIGIR '03: Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, 2003, pp. 10-17.

[12] F. Zhang, "Research on Recommendation List Diversity of Recommender Systems," Management of e-Commerce and e-Government, 2008. ICMECG '08. International Conference on, pp. 72-76, 2008.

[13] M. Zhang and N. Hurley, "Avoiding monotony: Improving the diversity of recommendation lists," in RecSys '08: Proceedings of the 2008 ACM Conference on Recommender Systems, 2008, pp. 123-130.

如果需要下載這些文章的電子檔，請到筆者的 CiteULike 資料庫（tag: Diversity）查看論文下載位址的細節資料。

協同過濾（collaborative filtering）推薦系統的實作

最近讀了交通大學資管所劉敦仁教授2007年發表在 Expert Systems with Application 的文章[1]⁠ ，他將客戶終生價值（customer lifetime value， CLV）融入協同過濾（collaborative filtering，CF）推薦系統框架，以加權後的 RFM （Recency、Frequency、Monetary）模型，作為客戶分群的依據。

試著將更多實務界或商管領域的思維，整合至資料挖掘的實作，一直是我在思考的方向，這篇文章的思路對我並不陌生，因此我試著更深入理解他的做法。

在閱讀的過程裡，我覺得這篇文章在整理過去研究成果（related work）的部分，蠻有意思的，本文整理協同過濾的各種不同做法，以實作時應用的各種基礎演算法（例如：關聯法則、分群）為基礎的分類思路，而不是從商品與顧客的不同觀察視角（item-based .vs. user-based）出發。個人認為，這種切入角度，能夠幫助有意實作推薦系統的讀者，更快的理解推薦系統的組成架構，並且幫助他們更有效率的擬定工作計畫。

協同過濾的基本精神，在於數大就是美，資料愈多，系統的表現愈佳。協同過濾的實作精要之處，則在於如何從購物人潮中找出與特定顧客品味嗜好相近的同好，或是任意揀選一件商品，如何找出相似的品項。如何找出人與物的相似處，就取決於相似度（similarity）的計算方式了。歷來學者曾在文獻中建議使用的相似度公式，五花八門琳琅滿目，用族繁不及備載來形容一點也不誇張。

最常被人提及的計算方式包括 Euclidean Distance、 Pearson correlation coefficient、Jaccard coefficient、Manhatten distance、Cosine correlation coefficient 等等。許多學者在這些基礎上，設計了更複雜的計算方式，比如劉教授建議以商管領域常使用的 RFM （Recency、Frequency、Monetary）模型，計算客戶貢獻度（客戶對業者的價值）為基礎的計算方式，他還以此為基礎，建議更複雜的加權式 RFM （Weighted RFM）計算公式。簡而言之，更有用的相似度判斷方式，一直是學者努力的重點之一。

定義相似度之後，最重要的是怎麼應用相似度來建構推薦機制。根據劉教授的整理，有三大類計算方式（當然啦，這只是我個人的理解）：

k-nearest neighbor（kNN ）

這個方法是最直覺，也最容易理解的。指定一個消費者（或者指定商品，道理都是一樣的），利用相似度公式，計算出和這個消費者最相似的 k 個顧客。然後我們分析這些選出來的對象，找出他們購買過，但我們的主人翁還沒有購買的項目，這些就是要推薦給主人翁的商品。實務上，可能在計算上更複雜一點，不過這就是最基本的道理了。如果讀者可以參考 Programming Collective Intelligence （O'REILLY 出版）這本書的第二章和第八章，就更能體會這個方法的神髓了。

Clustering

這個方法在邏輯上也很單純，先將顧客依照某些條件分群，讓後再針對每一個群組作關聯法則的分析。我們依照關聯法則的分析，對這個群組裡的消費者，產生推薦清單（這個群裡其他人都買了，他還沒有買的商品就是推薦對象）。最簡單直覺的分群演算法，就是 k-mean clustering 了，但別忘了最重要的分群依據，就是前述一再強調的相似度計算方法。

Hybrid Approach

寸有所長，尺有所短。每一種方法，都有其優勢和缺點，因此學者嘗試將 content-based (CB) 和 collaborative filtering (CF)結合在一起，這就是所謂的融合解法 （hybrid approach）。將不同的計算方法結合在一起，說來簡單，作起來卻有很多變化。學者 Burke 有篇論文[2]⁠ - Hybrid Recommender Systems: Survey and Experiments，整理了做法，一共有 weighted、switching、mixed、feature combination、casade、feature augmentaion & meta-level 七種之多。依照劉教授的整理看來，他最重視 weighted 和 meta-level 兩種方法。

(圖表來源：Hybrid Recommender Systems: Survey and Experiments)

---

雖然我一直覺得，RFM 是不是能表達愛好與品味，還是個問號？不過本篇論文的整理功夫，的確值得稱道，配合 Programming Collective Intelligence 一起看，將論文裡的數學符號和實作連結起來，收獲特別多。

參考資料：

[1] Y. Shih and D. Liu, “Product recommendation approaches: Collaborative filtering via customer lifetime value and customer demands,” Expert Syst. Appl., vol. 35, 2008, pp. 350-360.

[2] R. Burke, “Hybrid Recommender Systems: Survey and Experiments,” User Modeling and User-Adapted Interaction, vol. 12, Nov. 2002, pp. 331-370.