【统计学习方法】隐马尔可夫模型(HMM) Python实现

小咪咪 2022-05-26 12:00 47阅读 0赞

# 前言 #

代码可在Github上下载:[代码下载][Link 1]  
隐马尔可夫模型在自然语言处理等各领域中，经常被用来处理标注问题。

> 隐马尔可夫模型由初始状态概率向量 π \\pi π、状态转移概率矩阵A和观测概率矩阵B决定。其中 π \\pi π和A决定状态序列，B决定观测序列。  
>  λ = ( A , B , π ) \\lambda=(A,B,\\pi) λ=(A,B,π)  
>  A = \[ a i j \] N × N \{\\rm\{A = \}\}\{\\left\[ \{ \{a\_\{ij\}\}\} \\right\]\_\{N \\times N\}\} A=\[aij\]N×N  
> 其中  a i j = P ( i t + 1 = q j ∣ i t = q i ) \{a\_\{ij\}\} = P\\left( \{ \{i\_\{t + 1\}\} = \{q\_j\}|\{i\_t\} = \{q\_i\}\} \\right) aij=P(it\+1=qj∣it=qi)，表示t时刻的状态 q i \{q\_i\} qi转移到t+1时刻的状态 q j 的 概 率 \{q\_j\}的概率 qj的概率  
>  B = \[ b j ( k ) \] N × M B = \{\\left\[ \{ \{b\_j\}\\left( k \\right)\} \\right\]\_\{N \\times M\}\} B=\[bj(k)\]N×M  
> 其中 b j ( k ) = P ( o t = v k ∣ i t = q j ) \{b\_j\}\\left( k \\right) = P\\left( \{ \{o\_t\} = \{v\_k\}|\{i\_t\} = \{q\_j\}\} \\right) bj(k)=P(ot=vk∣it=qj)，表示t时刻 q j q\_j qj生成观测 v k v\_k vk的概率  
>  π = ( π i ) \\pi=(\{\\pi\_i\}) π=(πi)  
> 其中 π i = P ( i 1 = q i ) \{\\pi\_i\}=P(\{i\_1\}=\{q\_i\}) πi=P(i1=qi)表示t=1时刻处于 q i \{q\_i\} qi的概率

其中隐马尔可夫有两个基本假设：  
（1）齐次马尔科夫行假设，任意时刻t的状态只依赖t-1时刻的状态。  
（2）观测独立性假设，当前时刻的观测只依赖当前时刻的状态。

有了以上定义，我们来试图解决隐马尔可夫模型有3个基本问题：（1）概率计算问题（2）学习问题（3）预测问题。  
本文主要实现了隐马尔可夫模型中的前向算法，后向算法，以及维特比算法。重点讲下前向算法，如果前向算法能理解，那后向算法和维特比算法也将迎刃而解。

# 概率计算算法 #

概率计算问题就是给出一个观测序列 O = ( o 1 , o 2 , . . . , o T ) O=(o\_1,o\_2,...,o\_T) O=(o1,o2,...,oT)，求出 P = ( O ∣ λ ) P=(O|\\lambda) P=(O∣λ)的概率。  
概率计算算法通常有（1）直接计算法（2）前向算法（3）后向算法。  
直接计算法简单来说就是求出所有可能的状态序列所对应的观测序列进行计算，这当然是不可能的。  
那么还有的一种办法是前向算法。首先先思考，想要得到一个观测 o 1 o\_1 o1的概率，我们是否可以将所有可能的状态 a i a\_i ai乘以对应的观测概率 b i ( o 1 ) 得 到 b\_i(o\_1)得到 bi(o1)得到 p ( o 1 ∣ λ ) = ∑ i = 1 N q i 1 b i ( o 1 ) p(o\_1|\\lambda)=\\sum\\limits\_\{i = 1\}^N \{ \{q\_\{i1\}\}\{b\_i\}\\left( \{ \{o\_1\}\} \\right)\} p(o1∣λ)=i=1∑Nqi1bi(o1)得到？明显是可以的。  
进一步地，我们想得到 P ( o 1 , o 2 ∣ λ ) P(o\_1,o\_2|\\lambda) P(o1,o2∣λ)，那么我们可以 p ( o 2 ∣ λ ) = ∑ i = 1 N q i 2 b i ( o 1 ) p(o\_2|\\lambda)=\\sum\\limits\_\{i = 1\}^N \{ \{q\_\{i2\}\}\{b\_i\}\\left( \{ \{o\_1\}\} \\right)\} p(o2∣λ)=i=1∑Nqi2bi(o1)，但是我们要想把 q i 2 q\_\{i2\} qi2跟刚才关联起来，变成求 p ( o 1 , o 2 ∣ λ ) p(o\_1,o\_2|\\lambda) p(o1,o2∣λ)的话，我们需要考虑有哪些状态达到 q i 2 q\_\{i2\} qi2，可能是状态 q 11 q\_\{11\} q11，也有可能是状态 q 12 q\_\{12\} q12， p ( o 1 , o 2 ∣ λ ) p(o\_1,o\_2|\\lambda) p(o1,o2∣λ)可以改写成 p ( o 1 , o 2 ∣ λ ) = ∑ i = 1 N ∑ j = 1 N q i 1 b j ( o 1 ) a j i b i ( o 2 ) p(\{o\_1\},\{o\_2\}|\\lambda ) = \\sum\\limits\_\{i = 1\}^N \{\\sum\\limits\_\{j = 1\}^N \{ \{q\_\{i1\}\}\{b\_j\}\\left( \{ \{o\_1\}\} \\right)\{a\_\{ji\}\}\{b\_i\}\\left( \{ \{o\_2\}\} \\right)\} \} p(o1,o2∣λ)=i=1∑Nj=1∑Nqi1bj(o1)ajibi(o2)。  
于是先定义 α t ( i ) \\alpha\_t(i) αt(i)为观测序列 O = ( o 1 , o 2 , . . . , o t ) O=(o\_1,o\_2,...,o\_t) O=(o1,o2,...,ot)，且状态为 I t = q i I\_t=q\_i It=qi的概率。当我们想得到 O = ( o 0 , o 1 , . . . , o t + 1 ) O=(o\_0,o\_1,...,o\_\{t+1\}) O=(o0,o1,...,ot\+1)的概率时，只要得到 a t + 1 ( i ) a\_\{t+1\}(i) at\+1(i)，并且求和即可。

