有用的学习资料：NOTE|CS 228: Probabilistic Graphical Models

概率图模型(Probabilistic Graphical Model)是用图论方法以表现数个独立随机变量之关联的一种建模法。其中有向图又叫做贝叶斯网络(Bayesian Network)，无向图又叫做马尔可夫随机场(Markov Random Field)。

为什么要引入概率图模型？

  • 图模型使得联合概率分布的分解可视化了，使得一些变量之间的条件独立关系能够很容易的从图中观测出来；
  • 一些概率上的复杂的计算可以理解为图上的信息传递，这时我们就无需关注太多的复杂表达式。

贝叶斯网络

【西电数模国赛培训】0706概率图模型及其应用
贝叶斯网络是一种概率图型模型，借由有向无环图（Directed Acyclic Graphs, DAGs）中得知一组随机变量{X1,X2,...,Xn}\{X_{1},X_{2},...,X_{n}\}及其nn组条件概率分布的性质。一般而言，贝叶斯网络的有向无环图中的节点表示随机变量，它们可以是可观察到的变量，抑或是隐变量、未知参数等。连接两个节点的箭头代表此两个随机变量是具有因果关系或是非条件独立的；而两个节点间若没有箭头相互连接一起的情况就称其随机变量彼此间为条件独立。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因（Parents）”，另一个是“果（Children）”，两节点就会产生一个条件概率值。
贝叶斯网络是一个二元组，即 BN=(G,P)BN = (G, P)，其中 G=(V,E)G = (V, E)：

  • VV 是点集，与领域的随机变量一一对应
  • EE 为有向边集，反映变量之间的因果依赖关系
  • PP 为节点的概率分布，表示节点之间因果影响强度
    每个节点都有一个条件概率表 (Conditional Probability Table,CPT)，定量描述其所有父节点对该节点的作用效果。

三变量的贝叶斯网络，编码了不同类型的依赖关系：级联（a、b）、共父节点（c）和 V 结构（d）

贝叶斯网络的例子

条件独立

关于多变量概率分布的一个重要概念是条件独立性（Dawid, 1980）。考虑三个变量 aa、bb 和 cc，并假设给定 bb 和 cc 时 aa 的条件分布不依赖于 bb 的值，即有

p(a∣b,c)=p(a∣c)\begin{align} p(a|b,c) = p(a|c) \end{align}

我们称，给定 cc 时，aa 条件独立于 bb。如果我们考虑给定 cc 的条件下 aa 和 bb 的联合分布，则可以用一种略有不同的方式来表达，我们可以将其写成以下形式：

p(a,b∣c)=p(a∣b,c)p(b∣c)=p(a∣c)p(b∣c)\begin{align} p(a,b|c) &= p(a|b,c)p(b|c) \notag \\ &= p(a|c)p(b|c) \end{align}

这里我们结合使用了概率的乘积规则以及公式(8.20)。因此我们看到，在给定 cc 的条件下，aa 和 bb 的联合分布可分解为 aa 的边缘分布与 bb 的边缘分布（两者同样是在给定 cc 的条件下）的乘积。这表明，给定 cc 时，变量 aa 和 bb 是统计独立的。请注意，我们对条件独立的定义要求公式(1)，或者说等价的公式(2)，必须对 cc 的每一个可能值都成立，而不仅仅是对某些值成立。我们有时会使用条件独立的简写符号（Dawid, 1979），即

a⊥b∣c\begin{align} a \perp b \mid c \end{align}

表示给定 cc 时，aa 条件独立于 bb，并且等价于公式(1)。

如图 “三变量的贝叶斯网络” 所示，图(a)(b)(c)中的变量XX、YY在给定ZZ的条件下是条件独立的，而图(d)中的变量XX、YY在给定ZZ的条件下不是条件独立的。

条件独立性性质在将概率模型用于模式识别时扮演着重要角色，它通过简化模型的结构以及在该模型下执行推断和学习所需的计算来实现这一点。我们很快将看到相关的例子。

如果给定一个关于一组变量联合分布的表达式（以条件分布的乘积形式给出，即构成有向图基础的数学表示），那么我们原则上可以通过重复应用概率的求和规则与乘积规则，来检验任何潜在的条件独立性性质是否成立。然而在实践中，这种方法会非常耗时。图模型一个重要且优雅的特点是，联合分布的条件独立性性质可以直接从图中读取，而无需进行任何解析演算。实现这一点的通用框架被称为 dd-分离，其中的 ”dd“ 代表 ”有向的“（Pearl, 1988）。在此，我们将引出 dd-分离的概念，并给出 dd-分离准则的一般性陈述。其形式化证明可参考 Lauritzen (1996)。

