将文本输入与词汇知识库相匹配并利用匹配结果的系统和方法

摘要

本发明可以被用于自然语言处理系统(100)中，以确定两个文本段之间的关系(例如，含义类似)。可以根据从文本段被生成的逻辑图表(例如，图3B、3C)来识别或确定该关系。确定第一个逻辑图表与第二个逻辑图表(图3B、3C)之间的关系。不管第一个逻辑图表与第二个逻辑图表(图3B、3C)之间是否有确切的匹配，都可以实现这一点。在一个实施例中，第一个图表(图3B)表示输入文本演讲单元。在一个实施例中，第二个图表(图3C)表示词汇知识库(LKB)(106)中的信息。即使输入图表和第二个图表在词汇或结构上有所不同，如果它们具有类似的含义，则两者也可以相互匹配。

说明书

技术领域

本发明针对用于确定文本的两个部分之间的关系(例如，含义类似)的一种系统和方法。尤其是，本发明涉及将文本输入与词汇知识库的一个部分相匹配以及利用该匹配。

背景技术

当前正在开发的许多应用程序领域尝试“理解”文本输入的含义。这类领域的例子包括信息检索、机器翻译、对话界面与用户界面，以及自然语言处理。例如，当信息检索系统的用户输入询问时，信息检索系统能确切地将询问中的单词与正在被搜索的数据库中的单词进行匹配，而且理解询问的含义，使得它在可能不使用完全相同词的情况能够识别与该含义有关的文档，这是很有益的。

同样，在机器翻译系统中，一些单词或短语没有被确切地从一种语言翻译成另一种语言。在那些情况下，翻译系统能理解将被翻译的文本的含义使得实现更加准确的翻译，也将是很有益的。

在对话界面或用户界面中，一些计算机尝试接收自然语言输入(或者，口头说出，在这种情况下，也利用语音识别部件；或者，采用手写或打字的形式)，识别该输入，并根据该输入来采取指定的行动。当然，有各种各样可以从不同的用户那里被接收的输入，这些输入都意味着同一个事物。所以，自然语言处理技术的这项和许多其他的应用程序可以从理解文本输入的含义中获益。

理解文本输入的含义非常有用，然而，该行业在尝试开发这类系统方面面临许多问题。

第一个问题涉及解释的识别。要充分理解被输入的文本，以便即使“意味着同一个事物”的各个文本段可能不是正好共享内容单词或句法结构，也能够识别它们之间的解释的关系，系统在这方面遇到很大的困难。

与解释的识别密切相关的一个问题是：词义解疑。几乎所有单词都是多义的，在某种程度上，它们根据其被使用的上下文而具有不同的含义。根据上下文中微妙的变化，这些不同的含义经常被排列在一个连续统上，所以一个含义与另一个含义相互混合。词义解疑涉及将一个或多个意思分配给言词中的一个模棱两可的单词。解决词义解疑的传统方法是为每个多义词创建许多“桶”，每个桶被标注有单独的意思号码。一旦创建了这些桶，分析器就根据许多预定的标准来尝试将文本输入中的单词放在给定的桶中。这个策略在诸如信息检索和机器翻译的应用程序方面遇到很大困难，因为(1)单词的使用不总是符合这些离散的桶和(2)解疑技术进展情况十分不可靠。

另一个有关的问题是：要求允许软件应用程序开发者可以容易地将其应用程序定制成接受自然语言输入，以便能够实现对话界面。传统上，这类开发者只尝试过考虑用户可以规定或要求应用程序功能的每种可能的方法。当用户输入被接收时，系统尝试将该用户输入与由开发者开发的各种可能的方法中的一种方法进行匹配。将自然语言匹配入程序功能的问题是一个根本的问题。但是，即使知道它的重要性，开发者也无法完全地规定用户可能用来命令应用程序的言词的广泛范围以及这些言词应该如何映射入功能调用。

过去一直被用于解释的识别的一些方法论包括基于词典的系统、基于例子的系统和基于主体的系统。基于词典的工作主要着重于根据机器可读词典来创建词汇知识库，尤其是分类学。大多数基于例子的研究的目的一直是：创建大型例库或示例关系或短语的集合，以及开发用于将引入的文本与所存储的例子进行匹配的方法。基于主体的研究致力于使用对文本主体的定量分析来开发单词之间的关系的统计模型(包括简单的共同发生和更深入的类似性关系)。

发明内容

可以在自然语言处理系统中使用本发明，来获得对文本输入段的理解或识别两个文本段之间的关系(例如，含义类似)。文本段可以由逻辑图表来表示。即使两个逻辑图表之间的匹配不精确，只要它们被确定为类似，就可以将它们识别为匹配。

例如，在一个实施例中，第一个图表表示文本输入段，第二个图表表示词汇知识库(LKB)中的信息。

不管第一个逻辑图表与第二个逻辑图表之间是否有精确的匹配，都可以确定第一个逻辑图表与第二个逻辑图表之间的关系。即使被输入的图表和第二个图表在词汇或结构上有所不同，两者也可以相互匹配。根据这两个图表中的各个单词与各种关系之间的关系(例如，类似性)来识别不精确的匹配。

附图说明

图1是可以在其中使用本发明的一种计算机系统的方框图。

图2A是根据本发明的一个方面的简化方框图。

图2B是流程图，展示了根据本发明的一个方面的，图2A中所示的系统的操作。

图2C是流程图，展示了获得当前已知的词汇知识库的一个实施例。

图2D是反向的语义关系结构。

图2E是简化图表，展示了根据本发明的一个实施例的词汇知识库的一个部分。

图3A是一幅更加详细的方框图，展示了根据本发明的一个方面的、图2A中所示的系统的操作。

图3B是根据本发明的一个实施例而形成的文本输入的图表结构。

图3C是根据本发明的一个实施例的LKB中所包含的图表结构。

