第3章
CHAPTER 3


贝叶斯决策






决策是机器学习中一个相对独立的部分。当机器学习的模型已经确定，对于新的输入可计算模型输出，模型的输出代表什么，即对模型输出做出最后判断，这是决策过程要做的事情。针对不同的模型，决策过程的作用是不一样的。对于有的模型，模型输出直接表示了明确的结果，不需要一个附加的决策过程； 而对于其他模型，尤其是概率类模型，往往需要对模型输出做出一个最终的决策，这是决策过程的作用。在机器学习中，决策往往是一个独立且相对简单的单元，本章讨论决策问题，集中在贝叶斯决策。


ML05统
计基础2


3.1机器学习中的决策
一般来讲，机器学习是通过训练过程得到描述问题的模型，可将模型表示为一种数学关系。当给出新的输入数据时，可按照模型需要的格式将输入数据转换为模型可接受的输入特征向量，计算模型的输出。所谓决策，就是对于模型的输出给出一个判决结果。
决策就是要做出最后的结论，对于分类，要给出类型的结果； 对于回归，要给出输出值。对于一个模型，从其输出是否确定的角度，可将模型分为概率和非概率模型。对于非概率模型，模型是一个确定性的判别函数，该模型通过训练过程直接得到确定的函数关系y^=f(x)，其中x为输入特征向量。当通过训练得到模型后，给出一个新的x，函数产生结果y^。对于分类问题，y^取离散值并表示类型； 对于回归问题，y^得到连续的输出值。对于这类确定性模型，决策是直接的，一般不需要进一步决策。
对于概率模型，训练过程中给出的模型是输出y的一种概率表示。有两类基本的概率模型： 一类是生成模型，给出的是联合概率p(x,y)； 另一类是判别模型(注意与确定性判别函数是有区别的)，给出的是后验概率p(y|x)。目前的概率模型中，判别模型应用更广泛。以判别模型为例，假设通过训练过程得到了后验概率表示式p(y|x)，我们将首先针对二分类问题说明决策过程。设分别用C1和C2表示类型，则对于新的x，可计算p(y=C1|x)(简记为p(C1|x))和p(y=C2|x)(简记为p(C2|x))，由这些概率怎样确定输入x对应哪一类呢？这需要通过决策理论做出最后的判决。例如，p(C1|x)=0.6，p(C2|x)=0.4，是否一定会判决为类型C1呢？
对于概率模型，怎样做出最后的决策呢？为了得出最后的结论，需要给出问题的评价函数，一般可以用风险函数作为评价函数，通过最小化风险函数的后验概率期望(即贝叶斯风险函数)获得判决准则，然后利用判决准则对模型输出的结果做出结论。由于主要使用后验概率做出决策，并采用贝叶斯风险函数作为评价函数，故将所讨论的决策问题称为贝叶斯决策。分类和回归的决策方法和评价函数不同，将单独予以处理。
前文提到的生成模型主要是针对监督学习情况。实际上，生成模型是机器学习中一类重要的模型。更一般地，给出训练样本集xnNn=1，这里xn表示一般化的样本向量，它是通过对一个概率分布p(x)采样所获得的，但对我们来讲p(x)是未知的，通过样本集学习出p(x)，这是生成模型的一般含义。若p(x)可由高斯分布表示，则生成模型是简单的，但在机器学习中常遇到各种非常复杂的数据，其背后的p(x)同样极其复杂，这种情况下生成模型的学习具有很高的挑战性。稍后，3.3节针对高斯情况，第5章针对简单的离散分布(朴素贝叶斯)，以分类为例给出简单的生成模型算法，第11章将介绍一种很有效的针对无监督情况的生成模型学习，即生成对抗网络。




3.2分类的决策
假设学习阶段通过训练已得到模型的联合概率p(x,y)(对于生成模型)或后验概率p(y|x)(对于判别模型)，需要对类型输出做出最终判决，即决策。
首先讨论二分类问题。以下使用联合概率导出结论，但实际上对于分类决策只需要后验概率。
在讨论的开始，首先假设特征输入x和类型C的联合概率p(x,C)已知，由于是二分类问题，C只有C1和C2两个取值，故可以分别写出两种类型的联合概率值p(x,C1)和p(x,C2)。对于分类问题，一个最直接的评价函数是错误分类率，错误分类率等于两部分之和： x属于C1类却被分类为C2和x属于C2却被分类为C1。决策理论的目标是找到一个判决准则，使错误分类率最小，即最小错误分类率(Minimum Misclassification Rate，MMR)准则。
设输入特征向量x是D维向量，其输入空间是D维向量空间的一个区域R，通过决策理论，可将区域R划分为两个不重叠区域R1和R2。当x∈R1时，判断类型输出为C1； 当x∈R2时，判断类型输出为C2。划分区域的准则就是MMR。
为了便于理解，图3.2.1所示为x为标量情况下的概率密度函数p(x,C1)和p(x,C2)。假如已经做出了区域划分R1和R2，那么当x∈R1但其真实是属于C2，则对应一个错误的分类，其错误概率可表示为

p(x∈R1,C2)=∫R1px,C2dx

反之，当x∈R2但真实是属于C1类时，则对应一个错误分类，其错误概率为

px∈R2,C1=∫R2px,C1dx

将两者合并一起，总的错误分类率pe为


pe=px∈R1,C2+px∈R2,C1

=∫R1px,C2dx+∫R2px,C1dx(3.2.1)


以上假设已划分出R1和R2，从而写出了错误分类率公式。现在我们反过来，通过错误分类率公式，选择R1和R2使pe最小。通过观察图3.2.1和式(3.2.1)发现，若想pe最小，只需这样选择R1和R2： 将满足px,C1＞px,C2的取值集合取为R1，反之取为R2，一般将px,C1=px,C2的点任意分配给R1或R2。
由此可得到判决准则，当给出一个新的x，若

px,C1＞px,C2(3.2.2)

则分类为C1，反之分类为C2。由概率公式px,Ci=pCi|xp(x)，将式(3.2.2)表示为后验概率形式为，即若

pC1|x＞pC2|x(3.2.3)

则分类为C1，否则分类为C2。应用MMR准则的决策公式为式(3.2.2)或式(3.2.3)。目前分类算法中，判别模型应用更多，故式(3.2.3)更常用。由于式(3.2.3)也表示了式(3.2.2)的含义，因此若非特殊需要，总是以式(3.2.3)表示决策公式。


图3.2.1联合概率和判决


以上结果可直接推广到多类情况，设有C1,C2,…,CK种类型，最后分类结果为Ci*，则

Ci*=argmaxCipCi|x(3.2.4)

以上给出了在最小错误分类率准则下的判决准则，结果非常直观，即将后验概率最大的类作为分类输出。回到本章的开始，若一个机器学习模型是概率模型，对于新的x可分别计算分类为Ci的后验概率，则决策准则将后验概率最大的类作为最终类输出。
以上的基本决策原理的前提条件是假设所有错误的代价是平等的，这在很多实际应用中不符合现实，下面讨论两种更实际的判决方式。

