人工智能 关于核方法和支持向量机

suini87 · December 08, 2019 · 36 hits

阅读了王东老师《现代机器学习技术导论》第五章关于核函数和支持向量机的介绍后,我总算是系统地学习了核函数相关的知识,知道这是个什么玩意,不会再谈 “核” 色变了。此外,在打牢了逻辑回归的知识基础后,学习支持向量机也非常轻松。然而在阅读第五章核函数相关的过程中,我也遇到了很多困难,很多数学方面的概念对我来说非常抽象,于是我也求助了博客、知乎,还结合书本内容看了很多遍吴恩达关于核函数的讲解,在这篇读书笔记中,我把自己的理解过程记录了下来。

Summary about Kernel Method

线性分类模型的局限性在于,如果数据线性不可分,模型将不再适用,因而需要对数据做非线性映射,在更高的维度中将数据区分开来,使其线性可分。神经网络可以用来学习映射,即特征提取,但是在有些情况下不适用;核函数则是另一种生成映射函数的方法,通过隐式定义数据间的相关性函数来映射。

核函数描述了训练数据间的关系,使得预测时依赖训练数据而非参数模型。接下来引入了核函数的合法条件 Mercer 定理,即函数对称且半正定。然后,介绍了一些简单核函数,如线性核(应用于 Kernel PCA 方法),多项式核(等价于对原始数据进行特征扩展,不仅考虑原始特征还考虑特征之间相关性,多应用于 NLP),高斯核(对应无限维特征空间,是距离的函数,形式与 RBF 一致,故又叫 RBF 核),概率核等,还可以进行核函数组合。

讨论了一些简单核函数后,又介绍了复杂核函数。然后讨论了四类具体的核方法:Kernel PCA,Gaussian Process,SVM,RVM。

KPCA:不符合高斯分布的数据很难用 PCA 找到一个合适的主成分方向,所以用线性核将数据映射到特征空间,再进行 PCA。

高斯过程:由于不存在显式的模型参数,所以在贝叶斯方法做未知数据概率预测时不能通过参数引入先验概率;但高斯过程引入了数据间距离,通过该距离定义了一个联合概率分布,从而引入了预测模型的随机性,因此可以给出预测过程的可信度。

支持向量机:分类问题中,希望得到的线性分类面具有最大边界属性,而边界样本集中的训练样本就叫支持向量,而这个分类器就叫 SVM。值得注意的是,SVM 中只有支持向量才会对分类预测起作用,其余数据都可以丢弃,这样的稀疏模型大大减小了计算量。为什么 SVM 能做到最大边界呢?具体又是怎么用核函数进行计算更新的呢?多分类怎么办?后面笔记有更详细的内容。

相关向量机:SVM 基于距离,而缺少概率意义。用相关向量代替支持向量,就是 RVM 的思想。

对比神经模型和核方法这两种生成映射函数的方法,神经模型是典型的数据驱动模型,包含大量参数,需要足够的数据量以确定这些参数;核方法中可以调节的参数比较少,不需要太多数据,但需要较强的先验知识来设计核函数的形式。

SVM = Hinge Loss + Kernel Method

SVM,support vector machine。即 Hinge Loss + Kernel Method。
先考虑什么是 hinge loss:
在二分类问题当中,紫色的那条 loss 函数就是 hinge loss。

  
Loss functions in classification
  

Hinge loss 和 cross entropy+sigmoid 的方法相比,最大的差别在于已经 good enough 的部分。交叉熵会让好的还要更好,而 hinge 是及格就好。而 linear SVM 和 logistic regression 的最大区别就在于 loss 函数的选用。如果选用交叉熵,就是 logistic regression。对于 linear SVM,多个输入的 hinge loss 以及约束相加得到的是一个凸函数(convex)。Linear svm 也可以用 gradient descent 来训练,也可以用二次规划来求解。

  
Duel representation
  

看到这里看不下去了….SVM 到底是什么呢?又是怎么实现的呢?感觉自己对 SVM 的理解是碎片化的,跟着做了一些复杂的数学推导,也看了一些形象的讲解,但是不明白为什么要这样推导。

于是在知乎上找了关于 SVM 的思维导图,左边是求解基本的 SVM 问题,右边是相关扩展:

  
SVM summary
  

然后转而去看吴恩达的课,反复看了三遍,最后一遍的时候才看懂,感觉知识突然串成一片了:

在 SVM 中,损失函数用 hinge loss 来代替逻辑回归的交叉熵;另外有一点需要注意,SVM 不是给出分类的概率,而是当ΘTx 大于等于 0 时,预测 y=1;当ΘTx 小于 0 时,预测 y=0。

  
Hinge loss
  

