机器学习 课件 第7章　概率无向图模型

概率有向图模型—贝叶斯网络使用有向无环图表示变量之间的关系概率有向图模型基本原理是关于变量的一个联合概率分布例：概率乘积规则展开K个变量的概率有向图模型？每个条件概率对应⼀条有向边，起点是条件概率中条件随机变量对应的结点每个变量对应一个结点，如果存在从结点到结点的有向边，则结点是结点的父结点，结点是结点的子结点概率有向图模型K个变量的联合概率分布表示为概率乘积规则展开…………完全⼀般的联合概率分布全连接概率图模型非全连接概率图模型？对应概率有向图模型请思考：下式如何用概率图模型进行表示，它是全连接的吗？概率有向图模型结论：图的所有结点上定义的联合概率分布由每个结点上的条件概率分布的乘积表示，每个条件概率分布的条件都是图中结点的父结点所对应的变量。表示结点的父结点的集合此公式表示有向图模型的联合概率分布的分解属性。⼀个有K个结点的图，联合概率：有向图不能存在有向环贝叶斯网络起源于贝叶斯统计学，是以概率论为基础的有向图模型。

贝叶斯网络是用来表示变量间概率依赖关系的有向无环图。贝叶斯网络在统计学、推荐系统、图像识别等领域具有广泛的应用价值。表示随机变量，是对过程、事件、状态等实体的某些特征的描述表示变量间的概率依赖关系两个重要条件独立性结点与其非后代结点条件独立给定一个结点的马尔可夫覆盖，这个结点和网络所有其他结点条件独立结点有向边贝叶斯网络贝叶斯网络

贝叶斯网络

N表示为其中表示结点关系的有向无环图，即贝叶斯网络结构；表示每个结点Vi在它父结点集pa(Xi)条件下的条件概率，即贝叶斯网络参数。，结点集，结点集

，贝叶斯网络特点一种不定性因果关联模型。具有强大的不确定性问题处理能力。具有良好的可理解性和逻辑性。能有效地进行多源信息表达与融合。结合先验知识，用图形化模型描述数据间的相互关系，便于进行预测分析。51234贝叶斯定理贝叶斯定理随机事件A

和B

的条件概率：推导

贝叶斯定理贝叶斯定理可以表述下列情形：设

是观测向量，是未知参数向量，、

的联合分布密度是

它们的边际密度分别为

、

，通过观测向量获得未知参数向量的估计，则

其中，

为

的先验分布对未知参数向量的估计综合了它的先验信息和样本信息传统的参数估计方法只考虑了样本信息（最大似然估计）贝叶斯定理贝叶斯方法对未知参数向量估计：

将未知参数

看成是随机向量。这是贝叶斯方法与传统参数估计方法的最大区别。

计算后验分布密度，做出对未知参数的推断。

123贝叶斯定理贝叶斯假设：

在处理无信息先验分布，尤其是未知参数无界的情况时遇到困难。

经验贝叶斯估计：

把经典的方法和贝叶斯方法结合在一起，用经典的方法获得样本的边际密度

贝叶斯网络—有向分离（D-Separation）有向分离对应于概率论中的条件独立性，目的：从图的角度寻找结点之间的条件独立性。

考虑三类特殊的结点连接：其中结点分别称为头对尾结点、尾对尾结点和头对头结点贝叶斯网络—有向分离根据条件独立知识：在顺序连接和发散连接中，未知情况下，和

之间存在相关性；已知情况下，和关于条件独立（即

和被有向分离)。

当结点状态贝叶斯网络—有向分离有向分离

有向分离的条件贝叶斯网络—有向分离Z包含l中不同于

和

的某一头对尾结点；Z包含l中不同于

和

的某一尾对尾结点；Z不包含l中不同于

和

的某一头对头结点及其子孙结点。

贝叶斯网络—有向分离结点集之间的有向分离判断

G中结点集X和Y是否被Z有向分离

X和Y是否在新的有向无环图G’无连接路径