隐马尔科夫模型

【西电数模】【2024年数模国赛培训】7.9 下午7-8节几类概率图模型及其应用-朱明敏】

前置知识：马尔科夫链

  • 状态空间（State Space）：马尔科夫链所有可能状态的集合，通常记为 S={s1,s2,s3,...,sk}S = \{s_1, s_2, s_3, ..., s_k\} (离散且有限的情况)。状态可以是任何定义明确的事物。
  • 转移概率（Transition Probability）：从当前状态 ii 在下一步转移到状态 jj 的概率，记为：

pij=P(Xn+1=j∣Xn=i)\begin{align} p_{ij} = P(X_{n+1} = j | X_n = i) \end{align}

这里假设时间步长是离散的（n=0,1,2,...n=0, 1, 2, ...），且转移概率 pijp_{ij} 与时间步 nn 无关（齐次马尔科夫链）。

  • 转移概率矩阵（Transition Probability Matrix）：一个方阵 PP，其元素 [P]ij=pij[P]_{ij} = p_{ij} 表示从状态 ii 转移到状态 jj 的概率。该矩阵满足两个关键性质：

P=[p11p12⋯p1kp21p22⋯p2k⋮⋮⋱⋮pk1pk2⋯pkk]P = \begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1k} \\ p_{21} & p_{22} & \cdots & p_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ p_{k1} & p_{k2} & \cdots & p_{kk} \end{bmatrix}

马尔科夫性质

过程在将来时刻 tn+1t_{n+1} 的状态 Xtn+1X_{t_{n+1}} 的条件概率分布仅依赖于其当前时刻 tnt_n 的状态 XtnX_{t_n}，而与其过去时刻 t1,t2,...,tn−1t_1, t_2, ..., t_{n-1} 的状态 Xt1,Xt2,...,Xtn−1X_{t_1}, X_{t_2}, ..., X_{t_{n-1}} 无关。用数学公式表示为：

P(Xtn+1=xj∣Xt1=xi1,Xt2=xi2,...,Xtn=xin)=P(Xtn+1=xj∣Xtn=xin)\begin{align} P(X_{t_{n+1}} = x_{j} | X_{t_1} = x_{i_1}, X_{t_2} = x_{i_2}, ..., X_{t_n}= x_{i_n}) = P(X_{t_{n+1}} = x_{j} | X_{t_n} = x_{i_n}) \end{align}

其中 xjx_j, xi1,...,xinx_{i_1}, ..., x_{i_n} 是过程可能取的状态。
马尔科夫链是一种随机过程，它具有马尔科夫性质。

例题#1：天气预测模型

假设某个地方的天气只有两种状态：晴天（Sunny, S）和雨天（Rainy, R）。气象学家根据历史数据观察到以下天气变化规律：
如果今天是晴天（S），那么明天有 80% 的概率还是晴天（S），有 20% 的概率会下雨（R）。
如果今天是雨天（R），那么明天有 60% 的概率还是雨天（R），有 40% 的概率会放晴（S）。
问题 1： 如果今天是晴天（X0=SX_0 = S），那么
a) 明天是雨天的概率是多少？
b) 后天是雨天的概率是多少？
c) 两天后是雨天的概率是多少？
解答 1a：
直接根据转移概率：P(X1=R∣X0=S)=pSR=0.2P(X_1 = R | X_0 = S) = p_{SR} = 0.2。
解答 1b：
后天的状态 X2X_2 取决于明天的状态 X1X_1。我们需要考虑所有从今天（S）到后天（R）的可能路径：
路径 1： 今天 S →0.8\overset{0.8}{\to} 明天 S →0.2\overset{0.2}{\to} 后天 R。概率 = pSS∗pSR=0.8∗0.2=0.16p_{SS} * p_{SR} = 0.8 * 0.2 = 0.16
路径 2： 今天 S →0.2\overset{0.2}{\to} 明天 R →0.6\overset{0.6}{\to} 后天 R。概率 = pSR∗pRR=0.2∗0.6=0.12p_{SR} * p_{RR} = 0.2 * 0.6 = 0.12
因为这两条路径互斥，所以后天是雨天（R）的总概率是两条路径概率之和：

