线性得分计算公式

分类的线性⽅法

分类的线性⽅法(PRML4.*、ESL4.*)

在本章中，我们考虑分类的线性模型。所谓分类线性模型，是指决策⾯是输⼊向量x的线性函数，因此被定义为D维输⼊空间中的(D-1)维超

平⾯。

Prmlesl中的线性分类模型涉及到

指⽰矩阵线性回归模型

线性判别分析(LDA)

Logistic回归

分离超平⾯

指⽰矩阵的线性回归模型

⽅法:

⽤线性回归模型拟合类指⽰变量,并分类到最⼤拟合(esl定义)

指⽰变量编码:

如果类别有K个,⽤1-of-K编码⽅式

例如每⼀个xn的响应(类别)变量表⽰为tn=(0,0,0,…,0,1,0)

每个类别Ck由⾃⼰的线性模型描述，即

其中k=1;:::;K。使⽤向量记号，我们可以很容易地把这些量聚集在⼀起表⽰，即

我们现在通过最⼩化平⽅和误差函数来确定参数矩阵~W

，

令上式关于~W的导数等于零，整理，可以得到~W的解，形式为

其中~X^⼗字是矩阵~X的伪逆矩阵，正如3.1.1节讨论的那样。这样我们得到了判别函数，形式为

但是这个模型有⼀些问题:

最⼩平⽅解对于离群点缺少鲁棒性,平⽅和误差函数惩罚了"过于正确"的预测.

但是，最⼩平⽅⽅法的问题实际上⽐简单的缺乏鲁棒性更加严重，如图4.5所⽰。这幅图给出了⼆维空间(x1;x2)中，来⾃三个类别的⼈⼯⽣

成的数据。线性决策边界能够将数据点完美地分开。实际上，在本章的后⾯将要介绍的逻辑回归⽅法可以给出⼀个令⼈满意的解，如右侧的

图所⽰。然⽽，最⼩平⽅⽅法给出的结果相当差，输⼊空间中只有⼀个相当⼩的区域被分给了绿⾊的类别。

由上图左边图可以看出,线性回归模型试图拟合阶梯型0-1函数,⼜因为每⼀类的得分之和必须为1,因此拟合结果为上图左边.这就使得在图4.2

左边处于中间位置的数据团(当其数量不是很多时)拟合的直线(图4.3左中的绿⾊直线)位置偏下(数据量少,概率低),因此"不占⽀配地位,被屏蔽."

(esl)

(上图中的阶梯型函数就是线性回归模型需要拟合的⽬标曲线).

最⼩平⽅⽅法的失败并不让我们感觉惊讶。回忆⼀下，最⼩平⽅⽅法对应于⾼斯条件分布假设下的最⼤似然法，⽽⼆值⽬标向量的概率分布

显然不是⾼斯分布。通过使⽤更恰当的概率模型，我们会得到性质⽐最⼩平⽅⽅法更好的分类⽅法。

线性判别分析

模型定义

由分类的判定理论(esl2.4)可知,为了最优分类,我们需要知道后验概率P(G|X).设f_k(x)是类G=k中X的类条件密度,⽽pi_x是类k的先验,并且

sum_k(pi_k)=1.贝叶斯定理的简单应⽤给出:

我们看到,从分类能⼒将,有了f_k(x)⼏乎等价于有了P(G=k|X=x).

许多技术都是基于类密度的模型:

有上⾯可以看出,LDA是基于⾼斯,其次假设每⼀类的协⽅差矩阵相同.

LDA与QDA

⼆次判别式则去掉协⽅差相同的假设,因此上述的判别函数含有⼆次项.

LDA与QDA的⽐较着重考虑参数多少(LDA参数少,QDA参数较多)

LDA的计算

降秩线性判别分析(Fisher线性判别函数)

迄今为⽌,LDA作为⼀种受限的⾼斯分类法,他的流⾏部分因为附加的限制允许我们观察数据的富含信息的低维投影.

