机器学习11——支持向量机上

支持向量机上

理论引入

Learning Machines：什么是学习机器？

目标：学习一个映射关系

• 学习机器的任务是学习输入 ${\mathbf{x}}_i$ 到输出 $y_i$ 的映射关系：

$${\mathbf{x}}_i⟶y_i$$

学习机器模型的定义形式：

我们假设有一个函数模型来描述这个映射：
$$y=f(\mathbf{x},\mathbf{\alpha })$$
其中：

• $\mathbf{x}$：输入特征向量
• $f$：模型结构（如线性函数、神经网络、SVM 等）
• $\mathbf{\alpha }$：模型参数（如权重、偏置、核参数等）

学习本质：通过调整 $\mathbf{\alpha }$ 参数，使得 $f(\mathbf{x},\mathbf{\alpha })$ 更好地逼近真实标签 $y$。

Generalization vs. Learning：泛化 vs. 拟合

学习过程的本质：

• 通过参数的调整，对特征空间进行划分，从而实现分类或回归。
• 经典方法是：最小化经验风险（Empirical Risk）。

学到的内容是规则还是记忆？

• 学习机器可能：
  • 只记住样本（记忆训练数据）
  • 提取出一般规律（泛化能力）

问题在于，如果我们只最小化经验风险，机器是否真正学到了规律？

风险的定义与分析

期望风险（Expected Risk）：也称为泛化误差

$$R(\mathbf{\alpha })=\int \frac{1}{2}|y-f(\mathbf{x},\mathbf{\alpha })|dP(\mathbf{x},y)$$

• 这是机器在所有可能样本上的平均错误，是我们真正想要最小化的目标。
• 但问题是：$P(\mathbf{x},y)$ 是未知的分布，我们无法直接计算它。

经验风险（Empirical Risk）：也称为训练误差

$$R_{\text{emp}}(\mathbf{\alpha })=\frac{1}{2l}\sum _{i=1}^l\left|y_i-f({\mathbf{x}}_i,\mathbf{\alpha })\right|$$

• 我们能做的是在训练数据上计算平均误差，即经验风险。

问题是：

是否 $R(\mathbf{\alpha })\approx R_{\text{emp}}(\mathbf{\alpha })$？

Empirical Risk 的局限性

如何让经验风险趋近于 0？

只要我们使用一个具有强大记忆能力的模型（比如高阶多项式、深度神经网络），就可以拟合训练集，令经验风险非常小。

但这样做的隐患：

• 机器并不一定学到了规律。
• 有可能只是在死记硬背训练数据。
• 此时的泛化误差（Expected Risk）可能非常大。

这就导致了**过拟合（Overfitting）**问题。

结构风险最小化（SRM）理论

什么是 SRM？

目标：不仅最小化经验风险，还要控制模型的结构复杂度。

新的风险定义方式：

$$\text{Total Risk}=\underset{\text{拟合好训练数据}}{\underbrace{\text{Empirical Risk}}}+\underset{\text{模型复杂度引起的风险}}{\underbrace{\text{Structure Risk}}}$$

也可以理解为：
$$R_{\text{total}}=R_{\text{emp}}+\Omega (\text{模型复杂度})$$
其中 $\Omega$ 是对模型复杂度的惩罚函数（如正则化项 $\lambda ||\mathbf{w}|{|}^2$）

理解“结构”和“规则”

什么是结构？

结构是指模型的构成形式，比如：

• 模型的类型（线性/非线性、神经网络/SVM）
• 参数个数（维度）
• 模型复杂度（VC维、深度）

选择合适的结构是防止过拟合的关键。

什么是规则？

规则是模型从数据中提取出的可泛化的规律。好的规则能在新数据上也正确预测。

VC 维（Vapnik-Chervonenkis Dimension）

来源于统计理论，尤其是霍夫丁不等式，有关推导参考：

统计学习理论之VC维究竟是什么 | TangShusen

霍夫丁(Hoeffding)不等式 - _yanghh - 博客园 (cnblogs.com)

什么是 VC Dimension（VC维）？

基本定义：

VC 维是**衡量模型容量（复杂度）**的重要指标。

• 给定一个函数集合 $f(\mathbf{x},\alpha )$，其中 $f:{\mathbb{R}}^d\to -1,1$。
• 如果这个函数集合能够对某 $l$ 个样本点的所有 $2^l$ 种可能的标签进行完全分类，我们说这个集合**“shatter”这 $l$ 个点**。
• VC dimension 就是这个函数集合最多可以 shatter 的样本点数目。

换句话说，VC维越大，模型越“有能力”去记住数据的各种标签组合。

VC 维举例：二维空间中的有向直线

• 在线性分类器中，在 $R^2$ 中用一条有向直线进行二分类。
• 实验证明：最多可以打散任意3个点，但不能打散所有4个点的组合。

因此，二维空间中有向直线分类器的 VC 维为：

VC dimension = 3

一般结论：

• 在 ${\mathbb{R}}^n$ 中，超平面（linear classifiers）的 VC 维是：
  $$h=n+1$$

• 但注意：VC维 不等于参数个数！Vapnik (1995) 的一个例子中，只有 1 个参数的模型，却可以拥有无限 VC 维！

VC Dimension 与泛化误差的关系

回顾两个风险：

