支持向量机

这个是真的难，反正我没看懂

导论：从“能分开”到“分得最稳”

感知机（Perceptron）只要找到一条能分开数据的超平面就停下，但这样的超平面有无穷多条。
SVM 的哲学是：不仅要分开，还要让两类之间的“路”尽可能宽。
这条“路”的宽度叫 间隔（Margin）。落在路边界上的样本叫 支持向量（Support Vectors）——它们唯一决定了这条路的走向。

一句话概括 SVM：
在特征空间中寻找一个最大间隔超平面，使得最近的不同类样本到它的距离最大化。

第一部分：硬间隔 SVM —— 理想世界的最大间隔

1.1 几何直观

设超平面为：

w^{T} x + b = 0

样本 $x_{i}$ 到超平面的有符号距离为：

\frac{w^{T} x_{i} + b}{∥ w ∥}

对于二分类 $y_{i} \in {- 1, + 1}$ ，要求正确分类且位于间隔外：

y_{i} (w^{T} x_{i} + b) \geq 1

此时最近点到超平面的距离为：

\frac{1}{∥ w ∥}

因此间隔宽度为：

\frac{2}{∥ w ∥}

最大化间隔等价于最小化 $∥ w ∥$ 。

1.2 严格定义（硬间隔原问题）

min_{w, b} \frac{1}{2} ∥ w ∥^{2}

s.t. y_{i} (w^{T} x_{i} + b) \geq 1, i = 1, \dots, N

这是一个 凸二次规划（QP） 问题，有唯一全局最优解。

1.3 支持向量

满足 $y_{i} (w^{T} x_{i} + b) = 1$ 的样本就是支持向量。
只有它们对应的拉格朗日乘子 $α_{i} > 0$ ，其余样本 $α_{i} = 0$ 。
SVM 的解只依赖支持向量，与其余样本无关——这是它抗过拟合、适合小样本的核心原因。

第二部分：软间隔 SVM —— 现实世界的妥协

现实数据往往线性不可分，或存在噪声。硬间隔会过拟合，甚至无解。
引入 松弛变量（Slack Variables） $ξ_{i} \geq 0$ ，允许少量样本越界：

min_{w, b, ξ} \frac{1}{2} ∥ w ∥^{2} + C \sum_{i = 1}^{N} ξ_{i}

s.t. y_{i} (w^{T} x_{i} + b) \geq 1 - ξ_{i}, ξ_{i} \geq 0

$C > 0$ 是惩罚系数：
- $C$ 大 → 更不容忍错分，间隔窄，易过拟合。
- $C$ 小 → 更容忍错分，间隔宽，偏欠拟合。

2.1 合页损失（Hinge Loss）视角

软间隔 SVM 等价于：

min_{w, b} \frac{1}{2} ∥ w ∥^{2} + C \sum_{i = 1}^{N} max (0, 1 - y_{i} (w^{T} x_{i} + b))

合页损失只惩罚“分类不够自信”的样本。
与逻辑回归的交叉熵损失相比，合页损失在 $y_{i} f (x_{i}) > 1$ 后梯度为零，因此解更稀疏——只有支持向量影响模型。

第三部分：对偶问题与核技巧 —— SVM 的灵魂

3.1 拉格朗日对偶

引入乘子 $α_{i} \geq 0$ ，构造拉格朗日函数并求极小，得到对偶问题：

max_{α} \sum_{i = 1}^{N} α_{i} - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} x_{i}^{T} x_{j}

s.t. 0 \leq α_{i} \leq C, \sum_{i = 1}^{N} α_{i} y_{i} = 0

最终判别函数：

f (x) = sign (\sum_{i = 1}^{N} α_{i} y_{i} x_{i}^{T} x + b)

关键观察：对偶形式中只出现样本间的内积 $x_{i}^{T} x_{j}$ 。

3.2 KKT 条件与支持向量

$α_{i} = 0$ ：样本被正确分类且在间隔外，非支持向量。
$0 < α_{i} < C$ ：样本在间隔边界上，是支持向量。
$α_{i} = C$ ：样本在间隔内或被错分，也是支持向量。

