2022年词图搜索算法-模式识别 .pdf

《2022年词图搜索算法-模式识别 .pdf》由会员分享，可在线阅读，更多相关《2022年词图搜索算法-模式识别 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六届全国人机语音通讯学术会议，203-206 页，2001 年 11月 20-22 日，深圳一种基于 HTK 的词图搜索算法罗春华，张继勇，郑方，徐明星清华大学计算机系人工智能与系统国家重点实验室语音技术中心 摘要在连续语音识别中，为了能够在搜索的过程中实现更有效的剪枝策略，必须充分应用语言模型提供的信息。对于在一遍搜索过程中同时使用声学模型和语言模型的搜索算法而言，虽然能够获得比较高的识别率，但是耗时比较多。为此，本文实现了一种能够在后续处理过程中有效地利用Trigram 语言模型和更复杂语言模型信息的词图搜索算法。它是基于HTK 平台的。文中对词图的数据结构和词图的生成算法给出了非常详细

2、的论述，基于给定词图的搜索算法也在文中给出。实验表明，词图搜索算法能够充分地利用语言模型提供的信息指导搜索而且速度很快。1.引言在语音识别的过程中，如果我们能够利用一些知识来指导搜索过程，一方面可以有效的提高搜索速度，另一方面可以提高识别率。在HTK中搜索使用的是Token Passing1算法。该算法由一个识别网络进行控制，识别网络的生成充分利用了词典和HMM模型提供的信息。在Token passing 算法中，Token 表示网络中从时刻0 扩展到时刻t的部分路径。时刻0，在每个可能的开始结点上都有一个Token，随着时间的推移，它们沿着识别网络的弧进行传播，直到到达一个HMM的退出状态。

3、如果一个结点有几个出口，则该Token 会被拷贝以保证多条路径能够并行的得到扩展。当Token 沿着弧和结点进行传播时，它的对数似然度 分 数会 加 上 相 应 的 转 移 概 率 和 输 出 概 率。当Token 沿着网络进行传播时，它必须保留它的历史路由的 记录。历史 记录 保留的详细程度取决 于识别输出的需要，通常保留词边界 的信息 就能够 满足 大多数应用的 需要。由于HTK 是一个实验平台，因此它的算法 没有考虑到实 际应用的 需要。为了能够保证该算法的通用性，它的数据结构设计得很复杂。一个典型的例子就 是它的识别网络。对于汉语连续语音识别，通常词表的大小为5 6 万 词，按照 它的

4、算法构造的网络非常庞大，因此要 想在它的上面使用Trigram 语言模型几 乎是不可能的。为了能够建立 一个实用的识别器，我们在 HTK 的基 础上，借鉴 了它的一些 好的思路，实现了自己 的识别 器。通过Trigram 的加 入，取得了比较好的效果。我们算法的基本思路是 首先 在一遍搜索的过程中使用声学模型和Bigram 语言模型来 产生一些可能的词 候选，利用 这些词 候选 来产生词图，然后在后续的过程中利用Trigram 对词图 里的可能路径进行分数重 估，最后输出 具有最大似然度的路径 作 为识别候选。本文 将按照 如下方式组织：在论文的第 二部分，将介绍 利用复杂语言模型的词图搜索算

5、法的框架；基于该框架 结构的词图重估算法 将在第 三部分给出；论文的第 四部分为 采用这种词图搜索算法的实验结果；相关的结论 将在论文的第 五部分给出；论文的 最后给出相关 的参考 文献。2.词图搜索算法的框架采 用词图搜索算法的语音识别系统的框架 结构如 下图所 示：集成搜索语音输入词图重估过程词串输出声学模型Bigram Trigram 图 1.采用词图搜索算法的连续语音识别系统的框架语音输入 后，经 过 特 征 提 取，首先 经 过 集 成搜索（Integrated search）模块，这个过程利用声学模型来产 生声学 候选，同时利用Bigram 语言模型来剪枝，该模 块产 生的词图（W

