機器學習-內建學習

(一)內建學習的基本概念

(二)Boosting

(三)随機森林

(四)結合政策

(五)多樣性

(六)梯度相關

這裡考綱隻要求(一)至(三)。

(零) 前置知識

0 基礎概念

0.1 伯努利實驗

伯努利試驗（Bernoulli trial）(或譯為白努利試驗)是隻有兩種可能結果（成功或失敗）的單次随機試驗，即對于一個随機變量X而言，

\[P_r[X=1] = p \\

P_r[X=0] = 1-p

在數學上，這樣的試驗是以随機變量為模型，而随機變量隻能有兩個值：0和1，1被認為是"成功"。在單次的伯努利試驗中，如果 p 是成功的機率，那麼将呈現伯努利分布，此時随機變量的期望值就是 p ，且其标準差$\sqrt{p(1-p)}$。

一個伯努利過程（Bernoulli process）是由重複出現獨立但是相同分布的伯努利試驗組成，例如抛硬币十次，而此時呈現之結果将呈現二項分布。

0.2 $Hodffding$(霍夫丁不等式)

　　霍夫丁不等式（Hoeffding's inequality）是機器學習的基礎理論，通過它可以推導出機器學習在理論上的可行性。霍夫丁不等式經常被應用于一些獨立分布的伯努利随機變量的重要特例中，這也是為什麼這個不等式在計算機科學以及組合數學中如此常見。

0.2.1 伯努利随機變量的特例

我們認為一個抛硬币時一個硬币A面朝上的機率為$p$，B面朝上的機率則為$1-p$。我們抛$n$次硬币，那麼A面朝上次數的期望值為$np$。那麼進一步我們可以知道，A面朝上的次數不超過k次的機率能夠被下面的表達式完全确定：

\[\mathbb{P}(H(n)\leq k) = \sum \limits_{i=0}^k \begin{pmatrix} n \\i\end{pmatrix}p^i(1-p)^{n-i}

這裡的$H(n)$為抛n次硬币其Ａ面朝上的次數。

對于某一$\varepsilon>0$，當$k=(p-\varepsilon)n$時，上面不等式确定的霍夫丁上界将會按照指數級變化：

\[\mathbb{P(H(n)} \leq (p-\varepsilon)n) \leq exp(-2\varepsilon^2n)

相似的，對于某一$\varepsilon>0$，當$k=(p+\varepsilon)n$，霍夫丁不等式的機率邊界同樣可以确定為:

\[\mathbb{P}(H(x) \geq (p+\varepsilon)n)　\leq exp(-2 \varepsilon^2n)

這樣根據上面兩個式子我們可以得到：

\[\mathbb{P}((p-\varepsilon)n \leq H(n) \leq (p+\varepsilon)n) \geq 1-2exp(-2\varepsilon^2n)

比如說現在我們令$\varepsilon = \sqrt{\frac{ln n}{n}}$，那麼可以得到

\[\mathbb{P}(|H(n) - pn|\leq\sqrt{nlnn}) \geq 1-2exp(-2ln2) = 1 - \frac{2}{n^2}

0.2.2 伯努利的普遍情況

現在令$X_1,X_2,...,X_n$為[0,1]的獨立随機變量，即$0\leq X_i \leq 1$。

我們定義這些變量的經驗均值為:

\[\overline{X} = \frac{1}{(X_1+X_2+...+X_n)}

在1963年霍夫丁提出該不等式，其中霍夫丁定理一中的一個不等式為：

\[\mathbb{P}(\overline{X}-E[\overline{X}] \geq t) \leq e^{-2nt^2}

當知道$X_i$嚴格的邊界範圍$a_i,b_i$(即$X_i$屬于[$a_i,b_i$])時，霍夫丁定理二更加廣泛：

\[\mathbb{P}(\overline{X}-E[\overline{X}] \geq t) \leq exp \left(-\frac{2n^2t^2}{\sum \limits_{i=1}^n(b_i-a_i)^2 }\right) \\

\mathbb{P}(\overline{X}-E[\overline{X}] \geq t) \leq 2exp \left(-\frac{2n^2t^2}{\sum \limits_{i=1}^n(b_i-a_i)^2 }\right)

其中$S_n = X_1 + X_2 +...+X_n$.

0.3 決策樹

0.3.1 決策樹簡介

在解釋随機森林前，需要先提一下決策樹。決策樹是一種很簡單的算法，他的解釋性強，也符合人類的直覺思維。這是一種基于if-then-else規則的有監督學習算法。

　　機器學習中，決策樹是一個預測模型；他代表的是對象屬性與對象值之間的一種映射關系。樹中每個節點表示某個對象，而每個分叉路徑則代表某個可能的屬性值，而每個葉節點則對應從根節點到該葉節點所經曆的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有複數輸出，可以建立獨立的決策樹以處理不同輸出。資料挖掘中決策樹是一種經常要用到的技術，可以用于分析資料，同樣也可以用來作預測。

　　從資料産生決策樹的機器學習技術叫做決策樹學習,通俗說就是決策樹。　

一個決策樹包含三種類型的節點：

1.決策節點：通常用矩形框來表示

2.機會節點：通常用圓圈來表示

3.終結點：通常用三角形來表示

　　決策樹學習也是資料挖掘中一個普通的方法。在這裡，每個決策樹都表述了一種樹型結構，它由它的分支來對該類型的對象依靠屬性進行分類。每個決策樹可以依靠對源資料庫的分割進行資料測試。這個過程可以遞歸式的對樹進行修剪。當不能再進行分割或一個單獨的類可以被應用于某一分支時，遞歸過程就完成了。另外，随機森林分類器将許多決策樹結合起來以提升分類的正确率。

0.3.2 決策樹類型

決策樹有幾種産生方法：

分類樹分析是當預計結果可能為離散類型（例如三個種類的花，輸赢等）使用的概念。
回歸樹分析是當局域結果可能為實數（例如房價，患者住院時間等）使用的概念。
CART分析是結合了上述二者的一個概念。CART是Classification And Regression Trees的縮寫.
CHAID（Chi-Square Automatic Interaction Detector）

0.3.3 決策樹的優點

相對于其他資料挖掘算法，決策樹在以下幾個方面擁有優勢：

決策樹易于了解和實作.人們在通過解釋後都有能力去了解決策樹所表達的意義。
對于決策樹，資料的準備往往是簡單或者是不必要的.其他的技術往往要求先把資料一般化，比如去掉多餘的或者空白的屬性。
能夠同時處理資料型和正常型屬性。其他的技術往往要求資料屬性的單一。
是一個白盒模型如果給定一個觀察的模型，那麼根據所産生的決策樹很容易推出相應的邏輯表達式。
易于通過靜态測試來對模型進行評測。表示有可能測量該模型的可信度。
在相對短的時間内能夠對大型資料源做出可行且效果良好的結果。

0.3.4 決策樹的缺點

對于那些各類别樣本數量不一緻的資料，在決策樹當中資訊增益的結果偏向于那些具有更多數值的特征。

(一) 內建學習的基本概念

1.0 什麼是內建學習?

　內建學習歸屬于機器學習，它是一種「訓練思路」，并不是某種具體的方法或者算法。

　現實生活中，大家都知道「人多力量大」，「3 個臭皮匠頂個諸葛亮」。而內建學習的核心思路就是「人多力量大」，它并沒有創造出新的算法，而是把已有的算法進行結合，進而得到更好的效果。

內建學習會挑選一些簡單的基礎模型進行組裝，組裝這些基礎模型的思路主要有 2 種方法：

bagging（bootstrap aggregating的縮寫，也稱作“套袋法”）
boosting

1.1 概述

　　監督學習算法通常被描述為執行搜尋假設空間的任務以找到合适的假設，該假設将對特定問題做出良好的預測。即使假設空間包含非常适合特定問題的假設，也可能很難找到一個很好的假設。內建學習結合多個假設，形成一個(希望)更好的假設。評估內建學習的預測通常需要比評估單個模型的預測更多的計算，是以內建可以被認為是通過執行大量額外計算來補償差的學習算法的方式。諸如決策樹之類的快速算法通常用于集合方法(如随機森林)，盡管較慢的算法也可以從內建方法中受益。

通過類比，內建技術也已用于無監督學習場景中，如共識聚類或異常檢測。

1.2 內建理論

　　內建學習本身是一種監督學習算法，因為它可以被訓練然後用于進行預測。是以，訓練後的內建模型代表了一個假設，但這個假設不一定被包含在建構它的模型的假設空間内。是以，可以正面內建學習在它們可以表示的功能方面具有更大的靈活性，理論上，這種靈活性使他們能夠比單一模型更多地過拟合訓練資料，但在實踐中，一些內建算法(如Bagging算法)傾向于減少對訓練資料過拟合相關的問題。

　　根據經驗，當模型之間存在顯著差異時，內建往往會産生更好的結果。是以，許多內建方法試圖促進它們組合的模型之間的多樣性。盡管可能不是直覺的，更随機的算法(如随機決策樹)可用于産生比非常有意識的算法(如熵減少決策樹)更強大的內建模型。然而，使用各種強大的學習算法已被證明是比使用試圖愚弄模型以促進多樣性的技術更有效。

1.3 內建模型大小

雖然內建中的組成分類器的數量對預測的準确性具有很大影響，但是解決該問題的研究數量比較有限。先驗地确定內建模型的大小以及大資料流的體積和速度使得這對于線上內建分類器來說更加重要，其中大多數統計測試被用于确定适當數量的元件。最近，理論架構表明對于內建模型存在理想數量的分類器，具有多于或少于該數量的分類器将使精度變差，這被稱為“內建建構效果遞減規律”。理論架構表明，使用與類标簽數相同的獨立分類器可以達到最高的準确率。

1.4 個體與內建

　　內建學習(ensemble learning)通過建構并集合多個學習器來完成學習任務，有時也被稱為多分類器系統(multi-classifier system)、基于委員會的學習(committee-based learning)等。

　　內建學習的一般結構：先産生一組“個體學習器”(individual learner)，再用某種政策将它們結合起來。

個體學習器通常由一個線程的學習算法從訓練資料産生，例如$C4.5$決策樹算法、BP神經網絡算法等。

此時內建中隻包含同種類型的個體學習器，例如“決策樹內建”中全是決策樹，“神經網絡內建”中全是神經網絡，這樣的內建是“同質”的(homogeneous)。

同質內建：同質內建中的個體學習器稱為“基學習器”（base learner），相應的學習算法為“基學習算法”（base learning algorithm）。

內建也可包含不同類型的個體學習器，例如同時包含決策樹和神經網絡，這樣的內建是“異質的”。

異質內建：異質內建中的個體學習器由不同的學習算法生成，稱為“元件學習器”（component learner）或直稱為“個體學習器”。

　　同質內建中的個體學習器亦稱為“基學習器”(base learner)，相應的學習算法稱為“基學習算法”(base learning algorithm)。內建也可包含不同類型的個體學習器，例如同時包含決策樹和神經網絡，這樣的內建是“異質”的(heterogenous)。

　　異質內建中的個體學習器由不同的學習算法生成，這時就不再由基學習算法；相應的，個體學習器一般不稱為基學習器，常稱為“元件學習器”(component learner)或直接稱為個體學習器。

　　內建學習通過将多個學習器進行結合，常可獲得比單一學習器顯著優越的泛化性能。這對“弱學習器”(weak learner)尤為明顯，是以內建學習的很多理論研究都是針對弱學習器進行的，而基學習器有時也被直接稱為弱學習器。但需注意的是，雖然從理論上來說使用弱學習器內建足以獲得好的性能，但在實踐中出于種種考慮，例如希望使用較少的個體學習器，或是重用關于常見學習器的一些經驗等，人們往往會使用比較強的學習器。

　考慮一個簡單的例子：在二分類任務中，假定三個分類器($h_1,h_2,h_3$)在三個測試樣本上的表現如下圖所示，

其中$“√”$表示分類正确，“×”表示分類錯誤，內建學習的結果通過投票法(voting)産生，即“少數服從多數”。

　　在下圖(a)中，每個分類器($h_1,h_2,h_3$)都隻有$66.6%$的精度，但內建學習卻達到了$100$%；

　　在下圖(b)中，三個分類器沒有差别，內建之後性能沒有提高；

　　在下圖(c)中，每個分類器的精度都隻有$33.3$％，內建學習的結果變得更糟。　　　

　　以上這個簡單的例子顯示出：要獲得好的內建，個體學習器應“好而不同”，即個體學習器要有一定的“準确性”，即學習器不能太壞，并且要有“多樣性”(diversity)，即學習器間具有差異。

　　我們來做個簡單的分析。考慮二分類問題$y∈\left\{-1,+1\right\}$和真實函數$f$，假定基分類器之間互相獨立（能提供較高的差異度），且錯誤率相等為$\epsilon$，即對每個基分類器$h_i$有

\[P(h_i(x)\neq f(x)) = \epsilon \quad \quad (8.1)

注意到$f(x)$為x的真實标記，而$h_i(x)$為基分類器$h_i$對$x$的預測标記，是以$h_i(x)\neq f(x)$表示預測标記與真實标記不相同的情況，即預測出錯，$P(h_i(x)\neq　f(x))$即為錯誤率

　假設內建通過簡單投票法結合$T$個基分類器，若有超過半數的基分類器正确，則內建分類就正确;

\[H(x) = sign \left(\sum \limits_{i=1}^T h_i(x) \right) \quad \quad (8.2)

注意到目前僅針對二分類問題$y∈\left\{-1,+1\right\}$，即預測标記$h_i(x)∈ \left\{-1,+1\right\}$。是以，若$T$個基分類器中預測輸出+1占半數以上，則$\sum \limits_{i=1}^Th_i(x)>0$；反之，若$T$個基分類器中預測輸出-1占半數以上，則$\sum \limits_{i=1}^Th_i(x)<0$。函數$sign(\cdot)$為符号函數，在$\cdot<0$時取值為-1，在$\cdot>0$時取值為+1，即函數$H(x)$與多數基分類器輸出一緻，即滿足多數投票，少數服從多數。

　假設基分類器的錯誤率互相獨立，則由$Hodffding$(霍夫丁)不等式可知，內建的錯誤率為

\[P(H(x)\neq f(x)) = \sum \limits_{k=1}^{\lfloor T/2 \rfloor}\begin{pmatrix}

T \\k\end{pmatrix}(1-\epsilon)^k \epsilon^{T-k} \\ \leq exp \left(-\frac{1}{2}T(1-2\epsilon)^2 \right) \quad \quad (8.3)

式(8.3)的推導

本節推導基于Hoeffding不等式。首先将本章課後習題8.1的式(8.43)變形如下：

　　　$P(H(T) \leq　\lfloor T/2 \rfloor) = \sum \limits_{k=1}^{\lfloor T/2 \rfloor}\begin{pmatrix} T \\k\end{pmatrix}(1 - \epsilon)^k \epsilon^{T-k}$

從式(8.43)到上式的符号變化包括$n \to T, k \to \lfloor T/2\rfloor, i \to k, p \to (1 - \epsilon)$。相應的，對應接下來的式(8.44),則對$\delta>0, \lfloor T/2 \rfloor = (1 - \epsilon - \delta)T$，有Hodeffding不等式

　　$P(H|T) \leq (1 - \epsilon - \delta)T = e^{-2\delta^2 T}$

對于$\lfloor T / 2\rfloor = (1 - \epsilon - \delta)T$，整理變形得$\delta$表達式

　　　$\delta = 1 - \epsilon - \frac{\lfloor T /2 \rfloor}{T}$

注意到內建學習要求基分類器泛化性能優于随機猜測的學習器，例如在二分類問題上精度略高于50%的分類器，即$\epsilon < 0.5$，是以$1 - \epsilon > \frac{1}{2}$；而$\frac{\lfloor T / 2\rfloor}{T} \leq \frac{1}{2}$(符号$\lfloor \cdot \rfloor$表示向下取整，“＝”在$T$為偶數時成立，若$T$為奇數，則一定是“<”)。是以

　　$P(H(T) \leq \lfloor T / 2\rfloor) = e^{-2\delta^2T} \leq e^{-2(1 - \epsilon - \frac{1}{2})^2T} = e^{-\frac{T}{2}(1 - 2\epsilon)^2}$

而根據式(8.2)中$H(x)$的含義，$H(T) \leq \lfloor T / 2\rfloor$(即$T$個基分類器中預測正确的個數不超過$\lfloor T /2\rfloor$，也就是預測錯誤)與$H(x) \neq f(x)$等價，至此，本式推導完畢。

上式顯示出，随着內建中個體分類器數目Ｔ的增大，內建的錯誤率将指數級下降，最終趨向于零。

　　然而我們必須注意到，上面的分析有一個關鍵假設：基學習器的誤差互相獨立。在現實任務中，個體學習器是為解決同一個問題訓練出來的，它們顯然不可能互相獨立!事實上，個體學習器的“準确性”和“多樣性”本身就存在沖突。一般的，準确性很高之後，要增加多樣性就需要犧牲準确性。事實上，如何産生并結合“好而不同”的個體學習器，恰是內建學習研究的核心。

　　根據個體學習器的生成方式，目前的內建學習方法大緻可分為兩大類，即個體學習器間存在強依賴關系、必須串行生成的序列化方法，以及個體學習器間不存在強依賴關系、可同時生成的并行化方法；前者的代表是$Boosting$，後者的代表是$Bagging$和“随機森林”(Random Forest)

(二) Boosting 提升方法

　　提升(Boosting)方法是一種常用的統計學習方法，應用廣泛且有效。在分類問題中，它通過改變訓練樣本的權重，學習多個分類器，并将這些分類器進行線性組合，提高分類的性能。

　　Boosting是一族可将弱學習器提升為強學習器的算法。這族算法的工作機制類似：

先從初始訓練集訓練出一個基學習器，再根據基學習器的表現對訓練樣本分布進行調整，使得先前基學習器做錯的訓練樣本在後續受到更多關注，然後基于調整後的樣本分布來訓練下一個基學習器；如此重複進行，直至基學習器數目達到事先指定的值Ｔ，最終将這Ｔ個基學習器進行權重結合。

　　Boosting是一種串行的工作機制，即個體學習器的訓練存在依賴關系，必須一步一步序列化進行。其基本思想是：增加前一個基學習器在訓練訓練過程中預測錯誤樣本的權重，使得後續基學習器更加關注這些打标錯誤的訓練樣本，盡可能糾正這些錯誤，一直向下串行直至産生需要的$T$個基學習器，Boosting最終對這$T$個學習器進行權重結合，産生學習器委員會。

2.0 提升方法的基本思路

　　提升方法基于這樣一種思想：對于一個複雜任務來說，将多個專家的判斷進行适當的綜合所得出的判斷，要比其中任何一個專家單獨的判斷好。實際上，這就是說“三個臭皮匠頂個諸葛亮”的道理。

　　曆史上，Kearns和Valiant首先提出了“強可學習(strongly learnable)”和“弱可學習(weakly learnable)”的概念。指出：在機率近似正确(probably approximately correct,PAC)學習的架構中，一個概念(一個類)，如果存在一個多項式的學習算法能夠學習它，并且正确率很高，那麼就稱這個概念是強可學習的；一個概念。如果存在一個多現實的學習算法能夠學習它，學習的正确率僅比随機猜測略好，那麼就稱這個概念是弱可學習的。非常有趣的是Schapire後來證明強可學習與弱可學習是等價的，也就是說，在PAC學習的架構下，一個概念是強可學習的充分必要條件是這個概念是弱可學習的。

　　這樣一來，問題便稱為，在學習中，如果已經發現了“弱學習算法”，那麼能否将它提升(boost)為“強學習算法”。大家知道，發現弱學習算法通常要比發現強學習算法容易得多。那麼如何具體實施提升，便成為開發提升方法時所要解決的問題。關于提升方法的研究有很多，有很多算法被提出。最具代表性的是AdaBoost算法(AdaBoost algorithm)。

　　對于分類問題而言，給定一個訓練樣本集，求比較粗糙的分類規則(弱分類器)要比求精确的分類規則(強分類器)容易得多。提升方法就是從弱學習算法出發，反複學習，得到一系列弱分類器(又稱為基本分類器)，然後組合這些分類器，構成一個強分類器。大多數的提升方法都是改變訓練資料的機率分布(訓練資料的權值分布)，針對不同的訓練資料分布調用一系列弱分類器。

這樣，對提升方法來說，有兩個問題需要回答：

一是在每一輪如何改變訓練資料的權值或機率分布；
二是如何将弱分類器組合成一個強分類器。

　　關于第一個問題的，AdaBoost的做法是，提高那些被前一輪弱分類器錯誤分類樣本的權值，而降低那些被正确分類樣本的權值。這樣一來，那些沒有得到正确分類的資料，由于其權值的加大而受到後一輪的弱分類器的更大關注。于是，分類問題被一系列的弱分類器“分而治之”。

　　至于第二個問題，即弱分類器的組合，AdaBoost采取權重多數表決的方法。具體地，加大分類誤差率小的弱分類器的權值，使其在表決中起到較大的作用，減小分類誤差率大的弱分類器的權值，使其在表決中起較小的作用。

　　AdaBoost的巧妙之處就在于它将這些想法自然且有效地實作在一種算法裡。

2.1 AdaBoost算法

Boosting族算法最著名、使用最為廣泛的就是AdaBoost，是以下面主要是對AdaBoost算法進行介紹。AdaBoost使用的是指數損失函數，是以AdaBoost的權值與樣本分布的更新都是圍繞着最小化指數損失函數進行的。

看到這裡回想一下之前的機器學習算法，不難發現機器學習的大部分帶參模型隻是改變了最優化目标中的損失函數：

如果損失函數是Square Loss，那就是最小二乘；
如果損失函數是Hinge Loss，那就是著名的SVM；
如果損失函數是log-Loss，那就是Logistic Regression。

定義基學習器的內建為權重結合，則有：$$H(x)=\sum_{t=1}^{T} \alpha_{t} h_{t}(x)$$ AdaBoost算法的指數損失函數定義為：$$\text{loss}{\exp }(h)=\mathbb{E}{x \sim \mathcal{D}, y}\left[e^{-y h(x)}\right]$$其中$-yh(x)$表示打标正确為負，打标錯誤為正。

具體說來，整個Adaboost疊代算法分為3步：

初始化訓練資料的權值分布。如果有$N$個樣本，則每一個訓練樣本最開始時都被賦予相同的權值：$1/N$。
訓練弱分類器。具體訓練過程中，如果某個樣本點已經被準确地分類，那麼在構造下一個訓練集中，它的權值就被降低；相反，如果某個樣本點沒有被準确地分類，那麼它的權值就得到提高。然後，權值更新過的樣本集被用于訓練下一個分類器，整個訓練過程如此疊代地進行下去。
将各個訓練得到的弱分類器組合成強分類器。各個弱分類器的訓練過程結束後，加大分類誤差率小的弱分類器的權重，使其在最終的分類函數中起着較大的決定作用，而降低分類誤差率大的弱分類器的權重，使其在最終的分類函數中起着較小的決定作用。

Boosting 的核心思路是 —— 挑選精英。

　　Boosting 和 bagging 最本質的差别在于他對基礎模型不是一緻對待的，而是經過不停的考驗和篩選來挑選出「精英」，然後給精英更多的投票權，表現不好的基礎模型則給較少的投票權，然後綜合所有人的投票得到最終結果。

大部分情況下，經過 boosting 得到的結果偏差（bias）更小。

具體過程：

通過加法模型将基礎模型進行線性的組合。
每一輪訓練都提升那些錯誤率小的基礎模型權重，同時減小錯誤率高的模型權重。
在每一輪改變訓練資料的權值或機率分布，通過提高那些在前一輪被弱分類器分錯樣例的權值，減小前一輪分對樣例的權值，來使得分類器對誤分的資料有較好的效果。

2.1.1 AdaBoost算法

2.1.1.1 什麼是AdaBoost算法？

　　Boosting是一種集合技術，試圖從許多弱分類器中建立一個強分類器。這是通過從訓練資料構模組化型，然後建立第二個模型來嘗試從第一個模型中糾正錯誤來完成的。添加模型直到完美預測訓練集或添加最大數量的模型。

　　AdaBoost是Adaptive Boosting的縮寫，是由Yoav Freund和Robert Schapire制作的機器學習元算法，他們因其工作而獲得2003年哥德爾獎。它可以與許多其他類型的學習算法結合使用，以提高性能。其他學習算法（“弱學習者”）的輸出被組合成權重和，該權重和表示提升分類器的最終輸出。

　　AdaBoost是第一個為二進制分類開發的真正成功的增強算法。這是了解助力的最佳起點。現代助推方法建立在AdaBoost上，最着名的是随機梯度增強機。

　　AdaBoost在某種意義上是适應性的，即随後的弱學習者被調整為支援那些被先前分類器錯誤分類的執行個體。AdaBoost對噪聲資料和異常值敏感。在某些問題中，它可能比其他學習算法更不容易受到過度拟合問題的影響。個體學習者可能很弱，但隻要每個學習者的表現略好于随機猜測，最終的模型就可以證明可以融合到強大的學習者身上。

　　AdaBoost可用于短決策樹。在建立第一個樹之後，每個訓練執行個體上的樹的性能用于權重建立的下一個樹應該關注每個訓練執行個體的注意力。難以預測的訓練資料被賦予更多權重，而易于預測的執行個體被賦予更少的權重。模型一個接一個地順序建立，每個模型更新訓練執行個體上的權重，這些權重影響序列中下一個樹所執行的學習。建構完所有樹之後，将對新資料進行預測，并根據訓練資料的準确性對每棵樹的性能進行權重。

因為通過算法如此關注糾正錯誤，是以必須删除帶有異常值的幹淨資料。

2.1.1.2 Adaboost 的優缺點

AdaBoost算法優點：

很好的利用了弱分類器進行級聯；
可以将不同的分類算法作為弱分類器；
AdaBoost具有很高的精度；
相對于bagging算法和Random Forest算法，AdaBoost充分考慮的每個分類器的權重；

Adaboost算法缺點：

AdaBoost疊代次數也就是弱分類器數目不太好設定，可以使用交叉驗證來進行确定；
資料不平衡導緻分類精度下降；
訓練比較耗時，每次重新選擇目前分類器最好切分點；

2.1.1.3 AdaBoost算法推導過程

AdaBoost算法有多種推導方式，比較容易了解的是基于“加性模型”(additive model)，即基學習器的線性組合

\[H(x) = \sum \limits_{t=1}^T \alpha_t h_t(x)　\quad \quad (8.4)

式(8.4)的解釋

注意到$h_t(x) \in \left\{-1, +1\right\}$，權重系數$\alpha_t$由後面的式(8.11)給出了(T個系數$\alpha_t$僅與自身對應的基學習器錯誤率$\epsilon_t$有關，互相之間無必然聯系；由于要求$\epsilon_t < 0.5$，是以$\alpha_t > 0$)，所得線性權重結果$H(x)$就是一個實數，可能大于零，也可能小于零，取值範圍無法确定。

來最小化指數損失函數(exponential loss function)

\[\ell_{exp}(H|\mathcal{D}) = \mathbb{E}_{x\simＤ}[e^{-f(x)H(x)}]. \quad \quad (8.5)

式(8.5)的解釋

(1)先解釋指數損失函數$e^{-f(x)H(x)}$的含義：$f$為真實函數，對于樣本$x$來說，$f(x) \in \left\{-1, +1 \right\}$隻能取-1和+1兩個值，而$H(x)$是一個實數；

　　當$H(x)$的符号與$f(x)$一緻時，$f(x)H(x) > 0$，是以$e^{-f(x)H(x)} = e^{-|H(x)|} < 1$，且$|H(x)|$越大指數損失函數$e^{-f(x)H(x)}$越小(這聽起來很合理：此時$|H(x)|$越大意味着分類器本身對于預測結果的信心越大，但預測結果是錯誤，是以損失應該越大；若$|H(x)|$在零附近，雖然預測錯誤，但表示分類器本身對預測結果資訊很小，雖然錯亂，損失應該較小)；

　　對比0/1損失函數：當$H(x)$的符号與$f(x)$不一緻時則損失為0，當$H(x)$的符号與$f(x)$不一緻時則損失為1，而不管$H(x)$的大小。

(2)再解釋符号$\mathbb{E}_{x \sim \mathcal{D}}[ \cdot]$的含義：$\mathcal{D}$為機率分布，可簡單了解為在資料集$D$中進行一次随機抽樣，每個樣本被取到的機率:$\mathbb{E}[\cdot]$為經典的期望，則綜合起來$\mathbb{E}_{x \sim \mathcal{D}}[\cdot]$表示在機率分布$\mathcal{D}$上的期望，可簡單了解為對資料集$D$以機率$\mathcal{D}$進行權重後的期望。

　　綜上所述，若資料集$D$中樣本$x$的權值分布為$\mathcal{D}(x)$，則式(8.5)可寫為:

　　　$\ell_{exp}(H|\mathcal{D}) = \mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H(x)}] \\ =\sum \limits_{x \in D} \mathcal{D}(x)e^{-f(x)H(x)} \\ =\sum \limits_{x \in D} \mathcal{D}(x)(e^{-H(x)}\mathbb{I}(f(x) = 1) + e^{H(x)}\mathbb{I}(f(x) = -1))$

特别地，若針對任意樣本$x$，若分布$\mathcal{D}(x) = \frac{1}{|D|}$，其中$|D|$為資料集$D$樣本個數，則

　　　$\ell_{exp}(H|\mathcal{D}) = \mathbb{E}_{x \sim \mathcal{D}}[E^{-f(x)H(x)}] = \frac{1}{|D|} \sum \limits_{x \in D} e^{-f(x)H(x)}$.

而這就是在求傳統平均值。

若$H(x)$能令指數損失函數最小化，則考慮$\ell_{exp}(H|\mathcal{D}) = \mathbb{E}_{x\simＤ}[e^{-f(x)H(x)}]$對$H(x)$的偏導

\[\frac{\partial \ell_{exp}(H|\mathcal{D})}{\partial H(x)} = -e^{-H(x)}P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x)　\quad \quad (8.6)

式(8.6)的推導

首先，當$f(x) = 1$時$e^{-f(x)H(x)} = e^{-H(x)}$,當$f(x) = -1$時$e^{-f(x)H(x)} = e^{H(x)}$；

其次，由以上分析可知式(8.5)包含$|D|$個不同的$e^{-f(x)H(x)}$，其中$x \in D$；

最後，針對每個$H(x)$求導，隻有對應的$e^{-f(x)H(x)}$會起到作用，其餘與$H(x)$無關的項求導後等于零。

為更友善了解，将式(8.5)的解釋中的式(8.5)改寫為如下形式

$\ell_{exp}(H|\mathcal{D}) = \mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H(x)}] = \sum \limits_{i=1}^{|D|}\mathcal{D}(x_i)e^{-f(x_i)H(x_i)} \\ = \sum \limits_{i=1}^{|D|}\mathcal{D}(x_i)(e^{-H(x_i)}\mathbb{I}(f(x_i) = 1) + e^{H(x_i)}\mathbb{I}(f(x_i) = -1))$

但這裡有點不同的是，式(8.6)是為了推導出式(8.7)和式(8.8)的判定準則預測$x$的類别，即無法得知$f(x)$具體等于$1$還是$-1$，隻能知道$f(x)$為$1$的後驗機率$P(f(x) = 1|x)$和為$-1$的後驗機率$P(f(x) = -1|x)$，是以上式可寫為

　　$\ell_{exp}(H|\mathcal{D}) = \sum \limits_{i=1}^{|D|}\mathcal{D}(x_i)\mathbb{E}[e^{-f(x_i)H(x_i)}] \\ = \sum \limits_{i=1}^{|D|}\mathcal{D}(x_i)(e^{-H(x_i)}P(f(x_i) = 1|x_i) + e^{H(x_i)}P(f(x_i) = -1|x_i)$

現對$H(x_i)$求導，求和項中隻有第$i$項目$\mathcal{D}\mathbb{E}[e^{-f(x_i)H(x_i)}]$會起作用。$\mathcal{D}(x_i)$為常量，不影響接下來式(8.7)中令導數等于零求解的過程，而

　　　$\frac{\partial e^{-H(x)}}{\partial H(x)} = -e^{-H(x)}, \quad \frac{\partial e^{H(x)}}{\partial H(x)} = e^{H(x)}$

是以求導結果為

　　　$\frac{\partial \ell_{exp}(H|\mathcal{D})}{\partial H(x)} = -e^{-H(x)}P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x)$.

即為式(8.6)，得證。

令上式為零可解得

\[H(x) = \frac{1}{2}ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)} \quad \quad (8.7)

式(8.7)的推導

令式(8.6)等于零:$-e^{-H(x)}P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x) = 0$

移項：$e^{H(x)}P(f(x) = -1) = e^{-H(x)}P(f(x)=1|x)$

兩邊同乘$\frac{e^{H(x)}]}{P(f(x) = -1|x)}$: $e^{2H(x)} = \frac{P(f(x) = 1|x)}{P(f(x) = -1|x)}$；

取$ln(\cdot)$：$2H(x) = ln\frac{P(f(x) = 1|x)}{P(f(x) = -1|x)}$；

兩邊同除$2$:即可得$H(x) = \frac{1}{2}ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)}$。

至此，式(8.7)得證。

是以，有

\[sign(H(x)) = sign \left(\frac{1}{2}ln\frac{P(f(x)=1|x)}{P(f(x)=-1|x)}\right) \\

=　\left\{\begin{matrix}

1,\quad P(f(x)=1|x) > P(f(x)=-1|x)\\

-1,\quad P(f(x)=1|x) <P(f(x)=-1|x)

\end{matrix}\right. \\

= \underset{y∈\left\{-1,1\right\}}{arg　max}P(f(x)=y|x) \quad \quad (8.8)

這意味着$sign(H(x))$達到了貝葉斯最優錯誤率。換言之，若指數損失函數最小化，則分類錯誤率也将最小化；

這說明指數損失函數是分類任務原來$0/1$損失函數的一緻的(consistent)替代損失函數。由于這個替代函數有更好的數學性質，例如它是連續可微函數，是以我們用它來替代$0/1$損失函數作為優化目标。

　　在AdaBoost算法中，第一個基分類器$h1$是通過直接将基學習算法用于初始資料分布而得；此後疊代地生成$h_t$和$\alpha_t$，當基分類器$h_t$基于分布$\mathcal{D}_t$産生後，該基分類器的權重$a_t$應使得$\alpha_th_t$最小化損失函數。

\[\ell_{exp}(\alpha_t h_t|\mathcal{D_t}) = \mathbb{E}_{x\sim \mathcal{D}_t} \left[e^{-f(x)\alpha_t h_t(x)} \right] \\

= \mathbb{E}_{x\sim \mathcal{D}_t} \left[e^{-\alpha_t}\mathbb{I}f((x)=h_t(x)) + e^{\alpha_t}\mathbb{I}(f(x)\neq h_t(x)) \right] \\

= e^{-\alpha_t}P_{x\sim \mathcal{D}_t}(f(x)=h_t(x)) + e^{\alpha_t}P_{x\sim \mathcal{D_t}}(f(x)\neq h_t(x)) \\

= e^{-\alpha_t}(1-\epsilon_t) + e^{\alpha_t}\epsilon_t \quad \quad (8.9)

式(8.9)的解釋

第一個等号與式(8.5)的差別僅在于到底針對$\alpha_th_t$還是$H(x)$，代入即可；

第二個等号是考慮到$h_t(x)$和$f(x)$均隻能取-1和+1兩個值，其中$\mathbb{I}(\cdot)$為訓示函數；

第三個等号對中括号的兩項分别求$\mathbb{E}_{x \sim \mathcal{D}}[\cdot]$，而$e^{\alpha_t}$和$e^{\alpha_t}$與$x$無關，可以作為常數項拿到$\mathbb{E}_{x \sim \mathcal{D}_t}[\cdot]$外面，而$\mathbb{E}_{x \sim \mathcal{D}_t}[\mathbb{I}(f(x) = h_t(x))]$表示在資料集D上、樣本權值分布為$\mathcal{D}_t$時$f(x)$和$h_t(x)$相等次數的期望，即$P_{x \sim \mathcal{D}_t}(f(x) = h_t(x))$，也就是是正确率，即$(1 - \epsilon_t)$；

同理，$\mathbb{E}_{x \sim \mathcal{D}_t}[\mathbb{I}(f(x) \neq h_t(x))]$表示在資料集$D$上、樣本權值分布為$\mathcal{D}_t$時$f(x)$和$h_t(x)$不相等次數的期望，即$P_{x \sim \mathcal{D}_t}(f(x) \neq h_t(x))$，也就是錯誤率$\epsilon_t$；

第四個等号即為将$P_{x \sim \mathcal{D}_t}(f(x) = h_t(x))$替換為$(1 - \epsilon_t)$、将$P_{x \sim \mathcal{D}_t}(f(x) \neq h_t(x))$替換為$\epsilon_t$的結果。

其中$\epsilon_t=P_{x\sim \mathcal{D}_t}(h_t(x)\neq f(x))$。

下面考慮指數損失函數的導數

\[\frac{\partial \ell_{exp}(\alpha_t h_t|\mathcal{D}_t)}{\partial \alpha_t} = -e^{-\alpha_t}(1-\epsilon_t) + e^{\alpha_t}\epsilon_t \quad \quad (8.10)

\[\alpha_t = \frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t}) \quad \quad (8.11)

這恰是AdaBoost算法疊代中的分類器權重更新公式。

AdaBoost算法在獲得$H_{t-1}$之後樣本分布将進行調整，使下一輪的基學習器$h_t$能糾正$H_{t-1}$的一些錯誤。

理想的$h_t$能糾正$H_{t-1}$的全部錯誤，即最小化

\[\ell_{exp}(H_{t-1} + h_t|\mathcal{D}) = \mathbb{E}_{x \sim D}[e^{-f(x)}(H_{t-1}(x) + h_t(x))] \\

= \mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_{t-1}(x) e^{-f(x)h_t(x)}}]. \quad \quad (8.12)

注意到$f^2(x) = h_t^2(x) = 1$，上式可以使用$e^{-f(x)h_t(x)}$的泰勒展開式近似為

\[\ell_{exp}(H_{t-1}+h_t|\mathcal{D})\simeq \mathbb{E}_{x\sim \mathcal{D}}\left[e^{-f(x)H_{t-1}(x)}(1-f(x)h_t(x)+\frac{f^2(x)h_t^2(x)}{2} \right] \\

= \mathbb{E}_{x\sim \mathcal{Ｄ}} \left[e^{-f(x)H_{t-1}(x)}(1-f(x)h_t(x) + \frac{1}{2} \right] \quad \quad (8.13)

式(8.13)的推導

複習以下泰勒展開式:

$f(x) = \frac{f(x_0)}{0!} + \frac{f'(x_0)}{1!}(x-x_0) + \frac{f''(x_0)}{2!}(x-x_0)^2 + ... + \frac{f^{(n)}(x_0)}{n!}(x - x_0)^n + ...$

當$f(x) = e^{-x}$時，在$x_0$處泰勒展開：

$e^{-x}$時，在$x_0$處泰勒展開，代入即可得式(8.13)。

實際上，此處保留一階泰勒展開項即可，後面提到的Gradient Boosting理論架構就是隻使用了一階泰勒展開；當然二階項為常數，也并不影響推導結果，原文獻中保留了二階項。

于是，理想的基學習器

\[\begin{align}

&h_t(x) = \mathop{\arg\min}_{h} \ell_{exp}(H_{t-1}+h|\mathcal{D}) \\

&= \mathop{\arg\min}_{h}\mathbb{E}_{x\sim \mathcal{D}} \left[e^{-f(x)H_{t-1}(x)} \left(1-f(x)h(x) + \frac{1}{2} \right) \right] \\

&= \mathop{\arg\min}_{h}\mathbb{E}_{x\sim \mathcal{D}} \left[e^{-f(x)H_{t-1}(x)}f(x)h(x) \right] \\

&= \mathop{\arg\min}_{h}\mathbb{E}_{x\sim \mathcal{D}} \left[\frac{e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\sim \mathcal{D}} [e^{-f(x)H_{t-1}(x)}]}f(xh(x)) \right] \quad \quad (8.14)

\end{align}

式(8.14)的推導

本式基于式(8.12)和式(8.13)的結果。理想的$h_t(x)$是使得$H_t(x)$的指數損失函數取得最小值時的$h_t(x)$，該式将次轉化成某個期望的最大值。

第二個等号就是在第一個等号的基礎上将式(8.13)代入；

第三個等号是因為

$\mathbb{E}_{x \sim \mathcal{D}} \left[e^{-f(x)H_{t-1}(x)} \left(1 - f(x)h(x) + \frac{1}{2} \right) \right] \\ = \mathbb{E}_{x \sim \mathcal{D}} \left[\frac{3}{2} e^{-f(x)H_{t-1}(x)} - e^{-f(x)H_{t-1}(x)}f(x)h(x) \right] \\ = \mathbb{E}_{x \sim \mathcal{D}} \left[\frac{3}{2}e^{-f(x)H_{t-1}(x)} \right] - \mathbb{E}_{x \sim \mathcal{D}} \left[e^{-f(x)H_{t-1}(x)}f(x)h(x) \right]$

本式自變量為$h(x)$，而$\mathbb{E}_{x \sim \mathcal{D}}[\frac{3}{2}e^{-f(x)H_{t-1}}(x)]$與$h(x)$無關，也就是一個常數；

這時我們隻需最大化第二項$\mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)}f(x)h(x)]$即可，将負号去掉，則原最小化問題變為最大化問題；

第四個等号仍是因為$\mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)}]$是與自變量$h(x)$無關的正常數(因為指數函數$e^{-f(x)H_{t-1}(x)}$大于零，進而求期望$\mathbb{E}_{x \sim \mathcal{D}}[\cdot]$的結果也大于零)，而最大化問題乘以某個正常數與原問題等價(例如$\arg \max_x(1 - x^2)$與$\arg \max_x 2(1-x^2)$的結果均為$x = 0$)；

注意到$\mathbb{E}_{x\sim \mathcal{D}} [e^{-f(x)H_{t-1}(x)}]$是一個常數。

則令$\mathcal{D}_t$表示一個分布

\[\mathcal{D}_t(x) = \frac{\mathcal{D}(x) e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)}]} \quad \quad (8.15)

則根據資料期望的定義，這等價于令

\[h_t(x) = \mathop{\arg\min}_{h} \mathbb{E}_{x\sim \mathcal{D}} \left[\frac{e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)}]}f(x)h(x) \right] \\

= \mathop{\arg\min}_{h} \mathbb{E}_{x\sim \mathcal{D_t}}[f(x)h(x)] \quad \quad (8.16)

式(8.16)的推導

首先解釋以下符号$\mathbb{E}_{x \sim \mathcal{D}}$的含義，這裡注意在本章有兩個符号$D$和$\mathcal{D}$，其中$D$表示資料集，而$\mathcal{D}$表示資料集$D$的樣本分布，可以了解為在資料集$D$上進行一次随機采樣，則樣本$x$被抽到的機率為$\mathcal{D}(x)$，那麼符号$\mathbb{E}_{x \sim \mathcal{D}}$表示的是在機率分布$\mathcal{D}$上的期望，可以簡單了解為對資料及$D$以機率$\mathcal{D}$權重之後的期望。

是以，類似于式(8.6)的推導中：

　　　　$\mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H(x)}] = \sum \limits_{i=1}^{|D|}e^{-f(x_i)H(x_i)}$

