用于语音识别和自然语言理解的具有合成统计和基于规则的语法模型的系统

摘要

本发明使用合成统计模型和基于规则的语法语言模型，以执行语音识别任务和自然语言理解任务。

说明书

发明背景

本发明涉及语音识别和自然语言理解。更为准确地说，本发明涉及使用一种由统计模型部分和基于规则的语法部分所组成的复合模型，来作为一种同时执行语音识别和自然语言理解的语言模型。

识别和理解口头的人类语言对于将来的计算环境而言被认为是必要的。到目前为止，依据两种不同的系统提出了识别和理解口头语言的任务。第一种系统是视语音识别系统，第二种系统是自然语言理解系统。

传统的语音识别系统接收一个指示口语输入的语音信号。通过使用声学模型和语言模型，在语音信号中识别声学特征并解码语音信号，以提供一个由输入语音信号所表示的字词的输出。

同样，为促进语音激活应用和服务的发展，基于语义的稳固的理解系统正处于开发中。这种系统被广泛应用于会话式的研究系统中。然而，对于传统的开发者在执行会话式系统时而言，他们并不是特别实用。很大程度上，这种执行依赖于领域特定语法(domain-specific grammars)的人工开发。该任务是费时的、易出错的，且要求领域中的大量专业知识。

为推进语音激活应用和服务的开发，引入一种基于实例的语法编辑工具。该工具称为SGStudio，且已在Y.Wang和A.Acero的《用于口语理解的语法学习》(IEEE自动语音识别和理解的专题研究组，意大利Madnna D.Campiglio，2001)以及Y.Wang和A.Acero的《ATIS域中口语语法学习的评估》(ICASSP学报，奥兰多，FL 2002)中被进一步地讨论。该工具通过利用在先信息的许多不同资源而大大简化了语法开发。其也允许不具备语言知识的正式的开发者建立用于语言理解的语义语法。该系统通过较少的数据来促进相对高质量的语义语法的半自动生成。此外，该工具不仅大大减少了语法开发中的工作，并且改进了跨越不同领域的理解的精确性。

然而，NLU系统中纯粹的基于规则的语法仍然缺乏稳固性且表现出脆弱性。

另外，最重要的是，如果不是全部的话，在先的方法将理解作为一个独立于语音识别的独立问题。通常采用一种双途径的方法，其中在第一途径中构建一个领域特定的n字符列语言模型并将其用于语音识别，在第二途径中运用通过各种训练算法所获得的理解模型，以“理解”语音识别器的输出。

发明概述

可以相信的是，将理解和语音识别作为两个分离的、独立的任务的在先系统表现出许多缺陷。首先，当建立一个用于语音识别的n字符列语言模型时，被最优化的目标函数减少了测试数据混乱，其涉及语音识别字词错误率的减少。这并不一定导致整个理解错误率的减少。其次，大量培训数据对于许多语音应用程序的开发而言很少有用。少量数据之上训练的n字符列产生不良的识别精确度。

因此，本发明使用复合统计模型和基于规则的语法语言模型，以执行语音识别任务和自然语言理解任务。

本发明的一个实施例还包括，通过借助参照越过后退状态的共享分布来处理每一n字符列的所有未现的字词，以一种紧凑方式来构建一个相应于复合模型的状态机，而不是在每个n字符列中为每个未现字词包括一个循环。

附图简述

图1是一个适用本发明的典型环境的框图。

图2A是根据本发明实施例的模型编辑组件的一个实施例的框图。

图2B说明一个实例概要。

图2C说明为实例概要而生成的一组实例规则。

图2D说明一个带注释的句子的实例。

图2E说明一个实例分析树。

图2F说明用于实例中的字词的可能的前终端表。

图2G是带有相关计数和概率的重写规则表。

图3A是非常详细地展示语法编辑组件的框图。

图3B是说明如图3A所示的语法编辑组件的流程图。

图4说明根据本发明另一实施例的一个模型编辑组件。

图5展示列举的分段的一个实例。

图6非常详细地说明根据本发明的一个实施例的统计模型。

图7是一个简化概要的实例。

图8是从图7概要中生成的一组规则的实例。

图9是带注释的句子的一个实例。

图10展示所生成的规则。

图11说明复合模型的状态图。

图12展示了描述训练技术的伪码。

图13说明用于使用根据本发明所生成的模型的运行期系统的框图。

图14说明一个解码器结构的实例。

图15是语音识别系统的一个简化框图。

图16说明被用于如图17A——18B所示的实例中的另一简化的应用程序模式。

图17A说明相应于图16所示概要所生成的顶级语法的一个隐藏马尔可夫模型(HMM)结构。

图17B非常详细地说明来自图17A的“ShowFlight”模型的HMM结构。

图17C说明如图17B所示的HMM结构的使用。

图18A说明带有两个观察字(a，b)的双字母组语言模型的一个有限状态表示。

图18B说明一个模型的有限状态表示，所述模型模拟在如图18A所示的后退状态之上的均匀分布。

图18C展示带有两个观察字(c，d)的双字母组语言模型的一个有限状态表示。

说明性实施例的详细描述

本发明涉及一种语音识别和自然语言理解系统。尤其是，本发明涉及可用于语音识别和自然语言理解的一个复合的基于规则的语法和统计模型。然而，在非常详细地讨论本发明之前，将讨论可使用本发明的一个典型环境。

图1说明执行本发明的一个适宜的计算系统环境100的实例。计算系统环境100仅是一个适宜的计算环境的实例，而并不是试图暗示关于本发明的使用或功能的范围的任何限制。计算环境100不得被解释为具有关于在典型运行环境100中说明的任一组件或其结合的任何依赖或要求。

本发明通过大量其它通用或专用计算环境或结构而运行。适合与本发明的同时使用的众所周知的计算系统、环境和/或结构的实例包括但不限于个人计算机、服务计算机、手提或膝上型设备、多处理器系统、基于微处理器的系统、顶置盒、可编程消费电子产品、网络PC、小型机、大型计算机、分布式计算环境、包括上述任意系统或设备的分布式计算环境及其类似物。

可在计算机执行计算机可读指令诸如程序模块的一般环境中描述本发明。通常，程序模块包括执行特殊任务或实施特殊的抽象数据类型的例程、程序、对象、元件、数据结构等。本发明还实践于分布式计算环境中，其中借助通过通信网络链接的远程处理设备来执行任务。在一个分布式计算环境中，程序模块可被置于包括存储设备的本地和远程的计算机存储媒介中。

参照图1，用于实施本发明的一个典型系统包括计算机110形式的一个通用计算设备。计算机110的组件可包括但不限于处理单元120、系统存储器130、耦合包括系统存储器到处理单元120在内的各种系统组件的系统总线121。系统总线121可以是几种类型总线结构的任一种，所述包括存储器总线或存储控制器、外围总线、使用各种总线结构的局域总线。作为示例，但并非限制，这种结构包括工业标准结构(ISA)总线、微通道结构(MCA)总线、增强的ISA(EISA)总线、视频电子标准协会(VESA)局域总线以及外围部件互连(PCI)总线也称为Mezzanine总线。

计算机110典型的包括多种计算机可读媒介。计算机可读媒体可以是任何一种可被计算机110访问的可用媒介，其包括易失性和非易失性媒介、可移动和不可移动媒介。作为示例而并非限制，计算机可读媒介可包括计算机存储媒介和通信媒介。计算机存储媒介包括以存储信息诸如计算机可读指令、数据结构、程序模块或其它数据之类的任一方法或技术来实施的易失性和非易失性媒介、可移动和不可移动媒介。计算机存储媒介包括，但不限于RAM、ROM、EEPROM、快速存储器或其它存储技术、CD-ROM、数字万能盘(DVD)或其它光盘存储器、磁带盒、磁带、磁盘存储器或其它磁存储设备，或任何可被用于存储所期望的信息且可被计算机00所访问的其它媒介。通信媒介典型的包括计算机可读指令、数据结构、程序模块或诸如载波或其它传输机制之类的调制数据信号中的其它数据，且包括任何信息传输媒介。术语“调制数据信号”是指具有一个或多个特征集合或根据信号中的编码信息而更改的信号。作为示例而并非限制，通信媒介包括诸如有线网络或直接有线连接之类的有线媒介，以及诸如声音、FR、红外线和其它无线媒介之类的无线媒介。上述任一的结合也被包括在计算机可读媒介的范围中。