P维输⼊的k个形⼼在⼀个⼩于等于K-1维的仿射⼦空间中.如果p很⼤,则可以相当可观的降维.此外,为了去顶最近的形⼼,我们可以忽略正交于

⼦空间的距离.这样,便可以把X^*投影到这个形⼼⽣成的⼦空间中H_(k-1),并在那⾥做距离⽐较.

这样,LDA存在⼀个基本的维归约,即最多需要在K-1维⼦空间上考虑数据.

K-1维只是k个类分开的⼦空间维度的上限.即K个类最多存在于⼀个K-1维空间中.K个类也可能存在于⼀维直线上.

如果K>3会怎样?我们可以寻找某个L<=K-1⼦空间H_L,使得它在某种意义下(loss)对LDA是最佳的.

Fisher定义最佳的含义是投影后的形⼼在⽅差意义下尽可能分散.

实际上,Fisher准则根据类间⽅差与类内⽅差的⽐值定义:

我们可以使⽤公式（4.20）、公式（4.23）和公式（4.24）对这个式⼦重写，显式地表达出J(w)对w的依赖。

对公式J(W)关于w求导，我们发现J(w)取得最⼤值的条件为

(4.29)

根据公式S_B，我们看到S_B*w总是在(m2-m1)的⽅向上。更重要的是，我们不关⼼w的⼤⼩，只关⼼它的⽅向，因此我们可以忽略标量因

⼦(wTSBw)和(wTSWw)。将公式（4.29）的两侧乘以S_w^-1，我们有

(4.30)

注意，如果类内协⽅差矩阵是各向同性的，从⽽SW正⽐于单位矩阵，那么我们看到w正⽐于类均值的差。公式(4.30)的结果被称为Fisher线

性判别函数（Fisherlineardiscriminant），虽然严格来说它并不是⼀个判别函数，⽽是对于数据向⼀维投影的⽅向的⼀个具体选择。

对于多类:

类内协⽅差矩阵可以使⽤公式

其中Nk是类别Ck中模式的数量。为了找到类间协⽅差矩阵的推⼴，我们使⽤DudaandHart（1973）的⽅法，⾸先考虑整体的协⽅差矩阵

整体的协⽅差矩阵可以分解为公式（4.40）和公式（4.41）给出的类内协⽅差矩阵，加上另⼀个矩阵SB，它可以看做类间协⽅差矩阵。

(4.44)

与之前⼀样，我们想构造⼀个标量，当类间协⽅差较⼤且类内协⽅差较⼩时，这个标量会较⼤。有许多可能的准则选择⽅式（Fukunaga,

1990）。其中⼀种选择是:

这个判别准则可以显式地写成投影矩阵W的函数，形式为

最⼤化这个判别准则是很直接的，虽然有些⿇烦。详细的推导可以参考Fukunaga（1990）。权值由SW^-1SB的特征向量确定，它对应了

D′个最⼤的特征值。再从数学上看下为什么只有K-1维⼦空间必需.值得强调的时，有⼀个重要的结果对于所有的这些判别准则都成⽴。⾸

先，根据公式SB，SB由K个矩阵的和组成，每⼀个矩阵都是两个向量的外积，因此秩等于1。此外，由于公式（4.44）给出的限制条件，这

些矩阵中只有(K-1)个是相互独⽴的。因此SB的秩最⼤等于(K-1)，因此最多有(K-1)个⾮零特征值。这表明，向由SB张成的(K-1)维空间

上的投影不会改变J(W)的值，因此通过这种⽅法我们不能够找到多于(K-1)个线性"特征"（Fukunaga,1990）。

LDA与指⽰矩阵的线性回归

容易证明:最⼩⼆乘⽅的系数向量正⽐于下式表⽰的LDA⽅向.

下⾯证明.

⽬前为⽌，我们已经考虑了⽬标变量的"1-of-K"表⽰⽅法来建模指⽰矩阵的线性回归模型.然⽽，如果我们使⽤⼀种稍微不同的表达⽅法，那

