开发者社区> apachecn_飞龙> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

斯坦福 CS228 概率图模型中文讲义 四、贝叶斯网络

简介: 四、贝叶斯网络 原文:Bayesian networks 译者:飞龙 协议:CC BY-NC-SA 4.0 自豪地采用谷歌翻译 我们从表示的话题开始:我们如何选择概率分布来为世界的一些有趣方面建模? 建立一个好的模型并不容易:我们在介绍中看到,垃圾邮件分类的朴素模型需要我们指定一些参数,这些参数对于英文单词数量是指数级的! 在本章中,我们将了解避免这类复杂事物的一种方法。
+关注继续查看

四、贝叶斯网络

原文:Bayesian networks

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

我们从表示的话题开始:我们如何选择概率分布来为世界的一些有趣方面建模? 建立一个好的模型并不容易:我们在介绍中看到,垃圾邮件分类的朴素模型需要我们指定一些参数,这些参数对于英文单词数量是指数级的!

在本章中,我们将了解避免这类复杂事物的一种方法。 我们将要:

  • 学习有效和通用的技术,仅使用少数参数来参数化概率分布。
  • 了解如何通过有向无环图(DAG)来优雅地描述所得模型。
  • 研究 DAG 结构与所描述的分布的模型假设之间的联系;这不仅会使这些模型假设更加明确,而且还会帮助我们设计更有效的推理算法。

我们将在这里看到的模型称为贝叶斯网络。 在下一章中,我们还会看到第二种方法,它涉及无向图,也称为马尔可夫随机场。

概率建模与贝叶斯网络

有向图模型(也称为贝叶斯网络)是一系列概率分布,它们允许紧凑的参数化,可以使用有向图来自然描述。

这个参数化背后的总体思路非常简单。

回想一下,通过链式法则,我们可以将任意概率p写为:

紧凑贝叶斯网络是一种分布,右侧的每个因子仅依赖于少量的祖先变量

例如,在一个有五个变量的模型中,我们可以选择用 来近似因子 。 在这种情况下,我们写作

当变量是离散的时候(我们会认为问题通常会是这种情况),我们可以将因子 看作概率表,其中行对应于 的赋值,并且列对应于 的值;条目包含实际概率 。 如果每个变量取d个值并且最多有k个祖先,那么整个表将包含最多O(dk + 1)个条目。 由于每个变量都有一个表,因此只用O(ndk + 1)个参数(与朴素方法的O(dn)相比),就可以简洁地描述整个概率分布。

图表示

这种形式的分布可以自然地表示为有向无环图,其中顶点对应于变量xi并且边表明了依赖关系。 特别是,我们将每个节点的父母设置为 的祖先

作为一个例子,考虑考试中的学生成绩g的模型; 成绩取决于几个因素:考试的难度d,学生的智力i,他的 SAT 分数s; 它也会影响教授课程的教授的推荐信的质量l。 每个变量都是二元的,除了g,它取 3 个可能的值。

描述考试中学生表现的贝叶斯网络模型。 分布可以表示为条件概率分布的乘积,由表指定。 这些分布的形式由图中的边描述。

5 个变量的联合概率分布自然因式分解如下:

这个分布的图表示是一个 DAG,它可视化地规定随机变量如何相互依赖。 图清楚地表明信件取决于年级,而它又取决于学生的智力和考试的难度。

解释有向图的另一种方式是根据数据如何生成的故事。 在上面的例子中,为了确定推荐信的质量,我们可以首先抽取一个智力水平和一个考试难度;然后,根据这些参数抽取学生的成绩;最后,推荐信是基于该成绩生成的。

在之前的垃圾邮件分类示例中,我们隐式假设电子邮件根据两步过程来生成:首先,我们选择垃圾邮件/非垃圾邮件标签y;然后我们独立地抽取每个词是否存在,并以该标签为条件。

形式定义

形式上,贝叶斯网络是一个有向图G =(V, E)

每个节点i∈V都是随机变量
一个节点有一个条件概率分布(CPD),规定 以父值为条件的概率。

因此,贝叶斯网络定义了概率分布p。 相反,我们说如果概率p可以分解为因式乘积,由G所规定,那么它可以在 DAG G上因式分解。

不难看出,由贝叶斯网络表示的概率将是有效的:显然,它将是非负的,并且可以使用归纳论证(以及使用 CPD 是有效概率的事实)来证明,所有变量赋值的和将为一。 相反,我们也可以通过反例说明,当G包含环时,其相关概率可能不会为一。

贝叶斯网络的依赖

总而言之,贝叶斯网络表示概率分布,它们可以通过更小的,局部条件概率分布(每个变量一个)来产生。 通过以这种形式表达概率,我们向模型中引入了一些假设,即某些变量是独立的。

