第5章



线性学习机器与线性分类器

5.1引言

从前面几章我们看到,如果能很好地描述和估计出样本的概率模型,可以用贝叶斯决策或最大似然估计的策略来实现分类或对其他目标进行判定。但是,很多情况下,建立样本的概率模型和准确估计概率密度函数及其他模型参数并不是一件容易的事,在特征空间维数高、内在关系复杂和样本较少的情况下尤其如此。
实际上,模式识别的目的是在特征空间中设法找到两类(或多类)之间的分界面,估计概率密度函数并不是我们的目的。两步贝叶斯决策是首先根据样本进行概率密度函数估计,再根据估计的概率密度函数求分类面。如果能直接根据样本求分类面,就可以省略对概率密度函数的估计。在第2章介绍正态分布下的贝叶斯决策时,已经看到,在样本为正态分布且各类协方差矩阵相等的条件下,贝叶斯决策的最优分类面是线性的,两类情况下判别函数形式是g(x)=wTx+ω0,而一般情况下为二次判别函数二次判别函数。实际上,如果知道判别函数的形式,可以设法从数据直接估计这种判别函数中的参数。这就是基于样本直接进行分类器设计的思想。进一步,即使不知道最优的判别函数是什么形式,仍然可以根据需要或对问题的理解设定判别函数类型,从数据直接求解判别函数。
基于样本直接设计分类器需要确定三个基本要素,一是分类器即判别函数的类型,也就是从什么样的判别函数类(函数集)中去求解; 二是分类器设计的目标或准则,在确定了设计准则后,分类器设计就是根据样本从事先决定的函数集中选择在该准则下最优的函数,通常就是确定函数类中的某些待定参数; 第三个要素就是在前两个要素明确之后,如何设计算法利用样本数据搜索到最优的函数参数(即选择函数集中的函数)。形式化表示就是:  在判别函数集{g(α),α∈Λ}中确定待定参数α*,使得准则函数L(α)最小(或最大),即L(α*)=minα L(α)。
不同的判别函数类、不同的准则及不同的优化算法就决定了不同的分类器设计方法。
在本章中,我们讨论线性判别函数线性判别函数,即g(x)=wTx+w0,多类情况下为gi(x)=wTix+wi0,i=1,2,…,c。采用不同的准则及不同的寻优算法就得到不同的线性判别方法。

5.1引言






线性分类器虽然是最简单的分类器,但是在样本为某些分布情况时,线性判别函数可以成为最小错误率或最小风险意义下的最优分类器。而在一般情况下,线性分类器只能是次优分类器,但是因为它简单而且在很多情况下效果接近最优,所以应用比较广泛,在样本有限的情况下有时甚至能取得比复杂的分类器更好的效果。
用线性函数去根据观测拟合变量间存在的依赖关系,是一个已经有两百年多年历史的研究课题,这就是著名的线性回归问题。在讨论线性分类器之前,我们先对线性回归进行简要的回顾。
5.2线性回归

5.2线性回归

线性回归是通过数据发现或估计两个或多个变量之间可能存在的线性依赖关系的基本的统计学方法。最早是在1805年和1809年由法国数学家AdrienMarie Legendre(1762—1833)和德国数学家Carl Friedrich Gauss(1777—1855)提出的
A.M.Legendre.Nouvelles méthodes pour la détermination des orbites des comètes, Firmin Didot, Paris, 1805.“Sur la Méthode des moindres quarrés” appears as an appendix.
C.F.Gauss.Theoria Motus Corporum Coelestium in Sectionibus Conicis Solem Ambientum.(1809).
。一般认为,比利时数学家、天文学家、社会学家、统计学家、诗人和剧作家Adolphe Quetelet(1796—1874)关于“平均人”的一系列定量研究为推动线性回归被广泛应用做出了奠基性的历史贡献。线性回归应该是人们最早对用数学方法关于从数据中“学习”规律的研究,可以看作是机器学习最原始的萌芽。
简单线性回归是学习两个取值为标量的随机变量之间的线性关系,如图51所示。其中一个变量称作响应变量或依赖变量,通常记作y,另一个变量称作解释变量或独立变量,通常记作x。线性回归就是通过(x,y)的一系列观测样本,估计它们之间的线性关系

y=w0+w1x
(51)

也就是估计其中的系数w1和w0。当响应变量依赖于多个解释变量时,这种关系就是多元线性回归

y=w0+w1x1+…+wdxd=∑di=0wixi=wTx
(52)


统计学把线性回归作为一门专门的学问进行了深入系统的研究,有大量关于回归的方法、理论性质及各种扩展的结论。我们在本书中只回顾其中最基本的估计方法。


图51线性回归示意图


在机器学习领域中,线性回归问题可以描述成如下的问题:  
假设有训练样本集

{(x1,y1),…,(xN,yN)},xj∈Rd+1,yj∈R
(53)

我们设计学习机器的模型为

f(x)=w0+w1x1+…+wdxd=∑di=0wixi=wTx
(54)

其中w=[w0,w1,…,wd]T是模型中待定的参数。线性回归估计的问题就是用训练样本集估计模型中的参数,使模型在最小平方误差意义下能够最好地拟合训练样本,即

minwE=1N∑Nj=1(f(xj)-yj)2
(55)


这个目标函数可以写成如下的矩阵形式

E(w)=1N∑Nj=1(f(xj)-yj)2=1NXw-y2=1N(Xw-y)T(Xw-y)
(56)

其中,X=xT1
︙
xTN为全部训练样本的解释变量向量组成的矩阵,y=y1
︙
yN是全部训练样本的响应变量组成的向量。
使式(56)的目标函数最小化的参数w应该满足

E(w)w=2NXT(Xw-y)=0
(57)

即

XTXw=XTy
(58)

因此,当矩阵(XTX)可逆时,最优参数的解为

w*=(XTX)-1XTy
(59)

这就是经典的“最小二乘法”线性回归,其中的矩阵(XTX)-1XT也被称作X的伪逆(Pseudoinverse)矩阵,记作X+。
采用这样的算法,假如真实的样本是服从式(52)的物理规律产生的,只是在观测中带有噪声或误差,则最小二乘线性回归就通过数据学习到了系统本来的模型。而在我们对数据背后的物理模型并不了解的情况下,线性回归给出了在最小平方误差意义下对解释变量与响应变量之间线性关系的最好的估计。
在5.6节中我们会看到,线性回归也可以通过迭代的方法求解,并且可以用来解决分类问题。
5.3线性判别函数的基本概念

5.3线性判别函数的基本概念

在第2章中,我们已经遇到过在两类情况下判别函数为线性的情况,这里给出它的一般表达式

g(x)=wTx+w0(510)

其中,x是d维特征向量,又称样本向量,w称为权向量,分别表示为

x=x1
x2
︙
xd,
w=w1
w2
︙
wd

w0是个常数,称为阈值权。对于两类问题的线性分类器可以采用下述决策规则:  令

g(x)=g1(x)-g2(x)

则

如果g(x)>0,则决策x∈ω1

如果g(x)<0,则决策x∈ω2

如果g(x)=0,可将x任意分到某一类,或拒绝(511)

方程g(x)=0定义了一个决策面,它把归类于ω1类的点与归类于ω2类的点分割开来。当g(x)为线性函数时,这个决策面便是超平面。
假设x1和x2都在决策面H上,则有

wTx1+w0=wTx2+w0(512)


或

wT(x1-x2)=0(513)



图52线性判别函数线性判别函数


这表明,w和超平面H上任一向量正交,即w是H的法向量。一般来说,一个超平面H把特征空间分成两个半空间,即对ω1类的决策域R1和对ω2类的决策域R2。因为当x在R1中时,g(x)>0,所以决策面的法向量是指向R1的。因此,有时称R1中的所有x在H的正侧,相应地,称R2中的所有x在H的负侧。
判别函数g(x)可以看成是特征空间中某点x到超平面的距离的一种代数度量,见图52。
若把x表示成

x=xp+rw‖w‖(514)

其中,xp是x在H上的射影向量; 
r是x到H的垂直距离; 
w‖w‖是w方向上的单位向量。

