第5章
CHAPTER 5


基本分类学习






本章讨论分类问题,介绍几种基本分类算法。为了概念的清楚,本章将只有两种类型的二分类问题和有多于两种类型的多类问题分开讨论。分类问题的表示方法比回归问题更丰富,本章将通过几个比较简单的方法理解分类中遇到的多种表示方式和目标函数,这些内容在后续章节中得以继续应用和扩展。例如,本章介绍的逻辑回归所使用的目标函数和优化算法,加以推广则可用于神经网络的学习。


ML08分
类学习1


5.1基本分类问题
设有满足独立同分布条件(I.I.D)的训练数据集为

D=(x1,y1),(x2,y2),…,(xN,yN)={(xn,yn)}Nn=1(5.1.1)

对于分类问题,训练集的标注y仅取有限的离散值,即y表示其所代表的类型编号。可将标注值表示为y∈{1,2,…,C},其中C表示一个学习任务中待分类类型的数目。当C=2时表示二分类任务,这是一种基本的分类任务。由于二分类可以清楚地说明分类的学习方法且表示简单、概念清晰,故本章重点讨论二分类问题。当C>2时称为多分类任务,可在二分类的概念和方法基础上进一步扩展至多分类。
首先讨论在分类中如何表示类型,包括标注和分类器的输出,以标注为例进行讨论。在二分类中,由于标注y仅取两个值,常用二值单变量表示类型,即y∈0,1或y∈1,-1,本章多采用前者。用y=1表示类型1,也可用符号C1表示类型1; y=0表示类型2,也可用符号C2表示类型2。即y=1与C1代表相同含义,类似地,y=0与C2相同含义。
在表示多分类任务中,标注y可以选择两种不同的表示方式,一种是y直接取一个标量值,即y取集合1,2,…,C中的值。机器学习中较多采用另一种C维向量编码方式表示y,即用以下形式的向量表示多类标注。

y=0,…,0,1,0,…,0T(5.1.2)

y中各分量yi只取0或1,且∑iyi=1,即只有一个分量yk=1表示y标注的是第k类,其他yi=0,i≠k。后面将会看到,这种编码向量表示多类型有其方便性。
与回归问题一样,利用训练数据集训练一个分类模型,模型的一般表示为

y^=f(x)(5.1.3)

其中,x表示一个新的特征输入; y^表示分类输出。式(5.1.3)是分类模型的一般性表示,在实际中,分类输出分为确定性输出和概率输出两大类,然后再区分两种不同的概率表示方式,可以把式(5.1.3)表示的分类模型分成3种情况,下面分别介绍。

1. 判别函数模型
与第4章介绍的基本回归模型类似,分类输出可表示为确定性的函数,如线性模型

y^(x)=wTx+w0(5.1.4)

通过训练确定参数w和w0,对于新的x计算y^(x)并与门限比较确定分为哪一类。也可以通过一个非线性函数(称为激活函数)得到以下广义线性模型。

y^(x)=fwTx+w0(5.1.5)

其中,f(·)为激活函数,在二分类问题中,最简单的是f(·)的输出只取0,1或1,-1,如取f(·)为符号函数sgn(·)。模型的输出可以直接分类。
有几种分类器属于判别函数的分类模型,如经典的感知机、Fisher判别函数和支持向量机(SVM)。




2. 判别概率模型
判别概率模型是常用的一种分类模型,也简称判别模型。式(5.1.3)不再是一个确定函数,而是一个后验概率。在二分类问题中,式(5.1.3)的函数f(x)实际是通过特征输入x计算分类为第1类的后验概率,即

y^=f(x)=pC1|x(5.1.6)

则输入x分类为第2类的后验概率为1-y^=1-pC1|x,然后由第3章介绍的决策原理得到最终分类输出。
若推广到多类情况,则式(5.1.3)的y^是一个向量,其分量表示分类为Ck的后验概率,即

y^k=pCk|x(5.1.7)

同样可根据决策原理得到分类输出。
应用后验概率进行分类具有灵活性,如第3章讨论的,若对每类分类错误的代价是相同的,则直接将输入特征向量分类为后验概率最大的一个,即分类为

Ck=argmaxCip(Ci|x)(5.1.8)

但当不同分类的分类错误代价不同时,如第3章所讨论的,可以通过对后验概率的加权得到分类决策,只要得到了后验概率,调整加权不需要重新计算后验概率。因此,求得后验概率后,可根据不同任务设置加权矩阵,获得不同要求下的分类输出。后验概率还有许多其他可用来扩展问题的特性,此处不再赘述。
3. 生成概率模型
一个构成更完整的概率描述的方法是生成概率模型,简称生成模型。通过训练样本集学习得到特征向量x和类型输出y的联合概率p(x,y)。一般情况下得到联合概率比得到后验概率更困难,因此,生成模型一直是机器学习中更有挑战性的工作。
从分类任务来讲,表示类型的y的取值是有限的,若按式(5.1.2)的编码模式表示y,则y只有C种取值,即yk=1,yi≠k=0,k=1,2,…,C,故联合概率可以表示成由C个固定y取值的概率集合,即p(x,yk=1),k=1,2,…,C。为了突出类型,可用p(x,Ck)代表p(x,yk=1),即用Ck代表yk=1,yi≠k=0的情况。在许多实际问题中,可能更容易得到类型作为条件下的特征向量x的概率函数pxyk=1=pxCk和类型的先验概率p(yk=1)=p(Ck),这里的pxCk称为类条件概率。由如式(5.1.9)所示的作为分类问题的生成模型。由概率公式

p(x,Ck)=pxCkp(Ck)(5.1.9)

对于所有k,可得到p(x,Ck)或pxCk与p(Ck),它们是等同的。由贝叶斯公式,有了生成模型,则后验概率为

pCk|x=p(x,Ck)p(x)=pxCkp(Ck)p(x)=pxCkp(Ck)∑kpxCkp(Ck)(5.1.10)

得到生成模型后,可直接得到类后验概率,利用决策原理进行分类。生成模型有更多的信息可用,按照样本是由对联合概率p(x,y)采样获得的假设,既然已得到了较准确的联合概率,则可以通过一些采样技术获得新的增广样本,改善学习质量。
注意到,对于判别概率模型和生成概率模型,由于最终做分类决策的都是用类后验概率,容易混淆其区别。对于判别概率模型,通过样本直接训练得到类后验概率表达式,并通过后验概率进行分类决策; 对于生成概率模型,直接学习得到的是联合概率,然后利用联合概率获得类后验概率进行分类决策,但是联合概率可以获得其他应用。判别概率模型学习过程中没有联合概率的出现,生成概率模型重要的是获得联合概率(或其等价物),用联合概率计算类后验概率用于分类只是其部分功能。
5.3节将介绍的逻辑回归是一种基本的判别概率模型分类算法,尽管原理简单,但其概念很容易扩展到神经网络的分类。目前神经网络包括深度神经网络的分类任务多数属于判别概率模型。4.4节介绍了一种简单的生成模型分类器——朴素贝叶斯算法。第11章将介绍深度学习中的一类生成模型——对抗生成网络(Generative Adversarial Networks,GAN)(GAN是一种无监督学习)。
5.2线性判别函数模型
对于二分类问题,线性判别函数是指学习一个形式(5.1.4)的模型,为方便,将线性判别函数重写为

y^(x)=wTx+w0(5.2.1)


对于一个给定的新输入x,若y^(x)>0,判别为第1类C1; 若y^(x)<0,判别为第2类C2。式(5.2.1)中的w0为偏置参数。-w0可看作阈值,wTx>-w0时可判别为C1。y^(x)=0时可随机选择判别为C1或C2,或不做判决。
设x为K维向量,则y^(x)=wTx+w0=0是K维空间的一个平面,将K维空间划分为两个子空间R1和R2,x落入R1时可判别为C1,x落入R2时判别为C2。超平面wTx+w0=0称为判决面。若有x1和x2均处于判决面上,则有

wTx1+w0=wTx2+w0

故

wTx1-x2=0


即w与判决面上的任意向量正交,w表示判决面的法线方向,由于x∈R1时y^(x)>0,故w指向的方向为R1。图5.2.1给出了三维空间判决面的示意图。


对于位于判决面之外的任意点x,它在判决面上的投影为xp,则x可表示为

x=xp±rw‖w‖(5.2.2)

其中,±分别表示x在R1和R2内; r>0表示x到判决面的距离。将式(5.2.2)表示的x代入式(5.2.1)得


y^(x)
=wTx+w0=wTxp±rw‖w‖+w0

=wTxp+w0±r‖w‖=±r‖w‖


即

r=±y^(x)‖w‖=y^(x)‖w‖(5.2.3)

式(5.2.3)表示空间任意点到判决面的距离。
对于给定的一组数据集,如果可以找到一个判决面将数据集的样本完全正确分类,则称数据集是线性可分的。设一个数据集的xn是二维的,如图5.2.2所示,则该数据集是线性可分的。对于二维问题,判决面退化成简单的直线,图5.2.2中画出了3条判决线,均可以将所有样本正确分类。


图5.2.1三维空间判决面的示意图




