08.13 Facebook 推薦算法

網絡上數據的增長使得在完整數據集上使用許多機器學習算法變得更加困難。特別是對於個性化問題，數據採樣通常不是一種選擇，因此有必要創新分佈式算法設計，以便我們可以擴展到這些不斷增長的數據集。

協同過濾（CF）是重要的應用領域之一。 CF是一種推薦的系統技術，可幫助人們發現與其最相關的項目。在Facebook上，這可能包括頁面，群組，活動，遊戲等。 CF基於這樣的想法，即最佳推薦來自具有相似品味的人。換句話說，它使用志同道合的人的歷史項目評級來預測某人如何評估項目。

CF和Facebook規模

Facebook的CF平均數據集擁有1000億個評級，超過10億用戶和數百萬個項目。相比之下，著名的Netflix Prize推薦競賽包含一個擁有1億個評級，480,000個用戶和17,770個電影（項目）的大型工業數據集。從那以後，該領域有了更多的發展，但我們讀到的最大數量至少比我們處理的數字小兩個數量級。

我們面臨的挑戰是設計一個分佈式算法，該算法將擴展到這些海量數據集以及如何克服由於我們數據的某些屬性引起的問題（例如偏斜的項目程度分佈，或隱式參與信號而不是評級）。

正如我們將在下面討論的那樣，現有解決方案中使用的方法無法有效處理我們的數據大小。簡而言之，我們需要一個新的解決方案。我們已經寫過Apache Giraph，一個用於分佈式迭代和圖形處理的強大平臺，以及我們為滿足我們的需求所做的工作。我們還編寫了一個用於圖形分區的開發應用程序。 Giraph在大量數據集上運行良好，易於擴展，我們在開發高性能應用程序方面擁有豐富的經驗。因此，Giraph是我們解決這個問題的明智選擇。

矩陣分解

CF的常用方法是通過矩陣分解，其中我們將問題視為具有一組用戶和一組項，以及表示已知用戶對項進行評級的非常稀疏的矩陣。我們想要預測此矩陣中的缺失值。為此，我們將每個用戶和每個項目表示為潛在特徵的向量，使得這些向量的點積與項目的已知用戶評級緊密匹配。期望對項目的未知用戶評級也可以通過相應特徵向量的點積來近似。我們想要最小化的最簡單的目標函數形式是：

這裡，r是已知的用戶到項目評級，x和y是我們試圖找到的用戶和項目特徵向量。由於存在許多自由參數，我們需要正則化部分來防止過度擬合和數值問題，其中γ是正則化因子。

目前在合理的時間內找到上述公式的最優解是不可行的，但是存在從隨機特徵向量開始並逐漸改進解的迭代方法。經過一些迭代後，特徵向量的變化變得非常小，並且達到了收斂。有兩種常用的迭代方法。

隨機梯度下降優化

隨機梯度下降（SGD）優化在許多其他問題中成功實施。該算法以隨機順序循環遍歷訓練數據中的所有評級，並且對於每個已知評級r，它進行預測r *（基於向量x和y的點積）並計算預測誤差e。然後我們通過在梯度的相反方向上移動它們來修改x和y，從而為x和y的每個特徵產生某些更新公式。

交替最小二乘

當有兩個因變量（在我們的例子中，向量x和y）時，交替最小二乘（ALS）是與非線性迴歸模型一起使用的另一種方法。該算法固定一個參數（用戶向量x），同時通過最小化二次形式最優地求解另一個（項向量y）。該算法在固定用戶向量和更新項目向量之間交替，並固定項目向量和更新用戶向量，直到滿足收斂標準。

標準方法和問題

為了以分佈式方式有效地解決上述公式，我們首先研究了與Giraph設計相似的系統如何做到（使用消息傳遞而不是map / reduce）。標準方法對應於將用戶和項目都作為圖形的頂點，邊緣表示已知的評級。然後，SGD / ALS的迭代將在圖的所有邊緣發送用戶和/或項目特徵向量並進行本地更新。

此解決方案存在一些問題：

