UCL等提出完全可微自適應神經樹：神經網路與決策樹完美結合

作者：由新智元發表于曲藝時間：2018-07-31

UCL、帝國理工和微軟的研究人員合作，將神經網路與決策樹結合在一起，提出了一種新的自適應神經樹模型ANT，打破往侷限，可以基於BP演算法做訓練，在MNIST和CIFAR-10資料集上的準確率高達到99%和90%。

神經網路的成功關鍵在於其表示學習的能力。但是隨著網路深度的增加，模型的容量和複雜度也不斷提高，訓練和調參耗時耗力。

另一方面，決策樹模型透過學習資料的分層結構，可以根據資料集的性質調整模型的複雜度。決策樹的可解釋性更高，無論是大資料還是小資料表現都很好。

如何借鑑兩者的優缺點，設計新的深度學習模型，是目前學術界關心的課題之一。

舉例來說，去年南大周志華教授等人提出“深度森林”，最初

採用多層級聯決策樹結構（gcForest）

，探索深度神經網路以外的深度模型。如今，深度深林系列已經發表了三篇論文，

第三篇提出了可做表示學習的多層GBDT森林（mGBDT）

，在很多神經網路不適合的應用領域中具有巨大的潛力。

日前，UCL、帝國理工和微軟的研究人員合作，提出了另一種新的思路，

他們將決策樹和神經網路結合到一起，生成了一種完全可微分的決策樹

（由transformer、router和solver組成）。

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

自適應神經樹結合了神經網路和決策樹的優點，尤其在處理分層資料結構方面，在CIFAR-10資料集上分類取得了99%的準確率。

在 refinement 之前（a）和之後（b），ANT各個節點處的類別分佈（紅色）和路徑機率（藍色）。（a）表明學習模型學會了可解釋的層次結構，在同一分支上對語義相似的影象進行分組。（b）表明 refinement 階段極化路徑機率，修剪分支。來源：研究論文

論文共同第一作者、帝國理工學院博士生Kai Arulkumaran表示，更寬泛地看，ANT也屬於自適應計算（adaptive computation paradigm）的一種。由於資料的性質是各不相同的，因此我們在處理這些資料時，也要考慮不同的方式。

新智元亦採訪了“深度森林”系列研究的參與者之一、南京大學博士生馮霽。馮霽表示，

這篇工作這是基於軟決策樹（可微分決策樹）這條路的一個最新探索

。具體而言，將神經網路同時嵌入到決策路徑和節點中，以提升單顆決策樹的能力。由於該模型可微分，整個系統可透過BP演算法進行訓練。

“ANT的出發點與mGBDT類似，都是期望將神經網路的表示學習和決策樹的特點做一個結合，不過，ANT依舊依賴神經網路BP演算法進行的實現，”馮霽說：“而

深度森林（gcForest/mGBDT）的目的是探索構建多層不可微分系統的能力

，換言之，沒有放棄樹模型非參/不可微這個特性，二者的動機和目標有所不同。”

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

ANT：結合神經網路和決策樹，各取雙方的優點

神經網路（NN）和決策樹（DT）都是強大的機器學習模型，在學術和商業應用上都取得了一定的成功。然而，這兩種方法通常具有互斥的優點和侷限性。

NN的特點是透過非線性變換的組合來學習資料的

層次表示(hierarchical representation)

，與其他機器學習模型相比，一定程度上減輕了對特徵工程的需求。此外，NN還使用隨機最佳化器（如隨機梯度下降）進行訓練，使訓練能夠擴充套件到大型資料集。因此，藉助現代硬體，可以在大型資料集中訓練多層NN，以前所未有的精確度解決目標檢測、語音識別等眾多問題。然而，它們的結構通常需要手動設計並且對每個任務和資料集都要進行修整。對於大型模型來說，由於每個樣本都會涉及網路中的每一部分，因此

推理(reasoning)

也是很重要的，例如

容量(capacity)

的增加會導致計算比例的增加。

DT的特點是透過資料驅動的體系結構，在預先指定的特徵上學習層次結構。一顆決策樹會學習如何分割輸入空間，以便每個子集中的線性模型可以對資料做出解釋。與標準的NN相比，DT的結構是基於訓練資料進行最佳化的，因此在資料稀缺的情況下是十分有幫助的。由於每個輸入樣本只使用樹中的一個

根到葉

（root-to-leaf）的路徑，因此DT是享有

