亞馬遜的推薦史，ItemCF的光輝史。n

原文鏈接：Two Decades of Recommender Systems at Amazon.com

近期，IEEE Internet Computing上發表了一篇名為《亞馬遜推薦系統二十年》的文章，提綱挈領地回顧了亞馬遜推薦系統二十年來的發展，而這二十年的起點，就是基於物品的協同過濾演算法，也就是ItemCF演算法的發明時間，而文章的作者，也正是當年ItemCF的發明人。作為靠ItemCF演算法養家糊口的從業人員，有必要學習一下「祖師爺」的訓導。

在翻譯的同時，譯者根據自己的從業經驗和個人想法，對本文進行了一些所謂的」批註「，以斜體的方式呈現在原文段落下方，希望能幫助讀者更好地理解本文，也希望提供給大家一些另外的視角，拋磚引玉地引發大家的思考和討論。

二十年以來[1]，亞馬遜一直致力於構建一個千人千面的商店。每個來到亞馬遜網站的人看到的都不一樣，因為網站針對他們的個人興趣做了個性化。就如同你走進一個商店，商店架子上的商品開始重新排布，將你可能需要的排在前面，你不太可能喜歡的排在後面。

基於你當前的場景和你過去的行為，亞馬遜的推薦系統從一個數以億計的商品庫中，為你挑選出少量你可能感興趣的物品。背後的演算法並不是什麼魔法，它只是將其他人已經發現的信息與你共享。一切都由演算法自動進行，在計算機的幫助下，人與人之間在隱性、匿名地互相幫助。

亞馬遜在1998年上線了基於物品的協同過濾演算法（下文簡稱ItemCF演算法），將推薦系統推向服務百萬級用戶和處理百萬級商品這樣一個前所未見的規模。自從我們2003年在IEEE Internet Computing上發表關於這一演算法的文章[2]之後，該演算法在互聯網上開始廣泛流傳，包括YouTube，Netflix和其他很多公司在內都在使用。該演算法的成功來源於以下幾個方面：

1. 簡單、可擴展。
2. 經常能給出令人驚喜和有用的推薦。
3. 可根據用戶的新信息立刻更新推薦。
4. 可解釋性強。

在我們2003年發表的文章中描述的內容這些年來曾經面對很多的挑戰，同時也經歷了極大的發展。在這裡，我們介紹ItemCF演算法的一些進展、改進和改良，同時也會闡述我們在協同過濾、推薦系統和個性化未來發展發展的一些看法。

演算法

譯者批：英文中常用 the xxx來表示xxx的地位，例如喬丹在98年總決賽中的絕殺被稱為the shot，本文這部分的標題叫做the algorithm，雖然作者本意並非如此，但譯者覺得用這種方式來表示ItemCF演算法在推薦系統中的地位也不為過。

如我們在2003年所描述的，ItemCF演算法是很直觀的。在90年代中期，協同過濾演算法主要還是基於用戶的，這意味著演算法的第一步是要通過搜索所有的用戶來計算某個用戶在興趣方面的相似用戶（例如擁有相似的購買模式），之後再看這些相似用戶看過哪些這個用戶沒有看過的東西。與之相反，我們的演算法第一步是計算每個物品的相關物品。這裡的「相關」可以表示多種含義，但在這裡，我們可以將其模糊地定義為「買了一個物品的人具有超乎尋常的可能性（unusually likely）會買另外一個」所以，對於每個物品i1，我們希望得到所有購買了i1的用戶會以超乎尋常的頻率一起購買的i2。

譯者批：其實UserCF也並不是一無是處，從計算形式上來講它和ItemCF是完全對等的。UserCF適用於用戶數的變化頻率小於物品數的變化頻率的場景，ItemCF則相反。當今的互聯網環境下確實是更適合ItemCF發揮，但未來說不好也會有適合UserCF的場景。

一旦這張相關物品的表構建好，我們可以通過一系列的查找來構建推薦系統。對於一個用戶當前場景下和歷史興趣中的每個部分，我們尋找到其相關物品，將它們結合起來得到用戶最可能感興趣的物品，過濾掉已經被看過或購買過的，剩下的就是就是待推薦的物品。

