SVM数学基础

0. 前言

本文将SVM中涉及的几个数据概念进行详细的探讨,包括拉格朗日乘子法、KKT条件、对偶问题、核技巧等。

1. 拉格朗日乘子法

参考

一句话解释:最值处,目标与约束的梯度向量平行

引例

x2 y = 3上的点,到原点的最短距离。

image-20220719161524528

在极值点处,圆与曲线相切;

圆的梯度与曲线的梯度向量平行;

拉格朗日乘子法梯度平行

梯度向量平行,数学符号表示为:image-20220719162206216

image-20220719162241595

定义

image-20220719162703114

变形

image-20220719162743137

F被成为拉格朗日函数。

引申到多个约束条件

image-20220719162853011

image-20220719162930189

image-20220719162953008

2. KKT条件

一句话解释不等约束:内部约束无效,边界才有效。
参考

不等式条件

等式约束就是拉格朗日乘子法典型算法,这里主要是针对不等式的条件:

image-20220719163146304

不等式条件要分成2种情况分别讨论,假设x* 为满足条件的最佳解,K = x∈ Rn | g(x) <=0

构建拉格朗日函数: L(x, λ) = f(x) + λg(x)

  1. g(x*) < 0,最佳解位于K的内部,约束条件是无效的。 这时候▽f = 0,且λ = 0.

  2. g(x*) = 0,最佳解落在K的边界上,约束条件是有效的,这时候 ▽f 的方向与 ▽g 的方向相反,表示为

    ▽f = -λ▽g 且λ >= 0

综合以上两种情况: λg(x) = 0。示例图如下:

image-20220719164513065

综合条件如下:

image-20220719164600979

这个条件就是KKT条件了

多个等式与不等式情况

image-20220719165838680

3. 对偶问题

SVM的对偶问题是通过惩罚项,强制目标函数在约束范围内,并通过不等式转换问题。
参考

找一个优化问题的对偶问题的一般因为是对偶问题比原问题更好解决,并且对偶问题的解和原问题是一样的。上面的拉格朗日函数也可以看做原问题的对偶问题。

为了去掉问题中的约束,可以把它们作为惩罚项加到目标函数中image-20220719172110295 其中 M, N 是两个很大的正数,在数值解法中可以直接这样做,这个就是罚函数法的思路 。不过在理论推导时这样做是不严谨的,除非 M, N 为无穷大。所以就把原问题改写 image-20220719172153842

这个意思是,x一定要满足约束,否则内层的max会让μ或λ无穷大,导致最后结果无穷大。根据KKT条件,满足条件下结果时,结果为0。

利用不等式:image-20220719173110361

等号满足时,是强对偶。

这样再来看:

image-20220715180722841

就能看懂了,黄色的字体是对内层求偏导数等于0之后得到的值,然后导入到对偶问题中,最后得到结果。

4. 核技巧

参考

核技巧在上节的SVM中讲的已经挺明白了,最初想法是把数据放到高维空间,然后再有决策超平面将他们分开,但这种运算成本更高(如果是无限维也不可能)。通过核函数可以先做变换,然后再求内积,达到相同的效果,并且降低了运算量。

核函数 = 内积 = 相似度

image-20220717174221416

两个向量相差越大,核函数就越小,反之越大。

5. 小结

  • 拉格朗日乘子法的本质是最值处梯度方向平行
  • KKT条件是不等式条件下,约束条件内部与边界的整合
  • 对偶问题是通过惩罚项,强制目标函数在约束范围内
  • 核技巧是通过内积,简化高维内积计算

6. 极大似然估计

似然函数

原文

似然函数L(x1, x2 ...xn; θ)指的是随机变量X取到指定样本x1,x2...xn时的概率的大小。这个概率值完全由未知参数 θ决定。

由于L(x1, x2 ...xn; θ)是关于 θ的函数,使L(x1, x2 ...xn; θ)取得最大值的θ,就是位置参数θ最大似然估计。

求解方式:由于似然函数是乘积形式,求导比价麻烦,先对其取ln,然后在对 θ取偏导数求解。

评论

Your browser is out-of-date!

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

×