将式(514)代入式(510),可得

g(x)=wTxp+rw‖w‖+w0=wTxp+w0+rwTw‖w‖=r‖w‖

或写作

r=g(x)‖w‖(515)

若x为原点,则

g(x)=w0
(516)

将式(516)代入式(515),就得到从原点到超平面H的距离



r0=w0‖w‖(517)


如果w0>0,则原点在H的正侧; 若w0<0,则原点在H的负侧。若w0=0,则g(x)具有齐次形式wTx,说明超平面H通过原点。图52对这些结果作了几何解释。
总之,利用线性判别函数进行决策,就是用一个超平面把特征空间分割成两个决策区域。超平面的方向由权向量w确定,它的位置由阈值权w0确定。判别函数g(x)正比于x点到超平面的代数距离(带正负号)。当x在H正侧时,g(x)>0; 在负侧时,g(x)<0。
5.4Fisher线性判别分析

5.4Fisher线性判别分析

现在从最直观的Fisher线性判别分析(linear discriminant analysis,LDA)开始来介绍一些最有代表性的线性判别方法。
LDA是R. A. Fisher于1936年提出来的方法
Fisher R A.The use of multiple measurements in taxonomic problems
.Annals of Eugenics,7:   179188,1936.。
两类的线性判别问题可以看作是把所有样本都投影到一个方向上,然后在这个一维空间中确定一个分类的阈值。过这个阈值点且与投影方向垂直的超平面就是两类的分类面。
那么,如何确定投影方向呢?
在图53的例子中,可以看到,按左图中的方向投影后两类样本可以比较好地分开,而按右图的方向投影后则两类样本混在一起。显然,左图的投影方向是更好的选择。Fisher线性判别的思想就是,选择投影方向,使投影后两类相隔尽可能远,而同时每一类内部的样本又尽可能聚集。


图53寻找有利于分类的投影方向



为了定量地研究这一问题,我们先来定义一些基本概念。
这里只讨论两类分类的问题。训练样本集是X={x1,…,xN},每个样本是一个d维向量,其中ω1类的样本是X1={x11,…,x1N1},ω2类的样本是X2={x21,…,x2N2}。我们要寻找一个投影方向w(w也是一个d维向量),投影以后的样本变成

yi=wTxi,i=1,2,…,N(518)

在原样本空间中,类均值向量为

mi=1Ni∑xj∈Xixj,i=1,2(519)

定义各类的类内离散度矩阵类内离散度矩阵(withinclass scatter matrix)为

Si=∑xj∈Xi(xj-mi)(xj-mi)T,i=1,2(520)

总类内离散度矩阵(pooled withinclass scatter matrix)为有文献采用如下定义:  


Si=1Ni∑xj∈Xi(xj-mi)(xj-mi)T,i=1,2(521a)

Sw=N1NSi+N2NS2(521b)


Sw=S1+S2(522)

类间离散度矩阵类间离散度矩阵(betweenclass scatter matrix)定义为 

Sb=(m1-m2)(m1-m2)T(523)

在投影以后的一维空间,两类的均值分别为

m~i=1Ni∑yj∈Yiyj=1Ni∑xj∈XiwTxj=wTmi,i=1,2(524)

类内离散度不再是一个矩阵,而是一个值

S~2i=∑yj∈Yi(yj-m~i)2,i=1,2(525)

总类内离散度为

S~w=S~21+S~22(526)

而类间离散度就成为两类均值差的平方 

S~b=(m~1-m~2)2(527)

前面已经提出,希望寻找的投影方向使投影以后两类尽可能分开,而各类内部又尽可能聚集,这一目标可以表示成如下的准则 

max JF(w)=S~bS~w=(m~1-m~2)2S~21+S~22(528)

这就是Fisher准则函数Fisher准则函数(Fishers Criterion)。
把式(518)代入式(527)和式(525),得到


S~b=(m~1-m~2)2

=(wTm1-wTm2)2

=wT(m1-m2)(m1-m2)Tw

=wTSbw(529)

以及


S~w=S~21+S~22

=∑xj∈X1(wTxj-wTm1)2+∑xj∈X2(wTxj-wTm2)2

=∑xj∈X1wT(xj-m1)(xj-m1)Tw+∑xj∈X2wT(xj-m2)(xj-m2)Tw

=wTS1w+wTS2w

=wTSww
(530)


因此,Fisher判别准则变成

maxw JF(w)=wTSbwwTSww(531)

这一表达式在数学物理中被称作广义Rayleigh商广义Rayleigh商(generalized Rayleigh quotient)。
应注意到,我们的目的是求使得式(531)最大的投影方向w。由于对w幅值的调节并不会影响w的方向,即不会影响JF(w)的值,因此,可以设定式(531)的分母为非零常数而最大化分子部分,即把式(531)的优化问题转化为

maxwTSbw

s.t.wTSww=c≠0(532)

其中,“s.t.”表示优化问题中需要满足的约束条件(英文“subject to”的缩写)。
这是一个等式约束下的极值问题,可以通过引入拉格朗日拉格朗日(Lagrange)乘子转化成以下拉格朗日函数的无约束极值问题:  

L(w,λ)=wTSbw-λ(wTSww-c)(533)

在式(533)的极值处,应该满足

L(w,λ)w=0(534)

由此可得,极值解w*应满足

Sbw*-λSww*=0(535)

假定Sw是非奇异的(样本数大于维数时通常是非奇异的),可以得到

S-1wSbw*=λw*(536)

也就是说,w*是矩阵S-1wSb的本征向量。我们把式(523)的Sb代入,式(536)变成

λw*=S-1w(m1-m2)(m1-m2)Tw*(537)

应注意到,(m1-m2)Tw*是标量,不影响w*的方向,因此可以得到w*的方向是由S-1w(m1-m2)决定的。由于我们只关心w*的方向,因此可以取

w*=S-1w(m1-m2)(538)

这就是Fisher判别准则下的最优投影方向。
Fisher线性判别投影方向也可以直接用下面另一种方法求得。 
式(531)的解满足如下极值条件

JF(w)w=0(539)

将JF(w)对w求导,可得

wT(m1-m2)wTSww2(m1-m2)-2wT(m1-m2)wTSwwSww=0(540)

(此公式的推导读者可作为习题练习)。分析式(540),可以看到,由于wT(m1-m2)wTSww是标量,在Sw非奇异的条件下,式(540)的解满足

w*∝S-1w(m1-m2)(541)

由于我们只关心w的方向,所以式(538)就是式(540)的解。
需要注意的是,Fisher判别函数最优的解本身只是给出了一个投影方向,并没有给出我们所要的分类面。要得到分类面,需要在投影后的方向(一维空间)上确定一个分类阈值w0,并采取决策规则

若g(x)=wTx+w00,
则x∈ω1


ω2(542)

回顾第2章中曾经讲到的,当样本是正态分布且两类协方差矩阵相同时,最优贝叶斯分类器是线性函数g(x)=wTx+w0,且其中


w=Σ-1(μ1-μ2)(543)

w0=-12(μ1+μ2)TΣ-1(μ1-μ2)-lnP(w2)P(w1)(544)


比较式(538)与式(543)可以看到,在样本为正态分布且两类协方差相同的情况下,如果把样本的算术平均作为均值的估计、把样本协方差矩阵当作是真实协方差矩阵的估计,则Fisher线性判别所得的方向实际就是最优贝叶斯决策的方向,因此,可以用式(544)来作为分类阈值,其中用mi代替μi,用S-1w代替Σ-1(采用式(521a)和式(521b)的定义),即 

w0=-12(m1+m2)TS-1w(m1-m2)-lnP(w2)P(w1)(545)

在样本不是正态分布时,这种投影方向和阈值并不能保证是最优的,但通常仍可以取得较好的分类结果。
如果不考虑先验概率的不同,则可以采用阈值

w0=-12(m~1+m~2)(546)

或者

w0=-m~(547)

其中,m~是所有样本在投影后的均值。
把式(545)代入式(542)中并考虑到式(538),可以把决策规则写成

