Support Vector Machine简单笔记。 特征空间上的间隔最大的线性分类器。学习策略是间隔最大化，转化为一个凸二次规划问题的求解。

SVM概览

线性分类器

逻辑回归的图像和公式如下，预测的分类为1的概率。

$$ h_\theta(x) = g(\theta^Tx), \quad g(z) = \frac{1}{1+e^{-z}}, \quad g(z) = \begin{cases} 1, & z\ge 0 \\ -1, & z < 0 \\ \end{cases} $$ $$y=\{\begin{array}{ll}1,& h_{\theta }(x)\ge 0.5,\mathrm{即}{\theta }^{T}x\ge 0\\ 0,& h_{\theta }(x)<0.5,\mathrm{即}{\theta }^{T}x<0\end{array}$$

其中${\theta }^{T}x=w^{T}x+b=0$ 是一个超平面。 用分类函数表示$f(x)=w^{T}x+b$ 。 $w$是这个超平面的法向量。

即对于任意一个x，有如下预测类别：

$$\hat{y}=\{\begin{array}{ll}1,& f(x)\ge 0\\ -1,& f(x)<0\end{array}$$

函数间隔与几何间隔

函数间隔

超平面$w^{T}x+b=0$确定后， $|w\cdot x+b|$表示点x到平面的距离，表示分类可靠性。距离越远，分类越可信。$y$与$w\cdot x+b$的符号的一致性表示分类的正确性。

超平面$(w,b)$关于样本点$(x_i,y_i)$的**函数间隔${\hat{\gamma }}_i$**如下：

$${\hat{\gamma }}_i=y_i(w^T\cdot x_i+b)$$

超平面关于所有样本点的函数间隔$\hat{\gamma }$ ：

$$\hat{\gamma }=min{\hat{\gamma }}_i$$

函数间隔的问题：w和b成比例改变，超平面未变，但函数间隔已变。

几何间隔

对函数间隔除以法向量的二范数，则得到超平面与点$(x_i,y_i)$的几何间隔${\gamma }_i$ ：

$${\gamma }_i=\frac{{\hat{\gamma }}_i}{\parallel w\parallel }=\frac{y_i(w^T\cdot x_i+b)}{\parallel w\parallel }$$

超平面关于所有样本点的几何间隔：

$$\gamma =min{\gamma }_i$$

几何间隔才是直观上点到超平面的距离。

最大间隔分类器

分类时，超平面离数据点的间隔越大，分类的确信度也越大。 所以要最大化这个几何间隔，目标函数如下：

$$L=\underset{w,b}{max}\gamma ,s.t,{\gamma }_i\ge \gamma$$

用函数间隔$\hat{\gamma }$描写为：

$$L=\underset{w,b}{max}\frac{\hat{\gamma }}{\parallel w\parallel },s.t,{\hat{\gamma }}_i\ge \hat{\gamma },\text{ 其中 }{\hat{\gamma }}_i=y_i(w^T\cdot x_i+b)$$

函数间隔$\hat{\gamma }$的取值并不会影响最优化问题的解。 $\lambda w,\lambda b\to \lambda \hat{\gamma }$

目标函数

取函数间隔为1，$\hat{\gamma }=1$， 则有目标函数：

$$L=\underset{w,b}{max}\frac{1}{\parallel w\parallel },s.t,y_i(w^T{x}_i+b)\ge 1$$

支持向量是虚线边界上的点，则有：

$$\{\begin{array}{ll}{y}_i(w^T{x}_i+b)=1,& \mathrm{支}\mathrm{持}\mathrm{向}\mathrm{量}\\ y_i(w^T{x}_i+b)>1,& \mathrm{其}\mathrm{他}\mathrm{点}\end{array}$$

分类

$$\hat{y}=\{\begin{array}{ll}1,& f(x)\ge 0\\ -1,& f(x)<0\end{array}$$

线性SVM

拉格朗日对偶性

1 原始问题

$f(x),c_i(x),h_j(x)$都连续可微。

最优化：

$$\underset{x\in R}{min}f(x)$$

有很多个约束条件（不等式约束和等式约束）：

$$c_i(x)\le 0,h_j(x)=0$$

求解原始问题

将约束问题无约束化。

引入拉格朗日函数，其中${\alpha }_i(\ge 0)$和${\beta }_j$是拉格朗日乘子

$$L(x,\alpha ,\beta )=f(x)+\sum {\alpha }_i{c}_i(x)+\sum {\beta }_j{h}_j(x)$$

定义关于$x$的函数**${\theta }_p(x)$**：

$${\theta }_p(x)=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )$$$${\theta }_p(x)=\{\begin{array}{ll}f(x),& x\mathrm{满}\mathrm{足}\mathrm{约}\mathrm{束}\\ +\mathrm{\infty },& \mathrm{其}\mathrm{他}\end{array}$$

$f(x)$求最小，则对${\theta }_p(x)$求最小。

原始问题： 先固定x，优化出参数$\alpha ,\beta$，再优化x。

$$\underset{x}{min}{\theta }_p(x)=\underset{x}{min}\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )$$

所以原始最优化问题 变为 拉格朗日函数的极小极大问题。

定义原始问题的最优解$p^{\ast }$ ：

$$p^{\ast }=\underset{x}{min}{\theta }_p(x)$$

2 对偶问题

定义关于$\alpha ,\beta$的函数${\theta }_d(\alpha ,\beta )$

$${\theta }_d(\alpha ,\beta )=\underset{x}{min}L(x,\alpha ,\beta )$$

对偶问题：先固定参数$\alpha ,\beta$ ，优化出x，再优化出参数。 先优化x。

$$\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}{\theta }_d(\alpha ,\beta )=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}\underset{x}{min}L(x,\alpha ,\beta )$$

原始问题： 先固定x，优化出参数$\alpha ,\beta$，再优化x。先优化参数。

$$\underset{x}{min}{\theta }_p(x)=\underset{x}{min}\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )$$