譯者批：短短几句話就把推薦系統架構核心點透，祖師爺果然功力深厚。

這個演算法相比於舊的基於用戶的協同過濾演算法具有很多優勢。最重要的是，主要的計算都是在離線發生的——相關物品的批量計算——而推薦的計算過程可以通過實時的一系列查找來完成。推薦結果質量高並且有用，尤其是數據量充足時。雖然二十年來各種新演算法在不斷被發明，在可觀測到的質量方面，ItemCF仍然極具競爭力。該演算法可無損地擴展到億級用戶和千萬級物品，而不需要抽樣或其他會影響推薦質量的手段。該演算法在用戶興趣更新時可以立刻隨之更新。最後，該演算法的結果可以用很直觀的方式來解釋，因為其來源就是用戶記得自己曾經買過的物品列表。

譯者批：ItemCF的優越性一方面來自於其演算法和架構設計的精妙，另一方面和使用了餘弦相似度這一」萬能公式「也有很大關係，有興趣的同學可參見我近期的一篇文章[3]，其中對餘弦相似度公式有些討論。

2003年：亞馬遜，Netflix，YouTube……

截至我們在2003年發表IEEE上的文章時，ItemCF已經在亞馬遜廣泛使用了。亞馬遜在主頁非常顯眼的位置放置了基於你購買歷史和瀏覽行為的個性化推薦模塊。搜索結果頁會給出和你搜索相關的推薦。購物車會給你推薦其他可以加入購物車的商品，可能會刺激你在最後一刻完成捆綁購買，或者對你已經打算購買的商品形成補充。在你訂單的尾部，會出現更多的推薦，給出建議你之後可以購買的東西。藉助電子郵件，列表頁，商品詳情頁以及其他頁面，很多亞馬遜上的頁面多少都會有些推薦模塊，開始形成一個千人千面的商店。

譯者批：在相關技術已經比較成熟的今天，仍然有很多網站大量依靠人工運營來決定網站上內容的排布，可見這種轉換中需要克服的阻力和慣性之大。所以我們不僅要佩服亞馬遜的技術能力，更要向其敢於革新的勇氣和決心看齊。此外，這種」全面推薦化「的產品思路的意義不只是提升技術逼格，更重要的是，它提供了一種規模化的、持續可依賴的效果提升路線。從此銷量或點擊的提升不再取決於銷售或運營人員的靈機一動，也不再受限於運營的人力，而是可以用演算法系統化持續取得提升。

很多其他公司和組織也在使用這個演算法。在2010年，YouTube宣城他們使用ItemCF來做視頻推薦[4]。很多開源工具和第三方廠商都使用了這個演算法，這使得該演算法在網上零售、旅行、新聞、廣告等行業中開始廣泛出現。在後面的幾年中，根據微軟研究院的估計，亞馬遜上大約30%的頁面瀏覽來自於推薦系統[5]。類似的，Netflix也在廣泛使用推薦系統，他們的首席產品官聲稱80%以上的電影觀看來自於推薦系統[6]，並宣稱Netflix推薦系統的價值每年高達十億美元，還要多。

譯者批：現在來看，各位老闆們應該思考的問題已經不再是」我的業務能否使用推薦「，而是」如何在我的業務中最大化地使用推薦「。尤其是直接服務於個人用戶的產品，可以說沒有幾個產品是推薦不能發揮作用的。

我們最初發明ItemCF的時候，亞馬遜還只是一個網上書店。從那時起，亞馬遜的銷售額增長了不止一百倍，並且從圖書擴展到以非出版物為主，從筆記本電腦到女裝。這樣的增長挑戰著很多演算法設計之初的假設，需要適應新的不斷改變的大環境。通過一些經驗，我們也找到了一些演算法的改進方法，來為很多推薦系統新的應用計算出更加相關的推薦。

譯者批：在機器學習技術逐漸興盛的這個時代，經典演算法的調優似乎在逐漸失去人們的重視，但從譯者自己的經驗來看，ItemCF演算法的調優帶來的效果提升空間非常大。在此還希望大家能夠」重視基礎，勿忘初心「。

定義」相關「物品

