专栏首页用户2133719的专栏CS229 课程笔记之十四:隐马尔可夫模型基础

CS229 课程笔记之十四:隐马尔可夫模型基础

1 马尔可夫模型

马尔可夫模型是一种推理时间序列上状态变化的形式。给定一个「状态集」

S=\left\{s_{1}, s_{2}, \ldots s_{|S|}\right\}

,我们可以观察出一个随时间变化的序列

\vec{z} \in S^{T}

。以一个天气系统的状态

S = \{sun, cloud, rain\}

为例,我们可以观察出一个 5 天(

T= 5

)的天气变化序列

\{z_1 = s_{sun}, z_2 = s_{cloud},z_3 = s_{cloud},z_4 = s_{rain},z_5 = s_{cloud}\}

.

如果不进行某些限定,则时间

t

的状态

s_j

将会是任意数量变量的函数,将难以建模。因此,我们会提出两个「马尔可夫假设」来便于我们建模。第一个假设是「有限地平线假设」(limited horizon assumption),该假设指出时间

t

的状态的概率分布只取决于

t-1

时刻的状态。直观的理解就是时刻

t

状态代表了对过去的“足够”总结,可以合理地预测未来

P\left(z_{t} | z_{t-1}, z_{t-2}, \ldots, z_{1}\right)=P\left(z_{t} | z_{t-1}\right)

第二个假设是「平稳过程假设」(stationary process assumption),该假设指出给定当前状态,下一个状态的条件分布不随时间变化,即:

P\left(z_{t} | z_{t-1}\right)=P\left(z_{2} | z_{1}\right) ; t \in 2 \ldots T

为了方便,我们会假定存在一个初始状态和初始观察

z_{0} \equiv s_{0}

,其中

s_0

表示时刻 0 时状态的初始概率分布(可以理解为一个未知状态)。这种符号定义可以允许我们将真实初始状态

z_1

的先验分布用

P\left(z_{1} | z_{0}\right)

来表示。

因为对于任何状态序列都有

z_0 = s_0

,所以:

P\left(z_{t} | z_{t-1}, \ldots, z_{1}\right)=P\left(z_{t} | z_{t-1}, \ldots, z_{1}, z_{0}\right)

我们通过定义一个状态转移矩阵

A \in \mathbb{R}^{(|S|+1) \times(|S|+1)}

来参数化这些转变。

A_{i j}

的值表示在任意时刻

t

从状态

i

转移到状态

j

的概率。下面给出关于天气状态的转换矩阵:

从概率可以看出天气是自相关的,即晴天趋向于保持晴天,多云趋向于保持多云。这种模式出现在很多马尔可夫模型中,可以总结为转换矩阵的「强对角性」。此外,在矩阵中,由初始状态转换为其他三个状态的概率是相同的。

1.1 马尔可夫模型的两个问题

基于上述两个假设以及状态转移矩阵

A

,针对一个马尔科夫链中的状态序列,我们可以提出两个问题:

  1. 一个特定的状态序列
\vec{z}

的概率是多少?

  1. 我们如何估计
A

的参数来最大化一个观测序列

\vec{z}

的概率?

1.1.1 一个状态序列的概率

我们可以通过概率的链式法则来计算一个特定状态序列

\vec{z}

的概率:

\begin{aligned} P(\vec{z}) &=P\left(z_{t}, z_{t-1}, \ldots, z_{1} ; A\right) \\ &=P\left(z_{t}, z_{t-1}, \ldots, z_{1}, z_{0} ; A\right) \\ &=P\left(z_{t} | z_{t-1}, z_{t-2}, \ldots, z_{1} ; A\right) P\left(z_{t-1} | z_{t-2}, \ldots, z_{1} ; A\right) \ldots P\left(z_{1} | z_{0} ; A\right) \\ &=P\left(z_{t} | z_{t-1} ; A\right) P\left(z_{t-1} | z_{t-2} ; A\right) \ldots P\left(z_{2} | z_{1} ; A\right) P\left(z_{1} | z_{0} ; A\right) \\ &=\prod_{t=1}^{T} P\left(z_{t} | z_{t-1} ; A\right) \\&= \prod_{t=1}^{T} A_{z_{t-1} z_{t}}\end{aligned}

