机器学习【二】 支持向量机

目录

线性可分定义

支持向量机如何解决线性可分问题

支持向量机的优化问题

 线性不可分情况

 核函数

原问题和对偶问题

如何转化为对偶问题

---

线性可分定义

        线性可分（Linear Separable）：存在一条直线，可以分开⚪和×；

        线性不可分（Nonlinear Separable）：不存在一条直线，可以分开⚪和×；

        

         放在三位空间中就变成了一个平面：

        

         由于人眼仅限于三维空间，所以我们需要借助数学来对线性可分和线性不可分给出一个精确的定义。

        同样先以二维做例子：

        需要注意的是，这个w1和w2是人为设定的，如果反一下的话，符号也要反一下。

         我们可以假设有N个训练样本和标签，{（x1,y1）,（x2,y2），……，（xn,yn）}，其中，若xi属于c1,则yi = + 1，否则yi = -1.

线性可分的严格定义：

        一个训练样本集{（x1,y1）,（x2,y2），……，（xn,yn）}，在 i = 1~N线性可分，是指存在（w1，w2，b）使得对 i = 1~N，有：

        （1）若 yi = +1，则w1·xi1 + w2·xi2 + b > 0

        （2）若 yi = - 1，则w1·xi1 + w2·xi2 + b < 0

用向量形式作简化：

                                xi=[(xi1xi2)]T" role="presentation" style="position: relative;">xi=[(xi1xi2)]T$x_i=[(\begin{array}{c}{x}_{i1}\\ x_{i2}\end{array}){]}^T$    ωi=[(ω1ω2)]T" role="presentation" style="position: relative;">ωi=[(ω1ω2)]T${\omega }_i=[(\begin{array}{c}{\omega }_1\\ {\omega }_2\end{array}){]}^T$

        （1）若yi" role="presentation" style="position: relative;">yi$y_i$ = + 1，则 ωT⋅xi+b>0" role="presentation" style="position: relative;">ωT⋅xi+b>0${\omega }^T\cdot x_i+b>0$

        （2）若yi" role="presentation" style="position: relative;">yi$y_i$ = - 1，则 ωT⋅xi+b<0" role="presentation" style="position: relative;">ωT⋅xi+b<0${\omega }^T\cdot x_i+b<0$

支持向量机如何解决线性可分问题

        从前面可以引出一个问题：在无数多个分开各个类别的超平面中，到底哪一个最好呢？

        例如下面三条线，哪一条更好？

         大多人应该都会选择2号线，根据没有免费午餐定理，每一条线的表现应该是一样的。这里就需要考虑训练样本的位置在特征空间上有测量的误差，而2号线对误差的容忍程度最高，也就是容错最大。

        那么接下来就是考虑怎么寻找2号线？

VAPNIK给出的回答是：

        对于任意一条符合条件的线，尽可能地向两侧移动，即移动到上图中的两条虚线位置。此时我们定义这两条虚线碰到的训练样本叫做这个数据集的支持向量，把两条线之间的距离称为间隔（margin），我们所要求的2号线就是间隔最大的两条线的正中间位置的那条。

支持向量机的优化问题

        这里主要讲如何用严格的数学，寻找最优分类超平面的过程，写成一个最优化问题。

        我们假设训练样本集是线性可分的，支持向量机需要寻找的是最大化间隔（margin）的超平面，可以写成如下的形式：

        最小化（Minimize）：12⋅||ω||2" role="presentation" style="position: relative;">12⋅||ω||2$\frac{1}{2}\cdot {\left|\begin{array}{c}\left|\begin{array}{c}\omega \end{array}\right|\end{array}\right|}^2$

        限制条件： yi(ωTxi+b)≥1,(i=1∼N)" role="presentation" style="position: relative;">yi(ωTxi+b)≥1,(i=1∼N)$y_i({\omega }^T{x}_i+b)\ge 1,(i=1\sim N)$

        其中，(xi,yi),i=1∼N" role="presentation" style="position: relative;">(xi,yi),i=1∼N$(x_i,y_i),i=1\sim N$ 是已知的，(ω,b)" role="presentation" style="position: relative;">(ω,b)$(\omega ,b)$是待求得，这显然是凸优化（Convex Optimization）问题中的二次规划问题。

