9.3 支援向量機（Support Vector Machines）

非線性分類的核方法革命

📄 頁 384–389 📖 ISLP §9.3 難度 ★★★★☆ SVM 核方法 RBF 非線性分類 Heart 資料

📖 概述

前兩節我們學到：§9.1 的最大邊界分類器只能在線性可分的完美世界運作，§9.2 的支援向量分類器（SVC）引入寬容參數 C，允許些許誤分類以換取更穩健的邊界。但這兩個方法有個共同的根本侷限：它們只能畫出直線（或超平面）決策邊界。

現實世界的資料很少是線性可分的——想想手寫數字辨識、人臉辨識、或信用卡詐欺偵測。本節介紹的 支援向量機（SVM） 正是為了解決這個問題：透過 核方法（kernel trick），SVM 能隱式地在高維（甚至無限維）空間中尋找線性邊界，這在原空間中對應到非線性的決策邊界。

ISLP §9.3 的核心貢獻：將線性分類器推廣到非線性情境，不需手動構造高階特徵，而是透過核函數自動完成特徵空間的擴張——這是機器學習史上最優雅的計算技巧之一。

📎 Boser, Guyon & Vapnik (1992) — 首次提出 kernel trick 應用於 SVM · Cortes & Vapnik (1995) — 引入 soft margin · Schölkopf & Smola (2002) Learning with Kernels — 經典專著

9.3.1 非線性決策邊界

想像你在一個二維平面上有兩類資料點，一類圍成圓圈，另一類散布在圈外（如課本 Figure 9.8 左圖）。任何直線都無法區分這兩類——線性分類器在這裡完全無能為力。

在第 7 章我們曾遇到類似困境：當反應變數與預測變數呈非線性關係時，線性迴歸的表現很差。當時的解法是擴張特徵空間——加入多項式項（X², X³, …）或交互作用項（X₁X₂）。SVM 用同樣的策略：不直接用原始 p 個特徵擬合，而是使用 2p 個特徵（每個原始特徵加上它的平方項）：

\text{原特徵：} X_1, X_2, \ldots, X_p \quad\longrightarrow\quad \text{擴張特徵：} X_1, X_1^2, X_2, X_2^2, \ldots, X_p, X_p^2

在擴張後的特徵空間中，最佳化問題（9.16）找到的決策邊界是線性的；但映射回原始空間後，邊界變成二次多項式 q(x) = 0 的解——這就是一條非線性曲線。

然而問題來了：如果我們加入三次項、四次項、交互作用項……特徵數量會爆炸性成長。在這種情況下，直接在高維空間做計算是不可行的。這就是核方法的登場時機。

9.3.2 核方法：SVM 的核心魔法

線性 SVM 的內積表示

關鍵洞察：支援向量分類器的最佳化問題（9.12–9.15）的解只依賴觀測值之間的內積（inner product），而非觀測值本身。兩個向量 a, b 的內積定義為：

\langle \mathbf{x}_i, \mathbf{x}_{i'} \rangle = \sum_{j=1}^{p} x_{ij} \, x_{i'j}

線性支援向量分類器可以表示為：

f(\mathbf{x}) = \beta_0 + \sum_{i=1}^{n} \alpha_i \langle \mathbf{x}, \mathbf{x}_i \rangle

其中 α_i 只有在 x_i 是支援向量（support vector）時才非零。令 S 為支援向量的索引集合，則：

f(\mathbf{x}) = \beta_0 + \sum_{i \in S} \alpha_i \langle \mathbf{x}, \mathbf{x}_i \rangle

這意味著：要評估分類函數 f(x)，只需要計算新點 x 與每個支援向量的內積。

核函數：取代內積

現在是關鍵一步——把所有的內積 ⟨x_i, x_i'⟩ 替換成一個更一般的核函數 K(x_i, x_i')：

f(\mathbf{x}) = \beta_0 + \sum_{i \in S} \alpha_i \, K(\mathbf{x}, \mathbf{x}_i)

核函數本質上是在隱式地計算兩個觀測值在某個高維（或無限維）特徵空間中的內積，但不需要真的把資料映射到那個空間去。這就是 kernel trick——用 O(n²) 的計算成本換取無限維度的表現力。

三種常用的核函數

