主页 > IT百科 > 机器学习之四:支持向量机推导
2014年05月21日

机器学习之四:支持向量机推导

一、支持向量机(SVM)

支持向量机,�是用于解决分类问题。为什么叫做支持向量机,���后面的内容再做解释,�������这里先跳过。

在之前《逻辑回归》的文章中,��我们讨论过,��对于分类问题的解决,就是要找出一条能将数据划分开的边界。

对于不同的算法,其定义的边界可能是不同的,对于SVM算法,是如何定义其边界的?其定义方法有什么优点?将是下面要讨论的内容。

1、哪个模型更优

先来讨论一个二分类问题。

数据样本如下图所示:

image

其可能的划分边界可能是如下图中的蓝线、红线:

image

图中的蓝、红两种分类边界,都能达到分类的效果,但是哪一个效果更优?

评判一个模型的优劣,最主要的,是其对样本的泛化能力。

若有一个新样本,其二维特征位置,如下图蓝色方块所示:

image

两个模型,所得到的结果,显然是各不相同的,但从聚类的情况来看,该样本更偏向于“圆”的分类。

也就是说,蓝色边界所表示的模型,更有代表性。

而它,也是SVM算法所得到的模型。从直观上看,SVM确定的边界,刚好在两类样本的“中间”位置,不偏不倚

下面接着讨论,SVM是如何确定边界的。

2、支持向量机

支持向量机的基本思想是:找到集合边缘上的若干数据(称为支持向量),用这些点找出一个平面(称为决策面),使得支持向量到该平面的距离最长。

该算法,依靠支持向量来求解边界,支持向量机这个名字,也来源于此。

以上面的样本为例,解释SVM的步聚,如下图:

image

如下两步:

  • 找到两类样本边缘的若干个样本点,如上图中圈起来的三个样本

  • 由上面的样本点,找到一个决策平面,该平面与两类样本的向量距离最长

综上所述,虽然还未涉及SVM的具体运算,但可以初步看出,支持向量机有如下优点:

  • 计算量少。只使用了支持向量进行计算,而其他距离边界很远的点,其特征很明显,不会引起歧义,不用参与计算。

  • 泛化能力好。因其定义的边界,距离正负样本距离是最长的,具备良好的区分效果。

二、SVM推导

本节,将讨论SVM寻找决策面的数学推理过程。

根据数据集的属性,可以将这个问题分为两个层次:

  • 线性可分:数据分布简单,如上面的例子。可以找到一个超平面,直接在原始空间中将数据进行切分。

  • 线性不可分:数据分布复杂,不存在这样的超平面,则通过将原始空间映射到一个高维空间,在高维空间对数据进行划分。

1、线性可分决策面

线性可分是一个最简单的分类问题,下面做推导。

1.1、首先是样本集

\[ {(x_1,y_1),(x_2,y_2),...,(x_n,y_n)} \]

其中,\(y\) 的取值为 {+1,−1}。

1.2、决策面方程

从第一节知道,分类的手段是取得一个符合条件的决策平面。

平面可以用方程表示:

\[ w^Tx + b = 0 \]

那么问题的解决,则转化为找到符合条件的 \(w\)\(b\),条件是:使得数据集边缘若干点,到这个平面的距离是最长的。

因两类数据分布在决策平面的两侧,所以,\(y = -1\) 的样本点所在区域可表示为:

\[w^Tx + b < 0\]

同理, \(y = +1\) 的样本点所在区域为:

\[w^Tx + b > 0\]

那么支持向量所在的平面可以表示为:

\[w^Tx + b = \pm A\]

在后面的优化中,其实\(A\)的值为多少,并不影响结果,为了方便计算,令 \(A = 1\),即:

\[w^Tx + b = \pm 1\]

如下图所示:

image

1.3、计算最长距离

有了决策平面,接下来便是要计算支持向量到决策平台的距离,当该距离最长时所得到的参数,就是所需要的解。

由几何知识可知,点到平面的距离可以表示为:

\[ \gamma = \frac{w^Tx+b}{{||w||}} \]

此距离称为几何距离,存在正负。

而算法的目标,就是找到一个集合 \(x\) (支持向量),使得 \(\gamma\) 的值最小。

\(y\) 的取值为{+1,−1},所以上式可以乘上一个 \(y\),使该距离恒为正。

所以最大距离可表示为:

\[ \gamma_{max} = max({\frac{y(w^Tx+b)}{{||w||}}}) \]

结合上一节的假设,支持向量所在方程:

\[ w^Tx + b = \pm 1 \]

故而

\[ y(w^Tx+b) = 1 \]

则最大距离简化为

\[ \gamma_{max} = max({\frac{1}{{||w||}}}) \]

求解上式最大值,等同于求解下式的最小化值