下面重点开始解释：

先要讲两个事实：

        事实一：

                ωTx+b=0" role="presentation" style="position: relative;">ωTx+b=0${\omega }^{T}x+b=0$ 与 (αωT)x+(αb)=0" role="presentation" style="position: relative;">(αωT)x+(αb)=0$(\alpha {\omega }^T)x+(\alpha b)=0$ 是同一个超平面。 (α≠0)" role="presentation" style="position: relative;">(α≠0)$(\alpha \ne 0)$

        事实二：

                一个点 X0" role="presentation" style="position: relative;">X0$X_0$ 到超平面 ωTx+b=0" role="presentation" style="position: relative;">ωTx+b=0${\omega }^{T}x+b=0$ 的距离    d=|ωTx0+b|‖ω‖" role="presentation" style="position: relative;">d=∣∣ωTx0+b∣∣∥ω∥$d=\frac{\left|{\omega }^T{x}_0+b\right|}{\Vert \omega \Vert }$  .

最小化（Minimize）：12⋅||ω||2" role="presentation" style="position: relative;">12⋅||ω||2$\frac{1}{2}\cdot {\left|\begin{array}{c}\left|\begin{array}{c}\omega \end{array}\right|\end{array}\right|}^2$

          ω=[ω1ω2⋮ωm]" role="presentation" style="position: relative;">ω=⎡⎣⎢⎢⎢⎢ω1ω2⋮ωm⎤⎦⎥⎥⎥⎥$\omega =\left[\begin{array}{c}{\omega }_1\\ {\omega }_2\\ ⋮\\ {\omega }_m\end{array}\right]$   ,        ||ω||2=ω12+ω22+...+ωm2=∑i=1mωi2" role="presentation" style="position: relative;">||ω||2=ω21+ω22+...+ω2m=∑mi=1ω2i${\left|\begin{array}{c}\left|\begin{array}{c}\omega \end{array}\right|\end{array}\right|}^2={\omega }_1^2+{\omega }_2^2+...+{\omega }_m^2=\sum _{i=1}^m{\omega }_i^2$

        基于上面两个事实，我们可以找到一个α" role="presentation" style="position: relative;">α$\alpha$进行缩放 (ω,b)→(αω,αb)" role="presentation" style="position: relative;">(ω,b)→(αω,αb)$(\omega ,b)\to (\alpha \omega ,\alpha b)$ ，最终使得：

                在支持向量 x0" role="presentation" style="position: relative;">x0$x_0$ 上有 |ωTx0+b|=1" role="presentation" style="position: relative;">∣∣ωTx0+b∣∣=1$\left|{\omega }^T{x}_0+b\right|=1$

                而在非支持向量上 |ωTx0+b|>1" role="presentation" style="position: relative;">∣∣ωTx0+b∣∣>1$\left|{\omega }^T{x}_0+b\right|>1$

                此时 d=1‖ω‖" role="presentation" style="position: relative;">d=1∥ω∥$d=\frac{1}{\Vert \omega \Vert }$，要最大化d，就是要最小化 ‖ω‖" role="presentation" style="position: relative;">∥ω∥$\Vert \omega \Vert$

限制条件： yi(ωTxi+b)≥1,(i=1∼N)" role="presentation" style="position: relative;">yi(ωTxi+b)≥1,(i=1∼N)$y_i({\omega }^T{x}_i+b)\ge 1,(i=1\sim N)$

        其中 yi" role="presentation" style="position: relative;">yi$y_i$ 的作用是协调超平面的作用，使得一边的  (ωTx+b)>1" role="presentation" style="position: relative;">(ωTx+b)>1$({\omega }^{T}x+b)>1$,另一边的(ωTx+b)<1" role="presentation" style="position: relative;">(ωTx+b)<1$({\omega }^{T}x+b)<1$

 二次规划的定义是：

        （1）目标函数（Objective Function）是二次项。

        （2）限制条件是一次项。

