[p]贝叶斯网络

贝叶斯网络贝叶斯网络（Bayesiannetwork），又称信念网络（beliefnetwork）或是有向无环图模型（directedacyclicgraphicalmodel），是一种概率图型模型，借由有向无环图（directedacyclicgraphs,orDAGs）中得知一组随机变数{}及其n组条件概率分配（conditionalprobabilitydistributions,orCPDs）的性质。举例而言，贝叶斯网络可用来表示疾病和其相关症状间的概率关系；倘若已知某种症状下，贝叶斯网络就可用来计算各种可能罹患疾病之发生概率。一般而言，贝叶斯网络的有向无环图中的节点表示随机变数，它们可以是可观察到的变量，抑或是隐变量、未知参数等。连接两个节点的箭头代表此两个随机变数是具有因果关系或是非条件独立的；而两个节点间若没有箭头相互连接一起的情况就称其随机变数彼此间为条件独立。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因（parents）”，另一个是“果（descendantsorchildren）”，两节点就会产生一个条件概率值。比方说，我们以表示第i个节点，而的“因”以表示，的“果”以表示；图一就是一种典型的贝叶斯网络结构图，依照先前的定义，我们就可以轻易的从图一可以得知：，以及大部分的情况下，贝叶斯网络适用在节点的性质是属于离散型的情况下，且依照此条件概率写出条件概率表（conditionalprobabilitytable,orCPT），此条件概率表的每一行（row）列出所有可能发生的，每一列（column）列出所有可能发生的，且任一行的概率总和必为1。写出条件概率表后就很容易将事情给条理化，且轻易地得知此贝叶斯网络结构图中各节点间之因果关系；但是条件概率表也有其缺点：若是节点是由很多的“因”所造成的“果”，如此条件概率表就会变得在计算上既复杂又使用不便。下图为图一贝叶斯网络中某部分结构图之条件概率表。图一：部分结构图之条件概率表目录[隐藏]1数学定义2马尔可夫毯（Markovblanket）3举例说明4求解方法o4.1精确推理o4.2随机推理（蒙特卡洛方法）4.2.11.结构已知，观测值完整：4.2.22.结构已知，观测值不完整（有遗漏数据）：5补充例子（枚举推理法）6贝叶斯网络的应用层面7参考文献8外部链接数学定义[编辑]令G=(I,E)表示一个有向无环图（DAG），其中I代表图形中所有的节点的集合，而E代表有向连接线段的集合，且令X=(Xi)i∈I为其有向无环图中的某一节点i所代表之随机变数，若节点X的联合概率分配可以表示成：则称X为相对于一有向无环图G的贝叶斯网络，其中表示节点i之“因”。对任意的随机变数，其联合分配可由各自的局部条件概率分配相乘而得出：依照上式，我们可以将一贝叶斯网络的联合概率分配写成：（对每个相对于Xi的“因”变数Xj而言）上面两个表示式之差别在于条件概率的部分，在贝叶斯网络中，若已知其“因”变数下，某些节点会与其“因”变数条件独立，只有与“因”变数有关的节点才会有条件概率的存在。如果联合分配的相依数目很稀少时，使用贝氏函数的方法可以节省相当大的存储器容量。举例而言，若想将10个变数其值皆为0或1存储成一条件概率表型式，一个直观的想法可知我们总共必须要计算个值；但若这10个变数中无任何变数之相关“因”变数是超过三个以上的话，则贝叶斯网络的条件概率表最多只需计算个值即可！另一个贝式网络优点在于：对人类而言，它更能轻易地得知各变数间是否条件独立或相依与其局部分配（localdistribution）的型态来求得所有随机变数之联合分配。马尔可夫毯（Markovblanket）[编辑]定义一个节点之马尔可夫毯为此节点的因节点、果节点与果节点的因节点所成之集合。一旦给定其马尔可夫毯的值后，若网络内之任一节点X皆会与其他的节点条件独立的话，就称X为相对于一有向无环图G的贝叶斯网络。举例说明[编辑]假设有两个服务器，会发送数据包到用户端（以U表示之），但是第二个服务器的数据包发送成功率会与第一个服务器发送成功与否有关，因此此贝叶斯网络的结构图可以表示成如图二的型式。就每个数据包发送而言，只有两种可能值：T（成功）或F（失败）。则此贝叶斯网络之联合概率分配可以表示成：图二：简单的贝叶斯网络例子此模型亦可回答如：“假设已知用户端成功接受到数据包，求第一服务器成功发送数据包的概率?”诸如此类的问题，而此类型问题皆可用条件概率的方法来算出其所求之发生概率：。求解方法[编辑]以上例子是一个很简单的贝叶斯网络模型，但是如果当模型很复杂时，这时使用枚举式的方法来求解概率就会变得非常复杂且难以计算，因此必须使用其他的替代方法。一般来说，贝氏概率有以下几种求法：精确推理[编辑]枚举推理法（如上述例子）变数消元算法（variableelimination）随机推理（蒙特卡洛方法）[编辑]直接取样算法拒绝取样算法概似加权算法马尔可夫链蒙特卡洛算法（MarkovchainMonteCarloalgorithm）在此，以马尔可夫链蒙特卡洛算法为例，又马尔可夫链蒙特卡洛算法的类型很多，故在这里只说明其中一种Gibbssampling的操作步骤：首先将已给定数值的变数固定，然后将未给定数值的其他变数随意给定一个初始值，接着进入以下迭代步骤：（1）随意挑选其中一个未给定数值的变数（2）从条件分配抽样出新的的值，接着重新计算当迭代退出后，删除前面若干笔尚未稳定的数值，就可以求出的近似条件概率分配。马尔可夫链蒙特卡洛算法的优点是在计算很大的网络时效率很好，但缺点是所抽取出的样本并不具独立性。当贝叶斯网络上的结构跟参数皆已知时，我们可以通过以上方法来求得特定情况的概率，不过，如果当网络的结构或参数未知时，我们必须借由所观测到的数据去推估网络的结构或参数，一般而言，推估网络的结构会比推估节点上的参数来的困难。依照对贝叶斯网络结构的了解和观测值的完整与否，我们可以分成下列四种情形：结构观测值方法已知完整最大似然估计法（MLE）已知部分EM算法GreedyHill-climbingmethod未知完整搜索整个模型空间未知部分结构算法EM算法Boundcontraction以下就结构已知的部分，作进一步的说明。1.结构已知，观测值完整：[编辑]此时我们可以用最大似然估计法（MLE）来求得参数。其对数概似函数为其中代表的因变数，代表第个观测值，N代表观测值数据的总数。以图二当例子，我们可以求出节点U的最大似然估计式为由上式就可以借由观测值来估计出节点U的条件分配。如果当模型很复杂时，这时可能就要利用数值分析或其它最优化技巧来求出参数。2.结构已知，观测值不完整（有遗漏数据）：[编辑]如果有些节点观测不到的话，可以使用EM算法（Expectation-Maximizationalgorithm）来决定出参数的区域最佳概似估计式。而EM算法的的主要精神在于如果所有节点的值都已知下，在M阶段就会很简单，如同最大似然估计法。而EM算法的步骤如下：（1）首先给定欲估计的参数一个起始值，然后利用此起始值和其他的观测值，求出其他未观测到节点的条件期望值，接着将所估计出的值视为观测值，将此完整的观测值带入此模型的最大似然估计式中，如下所示（以图二为例）：其中代表在目前的估计参数下，事件x的条件概率期望值为（2）最大化此最大似然估计式，求出此参数之最有可能值，如此重复步骤（1）与（2），直到参数收敛为止，即可得到最佳的参数估计值。补充例子（枚举推理法）[编辑]让我们考虑一个应用在医药上的概率推论例子，在此病人会被诊断出是否有呼吸困难的症状。表一代表一个我们所观测到的数据集合，包含10笔观测值，S代表的是吸烟与否（Smoker），C代表是否为罹癌者（Cancer），B代表是否罹患支气管炎（bronchitis），D代表是否有呼吸困难及咳嗽（dyspneaandasthma）的症状。‘1’和‘0’分别代表‘是’和‘否’。此医药网络结构显示于图三。表二代表的是整个网络的经验联合概率分配，是由所收集到的数据所建构而成，利用此表可建构出节点的联合概率分配。见图四。此贝氏公式可利用节点的边际概率和联合概率去计算节点的条件概率，待会会应用在创建条件概率表格（ConditionalprobabilityTable;CPT）上。见图五。贝叶斯网络的联合概率可由下列式子计算：其值见表三。使用整个网络经验联合概率分配所计算出来的值会与使用CPT所计算出来的值不同，其差异可由表二和表三得知。其中差异不只是值的不同，也出现了新事件的概率（原本所没观察到的事件）。创建在观测数据上的概率推论算法：1.数据集合，其中（下标代表第几个观测值，上标代表第几个变数），且一共有n个观测值。每一个观测值包含个变数，第j个变数有状态。2.此贝叶斯网络的结构G代表N个前代（predecessors）节点集合，也就是对第j个节点，为其亲代节点的集合,j=1,2,…,N3.示例点（instantiatednode)为节点在已知状态，即在此状态的概率为1。如果示例点为空集合，将使用古典概率推论使用表一的观测值和图一的贝叶斯网络结构，并且已知示例点（instantiatednode）为，也就是病人为非吸烟者和罹癌者：问题：1.病人患有支气管炎的概率2.病人会有呼吸困难的概率解答：1.故为0.22.贝叶斯网络的应用层面[编辑]贝叶斯网络目前应用在模拟计算生物学（computationalbiology）与生物信息学（bioinformatics）基因调控网络（generegulatorynetworks）、蛋白质结构（proteinstructure）、基因表达分析（geneexpressionanalysis）、医学（medicine）、文件分类（documentclassification）、信息检索（informationretrieval）、决策支持系统（decisionsupportsystems）、工程学（engineering）、游戏与法律上（gamingandlaw）、数据结合（datafusion）、图像处理（imageprocessing）等。