線性分類器：畫一條線，把世界分兩邊

🐘 先把問題說清楚：不是「線性一定最好」

Ch2 用機率密度與 Bayesian 方法設計分類器；有些結果最後也會長成線性判別函數。Ch3 換一個角度：不先假設資料由哪一個 pdf 產生，而是直接求出線性函數的參數。

這樣做的優點是兩個字：簡單、快。代價也很明白：如果資料真的不是線性可分，我們只能在「允許錯誤」的前提下，選一個準則最好的線。

本次重寫的閱讀契約：比例看得到，簡略跑不掉

本頁不是把原文壓成八句口號。每一站都保留原文的定義、主要公式、課本例題、Remark／演算法與工程限制；完整對照表見套件根目錄的 source_coverage.md。

讀完這一章，你要能做的事

• 看見 $g(\boldsymbol{x})$ 就說出正負側與距離意義。
• 手算一次感知機更新，並解釋「線性可分才保證收斂」。
• 從 MSE 推到正規方程、LMS 與後驗機率的連結。
• 說清楚 Logistic 的 log-odds、SVM 的 margin、support vector 與 $C/\nu$。
• 用凸包／縮減凸包的幾何語言重新說一次 SVM。

🐘 生活類比：機場安檢線

地板上的線是決策邊界。線的一側是「可通過」，另一側是「請留下」。$\boldsymbol{w}$ 不是線本身，而是垂直指向線的箭頭；它告訴我們哪個方向會讓分數增加。

取決策線上的兩點 $\boldsymbol{x}_1,\boldsymbol{x}_2$，兩點都讓 $g=0$，相減後：

所以線上任意方向都和 $\boldsymbol{w}$ 垂直。這就是「法向量」的來源，不是背公式背出來的。

距離不是 $|g|$ 本身：要除以箭頭長度

原文先給兩個幾何量。原點到線的距離是：

任意點 $\boldsymbol{x}$ 到線的有號距離大小是：

因此 $|g(\boldsymbol{x})|$ 只能當作「未正規化信心分數」；真正的歐氏距離還要除以 $\|\boldsymbol{w}\|$。$g>0$ 與 $g<0$ 分別在兩側；若 $w_0=0$，線穿過原點。

數字例子：令 $\boldsymbol{w}=[2,1]^T$、$w_0=-3$、$\boldsymbol{x}=[2,1]^T$。

你應該能回答

① 為什麼 $\boldsymbol{w}$ 垂直於超平面？ ② $|g|$ 和真正距離差在哪？ ③ $w_0=0$ 時幾何上發生什麼事？

1. 先把「不過原點的線」搬進擴充空間

若 $\boldsymbol{w}^{*T}\boldsymbol{x}=0$ 能分開兩類，則 $\omega_1$ 在正側、$\omega_2$ 在負側。一般有 threshold 的線也能用擴充向量處理：

這個小技巧讓後面所有式子看起來都像「過原點的超平面」。最後一個座標其實就是截距的插座。

2. Perceptron cost：只把錯題加總

令 $Y$ 是目前被分錯的樣本集合；$\delta_x=-1$（$\omega_1$）或 $+1$（$\omega_2$）。在錯誤樣本上，下面的乘積會是正數；全對時 $Y=\varnothing$，成本變成 0：

$J$ 是連續、分段線性的函數。當某個點跨過邊界，$Y$ 會改變，梯度在那個位置不連續；所以它不是一個可以放心套用平滑梯度下降理論的普通函數。

更新方向很有直覺：被誤判的點會把 $\boldsymbol{w}$ 往「修正它」的方向推。

3. 原文演算法骨架

1. 隨機選 $\boldsymbol{w}(0)$ 與正學習率 $\rho_0$。
2. 掃過所有樣本，找出 $\delta_{x_i}\boldsymbol{w}^{T}\boldsymbol{x}_i\geq0$ 的錯誤集合 $Y$。
3. 依 (3.9) 更新；調整 $\rho_t$；重複。
4. $Y=\varnothing$ 才停止。

