SVM是机器学习里应用最广泛的模型之一，而说起SVM大家一般都会提kernel，有叫kernel function也有叫kernel trick的。这是因为实际的应用中，没有kernel的SVM也就是一个线性分类器，与LR（logstic regression）没有本质的差别，就连目标函数都很相似。线性分类器是指它的__decision boundary__是线性的，但训练数据并不一定能被线性区分开(linearly speratable)，这种情况经常被描述为“__线性模型的表达或拟合能力不够__”。> 注意：这里的线性是相对于特征空间本身的维度而言，比如2维空间对应1维直线，3维空间对应2维平面，n维对应(n-1)维的超平面。人的直观理解一般无法超过3维，所以一般的文章教材都用2维空间来讨论问题。比如左下图的2维空间，两类数据点无法被线性(2维下就是直线)区分，这时候就需要kernel来救场了。kernel所带的解药是什么？最naive的理解是，把数据点从2维空间__映射__到3维或更高维的空间，这样就能线性区分开了，就如右下图所展示的。> 顺便提一下：LR也有类似的trick，使得自身的线性模型能拟合非线性数据，那就是__特征组合__。因此，实际应用中，LR的特征维度会非常大，BAT这种级别的互联网公司，维度动不动搞到十亿甚至百亿维度，各种特征组合占到了主要部分。另外，其实kernel并不是SVM的专属，其也可以应用到LR上面的，这里就不作讨论了。前文中提到kernel最naive理解是__把特征空间从低维映射到高维从而线性可分__。之所以说naive，是因为这种描述并不太全面，知乎上有很多大牛反驳了这样的说法。但是，作为初学者，我个人感觉这样的intuition最容易被人记住，抛开复杂的数学推导，用一句话来解释SVM kernel，从传播的角度看没毛病。那么，为啥大牛们认为“低维到高维论”不全面呢，究竟怎么理解kernel？说实话，完整的数据推导现在我也没太搞明白，这里只是根据从其他大神那里吸收的一些皮毛简单解释下，也不一定对：先给一个更可能被大牛们接受的SVM kernel描述：__一种隐含特征空间映射、以更低计算复杂度实现向量内积运算的特殊函数__。有点抽象对不对，隐含怎么理解，更低计算复杂度内积运算怎么理解？下面通过例子来解释：考虑上文提到的2维空间图，要把每个数据点映射到3维空间，才有可能线性可分。而映射到了3维空间后，计算寻找最优SVM decision boundary的过程里需要计算任意两个向量的内积（注：为什么需要求向量内积属于SVM数学推导过程，这里省略）。对于一个2维空间数据点v = (x, y)，要把它映射到3维空间，其中一种映射关系是：$p(x, y)=(x^2,\sqrt2xy, y^2)$。假如有任意两个数据点：$v_1 =(x_1, y_1), v_2 =(x_2, y_2)$，我们可以直接计算它们对应向量的内积为：
$< p(v_1), p(v_2)> = <(x_1^2,\sqrt2x_1y_1, y_1^2),(x_2^2,\sqrt2x_2y_2, y_2^2)>$很明显，这是一个3维运算。假如3维还是无法线性区分，要映射到N维去，那这里就是N维运算，N越大计算量越大。有没有办法能够降低这个计算量呢？我们来展开推导一下：$<(x_1^2,\sqrt2x_1y_1, y_1^2),(x_2^2,\sqrt2x_2y_2, y_2^2)= x_1^2x_2^2 + 2x_1x_2y_1y_2 + y_1^2y_2^2$$=(x_1x_2 + y_1y_2)^2 =()^2$经过推导可以看到，两个数据点在映射后的向量内积等于映射前向量内积的平方。如果我们引入核函数：$K(v_1, v_2)=()^2$，那么就可以通过核函数的计算来等价于映射后的向量内积，实现了高维向量运算转换为低维向量计算（本例中是2维向量运算代替了3维向量运算）。由此看出，即使没有kernel，只要找到映射关系，我们仍然可以实现低维空间映射到高维空间，进而通过高维向量内积运算来寻找最佳分割超平面。但是，kernel的引入，降低了向量内积运算的计算复杂度。无论我们映射到几维空间，我们只要把原有维度代入核函数，就能等价于高维上的内积运算。极端的情况下，特征空间映射到了无穷维度空间，如果没有核函数，根本无法计算出映射后的向量内积。> 有没有kernel，低维都可以映射到高维，引入kernel只是计算量的差别而已，这就解释了为啥大牛们不同意kernel的“低维到高维论”了。然而，到这里讨论并没有结束。想象一下，要把上文示例的SVM模型训练跑通，需要走两步：第一步，找低维到高维空间的映射关系；第二步，找到这种映射关系对应的kernel函数。仔细思考下，是不是发现哪不太对——低维在第一步映射到了高维，但在第二步又被转换为了原维度的运算。这意味着：> 最终的模型训练计算过程，其实根本不需要__显式__地考虑高维是啥样子，只要kernel函数找好了，低维到高维的映射关系实际上被__隐式__的带出来了。你甚至不需要知道这个映射长啥样子，或者其干脆根本无法被描述出来。现在，问题关键变成了，怎么去找合适的核函数，并不是任意的函数都能隐含低维到高维的映射关系吧？答案很简单，过往的巨人们已经帮你找好了，站在他们的肩膀上膜拜吧。核函数有不少，最常用的是以下几个：最后，为了让你相信这些核函数可以隐含低维到高维的映射关系，这里还是举例证明下： - 先来看多项式核，假设有 a = 1, c = 0, d = 2，那么多项式核可表示为：$k(x, y)=(x^Ty)^2 =()^2$，这不就是上文最开始推导出的核函数吗，它对应的映射关系之前已经给出了。实际上，多项式核一定对应一个低维到高维的映射，高维的维度取决于参数d。 - 再来看高斯核或RBF，根据泰特展开公式：$e^x =$$\sum_{i=0}^n\frac{x^n}{n!}$，$K(x, y)$可以近似展开为n维的多项式，n越大越近似，直至无穷大。而多项式核一定对应低维到高维的映射，只是这个映射已经无法描述了。> 由此也看到，基于高斯核的情况下，2维可以被映射到无穷维度，如果没有核函数，已经不可能计算出那个空间的向量内积了。最后，总结下理解SVM kernel的几个要点：- kernel使SVM模型具备了非线性的拟合能力，没有kernel的线性SVM与LR无本质差别- kernel简单描述成“把特征空间从低维映射到高维从而线性可分”是不全面的。kernel只是其充分条件，不是必要条件，没有kernel一样可以做到（无穷高维度除外），kernel只是降低了模型训练的计算量，具体点说是降低了向量内积运算的复杂度- 实际应用中，没有人去显式地寻找低维到高维的映射关系，而是先找kernel，由kernel隐式地带来映射，而且该映射有时甚至无法描述，也没必要关心- 在众多核函数中如何选择，有赖于选择不同函数、不同参数的不断实验对比，而高斯核貌似是很多人的默认选择__参考资料__https://www.zhihu.com/question/35602879/answer/63963315https://www.zhihu.com/question/24627666/answer/310362701http://mp.weixin.qq.com/s?__biz=MzIxNDIwMTk2OQ==&mid=2649077019&idx=1&sn=e0c4a6c502e3668e1dc410f21e531cfd&scene=0#wechat_redirecthttp://blog.csdn.net/qq_27231343/article/details/51817866
网友评论