么权值的最⼩平⽅解就会变得等价于Fisher解（DudaandHart,1973）特别地，我们让属于C1的⽬标值等于N/N11，其中N1是类别C1的模

式的数量，N是总的模式数量。这个⽬标值近似于类别C1的先验概率的导数。对于类别C2，我们令⽬标值等于-N/N2，其中N2是类别C2的

模式的数量。

平⽅和误差函数可以写成

令E关于w0和w的导数等于零，我们有

根据上(1)公式，使⽤我们对于⽬标值tn的表⽰⽅法，我们可以得到偏置的表达式

通过⼀些简单的计算，并且再次使⽤我们对于tn的新的表⽰⽅法，⽅程(2)变为

我们注意到SBw总是在(m2-m1)的⽅向上,因此

其中，我们已经忽略了不相关的标量因⼦.因此权向量恰好与LDA准则得到的结果相同.

但是不同的是,LDA还有⼀个截距,参见公式

当N1不等于N2时,最⼩⼆乘法得到的投影⽅向虽然与LDA得到的投影⽅向相同,但是LDA还有⼀个截距,这使得分类策略不同.

Logistic回归

模型定义

逻辑斯缔回归源于这样⼀种愿望:通过x的线性函数对K个类的后验概率(的对数⼏率)建模,⽽同时确保它们的和为1.并且都在[0,1]中.该模型具有

如下形式:

该模型⽤K-1个对数⼏率或分对数变换确定.尽管模型使⽤最后⼀个类作为⼏率中的分母,但分母的选择是任意的.

简单的计算下得到:

⽽它们的和显然为1.

由贝叶斯分类理论可知,选择分类器

上述模型属于概率判别式模型.

参数估计

逻辑斯缔回归模型的参数是线性函数的系数.因为分类器定义为最⼤后验概率,(⽽且是真正的概率),对响应(⽬标变量)的编码采⽤1-of-K⽅式.tn

=[0,0,…1,0]

Loss函数采⽤负对数似然.

实际上,最⼤似然估计跟最⼩化负对数似然Loss本质上是⼀致的.

⾸先考虑⼆分类

对于⼀个数据集ϕn;tn，似然函数可以写成

其中t=(t1;:::;tN)T且yn=p(C1|ϕn)。

与之前⼀样，我们可以通过取似然函数的负对数的⽅式，定义⼀个误差函数。这种⽅式产⽣了交叉熵（cross-entropy）误差函数

其中yn=sigmoid(an)且an=wTϕn。两侧关于w取误差函数的梯度，我们有

我们看到，涉及到logisticsigmoid的导数的因⼦已经被消去，使得对数似然函数的梯度的形式⼗分简单。特别地，数据点n对梯度的贡献为

⽬标值和模型预测值之间的"误差"yn-tn与基函数向量ϕn相乘。此外，与公式（3.13）的对⽐表明，它的函数形式与线性回归模型中的平⽅

和误差函数的梯度的函数形式完全相同。

在第3章讨论线性回归模型的时候，在⾼斯噪声模型的假设的情况下，最⼤似然解有解析解。这是因为对数似然函数为参数向量w的⼆次函

数。对于logistic回归来说，不再有解析解了，因为logisticsigmoid函数是⼀个⾮线性函数。然⽽，函数形式不是⼆次函数并不是本质的原

因。精确地说，正如我们将要看到的那样，误差函数是凸函数，因此有⼀个唯⼀的最⼩值。此外，误差函数可以通过⼀种⾼效的迭代⽅法求

出最⼩值，这种迭代⽅法基于Newton-Raphson迭代最优化框架，使⽤了对数似然函数的局部⼆次近似。为了最⼩化函数E(w)，Newton-

Raphson对权值的更新的形式为（Fletcher,1987;BishopandNabney,2008）

其中H是⼀个Hessian矩阵，它的元素由E(w)关于w的⼆阶导数组成。

