結(jié)合深度神經(jīng)網(wǎng)絡(luò)和決策樹的完美方案

UCL、帝國理工和微軟的研究人員合作，將神經(jīng)網(wǎng)絡(luò)與決策樹結(jié)合在一起，提出了一種新的自適應(yīng)神經(jīng)樹模型ANT，打破往局限，可以基于BP算法做訓(xùn)練，在MNIST和CIFAR-10數(shù)據(jù)集上的準確率高達到99%和90%。

將神經(jīng)網(wǎng)絡(luò)和決策樹結(jié)合在一起的自適應(yīng)神經(jīng)樹

神經(jīng)網(wǎng)絡(luò)的成功關(guān)鍵在于其表示學(xué)習(xí)的能力。但是隨著網(wǎng)絡(luò)深度的增加，模型的容量和復(fù)雜度也不斷提高，訓(xùn)練和調(diào)參耗時耗力。

另一方面，決策樹模型通過學(xué)習(xí)數(shù)據(jù)的分層結(jié)構(gòu)，可以根據(jù)數(shù)據(jù)集的性質(zhì)調(diào)整模型的復(fù)雜度。決策樹的可解釋性更高，無論是大數(shù)據(jù)還是小數(shù)據(jù)表現(xiàn)都很好。

如何借鑒兩者的優(yōu)缺點，設(shè)計新的深度學(xué)習(xí)模型，是目前學(xué)術(shù)界關(guān)心的課題之一。

舉例來說，去年南大周志華教授等人提出“深度森林”，最初采用多層級聯(lián)決策樹結(jié)構(gòu)（gcForest），探索深度神經(jīng)網(wǎng)絡(luò)以外的深度模型。如今，深度深林系列已經(jīng)發(fā)表了三篇論文，第三篇提出了可做表示學(xué)習(xí)的多層GBDT森林（mGBDT），在很多神經(jīng)網(wǎng)絡(luò)不適合的應(yīng)用領(lǐng)域中具有巨大的潛力。

日前，UCL、帝國理工和微軟的研究人員合作，提出了另一種新的思路，他們將決策樹和神經(jīng)網(wǎng)絡(luò)結(jié)合到一起，生成了一種完全可微分的決策樹（由transformer、router和solver組成）。

他們將這種新的模型稱為“自適應(yīng)神經(jīng)樹”（Adaptive Neural Trees，ANT），這種新模型能夠根據(jù)驗證誤差，或者加深或者分叉。在推斷過程中，整個模型都可以作為一種較慢的分層混合專家系統(tǒng)，也可以是快速的決策樹模型。

自適應(yīng)神經(jīng)樹結(jié)合了神經(jīng)網(wǎng)絡(luò)和決策樹的優(yōu)點，尤其在處理分層數(shù)據(jù)結(jié)構(gòu)方面，在CIFAR-10數(shù)據(jù)集上分類取得了99%的準確率。

在 refinement 之前（a）和之后（b），ANT各個節(jié)點處的類別分布（紅色）和路徑概率（藍色）。（a）表明學(xué)習(xí)模型學(xué)會了可解釋的層次結(jié)構(gòu)，在同一分支上對語義相似的圖像進行分組。（b）表明 refinement 階段極化路徑概率，修剪分支。來源：研究論文

論文共同第一作者、帝國理工學(xué)院博士生Kai Arulkumaran表示，更寬泛地看，ANT也屬于自適應(yīng)計算（adaptive computation paradigm）的一種。由于數(shù)據(jù)的性質(zhì)是各不相同的，因此我們在處理這些數(shù)據(jù)時，也要考慮不同的方式。

新智元亦采訪了“深度森林”系列研究的參與者之一、南京大學(xué)博士生馮霽。馮霽表示，這篇工作這是基于軟決策樹（可微分決策樹）這條路的一個最新探索。具體而言，將神經(jīng)網(wǎng)絡(luò)同時嵌入到?jīng)Q策路徑和節(jié)點中，以提升單顆決策樹的能力。由于該模型可微分，整個系統(tǒng)可通過BP算法進行訓(xùn)練。

“ANT的出發(fā)點與mGBDT類似，都是期望將神經(jīng)網(wǎng)絡(luò)的表示學(xué)習(xí)和決策樹的特點做一個結(jié)合，不過，ANT依舊依賴神經(jīng)網(wǎng)絡(luò)BP算法進行的實現(xiàn)，”馮霽說：“而深度森林（gcForest/mGBDT）的目的是探索構(gòu)建多層不可微分系統(tǒng)的能力，換言之，沒有放棄樹模型非參/不可微這個特性，二者的動機和目標有所不同。”

