em算法java

1. mahout topic模型怎么使用

利用sqoop将数据从MySQL导入到HDFS中,利用mahout的LDA的cvb实现对输入数据进行聚类,并将结果更新到数据库中。数据流向图如下

mahout算法分析

输入数据格式
为<IntegerWritable, VectorWritable>的matrix矩阵,key为待聚类文本的数字编号，value为待聚类文本的单词向量Vector, Vector的index为单词在字典中的编号, value为TFIDF值。

算法相关参数详解(不包含hadoop运行参数)
项目中所有参数设置均与mahout-0.9目录下的examples/bin/cluster-reuters.sh的147-172行设置一样，即
$SCOUT cvb -i ${WORK_DIR}/${ROWID_MATRIX_DIR}/matrix -o ${WORK_DIR}/${LDA_DIR} -k 20 -ow -x 20 -dict ${WORK_DIR}/${DICTIONARY_FILES} -dt ${WORK_DIR}/${LDA_TOPICS_DIR} -mt ${WORK_DIR}/${LDA_MODEL_DIR}

input -- 输入数据的hdfs路径,这里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-out-matrix-debug/matrix
dt -- 文档主题输出路径,保存了每个文档的相应topic的概率,这里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-lda-topics
mt -- model的路径,这里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-lda-debug
k -- number of topics to learn,这里设置成20
x -- 模型迭代次数,也就是需要多少次迭代来生成最后的Model,默认值20
seed -- Random seed,生成初始readModel时的种子,默认值System.nanoTime() % 10000
dict -- 字典路径,这里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-out-seqdir-sparse-lda/dictionary.file-*
a -- Smoothing for document/topic distribution, document/topic分布的平滑系数,默认为1.0E-4
e -- Smoothing for topic/term distribution, topic/term分布的平滑系数,默认为1.0E-4
关于a和e,根据描述,a和e的合适取值为k/50(k为topic数量),但是这个网页还保留着mahout ldatopics的命令介绍,而mahout 0.8,0.9均没有该命令,推测应该是比较陈旧的内容,因此还是根据cluster-reuters.sh中的设置来，也就是采取默认值。
mipd -- 这个参数非常重要，对于每个文档程序是先用RandomSeed来生成一个初始的readModel然后进行mipd次迭代，算出最终的model进行更新，这里选默认值10次

LDA算法程序分析

算法的大致流程如下

1.解析参数与Configuration设置

2.读取Model(第一次运行时没有这个过程)
如果hfds上面已经有部分model，那么程序将读取最后一个model，并以这个model作为初始readModel来继续进行算法迭代，也就是说有类似于断电-重启的机制

3.运行算法迭代(Mapper过程)生成LDA模型
这个过程是最为复杂的阶段，许多地方我也不是很明白，我将尽最大努力进行解释
首先分析Mapper,即CachingCVB0Mapper,顾名思义就是能够缓存的Mapper，表现在其readModel的选取上面，如果目录里面不存在任何model则用RandomSeed初始化一个readModel，否则读取最近的一个model。程序将model划分为readModel和writeModel，这两个都是TopicModel类，并由ModelTrainer来进行调度和管理

CachingCVB0Mapper整个过程如下图所示(清晰大图见附件)

在上面这个整体框架下,mahout程序应用了CVB0 Algorithm来计算LDA模型, 在map过程中通过对向量docTopic和矩阵docTopicModel的反复迭代求解，算出每个document的docTopicModel并且在update writeModel阶段将docTopicModel矩阵进行向量的相加操作，经历完所有的map过程后得到整个corpus的docTopicModel矩阵，最终在cleanup过程中将topic的index作为key，矩阵docTopicModel作为value写入rece。该过程涉及到的算法如下所示

CVB0算法分析图解(清晰大图见附件)

4.利用生成的LDA模型推导出topic的概率分布

算法总结
可以看出算法本质上面就是bayes公式和EM算法的结合
E过程就是首先假定一个均匀分布且归一化的topic概率分布向量docTopics，利用该值通过贝叶斯公式算出单词 - 主题的概率分布矩阵 docTopicModel(见CVB0算法分析图解中的第一步)

M过程就是根据生成的docTopicModel进行CVB0算法分析图解中的2,3,4,5步重新计算得到新的docTopics

然后反复重复 E - M 过程n次，得到收敛后的docTopics和docTopicModel，其中docTopicModel可以用于lda模型的更新，而docTopics就是我们聚类需要的topic概率分布向量

算法后记
几点问题还没有得到解决
1.在mahout中是按照下面的式子计算docTopicModel的
double termTopicLikelihood =
(topicTermRow.get(termIndex) + eta) * (topicWeight + alpha)/ (topicSum + eta * numTerms);
疑问就是该式子比贝叶斯公式添加了几个平滑系数项，这样写的理论依据在哪里，来源于哪篇着作或者论文，平滑系数eta和alpha分别是代表什么含义，如何选取这两个系数。
2.CVB0算法分析图解中第2步进行归一化的理论依据，即为什么要进行归一化
3.update writeModel过程中对于topicTermCounts的计算
即为什么要在每次map时候对p(topic | term)进行累加，还没有完全想明白

项目运行环境
hadoop-1.2.1
sqoop-1.4.4
mahout-0.9
关于环境的安装部署请参考相关文章，这里不多加赘述。上面三个软件在我本机的都是部署在/home/hadoop-user/mahout_workspace/目录下。另外自己写的scout项目部署在/home/hadoop-user/scout_workspace/目录下

项目代码
项目代码已经放到Github上有兴趣的同学可以下载下来看下，重点查看bin目录下的脚本文件以及driver,export,analyzer等几个包下的java文件

整个项目架构分析
该项目的初始数据保存在MySQL中, 算法分析需要map/rece过程以及hdfs文件系统的参与, 最后将结果更新至MySQL,整个过程如图所示

