贝叶斯网络

一个简单的贝氏网路。雨水影响洒水器是否有动作，且雨水及洒水器二者均可影响草是否湿润.

贝氏网路（Bayesian network），又称信念网络（belief network）或是有向无环图模型（directed acyclic graphical model），是一种机率图型模型，借由有向无环图（directed acyclic graphs, or DAGs）中得知一组随机变数$\left\{X_{1},X_{2},...,X_{n}\right\}$及其n组条件机率分配（conditional probability distributions, or CPDs）的性质。举例而言，贝氏网路可用来表示疾病和其相关症状间的机率关系；倘若已知某种症状下，贝氏网路就可用来计算各种可能罹患疾病之发生机率。

一般而言，贝氏网路的有向无环图中的节点表示随机变数，它们可以是可观察到的变量，抑或是潜在变量、未知参数等。连接两个节点的箭头代表此两个随机变数是具有因果关系或是非条件独立的；而两个节点间若没有箭头相互连接一起的情况就称其随机变数彼此间为条件独立。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因（parents）”，另一个是“果（descendants or children）”，两节点就会产生一个条件机率值。比方说，我们以$X_{i}$表示第i个节点，而$X_{i}$的“因”以$P_{i}$表示，$X_{i}$的“果”以$C_{i}$表示；图一就是一种典型的贝氏网路结构图，依照先前的定义，我们就可以轻易的从图一可以得知：

$P_{2}=\left\{X_{4},X_{5}\right\},C_{2}=\emptyset ,P_{4}=\emptyset ,C_{4}=\left\{X_{2},X_{5}\right\},P_{5}=\left\{X_{4}\right\}$，以及$C_{5}=\left\{X_{2}\right\}$

大部分的情况下，贝氏网路适用在节点的性质是属于离散型的情况下，且依照$P(X_{i}|P_{i})$此条件机率写出条件机率表，此条件机率表的每一行（row）列出所有可能发生的$P_{i}$，每一列（column）列出所有可能发生的$X_{i}$，且任一行的机率总和必为1。写出条件机率表后就很容易将事情给条理化，且轻易地得知此贝氏网路结构图中各节点间之因果关系；但是条件机率表也有其缺点：若是节点$X_{i}$是由很多的“因”所造成的“果”，如此条件机率表就会变得在计算上既复杂又使用不便。下图为图一贝氏网路中某部分结构图之条件机率表。

图一：部分结构图之条件机率表

数学定义

令 G = (I,E) 表示一个有向无环图（DAG），其中 I 代表图中所有的节点的集合，而 E 代表有向连接线段的集合，且令 X = (X_i)_i∈I 为其有向无环图中的某一节点 i 所代表之随机变数，若节点 X 的联合机率分配可以表示成：

$p(x)=\prod _{i\in I}p{\big (}x_{i}\,{\big |}\,x_{\operatorname {pa} (i)}{\big )}$

则称 X 为相对于一有向无环图 G 的贝氏网路，其中$pa(i)$表示节点 i 之“因”。

对任意的随机变数，其联合分配可由各自的局部条件机率分配相乘而得出：