譯者批：這部分講到的是如何定義和評價相關性，讀起來相對繞一些，看不明白的同學可類比統計中的假設檢驗的思路來看：作者提出了一個假設（商品X和Y是否真正相關），然後構造了一個對應統計量，最後通過假設檢驗的方法來決定接受還是拒絕這個假設。

推薦的質量很大程度依賴於」相關「的含義。例如，當我們說買了X之後具有」超乎尋常的可能性「會購買Y的時候，究竟是什麼意思？當我們觀察到用戶同時購買了X和Y時，我們會好奇多少買了X的人會隨機購買到Y——如果X和Y不相關的話。一個推薦系統說到底是一個統計學的應用系統。用戶行為是包含噪音的，而我們面對的挑戰就是如何在隨機中發現規律。

要估計共同購買X和Y的用戶數，Nxy，的一種直觀的方法，是認為所有購買X的用戶都有同樣的概率P(Y)來購買Y，其中P(Y)=購買Y的人數/所有發生購買的用戶數，那麼購買X的用戶數乘以P(Y)就可以認為是Nxy的一個期望值，記為Exy。在我們2003年的文章中，以及在此之前的很多工作中，使用的都是類似的計算方法。

有趣的是，對於基於任意兩個物品X和Y，購買了X的用戶總要比整體用戶更可能購買Y。這是怎麼回事呢？想像一個超級剁手黨——一個購買了商店中所有物品的人。當我們在尋找購買了X的用戶時，這個用戶總是會被選中。類似的，一個購買了1000件商品的用戶總要比購買了20件商品的用戶的被選中幾率高50倍。所以從購買記錄中隨機採樣得到的結果在用戶維度上並不是均勻分布的，也就是說我們得到的是有偏的樣本。對於任意物品X，購買了X的用戶要比整體用戶購買量更多。

譯者批：這部分譯者花了一些時間理解，在這裡和大家分享一下。之所以會出現這種現象，原因在於，根據作者的邏輯，買了X的用戶中，很大概率會包含一些比普通人更能剁手的剁手黨——例如文中那個超級剁手黨就肯定會被選中，那麼購買X的用戶的購買量就被這些人拉高了，要高於整體用戶的平均購買量。這部分如果還有問題大家可在評論中討論。

這種用戶購買歷史的非均勻分布，意味著我們在計算有多少購買了X的用戶會隨機購買Y時不能忽略是誰買了X。我們發現將用戶建模成具有多次購買Y的機會會很有用[7]。例如，對於一個有20次購買的用戶，我們視其擁有20次獨立的購買Y的機會。

更正式的，對於一個購買了X的用戶c，我們可以將c購買Y的概率估計為1-(1-Py)^|c|，其中|c|代表用戶c的購買次數減去其對於X的購買次數，Py=|Y的購買次數|/|所有的購買次數|，代表任意一次購買是對於Y的購買的概率。之後，我們可以通過對所有購買X的用戶進行匯總，再加上二項式展開，來計算購買X的用戶中購買Y的用戶數的期望值Exy（見下圖）。

我們可以將Exy寫作Py的多項式，其係數只與X有關。實際中，Py通常都很小，所以可以用一個上界k來做近似。此外，Py和alpha_k(X)可以事先計算好，所以任意兩個X和Y的Exy只需要對事先計算好的值進行簡單組合即可到到一個近似值。

有了一個計算Exy的健壯方法之後，我們可以用其來計算觀測到的Nxy是否明顯高於或低於隨機。例如，Nxy-Exy可認為是非隨機共現的一個估計，而(Nxy-Exy)/Exy則給出了一個非隨機共現相對期望值的比例。這兩個例子都可認為是衡量有多少用戶會同時購買X和Y的相似度函數S(X,Y)。第一種方法，Nxy-Exy，會偏向於更流行的Y，例如第一本哈利波特，這會使得推薦結果看上去過於流行或無關。第二種方法，(Nxy-Exy)/Exy，會使得低銷量的物品很容易獲得高分數，使得推薦結果看著過於奇怪或隨機，大量低銷量物品的存在使得這個問題尤為嚴重。所以相關性分數需要在這兩者之間找到平衡點。基於(Nxy-Exy)/sqrt(Exy)的卡方檢驗就是這樣一個平衡的例子。

