模式识别和机器学习 笔记 第四章 线性分类模型(一)

快看是Charlie 2011-05-26

在前面的章节,我们已经看到线性回归模型具有很简单的分析性和计算性。我么现在我们讨论这种类似的模型来解决分类问题。分类的目的是给出一个输入向量X,将它赋值为k个离散的类别Ck之一,通常的情景是类别是不想交的,每一个输入只会有一个类别。这样输入空间被分成决策区域,它的边界被称为决策边界。本章我们考虑用于分类的线性模型,也就是说决策边界是关于输入变量x线性函数,它在D维的输入空间中定义了D-1维的超平面。类别可以被线性决策边缘分开的数据集合被称为线性可分。

在回归问题中,我们可以使用实数的向量来表示预测值t,在分类问题,我们可以采用1-of-K的编码模式,t是一个长度为K的向量,如果类别是Cj,那么除了tj为1,其他的元素tk都是0.比如K=5,C2可以表示为t={0,1,0,0,0)T

在第一章我们已经学习了三种不同的方法来解决分类问题,一种是简单的判别函数(discriminantfunction),它直接把输入变量x映射的特定的类别。另一比较强大的方式,建模条件分布p(Ck|x)。建模p(ck|x)的方式有两种:一种是直接建模,比如表示为参数模型,然后用训练数据计算出最优的参数,另一用方法是结合类别条件分布p(x|Ck)和先验概率p(Ck),然后利用贝叶斯公式计算后验概率:

p(Ck|x)=p(x|Ck)p(Ck)/p(x)

我们在本章讨论以上三种方式。

在第三章的线性回归模型中,模型预测函数y(x,w)是一个参数为w的线性函数,在最简单的情况,模型对于输入变量是线性的,具有如下形式:y=wTx+w0,所以y是个实数,对于分类问题我们希望预测离散的类别标签,或者更一般的区间在[0,1]之间的后验概率。我们可以利用一个非线性函数f(.)来将关于w的线性函数进行转换,即y(x)=f(wTx+w0),类别模型y(x)被认为是线性模型的推广,相对于回归模型而言,由于非线性函数f(.),对于参数已经不是线性的了。这会比回归模型具有更复杂的分析和计算性,但是对于一般的非线性的模型,这个模型相对已经比较简单了。

本章的算法也会讨论想第三章那样固定非线性基本函数,做一个固定的非线性变换。

4.1判别函数

一个判别函数是将输入向量x映射到一个K个类别之一Ck。本章我们仅限于线性判别函数,他们的决策边缘是一个超平面。为了简化我们先看2类的问题,然后扩展到K>2的情景。

4.1.1两类问题

最简单的线性判别函数是关于输入向量x的线性函数,即:

y(x)=wTx+w0

w被称为权重向量,w0被称为偏置(bias),偏置的负数被称为阈值。

对于输入变量x,如果y(x)>=0那么分类为C1,否则为C2。所以决策边界定义为y(x)=0,

为D维输入空间中的D-1维超平面。考虑两个点xA和xB,他们都在决策边缘上,那么

y(xA)=y(xB)=0,wT(xA-xB)=0,所以向量w正交于决策边缘,所以w决定了决策边缘的方向。如果x是决策边缘上的一点,那么y(x)=0,那么原点到决策边缘的距离

为wTx/||w||=-w0/||w||

所以偏置(bias)参数w0决定了决策边缘的位置。

任意一点在x和在决策边缘的x_的关系

x=x_+r*w/||w||

我们根据及y(x_)=wTx_+w0=0可以得到

r=y(x)/||w||

可以将向量w和x,进行扩展得到增广向量W=(w0,w)X=(x0,x)

那么y(x)=WX

4.1.2多类问题:

现在我们考虑K>2的线性判别函数的扩展。我们可以组合一些两类的判别函数得到K类

的判别函数,但是这会导致一些困难。

如果我们使用K-1个分类器,每一个解决2类问题,这被称为one-versus-the-rest分类器。但是有一些区域没有被分类(见图4.2的例子)。

另一种选择是引入K(k-1)/2个二元分类器,每一个对应一对类别,这被称为one-versus-one分类器。但是仍然有一些区域不能分开(见图4.2)

我们可以考虑一个单个的k-class的一起函数,他组合了K个线性函数:

yk(x)=wkTx+wk0

如果yk(x)>yj(x),j!=k,那么将点x赋值给类Ck。这个在Ck和Cj的决策边界

由yk(x)=yj(x)给出,因此(D-1)维的超平面被定义为:

(wk-wj)Tx+(wk0-wj0)=0

这和2-class的决策边缘类似。

