一、概述
计算机科学中所谈的“模式”通常指按照一定顺序发生的事件序列，比如机器翻译和自然语言处理中的文字（词）序列，程序设计中的指令序列，模式则体现了序列中事件的相关性。

举一个简单的例子，传说可以通过观察海草来预测天气，比如湿润（soggy）的海草意味着雨天（rainy），干燥（dry）的海草则意味着晴天（sunny）。可以再加入一个中间的状态“潮湿（dump）”，同时引入阴天（cloudy）。当然，这种关系并不是永远成立，因此他们之间存在着一个概率分布。

而预测天气的另外一个线索是：先前的天气，这很容易理解。那么，现在开始，我们将用这些已知条件来预测天气。

首先，我们会引入一个通过上述的关系预测出天气转换模型。然后，我们将引入“隐”系统的概念，隐系统相对于观察到的结果，在这个例子中，海草的干湿是观察结果，而实际的天气就是一个隐系统，因为我们看不到它。最后，我们会利用建立起来的整个系统模型去解决一些问题，比如通过海草来预测一周的天气，甚至来判断当时的季节（直觉上，夏天海草会干，而冬天会湿）。

二、转换模型（Generateing Pattern，转移网络）

1）决定性的（Deterministic）

决定性的转换模型，例如交通灯，红－红/黄－绿－黄（amber），状态之间的转换在满足条件的状态下只有一种可能性，显然这不能应用在天气的预测上。

2）非决定性的（Non-Deterministic）

在马尔可夫假设（Markov Assumption）中，当前状态只与前面的若干个状态有关，这使得模型可以大大简化。虽然这会导致预测的错误（显然，在天气的预测中，只考虑到前几天是晴天还是雨天并不明智，还应当考虑气流，气压，风速等等），但这种错误通常是可以接受的。

若马尔可夫模型中，当前状态只与前n个状态有关，则称之为n序模型（order n）。在本例中，假设当前天气只与头天天气有关（n＝1），那么三种天气状态（M＝3）间存在3^2＝9种转换。（表项的列和为1，是为了对应后面的条件概率计算）

于是，我们有了一个简单的一阶马尔可夫过程（first order Markov Process），它包括：

1）初始化向量（Π向量），代表系统的初始状态

2）状态集：Sunny，Cloudy，Rainy

3）状态转移矩阵（表1）

三、隐模型（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矩阵则都已经在前文中给出。ttp://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/s3_pg1.htmldD

 六、维特比算法（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))，即可求得完整的序列。
维特比算法的优势在于不仅仅考察前后两个观察状态的关系，而是全面考察整个观察序列，得出一个“最大似然”的结果。这在语音识别，通信领域有着巨大的意义——即使序列中有一两个误码，还是能够根据整个序列给出正确的解码。
原文给出的模拟计算有问题，因此不再给出链接。