要么无解，要么只有唯一的最小值。

 线性不可分情况

        如果线性不可分，那么上面是无解的，即不存在  ω" role="presentation" style="position: relative;">ω$\omega$ 和 b 满足上面的所有N个限制条件。所以我们需要放松限制条件：

        限制条件改写为：    yi(ωTφ(Xi)+b)≥1−δi,(i=1∼N)" role="presentation" style="position: relative;">yi(ωTφ(Xi)+b)≥1−δi,(i=1∼N)$y_i({\omega }^T\phi (X_i)+b)\ge 1-{\delta }_i,(i=1\sim N)$ ， 其中 δi" role="presentation" style="position: relative;">δi${\delta }_i$ 为松弛变量。

        改造后的支持向量机优化版本：

                最小化 ：12‖ω‖2+C∑i=1Nδi" role="presentation" style="position: relative;">12∥ω∥2+C∑Ni=1δi$\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^N{\delta }_i$   或 12‖ω‖2+C∑i=1Nδi2" role="presentation" style="position: relative;">12∥ω∥2+C∑Ni=1δ2i$\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^N{\delta }_i^2$     

                限制条件： （1）δ≥0.(i=1∼N)" role="presentation" style="position: relative;">δ≥0.(i=1∼N)$\delta \ge 0.(i=1\sim N)$

                                   （2）yi(ωTφ(Xi)+b)≥1−δi,(i=1∼N)" role="presentation" style="position: relative;">yi(ωTφ(Xi)+b)≥1−δi,(i=1∼N)$y_i({\omega }^T\phi (X_i)+b)\ge 1-{\delta }_i,(i=1\sim N)$

        比例因子C 起到了平衡两项的关键作用，是由人为设定的。

        我们把人为事先设定的参数叫做算法的超参数。

        通常会不断变化C的值 => 同时测试算法的识别率 => 选取合适的超参数C  （调参侠出现啦！！）

         支持向量机采用的是将特征空间由低维映射到高维，然后再用线性超平面对数据进行分类。

一个定理：

        假设在一个M维空间上随机取N个训练样本，随机得对每个训练样本赋予标签+1 或 -1，若这些训练样本线性可分得概率为P(M)，

则有：当M趋于无穷大时，P(M) = 1.

直观上地感受一下： 当特征空间得维度M增加的时候，带估计参数(ω,b)" role="presentation" style="position: relative;">(ω,b)$(\omega ,b)$的维度也会增加，也就是说整个算法模型的自由度会增加，当然更容易分开低维的时候无法分开的数据集。

 核函数

        这里以具体研究 φ(Xi)" role="presentation" style="position: relative;">φ(Xi)$\phi (X_i)$ 的形式，来引入核函数的概念。

Vladimir Naumovich Vapnik：我们可以不用知道 φ(X)" role="presentation" style="position: relative;">φ(X)$\phi (X)$ 的具体形式。

         我们定义 K(X1,X2)" role="presentation" style="position: relative;">K(X1,X2)$K(X_1,X_2)$ 为核函数。 

        核函数K和映射 φ" role="presentation" style="position: relative;">φ$\phi$ 是一一对应的关系。

K(X1,X2)" role="presentation" style="position: relative;">K(X1,X2)$K(X_1,X_2)$ 能写成 φ(X1)T⋅φ(X2)" role="presentation" style="position: relative;">φ(X1)T⋅φ(X2)$\phi (X_1{)}^T\cdot \phi (X_2)$ 的充要条件：

        （1）K(X1,X2)=K(X2,X1)" role="presentation">K(X1,X2)=K(X2,X1)$K(X_1,X_2)=K(X_2,X_1)$ （交换性）

        （2）∀Ci(i=1∼N),∀N∑i=1N∑j=1NCiCjK(Xi,Xj)>=0" role="presentation">∀Ci(i=1∼N),∀N∑Ni=1∑Nj=1CiCjK(Xi,Xj)>=0$\mathrm{\forall }{C}_i(i=1\sim N),\mathrm{\forall }N\sum _{i=1}^N\sum _{j=1}^N{C}_i{C}_{j}K(X_i,X_j)>=0$ （半正定性）

