线性分类器 VS 非线性分类器

在这一小节,我展示了Naive Bayes和Rocchio这两个学习方法,它们都属于线性分类器,大概也是文本分类器中最重要的一组,接着我把它们和非线性分类器做了一个比较。为了简化讨论部分,我在这一节将只考虑二类分类器,并将不同特征的线性组合和阈值做比较从而定义一个线性分类器为一个二类分类器。

图 14.8:有无数个可划分这两个线性可分类的超平面

在二维空间里面,一个线性分类器是一条线。图14.8展示了五个分类例子。这些线有一个函数形式w1x1­+w2­x2=b。线性分类器的分类规则是:如果w1x1­+w2­x2>b,就把一个文档归类为,如果w1x1­+w2­x2<=b,就把它归类为。在这里,(x1,x2)T是文档的二维向量表示,(w1,w2)是参数向量,和b一起决定决策边界。此外,在图 15.7中给出了线性分类器的另一种几何解释。

正如我们之前在公式 140中处理的那样,我们可以通过定义一个超平面将一个二维线性分类器映射到更高维空间,这里我重复一下之前的公式,即公式 144:

然后,分类标准更改为:如果,就归类为,如果,就归类为。我们把使用的超平面作为一个线性分类器的决策超平面。

图14.9 线性分类算法

图 14.9展示的是在M维空间中对应的线性分类算法。首先,从给出的这个简化算法表述来看,线性分类似乎是很简单的。然而,困难的是线性分类器的训练,也就是基于数据集来确定参数和b。我们用于评估学习算法性能的标准是通过比较经过学习得到的线性分类器在新数据上的表现效果来确定的,通常会有一些学习算法最后会计算出优于其它算法的参数。

现在,我们来证实下Rocchio和Naive Bayes这两个线性分类器。让我们先来看看Rocchio,可以看出如果一个向量到两个类质心的距离相等,那么它就位于决策边界上。

我们可以从它的决策规则中推导出Naïve bayes的线性,它选择有最大的作为类别(如图 13.2 , 页码 13.2 ),其中:

表示的是词表中包含的词在文档中出现的个数。对立类别用表示,我们可以得到log概率:

如果概率大于1,或是log概率大于0,我们就归类为。很容易看出,公式 147 是公式 144 的一个实例,其中,xi=d中ti的出现次数,。这里,下标i, 指的是词表中的词(并不是和k一样,指词在文档d中的位置;参见variantmultinomial),x和w是M维向量。因此,在log空间中,朴素贝叶斯是一个线性分类器。

一个线性分类器。在Reuters-21578中用于分类interest(如interest rate)的线性分类器的维数

和参数

,阈值

。像dlr和world这样的术语有负权重,因为它们是用于另一个类别“货币”的标志。

工作例子。表14.4定义了一个用于在Reuters-21578(见 13.6节,页 13.6)中分类interest的线性分类器。我们把文档`

`rate discount dlrs world''分为interest,因为

。我们把`

`prime dlrs''分为对立类(不在interest中),因为

。为了简化,我们在这个例子中假设一个简单的二类向量可以表示为如下形式:1表示出现的术语,0表示没有出现的术语。工作例子到此为止。

一个有噪声数据的线性问题。在这个假设的web页面分类场景中,全是中文的网页用实心圆标记,中英混合的网页用正方形表示。这两类被一个线性分类边界(虚线、短虚线)区分开,除了三个噪声文档(使用箭头标记)

图 14.10是线性问题的图例,我们的定义表明两个类的潜在分布

中有一条分隔线。我们把这条分割线称作类边界。这是两类的“true”边界并且我们把它从决策边界(学习方法计算类边界的近似值)中识别出来。

在典型的文本分类中,如图 14.10 (使用箭头标记的部分)有一些噪声文档,没有很好的拟合类别的整体分布。在 13.5 小节(页码 13.5 ),我们把噪声特征定义为误导特征,当文档中包含有噪声特征时,分类误差会均匀地增加。类似的,当训练集中包含噪声文档时,那么它将会误导学习方法并且增加分类错误率。直觉上,将代表空间划分为不同的区域,区域内的大部分样本类别都相同。一个文档如果不属于它所在区域的主要类别,那么它就是噪声文档。

噪声文档是使训练线性分类器变得困难的一个原因。在选择分类器决策超平面时,如果我们过于关注噪声文档,那么分类器在新的数据上就会表现得的不精确。最根本的是,通常很难决定哪一个文档属于噪声文档并因此潜在的误导我们。