图4A是流程图，更加详细地展示了实现模糊匹配。图4B展示了“钢笔”与“铅笔”之间被高度加权的语义关系路径。

图4C展示了在图4A中所陈述的过程期间所获得的被最高加权的匹配结构。

图4D-4F是流程图，分别展示了关于信息检索、机器翻译和自然语言界面的特殊应用程序的图2A中所示的系统的操作。

图5是流程图，展示了根据本发明的一个方面的引动操作。

图6是流程图，更加详细地展示了实现模糊匹配的另一个实施例。

具体实施方式

纵览

本发明针对匹配逻辑图表，这些逻辑图表在词汇或结构上可能彼此不同。逻辑关系包括由方向关系类型(例如，“部分”、“时间”、“Hypernym”、“逻辑-主语”)结合的两个单词。在开始详细讨论本发明之前，将讨论整篇说明书中所用的许多术语。语义关系使用方向关系类型并按一种定义明确的方法来叙述一对单词的含义。例如，以下的关系指出，名词“船”作为动词“漂浮”的主语：

                      船←逻辑主语-漂浮

这个语义关系被称为具有关系类型“逻辑主语”。关系类型包括许多普通的含义关系，例如：原因、领域、Hypernym、位置、方式、素材、方法、修饰语、部分、所有格、目的、类似Hypernym、同义词、时间、逻辑宾语、逻辑主语和用户。词汇知识库(下文将更加详细地加以描述)包含许多这类的语义关系。所以，语义关系路径(或只被称作“路径”)可以存在于被任意选择的各对单词之间。

逻辑表格是表示单个文本输入(例如，句子)的被连接的逻辑关系的图表。它至少包括一种逻辑关系。

特别是，逻辑表格描述了输入串中的各个重要单词之间的各种结构关系(即句法关系和语义关系)，尤其是论据关系和/或附属关系。

子图(类型A)是逻辑表格中被连接的逻辑关系的一个邻接的子集。

逻辑表格通过将节点与共同的词汇项目连接组成。

逻辑图表是单个的逻辑图表或各个逻辑图表和/或各个子图的合成。

子图(类型B)是逻辑图表中被连接的逻辑关系的一个邻接的子集。

路径是一种子图(类型A或B)，其中，各种逻辑关系按直线的顺序被连接。

在合成路径中，逻辑关系来自两个不同的逻辑表格。

词汇知识库是表示词汇主体的逻辑图表的集合。这些逻辑图表包括主体中每个词汇段的逻辑表格，它们按共同的单词组成。

为了使上述的各个术语与以前被包括用作参考的作品中的它们的同等物联系起来，可以参考以下表格：

表格1

   被包括的参考书目中的术语    语义关系(semrel)    逻辑表格三个一组    逻辑表格图表或其子图   这里所用的对应的术语    逻辑关系    逻辑关系    逻辑图表或其子图    语义关系结构    语义关系路径    被延伸的语义关系路径    逻辑表格    路径    路径(特别是合成路径)

在一个说明性实施例中，本发明针对将表示文本输入的逻辑图表与词汇知识库(LKB)中的逻辑图表进行匹配。本发明的一个实施例还针对将LKB中的逻辑图表与外部信息相链接。按“模糊”方式来实现图表匹配，即使被输入的图表与LKB中的逻辑图表之间存在结构上和词汇上的差别，该“模糊”方式也允许图表匹配。LKB中的逻辑图表与外部信息之间的链接可以采取众多方式(包括用于执行信息检索任务的指向文档的文档偏移量或指针、用于填充应用程序帧中的存储槽的信息、到关于机器翻译的其他语言(可能驻留在另一个LKB中)对应结构的节点的链接等)中的一种方式。

以下图1的讨论只陈述了其中可以使用本发明的一个说明性环境，虽然也能在其他环境中使用本发明。

图1是根据本发明的一个说明性实施例的计算机20的方框图。图1和有关的讨论意在对其中可实现本发明的一个合适的计算环境进行简要、概括的描述。虽然不作要求，但是，将至少部分地以由个人计算机执行的计算机可执行指令(例如，程序模块)的一般上下文中对本发明进行描述。通常，程序模块包括执行特殊任务或实施特殊的抽象数据类型的例行程序、对象、部件、数据结构等。而且，精通该技术领域的人将会理解，可以利用其他的计算机系统配置(包括手持设备、多处理器系统、基于微处理器的消费电子设备或可编程的消费电子设备、网络PCs、小型计算机、主机计算机等)来实现本发明。也可以在各种分布式计算环境中实现本发明，在这些分布式计算环境中，由通过通信网络被连接的远程处理设备来执行任务。在分布式计算环境中，程序模块既可以位于当地存储器设备中，又可以位于远程存储器设备中。

在图1中，用于实行本发明的一种示范系统包括采取传统个人计算机20的形式的一个通用计算设备，该通用计算设备包括处理单元21、一个系统存储器22和将包括该系统存储器的各种系统部件耦合到处理单元21的一个系统总线23。系统总线23可以是几种类型的总线结构(包括存储器总线或存储器控制器、外围总线和使用任何的各种总线结构的一个局部总线)中的任何总线结构。系统存储器包括只读存储器(ROM)24和随机存取存储器(RAM)25。基本输入/输出系统26(BIOS)被存储在ROM 24中，该基本输入/输出系统包含(例如，在启动时)帮助在个人计算机20内的各个元件之间传递信息的基本例行程序。个人计算机20还包括用于从硬盘(未示出)读取和写入硬盘的一个硬盘驱动器27、用于从可移动的磁盘29读取或写入可移动的磁盘29的一个磁盘驱动器28，以及用于从可移动的光盘31(例如，CD ROM或其他光媒体)读取或写入可可移动的光盘31的一个光盘驱动器30。硬盘驱动器27、磁盘驱动器28和光盘驱动器30分别由硬盘驱动器接口32、磁盘驱动器接口33和光驱动器接口34连接到系统总线23。驱动器和有关的计算机可读媒体为个人计算机20提供对计算机可读指令、数据结构、程序模块和其他数据的非易失性存储。

