机器学习支持向量机

机器学习之支持向量机（中）

2019-03-18  本文已影响0人  Vophan

这一节，我们来讲解一下什么叫做核技巧，也就是kernal trick

img

前面我们讲的hard margin和soft margin分别是线性可分，线性不可分的情况，但是我们的支持向量机都是线性支持向量机，但是还有一种情况就是：非线性可分

如图，我们在低维情况下无法用超平面解决的分类问题。

所以，我们就要使用核技巧

所以，什么是核技巧

对于上面的非线性可分问题，我们解决的思路，就是通过映射函数将数据升维到高维空间，然后非线性可分问题就变成了线性可分问题。但是，我们需要知道一个概念：维数灾难

什么是维数灾难呢？

维数灾难（英语：curse of dimensionality，又名维度的诅咒）是一个最早由理查德·贝尔曼（Richard E. Bellman）在考虑优化问题时首次提出来的术语，用来描述当（数学）空间维度增加时，分析和组织高维空间（通常有成百上千维），因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到，如物理空间通常只用三维来建模。

举例来说，100个平均分布的点能把一个单位区间以每个点距离不超过0.01采样；而当维度增加到10后，如果以相邻点距离不超过0.01小方格采样一单位超正方体，则需要1020 个采样点:所以，这个10维的超正方体也可以说是比单位区间大1018倍。（这个是理查德·贝尔曼所举的例子）

所以，并不是维度高了，我们就可以解决这个问题了。

所以，这里就体现出了核函数的重要性：

什么是核函数

简单的说就是，低维的一个方法k(x,y)可以达到高维映射函数的效果，那么这个函数就是核函数。

所以采用核函数，我们就可以在将数据升维的同时，避免了维度灾难带来的巨大计算量。

举个例子：

img

公式推导

首先，我们回忆一下前面的公式，在最后，我们得到了：
min L(\omega, b, \lambda) = \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_ix_j)-\sum_{i=1}^N\alpha_i
现在，我们通过核技巧，将原来低维空间中数据的内积变为高维特征空间中的内积，用核函数的形式表示：
min L(\omega, b, \lambda) = \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jk(x_i, x_j)-\sum_{i=1}^N\alpha_i

常用核函数

  1. 多项式核函数
    K(x, z) = (xz+1)^p
    对应的分类决策函数：
    f(x) = sign(\sum_{i=1}^N a_i^*y_i(x_ix_j+1)^p+b^*)

  2. 高斯核函数
    K(x, z) = exp(-\frac{||x-z||^2}{2\sigma^2})
    高斯径向基函数分类器，分类决策函数为：
    f(x) = sign(\sum_{i=1}^N a_i^*y_iexp(-\frac{||x_i-x_j||^2}{2\sigma^2})+b^*)

上一篇下一篇

猜你喜欢

热点阅读