3.2.1加权错误率准则
在实际应用中，一些错误比另一些错误代价更大。例如，一辆无人驾驶汽车的刹车系统，为了方便说明，一个简化的模型输出只有两类： 刹车或不刹车，这可看作分类问题。应刹车时判决为不刹车，比不应刹车时判决为刹车往往代价更大，所以要对刹车判决的不同错误定义不同的代价，如图3.2.2所示。


图3.2.2刹车决策的错误代价加权矩阵


在图3.2.2中，刹车被错判为不刹车的代价是不刹车被错判为刹车的代价的10倍，这是一个主观的加权。对于实际问题，如刹车问题，可通过预先得到的大量交通事故数据按所关心的指标给出加权矩阵的统计值。对于更一般的多类型情况，将加权矩阵表示为L，矩阵的各元素表示为Lkj=LCjCk，即将Ck分类为Cj的代价加权值。考虑所有的Ck和Cj的组合，得到总期望损失为

EL=∑k∑jLkj∫Rjp(x,Ck)dx(3.2.5)

将式（3.2.5）重组为

EL=∑j∫Rj∑kLkjp(x,Ck)dx=∑j∫Rj∑kLkjpCk|xp(x)dx(3.2.6)

分类为Cj的风险定义为

RCj|x=∑kLkjpCk|x(3.2.7)

可见为了使式(3.2.6)的结果最小，划分Rj的准则是将R(Cj|x)最小的区间划分为Rj。由于Cj表示所有可能的类，故分类为Ci*的决策公式为

Ci*= argminCjRCj|x=∑kLkjpCk|x(3.2.8)

由于每个pCk|x在学习过程都已经训练得到，Lkj是预先确定的，式(3.2.8)的决策是简单的加权求和与比较运算。
例3.2.1讨论式(3.2.8)在二分类情况下的特殊形式。只有两类时，式(3.2.7)的风险值只有两个，即


R(C1|x)=L11p(C1|x)+L21p(C2|x)

R(C2|x)=L12p(C1|x)+L22p(C2|x)
(3.2.9)

由式(3.2.8)，若要分类结果为C1，则只需R(C1|x)＜R(C2|x)，将(3.2.9)各式代入并整理得

L12－L11p(C1|x)＞L21－L22p(C2|x)(3.2.10)

(1) 情况1。取L12=L21=1,L22=L11=0，则式(3.2.10)简化为p(C1|x)＞p(C2|x)，即在各种错误等代价的二分类问题时，式(3.2.8)与式(3.2.3)等价。
(2) 情况2。若取L12=10,L21=1,L22=L11=0，则式(3.2.10)简化为p(C1|x)＞0.1p(C2|x)，即可判断为C1，这里的加权用的是图3.2.2的有关刹车的加权矩阵，可见在该损失加权的条件下，p(C1|x)=0.1就可以决策为刹车。
由贝叶斯公式，可将式(3.2.10)写为

L12－L11pxC1pC1＞L21－L22pxC2pC2(3.2.11)

整理得到分类为C1的条件为

pxC1pxC2＞L21－L22L12－L11pC2pC1(3.2.12)

式(3.2.12)中利用了类条件概率(密度)pxCi和类先验概率pCi，称为似然比准则。

3.2.2拒绝判决
在各种误分类代价相等的情况下，在二分类时只要满足式(3.2.3)即可分为类型C1，如p(C1|x)=0.51即可分类为C1。当两类的后验概率很接近时，分类结果可信度不高，错误分类率也较大，在一些需要高可靠分类的应用中，这种分类结果显然无法接受，故在很多情况下，可能对一定的后验概率范围拒绝做出判决。如图3.2.3所示，在pxCi均小于一个预定的阈值θ(如θ=0.9)时拒绝做出判决。对于多分类问题，只有至少有一个p(x|Ci)≥θ时，才利用式(3.2.4)做判决，否则拒绝判决。


图3.2.3拒绝判决


拒绝判决是一个有意义但需要谨慎使用的原则，其使用与所面对的问题的代价分析有关。例如，在一个邮件自动分拣的邮政编码识别系统中，假设一封信的第1位邮政编码数字被自动分类为1和7的概率最大但很接近，该信可以由自动分拣系统拒绝判决，转为人工服务，显然，人工服务的成本比自动分拣高，但远低于一封信被错误投递的代价。
拒绝判决可降低错误分类率，极端的例子是，拒绝做任何判决则错误分类率为0，但这样的系统毫无意义。故选择拒绝判决以及拒绝判决的阈值与应用是密切相关的，需要在实际系统设计中谨慎选择。
3.3回归的决策
对于回归问题，本书介绍的回归模型较多的是直接得到回归函数y^=g(x)，也有一些方法是首先通过学习过程得到联合概率p(x,y)或后验概率p(y|x)，对这种模型首先需要选择一种评价性能的函数，通过决策给出回归的连续输出值y^。在回归情况下最常用的评价函数之一是均方误差(Mean Square Error,MSE)。回归输出y^与真实y的均方误差定义为


mse(y^)=(y－y^)2p(x,y)dxdy(3.3.1)

若要求一个y^使均方误差最小，可令将(3.3.1)两侧对y^求导且令导数为0，将得到一个解为y^=g(x)。
利用贝叶斯公式，有

mse(y^)=∫∫(y－y^)2p(x,y)dxdy=∫∫(y－y^)2p(y|x)dypx(x)dx
(3.3.2)

将上述等式对y^求导，并交换积分和求导顺序，得

mse(y^)y^=∫y^∫(y^－y)2p(y|x)dypx(x)dx
(3.3.3)

为求最小均方估计y^，只需令式(3.3.3)为0，因为对所有x，px(x)≥0，故欲使mse(y^)y^=0，只需令

y^∫(y－y^)2p(y|x)dy=0(3.3.4)

将式(3.3.4)中求导和积分次序交换，得

y^∫(y－y^)2p(y|x)dy=－2∫(y－y^)p(y|x)dy＝0

得到

y^=∫yp(y|x)dy=Ey|x(y|x)(3.3.5)

这是最小均方误差(Minimum Mean Square Error，MMSE)意义下回归的最优输出值，称为后验期望输出。在参数估计问题中，若用参数θ代替回归输出y，则同样的结论称为MMSE贝叶斯参数估计器。
对于一个回归学习系统，通过学习过程得到了后验概率p(y|x)，则给出一个新的特征向量输入x后，回归的输出是y的后验条件期望值y^=Ey|x(y|x)。将回归输出y^代入式(3.3.1)，得到最小均方误差为

mmse(θ^)=(y－E(yx))2p(x,y)dxdy

例3.3.1对于回归问题，仍以高斯分布为例。若有一个回归问题，则通过学习过程得到的后验概率为

p(y|x)=NywTx,σ2y|x

其中，w为通过训练得到的权系数向量。由高斯分布的特点和式(3.3.5)可得，使MSE最小的回归输出为

