支持向量机（SVM）

SVM是一种基于最大间隔原则的分类方法。其基本思想是：找到一个超平面，使得两类数据点到该超平面的最小距离（间隔）最大化。
线性可分SVM：
对于数据 $(x_i, y_i)$，$y_i \in {-1, 1}$，寻找超平面 $w^T x + b = 0$ 使得：
$$y_i(w^T x_i + b) \geq 1, \quad \forall i$$
最大化间隔等价于最小化 $\frac{1}{2}|w|^2$：
$$\min_{w,b} \frac{1}{2}|w|^2 \quad \text{s.t.} \quad y_i(w^T x_i + b) \geq 1 \tag{2-28}$$
软间隔SVM：
当数据不完全线性可分时，引入松弛变量 $\xi_i \geq 0$：
$$\min_{w,b,\xi} \frac{1}{2}|w|^2 + C\sum_{i=1}^{n} \xi_i$$
$$\text{s.t.} \quad y_i(w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0$$
$C$ 是惩罚参数，$C$ 越大，对误分类的惩罚越重，模型越复杂。
核方法（Kernel Trick）：
当数据线性不可分时，通过映射 $\phi(x)$ 将数据映射到高维空间，在高维空间中寻找线性超平面。通过核函数 $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$，不需要显式计算 $\phi(x)$。
常用核函数：
- 线性核：$K(x_i, x_j) = x_i^T x_j$
- 多项式核：$K(x_i, x_j) = (x_i^T x_j + c)^d$
- RBF（高斯核）：$K(x_i, x_j) = \exp(-\gamma|x_i - x_j|^2)$
- Sigmoid核：$K(x_i, x_j) = \tanh(\kappa x_i^T x_j + \theta)$
对偶问题：
通过拉格朗日乘子法，原问题转化为对偶问题：
$$\max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j K(x_i, x_j)$$
$$\text{s.t.} \quad \sum_{i=1}^{n} \alpha_i y_i = 0, \quad 0 \leq \alpha_i \leq C$$
决策函数：$f(x) = \text{sign}\left(\sum_{i=1}^{n} \alpha_i y_i K(x_i, x) + b\right)$
支持向量：满足 $\alpha_i > 0$ 的样本。只有支持向量影响最终的决策边界，其他样本对模型没有影响。
SVM的优缺点：
- 优点：泛化能力强，高维数据有效，核方法灵活
- 缺点：大规模数据训练慢，核函数和参数选择需要经验，不直接给出概率