原题：Markov Chains and HMMs——Main concepts, properties, and applications
原文：HTML
作者：Maël Fabien

---

---

在本文中，将重点介绍马尔可夫模型（Markov Models）以及隐马尔可夫模型（Hidden Markov Models ，HMM）的理论及其应用。在第二篇文章中，我将介绍算法的Python实现。文章和相应的代码发布在此存储库中：Github

---

马尔可夫模型，尤其是隐马尔可夫模型（HMM）主要应用于以下领域：

• Speech recognition
• Writing recognition
• Object or face detection
• Economic Scenario Generation and specific Finance tasks
• And several NLP tasks …

---

I. Stochastic model

Discrete-Time Stochastic Process

首先，我们定义什么是随机模型（stochastic model）。从本质上讲，它是一个在时间索引 1 , 2 , . . . 1,2,... 1,2,... 处建立离散时间的过程，该过程具有被称为“状态（states）”的值，这些观察值为： q 1 , q 2 , . . . q_1,q_2,... q1​,q2​,...。状态仅对应于过程的实际值，通常由有限空间定义： S = 1 , … Q S = 1,…Q S=1,…Q。

该过程开始于初始状态 q 1 q_1 q1​。然后，根据转移概率，我们在状态之间移动。我们可以使用贝叶斯规则（Bayes Rule）来计算状态序列的概率：

为了表征模型，我们需要：

• The initial probability P ( q 1 ) P(q_1) P(q1​)；
• All the transition probabilities；

您可能会猜到，这很难实现，因为我们需要了解很多参数。

---

II. Discrete Time Markov Chain Models (DTMC)

1. What is a Markov Chain?

DTMC

离散时间马尔可夫链（DTMC）是时间和事件的离散随机过程。马尔可夫链依赖于马尔可夫属性，即过程中的有限的依赖性（limited dependence）：


我们来说明一下：考虑一个简单的迷宫，里面有一只老鼠被困住了。我们将把 q t q_t qt​ 表示为老鼠在 t t t 步后所处的迷宫的位置。我们将假设老鼠不记得它在迷宫中采取的步骤。它只是按照写在每次移动旁边的概率，随机地到达那个位置。

这里的状态可能代表许多事物，包括NLP。例如：

• 1 = Noun,
• 2 = Verb,
• 3 = Adjective…

例如，我们会对名词后面有一个动词的概率感兴趣。

2. Transition probabilities

如果离散时间马尔可夫链的转移概率不依赖于时间 t t t，则称其为同质的（homogeneous）：

该过程是一个转移矩阵（transition matrix），表示为 A = [ a i j ] , i ∈ 1 … Q , j ∈ 1 … Q A=[a_{ij}], i ∈ 1…Q, j ∈ 1…Q A=[aij​],i∈1…Q,j∈1…Q。满足以下条件时，转移矩阵是随机的：

• All entries are non-negative
• Each line sums to 1

在本示例中，转移矩阵为：

注意，如果 A A A 是随机的，则 A n A^n An 也是随机的。

3. States

有几种描述状态的方法。令 p i i p_{ii} pii​ 为离开 i i i 后返回状态 i i i 的概率：

• A state i i i is transient if p i i < 1 p_{ii}<1 pii​<1
• A state i i i is recurrent if p i i = 1 p_{ii}=1 pii​=1
• A state i i i is absorbing if a i i = 1 a_{ii}=1 aii​=1

因此，如果返回到表示为 T i i T_{ii} Tii​ 的相同状态之前的平均时间是有限的，则该状态为正循环（positive recurrent）。

如果可以从任何其他状态 i i i 起有限的步长达到状态 j j j，则DTMC是不可约的（irreducible）。不可约DTMC实际上是一个强连通图（strongly connected graph）。

如果离散时间马尔可夫链中的状态只能以大于1的某个整数的倍数返回状态，则该状态是周期性的（periodic）。

例如：

Periodic Markov Chain

否则，它称为非周期性的（aperiodic）。具有自环的状态始终是非周期性的。

4. Sojourn time

令 T i T_i Ti​ 为在跳到其他状态之前在状态 i i i 中花费的时间。

