Created by potrace 1.13, written by Peter Selinger 2001-2015

支持向量机(SVM)

从分类问题到超平面

支持向量机其实是一个多维空间中的二分类问题.

在二维平面内,如果想将两个类别分开,只需要找到一条直线就可以了,在直线一边是一类,在直线另一边是另一类.直线的公式为:

Ax+By+C=0

如果是三维空间,我们需要通过一个面来区分两个类,所以得到面的公式

Ax+By+Cz+D=0

推广到n维空间,需要用一个超平面来区分两个类别,超平面的公式为:

Ax+By+Cz+...+b=0

这个公式可以写成矩阵 \omega=(A,B,C,...) 的转置与矩阵 x=(x,y,z,...) 相乘,所以超平面的公式为

\omega^{T}\cdot x+b=0

支持向量机就是寻找这样一个能够将两个类别分开的超平面.

image

距离平面最近的点被称为支持向量.

间隔

在超平面 \omega^{T}\cdot x+b=0 确定的情况下,可得点到平面的距离:

\gamma = \frac{|\omega^{T}x+b|}{||\omega||}

假设存在超平面能够对样本正确分类,设 y_i\in \{-1,1\} ,有:

\left\{ \begin{array} { l l } { \boldsymbol { w } ^ { \mathrm { T } } \boldsymbol { x } _ { i } + b \geqslant + c , } & { y _ { i } = + 1 } \\ { \boldsymbol { w } ^ { \mathrm { T } } \boldsymbol { x } _ { i } + b \leqslant - c , } & { y _ { i } = - 1 } \end{array} \right.

当样本为支持向量是取等号.

结合上面两个公式可得超平面两边的支持向量到超平面的距离之和为:

\gamma = \frac { 2c } { \| \boldsymbol { w } \| }

常量 c 可以放到 \| \boldsymbol { w } \| 里面,即通过缩放 \| \boldsymbol { w } \| 消掉 c :

\gamma = \frac { 2 } { \| \boldsymbol { w } \| }

欲找到最大间隔的超平面,即:

\begin{array} { l } { \max _ { \boldsymbol { w } , b } \frac { 2 } { \| \boldsymbol { w } \| } } \quad { \text { s.t. } y _ { i } \left( \boldsymbol { w } ^ { \mathrm { T } } \boldsymbol { x } _ { i } + b \right) \geqslant 1 , \quad i = 1,2 , \ldots , m } \end{array}

以上优化相当于:

\begin{array} { l } { \min _ { \boldsymbol { w } , b } \frac { 1 } { 2 } \| \boldsymbol { w } \| ^ { 2 } } \quad { \text { s.t. } y _ { i } \left( \boldsymbol { w } ^ { \mathrm { T } } \boldsymbol { x } _ { i } + b \right) \geqslant 1 , \quad i = 1,2 , \ldots , m } \end{array} \tag{1}

至此,我们已经将这个优化问题转换成为了一个带有约束条件的凸优化问题.已经可以通过一些算法,比如说梯度下降,来求的这个优化问题的解.

我们通过下图来理解一下此刻的优化问题.图中的点为函数f(x1,x2)的极致点,周围是等值线.h(x1,x2)为约束条件,优化问题的解为约束条件与等值线的切点.

image

但是,我们最开始是在数据是线性可分的条件下进行推导的.接下来让我们把这个优化问题推广到非线性.

低维空间到多维空间的映射

我们前面的讨论是在线性可分的前提下,也就是说可以通过一条线,或是一个平面将数据分开.那么如果数据是非线性的我们该如何区分两个类别呢?比如下面这幅图中的绿点和红点.

image

我们无法直接用一条直线来区分两种类别,那有没有什么方法可以区分出来两个类别呢?
image

我们发现x和y的积可以明显的区分出来这两种类别.我们新构造一个维度z,而各点在z轴方向的值为xy.于是一个二维的空间转换为一个三维空间.
image

在三维空间中,我们可以明显的用一个面来区分两个类别.

更通常的,当数据为非线性,我们希望能够得到一个函数 \phi(x) ,可以将数据映射到更高维空间,以期望在高维空间中线性可分.如果可以找到这样的 \phi(x) 那么只需要用 \phi(x) 替换我们在线性假设中的x,那么非线性的问题就可以解决了.

事实上,这样的 \phi(x) 是可以找到的,不过会有效率问题,上面的例子中,二维空间中的点为(x,y),我们新增纬度z,值为xy.现在我们把例子改一下,把所有点都改成三维空间中的点(x1,x2,x3),那么:

\phi((x1,x2,x3)) = \begin{bmatrix} x1x1 \\ x1x2\\ x1x2 \\x2x2 \\ x2x1\\ x2x3 \\ x3x3 \\ x3x1\\ x3x2 \\ \end{bmatrix} \quad

可以看出 \phi(x) 的时间复杂度为 O(n^2) ,n为数据的特征数.

这里有个更直观的例子,对于下面这些样本的分类:

image

SVM添加一个维度映射到高维空间后是这样的:

image

此时可以使用一个超平面将样本进行分割.在原空间看来决策平面是一个曲线:

image

多项式核函数

我们定义

K(x,z) = (x^Tz)^2

将公式展开

K(x,z) = (\sum_{i=1}^nx_iz_i)(\sum_{j=1}^nx_jz_j) \\=\sum_{i=1}^n{\sum_{j=1}^nx_ix_jz_iz_j}\\ =\sum_{i,j=1}^n{x_ix_jz_iz_j}\\ =\phi(x)^T\phi(z)

K(x,z) 可以转换成两个 \phi(x) 点乘的形式,而 K(x,z) 的复杂度为 O(n) .

这里的 K(x,z) 称为核函数.

我们上面所使用的核核函数被称为多项式核函数,他的完整定义是这样的

K(x,z) = (x^Tz+c)^d

多项式核函数会将n维的数据映射到 \frac{n+d}{d} 维空间.

\phi((x1,x2,x3)) = \begin{bmatrix} x1x1 \\ x1x2\\ x1x2 \\x2x2 \\ x2x1\\ x2x3 \\ x3x3 \\ x3x1\\ x3x2 \\ \sqrt{2c}x1 \\ \sqrt{2c}x2\\ \sqrt{2c}x3 \\c \\ \end{bmatrix} \quad

高斯核函数

另外一种比较常用的核函数是RBF核函数,也称作高斯核函数.

高斯核会将数据映射到无限维空间.

\begin{align} K(\mathbf{x}, \mathbf{y}) & = exp(-\frac{||\mathbf{x}-\mathbf{y}||^2}{2\sigma^2})\\ & = exp(-\frac{1}{2\sigma^2}(\mathbf{x}-\mathbf{y})^T(\mathbf{x}-\mathbf{y}))\\ & = exp(-\frac{1}{2\sigma^2}(\mathbf{x}^T\mathbf{x} + \mathbf{y}^T\mathbf{y}- 2\mathbf{y}^T\mathbf{x}))\\ & = exp(-\frac{1}{2\sigma^2}(||\mathbf{x}||^2+||\mathbf{y}||^2))\cdot exp(\frac{1}{\sigma^2}\mathbf{y}^T\mathbf{x})\\ & = C \cdot exp(\frac{1}{\sigma^2}\mathbf{y}^T\mathbf{x})\\ & = C \cdot \sum_{i=0}^{\infty}\frac{(\frac{1}{\sigma^2}\mathbf{y}^T\mathbf{x})^i}{i!}\\ & = \sum_{i=0}^{\infty}\frac{C}{\sigma^{2i}i!}(\mathbf{y}^T\mathbf{x})^i\\ & =\sum_{i=0}^{\infty}a_i\phi_i(\mathbf{y})^Ta_i\phi_i(\mathbf{x}) \\ & =\phi(x)^T\phi(z)\end{align}

上述公式中

C \cdot exp(\frac{1}{\sigma^2}\mathbf{y}^T\mathbf{x}) = C \cdot \sum_{i=0}^{\infty}\frac{(\frac{1}{\sigma^2}\mathbf{y}^T\mathbf{x})^i}{i!}

使用的是泰勒展开:

e^x = \sum_{n=0}^{\infty}\frac{x^n}{n!}

\sum_{i=0}^{\infty}\frac{(\frac{1}{\sigma^2}\mathbf{y}^T\mathbf{x})^i}{i!} 相当于无限个不同维的多项式核函数之和.多项式核函数可以将低维数据映射到高维,那么对于无限个不同维的多项式核函数之和当然是把数据映射到了无限维.

如果你想了解更多的核函数,可以参考这篇文章:Kernel Functions for Machine Learning Applications

拉格朗日对偶

如果我们能将公式(1)转化成包含 \langle x1,x2 \rangle 的形式,那么就可以使用核函数 K(x1,x2) 替换优化函数中的 \langle x1,x2 \rangle ,从而间接的替换 \langle x1,x2 \rangle 为 \langle \phi(x1),\phi(x2) \rangle .我们会使用拉格朗日对偶完成这个转换.正因为我们是计算 \langle x1,x2 \rangle 而间接计算了 \phi(x) ,所以我们可以用有限的时间计算无限维的数据.

对公式(1)构建优化问题的拉格朗日函数,这样我们就去掉了约束条件,使问题能用一个方程表达出来,方便求极值

L(w,\alpha,b)=\frac{1}{2}\lVert w\rVert^2+\sum_{i=1}^m{\alpha_i(y_i(w^Tx_i+b)-1)} \tag{2}

优化过程先要求 \alpha 的最大值,然后再求 w 与 b 的最小值,即:

\min_{w,b}\max_{\alpha_ { i } \geq 0}L(w,\alpha,b)

\max_{\alpha_ { i } \geq 0}L(w,\alpha,b) 又是一个有约束条件的极值问题,不太好求,根据拉格朗日对偶:

\min_{w,b}\max_{\alpha_ { i } \geq 0}L(w,\alpha,b) \geq \max_{\alpha_ { i } \geq 0}\min_{w,b}L(w,\alpha,b)

image

当满足KKT条件的时候取等号,这个问题是满足KKT条件的,这里就不证明了,详情可以参考文章拉格朗日对偶,所以我们可以用对偶问题代替原问题:

\max_{\alpha_i \geq 0}\min_{w,b}L(w,\alpha,b)

\min_{w,b}L(w,\alpha,b) 的极值就是 w 与 b 导数为0的点.对 w 与 b 求偏导,得到:

w = \sum_{i=1}^m{\alpha_i y_i x_i} \tag{3}

\sum_{i=1}^m{\alpha_i y_i} = 0 \tag{4}

将公式(3)(4)带入到公式(2),得到

\max_\alpha L(\alpha)=\sum_{i=1}^m{\alpha_i}+\frac{1}{2}\sum_{i,j=1}^m{y_iy_j\alpha_i\alpha_jx_i^Tx_j} \\s.t. \quad \alpha_i \geq 0, i=1,...,m\\ \qquad \sum_{i=1}^m{\alpha_i y_i} = 0

这个时候已经得到我们想要的内积形式 \langle x_i,x_j\rangle .

将公式(3)带入到超平面公式可以得到:

w^Tx + b =(\sum_{i=1}^m{\alpha_iy_ix_i})^Tx+b =\sum_{i=1}^m{\alpha_iy_i\langle x_i,x \rangle}+b \tag{5}

如果超平面的 w 参数确定了,相当于超平面的方向确定了,b参数只相当于确定超平面的位置.

image

如图所示,我们想要的超平面是在这两条虚线中间,所以

b = -\dfrac{\max_{i:y_i=-1}w^Tx_i+\min_{i:y_i=1}w^Tx_i}{2}

图中在虚线上的点被称为支持向量,支持向量是距离超平面最近的点,其实超平面仅取决于支持向量,而其他数据对超平面的影响不大.

正则化与不可分情况

有时候数据即使映射到高维空间.也会出现不可分情况,或者某些噪点会使分类误差增大.

image

所以我们使用用L1正则化增加模型的容错率.之所以选择L1正则化是因为L1正则化产生稀疏性，使 w 中许多项变成零。除了计算量上的好处之外,稀疏矩阵可以直接忽略掉对结果没有影响的特征.

\min_{r,\omega,b}\dfrac{1}{2}\lVert\omega\rVert^2 + C\sum_{i=1}^m\varepsilon_i \qquad \\s.t.\quad y_i(\omega^{T}\cdot x_{i}+b) \geq 1 -\varepsilon_i \qquad i=1,…,m\\ \qquad \varepsilon_i \leq 0 \qquad i=1,…,m

转换为拉格朗日函数

L(w,b,\varepsilon,\alpha,r)=\frac{1}{2}\lVert w\rVert^2+ C\sum_{i=1}^m\varepsilon_i-\sum_{i=1}^m{\alpha_i(y_i(w\cdot x_i+b)-1+\varepsilon_i)}- \sum_{i=1}^mr_i\varepsilon_i

对 \varepsilon 求导可以得到

C-\alpha_i-r_i = 0

所以

L(w,b,\varepsilon,\alpha,r)=\sum_{i=1}^m{\alpha_i}-\frac{1}{2}\sum_{i,j=1}^m{y_iy_j\alpha_i\alpha_jx_i^Tx_j} \qquad \\s.t.\quad 0 \leq \alpha \leq C \qquad i=1,…,m\\ \qquad \sum_{i=1}^m{\alpha_i y_i} = 0

对偶问题为:

\max_\alpha \quad L(\alpha)=\sum_{i=1}^m{\alpha_i}-\frac{1}{2}\sum_{i,j=1}^m{y_iy_j\alpha_i\alpha_j\langle x_i,x_j\rangle} \\s.t. \quad 0 \leq \alpha \leq C \qquad i=1,…,m\\ \qquad \sum_{i=1}^m{\alpha_i y_i} = 0 \tag{6}

坐标上升算法

假设有一个函数 W(\alpha_1,\alpha_2,...,\alpha_m) ,我们需要通过调整 \alpha_1,\alpha_2,...,\alpha_m 来找到函数函数的最大值.即

\max_\alpha W(\alpha_1,\alpha_2,...,\alpha_m)

我们可以这样来求极值:

如此循环几次,就可以找出函数的极值

image

顺序最小化优化(SMO)

坐标上升算法不能直接用于我们的优化问题,因为我们的优化函数有一个约束条件:
\sum_{i=1}^m{\alpha_i y_i} = 0
我们无法每次只调整一个 \alpha 并且服从这个约束条件.如果仅改变一个 \alpha ,累加和一定会改变.

所以SMO算法,每次调整两个 \alpha .假设我们调整 \alpha_1 和 \alpha_2 ,那么只要满足

\alpha_1y_1+\alpha_2y_2=\xi \tag{7}

就可以保证 \sum_{i=1}^m{\alpha_i y_i} = 0 ,如下图所示

image

最优解 \alpha_1 和 \alpha_2 都必须在[0,C]之间,而且最优解必须在直线上.所以我们可以得出

L \leq \alpha_2 leq H

接下来把公式(7)带入到 W() ,得到:

W(\alpha_1,\alpha_2) = W(\frac{\xi-\alpha_2y_2}{y_1},\alpha_2)

而 W() 函数其实是关于 \alpha 的一个二次函数,可以转换成

W(\alpha_1,\alpha_2) = a\alpha_2^2+b\alpha_2+c

这是一个关于 \alpha_2 二次函数,很容易求极值.所以这里有三种情况:
第一种情况, W() 与直线的切点 [H,+\infty] .这时候 \alpha_2 的最优解我们取H.

image

第二种情况, W() 与直线的切点在 [L,H] .这时候 \alpha_2 的最优解我们取切点的值.
image

第三种情况, W() 与直线的切点 [-\infty,L] .这时候 \alpha_2 的最优解我们取L.
image

综上

\alpha_2=\begin{cases}H,\qquad \alpha_2 > H\\ \alpha_2,\qquad L \leq \alpha_2 \leq H\\ L,\qquad \alpha_2 < L\\ \end{cases}

最终,重复这种方法即可计算出所有的 \alpha_i .带入到公式(5)即可求出超平面方程.

参考:

posted @ 2018-06-14 14:24:59
评论加载中...
发表评论