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