原问题和对偶问题

原问题的定义：

        最小化： f(ω)" role="presentation" style="position: relative;">f(ω)$f(\omega )$

        限制条件： gi(ω)<=0i=1∼K" role="presentation" style="position: relative;">gi(ω)<=0i=1∼K$g_i(\omega )<=0i=1\sim K$ ,

                           hi(ω)=0i=1∼m" role="presentation" style="position: relative;">hi(ω)=0i=1∼m$h_i(\omega )=0i=1\sim m$

定义该原问题的对偶问题如下：

        定义函数： L(ω,α,β)=f(ω)+∑i=1Kαigi(ω)+∑i=1Kβihi(ω)=f(ω)+αTg(ω)+βTh(ω)" role="presentation" style="position: relative;">L(ω,α,β)=f(ω)+∑Ki=1αigi(ω)+∑Ki=1βihi(ω)=f(ω)+αTg(ω)+βTh(ω)$L(\omega ,\alpha ,\beta )=f(\omega )+\sum _{i=1}^K{\alpha }_i{g}_i(\omega )+\sum _{i=1}^K{\beta }_i{h}_i(\omega )=f(\omega )+{\alpha }^{T}g(\omega )+{\beta }^{T}h(\omega )$

        其中， α=[α1,α2,...,αK]T" role="presentation" style="position: relative;">α=[α1,α2,...,αK]T$\alpha =[{\alpha }_1,{\alpha }_2,...,{\alpha }_K{]}^T$,

                   β=[β1,β2,...,βM]T" role="presentation" style="position: relative;">β=[β1,β2,...,βM]T$\beta =[{\beta }_1,{\beta }_2,...,{\beta }_M{]}^T$,

                   g(ω)=[g1(ω),g2(ω),...,gK(ω)]T" role="presentation" style="position: relative;">g(ω)=[g1(ω),g2(ω),...,gK(ω)]T$g(\omega )=[g_1(\omega ),g_2(\omega ),...,g_K(\omega ){]}^T$,

                   h(ω)=[h1(ω),h2(ω),...,hM(ω)]T" role="presentation" style="position: relative;">h(ω)=[h1(ω),h2(ω),...,hM(ω)]T$h(\omega )=[h_1(\omega ),h_2(\omega ),...,h_M(\omega ){]}^T$,

        在此基础上，定义对偶问题如下：

                最大化： θ(α,β)=infL(ω,α,β)" role="presentation" style="position: relative;">θ(α,β)=infL(ω,α,β)$\theta (\alpha ,\beta )=infL(\omega ,\alpha ,\beta )$ ,

                限制条件： αi≥0,i=1∼K" role="presentation" style="position: relative;">αi≥0,i=1∼K${\alpha }_i\ge 0,i=1\sim K$

综合原问题和对偶问题的定义得到：

定理一：

        如果 ω∗" role="presentation" style="position: relative;">ω∗${\omega }^{\ast }$ 是原问题的解，(α∗,β∗)" role="presentation" style="position: relative;">(α∗,β∗)$({\alpha }^{\ast },{\beta }^{\ast })$ 是对偶问题的解，则有：

                f(ω∗)≥θ(α∗,β∗)" role="presentation" style="position: relative;">f(ω∗)≥θ(α∗,β∗)$f({\omega }^{\ast })\ge \theta ({\alpha }^{\ast },{\beta }^{\ast })$

        我们定义 f(ω∗)−θ(α∗,β∗)" role="presentation" style="position: relative;">f(ω∗)−θ(α∗,β∗)$f({\omega }^{\ast })-\theta ({\alpha }^{\ast },{\beta }^{\ast })$ 为对偶差距， 显然 ≥ 0.

