马尔科夫链的应用

马尔科夫链的应用戴奇2013/12/17马尔科夫链马尔科夫假设：即随机过程中各个状态St的概率分布，只与它的前一个状态St-1有关，即马尔科夫链：符合这个假设的随机过程则称为马尔科夫链（也称为马尔科夫过程）离散的马尔科夫链（举例）圈：表示状态边：表示可能的状态转换权值：转移概率每一个状态只和它的前一个状态有关隐含马尔科夫模型（HMM）美国数学家鲍姆等人在20世纪六七十年代发表的一系列论文中提出的马尔科夫链的一个扩展：任一时刻t的状态St是不可见的状态并不是直接可见的，但受状态影响的某些变量则是可见的每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。独立输出假设：每个时刻t(隐含状态St)会输出一个符号Ot，而且Ot和St相关而且仅和St相关HMM的状态变迁图x:隐含状态y:可观察的输出a:转换概率b:输出概率（或生成概率）HMM（举例）住得很远的朋友，每天打电话告诉你做了什么，三种活动感兴趣:公园散步,购物以及清理房间，选择做什么事情只凭天气，你对于他所住的地方的天气情况并不了解,但是你知道总的趋势天气的运行就像一个马尔可夫链。其有两个状态雨和晴,但是你无法直接观察它们。你的朋友有一定的概率进行下列活动:散步,购物,或清理。因为你朋友告诉你他的活动,所以这些活动就是你的观察数据这整个系统就是一个隐含马尔可夫模型HMM维特比（Viterbi）算法安德鲁·维特比(AndrewViterbi)于1967年提出针对一个特殊的图——篱笆网络的有向图（Lattice）的最短路径问题而提出的它之所以重要，是因为凡是使用隐含马尔科夫模型描述的问题都可以用它来解码一种动态规划算法。它用于寻找最有可能产生观测事件序列的-维特比路径-隐含状态序列,特别是在马尔可夫信息源上下文和隐含马尔可夫模型中。维特比算法（举例）输入拼音：y1，y2，....,yN（输入序列）对应汉字：x1，x2，....,xN（隐含序列）每个状态的输出是固定的，状态的值可以变化维特比算法（举例）xij表示状态Xi的第j个可能的值，得到篱笆网络维特比算法（举例）基础：假定状态i—状态i+1,起始点S到状态i上各个节点的最短路径已经找到，并且记录在这些节点上，那么再计算S到第i+1状态的某个节点xi+1的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这k个节点到xi+1，j距离即可。维特比算法（举例）算法步骤第一步，从点S出发，对于第一个状态x1的各个节点（不妨设n1个），计算出S到它们的距离d(S,x1i)第二步，对于第二个状态的x2的所有节点，要计算出S到它们的最短距离接下来，类似的按照上述方法从第二个状态走到第三个状态，一直走到最后一个状态，就得到了整个网格从头到尾的最短路径1、马尔科夫链在pagerank算法中的应用pagerank的思想精华：将一个网页级别/重要性的排序问题转化成了一个公共参与、以群体民主投票的方式求解的问题，网页之间的链接即被认为是投票行为同时，各个站点投票的权重不同，重要的网站投票具有较大的分量，而该网站是否重要的标准还需要依照其PageRank值矛盾：用PageRank值来计算PageRank值佩奇和布林证明了这个过程最终收敛值与初始值无关迭代收敛所有PageRank的计算是同时的。即在计算之前，类似上面的一个有向图已经确定了。然后所有网站的PageRank同时用上面这个公式计算。迭代过程如下：初始：所有网站的PageRank均等第一次迭代：每个网站得到了一个新的PageRank第二次迭代：用这组新的PageRank再按上述公式迭代形成另一组新的PageRank马尔科夫链的平稳分布设齐次马尔科夫链转移概率矩阵为A，若满足方程则称为该马尔科夫链的平稳分布例子：{A,B,C}为马尔科夫链，转移概率如下：A=[]设平稳分布为解得，x=0.1765，y=0.2353，z=0.5882),,(21NxxxAiix1),,(21Nxxx0.70.10.20.10.80.10.050.050.9),,(zyxpagerank算法的马尔科夫过程分析假设这里有7个网页，且链接关系是闭合的那么我们可以很容易地将这个链接关系使用数学的方式表示出来。首先，分析链接的关系，列举出各个链接源的ID及其所链接的目标ID链接源ID链接目标ID12,3,4,5,72131,242,3,551,3,4,661,575链接关系（数学表示）链接关系（矩阵表示）使用邻接矩阵的形式表述网页之间的链接关系，G[i][j]=1表示从i到j有链接，否则表示无链接，G为7*7的矩阵0,1,1,1,1,0,1;1,0,0,0,0,0,0;1,1,0,0,0,0,0;G=0,1,1,0,1,0,0;1,0,1,1,0,1,0;1,0,0,0,1,0,0;0,0,0,0,1,0,0;转移概率矩阵假设每个网页初始的PageRank均为1，则会形成一个初始的PageRank转移矩阵0,1/5,1/5,1/5,1/5,0,1/5;1,0,0,0,0,0,0;1/2,1/2,0,0,0,0,0;A=0,1/3,1/3,0,1/3,0,0;1/4,0,1/4,1/4,0,1/4,0;1/2,0,0,0,1/2,0,0;0,0,0,0,1,0,0;pagerank收敛值按照求马氏链平稳分布的方式，求得PageRank收敛结果，方程组为：解得，X1=0.303514，X2=0.38286，X3=0.32396，X4=0.24297，X5=0.41231，X6=0.10308，X7=0.13989X1=X2+X3/2+X5/4+X6/2X2=X1/5+X3/2+X4/3X3=X1/5+X4/3+X5/4X4=X1/5+X5/4X5=X1/5+X4/3+X6/2+X7X6=X5/4X7=X1/5X1+X2+X3+X4+X5+X6+x7=1PR值顺序排列将PageRank的评价按顺序排列，小数点3位四舍五入，可以得到下表：页面之间状态转移图2、马尔科夫链在中文分词中的应用假定一个句子S可以有几种分词方法，为了简单起见，假定有以下三种：A1，A2，A3，....，AkB1，B2，B3，...，BmC1，C2，C3，...，Cn（其中A1，A2，...B1，B2，...C1，C2，...等等都是汉语的词）上述各种分词结果可能产生不同数量的词串，因为我用了k,m,n三个不同的下标表示句子在不同的分词时词的数目。最好的分词最好的一种分词方法应该保证分完词后这个句子出现的概率最大。假如A1，A2，A3，....，Ak是最好的分法，那么其概率满足：P(A1，A2，...，Ak)P(B1，B2，...，Bm)P(A1，A2，...，Ak)P(C1，C2，...，Cn)最好分词的概率P(A1，A2，...，Ak)=P(A1)*P(A2|A1)*P(A3|A1,A2)...*P(An|A1，A2，A3，...，Ak-1)但是，发现从第三项开始条件概率就比较难算了利用马尔科夫假设，即任意一个词Ai出现的概率只同它前面的词Ai-1有关，于是得，P(A1，A2，...，Ak)=p(A1)*P(A2|A1)*P(A3|A2)....*P(An|An-1)P(Ai|Ai-1)=P(Ai-1,Ai)/P(Ai-1)近似等于#(Ai-1,Ai)/#(Ai-1)穷举的缺点如果穷举所有的分词方法，计算量是相当大的，因此，可以把它看成一个动态规划的问题，并利用维特比算法快速地找到最佳分词