隐马尔可夫模型--习题

10.1

本题考查概率计算的前向或后向算法:

前向算法：$${\alpha }_{t+1}(i)=[\sum _{j=1}^N{\alpha }_t(j)\ast aji]\ast b_i(O_{t+1})$$
后向算法：$${\beta }_t(i)=\sum _{j=1}^N{a}_{ij}{b}_j(O_{t+1}){\beta }_{t+1}(j)$$
下面给出基于numpy库的实现：

import numpy as np


# 前向算法
def forward_algorithm(A, B, pi, O, t=None):
    state = len(O) if t is None else t
    alpha = np.ones_like(pi)
    for i in range(state):
        a = pi if i == 0 else np.sum(alpha * A, axis=0, keepdims=True).T
        alpha = a * B[:, O[i]: O[i] + 1]
    return alpha, alpha.sum()


# 后向算法
def backward_algorithm(A, B, pi, O, t=None):
    state = -1 if t is None else len(O)-t-1
    beta = np.ones_like(pi)
    for i in range(len(O) - 1, state, -1):
        a = A if i != 0 else pi.T
        beta = np.sum(a * B[:, O[i]] * beta.T, axis=1, keepdims=True)
    return beta, beta.sum()
    
if __name__ == "__main__":
	A = np.array([[0.5, 0.2, 0.3],
                  [0.3, 0.5, 0.2],
                  [0.2, 0.3, 0.5]])
    B = np.array([[0.5, 0.5],
                  [0.4, 0.6],
                  [0.7, 0.3]])
    pi = np.array([0.2, 0.4, 0.4]).reshape((-1, 1))
    O = [0, 1, 0, 1]
    print(forward_algorithm(A, B, pi, O))
    # 得出答案: 0.06009079999999999
    print(backward_algorithm(A, B, pi, O))
    # 得出答案: 0.06009079999999999

---

10.2

本题主要考察利用前向概率和后向概率，计算关于单个状态的概率，在给定观测序列O和模型$\lambda$下，t时刻处于的概率为$q_i$的概率为：
$${\gamma }_t(i)=P(i_t=q_i,O|\lambda )=\frac{{\alpha }_t(i)\ast {\beta }_t(i)}{{\sum }_{i=1}^N{\alpha }_t(i)\ast {\beta }_t(i)}$$

# 前向后向算法单个状态概率计算
def gamma_t(A, B, pi, O, t, i):
    alpha, alpha_sum = forward_algorithm(A, B, pi, O, t)
    beta, beta_sum = backward_algorithm(A, B, pi, O, t)
    alpha_beta_t = alpha * beta
    return alpha_beta_t[i-1].item() / alpha_beta_t.sum()


if __name__ == '__main__':
    A = np.array([[0.5, 0.1, 0.4],
                  [0.3, 0.5, 0.2],
                  [0.2, 0.2, 0.6]])
    B = np.array([[0.5, 0.5],
                  [0.4, 0.6],
                  [0.7, 0.3]])
    pi = np.array([0.2, 0.3, 0.5]).reshape((-1, 1))
    O = [0, 1, 0, 0, 1, 0, 1, 1]
    print(gamma_t(A, B, pi, O, t=4, i=3))
    # 得出答案: 0.5369518160647323

---

10.3

本题主要考察维比特算法的迭代公式：

# 维特比算法
def viterbi_algorithm(A, B, pi, O):
    state_num = A.shape[0]
    delta = np.ones_like(pi)
    psi = np.zeros((len(O), state_num), dtype=np.int)
    for i in range(len(O)):
        a = pi
        if i != 0:
            a = delta * A
            psi[i] = np.argmax(a, axis=0)
            a = a[psi[i], np.arange(state_num)].reshape(-1, 1)
        delta = a * B[:, O[i]: O[i] + 1]
    path = [np.argmax(delta)]
    for i in range(len(O)-1, 0, -1):
        path.append(psi[i][path[-1]])
    return [i + 1 for i in path[::-1]]

if __name__ == '__main__':
    A = np.array([[0.5, 0.2, 0.3],
                  [0.3, 0.5, 0.2],
                  [0.2, 0.3, 0.5]])
    B = np.array([[0.5, 0.5],
                  [0.4, 0.6],
                  [0.7, 0.3]])
    pi = np.array([0.2, 0.4, 0.4]).reshape((-1, 1))
    O = [0, 1, 0, 1]
    print(viterbi_algorithm(A, B, pi, O))
    # 得出答案: [3,2,2,2]

10.4

10.5

$\delta$为迭代过程中，到t时刻，t-1时刻状态节点到该状态节点所有路径中的最大概率；
$\alpha$为迭代过程中，到t时刻，t-1时刻状态节点到该状态节点所有路径的概率和。

本文地址：https://blog.csdn.net/qq_40773666/article/details/110228358