虽然这里所描述的示范环境使用一个硬盘、一个可移动的磁盘29和一个可移动的光盘31，但是，精通该技术领域的人应该理解，能够存储可由计算机存取的数据的其他类型的计算机可读媒体(例如，盒式磁带、闪存卡、数字化视频光盘、伯努里式盒式磁带、随机存取存储器(RAMs)、只读存储器(ROM)等)也可以被用在示范操作环境中。

许多程序模块(包括一个操作系统35、一个或多个应用程序36、其他程序模块37和程序数据38)可以被存储在硬盘、磁盘29、光盘31、ROM 24或RAM 25上。用户可以通过各种输入设备(例如，键盘40和指示设备42)来将命令和信息输入个人计算机20。其他的输入设备(未示出)可以包括话筒、游戏杆、游戏垫、圆盘式卫星电视天线、扫描仪等。这些和其他的输入设备经常通过被耦合到系统总线23的串行端口接口45而被连接到处理单元21，但也可以由诸如声卡、并行端口、游戏端口或通用串行总线(USB)的其他接口来连接。监视器47或其他类型的显示设备也经由一个接口(例如，视频适配器48)被连接到系统总线23。除了监视器47以外，个人计算机通常可以包括诸如扬声器和打印机(未示出)的其他外围输出设备。

个人计算机20可以在使用与一台或多台远程计算机(例如，远程计算机49)的逻辑连接的联网环境中运行。远程计算机49可能是另一台个人计算机、一个服务器、一个路由器、一个网络PC、一个同等设备或其他网络节点，并且通常包括与个人计算机20有关的上述许多或全部元件，虽然图1中只展示了一个内存存储设备50。图1中所描绘的逻辑连接包括一个局域网(LAN)51和一个广域网(WAN)52。这类联网环境在办公室、企业范围的计算机网络内联网和因特网中很普通。

当被用于LAN联网环境中时，个人计算机20通过网络接口或适配器53被连接到局域网51。当被用于WAN联网环境中时，个人计算机20通常包括一个调制解调器54或用于在广域网52(例如，互联网)上建立通信的其他设备。调制解调器54(可能是内部的，也可能是外部的)经由串行端口接口46被连接到系统总线23。在联网环境中，与个人计算机20有关的所描绘的程序模块或其各个部分可以被存储在远程内存存储设备中。将会理解，所示的各种网络连接是起示范作用，可以使用在各台计算机之间建立通信链接的其他方法。

图2A是根据本发明的一个说明性实施例的匹配系统100的方框图。匹配系统100包括输入分析器102、匹配部件104和词汇知识库(LKB)106。应该注意，图1中所展示的计算机20中可以包含整个系统100或系统100的一个部分。例如，输入分析器102和匹配部件104可以是作为(例如)应用程序36或程序模块37而被存储在存储器22中的软件模块，或者，它们可以被并入操作系统35。同样，LKB 106可以被存储在存储器22中，或者被存储在任何其他的存储设备上，例如，硬盘27、可移动的存储器29、光驱动器31或在广域网52或局域网51上的存储器设备。

在任何情况下，将根据图2B-2D来描述系统100的操作。虽然本发明的主要方面被用来仅仅匹配逻辑图表，但描述则对于一个说明性实施例进行。在该说明性实施例中，将被匹配的多个项目中的一个项目表示文本输入，另一个项目表示词汇知识库中的信息。将文本输入与词汇知识库中的逻辑图表进行匹配的第一个步骤是：获得图2A中所示的词汇知识库106。图2B中的方框108指出这一点。可以用众多已知的方式来获得词汇知识库106，图2C中特别陈述了那些方式中的一种方式，下文将更加详细地描述该方式。

一旦获得词汇知识库106，系统100就接收文本输入。图2B中的方框110指出这一点。应该注意，文本输入可以采取书面形式或口头形式。如果采取口头形式，则输入分析器102包括一个语音识别部件，该语音识别部件识别所接收的口头单词并将其精简为机器可读形式。可以用实质上任何已知的方式来实现这一点。如果文本输入采取书面形式，则它通常可以通过指示设备、键盘、笔迹分析部件等来被提供。

在任何情况下，一旦文本输入采取机器可读形式，则由输入分析器102对其加以分析。参考图3来更加详细地描述输入分析器102的功能。简而言之，输入分析器102分析文本输入，并创建一种表示文本输入的逻辑表格。存取LKB 106中的信息的匹配部件104提供这种逻辑表格。图2B中的方框112指出这一点。

匹配部件104尝试将表示文本输入的逻辑表格与LKB 106中的逻辑图表进行匹配。一旦发现匹配，匹配部件104就提供一个输出，该输出建立在对应于LKB 106中匹配的逻辑图表的注释的基础上。图2B中的方框114指出这一点。

LKB 106的生成

图2C是更加详细的流程图，展示了如何获得LKB 106。在所展示的实施例中，LKB 106是一种包括计算词典和结构完整的词汇例子库的各个部件的自动构造资源，被称作由华盛顿的雷德蒙(Redmond)的微软公司开发的“MindNet”。在以上被包括的文档中，也在由Richardson、Dolan和Vanderwende于1998年撰写的标题为《MindNet：从文本获取和建立语义信息》的文档中，更加详细地描述了开发MindNet词汇知识库的方法；读者参考那些文档，以便进行更加详细的讨论。但是，为完整起见，这里简要地陈述该方法。以上在表格1中的纵览部分陈述了有关该描述的术语等同物。但是，在这个部分中，所用的术语与被包括用作参考的文档(即，在以上表格1的左侧)中所用的术语一致。