定义对偶问题的最优值：

$$d^{\ast }=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}{\theta }_d(\alpha ,\beta )$$

3 原始问题与对偶问题的关系

因为：

$${\theta }_d(\alpha ,\beta )=\underset{x}{min}L(x,\alpha ,\beta )\le \underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )={\theta }_p(x)$$

定理1：如果原始问题与对偶问题均有最优值，则有：$d^{\ast }\le p^{\ast }$

$$d^{\ast }=\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}\underset{x}{min}L(x,\alpha ,\beta )\le \underset{x}{min}\underset{\alpha ,\beta :{\alpha }_i\ge 0}{max}L(x,\alpha ,\beta )=p^{\ast }$$

推论1：如果$d^{\ast }=p^{\ast }$， 那么$x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }$分别是原始问题和对偶问题的最优解。

通过对偶问题，来解决原始问题。

4 KKT条件

满足什么条件，才能使$d^{\ast }=p^{\ast }$呢 ？

首先满足下面的大条件：

假设$f(x)$和$c_i(x)$都是凸函数， $h_j(x)$是仿射函数；假设不等式约束$c_i(x)$是严格可行的。

定理2：则存在解，$x^{\ast }$是原始问题的最优解，${\alpha }^{\ast },{\beta }^{\ast }$是对偶问题的最优解。 并且：

$$d^{\ast }=p^{\ast }=L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })$$

KKT条件：则$x^{\ast }$是原始问题、${\alpha }^{\ast },{\beta }^{\ast }$是对偶问题的最优解的充分必要条件是**$x^{\ast },{\alpha }^{\ast },{\beta }^{\ast }$满足下面的KKT条件**：

$$\begin{array}{rl}& \mathrm{偏}\mathrm{导}\mathrm{为}0\mathrm{条}\mathrm{件}\\ & {\mathrm{\nabla }}_{x}L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0\\ & {\mathrm{\nabla }}_{\alpha }L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0\\ & {\mathrm{\nabla }}_{\beta }L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0\\ & \mathrm{约}\mathrm{束}\mathrm{条}\mathrm{件}\\ & c_i(x^{\ast })\le 0\\ & h_j(x^{\ast })=0\\ & {\alpha }_i^{\ast }\ge 0\\ & \mathrm{K}\mathrm{K}\mathrm{T}\mathrm{对}\mathrm{偶}\mathrm{互}\mathrm{补}\mathrm{条}\mathrm{件}\\ & {\alpha }_i^{\ast }{c}_i(x^{\ast })=0\end{array}$$

