基于加权有限状态机的动态匹配词图生成算法

第36卷第1期电子与信息学报Vol.36No.12014年1月JournalofElectronics&InformationTechnologyJan.2014基于加权有限状态机的动态匹配词图生成算法郭宇弘*黎塔肖业鸣潘接林颜永红(中国科学院语言声学与内容理解重点实验室北京100190)摘要：由于现有的加权有限状态机(WFST)解码网络没有精确词尾标记，导致当前已有的词图生成算法不含精确的词尾时间点，或者仅是状态、音素级别的词图，无法应用到关键词检索中。该文提出在WFST静态解码器下的语音识别词图生成算法。首先从理论上分析了WFST解码音素图和词图的可转换关系，然后提出了字典的动态音素匹配方法解决了WFST网络中词尾时间点对齐的问题，最后通过令牌传递的遍历方法生成了词图。同时，考虑到计算量优化，在令牌传递过程中引入了剪枝算法，使音素图转词图的耗时不到解码耗时的3%。得到的词图，不仅可以用于语言模型重打分，由于含有精确的词尾时间点，还可以直接应用到关键词检索系统中。实验结果表明，该文的词图生成算法具有较高的计算效率；和已有动态解码器的词图相比，词图中包含更多解码信息，在大词汇连续语音识别的重打分结果和关键词检索中都能取得更好的性能。关键词：自动语音识别；加权有限状态机；词图生成；关键词检索中图分类号：TP391.42文献标识码：A文章编号：1009-5896(2014)01-0140-07DOI:10.3724/SP.J.1146.2013.00422ExactWordLatticeGenerationinWeightedFiniteStateTransducerFrameworkGuoYu-hongLiTaXiaoYe-mingPanJie-linYanYong-hong(KeyLaboratoryofSpeechAcousticsandContentUnderstanding,ChineseAcademyofSciences,Beijing100190,China)Abstract:TheexistinglatticegenerationalgorithmshavenoexactwordendtimebecausetheWeightedFiniteStateTransducer(WFST)decodingnetworkshavenowordendnode.AnalgorithmisproposedtogeneratethestandardspeechrecognitionlatticewithintheWFSTdecodingframework.Thelatticeswhichhavenoexactwordendtimecannotbeusedinthekeywordspottingsystem.Inthispaper,thetransformationrelationshipbetweenWFSTphonelatticesandstandardwordlatticeisfirstlystudied.Afterward,adynamiclexiconmatchingmethodisproposedtogetbackthewordendtime.Finally,atokenpassingmethodisproposedtotransformthephonelatticesintostandardwordlattices.Aprunestrategyisalsoproposedtoacceleratethetokenpassingprocess,whichdecreasesthetransformingtimetolessthan3%additionalcomputationtimeaboveone-passdecoding.Thelatticesgeneratedbytheproposedalgorithmcanbeusedinnotonlythelanguagemodelrescoringbutalsothekeywordspottingsystems.Theexperimentalresultsshowthattheproposedalgorithmisefficientforpracticalapplicationandthelatticesgeneratedbytheproposedalgorithmhavemoreinformationthanthelatticesgeneratedbythecomparativedynamicdecoder.Thisalgorithmhasagoodperformanceinlanguagemodelrescoringandkeywordspotting.Keywords:Automaticspeechrecognition;WeightedFiniteStateTransducer(WFST);Latticegeneration;Keywordspotting1引言作为大词表连续语音识别的核心模块，语音识2013-04-01收到，2013-07-18改回国家自然科学基金(10925419,90920302,61072124,11074275,11161140319,91120001,61271426)，中国科学院战略性先导科技专项(XDA06030100,XDA06030500)，国家863计划项目(2012AA012503)和中科院重点部署项目(KGZD-EW-103-2)资助课题*通信作者：郭宇弘[e-mail]别解码器负责利用上下文相关的声学模型、字典和语言模型等知识源把语音信号转换为文本。评价语音识别解码器性能的一项关键指标就是识别器的准确率。在非常理想的情况下，语音识别应具有非常高的识别准确率，此时仅仅选用语音识别的解码首选结果就可以使语音搜索、关键词检错等应用的准确率非常高。然而，考虑到现实应用经常出现的信道不匹配、说话人不匹配或者说话人发音不标准的第1期郭宇弘等：基于加权有限状态机的动态匹配词图生成算法141问题，导致大词表连续语音识别(LargeVocabularyContinuousSpeechRecognition,LVCSR)的首选结果在电话环境一类语音的识别错误率通常在40%左右。在这种较低准确率的情况下仅仅使用解码的首选结果往往是不够的。识别结果可以以多候选(N-Best)或者词图等形式输出，这种多候选或者词图结果保留了识别中的更多识别信息，把它们交由后处理模块能有效提高识别结果的准确性。常见的后处理技术包括：基于词图的重打分[1]、多遍解码[2]、混淆网络[3]等。和多候选结果相比，词图形式包含了更多的信息，它不仅有多个识别词序列结果，更包含了每个词、音素的声学得分、语言得分以及时间点等信息，并且它合并了多候选的冗余信息，其表示也更加高效[4]。因此，词图在语音识别后处理中得到非常广泛的应用。例如：可以从词图里面直接抽取多候选结果；另外词图本身已经具有了图的性质，在某些场合第1遍解码用比较精细的模型会带来计算量过高的问题，此时可以用简单的模型在第1遍解码时生成词图，再用精细的模型在词图上进行2遍解码或者重打分则可获得更好的效果；而在关键词检索的应用中，词图或者词图的混淆网络形式可以作为检索器的输入。因此，词图成为了语音识别中第1遍解码和后处理模块之间的桥梁。词图的生成过程是由解码器搜索解码网络，记录下搜索路径从而转化成相应的词图。解码网络是由各个知识源构成的一个搜索空间，一般来讲可以分为动态构建的解码网络和静态网络。基于动态网络的解码器，以前缀树的发音词典作为搜索网络，语言模型则通过动态查询的方式把得分引入解码过程之中，然后利用重入字典树或者字典树拷贝的方式对整个解码网络进行搜索[5]。动态网络解码器的优势在于，由于字典和语言模型是分离的，其占用内存较少，同时，由于搜索空间为一个前缀树的字典，字典里面有准确的词尾节点，这样，在进行词图生成的时候，可以准确地获取到词尾时间点。然而，动态网络解码器的最大缺点在于它的时间复杂度较高[6]，相对于静态网络解码器，它的速度较慢。对于当今的大规模的语音识别应用，往往需要更快的响应速度，因而解码速度更快的静态网络解码器更加适合。静态网络的解码器基于加权有限状态机(WeightedFiniteStateTransducer,WFST)[7]。WFST解码器的特点是实现简单，解码速度快，对于知识源有统一的建模方式，并且它具有完善的理论框架以及成熟的优化算法。应用在语音识别的WFST网络输入一般为上下文相关的三音素或者隐马尔科夫模型(HMM)状态，输出为识别词。为了让解码器网络得到充分优化加快解码速度和降低解码的内存占用，解码网络中不含词边界信息，这就为WFST解码器生成含有精确时间点的词图造成了一定困难。文献[8]中提出了最早的WFST解码器的词图生成算法，准确说文献[8]是介绍了一种记录WFST格式的解码路径的算法，它并不包含词的边界和时间信息，它产生的词图主要用于语言模型重打分。文献[6]提出了在构建解码网络的时候插入额外的词尾标记用于找回词尾时间信息，但额外的词尾标记会导致解码网络得不到充分优化，从而网络变大，并且，解码网络格式的变化也导致解码网络的使用缺乏兼容性，需要为生成词图的解码器重新构建网络。Povey等人[9]提出了一种WFST的词图生成算法并应用在开源项目Kaldi[10]中。但是这种算法产生的是一种HMM状态级别的词图，仍然不是标准的词图。文献[9]在文中提到不同解码器产生的词图在格式上不统一的问题，要做统一的比较和解释比较困难。本文在给出了语音识别标准词图和WFST的解码音素图的定义之后，探索了两者之间的联系，提出在WFST解码器下的词图生成算法。本文首先提出了一种动态字典匹配的方法，此方法可以用来进行词的时间点对齐，解决了WFST解码网络没有精确词尾节点的问题。然后提出了一种基于令牌传递(tokenpassing)的方法，把WFST的解码音素图转换为标准词图。由于本文提出的WFST词图生成算法生成的是标准的词图，可以应用到已有的重打分、关键词检索等一系列后处理应用中而无需额外操作，且由于没有对网络进行特殊处理，本算法在网络使用上具有兼容性，无需重新构建解码网络。本文的组织结构如下：第2节介绍背景知识，给出了WFST的定义和解码框架以及标准词图的定义；第3节揭示了WFST音素图和词图的联系和映射关系；第4节和第5节分别给出了词图的生成算法和相应的实验结果及分析；最后，第6节给出结论。2背景知识2.1基于WFST的解码框架WFST是一个权值定义在半环K上的8元组[7]：,,,,,,,TQEiF(1)其中和分别表示输入符号和输出符号，Q为有限状态集，iQ和FQ分别为起始状态和最终状态集合，起始状态的权值和最终状态集的权值函142电子与信息学报第36卷数分别为和，边集{{}}{{}}EQKQ，表示了一种转换功能：从一个状态跳转到另一个状态的同时，可以把输入符号转换为对应的输出符号，同时经过这条边的权值为k。代表的是空的输入输出符号。在语音识别中常用的权值半环有Log半环和Tropical半环[7]，为了达到更精确的识别率，本文采用Log半环。最终的静态解码网络的构建可以表示成为mindet()FC'L'G'(2)其中C',L',G'分别代表了加入辅助符号的上下文相关模型、发音字典和语言模型；min,det和分别代表WFST的最小化、确定化和复合操作；代表的把辅助符号转换成空边的操作。生成的WFST的最终解码网络是一个有向有环图。一条WFST的路径包含了一个输入序列1()()()nllele和对应的输出序列1()()()nOOeOe，路径的权值在Log半环下表示成为1()nnKKeKee(3)2.2标准词图标准词图是一个含有解码信息