第四章非線性分類器 — 互動式學習講義（Nonlinear Classifiers）

為什麼需要非線性？

Why nonlinear (4.1–2)

上一章的直線分類器遇到「畫不開」的資料——最簡單的例子就是 XOR。

🐘 生活類比：「非黑即白」的世界不夠用了

想像你開飲料店，規則：「甜的加冰、不甜的不加冰」——甜度軸畫一條線就好。但規則改成：「甜的加冰、不甜的也加冰、唯獨半甜不加冰」——怎麼畫線都分不開。這就是非線性分類器誕生的原因。

🔗 XOR：最簡單的「線畫不開」

互斥或：兩輸入相同→B，不同→A。四個點，任何一條直線都分不開。但兩條線可以！

$x_1$	$x_2$	XOR	類別
0	0	0	B
0	1	1	A
1	0	1	A
1	1	0	B

互動 Demo 1｜XOR 問題：你來畫線試試拖曳畫線，看能不能分開四個點

拖曳畫線——分不開時按「自動解」看兩條線怎麼合作。

你應該能回答

① XOR 為什麼一條線分不開？ ② 兩條線要怎麼切才能解？

MLP 架構：把空間切成格子

Two-layer & three-layer perceptrons (4.3–4)

XOR 的解法：第一層「畫兩條線」切成格子，第二層「把格子歸類」。

🐘 生活類比：疊篩子

你有一堆紅豆綠豆混在一起。第一層篩子按大小分，第二層按形狀分，第三層把結果組合——每層很簡單，幾層疊起來就能分辨任何組合。MLP 就是這種「疊篩子」架構。

第一層每個神經元畫一條超平面，$p$ 個神經元畫 $p$ 條，把空間切成多面體格子；第二層把格子歸類。兩層可分格子狀類別；三層可分任何形狀（格子的聯集）。

超立方體映射

隱藏層用 step 函數時，輸出 $y_i$ 要嘛 0 要嘛 1——整個隱藏層的輸出就是超立方體 $H_p$ 的一個頂點。第一層把輸入空間映射到超立方體頂點，第二層在超立方體裡畫超平面分類。

你應該能回答

① 兩層 MLP 能分哪些形狀？ ② 三層增加什麼能力？ ③ 超立方體映射的意思？

精確分類：先把網路「蓋」到零失誤

Constructive techniques (4.5)

不最小化任何代價函數——直接把網路一個神經元一個神經元地蓋，直到全部分對。

🐘 生活類比：積木蓋房子

你不會一次畫好整棟藍圖。你先蓋一間小房間（一個神經元），不夠住再加——直到所有人都有房間。tiling 演算法就是這樣：一個「主人」開始，每當發現某區域還有混亂，就加一個「助手」處理。tiling 保證：每個新主人至少正確分類一個之前分錯的樣本 → 有限步收斂。最多三層就夠。

cascade correlation（Fahlman 1990）是另一種建構式，一個一個加隱藏神經元，每加一個就把「殘差」吃掉。

你應該能回答

① tiling 為什麼一定收斂？ ② 「精確分類」的問題？（Hint：過擬合＋泛化）

反向傳播：深度學習的引擎

Backpropagation (4.6)

「精確分類」太暴力；我們改最小化代價函數——但 step 不可微。解法：sigmoid + 鏈鎖法則 + 反向傳播。

🐘 生活類比：工廠品質回饋

客戶抱怨成品品質差——你回溯：二樓加工有問題，還是一樓原料就有瑕疵？反向傳播就是：從最終誤差出發，一層一層往回追「誰該負責多少」。

sigmoid：把 step 換成可微分的 S 曲線

$$f(x)=\frac{1}{1+e^{-ax}} \quad (4.1)\qquad f'(x)=a\,f(x)(1-f(x))$$

$a$ 越大越接近 step。實務 $a=1$。

核心：$\delta$ 規則——鏈鎖法則的系統化

定義敏感度 $\delta_j^r(i)=\partial\mathcal{E}/\partial v_j^r$——「這個神經元的加權和變一點點，誤差會變多少」。

$$\Delta\boldsymbol{w}_j^r=-\mu\sum_i \delta_j^r(i)\,\boldsymbol{y}^{r-1}(i) \quad (4.12)$$

$$\delta_j^L(i)=e_j(i)\,f'(v_j^L(i)) \quad (4.15)\qquad \delta_j^{r-1}(i)=\Bigl[\sum_k \delta_k^r(i)\,w_{kj}^r\Bigr]\,f'(v_j^{r-1}(i)) \quad (4.21)$$

口訣：輸出層 $\delta$ = 誤差乘導數；隱藏層 $\delta$ = 下一層 $\delta$ 加權回來乘本層導數。理解這個就理解了「反向」傳播。

