别再死记公式了用‘朋友推特猜天气’这个例子5分钟搞懂维特比算法HMM实战想象你有个喜欢发推文但从不提天气的朋友。周一他说去爬山周二发宅家看电影周三写咖啡馆赶工。你能通过这些活动倒推他所在地的天气吗这就是隐马尔可夫模型HMM的经典问题——通过可见的活动序列推断背后隐藏的天气状态。而维特比算法就是解决这个问题的金钥匙。传统教材总爱从状态转移矩阵和发射概率讲起让人还没开始就想放弃。今天我们用完全不同的视角把算法过程变成一场侦探游戏你会看到维特比如何像老练的探长一样通过排除不可能选项最终锁定最可能的天气序列。1. 从生活场景理解HMM三要素HMM的核心就像在玩一个双重猜谜游戏天气影响活动活动反映天气。要玩好这个游戏需要三个关键道具状态集合本例中的天气只有两种可能晴天Sunny或雨天Rainy观测集合朋友可能进行的活动爬山Hike、看电影Movie、喝咖啡Coffee概率矩阵转移概率今天天气如何影响明天天气发射概率某种天气下进行某项活动的可能性用表格表示更直观天气转移概率今天→明天当前天气明天晴天明天雨天晴天70%30%雨天40%60%活动发射概率天气爬山看电影喝咖啡晴天60%20%20%雨天10%50%40%注意这些概率需要提前定义实际应用中可通过历史数据统计得到2. 暴力枚举法为什么行不通最直接的方法是列出所有可能的天气序列计算每条路径的概率然后选最大的。对于3天的观察晴→晴→晴晴→晴→雨晴→雨→晴晴→雨→雨雨→晴→晴雨→晴→雨雨→雨→晴雨→雨→雨看似只有8种可能但天数增加到N时路径数会指数爆炸2^N。当N30路径数超过10亿条这就是著名的维度灾难。维特比算法的精妙之处在于它发现不需要计算所有路径因为在每一步只需要记住当前最优的选择。3. 维特比算法的侦探思维让我们用侦探破案的视角来看算法流程。已知朋友三天的活动序列是爬山→看电影→喝咖啡。3.1 第一天初始线索假设我们知道朋友所在地第一天是晴天的概率60%雨天40%初始概率。观察到爬山活动晴天且爬山的联合概率0.6(初始) × 0.6(发射) 0.36雨天且爬山的联合概率0.4 × 0.1 0.04此时保留两条路径路径A晴天概率0.36路径B雨天概率0.04关键点已经可以排除那些概率更低的路径比如雨天且爬山的可能性只有4%3.2 第二天排除法破案第二天活动是看电影。对于每条现有路径考虑天气转移从路径A晴出发晴→晴0.36 × 0.7 × 0.2 0.0504晴→雨0.36 × 0.3 × 0.5 0.054从路径B雨出发雨→晴0.04 × 0.4 × 0.2 0.0032雨→雨0.04 × 0.6 × 0.5 0.012此时保留四条路径中概率最高的两条晴→雨0.054晴→晴0.0504另外两条路径雨→晴和雨→雨因为概率过低被剪枝。这就是维特比算法的核心——每一步只保留局部最优路径。3.3 第三天锁定真凶第三天活动是喝咖啡。继续扩展保留的两条路径从晴→雨出发雨→晴0.054 × 0.4 × 0.2 0.00432雨→雨0.054 × 0.6 × 0.4 0.01296从晴→晴出发晴→晴0.0504 × 0.7 × 0.2 0.007056晴→雨0.0504 × 0.3 × 0.4 0.006048最终四条路径中晴→雨→雨以0.01296的概率胜出。这就是最可能的天气序列4. 为什么不是每一步选最大概率常见误区是认为每天选概率最大的天气组合起来就是最佳路径。让我们验证第一天晴天0.36 雨天0.04→选晴第二天比较晴→晴0.0504和晴→雨0.054→选雨第三天比较雨→晴0.00432和雨→雨0.01296→选雨这样得到的序列也是晴→雨→雨看似与维特比结果相同。但这只是巧合看这个反例假设第三天活动是看电影雨→晴0.054 × 0.4 × 0.2 0.00432雨→雨0.054 × 0.6 × 0.5 0.0162此时维特比路径是晴→雨→雨0.0162。但按每天最优第一天晴第二天晴→雨0.054 晴→晴0.0504→选雨第三天雨→晴0.00432 vs 雨→雨0.0162→选雨依然得到相同结果。再调整参数让雨→晴的转移概率提高到80%晴→晴降到50%维特比路径晴→雨→晴0.6 × 0.6 × 0.3 × 0.8 × 0.2 0.01728晴→雨→雨0.6 × 0.6 × 0.3 × 0.2 × 0.5 0.0108此时最优路径是晴→雨→晴。但每天最优法第一天晴第二天晴→雨因为0.3 调整后的晴→晴概率第三天雨→晴因为0.8 0.2虽然这次结果一致但通过数学证明可以知道维特比算法找到的是全局最优路径而贪心算法每天最优只能保证局部最优两者不等价。5. 算法实现的关键技巧用Python实现时有三个优化点值得注意def viterbi(obs, states, start_p, trans_p, emit_p): V [{}] # 动态规划表 path {} # 路径记录 # 初始化 for y in states: V[0][y] start_p[y] * emit_p[y][obs[0]] path[y] [y] # 递推 for t in range(1, len(obs)): V.append({}) newpath {} for y in states: # 找出概率最大的前驱状态 (prob, state) max( (V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states ) V[t][y] prob newpath[y] path[state] [y] path newpath # 回溯 (prob, state) max((V[len(obs) - 1][y], y) for y in states) return (prob, path[state])提示实际应用中建议使用对数概率避免连续乘法导致数值下溢6. 算法在真实世界的应用场景维特比算法远不止于猜天气游戏它在这些领域大显身手自然语言处理词性标注通过词语序列推断词性标记序列命名实体识别判断文本中的人名、地名等生物信息学DNA序列分析蛋白质结构预测通信工程信号解码错误校正金融领域市场状态预测交易模式识别在语音识别中当系统接收到声学信号序列时需要找到最可能的单词序列——这正是HMM维特比的经典组合能解决的问题。