这就产生了一个问题:通过使用模型贝叶斯网络,以及由G描述的给定结构,我们做了哪些独立性假设? 这个问题很重要,有两个原因:我们应该确切地知道我们正在做什么模型假设(以及它们是否正确);此外,这些信息将有助于我们稍后设计更高效的推理算法。

让我们使用符号I(p)来表示对于联合分布p成立的,所有条件独立性的集合。 例如,如果p(x,y)=p(x)p(y),那么我们说x⊥y∈I(p)

由有向图描述的独立性

结果表明,贝叶斯网络p非常优雅地描述了I(p)中的许多独立性;通过查看三种类型的结构,可以从图中恢复这些独立性。

为了简单起见,我们首先看看具有三个节点A, B, C的贝叶斯网络G。在这种情况下,G基本上只有三种可能的结构,每种结构产生不同的独立性假设。 感兴趣的读者可以使用一些代数来轻松证明这些结果。

三个变量上的贝叶斯网络,编码了不同类型的依赖关系:级联(a,b),公共父级(c)和 V 结构(d)。

  • 公共父级:如果G的形式是A←B→C,并且观察到了B,则A⊥C|B。 但是,如果B未被观察到,则 。 直观地说,这源于一个事实,B包含决定AC结果的所有信息;一旦观察到,没有其他因素影响这些变量的结果。
  • 级联:如果G等于A→B→C,并且再次观察到了B,则再次A⊥C|B。 但是,如果B未被观察到,则 。 这里的直觉是,B再次拥有决定C的结果的所有信息; 因此,A取什么样的值并不重要。
  • V 结构(也称为 Explaining Away):如果GA→C←B,则知道C就结合了AB。换句话说,如果C未被观察,则A⊥B,但如果观察到了C

最后一种情况需要额外的解释。假设C是一个布尔变量,表明我们的草坪在早上是否潮湿;AB对潮湿有两种解释:下雨(用A表示)或喷水器打开(用B表示)。如果我们知道草地是湿的(C为真)并且喷水器没有打开(B是假的),那么A为真的概率必须是 1,因为这是唯一可能的解释。因此,AB并不是独立的。

这些结构清楚地描述了由三变量贝叶斯网络编码的独立性。我们可以通过在任何更大的图上递归地应用它们,来将它们扩展到通用网络。这产生了一种被称为 D-分离的概念(其中d代表有向)。

我们说,如果变量QW没有由活动路径连接,观察到变量O时,QW是 D-分离的。如果对于路径上的每三个连续的变量X, Y, Z,满足下列条件之一,贝叶斯网络结构G中的无向路径被称为在观察变量O条件下活动的:

  • X←Y←ZY未被观测,Y∉O
  • X→Y→ZY未被观测,Y∉O
  • X←Y→ZY未被观测,Y∉O
  • X→Y←ZY或任何后继被观测

例如,在上面的图中,X1X6X2, X3条件下是 D-分离的。

但是,X2, X3X1, X6条件下不是 D-分离的,因为我们可以找到活动路径(X2, X6, X5, X3)

之前有个 CS228 学生创建了一个交互式网络模拟来测试 D-分离。 随意使用它,如果是这样,请通过 Web 应用程序上的反馈按钮提交任何反馈或错误。

D-分离的概念很有用,因为它让我们描述了我们模型中很大一部分依赖关系。 令I(G)={(X⊥Y|Z)},其中X, Y是条件Z下的 D-分离,它是G中 D-分离变量的集合。

事实 [1]:如果pG上隐式分解,那么I(G)⊆I(p)。这里,我们说Gp的 I-map(独立性映射)。

[1] 我们不会正式证明它,但直觉是,如果X, YY, Z是相互依赖的,那么X, Z也是如此。 因此,我们可以根据上面概述的本地依赖性结构,查看相邻节点并传播依赖关系。

换句话说,用G编码的所有独立性都是合理的:G中的 D-分离的变量,在p中是真正独立的。 然而,相反的情况并非如此:分布可能在G上因式分解,但具有在G中未捕获的独立性。

在某种程度上,这几乎是一个无意义的陈述。 如果p(x,y)=p(x)p(y),那么这个分布仍然在图y→x上因式分解,因为我们总是可以使用 CPD ​p(x|y),把它写成p(x,y)=p(x|y)p(y),其中x的概率实际上并不随y变化。 但是,我们可以通过简单地删除不必要的边来构造一个图,匹配p的结构。

有向图的表现力

这引发了我们最后的也许是最重要的问题:有向图可以表示任何分布p的所有独立性吗? 更正式地说,给定一个分布p,我们是否可以构造一个图G,使得I(G)=I(p)

首先,请注意,构造G使得I(G)⊆I(p)非常容易。 因为I(G)=∅,全连通的 DAG G是任何分布的 I-map。

四个变量的全连通贝叶斯网络。这个模型中没有独立性,并且它是任何分布的 I-map。