核函數	公式	參數	特性
線性核（Linear）	\(K(\mathbf{x}_i, \mathbf{x}_{i'}) = \sum_{j=1}^{p} x_{ij} x_{i'j}\)	無	退化成標準 SVC；等價於 Pearson 相關性量度
多項式核（Polynomial）	\(K(\mathbf{x}_i, \mathbf{x}_{i'}) = \left(1 + \sum_{j=1}^{p} x_{ij} x_{i'j}\right)^d\)	d（次數）	對應到 d 次多項式特徵空間；d=1 即為線性核
徑向核（Radial / RBF）	\(K(\mathbf{x}_i, \mathbf{x}_{i'}) = \exp\!\left(-\gamma \sum_{j=1}^{p} (x_{ij} - x_{i'j})^2\right)\)	γ > 0	局部行為：只受鄰近點影響；隱式特徵空間為無限維

為何必須用核方法？

直接擴張特徵空間（如 9.3.1 所述）需要明確構造所有高階項——對於 d 次多項式核，這意味著 O(p^d) 個特徵。核方法的優雅之處在於：只需要計算所有 'n choose 2' 對觀測值的核函數值，完全不需踏入高維空間。對於 RBF 核這類隱式特徵空間為無限維的核，直接計算是物理上不可能的。

💡 生活化比喻：核方法就像用 Google 翻譯——你不需要學對方的語言，只需把問題丟進翻譯機（核函數），它自動在「高維語義空間」中找到對應關係。或者想成：你不需要親自飛到每個國家去比較物價，只需要看匯率換算表（核矩陣）就能做跨國比較。

金融：信用卡詐欺偵測

詐欺交易的特徵空間高度非線性——正常用戶的消費模式與詐欺者之間沒有簡單的線性邊界。SVM + RBF 核可以在高維隱式空間中捕捉「深夜小額測試 → 大額異常消費」這類非線性模式。實務中，γ 參數控制「局部性」：γ 越大，決策邊界越貼近訓練資料（可能過擬合）；γ 越小，邊界越平滑。

生醫：蛋白質結構分類

胺基酸序列之間的相似度無法用簡單的歐氏距離捕捉。使用專用的 string kernel 或 spectrum kernel，SVM 可以在序列空間中隱式工作，區分不同功能的蛋白質家族。這是線性方法（如 LDA）完全無法處理的場景。

9.3.3 應用：Heart 疾病資料

課本在 Heart 資料集上比較 LDA、SVC 和 SVM（RBF 核）。297 位受試者（移除 6 筆缺失值），隨機分為 207 訓練 / 90 測試。13 個預測變數（Age, Sex, Chol 等），目標是預測心臟病（AHD）。

以下程式碼重現課本圖 9.10 的核心比較：

#!/usr/bin/env python3
"""9.3 SVM vs LDA on Heart data — reproducing ISLP Figure 9.10 core comparison."""
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

try:
    from google.colab import drive
    drive.mount('/content/drive')
    DATA_PATH = '/content/drive/MyDrive/ISLP_data/'
except ImportError:
    DATA_PATH = '/tmp/'

from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.metrics import roc_curve, roc_auc_score

# Load Heart data
heart = pd.read_csv(DATA_PATH + 'Heart.csv')
# Remove rows with missing values
heart = heart.dropna()
# Convert AHD to binary
heart['AHD_binary'] = (heart['AHD'] == 'Yes').astype(int)
# Select predictors
predictors = ['Age', 'Sex', 'ChestPain', 'RestBP', 'Chol', 'Fbs', 'RestECG',
              'MaxHR', 'ExAng', 'Oldpeak', 'Slope', 'Ca', 'Thal']
X = pd.get_dummies(heart[predictors], drop_first=True).to_numpy(dtype=np.float64)
y = heart['AHD_binary'].to_numpy(dtype=np.float64)

# Train/test split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=90, random_state=42, stratify=y.astype(int))

print(f'Train: {X_train.shape[0]}, Test: {X_test.shape[0]}')
print(f'Positive rate: {y_train.mean():.2f}')

# Fit models
lda = LinearDiscriminantAnalysis()
lda.fit(X_train, y_train)

svc = SVC(kernel='linear', C=1.0, probability=True, random_state=42)
svc.fit(X_train, y_train)

