一.理论基础

一.支持向量机分类

SVM 是一种二分类模型，包含三种类型：线性可分支持向量机，线性支持向量机以及非线性支持向量机；

线性可分支持向量机：当训练数据可分时，通过硬间隔最大化，学习一个线性的分类器
线性支持向量机：当训练数据近似线性可分时，通过软间隔最大化，学习一个线性的分类器，即线性支持向量机，有又称为软间隔支持向量机
非线性支持向量机：当训练数据线性不可分时，通过使用核技巧以及软件个最大化

二.函数间隔与几何间隔

函数间隔：对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点 $x_i,y_i)$ 的函数间隔为
$\hat{\gamma}_i = y_i(w\cdot{x_i} + b)$
定义超平面（w,b）关于训练集T的函数间隔所有样本点的函数间隔最小值，即： $\hat{\gamma}= \max \limits_{i=1,.....,N} \hat{\gamma}_i$

几何间隔：对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点 $x_i,y_i)$ 的几何间隔为
$\gamma_i = y_i(\frac{w}{||w||_2}\cdot{x_i} + \frac{b}{||w||_2})$

定义超平面（w,b）关于训练集T的几何间隔所有样本点的几何间隔最小值，即： $\gamma= \max \limits_{i=1,.....,N} \gamma_i$

三.支持向量

如下图所示，分离超平面为wTx+b=0。和超平面平行的保持一定的函数距离的这两个超平面对应的向量，我们定义为支持向量，如下图虚线所示。支持向量到超平面的距离为 $\frac{1}{||w||_2}$ ,两个支持向量之间的距离为 $\frac{2}{||w||_2}$
在这里插入图片描述

四.线性可分支持向量机

4.1 线性可分支持向量机的优化函数

SVM 的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。这个可以表示为约束最优化问题：

$\max \limits_{w,b} \gamma$
$s.t.\ \ \ \gamma_i = y_i(\frac{w}{||w||_2}\cdot{x_i} + \frac{b}{||w||_2}) \geq \gamma \ \ i={1,2......,N}$

考虑到几何间隔和函数间隔的关系，上面约束最优化问题可以表示成：
$\max \limits_{w,b} \frac{\hat\gamma}{||w||_2}$
$s.t.\ \ \ \hat{\gamma}_i= y_i(w\cdot{x_i} + b) \geq \hat\gamma \ \ i={1,2......,N}$

通常这里取 $\hat\gamma=1$ ，最大化 $\frac{1}{||w||_2}$ 和最小化 $\frac{1}{2}||w||^{2}_2$ 等价。

SVM的优化函数等价于

$\min\limits_{w,b} \frac{1}{2}||w||^{2}_2$
$s.t.\ \ \ \hat{\gamma}_i= y_i(w\cdot{x_i} + b) - 1\geq 0 \ \ i={1,2......,N}$

4.2 线性可分支持向量机的最优化问题求解

4.2 .1 线性可分支持向量机的最优化问题转化成对偶最优化问题

目标函数 $\frac{1}{2}||w||^{2}_2$ 为凸函数，同时约束条件不等式是仿函数；可以通过拉格朗日函数将目标函数转化成无约束的优化函数：
在这里插入图片描述
引入拉格朗日乘子后，我们的优化目标变成：
$\min\limits_{w,b}\max\limits_{a_i \geq 0} L(w,b,\alpha)$
其对偶问题为极大值极小值问题：
$\max\limits_{a_i \geq 0} \min\limits_{w,b}L(w,b,\alpha)$