## 前向算法实现 ##

def forward(self, Q, V, A, B, O, PI):  # 使用前向算法
        N = len(Q)  # 状态序列的大小
        M = len(O)  # 观测序列的大小
        alphas = np.zeros((N, M))  # alpha值
        T = M  # 有几个时刻，有几个观测序列，就有几个时刻
        for t in range(T):  # 遍历每一时刻，算出alpha值
            indexOfO = V.index(O[t])  # 找出序列对应的索引
            for i in range(N):
                if t == 0:  # 计算初值
                    alphas[i][t] = PI[t][i] * B[i][indexOfO]  # P176（10.15）
                    print('alpha1(%d)=p%db%db(o1)=%f' % (i, i, i, alphas[i][t]))
                else:
                    alphas[i][t] = np.dot([alpha[t - 1] for alpha in alphas], [a[i] for a in A]) * B[i][
                        indexOfO]  # 对应P176（10.16）
                    print('alpha%d(%d)=[sigma alpha%d(i)ai%d]b%d(o%d)=%f' % (t, i, t - 1, i, i, t, alphas[i][t]))
                    # print(alphas)
        P = np.sum([alpha[M - 1] for alpha in alphas])  # P176(10.17)
        # alpha11 = pi[0][0] * B[0][0]    #代表a1(1)
        # alpha12 = pi[0][1] * B[1][0]    #代表a1(2)
        # alpha13 = pi[0][2] * B[2][0]    #代表a1(3)

首先需要一个矩阵来存储alpha值`alphas = np.zeros((N, M)) #alpha值`，这里定义了一个 N × M N \\times M N×M大小的矩阵，每一列是一个时刻存储的alpha值，总共有M（T个时刻）列。  
按照书上P175算法10.2，需要遍历每个时刻，所以`for t in range(T): #遍历每一时刻，算出alpha值`，然后每种时刻需要计算N个状态，也就是`for i in range(N):`。  
当t=0时（由于大多数计算机编程的数组大多是从0开始，所以这里的0代表是时刻t=1），我们需要计算初值，p176（10.15）

if t == 0:  # 计算初值
          alphas[i][t] = PI[t][i] * B[i][indexOfO]

然后，递推算出，  
`alphas[i][t] = np.sum(np.multiply([alpha[t-1] for alpha in alphas], [a[i] for a in A])) * B[i][indexOfO] #对应P176（10.16）`等到执行完毕后，我们就得到了一个alpha矩阵了，这是这个算法最终的东西了。  
也许看到这里，有人会无法理解上面这段代码和公式的写法。这里我解释一下，通常看到 ∑ j = 1 N α i ( j ) a j i \\sum\\limits\_\{j = 1\}^N \{ \{\\alpha\_i\}\\left( j \\right)\{a\_\{ji\}\}\} j=1∑Nαi(j)aji，第一反应是会先想到用一个for循环来做，但是我这里的做法是提取出两个向量，然后求内积(使用np.dot()，这是一个可以求出内积的函数)，这也是吴恩达所推荐的一种做法，原因对向量操作会for循环效率会高。  
最后根据书上的公式得到最终的P，代码如下。

P = np.sum([alpha[M - 1] for alpha in alphas])  # P176(10.17)

