论文部分内容阅读
摘要：贝叶斯网络是人工智能中不确定知识表示和推理的有力工具。介绍了贝叶斯网络的概念，给出一个实例，分析了贝叶斯网络推理的方法和过程。
关键词：贝叶斯网络；贝叶斯网络推理；概率推理
中图分类号：TP18 文献标识码：A文章编号：1009-3044(2007)15-30834-02
Research and Analysis of Bayesian Networks Inference
HUANG Jian-ming1，FANG Jiao-li1，ZHAO Bo2
(1.Computer Center,Kunming University of Science and Technology，Kunming 650093,China；2.Yunnan Nationalities University，Kunming 650031,China)
Abstract：Bayesian networks is a powerful tool to uncertain knowledge representation and reasoning in Artificial Intelligence。This thesis gives a introduction to the concept of Bayesian networks，and gives one example，the method and process is presented to Bayesian networks inference。
Key words：Bayesian ntworks；Bayesian networks inference；Probability inference
1 引言
贝叶斯网络是一种有向无环图（DAG），由Pearl于1988年提出的一种基于概率论和图论的不确定知识表示和推理模型。它具有坚实的理论基础，知识结构的自然表达方式，灵活的推理能力，方便的决策机制。随着研究的逐渐成熟，贝叶斯网络已被广泛应用在医疗诊断、数据挖掘、模式识别、决策支持等领域。目前贝叶斯网络的研究热点主要集中在结构学习、推理和应用三个方面。
2 贝叶斯网络
贝叶斯网是每个结点都带有一张概率表的有向无环图（DAG），在贝叶斯网中，结点表示问题域中的随机变量，弧表示这些变量之间的条件依赖关系。每一个结点都包含一张概率表，把各结点和它的直接父结点关联起来。
定义：贝叶斯网络是一个有向无环图，它可以表示为一个三元组（N,E,P）。N是一组结点的集合，N={x1,x2,…,xn}，每一个结点代表一个变量(属性)。Ｅ是一组有向边的集合，E={|xi≠xj并且xi,xj∈N}。每一条边表示变量xi,xj具有因果关系(xi是xj的因，xj是xi的果)。P是一组条件概率的集合，P={p(xi|πi)|p(xi|πi)}表示xi的父亲们πi对xi的影响，p(xi|πi)表示给定条件πi，xi发生概率}。
定理：一个贝叶斯网络表示的联合概率函数p=(x1,x2,…,xn)定义为：（假设贝叶斯网有n个结点）p=(x1,x2,…,xn)=■p(xi|πi)，其中πi为xi的父亲结点的集合。P=(x1,x2,…,xn)表示事件x1,x2,…,xn同时发生的概率。
图1是一个简单的贝叶斯网，表示下雪、堵车、摔交、迟到、骨折之间的关系。它表示的联合概率函数为：
p(a,b,c,d,e)=p(a)p(b|a)p(c|a)p(d|b,c)p(e|c)
贝叶斯网络中的一个结点，如果它的父结点已知，则它条件独立于它的所有非后代结点。图1中，给定C，则E条件独立于A，B，D。
除了条件独立性外，每个结点还关联一个概率表。
（1）如果结点X没有父结点，则表中只包含先验概率P（X）。
（2）如果结点X只有一个父结点Y，则表中包含条件概率P（X｜Y）。
（3）如果结点X有多个父结点{Y1，Y2，．．．，Yk}，则表中包含条件概率P（X｜Y1，Y2，．．．，Yk）。
图1 一个简单的贝叶斯网络
3 贝叶斯网络的推理
贝叶斯网的推理是在给定的网络结构和已知证据下，计算某一事件发生的概率。贝叶斯网络推理有两种推理模式，即因果推理（由上向下）和诊断推理（自底向上）。因果是给出一些特征，来预测可能发生的情况；而诊断是指己知发生的事件，去探索发生该事件的可能原因。根据不同的推理目标，贝叶斯网推理有四种推理任务: 信度计算与更新(Belief Updating)，最大后验假设(Most Aposterior Hypothesis)，最可能解释(Most Probable Explanation)，期望有利度最大(Maximize the Expected Utility of Problem)。
贝叶斯网的推理方法可分为两类：一类称为精确推理，即精确地计算假设变量的后验概率。另一类称为近似推理，即在不影响推理正确性的前提下，通过适当降低推理精度来达到提高计算效率的目的。精确推理一般用于结构简单的贝叶斯网推理。对于结点数量大、结构复杂的贝叶斯网，精确推理的复杂性会很高，因此常采用近似推理。
精确推理完全按着概率基本公式对查询给以回答，当前的一些精确算法是有效的，能够解决现实中的大部分问题，然而受知识的认知程度所限，精确推理算法中还面临着很多问题需要解决，其中网络的拓扑结构是影响推理复杂性的主要原因。比较典型的精确推理算法有：基于Poly Tree Propagation的算法，基于Clique Tree Propagation的算法，Graph Reduction方法，基于组合优化问题的求解方法（SPI）。
理论上，精确推理能够满足任何推理任务，然而随着网络规模的扩张，精确推理的时间是难以预测的。同时，网络拓扑结构的一个微小变动可能使相对简单的问题变得相当复杂，所以研究近似的推理算法成为一个相当活跃的领域，然而就算法复杂性而言，精确推理和近似推理都是NP问题，但近似推理算法确实可以解决一些精确推理无法解决的问题。近似推理方法在运行时间和推理精度之间采取了一些折中，力求在较短的时间内给出一个满足精度的解。近似推理算法主要有：随机仿真法（Stochastic Sampling），基于搜索的近似算法（Search-based），模型简化方法（Model Simplification）和循环信度传递方法（Loopy Propagation）。
3 一个贝叶斯网络推理的实例
图2是对心脏病或心口痛患者建模的贝叶斯网络。假设图中每个变量都是两个值。心脏病结点（HD）的父结点为影响该疾病的危险因素，有锻炼（E）和饮食（D）等。心脏病结点（HD）的子结点对应该疾病的症状，如胸痛（CP）和高血压（BP）等。而心口痛（h）可能源于不健康的饮食，同时又可能导致胸痛。
图2 发现心脏病和心口痛病人的贝叶斯网络
根据图2，讨论不同情况下，如何诊断一个人是否患有心脏病。
（1）没有先验信息
可通过计算P(HD=Yes)来判断一个人是否患心脏病。设α∈{Yes，No}表示锻炼情况的两个值，β∈{健康，不健康}表示饮食的两个值。
即此人得心脏病的可能性为49%。而P(HD=No)=1-P(HD=Yes)=0.51。
（2）患高血压的情况下
如果一个人有高血压，可计算P(HD=Yes|BP=高)来诊断他是否患心脏病。首先，应先计算P(BP=高)。
P(BP=高)=■P(BP=高|HD=γ)P(HD=γ)=0.85×0.49＋0.2×0.51=0.5185
其中，γ∈{Yes，No}。所以，此人患心脏病的概率为：
因此，当他患有高血压时，患心脏病的概率为80.33%。相应地，P(HD=No|BP=|高) 1－0.8033＝0.1967。
（3）患高血压、饮食健康、经常锻炼身体的情况下
此人患心脏病的概率为：
即在此情况下，他患心脏病的概率为58.62%。
4 结束语
贝叶斯网络是人工智能中不确定知识表示和推理的有力工具，而贝叶斯网络的推理和贝叶斯网络的学习、贝叶斯网络的应用都是贝叶斯网络当前研究的热点。本文给出了贝叶斯网络的定义，并结合实例，介绍了贝叶斯网络推理的方法和过程。
参考文献:
[1]Pear J．Probalilistic reasoning in intelligent systems：Networks of plausible inference．San Mateo：Morgan Kaufmann Publishers，1988．
[2]Nils J.Nilsson(美).人工智能[M].郑扣根,庄越挺,译.北京:机械工业出版社,2005:197-224.
[3]Pang-Ning Tan Michael Steinbach Vipin Kumar(美),范明，范宏建，译.数据挖掘导论[M]．北京：人民邮电出版社，2006:139—150．
[4]刘启元,张聪,沈一栋.信度网推理-方法和问题[J].计算机科学,2001,28(1):74-77.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：贝叶斯网络；贝叶斯网络推理；概率推理
中图分类号：TP18 文献标识码：A文章编号：1009-3044(2007)15-30834-02
Research and Analysis of Bayesian Networks Inference
HUANG Jian-ming1，FANG Jiao-li1，ZHAO Bo2
(1.Computer Center,Kunming University of Science and Technology，Kunming 650093,China；2.Yunnan Nationalities University，Kunming 650031,China)
Abstract：Bayesian networks is a powerful tool to uncertain knowledge representation and reasoning in Artificial Intelligence。This thesis gives a introduction to the concept of Bayesian networks，and gives one example，the method and process is presented to Bayesian networks inference。
Key words：Bayesian ntworks；Bayesian networks inference；Probability inference
1 引言
贝叶斯网络是一种有向无环图（DAG），由Pearl于1988年提出的一种基于概率论和图论的不确定知识表示和推理模型。它具有坚实的理论基础，知识结构的自然表达方式，灵活的推理能力，方便的决策机制。随着研究的逐渐成熟，贝叶斯网络已被广泛应用在医疗诊断、数据挖掘、模式识别、决策支持等领域。目前贝叶斯网络的研究热点主要集中在结构学习、推理和应用三个方面。
2 贝叶斯网络
贝叶斯网是每个结点都带有一张概率表的有向无环图（DAG），在贝叶斯网中，结点表示问题域中的随机变量，弧表示这些变量之间的条件依赖关系。每一个结点都包含一张概率表，把各结点和它的直接父结点关联起来。
定义：贝叶斯网络是一个有向无环图，它可以表示为一个三元组（N,E,P）。N是一组结点的集合，N={x1,x2,…,xn}，每一个结点代表一个变量(属性)。Ｅ是一组有向边的集合，E={
定理：一个贝叶斯网络表示的联合概率函数p=(x1,x2,…,xn)定义为：（假设贝叶斯网有n个结点）p=(x1,x2,…,xn)=■p(xi|πi)，其中πi为xi的父亲结点的集合。P=(x1,x2,…,xn)表示事件x1,x2,…,xn同时发生的概率。
图1是一个简单的贝叶斯网，表示下雪、堵车、摔交、迟到、骨折之间的关系。它表示的联合概率函数为：
p(a,b,c,d,e)=p(a)p(b|a)p(c|a)p(d|b,c)p(e|c)
贝叶斯网络中的一个结点，如果它的父结点已知，则它条件独立于它的所有非后代结点。图1中，给定C，则E条件独立于A，B，D。
除了条件独立性外，每个结点还关联一个概率表。
（1）如果结点X没有父结点，则表中只包含先验概率P（X）。
（2）如果结点X只有一个父结点Y，则表中包含条件概率P（X｜Y）。
（3）如果结点X有多个父结点{Y1，Y2，．．．，Yk}，则表中包含条件概率P（X｜Y1，Y2，．．．，Yk）。
图1 一个简单的贝叶斯网络
3 贝叶斯网络的推理
贝叶斯网的推理是在给定的网络结构和已知证据下，计算某一事件发生的概率。贝叶斯网络推理有两种推理模式，即因果推理（由上向下）和诊断推理（自底向上）。因果是给出一些特征，来预测可能发生的情况；而诊断是指己知发生的事件，去探索发生该事件的可能原因。根据不同的推理目标，贝叶斯网推理有四种推理任务: 信度计算与更新(Belief Updating)，最大后验假设(Most Aposterior Hypothesis)，最可能解释(Most Probable Explanation)，期望有利度最大(Maximize the Expected Utility of Problem)。
贝叶斯网的推理方法可分为两类：一类称为精确推理，即精确地计算假设变量的后验概率。另一类称为近似推理，即在不影响推理正确性的前提下，通过适当降低推理精度来达到提高计算效率的目的。精确推理一般用于结构简单的贝叶斯网推理。对于结点数量大、结构复杂的贝叶斯网，精确推理的复杂性会很高，因此常采用近似推理。
精确推理完全按着概率基本公式对查询给以回答，当前的一些精确算法是有效的，能够解决现实中的大部分问题，然而受知识的认知程度所限，精确推理算法中还面临着很多问题需要解决，其中网络的拓扑结构是影响推理复杂性的主要原因。比较典型的精确推理算法有：基于Poly Tree Propagation的算法，基于Clique Tree Propagation的算法，Graph Reduction方法，基于组合优化问题的求解方法（SPI）。
理论上，精确推理能够满足任何推理任务，然而随着网络规模的扩张，精确推理的时间是难以预测的。同时，网络拓扑结构的一个微小变动可能使相对简单的问题变得相当复杂，所以研究近似的推理算法成为一个相当活跃的领域，然而就算法复杂性而言，精确推理和近似推理都是NP问题，但近似推理算法确实可以解决一些精确推理无法解决的问题。近似推理方法在运行时间和推理精度之间采取了一些折中，力求在较短的时间内给出一个满足精度的解。近似推理算法主要有：随机仿真法（Stochastic Sampling），基于搜索的近似算法（Search-based），模型简化方法（Model Simplification）和循环信度传递方法（Loopy Propagation）。
3 一个贝叶斯网络推理的实例
图2是对心脏病或心口痛患者建模的贝叶斯网络。假设图中每个变量都是两个值。心脏病结点（HD）的父结点为影响该疾病的危险因素，有锻炼（E）和饮食（D）等。心脏病结点（HD）的子结点对应该疾病的症状，如胸痛（CP）和高血压（BP）等。而心口痛（h）可能源于不健康的饮食，同时又可能导致胸痛。
图2 发现心脏病和心口痛病人的贝叶斯网络
根据图2，讨论不同情况下，如何诊断一个人是否患有心脏病。
（1）没有先验信息
可通过计算P(HD=Yes)来判断一个人是否患心脏病。设α∈{Yes，No}表示锻炼情况的两个值，β∈{健康，不健康}表示饮食的两个值。
即此人得心脏病的可能性为49%。而P(HD=No)=1-P(HD=Yes)=0.51。
（2）患高血压的情况下
如果一个人有高血压，可计算P(HD=Yes|BP=高)来诊断他是否患心脏病。首先，应先计算P(BP=高)。
P(BP=高)=■P(BP=高|HD=γ)P(HD=γ)=0.85×0.49＋0.2×0.51=0.5185
其中，γ∈{Yes，No}。所以，此人患心脏病的概率为：
因此，当他患有高血压时，患心脏病的概率为80.33%。相应地，P(HD=No|BP=|高) 1－0.8033＝0.1967。
（3）患高血压、饮食健康、经常锻炼身体的情况下
此人患心脏病的概率为：
即在此情况下，他患心脏病的概率为58.62%。
4 结束语
贝叶斯网络是人工智能中不确定知识表示和推理的有力工具，而贝叶斯网络的推理和贝叶斯网络的学习、贝叶斯网络的应用都是贝叶斯网络当前研究的热点。本文给出了贝叶斯网络的定义，并结合实例，介绍了贝叶斯网络推理的方法和过程。
参考文献:
[1]Pear J．Probalilistic reasoning in intelligent systems：Networks of plausible inference．San Mateo：Morgan Kaufmann Publishers，1988．
[2]Nils J.Nilsson(美).人工智能[M].郑扣根,庄越挺,译.北京:机械工业出版社,2005:197-224.
[3]Pang-Ning Tan Michael Steinbach Vipin Kumar(美),范明，范宏建，译.数据挖掘导论[M]．北京：人民邮电出版社，2006:139—150．
[4]刘启元,张聪,沈一栋.信度网推理-方法和问题[J].计算机科学,2001,28(1):74-77.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。