⾸先，让我们把Newton-Raphson⽅法应⽤到纯线性回归模型（3.3）上，误差函数为平⽅和误差函数（3.12）。这个误差函数的梯度和

Hessian矩阵为

其中_是N_M设计矩阵，第n⾏为ϕn^T。于是，Newton-Raphson更新的形式为

我们看到这是标准的最⼩平⽅解。注意，这种情况下误差函数是⼆次的，因此Newton-Raphson公式⽤1步就给出了精确解。现在让我们把

Newton-Raphson更新应⽤到logistic回归模型的交叉熵误差函数（4.90）上。根据公式（4.91），我们看到这个误差函数的梯度和Hessian

矩阵为

推导过程中我们使⽤了公式（4.88）。并且，我们引⼊了⼀个N_N的对⾓矩阵R，元素为

我们看到Hessian矩阵不再是常量，⽽是通过权矩阵R依赖于w。这对应于误差函数不是⼆次函数的事实。使⽤性质0

⾃于logisticsigmoid函数形式），我们看到对于任意向量u都有uTHu>0，因此Hessian矩阵H是正定的。因此误差函数是w的⼀个凸函数，

从⽽有唯⼀的最⼩值。

这样，logistic回归模型的Newton-Raphson更新公式就变成了

其中z是⼀个N维向量，元素为

我们看到更新公式（4.99）的形式为⼀组加权最⼩平⽅问题的规范⽅程。由于权矩阵R不是常量，⽽是依赖于参数向量w，因此我们必须迭

代地应⽤规范⽅程，每次使⽤新的权向量w计算⼀个修正的权矩阵R。由于这个原因，这个算法被称为迭代重加权最⼩平⽅

（iterativereweightedleastsquares），或者简称为IRLS（Rubin,1983）。与加权的最⼩平⽅问题⼀样，对⾓矩阵R可以看成⽅差，因为

logistic回归模型的t的均值和⽅差为

多类逻辑斯缔回归

见PRML4.34

对线性可分的奇异性

值得注意的⼀点是，最⼤似然⽅法对于线性可分的数据集会产⽣严重的过拟合现象。这是由于最⼤似然解出现在超平⾯对应于_=0:5的情

况，它等价于wTϕ=0。最⼤似然解把数据集分成了两类，并且w的⼤⼩趋向于⽆穷⼤。这种情况下，logisticsigmoid函数在特征空间中变得

⾮常陡峭，对应于⼀个跳变的阶梯函数，使得每⼀个来⾃类别k的训练数据都被赋予⼀个后验概率p(Ck|x)=1。此外，通常这些解之间存在

连续性，因为任何切分超平⾯都会造成训练数据点中同样的后验概率，正如后⾯在图10.13中将会看到的那样。最⼤似然⽅法⽆法区分某个

解优于另⼀个解，并且在实际应⽤中哪个解被找到将会依赖于优化算法的选择和参数的初始化。注意，即使与模型的参数相⽐数据点的数量

很多，只要数据是线性可分的，这个问题就会出现。通过引⼊先验概率，然后寻找w的MAP解，或者等价地，通过给误差函数增加⼀个正则

化项，这种奇异性就可以被避免。

参数数量

对⽐概率⽣成式模型,逻辑斯缔回归模型的参数相对较少.

对于⼀个M维特征空间ϕ，这个模型有M个可调节参数。相反，如果我们使⽤最⼤似然⽅法调节了⾼斯类条件概率密度(⽣成式模型)，那么我

们有2M个参数来描述均值，以及M(M+1)/2个参数来描述（共享的）协⽅差矩阵。算上类先验p(C1)，参数的总数为M(M+5)/2+1，这随着M

的增长⽽以⼆次的⽅式增长。这和logistic回归⽅法中对于参数数量M的线性依赖不同。对于⼤的M值，直接使⽤logistic回归模型有着很明显

的优势。

回归系数选择

见ESL4.42例:南⾮⼼脏病

逻辑斯缔回归还是LDA

分离超平⾯

感知机

⽀持向量机