1. 章节主要内容

支持向量机是我认为的机器学习算法中最复杂的算法之一，又因为我在总结西瓜书内容的时候是秉持着尽量不贴各种复杂数学公式的原则的，所以这一章的总结十分困难。综合考虑下，我仍然还是会以介绍算法原理和数学证明背后具体的思考逻辑为主，复杂的数学公式和证明过程我将略过。希望这样能帮助大家在不用头疼理解复杂数学公式的情况下对支持向量机有个较为深入的理解。如果有什么解释不够清楚或错误的地方，欢迎大家指出。

1）支持向量机是在以什么逻辑去解决机器学习的问题？

支持向量机是一个二分类的学习器，其基于分类学习最基本的想法：基于训练集 D 在样本空间中找到一个划分超平面，将不同类别的样本分开。但能将训练样本分开的划分超平面可能有很多，不同的超平面的性能往往差别挺大，所以支持向量机的训练目标就是要找到泛化性能最佳的那个超平面。

支持向量机算法将“找寻最佳超平面”的问题进行了几步转换，使得如果我们找到了转换后的问题的解，我们也就找到了目标的最佳超平面。

［1］为“最佳”的超平面定性

在考虑哪一个超平面性能会更佳时，一个直观的想法就是位于两类训练样本“正中间”的划分超平面会更好一些，因为它对训练样本局部扰动的“容忍性”最好。而这个正中间的超平面一定满足这样的一个条件，那就是离它最近的正例数据和反例数据到它的距离之和最大。

所以，支持向量机算法第一步将寻找“最佳”超平面的问题转换为寻找“最大间隔”的划分超平面问题。

［2］“最大间隔”由什么确定

为了更形象地表现正负样本的间隔，我们可以在分割超平面的两侧再定义两个平行的超平面H1和H2，这两个超平面分别通过正样本和负样本中离分割超平面最近的样本点。

我们定义超平面H1和H2上面的点叫做支持向量。正负样本的间隔可以定义为超平面H1和H2之间的间隔，它是分割超平面距最近正样本点距离和最近负样本点距离之和。

支持向量对于分割超平面的位置是起到关键作用的。在优化分割超平面位置之后，支持向量也显露出来，而支持向量之外的样本点则对分类并不关键。为什么这样说呢？因为即使把支持向量以外的样本点全部删除，再找到最优的分割超平面，这个超平面的位置跟原先的分割超平面的位置也是一样的。总结起来就是：支持向量包含着重构分割超平面所需要的全部信息！

在样本空间中，超平面可以用如下线性方程来描述：

wx + b = 0，w为超平面的法向量

对于任意的一个点x，它可以表示为：x ＝ xp ＋ r ( w / ||w|| )，xp为x在超平面的投影，r为x和超平面的距离，我们设定g(x) = wx + b，因为g(xp) = 0，所以可得到：

g(x) = r ||w||，即可得任意点x到超平面的距离： r = |g(x)| / ||w||

根据超平面概念，g(x)应该满足：

wxi + b > 0, yi = +1;

wxi + b < 0, yi = -1;

存在一个变量a，使得g'(x) = a g(x)，满足下式：

w'xi + b' >= 1, yi = +1;

w'xi + b' <= -1, yi = -1;

当xi为支持向量时，等式成立，所以我们所要求的最大间隔其实就是求：

式(1)

上边等价于：求解当满足不等式 yi*g(x) >= 1时，使||w||的平方达到最小值的w和b的值

最后还是写了数学算法推导过程，因为感觉不写的话，对于结论是如何得到的大伙就一头雾水了。看得头都大了，如果只是想了解支持向量机的思考逻辑的话，大伙其实记住下边这句结论应该就可以了。

支持向量机算法第二步将寻找“最大间隔”的问题转换为不等式约束的优化问题

所以总结一下，支持向量机分类的背后逻辑是：找到最好的超平面将训练样本正确分类 --> 最好的超平面为是正反例样本“间隔最大”的平面 --> 间隔最大的平面寻找实际上是一个不等式约束优化问题

2）不等式约束优化问题的求解逻辑？

式(1)是一个二次规划问题，我们可以通过拉格朗日乘子法将其转换为它的对偶问题来进行计算。具体的转换和计算过程请小伙伴们查看书中的介绍，这里就不做公式的搬运工作了。通过转换，我们将上边所要算的不等式约束优化问题转化为下边的式子：

通过计算上式的拉格朗日乘子：阿尔法a，我们可以得到最优解的 w 和 b

3）当超平面在样本空间上无法划分开训练样本时，该如何处理？

在本章前面的讨论中，我们假设训练样本是线性可分的，然而在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。

对待原始数据无法线性可分的问题，一个合适的思路是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分

因为存在一个特征映射函数，所以拉格朗日乘子法转换的对偶问题式子可转换为：

