0ec27782b015e085e00ae65e385e3919
支持向量机(Support Vector Machine)

1、前言

在之前我们介绍了线性回归算法以及其变种,LASSO回归、Ridge回归。他们是从减少过拟合的角度出发而得到的算法,而 SVM(支持向量机)则是优化原本线性回归算法中选择“分割线”,或者说选择分割超平面这样一个过程。
TAG:# 拉格朗日数乘子算法 # KKT条件

2、SVM的优点和缺点

  • 优点:泛化错误率低,计算开销不大,结果易解释
  • 缺点:对参数调节和核函数的选择敏感,原始分类器不加修改仅适用于处理二类问题。
  • 数据类型:数值型和标称型数据。

3、SVM算法原理

首先我们都知道,为了划分二维的数据需要一根线,划分三维数据需要一个面。这里线是一维,面是二维,同理继续推出对 N 维的数据需要使用 N-1 维的对象进行分割,线性回归和 SVM 本质都是通过找这个超平面来达到分类的效果。

具体的来说SVM是在优化线性回归中的 $kx+b$ 模型。在线性回归中只需要考虑有一个分割超平面能进行分类即可,而SVM则想找出所有能分类的分割超平面中最优的超平面,即所有点都到分割超平面的距离最大,而支持向量指的就是离超平面最近的那些点。

超平面的公式为公式 2.1。所以点 A 到分割超平面的距离为公式 2.2。这里我们为了方便计算引入类别标签为-1和+1。所以保证所有的最小间隔的点最大化的公式为公式 2.3。
注1:-1和+1是为了保证预测正确的时候,$y(x_i)label_i$都是一个很大的正值。*
注2:$arg\ max_{w,b}$的含义是,得到w和b使得后面式子取最大值
$$
y(x) = w^TX+b\ \ \ 公式2.1
$$

$$
\frac{|w^TX+b|}{||w||}\ \ \ 公式2.2
$$

$$
arg\ max_{w,b}\{min_i(label_i*(w^Tx_i+b) * \frac{1}{||w||})\}\ \ \ 公式2.3
$$

显然我们不能直接求解上面的式子。需要化简下它。首先由于公式2.1在正确预测时,同 $label$ 的乘积大于 1。所以我们可以拆分公式2.3为公式2.4和约束条件公式2.5。
注:这里的约束条件公式2.5中,要对每一个式子前都要加系数,即拉格朗日数乘子$\alpha_i$
$$
arg\ min_{w,b}\ ||w||\ \ \ 公式2.4
$$
$$
st.\ \ label_i*(w^Tx_i+b) \geq 1 \ \ \ 公式2.5
$$
对为了方便求导计算在公式 2.4 前加上$\frac{1}{2}$这个系数。之后使用拉格朗日乘子法得到公式2.6,并进行计算。根据KKT条件,让偏导数等于0得到公式2.7和公式2.8。
*注:这里需要注意的是拉格朗日数乘子的正负号,这个同不等式的符号有关*

$$
L(w,b,\alpha)= \frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i* [label_i*(w^Tx_i+b)-1]\ \ \ 公式2.6
$$
$$
\sum_{i=1}^{n}\alpha_i label_i x_i = w\ \ \ 公式2.7
$$
$$
\sum_{i=1}^{n}\alpha_i label_i = 0\ \ \ 公式2.8
$$
将公式2.7,公式2.8代入公式2.6化简,再根据对偶问题得到最终公式2.9,根据KKT,其约束条件为公式2.10。

注1:KKT条件在SMO算法中统一进行讲解。
注2:b是由公式2.8消掉的。
注3:在拉格朗日乘子法应用在这里,我们可以把$||w||$,写作$max_\alpha\ L(w,b,\alpha)$,所以原式可以写作$min_{w,b}\ max_\alpha\ L(w,b,\alpha)$,根据对偶问题,就可以变成$max_\alpha\ min_{w,b}\ L(w,b,\alpha)$,这也是能把公式2.7和公式2.8代入公式2.6的原因,也是公式2.9种是$max_\alpha$的原因。具体证明在KKT中的附上的博客中。
$$
max_\alpha\ \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{m}label_i * label_j * a_i * a_j\langle x_i·x_j\rangle\ \ \ 公式2.9
$$

$$
\alpha_i \geq 0\ \ 且\ \sum_{i=1}^{m}\alpha_i*label_i = 0\ \ \ 公式2.10
$$

注:这里$\langle x_i·x_j\rangle$是两者向量积的运算,是从$x_i^T * x_j$得到的。

这么看来我们算出了$\alpha$就能算出超平面,所以SVM的工作就是算出这些$\alpha$,而SMO算法就是求$\alpha$的典型算法。

4、对SVM引入线性不可分

由于数据都不那么干净,所以我们不应该假设数据能够100%的线性可分。我们通过对判定的公式,公式2.5,引入松弛变量$\xi_i\geq 0$,得到其引入了松弛因子的形式,如下公式3.1。
$$
y_i(w * x_i+b)\geq1-\xi_i\ \ \ 公式3.1
$$
同时对于目标函数公式2.4也需要调整,我们将$\xi$引入目标函数并对其设置权值,得到公式3.2,也因此其约束条件变为公式3.1,公式3.2。
$$
min_{w,b}\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i\ \ \ 公式3.2
$$
$$
\begin{split}
st.\ \ \ &y_i(w * x_i+b)\geq 1 - \xi_i\\
&\xi \geq 0
\end{split}
$$
故拉格朗日函数$L(w,b,\xi,\alpha,\mu)$为如下公式3.3,其中$\alpha$,$\mu$为拉格朗日数乘子。
$$
L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^n\alpha_i * [label_i*(w^Tx_i+b)-1+\xi_i]-\sum_{i=1}^n\mu_i\xi_i\ \ \ 公式3.3
$$
和之前的操作一样,对其进行求偏导操作后,类似的得到了相同的公式2.7,公式2.8,不同的是这里对$\xi$的求到后对$\alpha$有了限制,得到了公式3.4,由于$\mu\geq0$所以有$\alpha_i$的取值范围$0 \leq \alpha_i \leq C$。
*注:注意这里的$\alpha$取值,之后SMO会用*

top Created with Sketch.