一、支持向量机的分类

支持向量机可以分为：线性可分支持向量机、线性支持向量机、非线性支持向量机。

二、线性可分支持向量机

线性可分支持向量机中的线性可分是指：对于一个二分类问题，可以通过一个超平面将两个种类别完美分开。

我们的问题是：如何求解该超平面，做到间隔$\gamma$最大化？

给定训练集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$

求解最大几何间隔$max_{w,b}{\gamma}$且满足$y_i·(\frac{w}{||w||}·x_i+\frac{b}{||w||})\geq{\gamma},i=1,2,…,N$

或者求解函数间隔$max_{(w,b)}{\frac{r^-}{||w||}}$且满足$y_i·(w·x_i+b)\geq{\gamma^-},i=1,2,…,N$。我们的落脚点为函数间隔，因为函数间隔可以放大缩小，不影响超平面所在的位置，以便我们的求解。

令函数间隔$r^-=1$，则应用函数与间隔求解，则表示为：

$max_{(w,b)}{\frac{1}{||w||}}，且满足y_i·(w·x_i+b)\geq{1},i=1,2,...,N$

上式等价表示为：

$min_{(w,b)}\frac{1}{2}||w||^2，且满足y_i·(w·x_i+b)\geq{1},i=1,2,...,N$

上式存在不等式约束条件，我们使用拉格朗日函数进行最小值求解：

可以发现当满足约束条件$y_i·(w·x_i+b)\geq{1},i=1,2,…,N$时，拉格朗日函数后向恒小于等于零，即拉格朗日函数的最大值为：$\frac{1}{2}||w||^2$

$max_{\alpha}L(w,b,\alpha)=\begin{cases} \frac{1}{2}||w||^2 & 当满足不等式约束条件时 \\ \infty & 当不满足约束条件时 \end{cases}$

故我们的问题转化为求解：

$min_{(w,b)}max_{\alpha}L(w,b,a)=min_{(w,b)}\frac{1}{2}||w||^2$

称该问题为原始问题。

称

$max_{(\alpha)}min_{(w,b)}L(w,b,a)$

为对偶问题。

之所以提出对偶问题是因为原始问题虽然与我们支持向量机的求解直接相关，但是原始问题的求仍然很难，所以我们要利用对偶问题进行求解。但一般来说，二者并不等价。

可见原始问题总是小于等于对偶问题，即：

$min_{(w,b)}max_{(\alpha)}L(w,b,a){\leq}max_{(\alpha)}min_{(w,b)}L(w,b,a)$

我们需要加上相等的条件。

上面指出，在满足KKT条件下，原始问题与对偶问题等价。