譯者批：第一種方法的問題較好理解。第二種方法會偏向低銷量商品的原因在於(Nxy-Exy)/Exy這個式子不夠穩定，尤其是分母較小時（銷量較低時），分子上的小幅度變化就會引起整個式子取值的較大波動。此外分母本身的取值也不穩定。

譯者批：活學活用概率統計的案例：將自己的問題構造成一個統計問題，剩下的交給數學就好了。如果我們能將遇到的度量問題都能成功地進行類似的抽象，很多工作就會簡單很多。

除此以外還有一些其他方法和參數可用來衡量相關性，以及從相關物品中做出推薦。我們的經驗是，沒有那個得分是在所有場景下都最優。最終來講，只有可觀測的質量是推薦系統真正的評價標準，推薦系統只有在人們認為其有用時才是有用的。

機器學習和ABTest可以學習到用戶真正的喜好，選擇推薦中使用的最優參數。我們不僅可以衡量哪些推薦是有效的，同時我們還可以收集到哪些推薦被用戶喜歡、點擊和購買，並將這些信息再次輸入到演算法中，進一步學習那些對用戶幫助最大 [8]。

例如，兼容性是一種重要的關係。我們可能會觀察到購買了某型號數碼相機的用戶會有很高的幾率會購買某特定型號的存庫卡，但這並不能保證這張存儲卡與這部相機兼容。用戶會因為很多與熱鬧而購買存儲卡，我們觀測到的相關性可能是隨機現象。確實，亞馬遜的商品庫中有幾十萬中存儲卡，這裡面很多都與這部相機隨機相關聯 。很多電商網站使用人工編輯的兼容性資料庫，而這是很昂貴並且容易出錯的，尤其是在有亞馬遜這個量級上。我們發現，只要有足夠的數據，再加上一個衡量相關性的健壯方法，兼容性可能從人們的行為中學習出來，錯誤信號逐漸消失，而正確的物品逐漸浮現。

有趣的是，我們發現相關物品的含義會從數據中自己浮現出來，完全依靠用戶自己。考慮用戶瀏覽的物品和購買的物品的不同。對於書籍、音樂以及其他低價商品，用戶傾向於瀏覽併購買類似的東西。但對於很多昂貴的物品來說，尤其是非出版物的物品，用戶瀏覽的和最終購買的會有很大的不同。例如，用戶可能會瀏覽很多電視機，但是最終只會購買一個。他們在瀏覽這台電視機的同時也在瀏覽的其他物品，通常會是其他電視機。而他們在購買這台電視機的同時購買的其他物品，則更可能是這台電視機的配套物品，例如一台藍光播放器或掛牆支架。

譯者批：這種」自我發現「的數據模式是演算法優於人工的另一重要原因，優於每個人固有的局限性，無法窮舉所有可能的匹配模式，而且還會存在滯後性，但是機器可以，演算法可以。只要有合適的度量方法和計算資源以及數據，所有有用的搭配模式都可以被發現，而且可以在模式剛剛出現時就將其找到。

時間的重要性

充分理解時間扮演的角色對於改進推薦系統質量有著重要的作用。例如，當計算相關物品時，兩個物品的相關性很大程度上依賴他們在時間間隔的長短。如果一個用戶在買了一本書的五個月之後又買了一本書，那這兩本書之間的相關性就要弱於兩本在同一天內被購買的書的相關性。時間的方向性也比較有用。例如，用戶會在買了相機之後買存儲卡，而不是反過來。這告訴我們不應該給購買了存儲卡的用戶推薦相機。有時物品的購買具有序列性，例如書籍、電影和電視劇，那麼推薦就應該給出你下一步想要做的東西。

亞馬遜的商品庫一直在變化。每天，數千的新商品到來，而很多其他商品則逐漸失效或沉寂。這種循環在某些類別上尤其明顯。例如，服飾具有明顯的季節性，消費電子更新換代很快。由於沒有足夠用戶行為數據來計算相關性，新物品會有一定的劣勢。這種問題被稱作冷啟動問題，通常需要藉助E/E的方式來給予新商品足夠的曝光機會。新聞和社交媒體這些易過期的物品在冷啟動方面尤其具有挑戰性，通常需要融合基於內容的演算法（使用題目，主題和文本等）和基於行為的演算法（使用購買，瀏覽和打分等）。