大量的網絡流量：這是所有

分佈式矩陣分解算法的主要瓶頸。由於我們在圖形的每個邊緣發送一個特徵向量，因此在一次迭代中通過線路發送的數據量與#Ratings * #Features成比例（在我們使用的文本中此處和後面的＃作為'number of'的表示法） 。對於1000億次評級和100次雙重功能，每次迭代可產生80 TB的網絡流量。在這裡，我們假設用戶和項目是隨機分佈的，我們忽略了一些評級可以生活在同一個工人身上的事實（平均而言，這應該乘以因子1 - （1 / #Workers））。請注意，由於具有較大度數的項目，智能分區無法大量減少網絡流量，並且無法解決我們的問題。

我們的數據集中的一些項目非常受歡迎，因此項目度分佈高度傾斜：這可能導致內存問題 - 每個項目都接收度* #Features數據量。例如，如果一個項目具有1億個已知評級並且使用了100個雙重功能，則僅此項目將接收80 GB的數據。大學位項目也會導致處理瓶頸（因為每個頂點都是原子處理的），每個人都會等待幾個最大程度的項目完成。

這並沒有完全在原始公式中實現SGD：每個頂點都使用它在迭代開始時收到的特徵向量，而不是它們的最新版本。例如，假設項目A對用戶B和C有評級。在順序解決方案中，我們首先更新A和B，獲得A'和B'，然後更新A'和C.使用此解決方案，B和C將使用A進行更新，A是迭代開始時項目的特徵向量。 （這是通過一些無鎖並行執行算法實現的，可以減慢收斂速度。）

我們的解決方案 - 旋轉混合方法

主要問題是在每次迭代中發送所有更新，因此我們需要一種新技術來組合這些更新併發送更少的數據。首先，我們嘗試利用聚合器並使用它們來分發項目數據，但我們嘗試用於組合項目特徵向量的部分更新的公式都沒有奏效。

我們最終提出了一種方法，要求我們通過工人到工作人員的消息傳遞來擴展Giraph框架。用戶仍然是圖表的頂點，但項目在#Workers不相交的部分中分區，每個部分都存儲在其中一個工作人員的全局數據中。我們將所有工人放在一個圓圈中，並在每次超級步驟後按順時針方向旋轉項目，方法是將包含每個工人的項目的工人到工人的消息發送到該行中的下一個工作人員。

因此，在每個超級步驟中，我們處理工作人員當前項目的工作者用戶評級的一部分，因此在#Workers超越之後處理所有評級。讓我們分析以前解決方案遇到的問題：

網絡流量數量：對於SGD，在一次迭代中通過線路發送的數據量與#Items * #Features * #Workers成比例，並且它不再取決於已知級別的數量。對於1000萬個項目，100個雙功能和50個工作人員，這總共帶來了400 GB，比標準方法小20倍。因此，對於#Workers <= #Ratings / #Items，旋轉方法表現更好，即如果工人數量小於平均項目程度。在我們使用的所有數據集中，我們忽略較小的項目，因為它們不代表好的建議，可能只是噪音，因此平均項目非常大。我們將在下面討論ALS。

傾斜項目學位：這不再是問題 - 用戶頂點是唯一正在處理的項目，項目從不保存有關其用戶評級的信息。

SGD計算：在順序解決方案中這是相同的，因為在任何時間點只有一個版本的特徵向量，而不是將它們的副本發送給許多工作者並基於此進行更新。

使用ALS進行計算比使用SGD更棘手，因為我們需要所有項目/用戶特徵向量才能更新用戶/項目。事實上，ALS的更新方式是我們正在求解A * X = B類型的矩陣方程，其中A是#Features x #Features矩陣，B是1 x #Features向量，A和B是/用戶計算的項目特徵向量。形成項目/用戶的所有已知評級。因此，在更新項目時，我們可以旋轉A和B而不是僅旋轉它們的特徵向量，在每個#Workers超級步驟中更新它們，最後計算新的特徵向量。這將增加#Items *＃Features2 * #Workers的網絡流量。根據所有數據維度之間的比率，這比某些項目的標準方法更好，但對某些項目則不然。

