线性分类器 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(译者/刘帝伟 审校/赵屹华、朱正贵、李子健 责编/仲浩)

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


原文发布于微信公众号 - 人工智能头条(AI_Thinker)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老秦求学

[Deep-Learning-with-Python]机器学习基础

二分类、多分类以及回归问题都属于监督学习--目标是学习训练输入和对应标签之间的关系。 监督学习只是机器学习的冰山一角。机器学习主要分为4类:监督学习、非监督学...

1043
来自专栏CDA数据分析师

机器学习新手必看十大算法

编译 机器之心 原文链接:https://towardsdatascience.com/a-tour-of-the-top-10-algorithms-for...

4456
来自专栏新智元

【计算机视觉必读干货】图像分类、定位、检测,语义分割和实例分割方法梳理

作者:张皓 【新智元导读】本文作者来自南京大学计算机系机器学习与数据挖掘所(LAMDA),本文直观系统地梳理了深度学习在计算机视觉领域四大基本任务中的应用,包括...

6296
来自专栏红色石头的机器学习之路

机器学习中的维度灾难

一、介绍 本篇文章,我们将讨论所谓的“维度灾难”,并解释在设计一个分类器时它为何如此重要。在下面几节中我将对这个概念进行直观的解释,并通过一个由于维度灾难导致的...

6110
来自专栏大数据文摘

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

1903
来自专栏AI研习社

一文详解分类问题中的维度灾难及解决办法

一、介绍 本篇文章,我们将讨论所谓的“维度灾难”,并解释在设计一个分类器时它为何如此重要。在下面几节中我将对这个概念进行直观的解释,并通过一个由于维度灾难导...

3574
来自专栏计算机视觉life

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

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

44110
来自专栏CSDN技术头条

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

在这一小节,我展示了Naive Bayes和Rocchio这两个学习方法,它们都属于线性分类器,大概也是文本分类器中最重要的一组,接着我把它们和非线性分类器做了...

3705
来自专栏人工智能

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

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

26310
来自专栏机器学习算法工程师

机器学习中的数据不平衡解决方案大全

在机器学习任务中,我们经常会遇到这种困扰:数据不平衡问题。 数据不平衡问题主要存在于有监督机器学习任务中。当遇到不平衡数据时,以总体分类准确率为学...

2584

扫码关注云+社区

领取腾讯云代金券