一次把整批錯誤加總，是 batch 形式；下面的 reward-and-punishment 則是一個樣本一個樣本修。

4. 為什麼會收斂？把證明讀成「距離帳本」

原文不是只說「實驗看起來會停」。它選一個真正的解 $\boldsymbol{w}^*$，比較 $\boldsymbol{w}(t)$ 和 $\alpha\boldsymbol{w}^*$ 的距離。更新後平方距離可被壓成：

$\beta^2$ 是所有可能錯誤子集合的修正向量最大平方長度；$\gamma<0$ 則記錄真解對錯誤樣本提供的負向量量。選 $\alpha=\beta^2/(2|\gamma|)$ 後，累加得到 (3.16)。要讓「累積前進量」壓過「累積噪聲」，學習率需滿足：

第一條說步子總和不能太小；第二條說平方噪聲總和要有限。典型選擇是 $\rho_t=c/(t+1)$。在適當有界條件下，常數 $\rho$ 也能收斂，但速度與步幅很敏感。重點：收斂保證的前提是線性可分，而且解不一定唯一。

5. Example 3.1：一次更新真的把線轉正

目前權重是 $[1,1,-0.5]^T$、$\rho=0.7$；被誤判的兩點是 $[0.4,0.05]^T$（$\delta=-1$）與 $[-0.2,0.75]^T$（$\delta=+1$）。把兩個錯誤一起放入 (3.9)：

新線是 $1.42x_1+0.51x_2-0.5=0$，課本指出它把所有點分對，演算法停止。

6. Reward-and-punishment：單筆更新版

樣本依序進來。$\omega_1$ 被錯判就加 $\rho\boldsymbol{x}_{(t)}$；$\omega_2$ 被錯判就減；分對就完全不動：

它就是「答對獎勵不扣分、答錯處罰並訂正」的學習機制。

7. Example 3.2：四點逐步得到 $x_1=x_2$

類別 $\omega_1$：$(-1,0),(0,1)$；類別 $\omega_2$：$(0,-1),(1,0)$。擴充成三維，$\rho=1$、$\boldsymbol{w}(0)=[0,0,0]^T$：

再掃過四個點都不需修正，得到 $-x_1+x_2=0$，也就是 $x_1=x_2$。

8. Perceptron 是一個神經元

分類規則是 $\boldsymbol{w}^{T}\boldsymbol{x}+w_0>0$ 判給 $\omega_1$、小於 0 判給 $\omega_2$。網路實作就是：輸入乘 synaptic weights → 加總 threshold → 經過 hard limiter step function。

輸出也可以改成 0/1。這個 McCulloch–Pitts 型神經元，是後面更複雜學習網路的基本零件。

9. 不可分時：Pocket 先把最好成績放口袋

若類別不可線性分，普通感知機會一直更新、不保證停止。Pocket algorithm 仍照感知機更新，但另外保存目前「分對最多」的 $\boldsymbol{w}_s$ 與歷史正確數 $b_s$：

1. 隨機初始化 $\boldsymbol{w}(0)$，口袋向量與計數歸零。
2. 做一次感知機更新，計算新權重分對的樣本數 $b$。
3. 若 $b>b_s$，把新權重放進口袋；繼續迭代。

原文指出，在適當條件下它以機率一收斂到錯誤數最少的解。它不是把不可分資料變魔術，而是把「永遠找不到零錯誤」改成「留住目前最好的線」。

10. Kesler's construction：把多類問題搬成二類

多類時，每一類有一個 $g_i(\boldsymbol{x})=\boldsymbol{w}_i^T\boldsymbol{x}$；若 $\boldsymbol{x}\in\omega_i$，希望 $g_i>g_j$ 對所有 $j\ne i$。對每一個 $i,j$ 建立 block vector：

