学习笔记：马尔可夫模型

马尔可夫模型

马尔可夫

安德雷·马尔可夫(Andrey Markov)，俄国数学家，在概率论、数理统计和随机过程等领域做出了重要贡献，20世纪初期提出了一种数学模型，即马尔可夫过程Markov Process），用于描述具有“无记忆性”的随机过程。

马尔可夫性质

马尔可夫性质（Markov Property）是概率论中的一个概念，它是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态，而与过去状态（即该过程的历史路径）是条件独立的。

简单来说，马尔可夫性质是指一个系统的状态转移概率只与当前状态有关，而与过去的状态无关。这意味着，无论过去的状态如何，系统的未来状态只取决于当前状态，而不受过去状态的影响。

马尔可夫过程/马尔科夫链

马尔可夫过程（Markov Process），也叫做马尔可夫链（Markov Chain），是一种随机过程，它具有“马尔可夫性质”，即当前状态的概率只取决于前一个状态而不受更早状态的影响。

在数学上，一个离散时间的马尔可夫过程可以由一个四元组$(S,\mathbf{P},{\pi }_0,T)$来定义，其中：

• $S$是状态空间，表示该过程可能处于哪些状态；
• $\mathbf{P}$是转移概率矩阵，表示从一个状态转移到另一个状态的概率；
• ${\pi }_0$是初始概率分布，表示该过程最初处于各种状态的概率分布；
• $T$是时间集合，表示该过程所对应的时间轴。

假设 { X n } \{X_n\} {Xn​}表示一个随机过程，其中$X_n$可以取值于状态集合$S$中的某一个状态。若对于任意的$n\ge 0$和任意的状态$i_0,i_1,\cdots ,i_{n-1},i,j\in S$，都有：

$$P(X_{n+1}=j|X_0=i_0,X_1=i_1,\cdots ,X_n=i_n)=P(X_{n+1}=j|X_n=i)$$

则称该随机过程为马尔可夫过程，其中$P(X_{n+1}=j|X_n=i)$为从状态$i$到状态$j$的转移概率，并且该转移概率与时间$n$无关。上述公式的状态转移概率只考虑前一个状态，也叫一阶马尔可夫链。

从一阶能够扩展到高阶马尔可夫过程，相应的计算复杂度也会增加，二阶马尔科夫链：

假设 { X n } \{X_n\} {Xn​}表示一个随机过程，其中$X_n$可以取值于状态集合$S$中的某一个状态。若对于任意的$n\ge 2$和任意的状态$i_0,i_1,\cdots ,i_{n-1},i,j,k\in S$，都有：

$$P(X_{n+1}=k|X_n=j,X_{n-1}=i,X_0=i_0,X_1=i_1,\cdots ,X_{n-2}=i_{n-2})=P(X_{n+1}=k|X_n=j,X_{n-1}=i)$$

上面的马尔科夫链考虑的都是在某一个状态经过固定时间间隔转移到下一个状态，定义的状态转移概率只与时间间隔有关，与起始状态无关，这种性质称为时齐性。需要注意的是，马尔可夫过程通常具有离散时间和连续时间两种形式。在离散时间马尔可夫过程中，状态变量的取值仅在离散的时间点上发生改变；而在连续时间马尔可夫过程中，状态变量可以在任意时刻随机转移。

状态转移矩阵

马尔可夫链的状态转移矩阵，通常也称为转移概率矩阵，是一个方阵，矩阵中的元素表示从当前状态到达下一状态的概率。假设该马尔可夫链具有N个状态，则其状态转移矩阵可以表示为：

P = [ p 11 p 12 ⋯ p 1 N p 21 p 22 ⋯ p 2 N ⋮ ⋮ ⋱ ⋮ p N 1 p N 2 ⋯ p N N ] P=\begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1N} \\ p_{21} & p_{22} & \cdots & p_{2N} \\ \vdots & \vdots & \ddots & \vdots \\ p_{N1} & p_{N2} & \cdots & p_{NN} \end{bmatrix} P= ​p11​p21​⋮pN1​​p12​p22​⋮pN2​​⋯⋯⋱⋯​p1N​p2N​⋮pNN​​ ​

其中，$p_{ij}$表示从状态$i$到状态$j$的概率。

$p_{ij}$ 可以通过统计该过程在实际应用中从状态 $i$ 到达状态 $j$ 的频率来估计。具体地，假设我们在观察该过程时记录了 $T$ 次状态转移，其中第 $t$ 次状态转移时从状态 $i_t$ 转移到了状态 $j_t$，则状态转移概率可以表示为：