用戶維度的生命周期也存在冷啟動的問題。在對用戶興趣缺乏足夠了解的情況下如何給出推薦一直都是一個問題。何時利用有限的信息以及何時使用熱品來保證策略安全是一個不容易判斷正確的複雜轉換過程。

譯者批：冷啟動問題的解決不僅是個技術問題，也是個產品問題。例如可以考慮讓用戶選擇一些喜好，但也要考慮用戶是否接受這種形式。好的產品引導和設計可以幫助技術更好更快地解決冷啟動問題。

即使對於信息完備的用戶，正確地使用時間信息對於推薦質量也有著重要影響。隨著年齡的變化，之前的購買對於用戶當前的興趣的影響越來越小。更複雜的是，不同類型的物品的減弱效應還各不相同。例如，像」波濤洶湧的大海航行指南「這樣的購買記錄代表的通常是可持續的長期興趣。其他的例如洗碗機修理工具這樣的東西在周末的工程之後可能就不再相關了。甚至還有一些像撥浪鼓這樣的商品需要隨著時間不斷變化；四年之後，我們應該推薦的是平衡車而不是奶瓶。還有一些商品，例如書籍，通常只會購買一次；其他的，例如牙膏，經常是被以可預期的周期重複購買。

譯者批：文中提到的購買模式的問題，直到今天仍然沒有得到完全的解決。例如周期性購買的問題，據譯者所知，國內多家電商都做過類似嘗試，但都未取得預期的效果，其中的複雜度，遠比看上去的高。再例如大家經常吐槽的某些電商網站在你買了什麼之後立刻就再推一遍什麼，都是問題尚未完全解決的代表。

推薦的質量不僅取決於購買的時間，還取決於購買的內容。我們發現一本書的購買信息可以暴露很多用戶的興趣，讓我們能夠給出很多高度相關的推薦。但是非出版物類的購買，即使次數很多，也不能給我們提供用戶的什麼信息。我們能從一次訂書機的購買記錄中收集到什麼信息？基於一雙襪子的購買記錄我們能給出什麼樣驚奇而有深度的推薦？當前來說推薦膠帶切割機或者更多的內衣或許是有用的，但是長期來說會導致推薦很無聊。所以，我們需要開發一種技術，能夠識別哪些購買能提供有用的推薦而哪些應該被忽略。

譯者批：自動識別這兩種行為很具有挑戰性，但是在自動解決之前，人為地通過策略進行緩解也是不錯的選擇。

最後，推薦系統中多樣性的重要性也是眾所周知的；有時相比一個範圍很窄的推薦列表，給出一些更多樣的相關物品會更好。亞馬遜豐富的商品庫以及多樣的商品類型，相比例如書店這樣的垂類電商，提出了多樣性方面更大的挑戰。例如，給一個重度閱讀愛好者推薦更多的書可能會帶動更多的銷量，但是從長期來看，讓用戶發現他們之前從未考慮過的產品線中的新商品可能是更有用的。意圖的明確性也是多樣性中的一個因素。當用戶很明顯是在尋找某個具體的商品時，推薦系統應該收窄範圍幫助用戶快速找到所需。但是當意圖並不明確或確定時，探索性和新奇性應該是推薦的目標。想要找到推薦系統中多樣性的正確平衡點，不僅需要實驗，更需要一顆想要從長期進行優化的心。

譯者批：這一部分中，作者集中提出了一些推薦系統的核心挑戰，其中很多直到現在也沒有完全得到解決。而這其中又不全是技術問題，還涉及很多產品設計和利益權衡，例如推薦多樣性和E/E問題，其產品決策層面的難度要大於技術實現的難度。但另一方面，其中一些問題都可以通過譯者上面提到的對ItemCF演算法的優化來解決或緩解。

未來：推薦無處不在

推薦的未來將通向何方？我們認為未來的機會要比過去的機會更多。我們可以想像一種智能交互，使得購物就像對話一樣簡單。

