SVM原理

这是一篇

坐在马桶上都能看懂的

SVM笔记

《统计学习方法》、《机器学习》SVM章节整理


支持向量机SVM (support vector machine)

SVM是一种二分类模型,学习策略就是间隔最大化,由简至繁,可分为三种模型:

1. 线性可分支持向量机

SVM的目的是使类间间隔最大化。对于线性可分的问题,虽然有多个超平面可以将两类分开,但能使类间间隔最大的超平面只有一个(证明见《统计学习方法》by 李航)。对于两类问题($y_i\in \{+1,-1\}$),分类超平面就是一条直线,$w$是直线的法向量,以下用两类问题举例。
下图3条分类直线的灰色阴影部分代表类间间隔,两类的样本点都在阴影部分两边,最宽的阴影部分(类间间隔最大)对应的直线即为最佳分类线:

支持向量机的任务就是确定这条直线。

1.1 间隔距离的表示

函数间隔

  • 与样本点的函数间隔
    对于给定的训练数据集$T$和超平面$(\vec{\boldsymbol{w}}, b)$,定义超平面$(\vec{\boldsymbol{w}}, b)$关于样本点$(\vec{\boldsymbol{x_i}}, y_i)$的函数间隔为:
    $$
    \hat{γ_i} = y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) \tag{1.1}
    $$

  • 与训练集的函数间隔
    定义超平面$(\vec{\boldsymbol{w}}, b)$关于训练数据集$T$的函数间隔为超平面$(\vec{\boldsymbol{w}}, b)$关于$T$中所有样本点$(\vec{\boldsymbol{x_i}}, y_i)$的函数间隔之最小值:
    $$
    \hatγ=\min\limits_{i=1,\cdots,N}\hat{γ_i}\tag{1.2}
    $$

随着$\vec{\boldsymbol{w}}, b​$成比例的改变,超平面没变 (${\vec{\boldsymbol{w}}}^T·\vec{\boldsymbol{x}}+b=0​$ 仍然成立),但由$(1.1)​$可知,函数间隔会发生变化。所以令$\Vert\vec{\boldsymbol{w’}}\Vert=1​$,使间隔确定。这时函数间隔成为几何间隔。

几何间隔

由$\Vert\frac{\vec{\boldsymbol{w}}}{\Vert\vec{\boldsymbol{w}}\Vert}\Vert=\Vert\vec{\boldsymbol{w’}}\Vert=1$

  • 与样本点的几何间隔
    对于给定的训练数据集$T$和超平面 $(\vec{\boldsymbol{w}}, b)$,定义超平面 $(\vec{\boldsymbol{w}}, b)$ 关于样本点 $(\vec{\boldsymbol{x_i}}, y_i)$ 的几何间隔为:
    $$
    γ_i=y_i\frac{|\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b|}{\Vert\vec{\boldsymbol{w}}\Vert}\tag{1.3}
    $$
    这就是样本空间中任意点到超平面的距离,总是正值。

  • 与训练集的几何间隔
    定义超平面$(\vec{\boldsymbol{w}}, b)$关于训练数据集$T$的几何间隔为超平面 $(\vec{\boldsymbol{w}}, b)$ 关于$T$中所有样本点 $(\vec{\boldsymbol{x_i}}, y_i)$ 的几何间隔之最小值:
    $$
    γ=\min\limits_{i=1,\cdots,N}{γ_i}\tag{1.4}
    $$

  • 函数间隔和几何间隔的关系:

$$
\begin{cases}
γ_i = \dfrac{\hat{γ_i}}{\Vert\vec{\boldsymbol{w}}\Vert} \\
γ = \dfrac{\hat{γ}}{\Vert\vec{\boldsymbol{w}}\Vert}
\end{cases}
\tag {1.5}
$$

1.2 支持向量

在线性可分情况下,训练集中与分类超平面最近的点称为支持向量(即在灰色阴影区边界上的点,下图为虚线边界上的点)。 对于两类问题,$y_i\in{+1,-1}$(将类别标记为$+1,-1$是为了方便计算)。

在决定分类超平面时只有支持向量起作用(控制阴影区的范围),这就是是支持向量机名字的由来。

