前面两篇博客对线性支持向量机进行了详细的讲解，但线性SVM对于非线性的数据是无可奈何的。这篇博客将讲一下非线性支持向量机。

1. 核方法

　　对SVM有过一定耳闻的人，一定听说过“核技巧”、“核方法”这些名词，其实核方法并不是只能应用于SVM，还可以应用于其他地方。现在就来讲讲核方法是如何处理非线性数据的。

　　假设给定如下数据（上面左图），显然我们没法用一条直线将$'\circ'$和$'\times'$分开，如果用一个椭圆，将会得到很好的效果。我们希望将这个非线性分类问题变换为线性问题，通过变换后的线性问题的方法求解原来的非线性问题。上图中，我们可以将左图的椭圆变换成右图中的直线，将非线性分类问题变换为线性分类问题。
　　假设原空间为$X \in \mathbb{R}^2,x=(x^{(1)},x^{(2)})\in X$，新空间为$Z \in \mathbb{R}^2,z=(z^{(1)},z^{(2)})\in Z$，定义从原空间到新空间的变换为：

$$z=\phi(x)=((x^{(1)})^2,(x^{(2)})^2)$$ 经过变换 $z=\phi(x)$，原空间 $X \in \mathbb{R}^2$变换为 $Z \in \mathbb{Z}^2$，原空间的点相应的变换为新空间中的点，所以原空间的椭圆 $$w_1(x^{(1)})^2+w_2(x^{(2)})^2+b=0$$ 变换成新空间中的直线 $$w_1z^{(1)}+w_2z^{(2)}+b=0$$ 在变换后的新空间里，直线 $w_1z^{(1)}+w_2z^{(2)}+b=0$可以将变换后的正类和负类样本点正确分开。于是，原空间的非线性可分问题就变成了新空间中的线性可分问题。
　　总结一下，用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间； 然后再新空间里用线性分类学习方法从训练数据中学习分类模型。
　　 核技巧就属于这样的方法，应用到SVM上面的基本想法就是通过一个非线性变换 $\phi(x)$将输入空间（欧式空间或离散集合）对应于一个特征空间（希尔伯特空间），使得输入空间的超曲面模型对应于特征空间中的超平面模型。幸运的是， 如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本线性可分。于是在特征空间中分离超平面所对应的模型可表示为： $$f(x)=w\cdot \phi(x)+b$$ 优化目标函数可表示为（约束条件这里就不写了）： $$\min_{\alpha} \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}(\phi(x^{(i)})\cdot \phi(x^{(j)}))-\sum_{i=1}^m\alpha_i\tag{1}$$ 求解上面的优化函数涉及到计算 $\phi(x^{(i)})\cdot \phi(x^{(j)})$，这是样本 $x^{(i)}$和 $x^{(j)}$映射到特征空间的内积，由于特征空间维度可能很高，甚至是无穷维，因此直接计算 $\phi(x^{(i)})\cdot \phi(x^{(j)})$通常是困难的，避开这个障碍的一个方法是引入核函数： $$K(x^{(i)},x^{(j)})=\phi(x^{(i)})\cdot \phi(x^{(j)})\tag{2}$$ 即我们只定义核函数 $K(x,z)$，而不显式地定义映射函数 $\phi(x)$，这样我们就不用去计算高维甚至无穷维特征空间中的内积。对于给定的核函数，可以取不同的特征空间，即便是在同一特征空间里也可以取不同的映射。于是(1)可以重写为： $$\min_{\alpha} \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}K(x^{(i)},x^{(j)})-\sum_{i=1}^m\alpha_i\tag{3}$$ 用SMO算法解得 $\alpha_i^*$，然后确定分离超平面和分类决策函数。算法步骤和原来SVM一模一样，几乎不需要改动，只需要将 $\phi(x^{(i)})\cdot \phi(x^{(j)})$替换成 $K(x^{(i)},x^{(j)})$即可。

2. 核函数