贝叶斯网络—有向分离定理G’是由G根据下面的规则修剪G所得：从G中删除所有不属于删除从Z中结点输出的所有边。的叶结点，重复这一步直到无满足条件的叶结点存在；通过定理，可以将有向图简化成非连接图，这样可以在线性时间内判断是否满足有向分离，从而降低分析的复杂度。贝叶斯网络—有向分离请思考：有向分离对应于条件独立，在贝叶斯网络中，当结构图中X和Y被Z有向分离，根据有向分离定义可以推出X和Y必然是关于Z条件独立。不一定当X和Y关于Z条件独立时，是否X和Y被Z有向分离呢?

贝叶斯网络—有向分离

贝叶斯网络构造TheEnd贝叶斯网络结构学习主讲人：李侃

贝叶斯网络结构学习从给定的数据集中学出贝叶斯网络结构，即各结点之间的依赖关系；只有确定了结构才能学习网络参数，即表示各结点之间依赖性的条件概率。根据训练数据是否存在缺失

完整数据结构学习

缺失数据结构学习贝叶斯网络结构学习网络结构学习基于搜索评分的方法基于约束的方法修复数据集的方法近似计算的方法

贝叶斯网络结构学习从给定的数据集中学出贝叶斯网络结构，即各结点之间的依赖关系；只有确定了结构才能学习网络参数，即表示各结点之间依赖性的条件概率。根据训练数据是否存在缺失

完整数据结构学习

缺失数据结构学习贝叶斯网络结构学习网络结构学习基于搜索评分的方法基于约束的方法修复数据集的方法近似计算的方法基于搜索评分的方法贝叶斯网络结构学习问题看成是优化问题，通过给定结构的评分函数，利用搜索算法，去寻找评分最优的网络结构。贝叶斯网络结构学习—完整数据结构学习关键点确定合适的搜索策略确定评分函数

基于搜索评分的方法

基于搜索评分的方法给定训练数据D及一个可能的结构G，如何去计算其评分f(G，D)。如果评分函数能够满足一些特性如一致性，则其评分效果更佳。评分函数

基于贝叶斯的评分基于信息论的评分基于搜索评分的方法基于贝叶斯的评分函数

基于搜索评分的方法基于贝叶斯的评分函数

基于搜索评分的方法基于贝叶斯的评分函数

基于搜索评分的方法BD（BayesianDirichlet）评分

基于搜索评分的方法基于贝叶斯的评分函数上式两边同时取对数，则BD(BayesianDirichlet)评分：基于搜索评分的方法

BD（BayesianDirichlet）评分基于贝叶斯的评分函数

基于搜索评分的方法K2评分基于贝叶斯的评分函数

基于搜索评分的方法BDeu评分基于贝叶斯的评分函数基于信息论的评分函数基于搜索评分的方法

基本思想：将训练数据进行压缩，利用最小描述长度MDL(minimumdescriptionlength)来挖掘其中的规则。

基于搜索评分的方法基于信息论的评分函数LL

(log-likelihood)评分函数

基于搜索评分的方法基于信息论的评分函数AIC(akaikeinformationcriterion)评分函数

基于搜索评分的方法基于信息论的评分函数BIC(bayesianinformationcriterion)评分函数

基于搜索评分的方法基于信息论的评分函数MDL评分函数

基于搜索评分的方法基于信息论的评分函数两种方法的比较基于搜索评分的方法能够更好地区分训练样本较大的贝叶斯网络结构。适用小样本的训练数据，尤其是BIC评分函数所学习到的结构效果更好。基于贝叶斯的评分函数基于信息论的评分函数搜寻最优结构定义评分函数寻找最高评价值的搜索最优问题采用启发式或元启发式搜索方法基于搜索评分的方法学习贝叶斯网络结构是NP一难问题搜索算法K2算法爬山算法GES算法基于进化计算的方法基于搜索评分的方法基于搜索评分的方法K2算法搜索算法基于贪婪搜索的结构学习算法采用评分来衡量结构的优劣性，并利用结点序以及正整数来限制搜索空间的大小

