课程概要：

1.核技法

2.软间隔分类器

3.SVM求解的序列最小化算法(SMO)

4.SVM应用

一.核技法

回忆一下上篇中得到的简化的最优问题，，#1：

定义函数ϕ(x)为向量之间的映射，一般是从低维映射到高维，比如在前面笔记中提到的房价和面积的关系问题中，可以定义ϕ为：

这样，就可以将#1 问题中目标函数中的内积的形式

这样就达到了将低维空间上的数据映射到高维空间上，使数据线性可分的概率变大，即不能
保证在高维上一定是线性可分的，但一般情况下高维空间上比低维空间上更加线性可分。
但有些时候，经过ϕ映射后的向量的维度过高，导致映射后向量内积的计算复杂度过高。
为了解决这个问题，我们正式引入核函数：

其中，X,Z即为上面的为了简化表示，去掉了上标。

核函数的作用在于定义了核函数后，可以不用明确的定义出映射函数，就能计算两个向量在高维空间中的内积了，而且时间复杂度低。

下面举几个核函数的例子：

其对应的映射函数为

一个相似的核函数如下： 

其对应的映射函数为

一个更一般化的核函数如下：

该核函数对应的映射函数的结果是一个.大小的向量，向量中每个元素都是最高为d阶的变量的组合。
对于公式2、 4、 6中的核函数而言，虽然它们对应的映射函数的维度可能是 n^2或者 n^d，意味着如果直接计算映射结果的内积的话复杂度分别为O(n^2)或O(n^d)，但是如果直接计算核函数的值，其复杂度均为O(n)，这也体现了核函数降低计算量的好处。

直观上来看，如果ϕ(x)ϕ(z)在其对应的维度空间中位置接近，那么内积值 K 会很大，反之则内积会小。这意味着核函数 K 是一个向量 x 和向量 z 何等接近的度量函数，从而可
以引出SVM中使用较广泛的高斯核：

值得一提的是，高斯核对应的映射函数ϕ是映射到无限维的。
那么，什么样的核函数才是正确的核函数，是不是所有的以 x，z 为变量的函数都能做核函数呢？即如何判断一个函数是不是能拆分成映射函数乘积的形式？前后两个问题等价
的原因是核函数是由映射函数乘积得到的，因而如果核函数合法，那么必然能写成两个映射函数乘积的形式。

   为了解决这个问题，首先定义核矩阵。对于一个数据集,定义一个m*m的矩阵K（K既代表核函数也代表核矩阵），K中的每个元素定义如下：

对于核矩阵，有几个性质，首先很显然，Kij=Kji，核矩阵是一个对称（symmetric）矩阵。
其次，对于任意的m维向量 z，可以得到：

由此，因为z是任意向量，所以 K是半正定（positive semi-definite）矩阵。事实上，这不仅是一个必要条件还是一个充分条件。因为存在一个 Mercer定理：
给定一个K：ℝ^n × ℝ^n ⟶ℝ，那么K是合法的核（又称 Mercer核）的充分必要条件是：
对于任意一个有限数据集，对应的核矩阵是对称半正定矩阵。
对于核来说，不仅仅只存在于 SVM 内，对于任意的算法，只要计算时出现了内积的，都可以用核函数替代，从而提高在高维数据上的性能，比如感知器算法，代入后可发展为核感知器算法。这也是核函数被称为核技法的原因吧。

二、软间隔分类器

之前讲述最优间隔分类器时，一直强调数据是线性可分的。但是，当数据是线性不可分时，或者映射到高维空间后仍然不是线性可分，再或者即便是线性可分的但实际应用中不可避免出现噪声时，该如何处理呢？本节提供了一个比较通用的解法。

首先，对原始问题进行变形，得到#2：

由#2可知，有些数据点可以被允许拥有比 1小的几何间隔，但是这种情况要受到惩罚，C 为惩罚因子，是一个预设的参数。
其中，由目标函数的两部分，w 部分和惩罚部分，按照它们的指数可以分为多种组合。
当 w 的指数为 n时，称之为 Ln 正规化；当惩罚部分的指数为 n 时，称之为 Ln 损失；比如
#2中的目标函数即为L2 正规化-L1损失 SVC（Support Vector Classification）1。
按照上篇笔记中的将原始问题转化为对偶问题进行简化的例子，写出#2 对应的拉格朗日方程：