P(X2=R∣X0=S)=(0.8∗0.2)+(0.2∗0.6)=0.16+0.12=0.28P(X_2 = R | X_0 = S) = (0.8 * 0.2) + (0.2 * 0.6) = 0.16 + 0.12 = 0.28

解答 1c ：
计算2 步转移概率矩阵 P(2)=P2P^{(2)} = P^2。

P2=[0.80.20.40.6][0.80.20.40.6]=[0.720.280.560.44]P^2 = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.72 & 0.28 \\ 0.56 & 0.44 \end{bmatrix}

P2P^2 的元素 [P2]ij[P^2]_{ij} 表示从状态 ii 经过 2 步转移到状态 jj 的概率。

  • 我们关心从状态 SS (第一行) 转移到状态 RR (第二列) 的概率。
  • 查看 P2P^2 矩阵的第一行第二列元素：[P2]SR=0.28[P^2]_{SR} = 0.28。
    因此，P(X2=R∣X0=S)=0.28P(X_2 = R | X_0 = S) = 0.28。

问题 2：从长远来看（即经过很多很多天后），这个地方是晴天和雨天的概率分别是多少？
解答：
稳态分布满足方程

{πSpSS+πRpRS=πSπSpSR+πRpRR=πR且πS+πR=1,πS≥0,πR≥0\begin{cases} \pi_S p_{SS} + \pi_R p_{RS} = \pi_S \\ \pi_S p_{SR} + \pi_R p_{RR} = \pi_R \end{cases} \quad \text{且} \quad \pi_S + \pi_R = 1, \quad \pi_S \geq 0, \quad \pi_R \geq 0

将转移概率代入方程组：

{πS∗0.8+πR∗0.4=πS(1)πS∗0.2+πR∗0.6=πR(2)πS+πR=1(3)\begin{cases} \pi_S * 0.8 + \pi_R * 0.4 = \pi_S \quad & (1) \\ \pi_S * 0.2 + \pi_R * 0.6 = \pi_R \quad & (2) \\ \pi_S + \pi_R = 1 \quad & (3) \end{cases}

由方程 (1)得

⇒πS=2πR(4)\Rightarrow \pi_S = 2\pi_R \quad (4)

将 (4) 代入 (3)：

2πR+πR=12\pi_R + \pi_R = 1

3πR=13\pi_R = 1

πR=13≈0.3333\pi_R = \frac{1}{3} \approx 0.3333

代入 (4)：

πS=2∗13=23≈0.6667\pi_S = 2 * \frac{1}{3} = \frac{2}{3} \approx 0.6667

因此，从长远来看，这个地方是晴天的概率约为 66.67%，是雨天的概率约为33.33%。无论今天是什么天气，经过足够长的时间后，天气分布都会稳定在这个比例上。

常返性

假设一个马尔科夫链从状态ii开始。若满足：

pi=P(永远返回状态i)=1\begin{align} p_{i} = P(永远返回状态i) = 1 \end{align}

则称状态ii是常返的（Recurrent）。若pi<1p_{i} < 1，则称状态ii为瞬态（Transient）。
若一个马尔科夫链有一些瞬态和常返态，则该过程最终只在常返态之间移动。
马尔科夫链的常返和非常返示例|1、2为常返的，3、4为非常返的
设有马尔可夫链 X={X0,X1,⋯ ,Xt,⋯ }X = \{X_0, X_1, \cdots, X_t, \cdots\}，状态空间为 SS。对于任意状态 i,j∈Si, j \in S，定义概率 pij(t)p_{ij}^{(t)} 为时刻 00 从状态 jj 出发，时刻 tt 首次转移到状态 ii 的概率，即

pij(t)=P(Xt=i,Xs≠i,s=1,2,⋯ ,t−1∣X0=j),t=1,2,⋯\begin{align} p_{ij}^{(t)} = P(X_t = i, X_s \neq i, s = 1, 2, \cdots, t - 1|X_0 = j), \quad t = 1, 2, \cdots \end{align}

若对所有状态 i,ji, j 都满足lim⁡t→∞pij(t)>0\lim_{t \to \infty} p_{ij}^{(t)} > 0，则称马尔可夫链 XX 是正常返的（Positive Recurrent）。
若状态 i∈Si \in S 是常返的，且其平均返回时间

μi=E[Ti∣X0=i]=∞\begin{align} \mu_i = \mathbb{E}[T_i \mid X_0 = i] = \infty \end{align}

即稳态概率

πi=1E[Ti∣X0=i]=0\begin{align} \pi_{i} = \frac{1}{\mathbb{E}[T_i \mid X_0 = i]} = 0 \end{align}

则称状态 ii 是零常返的（Null Recurrent）。若马尔可夫链的所有常返状态均为零常返，则称该链为零常返的。

周期性

设状态ii为马尔科夫链的一个状态，使Pii(n)>0P_{ii}^{(n)} > 0的所有正整数n(n≥1)n(n\geq1)的最大公约数称为状态ii的周期，记作did_{i}。
周期性常返型马尔科夫链，d=3

马尔科夫链的可约与不可约

设有马尔可夫链 X=X0,X1,⋯ ,Xt,⋯X = {X_0, X_1, \cdots, X_t, \cdots}，状态空间为 SS。对于任意状态 i,j∈Si, j \in S，如果存在一个时刻 t(t>0)t(t > 0) 满足

P(Xt=i∣X0=j)>0\begin{align} P(X_t = i|X_0 = j) > 0 \end{align}

即时刻 00 从状态 jj 出发，时刻 tt 到达状态 ii 的概率大于 00，则称此马尔可夫链 XX 是不可约的（Irreducible）；否则称马尔可夫链是可约的（Reducible）。可约链在大多数应用领域无实际价值，因此通常只研究不可约链。
可约的马尔科夫链

  • 不可约、非周期且正常返的马尔科夫链有唯一平稳分布存在。
  • 同时具有正常返和零常返的马尔科夫链是可约的。

可逆的马尔科夫链

设有马尔可夫链 X={X0,X1,⋯ ,Xt,⋯ }X = \{X_0, X_1, \cdots, X_t, \cdots\}，状态空间为 SS，转移概率矩阵为 PP，如果有状态分布 π=(π1,π2,⋯ )T\pi = (\pi_1, \pi_2, \cdots)^T，对于任意状态 i,j∈Si, j \in S，对任意一个时刻 tt 满足

P(Xt=i∣Xt−1=j)πj=P(Xt−1=j∣Xt=i)πi,i,j=1,2,⋯P(X_t = i|X_{t-1} = j) \pi_j = P(X_{t-1} = j|X_t = i) \pi_i, \quad i, j = 1, 2, \cdots

或简写为

pjiπj=pijπi,i,j=1,2,⋯\begin{align} p_{ji} \pi_j = p_{ij} \pi_i, \quad i, j = 1, 2, \cdots \end{align}

则称此马尔可夫链 XX 为可逆马尔可夫链（Reversible Markov Chain）。

隐马尔科夫模型的基本概念

隐马尔科夫模型(Hidden Markov Model,HMM)是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。隐藏的马尔科夫链随机生成的状态的序列称为状态序列（State Sequence）；每个状态生成一个观测，而由此产生的观测的随机序列称为观测序列（Observation Sequence）。序列的每一个位置又可以看作是一个时刻。

隐马尔科夫模型是一种特殊的贝叶斯网络。

所有可能的状态的集合Q={q1,q2,…,qN}Q = \{q_{1},q_{2},\dots,q_{N}\}，所有可能的观测的集合V={v1,v2,⋯ ,vM}V = \{v_1, v_2, \cdots, v_M\}，其中，NN 是可能的状态数，MM 是可能的观测数；
I=(i1,i2,⋯ ,iT)I = (i_1, i_2, \cdots, i_T) 是长度为 TT 的状态序列，O=(o1,o2,⋯ ,oT)O = (o_1, o_2, \cdots, o_T) 是对应的观测序列；
A=[aij]N×NA = [a_{ij}]_{N \times N}是状态转移概率矩阵，其中aij=P(it+1=qj∣it=qi),i=1,2,⋯ ,N,j=1,2,⋯ ,Na_{ij} = P(i_{t+1} = q_j | i_t = q_i), \quad i = 1, 2, \cdots, N, \quad j = 1, 2, \cdots, N是在时刻 tt 处于状态 qiq_i 的条件下在时刻 t+1t + 1 转移到状态 qjq_j 的概率。
B=[bj(k)]N×MB = [b_j(k)]_{N \times M} 是观测概率矩阵，其中，bj(k)=P(ot=vk∣it=qj),k=1,2,⋯ ,M,j=1,2,⋯ ,Nb_j(k) = P(o_t = v_k|i_t = q_j), \quad k = 1, 2, \cdots, M, \quad j = 1, 2, \cdots, N是在时刻 tt 处于状态 qjq_j 的条件下生成观测 vkv_k 的概率；
π=(πi)\pi = (\pi_i) 是初始状态概率向量，其中，πi=P(i1=qi),i=1,2,⋯ ,N\pi_i = P(i_1 = q_i), \quad i = 1, 2, \cdots, N是时刻 t=1t = 1 处于状态 qiq_i 的概率。
隐马尔可夫模型由初始状态概率向量 π\pi、状态转移概率矩阵 AA 和观测概率矩阵 BB 决定。π\pi 和 AA 决定状态序列，BB 决定观测序列。因此，隐马尔可夫模型 λ\lambda 可以用三元符号表示，即

λ=(A,B,π)\begin{align} \lambda = (A, B, \pi) \end{align}

A,B,πA, B, \pi 称为隐马尔可夫模型的三要素。
状态转移概率矩阵 AA 与初始状态概率向量 π\pi 确定了隐藏的马尔可夫链，生成不可观测的状态序列。观测概率矩阵 BB 确定了如何从状态生成观测，与状态序列综合确定了如何产生观测序列。

从定义可知，隐马尔可夫模型作了两个基本假设：

  1. 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻 tt 的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻 tt 无关：

P(it∣it−1,ot−1,⋯ ,i1,o1)=P(it∣it−1),t=1,2,⋯ ,T\begin{align} P(i_t|i_{t-1}, o_{t-1}, \cdots, i_1, o_1) = P(i_t|i_{t-1}), \quad t = 1, 2, \cdots, T \end{align}

  1. 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关：

P(ot∣iT,oT,iT−1,oT−1,⋯ ,it+1,ot+1,it,it−1,ot−1,⋯ ,i1,o1)=P(ot∣it)\begin{align} P(o_t|i_T, o_T, i_{T-1}, o_{T-1}, \cdots, i_{t+1}, o_{t+1}, i_t, i_{t-1}, o_{t-1}, \cdots, i_1, o_1) = P(o_t|i_t) \end{align}

例题#2：盒子和球模型


概率计算方法

隐马尔可夫模型（HMM）前向算法

\begin{algorithm}
\caption{Forward Algorithm}
\begin{algorithmic}
\Require 隐马尔可夫模型 $\lambda = (A, B, \pi)$，观测序列 $O = (o_1, o_2, \dots, o_T)$
\Ensure 观测序列概率 $P(O|\lambda)$

\State \textbf{初始化} ($t=1$):\\
$\alpha_1(i) = \pi_i b_i(o_1), \quad i = 1, 2, \dots, N$

\State \textbf{递推} ($t=2$ 到 $T$):
\For{$t = 2$ \To $T$}
    \For{$i = 1$ \To $N$}
        \State $\alpha_t(i) = \left[ \sum_{j=1}^N \alpha_{t-1}(j) a_{ji} \right] b_i(o_t)$
    \EndFor
\EndFor

\State \textbf{计算总概率}:
\State $P(O|\lambda) = \sum_{i=1}^N \alpha_T(i)$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Backward Algorithm}
\begin{algorithmic}
\Require 隐马尔可夫模型 $\lambda = (A, B, \pi)$，观测序列 $O = (o_1, o_2, \dots, o_T)$
\Ensure 观测序列概率 $P(O|\lambda)$

\State \textbf{初始化} ($t=T$):
\For{$i = 1$ \To $N$}
    \State $\beta_T(i) = 1$
\EndFor

\State \textbf{递推} ($t=T-1$ 到 $1$):
\For{$t = T-1$ \Downto $1$}
    \For{$i = 1$ \To $N$}
        \State $\beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j)$
    \EndFor
