2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 6章 贝叶斯学习
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
贝叶斯推理提供了一种概率手段，基于如下的假定：待考察的量遵循某概率分布，且可根据这些概率及已观察到的数据进行推理，以作出最优的决策。
贝叶斯推理为衡量多个假设的置信度提供了定量的方法
贝叶斯推理为直接操作概率的学习算法提供了基础，也为其他算法的分析提供了理论框架
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
贝叶斯学习算法与机器学习相关的两个原因：
– 贝叶斯学习算法能够计算显示的假设概率，比如朴素贝叶斯分类
– 贝叶斯方法为理解多数学习算法提供了一种有效的手段，而这些算法不一定直接操纵概率数据，比如
Find-S
候选消除算法
神经网络学习：选择使误差平方和最小化的神经网络
推导出另一种误差函数：交叉熵
分析了决策树的归纳偏置
考察了最小描述长度原则
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
贝叶斯学习方法的特性
观察到的每个训练样例可以增量地降低或升高某假设的估计概率。而其他算法会在某个假设与任一样例不一致时完全去掉该假设
先验知识可以与观察数据一起决定假设的最终概率，
先验知识的形式是,1）每个候选假设的先验概率； 2）
每个可能假设在可观察数据上的概率分布
贝叶斯方法可允许假设做出不确定性的预测
新的实例分类可由多个假设一起做出预测，用它们的概率来加权
即使在贝叶斯方法计算复杂度较高时，它们仍可作为一个最优的决策标准衡量其他方法
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
贝叶斯方法的难度
难度之一：需要概率的初始知识，当概率预先未知时，可以基于背景知识、预先准备好的数据以及基准分布的假定来估计这些概率
难度之二：一般情况下，确定贝叶斯最优假设的计算代价比较大（在某些特定情形下，这种计算代价可以大大降低）。
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
内容安排
介绍贝叶斯理论
定义极大似然假设和极大后验概率假设
将此概率框架应用于分析前面章节的相关问题和学习算法
介绍几种直接操作概率的学习算法
– 贝叶斯最优分类器
– Gibbs算法
– 朴素贝叶斯分类器
讨论贝叶斯信念网，这是存在未知变量时被广泛使用的学习算法
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
贝叶斯法则
机器学习的任务：在给定训练数据 D时，确定假设空间 H中的最佳假设。
最佳假设：一种方法是把它定义为在给定数据
D以及 H中不同假设的先验概率的有关知识下的最可能假设
贝叶斯理论提供了一种计算假设概率的方法，
基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
先验概率和后验概率
用 P(h)表示在没有训练数据前假设 h拥有的初始概率。 P(h)被称为 h的先验概率。
先验概率反映了关于 h是一正确假设的机会的背景知识
如果没有这一先验知识，可以简单地将每一候选假设赋予相同的先验概率
类似地,P(D)表示训练数据 D的先验概率，
P(D|h)表示假设 h成立时 D的概率
机器学习中，我们关心的是 P(h|D)，即给定 D时
h的成立的概率，称为 h的后验概率
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
贝叶斯公式
贝叶斯公式提供了从先验概率 P(h),P(D)
和 P(D|h)计算后验概率 P(h|D)的方法
P(h|D)随着 P(h)和 P(D|h)的增长而增长，
随着 P(D)的增长而减少，即如果 D独立于
h时被观察到的可能性越大，那么 D对 h的支持度越小
)( )()|()|( DP hPhDPDhP?
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
极大后验假设
学习器在候选假设集合 H中寻找给定数据
D时可能性最大的假设 h,h被称为极大后验假设（ MAP）
确定 MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下最后一步，去掉了 P(D)，因为它是不依赖于 h的常量
)()|(m a xa r g)( )()|(m a xa r g)|(m a xa r g hPhDPDP hPhDPDhPh HhHhHhM A P
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
极大似然假设
在某些情况下，可假定 H中每个假设有相同的先验概率，这样式子 6.2可以进一步简化，只需考虑 P(D|h)来寻找极大可能假设。
P(D|h)常被称为给定 h时数据 D的似然度，而使
P(D|h)最大的假设被称为极大似然假设
假设空间 H可扩展为任意的互斥命题集合，只要这些命题的概率之和为 1
)|(m a xa rg hDPh HhML
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
举例：一个医疗诊断问题
有两个可选的假设：病人有癌症、病人无癌症
可用数据来自化验结果：正 +和负 -
有先验知识：在所有人口中，患病率是 0.008
对确实有病的患者的化验准确率为 98%，对确实无病的患者的化验准确率为 97%
总结如下
P(cancer)=0.008,P(?cancer)=0.992
P(+|cancer)=0.98,P(-|cancer)=0.02
P(+|?cancer)=0.03,P(-|?cancer)=0.97
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
举例：一个医疗诊断问题（ 2）
问题：假定有一个新病人，化验结果为正，是否应将病人断定为有癌症？求后验概率 P(cancer|+)和 P(?cancer|+)
利用式子 6.2找到极大后验假设
– P(+|cancer)P(cancer)=0.0078
– P(+|?cancer)P(?cancer)=0.0298
– hMAP=?cancer
确切的后验概率可将上面的结果归一化以使它们的和为 1
– P(canner|+)=0.0078/(0.0078+0.0298)=0.21
– P(?cancer|-)=0.79
贝叶斯推理的结果很大程度上依赖于先验概率，另外不是完全接受或拒绝假设，只是在观察到较多的数据后增大或减小了假设的可能性
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
基本概率公式表
乘法规则：
P(A?B)=P(A|B)P(B)=P(B|A)P(A)
加法规则,P(A?B)=P(A)+P(B)-P(A?B)
贝叶斯法则,P(h|D)=P(D|h)P(h)/P(D)
全概率法则：如果事件 A1...An互斥，且满足,则1)(1ni iAP ni ii APABPBP 1 )()|()(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
贝叶斯法则和概念学习
贝叶斯法则为计算给定训练数据下任一假设的后验概率提供了原则性方法，因此可以直接将其作为一个基本的学习方法：计算每个假设的概率，再输出其中概率最大的。这个方法称为
Brute-Force贝叶斯概念学习算法。
将上面方法与第 2章介绍的概念学习算法比较，
可以看到：在特定条件下，它们学习得到相同的假设，不同的是第 2章的方法不明确计算概率，而且效率更高。
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
Brute-Force贝叶斯概念学习
概念学习问题：有限假设空间 H定义在实例空间 X上，任务是学习某个目标概念 c。
Brute-Force MAP学习算法
– 对于 H中每个假设 h，计算后验概率
– 输出有最高后验概率的假设
上面算法需要较大计算量，因为它要计算每个假设的后验概率，对于大的假设空间显得不切实际，但是它提供了一个标准以判断其他概念学习算法的性能
)( )()|()|( DP hPhDPDhP?
)|(m a xa rg DhPh HhM A P
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
特定情况下的 MAP假设
假定
– 训练数据 D是无噪声的，即 di=c(xi)
– 目标概念 c包含在假设空间 H中
– 每个假设的概率相同
求得
– 由于所有假设的概率之和是 1，因此
– 由于训练数据无噪声，那么给定假设 h时，与 h一致的 D的概率为 1，不一致的概率为 0，因此
|| 1)( HhP?
o th erw isexhddhDP iii )(,01)|(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
特定情况下的 MAP假设（ 2）
考虑 Brute-Force MAP算法的第一步
– h与 D不一致，
– h与 D一致，,
VSH,D是关于 D的变型空间（见第 2章，即与
D一致的假设集）
0)( )(0)|( DP hPDhP
||
1
||
||
||
1
)(
||
11
)|(
,,DHDH VS
H
VS
H
DP
HDhP
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
特定情况下的 MAP假设（ 3）
P(D)的推导
P(D)
假设的概率演化情况如图 6-1所示，初始时所有假设具有相同的概率，当训练数据逐步出现后，
不一致假设的概率变为 0，而整个概率的和为 1，
它们均匀分布到剩余的一致假设中
每个一致的假设都是 MAP假设
||
||
||
1
1
||
1
0
||
1
1
)()|(
,
,
,,
H
VS
H
HH
hPhDP
DH
VSh
VShVSh
Hh
ii
DHi
DHiDHi
i
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
MAP假设和一致学习器
一致学习器：如果某个学习器输出的假设在训练样例上为 0错误率，则称为一致学习器
如果 H上有均匀的先验概率，且训练数据是确定性和无噪声的，任意一致学习器将输出一个 MAP假设
Find-S算法按照特殊到一般的顺序搜索架设空间 H，并输出一个极大特殊的一致假设，因此可知在上面定义的 P(h)和 P(D|h)概率分布下，它输出 MAP假设
更一般地，对于先验概率偏袒于更特殊假设的任何概率分布,Find-S输出的假设都是 MAP假设
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
MAP假设和一致学习器（ 2）
贝叶斯框架提出了一种刻画学习算法行为的方法，即便该学习算法不进行概率操作，通过确定算法输出最优假设时使用的概率分布 P(h)和
P(D|h)，可以刻画出算法具有最优行为时的隐含假定
使用贝叶斯方法刻画学习算法，与揭示学习器中的归纳偏置在思想上是类似的
在第 2章，将学习算法的归纳偏置定义为断言集合 B，通过它可充分地演绎推断出学习器所执行的归纳推理结果，即学习器的输出是由其输入和隐含的归纳偏置所演绎得出的
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
MAP假设和一致学习器（ 3）
贝叶斯解释对于描述学习算法中的隐含假定提供了另一种方法，用基于贝叶斯理论的一个等效的概率推理系统来建模
贝叶斯解释隐含的假定形式为,H上的先验概率由 P(h)分布给出，数据拒绝或接受假设的强度由 P(D|h)给出
在已知这些假定的概率分布后，一个基于贝叶斯理论的概率推理系统将产生等效于 Find-S、
候选消除等算法的输入 -输出行为
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
极大似然和最小误差平方假设
前面分析表明：某些学习算法即使没有显示地使用贝叶斯规则，或以某种形式计算概率，但它们输出的结果符合贝叶斯原理，是一个 MAP假设
通过简单的贝叶斯分析，可以表明在特定前提下，任一学习算法如果使输出的假设预测和训练数据之间的误差平方和最小化，它将输出一极大似然假设
上面结论的意义是，对于许多神经网络和曲线拟合的方法，如果它们试图在训练数据上使误差平方和最小化，此结论提供了基于贝叶斯的理论依据
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
极大似然和最小误差平方假设
（ 2）
问题框架：
– 学习器 L工作在实例空间 X和假设空间 H上,H中的假设为 X上定义的某种实数值函数。
– L面临的问题是学习一个从 H中抽取出的未知目标函数 f，给定 m个训练样例的集合，每个样例的目标值被某随机噪声干扰，此随机噪声服从正态分布
– 更精确地讲，每个训练样例是序偶 <xi,di>，
di=f(xi)+ei,ei是代表噪声的随机变量，假定 ei的值是独立抽取的，并且它们的分布服从 0均值的正态分布
– 学习器的任务是在所有假设有相等的先验概率前提下，输出极大似然假设（即 MAP假设）
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
极大似然和最小误差平方假设
（ 3）
用一个简单情况，即线性函数来说明问题。如图 6-2所示，实线表示线性目标函数 f，实点表示有噪声的训练样例集，虚线对应有最小平方训练误差的假设 hML，即极大似然假设。
对于 e这样的连续变量上的概率，使用概率密度表示概率分布，它在所有值上的积分为 1，
用小写的 p表示。有限概率 P有时又称为概率质量
概率密度函数,)(1lim)( 0000 xxxPxp
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
极大似然和最小误差平方假设
（ 4）
假定有一固定的训练实例集合，因此只考虑相应的目标值序列
D=<d1...dm>，这里 di=f(xi)+ei。
假定训练样例是相互独立的，给定 h时，可将 P(D|h)写成各 p(di|h)
的积
如果误差 ei服从 0均值和未知方差?2的正态分布，那么每个 di服从均值为 f(xi)，方差不变的正态分布。因此，
p(di|h)可写为方差?2、均值 f(xi)的正态分布
使用表 5-4中的正态分布公式并将相应的参数代入，由于概率 di的表达式是在 h为目标函数 f的正确描述条件下的，所以替换?=f(xi)=h(xi)
mi iHhML hdph 1 )|(m a xa rg
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
极大似然和最小误差平方假设
（ 5）
hML
上式说明了极大似然假设等价于使训练值和假设预测值之间的误差的平方和最小的那个假设
这个结论的前提是：训练值等于真实目标值加上随机噪声，其中随机噪声从一个均值为 0的正态分布中独立抽取
m
i
ii
Hh
m
i
ii
Hh
m
i
ii
Hh
xhdm
iHh
m
i
d
Hh
xhd
xhd
xhd
e
e
ii
i
1
2
1
2
2
1
2
22
))((
2
1
1
2
1
)(
2
1
2
))((mina r g
))((
2
1
m a xa r g
))((
2
1
2
1
lnm a xa r g
2
1
m a xa r g
2
1
m a xa r g
2
2
2
2
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
采用正态分布的合理性
数学计算的简洁性
对许多物理系统的噪声都有良好的近似
第 5章中心极限定律显示，足够多的独立同分布随机变量的和服从正态分布
由许多独立同分布的因素的和所生成的噪声将成为正态分布（当然，现实中不同的分量对噪声的贡献也许不是同分布的）
使误差平方最小化的方法经常被用于神经网络、曲线拟合及其他许多实函数逼近的算法中
上面的分析只考虑了训练样例的目标值中的噪声，而没有考虑实例属性值的噪声
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
用于预测概率的极大似然假设
问题框架：
– 学习一个不确定性函数 f,X?{0,1}，它有两个离散的值输出
– 这种不可预测性来源于未能观察到的因素，
导致目标函数的输出是输入的概率函数
学习得到的神经网络（或其他实函数学习器）的输出是 f(x)=1的概率，表示为
f’,X?[0,1]，即 f’=P(f(x)=1)
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
用于预测概率的极大似然假设
（ 2）
Brute-Force法
– 首先收集对 x的每个可能值观察到的 1和 0的频率，然后训练神经网络，对每个 x输出目标频率
可以直接从 f的训练样例中训练神经网络，
然后推导出 f’的极大似然假设
– D={<x1,d1>...<xm,dm>}
– mi iiimi ii xPxhdPhdxPhDP 11 )(),|()|,()|(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
用于预测概率的极大似然假设
（ 3）
–
–
– hML
– 式子 6.13与熵函数的一般式相似，因此它的负值常称为交叉熵
ii didi
i
i
i
iii xhxhddxhxhxhdP 1))(1()(01)(1 )(),|(
mi ididi xPxhxhhDP ii1 1 )())(1()()|(
m
i
iiii
Hh
m
i
d
i
d
i
Hh
m
i
i
d
i
d
i
Hh
xhdxhd
xhxh
xpxhxh
ii
ii
1
1
1
1
1
))(1ln ()1()(lnm a xa r g
))(1()(m a xa r g
)())(1()(m a xa r g
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
在神经网络中梯度搜索以达到似然最大化
前面讨论了利用式子 6.13求极大似然假设，现用 G(h,D)表示，为神经网络学习推导一个权值训练法则，使用梯度上升法使 G(h,D)最大化
考虑简单的情况，假定神经网络从一个单层的
sigmoid单元建立，则
m
i jk
i
ii
ii
m
i jk
i
i
iiii
m
i jk
i
ijk
w
xh
xhxh
xhd
w
xh
xh
xhdxhd
w
xh
xh
DhG
w
DhG
1
1
1
)(
))(1)((
)(
)(
)(
) ) )(1ln ()1()(ln(
)(
)(
),(),(
ijkiiijkijki xxhxhxxw xh ))(1)(()(')(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
在神经网络中梯度搜索以达到似然最大化（ 2）
因为要使 P(D|h)最大化而不是最小化，因此执行梯度上升搜索，而不是梯度下降搜索。
与反向传播更新法则对比
– 使误差平方最小化的法则寻找到极大似然假设的前提是：训练数据可以由目标函数值加上正态分布噪声来模拟
– 使交叉熵最小化的法则寻找极大似然假设基于的前提是：观察到的布尔值为输入实例的概率函数
mi ijkiijk xxhdw DhG 1 ))((),(
jkjkjk www
m
i ijkiijk xxhdw 1 ))((?
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
最小描述长度准则
奥坎姆剃刀可以概括为：为观察到的数据选择最短的解释
此处给出一个贝叶斯分析，提出最小描述长度准则，根据信息论中的基本概念来解释 hMAP的定义
上式可以解释为在特定的假设编码表示方案上
“优先选择短的假设”
)(lo g)|(lo gm ina r g
)(lo g)|(lo gm a xa r g
)()|(m a xa r g
22
22
hPhDP
hPhDP
hPhDPh
Hh
Hh
Hh
M A P
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
最小描述长度准则（ 2）
信息论中的编码理论
– 设想要为随机传送的消息设计一个编码，其中遇到消息 i的概率是 pi
– 感兴趣的是，使得传输随机信息所需的最小期望传送位数的编码
– 直观上，为使期望的编码长度最小，可能性大的消息应该赋予较短的编码
– Shannon & Weaver证明了最优编码对消息 i的编码长度为 -log2pi
– 使用代码 C来编码消息 i所需的位数被称为消息 i关于
C的描述长度，记为 LC(i)
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
最小描述长度准则（ 3）
使用编码理论的结论来解释等式 6.16
– -log2P(h)是在假设空间 H的最优编码下 h的描述长度。
换言之，这是假设 h使用其最优表示时的大小
–,CH为假设空间 H的最优编码
– -log2P(D|h)是在给定假设 h时，训练数据 D的描述长度，,CD|h是假定发送者和接送者都知道假设 h时描述数据 D的最优编码
– 因此式子 6.16显示,hMAP是使假设描述长度和给定假设下数据描述长度之和最小化的假设
最小描述长度准则：
)(log)( 2 hPhL HC
)|(lo g)|( 2| hDPhDL hDC
)|()(m ina r g 21 hDLhLh CCHhM D L
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
最小描述长度准则（ 4）
如果选择 C1为假设的最优编码 CH,C2为最优编码 CD|h，
那么 hMDL=hMAP
可将 MDL准则想象为选择最短的方法来重新编码训练数据，其中不仅计算假设的大小，并且计算给定假设时编码数据的附加开销
将 MDL准则应用于决策树，如何选择假设和数据的表示 C1和 C2?
– 对于 C1，很自然地选择某种明确的决策树编码方法，其中描述长度随着树中节点和边的增长而增加
– 对于 C2，如果训练分类 f(xi)与假设的预计相同，那么就不需要传输有关这些样例的任何信息；如果不同，则要传输更正消息
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
最小描述长度准则（ 5）
MDL准则提供了一种方法在假设的复杂性和假设产生错误的数量之间进行折中，它有可能选择一个较短的产生少量错误的假设，而不是完美地分类训练数据的较长的假设
上面讨论自然给出了一种处理数据过度拟合的方法
Quinlan & Rivest描述了应用 MDL准则选择决策树大小的几个实验，报告指出，基于 MDL的方法产生的决策树的精度相当于第 3章中讨论的标准树修剪方法
第 125页,6.6节最后一段的含义？
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
贝叶斯最优分类器
前面我们讨论的问题是：给定训练数据，
最可能的假设是什么？
另一个相关的更有意义的问题是：给定训练数据，对新实例的最可能的分类是什么？
显然，第二个问题的解决可以将第一个问题的结果（ MAP）应用到新实例上得到，还存在更好的算法
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
贝叶斯最优分类器（ 2）
例子
– 考虑一个包含三个假设 h1,h2,h3的假设空间。
– 假定已知训练数据时三个假设的后验概率分别是 0.4,
0.3,0.3，因此 h1为 MAP假设。
– 若一新实例 x被 h1分类为正，被 h2和 h3分类为反
– 计算所有假设,x为正例的概率为 0.4，为反例的概率为 0.6
– 因此，这时最可能的分类与 MAP假设生成的分类不同
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
贝叶斯最优分类器（ 3）
一般而言，新实例的最可能分类可通过合并所有假设的预测得到，用后验概率来加权。
如果新实例的可能分类可取某集合 V中的任一值 vj，那么概率 P(vj|D)表示新实例分类为 vj的概率
新实例的最优分类为使 P(vj|D)最大的 vj值，贝叶斯最优分类器为：
Hh iijVv ij DhPhvP )|()|(m a xa r g
Hh iijj i DhPhvPDvP )|()|()|(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
贝叶斯最优分类器（ 4）
例子
– 已知：
新实例的可能分类集合为 V={+,-}
P(h1|D)=0.4,P(-|h1)=0,P(+|h1)=1
P(h2|D)=0.3,P(-|h2)=1,P(+|h2)=0
P(h3|D)=0.3,P(-|h3)=1,P(+|h2)=0
– 因此：
4.0)|()|( Hh ii
i
DhPhP
6.0)|()|( Hh ii
i
DhPhP
Hh iijHhv
iij
DhPhvP )|()|(m a xa r g },,{
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
贝叶斯最优分类器（ 5）
贝叶斯最优分类器在给定可用数据、假设空间及这些假设的先验概率下使新实例被正确分类的可能性达到最大
贝叶斯最优分类器的一个属性：它所做的分类可以对应于 H中不存在的假设
使用式子 6.18来分类 X中的每个实例，按此定义的实例标注不一定对应于 H中的任一单个假设 h对实例的标注
将贝叶斯分类器看成是不同于假设空间 H的另一空间
H’，在其上应用贝叶斯公式。 H’有效地包含了一组假设，它能在 H中多个假设的线性组合所作的预言中进行比较
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
Gibbs算法
贝叶斯最优分类器能从给定训练数据中获得最好的性能，
但算法的开销很大
一个替代的、非最优的方法是 Gibbs算法，定义如下：
– 按照 H上的后验概率分布，从 H中随机选择假设 h
– 使用 h来预言下一个实例 x的分类
在一定条件下,Gibbs算法的误分类率的期望值最多为贝叶斯最优分类器的两倍。确切地讲，期望值是在随机抽取的目标概念上作出的，抽取过程按照学习器假定的先验概率
对概念学习问题的一个启示：如果学习器假定 H上有均匀的先验概率，而且如果目标概念实际上也按该分布抽取，那么当前变型空间中随机抽取的假设对下一实例分类的期望误差最多为贝叶斯分类器的两倍（？）
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
朴素贝叶斯分类器
应用的学习任务：每个实例 x可由属性值的合取描述，而目标函数 f(x)从某有限集合 V中取值
贝叶斯方法的新实例分类目标是在给定描述实例的属性值 <a1,...,an>下，得到最可能的目标值
vMAP
使用贝叶斯公式变化上式
),.,.,|(m a xa r g 1 njvM A P aavPv j?
)()|,.,,,(m a xa r g
),.,,,(
)()|,.,,,(m a xa r g
1
1
1
jjnVv
n
jjn
VvM A P
vPvaaP
aaP
vPvaaPv
j
j
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
朴素贝叶斯分类器（ 2）
基于训练数据估计式子 6.19中的两个数据项的值
– 估计 P(vj)很容易：计算每个目标值 vj出现在训练数据中的频率
– 估计 P(a1,...an|vj)遇到数据稀疏问题，除非有一个非常大的训练数据集，否则无法获得可靠的估计
朴素贝叶斯分类器引入一个简单的假定避免数据稀疏问题：在给定目标值时，属性值之间相互条件独立，即 i jijn vaPvaaP )|()|,...,( 1
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
朴素贝叶斯分类器（ 3）
朴素贝叶斯分类器的定义：
从训练数据中估计不同 P(ai|vj)项的数量比要估计 P(a1,...,an|vj)项所需的量小得多
只要条件独立性得到满足，朴素贝叶斯分类
vNB等于 MAP分类，否则是近似
朴素贝叶斯分类器与其他已介绍的学习方法的一个区别：没有明确地搜索可能假设空间的过程（假设的形成不需要搜索，只是简单地计算训练样例中不同数据组合的出现频率）
i jijVvNB vaPvPv j )|()(m a xa r g
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
朴素贝叶斯分类器（ 4）
举例
– 表 3-2提供了目标概念 PlayTennis的 14个训练样例，给新实例
<sunny,cool,high,strong>分类
–
– 根据表 3-2，可以计算出上式需要的概率值
P(yes)=9/14=0.64
P(no)=5/14=0.36
P(strong|yes)=3/9=0.33
P(strong|no)=3/5=0.60
,..
– 求 vNB
P(yes)P(sunny|yes)P(cool|yes)P(high|yes)P(strong|yes)=0.0053
P(no)P(sunny|no)P(cool|no)P(high|no)P(strong|no)=0.0206
vNB=no
)|()|()|()|()(m a xa r g)|()(m a xa r g },{},{ jjjjjnoy e svi jijnoy e svNB vs t r ongPvhi ghPvc oolPvs unn yPvPvaPvPv jj
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
朴素贝叶斯分类器（ 5）
估计概率
– 我们通过在全部事件基础上观察某事件出现的比例来估计概率
– 当样本很小时，采用平滑技术,m-估计
– p是将要确定的概率的先验估计，而 m是一称为等效样本大小的常量
– 在缺少其他信息时，选择 p的一种典型的方法是均匀概率，比如某属性有 k个可能值，那么 p=1/k
– m被称为等效样本大小的原因是：式子 6.22可被解释为将 n个实际的观察扩大，加上 m个按 p分布的虚拟样本
mn mpnc
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 50
举例：学习分类文本
利用贝叶斯方法学习目标概念，然后用于文本自动过滤，比如
– 我感兴趣的电子新闻稿
– 讨论机器学习的万维网页
本节描述一个基于朴素贝叶斯分类器的文本分类的通用算法，它是目前所知的文本分类的最有效方法之一
问题框架：实例空间 X包含了所有的文本文档，
给定某未知目标函数 f(x)的一组训练样例,f(x)
的值来自某有限集合 V（作为示例，此处令
V={like,dislike}）
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 51
举例：学习分类文本（ 2）
应用朴素贝叶斯分类器的两个主要设计问题：
– 怎样将任意文档表示为属性值的形式
– 如何估计朴素贝叶斯分类器所需的概率
表示文档的方法
– 给定一个文本文档，对每个单词的位置定义一个属性，该属性的值为在此位置上找到的英文单词
假定我们共有 1000个训练文档，其中 700个分类为
dislike,300个分类为 like，现在要对下面的新文档进行分类：
– This is an example document for the naive Bayes classifier,This
document contains only one paragraph,or two sentences.
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 52
举例：学习分类文本（ 3）
计算式
注意此处贝叶斯分类器隐含的独立性假设并不成立。通常，某个位置上出现某个单词的概率与前后位置上出现的单词是相关的
虽然此处独立性假设不精确，但别无选择，否则要计算的概率项极为庞大。
另外实践中，朴素贝叶斯学习器在许多文本分类问题中性能非常好
)|""(),,.|""()(m a xa r g
)|()(m a xa r g
191},{
19
1},{
jjjd i s l i k el i k ev
i
jijd i s l i k el i k evNB
vs e n t e n c e saPvt h isaPvP
vaPvPv
j
j
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 53
举例：学习分类文本（ 4）
需要估计概率项 P(vi)和 P(ai=wk|vi)。前一项可基于每一类在训练数据中的比例很容易得到，后一项含三个参数，出现数据稀疏问题
再引入一个假定以减少需要估计的概率项的数量：假定单词 wk出现的概率独立于单词所在的位置，即
P(ai=wk|vi)=P(wk|vj)
作此假定的一个主要优点在于：使可用于估计每个所需概率的样例数增加了，因此增加了估计的可靠程度
采纳 m-估计方法，即有统一的先验概率并且 m等于词汇表的大小，因此
|| 1)|( V o ca b u la ryn nvwP kjk
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 54
表 6-2 用于学习和分类文本的朴素贝叶斯算法
Learn_Naive_Bayes_Text( Examples,V )
Examples为一组文本文档以及它们的目标值。 V为所有可能目标值的集合。此函数作用是学习概率项 P(wk|vj)和 P(vj)。
– 收集 Examples中所有的单词、标点符号以及其他记号
Vocabulary?在 Examples中任意文本文档中出现的所有单词及记号的集合
– 计算所需要的概率项 P(vj)和 P(wk|vj)
对 V中每个目标值 vj
– docsj?Examples中目标值为 vj的文档子集
– P(vj)?|docsj| / |Examples|
– Textj?将 docsj中所有成员连接起来建立的单个文档
– n?在 Textj中不同单词位置的总数
– 对 Vocabulary中每个单词 wk
nk?单词 wk出现在 Textj中的次数
P(wk|vj)?(nk+1) / (n+|Vocabulary|)
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 55
表 6-2 用于学习和分类文本的朴素贝叶斯算法（ 2）
Classify_Naive_Bayes_Text( Doc )
对文档 Doc返回其估计的目标值,ai代表在 Doc中的第 i个位置上出现的单词
–positions?在 Doc中的所有单词位置，
它包含能在 Vocabulary中找到的记号
–返回 vNB, p o s itio n si jijVvNB vaPvPv
j
)|()(m a xa r g
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 56
实验结果
Joachims将此算法用于新闻组文章的分类
– 每一篇文章的分类是该文章所属的新闻组名称
– 20个新闻组，每个新闻组有 1000篇文章，共 2万个文档
– 2/3作为训练样例,1/3进行性能测量
– 词汇表不包含最常用词（比如 the,of）和罕见词（数据集中出现次数少于 3）
Lang用此算法学习目标概念“我感兴趣的新闻组文章”
– NewsWeeder系统，让用户阅读新闻组文章并为其评分，然后使用这些评分的文章作为训练样例，来预测后续文章哪些是用户感兴趣的
– 每天向用户展示前 10%的自动评分文章，它建立的文章序列中包含的用户感兴趣的文章比通常高 3~4倍
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 57
贝叶斯信念网
朴素贝叶斯分类器假定各个属性取值在给定目标值 v下是条件独立的，从而化简了最优贝叶斯分类的计算复杂度。但在多数情况下，这一条件独立假定过于严厉了。
贝叶斯信念网描述的是一组变量所遵从的概率分布，
它通过一组条件概率来指定一组条件独立性假设
贝叶斯信念网中可表述变量的一个子集上的条件独立性假定，因此，贝叶斯信念网提供了一种中间的方法，
它比朴素贝叶斯分类器的限制更少，又比在所有变量中计算条件依赖更可行
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 58
贝叶斯信念网（ 2）
贝叶斯信念网描述了一组变量上的概率分布
考虑一任意的随机变量集合 Y1...Yn，其中每个
Yi可取的值集合为 V(Yi)
变量集合 Y的联合空间为叉乘 V(Y1)?..,?V(Yn)
在此联合空间上的概率分布称为联合概率分布，
联合概率分布指定了元组的每个可能的变量约束的概率
贝叶斯信念网则对一组变量描述了联合概率分布
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 59
条件独立性
精确定义条件独立性
– 令 X,Y和 Z为 3个离散值随机变量，当给定 Z值时 X服从的概率分布独立于 Y的值，称 X在给定 Z时条件独立于 Y，即
– 上式通常简写成 P(X|Y,Z)=P(X|Z)
扩展到变量集合
– 下面等式成立时，称变量集合 X1...Xl在给定变量集合 Z1...Zn时条件独立于变量集合 Y1...Ym
条件独立性与朴素贝叶斯分类器的之间的关系
)|(),|(,,kikjikji zZxXPzZyYxXPzyx
).,,|.,,().,,,.,,|.,,( 11111 nlnml ZZXXPZZYYXXP?
)|()|( )|(),|()|,( 21 22121 VAPVAP VAPVAAPVAAP
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 60
贝叶斯信念网的表示
贝叶斯信念网（简称贝叶斯网）表示一组变量的联合概率分布
一般地说，贝叶斯网表示联合概率分布的方法是指定一组条件独立性假定（有向无环图）以及一组局部条件概率集合
图 6-3，联合空间中每个变量在贝叶斯网中表示为一个节点，每个变量需要两种类型的信息
– 网络弧表示断言“此变量在给定其直接前驱时条件独立于其非后继”
– 每个变量有一个条件概率表，描述了该变量在给定其立即前驱时的概率分布
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 61
贝叶斯信念网的表示（ 2）
对网络变量的元组 <Y1...Yn>赋以所希望的值 (y1...yn)的联合概率计算公式如下：
所有变量的局部条件概率表以及由网络所描述的一组条件独立假定，描述了该网络的整个联合概率分布
ni iin YP a re n tsyPyyP 11 ))(|(),.,,,(
4.0),|( Tr u eupB u s T o u r G r oTr u eS t o r mTr u eC a m p f ir eP
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 62
贝叶斯信念网的推理
可以用贝叶斯网在给定其他变量的观察值时推理出某些目标变量的值
由于所处理的是随机变量，所以一般不会赋予目标变量一个确切的值
真正需要推理的是目标变量的概率分布，它指定了在给予其他变量的观察值条件下，目标变量取每一个可能值的概率
在网络中所有其他变量都确切知道的情况下，这一推理步骤很简单
一般来说，贝叶斯网络可用于在知道某些变量的值或分布时计算网络中另一部分变量的概率分布
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 63
贝叶斯信念网的推理（ 2）
对任意贝叶斯网络的概率的确切推理已经知道是一个 NP难题
Monte Carlo方法提供了一种近似的结果，
通过对未观察到的变量进行随机采样
理论上，即使是贝叶斯网络中的近似推理也可能是 NP难题
实践中许多情况下近似的方法被证明是有效的
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 64
学习贝叶斯信念网
从训练数据中学到贝叶斯信念网，有多种讨论的框架：
– 网络结构可以预先给出，或由训练数据中得到
– 所有的网络变量可以直接从每个训练样例中观察到，或某些变量不能观察到
如果网络结构已知且变量可以从训练样例中完全获得，
那么得到条件概率表就比较简单
如果网络结构已知，但只有一部分变量值能在数据中观察到，学习问题就困难多了。这类似于在人工神经网络中学习隐藏单元的权值
Russtll（ 1995）提出了一个简单的梯度上升过程以学习条件概率表中的项，相当于对表项搜索极大似然假设
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 65
贝叶斯网的梯度上升训练
令 wijk代表条件概率表的一个表项，即在给定父节点 Ui取值 uik时，网络变量 Yi值为
yij的概率
例如图 6-3,wijk为最右上方的表项，那么
Yi为变量 Campfire,Ui是其父节点的元组
<Storm,BusTourGroup>,yij=True，且
uik=<False,False>
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 66
贝叶斯网的梯度上升训练（ 2）
lnP(D|h)的梯度由对每个 wijk求导数得到
例如，为计算图 6-3中表左上方的表项的 lnP(D|h)的导数，
需要对 D中每个训练样例 d计算 P(Campfire=True,
Storm=False,BusTourGroup=False|d)
当训练样例中无法观察到这些变量时，这些概率可用标准的贝叶斯网从 d中观察到的变量中推理得到
这些量能够很容易地从贝叶斯网推理过程中得到，几乎不需要附加的开销
Dd ijk ikiijiijk w duUyYPw hDP )|,()|(ln
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 67
贝叶斯网的梯度上升训练（ 3）
式子 6.25的推导
– 用 Ph(D)来表示 P(D|h)
– 假定在数据集 D中的各样例 d都是独立抽取的
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 68
Dd i j k
ikijh
Dd ikijh
ikijh
Dd ikijh
ikhikijh
ikijh
ikhhikijh
Dd h
Dd
ikhikijh
h
Dd
ikhi j kikijh
i j kh
Dd
ikhikijhikijh
i j kh
ikh
kj
ikijhikijh
Dd i j kh
kj
ikijhikijh
Dd i j kh
i j k
h
Dd h
Dd
i j k
h
Dd
h
i j ki j k
h
w
duyP
uyP
duyP
uyP
uPduyP
uyP
uPdPduyP
dP
uPuydP
dP
uPwuydP
wdP
uPuyPuydP
wdP
uPuyPuydP
wdP
uyPuydP
wdP
w
dP
dP
w
dP
dP
ww
DP
)|,(
)|(
)|,(
),(
)()|,(
),(
)()()|,(
)(
1
)(),|(
)(
1
)(),|(
)(
1
)()|(),|(
)(
1
)()|(),|(
)(
1
),(),|(
)(
1
)(
)(
1
)(ln
)(ln
)(ln
'
','
''''
','
''''
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 69
贝叶斯网的梯度上升训练（ 4）
更新权值
归一化处理，保持在区间 [0,1]之间，且
jwijk对所有 i,k保持为 1
这个算法只保证找到局部最优解，替代梯度上升的一个算法是 EM算法
Dd ijk ikijhijkijk w duyPww )|,(?
ki ijkijkijk www,
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 70
学习贝叶斯网的结构
如果贝叶斯网的结构未知，那么需要学习贝叶斯网的结构
Cooper & Herskovits提出了一个贝叶斯评分尺度，以便从不同网络中进行选择
Cooper & Herskovits提出了算法 K2，启发式算法，用于在数据完全可观察时学习网络结构
基于约束的学习贝叶斯网络结构：从数据中推导出独立和相关的关系，然后用这些关系来构造贝叶斯网
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 71
EM算法
在许多实际的学习问题框架中，相关实例特征中只有一部分可观察到
已有许多方法被提出来处理存在未观察到变量的问题
– 比如，如果某些变量有时能观察到，有时不能，那么可以用观察到该变量的实例去预测未观察到的实例中的变量的值
EM算法是存在隐含变量时广泛使用的一种学习方法，
可用于变量的值从来没有被直接观察到的情形，只要这些变量所遵循的概率分布的一般形式已知
– 用于贝叶斯网的训练
– 用于马尔可夫模型的训练
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 72
估计 k个高斯分布的均值
考虑 D是一个实例集合，它由 k个不同正态分布的混合所得分布生成
每个实例使用一个两步骤的过程形成：
– 首先，随机选择 k个正态分布中的一个
– 其次，随机变量 xi按照此选择的分布生成
考虑一个简单情形：
– 单个正态分布的选择基于均匀的概率进行，且 k个正态分布有相同的方差
– 学习任务：输出一个假设 h=<?1...?k>，描述 k个分布中每个分布的均值，找到极大似然假设，即使得
p(D|h)最大化的假设
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 73
估计 k个高斯分布的均值（ 2）
当给定从一个正态分布中抽取的数据实例 x1,...,xm时，
很容易计算该分布的均值的极大似然假设，它是 6.4节中式子 6.6的一个特例，表示如下
然而，现在的问题涉及 k个不同正态分布，而且不知道哪个实例是哪个分布产生的。这是一个涉及隐藏变量的典型例子
对于图 6-4的例子，每个实例的完整描述是三元组
<xi,zi1,zi2>，其中 xi是第 i个实例的观测值,zi1和 zi2表示哪个正态分布被用来产生 xi，是隐藏变量
mi imi iML xmx 11 2 1)(m ina r g
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 74
估计 k个高斯分布的均值（ 3）
如果 zi1和 zi2的值可知，就可用式子 6.27来解决，
否则使用 EM算法
EM算法根据当前假设 <?1...?k>，不断地再估计隐藏变量 zij的期望值，然后用这些隐藏变量的期望值重新计算极大似然假设
以图 6-4为例，先将假设初始化为 h=<?1,?2>
– 计算每个隐藏变量 zij的期望值 E[zij]，假定当前假设
h=<?1,?2>成立
– 计算一个新的极大似然假设 h’=<?’1,?’k>，假定每个隐藏变量 zij所取值是第一步得到的期望值 E[zij]。
将假设替换为 h’=<?’1,?’2>，然后循环
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 75
两个步骤的计算式
E[zij]正是实例 xi由第 j个正态分布生成的概率
第二步，使用第一步得到的 E[zij]来导出一新的极大似然假设
2
1
)(
2
1
)(
2
1
2
1
2
2
2
2
)|(
)|(
][
n
x
x
n
ni
ji
ij
ni
ji
e
e
xxp
xxp
zE
m
i
ij
m
i
iij
j
zE
xzE
1
1
][
][
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 76
两个步骤的计算式（ 2）
第二步中的表达式类似于式 6.28，只是变成了加权样本均值
EM算法的要点：当前的假设用于估计未知变量，而这些变量的期望值再被用于改进假设
可以证明：算法的每一次循环中,EM算法能使似然 P(D|h)增加，除非 P(D|h)达到局部最大，
因此算法收敛到一个局部最大似然假设
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 77
EM算法的一般表述
EM算法可用于许多问题框架：其中需要估计一组描述基准概率分布的参数，只给定了由此分布产生的全部数据中能观察到的一部分。
– 上面的二均值问题中，感兴趣的参数是?=<?1,?2>，
全部数据是三元组 <xi,zi1,zi2>，而只能观察到 xi
一般地，令待估计参数是?，全部数据 Y=X?Z，
其中 X是可观察数据,Z是未观察数据。
Z可看作一个随机变量，它的概率分布依赖于参数?和已知数据 X
Y也是一个随机变量，因为它由随机变量 Z定义
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 78
EM算法的一般表述（ 2）
EM算法通过搜寻使 E[lnP(Y|h’)]最大的 h’来寻找极大似然假设 h’，其合理性是：
– P(Y|h’)是给定假设 h’下全部数据 Y的似然度，因此找到使得这个值最大的 h’是合理的
– 对数 lnP(Y|h’)最大化也使 P(Y|h’)最大化
– 由于 Y是一个随机变量，因此 P(Y|h’)无法计算，转而计算它的期望值 E[lnP(Y|h’)]
Y的概率分布由待估计的参数决定,EM算法使用当前假设 h代替实际参数，来估计 Y的概率分布
定义函数 Q(h’|h)=E[lnP(Y|h’)|h,X]
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 79
EM算法的一般表述（ 3）
EM算法的一般形式，重复下面的步骤，直至收敛
– 估计（ E）步骤：使用当前假设 h和观察到的数据 X
来估计 Y上的概率分布以计算 Q(h’|h)
Q(h’|h)?E[lnP(Y|h’)|h,X]
– 最大化（ M）步骤：将假设 h替换为使 Q函数最大化的假设 h’
h?argmaxh’Q(h’|h)
当函数 Q连续时,EM算法收敛到似然函数
P(Y|h’)的一个不动点，它保证收敛到一个局部最大值
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 80
K均值算法的推导
问题框架
– 要估计 k个正态分布的均值?=<?1...?k>
– 观察到的数据是 X={<xi>}
– 隐藏变量 Z={<zi1,...,zik>}表示 k个正态分布中哪一个生成 xi
用于 K均值问题的表达式 Q(h’|h)的推导
– 单个实例的概率
kj jiij xz
ikiii ehzzxphyp 1
2'2 )(2 1
21 2
1)'|,.,.,,()'|(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 81
K均值算法的推导（ 2）
– 所有实例的概率的对数
– 计算期望值
m
i
k
j
jiij
m
i
i
m
i
i
xz
hyp
hyphYP
1 1
2'
22
1
1
)(
2
1
2
1
ln
)'|(ln
)'|(ln)'|(ln
m
i
k
j
jiij
m
i
k
j
jiij
xzE
xzEhYPE
1 1
2'
22
1 1
2'
22
)]([2 1
2
1ln
)(2 1
2
1ln)]'|([ ln
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 82
K均值算法的推导（ 3）
– 求使 Q函数最大的假设
– 解上式得到
– 另外
m
i
k
j
jiij
h
m
i
k
j
jiij
hh
xzE
xzEhhQ
1 1
2'
'
1 1
2'
22''
m a xa r g
2
1
2
1lnm a xa r g)|'(m a xa r g
m
i
ij
m
i
iij
j
zE
xzE
1
1
][
k
n
x
x
ji
ji
e
ezijE
1
)(2 1
2)(2 1
2
2
2
][
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 83
小结
概率学习方法利用关于不同假设的先验概率，以及在给定假设时观察到不同数据的概率的知识
贝叶斯方法提供了概率学习方法的基础，基于这些先验和数据观察假定，赋予每个假设一个后验概率
贝叶斯方法确定的极大后验概率假设是最可能成为最优假设的假设
贝叶斯最优分类器将所有假设的预测结合起来，并用后验概率加权，以计算对新实例的最可能分类
朴素贝叶斯分类器增加了简化假定：属性值在给定实例的分类时条件独立
贝叶斯信念网能够表示属性的子集上的一组条件独立性假定
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 84
小结（ 2）
贝叶斯推理框架可对其他不直接应用贝叶斯公式的学习方法的分析提供理论基础
最小描述长度准则建议选取这样的假设，它使假设的描述长度和给定假设下数据的描述长度的和最小化。贝叶斯公式和信息论中的基本结论提供了此准则的根据
EM算法提供了一个通用的算法，在存在隐藏变量时进行学习。算法开始于一个任意的初始假设，然后迭代地计算隐藏变量的期望值，再重新计算极大似然假设，这个过程收敛到一个局部极大似然假设和隐藏变量的估计值
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 85
补充读物
Casella & Berger 1990在概率和统计方面的介绍性文章
Maisel 1971,Speigel 1991的快速参考书籍
Duda & Hart 1973对贝叶斯分类器和最小平方误差分类器的介绍
Domigos & Pazzani 1996分析了朴素贝叶斯分类器输出最优分类的条件
Cestnik 1990讨论了 m-估计
Michie et al,1994将不同贝叶斯方法与决策树等其他算法进行比较
Chauvin & Rumelhart1995提供了基于反向传播算法的神经网络的贝叶斯分析
Rissanen1 1983,1989讨论了最小描述长度准则
Quinlan & Rivest 1989描述了利用最小描述长度准则避免决策树过度拟合的方法
机器学习第 6章 贝叶斯学习
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
贝叶斯推理提供了一种概率手段，基于如下的假定：待考察的量遵循某概率分布，且可根据这些概率及已观察到的数据进行推理，以作出最优的决策。
贝叶斯推理为衡量多个假设的置信度提供了定量的方法
贝叶斯推理为直接操作概率的学习算法提供了基础，也为其他算法的分析提供了理论框架
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
贝叶斯学习算法与机器学习相关的两个原因：
– 贝叶斯学习算法能够计算显示的假设概率，比如朴素贝叶斯分类
– 贝叶斯方法为理解多数学习算法提供了一种有效的手段，而这些算法不一定直接操纵概率数据，比如
Find-S
候选消除算法
神经网络学习：选择使误差平方和最小化的神经网络
推导出另一种误差函数：交叉熵
分析了决策树的归纳偏置
考察了最小描述长度原则
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
贝叶斯学习方法的特性
观察到的每个训练样例可以增量地降低或升高某假设的估计概率。而其他算法会在某个假设与任一样例不一致时完全去掉该假设
先验知识可以与观察数据一起决定假设的最终概率，
先验知识的形式是,1）每个候选假设的先验概率； 2）
每个可能假设在可观察数据上的概率分布
贝叶斯方法可允许假设做出不确定性的预测
新的实例分类可由多个假设一起做出预测，用它们的概率来加权
即使在贝叶斯方法计算复杂度较高时，它们仍可作为一个最优的决策标准衡量其他方法
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
贝叶斯方法的难度
难度之一：需要概率的初始知识，当概率预先未知时，可以基于背景知识、预先准备好的数据以及基准分布的假定来估计这些概率
难度之二：一般情况下，确定贝叶斯最优假设的计算代价比较大（在某些特定情形下，这种计算代价可以大大降低）。
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
内容安排
介绍贝叶斯理论
定义极大似然假设和极大后验概率假设
将此概率框架应用于分析前面章节的相关问题和学习算法
介绍几种直接操作概率的学习算法
– 贝叶斯最优分类器
– Gibbs算法
– 朴素贝叶斯分类器
讨论贝叶斯信念网，这是存在未知变量时被广泛使用的学习算法
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
贝叶斯法则
机器学习的任务：在给定训练数据 D时，确定假设空间 H中的最佳假设。
最佳假设：一种方法是把它定义为在给定数据
D以及 H中不同假设的先验概率的有关知识下的最可能假设
贝叶斯理论提供了一种计算假设概率的方法，
基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
先验概率和后验概率
用 P(h)表示在没有训练数据前假设 h拥有的初始概率。 P(h)被称为 h的先验概率。
先验概率反映了关于 h是一正确假设的机会的背景知识
如果没有这一先验知识，可以简单地将每一候选假设赋予相同的先验概率
类似地,P(D)表示训练数据 D的先验概率，
P(D|h)表示假设 h成立时 D的概率
机器学习中，我们关心的是 P(h|D)，即给定 D时
h的成立的概率，称为 h的后验概率
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
贝叶斯公式
贝叶斯公式提供了从先验概率 P(h),P(D)
和 P(D|h)计算后验概率 P(h|D)的方法
P(h|D)随着 P(h)和 P(D|h)的增长而增长，
随着 P(D)的增长而减少，即如果 D独立于
h时被观察到的可能性越大，那么 D对 h的支持度越小
)( )()|()|( DP hPhDPDhP?
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
极大后验假设
学习器在候选假设集合 H中寻找给定数据
D时可能性最大的假设 h,h被称为极大后验假设（ MAP）
确定 MAP的方法是用贝叶斯公式计算每个候选假设的后验概率，计算式如下最后一步，去掉了 P(D)，因为它是不依赖于 h的常量
)()|(m a xa r g)( )()|(m a xa r g)|(m a xa r g hPhDPDP hPhDPDhPh HhHhHhM A P
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
极大似然假设
在某些情况下，可假定 H中每个假设有相同的先验概率，这样式子 6.2可以进一步简化，只需考虑 P(D|h)来寻找极大可能假设。
P(D|h)常被称为给定 h时数据 D的似然度，而使
P(D|h)最大的假设被称为极大似然假设
假设空间 H可扩展为任意的互斥命题集合，只要这些命题的概率之和为 1
)|(m a xa rg hDPh HhML
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
举例：一个医疗诊断问题
有两个可选的假设：病人有癌症、病人无癌症
可用数据来自化验结果：正 +和负 -
有先验知识：在所有人口中，患病率是 0.008
对确实有病的患者的化验准确率为 98%，对确实无病的患者的化验准确率为 97%
总结如下
P(cancer)=0.008,P(?cancer)=0.992
P(+|cancer)=0.98,P(-|cancer)=0.02
P(+|?cancer)=0.03,P(-|?cancer)=0.97
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
举例：一个医疗诊断问题（ 2）
问题：假定有一个新病人，化验结果为正，是否应将病人断定为有癌症？求后验概率 P(cancer|+)和 P(?cancer|+)
利用式子 6.2找到极大后验假设
– P(+|cancer)P(cancer)=0.0078
– P(+|?cancer)P(?cancer)=0.0298
– hMAP=?cancer
确切的后验概率可将上面的结果归一化以使它们的和为 1
– P(canner|+)=0.0078/(0.0078+0.0298)=0.21
– P(?cancer|-)=0.79
贝叶斯推理的结果很大程度上依赖于先验概率，另外不是完全接受或拒绝假设，只是在观察到较多的数据后增大或减小了假设的可能性
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
基本概率公式表
乘法规则：
P(A?B)=P(A|B)P(B)=P(B|A)P(A)
加法规则,P(A?B)=P(A)+P(B)-P(A?B)
贝叶斯法则,P(h|D)=P(D|h)P(h)/P(D)
全概率法则：如果事件 A1...An互斥，且满足,则1)(1ni iAP ni ii APABPBP 1 )()|()(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
贝叶斯法则和概念学习
贝叶斯法则为计算给定训练数据下任一假设的后验概率提供了原则性方法，因此可以直接将其作为一个基本的学习方法：计算每个假设的概率，再输出其中概率最大的。这个方法称为
Brute-Force贝叶斯概念学习算法。
将上面方法与第 2章介绍的概念学习算法比较，
可以看到：在特定条件下，它们学习得到相同的假设，不同的是第 2章的方法不明确计算概率，而且效率更高。
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
Brute-Force贝叶斯概念学习
概念学习问题：有限假设空间 H定义在实例空间 X上，任务是学习某个目标概念 c。
Brute-Force MAP学习算法
– 对于 H中每个假设 h，计算后验概率
– 输出有最高后验概率的假设
上面算法需要较大计算量，因为它要计算每个假设的后验概率，对于大的假设空间显得不切实际，但是它提供了一个标准以判断其他概念学习算法的性能
)( )()|()|( DP hPhDPDhP?
)|(m a xa rg DhPh HhM A P
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
特定情况下的 MAP假设
假定
– 训练数据 D是无噪声的，即 di=c(xi)
– 目标概念 c包含在假设空间 H中
– 每个假设的概率相同
求得
– 由于所有假设的概率之和是 1，因此
– 由于训练数据无噪声，那么给定假设 h时，与 h一致的 D的概率为 1，不一致的概率为 0，因此
|| 1)( HhP?
o th erw isexhddhDP iii )(,01)|(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
特定情况下的 MAP假设（ 2）
考虑 Brute-Force MAP算法的第一步
– h与 D不一致，
– h与 D一致，,
VSH,D是关于 D的变型空间（见第 2章，即与
D一致的假设集）
0)( )(0)|( DP hPDhP
||
1
||
||
||
1
)(
||
11
)|(
,,DHDH VS
H
VS
H
DP
HDhP
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
特定情况下的 MAP假设（ 3）
P(D)的推导
P(D)
假设的概率演化情况如图 6-1所示，初始时所有假设具有相同的概率，当训练数据逐步出现后，
不一致假设的概率变为 0，而整个概率的和为 1，
它们均匀分布到剩余的一致假设中
每个一致的假设都是 MAP假设
||
||
||
1
1
||
1
0
||
1
1
)()|(
,
,
,,
H
VS
H
HH
hPhDP
DH
VSh
VShVSh
Hh
ii
DHi
DHiDHi
i
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
MAP假设和一致学习器
一致学习器：如果某个学习器输出的假设在训练样例上为 0错误率，则称为一致学习器
如果 H上有均匀的先验概率，且训练数据是确定性和无噪声的，任意一致学习器将输出一个 MAP假设
Find-S算法按照特殊到一般的顺序搜索架设空间 H，并输出一个极大特殊的一致假设，因此可知在上面定义的 P(h)和 P(D|h)概率分布下，它输出 MAP假设
更一般地，对于先验概率偏袒于更特殊假设的任何概率分布,Find-S输出的假设都是 MAP假设
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
MAP假设和一致学习器（ 2）
贝叶斯框架提出了一种刻画学习算法行为的方法，即便该学习算法不进行概率操作，通过确定算法输出最优假设时使用的概率分布 P(h)和
P(D|h)，可以刻画出算法具有最优行为时的隐含假定
使用贝叶斯方法刻画学习算法，与揭示学习器中的归纳偏置在思想上是类似的
在第 2章，将学习算法的归纳偏置定义为断言集合 B，通过它可充分地演绎推断出学习器所执行的归纳推理结果，即学习器的输出是由其输入和隐含的归纳偏置所演绎得出的
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
MAP假设和一致学习器（ 3）
贝叶斯解释对于描述学习算法中的隐含假定提供了另一种方法，用基于贝叶斯理论的一个等效的概率推理系统来建模
贝叶斯解释隐含的假定形式为,H上的先验概率由 P(h)分布给出，数据拒绝或接受假设的强度由 P(D|h)给出
在已知这些假定的概率分布后，一个基于贝叶斯理论的概率推理系统将产生等效于 Find-S、
候选消除等算法的输入 -输出行为
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
极大似然和最小误差平方假设
前面分析表明：某些学习算法即使没有显示地使用贝叶斯规则，或以某种形式计算概率，但它们输出的结果符合贝叶斯原理，是一个 MAP假设
通过简单的贝叶斯分析，可以表明在特定前提下，任一学习算法如果使输出的假设预测和训练数据之间的误差平方和最小化，它将输出一极大似然假设
上面结论的意义是，对于许多神经网络和曲线拟合的方法，如果它们试图在训练数据上使误差平方和最小化，此结论提供了基于贝叶斯的理论依据
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
极大似然和最小误差平方假设
（ 2）
问题框架：
– 学习器 L工作在实例空间 X和假设空间 H上,H中的假设为 X上定义的某种实数值函数。
– L面临的问题是学习一个从 H中抽取出的未知目标函数 f，给定 m个训练样例的集合，每个样例的目标值被某随机噪声干扰，此随机噪声服从正态分布
– 更精确地讲，每个训练样例是序偶 <xi,di>，
di=f(xi)+ei,ei是代表噪声的随机变量，假定 ei的值是独立抽取的，并且它们的分布服从 0均值的正态分布
– 学习器的任务是在所有假设有相等的先验概率前提下，输出极大似然假设（即 MAP假设）
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
极大似然和最小误差平方假设
（ 3）
用一个简单情况，即线性函数来说明问题。如图 6-2所示，实线表示线性目标函数 f，实点表示有噪声的训练样例集，虚线对应有最小平方训练误差的假设 hML，即极大似然假设。
对于 e这样的连续变量上的概率，使用概率密度表示概率分布，它在所有值上的积分为 1，
用小写的 p表示。有限概率 P有时又称为概率质量
概率密度函数,)(1lim)( 0000 xxxPxp
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
极大似然和最小误差平方假设
（ 4）
假定有一固定的训练实例集合，因此只考虑相应的目标值序列
D=<d1...dm>，这里 di=f(xi)+ei。
假定训练样例是相互独立的，给定 h时，可将 P(D|h)写成各 p(di|h)
的积
如果误差 ei服从 0均值和未知方差?2的正态分布，那么每个 di服从均值为 f(xi)，方差不变的正态分布。因此，
p(di|h)可写为方差?2、均值 f(xi)的正态分布
使用表 5-4中的正态分布公式并将相应的参数代入，由于概率 di的表达式是在 h为目标函数 f的正确描述条件下的，所以替换?=f(xi)=h(xi)
mi iHhML hdph 1 )|(m a xa rg
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
极大似然和最小误差平方假设
（ 5）
hML
上式说明了极大似然假设等价于使训练值和假设预测值之间的误差的平方和最小的那个假设
这个结论的前提是：训练值等于真实目标值加上随机噪声，其中随机噪声从一个均值为 0的正态分布中独立抽取
m
i
ii
Hh
m
i
ii
Hh
m
i
ii
Hh
xhdm
iHh
m
i
d
Hh
xhd
xhd
xhd
e
e
ii
i
1
2
1
2
2
1
2
22
))((
2
1
1
2
1
)(
2
1
2
))((mina r g
))((
2
1
m a xa r g
))((
2
1
2
1
lnm a xa r g
2
1
m a xa r g
2
1
m a xa r g
2
2
2
2
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
采用正态分布的合理性
数学计算的简洁性
对许多物理系统的噪声都有良好的近似
第 5章中心极限定律显示，足够多的独立同分布随机变量的和服从正态分布
由许多独立同分布的因素的和所生成的噪声将成为正态分布（当然，现实中不同的分量对噪声的贡献也许不是同分布的）
使误差平方最小化的方法经常被用于神经网络、曲线拟合及其他许多实函数逼近的算法中
上面的分析只考虑了训练样例的目标值中的噪声，而没有考虑实例属性值的噪声
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
用于预测概率的极大似然假设
问题框架：
– 学习一个不确定性函数 f,X?{0,1}，它有两个离散的值输出
– 这种不可预测性来源于未能观察到的因素，
导致目标函数的输出是输入的概率函数
学习得到的神经网络（或其他实函数学习器）的输出是 f(x)=1的概率，表示为
f’,X?[0,1]，即 f’=P(f(x)=1)
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
用于预测概率的极大似然假设
（ 2）
Brute-Force法
– 首先收集对 x的每个可能值观察到的 1和 0的频率，然后训练神经网络，对每个 x输出目标频率
可以直接从 f的训练样例中训练神经网络，
然后推导出 f’的极大似然假设
– D={<x1,d1>...<xm,dm>}
– mi iiimi ii xPxhdPhdxPhDP 11 )(),|()|,()|(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
用于预测概率的极大似然假设
（ 3）
–
–
– hML
– 式子 6.13与熵函数的一般式相似，因此它的负值常称为交叉熵
ii didi
i
i
i
iii xhxhddxhxhxhdP 1))(1()(01)(1 )(),|(
mi ididi xPxhxhhDP ii1 1 )())(1()()|(
m
i
iiii
Hh
m
i
d
i
d
i
Hh
m
i
i
d
i
d
i
Hh
xhdxhd
xhxh
xpxhxh
ii
ii
1
1
1
1
1
))(1ln ()1()(lnm a xa r g
))(1()(m a xa r g
)())(1()(m a xa r g
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
在神经网络中梯度搜索以达到似然最大化
前面讨论了利用式子 6.13求极大似然假设，现用 G(h,D)表示，为神经网络学习推导一个权值训练法则，使用梯度上升法使 G(h,D)最大化
考虑简单的情况，假定神经网络从一个单层的
sigmoid单元建立，则
m
i jk
i
ii
ii
m
i jk
i
i
iiii
m
i jk
i
ijk
w
xh
xhxh
xhd
w
xh
xh
xhdxhd
w
xh
xh
DhG
w
DhG
1
1
1
)(
))(1)((
)(
)(
)(
) ) )(1ln ()1()(ln(
)(
)(
),(),(
ijkiiijkijki xxhxhxxw xh ))(1)(()(')(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
在神经网络中梯度搜索以达到似然最大化（ 2）
因为要使 P(D|h)最大化而不是最小化，因此执行梯度上升搜索，而不是梯度下降搜索。
与反向传播更新法则对比
– 使误差平方最小化的法则寻找到极大似然假设的前提是：训练数据可以由目标函数值加上正态分布噪声来模拟
– 使交叉熵最小化的法则寻找极大似然假设基于的前提是：观察到的布尔值为输入实例的概率函数
mi ijkiijk xxhdw DhG 1 ))((),(
jkjkjk www
m
i ijkiijk xxhdw 1 ))((?
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
最小描述长度准则
奥坎姆剃刀可以概括为：为观察到的数据选择最短的解释
此处给出一个贝叶斯分析，提出最小描述长度准则，根据信息论中的基本概念来解释 hMAP的定义
上式可以解释为在特定的假设编码表示方案上
“优先选择短的假设”
)(lo g)|(lo gm ina r g
)(lo g)|(lo gm a xa r g
)()|(m a xa r g
22
22
hPhDP
hPhDP
hPhDPh
Hh
Hh
Hh
M A P
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
最小描述长度准则（ 2）
信息论中的编码理论
– 设想要为随机传送的消息设计一个编码，其中遇到消息 i的概率是 pi
– 感兴趣的是，使得传输随机信息所需的最小期望传送位数的编码
– 直观上，为使期望的编码长度最小，可能性大的消息应该赋予较短的编码
– Shannon & Weaver证明了最优编码对消息 i的编码长度为 -log2pi
– 使用代码 C来编码消息 i所需的位数被称为消息 i关于
C的描述长度，记为 LC(i)
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
最小描述长度准则（ 3）
使用编码理论的结论来解释等式 6.16
– -log2P(h)是在假设空间 H的最优编码下 h的描述长度。
换言之，这是假设 h使用其最优表示时的大小
–,CH为假设空间 H的最优编码
– -log2P(D|h)是在给定假设 h时，训练数据 D的描述长度，,CD|h是假定发送者和接送者都知道假设 h时描述数据 D的最优编码
– 因此式子 6.16显示,hMAP是使假设描述长度和给定假设下数据描述长度之和最小化的假设
最小描述长度准则：
)(log)( 2 hPhL HC
)|(lo g)|( 2| hDPhDL hDC
)|()(m ina r g 21 hDLhLh CCHhM D L
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
最小描述长度准则（ 4）
如果选择 C1为假设的最优编码 CH,C2为最优编码 CD|h，
那么 hMDL=hMAP
可将 MDL准则想象为选择最短的方法来重新编码训练数据，其中不仅计算假设的大小，并且计算给定假设时编码数据的附加开销
将 MDL准则应用于决策树，如何选择假设和数据的表示 C1和 C2?
– 对于 C1，很自然地选择某种明确的决策树编码方法，其中描述长度随着树中节点和边的增长而增加
– 对于 C2，如果训练分类 f(xi)与假设的预计相同，那么就不需要传输有关这些样例的任何信息；如果不同，则要传输更正消息
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
最小描述长度准则（ 5）
MDL准则提供了一种方法在假设的复杂性和假设产生错误的数量之间进行折中，它有可能选择一个较短的产生少量错误的假设，而不是完美地分类训练数据的较长的假设
上面讨论自然给出了一种处理数据过度拟合的方法
Quinlan & Rivest描述了应用 MDL准则选择决策树大小的几个实验，报告指出，基于 MDL的方法产生的决策树的精度相当于第 3章中讨论的标准树修剪方法
第 125页,6.6节最后一段的含义？
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
贝叶斯最优分类器
前面我们讨论的问题是：给定训练数据，
最可能的假设是什么？
另一个相关的更有意义的问题是：给定训练数据，对新实例的最可能的分类是什么？
显然，第二个问题的解决可以将第一个问题的结果（ MAP）应用到新实例上得到，还存在更好的算法
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
贝叶斯最优分类器（ 2）
例子
– 考虑一个包含三个假设 h1,h2,h3的假设空间。
– 假定已知训练数据时三个假设的后验概率分别是 0.4,
0.3,0.3，因此 h1为 MAP假设。
– 若一新实例 x被 h1分类为正，被 h2和 h3分类为反
– 计算所有假设,x为正例的概率为 0.4，为反例的概率为 0.6
– 因此，这时最可能的分类与 MAP假设生成的分类不同
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
贝叶斯最优分类器（ 3）
一般而言，新实例的最可能分类可通过合并所有假设的预测得到，用后验概率来加权。
如果新实例的可能分类可取某集合 V中的任一值 vj，那么概率 P(vj|D)表示新实例分类为 vj的概率
新实例的最优分类为使 P(vj|D)最大的 vj值，贝叶斯最优分类器为：
Hh iijVv ij DhPhvP )|()|(m a xa r g
Hh iijj i DhPhvPDvP )|()|()|(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
贝叶斯最优分类器（ 4）
例子
– 已知：
新实例的可能分类集合为 V={+,-}
P(h1|D)=0.4,P(-|h1)=0,P(+|h1)=1
P(h2|D)=0.3,P(-|h2)=1,P(+|h2)=0
P(h3|D)=0.3,P(-|h3)=1,P(+|h2)=0
– 因此：
4.0)|()|( Hh ii
i
DhPhP
6.0)|()|( Hh ii
i
DhPhP
Hh iijHhv
iij
DhPhvP )|()|(m a xa r g },,{
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
贝叶斯最优分类器（ 5）
贝叶斯最优分类器在给定可用数据、假设空间及这些假设的先验概率下使新实例被正确分类的可能性达到最大
贝叶斯最优分类器的一个属性：它所做的分类可以对应于 H中不存在的假设
使用式子 6.18来分类 X中的每个实例，按此定义的实例标注不一定对应于 H中的任一单个假设 h对实例的标注
将贝叶斯分类器看成是不同于假设空间 H的另一空间
H’，在其上应用贝叶斯公式。 H’有效地包含了一组假设，它能在 H中多个假设的线性组合所作的预言中进行比较
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
Gibbs算法
贝叶斯最优分类器能从给定训练数据中获得最好的性能，
但算法的开销很大
一个替代的、非最优的方法是 Gibbs算法，定义如下：
– 按照 H上的后验概率分布，从 H中随机选择假设 h
– 使用 h来预言下一个实例 x的分类
在一定条件下,Gibbs算法的误分类率的期望值最多为贝叶斯最优分类器的两倍。确切地讲，期望值是在随机抽取的目标概念上作出的，抽取过程按照学习器假定的先验概率
对概念学习问题的一个启示：如果学习器假定 H上有均匀的先验概率，而且如果目标概念实际上也按该分布抽取，那么当前变型空间中随机抽取的假设对下一实例分类的期望误差最多为贝叶斯分类器的两倍（？）
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
朴素贝叶斯分类器
应用的学习任务：每个实例 x可由属性值的合取描述，而目标函数 f(x)从某有限集合 V中取值
贝叶斯方法的新实例分类目标是在给定描述实例的属性值 <a1,...,an>下，得到最可能的目标值
vMAP
使用贝叶斯公式变化上式
),.,.,|(m a xa r g 1 njvM A P aavPv j?
)()|,.,,,(m a xa r g
),.,,,(
)()|,.,,,(m a xa r g
1
1
1
jjnVv
n
jjn
VvM A P
vPvaaP
aaP
vPvaaPv
j
j
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
朴素贝叶斯分类器（ 2）
基于训练数据估计式子 6.19中的两个数据项的值
– 估计 P(vj)很容易：计算每个目标值 vj出现在训练数据中的频率
– 估计 P(a1,...an|vj)遇到数据稀疏问题，除非有一个非常大的训练数据集，否则无法获得可靠的估计
朴素贝叶斯分类器引入一个简单的假定避免数据稀疏问题：在给定目标值时，属性值之间相互条件独立，即 i jijn vaPvaaP )|()|,...,( 1
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
朴素贝叶斯分类器（ 3）
朴素贝叶斯分类器的定义：
从训练数据中估计不同 P(ai|vj)项的数量比要估计 P(a1,...,an|vj)项所需的量小得多
只要条件独立性得到满足，朴素贝叶斯分类
vNB等于 MAP分类，否则是近似
朴素贝叶斯分类器与其他已介绍的学习方法的一个区别：没有明确地搜索可能假设空间的过程（假设的形成不需要搜索，只是简单地计算训练样例中不同数据组合的出现频率）
i jijVvNB vaPvPv j )|()(m a xa r g
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
朴素贝叶斯分类器（ 4）
举例
– 表 3-2提供了目标概念 PlayTennis的 14个训练样例，给新实例
<sunny,cool,high,strong>分类
–
– 根据表 3-2，可以计算出上式需要的概率值
P(yes)=9/14=0.64
P(no)=5/14=0.36
P(strong|yes)=3/9=0.33
P(strong|no)=3/5=0.60
,..
– 求 vNB
P(yes)P(sunny|yes)P(cool|yes)P(high|yes)P(strong|yes)=0.0053
P(no)P(sunny|no)P(cool|no)P(high|no)P(strong|no)=0.0206
vNB=no
)|()|()|()|()(m a xa r g)|()(m a xa r g },{},{ jjjjjnoy e svi jijnoy e svNB vs t r ongPvhi ghPvc oolPvs unn yPvPvaPvPv jj
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
朴素贝叶斯分类器（ 5）
估计概率
– 我们通过在全部事件基础上观察某事件出现的比例来估计概率
– 当样本很小时，采用平滑技术,m-估计
– p是将要确定的概率的先验估计，而 m是一称为等效样本大小的常量
– 在缺少其他信息时，选择 p的一种典型的方法是均匀概率，比如某属性有 k个可能值，那么 p=1/k
– m被称为等效样本大小的原因是：式子 6.22可被解释为将 n个实际的观察扩大，加上 m个按 p分布的虚拟样本
mn mpnc
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 50
举例：学习分类文本
利用贝叶斯方法学习目标概念，然后用于文本自动过滤，比如
– 我感兴趣的电子新闻稿
– 讨论机器学习的万维网页
本节描述一个基于朴素贝叶斯分类器的文本分类的通用算法，它是目前所知的文本分类的最有效方法之一
问题框架：实例空间 X包含了所有的文本文档，
给定某未知目标函数 f(x)的一组训练样例,f(x)
的值来自某有限集合 V（作为示例，此处令
V={like,dislike}）
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 51
举例：学习分类文本（ 2）
应用朴素贝叶斯分类器的两个主要设计问题：
– 怎样将任意文档表示为属性值的形式
– 如何估计朴素贝叶斯分类器所需的概率
表示文档的方法
– 给定一个文本文档，对每个单词的位置定义一个属性，该属性的值为在此位置上找到的英文单词
假定我们共有 1000个训练文档，其中 700个分类为
dislike,300个分类为 like，现在要对下面的新文档进行分类：
– This is an example document for the naive Bayes classifier,This
document contains only one paragraph,or two sentences.
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 52
举例：学习分类文本（ 3）
计算式
注意此处贝叶斯分类器隐含的独立性假设并不成立。通常，某个位置上出现某个单词的概率与前后位置上出现的单词是相关的
虽然此处独立性假设不精确，但别无选择，否则要计算的概率项极为庞大。
另外实践中，朴素贝叶斯学习器在许多文本分类问题中性能非常好
)|""(),,.|""()(m a xa r g
)|()(m a xa r g
191},{
19
1},{
jjjd i s l i k el i k ev
i
jijd i s l i k el i k evNB
vs e n t e n c e saPvt h isaPvP
vaPvPv
j
j
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 53
举例：学习分类文本（ 4）
需要估计概率项 P(vi)和 P(ai=wk|vi)。前一项可基于每一类在训练数据中的比例很容易得到，后一项含三个参数，出现数据稀疏问题
再引入一个假定以减少需要估计的概率项的数量：假定单词 wk出现的概率独立于单词所在的位置，即
P(ai=wk|vi)=P(wk|vj)
作此假定的一个主要优点在于：使可用于估计每个所需概率的样例数增加了，因此增加了估计的可靠程度
采纳 m-估计方法，即有统一的先验概率并且 m等于词汇表的大小，因此
|| 1)|( V o ca b u la ryn nvwP kjk
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 54
表 6-2 用于学习和分类文本的朴素贝叶斯算法
Learn_Naive_Bayes_Text( Examples,V )
Examples为一组文本文档以及它们的目标值。 V为所有可能目标值的集合。此函数作用是学习概率项 P(wk|vj)和 P(vj)。
– 收集 Examples中所有的单词、标点符号以及其他记号
Vocabulary?在 Examples中任意文本文档中出现的所有单词及记号的集合
– 计算所需要的概率项 P(vj)和 P(wk|vj)
对 V中每个目标值 vj
– docsj?Examples中目标值为 vj的文档子集
– P(vj)?|docsj| / |Examples|
– Textj?将 docsj中所有成员连接起来建立的单个文档
– n?在 Textj中不同单词位置的总数
– 对 Vocabulary中每个单词 wk
nk?单词 wk出现在 Textj中的次数
P(wk|vj)?(nk+1) / (n+|Vocabulary|)
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 55
表 6-2 用于学习和分类文本的朴素贝叶斯算法（ 2）
Classify_Naive_Bayes_Text( Doc )
对文档 Doc返回其估计的目标值,ai代表在 Doc中的第 i个位置上出现的单词
–positions?在 Doc中的所有单词位置，
它包含能在 Vocabulary中找到的记号
–返回 vNB, p o s itio n si jijVvNB vaPvPv
j
)|()(m a xa r g
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 56
实验结果
Joachims将此算法用于新闻组文章的分类
– 每一篇文章的分类是该文章所属的新闻组名称
– 20个新闻组，每个新闻组有 1000篇文章，共 2万个文档
– 2/3作为训练样例,1/3进行性能测量
– 词汇表不包含最常用词（比如 the,of）和罕见词（数据集中出现次数少于 3）
Lang用此算法学习目标概念“我感兴趣的新闻组文章”
– NewsWeeder系统，让用户阅读新闻组文章并为其评分，然后使用这些评分的文章作为训练样例，来预测后续文章哪些是用户感兴趣的
– 每天向用户展示前 10%的自动评分文章，它建立的文章序列中包含的用户感兴趣的文章比通常高 3~4倍
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 57
贝叶斯信念网
朴素贝叶斯分类器假定各个属性取值在给定目标值 v下是条件独立的，从而化简了最优贝叶斯分类的计算复杂度。但在多数情况下，这一条件独立假定过于严厉了。
贝叶斯信念网描述的是一组变量所遵从的概率分布，
它通过一组条件概率来指定一组条件独立性假设
贝叶斯信念网中可表述变量的一个子集上的条件独立性假定，因此，贝叶斯信念网提供了一种中间的方法，
它比朴素贝叶斯分类器的限制更少，又比在所有变量中计算条件依赖更可行
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 58
贝叶斯信念网（ 2）
贝叶斯信念网描述了一组变量上的概率分布
考虑一任意的随机变量集合 Y1...Yn，其中每个
Yi可取的值集合为 V(Yi)
变量集合 Y的联合空间为叉乘 V(Y1)?..,?V(Yn)
在此联合空间上的概率分布称为联合概率分布，
联合概率分布指定了元组的每个可能的变量约束的概率
贝叶斯信念网则对一组变量描述了联合概率分布
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 59
条件独立性
精确定义条件独立性
– 令 X,Y和 Z为 3个离散值随机变量，当给定 Z值时 X服从的概率分布独立于 Y的值，称 X在给定 Z时条件独立于 Y，即
– 上式通常简写成 P(X|Y,Z)=P(X|Z)
扩展到变量集合
– 下面等式成立时，称变量集合 X1...Xl在给定变量集合 Z1...Zn时条件独立于变量集合 Y1...Ym
条件独立性与朴素贝叶斯分类器的之间的关系
)|(),|(,,kikjikji zZxXPzZyYxXPzyx
).,,|.,,().,,,.,,|.,,( 11111 nlnml ZZXXPZZYYXXP?
)|()|( )|(),|()|,( 21 22121 VAPVAP VAPVAAPVAAP
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 60
贝叶斯信念网的表示
贝叶斯信念网（简称贝叶斯网）表示一组变量的联合概率分布
一般地说，贝叶斯网表示联合概率分布的方法是指定一组条件独立性假定（有向无环图）以及一组局部条件概率集合
图 6-3，联合空间中每个变量在贝叶斯网中表示为一个节点，每个变量需要两种类型的信息
– 网络弧表示断言“此变量在给定其直接前驱时条件独立于其非后继”
– 每个变量有一个条件概率表，描述了该变量在给定其立即前驱时的概率分布
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 61
贝叶斯信念网的表示（ 2）
对网络变量的元组 <Y1...Yn>赋以所希望的值 (y1...yn)的联合概率计算公式如下：
所有变量的局部条件概率表以及由网络所描述的一组条件独立假定，描述了该网络的整个联合概率分布
ni iin YP a re n tsyPyyP 11 ))(|(),.,,,(
4.0),|( Tr u eupB u s T o u r G r oTr u eS t o r mTr u eC a m p f ir eP
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 62
贝叶斯信念网的推理
可以用贝叶斯网在给定其他变量的观察值时推理出某些目标变量的值
由于所处理的是随机变量，所以一般不会赋予目标变量一个确切的值
真正需要推理的是目标变量的概率分布，它指定了在给予其他变量的观察值条件下，目标变量取每一个可能值的概率
在网络中所有其他变量都确切知道的情况下，这一推理步骤很简单
一般来说，贝叶斯网络可用于在知道某些变量的值或分布时计算网络中另一部分变量的概率分布
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 63
贝叶斯信念网的推理（ 2）
对任意贝叶斯网络的概率的确切推理已经知道是一个 NP难题
Monte Carlo方法提供了一种近似的结果，
通过对未观察到的变量进行随机采样
理论上，即使是贝叶斯网络中的近似推理也可能是 NP难题
实践中许多情况下近似的方法被证明是有效的
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 64
学习贝叶斯信念网
从训练数据中学到贝叶斯信念网，有多种讨论的框架：
– 网络结构可以预先给出，或由训练数据中得到
– 所有的网络变量可以直接从每个训练样例中观察到，或某些变量不能观察到
如果网络结构已知且变量可以从训练样例中完全获得，
那么得到条件概率表就比较简单
如果网络结构已知，但只有一部分变量值能在数据中观察到，学习问题就困难多了。这类似于在人工神经网络中学习隐藏单元的权值
Russtll（ 1995）提出了一个简单的梯度上升过程以学习条件概率表中的项，相当于对表项搜索极大似然假设
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 65
贝叶斯网的梯度上升训练
令 wijk代表条件概率表的一个表项，即在给定父节点 Ui取值 uik时，网络变量 Yi值为
yij的概率
例如图 6-3,wijk为最右上方的表项，那么
Yi为变量 Campfire,Ui是其父节点的元组
<Storm,BusTourGroup>,yij=True，且
uik=<False,False>
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 66
贝叶斯网的梯度上升训练（ 2）
lnP(D|h)的梯度由对每个 wijk求导数得到
例如，为计算图 6-3中表左上方的表项的 lnP(D|h)的导数，
需要对 D中每个训练样例 d计算 P(Campfire=True,
Storm=False,BusTourGroup=False|d)
当训练样例中无法观察到这些变量时，这些概率可用标准的贝叶斯网从 d中观察到的变量中推理得到
这些量能够很容易地从贝叶斯网推理过程中得到，几乎不需要附加的开销
Dd ijk ikiijiijk w duUyYPw hDP )|,()|(ln
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 67
贝叶斯网的梯度上升训练（ 3）
式子 6.25的推导
– 用 Ph(D)来表示 P(D|h)
– 假定在数据集 D中的各样例 d都是独立抽取的
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 68
Dd i j k
ikijh
Dd ikijh
ikijh
Dd ikijh
ikhikijh
ikijh
ikhhikijh
Dd h
Dd
ikhikijh
h
Dd
ikhi j kikijh
i j kh
Dd
ikhikijhikijh
i j kh
ikh
kj
ikijhikijh
Dd i j kh
kj
ikijhikijh
Dd i j kh
i j k
h
Dd h
Dd
i j k
h
Dd
h
i j ki j k
h
w
duyP
uyP
duyP
uyP
uPduyP
uyP
uPdPduyP
dP
uPuydP
dP
uPwuydP
wdP
uPuyPuydP
wdP
uPuyPuydP
wdP
uyPuydP
wdP
w
dP
dP
w
dP
dP
ww
DP
)|,(
)|(
)|,(
),(
)()|,(
),(
)()()|,(
)(
1
)(),|(
)(
1
)(),|(
)(
1
)()|(),|(
)(
1
)()|(),|(
)(
1
),(),|(
)(
1
)(
)(
1
)(ln
)(ln
)(ln
'
','
''''
','
''''
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 69
贝叶斯网的梯度上升训练（ 4）
更新权值
归一化处理，保持在区间 [0,1]之间，且
jwijk对所有 i,k保持为 1
这个算法只保证找到局部最优解，替代梯度上升的一个算法是 EM算法
Dd ijk ikijhijkijk w duyPww )|,(?
ki ijkijkijk www,
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 70
学习贝叶斯网的结构
如果贝叶斯网的结构未知，那么需要学习贝叶斯网的结构
Cooper & Herskovits提出了一个贝叶斯评分尺度，以便从不同网络中进行选择
Cooper & Herskovits提出了算法 K2，启发式算法，用于在数据完全可观察时学习网络结构
基于约束的学习贝叶斯网络结构：从数据中推导出独立和相关的关系，然后用这些关系来构造贝叶斯网
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 71
EM算法
在许多实际的学习问题框架中，相关实例特征中只有一部分可观察到
已有许多方法被提出来处理存在未观察到变量的问题
– 比如，如果某些变量有时能观察到，有时不能，那么可以用观察到该变量的实例去预测未观察到的实例中的变量的值
EM算法是存在隐含变量时广泛使用的一种学习方法，
可用于变量的值从来没有被直接观察到的情形，只要这些变量所遵循的概率分布的一般形式已知
– 用于贝叶斯网的训练
– 用于马尔可夫模型的训练
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 72
估计 k个高斯分布的均值
考虑 D是一个实例集合，它由 k个不同正态分布的混合所得分布生成
每个实例使用一个两步骤的过程形成：
– 首先，随机选择 k个正态分布中的一个
– 其次，随机变量 xi按照此选择的分布生成
考虑一个简单情形：
– 单个正态分布的选择基于均匀的概率进行，且 k个正态分布有相同的方差
– 学习任务：输出一个假设 h=<?1...?k>，描述 k个分布中每个分布的均值，找到极大似然假设，即使得
p(D|h)最大化的假设
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 73
估计 k个高斯分布的均值（ 2）
当给定从一个正态分布中抽取的数据实例 x1,...,xm时，
很容易计算该分布的均值的极大似然假设，它是 6.4节中式子 6.6的一个特例，表示如下
然而，现在的问题涉及 k个不同正态分布，而且不知道哪个实例是哪个分布产生的。这是一个涉及隐藏变量的典型例子
对于图 6-4的例子，每个实例的完整描述是三元组
<xi,zi1,zi2>，其中 xi是第 i个实例的观测值,zi1和 zi2表示哪个正态分布被用来产生 xi，是隐藏变量
mi imi iML xmx 11 2 1)(m ina r g
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 74
估计 k个高斯分布的均值（ 3）
如果 zi1和 zi2的值可知，就可用式子 6.27来解决，
否则使用 EM算法
EM算法根据当前假设 <?1...?k>，不断地再估计隐藏变量 zij的期望值，然后用这些隐藏变量的期望值重新计算极大似然假设
以图 6-4为例，先将假设初始化为 h=<?1,?2>
– 计算每个隐藏变量 zij的期望值 E[zij]，假定当前假设
h=<?1,?2>成立
– 计算一个新的极大似然假设 h’=<?’1,?’k>，假定每个隐藏变量 zij所取值是第一步得到的期望值 E[zij]。
将假设替换为 h’=<?’1,?’2>，然后循环
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 75
两个步骤的计算式
E[zij]正是实例 xi由第 j个正态分布生成的概率
第二步，使用第一步得到的 E[zij]来导出一新的极大似然假设
2
1
)(
2
1
)(
2
1
2
1
2
2
2
2
)|(
)|(
][
n
x
x
n
ni
ji
ij
ni
ji
e
e
xxp
xxp
zE
m
i
ij
m
i
iij
j
zE
xzE
1
1
][
][
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 76
两个步骤的计算式（ 2）
第二步中的表达式类似于式 6.28，只是变成了加权样本均值
EM算法的要点：当前的假设用于估计未知变量，而这些变量的期望值再被用于改进假设
可以证明：算法的每一次循环中,EM算法能使似然 P(D|h)增加，除非 P(D|h)达到局部最大，
因此算法收敛到一个局部最大似然假设
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 77
EM算法的一般表述
EM算法可用于许多问题框架：其中需要估计一组描述基准概率分布的参数，只给定了由此分布产生的全部数据中能观察到的一部分。
– 上面的二均值问题中，感兴趣的参数是?=<?1,?2>，
全部数据是三元组 <xi,zi1,zi2>，而只能观察到 xi
一般地，令待估计参数是?，全部数据 Y=X?Z，
其中 X是可观察数据,Z是未观察数据。
Z可看作一个随机变量，它的概率分布依赖于参数?和已知数据 X
Y也是一个随机变量，因为它由随机变量 Z定义
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 78
EM算法的一般表述（ 2）
EM算法通过搜寻使 E[lnP(Y|h’)]最大的 h’来寻找极大似然假设 h’，其合理性是：
– P(Y|h’)是给定假设 h’下全部数据 Y的似然度，因此找到使得这个值最大的 h’是合理的
– 对数 lnP(Y|h’)最大化也使 P(Y|h’)最大化
– 由于 Y是一个随机变量，因此 P(Y|h’)无法计算，转而计算它的期望值 E[lnP(Y|h’)]
Y的概率分布由待估计的参数决定,EM算法使用当前假设 h代替实际参数，来估计 Y的概率分布
定义函数 Q(h’|h)=E[lnP(Y|h’)|h,X]
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 79
EM算法的一般表述（ 3）
EM算法的一般形式，重复下面的步骤，直至收敛
– 估计（ E）步骤：使用当前假设 h和观察到的数据 X
来估计 Y上的概率分布以计算 Q(h’|h)
Q(h’|h)?E[lnP(Y|h’)|h,X]
– 最大化（ M）步骤：将假设 h替换为使 Q函数最大化的假设 h’
h?argmaxh’Q(h’|h)
当函数 Q连续时,EM算法收敛到似然函数
P(Y|h’)的一个不动点，它保证收敛到一个局部最大值
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 80
K均值算法的推导
问题框架
– 要估计 k个正态分布的均值?=<?1...?k>
– 观察到的数据是 X={<xi>}
– 隐藏变量 Z={<zi1,...,zik>}表示 k个正态分布中哪一个生成 xi
用于 K均值问题的表达式 Q(h’|h)的推导
– 单个实例的概率
kj jiij xz
ikiii ehzzxphyp 1
2'2 )(2 1
21 2
1)'|,.,.,,()'|(
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 81
K均值算法的推导（ 2）
– 所有实例的概率的对数
– 计算期望值
m
i
k
j
jiij
m
i
i
m
i
i
xz
hyp
hyphYP
1 1
2'
22
1
1
)(
2
1
2
1
ln
)'|(ln
)'|(ln)'|(ln
m
i
k
j
jiij
m
i
k
j
jiij
xzE
xzEhYPE
1 1
2'
22
1 1
2'
22
)]([2 1
2
1ln
)(2 1
2
1ln)]'|([ ln
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 82
K均值算法的推导（ 3）
– 求使 Q函数最大的假设
– 解上式得到
– 另外
m
i
k
j
jiij
h
m
i
k
j
jiij
hh
xzE
xzEhhQ
1 1
2'
'
1 1
2'
22''
m a xa r g
2
1
2
1lnm a xa r g)|'(m a xa r g
m
i
ij
m
i
iij
j
zE
xzE
1
1
][
k
n
x
x
ji
ji
e
ezijE
1
)(2 1
2)(2 1
2
2
2
][
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 83
小结
概率学习方法利用关于不同假设的先验概率，以及在给定假设时观察到不同数据的概率的知识
贝叶斯方法提供了概率学习方法的基础，基于这些先验和数据观察假定，赋予每个假设一个后验概率
贝叶斯方法确定的极大后验概率假设是最可能成为最优假设的假设
贝叶斯最优分类器将所有假设的预测结合起来，并用后验概率加权，以计算对新实例的最可能分类
朴素贝叶斯分类器增加了简化假定：属性值在给定实例的分类时条件独立
贝叶斯信念网能够表示属性的子集上的一组条件独立性假定
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 84
小结（ 2）
贝叶斯推理框架可对其他不直接应用贝叶斯公式的学习方法的分析提供理论基础
最小描述长度准则建议选取这样的假设，它使假设的描述长度和给定假设下数据的描述长度的和最小化。贝叶斯公式和信息论中的基本结论提供了此准则的根据
EM算法提供了一个通用的算法，在存在隐藏变量时进行学习。算法开始于一个任意的初始假设，然后迭代地计算隐藏变量的期望值，再重新计算极大似然假设，这个过程收敛到一个局部极大似然假设和隐藏变量的估计值
2003.12.18 机器学习 -贝叶斯学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 85
补充读物
Casella & Berger 1990在概率和统计方面的介绍性文章
Maisel 1971,Speigel 1991的快速参考书籍
Duda & Hart 1973对贝叶斯分类器和最小平方误差分类器的介绍
Domigos & Pazzani 1996分析了朴素贝叶斯分类器输出最优分类的条件
Cestnik 1990讨论了 m-估计
Michie et al,1994将不同贝叶斯方法与决策树等其他算法进行比较
Chauvin & Rumelhart1995提供了基于反向传播算法的神经网络的贝叶斯分析
Rissanen1 1983,1989讨论了最小描述长度准则
Quinlan & Rivest 1989描述了利用最小描述长度准则避免决策树过度拟合的方法