图5.2.2线性可分数据集的例子



对于二分类问题,可以通过最小二乘得到权系数w的解。分类问题LS解的过程与线性回归类似,不同之处在于样本集合D={(xn,yn)}Nn=1中的标注值yn只取两个不同值。通过y^(xn)与yn之间误差平方和最小得到w的解,解的方程见第4章。由于二分类问题的LS解存在性能上的诸多缺陷,实际中很少使用,因此本节也不再赘述。
实际中应用最多的一种判别函数方法是支持向量机(SVM),其详细分析需要较大篇幅,将在第6章专门讨论。本节后续将对历史上曾有重要影响的两类方法做概要叙述,分别是Fisher线性判别分析和感知机。
5.2.1Fisher线性判别分析
Fisher线性判别分析(Linear Discriminant Analysis,LDA)不是一种标准的线性判别函数模型,它实际上是一种通过降维对数据类型进行最大分离的方法,但当降维的结果结合阀值进行分类时,与分类的线性判别函数模型是一致的。
首先讨论二分类问题,然后推广到多类问题。
1. 二分类Fisher LDA
设有一组数据样本D={(xn,yn)}Nn=1,这里讨论二分类的情况,故yn=1表示类型C1,yn=0表示类型C2。将属于C1的子样本集记为D1,共有N1个样本; 属于C2的子样本集记为D2,共有N2个样本。目标是给出一个向量w,将每个样本投影到w上得到一维投影值y^,即

y^=wTx(5.2.4)

设x为K维向量,w代表K维空间的一条直线,若‖w‖=1,则y^为x在w上的投影值,实际上w的方向是重要的,其范数大小无关紧要。
对于数据集D,根据标注分成两个子集D1和D2,两个子集的每个样本对应K维空间的一个点,将其投影到w表示的直线,即投影直线上的一点。对于每个xn,得到相应的投影y^n,可得到数据集中所有样本在w直线表示的一维空间中的投影集合y^nNn=1,其中子集D1和D2的投影子集分别记为Y1=y^nxn∈D1和Y2=y^nxn∈D2。若希望从投影中将类型区分开,则希望Y1和Y2是可分的,Y1和Y2的可分性与w的方向是相关的。如图5.2.3所示,在二维空间中,有两种类型的样本,若投影到图5.2.3(a)所示的w直线,则Y1和Y2是不可分的; 若投影到图5.2.3(b)所示的w直线,则Y1和Y2是可分的。


图5.2.3样本投影到不同直线的可分离情况


通过这个直观的分析,可将问题叙述为: 求最优w使集合Y1和Y2具有最大的分离性。为此,用数学形式表示两个集合的分离度,原理上可用两个集合的均值差表示它们的分离程度。对于每个样本xn,其投影值为y^n=wTxn,故每类的投影均值为


m^i
=1Ni∑y^n∈Yiy^n=1Ni∑xn∈DiwTxn

=wT1Ni∑xn∈Dixn=wTmi,i=1,2(5.2.5)


注意,这里i=1,2分别表示C1,C2两类样本。式(5.2.5)用到了投影前样本的均值,即

mi=1Ni∑xn∈Dixn,i=1,2(5.2.6)

由此得到类投影均值之差为

m^1- m^2=wTm1-m2(5.2.7)

式(5.2.7)的均值差会随着w范数的增加而增加。定义类内散布(Scatter)量为

s^2i=∑y^n∈Yiy^n- m^i2,i=1,2(5.2.8)

用s^21+s^22表示投影样本的总类内散布,有了这个准备,可将式(5.2.7)的类投影均值之差的平方除以总类内散布定义为Fisher准则函数,即

J(w)=m^1- m^22s^21+s^22(5.2.9)

一个最优的w,既可使式(5.2.9)的分子尽可能大,即两类投影集尽可能分离,又可使分母尽可能小,即每类在类内聚集得好。因此,使式(5.2.9)最大的w是本问题的最优解。为了得到式(5.2.9)与w的显式关系,进一步有


s^21+ s^22
=∑y^n∈Y1y^n- m^12+∑y^n∈Y2y^n- m^22

=∑xn∈D1wTxn-wTm12+∑xn∈D2wTxn-wTm22

=wT∑xn∈D1xn-m1xn-m1Tw+wT∑xn∈D2xn-m2xn-m2Tw

=wTS1w+wTS2w=wTSWw(5.2.10)


其中,S1和S2为类内散布矩阵,即

Si=∑xn∈Dixn-mixn-miT,i=1,2(5.2.11)

SW为总散布矩阵。

SW=S1+S2(5.2.12)

注意散布矩阵与自协方差矩阵的估计值之间相差N倍的系数。散布矩阵反映了样本的分散度。
类似地,有


m^1- m^22
=wTm1-wTm22

=wTm1-m2m1-m2Tw

=wTSBw(5.2.13)


其中,SB为类间散布矩阵,即

SB=m1-m2m1-m2T(5.2.14)

其秩为1。将式(5.2.13)和式(5.2.10)代入式(5.2.9)得

J(w)=wTSBwwTSWw(5.2.15)

令式(5.2.15)对w的导数等于0,整理得

2wTm1-m2wTSWwm1-m2-wTm1-m2wTSWwSWw=0(5.2.16)

由于wTm1-m2wTSWw=c是一个标量,则式(5.2.16)的解为

w∝S-1Wm1-m2

由于w的范数大小无关紧要,故取解为

wo=S-1Wm1-m2(5.2.17)

由于SW和m1,m2都是直接由样本集计算得到,因此,从样本集学习得到最优方向向量wo,对于新的输入向量x,可将其投影到wo表示的直线,即投影为y^=wTox,可以通过给出一个门限b,利用门限,若x满足

wTox+b≥0(5.2.18)

则分类为C1,否则分类为C2。
若假设数据的类条件概率pxCi,i=1,2为高斯分布,且已知类先验概率pCi,则可以证明(参考3.4节的讨论)式(5.2.18)的判别式可进一步表示为

wTox-m1+m2/2>lnp(C2)p(C1)(5.2.19)

这里,若通过样本集用最大似然估计pCi,则有pC1/pC2=N1/N2。
2. 多类Fisher LDA
多分类情况下,设共有C类。给出数据样本D={(xn,yn)}Nn=1,这里样本标注yn的编码方式不重要,只要由标注将样本分为C个子集Di,i=1,2,…,C,每个子集对应第Ci类。设xn是K维向量,通过(C-1)个投影运算,将每个样本投影到(C-1)维空间,设K>C,投影的第i个分量为

y^i=wTix(5.2.20)

用W表示由wi作为第i列的K×(C-1)维矩阵,则(C-1)维投影向量y^表示为

y^=y^1,y^2,…,y^C-1T=WTx(5.2.21)

对于每个样本xn,由式(5.2.21)产生投影向量y^n,样本子集Di产生的投影子集Y^i,i=1,2,…,C。与二类问题类似,若定义投影子集的距离和散布矩阵,则其最终都表示为样本散布矩阵和待求W之间的表达式,故首先推广二分类的样本散布矩阵到多分类情况。
首先定义样本的类内总散布矩阵为各类内散布矩阵之和,即

SW=∑Ci=1Si(5.2.22)

其中,各类的散布矩阵和类均值为

Si=∑xn∈Dixn-mixn-miT,i=1,2,…,C(5.2.23)

和

mi=1Ni∑xn∈Dixn,i=1,2,…,C(5.2.24)

为了导出类间散布矩阵,首先表示全样本的均值m和散布矩阵ST为

m=1N∑Nn=1xn=1N∑Ci=1Nimi(5.2.25)

和

ST=∑Nn=1xn-mxn-mT(5.2.26)

可对ST做分解,一方面,可以将ST分解为类内总散布矩阵与类间散布矩阵之和,即

ST=SW+SB(5.2.27)

另一方面,得到式(5.2.26)的一种分解形式


ST
=∑Ci=1∑xn∈Dixn-mi+mi-mxn-mi+mi-mT

=∑Ci=1∑xn∈Dixn-mixn-miT+∑Ci=1∑xn∈Dimi-mmi-mT

=SW+∑Ci=1Nimi-mmi-mT(5.2.28)


因此,得到类间散布矩阵为

SB=∑Ci=1Nimi-mmi-mT(5.2.29)

对于数据集D={(xn,yn)}Nn=1的每个样本的xn,由式(5.2.21)得到一个投影向量

y^n=WTxn(5.2.30)

将每个子集Di,i=1,2,…,C投影到相应子集Y^i,i=1,2,…,C,对比原数据集的各种散布矩阵,可以得到投影子集Y^i的均值和散布矩阵如下。


m^i=1Ni∑y^n∈Y^iy^n,i=1,2,…,C(5.2.31)
m^=1N∑Ci=1Nim^i(5.2.32)

S^W=∑Ci=1∑y^n∈Y^iy^n-m^iy^n-m^iT(5.2.33)

S^B=∑Ci=1Nim^i-m^m^i-m^T(5.2.34)


将式(5.2.30)代入式(5.2.33)和式(5.2.34),可以证明


S^W=WTSWW(5.2.35)

