上节课学习了 对偶支持向量机（Dual Support Vector Machine），实际上也是一个二次规划（QP）问题，可以使用二次规划求解。得到支持向量新的定义，即拉格朗日乘子 $\alpha_n>0$αn​>0 的在margin上的样本点才是支持向量。 经过推到之后，最优化问题变为有 $N$N 个变量，$N+1$N+1 个限制条件的问题，好像与特征空间的维度 $\tilde{d}$d~ 没有关系。但是上节课末尾留下了一个问题，即 $\tilde{d}$d~ 并没有真正消除掉，而是暗含在求解二次规划的二次项 $q_{n,m} == y_ny_mz^T_nz_m$qn,m​==yn​ym​znT​zm​ 中 (隐含在 $z$z 中) ，如果 $\tilde{d}$d~ 或 $N$N 过大，实际上都不容易求解。因此，希望找出某种方法真正消除 $\tilde{d}$d~ 的影响，来提高计算速度，这就是本节课介绍的内容–Kernel Support Vector Machine。

---

3 Kernel Support Vector Machine

3.1 Kernel Trick

在对偶支持向量机中，先做了特征空间的转换 $\Phi$Φ，将 $x$x 空间转换到 $z$z 空间，然后求内积运算 $z^T_nz_m$znT​zm​ ，这两个步骤的算法复杂度都是 $O(\tilde{d})$O(d~) ，当特征的维度 $\tilde{d}$d~ 过大时，计算向量内积比较困难，二次规划不容易求解。现在考虑减少算法复杂度，一个思路是将这两个步骤合起来，即将特征转换和内及运算合成一步完成。先看一个简单的例子，二次多项式转换：

为了计算方便，把 $x_0 =1$x0​=1 和 $x_1x_2,x_2x_1$x1​x2​,x2​x1​ 都包含进去，得到的结果中，$x^Tx'$xTx′ 表示 $x$x 空间中特征向量的内积，算法复杂度为 $O(d)$O(d)，而不是 $O(d^2)$O(d2)。可以看出，算法复杂度只与 $x$x 空间中特征的维度 $d$d 有关，而与 $z$z 空间中的特征维度 $\tilde{d}$d~ 无关，现在证明设想是正确的，达到了减少计算量提高计算速度的目的。类似以上将特征空间转换和内及运算一步完成的转换就称为 Kernel Function，用大写字母 $K$K 表示。