由KKT对偶互补条件可知，若${\alpha }_i^{\ast }>0$， 则$c_i(x^{\ast })=0$ 。SVM推导会用到。

若${\alpha }_i>0$， 则对应的$x_i$是支持向量， 有$y_i(w^{\ast }\cdot x+b^{\ast })=1$。 所有的非支持向量，都有${\alpha }_i=0$。

原始问题到对偶问题

先前的目标函数：

$$J=\underset{w,b}{max}\frac{1}{\parallel w\parallel },s.t,y_i(w^T{x}_i+b)\ge 1$$

最大变为最小，则有原始问题如下。目标函数是二次的，约束条件是线性的。所以是个凸二次规划问题。

$$J=\underset{w,b}{min}\frac{1}{2}\parallel w{\parallel }^2,s.t,y_i(w^T{x}_i+b)\ge 1$$

构造拉格朗日函数 ：

$$L(w,b,\lambda )=\frac{1}{2}\parallel w{\parallel }^2-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1)$$

原始问题

$${\theta }_p(w,b)=\underset{{\lambda }_i\ge 0}{max}L(w,b,\alpha )$$$$p^{\ast }=\underset{w,b}{min}{\theta }_p(w,b)=\underset{w,b}{min}\underset{{\lambda }_i\ge 0}{max}L(w,b,\alpha )$$

对偶问题

$${\theta }_d(\alpha )=\underset{w,b}{min}L(w,b,\alpha )$$$$d^{\ast }=\underset{{\alpha }_i\ge 0}{max}{\theta }_d(\alpha )=\underset{{\alpha }_i\ge 0}{max}\underset{w,b}{min}L(w,b,\alpha )$$

我们知道$d^{\ast }\le p^{\ast }$， 有时相等。原始问题可以转化为对偶问题求解，好处是：近似解，好求解。

求解对偶问题

拉格朗日函数：

$$L(w,b,\lambda )=\frac{1}{2}\parallel w{\parallel }^2-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1)$$

化简后：

$$L(w,b,\lambda )=\frac{1}{2}\parallel w{\parallel }^2-\sum _{i=1}^n{\alpha }_i{y}_i{w}^T{x}_i-\sum _{i=1}^n{\alpha }_i{y}_{i}b+\sum _{i=1}^n{\alpha }_i$$

目标函数：

$$d^{\ast }=\underset{{\alpha }_i\ge 0}{max}{\theta }_d(\alpha )=\underset{{\alpha }_i\ge 0}{max}\underset{w,b}{min}L(w,b,\alpha )$$

主要是三个步骤：

• 固定参数$\alpha$， 求 极小化$\underset{w,b}{min}L(w,b,\alpha )$的w和b
• 带入w和b，对$L$求参数$\alpha$ 的极大化
• 利用SMO算法求解对偶问题中的拉格朗日乘子$\alpha$

**1 极小求出w和b $\underset{w,b}{min}L(w,b,\alpha )$ **

对w和b求偏导，使其等于0。

$$\frac{\partial L}{\partial w}=w-\sum _{i=1}^n{\alpha }_i{y}_i{x}_i\stackrel{\mathrm{令}}{=}0\to w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i$$$$\frac{\partial L}{\partial b}=-\sum _{i=1}^n{\alpha }_i{y}_i\stackrel{\mathrm{令}}{=}0\to \sum _{i=1}^n{\alpha }_i{y}_i=0$$

特别地范式求导：$\frac{\partial \parallel w{\parallel }^2}{\partial w}=2w$

$$\frac{\partial \parallel w{\parallel }^2}{\partial w}=w$$

把上面两个结论，带入原式进行化简，得到：

