模式识别-Ch3-HMM

隐马尔可夫模型(HMM)

时间序列模型: X = { x 1 , x 2 . … , x n } X=\{\mathbf{x}_1,\mathbf{x}_2.\dots,\mathbf{x}_n\} X={x1​,x2​.…,xn​}

• $n$是序列长度
• ${\mathbf{x}}_t\in {\mathbb{R}}^d$是$X$在t时刻的观察数据
• 不满足独立假设、观测数据间具有很强的相关性。

**Q: 如何对序列数据表示、学习和推理? **

首先需要引入关于数据分布和时间轴依赖关系的概率模型，即如何表示$p({\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n)$

对$P(X)$的假定

• 方法1具有极强的灵活性、通用性，但参数量大、计算复杂度高
• 方法2具有极差的灵活性、通用性，但参数量小、计算复杂度低
• 如何平衡灵活性和复杂度?

方法	联合分布
方法1：不对数据做任何独立性假设，直接对条件分布建模(${\mathbf{x}}_t$和它的全部历史相关)	$p({\mathbf{x}}_1,\dots ,{\mathbf{x}}_n)=p({\mathbf{x}}_1){\prod }_{t=2}^{n}p({\mathbf{x}}_t|{\mathbf{x}}_1,{\mathbf{x}}_2.\dots ,{\mathbf{x}}_{t-1})$
方法2：假设 { x 1 , x 2 . … , x n } \{\mathbf{x}_1,\mathbf{x}_2.\dots,\mathbf{x}_n\} {x1​,x2​.…,xn​}独立，只对边缘分布建模	$p({\mathbf{x}}_1,\dots ,{\mathbf{x}}_n)={\prod }_{i=1}^{n}p({\mathbf{x}}_t)$
方法3：(Markov性)${\mathbf{x}}_t$只与${\mathbf{x}}_{t-1}$有关$p({\mathbf{x}}_t|{\mathbf{x}}_1,\dots ,{\mathbf{x}}_{t-1})=p({\mathbf{x}}_t|{\mathbf{x}}_{t-1})$	$p({\mathbf{x}}_1,\dots ,{\mathbf{x}}_n)=p({\mathbf{x}}_1){\prod }_{t=2}^{n}p({\mathbf{x}}_t|{\mathbf{x}}_{t-1})$

HMM的表示

Markov链

静态、离散、一阶Markov链的联合分布：
$$p({\mathbf{x}}_1,\dots ,{\mathbf{x}}_n)=p({\mathbf{x}}_1)\prod _{t=2}^{n}p({\mathbf{x}}_t|{\mathbf{x}}_{t-1})$$

参数	说明
离散马氏链	x t ∈ { 1 , 2 , … , K } , K \mathbf{x}_t\in\{1,2,\dots,K\},K xt​∈{1,2,…,K},K为状态数
静态马氏链	转移概率$p({\mathbf{x}}_{\mathbf{t}}|{\mathbf{x}}_{\mathbf{t}-1})$只与状态有关，与时间$t$无关
初始状态分布	$p({\mathbf{x}}_1)=\pi \in {\mathbb{R}}^K$
状态转移概率	$p({\mathbf{x}}_{\mathbf{t}}|{\mathbf{x}}_{\mathbf{t}-1})=A\in {\mathbb{R}}^{K\times K}$

例子

• x t ∈ { 雨天 , 晴天 , 阴天 } , K = 3 \mathbf{x}_t \in \{雨天,晴天,阴天\}, K = 3 xt​∈{雨天,晴天,阴天},K=3
• 初始状态分布：$\pi =[0.1,0.6,0.3]$
• 状态转移概率：

$$A=\left[\begin{array}{ccc}0.1& 0.4& 0.5\\ 0.1& 0.6& 0.3\\ 0.2& 0.4& 0.4\end{array}\right]$$

已知第$t$天是雨天，第$t+2$天是晴天的概率？
$$\begin{gathered} p({\mathbf{x}}_t)=[1,0,0{]}^T \\ p({\mathbf{x}}_{t+1})=A^{T}p({\mathbf{x}}_t)=[0.1,0.4,0.5{]}^T \\ p({\mathbf{x}}_{t+2})=A^{T}p({\mathbf{x}}_{t+1})=[0.15,0.48,0.37{]}^T \end{gathered}$$

HMM简介

• HMM的基本思想
  • 观测序列由一个不可见的马尔可夫链生成。
  • HMM的随机变量可分为两组：
    • 状态变量 { z 1 , z 2 , ⋯ , z n } \{z_1,z_2,\cdots,z_n\} {z1​,z2​,⋯,zn​}：构成一阶、离散、静态马尔可夫链。用于描述系统内部的状态变化，通常是隐藏的，不可被观测的。其中，$z_t$表示第$t$时刻系统的状态。
    • 观测变量 { x 1 , x 2 , ⋯ , x n } \{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\} {x1​,x2​,⋯,xn​}：其中，${\mathbf{x}}_t$表示第$t$时刻的观测变量，通过条件概率$p({\mathbf{x}}_t|z_t)$由状态变量$z_t$生成；根据具体问题，${\mathbf{x}}_t$可以是离散或连续，一维或多维。
  • 主要用于时序数据建模，在CV、NLP、语音识别中有诸多应用。

HMM的图结构

• 在图中，箭头表示依赖关系。
• $t$时刻的观测变量${\mathbf{x}}_t$的取值仅依赖于状态变量$z_t$。当$z_t$已知，${\mathbf{x}}_t$与其它状态独立。
• $t$时刻的状态变量$z_t$的取值仅依赖于$t-1$时刻的状态变量$z_{t-1}$。当$z_{t-1}$已知，$z_t$与其余$t-2$个状态独立。即 { z t } \{z_t\} {zt​}构成马尔可夫链，系统下一刻的状态仅由当前状态决定，不依赖于以往任何状态。

HMM中的条件独立性:
$$\begin{gathered} p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n|z_t)=p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_t|z_t)p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t) \\ p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n|z_{t-1},z_t)=p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_{t-2}|z_{t-1})p({\mathbf{x}}_{t-1}|z_{t-1})p({\mathbf{x}}_t|z_t)p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t) \\ p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_{t-1}|{\mathbf{x}}_t,z_t)=p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_{t-1}|z_t) \\ p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_{t-1}|z_{t-1},z_t)=p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_{t-1}|z_{t-1}) \\ p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|{\mathbf{x}}_t,z_t)=p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t) \\ p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t,z_{t+1})=p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_{t+1}) \end{gathered}$$