若g(x)=wTx-12(m1+m2)logP(ω2)P(ω1),则x∈
ω1


ω2(548)



图54Fisher线性判别示意图

其直观的解释就是,把待决策的样本投影到Fisher判别的方向上,通过与两类均值投影的平分点相比较做出分类决策。在先验概率相同的情况下,以该平分点为两类的分界点; 在先验概率不同时,分界点向先验概率小的一侧偏移,如图54所示。


Fisher线性判别并不对样本的分布作任何假设。但在很多情况下,当样本维数比较高且样本数也比较多时,投影到一维空间后样本接近正态分布。这时可以在一维空间中用样本拟合正态分布,用得到的参数来确定分类阈值。
5.5感知器

5.5感知器

Fisher线性判别是把线性分类器的设计分为两步,一是确定最优的方向,二是在这个方向上确定分类阈值。下面研究一种直接得到完整的线性判别函数g(x)=wTx+w0的方法——感知器(perceptron)。
感知器是人们设计的第一个具有学习能力的机器
Frank Rosenblatt, The Perceptrona perceiving and recognizing automaton, Report 854601, Cornell Aeronautical Laboratory, Jan. 1957.,在机器学习和模式识别历史上扮演了重要的角色。在后面章节的介绍中我们会看到,它是多层感知器神经网络方法和各种深度学习方法的基础,也是支持向量机方法的基础。
为了讨论方便,把向量x增加一维,但其取值为常数,即定义

y=[1,x1,x2,…,xd]T(549)

其中,xi为样本x的第i维分量。我们称y为增广的样本向量。相应地,定义增广的权向量为

α=[w0,w1,w2,…,wd]T(550)

线性判别函数变为

g(y)=αTy(551)

决策规则是:  如果g(y)>0,则y∈ω1; 如果g(y)<0,则y∈ω2。
下面定义样本集可分性的概念。

对于一组样本y1,…,yN,如果存在这样

图55线性可分的样本集和线性
不可分的样本集示例

的权向量α,使得对于样本集中的任一个样本yi,i=1,…,N,若y∈ω1则αTyi>0,若y∈ω2则αTyi<0,那么称这组样本或这个样本集是线性可分线性可分的。即在样本的特征空间中,至少存在一个线性分类面能够把两类样本没有错误地分开,如图55(a)所示,而55(b)中的一组样本则是线性不可分的。


如果定义一个新的变量y′,使对于第一类的样本y′=y,而对第二类样本则y′=-y,即

y′i=yi,若yi∈ω1


-yi,若yi∈ω2i=1,2,…,N(552)

则样本可分性条件就变成了存在α,使

αTy′i>0,i=1,2,…,N(553)

这样定义的y′称作规范化增广样本向量规范化增广样本向量增广样本向量。在本节和下一节,为了讨论方便,都采用规范化增广样本向量,并且把y′仍然记作y。
本小节只讨论样本线性可分的情况。
对于线性可分的一组样本y1,…,yN(采用规范化增广样本向量表示),如果一个权向量α*满足

αTyi>0,i=1,2,…,N(554)

则称α*为一个解向量。在权值空间中所有解向量组成的区域称作解区。
显然,权向量和样本向量的维数相同,可以把权向量画到样本空间。对于一个样本yi,αTyi=0定义了权空间中一个过原点的超平面H^i。对于这个样本来说,处于超平面H^i正侧的任何一个向量都能使αTyi>0,因而都是对这个样本的一个解。考虑样本集中的所有样本,解区就是每个样本对应超平面的正侧的交集,如图56所示。


解区中的任意一个向量都是解向量,都能把样本没有错误地分开。但是,从直观角度看,如果一个解向量靠近解区的边缘,虽然所有样本都能满足αTyi>0,但某些样本的判别函数可能刚刚大于零,考虑到噪声、数值计算误差等因素,靠近解区中间的解向量应该更加可靠。因此,人们提出了余量的概念,即把解区向中间缩小,不取靠近边缘的解,如图57所示。形式化表示就是,引入余量b>0,要求解向量对满足

αTyi>b,i=1,2,…,N(555)




图56解向量和解区





图57带有余量的解区


下面我们来看如何找到一个解向量。
对于权向量α,如果某个样本yk被错误分类,则αTyk≤0。我们可以用对所有错分样本的求和来表示对错分样本的惩罚 

JP(α)=∑αTyk≤0(-αTyk)(556)

这就是20世纪50年代Rosenblatt提出的感知器(Perceptron)准则函数Rosenblatt F.The perceptron:  a probabilistic model for information storage and organization in the brain.Cornell Aeronautical Laboratory,
Psychological Review,1958,65(6):  386408.。
显然,当且仅当Jp(α*)=minJP(α)=0时α*是解向量。
感知器准则函数式(546)的最小化可以用梯度下降方法迭代求解

α(t+1)=α(t)-ρtJP(α)(557)

即下一时刻的权向量是把当前时刻的权向量向目标函数的负梯度方向调整一个修正量,其中ρt为调整的步长。目标函数JP对权向量α的梯度是 

JP(α)=JP(α)α=∑αTyk≤0(-yk)(558)

因此,迭代修正的公式就是

α(t+1)=α(t)+ρt∑αTyk≤0yk(559)

即在每一步迭代时把错分的样本按照某个系数加到权向量上。
通常情况下,一次将所有错误样本都进行修正的做法并不是效率最高的,更常用的是每次只修正一个样本的固定增量法,算法步骤是:  
(1) 任意选择初始的权向量α(0),置t=0; 
(2) 考查样本yj,若α(t)Tyj≤0,则α(t+1)=α(t)+yj,否则继续; 
(3) 考查另一个样本,重复(2),直至对所有样本都有α(t)Tyj>0,即JP(α)=0。
如果考虑余量b,则只需将上面的算法中的错分判断条件变成α(t)Tyj≤b即可。


图58感知器学习算法
收敛过程示意

可以证明,对于线性可分的样本集,采用这种梯度下降的迭代算法,经过有限次修正后一定会收敛到一个解向量α*。这里不给出严格的证明,而是用图58的例子来直观地说明这一收敛过程。


在图58的例子中,只有三个样本y1,y2,y3(注意是规范化增广样本向量)。假设令权向量初值为α(0)=0(零向量,图58中的“1”位置); 在第一步,考查y1,α(0)Ty1=0,所以需要向y1的方向修正权值α(1)=α(0)+y1,权向量变成图58中的第2个点; 下一步,考查y2,α(1)Ty2>0,再考查y3,发现α(1)Ty3<0,所以采取修正α(2)=α(1)+y3,得到了图中的第3个点; 第四步发现y1又被分错,α(2)Ty1<0,再采取修正α(3)=α(2)+y1,权向量变成了图中的第4个点; 第五步,y2依然是分类正确的,而y3又被分错,所以需再次向y3方向调整权值α(4)=α(3)+y3,变成了图中的第5个点; 第六步,由于新的权值又对y1错分了,所以再次将y1方向调整,α(5)=α(4)+y1,得到第6个点所示的权向量。此时再次考查3个训练样本,发现都被正确分类了,α(5)就是迭代求得的解向量。不难想象,不论样本数目和维数如何,只要解区存在(样本线性可分),那么根据相同的原理,总可以经过有限步的迭代求得一个解向量。
这种单步的固定增量法采用的修正步长是ρt=1。为了减少迭代步数,人们还提出可以使用可变的步长,例如绝对修正法就是对错分样本yj用下面的步长来调整权向量 

ρt=|α(k)Tyj|‖yj‖2(560)

感知器算法是最简单的可以学习的机器。由于它只能解决线性可分的问题,所以,在实际应用中,直接使用感知器算法的场合并不多。但是,它是很多更复杂的算法的基础,例如第6章将要介绍的支持向量机和多层感知器人工神经网络。
在感知器准则中,要求全部样本是线性可分的。此时,经过有限步的迭代梯度下降法就可以收敛到一个解。当样本不是线性可分时,如果仍然使用感知器算法,则算法不会收敛。如果任意地让算法停止在某一时刻,则无法保证得到的解是有用的(能够把较多的样本正确分类)。人们研究了很多策略来设法使感知器算法在样本集不是线性可分时仍能得到合理有用的解,其中一种比较常用的做法是,在梯度下降过程中让步长按照一定的启发式规则逐渐缩小,这样就可以强制算法收敛,而且往往可以得到有用的解。如果多数样本是可分的,那么这种简单的做法在很多情况下还是有效的。
5.6最小平方误差判别