3.3 核技巧（Kernel Trick）

将内积替换为核函数：

K (x_{i}, x_{j}) = ϕ (x_{i})^{T} ϕ (x_{j})

无需显式计算高维映射 $ϕ (x)$ ，直接计算核函数即可。
常见核函数：

核函数	表达式	特点
线性核	$x_{i}^{T} x_{j}$	高维稀疏数据，文本分类
多项式核	$(x_{i}^{T} x_{j} + c)^{d}$	捕捉特征交互
RBF / 高斯核	$\exp (- γ \| x_{i} - x_{j} \|^{2})$	最常用，无限维映射
Sigmoid 核	$\tanh (γ x_{i}^{T} x_{j} + r)$	类似神经网络

Mercer 定理：核矩阵半正定是核函数合法的充要条件。

第四部分：SMO 与工程实践

4.1 SMO 算法思想

对偶问题有 $N$ 个变量，直接求解代价高。
SMO（Sequential Minimal Optimization） 每次只选两个变量 $α_{i}, α_{j}$ 优化，其余固定。
因为约束 $\sum α_{i} y_{i} = 0$ ，两个变量可解析求解。
重复直到收敛。这是 libsvm / sklearn 的底层算法。

4.2 sklearn 工程模板

python

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV

# 关键：SVM 对特征尺度极其敏感，必须先标准化
pipe = make_pipeline(StandardScaler(), SVC(kernel='rbf', class_weight='balanced'))

param_grid = {
    'svc__C': [0.1, 1, 10, 100],
    'svc__gamma': ['scale', 0.01, 0.1, 1]
}

grid = GridSearchCV(pipe, param_grid, cv=5, scoring='f1_macro')
grid.fit(X_train, y_train)

4.3 调参法则

必须标准化：SVM 基于欧氏距离，量纲不同会毁掉间隔。
RBF 核：先调 $C$ 和 $γ$ 。
- $C$ 越大，模型越复杂。
- $γ$ 越大，每个样本影响范围越小，越容易过拟合。
类别不平衡：设置 class_weight='balanced'，或手动指定字典。
概率输出：SVC 默认不输出概率，需 probability=True，但会内部做 Platt 校准，训练变慢。
大数据：核 SVM 训练复杂度 $O (N^{2})$ 到 $O (N^{3})$ ，超过几万样本建议用 LinearSVC 或转向树模型/神经网络。

第五部分：多分类与回归

5.1 多分类

SVM 原生是二分类。常用策略：

OvO（One-vs-One）：每两类训练一个分类器，投票决定。libsvm 默认，适合类别多但样本少。
OvR（One-vs-Rest）：每类对剩余类训练一个分类器，取最大决策值。
DAG-SVM：有向无环图，减少测试时间。

5.2 SVR（支持向量回归）

将间隔思想搬到回归：允许预测值落在 $f (x) \pm ϵ$ 的“管道”内，不计损失。
优化：

min \frac{1}{2} ∥ w ∥^{2} + C \sum_{i = 1}^{N} (ξ_{i} + ξ_{i}^{*})

s.t. y_{i} - f (x_{i}) \leq ϵ + ξ_{i}, f (x_{i}) - y_{i} \leq ϵ + ξ_{i}^{*}

只有管道外的样本才是支持向量。SVR 对异常值鲁棒，但同样对核与参数敏感。

第六部分：宏观对比与选型法则

维度	SVM	逻辑回归	树模型（XGBoost/LGBM）	神经网络
数据规模	小样本（< 10 万）	中小规模	中大规格	大规模
特征维度	高维稀疏表现好	高维表现好	中高维	高维需嵌入
非线性	核技巧	需手动构造	天然非线性	天然非线性
可解释性	支持向量可解释	系数可解释	特征重要性	黑箱
类别不平衡	`class_weight` + 调阈值	权重 + 阈值	`scale_pos_weight`	损失加权
训练速度	慢（核）	快	快	慢
概率输出	需校准	天然概率	天然概率	天然概率

选型决策树（工程口诀）：