輕量級推理

（lightweight inference）的。然而，在使用DT的成功應用中，往往需要手動設計好的資料特徵。由於DT通常使用簡單的路徑函式，它在

表達能力

（expressivity）方面是具有侷限性的，例如

軸對齊

（axis-aligned）特徵的拆分。用於最佳化

硬分割槽

（hard partitioning）的損失函式是不可微的，這就阻礙了基於梯度下降最佳化策略的使用，從而導致分割函式變得更加複雜。目前增加容量的技術主要是一些整合方法，例如隨機森林（RF）和梯度提升樹（GBT）等。

為結合NN和DT的優點，提出一種叫自適應神經樹（ANT）的方法，主要包括兩個關鍵創新點：

一種新穎的DT形式

：

計算路徑

（computational path）和

路由決策

（routing decision）由NN來表示；

基於反向傳播的訓練演算法

：從簡單的模組開始對結構進行擴充套件。ANT還解決了過去一些方法的侷限性，如下圖所示：

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

表示學習

（Representation learning）：由於ANT中的每個

根到葉

（root-to-leaf）路徑都是NN，因此可以透過基於梯度的最佳化來

端到端

（end-to-end）地學習特徵。訓練演算法也適用於SGD。

結構學習

（Architecture learning）：透過逐步增長的ANT，結構可以適應資料的可用性和複雜性。增長過程可以看作是神經結構搜尋的一種形式。

輕量級推理

（Lightweight Inference）：在推理時，ANT執行

條件計算

（conditional computation），基於每個樣本，在樹中選擇一個

根到葉

（root-to-leaf）的路徑，且只啟用模型的一個子集。

自適應神經樹結構：路由器、轉換器、求解器

自適應神經樹（ANT）定義：用

深度卷積表示

（representation）來增強DT的一種形式。該方法旨在從一組被標籤的樣本N（訓練資料）（x（1），y（1）），。。。（x（n），y（n））∈

學習條件分p（x|y）。值得注意的是，ANT也可以擴充套件到其它需要機器學習的任務中。

模型拓展與操作

簡而言之，ANT是一個樹形結構模型，其特點是輸入空間X擁有一組

分層分割槽

（hierarchical partition）、一系列非線性轉換以及在各個分量區域中有獨立的預測模型。更正式地說，ANT可以定義為一對（T，O），其中T表示模型拓撲，O表示操作集。

將T約束為二叉樹的例項，並定義為一組

有限圖

（finite graph），其中，每個節點要麼是內部節點，要麼是葉子節點，並且是一個父節點的子節點（除了無父節點外）。將樹的拓撲定義為T：={N，ε}，其中N是所有節點的集合，ε是邊的集合。沒有孩子的節點是葉子節Nleaf，其它所有節點都是內部節Nint。每個內部節點都有兩個孩子節點，表示leftj和rightj。與標準樹不同，ε包含一條能夠將輸入資料X與根節點連線起來的邊。如下圖所示：

一個ANT是基於下面三個可微操作的基本模組構建的：

路由器(Router)

，R：每個內部節點j∈Nint都有一個路由模組，將來自傳入邊（incomming edge）的樣本傳送到左子節點或右子節點。

轉換器(transformer)

，T：樹中的每條邊e∈ε都有一個或一組多轉換模組（ multiple transformer module）。每個轉換teψ∈T都是一個非線性函式，將前一個模組中的樣本進行轉換並傳遞給下一個模組。

求解器(Solver)

，S：每個求解器模組分配一個葉子節點，該求解器模組對變換的輸入資料進行操作並輸出對條件分佈p（y|x）的估計。

機率模型和推理

ANT對條件分佈p（y|x）進行建模並作為

層次混合專家網路

（HME），每個HME被定義為一個NN並對應於樹中特定的根到葉（root-to-leaf）路徑。假設我們有L個葉子節點，則完整的預測分佈為：

其中，

實驗結果：

其中，列“Error （Full）” 和 “Error （Path）”表示基於

全分佈

和

單路徑推斷

（single-pathinference）的預測分類錯誤。列“Params（Full）”和“Params（Path）”分別表示模型中的引數總數和單路徑推斷的引數平均值。“Ensemble Size”表示整合的規模。“-”表示空值，“+”表示與ANT在相同的實驗裝置進行訓練的方法， “*”表示引數是使用預先訓練的CNN初始化的。