SVM支持向量机

SVM是一种二分类模型。基本模型定义是，在特征空间中间隔最大的线性分类器。

• 线性可分支持向量机（硬间隔支持向量机）
• 线性支持向量机（软间隔支持向量机）
• 非线性支持向量机

线性可分支持向量机

将输入的n维空间，分成两部分。
假设输入空间和输出空间是不同的两部分，输入空间为欧氏空间或离散集合，特征空间为欧氏空间或者希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射成特征空间中的特征向量。

• 假设给定训练数据 T={(x1,y1),(x2,y2),...,(xn,yn)}T = \{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}T={(x1​,y1​),(x2​,y2​),...,(xn​,yn​)},其中$x_i$为第 i 个特征向量。$y_i=+1$，称$x_i$是正实例，$y_i=+1$称$x_i$是负实例
• 假设给定实例是线性可分的，给定一个超平面，能将给定数据集的正负实例完全的划分到超平面的两侧。
• 当数据集线性可分的时候，存在无数个超平面将政府数据集分开。线性可分支持向量机利用间隔最大化，求最优超平面，这时，解是唯一的。

函数间隔和几何间隔

超平面：Hyperplane ${\omega }^{T}x+b=0\omega 是平面的法向量$
如果该预测点距离超平面较远，则证明确信预测是正确的，如果该预测点距离超平面较近，则对预测结果不那么确信。
函数间隔

$|{\omega }^{T}x+b|$能相对的表示点x距离超平面的远近，并且${\omega }^{T}x+b$的符号与 y 的符号是否一致也能表明分类是否正确，因此使用$y({\omega }^{T}x+b)$来表示分类得正确行与可信度。
定义：定以超平面( w , b ),数据点( xi, yi ),函数间隔为
$${\hat{\gamma }}_i=y_i(\omega x_i+b)$$
整个数据集的函数间隔
超平面（w，b）关于整个数据集T的间隔为，T中所有间隔的最小值。
$$\hat{\gamma }=\underset{i=1,...,m}{\min }{\hat{\gamma }}_i$$

但是当对w,b进行同步放缩的时候，超平面 ${\omega }^{T}x+b=0$ 并没有改变，但是函数间隔 ${\hat{\gamma }}_i=y_i(\omega x_i+b)$却被放缩了。
几何间隔
对超平面的法向量加以约束，对其规范化，$\Vert w\Vert =1$,使得区间不能被随意放缩，成为几何间隔
$${\gamma }_i=y_i(\frac{\omega }{\Vert w\Vert }{x}_i+\frac{b}{\Vert w\Vert })$$

$$\gamma =\underset{i=1,...,m}{\min }{\gamma }_i$$
几何间隔和函数间隔关系

$$\gamma =\frac{\hat{\gamma }}{\Vert w\Vert }$$

间隔最大化

• 超平面（Hyperplane）实际上作为区分正负样本的决策平面。
• 如果给定的分界间隔越大，那么最决策的确信度越高。例如数据距离超平面非常远，分类的确信度会更高。
• 有一定数量的超平面，哪一个是最优的？
  $$\underset{w,b}{\max }\underset{i}{\min }{\gamma }_i$$

上述问题等价于：
$$\begin{gathered} \underset{w,b}{\max }\gamma \\ s.t.y_i(\frac{\omega }{\Vert w\Vert }{x}_i+\frac{b}{\Vert w\Vert })\ge \gamma \end{gathered}$$
则,下面通过对w，b的一些放缩，变换要求解的最优化函数，但是并不影响最终的优化结果，这里的放缩改变形式是为了方便求解。

