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

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

算法原理

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的凸函数，因此支持向量机是一个凸优化问题。