這就是為什麼我們的旋轉方法和標準方法的融合提供了一個很好的解決方案。通過在某種程度上查看項目，在標準方法中，與之關聯的網絡流量是度* #Features，並且使用我們的輪換方法，它是#Workers *＃Features2。我們仍然會使用標準方法更新

為了求解矩陣方程A * X = B，我們需要找到逆A-1。我們使用開源庫JBLAS，它具有最有效的矩陣逆實現。

由於SGD和ALS共享相同的優化公式，因此也可以組合這些算法。 ALS比SGD計算複雜。我們提供了一個選項來組合一些SGD迭代，然後是ALS的單次迭代。對於某些數據集，這已被證明對離線度量（例如，均方根誤差或平均平均水平）有幫助。

我們遇到過大學項目的數字問題。有幾種方法可以解決這個問題（忽略這些項目或對它們進行抽樣），但我們正在使用基於項目和用戶級別的正則化。這使用戶和項目向量的值保持在一定的值範圍內。

評估數據和參數

為了衡量建議的質量，我們可以使用現有數據的樣本在運行實際A / B測試之前計算一些離線指標，這表明我們的估計與實際用戶偏好之間的差異。這兩種算法都有許多超參數，可以通過交叉驗證進行調整以獲得最佳建議。我們還提供其他選項，例如添加用戶和項目偏差。

輸入評級可以清楚地分為兩個數據集（培訓和測試）。這在測試數據包含所有訓練實例之後的時間間隔內的所有用戶操作的情況下非常有用。否則，為了構建測試數據，我們隨機選擇每個用戶T = 1並將它們與訓練分開。

在算法期間，對於一定百分比的用戶，我們對所有未評級的項目（即，不在訓練集中的項目）進行排名，並在排名的推薦列表中觀察訓練和測試項目的位置。然後我們可以評估以下指標：平均排名（排名列表中的位置，所有測試項目的平均值），位置精度1/10/100，所有測試項目的平均準確度（MAP）等。此外，我們計算均方根誤差（RMSE），它放大了絕對值的貢獻。

物品推薦計算

為了獲得所有用戶的實際建議，我們需要找到每個用戶具有最高預測評級的項目。在處理龐大的數據集時，即使我們將問題分發給更多的工作人員，檢查每個（用戶，項目）對的點積也變得不可行。我們需要一種更快捷的方法來為每個用戶找到前K個推薦值，或者對它有一個很好的近似。

一種可能的解決方案是使用球樹數據結構來保存我們的項目向量。球樹是二叉樹，其中葉子包含項目向量的一些子集，並且每個內部節點定義圍繞其子樹內的所有向量的球。對於查詢向量和球內的任何向量，使用點積上限的公式，我們可以進行貪婪的樹遍歷，首先進入更有希望的分支，並且修剪不能包含解決方案的子樹比我們更好已經找到了。這種方法顯示比查看每對方法快10-100倍，因此在合理的時間內搜索我們數據集的建議。我們還添加了一個選項，以便在查找最佳建議時允許指定的錯誤，從而進一步加快計算速度。

可以近似解決問題的另一種方法是通過基於項目特徵向量聚類項目 - 這減少了查找頂級群集推薦的問題，然後基於這些頂級群集提取實際項目。這種方法加速了計算，同時基於實驗結果略微降低了推薦的質量。另一方面，群集中的項目是相似的，我們可以通過從每個群集中獲取有限數量的項目來獲得各種建議。請注意，我們在Giraph之上也有k-means聚類實現，並且在計算中合併這一步驟非常簡單。

與MLlib比較

Spark MLlib是一個非常流行的機器學習庫，包含該領域領先的開源實現之一。 2014年7月，Databricks團隊在Spark上發佈了他們的ALS實施的性能數據。實驗是在亞馬遜評論數據集的縮放副本上進行的，該數據集最初包含3500萬個評級並且進行了五次迭代。