然后，停留时间（sojourn time） T i T_i Ti​ 遵循几何分布（geometric distribution）：

预计平均花费时间为 E ( T ) = 1 / a i i E(T)=1 / a_{ii} E(T)=1/aii​

5. M-step transition

从 i i i 经过 m m m 步到 j j j 的概率表示为：

我们可以看到 a 22 ( 4 ) a_{22}(4) a22​(4) 是老鼠在时间 t = 4 t = 4 t=4 处在位置2的概率。因此， f i j ( n ) f_{ij}(n) fij​(n) 给出了从i到j精确地经过 n n n 步的概率，其中：

6. Probability distribution of states

设 π i ( n ) π_{i}(n) πi​(n) 为在时间 n n n 处在状态 i i i 的概率： π i ( n ) = P ( X n = i ) π_{i}(n)=P(X_n=i) πi​(n)=P(Xn​=i)

π ( n ) = [ π 1 ( n ) , π 2 ( n ) , … ] π(n)=[π_1(n),π_2(n),…] π(n)=[π1​(n),π2​(n),…] 是概率分布的向量，其取决于：

• the initial transition matrix A A A
• the initial distribution π ( 0 ) π(0) π(0)

注意， π ( n + 1 ) = π ( n ) A π(n+1) = π(n)A π(n+1)=π(n)A 递归地： π ( n ) = π ( 0 ) A n π(n) = π(0)A^n π(n)=π(0)An

对于不可约/非周期性DTMC，分布 π ( n ) π(n) π(n) 收敛到一个极限矢量 π ， π， π，该极限矢量与 π ( 0 ) π(0) π(0) 无关，并且是以下的唯一解： π = π P π=πP π=πP。且 ∑ i π i = 1 ∑i π_i=1 ∑iπi​=1。 π i π_i πi​ 也称为平稳概率（stationary probabilities），稳态（steady state）或平衡分布（equilibrium distribution）。

7. Generating sequences

为了模拟老鼠在迷宫中的路径，需要生成序列。

例如，当我们要生成序列时，从初始状态 q 1 = 1 q_1 = 1 q1​=1 开始。总体思路是：

• 我们选择一个随机数来知道应该从哪个状态开始；
• 然后，选择一个随机数以了解我们将移至哪个状态；

假设我们得到以下简单模型：

这对应于以下矩阵 A A A 和初始向量的概率 π π π ：

生成器的工作方式如下：通过连续绘制随机数来标识哪个是过渡。

第一步，我们选择一个随机数，然后查看它在概率初始向量中的位置。这给了我们第一个状态。

然后，选择以下数字，该数字从状态q1对应于转换概率（矩阵A的第一行）。如果该值小于0.3，则保留在q1中。否则，移至q2。等等…

8. Decoding sequences

解码序列的目的是识别导致当前状态的最可能路径。例如，如果老鼠处于状态3并以5个步骤到达那里，则要确定最可能的路径。

9. Use cases

马尔可夫链的主要应用为：

• 通过解码字符序列并识别最可能的语言来识别句子的语言。
• 预测宏观经济形势，例如市场崩溃以及衰退与扩张之间的周期。
• 预测资产和期权价格，并计算信用风险。

---

III. Hidden Markov Models

隐马尔可夫模型（HMM）广泛用于：

• speech recognition
• writing recognition
• object or face detection
• part-of-speech tagging and other NLP tasks…

我建议观看 Luis Serrano关于 HMM 的介绍。VIDEO

我们将专注于词性（PoS）标记（Part-of-Speech (PoS) tagging）。词性标记是一个过程，通过该过程，我们可以将给定单词标记为名词，代词，动词，副词…

PoS可以用于例如文本到语音的转换或词义的歧义消除。

在这种特定情况下，同一个单词bear具有完全不同的含义，因此相应的PoS也有所不同。

让我们考虑以下场景。在你的办公室里，有2个同事聊得很多。你知道他们要么谈论工作，要么谈论假期。因为他们看起来很酷，你想加入他们。但是你离理解整个对话太远了，你只能理解句子中的一些单词。

