Method and apparatus for understanding natural language

• US 6,272,455 B1
• Filed: 10/22/1997
• Issued: 08/07/2001
• Est. Priority Date: 10/22/1997
• Status: Expired due to Fees

• Current Assignee: IPR 1 Pty Limited
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Hoshen, Joseph, Levendel, Isaac, Vemuri, Kumar Venkata Visveswara
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/955,677
• Time in Patent Office: 1,385 Days
• Field of Search: 704/1, 704/9, 704/10, 704/246, 704/255, 704/257, 704/251, 704/236, 704/239, 704/247, 704/250
• US Class Current: 704/1
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 2015/088 Word spotting

Abstract

In a speech recognition system capable of identifying particular words, input speech signals can be processed to detect certain patterns and word combinations. The recognition of these speech patterns and word combinations allow the speech recognition system to replace a number-driven menu, automated attendant systems. Once the speech recognition system recognizes the input speech signal, it confirms the accuracy of the identified speech pattern or word combinations with the user.

Claims

1. A method for understanding natural language utterances within a well-defined language comprised of a set of predetermined, understandable keywords within a predetermined dictionary of such understandable keywords, said understandable keywords being representable by nodes in a tree graph the nodes of which include a root node, leaf nodes, and intermediate nodes between said root and leaf nodes, each leaf node and intermediate node of said tree graph representing one or more keywords in said predetermined dictionary of understandable keywords, syntactical relationships between recognizable keywords in said language being specified and representable by paths, formed by the edges in said tree graph linking said leaf nodes and said intermediate nodes to said root node in a predetermined order, said method comprising the steps of:

a) obtaining at least one input token representing an utterance from a user and determining if said at least one input token represents a recognizable keyword and mapping the occurrence of said recognizable keyword to a node in said tree, forming thereby marking nodes in said tree;

b) identifying mapped nodes in said tree to determine which nodes form a path between a leaf node to the root node of said tree by soliciting and receiving recognizable keywords testing mapped nodes according to a predetermined probability that mapped nodes correspond to a user'"'"'s utterance; and

c) identifying a path between said root node and a marked leaf node to be an understood utterance of said user.

2. The method of claim 1 further comprising the step of identifying mapped nodes in said tree to determine which nodes form a path between a leaf node to the root node of said tree by soliciting and receiving additional recognizable keywords iteratively to obtain a plurality of input tokens.

3. An apparatus for understanding natural language utterances within a well-defined language comprised of a set of predetermined, understandable keywords within a predetermined dictionary of such understandable keywords, said understandable keywords being representable by a tree graph formed by nodes that include a root node, leaf nodes, and intermediate nodes between said root and leaf nodes, each leaf node and intermediate node representing one of more keywords in said predetermined dictionary of understandable keywords, syntactical relationships between recognizable keywords in said language being specified and representable by paths, formed by the edges in said tree graph linking said leaf nodes and said intermediate nodes to said root node in a predetermined order, comprising:

a) input means for obtaining at least one input token representing an utterance from a user and determining if said at least one input token represents a recognizable keyword and mapping the occurrence of said recognizable keyword to a node in said tree, forming thereby mapped nodes in said tree;

b) determination means for identifying mapped nodes in said tree to determine which nodes form a path between a leaf node to the root node of said tree;

c) identification means for identifying recognizable keywords of said language that are represented by said leaf node of to be an understood utterance of said user; and

d) means for identifying mapped nodes in said tree to determine which nodes form a path between a leaf node to the root node of said tree by soliciting and receiving additional recognizable keywords and testing mapped nodes according to a predetermined probability that mapped nodes correspond to a user'"'"'s utterance.

4. The apparatus of claim 3 further including:

means for identifying a complete path between a leaf node to the root node of said tree.

5. The apparatus of claim 3 further including:

means for identifying mapped nodes in said tree to determine which nodes form a path between a leaf node to the root node of said tree by soliciting and receiving additional recognizable keywords iteratively for a plurality of input tokens.

6. The apparatus of claim 3 where said input means for obtaining at least one input token, said means for identifying mapped nodes, and said means for identifying recognizable keywords is a computer.

7. The apparatus of claim 3 where said input means for obtaining at least one input token is a keyboard.

8. The apparatus of claim 3 where said input means for obtaining at least one input token is a pointing device.

9. The apparatus of claim 3 where said input means for obtaining at least one input token is a handwriting recognition device.

10. The apparatus of claim 3 where said input means for obtaining at least one input token is facsimile machines.

11. The apparatus of claim 3 where said input means for obtaining at least one input token is an optical character recognition device.

12. The apparatus of claim 3 where said input means for obtaining at least one input token is output from a computer program.