第14章 概率图模型

14.1

[解析]：所有的相乘关系都表示概率的相互独立。三种概率P\left(y_{i}\right), P\left(x_{i} | y_{i}\right), P\left(y_{i} | y_{i-1}\right) 分别表示初始状态概率，输出观测概率和条件转移概率。

14.2

[解析]：因为各个团之间概率分布相互独立，因此它们连乘可以表示最终的概率。

14.3

[解析]：意义同式14.2, 区别在于此处的团为极大团。

14.4

[解析]：将图14.3分解成x_{A}, x_{C} 和 x_{B}, x_{C} 两个团。

14.5

[推导]：参见原书推导。

14.6

[推导]：参见原书推导。

14.7

[解析]：可由14.5、14.6联立可得。

14.8

[解析]：此为势函数的定义式，即将势函数写作指数函数的形式。指数函数满足非负性，且便于求导，因此在机器学习中具有广泛应用，例如西瓜书公式8.5和13.11。

14.9

[解析]：此为定义在变量\mathbf{x}_{Q}上的函数H_{Q}\left(\cdot\right)的定义式，第二项考虑单节点，第一项考虑每一对节点之间的关系。

14.10

[解析]：根据局部马尔科夫性，给定某变量的邻接变量，则该变量独立与其他变量，即该变量只与其邻接变量有关，所以式14.10中给定变量v 以外的所有变量与仅给定变量v的邻接变量是等价的。

14.14

[解析]：在消去变量的过程中，在消去每一个变量时需要保证其依赖的变量已经消去，因此消去顺序应该是有向概率图中的一条以目标节点为终点的拓扑序列。

14.15

[解析]：变量消去的顺序为从右至左求和号的下标，应当注意x_4与x_5相互独立，因此可与x_3的消去顺序互换，对最终结果无影响。

14.16

[解析]：注意到\sum_{x_{4}} P\left(x_{4} | x_{3}\right) = 1。

14.17

[解析]：忽略图14.7(a)中的箭头，然后把无向图中的每条边的两个端点作为一个团将其分解为四个团因子的乘积。Z为规范化因子确保所有可能性的概率之和为1。

14.18

[解析]：原理同式14.15, 区别在于把条件概率替换为势函数。

14.19

[解析]：该式表示从节点i传递到节点j的过程，求和号表示要考虑节点i的所有可能取值。连乘号解释见式14.20。应当注意这里连乘号的下标不包括节点j，节点i只需要把自己知道的关于j以外的消息告诉节点j即可。

14.20

[解析]：应当注意这里是正比于而不是等于，因为涉及到概率的规范化。可以这么解释，每个变量可以看作一个有一些邻居的房子，每个邻居根据其自己的见闻告诉你一些事情(消息)，任何一条消息的可信度应当与所有邻居都有相关性，此处这种相关性用乘积来表达。【引用http://helper.ipam.ucla.edu/publications/gss2013/gss2013_11344.pdf】

14.22

[推导]：假设x有M种不同的取值，x_i的采样数量为m_i(连续取值可以采用微积分的方法分割为离散的取值)，则

14.26

[解析]：假设变量\mathbf{x}所在的空间有n个状态(s_1,s_2,..,s_n), 定义在该空间上的一个转移矩阵\mathbf{T}\in\mathbb{R}^{n\times n}满足一定的条件则该马尔可夫过程存在一个稳态分布\boldsymbol{\pi}, 使得

其中, \boldsymbol{\pi}是一个是一个n维向量，代表s_1,s_2,..,s_n对应的概率. 反过来, 如果我们希望采样得到符合某个分布\boldsymbol{\pi}的一系列变量\mathbf{x}^1,\mathbf{x}^2,..,\mathbf{x}^t, 应当采用哪一个转移矩阵\mathbf{T}\in\mathbb{R}^{n\times n}呢？

事实上，转移矩阵只需要满足马尔可夫细致平稳条件

即公式14.26，这里采用的符号与西瓜书略有区别以便于理解. 证明如下

假设采样得到的序列为\mathbf{x}^1,\mathbf{x}^2,..,\mathbf{x}^{t-1},\mathbf{x}^t，则可以使用MH算法来使得\mathbf{x}^{t-1}(假设为状态s_i)转移到\mathbf{x}^t(假设为状态s_j)的概率满足式。

14.27

[解析]：这里把式14.26中的函数T 拆分为两个函数Q和A之积，即先验概率和接受概率，便于实际算法的实现。

14.28

[推导]：这个公式其实是拒绝采样的一个trick，因为基于式14.27只需要

即可满足式14.26，但是实际上等号右边的数值可能比较小，比如各为0.1和0.2，那么好不容易才到的样本只有百分之十几得到利用，所以不妨将接受率设为0.5和1，则细致平稳分布条件依然满足，样本利用率大大提高, 所以可以改进为

