lda算法实现

㈠ LDA的公式推导

根据符号说明可得类i的样本均值为：
同理我们也可以得到总体样本均值：

根据类间离散度矩阵和类内离散度矩阵定义，可以得到如下式子：


当然还有另一中类间的离散度矩阵表达方式：

其中是指i类样本的先验概率，即样本中属于i类的概率，把P(i)代入第二组式子中，我们可以发现第一组式子只是比第二组式子都少乘了1/m，我们将在稍后进行讨论，其实对于乘不乘该1/m，对于算法本身并没有影响，我们分析一下算法的思想，
我们可以知道矩阵的实际意义是一个协方差矩阵，这个矩阵所刻画的是该类与样本总体之间的关系，其中该矩阵对角线上的函数所代表的是该类相对样本总体的方差（即分散度），而非对角线上的元素所代表是该类样本总体均值的协方差（即该类和总体样本的相关联度或称冗余度），所以根据公式（3）可知（3）式即把所有样本中各个样本根据自己所属的类计算出样本与总体的协方差矩阵的总和，这从宏观上描述了所有类和总体之间的离散冗余程度。同理可以的得出（4）式中为分类内各个样本和所属类之间的协方差矩阵之和，它所刻画的是从总体来看类内各个样本与类之间（这里所刻画的类特性是由是类内各个样本的平均值矩阵构成）离散度，其实从中可以看出不管是类内的样本期望矩阵还是总体样本期望矩阵，它们都只是充当一个媒介作用，不管是类内还是类间离散度矩阵都是从宏观上刻画出类与类之间的样本的离散度和类内样本和样本之间的离散度。
LDA做为一个分类的算法，我们当然希望它所分的类之间耦合度低，类内的聚合度高，即类内离散度矩阵的中的数值要小，而类间离散度矩阵中的数值要大，这样的分类的效果才好。
这里我们引入Fisher鉴别准则表达式：

㈡ NLP系列（三）LDA主题模型

LDA模型是NLP中很基础也是大家广为熟知的模型，在面试过程也经常遇到。本文简单讲述下其大致流程。

首先，我们来感受下LDA是什么，

看来，不同人在不同场景下对LDA的认识，那我们看下网络的解释：

看到这里我们只需要先记住： LDA的目的就是要识别主题，即把文档—词汇矩阵变成文档—主题矩阵（分布）和主题—词汇矩阵（分布）

对于语料库中的每篇文档，LDA定义了如下生成过程（generativeprocess）：
1.对每一篇文档，从主题分布中抽取一个主题；
2.从上述被抽到的主题所对应的单词分布中抽取一个单词；
3.重复上述过程直至遍历文档中的每一个单词。

语料库中的每一篇文档与T（通过反复试验等方法事先给定）个主题的一个多项分布 （multinomialdistribution）相对应，将该多项分布记为θ。每个主题又与词汇表（vocabulary）中的V个单词的一个多项分布相对应，将这个多项分布记为φ。

LDA的核心公式如下：
p(w|d)=p(w|t)*p(t|d)
直观的看这个公式，就是以Topic作为中间层，可以通过当前的θd和φt给出了文档d中出现单词w的概率。其中p(t|d)利用θd计算得到，p(w|t)利用φt计算得到。
实际上，利用当前的θd和φt，我们可以为一个文档中的一个单词计算它对应任意一个Topic时的p(w|d)，然后根据这些结果来更新这个词应该对应的topic。然后，如果这个更新改变了这个单词所对应的Topic，就会反过来影响θd和φt。

LDA算法开始时，先随机地给θd和φt赋值（对所有的d和t）。然后上述过程不断重复，最终收敛到的结果就是LDA的输出。再详细说一下这个迭代的学习过程：
1.针对一个特定的文档ds中的第i单词wi，如果令该单词对应的topic为tj，可以把上述公式改写为：
pj(wi|ds)=p(wi|tj)*p(tj|ds)
2.现在我们可以枚举T中的topic，得到所有的pj(wi|ds)，其中j取值1~k。然后可以根据这些概率值结果为ds中的第i个单词wi选择一个topic。最简单的想法是取令pj(wi|ds)最大的tj（注意，这个式子里只有j是变量），即argmax[j]pj(wi|ds)
3.然后，如果ds中的第i个单词wi在这里选择了一个与原先不同的topic，就会对θd和φt有影响了（根据前面提到过的这两个向量的计算公式可以很容易知道）。它们的影响又会反过来影响对上面提到的p(w|d)的计算。对D中所有的d中的所有w进行一次p(w|d)的计算并重新选择topic看作一次迭代。这样进行n次循环迭代之后，就会收敛到LDA所需要的结果了。

