支持向量机

https://blog.****.net/sinat_20177327/article/details/79729551

https://blog.****.net/c406495762/article/details/78072313

 

1、拉格朗日函数和拉格朗日乘子

要找到函数 z=f(x,y) 在附加条件 φ(x,y)=0 ，下可能的极值点，可以先引进拉格朗日函数：

其中 λ 称为拉格朗日乘子。求其对 x 与 y 的一阶偏导数，并使之为零，然后再于附加条件方程联立：

同理可以扩展至多元函数：

 

2、超平面：这里说的超平面实际为仿射超平面

仿射超平面是仿射空间中的代数1的仿射子空间。 在笛卡尔坐标中，可以用以下形式的单一线性方程来描述这样的超平面（至少有一个ai不是0）：

在真实仿射空间的情况下，换句话说，当坐标为实数时，该仿射空间将空间分成两个半空间，它们是超平面的补码的连接分量，由不等式给出：

和

作为一个例子，一点是一维空间中的超平面，一条线是二维空间中的超平面，一个平面是三维空间中的超平面。 三维空间中的一行不是超平面，并且不将空间分成两部分（这样一条线的补码连接起来）。

欧几里德空间的任何超平面具有两个单位法向量。

仿射超平面用于定义许多机器学习算法中的决策边界，例如线性组合（倾斜）决策树和感知器。

 

3、凸函数：

首先，以上的支持向量机是凸函数。理解凸函数，我们还要先明确另一个概念，凸集。在凸几何中，凸集(convex set)是在)凸组合下闭合的放射空间的子集。看一幅图可能更容易理解：

左右量图都是一个集合。如果集合中任意2个元素连线上的点也在集合中，那么这个集合就是凸集。显然，上图中的左图是一个凸集，上图中的右图是一个非凸集。

凸函数的定义也是如此，其几何意义表示为函数任意两点连线上的值大于对应自变量处的函数值。若这里凸集C即某个区间L，那么，设函数f为定义在区间L上的函数，若对L上的任意两点x1，x2和任意的实数λ，λ属于(0,1)，总有：

则函数f称为L上的凸函数，当且仅当其上镜图（在函数图像上方的点集）为一个凸集。再看一幅图，也许更容易理解：

像上图这样的函数，它整体就是一个非凸函数，我们无法获得全局最优解的，只能获得局部最优解。比如红框内的部分，如果单独拿出来，它就是一个凸函数

 

4、线性可分支持向量机：

首先用向量形式表达超平面方程：

其中w为法向量，决定了超平面的方向，b为位移量，可以通过三维坐标系的点到平面的距离来理解点到超平面的距离，因为点到超平面的距离没有物理概念，只有数学概念：

点到平面的距离： 点(x0,y0,z0)到了平面Ax+By+Cz+D=0的距离 为：d=|Ax0+By0+Cz0+D|/√(A^2+B^2+C^2)

假设超平面能将训练样本正确地分类，即对于训练样本，满足以下公式：

公式称为最大间隔假设，yi=+1表示样本为正样本，yi=−1 表示样本为负样本，式子前面选择大于等于+1，小于等于-1只是为了计算方便，原则上可以是任意常数，但无论是多少，都可以通过对 w 的变换使其为 +1 和 -1 ，此时将公式左右都乘以 yi，得到如下：

实际上等价于（训练集中的所有样本都应满足的公式）：

如下图所示，距离超平面最近的这几个样本点满足 ，它们被称为“支持向量”。虚线称为边界，两条虚线间的距离称为间隔（margin）：

下面我们开始计算间隔，其实间隔就等于两个异类支持向量的差在 w 上的投影，即：

其中 x+ 和 x−分别表示两个正负支持向量，因为 x+ 和 x−满足 ，即：

推出：

代入w 上的投影公式中可以得到：

至此，我们求得了间隔，SVM的思想是使得间隔最大化，也就是： 

显然，最大化 2/||w||相当于最小化 ||w||，为了计算方便，将公式转化成如下： 

以上公式即为支持向量机的基本型。

 

5、线性可分支持向量机极值求解：

我们通过拉格朗日乘子来求解