5.6最小平方误差判别

这一节讨论考虑线性不可分样本集的分类方法。在线性不可分的情况下,不等式组

αTyi>0,i=1,2,…,N(561)

不可能同时满足。一种直观的想法就是,希望求解一个α*使被错分的样本尽可能少,即不满足不等式(561)的样本尽可能少,这种方法是通过解线性不等式组来最小化错分样本数目,通常采用搜索算法求解。
但是,求解线性不等式组有时并不方便,为了避免此问题,可以引进一系列待定的常数,把不等式组(561)转变成下列方程组

αTyi=bi>0,i=1,2,…,N(562)

或写成矩阵形式 

Yα=b(563)

其中



Y=yT1
︙
yTN=
y11…y1d^


︙︙

yN1…yNd^
(564)

b=[b1,b2,…,bN]T(565)


其中d^是增广的样本向量的维数,d^=d+1。暂且不考虑常数向量b如何确定的问题,先来看这个方程组的求解。
很显然,这个方程组求解的问题就是5.2节中讨论的线性回归问题,只不过这里的响应变量是人为对每个样本给定的bi。
通常情况下,N>d^,所以式(563)中的方程个数大于未知数个数,属于矛盾方程组,无法求得精确解。方程组的误差为e=Yα-b,可以求解方程组的最小平方误差解,即

α*: minα JS(α)(566)

其中JS(α)是最小平方误差(MSE)准则函数 

JS(α)=‖Yα-b‖2=∑Ni=1αTyi-bi2(567)

这个准则函数的最小化主要有两类方法:  伪逆伪逆法求解与梯度下降法求解。
JS(α)在极值处对α的梯度应该为零,依此可以得到

JS(α)=2 YT(Yα-b)=0(568)

可得

α*=(YTY)-1YTb=Y+b(569)

其中Y+=(YTY)-1YT是长方矩阵Y的伪逆。

也可以用梯度下降法梯度下降法来迭代求解式(567)的最小值。算法如下:  
(1) 任意选择初始的权向量α(0),置t=0; 
(2) 按照梯度下降的方向迭代更新权向量 

α(t+1)=α(t)-ρtYT(Yα-b)(570)

直到满足JS(α)≤ξ或者‖α(t+1)-α(t)‖≤ξ时为止,其中ξ是事先确定的误差灵敏度。
参照感知器算法中的单步修正法,对最小平方误差准则,也可以采用单样本修正法来调整权向量 

α(t+1)=α(t)+ρt(bk-α(t)Tyk)yk(571)

其中,yk是使得α(t)Tyk≠bk的样本。
这种算法称作WidrowHoff算法WidrowHoff算法,也称作最小均方根算法(LMS算法)最小均方根算法或LMS算法(leastmeansquare algorithm)。历史上,用这种算法构造的学习机器称作ADALINE
Widrow & Hoff, Adaptive switching circuits,1960 IRE Western Electric Show and Convention Record, Part 4, pp.96104, Aug, 1960.,与感知器一起是现在神经网络类学习机器的最早形式。
显然,我们也同样可以用类似式(571)的迭代算法来实现5.2节中提出的线性回归问题的迭代求解。
上面一直没有讨论b的选取问题。选择不同的b会带来不同的结果。可以证明,如果对应同一类样本的bi选择为相同的值,那么最小平方误差方法的解等价于Fisher线性判别的解,把样本和权向量都还原成增广以前的形式后有

w*∝S-1W(m1-m2)(572)

其中,m1、m2是两类各自的均值向量,SW是总类内离散度矩阵。特别地,当b的选择为第一类样本对应的bi都是N/N1,第二类样本对应的bi都是N/N2时,阈值w*0为样本均值在所得一维判别函数方向的投影,即

w0=-mTw*(573)

其中,N1、N2分别是第一类和第二类的样本数,N是样本总数,m是全部样本的均值,即m=1N(N1m1+N2m2)。
另外还可以证明,如果对所有样本都取bi=1,那么当N→∞时,MSE算法的解是贝叶斯判别函数

g0(x)=P(ω1|x)-P(ω2|x)(574)

的最小平方误差逼近。即,下面定义的均方逼近误差

ε2=∫αTy-g0(x)2p(x)dx(575)

在α*=Y+1N时取得最小值,其中1N表示由N个1组成的列向量。
5.7罗杰斯特回归
罗杰斯特回归(Logistic regression):  国内部分文献和教科书译为“逻辑回归”,个别在线词典也把logistic翻译为“逻辑的”,笔者经考证后认为不妥。从语言学上logistic一词与logic并无关系,故笔者采用了部分统计学文献中音译的做法,类似的音译还有“罗杰斯蒂回归”等。Logistic这个形容词来源于名词logistics,据牛津字典,其含义是The detailed coordination of a complex operation involving many people, facilities, or supplies,即涉及很多人、设施和物资的复杂任务的详细协调,经常用于指军事或其他重大行动中的后勤,也指现代社会中的物流。法国数学家PierreFrancois Verhulst(1804—1849)在1845年把图510中的曲线用法文称作courbe logistique,即罗杰斯特曲线(Logistic curve),把对应的函数称作罗杰斯特函数(logistic function)。当时他在文献中并未对名字进行解释,后人就一直沿用这个名字。

5.7罗杰斯特回归

在5.2节中简要介绍的线性回归,在很多实际问题中有大量应用,例如我们可以用它来研究身高与体重的关系。事实上,推动线性回归走入应用的数学家Adolphe Quetelet基于身高与体重关系所定义的体重指数BMI一直被沿用至今。图59给出了一组样本上得到的人的血压(收缩压)与年龄的关系,这种线性回归对我们从数据中认识规律发挥了重要作用,从数据中学习到的线性模型也可以用来对连续取值的响应变量进行定量预测。


图59线性回归的例子(Colton T. Statistics in Medicine. Boston:   Little Brown, 1974)


一般情况下,所关心的变量可能与多个自变量有关系,这就是多元线性回归问题,即求下列线性模型中的系数的问题:  y=β0+β1x1+…+βmxm+ε,其中,y是我们要回归的变量,x1,…,xm是与它有关系的特征变量,β1,…,βm是它们对应的系数,β0是常数项,ε是回归的残差(亦称离差),即用x的线性函数β0+β1x1+…+βmxm估计y带来的误差。特征xi可以是连续变量,也可以是离散变量,如性别、基因型等。
求解线性回归的最基本方法就是最小二乘法,即求使各样本残差的平方和达到最小的系数βi。这实际是在变量y服从正态分布假设下的最大似然估计最大似然估计。(可作为习题留给读者练习)
系数βi的直观解释是,当其他因素都不变时,特征xi增加一个单位所带来的y的变化。由于多元线性回归能够把特征的作用量化,在很多根据观测数据研究未知机理的问题里有很广泛的应用。
在模式识别问题中,所关心的量是分类,例如是否会患某种疾病,这时就不能再用简单的线性回归的方法来研究特征与分类之间的关系。
人们观察到,现实世界里有很多这样的情况,就是某个因素对于事物性质的影响是按比例渐进的:  设x∈R是样本的特征(例如体重指数),考查样本是否属于所关心类别(如患有某种疾病),我们很难建立患病(y=1)或不患病(y=-1)与x的关系,但却经常可以发现x与人群中患病概率的关系符合图510的Logistic函数所示的形式,即

P(y=1|x)=ew0+w1x1+ew0+w1x
(576)



图510Logistic函数


其中P(y=1|x)经常简记作P(y|x)。这种函数被称作罗杰斯特函数,在神经网络中被称作Sigmoid函数。人们经常用θ(s)来代表罗杰斯特函数,即

