CatBoost原文:
《CatBoost:gradient boosting with categorical features support》-2018
俄羅斯人寫的文章,真的是…唉…
用詞習慣和英美作者風格不太一致.
###################################################
先說下文章結構吧:
$$原文結構=?\begin{array}{r}1.Introduction\\ 2.Categoricalfeatures\\ 3.FightingGradientBias\\ 4.FastScocer\\ 5.FasttrainingonGPU\\ 6.Experiments\end{array}$$

所以文章第2、3部分是重點,其他是講怎么在速度上優化的,即使你去讀博士,你不搞這個研究方向,那就沒必要看.

下面這個博客解讀了catboost在youtube中的講解內容
https://blog.csdn.net/friyal/article/details/82758532
先說說問題:
上面的這個博客中提到CatBoost使用的是完全對稱樹來解決過擬合問題,關于這個,
我個人…不是太看好…
因為,過擬合問題,不能純粹的使用對稱樹來解決,對稱樹不可能解決所有的過擬合的情況,而應該具體問題具體對待.

##################################
注意,這篇文章中說的GBDT和百度上的GBDT不是一個意思.
過往的算法先回顧下:
GBDT:每一顆樹的建立都使用殘差
XGBOOST:每棵樹之間地位是等同的,使用特征列采樣來建立樹.
這篇文章把GBDT和XGBOOST都稱為是GBDTS,意即:
$$GBDTS=\{\begin{array}{r}1.GBDT\\ 2.XGBOOST\end{array}$$
這個算法的優點就是提供了GPU版本,并且能夠獨熱一些離散特征.

#########################################
下面詳解文章的2、3部分,分別講了啥.
注意哈,論文原文中對算法細節的講解不如上面那篇博客那么詳細.

2.Categorical features
這個標題的意思就是離散特征.
為啥取了這么個奇怪的名字呢?
因為這個部分是講解怎么把離散特征的處理過程與標簽(也就是y,你懂的)給關聯起來,所以在標簽中沒有使用discrete features的說法,也就是說,底層依然是Cart,我們知道,Cart是不能接收離散特征值為字符串的情況的.

文章這一部分的主要貢獻是:
根據過往的:
$$\frac{{\sum }_{j=1}^n[x_{j,k}=x_{i,k}]?Y_j}{{\sum }_{j=1}^n[x_{j,k}=x_{i,k}]}$$
改成:
$$\frac{{\sum }_{j=1}^{p?1}[x_{{\sigma }_j,k}=x_{{\sigma }_p,k}]Y_{\sigma ,j}+a?P}{{\sum }_{j=1}^{p?1}[x_{{\sigma }_j,k}=x_{{\sigma }_p,k}]}$$

好了,打住裝逼,講人話,這個東西到底是干嘛的?
∵Cart決策樹無法處理取值為字符串型的離散特征
∴用來把離散特征變成數值型特征的.
上面的${\sigma }_j$表示第j條數據(所以俄羅斯人用符號也很奇怪)
上面的k表示第k列,第k個特征(這個特征是離散特征)

這里的中括號論文中說是Iverson brackets,
你看看,俄羅斯人的用詞,真是無力吐槽.
講人話,這個中括號就是指示函數,符合里面的條件就為1,否則就為0.

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
整個式子的意思是,把$x_{{\sigma }_j,k}$也就是第${\sigma }_j$條數據中的第k個特征替換為上面的式子.

上面這個式子的理論依據是啥?☆☆☆☆☆☆
根據我的理解,是李航的<統計學習方法>中的P51的式(4.10)貝葉斯估計.
然后這一部分還提了特征整合,但是論文中沒有細講,參考上面的那個鏈接就好了.

接下來第3部分:
3.Fighting Gradient Bias:
先上算法:

這部分開頭說要解決一個biased pointwise gradient estimates
這個是什么意思呢?就是下面這個圖,說人話就是噪聲點問題.

所以作者提出了一個設想,為了避免使用異常點,訓練時不使用這個點.
但是這樣的話,豈不是一開始的訓練也進行不下去了?
于是作者提出了一些技巧:
一開始對整個數據集進行s次隨機排序.
文中寫道:
For each permutation $\sigma$,we train n different models $M_i$.
所以到這里為止,復雜度已經有$O(sn)$了
對于每次排序:
對于每個模型$M_i$(指的是去除第i條數據,為了以防異常點的影響)
我們更新$M_i(X_1),???,M_i(X_i)$
所以到這里為止,復雜度就是$O(s{n}^2)$

這里的$M_i(X_1)$在論文中沒有具體說明,應該是去除第$X_i$條數據建立的模型對$X_1$這條數據的預測值

##############
也就是說,對于s次排列中的每次排列而言,我們建立n個模型$M_i$,每個模型都是去除$X_i$的情況下建立的,對于$M_i$模型而言,我們需要更新前面i個值的預測值,所以整體復雜度約為$O(s{n}^2)$

上面的是什么意思呢?
因為CatBoost是類似于GBDT的一種算法,所以也就是說每棵樹都是基于上一棵樹的殘差來建立的.

那么上面的描述是如何解決這個"biased pointwise gradient estimates"的問題呢的?
也就是說,可以修改該問題的描述為:“第i條數據在模型中的梯度如何確立”?
算法大意為:
去掉第i條數據($X_i$),建立模型$M_i$
對于前面的i-1條數據,依次計算$Loss$的梯度$g_j$
把i-1個$g_j$和$X_j$傳入函數LearnOneTree建立一棵殘差樹M
修改最初的$M_i$為$M_i+M$
通俗地講,就是利用前面i-1條數據的情況來預測第i條數據在模型中的對應的預測值.

最后總結下就是:
利用所有訓練集(除第i條)建立模型$M_i$,然后使用第1條到第i-1條數據來建一個修正樹M,累加到原來模型$M_i$上,以回避上面的"biased pointwise gradient estimates"問題.

好了,最后呢,上面這個算法被進行了修正.我們可以看到,上面這個算法是3重for循環
第二重是i,循環范圍是(1,n)
好了,優化辦法是每次處理$2^i$條數據,所以循環次數變成$lo{g}_{2}n$次
$M_i^{\prime }(X_j)$是根據$2^i$次條數據進行建模,然后對與$X_j$的預測值
我們需要的$M_i^{\prime }(X_j)$的數量是${\sum }_{0\le i\le lo{g}_2(n)}{2}^{i+1}<4n$個
所以復雜度變為$O(s?4n)=O(sn)$

總結

以上是生活随笔為你收集整理的Catboost原文解读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。