$$\begin{gathered} \underset{w,b}{\max }\gamma \\ s.t.y_i(\omega x_i+b)\ge \gamma \Vert w\Vert \end{gathered}$$
通过放缩w，可以使得${\min }_i{y}_i(w{x}_i+b)=1$,将w,b的放缩对于目标函数的优化没有影响
$$\gamma =\underset{i}{\min }{y}_i(\frac{\omega }{\Vert w\Vert }{x}_i+\frac{b}{\Vert w\Vert })=\frac{1}{\Vert w\Vert }$$
则
$$\begin{gathered} \underset{w,b}{\max }\frac{1}{\Vert w\Vert } \\ s.t.y_i(\omega x_i+b)\ge 1\forall i \end{gathered}$$

至此，放缩w，b的工作完成。
我们要求解在约束条件下的${\max }_{w,b}\frac{1}{\Vert w\Vert }$,等价于最小化$\Vert w\Vert$,由于$\Vert w\Vert$存在根号，因此为了方便的去除根号我们使用$\Vert w{\Vert }^2$
注：||w||,w的2-范数，详看文章末尾

$$\begin{gathered} \underset{w,b}{\min }\Vert w{\Vert }^2 \\ s.t.y_i(\omega x_i+b)-1\ge 0\forall i \end{gathered}$$

这是一个凸二次优化问题（cnovex quadratic programming）QP问题

• 凸函数在上一篇已经提到了，$y=x^2$就是一个凸函数
  关于凸二次优化问题，可以自行百度，不在讨论范围内.
  现有的通用的解凸二次优化问题的方法非常低效，特别是面对非常大的数据集的时候。

最优化问题（Optimization Problem）

在约束最优化问题中，常常利用拉格朗日对偶性，将原始问题转换为对偶问题，通过求解对偶问题而得到原始问题的解。
原始问题
$$\begin{gathered} \underset{w}{\min }f(w) \\ s.t.g_i(w)\le 0,i=1,...k \\ {h}_j(w)=0,j=1,...,l \end{gathered}$$

$w\in {\mathbb{R}}^n$为变量，$p^{\ast }$为最优值。
拉格朗日函数：$L:{\mathbb{R}}^n\times {\mathbb{R}}^k\times {\mathbb{R}}^l\to \mathbb{R}$
$$L(w,\alpha ,\beta )=f(w)+\sum _{i=1}^k{\alpha }_i{g}_i(w)+\sum _{j=1}^l{\beta }_j{h}_j(w)$$
$$\begin{gathered} {\alpha }_i是拉格朗日乘子，g_i(w)\le 0 \\ {\beta }_j是拉格朗日乘子，h_j(w)=0 \end{gathered}$$
拉格朗日对偶函数：$G:{\mathbb{R}}^k\times {\mathbb{R}}^l\to \mathbb{R}$

$$\begin{gathered} G(\alpha ,\beta )=\underset{w\in D}{\inf }L(w,\alpha ,\beta ) \\ =\underset{w\in D}{\inf }\left(f(w)+\sum _{i=1}^k{\alpha }_i{g}_i(w)+\sum _{j=1}^l{\beta }_j{h}_j(w)\right) \end{gathered}$$

• G是 $L(w,\alpha ,\beta )$的下确界
• G是一个凹函数，并且对g，h是什么函数没有要求。且G有唯一最大值。

下界的正确性
如果$\alpha \ge 0(\alpha 中每一个元素都大于等于0)$，那么$G(\alpha ,\beta )\le p^{\ast },其中p^{\ast }是原问题的最优值。$
证明 如果 $\tilde{w}$ 是 可行的并且 $\alpha \ge 0$，那么
$$f(\tilde{w})\ge L(\tilde{w},\alpha ,\beta )\ge \underset{w\in D}{\inf }L(w,\alpha ,\beta )=G(\alpha ,\beta )$$
(这里比较显然，因为$g_i(w)\le 0,a_i\ge 0,所以f(\tilde{w})\ge L(\tilde{w},\alpha ,\beta )$)

在所有的可行解中，minimizing的最优值 $p^{\ast }\ge G(\alpha ,\beta )$

$p^{\ast }$是$f(w)$的最小值，但是$f(w)$的最小值依旧大于等于 $G(\alpha ,\beta )$ 。

