周志華新論文：首個基於決策樹集成的自動編碼器，表現優於DNN

翻譯 | AI科技大本營（rgznai100）

參與 | 周翔、reason_W成龍，Shawn

今年 2 月，南京大學的周志華教授和他的學生 Ji Feng 提出了一種不同於深度神經網路（DNN）的 Deep Forest 模型——gcForest，這是一種決策樹集成的方法，較之深度神經網路有很強的競爭力。深度神經網路需要花大力氣調參，相比之下 gcForest 要容易訓練得多。此外，深度神經網路需要大規模的訓練數據，而 gcForest 在僅有小規模訓練數據的情況下也照常運轉。不僅如此，作為一種基於決策樹的方法，gcForest 在理論分析方面也應當比深度神經網路更加容易。

半年之後，這兩位學者又跟 DNN 杠上了，提出了首個基於決策樹集成（Tree Ensamble）演算法的自動編碼器——EncoderForest （簡稱 eForest）。

通常，自動編碼這個重要任務都是通過卷積神經網路（CNN）等深度神經網路（DNN）來實現的。但是周志華教授在論文中表示，他們提出的這種演算法可以使森林（forests）能夠利用決策樹決策路徑（decision paths）定義的等效類（equivalent classes）別來進行反向重構（backward reconstruction），並且證明了這種演算法在監督學習和無監督學習中的可行性。

實驗結果表明，與 DNN 自動編碼器相比，eForest 能夠不僅訓練速度更快，而且數據重構的錯誤率根底，此外，模型本身對損壞有一定的容忍度，並且可以重複使用。

不管是 gcForest 還是 eForest，這種基於決策樹集成的方法真的有取代 DNN 的潛力嗎？讓我們一起看看這篇論文，或許你會有更好的了解。（註：本文截取論文重點進行編譯，非全文編譯。如需觀摩原文，請查閱文末鏈接）

簡介

自動編碼器這類模型的作用是將輸入映射到隱藏空間，然後再將其映射到原始空間，期間，重構失誤率越小越好。在過去，構建這樣的模型往往需要用到神經網路。例如，基於神經網路的自動編碼器通常由一個編碼器和一個解碼器構成。編碼器將輸入映射到隱藏層，然後解碼器將輸入映射到輸入空間。通過將這兩步連接在一起，並將重構錯誤作為學習目標，我們可以使用反向傳播演算法來訓練此類模型。這種演算法被廣泛應用於降維、表徵學習以及生成模型近期的一些工作（例如變分自動編碼器）。

集成學習（Ensemble learning）是一種強大的學習方式，它可以訓練多個學習網路，並將它們結合起來處理問題。它廣泛應用於很多種任務，並且都有著很好的表現。決策樹集成演算法或者森林演算法（如隨機森林）是適用於監督學習的最好方法之一。其他成功的決策樹集成演算法還有基於梯度的決策樹（gradient based decision trees ，GBDT），這種演算法的效果在過去 10 年間得到了很好的證明。除了監督學習任務之外，決策樹集成演算法還在其他任務中大顯身手，例如isolation forest，這是一種可以有效檢測異常的無監督學習方法。另外，最近提出的基於森林的深度模型也在多種任務中表現出與 DNN 比肩的性能，但是它的超參數數量更少。

在本論文中，我們提出了 eForest，它可以使決策樹集成演算法執行向前編碼和向後解碼的操作，這種自動編碼器既能以監督學習又可以以無監督學習的方式進行訓練。實驗證明，eForest 有以下優勢：

準確：它在實驗中的重構錯誤率比基於多層感知器（MLP）或卷積神經網路（CNN）的自動編碼器更低。

高效：eForest 在 KNL（多核 CPU）上的運行速度甚至比 CNN 自動編碼器在 Titan-X GPU 上訓練速度還快。

對損壞的容忍度：訓練後的模型即使有部分損壞也能正常工作。

可重複利用：用一個數據集訓練的模型可以被直接應用在相同域中的其他數據集上。

方法

自動編碼器有兩個基本功能：編碼和解碼。對森林來說，編碼是沒有困難的，因為至少上面的葉節點信息就可以被認為是一種編碼方式；更不用說，節點的子集或者甚至路徑分支都能夠提供更多的編碼信息。

首先，我們給出了 EncoderForest 的編碼過程。給定一個訓練過的 T 棵樹的決策樹集成模型（ tree ensemble model），前向編碼過程用來接收輸入數據，並將該數據傳遞給集成中每棵樹的根節點。一旦數據遍歷完所有樹的葉節點，程序將返回一個 T 維向量，其中每個元素 t 是對應的樹 t 中葉節點的整數索引。

