机器学习-白板推导 7 核方法

1. 线性不可分问题

对于如下图中的异或问题,是线性不可分的。

image-20210531213728143

但是将数据映射到高维空间后就可以实现线性可分。如果将异或问题中的数据通过一个映射将低维空间中的数据映射成高维空间中的来实现数据的线性可分。如:

就可以得到如下数据分布:

image-20210601090713029

这时就可以轻松将两类点分开。

2. 核函数的引入

机器学习-白板推导6 SVM 小节3中对偶问题的拉格朗日乘子法目标函数为:

其中,含有项,如果我们定义一个映射,将低维的特征映射到高维特征空间中,将会使得数据线性可分。但是这个映射过程如果维度过高,计算量将非常大。为此引入核函数,kernel function的作用之一就是省去计算,直接得到

核函数定义: (《统计机器学习 》P144定义)

是输入空间(),又设是希尔伯特空间,如果存在:

使得对所有的,函数满足条件:

其中就是内积,希尔伯特空间在下一节介绍。

例子:

$k(x,x’)=\exp(-\frac{(x-x’)^2}{2\sigma^2})$ 是一个核函数。

证明:

实际上,我们一般使用的都是正定核函数。那么什么是正定核函数呢?

3. 正定核函数的两个定义

定义一

定义二

对称性,正定性解释

  1. 对称性:
  2. 正定性: 任取N个元素, ,其对应的Gram Matrix (也叫Kernel Matrix) ,就是对应元素的kernel矩阵是半正定的

先介绍Hilbert Space: 希尔伯特空间是一个完备的,可能是无限维的,被赋予内积运算的线性空间。

  1. 线性空间:空间中任意两个向量都可以由基向量线性表示

  2. 完备的:对极限操作的封闭性。希尔伯特空间是一个函数空间,空间中每个元素都是函数,因此:

  3. 内积 内积要满足3个条件:正定性, 对称性, 线性

  • 对称性:, 就有,这里都是函数。
  • 正定性:, 只有当 时取等号。
  • 线性:

如果使用定义一,很难找到,我们一般用定义二来判断是否为正定核函数。

4. 正定核函数充要条件

问题是:

  1. 对称性

又因为:

所以

  1. 正定性:令所有K是半正定的。

5. 非线性支持向量机

式1引入核函数就能应用到非线性分类中:

现在SVM算法选择合适的核函数就可以对非线性可分数据集分类了。

Inference

[1] 支持向量机原理(三)线性不可分支持向量机与核函数