别再死记公式了！用‘朋友推特猜天气’这个例子，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）。当N=30，路径数超过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+维特比的经典组合能解决的问题。