基于搜索评分的方法爬山（hillclimbing）算法搜索算法加边、减边以及删除边的局部操作，

根据评分确定是否选择该操作。通过贪婪选择来判断是否对模型结构进行更新。搜索过程简单，但无法保证搜索到的结构一定是最优的。GES

(greedyequivalentsearch)算法从一个空图出发，采用两个不同的搜索阶段来寻找评分最高的结构。采用贪心前向搜索法（GFS）来不断地在空图中加边，直至评分值无法提高为止；利用贪心反向搜索法（greedybackwardsearch，GBS）在图中不断地删除边，直至评分值不能提高为止。基于搜索评分的方法搜索算法基于约束的方法通过统计独立性测试来学习结点间的独立性和相关性，并根据独立性或相关性构建出相应的有向无环图结构。贝叶斯网络结构学习—完整数据结构学习

PC算法由Peter和Clark提出并以他们名字命名的贝叶斯网络结构学习方法基本思想：通过寻找结点

X的父结点和子结点集合

pc(X)，以及寻找v-结构来学习DAG结构。基于约束的方法基于约束的方法—PC算法从一个完全连接的无向图出发，以Z=ø作为第一次CI测试来限制潜在的邻居结点集。对于每个结点，首先考虑邻居结点集为l的子集结点来判断是否条件独立，然后结点集为2，不断增加结点集数目直至收敛。对于v-结构，通过检查将vi和vj分离的结点集合，不需要额外的CI测试来判断是否存在v-结构TPDA算法制定（drafting）增厚（thickening）变薄（thinning）基于约束的方法从一个空图出发，通过简单的互信息测试来产生一组初始边，从而形成一个单连接的无环图通过CI测试检查每对结点间是否能被有向分离，如果不能，则为其添加边对图中每条边进行检查，通过判断其对应的结点对之间是否存在条件独立，来决定是否移除边。基于三层独立性测试的结构学习方法两种结构学习方法的局限

基于约束的方法贝叶斯网络结构学习—完整数据对于数据的要求性较高，需要训练数据无噪声且真实，训练数据量需要足够大基于搜索评分的方法

复杂度高，当结点较多时，会使搜索空间巨大，从庞大搜索空间中搜索最优结构耗时混合约束和搜索评分的结构学习方法思想：通过独立性测试来降低搜索空间的大小，再利用搜索评分的方法来寻找最优的网络结构。贝叶斯网络结构学习—完整数据MMHC(max-minhillclimbing)算法：将局部学习、CI测试以及搜索评分方法进行融合，通过采用独立性测试来学习出结构的框架，然后采用搜索评分的方式来确定网络中的边以及边的方向。

贝叶斯网络结构学习从给定的数据集中学出贝叶斯网络结构，即各结点之间的依赖关系；只有确定了结构才能学习网络参数，即表示各结点之间依赖性的条件概率。根据训练数据是否存在缺失

完整数据结构学习

缺失数据结构学习贝叶斯网络结构学习网络结构学习基于搜索评分的方法基于约束的方法修复数据集的方法近似计算的方法缺失数据条件下学习网络结构所有评分函数无法分解成只与局部结构相关的因式需要执行非线性的优化过程为评判当前网络结构必须评估其所有的“邻居”贝叶斯网络结构学习缺失数据条件下学习网络结构EM算法高效地从不完整数据条件下学习网络参数，具有较高的精度。一般是收敛到局部最优结构。SEM算法只对当前选中的网络结构使用EM算法，进行概率分布评估；对于未被选中的网络并不使用EM算法。每评价一个当前网络的“邻居”集，只调用一次EM算法，节省了计算开销。贝叶斯网络结构学习TheEnd贝叶斯网络参数学习主讲人：李侃贝叶斯网络参数学习（参数估计）：在给定网络结构的基础上，从训练数据中学习得到结点的条件概率分布表的过程。贝叶斯网络参数学习贝叶斯网络主要是处理离散数据，因此在参数学习过程中，通常假设网络中变量的状态是离散的或是呈现高斯分布。在实际应用中，结点变量一般是不满足高斯分布的，通常可以采用等频率或者等区间的离散型方法对训练数据进行离散化。训练数据中所有变量状态都可观测贝叶斯方法(Bayesianestimation，BE)最大似然估计方法(maximumlikelihoodestimation，MLE)某些结点变量的状态未必能观测最大期望(expectationmaximization，EM)贝叶斯网络参数学习最大似然估计方法(maximumlikelihoodestimate,MLE)实例数据完备情况下的学习方法。它依据参数与数据集的似然程度来选择参数。贝叶斯网络参数学习最大似然估计方法

