超详细白板推导:从模型和优化 2 个角度详解 SVM 核函数

SVM 白板推导| 由最大间隔化目标演化的损失函数推导过程 中白板手推了 SVM 的原理,并介绍了硬间隔核函数的实现原理及公式推导,这一节我来详细介绍下 SVM 中的 Keynel Function。segmentfault

一直以来咱们只知道核函数能让 SVM 在高维空间中实现非线性可分,那么,核函数是在什么状况下被提出的呢?又有哪几种核函数呢?数组

本篇文章从 2 个角度讲解 SVM 核函数。函数

  1. 非线性带来高维转换 (模型角度),$X → Φ(X)$
  2. 对偶表示带来内积 (优化角度),$x_i^Tx_j$

从线性可分到线性不可分

以下表中介绍了 感知机 PLA 和 SVM 从线性可分到非线性可分的模型演变结果。性能

而在线性不可分的状况下,若是让模型可以变得线性可分?上面已经讲了,从 2 个角度来理解。优化

1. 非线性带来高维转换,引入 $Φ(X)$

咱们知道高维空间中的特征比低维空间中的特征更易线性可分,这是一个定理,是能够证实的,这里只须要知道就行。spa

那么,咱们就能够想到一个办法,就是把在输入空间中的特征经过一个函数映射到高维空间。rem

假设输入空间有一个点 $X=(x_1, x_2)$,是二维的,咱们经过一个函数 $Φ(X)$ 将其映射到三维空间 $Z=(x_1,x_2,(x_1-x_2)^2)$,从二维到三维空间中的表示为:get

2. 对偶表示带来内积,引入核函数

从另外一个角度来看,以前咱们已经推导出 SVM 的损失函数,Hard-Margin SVM 的对偶问题中,最终的优化问题只与 X 的内积有关,也便是支持向量有关。it

由此,咱们能够将 X 的内积表示为 $Φ(X)$ 的内积 $Φ(x_i)^TΦ(x_j)$。io

而咱们现实生活中,可能 $Φ(X)$ 并非上面举例的三维或者更高维,而是无限维,那么 的 $Φ(X)$ 将会很是难求。

换个角度思考,其实咱们关心的只是 $Φ(x_i)^TΦ(x_j)$ 的内积,并不关心 $Φ(X)$。有没有一种方法能直接求出内积?答案是有的。

咱们能够引入核函数 keynel function。

如上中的一个核函数,咱们能够直接求出 X 的内积,避免在高维空间中求 $Φ(x_i)^TΦ(x_j)$。

针对核函数,咱们能够总结出 3 点。

  1. 当在线性不可分的时候,咱们能够将输入空间中的特征映射到高维空间,来实现线性可分。
  2. 在高维空间中,因为计算 $Φ(x_i)^TΦ(x_j)$ 很是困难,由于 $Φ(X)$ 可能有无限维。
  3. 所以,咱们引入核函数,将本来须要在高维空间计算的内积变成在输入空间计算内积,也能达到同样的效果,从而减少计算。

核函数存在条件

定理: 令 $χ$ 为输入空间,$k(⋅,⋅)$ 是定义在 $χ×χ$上的对称函数,则 $k$ 是核函数当且仅当对于任意数据$D=x_1,x_2,⋯,x_m$,“核矩阵” $K$ 老是半正定的:

定理代表,只要一个对称函数所对应的核矩阵半正定,那么它就能够做为核函数使用。事实上,对于一个半正定核矩阵,总能找到一个与之对应的映射 $ϕ(X)$。换言之,任何一个核函数都隐式定义了一个称为 “再生核希尔伯特空间” 的特征空间。

常见的核函数

经过前面的介绍,核函数的选择,对于非线性支持向量机的性能相当重要。可是因为咱们很难知道特征映射的形式,因此致使咱们没法选择合适的核函数进行目标优化。因而 “核函数的选择” 称为支持向量机的最大变数,咱们常见的核函数有如下几种:

此外,还能够经过函数组合获得,例如:

  • 若 $k_1$ 和 $k_2$ 为核函数,则对于任意正数 $γ_1,γ_2$,其线性组合也是核函数。$γ_1k_1+γ_2k_2$
  • 若 $k_1$ 和 $k_2$ 为核函数,则核函数的直积也是核函数。$k_1⨂k_2(x,z)=k_1(x,z),k_2(x,z)$
  • 若k_1k1为核函数,则对于任意函数 $g(x)$ 也是核函数。 $k(x,z)=g(x)k_1(x,z)g(z)$

对于非线性的状况,SVM 的处理方法是选择一个核函数 $κ(⋅,⋅)$,经过将数据映射到高维空间,来解决在原始空间中线性不可分的问题。因为核函数的优良品质,这样的非线性扩展在计算量上并无比原来复杂多少,这一点是很是可贵的。

固然,这要归功于核方法——除了 SVM 以外,任何将计算表示为数据点的内积的方法,均可以使用核方法进行非线性扩展。

相关文章
相关标签/搜索