其中

即西瓜书中的14.28。

14.29

[解析]：连乘号是因为N个变量的生成过程相互独立。求和号是因为每个变量的生成过程需要考虑中间隐变量的所有可能性，类似于边际分布的计算方式。

14.30

[解析]：对式14.29取对数。

14.31

[解析]：EM算法中的M步，参见7.6节。

14.32

\begin{aligned}
{\rm ln}p(x)&=\int q(z){\rm ln}p(x)dz \
&=\int q(z){\rm ln}\frac{p(x,z)}{p(z|x)}\
&=\int q(z){\rm ln}\bigg{\frac{p(x,z)}{q(z)}\cdot\frac{q(z)}{p(z|x)}\bigg} \
&=\int q(z)\bigg({\rm ln}\frac{p(x,z)}{q(z)}-{\rm ln}\frac{p(z|x)}{q(z)}\bigg) \
&=\int q(z){\rm ln}\bigg{\frac{p(x,z)}{q(z)}\bigg}-\int q(z){\rm ln}\frac{p(z|x)}{q(z)} \
&=\mathcal{L}(q)+{\rm KL}(q \parallel p)\qquad
\end{aligned}

\mathcal{L}(q)=\int q(\mathbf{z}) \ln \left{\frac{p(\mathbf{x}, \mathbf{z})}{q(\mathbf{z})}\right} \mathrm{d} \mathbf{z}

\mathrm{KL}(q | p)=-\int q(\mathrm{z}) \ln \frac{p(\mathrm{z} | \mathrm{x})}{q(\mathrm{z})} \mathrm{d} \mathrm{z}

q(\mathbf{z})=\prod_{i=1}^{M} q_{i}\left(\mathbf{z}_{i}\right)

\begin{aligned}
\mathcal{L}(q)&=\int \prod_{i}q_{i}\bigg{ {\rm ln}p({\rm \mathbf{x},\mathbf{z}})-\sum_{i}{\rm ln}q_{i}\bigg}d{\rm\mathbf{z}} \
&=\int q_{j}\bigg{\int p(x,z)\prod_{i\ne j}q_{i}d{\rm\mathbf{z_{i}}}\bigg}d{\rm\mathbf{z_{j}}}-\int q_{j}{\rm ln}q_{j}d{\rm\mathbf{z_{j}}}+{\rm const} \
&=\int q_{j}{\rm ln}\tilde{p}({\rm \mathbf{x},\mathbf{z_{j}}})d{\rm\mathbf{z_{j}}}-\int q_{j}{\rm ln}q_{j}d{\rm\mathbf{z_{j}}}+{\rm const}
\end{aligned}

\mathcal{L}(q)=\int \prod_{i}q_{i}\bigg{ {\rm ln}p({\rm \mathbf{x},\mathbf{z}})-\sum_{i}{\rm ln}q_{i}\bigg}d{\rm\mathbf{z}}=\int\prod_{i}q_{i}{\rm ln}p({\rm \mathbf{x},\mathbf{z}})d{\rm\mathbf{z}}-\int\prod_{i}q_{i}\sum_{i}{\rm ln}q_{i}d{\rm\mathbf{z}}

\begin{aligned}
\int\prod_{i}q_{i}{\rm ln}p({\rm \mathbf{x},\mathbf{z}})d{\rm\mathbf{z}} &= \int q_{j}\prod_{i\ne j}q_{i}{\rm ln}p({\rm \mathbf{x},\mathbf{z}})d{\rm\mathbf{z}} \
&= \int q_{j}\bigg{\int{\rm ln}p({\rm \mathbf{x},\mathbf{z}})\prod_{i\ne j}q_{i}d{\rm\mathbf{z_{i}}}\bigg}d{\rm\mathbf{z_{j}}}\qquad
\end{aligned}

\begin{aligned}
\int\prod_{i}q_{i}{\rm ln}q_{k}d{\rm\mathbf{z}}&= \int q_{i^{\prime}}\prod_{i\ne i^{\prime}}q_{i}{\rm ln}q_{k}d{\rm\mathbf{z}}\qquad \
&=\int q_{i^{\prime}}\bigg{\int\prod_{i\ne i^{\prime}}q_{i}{\rm ln}q_{k}d{\rm\mathbf{z_{i}}}\bigg}d{\rm\mathbf{z_{i^{\prime}}}}
\end{aligned}

\begin{aligned}
\int\prod_{i}q_{i}{\rm ln}q_{k}d{\rm\mathbf{z}}&=\int\prod_{i\ne i^{\prime}}q_{i}{\rm ln}q_{k}d{\rm\mathbf{z_{i}}} \
&= \int q_{k}{\rm ln}q_{k}d{\rm\mathbf{z_k}}\qquad
\end{aligned}

