from：http://www.infoq.com/cn/news/2015/06/facebook-recommender-system

為了保證用戶體驗和使用效果，推薦系統(tǒng)中的機器學習算法一般都是針對完整的數(shù)據(jù)集進行的。然而，隨著推薦系統(tǒng)輸入數(shù)據(jù)量的飛速增長，傳統(tǒng)的集中式機器學習算法越來越難以滿足應用需求。因此，分布式機器學習算法被提出用來大規(guī)模數(shù)據(jù)集的分析。作為全球排名第一的社交網(wǎng)站，Facebook就需要利用分布式推薦系統(tǒng)來幫助用戶找到他們可能感興趣的頁面、組、事件或者游戲等。近日，Facebook就在其官網(wǎng)公布了其推薦系統(tǒng)的原理、性能及使用情況。

目前，Facebook中推薦系統(tǒng)所要面對的數(shù)據(jù)集包含了約1000億個評分、超過10億的用戶以及數(shù)百萬的物品。相比于著名的Netflix Prize?，Facebook的數(shù)據(jù)規(guī)模已經(jīng)超過了它兩個數(shù)據(jù)級。如何在在大數(shù)據(jù)規(guī)模情況下仍然保持良好性能已經(jīng)成為世界級的難題。為此， Facebook設計了一個全新的推薦系統(tǒng)。幸運的是，Facebook團隊之前已經(jīng)在使用一個分布式迭代和圖像處理平臺——Apache Giraph。因其能夠很好的支持大規(guī)模數(shù)據(jù)，Giraph就成為了Facebook推薦系統(tǒng)的基礎平臺。

在工作原理方面，Facebook推薦系統(tǒng)采用的是流行的協(xié)同過濾（Collaborative filtering，CF）技術。CF技術的基本思路就是根據(jù)相同人群所關注事物的評分來預測某個人對該事物的評分或喜愛程度。從數(shù)學角度而言，該問題就是根據(jù)用戶-物品的評分矩陣中已知的值來預測未知的值。其求解過程通常采用矩陣分解（Matrix Factorization, MF）方法。MF方法把用戶評分矩陣表達為用戶矩陣和物品的乘積，用這些矩陣相乘的結果R’來擬合原來的評分矩陣R，使得二者盡量接近。如果把R和R’之間的距離作為優(yōu)化目標,那么矩陣分解就變成了求最小值問題。

對大規(guī)模數(shù)據(jù)而言，求解過程將會十分耗時。為了降低時間和空間復雜度，一些從隨機特征向量開始的迭代式算法被提出。這些迭代式算法漸漸收斂，可以在合理的時間內(nèi)找到一個最優(yōu)解。隨機梯度下降（Stochastic Gradient Descent, SGD）算法就是其中之一，其已經(jīng)成功的用于多個問題的求解。SGD基本思路是以隨機方式遍歷訓練集中的數(shù)據(jù)，并給出每個已知評分的預測評分值。用戶和物品特征向量的調整就沿著評分誤差越來越小的方向迭代進行，直到誤差到達設計要求。因此，SGD方法可以不需要遍歷所有的樣本即可完成特征向量的求解。交替最小二乘法（Alternating Least Square, ALS）是另外一個迭代算法。其基本思路為交替固定用戶特征向量和物品特征向量的值，不斷的尋找局部最優(yōu)解直到滿足求解條件。

為了利用上述算法解決Facebook推薦系統(tǒng)的問題，原本Giraph中的標準方法就需要進行改變。之前，Giraph的標準方法是把用戶和物品都當作為圖中的頂點、已知的評分當作邊。那么，SGD或ALS的迭代過程就是遍歷圖中所有的邊，發(fā)送用戶和物品的特征向量并進行局部更新。該方法存在若干重大問題。首先，迭代過程會帶來巨大的網(wǎng)絡通信負載。由于迭代過程需要遍歷所有的邊，一次迭代所發(fā)送的數(shù)據(jù)量就為邊與特征向量個數(shù)的乘積。假設評分數(shù)為1000億、特征向量為100對，每次迭代的通信數(shù)據(jù)量就為80TB。其次，物品流行程度的不同會導致圖中節(jié)點度的分布不均勻。該問題可能會導致內(nèi)存不夠或者引起處理瓶頸。假設一個物品有1000億個評分、特征向量同樣為100對，該物品對應的一個點在一次迭代中就需要接收80GB的數(shù)據(jù)。最后，Giraph中并沒有完全按照公式中的要求實現(xiàn)SGD算法。真正實現(xiàn)中，每個點都是利用迭代開始時實際收到的特征向量進行工作，而并非全局最新的特征向量。