y^=Ey|x(y|x)=wTx

方差σ2y|x刻画了回归输出的不确定性大小。


本节注释1介绍决策理论后，可对机器学习的框架再做一个概要讨论。通过机器学习解决一个实际问题，大致分为3个步骤： ①针对要解决的问题收集数据，预处理数据(数据清洗、标注等)，确定解决问题的算法模型，如选择采用监督学习、选择神经网络模型、支持向量机模型或其他模型； ②训练过程，用样本集对模型进行训练，选择模型规模和参数，对确定性模型得到y^=f(x)的判别函数，对概率模型得到联合概率p(x,y)或后验概率p(y|x)； ③推断或预测过程，给出新的特征输入x，对确定性模型直接得到结果，对概率模型计算得到后验概率p(y|x)，通过后验概率和风险函数获得判决准则做出决策。对于复杂问题，以上3个步骤也可能要反复，直至得到需要的结果。决策理论是机器学习过程中最后一步的组成部分，总的来讲是比较容易的一部分，本章给出了决策理论的一个概要介绍，后续章节直接应用这些结果，一般来讲，若不与具体应用环境结合，就采用最简单的决策公式（见式(3.2.4)）。
本节注释2在许多实际应用中，对于决策的目标函数设计，有一些特定的针对性指标，这些内容与应用密切关联。比较广泛的应用包括自然语言处理、计算机视觉、推荐系统、信息检索等，也有很多更专门的应用，如医学诊断、DNA分析、雷达目标分类、通信信道建模、震动检测等。本书作为机器学习的基本教程，不讨论与这些专门应用对应的一些特殊指标，有兴趣的读者可参考这些领域的专门文献。

3.4高斯情况下的分类决策
由于对机器学习需求的广泛性，所面对的数据类型也是非常广泛的，既有物理传感器采集的物理信号，也有社会调查所获得的不同人群的各类数据，或是电商平台记录的用户购物数据。面对如此广泛的数据类型，没有一个学习模型是通用的，这也是“没有免费的午餐”定理所阐述的原则。因此，本书会介绍多种不同的学习模型，以适应不同的应用需求。大多数的学习模型表现出不同的复杂性。但在数据的概率分布服从高斯分布时，问题往往变得简单且具有有效的闭式解。
本节以高斯情况为例，进一步理解决策理论在分类的应用，并导出最基本的学习模型。假设所要分类的数据集中包含K种类型CiKi=1，类Ci的出现概率为pCi。高斯情况是指在类型确定为Ci时，类条件概率px(xy=Ci)(简写为px(xCi))服从高斯分布，即

p(xCi)=1(2π)M/2Σi1/2exp－12x－μiTΣ－1ix－μi(3.4.1)

其中，μi,ΣiKi=1表示各类条件概率的参数。若假设式(3.4.1)中的各参数均已知，给出一个新的特征向量x，利用3.2节的决策准则，给出x所对应的类型。
决策准则式(见式(3.2.4))需要用后验概率进行判决，由于p(x)不影响结果，则

pCi|x∝pxCipCi(3.4.2)

对于该问题，为了导出更加直接的决策准则，首先定义对应后验概率式(3.4.2)的判别函数gi(x)为


gi(x)=lnpxCipCi

=－12x－μiTΣ－1ix－μi－12lnΣi－M2ln2π+lnpCi
(3.4.3)


由式(3.4.3)可导出更直接的分类判决准则。下面首先讨论二分类问题，分别讨论Σ1=Σ2=Σ和Σ1≠Σ2两种情况，然后推广到多分类情况。
3.4.1相同协方差矩阵情况的二分类
在二分类问题中，只有C1和C2两种类型，假设Σ1=Σ2=Σ，由μ1和μ2区分两类。注意到当利用式(3.2.3)进行判决时，若p(C1|x)＞p(C2|x)，则判决为类型C1，这等价于g1(x)＞g2(x)。由于只需比较gi(x)的大小，故将式(3.4.3)中各gi(x)的相同项丢弃，重写简化的gi(x)为

gi(x)=－12x－μiTΣ－1x－μi+lnpCi,i=1,2(3.4.4)

注意到，式(3.4.4)等号右侧第一项展开后，二次项xTΣ－1x与类型无关，也可删去，这样gi(x)进一步简化为

gi(x)=wTix+wi0(3.4.5)

其中，系数和偏置分别为

wi=Σ－1μi

wi0=－12μTiΣ－1μi+ln［p(Ci)］
,i=1,2

(3.4.6)

若分类输出判决为C1，则需要

g1(x)＞g2(x)(3.4.7)

将式(3.4.6)代入式(3.4.7)加以整理，得判决为C1的条件为

g(x)=wTx+w0＞0(3.4.8)

式(3.4.8)的系数为


w=w1－w2=Σ－1(μ1－μ2)

w0=w10－w20=－12μT1Σ－1μ1+12μT2Σ－1μ2+lnp(C1)p(C2)

(3.4.9)

对于高斯分布，若已知μ1,μ2和Σ，对于一个新的特征输入x，进行式(3.4.8)的判决，若成立，则输出类型C1，否则输出类型C2。
在机器学习的应用中，一般并不知道μ1,μ2，p(C1),p(C2)和Σ这些参数，而是存在一组训练样本

D=xn,ynNn=1(3.4.10)

设训练样本是IID的，下面通过训练样本估计这些参数，这是例2.3.4的一个推广。在例2.3.4中没有类型标注yn。为了估计上述参数，需要表示联合分布pxn,yn，然后通过MLE估计参数。这里，yn作为标注，yn=1表示类型C1，yn=0表示类型C2，为表示简洁，类型概率表示为

pC1=pyn=1=π，pC2=pyn=0=1－π(3.4.11)

则


pxn,yn=1=pxn,C1=pxnC1pC1

=πNxnμ1,Σ(3.4.12)

pxn,yn=0=pxn,C2=pxnC2pC2

=(1－π)Nxnμ2,Σ(3.4.13)


yn只有两个取值，相当于伯努利分布，故联合分布pxn,yn为


pxn,ynπ,μ1,μ2,Σ=πNxnμ1,Σyn
(1－π)Nxnμ2,Σ1－yn
(3.4.14)


考虑样本是I.I.D的，则对数似然函数为


lnpX,yπ,μ1,μ2,Σ

=ln∏Nn=1πNxnμ1,Σyn(1－π)Nxnμ2,Σ1－yn

=∑Nn=1ynlnπNxnμ1,Σ+(1－yn)ln(1－π)Nxnμ2,Σ(3.4.15)


式(3.4.15)对各参数求偏导数并令其为0，分别得到各参数的估计值为


π^=1N∑Nn=1yn=N1N(3.4.16)

μ^1=1N1∑Nn=1ynxn,μ^2=1N2∑Nn=1(1－yn)xn(3.4.17)

Σ^=1N∑Nn=1ynxn－μ^1xn－μ^1T+

∑Nn=1(1－yn)xn－μ^2xn－μ^2T(3.4.18)