因为已经令 $\Vert\vec{\boldsymbol{w’}}\Vert=1$,所以两类的支持向量分别在超平面 ${\vec{\boldsymbol{w}}}^T·\vec{\boldsymbol{x}}+b=+1$ 和 ${\vec{\boldsymbol{w}}}^T·\vec{\boldsymbol{x}}+b=-1$ 上 :

  1. 由公式$(1.3)$可知,任意一类的支持向量到超平面的距离都为:$\frac{1}{\Vert\vec{\boldsymbol{w}}\Vert}$
  2. 对于所有样本点:

$$
\begin{cases}
{\vec{\boldsymbol{w}}}^T·\vec{\boldsymbol{x}}+b≥+1, & y_i = +1 \\
{\vec{\boldsymbol{w}}}^T·\vec{\boldsymbol{x}}+b≤-1, & y_i=-1
\end{cases}
\tag{1.6}
$$
所以$y(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x}}+b)​$可以表示分类的正确性及确信度:

  • 正确性:$y_i\in{+1,-1}$,分类正确的情况下,$y(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x}}+b)>0$。分类错误的情况下,$y(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x}}+b)<0$
  • 确信度:一般来说,一个点距离分类超平面的远近可以表示分类预测的确信程度。在超平面 $\vec{\boldsymbol{w}}·\vec{\boldsymbol{x}}+b=0$ 确定的情况下,$|\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x}}+b|$能够相对地表示样本点$\vec{\boldsymbol{x}}$距离超平面的远近。所以 $y(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x}}+b)$ 的值越大,确信度越高。

1.3 最大间隔学习算法

可以发现,当支持向量到分类线的几何距离(式$(1.4)$的$γ$)越大,阴影部分就越粗。要找阴影部分最粗的分类线,相当于求最大的$γ$,可以表示为下面的约束最优化问题:
$$
\begin{array}{ll}
\max\limits_{\vec{\boldsymbol{w}}, b} & γ \\
\text{s.t.} & y_i\dfrac{|\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b|}{\Vert\vec{\boldsymbol{w}}\Vert}≥γ & i=1,2,···,N
\end{array}
\tag{1.7}
$$
约束表示这个$γ​$一定是支持向量的几何距离。一句话描述$(1.6)​$就是“让支持向量到分类超平面的距离最大”。

$(1.7)​$是用几何间隔表示的,改用函数间隔表示:
$$
\begin{array}{ll}
\max\limits_{\vec{\boldsymbol{w}}, b} & \dfrac{\hatγ}{\Vert\vec{\boldsymbol{w}}\Vert} \\
\text{s.t.} & y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) ≥\hatγ & i=1,2,···,N
\end{array}
\tag{1.8}
$$
函数间隔$\hatγ​$的取值并不影响优化问题的解,取$\hatγ=1​$,将求最大化的$\dfrac{1}{\Vert\vec{\boldsymbol{w}}\Vert}​$改为求最小化的$\dfrac{\Vert\vec{\boldsymbol{w}}\Vert^2}{2}​$.

于是,对于线性可分问题,构造并求解约束最优化问题:
$$
\begin{array}{ll}
\min\limits_{\vec{\boldsymbol{w}}, b} & \dfrac{\Vert\vec{\boldsymbol{w}}\Vert^2}{2} \\
\text{s.t.} & y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) -1≥0 & i=1,2,···,N
\end{array}
\tag{1.9}
$$
这是一个凸二次优化问题,求得最优解 $\vec{\boldsymbol{w}}^\ast , b^\ast ​$。确定分类超平面:$\vec{\boldsymbol{w}}^\ast·\vec{\boldsymbol{x}}+b^\ast=0​$. 式$(1.9)​$就是支持向量机的基本型。

1.4 最大间隔学习的对偶算法 (线性可分支持向量机学习算法)

对于最优化问题 $(1.9)$,应用拉格朗日对偶性,通过求解对偶问题,得到原始问题的最优解,这就是线性可分支持向量机的对偶算法(dual algorithm)。

引入对偶算法的两个好处:

  1. 对偶问题往往更容易求解。
  2. 自然引入核函数,进而推广到非线性分类问题。

