Facebook如何做到了解10億用戶？！

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

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

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

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

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

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

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

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

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

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

感謝徐川對本文的審校。