其中，N1为样本集中属于C1的样本数目； N2为样本集中属于C2的样本数目。
将估计的参数代入式(3.4.9)计算w和w0，则式(3.4.8)的判决方程就确定了，给出新的特征输入，就可以做出分类决策。注意到在等协方差矩阵的高斯情况下，判决方程是一个线性函数，令

g(x)=wTx+w0=0(3.4.19)

得到一个x空间的超平面，该平面将空间分划成两个区域，g(x)＞0的区域属于类型C1，g(x)＜0的区域属于C2，位于超平面上的点可任意判决为C1或C2。在这种情况下，依据式(3.2.3)得到的判决方程式(3.4.8)已经退化成一个确定性的线性判决函数，由其可进行分类判决，判决函数使用起来更简单直接，但已失去后验概率所具有的丰富内涵。而后验概率自身有着丰富的内涵，可以进行拒绝判决，可以结合加权损失，也可以通过概率原理集成多个分类器。
在高斯情况下，由以上已得结果可以导出后验概率pCi|x。先看p(C1|x)，由贝叶斯公式

p(C1|x)=px,C1p(x)=pxC1pC1pxC1pC1+pxC2pC2(3.4.20)

用一点数学技巧，得

p(C1|x)=11+pxC2pC2pxC1pC1=11+e－a(x)=σa(x)(3.4.21)

这里使用了

a(x)=lnpxC1pC1pxC2pC2(3.4.22)

并且使用了一个函数定义，即

σ(a)=11+e－a(3.4.23)

该函数称为Sigmoid函数，其详细的讨论和性质将在第5章给出，它是机器学习中广泛使用的函数，这里暂不做深入讨论，只需要注意到σ0=0.5，α＞0时，σ(a)＞0.5。p(C2|x)可以表示为

pC2|x=1－p(C1|x)(3.4.24)

式(3.4.21)给出了后验概率的表达式，其中参数a(x)由式(3.4.22)计算，不难验证，将pxCi,pCi代入式(3.4.22)整理得(推导细节留作习题)

a(x)=g(x)=wTx+w0(3.4.25)

式(3.4.25)的系数wT和w0在式(3.4.9)已求得。注意到，由式(3.4.21)可见，当a(x)＞0时，p(C1|x)＞0.5，分类判决为C1，这与式(3.4.8)结果一致。在更多应用中，后验概率比式(3.4.8)的判别方程内涵更丰富。
3.4.2不同协方差矩阵情况的二分类
在Σ1≠Σ2的条件下，除数学表达上略复杂一些，过程与相同协方差矩阵情况相似。略去与比较大小无关的项，gi(x)表示为

gi(x)=xTWix+wTix+wi0,i=1,2(3.4.26)

其中，系数和偏置分别为


Wi=－12Σ－1i

wi=Σ－1iμi

wi0=－12μTiΣ－1iμi－12lnΣi+lnpCi(3.4.27)

对于输入x，若分类输出判决为C1，则需要

g(x)=xTWx+wTx+w0＞0(3.4.28)

其中，权系数为


W=－12Σ－11－Σ－12

w=Σ－11μ1－Σ－12μ2

w0=－12μ1TΣ－11μ1+12μT2Σ－12μ2－12lnΣ1Σ2+lnpC1pC2(3.4.29)

在Σ1≠Σ2的条件下，对参数μi和Σi的估计更简单，按照yn取1或0将样本集分为D1和D2，直接利用例2.3.4的结果，用各子样本集Di直接估计μi和Σi，π的估计仍用式(3.4.16)。容易验证，只需要用式(3.4.28)的g(x)替代式(3.4.8)的g(x)，则后验概率p(C1|x)的表达式不变，仍如式(3.4.21)和式(3.4.25)所示。
3.4.3多分类情况
可将二分类的结果直接推广到有K个类型的多分类问题，对于判别函数gi(x)，只需将式(3.4.26)中的i=1,2扩展为i=1,2,…,K，并取gi(x)最大的类为输出类型。对于后验概率pCi|x，可得到结果(推导细节留作习题)

pCi|x=exp［gi(x)］∑Kk=1expgk(x)(3.4.30)

以上已对高斯情况的分类问题做了较详细的讨论，利用了决策理论的结果。可以看到在满足式(3.4.1)假设的情况下，对于给出如式(3.4.10)所示的样本集，可估计式(3.4.1)的所有参数，也可估计pCi的概率。如果以基本的最小错误分类率准则进行分类，在高斯情况下，可得到简单的判决函数gi(x)； 若需要更丰富信息的后验概率p(Ci|x)，也得到了后验概率的解析公式。
对于高斯情况，在给出式(3.4.10)的训练样本集后，可以估计出式(3.4.14)的联合概率密度函数p(x,y)和各种情况下的类后验概率pCi|x，获得所谓的生成模型和判决模型都不困难。但对于其他复杂概率分布，一般生成模型的学习是很困难的。
若高斯假设与实际数据相符合，则对于分类问题，本节给出的结果是性能良好的，对于复杂的实际情况，高斯假设只有一定的符合度或符合度较差，这种情况下，通过本节的方法很难得到满意的较低的错误分类率，需要探索更多类型的分类算法。本书第5章介绍了一些基本的分类算法，后续章节给出了各种更专门的分类算法，如支持向量机、神经网络、决策树和集成学习算法。

3.5KNN方法
第1章中以KNN分类器为例对分类器功能进行了说明，利用3.2节的决策理论可进一步解释KNN分类器的原理。
设训练样本集D=xn,ynNn=1对应C1,C2,…,CJ共J种类型，总样本数为N，各类型对应的样本数分别为N1,N2,…,NJ。对于一个给定的x，以其为中心的超球体内包括K个样本，体积为V。设近邻的K个样本中，标注为各类型的样本数分别为K1,K2…,KJ，利用这些数据进行概率估计，显然有

p^(x)=KNV，p^(xCj)=KjNjV，p^(Cj)=NjN(3.5.1)

故后验概率为

p^(Cj|x)=p^(xCj)p^(Cj)p^(x)=KjK(3.5.2)

按照3.2节分类错误率最小的决策准则（见式(3.2.4)），如果一个类型Cj*的后验概率最大，则输出为Cj*类。在KNN算法中，由式(3.5.2)可见，p^(Cj*|x)最大对应近邻样本数Kj*最多，则分类为Cj*。可见KNN分类器是一种建立在后验概率最大化基础上的分类器，只是后验概率的估计采用了KNN概率估计。
当K=1时，称为最近邻分类器，即将待分类的输入特征向量分类为距离最近的训练样本的类型。可以证明，用简单的最近邻分类器，当N→∞时，分类误差不大于最优分类误差的2倍； 若取较大的K，分类误差进一步降低。尽管简单，但在一些应用中KNN分类器可以获得可接受的分类效果。
KNN方法同样可以用于回归估计，若样本集D=xn,ynNn=1的标注是实数，对于一个给定的x，得到以其为中心的超球体，其内包括K个样本，记x的K个近邻样本集合为DK(x)，则KNN回归输出为