对 $(1.9)$的每一个不等式约束(共有N个不等式约束)引进拉格朗日乘子$\alpha_i≥0, i=1,2···,N$,该问题的拉格朗日函数可写为:
$$
L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}})=\dfrac{\Vert\vec{\boldsymbol{w}}\Vert^2}{2}-\sum\limits_{i=1}^N\alpha_i(y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) -1) \tag{1.10}
$$
$\vec{\boldsymbol{\alpha}}=(\alpha_1, \alpha_2, ···, \alpha_N)​$为拉格朗日乘子向量。根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:
$$
\max_{\vec{\boldsymbol{\alpha}}}\min_{\vec{\boldsymbol{w}},b}L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}}) \tag{1.11}
$$
所以,为了得到对偶问题的解,需要先求$L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}})$对 $\vec{\boldsymbol{w}},b$ 的极小 $\min\limits_{\vec{\boldsymbol{w}},b}L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}})$,再求对 $\vec{\boldsymbol{\alpha}}$的极大$\max\limits_{\vec{\boldsymbol{\alpha}}}\min\limits_{\vec{\boldsymbol{w}},b}L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}})$。

  • 求 $\min\limits_{\vec{\boldsymbol{w}},b}L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}})$

    将拉格朗日函数$L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}})$分别对$\vec{\boldsymbol{w}},b$求偏导数并令其等于$0$,得:
    $$
    \begin{cases}
    \vec{\boldsymbol{w}}=\sum\limits_{i=1}^N\alpha_iy_i\vec{\boldsymbol{x_i}}\\
    \sum\limits_{i=1}^N\alpha_iy_i=0
    \end{cases}
    \tag{1.12}
    $$

    将式 $(1.12)$ 带入式 $(1.10)$,得:
    $$
    \min\limits_{\vec{\boldsymbol{w}},b}L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}})=-\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_j(\vec{\boldsymbol{x_i}}^T\vec{\boldsymbol{x_j}})+\sum\limits_{i=1}^N\alpha_i\tag{1.13}
    $$

  • 求$\max\limits_{\vec{\boldsymbol{\alpha}}}\min\limits_{\vec{\boldsymbol{w}},b}L(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\alpha}})​$

    $$
    \begin{array}{ll}
    \max\limits_{\vec{\boldsymbol{\alpha}}} & -\dfrac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_j(\vec{\boldsymbol{x_i}}^T\vec{\boldsymbol{x_j}})+\sum\limits_{i=1}^N\alpha_i \\
    \text{s.t.} & \sum\limits_{i=1}^N\alpha_iy_i=0 \\
    &\alpha_i≥0, i=1,2···,N
    \end{array}
    \tag{1.14}
    $$

将式$(1.14)$的目标函数由求极大转换为求极小,就得到了等价的对偶最优化问题,如下:
$$
\begin{array}{ll}
\min\limits_{\vec{\boldsymbol{\alpha}}} & \dfrac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_j(\vec{\boldsymbol{x_i}}^T\vec{\boldsymbol{x_j}})-\sum\limits_{i=1}^N\alpha_i \\
\text{s.t.} & \sum\limits_{i=1}^N\alpha_iy_i=0 \\
&\alpha_i≥0, i=1,2···,N
\end{array}
\tag{1.15}
$$

定理:设$\vec{\boldsymbol{\alpha}}^\ast=(\alpha_1^\ast,\alpha_2^\ast,···,\alpha_l^\ast)$是$(1.15)$的解,则存在下标 $j$,使得$\alpha_l^\ast>0$,并可按下式求得原始最优化问题$(1.9)$的解$\vec{\boldsymbol{w}}^\ast , b^\ast $:
$$
\begin{align}
\vec{\boldsymbol{w^\ast}} &= \sum\limits_{i=1}^N\alpha_i^\ast y_i\vec{\boldsymbol{x_i}} \tag{1.16} \\
b^\ast &= y_j- \sum\limits_{i=1}^N\alpha_i^\ast y_i(\vec{\boldsymbol{x_i}}^T\vec{\boldsymbol{x_j}}) \tag{1.17}
\end{align}
$$
上面定理的证明需要用到KKT条件,在证明过程中,可以发现 $\vec{\boldsymbol{w}}^\ast , b^\ast ​$只依赖于训练集中对应于$\alpha_i^\ast>0​$的样本点 $(x_i,y_i)​$ ,而其他的样本点($\alpha_j^\ast=0​$)对 $\vec{\boldsymbol{w}}^\ast , b^\ast ​$ 没有影响。对应于$\alpha_i^\ast>0​$的样本点 $(x_i,y_i)​$ 就是支持向量 (这是线性可分情况下支持向量的定义)。