\EndFor

\State \textbf{计算总概率}:
\State $P(O|\lambda) = \sum_{i=1}^N \pi_i b_i(o_1) \beta_1(i)$
\end{algorithmic}
\end{algorithm}

前向算法与后向算法的具体实现见下面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import numpy as np

class HMM:
    def __init__(self, A, B, pi):
        """
        初始化HMM模型参数
        
        参数:
        A -- 状态转移矩阵 (N x N)
        B -- 观测概率矩阵 (N x M)
        pi -- 初始状态概率向量 (N)
        """
        self.A = np.array(A)    # 状态转移概率
        self.B = np.array(B)    # 观测发射概率
        self.pi = np.array(pi)  # 初始状态分布
        self.N = len(pi)        # 隐状态数量
        self.M = self.B.shape[1]     # 观测状态数量
    
    def forward(self, obs):
        """
        前向算法
        返回: 前向概率矩阵alpha和观测序列概率P(O|λ)
        """
        T = len(obs)            # 观测序列长度
        alpha = np.zeros((T, self.N))
        
        # 初始化: alpha_0(i) = pi_i * b_i(o_0)
        alpha[0] = self.pi * self.B[:, obs[0]]
        
        # 递归计算
        for t in range(1, T):
            for j in range(self.N):
                alpha[t, j] = np.sum(alpha[t-1] * self.A[:, j]) * self.B[j, obs[t]]
        
        # 观测序列概率: P(O|λ) = sum(alpha_T)
        prob = np.sum(alpha[-1])
        return alpha, prob
    
    def backward(self, obs):
        """
        后向算法
        返回: 后向概率矩阵beta
        """
        T = len(obs)            # 观测序列长度
        beta = np.zeros((T, self.N))
        
        # 初始化: beta_T-1(i) = 1
        beta[-1] = 1.0
        
        # 递归计算(从后向前)
        for t in range(T-2, -1, -1):
            for i in range(self.N):
                beta[t, i] = np.sum(
                    self.A[i, :] * self.B[:, obs[t+1]] * beta[t+1, :]
                )
        
        # 观测序列概率也可通过后向算法计算: 
        # P(O|λ) = sum(pi_i * b_i(o_0) * beta_0(i))
        prob = np.sum(self.pi * self.B[:, obs[0]] * beta[0])
        return beta, prob