ANT論文的其中一位作者、微軟研究院的Antonio Criminisi，在2011年與人合著了一本專著《決策森林：分類、回歸、密度估計、流形學(xué)習(xí)和半監(jiān)督學(xué)習(xí)的統(tǒng)一框架》，可以稱得上領(lǐng)域大牛。

ANT：結(jié)合神經(jīng)網(wǎng)絡(luò)和決策樹，各取雙方的優(yōu)點

神經(jīng)網(wǎng)絡(luò)(NN)和決策樹(DT)都是強大的機器學(xué)習(xí)模型，在學(xué)術(shù)和商業(yè)應(yīng)用上都取得了一定的成功。然而，這兩種方法通常具有互斥的優(yōu)點和局限性。

NN的特點是通過非線性變換的組合來學(xué)習(xí)數(shù)據(jù)的層次表示(hierarchical representation)，與其他機器學(xué)習(xí)模型相比，一定程度上減輕了對特征工程的需求。此外，NN還使用隨機優(yōu)化器(如隨機梯度下降)進行訓(xùn)練，使訓(xùn)練能夠擴展到大型數(shù)據(jù)集。因此，借助現(xiàn)代硬件，可以在大型數(shù)據(jù)集中訓(xùn)練多層NN，以前所未有的精確度解決目標檢測、語音識別等眾多問題。然而，它們的結(jié)構(gòu)通常需要手動設(shè)計并且對每個任務(wù)和數(shù)據(jù)集都要進行修整。對于大型模型來說，由于每個樣本都會涉及網(wǎng)絡(luò)中的每一部分，因此推理(reasoning)也是很重要的，例如容量(capacity)的增加會導(dǎo)致計算比例的增加。

DT的特點是通過數(shù)據(jù)驅(qū)動的體系結(jié)構(gòu)，在預(yù)先指定的特征上學(xué)習(xí)層次結(jié)構(gòu)。一顆決策樹會學(xué)習(xí)如何分割輸入空間，以便每個子集中的線性模型可以對數(shù)據(jù)做出解釋。與標準的NN相比，DT的結(jié)構(gòu)是基于訓(xùn)練數(shù)據(jù)進行優(yōu)化的，因此在數(shù)據(jù)稀缺的情況下是十分有幫助的。由于每個輸入樣本只使用樹中的一個根到葉(root-to-leaf)的路徑，因此DT是享有輕量級推理(lightweight inference)的。然而，在使用DT的成功應(yīng)用中，往往需要手動設(shè)計好的數(shù)據(jù)特征。由于DT通常使用簡單的路徑函數(shù)，它在表達能力(expressivity)方面是具有局限性的，例如軸對齊(axis-aligned)特征的拆分。用于優(yōu)化硬分區(qū)(hard partitioning)的損失函數(shù)是不可微的，這就阻礙了基于梯度下降優(yōu)化策略的使用，從而導(dǎo)致分割函數(shù)變得更加復(fù)雜。目前增加容量的技術(shù)主要是一些集成方法，例如隨機森林(RF)和梯度提升樹(GBT)等。

為結(jié)合NN和DT的優(yōu)點，提出一種叫自適應(yīng)神經(jīng)樹(ANT)的方法，主要包括兩個關(guān)鍵創(chuàng)新點：

一種新穎的DT形式：計算路徑(computational path)和路由決策(routing decision)由NN來表示；

基于反向傳播的訓(xùn)練算法：從簡單的模塊開始對結(jié)構(gòu)進行擴展。ANT還解決了過去一些方法的局限性，如下圖所示：

ANT從DT和NN中繼承了如下屬性：

表示學(xué)習(xí)(Representation learning)：由于ANT中的每個根到葉(root-to-leaf)路徑都是NN，因此可以通過基于梯度的優(yōu)化來端到端(end-to-end)地學(xué)習(xí)特征。訓(xùn)練算法也適用于SGD。

結(jié)構(gòu)學(xué)習(xí)(Architecture learning)：通過逐步增長的ANT，結(jié)構(gòu)可以適應(yīng)數(shù)據(jù)的可用性和復(fù)雜性。增長過程可以看作是神經(jīng)結(jié)構(gòu)搜索的一種形式。

輕量級推理(Lightweight Inference):在推理時，ANT執(zhí)行條件計算(conditional computation)，基于每個樣本，在樹中選擇一個根到葉(root-to-leaf)的路徑，且只激活模型的一個子集。

自適應(yīng)神經(jīng)樹結(jié)構(gòu)：路由器、轉(zhuǎn)換器、求解器