系统存储器130包括易失性和非易失性存储器形式的计算机存储媒介，诸如只读存储器(ROM)131和随机访问存储器(RAM)132。基本的输入/输出系统133(BIOS)通常存储于ROM131，该系统包括在启动期间有助于计算机110中元件之间传输信息的基本程序。RAM132通常包括可被处理单元120所直接访问和/或当前处理的数据和/或程序模块。作为示例而非限制，图1说明操作系统134、应用程序135、其它程序模块136和程序数据137。

计算机110还可包括其它可移动/不可移动、易失性/非易失性计算机存储媒介。仅作为示例，图1说明：对不可移动的、非易失性的磁媒介进行读写的硬盘驱动器141，对可移动的、非易失性的磁盘152进行读写的磁盘驱动器151，以及对诸如CDROM或其它光学媒介之类的可移动的、非易失性光盘156进行读写的光盘驱动器155。可被用于典型的操作环境中的其它可移动的/不可移动的、易失性/非易失性计算机存储媒介包括但不限于磁带盒、快速存储卡、数字万能盘、数字视频带、固态RAM、固态ROM及其类似物。硬盘驱动器141通常通过诸如接口140之类的不可移动的存储器接口而连接于系统总线121，磁盘驱动器151和光盘驱动器155通常可通过诸如接口150之类的可移动的存储器接口而连接于系统总线121。

在上文中讨论及在图1中说明的驱动器和它们的相关计算机存储媒介存储有计算机110的计算机可读指令、数据结构、程序模块和其它数据。在图1中，例如，硬盘驱动器141存储有操作系统144、应用程序145、其它程序模块146和程序数据147。需要注意的是，这些组件可相同或不同于操作系统134、应用程序135、其它程序模块136和程序数据137。对操作系统144、应用程序145、其它程序模块146和程序数据147给出不同的数字以便于说明至少它们是不同的复制品。

用户可通过诸如键盘162、麦克风163和指示设备161(譬如鼠标、跟踪球、触摸垫等)之类的输入设备来将命令和信息输入到计算机110。其它输入设备(图中未示)可包括操纵杆、游戏垫、卫星反射器、扫描仪或其类似物。这些或其它输入设备通常通过被耦合到系统总线的用户输入接口160而连接到处理单元120，还可通过其它接口和诸如平行端口、游戏端口或通用串行总线端口(USB)之类的总线结构而被连接。监视器191或其它类型的显示设备还可经由诸如视频接口190之类的接口而被连接到系统总线121。除监视器外，计算机还可包括诸如扬声器197和打印机196之类的其它外围输出设备，其可通过输出外围接口190而被连接。

借助和诸如远程计算机180之类的一个或多个远程计算机的逻辑连接，计算机110可在网络环境中操作。远程计算机180可以是个人计算机、手提设备、服务器、路由器、网络PC、同级设备或其它普通网络节点，且通常包括上述和计算机110相关的许多或全部部件。在图1中描述的逻辑连接包括本地局域网(LAN)171和广域网(WAN)173，还包括其它网络。这种网络环境在办公室、广域企业计算机网络、企业内部互联网和因特网中是常见的。

当在LAN网络环境中使用计算机110时，它通过网络接口或适配器170而连接到LAN171。当在WAN环境中使用计算机110时，它通常包括在WAN173(例如因特网)上建立通信的调制解调器172或其它装置。可处于内部或外部的调制解调器172可经由用户输入接口160或其他合适的机构而连接到系统总线121。在网络环境中，所描述的和计算机110相关的程序模块或其中的部分可被存储在远程存储器设备中。作为示例而非限制，图1说明驻留在远程计算机180上的远程应用程序。可以理解的是，所示的网络连接是典型的，且可使用其他手段在计算机之间建立通信链接。

应该注意到，本发明可在诸如就图1所描述的计算机系统上运行。然而，本发明可在服务器、专用于信息处理的计算机或在分布式系统中运行，其中在分布式系统中本发明的不同部分在分布式系统的不同部分中运行。

图2A是根据本发明的一个实施例的模型编辑系统200的框图。模型编辑系统200包括模型编辑组件202和可选用户接口204。图2A还展示了模型编辑组件202接收概要206、一组训练实例文本串208、可选语法库209来作为输入，并输出基于规则的语法(例如上下文无关语法或CFG)210。可选语法库209包括用于域独立概念(例如日期和时间)和域从属概念(例如城市名、航线等)的定义，其可从应用数据库中被获得。

以下将用较长篇幅来描述系统200的详细操作。然而，简要地说，用户提供具有概要206和训练实例文本串208的模型编辑组件202。既可以通过可选用户接口204也可通过其他的一些用户输入机构或通过自动装置来实现。模型编辑组件202接收输入并且基于输入而产生基于规则的语法210。作为基于规则的语法的例子是一允许计算机将输入映射到文本的语义表示的上下文无关语法(或CFG)。

概要206例证性地是被模拟域的语义描述。在图2B中展示了概要的图解。图2B说明了大大简化的概要212，其可通过开发人员而被输入到系统200中。概要212表示用于从用户输入到显示飞机启程和抵达的不同城市且具有不同的启程和抵达时间的各种文本串的含义。概要212表明显示飞行命令(ShowFlight)包括作为一时间段的Flight的语义类别。概要212还非常详细地说明Flight的语义类别，指示其具有四个分别相应于启程时间、抵达时间、启程城市和抵达城市的时间段。

从概要212中，模型编辑组件202可生成一组图2C所说明的规则。规则一表明ShowFlight句子将一直具有命令部分ShowFlightCmd，其后有属性部分ShowFlightProperties。

规则二表明ShowFlightProperties部分在其中具有一个或多个属性。例如，规则二表明ShowFlightProperties部分包括至少一个可跟随有可选ShowFlightProperties部分的ShowFlightProperty。该ShowFlightProperties的递归定义简化了它的表达并允许其具有一个或多个属性。

规则三表明ShowFlightProperty部分包括一个ShowFlightPreFlight部分、一个Flight部分和一个ShowFlightPostFlight部分。其表明概要中的时间段Flight可具有前文和后文。

由于Flight是概要中的一个对象而ShowFlight是一个命令，所以规则四表明概要中的对象Flight不具有命令部分，但仅具有一个属性部分(ShowFlightProperties)。规则五展示ShowFlightProperties部分再次被递归定义为包括至少一个跟随有可选ShowFlightProperties的ShowFlightProperty。

规则六—九相应于如图2B所示概要212中的四个时间段。规则六将第一属性定义为具有一个启程城市时间段，该时间段被前文(FlightPreDepartureCity)超先且跟随有后文(FlightPostDepartureCity)。规则七以相同的方法定义抵达城市，规则八和九分别以相似的方式定义启程时间和抵达时间。

即使存在这样的事实，即模型编辑组件202可从概要212中自动生成在图2C中被识别的全部规则，这里依然没有重写规则，该重写规则表明什么样的特定字词实际上被映射到特定的前终端(用于命令语义类别的命令以及用于时间段的前文和后文)。例如，不存在表明短语“please show me the fiight...”被映射到ShowFlightCmd的规则。同样，不存在表明字词被映射到例如FlightPreArrivalCity前文等的规则。由此，开发人员也可输入训练实例文本串和注释208，以使模型编辑组件202也可学习这些重写规则。

