edfward

MCMC,LDA,文本建模 (一)

很久没写 blog 了,PyMoTW 也没想好下一个对象,刚好最近读完一篇关于文本建模的科普「LDA数学八卦」,也做了很多的笔记(扫描到 Evernote 上了),这次就先聊聊它们吧。

先梳理一下做的笔记,大致结构与原文「LDA数学八卦」相仿,感兴趣的话请务必翻翻那篇文章:

  1. 讲的是 Gamma 函数的推导和 Beta 函数的引入
  2. 写了 Gamma 分布以及 Binomial 分布与 Poisson 分布的关系(略去了从 Binomial 到 Gamma 的推导因为涉及到了一个比较复杂的等式)
  3. 从一个例子入手着重讲了 Beta 分布。这部分强烈推荐看原文,魔鬼和骰子的故事讲的很生动
  4. Beta-Binomial 共轭,是前面例子的延伸,对理解之后的 Dirichlet-Multinomial 共轭和更后面的 LDA 建模有很大的帮助
  5. 推广到 D-M 共轭,同时介绍了这两个分布的参数估计
  6. 噔噔噔噔,进入 Markov Chain 部分~讲了 Markov Chain 的平稳分布收敛条件和一些性质,是后文 Markov Chain Monte Carlo 算法的基础
  7. MCMC。平稳分布的判定条件(detailed balance condition)、如何人工满足这个条件(α 接受概率的引入)以及以此为基础的 MCMC 采样算法(最简单的 Metropolis-Hastings 采样算法)。这部分难度比之前大了一些(个人感觉)
  8. M-H 算法衍生的大名鼎鼎的 Gibbs Sampling,以及从二维到高维的推广
  9. 进入文本建模部分。Unigram Model,涉及 D-M 共轭和参数估计
  10. PLSA (Probabilistic Latent Semantic Analysis) 简述
  11. 比 PLSA 更进一步(或者说更 Bayesian)的 LDA (Latent Dirichlet Allocation)。看了原文不下4,5遍才算是勉强理解。重点在于理解文档生成的方式以及 D-M 共轭是怎么出现的
  12. 有了模型之后利用 Gibbs Sampling 进行参数计算和文档统计,这部分数学稍重

可以发现1-5是概率知识的普及,6-8是 MCMC 的介绍,从9开始才是真正的文本建模部分。

之后两张纸是「漫谈 HMM:Forward-Backward Algorithm」以及「漫谈 HMM:Definition」(都来自目前在 MIT 的 pluskid 的博文,个人偶像之一)。HMM 经常忘,刚好笔记也不是太长就附在后面了。有兴趣的话可以看看原文再看看笔记,希望有帮助。

结果再唠叨几句。在实验室做事情花的时间也不少了,但是看 paper 始终会觉得这儿不懂那儿不懂,然后翻回之前提到这个算法的 paper 再重复这个过程。我觉得相比起在 paper 中间那么点儿地方去了解一个算法不如翻回最早提到该算法的 paper 或者是别人整理出来的科普,拿出纸笔去算去写,才能有更好的领悟吧。像刚刚结束的组会提到了 wordnet random walk,当时不明白为什么一定会 converge,后来翻了翻笔记发现它就是个典型的 Markov random walk,根据笔记 part 6 里提到的如果马氏链满足平稳分布收敛条件(非周期且各个状态连通),最终一定会收敛到平稳分布去;还提到了 explicit semantic analysis,如果了解了 PLSA 那么对 ESA 的理解就更没问题了。发现刚知道的知识在实际问题中可以如此应用的时候便觉得花这么些功夫还是值得的。

相关的文大概有:

「Gibbs sampler in various languages (revisited)」: 比较了各个语言的 Gibbs Sampler 的效率(当然 C 完胜,Python 在 PyPy 的帮助下只慢了三倍…)。值得关注的是一个典型的 Gibbs Sampler 是怎么写的(Python 只用了13行),功夫其实是花在对要采样的分布进行分析上的。由于本人微积分都还给老师了所以只好请准备考研的室友把那个分布的 conditional probability 算了一下,了不起的是那么复杂一个积分他居然还算对了…赞。

「如何生成随机数(上)」: Warning: 该文没有(下)…依然来自于刚刚提到的偶像 pluskid。浅显易懂的讲了随机数的生成:如何从 Uniform Distribution 产生的随机数映射到更复杂的分布,以及比较简单的一个采样算法 Inverse Transform Sampling Method,当然也少不了方便直观展示的 python 代码。虽然烂尾了但还是好评。

另外还想谈的一篇文由于要说的太多,下次再讲吧(里面遇到的问题想了好久最后还是通过洗了一个澡才解决的——讲真,洗澡永远是灵感之源)。

那么,下回再见。

PS: 顺便把自己觉得写得最好的一页贴出来…

对不起静态图都挂了哇哈哈。