并結合式(8.15)的定義可知

　　　　$\mathcal{D}_t(x_i) = \mathcal{D}(x_i) \frac{e^{-f(x_i)H_{t-1}(x_i)}}{\mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)}]}$

其中$x_i$表示資料集D的第$i$個樣本，故與式(8.15)一樣。

是以針對式(8.14式的最後一行表達式，(8.16可以表示為

　　　　$\mathbb{E}_{x \sim \mathcal{D}} \left[\frac{e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x \sim \mathcal{D}[e^{-f(x)H_{t-1}(x)}]}}f(x)h(x) \right] \\ = \sum \limits_{i=1}^{|D|}\mathcal{D}(x_i) \frac{e^{-f(x_i)H_{t-1}(x_i)}}{\mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x}H_{t-1}(x)]}f(x_i)h(x_i) \\ = \sum \limits_{i=1}^{|D|}\mathcal{D}_t(x_i)f(x_i)h(x_i) \\ = \sum \limits_{x \sim \mathcal{D}_t}[f(x)h(x)]$

由$f(x),h(x)∈\left\{-1,+1 \right\}$有

\[f(x)h(x) = 1 - 2 \mathbb{I}(f(x) \neq h(x)) \quad \quad (8.17)

式(8.17)的推導

當$f(x) = h(x)$時，$f(x)h(x) = 1$；

當$f(x) \neq h(x)$，$f(x)h(x) = -1$；

當$f(x) = h(x)$時，$\mathbb{I}(f(x) \neq h(x)) = 0$，則$1 - 2\mathbb{I}(f(x) \neq h(x)) = 1$；

當$f(x) \neq h(x)$時，$\mathbb{I}(f(x) \neq h(x)) = 1$，則$1 - 2\mathbb{I}(f(x) \neq h(x)) = -1$；

綜上所述，等式兩邊相等。

則理想的基學習器

\[h_t(x) = \mathop{\arg\min}_{h} \mathbb{E}_{x\sim \mathcal{D}_t} [\mathbb{I}f(x) \neq h(x)] \quad \quad (8.18)

式(8.18)的推導

本式基于式(8.17)的恒等關系，由式(8.16)推導而來。

　　　$\mathbb{E}_{x \sim \mathcal{D}}[f(x)h(x)] = \mathcal{E}_{x \sim \mathcal{D}_t}[1 - 2\mathbb{I}(f(x)) \neq h(x)] \\ =\mathbb{E}_{x \sim \mathcal{D_t}[1] - 2\mathbb{E}_{x \sim \mathcal{D}_t}}[\mathbb{I}(f(x) \neq h(x))]$

類似于式(8.14)的第3個和第4個等号，由式(8.16)的結果開始推導:

$h_t(x) = \mathop{\arg\max} \limits_{h} \mathbb{E}_{x \sim \mathcal{D}_t}[f(x)h(x)] \\ = \mathop{\arg\max} \limits_{h} (1 - 2 \mathbb{E}_{x \sim \mathcal{D}_t})[\mathbb{I}(f(x) \neq h(x))] \\ = \mathop{\arg\max} \limits_{h} (1 - 2\mathbb{E}_{x \sim \mathcal{D}_t)}[\mathbb{I}(f(x) \neq h(x))] \\ = \mathop{\arg\min} \limits_{h} \mathbb{E}_{x \sim \mathcal{D}_t} [\mathbb{I}(f(x) \neq h(x))]$

此式表示理想的$h_t(x)$在分布$\mathcal{D}_t$下最小化分類誤差，是以有圖8.3第3行$h_t(x) = \mathcal{L}(D, \mathcal{D}_t)$，即分類器$h_t(x)$可以基于分布$\mathcal{D}_t$從資料集$D$中訓練而得，而我們在訓練分類器時一般來說最小化的損失函數就是分類誤差。

由此可見，理想的$h_t$将在分布$\mathcal{D}_t$下最小化分類誤差。

是以，弱分類器将基于分布$\mathcal{D}_t$來訓練，且針對$\mathcal{D}_t$的分類誤差應小于0.5。這在一定程度上類似于“殘差逼近”的思想。考慮到$\mathcal{D}_t$和$\mathcal{D}_{t+1}$的關系，有

\[\mathcal{D}_{t+1} = \frac{\mathcal{D}(x) e^{-f(x)H_t(x)}}{\mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_{t}(x)}]} \\

=　\frac{\mathcal{D}(x) e^{-f(x)H_{t-1}(x)}e^{-f(x)\alpha_th_t(x)}}{\mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_t(x)}]} \\