贝叶斯网络—贝叶斯网络参数学习最大似然估计方法

贝叶斯网络—贝叶斯网络参数学习

最大似然估计方法概率是频率的一种逼近，属于传统统计方法。贝叶斯方法基于贝叶斯公式，认为代表不确定性的概率参数是由先验知识和观察到数据集共同决定的。贝叶斯网络参数学习

贝叶斯方法

贝叶斯网络参数学习贝叶斯方法

贝叶斯网络参数学习贝叶斯方法

贝叶斯网络参数学习常见的共轭分布二项分布多项分布正态分布Gamma分布Poisson分布Dirichlet分布（最常用）Dirichlet分布

贝叶斯网络参数学习—贝叶斯方法Dirichlet分布

贝叶斯网络—贝叶斯网络参数学习Dirichlet分布

贝叶斯网络—贝叶斯网络参数学习

数据不完整时贝叶斯网络的参数学习在数据不完备时，似然函数的计算将变得很复杂．精确计算极大值几乎不可能，只能近似求出似然函数的极大值，并将该点的概率分布作为估计值。贝叶斯网络参数学习近似方法Monte-Carlo方法高斯逼近Laplace近似EM算法求ML（极大似然）MAP（极大后验）Monte-Carlo方法Geman等提出的Gibbs采样方法是众多Monte-Carlo方法中常用的一种。基本思想是以Gibbs采样估计变量集上联合概率分布的数学期望。Monte-Carlo方法样本越大，运行时间越长，结果越精确，但计算复杂度是事例数的指数幕次。数据不完整时贝叶斯网络的参数学习Monte-Carlo方法

数据不完整时贝叶斯网络的参数学习

Monte-Carlo方法

数据不完整时贝叶斯网络的参数学习高斯逼近

数据不完整时贝叶斯网络的参数学习高斯逼近数据不完整时贝叶斯网络的参数学习

高斯逼近数据不完整时贝叶斯网络的参数学习

Laplace近似

数据不完整时贝叶斯网络的参数学习

Laplace近似

数据不完整时贝叶斯网络的参数学习贝叶斯信息标准（bayesianinformationcriterion,BIC）EM算法最常用的从不完整数据条件下统计概率分布的方法。数据不完整时贝叶斯网络的参数学习

EM算法

数据不完整时贝叶斯网络的参数学习EM算法

数据不完整时贝叶斯网络的参数学习

TheEnd隐马尔可夫模型主讲人：李侃

隐马尔可夫模型

(hiddenMarkovmodel，HMM)

描述由隐马尔可夫链随机生成观测序列的过程，属于生成模型。它是结构简单的动态贝叶斯网，是一种有向图模型，在语音识别，自然语言处理以及生物信息等领域具有广泛的应用价值。隐马尔可夫模型马尔可夫过程马尔可夫过程(Markovprocess)，因俄罗斯数学家AndreyAndreyevichMarkov而得名，代表数学中具有马尔可夫性质的离散随机过程。隐马尔可夫模型每个状态的转移只依赖于之前的n个状态，这个过程被称为n

阶模型，其中