词典、分段和语言模型联合优化的系统和迭代方法

专利名称：词典、分段和语言模型联合优化的系统和迭代方法
技术领域：
本发明涉及语言建模，更具体地说涉及词典、文字分段和语言模式联合优化的系统和迭代方法。
背景技术：
近来计算能力和相关技术的发展促进了新一代强大的应用软件的发展，包括web浏览器、字处理和语音识别应用程序。例如，在输入域名的两三个最初字符之后，最新一代的web浏览器预料统一资源定位符(URL)地址输入。字处理器提供改进的拼写和语法检查能力、字预测和语言转换。较新的语音识别应用程序类似地提供具有令人佩服的识别和预测精度的各种特征。为了对终端用户有用，必须基本实时地实现这些特征。为了提供这种性能，许多应用程序依赖树状数据结构来建立简单的语言模型。
简单地说，语言模式测量任意指定句子的似然性。即，语言模型可获取任意条目的序列(文字、字符、字母等)并估计该序列的可能性。建立现有的语言模式的一种常见途径是根据已知的文本语料库(textual corpus)的训练集合，利用前缀树状数据结构建立N-gram(N字母组)语言模型。
前缀树状数据结构(也叫作后缀树或者PAT树)的使用使高级应用程序能够快速遍历语言模型，提供上面描述的基本实时的性能特征。简单地说，N-gram语言模型计数整个文本中在一个串(大小为N的)内特定项目(文字、字符等)的出现次数。计数值被用于计算该项目串的使用概率。通常，tri-gram(N-gram，这里N＝3)方法包括下述步骤(a)把文本语料库分成若干项目(字符、字母、数字等)；(b)根据较小的预定词典和简单的预定分段算法，对所述若干项目(例如字符(C))分段(例如分成词(W))，这里在树状数据结构中各个W被映射成一个或多个C；(c)通过计数字符串的出现次数，根据分离的语料库(corpus)训练语言模型，籍此由前两个词预测一系列词(W1，W2，…WM)的概率P(W1，W2，W3，...WM)≈∏P(Wi|Wi-1，Wi-2)(1)N-gram语言模型在若干方面存在局限。首先，构造前缀树中使用的计数程序非常耗时。从而实际上只能实现较小的N-gram模型(一般为2-gram或者3-gram)。其次，随着N-gram语言模型的串长度(N)的增大，存储前缀树所需的存储器按2N增加。从而，对于大于3(即3-gram)的N-gram来说，存储N-gram语言模型所需的存储器，以及利用较大的N-gram语言模型所需的访问时间非常大。
现有技术的N-gram语言模型倾向于使用固定(较小)的词典，过分简单的分段算法，一般只依赖于前两个单词来预测当前的单词(就3-gram模型而论)。
固定的词典限制了模型选择通用或者专用于任务的最佳单词的能力。如果某一单词不存在于词典中，则就所涉及的模型来说，该单词不存在。从而，较小的词典不可能覆盖预期的语言内容。
分段算法通常较为特别，并且不是以任何统计或语义原理为基础。过于简单的分段算法一般错误地放弃较小的单词而采用较大的单词。从而该模型不能准确地预测包含在语义上可接受的较大字符串内的较小单词。
由于上述限制的结果，使用现有技术词典和分段算法的语言模型往往易于出错。即，在词典或分段阶段中产生的任意错误被传播到整个语言模型内，从而限制了语言模型的准确性和预测属性。
最后，把模型局限于上下文的最多两个在先单词(就3-gram语言模型而论)同样是有限制性的，因为要准确地预测单词的可能性或许需要更多的上下文。语言模型这三方面的局限性通常导致该语言模型的预测质量较差。
从而，需要一种不受通常与现有技术的语言建模技术相关的缺陷和局限性的妨碍，用于词典、分段算法和语言模型联合优化的系统和方法。下面提供恰好如此的一种解决方案。

发明内容
本发明涉及词典、分段和语言模型联合优化的系统和迭代方法。为了克服与现有技术相关的局限性，本发明不依赖于预定的词典或分段算法，相反在优化语言模型的迭代过程中，动态生成词典和分段算法。根据一种实现，提供一种改善语言模型性能的方法，包括根据利用最大匹配技术接收的文本语料库获得的词典和分段形成初始的语言模型，通过按照统计原理动态更新词典并且对文本语料库重新分段，反复精炼初始的语言模型，直到达到预测能力阈值为止。


