Method and system for efficient representation, manipulation, communication, and search of hierarchical composite named entities

• US 8,768,969 B2
• Filed: 07/09/2004
• Issued: 07/01/2014
• Est. Priority Date: 07/09/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Huerta, Juan Manuel, Lubensky, David, Raman, Thiruvilwamalai Venkatraman, Wiecha, Charles Francis
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US10/886,571
• Publication Number:
  US 20060010138A1
• Time in Patent Office: 3,644 Days
• Field of Search: 707/797, 704/246
• US Class Current: 707/797
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 40/279 Recognition of textual entities

Abstract

A method for managing dialogue interaction includes generating a hierarchical tree representation of a set of hierarchical data entities, and identifying a leaf node in the hierarchical tree representation. A system for managing dialogue interaction includes a hierarchical data format having a plurality of hierarchical data entities, and a dialogue interaction manager that manages a dialogue with a user based upon the hierarchical data format.

Claims

1. A method for managing dialogue interaction involving a computer, to allow a user to complete information for a composite data entity, said method

operating on a hierarchical representation of a set of composite data entities and storing said hierarchical representation in a memory of the computer, the hierarchical representation comprising a plurality of levels, each level corresponding to a respective attribute of the composite data entities and each level comprising one or more nodes, each node comprising a value for the respective attribute such that each composite data entity is represented by a path through the hierarchical representation to a leaf node, the method comprising:

with a processor of the computer, iteratively performing acts, comprising, for each iteration;

with a component executing on the computer, generating one or more prompts to the user based on the hierarchical representation, the one or more prompts requesting user input that differentiates between two or more paths, each of the two or more paths being a path through the hierarchical representation to a leaf node of the plurality of leaf nodes in the hierarchical representation;

recognizing in an utterance received from the user in response to the one or more prompts, one or more recognized values, each recognized value corresponding to a value of a node in the hierarchical representation;

identifying a subset of the paths in said hierarchical representation, each path in the subset having a node with a value corresponding to each of the one or more recognized values;

when the subset of paths ambiguously corresponds to a plurality of paths from a root node of the hierarchical representation to one or more of the leaf nodes;

selecting a disambiguative portion of the hierarchical representation, the disambiguative portion comprising the subset of paths; and

for a subsequent iteration, restricting generation, by the component, of the one or more prompts to the user, the component being restricted so as to generate the one or more prompts using the disambiguative portion of the hierarchical representation,

wherein;

the hierarchical representation comprises a tree; and

the method further comprises determining whether the subset of paths ambiguously corresponds to a plurality of paths by determining whether a first set of nodes unambiguously corresponds to a single leaf node or ambiguously corresponds to a set of leaf nodes, the first set of nodes comprising each node in the hierarchical representation having a value corresponding to a value of the one or more recognized values.

2. The method of claim 1, wherein generating one or more prompts comprises querying a user by enumerating the subset of paths.

3. The method of claim 1, wherein generating one or more prompts comprises querying a user to elicit a response differentiating between paths within the disambiguative portion.

4. The method of claim 1, wherein restricting generation by the component comprises issuing a restrictive directive.

5. The method of claim 1, wherein said dialogue interaction comprises one of recognizing speech, understanding a natural language, decoding speech, and parsing speech.

6. The method of claim 1, wherein generating the hierarchical representation of a set of composite data entities and storing said hierarchical representation in a memory of the computer comprises storing the representation in a markup language.

7. The method of claim 1, wherein the hierarchical representation comprises a number M of levels and the generating one or more prompts comprises generating fewer than M−

1 prompts to identify the unambiguous path.

8. A system involving a computer for managing interaction during a dialogue, said system comprising:

a memory storing a hierarchical representation of a plurality of composite data entities, the hierarchical data representation comprising a tree comprising a plurality of nodes, the hierarchical representation comprising a plurality of levels, each level corresponding to a respective attribute of the composite data entities, and each node being associated with a level of the plurality of levels, and each node being associated with a value forming a portion of a composite data entity and each path through the hierarchical representation defining values that form a composite data entity of the plurality of composite data entities such that each composite data entity is represented by a path through the hierarchical representation to a leaf node; and

a speech recognition mechanism for recognizing in an input utterance one or more of the values associated with nodes of the plurality of nodes regardless of an order in which the one or more values occur in the dialogue;

a dialogue interaction manager coupled to the speech recognition mechanism, said dialogue interaction manager identifying at least a node in said hierarchical representation having a value recognized in the input utterance or a path through said hierarchical representation that comprises one or more nodes having values recognized in the input utterance, said dialogue interaction manager further managing a dialogue with a user based upon the hierarchical representation to request from said user further utterances that contain values to complete information missing for one of said composite data entities, the dialogue comprising a plurality of requests, wherein;

each request in the dialogue is selected to differentiate between a plurality of paths through a sub-portion of the hierarchical representation, each of the paths in the plurality of paths containing at least one node with a value previously recognized in the input utterance or a received utterances of the further utterances in the dialogue,

the sub-portion is selected for each request of the plurality of requests to exclude portions of the hierarchical representation for which there is no ambiguous path to a node with a value previously recognized in the input utterance or the received utterances of the further utterances in the dialogue,

the sub-portion is communicated to the speech recognition mechanism for recognizing one or more of the values associated with nodes in the sub-portion in an input received in response to the request; and