图2D说明相应于文本串213的语义注释214和实例文本串213“Flight fromSeattle to Boston”的例子。语义注释214由开发人员提供并表明串213的语义意义。例如，语义注释214表明相应于ShowFlight命令的输入文本串213具有自身包括两个时间段且都为城市的时间段Flight。Flight时间段中的两个时间段之间的区别仅在于时间段的名称。其中之一被称为“抵达”城市，另一个被称为“启程”城市。语义注释214也将字词“Boston”映射到“到达”城市时间段，将字词“Seattle”映射到“启程”城市时间段。因此，基于注释214，模型编辑组件202将知道哪个slot被映射到字词“Seattle”和“Boston”。

根据图2C所示注释的实例和模板语法规则，模型编辑组件202可生成基于规则的语法(或CFG)分析树，例如在图2E中说明的分析树216。分析树216的第一级218(该部分表明ShowFlight由跟随有ShowFlightProperties的ShowFlightCmd所形成)由图2C中的规则1所形成。

第二级220(该部分表明ShowFlightProperties由ShowFlightPropert所形成)从规则2中生成，在规则2中不使用可选ShowFlightProperties部分。

下一级222(该部分表明ShowFlightProperty由跟随有Flight的ShowFlightPreFlight所形成，其中该Flight又跟随有ShowFlightPostFlight)从图2C中的规则3中生成。

下一级224(表明Flight对象由FlightProperties部分所形成)从图2C中的规则4中生成。

下一级226(该部分表明FlightProperties部分由跟随有FlightProperties部分的FlightProperty部分所形成)从图2C中的规则5中生成。

下一级228(该级表明FlightProperty部分由跟随有City时间段的FlightPreDepartureCity部分所形成，其中该City时间段又跟随有FlightPreDepartureCity后文)从规则6中生成，下一级230(该级表明FlightProperties由FlightPreArrivalCity前文、City slot和FlightPostArrivalCity后文所形成)从规则7中生成。

最终，该级根据从由用户输入的语义注释214而生成，其中该级表明字词“Seattle”被映射到级228下的City时间段且字词“Boston”被映射到级230下的City时间段。从而，模型编辑组件202可学习如何从输入句子中的字词“Seattle”和“Boston”映射到CFG分析树和在图2C中生成的规则之中。应该注意的是，也可替代注释数据而从库语法(其可通过从域特定数据库中提取数据数据而被依次构建)中获得城市规则。

然而，在输入句子中仍然存在大量还未被映射到树的字词。这些字词包括“Flight”、“from”和“to”。由于字词“Flight”和“from”在字词“Seattle”之前，它们可映射到分析树216的多个前终端，包括FlihgtCmd、ShowFlightPreFlight和FlightPreDepartureCity。同样，由于字词“to”位于输入文本串213中的字词“Seattle”和“Boston”之间，字词“to”可映射到FlightPostDepatureCity或FlightPreArrivalCity。

由于可知字词“to”是介词，必须修改在其后所出现的词。因此，可确定字词“to”被映射到分析树216中的FlightPreArrivalCity前终端。

然而，仍然不知道分析树216中的字词“Flight”和“from”位于何处。同样，也不知道两个字词的特殊分段。例如，在一个可选方案中，字词“Flight”可被映射到ShowFlightCmd，而字词“from”被映射到ShowFlightPreFlight。在这种情况下，前终端FlightPreDepatureCity被映射到一个空集。

根据另一可选方案，字词“Flight”和“from”都可被映射到“ShowFlightCmd”，而其它前终端ShowFlightPreFlight和FlightPreDepartureCity都被映射到空集。

在另一可选方案中，“Flight”被映射到ShowFlightCmd，且“from”被映射到FlightPreDepartureCity，而保留的前终端ShowFlightPreFlight被映射到一个空集。

这代表分段歧义，所述分段歧义在没有来自开发人员的附加信息的情况下过去仍未被解决。在现有系统中，每一可能的分段被简单地呈现给用户，且允许用户选择这些分段中的一个。

然而，这已产生大量的问题。首先，和用户的这种交互是扰人的且耗时的。同样，当这里可能的前终端越多，输入文本串中的单独的字词也就越多，必须呈现给用户的似然的数量戏剧性地增长。如果可能的话，为用户的选择而有效显示所有这种候选分段使非常困难的。另外，即使当为用户的选择而充分显示分段时，用户经常在分段中出错或不一致地分割相似的文本串。

根据一个实施例，期望最大化算法(EM)被应用于模型组件202中的分段歧义中，以消除分段选择的歧义。当模型包括不可观测的隐藏的变量时，EM算法通常是通过最大化可能的估算量来估算模型参数的算法。

图3A示出一非常详细地说明模型编辑组件202的框图。图3A示出的模型编辑组件202说明性地包括模板语法生成器200、分段EM应用组件302和修剪组件304。模板语法生成器300接收概要206和被概要206中的语义类别所参照的可选语法库209中的任意规则，并生成包括所有规则的模板语法，这些规则可从概要206或可选语法库209中获得或搜集。然后EM分段组件获得模板语法和训练实例(文本串和其它注释)以作为输入。EM分段组件302使用模板语法，以发现训练实例中的分段歧义。然后运行组件302，以消除任何分段歧义。基于这些歧义的消除，可使用修剪组件来从语法中修剪重写规则，以提供基于规则的语法210。

为进一步说明EM分段组件302的运行，图2F和2G提供示范表。图2F展示包括一组实例的表。所展示的第一字词“from”有可能被映射到前终端ShowFlightCmd或前终端FlightPreDepartureCity。组件302可从诸如“from Seattle toBoston”之类的一个实例句子中获得该实例。第二个实例表明字词“Flight from”可被映射到前终端“ShowFlightCmd”和“FlightPreDepatureCity”，其可被组件302从诸如“Flight to Boston on Tuesday”之类的一个实例中同样地获得。然而，实例的分段是有歧义的。换言之，仍然不知道第一实例中的字词“from”是否被映射到前终端ShowFlightCmd或前终端FlightPreDepartureCity。同样，仍然不知道字词“Flight from”如何被映射到前终端ShowFlightCmd和FlightPreDepartureCity之间。另外，当然，也不知道字词“Flight to”如何被映射到可能的前终端前终端ShowFlightCmd和FlightPreArrivalCity。

图2G是进一步说明EM算法应用组件203的操作的表。图3B是说明组件203的操作流程图且和图2F和2G一起被描述。

首先，组件302列举所有可能的分段。这在标有可能重写规则的图2G的左列中展示。在图2G所示的重写规则中，简化能够形成前终端名称的一些字词。因此，例如，重写规则SFCmd->ε表明其中ShowFlightCmd(简化的SFCmd)前终端被映射到一个空集的分段。同样，重写规则SFCmd->from表示其中字词“from”被映射到前终端ShowFlightCmd的分段。此外，重写规则FPDCity->ε表示其中前终端FlightPreDepartureCity(简化的FPDCity)被映射到空集的分段，PFACity->ε表示其中前终端FlightPreArrivalCity(简化的FPACity)被映射到空集的分段。从这些实例中，图2G所示表的重写规则部分的其它符号能够自我解释。完全可以说，列举了图2F所示的实例的每一可能的分段。

根据图2F的第一实例，一个表明字词“from”的分段被映射到ShowFlightCmd，且表明字词“from”的其它分段被映射到FlightPreDepartureCity。

图2F中的第二实例也支持许多不同的分段替换方案。例如，根据一个分段替换方案，字词“Flight from”被映射到前终端ShowFlightCmd，且前终端FlightPreDepartureCity被映射到ε。在另一替换方案中，字词“Flight”和“from”被分离，以使字词“Flight”被映射到前终端ShowFlightCmd，且字词“from”被映射到前终端FlightPreDepartureCity。在图2G所列举的重写规则中也展示了这些分段中的每一个。