S^B=WTSBW(5.2.36)


对于多分类情况,由于投影是向量y^,其类间散布矩阵和类内散布矩阵无法直接评价其分离性,但是这些矩阵的迹是标量并可描述其分离性,故多分类情况下的Fisher准则函数为

JW=trS^BtrS^W=trWTSBWtrWTSWW(5.2.37)

在4.1.4节已看到对迹目标函数求最优的问题,类似地,可以证明(留作习题)式(5.2.37)最大化所得到的W最优解满足

SBwi=λiSWwi,i=1,2,…,C-1(5.2.38)

其中,wi为W的列向量,是对应于S-1WSB的前(C-1)个最大特征值的特征向量。注意到式(5.2.29)中SB的定义,SB是由C项组成,每项的秩最大为1,但这C项只有(C-1)项是独立的,故SB的秩至多为C-1,因此,不为0的特征值至多为C-1,所求的解向量wi即为这些非0特征值所对应的特征向量。
类似于二分类问题,对于多分类问题,若类条件概率是高斯的,则可以证明: 对于新的x,可计算

gi=lnp(Ci)-12mTiS-1Wmi+12xTS-1Wmi,i=1,2,…,C(5.2.39)

若分类为Ck,k满足

k=argmaxigi(5.2.40)

注意到,尽管可以利用Fisher判别分析直接进行分类,但本质上Fisher判别分析是一种预处理,将数据投影到具有最大分离性的低维空间。在二分类问题中,低维空间是一维的; 在多分类问题中,低维空间是(C-1)维的。对于多分类问题,通过Fisher判别分析后,可以将数据集从D={(xn,yn)}Nn=1投影到D^=y^n,ynNn=1,若数据集是非高斯分布的,则可以用D^作为预处理后的数据集通过后续章节介绍的更高级的多分类器进行分类。
*5.2.2感知机
感知机(Perceptron)是一种广义线性判别函数,用于二分类问题。感知机的判别函数输出为

y^(x; w)=sgnwTx+w0(5.2.41)

其中,sgn(·)是符号函数,即

sgn(x)=1,x≥0

-1,x<0(5.2.42)



图5.2.4感知机的结构框图


感知机的输出只有±1,+1表示类C1,-1表示类C2。在感知机学习中,相应的样本集D={(xn,yn)}Nn=1的标注yn也取±1,而非0和1。图5.2.4所示为感知机的结构框图,图中空心圆表示两方面的计算: 元素求和与符号函数sgn(·)。

感知机与线性判别函数一样,其判决面是wTx+w0=0的超平面。为了训练感知机,需要由样本集D学习参数w,为此,需要确定感知机的目标函数。
为了描述算法方便,类似于线性回归的表示,可将wTx+w0表示为w-Tx-,这里w-=w0,wTT,x-包含哑元x0=1作为第1个元素。如果样本集D是可分的,总可以找到一个w-,使所有样本都能被正确分类。即若xn属于C1,则w-Tx-n>0,且yn=1; 若xn属于C2,则w-Tx-n<0,且yn=-1。可见,不管xn属于哪一类,正确分类情况下都有w-Tx-nyn>0。在感知机的训练初始阶段,给出的w-将一部分样本正确分类,而将另一部分样本错误分类,将错误分类的样本记为集合DE,则对于一个样本xn∈DE,有w-Tx-nyn<0,因此,将感知机目标函数定义为

Jw-=-∑xn∈DEw-Tx-nyn(5.2.43)

原理上,确定w-使感知机目标函数最小。仍然使用梯度算法,可得梯度为

w-Jw-=-∑xn∈DEx-nyn(5.2.44)

为了迭代实现方便,实际中采用SGD算法,即对于一个被错误分类的样本xn,yn,更新权系数为

w-(k+1)=w-(k)-ηw-Jnw-=w-(k)+ηx-nyn(5.2.45)

其中,上标(k)表示权系数更新的迭代序号; 学习率0<η≤1。
为了进行感知机的训练,首先给出权向量的初始值w-(0),从样本集中按照一定顺序取出一个样本xn,yn,判断其是否是被错误分类的样本,即是否满足w-(k)Tx-nyn<0,若不满足则跳过该样本,否则进行式(5.2.45)的权更新,直到所有样本都被正确分类,感知机收敛。
可以证明,在样本集满足线性可分的条件下,感知机是收敛的; 在样本集不满足线性可分的条件下,感知机不收敛。本节介绍感知机的主要目的是对历史的回忆,感知机算法由Frank Rosenblatt于1962年提出,是最早的有影响力的机器学习算法之一,代表了神经网络的早期工作。目前人们很少再用感知机设计一个实际的分类器,本节也不再对其进行更详细的讨论,最后只是简要介绍一下感知机的“异或”问题。
异或是一种逻辑运算,输入特征向量x是二维的,仅有两个分量x1和x2,每个分量只取0或1,当x1=x2时输出y=-1(标准逻辑运算时y=0,这里为了与感知机的输出一致,采用了-1),当x1≠x2时输出y=1。因此,异或问题只有4个样本,即样本集为

D=(0,0)T,-1,(0,1)T,1,(1,0)T,1,(1,1)T,-1(5.2.46)

样本如图5.2.5(a)所示,可以看到,找不到一条直线可将两类样本分开,故这是线性不可分的,感知机无法将两类样本正确分类。

式(5.2.41)和图5.2.4所示的感知机是早期神经网络的一个代表,实际上这只是一个神经元的结构,尚未构成“网络”。这种简单线性单元无法解决类似“异或”这样简单的线性不可分问题,限制了其应用。解决这类问题有两种直接办法,一是多个神经元并联和级联组成多层感知网络,二是引入非线性变换。第一种办法中的多层感知机或神经网络将在第9章详细讨论。引入非线性变换的方法在第4章的回归模型中已经采用过,一种简单的方法是由x映射到一组基函数向量φ(x)=φ1(x),φ2(x),…,φM-1(x)T,将式(5.2.41)扩充为

y^(x; w)=sgnwTφ(x)+w0(5.2.47)

将x映射到φ(x)空间,可将线性不可分样本集变换成φ(x)所表示空间中的线性可分集,从而用基函数感知机正确分类。
对于异或问题,可定义一个多项式函数φ(x),其中


φ1(x)=2(x1-0.5)

φ2(x)=4(x1-0.5)(x2-0.5)

(5.2.48)


把样本D={(xn,yn)}映射成Dφ=φ(xn),yn,则式(5.2.46)的样本集映射为

Dφ=(-1,1)T,-1,(-1,-1)T,1,(1,-1)T,1,(1,1)T,-1

注意,映射后的样本示如图5.2.5(b)所示,坐标轴分别记为φ1和φ2,在φ(x)各分量为坐标轴的空间内数据集是线性可分的,一条判决线是φ2=0,或-φ2>0可判决为正样。对应到x空间,对应的判决线是φ2(x)=4(x1-0.5)(x2-0.5)=0,即对应了图5.2.5(a)中的十字交叉虚线,(x1-0.5)(x2-0.5)<0为正样的判决区间,是由十字交叉虚线分割的4个区域的左上和右下区域,可见,这是正确的分类。


图5.2.5异或的示意图


通过映射φ(x),将样本映射到新空间,这些样本在新空间可能是线性可分的,由φi(x)的线性组合构成分类器的判别函数,判决面在新空间是超平面,判决面映射到x空间则是非线性曲面。选择合理的映射φ(x),可容易地解决异或问题。
对于该问题,φ2=0是最优的判决线,其他判决线(如图5.2.5(b)的几条虚线)也可以做出正确分类,但分类性能都不如φ2=0判决线性能稳健(即泛化性能好),即输入存在误差时可靠分类的能力。在将样本映射为Dφ后,训练式(5.2.4)的感知机,不能保证得到的判决线是φ2=0,由初始值和样本使用顺序,可能得到如图5.2.5(b)虚线所示的判决线,这样的判决线映射到x空间,也不再是图5.2.5(a)的十字虚线,而是有相应的变化,对标准输入样本仍可正确分类,但输入存在误差时则更容易出错。
对于异或的例子,感知机不能保证训练过程得到φ2=0的判决线,对于该问题,第6章讨论的SVM则可保证得到φ2=0作为判决线。一般在线性可分情况下,SVM可得到泛化性能更好的分类器; 在不可分情况下,SVM也可以良好地工作,由于SVM在机器学习中的重要性,专门在第6章做详细讨论。
5.3逻辑回归
逻辑回归(Logistic Regression)是一种典型的判别概率模型,本节讨论逻辑回归的目标函数和学习算法。对于中文名词“逻辑回归”稍做解释,尽管名称中有“回归”一词,逻辑回归却是一种基本的分类模型; 另外,单词Logistic并不是“逻辑”的意思,为此,也有作者使用音译名词“逻辑斯蒂回归”,考虑到“逻辑回归”一词在国内文献中使用已经很广泛,且用词简练,本书沿用“逻辑回归”的说法。作为判别概率模型,逻辑回归直接从样本中训练类后验概率表示。首先讨论二分类这一基本问题,然后推广到多分类问题。本节讨论的后验概率表示、模型的目标函数等内容,在第9章将直接推广到神经网络。
5.3.1二分类问题的逻辑回归
首先考虑只有两类的情况,分别表示为C1和C2,在数据集的样本xn,yn中,标注yn=1代表第1类,即C1,yn=0代表第2类,即C2。通过一个数据集学习一个模型,当给出一个新的特征向量输入x时,由模型计算分类为C1的后验概率pC1|x,则分类为C2的后验概率为pC2|x=1-pC1|x。由于0≤pC1|x≤1,需要给出一种函数表示这种后验概率,这里定义一种Logistic Sigmoid函数(简称为Sigmoid函数)表示后验概率。Sigmoid函数定义为

