学习贝叶斯网络的结构

到目前为止，我们一直假定贝叶斯网络的结构是已知的，而我们只是试图学习参数。网络的结构表示了一个域的基本因果知识，往往专家甚至新手都很容易提供。然而，在某些情况下，因果模型可能无法得到或者有争议——例如，有的公司一直宣称吸烟不会导致癌症—所以，重要的是理解如何能够从数据中学习贝叶斯网络的结构。现在，结构学习算法才刚刚起步，所以我们仅仅对主要的思想进行一个简要的概述。

最显而易见的方法是搜索一个好的模型。我们可以从不包含任何有向边的模型入手，然后开始为每个节点添加父节点，要符合我们刚刚谈论过的方法中的参数，并且估量结果模型的准确性。此外，我们还可以先对模型的结构有一个初始猜测，然后使用爬山法或者模拟退火搜索进行修正，随着结构的每次变化调整参数。修正方法可以包括反转、添加或者删除弧。在这个过程中我们必须避免引入环，所以很多算法假定变量是有顺序的，而一个节点的父节点必须是在排序中先出现的节点（正如第十四章的构造过程一样）。为了完全的一般性，我们还需要搜索可能的排序。

还有两种可选方法用于判断何时一个合适的结构已经被找到。首先测试隐含于结构中的条件独立性断言是否确实能满足数据。例如，针对餐馆问题的朴素贝叶斯模型就假定了

P(Fri/Sat,Bar|WillWait)=P(Fri/Sat|WillWait)P（Bar|WillWait）

然后我们可以检验数据，在对应的条件频度之间上式成立与否。现在，即使这个结构描述了域的真实因果本质，数据集中的统计波动意味着该公式永远无法得到严格的满足，所以我们需要执行一个合适的统计测试，来看看是否有足够的证据表明独立性假设被破坏了。结果网络的复杂度将取决于测试中使用的阈值——独立性测试越严格，加入的有向边越多，过拟合的风险也就越大。

一种和本章的主旨更一致的方法来自于所提出模型（在概率意义下）对数据的解释程度。不过，我们必须非常注意如何度量解释程度。如果我们只是尝试找到最大似然假设，则我们最终会得到一个全连接网络，这是因为给一个节点添加更多的父节点不会减少似然程度（习题 20.9）。我们被迫以某种方式对模型的复杂度加以惩罚。MAP（或 MDL）方法只是在比较不同的结构之前简单地根据结构的似然度（在参数调整之后）减去惩罚值。贝叶斯方法是在结构和参数之上设置一个联合的先验概率。通常情况下由于有过多的结构而无法求和（是变量数目的超指数量级），所以大部分研究者采用MCMC对结构进行采样。

（无论通过MAP还是贝叶斯方法）惩罚复杂度在最优化结构与网络中条件分布的表示本质之间引入了一个重要的联系。对于表格化表示的分布，一个节点的分布复杂度惩罚随着父节点数目的增加呈指数级增长，但是，对于比如说“噪声或”分布，则只是线性增长。这意味着通过噪声或模型（或其它简洁的参数化模型）进行学习倾向于比通过表格化分布进行学习产生包含更多父节点的结构。