能以和第二实例相同的方式来分割第三实例，其中字词“Flight to”可被映射到前终端ShowFlightCmd或前终端FlightPreArrivalCity，而其它前终端被映射到ε，或者可在前终端ShowFlightCmd和前终端FlightPreArrivalCity之间分离字词“Flight to”。此外，在图2G所示的重写规则中表示这些分段。

图3B的流程图中的块306表明了所有可能的分段的列举。

一旦列举了支持分段的重写规则，则它们被一一分配一个概率。最初，图2G中所说明的所有分段被分配相同的概率。这可通过图3B中的块308表明。

接着，基于在图2F所示实例中可能出现的计数，组件302将最新期望的计数分配给所列举的重写规则。这通过块310来指示。例如，根据第一实例，存在两种可能的分段，其中之一将字词“from”映射到ShowFlightCmd且将前终端FlightPreDepartureCity映射到ε，而其中另一个将ShowFlightCmd映射到ε且将字词“from”映射到前终端FlightPreDepartureCity。第一重写规则规定ShowFlightCmd前终端映射到ε(空集)。因此，实例1中一半的分段支持图2G的表中所示的第一重写规则。从而，根据第一实例，第一重写规则(ShowFlightCmd->ε)被分配二分之一的数量。

如上所述，第二实例支持三个不同的分段，其中之一将字词“Flight from”分配给前终端ShowFlightCmd并将前终端FlightPreDepartureCity分配给ε，其中另一个将字词“Flight”映射到前终端ShowFlightCmd并将字词“from”映射到前终端FlightPreDepartureCity，其中最后一个将前终端ShowFlightCmd映射到ε并将字词“Flight from”映射到前终端FlightPreDepartureCity。关于这三种分段，其中之一支持第一重写规则(SFCmd->ε)。因此，根据第二实例，第一重写规则被分配三分之一的数量。

以相同的方式，第三实例具有三种可能的分段，其中之一将前终端ShowFlightCmd映射到ε。因此，根据第三实例，图2中所示的第一重写规则被分配三分之一的数量。

通过这种分析，可知第二重写规则(SFCmd->from)仅仅被第一实例所支持。因此，由于对于第一实例来说存在两种可能的分段，因此其中之一支持第二重写规则，第二重写规则(SFCmd->from)被分配二分之一的数量。

来自图2F所示第二和第三实例的分段中的一种支持第三重写规则(SFCmd->Flight)。因此，由于这些实例中的每一个具有三种可能的分段，第三重写规则(SFCmd->Flight)根据每一实例被分配三分之一的数量。

组件302以这种方式将计数分配给图2G中所列举的每一重写规则，且这些计数在图2G所示的表的第二列中得以被说明。计数都被转换，以使它们具有一个公分母，且它们接着规范化每一前终端，以获得概率。换言之，ShowFlightCmd终端的整个概率集必须被加在一起。因此，每一重写规则的计数乘以一个标准化因数，以获得与重写规则相关的一个概率。

例如，可知前终端ShowFlightCmd的计数总数为3。因此，第一重写规则(SFCmd->ε)的概率为7/18。同样，第二重写规则的概率为3/18等等。为获得概率，组件302为每一重写规则和每一前终端处理计数。

由此可知，对于前终端FPDCity，全部不同规则的计数总和为2，因此标准化因数为1/2。对于最终的前终端FPACity，仅存在一个计数(3*1/3＝1)，因此标准化因数为l。由此可知，组件302将相关于每一重写规则的概率重置为更加准确地反映实例所支持的重写规则的发生的一个数目。图3B中的块312表明为获得新的概率而标准化计数。

组件302重复该过程(重新估算计数并获得新的概率)，直到计数和概率汇合为止。这由块314来指示。例如，为获得第一重写规则的新的计数C，组件302执行等式1，该等式首先找出观察字词“from”的整个似然，“from”给出非终端序列ShowFlightCmd和FPDCity，等式如下：

Eq.1    P(from|ShowFlightCmd FPDCity)

        ＝P(ε|ShowFlightCmd)*P(from|FPDCity)

        +P(from|ShowFlightCmd)*P(ε|FPDCity)

        ＝[(7/18)×(5/12)]+[(3/18)×(5/12)]＝50/216

在该数量之外，将空串对准ShowFlightCmd与将“from”对准FPDCity的分段比例成为新的所期望的计数C：

$>ver>>C>‾>>>(>ϵ>|>cmd>)>>=>>>P>>(>ϵ>|>cmd>)>>*>P>>(>from>|>FPDCity>)>>>>P>>(>from>|>cmdFPDCity>)>>>>>s>$

Eq.2 $>>=>>>>7>18>>\times >>5>12>>>>50>216>>>=>>>35>216>>>50>216>>>=>>35>50>>=>>7>10>>>s>$

同样，如下计算第二重写规则的新的计数C：

Eq.3 $>ver>>C>‾>>>(>from>|>cmd>)>>=>>>P>>(>from>|>cmd>)>>*>P>>(>ϵ>|>FPDCity>)>>>>P>>(>from>|>cmdFDPCity>)>>>>=>>>>3>18>>\times >>5>12>>>>50>216>>>=>>>15>216>>>50>216>>>=>>3>10>>>s>$

该过程继续每一重写规则以从每一实例收集计数C。然后，新的计数乘以标准化因数以获得新的概率。如图3B所示，组件302重复该过程，重新估算新的计数和新的概率，直到概率汇合为止。

一旦完成了重复，组件302将计算与所列举的每一重写规则相关的新的计数和新的概率。同时这对于其本身也是有帮助的，因为其将概率分配给相应于训练期间获得的不同分段的根据规则的每一分段，其不是期望的最终结果。例如，一些分析器不能利用概率。同样，在一些分析组件中，大量规则导致分析器的低效。

因此，根据说明性的实施例，组件302向其中能够剪除规则的剪除组件304提供规则和相关的概率。这由图3B中的块316和318所表示。剪除组件304能以多种不同方式中的一种方式来剪除规则(如块320所示)。例如，剪除组件304可简单地剪除具有低于所期望的阀值的概率的规则。组件304接着将剩余的规则引入基于规则的语法210。

根据另一说明性的实施例，剪除组件304删除除预定的分段数目之外的所有内容，所述分段具有相应于每一实例的较高的似然，并且剪除组件304根据剩余的分段而仅仅将重写规则引入语法。例如，组件304可列举除了似然最高的分段以外的相应于每一实例的所有分段。因此，对于实例1，假定将字词“from”映射到前终端FlightPreDepartureCity的分段具有高于将字词“from”分配给前终端ShowFlightCmd的分段的概率。在这个实例中，删除第二分段(其将“from”映射到ShowFlightCmd)。在这种情况下，支持所选择分段的两个重写规则被添加到语法中。因此，重写规则“SFCmc->ε”和重写规则“FPDCity->from”都被添加到语法中。

同样，可从图2G列举的规则中删除不再被任何实例的最佳分段所支持的规则。从而，由于规则“SFCmd->from”仅仅被已被删除的实例1的分段所支持，因此将其删除。

现在将以更为正式的数学术语来描述这种方式的EM算法的应用。分段歧义分解可定形为寻找一个字词序列w＝w₁，w₂，...，w_n的m块分割π＝α₁，α₂，...，α_m的问题，以使每一块对准序列N＝NT₁，NT₂，...，NT_m中的前终端。块可包括0或更多来自w的字词。

如果我们通过以下等式来模拟π，N和w的连接概率：

Eq.4 $>>P>>(>\pi >,>N>,>w>)>>=>>\Pi >>i>=>1>>m>>P>>(>>NT>1>>\to >>\alpha >i>>)>>>s>$

然后给出N和w，最相似的分段可被包括，作为：