N个文档组成的语料库（𝐷 1，𝐷 2，"……" ，𝐷 𝑛），由V个词组成的词汇表。矩阵中的值表示了词𝑊𝑗 〖在文档𝐷〗 𝑖 中出现的频率，主题用Z表示，下面对语料库中的每一个word随机指派一个主题编号𝑍 𝑖，统计每个𝑍_𝑖下出现的word次数，可得一个主题—词汇矩阵。

统计每个词代表的主题在每一个文档中出现的次数，可得出以下矩阵文档—主题矩阵

以上讲了大致LDA的感性认识，如果进行严格的数学推导请看这篇文章( https://www.jianshu.com/p/74ec7d5f6821 )，本人认为是看到的不错的文章。

LDA对自己一直是一个谜，看了网上的很多资料，然后整理了几篇不错的，我在这里贴出来。本篇文章主要大致了解了下LDA的大致流程，如果真正搞懂其背后数学原理，还得反复看一下下面的文章：

LDA（LDA文档主题生成模型）_网络

㈢ 无监督第五节：LDA (Latent Dirichlet Allocation算法细节)（主题模型）

LDA是生成式概率模型。基本的观点是一个文档由多个隐主题生成，每个主题是由单词的分布式表达。

LDA假设在语料库D中每个文档的生成过程如下：

1.主题数量k已知

2.单词的概率由参数 控制

参数 是一个k 维的向量，并且每个元素大于0， 服从Gamma 分布

已知参数 ， 联合分布主题混合的参数 , 表示主题的参数 z,表示文档的参数w:

对 积分，并对z求和得到关于文档的边缘分布：

所有文档的边缘分布相乘，得到整个语料库的概率：

参数 和参数 是语料库级别的参数，在生成语料库的过程中使用。

变量 是文档级别的参数，每个文档采样一次。

变量 和 是单词级别的参数，每个文档中每个单词都采样一次.

一组随机变量如果联合分布和变量的排列顺序无关，则称这组变量是可交换的。

在LDA中，我们假设单词是由主题生成的，并且这些主题在文档中是无限可交换的，

其中 是关于主题多项式分布的随机变量。

通过对隐主题变量z积分。可以得到单词分布：

这是一个随机量，因为他依赖于

我们定义接下来的生成过程， 对于一个文档 w

1.选择θ∼Dir(α)

2.对于每个N的单词 :

(a)从 中选择一个单词

这个过程定义一篇文档的边缘分布看成一个连续的混合分布

inference的关心的问题使用LDA来计算隐变量z的后验分布：

这个分布通常很难计算。通过normaliza 分布，并且计算边缘分布。

这个后验分布很难计算，但是通过一些变分推断的方法还是可以得到。

基本的观点是使用jensen's 不等式来获得一个调整的下界，变分参数通过优化过程来试图找到最接近的可能的下界。

一个简单的方式是通过鲜花原始的计算图，将一些边和节点移去。在LDA中，原始的图是左图，通过把 移去，生成右边含有自由变分参数的图。
新的计算图使用如下变分分布：

是狄利克雷参数，多项式参数(φ1 , . . . , φ N ) 是自由变量参数。

得到简化的概率分布后，下一步是开始的优化问题是决定变分参数 的值。

优化这个变分参数是通过最小化KL散度来实现，并且吧他们设为0，得到以下的更新参数。

在文本的语言中，优化参数 是文档制定的。特别的，我们认为狄利克雷参数 是一个文档的主题表达。

经验贝叶斯方法来估计LDA中的参数。给定一个语料D，我们希望找到参数 来最大化边缘似然概率：

计算 比较困难，可以通过变分EM算法来估计。

1.E step,对于每个文档，找到最优的变分参数 。

2.M step, 最大化结果的下界。

重复上述几步直到下界收敛。

㈣ 降维算法二：LDA（Linear Discriminant Analysis）

学习分类算法，线性分类器最简单的就是LDA，它可以看做是简化版的SVM，如果想理解SVM这种分类器，那理解LDA就是很有必要的了。

谈到LDA，就不得不谈谈PCA，PCA是一个和LDA非常相关的算法，从推导、求解、到算法最终的结果，都有着相当的相似。

本次的内容主要是以推导数学公式为主，都是从算法的物理意义出发，然后一步一步最终推导到最终的式子，LDA和PCA最终的表现都是解一个矩阵特征值的问题，但是理解了如何推导，才能更深刻的理解其中的含义。本次内容要求读者有一些基本的线性代数基础，比如说特征值、特征向量的概念，空间投影，点乘等的一些基本知识等。除此之外的其他公式、我都尽量讲得更简单清楚。

LDA的全称是Linear Discriminant Analysis（线性判别分析），是一种 supervised learning 。有些资料上也称为是Fisher’s Linear Discriminant，因为它被Ronald Fisher发明自1936年，Discriminant这次词我个人的理解是，一个模型，不需要去通过概率的方法来训练、预测数据，比如说各种贝叶斯方法，就需要获取数据的先验、后验概率等等。LDA是在 目前机器学习、数据挖掘领域经典且热门的一个算法 ，据我所知，网络的商务搜索部里面就用了不少这方面的算法。

LDA的原理是，将带上标签的数据（点），通过投影的方法，投影到维度更低的空间中，使得投影后的点，会形成按类别区分，一簇一簇的情况，相同类别的点，将会在投影后的空间中更接近。要说明白LDA，首先得弄明白线性分类器( Linear Classifier )：因为LDA是一种线性分类器。对于K-分类的一个分类问题，会有K个线性函数：

上式实际上就是一种投影，是将一个高维的点投影到一条高维的直线上，LDA最求的目标是，给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开，当k=2即二分类问题的时候，如下图所示：

红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了，这个数据只是随便画的，如果在高维的情况下，看起来会更好一点。下面我来推导一下二分类LDA问题的公式：
假设用来区分二分类的直线（投影函数)为：