强对偶定理：

        如果 g(ω)=Aω+b,h(ω)=Cω+d,f(ω)" role="presentation" style="position: relative;">g(ω)=Aω+b,h(ω)=Cω+d,f(ω)$g(\omega )=A\omega +b,h(\omega )=C\omega +d,f(\omega )$ 为凸函数，则有f(ω∗)=θ(α∗,β∗)" role="presentation" style="position: relative;">f(ω∗)=θ(α∗,β∗)$f({\omega }^{\ast })=\theta ({\alpha }^{\ast },{\beta }^{\ast })$，即对偶差距为0.

        （也就是说，如果原问题的目标函数是凸函数，限制条件是线性函数，那么对偶差距等于0）

根据定理一推出的不等式：

        若 f(ω∗)=θ(α∗,β∗)" role="presentation" style="position: relative;">f(ω∗)=θ(α∗,β∗)$f({\omega }^{\ast })=\theta ({\alpha }^{\ast },{\beta }^{\ast })$ ，则定理一中必然能够推出，对于所有的 i=1∼K" role="presentation" style="position: relative;">i=1∼K$i=1\sim K$ ,要么 αi=0" role="presentation" style="position: relative;">αi=0${\alpha }_i=0$ ，要么gi(ω∗)=0" role="presentation" style="position: relative;">gi(ω∗)=0$g_i({\omega }^{\ast })=0$ 。这个条件成为KKT条件。

如何转化为对偶问题

 回顾一下。

首先： δi≥0,(i=1∼N)" role="presentation" style="position: relative;">δi≥0,(i=1∼N)${\delta }_i\ge 0,(i=1\sim N)$  转换成 δi≤0,(i=1∼N)" role="presentation" style="position: relative;">δi≤0,(i=1∼N)${\delta }_i\le 0,(i=1\sim N)$

得到：  最小化： 12‖ω‖2−C∑i=1Nδi" role="presentation" style="position: relative;">12∥ω∥2−C∑Ni=1δi$\frac{1}{2}{\Vert \omega \Vert }^2-C\sum _{i=1}^N{\delta }_i$  或  12‖ω‖2+C∑i=1Nδi2" role="presentation" style="position: relative;">12∥ω∥2+C∑Ni=1δ2i$\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^N{\delta }_i^2$

             限制条件：（1）δi≤0,(i=1∼N)" role="presentation" style="position: relative;">δi≤0,(i=1∼N)${\delta }_i\le 0,(i=1\sim N)$

                               （2）1+δi−yiωTφ(Xi)−yib≤0(i=1∼N)" role="presentation" style="position: relative;">1+δi−yiωTφ(Xi)−yib≤0(i=1∼N)$1+{\delta }_i-y_i{\omega }^T\phi (X_i)-y_{i}b\le 0(i=1\sim N)$

将对偶问题写成如下形式：

        最大化：θ(α,β)=infω,δi,b{12‖ω‖T−C∑i=1Nβiδi+∑i=1Nαi[1+δi−yiωTφ(Xi)−yib]}" role="presentation" style="position: relative;">θ(α,β)=infω,δi,b{12∥ω∥T−C∑Ni=1βiδi+∑Ni=1αi[1+δi−yiωTφ(Xi)−yib]}$\theta (\alpha ,\beta )=\underset{\omega ,{\delta }_i,b}{inf}\left\{\frac{1}{2}{\Vert \omega \Vert }^T-C\sum _{i=1}^N{\beta }_i{\delta }_i+\sum _{i=1}^N{\alpha }_i[1+{\delta }_i-y_i{\omega }^T\phi (X_i)-y_{i}b]\right\}$

        限制条件： （1）αi≥0" role="presentation" style="position: relative;">αi≥0${\alpha }_i\ge 0$

                           （2）βi≥0" role="presentation" style="position: relative;">βi≥0${\beta }_i\ge 0$