1、前言
支持向量机(support vector machines,SVM)是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器。间隔最大使之有别于感知机。
2、线性可分支持向量机
一般地，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。感知机利用误分类最小的策略，但是解有无穷多个；线性可分支持向量机利用间隔最大化求最优分离超平面，解唯一。
2.1线性可分支持向量机
给定线性可分训练数据集，通过间隔最大化或者等价地求解相应凸二次规划问题学习得到的分离超平面为
相应的分类决策函数为
称为线性可分支持向量机。
2.2 函数间隔
函数间隔(functional margin)概念：wx+b的符号与类标记y的符号是否一致能够表示分类是否正确，所以可用量y(wx+b)来表示分类的正确性及确信度。
对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点（xi,yi）的函数间隔为
注意：即使超平面不变，函数间隔仍会受w和b绝对大小影响。
2.3 几何间隔
一般地，当样本点被超平面正确分类时，点x与超平面的距离是
其中||w||是w的L2范数，这就是几何间隔的定义。定义超平面关于训练数据集T的几何间隔为超平面关于T中所有样本点的几何间隔之最小值，可知
，当||w||=1时几何间隔和函数间隔相等。
2.4 硬间隔最大化
对线性可分的训练集而言，这里的间隔最大化又称为硬间隔最大化，求最大间隔分离超平面，优化为以下凸二次规划问题：
2.5 对偶算法
通过求解对偶问题得到原始问题的最优解。
首先引进拉格朗日乘子，定义拉格朗日函数
其中α为拉格朗日乘子向量。
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题，即需要先求L对w,b的极小，再求对α的极大。
（1）求minL(w,b,α)
分别对w,b求偏导=0，带入化简得到以下式子：
(2)求minL(w,b,α)的极大，即是对偶问题
优化后：
假设α是对偶最优化问题的解，则原始问题的解为
由此可知，分离超平面可以写成
分类决策函数可以写成：
综上，对于给定的线性可分训练数据集，可以首先求对偶问题的解，再利用公式求得原始问题w*,b*,从而等到分离超平面及分类决策函数，这种算法称为线性可分支持向量机的对偶学习算法。
2.6支持向量和间隔边界
与分离超平面距离最近的样本点的实例称为支持向量，约束条件之间形成一条长带，宽度为
,在决定分离超平面时只有支持向量在起作用。
一般将训练数据集中对应于 
的样本点的实例称为支持向量。
3、线性支持向量机
如果训练数据是线性不可分的，那么上述方法的不等式约束不能都成立，需要修改硬间隔最大化，使其成为软间隔最大化。
线性不可分意味着某些特异点不能满足函数间隔大于等于1的约束条件，可以对每个样本引进一个松弛变量。
学习问题变成如下凸二次规划问题：可以证明w的解是唯一的，但b的解存在一个区间。
这样约束条件变成：
目标函数变为：
C为惩罚参数，最小化目标函数包含两层意思，是前半部分尽量小即间隔尽量大，同时使误分类点的个数尽量小
3.1对偶函数
（1）求w,b,?极小值
（2）再对极小值求α的极大值
以上过程省略，由此可知，分离超平面可以写成
分类决策函数可以写成：
3.2合页损失函数
可以认为是0-1损失函数的上界，而线性支持向量机可以认为是优化合页损失函数构成的目标函数。
间隔最大化可形式化为一个求解凸二次规划的问题，也等价于正则化的和也损失函数的最小化问题。
4、非线性支持向量机
非线性分类问题：用线性分类方法求解分线性分类问题分为两个步骤，首先使用一个变换将原空间的数据映射到新空间，然后在新空间里用线性分类学习方法从训练数据中学习分类模型，核技巧就是这样的方法。
核函数：设X是输入空间（欧氏空间的子集或离散集合），H为特征空间（希尔伯特空间），一般是高维或者无穷维的，如果存在一个从X到H的映射，使得对所有x,z属于X，函数K(x,z)满足条件
，点乘代表内积，则称K(x,z)为核函数。
核技巧：基本思想是通过一个非线性变换将输入空间对应于一个特征空间，使得输入空间中的超曲面模型对应于特征空间中的超平面模型，在学习和预测中只定义核函数，而不显式定义映射函数，特征空间和映射函数取法不唯一。
正定核：通常说的核函数是指的正定核函数，只要满足正定核的充要条件（半正定矩阵，难以验证），那么给定的函数K就是正定核函数。
4.1 算法
选取适当的核函数K和适当的参数C，将线性支持向量机对偶形式中的内积换成核函数，构造求解最优化问题
分离超平面可以写成
分类决策函数可以写成：
4.2常用核函数
1多项式核函数
2高斯核函数
3字符串核函数：核函数不仅可以定义在欧式空间上，还可以定义在离散数据的集合上，字符串核函数给出了字符串中长度等于n的所有子串组成的特征向量的余弦相似度
4.3 序列最小最优化（SMO）算法
smo是一种快速求解凸二次规划问题的算法，基本思路是：如果所有变量都满足此优化问题的KKT条件，那么解就得到了，否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，不断地将原问题分解为子问题，并求解
参考博客：https://blog.csdn.net/weixin_35479108/article/details/87605228
原文：https://www.cnblogs.com/xutianlun/p/12249278.html