附图中相同的索引数字被用于代表相同的组件和特征。
图1是体现本发明教导的计算机系统的方框图；图2是根据本发明的一种实现的迭代形成词典、分段和语言模型的例证建模代理的方框图；图3是根据本发明一个方面的DOMM树的图形表示；图4是建立DOMM树的例证方法的流程图；图5是根据本发明教导的用于词典、分段和语言模型联合优化的例证方法的流程图；图6是详细说明根据本发明的一种实现的产生初始词典，并且反复改变动态产生的词典、分段和语言模型，直到会聚为止的方法步骤的流程图；图7是根据本发明备选实施例的具有若干可执行指令的存储介质，所述若干可执行指令当被执行时，实现本发明的创新建模代理。
具体实施例方式
本发明涉及词典、分段和语言模型联合优化的系统和迭代方法。在说明本发明的过程中，引用了创新的语言模型，动态排序Markov模型(DOMM)。在同时待审的Lee等的美国专利申请No.09/XXXXXX，“A Method and Apparatus for Generating andManaging a Language Model Data Structure”中给出DOMM的详细说明，该专利申请的公开内容作为参考包含于此。
在这里的讨论中，在诸如程序模块之类计算机可执行的指令被一个或多个常规计算机执行的一般情况下说明本发明。一般来说，程序模块包括执行特殊任务或实现特定抽象数据类型的例行程序、程序、对象、组件、数据结构等。此外，本领域的技术人员要认识到可利用其它计算机系统结构，包括手持式装置、个人数字助理、多处理器系统、基于微处理器的或可编程的消费电子产品、网络PC、微型计算机、大型计算机等实践本发明。在分布式计算机环境中，程序模块既可位于本地存储装置中又可位于远程存储装置中。但是要指出的是在不脱离本发明的精神和范围的情况下，也可对这里说明的体系结构和方法进行修改。
例证的计算机系统图1图解说明包括根据本发明的教导联合优化词典、分段和语言模型的创新语言建模代理104的例证计算机系统102。要认识到虽然在图1中被描述为单独的应用程序，不过语言建模代理104也可被实现为应用程序，例如字处理器、web浏览器、语音识别系统等的一种功能。此外，虽然被描述为软件应用程序，不过本领域中的技术人员将认识到也可在硬件中实现该创新建模代理，例如可编程的逻辑阵列(PLA)、专用处理器、专用集成电路(ASIC)、微控制器等。
根据下面的说明，显然计算机102是用来代表任意类别的通用或者专用计算平台，所述计算平台当被赋予创新的语言建模代理(LMA)104时，实现根据上面介绍的第一例证实现的本发明的教导。要认识到虽然这里把语言建模代理描述为应用软件，不过计算机系统102可选择地支持LMA 104的硬件实现。在这方面，对于LMA 104的说明，下述计算机系统102的描述仅仅是例证性的，因为在不脱离本发明的精神和范围的情况下，可用性能更好或较弱的计算机系统替换。
如图所示，计算机102包括一个或多个处理器132、系统存储器134和使包括系统存储器134在内的各种系统组件和处理器132耦接的总线136。
总线136代表几种总线结构中的任意一种或者多种总线结构，包括存储器总线或存储器控制器，外围总线，加速图形端口和使用各种总线结构中的任意一种总线结构的处理器或本地总线。系统存储器包括只读存储器(ROM)138和随机存取存储器(RAM)140。包含例如在起动过程中，有助于在计算机102内的元件之间传送信息的基本例程的基本输入/输出系统(BIOS)142保存在ROM 138中。计算机102还包括对硬盘(图中未表示)进行读写的硬盘驱动器144，对可移除的磁盘148读写的磁盘驱动器146，和对诸如CD ROM、DVD ROM或者其它光学介质之类可移除光盘152进行读写的光盘驱动器150。硬盘驱动器144、磁盘驱动器146和光盘驱动器150通过SCSI接口154或者其它一些适当的总线接口与总线136相连。这些驱动器及它们相关的计算机可读介质为计算机102提供计算机可读指令、数据结构、程序模块及其它数据的非易失性存储。
虽然这里描述的例证环境采用硬盘144、可移动的磁盘148和可移动的光盘152，但是本领域的技术人员应认识到在例证的操作环境中也可使用能够保存计算机可存取的数据的其它类型的计算机可读介质，例如盒式磁带、快速存储卡、数字视频盘、随机存取存储器(RAM)只读存储器(ROM)等等。
若干程序模块可保存在硬盘144、磁盘148、光盘152、ROM 138或RAM 140上，包括操作系统158、包括体现本发明教导的创新LMA104在内的一个或多个应用程序160、其它程序模块162和程序数据164(例如最后得到的语言模型数据结构等)。用户可通过诸如键盘166和定点设备168之类的输入装置把命令和信息输入计算机102。其它输入装置(图中未示出)可包括麦克风、操纵杆、游戏垫、碟形卫星天线、扫描仪等等。这些及其它输入装置通过与总线136耦接的接口170与处理器132连接。监视器172或者其它类型的显示装置也通过诸如视频适配器174之类的接口与总线136相连。除了监视器172之外，个人计算机通常包括诸如扬声器和打印机之类的其它外围输出装置(图中未示出)。
如图所示，计算机102在利用与一个或多个远程计算机，例如远程计算机176的逻辑连接的网络化环境中工作。远程计算机176可以是另一个人计算机、个人数字助理、服务器、路由器或者其它网络设备、网络“瘦客户机(thin-client)”PC、对等设备或者其它常见网络节点，并且一般包括上面相对于计算机102说明的一些或者所有元件，不过在图1中只图解表示了存储器178。
如图所示，图1中描述的逻辑连接包括局域网(LAN)180和广域网(WAN)182。在办公室、企业范围计算机网络、企业内部互联网和因特网中这种网络化环境很平常。在一个实施例中，远程计算机176执行诸如由Washington，Redmond的Microsoft Corporation生产并供销的“Internet Explorer”之类的因特网Web浏览器程序，以便访问并利用在线服务。
当用在LAN网络环境中时，计算机102通过网络接口或适配器184与局域网180相连。当用在WAN网络环境中时，计算机102一般包括与诸如因特网之类的广域网182建立通信的调制解调器186或者其它装置。调制解调器186(可以是内置的也可以是外置的)通过输入/输出(I/O)接口156与总线136相连。除了网络连通性之外，I/O接口156还支持一个或多个打印机188。在网络化环境中，相对于个人计算机102或其各个部分说明的程序模块可保存在远程存储器中。要认识到所表示的网络连接是例证性的，可使用在计算机之间建立通信连接的其它手段。
一般来说，借助在不同时间保存到计算机的各种计算机可读存储介质中的指令对计算机102的数据处理器编程。程序和操作系统一般分布在例如软盘或CD-ROM上。程序和操作系统从软盘或CD-ROM上被安装或者加载到计算机的辅助存储器中。执行时，它们至少被部分加载到计算机的主电子存储器中。当这些及其它各种类型的计算机可读存储介质和微处理器或者其它数据处理器一起包含实现下面说明的创新步骤的指令或程序时，这里描述的发明包括这样的计算机可读存储介质。当计算机本身按照下面说明的方法和技术编程时，本发明还包括该计算机。此外，可对计算机的某些子部件编程，以便执行下面描述的功能和步骤。当按照所述对这些子部件编程时，本发明还包括这样的子部件。另外，这里描述的发明包括下面说明的包含在各种存储介质上的数据结构。
为了便于说明，这里把程序和其它可执行的程序组件，例如操作系统表示为分离的程序块，不过要认识到这样的程序和组件在不同时候驻留在计算机的不同存储部件上，并且由计算机的数据处理器执行。
例证的语言建模代理图2图解说明体现本发明教导的例证语言建模代理(LMA)(104)的方框图。如图所示，语言建模代理104由一个或多个控制器202、创新的分析引擎204、存储器206和可选的一个或多个辅助应用程序(例如图形用户界面、预测应用程序、验证应用程序、估计应用程序等)208组成。它们如图所示通过通信相连。要认识到虽然在图2中被描述成若干不同的部分，不过LMA 104的一个或多个功能元件也可结合在一起。在这方面，在不脱离本发明的精神和范围的情况下，可采用更复杂或者较简单的迭代联合优化动态词典、分段和语言模型的建模代理。
如上间接所示，虽然被描述成单独的功能元件，LMA 104也可被实现成更高级应用程序，例如字处理器、web浏览器、语音识别系统或者语言转换系统的一种功能。在这方面，LMA 104的控制器202对来自父应用程序的一个或多个指示命令作出反应，有选择地调用LMA104的特征。另一方面，LMA 104也可被实现为单独的语言建模工具，向用户提供有选择地实现下面所述的LMA 104的特征的用户界面(208)。
在任一种情况下，LMA 104的控制器202有选择地调用分析引擎204的一个或多个功能，从而根据动态产生的词典和分段算法优化语言模型。从而除了被配置成实现本发明的教导之外，控制器202用来代表本领域中已知的若干备选控制系统中的任意一种控制系统，包括(但不局限于)微处理器、可编程的逻辑阵列(PLA)、微型机、专用集成电路(ASIC)等等。在备选实现中，控制器202用来代表实现上述控制逻辑的一系列可执行的指令。
如图所示，创新的分析引擎204由Markov概率计算器212、包括频率计算子例程213、动态词典生成子例程214和动态分段子例程216的数据结构生成器210及数据结构存储管理器218构成。当接收外部指示时，控制器202有选择地调用分析引擎204的某一实例形成、修改并优化统计语言模型(SLM)。更具体地说，和现有的语言建模技术相反，分析引擎204基本根据文本语料库(例如一组或多组文本)的单个项目(例如字符、字母、数字等)之间的Markov转移概率产生统计语言模型数据结构。此外，如同将说明的一样，分析引擎204利用尽可能多的数据(称为“语境(context)”或“排序(order)”)来计算项目串的概率。在这方面，本发明的语言模型被恰如其分地称为动态排序Markov模型(DOMM)。
当被控制器202调用以建立DOMM数据结构时，分析引擎204有选择地调用数据结构生成器210。作为响应，数据结构生成器210建立由若干节点(与若干项目中的各个项目相关)组成，并且表示节点间的从属性的树状数据结构。如上所述，这里把树状数据结构称为DOMM数据结构或者DOMM树。控制器202接收文本语料库，并且至少把文本语料库的一个子集作为动态训练集合222保存到存储器206中，将根据动态训练集合222产生语言模型。要认识到在备选实施例中，也可使用预定的训练集合。
一旦收到动态训练集合，频率计算子例程213至少取回训练集合222的一个子集以供分析。频率计算子例程213确定训练集合子集中各个项目(字符、字母、数字、单词等)的出现频率。根据节点间的从属性，数据结构生成器210把各个项目分配给DOMM树的适当节点，并有频率值(Ci)的指示和比较位(bi)。
Markov概率计算器212根据相关项目的语境(j)计算项目(字符、字母、数字等)的概率。更具体地说，根据本发明的教导，特定项目的Markov概率(Ci)依赖于数据“允许”的尽可能多的在先字符，换句话说P(C1，C2，C3，...，CN)≈∏P(CI|CI-1，CI-2，CI-3，...，CJ) (2)Markov概率计算器212用作语境(j)的字符数不同于字符Ci，Ci-1，Ci-2，Ci-3等的各个序列的“动态”数量。根据一种实现，Markov概率计算器212计算的依赖于语境(j)的字符数至少部分取决于各个字符的频率值，即它们在整个文本语料库内出现的比率。更具体地说，如果在确定文本语料库的项目的情况下，Markov概率计算器212至少不确定特定项目的最小出现频率，则由于与统计不相关，可能从树状数据结构中将其剪除(即排除)。根据一个实施例，最低频率阈值为三(3)。
如上间接所示，分析引擎204不依赖固定词典或者简单的分段算法(它们均易于出错)。相反，分析引擎204有选择地调用动态分段子例程216把项目(例如字符或字母)分成串(例如单词)。更准确地说，分段子例程216把训练集合222分成子集(大块)，并且计算内聚度(即子集内项目间的相似性的一种量度)。分段子例程216反复进行分段及内聚性计算，直到各个子集的内聚度达到预定阈值为止。
词典生成子例程214被调用，从而动态生成词典220并将其保存到存储器206中。根据一种实现，词典生成子例程214分析分段结果，并根据Markov转移概率超过阈值的项目串产生词典。在这方面，词典生成子例程214根据超过从由分析引擎204产生的一个或多个语言模型获得的预定Markov转移概率的项目串产生动态词典220。因此，不同于依赖于易于出错的已知固定词典的现有语言模型，分析引擎204根据在一段时间内形成的一个或多个语言模型，产生统计意义更重要、统计准确的项目串的词典。根据一个实施例，词典220包括在形成后续语言模型中，Markov概率计算器212所依赖的“虚拟语料库”(除动态训练集合之外)。
当被调用从而修改或利用DOMM语言模型数据结构时，分析引擎204有选择地调用数据结构存储管理器218的一个实例。根据本发明的一个方面，数据结构存储管理器218利用系统存储器及扩展存储器保存DOMM数据结构。更具体地说，如下下面将参考图6和7更详细说明的那样，数据结构存储管理器218采用WriteNode子例程和ReadNote子例程(图中未示出)把最近使用的DOMM数据结构的节点子集保存到系统存储器206的一级高速缓冲存储器224中，同时把最近很少使用的节点转移到扩展存储器(例如硬盘驱动器144或者某些远程驱动器中的磁盘文件)中，从而提供改进的性能特征。另外，系统存储器206的二级高速缓冲存储器被用于集合写入命令，直到达到预定的阈值为止，在该阈值点，数据结构存储管理器向存储器中的适当位置发出一个集合WriteNode命令。虽然被描述成独立的功能元件，不过本领域的技术人员将认识到在不脱离本发明的精神和范围的情况下，数据结构存储管理器218也可被组合成控制器202的功能元件。
例证的数据结构-动态排序Markov模型(DOMM)树图3表示根据本发明教导的例证动态排序Markov模型树状数据结构300的原理图。为了从原理上说明DOMM树状数据结构300是如何构成的，图3给出了由英文字母表，即A、B、C、…Z形成的语言模型的例证DOMM数据结构300。如图所示，DOMM树300包括一个或多个根节点302和一个或多个从属节点304，这些节点与文本语料库的一个项目(字符、字母、数字、单词等)相关，并被逻辑连接以表示节点之间的从属性。根据本发明的一个实现，根节点302由一个项目和一个频率值(例如该项目在文本语料库中出现多少次的计数值)组成。在根节点层302下的某一层，从属节点被布置成二叉子树，其中每个节点包括一个比较位(bi)，该节点与之相关的项目(A、B、…)和该项目的频率值(CN)。
从而，从与项目B 306相关的根节点开始，二叉子树由表示节点之间的关系的从属节点308-318及它们的出现频率组成。给定该原理性例子，应认识到从根节点，例如节点306开始，DOMM树的搜索复杂性接近log(N)，N是要搜索的节点的总数。
如上间接所示，DOMM树300的大小可超过LMA 104的存储器206和/或计算机系统102的主存储器中的可用空间。因此，数据结构存储管理器218便于跨越主存储器(例如140和/或260)把DOMM树数据结构300保存到扩展的存储空间，例如诸如计算机系统102的硬盘驱动器144之类主存储装置上的磁盘文件中。
例证的操作和实现已参考图1-3介绍了本发明的功能和概念元件，下面将参考图5-10说明创新的语言建模代理104的操作。
建立DOMM树数据结构图4是根据本发明的一方面，建立动态排序Markov模型(DOMM)的例证方法的流程图。如上间接所示，语言建模代理104可直接被用户或高级应用程序调用。作为响应，LMA 104的控制器202有选择地调用分析引擎204的一个实例，文本语料库(例如一个或多个文档)作为动态训练集合222被加载到存储器206中，并被分成子集(例如句子，诗句等)，方框402。作为响应，数据结构生成器210把该子集的各个项目分配给数据结构中的节点，并计算该项目的频率值，方框404。根据一种实现，一旦数据结构生成器已利用该子集填充该数据结构，则调用频率计算子例程213确定训练集合子集内各个项目的出现频率。
在方框406中，数据结构生成器确定是否存在训练集合的其它子集，如果是，则在方框408读取下一子集，并在方框404继续该过程。在备选实现中，在调用频率计算子例程213之前，数据结构生成器210每次一个子集地填充该数据结构。在备选实施例中，频率计算子例程只计数当其被放入数据结构的相关节点时的各个项目。
如果在方框406中，数据结构生成器210已完全给数据结构300加上训练集合222的各个项目，则数据结构生成器210可随意地删除数据结构，方框410。可采用若干种机制删除作为结果得到的数据结构300。
词典、分段和语言模型联合优化的例证方法图5是根据本发明教导的词典、分段和语言模型联合优化的例证方法的流程图。如图所示，该方法开始于方框400，在方框400中，调用LM 104，并且建立至少接收的文本语料库的一个子集的前缀树。更具体地说，如图4中所示，建模代理104的数据结构生成器210分析接收的文本语料库，并且至少选择一个子集作为训练集合，根据该训练集合建立DOMM树。
在方框502中，根据前缀树建立一个很大的词典，对该词典进行预处理，从而除去某些明显不合逻辑的单词。更具体地说，调用词典生成子例程214，根据前缀树建立初始词典。根据一种实现，利用其长度小于某一预定值，比方说十(10)个项目的所有子串(即从根节点到最大的从属节点，该子串为10个节点或小于10个节点)，根据前缀树建立初始词典。一旦汇编完成初始词典，词典生成子例程214通过删除某些明显不合逻辑的单词精减该词典(例如参见下面的方框604)。根据一种实现，词典生成子例程214把至少根据接收的文本语料库的训练集合产生的新的初始词典附加到预定的词典上。
在方框504中，利用初始词典至少对接收的文本语料库的训练集合分段。更具体地说，调用动态分段子例程216至少对接收的文本语料库的训练集合分段，产生初始的分段文本语料库。本领域的技术人员将认识到存在各种对训练文本语料库分段的方法，例如固定长度分段，最大匹配等等。为此在还没有根据接收的文本语料库产生统计语言模型(SLM)的情况下，动态分段子例程216利用最大匹配技术提供初始的分段文本语料库。因此，分段子例程216开始于项目串(或者DOMM树的分支)的起点，并且搜索词典，查看初始的项目(I1)是否是一个(one-item)“单词”。分段子例程随后把该项目与串中的下一项目进行组合，以了解在该词典中是否以“单词”的形式找到组合结果(例如I1I2)，依次类推。根据一种实现，在词典中找到的项目的最长串(I1，I2，…IN)被认为是该串的正确分段。要认识到在不脱离本发明的精神和范围的情况下，分段子例程216可利用更复杂的最大匹配算法。
在根据训练文本语料库形成初始词典和分段之后，进入迭代过程，其中词典、分段和语言模型被联合优化，方框506。更具体地说，如同下面将更详细说明的那样，创新的迭代优化采用统计语言建模方法动态调整分段和词典，从而提供优化的语言模型。即，不同于现有的语言建模技术，建模代理104不依赖于预定的静态词典，或者过分简单的分段算法来产生语言模型。相反，建模代理104利用接收的文本语料库，或者至少利用接收的文本语料库的一个子集(训练集合)动态产生词典和分段，从而产生优化的语言模型。在这方面，建模代理104产生的语言模型不存在通常和现有的建模系统相关的缺陷和局限性。
在已介绍图5中的创新过程之后，图6根据本发明的一种实现，给出产生初始词典的更详细的流程图，以及提炼词典和分段从而优化语言模型的迭代过程。如前面一样，该方法开始于根据接收的文本语料库建立前缀树的步骤400(图4)。如上所述，可利用整个文本语料库，或者利用整体文本语料库的一个子集(称为训练语料库)建立前缀树。
在方框502中，产生初始词典的过程开始于方框602，其中词典生成子例程214通过识别具有小于预定数目的项目的子串(或者前缀树的分支)，根据前缀树产生初始词典。根据一种实现，词典生成子例程214确定十(10)个项目或者少于10个项目的子串，从而构成初始词典。在方框604中，词典生成子例程214针对显然不合逻辑的子串分析在步骤602中产生的初始词典，从初始词典中除去这些子串。即，词典生成子例程214分析初始词典子串中不合逻辑的或者不可能的单词，并从词典中除去这些单词。对于初始删减来说，调用动态分段子例程216至少对接收的文本语料库的训练集合分段，产生分段的语料库。根据一种实现，最大匹配算法被用于根据初始词典进行分段。随后调用频率分析子例程213，计算词典中各个单词在接收的文本语料库中的出现频率，并且按照出现频率对词典分类。确定频率最低的单词并从词典中删除该单词。可根据语料库的大小确定删除和重新分段的阈值。根据一种实现，600M项目的语料库可利用500的频率阈值被包含在该词典内。这样，可从初始词典中删除绝大多数明显不合逻辑的单词。
一旦在步骤502产生并删减初始词典，则至少部分根据初始词典对接收的文本语料库分段，方框504。如上所述，根据一种实现，利用最大匹配方法完成文本语料库的初始分段。
一旦完成初始词典和文本语料库分段过程，则动态改变词典和分段的迭代过程开始根据接收的文本语料库(或者训练集合)优化统计语言模型(SLM)，方框506。如图所示，该程序开始于方框606，其中Markov概率计算器212利用初始词典和分段开始使用分段文本语料库进行语言模型训练。即，给定初始词典和初始分段，可由其产生统计语言模型。应注意虽然语言模型没有得益于精炼的词典和基于统计的分段(这将演变成下面的步骤)，但是语言模型基本上是以接收的文本语料库自身为基础的。从而，虽然初始的语言模型。
在方框608中，在已进行初始语言模型训练之后，利用基于SLM的分段对分段的文本语料库(或者训练集合)重新分段。已知句子w1，w2，…wn的情况下，存在M种对其分段的可能途径(M≥1)。动态分段子例程216根据N-gram统计语言模型，计算各个分段(Si)的概率(pi)。根据一种实现，分段子例程216利用tri-gram(即N＝3)统计语言模型确定任意给定分段的概率。采用Viterbi搜索算法找出最可能的分段Sk，这里Sk＝arg max(pi) (3)在方框610中，利用由上述基于SLM的分段得到的重新分段的文本语料库更新词典。根据一种实现，建模代理104调用频率分配子例程213计算词典中各个单词在接收的文本语料库中的出现频率，按照出现频率对词典分类。确定频率最低的单词，并将其从词典中删除。随后当重新计算所有这些单词的单一计数时，必须把该单词的所有出现重新分成较小的单词。可根据语料库的大小确定这种删除和重新分段的阈值。根据一种实现，600M项目的语料库可利用为500的频率阈值被包含在该词典内。
在方框612中，更新语言模型，以反映动态产生的词典和基于SLM的分段，Markov概率计算器212计算语言模型混乱性的量度(即相反的概率量度)。如果混乱性继续会聚(趋近0)，即得到改善，则在方框608继续该程序，在方框608中，在有意进一步改善语言模型性能(以混乱性量度)的情况下，再一次修改词典和分段。如果在方框614中确定对词典和分段的新近修改没有改善语言模型，则在方框616进一步确定混乱性是否已达到可接受的阈值。如果是，则该程序终止。
但是如果语言模型还未达到可接受的混乱性阈值，则在方框608，词典生成子例程214从词典中删除在语料库中出现频率最低的单词，在方框618把该单词重新分成更小的单词，程序继续进行到方框610。
根据上述说明，要认识到以在统计上至少基于接收语料库的子集的动态生成的词典和分段规则作为前提，创新的语言建模代理104产生优化的语言模型。在这方面，和现有的语言模型相比，最后得到的语言模型具有改进的计算和预测能力。
备选实施例图7是根据本发明另一实施例的其上存储有若干指令，包括实现本发明的创新建模代理的指令的存储介质的方框图。一般来说，图7图解说明了具有存储于其上的若干可执行的指令702的存储介质/装置700，所述可执行的指令702至少包括当被执行时，实现本发明的创新建模代理104的指令的一个子集。当被主系统的处理器执行时，可执行的指令702实现建模代理，产生供在主系统上执行或者以其它方式适用于主系统的其它应用程序的任意主机使用的文本语料库的统计语言模型表示。
这里使用的存储介质700是用来代表本领域的技术人员已知的若干存储装置和/或存储介质中的任意一种，例如易失性存储装置、非易失性存储装置、磁性存储介质、光学存储介质等等。类似地，可执行的指令是用来反映本领域中已知的若干软件语言中的任意一种，例如C++、Visual Basic、超文本链接标示语言(HTML)、Java、扩展标示语言(XML)等等。此外，要认识到存储介质/装置700不必和任意主系统协同定位。即，存储介质/装置700可驻留在与执行系统通信耦接，并且可被执行系统访问的远程服务器内。因此，图7的软件实现应被看作是例证性的，因为可以预料备选的存储介质和软件实现在本发明的精神和范围内。
虽然已在特定于结构特征和/或方法步骤的语言方面说明了本发明，但是要明白在附加的权利要求中限定的本发明不必局限于所说明的具体特征或步骤。相反，只是作为实现要求权利的发明的例证形式公开了这些具体的特征和步骤。
权利要求
1.一种方法，包括根据由接收的语料库获得的词典和分段形成初始的语言模型；和通过根据统计原理，动态地更新词典和对语料库重新分段，反复精炼初始语言模型，直到达到预测能力阈值为止。
2.按照权利要求1所述的方法，其中建立初始的语言模型的步骤包括根据从接收的语料库分解的项目生成前缀树数据结构；根据前缀树数据结构确定N个项目或小于N个项目的子串；利用确定的子串填充所述词典。
3.按照权利要求2所述的方法，其中N等于3。
4.按照权利要求1所述的方法，其中迭代改进初始语言模型的步骤包括通过确定各个分段的出现概率，对所述语料库重新分段。
5.按照权利要求4所述的方法，其中利用N-gram语言模型计算确定分段的出现概率。
6.按照权利要求5所述的方法，其中N-grim语言模型是3-gram语言模型。
7.按照权利要求4所述的方法，其中利用两个在先分段计算确定分段的出现概率。
8.按照权利要求4所述的方法，其中迭代改进语言模型的步骤包括根据重新分段的语料库更新词典。
9.按照权利要求8所述的方法，其中更新词典包括确定词典的各个单词在接收的语料库中的出现频率；和从词典中删除所确定的频率最低的单词。
10.按照权利要求9所述的方法，还包括把删除的单词重新分成两个或更多的较小单词，并且利用重新分段的单词更新词典。
11.按照权利要求8所述的方法，还包括利用更新的词典和重新分段的语料库，计算语言模型的预测量度。
12.按照权利要求11所述的方法，其中预测量度是语言模型混乱性。
13.按照权利要求11所述的方法，还包括确定由于更新和重新分段的结果，语言模型的预测能力是否被改善；和如果预测能力被改善，则进行另外的更新和重新分段，直到确定没有进一步的改进为止。
14.按照权利要求1所述的方法，其中利用最大匹配技术得到初始语言模型。
15.按照权利要求1所述的方法，其中预测能力被量化表述为混乱性量度。
16.按照权利要求15所述的方法，其中改进语言模型，直到混乱性量度被降低到低于可接受的预测阈值为止。
17.按照权利要求1所述的方法，还包括在应用程序中利用反复改进的语言模型预测另一语料库的可能性。
18.按照权利要求17所述的方法，其中所述应用程序是拼写和/或语法检查器、字处理应用程序、语言翻译应用程序、语音识别应用程序等的一种或多种。
19.一种包括若干可执行指令的存储介质，所述可执行指令至少包括当被执行时，实现按照权利要求1所述的方法的指令子集。
20.一种计算机系统，包括其中保存若干可执行指令的存储装置；与所述存储装置耦接，至少执行所述若干可执行指令的指令子集，从而实现按照权利要求1所述的方法的执行单元。
21.一种包括若干可执行指令的存储介质，所述可执行指令至少包括当被执行时，实现语言建模代理的指令子集，所述语言建模代理包括根据由接收的语料库得到的词典和分段建立初始语言模型的子例程，以及通过根据统计原理动态更新词典并且对语料库重新分段，反复改进初始语言模型，直到达到预测能力的阈值为止的子例程。
22.按照权利要求21所述的存储介质，其中语言建模代理利用混乱性量度量化确定预测能力。
23.按照权利要求21所述的存储介质，其中语言建模代理利用最大匹配技术，由接收的语料库获得词典和分段。
24.按照权利要求21所述的存储介质，其中建立初始语言模型的子例程根据从接收的语料库分解的项目生成前缀树数据结构，根据前缀树确定N个项目或少于N个项目的子串，并且利用确定的子串填充词典。
25.按照权利要求21所述的存储介质，其中子例程通过确定各个分段的出现频率，反复改进初始语言模型，并对语料库进行重新分段，以反映改进的分段概率。
26.按照权利要求25所述的存储介质，其中语言建模代理利用隐藏的Markov概率量度确定各个分段的出现概率。
27.按照权利要求19所述的存储介质，还包括至少当被执行时，通过利用由语言建模代理建立的语言模型实现应用程序的指令子集。
28.一种系统，包括可拆卸地安放按照权利要求19所述的存储介质的存储介质驱动器；和与所述存储介质驱动器耦接，至少访问并执行驻留在可拆卸地安放的存储介质上的若干可执行指令的指令子集，从而实现语言建模代理的执行单元。
29.一种建模代理，包括确定语料库分段的似然性的统计计算器；和一个数据结构生成器，根据由接收的语料库动态获得的词典和分段建立初始语言模型，并且反复改进语言模型，直到语料库分段的似然性达到可接受的阈值为止。
30.按照权利要求29所述的建模代理，其中统计计算器利用Markov建模技术确定语料库分段的似然性。
31.按照权利要求29所述的建模代理，其中数据结构生成器根据从接收的语料库分解的项目生成前缀树数据结构，根据前缀树确定N个项目或小于N个项目的子串，并且利用确定的子串填充词典。
32.按照权利要求31所述的建模代理，其中统计计算器确定被确定的子串的似然性，其中建模代理对语料库重新分段，试图提高子串似然性。
全文摘要
提供一种优化语言模型的方法,包括利用最大匹配技术,根据由接收的语料库获得的词典和分段建立初始语言模型,并且通过根据统计原理,动态更新词典和对语料库进行重新分段,反复改进初始语言模型,直到达到预测能力的阈值为止。
文档编号G10L15/06GK1387651SQ00815294
公开日2002年12月25日 申请日期2000年11月3日 优先权日1999年11月5日
发明者王海峰, 黄常宁, 李凯夫, 狄硕, 蔡东峰, 秦立峰, 郭建峰 申请人:微软公司