互動 Demo 3｜反向傳播學會 XOR2-2-1 MLP + sigmoid

左：決策邊界；右：損失曲線。損失降到 0.01 以下 = 學會 XOR。

你應該能回答

① 為什麼 step 不能用在 BP？ ② $\delta$ 規則的「反向」指什麼？ ③ batch vs pattern 各自優缺？

BP 變型＋代價函數：訓練大型網路的秘訣

Variations on BP & cost functions (4.7–8)

原始 BP 有兩個問題：收斂慢＋容易卡在局部最小。這一節的變型就是「加速器」和「導航儀」。

🐘 生活類比：下坡滑雪

想像你在山上滑雪找最低點。基本 BP 就像「每一步都看腳下、往下走」——遇到小坑就卡住（局部最小）。momentum 就像滑雪的「慣性」：你有速度時，小坑擋不住你，你會衝過去。

$$\Delta\boldsymbol{w}_j^r(\mathrm{new})=\alpha\,\Delta\boldsymbol{w}_j^r(\mathrm{old})-\mu\sum_i\delta_j^r(i)\,\boldsymbol{y}^{r-1}(i) \quad (4.24)$$

$\alpha$（慣性因子，通常 0.1–0.8）越大，「衝力」越大。在低曲率區域，momentum 等效於把學習率放大到 $\mu/(1-\alpha)$——收斂速度提升 2 倍以上！

自適應學習率：成本在降 → 加大步幅（$r_i=1.05$）；成本在升 → 縮小步幅（$r_d=0.7$）。像自動調整油門。

快速推進（quickprop）：把每個權重當獨立的二次曲線來猜最小值——像「滑雪時看遠一點，直接瞄谷底」。

代價函數：用什麼當「考試標準」？

最小平方（LS）：$\mathcal{E}(i)=\frac{1}{2}\sum_m(y_m-\hat{y}_m)^2$——好用但有 plateau 問題（錯誤很大時梯度反而很小，因為趨近常數）。

交叉熵（cross-entropy）：

$$J=-\sum_i\sum_k\Bigl[y_k(i)\ln\hat{y}_k(i)+(1-y_k(i))\ln(1-\hat{y}_k(i))\Bigr] \quad (4.30)$$

關鍵差異：交叉熵用相對誤差（不是絕對誤差），小值和大值同等重要。而且如果預測完全錯誤（$\hat{y}\to 0$ 但 $y=1$），交叉熵會趨近 $\infty$ → 梯度很大 → 訓練反應快。LS 的梯度趨近常數 → 訓練「卡住」。

softmax：$\hat{y}_k=\exp(v_k^L)/\sum_{k'}\exp(v_{k'}^L)$——保證輸出在 [0,1] 且和為 1，直接當機率用。

🍀 代價函數選法口訣：迴歸用 LS，分類用交叉熵，多類用 softmax。三者在最優條件下都估後驗機率（回顧 Ch3），但交叉學訓練最快。

你應該能回答

① momentum 為什麼能加速？（Hint：等效學習率放大） ② 交叉熵 vs LS 的關鍵差異？ ③ softmax 保證什麼？

網路太大怎麼辦？剪枝、正則化、建構式

Choice of network size (4.9)

神經元太多 → 過擬合；太少 → 欠擬合。這是 bias–variance 兩難的網路版。

🐘 生活類比：請客點菜

請 10 個人吃飯，你不會點 100 道菜（太多＝浪費＝過擬合），也不會只點 3 道（太少＝吃不飽＝欠擬合）。你會「剛好夠吃」。網路大小選擇就是在找「剛好夠用」的神經元數量。

圖 4.14 經典：訓練集誤差一路降（學到越多越好），但驗證集誤差降到某個點就開始升——這個點就是「過訓練」的開始，應該在這裡停下來（early stopping）。

三種策略

策略	思路	代表方法
估數量	用公式算出「最多需要幾個超平面切出格子」	$M=\sum_{m=0}^l\binom{K}{m}$（4.37）——但這只算靜態能力，不考慮訓練過程
先大後剪	先訓練一個超大網路，再逐步砍掉「不重要」的權重	saliency（4.39）：$s_i=h_{ii}w_i^2/2$——對損失影響小的先砍
正則化	在損失函數裡加「懲罰大權重」的項	$J=\sum\mathcal{E}(i)+\alpha\sum h(w_k^2)$（4.40）——權重太大就被罰

Bartlett 定理（1998）：泛化能力取決於「權重大小」而非「權重數量」！即使網路很大，只要權重小、訓練誤差低，泛化就好。這解釋了為什麼大型網路有時泛化也不差。

你應該能回答

① early stopping 的原理？ ② 剪枝 vs 正則化的差異？ ③ Bartlett 定理說什麼？

廣義線性分類器：先映射、再畫線

Generalized linear classifiers (4.12–13)

