支持向量机是一种二分类模型，其主要思想是最大化特征空间中两个类别之间的间隔。按照数据集是否线性可分，有：

1. hard-margin SVM：数据集线性可分
2. soft-margin SVM：数据集整体线性可分，但存在少量不可分的错误点
3. kernel Method：数据集线性不可分，是非线性问题

   1. 支持向量机(hard-margin SVM)建模

   给定训练样本集 ，其中 ， 。分类学习最基本的想法就是基于训练集 在样本空间中找到一个划分超平面，将不同类别的样本分开。在样本空间中，划分超平面可通过如下线性方程来描述：
   
   其中 为法向量，决定了超平面的方向； 为位移项，决定了超平面与原点之间的距离。
   但能将训练样本分开的划分超平面可能有无数个，为了对训练样本局部扰动的容忍性最好，支持向量机要求超平面不仅能对训练样本进行正确分类，并且要满足使得两个类别之间的间隔最大化，可表示为：
   

，但当 ~~ 和 等比例缩放后超平面不变而函数间隔 却变化了。所以需要将 的大小固定，如将函数间隔除以 以实现 的归一化，此时 ，代入 得：~~ 因为 ~~ ，故 ，因函数间隔 的值随着 和 等比例变化而变化，不妨令 ，代入 得：~~

更新：
其中，即为距分隔超平面最近的数据点的距离，根据点与平面距离公式可得：

因为当 和 等比例缩放时，超平面不变，而 的值会变化，不妨令离分隔超平面最近的点满足，故上式为：

因为大于0，故等价于，此时SVM如下：

上式等价于：

通过拉格朗日乘子法将带约束优化问题转换为无约束优化问题，即：


因该问题为二次凸优化问题，满足强对偶，即 ， 式等价于其对偶问题：

2. 数学模型求解

1) 求 :

首先解 ，令 ，带入 ：

再令 ，得 ，带入 式得：

2) 求 ：

此时式 可写为：

通过SMO序列最小优化算法(Sequential Minimal Optimization, SMO)可迭代求得参数 SMO算法：每次取 > 为未知数 ，令其他值 > 为常数由 > ，可得 > 与 > 的线形关系，问题转化为一元函数对该一元函数求极值，可解得 > 和 > 的值如此反复迭代

3）求 ：

由KKT条件，训练样本集中的所有点都必须满足：

当：

• ，即 ，样本点 不是支持向量，此时 ；
• ，即 ，样本点 是支持向量，此时

所以 所对应的样本点 即为支持向量
理论上，可选取任意支持向量并通过求解式子 获得 ，但现实任务中常采用一种更鲁棒的做法：使用所有支持向量求解的平均值：

3. 软间隔支持向量机

在之前的讨论中，我们一直假定训练样本在特征空间中是线形可分的，然而在现实任务中训练样本中往往有一些数据点不能满足线性可分，为此，要引入“软间隔”，在最大化间隔的同时，使不满足约束的样本尽可能少。定义loss为：

合并成一项为 ，这就是hinge loss。令 ，数学模型变为：

通过拉格朗日乘子法可得到式 的拉格朗日函数：

其中 是拉格朗日乘子。
令 对 的偏导为零可得：

将 代入 即可得到式 的对偶问题：

由KKT条件中 ，当 ， ，该样本点是支持向量：

• 当 ，由 ，有 ，又因 ，所以 ，即该样本点恰在最大间隔边界上。

• 当 ， ，则 。此时若 ，样本点在最大间隔内部；若 ，则该样本点被错误分类。

  4. 核函数

  在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。核函数是为处理非线性情况，若直接映射到高维计算恐维度爆炸，故在低维计算，等效高维表现。
  如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。

  5. 总结

  1）LR与SVM

  相同：

• 都是线性分类器。本质上都是求一个最佳分类超平面

• 都是监督学习算法

• 都是判别模型。判别模型不关心数据是怎么生成的，它只关心信号之间的差别，然后用差别来简单对给定的一个信号进行分类。常见的判别模型有：KNN、SVM、LR，常见的生成模型有：朴素贝叶斯，隐马尔可夫模型

  不同：

• LR是参数模型，svm是非参数模型

• 从目标函数来看，区别在于逻辑回归采用的是logistical loss，SVM采用的是hinge loss，这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重
• SVM的处理方法是只考虑support vectors，也就是和分类最相关的少数点，去学习分类器。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重
• 逻辑回归相对来说模型更简单，好理解，特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些，SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算
• logic 能做的 svm能做，但可能在准确率上有问题，svm能做的logic有的做不了

• LR适合数据量大的场景（计算速度快），SVM适合数据量较小的场景（只有支持向量决定决策面）。

  2）核函数的选择

• 特征多用linear（高维空间通常线性可分）

• 特征少用RBF（高斯核函数对数据进行升维，使数据线性可分，通常时间较长）

  3）线性分类器与非线形分类器

• 线性分类器可解释性好，计算复杂度较低，不足之处是模型的拟合效果相对弱些。
  LR,贝叶斯分类，单层感知机、线性回归

• 非线性分类器效果拟合能力较强，不足之处是数据量不足容易过拟合、计算复杂度高、可解释性不好。
  决策树、RF、GBDT、多层感知机

  4）求对偶问题的好处

• 对偶问题往往更容易求解

• SVM的对偶问题中输入向量涉及的恰好都是向量间的内积，可自然引入核函数进而推广到非线性分类问题

  5）kkt条件

  最后由kkt条件中的互补条件可求。
  

  6）核函数

  设是输入空间，是特征空间，是输入空间到特征空间的映射，若对所有，满足：
  
  则称为核函数。