Eq.5

这种分割可通过维特比搜索来发现。从而仅剩的问题为估算每个前终端(或概念)NT和字词序列α的模型参数P(NT->α)。如果训练数据是与每个前终端的字词序列成对的前终端的列表，则这可通过最大似然似然(ML)估算来处理。然而，经由编辑工具而从用户获得的训练实例是说明性的前终端序列和终端序列对。分割或分段是一个隐藏的变量且不为工具所知。

EM算法最初设置模型的参数P_，然后将参数重复修改为P_’，以增加观测D的似然。

为找出该P_’，我们在(6)中定义辅助函数：

Eq.6 $>>Q>>(>>P>>\phi >>>,>>>>|>>P>\phi >>)>>=>>\Sigma >>N>,>w>>>c>>(>N>,>w>)>>>\Sigma >\pi >>>P>\phi >>>(>\pi >|>N>,>w>)>>log>>>>P>>\phi >,>>>>(>\pi >,>N>,>w>)>>>>>P>\phi >>>(>\pi >,>N>,>w>)>>>>>s>$

这是两种模型参数化之间的训练数据的L(D|P_’)-L(D|P_)似然差异的较低范围。根据前终端的所有可能的重写规则的概率总和必须为1的这个约束条件，EM算法通过最大化Q来完全重置参数P_’，以通过新的参数化来最大化增加训练样本似然。因此，对于每一规则NT_α，可通过求解以下等式来获得其新的概率：

Eq.7 $>>>>\partial >>(>Q>>(>>P>>\phi >,>>>|>>P>\phi >>)>>+>\lambda >>(>>\Sigma >\alpha >>>P>>\phi >,>>>>(>NT>\to >\alpha >)>>->1>)>>)>>>>\partial >>P>>\phi >,>>>>(>NT>\to >\alpha >)>>>>=>0>>s>$

$>>Since>>P>>\phi >,>>>>(>\pi >,>N>,>w>)>>=>>\Pi >>NT>,>\alpha >>>>P>>\phi >,>>>>>(>NT>\to >\alpha >)>>>\alpha >>(>NT>\to >\alpha >,>N>,>w>)>>>>,>>s>$

E.8 $>>>>\partial >Q>>(>>P>>\phi >,>>>|>>P>\phi >>)>>>>\partial >>P>>\phi >,>>>>(>NT>\to >\alpha >)>>>>=>>s>$

$>>>\Sigma >>N>,>w>>>c>>(>N>,>w>)>>>\Sigma >\pi >>>>>P>\phi >>>(>N>,>w>)>>c>>(>NT>\to >\alpha >;>\pi >,>N>,>w>)>>>>>P>>\phi >,>>>>(>NT>\to >\alpha >)>>>>=>->\lambda >,>>s>$

因此，概率可被重置为调节标准化因数-1/λ的所期望的计数：

Eq.9 $>>>P>>\phi >,>>>>(>NT>\to >\alpha >)>>=>>s>$

$>>->1>/>\lambda >>\Sigma >>N>,>w>>>c>>(>N>,>w>)>>>\Sigma >s>>>P>\phi >>>(>\pi >|>N>,>w>)>>c>>(>NT>\to >\alpha >;>\pi >,>N>,>w>)>>.>>s>$

为计算所期望的计数，则注意：

Eq.10 $>>>>\partial >>P>\phi >>>(>N>,>w>)>>>>\partial >>P>\phi >>>(>NT>\to >\alpha >)>>>>=>>>\partial >>\Sigma >\pi >>>P>\phi >>>(>\pi >,>N>,>w>)>>>>\partial >>P>\phi >>>(>NT>\to >\alpha >)>>>>>s>$

$>>=>>\Sigma >\pi >>>>c>>(>NT>\to >\alpha >;>\pi >,>N>,>w>)>>>\Pi >>NT>,>\alpha >>>>P>\phi >>>>(>NT>\to >\alpha >)>>>c>>(>NT>\to >\alpha >;>\pi >,>N>.>w>)>>>>>>>P>\phi >>>(>NT>\to >\alpha >)>>>>>s>$

$>>=>>\Sigma >\pi >>>>>P>\phi >>>(>\pi >,>N>,>w>)>>c>>(>NT>\to >\alpha >;>\pi >,>N>,>w>)>>>>>P>\phi >>>(>NT>\to >\alpha >)>>>>>s>$

$>>=>>P>\phi >>>(>N>,>w>)>>>>>\Sigma >\pi >>>P>\phi >>>(>\pi >|>N>,>w>)>>c>>(>NT>\to >\alpha >;>\pi >,>N>,>w>)>>>>>P>\phi >>>(>NT>\to >\alpha >)>>>>>s>$

因此

Eq.11 $>>>\Sigma >\pi >>>P>\phi >>>(>\pi >|>N>,>w>)>>c>>(>NT>\to >\alpha >;>\pi >,>N>,>w>)>>>s>$

$>>=>>>>P>\phi >>>(>NT>\to >\alpha >)>>>>>P>\phi >>>(>N>,>w>)>>>>>>\partial >>P>\phi >>>(>N>,>w>)>>>>\partial >>P>\phi >>>(>NT>\to >\alpha >)>>>>.>>s>$

使E^k_ij＝(N＝＞w₁，...w_n)成为事件，即在重写前终端序列N到字词序列的过程中，规则NT->α被用于N中的第k个前终端，以生成子序列α＝w_i，...w_j，并使λ^t_s(p，q)成为序列N中从位置s到t的前终端覆盖终端字词w_p，...w_q＝1的概率。然后：

Eq.12 $>>>P>\phi >>>(>N>,>w>)>>=>>\Sigma >ij>sup>>E>ij>ksup>>=>>s>$

$>>>\Sigma >y>sup>>\lambda >1>>k>->1>sup>>>(>1>,>i>)>sup>>\lambda >>k>+>1>>msup>>>(>j>+>1>,>n>+>1>)>>>P>\phi >>>(>NT>\to >>w>i>>,>.>.>.>,>>w>j>>)>>>s>$

Eq.13 $>>>>\partial >>P>\phi >>>(>N>,>w>)>>>>\partial >>P>\phi >>>(>>NT>k>>\to >\alpha >)>>>>=>>\Sigma >>ij>=>>w>i>>,>.>.>.>,>>w>j>>>sup>>\lambda >j>>k>->1>sup>>>(>1>,>i>)>sup>>\lambda >>k>+>1>>msup>>>(>j>+>1>,>n>+>1>)>>>s>$

因此如果我们能够计算λt_s^t(p，q)，我们便能结合等式(9)、(11)和(13)以获得所期望的计数并重置模型参数。根据(14)通过动态设计来计算λ^t_s(p，q)的情况下，ε是空串：

Eq.14 $>sup>>\lambda >s>tsup>>>(>p>,>q>)>>=>>\Sigma >>p>\le >r>\le >q>>sup>>\lambda >s>>t>->1>sup>>>(>p>,>r>)>sup>>\lambda >s>tsup>>>(>r>,>q>)>>;>>s>$

注意P_(N，w)＝λ_l^m(1，n+1)可被用于等式(11)中。

图4说明根据本发明一个不同方面的模型编辑组件350的另一实施例。基于规则的语法210仍然较弱且比所期望的要脆弱。例如，假定在训练生成如下规则期间，为模拟如下前终端：

FlightPreArrivalCity->to

ShowFlightCmd->Show me the flight

进一步假定，在运行时间期间，句子输入为“Show flight to Boston”。由于不存在说明“Show flight”是ShowFlightCmd的规则，所以不能理解输入句。

CFG良好工作以适于高分解理解。高分解理解表示将句子分解为大量时间段的语法。时间段的数量越大，语法所展示的分解理解就越高。CFG能在高分解的情况下良好的归纳。