於是原本的 $M$ 類比較，被改寫成擴充空間裡的「所有 block vector 都在正側」的二類感知機問題。

Example 3.3：三類分別落在三個象限。課本以 $\rho_t=0.5$ 的感知機跑 4 次，得到：

這個建構法的代價是維度變成 $(l+1)M$，樣本數也變成 $(M-1)N$；類別多時，計算量會明顯增加。

你應該能回答

① 感知機 cost 為何是分段線性？ ② 收斂條件兩個無窮和各自防什麼？ ③ Pocket 解決什麼問題？ ④ Kesler 如何把多類轉成二類？

1. MSE：允許犯錯，但要付平方代價

二類 desired response 設成 $y=+1$ 或 $-1$；模型輸出是 $\boldsymbol{w}^{T}\boldsymbol{x}$。MSE 把整體期望誤差平方最小化：

若把兩類的條件分布展開，這就是 $\omega_1$ 的 $(1-\boldsymbol{x}^{T}\boldsymbol{w})^2$ 加上 $\omega_2$ 的 $(1+\boldsymbol{x}^{T}\boldsymbol{w})^2$，並用先驗機率加權（3.28）。

$R_x$ 是 autocorrelation matrix；$E[\boldsymbol{x}y]$ 是 cross-correlation。前提是 $R_x$ 可逆。

2. 正交投影：MSE 為何長這樣？

把隨機變數當成向量，內積用 $E[uv]$ 定義。模型 $\boldsymbol{w}^{T}\boldsymbol{x}$ 是由輸入座標張成的子空間中的一個向量。最好的解讓殘差 $y-\boldsymbol{w}^{T}\boldsymbol{x}$ 和每個輸入 $x_i$ 都垂直：

所以 MSE 不是神秘的黑盒：它把 $y$ 正交投影到輸入能表示的子空間。若真實關係不在這個子空間裡，剩下的就是不可消除的投影誤差。

3. 多類 MSE：一個輸出變成 one-hot 向量

$M$ 類時，令 $y_i=1$（屬於 $\omega_i$）或 0（不屬於），$W=[\boldsymbol{w}_1,\ldots,\boldsymbol{w}_M]$。一次最小化所有輸出的平方誤差：

它等價於 $M$ 個獨立的 scalar MSE 問題。最後選輸出最大的類別。

4. 不知道期望值怎麼辦？Robbins–Monro → LMS

理論解需要 $R_x$ 與 cross-correlation，但真實 pdf 通常不知道。隨機近似用單筆樣本替代期望：

第一條不讓學習太早凍結；第二條讓累積噪聲有限，於是 $\rho_k\to0$，估計值以機率、也以 MSE 意義趨近真解（3.37–3.39）。最簡單的平均值例子是：

套回分類問題，就是 LMS／Widrow–Hoff：

若用固定 $\rho$，只要 $0<\rho<2/\operatorname{trace}(R_x)$，平均值仍趨近 MSE 解，但方差會停在一個非零常數（3.41）。$\rho$ 小：穩但慢；$\rho$ 大：快但抖。固定步幅的好處是資料統計慢慢漂移時，模型還能追蹤。

5. LS／SSE：把期望值換成有限訓練集

有 $N$ 筆資料時，直接最小化誤差平方和：

把樣本排成 $X$ 的列、desired response 排成 $\boldsymbol{y}$：

$X^+$ 是 pseudoinverse；只有 $X^TX$ 可逆、$X$ 滿 column rank 時，上面的顯式逆矩陣才合法。當 $N>l$，通常沒有一條線通過所有點，偽逆給的是平方和最小的折衷。

6. Example 3.4：不可分資料也能算出一條最好的線

課本給兩類各 5 個二維點，追加常數 1 後得到 $10\times3$ 的 $X$；desired response 是前五個 $+1$、後五個 $-1$：

