3.2.3 贝叶斯网络的结构学习

贝叶斯网络的结构学习，就是从训练样本数据中学习出对应的有向无环图（DAG）结构，如图3.4所示。通常建立DAG的方式有两种，基于专家知识的构建和基于数据学习的构建。

由专家知识构建DAG，类似于基于规则的方法。通过咨询相关领域的专家，利用打分、投票以及结合实际情况的方式，确定节点之间是否存在因果联系，从而构建出最符合实际情况的DAG。然而，基于专家知识构建DAG的方式是耗时耗力的，而且当贝叶斯网络中节点数很多，如成百上千时，通过打分来确定贝叶斯网络结构会带来很大的麻烦，在大规模系统的贝叶斯网络应用中，仅仅利用专家知识构建合适的DAG结构是不太现实的。

在贝叶斯网络应用中，每个节点的状态信息会保存在历史数据中，而通过这些历史数据（训练数据）学习DAG结构则被称为结构学习。相比于专家知识的方法，基于数据学习的方法更省资源且更高效，学习得到的结构也更贴近于实际应用，这也使得基于数据学习的方法更适用于构建贝叶斯网络。由于贝叶斯网络结构空间的大小会随着节点的数目以及节点的状态数呈现指数级别增长，使得结构学习成为一个NP问题[1]。如何降低结构学习中的计算和搜索的复杂度问题，成为研究贝叶斯网络的重点和难点之一[1]。

很多实际应用中，可以将数据学习和专家知识相结合，从而形成混合型结构学习方法。Flores[2]首先通过相应的医疗专家对诊断心脏的训练数据进行筛选，从253个相关诱因中筛选出28个最主要的因素，然后再采用数据学习方法学习出相应的贝叶斯网络结构。Masegosa等[3]提出在利用训练数据学习的过程中，将专家知识融入进去，对不合理及不符合实际的有向边进行删除，从而确保在数据学习过程中所学习到的结构是合理且合法的。通过结合数据学习方法和专家知识，一方面可以在数据处理方面移除与所需构建的模型不太相关的一些变量，从而降低学习的复杂度；另一方面当训练数据量不足或存在很多噪声时，所学习的贝叶斯网络结构可能与实际相差巨大，通过专家对所学习的结构进行修正，能够确保所构建的贝叶斯网络结构是符合实际应用的。

结构学习的目的是通过对样本数据集的分析，从中发现节点与节点之间的依赖关系，从而构建出与样本集最为吻合的网络结构，这也是学习和应用贝叶斯网络的基础和核心。根据训练数据是否存在缺失，结构学习也分为完整数据结构学习以及缺失数据结构学习，本章主要介绍完整训练集下的贝叶斯网络结构学习问题。

对于一组随机变量V={V₁，V₂，…，V_n}及关于这些变量的训练数据集D={D（1），D（2），…，D（m）}，其中n为变量数，m为样本数。结构学习的目的是输出相应的有向无环图结构G。当变量很少时（n=1，2），可以很容易地确定出结构图。当节点增多时，相应的有向无环结构图也会呈指数增长。Robinson［4］证明DAG的数目g（n）与节点数n之间满足下面的函数：

显然，g(5)=29281，g(10)=4.2×1018，如此巨大的数量，简单地通过人工构建DAG结构是无法完成的。经过研究者长期的研究，结构学习的算法也已经不断地演化出不同的类型。然而，从本质上这些方法可以分为两大类：即基于约束的方法和基于搜索评分的方法。

1. 基于约束的方法

基于约束的贝叶斯网络结构学习（Constrain-Based Bayesian Network Structure Learning）方法是通过统计独立性测试来学习得到节点间的独立性和相关性，并根据独立性或相关性构建出相应的有向无环图结构。为了获得节点间的独立性关系X╨Y|Z，基于约束的方法通常采用置信区间（Confidence Interval，CI）来进行独立性测试。在离散训练集的结构学习中通常采用G检验或χ2检验，而对于连续训练集的结构学习，通常采用Fisher提出的Z检验。这些检验方式都要统计训练数据D中X、Y和Z的状态数，并做出零假设H₀：X╨Y|Z，与之对应的备择假设，即X和Y不被Z有向分离。可以通过计算频率的方式计算P（D|H₀），然后判断是否超过阈值，从而判定是否接受假设H₀。

基于约束的贝叶斯网络结构学习方法实现起来相对简单，通过统计来判断节点之间是否独立或相关，然后再对空图添加边，或者在完全图中删除边，从而建立与数据对应的有向无环图结构。这种方法求解效率高，能够适用于规模较大的网络结构学习，但会有精度较低的现象出现，一旦数据不足或存在噪声时，结果将会与实际偏差较大。

2. 基于搜索评分的方法

