统计学习方法 第7章 支持向量机（1）

支持向量机 是一种二类分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器。支持向量机还包括了核技巧，使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划问题。

线性可分支持向量机

假设给定一个特征空间上的训练数据集

其中x_i为特征向量，y_i为±1，分别表示正类和负类。

若数据集是线性可分的，则通过间隔最大化学习得到的分离超平面为

以及相应的分类决策函数

称为线性可分支持向量机。

函数间隔和几何间隔

一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。w·x+b的绝对值可以表示远近，而它和y的符号是否一致能表示分类是否正确。因此函数间隔定义为

训练数据集的函数间隔为超平面关于所有样本点的函数间隔最小值

为避免成比例放大w和b导致超平面不变而函数间隔改变，引入几何间隔

训练数据集的几何间隔为超平面关于所有样本点的几何间隔最小值

间隔最大化

最大间隔分离超平面问题可以表示为约束最优化为题

或使用函数间隔

由于将w，b以及函数间隔同时放大λ倍，不影响该最优化为题的解，因此可取函数间隔为1，得到

得到一个凸二次规划问题。

线性可分训练数据集的最大间隔分离超平面是存在且唯一的。

训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量，即

H₁和H₂之间的距离称为间隔。

在决定分离超平面时只有支持向量起作用，其他实例点并不起作用。

学习的对偶算法

为了求解线性可分支持向量机的最优化为题，首先引入拉格朗日乘子构建拉格朗日函数

其中为拉格朗日乘子向量。

根据拉格朗日对偶型，原问题的对偶问题为

首先对w，b求极小

得到

代入得到

再求对α的极大，即对偶问题

即

线性可分支持向量机学习算法

1. 构造并求解约束最优化问题
   
   得到最优解α^*
2. 计算
   
   并选择α^*的一个正分量α^*_j，计算
   
3. 求得超平面
   
   和分类决策函数