在一个说明性实施例中，首先获得机器可读词典。方框116指出这一点。接下来，根据机器可读词典中所用的各种定义或句子来获得语义关系结构。通过创建一个语法分析树状结构和一个更深入的逻辑表格，可以获得这种语义关系结构。逻辑表格处理识别语法角色(比如逻辑主语和宾语)，解析远距离从属性，并使象主动/被动的一些句法更换规格化。它也解析代词的首语重复提及。从定义或例句中提取语义关系(semrels)会产生这些关系的一个分层结构，代表它们来自那里的整个定义或句子。这种结构被整体存储在LKB106中。图2C中的方框118指出获得这种语义关系结构的步骤。

然后，这些语义关系结构完全被颠倒并被传播通过整个LKB 106，与出现在它们中的每个单词相链接。图2C中的方框120和122中指出这一点。在被存储在LKB 106中的完全被颠倒的结构中，不管出现在什么地方，所有单词都被交叉链接。

图2D中描述了这种被颠倒和传播的结构。图2D中所展示的结构根据“驾车者”的定义而产生，并且与“汽车”的条目(作为被颠倒的结构的根部)相链接。

被颠倒的结构有助于获得每个结构的根部单词(是包含它的MindNet LKB条目的头部单词)与这些结构中所包含的其他每个单词之间的直接关系和间接关系。这些关系(包括直线地连接在一起的一种或多种语义关系)构成两个单词之间的语义关系路径。例如，图2D中的“汽车”与“人”之间的语义关系路径是：

                 汽车<T_宾语-驾驶-T_主语>驾车者-Hyp>人

被延伸的语义关系路径是从两个不同的、被颠倒的语义关系结构中的各个子路径创建而成的路径。例如，“汽车”和“卡车”不在语义关系上直接相关，也不在来自任何单个语义关系的语义关系路径上直接相关。但是，如果允许连接单词“车辆”处的语义关系“汽车-Hyp-车辆”和“车辆-Hyp-卡车”(每个来自不同的语义关系结构)，则会产生语义关系路径：“汽车-Hyp>车辆-Hyp>卡车”。被延伸的语义关系路径(被充分约束)证明对于确定MindNetLKB(否则将不被连接)中的各个单词之间的关系具有极为重要的作用。

语义关系路径被自动分配体现其显著性的加权。MindNet LKB中的这些加权建立在计算偏向语义关系(发生频率为中等)的平均顶点概率的基础上。此外，因连接来自不同结构的两个语义关系路径而产生被延伸的语义关系路径，为此处罚加权。在这里被包括用作参考的Richardson的论文中，详细陈述了一项说明性加权技术。图2C中的方框126指出：将加权分配给语义关系结构中的语义关系路径。

图2E表示MindNet LKB的一个片段。尤其是，图2E表现了直接与链接单词“把手”和“剑”的被最高加权的语义关系路径有关的MindNet LKB的片段。该片段展示了复杂的、被标记的关系链。当然，图2E是有关加权的简化插图说明，为清楚起见，已从图中除去其他的图表结构和注释。

处理输入和存取LKB

图3A是根据本发明的一个说明性实施例的、接收文本输入和存取LKB的更加详细的流程图。文本输入如以上参考图2A所讨论的那样来加以接收。图3A中的方框128指出这一点。

然后，生成表示文本输入的逻辑表格。当然，文本输入可以是一个句子片段、一个完整的句子或某个更大的演讲单元。在任何情况下，都可创建输入逻辑表格，该输入逻辑表格表示对文本输入的分析。

例如，在信息检索应用程序中，文本输入通常可能是一个询问，例如：  “德国什么时候越过波兰边境？”图3B只展示了表示那个文本输入的逻辑表格的一个实施例。该逻辑表格展示了询问中的各个内容单词之间的各种逻辑关系。图3A中的方框130指出：生成一个表示文本输入的输入逻辑表格。

接下来，匹配部分104(在图2A中被示出)执行将在方框130处所生成的输入逻辑表格与LKB 106中的一个或多个逻辑图表进行“模糊匹配”。根据本发明的一个实施例，所用的模糊匹配技术将定位一个文本片段，例如：

希特勒于1939年侵入波兰的边境。

图3C展示了关于以上回答的对应的逻辑图表。应该注意，这个逻辑图表是被存储在LKB 106中的各个逻辑表格的合成物。当然，图3C中所展示的关于回答的逻辑图表不等同于图3B中所展示的关于询问的逻辑表格。但是，根据本发明的一个方面的所使用的模糊匹配技术将把图3C中所展示的逻辑图表识别为匹配图表。以下参考图4A来更加详细地讨论执行匹配技术，图3A中的方框132指出这一点。即使各个图表之间存在结构差别或词汇差别，该匹配技术也允许在它们之间进行匹配。

一旦LKB中的匹配逻辑图表被定位，有关这些图表的任何指针或链接就被拷贝到输入逻辑表格。这个被注释的逻辑表格(被应用程序用来执行合适的动作)是这个匹配程序的输出。方框134指出这一点，以下参考图4D-4F来对其进行更加详细的讨论。例如，这类指针或链接可以包括识别曾产生匹配的逻辑图表的文本片段的文档偏移、关于可能驻留在另一个LKB中用于机器翻译的其他语言的对应的图表或用于填充语义帧中的存储槽的填充物。

模糊匹配

图4A是流程图，展示了根据本发明的一个说明性实施例的匹配技术。匹配部件104首先选择已根据文本输入而被生成的输入逻辑表格(例如，图3B中所示的输入逻辑表格)中的第一种逻辑关系。

举例来讲，所选择的第一种逻辑关系可以是被指定的“越过-Lsub>德国”。该逻辑关系中的两个内容单词是“越过”和“德国”。然后，匹配部件104在LKB中定位所选逻辑关系中的两个内容单词之间的n个最高加权路径。换言之，在LKB中的“越过”与“德国”之间可能有许多不同的路径，每个路径具有一个有关的加权。数字n可以是任何所需的整数。