这种判别的决策区域是单联通的,并且是凸。考虑两个点xA和xB,他们都在决策边缘Rk上,任何在连接xA和xB的线上的点x^,可以表示为:

x^=λxA+(1−λ)xB其中0=<λ<=1

对于线性的判别函数:

yk(x^)=λyk(xA)+(1-λ)yk(xB)

由于xA和xB都在决策区域Rk内,那么对于所有的j!=k,

yk(xA)>yj(xA),yk(xB)>yj(xB)

因此yk(x^)>yj(x^)

所以x^也在决策区域内Rk内。所以Rk是单连通并且是凸的。

我们下面将要介绍三种学习线性判别函数的方法:最小二乘法、Fisher线性判别函数,

感知器算法。

4.1.3用于分类的最小二乘法

我们在第三章看到,我们考虑了关于参数的线性函数的模型,我们使用最小化错误平方函数的方法得到了简单的关于参数的解,因为我们可以可以看一下是否这种方法可以应用于分类问题。

考虑一般的分类问题,有k个类别,对于目标向量t使用1-of-k的二元编码方式.一种可以证明可以使用最小二乘法的情形是,给定输入向量x的目标值t逼近条件期望E(t|x)。

对于二元编码,条件期望由后验分类概率给出。不幸的是这种概率的逼近非常的差,事实上这种逼近可能会超出(0,1)的区间,由于线性模型有限的灵活性导致的。

对于每个类Ck都有他们自己的线性模型,所以

yk(x)=wkTx+w0k=1,...,k。

我们可以写成:

y(x)=WX

其中W=(wk0,wkT)T,X=(1,XT)T

对于新的输入x被赋值为ck,如果yk=WkTXT最大。

我们通过最小化错误平方和,我们可以得出参数矩阵W,就像我们第三章回归中所做的。

对于训练集{xn,tn),n=1,...,N,我们定义一个矩阵T,他的第n行是向量tnT,矩阵

X的第n行是xTn。那么平方和错误函数可以写成:

