【机器学习 课后习题 系列教程】第 10 章 习题解答

习题 10.1 详解

「习题 10.1」 给定盒子和球组成的隐马尔可夫模型  ，其中

设  ，试用后向算法计算  。

「解」

【十分钟 机器学习 系列课程】讲义（74）中已详细列出应用后向算法计算   的过程。这里，我们以 Ptyhon 代码实现，并列出所有后向概率，代码如下。

import numpy as np

# 定义隐马尔可夫模型的参数
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])  # 初始状态概率向量

# 定义观测序列
O = ['Red', 'White', 'Red', 'White']  # 观测序列
T = len(O)  # 观测序列长度
N = A.shape[0]  # 状态数

# 将观测值映射为索引（红 -> 0, 白 -> 1）
obs_map = {'Red': 0, 'White': 1}
O_idx = [obs_map[o] for o in O]  # 转换为索引形式

# 后向算法
def backward_algorithm(A, B, pi, O_idx):
    T = len(O_idx)  # 观测序列长度
    N = A.shape[0]  # 状态数

    # 初始化后向概率
    beta = np.zeros((T, N))
    beta[-1, :] = 1# 时刻 T 的后向概率为 1

    # 递归计算后向概率
    for t in range(T - 2, -1, -1):  # 从 T-1 到 0
        for i in range(N):
            beta[t, i] = np.sum(A[i, :] * B[:, O_idx[t + 1]] * beta[t + 1, :])

    # 计算观测序列的概率
    P_O = np.sum(pi * B[:, O_idx[0]] * beta[0, :])
    return P_O, beta

# 计算观测序列的概率和后向概率
P_O, beta = backward_algorithm(A, B, pi, O_idx)

# 输出每个时刻的后向概率
print("Backward Probabilities")
for t in range(T):
    print(f"Time {t+1} backward probabilities : {beta[t, :]}")

# 输出观测序列的概率
print(f"\n Probability of the observation sequence:  P(O|λ) = {P_O:.6f}")

运行代码，得到结果如下。

Backward Probabilities
Time 1 backward probabilities: [0.1124620.1217370.104881]
Time 2 backward probabilities: [0.24610.23120.2577]
Time 3 backward probabilities: [0.460.510.43]
Time 4 backward probabilities: [1.1.1.]

Probability of the observation sequence:  P(O|λ) = 0.060091

所以，观测序列的概率为  。

习题 10.2 详解

「习题 10.2」  考虑盒子和球组成的隐马尔可夫模型  ，其中

设  ，用前向后向算法计算  。

「解」

编写前向算法、后向算法和状态条件概率计算的函数，输出所有的前向概率和后向概率、  和  。

import numpy as np

# 定义隐马尔可夫模型（HMM）的参数
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])  # 初始状态分布

# 定义观测序列
O = ['Red', 'White', 'Red', 'Red', 'White', 'Red', 'White', 'White']  # 观测序列
T = len(O)  # 观测序列的长度
N = A.shape[0]  # 状态数

# 将观测值映射为索引（红 -> 0, 白 -> 1）
obs_map = {'Red': 0, 'White': 1}
O_idx = [obs_map[o] for o in O]  # 将观测序列转换为索引形式

# 前向算法
def forward_algorithm(A, B, pi, O_idx):
    T = len(O_idx)  # 观测序列长度
    N = A.shape[0]  # 状态数

    # 初始化前向概率 alpha
    alpha = np.zeros((T, N))
    alpha[0, :] = pi * B[:, O_idx[0]]  # 初始时刻的前向概率

    # 递归计算前向概率
    for t in range(1, T):
        for i in range(N):
            alpha[t, i] = np.sum(alpha[t - 1, :] * A[:, i]) * B[i, O_idx[t]]

    # 计算观测序列的概率 P(O|λ)
    P_O = np.sum(alpha[-1, :])
    return P_O, alpha

