解密：「猜你喜歡」是怎麼猜中你心思的？ @ 帆軟大師兄

如今，到網上購物的人已經習慣了收到系統為他們做出的個性化推薦。Netflix 會推薦你可能會喜歡看的視頻。TiVo 會自動把節目錄下來，如果你感興趣就可以看。Pandora 會通過預測我們想要聽什麼歌曲從而生成個性化的音樂流。
所有這些推薦結果都來自於各式各樣的推薦系統。它們依靠計算機演算法運行，根據顧客的瀏覽、搜索、下單和喜好，為顧客選擇他們可能會喜歡、有可能會購買的商品，從而為消費者服務。推薦系統的設計初衷是幫助在線零售商提高銷售額，現在這是一塊兒規模巨大且不斷增長的業務。與此同時，推薦系統的開發也已經從上世紀 90 年代中期只有幾十個人研究，發展到了今天擁有數百名研究人員，分別供職於各高校、大型在線零售商和數十家專註於這類系統的其他企業。
這些年來，推薦系統有了相當的進展。開始時它們還相對較為粗糙，往往對行為做出不準確的預測；但隨著更多的和不同類型的網站用戶數據變得可用，推薦系統得以將創新演算法應用於這些數據之上，它們迅速得到了改善。今天，推薦系統都是些極其複雜和精專的系統，常常看起來比你自己還要了解你。同時，推薦系統正在向零售網站以外的領域拓展：大學用它們來引導學生選課，行動電話公司靠它們來預測哪些用戶有可能轉投另一家供應商，會議主辦方也測試過用它們來分配論文給審稿專家。
我們兩人從推薦系統的早期開始便一直在開發和研究它們，最初是以學術研究者的身份，參與 GroupLens 計劃（GroupLens Project）。1992 年起，GroupLens 通過對美國興趣論壇網站 Usenet 討論區里的消息進行排序，將用戶指向他們可能會感興趣、但自己尚未發現的話題線索。幾年以後，我們成立了 Net Perceptions，這是一家推薦演算法公司，在網際網路第一次熱潮期間（1997 年 – 2000 年），一直處於業界領先地位。有鑒於此，雖然這些公司極少公開談論他們的推薦系統是如何運作的，我們的經驗使我們能夠深入了解亞馬遜和其他在線零售商幕後的情景。（在本文中，我們的分析是在觀察和推理的基礎上得出的，不包含任何內部消息）。
下面就是我們所看到的。
推薦演算法是怎麼「猜你喜歡」的？
你有沒有想過自己在亞馬遜眼中是什麼樣子？答案是：你是一個很大、很大的表格里一串很長的數字。這串數字描述了你所看過的每一樣東西，你點擊的每一個鏈接以及你在亞馬遜網站上買的每一件商品；表格里的其餘部分則代表了其他數百萬到亞馬遜購物的人。你每次登陸網站，你的數字就會發生改變；在此期間，你在網站上每動一下，這個數字就會跟著改變。這個信息又會反過來影響你在訪問的每個頁面上會看到什麼，還有你會從亞馬遜公司收到什麼郵件和優惠信息。
許多年來，推薦系統的開發者試過用各種各樣的方法來採集和解析所有這些數據。最近這段時間，多數人都選擇使用被稱為個性化協同推薦（Personalized Collaborative Recommender）的演算法。這也是亞馬遜、Netflix、Facebook 的好友推薦，以及一家英國流行音樂網站 Last.fm 的核心演算法。說它「個性化」，是因為這種演算法會追蹤用戶的每一個行為（如瀏覽過的頁面、訂單記錄和商品評分），以此進行推薦；它們可不是瞎貓碰上死耗子——全憑運氣。說它「協同」，則是因為這種演算法會根據許多其他的顧客也購買了這些商品或者對其顯示出好感，而將兩樣物品視為彼此關聯，它不是通過分析商品特徵或者關鍵詞來進行判斷的。
不同類型的個性化協同推薦系統最晚從 1992 年開始便已經出現。除了 GroupLens 計劃，另一項早期的推薦系統是 MIT 的 Ringo，它會根據用戶的音樂播放列表從而給用戶推薦其他他們有可能會喜歡的音樂。
User-User 演算法：計算用戶之間的相似度
GroupLens 和 Ringo 都使用了一種簡單的協同演算法，被稱為「用戶關聯」（user-user）的演算法。這種類型的演算法會計算一對用戶之間的「距離」，根據的是他們對同一物品打分的相似程度。舉例來說，如果吉姆和簡都給《電子世界爭霸戰》（Tron）這部電影打了 5 分，那麼他們之間的距離就是 0。如果吉姆給它的續集《創：戰紀》（Tron: Legacy ）這部電影打了 5 分，而簡只打了 3 分，那麼他們之間的距離就變大了。按照這樣的計算得出來品味相對「靠近」的用戶，我們把他們稱之為共有一個「鄰集」（neighborhood）。
但是，這種用戶關聯的策略效果並不是很好。首先，形成有意義的鄰集很難：很多用戶兩兩之間只有很少幾個共同評分，有的就完全沒有；而僅有的那幾個都打了分的項目呢，往往是票房大片，基本上人人都喜歡的那種。再來，由於用戶之間的距離可以變得很快，演算法必須當場就進行大部分的計算；而這可能會比一個在網站上這兒點點那兒戳戳的人下一個動作發出之前需要更久的時間。
Item-Item 演算法：計算物品之間的關聯
因此，大部分的推薦系統如今都依靠一種「物-物關聯」（item-item）的演算法，這種演算法計算的是兩本書、兩部電影或者兩個其他什麼東西之間的距離，依據的是給它們打過分的用戶的相似度。喜歡 Tom Clancy 書的人很可能會給 Clive Cussler 的作品打高分，因此 Clancy 和 Cussler 的書就共處一個鄰集。一對物品之間的距離可能是根據成百上千萬的用戶的評分計算得出，在一段時間裡往往保持相對穩定，因此推薦系統可以預先計算距離，並更快的生成推薦結果。亞馬遜和 Netflix 都曾公開表示過他們使用的是物-物關聯演算法的變種，但對細節都絕口不提。
用戶關聯演算法和物-物關聯演算法都有的一個問題，是用戶評分的不一致性。當給他們機會再評一次分時，用戶往往會對同一件物品給出不同的得分。品味在變、心情在變，印象也在變。MIT 在上世紀 90 年代進行的一項研究表明，在最初打分一年以後，用戶的評分會發生平均 1 分（滿分 7 分）的變動。研究人員們也在一直在嘗試不同的方法在模型中納入這一變量；比如說，如果用戶給某個商品了打一個分，但這個評分與推薦演算法所了解的關於這個人和這個商品的所有其他信息不相符，有的推薦演算法就會邀請用戶再次對這個商品進行評價。
降維演算法：把事物特徵一般化
不過，用戶關聯演算法和物-物關聯演算法還存在一個比一致性更大的問題：它們太死了。就是說，它們能發現都喜歡同一樣東西的人，但卻忽略了愛好非常相似的潛在用戶組合。比如說你喜歡莫奈的睡蓮。那麼，在這個法國印象派大師畫的 250 幅睡蓮中，你最喜歡哪一幅？在一群喜歡莫奈的人當中，完全可能每個人喜歡的睡蓮都不相同，而基本的演算法就有可能識別不出這些人都有著共同的愛好。
大約十年前，研究者們想出了一個辦法，通過一個叫降維（Dimensionality Reduction）的過程，把事物更一般化的表現出來。這種方法在計算量上比用戶關聯和物-物關聯演算法要密集得多，因此也就沒有那麼快的得到採用。但隨著計算機變更快更便宜，降維演算法也逐步取得了一些進展。
為了弄清降維演算法是怎麼工作的，我們來看看你愛吃的東西，以及如何把它跟其他一百萬人愛吃的東西做比較。你可以把這些信息用一個巨型矩陣表示出來，每一條豎線代表一樣食物，每個人愛吃什麼東西就自然形成了一行。在你的這一行上面或許會顯示你給了烤牛排 5 顆星、紅燒小排 4 星半、烤雞翅 2 顆星、凍豆腐卷 1 顆星、乳酪烤蘑菇 5 顆星、鹽水毛豆 4 顆星，等等。
然而，使用這個矩陣的推薦演算法並不關心你給哪種食物評了多少顆星。它想要了解的是你一般而言的喜好，這樣它可以將這個信息應用到更豐富多樣的食物上。比如說，基於你上面給出的信息，演算法可能會認為你喜歡牛肉、鹹的東西和烤制菜品，不喜歡雞肉和任何油炸的東西，不喜歡也不討厭蔬菜，依此類推。你愛吃的食物所擁有的特點或者說維度，它的數量和符合你要求的食物的數量比起來要小得多——至多可能 50 或 100。通過查對這些維度，推薦演算法可以迅速決定你是否會喜歡一種新的食物（比方說鹽焗排骨），方法就是把這種食物的各項維度（鹹的、牛肉做的、不是雞肉、不是炒的、不是蔬菜、不是烤的）同你的資料進行比對。這種更為一般性的呈現使得推薦演算法能準確的發現有著相似但不同喜好的用戶。而且，它大幅壓縮了矩陣的規模，使演算法變得更加高效。
這是一個很酷的解決方案。不過，你愛吃的食物的維度該上哪兒去找呢？肯定不是去問廚師。推薦系統會使用一種稱為奇異值分解的數學方法來計算維度。這種方法涉及到把最初的一個巨型矩陣分解為兩個「口味矩陣」——其中一個包含了所有的用戶和 100 項口味維度，另一個則包含了所有的食物和 100 項口味維度——再加上第三個矩陣，當乘以前面兩個矩陣中的任意一個時，會得到最初的那個矩陣（※此處已更改）。
不像上面例子中說的那樣，計算用的維度既不是描述性的，也一點兒都不直觀；它們是純抽象的值。這並沒有什麼，只要這些值最終生成準確的推薦結果就行了。這種方法的主要缺點是，創建矩陣所需要的時間會隨著客戶和產品數量的增多而飛速增長——創建一個擁有 2.5 億名客戶和 1000 萬種產品的矩陣，需要花上創建一個 25 萬名客戶和 1 萬種產品的矩陣 10 億倍那麼多的時間。而且這一過程還需要經常重複。一旦收到新的評分，矩陣就已經過時；在像亞馬遜這樣的公司，每一秒鐘都會收到新的評論。幸運的是，就算略微過時，矩陣仍然能以一個挺不錯的水平運作。研究人員們也已經在設計新的演算法，為奇異值分解提供可用的近似值並顯著縮短計算時間。