在下圖中，我們將我們的旋轉混合方法（我們在Giraph中實現）與標準方法（在Spark MLlib中實現，包括一些額外的優化，例如最多向機器發送一次特徵向量），相同的數據進行了比較組。由於硬件差異（我們每臺機器的處理能力大約是兩倍），為了進行公平的比較，我們考慮了總CPU分鐘數。旋轉混合解決方案快了約10倍。

此外，使用標準方法進行實驗的最大數據集具有35億個評級。通過旋轉混合方法，我們可以輕鬆處理超過1000億的額定值。請注意，兩者的結果質量相同，並且所有性能和可伸縮性增益都來自不同的數據佈局和減少的網絡流量.Facebook用例和隱式反饋

我們將此算法用於Facebook的多個應用程序，例如用於推薦您可能喜歡的頁面或您應該加入的群組。如前所述，我們的數據集由超過10億用戶組成，通常有數千萬個項目。實際上有更多的頁面或組，但我們僅限於通過一定質量閾值的項目 - 最簡單的版本是項目度數大於100.（有趣的是注意：另一方面，我們有一些非常大型頁面 - Facebook“每個手機的Facebook”頁面實際上被Facebook當前每月活躍用戶的一半所喜歡。）

我們的第一次迭代包括頁面喜歡/組連接作為正信號。 Facebook上的負面信號並不常見（負面信號包括不喜歡頁面或在一段時間後離開一個組）。這也可能實際上並不意味著用戶對該項目有負面反饋;相反，他或她可能對該主題或接收更新失去了興趣。為了獲得好的建議，非常需要從集合中的未評級對添加負項。以前的方法包括從未評級項目中隨機挑選負面訓練樣本（導致有偏見的非最佳解決方案）或將所有未知評級視為負面，這極大地增加了算法的複雜性。在這裡，我們通過考慮用戶和項目程度（根據項目程度分佈添加與用戶程度成比例的負面評級）實施添加隨機負面評級，並且權衡負評級小於正評級，因為我們未能學到好處採用均勻隨機抽樣方法的模型。

另一方面，我們有來自用戶的隱式反饋（用戶是否正在主動查看頁面，喜歡或評論組中的帖子）。我們還為隱式反饋數據集實現了一個眾所周知的基於ALS的算法。這種方法不是直接對評級矩陣進行建模，而是將數據視為二元偏好和置信度值的組合。然後，評級與觀察到的用戶偏好的置信水平相關，而不是與項目的明確評級相關。

運行矩陣分解算法後，我們有另一個Giraph工作，實際計算所有用戶的最佳建議。

以下代碼顯示了使用我們的框架，調整參數和插入不同數據集是多麼容易：

CFTrain(

ratings=CFRatings(table='cf_ratings'),

feature_vectors=CFVectors(table='cf_feature_vectors'),

features_size=128,

iterations=100,

regularization_factor=0.02,

num_workers=5,

)

CFRecommend(

ratings=CFRatings(table='cf_ratings'),

feature_vectors=CFVectors(table='cf_feature_vectors'),

recommendations=CFRecommendations(table='cf_recommendations'),

num_recommendations=50,

num_workers=10,

)

此外，可以通過擴展SGD或ALS計算簡單地實現其他目標函數（例如秩優化或相鄰模型）。

可擴展的CF.

推薦系統正在成為預測用戶偏好的重要工具。我們的矩陣分解和計算頂級用戶推薦框架能夠有效處理Facebook擁有1000億次評級的海量數據集。它易於使用，並可與其他方法一起使用。

我們正在考慮許多改進和算法，包括：

結合社交圖和用戶連接以提供更好的建議集

從以前的模型開始而不是隨機初始化，用於反覆學習

具有交叉驗證的自動參數擬合，用於優化給定數據集的不同度量

在旋轉期間嘗試更好的分區和跳過不需要某些項目數據的機器

我們正積極致力於建立Giraph之上的建議和許多其他應用程序，因此請繼續關注該領域中更多令人興奮的功能和開發。