1.SVM模型

——基本模型是特征空间上的间隔最大的线性分类器，使用核技巧使它成为非线性分类器

——SVM学习策略是间隔最大化，可形式化成一个求解凸二次规划的问题

——SVM等价于正则化的合页损失函数（hinge loss）的最小化问题。

2.SVM由简至繁的模型

线性可分支持向量机（硬间隔支持向量机）——>线性支持向量机（软间隔支持向量机）——>非线性支持向量机（使用核技巧和软间隔最大化）

3.输入空间和特征空间

假设输入空间是欧式空间或者离散集合，特征空间是欧式空间或者希尔伯特空间

线性可分支持向量机（硬）和线性支持向量 （软）假设这两个空间元素意义对应，而非线性支持向量机（使用核技巧）利用一个非线性映射将输入从输入空间转换到特征空间

SVM的学习是在特征空间上进行的。

4.分离超平面

wTx+b=0将训练集实例分到不同的类（正例和负例）

如果训练数据集是线性可分时，存在无数多个分离超平面

感知机是利用误分类最小的策略，求得分离超平面，有无穷多个解；线性可分支持向量机利用间隔最大化，这时解是唯一的。

5.函数间隔和几何间隔

一般情况下|wx+b|能够相对地表示点x距离超平面的远近，而wx+b的符号和类标记y的符号是否一致能够表示分类是否正确。所以y（wx+b）来表示分类的正确性和确信度。这就是函数间隔

但是要让函数间隔最大化还不够，只要成比例的改变w和b，比如变成2w和2b，超平面并没有改变，但是函数间隔却变大了。于是要对超平面的法向量w加某些约束，如规范化||w||=1，使得间隔是确定的，这就是几何间隔。几何间隔是实例点到超平面的带符号（signed）的距离。

6.间隔最大化（线性可分）

SVM的学习的基本思想是求解能够正确划分训练集并且几何间隔最大的分离超平面。这意味着以充分大的确信度对训练集数据进行分类，不仅将正负实例分开，而且对最难分的实例点（距离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

将整个训练集函数间隔最小值设为1，可以得到等价的优化问题，即一个凸二次规划问题。

何为间隔？对于正例点的支持向量，位于wx+b=1；对于负例点的支持向量，位于wx+b=-1；这两条线与分离超平面平行，它们中间的带宽就是间隔（margin），等于2/||w||

在决定分离超平面时，只有支持向量起作用，其他的实例点并不起作用。所以SVM由很少的“重要的”训练样本决定。

7.对偶问题（max min）

为什么引入对偶问题？对偶问题（dual）给出了原始问题（primal）最优解的下界。这样做的优点：一是对偶问题往往更容易求解；二是引入了核函数，进而推广到非线性分类问题。

8.软间隔最大化（有些噪声点，线性不可分）

不能满足函数间隔大于等于1的约束条件。

函数间隔加上松弛变量大于等于1. 对于每个松弛变量，支付一个代价，惩罚参数C，C值大时对于误分类的惩罚增大；C值小时对于误分类惩罚变小。

最小化目标函数见上图。包含两层含义：使1/2||w||的平方尽量小即间隔尽量大，同时使得误分类的点的个数尽量少。

可以证明w的解是唯一的，但是b的解在一个区间上。

9.支持向量

对应于α>0的样本点。

对于硬间隔来说，支持向量在wx+b=1和wx+b=-1上的样本点。

对于软间隔来说，比较复杂。或在间隔边界上，或者在间隔边界和分离超平面之间，或在分离超平面误分一侧。

10.合页损失函数

对于线性SVM，模型是超平面wx+b=0和决策函数f（x）=sign（wx+b）；学习策略是软间隔最大化；学习算法为凸二次规划。

还有另一种解释，就是最小化以下目标函数

第一项是合页损失函数，意思是：当样本点被正确分类且函数间隔（确信度）y（wx+b）大于1时，损失是0；否则损失是1-y（wx+b）

第二项是系数为λ的w的L2范数，是正则化项。

二分分类问题真正的损失函数是0-1损失函数（不是连续可导的），而合页损失函数是0-1损失函数的上界。

11.损失函数

SVM：合页损失函数     [1-函数间隔]+

逻辑回归：-logP（y|x）

这二者可看做对0-1损失这种非凸性优化的凸性近似。

12.SMO优化算法

其特点是不断将原二次规划问题分解成只有两个变量的二次规划子问题，并对子问题进行解析求解，知道所有变量满足KKT条件。

这样通过启发式的方法得到原二次规划问题的最优解，因为子问题有解析解，所以每个子问题都计算的很快。