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

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

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

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

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

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

舉例來(lái)說(shuō)，去年南大周志華教授等人提出“深度森林”，最初采用多層級(jí)聯(lián)決策樹(shù)結(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、帝國(guó)理工和微軟的研究人員合作，提出了另一種新的思路，他們將決策樹(shù)和神經(jīng)網(wǎng)絡(luò)結(jié)合到一起，生成了一種完全可微分的決策樹(shù)（由transformer、router和solver組成）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

模型拓展與操作

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

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

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

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

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

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

概率模型和推理

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

其中，

實(shí)驗(yàn)結(jié)果：

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

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

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

摘要

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