這條線不可能零錯誤，但它的總平方誤差已經是所有線性模型中最小。這是「最佳」不等於「全對」的第一個重要示範。

你應該能回答

① MSE 正規方程的幾何意義？ ② LMS 為何需要遞減步幅？固定步幅何時反而有用？ ③ 偽逆在 $N>l$ 時替我們解決什麼問題？

1. Regression：最好的平方誤差預測是條件平均

先不限定模型是直線。給定觀測到的 $\boldsymbol{x}$，想用某個 $\tilde{\boldsymbol{y}}$ 預測 $\boldsymbol{y}$：

證明就是平方展開：拿任意估計 $\tilde{\boldsymbol{y}}$ 與條件平均比較，交叉項的期望為 0，剩下一個非負的距離平方：

因此 regression function $E[\boldsymbol{y}\mid\boldsymbol{x}]$ 一般可以是非線性的；只有加上共同 Gaussian 等條件時，才會退化成線性函數。

2. 1-of-M 輸出：MSE 偷偷估出 posterior

多類標籤用 one-hot 向量 $\boldsymbol{y}$：正確類別是 1，其餘是 0。令 $\boldsymbol{g}(\boldsymbol{x})$ 是模型輸出：

把平方項加減 $\left(E[y_i\mid\boldsymbol{x}]\right)^2$，可以分成「模型和條件平均的距離」以及與 $g_i$ 無關的條件變異：

所以只要用 1/0 目標做 MSE，理想上 $g_i(\boldsymbol{x})$ 就是第 $i$ 類的後驗機率估計；再取最大的 $g_i$ 就能做 Bayesian-style decision。限制不在這個結論，而在於你選的模型（例如直線）能不能把真正的非線性 posterior 表示好。

3. Bias–variance：同一個真相，換資料集就換一條線

訓練資料集記成 $\mathcal{D}$，模型其實是 $g(\boldsymbol{x};\mathcal{D})$。對所有可能的同大小資料集平均：

第一項是 bias，第二項是 variance。模型越簡單，常見情況是 bias 大、variance 小；模型越複雜，可能把每個資料集的噪聲都背起來，bias 小但 variance 大。

原文也提醒：分類不能只看 MSE。輸出即使離 $+1/-1$ 很遠，只要大多站在正確一側，分類錯誤率仍可能很好。有限資料下，我們要找的是 bias 與 variance 的折衷；這正是後續泛化理論關心的問題。

你應該能回答

① 為什麼條件平均是 MSE 最佳答案？ ② one-hot 的條件平均為什麼等於 posterior？ ③ 高階模型如何同時降低 bias 卻提高 variance？

1. 多類：先寫 log likelihood ratio，再讓機率總和為 1

選第 $M$ 類當參考類別，對 $i=1,\ldots,M-1$ 設：

兩式合起來就是 softmax 型的 posterior：

2. 二類：sigmoid 是 softmax 的特例

當 $w_0+\boldsymbol{w}^T\boldsymbol{x}=0$，兩類機率相等；正側往 $\omega_1$ 靠近，負側往 $\omega_2$ 靠近。這次的輸出不是硬切的 $+1/-1$，而是有機率意義的軟分數。

3. Maximum likelihood：參數怎麼學？

已知每筆訓練樣本的類別，令 $\boldsymbol{\theta}$ 收集所有 $w_{i,0}$ 與 $\boldsymbol{w}_i$。原文先寫條件 likelihood 的乘積：

利用 Bayes 公式，所有與 $\boldsymbol{\theta}$ 無關的 marginal 項收進常數 $C$，真正要最大化的是：

接著可用梯度法或其他最佳化法求參數。這就是 Logistic regression 的核心：對條件機率做最大概似，不需要先寫出每一類的完整 pdf。

4. Logistic 與 LDA：長得像，假設不同

若各類是 Gaussian 且共用 covariance $\Sigma$，Ch2 的 LDA log posterior odds 也可寫成：