svm = SVC(kernel='rbf', C=1.0, gamma=0.01, probability=True, random_state=42)
svm.fit(X_train, y_train)

# Predict probabilities
y_score_lda = lda.predict_proba(X_test)[:, 1]
y_score_svc = svc.predict_proba(X_test)[:, 1]
y_score_svm = svm.predict_proba(X_test)[:, 1]

# Compute ROC
fpr_lda, tpr_lda, _ = roc_curve(y_test.astype(int), y_score_lda)
fpr_svc, tpr_svc, _ = roc_curve(y_test.astype(int), y_score_svc)
fpr_svm, tpr_svm, _ = roc_curve(y_test.astype(int), y_score_svm)

auc_lda = roc_auc_score(y_test.astype(int), y_score_lda)
auc_svc = roc_auc_score(y_test.astype(int), y_score_svc)
auc_svm = roc_auc_score(y_test.astype(int), y_score_svm)

print(f'LDA AUC: {auc_lda:.3f}')
print(f'SVC AUC: {auc_svc:.3f}')
print(f'SVM (RBF) AUC: {auc_svm:.3f}')

# Plot
fig, ax = plt.subplots(figsize=(7, 6))
ax.plot(fpr_lda, tpr_lda, 'b-', label=f'LDA (AUC={auc_lda:.3f})', linewidth=2)
ax.plot(fpr_svc, tpr_svc, 'g--', label=f'SVC (AUC={auc_svc:.3f})', linewidth=2)
ax.plot(fpr_svm, tpr_svm, 'r-', label=f'SVM RBF (AUC={auc_svm:.3f})', linewidth=2)
ax.plot([0, 1], [0, 1], 'k:', alpha=0.3)
ax.set_xlabel('False Positive Rate')
ax.set_ylabel('True Positive Rate')
ax.set_title('ROC Curves: LDA vs SVC vs SVM (Heart Data)')
ax.legend(loc='lower right')
ax.grid(True, alpha=0.2)
plt.tight_layout()
plt.savefig('/tmp/svm_heart_roc.png', dpi=100, bbox_inches='tight')
plt.show()

# 預期輸出（數值為近似，來自課本 Figure 9.10 與 sklearn 實作） Train: 207, Test: 90 Positive rate: 0.46 LDA AUC: 0.892 SVC AUC: 0.898 SVM (RBF) AUC: 0.911

如課本 Figure 9.10 所示：SVM（RBF 核）的 ROC 曲線最貼近左上角，AUC 最高。RBF 核的非線性決策邊界比線性 SVC 或 LDA 更適合捕捉心臟病預測因子之間的複雜交互作用。

RBF 核的 γ 參數：控制局部性

RBF 核的行為可以用一個比喻來理解：每個訓練點都是一座小山，γ 控制山的「陡峭度」。γ 越大，山越陡——只有非常靠近山頂（訓練點）的測試點才會受到影響。γ 越小，山越平緩——遠處的點也會被納入考量。

#!/usr/bin/env python3
"""Demonstrate the effect of gamma on RBF kernel decision boundary."""
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import numpy as np

try:
    from google.colab import drive
    drive.mount('/content/drive')
    DATA_PATH = '/content/drive/MyDrive/ISLP_data/'
except ImportError:
    DATA_PATH = '/tmp/'

from sklearn.svm import SVC

