一、?簡介

? ? ? ? CatBoost?與 XGBoost 、LightGBM是主流的三大Boosting框架，都是高效的GBDT算法工程化實現(xiàn)框架。CatBoost?則因長于處理類別特征而取名為CatBoost(Categorical + Boosting)。算法的理論特色，包括用于處理類別變量的目標變量統(tǒng)計和排序提升算法。算法原文地址：CatBoost算法論文。原文結構如下：

1、Introduction(簡介)

2、Background（算法提出背景）

3、Categary Features（處理類別特征）

4、Prediction shift and ordered boosting（預測偏移與有序提升算法）

5、Practical implementation of ordered boosting（有序提升的實現(xiàn)）

6、Experiments（實驗與對比）

? ? ? ?其中3、4、5是論文核心，專門闡釋CatBoost處理類別變量統(tǒng)計和排序提升算法及實施。本文對3、4、5嘗試解讀以闡釋catboost原理。

二、?算法主要部分

? ? ?如論文簡介所述，論文主要引入了兩個關鍵算法以處理預測偏移問題：一種處理類別特征的創(chuàng)新算法Ordered Target Statistics 和 有序增強實現(xiàn)（一種排列驅動的替代經(jīng)典算法）。這兩種技術都是為了應對當前所有梯度增強算法實現(xiàn)中存在的一種被稱之為的“目標泄漏”（是指特征的條件分布?在訓練樣本和測試樣本中存在不同）所造成的預測偏移。

? ? 首先是處理類別的算法，目標統(tǒng)計（注：目標就是一個樣本中的標簽?，目標統(tǒng)計就是用對的期望值代替?的類別特征值）。所有現(xiàn)有的梯度提升的實現(xiàn)通常面臨以下問題，經(jīng)過幾步增強得到的預測模型F依賴于所有訓練示例的目標。論文證明，這實際上導致訓練示例的F() | 的分布與測試示例x的F() | 的分布不一致，并最終導致學習模型的預測偏離。此外，在分類特征預處理的標準算法中也存在類似的問題。在梯度提升中使用它們的最有效方法之一是將類別轉換為它們的目標統(tǒng)計值。

? ? ? 2.1?類別特征和目標統(tǒng)計

? ? ? ? 類別特征是一種由一系列離散的且不能彼此比較的值所組成的集合，提升樹通常處理類別特征的方法是獨熱編碼，例如對每一類的取值，添加一個新的二進制特征來標志它，例如，某類離散取值有（甲類、乙類、丙類），則獨熱編碼，增加三個特征：甲類、乙類、丙類，每一類取值0?或1?以標志某個樣本是否屬于某一類；然而這對于高基數(shù)的特征，比如用戶ID號（通常是很大的正整數(shù)），則會導致實際不可行的大量新增的特征，如1000個取值就要新增加1000個特征，這對于算法而言會產(chǎn)生不小的負擔。?通常解決辦法是，將類別特征的取值再次分組為數(shù)量較少的幾簇，然后再進行one-hot編碼。還有一種方法就是使用每一類對應的標簽值的統(tǒng)計值代替類別本身的值，譬如某個特征取值為 'm' 的n個樣本 ，對應目標變量為、、...... ，則取、、...... 的某種統(tǒng)計值代替'm'。這樣，特征的取值就由這些取值對應的?目標變量統(tǒng)計替代，而目標變量統(tǒng)計值的數(shù)量要比特征的取值數(shù)少，間接實現(xiàn)了降低特征取值數(shù)量的目的。

? ? ? ? 正如上所述，一個有效的解決類別特征i的方法就是將樣本k的第 i?個特征值?用一個數(shù)值特征比如(TS) ?統(tǒng)計。通常，這個估計值用某個類別對應的 y的期望值代替：?。論文對于目標變量統(tǒng)計（TS）列舉了 Greedy TS、HoldoutTS、Leave-one-out TS?并根據(jù)P1、P2準則（下文介紹）指出其中的不足，最后引出CatBoost提出的 ordered TS。

? ? ? Greedy TS:?估算函數(shù)最直接方式就是采用訓練集中相同類別的樣本的目標變量y的平均值，這種估算方式在低頻率類別上有噪聲，因此常常會加先驗p進行平滑。

??? ? ? ? ? ?-------(1)

? ? 其中i指示類別i，k指示樣本k。而 ?的意思是判斷：當前樣本j是否與樣本k是同一類別i，如果是則為1，反之則為0。而先驗p為數(shù)據(jù)集中對應i特征的所有目標值的均值，?α?是 控制先驗參與編碼的權重。Greedy TS?的局限是：不滿足文中提出的P1準則條件，即訓練集某個樣本在某個特征取新值（目標統(tǒng)計值）的期望?等于?測試集某個特征對應于本樣本取值所對應的目標統(tǒng)計值的均值。

