网站建设的卷子,公共服务平台官网,wordpress音乐页面面板,wordpress的播放器引言
这是《统计学习方法》第二版的读书笔记#xff0c;由于包含书上所有公式的推导和大量的图示#xff0c;因此文章较长#xff0c;正文分成三篇#xff0c;以及课后习题解答#xff0c;在习题解答中用Numpy实现了维特比算法和前向后向算法。 《统计学习方法》——隐马…引言
这是《统计学习方法》第二版的读书笔记由于包含书上所有公式的推导和大量的图示因此文章较长正文分成三篇以及课后习题解答在习题解答中用Numpy实现了维特比算法和前向后向算法。 《统计学习方法》——隐马尔可夫模型(上)《统计学习方法》——隐马尔可夫模型(中)《统计学习方法》——隐马尔可夫模型(下)《统计学习方法》——隐马尔可夫模型#习题解答#
隐马尔可夫模型(Hidden Markov Model,HMM)是描述隐藏的马尔可夫链随机生成观测数据过程的模型。
前置知识
马尔可夫链
马尔可夫链(Markov chain)又称离散时间马尔可夫链使用 t t t来表示时刻用 X t X_t Xt来表示在时刻 t t t链的状态假定所有可能状态组成的有限集合 S \cal S S称为状态空间。
马尔可夫链为状态空间中从一个状态到另一个状态的转换的随机过程。
在马尔可夫链的每一步根据概率分布可以从一个状态变到另一个状态也可以保存当前状态。状态的概率叫做转移状态改变的概率相关的概率就转移概率。
描述当前状态为 i i i下一个状态为 j j j的转移概率 p i j p_{ij} pij定义为 p i j P ( X t 1 j ∣ X t i ) , i , j ∈ S p_{ij} P(X_{t1}j|X_ti), \qquad i,j \in \cal S pijP(Xt1j∣Xti),i,j∈S 马尔可夫链的核心假设是只要时刻 t t t的状态为 i i i不论过去发生了什么也不论链是如何到达状态 i i i的下一个时刻转移到状态 j j j的概率就一定是状态转移概率 p i j p_{ij} pij。即该过程要求具备“无记忆”的性质下一状态的概率分布只能由当前状态决定与时间序列上它前面的事件无关。这种无记忆性称为马尔可夫性质。在数学上表示为 P ( X t 1 j ∣ X t i , X t − 1 i n − 1 , ⋯ , X 0 i 0 ) P ( X t 1 j ∣ X t i ) p i j P(X_{t1}j|X_ti,X_{t-1}i_{n-1},\cdots,X_0i_0) P(X_{t1}j|X_ti)p_{ij} P(Xt1j∣Xti,Xt−1in−1,⋯,X0i0)P(Xt1j∣Xti)pij 转移概率 P i j P_{ij} Pij一定是非负的且和为1 ∑ j p i j 1 \sum_j p_{ij} 1 j∑pij1 下一个状态可能和当前状态一样即状态没有发生变化我们也认为状态发生了一次特殊的转移(自身转移)。
总结一下一个马尔可夫链模型由以下特征确定:
状态集合 S \cal S S可能发生状态转移 ( i , j ) (i,j) (i,j)的集合即由所有 p i j 0 p_{ij} 0 pij0的 ( i , j ) (i,j) (i,j)组成 p i j p_{ij} pij的取值为正
马尔可夫链可以由转移概率矩阵所刻画它是一个简单的二元矩阵其第 i i i行第 j j j列的元素为 p i j p_{ij} pij假设共有 m m m个状态 [ p 11 p 12 ⋯ p 1 m p 21 p 22 ⋯ p 2 m ⋮ ⋮ ⋮ ⋮ p m 1 p m 2 ⋯ p m m ] \begin{bmatrix} p_{11} p_{12} \cdots p_{1m} \\ p_{21} p_{22} \cdots p_{2m} \\ \vdots \vdots \vdots \vdots \\ p_{m1} p_{m2} \cdots p_{mm} \\ \end{bmatrix} p11p21⋮pm1p12p22⋮pm2⋯⋯⋮⋯p1mp2m⋮pmm 也可以用转移概率图表示马尔可夫链图中用节点表示状态连接节点的(有向)弧线表示可能发生的转移将 p i j p_{ij} pij的数值标记在相应的弧线旁边。
比如下面来自维基百科的一个例子它表示一个具有两个状态转换的马尔可夫链 图p1 马尔可夫链的例子 来自维基百科 概率图模型
概率图模型(probabilistic graphical models)是概率分布的图形表示它非常方便我们分析模型的性质尤其是条件独立性质。 和我们数据结构中学的图一样一个图由节点、节点间的边组成。概率图模型中每个节点表示一个随机变量边表示这些变量之间的概率关系缺失的边表示条件独立假设。
概率图主要分为两大类有向图模型也称为贝叶斯网络(实际上和贝叶斯关系不大)无向图模型也称为马尔可夫随机场(名字也没那么直观)。
这里主要简单介绍下有向图模型因为HMM可以通过它进行表示。它的一些概念有助于后面的公式推理。
首先介绍下 条件独立(conditional independence, CI) 的概念。 我们先来回顾下独立的概念假设有两个随机变量 a , b a,b a,b相互独立的话有 p ( a , b ) p ( a ) p ( b ) p(a,b) p(a)p(b) p(a,b)p(a)p(b) 如果此时求给定 b b b的条件下 a a a的概率 p ( a ∣ b ) p ( a , b ) p ( b ) p ( a ) p ( b ) p ( b ) p ( a ) (p1) p(a|b) \frac{p(a,b)}{p(b)} \frac{p(a)p(b)}{p(b)} p(a) \tag{p1} p(a∣b)p(b)p(a,b)p(b)p(a)p(b)p(a)(p1) 即不管 b b b的取值如何都不影响 a a a发生的概率。也可以说 a a a条件独立于 b b b。
现在假设有三个变量 a , b , c a,b,c a,b,c假设给定 b , c b,c b,c的条件下 a a a的条件分布不依赖于 b b b的值即 p ( a ∣ b , c ) p ( a ∣ c ) (p2) p(a|b,c) p(a|c) \tag{p2} p(a∣b,c)p(a∣c)(p2) 也就是说在给定 c c c的条件下 a a a条件独立于 b b b。在给定 c c c的条件下 b b b作为条件的取值不会影响 p ( a ∣ c ) p(a|c) p(a∣c)。
我们考虑将 p ( a , b ∣ c ) p(a,b|c) p(a,b∣c)展开 p ( a , b ∣ c ) p ( a ∣ b , c ) p ( b ∣ c ) p ( a ∣ c ) p ( b ∣ c ) (p3) p(a,b|c) p(a|b,c)p(b|c) p(a|c)p(b|c) \tag{p3} p(a,b∣c)p(a∣b,c)p(b∣c)p(a∣c)p(b∣c)(p3) ( p 2 ) (p2) (p2)和 ( p 3 ) (p3) (p3)都是在这种情况下条件独立的不同描述。 注意条件独立中的条件二字比如这里都是在以 c c c为条件的前提下而且是对于 c c c的所有取值都成立。 记为 a ⊥ b ∣ c a \,\bot \,b \,|\, c a⊥b∣c 表示给定 c c c的条件下 a a a和 v v v条件独立。
我们以此为基础再来看下马尔可夫链假设 x t 1 ⊥ x 1 : t − 1 ∣ x t x_{t1} \,\bot \,x_{1:t-1} \, | \, x_t xt1⊥x1:t−1∣xt即下一时刻仅依赖于当前时刻和所有的之前时刻无关这就是(一阶)马尔可夫假设。
基于该假设结合链式法则 x 1 : N x_{1:N} x1:N的联合概率分布可以写成 p ( x 1 : N ) p ( x 1 ) ∏ t 2 N p ( x t ∣ x 1 : t − 1 ) p ( x 1 ) ∏ t 2 N p ( x t ∣ x t − 1 ) (p4) p(x_{1:N})p(x_1)\prod_{t2}^N p(x_t|x_{1:t-1}) p(x_1)\prod _{t2}^N p(x_t|x_{t-1}) \tag{p4} p(x1:N)p(x1)t2∏Np(xt∣x1:t−1)p(x1)t2∏Np(xt∣xt−1)(p4) 这就是一阶马尔可夫链。这里说的一阶是什么意思说的 x t x_t xt仅依赖于 x t − 1 x_{t-1} xt−1如果是二阶则依赖于 x t − 1 , x t − 2 x_{t-1},x_{t-2} xt−1,xt−2。相当于假设要弱一点但带来的复杂性也高一点。那最强的假设是什么朴素贝叶斯假设所有的 x t x_t xt之间是相互独立的。
前面说概率图模型是概率分布的图形表示那么它如何表示概率分布呢
考虑三个变量 a , b , c a,b,c a,b,c的联合分布 p ( a , b , c ) p(a,b,c) p(a,b,c)此时我们不对这些变量做出任何的假设通过概率的乘积规则可以将联合概率分布写成 p ( a , b , c ) p ( c ∣ a , b ) p ( a , b ) p ( c ∣ a , b ) p ( b ∣ a ) p ( a ) (p5) p(a,b,c)p(c|a,b)p(a,b)p(c|a,b)p(b|a)p(a) \tag{p5} p(a,b,c)p(c∣a,b)p(a,b)p(c∣a,b)p(b∣a)p(a)(p5) 此时我们引入图模型来表示上面等式的右侧。首先我们为每个随机变量引入一个节点然后为每个节点关联上式右侧对应的条件概率然后对于每个条件概率分布我们在图中添加一个链接(箭头)箭头的起点是条件概率中条件的随机变量对应的节点。结果就是图p2中的图。
图p2 有向图模型的例子 可以看到这个图描述了联合概率分布 p ( a , b , c ) p(a,b,c) p(a,b,c)在所有随机变量上能分解成一组因子的乘积的方式每个因子只依赖于随机变量的一个子集。 比如对于因子 p ( a ) p(a) p(a)没有输入的链接也就没有箭头指向它。而对于因子 p ( c ∣ a , b ) p(c|a,b) p(c∣a,b)存在从节点 a , b a,b a,b到节点 c c c的链接。 这里我们说节点 a a a是节点 b b b的父节点节点 b b b是节点 a a a的子节点。这种关系和数据结构中的图一致。
这里要注意的是我们隐式地选择了一种顺序来分解 p 5 p5 p5不同的顺序会对应不同的分解方式也得到不同的图表示。
我们看到在图的所有节点上定义的联合概率分布由每个节点上的条件概率分布的乘积表示每个条件概率分布的条件都是图中节点的父节点所对应的变量。因此对于一个有 K K K个节点的图联合概率为 p ( x ) ∏ k 1 K p ( x k ∣ p a k ) (p6) p(\pmb x) \prod_{k1}^K p(x_k|pa_k) \tag{p6} p(x)k1∏Kp(xk∣pak)(p6) 其中 p a k pa_k pak表示 x K x_K xK的父节点的集合 x { x 1 , ⋯ , x K } \pmb x\{x_1,\cdots,x_K\} x{x1,⋯,xK}。这个公式非常重要表示有向图模型的联合概率的分解(factorization)属性。图中每个节点还可以关联一个变量的集合。
有向图的独立性质
有了这些概念下面我们来看条件独立相关的图表示我们以三个变量 a , b , c a,b,c a,b,c的图模型为例。 三个变量 a , b , c a,b,c a,b,c之间的有向图连接对应三个经典的例子我们先来看第一个。如图p3所示
图p3 根据 ( p 6 ) (p6) (p6)我们可以写出这个图的联合概率分布 p ( a , b , c ) p ( c ) p ( a ∣ c ) p ( b ∣ c ) (p7) p(a,b,c) p(c)p(a|c)p(b|c) \tag{p7} p(a,b,c)p(c)p(a∣c)p(b∣c)(p7) 该结构为同父结构即节点 a , b a,b a,b存在相同的父节点 a a a。当父节点 c c c被观测到时 a , b a,b a,b条件独立。 考虑没有变量是观测变量的情形即我们通过对 ( p 7 ) (p7) (p7)两边进行积分或求和的方式来考察 a a a和 b b b是否为相互独立的即 p ( a , b ) ∑ c p ( c ) p ( a ∣ c ) p ( b ∣ c ) (p8) p(a,b) \sum_c p(c)p(a|c)p(b|c) \tag{p8} p(a,b)c∑p(c)p(a∣c)p(b∣c)(p8) 这通常不能分解为乘积 p ( a ) p ( b ) p(a)p(b) p(a)p(b)的形式因此我们说 a ⊥̸ b ∣ ∅ a \not \bot \, b \,|\, \empty a⊥b∣∅
这里 ∅ \empty ∅表示空集符号 ⊥̸ \not \bot ⊥表示条件独立性质不总是成立。
现在假设我们以变量 c c c为条件(或者说观测到变量 c c c即 c c c取了特定值不再是一个随机变量)得到的图如p4所示。 图p4 我们为上图中的节点添加阴影部分如节点 c c c所示表示它被观测到了。
我们可以写成给定 c c c的条件下 a a a和 b b b的条件概率分布并结合 ( p 7 ) (p7) (p7) p ( a , b ∣ c ) p ( a , b , c ) p ( c ) p ( c ) p ( a ∣ c ) p ( b ∣ c ) p ( c ) p ( a ∣ c ) p ( b ∣ c ) p(a,b|c) \frac{p(a,b,c)}{p(c)} \frac{p(c)p(a|c)p(b|c) }{p(c)} p(a|c)p(b|c) p(a,b∣c)p(c)p(a,b,c)p(c)p(c)p(a∣c)p(b∣c)p(a∣c)p(b∣c) 因此我们可以得到条件独立性质(回顾 ( p 3 ) (p3) (p3)) a ⊥ b ∣ c a \,\bot \,b \,|\, c a⊥b∣c 这里节点 c c c被关于关于从节点 a a a经过节点 c c c到节点 b b b路径的尾到尾(tail-to-tail)因为节点与两个箭头的尾部相连。 这样的一个连接节点 a a a和节点 b b b的路径的存在(从箭头头部到尾部的路径是通的)使得节点相互依赖。 然而当我们观测到节点 c c c或者说以 c c c为条件时被当做条件的节点 c c c阻隔了从 a a a到 b b b的路径使得 a a a和 b b b变成(条件)独立了。
路径的阻隔表示条件独立
我们再来看第二个例子如图p5所示 图p5 该结构称为顺序结构。当 c c c被观测到时 a , b a,b a,b条件独立。 这幅图的联合概率分布通过 ( p 6 ) (p6) (p6)得到形式为 p ( a , b , c ) p ( a ) p ( c ∣ a ) p ( b ∣ c ) (p9) p(a,b,c) p(a) p(c|a)p(b|c) \tag{p9} p(a,b,c)p(a)p(c∣a)p(b∣c)(p9) 与之前一样我们对 c c c积分或求和来考察 a a a和 b b b是否互相独立 p ( a , b ) p ( a ) ∑ c p ( c ∣ a ) p ( b ∣ c ) p(a,b) p(a) \sum_c p(c|a) p(b|c) p(a,b)p(a)c∑p(c∣a)p(b∣c) 这一般也不能分解为 p ( a ) p ( b ) p(a)p(b) p(a)p(b)因此 a ⊥̸ b ∣ ∅ a \not \bot \, b \,|\, \empty a⊥b∣∅ 现在以节点 c c c为条件再利用公式 ( p 9 ) (p9) (p9) p ( a , b ∣ c ) p ( a , b , c ) p ( c ) p ( a ) p ( c ∣ a ) p ( b ∣ c ) p ( c ) p ( a , c ) p ( b ∣ c ) p ( c ) p ( a ∣ c ) p ( b ∣ c ) \begin{aligned} p(a,b|c) \frac{p(a,b,c)}{p(c)} \\ \frac{p(a) p(c|a)p(b|c)}{p(c)} \\ \frac{p(a,c)p(b|c)}{p(c)} \\ p(a|c)p(b|c) \end{aligned} p(a,b∣c)p(c)p(a,b,c)p(c)p(a)p(c∣a)p(b∣c)p(c)p(a,c)p(b∣c)p(a∣c)p(b∣c) 我们再次得到了条件独立性质 a ⊥ b ∣ c a \,\bot \,b \,|\, c a⊥b∣c 节点 c c c被称为关于从节点 a a a到节点 b b b的路径的头到尾(head-to-tail)。这样的一个连接节点 a a a和节点 b b b的路径的存在使得节点相互依赖。如果我们观测节点 c c c如图p6所示这个观测阻隔了从 a a a到 b b b的路径因此我们得到了条件独立性质。 图p6 最后我们考虑第三个例子也是最难理解的例子。如图p7所示 图p7 V型结构也称冲状撞结构。当 c c c未被观测或者说 c c c未知的情况下 a , b a,b a,b相互独立。当 c c c被观测到 a , b a,b a,b必不独立。 这里提到了给定和未知。基于条件概率 p ( A ∣ B ) p(A|B) p(A∣B)指事件 A A A在事件 B B B已经发生条件下的发生概率。事件 B B B是已经发生的即给定的、观测到的事件 A A A的发生是以概率形式表现的 A A A是否发生是未知的。 同样我们可以得到联合概率分布 p ( a , b , c ) p ( a ) p ( b ) p ( c ∣ a , b ) (p10) p(a,b,c)p(a)p(b)p(c|a,b) \tag{p10} p(a,b,c)p(a)p(b)p(c∣a,b)(p10) 对上式两侧关于 c c c积分或求和得到 p ( a , b ) p ( a ) p ( b ) p(a,b)p(a)p(b) p(a,b)p(a)p(b) 因为 p ( c ∣ a , b ) p(c|a,b) p(c∣a,b)是关于 c c c的条件分布也是一种概率分布对 c c c求和或积分结果为 1 1 1。
这样我们得到了和之前不一样的结果当没有变量被观测时 a a a和 b b b是独立的。我们可以把这个结果写成 a ⊥ b ∣ ∅ a \,\bot \,b \,|\, \empty a⊥b∣∅ 图p8 那么假设我们还是以 c c c为条件如图p8所示有 p ( a , b ∣ c ) p ( a , b , c ) p ( c ) p ( a ) p ( b ) p ( c ∣ a , b ) p ( c ) p(a,b|c) \frac{p(a,b,c)}{p(c)} \frac{p(a)p(b)p(c|a,b)}{p(c)} p(a,b∣c)p(c)p(a,b,c)p(c)p(a)p(b)p(c∣a,b) 这通常也不能分解为 p ( a ) p ( b ) p(a)p(b) p(a)p(b)因此 a ⊥̸ b ∣ c a \,\not \bot \,b \,|\, c a⊥b∣c 图形上来看我们说节点 c c c关于从 a a a到 b b b的路径是头到头(head-to-head)。当 c c c没有被观测到时它阻隔了路径使得变量 a a a和 b b b是相互独立的。当以 c c c为条件时路径被解除阻隔使得 a a a和 b b b相互依赖了。
特别地我们考虑下图p9这种情形。是V型结构的延伸其中新节点 d d d是节点 c c c的孩子节点但该结构中仅 d d d被观测到那么 a a a和 b b b也会被解除阻隔。其实不仅是 c c c的直接孩子节点 d d d当 c c c或 c c c的任意后继(descendant)节点被观测到都会使得 a a a和 b b b解除阻隔。 图p9 怎么证明呢
我们还是先写出概率分布 p ( a , b , c , d ) p ( a ) p ( b ) p ( c ∣ a , b ) p ( d ∣ c ) p(a,b,c,d) p(a)p(b)p(c|a,b)p(d|c) p(a,b,c,d)p(a)p(b)p(c∣a,b)p(d∣c)
假设观测到 d d d我们考虑 a , b a,b a,b是否是条件独立的。 p ( a , b ∣ d ) ∑ c p ( a , b , c ∣ d ) ∑ c p ( a , b , c , d ) p ( d ) ∑ c p ( a ) p ( b ) p ( c ∣ a , b ) p ( d ∣ c ) p ( d ) ∑ c p ( a ) p ( b ) p ( c ∣ a , b ) p ( d ∣ c , a , b ) p ( d ) ∑ c p ( a ) p ( b ) p ( d , c ∣ a , b ) p ( d ) p ( a ) p ( b ) p ( d ∣ a , b ) p ( d ) ≠ p ( a ) p ( b ) \begin{aligned} p(a,b|d) \sum_c p(a,b,c|d) \\ \sum_c \frac{p(a,b,c,d)}{p(d)} \\ \sum_c \frac{ p(a)p(b)p(c|a,b)p(d|c)}{p(d)} \\ \sum_c \frac{ p(a)p(b)p(c|a,b)p(d|c,a,b)}{p(d)} \\ \sum_c \frac{ p(a)p(b)p(d,c|a,b)}{p(d)} \\ \frac{ p(a)p(b)p(d|a,b)}{p(d)} \\ \neq p(a)p(b) \end{aligned} p(a,b∣d)c∑p(a,b,c∣d)c∑p(d)p(a,b,c,d)c∑p(d)p(a)p(b)p(c∣a,b)p(d∣c)c∑p(d)p(a)p(b)p(c∣a,b)p(d∣c,a,b)c∑p(d)p(a)p(b)p(d,c∣a,b)p(d)p(a)p(b)p(d∣a,b)p(a)p(b)
这里用到了 d , c , a d,c,a d,c,a和 d , c , b d,c,b d,c,b满足上面描述的顺序结构即 p ( d ∣ a , b , c ) p ( d ∣ c ) p(d|a,b,c)p(d|c) p(d∣a,b,c)p(d∣c)。
我们再考虑相反的情况假设未观测到 d d d有 p ( a , b , c , d ) p ( a ) p ( b ) p ( c ∣ a , b ) p ( d ∣ c ) p(a,b,c,d) p(a)p(b)p(c|a,b)p(d|c) p(a,b,c,d)p(a)p(b)p(c∣a,b)p(d∣c) 对上式两侧关于 d d d积分或求和得到 p ( a , b , c ) p ( a ) p ( b ) p ( c ∣ a , b ) p(a,b,c) p(a)p(b)p(c|a,b) p(a,b,c)p(a)p(b)p(c∣a,b) 再关于 c c c积分或求和 p ( a , b ) p ( a ) p ( b ) p(a,b)p(a)p(b) p(a,b)p(a)p(b)
同样当没有变量被观测到时有 a ⊥ b ∣ ∅ a \,\bot \,b \,|\, \empty a⊥b∣∅
可以看到在未观测到 d d d的情况下 a , b a,b a,b还是互相独立的。这和节点 c c c的性质是一样的。反之在观测到 d d d的情况下联合概率不能分解成 p ( a ) p ( b ) p(a)p(b) p(a)p(b)。
我们可以以一个例子来简单理解假设你家装了一个偷窃报警器当家里遭窃或地震都有可能触发这个偷窃报警器响而当报警器响的情况下邻居听到后可能给你打电话。 图p10 地震与否不会被你家是否遭窃影响。这里也假设小偷不管有没有地震都不影响他进行偷窃。此时这两个事件在报警响未被观测到的情况下就是独立的。
假设你正在外度假邻居给你打电话说你家报警器响了。那么从邻居打电话这个事件我们可以得到警报响这个事件发生了。
最后我们总结成一个图 图p11 再重申一次若 a a a到 b b b的路径被阻隔说明它们是(条件)独立的。
基于上面的三个例子下面我们引入一个非常重要的概念D-划分(D-Separation)也称为有向分离或D-分离。
D-划分
图模型的一个重要且优雅的特征是联合概率分布的条件独立性可以直接从图中读出来不用进行任何计算。完成这件事的一般框架就是d-划分d表示有向。
考虑一个一般的有向图其中 A , B , C A,B,C A,B,C是任意无交集的节点集合。我们考虑从 A A A中任意节点到 B B B中任意节点的所有可能的路径我们说这样的路径被阻隔如果它包含一个节点满足下面两个性质中的任意一个
路径上的箭头以头到尾或尾到尾的方式交汇于这个节点且这个节点在集合 C C C中箭头以头到头的方式交汇于这个节点且这个节点和它的所有后继都不在集合 C C C中
如果所有的路径都被阻隔我们说 C C C把 A A A从 B B B中d-划分开且图中所有变量上的联合概率分布都满足 A ⊥ B ∣ C A \, \bot \, B \, | \, C A⊥B∣C。 图p12 如图p12所示。尾到尾是红线表示头到尾是黑线表示都交汇于集合 C C C中而头到头方式交汇的节点不在集合 C C C中。
我们再通过一个例子来理解一下例子来自PRML。 图p13 来自PRML 在p13左图中从 a a a到 b b b的路径是通的首先对于 a → e → f a \rightarrow e \rightarrow f a→e→f的路径这是一个头到头结构虽然 e e e未被观测到但 e e e的后继 c c c被观测到因此这条路径是通的然后对于 e → f → b e \rightarrow f \rightarrow b e→f→b的路径这是尾到尾结构且 f f f没有被观测到没有被 f f f阻隔
在p13右图中从 a a a到 b b b的路径被节点 e e e和 f f f阻隔对于 a → e → f a \rightarrow e \rightarrow f a→e→f的路径 e e e和 e e e的后继没有被观测到(没有在条件集合中) a a a到 f f f是被阻隔的同时对于 e → f → b e \rightarrow f \rightarrow b e→f→b来说是一个尾到尾结构且 f f f被观测到。因此使用这幅图进行分解的任何概率分布都满足条件独立性质 a ⊥ b ∣ f a \, \bot \, b \, | \, f a⊥b∣f。
下面我们来看如何用概率图来表示隐马尔科夫模型。
隐马尔可夫模型图示
假设针对顺序观测数据基于一阶马尔可夫假设即每个观测只与最近的一次观测有关我们就得到了一阶马尔科夫链(马尔科夫模型) N N N次观测的序列的联合分布为 p ( x 1 : N ) p ( x 1 ) ∏ t 2 N p ( x t ∣ x 1 : t − 1 ) p ( x 1 ) ∏ t 2 N p ( x t ∣ x t − 1 ) p(x_{1:N})p(x_1)\prod_{t2}^N p(x_t|x_{1:t-1}) p(x_1)\prod _{t2}^N p(x_t|x_{t-1}) p(x1:N)p(x1)t2∏Np(xt∣x1:t−1)p(x1)t2∏Np(xt∣xt−1) 该一阶马尔可夫链用概率图表示如图p14所示 图p14 再进一步如果引入额外的潜在变量 z n z_n zn假设潜在变量也构成了马尔可夫链得到的图结构称为状态空间结构(state space model)如图p15所示。它满足下面的条件独立性质即在给定 z n z_n zn的条件下 z n − 1 z_{n-1} zn−1和 z n 1 z_{n1} zn1是独立的有 z n 1 ⊥ z n − 1 ∣ z n (p11) z_{n1} \, \bot \, z_{n-1}\, | \,z_n \tag{p11} zn1⊥zn−1∣zn(p11)
图p15 这个模型的联合概率分布为 p ( x 1 , ⋯ , x N , z 1 , ⋯ , z N ) p ( z 1 ) [ ∏ t 2 N p ( z t ∣ z t − 1 ) ] ∏ t 1 N p ( x t ∣ z t ) (p12) p(x_1,\cdots,x_N,z_1,\cdots,z_N) p(z_1)\left[\prod_{t2}^N p(z_t|z_{t-1}) \right] \prod_{t1}^N p(x_t|z_t) \tag{p12} p(x1,⋯,xN,z1,⋯,zN)p(z1)[t2∏Np(zt∣zt−1)]t1∏Np(xt∣zt)(p12) 根据d-划分准则我们看到总存在一个路径通过潜在变量连接了任意两个观测变量 x n x_n xn和 x m x_m xm并且这个路径永远不会被阻隔。对于观测变量 x n 1 x_{n1} xn1来说给定所有之间的观测条件概率分布 p ( x n 1 ∣ x 1 : n ) p(x_{n1}|x_{1:n}) p(xn1∣x1:n)不会表现出任何的条件独立性因为对 x n 1 x_{n1} xn1的预测依赖于所有之前的观测。
对于顺序数据来说如果潜在变量是离散的那么这个图描述的就是隐马尔可夫模型。
隐马尔可夫模型的基本概念
隐马尔可夫模型的定义
定义 10.1(隐马尔可夫模型) 隐马尔可夫模型是关于时序的概率模型描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列(状态序列,state sequence)然后由每个状态生成一个观测从而产生随机观测序列(observation sequence)的过程。序列的每一个位置又可以看作是一个时刻。
隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定模型概率图示如图1所示模型的形式定义为 图1 HMM的概率图 设 Q Q Q是所有可能的状态的集合 V V V是所有可能的观测的集合 Q { q 1 , q 2 , ⋯ , q N } , V { v 1 , v 2 , ⋯ , v M } Q\{q_1,q_2,\cdots,q_N\},\qquad V\{v_1,v_2,\cdots,v_M\} Q{q1,q2,⋯,qN},V{v1,v2,⋯,vM} 其中 N N N是可能的状态数 M M M是可能的观测数。 I I I是长度为 T T T的状态序列 O O O是对应的观测序列由于一个状态生成一个观测所以它们的长度是相同的 I ( i 1 , i 2 , ⋯ , i T ) , O ( o 1 , o 2 , ⋯ , o T ) I(i_1,i_2,\cdots,i_T),\qquad O(o_1,o_2,\cdots,o_T) I(i1,i2,⋯,iT),O(o1,o2,⋯,oT) A A A是状态转移概率矩阵 A [ a i j ] N × N (10.1) A[a_{ij}]_{N\times N} \tag{10.1} A[aij]N×N(10.1) 其中 a i j P ( i t 1 q j ∣ i t q i ) , i 1 , 2 , ⋯ , N ; j 1 , 2 , ⋯ , N (10.2) a_{ij} P(i_{t1}q_j|i_tq_i),\quad i1,2,\cdots,N;\quad j1,2,\cdots,N \tag{10.2} aijP(it1qj∣itqi),i1,2,⋯,N;j1,2,⋯,N(10.2) 表示时刻 t t t处于状态 q i q_i qi的条件下在时刻 t 1 t1 t1转移到状态 q j q_j qj的概率。 B B B是观测概率矩阵 B [ b j ( k ) ] N × M (10.3) B[b_j(k)]_{N \times M} \tag{10.3} B[bj(k)]N×M(10.3) 其中 b j ( k ) P ( o t v k ∣ i t q j ) , k 1 , 2 , ⋯ , M ; j 1 , 2 , ⋯ , N (10.4) b_j(k) P(o_tv_k|i_tq_j),\quad k1,2,\cdots,M;\quad j1,2,\cdots,N \tag{10.4} bj(k)P(otvk∣itqj),k1,2,⋯,M;j1,2,⋯,N(10.4) 这个表示可能不好理解类似 a i j a_{ij} aij下标表示状态那么这里用括号表示观测。
表示时刻 t t t处于状态 q j q_j qj的条件下生成观测 v k v_k vk的概率。 b j ( k ) b_j(k) bj(k)只涉及到当前时刻 t t t。 π \pi π是初始状态概率向量 π ( π i ) (10.5) \pi (\pi_i) \tag{10.5} π(πi)(10.5) 其中 π i P ( i 1 q i ) , i 1 , 2 , ⋯ , N (10.6) \pi_i P(i_1q_i),\quad i1,2,\cdots,N \tag{10.6} πiP(i1qi),i1,2,⋯,N(10.6) 还是用下标表示状态但符号变成了 π \pi π表示时刻 t 1 t1 t1处于状态 q i q_i qi的概率所以是初始概率。
上面的符号有点多记不住没关系后面碰到的时候多回顾几次就好了。
HMM由初始状态概率向量 π \pi π、状态转移概率矩阵 A A A和观测概率矩阵 B B B决定。 π \pi π和 A A A决定状态序列 B B B决定观测序列。因此隐马尔可夫模型 λ \lambda λ可用三元符号表示 λ ( A , B , π ) (10.7) \lambda(A,B,\pi) \tag{10.7} λ(A,B,π)(10.7) A , B , π A,B,\pi A,B,π称为隐马尔可夫模型的三要素。
A和 π \pi π确定了隐藏的马尔可夫链生成不可观测的状态序列。观测概率矩阵 B B B确定了如何从状态生成观测。
从定义可知隐马尔可夫模型作了两个基本假设
(1) 齐次马尔可夫性假设即假设隐藏的马尔可夫链在任意时刻 t t t的状态只依赖于其前一时刻的状态与其他时刻的状态及观测无关也与时刻 t t t无关 P ( i t ∣ i t − 1 , o t − 1 , ⋯ , i 1 , o 1 ) P ( i t ∣ i t − 1 ) t 1 , 2 , ⋯ , T (10.8) P(i_t|i_{t-1},o_{t-1},\cdots,i_1,o_1) P(i_t|i_{t-1})\quad t1,2,\cdots,T \tag{10.8} P(it∣it−1,ot−1,⋯,i1,o1)P(it∣it−1)t1,2,⋯,T(10.8) 齐次指的是任何时刻的状态转移概率与时刻 t t t无关都是一样的。
(2) 观测独立假设即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态与其他观测及状态无关 P ( o t ∣ i T , o T , i T − 1 , o T − 1 , ⋯ , i t 1 , o t 1 , i t , i t − 1 , o t − 1 , ⋯ , i 1 , o 1 ) P ( o t ∣ i t ) (10.9) P(o_t|i_T,o_T,i_{T-1},o_{T-1},\cdots,i_{t1},o_{t1},i_t,i_{t-1},o_{t-1},\cdots,i_1,o_1) P(o_t|i_t) \tag{10.9} P(ot∣iT,oT,iT−1,oT−1,⋯,it1,ot1,it,it−1,ot−1,⋯,i1,o1)P(ot∣it)(10.9)
隐马尔可夫模型可用于标注此时状态就对应要标注的标签(标记)。标注问题的标记是隐藏的、未知的已知的是观测到的(单词)序列。
例 10.1(盒子和球模型) 假设有4个盒子每个盒子里都装有红、白两种颜色的球。该例子主要是描述了初始概率分布 π \pi π状态转移概率分布 A A A和观测概率分布 B B B。具体可以查阅书上的内容。
观测序列的生成过程
可以将一个长度为 T T T的观测序列 O ( o 1 , o 2 , ⋯ , o T ) O(o_1,o_2,\cdots,o_T) O(o1,o2,⋯,oT)的生成过程描述如下。
算法10.1(观测序列的生成)
输入隐马尔可夫模型 λ ( A , B , π ) \lambda(A,B,\pi) λ(A,B,π)观测序列长度 T T T
输出观测序列 O ( o 1 , o 2 , ⋯ , o T ) O(o_1,o_2,\cdots,o_T) O(o1,o2,⋯,oT)。
(1) 安装初始状态分布 π \pi π产生状态 i 1 i_1 i1
(2) 令 t 1 t1 t1
(3) 按照状态 i t i_t it的观测概率分布 b i t ( k ) b_{i_t}(k) bit(k)生成 o t v k o_tv_k otvk
(4) 按照状态 i t i_t it的状态转移概率分布 { a i t , i t 1 } \{a_{i_t,i_{t1}}\} {ait,it1}产生状态 i t 1 i_{t1} it1
(5) 令 t t 1 tt1 tt1如果 t T t T tT转步(3)否则终止。
隐马尔可夫模型的3个基本问题
隐马尔可夫模型由3个基本问题
(1) 概率计算问题。给定模型 λ ( A , B , π ) \lambda(A,B,\pi) λ(A,B,π)和观测序列 O ( o 1 , o 2 , ⋯ , o T ) O(o_1,o_2,\cdots,o_T) O(o1,o2,⋯,oT)计算在模型 λ \lambda λ下观测序列 O O O出现的概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)。
(2) 学习问题。已知观测序列 O ( o 1 , o 2 , ⋯ , o T ) O(o_1,o_2,\cdots,o_T) O(o1,o2,⋯,oT)估计模型 λ ( A , B , π ) \lambda(A,B,\pi) λ(A,B,π)参数使得在该模型下观测序列概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)最大。即用极大似然估计法估计参数。
(3) 预测问题也称为解码问题。已知模型 λ ( A , B , π ) \lambda(A,B,\pi) λ(A,B,π)和观测序列 O ( o 1 , o 2 , ⋯ , o T ) O(o_1,o_2,\cdots,o_T) O(o1,o2,⋯,oT)求对给定观测序列条件概率 P ( I ∣ O ) P(I|O) P(I∣O)最大的状态序列 I ( i 1 , i 2 , ⋯ , i T ) I(i_1,i_2,\cdots,i_T) I(i1,i2,⋯,iT)。即给定观测序列求对应的最有可能的状态序列。 文章转载自： http://www.morning.dwgcx.cn.gov.cn.dwgcx.cn http://www.morning.wrtpk.cn.gov.cn.wrtpk.cn http://www.morning.mjjty.cn.gov.cn.mjjty.cn http://www.morning.fgxnb.cn.gov.cn.fgxnb.cn http://www.morning.frpb.cn.gov.cn.frpb.cn http://www.morning.hwhnx.cn.gov.cn.hwhnx.cn http://www.morning.fpqsd.cn.gov.cn.fpqsd.cn http://www.morning.ssxlt.cn.gov.cn.ssxlt.cn http://www.morning.gnjkn.cn.gov.cn.gnjkn.cn http://www.morning.lgpzq.cn.gov.cn.lgpzq.cn http://www.morning.ybmp.cn.gov.cn.ybmp.cn http://www.morning.tsmxh.cn.gov.cn.tsmxh.cn http://www.morning.qwnqt.cn.gov.cn.qwnqt.cn http://www.morning.hbjqn.cn.gov.cn.hbjqn.cn http://www.morning.ylyzk.cn.gov.cn.ylyzk.cn http://www.morning.mlzyx.cn.gov.cn.mlzyx.cn http://www.morning.tkrpt.cn.gov.cn.tkrpt.cn http://www.morning.gbjxj.cn.gov.cn.gbjxj.cn http://www.morning.tbrnl.cn.gov.cn.tbrnl.cn http://www.morning.jrrqs.cn.gov.cn.jrrqs.cn http://www.morning.stlgg.cn.gov.cn.stlgg.cn http://www.morning.rfyk.cn.gov.cn.rfyk.cn http://www.morning.ffwrq.cn.gov.cn.ffwrq.cn http://www.morning.kqzrt.cn.gov.cn.kqzrt.cn http://www.morning.dphmj.cn.gov.cn.dphmj.cn http://www.morning.qpmmg.cn.gov.cn.qpmmg.cn http://www.morning.qbgff.cn.gov.cn.qbgff.cn http://www.morning.hcsqznn.cn.gov.cn.hcsqznn.cn http://www.morning.xgjhy.cn.gov.cn.xgjhy.cn http://www.morning.sffwz.cn.gov.cn.sffwz.cn http://www.morning.hnrpk.cn.gov.cn.hnrpk.cn http://www.morning.kfcz.cn.gov.cn.kfcz.cn http://www.morning.cznsq.cn.gov.cn.cznsq.cn http://www.morning.jfjbl.cn.gov.cn.jfjbl.cn http://www.morning.rqsnl.cn.gov.cn.rqsnl.cn http://www.morning.mcjrf.cn.gov.cn.mcjrf.cn http://www.morning.srcth.cn.gov.cn.srcth.cn http://www.morning.pynzj.cn.gov.cn.pynzj.cn http://www.morning.ltkms.cn.gov.cn.ltkms.cn http://www.morning.wjlbb.cn.gov.cn.wjlbb.cn http://www.morning.kntbk.cn.gov.cn.kntbk.cn http://www.morning.yymlk.cn.gov.cn.yymlk.cn http://www.morning.nmyrg.cn.gov.cn.nmyrg.cn http://www.morning.xcszl.cn.gov.cn.xcszl.cn http://www.morning.yxlpj.cn.gov.cn.yxlpj.cn http://www.morning.qbwyd.cn.gov.cn.qbwyd.cn http://www.morning.znsyn.cn.gov.cn.znsyn.cn http://www.morning.rysmn.cn.gov.cn.rysmn.cn http://www.morning.ymyhg.cn.gov.cn.ymyhg.cn http://www.morning.krxzl.cn.gov.cn.krxzl.cn http://www.morning.lmbm.cn.gov.cn.lmbm.cn http://www.morning.sryyt.cn.gov.cn.sryyt.cn http://www.morning.mrfjr.cn.gov.cn.mrfjr.cn http://www.morning.jytrb.cn.gov.cn.jytrb.cn http://www.morning.yngtl.cn.gov.cn.yngtl.cn http://www.morning.qpzjh.cn.gov.cn.qpzjh.cn http://www.morning.qbtkg.cn.gov.cn.qbtkg.cn http://www.morning.ymjrg.cn.gov.cn.ymjrg.cn http://www.morning.xpqyf.cn.gov.cn.xpqyf.cn http://www.morning.wtwhj.cn.gov.cn.wtwhj.cn http://www.morning.gjmll.cn.gov.cn.gjmll.cn http://www.morning.snktp.cn.gov.cn.snktp.cn http://www.morning.kqlrl.cn.gov.cn.kqlrl.cn http://www.morning.wyrsn.cn.gov.cn.wyrsn.cn http://www.morning.paoers.com.gov.cn.paoers.com http://www.morning.wgqtt.cn.gov.cn.wgqtt.cn http://www.morning.pfnlc.cn.gov.cn.pfnlc.cn http://www.morning.wrtsm.cn.gov.cn.wrtsm.cn http://www.morning.hrtct.cn.gov.cn.hrtct.cn http://www.morning.scjtr.cn.gov.cn.scjtr.cn http://www.morning.ynstj.cn.gov.cn.ynstj.cn http://www.morning.mfmx.cn.gov.cn.mfmx.cn http://www.morning.kgfsz.cn.gov.cn.kgfsz.cn http://www.morning.cprls.cn.gov.cn.cprls.cn http://www.morning.jxlnr.cn.gov.cn.jxlnr.cn http://www.morning.jrplk.cn.gov.cn.jrplk.cn http://www.morning.kjksn.cn.gov.cn.kjksn.cn http://www.morning.rkdzm.cn.gov.cn.rkdzm.cn http://www.morning.bpmfq.cn.gov.cn.bpmfq.cn http://www.morning.pxlpt.cn.gov.cn.pxlpt.cn