既然直線分不開，那就先把資料「搬到一個新空間」，在那裡直線就分得開了。這就是「廣義線性分類器」的核心思想。

🐘 生活類比：從地球搬到火星

在地球上，有些城市之間被山脈擋住（不可線性分開）。如果你把它們「投影」到一張 3D 地圖上，山脈就繞開了——直線就能連上。映射 $\phi$ 就是這個「投影」：把原始資料搬到高維空間，在那裡畫直線，再投影回來。

$$g(\boldsymbol{x})=w_0+\sum_{i=1}^k w_i f_i(\boldsymbol{x}) \quad (4.47)$$

Cover 定理：空間越高，越容易線性可分

Cover（1965）的結論：$N$ 個點在 $l$ 維空間隨機分佈時，線性可分的機率：

$$P_N^l=\frac{1}{2^{N-1}}\sum_{i=0}^l\binom{N-1}{i} \quad (4.50)$$

白話：當 $N \leq l+1$ 時，機率 = 1（一定線性可分）；當 $N = 2(l+1)$ 時，機率 = 1/2。所以：把資料投到更高維空間，分類就更容易。這就是 kernel 方法的理論基礎。

你應該能回答

① 廣義線性分類器的「廣義」指什麼？ ② Cover 定理的白話意思是？ ③ 為什麼高維空間更容易線性可分？

多項式分類器：用「平方項」當新特徵

Polynomial classifiers (4.14)

Cover 定理說「高維好分」——那用什麼當新維度？最直覺的選擇：二次項 $x_1^2, x_1x_2, x_2^2$。

🐘 生活類比：用「面積」來分辨

你要分辨「長房間」和「方房間」——只看長度或寬度都分不開（它們重疊）。但如果你計算「面積 = 長乘寬」，兩類立刻分開。面積就是「二次項」——原始特徵的交互作用。

$$g(\boldsymbol{x})=w_0+\sum_i w_i x_i+\sum_{i\lt j} w_{ij}x_ix_j+\sum_i w_{ii}x_i^2 \quad (4.51)$$

$l=2$ 的二次展開：$\boldsymbol{y}=[x_1, x_2, x_1x_2, x_1^2, x_2^2]^T$——5 維。XOR 問題用 $x_1x_2$ 一項就解開：

$$y_1+y_2-2y_3-\frac{1}{4}=0 \quad\Leftrightarrow\quad x_1+x_2-2x_1x_2-\frac{1}{4}=0$$

⚠ 但自由參數爆炸：$l=10, r=10$ 時 $k=184,756$ 個！「維度詛咒」在這裡開始出現。

你應該能回答

① 為什麼 $x_1x_2$ 能解 XOR？ ② 多項式分類器的問題？（Hint：參數爆炸）

RBF 網路：每個神經元管一塊「圓形區域」

Radial Basis Function networks (4.15)

MLP 的神經元管「半空間」（超平面一邊）；RBF 的神經元管「圓形區域」——離中心近就亮、遠就暗。

🐘 生活類比：Wi-Fi 基地台

每個 Wi-Fi 基地台覆蓋一個圓形區域：離得近訊號強、離得遠訊號弱。RBF 網路就是把一堆「基地台」放在空間裡，每個基地台的輸出是高斯衰減：

$$f_i(\boldsymbol{x})=\exp\Bigl(-\frac{\|\boldsymbol{x}-\boldsymbol{c}_i\|^2}{2\sigma_i^2}\Bigr) \quad (4.53)$$

然後用一個線性組合把所有基地台的輸出加起來：

$$g(\boldsymbol{x})=w_0+\sum_{i=1}^k w_i\exp\Bigl(-\frac{\|\boldsymbol{x}-\boldsymbol{c}_i\|^2}{2\sigma_i^2}\Bigr) \quad (4.55)$$

RBF vs MLP：RBF 是「局域性」（離中心遠就沒反應），MLP 是「全域性」（超平面影響整個空間）。RBF 學得快但容易需要更多神經元（維度詛咒）；MLP 學得慢但泛化更好。

中心怎麼選？

隨機挑：從訓練集隨機抽 $k$ 個點當中心（最簡單）
聚類：先跑 K-means 找聚類中心 → 用它們當 RBF 中心
SVM：支持向量就是最佳中心（見下一節）

🍀 類比口訣：RBF 像「在空間裡撒種子，每顆種子管一塊地」；種子太多（高維度）→ 要撒的種子爆炸 → 這就是維度詛咒的 RBF 版。

你應該能回答

① RBF 的「局域性」指什麼？ ② RBF vs MLP 的優缺？ ③ 中心選擇的三種方法？

非線性 SVM：Mercer 定理與核技巧

Nonlinear SVM (4.18)