（1）评分函数。基于搜索评分的贝叶斯网络结构学习（Search-and-Score-Based Bayesian Network Structure Learning）方法是将贝叶斯网络结构学习问题看成是优化问题，通过给定结构的评分函数，利用搜索算法去寻找评分最优的网络结构。基于搜索评分的结构学习数学模型可以表示为

其中，f为结构评分函数；Φ为结构空间（即可能的结构）；G=C表示结构G满足约束条件C。在搜索评分过程中，其约束条件C要求搜索到的结构满足结构图中无环。这样，最优结构G∗可以表示为

在基于搜索评分的结构学习中，给定训练数据D及一个可能的结构G，考虑如何去计算其评分函数f（G，D）。很显然，评分函数需要对不满足数据及有向无环图特性的结构进行惩罚（Penalize），并且当这些结构满足数据的分布时，应该选择更简单的图模型。如果评分函数能够满足某些特性，如一致性，则其评分效果更佳。根据这些因素，研究者们提出的评分函数主要可以分为两类：基于贝叶斯的评分与基于信息论的评分，以下将分别介绍基于这两种方法的评分函数。

1）基于贝叶斯的评分函数。基于贝叶斯的评分函数，可以将式（3.14）看作一个最大后验概率（MAP）问题

其中，P（G|D）为给定D的条件下结构G的后验概率。假定G的先验概率为P（G），根据贝叶斯公式可知

由于P（D）与G是无关的，故有P（G|D）∝P（D|G）P（G），两边取对数，得

假设模型结构G的参数集为Θ_G，则可得

其中，P（D|G，Θ_G）通常被称为模型关于数据的似然函数L（G，Θ_G|D）。在离散数据的结构学习中，通常假设模型参数的先验分布P（Θ_G| G）服从参数为α_ijk的狄利克雷（Dirichlet）分布，即

亦可写成如下的精确等式：

其中，Γ为Gamma函数（伽马函数）；r_i为节点V_i的状态数；θ_ijk为节点V_i取k状态时其父节点处于j状态的概率。所谓父节点处于j状态，系指对节点V的父节点（集）的所有状态组合，按词典序（Lexicographical order）排列，并从1开始顺序编号，将父节点（集）状态的第j个组合称为父节点处于j状态。

给定数据集D，可以得出：

其中，m_ijk是数据集D中节点V_i为k状态且父节点状态组合为j的样本数，，且。

对式（3.20）两边取对数，并结合式（3.17），可得

称式（3.21）为BD（Bayesian-Dirichlet）评分，当网络结构的先验分布为均匀分布时，logP（G）=0，BD评分则被称为是CH（Cooper-Herskovits）评分。

对于BD评分中的Dirichlet参数α_ijk，一种假设［5］是其服从统一的参数α_ijk=1，这样BD评分转变为一种新的评分——K2评分：

还有一种假设[6]，如果参数满足，BD评分就转变成新的评分——BDeu评分：

2）基于信息论的评分函数。首先，介绍对数似然（Log-Likelihood，LL）评分的定义如下：

对数似然（LL）评分常用于完善网络结构，它不能在学习网络中给出一种有用的、独立假设下的表达方法。对于其产生的过度拟合现象，通常采用两种方法来避免：限制每个网络变量的父节点数，或者在LL评分中使用一些惩罚因子。在使用惩罚因子的方法中，诞生出了贝叶斯信息准则（Bayesian Information Criterion，BIC）评分函数和最小描述长度（Minimum Description Length，MDL）评分函数，下面逐个阐述这两种评分函数。

① 贝叶斯信息准则（BIC）评分函数。该评分准则是由Schwarz［7］在1978年提出，在样本满足独立于同分布假设的前提下，用对数似然度来度量网络结构与观测数据的拟合程度：

其中，n是网络节点的数目；q是节点变量X_i父节点取值组合的数目；r_i是节点变量X_i的取值数目；m_ijk是X_i的父节点取j值；X_i表示取k值时的样本数目；，θ_ijk=m_ijk/m_ij表示似然条件概率，且0≤θ_ijk≤1，。

BIC评分函数相对简单，而且在精准度和复杂度之间选择较为均衡，所以经常被用于实际的结构学习问题中。

② 最小描述长度评分函数（MDL）评分函数。Lam等人［8，9］在1994年提出的算法以最小描述长度（MDL）作为衡量标准，通过搜索与评价来找出正确的网络结构，而不需要指导节点顺序等信息。MDL的评分函数如式（3.26）所示，式中第一项是拟合程度的度量，第二项是模型复杂度的惩罚量。MDL评分函数在观测数据量比较小的时候，惩罚量所占的得分比重较大，导致数据与结构的欠拟合；当观测数据量较大时，惩罚量所占的比重较小，使得数据与结构过拟合。所以，在实际的计算中MDL的计算精确度不高。