然而，许多应用要求较低的分解理解，其中不存在被填充的大量时间段。例如，在一个命令和控制应用中，一些必须被识别的命令包括“ChangePassword”、“ChangeBackground”和“ChangeLoginPicture”。在这些实例中，不存在被填充的时间段，且整个句子必须作为命令而被识别。在训练期间，这将导致一个如下的规则：

ChangeLoginPictureCmd->Please change my login icon。

由于“ChangeLoginPicture”是一个命令，所以对于规则不存在属性部分。因此，语法学习者以所获得的规则简单地“记忆”整个句子。为识别和调用用于发布的命令，该命令必须在训练数据中匹配一个完整的句子。这里完全不存在普遍性。

本发明的另一实施例在于以模板语法中的规则替代模拟前终端(例如命令、前文和后文)，统计模型(例如一个n字符列)被用于模拟前终端。在一个实施例中，为相应于模板语法中前终端所列举的分段而生成的文本被用作n字符列(或其它统计模型)的训练数据。因此，在上述实例中，相应于前终端所列举的分段的文本串，与EM算法的期望步骤中所收集的其所期望的计数一起，被用于训练前终端的n字符列。因此，文本“Show me the flight”被用作训练数据，以便为模拟ShowFlightCmd前终端而训练一个n字符列。因此，其中带有“Show flight”的句子被识别为ShowFlightCmd的概率可做如下计算：

Eq.15

Pr(<s>showflight</s>|ShowFlightCmd)＝

Pr(show|<s>；ShowFlightCmd)*

Pr(flight|show；ShowFlightCmd)*

Pr(</s>|flight；ShowFlightCmd)

当规则不能将ShowFlightCmd的识别为“show flight”时，Eq.15中的上述n字符列概率将不会为零。由于等式15中的第一因数和第三因数相应于实际存在于训练数据(例如，[<s>show]和[flight,</s>])中的双字母组，因此它们不会为零。第二因数与训练数据中显露的双字母组不一致，但是由于诸如补偿(在下文中被描述)之类的平滑技术，所以其也具有非零概率且可被如下表示：

Eq.16

Pr(flight|show；ShowFlightCmd)＝

Backoff_weight*Pr(flight|ShowFlightCmd)

如所期望那样，可以凭经验或者别的方法来设置补偿位权，由于“flight”是训练数据中的一个字词，所以单字符列概率Pr(flight|ShowFlightCmd)非零。

由于Pr(show flight</s>|ShowFlightCmd)＞0，分析器将输入句看作ShowFlight候选。输入句的最终解释将依赖于与其它候选解释的比较。

所以图4示出模型编辑组件350的另一实施例，该模型编辑组件350编辑包括语法部分210(例如CFG)的复合模型351，语法部分210包括用于模拟时间段和识别前终端(例如命令、前文和后文)的统计模型部分326(例如n字符列)的规则。因此，在运行期间，借助统计模型部分326来估算输入句，以识别前终端，且借助基于规则的语法部分210来估算输入句，以填充时间段。

组件350通过部分地利用上述EM算法技术来训练复合模型351。例如，假定图5根据不同的样本分段来展示所有所列举的ShowFlightCmd的规则。

对于上述和图2-3B相关的模型，在EM算法的E步骤期间，为图5所示的每个所列举的规则而收集所期望的计数。在M步骤期间，标准化计数。然而，对于复合模型351，替代在算法的M步骤期间标准化计数，列举的规则的右侧上的文本串和相应于这些规则的相关的所期望的计数被用作训练数据，以训练和平滑ShowFlightCmd前终端的n字符列。

换言之，在训练n字符列中，不需要为字词序列的每次发生而添加整个计数。作为替代，为字词序列的每次发生而添加相应于与培训句(由图3A中所说明的EM应用组件302所生成)相关的规则所期望的计数的分数数据。

和关于图2-3B而描述分段歧义消除的所述实施例的另一区别包括EM算法的E步骤。作为将概率和每个所列举的规则相结合的替代，规则的概率是规则中所有n字符列的乘积。

例如，在上述基于规则的语法中，规则：

ShowFlightCmd->Show me the flight

具有与其相关的基本概率。然而，在模型组件351中，可如下计算规则的概率：

Eq.17

Pr(ShowFlightCmd->show me the flight)＝

Pr(show|<s>；ShowFlightCmd)*

Pr(me|show；ShowFlightCmd)*

Pr(the|me；ShowFlightCmd)*

Pr(flight|the；ShowFlightCmd)*

Pr(</s>|flight；ShowFlightCmd).

同样，根据本发明的一个实施例，训练前终端的统计模型包括应用平滑算法。例如，由于其仅仅包括与给定的前终端相关的分段所列举的文本串，用于培训前终端的统计模型的培训数据可相对较少。这将留下相对大量的未被统计模型所覆盖的语言表达，且因此致使统计模型相对脆弱。因此，利用低级n字符列和均匀分布来平滑模型概率。换言之，如果统计模型包括一个双字母组，则无论上下文如何，通过向模拟的字词提供概率的单字符列来平滑。另外，通过均匀分布来平滑统计模型，该均匀分布将相同的概率分配给词汇中的每个字词。因此，如果字词处于词汇中，则统计模型将不以零概率来对其模拟。删除的内插被用于寻找平滑操作中的每一模型的位权并线性内插不同次序的模型。

组件350也可根据本发明的不同实施例来训练附加的统计模型组件。这在图6所示的框图中被非常详细地说明。例如，在上述框图中，统计模型部分326被示为不仅包括前终端340的统计模型组件，还包括多个其它统计模型。例如，一个实施例中的统计模型326可包括组件342和344，该组件包括模拟任务的先验概率的统计模型和slot转换的统计模型。

例如，如果运行期，输入句为“Show flight to Boston arriving on Tuesday，11:00a.m.”，则将分析术语“arriving on”，该术语表明“Tuesday”相应于抵达日期。然而，在“11:00 a.m.”之前不存在表明是启程时间还是抵达时间的字词。跟随“arrival date”时间段的“arrival time”时间段的概率将很可能高于跟随“arrivaldate”时间段的“departure time”时间段的概率，时间段转换模型将倾向于“11:00a.m.”和“arrival time”时间段相匹配。还可注意到为模拟时间段转换而训练统计模型(例如n字符列模型)和为模拟时间段的先验概率而训练统计模型(例如n字符列)相同。对于时间段的先验概率，单字符列模型被培训且模拟两个时间段之间的时间段转换，双字母组模型也被训练等等。

并且，一些命令比其它命令更加频繁的出现于训练数据中。因此，在模型342中模拟命令的先验概率。

下面将结合其它实例而十分详细地描述本发明。图7示出概要中的语义类别的一个典型的简化的实例，其中该概要定义语义以用于指定调度命令NewAppt。

图8说明自动生成的模板规则以用于语义类别NewAppt，其中括号中的符号是可选的。图9说明注释句“New meeting with Peter at 5:00”的实施例。图10说明一旦如上述地执行分段歧义消除而被添加的两个规则。

然而，如上所述，纯粹的基于规则的语法缺乏稳固性且表现出脆弱性。因此，本发明的一个方面以n字符列来替代CFG规则，以模拟模板语法中的每个命令、前文和后文以及模拟时间段转换。时间段n字符列约束缺乏前文和后文的时间段的解释。最后得到的模型是统计模型(或HMM)和CFG的复合物。HMM模拟模板规则和n字符列前终端，CFG模拟库语法。

在图11中示出该模型的一个实例。术语“Att”是“Attendee”的一个缩写，“ST”是“StartTime”的一个缩写。发射概率b是前终端从属n字符列(在附图中它们被描述为单字符列，但是高次发射分布将导致高次HMM)，且转换概率a是时间段转换双字母组。来自时间段节点的发射τ是库CFG非终端。根据CFG模型P_CFG而从它们之中生成字词。