\begin{aligned}
\int\prod_{i}q_{i}\sum_{i}{\rm ln}q_{i}d{\rm\mathbf{z}}&= \int\prod_{i}q_{i}{\rm ln}q_{j}d{\rm\mathbf{z}} + \sum_{k\ne j}\int\prod_{i}q_{i}{\rm ln}q_{k}d{\rm\mathbf{z}} \
&= \int q_{j}{\rm ln}q_{j}d{\rm\mathbf{z_j}} + \sum_{k\ne j}\int q_{k}{\rm ln}q_{k}d{\rm\mathbf{z_k}}\qquad \
&= \int q_{j}{\rm ln}q_{j}d{\rm\mathbf{z_j}} + {\rm const} \qquad
\end{aligned}

\ln \tilde{p}\left(\mathbf{x}, \mathbf{z}{j}\right)=\mathbb{E}{i \neq j}[\ln p(\mathbf{x}, \mathbf{z})]+\text { const }

\mathbb{E}{i \neq j}[\ln p(\mathbf{x}, \mathbf{z})]=\int \ln p(\mathbf{x}, \mathbf{z}) \prod{i \neq j} q_{i} \mathrm{d} \mathbf{z}_{i}

\ln q_{j}^{*}\left(\mathbf{z}{j}\right)=\mathbb{E}{i \neq j}[\ln p(\mathbf{x}, \mathbf{z})]+\mathrm{const}

\begin{aligned}
q_j^*(\mathbf{z}j) = \frac{ \exp\left ( \mathbb{E}{i\neq j}[\ln (p(\mathbf{x},\mathbf{z}))] \right ) }{\int \exp\left ( \mathbb{E}_{i\neq j}[\ln (p(\mathbf{x},\mathbf{z}))] \right ) \mathrm{d}\mathbf{z}_j}
\end{aligned}

\begin{aligned}
\int q_j^*(\mathbf{z}_j)\mathrm{d}\mathbf{z}j &=\int \exp\left ( \mathbb{E}{i\neq j}[\ln (p(\mathbf{x},\mathbf{z}))] \right )\cdot\exp(const) , \mathrm{d}\mathbf{z}j \
&=\exp(const) \int \exp\left ( \mathbb{E}{i\neq j}[\ln (p(\mathbf{x},\mathbf{z}))] \right ) , \mathrm{d}\mathbf{z}_j \
&= 1
\end{aligned}

\exp(const) = \dfrac{1}{\int \exp\left ( \mathbb{E}_{i\neq j}[\ln (p(\mathbf{x},\mathbf{z}))] \right ) , \mathrm{d}\mathbf{z}_j} \

\begin{aligned}
q_j^*(\mathbf{z}j) &= \exp\left ( \mathbb{E}{i\neq j}[\ln (p(\mathbf{x},\mathbf{z}))] \right )\cdot\exp(const) \
&= \frac{ \exp\left ( \mathbb{E}{i\neq j}[\ln (p(\mathbf{x},\mathbf{z}))] \right ) }{\int \exp\left ( \mathbb{E}{i\neq j}[\ln (p(\mathbf{x},\mathbf{z}))] \right ) \mathrm{d}\mathbf{z}_j}
\end{aligned}

p(\boldsymbol W,\boldsymbol z,\boldsymbol \beta,\boldsymbol \theta | \boldsymbol \alpha,\boldsymbol \eta) =
\prod_{t=1}^{T}p(\boldsymbol \theta_t | \boldsymbol \alpha)
\prod_{k=1}^{K}p(\boldsymbol \beta_k | \boldsymbol \eta)
(\prod_{n=1}^{N}P(w_{t,n} | z_{t,n}, \boldsymbol \beta_k)P( z_{t,n} | \boldsymbol \theta_t))

p\left(\Theta_{t} | \boldsymbol{\alpha}\right)=\frac{\Gamma\left(\sum_{k} \alpha_{k}\right)}{\prod_{k} \Gamma\left(\alpha_{k}\right)} \prod_{k} \Theta_{t, k}^{\alpha_{k}-1}

L L(\boldsymbol{\alpha}, \boldsymbol{\eta})=\sum_{t=1}^{T} \ln p\left(\boldsymbol{w}_{t} | \boldsymbol{\alpha}, \boldsymbol{\eta}\right)

p(\mathbf{z}, \boldsymbol{\beta}, \Theta | \mathbf{W}, \boldsymbol{\alpha}, \boldsymbol{\eta})=\frac{p(\mathbf{W}, \mathbf{z}, \boldsymbol{\beta}, \boldsymbol{\Theta} | \boldsymbol{\alpha}, \boldsymbol{\eta})}{p(\mathbf{W} | \boldsymbol{\alpha}, \boldsymbol{\eta})}