LDA分类的一个目标是使得不同类别之间的距离越远越好，同一类别之中的距离越近越好，所以我们需要定义几个关键的值。
类别i的原始中心点为：（Di表示属于类别i的点)

类别i投影后的中心点为：

衡量类别i投影后，类别点之间的分散程度（方差）为：

最终我们可以得到一个下面的公式，表示LDA投影到w后的损失函数：

分类的目标是， 使得类别内的点距离越近越好（集中），类别间的点越远越好。 分母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化J(w)就可以求出最优的w了。想要求出最优的w，可以使用拉格朗日乘子法，但是现在我们得到的J(w)里面，w是不能被单独提出来的，我们就得想办法将w单独提出来。
我们定义一个投影前的各类别分散程度的矩阵，这个矩阵看起来有一点麻烦，其实意思是，如果某一个分类的输入点集Di里面的点距离这个分类的中心店mi越近，则Si里面元素的值就越小，如果分类的点都紧紧地围绕着mi，则Si里面的元素值越更接近0.

同样的将J(w)分子化为：

我们希望 分母越小越好，分子越大越好 ：
分母小，则每个类内部数据点比较聚集；
分子大，则两个类别的距离较远。
所以需要找出一个 W 使 J(W) 的值最大。

这样就可以用最喜欢的拉格朗日乘子法了，但是还有一个问题，如果分子、分母是都可以取任意值的，那就会使得有无穷解，我们将分母限制为长度为1（这是用拉格朗日乘子法一个很重要的技巧，在下面将说的PCA里面也会用到，如果忘记了，请复习一下高数），并作为拉格朗日乘子法的限制条件，带入得到：

这样的式子就是一个求特征值的问题了。
对于N(N>2)分类的问题，我就直接写出下面的结论了：

二者都有降维的作用。