2. WEB超链分析算法的WEB超链分析算法

搜索引擎Google最初是斯坦福大学的博士研究生Sergey Brin和Lawrence Page实现的一个原型系统[2]，现在已经发展成为WWW上最好的搜索引擎之一。Google的体系结构类似于传统的搜索引擎，它与传统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序处理，使最重要的网页出现在结果的最前面。Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在结果集中的出现位置，PageRank值越高的网页，在结果中出现的位置越前。
2.1.1PageRank算法
PageRank算法基于下面2个前提：
前提1：一个网页被多次引用，则它可能是很重要的；一个网页虽然没有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。这种重要的网页称为权威（Authoritive）网页。
前提2：假定用户一开始随机的访问网页集合中的一个网页，以后跟随网页的向外链接向前浏览网页，不回退浏览，浏览下一个网页的概率就是被浏览网页的PageRank值。
简单PageRank算法描述如下：u是一个网页，是u指向的网页集合，是指向u的网页集合，是u指向外的链接数，显然=| | ，c是一个用于规范化的因子（Google通常取0.85），（这种表示法也适用于以后介绍的算法）则u的Rank值计算如下：
这就是算法的形式化描述，也可以用矩阵来描述此算法，设A为一个方阵，行和列对应网页集的网页。如果网页i有指向网页j的一个链接，则，否则=0。设V是对应网页集的一个向量，有V=cAV，V为A的特征根为c的特征向量。实际上，只需要求出最大特征根的特征向量，就是网页集对应的最终PageRank值，这可以用迭代方法计算。
如果有2个相互指向的网页a，b,他们不指向其它任何网页，另外有某个网页c，指向a，b中的某一个，比如a，那么在迭代计算中，a，b的rank值不分布出去而不断的累计。如下图：
为了解决这个问题，Sergey Brin和Lawrence Page改进了算法，引入了衰退因子E(u)，E(U)是对应网页集的某一向量，对应rank的初始值，算法改进如下：
其中，=1，对应的矩阵形式为V’=c(AV’+E)。
另外还有一些特殊的链接，指向的网页没有向外的链接。PageRank计算时，把这种链接首先除去，等计算完以后再加入，这对原来计算出的网页的rank值影响是很小的。
Pagerank算法除了对搜索结果进行排序外，还可以应用到其它方面，如估算网络流量，向后链接的预测器，为用户导航等[2]。
2.1.2算法的一些问题
Google是结合文本的方法来实现PageRank算法的[2]，所以只返回包含查询项的网页，然后根据网页的rank值对搜索到的结果进行排序，把rank值最高的网页放置到最前面，但是如果最重要的网页不在结果网页集中，PageRank算法就无能为力了，比如在 Google中查询search engines，像Google，Yahoo，Altivisa等都是很重要的，但是Google返回的结果中这些网页并没有出现。 同样的查询例子也可以说明另外一个问题，Google，Yahoo是WWW上最受欢迎的网页，如果出现在查询项car的结果集中，一定会有很多网页指向它们，就会得到较高的rank值， 事实上他们与car不太相关。
在PageRank算法的基础上，其它的研究者提出了改进的PageRank算法。华盛顿大学计算机科学与工程系的Matthew Richardson和Pedro Dominggos提出了结合链接和内容信息的PageRank算法，去除了PageRank算法需要的前提2，增加考虑了用户从一个网页直接跳转到非直接相邻的但是内容相关的另外一个网页的情况[3]。斯坦大学计算机科学系Taher Haveliwala提出了主题敏感（Topic-sensitive）PageRank算法[4]。斯坦福大学计算机科学系Arvind Arasu等经过试验表明，PageRank算法计算效率还可以得到很大的提高[22]。 PageRank算法中对于向外链接的权值贡献是平均的，也就是不考虑不同链接的重要性。而WEB的链接具有以下特征：
1.有些链接具有注释性，也有些链接是起导航或广告作用。有注释性的链接才用于权威判断。
2.基于商业或竞争因素考虑，很少有WEB网页指向其竞争领域的权威网页。
3.权威网页很少具有显式的描述，比如Google主页不会明确给出WEB搜索引擎之类的描述信息。
可见平均的分布权值不符合链接的实际情况[17]。J. Kleinberg[5]提出的HITS算法中引入了另外一种网页，称为Hub网页，Hub网页是提供指向权威网页链接集合的WEB网页，它本身可能并不重要，或者说没有几个网页指向它，但是Hub网页确提供了指向就某个主题而言最为重要的站点的链接集合，比一个课程主页上的推荐参考文献列表。一般来说，好的Hub网页指向许多好的权威网页；好的权威网页是有许多好的Hub网页指向的WEB网页。这种Hub与Authoritive网页之间的相互加强关系，可用于权威网页的发现和WEB结构和资源的自动发现，这就是Hub/Authority方法的基本思想。
2.2.1HITS算法
HITS（Hyperlink－Inced Topic Search）算法是利用Hub/Authority方法的搜索方法，算法如下：将查询q提交给传统的基于关键字匹配的搜索引擎．搜索引擎返回很多网页，从中取前n个网页作为根集(root set)，用S表示。S满足如下3个条件：
1．S中网页数量相对较小
2．S中网页大多数是与查询q相关的网页
3．S中网页包含较多的权威网页。
通过向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T．
以T中的Hub网页为顶点集Vl，以权威网页为顶点集V2，Vl中的网页到V2中的网页的超链接为边集E，形成一个二分有向图SG=(V1，V2，E)。对V1中的任一个顶点v，用h(v)表示网页v的Hub值，对V2中的顶点u，用a(u)表示网页的Authority值。开始时h(v)=a(u)=1，对u执行I操作修改它的a(u)，对v执行O操作修改它的h(v)，然后规范化a（u），h（v），如此不断的重复计算下面的操作I，O，直到a（u），h（v）收敛。（证明此算法收敛可见）
I 操作： （1） O操作： （2）
每次迭代后需要对a(u),h(v)进行规范化处理：
式(1)反映了若一个网页由很多好的Hub指向，则其权威值会相应增加(即权威值增加为所有指向它的网页的现有Hub值之和)。式(2)反映了若一个网页指向许多好的权威页，则Hub值也会相应增加(即Hub值增加为该网页链接的所有网页的权威值之和)。
和PageRank算法一样，可以用矩阵形式来描述算法，这里省略不写。
HITS算法输出一组具有较大Hub值的网页和具有较大权威值的网页。
2.2.2HITS的问题
HITS算法有以下几个问题：
1．实际应用中，由S生成T的时间开销是很昂贵的，需要下载和分析S中每个网页包含的所有链接，并且排除重复的链接。一般T比S大很多，由T生成有向图也很耗时。需要分别计算网页的A/H值，计算量比PageRank算法大。
2．有些时候，一主机A上的很多文档可能指向另外一台主机B上的某个文档，这就增加了A上文档的Hub值和B上文档的Authority，相反的情况也如此。HITS是假定某一文档的权威值是由不同的单个组织或者个人决定的，上述情况影响了A和B上文档的Hub和Authority值[7]。
3．网页中一些无关的链接影响A，H值的计算。在制作网页的时候，有些开发工具会自动的在网页上加入一些链接，这些链接大多是与查询主题无关的。同一个站点内的链接目的是为用户提供导航帮助，也与查询主题不甚无关，还有一些商业广告，赞助商和用于友情交换的链接，也会降低HITS算法的精度[8]。
4．HITS算法只计算主特征向量，也就是只能发现T集合中的主社区（Community），忽略了其它重要的社区[12]。事实上，其它社区可能也非常重要。
5．HITS算法最大的弱点是处理不好主题漂移问题（topic drift）[7,8]，也就是紧密链接TKC（Tightly-Knit Community Effect）现象[8]。如果在集合T中有少数与查询主题无关的网页，但是他们是紧密链接的，HITS算法的结果可能就是这些网页，因为HITS只能发现主社区，从而偏离了原来的查询主题。下面讨论的SALSA算法中解决了TKC问题。
6．用HITS进行窄主题查询时，可能产生主题泛化问题[5,9]，即扩展以后引入了比原来主题更重要的新的主题，新的主题可能与原始查询无关。泛化的原因是因为网页中包含不同主题的向外链接，而且新主题的链接具有更加的重要性。
2.2.3HITS的变种
HITS算法遇到的问题，大多是因为HITS是纯粹的基于链接分析的算法，没有考虑文本内容，继J. Kleinberg提出HITS算法以后，很多研究者对HITS进行了改进，提出了许多HITS的变种算法，主要有：
2.2.3.1Monika R. Henzinger和Krishna Bharat对HITS的改进
对于上述提到的HITS遇到的第2个问题，Monika R. Henzinger和Krishna Bharat在[7]中进行了改进。假定主机A上有k个网页指向主机B上的某个文档d，则A上的k个文档对B的Authority贡献值总共为1,每个文档贡献1/k，而不是HITS中的每个文档贡献1，总共贡献k。类似的，对于Hub值，假定主机A上某个文档t指向主机B上的m个文档，则B上m个文档对t的Hub值总共贡献1，每个文档贡献1/m。I，O操作改为如下
I 操作：
O操作：
调整后的算法有效的解决了问题2，称之为imp算法。
在这基础上，Monika R. Henzinger和Krishna Bharat还引入了传统信息检索的内容分析技术来解决4和5，实际上也同时解决了问题3。具体方法如下，提取根集S中的每个文档的前1000个词语，串连起来作为查询主题Q，文档Dj和主题Q的相似度按如下公式计算：
，，=项i在查询Q中的出现次数，
=项i在文档Dj中的出现次数，IDFi是WWW上包含项i的文档数目的估计值。
在S扩展到T后，计算每个文档的主题相似度，根据不同的阈值（threshold）进行刷选，可以选择所有文档相似度的中值，根集文档相似度的中值，最大文档相似度的分数，如1/10，作为阈值。根据不同阈值进行处理，删除不满足条件的文档，再运行imp算法计算文档的A/H值，这些算法分别称为med，startmed，maxby10。
在此改进的算法中，计算文档的相似度时间开销会很大。
2.2.3.2ARC算法
IBM Almaden研究中心的Clever工程组提出了ARC（Automatic Resource Compilation）算法，对原始的HITS做了改进，赋予网页集对应的连结矩阵初值时结合了链接的锚（anchor）文本，适应了不同的链接具有不同的权值的情况。
ARC算法与HITS的不同主要有以下3点：
1．由根集S扩展为T时，HITS只扩展与根集中网页链接路径长度为1的网页，也就是只扩展直接与S相邻的网页，而ARC中把扩展的链接长度增加到2，扩展后的网页集称为增集（Augment Set）。
2．HITS算法中，每个链接对应的矩阵值设为1，实际上每个链接的重要性是不同的，ARC算法考虑了链接周围的文本来确定链接的重要性。考虑链接p－>q，p中有若干链接标记，文本1<a href=”q”>锚文本</a>文本2，设查询项t在文本1，锚文本，文本2，出现的次数为n（t），则w（p，q）=1+n（t）。文本1和文本2的长度经过试验设为50字节[10]。构造矩阵W，如果有网页i－>j ，Wi,j=w（i，j），否则Wi,j=0，H值设为1，Z为W的转置矩阵，迭代执行下面3个的操作：
（1）A=WH （2）H=ZA （3）规范化A，H
3．ARC算法的目标是找到前15个最重要的网页，只需要A/H的前15个值相对大小保持稳定即可，不需要A/H整个收敛，这样2中迭代次数很小就能满足，[10]中指出迭代5次就可以，所以ARC算法有很高的计算效率，开销主要是在扩展根集上。
2.2.3.3Hub平均（ Hub－Averaging－Kleinberg）算法
Allan Borodin等在[11]指出了一种现象，设有M+1个Hub网页，M+1个权威网页，前M个Hub指向第一个权威网页，第M+1个Hub网页指向了所有M+1个权威网页。显然根据HITS算法，第一个权威网页最重要，有最高的Authority值，这是我们希望的。但是，根据HITS，第M+1个Hub网页有最高的Hub值，事实上，第M+1个Hub网页既指向了权威值很高的第一个权威网页，同时也指向了其它权威值不高的网页，它的Hub值不应该比前M个网页的Hub值高。因此，Allan Borodin修改了HITS的O操作：
O操作： ，n是(v,u)的个数
调整以后，仅指向权威值高的网页的Hub值比既指向权威值高又指向权威值低的网页的Hub值高，此算法称为Hub平均（Hub－Averaging－Kleinberg）算法。
2.2.3.4阈值（Threshhold—Kleinberg）算法
Allan Borodin等在[11]中同时提出了3种阈值控制的算法，分别是Hub阈值算法，Authority阈值算法，以及结合2者的全阈值算法。
计算网页p的Authority时候，不考虑指向它的所有网页Hub值对它的贡献，只考虑Hub值超过平均值的网页的贡献，这就是Hub阈值方法。
Authority阈值算法和Hub阈值方法类似，不考虑所有p指向的网页的Authority对p的Hub值贡献，只计算前K个权威网页对它Hub值的贡献，这是基于算法的目标是查找最重要的K个权威网页的前提。
同时使用Authority阈值算法和Hub阈值方法的算法，就是全阈值算法 PageRank算法是基于用户随机的向前浏览网页的直觉知识，HITS算法考虑的是Authoritive网页和Hub网页之间的加强关系。实际应用中，用户大多数情况下是向前浏览网页，但是很多时候也会回退浏览网页。基于上述直觉知识，R. Lempel和S. Moran提出了SALSA（Stochastic Approach for Link-Structure Analysis）算法[8]，考虑了用户回退浏览网页的情况，保留了PageRank的随机漫游和HITS中把网页分为Authoritive和Hub的思想，取消了Authoritive和Hub之间的相互加强关系。
具体算法如下：
1．和HITS算法的第一步一样，得到根集并且扩展为网页集合T，并除去孤立节点。
2．从集合T构造无向图G’=（Vh，Va，E）
Vh = { sh | s∈C and out-degree(s) > 0 } ( G’的Hub边).
Va = { sa | s∈C and in-degree(s) > 0 } (G’的Authority边).
E= { (sh , ra) |s－>r in T}
这就定义了2条链，Authority链和Hub链。
3．定义2条马尔可夫链的变化矩阵，也是随机矩阵，分别是Hub矩阵H，Authority矩阵A。
4．求出矩阵H，A的主特征向量，就是对应的马尔可夫链的静态分布。
5．A中值大的对应的网页就是所要找的重要网页。
SALSA算法没有HITS中相互加强的迭代过程，计算量远小于HITS。SALSA算法只考虑直接相邻的网页对自身A/H的影响，而HITS是计算整个网页集合T对自身AH的影响。
实际应用中，SALSA在扩展根集时忽略了很多无关的链接，比如
1．同一站点内的链接，因为这些链接大多只起导航作用。
2．CGI 脚本链接。
3．广告和赞助商链接。
试验结果表明，对于单主题查询java，SALSA有比HITS更精确的结果，对于多主题查询abortion，HITS的结果集中于主题的某个方面，而SALSA算法的结果覆盖了多个方面，也就是说，对于TKC现象，SALSA算法比HITS算法有更高的健壮性。
2.3.1BFS（Backword Forward Step）算法
SALSA算法计算网页的Authority值时，只考虑网页在直接相邻网页集中的受欢迎程度，忽略其它网页对它的影响。HITS算法考虑的是整个图的结构，特别的，经过n步以后，网页i的Authority的权重是，为离开网页i的的路径的数目，也就是说网页j<>i，对i的权值贡献等于从i到j的路径的数量。如果从i到j包含有一个回路，那么j对i的贡献将会呈指数级增加，这并不是算法所希望的，因为回路可能不是与查询相关的。
因此，Allan Borodin等[11]提出了BFS（Backward Forward Step）算法，既是SALSA的扩展情况，也是HITS的限制情况。基本思想是，SALSA只考虑直接相邻网页的影响，BFS扩展到考虑路径长度为n的相邻网页的影响。在BFS中，被指定表示能通过路径到达i的结点的集合，这样j对i的贡献依赖就与j到i的距离。BFS采用指数级降低权值的方式，结点i的权值计算公式如下：
=|B(i)|+ |BF(i)| +|BFB(i)|+……+||
算法从结点i开始，第一步向后访问，然后继续向前或者向后访问邻居，每一步遇到新的结点加入权值计算，结点只有在第一次被访问时加入进去计算。 D.Cohn and H.Chang提出了计算Hub和Authority的统计算法PHITS（Probabilistic analogue of the HITS）[12]。他们提出了一个概率模型，在这个模型里面一个潜在的因子或者主题z影响了文档d到文档c的一个链接，他们进一步假定，给定因子z，文档c的条件分布P(c|z)存在，并且给定文档d，因子z的条件分布P（z|d）也存在。
P(d) P(z|d) P(c|z) ，其中
根据这些条件分布，提出了一个可能性函数（likelihood function）L,
，M是对应的连结矩阵
然后，PHITS算法使用Dempster等提出的EM算法[20]分配未知的条件概率使得L最大化，也就是最好的解释了网页之间的链接关系。算法要求因子z的数目事先给定。Allan Borodin指出，PHITS中使用的EM算法可能会收敛于局部的最大化，而不是真正的全局最大化[11]。D. Cohn和T. Hofmann还提出了结合文档内容和超链接的概率模型[13]。 Allan Borodin等提出了完全的贝叶斯统计方法来确定Hub和Authoritive网页[11]。假定有M个Hub网页和N个Authority网页，可以是相同的集合。每个Hub网页有一个未知的实数参数，表示拥有超链的一般趋势，一个未知的非负参数，表示拥有指向Authority网页的链接的趋势。每个Authoritive网页j，有一个未知的非负参数，表示j的Authority的级别。
统计模型如下，Hub网页i到Authority网页j的链接的先验概率如下给定：
P（i，j）=Exp（+）/（1+Exp（+））
Hub网页i到Authority网页j没有链接时，P（i，j）=1/（1+Exp（+））
从以上公式可以看出，如果很大（表示Hub网页i有很高的趋势指向任何一个网页），或者和都很大（表示i是个高质量Hub，j是个高质量的Authority网页），那么i－>j的链接的概率就比较大。
为了符合贝叶斯统计模型的规范，要给2M+N个未知参数（，，）指定先验分布，这些分布应该是一般化的，不提供信息的，不依赖于被观察数据的，对结果只能产生很小影响的。Allan Borodin等在中指定满足正太分布N（μ，）,均值μ=0，标准方差δ=10，指定和满足Exp（1）分布，即x>=0，P(>=x)=P(>=x)=Exp（－x）。
接下来就是标准的贝叶斯方法处理和HITS中求矩阵特征根的运算。
2.5.1简化的贝叶斯算法
Allan Borodin同时提出了简化的上述贝叶斯算法，完全除去了参数，也就不再需要正太分布的参数μ，δ了。计算公式变为：P（i，j）=/（1+），Hub网页到Authority网页j没有链接时，P（i，j）=1/(1+)。
Allan Borodin 指出简化的贝叶斯产生的效果与SALSA算法的结果非常类似。 上面的所有算法，都是从查询项或者主题出发，经过算法处理，得到结果网页。多伦多大学计算机系Alberto Mendelzon, Davood Rafiei提出了一种反向的算法，输入为某个网页的URL地址，输出为一组主题，网页在这些主题上有声望（repution）[16]。比如输入，www.gamelan.com，可能的输出结果是“java”，具体的系统可以访问htpp://www.cs.toronto.e/db/topic。
给定一个网页p，计算在主题t上的声望，首先定义2个参数，渗透率和聚焦率，简单起见，网页p包含主题项t，就认为p在主题t上。
是指向p而且包含t的网页数目，是指向p的网页数目，是包含t的网页数目。结合非条件概率，引入，，是WEB上网页的数目。P在t上的声望计算如下：
指定是既指向p有包含t的概率，即，显然有
我们可以从搜索引擎（如Altavista）的结果得到，, ,WEB上网页的总数估计值某些组织会经常公布，在计算中是个常量不影响RM的排序，RM最后如此计算：
给定网页p和主题t，RM可以如上计算，但是多数的情况的只给定网页p，需要提取主题后计算。算法的目标是找到一组t，使得RM（p，t）有较大的值。TOPIC系统中是抽取指向p的网页中的锚文本的单词作为主题（上面已经讨论过锚文本能很好描述目标网页，精度很高），避免了下载所有指向p的网页，而且RM（p，t）的计算很简单，算法的效率较高。主题抽取时，还忽略了用于导航、重复的链接的文本，同时也过滤了停止字（stop word），如“a”，“the”，“for”，“in”等。
Reputation算法也是基于随机漫游模型的（random walk），可以说是PageRank和SALSA算法的结合体。
3.链接算法的分类及其评价
链接分析算法可以用来提高搜索引擎的查询效果，可以发现WWW上的重要的社区，可以分析某个网站的拓扑结构，声望，分类等，可以用来实现文档的自动分类等。归根结底，能够帮助用户在WWW海量的信息里面准确找到需要的信息。这是一个正在迅速发展的研究领域。
上面我们从历史的角度总结了链接分析算法的发展历程，较为详细的介绍了算法的基本思想和具体实现，对算法的存在的问题也做了讨论。这些算法有的处于研究阶段，有的已经在具体的系统实现了。这些算法大体可以分为3类，基于随机漫游模型的，比如PageRank，Repution算法，基于Hub和Authority相互加强模型的，如HITS及其变种，基于概率模型的，如SALSA，PHITS，基于贝叶斯模型的，如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传统的内容分析技术进行了优化。一些实际的系统实现了某些算法，并且获得了很好的效果，Google实现了PageRank算法，IBM Almaden Research Center 的Clever Project实现了ARC算法，多伦多大学计算机系实现了一个原型系统TOPIC，来计算指定网页有声望的主题。
AT&T香农实验室的Brian Amento在指出，用权威性来评价网页的质量和人类专家评价的结果是一致的，并且各种链接分析算法的结果在大多数的情况下差别很小[15]。但是，Allan Borodin也指出没有一种算法是完美的，在某些查询下，结果可能很好，在另外的查询下，结果可能很差[11]。所以应该根据不同查询的情况，选择不同的合适的算法。
基于链接分析的算法，提供了一种衡量网页质量的客观方法，独立于语言，独立于内容，不需人工干预就能自动发现WEB上重要的资源，挖掘出WEB上重要的社区，自动实现文档分类。但是也有一些共同的问题影响着算法的精度。
1．根集的质量。根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页，产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量网页集找出很多高质量的网页。
2．噪音链接。WEB上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商，用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果。如何有效的去除这些无关链接，也是算法的一个关键点。
3．锚文本的利用。锚文本有很高的精度，对链接和目标网页的描述比较精确。上述算法在具体的实现中利用了锚文本来优化算法。如何准确充分的利用锚文本，对算法的精度影响很大。
4．查询的分类。每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法，以求获得最好的结果。因此，对于查询的分类也显得非常重要。
结束语：当然，这些问题带有很大的主观性，比如，质量不能精确的定义，链接是否包含重要的信息也没有有效的方法能准确的判定，分析锚文本又涉及到语义问题，查询的分类也没有明确界限。如果算法要取得更好的效果，在这几个方面需要继续做深入的研究，相信在不久的将来会有更多的有趣和有用的成果出现。