那么反过来,如果 y^=1,我们会希望 SVM 的ΘTx 大于等于 1(hinge loss 要求不止及格,要做到更好)。如果训练中给损失函数的权重很大(正则项权重较小)的话,最终前面的损失函数项会下降到 0,剩下来就变成了怎样使后面的正则项最小的问题。

  
SVM decision boundary
  

然后有数学推导可以推导出在这种情况(已经完成分类任务,即 loss 项为 0)下,SVM 会主动使倾斜的线满足 margin 最大的要求。当然,如果损失函数与正则项的权重做调整,可以避免过拟合。

接下来需要理解 kernels 核函数。如何找到一个合适的 decision boundary 呢?之前我们一致通过构造ΘTx(多项式特征变量)来找决策边界。参数ΘT 的值是通过训练得到的,不需要我们操心,我们要做的就是多写几个 x。这里的每一项 x,可以是 x1,也可以是 (x2)^2,也可以是 x1x2。现在我们不直接使用多项式来作为特征变量,这样计算量太大了,我们转而用核函数方法来计算新的 features,用 f 来表示每一项 x,这里的 f 就是相似度函数(特殊的,在我们的例子中用到的是高斯核函数),我们可以直观地计算出他们的值,继而直接给出分类结果,画出决策边界。

以高斯核函数为例子,Gaussian Kernel:

  
Kernels and similarity
  

为什么叫相似度函数呢?看下面这张图可以看出来,x 离 l 越近,f 值越接近 1;x 离 l 越远,f 值越接近 0.另外分母项可以约束值下降的速度。

  
Gaussian kernel
  

然后我们弄懂了高斯核函数是什么,接下来需要弄明白高斯核函数代入损失函数之后,是怎么完成分类任务的。我们假设一个例子如下图,已经训练更新后得到了一组参数ΘT,再根据各个 x 的位置算出 f 的值。这样画出来的 decision boundary 就会是这样一个圈圈。可以看出来效果相当不错。

  
Prediction task example
  

那么我们是怎么选取 landmarks 的呢?将 landmarks 选取在每一个训练样本点的位置即可,这样对 m 个训练样本我们就可以取 m 个标记点作为 landmarks。这样一来,我们就用新的特征向量 f(i) 替换了原来的 x(i)。

  
How to choose landmarks
  

完成了替换之后,我们就得到了新的 loss 函数,然后训练使其最小即可。另外关于最后一项正则向,有一种新的写法就是把平方换成ΘTΘ,根据核函数选取的不同还可能在中间乘一个矩阵 M 变成ΘTMΘ,可以解决样本数量过大时计算效率不足的问题。

还有一个问题是,为什么不把核函数和标记点的方法应用到逻辑回归上呢?其实是可以的,但是支持向量机的一些计算技巧并不能很好地移植到逻辑回归等其他算法上,计算效率也会降低。种种原因使得 SVM 和核函数最为适配。

  
Training
  

在基本搞明白 SVM 和核函数之后,会面临一些更具体的问题,比如如何权衡参数 C 呢?C 选取较大意味着忽略正则,也就是低 bias 和高 variance;而 C 选取较小意味着强调正则,即高 bias 和低 variance。其他的参数的影响可以在下面看到。

  
Effection of parameters
  

具体在使用 SVM 时,一般用 SVM software package 如 liblinear,libsvm 等等来求解参数Θ。需要明确参数 C 以及核函数(相似度函数)的选择。如果用 linear kernel,其实就是 no kernel,当ΘTx 大于等于 0 时预测 y=1,这种情况适用于数据量很少,但是数据维度可能很大的情况,此时用线性核函数可以防止过拟合,当然这种情况也可以用逻辑回归;如果选用高斯核函数(Gaussian kernel),还需要选择分母项 sigma^2,对于数据量比较大但是维度比较小(比如二维),会想要找一个非线性决策边界去分开数据,就可以用高斯核函数。目前高斯核函数和线性核函数是最为常用的两个。如果维度比较小,数据量巨多(比如 50000+),高斯核 SVM 可能会有点慢,此时考虑多找一些特征,扩大维度然后再用线性核函数或者逻辑回归来分类。

此外,注意数据要做 normalization 归一化,不然的话计算相似度时 x-l 的长度平方就容易被某一维度的距离平方所左右。还有就是不是所有的相似度函数都可以做核函数,需要满足默塞尔定理 Mercer’s Theorem,这样 SVM 才能做有效的 optimization 而不会不收敛。其他满足的函数还包括多项式核函数 polynomial kernel、string kernel、chi-square kernel 等。

Multi-class classification 的情况下,采取 one vs the rest 的方式,可以训练 k 个 SVM,各自将一类与其他类分开来,再 pick class i with largest Θ(i) Tx。

No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.