$$p_{ij}=\frac{{\sum }_{t=1}^{T}I(i_t=i,j_t=j)}{{\sum }_{t=1}^{T}I(i_t=i)}$$

其中，$I(\cdot )$ 是指示函数，当括号中的条件成立时为1，否则为0。

该公式的含义是：状态转移概率 $p_{ij}$ 等于在所有从状态 $i$ 转移到其他状态的次数中，到达状态 $j$ 的次数比例。分母表示了从状态 $i$ 出发的总次数，分子则表示了从状态 $i$ 到状态 $j$ 的转移次数。

需要注意的是，当某个状态 $i$ 从未出现过或从该状态无法转移到其他状态时，对应的行将全为0。此外，由于状态转移概率矩阵的每一行元素之和必须等于1，因此需要对每一行的各个元素进行归一化处理。

需要注意的是，对于一个马尔可夫链，其状态转移概率需要满足以下两个条件：

1. 非负性：所有的状态转移概率$p_{ij}$都必须大于等于0。
2. 行和为1性：每一行元素之和必须等于1，即${\sum }_{j=1}^N{p}_{ij}=1$。

这两个条件保证了状态转移矩阵的合理性，且使得该马尔可夫链具有无后效性和平稳性。同时，利用状态转移矩阵，我们可以求出该马尔可夫链的平稳分布向量，用于描述该过程在长期的状态分布。

其 $m$ 步转移矩阵可以定义为 $P^m$，表示从当前状态出发，经过 $m$ 步后到达不同状态的概率矩阵。
具体地，假设该马尔可夫链共有 $N$ 个状态，则其 $m$ 步转移矩阵中第 $i$ 行第 $j$ 列表示从状态 $i$ 出发经过 $m$ 步到达状态 $j$ 的概率，即：

$$(P^m{)}_{ij}=P(X_{n+m}=j|X_n=i)$$

其中，$X_n$ 表示在时间点 $n$ 的状态。

需要注意的是，通过 $m$ 步转移矩阵，我们可以预测未来 $m$ 个时间点内的状态分布。同时，对于一个平稳的马尔可夫链，当 $m$ 趋向于无穷大时，$P^m$ 趋近于一个稳定分布 $\pi$，即：

lim ⁡ m → ∞ P m = [ π 1 π 2 ⋯ π N π 1 π 2 ⋯ π N ⋮ ⋮ ⋱ ⋮ π 1 π 2 ⋯ π N ] \lim_{m\to \infty} P^m = \begin{bmatrix}\pi_1 & \pi_2 & \cdots & \pi_N \\ \pi_1 & \pi_2 & \cdots & \pi_N \\ \vdots & \vdots & \ddots & \vdots \\ \pi_1 & \pi_2 & \cdots & \pi_N \end{bmatrix} m→∞lim​Pm= ​π1​π1​⋮π1​​π2​π2​⋮π2​​⋯⋯⋱⋯​πN​πN​⋮πN​​ ​

其中，${\pi }_i$ 表示该马尔可夫链在平稳状态下，处于状态 $i$ 的概率。

因此，通过 $m$ 步转移矩阵，我们不仅可以预测未来一定时间内的状态分布，还可以求出该马尔可夫链在长期平稳状态下的状态分布。

柯尔莫哥洛夫-开普曼定理

柯尔莫哥洛夫-开普曼定理（Kolmogorov-Chapman Theorem）是关于马尔可夫链的基本定理之一，它描述了该链在任意时刻的状态概率分布如何由其初始状态概率分布进行递推计算。

对于一个 $N$ 状态的马尔可夫链，其状态转移矩阵可以表示为 P = { p i j } P = \{p_{ij}\} P={pij​}。同时假设该链在时刻 $n$ 的状态概率分布为 ${\mathbf{\pi }}_n=[{\pi }_{n,1},{\pi }_{n,2},\cdots ,{\pi }_{n,N}]$，则柯尔莫哥洛夫-开普曼定理可以表示为：

$${\mathbf{\pi }}_{n+m}={\mathbf{\pi }}_n{P}^m$$

其中，${\mathbf{\pi }}_{n+m}$ 表示在时刻 $n+m$ 的状态概率分布，${\mathbf{\pi }}_n$ 表示在时刻 $n$ 的状态概率分布，$P^m$ 表示 $m$ 步转移矩阵，表示从当前状态出发，经过 $m$ 步到达不同状态的概率矩阵。