# 创建HMM模型
hmm = HMM(
    A=[[0.5,0.2, 0.3], [0.3,0.5,0.2], [0.2,0.3,0.5]],         # 状态转移矩阵
    B=[[0.5,0.5], [0.4,0.6], [0.7,0.3]], # 观测概率矩阵
    pi=[0.2,0.4,0.4]                       # 初始状态概率
)


obs_seq = [0, 1, 0]

# 前向算法
alpha, prob_forward = hmm.forward(obs_seq)
print("前向概率矩阵alpha:")
print(alpha)
print(f"前向算法计算的观测序列概率: {prob_forward:.6f}\n")

# 后向算法
beta, prob_backward = hmm.backward(obs_seq)
print("后向概率矩阵beta:")
print(beta)
print(f"后向算法计算的观测序列概率: {prob_backward:.6f}\n")

# 验证两种方法计算结果一致
print(f"概率一致性检查: {np.isclose(prob_forward, prob_backward)}\n")

学习算法

\begin{algorithm}
\caption{Baum-Welch Algorithm}
\begin{algorithmic}
\Require 观测序列 $O = (o_1, o_2, \dots, o_T)$
\Ensure 隐马尔可夫模型参数 $\lambda$

\State \textbf{初始化}:
\State 对 $n=0$，选取 $a_{ij}^{(0)}$, $b_j(k)^{(0)}$, $\pi_i^{(0)}$，得到模型 $\lambda^{(0)} = (A^{(0)}, B^{(0)}, \pi^{(0)})$

