马尔可夫模型介绍(从零开始)

马尔可夫模型介绍（从零开始）（一）：定义及简介：介绍（introduction）通常我们总是对寻找某一段时间上的模式感兴趣，这些模式可能出现在很多领域：一个人在使用电脑的时候使用的命令的序列模式；一句话中的单词的序列；口语中的音素序列。总之能产生一系列事件的地方都能产生有用的模式。考虑一个最简单的情况：有人(柯南？)试图从一块海藻来推断天气的情况。一些民间的传说认为“soggy”的海藻意味着潮湿（wet）的天气，“dry”的海藻预示着晴朗（sun）。如果海藻处于中间状态“damp”，那就无法确定了。但是，天气的情况不可能严格的按照海藻的状态来变化，所以我们可以说在一定程度上可能是雨天或是晴天。另一个有价值的信息是之前某些天的天气情况，结合昨天的天气和可以观察到的海藻的状态，我们就可以为今天的天气做一个较好的预报。这是在我们这个系列的介绍中一个非常典型的系统。首先我们介绍一个可以随时间产生概率性模型的系统，例如天气在晴天或者雨天之间变动。接下来我们试图去预言我们所不能观察到的隐形的系统状态，在上面的例子中，能被观察到的序列就是海藻的状态吗，隐形的系统就是天气情况然后我们看一下关于我们这个模型的一些问题，在上面那个例子中，也许我们想知道1.如果我们观察一个星期每一天的海藻的状态，我们是否能知相应的其天气情况2.如果给出一个海藻状态的序列，我们是否能判断是冬天还是夏天？我们假设，如果海藻干（dry）了一段时间，那就意味着是夏天如果海藻潮湿（soggy）了一段时间，那可能就是冬天。（二）：生成模式（GeneratingPatterns）确定的模式（DeterministicPatterns）考虑交通灯的例子，一个序列可能是红-红/橙-绿-橙-红。这个序列可以画成一个状态机，不同的状态按照这个状态机互相交替我们可以注意到，每一个状态都只依赖于此前的状态，如果当前的是绿灯，那么接下来就是橙灯，这就是一个确定型的系统。确定型的系统更容易理解和分析，只要这些状态转移都是已知的。不确定的模式（Non-DeterministicPatterns）为了让之前那个天气的例子更贴近现实，我们可以添加一个状态-多云。和交通灯的例子不同，我们不能得到一个确定的状态转移系统，但是我们还是希望能得到一个天气的模式。一种办法就是假设这个模型的每个状态都只依赖于之前的状态，这个假设被称为马尔科夫假设，这个假设可以大大的简化这个问题。显然，这个假设可能是一个非常糟糕的假设，导致很多重要的信息都丢失了。当涉及到天气的时候，马尔科夫假设假设如果我们知道之间一些天的天气的信息，不考虑风力、气压等因素，那么我们就能预言今天的天气。当然，和其他许多例子一样，这个列子也是不合实际的。但是，这样一个简化的系统可以有利于我们的分析，所以我们通常接受这样的假设，因为我们知道这样的系统能让我们获得一些有用的信息，尽管不是十分准确的。一个马尔科夫过程就是指过程中的每个状态的转移只依赖于之前的n个状态，这个过程被称为1个n阶的模型，其中n是影响转移的状态的数目。最简单的马尔科夫过程就是一阶过程，每一个状态的转移只依赖于其之间的那一个状态。注意这和确定型的系统不一样，因为这种装因是有概率的，而不是确定的。下面这个图展示了天气这个例子中所有可能的一阶转移：注意一个含有M个状态的一阶过程有M的平方个状态转移。每一个转移的概率叫做状态转移概率（statetransitionprobability），就是从一个状态转移到另一个状态的概率。这所有的M的平方个概率可以用一个状态转移矩阵来表示。注意这里有一个假设，概率不随时间的变化而变化，这又是一个不现实但很重要的假设。下面就是一个状态转移矩阵的列子：这个矩阵的意思是，如果昨天是晴天，那么今天又50%的可能是晴天，37.5%的概率是阴天，12.5%的概率会下雨，很明显，每一行的和都是1。为了初始化这样一个系统，我们需要一个初始的概率向量：这个向量表示第一天是晴天。到这里，我们就为一阶马尔科夫过程定义了以下三个部分:状态：晴天、阴天和下雨初始向量：定义系统在时间为0的时候的状态的概率状态转移矩阵：每种天气转换的概率所有的能被这样描述的系统都是一个马尔科夫过程。总结（Summary）我们为了找到随时间变化的模式，就试图去建立一个可以产生模式的过程模型。我们使用了具体的时间步骤、状态、并且做了马尔科夫假设。有了这些假设，这个能产生模式系统就是一个马尔科夫过程。一个马尔科夫过程包括一个初始向量和一个状态转移矩阵。关于这个假设需要注意的一点是状态转移概率不随时间变化。（三）：隐含模式（HiddenPatterns）当马尔科夫过程不够强大的时候，我们又该怎么办呢？在某些情况下马尔科夫过程不足以描述我们希望发现的模式。回到之前那个天气的例子，一个隐居的人可能不能直观的观察到天气的情况，但是有一些海藻。民间的传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合，一个可以观察到的状态集合（海藻的状态）和一个隐藏的状态（天气的状况）。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。一个更现实的例子是语音识别，我们听到的声音是声带、喉咙和一起其他的发音器官共同作用的结果。这些因素相互作用，共同决定了每一个单词的声音，而一个语音识别系统检测的声音（可以观察的状态）是人体内部各种物理变化（隐藏的状态、引申一个人真正想表达的意思）产生的。某些语音识别设备把内部的发音机制作为一个隐藏的状态序列，把最后的声音看成是一个和隐藏的状态序列十分相似的可以观察到的状态的序列。在这两个例子中，一个非常重要的地方是隐藏状态的数目和可以观察到的状态的数目可能是不一样的。在一个有三种状态的天气系统（sunny、cloudy、rainy）中，也许可以观察到四种潮湿程度的海藻（dry、dryish、damp、soggy）。在语音识别中，一个简单的发言也许只需要80个语素来描述，但是一个内部的发音机制可以产生不到80或者超过80种不同的声音。在上面的这些情况下，可以观察到的状态序列和隐藏的状态序列是概率相关的。于是我们可以将这种类型的过程建模为又一个隐藏的马尔科夫过程和一个和这个马尔科夫过程概率相关的并且可以观察到的状态集合。下图显示了天气的例子中隐藏的状态和可以观察到的状态之间的关系。我们假设隐藏的状态是一个简单的一阶马尔科夫过程，并且他们两两之间都可以相互转换。下图则明确的表示出模型的演化，其中绿色的圆圈表示隐藏状态，紫色圆圈表示可观察到状态，箭头表示状态之间的依存概率，一个HMM可用一个5元组{N,M,π，A，B}表示，其中N表示隐藏状态的数量，我们要么知道确切的值，要么猜测该值，M表示可观测状态的数量，可以通过训练集获得，π={πi}为初始状态概率，A={aij}为隐藏状态的转移矩阵Pr(xt(i)|xt-1(j))，B={bik}表示某个时刻因隐藏状态而可观察的状态的概率，即混淆矩阵，Pr(ot(i)|xt(j))。在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的，即当系统演化时，这些矩阵并不随时间改变。对于一个N和M固的HMM来说，用λ={π,A,B}表示HMM参数。隐藏的状态和可以观察到的状态之间有一种概率上的关系，也就是说某种隐藏状态H被认为是某个可以观察的状态O1是有概率的，假设为P（O1|H）。如果可以可以观察的状态有三种，那么很显然P（O1|H）+P（O2|H）+P（O3|H）=1。这里我和原文的意思不太相同，原文说的意思是P（O1|H1）+P（O1|H2）+P（O1|H3）=1，但是这和下面的例子又不同。这样，我们也可以得到一个另一个矩阵，称为混淆矩阵。这个矩阵的内容是某个隐藏的状态被分别观察成集中不同的可以观察的状态的概率，在天气的例子中，这个矩阵如下图：注意到图中每一行的和为1，但是每一列的和不为1，这里我觉得可能是原文出错了，或者隐藏状态还有其他。总结我们已经看到有一些过程是和一个隐藏的马尔科夫过程概率相关的。在这种情况下，可以观察到的状态和隐藏的状态的数目可能是不一样的。我们可以把这种过程建模为隐马尔科夫模型（HMM）。这个模型包含两个状态集合和三个概率集合。隐藏的状态：一个隐藏的马尔科夫过程可以观察到的状态：如名初始向量：初始状态的隐藏状态的概率状态转移矩阵：隐藏状态的状态转移概率混淆矩阵：隐藏状态被观察成各个可以观察到的状态的概率我们可以认为隐马尔科夫模型是在一个不可观察的马尔科夫过程上添加了一个可以观察到的状态集合，加上这个过程到这个集合的一些概率关系得到的。（四）：隐马尔科夫模型（HiddenMarkovModels）定义：隐马尔科夫模型可以用一个三元组(π,A,B)来定义:1.π表示初始状态概率的向量2.A=（aij）（隐藏状态的）转移矩阵P（Xit|Xj（t-1））t-1时刻是j而t时刻是i的概率3.B=（bij）混淆矩阵P（Yi|Xj）在某个时刻因隐藏状态为Xj而观察状态为Yi的概率值得注意的是，在状态转移矩阵中的每个概率都是时间无关的，也就是说我们假设这个概率是固定的，不随时间变化。当然，这是马尔科夫模型最不切合实际的一个假设。隐马尔科夫模型的使用如果一个模型可以被描述成一个隐马尔科夫模型，有三个问题可以得到解决。前两个是模式识别的问题：1）根据隐马尔科夫模型得到一个可观察状态序列的概率（评价）；2）找到一个隐藏状态的序列使得这个序列产生一个可观察状态序列的概率最大(解码)。第三个问题就是根据一个可以观察到的状态序列集产生一个隐马尔科夫模型（学习）。1.评价假设我们有很多隐马尔科夫模型（也就是说一个三元组的集合）描述不同的系统和一个可观察状态序列集。我们也许想知道哪一个隐马尔科夫模型最可能产生某个可观察状态序列。比如说，我们也许有一个海藻的“Summer”模型和一个“Winter”模型，因为海藻在夏天和冬天的状态应该是不同的，我们希望根据一个可观察状态（海藻的潮湿与否）序列来判断现在是夏天还是冬天。我们可以使用前向算法来计算在某个特定的HMM下一个可观察序列的概率，然后据此找到最可能的模型。这种类型的应用通常出现在语音设别中，通常我们会使用很多HMM，每一个针对一个特别的单词。一个可观察状态的序列是从一个可以听到的单词向前得到的，然后这个单词就可以通过找到满足这个可观察状态序列的最大概率的HMM来识别。2.解码根绝可观察状态的序列找到一个最可能的隐藏状态序列。和上面一个问题相似的并且更有趣的是根据可观察序列找到隐藏序列。在很多情况下，我们队隐藏状态更有兴趣，因为其包含了一些不能被直接观察到的有价值的信息。比如说在海藻和天气的例子中，一个隐居的人只能看到海藻的状态，但是他想知道天气的状态。这时候我们就可以使用Viterbi算法来根据可观察序列得到最优可能的隐藏状态的序列，当然前提是已经有一个HMM。另一个广泛使用Viterbi算法的领域是自然语言处中标引词性。句子中的单词是可以观察到的，词性是隐藏的状态。通过根据语句的上下文找到一句话中的单词序列的最有可能的隐藏状态序列，我们就可以得到一个单词的词性（可能性最大）。这样我们就可以用这种信息来完成其他一些工作。3.学习从一个观察集中得到一个隐马尔科夫模型。第三个问题也是最困难的问题，根绝观察到的序列集来找到一个最有可能的HMM，也就是说确定一个最有可能的三元组(π,A,B）。当A，B矩阵都不是直观可测量（通过经验得到）的的时候，可以使用前向后向算法来解决这个问题。总结尽管做出了一些不太符合实际的假设，但是用三元组描述的HMMs在描述真实系统并进行分析的时候具有很大的价值，并且可以解决下面这些问题：1.用前向算法找到最有可能的隐马尔科夫模型2.用Viterbi算法根据观察序列找到最有可能的隐藏序列3.用前向后向算法决定最有可能产生某个观察集的隐马尔科夫模型的参数（五）：前向算法(ForwardAlgorithm)1、如果计算一个可观察序列的概率？1.穷举搜索加入给定一个HMM，也就是说(,A,B)这个三元组已知，