6、ord graph）被词图重估模块（Word graph rescoring）用来进行后处理，在这个过程中可以充分地利用Trigram 语言模型提供的信息，最 后我们可以得到识别出来的中文词序列。2.1.集成搜索模 块该模 块的主要功能是利用声学模型和Bigram 语言模型提供的信息来产生词 候选，便于词图的生成。为了能够进行上下文相 关建 模，我们 选取 了声 母和 韵母作为语音识别基元，在此基 础上，利用HTK 提供的 训练 工具 HINIT，HREST 和 HEREST 来训练 TriIF 模型（请注意，这里 的 IF 指的是声 母或者韵母）。由于 汉语的常用词大 约有 50000 多个

7、，因此我们 采用树型结构来 组织这 些词，它可以有效的合并具有相同 前缀的词。每个词的模型通过连接 对应的TriIF 模型来获名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -得。如词“饱餐”由“b+ao”，“b-ao+c”，“ao-c+an”，“c-an”组 成，当然如果考虑 上下 文相 关（即Cross-word）2，则词的模型要考虑 到它的 前驱词的 具体内容才 能最终确 定。在搜索的过程中，充分利用了目前 比较常用的一些剪枝技术，如声学剪枝、语言模型剪枝和直方图剪枝，同时 还使用了 两种 Look-ahead 技术，分别是语言模型Look-ahead3和 IF L