綜合以上可以看出，Giraph中最大的問題就在于每次迭代中都需要把更新信息發(fā)送到每一個頂點。為了解決這個問題，Facebook發(fā)明了一種利用work-to-work信息傳遞的高效、便捷方法。該方法把原有的圖劃分為了由若干work構成的一個圓。每個worker都包含了一個物品集合和若干用戶。在每一步，相鄰的worker沿順時針方法把包含物品更新的信息發(fā)送到下游的worker。這樣，每一步都只處理了各個worker內(nèi)部的評分，而經(jīng)過與worker個數(shù)相同的步驟后，所有的評分也全部都被處理。該方法實現(xiàn)了通信量與評分數(shù)無關，可以明顯減少圖中數(shù)據(jù)的通信量。而且，標準方法中節(jié)點度分布不均勻的問題也因為物品不再用頂點來表示而不復存在。為了進一步提高算法性能，Facebook把SGD和ALS兩個算法進行了揉合，提出了旋轉混合式求解方法。

接下來，Facebook在運行實際的A/B測試之間對推薦系統(tǒng)的性能進行了測量。首先，通過輸入一直的訓練集，推薦系統(tǒng)對算法的參數(shù)進行微調來提高預測精度。然后，系統(tǒng)針對測試集給出評分并與已知的結果進行比較。Facebook團隊從物品平均評分、前1/10/100物品的評分精度、所有測試物品的平均精度等來評估推薦系統(tǒng)。此外，均方根誤差（Root Mean Squared Error, RMSE）也被用來記錄單個誤差所帶來的影響。

此外，即使是采用了分布式計算方法，Facebook仍然不可能檢查每一個用戶/物品對的評分。團隊需要尋找更快的方法來獲得每個用戶排名前K的推薦物品，然后再利用推薦系統(tǒng)計算用戶對其的評分。其中一種可能的解決方案是采用ball tree數(shù)據(jù)結構來存儲物品向量。all tree結構可以實現(xiàn)搜索過程10-100倍的加速，使得物品推薦工作能夠在合理時間內(nèi)完成。另外一個能夠近似解決問題的方法是根據(jù)物品特征向量對物品進行分類。這樣，尋找推薦評分就劃分為尋找最推薦的物品群和在物品群中再提取評分最高的物品兩個過程。該方法在一定程度上會降低推薦系統(tǒng)的可信度，卻能夠加速計算過程。

最后，Facebook給出了一些實驗的結果。在2014年7月，Databricks公布了在Spark上實現(xiàn)ALS的性能結果。Facebook針對Amazon的數(shù)據(jù)集，基于Spark MLlib進行標準實驗，與自己的旋轉混合式方法的結果進行了比較。實驗結果表明，Facebook的系統(tǒng)比標準系統(tǒng)要快10倍左右。而且，前者可以輕松處理超過1000億個評分。

目前，該方法已經(jīng)用了Facebook的多個應用中，包括頁面或者組的推薦等。為了能夠減小系統(tǒng)負擔，Facebook只是把度超過100的頁面和組考慮為候選對象。而且，在初始迭代中，Facebook推薦系統(tǒng)把用戶喜歡的頁面/加入的組以及用戶不喜歡或者拒絕加入的組都作為輸入。此外，Facebook還利用基于ALS的算法，從用戶獲得間接的反饋。未來，Facebook會繼續(xù)對推薦系統(tǒng)進行改進，包括利用社交圖和用戶連接改善推薦集合、自動化參數(shù)調整以及嘗試比較好的劃分機器等。

---

感謝徐川對本文的審校。

給InfoQ中文站投稿或者參與內(nèi)容翻譯工作，請郵件至editors@cn.infoq.com。也歡迎大家通過新浪微博（@InfoQ，@丁曉昀），微信（微信號：InfoQChina）關注我們，并與我們的編輯和其他讀者朋友交流（歡迎加入InfoQ讀者交流群）。

總結

以上是生活随笔為你收集整理的Facebook如何向十亿人推荐东西的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。