θ(s)=es1+es=11+e-s
(577)

容易证明,

θ(-s)=1-θ(s)
(578)


在医学研究中,人们经常关心一个称作“几率几率”(odds)的概念,指患某种疾病的可能性与不患病的可能性之比。如果患病概率符合Logistic函数,则几率为


P(y|x)1-P(y|x)=ew0+w1x(579)


对它取自然对数,得到对数几率(log odds) 


lnP(y|x)1-P(y|x)=w0+w1x(580)


公式左边被称作P(y|x)的logit函数。变量y与x之间的这种关系模型称作logistic模型,其中的w1反映了当x增加一个单位时,样本属于y=1类的几率在对数尺度上增加的幅度。
正如线性回归中一样,logistic模型也可以有多个自变量x1,…,xm,即样本x是由m维特征组成的,这些特征可以是连续特征,也可以是离散特征。
多元的logit函数是


logit(x)=lnP(y|x)1-P(y|x)=w0+w1x1+…+wmxm(581)


样本属于y=1类的概率是


P(y|x)=ew0+w1x1+…+wmxm1+ew0+w1x1+…+wmxm(582)


罗杰斯特回归罗杰斯特回归(Logistic regression)就是用式(581)的对数几率模型,即式(582)的概率模型来描述样本属于某类的可能性与样本特征之间的关系,用训练数据来估计式(582)中的系数。得到这些系数后,罗杰斯特回归的决策函数是 


若logit(x)00,则x∈ω1
x∈ω2(583)


罗杰斯特回归最基本的学习算法是最大似然法。
设共有N个独立的训练样本{(x1,y1),…,(xN,yN)},xj∈Rd+1,yj∈{-1,1},其中y=1表示样本属于所关心类别,y=-1表示不属于。我们假设样本的类别是从某个未知的概率f(x)中产生出来的,以概率f(x)属于所关心类别,以概率1-f(x)不属于该类,即

P(y|x)=f(x),y=+1


1-f(x),y=-1
(584)

用罗杰斯特函数h(x)=θ(wTx)来估计f(x),其中w是罗杰斯特函数中待求参数组成的向量。
对于样板集中的一个样本实例(xj,yj),xj和yj都是已知的,而概率模型h(x)未知,于是下面的概率就度量了该已经发生的样本是从该未知的模型中产生出来的可能性:  

P(yj|xj)=h(xj),yj=+1


1-h(xj),yj=-1
(585)

称作模型h在样本上的似然函数。
注意到θ(-s)=1-θ(s),我们可以把上式的两种情况合并在一起,并记作l(·),即

l(h|(xj,yj))P(yj|xj,h)=θ(yjwTxj)
(586)

它是模型h在样本(xj,yj)上的似然函数。
对于样本集中所有的样本,模型的似然函数是

L(w)=∏Nj=1P(yj|xj)=∏Nj=1θ(yjwTxj)
(587)

这里,我们把似然函数显式地写成模型中未知参数w的函数。罗杰斯特回归就是要用训练样本集来估计参数w,使样本集是从这个模型中产生出来的可能性最大。
我们可以沿用在感知器和最小平方误差方法中的策略,用梯度下降的方法来最优化目标函数。为此,我们定义目标函数为似然函数的负对数,优化问题是

minE(w)=-1Nln(L(w))=-1Nln∏Nj=1θ(yjwTxj)
=1N∑Nj=1ln 1θ(yjwTxj)
=1N∑Nj=1ln1+e-yjwTxj(588)


于是,我们得到下面的采用梯度下降法寻优的罗杰斯特回归算法:  
(1) 记时刻为k=0,初始化参数w(0)。
(2) 计算目标函数的负梯度方向

E=-1N∑Nj=1yjxj1+eyjw(k)Txj


按步长(学习率)η更新下一时刻参数

w(k+1)=w(k)-ηE


检查是否达到终止条件,如未达到,令k=k+1,重新进行(2)。
(3) 算法停止,输出得到的参数w。
其中终止条件可以是似然函数的梯度已经小于某个预设值,训练过程不再有显著更新,或者是迭代达到预设的上限,等等。
5.8最优分类超平面与线性支持向量机

5.8最优分类超平面与线性支持向量机

现在再回到线性可分情况。容易发现,只要一个样本集线性可分,就肯定存在无数多解,解区中的任何向量都是一个解向量。感知器算法采用不同的初始值和不同的迭代参数就会得到不同的解。如图511所示,在这些解中,哪一个更好呢?


图511线性可分线性可分情况下的多解性


5.8.1最优分类超平面
对于图511中的例子,如果要求手动画出一条分类线,多数人会倾向于画在两类的中间,大约线AB的位置上,因为这条分类线离两类样本都最远。下面来形式化地定义这样的分类线(面)。这里我们使用原始的样本向量表示而不采用增广向量。
假定有训练样本集

(x1,y1),(x2,y2),…,(xN,yN),xi∈Rd,yi∈{+1,-1}(589)

其中每个样本是d维向量,y是类别标号,ω1类用+1表示,ω2类用-1表示。这些样本是线性可分的,即存在超平面

g(x)=(w·x)+b=0(590)

把所有N个样本都没有错误地分开。这里,w∈Rd是线性判别函数的权值,b是其中的常数项,在前面几小节中都用w0表示,而这里为了与其他有关支持向量机的文献一致,我们用b来表示。(w·x)表示向量w与x的内积,即wTx。


图512分类间隔分类间隔与最优超平面

定义:  一个超平面,如果它能够将训练样本没有错误地分开,并且两类训练样本中离超平面最近的样本与超平面之间的距离是最大的,则把这个超平面称作最优分类超平面(optimal separating hyperplane),简称最优超平面最优超平面(optimal hyperplane)。两类样本中离分类面最近的样本到分类面的距离称作分类间隔(margin),最优超平面也称作最大间隔超平面,如图512所示。


最优超平面定义的分类决策函数为 

f(x)=sgn(g(x))=sgn((w·x)+b)(591)

其中,sgn(·)为符号函数,当自变量为正值时函数取值为1,自变量为负值时函数取值为-1。
根据5.3节的基本知识我们知道,向量x到分类面g(x)=0的距离是|g(x)|/‖w‖,其中‖w‖是权向量的模,即‖w‖=(w·w)1/2。
容易注意到,对于式(592)的决策函数,对权值w和b作任何正的尺度调整都不会影响分类决策,同时也不会改变样本到分类面的距离,因此上面定义的最优分类面没有唯一解,而是有无数多个等价的解。为了使这一问题有唯一解,需要把w和b的尺度确定下来。
所有N个样本都可以被超平面没有错误地分开,就是要求所有样本都满足

(w·xi)+b>0,yi=+1


(w·xi)+b<0,yi=-1(592)

既然尺度可以调整,我们可以把式(591)的条件变成

(w·xi)+b≥1,yi=+1


(w·xi)+b≤-1,yi=-1(593)

即要求第一类样本中g(x)最小等于1,而第二类样本中g(x)最大等于-1。把样本的类别标号y值乘到不等式(593)中,可以把两个不等式合并成一个统一的形式: 

yi[(w·xi)+b]≥1,i=1,2,…,N(594)

用此条件约束分类超平面的权值尺度变化,这种超平面称作规范化的分类超平面(the canonical form of the separating hyperplane)。g(x)=1和g(x)=-1就是过两类中各自离分类面最近的样本且与分类面平行的两个边界超平面。


图513规范化的最优分类面


如图513所示,由于限制两类离分类面最近的样本的g(x)分别等于1和-1,那么分类间隔就是M=2‖w‖。于是,求解最优超平面的问题就成为 

minw,b12‖w‖2(595)

s.t.yi[(w·xi)+b]-1≥0,i=1,2,…,N(596)

这是一个在不等式约束下的优化问题,可以通过拉格朗日法求解。对每个样本引入一个拉格朗日系数

αi≥0,i=1,…,N(597)

可以把式(572)和式(573)的优化问题等价地转化为下面的问题 