$\mathrm {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{i=1}^{n}\mathrm {P} (X_{i}=x_{i}\mid X_{i+1}=x_{i+1},\ldots ,X_{n}=x_{n})$

依照上式，我们可以将一贝氏网路的联合机率分配写成：

$\mathrm {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{i=1}^{n}\mathrm {P} (X_{i}=x_{i}\mid X_{j}=x_{j})$（对每个相对于X_i的“因”变数 X_j 而言)

上面两个表示式之差别在于条件机率的部分，在贝氏网路中，若已知其“因”变数下，某些节点会与其“因”变数条件独立，只有与“因”变数有关的节点才会有条件机率的存在。

如果联合分配的相依数目很稀少时，使用贝氏函数的方法可以节省相当大的记忆体容量。举例而言，若想将10个变数其值皆为0或1储存成一条件机率表型式，一个直观的想法可知我们总共必须要计算$2^{10}=1024$个值；但若这10个变数中无任何变数之相关“因”变数是超过三个以上的话，则贝氏网路的条件机率表最多只需计算$10*2^{3}=80$个值即可。另一个贝式网路优点在于：对人类而言，它更能轻易地得知各变数间是否条件独立或相依与其局部分配（local distribution）的型态来求得所有随机变数之联合分配。

马可夫毯（Markov blanket）

定义一个节点之马可夫毯为此节点的因节点、果节点与果节点的因节点所成之集合。一旦给定其马可夫毯的值后，若网路内之任一节点X皆会与其他的节点条件独立的话，就称X为相对于一有向无环图G的贝氏网路。

举例说明

假设有两个伺服器$(S_{1},S_{2})$，会传送封包到使用者端（以U表示之），但是第二个伺服器的封包传送成功率会与第一个伺服器传送成功与否有关，因此此贝氏网路的结构图可以表示成如图二的型式。就每个封包传送而言，只有两种可能值：T（成功）或 F（失败）。则此贝氏网路之联合机率分配可以表示成：

$P(U,S_{1},S_{2})=P(U|S_{1},S_{2})\times P(S_{2}|S_{1})\times P(S_{1})$

图二：简单的贝氏网路例子

此模型亦可回答如：“假设已知使用者端成功接受到封包，求第一伺服器成功发送封包的机率?”诸如此类的问题，而此类型问题皆可用条件机率的方法来算出其所求之发生机率：

$\mathrm {P} ({\mathit {S_{1}}}=T\mid {\mathit {U}}=T)={\frac {\mathrm {P} ({\mathit {S_{1}}}=T,{\mathit {U}}=T)}{\mathrm {P} ({\mathit {U}}=T)}}$

$={\frac {\sum _{{\mathit {S_{2}}}\in \{T,F\}}\mathrm {P} ({\mathit {S_{1}}}=T,{\mathit {S_{2}}},{\mathit {U}}=T)}{\sum _{{\mathit {S_{1}}},{\mathit {S_{2}}}\in \{T,F\}}\mathrm {P} ({\mathit {U}}=T,{\mathit {S_{1}}},{\mathit {S_{2}}})}}$

$={\frac {(0.4\times 0.3\times 1)_{U=T,S_{1}=T,S_{2}=F}+(0.4\times 0.7\times 1)_{U=T,S_{1}=T,S_{2}=T}}{(0.4\times 0.3\times 1)_{TTF}+(0.4\times 0.7\times 1)_{TTT}+(0.6\times 0.3\times 1)_{FTT}+0_{TFF}}}$

$\approx 68.96\%$。

求解方法

以上例子是一个很简单的贝氏网路模型，但是如果当模型很复杂时，这时使用列举式的方法来求解机率就会变得非常复杂且难以计算，因此必须使用其他的替代方法。一般来说，贝氏机率有以下几种求法：

精确推论

• 列举推理法（如上述例子）
• 变数消元演算法（variable elimination）

随机推论（蒙地卡罗方法）

• 直接取样演算法
• 拒绝取样演算法
• 概似加权演算法
• 马可夫链蒙地卡罗演算法（Markov chain Monte Carlo algorithm）

在此，以马可夫链蒙地卡罗演算法为例，又马可夫链蒙地卡罗演算法的类型很多，故在这里只说明其中一种吉布斯采样的操作步骤： 首先将已给定数值的变数固定，然后将未给定数值的其他变数随意给定一个初始值，接著进入以下迭代步骤：

（1）随意挑选其中一个未给定数值的变数

（2）从条件分配$P(X_{i}|{\text{Markovblanket}}(X_{i}))$抽样出新的$X_{i}$的值，接著重新计算$P(X_{i}|{\text{Markovblanket}}(X_{i}))=\alpha P(X_{i}|{\text{parents}}(X_{i}))\times \prod _{Y_{i}\in {\text{children}}(X_{i})}{\text{parent}}(Y_{i})$

当迭代结束后，删除前面若干笔尚未稳定的数值，就可以求出的近似条件机率分配。马可夫链蒙地卡罗演算法的优点是在计算很大的网路时效率很好，但缺点是所抽取出的样本并不具独立性。

当贝氏网路上的结构跟参数皆已知时，我们可以透过以上方法来求得特定情况的机率，不过，如果当网路的结构或参数未知时，我们必须借由所观测到的资料去推估网路的结构或参数，一般而言，推估网路的结构会比推估节点上的参数来的困难。依照对贝氏网路结构的了解和观测值的完整与否，我们可以分成下列四种情形：

结构	观测值	方法
已知	完整	最大概似估计法（MLE）
已知	部份	EM演算法 Greedy Hill-climbing method
未知	完整	搜寻整个模型空间
未知	部份	结构演算法 EM演算法 Bound contraction

以下就结构已知的部分，作进一步的说明。

1.结构已知，观测值完整：

此时我们可以用最大概似估计法（MLE）来求得参数。其对数概似函数为

$L={\frac {1}{N}}\sum _{i=1}^{n}\sum _{i=1}^{s}\log(P(X_{i}|pa(X_{i}),D_{i}))$

其中$pa(X_{i})$代表$X_{i}$的因变数，$D_{i}$代表第${\mathit {1}}$个观测值，N代表观测值资料的总数。

以图二当例子，我们可以求出节点U的最大概似估计式为

$P(U=u|S_{1}=s_{1},S_{2}=s_{2})={\frac {n(U=u,S_{1}=s_{1},S_{2}=s_{2})}{n(S_{1}=s_{1},S_{2}=s_{2})}}$

由上式就可以借由观测值来估计出节点U的条件分配。如果当模型很复杂时，这时可能就要利用数值分析或其它最佳化技巧来求出参数。

2.结构已知，观测值不完整（有遗漏资料）：

如果有些节点观测不到的话，可以使用EM演算法（Expectation-Maximization algorithm）来决定出参数的区域最佳概似估计式。而EM演算法的主要精神在于如果所有节点的值都已知下，在M阶段就会很简单，如同最大概似估计法。而EM演算法的步骤如下：

（1）首先给定欲估计的参数一个起始值，然后利用此起始值和其他的观测值，求出其他未观测到节点的条件期望值，接著将所估计出的值视为观测值，将此完整的观测值带入此模型的最大概似估计式中，如下所示（以图二为例）：

$P(U=u|S_{1}=s_{1},S_{2}=s_{2})={\frac {EN(U=u,S_{1}=s_{1},S_{2}=s_{2})}{EN(S_{1}=s_{1},S_{2}=s_{2})}}$

其中$EN(x)$代表在目前的估计参数下，事件x的条件机率期望值为

$EN(x)=E\sum _{k}I(x|D(k))=\sum _{k}P(x|D(k))$

（2）最大化此最大概似估计式，求出此参数之最有可能值，如此重复步骤（1）与（2），直到参数收敛为止，即可得到最佳的参数估计值。

补充例子（列举推理法）

让我们考虑一个应用在医药上的机率推论例子，在此病人会被诊断出是否有呼吸困难的症状。表一代表一个我们所观测到的资料集合，包含10笔观测值，S代表的是吸烟与否（Smoker），C代表是否为罹癌者（Cancer），B代表是否罹患支气管炎（bronchitis），D代表是否有呼吸困难及咳嗽（dyspnea and asthma）的症状。‘1’和‘0’分别代表‘是’和‘否’。此医药网路结构显示于图三。

表一

表二代表的是整个网路的经验联合机率分配，是由所收集到的资料所建构而成，利用此表可建构出节点的联合机率分配。见图四。此贝氏公式$P(A|B)={\frac {P(A,B)}{P(B)}}$可利用节点的边际机率和联合机率去计算节点的条件机率，待会会应用在建立条件机率表格（Conditional probability Table; CPT）上。见图五。贝氏网路的联合机率可由下列式子计算：

$P(S,C,B,D)=P(S)\times P(C|S)\times P(B|S,C)\times P(D|B,C)$

其值见表三。

使用整个网路经验联合机率分配所计算出来的值会与使用CPT所计算出来的值不同，其差异可由表二和表三得知。其中差异不只是值的不同，也出现了新事件的机率（原本所没观察到的事件）。

表二

图四

图五

表三

建立在观测资料上的机率推论演算法：

1.资料集合$D=\left\{d_{1},\ldots ,d_{n}\right\}$，其中$d_{i}={x_{i}^{(1)},\ldots ,x_{i}^{(N)}}$（下标代表第几个观测值，上标代表第几个变数），且一共有n个观测值。每一个观测值包含$N(N\geq 2)$个变数${X_{i}^{(1)},\ldots ,X_{i}^{(N)}}$，第j个变数有$A^{(j)}={0,1,\ldots ,\alpha ^{(j)}-1}(\alpha ^{(j)}\geq 2)$状态。

2.此贝氏网路的结构G代表N个前代（predecessors）节点集合$\left\{\Pi ^{(1)},\ldots ,\Pi ^{(N)}\right\}$，也就是对第j个节点，$\Pi ^{(j)}$为其亲代节点的集合, j=1,2,…,N

3.范例点（instantiated node）$\left\{X^{P_{1}}=x^{P_{1}},\ldots ,X^{P_{v}}=x^{P_{v}}\right\}$为节点在已知状态，即在此状态的机率为1。如果范例点为空集合，将使用古典机率推论

使用表一的观测值和图一的贝氏网路结构，并且已知范例点（instantiated node）为$\left\{S=0,C=0\right\}$，也就是病人为非吸烟者和罹癌者：$P\left(S=0\right)=1,P\left(C=0\right)=1$

问题：
1.病人患有支气管炎的机率$P\left(B\right)=?$
2.病人会有呼吸困难的机率$P\left(D\right)=?$

解答：
1. $P\left(B=0|S=0,C=0\right)=0.8$

$P\left(B=1|S=0,C=0\right)=0.2$
故为0.2

2. $P\left(D=0|S=0,C=0\right)$

$=P\left(D=0,B=0|S=0,C=0\right)+P\left(D=0,B=1|S=0,C=0\right)$

$=P\left(D=0|B=0,S=0,C=0\right)\times P\left(B=0|S=0,C=0\right)$

$+P\left(D=0|B=1,S=0,C=0\right)\times P\left(B=1|S=0,C=0\right)$

$P\left(D=1|S=0,C=0\right)$

$=P\left(D=1,B=1|S=0,C=0\right)+P\left(D=1,B=0|S=0,C=0\right)$

$=P\left(D=1|B=0,S=0,C=0\right)\times P\left(B=0|S=0,C=0\right)$

$+P\left(D=1|B=1,S=0,C=0\right)\times P\left(B=1|S=0,C=0\right)$

应用

贝氏网路目前应用在类比计算生物学与生物资讯学基因调控网路、蛋白质结构、基因表达分析、医学、文档分类、资讯检索、决策支援系统、工程学、资料结合、图像处理等。

参考文献

• A. N. Terent' yev and P. I. Bidyuk. METHOD OF PROBABILISTIC INFERENCE FROM LEARNING DATA IN BAYESIAN NETWORKS. Cybernetics and Systems Analysis, 391-396, Vol. 43, No. 3, 2007
• Emilia Mendes and Nile Mosley. Bayesian Network Models for Web Effort Prediction: A Comparative Study. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 723-737, VOL. 34, NO. 6, NOVEMBER/DECEMBER 2008
• Yu. V. Kapitonova, N. M. Mishchenko, O. D. Felizhanko, and N. N. Shchegoleva. USING BAYESIAN NETWORKS FOR MONITORING COMPUTER USERS. Cybernetics and Systems Analysis, 789-799, Vol. 40, No. 6, 2004
• Ben-Gal I., Bayesian Networks, in Ruggeri F., Faltin F. & Kenett R. ,Encyclopedia of Statistics in Quality & Reliability, Wiley & Sons (2007).
• Radu Stefan Niculescu, Tom M. Mitchell and R. Bharat Rao, Journal of Machine Learning Research 7 (2006) 1357–1383
• N. Terent' yev and P. I. Bidyuk. METHOD OF PROBABILISTIC INFERENCE FROM LEARNING DATA IN BAYESIAN NETWORKS. Cybernetics and Systems Analysis, 391-396, Vol. 43, No. 3, 2007
• P. I. Bidyuk, A. N. Terent’ev, and A. S. Gasanov. CONSTRUCTION AND METHODS OF LEARNING OF BAYESIAN NETWORKS. Cybernetics and Systems Analysis, 587-598, Vol. 41, No. 4, 2005

外部链接

• A tutorial on learning with Bayesian Networks
• An Introduction to Bayesian Networks and their Contemporary Applications （页面存档备份，存于互联网档案馆）
• On-line Tutorial on Bayesian nets and probability （页面存档备份，存于互联网档案馆）
• Web-App to create Bayesian nets and run it with a Monte Carlo method
• Continuous Time Bayesian Networks （页面存档备份，存于互联网档案馆）
• Bayesian Networks: Explanation and Analogy
• A live tutorial on learning Bayesian networks （页面存档备份，存于互联网档案馆）
• A hierarchical Bayes Model for handling sample heterogeneity in classification problems （页面存档备份，存于互联网档案馆）, provides a classification model taking into consideration the uncertainty associated with measuring replicate samples.
• Hierarchical Naive Bayes Model for handling sample uncertainty （页面存档备份，存于互联网档案馆）, shows how to perform classification and learning with continuous and discrete variables with replicated measurements.