3. 谁做过 EM算法 java实现

参考：

packagenlp;
/**
*@authorOrisun
*date2011-10-22
*/
importjava.util.ArrayList;

publicclassBaumWelch{

intM;//隐藏状态的种数
intN;//输出活动的种数
double[]PI;//初始状态概率矩阵
double[][]A;//状态转移矩阵
double[][]B;//混淆矩阵

ArrayList<Integer>observation=newArrayList<Integer>();//观察到的集合
ArrayList<Integer>state=newArrayList<Integer>();//中间状态集合
int[]out_seq={2,1,1,1,2,2,2,2,2,1,1,1,1,2,2,2,2,1,1,
1,1,1,2,2,2,1,1,1,1,1,2,1};//测试用的观察序列
int[]hidden_seq={1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,1,
1,1,1,1,2,2,2,1,1,1,1,1,1,1};//测试用的隐藏状态序列
intT=32;//序列长度为32

double[][]alpha=newdouble[T][];//向前变量
doublePO;
double[][]beta=newdouble[T][];//向后变量
double[][]gamma=newdouble[T][];
double[][][]xi=newdouble[T-1][][];

//初始化参数。Baum-Welch得到的是局部最优解，所以初始参数直接影响解的好坏
publicvoidinitParameters(){
M=2;
N=2;
PI=newdouble[M];
PI[0]=0.5;
PI[1]=0.5;
A=newdouble[M][];
B=newdouble[M][];
for(inti=0;i<M;i++){
A[i]=newdouble[M];
B[i]=newdouble[N];
}
A[0][0]=0.8125;
A[0][1]=0.1875;
A[1][0]=0.2;
A[1][1]=0.8;
B[0][0]=0.875;
B[0][1]=0.125;
B[1][0]=0.25;
B[1][1]=0.75;

observation.add(1);
observation.add(2);
state.add(1);
state.add(2);

for(intt=0;t<T;t++){
alpha[t]=newdouble[M];
beta[t]=newdouble[M];
gamma[t]=newdouble[M];
}
for(intt=0;t<T-1;t++){
xi[t]=newdouble[M][];
for(inti=0;i<M;i++)
xi[t][i]=newdouble[M];
}
}

//更新向前变量
publicvoipdateAlpha(){
for(inti=0;i<M;i++){
alpha[0][i]=PI[i]*B[i][observation.indexOf(out_seq[0])];
}
for(intt=1;t<T;t++){
for(inti=0;i<M;i++){
alpha[t][i]=0;
for(intj=0;j<M;j++){
alpha[t][i]+=alpha[t-1][j]*A[j][i];
}
alpha[t][i]*=B[i][observation.indexOf(out_seq[t])];
}
}
}

//更新观察序列出现的概率，它在一些公式中当分母
publicvoipdatePO(){
for(inti=0;i<M;i++)
PO+=alpha[T-1][i];
}

//更新向后变量
publicvoipdateBeta(){
for(inti=0;i<M;i++){
beta[T-1][i]=1;
}
for(intt=T-2;t>=0;t--){
for(inti=0;i<M;i++){
for(intj=0;j<M;j++){
beta[t][i]+=A[i][j]
*B[j][observation.indexOf(out_seq[t+1])]
*beta[t+1][j];
}
}
}
}

//更新xi
publicvoipdateXi(){
for(intt=0;t<T-1;t++){
doublefrac=0.0;
for(inti=0;i<M;i++){
for(intj=0;j<M;j++){
frac+=alpha[t][i]*A[i][j]
*B[j][observation.indexOf(out_seq[t+1])]
*beta[t+1][j];
}
}
for(inti=0;i<M;i++){
for(intj=0;j<M;j++){
xi[t][i][j]=alpha[t][i]*A[i][j]
*B[j][observation.indexOf(out_seq[t+1])]
*beta[t+1][j]/frac;
}
}
}
}

//更新gamma
publicvoipdateGamma(){
for(intt=0;t<T-1;t++){
doublefrac=0.0;
for(inti=0;i<M;i++){
frac+=alpha[t][i]*beta[t][i];
}
//doublefrac=PO;
for(inti=0;i<M;i++){
gamma[t][i]=alpha[t][i]*beta[t][i]/frac;
}
//for(inti=0;i<M;i++){
//gamma[t][i]=0;
//for(intj=0;j<M;j++)
//gamma[t][i]+=xi[t][i][j];
//}
}
}

//更新状态概率矩阵
publicvoipdatePI(){
for(inti=0;i<M;i++)
PI[i]=gamma[0][i];
}

//更新状态转移矩阵
publicvoipdateA(){
for(inti=0;i<M;i++){
doublefrac=0.0;
for(intt=0;t<T-1;t++){
frac+=gamma[t][i];
}
for(intj=0;j<M;j++){
doubledem=0.0;
//for(intt=0;t<T-1;t++){
//dem+=xi[t][i][j];
//for(intk=0;k<M;k++)
//frac+=xi[t][i][k];
//}
for(intt=0;t<T-1;t++){
dem+=xi[t][i][j];
}
A[i][j]=dem/frac;
}
}
}

//更新混淆矩阵
publicvoipdateB(){
for(inti=0;i<M;i++){
doublefrac=0.0;
for(intt=0;t<T;t++)
frac+=gamma[t][i];
for(intj=0;j<N;j++){
doubledem=0.0;
for(intt=0;t<T;t++){
if(out_seq[t]==observation.get(j))
dem+=gamma[t][i];
}
B[i][j]=dem/frac;
}
}
}

//运行Baum-Welch算法
publicvoidrun(){
initParameters();
intiter=22;//迭代次数
while(iter-->0){
//E-Step
updateAlpha();
//updatePO();
updateBeta();
updateGamma();
updatePI();
updateXi();
//M-Step
updateA();
updateB();
}
}

publicstaticvoidmain(String[]args){
BaumWelchbw=newBaumWelch();
bw.run();
System.out.println("训练后的初始状态概率矩阵：");
for(inti=0;i<bw.M;i++)
System.out.print(bw.PI[i]+"	");
System.out.println();
System.out.println("训练后的状态转移矩阵：");
for(inti=0;i<bw.M;i++){
for(intj=0;j<bw.M;j++){
System.out.print(bw.A[i][j]+"	");
}
System.out.println();
}
System.out.println("训练后的混淆矩阵：");
for(inti=0;i<bw.M;i++){
for(intj=0;j<bw.N;j++){
System.out.print(bw.B[i][j]+"	");
}
System.out.println();
}
}
}