\State \textbf{递推}:
\For{$n = 1, 2, \dots$}
    \State $a_{ij}^{(n+1)} = \dfrac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_t(i)}$
    \State $b_j(k)^{(n+1)} = \dfrac{\sum_{t=1}^{T} \gamma_t(j)}{\sum_{t=1}^{T} \gamma_t(j)}$
    \State $\pi_i^{(n+1)} = \gamma_1(i)$
    \State 右端各值按观测 $O$ 和模型 $\lambda^{(n)} = (A^{(n)}, B^{(n)}, \pi^{(n)})$ 计算
\EndFor

\State \textbf{终止}:
\State 得到模型参数 $\lambda^{(n+1)} = (A^{(n+1)}, B^{(n+1)}, \pi^{(n+1)})$
\end{algorithmic}
\end{algorithm}

预测算法

\begin{algorithm}
\caption{Viterbi Algorithm}
\begin{algorithmic}
\Require 模型 $\lambda = (A, B, \pi)$ 和观测 $O = (o_1, o_2, \dots, o_T)$
\Ensure 最优路径 $I^* = (i_1^*, i_2^*, \dots, i_T^*)$

\State \textbf{初始化}:
\For{$i = 1$ \To $N$}
    \State $\delta_1(i) = \pi_i b_i(o_1)$
    \State $\Psi_1(i) = 0$