自適應(yīng)神經(jīng)樹(ANT)定義：用深度卷積表示(representation)來增強DT的一種形式。該方法旨在從一組被標簽的樣本N(訓(xùn)練數(shù)據(jù))(x(1),y(1)),...(x(n),y(n))∈X×Y學(xué)習(xí)條件分p(x|y)。值得注意的是，ANT也可以擴展到其它需要機器學(xué)習(xí)的任務(wù)中。

模型拓展與操作

簡而言之，ANT是一個樹形結(jié)構(gòu)模型，其特點是輸入空間X擁有一組分層分區(qū)(hierarchical partition)、一系列非線性轉(zhuǎn)換以及在各個分量區(qū)域中有獨立的預(yù)測模型。更正式地說，ANT可以定義為一對(T,O)，其中T表示模型拓撲，O表示操作集。

將T約束為二叉樹的實例，并定義為一組有限圖(finite graph)，其中，每個節(jié)點要么是內(nèi)部節(jié)點，要么是葉子節(jié)點，并且是一個父節(jié)點的子節(jié)點(除了無父節(jié)點外)。將樹的拓撲定義為T：={N,ε}，其中N是所有節(jié)點的集合，ε是邊的集合。沒有孩子的節(jié)點是葉子節(jié)Nleaf，其它所有節(jié)點都是內(nèi)部節(jié)Nint。每個內(nèi)部節(jié)點都有兩個孩子節(jié)點，表示leftj和rightj。與標準樹不同，ε包含一條能夠?qū)⑤斎霐?shù)據(jù)X與根節(jié)點連接起來的邊。如下圖所示：

一個ANT是基于下面三個可微操作的基本模塊構(gòu)建的:

路由器(Router),R：每個內(nèi)部節(jié)點j∈Nint都有一個路由模塊，將來自傳入邊(incomming edge)的樣本發(fā)送到左子節(jié)點或右子節(jié)點。

轉(zhuǎn)換器(transformer),T：樹中的每條邊e∈ε都有一個或一組多轉(zhuǎn)換模塊( multiple transformermodule)。每個轉(zhuǎn)換teψ∈T都是一個非線性函數(shù)，將前一個模塊中的樣本進行轉(zhuǎn)換并傳遞給下一個模塊。

求解器(Solver),S：每個求解器模塊分配一個葉子節(jié)點，該求解器模塊對變換的輸入數(shù)據(jù)進行操作并輸出對條件分布p(y|x)的估計。

概率模型和推理

ANT對條件分布p(y|x)進行建模并作為層次混合專家網(wǎng)絡(luò)(HME)，每個HME被定義為一個NN并對應(yīng)于樹中特定的根到葉(root-to-leaf)路徑。假設(shè)我們有L個葉子節(jié)點，則完整的預(yù)測分布為：

其中，

實驗結(jié)果：

其中，列“Error (Full)”和“Error (Path)”表示基于全分布和單路徑推斷(single-pathinference)的預(yù)測分類錯誤。列“Params(Full)”和“Params(Path)”分別表示模型中的參數(shù)總數(shù)和單路徑推斷的參數(shù)平均值?！癊nsemble Size”表示集成的規(guī)模?！?”表示空值，“+”表示與ANT在相同的實驗設(shè)備進行訓(xùn)練的方法，“*”表示參數(shù)是使用預(yù)先訓(xùn)練的CNN初始化的。

不同模型在MNIST和CIFAR-10上性能的比較

論文：自適應(yīng)神經(jīng)樹

摘要

深度神經(jīng)網(wǎng)絡(luò)和決策樹很大程度上是相互獨立的。通常，前者是用預(yù)先指定的體系結(jié)構(gòu)來進行表示學(xué)習(xí)（representation learning），而后者的特點是通過數(shù)據(jù)驅(qū)動的體系結(jié)構(gòu)，在預(yù)先指定的特征上學(xué)習(xí)層次結(jié)構(gòu)。通過自適應(yīng)神經(jīng)樹（Adaptive Neural Trees，ANT），一種將表示學(xué)習(xí)嵌入到?jīng)Q策樹的邊、路徑函數(shù)以及葉節(jié)點的模型，以及基于反向傳播的訓(xùn)練算法（可自適應(yīng)地從類似卷積層這樣的原始模塊對結(jié)構(gòu)進行擴展）將兩者進行結(jié)合。在MNIST和CIFAR-10數(shù)據(jù)集上的準確率分別達到了99%和90%。ANT的優(yōu)勢在于(i)可通過條件計算（conditional computation）進行更快的推斷；(ii)可通過分層聚類（hierarchical clustering）提高可解釋性；(iii)有一個可以適應(yīng)訓(xùn)練數(shù)據(jù)集規(guī)模和復(fù)雜性的機制。