转自微信公众号：机器学习算法与Python学习
统计学习方法 & 小象学院
SVM算法优点：
可用于线性/非线性分类，也可以用于回归
低泛化误差
容易解释
计算复杂度低
缺点：
对参数和核函数的选择比较敏感
原始SVM只比较擅长处理二分类问题
它的基本模型是定义在特征空间上的间隔最大的分类器，间隔最大使它有别于感知机。
SVM还包括核技巧，这使它成为实质上的非线性分类器。
支持向量机的学习策略就是间隔最大化，可以形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。
支持向量机的学习算法是求解凸二次规划的最优化算法
方法包括：
1. 线性可分支持向量机
2. 线性支持向量机
3. 非线性支持向量机
线性可分时，通过硬间隔最大化，当数据近似线性可分时，通过软间隔最大化，当训练数据线性不可分时，通过使用核技巧及软间隔最大化
通过核函数可以学习非线性支持向量机，等价于隐式地在高维特征空间中学习线性支持向量机。这样的方法称为核技巧
关键点：支持向量机、核函数、序列最小优化算法SMO
一、线性可分与硬间隔最大化
假设输入空间与特征空间为两个不同的空间。输入空间为欧式空间或离散集合，特征空间为欧式空间或希尔伯特空间。假设这两个空间元素一一对应并将输入空间中的输入映射为特征空间中的特征向量。
非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。所以输入都是由输入空间转换到特征空间，支持向量机的学习是在特征空间进行的。
假设给定一个特征空间上的训练数据集
其中xi为第i个特征向量，yi为xi类的标记。学习目标是在特征空间中找到一个分离超平面，wx+b=0
一般地，当训练数据线性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小策略，求得分离超平面，这时的解也是无穷多个的，因为解和初始解的选择和步骤有密切关系。
而线性可分支持向量机利用间隔最大化求最优分离超平面，这时解是唯一的。
--函数间隔与几何间隔
一般来说，一个点距离分离超平面的远近可以表示为分类预测的准信度，在超平面wx+b=0确定的情况下，|wx+b|能够相对地表示点x距离超平面的远近。所以可以用y（wx+b）来表示分类的正确性以及确信度，这就是函数间隔
函数间隔可以表示分类预测的正确性以及确信度，但是选择分离超平面时只有函数间隔是不够的，因为只要成比例地改变w和b，超平面并没有改变，但是函数间隔却变为原来的n倍。所以，我们需要对超平面的法向量w加上某些约束，如规范化，||w||=1，这样使得间隔是确定的，这时函数为几何间隔。
--间隔最大化
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。与感知机相比不仅将正负实例点分来，而且对于最难分的实例点（离超平面最近的点）也有足够的确信度将它们分开
原始问题
对偶问题
在决定分离超平面时只有支持向量起作用，而其他实例不起作用
支持向量的个数一般很少，所以支持向量机由很少的重要的训练样本决定
学习的对偶算法
通过求解对偶问题得到原始问题的最优解，优点是：1.对偶问题往往更容易求解；2. 引入核函数，推广到非线性分类问题
引入拉格朗日函数
其中alpha=（alpha1,...,alphan）T的拉格朗日乘子向量
为了得到对偶问题的解，首先对L（w,b,alpha）对w，b的极小，再对alpha求极大
将目标函数由极大转换为极小得到如下等价对偶最优化问题
补充KKT条件
对于含有不等式约束的优化问题，如何求取最优值呢？常用的方法是KKT条件，同样地，把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a, b, x)= f(x) + a*g(x)+b*h(x)，KKT条件是说最优值必须满足以下条件：
1. L(a, b, x)对x求导为零；
2. h(x) =0;
3. a*g(x) = 0;
也就是说，分类决策函数只依赖于输入x和训练样本输入内积。7.30称为线性可分支持向量机的对偶形式。
在此模型中w和b只依赖于训练数据中对应于alphai>0的样本点
线性支持向量机与软间隔最大化
通常，训练数据中有一些奇异点（outlier）,将这些奇异点去除后剩下的大部分样本点是线性可分的。
线性不可分意味着某些样本点不满足函数间隔大于等于1的约束条件，因此我们可以引进一个松弛变量eta>=0
约束条件变为
目标函数变为
C>0称为惩罚参数，C值大对误分类的惩罚增大，C值小时对于误分类的惩罚减小。
目标函数包含两层含义：使1/2||w||^2尽量小即间隔尽量大，同时使得误分类点的个数尽量小，C是协调二者的关系。
变为如下凸二次规划问题原始问题
解为(w,b,eta)
学习的对偶算法
由于原始问题对于b的解并不唯一，所以实际计算可以取在所有复合条件的样本点上的平均值
