① 依序閱讀：每節先讀說明；遇到互動元件時，先預測結果，再操作驗證。 ② 對照來源：章節旁標示課本章節與講義主題，正文保留公式、條件與算例；計算細節、完整實作與證明預設收合，可按需要展開。來源標記可查原教材。 ③ 檢查理解：答錯時先看回饋，再回到相關說明；標為延伸的內容可留待第二輪。 ④ 最後翻關鍵詞彙卡自測術語，並用 重點速查與來源查閱。標「ESL 進階」的節是課堂沒細講的延伸，第一輪可略過。
教科書：An Introduction to Statistical Learning with Applications in Python（ISLP）；
進階參考：The Elements of Statistical Learning（ESL）。章節旁的來源標記可點到本頁書目。
前面幾章的模型都在擬合一個式子：線性迴歸擬合一條線、樣條擬合一條彎的曲線、 邏輯斯迴歸擬合一個機率。這一章換一個完全不同的想法——直接把特徵空間切成方塊，各區給出固定預測， 每個方塊裡的所有點都給同一個預測值。
ISLP §8.1 的例子是棒球員薪水（Hitters）：用 Years（打了幾年）
和 Hits（去年幾支安打）預測 log 薪水。整棵樹只有兩刀，就把球員切成三塊：
三塊的預測值是各塊訓練資料 log 薪水的平均，換回薪水尺度是 $e^{5.107}$、$e^{5.999}$、$e^{6.740}$ 千美元，也就是約 16.5 萬、40.3 萬、84.5 萬（指數轉回來是幾何平均的尺度，不等於平均薪水）。整個模型可以用一句話講完： 資淺的便宜；資深的看安打數。這種「一句話講得完」的能力，是樹最大的賣點。
Years < 4.5）的節點。樹的整體形狀就是一個階梯函數：
$$f(X) = \sum_{m=1}^{M} c_m \cdot \mathbf{1}(X \in R_m)$$其中 $M$ 是葉子數、$c_m$ 是第 $m$ 片葉的預測值；$\mathbf{1}(X\in R_m)$ 在 $X$ 落在 $R_m$ 時是 1，否則是 0。
對照線性迴歸的 $f(X) = \beta_0 + \sum_j X_j \beta_j$——一個是連續的斜面， 一個是一格一格的台階。哪個對？看真實關係長什麼樣，這是「樹 vs 線性模型」一節的主題。
樹的長處和它最大的弱點，都在下一節「為什麼要種一片森林」說明。
一棵迴歸樹對落在同一個葉節點裡的兩個觀測值，會給出什麼預測？
Hitters 那棵樹只切兩刀，卻已經做到線性迴歸要額外設計才做得到的事：Hits 只在 Years ≥ 4.5 的那一支才有作用。這是樹自己長出來的交互作用。樹還有幾個長處：
| 線性迴歸 | 決策樹 | |
|---|---|---|
| 模型長相 | 一個斜面（連續、光滑） | 一堆方塊（階梯、有稜角） |
| 外插能力 | 有（可以往定義域外推） | 沒有（葉的值是常數，出界就給邊界值） |
| 類別變數 | 要做虛擬變數編碼 | 天生就會處理（把水準分兩堆） |
| 變數尺度 | 要小心（正則化時必須標準化） | 完全不受影響（只看大小順序） |
| 交互作用 | 要自己乘出來 | 自動有（連續兩刀就是一個交互作用） |
| 最大弱點 | 真實關係非線性時失手 | 不穩定：資料動一點，樹就長成另一棵 |
代價是不穩定。樹的每一刀都建立在上一刀之上，資料稍微變一點，根節點換了一個切點或變數，下面整棵樹就跟著全部改寫。把訓練資料隨機切成兩半各長一棵，兩棵可能完全不像。這就是變異很大。另外，單棵樹的預測準確度通常比不上最好的方法；葉子是常數，也不會外插。
解法是不要只相信一棵樹，讓很多棵一起決定。為什麼「一群不太準的模型」合起來會變準？先看一枚硬幣。
假設一枚硬幣出現正面的機率是 51%，只比公平硬幣多 1%。擲一次，你幾乎感覺不到這個優勢。擲一千次，正面過半的機率就到了約四分之三；擲一萬次，接近 98%。
把「正面」換成「答對」，就是集成的直覺：M 個分類器各投一票，以二元分類、M 為奇數為例（這裡的 M 是分類器個數，和上一節的葉子數無關），如果它們彼此獨立、每個答對的機率都是 $p$，那麼多數決答對的機率是二項分佈的尾巴：
$$P(\text{多數決答對})=\sum_{k>M/2}\binom Mk p^k(1-p)^{M-k}.$$$p>0.5$ 時，M 愈大愈接近 1；$p<0.5$ 時方向反過來，愈投愈錯，投票只會放大原本的傾向。元件下半那條點線是另一個極端：M 個分類器一模一樣時，投一千票和投一票沒有差別。所以獨立是整個論證的前提。講義說的「1000 個約 75%」和精確值的小差別，在下面的收合裡說明。
為什麼 M 一大就穩贏。令 $S_M$ 為 M 票中答對的票數，$S_M\sim\mathrm{Bin}(M,p)$，平均 $Mp$、標準差 $\sqrt{Mp(1-p)}$。平均隨 M 線性成長，雜訊只隨 $\sqrt M$ 成長。用常態近似，
$$P\!\left(S_M>\tfrac M2\right)\approx\Phi\!\left(\sqrt M\cdot\frac{p-0.5}{\sqrt{p(1-p)}}\right),$$$\Phi$ 是標準常態的累積分佈函數。$p=0.51$ 時，$M=1000$ 代入得 $\Phi(0.63)\approx73.6\%$，$M=10000$ 得 $\Phi(2.0)\approx97.7\%$。關鍵是前面的 $\sqrt M$：只要 $p>0.5$，括號裡的值就會往無限大跑。這就是 Condorcet 陪審團定理：獨立的陪審員各自比瞎猜好一點，人數愈多，多數決愈可能是對的。
講義的「約 75%」。講義說 1000 個 51% 的分類器投票可以到約 75%。精確計算時，偶數 M 會碰到平手，答案看平手怎麼算：嚴格過半是 72.6%，平手時擲硬幣決定是 73.6%，平手也算答對則是 74.7%。最後一種只是事件機率，實際上不可能「平手時自動答對」。上面的元件只用奇數 M 避開平手，M = 1001 得 73.7%。所以 75% 是概數，大約四分之三就對了。
兩個常見誤會。有些硬幣範例會寫「bagging 創造了獨立性」，又說只要 i.i.d. 錯誤率就指數下降。數學沒錯，錯在前提：bagging 的樹來自同一份資料，彼此高度相關（見下方「真實的樹不獨立」）。範例也把 random forest 說成「彙總成千上萬個弱分類器」，但 random forest 的樹通常長很深、各自不弱；用很多棵很弱的小樹的是 boosting。
同一份資料長出來的樹，錯的地方常常一樣，彼此相關。這時平均只能壓掉樹與樹之間不相關的那一部分變異；大家一起動的那一部分，種再多棵樹也壓不掉。硬幣的例子是完全不相關的理想狀況，真實的集成方法都會碰到這個限制。
迴歸的情況可以算得很清楚：固定一個 $x$，設每棵樹的預測變異都是 $\sigma^2$、兩兩相關係數都是 $\rho$，B 棵樹平均之後
$$\operatorname{Var}\!\left(\frac1B\sum_{b=1}^B\hat f^{b}(x)\right)=\rho\sigma^2+\frac{1-\rho}{B}\sigma^2.$$第二項隨 B 變大而消失，第一項 $\rho\sigma^2$ 不管種幾棵樹都在。硬幣的例子是 $\rho=0$ 的理想狀況。
這條公式只講平均預測的變異，條件是固定 $x$、每棵樹的變異都是 $\sigma^2$、兩兩相關都是 $\rho$；推導見 random forest 一節的證明。它不能直接換算成分類的投票正確率：只知道兩兩相關係數，還不足以決定多數決答對的機率。這裡的變異與相關，指的是「換一份訓練資料、重新訓練」造成的變動。給定訓練資料以後，各棵樹的 bootstrap 抽樣與隨機種子可以互相獨立；可是訓練資料一換，所有樹會一起往同一個方向動，這個共同的變動就是 $\rho\sigma^2$。
後面幾節的集成方法，都可以用這兩個想法定位：獨立的投票會放大小優勢，樹與樹的相關會限制平均的效果。
| 方法 | 怎麼組合 | 主要對付 | 對應的節 |
|---|---|---|---|
| Bagging | bootstrap 重抽 B 份，各長一棵深樹再平均（或投票） | 樹與樹之間不相關的那部分變異 | Bagging 與 OOB |
| Random forest | 同 bagging，但每個節點都重新抽 m 個變數，只准從中挑（不是每棵樹固定一組） | 降低樹與樹之間的相關（代價是單棵樹可能變弱） | Random Forest |
| Boosting | 一棵接一棵長小樹，每棵修正前面還沒解釋的部分 | 主要是偏差；它不是在平均同分佈的樹 | Boosting |
| BART | 從上一輪的樹微調，跑馬可夫鏈蒙地卡羅（MCMC）再平均 | 兼有隨機化與修正殘差 | Stacking 與 BART |
講義的結論是：random forest 與梯度提升樹（GBDT）是大多數表格資料任務應該最先試的模型，而且幾乎不需要前處理，很適合快速做出第一版。代價是失去單棵樹「畫得出來、一句話講完」的解釋力。在那之前，先把單棵樹怎麼長、怎麼剪弄清楚。
方塊要怎麼切？理想上我們想找到讓下面這個 RSS 最小的一組方塊 $R_1, \dots, R_J$：
$$\sum_{j=1}^{J} \sum_{i \in R_j} \left(y_i - \hat y_{R_j}\right)^2$$其中 $\hat y_{R_j}$ 是第 $j$ 塊內訓練資料 $y$ 的平均。問題是——所有可能的切法多到算不完。所以實務上用一個貪婪的近似： 遞迴二元分裂（recursive binary splitting）。
做法只有一句話：每一步，在所有變數 $X_j$ 與所有切點 $s$ 裡面， 選讓 RSS 掉最多的那一刀。切完之後，對切出來的兩塊各自再問同樣的問題，一直遞迴下去。 數學上就是找 $(j, s)$ 最小化
$$\sum_{i:\, x_i \in R_1(j,s)} \left(y_i - \hat y_{R_1}\right)^2 + \sum_{i:\, x_i \in R_2(j,s)} \left(y_i - \hat y_{R_2}\right)^2$$其中 $R_1(j,s) = \{X \mid X_j < s\}$、$R_2(j,s) = \{X \mid X_j \ge s\}$。一直切到某個停止條件為止，例如每一塊都不超過 5 筆觀測。
方塊理論上可以是任何形狀，只用軸平行的長方形，是為了好算，也好解釋。
樹的交互作用是「走到這一支，下一刀才切那個變數」。這個機制很方便，但要的刀數比想像多。
如果真實關係是 $Y=X_1X_2$，最粗略的近似是四個象限各給一個正負號，這需要深度 2 的樹：根節點一刀，左右兩邊各再一刀，共 3 次分裂、4 片葉子。每條從根到葉的路徑只用兩刀，但整棵樹是三刀。想把乘積曲面描得更細，就得再多切很多刀。
相對地，GAM 每個變數各配一條曲線再加起來，不會自己長出交互作用，要用就得自己寫進 $f_{12}(X_1,X_2)$。樹會自己找，但找得到與否要看資料和搜尋方式。
玩過上面的元件之後有三件事應該很明顯：
連續變數先排序，只需考慮相鄰相異數值之間的分割；相同數值不能分到門檻值兩側。若有 $u$ 個相異值，最多有 $u-1$ 個候選門檻值。名目變數有 $q$ 個水準時，則要選非空子集合 $A$，以 $x_j\in A$ 或 $x_j\notin A$ 分開；不計左右互換，共有 $2^{q-1}-1$ 種，例如 4 個水準就有 7 種。只比較「一個水準對其他全部」（one-versus-rest）只看 $q$ 種，會漏掉像 $\{A,B\}$ 對 $\{C,D\}$ 這樣的分法。
平方損失的迴歸樹可先按每個水準的平均反應排序，再比較 $q-1$ 個相鄰切點。排序使用當前訓練節點的反應，不能先用全資料的目標幫驗證資料編碼。二元分類依各水準 $Y=1$ 的比例排序，用 Gini 或交叉熵時同樣保證找到最佳分割；多類別問題沒有這個捷徑，也不可直接把類別編號平均後套用。水準很多時，用訓練資料的平均排序容易過度擬合。scikit-learn 的一般決策樹只接收數值欄，Lab 先用 ModelSpec 產生設計矩陣再訓練，這和原生的類別子集合分割不是同一個搜尋空間。
ID3 以資訊增益挑類別特徵並做多叉分裂；C4.5 擴充連續特徵與增益比，並具有剪枝與規則表示；C5.0 是後續系統。CART 做二元分裂，可用平方損失處理回歸，也可用 Gini 等準則處理分類。scikit-learn 的一般決策樹採 CART 家族做法，輸入介面對類別特徵的支援需另查，不能由「理論上的樹能分割類別」推成「任何套件都直接接受字串」。
固定一個葉子的資料集合 $R$，$\sum_{i\in R}(y_i-c)^2=\sum_{i\in R}(y_i-\bar y_R)^2+|R|(c-\bar y_R)^2$，故最優常數為平均。將每個類別先縮成帶權重的平均後，類別內的 RSS 是不隨分組改變的常數，剩下的是在一維類別平均上選兩個中心的平方損失問題。給定兩個有序中心，每個類別歸到較近中心的分界在兩中心中點，故存在最佳分割是平均排序的一次切分。這個證明使用平方距離與兩組，不能無條件搬到多類別 impurity。
找第一刀時，演算法實際上比較了多少種可能？（p 個變數、n 筆資料）
講義先刪除缺失 Salary，再取對數。第一個門檻是 Years 4.5：較少經驗者同屬第一葉；其餘人再用 Hits 117.5 分成兩葉。因此 Hits 的作用取決於 Years 所在區域，樹自動表達了交互作用。每葉的值是該葉訓練資料的平均 log Salary。指數轉換之後的尺度，開場已經說明。
本主題的講義來源與延伸閱讀：Hitters 資料說明、迴歸樹的分裂推導、候選分裂門檻、分類樹的分裂推導、樹演算法家族官方說明、ID3 演算法背景、CART 背景。
上一節的過程如果不管它，樹會一直長到每個葉子只剩幾個點。訓練誤差很低， 測試誤差卻可能很高——典型的過度擬合。
直覺的解法是「RSS 下降量小於某個門檻就停」。這個做法有盲點， 而且這個盲點很有教育意義：它太短視。一刀本身看起來沒用， 但切完之後下一刀可能大幅降低 RSS；提早停就永遠看不到那一刀。
直接限制樹的深度或每片葉的最少筆數（sklearn 的 max_depth、min_samples_leaf）也是常見做法，簡單好用，但上限是事先定死的，不看後面還能切出什麼。
講義推薦的做法是先長太大，再剪回來。剪的依據是 成本複雜度剪枝（cost complexity pruning，也叫 weakest link pruning）： 對每個 $\alpha \ge 0$，找讓下式最小的子樹 $T \subset T_0$（$T_0$ 是先長出來的那棵大樹）
$$\sum_{m=1}^{|T|} \sum_{i:\, x_i \in R_m} \left(y_i - \hat y_{R_m}\right)^2 + \alpha |T|$$$|T|$ 是葉子數。左邊是擬合程度，右邊是複雜度的罰款—— 採用第 6 章 lasso 也使用的損失加懲罰形式：一個要小的目標加上一個乘了調整參數的罰項。 $\alpha = 0$ 時罰款是零，最小化的就是訓練誤差，答案是完整的 $T_0$； $\alpha$ 愈大，多留一個葉子愈貴，樹就愈小。
用交叉驗證比較不同複雜度，選好參數後再以完整訓練資料擬合。下方互動可觀察剪枝如何改變樹的大小與誤差。
scikit-learn 的
cost_complexity_pruning_path() 回傳的就是這條序列的斷點。
剩下的問題是 α 該取多少。可以沿用第 5 章的方法：用交叉驗證選。 ISLP 演算法 8.1 把整套流程寫成四步：
下面的教材 lab 採一個較簡化的實作：先用完整外層訓練資料算一次剪枝路徑，
把得到的 ccp_alphas 固定成候選格點，再交給 GridSearchCV。
每個固定 α 的樹仍會在各折訓練部分重新擬合；只有候選格點沒有在每折重建。
上述演算法 8.1 的嚴格版本則連候選路徑都在每折的訓練部分重新建立。
以內部節點 $t$ 為根的子樹記為 $T_t$，$|T_t|$ 是它的葉數，$R(\cdot)$ 是訓練 RSS（分類樹則是對應的不純度）。把 $T_t$ 收成一片葉，損失由 $R(T_t)$ 變成 $R(t)$，葉子由 $|T_t|$ 片變成一片。兩種成本恰好相等的臨界值是
$$\alpha_{\rm eff}(t)=\frac{R(t)-R(T_t)}{|T_t|-1}.$$先在所有內部節點中找最小的非負臨界值，剪掉該弱連結，重新計算剩下的候選值，得到巢狀路徑。相同臨界值的多個分支需一致處理 ties。最後用訓練折中的剪枝路徑與驗證損失挑 $\alpha$。
保留子樹與收成一葉的成本差為 $R(T_t)+\alpha|T_t|-\{R(t)+\alpha\}=R(T_t)-R(t)+\alpha(|T_t|-1)$。令差為 0 即得正文的臨界值；大於此值時收成一葉更便宜。weakest-link 演算法逐次選最先達到這個臨界值的分支，無須列舉所有可能子樹。
巢狀性質。對內部節點 $t$ 令 $d_t=R(t)-R(t_L)-R(t_R)$（$t_L$、$t_R$ 是 $t$ 的左右子節點），代表在 $t$ 多切一刀省下的 RSS。剪枝子樹 $T$ 由它保留的內部節點集合 $I(T)$ 決定，而 $I(T)$ 對祖先封閉（保留一個節點就得保留它的所有祖先）。因為 $R(T)=R(\text{根})-\sum_{t\in I(T)}d_t$、$|T|=1+|I(T)|$，
$$C_\alpha(T)=R(\text{根})+\alpha+\sum_{t\in I(T)}(\alpha-d_t).$$設 $\alpha_1<\alpha_2$，$I_1$、$I_2$ 分別是兩者的最佳解。對祖先封閉的集合取聯集、交集仍然對祖先封閉，所以 $I_1\cup I_2$ 是合法的子樹。$I_1$ 在 $\alpha_1$ 下最佳，比 $I_1\cup I_2$ 不差，得到 $\sum_{t\in I_2\setminus I_1}(\alpha_1-d_t)\ge0$。於是在 $\alpha_2$ 下
$$\sum_{t\in I_2\setminus I_1}(\alpha_2-d_t)\ge(\alpha_2-\alpha_1)\,|I_2\setminus I_1|.$$若 $I_2\setminus I_1$ 不空，右邊大於 0，那麼把這些節點拿掉的 $I_1\cap I_2$ 在 $\alpha_2$ 下嚴格更便宜，和 $I_2$ 最佳矛盾。所以 $I_2\subseteq I_1$：$\alpha$ 變大時，最佳子樹只會變小，不會換到另一支。同一個 $\alpha$ 有多棵並列最佳時，取葉子最少的那棵，路徑就唯一。這裡的「最佳」是在給定的 $T_0$ 之內；$T_0$ 本身是貪婪長出來的，不保證是所有樹裡最好的。
限制「本次 RSS 降幅太小就停止」可能錯過必須先做一個小改善、後續才能得到大改善的結構。成本複雜度剪枝先得到足夠大的 $T_0$，再在其子樹中比較 $RSS(T)+\alpha|T|$。$\alpha$ 是每個葉節點的成本，增大時偏向較少葉；不要把它當成所有葉值的 L2 收縮係數。
Lab 的 cost_complexity_pruning_path 回傳候選 ccp_alphas。用 GridSearchCV 在訓練資料內部選 ccp_alpha，再用該參數重新擬合完整訓練資料，最後再用測試資料評估效能。講義 Hitters 的 132／131 切分與 Lab 具體隨機切分各有來源，不混成同一次結果。
數學講義的 $RSS$ 是總和，而 sklearn 成本採用加權節點不純度，並有樣本數正規化。結構相同的剪枝推導仍適用，但 $\alpha$ 數值尺度不可直接互換。若使用一標準誤規則，選的是在最小 CV 誤差加一個標準誤範圍內較小的樹；不能只因為圖上誤差差不多就宣稱已套用該規則。
以下把上面的臨界值記成 $g(t)=\alpha_{\rm eff}(t)$。假設一棵大樹 $T_0$ 有三個內部節點：根、A、B，A 與 B 各管兩片葉。$R(t)$ 是把節點收成一片葉的 RSS，$R(T_t)$ 是保留它底下子樹的 RSS：
| 節點 | 收成一片葉的 RSS | 保留子樹的 RSS | 子樹葉數 | $g(t)$ |
|---|---|---|---|---|
| A | 16 | 10 | 2 | $(16-10)/(2-1)=6$ |
| B | 22 | 18 | 2 | $(22-18)/(2-1)=4$ |
| 根 | 60 | 28 | 4 | $(60-28)/(4-1)=32/3$ |
最小的是 B，所以 $\alpha_1=4$ 時先剪 B。剪完之後根底下的子樹 RSS 變成 $10+22=32$、葉數 3，根的值要重算：$(60-32)/(3-1)=14$。這時 A 的 6 比較小，$\alpha_2=6$ 剪 A；最後根的子樹 RSS 是 38、葉數 2，$\alpha_3=(60-38)/(2-1)=22$ 剪成只剩根。得到 $T_0\supset T_1\supset T_2\supset T_3$，每個 $\alpha$ 的最佳子樹都在這條路徑上，$\alpha$ 也不是事先設好的格點，而是演算法算出來的斷點。
容易搞混的一點：「最小化 $g(t)$」不是「在某個固定的 $\alpha$ 下，挑讓成本下降最多的那一刀」。各分支的 $|T_t|-1$ 不同，兩件事不等價；$g(t)$ 最小的分支，是 $\alpha$ 由小變大時最早不值得保留的那一支。
「可預測」的意思是：每棵子樹的成本 $R(T)+\alpha|T|$ 都是 $\alpha$ 的一條直線，最佳子樹是這些直線的下包絡，所以只在有限個 $\alpha$ 處換人。例如三棵子樹的成本 $100+6\alpha$、$110+4\alpha$、$130+2\alpha$，最佳子樹只在 $\alpha=5$ 與 $\alpha=10$ 換手。
分類樹長樹時用 Gini 或交叉熵，因為它們對純度比較敏感；剪樹時如果最終目標是預測準確率，ISLP 指出用錯誤率比較好。sklearn 實際怎麼做，見分類樹一節「剪枝路徑與選參數的指標要分開」。
ISLP 圖 8.4 是剪枝前的 Hitters 大樹，除了 Years 與 Hits，還用到 RBI、Putouts、Walks、Runs 等變數；交叉驗證之後只剩 3 片葉，回到開場那棵兩刀的樹。
本主題的講義來源與延伸閱讀：剪枝參數選擇。
Ch08-baggboost-lab-zh.ipynb
為什麼不直接「RSS 下降量小於門檻就停止分裂」，而要先長大再剪？
分類樹跟迴歸樹幾乎一樣：一樣遞迴二元分裂、一樣剪枝。只有兩件事要換。
第一，預測值換成多數類別。落在某個葉子的觀測， 預測為該葉子內訓練資料最常出現的那一類。 但別忘了同時看類別比例——「90% 是 Yes」跟「51% 是 Yes」的可信度完全不同。
第二，RSS 換掉。類別沒有平方誤差可算。最直覺的替代品是 錯誤率（classification error rate）：
$$E = 1 - \max_k \hat p_{mk}$$$\hat p_{mk}$ 是第 $m$ 個節點裡屬於第 $k$ 類的比例，$K$ 是類別數。看起來很合理， 但它不夠敏感，不適合當分裂準則。實務上用另外兩個：
$$G = \sum_{k=1}^{K} \hat p_{mk} (1 - \hat p_{mk}) \qquad\text{（Gini 指數）}$$ $$D = -\sum_{k=1}^{K} \hat p_{mk} \log \hat p_{mk} \qquad\text{（交叉熵 / entropy）}$$兩個都在量節點純度（node purity）：所有 $\hat p_{mk}$ 都靠近 0 或 1 時值很小。 兩者數值上非常接近，實務上選哪個幾乎沒差，而且都是可微的。
評估一刀時，看的是兩個子節點不純度的加權和，權重是各自占父節點觀測的比例 $N_L$、$N_R$：$N_L\,G(R_L)+N_R\,G(R_R)$（交叉熵同理），挑讓它最小的那一刀。
父節點有 70 筆 A、30 筆 B，錯誤率 $E=0.30$、Gini $G=1-0.7^2-0.3^2=0.42$。比較兩種各切成 50 筆的分法：
| 左節點 | 右節點 | 加權錯誤率 | 加權 Gini | 加權交叉熵 | |
|---|---|---|---|---|---|
| 分法一 | 35A／15B | 35A／15B | 0.30 | 0.42 | 0.611 |
| 分法二 | 40A／10B | 30A／20B | 0.30 | 0.40 | 0.587 |
兩種分法裡，兩個子節點的多數類別都還是 A，答錯的筆數一樣是 30，錯誤率完全沒動。可是分法二的左節點明顯比較純，Gini 從 0.42 降到 $\tfrac12(0.32)+\tfrac12(0.48)=0.40$，交叉熵（以 $e$ 為底）從 0.611 降到 0.587。用錯誤率當準則，演算法會覺得兩刀一樣沒用；Gini 與交叉熵看得出分法二比較好。
ISLP 圖 8.6 的 Heart 例子有同一個現象的實例：
未剪枝樹右下角那一刀 RestECG < 1，兩邊的預測都是 Yes——
錯誤率完全沒降，可是右邊那 9 筆全是 Yes、左邊只有 7/11，
純度差很多。這一刀之所以被切，就是因為 Gini 與交叉熵看得到差別。
ISLP 的 Heart 資料有 303 位胸痛病人，反應變數 HD 是血管攝影檢查有沒有心臟病，預測變數有 13 個，包括 Age、Sex、Chol（膽固醇）與其他心肺功能指標。交叉驗證選出的樹有 6 片葉。
有些預測變數是類別型，樹圖上會寫成 Thal:a 或 ChestPain:bc：左分支是該變數取第一個水準（Thal 的 a），或取第二、三個水準（ChestPain 的 b 與 c）；其餘水準走右分支。
ccp_alpha 決定在這條路徑選哪棵樹；
GridSearchCV(scoring='accuracy') 則以驗證正確率挑 α。
所以 Lab 是先依 entropy 建立剪枝路徑，再以 accuracy 選剪枝強度，
並沒有把路徑本身改成以分類錯誤率計算。
Ch08-baggboost-lab-zh.ipynb
本主題的講義來源與延伸閱讀：分類樹的分裂推導、Heart 資料下載、迴歸樹的分裂推導。
因為錯誤率對純度的變化不敏感，常常給出「下降量 0」的假訊號，讓貪婪演算法以為這一刀沒用而不切。
可以從函數形狀比較。兩類的情況下錯誤率是 $\min(\hat p, 1-\hat p)$，這是兩段直線；Gini 是 $2\hat p(1-\hat p)$、交叉熵是 $-\hat p \log \hat p - (1-\hat p)\log(1-\hat p)$，兩者都嚴格凹。而「切一刀的不純度下降量」等於父節點的不純度減掉兩個子節點不純度的加權平均。對嚴格凹的函數，這個下降量永遠大於 0（除非兩邊的 $\hat p$ 剛好相同）；對線性的函數，只要兩邊的 $\hat p$ 落在 0.5 的同一側，加權平均就剛好等於父節點的值，下降量是 0。
上面 Heart 的右葉 9 筆全是 Yes、左葉 11 筆有 7 筆 Yes。父節點共 16 筆 Yes、4 筆 No，錯誤率是 4/20 = 0.2；子節點的加權錯誤率為 (11/20)(4/11) + (9/20)0 = 0.2，與不切相同。
父節點 Gini 是 2(16/20)(4/20) = 0.32；子節點的加權 Gini 是 (11/20) × 2(7/11)(4/11) = 0.254545，因此下降 0.065455。這一刀讓類別分布更集中，但沒有改變整體多數類別的判對比例。
葉子的類別比例可以作為訓練樣本的經驗機率，但純葉並不保證對新資料就有高信心；是否校準仍須用保留資料檢查。Bagging 可平均分類器的機率或投票；boosting 依採用的損失與模型更新分數，不是一律把葉機率直接加總。
實務上，sklearn 的分裂與剪枝路徑依 criterion 的不純度定義；再依問題用驗證錯誤率、accuracy 或 AUC（ROC 曲線下面積）選 α 和評估。建立候選樹與比較候選樹的指標可以不同。
兩類問題中，某節點有 50 筆 Yes、50 筆 No。它的 Gini 指數是多少？
兩個模型形式擺在一起：
$$f(X) = \beta_0 + \sum_{j=1}^{p} X_j \beta_j \qquad\text{對上}\qquad f(X) = \sum_{m=1}^{M} c_m \cdot \mathbf{1}(X \in R_m)$$哪一個好？沒有普遍答案，看真實的邊界長什麼樣。 ISLP 圖 8.7 用兩排圖把這件事講完：
| 真實邊界 | 線性模型（左欄） | 樹（右欄） | 誰贏 |
|---|---|---|---|
| 線性（斜的一刀） | 一刀就完美切開 | 要用很多階梯去逼近那條斜線，邊界呈鋸齒狀 | 線性模型 |
| 非線性（方塊狀） | 怎麼轉都切不對，一定有一大塊錯的 | 少數幾次分裂即可逼近 | 樹 |
關鍵在於樹的每一刀都是軸平行的。要表現「$X_1 + X_2 > 1$」這種斜邊界， 樹只能用一堆小台階去爬那條斜線——能逼近，但要很多刀， 而每一刀都花掉自由度、都增加變異。反過來， 「$X_1 < 3$ 且 $X_2 > 5$ 的那一塊特別高」這種方塊狀結構， 線性模型除非你手動把交互作用項乘出來，否則永遠抓不到。
ISLP §8.1.4 把樹的優缺點列成清單，值得整段記下來：
| 內容 | |
|---|---|
| ✔ 好解釋 | 比線性迴歸還好解釋。可以畫出來給非專業的人看懂 |
| ✔ 像人在想事情 | 「先看這個、再看那個」的層層判斷，貼近人的決策過程 |
| ✔ 類別變數免編碼 | 一刀就是「把某些水準分到左邊」，不需要虛擬變數 |
| ✔ 尺度無關 | 只看大小順序，不必標準化，也不怕離群的 x |
| ✘ 準確率不夠好 | 單一棵樹通常打不過本書其他方法 |
| ✘ 非常不穩定 | 資料動一點點，整棵樹的結構可能完全改變 |
後半章從最後一項「不穩定」出發，「為什麼要種一片森林」那一節已經說明為什麼平均可以壓低變異。
真實的決策邊界是一條斜線 $X_1 + X_2 = 1$。用決策樹擬合會發生什麼事？
線性迴歸用整個空間的加法平面描述條件平均，樹以軸向門檻把空間分成區域。真正邊界接近直線時，線性模型用少數係數就能有效描述；用很多矩形葉去逼近斜線可能需要較大樹。真正關係是局部條件和交互作用時，樹的區域規則更自然。講義對比圖是在說明這個偏差與變異取捨，並非保證某方法永遠勝出。
樹預測在每個葉節點內是常數，因此對於超出訓練範圍的新數值通常延用最外側葉的預測，不作線性外推。它可以適應門檻型變化，卻不能用同一葉內的線性趨勢預測更遠的值。是否需要外推，是選模型時應明確考慮的問題。
樹常不需標準化數值，因為嚴格單調轉換保留候選切分的觀測排序；但它不表示任意轉換、不同分箱、捨入或近似搜尋都不影響結果。原生類別處理、one-hot 編碼以及把類別任意編成整數，提供的候選分割不同，必須對照使用的工具。
CatBoost 的類別支援以有序統計及類別組合為工具；它與 sklearn 單樹的處理不同。特徵工程應先在訓練資料擬合，再套到驗證與測試；有序或原生類別功能仍不取代保留資料的效能驗證。
本主題的講義來源與延伸閱讀：CatBoost 有序類別統計。
把一個難題交給幾千位隨機選出的路人，再彙整他們的答案，彙整的答案常常比一個專家還準。這叫群眾智慧（wisdom of the crowd）。機器學習版本的說法是：一群預測器合起來，常常比裡面最好的那一個還準。這一群叫做集成（ensemble）。實務上，集成多半用在專案後段，已經有幾個不錯的模型之後；機器學習競賽的冠軍解法也常常是集成。
硬幣那張圖說明了：在那個二元分類的例子裡，投票要有效，成員得各自比瞎猜好，而且錯的地方不能都一樣。同一份資料、同一種演算法訓練出來的模型，常常在同一批觀測上一起犯錯，這時投一百票和投一票差不多。所以每一種集成方法都得回答：多樣性從哪裡來？
bagging、random forest、boosting 各自的答案，整理在路線圖裡。這一節看最直接的一種：用不同的演算法，例如下面三個完全不同的分類器一起投票；更進一步讓另一個模型學怎麼組合它們，就是 stacking。
最簡單的組合方式是硬投票（hard voting）：每個分類器投一票，票多的類別勝出。另一種是軟投票（soft voting）：平均各模型預測的類別機率，再挑最大的那一類。
Hard voting 數各類別標籤的票；soft voting 平均各類預測機率後選擇最大者。後者保留預測強弱，但不同模型的機率質量和校準程度會影響平均；「有 predict_proba」不代表數值可靠。Lab 的 Carseats 用不同基模型比較投票與 stacking，評估需用相同資料劃分或相同外層 CV 才公平。
Ch08-baggboost-lab-zh.ipynb
回到樹。單一棵樹的問題是變異太大，降變異最古典的手段是平均。設每棵樹的預測變異是 $\sigma^2$、兩兩相關係數是 $\rho$，B 個預測平均之後，變異剩 $\rho\sigma^2+(1-\rho)\sigma^2/B$（推導與互動圖在開頭那節的收合）；如果它們彼此獨立（$\rho=0$），就只剩 $\sigma^2/B$。
所以理想的做法是：蒐集 $B$ 份獨立的訓練資料、各擬合一棵樹、把預測平均起來。 問題是我們只有一份資料。那就用 bootstrap 重抽樣產生 $B$ 份。 這就是 bootstrap aggregation，簡稱 bagging：
$$\hat f_{\text{bag}}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat f^{*b}(x)$$其中 $\hat f^{*b}$ 是用第 $b$ 份 bootstrap 樣本長出來的樹。分類問題就把平均換成多數投票：B 棵樹各投一票，票多的那一類就是答案。
bagging 還能提供袋外誤差估計。有放回抽 $n$ 次，某一筆始終沒被抽到的機率是
$$\left(1 - \frac{1}{n}\right)^n \;\xrightarrow[n \to \infty]{}\; e^{-1} \approx 0.368$$所以每棵樹平均只用到約 2/3 的資料，剩下那 1/3 沒被用到的叫做 袋外樣本（out-of-bag, OOB）。它們對這棵樹來說是天然的驗證集—— 幾乎免費的測試誤差估計。只是要估 bagging 本身的誤差，可以不必另做交叉驗證；拿 OOB 誤差去挑超參數時則另當別論，見下方問答。 （這個 0.632／0.368 在第 5 章 bootstrap 那一節推導過，回去對一下。）
還有一件實務上很重要的事：B 通常設到平均預測已穩定的大小。 ISLP 圖 8.8 顯示誤差隨 B 上升而下降、然後平掉就不動了—— B 太大不會過度擬合（只是增加運算成本），B 太小只是變異還沒壓下來。 所以做法是「挑一個大到誤差已經平掉的 B」，通常 100 到 500 就夠。
圖 8.8 用的是 Heart 資料，還有三個細節：虛線是單棵分類樹的測試誤差；random forest 那條用 $m=\sqrt p$；OOB 誤差那兩條在這張圖裡明顯比測試誤差低，ISLP 說這只是碰巧。
Ch08-baggboost-lab-zh.ipynb
每棵樹從 $n$ 筆訓練資料抽 $n$ 次且允許重複，並非把原資料隨機切成互斥的 B 份。某筆資料完全未被抽中的機率是 $(1-1/n)^n\to e^{-1}$；它可以用那些沒看過自己的樹產生 OOB 預測。不同觀測的 OOB 樹數會不同，樹太少時可能沒有穩定的 OOB 估計。
迴歸對樹預測取平均，分類可以投票或平均機率。scikit-learn 的 random forest 分類以平均類別機率決策；這與先把每棵樹硬分成一類再數票不總是相同。兩個規則都應先對照實現，再解讀講義中的「多數決」概念。
OOB 只排除該筆對某棵樹的訓練，沒有自動排除在全資料預先估計的目標編碼、變數選擇或其他使用 $y$ 的前處理。若資料是同病人多筆記錄，另一筆同病人的記錄可能仍在樹內；OOB 不保證群組隔離。調參反覆挑最好的 OOB score，也會引入選擇偏差；最終報告仍要有與選參隔離的評估。
Lab 用 RandomForestRegressor(max_features=p) 表示每次分裂可用全部特徵的 bagging，再改 max_features 比較 random forest。增加樹數主要穩定隨機平均；深度、葉大小與特徵抽樣仍控制基模型和集成模型的複雜度，不能把「更多樹通常不增加過度擬合」讀成訓練流程無須驗證。
本主題的講義來源與延伸閱讀：Bagging 原理、相關平均量的變異、分類器組合的理論來源、分類器組合教材、ESL 習題解答入口。
固定 x，考慮重複訓練造成的變動。設每棵 bootstrap 樹的預測期望值都是 $\mu(x)$。平均 B 棵之後，期望值還是 $\mu(x)$，所以偏差 $\mu(x)-f(x)$ 和單棵 bootstrap 樹一樣。變異則不同：B 變大只能壓掉樹與樹之間不相關的那一部分，共同的那一部分（本節開頭那條公式的第一項 $\rho\sigma^2$）留下來，這是下一節 random forest 要對付的東西。
所以 bagging 的正確用法是：拿變異很大、偏差很小的東西去平均。長很深不剪枝的樹剛好就是這種東西。深樹的彈性大，近似誤差（偏差）通常小，但資料換一點就長成另一棵（高變異）。反過來，拿 bagging 去平均一堆線性迴歸幾乎沒有用：線性迴歸本來變異就小，沒什麼可壓的。
估 bagging／random forest 本身的測試誤差時，OOB 就夠了，而且便宜太多：擬合一次模型就順手拿到，不必像 k-fold 那樣擬合 k 次。ISLP 說 B 夠大時 OOB 誤差幾乎等於 LOOCV 誤差。
要小心的是兩件事。第一，如果你用 OOB 誤差去挑超參數（例如挑 m、挑樹的深度），那被挑中的那組的 OOB 誤差就跟第 5 章講的一樣會偏低，不能再當誠實的測試誤差報出來。第二，OOB 只有在有 bootstrap 抽樣時才存在——boosting 沒有 bootstrap，所以沒有 OOB，只能用驗證集或 CV。
做 bagging 時，每一棵樹該長多深？
Bagging 的樹若經常依賴同一組特徵，預測也容易一起出錯；單靠增加樹數，無法消除這部分共同變動。
如果資料裡有一個特別強的變數，那麼幾乎每一棵 bagged 樹都會拿它當根節點的分裂變數。 根一樣，接下來的結構也就大同小異——B 棵樹長得像複製品，$\rho$ 接近 1， 平均一百棵跟平均一棵差不多。
Random forest 採用以下方式增加樹的多樣性：每一次分裂， 只准從隨機挑出的 $m$ 個變數裡選（$m < p$，而且每一刀都重新抽一次）。 典型取 $m \approx \sqrt{p}$（分類）或 $m = p/3$（迴歸）。
於是平均有 $(p-m)/p$ 比例的分裂無法選用那個強變數， 其他變數就有機會出頭。這讓樹有機會長得更不一樣，降低預測的相關性， 稱為去相關（decorrelate）；效果與預測能力的取捨仍要看資料。 注意 $m = p$ 時 random forest 就退化成 bagging， 所以 bagging 只是 random forest 的一個特例。
用上一節那條公式來說，random forest 想把第一項 $\rho\sigma^2$ 壓低。Heart 資料有 13 個預測變數，$m\approx\sqrt{13}$，每次分裂只看 4 個。講義也提醒：預測變數很多、彼此又高度相關時，小一點的 $m$ 通常有幫助。
Random forest 在每個節點抽候選變數，再搜尋其最佳門檻值；極端隨機樹（Extra-trees）還對候選變數隨機產生門檻值，再從這些候選中選損失最低者。這減少門檻值搜尋，也增加隨機性，偏差與變異的取捨須用驗證比較；它不等於完全隨機選一刀。ExtraTreesClassifier 預設 bootstrap=False，所以不能直接假設有 OOB。
Random subspaces 對每個基礎模型固定抽一組特徵；random patches 同時抽樣本與特徵。它們與 RF 每個節點重新抽特徵的層次不同。例如三個特徵中，每棵樹固定用兩個是 subspace；同一棵樹根節點看前兩個、子節點又換一組才是 RF 的機制。bootstrap 與是否抽特徵是兩個獨立選項，
固定預測位置 $x$，若各隨機樹預測的變異都是 $\sigma^2$、兩兩相關都是 $\rho$，則 $\operatorname{Var}(B^{-1}\sum_bT_b)=B^{-2}\{B\sigma^2+B(B-1)\rho\sigma^2\}=\rho\sigma^2+(1-\rho)\sigma^2/B$。只有不相關部分隨樹數消失。共同訓練資料會帶來相關性；跨測試點計算的相關係數並不等於這個固定 $x$、對重複訓練取分布的 $\rho$。
講義的基因表達例子有 349 位病人、4,718 個基因的表現量，反應變數有 15 類（正常或 14 種癌症之一）。先挑訓練資料中變異最大的 500 個基因當預測變數，再比較三種 $m$ 與不同樹數（圖 8.10）。單棵分類樹的測試錯誤率是 45.7%，random forest（$m<p$）比 bagging（$m=p$）再好一點；圖中的結果只針對該資料與切分，不能把 $\sqrt p$ 當成所有任務的最佳值。Lab 的 Boston 回歸同樣透過保留資料判斷特徵子抽樣是否改善，分類和回歸的預設設定需分別查證。
本主題的講義來源與延伸閱讀：Random forest 去相關、Extra-trees 官方說明。
Ch08-baggboost-lab-zh.ipynb
Ch08-baggboost-lab-zh.ipynb
平均的變異數公式是在固定 x 下，對重複訓練所產生的預測變動而言。在其他條件相同時，降低相關性有助於壓低不隨 B 消失的那一項。
但限制 m 也可能讓樹錯過有用變數、降低預測能力；「樹變弱」不等於「變異數一定增加」，也可能是偏差增加。這個取捨不能只看相關性，要用驗證誤差判斷。
本頁的相關數字是同一次擬合中、各棵樹跨測試樣本預測向量的平均相關，只能描述這組樹的相似程度，不能代入上面的理論公式。m 是超參數，可從 √p 開始，再用驗證選擇。
Random forest 每次分裂只從 m 個隨機挑出的變數裡選。這個 m 是怎麼抽的？
Bagging 與 random forest 是並行的：B 棵樹互不相干， 誰先誰後無所謂，可以開 B 個執行緒一起長。Boosting 完全相反——樹是序列長出來的， 每一棵都靠前面那些樹的資訊決定自己要做什麼。而且沒有 bootstrap， 每棵樹都看全部資料，只是看的目標被改過。
這是和前兩節不同的另一條路。Bagging 與 random forest 平均一堆深樹，靠平均壓低變異，所以才需要 $\rho$ 那條公式；boosting 不是在平均同分佈的樹，而是一棵接一棵用小樹修正前面還沒解釋掉的部分，主要在降低偏差。因為每棵新樹都考慮了已經長好的樹，小樹就夠用。講義說 bagging 的每棵樹「各自建立在自己的 bootstrap 樣本上」，指的是建樹時互不參照，不是說樹的預測彼此獨立。
ISLP 演算法 8.2 是整章最值得背下來的十行：
步驟 (a) 使用目前模型的殘差 $r$作為新目標；原始目標 $y$ 已包含在殘差的計算中。 第一棵樹抓走一部分結構，剩下沒解釋掉的變成新的目標，第二棵樹去抓它，以此類推。 ISLP 的說法是 boosting 學得很慢（learns slowly）—— 而在統計學習裡，學得慢的方法往往表現得好。
Boosting 有三個要調的參數，而且跟 bagging 不同， 它真的會過度擬合：
| 參數 | 意思 | 典型值 | 調錯會怎樣 |
|---|---|---|---|
| B（樹的棵數） | 跑幾輪 | 由 CV 決定 | 太大會過度擬合（只是通常發生得很慢）。bagging 沒有這個問題 |
| λ（學習率／收縮） | 每棵樹只採用 λ 倍 | 0.01 或 0.001 | 太小 → 需要非常大的 B；太大 → 幾步就衝過頭，開始擬合雜訊 |
| d（每棵樹的總分裂數） | 交互作用深度 | 常常 1 就夠 | d = 1（stump）的集成是加法模型；d 愈大能抓愈高階的交互作用，也愈容易過度擬合 |
講義用同一份基因表達資料改做二元分類（癌症或正常），比較 boosting 與 random forest（圖 8.11）。兩個 boosting 模型都用 $\lambda=0.01$：深度 1 的樹略勝深度 2，兩者都勝過 random forest；單棵樹的測試錯誤率是 24%。這和 random forest 一節那個 15 類、單樹 45.7% 的問題不同，兩個數字不能直接比。用 stump 時得到的是加法模型。
$B$ 與 $\lambda$ 是綁在一起的：λ 砍十倍，B 大約要放大十倍。
lab 用的是 n_estimators=5000, learning_rate=0.001，
互動元件與 Lab 用 max_depth 限制最大深度，這裡記為 D；
它與課本演算法的總分裂數 d 不同。最大深度 D 的二元樹至多有 2^D 個葉，
實際葉數可以更少；總共 d 次分裂則有 d + 1 個葉。
換成 learning_rate=0.2 之後測試 MSE 幾乎一樣（14.48 vs 14.50）——
在這份資料上兩組設定都落在「已經收斂」的區域裡。
Boosting 還有另一種更早的版本。AdaBoost 保留原始目標，並調整每一筆資料的權重：這一輪答錯的點，下一輪權重變大， 於是下一個分類器會特別在意它們。講義的式子是
$$\alpha_j = \eta \log \frac{1 - e_j}{e_j}, \qquad w_{j+1}(i) = \begin{cases} w_j(i) \cdot e^{-\alpha_j} & \text{答對} \\ w_j(i) \cdot e^{+\alpha_j} & \text{答錯} \end{cases}$$其中 $w_j(i)$ 是第 $j$ 輪第 $i$ 筆資料的權重，$\eta$ 是控制更新幅度的係數；這裡的 $\alpha_j$ 和剪枝的 $\alpha$ 無關。下面最終預測式裡的 $h_j(x)$ 是第 $j$ 個分類器的預測類別。
$e_j$ 是第 $j$ 個分類器的加權錯誤率，$\alpha_j$ 同時是它在最終投票裡的份量： 錯誤率愈低、$\alpha$ 愈大、票愈重。最終預測是 $\hat y = \arg\max_k \sum_{j:\, h_j(x) = k} \alpha_j$。 下面的元件取 $\eta = \tfrac{1}{2}$，那正是 Freund–Schapire 原版的 AdaBoost； $\eta = 1$ 代入這組對稱更新會加倍經典二元係數；較大的更新在小樣本上容易讓權重 幾輪就集中到少數幾點上。
Ch08-baggboost-lab-zh.ipynb
可比較三個面向：擬合順序、偏差與變異、樹的深度。而第三點是前兩點的必然結果。
Bagging 降變異。它平均一堆同分佈的估計，期望值不變（偏差不變）、可以平均掉的那部分變異隨 B 變小（樹之間共同的變動 $\rho\sigma^2$ 仍然留著）。既然偏差不會被改善，就必須讓每棵樹的偏差一開始就很低，所以樹要長很深、不剪枝。平均可以降低深樹的高變異。
Boosting 降偏差。它把「還沒解釋掉的部分」（殘差／被放大權重的難樣本）交給下一棵樹，是一個逐步降低偏差的過程。每一步只需要修一小塊，所以每棵樹只要很淺（ISLP 說 $d = 1$ 常常就夠）。反過來，每棵樹都長很深時，模型很快就開始追著雜訊跑；深度、學習率與樹數要一起用驗證來選。
由此還推得幾個實務差別：bagging／RF 的 B 不會過度擬合（平均更多同分佈的東西只會更穩），所以 B 挑大一點就好；boosting 的 B 會過度擬合，必須用 CV 或 early stopping 挑。而且 bagging 可以完全平行、boosting 天生序列（這正是 XGBoost 要花那麼多力氣在工程上加速的原因）。最後：bagging 有 bootstrap 所以有免費的 OOB 誤差，boosting 沒有 bootstrap，所以沒有 OOB。
梯度提升的第 b 棵樹，擬合的目標（response）是什麼？
對可微損失 $\ell(y,F)$，先用最佳常數 $F_0=\arg\min_c\sum_i\ell(y_i,c)$。第 $m$ 輪（對應演算法 8.2 的第 $b$ 棵）在目前預測上算負梯度，再用小樹擬合它：
$$r_{im}=-\left.\frac{\partial\ell(y_i,F)}{\partial F}\right|_{F=F_{m-1}(x_i)},\qquad h_m\approx r_m.$$可沿樹的方向做線搜尋 $\gamma_m=\arg\min_\gamma\sum_i\ell(y_i,F_{m-1}(x_i)+\gamma h_m(x_i))$，再更新 $F_m=F_{m-1}+\nu\gamma_mh_m$。樹也可在每片葉上分別估計最優增量。$0<\nu\le1$ 是學習率（演算法 8.2 的 $\lambda$），樹數、葉數與驗證停止輪次共同控制複雜度。
平方損失取 $\ell=(y-F)^2/2$，負梯度正好是 $y-F$。二元 logistic loss 在 logit 尺度使用 $\ell=\log(1+e^F)-yF$，負梯度為 $y-p$（$p=1/(1+e^{-F})$），輸出預測必須再轉成機率。
這裡用 $m$ 當輪次，$a_m$ 就是上面 AdaBoost 收合裡的 $\alpha_j$。經典二元 AdaBoost 採 $y_i,h_m(x_i)\in\{-1,1\}$，權重先正規化為總和 1。令 $e_m=\sum_iw_iI(y_i\ne h_m(x_i))$，當 $0<e_m<1/2$ 時取 $a_m=\frac12\log\{(1-e_m)/e_m\}$，更新 $w_i\leftarrow w_i e^{-a_my_ih_m(x_i)}$ 後再次正規化。最終以 $\operatorname{sign}\sum_ma_mh_m(x)$ 分類；$e_m=0$ 可停止，$e_m\ge1/2$ 需拒絕或更換弱分類器。
固定本輪弱分類器，指數損失按目前權重寫成 $Z(a)=(1-e)e^{-a}+ee^a$。對 $a$ 微分並令其為 0，得到 $ee^a=(1-e)e^{-a}$，因此 $a=\frac12\log((1-e)/e)$。二階導數為正，所以是極小值。逐點權重與 $\exp\{-y_iF_{m-1}(x_i)\}$ 成正比；新增 $ah_m$ 後便多乘 $e^{-ay_ih_m(x_i)}$。正規化只除以共同常數，不改變下一輪加權錯誤率的相對權重。
把訓練點上的預測看成向量 $F$。對小步長 $\epsilon$，$L(F+\epsilon h)=L(F)+\epsilon\nabla L(F)^Th+O(\epsilon^2)$。選 $h=-\nabla L(F)$ 時一階變化為 $-\epsilon\|\nabla L(F)\|^2$。樹的函數空間有限，故以最小平方把負梯度投影近似成可用的小樹，再調步長。擬合出的樹若與負梯度方向不一致，不能僅由名稱保證每一步都下降。
一般提升法可換損失，但每輪的工作反應和葉增量也要一起換。絕對損失 $|y-F|$ 的負次梯度為 $\operatorname{sign}(y-F)$，零殘差可取 0；初始常數是中位數，葉增量也以相應殘差中位數估計。Huber 損失在 $|r|\le\delta$ 時取 $r^2/2$，否則取 $\delta|r|-\delta^2/2$，負梯度為 $\operatorname{clip}(r,-\delta,\delta)$，因此限制極端殘差的影響。多類別 deviance 的第 $k$ 個分數負梯度為 $I(y_i=k)-p_{ik}$，需以 softmax 連結各類分數並固定可識別表示。
Lab 的 GradientBoostingRegressor 比較 n_estimators、learning_rate 與 max_depth。樹深決定一棵基樹能表示的交互作用層次；深度 1 的 stump 只能用單一特徵分裂，加很多棵也仍是加法結構。控制樹數用 CV 或獨立驗證集，測試集只供最後效能評估。
本主題的講義來源與延伸閱讀：提升法推導、Gradient boosting 影片、提升法推導、Gradient boosting 逐步示範、XGBoost 官方入口。
XGBoost、LightGBM 與 CatBoost 都以提升樹為基礎，分別加入正則化、搜尋加速或類別處理。選擇時先看資料型態、運算成本與驗證表現；以下可依需要查完整方法和實作。
這一節是課堂沒細講的延伸（講義）：三個現代 GBDT 套件與該調的超參數。 第一輪讀可以整節略過，回頭要用套件時再看。
以下將梯度提升延伸到二階目標、正則化與大資料搜尋。 三個常用套件提供了不同的加速與正則化做法：
該調哪些超參數？講義把三個套件的參數名對照起來， 分成「求快」「求準」「防過度擬合」三組：
| 目的 | XGBoost | LightGBM | CatBoost |
|---|---|---|---|
| 求快（抽樣列／欄、少幾棵） | subsamplecolsample_bytreen_estimators | bagging_fractionfeature_fractionnum_iterations | subsamplersmiterations |
| 控制過度擬合／求準 | learning_rate（0.01–0.2）max_depthmin_child_weightgamma | learning_ratemax_depthnum_leavesmin_data_in_leaf | learning_ratedepthl2_leaf_reg |
| 類別變數 | 實驗性支援（建議自己先編碼） | categorical_feature | cat_featuresone_hot_max_size |
lab 在 heart_disease.csv（303 筆、13 個特徵，用 !wget 抓 Packt 的那份）
上一個一個網格搜過去，基準是 0.79：
最大的一筆進步來自把 max_depth
從預設的 6 降到 3（0.79 → 0.812）——「把模型調簡單一點」。
subsample 降到 0.5 又多賺一點，同樣是在減少變異。
而把樹加到 800 棵反而變差：這份資料只有 303 筆，B 大不會有幫助。
Ch08-baggboost-lab-zh.ipynb
XGBoost 相對於課本演算法 8.2 的梯度提升，最主要的統計差別是什麼？（不算工程加速）
講義比較三種做法：one-hot 用指示欄表示每個水準；label encoding 把水準編成整數，只有水準本身有順序時才合理；target encoding 用各類別的目標平均取代類別，但要小心目標洩漏。細節見下方「類別編碼」收合。
本主題的講義來源與延伸閱讀：表格資料上的樹與深度學習比較。
XGBoost 每一輪用損失的一階與二階導數近似目標函數，講義說這和 Newton 法的想法相近。有了這個近似，每片葉的最佳輸出值和一刀分裂的淨收益都有公式可算；收益扣掉 $\gamma$ 之後不為正，就不切。推導細節見 XGBoost 官方的樹提升推導。
講義對這些機制各用一句話帶過，這裡也只列概念，細節見下方連結。
| 套件 | 機制 | 一句話 |
|---|---|---|
| XGBoost | 加權分位數草圖 | 只在少數代表性的切點上找最佳分裂，減少候選數。 |
| XGBoost | 稀疏感知搜尋 | 每個節點學一個「缺失值往哪邊走」的預設方向。 |
| LightGBM | 直方圖分箱 | 先把連續值分成少數幾箱，搜尋只掃過各箱，不必每次排序全部資料。 |
| LightGBM | Leaf-wise 生長 | 每次挑目前收益最大的葉繼續長，要搭配葉數或深度限制。 |
| LightGBM | GOSS（Gradient-based One-Side Sampling） | 保留梯度大的樣本，從梯度小的樣本中抽樣並補權重。 |
| LightGBM | EFB（Exclusive Feature Bundling） | 把很少同時非零的稀疏特徵綁成一欄。 |
| CatBoost | 對稱樹 | 同一層的節點共用同一個分裂條件，推論很快。 |
| CatBoost | 有序目標統計 | 每筆資料的類別編碼，只用排在它前面的資料計算，避免自己的目標洩漏進來。 |
| CatBoost | Ordered boosting | 這筆資料的預測由只看過前面資料的模型產生，梯度再用它自己的標籤計算，避免訓練時的預測太樂觀。 |
| CatBoost | MVS（Minimal Variance Sampling） | 依梯度大小做重要性抽樣，和 GOSS 的目的類似。 |
| XGBoost 等 | DART | 像神經網路的 dropout：每一輪暫時拿掉部分舊樹再長新樹，避免後面的樹過度依賴少數舊樹。 |
直方圖的好處可以用計算量說明：建箱只要掃一次資料，之後每個節點的搜尋量和箱數成正比，不必像精確搜尋那樣每次排序全部資料。Lab 比較三個套件在分類、迴歸、速度與 Melbourne 類別資料上的表現；不同套件同名的參數（例如最少葉內資料量）意義未必相同，要對照各自的文件。
本主題的講義來源與延伸閱讀：XGBoost 原論文、樹模型與特徵尺度、三個 boosting 套件比較、XGBoost 葉值與增益推導、XGBoost 概念影片、二階 Taylor 近似、XGBoost 原生類別支援、XGBoost 缺失值處理、XGBoost 搜尋與系統設計影片、記憶體存取延遲背景、LightGBM 直方圖、GOSS 與 EFB、直方圖 boosting 補充、Leaf-wise 與 level-wise、類別排序分裂的統計來源、Boosting 套件選擇背景、Boosting 套件選擇背景、CatBoost 原論文、CatBoost MVS、CatBoost 方法選擇背景、CatBoost 類別參數範例、DART dropout 官方說明。
One-hot 以每個類別的指示欄表示成員關係；線性模型含截距時通常刪去參考組以避免完全共線。樹不要求係數設計滿秩，但多個 dummy 給它的是「是不是某個類別」的候選條件，未必等同原生按子集合分割。高基數類別也會增加輸入欄數。
Ordinal encoding 把名目類別編成 0、1、2，會給以門檻值分裂的樹一個人為排序；Cat、Dog、Hamster 的編碼不意味著動物具有數值距離。真正有順序的類別可以明確定義順序；無順序類別若僅為方便整數化，必須瞭解它允許的分割及其限制。LabelEncoder 用來編碼目標，特徵類別通常用 OrdinalEncoder 或 OneHotEncoder。
Target encoding 以該組的目標平均表示類別。講義動物表中 Cat 的 0.67 是兩個 1 與一個 0 的平均；單筆類別會把自己目標完整暴露，產生特別嚴重的洩漏。
所以編碼對照只能用訓練資料估計；訓練資料本身也要用折外的方式編碼（講義的 K-fold target encoding），不能讓一筆資料的目標進入它自己的編碼。CatBoost 的有序目標統計是另一種避開洩漏的做法。
Melbourne Lab 同時比較原生類別和 one-hot 設定時，傳給模型的欄位型別、enable_categorical 或 cat_features 是方法的一部分。XGBoost 與 LightGBM 可學習缺失預設方向；CatBoost 的數值缺失與字串類別處理則有各自規則。特別是字串類別中的缺失需一致地轉成可識別類別，不能用某套件的成功推定其他套件也可直接接受。
本主題的講義來源與延伸閱讀：類別編碼教學、K-fold target encoding。
集成模型還能用重要度輔助解讀，也能再學一個模型合併預測。重要度不代表因果；stacking 的合併器必須使用折外預測。BART 則以貝氏抽樣表示樹與預測的不確定性。
這一節是課堂沒細講的延伸（講義、ISLP §8.2.4）：變數重要度的讀法、 stacking，以及貝氏版的加法樹 BART。第一輪讀可以整節略過。
單一棵樹最大的優點是可以畫出來給人看。集成之後這個優點就沒了。 你不可能把 500 棵樹貼在牆上。變數重要度（variable importance） 是輔助解讀集成模型的常見做法：
ISLP 圖 8.9 就是 Heart 資料上的這張圖（相對於最大值標準化），
最重要的三個是 Thal、Ca、ChestPain。
下面用 lab 的 Boston 例子重畫（Heart 不在 ISLP 0.4.0 裡）：
不純度重要度累加每個特徵帶來的加權 RSS、Gini 或 entropy 降幅，再正規化。連續值多或類別水準多的變數有更多候選切分，容易在訓練內找到偶然收益；所以高重要度不自動表示可靠訊號，更不表示因果影響。
另一種常見做法是置換重要度：在驗證資料上把某個變數的值打亂，看預測表現掉多少。它問的是「模型多依賴這個變數」，但同樣會被高度相關的變數互相稀釋。
「投票分類器」一節的 voting 是用一個固定的規則（多數票、平均）去合併。 Stacking 問了一個很自然的問題：為什麼不訓練一個模型來做這件合併？
做法的關鍵在怎麼造合併器的訓練資料。這裡有一個必須避開的洩漏：
第 1 步為什麼一定要用 CV？因為如果拿成員模型在訓練資料上的預測去餵合併器， 那些預測好得不真實（成員在訓練資料上本來就準），合併器會學到「完全相信最會過度擬合的那個成員」。 這就是第 5 章那個「所有用到 y 的步驟都要關在折裡面」的老規矩。
Ch08-baggboost-lab-zh.ipynb
一棵深樹可能幾乎記住訓練標籤。若用它在同一訓練資料的預測訓練負責合併預測的模型（blender），後者會以為深樹近乎完美，新資料卻沒有這種優勢。折外預測讓每筆在產生基模型特徵時都沒有參與相應基模型的訓練，才較接近未來預測情境。
Lab 的 StackingClassifier 內部 CV 是產生 blender 輸入，不是整個 stacking 的最後效能評估。外部 cross_val_score 再劃分資料，才能估計完整流程。這裡內層產生折外特徵，外層評估整個流程；一般的 nested hyperparameter search 則用內層選超參數，兩者的內層用途不同。
cv='prefit' 假設基模型已擬合；如果這些模型看過同一組 blender 標籤，就沒有內部折外保護。基模型中的 scaler、類別編碼與變數篩選也應放在相應訓練折內部。Soft voting 固定平均權重，stacking 學權重或更複雜組合，因此需要更多資料與獨立驗證。
BART（Bayesian additive regression trees）站在 bagging 與 boosting 中間：
因為每一輪只是微調，BART 每次只作局部修改， 模型的正則化還來自偏好小樹與收縮葉值的先驗。要選三個數字：樹的棵數 $K$、迭代次數 $B$、 丟掉的暖機輪數 $L$。講義的建議是 $K = 200$、$B = 1000$、$L = 100$， 最終預測是暖機後的平均
$$\hat f(x) = \frac{1}{B - L} \sum_{b = L+1}^{B} \hat f^b(x)$$其中 $\hat f^b$ 是第 $b$ 輪 K 棵樹的總和。
BART 出名的地方是幾乎不用調參就能跑出好結果（out-of-box performance）。
ISLP 圖 8.13 在 Heart 資料上比較 BART 與 boosting：BART 過了 100 輪暖機之後，訓練與測試誤差就穩定下來；boosting 跑到幾百輪之後開始過度擬合。演算法的起點是讓 K 棵樹都只有一片葉，葉值是 $\frac1{nK}\sum_i y_i$，加起來剛好是 $y$ 的平均。
Ch08-baggboost-lab-zh.ipynb
每一輪依序更新 K 棵樹：先扣掉其他 K−1 棵樹的預測，得到這棵樹要負責的偏殘差；再對這棵樹做一個小擾動（長一刀、剪一刀，或改葉值），是否接受由 MCMC 決定。正則化來自偏好小樹、把每棵樹的葉值往 0 收縮的先驗，所以每棵樹只負責一小部分訊號。完整的後驗推導超出課本範圍（ISLP 也這麼說），見下方 BART 教材。
B 是 MCMC 的總輪數，L 是丟棄的暖機輪數。每個保留輪的 $\hat f^b(x)$ 已經把 K 棵樹加總；預測再跨保留輪平均。增加 B 改善後驗 Monte Carlo 估計的精度，不等於增加模型中的 K 或逐輪累加新樹。講義 K=200、B=1000、L=100 是設定示例，不保證所有資料都已收斂。
本主題的講義來源與延伸閱讀：BART 後驗更新教材。
訓練 stacking 的合併器時，成員模型的預測值一定要用交叉驗證產生。為什麼？
下面幾題取自 ISLP §8.4 的課後習題，題號都對得回課本。先自己想過再點選項； 每個選項都有解說；需要完整解答時，可查閱下面3個站。
課本第 3 題要你把 Gini 指數、錯誤率、交叉熵都畫成 $\hat p_{{m1}}$ 的函數（兩類）。畫出來之後，哪一句話最能說明「為什麼分裂準則不用錯誤率」？
十個 bootstrap 樣本各擬合一棵分類樹，對同一個 X 給出 $P(\text{{紅}} \mid X)$ 的十個估計：0.1, 0.15, 0.2, 0.2, 0.55, 0.6, 0.6, 0.65, 0.7, 0.75。用多數投票與用平均機率，分別會判成哪一類？
課本第 2 題要你說明：用深度 1 的樹（stump）做 boosting，為什麼結果是一個加法模型 $f(X) = \sum_{{j=1}}^{{p}} f_j(X_j)$？
課本第 7 題要你在 Boston 上掃過一整片 max_features（m）與 n_estimators（B）的組合，畫成圖 8.10 那樣。預期會看到什麼？
考前把這一頁掃過去就好。
| 方法 | 樹怎麼來 | 樹的深度 | 主要降的是 | B 會過度擬合嗎 | 免費驗證集 |
|---|---|---|---|---|---|
| 單一棵樹 | 一棵，貪婪長 + 剪枝 | 由 CV 選 α | —（偏差與變異都要自己顧） | — | 沒有（要 CV） |
| Bagging | B 個 bootstrap，並行 | 很深、不剪枝 | 變異 | 不會（B 大只是增加運算成本） | 有（OOB） |
| Random Forest | 同上 ＋ 每刀只看 m 個變數 | 很深、不剪枝 | 變異（多壓了 ρ） | 不會 | 有（OOB） |
| Boosting | 擬合殘差／調權重，序列 | 很淺（d 常常 = 1） | 偏差 | 會（要用 CV 或 early stopping） | 沒有（沒 bootstrap） |
| BART | 微調上一輪的樹，MCMC | 小樹 | 兩者（貝氏平均） | 不會（B 是 MCMC 迭代數） | 沒有 |
| 名稱 | 式子 | 備註 |
|---|---|---|
| 樹的模型形式 | $f(X) = \sum_{m=1}^{M} c_m \mathbf{1}(X \in R_m)$ | 式 8.9 |
| 要最小化的 RSS | $\sum_{j=1}^{J} \sum_{i \in R_j} (y_i - \hat y_{R_j})^2$ | 式 8.1 |
| 一刀的目標 | $\sum_{i \in R_1(j,s)} (y_i - \hat y_{R_1})^2 + \sum_{i \in R_2(j,s)} (y_i - \hat y_{R_2})^2$ | 式 8.3，掃過所有 (j, s) |
| 成本複雜度剪枝 | $\sum_{m=1}^{|T|} \sum_{i \in R_m} (y_i - \hat y_{R_m})^2 + \alpha|T|$ | 式 8.4，形式同 lasso |
| 錯誤率 | $E = 1 - \max_k \hat p_{mk}$ | 式 8.5，不當分裂準則 |
| Gini 指數 | $G = \sum_{k} \hat p_{mk}(1 - \hat p_{mk})$ | 式 8.6 |
| 交叉熵 | $D = -\sum_{k} \hat p_{mk} \log \hat p_{mk}$ | 式 8.7 |
| Bagging | $\hat f_{\text{bag}}(x) = \frac1B \sum_{b} \hat f^{*b}(x)$ | 分類版改多數投票 |
| 平均的變異 | $\frac{1-\rho}{B}\sigma^2 + \rho\sigma^2$ | 第二項不隨 B 消失 → random forest 要壓 ρ |
| OOB 比例 | $(1 - 1/n)^n \to e^{-1} \approx 0.368$ | 第 5 章的 0.632 反面 |
| Boosting 更新 | $\hat f(x) \leftarrow \hat f(x) + \lambda \hat f^b(x)$ | 式 8.10 |
| Boosting 殘差 | $r_i \leftarrow r_i - \lambda \hat f^b(x_i)$ | 式 8.11 |
| Boosting 輸出 | $\hat f(x) = \sum_{b=1}^{B} \lambda \hat f^b(x)$ | 式 8.12，d = 1 時是加法模型 |
| AdaBoost 的權重 | $\alpha_j = \eta \log\frac{1-e_j}{e_j}$ | 講義，$e_j$ 是加權錯誤率 |
| 套件 | 什麼時候選它 |
|---|---|
| XGBoost | 社群最大、生產環境的支援最完整。不確定就先用它 |
| LightGBM | 資料很大、同時要速度與準確率時的較好選擇 |
| CatBoost | 資料量小，或類別變數很重要的時候 |
本主題的講義來源與延伸閱讀：ChefBoost 樹工具入口。
這些題目取自課程題庫，只給對錯與說明，不計分。答錯就回到對應章節重讀。
詞彙卡整理本章講義與 ISLP 第 8 章中常用的統計或機器學習專有名詞，正面附英文名稱。 先看正面的術語，試著說出定義，再翻面核對。可以洗牌複習，也可以搭配本章例子練習解釋。