4. 谁做过 EM算法 java实现

在基本配置(Basic Configuration)界面中，我们可以给以下选项设置参数：

默认的语言(Default Language)给安装过程和操作系统指定默认的语言。

键盘(Keyboard) 设置默认的键盘，通常要与语言相对应。

时区(Time Zone)把计算机的硬件时钟设置为utc的原子时间，后者即为格林威治标准时间。

超级系统管理员密码(root Password)指定超级系统管理员的密码，可能需要加密。

5. pattern recognition and machine learning这本书怎么看

作者：Richardmore
这本书可以说是机器学习的经典学习之作。以前在上机器学习这么课的时候，很多细节还没联系到，结果在读论文中就显得捉襟见肘。本文打算理清楚这本书的脉络，也顺便为学习机器学习的人打下一个学习路线图。

1. 排除两块内容

现排除第五章的内容神经网络，之所以把神经网络先单列出来，原因一是一个比较独立的研究脉络，二是因为这部分因为深度学习的原因太热了，所以我认为在学习机器学习中把神经网络单列出来学习，在交大的研究生课程安排中，神经网络是机器学习的后续课程。
对于第6，7章，也不在下面的学习路线中，因为这部分是关于核技巧方面的，主要是就是高斯过程回归，高斯过程分类以及SVM等内容。
2. 一个概率图框架为中心视角

