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