拉格朗日对偶问题
$$\begin{gathered} ma{x}_{\alpha ,\beta }G(\alpha ,\beta ) \\ s.t.\alpha \ge 0,\forall i=1,...,k \end{gathered}$$

• 通过拉格朗日对偶函数，寻找$p^{\ast }$的最优下界
• 凸优化问题的最优值记作$d^{\ast }$
• $\alpha ,\beta$都在函数G的可行域内

弱对偶
$$d^{\ast }=ma{x}_{\alpha ,\beta }G(\alpha ,\beta ),且d^{\ast }\le q^{\ast }$$

• 弱对偶一般都是成立的
• 可以用来求解困难问题的非平凡的下界。（非平凡这个词对非数学专业的还不好解释。平凡”英文是trivial，就是没什么用的意思，比如一些微分方程很容易看出有零解，但是零解并不是我们关心的，或者说求出来这个零解并没有什么用，我们更关心的是非平凡（nontrivial）解，也就是非零解。）
• optimal duality gap(最优对偶间隙——瞎翻译) ：$p^{\ast }-d^{\ast }$

强对偶
$$d^{\ast }=p^{\ast }$$

至此，我们将原问题 $\min f(w)$ 转换成了 $ma{x}_{\alpha ,\beta }G(\alpha ,\beta )s.t.\alpha \ge 0,\forall i=1,...,k$

互补松弛条件

假设在$w^{\ast }$处 $f(w)$ 取得最优值 $p^{\ast }$, $({\alpha }^{\ast },{\beta }^{\ast })$是是偶函数$G(\alpha ,\beta )$取得最优值点。
如果强对偶成立，那么
$${\alpha }_i{g}_i(w\ast )=0\forall i=1,2,...,k$$
证明
$$\begin{gathered} f(w^{\ast })=G({\alpha }^{\ast },{\beta }^{\ast }) \\ =\underset{w}{\inf }(f(w)+\sum _{i=1}^k{\alpha }_i^{\ast }{g}_i(w)+\sum _{j=1}^l{\beta }_j^{\ast }{h}_j(w)) \\ \le f(w^{\ast })+\sum _{i=1}^k{\alpha }_i^{\ast }{g}_i(w^{\ast })+\sum _{j=1}^l{\beta }_j^{\ast }{h}_j(w^{\ast })\le f(w^{\ast }) \end{gathered}$$
将上式中得不等式换成等式，要成立必有：
$$\sum _{i=1}^k{\alpha }_i{g}_i(w^{\ast })=0$$
因为$a_i\ge 0g_i(w)\le 0$,
$${\alpha }_i{g}_i(w^{\ast })=0$$

KKT条件

如果强对偶成立$p^{\ast }=d^{\ast }$, 下面这些条件都将成立
1、极值点：$w^{\ast }$ 是$f(w)$得极值点。
$$▽f(w^{\ast })+\sum _{i=1}^k{\alpha }_i▽g_i(w^{\ast })+\sum _{j=1}^l{\beta }_j▽h_j(w^{\ast })=0$$
2、主可行：
$$\begin{gathered} g_i(w^{\ast })\le 0,\forall i=1,...,k \\ {h}_j(w^{\ast })=0\forall j=1,...,l \end{gathered}$$
3、对偶可行性：
$${\alpha }_i^{\ast }\ge 0,\forall i=1,...,k$$
4、互补松弛条件：
$${\alpha }_i^{\ast }{g}_i(w^{\ast })=0,\forall i=1,...，k$$
但是以上的这些条件是否是强对偶的充分必要条件？
对于凸优化，如果强对偶成立，KKT条件是充分必要条件。

如果找到了$\alpha ,\beta$满足KKT条件，解决的对偶问题，也就解决了原问题。

最优间隔分类器（optimal margin classifier）