\EndFor

\State \textbf{递推}:
\For{$t = 2$ \To $T$}
    \For{$i = 1$ \To $N$}
        \State $\delta_t(i) = \max_{1 \leq j \leq N} [\delta_{t-1}(j)a_{ji}]b_i(o_t)$
        \State $\Psi_t(i) = \arg\max_{1 \leq j \leq N} [\delta_{t-1}(j)a_{ji}]$
    \EndFor
\EndFor

\State \textbf{终止}:
\State $P^* = \max_{1 \leq i \leq N} \delta_T(i)$
\State $i_T^* = \arg\max_{1 \leq i \leq N} [\delta_T(i)]$

\State \textbf{最优路径回溯}:
\For{$t = T-1$ \Downto $1$}
    \State $i_t^* = \Psi_{t+1}(i_{t+1}^*)$
\EndFor
\State 求得最优路径 $I^* = (i_1^*, i_2^*, \dots, i_T^*)$
\end{algorithmic}
\end{algorithm}

马尔科夫随机场

模型定义

给定一个联合概率分布P(Y)P(Y)和表示它的无向图GG。首先定义无向图表示的随机变量之间存在的三个性质：

成对马尔科夫性(pairwise Markov property)

设uu和vv是无向图GG中任意两个没有边连接的结点，结点uu和vv分别对应随机变量YuY_u和YvY_v。其他所有结点为OO，对应的随机变量组是YOY_{O}。成对马尔科夫性是指给定随机变量组YOY_{O}的条件下随机变量YuY_{u}和YvY_{v}是条件独立的，即

P(Yu,Yv∣YO)=P(Yu∣YO)P(Yv∣YO)\begin{align} P(Y_{u},Y_{v}|Y_{O}) = P(Y_{u}|Y_{O})P(Y_{v}|Y_{O}) \end{align}

局部马尔科夫性(local Markov property)

设v∈Vv \in V是无向图GG中任意一个结点，WW是与vv有边连接的所有结点，OO是vv和WW以外的其他所有结点。vv表示的是随机变量YvY_v，WW表示的随机变量组是YWY_{W}，OO表示的随机变量组是YOY_{O}。局部马尔科夫性是指在给定随机变量组是YWY_{W}的条件下随机变量YvY_v与随机变量组是YOY_{O}是独立的，即

P(Yv,YO∣YW)=P(Yv∣YW)P(YO∣YW)\begin{align} P(Y_{v},Y_{O}|Y_{W}) = P(Y_{v}|Y_{W})P(Y_{O}|Y_{W}) \end{align}

全局马尔科夫性(global Markov property)

设AA、BB、CC是三个互不相交的结点子集，且CC在图GG中分离了AA和BB（即AA与BB之间的所有路径均经过CC）。对应的随机变量组分别为YAY_{A}、YBY_{B}、YCY_{C}。全局马尔科夫性是指在给定随机变量组YCY_{C}的条件下，随机变量组YAY_{A}与YBY_{B}是条件独立的，即

P(YA,YB∣YC)=P(YA∣YC)P(YB∣YC)\begin{align} P(Y_{A}, Y_{B} \mid Y_{C}) = P(Y_{A} \mid Y_{C}) P(Y_{B} \mid Y_{C}) \end{align}

当我们需要用无向图建模随机变量之间的依赖关系时，如何保证联合概率分布与图结构一致？对于这种情况，我们引进如下概念：
设有联合概率分布P(Y)P(Y)，由无向图G=(V,E)G = (V,E)表示，在图GG中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布P(Y)P(Y)满足成对、局部或全局马尔科夫性，就称此联合概率分布为概率无向图模型（Probabilistic Undirected Graphical Model）也称马尔可夫随机场（Markov Random Field）。

马尔科夫随机场的因子分解

设CC是无向图GG的一个结点子集。若CC中任意两个结点均有边相连，则称CC为团（clique）；若CC是GG的一个团，且无法通过添加GG中其他任一结点形成更大的团，则称CC为最大团（maximal clique）。将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因式分解。

Hammersley-Clifford定理

设CC是概率无向图模型对应的图GG中的一个最大团，对应的随机变量组为YCY_C。势函数(potential function) 是指一个定义在YCY_C上的严格正实函数ψC(YC)\psi_C(Y_C)，通常形式为指数函数ψC(YC)=exp⁡(−E(YC))\psi_C(Y_C) = \exp(-E(Y_C))（其中E(YC)E(Y_C)为能量函数），使得联合概率分布P(Y)P(Y)可表示为所有最大团上的势函数的乘积经规范化后的结果，即

