马晨(sharpstill@163.com)
前言
前言
LDA 算法是主题模型领域非常著名的算法,值得深入研究应用,该算法也有
很深刻的数学背景和技术启发。曾经有哲人说:万物皆数。我个人是个十分喜欢
数学,喜欢算法,热爱技术的人,非常想从算法中寻找人工智能的永恒之道。我
尤其记得 19 世纪的数学家赫尔曼.汉克尔说的好:
就大多数学科而言,一代人摧毁的正是另一代人所建造的,而他们所建立的
也必将被另一代人所破坏。只有数学不同,每一代人都是在旧的建筑物上加进新
的一层。
所以说,数学的价值还具有一种永世不灭的恒久性,其他学科的时尚潮流往
往随着时代的变迁被人遗忘,那些旨在改变世界的理想,最终往往变成思想垃
圾。而只有数学和算法与此不同。
我们探究前人伟大的成果时,就能体会到奥利弗.亥维赛的精辟论说:“逻辑
能够很有耐性,因为它是永恒的”。
我在选择分析 Latent Dirichlet Allocation(LDA)这个算法课题时,我考
虑了很多因素,首先,该算法是已经被学术界和工业界广泛接受的;其次,该算
法能带来更多的新技术启示;最后,该算法能为您的工作,您的研究带来最具实
用性的技术启发。
LDA 算法恰好满足了这个条件。
虽然网上已经有许多分析 LDA 算法的博客文章,但是网上的博文相对零散不
成体系,读者阅读起来有较大困难,我的目标是不放弃任何一位读者,只要读者
有恒心和毅力,就一定可以从这部作品中受益,为什么需要这本书,因其有独
特的价值:
1.这部作品理论与实践并重:网上的同类文章非常零散,理论推导部分也缺
乏关键细节,这部作品的每一条公式都由作者手把手为您推理(每一条公式都
有详细的解释和备注),并且按照初学者的思路娓娓道来,从逻辑链条上打通算
法的整个环节,让用户有醍醐灌顶的认识。并且在实践部分,作者以多年的工
作实践经验为基础,精选了 6 个实现简单但又有巨大应用价值的 LDA 的应用方
法,这些精选的应用方法将成为读者未来工作实践不可多得的资料。
2. 这部作品饱含了作者的独到见解:这部作品最大的特色是从理论分析开
始就有包含着许多作者自己独到的理解和分析,从不同角度完美解释算法的整个
流程。
I
前言
3. 读者可以在这部作品各取所需:有的工程师对于算法推导不是很感兴
趣,这种情况下可以跳过前几章,直接从第 4 章读 LDA 算法怎么具体实现。如若
未来有兴趣研究 LDA 的来龙去脉时,可以再来看前几章的理论推导部分。如果读
者对大数据环境下的 LDA 感兴趣,包括怎么在 Hadoop、Spark 上实现 LDA 算法可
以直接看第 5 章。
4. 这部作品首次将 LDA 引入大数据时代:大数据时代最大的特色就是信息
爆炸,各种文本数据,用户生成(UGC)数据也变得非常庞大,网上查阅到的
LDA 算法资料大部分都是不能应对大数据环境的,这部作品的第 5 章深入浅出地
讲解了大数据环境下怎么实现并行化的 LDA 算法。
5. 这部作品是国内关于 LDA 的变分推断技术讲解最细致的书。
章节安排:
第 1 章为相关背景介绍,介绍了算法知识的来源:从 18 世纪的欧拉讲到剑
桥大学的 David Blei。
第 2 章和第 3 章为算法的理论分析阶段:第 2 章为 LDA 算法的前置知识,为
LDA 做了理论工具上的准备。
在第 2 章力求做到关键证明不遗漏,这样就可以与后面第 3 章的 LDA 的算法
推导构成一个完整的推理链条!这一章的有些证明需要一些简单的微积分知识,
但如果读者忘记了所有基础的微积分知识的话,那么看不懂某条证明,就请姑且
相信我的推理是对的吧,跳过去往后看,日后再复习。
第 3 章为 LDA 算法推导部分,用严谨的数学推导和清晰的讲解(每个公式都
做了清晰的标注),让读者认识该推理方法。
第 4 章为实现和应用部分,用伪代码方式庖丁解牛,讲解代码实现的精髓,
然后结合作者多年的工作实践,写了该算法的几个最具实用价值的应用,这些应
用方法中有相当一部分是作者的亲身工作经验的总结,在任何其他书籍上找不
到。
第 5 章为并行化,在大数据如火如荼的今天,要想大规模运行 LDA 算法,就
要靠并行化技术了,这一章从 2 个算法的改进形式讲解了该技术的并行化,并且
可以放在目前最流行的 spark 大数据引擎上运行。
第 6 章,第 7 章,第 8 章三个章节为 LDA 的变分 EM 技术的详细推导和 C 语
言代码实现的一个详尽剖析,这个方法的来龙去脉都在这三个章节有所体现。
本文是一个指南指引性质的作品,仍未完善完美,本书还有些地方可能仍有
II
前言
疏漏,本人水平有限,如果大家发现纰漏,请及时联系人民邮电出版社修正。
希望这部作品日臻完美。
作者:马晨 2016.4.19
III
目录
目录
第 1 章 背景 ...................................................................................................................1
第 2 章 前置知识 ...........................................................................................................5
2.1 gamma 函数 ......................................................................................................5
2.2 二项分布(binomial distribution) ......................................................................6
2.3 beta 分布(beta distribution) ..............................................................................7
2.4 多项分布(multinomial distribution) ..............................................................10
2.5 狄利克雷分布(dirichlet distribution) .............................................................12
2.6 共轭先验分布(conjugacy prior) .....................................................................13
2.6.1 从二项分布到 beta 分布 ....................................................................14
2.6.2 从多项分布到 Dirichlet 分布 .............................................................16
2.7 总结 ................................................................................................................18
参考文献 ...............................................................................................................18
第 3 章 LDA 的 Gibbs Sampling 推导 ...........................................................................19
3.1 unigram 假设 ...................................................................................................19
3.2 Latent Dirichlet Allocation 介绍 ......................................................................21
3.3 马尔可夫链 Metropolis-Hasting Gibbs Sampling ................................25
3.3.1 马尔可夫链(markov chain) .................................................................25
3.3.2 Metropolis-Hasting 算法 ......................................................................27
3.3.3 Gibbs Sampling .....................................................................................29
3.4 伟大的采样公式: Collapsed Gibbs Sampling 采样公式推导 ....................30
3.5 总结 ................................................................................................................36
参考文献 ...............................................................................................................36
第 4 章 实现与应用 .....................................................................................................38
4.1 实现 ................................................................................................................38
4.2 应用 ................................................................................................................45
4.2.1 相似文档发现 .....................................................................................45
4.2.2 自动打标签 .........................................................................................47
4.2.3 LDA 与 LR(逻辑斯蒂回归)结合做新闻个性化推荐系统 ..............48
4.2.4 topic rank[10] ..........................................................................................50
4.2.5 word rank ..............................................................................................52
4.2.6 文章质量评分算法 .............................................................................55
4.2.7 总结 .....................................................................................................59
参考文献 ...............................................................................................................59
第 5 章 并行化 .............................................................................................................61
5.1 AD-LDA .............................................................................................................61
5.2 spark-LDA .........................................................................................................63
5.2.1 切分块 .................................................................................................63
5.2.2 选择 .....................................................................................................65
5.2.3 计算和合并 .........................................................................................66
5.2.4 总结 .....................................................................................................67
参考文献 ...............................................................................................................67
第 6 章 变分贝叶斯的启蒙 .........................................................................................68
IV
目录
6.1 前置知识 ........................................................................................................68
6.1.1 指数分布族(exponential family) .........................................................68
6.1.2 再谈数学期望 .....................................................................................70
6.1.3 进一步观察指数分布族 .....................................................................74
6.1.4 拉格朗日的杰作——拉格朗日乘数法 ..............................................76
6.1.5 指数分布族的一点深入的思考 .........................................................78
6.1.6 Jensen 不等式 ......................................................................................80
6.2 补充材料:变分法的启蒙 ............................................................................82
6.2.1 改变世界的方程:欧拉-拉格朗日方程 ............................................83
6.2.2 E-L 方程的两种降阶形式 ....................................................................86
6.2.3 E-L 方程与拉格朗日乘数法的联姻 ....................................................87
参考文献 ...............................................................................................................93
第 7 章 LDA 的变分贝叶斯法 ......................................................................................94
7.1 Latent Dirichlet Allocation 的另一个视角 ......................................................94
7.2 分析模型 ........................................................................................................96
7.3 推导 ................................................................................................................99
7.3.1 启蒙 .....................................................................................................99
7.3.2 变分目标函数 .................................................................................. 101
7.3.3 下界(lower bound) ...................................................................... 102
7.3.4 下界展开 .......................................................................................... 104
7.3.5 变分推断 .......................................................................................... 106
7.3.6 参数估计 .......................................................................................... 109
7.4 误差讨论 ..................................................................................................... 111
参考文献 ............................................................................................................ 112
第 8 章 LDA 变分 EM 实现........................................................................................ 113
8.1 伪代码 ......................................................................................................... 113
8.2 工程优化分析 ............................................................................................. 115
8.3 Blei 的变分 LDA(C 语言版)源代码剖析 ................................................. 116
8.3.1 源代码下载 ...................................................................................... 116
8.3.2 使用命令与配置 .............................................................................. 117
8.3.3 源代码情况一览 .............................................................................. 118
8.3.4 Variational EM 代码剖析 ................................................................... 122
8.3.5 预测推断新文档 .............................................................................. 131
8.3.6 load model ......................................................................................... 132
8.3.7 运行效果与终止条件 ...................................................................... 132
值得进一步阅读的参考文献 .................................................................................... 136
V
第一章 背景
第1章 背景
LDA 算法使用的全部知识的渊源可以追溯到 18 世纪的欧拉,欧拉
(Leonhard Euler ,1707 年 4 月 15 日~1783 年 9 月 18 日),瑞士数学家。欧
拉一生贡献颇丰,1734 年,欧拉解决巴塞尔问题就立即出名了,巴塞尔问题就
是问式(1-1)的值是多少。
1
2
n n
1
1
lim (
2
1
n
1
2
2
...
1
2
n
)
?
(1-1)
这个问题困扰了几个世纪的数学家,当时的数学家只知道该级数的值小于
,欧拉的方法聪明
2,但不知道具体精确值,欧拉准确的推导出该式的值= 2 / 6
而新颖,他创造性将有限多项式的观察推广到无穷级数,并假设相同的性质对于
无穷级数也是成立的:
4
x
5!
6
x
7!
8
x
9!
2
x
3!
][1
][1
][1
(1-2)
1
2
x
16
2
]...
[1
2
x
2
2
x
2
4
2
x
2
9
欧拉最后的发现是令人惊奇的,这个数字在于圆周率无关的场合中出现
了,这足以说明数学之中、自然之中、冥冥之中存在着某些神秘的联系。虽然以
现代数学的眼光来看,欧拉的证明还不严密。但作为第一个(富有创造性的)证
明,欧拉的这个证明永远有着其宝贵的价值。欧拉的另一个发现就是发现了
gamma 函数
角之一。
x ,该函数后被广泛应用于概率论,这个函数也是本文的主
( )
f x
( )
1
第一章 背景
图 1-1 Euler
作为算法标题之一的 Dirichlet, wiki 一下,一个 19 世纪的人映入了我们
的眼帘,Dirichlet(1805~1859)德国数学家,生与现德国 Duren(当时属法
国),卒于哥廷根。他是解析数论的奠基者,也是现代函数观念的定义者。在本
文中该数学家的主要贡献是 Dirichlet 分布。
图 1-2 Peter Gustav Lejeune Dirichlet
但是这还不是故事的全部,说到底 19 世纪的时候还没有发明计算机,LDA
应该不是这哥们发明的,于是继续 search,最后查明英国剑桥大学的 David
M.Blei 是最初 LDA 论文的作者。Blei 同学借用了 Dirichlet Distribution,而
创造了 Latent Dirichlet Allocation。
下面这张照片的 blei 以 PLSA(LDA 之前的另一个概率模型)为基础,加上
2