CatBoost：比XGBoost更優秀的GBDT算法
譯文【51CTO.com快譯】互聯網的算法有很多應用場景，包括推薦系統、計算廣告和金融反欺詐等。許多互聯網的機器學習和數據挖掘問題都可以轉化為分類問題。在處理這一類分類問題的時候，最常用的方法包括邏輯回歸、GBDT和深度學習等。其中邏輯回歸因為算法效率高，能有效處理大規模的數據，在深度學習還沒有流行之前就被廣泛的應用于大型的互聯網公司。
深度學習是自 2012 年由百度首先成立深度學習實驗室之后在國內掀起的人工智能大潮。然而由于深度學習目前還處于蓬勃發展的階段，并且處理大規模數據時對于機器的經費的要求都比較高，因此在很多應用場景下大家選擇的并不是機器學習。GBDT 自問世以來便在諸多機器學習問題上取得了良好的效果，不僅在工業界，而且在 Kaggle 比賽上取得了非常優秀的成績。
針對 GBDT 算法，在學術界和工業界有許多開源的算法包。著名的包括 University of Washington 的陳天奇開發的 XGBoost ，微軟的 LightGBM ，還有 Yandex 公司開發的 CatBoost 。XGBoost 被廣泛的應用于工業界，LightGBM 有效的提升了 GBDT的計算效率， 而 Yandex 的 CatBoost 號稱是比 XGBoost 和 LightGBM 在算法準確率等方面表現更為優秀的算法。本文主要通過介紹 Yandex 2017 年發表的一篇題為 CatBoost: Unbiased Boosting with Categorical Features 的論文給大家介紹 CatBoost 算法。
CatBoost 算法的設計初衷是為了更好的處理 GBDT 特征中的 categorical features 。在處理 GBDT 特征中的 categorical features 的時候，最簡單的方法是用 categorical feature 對應的標簽的平均值來替換。在決策樹中，標簽平均值將作為節點分裂的標準。這種方法被稱為 Greedy Target-based Statistics , 簡稱 Greedy TBS，用公式來表達就是：
這種方法有一個顯而易見的缺陷，就是通常特征比標簽包含更多的信息，如果強行用標簽的平均值來表示特征的話，當訓練數據集和測試數據集數據結構和分布不一樣的時候會出問題（條件偏移問題）。
一個標準的改進 Greedy TBS的方式是添加先驗分布項，這樣可以減少噪聲和低頻率數據對于數據分布的影響：
其中 P 是添加的先驗項，a 通常是大于 0 的權重系數。
為了解決條件遷移問題，常用的方法例如可以將數據集合分為兩部分，在***個部分上對數據的特征進行類似 Greedy TBS 的處理，而在第二個數據集合上進行訓練。CatBoost 參考了在線學習的方法，首先對訓練書進行了隨機的重排列，然后選擇 作為訓練樣本，而整個的數據集合做為測試樣本。
類似的，在GBDT的模型訓練階段，同樣會因為訓練數據與測試數據分布不同的問題產生預測偏移（Prediction Shift）和殘差偏移（Residual Shift）的問題。為了解決相應的問題，CatBoost 作者采用了排序提升（Ordered Boosting）的方式，首先對所有的數據進行隨機排列，然后在計算第 i 步殘差時候的模型只利用了隨機排列中前 i-1 個樣本。
CatBoost 針對于原始 GBDT 的各種偏移問題進行改進之后的算法偽代碼如下：
CatBoost 和 XGBoost 以及 LightGBM 在一些知名的數據集合上的測試效果如下表所示，評測指標為 Logloss 和 Zero-one Loss 。
CatBoost 的基本原理是解決原始 GBDT 中的各種數據偏移問題。在一些開源的機器學習和數據挖掘的算法包里有現成的模塊可以調用。CatBoost 自從 2017 年被 Yandex ***提出以來得到了廣泛的關注。希望本文的介紹能給大家帶來幫助。
汪昊，恒昌利通大數據部負責人/資深架構師，美國猶他大學本科/碩士，對外經貿大學在職MBA。曾在百度，新浪，網易，豆瓣等公司有多年的研發和技術管理經驗，擅長機器學習，大數據，推薦系統，社交網絡分析等技術。在 TVCG 和 ASONAM 等國際會議和期刊發表論文 8 篇。本科畢業論文獲國際會議 IEEE SMI 2008 ***論文獎。
【51CTO譯稿，合作站點轉載請注明原文譯者和出處為51CTO.com】
