可观贝叶斯网络中的学习问题

发表于 | 分类于

完全可观的图模型学习

图模型学习的目的是在给定独立的样本集的情况下找到合适的的贝叶斯网络，这里的学习（learning）表示对参数的估计或者是从数据学习网络的拓扑结构。

最大似然在信息论上的解释

可以这样理解，将对数似然函数在数据上的和，转变为在变量状态上的和。
\begin{equation}\begin{split} l(\theta_G,G;D)&=log\ p(D\mid \theta_G,G) (Joint Likelilood)\\
& = log\ p\prod_n(\prod_i p(x_{n,i}\mid x_{n,\pi_{i(G)}}, \theta_{i\mid \pi_{i(G)}}) (BN Factorization Rule)\\
& = \Sigma_i(\Sigma_n log\ p(x_{n,i}\mid x_{n,\pi_{i(G)}}, \theta_{i\mid \pi_{i(G)}}))\\
& = M\ \Sigma_i(\Sigma_{x_i,x_{\pi_{i(G)}}} \frac{count(x_i,x_{\pi_{i(G)}})}{M} log\ p(x_i\mid x_{\pi_{i(G)}}, \theta_{i\mid \pi(G)})) \\
& = M\ \Sigma_i(\Sigma_{x_i,x_{\pi_{i(G)}}} \hat{p}(x_i, x_{\pi_{i(G)}}) log\ p(x_i\mid x_{\pi_{i(G)}}, \theta_{i\mid \pi(G)})) \\
\end{split}\end{equation}

这里的H表示变量状态，概率分布$p(x_i)$用计数函数取代（count function）。$(x_i,x_{\pi{i(G)}}$包括了所随机变量的值。
继续对上面的式子进行推导：
\begin{equation}\begin{split} l(\theta_G,G;D)&=M\ \Sigma_i(\Sigma_{x_i,x_{\pi_{i(G)}}} \hat{p}(x_i, x_{\pi_{i(G)}}) log\ p(x_i\mid x_{\pi_{i(G)}}, \theta_{i\mid \pi(G)})) \\
& = M\ \Sigma_i(\Sigma_{x_i,x_{\pi_{i(G)}}} \hat{p}(x_i, x_{\pi_{i(G)}}) log\ \frac{p(x_i, x_{\pi_{i(G)}}\mid \theta_{i\mid \pi_{(G)}})} {\hat{p}(x_i, x_{\pi_{i(G)}})}\frac{\hat{p}(x_i)}{\hat{p}(x_i)})\\
& = M\ \Sigma_i(\Sigma_{x_i,x_{\pi_{i(G)}}} \hat{p}(x_i, x_{\pi_{i(G)}}) log\ \frac{p(x_i, x_{\pi_{i(G)}}, \theta_{i\mid \pi_{(G)}})} {\hat{p}(x_i, x_{\pi_{i(G)}})\hat{p}(x_i)}) - M\ \Sigma_i\Sigma_{x_i} - \hat{p}(x_i)log\ \hat{p}(x_i)\\
& = M\ \Sigma_i\hat{I}(x_i,x_{\pi_{i(G)}}) - M\ \Sigma_i\hat{H}(x_i) \\
\end{split}\end{equation}
这样可以将最大似然估计分成两个部分，第一个部分是所有节点的互信息，第二部分是每个节点的熵。可以得出这样的结论，如果我们确定结构式树结构（每个节点只有一个父节点），那么基于最大似然估计下，我们可以获得一个最优的树。

Chow-Liu 算法

目标函数可以写成：
$$ l(\theta_G,G;D) = M\ \Sigma_i\hat{I}(x_i,x_{\pi_{i(G)}}) - M\ \Sigma_i\hat{H}(x_i) $$
将上式后面各个变量的熵去掉，因为变量的熵与树的结构无关，上式化简为：
\begin{equation}\begin{split} C(G) &= M\ \Sigma_i\hat{I}(x_i,x_{\pi_{i(G)}}) \\
&= M\ \Sigma_i\hat{I}(x_i,x_j) \\
\end{split}\end{equation}
我们只需要计算经验分布（empirical distribution）和每对节点的互信息（mutual information）就可以了。经验分布可以通过数据直接数出来，下面是计算每对节点$x_i$和$x_j$之间的经验分布和互信息。
$$ \hat{p}(X_i, X_j) = \frac{count(x_i, x_j)}{M} $$
$$ \hat{I}(X_i, X_j) = \Sigma_{x_i, x_j}\hat{p}(x_i, x_j)log\ \frac{\hat{p}(x_i, x_j)}{\hat{p}(x_i)\hat{p}(x_j)} $$
我们定义一个有节点$x_1, x_2, x_3, …,x_n$的图，指定图的边$(i, j)$的权值为$\hat{I}(X_i, X_j)$。Chow-Liu算法可以计算最大权重生成树。挑选任意节点作为根节点，然后使用宽度优先算法（breadth-first-search）来决定方向。

对于完全可观的给定结构的参数学习

假定图结构固定，从N个独立同分布的样本集中进行参数估计$D = \lbrace x_1, x_2, x_3, …, x_N\rbrace$。一般来说，每个训练样本$x_n = x_{n, 1}, x_{n,2}, …, x_{n,M}$是M维的向量，对应于每个节点。下面介绍几个常见用于参数估计的分布。

多项式模型

对于N个独立同分布的样本，采用unit basis vectors表示，$x_n = (x_{n,1}, x_{n,2}, …, x_{n,K})$，其中$x_{n,k}=\lbrace 0, 1 \rbrace $， $\Sigma_{k=1}^K x_{n, k} $。这种表示方法将事件抽离出来，不考虑事件本身的意义，关注事件发生与否。数据集$D = \lbrace x_1, x_2, x_3, …, x_N\rbrace$的似然函数为：
$$ L(\theta\mid D) = P(x_1, x_2, …, x_N\mid \theta) = \prod_{n=1}^N P(x_n\mid \theta) = \prod_k \theta_k^{n_k} $$
$$ l(\theta\mid D) = log\ \prod_k \theta_k^{n_k} = \Sigma_k n_k log\ \theta_k $$
因为存在着等式约束$\Sigma_{k=1}^K x_{n,k} = 1$，所以需要在$l(\theta\mid D)$中加入Lagarange乘子。
$$ \hat{l}(\theta\mid D) = \Sigma_k n_k log\ \theta_k + \lambda(1 - \Sigma_{k=1}^K x_{n,k}) $$
对$\theta_k$求偏导并令其为零：
$$ \hat{\theta}{k,MLE} = \frac{n_k}{N} $$
或者$$ \hat{\theta}{k,MLE} = \frac{1}{N}\Sigma_n x_{n,k}$$
此外，$\bar{n} = {n_1, n_2, …, n_K}$和$n_k = \Sigma_n x_{n,k}$是数据集D的充分统计量。

贝叶斯参数估计

贝叶斯参数估计就是通过贝叶斯定理，利用先验概率分布来推测出后验概率分布，所以先验概率分布对于贝叶斯参数估计方法来说非常的重要，下面介绍两种常见的先验。

狄利克雷先验(Dirichlet Prior)

Dirichlet Prior由一组超参数$\alpha_1, \alpha_2, …,\alpha_N$来定义。Dirichlet分布如下：
$$ P(\theta) = \frac{\Gamma(\Sigma_k \alpha_k)}{\prod_k \Gamma(\Sigma_k \alpha_k)} \prod_k \theta_k^{\alpha_k-1} = C(\alpha)\prod_k \theta_k^{\alpha_k-1} $$
其中$C(\alpha)$是正则化参数，后验概率可以写成如下形式：
$$ P(\theta\mid x_1, x_2, …, x_N) = \frac{P(x_1, x_2,…, x_N\mid \theta)P(\theta)}{P(x_1, x_2, …, x_N)} \propto \prod_k \theta_k^{\alpha_k + n_k -1} $$
因为后验概率与先验概率形式相同，所以被叫做共轭先验。也就是说，只要先验是Dirichlet分布，那么后验就必定是Dirichlet分布。
基于这一特性，就有了序列贝叶斯更新算法。由Dirichlet先验分布$P(\vec{\theta}\mid \vec{\alpha}) = Dir(\vec{\theta}\mid \vec{\alpha})$，后验更新为$P(\vec{\theta}\mid \vec{\alpha},\vec{n’}) = Dir(\vec{\theta}\mid \vec{\alpha}, \vec{n’})$，之后通过$N’$个样本，可以获得充分统计量$\vec{n’}$，后验变成：
$$ P(\vec{\theta}\mid \vec{\alpha},\vec{n’}, \vec{n’’}) = Dir(\vec{\theta}\mid \vec{\alpha}, \vec{n’}, \vec{n’’}) $$
观测另外$N’’$数据有充分统计量$\vec{n’’}$。这样序列化的处理数据方式和批处理是等价的。Dirichlet主要的缺点是一维的分布，不能处理多维的分布，对于多维有对数正态先验。

对数正态先验

对数正态先验相比于Dirichlet拥有更加丰富的分布性质。下面是对数先验的定义：
$$ \theta \sim LN_K(\mu, \Sigma) $$ $$ \gamma \sim N_{K-1}(\mu, \Sigma)\ \ \ \gamma_K = 0 $$ $$\theta_i \sim \lbrace \gamma_i - log(1 + \Sigma_{i=1}^{K-1} e^{\gamma_i}) $$
对数配分函数 $ C(\gamma) = log(1 + \Sigma_{i=1}^{K-1} e^{\gamma_i}) $
对数正态先验可以获得更好的协方差结构的性质，但是它不是共轭先验。

多元正态分布的参数估计

高斯分布的概率密度函数为：
$$p(X; \mu,\Sigma)=\frac{1}{(2\pi)^{n/2}\Sigma^{\frac{1}{2}}}exp \lbrace -\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu) \rbrace$$
可以对$\mu$和$\Sigma$进行最大似然估计：
$$ \mu_{MLE} = \frac{1}{N}\Sigma_n x_n $$
$$ \Sigma_{MLE} = \frac{1}{N}\Sigma_n (x_n - \mu_{MLE})(x_n - \mu_{MLE})^T $$
我们需要主要到当$\Sigma$不是满秩的时候，其也不是可逆的。贝叶斯估计的优势在于贝叶斯估计具有先验知识，或者是先验是共轭的，这样就可以进行序列化的处理，类似于批处理的方式。
特别的，当$\mu$未知，$\sigma$已知时：
$$ p(\mu) = (2\pi\tau^2)^{-1/2} exp\lbrace -(\mu - \mu_0)^2 /2\tau^2 \rbrace $$
联合概率分布为：
$$ P(x,\mu) = (2\pi\tau^2)^{-1/2} exp\lbrace -(\mu - \mu_0)^2 /2\tau^2 \rbrace * (2\pi\sigma^2)^{-N/2} exp\lbrace -\frac{1}{2\sigma^2}\Sigma_{n=1}^N (x_n - \mu)^2 \rbrace $$
后验概率即为：
$$ P(\mu\mid X) = (2\pi\tilde{\sigma}^2)^{-N/2} exp\lbrace -\frac{1}{2\tilde{\sigma}^2} (\mu - \tilde{\mu})^2 \rbrace $$
其中$\mu = \frac{N/\sigma^2}{N/\sigma^2 + 1/\tau} \bar{x} + \frac{1/\tau}{N/\sigma^2 + 1/\tau}\mu_0 $和$ \tilde{\sigma}^2 = (\frac{N}{\sigma^2} + \frac{1}{\tau^2})^{-1} $
后验均值是先验和极大似然估计的凸组合，权值与噪声水平成正比。
后验$1/\tilde{\sigma}^2$是先验$1/\tau^2$与每个观测数据对于$1/\sigma^2$的影响。

最大似然估计用于一般的贝叶斯网络

如果我们假定每个条件概率密度参数是全局独立的，所有的节点是可观的，那么对数似然函数可以分解为如下的形式：
$$ l(\theta; D) = log\ p(D\mid \theta) = \Sigma_i(\Sigma_n log\ p(x_{n,i} \mid x_{n,\pi_i}, \theta_i)) $$
对于独立同分布的数据似然函数为：
$$ p(D\mid \theta) = \prod_n p(x_n\mid \theta) $$

最大似然估计用于离散形式的贝叶斯网络

假定每个条件概率分布都可以用一个表格来表示，其中$\theta_{ijk} = P(X_i = j\mid x_{\pi_i} = k)$，然后充分统计量就是所有可能的状态的和$ n_{ijk} = \Sigma_n x_{n,i}^j x_{n,{\pi_i}}^k $，对数似然函数写成：
$$ l(\theta; \mid D) = log\prod_{i,j,k}\theta_{ijk}^{n_{ijk}} = \Sigma_{i,j,k}n_{i,j,k} log\ \theta_{i,j,k} $$
其中$\Sigma_j \theta_{ijk} = 1$，使用拉格朗日乘数法可以得出结果：
$$ \theta_{ijk}^{ML} = \frac{n_{ijk}}{\Sigma_{j’} n_{ij’k}} $$

贝叶斯参数估计

  • 全局独立性 $p(\theta_m\mid G) = \prod_{i=1}^M p(\theta_i \mid G)$

  • 局部独立性 $p(\theta_i\mid G) = \prod_{j=1}^{q_i} p(\theta_{x_i^k\mid x_{\pi_i^j}} \mid G)$
    全局参数独立性指的是每个节点间的参数是独立的，局部参数独立性指的是节点的参数在其父节点不同的情况下独立。

  • 离散的有向无环图模型满足$x_i\mid x_{\pi_i}^j \sim Multi(\theta)$，同时Dirichlet先验为$p(\theta) = C(\alpha)\prod_k \theta_k^{\alpha_k - 1}$。

  • 高斯有向无环图模型满足$x_i\mid x_{\pi_i}^j \sim Normal(\mu,\Sigma)$，正态Wishart先验为：
    $$ p(\mu\mid v,\alpha_{\mu},W) = Normal(v,(\alpha_{\mu}W)^{-1}) $$
    $$ p(W\mid \alpha_w,T) = c(n, \alpha_w)|T|^{\alpha_w /2}|W|^{(\alpha_w -n-1)/2} exp \lbrace\frac{1}{2}tr\lbrace TW \rbrace\rbrace $$
    其中$W = \Sigma^{-1}$。

马尔科夫链转移矩阵

考虑一个时不变的一阶马尔科夫链，初始状态概率向量为$\pi_k = P(X_1^K = 1)$，状态转移矩阵$A_{ij} = P(X_t^j = 1\mid x_{t-1}^i = 1)$。联合概率为：
$$ P(X_{1:T\mid \theta}) = P(x_1\mid \pi)\prod_{t=2}^T P(X_t\mid X_{t-1})$$
对数似然函数为：
$$ l(\theta;D) = \Sigma_n log\ p(x_{n,1}\mid \pi) + \Sigma_n\Sigma_{t=2}^T log\ P(x_{n,t}\mid x_{n,t-1,A}) $$
A是随机矩阵并且$\Sigma_j A_{ij}$，所以$A_{ij}$的最大似然估计是从$i$到$j$转移的分式：
$$ A_{ij}^{ML} = \frac{\Psi(i\rightarrow j)}{\Psi(i\rightarrow \star)} = \frac{\Sigma_n\Sigma_{t=2}^T x_{n,t-1}^i x_{n,t}^j}{\Sigma_n\Sigma_{t=2}^T x_{n,t-1}^i} $$

上面的方法有一个稀疏的问题，当$i\rightarrow j$没有出现时，$A_{ij}=0$，那么即将出现的单词对$i\rightarrow j$概率为零。可以使用下面的方法进行解决：
$$ \tilde{A}{i\rightarrow \star} = \lambda\eta_t + (1 - \lambda) A{i\rightarrow \star}^{ML} $$

隐马尔科夫模型

  • 两个状态之间转移的可能性$P(y_t^j = 1\mid y_{t-1}^i = 1) = a_{i,j}$或者$P(y_t\mid y_{t-1} = 1)\sim Multinomial(a_{i,1}, a_{i,2}, …, a_{i,M})$。
  • 开始概率$P(y_1) \sim Multinomial(\pi_1, \pi_2,…, \pi_M)$。
  • 每个y向x的传播概率$P(x_t\mid y_t^i = 1)\sim Multinomial(b_{i,1}, b_{i,2}, …, b_{i,K})$。

给定$x=x_1,…,x_N$对实际的状态路径已知，定义如下：
$A_{ij} = \Psi$状态转移在y上从$i\rightarrow j$
$B_{ik} = \Psi $状态i在y中影响在x中的k
$\theta$的最大似然估计：
$$a_{ij}^{ML} = \frac{\Psi(i\rightarrow j)} {\Psi(i\rightarrow \star)} = \frac{A_{ij}}{\Sigma_j A_{ij}}$$
$$ b_{ik}^{ML} = \frac{\Psi(i\rightarrow \star)}{\Psi(i\rightarrow \star)} = \frac{B_{ij}}{\Sigma_k B_{ik}} $$

对于样本较小的情况下，采用伪计数。
$A_{ij} = \Psi$状态转移在$y+R_{ij$}$上从$i\rightarrow j$
$B_{ik} = \Psi$状态i在$y$中影响在$x+S_{ik}$中的k
$R_{ij}$，$S_{ij}$是伪计数，体现了我们对先验信息的信任。

总结

对于完全可观的贝叶斯网络，可以进行分解，所以学习问题可以进行分解。

  • 结构学习
  • Chow Liu 算法
  • 近邻选择
  • 在概率图的单个节点上进行学习-密度估计：指数族分布
  • 一般的离散分布
  • 一般的连续分布
  • 共轭先验
  • 两个节点进行学习：广义线性模型
  • 条件概率密度估计
  • 分类
  • 更多的节点
  • 利用局部的性质

参考文献

[1] http://www.cs.cmu.edu/~epxing/Class/10708-14/lecture.html
注：本文主要参考[1]中第7讲视频以及笔记。

非常感谢各位老板投喂！