第6章 支持向量机
支持向量机是针对二分类任务设计的，对多分类任务要进行专门的推广。分类学习的基本想法是基于训练集 D 在样本空间中找到一个划分超平面，将不同类别的样本分开。在样本空间中，划分超平面可通过线性方程 wTx + b = 0 来描述，样本空间任意点 x 到超平面的距离可表示为
假设超平面能将训练样本正确分类，即对于(xi, yi)属于集合 D，如果yi = +1，则有 wTx + b > 0；如果yi = -1，则有 wTx + b < 0，令
支持向量指距离超平面最近的几个训练样本点，能使上面的公式成立，间隔指两个异类支持向量到超平面的距离之和
支持向量与间隔的示意图
明显，我们需要找到具有最大间隔的划分超平面，也即
||w||-1最大化即可得到最大间隔，等价于最小化||w||2，即
以上即是支持向量机(Support Vector Machine，简称SVM)的基本型。
对偶问题可以更高效地求得大间隔超平面模型的解，而对偶问题可以通过SMO等高效算法求解。
支持向量机的一个重要性质是，训练后完成后，大部分训练样本不需要保留，最终模型只跟支持向量有关。支持向量机的关键是如何从支持向量构建出解，气复杂度主要与支持向量的数目有关。
现实任务中，原始样本空间内可能并不存在一个能正确划分两类样本的超平面，这时可将样本从原始空间映射到更高维的特征空间，使得样本在改特征空间内线性可分。假设 Φ(x) 为 x 映射后的的特征向量，原来最大间隔的公式可表示为
对偶问题也是同理，问题是再求对偶问题的解时，涉及到 Φ(xi)TΦ(xj)的计算，即xi 和 yi 映射到特征空间后的内积，由于特征空间维数可能很高，甚至是无穷维，因此直接计算是困难的。所以假设 xi 与 xj 在特征空间的内积等于它们在原始样本空间中通过函数 κ(·,·) 计算的结果，κ(·,·) 表示为
如果有了这样的函数，我们就不必直接去计算高维甚至无穷维特征空间中的内积，而是将公式替换为 κ(·,·) 表示，这样的函数就是核函数
在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，所以“核函数选择”成为支持向量机的最大变数，如果核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。常用的核函数有线性核、多项式核、高斯核、拉普拉斯核、Sigmoid 核等，通过核函数的组合得到的也是核函数。
在现实任务中往往很难确定合适的核函数使得训练样本在特征空 间 中线性可分，缓解该问题的一个办法是允许支持向量机在一些样本上出错，也就是软间隔，图示
所以目标变成了在最大化间隔的同时，令不满足约束的样本应尽可能少，公式变为
其中 C > 0 是常数，l0/1 是0/1损失函数，人们通常用其他一些函数来代替0/1损失函数，即替代损失，替代损失函数一般具有较好的数学性质，常用有hinge损失、指数损失、对率损失等，替换后则是常用的软间隔支持向量机。
传统回归模型通常直接基于模型输出 f(x) 与真实输出 y 之间的差别来计算损失，当且仅当 f(x) 与 y 完全相同时，损失才为零，然而，支持向量回归 (Support Vector Regression，简称 SVR) 假设我们能容忍 f(x) 与 y 之间最多有 ε 的偏差，即仅当 f(x) 与 y 之间的差别绝对值大于 ε 时才计算损失，图示
于是 SVR 问题可表示为
若不考虑偏移项 b ，则兀论 SVM 还是 SVR，学得的模型总能表示成核函数 κ(x,xi) 的线性组合，因此发展出一系列基于核函数的学习方法，统称核方法，比如是通过核化（即引入核函数）来将线性学习器拓展为非线性学习器。
