三硬币问题-一个EM算法和Gibbs Sampling的例子

讲一个EM算法和Gibbs 抽样的小例子,用于加深理解(变分推断版本请见变分推断学习笔记(3)——三硬币问题的变分推断解法)。

题目(引用自参考1):假设有3枚硬币,分别记做A,B,C。这些硬币正面出现的概率分别是\(\pi\),\(p\)\(q\)。进行如下掷硬币实验:先掷硬币A,根据其结果选出硬币B或C,正面选B,反面选硬币C;然后投掷选重中的硬币,出现正面记作1,反面记作0;独立地重复\(n\)次(n=10),结果为 \[1111110000\] 我们只能观察投掷硬币的结果,而不知其过程,估计这三个参数\(\pi\),\(p\)\(q\)

EM算法

可以看到投掷硬币时到底选择了B或者C是未知的。我们设隐藏变量Z 来指示来自于哪个硬币,\(Z=\{z_1,z_2,\ldots,z_n \}\),令\(\theta=\{\pi,p,q\}\),观察数据\(X=\{x_1,x_2,\ldots,x_n \}\)

写出生成一个硬币时的概率: \[\begin{split}P(x|\theta) & =\sum_z P(x,z|\theta)=\sum_z P(z|\pi)P(x|z,\theta) \\& =\pi p^x (1-p)^{1-x}+(1-\pi)q^x(1-q)^{1-x} \\\end{split}\] 有了一个硬币的概率,我们就可以写出所有观察数据的log似然函数: \[L(\theta|X)=\log P(X|\theta)=\sum^n_{j=1}\log[\pi p^{x_j} (1-p)^{1-{x_j}}+(1-\pi)q^{x_j}(1-q)^{1-{x_j}}]\] 然后求极大似然 \[\hat{\theta}=\arg \max L(\theta|X)\] 其中\(L(\theta|X)=\log P(X|\theta)=\log \sum_Z P(X,Z|\theta)\)。因为log里面带着加和所以这个极大似然是求不出解析解的。

Read More

高斯混合模型参数估计详细推导过程

已知多元高斯分布的公式: \[N(x|\mu,\Sigma)=\frac{1}{(2\pi)^{D/2}|\Sigma|^{1/2}}\exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))\] 其中\(D\)为维度,\(x\)\(\mu\)均为\(D\)维向量,协方差\(\Sigma\)为D维矩阵。我们求得后验概率: \[w^{(i)}_j=Q_i(Z^{i}=j)=P(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)\] 在E步,\(w^{(i)}_j\)是一个固定值,然后我们用它来估计似然函数\(L(X,Z;\theta)\)(这里\(\theta=(\phi,\mu,\Sigma)\))在分布\(Z\sim P(Z|X;\theta)\)上的期望\(E_{Z|X,\theta_t}[L(X,Z;\theta)]\)(式子1): \[\begin{split} & \sum^m_{i=1}\sum_{z^{(i)}} Q_i(z^{(i)})\log{\frac{p(x^{(i)},z^{(i)};\phi,\mu,\Sigma)}{Q_i(z^{(i)})}} \\& =\sum^m_{i=1}\sum^k_{j=1} Q_i(z^{(i)}=j)\log{\frac{p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)p(z^{(i)}=j;\phi)}{Q_i(z^{(i)})}} \\& =\sum^m_{i=1}\sum^k_{j=1} w^{(i)}_j\log{\frac{\frac{1}{(2\pi)^{D/2}|\Sigma|^{1/2}}\exp(-\frac{1}{2}(x^{(i)}-\mu_j)^T\Sigma_j^{-1}(x^{(i)}-\mu_j))\cdot\phi_j}{ w^{(i)}_j}} \\\end{split}\] 由于分母\(w^{(i)}_j\)在取对数之后是常数,与参数无关,求导时自然会变成0,所以我们写公式的时候为了简便舍去分母。

Read More

一般形式的EM算法

问题定义

先给出一般EM算法的问题定义。 给定一个训练集\(X=\{x^{\{1\}},\ldots,x^{\{m\}}\}\)。根据模型的假设,我们希望能够通过这些数据来估计参数\(\theta\),但是每个我们观察到的\(x^{i}\) 还受着一个我们观察不到的隐含变量\(z^{i}\)(也是\(\theta\)生成的)控制,我们记\(Z=\{z^{\{1\}},\ldots,z^{\{m\}}\}\), 整个模型\(p(X,Z|\theta)\)是个关于变量\(X,Z\)的联合分布。

我们通过求最大似然\(L(\theta|X)\)来估计\(\theta\)的值。

\[ \theta=\arg\max_{\theta} L(\theta|X)\]

其中

\[ L(\theta|X)=\ln p(X|\theta)=\ln \sum_{Z}{p(X,Z|\theta)}\]

这里要注意\(p(X|\theta)\)是一个边缘分布,需要通过聚合\(Z\)得到。由于右边的式子在对数函数中又存在加和,所以我们直接对似然求导是没办法得到\(\theta\)的。

这里EM算法可以比较好地解决这个问题。对于EM的一般算法,有从期望的角度解释,用Jensen不等式证明正确性的方法(见参考2)。这里我讲的是另一种从相对熵角度解释,来自PRML的方法。这两种方法各有特定,对比如下:

  • 使用期望的角度来讲,可以地了解EM算法是如何绕过未知\(Z\)下难以计算的问题,即通过最大化它的期望。但是对E和M步如何逼近极大似然的过程,需要对Jensen不等式和单调逼近\(\theta\)最优值过程的理解。

  • 使用相对熵角度解释,可以看清似然函数和它的下界函的迭代增长过程。但是对\(Q(Z)\)和KL散度的引入,以及为什么要最大化下界函数这一点讲的不是很明白(个人看法)。2013年9月25日更新:这里应该是设一个分布Q(z)来近似P(Z),KL散度描述了这两个分布之间的差异,这里只是没有提到下界函数刚好是似然关于后验概率的期望,要求的是下界函数也就是期望的最大值。

Read More