Support Vector Machine(支持向量机)-机器学习基础

内容总结自自花书《deep learning》Chapter 5，由英文版翻译而来。英文版官网可以免费查阅：http://www.deeplearningbook.org/

支持向量机(Support Vector Machine,SVM)是监督学习中一种极具影响力的方法。这种模型与logistic regression相同，都是由线性函数${w\text{w}w}^{\top }x\text{x}x+b$推导而来的。但与线性回归不同的是，支持向量机不提供概率，只输出一个类别。SVM在${w\text{w}w}^{\top }x\text{x}x+b$为正数时预测其为正阳性类，反之，SVM在${w\text{w}w}^{\top }x\text{x}x+b$为负数时则预测其为负阴性类(针对二元分类而言，译者注)。

支持向量机的一个关键创新在于核技巧(kernel trick)。这种核技巧包含了观察到众多机器学习算法都完全能被写成样本之间点积(dot product)的形式。

该函数(5.83)相对x是非线性的，但是$\varphi (x\text{x}x)$和$\alpha \text{α}\alpha$之间是线性的。基于核的函数和使用$\varphi (x\text{x}x)$对所有输入进行数据预处理是完全等价的，之后在一个新的转换后的空间内学习一个线性模型。

核技巧由于以下两个原因是非常强有效的。第一，它使得我们能够学习一个关于x的非线性函数模型，并且保证可以使用凸优化技巧高效收敛。这是因为我们考虑固定$\varphi$和只优化$\alpha \text{α}\alpha$，也即，优化算法可以将决策函数看作在不同的空间内是线性的的。第二，核函数k通常采用的是实现方式会比简单的构造两个$\varphi (x\text{x}x)$向量并显式点积在计算上会高效得多。

在大多数情况下，$k(x\text{x}x,x^{\prime }\text{x′}{x}^{\prime })$都是一个非线性的，可解的x的函数即使$\varphi (x\text{x}x)$是不可解的。

常用的核是高斯核(Gaussian kernel):
高斯核也被称作radial basis function(RBF)核，它因其值在从u射出指向v的直线上降低而得名。

我们可以将高斯核看作是模板匹配(template matching)：

支持向量机并不是唯一的可以被核技巧(kernel trick)增强的算法，其他线性模型也可以以这样的形式被增强。这类使用核技巧的算法被称作核机器(kernel machine)或者核方法(kernal machine)。

核机器的一个主要缺陷在于计算决策函数的代价对于训练样本数目是线性增长的。支持向量机可以通过学习一个包含了很多0的$\alpha \text{α}\alpha$向量来减轻这个缺陷的影响。分类一个新的样本只需要针对含有非0${\alpha }_i$的训练样本计算核函数。这些训练样本被称作支持向量(support vector)。

核机器(kernel machine)也会在数据集庞大时面临高计算成本的问题。使用泛型核的核机器很难良好泛化。现在深度学习的出现就是旨在克服核机器的这些限制。当前深度学习的复兴是从Hinton et al.(2006)证明了一个神经网络能在MNIST benchmark上胜过使用RBF核的SVM开始的。