HMM联合概率分布:
$$p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n,z_1,\cdots ,z_n)=p(z_1)\prod _{t=2}^{n}p(z_t|z_{t-1})\prod _{t=1}^{n}p({\mathbf{x}}_t|z_t)$$

基本要素	对应公式
初始状态概率向量$\pi \in R^K$	${\pi }_k=P(z_1=k),1\le k\le K$
状态转移概率矩阵$A\in R^{K\times K}$	$A_{i,j}=P(z_t=j|z_{t-1}=i),1\le i,j\le K$
发射概率矩阵$B\in R^{K\times M}$	离散：$B_{i,j}=P({\mathbf{x}}_t=j|z_t=i),1\le i\le K,1\le j\le M$

例子

HMM的学习

三个基本问题

三个基本问题	简述	说明
给定模型$[A,B,\pi ]$，如何有效地计算其产生观测序列 x = { x 1 , x 2 , ⋯ , x n } \mathbf{x}=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\} x={x1​,x2​,⋯,xn​}的概率$P(\mathbf{x}|A,B,\pi )$？	评估模型与观测数据的匹配程度。	许多任务需要根据以往的观测序列来预测当前时刻最有可能的观测值。
给定模型$[A,B,\pi ]$和观测序列 x = { x 1 , x 2 , ⋯ , x n } \mathbf{x}=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\} x={x1​,x2​,⋯,xn​}，如何找到与此观测序列相匹配的状态序列 z = { z 1 , z 2 , ⋯ , z n } z=\{z_1,z_2,\cdots,z_n\} z={z1​,z2​,⋯,zn​}？	根据观测序列推断出隐藏的模型状态。(解码问题)	在语言识别中，观测值为语音信号，隐藏状态为文字，目标就是观测信号推断最有可能的状态。
给定观测序列 x = { x 1 , x 2 , ⋯ , x n } \mathbf{x}=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\} x={x1​,x2​,⋯,xn​}，如何调整模型参数$[A,B,\pi ]$使该序列出现的概率$P(\mathbf{x}|A,B,\pi )$最大？	如何模型使其能够最好地描述观测数据。(参数估计-学习问题)	在大多数实际应用中，人工指定参数已变得不可行，需要根据训练样本学习最优模型。

