三硬币问题-一个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

《Gibbs Sampling for the UniniTiated》阅读笔记(下)---连续型参数求积分的思考

《Gibbs Sampling for the UniniTiated》阅读笔记结构:

  1.  参数估计方法及Gibbs Sampling简介
  2. 一个朴素贝叶斯文档模型例子
  3. 连续型参数求积分的思考

这篇是下篇,讨论中篇联合分布中对参数求积分来简化的问题。

之前存在的一个问题就是为啥我们可以对连续参数\(\pi\)求积分消去它,而不能对词分布\(\theta_0\)\(\theta_1\)求积分。这个主意看上去很美,但是实际做的时候,你会碰到一大把无法约掉的伽马函数。让我们看看具体的过程。

Read More

《Gibbs Sampling for the UniniTiated》阅读笔记(中)---一个朴素贝叶斯文档模型例子

《Gibbs Sampling for the UniniTiated》阅读笔记结构:

  1.  参数估计方法及Gibbs Sampling简介
  2. 一个朴素贝叶斯文档模型例子
  3. 连续型参数求积分的思考

这篇是中篇,介绍一个非常简单的朴素贝叶斯文档模型生成的例子,用来说明Gibbs Sampler具体是如何构造的。

文档生成的建模过程

首先我们有一批文档,文档里面有很多单词,这些单词都是无顺序可交换的(词袋模型),这些文档分成两类,类标签为0或者1。给予一篇未标记的文档\(W_j\),我们要做的工作就是预测文档的类标签是\(L_j=0\)还是\(L_j=1\)。为了方便起见,我们定了类标签所表示的类\(\mathbb{C}_0={W_j|L_j=0}\)\(\mathbb{C}_1={W_j|L_j=1}\)。一般来说预测这种事都是选择最有可能发生的,即找到\(W_j\)的后验概率\(P(L_j|W_j)\)最大的标签\(L_j\)。使用贝叶斯公式 \[\begin{equation} \begin{split} L_j=\arg \max \limits_{L}P(L|W_j)& =\arg \max \limits_{L}\frac{P(W_j|L)P(L)}{P(W_j)}\\& =\arg \max \limits_{L} P(W_j|L)P(L) \\\end{split} \end{equation}\] 因为分母\(P(W_j)\)\(L\)无关所以删去了。 通过贝叶斯公式的转换,我们可以想象这些文档的生成过程。首先,我们选择文档的类标签\(L_j\);假设这个过程是通过投硬币完成的(正面概率为\(\pi=P(L_j=1)\) ),正式地来说,就是服从贝努利分布 \[\begin{equation}L_j \sim Bernoulli(\pi)\end{equation}\] 然后,对于文档上\(R_j\)个“词位”中的每一个,我们根据一个概率分布\(\theta\),随机独立地抽样一个词\(w_i\)。因为每个类生成词的\(\theta\)分布都不同,所以应该有\(\theta_1\)\(\theta_2\),具体地生成词的时候,我们根据文档的标签\(L_j\)来决定由哪个类来生成 \[\begin{equation} W_j \sim Multinomial(R_j,\theta_{L_j}) \end{equation}\]

Read More

《Gibbs Sampling for the UniniTiated》阅读笔记(上)---参数估计方法及Gibbs Sampling简介

前一阵子折腾的事儿太多,写了点东西都没有传上来,是我偷懒了- -,下不为例。

这篇文章基本上是来自于《Gibbs Sampling for the UniniTiated》,说是笔记其实和翻译也差不多了。

整个结构分为上中下三部分:

  1.  参数估计方法及Gibbs Sampling简介
  2. 一个朴素贝叶斯文档模型例子
  3. 连续型参数求积分的思考

这篇是上部分,介绍基础参数估计和Gibbs Sampling概念。

为什么求积分—参数估计方法

很多概率模型的算法并不需要使用积分,只要对概率求和就行了(比如隐马尔科夫链的Baum-Welch算法),那么什么时候用到求积分呢?—— 当为了获得概率密度估计的时候,比如说根据一句话前面部分的文本估计下一个词的概率,根据email的内容估计它是否是垃圾邮件的概率等等。为了估计概率密度,一般有MLE(最大似然估计),MAP(最大后验估计),bayesian estimation(贝叶斯估计)三种方法。

最大似然估计

这里举一个例子来讲最大似然估计。假设我们有一个硬币,它扔出正面的概率\(\pi\)不确定,我们扔了10次,结果为HHHHTTTTTT(H为正面,T为反面)。利用最大似然估计的话,很容易得到下一次为正面的概率为0.4,因为它估计的是使观察数据产生的概率最大的参数。 first

\(\chi=\{HHHHTTTTTT\}\)代表观察到的数据,\(y\)为下一次抛硬币可能的结果,估计公式如下: \[\begin{equation}\begin{split}\tilde{\pi}_{MLE} &=\arg \max \limits_{\pi}P(\chi|\pi) \\P(y|\chi) & \approx \int_{\pi} p(y|\tilde{\pi}_{MLE})P(\pi|\chi) d\pi = p(y|\tilde{\pi}_{MLE})\end{split}\end{equation}\]

Read More