σ(a)=11+e-a(5.3.1)

这里,用符号σ(·)表示Sigmoid函数,自变量a称为该函数的激活值,后面讨论实际分类模型时,将a表示为特征向量x的函数。
之所以用σ(·)函数表示后验概率,一个重要原因是其满足概率的性质,即0≤σ(a)≤1,σ(a)是a的单调函数,且σ(-∞)=0,σ(∞)=1,σ(0)=0.5,σ(x)的图形如图5.3.1所示。


图5.3.1Sigmoid函数的图形


Sigmoid函数σ(a)的另一个性质是处处光滑、处处可导,这便于数学处理。本节后续用到σ(a)的两个基本性质,仅在下面列出,证明留作习题。


σ-a=1-σ(a)(5.3.2)

dσ(a)da=σ(a)[1-σ(a)](5.3.3)


如前所述,可通过σ(a)表示类后验概率,由于类后验概率是x的函数,可以定义激活值a是x的函数。在逻辑回归中,一般可选择a是x的线性函数,如线性回归关系,即

a(x)=∑Kk=0wkxk=wTx-(5.3.4)

其中,x0=1为哑元,x-为包含了哑元的特征向量; w为待学习的参数向量。更一般地,可以与第4章一样,定义基函数向量

φ(x)=1,φ1(x),φ2(x),…,φM-1(x)T(5.3.5)

则a表示为如下基函数线性回归。

a(x)=wTφ(x)(5.3.6)

由于线性回归相当于是φ(x)=x-的一个特例,本节后续讨论中,a采用更一般的式(5.3.6)表示的基函数形式。


将式(5.3.6)代入σ(a)的定义,用于表示C1的后验概率pC1|x,即逻辑回归的输出为


y^(x,w)
=pC1|x=σ(a)=σwTφ(x)

=11+exp-wTφ(x)(5.3.7)


由于式(5.3.7)也可以表示成f[wTφ(x)]的形式,这里f是非线性函数,故式(5.3.7)表示的逻辑回归输出也是一个广义线性模型。图5.3.2给出了逻辑回归的结构图,这里画出的是φ(x)=x-的情况,带有符号+和σ的圆圈表示其先通过求和得到激活值a,再经过激活函数σ(·)。这个圆表示了一种复合运算,后续可以看到,在一般神经网络的构成中,图5.3.2的结构表示神经网络中的一个神经元。


图5.3.2逻辑回归的结构图


显然,C2的后验概率pC2|x可表示为

pC2|x=exp-wTφ(x)1+exp-wTφ(x)(5.3.8)

设已选定了φ(x),接下来通过给出的训练样本集D={(xn,yn)}Nn=1学习参数向量w。由于已选定了基函数向量,故首先将样本集转换成以基函数向量表示的数据集,即通过转换得到数据集φxn,ynNn=1=φn,ynNn=1,这里用了简化符号φn=φxn。为了叙述方便,避免多重括号和下标,也简化其他几个符号如下。


an=a(xn)=wTφn(5.3.9)

y^n= y^(xn,w)=pC1xn=σan(5.3.10)


对于一个给定的样本φn,yn,把yn作为一个二元随机变量,即伯努利分布,yn=1的概率即属于C1类别的概率为y^n=σan,因此写出yn的似然函数为


pyn|w
=(y^n)yn(1- y^n)1-yn

=σ(wTφn)yn1-σ(wTφn)1-yn(5.3.11)


由于样本集的独立同分布假设,则全体标注y=y1,y2,y3,…,yNT的似然函数为

py|w=∏Nn=1pyn|w=∏Nn=1(y^n)yn(1- y^n)1-yn(5.3.12)

以负对数似然函数作为损失函数,即


J(w)=-lnpy|w
=-∑Nn=1ynlny^n+(1-yn)ln(1- y^n)(5.3.13)

式(5.3.13)称为交叉熵准则,尽管该准则是针对逻辑回归问题由最大似然原理导出的,后续可以看到对其他二分类的判别概率模型,交叉熵准则是一个通用准则,是建立在最大似然基础上的二分类问题的一般性准则。交叉熵的取名来自式(5.3.13)的形式,熵是用同一组概率进行计算的,而式(5.3.13)可理解为用了两组概率yn,1-yn和其近似值y^n,1-y^n,故称为交叉熵。最大似然原理对应着交叉熵的最小化,以此为目标得到权系数向量w的解。
式(5.3.13)是通过y^n=σ(wTφn)与w联系的,J(w)是w的非线性函数,没有闭式解。这里给出两种迭代求解方法: 梯度法和牛顿法。对于规模不太大的逻辑回归问题,两种解法都是有效的,牛顿法一般收敛更快。
1. 随机梯度算法(SGD)
首先讨论梯度算法。直接在式(5.3.13)两侧对w求导,得到目标函数的梯度,计算如下


wJ(w)=J(w)w

=-∑Nn=1ynlny^nw+(1-yn)ln(1-y^n)w

=-∑Nn=1yny^nσwTφnw-(1-yn)1-y^nσwTφnw

=-∑Nn=1yny^ny^n(1-y^n)φn-(1-yn)1-y^ny^n(1-y^n)φn

=∑Nn=1(y^n-yn)φn(5.3.14)


注意,式(5.3.14)中从第3行到第4行用到了σ(·)函数的导数性质,即式(5.3.3)。式(5.3.14)是所有样本对梯度的贡献,若采样SGD算法,则单一样本对梯度的贡献为

wJn(w)=(y^n-yn)φn
=σwTφ(xn)-ynφ(xn)(5.3.15)

注意到随机梯度由一个误差项乘以基函数向量构成(不采用基函数时为特征向量),而误差项为逻辑回归的输出与标注之间的误差,对于线性和广义线性模型,这是梯度表达式的一般形式。
有了梯度公式,给出权系数的初始值w(0),每次从样本集抽取一个样本φn,yn,每次样本抽取可以是随机的,故样本的标号n和权系数的迭代序号k使用不同的符号。SGD算法的权系数向量更新为


w(k+1)
=w(k)-ηwJnw(k)
=w(k)-ηy^n-ynφn

=w(k)-ησw(k)Tφ(xn)-ynφ(xn)(5.3.16)


其中,η为学习率。可以一次抽取m个小批量样本,将SGD推广到小批量算法,这种推广是直接的,具体公式可参考4.1节,此处不再重复。
2. 重加权最小二乘算法
SGD是一阶迭代算法,为了更快的收敛速率,也可采用二阶迭代算法,二阶迭代算法的代表是牛顿法,牛顿法用了式(5.3.13)目标函数对w的二阶导数,即汉森(Hessian)矩阵,汉森矩阵的定义为

H=2wJ(w)=2J(w)wiwjM×M(5.3.17)

为了导出H的表达式,将式(5.3.14)的结果写为如下矩阵与向量积的紧凑形式。

wJ(w)=∑Nn=1(y^n-yn)φn=ΦTy^-y(5.3.18)

其中,y^为由y^n构成的向量; Φ为基函数数据矩阵,其定义见式(4.3.6),其第n行为φTn。式(5.3.18)再次对w求导,得到如下矩阵(证明留作习题)。


H=2wJ(w)=w∑Nn=1(y^n-yn)φn

=∑Nn=1y^n(1-y^n)φnφTn=ΦTRΦ(5.3.19)



其中,R为对角矩阵,R=diagy^1(1-y^1),…,y^N(1-y^N)。有了汉森矩阵,则牛顿迭代算法为


w(k+1)
=w(k)-H-1wJnw(k)

=w(k)-ΦTRΦ-1ΦTy^-y

=ΦTRΦ-1ΦTRΦw(k)-ΦTy^-y

=ΦTRΦ-1ΦTRz(5.3.20)


其中,向量z为

z=Φw(k)-R-1y^-y(5.3.21)

牛顿法的权更新公式如式(5.3.20)所示,这实际是一个加权最小二乘的计算公式,在每次迭代时,通过旧权系数w(k)计算R和z,数据矩阵Φ不变。对角矩阵R相当于最小二乘的加权矩阵,每次迭代需要重新计算,故式(5.3.20)的迭代算法称为重加权最小二乘算法(Iterative Reweighted Least Squares,IRLS)。由于Φ不变,ΦTRΦ中只有对角权矩阵R每次迭代时变化,可以导出高效的求逆算法。
3. 正则化逻辑回归
正则化逻辑回归(Regularized Logistic Regression)可用于解决过拟合等问题,通过正则化控制模型复杂性。一种基本的权衰减正则化目标函数为