其实由 $(1.12)$ 可得式 $(1.16)$,有了 $\vec{\boldsymbol{w^\ast}}$,根据线性可分支持向量的性质 $y({\vec{\boldsymbol{w}}}^T·\vec{\boldsymbol{x}}+b)=1$ ,也可以确定 $b^\ast$。

2. 线性支持向量机

对于以下线性不可分的情况,需要用到线性支持向量机,修改硬间隔最大化,使其成为软间隔最大化。

线性不可分意味着某些样本点 $(x_i,y_i)$ 不能满足函数间隔大于等于1的约束条件($(1.9)$ 中的约束条件)。即这些样本点 $(x_i,y_i)$ 被错误分类,因为要保证整体的分类准确性,必须牺牲这些样本。这些样本被去除之后,剩下的样本点组成的集合是线性可分的。

2.1 向量机学习算法

构造最优化问题,对每个样本点 $(x_i,y_i)$ 引进一个松弛变量 $\xi_i≥0$,使函数间隔加上松弛变量大于等于1。约束条件就变为 $y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) +\xi_i≥1$。同时,对每个松弛变量 $\xi_i$,将其看作一个代价。目标函数由原来的 $\frac{\Vert\vec{\boldsymbol{w}}\Vert^2}{2}$ 变为 $\dfrac{\Vert\vec{\boldsymbol{w}}\Vert^2}{2}+C\sum\limits_\limits{i=1}^N\xi_i$ ,这里, $C>0$ 称为惩罚参数,一般由实际问题决定。$C$ 值较大时对错分类的惩罚增加,间隔的边界就相对较“硬”;$C$ 值较小时对错分类的惩罚减小,间隔边界就比较“软”,允许更多的样本点落在间隔内。

线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题(原始问题):
$$
\begin{array}{ll}
\min\limits_{\vec{\boldsymbol{w}}, b,\vec{\boldsymbol{\xi}}} & \dfrac{\Vert\vec{\boldsymbol{w}}\Vert^2}{2}+C\sum\limits_\limits{i=1}^N\xi_i \\
\text{s.t.} & y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) +\xi_i≥1 & i=1,2,···,N \\
& \xi_i≥0 & i=1,2,···,N
\end{array}
\tag{2.1}
$$

原始问题 $(2.1)​$ 是一个凸二次规划问题,所以关于 $(\vec{\boldsymbol{w}},b,\vec{\boldsymbol{\xi}})​$ 的解是存在的。可以证明 $\vec{\boldsymbol{w}}​$ 的解是唯一的,但 $b​$ 的解可能不唯一,而是存在于一个区间。线性支持向量机包含线性可分支持向量机。

2.2 对偶算法(线性支持向量机学习算法)

与 1.4 节类似,可求得原始问题 $(2.1)$ 的对偶问题为:
$$
\begin{array}{ll}
\min\limits_{\vec{\boldsymbol{\alpha}}} & \dfrac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_j(\vec{\boldsymbol{x_i}}^T\vec{\boldsymbol{x_j}})-\sum\limits_{i=1}^N\alpha_i \\
\text{s.t.} & \sum\limits_{i=1}^N\alpha_iy_i=0 \\
&0≤\alpha_i≤C, i=1,2···,N
\end{array}
\tag{2.2}
$$
这就是线性支持向量机学习算法。对比线性可分支持向量机学习算法 $(1.15)$,可以看出两者的唯一区别就在于对偶变量 $\alpha_i$ 的约束不同,一个是 $0≤\alpha_i≤C$,一个是 $0≤\alpha_i$ 。它的解$\vec{\boldsymbol{w}}^\ast $ 也和线性可分支持向量机的解$\vec{\boldsymbol{w}}^\ast$ 一样 :$\vec{\boldsymbol{w^\ast}} = \sum\limits_{i=1}^N\alpha_i^\ast y_i\vec{\boldsymbol{x_i}}$,计算 $b^\ast$ 时,选择 $\vec{\boldsymbol{\alpha^\ast}}$ 的一个分量$\alpha_j^\ast$适合条件$0<\alpha_j^\ast<C$,计算$b^\ast = y_j- \sum\limits_{i=1}^N\alpha_i^\ast y_i(\vec{\boldsymbol{x_i}}^T\vec{\boldsymbol{x_j}}) $,所以 $b^\ast$ 可能不唯一。