the dialogue interaction manager determines whether the sub-portion ambiguously corresponds to a plurality of paths by determining whether a first set of nodes unambiguously corresponds to a single leaf node or ambiguously corresponds to a set of leaf nodes, the first set of nodes comprising each node in the sub-portion having a value corresponding to a value of the one or more recognized values.

9. The system of claim 8, wherein:

the speech recognition mechanism comprises a dialogue parser in communication with said dialog interaction manager, and

the dialogue parser and the dialog interaction manager each receive a restrictive directive identifying the sub-portion of the hierarchical representation.

10. The system of claim 8, further comprising one of a telephone server and a web server in communication with said system.

11. The system of claim 8, wherein said dialogue interaction manager comprises a disambiguation mechanism.

12. The system of claim 11, wherein said disambiguation mechanism comprises a restrictive directive.

13. The system of claim 12, wherein said restrictive directive comprises one of an explicit restrictive directive, an implicit restrictive directive, and an algebraic restrictive directive.

14. The system of claim 11, wherein a characteristic of said disambiguation mechanism is inferred based upon a dialog with a user and the hierarchical data format.

15. The system of claim 8, wherein said composite data entities comprise hierarchical data entities comprising multiple-attribute data structures.

16. The system of claim 8, wherein said hierarchical representation comprises a hierarchical data format comprising one of homonym nodes and a homonym graph.

17. A system for managing dialogue interaction comprising:

means for storing a hierarchical tree representation of a set of composite data entities in a computer, the hierarchical representation comprising a plurality of levels, each level corresponding to a respective attribute of the composite data entities, the hierarchical representation comprising a plurality of nodes, each node being associated with a level of the plurality of levels, and each node being associated with a value forming a portion of a composite data entity and each path through the hierarchical representation defining values that form a composite data entity of the plurality of composite data entities such that each composite data entity is represented by a path through the hierarchical representation to a leaf node;

means for receiving an utterance from a user in a computer;

means for recognizing the utterance; and

means for identifying at least one of a leaf node in the hierarchical tree representation and a path through said hierarchical tree representation that corresponds to the recognized utterance and for permitting a user to complete any information that might be missing for a composite data entity related to said utterance by requesting from said user further utterances that contain values to complete information missing for one of said composite data entities, wherein;

each request in the dialogue is selected to differentiate between a plurality of paths through a sub-portion of the hierarchical tree representation, each of the paths in the plurality of paths containing at least one node with a value previously recognized in the input utterance or received utterances of the further utterances in the dialogue, the request being made based on finding an attribute that distinguishes among paths of the plurality of paths such that a path is unambiguously identified with fewer requests than levels of the hierarchical representation spanned by the paths of the plurality of paths, and

the sub-portion is selected for each request to exclude portions of the hierarchical representation for which there is no ambiguous path to a node with a value previously recognized in the input utterance or the further utterances in the dialogue; and

the sub-portion is communicated to the means for recognizing the utterance for recognizing one or more of the values associated with nodes in the sub-portion in an input received in response to the request;

it is determined whether the subset sub-portion ambiguously corresponds to a plurality of paths by determining whether a first set of nodes unambiguously corresponds to a single leaf node or ambiguously corresponds to a set of leaf nodes, the first set of nodes comprising each node in the hierarchical representation having a value corresponding to one or more recognized utterances.

18. A non-transitory computer storage device comprising computer-readable code that, when executed in a computing system, performs a method of identifying a named entity, the computer-readable code comprising:

instructions for at least one of generating or storing a hierarchical tree representation of a set of data entities in a computer, the hierarchical representation comprising a plurality of levels, each level corresponding to a respective attribute of the composite data entities, the hierarchical representation comprising a plurality of nodes, each node being associated with a level of the plurality of levels, and each node being associated with a value forming a portion of a composite data entity and each path through the hierarchical representation defining values that form a composite data entity of the plurality of composite data entities such that each composite data entity is represented by a path through the hierarchical representation to a leaf node;

instructions for receiving a plurality of utterances from a user of a computer;

instructions for recognizing recognized values in the plurality of utterances;

instructions for identifying, at each of a plurality of times in response to utterances of the plurality of utterances received at the time, one or more paths, through the hierarchical representation, each of the one or more paths comprising nodes each having a value corresponding to a recognized value at the time;

instructions for determining whether the one or more paths ambiguously corresponds to a plurality of paths by determining whether a first set of nodes unambiguously corresponds to a single leaf node or ambiguously corresponds to a set of leaf nodes, the first set of nodes comprising each node in the hierarchical representation having a value corresponding to a value of the one or more recognized values;

instructions for generating one or more prompts to the user based on a specified portion of the hierarchical representation, the one or more prompts requesting user input that distinguishes between paths of the one or more paths in accordance with a disambiguation strategy that finds and utilizes an attribute of the plurality of attributes that distinguishes among the one or more paths;

instructions for, when the one or more paths ambiguously corresponds to a plurality of paths from a root node of the hierarchical tree representation to one or more leaf nodes, iteratively;

selecting a disambiguative portion of the hierarchical tree representation based on the plurality of paths; and

providing an indication of the disambiguative portion of the hierarchical tree representation as the specified portion for the instructions for generating one or more prompts, the indication comprising a restrictive directive, whereby an unambiguous path through the hierarchical tree representation to the leaf node is identified, the path indicating complete information for a hierarchical data entity.