参考文献：
http://www.blogjava.net/zhenandaci/archive/2009/03/01/257237.html
http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988406.html
NG的SVM课件
*大学林轩田老师的视频课程
注意1：本文自然过渡并引出核函数的概念，比课件和其他教程上的说明更加让人理所当然地接受！
注意2：貌似对于SVM原问题求解，很多地方直接采用KKT条件求解。实际上，它也是通过求解对偶问题来得到KKT条件。如此，SVM原问题必须直接或者间接地经过对偶问题这一步的推导。
注意3：文中最后给出林轩田老师的课件截图，可以看到映射ψ和核K的参数个数对比。很了然：（1）ψ的参数是K的参数指数次方，更高维对比更加明显。（2）K好选，ψ不好选。
文中对核方法的表示K(x，z)其实x是常数，z是低维表示的，它和x同维，不要认为z是高维空间的变量，容易被一个例子：z=[z1,z2,z3]=[x,x2,x3]迷惑了双眼。参见NG的SVM中的14页。文中的下式也是如此:
在对偶空间上说明这个问题。
(i)首先，我们在对偶空间中得到：
这里，我们假设x(i)，y(i),x是d维向量。内积Rd×Rd->R
(ii)对于非线性问题，如果先找到一个映射Φ(x):Rd->R(d×d)使非线性问题变成线性问题（这里只是一个映射的特例），通常需要变到很高的维数空间去，问题变成了（未必是Rd->R(d×d)，可能是Rd->R(d×c)）：
(1)
显然，算法复杂度的一个上界为：m×(d×d×2+d)+1，即O(m×d×d)，注意到
和
的复杂度都为d×d，比如对于d=3时，x=[x1,x2,x3]，其中的一种选择是：
注意到是3×3=9维。
(iii)对于上面的映射和，其中，
有
将和的表达式代入（1）中，得到：
化简有：
更进一步地，
其中，令
于是，
考虑到中，x和x(i)向量都是d维度，于是，总的计算复杂度为：m×(d+1)+1，即O(m×d)。
我们简化了两个工作：
（1）不用再去费劲去找
（2）O(m×d×d)复杂度将到O(m×d)。如何只就这部分来说，O(d2)复杂度降到O(d)。这里不考虑矩阵相乘分成子矩阵以降低复杂度。只是一个上界的讨论。
既然有这两个如此强大的技巧，它被人们视为一种常用的东西，被称为核技巧，核函数，核方法。至于为啥叫这个奇葩的名字，我就不知道了。
附1：
（1）这只是一种核函数，还有许许多多其它形式的。
（2）这里中的实际上除了支持向量之外的αm都为零。
（3）如果实在因为K(x，z)中的z纠结，那么不用管它，直接视为K好了。K为多项式核函数时，代入和时，由于对称性（也因为对称性K为半正定矩阵），总能化简成（xTz+c）d这样简单的形式（或者是其它更一般的形式）。
（4）当用软间隔最大化时，约束条件变成了0≤αi≤C，这样直接用KKT就无法解决。使用SMO算法。参见NG的SVM。
（5）高斯核函数是局部模型。（参见机器学习导论）
（6）核函数的组合与多核学习。（不需要选定一个特定的核）
附2：
第二次快速看*大学SVM视频有感：
（1）认为低维指实例个数m（可能默认：特征的向量维数＜实例个数）；高维指非线性映射之后的向量维数，如上的O（d2）
（2）核技巧不能表达所有可能的，确切地说，只能描述极其少一部分，只不过这一小部分就能解决很多问题。这些可以通过核函数K的参数空间可以看出：
多项式：
高斯核：
（3）L2正则化的logistics函数、ridge回归可以用高斯核
（4）SVM扩展到回归问题——SVR。这里首先引入tube regression；在这个基础上能提到margin问题，进而转到对偶空间等等。