= \mathcal{D}_t(x)\cdot e^{-f(x)\alpha_t h_t(x)} \frac{\mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)}]}{\mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_t(x)}]} \quad \quad (8.19)

這恰是AdaBoost算法疊代中的樣本分布更新公式。

式(8.19)的推導

boosting算法是根據調整後的樣本再去訓練下一個基分類器，這就是“重賦權法”的樣本分布的調整公式。

對于上式(8.19)，第一個等号是将式(8.15)中的$t$換成$t+1$(同時$t-1$換成$t$)；

第二個等号是将$H_t(x) = H_{t-1}(x) + \alpha_th_t(x)$代入分子即可；

第三等号是乘以$\frac{\mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)}]}{\mathbb{E}_{x \sim \mathcal{D}[e^{-f(x)H_{t-1}(x)}]}}$後，湊出式(8.15)的$\mathcal{D}_t(x)$，以符号$\mathcal{D}_t(x)$替換即得。

到此之後，得到$\mathcal{D}_{t+1}(x)$與$\mathcal{D}_t(x)$的關系，但為了確定$\mathcal{D}_{t+1}(x)$是一個分布，需要對得到的$\mathcal{D}_{t+1}(x)$進行規範化，即圖8.3第7行的$Z_t$。式(8.19)第3行最後一個分式将在規範化過程中被吸收。