主问题是凸优化问题
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2 \\ s.t.y^{(i)}(w^T{x}^{(i)}+b)\ge 1,\forall i \end{gathered}$$
凸优化问题，一般都是强对偶的，自然满足KKT条件。由于原问题，比较复杂，将其转换成对偶问题，求解对偶问题。
拉格朗日算子（Largrangian）
$$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^m{\alpha }_i(y^i(w^T{x}^{(i)}+b)-1)$$
拉格朗日对偶函数（Lagrange dual function）
$$G(\alpha )=\underset{w,b}{\inf }L(w,b,\alpha )$$

对偶问题公式（dual problem formulation）
$$\begin{gathered} \underset{\alpha }{\max }\underset{w,b}{\inf }L(w,b,\alpha ) \\ s.t.{\alpha }_i\ge 0\forall i \end{gathered}$$

依据KKT条件，要使得$L(w,b,\alpha )$关于w,b最小
$${▽}_{w}L(w,b,\alpha )=w-\sum _{i=1}^m{\alpha }_i{y}^{(i)}{x}^{(i)}=0\to w=\sum _{i=1}^m{\alpha }_i{y}^{(i)}{x}^{(i)}$$
$$\frac{\partial }{\partial b}L(w,b,\alpha )=\sum _{i=1}^m{\alpha }_i{y}^{(i)}=0$$