在图11所示的模型中，可通过寻找维特比语义类别c和状态序列б来获得输入句s的含义，其中状态序列б满足：

Eq.18 $>>>(>c>,>s>)>>=>>>arg>max>>>(>c>,>s>)>>>P>>(>c>,>s>|>s>)>>=>>>arg>max>>>(>c>,>s>)>>>P>>(>c>,>s>,>s>)>>>s>$

$>>=>>>arg>max>>>(>c>,>s>)>>>P>>>(>c>)>>\prime >>P>>(>s>,>s>|>c>)>>>s>$

新的模型克服了CFG模型的限制。对于低分解理解(任务分类)，没有将属性前终端引入模板语法。因此，所有训练数据被用于训练和平滑命令前终端的n字符列。模型按比例地缩小到等式19所表示的n字符列分类器。

Eq.19 $>ver>>c>‾>>=>>>arg>max>>c>>P>>(>c>)>>P>>(>s>|>c>)>>>s>$

$>>=>>>arg>max>>c>>P>>(>c>)>>>\Pi >i>>P>>(>>w>i>>|>,>>w>>i>->1>>>,>>w>>i>->2>>>,>.>.>.>,>>w>1>>;>cCmd>)>>>s>$

N字符列不要求精确的规则匹配。作为关于规则适用性的二元判定的替代，其比较从状态(前终端)序列生成所观测的字词序列的概率，以找出最可能的解释。因此，模型自身是稳固的且不需要稳固的分析器。

现在就图7-11所示的实例来十分详细地描述训练。为训练模型，EM算法自动分割字词序列并使每一分割α对准相应对的前终端序列中的相应的前终端NT。EM算法建立一个分配概率的模型P(NT-)α)，以便从NT生成字词串，且通过最初的均匀分布而用参数对其进行表示。然后如上说述，其重复地改进参数化。在每一重复中，其根据在先重复(E步骤)中的参数化来计算规则NT->α的所期望的计数，然后通过标准化所期望的计数(M步骤)来再次估算概率P(NT->α)。为训练新的模型，该模型模拟带有n字符列的前终端，在E步骤中收集所期望的计数在M步骤中被用于训练和平滑n字符列；通过EM算法来使用n字符列以便收集用于分段所期望的计数。这导致一种图12所说明的训练算法。

在一说明性的实施例中，图12最后一行中所说明的阈值设置为0.01。当然，也可使用其的阈值。

本发明的其它可选方面也是值得关注的。可选语法库209(如图2A、4和13所示)统计性地适于训练数据208。例如，假定语法库209包括相对较大的城市列表，该列表包括较大和较小的国际和国内城市。然而，进一步假定模型正被训练的这种特定应用仅仅涉及国内城市，且进一步假定诸如纽约和洛杉矶之类的大型国内城市比较小的城市更有可能被涉及。组件202和350获悉与概率性的上下文无关语法(PCFG)相关的概率。例如，其可被获悉规则Cityname->NewYork的概率大于规则Cityname->Tokyo的概率。这能以和所获悉的上述其它概率相同的方式来处理。

图13说明一个运行期系统，该系统使用用于时间段的基于规则的语法部分和前终端的统计模型部分。该系统接收一个输入，并使用语法部分和n字符列部分且输出一个输出402。

就图14来非常详细地描述解码。图14说明一个表示用于输入“new meetingwith Peter at five”的动态设计解码器的动态设计格子结构。

动态设计解码器寻找上述等式18所表示的维特比路径。一旦接收了输入，解码器首先使用自底向上的图表分析器来寻找覆盖一些输入范围的库语法非终端。在该实例中，其将“Peter”识别为<Person>，并将“five”识别为<time>或<num>。然后解码器在第一列(实例仅仅展示语义类别NewAppt)上搜索从语义类别节点启动的格子结构。在每个节点上，在同一列(切换为不同的非终端)中对其它节点进行转换或在同一行(通过非终端来消耗输入字词)中对下一节点进行转换。从左到右继续搜索，直到搜索到合适的大部分列。当其进行转换时，通过将合适的记录概率添加到启动节点的分数中来获得分数。然后将该分数和目的节点的分数相比较，如果新的分数较高，则将其替换。格子结构之下是被图表分析器识别的非终端。粗线路径表示维特比解释。较高的细线路径412识别正确的任务，但不识别时间段。较低的细线路径414(其分享维特比路径410的路径)识别在场者但不识别启动时间时间段。其将“at five”作为在场者的后文来处理。以下为维特比路径410而列举图14所示的每个九分之一的转换的记录概率。

1.log p(NewAppt)                    //Class Prior

2.log b(New|<s>；NewApptCmd)        //Word bigram

3.log b(meeting|new；NewApptCmd)    //Word bigram

4.log b(</s>|meeting；NewApptCmd)+  //Word bigram

  log a(Attendee|<s>；NewAppt)      //Slot bigram

5.log b(with|<s>；PreAttendee)      //Word bigram

6.log b(</s>|with；PreAttendee)     //Word bigram

7.log Pefy(Peter|<Person>)          //PCFG

8.0

9.log b(</s>|<s>；PostAttendee)+    //Word bigram

  log d(StartTime|Attendee；NewAppt)//Slotbigram

可使用任何所期望的修剪机构。例如，一个修剪机构所提供：在格子结构的每一列上，如果其分数比同一列中小于最大分数内的阀值(例如5.0)还要小，则没有从节点中做出转换。换言之，如果其比通向同一列的一个节点的另一个小上10⁵倍，则路径不被扩展。在修剪之后，解码器以稳固的分析器更快的数量级来运行。

根据本发明的一个实施例，复合模型351不仅被用于自然语言理解系统，也可被用于语音识别系统。在这个实施例中，语音识别系统同时执行语音识别和自然语言理解。

图15说明一个在其中使用复合模型351的说明性的语音识别系统500的框图。当然，由于在图15所示的语音识别系统中实现复合模型351，所以系统500也可像执行语音识别一样来执行自然语言理解。在对其非常详细地描述之前，先提供整个操作系统500的一个简要讨论。

在图15中，扬声器510向麦克风504发声。麦克风504所检测到的音频信号被转换为电信号，以提供给模拟——数字(A-to-D)转换器506。

A-to-D转换器506将来自麦克风504的模拟信号转换为一系列数值。在几个实施例中，A-to-D转换器506以每个样本16千赫和16比特来取样模拟信号，从而创建每秒32干字节的语音数据。这些数值被提供给帧构造器507，其在一个实施例中将数值集合成每隔10毫秒启动的25毫秒帧。

帧构造器507所创建的数据帧被提供给特征提取器508，其从每一帧中提取一个特征。例如特征提取模块包括用于执行线性预测编码(LPC)、LPC导出的倒谱、有理解力的线性预测(PLP)、听觉模型特征提取和唛耳频率倒谱系数(MFCC)特征提取的模块。注意本发明不限于这些特征提取模块且其它模块也可被用于本发明的环境中。

特征提取模型508制造和语音信号的帧相关联的特征矢量流。该特征矢量流被提供给解码器512，其基于特征矢量流、词典514、语言模型351和声音模型518来识别最有可能的字词序列。用于解码的特定方法对于本发明而言并不重要。

假定字词的最合适的序列可被提供给可选信用量度模块520。信用量度模块520识别最有可能已被语音识别器不正确地识别的字词。这可部分基于次要声音模型(未示)。然后信用量度模块520联同表明哪些字词已被不正确的识别的标识符一起，向输出模块522提供假定字词序列。熟知本领域的人士可知信用量度模块520对于本发明的实践而言并不是必须的。

在训练期间，相应于训练文本526的语音信号和训练文本526的词汇转录一起被输入给训练者524_[YW1]。训练者524基于训练输入来训练声音模型518。复合语言模型351的训练如上所述。

