Paul C's Blog

To be funny,to grow up!

0%

SVM

学习策略:间隔最大化。形式化为一个凸二次规划(convex quadratic programming)问题,等价于正则式的合页损失函数的最小化问题。

由简到繁:

  • 线性可分——>学习线性的分类器——>线性可分(硬间隔)支持向量机;
  • 数据近似线性可分—>软间隔最大化—>学习线性的分类器—>线性支持向量机;
  • 数据线性不可分—>kernel trick+软间隔最大化—>非线性支持向量机(等价于在高维空间中学习线性支持向量机);

1.超平面:

image-20220526234208124

2.函数间隔和几何间隔

因为超平面wx+b=0,所以对于点(xi,yi),(wxi+bi)能够表示点距离超平面的远近,其与yi的乘积的符号可以用来表示分类的正确性(-1表示分类错误,分类正确时)。

所以ri=yi(wxi+bi)定义为超平面关于样本点(xi,yi)的函数间隔;超平面关于训练集T的函数间隔为所有超平面关于每个样本点的函数间隔的最小值。

r’=min(ri)

函数间隔规范化(确保超平面不变的时候,间隔也是确定的)后,即w=w/||w||,b=b/||w||,函数间隔r'变为几何间隔r

约束优化问题为:求解能够正确划分训练数据集并且使得几何间隔最大的分离超平面

约束:正确划分训练数据集==任意样本的距离大于最小距离==yi(w/||w||·xi+b/||w||) >=r== yi(w·xi+b) >=r'

求解:max几何间隔r==max {r’/||w||} ,由于w和b可以等比例放缩,所以可令r’=1,此时最优化问题为调整w和b以最大化1/||w||,在约束条件y_i(w·x_i+b) ≥1下,而该式等价于下面的凸二次规划(convex quadratic programming)问题求解

image-20220607175209460

上面的式子即为最大间隔法的算法实现。

之所以构造成二次规划问题,是为了方便之后的求导。

3.间隔最大化

学习算法思想:让几何间隔最大化,即max r ,以足够确信对超平面周围的点正确分类,通过求解上个分段的最优化问题,解得超平面(w*,b*)。

由此得到分类决策函数为f(x)=sign(w*x+b*)1.支持向量

4.支持向量

在线性可分情况下才存在。两个类别中距离分离超平面最近的样本。即对于支持向量(xi,yi),yi(w·xi+b) =1,或者说yi(w·xi+b) -1=0,它们构造出来两个超平面(w·xi+b)±1=0,记这两个超平面为H1和H2。

由于移动两个边界以外的样本对解无影响,而移动支持向量解会发生变化,所以支持向量非常重要。

5.对偶问题

·genralized lagrange uality

原始约束最优化问题转化为广义拉格朗日函数的极小极大(min max L(x,α,β))问题,在KKT条件(导数值=0,对偶互补条件满足,原来的条件满足,拉格朗日乘子>=0)下,原始问题和对偶问题的最优值相等,此时,去解对偶问题的最优解。

附录

内积

image-20220607163751333

完备性就是说任意柯西列的极限仍然在这个空间中。

完备的内积空间称为希尔伯特空间。它是欧几里德空间(距离、内积、向量所具有的线性性质)的一个推广,其不再局限于有限维的情形。或者,如果一个空间线性的完备的,并且规定了范数内积距离的,就叫做希尔伯特空间。

image-20220607163542501

向量的长度叫做模,将模的概念推广,只要满足正定性、齐次性和三角不等式的映射就叫做范数。

L0范数是指向量中非0的元素的个数。(L0范数很难优化求解)

L1范数是指向量中各个元素绝对值之和

L2范数是指向量各元素的平方和然后求平方根,通常意义的模长。

凸优化

若二阶导数在区间上非负,则称为凸函数

若二阶导数在区间上恒大于0,则称严格凸函数

image-20220428110757207

假设f、g、h在定义域内是连续可微的,且目标函数f和不等式约束函数g是凸函数,等式约束h是仿射函数(线性函数),则约束最优化问题称为凸优化问题。

开发技巧

SVM+poly核函数+degree=1,相当于线性SVM。

SVM在标准化后的数据上效果好

linear有上限,开始即巅峰,巅峰即退役;而rbf可调参数多,训练速度快,可能性大。

1655918115199