第三行使用了链式法则(也可以理解为贝叶斯定理的重复),

P(z_1 |z_0)

实际上是先验分布;第四行来源于马尔可夫假设。

以之前的天气序列为例,我们可以将

P\left(z_{1}=s_{s u n}, z_{2}=s_{c l o u d}, z_{3}=s_{r a i n}, z_{4}=s_{r a i n}, z_{5}=s_{c l o u d}\right)

表示为:

P\left(s_{s u n} | s_{0}\right) P\left(s_{c l o u d} | s_{s u n}\right) P\left(s_{r a i n} | s_{c l o u d}\right) P\left(s_{r a i n} | s_{r a i n}\right) P\left(s_{c l o u d} | s_{r a i n}\right) \\= .33 \times .1 \times .2 \times .7 \times .2

1.1.2 最大似然参数赋值

从学习的观点来看,我们希望找到

A

的参数来最大化观测序列

\vec{z}

的对数似然函数。一个马尔科夫模型的对数似然函数定义如下:

\begin{aligned} l(A) &=\log P(\vec{z} ; A) \\ &=\log \prod_{t=1}^{T} A_{z_{t-1} z_{t}} \\ &=\sum_{t=1}^{T} \log A_{z_{t-1} z_{t}} \\ &=\sum_{i=1}^{|S|} \sum_{j=1}^{|S|} \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \log A_{i j} \end{aligned}

对于该优化问题,存在两个约束条件:

  • 每个状态向下一个状态转变的概率之和为 1
A

的所有元素都是非负的

基于以上两个约束,我们可以构建拉格朗日乘子:

\begin{align*} \max_{A} &\quad l(A) \\ \text{s.t.} &\quad \sum_{j=1}^{|S|} A_{i j}=1,\;i=1 . .|S| \\ &\quad A_{i j} \geq 0, \; i, j=1 . .|S| \end{align*}

我们将等式约束用到乘子构建中,而不等式约束可以被忽略,因为解总是为正数。

构建后的拉格朗日乘子为:

\mathcal{L}(A, \alpha)=\sum_{i=1}^{|S|} \sum_{j=1}^{|S|} \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \log A_{i j}+\sum_{i=1}^{|S|} \alpha_{i}\left(1-\sum_{j=1}^{|S|} A_{i j}\right)

求偏导可以得到:

\begin{aligned} \frac{\partial \mathcal{L}(A, \alpha)}{\partial A_{i j}} &=\frac{\partial}{\partial A_{i j}}\left(\sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \log A_{i j}\right)+\frac{\partial}{\partial A_{i j}} \alpha_{i}\left(1-\sum_{j=1}^{|S|} A_{i j}\right) \\ &=\frac{1}{A_{i j}} \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\}-\alpha_{i} \equiv 0 \\ & \Rightarrow A_{i j} =\frac{1}{\alpha_{i}} \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \end{aligned}

将上式代回再对

\alpha

求偏导可得:

\begin{aligned} \frac{\partial \mathcal{L}(A, \beta)}{\partial \alpha_{i}} &=1-\sum_{j=1}^{|S|} A_{i j} \\ &=1-\sum_{j=1}^{|S|} \frac{1}{\alpha_{i}} \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \equiv 0 \\ \Rightarrow \alpha &=\sum_{j=1}^{|S|} \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \\ &=\sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i}\right\} \end{aligned}

将上式代回

A_{ij}

的表达式可以得到最终的输出为:

\hat{A}_{i j}=\frac{\sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\}}{\sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i}\right\}}

对上式的直观理解:从状态

i

转换至状态

j

的最大似然概率即为

i

j

转移的实际次数除以我们处于状态

i

的总次数。

2 隐马尔可夫模型

马尔科夫模型是对时间序列数据的有力抽象,但是如果我们无法观测到序列的状态,就无法进行抽象。「隐马尔可夫模型」可以用来解决这个问题,我们无法观测到实际的状态序列,而是观测到由状态生成的某个输出序列。

正式来说,在一个隐马尔可夫模型中,我们有如下序列:

一个「观测输出序列」

x=\left\{x_{1}, x_{2}, \dots, x_{T}\right\}

其取值自输出字典

V=\left\{v_{1}, v_{2}, \dots, v_{|V|}\right\}

