支持向量机笔记

1. 前言

想着短时间快速看完整本的统计学习,目前而言,实现这个目标不太现实。想着与其降低质量看全,不如保证质量少看。在这样一种策略下,计划对:SVM、隐马尔科夫链条件随机场、PCA、LSA等5中模型进行学习。在这个过程中,会涉及一些不懂的概念,凿穿它们。这里是第一个模型SVM。

原视频

  • 定义问题

    SVM:最大化正负超平面之间的距离

  • 求解问题

    仿射约束下的凸优化问题

  • 软硬间隔

    软间隔(Soft Margin):间隔距离与损失值之间的取舍

  • 核技巧

    升维转换

    通过核函数,可以避免增加数据的维度,且又能达到相同的分类效果

    SVM本质是量化两类数据的差异,而核函数提供高纬度向量相似度的测量,通过选取合适的核函数,就可以不用知晓具体的维度转换函数,直接获得数据的高维度差异度。

2. 问题定义

SVM:最大化正负超平面之间的距离

image-20220715112131315

image-20220715170150943

向量w的方向:决策超平面垂直

image-20220715170226615

为什么向量w与决策超平面(线)垂直?从w1x1 + w2x2 + b = 0可以看出,w向量与该线垂直。

正负超平面的距离L与w的关系:L是xm - xn在w上投影,取L的做大值就是||w||的最小值

image-20220715170602996

从另外一个角度看,L是两倍的点到决策超平面的距离,公式如下:

image-20220718170351531

约束条件:仿射函数约束

image-20220715170814418

问题归结为:仿射约束下的凸优化问题。使用方法是拉格朗日乘子法

image-20220715112954878

拉格朗日乘子法需要确认,在其他推导中,后边的pi^2并不存在。

3. 求解问题

KKT条件

image-20220715171758412

新等式4代表:在分割超平面上,λ可以不为0,不在超平面上λ必须为0。这些在分割超平面上的点,被称为支持向量。

注意3带入4,就是消去了pi,与不引入pi结果是一样的。

image-20220715172450420

λ看做违背约束条件的乘法系数;

当不满足约束条件时,且λ<0时,没有最小值,故若不满足条件,λ>=0

视觉:

image-20220715172932071

image-20220715173638931

调整g1、g2的梯度向量得到f的梯度向量。2个约束条件加入后,两约束的交接处是最优解。

image-20220715174123242

非边界上的点,不参与计算。

image-20220715174517291

注意第一个等式,w向量与样本点(支持向量)的关系:支持向量的某种线性组合。

KKT条件

SVM对偶性

示例:

image-20220715180615609

image-20220715180722841

注:对偶问题的推导,黄色字体是将KKT条件进行了带入;最后的结果,只有λ是未知的,xi与yi已知。

image-20220715180827144

得到λ之后,带入到KKT条件中,求出w向量。

对偶问题有一个非常好的特征,最优解仅根据支持向量的点积结果所决定,也可以理解为仅由支持向量的空间相似度所决定。

  • 强对偶的推导

    image-20220715175156421

    构建新问题,

    注:这一步黄色的等式没有看懂;

    这一步应该是凸函数的性质,但我觉得更像是凹函数?

    image-20220715175810128

    两者同时成立时,是强对偶,而仿射约束下,强对偶成立,求解对偶问题,即可得到最优解。

    image-20220715180049913

4. 核技巧

image-20220717165609037

通过核技巧,将原维度x变到新维度T(x),从而进行求解。

image-20220717165831937

通过核函数直接求升维之后的结果。

二项式核函数

image-20220717170044046

举例说明多项式核函数

image-20220717170206481

核函数中c的作用可以丰富维度多样性

高斯核函数

image-20220717170346192

高斯核函数**(RBF)**相当于无限维多项式情况

image-20220717174221416反应了向量相似度与两点距离的关系,两点距离越大,其相似度越向0靠近。

小gamma( γ)值,数据点间的相似度被放大了,使数据点更容易被简单超平面分割。

image-20220717183022296

由于指数函数的特性等价于无限多项式的和,也就将达到了向无限维推广的目的。高斯核函数就成了最受人喜欢的核函数。

5. 软间隔

image-20220717183652172

新加入的点A违背了约束条件。

image-20220717183854492

铰链损失函数,

image-20220717184159782

软间隔的最优化问题,以及其余||w||之间的负相关关系:间隔越大,错误越多;间隔越小,错误越小。

image-20220717184318383

最终增加一个常数项C,来对损失函数进行惩罚

等式前一项||w||2/2 是可以看做政策,后一项是损失。这个损失被成为合页损失(Hinge)。

6. 实验

最终,SVM最重要的2个参数:gamma( γ)与C。gamma( γ)是高斯核的系数,C是软间隔的惩罚系数。

gamma越大,数据间的相似度越小;C越大,对错误的容忍越低,正负超平面的距离变窄。

综合看:gamma与C越大,正确率越高,同时泛化能力越低。

7. 总结

  • 拉格朗日乘子法
  • 对偶问题
  • 核技巧
  • 软间隔的惩罚系数

从应用上看,生成好数据集,然后选择对应的核函数,接着进行调参即可。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×