minw,bmaxα L(w,b,α)=12(w·w)-∑Ni=1αi{yi[(w·xi)+b]-1}(598)

式中的L(w,b,α)是拉格朗日泛函,式(595)、式(596)的解等价于式(598)对w和b求最小、而对α求最大,最优解在L(w,b,α)的鞍点上取得,如图514所示。


图514鞍点示意图



在式(598)的鞍点处,目标函数L(w,b,α)对w和b的偏导数都为零,由此我们可以得到,对最优解处,有

w*=∑Ni=1α*iyixi(599)

且

∑Ni=1yiα*i=0(5100)

将这两个条件代入拉格朗日泛函中可以得到,式(595)、式(596)的最优超平面问题的解等价于下面的优化问题的解

maxαQ(α)=∑Ni=1αi-12∑Ni,j=1αiαjyiyj(xi·xj)(5101)

s.t.∑Ni=1yiαi=0(5102)

且

αi≥0,i=1,…,N(5103)

这是一个对αi,i=1,…,N的二次优化问题,称作最优超平面的对偶问题对偶问题(the dual problem),而式(595)、式(596)的优化问题称作最优超平面的原问题原问题(the primary problem)。通过对偶问题的解α*i,i=1,…,N,可以求出原问题的解 

w*=∑Ni=1α*iyixi(5104)

f(x)=sgn{g(x)}=sgn{(w*·x)+b}=sgn{∑Ni=1α*iyi(xi·x)+b*}(5105)

即,最优超平面的权值向量等于训练样本以一定的系数加权后进行线性组合。
应注意到,在判别函数式(5105)中的b*尚没有得到。现在来看b*的求解问题。
根据最优化理论中的库恩塔克(KuhnTucker)条件,式(598)中的拉格朗日泛函的鞍点处满足

αiyi[(w·xi)+b]-1=0,i=1,2,…,N(5106)
再考虑到式(596)和式(597),可以看到,对于满足式(596)中大于号的样本,必定有αi=0。而只有那些使式(596)中等号成立的样本所对应的αi才会大于0。这些样本就是离分类面最近的那些样本,从图513中可以看到,是这些样本决定了最终的最优超平面的位置; 在式(5104)和式(5105)的加权求和中,实际也只有这些αi>0的样本参与求和。这些样本被称作支持向量支持向量(support vectors),它们往往只是训练样本中的很少一部分。
对于这些支持向量来说,有

yi[(w*·xi)+b*]-1=0(5107)

因为已经求出了w*,所以b*可以用任何一个支持向量根据式(5107)求得。在实际的数值计算中,人们通常采用所有αi非零的样本用式(5107)求解b*后再取平均。
最优超平面的思想是苏联学者Vapnik和Chervonenkis在20世纪70年代提出的Vapnik V N,Chervonenkis A Ja.Theory of Pattern Recognition[俄文版].Nauka,Mosco,1974.,20世纪90年代由美国AT&T贝尔实验室Vapnik领导的小组对其进行了进一步发展,从20世纪90年代末开始在国际上迅速得到重视。由于最优超平面的解最后是完全由支持向量决定的,所以这种方法后来被称作支持向量机支持向量机(support vector machines),通常被简写为SVM或SV机。
这里介绍的只是线性可分情况下的线性支持向量机,更复杂的情况将在5.8.3节和第6章进一步介绍。
对比5.5节中的感知器算法,我们也可以把最优超平面等价地看作是在限制权值尺度的条件下求余量的最大化。感兴趣的读者可以自己尝试分析这一关系。
5.8.2大间隔与推广能力
5.8.1节从直观分析出发定义了最优超平面,即最大间隔分类超平面。那么,一个问题是,这样定义的超平面真的是最优吗?在什么意义下是最优的?在第7章中我们将介绍统计学习理论的核心思想和结论。由于一部分读者可能不需要掌握统计学习理论所涉及的理论内容,为了适应不同读者的需要,在本小节中,我们根据统计学习理论对这一问题进行简要说明。
从第1章的讨论已经知道,模式识别是一种基于数据的机器学习,学习的目的不仅是要对训练样本能够正确分类,而是要能够对所有可能的样本正确分类,这种能力叫做推广推广(generalization)。在线性可分情况下,我们用感知器算法(或其他算法)可以得到无数多种可能的解,它们都可以是训练误差为0,我们要追求的最优解应该是这些解中推广能力最大的解。
对于某个样本x,其真实的类别为y,我们要用判别函数f(x,w)来估计y,定义这种估计带来的损失是L(y,f(x,w)),这里为了强调权值参数w对最后损失的影响,我们把它写为判别函数的自变量之一。那么,在某个w下对所有训练样本的分类决策损失就是

Remp(w)=1N∑Ni=1L(yi,f(xi,w))(5108)

称作经验风险经验风险。线性可分情况下,通过感知器算法,已经能使经验风险达到零。
但是,我们真正关心的是在权值w下未来所有可能出现的样本的错误率或风险,即

R(w)=∫L(y,f(x,w))dF(x,y)(5109)

称作期望风险。其中,F(x,y)表示所有可能出现的样本及其类别的联合概率模型。对比式(5108)和式(5109)可以知道,经验风险只是在给定的训练样本上对期望风险的估计。
那么,这样的估计准确吗?在多个使经验风险为0的解中,如何才能找到使期望风险最小的解?
由Vapnik等提出和发展的统计学习理论系统地回答了这一问题。
统计学习理论指出,有限样本下,经验风险与期望风险是有差别的,期望风险可能大于经验风险,但它们之间满足下面的规律 

R(w)≤Remp(w)+φhN(5110)

其中,φ(h/N)称作置信范围,它与样本数N成反比,而与一个重要的参数h成正比。这个参数h是依赖于模式识别算法的设计的,称作VC维VC维(VC Dimension),它反映了所设计的学习机器(函数集)的复杂性,确切的定义请参考第7章和Vapnik所著的《统计学习理论的本质》或《统计学习理论》。
式(5110)给出了有限样本下期望风险的上界。它告诉我们,在训练误差相同的情况下,学习机器的复杂度越低(VC维越低),则期望风险与经验风险的差别就越小,因而学习机器的推广能力就越好。
在线性可分的问题中,我们能得到很多使Remp(w)为0的解,要使方法有最好的推广能力,就应该设法使φ(h/N)最小。由于训练样本集是给定的,即N固定,能够调整的是算法的VC维。
统计学习理论中的另一个重要的结论是,对于规范化的分类超平面,如果权值满足‖w‖≤A,那么这种分类超平面集合的VC维有下面的上界

h≤min[R2A2],d+1(5111)

其中,R2是样本特征空间中能包含所有训练样本的最小超球体的半径,d是样本特征的维数。对于给定的样本集,这两项均是确定的。在求最大间隔分类超平面时,最大化分类间隔也就等价于最小化A2,实际上是使VC维上界最小。根据式(5110),这样就是试图使期望风险的置信范围尽可能小,即在经验风险都最小化为0的情况下追求期望风险的上界的最小化。
因此,支持向量机中最大分类间隔的准则,是为了通过控制算法的VC维实现最好的推广能力。在这个意义下,所得的分类超平面是最优的。
5.8.3线性不可分情况
前面我们只讨论了线性可分情况下的最优超平面。线性不可分的情况下,上面定义的最优超平面不存在。本节我们来分析如何在这种情况下定义和求解支持向量机。
样本集不是线性可分,就是说对样本集

(x1,y1),(x2,y2),…,(xN,yN),xi∈Rd,yi∈{+1,-1}(5112)

不等式

yi[(w·xi)+b]-1≥0,i=1,2,…,N(5113)

不可能被所有样本同时满足。
假定某个样本xk不满足式(5113)的条件,即yk[(w·xk)+b]-1<0,那么总可以在不等式的左侧加上一个正数ξk,使得新的不等式yk[(w·xk)+b]-1+ξk≥0成立。
从这个思路出发,对每一个样本引入一个非负的松弛变量ξi,i=1,…,N,就可以把式(5113)的不等式约束条件变为

