从零开始学人工智能(29)--Python · SVM(三)· 核方法

浏览: 779

作者:射命丸咲    Python 与 机器学习 爱好者

知乎专栏:https://zhuanlan.zhihu.com/carefree0910-pyml 

个人网站:http://www.carefree0910.com 

往期阅读:

机器学习综述

从零开始学人工智能(21)--数学 · CNN · 从 NN 到 CNN 

从零开始学人工智能(22)--Python · 朴素贝叶斯(一)· 框架

从零开始学人工智能(23)--Python · 朴素贝叶斯(二)· MultinomialNB

从零开始学人工智能(24)--Python · 朴素贝叶斯(三)·  GaussianNB

从零开始学人工智能(25)--Python · 朴素贝叶斯(四)· MergedNB

从零开始学人工智能(26)--Tensorflow · LinearSVM

从零开始学人工智能(27)--Python · SVM(一)· 感知机

从零开始学人工智能(28)--Python · SVM(二)· LinearSVM


GitHub 地址:https://github.com/carefree0910/MachineLearning/blob/master/Notebooks/SVM/zh-cn/Kernel%20Methods.ipynb

=============正文如下===========


关于核方法的比较严谨的叙述,个人建议观众老爷们可以看看这个问题(https://www.zhihu.com/question/24627666下面的前几个回答;在这里的话,我们就还是只注重直观和应用层面

什么是核方法?

往简单里说,核方法是将一个低维的线性不可分的数据映射到一个高维的空间、并期望映射后的数据在高维空间里是线性可分的。我们以异或数据集为例:在二维空间中、异或数据集是线性不可分的;但是通过将其映射到三维空间、我们可以非常简单地让其在三维空间中变得线性可分。比如定义映射:

image.png

该映射的效果如下图所示:

image.png

可以看到,虽然左图的数据集线性不可分、但显然右图的数据集是线性可分的,这就是核工作原理的一个不太严谨但仍然合理的解释

从直观上来说,确实容易想象、同一份数据在越高维的空间中越有可能线性可分,但从理论上是否确实如此呢?1965 年提出的 Cover 定理从理论上解决了这个问题,我们会在文末附上相应的公式,这里暂时按下不表

至此,似乎问题就转化为了如何寻找合适的映射image.png、使得数据集在被它映射到高维空间后变得线性可分。不过可以想象的是,现实任务中的数据集要比上文我们拿来举例的异或数据集要复杂得多、直接构造一个恰当的image.png的难度甚至可能高于解决问题本身。而核方法的巧妙之处就在于,它能将构造映射这个过程再次进行转化、从而使得问题变得简易:它通过核函数来避免显式定义映射。往简单里说,核方法会通过用能够表示成image.png的核函数image.png替换各算式中出现的内积image.png来完成将数据从低维映射到高维的过程。换句话说、核方法的思想如下:

  • 将算法表述成样本点内积的组合(这经常能通过算法的对偶形式实现)

  • 设法找到核函数image.png,它能返回样本点x(i)、x(j)image.png作用后的内积

  • image.png替换image.png、完成低维到高维的映射(同时也完成了从线性算法到非线性算法的转换)

当然了,不难想象的是,并不是所有的函数K都能够对应一个映射(亦即不是所有的image.png都能拆成image.png;比如说,显然image.png至少需要是一个对称函数)。幸运的是,1909 年提出的 Mercer 定理解决了这个问题,它的具体叙述会在文末给出

Mercer 定理为寻找核函数带来了极大的便利。可以证明如下两族函数都是核函数:

image.png

那么核方法的应用场景有哪些呢?在 2002 年由 Scholkopf 和 Smola 证明的表示定理告诉我们它的应用场景非常广泛。定理的具体内容同样会附在文末,这里就暂时按下不表

核模型的表现

还是用 GIF 来说明问题最为形象。当我们对感知机应用核方法后,它就能对非线性数据集(比如螺旋线数据集)进行分类了,训练过程将如下:

怎么应用核方法?

简单来说,就是把算法中涉及到样本的地方都通过某种变换、弄成样本的内积形式()。以感知机为例,感知机的原始损失函数为image.png

为了让损失函数中的样本都变成内积形式,考虑令

image.png

image.png


如何训练核模型?

【注意:为简洁,从此往后的推导和实现均以核感知机为例,核 SVM 的相关讨论会放在下一章介绍 SMO 算法时进行】

简洁起见,我们还是用梯度下降法来进行训练,为此我们需要进行求导工作。假设当前模型参数为image.pngxi在参数下的预测值为,则:

image.png

为了加速训练,我们需要将该算式向量化,为此我们需要定义核矩阵。假设现在我们有两组样本:image.pngimage.png,那么它们的核矩阵即为image.png

对于训练过程而言,我们关心的是训练样本之间的核矩阵image.png

利用它,不难写出相应的向量化代码:

# 假设 k_mat 存储着原样本之间的核矩阵# 1、计算损失err = -y * (k_mat.dot(alpha) + b)# 2、找出使得损失不小于 0 的样本mask = err >= 0# 3、进行相应梯度下降,lr 是学习速率delta = lr * y[mask]alpha += np.sum(delta[..., None] * k_mat[mask], axis=0)b += np.sum(delta)

对于预测过程,我们关心的是原样本和新样本之间的核矩阵。假设新样本为image.png,则image.png

那么预测过程即为image.png

于是关键就在于如何定义计算核矩阵的核函数了。对于多项式核来说,核函数的实现是直观的:

@staticmethoddef _poly(x, y, p):
   return (x.dot(y.T) + 1) ** p

但对于 RBF 来说就没那么直观了,用到了 Numpy 的高级实用技巧之一——升维:

@staticmethoddef _rbf(x, y, gamma):
   return np.exp(-gamma * np.sum((x[..., None, :] - y) ** 2, axis=2))

当然直接用 for 来实现也是可以的,不过那将会非常非常慢……

核模型的实现

如果思路能够整理清楚,那么核模型相比原模型来说只有如下两点改变:

需要定义核函数并计算出核矩阵

计算预测值时不是image.png,而是image.png,其中

在训练时,K为原样本之间的核矩阵

在测试时,K为原样本和新样本的核矩阵

所以实现起来的话会有许多重复代码,这里就只展现其中最核心的部分(仍以核感知机为例):

# 训练代码def fit(...):
   ...
   self._alpha = np.zeros(len(x))
   self._b = 0.
   self._x = x
   # self._kernel 即为核函数,能够计算两组样本的核矩阵
   k_mat = self._kernel(x, x)
   for _ in range(epoch):
       err = -y * (self._alpha.dot(k_mat) + self._b)
       if np.max(err) < 0:
           continue
       mask = err >= 0
       delta = lr * y[mask]
       self._alpha += np.sum(delta[..., None] * k_mat[mask], axis=0)
       self._b += np.sum(delta)# 预测代码def predict(self, x, raw=False):
   x = np.atleast_2d(x).astype(np.float32)
   # 计算原样本与新样本的核矩阵并根据它来计算预测值
   k_mat = self._kernel(self._x, x)
   y_pred = self._alpha.dot(k_mat) + self._b
   if raw:
       return y_pred
   return np.sign(y_pred).astype(np.float32)

相关数学理论

1)Cover 定理