排除了上面几章的内容，PRML书中可以用下面的学习路线图覆盖，通过这个图可以理清楚了各个内容的不同角色。
<img src="https://pic3.mg.com/_b.png" data-rawwidth="1888" data-rawheight="412" class="origin_image zh-lightbox-thumb" width="1888" data-original="https://pic3.mg.com/_r.png">

说明：
（1）一般模型中都会有隐变量因此，，因此对于P（X）的采用MLE学习的另一个技巧,便是第九章 EM算法。条件是在M步时，Q要可以被analytically computed。
（2）至于为什么近似，Exact Inference is hard we resort to approximation
3. 隐变量技巧

下面我们看看另外一个视角：隐变量技巧。隐变量不仅可以使得模型的表达能力丰富起来，而且通常对于隐变量往往富有一定的实际意义。

<img src="https://pic1.mg.com/_b.png" data-rawwidth="1764" data-rawheight="422" class="origin_image zh-lightbox-thumb" width="1764" data-original="https://pic1.mg.com/_r.png">

说明：
（1）这里所谓的结合模型中，在PRML中最后一章仅仅提到了以加法的方式进行模型集合，也就是mixture of experts，在论文Hinton G E. Training procts of experts by minimizing contrastive divergence[J]. Neural computation, 2002, 14(8): 1771-1800. 提出了proct of experts 模型，也就是以乘法的方式进行结合，RBM就是一种特殊的proct of experts 模型，而高斯混合模型便是加法模型的代表。
（2）隐变量的技巧是机器学习中一种重要的技巧，隐变量的加入不仅仅增加了模型的表达能力，而且，隐变量还可以被赋予某种特殊的意义，比如RBM模型中隐变量h被当成显变量v的特征抽象。这当然归根结底是因为隐变量模型确实是现实世界真实存在的情况，unobserved but important variables do exist! 当然隐变量的引入也为模型的推断带来了新的挑战，有很多比较好的隐变量模型往往找不到很高效的方法，而被限制着。
4. 例子说明