参数学习的基本任务

通过拟合观测序列，确定HMM中的参数:$\theta =(\pi ,A,B)$

EM算法步骤:

• E Step: 对给定的$\theta$，估计：
  $$q(z_1,\cdots ,z_n)=p_{\theta }(z_1,\cdots ,z_n|{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n)$$

• M Step: 用估计出的$q(z_1,\cdots ,z_n)$，更新$\theta$：
  $$\theta =\arg \underset{\theta }{\max }\sum _{z}q(z_1,\cdots ,z_n)\ln p_{\theta }({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n,z_1,\cdots ,z_n)$$

• E步和M步迭代运行，直至收敛

M step: 更新$\theta$

$p_{\theta }({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n,z_1,\cdots ,z_n)=p_{\theta }(z_1){\prod }_{t=2}^n{p}_{\theta }(z_t|z_{t-1}){\prod }_{t=1}^n{p}_{\theta }({\mathbf{x}}_t|z_t)$

$$\begin{array}{rl}Q(\theta ,{\theta }^{old})& =\sum _{z}q(z_1,\cdots ,z_n)\ln p_{\theta }({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n,z_1,\cdots ,z_n)\\ & =\sum _{z}q(z_1,\cdots ,z_n)(\ln p_{\theta }(z_1)+\sum _{t=2}^n\ln p_{\theta }(z_t|z_{t-1})+\sum _{t=1}^n\ln p_{\theta }({\mathbf{x}}_t|z_t))\\ & =\sum _{z_1=1}^{K}q(z_1)\ln p_{\theta }(z_1)+\sum _{t=2}^n\sum _{z_{t-1},z_t=1}^{K}q(z_{t-1},z_t)\ln p_{\theta }(z_t|z_{t-1})+\sum _{t=1}^n\sum _{z_t=1}^{K}q(z_t)\ln p_{\theta }({\mathbf{x}}_t|z_t)\\ & =\sum _{z_1=1}^{K}q(z_1)\ln p_{\theta }({\pi }_{z_1})+\sum _{t=2}^n\sum _{z_{t-1},z_t=1}^{K}q(z_{t-1},z_t)\ln A_{z_{t-1},z_t}+\sum _{t=1}^n\sum _{z_t=1}^{K}q(z_t)\ln B_{z_t,x_t}\end{array}$$

用拉格朗日乘子法优化以下问题，可得：

参数	计算	约束	结果
$\pi$	$\arg {\max }_{\pi }{\sum }_{z_1=1}^{K}q(z_1)\ln {\pi }_{z_1}$	${\sum }_{k=1}^K{\pi }_k=1$	${\pi }_k=q(z_1=k)$
$A$	$\arg {\max }_A{\sum }_{t=2}^n{\sum }_{z_{t-1},z_t=1}^{K}q(z_{t-1},z_t)\ln A_{z_{t-1},z_t}$	$\forall i{\sum }_{j=1}^K{A}_{i,j}=1$	$A_{i,j}=\frac{{\sum }_{t=2}^{n}q(z_{t-1}=i,z_t=j)}{{\sum }_{t=2}^n{\sum }_{k=1}^{K}q(z_{t-1}=i,z_t=k)}$
$B$	$\arg {\max }_B{\sum }_{t=1}^n{\sum }_{z_t=1}^{K}q(z_t)\ln B_{z_t,{\mathbf{x}}_t}$	$\forall i{\sum }_{j=1}^M{B}_{i,j}=1$	B i , j = ∑ t = 1 n 1 { x t = = j ^ } q ( z t = i ) ∑ t = 1 n q ( z t = i ) B_{i,j} = \frac{\sum_{t = 1}^{n} \mathbf{1}\{\mathbf{x}_t == \hat j\}q(z_t = i)}{\sum_{t = 1}^{n} q(z_t = i)} Bi,j​=∑t=1n​q(zt​=i)∑t=1n​1{xt​==j^​}q(zt​=i)​

E Step: 对给定的$\theta$，估计$q(z_1,\cdots ,z_n)=p_{\theta }(z_1,\cdots ,z_n|{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n)$

只需估计：
$$\begin{gathered} q(z_t)=p_{\theta }(z_t|{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n) \\ q(z_{t-1},z_t)=p_{\theta }(z_{t-1},z_t|{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n) \end{gathered}$$
以下省略$\theta$：
$$\begin{array}{rl}q(z_t)& =\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n,z_t)}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)}=\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n|z_t)p(z_t)}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)}\\ & =\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_t|z_t)p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t)p(z_t)}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)}\\ & =\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_t,z_t)p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t)}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)}\\ & \\ q(z_{t-1},z_t)& =\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n,z_{t-1},z_t)}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)}\\ & =\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n,z_t|z_{t-1})p(z_{t-1})}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)}\\ & =\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_{t-1}|z_{t-1})p({\mathbf{x}}_t,\cdots ,{\mathbf{x}}_n,z_t|z_{t-1})p(z_{t-1})}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)}\\ & =\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_{t-1},z_{t-1})p({\mathbf{x}}_t,\cdots ,{\mathbf{x}}_n,z_t|z_{t-1})}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)}\end{array}$$