例如，匹配部件可以在“越过”与“德国”之间找到一个被高度加权的路径，而不只是找到逻辑关系“越过-Lsub>德国”。该路径如下所示：

越过-Lsub>希特勒-所有格>德国

在最高的n个路径被定位后，匹配部件104可以推断逻辑关系，并确定输入逻辑表格中所选择的逻辑关系(在这种情况下，逻辑关系是“越过-Lsub>德国”)中的单词与在输入逻辑表格中没有被找到的所识别的n个路径中的单词之间的类似性。在以上被参考并被包括的标题为《确定单词之间的类似性》和《推断语义关系》的文档中，陈述了这样做的一种方法。这样，在以上的例子中，匹配部件104将确定“希特勒”与“德国”之间的类似性。

虽然在以上被识别和被包括的论文和专利申请中更加详细地描述了用于推断语义关系和确定类似性的一个说明性实施例，但是，为清楚起见，这里对其加以概述。这个概述将再次使用在被包括的参考书目中发现的历史术语(即以上“纵览”部分中的表格1左边的术语)。简而言之，该技术将syntagmatic信息和例证信息并入单个的知识库或LKB。类似性过程建立在单词之间的最高等级的(根据加权)路径的基础上。例如，图4B表现了单词“钢笔”与单词“铅笔”之间的MindNet LKB中的一些最高等级的路径。在图4B所示的例子中，语义关系对称的样式明显地出现在许多路径中。通过观察这种对称，可以理解，类似的单词通常被路径连接在MindNet LKB中，这些路径常常展示某些关系样式(不包括它们实际连接的单词)，许多样式是对称的，其他样式则不是对称的。

为了确定两个单词之间的类似性，通过利用语义关系对称的样式，本发明的一个说明性实施例涉及用于识别和加权所观察的各种路径样式的培训阶段，以及用于使用在培训阶段中被确定的路径样式加权来确定各对单词之间的类似性级别的类似性确定阶段。在培训阶段中，获得一对同义词，并且为每对同义词识别连接各对同义词的最显著的对。提取每个这样的路径的路径样式，并计算这些路径样式发生的频率。该频率(被称作“路径样式频率”或“路径样式加权”)表征每个路径样式趋向，指出由具备该路径样式的路径连接的单词的类似性。

在类似性确定阶段中，匹配部件104将一对单词(将为其确定类似性)作为输入来接收，并在定量地确定被输入的单词的类似性。匹配部件104识别被输入的各个单词之间的最显著的路径，并提取这些路径的路径样式。然后，匹配部件104确定在每种被提取的路径样式的培训阶段期间所计算的频率，并计算这些频率的平均数。这个平均频率表示被输入单词的类似性的相对测度。可以应用这同一个过程来在定量地确定同一个单词的两种意思之间的类似性的相对级别。

显著的语义关系路径发生器被匹配部件104用来识别两个单词之间的最显著的语义关系路径，该显著的语义关系路径发生器说明性地从词汇知识库获得这些最显著的路径，该词汇知识库为来自文档(代表主语内容领域)主体的特殊主语内容领域而进行自动编译。在以上被参考的标题为《识别两个单词之间的显著的语义关系路径》的美国专利申请(序列号＿＿＿＿)中，详细描述了这种显著的语义关系路径发生器的一个说明性实施。

换言之，已开发了一种推论过程，该推论过程允许根据目前在MindNet LKB中的语义关系来推断目前不在MindNet LKB中的语义关系。在以上所参考的文档和标题为《推断语义关系》的申请(两者都被包括，以用作参考)中，也更加详细地阐明了这种过程。简而言之，该程序利用将被推断的关系中的单词之间的最高等级的路径。例如，如果关系“观看-方法>望远镜”不在MindNetLKB中，则通过首先找到“观看”与“望远镜”之间的各个路径，再检查那些路径以发现是否有另一个单词与“望远镜”有“方法”的关系，可以将其推断出。如果有这样的另一个单词，则如以上所讨论的那样来确定那个单词与单词“观看”之间的类似性。结果是，单词“观察”满足以下路径中的这些条件：

                   观看-Hyp-观察>方法>望远镜

所以，可以推断出，某人可以利用“望远镜”这种“方法”来“观看”。

现在，继续描述在以上“纵览”中的表格1的右侧发现的对应的术语等同物。在以上参考图3B和3C所提供的例子中，单词“希特勒”和“德国”被确定为相类似，如同推断“越过”与“德国”之间的逻辑关系的副作用。所以，单词“希特勒”将被识别为类似的单词或“类似单词”(“simword”)。方框140中的过程指出：推断“越过”与“德国”之间的这种逻辑关系。

接下来，匹配部件104确定还没有被推断的输入逻辑表格中是否有任何其余的逻辑关系。图4A中的方框142指出这一点。如果有，则匹配部件104选择下一种逻辑关系(如方框143所指出的)，并为输入逻辑表格中的每种逻辑关系重复由方框138和140指出的各个步骤。例如，接下来，将推断第二种逻辑关系“越过-Lobj>边境”。假设在LKB中发现路径“越过-HypOf>侵入-Lobj>边境”，则匹配部件104在单词“越过”与“侵入”之间执行类似性分析，并发现它们类似，因此将“侵入”标注为另一个类似单词。

为本例考虑，假设匹配部件104在单词“越过”与“时间”之间没有发现任何被最高加权的路径，但是，它却为逻辑关系“边境位置-波兰”发现了包括单一逻辑关系“边境-所有格>波兰”的路径。虽然这两种逻辑关系并不相同，但是，可以将它们识别为在一种解释的关系中。因此，“边境-所有格>波兰”逻辑关系被识别为被输入的逻辑关系的结构解释。