2)Mercer 定理

image.png

【注意:通常我们会称满足这两个充要条件之一的函数为 Mercer 核函数而把核函数定义得更宽泛。不过如果不打算在理论上深入太多的话,将 Mercer 核函数简称为核函数是可以的。此外,虽说 Mercer 核函数确实具有 Hilbert 空间中的内积形式、但此时的 Hilbert 空间并不一定具有“维度”这么好的概念(或说、可以认为此时 Hilbert 空间的维度为无穷大;比如说 RBF 核,它映射后的空间就是无穷维的)】

3)表示定理

下一篇文章我们则会抛开梯度下降这个有些“偷懒”的做法,并介绍一种叫序列最小最优化(SMO)的算法

希望观众老爷们能够喜欢~


公众号后台回复关键词学习

回复 人工智能          揭开人工智能的神秘面纱

回复 贝叶斯算法      贝叶斯算法与新闻分类

回复 机器学习          R&Python机器学习

回复 阿里数据          阿里数据系列课程

回复 Python            Python机器学习案例实战

回复 Spark              征服Spark第一季

回复 kaggle             机器学习kaggle案例

回复 大数据             大数据系列视频

回复 数据分析         数据分析人员的转型

回复 数据挖掘         数据挖掘与人工智能

回复 机器学习         R&Python机器学习

回复 阿里数据         阿里数据系列课程

回复 R                     R&Python机器学习入门

推荐 0
本文由 人工智能爱好者社区 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册