在加入谈话之前，为了听起来不太奇怪，你想猜猜他谈论的是工作还是假期。例如，你的朋友可能会念这样一句话：

1. Emission probabilities

你只听到独特的单词python或bear，并试图猜测句子的上下文。既然你的朋友都是Python开发人员，那么他们在谈工作的时候，80%的时间都在谈Python。

这些概率称为排放概率（Emission Probabilities）。

2. Transition probabilities

你听他们的对话，每分钟都在努力理解主题。你朋友的谈话有某种连贯性。事实上，如果一个小时他们谈论工作，下一分钟他们谈论假期的可能性就更低。

我们可以为这种情况定义为 隐马尔可夫模型（Hidden Markov Model）：

改变对话主题或不改变对话主题的概率称为过渡概率（transition probabilities）。

• 你所理解的词语被称为观察（observations）因为你能观察到它。
• 他们谈论的主题被称为隐藏状态（hidden state），因为你无法观察到它。

3. Discrete-Time Hidden Markov Models

HMM λ λ λ 是由2个随机过程组合而成的序列：

• An observed one: O = o 1 , o 2 , … , o T O=o_1,o_2,…,o_T O=o1​,o2​,…,oT​, here the words
• A hidden one: q = q 1 , q 2 , … q T q=q_1,q_2,…q_T q=q1​,q2​,…qT​, here the topic of the conversation. This is called the state of the process.

HMM模型定义为：

• 初始概率（initial probabilities）向量 π = [ π 1 , … π q ] π=[π1,…πq] π=[π1,…πq]，其中 π i = P ( q 1 = i ) πi=P(q1=i) πi=P(q1=i)
• 未观察到的序列A的转移矩阵（transition matrix）： A = [ a i j ] = P ( q t = j ∣ q t − 1 = j ) A=[aij]=P(qt=j ∣ qt−1=j) A=[aij]=P(qt=j∣qt−1=j)
• 观测概率的矩阵 B = [ b k i ] = P ( o t = s k ∣ q t = i ) B=[bki]=P(ot=sk ∣ qt=i) B=[bki]=P(ot=sk∣qt=i)

HMM背后的主要假设（main hypothesis）是什么？

• Independence of the observations conditionally to the hidden states: P ( o 1 , … , o t , … , o T ∣ q 1 , … , q t , … , q T , λ ) = ∏ i P ( o t ∣ q t , λ ) P(o1,…,ot,…,oT ∣ q1,…,qt,…,qT, λ) = ∏i P(ot ∣ qt, λ) P(o1,…,ot,…,oT∣q1,…,qt,…,qT,λ)=∏iP(ot∣qt,λ)
• The stationary Markov Chain : P ( q 1 , q 2 , … , q T ) = P ( q 1 ) P ( q 2 ∣ q 1 ) P ( q 3 ∣ q 2 ) … P ( q T ∣ q T − 1 ) P(q1,q2,…,qT) = P(q1)P(q2∣q1)P(q3∣q2)…P(qT∣qT−1) P(q1,q2,…,qT)=P(q1)P(q2∣q1)P(q3∣q2)…P(qT∣qT−1)
• Joint probability for a sequence of observations and states : P ( o 1 , o 2 , … o T , q 1 , … , q T ∣ λ ) = P ( o 1 , … , o T ∣ q 1 , … , q T , λ ) P ( q 1 , … , q T ) P(o1,o2,…oT,q1,…,qT ∣ λ) = P(o1,…,oT ∣ q1,…,qT, λ) P(q1,…,qT) P(o1,o2,…oT,q1,…,qT∣λ)=P(o1,…,oT∣q1,…,qT,λ)P(q1,…,qT)

HMM是贝叶斯网络的子情况。

4. Find the transition probabilities

转移概率是基于我们所做的观察。我们可以假设，在仔细听完之后，每一分钟，我们都设法理解了他们正在谈论的话题。然而，这并没有给我们关于他们目前正在谈论的话题的全部信息。

在过去的15分钟里，你有15次观察，W代表工作，H代表假期。

我们注意到，在五分之二的情况下，主题工作导致主题假日，这解释了上图中的转移概率。

