Friday, January 4, 2008

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

1 comment:

  1. Hi! 您好! 我是明新科技大學的學生,讀了您寫的推薦系統的分類(2008 Edition),發現正是我現在正在做的專題內容,您的內容都寫的不錯,我也讀了英文版的,而我們也做了類似的網站,但功能都很簡單,可以引用妳的文章嗎? 我會注名出處。不知還有什麼補充的料資,建議我們可以參考,只是個校內專題發表會,有關畢業專題的,希望不會因此為您帶來很大的困擾! 如果不便,請通知我。 敬謝 劉昌飛Romen_liu@hotmail.com

    ReplyDelete

如果我的心是一朵蓮花

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