上一章结束的时候讲到SVM在做优化的时候要计算z_n^Tz_m这一项，这里还要受到VC dimension的约束，同时计算的时候，我们先要把x_n扩展到高阶项，然后相应的计算，这一项计算比较耗费时间，下面就介绍能够更快计算这一项的方法。

以二阶项为例子，上述的式子可以用上述的形式进行化简，这样计算的时候只要先求x^Tx^'的值，那么就可以在x^Tx^'的基础上进行相应的计算，这样就把时间复杂度从O(d^2)降到了O(d)。

接下去就是利用二次项的Kernel Function把q_n,m, b, g_svm表示出来，由于项中已经把VC dimension隐去了，所以这里就避免了对d的依赖。我们利用Kernel对SVM求解的过程如下图所示。

通常在实际应用的时候，我们对x加上一定的系数，使其能化成完全平方式，这样计算起来更容易，同时加入了一个系数，可以更灵活地进行调节。

上图就是系数不同的时候,训练得到的SV也不一样，这里K值越大，那么对Margin的要求也是越大，所以造成了不同的SV点。关于K值的确定就是一个Hyperparameter确定的过程，一般要通过Validation,比如Cross-Validation的过程来确定.

当Q的阶次增加，那么训练的过程就会得到更为复杂的边界，但是要避免Overfit的发生。

线性的Kernel是一个特殊的例子，该计算很快，很容易，我们往往从该Kernel开始进行计算。

接下去介绍的这种Kernel把Xn的维度扩展到无限维，但是计算起来确很方便。那就是Gaussian Kernel

Gaussian Kernel的物理意义可以看作是以在SVs为中心的点上高斯展开的线性组合，所以也可以称作是Radial Basis Function。

 

Gaussian SVM可以看作是无限维度上的线性组合，同时通过large-margin的参数来保证其具有泛化的能力。

下图的第三幅图SVM明显Overfit了.

Linear Kernel的优点是简单，计算快速，容易解释，但是训练对象并不是总是线性可分的。

Polynomial Kernel就比Linear Kernel更少的约束，但是当Q很大的时候,Kernel Function的计算在数值上容易产生误差，同时三个参数来调节起来也比较麻烦。

Gaussian Kernel是最强大的Kernel，因为exp函数是有阶的，所以数值上计算没有Poly那么麻烦，只有一个参数，调节的时候也很方便，但是由于是无限维上的展开，没有w,所以解释上并不那么直观，参数的选取的时候也要考虑Overfit的情况。

 

构成Kernel的充要条件，需要半正定的。

知乎上这个回答解释半正定矩阵还是很有意思的：

https://www.zhihu.com/question/22098422