如果存在一个超平面能够完美的的划分两个类别,那么我们称这两个类别为线性可分。事实上,如果具有线性可分性,那么会有无数条线性分割线(练习 14.4 ),如图 14.8 所示,可分割超平面是无限的。

图 14.8表明了在训练线性分类器中的另一挑战。如果我们处理的是一个线性可分问题,那么我们需要一条标准从所有的决策超平面中来进行选择,让其能够完美的划分训练数据。通常这些超平面,有些可以在新数据上表现的很好,而另一些则表现的不尽人意。

图14.11 非线性问题

非线性分类器的一个典型例子就是kNN。从图 14.6这个例子可以看出,kNN的非线性是直观清晰的。kNN的决策边界(如14.6的 两条线 )是局部线性划分,但通常有一个复杂的形状,并不等同于二维空间中的一条线或是更高维空间中的一条超平面。

图 14.11是另一个非线性问题的例子:在

分布和

分布中没有一条很好的线性分割线,因为在图的左上角还有一个环形包围的“区域”。

线性分类器会误分圆形内部的部分,所以在处理这种类型的问题时,如果训练集足够大的话,像kNN这样的非线性分类器反而会表现得更加精确。

如果一个问题是非线性问题并且它的类边界不能够用线性超平面估计得很好,那么非线性分类器通常会比线性分类器表现得更精准。如果一个问题是线性的,那么最好使用简单的线性分类器来处理。

练习:

证明二分类中线性分割线的个数要么是无穷个,要么是零。

原文链接: Linear versus nonlinear classifiers(译者/刘帝伟 审校/赵屹华、朱正贵、李子健 责编/仲浩)

译者简介: 刘帝伟,中南大学软件学院在读研究生,关注机器学习、数据挖掘及生物信息领域。

本文分享自微信公众号 - CSDN技术头条(CSDN_Tech)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2015-09-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

李理:详解卷积神经网络

24770
来自专栏计算机视觉life

SLIC 超像素分割详解(三):应用

看过上面的介绍后,我们应该思考一下:分割好的超像素有什么用?怎么用?用到哪里? 首先,超像素可以用来做跟踪,可以参考卢湖川课题组发表在IEEE TIP上的《Ro...

509100
来自专栏人工智能

机器学习之——梯度下降算法

机器学习算法大都遵从同样的套路:设定需要学习的参数,通过最优化算法来最小(大)化学习目标,从而得到一组最好的待学习参数。例如,线性回归z=ax+by中,参数就是...

283100
来自专栏机器之心

教程 | 单级式目标检测方法概述:YOLO与SSD

在这篇文章中,我将概述用于基于卷积神经网络(CNN)的目标检测的深度学习技术。目标检测是很有价值的,可用于理解图像内容、描述图像中的事物以及确定目标在图像中的位...

13910
来自专栏生信小驿站

使用R语言进行机器学习特征选择②

特征工程其实是一个偏工程的术语,在数据库领域可能叫做属性选择,而在统计学领域叫变量选择,其实是一个意思:即最大限度地从原始数据中提取有用信息以供算法和模型使用,...

25520
来自专栏大数据文摘

论文Express | 谷歌大脑:基于元学习的无监督学习更新规则

21030
来自专栏本立2道生

特征,特征不变性,尺度空间与图像金字塔

在计算机视觉领域,特征是为了完成某一特定任务需要的相关信息。比如,人脸检测中,我们需要在图像中提取特征来判断哪些区域是人脸、哪些区域不是人脸,人脸验证中,我们需...

22720
来自专栏算法channel

3 张PPT理解如何训练 RNN

损失函数选用交叉熵,机器学习的很多算法模型也都会选用交叉熵。显然,损失函数大小不想受训练语料库的单词数影响,因此计算所有训练单词的交叉熵再求平均即可。

13310
来自专栏机器学习算法与理论

浅谈神经网络

一、神经网络介绍 神经网络是由具有适应性的简单单元组成的广泛并行互联的网络,它的组织能够模拟生物神经系统对真实世界物体作出的交互反应。 神经网络中最基本的成分...

39090
来自专栏机器人网

机器学习十大算法:新手看了变老手

在机器学习中,有一种叫做「没有免费的午餐」的定理。简而言之,它指出没有任何一种算法对所有问题都有效,在监督学习(即预测建模)中尤其如此。

15940

扫码关注云+社区

领取腾讯云代金券