每日算法 — 使用java实现维特比算法：隐马尔可夫模型最优路径解码

隐马尔可夫模型（HMM）是时序数据分析的基石，广泛应用于语音识别、自然语言处理、生物信息学等领域。维特比算法（Viterbi Algorithm）以动态规划思想，在 $O(T \cdot N^2)$ 时间内找到最可能产生观测序列的隐藏状态路径，是HMM解码问题的最优解法。

问题定义

HMM由五元组 $\lambda = (S, V, A, B, \pi)$ 定义：
– $S = {s_1, …, s_N}$：隐藏状态集合
– $V = {v_1, …, v_M}$：观测符号集合
– $A = [a_{ij}]$：状态转移概率矩阵，$a_{ij} = P(q_{t+1}=s_j \mid q_t=s_i)$
– $B = [b_j(k)]$：观测概率矩阵，$b_j(k) = P(o_t=v_k \mid q_t=s_j)$
– $\pi = [\pi_i]$：初始状态概率分布

解码问题：给定模型 $\lambda$ 和观测序列 $O = (o_1, o_2, …, o_T)$，求最可能的隐藏状态序列 $Q^* = \arg\max_Q P(Q \mid O, \lambda)$。

维特比动态规划

定义 $\delta_t(i)$ 为时刻 $t$ 到达状态 $s_i$ 的所有路径中的最大概率：

$$
\delta_t(i) = \max_{q_1…q_{t-1}} P(q_1…q_{t-1}, q_t=s_i, o_1…o_t \mid \lambda)
$$

递推公式：

$$
\delta_t(j) = \max_{1 \leq i \leq N} [\delta_{t-1}(i) \cdot a_{ij}] \cdot b_j(o_t)
$$

通过维护回溯指针 $\psi_t(j)$ 记录每一步的最优前驱状态，最终反向追踪得到完整路径。

Java实现

import java.util.*;

/**
 * 维特比算法：HMM最优状态序列解码
 */
public class ViterbiAlgorithm {

    /**
     * 执行维特比解码
     * @param A   转移概率矩阵 N×N
     * @param B   观测概率矩阵 N×M
     * @param pi  初始概率向量 N
     * @param obs 观测序列（符号索引数组）T
     * @return    最优隐藏状态索引序列
     */
    public static int[] decode(double[][] A, double[][] B, double[] pi, int[] obs) {
        int N = A.length;      // 状态数
        int T = obs.length;    // 观测序列长度

        // delta[t][i]: 时刻t到达状态i的最大概率（取对数防下溢）
        double[][] delta = new double[T][N];
        // psi[t][i]: 时刻t到达状态i的最优前驱状态
        int[][] psi = new int[T][N];

        // 初始化 t=0
        for (int i = 0; i < N; i++) {
            delta[0][i] = Math.log(pi[i]) + Math.log(B[i][obs[0]]);
            psi[0][i] = -1;
        }

        // 递推 t=1..T-1
        for (int t = 1; t < T; t++) {
            for (int j = 0; j < N; j++) {
                double maxProb = Double.NEGATIVE_INFINITY;
                int bestPrev = -1;
                for (int i = 0; i < N; i++) {
                    double prob = delta[t - 1][i] + Math.log(A[i][j]) + Math.log(B[j][obs[t]]);
                    if (prob > maxProb) {
                        maxProb = prob;
                        bestPrev = i;
                    }
                }
                delta[t][j] = maxProb;
                psi[t][j] = bestPrev;
            }
        }

        // 终止：找到最终时刻概率最大的状态
        double maxFinalProb = Double.NEGATIVE_INFINITY;
        int lastState = -1;
        for (int i = 0; i < N; i++) {
            if (delta[T - 1][i] > maxFinalProb) {
                maxFinalProb = delta[T - 1][i];
                lastState = i;
            }
        }

        // 回溯得到最优路径
        int[] path = new int[T];
        path[T - 1] = lastState;
        for (int t = T - 2; t >= 0; t--) {
            path[t] = psi[t + 1][path[t + 1]];
        }

        return path;
    }

    /**
     * 前向算法：计算观测序列的生成概率 P(O|λ)
     * 用于模型评估与训练（Baum-Welch）
     */
    public static double forward(double[][] A, double[][] B, double[] pi, int[] obs) {
        int N = A.length, T = obs.length;
        double[][] alpha = new double[T][N];

        // 初始化
        for (int i = 0; i < N; i++) {
            alpha[0][i] = pi[i] * B[i][obs[0]];
        }

        // 递推
        for (int t = 1; t < T; t++) {
            for (int j = 0; j < N; j++) {
                double sum = 0;
                for (int i = 0; i < N; i++) {
                    sum += alpha[t - 1][i] * A[i][j];
                }
                alpha[t][j] = sum * B[j][obs[t]];
            }
        }

        // 终止
        double prob = 0;
        for (int i = 0; i < N; i++) {
            prob += alpha[T - 1][i];
        }
        return prob;
    }

    public static void main(String[] args) {
        // 示例：天气预测模型
        // 状态: 0=晴天, 1=雨天
        // 观测: 0=干燥, 1=潮湿, 2=湿润
        double[][] A = {
            {0.7, 0.3},  // 晴->晴 0.7, 晴->雨 0.3
            {0.4, 0.6}   // 雨->晴 0.4, 雨->雨 0.6
        };
        double[][] B = {
            {0.6, 0.3, 0.1},  // 晴天: 干燥0.6 潮湿0.3 湿润0.1
            {0.1, 0.4, 0.5}   // 雨天: 干燥0.1 潮湿0.4 湿润0.5
        };
        double[] pi = {0.6, 0.4};  // 初始: 晴天0.6 雨天0.4

        // 观测序列: 干燥, 潮湿, 湿润, 湿润
        int[] observation = {0, 1, 2, 2};
        String[] states = {"晴天", "雨天"};
        String[] obsNames = {"干燥", "潮湿", "湿润"};

        int[] bestPath = decode(A, B, pi, observation);

        System.out.print("观测序列: ");
        for (int o : observation) System.out.print(obsNames[o] + " ");
        System.out.println();

        System.out.print("最优状态: ");
        for (int s : bestPath) System.out.print(states[s] + " ");
        System.out.println();

        double prob = forward(A, B, pi, observation);
        System.out.printf("观测序列概率 P(O|λ) = %.6f%n", prob);
    }
}

复杂度分析

对于 $N=5$ 个状态、$T=100$ 的观测序列，维特比仅需约 $2500$ 次运算，而暴力枚举需要 $5^{100}$，差距达 $10^{68}$ 倍。

应用场景

1. 语音识别：将声学特征序列映射为最可能的音素/单词序列
2. 词性标注：为句子中的每个词选择最可能的词性标签
3. 生物信息学：DNA序列的基因预测与蛋白质二级结构分析
4. 通信系统：卷积码的最优译码（卷积码本质上是HMM）

维特比算法展示了动态规划的精髓：通过状态压缩消除重叠子问题，将指数级复杂度转化为多项式级，是算法设计中”以空间换时间”的经典范例。