$$\begin{array}{rl}L(w,b,\alpha )& =\frac{1}{2}{w}^{T}w-\sum _{i=1}^n{\alpha }_i{y}_i{w}^T{x}_i-\sum _{i=1}^n{\alpha }_i{y}_{i}b+\sum _{i=1}^n{\alpha }_i\\ & =\frac{1}{2}{w}^T\sum _{i=1}^n{\alpha }_i{y}_i{x}_i-w^T\sum _{i=1}^n{\alpha }_i{y}_i{x}_i-b\sum _{i=1}^n{\alpha }_i{y}_i+\sum _{i=1}^n{\alpha }_i\text{(带入w，提出b，带入0)}\\ & =-\frac{1}{2}{\left(\sum _{i=1}^n{\alpha }_i{y}_i{x}_i\right)}^T\left(\sum _{i=1}^n{\alpha }_i{y}_i{x}_i\right)+\sum _{i=1}^n{\alpha }_i(\mathrm{只}\mathrm{有}x\mathrm{是}\mathrm{向}\mathrm{量}，\mathrm{直}\mathrm{接}\mathrm{转}\mathrm{置})\\ & =-\frac{1}{2}\left(\sum _{i=1}^n{\alpha }_i{y}_i{x}_i^T\right)\left(\sum _{i=1}^n{\alpha }_i{y}_i{x}_i\right)+\sum _{i=1}^n{\alpha }_i\\ & =\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{i=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\end{array}$$

得到只用$\alpha$表示的拉格朗日函数：

$$L(w,b,\alpha )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{i=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

2 求出对$\alpha$的极大 $\underset{{\alpha }_i\ge 0}{max}{\theta }_d(\alpha )=\underset{{\alpha }_i\ge 0}{max}\underset{w,b}{min}L(w,b,\alpha )$

对偶问题 如下：

目标函数：

$$\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{i=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

约束条件：

$$\begin{array}{rl}& {\alpha }_i\ge 0\\ & \sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

利用SMO算法求出拉格朗日乘子${\alpha }^{\ast }$。

3 求出w和b，得到分离超平面和决策函数

根据前面的公式得到**$w^{\ast }$**：

$$w\ast =\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i{x}_i$$

选一个**${\alpha }_j^{\ast }>0$对应的点**$(x_j,y_j)$ 就是支持向量。由于支持向量**$y_j(w^{\ast }\cdot x+b^{\ast })-1=0$** ，$y_j^2=1$

得到**$b^{\ast }$** ：

$$b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j),\text{(}{x}_i\cdot x_j\text{是向量内积，后面同理)}$$

通过公式可以看出，决定w和b的是支持向量， 其它点对超平面是没有影响的。

分离超平面

$$f(x)=\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(x_i\cdot x)+b^{\ast }=0$$

分类决策函数

$$f(x)=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}(\sum _{\mathrm{i}=1}^{\mathrm{n}}{\alpha }_{\mathrm{i}}^{\ast }{\mathrm{y}}_{\mathrm{i}}({\mathrm{x}}_{\mathrm{i}}\cdot \mathrm{x})+{\mathrm{b}}^{\ast })$$

简单总结

目标函数

$$J=\underset{w,b}{min}\frac{1}{2}\parallel w{\parallel }^2,s.t,y_i(w^T{x}_i+b)\ge 1$$

拉格朗日函数

$$L(w,b,\lambda )=\frac{1}{2}\parallel w{\parallel }^2-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1)$$

转化为对偶问题求解， 需要会求解过程、会推导公式。

$$\underset{{\alpha }_i\ge 0}{max}\underset{w,b}{min}L(w,b,\alpha )$$

主要是下面4个求解步骤：十分重要!!!

1. 固定$\alpha$， L对w和b求偏导，得到两个等式
2. 结果带入L，消去w和b，得到只有$\alpha$的L
3. 利用SMO求出${\alpha }^{\ast }$
4. 利用${\alpha }^{\ast }$和支持向量，算出w和b。得出分离超平面和分界函数。

求导后消去w和b，得到L

$$L(w,b,\alpha )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{i=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

利用SMO求得${\alpha }^{\ast }$后， 带回原式，得到w和b：

$$w\ast =\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i{x}_i,b^{\ast }=y_j-\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j),$$

实际上最重要是向量内积来进行决策

$$f(x)=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left(\sum _{\mathrm{i}=1}^{\mathrm{n}}{\alpha }_{\mathrm{i}}^{\ast }{\mathrm{y}}_{\mathrm{i}}({\mathrm{x}}_{\mathrm{i}}\cdot \mathrm{x})+{\mathrm{b}}^{\ast }\right)$$

目标函数

$$\underset{{\alpha }_i\ge 0}{max}L(w,b,\lambda )=\underset{{\alpha }_i\ge 0}{max}\frac{1}{2}\parallel w{\parallel }^2-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1)$$

两种数据点

• 支持向量：红色为0，${\alpha }_i>0$。 后面为0。
• 其它点：红色大于1，${\alpha }_i=0$。 后面为0。