然后，通过使用在前面的各个步骤中被识别的类似单词，来扩展搜索。这样，例如，通过用类似单词“侵入”代替术语“越过”并用类似单词“希特勒”代替“德国”，匹配部件104可以识别包括单一逻辑关系“侵占Lsub>希特勒”的路径。此外，由于术语“越过”和“侵入”已被确定为类似，因此，匹配部件104可以识别单一逻辑关系路径“侵入-Lobj>边境”。另外，通过用术语“侵入”代替第三个路径(“越过-时间>时间”)的“越过”，匹配部件104可以识别路径“侵入>时间-1939-Hyp>时间”。图4A中的方框144-149展示了使用类似单词来扩展采用这种方式的搜索。

简而言之，如方框144所指出的，选择被输入的逻辑表格中的第一种逻辑关系。在所选择的逻辑关系中的两个对应的单词的类似单词之间找到最高的n个路径。方框145指出这一点。然后，使用在方框140中被识别的类似单词，来为所选择的逻辑关系实现推论过程。方框146指出这一点。如果输入逻辑表格中留有任何逻辑关系，则选择下一种逻辑关系，处理回到方框145。方框148和149指出这一点。如果输入逻辑表格中不留有逻辑关系，则处理继续在方框150处进行。

在完成使用类似单词来扩展搜索和推断逻辑关系的各个步骤之后，匹配部件104保留因推断每种逻辑关系而产生的最高的n个路径。图4A中的方框150指出这一点。然后，匹配部件104创建不同的输出逻辑图表，这些输出逻辑图表包括因推断输入逻辑表格中的每种逻辑关系而产生的各个路径的不同组合。方框151指出这一点。当创建LKB时，输出逻辑图表按与逻辑表格相同的方式被进行加权(参考图2C进行更加详细的讨论)。方框152指出这一点。

保留最高的m个输出逻辑图表。例如，图4C展示了在图4A中所阐明的过程期间所获得的被最高加权的逻辑图表。可见，图4C中所展示的图表结构与图3C中所展示的图表同构。为了确定保留哪些逻辑图表，可使用一种加权机制。根据本发明的一个方面，有两个因素会影响逻辑图表的加权：(1)因推断输入逻辑表格中的每种逻辑关系而产生的各个路径的加权，和(2)所产生的逻辑图表中的各种逻辑关系是否来自相同的逻辑表格。包含来自相同逻辑表格的逻辑关系的逻辑图表将具有更高的加权。

使用匹配的结果

在完成模糊匹配之后，所产生的逻辑图表(根据LKB中的逻辑图表构制而成)可以具有可被用来完成所需任务的有关的指针或链接。图4D-4F展示了一些这样的任务。

图4D是流程图，展示了根据本发明的一个实施例的一种信息检索操作应用程序。图4D所示的许多方框类似于图3A所示的方框，并且，它们具有类似的编号。所以，接收被输入的询问，并根据被输入的询问来生成询问逻辑表格。方框128和130指出这一点。接下来，执行“模糊匹配”——将询问逻辑表格与LKB中的一个或多个逻辑图表进行匹配。方框132指出这一点。一旦已完成模糊匹配，匹配部件104或另一个部件就输出(1)曾在LKB中产生匹配的逻辑图表的实际文本，(2)包含该文本的文档，或(3)指向曾在LKB中产生匹配的逻辑图表的文本或文档的指针。方框154指出这一点。

也可以使用文本输入来完成文档集群操作，在该操作中，整个文档被馈入分析器并被放在一群类似的文档中。同样，可以使用系统来执行“发现类似”类型的操作。在该应用程序中，文本主体被提供给分析器，并且，要求系统找到类似类型的文档。也可以执行其他的应用程序。

图4E是流程图，展示了系统100在执行机器翻译任务中的操作。在该应用程序中，使用语言A的文本输入被接收，并且将被翻译成语言B。方框128指出这一点。然后，根据在方框128处所接收的文本输入来生成输入逻辑表格。方框130指出这一点。在输入逻辑表格与在语言A中被生成的LKB中的一个或多个逻辑图表之间执行模糊匹配。方框132指出这一点。

接下来，可以做许多事情。例如，语言A的LKB可以包括用于将输入翻译成语言B的翻译信息。这样，匹配部件104可以输出与LKB中匹配的逻辑图表有关的信息(表示将文本输入翻译成语言B)。或者，匹配部件104可以输出到语言B的LKB中的逻辑图表的链接，其中，这些链接与来自语言A的LKB的匹配的逻辑图表相关联。利用这种方法，可以确定曾产生有关的逻辑图表的、使用语言B的文本的位置。该文本将具有与待翻译的输入相同的或类似的含义。方框156指出这一点。另一种可供选择的方法是，匹配部件104可以输出指向曾产生指向语言B的LKB中的逻辑图表的文本的指针。方框158指出这一点。或者，匹配部件104可以输出曾产生指向语言B的LKB中的逻辑图表的实际文本。这实质上相当于语言A的文本输入的初步翻译。方框160指出这一点。可能要求额外的处理，以便从该输出产生更考究的翻译。

图4F是展示自然语言界面应用程序的另一幅图表。一些应用程序被设计成执行一项或多项任务，并根据自然语言输入命令来完成那些任务。例如，调度应用程序可以具有自然语言界面，该界面允许根据自然语言输入来建立约定。同样，多媒体应用程序可以允许用户提供自然语言输入，以控制光盘播放器(例如，选择一个光盘，并播放该光盘上的一个给定的磁道)。

应用程序开发者可以在LKB中提供链接，这些链接引起采取某些行动。例如，诸如“我想中午跟约翰见面”的输入可能会与由开发者的描述“某人(调度者)可以在一个时间(时间)安排与某人(被调度者)约会：(活动)”产生的一个LKB逻辑表格相匹配。这样，该匹配为调度应用程序提供它需要的信息来建立约会：“调度者＝我”、“活动＝见面”、“被调度者＝约翰”和“时间＝中午”。