8、ook-ahead。语言模型Look-ahead技术的 采用是为了能够比较早地使用语言模型提供的信息来指导搜索。为了确保算法能够比较高效地运行，我们利用的是Bigram。至于 IF Look-ahead 技术，它的引 入是为了更 好的进行声学 层的剪枝，从而提高识别的速度。2.2.词图的生成在集成搜索过程中我们会保留一些可能的候选，这些候选 被用来生成词图。在我们的搜索算法中，词图采用六 元组),(eawttswea来表示，其中ea,是词w的逻辑 开始和结 束结点，eatt,为逻辑 开始和结束 结 点 对 应 的 时 间 帧 序 号，ws为 词w在 区 间,eatt上的 HMM分数的对数 值。

9、在图 2 中我们给出一个词图的 例子。图 2.词图的 例子我们可以 看出词图 具有以 下特 点：?在同 样的时间 区间内，能够保留多个候选，如13 之间的“一派”和“离 开”。?同一个词可能有不同的结 束时刻，如34 之间的“港湾”和 35之 间的“港湾”。?同一个词可能有不同的开始时刻，如78 之间的“_SIL”和 68之 间的“_SIL”。在对词图 做具体描述时，我们采用了如 下的数据结构：词图的数据结构为：?Graphnode nodeMAXGRAPHNODE 记录 结点的信息?Grapharc arcMAXGRAPHARC 记录 弧的信息?int linkMAXGRAPHARC 记录

10、每个结点 发出去的弧?int offsetMAXGRAPHNODE+1 记录 每个结点 发出去的弧的 偏移量?int nodeNum 记录 词图中 总的结点数 目?int arcNum 记录 词图中 总的弧数 目其 中 MAXGRAPHARC和 MAXGRAPHNODE为两个预先 定义好 的常 量，分别表示词图所能拥有的弧的 最大数 目和结点的 最大数 目。Graphnode 为记录 词图中结点信息的数据结构，其具体 的表示 形式 为：?int nodeIdx 结点的索引?int timeId 结点的时间 戳，和时间 帧相对应?float maxScore 记录 通过一个结点的所有路径的 最大

11、分数Grapharc 为记录 词图中弧的信息的数据结构，其表示形式 为：?float likeScore 记录 词的似然度得分?int wordIdx 词的索引，该索引是从词典中获得的词的 编号?char wordString20 记录 表示词的中文字符串 的数组构 造词图 所需 要的 所有信息都在 集成搜索模 块 搜索过程中保 存的 Path 数据结构 里。在 HTK 中，Path 数据结构的定 义如下：?path*prev 记录前 一个词的 记录?LogDouble like 记录累 计的似然度得分，注意这里不仅包括 声学模型得分，也包括 语言模型分数?LogFloat lm 记录累 计的

12、词的语言模型得分?DWORD nodeidx 记录 结点在词法 树中对应的结点编号?int frame 记录 词结 束的时刻（用帧数表示）?Boolean used 是否被引用的 标志位?int usage 被下一条路径引用的次数?path*link 链表中的 下一条路径?path*knil 链表中的 前一条路径由该数据结构可以看出，路径信息 组成了一个 双向链表，这样做 的 主要 目的是为了方便地对 链 表进行 插入、删除 和查找等操作。如果我们从 那些能够到达 最后时间 帧的路径开始 回溯，则一 般能够 找出大 约 10条 左右 的路径。在一遍搜索过程中，通常是从这些路径中 挑选 出具有最

13、大似然度概率的路径作为最终 的识别结果。而在采用词图数据结构的搜索算法中，搜索的路径 范围 大大扩大了。我们仍然以图2 为例，在结点 3，这个时 候产 生的词为“港湾”，它的 前驱 词可能为“一派”和“离 开”。在结点3 向后扩展 之前，将首先执 行剪枝 操作。这个时 候“一派”和“离 开”中的 某一个词很有可能就被剪 掉，失去 了继续 向后扩展的机会。我们假设“一 派”被剪 掉，这样将 导致“一派”所 在的路径 无法到达语音输 入的结尾帧，从而 不可能被识别 器输出。而如果 采用词图数据结构来保留 候选，我们可以 看到，“一派”和“离开”都有可能是“港湾”的前驱，这时的可能路径条数就由原来的

14、一条 变成了 两条。词图中可能路径的变多，使得我们能够充分的使用Trigram 来评测各 种可能的 候选路径。候选 路径的多 少从某种程度上 反映 了词图的 稀05142_SIL _SIL 一派离开港湾78补救途径补酒_SIL港湾36_SIL不久名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -疏程度。词图过密，保留的 候选 必然很多，这样 在词图重 估的时 候比较 费时，但是它能够提高识别率。词图过 疏，重 估过程必然加快，但是它可能导致一些 期望的候选没 有在词图中出现。这个时 候无 论采用什么重估方法，都 将无 法获得 期望 的词 串输出，此时出现的错误 是无法恢复

15、的。因此需要在识别率和计算复杂度之间作权衡考虑。3.词图重 估算法词图重 估算法是词图搜索算法中比较重要的一个模块，其主 要目的是对词图中保存的可能的 候选 路径进行分数重 估，在重 估的过程中使用Trigram 语言模型或更复杂语言模型提供的信息来指导搜索。这个过程一般来说耗时比较 少。词图重 估算法可以 采用以 下的伪码 语言来 描述：1.对于 链表中的每个实 例 inst 执行如 下操作 步骤 1：根 据结点inst-nodeidx 发出去 的弧来扩展 inst，同时 把 inst 的 token src，dwHistoryId，nodeidx，arcidx 传递给新产生的实 例。?在实

16、 例链 表中 寻找历史词为 dwHistoryId，弧索引为 arcidx 的实 例 inst1?如果 inst1 为空，则 创建实例 inst1，计算 Trigram语言模型概率，并且赋给 inst1-nodelm，同时 把它加到实 例链 表的 末尾*?更新 src 的似然度：src-like+=inst1-nodelm+wordgraph.arcarcidx.likescore?如果 src-like inst1-state-like，则 把 token src 传递给 inst1 的状态 0*?如 果inst1-like低 于wordgraph.nodeinst1-nodeidx 的剪枝

17、 阈值，则 把 它从实 例链 表中移走，防止 后续的扩展?否则如果*为假而*为真，则扩展inst1 步骤2：利用路径 记录目前 正被处理的实 例的信息和它的 前趋词的 记录 2对路径数组进行 回溯 以获得 最佳的中文词 序列串。请注意，这个时 候路径数 组里所 保存的路径的似然得分是 各个词的 纯声学得分以 及 Trigram 语言得分的 总和，因此，即使是和一遍搜索里产 生的路径 完全一 样（这里 的一 样指的是词 序列 一样，而且对应词的时间分点也一 样），由于一遍搜索里使用的是Bigram 分数，它们的似然得分也是不一样的。4.实验实验 采用的模型为TriIF 模型，由 863 数据 库

18、中 70 个人的 男声数据 训练 而得，测试集选取 了 863 数据 库中的 2 个人的 男声数据，另 外为了 做对比，也 选取 了训练 集 中 的2 个人来 做测 试。特征参 数为16 维 的MFCC 和对数能 量，以 及它们的 ARCEP 参数，共 34维。每个 测试人的数据 包括 521 个句子。1)一遍搜索和词图搜索的比较表.1:一遍搜索和词图搜索的性能的比较测试人算法M00M08 M11 M16一遍搜索68.4%80.2%66.0%50.0%词图搜索69.0%80.7%67.6%52.6%这里 M00 和 M08 来自于训练集 的数据，M11 和 M16来 自于测试集的数据。2)时间

