Facebook 使用機器學(xué)習(xí)和排序模型給所有用戶帶來最佳體驗，例如發(fā)送什么通知，在你的消息推送中放入什么文章，以及對于你想關(guān)注的人提些什么建議。高質(zhì)量的機器學(xué)習(xí)模型對于找出最相關(guān)的內(nèi)容來說很重要。我們觀察了大量實時信號以制定最佳排序；例如，在過濾通知的使用情況中，我們觀察某人是否已點擊相似的通知，或者對應(yīng)通知的文章獲得了多少贊。由于每執(zhí)行一次就會生成一個新通知推送，所以我們想要盡快返回發(fā)送通知的決策。
　　更復(fù)雜的模型有助于提高預(yù)測的精度，提供更相關(guān)的內(nèi)容。但更復(fù)雜的模型需要更長的 CPU 周期（CPU cycles），返回結(jié)果的時間也更長?？紤]到這些限制，我們做不到對所有可能的候選模型進行評估。然而，通過提升模型效率，我們可以做到在相同的時間幀運用相同的計算資源評價更多的候選模型（inventory）。
　　在本文中，我們比較了梯度提升決策樹（gradient-boosted decision tree ，簡稱GBDT）這一類預(yù)測模型的不同實現(xiàn)，并描述了能產(chǎn)生更高效評估的 C++ 多方面改進。
　　決策樹模型
　　決策樹被普遍用作預(yù)測模型，該算法將關(guān)于對象的特征觀察值映射到對象類的目標(biāo)值。由于其非線性和快速求值的特點，它成為了機器學(xué)習(xí)、數(shù)據(jù)分析和統(tǒng)計學(xué)之中最常見的預(yù)測模型方法之一。在這些樹狀結(jié)構(gòu)中，葉結(jié)點表征分類標(biāo)簽，而有向邊表征產(chǎn)生這些分類標(biāo)簽的特征連接。
　　決策樹非常強大，但是訓(xùn)練數(shù)據(jù)中的小變動可以演化為決策樹中的大變化。這可通過使用一項被稱為梯度提升（gradient boosting）的技術(shù)來補救。即，為錯誤分類的訓(xùn)練實例提升權(quán)重，從而形成一個新的決策樹。接著對這一步驟進行連續(xù)重復(fù)以獲得新的決策樹。最后的分值（scores）是決策樹上每個葉節(jié)點分值的加權(quán)總和。
　　模型通常很少更新，且訓(xùn)練復(fù)雜模型需要花費數(shù)小時。然而，在 Facebook 的大規(guī)模數(shù)據(jù)上，我們想要更頻繁地更新模型，即按照毫秒間隔依次運行它們。Facebook 的很多后端服務(wù)是用 C++ 寫的，因此我們利用這一語言的一些屬性做了些改善，以產(chǎn)生只需要更短 CPU 周期進行求值的高效模型。
　　下圖是一個簡單的決策樹，它包含以下特征：
　　今天某人 A 點擊通知的數(shù)量（特征 F［0］）
　　對應(yīng)通知的文章點贊數(shù)量（特征 F［1］）
　　某人 A 點擊通知的總數(shù)量（特征 F［2］）
　　在不同的結(jié)點，我們查看了上述特征的值，并遍歷整棵決策樹以獲取通知點擊的概率。
　　
　　平面樹（Flat tree）的實現(xiàn)
　　決策樹模型的樸素實現(xiàn)是通過一個帶有指針的簡單二叉樹而完成的。然而，結(jié)點并不需要連續(xù)地存儲于內(nèi)存之中，因為這樣二叉樹并非很有效。另一方面，決策樹通常是完整的二叉樹（即二叉樹的每個結(jié)點一定存在零值或兩棵子樹），它通過使用向量而壓縮存儲。指針并不需要空間，而每一結(jié)點的父結(jié)點和子結(jié)點可通過數(shù)組索引算法查看。我們將用這一實現(xiàn)對比這一章節(jié)的實驗。
　　編譯樹（Compiled tree）的實現(xiàn)
　　每一個二叉樹都能由一個復(fù)雜的三元表達式表征，而這個表達式能進行編譯并鏈接到可直接在服務(wù)中使用的動態(tài)庫（DLL）。需要注意的是，我們可以實時添加或更新決策樹模型，而不需要重啟服務(wù)。
　　我們也可以利用 C++ 中的 LIKELY/UNLIKELY 注釋（annotations）。它們是編譯器發(fā)出指令的方向，并且能將分支預(yù)測更加偏向于跳轉(zhuǎn)指令（jump instruction）「可能」出現(xiàn)的一側(cè)。如果預(yù)測是對的，那么就意味著跳轉(zhuǎn)指令將占有 0 個 CPU 周期。我們可以根據(jù)在批量中排序的或離線分析中的真實樣本計算分支預(yù)測，這是因為訓(xùn)練和評估集的分布不應(yīng)該改變太多。