该定理的含义是：在已知初始状态概率分布 ${\mathbf{\pi }}_n$ 的情况下，可以通过连续应用 $P$ 的幂次来求解该链在任意时刻的状态概率分布。具体地，假设我们已知该链在时刻 $n$ 的状态概率分布 ${\mathbf{\pi }}_n$，则可以利用转移矩阵 $P$ 将其递推到时刻 $n+1$ 的状态概率分布：

$${\mathbf{\pi }}_{n+1}={\mathbf{\pi }}_{n}P$$

同理，可以继续递推得到时刻 $n+m$ 的状态概率分布：

$${\mathbf{\pi }}_{n+m}={\mathbf{\pi }}_{n+m-1}P=\cdots ={\mathbf{\pi }}_n{P}^m$$

因此，柯尔莫哥洛夫-开普曼定理提供了一种计算马尔可夫链状态概率分布的方法，对于很多实际应用都具有重要意义。

隐马尔可夫

隐马尔可夫模型(Hidden Markov Model，HMM)，用于描述一个潜在的马尔可夫过程，其中系统的状态不能直接观测到（即隐蔽的），但可以通过某些可观测的特征（观测值）进行间接推断。

隐马尔可夫模型是一个可以描述随机过程的统计模型。它由状态和可观察值组成，其中状态是不可见或“隐藏”的，而每个可观察值依赖于相应时间的状态。

设 Q = { q 1 , q 2 , ⋯   , q N } Q=\{q_1,q_2,\cdots,q_N\} Q={q1​,q2​,⋯,qN​} 表示可能的状态集合， V = { v 1 , v 2 , ⋯   , v M } V=\{v_1,v_2,\cdots,v_M\} V={v1​,v2​,⋯,vM​} 表示观测值集合。在任意时刻 $t$，系统处于 $Q$ 中的某一状态 $i_t$，但该状态对于观察者来说是不可见的，因此称之为“隐状态”。同时，系统会产生一个观测值 $o_t$，它是可见的，并满足条件概率分布 $B_i(o_t)$，其中 $i\in Q$。

隐马尔可夫模型可以用一个五元组 $(Q,V,A,B,\mathbf{\pi })$ 来描述，其中：

• $Q$：状态集合， $|Q|=N$。
• $V$：观测值集合， $|V|=M$。
• $A$：状态转移矩阵， $A_{ij}=P(i_{t+1}=j|i_t=i)$，表示从状态 $i$ 转移到状态 $j$ 的概率。
• $B$：发射矩阵， $B_i(o_t)=P(o_t|i_t=i)$，表示在状态 $i$ 下观测到观测值 $o_t$ 的概率。
• $\mathbf{\pi }$：初始状态概率分布， ${\pi }_i=P(i_1=i)$，表示在时刻 $t=1$ 系统处于状态 $i$ 的概率。

隐马尔可夫模型的主要问题包括三个方面：

• 概率计算问题（Probability Computation Problem）：给定模型参数 $\lambda$ 和观测值序列 $O$，计算出该观测序列的概率 $P(O|\lambda )$。
• 学习问题（Learning Problem）：给定观测值序列 $O$，求解使得该序列出现概率最大的模型参数 $\lambda$。
• 序列预测问题（Sequence Prediction Problem）：给定模型参数 $\lambda$ 和观测值序列 $O$，求解最可能的状态序列。

其中，概率计算问题和序列预测问题可以通过前向算法和后向算法来求解，学习问题则可以使用Baum-Welch算法（也称为EM算法）进行求解。通过这些算法，我们可以有效地应用隐马尔可夫模型来处理各种问题，例如语音识别、自然语言处理、生物信息学等领域。

在语音识别中，HMM被广泛用于将声音转换为文本。通常认为，一段语音信号是由许多不同的语音单元（音素）组成的。对于每个音素，我们可以建立一个对应的HMM，用于描述该音素的声学特征。随着语音信号的输入，我们可以使用序列预测问题来确定最可能的音素序列，并使用语言模型来转换为文本。类似地，在自然语言处理中，HMM也被应用于分词、词性标注等任务。

此外，隐马尔可夫模型还被广泛应用于基因序列分析、金融风险管理、图像和视频分析等领域。

马尔可夫随机场

马尔可夫随机场，也叫做马尔可夫网或无向图模型，是一个概率分布 $P(X)$，其中 X = { X 1 , X 2 , ⋯   , X n } X=\{X_1,X_2,\cdots,X_n\} X={X1​,X2​,⋯,Xn​} 表示一组随机变量。这些随机变量之间构成了一个无向图 $G=(V,E)$，其中 $V$ 表示所有节点的集合，$E$ 表示所有边的集合，每个节点 $i\in V$ 对应着一个随机变量 $X_i$。