　　显然，如果映射$\phi(x)$的具体形式已知，我们可以很轻松写出核函数$K(x,z)$。但现实任务中我们通常不知道$\phi(x)$是什么形式，那么合适的核函数是否一定存在呢？什么样的函数才能做核函数呢？
　　先上结论，一个函数能作为核函数的充要条件是——正定核函数。即核函数$K(x,z)$对应的Gram矩阵

$$K=[K(x^{(i)},x^{(j)})]_{m\times n}$$ 是半正定矩阵，那么 $K(x,z)$是正定核。鉴于在实际问题中往往是应用已有的核函数，自己设计核函数是“高玩”做的事，我这里就暂且先跳过证明这一步。下面来介绍一下常用的核函数，然后再来讨论一下核函数怎么选取的问题。

线性核函数

$$K(x,z)=x\cdot z$$ 也就是说，线性可分SVM其实就是使用了线性核函数的SVM，和非线性SVM只是核函数的差别，可以归为一类。

多项式核函数

$$K(x,z)=(\gamma x\cdot z + r)^p$$ 其中 $\gamma,r,p$都需要我们自己调参定义。

高斯核函数

$$K(x,z)=e^{-\frac{\|x-z\|^2}{2\sigma^2}}$$ 高斯核也称为径向基（RBF）核函数，其中 $\sigma$需要自己调参定义， $小的\sigma$对应更高维的空间。

Sigmoid核函数

$$K(x,z)=\tanh(\gamma x\cdot z+r)$$ 其中 $\gamma,r$都要自己调参定义。

3. 核函数的选取

　　一般情况下用的是线性核和高斯核，注意要对数据进行归一化处理。一般情况下高斯核的效果不会差于线性核，只不过高斯核计算量比线性核大。吴恩达课程里总结了这么几点：
　　(1) 当输入特征维度很大，和样本数量差不多时，这时选用线性核。因为特别高维度的空间，往往是线性可分的（核函数的动机不就是将低维特征映射到高维特征吗，既然已经维度很高，那么很有可能是线性可分的）。
　　(2) 当输入特征维度比较小，样本数量一般，选择高斯核较好。
　　(3) 当输入特征维度比较小，样本数量很多，则需要手工添加一些特征变成第一种情况。
　　线性核其实就是高斯核的一个特例，所以使用了高斯核的情况下就没必要考虑线性核了；在某些参数下，RBF和Sigmoid具有相似的性能；相比多项式核函数，RBF的参数较少，更容易选择。基于这些原因，高斯核是应用最广的核函数。

4. 小结

　　对非线性SVM算法流程做一个小结：
输入：线性可分数据集$T=\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots,(x^{(m)},y^{(m)})\}$，$y^{(i)}\in \{-1,+1\}$
输出：分离超平面和分类决策函数
(1)选取适当的核函数$K(x,z)$和惩罚系数$C$ 构造约束最优化问题：

$$\min_{\alpha} \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy^{(i)}y^{(j)}K(x^{(i)},x^{(j)})-\sum_{i=1}^m\alpha_i \\\begin{align*}s.t.　&\sum_{i=1}^m\alpha_iy^{(i)}=0\\ &0 \le \alpha_i \le C,　i=0,1,2,\dots,m\end{align*}$$ (2)使用SMO算法求解上述问题并解得$\alpha^*$
(3)计算得到$w^*$和$b^*$：

$$\begin{align*}w^*&=\sum_{i=1}^m\alpha_i^*y^{(i)}x^{(i)} \\b^*&=\frac{1}{p}\sum_{j=1}^p(y^{(j)}-\sum_{i=1}^m\alpha_i^*y^{(i)}K(x^{(i)},x^{(j)})\end{align*}$$ (4)求得分离超平面： $$\sum_{i=1}^m\alpha_i^*y^{(i)}K(x^{(i)},x^{(j)})) +b^*=0$$ 分类决策函数： $$f(x)=\mathrm{sign}(\sum_{i=1}^m\alpha_i^*y^{(i)}K(x^{(i)},x^{(j)}) +b^*)$$
　　SVM的最后一篇博客将讲一下之前遗漏的SMO算法。