机器学习-支持向量机

支持向量机总体是由一个合页损失函数和一个核函数组成

合页损失函数

由于函数形状像一个合页，故命合页损失函数，下图为合页损失函数的图形。

二分类问题求解分为三个步骤，第一步为定义函数

$g(x)= \begin{cases} f(x)>0, & \text {output= +1} \\ f(x)<0, & \text{output= -1} \end{cases}$

上述定义的函数，其输出由f(x)决定，当f(x)大于零时，输出为+1，当f(x)小于零时，输出为-1。第二步是通过损失函数判断函数的好坏。我们定义损失函数如下：

$L(f)=\sum_nI(g(x^n)\not \neq \hat y^n)$

$x^n$表示训练集中第n个数据，I代表指示函数，当它的输入为True的时候，输出1；否则输出0。也就是说，当我们的函数g预测的结果和实际结果一样的时候就没有损失，不一样的时候才有损失。但是这个损失函数是不可微分的，就无法用梯度下降的方法来优化。这时我们用另一个近似的函数来表示：

$L(f)=\sum_nI(f(x^n),\hat y^n)$

那这个损失函数是什么样的呢？我们来看一个这样的图形。

它的横轴是 $\hat{y}^nf(x)$，$\hat{y}^n$ 可以是+1或-1，我们希望当 $\hat{y}^n=+1$ 时，$f(x)$ 的值正的越大越好；当 $\hat{y}^n=-1$ 时，$ f(x)$ 的值负的越大越好。整体就 $\hat{y}^nf(x)$ 的值越大越好。纵轴当成损失的话，越往右，$\hat y^nf(x)$ 越大，损失越小。

损失函数的理想情况是两条黑线。当 $g(x^n) = \hat{y}^n$ 时损失为0，这时 $\hat{y}^nf(x)$ 为正数；当 $g(x^n)\neq \hat{y}^n$ 时损失为1，这时$\hat{y}^nf(x)$ 为负数；但是这样是无法微分的。我们把I用l来取代。

这时 l 有很多选择，比如：

$Square Loss = \begin{cases} if \hat y^n=1, & \text {f(x) close to 1} \\ if \hat y^n=-1, & \text{f(x) close to -1} \end{cases}$

这个是平方损失，可以写成: $l(f(x^n),\hat{y}^n) = (\hat{y}^nf(x^n) - 1)^2$ 。当 $\hat{y}^n=1$ 时，上式就是 $(f(x^n) - 1)^2$ ；当 $\hat{y}^n=-1$ 时，上式就是 $(-f(x^n) - 1)^2 = (f(x^n) + 1)^2$ 。所以，当 $\hat{y}^n=1$ 时，$ f(x^n)$ 要和 1 越接近越好；当 $f(x^n) = -1$ 时，$f(x^n)$ 要和 -1 越接近越好。

平方损失函数图形是上面红色的抛物线，但是它是不合理的，因为当 $\hat{y}^nf(x)$ 很大的时候，竟然有个很大的损失。还有一种选择是Sigmoid + Square Loss:

$Sigmoid + Square Loss = \begin{cases} if \hat y^n=1, & \text {σ(f(x)) close to 1} \\ if \hat y^n=-1, & \text{σ(f(x)) close to -1} \end{cases}$

它的图形是上面蓝色的线，我们讲过，在逻辑回归中，不会用平方损失，而是用交叉熵。我们这里替换成交叉熵。这里 $\sigma(f(x))$ 代表了一个分布，Ground Truth(指的是真实情况)代表另一个分布。

这两个分布之间的交叉熵，就是要最小化的损失值。

它可以写成：$l(f(x^n),\hat{y}^n) =\ln(1 + e^{-(\hat{y}^nf(x))})$ 。它是上面绿色的线，这里除了 $ln2$ ，这不是影响这个函数图形走势，但是可以让它变成理想损失的上边界(upper bound)，我们虽然无法最小化理想的损失，但是可以最小化它的上边界。

这个式子是合理的，当 $\hat{y}^nf(x)$ 趋近于正无穷大时， $e^{-\infty}=\frac{1}{e^\infty}=0$ ;当 $\hat{y}^nf(x)$ 趋近于负无穷大时，$e^{\infty}=\infty=>ln(1+\infty)=\infty$ 我们可以比较用交叉熵和平方损失的曲线，这样就可以知道为什么选择交叉熵。

我们把 $\hat{y}^nf(x) $ 从 -2 移动到 -1 时，交叉熵的那条线变化很明显，而平方损失的那条线变化很小。当 $\hat{y}^nf(x)$ 负的很大的时候，调整这个值，对总损失影响不大，这样训练出来的效果很不好。而交叉熵调整的时候影响很大。
最后看下什么是Hinge Loss

它的式子是：$l(f(x^n),\hat{y}^n) =\max(0,1 - \hat{y}^nf(x))$。当 $\hat{y}^n=1$ 时，只要 $f(x) > 1$，它的损失就是 0；而当 $\hat{y}^n = -1$ 时，$f(x)<-1$，它的损失才会是 0。

把折页损失的图像画出来，是上面紫色的那条线。在这条线上，只要 $\hat{y}^nf(x) > 1$ 时，就已经够好了，损失是0。

线性SVM

$f(x)=∑_iw_ix_i+b={w\brack b}⋅{1\brack x}=w^Tx$

上面这个线性等式可以看成是两个向量的内积。接下来我们把${w\brack b}$用新的 w 来表示，把 ${x\brack 1}$ 用新的x xx来表示，最终得到 $w^T x$ 这样当$f(x) > 0f(x)>0时属于一个类别；当 $f(x) < 0$ 时属于另一个类别。

