原题：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,...$ 处建立离散时间的过程，该过程具有被称为“状态（states）”的值，这些观察值为：$q_1,q_2,...$。状态仅对应于过程的实际值，通常由有限空间定义：$S=1,\dots Q$。

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

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

• The initial probability $P(q_1)$；
• All the transition probabilities；

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

---

II. Discrete Time Markov Chain Models (DTMC)

1. What is a Markov Chain?

DTMC

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


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

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

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

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

2. Transition probabilities

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

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

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

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

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

3. States

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

• A state $i$ is transient if $p_{ii}<1$
• A state $i$ is recurrent if $p_{ii}=1$
• A state $i$ is absorbing if $a_{ii}=1$

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

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

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

例如：

Periodic Markov Chain

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

4. Sojourn time

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

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

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

5. M-step transition

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

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

6. Probability distribution of states

设 ${\pi }_i(n)$ 为在时间 $n$ 处在状态 $i$ 的概率：${\pi }_i(n)=P(X_n=i)$

$\pi (n)=[{\pi }_1(n),{\pi }_2(n),\dots ]$ 是概率分布的向量，其取决于：

• the initial transition matrix $A$
• the initial distribution $\pi (0)$

注意，$\pi (n+1)=\pi (n)A$ 递归地：$\pi (n)=\pi (0)A^n$

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

7. Generating sequences

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

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

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

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

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

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

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

然后，选择以下数字，该数字从状态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 $\lambda$ 是由2个随机过程组合而成的序列：

• An observed one: $O=o_1,o_2,\dots ,o_T$, here the words
• A hidden one: $q=q_1,q_2,\dots q_T$, here the topic of the conversation. This is called the state of the process.

HMM模型定义为：

• 初始概率（initial probabilities）向量 $\pi =[\pi 1,\dots \pi q]$，其中 $\pi i=P(q1=i)$
• 未观察到的序列A的转移矩阵（transition matrix）：$A=[aij]=P(qt=j\mid qt-1=j)$
• 观测概率的矩阵 $B=[bki]=P(ot=sk\mid qt=i)$

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

• Independence of the observations conditionally to the hidden states: $P(o1,\dots ,ot,\dots ,oT\mid q1,\dots ,qt,\dots ,qT,\lambda )=\prod iP(ot\mid qt,\lambda )$
• The stationary Markov Chain : $P(q1,q2,\dots ,qT)=P(q1)P(q2\mid q1)P(q3\mid q2)\dots P(qT\mid qT-1)$
• Joint probability for a sequence of observations and states : $P(o1,o2,\dots oT,q1,\dots ,qT\mid \lambda )=P(o1,\dots ,oT\mid q1,\dots ,qT,\lambda )P(q1,\dots ,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(o1,o2,\dots ,oT\mid \lambda m)$。

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

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

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

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

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

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

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

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

通过递归可以表明：

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

我将不做进一步的详细介绍。你应该只记得有两种解决维特比（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中说明这些概念。