把w代入方程得到
$$G(\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^m{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j(x^{(i)}{)}^T{x}^{(j)}$$
并且满足${\sum }_{i=1}^m{\alpha }_i{y}^{(i)}=0$并且$a_i\ge 0$
对偶问题公式
$$\begin{gathered} \underset{\alpha }{\max }G(\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^m{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j(x^{(i)}{)}^T{x}^{(j)} \\ s.t.{\alpha }_i\ge 0\forall i \\ \sum _{i=1}^m{\alpha }_i{y}^{(i)}=0 \end{gathered}$$
这是一个二次规划问题，我们可以用MATLAB中现有的quadprog函数求解。

我们利用现有的QP问题解法直接去接，不用关心 ${\alpha }^{\ast }$具体怎么求解的

SVM求解结果

当我们通过QP问题，求解出${\alpha }^{\ast }$后，由于先前的KKT条件
$$w^{\ast }=\sum _{i=1}^m{\alpha }_i{y}^{(i)}{x}^{(i)}$$
如何求解$b^{\ast }$?
由于${\alpha }_i^{\ast }{g}_i(w^{\ast })=0,即{\alpha }_i^{\ast }(y^{(i)}(w^{\ast T}{x}^{(i)}+b)-1)=0$
∀i{i:αi∗>0}y(i)(w∗Tx(i)+b)−1=0\forall i\quad\{i:\alpha_i^* > 0\}\quad y^{(i)}(w^{*T}x^{(i)} + b )-1 = 0∀i{i:αi∗​>0}y(i)(w∗Tx(i)+b)−1=0
因此，∀i{i:αi∗>0}\forall i\quad\{i:\alpha_i^* > 0\}∀i{i:αi∗​>0},
$$b^{\ast }=y^{(i)}-w^{\ast T}{x}^{(i)}$$
并且由于KKT条件中 ${\alpha }_i^{\ast }{g}_i(w^{\ast })=0,g_i(w^{\ast })=y^i(w^T{x}^{(i)}+b)-1$ ,
因此只有少量的${\alpha }_i^{\ast }$不为0。也只有${\alpha }_i^{\ast }$不为零的点对于求解有作用，也就是当点处在margin 边界的时候，这些数据样本被称为support vector,正如下图中被标注出来的数据点。

那么重新定义一下$w^{\ast }$
$$w^{\ast }=\sum _{s\in S}{\alpha }_S^{\ast }{y}^{(s)}{x}^{(s)}$$
S代表了所有的Support Vectors

非线性可分支持向量机(Kenel Methods 核函数)

之前讨论的SVM是线性可分的，但是有些情况下，不存在线性的超平面。

Kernels:使得线性模型能够用在非线性的情况下

• 1、将数据映射到能显示出线性的更高维度
• 2、在新的空间中，使用线性模型
• 3、映射相当于改变feature的表示

Feature Mapping 特征映射

举个例子

在一维的状态现，自然没有分界线，但是当我们将其映射到高维，x→{x,x2}x\rightarrow \{x,x^2 \}x→{x,x2}

在新的表示下，数据变得线性可分，这里我们将一维映射到二维，数据就线性可分了。

另一个例子

这个例子中，数据是2维的，但是并不能找到，一个线性的分类。但是当我们将他从二位，向3维空间映射后。数据就变得线性可分了。
x={x1,x2}→z={x12,2x1x2,x22}x = \{x_1,x_2\} \rightarrow z = \{x_1^2,\sqrt{2}x_1x_2,x_2^2\}x={x1​,x2​}→z={x12​,2​x1​x2​,x22​}

考虑如下的映射函数$\varphi$,将对让样本x={x1,x2,...,xn}x = \{x_1,x_2,...,x_n\}x={x1​,x2​,...,xn​}进行映射

问题：将维度从n维映射到（n-1)n/2维，那可能会导致维度爆炸，并且可能无法储存的下这么多的feature

• 计算映射本身就非常低效，特别是新的维度特别高的情况
• 存储和使用映射后的features，耗费大

核方法

我们假设给定了一个核函数K ，对于输入的两个向量 x, z 进行如下的计算

上面的核函数K，隐含地定义了一个向高维的映射$\varphi$。

那么一个核函数，就和一个高维空间的映射相关联。
$K(x,z)=\varphi (x{)}^T\varphi (z)$

F 是一个向量空间，且在上面定义了点积运算(a dot product)，这样的F被称为希尔伯特空间（Hilbert Space）
并不是所有的函数都能当作核函数，必须要满足 Mercer‘s Condition

Mercer‘s Condition

如果K1,K2是核函数，那么如下的也是核函数

• K(x,z) = K1(x,z) + K2(x,z)
• K(x,z) = aK1(x,z)
• K(x,z) = K1(x,z)K2(x,z)

核矩阵 Kernel Matrix

如果给定了m 个samples{x(1),x(2),...,x(m)}\{x^{(1)},x^{(2)},...,x^{(m)}\}{x(1),x(2),...,x(m)},
$$K_{ij}=K(x^{(i)},x^{(j)})=\varphi (x^{(i)}{)}^T\varphi (x^{(j)})$$

常用的Kernels

• 线性核
  $K(x,z)=x^{T}z$
• 二次核
  $K(x,z)=(x^{T}z{)}^{2}or(1+x^{T}z{)}^2$
• 多项式核
  $K(x,z)=(x^{T}z{)}^{d}or(1+x^{T}z{)}^d$
• 高斯核
  $K(x,z)=exp(-\frac{\Vert x-z{\Vert }^2}{2{\sigma }^2})$
• sigmoid核
  $K(x,z)=tanh(a{x}^T+c)$

使用核的优点

• 核方法将线性的模型应用到非线性
• 核 K(x,z) 表示在高维空间中的点乘
• 对任意的学习方法，如果样本间的计算只有点乘，就可以被核化。
• 无需计算中间的高维feature

kernelized SVM Training

SVM 拉格朗日对偶，将点乘运算，替换为核函数运算

在高维空间中的分界面为$w^{\ast T}\varphi (x)+b^{\ast }$
将之前的 x 都替换为 $\varphi (x)$，来计算$w^{\ast },b^{\ast }$
$$\begin{gathered} w^{\ast }=\sum _{i:{\alpha }_i^{\ast }>0}{\alpha }_i^{\ast }{y}^{(i)}\varphi (x^{(i)}) \\ {b}^{\ast }=y^{(i)}-w^{\ast T}\varphi (x^{(i)}) \\ =y^{(i)}-\sum _{j:{\alpha }_j^{\ast }>0}{\alpha }_j^{\ast }{y}^{(j)}{\varphi }^T(x^{(j)})\varphi (x^{(i)}) \\ =y^{(i)}-\sum _{j:{\alpha }_j^{\ast }>0}{\alpha }_j^{\ast }{y}^{(j)}{K}_{ij} \end{gathered}$$

进行分类

$$\begin{gathered} y=sign(w^{\ast T}\varphi (x)+b^{\ast }) \\ =sign(\sum _{i:{\alpha }_i^{\ast }>0}{\alpha }_i^{\ast }{y}^{(i)}{\varphi }^T(x^{(i)})\varphi (x)+b^{\ast }) \\ =sign(\sum _{i:{\alpha }_i^{\ast }>0}{\alpha }_i^{\ast }{y}^{(i)}K(x^{(i)},x)+b^{\ast }) \end{gathered}$$

线性支持向量机 （软间隔 soft-margin SVM ）

允许误分类的情况。在之前的情况中，我们都使得数据点落在margin之外，或者margin上

对于线性不可分的情况，我们放松限制条件，

${\xi }_i被称为松弛变量$
尽管我们允许误分类但是，我们希望被误分类的数量尽可能地少，因此我们使得松弛变量的和 ${\sum }_i{\xi }_i$ 尽可能小

软间隔SVM公式

其中C控制了一个权重：

• C越小，会使得 $\frac{1}{2}\Vert w{\Vert }^2,$更小导致 margin更大
• C越大，误分类的情况会越少，但是会导致更小的margin

拉格朗日函数

$$L(w,b,\xi ,\alpha ,r)=\frac{1}{2}{w}^{T}w+C\sum _{i=1}^m{\xi }_i-\sum _{i=1}^m{\alpha }_i[y^{(i)}(w^T{x}^{(i)}+b)-1+{\xi }_i]-\sum _{i=1}^m{r}_i{\xi }_i$$
这里面有两组g函数，即小于等于约束
KKT条件

• ${▽}_{w}L(w,b,\xi ,\alpha ,r)=0\to w^{\ast }={\sum }_{i=1}^m{\alpha }_i^{\ast }{y}^{(i)}{x}^{(i)}$
• ${▽}_{b}L(w,b,\xi ,\alpha ,r)=0\to {\sum }_{i=1}^m{\alpha }_i{y}^{(i)}=0$
• ${▽}_{\xi }L(w,b,\xi ,\alpha ,r)=0\to {\alpha }_i^{\ast }+r_i^{\ast }=C\forall i$
• ${\alpha }_i^{\ast },r_i^{\ast },{\xi }_i^{\ast }\ge 0,for\forall i$
• $y^{(i)}(w^T{x}^{(i)}+b)-1+{\xi }_i\ge 0$
• ${\alpha }_i[y^{(i)}(w^T{x}^{(i)}+b)-1+{\xi }_i]=0$
• $r_i{\xi }_i=0$

对偶问题

和之前相同，求解QP问题，得到${\alpha }_i^{\ast }$, 用KKT条件求解出$w^{\ast },b^{\ast }$

当$0<{\alpha }_i^{\ast }<C$
$$y^{(i)}(w^{\ast T}{x}^{(i)}+b^{\ast })=1$$
$$b^{\ast }=\frac{{\sum }_{i:0<{\alpha }_i^{\ast }<C}(y^{(i)}-w^{\ast T}{x}^{(i)})}{{\sum }_{i=1}^{m}1(0<{\alpha }_i^{\ast }<C)}$$

由KKT条件得来的推论

• 当${\alpha }_i^{\ast }=0,y^{(i)}(w^{\ast T}{x}^{(i)}+b^{\ast })\ge 1$
• 当${\alpha }_i^{\ast }=C,y^{(i)}(w^{\ast T}{x}^{(i)}+b^{\ast })\le 1$
• 当$0<{\alpha }_i^{\ast }<C,y^{(i)}(w^{\ast T}{x}^{(i)}+b^{\ast })=1$