所以，为了完成这样的实施，如方框128所指出的，首先接收自然语言文本输入。如方框130所指出的，根据自然语言文本输入来生成输入逻辑表格，并且，在该逻辑表格与LKB中的一个或多个逻辑图表之间执行模糊匹配。方框132指出这一点。在该说明性实施例中，来自匹配系统的输出可以是具有来自匹配的逻辑图表的链接的单词，它们被用来填充应用程序帧中的存储槽。图4F中的方框162指出这一点。

图5展示了根据本发明的一个说明性实施例来被执行的另一项技术。该技术在这里被称作“引动-priming”。引动被用来调整LKB中的逻辑图表的加权，以便它们成为模糊匹配过程中的较佳匹配目标。这样，LKB被“引动”以期待某些种类的输入，模糊匹配过程将其搜索焦点放在这些区域周围的解释的空间，以便尝试识别匹配。

举例来讲，假设：文本输入是被输入到安排约会的计算机系统的一种自然语言。此外，假设：第一种自然语言输入是“我想安排中午与约翰约会”。根据该输入，匹配过程将匹配LKB中的逻辑图表，这些逻辑图表与安排约会有关。然后，引动或增加这些逻辑图表上的加权。所以，如果直接在后面的自然语言输入是“安排在图书馆约会”，则匹配过程将集中于跟安排与调度者应用程序约会有关的LKB的区域，而不是集中于其他的领域。结果将会是：“图书馆”将可能被解释为“见面的地点”。

如图5中所阐明的流程图所示，可以执行引动过程。如方框170所指出的，系统接收并匹配第一个文本输入。在该文本输入与LKB中的一个区域相匹配之后，LKB中被匹配的延伸路径或逻辑图表的加权增加偏差量。方框172指出这一点。用这种方法来增加加权可以有效地使LKB倾向于寻找某些类型的输入。

然后，获得第二个文本输入。方框174指出这一点。对第二个文本输入进行处理，以获得第二个输入逻辑表格，该输入逻辑表格与具有以前被匹配的逻辑图表(具有偏置加权)的LKB相匹配。这样，系统展示了与具有被增加的加权的逻辑图表进行匹配的偏爱。方框176指出这一点。一旦第二个输入逻辑表格与LKB中的逻辑图表相匹配，就提供合适的输出。例如，在以上所讨论的说明性实施例中，可以建立地点为“图书馆”的约会。方框178指出：提供输出。

图6是流程图，展示了根据本发明的一个方面来执行模糊匹配的另一个实施例。匹配部件104首先获得输入逻辑表格。方框200指出这一点。

接下来，部件104识别输入逻辑表格中的起点。方框202指出这一点。通过检查输入逻辑表格中的每个节点处的单词，来说明性地识别该起点。作为例证，起点可能是“最独特的”节点，其中，可以用任何数量的合适的方法来确定独特性。例如，可以根据单词出现在文本主体中的频率、单词所加入的LKB中的逻辑表格的数量、它具有的类似单词的数量、单词及其类似单词出现在主体中的总频率、单词及其类似单词所加入的LKB中的逻辑表格的总数、单词是否是适当的名词等来确定独特性。可以使用任何这类的方法或各种方法的组合。

一旦识别起点，就颠倒输入逻辑表格，以便被识别为起点的单词成为逻辑表格的根部。方框204指出这一点。

然后，确定新根部的所有类似单词的位置。方框206指出这一点。如以上所讨论的，也可以采用任何数量的合适的方法来实现这一点，例如，通过使用词典来寻找类似单词、检查单词所加入的LKB中的逻辑图表并对逻辑图表中的路径应用类似性样式。应该注意，这些方法中的一些方法可以产生比较多的类似单词。所以，可以采用几种方法(例如，通过对被识别为类似单词的单词进行部分语音的限制、通过将路径形成限制到从密切相关的数据提取的逻辑图表(例如，在相同的百科全书文章内等))中的一种方法或任何数量的其他方法来限制其数量。也可以应用许多类似单词识别方法和探索法来扩大或限制为根部节点发现的类似单词的数量。按类似性的程度来对类似单词进行说明性评价，也可以采用任何数量的合适的方法来执行这一点。例如，可以利用被用来获得类似性的类似性样式的加权、曾在其中发现类似性样式的路径的加权、这些技术的组合或任何其他合适的技术，来识别类似性的程度。

一旦已获得输入逻辑表格的根部单词及其类似单词，运算就识别LKB中的一组候补逻辑表格，这些逻辑表格具有作为它们的根部的输入逻辑表格的根部单词或其类似单词中的一个类似单词。接下来，算法尝试将输入逻辑表格与这一组候补逻辑表格进行匹配。方框208和209指出这一点。在一个说明性实施例中，按顺序来搜索候选者——首先搜索包含输入逻辑表格中原来的单词的候选者，然后搜索包含最类似的单词的候选者，接下来搜索具有仅次于最类似的单词的候选者，如此类推，最后搜索包含最不类似的单词的候选者。当然，如果已发现足够数量的合适的匹配(其中，“合适的”可以意味着其总分数超过某个被定义的阈值的匹配)，则可以在任何时间终止搜索。

关于每个被定位的逻辑表格，通过检查输入逻辑表格中的节点上的单词和关系类型，并通过将它们与当前正被检查的LKB中的逻辑表格的节点上的单词和关系类型进行比较，来进行与输入逻辑表格的匹配。

在一个说明性实施例中，按以下方式来为逻辑表格中的节点上的单词进行匹配：如果输入逻辑表格中的单词和LKB中的逻辑表格中的对应的单词相同，则给该匹配满分。其他匹配(包括(但不局限于)以下所列出的匹配)被评价为：随着匹配程度的降低，所具有的值也减少。以下清单描述了可能类型的单词匹配的许多例子：

