Facebook如何向十億人推薦東西 · 架構師（2015年7月）

作者張天雷為了保證用戶體驗和使用效果，推薦系統中的機器學習算法一般都是針對完整的數據集進行的。然而，隨著推薦系統輸入數據量的飛速增長，傳統的集中式機器學習算法越來越難以滿足應用需求。因此，分布式機器學習算法被提出用來大規模數據集的分析。作為全球排名第一的社交網站，Facebook就需要利用分布式推薦系統來幫助用戶找到他們可能感興趣的頁面、組、事件或者游戲等。近日，[Facebook就在其官網公布了其推薦系統的原理、性能及使用情況](https://code.facebook.com/posts/861999383875667/recommending-items-to-more-than-a-billion-people/)。目前，Facebook中推薦系統所要面對的數據集包含了約1000億個評分、超過10億的用戶以及數百萬的物品。相比于著名的[Netflix Prize](http://www.netflixprize.com/) ，Facebook的數據規模已經超過了它兩個數據級。如何在在大數據規模情況下仍然保持良好性能已經成為世界級的難題。為此， Facebook設計了一個全新的推薦系統。幸運的是，Facebook團隊之前已經在使用一個分布式迭代和圖像處理平臺——[Apache Giraph](http://giraph.apache.org/)。因其能夠很好的支持大規模數據，Giraph就成為了Facebook推薦系統的基礎平臺。在工作原理方面，Facebook推薦系統采用的是流行的協同過濾（Collaborative filtering，CF）技術。CF技術的基本思路就是根據相同人群所關注事物的評分來預測某個人對該事物的評分或喜愛程度。從數學角度而言，該問題就是根據用戶-物品的評分矩陣中已知的值來預測未知的值。其求解過程通常采用矩陣分解（[Matrix Factorization](http://en.wikipedia.org/wiki/Matrix_decomposition), MF）方法。MF方法把用戶評分矩陣表達為用戶矩陣和物品的乘積，用這些矩陣相乘的結果R’來擬合原來的評分矩陣R，使得二者盡量接近。如果把R和R’之間的距離作為優化目標,那么矩陣分解就變成了求最小值問題。對大規模數據而言，求解過程將會十分耗時。為了降低時間和空間復雜度，一些從隨機特征向量開始的迭代式算法被提出。這些迭代式算法漸漸收斂，可以在合理的時間內找到一個最優解。隨機梯度下降（[Stochastic Gradient Descent](http://en.wikipedia.org/wiki/Stochastic_gradient_descent), SGD）算法就是其中之一，其已經成功的用于多個問題的求解。SGD基本思路是以隨機方式遍歷訓練集中的數據，并給出每個已知評分的預測評分值。用戶和物品特征向量的調整就沿著評分誤差越來越小的方向迭代進行，直到誤差到達設計要求。因此，SGD方法可以不需要遍歷所有的樣本即可完成特征向量的求解。交替最小二乘法（[Alternating Least Square](http://bugra.github.io/work/notes/2014-04-19/alternating-least-squares-method-for-collaborative-filtering/), ALS）是另外一個迭代算法。其基本思路為交替固定用戶特征向量和物品特征向量的值，不斷的尋找局部最優解直到滿足求解條件。為了利用上述算法解決Facebook推薦系統的問題，原本Giraph中的標準方法就需要進行改變。之前，Giraph的標準方法是把用戶和物品都當作為圖中的頂點、已知的評分當作邊。那么，SGD或ALS的迭代過程就是遍歷圖中所有的邊，發送用戶和物品的特征向量并進行局部更新。該方法存在若干重大問題。首先，迭代過程會帶來巨大的網絡通信負載。由于迭代過程需要遍歷所有的邊，一次迭代所發送的數據量就為邊與特征向量個數的乘積。假設評分數為1000億、特征向量為100對，每次迭代的通信數據量就為80TB。其次，物品流行程度的不同會導致圖中節點度的分布不均勻。該問題可能會導致內存不夠或者引起處理瓶頸。假設一個物品有1000億個評分、特征向量同樣為100對，該物品對應的一個點在一次迭代中就需要接收80GB的數據。最后，Giraph中并沒有完全按照公式中的要求實現SGD算法。真正實現中，每個點都是利用迭代開始時實際收到的特征向量進行工作，而并非全局最新的特征向量。綜合以上可以看出，Giraph中最大的問題就在于每次迭代中都需要把更新信息發送到每一個頂點。為了解決這個問題，Facebook發明了一種利用work-to-work信息傳遞的高效、便捷方法。該方法把原有的圖劃分為了由若干work構成的一個圓。每個worker都包含了一個物品集合和若干用戶。在每一步，相鄰的worker沿順時針方法把包含物品更新的信息發送到下游的worker。這樣，每一步都只處理了各個worker內部的評分，而經過與worker個數相同的步驟后，所有的評分也全部都被處理。該方法實現了通信量與評分數無關，可以明顯減少圖中數據的通信量。而且，標準方法中節點度分布不均勻的問題也因為物品不再用頂點來表示而不復存在。為了進一步提高算法性能，Facebook把SGD和ALS兩個算法進行了揉合，提出了旋轉混合式求解方法。接下來，Facebook在運行實際的A/B測試之間對推薦系統的性能進行了測量。首先，通過輸入一直的訓練集，推薦系統對算法的參數進行微調來提高預測精度。然后，系統針對測試集給出評分并與已知的結果進行比較。Facebook團隊從物品平均評分、前1/10/100物品的評分精度、所有測試物品的平均精度等來評估推薦系統。此外，均方根誤差（Root Mean Squared Error, RMSE）也被用來記錄單個誤差所帶來的影響。此外，即使是采用了分布式計算方法，Facebook仍然不可能檢查每一個用戶/物品對的評分。團隊需要尋找更快的方法來獲得每個用戶排名前K的推薦物品，然后再利用推薦系統計算用戶對其的評分。其中一種可能的解決方案是采用[ball tree](http://en.wikipedia.org/wiki/Ball_tree)數據結構來存儲物品向量。all tree結構可以實現搜索過程10-100倍的加速，使得物品推薦工作能夠在合理時間內完成。另外一個能夠近似解決問題的方法是根據物品特征向量對物品進行分類。這樣，尋找推薦評分就劃分為尋找最推薦的物品群和在物品群中再提取評分最高的物品兩個過程。該方法在一定程度上會降低推薦系統的可信度，卻能夠加速計算過程。最后，Facebook給出了一些實驗的結果。在2014年7月，[Databricks公布了在Spark上實現ALS的性能結果](https://databricks.com/blog/2014/07/23/scalable-collaborative-filtering-with-spark-mllib.html)。Facebook[針對Amazon的數據集](https://snap.stanford.edu/data/web-Amazon.html)，基于[Spark MLlib](https://spark.apache.org/mllib/)進行標準實驗，與自己的旋轉混合式方法的結果進行了比較。實驗結果表明，Facebook的系統比標準系統要快10倍左右。而且，前者可以輕松處理超過1000億個評分。目前，該方法已經用了Facebook的多個應用中，包括頁面或者組的推薦等。為了能夠減小系統負擔，Facebook只是把度超過100的頁面和組考慮為候選對象。而且，在初始迭代中，Facebook推薦系統把用戶喜歡的頁面/加入的組以及用戶不喜歡或者拒絕加入的組都作為輸入。此外，Facebook還利用基于ALS的算法，從用戶獲得間接的反饋。未來，Facebook會繼續對推薦系統進行改進，包括利用社交圖和用戶連接改善推薦集合、自動化參數調整以及嘗試比較好的劃分機器等。