SVM 對偶公式裡，資料只以「內積」出現——如果我們能把「內積」換成「核函數」，就自動在高維空間裡畫超平面，而不用真的去高維空間算。這就是「核技巧」。

🐘 生活類比：用「距離量表」取代「實際距離」

你要比較兩個人的基因相似度——你不會真的去量每個鹼基對（維度太高）。你用一個「相似度分數」（核函數）來代替。只要這個分數滿足 Mercer 條件（半正定），它就等價於某個高維空間的內積——你不用知道那個空間長什麼樣。

$$K(\boldsymbol{x},\boldsymbol{z})=\langle\phi(\boldsymbol{x}),\phi(\boldsymbol{z})\rangle \quad (4.63)$$

常見核函數：

核	公式	效果
多項式	$(\boldsymbol{x}^\top\boldsymbol{z}+1)^q$	$q$ 次多項式決策邊界
RBF（高斯）	$\exp(-\\|\boldsymbol{x}-\boldsymbol{z}\\|^2/\sigma^2)$	無限維空間、局部決策
雙曲正切	$\tanh(\beta\boldsymbol{x}^\top\boldsymbol{z}+\gamma)$	類似兩層感知機

$$\max_{\lambda}\Bigl(\sum_i\lambda_i-\frac{1}{2}\sum_{i,j}\lambda_i\lambda_j y_i y_j K(\boldsymbol{x}_i,\boldsymbol{x}_j)\Bigr) \quad (4.69)$$

結果：只有支持向量（$\lambda_i\gt 0$）才出現在求和裡 → $N_s \ll N$ → 訓練快、泛化好。維度詛咒被核技巧完美繞過。

你應該能回答

① Mercer 定理說什麼？（Hint：核函數 = 某空間內積） ② 核技巧為什麼能繞過維度詛咒？ ③ 三種常見核的效果差異？

決策樹＋集成：一連串 if-then 達到智慧

Decision trees & ensembles (4.20–23)

決策樹＝一連串「if feature ≤ threshold → 左，else → 右」的二元問題。集成方法＝一群「弱」決策樹投票，達到「強」分類。

🐘 生活類比：20 問遊戲

你玩過「20 個問題猜動物」嗎？每個問題把可能性砍一半。決策樹就是這樣：每個節點問一個問題（「體溫 > 37.5？」），yes/no 走不同分支，直到葉子節點給出答案。熵（entropy）衡量「每個節點裡有多混亂」：

$$I(t)=-\sum_{i=1}^M P(\omega_i|t)\log_2 P(\omega_i|t) \quad (4.113)$$

每問一個問題，我們希望「混亂度下降最多」——這就是資訊增益：

$$\Delta I(t)=I(t)-\frac{N_{tY}}{N_t}I(t_Y)-\frac{N_{tN}}{N_t}I(t_N) \quad (4.114)$$

Example 4.2：$I(t)=1.521$，切完後 $\Delta I(t)=0.315$——混亂度降了 0.315。

集成方法：三個臭皮匠勝過諸葛亮

Bagging：隨機抽多份訓練集，各建一棵樹，最後投票。隨機森林：每棵樹只看 $F$ 個隨機特徵——更多樣性、更好泛化。

AdaBoost（boosting）：一次只建一個「弱分類器」（比亂猜好一點），然後把分錯的樣本加權，再建下一個。反覆 K 次：

$$\alpha_m=\frac{1}{2}\ln\frac{1-P_m}{P_m} \quad (4.139)\qquad w_i^{(m+1)}=\frac{w_i^{(m)}\exp(-y_i\alpha_m\phi(\boldsymbol{x}_i;\boldsymbol{\theta}_m))}{Z_m} \quad (4.140)$$

AdaBoost 的驚人性質：訓練 error 最終趨近 0（即使每個弱分類器只比亂猜好一點）；而且測試 error 會在訓練 error 歸零之後繼續降——它有「抗過擬合」的免疫力（margin 證明，4.142）。

組合規則：乘法 vs 加法 vs 投票

規則	公式	特性
乘法（幾何平均）	$\max\prod_j P_j(\omega_i\|x)$	最優但對 0 敏感
加法（算術平均）	$\max\sum_j P_j(\omega_i\|x)$	穩健、最常用
多數投票	≥半數同意才決定	硬決策、最直覺

實務建議：加法（sum rule）最穩健；投票簡單好用；乘法在「有些分類器很爛」時容易崩潰。

你應該能回答

① 熵（entropy）= 0 代表什麼？ ② AdaBoost 為什麼有抗過擬合能力？ ③ 組合規則中哪個最穩健？

職涯延伸路線圖

Career Roadmap

作品集建議

做一本「MLP vs RBF vs SVM 三種非線性分類器同場競技」的迷你專案——同一份非線性可分資料，三種模型各訓練一次，畫決策邊界、印準確率。