J(w)=-lnpy|w+12λ‖w‖22

=-∑Nn=1ynlny^n+(1-yn)ln(1-y^n)+12λwTw(5.3.22)


在正则化目标函数下,可得到梯度向量为

wJ(w)=∑Nn=1(y^n-yn)φn+λw(5.3.23)

如果使用随机梯度算法,则梯度向量为

wJn(w)=(y^n-yn)φn+λw(5.3.24)

注意,式(5.3.24)和式(5.3.23)中的λ取值不同,因为都是超参数,一般需要通过交叉验证获得,故用了同一个符号。使用随机梯度式(5.3.24)得到正则化情况下的SGD权更新公式为

w(k+1)=(1-ηλ)w(k)-ηy^n-ynφn

5.3.2多分类问题的逻辑回归
在表示多分类任务中,设共有C类,如式(5.1.2)所示用C维向量编码表示类型标注y,为方便重写如下。

y=0,…,0,1,0,…,0T(5.3.25)

y中各分量yi只取0或1,且∑iyi=1,即只有一个分量yk=1表示第k类,其他yi=0,i≠k,用符号Ck表示第k类。
在多分类问题的逻辑回归方法中,对于给出的特征向量x,输出它被分类为每类的后验概率,用C维向量y^表示输出,其分量表示分类为Ck的后验概率,即

y^k(x)=pCk|x(5.3.26)

为了用一种数学形式表示这种后验概率,即

0≤y^k(x)≤1,∑Ck=1y^k(x)=1(5.3.27)

推广式(5.3.1)的Sigmoid函数到Softmax函数。首先,针对每个y^k,定义一个相应的激活值,即

ak(x)=wTkφ(x),k=1,2,…,C(5.3.28)

其中,wk为一组待学习的参数向量,则Softmax函数定义为

y^k(x)=pCk|x=expak(x)∑Cj=1expaj(x),k=1,2,…,C(5.3.29)

可见,式(5.3.29)定义的Softmax函数满足式(5.3.27)的要求。先不考虑x,只考虑y^k作为aj的函数,可以证明一个基本性质如下(留作习题)。

y^kaj=y^k(Ikj-y^j)(5.3.30)

其中

Ikj=1,k=j

0,k≠j(5.3.31)

给出训练集{xn,yn}Nn=1,通过最大似然准则导出多分类逻辑回归的学习算法。首先,通过确定的基函数向量,将数据集变换为φxn,ynNn=1=φn,ynNn=1。为了表示清楚,给出一些符号的表示或缩写。标注yn可以进一步写为yn=yn1,yn2,…,ynCT,将yn转置作为第n行构成标注值矩阵Y=ynkN×C,对于一个样本xn,对应的基函数向量简写为φn,逻辑回归的Softmax输出y^n的一个分量记为y^nk=y^k(xn)=pCkxn。对于一个样本φn,yn,将yn作为C维二元向量,其概率表示为

pynw1,w2,…,wC=∏Ck=1(y^nk)ynk(5.3.32)

由所有样本的I.I.D性质,所有样本的联合概率为

pYw1,w2,…,wC=∏Nn=1∏Ck=1(y^nk)ynk(5.3.33)

式(5.3.33)中对w1,w2,…,wC的依赖是通过y^nk表现的。由于Y是已知的,式(5.3.33)是关于w1,w2,…,wC的似然函数。类似地,定义负对数似然函数作为损失函数,即

Jw1,w2,…,wC=-lnpYw1,w2,…,wC=-∑Nn=1∑Ck=1ynklny^nk(5.3.34)

以上函数存在约束条件

∑Ck=1ynk=1(5.3.35)

式(5.3.34)是多分类情况下的交叉熵准则。为了采用梯度法求解各权系数向量wj,需要求得式(5.3.34)对wj的梯度,可以证明梯度为

Jwj=∑Nn=1y^nj-ynjφn,j=1,…,C(5.3.36)

式(5.3.36)的证明如下。


Jwj=-wj∑Nn=1∑Ck=1ynklny^nk=-∑Nn=1∑Ck=1ynk1y^nky^nkanjanjwj

=-∑Nn=1∑Ck=1ynk1y^nky^nk(Ikj-y^nj)φn

=-∑Nn=1ynjφn-∑Ck=1ynky^njφn=∑Nn=1y^nj-ynjφn


以上证明从第1行到第2行用了式(5.3.30),最后一个等号用了约束条件式(5.3.35)。
注意到,对于每个权向量wj,梯度公式与二分类逻辑回归的梯度公式相同,如果采用SGD算法,每次随机抽取一个训练集样本,每个权向量用式(5.3.37)进行更新迭代。
w(k+1)j=w(k)j-ηjy^nj-ynjφn,j=1,2,…,C(5.3.37)

对于多类逻辑回归算法,每个权向量的更新公式与只有一个向量的二分类逻辑回归是相同的。因此,对每个权向量wj可导出相同的IRLS算法和正则化算法,扩展是直接的,不再详述。


ML09分
类学习2


5.4朴素贝叶斯方法
朴素贝叶斯方法是生成模型的一种,由于做了条件独立性假设,使其解得以简化。作为生成模型需要通过学习得到联合概率p(x,y),再通过贝叶斯公式得到分类的后验概率p(y|x),因此,朴素贝叶斯方法属于贝叶斯学习方法中的一类,由于其简单性,放在本章中作为分类的生成模型的例子。
为了叙述简单,本节只讨论二分类的例子,故y只取0和1。朴素贝叶斯的出发点是假设y作为条件下,x的各分量统计独立。这里设x为D维向量,即

x=x1,x2,…,xDT(5.4.1)

则朴素贝叶斯的假设为

p(x|y)=px1,x2,…,xD|y=∏Di=1p(xi|y)(5.4.2)

即在类型确定的条件下,特征向量的各分量是统计独立的。


图5.4.1朴素贝叶斯假
设的贝叶斯网络模型



在3.6.1节有向图模型的介绍时,曾以朴素贝叶斯假设作为有向图的一个实例说明了式(5.4.2)的假设尽管简单,但仍是一种合理的假设,作为复习,图5.4.1重画出朴素贝叶斯假设的有向图模型。因此,本节的内容也可以看作图模型从建模到参数学习再到推断和决策的一个简单但完整的实例。

在朴素贝叶斯方法中,常见的一种情况是假设x的每个分量取值是离散的,即xi只可能取M个有限值。在以下介绍中,首先假设一种简单情况,xi只取两个值,即xi∈0,1,这种情况下,给出朴素贝叶斯算法的详细推导,这个推导过程对于理解概率原理在机器学习中的应用是一个很好的例子,最后再把结果推广到xi可取M>2个不同值的一般情况。
在xi∈{0,1}的简单情况下,设D=10,x的一个例子为x=[0,1,1,0,1,0,0,1,0,0]T。由于各分量的独立性,对于x的每个分量,分别定义两个参数为


μi1=μiy=1=pxi=1y=1=pxi=1C1(5.4.3)

μi0=μiy=0=pxi=1y=0=pxi=1C2(5.4.4)


由于xi是一个伯努利随机变量,在条件y=k,k∈0,1下x的各分量独立,故可得到类条件概率为

pxy=k=∏Di=1μxiik1-μik1-xi,k∈0,1(5.4.5)

为了得到联合概率,需要y=k,k∈0,1的先验概率,定义如下符号表示该先验概率。

py=1=π

py=0=1-π(5.4.6)

有了这些准备,可以得到y取不同值时,联合概率的表示分别为


px,y=1=py=1pxy=1

=π∏Di=1μxii11-μi11-xi(5.4.7)


和


px,y=0=py=0pxy=0

=1-π∏Di=1μxii01-μi01-xi(5.4.8)


由于y只有两个取值,把两个取值考虑进来(相当于y是一个伯努利变量),得到联合概率为


px,yπ,μi1,μi0

=π∏Di=1μxii11-μi11-xiy×1-π∏Di=1μxii01-μi01-xi1-y(5.4.9)


在以上联合概率中,π,μi1,μi0,i=1,2,…,D是联合概率的参数,共有2D+1个参数待定。若给出训练样本{xn,yn}Nn=1,通过训练样本学习得到所有参数π,μi1,μi0,i=1,2,…,D,则学习过程得到了联合概率。设训练样本是I.I.D的,且样本已知,故似然函数为


py,Xπ,μi1,μi0

=∏Nn=1π∏Di=1μxnii11-μi11-xniyn1-π∏Di=1μxnii01-μi01-xni1-yn
(5.4.10)


将目标函数定义为负的对数似然,则


Jπ,μi1,μi0=-lnpy,Xπ,μi1,μi0

=-∑Nn=1ynlnπ+(1-yn)ln(1-π)-

∑Nn=1yn∑Di=1xnilnμi1+(1-xni)ln(1-μi1)-

∑Nn=1(1-yn)∑Di=1xnilnμi0+(1-xni)ln(1-μi0)(5.4.11)


将式(5.4.11)分别对各参数求导并令导数为0,得到各参数的解。令