P(Y)=1Z∏CψC(YC)\begin{align} P(Y) = \frac{1}{Z} \prod_{C} \psi_C(Y_C) \end{align}

其中ZZ是规范化因子，定义为

Z=∑Y∏CψC(YC)\begin{align} Z = \sum_{Y} \prod_{C} \psi_C(Y_C) \end{align}

设PP为定义在无向图GG上的严格正概率分布（即对所有可能取值，P(Y)>0P(Y) > 0）。则PP满足关于图GG的全局、局部或成对马尔科夫性，当且仅当PP可以表示为图GG中极大团CC上的势函数ψC\psi_C的乘积，即

P(Y)=1Z∏C∈CψC(YC)\begin{align} P(Y) = \frac{1}{Z} \prod_{C \in \mathcal{C}} \psi_C(Y_C) \end{align}

条件随机场

条件随机场与线性链条件随机场

设XX与YY是随机变量，P(Y∣X)P(Y|X)是在给定XX的条件下YY的条件概率分布。若随机变量YY构成一个由无向图G=(V,E)G=(V,E)表示的马尔可夫随机场，即

P(Yv∣X,Yw,w≠v)=P(Yv∣X,Yw,w∼v)\begin{align} P(Y_v | X, Y_w, w \ne v) = P(Y_v | X, Y_w, w \sim v) \end{align}

对任意结点vv成立，则称条件概率分布P(Y∣X)P(Y|X)为条件随机场(Conditional Random Field)。式中w∼vw \sim v表示在图G=(V,E)G=(V,E)中与结点vv有边连接的所有结点ww，w≠vw \ne v表示结点vv以外的所有结点，Yv,YwY_v, Y_w为结点vv与ww对应的随机变量。

设X=(X1,X2,⋯ ,Xn)X=(X_1,X_2,\cdots,X_n)，Y=(Y1,Y2,⋯ ,Yn)Y=(Y_1,Y_2,\cdots,Y_n)均为线性链表示的随机变量序列，若在给定XX的条件下，YY的条件概率分布P(Y∣X)P(Y|X)满足马尔可夫性

P(Yi∣X,Y1,⋯ ,Yi−1,Yi+1,⋯ ,Yn)=P(Yi∣X,Yi−1,Yi+1),i=1,2,⋯ ,n(Consider one−sided cases only at i=1 and i=n.)\begin{align} \begin{array}{c} P(Y_i | X, Y_1, \cdots, Y_{i-1}, Y_{i+1}, \cdots, Y_n) = P(Y_i | X, Y_{i-1}, Y_{i+1}), \\ i=1,2,\cdots,n(Consider\ one-sided\ cases\ only\ at\ i=1\ and\ i=n.) \end{array} \end{align}

则称P(Y∣X)P(Y|X)为线性链条件随机场(Linear Chain Conditional Random Field)。在标注问题中，XX表示输入观测序列，YY表示对应的输出标记序列或状态序列。
线性链条件随机场
设P(Y∣X)P(Y|X)为线性链条件随机场，则在随机变量XX取值为xx的条件下，随机变量YY取值为yy的条件概率具有线性链条件随机场的参数化形式：

P(y∣x)=1Z(x)exp⁡(∑i,kλktk(yi−1,yi,x,i)+∑i,lμlsl(yi,x,i)),\begin{align} P(y|x) = \frac{1}{Z(x)} \exp \left( \sum_{i,k} \lambda_k t_k (y_{i-1}, y_i, x, i) + \sum_{i,l} \mu_l s_l (y_i, x, i) \right), \end{align}

其中规范化因子Z(x)Z(x)定义为

Z(x)=∑yexp⁡(∑i,kλktk(yi−1,yi,x,i)+∑i,lμlsl(yi,x,i)).\begin{align} Z(x) = \sum_y \exp \left( \sum_{i,k} \lambda_k t_k (y_{i-1}, y_i, x, i) + \sum_{i,l} \mu_l s_l (y_i, x, i) \right). \end{align}

式中，tkt_k和sls_l是特征函数，λk\lambda_k和μl\mu_l是对应的权值，Z(x)Z(x)是规范化因子，求和是在所有可能的输出序列上进行的。