数据挖掘3.1支持向量机——引言

3.1 What’s special in an SVM?
3.1 SVM 有什么特别之处？

SVM (Support Vector Machines)支持向量机是另一种线性分类器，就像感知器。我们研究它是因为，它比感知器更好，并且有理论可以证实这一点。

前提背景

Empirical Risk Minimization 经济风险最小化

到目前为止，我们的机器学习模型是以下（经验误差）最小化：

$X_{train}：N\ast d$
$Y_{train}：N\ast 1$ 是(+1/-1)
$f:z$
This is called ERM (Empirical risk minimization) or training data error minimization.
这个完全从训练集数据学习得到误差最小化的过程，叫经验风险最小化。另一个名字是 训练数据错误最小化。

经济风险参数

下列线性分类器哪个更好？

可以看出，每个分类器都没有比另外几个更好，因为它们的误差都是0。

我们来看下面这两个分类器

噪声容忍度

理想的情况下，输入的微小变化不应该导致输出的巨大变化。因为现实中总会存在一些误差，这些误差可能会导致输入特征空间出现微小的扰动，，这些误差不应该改变红色方块的输出标签。

红线：数据波动，就分类错了，$<0$ 变成$>0$了
绿线：数据波动，没有影响

从这个角度看，绿色是一个更好的分类器，至少它对于这个特定的训练数据集更稳健。因为它不会因为输入的微小变化而改变输出。所以，我们可以说，绿色判别器更好的原因是因为它几乎位于这两个类的点中间。

对这两个类来说，绿色判别器，与数据点距离最大的边界对、噪声容忍度更高、泛化能力更强。我们已经讨论过它如何对噪声有更好的容忍度（输入中的微小变化对绿线生成标签的影响不如红线生成标签的影响大）

泛化能力

绿线的泛化能力比红线更好。

假设 测试数据例子follow 数据密度。也就是测试示例遵循与训练数据相同的数据分布。显然还是绿色更好。它以0误差对这两个类别进行分类，而且它与两个类别之间的距离最大，这就是我们接下来要介绍的，maximum margin，最大边距。

为什么这是一个合理的假设？
因为如果这个假设不成立，我们可能无法进行非常正确的分类。如果测试示例与训练示例差异很大，是无法进行泛化的。

这个假设技术上称为，平滑smoothness，或者更准确的说，叫 the independent and identically distributed 独立同分布。

margin 边距

线性分类器的边界在到达数据点之前可以增加的宽度称为线性分类器的边距。
边距越大，分类器就越健壮。因为它们对微小变化的免疫力越强，这样训练集中的微小变动就不会使得翻转它们的标签。

perceptron 感知器和支持向量机之间的主要区别： 感知器不能保证最大边距，因此没有最好的泛化能力。支持向量机不仅会减少error，并且会提供最大边距。感知器很大可能给出红线，而支持向量机是绿线。所以支持向量机是一个更好的近似器。

我们将尝试开发一个数学公式，引导得到绿线模型。

正则化

具有大边距的分类器具有一个属性：
Small changes in $x$ should cause small changes in output. $x$ 的微小变化应该导致输出的微小变化——正则化
small margin means low regularization as well. 边距小意味着正则化程度低。
边距大意味着正则化程度高。

一个分类器的正则化越高越好，因为这样的分类器很稳定。在技术的角度，就是分类器或者机器学习模型的权重较小。

也就是 $|w|$较小。$x$的变化对整个$f(x)$的影响就会小。

到现在为止，我们希望训练数据集进行误差最小化，感知器算法可以做到这一点。但我们已经看到，感知器算法会导致较小的边距，会导致由于误差产生的噪声的容忍度较差。并且它对未见过的测试样本的泛化能力也较差。

为了解决这个问题，我们需要良好或高度的正则化，或者说获得更大的边距，同时我们还需要较小的权重。因此我们现在有两个标准，第一我们应该最小化训练误差，在这个基础上，第二我们应该进行正则化。正则化（regularization）加上经验误差最小化（empiricial error mininization）的概念是由一位名为Vladimir vapnek的杰出科学家在1960s首次提出。 他说，经验误差最小化并不能保证在未见过的测试集上具有良好的泛化能力或良好的噪声容忍度。我们应该在误差最小化之外做更多的事情，我们现在在做两件事情，一件是empirical error minimization经验误差最小化，另一件是regularization 正则化，这被称为structural risk minimization 结构风险最小化。这个想法，构成了支持向量机的理论基础。