前向-后向算法(forward-backward algorithm)

$$\begin{gathered} q(z_t)=\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_t,z_t)p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t)}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)} \\ q(z_{t-1},z_t)=\frac{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_{t-1},z_{t-1})p({\mathbf{x}}_t,\cdots ,{\mathbf{x}}_n,z_t|z_{t-1})p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t)}{p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)} \end{gathered}$$

• 前向概率：${\alpha }_t(z_t)=p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_t,z_t)$

• 后向概率：${\beta }_t(z_t)=p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t)$

• 观测概率：$p({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)={\sum }_{k=1}^K{\alpha }_n(z_n)$
  $$q(z_t)=\frac{{\alpha }_t(z_t){\beta }_t(z_t)}{{\sum }_{z_n=1}^K{\alpha }_n(z_n)},q(z_{t-1},z_t)=\frac{{\alpha }_{t-1}(z_{t-1})p(z_t|z_{t-1})p({\mathbf{x}}_t|z_t){\beta }_t(z_t)}{{\sum }_{z_n=1}^K{\alpha }_n(z_n)}$$

从前向后计算，$t=1,\cdots ,n$

$$\begin{array}{rl}{\alpha }_t(z_t)& =p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_t,z_t)=\sum _{z_{t-1}}p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_t,z_{t-1},z_t)\\ & =\sum _{z_{t-1}}p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_t,z_t|z_{t-1})p(z_{t-1})\\ & =\sum _{z_{t-1}}p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_{t-1}|z_{t-1})p({\mathbf{x}}_t,z_t|z_{t-1})p(z_{t-1})\\ & =\sum _{z_{t-1}}p({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_{t-1},z_{t-1})p({\mathbf{x}}_t,z_t|z_{t-1})\\ & =\sum _{z_{t-1}}{\alpha }_{t-1}(z_{t-1})p(z_t|z_{t-1})p({\mathbf{x}}_t|z_t)\\ & =p({\mathbf{x}}_t|z_t)\sum _{z_{t-1}}{\alpha }_{t-1}(z_{t-1})p(z_t|z_{t-1})\end{array}$$

从后向前计算，$t=n,n-1,\cdots ,1$

$$\begin{array}{rl}{\beta }_t(z_t)& =p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t)=\sum _{z_{t+1}}p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n,z_{t+1}|z_t)\\ & =\sum _{z_{t+1}}p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_t,z_{t+1})p(z_{t+1}|z_t)\\ & =\sum _{z_{t+1}}p({\mathbf{x}}_{t+1},\cdots ,{\mathbf{x}}_n|z_{t+1})p(z_{t+1}|z_t)\\ & =\sum _{z_{t+1}}p({\mathbf{x}}_{t+2},\cdots ,{\mathbf{x}}_n|z_{t+1})p({\mathbf{x}}_{t+1}|z_{t+1})p(z_{t+1}|z_t)\\ & =\sum _{z_{t+1}}{\beta }_{t+1}(z_{t+1})p({\mathbf{x}}_{t+1}|z_{t+1})p(z_{t+1}|z_t)\end{array}$$

