5. 线性判别函数

支持向量机(SVM)的数学推导

支持向量机是一种基于统计学习理论的机器学习方法，其核心思想是寻找一个最优超平面，使得不同类别之间的间隔最大化。

1. 硬间隔SVM的数学表述

1.1 问题设定

设训练样本集为 ，其中：

• 是 维特征向量
• 是类别标签

假设数据线性可分，我们要找到一个超平面 将两类数据分开。

1.2 几何间隔与函数间隔

函数间隔：点 到超平面的函数间隔定义为：

几何间隔：点 到超平面的几何间隔定义为：

数据集关于超平面的几何间隔为：

1.3 最大间隔问题的原始形式

SVM的目标是最大化几何间隔，即：

为了简化计算，我们可以固定函数间隔 （通过重新缩放 和 实现），原问题等价于：

2. 拉格朗日对偶方法求解

2.1 拉格朗日函数

引入拉格朗日乘子 ，构造拉格朗日函数：

其中 。

2.2 KKT条件

根据KKT(Karush-Kuhn-Tucker)条件，最优解 必须满足：

1. 平稳性条件：

2. 原始可行性：

3. 对偶可行性：

4. 互补松弛条件：

2.3 对偶问题推导

从平稳性条件得到：

将这些条件代入拉格朗日函数，消除 和 ，得到对偶问题：

2.4 支持向量的确定

从互补松弛条件可知：

• 如果 ，则 ，样本 是支持向量
• 如果 ，则 ，样本 不是支持向量

3. 软间隔SVM

3.1 引入松弛变量

当数据不完全线性可分时，引入松弛变量 ：

其中 是正则化参数，控制对错误分类的惩罚程度。

3.2 软间隔SVM的对偶问题

构造拉格朗日函数：

通过KKT条件求解，得到软间隔SVM的对偶问题：

与硬间隔SVM相比，唯一的区别是约束条件从 变为 。

4. KKT求解的具体例子

4.1 简单二维例子

考虑一个简单的二维线性可分问题：

训练数据：

• 正类：，
• 正类：，
• 负类：，

4.2 对偶问题求解

对偶问题为：

计算内积：

目标函数：

4.3 利用约束条件简化

由约束条件 ，得 。

代入目标函数并化简：

4.4 求解最优解

对 和 求偏导并令其为零：

解得：

4.5 计算最优参数

权重向量：

偏置项：利用支持向量上的约束条件 。

4.6 KKT条件验证

最优解必须满足所有KKT条件：

1. 平稳性： ✓
2. 原始可行性： 对所有 成立 ✓
3. 对偶可行性： 对所有 成立 ✓
4. 互补松弛：由于所有 ，所有样本都是支持向量，满足 ✓

5. 决策函数

求解完成后，SVM的决策函数为：

只有支持向量（ 的样本）对决策函数有贡献，这体现了SVM的稀疏性特点。

6. 核化SVM

对于非线性问题，通过核函数 将原始特征空间映射到高维特征空间，对偶问题变为：

决策函数变为：

KKT条件和求解方法保持不变，只是将内积 替换为核函数 。