? ? ? ? ? ?： ?,其中（）是第k個樣本。

文中舉例說明，假設第 i 個是分類的，數(shù)據(jù)集此特征每個取值是唯一的，且取某個值A,y=1條件概率為0.5，因此對于每個樣本的?，TS值為?=???,因此?? 可以完整的區(qū)分所有的訓練樣本，然而對于測試樣本，greedy TS?的值為??= p? 。因而，對于上述例子說明，樣本?目標值的期望?不等于?測試集樣本目標值的期望，從而會導致目標泄露，進而會導致預測偏移。

? ? 有很多方法可以防止條件偏移，常見的策略就是統(tǒng)計某個樣本的TS時，將樣本排除在外，即用

?,? 得到下式：

? ----------(2)

HoldoutTS：就是把訓練集分成兩部分，用一部分按公式2計算TS值，然后用另一部分訓練，這種方法滿足準則1，且明顯減少了訓練和計算TS值得數(shù)據(jù)量，但是，它不滿足以下準則2：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?：? 有效地使用所有數(shù)據(jù)計算TS值和學習一個模型

Leave-one-out TS:?留一法 ，是將D去除樣本?后?計算???的TS值，并訓練，而測試集則用全部的數(shù)據(jù)集（即并不排除測試樣本本身）。文中同樣舉一特例，說明在這種情況下?的TS取值? 并且存在一個可劃分所有訓練樣本的閾值。因此不滿足準則1。

Ordered TS:? 就是本文要重點引出的，它受在線學習按時間序列取得訓練數(shù)據(jù)的處理方式啟發(fā)，認為每樣本的TS值依賴于觀測的歷史取值。為了將其移植到離線方式，引入虛擬的“人工時間”，就是把樣本的一個排列δ看成一個時間序列，然后對于這個時間序列，對于每個樣本??,取?={ ?}?,用公式（2）計算訓練樣本的TS值，而對于測試集取全部的??= D?用來計算測試樣本的TS值。Ordered TS?滿足準則1和準則2。但是，如果只用一個排列σ?則排列在前面的樣本TS值會比后面的有更高的方差，（因為后者用于計算TS值更多），因此在CatBoost對于梯度提升的不同輪次，采用了不同的排列，來解決這個問題。就是通過多次排列，訓練集中的每個樣本排在各個位置的概率相近，從而總體實現(xiàn)各樣本相同的方差。

? ? ? ? 2.2?預測偏移

? ? ? ? ?原文揭示了在梯度提升中存在的預測偏移。假設前一輪訓練得到的強分類器為,則本輪迭代要擬合的弱分類器為,的理想表達式為：

? ?---------（3）

公式表明h(x)就是擬合本輪強分類器負梯度（實際計算中，可用上一輪分類器表示）的最優(yōu)值，上式在實際計算的近似式為：

? ?----------（4）

由上式可知，最終預測偏移的鏈式傳遞為：

? ? ? ? ? ?1、訓練樣本梯度?的條件分布與測試樣本梯度條件分布存在偏移。

? ? ? ? ? ?2、?的近似公式（4）和理想公式（3）存在偏移。

? ? ? ? ? ?3、前二者最終會影響?的泛化性能。

? ? ? ? ? 建立的所有數(shù)據(jù)點的TS值，會在每一輪次被重復使用以計算梯度，而訓練樣本的分類器的條件分布與?測試樣本???的條件分布不一致，文中稱之為預測偏移。

? ? ? ? ?關于預測偏移的分析：以二次損失函數(shù)的形式簡單地分析了回歸任務的簡單預測轉移問題。 在這種情況下，公式（4）中的負梯度可以用殘差函數(shù)代替。 假設我們有m = 2個特征，，獨立同分布的伯努利隨機變量，其中p = 1/2和 = = 。 假設我們用決策樹樁（深度為1的樹）且步長為α= 1來進行N = 2步的梯度增強。獲得模型。假設基于，基于，這對于 | | > | | （這里在和之間設置了一些不對稱性)。

? ? ? ?根據(jù)以上假定，原文引出定理1（證明見原文附錄Section A）: 如果使用等式（4）分別使用大小為n的兩個獨立樣本和估計和，則對于任何x∈。 2.如果對于和在公式（4）中使用相同的數(shù)據(jù)集=?=，則。

? ? ? 定理說明：如果在加性模型的梯度提升的每一輪中，分別使用不同的獨立樣本集，則訓練的模型是真實模型?的無偏估計，而如果每一輪中使用相同的樣本集，則訓練模型與真實模型存在 的偏差。這就從理論上證明并精確估計了偏差。

? ? ? 2.3?有序提升算法