y^(x)=1K∑(xi,yi)∈DK(x)yi(3.5.3)

显然，这个输出近似等于E(y|x)，是利用K个近邻样本的标注值对E(y|x)的估计，E(y|x)为式(3.3.2)给出的回归问题的最优决策值。
*3.6概率图模型概述
机器学习中常使用概率模型描述数据，前面也看到可通过后验概率进行决策，总之，概率模型是机器学习中常用的工具。在机器学习中，常遇到高维随机向量x，当维数很高时，x的概率函数非常复杂，学习和推断过程也变得非常复杂，在这种情况下，若能将概率函数分解为多因子乘积的形式，将可能降低问题的复杂度。本节讨论用图的方式表示概率函数，称为概率图模型。概率图模型已经发展为一个相对独立且深入广博的子领域，限于本书的篇幅限制，本节仅给出其非常简略的介绍，对于希望更加深入了解概率图模型的读者，可参考在本章小结中列出的参考书。
本节简要介绍贝叶斯网络(或称为有向图模型)、无向图模型，及其学习和推断的原理。
3.6.1贝叶斯网络
图是由节点和边组成的，在有向图中边是带有方向的。贝叶斯网络是一个有向无环图(Directed Acyclic Graphs，DAG)，其中每个节点代表一个随机变量(更一般地，一个节点可代表一组随机变量，目前为了叙述简单，首先考虑一个节点仅代表一个随机变量的情况)，节点之间的连线表示两个随机变量之间有直接关系。


图3.6.1两个节点的
贝叶斯网络



观察一个最简单的图，如图3.6.1所示，只有两个节点a和b，分别表示两个同名的随机变量a和b，箭头从节点a指向节点b，表示节点a是节点b的父节点。节点a没有父节点，可以用p(a)的因子表示，而节点b有父节点a，可由条件概率p(b|a)表示该关系，则该图所表示的联合概率可表示为这两个因子的积，即

p(a,b)=p(a)p(b|a)(3.6.1)

式(3.6.1)正是联合概率的积公式。图3.6.1和式(3.6.1)都过于简单，难以说明更多问题。

2.1节给出了随机变量集x1,…,xD－1,xD的链式分解公式，重写如下。

p(x1,…,xD－1,xD)=p(xDxD－1,…,x1)…p(x2|x1)p(x1)(3.6.2)

为了表述简单和清楚，给出4个随机变量的例子，即

p(x1,x2,x3,x4)=p(x4|x3,x2,x1)p(x3x2,x1)p(x2|x1)p(x1)(3.6.3)

可用图3.6.2(a)的贝叶斯网络表示式(3.6.3)的因子分解形式。其中，节点x4有3个父节点x3,x2,x1，故表示为条件概率p(x4|x3,x2,x1)； 节点x3有两个父节点x2,x1，表示为条件概率p(x3x2,x1)； 节点x2只有一个父节点x1，表示为条件概率p(x2|x1)； x1节点没有父节点，故只表示为p(x1)，将所有这些因子相乘得到式(3.6.3)的链式分解。图3.6.2(a)是一个有全连接的图，即每两个节点之间都有连线(仅从小序号节点指向大序号节点)。对于更多的节点，这种全连接图对应式(3.6.2)的链式分解，即全连接图没有给出关于概率结构的特殊知识。
如果一种节点间连接的贝叶斯网络如图3.6.2(b)所示，即图中一些节点之间没有连线，说明这两个节点之间没有直接关系。x1和x2节点均没有父节点，故各自的因子为p(x1)和p(x2)，x3节点有两个父节点x2,x1，对应因子p(x3x2,x1)，x4节点只有一个父节点x3，对应因子p(x4|x3)，故图3.6.2(b)所表示的贝叶斯网络的联合概率函数为

p(x1,x2,x3,x4)=p(x4|x3)p(x3x2,x1)p(x2)p(x1)(3.6.4)

比较式(3.6.4)和式(3.6.3)，相当于图3.6.2(b)表示的概率结构将p(x4|x3,x2,x1)简化为p(x4|x3)，将p(x2|x1)简化为p(x2)。


图3.6.24个节点的贝叶斯网络实例


为了更清楚地理解图3.6.2(a)和图3.6.2(b)所表示的概率结构所带来的不同复杂度，以p(x1,x2,x3,x4)为例进行说明。设xi是离散的且只取两个值1或0，为了表示x1,x2,x3,x4的联合概率，需要24－1即15个参数(由于概率和为1，故减少1个参数)。若用图3.6.2(a)的有向图表示，对应式(3.6.3)的因子分解，在因子p(x4|x3,x2,x1)中，由于x3,x2,x1有8种组合，故描述p(x4=1|x3,x2,x1)需要8个参数(不需要用新参数描述p(x4=0|x3,x2,x1))，其他因子分别需要4、2、1个参数，共需要15个参数，全连接图模型与直接的联合概率表示对比没有减少参数。但对于图3.6.2(b)的模型，其对应的分解式(3.4.6)右侧中各因子分别需要2、4、1、1个参数，故描述其联合概率只需8个参数，需要的参数量明显下降。这里只是以D=4作为维数做了简单说明，在机器学习中，D表示的维数可能很大，如大于1000甚至更高，则利用概率图描述的结构，可能大大减少需要估计的模型参数。
对于一般的D个随机变量，记为x=x1,…,xD－1,xDT，其可以用具有D个节点的有向图表示，相应地，通过图可以将联合概率分解为

p(x)=∏Dk=1pxkxfk(3.6.5)

其中，对于节点xk，设其父节点集合为xfk，则每个因子写为条件概率pxkxfk。
例如，图3.6.3是一个具有D个节点的有向图模型，图中只有序号相邻的随机变量之间有连线，显然，该图表示的联合概率为

p(x)=px1∏Dk=2pxkxk－1(3.6.6)

仍假设xk是仅取两个值的离散随机变量，描述一般的p(x)需要2D－1个参数，若D=1000则参数多到无法存储，但式(3.6.6)或图3.6.3所表示的概率结构仅需要2D－1个参数，而这种只有近邻之间有直接相关性的情况，可代表许多数据类型。


图3.6.3一个只有相邻节点有连线的图结构


除了贝叶斯网络刻画的概率结构可能大大降低表示联合概率的复杂性外，一个有趣的应用是，可从图中直接判断两组随机变量子集之间是否在一个条件子集下是独立的。为此，我们首先考查3种基本结构。如图3.6.4所示，有3个随机变量，以及3种不同的连接方式。我们判断在给出x3时，x1和x2是否条件独立，即

px1,x2|x3Δpx1|x3px2|x3(3.6.7)




图3.6.43种基本结构



分别讨论3种连接方式。
(1) “尾尾”连接。
将图3.6.4(a)的连接方式称为“尾尾”连接，即从x1到x2的通道中，作为条件的节点x3连接的都是箭头的尾部。对于图3.6.4(a)，联合概率可写为

