查看文章 |
隐马尔可夫模型HMM（2）
2006-12-05 10:56
三、隐模型（Hidden Patten）
通常，马尔可夫过程是不够的，因为它并没有利用其他条件（如海草的干湿）。如果同时考虑海草的干湿，我们可以得到两个状态集，即观察结果集（海草）和“隐”状态集（天气）。之后我们将利用这两个状态集，通过算法预测未来的天气。 一个更实际的例子是语音识别，实际的语音序列是一系列隐状态的组合，而系统识别出的语音序列则是观察结果状态。同时，观察结果状态的个数和隐状态的个数不一定总相同，正如我们可以再给海草一个dryish状态，而实际的80个语素对应的发音也很可能不止80个。 这种对应关系也是有一定概率的，为此，我们使用隐马尔可夫模型来描述。 从上图中可以看出，观察状态的变化之下隐藏着实际状态的更改，而其中的概率关系可以用Pr(Obv|Weather)表示，其观察状态矩阵（confusion matrix）为：（我认为这个矩阵的值有问题，应当是列和为1，这样更符合后面以观察结果为依据计算天气）
可见，一个隐马尔可夫模型由5部分组成： 1）隐藏状态；2）观察状态；3）Π向量；4）状态转移矩阵；5）状态矩阵。 四、隐马尔可夫模型（Hidden Markov Models）
隐马尔可夫模型可以由一个三元组（Π，A，B）描述： 1）Π = (πi)是初始化向量； 2）A = (aij)是状态转移矩阵，元素为Pr(xj(t))|xi(t-1))，相当于头天天气xi，今天天气是xj的概率；（这是一个条件概率，列和为1，因此以列（今天）为前置条件） 3）B = (bij)是观察状态矩阵，元素为Pr(yj|xi)，相当于海草状态为yj时，天气是xi时概率。 它主要有三个方面的用途： 1）评价（Evaluation），从多个隐马尔可夫模型中选出一个最符合当前观察结果的。比如海草与天气的模型，在冬天和夏天应当是不同的。那么给出一个海草干湿状态变化的序列，就可以评估出哪个模型更合适，同时也就可以推断出这个序列出现在冬天还是夏天。 我们使用前向算法（Forward Algo）去计算一个序列在不同模型中的概率，从而取得最大可能的模型。语音识别中，同样使用这种方法去计算一个发音在不同模型（每个模型针对不同的词）中的概率，从而取得最大可能的词。 2）解码（Decoding），给定一个隐马尔可夫模型和观察结果序列，计算出可能性最大的隐状态序列，也可以认为是预测。 我们使用维特比算法（Viterbi Algo）进行解码计算，一个很大的用途就是自然语言处理中的词性标注。这里，句子中的词是观察结果，而词性则是隐状态（因为一个词可能对应多个词性）。通过对整个句子（观察结果序列）语法（隐状态序列）的识别，就可以确定词性。 3）学习（Learning），根据一系列的观察结果构建隐马尔可夫模型。 这也是最难的一种应用，我们使用前向-后向算法（Forward-Backward Algo）来进行计算。 五、前向算法（Forward Algo）
评价（Evaluation）的基本方法就是计算隐马尔可夫模型产生一个序列的概率（能力）。概率越大，这个序列就越可能是该隐马尔可夫模型生成的。 比如我们给定一个海草变化的序列：dry，dump，soggy。在隐模型（状态转换模型）中，可能存在27（3^3）个对应的天气变化序列，分别是sun，sun，sun；sun，cloud，sun；...；rain，rain，rain。 也就是说， Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)。 但是这个计算太复杂了，当序列长度增加时，运算复杂度呈指数增长。于是，我们要想办法降低复杂度，可以考虑动态规划的方法： 对于序列中的第 i 项，对应 3 种状态（sun，cloud，rain）。分别求出到达每种状态的概率，于是pr(dry, damp, soggy | HMM) = Pr(x, y, sun) + Pr(x, y, cloud) + Pr(x, y, rain)，Pr(x, y, sun) = Pr(x, sun, sun) + Pr(x, cloud, sun) + Pr(x, rain, sun) = Pr(x, sun) * Pr(sun, sun) + Pr(x, cloud) * Pr(cloud, sun) + Pr(x, rain) * Pr(rain, sun)。注意，Pr(x, sun)在计算Pr(x, y, sun)，Pr(x, y, cloud)和Pr(x, y, rain)中都会用到，这样就通过填表的方式降低了运算复杂度，计算量约为 k*n^2 ，k 为序列长度，n 为状态个数。 对于每个时间 t 下的每个状态 j ，公式为：x( t )( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)。需要说明的时，t = 1 时，Pr 为初始化向量对应的值。也可以描述为：x(t+1)(j) = b(j)(k(t+1)) * (Σx(t)(i)*a(i)(j))，k 为观察状态序列，t 为序列中的位置，i 从 1 到 n。 而总的概率为：Pr = Σx(T)(j)，j 从 1 到 n 。 原文给出了Π = <0.63, 0.17, 0.20>时的模拟计算（一个Java Applet），A和B矩阵则都已经在前文中给出。http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg1.html 六、维特比算法（Viterbi Algo）
解码（Decoding）是指：给定一个隐马尔可夫模型（HMM）和观察序列，求得可能性最大（见下文说明）的状态序列。其经典算法是维特比算法。 同样，对于这样一个海草变化的序列：dry，dump，soggy。在隐模型（状态转换模型）中，可能存在27（3^3）个对应的天气变化序列，分别是sun，sun，sun；sun，cloud，sun；...；rain，rain，rain。 也就是求出Max( Pr(dry,damp,soggy | sunny,sunny,sunny), Pr(dry,damp,soggy | sunny,sunny,cloudy), Pr(dry,damp,soggy | sunny,sunny,rainy), . . . . , Pr(dry,damp,soggy | rainy,rainy,rainy))，这同样是一个很复杂的计算过程。 维特比算法的思想在于动态规划和剪枝：对于每个时间 t 下的状态 i ，只保留概率最大的一枝：Pr(i at time t) = Max(Pr(j at time(t-1)) * Pr(i|j) * Pr(obv. at time t|i)，同时，记录这个最大值对应的 x(i) = j （填表），再通过 n 个这样的最大值计算 t+1 时的最大值。当 t = 1 时，Pr(i) = Max(Pr(obv. | i) * Π(i))。其复杂度和前向算法相同，都是 k*n^2。 说明，维特比算法是填一个 n*k 大小的表，每个表项由两部分组成，第一部分为 t 时刻到达 i 状态的概率 Pr ，另一部分为产生该概率的前序状态 j 。 这样，从Max(Pr(i at time T))求得产生该观察序列的最大可能的状态序列的最后一个状态 i(T) ，再从这个状态 i(T) 开始，在表中向前回溯，i(t-1) = x(i(t))，即可求得完整的序列。 维特比算法的优势在于不仅仅考察前后两个观察状态的关系，而是全面考察整个观察序列，得出一个“最大似然”的结果。这在语音识别，通信领域有着巨大的意义——即使序列中有一两个误码，还是能够根据整个序列给出正确的解码。 原文给出的模拟计算有问题，因此不再给出链接。 七、前向-后向算法（Forward-Backward Algo） 前向算法和维特比算法都是基于隐马尔可夫模型的应用，前提是隐马尔可夫模型已知。但是，在很多情况下，模型是未知的，这就是学习（Learning）问题。前项后向算法通过分析由观察状态集中的状态组成的一系列的观察序列和隐状态集，给出隐马尔可夫模型。 比如语音识别中，通常需要针对某个人的声音进行训练，才能更好地识别出这个人说的话。 但是，到目前为止，学习问题还没有解析解法。传统的方法是先给出一组初始化参数（也许完全是错误的），然后使用观察序列进行训练——修正其中的错误，或使错误最小化。 在前向-后向算法中，同样要先给出一组初始化参数，其基本原理是同时计算达到某个状态的概率（前向）和由这个状态到终止状态的概率（后向），并以此为依据对参数进行调整。 八、总结（Summary） 通常，模式不会孤立的存在，它往往以时间或空间为顺序，和它前面或后面的模式相关。因此，可以利用模式间的关系进行模式识别。 我们假设模式间的关系不随时间/空间的变化而变化，并假设第 n 个模式只与它前面的 k 个模式有关（最简单的是 k=1 ），这就构成了 k 阶马尔可夫过程。 又，模式并不一定存在于表面，它很有可能存在于某种现象之下，但现象和模式间存在某种联系，这就构成了隐马尔可夫模型。 隐马尔可夫模型主要解决三方面的问题： 1）给定观察序列和模型，求该模型生成该观察序列的概率：评估（Evaluation）； 2）给定观察序列和模型，求该模型下最可能生成该观察序列的状态序列：解码（Decoding）； 3）给定观察状态集和隐状态集，以及若干观察序列，求模型：学习（Learning）。 隐马尔可夫模型的应用广泛，它的局限性在于马尔可夫假设，即模式间关系的时不变性。 参考文献：L R Rabiner and B H Juang, 'An introduction to HMMs', iEEE ASSP Magazine, 3, 4-16. |
最近读者：
本篇日志被作者设置为禁止发表新评论