lnpy,Xπ,μi1,μi0π=0

解得

π=1N∑Nn=1yn(5.4.12)

令

lnpy,Xπ,μi1,μi0μi1=0

解得

μi1=∑Nn=1ynxni∑Nn=1yn,i=1,2,…,D(5.4.13)

令

lnpy,Xπ,μi1,μi0μi0=0

解得

μi0=∑Nn=11-ynxni∑Nn=1(1-yn),i=1,2,…,D(5.4.14)

当得到了参数π,μi1,μi0,i=1,2,…,D后,则式(5.4.5)~式(5.4.9)的各种概率都已得到,包括类的先验概率、类条件概率和联合概率。除此之外,由这组参数还可以得到在给定一个新的特征输入x时分类的后验概率。利用贝叶斯公式,得到x被分为C1类的后验概率为


p(C1|x)=py=1|x=pxy=1py=1p(x)

=∏Di=1pxiy=1py=1∏Di=1pxiy=1py=1+∏Di=1pxiy=0py=0


=π∏Di=1μxii11-μi11-xiπ∏Di=1μxii11-μi11-xi+(1-π)∏Di=1μxii01-μi01-xi(5.4.15)


显然,x被分为C2类的后验概率为

p(C2|x)=py=0|x=1-py=1|x(5.4.16)

本节针对相对简单的情况: 二分类且x的每个分量只有两个取值,详细推导了朴素贝叶斯算法。下面针对两方面问题,再做一些讨论。
1. 拉普拉斯平滑
在以上讨论中,已经得到当有一个新的输入时,分类为C1的后验概率,看上去问题得以圆满解决。但在实际应用中,式(5.4.15)可能会遇到0/0困境。注意到,若在估计的参数中,有一个μi1=0和一个μj0=0存在,这里i和j可以表示任意两个分量,则代入式(5.4.15)有

py=1|x=00(5.4.17)

这是一个无解的情况,无法做出判决。在x的维度D很大,训练样本集规模有限时,这是很可能发生的情况,这是由最大似然估计的局限性所致。
第2章曾提到,在离散事件的情况下,最大似然估计的概率就是样本集中一类事件出现的比例,最大似然的概率估计是符合对概率的“频率”解释的。在本节中也是如此,可以看到式(5.4.12)~式(5.4.14)都给出了所估计概率的按“比例”分配的解释。例如,式(5.4.12)中,分子统计了训练样本集中标注为1的样本数目N1,π=pC1=N1/N就是样本集中标注为C1的样本所占比例; 式(5.4.13)中μi1的公式复杂一些,但也代表了同样的含义,它的分母为N1,即样本集中所有标注为C1的样本总数,而分子的求和项ynxni的含义是标注为C1的同时xni=1的样本贡献一个计数1,因此分子的含义是在所有标注为C1的样本中,x的第i分量为1的样本数之和,μi1表示了在所有标注为C1的样本中x的第i分量为1的样本所占的比例。无须重复,μi0的意义是相同的。在本问题中π的估计没有问题,样本数足够估计π的,但是一些μi1或μi0可能估计为0。例如,若D=1000,样本总数为10 000,则很有可能在样本集中x的某个分量从来没有出现过xni=1的情况,此时μi1估计为0。
解决这一问题的系统化的方法是采用贝叶斯估计替代最大似然估计,这样做需要给出每个参数一个合理的先验概率,这并不总是容易做到的。一种改善最大似然零概率估计的简单方法是拉普拉斯平滑。拉普拉斯平滑用于改善离散随机变量的概率估计。设一个离散随机变量x,其仅取k个可能的值,即x∈1,2,…,k,给出一组样本x1,x2,…,xm,需要估计概率

μi=px=i,i=1,2,…,k

则标准最大似然估计为

μi=∑mn=1Ixn=im(5.4.18)

其中,I(z)为示性函数,z为真时I(z)=1,z非真时I(z)=0。最大似然估计μi统计的就是xn=i在样本集中的比例,而拉普拉斯平滑做了如下修改。

μi=1+∑mn=1Ixn=im+k(5.4.19)

拉普拉斯平滑作为一种简单的修改,保证μi>0的同时满足概率的基本约束∑ki=1μi=1。
我们可以这样理解拉普拉斯平滑: 对待估计的随机变量取值施加等概率的先验分布,但是不显式地使用贝叶斯框架,而是虚拟地产生k个附加样本。由于假设等概率先验,假想可将集合1,2,…,k中每个值各取一次作为一个虚拟样本,将这k个虚拟样本加到样本集中,构成一个增广样本集,则拉普拉斯变换相当于用这一增广样本集做的最大似然估计。可见,拉普拉斯平滑相当于一种“弱”贝叶斯方法,或相当于一种正则化的最大似然方法。在机器学习中,直接对样本集进行增广是一种常用的正则化技术。
将拉普拉斯平滑应用于μi1和μi0估计式(5.4.13)和式(5.4.14),注意在这两个公式中,相当于k=2。μi1和μi0的估计公式修改为


μi1=1+∑Nn=1ynxni2+∑Nn=1yn,i=1,2,…,D(5.4.20)

μi0=1+∑Nn=11-ynxni2+∑Nn=1(1-yn),i=1,2,…,D(5.4.21)



这样就解决了式(5.4.17)所表示的问题。
2. 朴素贝叶斯模型的更一般情况
为了把前述的简单情况下的朴素贝叶斯算法推广到更一般情况,通过示性函数,给出式(5.4.12)~式(5.4.14)的一种等价表示,用示性函数表示的参数估计公式为


π=1N∑Nn=1Iyn=1(5.4.22)
μi1=∑Nn=1Iyn=1∩xni=1∑Nn=1Iyn=1(5.4.23)

μi0=∑Nn=1Iyn=0∩xni=1∑Nn=1Iyn=0(5.4.24)


其中,符号∩表示两个条件的交,即两个条件均满足才为真。
讨论更一般的情况,首先是多分类问题,分类任务有C个类型,可用Ck,k=1,2,…,C表示每类,与前面讨论一致,用C维向量编码表示类型y,由于y中只有一个分量为1,其余为0,故yk=1等价于Ck。类似于二分类情况,可以定义每类的先验概率为

πk=p(Ck)=pyk=1(5.4.25)

对特征向量x也推广到更一般化,x的每个分量仍是离散的,但不再局限于只取两个可能值,设x的第i个分量可取Mi个值,不失一般性,设xi∈0,1,…,Mi-1。给出一个概率参数的更一般的符号为


μ(l)ik=pxi=lyk=1=pxi=lCk,

l=0,1,…,Mi-1,k=1,…,C,i=1,2,…,D(5.4.26)


给出训练样本{xn,yn}Nn=1,把式(5.4.22)~式(5.4.24)推广到这种更一般的情况,相应参数估计公式为


πk=1N∑Nn=1Iynk=1,k=1,2,…,C(5.4.27)

μ(l)ik=∑Nn=1Iynk=1∩xni=l∑Nn=1Iynk=1,

l=0,1,…,Mi-1,k=1,2,…,C,i=1,2,…,D(5.4.28)


学习了这些参数后,可以得到联合概率。如果主要用于分类,则可以得到类后验概率,由贝叶斯公式和朴素贝叶斯的假设,给出一个新的特征向量x,得到类后验概率为


pCk|x
=pxCkp(Ck)∑Cj=1pxCjpCj

=πk∏Di=1pxiCk∑Cj=1πj∏Di=1pxiCj,k=1,2,…,C(5.4.29)


在式(5.4.29)中,若x给定了,则xi的取值就给定了,若xi=l,则pxiCk=μ(l)ik就确定了,用式(5.4.29)可以得到所有类的后验概率,并通过决策过程完成分类。由于式(5.4.29)的分母对所有Ck是相等的,若所有类的分类错误代价是相等的,则只需要分子部分的比较即可决定分类结果,即可分类为

Cko=argmaxCkπk∏Di=1pxiCk(5.4.30)