为了描述这个概率分布，我们需要定义势函数（Potential Function）。对于任意子集 $C\subseteq V$，其对应的势函数定义为 ${\psi }_C(X_C)$，其中 $X_C$ 表示子集 $C$ 中所有随机变量 $X_i$ 取值的一个特定组合。若 $C$ 非空，则 ${\psi }_C(X_C)$ 一般是一个非负实数，反映了在观测到子集 $C$ 的取值时，该组随机变量的相互作用关系；若 $C$ 为空，则可以将其对应的势函数规定为常数。

基于定义的势函数和无向图，马尔可夫随机场的联合概率分布可以表示为：

$$P(X)=\frac{1}{Z}\prod _{C\in \mathcal{C}}{\psi }_C(X_C)$$

其中 $\mathcal{C}$ 表示无向图 $G$ 中所有的团， $Z$ 是归一化常数，保证概率分布的非负性和总和为1。

需要注意的是，在马尔可夫随机场中，任意两个不相邻的变量之间是条件独立的。即，对于任意子集 $A,B$，如果没有一条边连接 $A$ 和 $B$ 中的任何一个节点，则有：

$$P(X_A,X_B|X_{V-A-B})=P(X_A|X_{V-A-B})P(X_B|X_{V-A-B})$$

这种条件独立性质使得马尔可夫随机场成为了一种有效的概率模型，适用于图像处理、计算机视觉、自然语言处理等领域的各种问题。

马尔可夫聚类

马尔可夫聚类（Markov Clustering, MCL）是一种基于马尔可夫链的聚类算法，它可以用于发现复杂网络中的聚类结构。与传统的聚类算法不同，MCL基于马尔可夫链模型，将网络转化为一个矩阵，并通过迭代计算来刻画节点之间的相似性和聚类信息。

具体来说，MCL算法包含了以下两个主要步骤：

1. 转移矩阵构建

首先，我们需要将网络表示为一个转移矩阵，其中每个元素 $M_{ij}$ 表示从节点 $i$ 到节点 $j$ 的转移概率。在MCL中，通常采用随机游走策略来定义该转移矩阵。也就是说，我们假设从任意一个节点出发，等概率地随机到达相邻节点，并保证图的连通性。这样，在转移矩阵中，每一行的元素和均为1，即 ${\sum }_j{M}_{ij}=1$。

2. 迭代计算

基于转移矩阵，我们可以使用幂迭代（Power Iteration）来计算其$k$次方，得到一个新的矩阵 $M^k$。这里，$k$ 是一个大于1的整数，表示迭代的次数。通过不断迭代，矩阵中的元素会发生变化，从而刻画节点之间的相似性和聚类信息。具体来说，我们可以将矩阵中小于某个阈值的元素置为0，并将大于该阈值的元素视为聚类内部的连接。这样，我们就能够在网络中发现聚类结构，并将其可视化。

需要注意的是，MCL算法具有一定的参数敏感性，例如转移概率、迭代次数和阈值等。因此，在实际应用中，需要对参数进行调整，并进行多次试验来获得最优的聚类效果。同时，MCL算法也存在着一些局限性，例如对初始条件的依赖性、计算复杂度较高等问题，需要继续改进和优化。

一阶马尔可夫链预测例子

假设某个人在过去10天里的出行方式记录如下表所示：

这些数据可以用来估计每种出行方式的初始概率。根据上表，步行、骑车和开车的概率分别为0.3、0.4和0.3。

接着，我们还需要估计每对相邻出行方式之间的转移概率。假设我们再观察这个人在过去10天里相邻两天的出行方式，得到下面的转移情况：

我们可以将每个单元格中的数字除以该行的总和，来得到从前一天到后一天的转移概率，例如从步行到骑车的转移概率为2/3=0.6667。计算结果如下所示：

有了这些概率，我们可以用一阶马尔可夫模型来预测未来几天这个人可能的出行方式分布。例如，如果今天这个人的出行方式是步行，那么根据转移概率，明天他可能会骑车的概率为0.6667，开车的概率为0，继续步行的概率为0.3333。

假设我们希望预测未来3天这个人的出行方式，我们可以依次计算这三天后每种出行方式的概率分布。具体来说，我们可以将今天的状态作为初始状态，使用转移概率计算出明天的状态分布，再使用新的状态分布计算后天的状态分布，以此类推。