px1,x2,x3=px3px1|x3px2|x3(3.6.8)

由贝叶斯公式


px1,x2|x3=px1,x2,x3px3=px3px1|x3px2|x3px3

=px1|x3px2|x3(3.6.9)


可知在x3已知的条件下x1和x2是独立的

px1,x2|x3=px1|x3px2|x3(3.6.10)

注意，这种独立性是以x3作为条件。若没有x3作为条件，一般p(x1,x2)≠p(x1)p(x2)，可以说是x3的被观察到并作为条件“阻断”了x1和x2的联系，使x3作为条件时x1和x2条件独立。
(2) “尾头”连接。
图3.6.4(b)的连接方式称为“尾头”连接(反方向的“头尾”连接，结果相同)。类似地，可以验证： 在“尾头”连接的情况下，若在x3已知的条件下x1和x2是独立的，即式(3.6.10)成立。同样地，x3的被观察到并作为条件“阻断”了x1和x2的通道。

(3) “头头”连接。
图3.6.4(c)的“头头”连接方式与以上两种情况正好相反。可验证： 在不考虑条件的情况下，可得到

px1,x2=px1px2(3.6.11)

但在x3已知的条件下x1和x2是不独立的，即

px1,x2|x3≠px1|x3px2|x3(3.6.12)

与前两种情况相反，x3不作为条件时，它阻断从了x1和x2的通道，使之相互独立； 但当x3作为条件时，它不再阻断x1和x2的通道，使x1和x2不条件独立。
以上对3种基本连接方式给出了其独立性判断，对于“尾头”和“头头”连接的验证留作习题。
从以上3种基本连接方式出发，可给出更一般的条件独立的判断方法，称为“D分离”(Dseparation)条件。对于一个给定的贝叶斯网络，设有3个节点集合A,B,C，各集合不相交(两两之间交集为空)，将集合C作为条件，讨论集合A和B的条件独立性。

若通过一些中间节点(不考虑连线方向)连接了集合A中的一个节点和集合B中的一个节点，则称A和B之间有一条通道。如果满足以下条件之一，则称集合C阻断了一条通道。

(1) 遇到“头尾”或“尾尾”节点，该节点属于集合C。
(2) 遇到“头头”节点，该节点或其子孙节点均不属于集合C。
若A和B之间的全部通道都被集合C阻断了，则称C条件下集合A和B独立，即

pA,BC=pACpBC

D分离条件给出了多个节点组成的随机变量子集之间的条件独立关系，可在更复杂的有向图中进行条件独立性判断。下面给出两个实例，说明通过有向图模型建模独立性关系，这两个实例对应的学习算法均为机器学习中有影响的经典算法。
1. 朴素贝叶斯模型
讨论的第1个实例是朴素贝叶斯模型。例如,设计一个垃圾邮件检测器，相当于一个分类问题，输入特征向量为x=x1,…,xD－1,xDT，输出为y，y=1表示垃圾邮件，y=0表示正常邮件。预设一个关键词汇表，共有D个词，当词汇表中第i个词出现在邮件中，则对应xi=1，否则xi=0，即xi是离散随机变量，仅有两个取值。描述联合概率p(x,y)需要2D+1－1个参数，由于词汇表单词数目D比较大(如数千量级)，描述联合概率非常复杂。因此，我们采用简化的结构，给出如图3.6.5所示的关系，即当检测器输出y作为条件时，由y表示的是否为垃圾邮件分别对各输入分量xi的概率有影响。例如，x102代表词汇“化妆品”，当y=1时，x102=1的概率更高，而各词汇的概率互相没有影响。图3.6.5给出了这种假设的贝叶斯网络表示，由D分离原则，y作为条件时各xi的条件概率是互相独立的(“尾尾”连接)，即联合概率为

p(x,y)=p(y)p(x|y)=p(y)∏Dk=1pxk|y(3.6.13)

为了完整描述式(3.6.13)的联合概率，只需要以下参数集


μi1=Δpxi=1y=1

μi0=Δpxi=1y=0i=1,2,…,D

py=1=π
(3.6.14)


即只需要2D+1个参数。若通过样本集学习得到式(3.6.14)的参数，则对于给出的一个新的邮件，抽取其特征向量x，由后验概率p(y|x)可判断该邮件是否为垃圾邮件。我们将在5.4节给出朴素贝叶斯学习的详细讨论，其基础就是图3.6.5的概率结构假设。


图3.6.5朴素贝叶斯模型


本例为了直观说明问题，只假设了xi是仅取两个值的离散随机变量，实际上更一般的朴素贝叶斯假设只限制于图3.6.5的结构，至于xi是离散变量还是连续变量，都有同样的独立条件。

2. 隐马尔可夫模型
用贝叶斯网络建模的第2个实例是隐马尔可夫模型(Hidden Markov Models,HMM)。HMM用于建模序列数据，即按照时间顺序排列的数据向量x1,x2,…,xN，具有时序关系，这里每个xi自身是一个向量，即xi+1是在xi之后出现的，相互具有时间相关性。为了描述xi+1，需要条件概率

pxi+1xi,xi－1,…,x1(3.6.15)

即xi+1的取值概率与从xi起直到x1的所有以前向量均有关系。建模这样的序列关系，目前最常用的技术是循环神经网络(RNN)，在RNN广泛应用之前，HMM是序列建模的最常用方法。
为了描述序列的时间依赖性，又使问题处理简单，一个有效的方法是引入一系列隐变量。对于序列建模，可引入离散隐变量zi。所谓隐变量，是指无法观测的随机变量，但其与序列变量xi直接相关。可通过一系列隐变量zi产生一系列观测向量xi，将序列向量的产生用图3.6.6的贝叶斯网络表示。注意，与前面的例子相比，每个节点表示一个随机向量，而不是单一的随机变量。对具有任意时间依赖关系的序列进行建模，建立序列一般的时间依赖关系，可以利用隐变量带来的条件独立性以便于表示。例如，由图3.6.6中连接可见，从zn－1到zn+1经过zn，这是“尾头”连接，故满足条件独立性

pzn+1,zn－1zn=pzn+1znpzn－1zn(3.6.16)

类似地，如下条件独立性成立。

pxn,xn－1zn=pxnznpxn－1zn(3.6.17)

图3.6.6的图模型表示了HMM，由HMM图模型的节点因子关系，可得到联合概率为

px1,…,xN,z1,…，zN=pz1∏Nn=2pznzn－1∏Nn=1pxnzn(3.6.18)



图3.6.6HMM结构



在实际中，由于只能观测到多组序列样本x1,x2,…,xN集合，可由样本集估计HMM的参数，由于引入隐变量带来的式(3.6.18)的因子分解，可导出有效的参数学习算法。对隐变量的参数学习的一种有效方法是采用期望最大算法(EM)，本书在第12章详细讨论EM算法，用EM算法估计HMM参数的学习算法可参考本章小结中推荐的参考书。
3.6.2无向图模型
另外一种概率图模型是无向图，也称为马尔可夫随机场或马尔可夫网络，其节点表示一个或一组随机变量，两个节点之间通过无箭头的连线连接，表示两个节点之间有直接联系。图3.6.7所示为一个具有5个节点的无向图的示例。