5. Find the emission probabilities

既然我们对他们讨论的话题有所观察，并且我们观察了讨论中使用的词语，我们可以定义排放概率的估计值：

6. Probability for a topic at a random time

假设你要去喝杯咖啡，回来的时候他们还在谈论。你根本不知道他们在说什么。在那个随机的时刻，他们谈论工作或假期的概率是多少？

从以前的观察中我们可以得出结论：他们谈论假期的次数是10倍，工作是5倍。因此，它指出，我们有1/3的机会谈论工作，有2/3的机会谈论假期。

7. If you hear the word “Python”, what is the probability of each topic?

如果听到“Python”这个词，题目是“工作还是假期”的概率可以用贝叶斯定理定义：

达到57％。

8. If you hear a sequence of words, what is the probability of each topic?

让我们从连续2个观察开始。假设我们连续听到单词“Python”和“Bear”。有哪些可能的组合？

• Python was linked to Work, Bear was linked to work
• Python was linked to Holidays, Bear was linked to work
• Python was linked to Holidays, Bear was linked to Holidays
• Python was linked to Work, Bear was linked to Holidays

这些情况可以用这种方式总结：

所以最有可能隐藏的状态是节假日和节假日。听到2个字以上怎么办？假设50？计算所有可能的路径变得非常具有挑战性！这就是为什么引入维特比算法（Viterbi Algorithm）来克服这个问题。

9. Decoding with Viterbi Algorithm

维特比算法（Viterbi Algorithm）背后的主要思想是，当我们计算最佳解码序列时，我们不会保留所有可能的路径，而只会保留对应于最大似然性的路径。

运作方式如下。我们从观察到的事件序列开始 Python, Python, Python, Bear, Bear, Python。该序列仅对应于一个观测序列： P ( o 1 , o 2 , … , o T ∣ λ m ) P(o1, o2,…, oT ∣ λm) P(o1,o2,…,oT∣λm)。

对于第一个观察，假设我们观察到Python，则主题为Work的概率为Work的概率乘以Python为Work的概率。

最可能的状态序列仅对应于：

然后我们可以继续进行下一个观察。将会发生以下情况：

对于每个位置，我们使用前面的主题是工作或假期的事实来计算概率，对于每个情况，我们只保留最大值，因为我们的目标是找到最大可能性。因此，下一步是为假日主题估计相同的事情，并保留两条路径之间的最大值。

如果对整个序列进行解码，应该会得到类似的结果。我已经对每一步的值进行了四舍五入，因此你可能会得到稍微不同的结果：

当我们观察时最可能的顺序 Python, Python, Python, Bear, Bear, Python 因此 Work, Work, Work, Holidays, Holidays, Holidays。

经过这么长时间的跟踪，如果你终于去和你的同事聊天，你应该期待他们谈论假期。

在时间T结束于状态I并对应于观测值 o 1 , … , o T o1,…,oT o1,…,oT 的最佳潜在状态序列的联合概率由 δ T ( i ) δT(i) δT(i) 表示。这是上述可能的途径之一。

通过递归可以表明：

其中 b j bj bj 表示观测矩阵B的概率， a i j aij aij 表示未观测序列的转移矩阵的值。这些参数是根据观测序列和可用状态估计的。 δ δ δ 是我们前进时每一步的最大值。

我将不做进一步的详细介绍。你应该只记得有两种解决维特比（Viterbi）的方法，即向前（forward）（如我们所见）和向后（backward）。

当我们仅部分观察序列并且面对不完整的数据时，将使用EM算法。

10. Generating a sequence

正如我们在马尔可夫链中所看到的，我们可以使用HMM生成序列。为此，我们需要：

• Generate first the hidden state q1
• From q1, generate o1, e.g Work then Python
• Then generate the transition q1 to q2
• From q2, generate o2
• …

整个进程如何运作？如上所述，这是一个两步过程，我们首先生成状态，然后生成观察值。

---

Conclusion

在本文中，我们介绍了马尔可夫链和HMM的基本理论，包括术语，假设，属性，序列生成和解码。

在下一篇文章中，我将尝试在Python中说明这些概念。