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

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

七、缺值数据最大似然估计

3. EM算法

EM的E-步骤要计算的是 $Q(\theta|\theta')$ ，就是要计算充分统计量 $m'_{ijk}$ 。
由于 $\sum_{x_l \in \Omega_{X_l}} P(X_l = x_l \mid D_l, \theta^t) \cdot \mathbf{1}_{\{X_i = k,\; \pi(X_i)=j\}}(D_l, X_l = x_l) = P(X_i = k,\; \pi(X_i)=j \mid D_l, \theta^t)$ 。
所以， $m^t_{ijk}$ 可用下式来计算 $m^t_{ijk}=\sum^m_{l=1}P(X_I=K,\pi(X_i)=j|D_1,\theta^t)$ 。
EM的M-步骤要计算 $arg\sup_\theta Q(\theta|\theta')$ ，只需要把从式得到的 $m'_{ijk}$ 代入即可。
EM算法的伪代码如下：

输入：G - 贝叶斯网络N的结构；

输入：D - 一组关于N中变量的数据；

输入：δ - 收敛阈值。

输出：N的参数的估计：

1: $t\leftarrow 0,\theta^0\leftarrow$ 随机参数值；

2: $oldScore\leftarrow l(\theta^t|D)$ ;

3: while(true)

4: E-步骤:计算 $m^t_{ijk}(i=1,...,n;j=1,...,q_i;k=1,...,r_i)$ ;

5: M-步骤:计算 $\theta^{t+1}$ ;

6: $newScore\leftarrow l(\theta^{t+1}|D)$ ;

7: if(newScore > oldScore + δ)

8: $oldScore\leftarrow newScore$ ;

9: $t\leftarrow t+1$ ;

10: else

11: return $\theta^{t+1}$

12: end if

13:end while.

关于参数向量 $\theta^t$ 该如何表示，一种做法是把它表示为一个一维数组，但使用起来不方便。因为 $\theta^t$ 是贝叶斯网络中的所有参数组成的向量，所以比较好的办法是用贝叶斯网络的数据结构来表示它。
假设已知 $\theta^t$ ，如何来表示 $\theta^{t+1}$ ？
直接的方法是对每一个I，先按照调用变量消元算法m次来计算 $m^t_{ijk}(j=1,...,q_i;k=1,...,r_i)$ ，然后再计算相应的 $\theta^{t+1}_{ijk}$ 。
这样，在计算时会进行mn次推理，在各次推理之间没有实现计算共享。
可以用团书传播实现计算共享，从而加快 $\theta^{t+1}$ 的计算的方法。
设T是一颗覆盖N的团树，由以下4步组成：

(1) 将 $m^t_{ijk}(j=1,...,q_i;k=1,...,r_i)$ 置零；

(2)用 $\theta^t$ 将团书T初始化；

(3)对每一个样本 $D_l$ :

在团数T中按 $D_l$ 设置证据，并调用算法CTP的第3~5步进行信息传递；

对每一个变量 $X_i$ :

在团书T中找到 $X_i$ 的一个家族覆盖团 $C_{X_i}$ ，并调用算法CTP得到函数 $h(C_{X_i})$ ，进而得到 $P(X_i,\pi(X_i)|D_l,\theta^t)=\sum_{C_{X_i}\(X_i)\cap \pi(X_i)}h(C_{X_i})$ ;

在 $m^t_{ijk}(j=1,...,q_i;k=1,...,r_i)$ 中加上公式所得的结果；

(4)将 $m^t_{ijk}(i=1,...,n;j=1,...,q_i;k=1,...,r_i)$ 代入公式，获得 $\theta^{r+1}$ 。

关于EM算法中如何计算 $l(\theta^{t+1}|D)$ ：

由于i.i.d假设，可以对每一个样本 $D_l$ 分别调用VE算法来计算 $l(\theta^{t+1}|D_l)$ ，他们的和就是对数似然度 $l(\theta^{t+1}|D)$ 。

将上述计算 $\theta^{t+1}$ 的方法稍加修改，就可以在计算 $\theta^{t+1}$ 的同时获得对数似然度 $l(\theta^{t+1}|D)$ ，从而实现计算共享。

其基本思想是在信息传递完成之后，任选一个团C，将传递到C的信息以及储存在C处的函数相城，得到一个函数 $h(C)$ 。

$\sum_Ch(C)$ 就是 $l(\theta^{t+1}|D_l)$

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

七、缺值数据最大似然估计

3. EM算法

友情链接更多精彩内容