机器学习理论基础—支持向量机的推导（一）

机器学习理论基础—支持向量机的推导

算法原理

SVM:从几何角度，对于线性可分数据集，支持向量机就是找距离正负样本都最远的超平面，相比于感知机，其解是唯一的，且不偏不倚，泛化性能更好。

超平面

n维空间的超平面（wT X+ b= 0，其中w,x ∈ R）

• 超平面方程不唯—
• 法向量w和位移项b确定一个唯一超平面
• 法向量w垂直于超平面 （缩放w，b时，若缩放倍数为负数会改变法向量方向)
• 法向量w指向的那一半空间为正空间，另一半为负空间
• 任意点到超平面的距离公式为
  

点到超平面的距离公式

理论证明：提出假设条件

1.由于法向量W与x1x0向量平行，首先计算两个向量点乘的模长：而下x1x0向量的模长就是要求的距离R

2.按照点乘的坐标形式来进行计算，最后令两个式子相等即可以得到最终的结果。

两个式子相等得到最终的结果：

几何间隔

定义：M关于超平面的几何间隔为：（样本点的形式）

正确分类是指：正样本都集中在正空间，负样本都集中在负空间。

• 正确分类时r(i)>0,几何间隔此时也等价于点到超平面的距离。
• 没有正确分类时：r(i)<0

（数据集的定义形式 X为（x1,x2…）的数据集）：即是所有样本点几何间隔的最小值。

支持向量机

模型定义：给定线性可分数据集X，支持向量机模型希望求得数据集X关于超平面的几何间隔达到最大的那个超平面，然后套上一个sign函数实现分类功能

其中与感知机模型的区别在于，参数的不同支持向量机中的参数为b而感知机中的参数为一个阈值。

几何间隔最大的超平面一定是距离正负样本最远的超平面。

当超平面没有正确划分正负样本时：几何间隔最小的为误分类点，因此r<0
当超平面正确划分超平面时：r≥0，且越靠近中央越大。

支持向量机学习策略

策略：给定线性可分数据集X，设X中几何间隔最小的样本(xmin,ymin），那么支持向量机找超平面的过程可以转化为以下带约束条件的优化问题。

根据几何间隔的定义带入进行求解，可以得到最终的结果式子与约束条件


化简后的公式存在的问题：
假设该问题的最优解为(w*,b*），那么(αw*，αb*），α ∈R+也是最优解，且超平面也不变，因此还需要对w,b做一定限制才能使得上述优化问题有可解的唯一解。不妨令

因为对于特定的(Xmin,Ymin)来说，使得该公式为1的α 的值只有一个
因此该公式和约束条件可以进一步优化为：

为了便于计算在进一步进行化简得到最终的学习策略结果（平方取反转换为最小值问题）。

此优化问题为含不等式约束的优化问题，且为凸优化问题，因此可以直接用很多专门求解凸优化问题的方法求解该问题，在这里，支持向量机通常采用拉格朗日对偶来求解。

凸优化问题

若目标函数f(x)是凸函数，约束集合是凸集，则称上述优化问题为凸优化问题，特别地，g(x)是凸函数，h(x)是线性函数时，约束集合为凸集，该优化问题为凸优化问题。显然，支持向量机的目标函数1/2||w||2是关于w的凸函数，不等式约束1 一y(wtx(i)十b)是也是关于w的凸函数，因此支持向量机是一个凸优化问题。

拉格朗日对偶

用来处理一般的约束问题，对于上面的公式，使用拉格朗日函数进行构造可得有

其中μ=（μ1,μ2，·,μm)T,入=（入1,入2，.,入n)T为拉格朗日乘子向量。
定义上述优化问题的拉格朗日对偶函数T(μ,入）（注意其自变量不包含x）为L(x，μ，入)关于x的下确界，也即：

无论上述优化问题是否是凸优化问题，其对偶函数T(μ,入)恒为凹函数 (证明参见《凸优化》）当μ≥0时，(μ,入)构成了上述优化问题最优值p*的下界，也即:
对上面的使用拉格朗日对偶函数求最优值提供参考的证明步骤

定义在满足μ≥ 0这个约束条件下求对偶函数最大值的优化问题为拉格朗日对偶问题（原优化问题称为主问题）

设该优化问题的最优值为d*，显然d≤ p，此时称为“弱对偶性"成立，若d* = p*，则称为“强对偶性"成立。找到了求p*的方法（上面有参考的证明过程）

无论主问题是否为凸优化问题，对偶问题恒为凸优化问题，因为对偶函数T(μ,入)恒为凹函数（加个负号即可转为凸函数），约束条件μ≥0恒为凸集。

当主问题满足某些充分条件时，强对偶性成立。常见的充分条件有Slater条件：“若主问题是凸优化问题，且可行集D中存在一点能使得所有不等式约束的不等号成立，则强对偶性成立”（证明参见《凸优化》）。显然，支持向量机满足Slater条件。

KKT条件（5个）

设f(x),g(x),h(x)一阶偏导连续，x*，（μ*，入*)分别为主问题和对偶问题的最优解，若强对偶性成立，则x*，μ*，入*一定满足如下5个条件（证明参见《凸优化》

得出了第一种推导形式

根据支持向量机的主问题直接引出拉格朗日函数=0并对其求一阶偏导

若将w,b合并为=（w;b)，显然上式是关于w的凸函数，直接求一阶导令其等于0，然后带回即可得到最小值，也即拉格朗日对偶函数。