Facebook提升數十億使用者體驗的秘密武器：梯度提升決策樹

Facebook 使用機器學習和排序模型給所有使用者帶來最佳體驗，例如傳送什麼通知，在你的訊息推送中放入什麼文章，以及對於你想關注的人提些什麼建議。高質量的機器學習模型對於找出最相關的內容來說很重要。我們觀察了大量實時訊號以制定最佳排序；例如，在過濾通知的使用情況中，我們觀察某人是否已點選相似的通知，或者對應通知的文章獲得了多少贊。由於每執行一次就會生成一個新通知推送，所以我們想要儘快返回傳送通知的決策。

更復雜的模型有助於提高預測的精度，提供更相關的內容。但更復雜的模型需要更長的 CPU 週期（CPU cycles），返回結果的時間也更長。考慮到這些限制，我們做不到對所有可能的候選模型進行評估。然而，透過提升模型效率，我們可以做到在相同的時間幀運用相同的計算資源評價更多的候選模型（inventory）。

在本文中，我們比較了梯度提升決策樹（gradient-boosted decision tree ，簡稱GBDT）這一類預測模型的不同實現，並描述了能產生更高效評估的 C++ 多方面改進。

決策樹模型

決策樹被普遍用作預測模型，該演算法將關於物件的特徵觀察值對映到物件類的目標值。由於其非線性和快速求值的特點，它成為了機器學習、資料分析和統計學之中最常見的預測模型方法之一。在這些樹狀結構中，葉結點表徵分類標籤，而有向邊表徵產生這些分類標籤的特徵連線。

決策樹非常強大，但是訓練資料中的小變動可以演化為決策樹中的大變化。這可透過使用一項被稱為梯度提升（gradient boosting）的技術來補救。即，為錯誤分類的訓練例項提升權重，從而形成一個新的決策樹。接著對這一步驟進行連續重複以獲得新的決策樹。最後的分值（scores）是決策樹上每個葉節點分值的加權總和。

模型通常很少更新，且訓練複雜模型需要花費數小時。然而，在 Facebook 的大規模資料上，我們想要更頻繁地更新模型，即按照毫秒間隔依次執行它們。Facebook 的很多後端服務是用 C++ 寫的，因此我們利用這一語言的一些屬性做了些改善，以產生只需要更短 CPU 週期進行求值的高效模型。

下圖是一個簡單的決策樹，它包含以下特徵：

今天某人 A 點選通知的數量（特徵 F［0］）

對應通知的文章點贊數量（特徵 F［1］）

某人 A 點選通知的總數量（特徵 F［2］）

在不同的結點，我們查看了上述特徵的值，並遍歷整棵決策樹以獲取通知點選的機率。

平面樹（Flat tree）的實現

決策樹模型的樸素實現是透過一個帶有指標的簡單二叉樹而完成的。然而，結點並不需要連續地儲存於記憶體之中，因為這樣二叉樹並非很有效。另一方面，決策樹通常是完整的二叉樹（即二叉樹的每個結點一定存在零值或兩棵子樹），它透過使用向量而壓縮儲存。指標並不需要空間，而每一結點的父結點和子結點可透過陣列索引演算法檢視。我們將用這一實現對比這一章節的實驗。

編譯樹（Compiled tree）的實現

每一個二叉樹都能由一個複雜的三元表示式表徵，而這個表示式能進行編譯並連結到可直接在服務中使用的動態庫（DLL）。需要注意的是，我們可以實時新增或更新決策樹模型，而不需要重啟服務。

我們也可以利用 C++ 中的 LIKELY/UNLIKELY 註釋（annotations）。它們是編譯器發出指令的方向，並且能將分支預測更加偏向於跳轉指令（jump instruction）「可能」出現的一側。如果預測是對的，那麼就意味著跳轉指令將佔有 0 個 CPU 週期。我們可以根據在批次中排序的或離線分析中的真實樣本計算分支預測，這是因為訓練和評估集的分佈不應該改變太多。

下列程式碼表徵上述的簡單決策樹的一個實現：

模型範圍求值