2.3 支持向量

KKT 条件,对偶问题的解$\vec{\boldsymbol{\alpha}}^\ast=(\alpha_1^\ast,\alpha_2^\ast,···,\alpha_N^\ast)$中对应于$\alpha_i^\ast>0$ 的样本 $\vec{\boldsymbol{x_i}}$ 称为支持向量(软间隔的支持向量)。软间隔的支持向量或者在间隔边界上,或者在间隔边界与分离超平面之间,或者在分离超平面错分的一侧。

实例 $x_i$ 到间隔边界的距离为 $\frac{\xi_i}{\Vert\vec{\boldsymbol{w}}\Vert}$。由上图可知,若 $\alpha_i^\ast<C$ 则 $\xi_i=0$ (由KKT条件),支持向量 $x_j$ 落在间隔边界上;若 $\alpha_i^\ast=C$ , $0<\xi_i<1$ ,分类正确,支持向量 $x_j$ 落在间隔边界和超平面之间;若 $\alpha_i^\ast=C$ , $\xi_i=1$ ,支持向量 $x_j$ 落在超平面上;若 $\alpha_i^\ast=C$ , $\xi_i>1$ ,支持向量 $x_j$ 落在超平面错分的一侧。

2.4 算法的另一种解释

在 2.1 节,做了如下的假设:

对每个样本点 $(x_i,y_i)$ 引进一个松弛变量 $\xi_i≥0$,使函数间隔加上松弛变量大于等于1。约束条件就变为 $y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) +\xi_i≥1$。

再令间隔最大化的同时,为了让不满足约束的样本尽可能少,也可以理解为最小化以下目标函数:
$$
\begin{array}{ll}
\min\limits_{\vec{\boldsymbol{w}},b}&\sum\limits_{i=1}^N[1-y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b)]_++ \lambda\Vert\vec{\boldsymbol{w}}\Vert^2
\end{array}
\tag{2.3}
$$

其中,$[x]_+$ 函数定义如下:

$$
[x]_+ =
\begin{cases}
x, & \text{x>0} \\
0, & \text{x≤0}
\end{cases}
\tag{2.4}
$$

这个目标函数由两项组成,第一项中的 $[1-y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) ]_+$ 在错分类时为正值,在正确分类且函数间隔 (确信度)$y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b)$ 大于1时为 $0$,整个第一项就代表分类的损失。

函数 $f(x)=[1-x]_+$ 又叫hinge损失函数:

$$
\ell_{hinge}(x)=\max(0,1-x)\tag{2.5}
$$

用hinge损失函数来替代原始的0-1损失函数,因为它是凸的连续函数,有较好的数学性质,方便求解。还可以替换成其他常用的损失函数,比如指数损失:$\ell_{exp}(x)=e^{-x}$和对率损失:$\ell_{log}(x)=log(1+e^{-x})$。

为什么用 $[1-y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) ]_+$ 而不用 $[-y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) ]_+$ 呢?因为 $[-y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) ]_+$ 代表样本点只要被正确分类,损失就是0。 $[1-y_i(\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b) ]_+$ 不仅要求正确分类,还要求确信度足够高时损失才是0。

可以证明,$(2.3)$ 和 $(2.1)$ 是等价的。

3. 非线性支持向量机

数据集线性可分:

  • 给定一个数据集 $T=\{(\vec{\boldsymbol{x_1}},y_1),(\vec{\boldsymbol{x_2}},y_2),···,(\vec{\boldsymbol{x_l}},y_l)\}$ ,其中,$\vec{\boldsymbol{x_i}}\in\mathcal{X} =\boldsymbol{R}^n$,$y_i\in\mathcal{Y}=\{+1,-1\},i=1,2,···,l $,如果存在某个超平面 $S:\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x}}+b=0$ 能够将数据集的两类完全正确地划分到超平面的两侧,即对所有$y_i\in+1$的实例,有$\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b>0$,对所有$y_i\in-1$的实例,有$\vec{\boldsymbol{w}}^T·\vec{\boldsymbol{x_i}}+b<0$,则称数据集 $T$ 为线性可分数据集。