一个更有意思的问题是,我们能找到p的最小 I-map G,也就是一个 I-map,从G中移除单个边将导致它不再是一个 I-map。这很简单:我们可以从一个完全连接的G开始,并删除边,直到G不再是 I-map。一种方法是遵循图的自然拓扑排序,并删除节点祖先,直到不再可能这样;我们将在进行结构学习时回顾这种修剪方法。

然而,我们真正感兴趣的是,确定概率p是否拥有完美的映射G,其中I(p)=I(G)。不幸的是,答案是否定的。例如,考虑三个变量X, Y, Z的以下分布p:我们从伯努利分布中抽样X,Y~Ber(0.5),并且我们让Z = X xor Y(我们称之为 noisy-xor 示例) 。我们可以使用一些代数来检查,{X⊥Y,Z⊥Y,X⊥Z}∈I(p),但Z⊥{Y,X}∉I(p)。因此,X→Z←Yp的一个 I-map,但我们讨论的三节点图结构都没有完美描述I(p),因此这种分布没有完美的映射。

一个相关的问题是,当存在完美的映射时,它是否是唯一的。 同样,情况并非如此,因为X→YX←Y编码了相同的独立性,但形成不同的图。 更一般地说,如果两个贝叶斯网络G1G2编码相同的依赖性I(G1)=I(G2),它们就是 I-等价的。

两个贝叶斯网络什么时候是 I-等价的? 为了回答这个问题,让我们回到三个变量的简单例子。 我们说下面的每个图都有相同的骨架,这意味着如果我们放弃箭头的方向性,每种情况下我们会获得相同的无向图。

三个变量上的贝叶斯网络

级联结构(a,b)显然是对称的,箭头的方向性并不重要。 实际上,(a,b,c)编码了完全相同的依赖关系。 只要我们不将它们变成 V 结构(d),我们就可以改变箭头的方向。 然而,当我们有 V 结构时,我们不能改变任何箭头:结构(d)是唯一描述依赖关系 的图。 这些例子提供了 I-等价性的下列一般结果的直觉。

事实:如果G, G′具有相同的骨架和相同的 V 结构,则I(G)=I(G′)

同样,直观理解为什么这是真的,这很容易。 如果变量之间的 D-分离相同,则两个图是 I-等价的。 我们可以翻转任何边的方向,除非它形成一个 V 结构,并且图的 D-连通性将保持不变。 我们提请读者阅读 Koller 和 Friedman 的教科书来获得充分的证据。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
相亲app源码,服务器遭受攻击后需要做好的几件事
相亲app源码,服务器遭受攻击后需要做好的几件事
19 0
Jerry眼中的SAP客户数据模型
本文Jerry将介绍八款SAP产品中的客户模型。希望您在阅读完本文之后,能对SAP客户模型设计的思路有一个最最粗浅的了解。 由于Jerry水平和精力所限,本文不会详细阐述这些产品里的客户模型设计细节,而是介绍了一种方法,如果您对这些模型设计感兴趣,可以按照该方法自行深入研究。
36 0
SAP各种产品中的客户主数据模型建模详解
SAP各种产品中的客户主数据模型建模详解
53 0
java的nio之:java的bio流下实现的socket服务器同步阻塞模型和socket的伪异步的socket服务器的通信模型
同步I/O模型的弊端===>每一个线程的创建都会消耗服务端内存,当大量请求进来,会耗尽内存,导致服务宕机伪异步I/O的弊端分析===>当对Socket的输入流进行读取操作的时候,它会一直阻塞下去,知道发生如下三件事情(1)有数据可读(2)可用数据已经读取完毕(3)发生空指针或者I/O异常===>这意味着当对方发送请求或应答消息比较缓慢,或者网络传输比较慢时候,读取输入流的一方的通信线程将被长时间阻塞。
763 0
如何在 Java 中正确使用 wait, notify 和 notifyAll – 以生产者消费者模型为例
wait, notify 和 notifyAll,这些在多线程中被经常用到的保留关键字,在实际开发的时候很多时候却并没有被大家重视。本文对这些关键字的使用进行了描述。 在 Java 中可以用 wait、notify 和 notifyAll 来实现线程间的通信。
1320 0
x3d
JMS中的消息通信模型
1. MQ简介: 消息队列(Message Queue,简称MQ),是应用程序与应用程序之间的一种通信方法。应用程序通过发送和检索出入列队的针对应用程序的数据 - 消息来通信,而无需专用连接来链接它们。
1054 0
如何找到java对应的c/c++源码
很多时候java经常被c鄙视,因为c说我是你的基础,但java竟然有如此强的生命力就必然有其存在的价值。本文不探讨各种开发语言的优劣,仅仅介绍如何找到java对应c/c++实现的源码。
861 0
+关注
apachecn_飞龙
Github:@wizardforcel 简书:@ApacheCN_飞龙 微博:@龙雀 CSDN:@wizardforcel ApacheCN 官网:apachecn.org 机器学习交流群:629470233
719
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载