? ? ? ? ? 基于以上的預測偏移，原文提出了一種稱之為有序提升算法。假如訓練集數(shù)據(jù)無限大，則容易構建一個算法。在這個提升算法的每一步，可以獨立選取一個獨立的新的數(shù)據(jù)集，然后可以用這個數(shù)據(jù)集訓練得的模型計算在新訓練樣本上的無偏移殘差。然而在實際中，標簽數(shù)據(jù)是有限的，假設訓練至有I棵樹的模型，為了使殘差?的計算無偏移，需要在中排除,這樣為了使所有訓練樣本的殘差計算無偏移，則沒有樣本用來訓練。這似乎讓訓練成為不可能。實際上，可以用模型訓練所使用的樣本來區(qū)分而得到一系列的模型，這樣選取不包含這個樣本的模型就可以計算這個樣本的殘差。為了構建這一些模型，可以采用之前ordered TS的方法。具體就是，選取一個樣本的隨機排列，然后訓練n個支撐模型?、、........,其中?模型是用排列的前i個樣本訓練得出。在每一步為了獲得第j個樣本的殘差，使用模型,?這樣的算法就稱之為有序提升算法。這種算法需要訓練n個模型，增加了計算復雜度和存儲。在CatBoost?中，提出了一種針對有序提升算法的修改方法，該修改方法就是圖4中10-12行。

? ? ?在ordered TS?和 ordered boosting中，都相應地采用了訓練樣本的?、?排列用來計算，如果在一個算法中都采用兩者，則需要?=??以避免預測偏移。這樣確保了標簽值?沒有被用于訓練?（即沒有參與ordered TS?計算），可以設想?不等于，而如果在?使用了?，則在?中雖然沒有用，也參與了?ordered TS?的計算，這樣就會存在 TS計算分析中存在的預測偏移。? ?

? ? ? 2.4?有序提升算法的實現(xiàn)

? ? ? CatBoost?有兩種提升模式，普通模式和有序模式，前者就是標準的梯度提升樹中內嵌了ordered TS ，而后者就是在Algorithm1（如圖1所示）算法基礎上的改進。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖1?有序提升算法的Algorithm1?

Algorithm1：該算法圖是一個原理概略圖（詳見附錄的正式算法圖），輸入是n個樣本集合和樹的棵數(shù)（對于Boosting ，其實就是迭代次數(shù)，不同樹是疊加迭代關系），σ?是[1,n]?的一個排列，?就是上文提出的支撐模型,對應于不同的訓練樣本集，首先初始化為0 ; 算法有三個循環(huán)，第一個循環(huán)控制迭代次數(shù)，就是梯度提升次數(shù)，每一次對應構建了一個梯度樹，前一次在后一次的基礎上提升。第二個循環(huán)就是 擬合前計算殘差，每一次殘差的計算，都用到了上一輪生成的?系列模型，具體對應于樣本Xi?在排列中的?序數(shù) -1?即??的M ，?用來生成預測值，從而用于計算殘差。第三個循環(huán)和第二個循環(huán)并列，用于將在排列中前于等于i?的所有樣本的殘差值擬合成一棵殘差樹△M，然后用△M?更新?每一迭代次數(shù)?、、........?都得到了更新，經(jīng)過t次迭代，得到最終的?。（當??時 j?取值使得??，從而 j =i）

圖2?采用有序提升算法構建一棵樹

? ??Algorithm2：

? ? ? ? 不同參數(shù)含義：???：訓練集；α ：學習率；L ：損失函數(shù)類型；Mode:?提升模式；?

? ? ? ? 該算法圖也是一個原理概略圖（詳見附錄的正式算法圖），描述的是構建一棵樹的情形。輸入M?其實是一個?對應于排列集合?的?數(shù)組，在ordered?模式下，M采用Algorithm1得到，在plain模式下，M采用了普通的GBDT提升樹算法擬合，其次用梯度計算公式，計算對應模型的梯度數(shù)組，?對應于??。對于兩種模式計算相應的梯度數(shù)組G，對于Plain?模式，G =??,對應于 ordered?的模式 G=?? ,每一次構建一個樹時，選擇一個隨機排列。然后自頂而下構建一棵樹，在每個節(jié)點分裂時，候選出可分裂的節(jié)點值c,計算預分裂后每個樣本在節(jié)點的平均梯度值 ，然后結合樣本點已有的梯度，計算余弦相似度損失函數(shù)，選取余弦相似度損失函數(shù)最小值對應的c?進行分裂，以此方式分裂直至整棵樹完成。?最后將生成的樹用于更新所有預先生成的M數(shù)組，也分成plain模式和ordered?模式。（可見，每次迭代生成的樹擬合了某一隨機排列下的訓練集，綜合了訓練集的有用信息，而將每次迭代生成的樹用于更新M數(shù)組，就可以使用更新的數(shù)組包含前一排列訓練集的有用信息，以創(chuàng)建下一個樹，同時經(jīng)過多次迭代，M數(shù)組中，每個樣本對應的?可以降低方差）這樣就完成了一棵樹的構建，經(jīng)過多次迭代，得到t棵樹，用于構建最終樹，和最終樹對應的M數(shù)組。