其中,Cko为分类结果。
最后通过实例说明朴素贝叶斯方法的应用。朴素贝叶斯方法用于很多实际分类问题中,一个典型的应用是用于垃圾邮件检测。收到一封电子邮件后,通过一个检测器判断其是否是垃圾邮件。要完成垃圾邮件检测,需要收集大量实际邮件,并由人工标注其是否为垃圾邮件,设垃圾邮件为C1类,正常邮件为C2类。为了用一个向量x表示一封邮件,预先构造一个词汇表,按照顺序,x的一个分量表示一个词汇。若xi为0/1变量,则xi=1表示对应的词汇存在于该邮件中,在这种应用中,x的维数D与词汇表中的词汇数相等,可能是一个很大的数,如D=5000。若只选择使用关键词汇表,则D可取更小的值,如D=200。
朴素贝叶斯假设下,描述x的概率参数为2D,若不使用朴素贝叶斯的假设,则参数为22D,这是难以存储的参数量。对收集的邮件完成标注和特征向量抽取后,得到样本集D={(xn,yn)}Nn=1,通过样本集得到朴素贝叶斯分类器的所有参数,当一个新邮件收到后,通过同样的方式检查邮件中的词汇,得到特征向量,则由式(5.4.15)计算该邮件是垃圾邮件的后验概率并做出判决。
当xi可取多值时,可用xi表示一封邮件中某词汇出现的次数(若超过Mi则限定为可表示的最大值),这样可得到更丰富的信息。利用朴素贝叶斯方法可有效判别垃圾邮件,对于大多数邮箱服务器可满足要求。但这类算法仅通过词汇级知识,若通过深度学习进行文法分析和关联知识分析,则可以更准确地检测出垃圾邮件。
*5.5机器学习理论简介
在第4章介绍了回归算法后,以回归问题为例,讨论了偏和方差的折中问题,本节将以分类问题为例,讨论机器学习的另一个理论问题——泛化界。偏和方差的折中与泛化界是机器学习理论中关注的两个基本问题,都是关于泛化误差的,两者之间也有密切的联系。
在机器学习模型的训练过程中,一般只有一组训练集,通过训练误差的最小化学习到一个模型,但真正关心的是泛化误差,即对不存在于训练集中的新样本,模型的预测性能如何?所以我们要关心一个基本问题: 训练误差和泛化误差之间有多大的差距?机器学习的概率近似正确(Probably Approximately Correct,PAC)理论对这个问题进行了研究。下面对该理论给出一个极为简要的介绍。
本节以二分类问题为例,讨论PAC理论的一些最基本概念和结论。假设所面对的样本可表示为(x,y),x为输入特征向量x∈X,X表示输入空间,y∈0,1表示类型,(x,y)满足概率分布pD(x,y),简写为pD,故可用(x,y)~pD表示样本服从的分布。从pD中采样得到满足独立同分布(I.I.D)的训练样本集为

D={(xi,yi)}Ni=1(5.5.1)

其中,每个样本(xi,yi)~pD。
用机器学习理论常用的术语,将前文所述的一个机器学习模型称为一个假设h,h(x)输出0,1表示类型,即完成映射h: X→0,1。在一个机器学习过程中,所有可能选择的假设构成一个假设空间H。对于任意假设h∈H,其在训练样本集上的分类错误率定义为训练误差或经验风险,经验风险表示为

R^(h)=1N∑Ni=1I[h(xi)≠yi](5.5.2)

经验风险表示假设h在训练集上的分类错误率。式(5.5.2)中I(·)为示性函数。可定义一般的泛化误差为

R(h)=P(x,y)~pDh(x)≠y(5.5.3)

对于任意样本(x,y)~pD,不管其是否存在于训练集中,泛化误差均表示其总体统计意义上的误分类率。
若不考虑可实现性,理论上,希望学习到的假设是从H空间找到使泛化误差最小的假设,即

h*=argminh∈HR(h)(5.5.4)

实际上,由于无法准确获得pD(x,y),故无法通过泛化误差优化获得最优假设,实际上总是通过经验风险最小化(Empirical Risk Minimization,ERM)得到一个假设,即

h^= argminh∈HR^(h)(5.5.5)

我们关心的一个理论问题: 通过ERM得到的假设h^与真正的泛化误差最小的h*之间的泛化误差差距有多大?即Rh*与Rh^差距有多大?
在继续讨论之前,首先通过一个例子进一步理解以上概念。
例5.5.1一个假设空间的例子。在5.2节的感知机的例子中,为了与本节分类输出用0,1表示相符,将分类假设修改为

h(x)=Iw-T
x-≥0(5.5.6)

这里,x-包含了哑元,w-包含了偏置系数,是(K+1)维参数向量。式(5.5.6)是一个假设,则假设空间为

H=hw-hw-(x)=Iw-T
x-≥0,w-∈RK+1(5.5.7)

H表示K维向量空间中的所有线性分类器集合,其中RK+1为K+1维实数集合。由于不同w-构成H的不同成员,故式(5.5.5)可具体化为

h^=argminw-∈RK+1R^hw-(5.5.8)

h^为ERM意义下的假设,一般不能通过学习得到h*w-。
实际上,感知机的目标函数式(5.2.43)是式(5.5.2)的经验风险的一种逼近,故训练得到的感知机是对h^的一种逼近。
对逻辑回归也可做类似理解,同样,其目标函数交叉熵也是式(5.5.2)经验风险函数的一种近似。
为了研究Rh*与R(h^)的关系,给出以下引理。
引理5.5.1设Z1,Z2,…,ZN为N个独立同分布的随机变量,均服从伯努利分布,且PZi=1=μ,定义样本均值为μ^=1N∑Ni=1Zi,令ε>0为一个固定值,则

Pμ-μ^>ε≤2exp-2ε2N(5.5.9)

该引理说明对于独立同分布样本,当N充分大时,对于给定的ε>0,均值估计和实际概率值之差大于ε的概率是很小的。
接下来,对于H有限的情况,利用引理5.5.1导出训练误差和泛化误差的误差界,然后将结论推广到H无限的情况。
5.5.1假设空间有限时的泛化误差界
首先假设空间H是有限的,即H=h1,h2,…,hK,假设空间成员数目K=H可能很大,但是有限的。例如5.4节介绍的朴素贝叶斯方法,当特征分量取离散值时,其假设空间是有限的。若每个特征变量取有限值,则第7章介绍的决策树假设空间也是有限的。对于例5.5.1,若w-取值为实数,则假设空间是无限的,但若w-的每个分量是由有限位二进制表示的数值,则其假设空间是有限的(详细讨论见例5.5.2)。首先讨论H有限的情况。
可从H空间选择一个固定的假设hk,利用引理5.5.1容易得到对于hk,其训练误差和泛化误差的关系。为此定义一个随机变量,对于(x,y)~pD,定义

Z=I[hk(x)≠y](5.5.10)

即当hk对样本(x,y)不能正确分类时Z=1。对式(5.5.1)所示的每个样本有Zi=I[hk(xi)≠yi],显然,hk的训练误差为

R^hk=1N∑Ni=1Zj(5.5.11)

对比引理5.5.1,Zi是I.I.D的伯努利随机变量,R^hk是对Rhk的样本均值估计,则由式(5.5.9)直接得到

PRhk-R^hk>ε≤2exp-2ε2N(5.5.12)

以上是对于一个固定的hk,泛化误差和训练误差之差(绝对值)大于ε的概率。对于给定ε,若样本数N足够大,则泛化误差与训练误差相差大于ε的概率很小。利用这个关系,可导出一个更一般的结果。因此,定义事件Ak为Rhk-R^hk>ε,则有PAk≤2exp-2ε2N,利用概率性质,至少存在一个h(表示为h),其R(h)-R^(h)>ε的概率为


Ph∈H,R(h)-R^(h)>ε
=PA1∪A2∪…∪AK

≤∑Hk=1PAk
≤∑Hk=12exp-2ε2N

=2Hexp-2ε2N(5.5.13)


由于是概率值,由互补性,式(5.5.13)的等价表示为对于所有h,有

PR(h)-R^(h)≤ε,h∈H≥1-2Hexp-2ε2N(5.5.14)

在式(5.5.14)中,令

δ=2Hexp-2ε2N(5.5.15)

式(5.5.14)有丰富的内涵,其中有3个量: δ,ε,N,以下从几个方面讨论式(5.5.14)的含义,并讨论这3个量的关系。
(1) 式(5.5.14)可重写为

PR(h)-R^(h)≤ε≥1-δ,h∈H(5.5.16)

对于给定的ε,所有假设h∈H都以不小于1-δ的概率满足R(h)-R^(h)≤ε,即泛化误差和训练误差之差不大于界ε。这里1-δ是一个置信概率,当N很大时,δ很小,以很高的概率满足R(h)-R^(h)≤ε。
(2) 假设空间的元素数目H是确定的,若给出ε和δ,则可得到满足以1-δ为概率达到R(h)-R^(h)≤ε所需的样本数目。固定δ,ε,从式(5.5.15)反解N为

N=12ε2ln2Hδ(5.5.17)

由式(5.5.15),N增大,δ减小,故可将式(5.5.17)看作满足δ,ε约束的最小样本数。故对于给定δ,ε,样本数可取为

N≥12ε2ln2Hδ(5.5.18)

(3) 在式(5.5.15)中,固定δ,N,解得

ε=12Nln2Hδ(5.5.19)

这给出了式(5.5.16)另一种解释,对于给定的δ,N,误差界满足

R(h)-R^(h)≤12Nln2Hδ(5.5.20)

将以上解释总结为定理5.5.1。
定理5.5.1对于假设空间H,固定δ,N,则以概率不小于1-δ,泛化误差与训练误差满足

R(h)-R^(h)≤12Nln2Hδ

或固定δ,ε,若样本数目取

N≥12ε2ln2Hδ

则以概率不小于1-δ满足R(h)-R^(h)≤ε。
以上结论对于假设空间中的任意假设h∈H均成立。我们更感兴趣的一个问题是,对于以经验风险最小化学习得到的假设h^和理论上泛化误差最小对应的h*之间的泛化误差的比较,由以上结果,若对h∈H有R(h)-R^(h)≤ε,则

R(h)≤R^(h)+ε(5.5.21)

