Support Vector Machines
Perceptron and Linear Separability
假设存在一个 linear decision boundary，它可以完美地对 training dataset 进行分割。 那么，经由上述 Perceptron Algorithm 计算，它将返回哪一条 linear separator？
当 linear separator（即一个给定的超平面）的 margin \(\gamma\) 越大，则该模型的归纳与概括的性能越强。从几何的角度（二维）的角度来理解非常直观，我们需要这么一条 linear separator，即，它既能对 training dataset 进行完美的分割，同时，我们希望距它最近的数据点距它的距离最大化（如上图中间的那根直线）。否则，如果存在一个数据点距该 linear separator 的距离不是那么远，从直觉来说，围绕在该数据点附近且与它 label 相同的一个新数据点随意体现出的一个随机波动，将使得这个新数据点越过 linear separator，导致分类错误。
因此，现在的问题是，如何将 margin 纳入考量以求得这条最佳的 linear boundary？支持向量机将很好地解决这个问题。
Motivation（Why SVM？）
以下是 SVM 体现出的眼见的优势：
SVM 返回一个 linear classifier，并且由于其算法使 margin solution 最大化，故这个 linear classifier 是一个稳定的解。
对 SVM 稍加改变，则能提供一种解决当数据集 non-separable 情况的方法。
SVM 同样给出了进行非线性分类的隐性方法（implicit method，即上述的 kernel transformation）。
SVM Formula
假设存在一些 margin \(\gamma \in \Gamma\) 使得 training dataset \(\mathcal{S} = \mathcal{X} \times \mathcal{Y}\) 线性可分（但注意 linear separator 不一定穿过空间的原点）。
那么，decision boundary：