Deep Forest 演算法解讀

曾凡祥

北京郵電大學通信與信息系統博士，現為去哪兒網金融事業部大數據演算法工程師，主要進行機器學習、深度學習等人工智慧技術的研究和應用。

摘要

無論是這幾年興起的神經網路，還是經典的 LR、SVM、Random Forest 等機器學習模型，本質上都可以看成是 Representation Learning (呈現/表徵/表示學習)。深度學習之所以在圖像、語音、 NLP 等方面表現出超強的性能，本質上是因為深度神經網路代表了由具體特徵到抽象概念，由細粒度對象表示到高層語義的層層信息流動和聚集，其各層網路的權重共同構成了對數據的表示；而圖像，語音，自然語言這類數據的表徵上，完美與深度神經網路的表徵能力契合。比如圖像中，最小的表徵單元為像素，由像素構成一些基本線段，構成物體邊緣、輪廓，再構成物體部件，最後構成物體（當然這個過程可以更加細緻）。

但是，深度學習在實際的研究和應用中，需要大量的調參，因此不少人稱深度學習調參為一門「煉丹術」；再者，深度學習參數數量一般比較龐大，對數據集的規模有較大的需求。因此，才有了這篇 gcForest 演算法的嘗試，基於決策樹的集成模型(Decision Tree based Ensemble Model)，和深度學習類似，具有很好的表徵學習能力，同時降低調參難度（超參數規模很小，一套超參數，可以在不同數據集上表現出較好的性能），且對在小的數據集上表現優越。

後面對演算法的幾個關鍵組件：級聯森林，多粒度滑動窗口掃描，整體過程結合自己的一些經驗進行。

Fig.1 對每個隨機森林得到的類分布取平均值，然後哪個類的概率最大就是哪個類。

Cascade Forest Structure （級聯森林）

模擬神經網路的分層結構，級聯森林每一層使用一組 Forest 來模擬表徵，且每一層的森林會使用上一層的信息，作為自己的輸入信息，同時其輸出為下一層提供輸入信息(這是一種表徵學習的思想，神經網路里用卷積，用 MLP ，這裡使用 forest 而已， GBDT/XGBoost 等其他的模型都可以放到這種級聯的結構中來，它可以看成是一種結構化的 Ensemble of Ensemble Model)。

具體的，如圖 Fig.1所示，每一層包含2個完全隨機-森林和2個普通隨機森林；完全森林包含500棵完全隨機樹(完全隨機森林參考了 icForest 的構造，隨機選擇樣本子集，且在分割時，隨機選擇特徵，直到葉子結點只包含一個類別)；普通隨機森林也包含500棵樹，每棵樹隨機取 sqrt(d) 個特徵，通過 gini 係數構建； 每個隨機森林會輸出維度為 K 的類概率分布（要預測 K 個類別），每一層隨機森林會輸出(2+2) K 個類概率分布；這4K 個輸出將與原始的特徵向量連在一起，作為下層隨機森林的輸入（隨機森林輸出類概率的過程如圖 Fig.2所示，過程比較簡單，不再詳述。）；為降低過擬合風險，每一個隨機森林的 K 個輸出，會經過 K-fold 交叉驗證（取 K-1次的平均值）；森林停止增長的判定（cascade 的級數自動根據數據設定）：每增加一層隨機森林後，使用驗證集對已經生成的整個模型進行性能驗證，若性能沒有明顯的增長即停止增長。

Fig.2 Illustration of class vector generation. Different marks in leaf nodes imply different classes.（某個樣本 x 落在某個葉子節點，計算該葉子節點的類概率分布，然後對所有樹得到的概率分布取平均，即得到該森林的類分布概率。）

Multi-grained Scanning （多粒度滑動窗口掃描）

將原始特徵通過多粒度掃描後，可以得到增強的特徵向量，包含了特徵的局部結構的多種尺度。

Fig.3 多粒度滑動窗口掃描過程，上半部分針對1D 向量特徵，下半部分針對2D 類圖像特徵。

如圖 Fig.2所示，對於維度為400的訓練樣本，預測3個類，用大小為100的滑動窗口掃描，可以得到301個滑動樣本實例，每個實例維度為100；若用大小為200的滑動窗口，則可以得到201m 個樣本實例，每個實例的維度為200；（對於1D 向量特徵， N=D-W+1； N 為滑動樣本實例， D 為原始特徵維度， W 為窗口大小；對於2D 類圖像特徵， N=(D1-W1+1)(D2-W2+1)，其中 D1， D2對應輸入的長度和寬度， W1和 W2對應在長度和寬度上的採樣窗口大小）

以100的窗口為例，得到了301個樣本實例，每個實例代表了一種局部結構或者亞採樣樣本，假如訓練集有 m 個樣本，則每個實例可以得到 m 個訓練樣本，這 m 個100維的特徵作為隨機森林的輸入，可以得到一個3維的類概率分布；那麼所有301個實例（局部結構），則可以得到301*3=906維的類概率分布，這些類概率分布連在一起作為特徵呈現，輸入到下一級隨機森林；

這裡，其實可以看到為什麼這個方法能夠較好應對小樣本集，可以看到多粒度滑動窗口的方式，其功能類似於做了一次上採樣操作，一個樣本變成 N 個滑動實例樣本，並且這些樣本一定程度代表了原始樣本的局部結構，因此多粒度滑動窗口操作，可以稱之為結構化上採樣，增強了模型的表徵能力。

Fig.4 The overall procedure of gcForest. Suppose there are three classes to predict, raw features are 400-dim, three sliding window scales.（400維特徵，3個類。第一步是多粒度特徵生成，隨機森林的個數為2；第二步是級聯隨機森林生成，隨機森林個數為4。）

整個流程

實驗效果

4 個完全隨機森林和4個普通隨機森林（每個森林500棵樹），3-FOLD 交叉驗證用來產生類分布向量，先通過將訓練集分為增長集（80%）和估計集（20%），增長集用於構建級聯森林，估計集用於確定是否停止增長，在停止增長後，將增長集和估計集合併，重新調整已經生成的級聯隨機森林；滑動窗口（三種， d/16,d/8,d/4， d 為特徵維度）從論文給出的實驗結果來看，性能是很不錯的，在測試的數據集中，相當於或者好於深度神經網路模型。

總結

整體來講， gcForest 嘗試從深度學習/機器學習的本質表徵學習入手，借鑒了深度學習的分層結構，利用 Ensemble of Decision Tree 來建模每一層表徵，同時利用多粒度滑動窗口，學習數據更為豐富的表徵信息。當然這是一種思想，級聯森林中，森林具體使用什麼模型，可以根據實際應用的計算資源、性能需求綜合考慮，從 Random Forest, GBDT, XGboost 等模型選擇即可。

這個演算法直觀上，可以進行一些可能的改進，比如最終預測結果中，可以由級聯森林中間層預測的加權，而不是只用最後的特徵輸出（類似於深度學習中使用層次化特徵的過程）；級聯森林中間層的表徵學習過程還可以做一些變化。回頭需要測試一下在大量樣本的情況下， gcForest 與神經網路模型的性能對比。

參考文獻

[1] Zhihua Zhou and Ji Feng, Deep Forest: Towards An Alternative to Deep Neural Networks, IJCAI, 2017, https://arxiv.org/abs/1702.08835v2 (V2)[2] https://arxiv.org/pdf/1702.08835v1.pdf (V1)[3] Github地址: https://github.com/kingfengji/gcForest

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！