yi[(w·xi)+b]-1+ξi≥0,i=1,2,…,N(5114)

如果样本xj被正确分类,即yj[(w·xj)+b]-1≥0,则ξj=0; 而如果有一个错分样本,则这个样本对应的yj[(w·xj)+b]-1<0,对应的松弛变量ξj>0。

所有样本的松弛因子之和∑Ni=1ξi可以反映在整个训练样本集上的错分程度,错分样本数越多,则∑Ni=1ξi越大; 同时,如果样本错误的程度越大(在错误的方向上远离分类面),则∑Ni=1ξi也越大。显然,我们希望∑Ni=1ξi尽可能小。因此,可以在线性可分情况下的目标函数12‖w‖2上增加对错误的惩罚项,定义下面的广义最优分类面广义最优分类面的目标函数 

minw,b12(w·w)+C∑Ni=1ξi(5115)

这个目标函数反映了我们的两个目标:  一方面希望分类间隔尽可能大(对于分类正确的样本来说),另一方面希望错分的样本尽可能少且错误程度尽可能低。参数C是一个常数,反映在这两个目标之间的折中。(注意,这里样本被错分的定义不是yj[(w·xj)+b]<0,而是yj[(w·xj)+b]-1<0,即第一类样本只要g(x)小于1就算作错误,第二类样本只要g(x)大于-1就算作错误。)
C是一个需要人为选择的参数。通常,如果选择较小的C,则表示对错误比较容忍而更强调对于正确分类的样本的分类间隔; 相反,若选择较大的C,则更强调对分类错误的惩罚。实际应用中,如果样本线性可分,则C的大小只是影响算法的中间过程而不影响最后结果,因为∑Ni=1ξi最终会为0。在线性不可分情况下,有时需要试用不同的C来达到更理想的结果。
下面把引入松弛因子后的广义最优分类面问题正式表述如下:  在给定训练样本集

(x1,y1),(x2,y2),…,(xN,yN),xi∈Rd,yi∈{+1,-1}(5116)

的情况下,求解

minw,b,ξi12(w·w)+C∑Ni=1ξi(5117)

s.t.yi[(w·xi)+b]-1+ξi≥0,i=1,2,…,N(5118)


且
 ξi≥0,i=1,2,…,N(5119)

与线性可分情况下的最优分类面类似,可以把这个问题转化为以下拉格朗日泛函的鞍点问题 

minw,b,ξimaxα L(w,b,α)=12(w·w)+C∑Ni=1ξi-∑Ni=1αiyi(w·xi)+b-1+ξi-∑Ni=1γiξi(5120)

其中,αi≥0,γi≥0是对应式(5118)和式(5119)的拉格朗日乘子。
同样,把式(5120)的拉格朗日泛函分别对w、b、ξi求导并令其为0。经过一些简单的推导(读者可以作为课后练习),可以得到广义最优分类面的对偶优化问题

maxα Q(α)=∑Ni=1αi-12∑Ni,j=1αiαjyiyj(xi·xj)(5121)

s.t.∑Ni=1yiαi=0(5122)

且


0≤αi≤C,i=1,…,N(5123)

原问题中的解向量满足 

w*=∑Ni=1α*iyixi(5124)

广义最优分类面的判别函数是

f(x)=sgn{g(x)}=sgn{(w*·x)+b}=sgn∑Ni=1α*iyi(xi·x)+b*(5125)

我们注意到,对偶问题式(5121)~式(5123)与线性可分情况下最优分类面的对偶问题式(5101)~式(5103)几乎相同,唯一不同的是在对αi的约束条件式(5123)中比式(5103)多了一个上界C。
根据库恩塔克条件库恩塔克条件,式(598)的鞍点满足以下两套条件 

αi{yi[(w·xi)+b]-1+ξi}=0,i=1,2,…,N(5126)

γiξi=(C-αi)ξi=0,i=1,2,…,N(5127)

从式(5127)可以得到,只有对拉格朗日乘子达到上界αi=C的样本才有ξi>0,它们是被错分的样本(包括在两条平行的边界面之间的样本),其余样本对应的ξi=0。
而从式(5126)得到,多数的αi仍为0,只有

yi[(w·x)+b]-1+ξi=0(5128)


的样本才会使αi>0。这些样本又分为两种情况,一种是分类正确但处在分类边界面上的样本,它们的0<αi<C,ξi=0; 另外一种则是分类错误的样本,它们的αi=C,ξi>0。可以用其中0<αi<C的样本来通过式(5128)求得b。


图515线性不可分情况下的广义最优分类面及其中的支持向量



需要说明的是,这两部分αi>0的样本都是支持向量,但其含义与线性可分情况下已经不同。在某些文献里,把那些0<αi<C的支持向量叫做边界向量(margin vectors)。图515中给出了两种不同的支持向量的例子。

由于广义最优分类面可以兼容线性可分情况下的最优分类面,所以人们通常采用的支持向量机都是考虑广义最优分类面的形式。
考查式(5101)~式(5103)和式(5121)~式(5123)的优化问题,可以发现目标函数式(5101)、式(5121)中只有αi的二次项和一次项,这是一个对αi,i=1,…,N在等式和不等式约束下的二次优化问题,具有唯一的极值点。关于具体的解法将在第6章介绍非线性的支持向量机后作简略介绍。
5.9多类线性分类器

5.9多类线性分类器

在前几节中讨论的都是两类的分类问题。在很多实际应用中,经常会面对多类的分类问题,例如在手写数字识别中,面对的是0~9十类。
解决多类分类问题有两种基本思路,一种方法是把多类问题分解成多个两类问题,通过多个两类分类器实现多类的分类; 另一种方法是直接设计多类分类器。本节中我们讨论这两种多类分类方法中有代表性的线性方法。
5.9.1多个两类分类器的组合
假如要解决0、1、2、3、4、5、6、7、8、9这十个数字的识别问题,可以设计多个两类的分类器,例如,第一个分类器把“0”和其他数字分开,第二个分类器把“1”和其他数字分开……以此类推; 或者,也可以这样设计多个两类分类器:  用九个分类器分别把“0”和“1”、“0”和“2”、…、“0”和“9”分开,再用八个分类器分别把“1”和“2”、“1”和“3”、…、“1”和“9”分开……以此类推。这两种做法都可以最终实现把0~9十个数字分开,它们代表了用多个两类分类器构造多类分类器的两种典型的做法。
第一种做法叫做“一对多一对多”的做法,英文可以叫onevsrest或者oneoverall。假设共有c个类,ω1,ω2,…,ωc,我们共需要c-1个两类分类器就可以实现c个类的分类。
但是,这种做法可能会遇到两方面的问题。一个问题是,假如多类中各类的训练样本数目相当,那么,在构造每个一对多的两类分类器时会面临训练样本不均衡的问题,即两类训练样本的数目差别过大。虽然很多分类器算法并没有要求两类样本均衡,但是有些算法却可能会因为样本数目过于不均衡而导致分类面有偏,例如使得多数错误发生在样本数小的一类上。这在实际应用时需要注意,如果出现类似情况需要对算法采取适当的修正措施。
另一个问题是,用c-1个线性分类器来实现c类分类,就是用c-1个超平面来把样本所在的特征空间划分成c个区域,一般情况下,这种划分不会恰好得到c个区域,而是会多出一些区域,而在这些区域内的分类会出现歧义,如图516(a)中的阴影部分所示。


图516用多个两类分类器实现多类划分时可能出现的歧义区



