寻找最佳词语序列是一个重大的计算难题。对于给定的音频输入,可能的句子数量庞大到惊人。解码器计算每个可能句子的概率的暴力尝试法根本不可行。对于一个包含50,000词的词汇表,即使一个简短的10词句子,也有$50,000^{10}$种潜在组合。我们急需一种效率更高的办法,在这个庞大的搜索空间中找到出路。这正是维特比算法发挥作用之处。它是一种高效算法,属于被称为动态规划的一类方法。动态规划的核心思想是将一个复杂问题分解成一系列简单的子问题,每个子问题只解决一次并存储其解决方案。维特比算法运用此原则来找到模型中最可能的状态序列,在我们的情境中,这对应于最可能的词语序列。穿越时间的路径想象解码过程是在一个网格中寻找最佳路径,这个网格通常被称为篱笆图或格子图。网格中的每一列代表一个时间点(对应于一个音频帧或片段),每一列中的每个节点代表在该时间点可能说出的词语(或音素)。该算法每次一个时间步地从左到右在篱笆图中移动。在每一步,它计算到达每个可能词语的最可能路径。维特比算法的重要发现是:为了找到到达当前时间步某个词语的最佳路径,你只需要知道到达所有前一时间步词语的最佳路径。你不需要记住每条可能路径的完整历史。通过扩展前一步的最佳路径并加入新的成本(基于声学和语言模型概率),算法找到新的最佳路径集合。然后它丢弃所有其他不太可能的路径。这种持续修剪不可能路径的做法,正是该算法如此高效的原因。示例说明假设在听到一些音频后,解码器试图在两个部分句子之间做出选择:“recognize speech”和“wreck a nice beach”。声学模型可能会发现这两个短语听起来相似。然而,语言模型知道“recognize speech”比“wreck a nice speech”是更常见的短语。维特比算法将按以下步骤进行:时间步 1: 它考虑音频的第一部分。声学模型对“recognize”和“wreck a nice”都给出高分。算法将两者都保留为可能性。时间步 2: 它分析下一段音频,听起来像“speech”。解码器现在评估四条潜在路径:recognize -> speechrecognize -> beachwreck a nice -> speechwreck a nice -> beach计算与修剪: 对于这四条路径中的每一条,解码器通过结合声学分数(音频与词语的匹配程度)和语言模型分数(词语序列的可能性)来计算一个总分数。P(音频 | "recognize speech") * P("recognize speech") 很可能得分很高。P(音频 | "wreck a nice beach") * P("wreck a nice beach") 也将有相当高的分数。然而,像recognize -> beach和wreck a nice -> speech这样的路径,其语言模型概率会非常低。算法会为它们分配低分,并有效地将它们从考虑中移除。回溯: 到达音频末尾后,算法确定总体概率最高的路径的最后一个词。从那里,它通过保存的指针向后追溯,在每个时间步重建唯一的最佳词语序列。下图显示了此过程。在每个时间步,算法扩展前一步幸存下来的路径。不太可能的路径(虚线)被丢弃,只保留到达每个词语的最可能路径。通过从末尾回溯找到最终的最佳路径。digraph G { rankdir=LR; splines=true; node [shape=circle, style=filled, fontname="sans-serif", fixedsize=true, width=1.1, height=1.1]; edge [fontname="sans-serif", fontsize=10]; graph [fontname="sans-serif", label="维特比路径搜索", labelloc=t, fontsize=14]; subgraph cluster_0 { label="开始"; style=invis; start [label="开始", shape=plaintext, fontsize=12]; } subgraph cluster_1 { label="时间步1的假设"; bgcolor="#e9ecef"; style=filled; rec [label="recognize", fillcolor="#a5d8ff"]; wreck [label="wreck a nice", fillcolor="#a5d8ff"]; } subgraph cluster_2 { label="时间步2的假设"; bgcolor="#e9ecef"; style=filled; speech [label="speech", fillcolor="#a5d8ff"]; beach [label="beach", fillcolor="#a5d8ff"]; } subgraph cluster_3 { label="结束"; style=invis; end_node [label="结束", shape=plaintext, fontsize=12]; } start -> rec [label=" P(rec|start)"]; start -> wreck [label=" P(wreck|start)"]; rec -> speech [label=" P(speech|rec)", penwidth=2.5, color="#fd7e14"]; rec -> beach [label=" P(beach|rec)", style=dashed, color="#adb5bd"]; wreck -> speech [label=" P(speech|wreck)", style=dashed, color="#adb5bd"]; wreck -> beach [label=" P(beach|wreck)", penwidth=2.5, color="#fd7e14"]; speech -> end_node [penwidth=2.5, color="#fd7e14"]; beach -> end_node [style=dashed, color="#adb5bd"]; {rank=same; start;} {rank=same; rec; wreck;} {rank=same; speech; beach;} {rank=same; end_node;} }一个显示维特比搜索的简化格子图。算法根据结合声学和语言模型的分数评估转换。不太可能的路径被修剪(灰色虚线),而最可能路径(橙色)则通过从得分最高的最终状态回溯构建。其工作原理维特比算法保证能找到穿过篱笆图的唯一最佳路径。它这样做而无需评估每一个可能性。通过在每个时间步做出局部最优决策(即只保留到达每个词语的最佳路径),它达到了全局最优解。这种将一个难以处理的问题转化为可管理的问题的做法,是现代ASR系统如何快速准确地生成转录的根本方法。