LDAusingGibbsSampling

GibbsLDA++AC/C++ImplementationofLatentDirichletAllocation(LDA)usingGibbsSamplingforParameterEstimationandInference代码：D:\android-ndk-r6b-windows\android-ndk-r6b\projects\GibbsLDA++-0.2GibbsLDA++isusefulforthefollowingpotentialapplicationareas:1、InformationRetrieval(analyzingsemantic/latenttopic/conceptstructuresoflargetextcollectionforamoreintelligentinformationsearch.2、DocumentClassification/Clustering,DocumentSummarization(文本摘要),andText/WebDataMiningcommunityingeneral.3、CollaborativeFiltering(协同过滤)4、Content-basedImageClustering,ObjectRecognition,andotherapplicationsofComputerVision(计算机视觉)ingeneral.5、Otherpotentialapplicationsinbiologicaldata.使用吉布斯采样估计LDA参数在LDA最初提出的时候，人们使用EM（期望最大化算法）算法进行求解，后来人们普遍开始使用较为简单的GibbsSampling，具体过程如下：a.首先对所有文档中的所有词遍历一遍，为其都随机分配一个主题，即zm,n=k~Mult(1/K),其中m表示第m篇文档，n表示文档中的第n个词，k表示主题，K表示主题的总数，之后将对应的n(k)m+1,nm+1,n(t)k+1,nk+1,他们分别表示在m文档中k主题出现的次数(csy理解的应是在文档m中分配给主题k的词的个数)，m文档中主题数量的和，k主题对应的t词的次数，k主题对应的总词数。b.之后对下述操作进行重复迭代。c.对所有文档中的所有词进行遍历，假如当前文档m的词t对应主题为k，则n(k)m-1,nm-1,n(t)k-1,nk-1,即先拿出当前词，之后根据LDA中topicsample的概率分布sample出新的主题，在对应的n(k)m,nm,n(t)k,nk上分别+1。p(zi=k|z−i,w)∝(n(t)k,−i+βt)(n(k)m,−i+αk)/(∑Vt=1n(t)k,−i+βt)d.迭代完成后输出主题-词参数矩阵φ和文档-主题矩阵θϕk,t=(n(t)k+βt)/(nk+βt)θm,k=(n(k)m+αk)/(nm+αk)来源：隐含狄利克雷分布维基百科Gibbs抽样解LDA[csy]LDA参数推理采用的是Gibbs抽样1、Gibbs抽样：对P(z)，z是向量，按照Gibbs描述的步骤，可以抽取z(1),z(2),...z(n)这n个样本，Gibbs保证这n个样本的分布服从P(z)。z(0)=(z1,z2,...,zn)Repeatfori=1ton从p(zi|z1,z2,...,zi,zi+1,...,zn)中抽取zi得到z(t)=(z1,z2,...,zn)2、上面描述了一个一般的Gibbs抽样过程，假设重复N次，将得到z(1),z(2),...,z(N)个样本。抽样有一个收敛到目标分布的过程(burn-in)，假设需要a次，那么可以认为z(a),z(a+1),...,z(N)都是从P(z)中抽取出来的。Gibbs抽样中相邻两次得到的样本是相关的，因此通常每隔b次才抽样一次，来消除这种相关性。在实际中a和b通常采取预设置的方法比如几千设为a，几十或者几百设为b，因为二者没有很好的理论设置方法。3、假设通过Gibbs抽样我们得到了M个服从P(z)分布的样本，可以用来做什么？1）可以求期望：直接求样本平均即可2）可以求函数期望：将样本做相关的函数变换得到新的样本集，求平均即可3）直接利用样本本身，求相关的统计量这三种操作在P(z)本身比较复杂但是p(zi|z1,z2,...,zi,zi+1,...,zn)容易求解的时候十分有用。4、在LDA中我们关注三个参数z，theta和phi。其中z是语料中每一个word对应的隐变量（主题），theta是语料中每一个文档的主题分布，phi是每一个主题的term分布。其实只要求得z，其他两个可以通过简单的似然估计得到。于是需要将LDA的概率公式P(w,z,theta,phi|alpha,beta)通过积分的方法把theta和phi积掉，剩下P(w,z|alpha,beta)。然后求解P(z|w,alpha,beta)=P(w,z|alpha,beta)/P(w|alpha,beta)，由于分母要对K的n次方个项求和因此直接求不可行（其中K是主题数，n是词汇表的长度）。Gibbs抽样就是要完成对P(z|w,alpha,beta)的抽样，利用抽样结果通过简单的似然估计求得theta和phi。来源：Gibbs抽样解LDA_superbear_新浪博客用GibbsSampling学习LDAGibbsSampling是Markov-ChainMonteCarlo算法的一个特例。这个算法的运行方式是每次选取概率向量的一个维度，给定其他维度的变量值Sample当前维度的值。不断迭代，直到收敛输出待估计的参数。可以图示如下：初始时随机给文本中的每个单词分配主题,然后统计每个主题z下出现termt的数量以及每个文档m下出现主题z中的词的数量，每一轮计算，即排除当前词的主题分配，根据其他所有词的主题分配估计当前词分配各个主题的概率。当得到当前词属于所有主题z的概率分布后，根据这个概率分布为该词sample一个新的主题。然后用同样的方法不断更新下一个词的主题，直到发现每个文档下Topic分布和每个Topic下词的分布收敛，算法停止，输出待估计的参数和，最终每个单词的主题也同时得出。实际应用中会设置最大迭代次数。每一次计算的公式称为Gibbsupdatingrule注：是先拿出当前词,计算文档m中第n个词的新主题(因为初始随机分配一个主题)的公式。LDA建模LDA是一种生成式的主题模型，能够对文本集合进行建模，从而得到文本与特征之间隐含的关系，它可以随机生成一篇由所有的隐含主题组成的文章。[有人做过模拟实验，使用12个topic按照LDA生成模型随机生成几百万篇文档，然后使用LDA训练模型，几十个迭代之后，模型几乎完美收敛到原始的12个topic.]LDA模型采用词袋（bagofword,BOW）的方法，认为文本就是一个词语构成的集合，从而将每个文本看作一个向量的形式，将非结构化的文本信息转化为易于建模的结构化信息。LDA模型是三层贝叶斯模型，由词（word）、文本（document）、主题（topic）组成。词是描述非结构化数据的基本单位；文本可以看作N个词的序列，记为d=（w1,w2...wN）,其中wi表示第i个词；主题的数为K，且主题之间相互独立；整个语料库是M个文本的集合，记为D=(d1,d2...dM)。对于语料库中的每篇文档，LDA定义了如下生成过程（generativeprocess）：1.对每一篇文档，从主题分布中抽取一个主题；2.从上述被抽到的主题所对应的单词分布中抽取一个单词；3.重复上述过程直至遍历文档中的每一个单词。1、数据预处理将初始的文本集处理成词的集合，即d=(w1,w2...wN),其中N为文本d中词的个数。对数据集进行分词，即可将文本集在形式上变为如上格式。进一步去除停用词，再根据建模的目的，去除可能会造成干扰的词，比如基于主题的，希望选出的特征能够很好的反应文本描述的对象，容易想到，除名词之外，其他的词起不到这样的作用；比如基于观点的，只有观点词才能够对作者观点起到描述作用，介词、代词没有识别作用；2、建模过程LDA建模是将每篇文本看作K个主题的一个混合，更形式化的说，对于文本集中的每篇文本，与K（假设为已知的）个主题的一个这样的多项分布相对应，将该分布记为ϑ(即thetaθit西塔)，每个主题又与词表中V个词的一个多项分布对应，该分布记为ϕ(即phifai佛爱)。ϑ是一个带有超参数α(即alphaa:lf阿尔法）的Dirichlet先验分布，ϕ是带有β（即betabet贝塔）的Dirichlet先验分布。3、实现工具见“GibbsLDA++”，是一个c++版本的使用Gibbssampling的LDA实现。应用领域见章节”applicationareas”的介绍。GibbsSampling学习LDA参数的算法伪代码如下:Gibbsupdatingrule:Multinomial分布的参数和的计算公式如下:解释：ϕk,t表示的是：topic-worddistributions(phifai佛爱)ϑm,k表示的是：document-topicdistributions(thetaθit西塔)ϕk,t主题-词分布ϑm,k文档-主题分布，超参数nk(t)分配给主题k的词t的词数nk分配给主题k的词数nm(k)文本m中分配给主题k的词数nm文本m中所有的词数V词的总数K主题的总数3.1输入：数据输入格式统一如下，[M][document1][document2]...[documentM]第一行的M表示文本集中文本的总数.下面的每一行记录就是一个文本（这里的文本不是初始的文本）.文本格式如下：[documenti]=[wordi1][wordi2]...[wordiNi]其中[documenti]是第i个文本，包含可Ni个词/术语的数据集。即每篇文章占一行，对于英文来说，每个词之间已经用空格分开了，但是中文不行，所以你要先对文章进行分词。3.2输出：模型建立以后，会输出5个分别以others,phi,theta,tassign,twords为后缀名的文件，每个文件的含义如下(按照pdf手册)：1）others:文件保存的是与LDA模型有关的参数alpha=?#αbeta=?#βntopics=?#numberoftopicsndocs=?#numberofdocumentsnwords=?#thevocabularysizeliter=?#theGibbssamplingiterationatwhichthemodelwassaved2）phi：文件存储的是”词-主题”的概率分布（即主题数×词数量的矩阵），每一行是主题，每一列是词，元素值为p(wordw|topict)即分配给主题t的词w的概率（即某一主题选择词的概率）。注-csy：源码中计算phi，从源码注释中得知是”主题-词”的概率分布；但看phi文件的行数确实是主题的总数(ntopics)；所以是按照pdf而不是代码注释的，应是”词-主题”3）theta:文件存储的是”主题-文本”的概率分布（即文档数×主题数的矩阵），每一行是文本，每一列是主题，元素值为p(topict|documentm)即文档m中分配到主题t的概率（即每一个值都表示该文档选择了对应主题的概率）。注-csy：源码中计算theta，从源码注释中得知是”文本-主题”的概率分布；但看theta文件的行数确实是文本的总数(ndocs)；所以是按照pdf而不是代码注释的，应是”主题-文本”4）tassign:文件保存的是训练样本数据的词对应的主题映射，每一行是一个文本，存储一个集合wordij:topicofwordij即文本i中第j个词(其实是id，见wordmap.txt)：该词对应的主题，表示的是记录词项指派了其最大可能的所属类簇(csy-类簇是指主题吗？topic的范围是[0,K-1],K为主题数)。注-csy：出现过0:0（词的id为0）；6:0(词的id为6，但对应的主题