从SVM到多核学习MKL

SVM是机器学习里面最强大最好用的工具之一，它试图在特征空间里寻找一个超平面，以最小的错分率把正负样本分开。它的强大之处还在于，当样本在原特征空间中线性不可分，即找不到一个足够好的超平面时，可以利用核（kernel）函数，将特征映射到希尔伯特（Hilbert）空间。后者一般维度更高，通过这样的映射之后，样本在新的特征空间中便是线性可分的了。

记得刚刚学习SVM的时候，对“核”这个词很恐惧，一直理解不了它究竟是什么。在看MKL的时候，又经常会遇到“核矩阵”（kernel matrices）这个词。现在说一下我的理解。

刚才说过，我们通过核把特征从低维空间映射到高维空间。举例来说，我们看下面的多项式核函数：

其中x,y是两个样本，他们的特征分别是(x1,x2)，(y1,y2)，通过这个核函数，可以看到二维特征被映射到了六维特征。而且我们也可以理解，这个映射其实就是用一个矩阵A乘以原来的特征(x1,x2)得到的。矩阵A也就是核矩阵了。一个核函数对应一个核矩阵。

我们学过的SVM都是单核（single kernel）的，在使用的时候，需要我们根据经验或试验来选择用哪种核函数、怎样指定它的参数，这样很不方便。另一方面，实际应用当中，特征往往不是single domain的，而是异构的。拿图像分类来说，我们可能用到颜色相关的特征、纹理相关的特征、空间相关的特征，这几类特征对应的最佳的核函数未必相同，让他们共用同一个核函数，未必能得到最优的映射。对这些问题的思考，就引出了MKL。

简单地说，我们给定一些base kernels，比如linear,Polynomial,RBF,Sigmoid，对于每一个，可以指定多组参数，也就是一共有M个base kernels，我们想用它们的线性组合来作为最终的核函数。通过training，得到这个线性组合中每个kernel的权重d（weight）。由于融合了各种kernel，可以照顾到异构的特征；由于自动学习权重，我们就不需要费脑子想究竟用哪一个核哪一种参数，把可能的核、参数都拿过来，组合着来用就可以了。

与传统的单核SVM的不同，就是除了要学习w、b之外，还要学习上面提到的权重d。这样的话，decision function, cost function都会有些变化，棘手的是，cost function 的求解不再是一个convex problem，传统的优化方法就不适用了。近年来MKL比较热，很多论文都是在优化方法上面下功夫，企图达到更快的收敛速度、更好的解。具体的优化方法就比较复杂了，略去。

多核线性组合，最经典的是simpleMKL，也被作为MKL的具体实现，应用在了计算机各领域。为了使MKL应用地更广，应对各种特征组合、各种样本量级，后来又有人提出了GMKL，G即Generalized，最优化方法用的是PGD（Projected Gradient Descend）。为了改进收敛效果，Vishwanathan又提出SPG-GMKL(Spectral Projected Gradient)，同时提出了多核的product组合。SPG-GMKL也被后来者视作state-of-art。

除了MKL，还有一个MKB(Multiple Kernel Boosting)，大连理工大学的卢湖川有几篇论文就是用MKB做跟踪。论文生成MKB是基于MKL的，我觉得不然。请看MKB的框架图：

这里的确用到多核，但每一个SVM都是单核的，根本没有用到多核训练的东西。本质上就是训练出M * N个single-kernel SVM，然后用boosting的方法，把这些弱分类器ensemble为一个强分类器。用到的就是传统的SVM加传统的boosting，只是名字新，实质并无新意。

TKDE12 有一篇 MKBoost论文，这应该是正宗的MKB，它提出了一个框架，并提供了几个formulation，然后与MKL做了比较。论文中全是公式，没有看，以后需要的时候再研究吧。

MKL的经典实现有SimpleMKL，Shogun，SPG-GMKL，SMO-MKL，Google一下就可以找到。

如果只是要使用MKL，可以不看论文中的推导，更多的是看看上述几种实现附带的例子；可以看看MKL在跟踪、图像分类中的使用，输入输出是什么；可以看看这个和这个教程，简单易懂。