,即

x_{t} \in V, t=1 .. T

一个「状态序列」

z=\left\{z_{1}, z_{2}, \dots, z_{T}\right\}

其取值自状态字典

S=\left\{s_{1}, s_{2}, \dots s_{|S|}\right\}

,即

z_{t} \in S, t=1 \ldots T

。该序列是「未知」的(无法观测)。

在隐马尔可夫模型模型中,包含有两个矩阵:

  • 一个是之前提到的状态转移矩阵
A

A_{ij}

表示从状态

i

转移到状态

j

的概率

  • 另一个矩阵
B

用于对由隐藏状态生成观测输出的概率建模

我们需要提出「输出独立性假设」

P\left(x_{t}=v_{k} | z_{t}=s_{j}\right)=P\left(x_{t}=v_{k} | x_{1}, \ldots, x_{T}, z_{1}, \ldots, z_{T}\right) = B_{jk}
B_{jk}

表示给定当前时间的状态

s_j

,由该状态生成输出

v_k

的概率。

2.1 关于隐马尔可夫模型的三个问题

对于隐马尔可夫模型,我们可以提出三个基本问题:

  1. 观测序列的概率是多少?
  2. 最可能生成该观测序列的状态序列是什么?
  3. 给定一些数据,我们如何学习出矩阵
A

B

的参数?

2.2 观测序列的概率:前向算法

在 HMM 中,我们假设观测序列是通过如下流程生成的:

假设存在一个基于时间序列的状态序列

\vec{z}

,该序列由马尔可夫模型生成,以状态转移矩阵

A

为参数;在每个时间步

t

,我们选择一个输出

x_t

作为状态

z_t

的函数。因此,为了计算观测序列的概率,我们需要将给定所有可能状态序列的

\vec{x}

的似然概率相加:

\begin{aligned} P(\vec{x} ; A, B) &=\sum_{\vec{z}} P(\vec{x}, \vec{z} ; A, B) \\ &=\sum_{\vec{z}} P(\vec{x} | \vec{z} ; A, B) P(\vec{z} ; A, B) \end{aligned}

上述公式对任何概率分布均成立。HMM 假设可以让我们对上述表达式进行简化:

\begin{aligned} P(\vec{x} ; A, B) &=\sum_{\vec{z}} P(\vec{x} | \vec{z} ; A, B) P(\vec{z} ; A, B) \\ &=\sum_{\vec{z}}\left(\prod_{t=1}^{T} P\left(x_{t} | z_{t} ; B\right)\right)\left(\prod_{t=1}^{T} P\left(z_{t} | z_{t-1} ; A\right)\right) \\ &=\sum_{\vec{z}}\left(\prod_{t=1}^{T} B_{z_{t} x_{t}}\right)\left(\prod_{t=1}^{T} A_{z_{t-1} z_{t}}\right) \end{aligned}

上述推导基于输出独立性假设及马尔可夫模型中提到的两个假设。然而,该求和是基于所有可能的状态序列,而

z_t

|S|

个可能的取值,所以直接求和的时间复杂度为

O(|S|^T)

T

是总时间步数)。

幸运的是,我们可以通过一种动态规划算法:「前向算法」来更快地计算

P(\vec{x} ; A, B)

。首先我们定义一个量:

\alpha_{i}(t)=P\left(x_{1}, x_{2}, \ldots, x_{t}, z_{t}=s_{i} ; A, B\right)

,其代表时间长度为

t

的所有观测值(状态不限)以及在时刻

t

状态为

s_i

的联合概率。

通过这样一个量,我们可以将之前的公式表示为:

\begin{aligned} P(\vec{x} ; A, B) &=P\left(x_{1}, x_{2}, \ldots, x_{T} ; A, B\right) \\ &=\sum_{i=1}^{|S|} P\left(x_{1}, x_{2}, \ldots, x_{T}, z_{T}=s_{i} ; A, B\right) \\ &=\sum_{i=1}^{|S|} \alpha_{i}(T) \end{aligned}

我们可以通过如下算法来快速地进行求解

每个时间步的时间复杂度仅为

O(|S|)

,算法总体时间复杂度为

O(|S| \cdot T)

