Method and system for building and running natural language understanding systems

• US 6,629,066 B1
• Filed: 09/07/1999
• Issued: 09/30/2003
• Est. Priority Date: 07/18/1995
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Weng, Fuliang, Cohen, Michael H., Jackson, Eric G.
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/390,457
• Time in Patent Office: 1,484 Days
• Field of Search: 704/1, 704/8-10, 704/255, 704/257, 707/530, 707/531, 707/532, 707/200, 707/900, 707/908
• US Class Current: 704/9
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation

Abstract

A computerized method for building and running natural language understanding systems, wherein a natural language understanding system takes a sentence as input and returns some representation of the possible meanings of the sentence as output (the “interpretation”) using a run-time interpreter th assigns interpretations to sentences and a compiler that produces (in a computer memory) an internal specification needed for the run-time interpreter from a user specification of the semantics of the application. The compiler builds a natural language system, while the run-time interpreter runs the system.

Claims

1. A speech interpretation system on a digital computer, said interpretation system comprising in combination:

a first input means, said first input means for accepting as input an internal specification of application semantics, said internal specification of application semantics including a grammar format defining grammars, wherein at least one of said grammars includes one of a slot-filling command and a return command;

a second input means, said second input means for accepting as additional input speech having at least one phrase; and

a run-time interpreter, said run-time interpreter for assigning interpretations to said phrases, said run-time interpreter employing said internal specification in assigning said interpretations according to said application semantics and said grammars, said interpretations comprising slots supplied with values, wherein said run-time interpreter comprises means for assigning said interpretations such that each of said interpretations is from a corresponding first set of candidate interpretations, said first set containing candidate interpretations which use the most words from one of said input phrases.

2. The speech interpretation system according to claim 1 wherein said each of said interpretations is also from a corresponding second set of candidate interpretations, said second set containing candidate interpretations built from the fewest phrases of all candidate interpretations within said corresponding first set.

22. The system of claim 1 wherein:

the at least one grammar includes a slot-filling command; and

the slot-filling command is executed if the at least one grammar is matched against the phrase and a construction attached to the slot-filling command is part of the match.

23. The system of claim 22 wherein the slot-filling command is configured to fill at least one slot with the construction that is attached to the slot-filling command.

3. An interpretation system on a digital computer, said interpretation system comprising in combination:

a first input means, said first input means for accepting as input an internal specification of application semantics, said internal specification of application semantics including a grammar format defining grammars, wherein at least one of said grammars includes one of a slot-filling command and a return command;

a second input means, said second input means for accepting as additional input at least one sentence; and

a run-time interpreter, said run-time interpreter for assigning interpretations to said sentences, said run-time interpreter employing said internal specification in assigning said interpretations according to said application semantics, said interpretations comprising slots supplied with values, wherein said run-time interpreter is operative to assign said interpretations according to grammars, and said run-time interpreter comprises;

a phrase-matching means, said phrase-matching means for producing intermediate data by matching phrases from said input sentences to said grammars, said intermediate data comprising information on all matching phrases, said matching phrases each matching at least one of said grammars; and

an interpretation assembly means coupled to said phrase-matching means, said interpretation assembly means for assigning said interpretations using said intermediate data.

4. The interpretation system according to claim 3, wherein said interpretation assembly means uses a dynamic programming search method to assign said interpretations by combining said matching phrases according to an optimality definition.

5. The interpretation system according to claim 4 wherein said pre-defined user specification format includes a template format, said template format defining structure of a template specification within said user specification, said template specification defining templates, each of said templates comprising a collection of slot specifications, each of said interpretations being required to correspond to one of said templates such that all said slots within said each of said interpretations match said slot specifications within said corresponding template;

and wherein said dynamic programming search method uses states, said states being defined for any combination of said matching phrases, each of said states comprising a list of the templates with which said combination of matching phrases is compatible.

6. The interpretation system according to claim 4 wherein said pre-defined user specification format includes a slot combination format, said slot-combination format defining structure of a slot combination specification within said user specification, said slot combination specification defining slot combination rules, said combination rules defining allowable and unallowable combinations of slots within said interpretations;

and wherein said dynamic programming search method uses states, said states being defined for any combination of said matching phrases, each of said states comprising a list of the combination rules which are triggered by said combination of matching phrases and a list of the combination rules which are satisfied by said combination of matching phrases.

7. A system in a digital computer for processing specifications of application semantics, said semantics describing interpretations corresponding to sentences, said interpretations comprising slots supplied with values, said system comprising:

an input means, said input means for accepting as input a user specification of application semantics, said user specification of application semantics including a grammar format defining grammars, wherein at least one of said grammars includes one of a slot-filling command and a return command;

a verification means, said verification means for checking said user specification and said grammars for errors according to a pre-defined user specification format; and

a signaling means, said signaling means for indicating occurrences of errors as found by said verification means in said user specification and said grammars.

8. The system according to claim 7 wherein said pre-defined user specification format includes a slot class format, said slot class format defining structure of a slot class specification within said user specification, said slot class specification defining classes of slots.