图3.6.7无向图示例


无向图同样可以描述节点之间的条件独立性和概率函数的因子分解特性。无向图对于节点子集之间的条件独立性的判断更加简单。例如，图3.6.7中，设3个随机变量子集分别为A={x1}，B={x2,x3}和C={x4,x5}，以B作为条件，考查A和C的条件独立性。若从子集A的节点到子集C的节点的通道，都需要通过子集B的节点，则说明B阻断了A和C，则B作为条件时A和C独立； 否则，只要有一条通道不经过子集B的节点，B就没有阻断A和C的通路，则B作为条件时A和C不独立。图3.6.7的例子中，B阻断了A和C的通路，故有p(A,B|C)=p(A|C)p(B|C)。在无向图的条件独立性判断中，不需要区分“头头”或“尾尾”之类的区别，将更加简单。


为了通过无向图表示概率的因子分解，引入“团”(Clique)的概念，一个团是指一个节点子集，该子集中的任何一对节点间有连线。进一步，可引入“最大团”(Maximal Clique)的概念，对于一个给定的无向图，一个最大团是指一个节点子集构成的团，图中不再有一个其他节点能够与该子集构成更大的团。有这些定义，可见图3.6.7的无向图有如下子集构成了团： x1,x2，x2,x3，x1,x3，x2,x4，x3,x4，x2,x5，x4,x5，x1,x2,x3，x2,x3,x4，x2,x4,x5； 而最大团有3个： x1,x2,x3，x2,x3,x4，x2,x4,x5。用xc表示一个最大团，例如，本例中x1=x1,x2,x3，x2=x2,x3,x4，x3=x2,x4,x5，则可由最大团的势函数ψcxc作为因子，将无向图所表示的概率函数表示为各最大团势函数的积，即

p(x)=1Z∏cψcxc(3.6.19)

其中，Z为归一化常数。若x是离散的，则

Z=∑x∏cψcxc(3.6.20)

若x是连续的，只需要将求和改为积分即可。为了使p(x)为合格的概率函数，要求势函数ψcxc≥0。故一种常用的势函数由指数函数来定义，即

ψcxc=exp－E(xc)(3.6.21)

其中，E(xc)称为团的能量函数。用指数函数表示势函数的概率函数称为玻尔兹曼分布(Boltzmann Distribution)。将式(3.6.21)代入式(3.6.19)得到指数势函数的概率表示为


p(x)=1Zexp－∑cE(xc)=1Zexp－E(x)(3.6.22)

其中，E（x）为总能量函数。

E(x)=∑cE(xc)(3.6.23)

对于图3.6.7的无向图，用指数函数可以将概率函数写为


p(x)=1Zexp［－E(x1,x2,x3)］exp［－E(x2,x3,x4)］exp［－E(x2,x4,x5)］

=1Zexp－E(x1,x2,x3)－E(x2,x3,x4)－E(x2,x4,x5)


在实际中，根据不同的应用需求，可选择不同的能量函数(及其参数)，无向图模型有非常灵活的构成方式，并已获得许多应用成果。
下面通过一个例子说明无向图的建模过程，主要说明怎样根据应用选择能量函数和节点连接关系，从而由团因子构成概率函数。注意到，选择能量函数后，式(3.6.19)的因子相乘变化为式(3.6.23)的能量和的形式，以下例子中，直接使用能量和形式。
例3.6.1条件随机场模型。
以信息检索的一个应用场景为例进行说明，不关注信息检索的细节，只简单说明一下变量的背景，主要看怎样构成一个概率函数。这里讨论的条件随机场是一种对序列数据进行学习的概率模型，其


图3.6.8作为无向图模型的
条件随机场实例



定义了给定观测序列后输出序列的条件分布。在信息检索的模型学习中，对于给出的一个查询q，样本集给出一组文档，用向量xi表示一个文档的特征向量(输入向量)，yi表示文档对于该查询的得分(高得分说明该文档与查询匹配度高)，将yi看作输出(学习过程中相当于标注值)，对于一个查询给出的一组文档，用X=x1,x2,…,xn表示一个查询对应的文档集合的输入向量，用y=y1,y2,…,yn表示各文档对应的得分输出，在训练集中每个文档得分输出由专家打分作为标注值。用无向图的一个节点分别表示xi和yi，假设xi和yi是有连接的，一些yi之间可能有连接(但只假设两两之间有部分连接)。这种连接关系使xi,yi为团，另外一些有连接的yi,yj（i≠j）构成团。无向图结构如图3.6.8所示。

所谓条件随机场，是直接由图3.6.8的无向图表示X作为条件的y的概率函数，由团的组成可得

pyX=1ZXexp－∑i∑Kk=1αkfk(yi,xi)－∑i,jβgyi,yj(3.6.24)

实际上，对于团xi,yi定义了一组能量函数的和∑Kk=1αkfk(yi,xi)，对于团yi,yj（i≠j），定义了能量函数βgyi,yj，αk和β是需要学习的参数。由于是建模条件概率，故归一化因子ZX写为X的函数。由于得分y是连续值，故ZX的计算式为

ZX=∫yexp－∑i∑Kk=1αkfk(yi,xi)－∑i,jβgyi,yjdy(3.6.25)

在实际应用中，fk(yi,xi)和gyi,yj函数可适当选择，以获得良好的效果，一类信息检索的应用情况下，效果良好的一种函数选择为


fk(yi,xi)=yi－xi,k2(3.6.26)

gyi,yj=12Si,jyi－yj2(3.6.27)


其中，xi,k为xi第k分量的值； K为xi的维数； Si,j为预定的权系数，评价两个文档的相似性。在学习阶段，由样本集Xq,yqNq=1可学习模型的参数，当实际对新的输入X做检索时，可推断输出y为


y=argmaxy［pyX］

=argmaxy－∑i∑Kk=1αkfk(yi,xi)－∑i,jβgyi,yj(3.6.28)


本例给出的是无向图应用的一个完整工作的一部分，对于其学习或推断的细节，感兴趣的读者可阅读相关文献见本书参考文献［101］。。

3.6.3图模型的学习与推断
对概率图模型的参数可进行学习，利用已确定了参数的概率图模型可进行推断，本节对此问题仅进行简要介绍。

1. 学习
构成图模型的概率表达式中包含待确定参数。例如，在朴素贝叶斯实例中，式(3.6.14)所示的一组参数； 以及在图3.6.8所示的无向图实例中，式(3.6.24)中的参数αk和β。

首先讨论有向图的参数学习。为了表示图模型中包含的参数，可将有向图的概率表示（式(3.6.5)）重新表示为以下参数化形式。


p(x； θ)=∏Dk=1pxkxfk； θk(3.6.29)

在机器学习应用中，需通过IID的样本集X=x(n)Nn=1学习图模型中的参数，这里为了避免与图中变量的下标混淆，用上标(n)表示样本序号。当样本集确定后，关于参数的对数似然函数表示为

