[[242113]]

【51CTO.com快譯】互聯(lián)網(wǎng)的算法有很多應(yīng)用場景，包括推薦系統(tǒng)、計算廣告和金融反欺詐等。許多互聯(lián)網(wǎng)的機器學(xué)習(xí)和數(shù)據(jù)挖掘問題都可以轉(zhuǎn)化為分類問題。在處理這一類分類問題的時候，最常用的方法包括邏輯回歸、GBDT和深度學(xué)習(xí)等。其中邏輯回歸因為算法效率高，能有效處理大規(guī)模的數(shù)據(jù)，在深度學(xué)習(xí)還沒有流行之前就被廣泛的應(yīng)用于大型的互聯(lián)網(wǎng)公司。

深度學(xué)習(xí)是自 2012 年由百度首先成立深度學(xué)習(xí)實驗室之后在國內(nèi)掀起的人工智能大潮。然而由于深度學(xué)習(xí)目前還處于蓬勃發(fā)展的階段，并且處理大規(guī)模數(shù)據(jù)時對于機器的經(jīng)費的要求都比較高，因此在很多應(yīng)用場景下大家選擇的并不是機器學(xué)習(xí)。GBDT 自問世以來便在諸多機器學(xué)習(xí)問題上取得了良好的效果，不僅在工業(yè)界，而且在 Kaggle 比賽上取得了非常優(yōu)秀的成績。

針對 GBDT 算法，在學(xué)術(shù)界和工業(yè)界有許多開源的算法包。著名的包括 University of Washington 的陳天奇開發(fā)的 XGBoost ，微軟的 LightGBM ，還有 Yandex 公司開發(fā)的 CatBoost 。XGBoost 被廣泛的應(yīng)用于工業(yè)界，LightGBM 有效的提升了 GBDT的計算效率， 而 Yandex 的 CatBoost 號稱是比 XGBoost 和 LightGBM 在算法準確率等方面表現(xiàn)更為優(yōu)秀的算法。本文主要通過介紹 Yandex 2017 年發(fā)表的一篇題為 CatBoost: Unbiased Boosting with Categorical Features 的論文給大家介紹 CatBoost 算法。

CatBoost 算法的設(shè)計初衷是為了更好的處理 GBDT 特征中的 categorical features 。在處理 GBDT 特征中的 categorical features 的時候，最簡單的方法是用 categorical feature 對應(yīng)的標簽的平均值來替換。在決策樹中，標簽平均值將作為節(jié)點分裂的標準。這種方法被稱為 Greedy Target-based Statistics , 簡稱 Greedy TBS，用公式來表達就是： 

這種方法有一個顯而易見的缺陷，就是通常特征比標簽包含更多的信息，如果強行用標簽的平均值來表示特征的話，當訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集數(shù)據(jù)結(jié)構(gòu)和分布不一樣的時候會出問題（條件偏移問題）。

一個標準的改進 Greedy TBS的方式是添加先驗分布項，這樣可以減少噪聲和低頻率數(shù)據(jù)對于數(shù)據(jù)分布的影響：

其中 P 是添加的先驗項，a 通常是大于 0 的權(quán)重系數(shù)。

為了解決條件遷移問題，常用的方法例如可以將數(shù)據(jù)集合分為兩部分，在***個部分上對數(shù)據(jù)的特征進行類似 Greedy TBS 的處理，而在第二個數(shù)據(jù)集合上進行訓(xùn)練。CatBoost 參考了在線學(xué)習(xí)的方法，首先對訓(xùn)練書進行了隨機的重排列，然后選擇   作為訓(xùn)練樣本，而整個的數(shù)據(jù)集合做為測試樣本。

類似的，在GBDT的模型訓(xùn)練階段，同樣會因為訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)分布不同的問題產(chǎn)生預(yù)測偏移（Prediction Shift）和殘差偏移（Residual Shift）的問題。為了解決相應(yīng)的問題，CatBoost 作者采用了排序提升（Ordered Boosting）的方式，首先對所有的數(shù)據(jù)進行隨機排列，然后在計算第 i 步殘差時候的模型只利用了隨機排列中前 i-1 個樣本。

CatBoost 針對于原始 GBDT 的各種偏移問題進行改進之后的算法偽代碼如下：

CatBoost 和 XGBoost 以及 LightGBM 在一些知名的數(shù)據(jù)集合上的測試效果如下表所示，評測指標為 Logloss 和 Zero-one Loss 。

CatBoost 的基本原理是解決原始 GBDT 中的各種數(shù)據(jù)偏移問題。在一些開源的機器學(xué)習(xí)和數(shù)據(jù)挖掘的算法包里有現(xiàn)成的模塊可以調(diào)用。CatBoost 自從 2017 年被 Yandex ***提出以來得到了廣泛的關(guān)注。希望本文的介紹能給大家?guī)韼椭?/p>

汪昊，恒昌利通大數(shù)據(jù)部負責(zé)人/資深架構(gòu)師，美國猶他大學(xué)本科/碩士，對外經(jīng)貿(mào)大學(xué)在職MBA。曾在百度，新浪，網(wǎng)易，豆瓣等公司有多年的研發(fā)和技術(shù)管理經(jīng)驗，擅長機器學(xué)習(xí)，大數(shù)據(jù)，推薦系統(tǒng)，社交網(wǎng)絡(luò)分析等技術(shù)。在 TVCG 和 ASONAM 等國際會議和期刊發(fā)表論文 8 篇。本科畢業(yè)論文獲國際會議 IEEE SMI 2008 ***論文獎。

[[242116]]

【51CTO譯稿，合作站點轉(zhuǎn)載請注明原文譯者和出處為51CTO.com】