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

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

八、结构学习

2. 贝叶斯模型选择

设D是一组关于变量 $X_1,X_2,...,X_n$ 的完整i.i.d数据，G是一个以 $X_1,X_2,...,X_n$ 为节点的贝叶斯网络。
如果参数先验分布 $p(\theta_G|G)$ 是如下的乘积狄利克雷分布： $p(\theta_G|G)\propto \prod^n_{i=1}\prod^{q_i}_{j=1}\prod^{r_i}_{k=1}$ \theta^{\alpha_{ijk-1}}_{ijk}$。
那么 $L(G|D) = \prod^n_{i=1}\prod^{G_I}_{J=1}\frac{/Gamma(a_{ij}*)}{\Gamma(a_{ij}*+m_{ij}*)}\frac{\Gamma(a_{ijk}+m_{ijk})}{\Gamma(a_{ijk})}$ 。

其中 $m_{ijk}$ 是D中满足 $X_i=k,\pi(X_i)=j$ 的样本个数， $m_ij*=\sum^{r_i}_{k=1}m_{ijk},a_{ij}*=\sum^{r_i}_{k=1}a_{ijk}$

证明：为方便起见，约定在 $D = \phi$ 时， $P(D|G) = P(\phi|G)=1$ 。
在这一约定下 $P(G,D_{m+1})|G=P(G|D)P(D_{m+1}|G,D)$ 即使在 $D=\phi$ 时也成立。

当 $D=\phi$ 时，公式等号左边按约定是1。所以此时公式成立。

设公式在m个样本即 $D=(D_1,D_2,...,D_m)$ 的情况下成立。
下面证明它在m+1个样本即 $D\concate D_{m+1}=(D_1,D_2,...,D_m,D_{m+1})$ 时也成立。
设 $m_{ijk}是m$ 个样本时，满足 $X_i=k,\pi(X_i) = j$ 的样本的个数；
$m'_{ijk}$ 是m+1个样本时，满足 $X_i=k,\pi(X_i)=j$ 的样本的个数，有 $m_ijk=\sum^m_{l=1}\Chi(i,j,k:D_l),m'_{ijk}=\sum^{m+1}_{l=1}(i,j,k:D_l)$ 。
于是 $m'_{ijk}=m_{ijk}+\Chi(i,j,j:D_{m+1}),m'_{ij*}=m_{ij*}+\Chi(i,j,*:D_{m+1})$

其中 $\Chi(i,j,*:D_{m+1})=\sum^{r_i}_{k=1}\Chi (i,j,k:D_{m+1})$

根据归纳假设，有 $P(D|G) = \prod^n_{i=1}\prod^{q_i}_{j=1}\frac{\Gamma(a_{ij*})}{\Gamma(a_{ij*}+m_{ij*})}\prod^{r_i}_{k=1}\frac{\Gamma(a_{ijk}+m_{ijk})}{\Gamma(a_{ijk})}$
而 $P(D_{m+1}|G,D)$ 是在给定网络结构G的情况下，基于D对 $D_{m+1}$ 的分布进行贝叶斯估计的结果。
可以改写成如下式 $P(D_{m+1} \mid \mathcal{G}, \mathcal{D}) = \prod_{i=1}^n \prod_{j=1}^{q_i} \frac{1}{(m_{ij} + \alpha_{ij})} \chi_{(i,j,*,D_{m+1})} \prod_{k=1}^{r_i} (m_{ijk} + \alpha_{ijk})^{\chi_{(i,j,k,D_{m+1})}}$ 。
简化后，得 $P(\mathcal{D}, D_{m+1} \mid \mathcal{G}) = \prod_{i=1}^n \prod_{j=1}^{q_i} \frac{\Gamma(\alpha_{ij})}{\Gamma(\alpha_{ij} + m_{ij}) (m_{ij} + \alpha_{ij})^{\chi_{(i,j,*,D_{m+1})}}} \times \prod_{k=1}^{r_i} \frac{\Gamma(\alpha_{ijk} + m_{ijk}) (m_{ijk} + \alpha_{ijk})^{\chi_{(i,j,k,D_{m+1})}}}{\Gamma(\alpha_{ijk})}$
由于 $\Chi (i,j,*:D_{m+1})$ 非0即1，而 $\Gamma$ 函数满足 $\Gamma(a+1)=a\Gamma(a)$ ，有 $P(\mathcal{D}, D_{m+1} \mid \mathcal{G}) = \prod_{i=1}^n \prod_{j=1}^{q_i} \frac{\Gamma(\alpha_{ij})}{\Gamma(\alpha_{ij} + m_{ij}) + \chi_{(i,j,*,D_{m+1})}} \times \prod_{k=1}^{r_i} \frac{\Gamma(\alpha_{ijk} + m_{ijk}) + \chi_{(i,j,k,D_{m+1})}}{\Gamma(\alpha_{ijk})}$ 。
得 $P(\mathcal{D}, D_{m+1} \mid \mathcal{G}) = \prod_{i=1}^n \prod_{j=1}^{q_i} \frac{\Gamma(\alpha_{ij})}{\Gamma(\alpha_{ij} + m'_{ij})} \prod_{k=1}^{r_i} \frac{\Gamma(\alpha_{ijk} + m'_{ijk})}{\Gamma(\alpha_{ijk})}$
证明了前面的公式再m+1时成立，所以定理得证。
公式两边取对数，得 $l(\mathcal{G} \mid \mathcal{D}) = \sum_{i=1}^n \sum_{j=1}^{q_i} \left[ \log \frac{\Gamma(\alpha_{ij})}{\Gamma(\alpha_{ij} + m_{ij})} + \sum_{k=1}^{r_i} \log \frac{\Gamma(\alpha_{ijk} + m'_{ijk})}{\Gamma(\alpha_{ijk})} \right]$