非线性SVM

核函数

问题

大部分数据不是线性可分的，前面的超平面根本不存在。可以用一个超曲面进行分离，这就是非线性可分问题。

SVM可以通过核函数把输入映射到高维特征空间，最终在高维特征空间中构造最优分离超平面。

需要映射和学习线性SVM：

• 把输入映射到特征空间F
• 在特征空间F中使用线性学习器分类

$$f(x)=\sum _{i=1}^n{\alpha }_i^{\ast }{y}_i(\varphi (x_i)\cdot \varphi (x))+b^{\ast }$$

核函数的功能

核函数在特征空间中直接计算内积，就像在原始输入点的函数中一样，两个步骤合二为一：

$$K(x,z)=\varphi (x)\cdot \varphi (z)$$

分类函数：

$$f(x)=\sum _{i=1}^n{\alpha }_i^{\ast }{y}_{i}k(x_i,x)+b^{\ast }$$

对偶问题：

$$\begin{array}{rl}& \underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{i=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}k(x_i,x)\\ & s.t,{\alpha }_i\ge 0,\sum _{i=1}^n{\alpha }_i{y}_i=0\end{array}$$

核函数处理非线性数据

简单例子

上面的数据线性不可分，两个维度(a, b)。 应该用二次曲线(特殊圆)来区分：

$$w_{1}a+w_2{a}^2+w_{3}b+w_4{b}^2+w_{5}ab+b=0$$

看做映射到了五维空间：

$$w_1{z}_1+w_2{z}_2+w_3{z}_3+w_4{z}_4+w_5{z}_5+b=\sum _{i=1}^5{w}_i{z}_i+b=0$$

如下图：（实际映射到了三维空间的图），可以使用一个平面来分开：

问题

五维是由1维和2维进行组合，就可以解决问题。所以对输入数据无脑组合映射到高维可以吗？当然是不可以的。维数太高，根本没法计算，不能无脑组合映射。

核函数的功能

看核函数：

$$k(x_1,x_2)=(x_1\cdot x_2+1{)}^2$$

核函数和上面映射空间的结果是一样的！区别：

• 映射计算：先映射到高维空间，然后根据内积进行计算
• 核函数：直接在原来的低维空间中计算，而不需显示写出映射后的结果。避开了在高维空间中的计算！

常用核函数

1 线性核

$$k(x_1,x_2)=x_1\cdot x_2\text{(原始空间的内积)}$$

目的：映射前和映射后，形式上统一了起来。写个通用模板，再带入不同的核就可以了。

2 高斯核

$$k(x_1,x_2)=\exp (-\frac{\parallel x_1-x_2{\parallel }^2}{2{\sigma }^2})$$

高斯核函数，非常灵活，应用很广泛。可以映射到无穷维。

$\sigma$ 的选择

• 太大：权重衰减快，相当于映射到低维子空间
• 太小：将任意数据线性可分，容易陷入严重过拟合

3 多项式核

$$k(x_1,x_2)=((x_1,x_2)+R{)}^d$$

核函数总结

问题的出现

• 数据线性不可分，要映射到高维空间中去
• 不能无脑低维组合映射到高维空间，维度太大根本没法计算

核函数的功能

• 将特征向由低维向高维的转换
• 直接在低位空间中进行计算
• 实际的分类效果却是在高维上
• 避免了直接在高维空间中的复杂计算

SVM曲线，逻辑回归和决策树是直线。SVM的效果好。

松弛变量软间隔最大化

定义

数据可能有一些噪声特异点outlier导致不是线性可分或者效果不好。 如果不处理outlier，则会非常影响SVM。因为本身支持向量就只有几个。

给每个数据点加上松弛变量${\xi }_i\ge 0$， 使函数间隔+松弛变量大于等于1，即约束条件：