对于h^,可得到如下不等式。


Rh^≤R^h^+ε
≤R^h*+ε≤Rh*+2ε(5.5.22)

式(5.5.22)中第1个不等式只是将h^代入式(5.5.21); 第2个不等式用了R^h^≤R^h*,这是因为h^是经验误差最小的假设; 第3个不等式对h*再次使用式(5.5.21)。式(5.5.22)的结论是ERM学习得到的假设h^与泛化误差最优的h*,其泛化误差之差不大于2ε。将该结论总结为重要的定理5.5.2。
定理5.5.2对于假设空间H,固定δ,N,则以概率不小于1-δ,泛化误差满足

Rh^≤minh∈HR(h)+212Nln2Hδ(5.2.23)

或固定δ,ε,若样本数目取

N≥12ε2ln2Hδ

则以概率不小于1-δ满足Rh^≤minh∈HR(h)+2ε。
由两个定理可见,若固定δ,N,式(5.5.19)计算了一个界ε,对于任意h∈H,训练误差和泛化误差之差以概率1-δ不大于ε,同时EMR最小化得到的假设h^与最小泛化误差之间的差距不大于2ε。
例5.5.2讨论例5.5.1的假设空间

H=hw-hw-(x)=Iw-T
x-
≥0,w-∈RK+1

w-有K+1个系数,若w-的每个分量用字长L的二进制表示(计算机中常取L为16、32或64,近期一些研究采用低比特实现神经网络时,甚至取L为8、4),则表示w-所需的二进制位数为L(K+1),故假设空间H共有H=2L(K+1)个元素,由式(5.5.18)可得对于固定δ,ε时,样本数需满足

N≥12ε2ln2Hδ=12ε2ln2×2L(K+1)δ=OKLε2ln1δ=Oε,δK(5.2.24)

或记为

N~Oε,δK(5.2.25)

其中,O(·)表示量级; Oε,δ(·)表示量级函数,其中δ,ε是其参数。式(5.2.25)尽管有比例系数存在,但需要的样本数N与模型的参数数目K是呈线性关系的。

5.5.2假设空间无限时的泛化误差界
将定理5.5.2的结论推广到假设空间H无限的情况。如前所述,像例5.5.1所示的线性模型或后续章节介绍的支持向量机和神经网络等模型,当参数取实数时,假设空间是无限的,即H=∞,这种情况下式(5.5.23)变得无意义。需要对其进行推广。这里对假设空间无限的情况,只做一个非常扼要的介绍。
当H=∞时,为了表示假设空间的表示能力(或容量),给出两个概念: 打散(Shatters)和VC维(VapnikChervonenkis Dimension),这里只给出其简单、直观性的介绍。
首先给出打散的概念,对于一个包含d个点的集合S=x1,x2,…,xd,称H可打散S是指: 对点集S对应加上一个任意标注集y1,y2,…,yd,则必存在h∈H,使h(xi)=yi,i=1,2,…,d。
对于一个假设空间H,至少存在一个最大元素数为d的点集合S,H可打散S,则H的VC维为d,记为VCH=d。这里,d是能被H打散的点集的最大元素数,对于有d+1个元素的点集合,H均不可能打散它。
例5.5.3图5.5.1给出了二维平面上的3个点组成的点集和其对应的各种标注,直线表示判决线,假设空间为二维线性分类器,即H=h(x)=θ1x1+θ2x2+θ0θ0,θ1,θ2∈R,图中每条判决线属于H,对这个3个元素的点集,H可将其打散。如果是4个点,则对于标注为异或运算,H不能正确分类,故H不能打散4个点的点集,因此,平面线性分类器的VC维为3,即VC(H)=3。



图5.5.1可由线性分类器打散的点集


若用VC维d表示一个假设空间的容量,则可得到与定理5.5.2类似的结论,这里只给出对应的定理。
定理5.5.3对于假设空间H,若其VC维为d=VCH,则对于所有h∈H,以概率不小于1-δ,满足

R(h)-R^(h)≤OdNlnNd+1Nln1δ(5.5.26)

对于h^满足

Rh^≤minh∈HR(h)+OdNlnNd+1Nln1δ(5.5.27)

对于以概率不小于1-δ满足Rh^≤minh∈HR(h)+2ε,样本数目需要求

N~Oε,δd(5.5.28)

注意,这里只用了量级函数O(·)而忽视了表达式中的一些具体常数系数,对于了解性能界这就足够了。从式(5.5.28)看,对于无限假设空间,所需样本数与假设空间的VC维呈线性关系。
机器学习理论给出对学习性能的整体性洞察,是非常有意义的,但目前对于一类实际模型的学习算法(如逻辑回归、神经网络、决策树等),其给出的一些要求(如样本数等)与具体算法的实际需求还有较大距离,在指导一类具体算法的参数选择上的实际意义还有待改善,故实际中仍更常用交叉验证等技术确定机器学习模型的各类参数。
5.6本章小结
本章介绍了基本的分类算法。对于确定性的判别函数方法,介绍了Fisher判别函数和感知机算法; 对于概率判别方法,介绍了逻辑回归算法; 对于简化的生成模型方法,介绍了朴素贝叶斯算法。这几类算法尽管简单,仍有其应用价值,尤其是逻辑回归和朴素贝叶斯方法,在小样本集和低复杂度的问题上是一种有效且简单的学习算法。由逻辑回归算法所引出的交叉熵目标函数和随机梯度算法,可直接推广到神经网络包括深度神经网络的学习中。
本章最后给出了机器学习理论的一个极其简单的介绍。本书没有设置专门的机器学习理论章节,而是结合回归介绍了偏和方差的折中问题,结合分类介绍了泛化界定理。这样做的目的是,将有关理论分散在不同章节,并结合一类学习算法进行介绍,增加其直观性,使其更容易理解。本书更侧重于机器学习算法的介绍,有关机器学习理论的讨论非常简略,对机器学习理论更感兴趣的读者,可参考Mohri等的Foundations of Machine Learning和Shai等的Understanding Machine Learning: From Theory to Algorithms,这两本书对机器学习理论进行了较为深入的讨论,均由张文生等译成了中文。对于统计学习理论的一个简明版的读本是Vapnik的The Nature of Statistical Learning Theory,已由张学工译成中文。
习题
1. 证明: 式(5.2.35)和式(5.2.36)的投影的总类内散布矩阵和类间散布矩阵分别可表示为

S^W=WTSWW,S^B=WTSBW

2. 证明准则

JW=trS^BtrS^W=trWTSBWtrWTSWW

最大化所得到W的最优解满足SBwi=λiSWwi,i=1,2,…,C-1,其中wi为W的列向量,是对应于S-1WSB的前(C-1)个最大特征值的特征向量。
3. 异或的样本集D=(0,0)T,-1,(0,1)T,1,(1,0)T,1,(1,1)T,-1是线性不可分的,可定义x映射到基函数向量φ(x)=φ1(x),φ2(x),…,φM-1(x)T,在φ(x)表示下设计感知机为y^(x; w)=sgnwTφ(x)+w0,对于异或问题,可定义一个多项式函数φ(x),其中


φ1(x)=2(x1-0.5)

φ2(x)=4(x1-0.5)(x2-0.5)


把样本集D={(xn,yn)}映射成Dφ=φ(xn),yn,样本集映射为

Dφ=(-1,1)T,-1,(-1,-1)T,1,(1,-1)T,1,(1,1)T,-1

在样本集Dφ上手动训练一个感知机(自行给出初始值和样本使用顺序)。
4. 在第3题中,通过映射函数


φ1(x)=2(x1-0.5)

φ2(x)=4(x1-0.5)(x2-0.5)


将异或样本映射成线性可分的,请自行另设计一组映射函数,将异或样本映射为可分情况。
5. 对于Sigmoid函数

σ(a)=11+e-a

证明: σ-a=1-σ(a) ,dσ(a)da=σ(a)1-σ(a)。
6. 逻辑回归的目标函数为J(w)=-∑Nn=1ynlny^n+(1-yn)ln(1-y^n),对w求二阶导数得到汉森矩阵,证明: 汉森矩阵表示为

H=∑Nn=1y^n(1-y^n)φnφTn=ΦTRΦ

7. 由Softmax的定义

y^k=expak∑Cj=1expaj,k=1,2,…,C

证明: y^kaj=y^k(Ikj-y^j)。
*8. 在网络上搜索并下载Iris数据集,该数据集样本属于鸢尾属下的3个亚属,分别为山鸢尾(Setosa)、变色鸢尾(Versicolor)和弗吉尼亚鸢尾(Virginica)。4个特征被用作样本的定量描述,它们分别是花萼和花瓣的长度和宽度。该数据集包含150个数据,每类 50 个数据。
(1) 从数据集中取出变色鸢尾(Versicolor)和维吉尼亚鸢尾(Virginica)的100个样本,训练一个二分类的逻辑回归分类器,对其进行分类(建议: 每类40个样本做训练,10个样本做测试)。
(2) 设计一个用于三分类问题进行分类的逻辑回归分类器,对3种类型进行分类(建议: 每类40个样本做训练,10个样本做测试)。