第二种做法是对多类中的每两类构造一个分类器,称作“逐对”(pairwise)分类。考虑到把ωi和ωj分开与把ωj和ωi分开相同,对于c个类别,共需要c(c-1)2个两类分类器。显然,这种做法要比一对多的做法多用很多两类分类器。但是,逐对分类逐对分类不会出现两类样本数过于不均衡的问题,而且决策歧义的区域通常要比一对多分类器小,如图516(b)中阴影部分所示。
在这里的讨论中,我们没有涉及具体的两类分类器是什么,只是假定每个分类器给出样本属于两类中任意一类的决策。实际上,很多分类器在最后的分类决策前得到的是一个连续的量,分类是对这个量用某个阈值划分的结果,例如所有线性分类器都是最后转化为一个线性判别函数g(x)=wTx+w0与某一阈值(通常是0)比较的问题。SVM也是这样一种分类器。在很多线性分类器中,一个正确分类的样本,如果它离分类面越远,则往往对它的类别判断就更确定,因此可以把分类器的输出值看作对样本属于某一类别的一种打分,如果分值大于零(或其他阈值)则判断样本属于该类,而且分值越高对此分类越确信,反之决策不属于该类。
利用这种分类器,可以用c个一对多的两类分类器来构造多类分类系统,即每个类别对应一个分类器,其输出是对样本是否属于ωi类给出一个判断。在多类决策时,如果只有一个两类分类器给出了大于阈值的输出,而其余分类器输出均小于阈值,则把这个样本分到该类。更进一步,如果各个分类器的输出是可比的,而且根据类别的定义知道任意样本必定属于且仅属于c个类别中的一类,那么可以在决策时直接比较各个分类器的输出,把样本赋予输出值最大的分类器所对应的类别。(但是需要注意,对很多分类器来说,如果它们是分别训练的,其输出值之间并不一定能保证可比性,在实际应用时需根据具体情况仔细分析。)


图517用多个两类SVM实现多类分类的例子Ramaswamy S,et al..Multiclass cancer diagnosis using tumor gene expression signatures.PNAS,2001,98(26):  1514915154.



图517给出了一个生物信息学生物信息学中用多个SVM对基因芯片基因芯片数据进行多种癌症的分类的例子注意,由于在SVM训练中要调整w的尺度以达到间隔最大,且保证离分类面最近的样本的输出值是1,对不同的两类问题训练后的尺度并非完全相同。因此,这样得到的多个SVM的输出值之间严格来说并不能直接进行绝对值比较,只是g(x)的符号有可比性。但是,在这个例子里,各个分类器间的尺度差别并不明显,所以直接使用多个SVM的输出进行比较就可以得到较好的效果。一般情况下,对于根据多个支持向量机的输出值来进行多类决策,还有一些理论问题需要进一步研究。。在这个例子中,有14类癌症的基因表达数据,包括乳腺癌、肺癌、直肠癌、前列腺癌,等等。为了把这14类分开,他们对每一类癌症建立一个线性SVM分类器,把这类癌症与其他种类的癌症分开。这样共得到14个SVM分类器。在测试时,用这14个分类器分别对测试样本进行分类,哪个分类器给出最大的输出则把测试样本归到哪一类②。


图518用二叉树把多类分类问题
分解成多个两类问题


除了以上两种划分方法,对于某些多类问题,如果人们对所研究的类别有较好的认识,能够根据类别间的内在关系把它们分级合并成多个两类分类问题,则可以用类似图518所示的二叉树来构建多个两类分类器。例如假如我们的目标是分出a、b、c、d、e、f六个类,如果发现这些类别的概念间有内在的关系,例如e、f两个类关系比较紧密,同属于一个更高层次的概念,c、d同属于一个概念,b和c、d又关系比较紧密,等等,则可以把问题分解成{a}对{b,c,d,e,f}、{b,c,d}对{e,f}、{b}对{c,d}、{c}对{d}、{e}对{f}这五个两类分类问题。
5.9.2多类线性判别函数
所谓多类线性判别函数,是指对c类设计c个判别函数

gi(x)=wTix+wi0,i=1,2,…,c(5129)

在决策时哪一类的判别函数最大则决策为哪一类,即

若gi(x)>gj(x),j≠i,则x∈ωi(5130)

当然,我们也可以把这些判别函数表示成增广向量的形式 

gi(x)=αTiy,i=1,2,…,c(5131)

其中,αi=wi
wi0为增广权向量。
多类线性判别函数也称为多类线性机器多类线性机器,可以记作L(α1,α2,…,αc)。
与上面讨论的用多个两类分类器进行多类划分的方法相比,多类线性机器可以保证不会出现有决策歧义的区域,如图519所示。


图519多类线性机器



与两类情况下的感知器算法相同,这里首先考虑多类线性可分情况,即存在一个线性机器能够把所有样本都正确分类的情况。在这种情况下,可以用与感知器算法类似的单样本修正法来求解线性机器。具体算法如下:  
(1) 任意选择初始的权向量αi(0),i=1,2,…,c,置t=0。
(2) 考查某个样本yk∈ωi,若αi(t)Tyk>αj(t)Tyk,则所有权向量不变; 若存在某个类j,使αi(t)Tyk≤αj(t)Tyk,则选择αj(t)Tyk最大的类别j,对各类的权值进行如下的修正


αi(t+1)=αi(t)+ρtyk

αj(t+1)=αj(t)-ρtyk

αl(t+1)=αl(t),l≠i,j(5132)

ρt是步长,必要时可以随着t而改变。
(3) 如果所有样本都分类正确,则停止; 否则考查另一个样本,重复(2)。
这一算法被称作逐步修正法逐步修正法(incremental correction)。可以证明,如果样本集线性可分,则该算法可以在有限步内收敛于一组解向量。
与感知器算法一样,当样本不是线性可分时,这种逐步修正法不能收敛,人们可以对算法作适当的调整而使算法能够停止在一个可以接受的解上,例如通过逐渐减小步长而强制使算法收敛。
同样,也可以像在感知器算法中那样引入余量,即把αi(t)Tyk>αj(t)Tyk变为αi(t)Tyk>αj(t)Tyk+b。
很多其他的两类分类算法都可以发展出相应的多类分类算法,但其中多数在实际中的应用并不广泛,所以在此不做更多介绍。在后面两章里还会看到更多的可以用于多类分类的算法。
5.9.3多类罗杰斯特回归与软最大
在5.7节中讨论的罗杰斯特回归问题,所考虑的实际上是样本属于所关心的类和不属于所关心的类的问题。这个思路可以方便地推广到多类情况,对每一类考虑样本是否属于它。在这个视角下,式(5133)的罗杰斯特函数

P(y=1|x)=ew0+w1x1+ew0+w1x
(5133)

的分子可以看作是对样本属于该类的可能性的度量,而分母的作用则是把这个可能性归一化为概率。
把这个思路推广到多类情况,我们可以把模型设为样本属于每一类j都与一个参数为wj的指数判别函数成正比,即

P(y=j|x)∝ewj·x

用样本属于全部c个类别的判别函数做归一化,就得到

P(y=j|x)=ewj·x∑ck=1ewk·x,j=1,…,c
(5134)


这个归一化指数函数在机器学习领域中被称作软最大(Softmax)函数,就是对样本的多类罗杰斯特回归。可以采用与两类罗杰斯特回归类似的思路用最大似然法求解。在第12章介绍深度学习时,我们还会看到软最大函数在多种深度神经网络中的应用。
5.10讨论

5.10讨论

线性判别函数是形式最简单的判别函数。它虽然算法简单,但是在一定条件下能够实现或逼近最优分类器的性能,因此在很多实际问题中得到了广泛的应用。而且,在很多情况下,虽然所研究的问题可能并不是线性的,但是由于我们所拥有的样本数目有限,或者样本观测中有较大噪声,我们可能仍然会使用线性分类器。这不但是一种在特定条件下追求“有限合理”解的妥协方案,更重要的是,在一些情况下,线性分类器可能比更复杂的模型取得更好的结果,尤其是更好的推广能力。
世界是非线性的,但很多情况下可以用线性来近似。
毕竟还有很多情况需要采用更复杂的非线性方法。在第6章我们将看到,很多非线性方法是以本章介绍的线性方法为基础发展起来的。例如,利用解决多类分类的思路可以设计多个分类器,用分段线性来逼近非线性; 在本章中看到的最基本的感知器算法,就是一种最简单的人工神经元,人工神经网络中的多层感知器算法就是建立在它的基础上的; 通过引入广义线性判别函数广义线性判别函数,可以把很多线性方法映射为非线性方法,而非线性的支持向量机则是通过用核函数的方法来实现广义线性判别函数。