19、复杂度的比较选 取 的 测 试 数 据 为M16的100句 话，从m16c1041.mfc 一直到m16c1140.mfc，采用的方法分别为：直 接使用 Trigram 语言模型的一遍搜索（也称集 成搜索），在利用Bigram 的一遍搜索 产生的词图基 础上的词图搜索。表2:时间复杂度的比较算法评测量词图搜索一遍搜索I 一遍搜索II 时间41 分钟62 分钟108 分钟识别率44.9%42.3%43.8%在使用Trigram 语言模型的一遍搜索中，为了能够达到比较理 想的识别率，剪枝阈值不 能设置得太 小，否则由于 没 有保留 足 够多的历史信息，使用Trigram 并不 一定能够提高识别率。

20、表2 中一遍搜索I 和一遍搜索 II 的区别就在于一遍搜索II 中的 阈值设置 得比较大，在搜索的过程中保留了比较多的候选（这样 正确的 候 选 就 更 有 可能 被 保 留 下 来），因 此 通 过使用Trigram 语言模型分数，正确的候选才 更有可能被 挑选 出来，导 致识别率有了提高，但是要想超过词图搜索的识别率，剪枝阈值应该 设置得更 宽，此时耗 费的时间必然更多，这对于一个实时系统而言是无 法容忍的，因此在一遍搜索中直接使用Trigram 是不 大可能的。5.结论1 在词图搜索中使用Trigram 语言模型是可行的，而且耗 费的时间很 少。通过实验结果表2 可以 看出，在 没有很

21、好的剪枝策略的 前提下，是 没有办法在 集成搜索中直 接使用 Trigram 的，所以此时使用词图搜索算法 就成为了必然。2 词图搜索算法使得复杂语言模型的利用成为可能（比如 Long-span 语言模型）。词图搜索算法相比集成搜索算法的优越 之处不仅 在于它能够很 轻松 的使用Trigram 语言模型，更重要的是，我们可以在词图的名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -基础 上 尝试 使用 各 种复杂的语言模型，比如Long-range 的 Trigram 等。可以 这么说，词图搜索算法能够作为我们 测试语言模型 性能的一种方法。3 词图搜索算法在测试集中的

22、性能表现要 优于训练集，这主 要得 益于它从相似 候选 中选取 出正确候选 的能力。从表1 可以 看出，在 训练集（M00、M16）的测试中，M00 和 M08 的识别率 没有明 显的提高，而在测试集（M11、M16）中，M11 和 M16 的识别率有了一定程度的提高。这种现 象出现的 主要原因 在于：对于 训练集，由于声学模型就是用 这些数据 训练 出来的，因此相 互之 间匹配 得比较 好，这样 在识别的时候，它 产生的 候选 质量比较高，更为重要的是，我们期望 的候选（正确的声学 候选）所 在的路径的分数比较高，这样 只通过使用Bigram，这些正确的候选就 能够被 挑选 出来，因此在 训

23、练集 中的 测试看不 出明 显的效果。Trigram 挑选候选 的能 力在测试集中体现得比较明 显。这充分的 说明词与词 之间的 搭配 关系如果在识别的过程中得到正确 的应用，是能够提高识别率的，而且 不会带来明 显的计算 负担。6.参考 文献1Young,S.,Kershaw,D.,Odell,J.,Ollason,D.,Valtchev,V.&Woodland,P.,“The HTK Book”,Microsoft Corporation,Dec,1995bbu 2Beulen,K.,Ortmanns,S.&Elting,C.,“Dynamic Programming Search Tec

24、hniques for a Cross-Word Modeling in Speech Recognition”,IEEE Internal Conference on Acoustic,Speech and Signal Processing,vol.2,Phoenix,AZ,Mar.1999 3Ortmanns,S.,Eiden,A.,Ney,H.&Coenen,N.,“Look-ahead Techniques for Fast Beam Search”,Proc.Int.Conf.Acoustics,Speech and Signal Processing,vol.3,Munich,Germany,Apr.1997,pp.1783-1786 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -