机器学习技法-lecture3：Kernel Support Vector Machine

Kernel Support Vector Machine

课程回顾

lecture2中我们主要介绍了对偶SVM的解法及解法需要的条件，本节课我们将主要解决非线性变换导致的过高的计算成本的问题—kernel方法。

Kernel Trick

lecture2中我们通过推导将非线性SVM转化为求解α的QP问题，但是实际上计算层面并没有避免高维空间矩阵的计算问题，这将是我们本节课旨在解决的问题，我们的思路是：将特征转化过程和高维空间的计算过程等两个步骤合并为一个步骤，这样的过程我们称为kernel trick。

我们首先研究最简单的情形即二次多项式的转化过程，我们先对两个点分别做转化然后再相乘，可以得到上面的公式，蒸锅过程我们付出了O(d)而非O(d^2)的计算成本。

我们将特征转化和计算內积两个步骤一起完成的过程函数称为kernel function，相应地我们可以分别计算b和w,并返回相应的指示函数，于是我们得到了kernel SVM ，其相应的计算流程如下。

Polynomial Kernel

接下来我们推导二次多项式变换的一般形式，我们通过对一次系数和二次系数做一定的放缩变换，可以得到一般形式。需要指出的是，这个形式对应的二次变换能做的事情是一致的，但是不同的缩放对应着不同的內积，进而对应着不同的边界，实际应用中K2是常用的形式。

我们可以看到下面是三种不同的参数对应的边界：

更进一步，我们可以通过引入参数(γ,ζ)和Q来将kernel推广到更一般的情形，最后，需要指出的是Q=1的情形即linear kernel的情形，它是最简单的情形甚至不需要通过dual的方式去解决，这往往也是我们需要优先考虑的选择。

Gaussian Kernel

现在我们来思考我们能否使用kernel解决无限多维的转化问题，我们使用一个一维特征的x，使用高斯函数做Taylor展开，我们可以得到下面的结论，可以发现它对应到一个无线维度的特征变换，做一个一般化的推广，我们可以得到Gaussian kernel的形式。

进一步，我们可以总结得到gaussian svm的hypothesis，我们发现他实际上就是以sv为中心的高斯函数的线性组合，我们又把这个函数称为RBF kernel。

学到现在我们发现SVM已经能完成很多事情了，最开始我们只能做hyperplane，随后我们加入了transform,接着为了解决计算效率的问题我们引入了kernel，只做这三步我们没法控制model complexity，而large-margin恰好满足了我们的要求。

于是我们能在较少的hyperplane上做出复杂的边界并且可以使用kernel有效率地完成整个过程，所以我们没必要进行真实的转化在计算，也没必要存储真实的w而只需保存他的表现形式。

最后需要指出的是，SVM也会出现过拟合的，越大的γ对应更尖的高斯函数，当取无穷大的γ时就变成了对每个资料点做辨识，因此应用上不建议使用过大的γ。

Comparison of Kernels

接下来我们分别看看三类kernel的优缺点，首先是linear kernel，毫无疑问这是最简单的kernel也往往是我们首先要考虑使用的kernel，优点是安全和计算速度快，但是他的应用场景往往比较局限，不适用与非线性可分的问题。

polynomial kernel的优点是相对线性核的限制较小，可以认为根据实际情况和经验做Q的限制，缺点是当Q比较大时计算难度大结果不一定可靠，并且它对应着三个参数，选择上的难度较大。

Gaussion kernel无疑是最强大的kernel，同时它的边界在数值复杂度上低于poly,参数也只有一个；但是由于他强大，所以他往往会耗费更多的时间，也需要提防它过于强大而导致的过拟合。

本节课我们主要建立了kernel SVM，其中我们首先介绍了kernel trick,然后介绍了三种常见的kernel并总结了他们的优缺点。

——课堂小结