公式10中，α, r是拉格朗日乘子，均有不小于 0 的约束。

按照上篇笔记中的对偶问题的推导方式，先针对 w，b 最小化，然后再针对α最大化，得到新的对偶问题，即#3

与#1 对比得到，本问题只对αi做了进一步的约束。求解得到α后，w 仍然按照公式给出，但是截距 b的得到方式要变化。

另一个发生变化的地方在于 KKT 中的互补条件，现在变为：

这些条件将在下一节用于判断 SMO 算法是否收敛。 至此，终于已经得到一个可以应用于实际的具体问题了（#1 是假设数据集线性可分，
不符合实际），下面一节将对介绍对#3问题求解的算法。

三、SMO算法

坐标上升法

在介绍 SMO 算法之前，先介绍一个简化的但与 SMO 使用同一思想的算法，坐标上升法（Coordinate Ascent）。
先抛开SVM优化问题，看如下一个要解决的简单的新问题：

对函数寻找最优值，之前已介绍了梯度下降法和牛顿法。现在介绍一种新方法：

最内层循环中，当更新i时，保持其它的参数不变。 直观上看，这种方法比梯度下降和牛顿法迭代次数要多（一般情况下事实如此），
但当能很快的求解argmax时，该算法仍是一个高效的算法，下面是一种运行样例图：  由图可见，当保持其它参数不变而只改
变某个参数时，会使得参数的收敛方向都是平行于坐标轴的。 还有一点，这张图只有两个参数，所以才能在二维图中展示出来。

SMO算法

SMO（Sequential Minimal Optimization）与坐标上升法不同的地方在于，由于#3 问题中有一个约束为 ，

使得当固定其他参数只改变一个参数的时候，发现剩余的那个参数是固定的，因而SMO 算法每次选择两个参数进行优化。实际上，两个参数中可以将
一个当做变量，另外一个当做该变量的函数，函数关系为：

 SMO算法描述为：

循环中，在选择参数对时，使用一些启发式规则选择使全局函数增长最大的参数。

前面提到，这种算法虽然迭代次数多，但当最优化时速度快，仍不失为一种高效的算法，那么对于SVM最优化问题，优化起来效率如何呢？对于#3中的目标函数来说，当只保留两个参数变化时，代入公式14的关系，那么目标函数将变为一个二次函数，再加上0 ≤ αi ≤ C的条件，求最优值还是极为简单的。

当然，在计算最优值时，需要根据约束关系对自变量的取值范围进一步的计算，比如右图所示，假设以α2为自变量，那么它的范围就是[L,H]。

四、SVM应用

SVM 作为一种分类器，自然在分类问题上大展手脚了。比如文本分类、图像分类等。
下面列举几个SVM的实际应用。
比如手写数字识别问题，给定一张 16*16 的图片，上面写着 0-9的 10个数字，使用 SVM进行判定。这本来是NN（Neural Network）比较擅长的问题，但初次将SVM用于其上时效果之好令人惊讶，因为SVM没有图片识别的先验知识，只是依据像素就能达到很好的效果。
补充一点，SVM上使用高斯核和多项式核都能在该问题上达到和NN 相当的效果。 再比如通过氨基酸序列对蛋白质的种类进行判别，假设有 20 中氨基酸，它们按照不同
的序列可以组成不同的蛋白质，但这些氨基酸序列的长度差异很大，那么该如何设定特征呢？
有一种方式是使用连续四个氨基酸序列出现次数作为向量，比如氨基酸序列AABAABACDEF，那么可以得到 AABA:2, ABAA:1,…CDEF:1。据此，可以得到特征向量的
长度为204，如此大的特征向量，难以载入内存，有一种高效的动态规划算法可以解决此问题。
与氨基酸序列识别蛋白质类似的是，字符串的识别，对于长度为k 的字符串，如果以字母为特征，那么特征向量大小为 26k，也需要利用dp 算法进行解决。