Question

Markov Model

马可夫模型大意是：选一个状态作为起点，然后沿著边随意走访任何一个状态，一直走一直走，沿途累计机率，走累了就停在某个状态。

熟悉“ 图论 ”的读者应该很快就能上手，马可夫模型的外观看起来就是图──只不过代数符号多得令人生厌。

建议阅读：L. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, vol. 77, No. 2, February 1989.

State, S

图片中，每一个圆圈叫做一个“状态”。马可夫模型一共有 N 个状态，通常标作 s₁到 s_N。N 是我们自行设定的常数。

全部状态构成的集合，标作大写 S。

Transition Probability, A

每一个状态都会射出 N 条边，这 N 条边分别连向每一个状态，这 N 条边的数值都是机率，这 N 条边的数值皆介于 0 到 1，这 N 条边的数值总和必为 1，满足机率公设。

一条由状态 s_i到状态 s_j的边，其数值通常标作 a_ij。亦可标作条件机率 P( s_j | s_i )，意思是现在在状态 s_i、要来去状态 s_j。亦可套用稍后提到的状态序列，标作 P( q_t+1 = j | q_t = i )。

全部边构成的集合，标作 A。通常把 A 看作一个 N×N 矩阵。

写程式时，我们可以利用图的资料结构 adjacency matrix 储存全部的数值。当 A 有很多数值是零，去掉一些边之后，也可以改用 adjacency lists。

Initial Probability, Π

我们可以选择任何一个状态作为起点。机率总和为 1。

绘制图片时，我们可以设计一个虚幻状态 s₀，让 s₀射出 N 条虚幻边，分别连向每一个状态，其数值满足机率公设。如此一来我们就可以从冥冥之中的 s₀开始行动。

这 N 条虚幻边的数值通常标作π₁到π_N。亦可标作机率 P( s₁ ) 到 P( s_N )。亦可套用稍后提到的状态序列，标作 P( q₁ = 1 ) 到 P( q₁ = N )。

这 N 条虚幻边构成的集合，标作Π。通常把Π看作一个 N 维向量、一个 N×1 矩阵。

写程式时，通常我们不会设计一个虚幻的状态 s₀，而是把状态 s₁到 s_N重新标作 s₀到 s_N-1。

State Sequence, q₁ q₂ ...... q_T

选定起点后，可以沿著边，到处走来走去，一路走过 T 个状态以及 T-1 条边之后，就停下来。T 是我们自行设定的常数。

一条路径，通常标作 q₁ q₂ ...... q_T，为途经的状态编号。

一条路径的机率，可以写成π_q1 × a_q1q2 × ...... × a_qT-1qT，也可以写成 P( s_q1 ) × P( s_q2 | s_q1 ) × ...... × P( s_qT | s_qT-1 )。

Hidden Markov Model

Observation, V

隐藏马可夫模型添加了一个新要素：每当造访一个状态，就立刻从 M 个值当中，喷出其中一个值。每一个状态都是喷出相同的 M 种值，这 M 个值通常标作 v₁到 v_M。M 是我们自行设定的常数。

全部观察构成的集合，标作大写 V。

Observation Probability, B

每一个状态喷出这 M 种值的机率都不相同。

状态 s_i喷出 v_k的机率，通常标作 b_i( k ) 或者简单标作 b_ik。亦可标作条件机率 P( v_k | s_i )，意思是现在在状态 s_i、喷出观察 v_k。亦可套用状态序列与观察序列，标作 P( o_t = k | q_t = i )。

每个状态各自的喷出机率构成的集合，标作 B。通常把 B 看作 N 个函数，或者简单地看作一个 N×M 矩阵。

Observation Sequence, o₁ o₂ ...... o_T

走 T 步后，一路上 T 个状态个别喷出的值的编号。

有了状态序列与观察序列，一条路径的机率，可以写成π_q1 × b_q1( o₁ ) × a_q1q2 × b_q2( o₂ ) × ...... × a_qT-1qT × b_qT( o_T )，也可以写成 P( s_q1 ) × P( v_o1 | s_q1 ) × P( s_q2 | s_q1 ) × P( v_o2 | s_q2 ) × ...... × P( s_qT | s_qT-1 ) × P( v_oT | s_qT )。我想各位差不多眼花撩乱了。名可名，非常名，若能领会原理就不用刻意背诵代数了。

Continuous Hidden Markov Model

Gaussian Mixture Model

之前说，每个状态都会喷出 M 种固定的值。然而现实生活中，观察值通常是实数，也通常有误差，不见得恰好就是这 M 种值。

一个直觉的解决方案是假设误差呈常态分布：以常态分布的平均数μ，代表正确的喷出数值；以常态分布的变异数σ²，控制误差范围。M 个观察值分别制作 M 个常态分布，标作 N( v , μ₁ , σ₁² ) 到 N( v , μ_M , σ_M² )。

状态不再喷出 k 种值，而是有 k 种喷出管道。观察值不再是固定的、离散的数值 v₁到 v_M，而是变动的、连续的数值 v。

使用第 k 个喷出管道的机率，仍标作 b_i( k )。在第 k 个喷出管道，喷出数值 v 的机率，是一个常态分布函数 N( v , μ_k , σ_k² )；v 代入一个实际数值，就能计算其喷出机率。

当各个常态分布的平均数很接近，或者变异数很大时，不同的喷出管道可能喷出相同数值。状态 s_i喷出数值 v 的机率，M 个喷出管道都必须累计，为∑_i=1~M [ b_i( k ) × N( v , μ_k , σ_k² ) ]。

综观整个过程，是把 M 个常态分布以不同比重叠加起来，合成一个分布──此概念称作高斯混合模型，可以应用在许多地方，连续版本的 HMM 便是一例。另外，通常会将 b_i( k ) 重新标作 c_ik，以呼应加权比重的概念。

写程式时，我们不会预先叠加起来，而是分别记录 M 个常态分布的平均数和变异数。

每个状态喷出不同的观察值

套用高斯混合模型，观察值从原先的离散数值变成了连续数值。换个角度想，套用高斯混合模型，就能制造任何一种我们想要的连续分布。

每个状态可以使用不同平均数、不同变异数的常态分布，甚至可以使用不同数量的常态分布。状态 s_i使用的常态分布，标作 N( v , μ_ik , σ_ik² )。

观察值推广到高维度

观察值可以从一个值推广为一个向量。其实也就是每个维度分开处理罢了。

至于 Learning Problem，则要额外更新常态分布的平均数、变异数、加权比重了：

　　　路径第一步，穿过状态 si。
πi  =  γ1(i)

　　　分子是穿过边 aij。分母是穿过状态 si。
       ∑t=1~T-1 [ ξt(i,j) ]
aij = —————————————————————
         ∑t=1~T [ γt(i) ]

　　　分子是穿过状态 si、使用第 k 个喷出管道。分母是穿过状态 si。
          ∑t=1~T [ γtk(i) ]
cik = ————————————————————————
       ∑t=1~T ∑k=1~M [ γtk(i) ]

　　　分子是穿过状态 si、使用第 k 个喷出管道、喷出数值的平均数。
       ∑t=1~T [ γtk(i) ] * ot
μik = ————————————————————————
          ∑t=1~T [ γtk(i) ]

　　　分子是穿过状态 si、使用第 k 个喷出管道、喷出数值的共变异矩阵。
       ∑t=1~T [ γtk(i) ] * (ot - μik)(ot - μik)T
Σik = ——————————————————————————————————————————
                  ∑t=1~T [ γtk(i) ]

至此产生了连续版本的 HMM，已经可以应付各种情况了！