Large-Margin Separating Hyperplane
题目翻译为中文的意思大体上是 最大余量分类超平面。本节主要讲解如何确定该最佳分类超平面。
首先，我们回顾一下之前讲过的Linear Classfication ：有$\circ$和$\times$，我们用一条直线将$\circ$和$\times$分开，或者在高维空间中使用超平面将其分开。数学上，将资料拿来计算一个加权和，根据和的正负预测$\circ$和$\times$。
现在，给定一个线性可分的资料，则会有很多条线将和分开，但是下图中的那条线会更好呢？
PLA(Perceptron learning algorithm,For binary classification解决是非问题)会选哪一条线与PLA看到的错误有关，因此PLA得到哪一条线不定。从之前的理论来看，三条线似乎也没什么区别，例如从VC Bound来看：
$$E_{out}(w)\leqslant E_{in}(w) + \Omega(H) $$
其中$E_{in}(w)$为训练样本上的错误率，三条线都满足；$\Omega(H)$为复杂度，都是线，因此复杂度都为d+1。但是我们的直觉告诉我们最右边是最好的线。
一种原始的解释：
假设我们已经拿到原始资料，即图上的点，但是在测试的时候我们拿到跟原始资料相近的资料(测量误差、资料收集等造成)，下图中灰色的x。所以，测试资料可能会和训练资料有点出入。
假设我们绝对相信我们的训练资料，若果有误差，则我们人为最好的预测为将测试资料预测的与训练资料很接近(不完全一样)。
上图中左边与右边最大的差别就在于对测量误差的容忍度，点距离线越远则容忍度越好(tolerate more noise)，进而可以避免过拟合(more robust to overfitting)。
或者换个角度，看这条线有多胖（能涨出去多少），倾向于选择胖的线。
robustness = fatness: distance to closest xn
比较胖的线是比较好的。goal: find fattest separating hyperplane
在分类正确的基础上，找出最胖、最强壮(鲁棒)的线。
目标是：
我们要找出一条线，首先这条线可以将$\circ$和$\times$分开(线性可分)，然后取最胖的一条线，即计算所有点到线的距离，取其中最小的距离。也就是下面的公式所描述的：
fatness: formally called margin：
最胖的线，术语上叫“margin”，余量，留白的多少。
correctness: yn = sign(w^T x_n)
算出来的分数是正的还是负的，相乘是同号(分类正确)就可以。
goal: find largest-margin separating hyperplane：寻找边界最宽，能够完全分开的线（超平面）。
参考资料
- 台大林轩田《机器学习基石》学习笔记5：线性模型一（PLA/pocket、Linearregression ）
- 机器学习技法(林軒田)笔记之一
- 机器学习技法(林軒田)视频与讲稿。