# 后向算法
def backward_algorithm(A, B, pi, O_idx):
    T = len(O_idx)  # 观测序列长度
    N = A.shape[0]  # 状态数

    # 初始化后向概率
    beta = np.zeros((T, N))
    beta[-1, :] = 1# 时刻 T 的后向概率为 1

    # 递归计算后向概率
    for t in range(T - 2, -1, -1):  # 从 T-1 到 0
        for i in range(N):
            beta[t, i] = np.sum(A[i, :] * B[:, O_idx[t + 1]] * beta[t + 1, :])

    return beta

# 计算 gamma_t(i) = P(i_t = q_i | O, λ)
def compute_gamma(alpha, beta, P_O):
    gamma = (alpha * beta) / P_O
    return gamma

# 计算前向概率和后向概率
P_O, alpha = forward_algorithm(A, B, pi, O_idx)
beta = backward_algorithm(A, B, pi, O_idx)

# 输出前向概率
print("Forward Probabilities alpha_t(i):")
for t in range(T):
    print(f"Time {t + 1} forward probabilities: {alpha[t, :]}")

# 输出后向概率
print("\n Backward Probabilities beta_t(i):")
for t in range(T):
    print(f"Time {t + 1} backward probabilities: {beta[t, :]}")

# 输出观测序列的概率
print(f"\n Probability of the observation sequence P(O|λ) = {P_O:.6f}")

# 计算并输出 gamma_t(i)
gamma = compute_gamma(alpha, beta, P_O)
print("\n Conditional Probabilities gamma_t(i):")
for t in range(T):
    print(f"Time {t + 1} gamma_t(i): {gamma[t, :]}")

# 计算 P(i_4 = q_3 | O, \lambda)
P_i4_q3 = gamma[3, 2]  # 时刻 4 处于状态 q_3 的概率
print(f"\n P(i_4 = q_3 | O, λ) = {P_i4_q3:.6f}")

运行代码，得到结果如下。

Forward Probabilities:
Time 1 forward probabilities: [0.10.120.35]
Time 2 forward probabilities: [0.0780.0840.0822]
Time 3 forward probabilities: [0.040320.0264960.068124]
Time 4 forward probabilities: [0.02086680.012361920.04361112]
Time 5 forward probabilities: [0.01143210.010193920.01109573]
Time 6 forward probabilities: [0.005496690.003383730.00928834]
Time 7 forward probabilities: [0.002810560.002459520.00253453]
Time 8 forward probabilities: [0.001325020.001210630.00094105]

Backward Probabilities:
Time 1 backward probabilities: [0.006325690.006847060.00577855]
Time 2 backward probabilities: [0.014829640.012272140.01568294]
Time 3 backward probabilities: [0.025564420.023434480.02678985]
Time 4 backward probabilities: [0.045865310.052809090.04280618]
Time 5 backward probabilities: [0.1055210.1008830.111934]
Time 6 backward probabilities: [0.18610.24150.1762]
Time 7 backward probabilities: [0.430.510.4 ]
Time 8 backward probabilities: [1.1.1.]

Probability of the observation sequence P(O|λ) = 0.003477

P(i_4 = q_3 | O, λ) = 0.536952

所以，观测序列的概率为  。

习题 10.3 详解

「习题 10.3」 在习题 10.1 中，试用维特比算法求最优路径  。

「解」

【十分钟 机器学习 系列课程】讲义（78）中已详细列出应用维特比算法计算最优路径的过程。这里，我们以 Ptyhon 代码实现，并输出所有的   和  ，代码如下。

import numpy as np

# 定义隐马尔可夫模型的参数
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])  # 初始状态分布

# 定义观测序列
O = ['Red', 'White', 'Red', 'White']  # 观测序列
T = len(O)  # 观测序列长度
N = A.shape[0]  # 状态数

# 将观测值映射为索引（红 -> 0, 白 -> 1）
obs_map = {'Red': 0, 'White': 1}
O_idx = [obs_map[o] for o in O]  # 转换为索引形式