• 期望风险（Expected Risk）：在所有样本分布上的平均误差。
  $$R(\alpha )=\int \frac{1}{2}|y-f(\mathbf{x},\alpha )|dP(\mathbf{x},y)$$

• 经验风险（Empirical Risk）：在训练集上的平均误差。
  $$R_{\text{emp}}(\alpha )=\frac{1}{2l}\sum _{i=1}^l\left|y_i-f({\mathbf{x}}_i,\alpha )\right|$$

VC Confidence Bound（置信界）

Vapnik-Chervonenkis 理论提供了一个上界来衡量期望风险与经验风险之间的偏差：

对给定的置信度 $1-\eta$，有如下不等式成立：
$$R(\alpha )\le R_{\text{emp}}(\alpha )+\underset{\text{VC Confidence}}{\underbrace{\sqrt{\frac{h(\log (2l/h)+1)-\log (\eta /4)}{l}}}}$$
其中：

• $h$：模型的 VC 维
• $l$：训练样本个数
• $\eta$：置信失效概率（如 0.05）

含义解释：

• 第一项：经验风险
• 第二项：由模型复杂度 $h$ 和样本规模 $l$ 控制的置信项，表示“学习误差的上限偏移”

目标：在确保经验风险低的前提下，使VC 置信项也尽可能小。

结构风险最小化（Structure Risk Minimization, SRM）

回顾 SRM 原理

• 目标函数：
  $$\text{Total Risk}=R_{\text{emp}}+\text{VC Confidence}$$

• 不只最小化训练误差，更要控制模型复杂度（VC维）！

SRM 的实现方法：嵌套结构函数集

如图所示（见后两张图）：
$${\mathcal{F}}_1\subset {\mathcal{F}}_2\subset \cdots \subset {\mathcal{F}}_k$$

• 每个函数集合 ${\mathcal{F}}_i$ 都有不同的 VC 维 $h_i$；
• 在每个 ${\mathcal{F}}_i$ 中，最小化经验风险；
• 再在所有的 $i$ 中选择使得“总风险”最小的那个。

线性支持向量机（Linear SVM）

线性可分性（Linear Separability）

定义：

一组二分类数据点是线性可分的，当存在一个超平面（线）可以将正类与负类完全正确地分开，即没有误分类。

线性分类器如何选择最佳划分？

问题引出：

在所有可以正确分类的超平面中，哪个最好？

• 不同的线性分类器可能都能将数据分类正确（见图）。
• 但我们需要选择泛化能力最强的那个。

最大间隔分类器（Maximum Margin Classifier）

核心思想：

在所有能分开的超平面中，选择间隔（margin）最大的那个超平面。

几何定义：

对于数据点 $({\mathbf{x}}_i,y_i)$，若超平面由 $\mathbf{w}\cdot \mathbf{x}+b=0$ 定义，则：
$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$$
是支持向量机对线性可分数据的基本约束条件。按我的理解，正确分类的条件是（对于二分类）：$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 0$，即对于正样本（+1）预测为+1，对于负样本（-1）预测为-1。要求＞1即把条件变得更加苛刻。

$$\begin{array}{rl}\Rightarrow & \exists \mathbf{w},b\text{ such that }\\ & \mathbf{w}{\mathbf{x}}_i+b\ge +1\text{ for }{y}_i=+1\\ & \mathbf{w}{\mathbf{x}}_i+b\le -1\text{ for }{y}_i=-1\\ \equiv & y_i\left(\mathbf{w}{\mathbf{x}}_i+b\right)-1\ge 0\forall i\end{array}$$

为什么最大间隔是最优？

• 几何含义：最大化两个边界间的距离d（Margin is defined as the width that the boundary could be increased by before hitting a data point）

  推导如下：
  $$\begin{array}{rl}d& =\frac{1-b}{\Vert \mathbf{w}\Vert }-\frac{-1-b}{\Vert \mathbf{w}\Vert }\\ & =\frac{2}{\Vert \mathbf{w}\Vert }\end{array}$$

• 直觉解释：

  • 更大的间隔意味着模型对噪声和扰动更鲁棒。
  • 支持向量（离超平面最近的数据点）决定了边界，因此只“关注”关键点。
  • 理论上能带来更好的泛化能力（对应更小 VC 维）。

VC维与间隔的关系

理论结果：

假设所有数据点都被包含在半径为 $R$ 的球体中，间隔宽度为 $\gamma$，则支持向量机对应函数类的 VC 维 $h$ 满足：
$$h\le \min \left({\left(\frac{R}{\gamma }\right)}^2,d\right)+1$$
其中 $d$ 是输入空间维度。

含义解读：

• 更大的 margin（间隔） $\gamma$ 会降低 VC 维，从而减小泛化误差上界。
• 支持了结构风险最小化（SRM）的核心思想：在经验风险相同时，选择 VC 维更小（即 margin 更大的模型）。

SVM 优化目标与约束（Hard Margin SVM）

几何目标转化为优化问题：

最大化 margin 等价于最小化 $|\mathbf{w}|$，于是优化问题如下：

目标函数（Objective）：

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$$

约束条件（Constraints）：

$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1\forall i$$

这是一个标准的 凸二次规划问题，解这个问题需要使用 拉格朗日乘子法（Lagrange Multiplier）。