HMM的解码

• 在实际问题中，状态变量通常有明确的含义。如语音识别中，$z_t$表示语音信号${\mathbf{x}}_t$对应的文本。因此，经常需要根据观测序列推断状态序列。

• 对给定的HMM模型$\theta =(\pi ,A,B)$和观测序列 { x 1 , x 2 , ⋯ , x n } \{\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_n\} {x1​,x2​,⋯,xn​}，求解：
  $$z^{\ast }=\arg \underset{z}{\max }{p}_{\theta }(z_1,\cdots ,z_n|{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n)$$
  $z^{\ast }$是最大后验概率对应的状态序列，也称为最优状态路径。

• 这对应分类问题中的最大后验概率决策，$z_t$对应${\mathbf{x}}_t$的类别。

• 与分类中对${\mathbf{x}}_t$独立解码不同，HMM需要联合解码。

状态路径：$z_1,\cdots ,z_n$

• 对于给定的HMM模型和观测序列 { x 1 , x 2 , ⋯ , x n } \{\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_n\} {x1​,x2​,⋯,xn​}，不同状态路径对应不同的后验概率：$p_{\theta }(z_1,\cdots {,}_n|{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n)$。
• 共有$K^n$条可能的状态路径，对应$K^n$个概率值。
• 直接计算这些概率，然后选出$z^{\ast }$的复杂度为$O(K^n)$。

HMM的解码算法：维特比算法（Viterbi, 1967）

• 最优子问题：寻找以状态$z_t$结束的前$t$步最优状态路径
  $$\begin{gathered} w_t(z_t)\equiv \max \ln p_{\theta }({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_t,z_1,\cdots ,z_{t-1},z_t)\in R^K \\ {z}^{\ast }=\arg \underset{z}{\max }{p}_{\theta }(z_1,\cdots ,z_n|{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n)\iff \arg \underset{z}{\max }{p}_{\theta }(z_1,\cdots ,z_n,{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_n) \end{gathered}$$

• 动态规划算法

  • For$z_1=1,\cdots ,K$：$w_1(z_1)=\ln p(z_1)+\ln p({\mathbf{x}}_1|z_1)$

  • For$t=2,\cdots ,n$：

    • For$z_t=1,\cdots ,K$：
      w t ( z t ) = ln ⁡ p ( x t ∣ z t ) + max ⁡ z t − 1 ∈ { 1 , ⋯ , K } { w t − 1 ( z t − 1 ) + ln ⁡ p ( z t ∣ z t − 1 ) } w_t(z_t) = \ln p(\mathbf{x}_t | z_t) + \max_{z_{t - 1} \in \{1, \cdots, K\}} \{w_{t - 1}(z_{t - 1}) + \ln p(z_t | z_{t - 1})\} wt​(zt​)=lnp(xt​∣zt​)+zt−1​∈{1,⋯,K}max​{wt−1​(zt−1​)+lnp(zt​∣zt−1​)}

• 计算复杂度：$O(n{K}^2)$