兩者在實務上可能很接近；差異不在「邊界一定不同」，而在「參數估計時使用的資訊與假設不同」。

你應該能回答

① log-odds 為何適合用直線建模？ ② softmax 如何保證機率和為 1？ ③ Logistic 與 LDA 的關鍵差異是模型形狀還是估參數的假設？

1. Generalization：為什麼不選貼邊的線？

兩條線都能把訓練點分對，但留白較大的線，資料稍微漂移時比較不容易翻到另一側。這就是原文引入的 generalization intuition：訓練資料以外的新資料，也要有安全空間。

固定方向後，選一條到兩類最近點距離相等的線；再在所有方向中挑 margin 最大者。

2. 正規化後，最大邊距變成一個凸最佳化問題

因為把 $\boldsymbol{w},w_0$ 同時放大不會改變線的位置，所以把最近的正類點規範成 $+1$、負類點規範成 $-1$：

最小化 $\|\boldsymbol{w}\|$ 就是最大化 margin。這個目標是嚴格凸、限制是線性不等式，因此最優超平面唯一。

3. KKT：為什麼只有少數 support vectors 決定答案？

把每個限制放進 Lagrangian：

由此得到：

若 $\lambda_i=0$，那個點對最後的 $\boldsymbol{w}$ 沒貢獻；若 $\lambda_i>0$，互補鬆弛迫使它落在 $\boldsymbol{w}^T\boldsymbol{x}+w_0=\pm1$ 上。這些離邊界最近的點就是 support vectors。

4. Dual：資料只透過內積出現

這個對偶形式有兩個大禮物：第一，限制變成好處理的等式＋非負條件；第二，輸入只以 pairwise inner product 出現，公式不直接依賴輸入維度。這正是下一章 kernel trick 能接手的入口。注意：最終 $\boldsymbol{w}$ 唯一，但能產生它的 $\lambda_i$ 組合不一定唯一。

5. Example 3.5：最佳線 $x_1=0$，但 multipliers 不唯一

正類是 $[1,1]^T,[1,-1]^T$；負類是 $[-1,1]^T,[-1,-1]^T$。正方形的左右兩邊最近，所以最佳線：

四個點都剛好在兩條 margin 線上，因此四個都是 support vectors。把已知 $w_1=1,w_2=w_0=0$ 放回 KKT，只剩三條線性方程配四個 $\lambda$，所以 multipliers 可有多組，但最後的線一樣。

6. 不可分：slack variables 與 soft margin

不可分時，點有三類：在 margin 外且分對、落在 margin 內但仍分對、跑到錯側。用 $\xi_i$ 把三種情況放進同一條限制：

$\xi_i=0$ 表示在 margin 外；$0<\xi_i\leq1$ 表示帶內但可能仍分對；$\xi_i>1$ 表示錯側。原文先提出「是否有 slack」的 indicator cost，再用連續的 $\sum_i\xi_i$ 近似，讓問題保持凸且可解。

對偶的差異變成：

若 $\xi_i>0$，KKT 會把對應 $\lambda_i$ 推到 $C$。$C$ 越大，錯誤懲罰越重，模型會犧牲 margin 去少犯錯；$C$ 越小，容許較多點進 margin，換取較寬的車道。

7. Example 3.6：$C=0.2$ 和 $C=1000$ 的取捨

同一批不可分資料，$C=0.2$ 時讓較多點進 margin，車道較寬；$C=1000$ 時更重視每個 slack，線會移動、方向改變，margin 變窄，但錯誤／帶內點較少。這不是「哪個 $C$ 永遠正確」，而是工程上的正則化旋鈕。

8. 多類 SVM：三條路

原文也提醒計算限制：天真的 QP solver 訓練成本約 $O(N^3)$、記憶體約 $O(N^2)$；大型資料會用 decomposition／working set，SMO 更把 working set 壓到兩個點。