式（3.25）考虑了结构的复杂度，认为L（G）可以用对结构进行编码的位数来近似表示，这样评分函数可以表示为

其中，pa（V_i）代表节点V_i的父节点集。

在定义了对结构好坏进行评价的评分函数后，结构学习问题就可以转化成在所有可能的结构中寻找最高评价值的搜索最优问题。然而，根据式（3.12）可知，结构空间的大小会随着节点数而呈现出指数级别增加的。

Chickering等［10］也证明了学习贝叶斯网络结构是NP难题，因此通常采用启发式或元启发式的搜索方法来搜寻最优结构，例如K₂算法、爬山算法，以及基于进化计算的方法等。

（2）结构学习算法。

① K₂算法。K₂算法是由Cooper和Herskovits提出的一种基于贪婪搜索的结构学习算法[11]。在K₂算法中，采用CH评分[2]来衡量结构的优劣性，并利用节点顺序ρ以及正整数u来限制搜索空间的大小（见算法3.1）。

K₂算法从一个空图出发，按照节点顺序ρ逐个考察节点，通过比较添加某个节点后其CH（Cooper-Herskovits）评分是否增大来“贪婪”地添加其为父节点。正整数u则是用来限制父节点的个数，即限制|pa（V_i）|<u。Cooper将其测试于经典的ALARM网中，通过给定一个网络拓扑序并限制父节点个数为5，选择样本集个数为10000，实验发现结构与ALARM网相差不大。然而，在K₂算法中，最关键的问题在于选择合适的节点顺序ρ，不同的节点顺序会对最终学习到的结构影响很大，这也是限制K₂算法广泛应用的原因之一。针对节点顺序问题，研究者们提出了不同的解决方法，如通过遗传算法学习最优节点顺序［12］以及利用持续集成（CI）测试来学习节点顺序［13］等。

② 爬山搜索算法。爬山（Hill Climbing）算法通过在搜索过程中不断地进行加边、减边以及删除边的局部操作，并根据评分是否发生变化来确定是否选择该操作。爬山算法中可以采用任何的评分函数对结构进行评分，并通过贪婪选择来判断是否对模型结构进行更新。

如算法3.2所示，爬山算法从随机产生的结构图出发，选择能使结构向着优化发展的操作算子。然而，由于爬山算法的操作算子比较随机，会使得搜索性能较低，为了提高搜索的效率，通常对每个节点选择其父节点禁忌表来降低搜索的空间。同时，由于爬山算法选择的都是使结构评分得到提升的局部最优操作算子，这样就会容易让算法陷入局部最优，因此通常采用多组实验来选择其中评分最高的结构图。

3. 混合约束和搜索评分的结构学习方法

由于基于约束的方法对于数据的要求较高，要求训练数据是无噪声且真实的，而且训练数据量需要足够大，才能获得满意的独立性测试结构。而基于搜索评分的方法复杂度更高，尤其是当节点较多时，会使得搜索空间巨大，从而导致从庞大的搜索空间中搜索最优结构耗时巨大。

为了克服两类方法的缺陷，研究者们提出将这两类思想进行融合，即利用混合的方法对贝叶斯网络进行结构学习。首先，通过独立性测试来降低搜索空间的大小，然后再利用搜索评分的方法来寻找最优的网络结构。典型的有Tsamardinos等人提出的MMHC（Max-Min Hill Climbing）算法（见算法3.3）。

MMHC算法［14］将局部学习、CI测试以及搜索评分方法进行融合，通过采用独立性测试来学习出结构的框架，然后采用搜索评分的方式来确定网络中的边以及边的方向。MMHC算法首先通过MMPC（Max-Min Parents and Children）算法（见算法3.4）来获得每个节点V_i的父子节点集pc（V_i），从而构建出网络结构的框架，然后根据K₂搜索策略对已经得到的网络结构的框架进行搜索评分，以得到最优网络结构。MMPC算法采用CI测试来判断节点对之间的条件独立性；采用max-min的策略启发式，选择使得相对于以其父子节点集pc（V_i）为条件时的最小依赖最大的节点。如果在pc（V_i）中存在节点X，使得X╨V_i|Z，Z⊆pc（V_i）\{X}成立，则MMPC将X从pc（V_i）中删除。当MMPC学习到每个节点的父子节点集后，MMHC算法同样采用添加边和删除边的操作，需要指出的是，在MMHC添加边操作时仅仅考虑X∈pc（V_i），这也限制了搜索的空间，降低了搜索的复杂度。

基于混合约束与搜索评分的结构学习方法能够有效地将两者的优势相结合，能够很好地解决节点数较多的网络结构学习问题。目前，研究者们也在不断地尝试采用不同的混合方式来对贝叶斯网络进行结构学习。