上篇博客 机器学习入门|支持向量机（一） 提到了SMO算法，这是用来求解优化函数变为关于拉格朗日乘子的二次规划问题的，是由Microsoft Research的John C.Platt在1998年发表的论文《Sequential Minimal Optimaization A Fast Algorithm for Training Support Vector Machines》中提出的，是最快的二次规划优化算法，特别是在针对线性SVM和数据稀疏等问题时更表现出强大的性能。
单看周志华《机器学习》的那一节，远不足以透彻了解算法的详细过程，也搜到了介绍SMO的博客，数学功底实在太渣＞﹏＜总的了解完机器学习几大算法之后，回头再看支持向量机的时候，把那Platt的那篇论文看一下。现在，暂且跳过SMO，其基本思路是先固定$\alpha_{i}$之外的所有参数，然后求$\alpha_{i}$上的极值。
核函数
好了，经过之前的介绍，我们能解决训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类。然而，在现实任务中，原始样本空间也许并不存在一个能正确划分两类样本的超平面。就像上一篇一开始提到的，对原空间进行升维，把在本来维度上不可用一个平面分割的类别在更高的维度可分。也许你还记得这张图
加深一下印象，再看一张！自己体会
对！将样本从原始空间映射到一个更高维的特征空间，就能实现线性的划分。我们把原先的样本点从二维空间映射到了三维空间之后，便可以很方便的找到一个超平面将两类样本点划分开。划分开之后，我们再重新将样本点以及划分平面从高维映射到低维，便完成了分类任务。可以肯定的是，如果原始空间是有限维的，即属性数有限，那么一定存在一个高维特征空间是样本可分。
令$\phi(\boldsymbol{x})$表示将$\boldsymbol{x}$映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为
$$ f(\boldsymbol{x})=\boldsymbol{\omega}^{T}\phi(\boldsymbol{x})+b $$
同样的（也就是把上文的$\boldsymbol{x}$替换为$\phi(\boldsymbol{x})$）有
$$ \left\{\begin{matrix} \underset{\boldsymbol{\omega},b}{min}\frac{1}{2}||\boldsymbol{\omega}||^{2}\\ s.t. y_{i} (\boldsymbol{\omega}^{T}\phi(\boldsymbol{x}_{i})+b ) \geqslant 1 ,i = 1,2,...,m\end{matrix}\right.\; $$
其对偶问题
$$ \underset{\alpha}{max}\sum_{i = 1}^{n}\alpha_{i}- \frac{1}{2} \sum_{i= 1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\phi(\boldsymbol{x}_{i})^{T}\phi(\boldsymbol{x}_{j})\; $$
$$ s.t.\;\sum_{i=1}^{m}\alpha_{i}y_{i}=0,\;\alpha_{i}\geqslant0,i=1,2...,m. $$
上式中涉及到计算$\phi(\boldsymbol{x}_{i})^{T}\phi(\boldsymbol{x}_{j})$ ，这是样本$\boldsymbol{x}_{i}$和$\boldsymbol{x}_{j}$映射到特征空间之后的内积。由于特征空间的维度可能很高，甚至是无穷维，因此直接计算很困难，就可以设想这样一个函数
$$ \kappa (\boldsymbol{x}_{i},\boldsymbol{x}_{j})=\left \langle \phi(\boldsymbol{x}_{i}),\phi(\boldsymbol{x}_{j}) \right \rangle=\phi(\boldsymbol{x}_{i})^{T}\phi(\boldsymbol{x}_{j}) $$
即$\boldsymbol{x}_{i}$和$\boldsymbol{x}_{j}$在特征空间的内积等于它们在原始样本空间中通过函数$kappa(\cdot,\cdot)$计算的结果。这个函数就是鼎鼎大名的——核函数（kernel function）。于是，可以将对偶问题重新写为
$$ \underset{\alpha}{max}\sum_{i = 1}^{n}\alpha_{i}- \frac{1}{2} \sum_{i= 1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\kappa (\boldsymbol{x}_{i},\boldsymbol{x}_{j})\; $$
$$ s.t.\;\sum_{i=1}^{m}\alpha_{i}y_{i}=0,\;\alpha_{i}\geqslant0,i=1,2...,m. $$
求解后即可得到划分超平面
$$ f(\boldsymbol{x})=\boldsymbol{\omega}^{T}\phi(\boldsymbol{x})+b $$
$$ ==\sum_{i=1}^{m}\alpha_{i}y_{i}\phi(\boldsymbol{x}_{i})^{T}\phi(\boldsymbol{x}_{j})+b\; $$
$$ ==\sum_{i=1}^{m}\alpha_{i}y_{i}\kappa (\boldsymbol{x}_{i},\boldsymbol{x}_{j})+b\;.(1) $$
式（1）显示出模型最优解可以通过训练样本的核函数展开，这一展式亦称为“支持向量展式”（support vector expansion）。
当然，如果我们知道合适映射$\phi(\cdot)$的具体形式，则可写出核函数$\kappa(\cdot,\cdot).$但现实任务中我们通常不知道$\phi(\cdot)$是什么形式，那么合适的核函数是否一定存在（之前说过如果原始空间是有限维的那么一定存在）?什么样的函数能做核函数？我们有一下定理:
核函数： 令$\chi$为输入空间，$\kappa(\cdot,\cdot).$是定义在$\chi \times \chi$上的对称函数，则$\kappa$是核函数当且仅当对于任意数据$D=\left\{\boldsymbol{x}_{1},\boldsymbol{x}_{2},...,\boldsymbol{x}_{m}\right\},$“核矩阵”（kernel matrix）$\mathbf{K}$总是半正定的：
$$ \mathbf{K}=\begin{bmatrix}\kappa (\boldsymbol{x}_{1},\boldsymbol{x}_{1}) & \cdots & \kappa (\boldsymbol{x}_{1},\boldsymbol{x}_{j})& \cdots &\kappa (\boldsymbol{x}_{1},\boldsymbol{x}_{m}) \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \kappa (\boldsymbol{x}_{i},\boldsymbol{x}_{1})& \cdots & \kappa (\boldsymbol{x}_{i},\boldsymbol{x}_{j}) & \cdots &\kappa (\boldsymbol{x}_{i},\boldsymbol{x}_{m}) \\ \vdots & \ddots & \vdots & \ddots &\vdots \\ \kappa (\boldsymbol{x}_{m},\boldsymbol{x}_{1})& \cdots & \kappa (\boldsymbol{x}_{m},\boldsymbol{x}_{j}) & \cdots & \kappa (\boldsymbol{x}_{m},\boldsymbol{x}_{m}) \end{bmatrix} $$
上式表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射$\kappa$。换言之，任何一个核函数都隐式地定义了一个称为“再生和希尔伯特空间”（Reproducing Kernel Hilbert Space，简称RKHS）的特征空间。
通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需要注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数时合适的，而核函数也仅是隐式地定义了这个特征空间。于是“核函数选择“成为非线性划分情况下影响支持向量机分类性能的最大变数。若选择了一个不合适的核函数，则意味着将样本映射到了一个不合适的特征空间，从而导致性能不佳。
常用的核函数有：SVM核函数
最后引用别人博客的一段，梳理一下核函数的引入：
- 问题1：
SVM显然是线性分类器，但数据如果根本就线性不可分怎么办？ - 解决方案1：
数据在原始空间（称为输入空间）线性不可分，但是映射到高维空间（称为特征空间）后很可能就线性可分了。 - 问题2：
映射到高维空间同时带来一个问题：在高维空间上求解一个带约束的优化问题显然比在低维空间上计算量要大得多，这就是所谓的“维数灾难”。 - 解决方案2：
于是就引入了“核函数”，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但却方便计算。
在所有之前的讨论中，我们都一直假定训练样本在样本空间或特征空间式线性可分的，不允许任何一个样本划分错，这样会导致过拟合，所以我们就允许支持向量机在一些样本上出错，为此，要引入“软间隔”（soft margin）。
至于“软间隔”就先丢一边了，明天开始搞——神经网络！
PS：欢迎访问我的hexo博客╰(￣ω￣ｏ) 白水东城-支持向量机-2
参考：
流水无Qing-支持向量机（四）-- 核函数
周志华《机器学习》