此时，SVM采用的损失函数是折页损失。$l(f(x^n),\hat{y}^n) =\max (0,1 - \hat{y}^nf(x))$

通常还会加上正则化 $\lambda ||w||_2$ ，这个损失函数是凸函数。而 $\lambda ||w||_2$ 也是凸函数。把它们加起来仍然是一个凸函数。

这个函数其实不一定是线性的，如果不是线性的，也可以用梯度下降的方法来训练。

接下来看下如何用梯度下降来训练SVM。

我们的损失函数长这样，它是合页损失，这里为了简单，去掉了正则项。
只要可以对这个合页损失函数做微分，就能做梯度下降。

它有两个区域，可以是0是最大者；或 $1 - \hat{y}^nf(x^n)$ 是最大者。

我们现在要最小化$L(f)$，要选择一个最小的 $x^n$ 让 L 能最小，就是要选个 $x^n$ 让 $\varepsilon^n 越小越好。 $\varepsilon^n$ 的限制是大于等于0，以及大于等于 $1-\hat{y}^nf(x^n)$，让$ \varepsilon^n$ 最小的方法，就是让 $\varepsilon^n$ 等于 0 和 $1-\hat{y}^nf(x^n)$ 最大者。所以，当要最小化的时候，这两个红框是相等的。

Dual Representation

我们把能最小化损失函数的权值写成 $w^*$，它其实是我们的数据线性组合

$w^*=\sum_n\alpha^*_nx^n$

如果初始的w是个零向量，每次在更新w ww的时候，后面加上的就是数据点的线性组合。

w可以写成$\alpha X$，这时我们可以改写f(x)的式子，这里把 $(x^n \cdot x)$写成一个函数 $K(x^n,x)$这个函数就叫核函数(Kernel function)。

我知道可以这样写以后，未知的就变成了 $\alpha_n$，那在第二步和第三步的问题就变成了找一组最好的 $\alpha_n$，让总损失最小。

核技巧(Kernel Trick)

如果数据是非线性的，直接使用SVM，得不到好的结果。此时需要特殊处理，使用一个变换将原空间的数据映射到新空间中，变成线性可分的，然后再使用SVM。

所以，把 $x,z$ 先做特征转换后，再做内积等于它们先做内积的平方。有时直接计算$(x\cdot z)^2$会比先做特征转换，再做内积要快很多。比如 x,z都是 k 维的向量，我们想把它们投影到更高维的平面。在更高维的平面，要考虑向量元素中两两之间的关系。

如果用核技巧的话，可以轻易的计算出 $\phi(x) \cdot \phi(z)$ 的结果，怎么算呢，通过 $(x\cdot z)^2$ 就可以。

上式中可以x xx集中到一边就可以得到 $\phi(x)$ ，同理 z 也是一样。

还有更惊人的是RBF Kernel。

RBF Kernel

径向基函数核(Radial basis function Kernel,RBF Kernel)式子是这样的：

这个可以衡量 x,z 的相似度，如果 x,z 是一样的话，Kernel的值就是 1；如果 x,z 完全不一样的话，值就是 0。也可以写成两个高纬度的向量做内积。在这个式子中 $\phi(*)$ 的结果可以是无穷多维的，但是我们无法做到无穷多维向量的内积。可以看成是两个无穷长的向量做内积，最后得到的结果就是这个K(x,z)的结果。

Sigmoid Kernel

K(x,z)=tanh(x⋅z)

当我们把训练数据 x 代入 f 中的时候，其实是计算 x 和训练数据集中所有数据的 $K(x^n,x)$ 然后再乘上 $\alpha_n$ 如果用Sigmoid Kernel 的时候就是

如果我们用Sigmoid Kernel，这个f(x)可以想象成只有一个隐藏层的神经网络。x会和所有的 $x^n$ 做内积，就好像是有个神经元它的权值就是某笔数据 $x^n$ ,它的输入就是向量x。把 $x^1$ 当做第一个神经元的权值， $x^2$ 作为第二个神经元的权值

然后把它们都通过双曲正切(tanhx ,hyperbolic tangent) 得到输出后，再乘上$\alpha$，最后累加起来就得到f(x)的结果。

$\tanh x = \frac{\sinh x}{\cosh x} = \frac{e^x - e^{-x}}{e^x + e^{-x}}$

其实有了核技巧后，我们可以直接设计这个核函数，而不用考虑$\phi(x),\phi(z)$长什么样子。

什么时候可以这样呢，假设你的输入数据 x 是结构数据，比如序列，此时很难表示成 $\phi(x)$。

我们可以直接定它的核函数，我们知道核函数其实就是投影到高维的内积，所以核函数是个类似相似度(similarity)的东西。

所以可以定一个描述x , z x,zx,z相似度的函数，哪怕它们是结构数据，只要知道怎么计算两个序列之间的相似度，就可以把这个相似度当成核函数来使用。

不是所有的相似度函数都可以，有个Mercer’s 理论可以告诉你哪些函数可以。这个理论可以检查你定出来的相似度函数背后有没有两个向量做内积。

比如在语音上，假设你要分类的对象是声音讯号(Audio segment)。

每个声音讯号可以用向量序列(vector sequnce)来描述它。每段声音讯号的长度不一样，所以向量序列的长度也不一样。

假设现在给你一段声音讯号，要你判断说话者的情绪(高兴、生气…)。

因为声音讯号的长度不一，所以无法直接用一个向量来描述，这时可以直接定相似函数(核函数K(x,z))。

SVM和深度学习

我们知道深度学习的前几层可以看成适特征转换，最后一层可以看成是线性分类器。其实SVM做的事情也是很类似的。SVM先用一个核函数把特征转换到高维空间上面，然后就可以用线性分类器进行分类。