支持向量机（一）你确定不看吗_决策边界的边缘较小,决策边界任何轻微的扰动都可能对分类结果产生较大的影响。

最大边缘超平面（Maximal Margin HyperPlane）超级详细整理

预备知识：

超平面：

超平面是n维欧氏空间中余维度等于一的线性子空间，也就是必须是(n-1)维度。

这是平面中的直线、空间中的平面之推广（n大于3才被称为“超”平面），是纯粹的数学概念，不是现实的物理概念。因为是子空间，所以超平面一定经过原点。

在几何体中，超平面是一维小于其环境空间的子空间。 如果空间是3维的，那么它的超平面是二维平面，而如果空间是二维的，则其超平面是一维线。 该概念可以用于定义子空间维度概念的任何一般空间。 [1] 

在不同的设置中，超平面的对象可能具有不同的属性。 例如，n维仿射空间的超平面是尺寸为n-1的平坦子集。由于其性质，它将空间分成两个半空间。 n维投影空间的超平面不具有此属性。

————————————————————————一条羞耻的分割线————————————————————————

线性分类器最基本的想法是：在样本空间中寻找一个超平面，将不同类别的样本分开

明显可以将训练样本分开的超平面有很多，分类器必须从这些超平面中选择哪个来表示它的决策边界？

为了更好地解释不同的超平面对泛化误差的影响，考虑两个超平面B1和B2。

线性支持向量机

预备知识：

拉格朗日乘子法：

 第一步：引入拉格朗日乘子得到拉格朗日函数：

 第二步：令 偏导为零

 第三步：回代拉格朗日函数得到对偶优化问题：

对偶：

对偶是大自然中广泛存在的，呈“分形”形态分布的一种结构规律，及任何系统往下和往上均可找出对偶二象的结构关系，且二象间具有对立统一性、互涨性和互根性。

对偶问题：每一个线性规划问题都存在一个与其对偶的问题，原问题与对偶问题对一个实际问题从不同角度提出来，并进行描述，组成一对互为对偶问题。

P问题：min f = c'x ，Ax≥b ，且c'≥0；D问题：max g = y'b， y'A≤c'， 且y'≥0。问题 P和问题D互为对偶问题。其特点如下：目标函数的目标互为相反(max，min)；目标函数的系数是另一个约束条件右端的向量；约束系数矩阵是另一个的约束系数矩阵的转置；约束方程的个数与另一个的变量的个数相等；约束条件在一个问题中为“>”，在另一个问题中为 “<”。

(b) 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;

求取这三个等式之后就能得到候选最优值。其中第三个式子非常有趣，因为g(x)<=0，如果要满足这个等式，必须a=0或者g(x)=0.

 

基本性质

直觉上，决策边界的边缘较小，决策边界任何轻微的扰动都可能对分类结果产生较大的影响。也就是说，具有较大边缘的决策边界比那些具有较小边缘 的决策边界具有更好的泛化误差。

因此，根据结构风险最小化原理，需要设计最大化决策边界的边缘的线性分类器，以确保最坏情况下

的泛化误差最小。线性支持向量机(linear SVM) 就是这样的分类器。

给定训练数据集，线性分类器的决策边界可以写成如下线性方程：

$wx+b = 0$

其中 w为法向量，决定了决策边界的方向； 为位移量，决定了决策边界与原点之间 的距离。显然，决策边界由参数 w和 b确定。

假设决策边界能将训练样本正确分类，即对于任意样本点 ：若 y=1，则有 wx+b>0；若y = -1 则有wx+b<0 。那么通过调整决策边界的参数 w和b:

总可以得到：

距离决策边界最近的训练样本点使得上式中的等号成立，因此被称为“支持向量”(support vector)。

两个异类支持向量到决策边界的距离之和被称为决 策边界的“边缘” (margin) ，刚好等于超平面之间的间隔

因此，线性支持向量机的学习就是要寻找满足约束 条件的参数, 使得间隔最大。由于目标函数是二次的，并且约束条件在参数 和

上是线性的，因此线性支持向量机的学习问题是一 个凸二次优化问题，可以直接用现成的优化计算包求解，或者用更高效的拉格朗日乘子法求解。

因为线性SVM还需满足不等式约束 ，所以可以把不等式约束变换成等式约束，这 种变换得到拉格朗日乘子约束，也称作为Karush-Kuhn-Tucker (KKT)

线性SVM假定训练样本是线性可分的，即存在一个 线性的决策边界能将所有的训练样本正确分类。 然而在实际应用中，在原始的样本空间内也许并不存在这样的决策边界。对于这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在映射后的特征空间 内线性可分。

非线性支持向量机：

 

参考资料：
https://baike.baidu.com/item/%E8%B6%85%E5%B9%B3%E9%9D%A2/5360532?fr=aladdin

https://blog.csdn.net/tjcwt2011/article/details/80938400

https://blog.csdn.net/xianlingmao/article/details/7919597

J. Platt: Fast Training of Support Vector Machines using Sequential Minimal Optimization. In B. Schoelkopf and C. Burges

and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning, 1998.