1.输入逻辑表格中的节点上的单词或LKB中的逻辑表格中的节点上的单词可以与其他单词的子成分相匹配(例如，林肯与林肯总统相匹配)。

2.疑问单词“谁”可以与具有“人”这个Hypernym或具有一些合适的特点(例如，[+人类]、[+名]、[+姓]等)的任何单词相匹配。在一个说明性实施例中，在解析曾产生正在被检查的逻辑表格的文本期间，对这些特点加以识别。

3.疑问单词“何时”可以与具有“时间”或“日期”这个Hypernym或具有某个合适的特点(例如，[+时间]、[+上午]、[+下午]、[+日期]等)的任何单词相匹配。

4.疑问单词“何处”可以与具有“地方”这个Hypernym或具有某个合适的特点(例如，[+位置]等)的任何单词相匹配。

5.诸如“如何”、“什么”或“为什么”的其他疑问单词可以与具有其他合适的Hypernyms或特点的单词相匹配。

6.诸如“我”、“你”、“他”、“她”、“我们”、“他们(她们、它们)”的人称代词可以与具有Hypernym“人”或具有某个合适的特点(例如，[+人类]、[+名]、[+姓]等)的任何单词相匹配。

7.具有特点(例如，以上所列的特点)的单词可以与具有相同的或兼容的特点的单词相匹配。

8.人称代词可以与相同的人称代词或另一个不同的人称代词相匹配。

9.输入逻辑表格中正在被检查的单词和LKB中的逻辑表格中的单词可能彼此类似，该类似性如以上所讨论的那样被加以确定和评价。

这些匹配中的一些匹配不如其他匹配有利，可以对应地调整它们的相对分数。当然，可以用许多方法来确定分数，例如，使用语言学家的直觉来手工设置或根据所收集的统计数字并通过机器学习算法(例如，Bayes网络)来学习等。

可以用以下的方式来执行匹配关系类型。如果输入逻辑表格中的关系类型等同于LKB中的逻辑表格中对应的关系类型，则给该匹配满分。其他匹配(包括(但不局限于)以下所列出的匹配)可以被评价为：随着匹配程度的降低，所具有的值也减少。以下清单描述了一些可能类型的_关系类型匹配：

1.任何关系类型都可以与被认为是其解释的另一个关系类型相匹配。例如，在某些条件下，Lsub和Lobj可以被认为彼此互为解释。同样，“位置”、“所有格”和“部分”也可以是彼此的解释。

2.关系类型也可以与可包含不止一个关系类型和一个或多个中介单词的较长样式相匹配。例如，X--LsubOf--有--Lobj--Y可以与X--所有格--y相匹配。此外，X--LsubOf--是--Lobj-Y可以与X--Equiv-Y或X--Hyp--Y相匹配。

这些解释的样式可以有不同的分数。可以用几种方法中的一种方法来揭示各种解释的样式及其有关的分数。例如，可以使用已知由一种特殊的关系类型链接的一对单词来培训主体(例如，可以手工检查各对单词和它们之间的关系类型，以创建主体)。然后，可以运用上述的路径算法来获得LKB中每对单词之间的所有路径。链接这些路径中的单词的各种关系类型的样式可以被用来学习，什么样式能为这两个单词之间的已知关系类型提供最可靠的解释。应该注意，这是对被用来揭示上述类似性样式的方法的推广，这项技术揭示了任何所需关系类型的这类样式，而不是揭示已知彼此互为同义词的单词之间的样式。

一旦已完成对匹配的搜索，就通过结合给单词匹配和关系类型匹配的单独分数，来确定给输入逻辑表格与LKB中的逻辑表格之间的匹配的总分数。给没有匹配关系的单词一个任意的低分。方框210指出这一点。在一个说明性实施例中，只是将这些分数相乘(或者，将这些分数取对数相加)。

作为例证，保持有序的匹配清单。当找到分数超过所需阈值的规定数量的匹配时，搜索程序终止。匹配程序的输出是LKB中分数最高的匹配逻辑表格的匹配部分的副本。当然，如上所述，可能有一些与这些匹配的逻辑表格有关的应用程序专用数据项目来协助执行应用程序任务(例如，指向文档的指针等)。

也应该注意，可以为一些应用程序来改进图6中所描述的方法，用于处理更大的句子。在改进过程中，输入文本按从句边界被分开，并使用上述的匹配技术来分别匹配每个从句。然后，将每个从句的最佳匹配结合起来，以提供全部最佳匹配的清单。

或者，不是先验地分开输入，而是可以对整个输入运用匹配技术，其后，输入的各个部分保持未被匹配。通过从旧的输入逻辑表格中除去曾经被成功匹配的各个部分，可以创建新的输入逻辑表格。然后，可以对新的(被精简的)输入逻辑表格执行匹配算法。通过重复应用此过程直到没有发现新匹配为止，可以将多个完整、庞大的从句的输入与LKB中的多个逻辑表格(即逻辑图表)进行匹配。

这样，可见，本发明的模糊匹配过程的结果是一组被高度加权的逻辑图表，与这些逻辑图表相关联的是识别翻译等同物的链接、到曾产生匹配的逻辑图表的文本片段的链接，或到某个特殊的系统动作的链接。这个匹配过程利用存在于输入逻辑表格与LKB内的逻辑图表之间的充分的语言上的相互制约。

可见，本发明特别针对解释的识别、词义解疑和对话界面的用户化。本发明可以有利地加以在广泛的应用领域中实施。

虽然已参考较佳实施例来描述了本发明，但是，精通该技术领域的工作人员将会认识到，在不脱离本发明的精神和范围的前提下，可以对形式和细节进行更改。