样本量小、维度高、线性不可分 → RBF-SVM。
样本量大、追求速度与精度 → LightGBM / XGBoost。
需要概率输出与在线学习 → 逻辑回归 / SGD。
图像、语音、文本大模型 → 深度学习。
类别不平衡且漏报代价高 → SVM + class_weight='balanced' + 阈值向召回倾斜（F2）。

结语：SVM 的遗产

SVM 是统计学习理论的巅峰之作：

最大间隔 给出了泛化误差上界；
对偶与核技巧 让线性模型拥有非线性表达能力；
支持向量 揭示了“少即是多”的稀疏智慧。

尽管在超大规模数据上已被深度学习与集成树取代，但 SVM 的思想——间隔、对偶、核、稀疏性——仍然渗透在现代机器学习的血脉中。理解 SVM，就是理解“如何在有限样本下寻找最稳的决策边界”。

一句话记住 SVM：
用核函数把数据映射到高维，在那里找一条最宽的路；路上站着的，就是支持向量。

hdu6035 Colorful Tree

AT_dp_u Grouping

AT_dp_v Subtree

FFT

P1002 [NOIP 2002 普及组] 过河卒

P1014 [NOIP 1999 普及组] Cantor 表

P1792 [国家集训队] 种树

P2014 [CTSC1997] 选课

P2748 [USACO16OPEN] Landscaping P

P4025 [PA 2014] Bohater

P5985 [PA 2019] Muzyka pop

P6691 选择题

支持向量机

导论：从“能分开”到“分得最稳”

第一部分：硬间隔 SVM —— 理想世界的最大间隔

1.1 几何直观

1.2 严格定义（硬间隔原问题）

1.3 支持向量

第二部分：软间隔 SVM —— 现实世界的妥协

2.1 合页损失（Hinge Loss）视角

第三部分：对偶问题与核技巧 —— SVM 的灵魂

3.1 拉格朗日对偶

3.2 KKT 条件与支持向量

3.3 核技巧（Kernel Trick）

第四部分：SMO 与工程实践

4.1 SMO 算法思想

4.2 sklearn 工程模板

4.3 调参法则

第五部分：多分类与回归

5.1 多分类

5.2 SVR（支持向量回归）

第六部分：宏观对比与选型法则

结语：SVM 的遗产

支持向量机 ​

导论：从“能分开”到“分得最稳” ​

第一部分：硬间隔 SVM —— 理想世界的最大间隔 ​

1.1 几何直观 ​

1.2 严格定义（硬间隔原问题） ​

1.3 支持向量 ​

第二部分：软间隔 SVM —— 现实世界的妥协 ​

2.1 合页损失（Hinge Loss）视角 ​

第三部分：对偶问题与核技巧 —— SVM 的灵魂 ​

3.1 拉格朗日对偶 ​

3.2 KKT 条件与支持向量 ​

3.3 核技巧（Kernel Trick） ​

第四部分：SMO 与工程实践 ​

4.1 SMO 算法思想 ​

4.2 sklearn 工程模板 ​

4.3 调参法则 ​

第五部分：多分类与回归 ​

5.1 多分类 ​

5.2 SVR（支持向量回归） ​

第六部分：宏观对比与选型法则 ​

结语：SVM 的遗产 ​

支持向量机

导论：从“能分开”到“分得最稳”

第一部分：硬间隔 SVM —— 理想世界的最大间隔

1.1 几何直观

1.2 严格定义（硬间隔原问题）

1.3 支持向量

第二部分：软间隔 SVM —— 现实世界的妥协

2.1 合页损失（Hinge Loss）视角

第三部分：对偶问题与核技巧 —— SVM 的灵魂

3.1 拉格朗日对偶

3.2 KKT 条件与支持向量

3.3 核技巧（Kernel Trick）

第四部分：SMO 与工程实践

4.1 SMO 算法思想

4.2 sklearn 工程模板

4.3 调参法则

第五部分：多分类与回归

5.1 多分类

5.2 SVR（支持向量回归）

第六部分：宏观对比与选型法则

结语：SVM 的遗产