Bayesian Network / Belief Network 贝叶斯网

Machine Learning

借助有向无环图来刻画属性之间的依赖关系，用条件概率表描述属性的联合概率分布。
Image Loading

结构

Image Loading
Image Loading
用道德图 moral graph 能看出变量间的独立关系，没有直接相连的边。
Image Loading
生成道德图(无向图)的过程为：

  • 找出有向图中的所有 V 型结构，在 V 型结构的两个父节点之间加上一条无向边。
  • 将所有无向边改为有向边。

学习

在网络结构已知的情况下，贝叶斯网的学习就只是对训练样本计数，估计出每个节点的条件概率表即可。
因此，学习重点是根据训练数据集来找出结构最恰当的贝叶斯网。根据信息论准则，学习的目标是找到一个能以最短编码长度描述训练数据的模型。
Image Loading
Image Loading

  • f(θ)=1f(\theta) = 1，每个参数用1字节描述，Akaike Information Criterion。
    Image Loading
  • f(θ)=12logmf(\theta) = \frac{1}{2} \log m，每个参数用12log\frac{1}{2} \log描述，Bayesian Information Criterion。
    Image Loading
  • 若f(θ)=0f(\theta) = 0，即不计算对网络进行编码的长度，则评分函数退化为负对数似然，学习任务退化为极大似然估计。

从所有可能的网络结构空间搜索最优贝叶斯网结构是一个 NP 难问题。有两种常用的策略能在有限时间内求得近似解：

  • 贪心法。从某个网络开始增增减减，直到评分数值不再降低。
  • 给网络结构施加约束来削减搜索空间。例如必须是树。

推断

最理想是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，可惜这是 NP 难的。
所以现实中，要降低精度要求，在有限时间内求得近似解，贝叶斯网的近似推断常用吉布斯采样 Gibbs sampling。
Image Loading
Image Loading
实质上，吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据E=eE=e一直的子空间中进行随机漫步。每一步仅依赖于前一步的状态，这是一个马尔可夫链，会收敛于一个平稳分布。在 T 很大时，吉布斯采样相当于根据P(Q|E=e)采样，从而保证了7.33收敛于P(Q=q∣E=e)P(Q=q|E=e)。
注意：1.马尔可夫链收敛很慢。2.如果出现极端概率0或1，不保证马尔可夫链存在平稳分布。
Image Loading
Image Loading

Ref

[1] 机器学习 - 周志华
[2] http://www.stat.unm.edu/~ghuerta/stat574/notes-gibbs-metro.pdf