Edwin Chen的Netflix推薦競賽技術總結

【編者按】本文由CSDN博主 @松子茶 翻譯自Quora的問題：「Is there any summary of top models for the Netflix prize?」答主位為Edwin Chen，詳細解析了Netflix演算法的構建。

我試著在這裡說些想法。矩陣分解技術和模型組合方法可能是與Netflix Prize有關最多被討論的演算法，但我們也使用了很多其他的洞見。

Normalization of Global Effects 全局效應的正常化

假設Alice給《盜夢空間》打4分。我們可認為這個評分由以下幾部分組成：

基準分（比如所有用戶給電影打的分的均值是3.1分）

Alice的專門效應（比如愛麗絲傾向於打出比平均值低的分，因此她的打分比我們正常所期望的要低0.5分）

盜夢空間的專門效應（比如盜夢空間是很棒的電影，因此它的分值比我們所希望的要高0.7分）

Alice和盜夢空間之間難以預測的交互效應，佔了餘下的分值（比如Alice真心喜歡盜夢空間，因為他的萊昂納多和腦科學的組合，因此又得到額外的0.7分）

換句話，我們把這4分分解成4 = [3.1 (基準分) – 0.5 (Alice的專門效應) + 0.7(盜夢空間的專門效應) + 0.7(特別的交互效應)因此與其讓我們的模型預測4分本身，我們也可以首先試著去除基準預測的效應（前三部分）然後預測這特別的0.7分（我想你也可以認為這就是一種簡單的boosting）

更一般的，基準預測的其他例子還有：

一個因素：允許Alice的打分（線性的）依賴於自從她開始打分的天數的（平方根）。（比如，你是否注意到隨著時間增加你變成更嚴厲的評論家）

一個因素：允許Alice的打分依賴於所有人可以給電影打分的天數（如果你是一個最先看到這部電影的人，可能因為你是一個資深粉絲然後真心興奮於在DVD上看到他，因此你會偏重於給他打高分）

一個因素：允許Alice的打分依賴於所有給盜夢空間打過分的人數。（可能愛麗絲是個討厭跟風的潮人）

一個因素：允許Alice的打分依賴於電影的全體打分。

加上一堆其他的。

事實上，對這些偏倚建模被證明相當重要：在他們給出最終解決的論文中，Bell和Koren寫道：在眾多有貢獻的新演算法中，我想強調一個——那些粗陋的基準預測（偏倚）捕捉到的數據中的主效應。雖然文獻大多集中在更複雜的演算法方面，但我們已經知道，對主效應的準確對待未來很可能是至少跟建模演算法一樣有效的突破點。ps: 為什麼消除這些偏見是有用的？我們有一個更具體的例子，假設你知道Bob和Alice喜歡同一類的電影，預測Bob對盜夢空間的評分，代之以簡單預測其像Alice一樣打4分，如果我們知道Bob通常比平均分高0.3分，我們就可以去掉Alice的偏倚然後加上Bob的：4 + 0.5 + 0.3 = 4.8

Neighborhood Models 鄰居模型

讓我們看看一些更複雜的模型。當提到上面的部分時，一個標準的方法就是用鄰居模型進行協同過濾。鄰居模型主要按照以下工作。為預測Alice對《鐵達尼號》的評分，有兩件事可以做。

基於item的方法：找出與鐵達尼號類似的Alice也有打分的item集合，然後把Alice在其上的評分求加權和。

基於user的方法：找出與Alice類似的也給鐵達尼號打分的user集合，然後求出他們對鐵達尼號的評分的均值。

簡單以基於item方法為例，我們主要的問題是

怎樣找到相似item的集合

怎樣確定這些相似item評分的加權值

標準的方法是使用一些相似性的度量（比如相關性和雅可比指標）來定義電影對之間的相似性，使用在此度量下K個最相似的電影（K可能是用交叉驗證選擇的），在計算加權平均數時用同樣的相似性度量。但這有很多問題

鄰居不是獨立的，所以用標準的相似性度量定義加權平均時造成信息重複計算。舉例而言，假設你詢問五個朋友今天晚上吃什麼。由於其中有三個人上周去了墨西哥因此厭煩了burritos（一種墨西哥玉米煎餅），所以他們強烈不建議去taqueria（一家專賣煎玉米卷的墨西哥快餐館）。與你去五個互相完全不認識的朋友相比，這五個朋友的建議有強烈的偏見。（與此可以類比的是，三部指環王電影都是哈利·波特的鄰居）

不同的電影應可能有不同數量的鄰居。有些電影可能僅僅使用一個鄰居就可以預測的很好（比如哈利波特2隻需單個的哈利波特1即可預測的很好），有些電影需要很多，還有些電影可能就沒有好的鄰居，這時你應該完全忽略鄰居演算法而讓其他打分模型作用到這些電影上去。

所以另一種途徑是如下：

你可以仍然使用相關性或者預先相似性來選擇相似的items

但並非使用相似性度量來確定插值權重的平均值計算，基本上用執行（稀疏）的線性回歸以找到權重，最小化item評分和他鄰居評分的線性組合的誤差平方和。（一個略微複雜的基於user的方法與基於item的鄰居模型也很有用）

Implicit Data 隱性數據

在鄰居模型之上，也可以讓隱性數據影響我們的預測。一個小的事實比如用戶給很多科幻電影打分而沒有給西部電影打分，暗示了用戶喜歡科幻多過牛仔。所以使用與鄰居打分模型相似的框架，我們可以對盜夢空間學習到與它電影鄰居相聯繫的偏移量。無論我們想怎麼預測Bob在盜夢空間上的打分，我們看一下Bob是否給盜夢空間的鄰居電影打分了。如果有，我們加上一個相關的偏移；如果沒有，我們不加（這樣，Bob的打分就被隱性懲罰了）

Matrix Factorization 矩陣分解

用於補充協同過濾的鄰居方法是矩陣分解方法。鑒於鄰居方法是非常局部的評分方法（如果你喜歡哈利波特1那麼你會喜歡哈利波特2），矩陣分解方法提供了更全局的觀點（我們知道你喜歡幻想類的電影而哈利波特有很強的幻想元素，所以你會喜歡哈利波特），將用戶和電影分解為隱變數的集合（可認為是類似幻想或者暴力的屬性）。事實上，矩陣分解方法大概是贏得Netflix Prize技術中最重要的部分。在2008寫就的論文中，Bell和Koren寫到：

ps: 似乎基於矩陣分解的模型是最精確（因此也最流行），在最近關於Netflix Prize的出版物和論壇討論都很明顯。我們完全同意，並想將這些矩陣分解模型加上被時間效應和二元觀點所需要提供的重要靈活性。雖然如此，已經在大多數文獻中占很主導的鄰居模型仍然會繼續流行，這根據他的實際特點——無需訓練就能夠處理新的用戶評分並提供推薦的直接解釋。

找到這些分解的典型方法是在（稀疏）評分矩陣上執行奇異值分解（使用隨機梯度下降並正則化factor的權重，可能是限制權重為正以得到某種非負矩陣分解）。（注意這裡的SVD與在線性代數里學到的標準的SVD有所不同，因為不是每一個用戶在每一步電影上都有評分因而評分矩陣有很多缺失值但我們並不像簡單地認為其為0）

在Netflix Prize中一些SVD啟發的方法包括

標準SVD：只要你已經把用戶和電影都表達成隱變數的向量，就可以點乘Alice的向量和盜夢空間的向量以得到其對應的預測評分。

漸近SVD模型：代之以用戶擁有自己觀點的隱變數向量，可以把用戶表達為一個由他打過分（或者提供了隱含的反饋）的items集合。所以Alice表達為她已經打過分的item的向量之和（可能是加權的），然後與鐵達尼號的隱變數點乘得到預測分值。從實用的觀點來看，這個模型有額外的優點即不需要用戶參數化，因此用這個方法一旦用戶產生反饋（可以僅僅是看過item而不必要評分）就可以產生推薦，而不需要重新訓練模型以包含用戶因素。

SVD++模型：同時用戶本身因素和items集合因素表達用戶是以上兩者的綜合。

Regression 回歸

一些回歸模型也被用來預測。我認為該模型相當標準，因此不在這裡花費太久。基本上，正如鄰居模型，我們可以採取以用戶為中心的方法和以電影為中心的方法來做回歸。

以用戶為中心：我們為每個用戶訓練回歸模型，使用所有用戶的評分數據作為數據集。響應變數是用戶對該電影的評分，預測變數是與該電影有關的屬性（可以由比如說PCA,MDS或SVD推出）

以電影為中心：類似的，可以對每部電影學習回歸，用所有對這部電影打分的客戶作為數據集。

Restricted Boltzmann Machines 有限波爾茲曼機

有限波爾茲曼機提供了另一種可使用的隱變數方法。如下論文是如何應用該方法到Netflix Prize上的描述（如果這論文難於閱讀，這裡有RBMs的簡介）.

Temporal Effects 當時效應

很多模型包含當時的效應。舉例而言，當描述以上提到的基準預測時，我們使用一些時間有關的預測允許用戶的評分（線性的）依賴於從他首次評分開始的時間和電影首次被評分的時間。我們也可以得到更細粒度的時間效應：把電影按時間分為幾個月的評分，允許電影在每個分類下改變偏倚。（例如大概是2006年5月，時代雜誌提名鐵達尼號為有史以來最佳電影，因此那段時間對該電影的收視評分衝刺增長）。在矩陣分解方法中，用戶因素也認為是時間相關的。也可以給最近的用戶行為更高權重。

Regularization 正則化

正則化也用於很多模型的學習以防止數據集上的過擬合。嶺回歸在分解模型中大量使用於對較大的權重做懲罰，Lasso回歸（儘管不那麼有效）也是有用的。很多其他的參數（例如基準預測，鄰居模型中的相似性權重和插值權重）也使用非常標準的shrinkage技術進行估計。

Ensemble Methods 組合方法

最後談談怎麼把所有不同的演算法組合以提供一個利用每個模型有點的單一評分(ps: 注意，就像上面提到的一樣，這些模型中很多都不是在原始的評分數據直接訓練的，而是在其他模型的剩餘數據上)。論文中給出最終解決的細節，冠軍敘述了怎樣使用GBDT模型組合超過500個模型；之前的解決是使用線性回歸來組合預測值。

簡要地說，GBDT按照順序對數據擬合了一系列的決策樹；每棵樹被要求預測前面的樹的誤差，並往往略有不同版本的數據。更長的類似的技術的描述，請參看問題.

因為GBDT內置可以引用不同的方法在數據的不同切片上，我們可以添加一些預測，幫助樹們使用有用的聚類：

每個用戶評分的電影數量

每部電影評分的用戶數量

用戶和電影的隱變數向量

有限玻爾茲曼機的隱藏單元

舉例而言，當Bell和Koren在使用更早的混合方法時發現一件事，即當電影或者用戶有少量評分時候RBMs更有用，而當電影或者用戶有大量評分時矩陣分解方法更有用。這是一張2007年競賽的混合規模效應的圖.

ps: 然而我們要強調的是，沒有必要用這麼大量的模型也能做好。下面這個圖顯示RMSE作為使用方法數量的函數。少於50種方法就可以取得我們贏得比賽的分值（RMSE=0.8712），用最好的三種方法可以使RMSE小於0.8800，已經可以進入前十名。甚至只使用最好的單個模型就可以讓我們以0.8890進入排行榜。這提示我們，為了贏得比賽使用大量模型是游泳的，但在實用上，優秀的系統可以只使用少數經過精心挑選的模型即可。

最後, 距我完成Netflix Prize的論文已經有一段時間了，記憶與筆記都較粗略，非常歡迎指正和建議。

推薦閱讀：