# Generate non-linear toy data (concentric circles pattern)
np.random.seed(42)
n_samples = 200
r_inner = np.random.uniform(0, 1.5, n_samples // 2)
theta_inner = np.random.uniform(0, 2 * np.pi, n_samples // 2)
X_inner = np.column_stack([r_inner * np.cos(theta_inner), r_inner * np.sin(theta_inner)])

r_outer = np.random.uniform(2.5, 4.0, n_samples // 2)
theta_outer = np.random.uniform(0, 2 * np.pi, n_samples // 2)
X_outer = np.column_stack([r_outer * np.cos(theta_outer), r_outer * np.sin(theta_outer)])

X = np.vstack([X_inner, X_outer])
y = np.array([0] * (n_samples // 2) + [1] * (n_samples // 2))

# Fit SVMs with different gamma values
gammas = [0.1, 1.0, 10.0, 100.0]
fig, axes = plt.subplots(2, 2, figsize=(10, 10))

xx, yy = np.meshgrid(np.linspace(-5, 5, 200), np.linspace(-5, 5, 200))

for ax, gamma in zip(axes.ravel(), gammas):
    svm = SVC(kernel='rbf', C=1.0, gamma=gamma, random_state=42)
    svm.fit(X, y)
    Z = svm.decision_function(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    ax.contourf(xx, yy, Z, levels=[-10, 0, 10], colors=['#1a3a5c', '#3a1a1a'], alpha=0.3)
    ax.contour(xx, yy, Z, levels=[0], colors='white', linewidths=1.5)
    ax.scatter(X[y == 0, 0], X[y == 0, 1], c='#58a6ff', s=10, label='Class 0')
    ax.scatter(X[y == 1, 0], X[y == 1, 1], c='#f85149', s=10, label='Class 1')
    n_sv = (svm.n_support_[0] + svm.n_support_[1])
    ax.set_title(f'γ = {gamma}  (支援向量: {n_sv})')
    ax.set_xlim(-5, 5); ax.set_ylim(-5, 5)

plt.suptitle('RBF 核的 γ 參數對決策邊界的影響', fontsize=14, color='#f0f6fc')
plt.tight_layout()
plt.savefig('/tmp/svm_gamma_demo.png', dpi=100, bbox_inches='tight')
plt.show()

📊 γ 參數的解讀：γ 越小 → 決策邊界越平滑、越不容易過擬合；γ 越大 → 決策邊界越扭曲、越貼近訓練資料。上述示範中，γ=0.1 產生平滑的圓形邊界，γ=100 則產生極度扭曲且支援向量數量暴增的過擬合邊界。

自動非線性：不需手動設計高階特徵，核函數自動處理
理論保證：凸最佳化問題，解為全域最佳（不像神經網路可能卡在局部最小值）
稀疏解：只有支援向量影響決策邊界，模型緊湊
無限維度：RBF 核隱式使用無限維空間，但計算仍在原始樣本數級別
小樣本強：在高維低樣本（p ≫ n）場景下仍表現穩健

計算成本 O(n²)～O(n³)：大樣本（n > 10⁵）時難以擴展
參數敏感：C 和 γ 需要仔細調整（網格搜尋 + CV），預設值不保證好結果
黑箱決策：非線性 SVM 的決策邊界難以解釋——不像決策樹可以畫出規則
機率校準差：原始 SVM 不輸出機率；需要 Platt scaling 後處理（SVC(probability=True)）
類別不平衡敏感：預設對兩類對稱處理，不平衡時需加權或調整 C

📊 類似技術比較

方法	決策邊界	計算複雜度	可解釋性	最適合場景
LDA	線性	O(p²n)	高（線性係數）	類別近似常態、共變異數相同
Logistic Regression	線性	O(pn)	高（勝算比）	需要機率輸出、低維度
SVC（線性核）	線性	O(n²)～O(n³)	高	高維稀疏資料（如文本）
SVM（RBF 核）	非線性	O(n²)～O(n³)	低	中小樣本、複雜邊界
決策樹／隨機森林	階梯狀	O(pn log n)	高（規則可視化）	混合型態變數、需要可解釋性
神經網路	任意非線性	O(epochs × n)	極低	超大樣本、影像／語音

「核方法的精髓在於：你不用知道高維空間長什麼樣子，你只需要知道兩點在那個空間中有多相似。這正是『不直接解決問題，而是改變問題的表述方式』的典範。」

🔗 Hermes 架構啟發：Kernel Trick 與 Agent 路由

SVM 的 kernel trick 給了我一個深刻的架構洞察。在 Hermes 的多 agent 系統中，當子 agent 需要協作時，我不需要讓每個 agent 直接存取對方的內部狀態（這就像在原始空間中工作）；我只需要定義一個相似度函數（kernel）——例如，agent A 的輸出摘要與 agent B 的任務描述的語義相似度——就能在不共享內部表徵的情況下實現有效的任務路由。這就是 C-A-F Router（見 caf-router skill）的設計哲學來源：與其讓 agents 互相理解，不如定義一個好的相似度度量。

9.2 支援向量分類器 9.4 多類別 SVM