Ed(W)=1/2Tr{(XW-T)^T(XW-T)

将关于W的导数设置为0,我们得到

W=(WTW)-1X^TT=X†T

其中X†是矩阵X的pseduo-inverse,因为W可能不是方阵。

这样我们得到了判别函数:

y(x)=WTX=T^T(X†)^Tx.

另外一个有趣的特性是多目标变量的最小二乘法的解,如果训练集每一个目标向量满足某个线性约束aTtn+b=0

那么对于末个常量a和b,对于任意x的模型预测值也满足相同的约束

aTy(x)+b=0

因此如果我们使用k-class的1-of-k的编码模式,那么模型预测具有以下特性,

对于任意的x,y(x)的元素之和是1

但是这个约束并不能将模型的输出解释为概率,因为他们每个值并不一定在(0,1)

之间。

最小二乘法给出了精确的判别函数参数的解,然而判别函数存在很严重的问题。我们已经看到最小二乘法对离群点(outliers)缺乏健壮性,这个同样适应于分类的应用程序。在第7.1.2节我们会讨论几种对于分类可选的错误函数,他们不会遭受现在的困难。

由于我们假设最大似然函数是高斯条件分布,而二元目标向量的分布和高斯分布差别很大。

所以导致最小二乘法的失败。我们通过采取更恰当的概率模型,会得到比最小二乘法更好的分类技术。然而,现在我们继续介绍可选的非概率的参数化的线性分类模型。

4.1.4Fisher's线性判别函数

一种线性分类模型的方法被称为降维。首先考虑一下两类问题,假设我们的输入具有D维,我们y=wTx将其映射到一维,那么

如果对y设置一个阈值:当y>=-w0时分类为C1,否则为C2,我们得到了一个标准的线性分类函数。然而,一般的我们映射到一维会丢失很多信息,在D维能够分开的,在一维空间可能会重叠。然而我们可以通过调整w的权重,选择一个映射能够最大化分类的间隔。

我们考虑二类问题类C1有N1个点,类C2有N2个点,所以这两个类的均值向量为:

m1=1/N1*sum(xn)n∈C1

m2=1/N2*sum(xn)n∈C2

当我们映射到w上,最简单的测量类别间隔的方法是映射类的期望的偏离程度,这样我们选择w,去最大化m2-m1=wT(M2-M1)

其中mk=wT*Mk是类Ck映射的均值。这个表达式可以通过扩大w来任意增大,所以我们限制w具有单位长度,即sum(wi*wi)=1

可以使用拉格朗日乘子来解决具有约束条件的最大值。我们发现w∝M2-M1.

4.1.5

4.1.6

4.1.7感知机算法

另一个线性判别模型的例子是感知机,这个在模式识别的历史上占据了重要的地位。对于2类的问题,输入矩阵首先通过一个固定的非线性函数转换为特征向量矩阵,然后用来构建一个更一般的线性模型的形式:

y(x)=f(wTφ(x))

这个非线性的函数f由分段函数形式给出:

f(a)=ifa>=0then+1else-1end

向量φ(x)包含偏置组件φ0(x)=1.

在概率的模型中,我们对目标次的编码t∈{0,1},对于感知机来说使用

t=ifc1then+1else-1end

的编码更方便

感知机的参数w可以通过最小化错误函数来决定,一个很自然的错误函数的选择是错误分类的模式的个数。但是这并不是一个简单的算法,因为这是一个分段不连续的常数函数,这种根据错误函数的梯度来跟新w的算法不能适用,因为梯度几乎处处为0。

我们考虑另外的错误函数:感知器标准(perceptroncriterion)。我们注意到我们在寻找一个权重矩阵w,它能够使类c1的模式xn满足wT*φ(xn)>0,在c2中的模式xn满足wTφ(xn)<0,如果我们使用t∈{-1,+1}的编码方式,那么wT*φ(xn)*tn>0

如果每一个模式都能够被正确分类,那么错误为0.即努力去最小化

-wT*φ(xn)*tn

Ep(w)=-sum(wT*φ(xn)*tn)wheren∈M

M表示所有分类错误的模式。

我们可以对错误函数使用梯度算法(stochasticgradientdescentalgorithm)

权重向量w每次跟新由下面的式子给出:

w(τ+1)=w(τ)−η∇EP(w)=w(τ)+ηφntn

η是学习率。因为我们将w乘以一个常量,函数y(x,w)不会改变,所以我们可以去η为1

我们可以看到:

−w(τ+1)Tφntn=−w(τ)Tφntn−(φntn)Tφntn<−w(τ)Tφntn

更新w之后错误分类的模式的贡献将会被减少。但是w的修改可能导致前面正确分类的模式被错误分类,所以在这个学习规则不能够保证每个步骤中都减少错误总和的大小。

然而感知机收敛的理论证明如果有一个精确的解,那么感知机器可以在有限的步骤中找到它。

但是有的收敛很慢,我们无法区分不可分的问题和很慢收敛的问题,即使是线性可分的,它也依赖于最初的参数和点的顺序,对于非线性可分的问题,这个算法是不收敛的。

感知机给出概率输出,也不能泛化成为k>2的分类,这也是感知机的缺点。

LargeMarginClassificationUsingthePerceptronAlgorithm给出一个基于投票的感知机器:

训练:

输入:标记好的训练集<(x1,y1),...,(xm,ym)>,迭代次数T

输入:权重感知机<(v1,c1),...,(vk,ck)>列表

1.初始化k=0,v1=0,c1=0

2.重复T次迭代:

1.upto(m)do

*计算预测值y^=sign(vk*xi)

*ify^=ythenck=ck+1

elsevk+1=vk+yixi;

ck+1=1;

k=k+1

end

end

预测:

输入:权重感知机<(v1,c1),...,(vk,ck)>列表和未标注的实例x

计算

s=sum(ci*sign(vi*x))fori=1..k

y^=sign(s)

4.2概率生成模型

我们开始转向概率观点的分类问题,我们通过对数据分布的简单假设,展示如何使用线性决策边缘去建模。

对于二元分类的问题,C1的后验概率:

p(c1|x)=p(x|c1)*p(c1)/p(x|c1)*p(c1)+p(x|c2)*p(c2)

=1/1+exp(-a)=σ(a)

其中a=ln(p(x|c1)*p(c1)/p(x|c2)*p(c2))

σ(a)是logisticsigmoid函数:

σ(a)=1/1+exp(-a)

我们可以得到:

a=ln(σ/1-σ)

被称为logit函数,他代表了概率比的log值:ln(p(c1|x)/p(c2|x))

对于多类问题

p(ck|x)=p(x|ck)*p(ck)/sum(p(x|cj)*p(cj)=exp(ak)/sum(exp(aj))

其中ak=ln(p(x|ck)*p(ck))

4.2.1连续型输入ian

如果我们假设类别的条件密度是高斯函数,然后导出其后验概率的形式,我们首先假设所有的类别都有都有相同的协方差矩阵,那么类别Ck的条件概率:

f(x|Ck)=1/(2π)^D/2*1/|Σ|1/2exp{-1/2(x-μk)T*Σ^−1*(x-μk)}

考虑二元分类问题,我们得到:

p(c1|x)=σ(wTx+w0)

其中

w=Σ−1*(x-μk)

w0=−1/2*μ1T*Σ^−1*μ1+1/2*μ2T*Σ^−1*μ2+lnp(C1)

p(C2).

我们可以看到x关于w是线性的,所以决策边缘在输入空间内是线性的。

对于多类问题

ak(x)=wkT+wk0

其中

wk=Σ^−1*μk

wk0=−1/2*μkT*Σ^−1*μk+lnp(Ck)

看到x关于w是线性的,决策边缘在输入空间内是线性的

如果每个类条件概率p(x|Ck)都有自己的协方差矩阵,那么我们将得到x二次函数。

4.2.2最大似然法

一旦我们有了关于类别的参数化的条件分布p(x|Ck),我们就可以使用最大似然发来求出

参数的值,包括类别的先验概率p(Ck)

我们考虑两类的问题,每一个都具有关于类别的条件密度,他们共享协方差矩阵,假如我们具有数据集{xn,tn}其中n=1,...,N,tn=1表示类别C1,tn=0表示类C2。我们用p(c1)=π来表示类别的先验概率,所以p(C2)=1-π。

那么,对于c1:

p(xn,c1)=p(c1)*p(xn|c1)=π*N(xn|μ1,Σ)

对于c2:

p(xn,c2)=p(c2)*p(xn|c2)=(1-π)*N(xn|μ2,Σ)

我们得到似然函数:

p(t|π,μ1,μ2)=mult(1..n){π*N(xn|μ1,Σ)}^tn{(1-π)*N(xn|μ2,Σ)}^(1-tn)

依赖于π的似然函数

mult(1..n){tn*lnπ+(1-tn)*ln(1-π)}

我们对π求导,并使其为0,得到

π=1/N*sum(1..n)tn=N1/N=N1/(N1+N2)

我们现在考虑关于μ1,我们找出和μ1相关的部分,对μ1求导并使其为0得到:

μ1=1/N1*sum(1..N)tn*xn

μ2=1/N2*sum(1..N)tn*xn

我们找出和Σ相关的部分,对Σ求导并使其为0得到:

s=N1/Ns1+N2/N*s2

s1=1/N1sum(n∈C1){(xn-μ1)(xn-μ1)^T}

s1=1/N2sum(n∈C2){(xn-μ2)(xn-μ2)^T}

Σ=S,表示两个类别协方差的加权平均

我们很容易将其扩展到k类的问题。由于最大似然估计高斯分布不是很鲁棒,所以这种方法

对离群点不是很健壮。

4.2.3离散的特征

现在我们考虑离散的特征值xi。为了简化我们先看二元的特征值xi∈{0,1},然后在扩展到一般的离散值的情况。如果有D个输入,对于每一个类对应应2^D个元素的表,他的分布包含

2^D-1个独立的变量。由于这和特征数量成指数级增长,我们需要寻找一个更多限制的表示。

我们对NaiveBayes分布假设其对Ck的条件分布,其特征值之间是独立的。所以我们有:

p(x|Ck)=multiple(1..D){μki^xi*(1-μki)^1-xi

每一个类包含D个独立的参数,替换(4.63)我们得到:

ak(x)=sum{1..D}{xi*ln*ki+(l-xi)*ln(1-μki)}+lnp(Ck)

仍然是输入变量xi的线性函数。

4.2.4指数族分布

我们前面看到,不管高斯分布还是离散输入,后验类概率都是线性模型在logisticsigmoid(K=2)或者softmax(K>2)activation函数的推广。

我们通过假设类条件密度p(x|Ck)是指数族分布,我们得到了一个更一般的结果。

在(2.194)我们可以将指数族分布写成:

p(x|λk)=h(x)g(λk)exp{λkTu(x)}.

现在我们考虑限制u(x)=x得到这类分布的子集。

我们引入一个比例参数s,我们获得受限的指数族条件分布的概率密度形式:

p(x|λk,s)=1/s*h(1/s*x)*g(λk)*exp{1/s*λkT*x}

我们假设每个类别都有自己的参数向量λk,但是我们假设他们共享比例参数s。

对于两类问题,我们替换这个表达式到类条件概率密度函数,我们发现类的后验概率仍然

是相对于logisticsigmoid的线性函数:

a(x)=(λ1−λ2)T*x+lng(λ1)−lng(λ2)+lnp(C1)−lnp(C2).

类似的对于k-类问题。我们得到:

ak(x)=λkTx+lng(λk)+lnp(Ck)

仍然是关于x的线性函数。

相关推荐