数据集非线性可分:

  • 数据集不满足线性可分条件,但能用 $\boldsymbol{R}^n$ 中的一个超曲面分开。

非线性问题不好求解,通常将非线性分类问题转换为线性分类问题,过程分为两步:

  1. 使用一个变换将元空间的数据映射到新空间(希尔伯特空间)(如果原始空间是有限维,那么一定存在一个高维特征空间使样本可分)。
  2. 在新空间里用线性分类学习方法从训练数据中学习分类模型。

过程示意如下:

3.1 核技巧

令 $\phi(\vec{\boldsymbol{x}})$ 表示将 $\vec{\boldsymbol{x}}$ 映射后的特征向量,由于原算法 $(1.15)$ 中存在 $(\vec{\boldsymbol{x_i}}^T\vec{\boldsymbol{x_j}})$ 这一项,新空间中进行分类也就存在 $\phi(\vec{\boldsymbol{x_i}})^T\phi(\vec{\boldsymbol{x_j}})$ 这一项。由于新空间中维数很高,直接计算 $\phi(\vec{\boldsymbol{x_i}})^T\phi(\vec{\boldsymbol{x_j}})$ 通常是很困难的,可以设想一个函数:
$$
\kappa(\vec{\boldsymbol{x_i}},\vec{\boldsymbol{x_j}})=\phi(\vec{\boldsymbol{x_i}})^T\phi(\vec{\boldsymbol{x_j}}) \tag{3.1}
$$
即 $\vec{\boldsymbol{x_i}},\vec{\boldsymbol{x_j}}$ 在新空间中的内积 $\phi(\vec{\boldsymbol{x_i}})^T\phi(\vec{\boldsymbol{x_j}})$ 等于他们在原空间通过函数 $\kappa(·,·)$ 的计算结果,不必去计算更高维新空间的向量内积,这称为核技巧,$\kappa(·,·)$称为核函数。

式 $(1.15)$ 可以写为:
$$
\begin{array}{ll}
\min\limits_{\vec{\boldsymbol{\alpha}}} & \dfrac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_j\kappa(\vec{\boldsymbol{x_i}},\vec{\boldsymbol{x_j}})-\sum\limits_{i=1}^N\alpha_i \\
\text{s.t.} & \sum\limits_{i=1}^N\alpha_iy_i=0 \\
&\alpha_i≥0, i=1,2···,N
\end{array}
\tag{3.2}
$$
求解后得到新空间上的分类超平面:
$$
\begin{array}{ll}
f(x)&=\vec{\boldsymbol{w}}^T\phi(\vec{\boldsymbol{x}})+b\\
&=\sum\limits_{i=1}^N\alpha_iy_i\phi(\vec{\boldsymbol{x_i}})^T\phi(\vec{\boldsymbol{x}})+b \\
&=\sum\limits_{i=1}^N\alpha_iy_i\kappa(\vec{\boldsymbol{x_i}},\vec{\boldsymbol{x}})+b
\end{array}
\tag{3.3}
$$

3.2 核函数

如果知道映射$\phi( · )$ 的具体形式,那么可以写出核函数 $\kappa(·,·)$ 的具体形式。但现实任务中通常不知道映射的形式,不用构造映射 $\phi(\vec{\boldsymbol{x}})$ 能否直接判断一个给定的函数是不是核函数?或者说,函数 $\kappa(·,·)$ 满足什么条件才能称为核函数?有定理表明,只要一个对称函数所对应的核矩阵半正定,它就能作为核函数使用。

我们希望样本在新空间内线性可分,新空间的好坏就很重要。核函数的选择能够决定新空间的好坏,有几种常用的核:线性核、多项式核、高斯核、拉普拉斯核、Sigmoid核。在核的选择上有一些基本的经验,例如对文本数据通常采用线性核,情况不明时可先尝试高斯核。


----------over----------


文章标题:SVM原理

文章作者:Ge垚

发布时间:2018年05月07日 - 13:05

最后更新:2018年06月03日 - 21:06

原始链接:http://geyao1995.com/SVM原理/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。