這種方式超越了當前基於搜索和瀏覽的模式。相反，探索過程應該像和一位朋友聊天一樣，這位朋友了解你，知道你的愛好，陪伴你的每一步，知道你的需求。

這是一種智能無處不在的願景。每一次交互都會反映你是誰，你喜歡什麼，同時幫助你找到其他和你類似的人已經發現的東西。當你看到和你明顯不相關的東西時你會感到空虛和悲哀：難道你現在還不了解我嗎？

要想達成這樣的 願景需要從新的角度思考推薦。不應該有推薦特徵和推薦引擎。相反，讀懂你和其他人，以及當前擁有的資源應該是每次交互都應該擁有的。

推薦和個性化生存在數據的海洋中，我們在穿梭世界的過程中創造了這些數據，包括我們找到的，發現的和喜愛的。我們堅信未來的推薦系統將繼續構建在充分利用人類集體智慧的智能計算機演算法的基礎上。未來將繼續是計算機幫助人類互助。

大概二十年前，亞馬遜在百萬級商品上構建了推薦系統，來幫助百萬級用戶，幫助人們發現自己無法找到的東西。從那時起，原始的ItemCF演算法傳播到了互聯網的大部分角落，幫助人們尋找可觀看的視頻，可閱讀的資訊，同時也被其他演算法和技術挑戰著，也被改造以提供更好的多樣性、實時性、時間敏感性以及時序性等很多其他問題。由於其簡便性、可擴展性、可解釋性、可調性以及相對高質量的推薦，ItemCF演算法在當今仍然是最為流行的推薦演算法之一。

但是該領域仍然充滿機會。千人千面的用戶體驗仍然是一個沒有人能夠完全做到的願景。仍然有很多機會可以給系統的每個部分添加智能和個性化，製造一個懂你喜好，懂其他人喜好，同時也知道你有什麼選擇的老友般的體驗。推薦即發現，通過幫助你發現來提供驚喜和快樂。每種交互都應該是推薦。

譯者批：作者在這一部分描繪出的推薦的未來，譯者表示相當贊同，也正是這宏偉的願景，每天早上叫醒譯者去上班（老闆看這裡！）。經過多年的發展，推薦系統已經走過了童年和少年，進入了年盛力強的青年期，也通過這些年的工作向世界證明了推薦系統的價值，相信在未來，推薦系統核相關技術會繼續走出電商，佔領整個互聯網。

1. G.D. Linden, J.A. Jacobi, and E.A. Benson, Collaborative Recommendations Using Item-to-Item Similarity Mappings, US Patent 6,266,649, to Amazon.com, Patent and Trademark Office, 2001 (filed 1998).

2. G. Linden, B. Smith, and J. York, 「http://Amazon.com Recommendations: Item-to-Item Collaborative Filtering,」 IEEE Internet Computing, vol. 7, no. 1, 2003, pp. 76–80.

3. 可見《自然語言處理技術在推薦系統中的應用》（自然語言處理技術（NLP）在推薦系統中的應用 - 極客頭條 - CSDN.NET） 的」統一度量衡：權重計算和向量空間模型「部分。

4. J. Davidson et al., 「The YouTube Video Recommendation System,」 Proc. 4th ACM Conf. Recommender Systems, 2010, pp. 293–296.

5. A. Sharma, J.M. Hofman, D.J. Watts, 「Estimating the Causal Impact of Recommendation Systems from Observational Data,」 Proc. 16th ACM Conf. Economics and Computation, 2015, pp. 453–470.

6. C.A. Gomez-Uribe and N. Hunt, 「The Netflix Recommender System: Algorithms, # Business |Value, and Innovation,」 ACM Trans. Management Information Systems, vol. 6, no. 4, 2016, pp. 1–19.

7. B. Smith, R. Whitman, and G. Chanda, System for Detecting Probabilistic Associations between Items, US Patent 8,239,287, to Amazon.com, Patent and Trademark Office, 2012.

8. K. Chakrabarti and B. Smith, Method and System for Associating Feedback with Recommendation Rules, US Patent 8,090,621, to Amazon.com, Patent and Trademark Office, 2012.

推薦閱讀：