不同的转换对应不同的 Kernel Function，例如二次多项式对应：
$K_{Φ_2}(x,x') = 1 + (x^Tx') + (x^Tx')^2$KΦ2​​(x,x′)=1+(xTx′)+(xTx′)2
推导出Kernel Function之后，尝试将其应用来对偶支持向量机的求解过程中：

其核心思想是将先做特征空间转换再做内积运算的 $z^T_nz_m$znT​zm​ 转化为在 $x$x 空间中做内积运算的 Kernel Function $K(x_n,x_s)$K(xn​,xs​)，避免受 $z$z 空间的特征维度 $\tilde{d}$d~ 的影响，达到降低算法复杂度的目的。

计算出二次规划运算中的二次项系数 $q_{n,m}$qn,m​ 之后，就可以求解出拉格朗日乘子 $\alpha_n$αn​ ，即可求解出 $x$x 空间中的特征向量 $w$w 和偏置 $b$b ，也就得到了假设空间中最佳的假设函数矩g–$g_{SVM}$gSVM​。

引入Kernel Function，把原来的Dual SVM变为Kernel SVM，其伪代码为：

算法中没一个步骤的算法复杂度为：

---

习题1：

---

3.2 Polynomial Kernel

上一小节介绍的是二次多项式转换的特殊情况，下面介绍更一般的二次多项式转换：

红色的 $\Phi_2(x)$Φ2​(x) 是将一次项都乘以 $\sqrt{2}$2​ ，这样经过内积运算之后，最后的 Kernel Function 中由一次项计算得到的项的系数为 2 ，这样就很容易写成完全平方的形式。绿色的 $\Phi_2(x)$Φ2​(x) 更进一步，给二次项添加系数 $\gamma$γ ，得到更一般的二次多项式的 Kernel Function情形，记为 $K_2(x,x')$K2​(x,x′)。其表达式为：

转换之后，这两种转换公式的相同点是对应的空间相同；但表达式的形式不同，也就是说，内积运算的结果不同，在内积运算内的空间中，不同的内积就代表不同的距离，不同的距离会影响到margin（边界）。所以，不同的转换虽然空间没有变，但是SVM的margin可能不同。

怎么理解呢？继续往下看，如果使用 $K_{\Phi_2}$KΦ2​​ 求解支持向量（SV），并在输入空间中用方块“□”表示，其求解结果如下图所示：

如果添加一个自由度 $\gamma =0.001$γ=0.001，其求解结果如下图所示：

可以看到其超平面（分隔超平面，分类超平面，分类器，假设函数）的效果相比不添加自由度的第一种情况，好像要好一点（没有下边的超平面。如果令自由度 $\gamma = 1000$γ=1000 ，则其求解结果如下图所示：

通过以上对比可以发现，最佳的假设函数 $g_{SVM}$gSVM​ 不同，则支持向量不同，但是很难说哪一个更好。上例只是为了先建立一个关于分类器好坏的概念，知道改变Kernel（自由度 $\gamma$γ），就会改变margin，也就影响了SVM分类器的性能。下一步介绍如何选择最佳的Kernel。

上式中有三个参数，一个是 $\gamma$γ，表示做完内积之后要做多大的放缩（自由度）；另一个是 $\zeta$ζ ，表示常数项还有乘上的这些转换的系数要如何对应；还有一个是 $Q$Q ，表示做几次方的转化。要注意这里的运算都是在 $x$x 空间中计算的。高阶多项式的Kernel SVM的优点有两个：

• 限制条件使得支持向量的数目比较少，large-margin的存在会对抑制过拟合有一定的贡献；
• 内积运算在 $x$x 空间中计算，避免引入 $z$z 空间的特征维度 $\tilde{d}$d~，减少了算法复杂度，从而提高计算速度；
  
  下面考虑一种特殊情况，$Q=1$Q=1 ，此时就得到线性SVM。

在实际应用过程中，应该遵循由少到多，由简到繁的原则进行尝试。如果低阶的分类器的效果很好，就没有必要使用高阶的分类器。也就是奥卡姆剃刀定律（如无必要，勿增实体）的思想。

---

---

3.3 Gaussian Kernel

刚才介绍了polynomial kernel，但刚才介绍的 kernel 的阶数 $Q$Q 都是有限的，现在考虑如果是无线维度的转换 $\Phi(x)$Φ(x) 的情况，先看一个简单的例子：

构造一个函数 $K(x,x')$K(x,x′)，其推导过程如上图所示，最后得到 $\Phi(x)$Φ(x) ，其维度是无线维的，所构造的函数 $K(x,x')$K(x,x′) 称为高斯核（Gaussian Kernel），其更一般的表示形式为：

$K(x,x') = exp(−γ||x − x'||^2) \ with \ γ > 0$K(x,x′)=exp(−γ∣∣x−x′∣∣2) with γ>0

其中 $\gamma$γ 表示缩放因子，$||x-x'||$∣∣x−x′∣∣ 表示两个特征向量之间的平方欧几里得距离，$x'$x′ 表示核函数的中心（高斯函数的中心）。不要忘记，其求解方式仍然是二次规划，我们目前所做的工作都是在改变二次规划中的二次项系数 $q_{n,m}$qn,m​ ，来达到减少算法复杂度，从而减少计算量，进而提高模型泛化能力的目的。通过包含 $K(x,x')$K(x,x′) 的 $q_{n,m}$qn,m​，使用二次规划求解出 $\alpha_n$αn​，然后计算出 $b$b，得到最佳的假设函数矩g为：

使用高斯核的SVM，称为Gaussian SVM，它会把原来的数据映射到一个多维空间，然后在多维空间中找出最“胖”的边界（margin），实际上它是一堆在支持向量上面的高斯函数的线性组合，因为这个特性，也把高斯核函数 $K(x,x')$K(x,x′) 称为径向基函数（Radial Basis Function, RBF），Radial表示高斯函数，Basis Function表示对高斯函数做线性组合。

径向基函数是某种沿径向对称的标量函数，由于距离是径向同性的，通常定义为样本到数据中心之间径向距离（通常是欧氏距离）的单调函数。RBF是SVM中最常用的核函数。

高斯SVM引入高斯核，目的是求解线性组合的系数 $\alpha_n$αn​ ，以及要用哪些高斯核，即支持向量（SV）上的高斯核。

下面对比一下目前所学的几种SVM：

最初的线性SVM只能找到最大的边界（large-margin），即分隔超平面（hyperplane），对于非线性的输入空间要使用SVM实现分类，我们使用特征空间转换（transform），将非线性空间转换到线性空间，实现非线性输入空间的分类。然后，为了降低算法复杂度（$z$z 变换后，特征空间维度 $\tilde{d}$d~ 的影响），引入拉格朗日乘子，构造了对偶支持向量机，使得求解过程只和样本数量 $N$N 有关，但是实际上，$\tilde{d}$d~ 并没有真正消除，因为在二次规划计算二次项系数的过程中，内积运算实际上引入了 $\tilde{d}$d~。本节通过引入 Kernel ，以简单的二阶多项式转换为例，真正的消除了 $\tilde{d}$d~ 的影响；但是又有一个问题，即Kernel的大小对SVM分类性能有影响，但只能处理有限特征空间的情况；此时，引入了高斯核函数，实现了无限特征空间的转换，从而简化运算。 Kernel 的作用降低算法复杂度，但是只有Kernel，模型的泛化能力无法保证，所以需要large-margin来限制假设函数的数量，保证模型的泛化能力。

高斯核函数中，缩放因子 $\gamma$γ 变大，相当于高斯函数的图像变尖（标准差变小）。其取值的大小会影响分类效果，下图展示了不同的缩放因子对分类边界的影响：

可以看出，$\gamma$γ 越大其拟合能力越强，过拟合的风险就越大，其泛化能力就越差。所以需要仔细选择 $\gamma$γ 的值。

---

习题3：

---

3.4 Comparison of Kernels

本小节对比之前两节课和本节课所学的三种SVM，其实刚才已经总结过了，下面详细看一下这些SVM分类器的优缺点。

1.线性SVM

2.Polynominal Kernel SVM

3.Gaussian Kernel SVM

---

三种 SVM 对比：

名称	优点	缺点
线性SVM	算法复杂度低，计算速度快；特殊的QP问题；容易解释；	不能处理线性不可分的情况
Polynomial Kernel SVM	比线性SVM限制少；如果知道阶数 $Q$Q ，很容易控制；	当阶数过高时，K的波动范围大，稳定性差；参数过多，不容易选择；
Gaussian Kernel SVM	拟合能力强，即对非线性输入空间的分类效果好；计算复杂度相对较低；参数少，容易选择；	无法求解 w，计算速度较慢，容易发生过拟合；

---

高斯核函数（RBF） 是经常使用的核函数，但是需要注意缩放因子的设定。除了提到的核函数，还有很多其它有效的核函数。那么核（kernel）表示什么呢？实际上，kernel衡量的是 $x$x 和 $x'$x′ 的相似性，即特征空间转换后，在 $z$z 空间中向量的内积（向量内积本身代表的就是相似性）。但是反之不成立，也就是说，可以表征相似性的kernel并不一定是有效的kernel，需要满足两个条件（充分必要条件）：

• 矩阵 $K$K 为对称矩阵（symmetric）；
• 矩阵 $K$K 为半正定矩阵（positive semi-definite）；

这两个条件叫做 Mercer’s condition。只要满足这两个条件的kernel就一定是有效的kernel，但是实际上构造这样的 kernel 很困难。

• 二次型（quadratic form）：n个变量的二次多项式称为二次型，即在一个多项式中，未知数的个数为任意多个，但每一项的次数都为2的多项式。
• 实对称矩阵（real symmetric matrix）：如果有n阶矩阵A，其矩阵的元素都为实数，且矩阵A的转置等于其本身（$a_{ij}=a_{ji}$aij​=aji​）($i,j$i,j 为元素的脚标），则称A为实对称矩阵。
• 正定矩阵（positive definite, PD）：设M是n阶方阵，如果对任何非零向量 $z$z，都有 $z^TMz>0$zTMz>0，其中 $z^T$zT 表示 $z$z 的转置，就称 $M$M 为正定矩阵。
• 半正定矩阵（(positive semi-definite, PSD）：半正定矩阵是正定矩阵的推广。设A是n阶方阵，如果对任何非零向量X，都有X’AX≥0，其中X’表示X的转置，就称A为半正定矩阵。

---

习题4：

---

Summary

本节课介绍了kernel SVM，kernel 的 SVM 先讲了 Kernel Trick ，意思是说，把特征转换和内积运算合成一步，真正的消除了 $\tilde{d}$d~ 的影响，从而提高计算速度。然后讲了多项式Polynomial Kernel，把产生的系数添加进去；然后讲了Gaussian Kernel，实现了将输入空间无限多维度的转换。在之前讲到的SVM中，都要求输入空间是线性可分（ linear separable），即硬边界的SVM（Hard­-Margin SVM），即要求分类器将样本严格地分开，那对于线性不可分的情形呢？之前讲过说，转换到 $z$z 空间变为线性可分的情况，可能会导致过拟合问题，那么有没有办法解决，可以忍受一定的noise，但分类效果好呢？下一节课介绍 Soft-Margin SVM来解决这个问题。

---