下面分别从上面两个视角来分析RBM模型，贝叶斯线性回归和序列模型。
4.1 RBM模型
RBM模型是一个无向2层对称的图模型，从隐变量的视角来看，它是一个以乘法方式结合的distributed models。当然隐变量的引入增加了模型的复杂性和表达能力，但是也为学习，推断带来了问题。对于RBM的参数学习，因为是无向图，所以采用MLE最大化P（X），但是由于此时P（X，Z）难以评估，所以
<img src="https://pic2.mg.com/v2-_b.png" data-rawwidth="834" data-rawheight="94" class="origin_image zh-lightbox-thumb" width="834" data-original="https://pic2.mg.com/v2-_r.png">
很难计算，没有在RBM的学习中不能像高斯混合模型那样可以采取EM算法。因此只能采取最为标准的做法，求取P（X）的梯度，结果梯度公式如下：
<img src="https://pic2.mg.com/v2-_b.png" data-rawwidth="800" data-rawheight="90" class="origin_image zh-lightbox-thumb" width="800" data-original="https://pic2.mg.com/v2-_r.png">

然而对于计算后面的model部分的积分需要知道模型的概率分布，评估模型的概率分布需要计算一个标准化的分母，难以计算。因此就需要依赖近似，由于p（v｜h），p（h｜v）都是可以分析公式表达，因此采用Gibbs sampler来数值逼近积分。当然后来Hinton G E. Training procts of experts by minimizing contrastive divergence[J].发现对于这一部分，Gibbs sampler 不需要多部的迭代，一次迭代就可以了，从而使的训练RBM的时间代价大大降低了，后来（A fast learning algorithm for deep belief nets，2006）提出了贪婪式的训练多层DBN（stacked RBM），每层都是训练RBM，从而使的深度学习焕发新的活力（Recing the dimensionality of data with neural networks，2006）。