演算法 1 展示了一種更具體的前向編碼演算法。需要注意的是，對於樹來說，該編碼過程與涉及到如何分割節點的特定學習規則是相互獨立的。例如，決策規則既可以在諸如隨機森林這樣的監督集合中學習，也可以在比如完全隨機樹這樣的無監督集合中學習。

另一方面，解碼功能則沒有那麼明顯。事實上，森林通常用於從每棵樹的根節點到葉子的前向預測，而如何進行後向重建則是不清楚的，例如，如何通過葉子獲得的信息合成原始樣本。

假設我們正在處理一個具有四個屬性的二元分類任務。第一個和第二個屬性是數字屬性，第三個是布爾屬性，值為 YES 或 NO；第四個是三值屬性值為 RED、BLUE 或 GREEN。給定一個對象 x，令 xi 表示 x 的第 i 個屬性的值。

現在，假設在編碼步驟中，我們已經生成了一個圖1所示的森林。現在，我們只知道對象 x 所在的葉節點，即圖一中的紅色節點，並且希望重構 x。在這裡，我們提出了一個有效但簡單、甚至是最簡單的森林後向重建策略。首先，每個葉節點實際上都對應於一條來自根節點的路徑，我們可以根據葉節點識別路徑，同時避免不確定性。

例如，在圖1中，識別出來的路徑用紅色突出顯示。然後，每個路徑對應一個符號規則；比如，突出顯示的樹形路徑對應以下規則集，RULEi 對應森林中第 i 個樹的路徑，其中符號「:」表示否定判斷：

然後，我們可以推導出最大相容規則（MCR）。MCR 是這樣一個規則，即每個成員的覆蓋範圍都不能被放大，否則就會發生不兼容的問題。例如，從上面的規則集中，我們可以得到這樣的 MCR：

對於 MCR 的每個組成部分，如（2 ≥ x2 ≥ 1:5），它的覆蓋範圍都不能擴大；比如，如果將其放大到（3 ≥ x2 ≥ 1:5），它就會與 RULE2 中的條件（x2 ≥ 2）衝突。演算法2對這一規則給出了更詳細的描述。

以下定理的證明非常容易，因此我們在本文中省略了證明過程。

定理1：原始樣本必須位於由 MCR 定義的輸入區域中。

所以，在獲得 MCR 後，我們才可以重建原始樣本。對於諸如 x3 和 x4 的這樣的分類屬性來說，原始樣本在 MCR 中必須取這些值；對於數值屬性來說，如 x2，我們可以選擇其中具有代表性的值，如（2, 1.5）中的平均值。因此，重建後的樣本就是 x = [0.55, 1.75, GREEN, YES]。注意，對於數值屬性來說，我們有很多替代的方法都可以進行重建，比如中值、最大值、最小值，甚至可以計算它的直方圖。

鑒於以上描述，現在我們給出 eForest 的後向解碼過程。具體來說，給定一個訓練好的 T 棵樹的森林，同時對一個特定數據，有 RT（T 為上標）中的前向編碼 xenc（enc 為下標）。後向解碼將首先通過 xenc 中的每個元素定位單個葉節點，然後對於對應的決策路徑，獲得相應的 T 個決策規則。 然後，通過計算 MCR，我們可以將 xenc 返回給輸入區域中的 xdec。演算法3中給出了具體的演算法。

通過前向編碼和後向編碼操作，eForest 就可以實現自動編碼任務。另外，儘管超出了本文的範圍，eForest 模型可能給出一些關於決策樹集成模型的表徵學習能力的理論性的洞察，並且有助於設計深層森林的新模型。

實驗

1）圖像重建

我們分別評測了 eForest 在監督集合和非監督集合里的表現。在實驗中，我們採用隨機森林（Random Forest）來構建監督森林（supervised forest），採用完全隨機森林來（completely-random forest ）構建非監督森林（unsupervised forest）。

可以看出，eForest 的表現最好。我們使用了 Keras 文檔推薦的用於圖像自動編碼的架構，並通過交叉驗證仔細調試了其他的超參數，但是在 CIFAR-10 數據集上，基於 CNN 的自動編碼器的表現並不好。我們相信，DNN 自動編碼器可以通過進一步的調整來提高性能，不過，eForest 自動編碼器不需要精心調整參數就可以表現的很好。