\[ min({\frac{1}{{2}}}||w||^2) \]

这里增加了一个1/2系数、和一个平方,是为了方便求导。一求导两者就相消了。

这个式子有还有一些限制条件,完整的写下来,应该是这样的:

\[ min({\frac{1}{{2}}}||w||^2),s.t,y(w^Tx+b)\geq1 \]

s.t.后面的限制条件可以看做是一个凸多面体,我们要做的就是在这个凸多面体中找到最优解。

求解该式,可以用拉格朗日乘子法去解,使用了KKT条件的理论。

1.4、求最优解

对于具体的求解理论,这里不进行讨论,直接给出待求解式子的拉格朗日目标函数,如下,目标是让 $L(w,b,a) $ 针对 $ a $ 达到最大值:

\[ L(w,b,a) =\frac{1}{{2}}||w||^2-\sum_{i=1}^n \alpha_i(y_i(w^Tx+b)-1) \]

如何求解?

\(L\) 是关于 \(w、b、a\) 三个变量的函数,要得到使得 \(L\) 最大的 \(a\),需进行两步操作:

  • 首先需要先排除掉 \(w\)\(b\) 的影响,\(L\)关于\(w、b\) 最小化。如此一来,不管 \(w、b\) 如何改变,\(L\) 都不会再变小

  • 接着再让 \(L\) 关于 \(a\) 取最大值

(1)求\(L\) 关于 \(w、b\) 最小值

在可导的情况下,极值在导数为0的位置。于是令 \(L\) 关于 \(w、b\) 的偏导数为0,即:

\[ \frac{\partial L}{\partial w} = 0 \]

\[ \frac{\partial L}{\partial b} = 0 \]

求解上面的导数,得到:

\[ w=\sum_{i=1}^n\alpha_iy_ix_i \]

\[ \sum_{i=1}^n\alpha_iy_i = 0 \]

将上两式代入 $L(w,b,a) $,得到对偶问题的表达式:

\[ L(w,b,a) =\frac{1}{{2}}\sum_{i=1}^n\alpha_i - \frac{1}{{2}}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx^T_ix_j \]

于是新的目标问题及限制条件为(对偶问题):

\[ \begin{cases} max_a(\sum_{i=1}^n\alpha_i - \frac{1}{{2}}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx^T_ix_j) \\ \\ s.t.,\alpha \geq0,i=1,2,...,n \\ \\ \sum_{i=1}^n\alpha_iy_i = 0 \end{cases} \]

这个就是我们需要最终优化的式子,只关于 \(α\) 向量的式子。

(2) L关于 \(α\) 的最大值

上式最终的对偶问题,是一个凸二次规划问题,理论上用任何一个解决凸二次规划的软件包都可以解决。

一般使用SMO算法,输入是样本,输出是 \(a\)

SMO基本思想是,不断执行如下两个步骤,直至收敛:

  • 选取一对参数\((\alpha_i,\alpha_j)\)

  • 固定 \(\alpha\) 向量的其他参数,将\((\alpha_i,\alpha_j)\)代入上述表达式进行求最优解获得更新后的\((\alpha_i,\alpha_j)\)

解出 \(a\) 后,\(w、b\)也就确定下来,进而能得到决策面。

具体的SMO算法细节,有些超过本文的定位,就不在此处展开。

2、线性不可分决策面

上面讨论了线性可分的数据集的处理方式。但是,实际应用中的数据样本,可能更多的是线性不可分的,即不能找到一个可以将数据分类的超平面。

这种情况下,一般使用核函数将原始空间映射到一个高维空间,在高维高间对数据进行划分。理论上只要维度足够高,那么总能做到分类。

2.1 决策面方程

在线性可分的基础上,将样本 \(x\),进行一次变换,得到\(\phi(x)\)

超平台变为:

\[ w^T\phi(x) + b = 0 \]

2.2 求最优解

整个推理过程,与线性可分的基本一样,唯一不同的,是将各个公式化中的 \(x\),换成 \(\phi(x)\)

即得到对遇问题:

\[ \begin{cases} max_a(\sum_{i=1}^n\alpha_i - \frac{1}{{2}}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)) \\ \\ s.t.,\alpha \geq0,i=1,2,...,n \\ \\ \sum_{i=1}^n\alpha_iy_i = 0 \end{cases} \]

令:

\[ \phi(x_i)^T\phi(x_j) = K(x_i,x_j) \]

这个式子所做的事情就是将线性的空间映射到高维的空间,K函数有很多种,下面是比较典型的两种:

  • 多项式核

\[ K(x_i,x_j) = (x_i.x_j+1)^d \]

  • 高斯核

\[ K(x_i,x_j) = exp(-\frac{(x_i-x_j)^2}{2\sigma^2}) \]

最后一样能通过各类软件包,例如SMO,实现求解。