线性可分支持向量机要求数据是线性可分的

函数间隔vs几何间隔

样本点到超平面的函数间隔

$$ \hat{\gamma}_i=y_i\left(w\cdot x_i+b\right) $$

训练数据集到超平面的函数间隔

$$ \hat{\gamma}=\min_{i}y_i\left(w\cdot x_i+b\right) $$

样本点到超平面的几何间隔

$$ \gamma_i=\frac{1}{||w||}y_i\left(w\cdot x_i+b\right) $$

训练数据集到超平面的几何间隔

$$ \gamma=\min_{i}\frac{1}{||w||}y_i\left(w\cdot x_i+b\right) $$

支持向量机的优化问题

所有样本点到超平面的几何距离最远

$$ \begin{aligned}\max_{w,b} &\ \gamma\\\text { s.t } & y_i\left(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}\right)\geq\gamma(\forall i=1,2, \ldots n)\end{aligned} $$

同理为

$$ \begin{aligned}\max_{w,b} & \frac{\hat{\gamma}}{||w||}\\\text { s.t } & y_i\left(w\cdot x_i+b\right)\geq\hat{\gamma}(\forall i=1,2, \ldots n)\end{aligned} $$

由于函数间隔的取值并不影响最优化问题，故取函数间隔为1，等价为

凸二次规划问题

$$ \begin{aligned}\min_{w,b} & \frac{1}{2}||w||^2\\\text { s.t } & y_i\left(w\cdot x_i+b\right)-1\geq 0(\forall i=1,2, \ldots n)\end{aligned} $$

支持向量和间隔边界

支持向量满足

$$ y_i(w\cdot x_i+b)=1 $$

对于线性可分数据集，最大间隔分离超平面存在且唯一。

线性可分支持向量机学习算法（原始形式）

• 输入：线性可分训练数据集T
• 输出：最大间隔分类器和分类决策函数

1. 构造并求解约束最优化问题（凸二次规划问题）

   $$ \begin{aligned}\min_{w,b} & \frac{1}{2}||w||^2\\\text { s.t } & y_i\left(w\cdot x_i+b\right)-1\geq 0(\forall i=1,2, \ldots n)\end{aligned} $$

   得到最优解w*，b*

2. 得到分离超平面

   $$ w^*\cdot x+b=0 $$

   和分类决策函数

   $$ f(x)=sign(w^*\cdot x+b) $$

利用拉格朗日对偶性求解凸二次规划

引入拉格朗日乘子 𝛼_i≥0（i=1,2,…,N)

$$ L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^N\alpha_i\left[1-y_i(w\cdot x_i+b)\right] $$