Support Vector Machine

支持向量机(SVM)有两个特点：SVM=铰链损失(Hinge Loss)+核技巧(Kernel Method)

注：建议先看这篇博客了解SVM基础知识后再看本文的分析

Hinge Loss

Binary Classification

先回顾一下二元分类的做法，为了方便后续推导，这里定义data的标签为-1和+1

$f(x)>0$ $g(x)=1$ $f(x)<0$ $g(x)=-1$ ，表示属于第二类别
$\sum \delta(g(x^n)\ne \hat y^n)$ $\delta=1$ $x$ $\hat y$ $\delta=0$ ，但这个式子不可微分，无法使用梯度下降法更新参数
$l(f(x^n),\hat y^n)$ 来表示损失函数

$\hat y^n f(x)$ ，我们希望横坐标越大越好：

$\hat y^n>0$ $f(x)$ 越正越好
$\hat y^n<0$ $f(x)$ 越负越好

$\hat y^n f(x)$ 越大的时候，纵坐标loss要越小，横坐标越小，纵坐标loss要越大

ideal loss

$L(f)=\sum\limits_n \delta(g(x^n)\ne \hat y^n)$ $\hat y^n f(x)>0$ $\hat y^n f(x)<0$ ，则loss=1，如下图中加粗的黑线所示，可以看出该曲线是无法微分的，因此我们要另一条近似的曲线来替代该损失函数

square loss

$l(f(x^n),\hat y^n)=(\hat y^n f(x^n)-1)^2$

$\hat y^n=1$ $f(x)$ $(f(x^n)-1)^2$
$\hat y^n=-1$ $f(x)$ $(f(x^n)+1)^2$
$\hat y^n f(x)$ 很大的时候有一个更大的loss

sigmoid+square loss

$l(f(x^n),\hat y^n)=(\sigma(\hat y^n f(x^n))-1)^2$

$\hat y^n=1$ $\sigma (f(x))$ $(\sigma(f(x))-1)^2$
$\hat y^n=-1$ $\sigma (f(x))$ $(\sigma(f(x)))^2$
在逻辑回归的时候实践过，一般square loss的方法表现并不好，而是用cross entropy会更好

sigmoid+cross entropy

$l(f(x^n),\hat y^n)=ln(1+e^{-\hat y^n f(x)})$

$\sigma (f(x))$ 代表了一个分布，而Ground Truth则是真实分布，这两个分布之间的交叉熵，就是我们要去minimize的loss
$\hat y^n f(x)$ 很大的时候，loss接近于0
$\hat y^n f(x)$ 很小的时候，loss特别大
$ln2$ 的曲线，使之变成ideal loss的upper bound，且不会对损失函数本身产生影响
我们虽然不能minimize理想的loss曲线，但我们可以minimize它的upper bound，从而起到最小化loss的效果

cross entropy VS square error

为什么cross entropy要比square error要来的有效呢？

$\hat y^n$ $f(x)$ 非常不匹配导致横坐标非常负的时候，loss的梯度要很大，这样才能尽快地通过参数调整回到loss低的地方
对sigmoid+square loss来说，当横坐标非常负的时候，loss的曲线反而是平缓的，此时去调整参数值对最终loss的影响其实并不大，它并不能很快地降低
形象来说就是，“没有回报，不想努力”
而对cross entropy来说，当横坐标非常负的时候，loss的梯度很大，稍微调整参数就可以往loss小的地方走很大一段距离，这对训练是友好的
形象来说就是，“努力可以有回报""

Hinge Loss

$l(f(x^n),\hat y^n)=\max(0,1-\hat y^n f(x))$

$\hat y^n=1$ $\max(0,1-f(x))$
- $f(x)>1$ ，loss就会等于0
$\hat y^n=-1$ $\max(0,1+f(x))$
- $f(x)<-1$ ，loss就会等于0
$f(x)>1$ $f(x)<-1$ $f(x)$ 有一个很大的值

$\hat y^n f(x)>1$ $\hat y^n f(x)>0$ ，表示已经得到了正确答案，但Hinge Loss认为这还不够，它需要你继续往1的地方前进

$\hat y^n f(x)>1$ 时，它与Ideal loss近乎是完全贴近的

$\hat y^n f(x)>1$ 的区间上，cross entropy还想要往更大的地方走，而Hinge loss则已经停下来了，就像一个的目标是”还想要更好“，另一个的目标是”及格就好“

在实作上，两者差距并不大，而Hinge loss的优势在于它不怕outlier，训练出来的结果鲁棒性(robust)比较强

Linear SVM

model description

$f(x)=\sum\limits_i w_i x_i+b=w^Tx$ $\left [\begin{matrix}w\\b \end{matrix}\right ]$ $\left [\begin{matrix}x\\1 \end{matrix}\right ]$ $w$ $x$ ，这么做可以把bias项省略掉

$L(f)=\sum\limits_n l(f(x^n),\hat y^n)+\lambda ||w||_2$

这是一个convex的损失函数，好处在于无论从哪个地方开始做梯度下降，最终得到的结果都会在最低处，曲线中一些折角处等不可微的点可以参考NN中relu、maxout等函数的微分处理

对比Logistic Regression和Linear SVM，两者唯一的区别就是损失函数不同，前者用的是cross entropy，后者用的是Hinge loss

事实上，SVM并不局限于Linear，尽管Linear可以带来很多好的特质，但我们完全可以在一个Deep的神经网络中使用Hinge loss的损失函数，就成为了Deep SVM，其实Deep Learning、SVM这些方法背后的精神都是相通的，并没有那么大的界限

gradient descent

尽管SVM大多不是用梯度下降训练的，但使用该方法训练确实是可行的，推导过程如下：

another formulation