? ? ? 原文內容：

? ? ? CatBoost?產(chǎn)生s+1?個獨立的隨機排列。用于評估樹節(jié)點分裂，產(chǎn)生一棵樹。?用于計算 已獲得樹的葉節(jié)點值；對于在給定的排列中前序很短的例子，有序提升使用的TS和預測(算法1中的Mσ(i)?1(xi))都有很大的方差。因此，僅使用一種排列可能會增加最終模型預測的方差，而使用多種排列則減少這種影響，后續(xù)會繼續(xù)描述。在第6節(jié)的實驗證實了采用多種排列的優(yōu)點。

? ? ? 構建一顆樹：

? ? ? 在CatBoost中，基本的預測器是oblivious樹，oblivious是指在整個樹的同一層次上使用相同的分割標準，即是用相同的特征進行分割。這樣的樹是平衡的，不容易過度擬合，并允許在測試時間顯著加快執(zhí)行。在CatBoost中建立樹的過程在Algorithm2中描述。

? ? ?在有序提升模式中，在學習過程中，維持一個支持模型序列，其中是基于排列中前j個例子的對第i個例子的當前預測。在算法的每一次迭代t中，我們從{σ1，…，σs}隨機選擇一個，并在此基礎上構造樹。首先，對于類別特征，根據(jù)這種排列計算所有的TS值。其次，排列影響樹的學習過程。即，基于，計算相應的梯度。然后，在構造樹的時候，用余弦相似度cos(·,·)來近似梯度G。其中，對于每個例子i，我們取梯度(它僅基于在σr中排在i之前的例子)。在候選拆分評估步驟中，葉片值?(i)例如i分別通過對位于實例i所屬葉片中的且在排列中先于i的p梯度平均值得到。注意，依賴于所選擇的排列σr，因為σr可以影響樣本i?的ordered TS值。讓我們強調一下，當Tt樹構建后，這個數(shù)被用于更新所有M數(shù)組系列，但是這棵樹根據(jù)和j的不同，被添加到不同的上，，如算法Algorithm2所述。

? ? ? 純提升模式的工作原理與標準的GBDT過程相似，但是，如果有分類特征，它在σ1的基礎上維持一個與TS對應的支持模型Mr ，而TS值與?對應。

? ? ?選擇葉節(jié)點：當所有樹構建完成后，葉子結點的值就可以通過最終模型F?計算，而F是基于標準的GBDT樹?等權加總每個子樹得到。而訓練樣本i?匹配到?中，就是基于計算樣本i的TS值。當最終模型應用于新的測試實例時，所有基于訓練樣本計算的TS值就會被使用，將其用于分配給?，便于F模型中的?函數(shù)判斷樣本所屬葉子結點使用。（和更新模型使用）

? ? ?模型復雜度：

其中Calc ordered TS的時間復雜度是指?在第t棵樹中查找樣本并計算一個樣本的TS值得平均時間()乘以樣本數(shù)n。

? ? ?特征組合：CatBoost的另一個重要細節(jié)是使用分類特征的組合作為附加的分類特征?？赡艿慕M合的數(shù)量隨著分類特征的數(shù)量呈指數(shù)增長，對所有分類特征進行處理是不可行的。CatBoost以一種貪婪的方式構造組合。也就是說，對于樹的每一個分割，CatBoost將所有分類特征(及其組合)與數(shù)據(jù)集中的所有分類特征結合(連接)。前者是指：在當前樹中已經(jīng)用于分割的所有分類特征(及其組合)。組合被動態(tài)轉換為TS。

? ??

三、附錄正式算法偽代碼

圖3 CatBoost?正式算法圖

? ? ?圖 4?更新模型算法

圖5?構建樹

四、參考資料

? ? ? ? ?https://blog.csdn.net/qq_41185868/article/details/112384070

? ? ? ? ?https://blog.csdn.net/u014686462/article/details/83543609

? ? ? ? ?https://blog.csdn.net/appleyuchi/article/details/85413352

? ? ? ? ?https://blog.csdn.net/qq_24591139/article/details/100104812

? ? ? ? ?https://zhuanlan.zhihu.com/p/540956200

? ? ? ?

? ? ? ? ? ?文章來源地址http://www.zghlxwxcb.cn/news/detail-842226.html

到了這里，關于CatBoost 原理解釋及主要算法圖分析的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！