于是，由$\alpha_t = \frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t})$和$\mathcal{D}_{t+1} = \mathcal{D}_t(x)\cdot e^{-f(x)\alpha_t h_t(x)} \frac{\mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)}]}{\mathbb{E}_{x\sim \mathcal{D}}[e^{-f(x)H_t(x)}]}$可見,我們基于加性模型疊代式優化指數損失函數的角度推導出了AdaBoost算法。

2.1.2 AdaBoost推導梳理

2.1.3 AdaBoost算法描述

整個AdaBoost的算法描述如下所示：(其中$y_i∈\left\{-1,+1\right\}$,$f$是真實函數。)(參考-西瓜書)

輸入：訓練集$D=\{(x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\}$；

基學習算法$\mathcal{L}$；

訓練輪數$T$；

過程：

  1: 初始化權重：$D_1(i)=1/m$

  2: for $t=1,\cdots,T$:

  3:   $h_t=\mathcal{L}(D,D_t)$；用$D$和$D_t$訓練一個學習器$h_t$；

  4:   $\epsilon_t=Pr_{x \sim D_{t,y}}I[h_t(x) \neq y]$；計算$h_t$的誤差；

  5:   if $\epsilon > 0.5$ then break

  6:   $\displaystyle \alpha_t=\frac{1}{2} \ln \left(\frac{1-\epsilon_t}{\epsilon_t} \right)$；計算基學習器權重；

$\begin{aligned} \text{7:} \quad D_{t+1}(i)

&=\displaystyle \frac{D_{t}(i)}{Z_{t}} \times\left\{\begin{array}{l}{\exp (-\alpha_t) \text { if } h_{t}(x_i)=y_i} \\ {\exp (\alpha_t) \quad \text { if } h_{t}(x_i) \neq y_i}\end{array}\right. \\

&=\displaystyle \frac{D_t(i) \exp(-\alpha_t y_i h_t(x_i))}{Z_t}

\end{aligned}$

    樣本權重分布更新；

  8: end for

輸出：$\displaystyle H(x)=\text{sign}(\sum_{t=1}^T \alpha_t h_t(x)) $

2.1.3.1 AdaBoost算法詳解

這裡進一步深入叙述AdaBoost算法(參考《統計學習方法》)。

假設給定一個二類分類的訓練資料集合

\[T = \left\{(x_1,y_1),(x_2,y_2),...,(x_N，y_N) \right\}

其中，每個樣本點由執行個體與标記組成。執行個體$x_i∈\mathcal{X}\subseteqＲ^2$，标記$y_i∈\mathcal{Y}=\left\{-1,+1 \right\}$，$\mathcal{X}$是執行個體空間，$\mathcal{Y}$是标記集合。AdaBoost利用以下算法，從訓練資料中學習一系列弱分類器或基本分類器，并将這些弱分類器線性組合成為一個強分類器。

輸入：訓練資料集$T = \left\{(x_1,y_1),(x_2,y_2),...,(x_N，y_N) \right\}$,其中$x_i∈\mathcal{X}\subseteqＲ^2$,$y_i∈\mathcal{Y}=\left\{-1,+1 \right\}$；弱學習算法

輸出：最終分類器G(x)

(1)初始化訓練資料的權值分布

\[D_1 = (w_{11},...,w_{1i},...,w_{1N}), \quad w_{1i} = \frac{1}{N}, i = 1,2,...,N

(2)對$m=1,2,...,M$.

　　(a) 使用具有權值分布$D_m$的訓練資料集學習，得到基本分類器.

\[G_m(x):\mathcal{X} \to \left\{-1,+1\right\}

　　(b) 計算$G_m(x)$在訓練資料集上的分類誤差率.

\[e_m = \sum \limits_{i=1}^N P(G_m(x_i) \neq y_i) = \sum \limits_{i=1}^N W_{mi}I(G_m(x_i)\neq y_i)

　　(c)計算$G_m(x)$的系數.

\[\alpha_m = \frac{1}{2} log \frac{1-e_m}{e_m} = \frac{1}{2}ln\frac{1-e_m}{e_m}

　　　　這裡的對數是自然對數

　　(d)更新訓練資料集的權值分布.

\[D_{m+1} = (w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})　\\

w_{m+1,i} = \frac{w_{mi}}{Z_{m}} exp(-\alpha_m y_iG_m(x_i)), \quad i=1,2,...,N

　　　　　這裡的$Z_m$是規範化因子,它使$D_{m+1}$成為一個機率分布。

\[Z_m = \sum \limits_{i=1}^N w_{mi} exp(-\alpha_m y_i G_m(x_i))

(3)建構基本分類器的線性組合.

\[f(x) = \sum \limits_{m=1}^M \alpha_m G_m(x)

得到最終分類器

\[G(x) = sign(f(x)) = sign(\sum \limits_{m=1}^M \alpha_m G_m(x))

對AdaBoost算法作如下說明:

　　步驟(1)　假設訓練資料集具有均勻的權重分布，即每個訓練樣本在基本分類器的學習中作用相同，這以假設保證第1步能夠在原始資料上學習基本分類器$G_1(x)$.

　　步驟(2)　AdaBoost反複學習基本分類器，在每一輪$m=1,2,...,M$順次地執行下列操作:

　　　　(a) 使用目前分布$D_m$權重的訓練資料集，學習基本分類器$G_m(x)$．

　　　　(b) 計算基本分類器$G_m(x)$在權重訓練資料集上的分類誤差率:

\[e_m = \sum \limits_{i=1}^N P(G_m(x_i)\neq y_i) = \sum \limits_{G_m(x_i)\neq y_i}w_{mi}.

　　　　這裡，$w_{mi}$表示第m輪中第$i$個執行個體的權值，$\sum \limits_{i=1}^N w_{mi}=1$。

　　　　這表明基本分類器$G_m(x)$在權重的訓練資料集上的分類誤差率是被$G_m(x)$誤分類樣本的權值之和。

　　　　由此可以看出資料權重分布$D_m$與基本分類器$G_m(x)$的分類誤差率的關系。

　　　　由$\alpha_m = \frac{1}{2}ln\frac{1-e_m}{e_m}$可知，當$e_m\leq \frac{1}{2}$時，$\alpha_m\geq 0$，并且$\alpha_m$随着$e_m$的減小而增大。

　　　　是以分類誤差率越小的分類器在最終分類器中的作用越大。

　　　　(d) 更新訓練資料的權重分布為下一輪作準備。

　　　　$w_{m+1,i} = \frac{w_{mi}}{Z_{m}} exp(-\alpha_m y_iG_m(x_i)), \quad i=1,2,...,N$可以寫成

\[w_{m+1,i} = \left\{\begin{matrix}

\frac{w_{mi}}{Z_{m}}e^{-\alpha_m}, \quad G_m(x_i) = y_i \\

\frac{w_{mi}}{Z_m}e^{\alpha_m}, \quad G_m(x_i) \neq y_i

\end{matrix}\right.

　　　　由此可知，被基本分類器$G_m(x)$誤分類樣本的權值得以擴大，而被正确分類樣本的權值卻得以縮小。

　　　　兩相比較，由$\alpha_m = \frac{1}{2}ln\frac{1-e_m}{e_m}$知誤分類樣本的權值被放大$e^{2\alpha_m} = \frac{1-e_m}{e_m}$倍。

　　　　是以，誤分類樣本在下一輪學習中起更大的作用。

　　　　不改變所給的訓練資料，而不斷改變訓練資料權值的分布，

　　　　使得訓練資料在基本分類器的學習中起不同的作用，這是AdaBoost的一個特點。

　　步驟(3)　線性組合$f(x)$實作Ｍ個基本分類器的權重表決。

　　系數$\alpha_m$表示了基本分類器$G_m(x)$的重要性，這裡，所有$\alpha_m$之和并不為1。

　　$f(x)$的符号決定執行個體$x$的類，$f(x)$的絕對值表示分類的确信度。

　　利用基本分類器的線性組合建構最終分類器是AdaBoost的另一個特點。

重賦權法：　

Boosting算法要求基學習器能對特定的資料分布進行學習，這可通過“重賦權法”(re-weighting)實施，即在訓練過程的每一輪中，根據樣本分布為每個訓練樣本重新賦予一個權重，即在訓練過程的每一輪中，根據樣本分布為每個訓練樣本重新賦予一個權重。
重采樣法：

對無法接受帶權樣本的基學習算法，則可通過“重采樣法”(re-sampling)來處理，即在每一輪學習中，根據樣本分布對訓練集重新進行采樣，再用重采樣而得的樣本集對基學習器進行訓練。

　　一般而言，這兩種做法沒有顯著的優劣差别。但需要注意的是，Boosting算法在訓練的每一輪都要檢查目前生成的基學習器是否滿足基本條件(例如，檢查目前基分類器是否是比随機猜測好)，一旦條件不滿足，則目前基學習器即被抛棄，且學習過程停止。在此種情形下，初始設定的學習輪數Ｔ也許還遠未達到，可能導緻最終內建中隻包含很少的基學習器而性能不佳。

　　若采用“重采樣法”，則可獲得“重新開機動”機會以避免訓練過程停止，即在抛棄不滿足條件的目前基學習器之後，可根據目前分布重新對訓練樣本進行采樣，再基于新的采樣結果重新訓練出基學習器，進而使得學習過程可以持續到預設的Ｔ輪完成。

　　從偏差－方差分解的角度看，Boosting主要關注降低偏差，是以Boosting能基于泛化性能相當弱的學習器建構出很強的內建。從AdaBoost的算法流程來看，标準的AdaBoost隻适用于二分類問題。

　　我們以決策樹樁為基學習器，在西瓜資料集$3.0\alpha$上運作AdaBoost算法，不同規模(size)的內建及其基學習器所對應的分類邊界如下所示。

例題1 試用AdaBoost算法學習一個強分類器。

給定如下表所示的訓練資料。假設弱分類器由$x<v$或$x>v$産生，其門檻值$v$使該分類器在訓練資料集上分類誤差率最低。試用AdaBoost算法學習一個強分類器。

解　初始化資料權重分布

\[D_1 = (w_{1,1},w_{1,2},...,w_{1,10})

第一輪對m=1,

　　(a) 在權重分布為$D_1$的訓練資料上，門檻值$v$取2.5時分類誤差率最低，故基本分類器為

\[G_1(x) = \left\{\begin{matrix}

1, \quad x < 2.5 \\

-1, \quad x> 2.5

　　(b) $G_1(x)$在訓練資料集上的誤差率$e_1 = P(G_1(x_i)\neq y_i)=0.3$。

　　(d) 更新訓練資料的權值分布:

\[D_2 = (w_{2,1},...,w_{2,i},...,w_{2,10}) \\

w_{2,i} = \frac{w_{1,i}}{Z_1}exp(-\alpha_1 y_i G_1(x_i)), \quad i = 1,2,...,10 \\

D_2 = (0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,\\0.16667, 0.16667,0.16667,0.07143)　\\

f_1(x) = 0.4236G_1(x)

對分類器sign[$f_1(x)$]在訓練資料上有3個誤分類點。

第二輪對m=2,

　　(a) 在權重分布為$D_2$的訓練資料上，門檻值$v$取8.5時分類誤差率最低，故基本分類器為

\[G_2(x) = \left\{\begin{matrix}

1, \quad x < 8.5 \\

-1, \quad x> 8.5

　　(b) $G_2(x)$在訓練資料集上的誤差率$e_2 = P(G_2(x_i)\neq y_i)=0.2143$。

\[D_3 = (0.0455,0.0455,0.0455,0.16667,0.16667,\\0.16667,0.1060,0.1060,0.1060,0.0455)　\\f_2(x) = 0.4236G_1(x) + 0.6496G_2(x).

對分類器sign[$f_2(x)$]在訓練資料上有3個誤分類點。

第三輪對m=3,

　　(a) 在權重分布為$D_3$的訓練資料上，門檻值$v$取5.5時分類誤差率最低，故基本分類器為

\[G_3(x) = \left\{\begin{matrix}1, \quad x < 5.5 \\-1, \quad x > 5.5\end{matrix}\right.

　　(b) $G_2(x)$在訓練資料集上的誤差率$e_3 = P(G_3(x_i)\neq y_i)=0.1820$。

\[D_4 = (0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)

　　于是得到:

\[f_3(x) = 0.4236G_1(x) + 0.6496G_2(x) + 0.7514G_3(x).

　　對分類器sign[$f_3(x)$]在訓練資料上有0個誤分類點。

于是最終分類器為

\[Ｇ(x) = sign[f_3(x)] = sign[0.4236G_1(x) + 0.6496G_2(x) + 0.7514G_3(x)]

(三) Bagging與随機森林

　　與AdaBoost算法相比，Bagging與随機森林算法就簡潔許多，我們知道産生“好而不同”的個體學習器是內建學習研究的核心，即在保證基學習器準确性的同時增加基學習器之間的多樣性。而這兩種算法的基本思想都是通過“自助采樣法”來增加多樣性。

　　由前面的讨論中，我們可以知道，欲得到泛化性能強的內建，內建中的個體學習器應盡可能獨立；雖然“獨立”在現實任務中無法做到，但可以設法使基學習器盡可能具有較大的差異。給定一個訓練資料集，一種可能的做法是對訓練樣本進行采樣，産生出若幹個不同的子集，再從每個資料子集中訓練出一個基學習器。

　　這樣，由于訓練資料不同，我們獲得的基學習器可望具有比較大的差異。然而，為獲得好的內建，我們同時還希望個體學習器不能太差。如果采樣出的每個子集都完全不同，則每個基學習器隻用到了一小部分訓練資料，甚至不足以進行有效學習，這顯然無法確定産生出比較好的基學習器。為解決這個問題，我們可考慮使用互相有交疊的采樣子集。　

3.1 Bagging

　　Bagging是并行式內建學習方法著名的代表。從名字即可看出，它直接基于我們之前介紹過的自助采樣法(bootstrap sampling)。給定包含m個樣本的資料集，我們先随機取出一個樣本放入采樣集中，再把該樣本放回初始資料集，使得下次采樣時該樣本仍有可能被選中，這樣，經過m次随機采樣操作，我們得到m個樣本的采樣集合，初始訓練集中有的樣本在采樣集裡多次出現，有的則從未出現，則樣本在m次采樣中始終不被采到的機率為$(1-\frac{1}{m})^m$,取極限可得

\[\lim_{m \longmapsto \infty}(1-\frac{1}{m})^m \longmapsto \frac{1}{e}\approx 0.368 = 36.8\%

由此可知，初始訓練集中約有63.2%的樣本出現在采樣集中。

3.1.1 Bagging的基礎流程

　　Bagging 的核心思路是 — — 民主。

　　Bagging 的思路是所有基礎模型都一緻對待，每個基礎模型手裡都隻有一票。然後使用民主投票的方式得到最終的結果。大部分情況下，經過 bagging 得到的結果方差（variance）更小。

　　照這樣，我們可采樣出T個含m個訓練樣本的采樣集，然後基于每個采樣集訓練出一個基學習器，再将這些基學習器進行結合。這就是Bagging的基礎流程。

　　在對預測輸出進行結合時，Bagging通常對分類任務使用簡單投票法，對回歸任務使用簡單平均法。若分類預測時出現兩個同樣票數的情形，則最簡單的做法是随機選擇一個，也可進一步考察學習器投票的置信度來确定最終勝者。

從原始樣本集中抽取訓練集。每輪從原始樣本集中使用Bootstraping的方法抽取n個訓練樣本（在訓練集中，有些樣本可能被多次抽取到，而有些樣本可能一次都沒有被抽中）。共進行k輪抽取，得到k個訓練集。（k個訓練集之間是互相獨立的）
每次使用一個訓練集得到一個模型，k個訓練集共得到k個模型。（注：這裡并沒有具體的分類算法或回歸方法，我們可以根據具體問題采用不同的分類或回歸方法，如決策樹、感覺器等）
對分類問題：将上步得到的k個模型采用投票的方式得到分類結果；對回歸問題，計算上述模型的均值作為最後的結果。（所有模型的重要性相同）

3.1.2 Bagging算法描述

基學習算法$L$；

  1: for $t=1,2,\cdots,T$ do

  2:   $h_t=L(D,D_{bs})$；

  3: end for

輸出：$H(x)=\underset{y \in \mathcal{Y}}{\arg \max } \sum_{t=1}^{T} I\left(h_{t}(x)=y\right)$　　

　　假定基學習器的計算複雜度為O(m)，則Bagging的複雜度大緻為T(0(m)+0(s))，考慮到采樣與投票/平均過程的複雜度O(s)很小，而Ｔ通常是一個不太大的常數，是以，訓練一個Bagging內建與直接使用基學習算法訓練一個學期器的複雜度同階，這說明Bagging是一個很高效的內建學習算法。另外，與标準AdaBoost隻适用于二分類任務不同，Bagging能不經修改地用于多分類、回歸等任務。

　　值得一提的是，自助采樣過程除了簡單高效之外，還給Bagging帶來了另一個優點：由于每個基學習器隻使用了初始訓練集中約63.2%的樣本，剩下約36.8%的樣本可用作驗證集來對泛化性能進行“包外估計”(out-of-bag estimate)。

　　為此需記錄每個基學習器所使用的訓練樣本。不妨令$D_t$表示分類器$h_t$實際使用的訓練樣本集，令$h^{oob}$表示對樣本$x$的包外預測，即僅考慮那些未使用$x$訓練的基學習器在$x$上的預測，有

\[H^{oob}(x) = \mathop{arg\max}_{y∈\mathcal{Y}}\sum \limits_{t=1}^T\mathbb{I}(h_t(x)=y)\cdot \mathbb{I}(x∉D_t) \quad \quad (8.20)

式(8.20)的解釋

僅注意一點即可，每個基分類器對應的36.8%的剩餘樣本均是不同的(可能會有樣本出現在多個基分類器對應的36.8%的剩餘樣本集合中)，是以總體考慮包外估計時，整體考慮的樣本肯定大于訓練集36.8%的樣本個數，但這些樣本并不一定是所有$T$個基分類器的包外樣本，是以在式(8.20)投票時，針對每個樣本$x$不會有$T$票出現($\mathbb{I}(x \notin D_t)$)一般不會$T$次均為真，即“僅考慮那些未使用$x$訓練的基學習器在$x$上的預測”。

其中$\mathbb{I}(h_t(x) = y)$表示對$T$個基學習器，每一個都判斷結果是否與$y$一緻，$y$的取值一般是-1和+1，

如果基學習器結果與$y$一緻，則$\mathbb{I}(h_t(x) = y) = 1$，

如果樣本不在訓練集内，則$\mathbb{I}(x \notin D_t) = 1$，

綜合起來看就是，對包外的資料，用“投票法”選擇包外估計的結果，即-1或+1。

則Bagging泛化誤差的包外估計為

\[\epsilon^{oob} = \frac{1}{|D|}\sum \limits_{(x,y)∈D} \mathbb{I}(H^{oob}(x)\neq y) \quad \quad (8.21)

式(8.21)的解釋

由式(8.20)可知，$H^{oob}(x)$是對包外資料的估計結果，則該式表示錯誤的個數除以總的個數，即得到泛化誤差的包外估計。本式直接使用将式(8.20)的包外預測結果，直接除以$|D|$(訓練集D的樣本個數)，也就是說此處假設$T$個基分類器的各自的包外樣本的并集一定為訓練集Ｄ。

　　事實上，包外樣本還有許多其他用途，例如當基學習器是決策樹時，可使用包外樣本來輔助剪枝，或用于估計決策中各節點的後驗機率以輔助對零訓練樣本節點的處理；當基學習器是神經網絡時，可使用包外樣本來輔助早期停止以減小過拟合風險。

　　從偏差-方差分解的角度來看，Bagging主要關注降低方差，是以它在不剪枝決策樹、神經網絡等易受樣本擾動的學習器上效用更為明顯。

　　我們以基于資訊增益劃分的決策樹為基學習器，在西瓜資料集3.0$\alpha$上運作Bagging算法，不同規模的內建及其基學習器所對應的分類邊界如下圖所示。

3.2 随機森林(Random Forest)

3.2.1 什麼是随機森林?

　　随機森林(Random Forest，簡稱RF)是Bagging的一個擴充變體。随機森林屬于內建學習中的 Bagging（Bootstrap AGgregation 的簡稱）方法。如果用圖來表示他們之間的關系如下：

　　随機森林RF在以決策樹為基學習器建構Bagging內建的基礎上，進一步在決策樹的訓練過程中引入了随機屬性選擇。具體來說，傳統決策樹在選擇劃分屬性時是在目前節點的屬性集合(假定有d個屬性)中選擇一個最優屬性；而在随機森林RF中，對基決策樹的每個節點，先從該節點的屬性集合中随機選擇一個包含$k$個屬性的子集，然後再從這個子集中選擇一個最優屬性用于劃分。

　　這裡的參數$k$控制了随機性的引入程度：若令$k=d$，則基決策樹的建構與傳統決策樹相同；若令$k=1$，則是随機選擇一個屬性用于劃分；一般情況下，推薦設定$k$的值為$k=log_2d$。

　　随機森林是由很多決策樹構成的，不同決策樹之間沒有關聯。

　　當我們進行分類任務時，新的輸入樣本進入，就讓森林中的每一棵決策樹分别進行判斷和分類，每個決策樹會得到一個自己的分類結果，決策樹的分類結果中哪一個分類最多，那麼随機森林就會把這個結果當做最終的結果。

　　随機森林具有簡單、容易實作、計算開銷小的特點，令人驚奇的是，它在很多現實任務中展現出強大的性能，被譽為“代表內建學習技術水準的方法”。從算法流程上可以看出，随機森林對Bagging隻做了小改動，但是與Bagging中基學習器的“多樣性”僅通過樣本擾動(通過對初始訓練集采樣)而來不同，随機森林中基學習器的多樣性不僅來自樣本擾動，還來自屬性擾動，這就使得最終內建的泛化性能可通過個體學習器之間的差異度的增加而進一步提升。

　　随機森林的收斂性與Bagging相似。如下圖所示，随機森林的起始性能往往相對較差，特别是在內建中隻包含一個基學習器時。這很容易了解，因為通過引入屬性擾動，随機森林中個體學習器的性能往往有所降低。然而，随着個體學習器數目的增加，随機森林通常會收斂到更低的泛化誤差。

　　值得一提的是，随機森林的訓練效率常由于Bagging，因為在個體決策樹的建構過程中，Bagging使用的是“确定型”決策樹，在選擇劃分屬性時要對節點的所有屬性進行考察，而随機森林使用的“随機型”決策樹則隻需考察一個屬性子集。

3.2.2 構造随機森林的4個步驟

一個樣本容量為N的樣本，有放回的抽取N次，每次抽取1個，最終形成了N個樣本。這選擇好了的N個樣本用來訓練一個決策樹，作為決策樹根節點處的樣本。
當每個樣本有M個屬性時，在決策樹的每個節點需要分裂時，随機從這M個屬性中選取出m個屬性，滿足條件m << M。然後從這m個屬性中采用某種政策（比如說資訊增益）來選擇1個屬性作為該節點的分裂屬性。
決策樹形成過程中每個節點都要按照步驟2來分裂（很容易了解，如果下一次該節點選出來的那一個屬性是剛剛其父節點分裂時用過的屬性，則該節點已經達到了葉子節點，無須繼續分裂了）。一直到不能夠再分裂為止。注意整個決策樹形成過程中沒有進行剪枝。
按照步驟1~3建立大量的決策樹，這樣就構成了随機森林了。

3.2.3 随機森林的優缺點

優點

它可以出來很高次元（特征很多）的資料，并且不用降維，無需做特征選擇
它可以判斷特征的重要程度
可以判斷出不同特征之間的互相影響
不容易過拟合
訓練速度比較快，容易做成并行方法
實作起來比較簡單
對于不平衡的資料集來說，它可以平衡誤差。
如果有很大一部分的特征遺失，仍可以維持準确度。

缺點

随機森林已經被證明在某些噪音較大的分類或回歸問題上會過拟合。
對于有不同取值的屬性的資料，取值劃分較多的屬性會對随機森林産生更大的影響，是以随機森林在這種資料上産出的屬性權值是不可信的

(四) 結合政策

4.1 為什麼要進行學習器結合的原因？

我們将多個學習器結合可能會從以下三個方面帶來好處：

一、從統計的角度來看，可降低由于因單學習器可能誤選錯誤的假設而導緻泛化性能不佳的風險。
二、從計算的方面來看，可降低學習器陷入糟糕局部極小點的風險。
三、從表示的方面來看，可更逼近真實假設，學到因學習器結合而擴大的假設空間中更好的近似。

下面是學習器結合後帶來三個方面好處的直覺示意圖。

我們分别從以下三個方面來分析為什麼要結合學習器的原因：

考慮(a)統計的原因，由于學習任務的假設空間往往很大，是以可能有多個假設在訓練集上達到同等性能，此時若使用單學習器可能因誤選而導緻泛化性能不佳，結合多個學習器則會減小這一風險；

考慮(b)計算的原因，由于學習算法往往會陷入局部極小的情況，其中有的局部極小點所對應的泛化性能可能會很糟糕，而通過多次運作之後進行結合，可降低陷入糟糕局部極小點的風險；

考慮(c)表示的原因，由于某些學習任務的真實假設可能不在目前學習算法所考慮的假設空間中，此時若使用單學習器則肯定無效，而通過結合多個學習器，又由于相應的假設空間有所擴大，有可能學得更好的近似。

4.2 常見的結合政策

我們這裡假定內建包含Ｔ個基學習器{$h_1,h_2,...,h_{T}$}，其中$h_i$在示例$x$上的輸出為$h_i(x)$。

下面簡要介紹幾種對基學習器$h_i$進行結合的常見政策。

4.2.1 平均法

　　對數值型輸出$h_i(x)∈\mathbb{R}$，最常見的結合政策是使用平均法(averaging)。

針對平均法有以下兩種實作方式：

簡單平均法(simple averaging)

\[H(x) = \frac{1}{T}\sum \limits_{i=1}^T h_i(x). \quad \quad (8.22)

對基分類器的結果進行簡單的平均。

權重平均法(weighted averaging)

\[H(x) = \sum \limits_{i=1}^T w_ih_i(x). \quad \quad (8.23)

對基分類器的結果進行權重平均

其中$w_i$是個體學習器$h_i$的權重，通常要求$w_i\geq0$,$\sum \limits_{i=1}^T w_i=1$。

顯然，簡單平均法是權重平均法令$w_i = \frac{1}{T}$的特例。簡單平均法在內建學習中具有特别的意義，內建學習中的各種結合方法都可視為其特例或變體。

權重平均法的權重一般是從訓練資料中學習而得，然而現實任務中的訓練樣本通常不充分或存在噪聲，這将使得學出的權重不完全可靠。尤其是對規模比較大的內建來說，要學習的權重比較多，較容易導緻過拟合。事實上，權重平均法可認為是內建學習研究的基本出發點，對給定的基學習器，不同的內建學習方法可視為通過不同的方式來确定權重平均法中的基學習器權重。

在實驗和應用中均顯示出，權重平均法未必一定優于簡單平均法。一般而言，在個體學習器性能相差較大時宜使用權重平均法，而在個體學習器性能相近時宜使用簡單平均法。

4.2.2 投票法

　　對于分類任務來說，學習器$h_i$将從類别标記集合{$c_1,c_2,...,c_N$}中預測出一個标記，最常見的結合政策是使用投票法(voting)。為便于讨論，我們将$h_i$在樣本$x$上的預測輸出表示出一個Ｎ維向量($h_i^1(x);h_i^2(x);...;h_N^1(x)$)，其中$h_i^j(x)$是$h_i$在類别标記$c_j$上的輸出。

針對投票法，有以下三種實作方式：

絕對多數投票法(majority voting)

\[H(x) = \left\{\begin{matrix}

c_j, \quad if \sum \limits_{i=1}^T h_i^j(x) > \frac{1}{2} \sum \limits_{k=1}^N \sum \limits_{i=1}^T h_i^k(x); \\

reject, \quad otherwise

\end{matrix}\right. \quad \quad (8.24)

即若某标記得票過半數，則預測為該标記；否則拒絕預測。

當某個類别$j$的基分類器的結果之和，大于所有結果之和的一半，則選擇該類别$j$為最終結果。

相對多數投票法(plurality voting)

\[H(x) = c_{\underset{j}{arg　max} \sum_{i=1}^T h_i^j(x)} \quad \quad (8.25)

即預測為得票最多的标記，若同時有多個标記獲得最高票，則從中随機選取一個。

相比與其他類别，該類别$j$的基分類器的結果之和最大，則選擇類别$j$為最終結果。
權重投票法(weighted voting)

\[H(x) = c_{\underset{j}{arg　max} \sum_{i=1}^T w_ih_i^j(x)} \quad \quad (8.26)

相比與其他類别，該類别$j$的基分類器的結果之和最大，則選擇類别$j$作為最終結果，與式(8.25)不同的是，該式在基分類器前面乘上一個權重系數，該系數大于等于0，且$T$個權重之和為1。

與權重平均法類似，$w_i$是$h_i$的權重，通常$w_i\geq 0$,$\sum \limits_{i=1}^T w_i = 1$.

　　标準的多數絕對投票法提供了“拒絕預測”選項，這在可靠性要求較高的學習任務是一個很好的機制。但若學習任務要求必須提供預測結果，則絕對多數投票法将退化為相對多數投票法。是以，在不允許拒絕預測的任務中，絕對多數、相對多數投票法統稱為“多數投票法”。

　　以上三種方法都沒有限制個體學習器輸出值的類型。在現實任務中，不同類型個體學習器可能産生不同類型的$h_i^j(x)$值，常見的有：

類标記：$h_i^j(x)∈\left\{0,1\right\}$，若$h_i$将樣本$x$預測為類别$c_j$則取值為1，否則為0。

使用類标記的投票亦稱“硬投票”(hard voting).
類機率：$h_i^j(x)∈\left[0,1\right]$，相當于對後驗機率$P(c_j|x)$的一個估計。

使用類機率的投票亦稱“軟投票”

需要注意的是，不同類型的$h_i^j(x)$值不能混用。

對一些能在預測出類别标記的同時，産生分類置信度的學習器，其分類置信度可轉化為類機率使用。

若此類值未進行規範化，例如支援向量機的分類間隔值，則必須使用一些技術如Platt縮放、等分回歸等進行“校準”(calibration)後才能作為類機率使用。有趣的是，雖然分類器估計出的類機率值一般都不太準确。

同時需要注意，若基學習器的類型不太，則類機率值不能直接進行比較；在此種情形下，通常可将類機率輸出轉化為類标記輸出(例如将類機率輸出最大的$h_i^j(x)$設為1，其他設為0)，然後再進行投票。

4.2.3 學習法

　　當訓練資料很多時，一種更為強大的集合政策是使用“學習法”，即通過另一個學習器來進行結合。

4.2.3.1 Stacking

　　Stacking是學習法的典型代表，這裡我們把個體學習器稱為初級學習器，用于結合的學習器稱為次級學習器或元學習器(meta-learner)。

　　Stacking先從初始資料集訓練出初級學習法，然後“生成”一個新資料集用于訓練次級學習器。在這個新Ｓ資料集中，初級學習器的輸出被當作樣例輸入特征，而初始樣本的标記仍被當作樣例标記。

算法Stacking的算法描述

Stacking的算法如下所示，這裡我們假定初級學習器使用不同學習算法産生，即初級內建是異質的。

初級學習算法$\mathcal{L}_1,\mathcal{L}_2,\ldots,\mathcal{L}_T$；

次級學習算法$\mathcal{L}$.

  1: for $t=1,\cdots,T$ do

  2:   $h_t=\mathcal{L}_t(D)$

  4: $D'=\emptyset$

  5: for $i=1,2,\ldots,m$ do

  6:   for $t=1,2,\ldots,T$ do

  7:     $z_{it}=h_t(x_i)$

  8:   end for

  9:   $D'=D' \cup ((z_{i1},z_{i2},\ldots,z_{iT}), y_i)$

  10: end for

  11: $h'=\mathcal{L}(D')$

輸出：$H(x)=h'(h_1(x),h_2(x),\ldots,h_T(x))$.

　　在訓練階段，次級訓練集是利用初級學習器産生的，若直接用初級學習器的訓練集來産生次級訓練集合，則過拟合風險會比較大；是以，一般是通過使用交叉驗證或留一法這樣的方式，用訓練初級學習器未使用的樣本來産生次級學習器的訓練樣本。

　　以k折交叉驗證為例，初始訓練集Ｄ被随機劃分為k個大小相似的集合$D_1,D_2,...,D_k$。令$D_j$和$\overline{D}_j$\ $D_j$分别表示第$j$折的測試集和訓練集。給定Ｔ個初級學習算法，初級學習器$h_t^{(j)}$通過在$\overline{D}_j$上使用第t個學習算法而得。對$D_j$中每個樣本$x_i$，令$z_{it}=h_t^{(j)}(x_i)$，則由$x_i$所産生的次級訓練樣例的示例部分為$z_{i}=(z_{i1};z_{i2};...;z_{iT})$，标記部分為$y_i$。于是，在整個交叉驗證過程結束後，從這T個初級學習器産生的次級訓練集是$D'=\left\{(z_{i},y_i)\right\}_{i=1}^m$，然後将$D’$将用于訓練次級學習器。

　　次級學習器的輸入屬性表示和次級學習算法對Stacking內建的泛化性能有很大影響。有研究表明，将初級學習器的輸出類機率作為次級學習器的輸入屬性，用多響應線性回歸(Multi-response Linear Regression，簡稱MLR)作為次級學習算法效果較好，在MLR中使用不同的屬性集更佳。｜

4.2.3.1 貝葉斯模型平均BMA

　　貝葉斯模型平均(Bayes Model Averaging，簡稱BMA)基于後驗機率來為不同模型賦予權重，可視為權重平均法的一種特殊實作。對Stacking和BMA進行了比較。理論上來說，若資料生成t模型恰在目前考慮的模型中，且資料噪聲很少，則BMA不差于Stacking；然而，在現實應用中無法確定資料生成模型一定在目前考慮的模型中，甚至可能難以用目前考慮的模型來近似，是以，Stacking通常優于BMA，因為其魯棒性比BMA更好，而且BMA對模型近似誤差非常敏感。

(五) 多樣性

5.1 誤差－分歧分解

　　根據前面的讨論，我們知道，欲建構泛化能力強的內建，個體學習器應“好而不同”。

　　假定我們用個體學習器$h_1,h_2,...,h_T$通過權重平均法$H(x) = \sum \limits_{i=1}^T w_ih_i(x).$結合産生的內建來完成回歸學習任務$f:\mathbb{R}^d \longmapsto \mathbb{R}$。

對示例$x$，定義$x$，定義學習器$h_i$的“分歧”為

\[A(h_i|x) = (h_i(x)-H(x))^2 \quad \quad (8.27)

該式表示個體學習器結果與預測結果的內插補點的平方，即為個體學習器的“分歧”。

則內建的“分歧”是

\[\overline{A}(h|x) = \begin{equation*}{\sum}_{i=1}^{T}\end{equation*}w_iA(h_i|x) \\

= \sum_{i=1}^{T}w_i(h_i(x)-H(x))^2 \quad \quad (8.28)

該式表示對各個個體學習器的“分歧”權重平均的結果，即內建的“分歧”。

顯然，這裡的“分歧”項表征了個體學習器在樣本$x$上的不一緻性，即在一定程度上反映了個體學習器的多樣性。個體學習器$h_i$和內建H的平方誤差分别為

\[E(h_i|x) = (f(x)-h_i(x))^2 \quad \quad (8.29)\\

該式表示個體學習器與真實值之間內插補點的平方，即個體學習器的平方誤差。

\[E(H|x) = (f(x) - H(X))^2 \quad \quad (8.30)

該式表示內建與真實值之間內插補點的平方，即內建的平方誤差。

令$\overline{A}(h|x)=\sum_{i=1}^T w_i\cdot E(h_i|x)$表示個體學習器誤差的權重均值，有

\[\overline{A}(h|x) = \sum \limits_{i=1}^T w_iE(h_i|x) - E(H|x) \\

= \overline{E}(h|x) - E(H|x). \quad \quad (8.31)

式(8.31)的推導

由式(8.28)可知

　　　　$\overline{A}(h|x) = \sum \limits_{i=1}^T w_i(h_i(x) - H(x))^2 \\ = \sum limits_{i=1}^T w_i(h_i(x)^2 - 2h_i(x)H(x) + H(x)^2) \\ = \sum \limits_{i=1}^T w_ih_i(x)^2 - H(x)^2$

又因為

　　　　$\sum \limits_{i=1}^T w_iE(h_i|x) - E(H|x) \\ = \sum \limits_{i=1}^T w_i(f(x) - h_i(x))^2 - (f(x)-H(x))^2 \\ = \sum \limits_{i=1}^T w_ih_i(x)^2 - H(x)^2$

是以

　　　　$\overline{A}(h|x) = \sum \limits_{i=1}^T w_iE(h_i|x) - E(H|x)$

上式對所有樣本$x$均成立，令$p(x)$表示樣本的機率密度，則在全樣本上有

\[\sum \limits_{i=1}^T w_i \int A(h_i|x)p(x)dx = \sum \limits_{i=1}^T w_i \int E(h_i|x)p(x)dx - \int E(H|x)p(x)dx \quad \quad (8.32)

$\int A(h_i|x)p(x)dx$表示個體學習器在全樣本上的“分歧”，

$\sum_{i=1}^T w_i \int A(h_i|x)p(x)dx$表示內建在全樣本上的“分歧”，然後根據式(8.31)拆成誤差的形似。

類似的，個體學習器$h_i$在全樣本上的泛化誤差和分歧項分别為

\[E_i = \int E(h_i|x)p(x)dx \quad \quad (8.33)\\

表示個體學習器在全樣本上的泛化誤差。

\[A_i = \int A(h_i|x)p(x)dx \quad \quad (8.34)\\

表示個體學習器在全樣本上的分歧。

內建的泛化誤差為

\[E = \int E(H|x)p(x)dx \quad \quad (8.35)

表示內建在全樣本上的泛化誤差。

将$E_i$,$A_i$,$E$代入$\sum \limits_{i=1}^T w_i \int A(h_i|x)p(x)dx = \sum \limits_{i=1}^T w_i \int E(h_i|x)p(x)dx - \int E(H|x)p(x)dx$，再令$\overline{E}=\sum_{i=1}^T w_iE_i$表示個體學習器泛化誤差的權重均值，$\overline{A}=\sum_{i=1}^T w_iA_i$表示個體學習器的權重分歧值，有

\[E = \overline{E}-\overline{A} \quad \quad (8.36)

$\overline{E}$表示個體學習器泛化誤差的權重均值，$\overline{A}$表示個體學習器分歧項的權重均值，該式稱為“誤差-分歧分解”。

上面這個漂亮的式子，明确提示出：個體學習器準确性越高、多樣性越大，則內建越好。

上面這個分析首先由[Krogh and Vedelsby,1995]給出，稱為“誤差－分歧分解”

這裡需要注意的是，我們直接将$\overline{E}-\overline{A}$作為優化目标來求解，在現實任務中是很難直接實作的。不僅由于它們是定義在整個樣本空間上，還由于$\overline{A}$不是一個可直接操作的多樣性度量，它僅在內建構造好之後才能進行估計。此外，還需要注意的是，上面的推導過程隻适用于回歸學習，難以直接推廣到分類學習上去。

5.2 多樣性度量

　　顧名思義，多樣性度量(diversity measure)是用于度量內建中個體分類器的多樣性，即估算個體學習器的多樣化程度。典型做法是考慮個體分類器的兩兩相似/不相似性。

　　給定資料集D＝{$(x_1,y_1),(x_2,y_2),...,(x_m,y_m)$}，對二分類任務，$y_i∈\left\{-1,+1\right\}$，分類器$h_i$與$h_j$的預測結果列聯表(contingency table)為

$h_i=+1$	$h_i=-1$
$h_j=+1$	a	c
$h_j=-1$	b	d

其中，$a$表示$h_i$與$h_j$均預測為正類的樣本數目；$b,c,d$含義由此類推；

$a+b+c+d=m$。基于這個列聯表，下面給出一些常見的多樣性度量。

不合度量(disagreement measure)

\[dis_{ij} = \frac{b+c}{m}　\quad \quad (8.37)

$dis_{ij}$的值域為[0,1]。值越大則多樣性越大。
相關系數(correlation coefficient)

\[p_{ij} = \frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}} \quad \quad (8.38)

$p_{ij}$為值域為[-1,+1]。若$h_i$和$h_j$無關，則值為0；若$h_i$與$h_j$正相關則值為正，否則為負。
Q-統計量(Q-statistic)

\[Q_{ij} = \frac{ad-bc}{ad+bc} \quad \quad (8.39)

$Q_{ij}$與相關系數$p_{ij}$的符号相同，且$|Q_{ij}|\leq|p_{ij}|$.
$\kappa-$統計量($\kappa-$statistic)

\[\kappa = \frac{p_1-p_2}{1-p_2} \quad \quad (8.40)

式(8.40)的解釋

當$p_1 = p_2$時，$\kappa = 0$；當$p_1 = 1$時，$\kappa = 1$；

一般來說，$p_1 \geq p_2$，即$\kappa \geq 0$，但偶爾也有$p_1 < p_2$的情況，此時$\kappa < 0$。

其中，$p_1$是兩個分類器取得一緻的機率；$p_2$是兩個分類器偶然達到一緻的機率，它們可由資料集$D$估算：

\[p_1 = \frac{a+d}{m} \quad \quad (8.41) \\

式(8.41)的解釋

分子$a+d$為分類器$h_i$與$h_j$在資料集$D$上預測結果相同的樣本數目，分母為資料集$D$總數目，是以$p_1$為兩個分類器$h_i$與$h_j$預測結果相同的機率。

若$a + d = m$，即分類器$h_i$與$h_j$對資料集$D$所有樣本預測結果均相同，此時$p_1 = 1$。

\[p_2 = \frac{(a+b)(a+c)+(c+d)(b+d)}{m^2} \quad \quad (8.42)
式(8.42)的解釋

　　将式(8.42)拆分為如下形似，将會很容易了解其含義：

　　　　$p_2 = \frac{a + b}{m} \cdot \frac{a + c}{m} + \frac{c + d}{m} \cdot \frac{b + d}{m}$

　　其中$\frac{a + b}{m}$為分類器$h_i$将樣本預測為$+1$的機率，$\frac{a + c}{m}$為分類器$h_j$将樣本預測為+1的機率，二者相乘$\frac{a + b}{m} \cdot \frac{a + c}{m}$了解為分類器$h_i$與$h_j$将樣本預測為+1的機率；$\frac{c+d}{m}$為分類器$h_i$将樣本預測為-1的機率，$\frac{b + d}{m}$為分類器$h_j$将樣本預測為-1的機率，二者相乘$\frac{c+d}{m} \cdot \frac{b + d}{m}$可了解為分類器$h_i$與$h_j$将樣本預測為-1的機率．

　　這裡需要注意下$\frac{a + b}{m} \cdot \frac{a + c}{m}$與$\frac{a}{m}$的不同，$\frac{c + d}{m} \cdot \frac{b + d}{m}$與$\frac{d}{m}$的不同：

　　$\frac{a + b}{m} \cdot \frac{a + c}{m} = p(h_i = +1)p(h_j = +1)$

　　$\frac{a}{m} = p(h_i = +1, h_j = +1)$

　　$\frac{c + d}{m} \cdot \frac{b + d}{m} = p(h_i = -1)p(h_j = -1)$

　　$\frac{d}{m} = p(h_i =-1, h_j = -1)$

即$\frac{a + b}{m} \cdot \frac{c + d}{m} \cdot \frac{b + d}{m}$是分别考慮分類器$h_i$與$h_j$時的機率($h_i$與$h_j$獨立)，而$\frac{a}{m}$和$\frac{d}{m}$是同時考慮$h_i$與$h_j$時的機率)(聯合機率)。

若分類器$h_i$與$h_j$在D上完全一緻，則$\kappa=1$;若它們僅是偶然達成一緻，則$\kappa=0$。

$\kappa$通常為非負值，僅在$h_i$與$h_j$達成一緻的機率甚至低于偶然性的情況下取負值。

　　以上介紹的都是“成對型”(pairwise)多樣性度量，它們可以容易地通過2維圖繪制出來。例如著名的“$\kappa-$誤差圖”，就是将每一對分類器作為圖上的一個點，橫坐标是這對分類器的$\kappa$值，縱坐标是它們的平均誤差，下圖給出了一個例子。顯然，資料點雲的位置越高，則個體分類器準确性越低；點雲的位置越靠右，則個體學習器的多樣性越小。

5.3 多樣性增強

　　在內建學習中需要有效地生成多樣性大的個體學習器。與簡單地直接用初始資料訓練出個體學習器，如何增強多樣性呢？一般思路是在學習過程中引入随機性，常見做法主要是對資料樣本、輸入屬性、輸出表示、算法參數進行擾動。

資料樣本擾動

　　給定初始資料集，可從中産生出不同的資料子集，再利用不同的資料子集訓練出不同的個體學習器。

資料樣本擾動通常是基于采樣法，例如在Bagging張使用自助采樣，在AdaBoost中使用序列采樣。此類做法簡單高效，使用最廣。對很多常見的基學習器，例如決策樹、神經網絡等，訓練樣本稍加變化就會導緻學習器有顯著變動，資料樣本擾動法對這樣的“不穩定基學習器”很有效；然而，有一些基學習器對資料樣本的擾動不敏感，例如線性學習器、支援向量機、樸素貝葉斯、k近似學習器等，這樣的基學習器稱為穩定基學習器(stable base learner)，對此類基學習器進行內建往往需使用輸入屬性擾動等其他機制。

輸入屬性擾動

　　訓練樣本通常是一組屬性描述，不同的“子空間”(subspace，即屬性子集)提供了觀察資料的不同視角。顯然，從不同子空間訓練出個體學習器必然有所不同。著名的随機子空間(random subspace)算法就依賴于輸入屬性擾動，該算法從初始屬性集中抽取出若幹個屬性子集，再基于每個屬性子集訓練一個基學習器。

　　算法描述如下所示。對包含大量備援屬性的資料，在子空間中訓練個體學習器不僅能産生多樣性大的個體，還會因屬性數的減少而大幅節省時間開銷，同時，由于備援屬性多，減少一些屬性後訓練出的個體學習器也不至于太差。若資料隻包含少量屬性，或者備援屬性很少，則不宜使用輸入屬性擾動法。

随機子空間算法描述

輸入：訓練集D={$(x_1,y_1),(x_2,y_2),...,(x_m,y_m)$};

　　　基學習算法$\mathcal{L}$；

　　　基學習器數T；

　　　子空間屬性$d'$;

1:　for $t=1,2,...,T$ do

2:　　$\mathcal{F}_t=RS(D,d')$

3: 　　$D_t=Map_{\mathcal{F}_t}(D)$

4:　　 $h_t = \mathcal{L}(D_t)$

5:　end for

輸出：$H(x)=\underset{y∈\mathcal{Y}}{arg　max}\sum_{t=1}^T\mathbb{I}(h_t(Map_{\mathcal{F}_t}(x))=y)$

輸出表示擾動
　此類做法的基本思路是對輸出表示進行操縱以增強多樣性。可對訓練樣本的類标記稍作變動，如“翻轉”(Flipping Output)随機改變一些訓練樣本的标記；也可對輸出表示進行轉化，如“輸出調制法”(Output Smearing)将分類輸出轉化為回歸輸出後建構個體學習器；還可将原任務拆解為多個可同時求解的子任務，如EOOC法利用糾錯輸出碼将多分類任務拆解為一系列二分類任務來訓練基學習器。
算法參數擾動

　　基學習算法一般都有參數需進行設定，例如神經網絡的隐層神經元數、初始連接配接權值等，通過随機設定不同的參數，往往可産生差别較大的個體學習器。例如“負相關法”(Negative Correlation)顯式地通過正則化項來強制個體神經網絡使用不同的參數。對參數較少的算法，可通過将其學習過程中某些類似方式來替代，進而達到擾動的目的，例如可将決策樹使用的屬性選擇機制替換成其他的屬性選擇機制。值得指出的是，使用單一學習器時通常需使用交叉驗證等方法來确定參數值，這事實上已使用了不同參數訓練出多個學習器，隻不過最終僅選擇其中一個學習器進行使用，而內建學習則相當于把這些學習器都利用起來；由此也可看出，內建學習技術的實際計算開銷并不比使用單一學習器大很多。

　

　　不同的多樣性增強機制可同時使用，例如随機森林中同時使用了資料樣本擾動和輸入屬性擾動，有些方法甚至同時使用了更多機制。

在內建學習中，梯度提升(Gradient Boosting，GB)、梯度提升樹(GB Decision Tree，GBDT)很常見，尤其是近幾年非常流行的XGBoost不可忽略，此處單獨介紹對比這些機率。

6.1 梯度下降法

設目标函數$f(x)$在$x_k$附近連續可微，且$\nabla f(x_k) = \frac{\nabla f(x)}{\nabla x}\bigg|_{x= x_k} \neq 0$。将$f(x)$在$x_k$處進行一階$Taylor$展開

\[f(x) \approx f(x_k) + \nabla f(x_k)^T(x - x_k)

記$x - x_k = \Delta x$，則上式可寫為

\[f(x_k + \Delta x) \approx f(x_k) + \nabla f(x_k)^T \Delta x

顯然，若$\nabla f(x_k)^T \Delta x < 0$，則有$f(x_k + \Delta x) < f(x_k)$，即相比于$f(x_k)$，自變量增量$\Delta x$會使$f(x)$函數值下降；若要使$f(x) = f(x_k + \Delta x)$下降最快，隻要選擇$\Delta x$使$\nabla f(x_k)^T \Delta x$最小即可，而此時$\nabla f(x_k)^T \Delta x < 0$，是以使絕對值$|\nabla f(x_k)^T \Delta x|$最大即可。将$\Delta x$分成兩部分：$\Delta x = \alpha_k d_k$，其中$d_k$為待求機關向量，$\alpha_k > 0$為待解向量；$d_k$表示往哪個方向改變$x$函數值下降最快，而$\alpha_k$表示沿這個方向的步長。是以，求解$\Delta x$的問題變為

\[(\alpha_k, d_k) = \mathop{\arg\min}_{\alpha,d} \nabla f(x_k)^T \alpha d

将以上優化問題分為兩步來求解，即

\[d_k = \mathop{\arg\min}_{d} \nabla f(x_k)^T d \quad \text{s.t.}||d||_2 =1 \\

\alpha_k = \mathop{\arg\min}_{\alpha} \nabla f(x_k)^T d_k \alpha

以上求解$\alpha_k$的優化問題明顯有問題，因為對于$\nabla f(x_k)^T d_k < 0$來說，顯然$\alpha_k = +\infty$時取得最小值，求解$\alpha_k$應該求解如下優化問題：

\[\alpha_k = \mathop{\arg\min}_{\alpha} f(x_k + \alpha d_k)

對于凸函數來說，以上兩步可以得到最優解；但對非凸函數來說，聯合求解得到$d_k$和$\alpha_k$，與先求$d_k$然後基于此再求$\alpha_k$的結果應該有時是不同的。

　　由Cauchy-Schwarrtz不等式

\[|\nabla f(x_k)^T d_k| \leq ||\nabla f(x_k)||_2 ||d_k||_2

可知，當且僅當$d_k = -\frac{\nabla f(x_k)}{||\nabla f(x_k)||_2}$時，$\nabla f(x_k)^T d_k$最小，$-\nabla f(x_k)^T d_k$最大。

　　對于$\alpha_k$，若$f(x_k + \alpha d_k)$對$\alpha$的導數存在，則可簡單求解如下單變量方程即可：

\[\frac{\partial f(x_k + \alpha d_k)}{\partial \alpha} = 0

下面通過兩個例題來幫助了解：

例1：試求$f(x) = x^2$在$x_k = 2$處的梯度方向$d_k$和步長$\alpha_k$。

解：對$f(x)$在$x_k = 2$處進行一階Taylor展開:

\[f(x) = f(x_k) + f'(x_k)(x - x_k) \\

= x_k^2 + 2x_k(x - x_k) \\

= x_k^2 + 2x_k \alpha d

由于此時自變量為一維，是以隻有兩個方向可以選擇，要麼正方向，要麼反方向。

此時得出$f'(x_k) = 4$，是以$d_k = -\frac{f'(x_k)}{|f'(x_k)|} = -1$。

接下來求$\alpha_k$，将$x_k$和$d_k$代入：

\[f(x_k + \alpha d_k) = f(2 - \alpha) = (2 - \alpha)^2

進而有

\[\frac{\partial f(x_k + \alpha d_k)}{\partial \alpha} = -2(2 - \alpha)

令導數等于0，得$\alpha_k = 2$。

則此時

\[\Delta x = \alpha_k d_k = -2

則$x_k + \Delta x = 0$，函數值$f(x_k + \Delta x) = 0$。

例2：試求$f(x) = ||x||_2^2 = x^Tx$在$x_k = [x_k^1,x_k^2]^T = [3,4]^T$處的梯度方向$d_k$和步長$\alpha_k$。

解：對$f(x)$在$x_k = [x_k^1, x_k^2]^T = [3,4]^T$處進行一階Taylor展開：

\[f(x) = f(x_k) + \nabla f(x_k)^T (x - x_k) \\

= ||x||_2^2 + 2x_k^T(X - X_K) \\

= ||X||_2^2 + 2X_k^T \alpha d

此時$\nabla f(x_k) = [6,8]^T$,是以$d_k = - \frac{\nabla f(x_k)}{||\nabla f(x_k)||_2} = [-0.6, -0.8]^T$。

接下來求$\alpha_k$，将$x_k$和$d_k$代入:

\[f(x_k + \alpha d_k) = (3 - 0.6 \alpha)^2 + (4 - 0.8 \alpha)^2 \\

= \alpha^2 - 10 \alpha + 25 \\

= (\alpha -5)^2

是以可得$\alpha_k = 5$(或對$\alpha$求導，再令導數等于0)。此時

\[\Delta x = \alpha_k d_k = [-3, -4]^T

則$x_k+\Delta x = [0,0]^T$,函數值$f(x_k+\Delta x) = 0$。

通過以上分析，需要突出強調兩點：

(1)梯度下降法求解下降速度最快的方向$d_k$時應該求解如下優化問題：

\[d_k = \mathop{\arg\min}_{d} \nabla f(x_k)^T d \text{s.t.} ||d||_2 = C

其中$C$為常量，即不必嚴格限定$||d_k||_2 = 1$，隻要固定向量長度，與$\alpha_k$搭配即可。

(2)梯度下降法求解步長$\alpha_k$應該求解如下優化問題：

實際應用中，很多時候不會去求最優的$\alpha_k$，而是靠經驗設定一個步長。

6.2 從梯度下降的角度解釋AdaBoost

AdaBoost第$t$輪疊代時最小化式(8.5)的指數損失函數

\[\ell_{exp}(H_t|\mathcal{D}) = \mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H_t(x)}] = \sum \limits_{x \in D}\mathcal{D}(x)e^{-f(x)H_t(x)}

對$\ell_{exp}(H_t|\mathcal{D})$每一項在$H_{t-1}$處泰勒展開

\[\ell_{exp}(H_t|\mathcal{D}) \approx \sum \limits_{x \in D} \mathcal{D}(x) (e^{-f(x)H_{t-1}(x)} - f(x)e^{-f(x)H_{t-1}(x)}(H_t(x) - H_{t-1}(x))) \\

= \sum \limits_{x \in D}\mathcal{D}(E^{-f(x)H_{t-1}(x)} - e^{-f(x)H_{t-1}(x)}f(x)\alpha_t h_t(x)) \\

= \mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H_{t-1}(x)} - e^{-f(x)H_{t-1}(x)}f(x)\alpha_th_t(x)]

其中$H_t = H_{t-1} + \alpha_t h_t$。注意：$\alpha_t，h_t$是第$t$輪待解的變量。

另外補充以下，在上式展開中的變量為$H_{t}(x)$，在$H_{t-1}$處一階導數為

\[\frac{\partial e^{-f(x)H_t(x)}}{\partial H_t(x)}\bigg|_{H_t(x) = H_{t-1}(x)} = -f(x)e^{-f(x)H_{t-1}(x)}

如果看不習慣上述泰勒展開過程，可令變量$z = H_t(x)$和函數$g(x) = e^{-f(x)z}$，對$g(z)$在$z_0 = H_{t-1}(x)$處泰勒展開，得

&g(z) \approx g(z_0) + g'(z_0)(z-z_0) \\

&= g(z_0) - f(x)e^{-f(x)z_0}(z - z_0) \\

&= e^{-f(x)H_{t-1}(x)} - e^{-f(x)H_{t-1}(x)}f(x)(H_t(x) - H_{t-1}(x)) \\

&=e^{-f(x)H_{t-1}(x)} - e^{-f(x)H_{t-1}(x)}f(x)\alpha_t h_t(x)

注意此處$h_t(x) \in \left\{-1,+1\right\}$，類似于梯度下降法中的限制$||d_k||_2 = 1$。

　　類似于梯度下降法求解下降最快的方向$d_k$，此處先求$h_t$(先不管$\alpha_t$):

\[h_t = \mathop{\arg\min}_{h} \sum \limits_{x \in D}\mathcal{D}(x) (-e^-f(x)H_{t-1}(x))f(x)h(x)) \text{s.t.} h(x) \in \left\{-1, +1 \right\}

将負号去掉，最小化變為最大化問題

\[h_t = \mathop{\arg\max}_{h} \sum \limits_{x \in D}\mathcal{D}(x) (e^{-f(x)H_{t-1}(x)}f(x)h(x)) \\

= \mathop{\arg\max}_{h} \mathbb{E}_{x \in \mathcal{D}}[e^{-f(x)H_{t-1}(x)}f(x)h(x)] \quad \text{s.t.} h(x) \in \left\{-1, +1\right\}

這就是式(8.14)的第3個等号的結果(其餘推導參見8.2節即可)

　　由于這裡的$h(x)$限制較強，是以不能直接取負梯度方向，書中經過推導得到了$h_t(x)$的表達式，即式(8.18)。實際上，可以将此結果了解為滿足限制條件的最快下降方向。

　　求得$h_t(x)$之後再求$\alpha_t$:

\[\alpha_k = \mathop{\arg\min}_{\alpha} \ell_{exp}(H_{t-1} + \alpha h_t |\mathcal{D})

對指數損失函數$\ell(H_{t-1}+\alpha h_t|\mathcal{D})$求導，得

\[\frac{H_{t-1}+\alpha h_t|\mathcal{D}}{\partial \alpha} = \frac{\partial \left(e^{-\alpha}\sum_{i=1}^{|D|}\mathcal{D}_t'(x_i)+(e^{\alpha}-e^{-\alpha})\sum \limits_{i=1}^{|D|}\mathcal{D}_t'(x_i) \mathbb{I}(f(x_i) \neq h(x_i)) \right)}{\partial \alpha} \\

= -e^{-\alpha} \sum \limits_{i=1}^{|D|}\mathcal{D}_t'(x_i) + (e^{\alpha} + e^{-\alpha})\sum \limits_{i=1}^{|D|}\mathcal{D}_t'(x_i) \mathbb{I}(f(x_i) \neq h(x_i))

令導數等于零，得

\[\frac{e^{-\alpha}}{e^{\alpha} + e^{-\alpha}} = \frac{\sum_{i=1}^{|D|}\mathcal{D}_t'(x_i)\mathbb{I}(f(x_i) \neq h(x_i))}{\sum_{i=1}^{|D|}\mathcal{D}_t'(x_i)} = \sum \limits_{i=1}^{|D|} \frac{\mathcal{D}_t'(x_i)}{Z_t}\mathbb{I}(f(x_i) \neq h(x_i)) \\

= \sum \limits_{i=1}^{|D|}\mathcal{D}_t(x_i)\mathbb{I}(f(x_i) \neq h(x_i)) = \mathbb{E}_{x \sim \mathcal{D}_t}[\mathbb{I}(f(x_i) \neq h(x_i))] \\

= \epsilon_t

對上述等式化簡，可得

\[\frac{e^{-\alpha}}{e^{\alpha}+e^{-\alpha}} = \frac{1}{e^{2\alpha} + 1} \Rightarrow e^{2\alpha}+1 = \frac{1}{\epsilon_t} \\

\Rightarrow e^{2 \alpha} = \frac{1 - \epsilon_t}{\epsilon_t} \Rightarrow 2\alpha = ln(\frac{1 - \epsilon_t}{\epsilon_t}) \\

\Rightarrow \alpha_t = \frac{1}{2}ln(\frac{1 - \epsilon_t}{\epsilon_t})

即式(8.11)。

通過以上推導可以發現：AdaBoost每一輪的疊代就是基于梯度下降法求解損失函數為指數損失函數的二分類問題(限制條件$h_t(x) \in \left\{-1, +1\right\}$)。

6.3 梯度提升(Gradient Boosting)

　　将AdaBoost的問題一般化，即不限定損失函數為指數損失函數，也不局限于二分類問題，則可以将式(8.5)寫為更一般化的形式

\[\ell(H_t|\mathcal{D}) = \mathbb{E}_{x \sim \mathcal{D}}[err(H_t(x), f(x))] \\

= \mathbb{E}_{x \sim \mathcal{D}}[err(H_{t-1}(x) + \alpha_t h_t(x), f(x))]

易知，當$f(x) \in \left\{-1, +1 \right\}$且$err(H_t(x), f(x)) = e^{-f(x)H_t(x)}$時，就是式(8.5)。

當時回歸問題時，$f(x) \in \mathbb{R}$，損失函數可使用平方損失$err(H_t(x), f(x)) = (H_t(x) - f(x))^2$。

　　針對該一般化的損失函數和一般的學習問題，要通過$T$輪疊代得到學習器

\[H(x) = \sum \limits_{t=1}^T \alpha_t h_t(x)

類似于AdaBoost，第$t$輪得到$\alpha_t, h_t(x)$，可先對損失函數在$H_{t-1}(x)$處進行泰勒展開:

\[\ell_{H_t|\mathcal{D}} \approx \mathbb{E}_{x \sim \mathcal{D}} \left[err(H_{t-1}(x), f(x)) + \frac{\partial err(H_t(x), f(x))}{\partial H_t(x)} \bigg|_{H_t(x) = H_{t-1}(x)}(H_t(x) - H_{t-1}(x))\right] \\

= \mathbb{E}_{x \sim \mathcal{D}} \left[err(H_{t-1}(x), f(x)) + \frac{\partial err(H_t(x),f(x))}{\partial H_t(x)}\bigg|_{H_t(x) = H_{t-1}(x)}\alpha_t h_t(x) \right] \\

= \mathbb{E}_{x \sim \mathcal{D}}[err(H_{t-1}(x), f(x))] + \mathbb{E}_{x \sim \mathcal{D}} \left[\frac{\partial err(H_t(x), f(x))}{\partial H_t(x)}\bigg|_{H_t(x) = H_{t-1}(x)} \alpha_t h_t(x) \right]

注意，在上式展開中的變量為$H_t(x)$，且有$H_t(x) = H_{t-1}(x) + \alpha_t h_t(x)$(類似于梯度下降法中$x = x_k + \alpha_k d_k$)。上式中括号内第1項為常量$\ell(H_{t-1}|\mathcal{D})$，最小化$\ell(H_t|\mathcal{D})$隻須最小化第二項即可。

先不考慮權重$\alpha_t$，求解如下優化問題$h_t(x)$：

\[h_t(x) = \mathop{\arg\min}_{h} \mathbb{E}_{x \sim \mathcal{D}} \left[\frac{\partial err(H_{t}(x), f(x))}{\partial H_t(x)}\bigg|_{H_t(x) = H_{t-1}(x)}h(x) \right] \quad \text{s.t.} \quad constraints \quad for h(x)

解得$h_t(x)$之後，再求解如下優化問題可得權重$\alpha_t$：

\[\alpha_t = \mathop{\arg\min}_{\alpha} \mathbb{E}_{x \sim \mathcal{D}}[err(H_{t-1}(x) + \alpha h_t(x), f(x))]

以上就是梯度提升(Gradient Boosting)的理論架構，即每輪通過梯度(Gradient)下降的方式将$T$個弱學習提升(Boosting)為強學習器可以看出AdaBoost是其特殊形式。

Gradient Boosting 算法的官方版本參見[Friedman J H. Greedy function approximation: a gradient boosting machine[J]. Annals of statistics, 2001: 1189-1232.]的第 5-6 頁(第 1193-1194 頁):

& ALGORITHM　1(Gradient_Boost) \\

& 1. F_0(x) = \mathop{\arg\min}_{p}\sum_{i=1}^N L(y_i,\rho)　\\

& 2. For \quad m = 1 \quad to \quad M \quad do:\\

& 3. \tilde{y_i} = -[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}]_{F(x) = F_{m-1}(x)}，i = 1,N \\

& 4. a_m = \mathop{\arg\min}_{a, \beta}\sum_{i=1}^N L(y_i, F_{m-1}(x_i) + \rho(x_i; a_m)) \\

& 5. \rho_m = \mathop{\arg\min}_{\rho}\sum_{i=1}^N L(y_i, F_{m-1}(x) + \rho h(x_i; a_m)) \\

& 6. F_m(x) = F_{m-1}(x) + \rho_mh(x; a_m) \\

& 7. end \quad For \\

& end \quad Algorithm

直覺地來看，該僞代碼針對的還是在任意損失函數$L(y_i, F(x_i))$下的回歸問題。

Algorithm 1中第3步和第4不意思是用$\beta h(x_i, a)$拟合$F(x) = F_{m-1}(x)$負梯度，但第4步表示隻求參數$a_m$，第5步單獨求解參數$\rho_m$，這裡的疑問是為什麼第4步要用最小二乘法(即3.2節的線性回歸)去拟合負梯度(或僞殘差)？

　　簡單了解如下：第4步要解的$h(x_i,a)$相當于梯度下降法中的待解的下降方向$d$，在梯度下降法中也已提到不必嚴格限制$||d||_2 = 1$，長度可以由步長$\alpha$調節(例如前面梯度下降解釋中的例1，若直接取$d_k = -f'(x_k) = -4$,則可得$\alpha_k = 0.5$，仍有$\Delta x = \alpha_k d_k = -2$)，是以第4步直接用$h(x_i, a)$拟合負梯度，與梯度下降中限制$||d||_2 = 1$的差別在于未對負梯度除以其模值進行歸一化而已。

　　那為什麼不是直接令$h(x_i, a)$等于負梯度呢?因為這裡實際是求假設函數$h$，将資料集中所有的$x_i$經假設函數$h$映射到對應的僞殘差(負梯度)$\tilde{y_i}$，是以隻能做線性回歸了。

　　李航《統計學習方法》第8.4.3節中的算法8.4并未顯式展現參數$\rho_m$，這應該是第2步的$(c)$步完成的，因為$(b)$步隻是拟合一棵回歸樹(相當于Algorithm 1第5步解得$rho_m$，隻是每個葉節點均對應一個$rho_m$)；而且回歸問題中基函數為實值函數，可以将參數$\rho_m$吸收到基函數中。

6.4 梯度提升樹

本部分無實質 GBDT 内容,僅為梳理 GBDT 的概念,具體可參考給出的資源連結。

對于 GBDT,一般資料是按 Gradient Boosting+CART 處理回歸問題講解的,如林軒田《機器學習技法》課程第 11 講(損失函數為平方損失, PPT 中的 C&RT 是 http://pages.stat.wisc.edu/~loh/treeprogs/guide/wires11.pdf的基礎版本) :

Gradient Boosted Decision Tree(GBDT)

　　但是,分類問題也可以用回歸來處理,例如 3.3 節的對數幾率回歸,隻需将平方損失換

為對率損失(參見式(3.27)和式(6.33),二者關系可參見第 3 章注解中有關式(3.27)的推導)

即可。部落格梯度提升樹(GBDT)原理小結(https://www.cnblogs.com/pinard/p/6140514.html)從更

一般的角度推導了 GBDT,包括 GBDT 回歸版本和分類版本。

特别地,林軒田老師(個人首頁:https://www.csie.ntu.edu.tw/~htlin/)的《機器學習基

石》和《機器學習技法》兩門課程的首頁參見 https://www.csie.ntu.edu.tw/~htlin/mooc/,課程

視訊 https://www.bilibili.com/video/av12463015/和 https://www.bilibili.com/video/av12469267/。

6.5 XGBoost

本部分無實質 XGBoost 内容,僅為梳理 XGBoost 的概念,具體可參考給出的資源連結。

首先,XGBoost 是 eXtreme Gradient Boosting 的簡稱。

其次,XGBoost 與 GBDT 的關系,可大緻類比為 LIBSVM 與 SVM(或 SMO 算法)的

關系。LIBSVM 是 SVM 算法的一種高效實作軟體包,XGBoost 是 GBDT 的一種高效實作;

在實作層面,LIBSVM 對 SMO 算法進行了許多改進,XGBoost 也對 GBDT 進行了許多改進;

另外,LIBSVM 擴充了許多 SVM 變體,XGBoost 也不再僅僅是标準的 GBDT,也擴充了一

些其它功能。

最後,XGBoost 是由陳天奇(個人首頁:https://homes.cs.washington.edu/~tqchen/)開發

的;XGBoost 論文發表在 KDD’16 上,可在 arXiv 下載下傳 https://arxiv.org/abs/1603.02754;

XGBoost 工具包首頁 https://xgboost.ai/,文檔 https://xgboost.readthedocs.io/en/latest/,源碼

https://github.com/dmlc/xgboost;統計之都(https://cosx.org/)曾對陳天奇做過一個采訪,參見

《COS 訪談第 18 期:陳天奇》(https://cosx.org/2015/06/interview-of-tianqi),裡面介紹的一

些有關作者的資訊是論文中看不到的。

官方文檔開篇如是介紹 XGBoost:

GB、 GBDT、 XGBoost 的遞進關系簡單介紹可參見:一步一步了解 GB、 GBDT、 xgboost

(https://www.cnblogs.com/wxquare/p/5541414.html);另外,有關 XGBoost 介紹,很多人推薦

陳天奇的 PPT:https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf。

6.6 本章小結

本章内容整體上看并不複雜 , 可以看成是作者的英文專著《 Ensemble Methods:Foundations and Algorithms》 (https://book.douban.com/subject/10494228/,據悉該書中文版即

将由電子工業出版社出版)的精簡版,但 8.2 節有關 AdaBoost 的推導感覺很難吃透,尤其是本節還涉及到如 Gradient Boosting、GBDT、XGBoost 等概念,是以必須讀一些原始文獻和其它參考資料方能對此有所了解,下面對這些概念進行一個簡單的梳理。

提升(Boosting)是一族可将弱學習提升為強學習器的算法,弱學習器間存在強依賴關系、

必須串行生成。這族算法的工作機制類似:先從初始訓練集訓練出一個基學習器,再根據基學習器的表現對訓練樣本分布進行調整,使得先前基學習器做錯的訓練樣本在後續受到更多關注,然後基于調整後打着本分布來訓練下一個基學習器;如此重複進行,直至基學習器數目達到事先指定的值 T,最終将這 T 個基學習器進行權重結合。(摘自西瓜書 P173)

提升樹(Boosting Tree)是以決策樹為基學習器的提升方法(i.e.,Boosting+ Decision Tree)。

對分類問題決策樹是二叉分類樹,對回歸問題決策樹是二叉回歸樹。

(李航《統計學習方法》 )

梯度提升(Gradient Boosting)是基于加法模型和前向分步算法一種理論架構,并不限定損失函數,也不限定基分類器的類型(類型包含兩層含義:第 1 層如分類和回歸等;第 2層如決策樹、SVM、神經網絡等)。

梯度提升樹(GBDT) = Gradient Boosting + Decision Tree (CART),這裡 CART 取為回歸樹。李航《統計學習方法》第 8.4.3 節中的算法 8.4 實際為 GBDT 算法,與劉建平 Pinard 部落格《梯度提升樹(GBDT)原理小結》介紹基本一緻,林軒田《機器學習技法》課程第 11 講則特指損失函數為平方損失。

特别地,8.2 節介紹的 AdaBoost(Adaptive Boosting)是當 Gradient Boosting 中損失函數為指數損失函數、基分類器為二分類(隻能取+1 和-1 兩個值)時的特殊形式(i.e., Gradient Boosting + Exponential Loss + Binary base classifier),這裡基分類器可以為任何二分類器,如決策樹、SVM、神經網絡等。當然,西瓜書作者在第 190 頁的閱讀材料中提到,這僅是源“統計視角”的一種推導而已,但這派理論産生的推論并不能解釋某些現象,是以這可能僅是一個與 AdaBoost 相似的學習過程而非 AdaBoost 本身。

當 AdaBoost 的基分類器為二分類決策樹時,也可以稱為提升樹,

“對二類分類問題,提升樹算法隻需将 AdaBoost 算法 8.1 中的基本分類器限制為二類分類樹即可,可以說這時的

提升樹是 AdaBoost 算法的特殊情況”。但這裡與 GBDT 不一樣,因為

AdaBoost 限定了基分類器為二分類(實際上也可以做回歸任務),并不像 GBDT 裡那樣,每輪疊代與殘差(負梯度)拟合;而且已經提到,GBDT 一般特指 Gradient Boosting 與 CART 回歸樹的結合。

XGBoost 是 GBDT 的一個軟體包,類似于 LIBSVM 是 SVM 的一個軟體包。XGBoost在實作 GBDT 時進行了一些細節上的改進和擴充。

各種概念之間的包含關系如下圖所示:

以上僅為個人的初步了解,可能有誤,勿被誤導_

參考材料:

[1] 周志華《機器學習》

[2] 李航《統計學習方法》

[3] 邱錫鵬《神經網絡與深度學習》

[4] Adaboost 算法

[5] 一文看懂內建學習（詳解 bagging、boosting 以及他們的 4 點差別）

[6] 機器學習數學原理（8）——霍夫丁不等式

Talk is cheap. Show me the code

\(h_i=+1\)	\(h_i=-1\)
\(h_j=+1\)	a	c
\(h_j=-1\)	b	d

機器學習-內建學習