$$y_i(w\cdot x_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

为每个松弛变量${\xi }_i$支付一个代价${\xi }_i$， 新的目标函数和约束条件如下：

$$min\frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^n{\xi }_i$$$$s.t,y_i(w\cdot x_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

惩罚系数C是一个常数

• C大时，对误分类的惩罚增大
• C来调节权衡：使间隔尽量大；误分类点个数尽量少

求解

定义新的拉格朗日函数：

$$L(w,b,\xi ,\alpha ,r)=\frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^n{\xi }_i-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1+{\xi }_i)-\sum _{i=1}^n{r}_i{\xi }_i$$

和前面对偶问题求解一样，求导求解：

$$\frac{\partial L}{\partial w}=0\to w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i$$$$\frac{\partial L}{\partial b}=0\to \sum _{i=1}^n{\alpha }_i{y}_i=0$$$$\frac{\partial L}{\partial \xi }=0\to C-{\alpha }_i-r_i=0$$

带入，得到新的L

$$\underset{\alpha }{max}L=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{i=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)$$

约束条件：

$$0\le {\alpha }_i\le C,\sum _{i=1}^n{\alpha }_i{y}_i=0$$

SVM的深层理解

感知机算法

感知机算法是一个二类分类的线性模型，也是找一个超平面进行划分数据：

$$f(x)=\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}(\mathrm{w}\cdot \mathrm{x}+\mathrm{b})$$

损失函数是所有误分类点到超平面的总距离：

$$\underset{w,b}{min}L(w,b)=-\sum _{x_i\in M}{y}_i(w\cdot x_i+b)$$

可以使用SGD对损失函数进行优化。

当训练数据集线性可分时，感知机算法是收敛的。可以在一定迭代次数上，找到一个超平面，有很多个解。

感知机的超平面不是最优效果，最优是SVM。

损失函数

数据$x$， 预测值$f(x)=\hat{y}$， 真实值$y$。

常见损失

1. 01损失

$$L(y,\hat{y})=\{\begin{array}{ll}1,& y\ne \hat{y}\\ 0,& y=\hat{y}\end{array}$$

2. 平方损失

   $$L(y,\hat{y})=(y-\hat{y}{)}^2$$

3. 绝对损失

   $$L(y,\hat{y})=|y-\hat{y}|$$

4. 对数损失

   $$L(y,\hat{y})=-\log P(y\hat{x})$$

期望损失

期望损失也称为风险函数，需要知道联合概率分布$P(X,Y)$， 一般不知道。

$$R_{\mathrm{e}\mathrm{x}\mathrm{p}}=E_p[L(y,\hat{y})]={\int }_{(x,y)}L(y,\hat{y})P(x,y)\mathrm{d}x\mathrm{d}y$$

经验损失

经验损失也成为经验风险 ，所以监督学习就是要经验风险最小化。

$$R_{\mathrm{e}\mathrm{m}\mathrm{p}}(f)=\frac{1}{N}\sum _{i=1}^{N}L(y_i,{\hat{y}}_i)$$

结构风险最小化

样本数量太小时，容易过拟合。需要加上正则化项，也称为惩罚项。 模型越复杂，越大。

$$R_{\mathrm{s}\mathrm{r}\mathrm{m}}(f)=\frac{1}{N}\sum _{i=1}^{N}L(y_i,{\hat{y}}_i)+\lambda J(f)$$

$\lambda \ge 0$ 是系数，权衡经验风险和模型复杂度。 监督学习，就是要使结构风险最小化。

SVM也是最优化+损失最小。 可以从损失函数和优化算法角度去看SVM、boosting、LR，可能会有不同的收获。

SVM的合页损失函数

从最优化+损失最小的角度去理解SVM。

最小二乘法

最小二乘法，就是通过最小化误差的平方来进行数学优化。对参数进行求偏导，进行求解。

SMO

模型

$$min\frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^n{\xi }_i$$$$s.t,y_i(w\cdot x_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

序列最小最优化SMO (Sequential minimal optimization)，解决求解$\alpha$的问题：

$$\underset{\alpha }{min}L=\frac{1}{2}\sum _{i=1}^n\sum _{i=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-\sum _{i=1}^n{\alpha }_i$$$$s.t,0\le {\alpha }_i\le C,\sum _{i=1}^n{\alpha }_i{y}_i=0$$

如果所有变量的解都满足KKT条件，则最优化问题的解已经得到。

思想

每次抽取两个乘子${\alpha }_1,{\alpha }_2$，然后固定其他乘子，针对这两个变量构建一个子二次规划问题，进行求解。不断迭代求解子问题，最终解得原问题。

选择乘子

${\alpha }_1$选择违反KKT条件最严重的，${\alpha }_2$选择让${\alpha }_1$变化最大的。