9. The system according to claim 7 wherein said pre-defined user specification format includes a template format, said template format defining structure of a template specification within said user specification, said template specification defining templates, each of said templates comprising a collection of slot specifications, each of said interpretations being required to correspond to one of said templates such that all said slots within said each of said interpretations match said slot specifications within said corresponding template.

10. The system according to claim 7 wherein said pre-defined user specification format includes a slot combination format, said slot combination format defining structure of a slot combination specification within said user specification, said slot combination specification defining allowable and unallowable combinations of slots within said interpretations.

11. The system according to claim 7 further comprising a specification generator means, said specification generator means for producing an internal specification of application semantics from said user specification, said internal specification relating said application semantics.

24. The system of claim 11 wherein:

the at least one grammar includes a return command;

and the return command is executed if the at least one grammar is matched against the phrase and a construction attached to the return command is part of the match.

25. The system of claim 24 wherein the return command is configured to fill at least one slot with the construction that is attached to the return command.

26. The system of claim 25 wherein:

the at least one slot filled by the return command is identified by a variable having a variable name that matches the at least one slot; and

the variable is assigned the construction that is attached to the return command.

12. A development method operative on a digital computer for building a natural language understanding system, said development method comprising the steps of:

accepting as input a user specification of application semantics, said user specification of application semantics including a grammar format defining grammars, wherein at least one of said grammars includes one of a slot-filling command and a return command;

checking said user specification and said grammars for errors according to a pre-defined user specification format; and

producing an internal specification of application semantics from said user specification, said internal specification of application semantics including said grammars in a run-time interpreter executable form, said internal specification for supplying said application semantics and said grammars to said run-time interpreter, said run-time interpreter for assigning interpretations to input sentences according to said grammars, said interpretations comprising slots supplied with values.

13. The development method according to claim 12 wherein said pre-defined user specification format includes a slot class format, said slot class format defining structure of a slot class specification within said user specification, said slot class specification defining classes of slots.

14. The development method according to claim 12 wherein said pre-defined user, specification format includes a template format, said template format defining structure of a template specification within said user specification, said template specification defining templates, each of said templates comprising a collection of slot specifications, each of said interpretations being required to correspond to one of said templates such that all said slots within said each of said interpretations match said slot specifications within said corresponding template.

15. The development method according to claim 12 wherein said pre-defined user specification format includes a slot combination format, said slot combination format defining structure of a slot combination specification within said user specification, said slot combination specification defining allowable and unallowable combinations of slots within said interpretations.

16. A method operative on a digital computer for natural language understanding, said method comprising the steps of:

accepting as input an internal specification of application semantics, said internal specification of application semantics including a grammar format defining grammars, wherein at least one grammar includes one of a slot-filling command and a return command;

accepting as additional input at least one sentence; and

assigning interpretations to said sentences employing said specification and said grammars, said interpretations comprising slots supplied with values, further comprising producing each one of said interpretations from a corresponding first set of candidate interpretations, said first set containing candidate interpretations which use the most words from one of said input sentences.

17. The method according to claim 16 wherein said each of said interpretations is also from a corresponding second set of candidate interpretations, said second set containing candidate interpretations built from the fewest phrases of all candidate interpretations within said corresponding first set.

18. A method operative on a digital computer for natural language understanding, said method comprising the steps of:

accepting as input an internal specification of application semantics, said internal specification of application semantics including a grammar format defining grammars, wherein at least one grammar includes one of a slot-filling command and a return command;

accepting as additional input at least one sentence;

assigning interpretations to said sentences employing said specification and said grammars, said interpretations comprising slots supplied with values; and

matching phrases from said input sentences to at least one of said grammars to produce intermediate data, said matching step preceding said interpretations assigning step, said interpretations assigning step using said intermediate data, said intermediate data comprising information on all matching phrases, said matching phrases each matching at least one of said grammars.

19. The method according to claim 18 wherein said interpretations assigning step uses a dynamic programming search method to assign said interpretations by combining said matching phrases according to an optimality definition.

20. The method according to claim 19 wherein said pre-defined user specification format includes a template format, said template format defining structure of a template specification within said user specification, said template specification defining templates, each of said templates comprising a collection of slot specifications, each of said interpretations being required to correspond to one of said templates such that all said slots within said each of said interpretations match said slot specifications within said corresponding template;

and wherein said dynamic programming search method uses states, said states being defined for any combination of said matching phrases, each of said states comprising a list of the templates with which said combination of matching phrases is compatible.

21. The method according to claim 19, wherein said pre-defined user specification format includes a slot combination format, said slot combination format defining structure of a slot combination specification within said user specification, said slot combination specification defining slot combination rules, said combination rules defining allowable and unallowable combinations of slots within said interpretations;

and wherein said dynamic programming search method uses states, said states being defined for any combination of said matching phrases, each of said states comprising a list of the combination rules which are triggered by said combination of matching phrases and a list of the combination rules which are satisfied by said combination of matching phrases.