4.2 贝叶斯线性回归Bayesian Linear Regression BLR

这个模型是最为基础的，这个模型在PRML中，利用直接推断，变分法推断，MCMC采样都是可以做的；因此便于比较不同算法得到的结果。之前，本来打算在这里以LDA主题模型来举例，虽然LDA的EM算法， 变分法，以及Gibbs sampling 都是可以做的，但是模型太复杂，所以果断放弃了，以BLR模型作为例子说明。
BLR是一个有向图模型，是一个典型的贝叶斯网络（虽然简单一点）。如果以一个贝叶斯的视角来看，其中的隐变量便是线性参数w，以及各种超参数α,β.....，在贝叶斯的处理视角之下，这些都会赋予一个先验分布。当然，有些模型书中也提到，有不同层次上的贝叶斯网络。有的是仅仅对参数w赋予一个先验分布，而对于其他的参数（hyperparameter）仅仅是作为模型参数，就是假设是一个渡固定的数值，然后再通过learn evidence function，其实说白了就是MLE，来寻找最佳的超参数α,β....。相比于把线性参数w，以及各种超参数α,β.....全部作为放入到贝叶斯网络中，这样的做法显然简化了模型，降低了贝叶斯网络的复杂性。这个技巧也在多处的论文中出现。
从隐变量的角度来看，由于BLR模型相对简单，其中并没有随机隐变量，仅仅是一些参数w，以及各种超参数α,β..的环境隐变量。
4.3 序列模型：隐马尔可夫链HMM与条件随机CRF

