:::info 前几章假设概率模型的结构是已知的，而本章讨论从数据中学习模型结构的方法。
首先介绍如何在给定数据的情况下计算图形结构的概率，并且通常需要使该概率最大化。由于图形结构可能过大，无法枚举，还讨论了有效搜索该空间的方法。 :::

1. 贝叶斯网络评分 Bayesian Network Scoring

根据网络结构5 结构学习 Structure Learning - 图1对数据进行建模的好坏进行评分。结构学习的最大后验方法包括找到使5 结构学习 Structure Learning - 图2最大化的5 结构学习 Structure Learning - 图3。
基于5 结构学习 Structure Learning - 图4计算贝叶斯得分：
5 结构学习 Structure Learning - 图5
5 结构学习 Structure Learning - 图6，其中5 结构学习 Structure Learning - 图7
贝叶斯评分：5 结构学习 Structure Learning - 图8

image.png image.png 从上图可以看出，在样本数小于5000时，完全不连接的模型的贝叶斯评分比真实模型更高；当样本数较大时，完全不连接的模型甚至比完全连接的模型表现更差，因为有足够的数据来充分证明完全连接的模型的7个独立参数。 表明在数据稀缺的情况下，简单模型的表现优于复杂模型。

2. 有向图搜索 Directed Graph Search

在有向图搜索中，我们需要在有向无环图的空间中找到贝叶斯评分最高的图。但可能的贝叶斯网络结构数目随节点数量指数增长。无法枚举所有的网络结构，必须通过搜索策略。
K2搜索算法：最常见的搜索策略之一。以多项式的时间运行，但不能保证找到全局最优的网络结构。
局部搜索：一般的搜索策略。局部搜索会陷入局部最优。
总体而言，寻找全局最优解是NP-hard。但许多应用并不需要全局最优的网络结构，局部最优也可以接受。

3. 马尔可夫等价类 Markov Equivalence Classes

马尔可夫等价：如果两个网络编码相同的条件独立假设，则它们是马尔可夫等价。
两个图马尔可夫等价，当且仅当 ①具有相同的边（不考虑方向）；②具有相同的immoral v结构。
（immoral v结构：5 结构学习 Structure Learning - 图11且5 结构学习 Structure Learning - 图12和5 结构学习 Structure Learning - 图13未直接相连）
image.png
马尔可夫等价类：包含所有马尔可夫等价的有向无环图的集合。
如果贝叶斯得分与Dirichlet先验一起使用，则对于所有5 结构学习 Structure Learning - 图15，5 结构学习 Structure Learning - 图16均为常数，则这两个马尔可夫等价结构被赋予相同的分数。这种先验称为BDe。
分数等效函数：为同一类中的所有结构分配相同分数的评分函数。

image.png 上图是具有4个节点的部分有向无环图，该图没有马尔可夫等价类。 不能用有向边替换5 结构学习 Structure Learning - 图18和5 结构学习 Structure Learning - 图19之间的无向边，因为会引入新的immoral v结构。

4. 部分有向图搜索 Partially Directed Graph Search

部分有向图：同时包含有向边和无向边。马尔可夫等价类可以表示为部分有向图。
我们可以搜索由部分有向图表示的马尔可夫等价类的空间，而不是搜索有向无环图的空间。
定义图的领域的局部图操作：（并保持无环）

  • 如果5 结构学习 Structure Learning - 图20和5 结构学习 Structure Learning - 图21之间不存在边，添加5 结构学习 Structure Learning - 图22或5 结构学习 Structure Learning - 图23
  • 如果5 结构学习 Structure Learning - 图24或5 结构学习 Structure Learning - 图25，移除5 结构学习 Structure Learning - 图26和5 结构学习 Structure Learning - 图27之间的边
  • 如果5 结构学习 Structure Learning - 图28，反转边的方向得到5 结构学习 Structure Learning - 图29
  • 如果5 结构学习 Structure Learning - 图30，添加5 结构学习 Structure Learning - 图31