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

在前面的章节，我们已经看到线性回归模型具有很简单的分析性和计算性。我么现在我们讨论这种类似的模型来解决分类问题。分类的目的是给出一个输入向量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)=λkＴx+lng(λk)+lnp(Ck)

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