隐马尔可夫链HMM这个模型是一个有向图模型，典型的贝叶斯网络，只不过这个网络是一个线性链（linear chains），因此可以进行分析上推断，要知道对于一般网络，并不存在通用的实用的inference算法。因为HMM是一个有向图模型。但是（1）在PRML书中，以及李航《统计学习》中并没有把其当作一个贝叶斯网络来进行处理，对所有的参数比如发射概率，转移矩阵概率都是模型的参数，而不是通过赋予一个先验分布，从而纳入到贝叶斯网络框架之中。因此对于模型而言，关键的便是通过MLE最大化P（X）来学习模型的参数，因为这里的有隐变量，因此在PRML，以及《统计学习》中都是通过EM算法做的。（2）其实，HMM是一个典型的线性链式的贝叶斯网络，因此对于通过对其参数赋予先验分布，进而从贝叶斯的角度，来对模型进行推断是一个非常自然的想法。我在论文Sharon Goldwater， Thomas L Griffiths 论文 A Fully Bayesian Approach to Unsupervised Part-of-Speech Tagging，中作者采用了Bayesian HMM 重新做了POS任务。作者在文中还详细罗列了Bayesian HMM 相比普通的HMM的优点：（a）可以使用先验知识，例如在POS中语言的认知可以加入到先验分布之中，而且（b）贝叶斯的推断，是通过一个后验分布推断参数，相比MLE点估计，会更加准确。对于贝叶斯的推断，作者在文中使用了Gibbs sample抽样实现了数值采样推断模型。最后作者比较了Gibbs sample＋Bayesian HMM和普通的HMM ＋EM，在POS任务效果更加好。另外，对于本论文的作者Thomas L Griffiths，第一次接触这个学者，是在读Gibbs sample in LDA这篇文章，作者推导了LDA的各种的条件分布，然后基于Gibbs sample 进行采样，记得Github上有Java版的实现代码，其推导十分严谨，并且有代码辅助，是学习LDA的一个捷径。在近似推断方面可以看出Thomas L Griffiths是一个坚定的数值采样学派，而LDA的开山之作《Latent Dirichlet Allocation 》的作者David M. Blei，看了作者部分文章以后，发现这个人是在近似推断方面是一个变分法的坚定学派，在《Latent Dirichlet Allocation 》之中，便是通过变分法进行推断了，David M. Blei还写了一个关于变分法的入门讲义pdf，网上可以搜到。所以回看我们概率图视角，做机器学习推断是不可避免的，有的是变分法近似，有的是数值采样近似，也有的是EM算法试一试。至于选择哪一种，就看你的问题哪一个比较简单了。但是好像有的人对这些方面各有偏爱。
再说一下条件随机场CRF，相比与HMM，这也是一个序列模型，在很多的NLP任务中，CRF都是state of art 的算法，毕竟人家可以方便的特征工程嘛。但是这种日子被深度学习取代了，在NLP方面，RNN（递归神经网络）要比CRF表现更好，见我之前博文基于RNN做语义理解和词向量。先不说这么远，CRF的模型架构上是一个典型的无向的链式概率图模型，因此，（回看我们概率图的视角），CRF的关键问题便是如何进行学习了P（X），好在求其该模型直接求其梯度并没有太大的困难，具体可以参见李航的《统计学习》。
5 结束语

这篇文章，从概率图，隐变量两个视角对PRML中各个章节进行了串联，并以RBM，BLR，序列模型（HMM&CRF）具体说明这种串联。