王妮梅連續搞砸了媽媽介紹的40個男生，要麼不約要麼約完再無聯繫，她媽媽心急如焚又給她找了20個男生。王妮梅瘋了，因為她失敗了這麼多次，已經不再相信自己對男生喜好的判斷了。這時她找來閨蜜劉舒，想讓劉舒幫她捋一捋，告訴她這20個男生哪個喜歡應該去約哪個討厭應該不約？
王妮梅
劉舒，能幫我捋一捋這 20 個男生哪個喜歡應該去約哪個討厭應該不約嗎？
劉舒
你瘋了嗎？這太難了吧，起碼你得給我你對男生的一些判斷標準吧。
劉舒也瘋了，覺得這也太難了，起碼讓我知道王妮梅你對男生的一些判斷標準吧。王妮梅把之前失敗的 40 個男生信息給她，也告訴了她之前對每個男生做出的「約或不約」的判斷。王妮梅這就是將樣本 (男生) 打上標籤 (約/不約)，給劉舒參考。
劉舒看完所有信息之後大概知道了王妮梅對男生的喜好標準，然後對這20個男生設計了一系列的問題，比如「X 是否有大男子主義？」，「X 是否不接你的電話」等等。問完之後劉舒說應該約 X。劉舒 (柳樹) 是判斷王妮梅的男生喜好的一棵決策樹 (decision tree)。
劉舒只是個人，所以她並不總能很好地概括王妮梅的喜好 (過擬合)。為了獲得更準確的建議，王妮梅去詢問一堆朋友，結果他們中的大多數人認為自己應該約 X。這些朋友叫宋舒 (松樹)、楊舒 (楊樹) 和佰舒 (柏樹)，他們組成了判斷王妮梅的男生喜好的一片森林 (forest)。
現在王妮梅不想讓她的每個朋友都做同樣的事情，給你一樣的答案，所以王妮梅首先給每個人略有不同的數據。畢竟，王妮梅也並不完全確定自己的喜好：
所以，王妮梅決定給宋舒、楊舒和佰舒的數據不要和給劉舒的數據一樣，她在給他們的數據上隨機加一些輕微的幹擾項。王妮梅不會改變自己的最終喜好，只會加一些「很喜歡」、「一般喜歡」、「很討厭」之類的感情色彩。這時候王妮梅給每個朋友是原始數據的自助採樣 (bootstrapped) 版本。通常這種機制，王妮梅希望朋友能給她一些相互獨立的推薦，劉舒覺得你喜歡 X 和 Z，宋舒覺得你喜歡 X 和 Y，而楊舒覺得你討厭所有人。他們之間這些錯誤可以在多數投票時可以相互抵消。現在他們組成了判斷王妮梅的男生喜好的一片隨機森林 (random forest)。
雖然王妮梅喜歡 X 和 Y，但並不是因為他們都是基金經理，也許她喜歡這兩個男生有其他原因。因此，王妮梅不希望她的朋友們都根據「是否賺錢多」而提出建議。王妮梅只允許朋友們問一小部分隨機的問題，比如劉舒不能問「是否賺錢多」，柏舒不能問「是否熱愛小動物」等等。以前王妮梅在數據層面注入隨機性 (通過稍微擾亂自己的男生喜好)，現在她在問題層面注入隨機性 (讓她的朋友在不同的時間提出不同的問題)。現在他們組成了判斷王妮梅的男生喜好的一片更為隨機的隨機森林 (random forest)。
最終，王妮梅拿到所有人對這 20 個男生的推薦，再根據自己對這些朋友的信任度和品位在他們的推薦上加個權重。信任劉舒多一些，就多注重她的推薦，信任楊舒少一些，就少注重他的推薦。這個最終結合類似於 boosting。
上貼的裝袋法 (bagging) 和提升法 (boosting) 的兩種結合 (aggregate) 方法，但是結合的模型或假想都是抽象的 h，本帖將 h 具體化，來探討這兩種方法配上樹模型之後的結合模型，bagging 對應的隨機森林和 boosting 對應的提升樹。
第一章 - 前戲王
1.1 偏差和方差
1.2 分類回歸樹
1.3 損失函數和代價函數
1.4 加法模型和前向分布算法
第二章 - 隨機森林
2.1 隨機來源
2.2 包外估計
2.3 特徵選擇
第三章 - 提升樹
3.1 提升分類樹
3.2 提升回歸樹
3.3 梯度提升分類樹
總結和下帖預告
給定一個模型，它做回歸或分類預測是一定會有誤差的，誤差來源有三個：
對 N 套訓練集得到的 N 個模型求均值得到一個平均模型，它與真實模型之間的差距叫做偏差 (bias)
用 N 套訓練集得到的 N 個模型本身也各不相同，它們的變動水平叫做方差 (variance)
一些不可消除的因素造成的誤差是噪聲 (noise)
更多關於偏差和方差的細節可見模型的評估和選擇一貼，簡單來講
用決策樹當模型，那麼樹的深度越大葉子越多，模型複雜度也就越高。因此決策樹樁 (decision stump) 最簡單，偏差大方差小，而長成的樹 (fully-grown tree) 最複雜，偏差小方差大。一張圖勝過千句話：
註：小節 2.1 會用到
分類回歸樹 (classification and regression tree, CART) 既可以用於創建分類樹 (classification tree)，也可以用於創建回歸樹 (regression Tree)。CART 的主要特點有：
特徵選擇：根據 CART 要做回歸還是分類任務，對於
二叉樹：在內節點都是對特徵屬性進行二分 (binary split)。根據特徵屬性是連續類型還是離散類型，對於
{ [好，一般]，[壞] }
{ [好，壞]， [一般] }
{ [好]， [一般，壞] }
需要分別計算按照上述三個在二分序列做分叉時的基尼指數，然後選取產生最小的基尼指數的二分序列做該特徵的分叉二值序列參與回歸樹。因此，CART 不適用於離散特徵有多個取值的場景。
停止條件：根據特徵屬性是連續類型還是離散類型，對於
連續類型特徵：當某個分支裡所有樣例都分到一邊
離散類型特徵：
當某個分支裡所有樣例都分到一邊
當某個分支上特徵已經用完了
對「停止條件」這條還想加點說明：根據離散特徵分支劃分子樹時，子樹中不應再包含該特徵。比如用特徵「相貌」來劃分成左子樹 (相貌=醜) 和右子樹 (相貌=美)，那麼無論在哪顆子樹再往下走，再按特徵「相貌」劃分完全時多餘的，因為上面早已用「相貌」劃分好；而根據連續特徵分支時，各分支下的子樹必須依舊包含該特徵 (因為該連續特徵再接下來的樹分支過程中可能依舊起著決定性作用)。
通常先讓 CART 長成一棵完整的樹 (fully-grown tree)，之後為了避免過擬合，再後修剪 (post-pruning) 樹，具體用到的方法見決策樹一貼。
下面兩圖分別畫出分類樹和回歸樹的一個例子：
第二、三章要講隨機森林和提升樹，下面兩圖畫出分別由分類樹林或回歸樹林的一個例子：
註：在第二、三章講的隨機森林和提升樹用的原材料都是 CART
損失函數 (loss function) 是用來估量在一個樣本點上模型的預測值 h(x) 與真實值 y 的不一致程度。它是一個非負實值函數，通常使用 L(y, h(x)) 來表示。
損失函數可由 y 的類型來分類，而第三章提升樹的梯度提升法在高層面上講是相同的，不同的是用的不一樣損失函數。
如果 y 是離散型變量 (對應著提升分類樹 y 和 sign(h) 取 -1 和 1)
如果 y 是連續性變量 (對應著提升回歸樹 y 和 h 取任意實數)
下表列出了每個損失函數的具體表達式：
當 y 是離散性變量時對應的問題都是分類問題
當 y 是連續性變量時對應的問題都是回歸問題
代價函數 (cost function)就是所有樣本點上的損失函數的加總。代價函數越小，模型的魯棒性 (robustness) 就越好。
註：小節 3.1 和 3.2 會用到
加法模型 (additive model) 是由一系列的基函數 (base function) 線性組成，表示如下
其中
h(x; at)是基函數
at 是基函數的參數
wt 是基函數的係數 (權重)
在給定訓練數據 (x(i), y(i)) 及損失函數 L(y, H(x)) 的條件下，學習加法模型 H(x) 可轉換成下面損失函數最小化問題
通常一次性優化解出 wt 和 at 是很複雜的，我們現在思路是如果從 t 等於 1 到 T，每一步只學習一個基函數和其係數，逐步逼近上面的函數式，從而簡化了優化的複雜度。具體優化步驟如下：
上面的算法也稱為前向分布 (forward stage-wise) 算法。
這樣，前向分布算法將同時求解從 t 等於 1 到 T 所有參數 wt 和 at 的優化問題簡化為逐步求解各個 wt 和 at 的優化問題。大家仔細回顧一下上貼集成學習前傳講的 adaBoost 算法裡面也是逐步確定權重的，和前向分布算法的步驟很像，兩者有什麼聯繫嗎？
註：整個第三章會用到
隨機森林 (random forest, RF) 是用隨機的方式建立一個森林。為什麼叫森林呢？因為它是由許多決策樹組成的。為什麼叫隨機呢？下節告訴你。
數據集是二維的，每一行是一個樣例 (instance)，除最後一列的每一列是一個特徵 (features)，最後一列是標記 (label)，如下圖所示：
根據數據的二維結構，生成隨機數據的辦法有兩個：
因此隨機森林有兩種常見形式，第一種是只做行採樣，第二種是做行採樣和列採樣。第二種森林裡面的樹更加隨機，因此在實踐中用的也更多。這二種隨機形式如下圖。
第一種：沒有在特徵上隨機採樣
第二種：從 9 個特徵隨機取 3 個
隨機選出數據和特徵之後，使用完全分裂的方式建立出決策樹。一般很多的決策樹算法都一個重要的步驟 - 剪枝，但是在隨機森林不需要做。由於之前的兩種隨機採樣的過程保證了隨機性，只要森林裡面的樹夠多，所以就算不剪枝，也不會出現過擬合。
在生成森林之後，當有一個新的輸入樣本進入的時候，就讓森林中的每一棵決策樹分別進行一下判斷，對於
由於在數據上、特徵上都注入隨機的成分，因此可以認為隨機森林中的每一棵決策樹之間是相互獨立的。假設森林有 M 棵小樹
M 棵樹的平均誤差等於每個小樹和真實樹之間誤差的平方再平均
森林的平均誤差等於森林和真實樹之間誤差的平方
上式倒數第三步因為小樹之間相互獨立，因此它們之間誤差的協方差等於零。由上面證明可看出隨機森林通過均勻結合的方式可以降低誤差 (由上貼集成學習前傳的 1.3 小節可知降低誤差這一部分都是方差而不是偏差)，因而對每個子模型 (即，決策樹) 可以選複雜的高方差低偏差 (即，完全長成的樹)。這樣一來，每棵小樹的缺點是方差高，優點是偏差低；而森林將所有小樹融合起來，降低了整體的方差，也沒有增高偏差。此外，隨機森林算法從 bagging 過程中可以分配到不同的計算機中進行計算，每臺計算機可以獨立學習一棵樹，不同的樹之間沒有任何依賴關係。這使得隨機森林算法很容易實現並行化。
對一個樣本數量為 n 的初始數據集自助採樣 (bagging)，如果採樣集的樣本數量也為 n，那麼沒有被選到的樣本大概佔 (1 – 1/n)n，當 n 很大時，有下列極限公式
因此每次做這樣一次自助採樣，初始數據集裡面只有 63.2% 的數據被選中當訓練數據，剩下 36.8% 沒被選中的可以自動作為驗證數據。這些驗證數據可對隨機森林的泛化能力做包外 (out-of-bag, OOB) 估計。
假設有 n 個數據，森林裡面有 T 棵樹，下圖列出每個數據 (x(i), y(i)) 出現在不同的樹 ht 裡的一種可能情況。
其中「勾勾」表示該數據出現在用來訓練某一棵樹的數據集中，「叉叉」表示該數據沒有出現在用來訓練某一棵樹的數據集中。比如
(x(1), y(1)) 用來訓練 h1, ht 和 hT-1
(x(2), y(2)) 用來訓練 h2, ht 和 hT
(x(n), y(n)) 用來訓練 h1, h2 和 h3
那些沒有用來當訓練集的數據可以自動歸為測試集。需要注意的是
這些測試集不需要測試每課樹，因為即使單棵樹測試出來的性能很差，並不能說明均勻結合後的森林的性能很差
測試集裡某數據只能測試這個數據沒有用於訓練的樹上，比如 (x(1), y(1)) 訓練了 h1, ht 和 hT-1，那麼它只能測試 h2 和 hT
上述過程總結與下圖
定義第 i 個數據對應的測試樹集為 G(i)，那麼用所有 OOB 數據計算出來的測試誤差為
其中
e(∙) 是誤差函數
G 是整個測試樹集
G(i) 是第 i 個測試樹集
|G(i)| 是集合的大小
Gj(i) 是第 i 個測試樹集裡第 j 棵樹
特徵選擇 (feature selection)，其目的主要是使用程序來自動選擇需要的特徵，而將冗餘的、不相關的特徵忽略掉。對於線性模型，特徵選擇很簡單。在正規化線性回歸一帖中講過，擬合出 y = wTx 裡面的參數 w，根據每個參數的絕對值大小 (絕對值越大，變動一點 x 對 y 的影響越大) 來對其重要性排序，選出前 d 個作為最重要的 d 個特徵。因此對線性模型，根據重要性 (參數的絕對值) 來選擇特徵 (回憶一下嶺回歸和套索回歸)
重要性(j) = |wj|
但是對非線性模型，特徵選擇就沒有這麼簡單了。幸運的是，隨機森林雖然是非線性模型，但是其特有的機制可以很容易做到初步的特徵選擇。隨機森林的特徵選擇的核心思想是「如果特徵 j 是重要特徵，那麼加入一些隨機噪聲模型性能會下降」。現在問題就在如何加隨機噪聲了。直接在原數據上加一些均值分布或正態分布的數據好嗎？不好，因為這樣做會改變原有特徵的數據分布。因此我們的做法是把所有數據在特徵 j 上的值重新隨機排列，整個過程的專業叫法是置換檢驗 (permutation test)。這樣做的好處是可以保證隨機打亂 (幹擾) 的數據分布和原數據接近一致。
下圖給出了在特徵「性格」上做隨機排列後的數據樣貌，隨機排列將「好壞壞好壞壞好好」排成「壞壞好好好壞壞好」。
在置換檢驗後，特徵 j 的重要性可看成是森林「在原數據的性能」和「在特徵 j 數據置換後的性能」的差距，有
重要性(j) = |性能(D) – 性能(Dp)|
其中
D 是原有採樣數據
Dp 是置換之後的數據
這樣做太消耗時間，還要重新再用 Dp 訓練一遍隨機森林。隨機森林的 OOB 數據可以簡化以上步驟：
重要性(j) = |性能(D) – 性能(Dp)|
= |誤差(DOOB) – 誤差(DpOOB)|
其中
DOOB 是 OOB 數據
DpOOB 是 OOB 置換之後的數據
這樣看來，我們就不用重新訓練模型了。訓練好森林之後，對每個樹 ht 對應的 OOB 數據，在特徵 j 上隨機打亂 (注意現在隨機打亂的是 OOB 數據而不是全部數據)，分別計算打亂前和打亂後的誤差，最後在森林層面上再求一個平均，公式如下：
若給特徵 j 隨機加入噪聲之後，OOB 的誤差率大幅度增高，則重要性(j)也會大幅度增大，因此它特徵比較重要而應該選擇。
提升樹 (boosted tree) 主要在回歸分類樹上提升性能，3.1 節從上貼的 adaBoost 開始引出提升分類樹；3.2 節從一個簡單例子開始引出提升回歸樹；3.3 節則從提升回歸樹的算法發現梯度提升的規律，進而一般化為梯度提升樹。這三節都回用到 1.4 節介紹的加法模型和前向分布算法。
回顧集成學習前傳一帖小節 3.3 講的逐步提升(adaBoost) 的算法：
在集成學習前傳一帖中，上面算法推出的核心思想是「在第 t+1 輪生成一個樹樁，使得它和第 t 輪的樹樁儘量獨立」。在本小節，我們根據之前介紹的加法模型和前向分布算法來推出上貼的 adaBoost 算法，在這裡就成為提升樹樁算法
提升樹樁模型是由決策樹樁組成的加法模型，損失函數用的是指數損失函數，總結在下表：
定義
H0(x) = 0
Ht(x) = Ht-1(x) + wtht(x)
因此
H(x) = HT(x)
在前向分布算法中，對於求出的前 t-1 個二分類器，我們認為是已知的了，不要去改變它們，而目標是放在之後的分類器建立上。假設經過 t-1 輪迭代的前向分布算法已經得到 Ht-1(x)，在第 t 輪最小化損失函數 L(w,h) 得到 wt 和 ht(x)。這裡我們把函數 h 當做損失函數中的一個參數。
其中 u(i)t 不依賴 wt 和 ht，因此與最小化無關，但是它依賴 Ht-1(x)，因此隨著每一輪迭代而改變。現在的任務就是就最優解 wt 和 ht 而使得上式最小。
第一步：求 ht
在而分類器是決策樹樁的前提下，特徵個數是有限的，因此相對應的決策樹樁個數也是有限的，你計算出所有決策樹樁的誤差率，然後找一個最小的作為 h。原因是 w 大於零，要是 exp(-ywh) 最小，那麼 y 和 h 要同號的最多，因此要找一個分類誤差率最小的 h。
第二步：求 wt
用第一步求出的 h 帶入目標函數中，得
將上式求導設成 0 得到
這和上貼 adaBoost 計算出來的 wt 完全一致。最後來看每一輪樣本權值 u(i)t+1 更新，有
當 t = 0 時，H0(x) = 0，因為每個u(i)1 都等於 1，規範化之後等於 1/N。這和上貼 adaBoost 計算出來的 u(i)t+1 也幾乎一致，就相差規範化的因子，因而兩者也是等價的。
用加法模型和前向分布算法的提升樹樁算法的流程如下：
在講提升回歸樹前，先做一個遊戲。假設你有 n 個數據 (x1, y1), (x2, y2),…, (xn, yn)，任務是擬合一個函數來最小化平方損失。現在你朋友給你一個函數 H，你發現這個函數擬合的不錯但不完美，在每個點上還是有誤差，比如 H(x1) = 0.8 但是 y1 = 0.9；H(x2) = 1.4 但是 y2 = 1.3。現在你朋友讓你改進這個模型，但是必須遵守以下兩點規則：
不能改變 H 裡面任何項或任何參數
只能在 H 上加額外模型 h (新的預測是 H+h)
最簡單的模型改進做法是直接求出 h
當然你不能把函數 h 在每個點都完美擬合出來，但是在數據 (x1, h1), (x2, h2),…, (xn, hn) 進行新的一輪迴歸，你可以得到更好的模型 H+h。其中 hi = yi – H(xi) 叫做殘差，它們是 H 在第一輪表現不好的地方，也就是說 h 是現有模型 H 的缺點。如果 H+h 的結果還不滿意，再進行一輪迴歸。既然是回歸，當然也可以用回歸樹來做進而一步步提升模型。
提升回歸樹模型是由回歸樹組成的加法模型，損失函數用的是 L2 損失函數，總結在下表：
提升回歸樹算法的流程如下：
回到上節提升回歸樹的問題，令代價函數為 J，它是對所有數據點上的損失函數的總和，我們有
我們發現每輪擬合的殘差恰恰就是其損失函數的負梯度，根據上節最後的算法，在第 t 輪更新回歸樹
上式最後一步不就是梯度下降 (gradient descent) 嗎？回憶一下線性回歸裡面梯度下降的公式 wt = wt-1 – a∙∂J/∂wt-1。
根據在提升回歸樹擬合殘差來更新模型的過程，又因為殘差等於負梯度，下表類比出來更新模型的過程可以用梯度下降來描述：
因此我們使用梯度下降法來更新模型，而梯度的概念遠比殘差的概念更廣義，因此讓我們現在忘掉殘差而接受梯度吧，而其對應的提升樹叫做梯度提升樹 (gradient boosted tree, GBT)。除了 L2 損失函數，它可以處理任何損失函數。對於回歸問題為什麼還要選其他損失函數呢，L2 損失函數不夠嗎？請看下表：
注意上表 y 等於 5 時是一個異常點，而用 L2 算出的損失是 5.445，比起在其他點的損失太過於大了，因此 L2 作為損失函數會放大異常點而降低模型的魯棒性。再看 L1 和 Huber 下算出的損失就友好很多了，因此在很多提升樹模型中，我們會選 L1 和 Huber 損失函數，而這時要套用上節提升回歸樹的算法，只用計算 L1 和 Huber 損失函數的梯度即可，如下表：
對梯度提升回歸樹算法的流程如下：
最後總結：其實提升更像是一種思想，梯度提升是一種提升的方法，它的核心理念是，每一次建立模型是在之前建立模型損失函數的梯度下降方向。注意：本節沒有講如何選擇一個適當的參數 wt，也沒有講梯度提升分類樹。
隨機森林 (RF) 和梯度提升樹 (GBT) 都是在樹上做集成學習，這兩種方法都是 Kaggle 中做集成比選用的方法：
隨機森林的 bagging 本身就用於減小方差，因此森林裡面的樹可以是高方差低偏差而不用剪枝的強樹。此外隨機森林容易並行處理，而且自帶袋外數據作驗證，還可以做特徵選擇。提升樹是將一堆高偏差低方差的弱樹結合起來，按順序的訓練出一顆顆樹，每棵樹通過提升梯度來改進前面訓練的結果。其中極度梯度提升 (extreme gradient boosting, XGBoost) 的方法是梯度提升的極品，速度快，效果好，功能多，是 Kaggle 數據科學競賽獲獎選手最常用的方法之一。
沒有模型是完美的。使用簡單模型 (決策樹) 或複雜模型 (隨機森林、提升樹) 是在模型預測能力和可解釋性兩者做權衡。這些複雜模型通常被認為是黑盒子，因為隨機森林是隨機的生成的決策樹，而不是由明確的預測規則領導，或梯度提升樹後面的數學概念太過複雜，很難想大眾解釋清楚。有時候不可解釋或難於解釋的預測可能會在醫療領域使用時帶來倫理問題。儘管如此，隨機森林和梯度提升樹還是被廣泛使用，因為它們易於實施，特別是當結果的準確性比可解釋性更重要的時候。
下一貼充滿著真實數據 (來自美國借貸俱樂部，Lending Club)，實際問題和編程代碼的一貼。學而不編則罔，編而不學則殆，希望下一貼用代碼來複習決策樹和集成學習的內容，包括構建樹和樹樁，用 adaBoost 來提高樹的分類性能。Stay Tuned!