支持向量机
原理
6.1 间隔与支持向量
- 给定训练样本集 D，分类学习最基本的想法就是基于训练集 D 在样本空间中找到一个划分超平面，将不同类别的样本分开。但能将训练样本分开的划分平面可能有很多，我们应该努力去找哪一个呢？
- 直观上看，应该去找位于两类训练样本“正中间”的划分超平面，因为该划分超平面对训练样本局部扰动的“容忍”性最好。换言之，这个划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。
- 距离超平面最近的这几个训练样本点对应的特征向量，被称为“支持向量”(support vector)。两个异类支持向量到超平面的距离之和被称为“间隔”(margin)
-
欲找到具有“最大间隔”(maximum margin)的划分超平面，也就是能找到满足下式中约束的参数 w 和 b，使得 γ 最大，即
(6-6)
这就是支持向量机(Support Vector Machine, SVM)的基本型。
6.2 对偶问题
- 我们希望求解式(6-6)来得到最大间隔划分超平面所对应的模型。注意到式(6-6)本身是一个凸二次规划(convex quadratic programming)问题，能直接用现成的优化计算包求解，但我们可以有更搞笑的办法。
- 对式(6-6)使用拉格朗日乘子法可得到其“对偶问题”(dual problem)。
6.3 核函数
- 本章前面的讨论中，我们假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类。然而在现实任务中，原始样本空间也许并不存在一个能正确划分两类样本的超平面。例如“异或”问题就不是线性可分的。
- 对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。
- 令 ψ(x) 表示将 x 映射后的特征向量。求解涉及到计算 ψ(xi)Tψ(xj)，这是样本 xi 与 xj 映射到特征空间之后的内积。由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算通常是困难的。为了必考这个障碍，可以设想这样一个函数：k(xi, xj) = <ψ(xi), ψ(xj)> = ψ(xi)Tψ(xj)。即 xi 与 xj 在特征空间的内积等于它们在原始样本空间中通过函数 k(. , .) 计算的结果。
- 这里的函数 k(. , .)就是“核函数”(kernel function)。显然，若已知合适映射 ψ(.) 的具体形式，则可写出核函数 k(. , .)。但在现实任务中我们通常不知道 ψ(.) 是什么形式，那么，合适的核函数是否一定存在呢？什么样的函数能做核函数呢？我们有下面的定理：
- 定理 6.1 令 X 为输入空间，k(. , .)是定义在 X * X 上的对称函数，则 k 是核函数当且仅当对于任意数据 D = {x1, x2, ..., xm}，“核矩阵”(kernel matrix) K 总是半正定的
- 定理6.1表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射 ψ。换言之，任何一个核函数都隐式地定义了一个称为“再生希尔伯特空间”(Reproducing Kernel Hillbert Space, RKHS) 的特征空间。
- 通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需要注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，而核函数也仅是隐式地定义了这个特征空间。于是，“核函数选择”称为支持向量机的最大变数。若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。
- 几种常用的核函数：线性核、多项式核、高斯核、拉普拉斯核、Sigmoid核
6.4 软间隔与正则化
- 在前面的讨论中，我们一直假设训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；退一步说，即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合造成的。
- 缓解该问题的一个办法是允许支持向量机在一些样本上出错。为此，要引入“软间隔”(soft margin) 的概念。
- 具体来说，前面介绍的支持向量机形式是要求所有样本均满足约束，即所有样本都必须划分正确，这称为“硬间隔”(hard margin)，而软间隔则是允许某些样本不满足约束。当然，在最大化间隔的同时，不满足约束的样本应尽可能少。
6.5 支持向量回归
- 现在我们来考虑回归问题，给定训练样本 D = {(x1, y1), (x2, y2), ..., (xm, ym)}。希望学得一个回归模型，使得 f(x) 与 y 尽可能接近， w 和 b 是待确定的模型参数。
- 对样本 (x, y)，传统回归模型通常直接基于模型输入 f(x) 与真实输入 y 之间的差别来计算损失，当且仅当 f(x) 与 y 完全相同时，损失才为零。与此不同，支持向量回归(Support Vector Regression, SVR)假设我们能容忍 f(x) 与 y 之间最多有 e 的偏差，即仅当 f(x) 与 y 之间的差别绝对值大于 e 时才计算损失。这相当于以 f(x) 为中心，构建了一个宽度为 2e 的间隔带，若训练样本落入此间隔带，则认为是被预测正确的。
6.6 核方法
- 若不考虑偏移量 b，则无论 SVM 还是 SVR，学得的模型总能表示成核函数 k(x, xi) 的线性组合。不仅如此，事实上我们有“表示定理”(representer theorem)的更一般的结论。
- 表示定理对损失函数没有限制，对正则化项 Ω 仅要求单调递增，甚至不要求 Ω 是凸函数，意味着对于一般的损失函数和正则化项，优化问题的最优解 h*(x) 都可表示为核函数 k(x, xi) 的线性组合；这显示出核函数的巨大威力。
- 人们发展处一系列基于核函数的学习方法，统称为“核方法” (kernel methods)。最常见的，是通过“核化”(即引入核函数)来将线性学习器拓展为非线性学习器。我们以线性判别分析为例，得到“核线性判别分析”(Kernelized Linear Discriminant Analysis, KLDA)