值得注意的是，在具有相同的 trees 的情況下，非監督 eForest 比監督 eForest 表現更好。請注意，每個決策樹路徑都對應著一個規則，而較長的規則意味著更加嚴格定義的 MCR。我們推測，更嚴格的 MCR 可能會讓重建更加準確。因此，具有較長的 tree depth 的森林可能會有更好的表現。

實驗結果也正面支持了我們的推測。如表2所示，非監督 eForest 的平均深度確實更長。

2）文字重建

注意，DNN 自動編碼器主要用於圖像，如果要用在文本領域，則需要增加一些額外的機制，比如通過嵌入 word2vec 對文字進行預處理。在本次實驗中，我們想要研究模型直接在文本數據上自動編碼的性能表現。

我們將餘弦距離（Cosine distance）作為評判標準，餘弦距離越小越好。

從上述結果可以看出，eForest 在文本數據重建任務中也有著上佳的表現。另外要注意的是，僅僅使用 10% 的表徵位數（bits），eForest 就已經能夠非常準確地重建原始輸入。這個結果展示了 eForest 在壓縮數據方面的前景。

3）計算效率

作為樹組合模型的共通優勢，並行實現同樣也適用於 eForest。我們在單個 KNL-7250（英特爾 XEON Phi 多核產品系列）上運行 eForest，與串列計算相比，我們在無監督集合中訓練 1000 棵決策樹時實現了 67.7 倍的加速。

從表4中可以看出，與基於 DNN 的自動編碼器相比，eForest 的訓練速度快 100 倍，但是編碼速度卻更慢。我們希望未來通過優化可以加速 eForest 的解碼速度。

4）對的損壞的容忍度

在某些情況下，模型會因為各種原因（如內存或磁碟故障）而部分損壞。然而，如果這種模型在受到損壞的情況下仍然能夠運行，那麼說明這個模型具備魯棒性。而 eForest 的自動編碼天生就具備魯棒性，因為在森林只有一個樹的子集的時候，我們仍然可以預測 MCR。

上圖的結果表明，與 MLP-AE 相比，eForest 對損壞的容忍度更高，其中，又數 unsupervised eForest 的表現最好。

5）eForest的模型重用性

在開放的環境中，用於編碼/解碼的測試數據可能和訓練數據具有不同的分布。在本節中，我們測試了模型重複使用的能力，其目的是在一個數據集中訓練一個模型，並在另一個數據集中重用它，而無需任何修改或者重新訓練。在這種情況下，模型重用的能力是未來機器學習發展的重要特性。

具體來說，我們是這樣評估模型的重用能力的。我們在 CIFAR-10 數據集（已經轉換和重新定標成了28×28的灰度數據）上訓練了一個無監督和一個有監督的 eForest ，每個 eForest 由1000棵樹組成，然後使用同一個模型對 MNIST 測試數據集中的數據進行了編碼/解碼。類似地，我們也在 MNIST 數據集上訓練了兩個這樣的由 1000 棵樹組成的 eForest，並在 Omniglot 數據集上直接進行了編碼/解碼的性能。為了公平比較，我們在相同的數據集上訓練了一個 CNN自動編碼器和一個 MLP 自動編碼器，且沒有進行微調。MLP/CNN-AE 的架構和訓練過程與前面的部分相同。 最後，我們用 MSE 來進行性能評估。

一些隨機抽取的重建樣本如圖4所示，整個測試集的數字化的評估見表5。可以看出，在 CIFAR-10 上訓練的 eForest 可以在 MNIST 數據集上更好地執行編碼/解碼任務，而且這兩個數據集完全不同。它顯示了 eForest 模型重用的泛化能力。

總結

在該篇論文中，我們提出了 EncoderForest（簡稱 eForest），它是第一個基於自動編碼器模型的樹集合模型：通過設計一個有效的過程，使得森林能夠通過使用由樹的決策路徑定義的 MCR（Maximal-Compatible Rule，最大相容規則）來重建原始路徑。

實驗證明，eForest 除了在精度和速度方面都表現良好，以及具備一定的魯棒性之外，還能夠重複使用。需要特別指出的是，在重建文本數據時，僅僅需要 10% 的輸入位（input bits），該模型依然能夠以很高的精度重建原始數據。

eForest 的另一個優點在於，它可以直接應用於符號屬性或者混合屬性的數據，而不需要將符號屬性的數據轉換成數字屬性的數據。考慮到這種轉換過程通常伴隨著信息丟失和額外偏差，因此 eForest 的這種特性具有重要意義。

更多資訊請關注微信公眾號：AI科技大本營（rgznai100）

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