解题思路

题目要求对每条观测序列，求：

1. 最优隐藏状态序列
2. 该最优路径对应的对数概率 $log P(q̂, o)$

这正是经典的$Viterbi$ 算法问题。

题目内容

请在仅使用 $numpy$ 的前提下，实现离散型隐马尔可夫模型 ($HMM$) 的 $Viterbi$ 动态规划。

给定：

• 初始分布 $\pi \in \mathbb{R}^{N}$

• 状态转移矩阵 $A \in \mathbb{R}^{N \times N}$

• 观测概率矩阵 $B \in \mathbb{R}^{N \times M}$ (列索引=观测符号)

• 多条离散观测序列 $\left\{\mathbf{o}^{(s)}\right\}_{s=1}^{S}$ ，符号取值 $0...M-1$

请为每条序列计算

1.最优隐藏状态序列 $\hat{\mathbf{q}}^{(s)}=\left(q_{1}, \ldots, q_{T}\right)$

2.该序列的对数概率 $\log P(\hat{\mathbf{q}}, \mathbf{o})$

实现要求

• 对数域计算，避免下溢：所有乘法用 $log+$，求和用 $logsumexp$ 或 $np.logaddexp.reduce$

• 只需前向传递 $+$ 回溯，无需 $forward/backward$ 或 $EM$ 训练

• 所有浮点以 $float64$ 计算；输出对数概率保留 $6$ 位小数(四舍五入)

输入描述

单行 JSON:

{

"pi":[0.6,0.4],                        //长度N

"A": [[0.7,0.3],[0.4,0.6]],         // N×N

"B": [[0.5,0.4,0.1],[0.1,0.3,0.6]], // N×M

"obs":[[0.0],[2.2]...]          //S条序列，符号整数

}

• $N≤4,M≤4$，序列长度 $T≤6,S≤10$

• 所有概率矩阵行各自已归一化；不必检验

输出描述

仅一行 JSON:

{

"paths":[[q11,q12,...],[q21,...],...],         //每条序列最优路径

"logp":[-2.253795,-2.448768,...]         //对应对数概率，使用 round(x,6) 保留小数位

}

次序须与输入 $obs$ 保持一致。

补充说明

为确保通过测试用例，仅允许使用 $numpy$ 。

样例1

输入

{"pi:[0.6,0.4],"A":[[0.7,0.3],[0.4,0.6]],"B":[[0.5,0.4,0.1],[0.1,0.3,0.6]l,"obs":[[0,0]])

输出

{"paths": [[0, 0]], "logp": [-2.253795]}