10.1
本题考查概率计算的前向或后向算法:
前向算法：
α
t
+
1
(
i
)
=
[
∑
j
=
1
N
α
t
(
j
)
∗
a
j
i
]
∗
b
i
(
O
t
+
1
)
\alpha_{t+1}(i) = [\sum_{j=1}^{N} \alpha_{t}(j)*aji]*b_{i}(O_{t+1})
αt+1(i)=[j=1∑Nαt(j)∗aji]∗bi(Ot+1)
后向算法：
β
t
(
i
)
=
∑
j
=
1
N
a
i
j
b
j
(
O
t
+
1
)
β
t
+
1
(
j
)
\beta_t(i) = \sum_{j=1}^{N}a_{ij}b_{j}(O_{t+1})\beta_{t+1}(j)
βt(i)=j=1∑Naijbj(Ot+1)β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
q_i
qi的概率为：
γ
t
(
i
)
=
P
(
i
t
=
q
i
,
O
∣
λ
)
=
α
t
(
i
)
∗
β
t
(
i
)
∑
i
=
1
N
α
t
(
i
)
∗
β
t
(
i
)
\gamma_t(i)=P(i_t=q_i,O | \lambda) = \frac{\alpha_t(i)*\beta_t(i)}{\sum_{i=1}^{N}{\alpha_t(i)*\beta_t(i)}}
γt(i)=P(it=qi,O∣λ)=∑i=1Nαt(i)∗βt(i)αt(i)∗β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