例如，我们可以先根据今天是步行，使用转移概率得到明天每种出行方式的概率分布：

接着，我们使用这个概率分布来估计后天每种出行方式的概率分布：

最后，我们使用这个概率分布来估计大后天每种出行方式的概率分布：

这样，我们就可以预测未来三天这个人可能的出行方式分布了。需要注意的是，在实践中，我们可能需要使用更多的历史数据和更复杂的模型来进行预测，以提高预测的准确率。

python编程

当涉及到马尔可夫模型时，Python提供了许多有用的工具和库。以下是一些常用于马尔可夫模型的Python库：

1. NumPy：NumPy是Python中用于数值计算的基础库。使用NumPy，可以轻松地实现矩阵和向量的运算，这在计算状态转移矩阵和预测概率分布时非常有用。

2. SciPy：SciPy是Python中用于科学计算的库。它包含许多有用的函数和数据结构，例如概率分布、最优化、插值和积分等。对于马尔可夫模型，SciPy中的概率分布函数和生成随机数的函数非常有用。

3. Pandas：Pandas是Python中一个流行的数据处理库。使用Pandas，可以轻松地处理时间序列数据和表格数据，并进行数据聚合和转换。对于马尔可夫模型，Pandas中的shift和groupby函数非常有用。

4. PyMC3：PyMC3是Python中一个用于贝叶斯统计建模和推断的库。它提供了广泛的随机变量和分布，并支持MCMC方法进行采样。对于马尔可夫模型，可以使用PyMC3构建和拟合模型，从而估计参数和预测未来状态分布。

5. HMMlearn：HMMlearn是Python中一个用于隐马尔可夫模型的库。它提供了多种隐马尔可夫模型的实现，包括高斯混合模型、离散模型和连续模型等。对于马尔可夫模型，可以使用HMMlearn来实现一些更复杂的模型。

6. TensorFlow Probability：TensorFlow Probability是TensorFlow的扩展库之一，用于概率编程和贝叶斯推断。它支持各种分布和随机过程，并提供了强大的梯度计算和优化功能。对于马尔可夫模型，可以使用TensorFlow Probability来构建和拟合复杂的模型，并进行预测和推断。

例子：

import numpy as np

# 定义状态空间，这里假设有3种不同的状态
states = ['Sunny', 'Cloudy', 'Rainy']

# 定义状态转移矩阵，这里假设在晴天下一天有40%的可能性仍然是晴天，30%的可能性变成多云，30%的可能性变成雨天
trans_matrix = np.array([[0.4, 0.3, 0.3], [0.2, 0.6, 0.2], [0.1, 0.3, 0.6]])

# 定义初始状态概率分布，这里假设初始状态为晴天的概率为50%，多云和雨天的概率均为25%
init_dist = np.array([0.5, 0.25, 0.25])

# 定义观测序列，这里假设观测到的天气情况是Sunny、Sunny、Cloudy
observations = ['Sunny', 'Sunny', 'Cloudy']

# 计算前向概率矩阵
alpha = np.zeros((len(observations), len(states)))
for i in range(len(states)):
    alpha[0][i] = init_dist[i] * (trans_matrix[i][states.index(observations[0])])
for t in range(1, len(observations)):
    for j in range(len(states)):
        alpha[t][j] = np.sum(alpha[t-1] * trans_matrix[:,j]) * (trans_matrix[j][states.index(observations[t])])

# 计算预测概率分布
predict_dist = alpha[-1] / np.sum(alpha[-1])
print("One-step-ahead prediction:", predict_dist)

在这个例子中，我们定义了一个包含3种不同状态的马尔可夫模型，即Sunny、Cloudy和Rainy。我们假设初始状态为晴天的概率为50%，多云和雨天的概率均为25%。我们还定义了状态转移矩阵，用于描述状态之间的转移关系。最后，我们定义了一个观测序列，即Sunny、Sunny、Cloudy。通过计算前向概率矩阵和预测概率分布，我们可以估计在观测到这个序列后，下一天的天气情况的概率分布。

参考书籍：
司守奎,孙玺菁 《数学建模算法与应用》(第3版)

参考文章：

学习笔记——详解马尔可夫，马尔可夫链，马尔可夫模型，隐马

【算法学习】马尔可夫过程及经典例题讲解（含代码实现）

注:上述内容部分来自chatgpt、文心一言。文章来源地址https://www.toymoban.com/news/detail-764824.html

到了这里，关于学习笔记：马尔可夫模型的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！