如上所述，模型351使用统计部分(例如，利用隐藏马尔可夫模型技术而被实施的)来编码应用概要的结构信息，并使用基于规则的部分(例如，利用CFG技术而被实施的)来模拟一些HMM状态的发射。图16——17B说明这种方式的模型拓扑，以方便讨论即使在其解释未现字词的情况下，如何能在一种紧凑方式中以一个有限状态表达来表示该模型。

图16是另一应用概要600的一个说明性的实施例。概要600简单地陈述应用支持两种类型的信息查询：飞行信息(ShowFlight任务)和地面运输信息(GoundTransport任务)。为获得飞行信息，用户必须提供关于抵达城市(Acity)的和/或启程城市(Dcity)时间段的信息，于是系统可根据用户的说明来搜索信息。时间段类型规定其“fillers”的要求。对于Acity和Dcity时间段而言，填充物必须是在语法库中被模拟的一个表达，其中该语法参照“City”类型的对象。

图17A和17B示出一个统计模型部分(一个HMM)，该部分将概要600的语义合并成一种自然语言理解基于规则的语法(例如CFG)。图17A说明具有两个分支的顶级结构602，其中一个分支通向ShowFlight子网络604，另一个分支通向GroundTransport网络606。每一分支的转换位权是两个任务的概率。因此，从S节点到ShowFlight子网络604的转换位权相应于ShowFlight任务(或命令)的概率，而到GroundTransport子网络606的转换概率相应于GroundTraransport任务的概率。

图17B十分详细地说明ShowFlight子网络604，图17C说明子网络模型的用途。图17B所示的ShowFlight子网络模型模拟语义表达式，用户可使用该表达式来发布ShowFlight命令。子网络模型从跟随有时间段的表达式的命令部分(例如“Show me the flight”)开始。每个时间段通过前文和后文而被扩在一起，其起到用于时间段的语言环境的作用。例如，字词“from”是Dcity时间段的前文。其用信号通知随后的City很可能是启程城市。时间段互连，并且为了时间段的传送，用双字母组概率来加权连接，所述双字母组概率根据训练数据来估算。

在子网络模型604中，借助统计的n字符列模型来模拟命令、前文和后文。这些通过子网络模型604中的椭圆部分而得以说明。借助来自语法库的概率性的CFG规则来模拟时间段填充。这些由子网络模型604所示的矩形来说明。利用域特定数据来说明性地调整语法库中的规则的概率且对其进行平滑处理。模型604中的n字符列和被部分标记的训练数据相结合。如上所述，EM算法可被用于在网络中培训N字符列，其中定位被作为隐藏变量。

不同与在先稳固理解技术，其依赖于稳固的分析器以忽略未被语法所覆盖的字词，语法中的前终端的n字符列模型的使用使模型实质上稳固。这启用本发明的一个特征，其不仅将复合模型351(图17A和17B所示的一个实施例)用在自然语言理解中，也用在语音识别中。这克服了被用于在先系统中的不是最理想的双道方法，以便完成语音识别和自然语言理解，且其使用先验知识以使其能比在先系统更好地来说明性地概括。

然而，为识别语音识别系统(例如图15所示的语言模型)中的模型351，模型首先被转换为可被解码器512视作其语言模型的格式。因此，被用于模拟命令、前文和后文(例如，CFG中的那些n字符列)的统计的n字符列模型被转换为概率性的有限状态自动机。所转换的n字符列和顶级HMM结构(例如图17A所示的602)和库语法中的规则一起来形成概率性的上下文无关语法(PCFG)语言模型。该转换基于著名的转换算法，例如在Riccardi，G，等所著的《语言模型的随机自动机》(《计算机语音和语言》，10，第265——293页，1996)中所陈述的转换算法。

然而，为大大减小模型的规模，对转换算法做出重大改动。这由图18A、18B和18C所说明。图18A和18C说明两个前终端的双字母组语言模型的有限状态表达，其中每一个前终端已被结合两个观测字词(分别是所指定的a，b和c，d)。模型中的每个弧的标记说明位权和输出符。字母I表示初始状态，而字母O表示后退状态，字母F表示有限状态。图18B是共享均匀分布的有限状态表示，其被用于将一个后退概率分配给未现字词(例如，未出现在图18A所示的特定n字符列模型的培训数据中的那些字词)。

为说明图18A所示的模型的运行，考虑和字词“a”的发音相关的概率，“a”跟随有字词“b”的发音。这相应于以下概率的结合：

P(a|<s>)：a

P(b|a)：b

Pr(</s>|b)

第一概率是跟随句子符号开始的字词“a”的n字符列概率。这相应于从初始状态I到状态a的转换。第二概率是跟随字词“a”的字词“b”的概率，该概率被标记于从状态a到状态b的转换。第三概率是跟随字词“b”的句子符号的末尾的概率，该概率被标记于从状态b到最终状态F的转换。这种次序转换形成了有限状态机中的一条路径，该有限状态机接受发音“a b”并通过乘上路径中的转换概率来计算发言的概率。

对于训练数据中未被观测的字词序列的发音而言，有限状态机将不对其分配0概率。作为替代，将后退位权和单字符列概率的乘积用作未现事件的双字母组概率，从而一条路径通过后退状态。例如，通过图18A中的以下路径来计算发言“a a”的概率：

I->aP(a|<s>)：a

a->OB(a)：ε

o->aP(a)：a

a-FP(</s>|a)

在这里，即使在训练数据中未观测到双字母组“a a”，P(a|a)＝B(a)*P(a)＞0。

对于在被模拟的特定n字符列的训练数据中未现的字词的发言，如果字词在词汇中，则其被分配一个后退到统一概率1/|V|的概率，其中|V|是词汇大小。在在先系统中，这导致在每一未现字词的后退状态O上的自循环。由于复合模型中的每个n字符列的训练数据可相对稀少，所以和模型相关的词汇中的许多字词在每个n字符列的训练数据中是看不见的。由于模型351将说明性地支持具有大量字词(说明性的几百个)的词汇，且由于该模型也具有大量n字符列(也是说明性的几百个)，所以通过整个复合模型中的后退状态O的自循环的数目也将十分巨大。

因此，根据本发明的一个说明性的实施例，作为为每个未现字词添加循环的替代，复合模型351(例如图18A所示)中的n字符列模型包括一个通过后退状态O的单循环620_[YW1]。单循环620参照一个诸如图18B所示的共享的均匀分布模型。

在图18B所示的均匀分布中，字母n涉及词汇中的大量字词，其中词汇中的w1涉及第一字词“a”；w2涉及第二字词“b”等等。因此，对于每个未现字词，作为在后退状态上的循环的替代，通过标记有在后退状态O上的均匀分布的自循环来大致平滑模型。为复合模型351中的所有n字符列而共享图18B所示的均匀分布模型。每个n字符列仅仅具有一个和图18A所示的循环620相似的循环，其参照图18B所示的均匀分布模型。这在图18C中得以说明。这节省了模型351中的基本数量的空间，其中模型351比在先系统显得更为紧凑。

由此可知，本发明的各个实施例不仅包括前终端的统计模型部分，也包括填充时间段的基于规则的语法部分，且该复合模型被用在语音识别或语音识别和自然语言理解系统的结合中。这实质上减少了与不是最理想的双道系统相关的无效性，且包括语言模型中的先验知识，以补偿语言模型培训数据的缺乏(即定址数据稀少)。组合的方法也减少整个理解出错率。本发明的另一实施例也包括通过参照分离的补偿模型(例如一个均匀分布模型)来平滑n字符列模型，以替代利用越过n字符列中的后退状态的自循环。这减小了显得更加紧凑的模型的大小。

尽管已根据特定的实施例来描述了本发明，然而熟知本领域的人士可知，能在不脱离本发明的精神和范围的情况下在形式和细节上对其进行更改。