核函数与SVM
kernel在SVM中的应用真心只是冰山一角，做kernel的人基本不关心这个问题，就像用SVM的人也不关心kernel是啥一样。
kernel 和 SVM 完全是两个正交的概念，早在SVM提出以前，reproducing kernel Hilbert space（RKHS）的应用就比较广泛了。一个经典的例子就是信号处理中signal detection的问题：给一条time series我如何知道它不是一个random walk的噪音而是有一个特定的pattern在里面呢？在这个情景下，RKHS理论就给出了一个通过现实求解likelihood ratio的假设检验方案，其中的kernel实际上是某个随机过程 R(t) 在两个不同时间点的correlation。
很多人觉得kernel定义了一个从低维度到高维度的映射，这是不准确的。首先，并不是所有空间都像欧式空间那样有所谓“维度”的良好定义，很多空间是没有维度的意义的，或者可以认为维度都是无穷大，这样就无法区分不同的RKHS了。但是kernel确实可以定义一个映射，而且确实是一个非常强大的映射，很多方法在这个映射下是可以直接推广到kernel space的，包括SVM，logistic regression, least squre，dimension reduction。
那么这个映射是什么呢？我略过数学的setup（估计也没有人看）简单讲讲RKHS是什么一个故事：实际上RKHS的定义是反过来的，首先在原空间上考虑所有连续函数，这些连续函数可以做加法和数乘，所以真主给他们（中的一部分）施加一个内积结构，比如所有二阶多项式其系数在欧式空间展开构成的内积就是高票主提供的例子；这个内积实现中的一部分就可以对应到原空间中的两两之间点的kernel。所以RKHS是先有内积才有kernel的，但是另个一个牛逼的定理说，只要kernel满足一些条件，就存在这样一个（唯一的）内积结构与之对应。（其实这部分的数学，一个普通大学数学系的本科生就能看懂了或者学过了，并不是什么高深的内容）
kernel有什么作用？kernel不仅可以建立点对点的映射（如SVM那样），还可以建立原空间上一个分布对点的映射，有兴趣的读者请谷歌 kernel embedding of distributions。 在这一个映射下，人们会关心这么一个问题，给两组数据，我如何知道他们是不是从同一个分布中来的呢？在kernel map下，两组数据被map成了kernel space的两个点，我们可以看看在那个空间里他们距离是远还是近，如果很近就很可能是同一个点加上一点sample variance，以此来判断两组数据是不是同一个分布（two sample test）。
最后谈一谈不同的核函数，应用中最常见的估计就是RBF kernel了比如Gaussian kernel，这类kernel的强大之处在于他们提供的embedding space非常丰富（当然有人可以理解为维度非常高，但是既然是无穷维，谈维度已经没有意义了），以至于原空间中不同的分布可以被直接map到不同的点，这类kernel有个名字叫characteristic kernel。回到我们最初的kernel 定义到底什么样的kernel才能reproduce如此丰富的embedding 空间呢？答案是能把整个连续函数空间填满(dense)的kernel。比如一般的多项式kernel就不行，因为二阶多项式的线性组合不能表示更高阶的多项式函数了。这种能把整个连续函数空间填满的kernel，叫universal kernel。一个重要的结果是universal kernel就是characteristic kernel，换句话说只要你能把连续函数空间填满，那么原空间上不同的分布在这个map下都会变成不同的点。
说了这么多，我只想吐槽初学者太容易被几个大牛写的tutorial忽悠了，我刚学SVM的时候也不知道原来kernel是一个独立的概念，直到很多年后= =吃了很多亏才长了一点姿势。
最后补一个最近刚看到的视频，里面对kernel machine的应用讲的比较全面(大家可以注意一下台下都有谁。。）：https://royalsociety.org/events/2014/11/milner-lecture/