由于样本 xi 和 xj 映射到特征空间之后的内积因为维数可能很高，所以比较难直接计算。为了避开这个障碍，我们设计了“核函数”（kernel function），这个函数使得 xi 和 xj 在特征空间的内积等于它们在原始样本空间中通过核函数 k(xi, xj) 计算的结果。

如果我们已知合适的特征映射O(.)的具体形式，则可写出核函数 k(. , .)，但在现实任务中我们通常不知道O(.)是什么形式。

幸运的是，我们知道：只要一个对称函数所对应的核矩阵是半正定，它就能作为核函数使用，并且对于一个半正定核矩阵，总能找到一个与之对应的映射O(.)空间。

所以，我们知道了吧，对于在样本空间中无法线性可分的数据，我们不是先去找到使它线性可分的映射空间，然后通过核函数去计算的；相反，我们是得要选择一个核函数先，然后通过这个核函数去找到对应的映射特征空间，并计算在该映射空间上的最优超平面。

很显然，核函数的选择不当，很可能会导致样本被映射到一个不好的空间，导致算法性能不佳。于是，“核函数选择”成为了支持向量机的最大变数。不过一些基本的经验还是有的，例如对文本数据通常采用线性核函数，情况不明时可先尝试高斯核。下边是一些常用的核函数列表：

4）当超平面无法完全划分开训练样本时，该如何处理？

因为在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分，为了缓解该问题，一个合理的办法是允许支持向量机在一些样本上出错。这种策略被称为“软间隔”（soft margin），它允许某些样本不满足不等式约束。

当然，在最大化间隔的同时，不满足约束的样本应尽可能少，于是，我们式(1)中的优化目标可改写为：

很明显，我们在之前的优化目标式子中加入了损失函数的影响，当样本落入不满足约束的空间内时，损失函数的值就会变大，使得优化目标的值向反方向移动；当样本落入满足约束的空间内时，损失函数的值减小甚至为0，使得优化目标的值向着目标方向移动。C > 0是个常数，代表着损失函数的影响力，当C无穷大时，会迫使所有的样本要满足约束。

然后同样通过拉格朗日乘子法对上式进行计算，即可算得使我们优化目标最小的参数 w 和 b 的值。

5）支持向量回归（SVR）

前边的支持向量机是一个二分类器，SVR就是支持向量机算法在回归模型上的应用。同前一节的方式类似，只不过这次引入的损失函数是根据回归模型的原理设计的，是一个预测结果g(x)与真实结果y之间的差值，当这个差值大于一个常数 e 时，才会被计算。

同样的，通过使用拉格朗日乘子法计算出参数 w 和 b 的值

6）核方法

给定训练样本，若不考虑偏移项，则无论 SVM 还是 SVR ，学得的模型总能表示成核函数的线性组合。正因为核函数的重要性，人们发展出一系列基于核函数的学习方法，统称为“核方法”（kernel methods）

2. 基础知识

1）法向量

法向量是空间解析几何的一个概念，垂直于平面的直线所表示的向量为该平面的法向量。

2）线性规划

线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。

3）对偶问题

每一个线性规划问题都伴随有另一个线性规划问题，称为对偶问题。对偶问题起源于这样的思想：原始问题比较难求解求解另外一个问题，希望得到原始问题都最优解或者下界(对于最小化问题)。主要的方式为增加变量，将约束写入目标来实现。

4）拉格朗日乘子法（Lagrange multipliers）

拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子，可将有d个变量与k个约束条件的最优化问题转化为具有d＋k个变量的无约束优化问题求解

基本的拉格朗日乘子法就是求函数f(x1,x2,...)在g(x1,x2,...)=M的约束条件下的极值的方法。其主要思想是将约束条件函数与原函数联系到一起，使能配成与变量数量相等的等式方程，从而求出得到原函数极值的各个变量的解。

5）核函数

一个函数如果使得任意训练样本 xi 和 xj 在特征空间的映射向量的内积等于它们在原始样本空间中通过函数 k(xi, xj) 计算的结果，那么该函数就是核函数

3. 总结

支持向量机这一章的学习过程十分痛苦，因为我不想在读书总结中引入公式，导致总结过程十分艰难。最后虽然也妥协了，但是因为只是放了部分公式、并且有的内容我自己可能都理解的不够深入，所以大伙可能理解困难也挺麻烦的。希望大家多提提意见，共同成长。不过要大概了解支持向量机是干什么的，知道下边的总结内容，应该就可以了。

1）支持向量机的基本思想是：基于训练集 D 在样本空间中找到一个划分超平面，将不同类别的样本分开

2）支持向量机的目标是：找到泛化性能最佳的那个超平面

3）支持向量机的计算逻辑是：第一步将寻找“最佳”超平面的问题转换为寻找“最大间隔”的划分超平面问题；第二步将寻找“最大间隔”的问题转换为不等式约束的优化问题

4）当超平面无法在样本空间中将训练数据划分开时，将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分

5）当超平面无法完全将训练数据划分开时，使用软间隔的策略，允许某些样本不满足不等式约束。具体通过引入损失函数到优化目标方程中实现。