你應該能回答

① 最大化 margin 為何等價於最小化 $\|\boldsymbol{w}\|^2$？ ② KKT 如何挑出 support vectors？ ③ $C$ 變大會怎麼改變 margin？ ④ ECOC 的碼距如何提供容錯？

1. ν-SVM：把 margin 寬度本身拿來調

用兩條平行線 $\boldsymbol{w}^T\boldsymbol{x}+w_0=\pm\rho$，$\rho\geq0$ 也是要學的變數。原文的 primal 問題：

若 $\xi_i=0$，兩條 margin 線的距離是 $2\rho/\|\boldsymbol{w}\|$。$\nu\in[0,1]$ 控制擴大 margin 與容許 slack 的拉扯。

2. ν 的兩個可讀保證

對偶限制可寫成：

在非平凡解 $\rho>0$ 下，原文推得：

白話：$\nu$ 給訓練錯誤率一個上界，也給 support vector 數量一個下界。這不是測試集保證；它是設計者對訓練解的可讀控制訊號。

3. Convex hull：最大邊距其實是在找兩個最近點

一組點的 convex hull 是所有 convex combinations 的集合：

對可分兩類，分別在正類與負類 convex hull 找兩個最近點；連接它們的線段，其垂直平分線就是最大 margin 分類器。也就是「解析的 SVM dual」和「幾何最近點」是同一件事的兩種語言。

4. RCH：資料不可分時，把兩塊凸包縮小

普通 convex hull 可能相交，最近距離是 0；RCH 對每個係數加上上限 $\mu$：

$\mu$ 越小，每個原始點能分到的權重越少，RCH 越縮；兩個 RCH 若終於分開，就可以取兩個最近點的垂直平分線作分類器。縮放關係是 $\nu=2/(\mu N)$。若兩類各有 $N/2$ 個點，最小可行 $\mu$ 時每個 RCH 會縮到各自類別的 centroid；兩個 centroid 不同才有非平凡方向。

5. 原文的可行性與工程提醒

• 若 $\mu<1/N_{\min}$，某一類的係數總和連 1 都湊不出來；因此需要 $\mu\geq1/N_{\min}$。
• 若兩個 RCH 仍相交，最近距離為 0，可能得到 $\boldsymbol{w}=\boldsymbol{0}$ 的 trivial solution；所以 $\nu$ 不能任意小。
• 幾何法得到的方向和 KKT 解一致，但不可分時 $w_0$ 的幾何中點公式與 KKT 的 $w_0$ 可能需再校正。
• RCH 的極點不一定是原始樣本，而是樣本的組合；$\mu$ 越小，參與一個極點的樣本可能越多，因此最近點演算法不只是把 convex-hull 演算法照搬。

6. 原文 Problems、MATLAB 與 computer experiments：把理論落地

原文最後不是只留公式，而是要求實作與比較：

課本 computer experiments 使用固定亂數種子，並比較類別平均差距 $5$、$2$、$1$ 的資料；這正好展示類別越靠近，線性方法的錯誤與模型差異越值得觀察。

你應該能回答

① ν 同時控制哪兩個量？ ② 為什麼 convex hull 最近點會產生最大 margin？ ③ RCH 的 $\mu$ 為何能處理原本相交的類別？ ④ 大型 SVM 為何需要 SMO／decomposition？

把這一章端上你的作品集

做一本 「三種線性分類器同場競技」的迷你專案（nb6）：同一份「可分成／攪在一起」的合成資料，用手寫感知機、正規方程（LS）、SVM 各訓練一次，畫出三條線、印出準確率——這是「我能把想法變成可量測分類器」的最短證明，面試拿得出手。

接著往上游走：Ch4 多層感知機（把直線疊成曲線）→ Ch5 深度學習（kernel → CNN/RNN），直攻影像與音訊 AI。線性分類器不是天花板，是最穩的出發樓梯。