大师兄的贝叶斯网络学习笔记（五十）：贝叶斯网络（二十四）

大师兄的贝叶斯网络学习笔记（四十九）：贝叶斯网络（二十三）
大师兄的贝叶斯网络学习笔记（五十一）：贝叶斯网络（二十五）

八、结构学习

6. 缺值数据结构学习

6.2 SEM算法

设(G,θ)是一个贝叶斯网络，定义(G,θ)的BIC评分如下：

$BIC(G,\theta|D) = logP(D|G,\theta)-\frac{d(G)}{2}\log m$

当θ是最大似然估计θ*时，BIC(G,θ|D)就是模型结构G的BIC评分： $BIC(G|D)=BIC(G,\theta*|D)$ 。
这一节假设数据有缺值，所关心的问题是在缺值数据情况下如何寻找BIC评分最高的贝叶斯网络 $G*,\theta*$ ： $BIC(G*,\theta*|D)\geq BIC(G,\theta|D),\all G,\theta$ 。
设从某初始贝叶斯网络出发，通过一系列优化步骤，SEM得到了贝叶斯网络 $(\overline G,\overline\theta)$ 。
设 $\overline D$ 是基于 $(\overline G,\overline\theta)$ 队数据D进行修补而得到的完整户数。
与参数EM的情况类似，一个贝叶斯网络(G,\theta)的基于数据 $(\overline D)$ 的BIC评分为 $BIC(G,\theta|\overline D) = \sum^m_{i=1}\sum_{x_l}P(X_l|D_l,\overline G,\overline \theta)\log P(D_l,X_l|G,\theta)-\frac{d(G)}(2)\log m$ 。

其中 $X_l是D_l$ 中所有缺值变量的集合。

$BIC(G,\theta|\overline D)$ 也称为(G,\θ)的基于D的期望BIC评分(expected BIC score)，可以记为 $Q(G,\theta|\overline G,\overline\theta)$ 。
可得： $Q(\theta, \theta \mid \bar{\theta}, \bar{\theta}) = \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \frac{m_{ijk}^2}{2} \log \theta_{ijk} - \frac{d(\bar{\theta})}{2} \log m$ 。
其中 $\overline{m}_{ijk} = \sum_{l=1}^m P(X_i = k, \pi_\theta(X_i) = j \mid D_l, \bar{\theta})$ 。
这里 $\pi_G(X_i)$ 是 $X_i$ 在G中的所有父节点的集合， $q_i=|\pi_G(X_i)|$ 。
如果下一步是要优化参数，SEM就规定 $G=\overline G$ ，并计算使 $Q(\overline G,\theta| \overline G,\overline \theta)$ 达到最大的参数值θ'。
因为 $G=\overline G$ ，所以罚项为一常数，有 $\theta_{ijk} = \frac{\overline{m}_{ijk}^g}{\sum_{k=1}^r \overline{m}_{ijk}^g}$ 。
如果下一步要同时优化模型结构和参数，SEM首先构造出所有能够通过对G进行一次加边、减边或转边而得到的候选模型，这些候选模型的集合记为L。
对其中任一候选模型G，SEM用下式优化其参数，即 $\theta_{ijk} = \dfrac{\overline{m}_{ijk}^g}{\displaystyle\sum_{k=1}^r \overline{m}_{ijk}^g}$ 。
接着，求得 $Q(G,\theta |\overline G,\overline \theta)$ 。
最后再找出使 $Q(G,\theta)|\overlineG,\overline\theta$ 达到最大的模型，即 $\langle g', \theta' \rangle = \arg \max \sup Q(g, \theta \mid \bar{g}, \bar{\theta})$ 。
SEM的伪代码如下：
$\documentclass{article}
\usepackage[UTF8]{ctex} % 支持中文，若无需中文可删除此行
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{amsmath, amssymb}

\begin{document}

\begin{algorithm}
\caption{SEM}
\label{alg:sem}
\begin{algorithmic}[1]
\Require{ $X$ —— 一组变量； $\Theta^0$ —— 初始网络结构； $R$ —— 两次结构优化之间的参数优化次数；}
\Ensure{一个贝叶斯网}
\For{ $t = 0$ 到 $\infty$ }
\For{ $r = 0$ 到 $R-1$ }
\State $\Theta^{0,t+1} \gets \arg \sup Q(\Theta^0, \Theta \mid \Theta^{0,t,r})$ \Comment{式(8.53)}
\EndFor
\State $L \gets$ 所有对 $\Theta^0$ 做一次加边、减边或转边而得到的模型结构；
\State $(\Theta^{0,t+1}, \Theta^{0,t+1,0}) \gets \arg \max \sup Q(\Theta, \Theta \mid \Theta^{0,t,R})$ \Comment{式(8.54), 式(8.55)}
\If{ $\mathrm{BIC}(\Theta^{0,t+1}, \Theta^{0,t+1,0} \mid \Theta) \le \mathrm{BIC}(\Theta^{0,t,R} \mid \Theta)$ }
\State \Return $(\Theta^{0,t,R})$
\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}

\end{document}$

它先进行R次参数优化（2-3行）

接着同时优化模型结构及参数（5-6行）。

如果模型家参数优化得到评分更高的模型，SEM就重复前面的运算，否则就停止并返回找到的BIC评分最高的贝叶斯网络(7-8行)。

注意，一个贝叶斯网络的BIC评分BIC(g,θ|D)与期望BIC评分不同。

在缺值数据的情况下，SEM的运算复杂度远远低于LearnBN-HC算法。
主要原因是在优化模型结构时，SEM不需要像LearnBN-HC那样调用EM算法来优化候选结构的参数。
SEM只需要优化最优候选结构的参数，即使这时，他也只进行R次参数优化，而不是像EM那样一直优化参数直到收敛为止。
团树传播也可以用来实现SEM的第6行。
这里对每一个候选结构G,首先需要计算其参数的、基于修补后数据 $\overline D$ 的最大似然估计θ，然后再计算 $Q(G,\theta)|G',\theta^{t_GR}$ 。
必须对每一数据样本 $D_l$ 和每一变量 $X_l$ 计算 $P(X_i, \pi_s(X_i)) \mid D_i, \theta^i, \theta^{i,R}$ 。
为此，可以构造一个覆盖 $G^t$ 的团树T，并用 $\theta^{t_GR}$ 将其初始化。
对每个数据样本 $D_l$ ，按照它设置证据，然后进行信息传播。
在信息传播结束后，就可以计算的后验概率分布。