好，这里也就是本次前向算法的实现。

## 后向算法实现 ##

后向算法定义 β t ( i ) = P ( o t + 1 , o t + 2 , . . . , o T ∣ i t = q i , λ ) \\beta\_t(i)=P(o\_\{t+1\},o\_\{t+2\},...,o\_T|i\_t=q\_i,\\lambda) βt(i)=P(ot\+1,ot\+2,...,oT∣it=qi,λ)。  
想得到 P ( o 1 , o 2 , . . . , o T ∣ i t = q i , λ ) P(o\_\{1\},o\_\{2\},...,o\_T|i\_t=q\_i,\\lambda) P(o1,o2,...,oT∣it=qi,λ)的话，得到 i 0 i\_0 i0代入即可。  
有了前向算法的实现，我们同理可以得到后向算法。

def backward(self, Q, V, A, B, O, PI):  # 后向算法
        N = len(Q)  # 状态序列的大小
        M = len(O)  # 观测序列的大小
        betas = np.ones((N, M))  # beta
        for i in range(N):
            print('beta%d(%d)=1' % (M, i))
        for t in range(M - 2, -1, -1):
            indexOfO = V.index(O[t + 1])  # 找出序列对应的索引
            for i in range(N):
                betas[i][t] = np.dot(np.multiply(A[i], [b[indexOfO] for b in B]), [beta[t + 1] for beta in betas])
                realT = t + 1
                realI = i + 1
                print('beta%d(%d)=[sigma a%djbj(o%d)]beta%d(j)=(' % (realT, realI, realI, realT + 1, realT + 1),
                      end='')
                for j in range(N):
                    print("%.2f*%.2f*%.2f+" % (A[i][j], B[j][indexOfO], betas[j][t + 1]), end='')
                print("0)=%.3f" % betas[i][t])
        # print(betas)
        indexOfO = V.index(O[0])
        P = np.dot(np.multiply(PI, [b[indexOfO] for b in B]), [beta[0] for beta in betas])
        print("P(O|lambda)=", end="")
        for i in range(N):
            print("%.1f*%.1f*%.5f+" % (PI[0][i], B[i][indexOfO], betas[i][0]), end="")
        print("0=%f" % P)

# 预测算法 #

类似的，等你学会实现前向算法，维特比算法也是依葫芦画瓢。这里不再赘述，直接给出算法，该算法可以用来预测出状态。

def viterbi(self, Q, V, A, B, O, PI):
        N = len(Q)  # 状态序列的大小
        M = len(O)  # 观测序列的大小
        deltas = np.zeros((N, M))
        psis = np.zeros((N, M))
        I = np.zeros((1, M))
        for t in range(M):
            realT = t+1
            indexOfO = V.index(O[t])  # 找出序列对应的索引
            for i in range(N):
                realI = i+1
                if t == 0:
                    deltas[i][t] = PI[0][i] * B[i][indexOfO]
                    psis[i][t] = 0
                    print('delta1(%d)=pi%d * b%d(o1)=%.2f * %.2f=%.2f'%(realI, realI, realI, PI[0][i], B[i][indexOfO], deltas[i][t]))
                    print('psis1(%d)=0' % (realI))
                else:
                    deltas[i][t] = np.max(np.multiply([delta[t-1] for delta in deltas], [a[i] for a in A])) * B[i][indexOfO]
                    print('delta%d(%d)=max[delta%d(j)aj%d]b%d(o%d)=%.2f*%.2f=%.5f'%(realT, realI, realT-1, realI, realI, realT, np.max(np.multiply([delta[t-1] for delta in deltas], [a[i] for a in A])), B[i][indexOfO], deltas[i][t]))
                    psis[i][t] = np.argmax(np.multiply([delta[t-1] for delta in deltas], [a[i] for a in A]))
                    print('psis%d(%d)=argmax[delta%d(j)aj%d]=%d' % (realT, realI, realT-1, realI, psis[i][t]))
        print(deltas)
        print(psis)
        I[0][M-1] = np.argmax([delta[M-1] for delta in deltas])
        print('i%d=argmax[deltaT(i)]=%d' % (M, I[0][M-1]+1))
        for t in range(M-2, -1, -1):
            I[0][t] = psis[int(I[0][t+1])][t+1]
            print('i%d=psis%d(i%d)=%d' % (t+1, t+2, t+2, I[0][t]+1))
        print(I)=argmax[deltaT(i)]=%d' % (M, I[0][M-1]+1))
            for t in range(M-2, -1, -1):
                I[0][t] = psis[int(I[0][t+1])][t+1]
                print('i%d=psis%d(i%d)=%d' % (t+1, t+2, t+2, I[0][t]+1))
            print(I)

[Link 1]: https://github.com/FlameCharmander/MachineLearning