# 维特比算法
def viterbi_algorithm(A, B, pi, O_idx):
    T = len(O_idx)  # 观测序列长度
    N = A.shape[0]  # 状态数

    # 初始化 delta 和 Phi
    delta = np.zeros((T, N))  # delta_t(i) 存储时刻 t 处于状态 i 的最大概率
    Phi = np.zeros((T, N), dtype=int)  # Phi_t(i) 存储时刻 t 处于状态 i 的最优前驱状态

    # (1) 初始化
    delta[0, :] = pi * B[:, O_idx[0]]  # 初始时刻的 delta
    Phi[0, :] = 0# 初始时刻没有前驱状态，设为 0

    # (2) 递推
    for t in range(1, T):
        for i in range(N):
            # 计算 delta_t(i)
            delta[t, i] = np.max(delta[t - 1, :] * A[:, i]) * B[i, O_idx[t]]
            # 记录最优前驱状态
            Phi[t, i] = np.argmax(delta[t - 1, :] * A[:, i])

    # (3) 终止
    P_star = np.max(delta[-1, :])  # 最优路径的概率
    i_T_star = np.argmax(delta[-1, :])  # 最优路径的最终状态

    # (4) 最优路径回溯
    I_star = np.zeros(T, dtype=int)  # 存储最优路径
    I_star[-1] = i_T_star  # 最终状态
    for t in range(T - 2, -1, -1):
        I_star[t] = Phi[t + 1, I_star[t + 1]]  # 根据 phi 回溯前驱状态

    return delta, Phi, I_star, P_star

# 运行维特比算法
delta, Phi, I_star, P_star = viterbi_algorithm(A, B, pi, O_idx)

# 输出 delta_t(i)
print(" Delta values delta_t(i):")
for t in range(T):
    print(f"Time {t + 1} delta_{t + 1}(i): {delta[t, :]}")

# 输出 Phi_t(i)
print("\n Phi values Phi_t(i):")
for t in range(T):
    print(f"Time {t + 1} Phi_{t + 1}(i): {Phi[t, :]}")

# 输出最优路径
print("\n Optimal path I_star:")
print(I_star + 1) 

# 输出最优路径的概率
print(f"\n Probability of the optimal path P_star: {P_star:.6f}")

运行代码，得到结果如下。

Delta values delta_t(i):
Time 1 delta_1(i): [0.10.160.28]
Time 2 delta_2(i): [0.0280.05040.042 ]
Time 3 delta_3(i): [0.007560.010080.0147 ]
Time 4 delta_4(i): [0.001890.0030240.002205]

Phi values Phi_t(i):
Time 1 Phi_1(i): [000]
Time 2 Phi_2(i): [222]
Time 3 Phi_3(i): [112]
Time 4 Phi_4(i): [012]

Optimal path I_star:
[3222]

Probability of the optimal path: 0.003024

所以，最优路径为  。

习题 10.4 详解

「习题 10.4」试用前向概率和后向概率推导

「解」

根据全概率公式，可以将   分解

这意味着，任取一个时刻  ，都可以根据前向概率、后向概率、状态转移概率矩阵和观测概率矩阵计算观测序列的概率。

习题 10.5 详解

「习题 10.5」 比较维特比算法中变量   的计算和前向算法中变量   的计算的主要区别。

「解」 我们主要从定义以及运算出发进行比较。

(1) 定义公式和所代表的含义不同：

• 维特比算法中的   定义为

递推公式为

• 前向算法中的   定义为

递推公式为

虽然两者在初始时刻的值是相同的，但是两者的定义和递推公式明显不同。  表示在时刻   处于状   的所有可能路径中，概率最大的路径的概率值。  表示在时刻   处于状态  ，并且观测序列为   的概率。

(2) 运算符号不同：

• 因为维特比算法的目的是找到最优路径，所以    的计算采用   运算符，选择概率最大值。

• 前向算法的目的是计算观测序列的概率，所以   的计算采用   运算符，将所有路径的概率累加求和。