。除了前向算法之外,还有一个类似的「后向算法」用来计算如下概率:

\beta_{i}(t)=P\left(x_{T}, x_{T-1}, . ., x_{t+1}, z_{t}=s_{i} ; A, B\right)

2.3 最大似然状态序列:维特比算法

HMM 最常见的一个问题是:给定一个观测序列输出

\vec{x} \in V^{T}

,最可能的状态序列

\vec{z} \in S^{T}

是什么?

该问题可以用如下公式表达:

\arg \max _{\vec{z}} P(\vec{z} | \vec{x} ; A, B)=\arg \max _{\vec{z}} \frac{P(\vec{x}, \vec{z} ; A, B)}{\sum_{\vec{z}} P(\vec{x}, \vec{z} ; A, B)}=\arg \max _{\vec{z}} P(\vec{x}, \vec{z} ; A, B)

第一步运用了贝叶斯法则;第二步的依据是分母不与

\vec{z}

直接相关。

我们可以通过枚举法进行求解,但时间复杂度为

O(|S|^T)

,与之前类似,我们可以使用动态规划的方法来简化运算。用于求解上述问题的动态规划方法被称为「维特比算法」(Viterbi algorithm),其与前向算法十分类似,区别在于这里不需要追踪概率之和,而是追踪最大概率并记录其对应的状态序列。

2.4 参数学习:基于 EM 算法的 HMM

关于 HMM 的最后一个问题是:给定一个状态序列集,如何求解矩阵

A

B

中的参数?本节将使用 「EM 算法」来进行求解,下图给出了算法的基本流程(针对单个样本):

注意 M-step 中包含了约束条件(因为

A

B

中含有概率),我们将使用拉格朗日乘子来求解上述优化问题。此外,注意到在 E-step 和 M-step 中均需要枚举所有的状态序列,导致过大的时间复杂度。因此我们将使用之前提到的前向和后向算法来简化计算。

首先,使用马尔可夫假设来重写目标函数:

\begin{aligned} A,B &= \arg \max _{A, B} \sum_{\vec{z}} Q(\vec{z}) \log \frac{P(\vec{x}, \vec{z} ; A, B)}{Q(\vec{z})} \\ &= \arg \max _{A, B} \sum_{\vec{z}} Q(\vec{z}) \log P(\vec{x}, \vec{z} ; A, B)\\ &= \arg \max _{A, B} \sum_{\vec{z}} Q(\vec{z}) \log \left(\prod_{t=1}^{T} P\left(x_{t} | z_{t} ; B\right)\right)\left(\prod_{t=1}^{T} P\left(z_{t} | z_{t-1} ; A\right)\right)\\ &= \arg \max _{A, B} \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} \log B_{z_{t} x_{t}}+\log A_{z_{t-1} z_{t}}\\ &= \arg \max _{A, B} \sum_{\vec{z}} Q(\vec{z}) \sum_{i=1}^{|S|} \sum_{j=1}^{|S|} \sum_{k=1}^{|V|}\sum_{t=1}^{T} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\} \log B_{j k}+1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \log A_{i j}\\ \end{aligned}

第二行去除了分母,因为其与

A

B

无关;第三行应用了马尔可夫假设;第五行使用指示函数来按状态索引

A

B

下面构建拉格朗日乘子。与之前一样,因为解必为非负,所以不等约束可以忽略:

\begin{aligned} \mathcal{L}(A, B, \delta, \epsilon)=& \sum_{\vec{z}} Q(\vec{z}) \sum_{i=1}^{|S|} \sum_{j=1}^{|S|} \sum_{k=1}^{|V|} \sum_{t=1}^{T} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\} \log B_{j k}+1\left\{z_{t-1}=s_{i}\wedge z_{t}=s_{j}\right\}\log A_{i j}\\ &+\sum_{j=1}^{|S|} \epsilon_{j}\left(1-\sum_{k=1}^{|V|} B_{j k}\right)+\sum_{i=1}^{|S|} \delta_{i}\left(1-\sum_{j=1}^{|S|} A_{i j}\right) \end{aligned}

求偏导并将其设为 0 可得:

