一种快速的语音识别词图生成算法

NCMMSC’2009，8月14－16日，新疆乌鲁木齐一种快速的语音识别词图生成算法*李伟，吴及，王智国(清华大学电子系，北京100084)文摘：作为语音识别结果的表现形式之一，词图（Lattice）以其紧凑的结构被广泛应用于大词表连续语音识别、语音检索等系统中。词图的高效生成算法同时成为了语音识别领域一个研究课题。本文提出了一种基于词格的词图生成算法(Trellis-BasedLattice-Generatingalgorithm：TBLD)：该算法在正向Viterbi解码生成的词格（Trellis）基础上，进行反向A*解码生成词图。实验结果表明，与经典的解码器HDecode相比，在相同识别率下，TBLD算法速度快且词图质量高。关键词：语音识别；词图；解码；正向-反向算法中图分类号：TN912.34*基金项目：十一五863项目（2006AA01Z149）作者简介：李伟（1981-），男（汉），北京，博士研究生。通讯联系人：吴及，副教授，E-mail：[e-mail]词图（Lattice）是近年来较常用的一种语音识别结果表现形式。它将解码的多候选结果在一个有向无环图上加以表示，在保留多候选信息的同时节约了存储空间。一些图论算法可以被应用到词图中——为识别结果的后处理（如生成ConfusionNet-work等）提供了高效的理论依据。词图的产生与语音信号的解码过程是紧密联系的。词图的生成方法已经有相关的研究。文献[1]提出了一种基于“TokenPassing”的词图生成算法。该算法对基本的Viterbi解码方法进行扩展，从而一遍解码（onepass）后便可生成词图解码结果。该算法及相应的语音识别工具（HDecode）被广泛应用在语音识别领域。这种算法存在的问题是速度较慢。不适合实时率要求较高的应用环境。另一方面，提高解码速度的研究也有了很多成果。[2]提出了一种基于“正向-反向”的两遍解码思路。它通过减少每遍解码的工作量，来减少解码过程的整体复杂度。文献[3]提出了一种基于“正向-反向”的N候选（N-Best）生成算法Tree-TrellisSearch。该算法将正向Viterbi与反向A*算法相结合，能够快速而精确地得到语音识别的N候选结果。正向Viterbi解码后，生成词格（Trellis）结构的识别结果。作为一种中间的识别结果，词格将识别信息保存在“识别单元*帧”的二维表格中：表格上的每个结点表征了相应的识别单元结尾。同时由于剪枝的存在，很多识别结果没有路径到达某一帧后就中断了。相比之下，词图则是一种更加紧凑的结构。它以弧表示词，以结点表示词的连接关系。而每个词都属于一个从开始结点到结束结点的路径。在反向解码中，基于A*的反向扩展算法被引入：词格上的每个结点被反向Viterbi解码（反向扩展）。于是，词格上的每个结点将生成一系列的入弧（IsolatedWordExtensionArc）。每条入弧记录了相应的词ID及得分信息。以入弧为分割，一条完整的全路径被划分成三部分：被扩展的弧与该弧的后续路径的得分由反向Viterbi得到；而被扩展出的结点到开始结点的得分由生成词格时的结点得分作为A*启发得分。路径的总得分可以由三部分相加得到。为了保证昀优的N个候选—即N条路径—被有效选出，引入了优先级队列。跟据路径得分的高低，待扩展结点被依次放入优先级队列中。该队列头部的结点，优先进行扩展。从后向前的重复上述过程，当优先级队列中取出的结点位于开始帧时，便找到了昀优候选路径。N个昀优候选路径都找到后，解码过程结束。这种方法被证明是一种高效的N-Best生成算法。但是，N-Best是识别多候选的线性表现形式，与Lattice即图的多候选表现形式不同。该算法不能被直接应用于生成词图解码结果。为了生成词图结果，本文在[3]的基础上：根据词图的特点，在反向解码算法中对优先级队列、跨词单元的处理等方面进行了修改，同时引入了剪枝策略，形成了一个快速的基于词格的词图生成算法（Trellis-BasedLattice-Generatingalgorithm：TBLD）。TBLD算法与经典的基于tokenpassing的词图生成算法（HDecode）相比，具有解码复杂度15低，生成词图效果好等优点。本文安排如下：第一节概述了TBLD算法；第二节详细描述了算法中的反向解码；TBLD算法与HDecode的对比实验在第三节；昀后是本文小结。1算法概述1.1Tree-TrellisSearch算法的修改同样是多候选的语音识别结果，N候选与词图在识别目标与表现形式上有所区别，正是这样的区别使得N候选的Tree-TrellisSearch生成算法不能被直接应用在词图的生成过程中。首先，N候选生成算法中一个结点可以在不同的路径中存在：一个结点可能被进行多次扩展。而词图的紧凑结构决定了扩展过程中每个结点只能被扩展一次。为了有效解决这个问题，原始算法中的优先级队列的优先级准则需要调整：将原始的“以得分大小为排列方式”修改为“以结点所在位置为排列方式”。处于后面位置的结点先进行扩展。而一旦新扩展生成的结点已经包含在队列中，则需要进行结点的合并。其次，同样是词格结果后处理，对于N候选来说，词格的整个搜索空间不是昀重要的：它只关心前N个昀优结果。反之，词图要求通过紧凑的表示形式包含更多的识别信息。因此，原始算法的结束条件需要修改为“优先级队列为空时结束”。1.2跨词单元的解码近似在进行词图的反向生成过程中，一个新产生的问题就是“跨词单元的解码近似”问题。典型的跨词单元包括跨词Tri-phone等。N候选生成时，每一个将要扩展的结点其后继词都是唯一的，这样反向Viterbi解码时待扩展词的结束声学模型可以被唯一确定。如图1所示。而生成词图的过程中，由于存在结点的合并，在对一个结点进行扩展时，其后继词可以有多种可能。此时跨词单元的使用将存在限制。如图2所示。图1：N候选扩展时的反向Viterbi模型确定。设要扩展的词为ExtWord，其后继词为PostWord。使用跨词Tri-phone时，由于PostWord确定，因此ExtWord昀后的声学模型也可以确定为“?-n1+p1”的形式。图2：词图扩展时的反向Viterbi模型具有不确定性。设要扩展的词为ExtWord，其后继词可能有多种（PostWord1与PostWord2）。如果二者的开始声学模型（p1与p4）不相同，则ExtWord的结尾声学模型也不能唯一确定可以有很多的方法来解决这个问题。本文使用一个估计得分来代替待扩展词结尾的声学模型得分进行近似。1.3剪枝与结点的合并在解码过程中，对一个结点的反向扩展往往产生多个新的待扩展结点。而为了保证解码过程的效率，对新产生的结点要进行剪枝操作。目前，本解码器采用两种剪枝策略：全局剪枝与昀大扩展结点数目剪枝。在对一个结点扩展完毕后，将生成一系列新结点。每个结点对应一个全局路径得分。如果某个结点的全局路径得分与昀优路径得分之间相差一个阈值，则该结点被剪枝——这就是全局剪枝策略。而经过全局剪枝后，如果新生成的结点数目还是大于一个阈值，处于后面的结点要被剪枝——这就是昀大扩展结点数目剪枝.而剪枝之后的结点将被加入到优先级队列中。在结点的加入过程中，一旦发现优先级队列中已经存在ID与时间信息相同的结点，新的结点要与旧的结点进行合并——成为一个结点。1.4Silence弧的去除静音（Silence）作为一种声学现象体现在语音识别结果中。在一些情况下，生成的结果中不需要静音段。此时，可以在生成词图的同时去除中间的静音段。具体算法如下：z当对一个静音段（Sil）的终止结点X反向扩展结束后，可以得到一系列新的待扩展结点——设为I={i1,i2,iM}；z通过图的路径后向查询，可以找到X的所有直接后继结点——设为O={o1,o2,…,oN}；z将O与I两两连接，形成一系列新的弧；z从词图中删除X以及X的所有出弧、入弧。图3显示了去除静音弧前后词图的结构变化。16图3：去除静音弧的前后变化。在对静音段的结尾结点X进行反向扩展后，通过图的拓扑结构可以得到X的直接前趋集合I与直接后继集合O。将I与O中的点两两连接后去除X以得到新的词图结构。2反向算法流程整体的词图算法分为“正向解码，生成Trellis”的部分与“反向解码，生成词图”的部分。第一步可以采用经典的TokenPassing等方式实现，本文不再赘述。对于后半部分，这里采用一个有限状态机的方式实现。2.1主框架流程初始化（初始状态）While(TRUE){If(优先级队列只有一个结点&&该结点为起始结点)break结点的反向扩展（扩展状态）结点的剪枝与合并（剪枝与合并状态）}后期处理（结束状态）2.2初始化（初始状态）流程建立优先级队列Q将Trellis中处于结尾帧的候选放入Q中2.3结点的反向扩展（扩展状态）流程从Q中取出头结点X对X进行反向Viterbi扩展If(X是Silence结点&&进行去除静音弧的工作)去除静音弧将产生的结点加入临时缓冲区TempBuffer2.4结点的剪枝与合并（剪枝与合并状态）流程For(TempBuffer中每一个结点X){计算X所在路径的得分SIf(使用全局剪枝&&S昀大得分-全局剪枝阈值)从TempBuffer中删除X;}If(使用昀大扩展结点数目剪枝&&TempBuffer中结点数目剪枝门限N)保留TempBuffer中昀优的N个结点For(TempBuffer中每一个结点X){For(Q中每一个结点Y){If(Y.ID=X.ID&&Y.位置=X.位置)合并X/YElse将X插入Q}}2.5后期处理（结束状态）流程取出Q中的起始结点以该结点为根进行遍历：得到昀终结果3实验3.1实验设置本文使用2003/2004年863LVCSR测试评估数据作为系统的性能测试集合。2003年数据（以下简称CSLEC03）包括120句话，由6男6女朗读。2004年数据（以下简称CSLEC04）包括200句话，由10男10女朗读。两份数据均为16K采样的PCM，使用“39维MFCC+4维Pitch”进行参数提取。为了与一些成熟的语音识别系统进行比较，这里采用了HTK3.4中的HDecode作为对比系统。在模型方面，两个解码器采用Bigram语言模型（Bi-gram约501万条），使用8000个状态，20Mixture-GMM的HMM进行声学建模。3.2最优路径准确性通过对两种不同类型的解码器解码结果的后处理，从中得到昀优候选的结果。相应的准确度结果见表1。可以看出，二者的性能是相近的。表1：TBLD与HDecode的昀优路径准确性分析1-BestAccuracy(%)TBLDHDecodeCSLEC0363.2860.64CSLEC0458.6857.783.3覆盖度分析词图的另一个重要评价指标是其覆盖度（OracleCharacterErrorRate）：在词图中找到一条与标注文本昀接近的路径，看该路径的错误程度。图4展示了不同密度下两种解码器的覆盖度性能。从图中可以看出，TBLD与HDecode具有类似的覆盖度性能。图4：不同密度下两种解码器的覆盖度性能：将两个测试集合结果平均后得到。从图中可以看出，两种解码器生成的词17图覆盖度类似。3.4解码时间复杂度分析由于解码器的结构相对复杂：进行精确的时间复杂度分析较困难。这里采用同样的计算机（Intel3GHzCPU，内存1G）分别运行解码器程序。观察其实际运行速度。图5展示了测试结果。从图中可以看出，TBLD的速度要明显优于HDecode。图5:不同密度下两种解码器的速度性能：将两个测试集合结果平均后得到。从图中可以看出，TBLD的速度要明显快于HDecode。且随着生成词图密度的增加，TBLD受到的影响要远远小于HDecode3.5空间复杂度分析空间复杂度主要体现在解码过程所消耗的内存与解码完毕后词图占用的空间上。在这里，我们重点关心“解码完毕后词图占用的空间”这个问题。而这里通过对生成词图的结点数目与弧数目进行统计来反映词图占