在典型的排序設定中，我們需要在多個特徵向量的例項上評估相同的已訓練模型。例如，我們需要為了一個給定的人排序 1000 個潛在候選項，並選擇最相關的候選項。

一種方法是迭代所有候選項並逐一排序。而通常情況下，模型和所有候選者都不能組合到 CPU 指令快取中。而受到提升訓練（boosted training）的驅動，實際上我們可以將模型分解到樹的範圍內（第一批 N 子棵樹，第二批 N 棵子樹等等）。這樣每個範圍就能足夠小以適應快取。隨後我們可以調轉評估順序：我們將評估每個範圍上的所有樣本，而不是評估一個樣本上的所有樹。採用這種方法，我們可以在 CPU 快取中將整棵樹的集合與所有的特徵向量進行合併，並在下一次迭代中僅僅只是替代子樹集。這種方法不僅減少了快取未命中（cache misses）數量，同時還使用區塊讀/寫而不是 RAM。

此外，經常還出現多個模型需要評估相同特徵向量的情況。例如，使用者在文章中點選、點贊或評論的機率。這種方法有助於將所有特徵向量儲存在 CPU 快取中，並逐個評估模型。

另外一個折衷方法可以考慮為前 N 棵樹排序所有的候選項，並由於提升演算法的自然屬性，我們可以丟棄排名最低的候選項。這樣雖然可以提高延遲，但精度也會略微地下降。

普遍特徵

有時特徵在所有的特徵向量中很普遍。在上述對於某個特定個人的例項中，我們需要排序所有的候選通知。上文描述的特徵向量 ［F［0］、F［1］、F［2］］ 可為：

［0、2、100］

［0、0、100］

［0、1、100］

［0、1、100］

我們很容易發現特徵 F［0］ 和 F［2］ 對於候選項是相同的。我們可以透過聚焦 F［1］ 的值顯著縮小決策樹，從而改善求值的時間。

類屬（Categorical features）特徵

絕大多數機器學習演算法使用二叉樹，並且二叉樹可被延伸成 k-ary 樹。另一方面，特徵中的一些實際上並不能被比較，因而被稱為類屬特徵。例如，如果國家是一個特徵，一個人不可能說這個國家的值是否少於或者等於美國（或者一個對應的列舉值）。如果樹足夠深，那麼這個比較可透過使用多個層級實現。但是這裡我們已經實現了檢查當前特徵是否屬於一組值的可能性。

這個學習方法並沒有改變太多，我們依然在嘗試找到可被分割的最優子集，並且其求值也非常快。基於集的大小，我們使用 in_set C++ 實現，或者僅僅把 if 條件連線起來。這減小了模型，對於收斂也有所幫助。

計算結果

我們訓練了一個提升決策樹（boosted decision tree）模型以預測一個使用了 256 個決策樹、每個樹包含 32 個葉結點的通知點選機率。接著，我們比較了特徵向量求值的 CPU 使用率，其中每個批次平均排序 1000 個候選項。批次大小值 N 基於機器 L1/L2 快取大小進行調整和最佳化。下面讓我們看一下在平面樹（flat tree）實現期間的效能提升：

普通編譯模型：2 倍提升。

帶註釋的編譯模型：2。5 倍提升。

帶註釋、範圍和普遍／特殊特徵的編譯模型：5 倍提升。

效能提升對於不同的演算法引數（128 或 512 個樹，16 或 64 個葉結點）是相似的。

結論

CPU 使用率的提升和附帶的加速允許我們增加排序例項的數量，或者在使用相同數量資源的情況下增加模型的大小。這一方法已被應用於 Facebook 的幾個排序模型之中，比如通知過濾、推送排序、建議和使用者關注。我們的機器學習平臺在持續進化，更精確模型與更高效的模型求值方法的結合將允許我們持續提升排序系統的效能，併為數十億人帶來最佳的個人化體驗。

————-文章來源：Facebook提升數十億使用者體驗的秘密武器：梯度提升決策樹

大家可以加小編微信：xtechday （備註：知乎），一起到 知乎人工智慧愛好者交流群 探討交流。