logpX； θ=∑Nn=1logp(x(n)； θ)=∑Nn=1∑Dk=1logpx(n)kx(n)fk； θk(3.6.30)

由于因子的参数θk是各自独立的，故最大似然的参数求解为

θ^k=argmaxθk∑Nn=1logpx(n)kx(n)fk； θk，k=1,2,…,D(3.6.31)

对于无向图，若采用指数函数表示的势函数，则式(3.6.22)式重写为

px； θ=1Zθexp－∑cE(xc； θc)(3.6.32)

注意到，由归一化因子的定义可知，Zθ是随θ变化的，其对数似然函数为

logpX； θ=∑Nn=1logp(x(n)； θ)=－∑Nn=1∑cE(x(n)c； θc)－NZθ(3.6.33)

5.4节将对朴素贝叶斯假设给出其参数学习的详细过程，对于图3.6.8的无向图实例，其学习过程可参考相关文献见本书参考文献［101］。。
当在图模型中引入隐变量时，如HMM，则用EM算法学习模型参数是有效的，EM算法的详细介绍可参考12.2节。
2. 推断
当通过学习过程确定了图模型的参数后，可通过图模型进行推断。所谓推断，是指给出图模型表示的随机变量集合x的部分观测值后，去推断另一些感兴趣的变量的条件概率。这里可将x分为互不重叠的3个子集x=xo,xq,xu，其中xo表示本次推断观测到取值的变量集合； xq表示本次推断感兴趣的变量集合； xu表示本次推断时既没有观测到取值也不感兴趣的变量集合。所谓一次推断的任务是从pxq,xo,xu的表示出发，计算条件概率pxqxo，由贝叶斯公式可得

pxqxo=pxq,xopxo=∑xupxq,xo,xu∑xq,xupxq,xo,xu(3.6.34)

式(3.6.34)预设了随机变量是离散的，若需要边际化的随机变量是连续的，用积分替代以上求和。
以上推断过程中，若每个随机变量可取K个值，有V个变量，直接运算需要的计算复杂度为OKV，当V很大时，运算开销非常大。若利用图模型的消息传递，可有效控制计算复杂度。若概率图是如图3.6.3所示的链图，计算复杂度可限制在OKV。若概率图是一种宽度较小的树形结构，则仍可大量节省运算量。在图模型上有效计算边际概率的算法之一是和积算法(SumProduct)，其详细介绍可参考相关文献见本书参考文献［13，93］。。
若在一个简单的二分类问题中使用图模型，可将x分为两个子集x=xi,y，这里用xi表示分类问题的输入特征向量，y表示分类输出，仅取0和1两个值，则给出输入xi，y的条件概率为

pyxi=py,xipy=0,xi+py=1,xi(3.6.35)

若已由图模型的参数学习确定了py,xi，则分类输出y的后验概率pyxi的计算变得较为简单。有了pyxi，由3.2节的决策原理确定输出的类型。5.4节的朴素贝叶斯方法将描述一个简单图模型的建模、学习和推断的完整实例。
概率图模型涉及的内容广泛而深刻，除了对于一个给定模型的学习和推断外，还可能从数据中学习出有效的图结构，本书仅给出了图模型的一个极其简略的介绍，有兴趣的读者可进一步阅读本章小结中推荐的参考书。
3.7本章小结
决策是机器学习中一个相对独立的部分，通过训练过程确定了一个机器学习模型，若该模型是概率模型，当有一个新的输入特征向量时，可在推断过程计算出分类或回归的后验概率，则决策过程确定最终的输出。对于分类问题，若各类错误是同等重要的，则简单的最大后验即可确定分类输出； 对于回归问题，则计算后验期望并作为回归输出。通过基本的决策理论讨论了高斯分布和KNN方法的决策实例。
概率结构对许多学习算法和推断算法有重要影响，概率图模型以相对直观的方法描述了概率结构，概率图模型已发展出非常完整的理论和算法，并不断与其他机器学习方法相结合扩展出新的技术，本节只给出了非常简略的介绍。
多个领域的著作均对决策理论给出了深入讨论，统计学的著作中有对决策理论的细致讨论，如Casella等的Statistical Inference； 侧重统计模式识别的著作常有对决策理论的详细讨论，如Duda等的Pattern Classification； 信号处理类的著作中，也有很深入的决策理论的讨论，如Poor的An Introduction to Signal Detection and Estimation。对于概率图模型，Bishop的Pattern Recognition and Machine Learning和Murphy的Machine Learning这两本经典机器学习著作都给出了中等深度的介绍，也都给出了通过EM算法和概率图模型估计HMM参数的算法； 而Koller等的著作Probabilistic Graphical Models： Principles and Techniques则给出了概率图模型更加全面、系统和深入的介绍。
习题
1. 对于特征向量x是一个一维标量的情况，设样本集中只有两种类型，类条件概率分别为


p(xC1)=12×(2π)1/2exp－18x+12

p(xC2)=12×(2π)1/2exp－18x－22


且pC1=pC2=0.5。
(1) 在错误分类率最小意义下，给出将新的输入x判决为C1或C2的判决边界。
(2) 在问题(1)求出的判决边界的条件下，求总的错误分类率。
2. 试推导： 由式(3.4.22)的定义可得到式(3.4.25)。
3. 对于高斯分布的多分类问题，证明其后验概率pCi|x可表示为

pCi|x=pxCipCi∑Kk=1pxCkp(Ck)=expai∑Kk=1expak

其中，ak=lnpxCkp(Ck)，并证明

ai=gi(x)=xTWix+wTix+wi0i=1,…,K

其中，系数如式(3.4.27)所示。
4. 一个二分类问题，特征向量x是二维的，有样本集


D={xn,ynNn=1

=0.5,1.5T,1,1.5,1.5T,1,0.5,0.5T,1,1.5,0.5T,1,

1.5,0.5T,0,2.5,0.5T,0,1.5,－0.5T,0,2.5,－0.5T,0


类条件概率服从高斯分布，且Σ1=Σ2=Σ。
(1) 求通过样本得到的判别函数g(x)，在x平面上画出分类为C1和C2的区间。 
(2) 求后验概率p(C1|x)表达式。 
(3) 对于新的特征输入x=2.0,－0.3T，可分为哪一类？计算后验概率p(C1|x)。
5. 图3.6.4的3种基本连接中，对于图3.6.4(b)的“尾头”连接方式，证明： 在x3已知的条件下x1和x2是独立的； 对于图3.6.4(c)的“头头”连接方式，证明： 在不考虑条件的情况下，可得到

px1,x2=px1px2

但在x3已知的条件下x1和x2是不独立的，即

px1,x2|x3≠px1|x3px2|x3

6. 如图所示，利用D分离原则，证明： 对于图(a)，p(a,b|c)≠p(a|c)p(b|c)； 对于图(b)，p(a,b|f)=p(a|f)p(b|f)。


第6题图