\begin{aligned} \frac{\partial \mathcal{L}(A, B, \delta, \epsilon)}{\partial A_{i j}} &=\sum_{\vec{z}} Q(\vec{z}) \frac{1}{A_{i j}} \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\}-\delta_{i} \equiv 0 \\ A_{i j} &=\frac{1}{\delta_{i}} \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \end{aligned}
\begin{aligned} \frac{\partial \mathcal{L}(A, B, \delta, \epsilon)}{\partial B_{j k}} &=\sum_{\vec{z}} Q(\vec{z}) \frac{1}{B_{j k}} \sum_{t=1}^{T} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\}-\epsilon_{j} \equiv 0 \\ B_{j k} &=\frac{1}{\epsilon_{j}} \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\} \end{aligned}

将上述结果代回并关于拉格朗日乘子求偏导可得:

\begin{aligned} \frac{\partial \mathcal{L}(A, B, \delta, \epsilon)}{\partial \delta_{i}} &=1-\sum_{j=1}^{|S|} A_{i j} \\ &=1-\sum_{j=1}^{|S|} \frac{1}{\delta_{i}} \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \equiv 0 \\ \delta_{i} &=\sum_{j=1}^{|S|} \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \\ &=\sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i}\right\} \end{aligned}
\begin{aligned} \frac{\partial \mathcal{L}(A, B, \delta, \epsilon)}{\partial \epsilon_{j}} &=1-\sum_{k=1}^{|V|} B_{j k} \\ &=1-\sum_{k=1}^{|V|} \frac{1}{\epsilon_{j}} \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\} \equiv 0 \\ \epsilon_{j} &=\sum_{k=1}^{|V|} \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\} \\ &=\sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t}=s_{j}\right\} \end{aligned}

将上述结果代回,可以解得:

\begin{aligned} \hat{A}_{i j} &=\frac{\sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\}}{\sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i}\right\}} \\ \hat{B}_{j k} &=\frac{\sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\}}{\sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t}=s_{j}\right\}} \end{aligned}

上述公式需要遍历所有状态序列,我们可以使用前向和后向概率来进行化简,首先对

\hat{A}_{i j}

的分子进行化简:

\begin{aligned} & \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \\ = & \sum_{t=1}^{T} \sum_{\vec{z}} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} Q(\vec{z}) \\ = & \sum_{t=1}^{T} \sum_{\vec{z}} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} P(\vec{z} | \vec{x} ; A, B)\\ = & \frac{1}{P(\vec{x} ; A, B)} \sum_{t=1}^{T} \sum_{\vec{z}} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} P(\vec{z}, \vec{x} ; A, B)\\ = & \frac{1}{P(\vec{x} ; A, B)} \sum_{t=1}^{T} \alpha_{i}(t) A_{i j} B_{j x_{t}} \beta_{j}(t+1)\\ \end{aligned}

前两步进行了重新排列并引入了

Q

的定义;第三步使用了贝叶斯法则;第四步使用了各元素的定义。

类似地,分母也可以进行化简:

\begin{aligned} & \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i}\right\} \\=& \sum_{j=1}^{|S|} \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} \\=& \frac{1}{P(\vec{x} ; A, B)} \sum_{j=1}^{|S|} \sum_{t=1}^{T} \alpha_{i}(t) A_{i j} B_{j x_{t}} \beta_{j}(t+1) \end{aligned}

将上述结果综合,可以得到:

\hat{A}_{i j}=\frac{\sum_{t=1}^{T} \alpha_{i}(t) A_{i j} B_{j x_{t}} \beta_{j}(t+1)}{\sum_{j=1}^{|S|} \sum_{t=1}^{T} \alpha_{i}(t) A_{i j} B_{j x_{t}} \beta_{j}(t+1)}

类似地,对

\hat{B}_{j k}

的分子进行如下化简:

\begin{aligned} & \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\}\\ = & \frac{1}{P(\vec{x} ; A, B)} \sum_{t=1}^{T} \sum_{\vec{z}} 1\left\{z_{t}=s_{j} \wedge x_{t}=v_{k}\right\} P(\vec{z}, \vec{x} ; A, B)\\ = & \frac{1}{P(\vec{x} ; A, B)} \sum_{i=1}^{|S|} \sum_{t=1}^{T} \sum_{\vec{z}}1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j} \wedge x_{t}=v_{k}\right\} P(\vec{z}, \vec{x} ; A, B)\\ = & \frac{1}{P(\vec{x} ; A, B)} \sum_{i=1}^{|S|} \sum_{t=1}^{T} 1\left\{x_{t}=v_{k}\right\} \alpha_{i}(t) A_{i j} B_{j x_{t}} \beta_{j}(t+1)\\ \end{aligned}