前面列出的式子可能与你平常看到的SVM不大一样，这里将其做一下简单的转换

$L(f)=\sum\limits_n \max(0,1-\hat y^n f(x))+\lambda ||w||_2$ $L(f)=\sum\limits_n \epsilon^n+\lambda ||w||_2$ 来表示

$\epsilon^n=\max(0,1-\hat y^n f(x))$

$\epsilon^n\geq0$ $\epsilon^n\geq1-\hat y^n f(x)$ $\geq$ 则取到等号的限制

$L(f)$ $\geq$ 就要取到等号，两者就是等价的

此时该表达式就和你熟知的SVM一样了：

$L(f)=\sum\limits_n \epsilon^n+\lambda ||w||_2$ $\hat y^n f(x)\geq 1-\epsilon^n$ $\hat y^n$ $f(x)$ $\epsilon^n$ $\epsilon^n$ 的作用就是放宽1的margin，也叫作松弛变量(slack variable)

这是一个QP问题(Quadradic programming problem)，可以用对应方法求解，当然前面提到的梯度下降法也可以解

Kernel Method

explain linear combination

你要先说服你自己一件事：实际上我们找出来的可以minimize损失函数的参数，其实就是data的线性组合

w^*=\sum\limits_n \alpha^*_n x^n

你可以通过拉格朗日乘数法去求解前面的式子来验证，这里试图从梯度下降的角度来解释：

$w$ $w=w-\eta\sum\limits_n c^n(w)x^n$ $w$ $x$ $w$ $x$ 的Linear Combination

$c^n(w)$ $x^n$ $w$ $w$ $x^n$ ，就叫做support vector

$\alpha_n$ $x^n$ $x^n$ 的样本点移除掉，对结果也是没有影响的，这可以增强系统的鲁棒性；而在传统的cross entropy的做法里，每一笔data对结果都会有影响，因此鲁棒性就没有那么好

redefine model and loss function

$w$ $x^n$ 的线性组合之后，我们就可以对原先的SVM函数进行改写：

w=\sum_n\alpha_nx^n=X\alpha \\ f(x)=w^Tx=\alpha^TX^Tx=\sum_n\alpha_n(x^n\cdot x)

$x$ $x^n$ $\alpha_n$ 为0，因此计算量并不是很大

$x^n$ $x$ $x^n\cdot x=K(x^n,x)$

$f(x)= \sum\limits_n\alpha_n K(x^n,x)$ $\alpha_n$

$\alpha_n$ ，让loss最小，此时损失函数改写为：

L(f)=\sum\limits_n l(\sum\limits_{n'} \alpha_{n'}K(x^{n'},x^n),\hat y^n)

$x$ $x$ $z$ $K(x,z)$ $K(x,z)$ ，就可以去对参数做优化了，这招就叫做Kernel Trick

Kernel Trick

$x=\left[ \begin{matrix}x_1\\x_2 \end{matrix} \right]$ ，先要对它做feature transform，然后再去应用Linear SVM

$\phi(x)=\left[ \begin{matrix}x_1^2\\\sqrt{2}x_1x_2\\ x_2^2 \end{matrix} \right]$ ，此时Kernel function就变为：

K(x,z)=\phi(x)\cdot \phi(z)=\left[ \begin{matrix}x_1^2\\\sqrt{2}x_1x_2\\ x_2^2 \end{matrix} \right] \cdot \left[ \begin{matrix}z_1^2\\\sqrt{2}z_1z_2\\ z_2^2 \end{matrix} \right]=(x_1z_1+x_2z_2)^2=(\left[ \begin{matrix}x_1\\x_2 \end{matrix} \right]\cdot \left[ \begin{matrix}z_1\\z_2 \end{matrix} \right])^2=(x\cdot z)^2

$x$ $z$ 做特征转换+内积，就等同于在原先的空间上先做内积再平方，在高维空间里，这种方式可以有更快的速度和更小的运算量

RBF Kernel

$K(x,z)=e^{-\frac{1}{2}||x-z||_2}$ $\phi(x)\cdot \phi(z)$ $\phi(*)$ 的维数是无穷大的，所以我们直接使用Kernel trick计算，其实就等同于在无穷多维的空间中计算两个向量的内积

将Kernel展开成无穷维如下：

$x$ $\phi(x)$ $z$ $\phi(z)$ ，也就是说，当你使用RBF Kernel的时候，实际上就是在无穷多维的平面上做事情，当然这也意味着很容易过拟合

Sigmoid Kernel

$K(x,z)=\tanh(x,z)$

$f(x)$ $x^1$ $x^n$ $x$ $\alpha^1$ $\alpha^n$ $f(x)$

其中neuron的数目，由support vector的数量决定

Design Kernel Function

既然有了Kernel Trick，其实就可以直接去设计Kernel Function，它代表了投影到高维以后的内积，类似于相似度的概念

$x$ $z$ $x$ $z$ $K(x,z)$ $x$ $z$ 经过转换后的内积，这样就省去了转换特征这一步

$x$ $x$ $\phi(x)$ 了，但是只要知道怎么计算两者之间的相似度，就有机会把这个Similarity当做Kernel来使用

我们随便定义一个Kernel Function，其实并不一定能够拆成两个向量内积的结果，但有Mercer's theory可以帮助你判断当前的function是否可拆分

$K(x,z)$ 来做Kernel Trick的示例：

SVM vs Deep Learning

这里简单比较一下SVM和Deep Learning的差别：

deep learning的前几层layer可以看成是在做feature transform，而后几层layer则是在做linear classifier
SVM也类似，先用Kernel Function把feature transform到高维空间上，然后再使用linear classifier
在SVM里一般Linear Classifier都会采用Hinge Loss