LDA漫游指南.pdf

马晨()马晨()前言 I 前言前言 LDA 算法是主题模型领域非常著名的算法，值得深入研究应用，该算法也有很深刻的数学背景和技术启发。曾经有哲人说：万物皆数。我个人是个十分喜欢数学，喜欢算法，热爱技术的人，非常想从算法中寻找人工智能的永恒之道。我尤其记得 19 世纪的数学家赫尔曼.汉克尔说的好：就大多数学科而言，一代人摧毁的正是另一代人所建造的，而他们所建立的也必将被另一代人所破坏。只有数学不同，每一代人都是在旧的建筑物上加进新的一层。所以说，数学的价值还具有一种永世不灭的恒久性，其他学科的时尚潮流往往随着时代的变迁被人遗忘，那些旨在改变世界的理想，最终往往变成思想垃圾。而只有数学和算法与此不同。我们探究前人伟大的成果时，就能体会到奥利弗.亥维赛的精辟论说：“逻辑能够很有耐性，因为它是永恒的”。我在选择分析 Latent Dirichlet Allocation(LDA)这个算法课题时，我考虑了很多因素，首先，该算法是已经被学术界和工业界广泛接受的；其次，该算法能带来更多的新技术启示；最后,该算法能为您的工作，您的研究带来最具实用性的技术启发。LDA 算法恰好满足了这个条件。虽然网上已经有许多分析 LDA 算法的博客文章，但是网上的博文相对零散不成体系，读者阅读起来有较大困难，我的目标是不放弃任何一位读者，只要读者有恒心和毅力，就一定可以从这部作品中受益，为什么需要这本书，因其有独独特的价值特的价值：1.这部作品理论与实践并重:1.这部作品理论与实践并重:网上的同类文章非常零散，理论推导部分也缺乏关键细节关键细节，这部作品的每一条公式都由作者手把手为您推理（每一条公式都有详细的解释和备注），并且按照初学者的思路娓娓道来，从逻辑链条上打通算法的整个环节，让用户有醍醐灌顶的认识。并且在实践部分实践部分，作者以多年的工作实践经验为基础，精选精选了 6 个实现简单但又有巨大应用价值的 LDA 的应用方法，这些精选的应用方法将成为读者未来工作实践不可多得的资料。2.这部作品饱含了作者的独到见解：2.这部作品饱含了作者的独到见解：这部作品最大的特色是从理论分析开始就有包含着许多作者自己独到的理解和分析，从不同角度完美解释算法的整个流程。前言 II 3.读者可以在这部作品各取所需：3.读者可以在这部作品各取所需：有的工程师对于算法推导不是很感兴趣，这种情况下可以跳过前几章，直接从第 4 章读 LDA 算法怎么具体实现。如若未来有兴趣研究 LDA 的来龙去脉时，可以再来看前几章的理论推导部分。如果读者对大数据环境下的 LDA 感兴趣，包括怎么在 Hadoop、Spark 上实现 LDA 算法可以直接看第 5 章。4.这部作品首次将 LDA 引入大数据时代：4.这部作品首次将 LDA 引入大数据时代：大数据时代最大的特色就是信息爆炸，各种文本数据，用户生成（UGC）数据也变得非常庞大，网上查阅到的LDA 算法资料大部分都是不能应对大数据环境的，这部作品的第 5 章深入浅出地讲解了大数据环境下怎么实现并行化的 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 语言代码实现的一个详尽剖析，这个方法的来龙去脉都在这三个章节有所体现。本文是一个指南指引性质的作品，仍未完善完美，本书还有些地方可能仍有前言 III 疏漏，本人水平有限，如果大家发现纰漏，请及时联系人民邮电出版社修正。希望这部作品日臻完美。希望这部作品日臻完美。作者：马晨 2016.4.19 作者：马晨 2016.4.19 目录 IV 目录 第 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 rank10.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 目录 V 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 第一章 背景 1 第1章 背景 第1章 背景 LDA 算法使用的全部知识的渊源可以追溯到 18 世纪的欧拉，欧拉（Leonhard Euler，1707 年 4 月 15 日1783 年 9 月 18 日），瑞士数学家。欧拉一生贡献颇丰，1734 年，欧拉解决巴塞尔问题就立即出名了，巴塞尔问题就是问式(1-1)的值是多少。222211111lim(.)?12nnnn (1-1)(1-1)这个问题困扰了几个世纪的数学家，当时的数学家只知道该级数的值小于2，但不知道具体精确值，欧拉准确的推导出该式的值=2/6，欧拉的方法聪明而新颖，他创造性将有限多项式的观察推广到无穷级数，并假设相同的性质对于无穷级数也是成立的：24682222222211111.3!5!7!9!4916xxxxxxxx (1-2)(1-2)欧拉最后的发现是令人惊奇的，这个数字在于圆周率无关的场合中出现了，这足以说明数学之中、自然之中、冥冥之中存在着某些神秘的联系。虽然以现代数学的眼光来看，欧拉的证明还不严密。但作为第一个（富有创造性的）证明，欧拉的这个证明永远有着其宝贵的价值。欧拉的另一个发现就是发现了gamma 函数()()f xx，该函数后被广泛应用于概率论，这个函数也是本文的主角之一。第一章 背景 2 图图 1-1 EulerEuler 作为算法标题之一的 Dirichlet，wiki 一下，一个 19 世纪的人映入了我们的眼帘，Dirichlet（18051859）德国数学家，生与现德国 Duren（当时属法国），卒于哥廷根。他是解析数论的奠基者，也是现代函数观念的定义者。在本文中该数学家的主要贡献是 Dirichlet 分布。图图 1-2 Peter Gustav Lejeune Dirichlet 但是这还不是故事的全部，说到底 19 世纪的时候还没有发明计算机，LDA应该不是这哥们发明的，于是继续 search，最后查明英国剑桥大学的 David M.Blei 是最初 LDA 论文的作者。Blei 同学借用了 Dirichlet Distribution，而创造了 Latent Dirichlet Allocation。下面这张照片的 blei 以 PLSA（LDA 之前的另一个概率模型）为基础，加上第一章 背景 3 了贝叶斯先验，从而诞生了 LDA 算法，LDA 算法最初的论文使用的是变分 EM 方法训练（Variational Inference）。该方法较为复杂，而且最后训练出的 topic主题非全局最优分布，而是局部最优分布。后期发明了 Collapsed Gibbs Sampling 方法，推导和使用都较为简洁。Blei 及其 LDA 算法正式的介绍如下：图图 1-3 David Blei Latent Dirichlet Allocation 是 Blei 等人于 2003 年提出的基于概率模型的主题模型算法，LDA 是一种无监督机器学习技术，可以用来识别大规模文档集或语料库中的潜在隐藏的主题信息。该方法假设每个词是由背后的一个潜在隐藏的主题中抽取出来。对于语料库中的每篇文档，LDA 定义了如下生成过程（generative process）：1.对每