同理,其分母可以表示为:

\begin{aligned} & \sum_{\vec{z}} Q(\vec{z}) \sum_{t=1}^{T} 1\left\{z_{t}=s_{j}\right\} \\=& \frac{1}{P(\vec{x} ; A, B)} \sum_{i=1}^{|S|} \sum_{t=1}^{T} \sum_{\vec{z}}1\left\{z_{t-1}=s_{i} \wedge z_{t}=s_{j}\right\} P(\vec{z}, \vec{x} ; A, B) \\=& \frac{1}{P(\vec{x} ; A, B)} \sum_{i=1}^{|S|} \sum_{t=1}^{T} \alpha_{i}(t) A_{i j} B_{j x_{t}} \beta_{j}(t+1) \end{aligned}

将上述结果综合,可以得到:

\hat{B}_{j k}=\frac{\sum_{i=1}^{|S|} \sum_{t=1}^{T} 1\left\{x_{t}=v_{k}\right\} \alpha_{i}(t) A_{i j} B_{j x_{t}} \beta_{j}(t+1)}{\sum_{i=1}^{|S|} \sum_{t=1}^{T} \alpha_{i}(t) A_{i j} B_{j x_{t}} \beta_{j}(t+1)}

基于上述结果,可以提出用于 HMM 参数学习的前向-后向算法,该算法也被称为 Baum-Welch 算法:

与许多 EM 算法的应用类似,该算法是一个非凸优化问题,存在许多局部最优解。EM 算法将基于初始值收敛至最大值,因此可以考虑多次运行算法。此外,对由

A

B

表示的概率分布进行「平滑处理」也十分重要,即没有转移或生成为 0 概率(除去初始情况)。

3 思维导图

本文分享自微信公众号 - 口仆(roito33),作者:口仆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 卡特兰数入门

    括号的合法匹配方式为:一个左括号对应一个右括号,且左括号必须要在右括号前面出现。为了方便说明,这里将左括号记作 +1,右括号记作 -1,则一个合法序列和一个非法...

    口仆
  • CS229 课程笔记之九:EM 算法与聚类

    为了证明 k-means 算法能否保证收敛,我们定义「失真函数」(distortion function)为:

    口仆
  • CS229 课程笔记之十二:独立成分分析

    「独立成分分析」(ICA)与 PCA 类似,也会找到一个新基底来表示数据,但两者的目标完全不同。

    口仆
  • 隐马尔可夫模型(HMM)

    原文地址:http://www.cnblogs.com/jacklu/p/7753471.html

    用户7043923
  • Kaggle:一套完整的网站流量预测模型

    今天给大家推荐的是一个名叫Kaggle的网站流量预测项目,本项目采用Python语言开发,可以给大家的流量预测建模提供一些思路。 ? 数据模型 Kaggle的训...

    FB客服
  • Markov与HMM

    马尔可夫模型(Markov Model)和回归、分类那些处理相互独立的样本数据的模型不同,它用于处理时间序列数据,即样本之间有时间序列关系的数据。Markov最...

    mathor
  • sam文件格式说明

    bowtie2是当前最流行的短序列比对软,SAM(SequenceAlignment/Map)格式是一种通用的比对格式,用来存储reads到参考序列的比对信息S...

    HUBU生信
  • PSVR版《亚利桑那阳光》将于下月登陆欧洲零售店,将包含最新内容

    VRPinea
  • 关于c语言中结构体的初始化

    这种方式不能指明结构体类型名而是直接定义结构体变量,并且在值定义一次结构体变量时适用,无结构体名的结构体类型是无法重复使用的。

    用户4645519
  • 持久化类与缓存

    持久态:已经有了id,调用session方法,把对象给session,才被session所管理,添加到session之后, 对象一直处理持久态,当对象处理持久态...

    木瓜煲鸡脚

扫码关注云+社区

领取腾讯云代金券