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

[0001] 1. Field of the Invention

[0002] The present invention generally relates to systems and methods for efficiently representing, manipulating, communicating, and searching hierarchical composite named entities. In particular, the present invention relates to a system and method for creating a tree representation of hierarchically related data, as well as, to systems and methods for manipulating and searching using a hierarchical tree representation.

[0003] 2. Description of the Related Art

[0004] Conventional speech and natural language understanding systems are greatly limited by the grammars and models of the speech data that are used by such systems. The grammars are used for both recognition of speech and for use in labeling of data. The types of grammars that are typically used are of two types: simple and complex. A simple grammar is a simple enumeration of entities while a complex grammar is an enumeration of a space of values of complex entities.

[0005] A problem for these conventional speech and natural language understanding systems is that, when they use a simple grammar, any interaction with the user that involves resolving ambiguities is often lengthy and complicated.

[0006] Natural language understanding systems are often called upon to capture data from a user that is a hierarchical data type. For example, a natural language understanding system may be written to identify a specific airport based upon a user's input. A natural language understanding system that relies upon a simple grammar to identify the airport requires a specific number of interactions to determine (i.e., to “disambiguate”) the user's input into a specific airport identifier. Such a system would require the user/system interaction to start broadly, such as by identifying a state in which the airport is located, and successively narrow down the location, such as by identifying a county within the identified state, then a city/town, et. seq.

[0007] In this instance, a simple grammar is required to recognize each of the fifty states, another simple grammar is required to recognize each county within each recognized state, yet another simple grammar is required to recognize each city/town within each recognized county, et. seq.

[0008] It is very difficult and labor intensive to write such a large number of simple grammars because the number of simple grammars that may be required grow significantly as each particular airport is added to the list of possible airports that may be recognized.

[0009] A problem for these conventional speech and natural language understanding systems when they use a complex grammar is that a complex grammar is very manually intensive and laborious to maintain and establish. This is true because complex grammars often require the developer of the grammar to specify every possible combination and subset of entities that are associated with the complex grammar.

[0010] If an application is written using a complex grammar to identify an airport, such a grammar must be capable of identifying each airport based upon a variety of possible user input. For example, a complex grammar must be written that will identify John F. Kennedy (JFK) airport in New York City, based upon any number of possible recognized user utterances, such as “JFK airport,” “New York state, New York city,” or “New York City, N.Y. State,” etc. In this approach, a grammar must be written that is very complex in that, for each airport, multiple types of utterances may correspond to any given entry in the list of airports and the grammar must be written to incorporate all possible types of utterances which will identify any given airport. Such a grammar is very complex and is very laborious to generate and to maintain.

[0011] In view of the foregoing and other exemplary problems, drawbacks, and disadvantages of the conventional methods and structures, an exemplary feature of the present invention is to provide a method and system that creates a tree representation of hierarchically related data, as well as, to systems and methods for manipulating and searching such a tree representation.

[0012] In a first exemplary aspect of the present invention, 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.

[0013] In a second exemplary aspect of the present invention, a method of generating a tree includes organizing a set of hierarchical data entities into a hierarchical tree based upon their hierarchical relationship.

[0014] In a third exemplary aspect of the present invention, a system for managing dialogue interaction includes a hierarchical data format that includes a plurality of hierarchical data entities, and a dialog interaction manager that manages a dialogue with a user based upon the hierarchical data format.

[0015] In a fourth exemplary aspect of the present invention, a system for managing dialogue interaction includes means for generating a hierarchical tree representation of a set of hierarchical data entities, and means for identifying a leaf node in the hierarchical tree representation.

[0016] In a fifth exemplary aspect of the present invention, a method for deploying computing infrastructure includes integrating computer-readable code into a computing system. The computer-readable code includes instructions for generating a hierarchical tree representation of a set of hierarchical data entities, and instructions for identifying a leaf node in the hierarchical tree representation.

[0017] An exemplary embodiment of the present invention addresses the problems that are involved when specifying, representing, manipulating, communicating and/or searching composite data entities in a concise structured and efficient manner.

[0018] An exemplary embodiment of the present invention may be used in a speech and/or natural language understanding system.

[0019] An exemplary embodiment of the present invention may be used, for example, in a speech recognition system, a speech decoder system and/or a speech parsing system.

[0020] In contrast to the above-mentioned conventional speech recognition systems and natural language understanding systems, the present invention allows for the use of implicit disambiguation mechanisms. In other words, in accordance with the present invention the disambiguation and/or clarification mechanisms may be inferred (implied) based upon the hierarchical data format.

[0021] Further, an exemplary embodiment of the present invention automatically generates data structures that are required to perform a search in a recognition state directly from a hierarchical data structure (such as a tree).

[0022] These and many other advantages may be achieved with the present invention.

[0031] Referring now to the drawings, and more particularly to FIGS. 1-7, there are shown exemplary embodiments of the method and structures of the present invention.

[0032] Composite data are data entities that include multiple-attribute structures. Examples of composite data entities include addresses, airport listings, business listings, government listings, product information, and the like.

[0033] One example of a format for a composite address data entity may be state name, city name, street name, and street number. A quality of this format is that it is hierarchical and constrained. An instance of such an address data entity is “222 Broadway Street, Springfield, N.Y.” in this example.

[0034] One exemplary embodiment of the present invention may be used by a speech and natural language understanding system 100 as illustrated, for example, by FIG. 1. FIG. 1 shows a block diagram of an exemplary speech and natural language recognition system 100 in a web/telephony environment.

[0035] The block diagram of FIG. 1 illustrates communication links between a user 170 and the natural language understanding system 100. The natural language understanding system 100 includes a telephony/web server 110, a speech recognizer 120, a parser (or labeler) 130 and a dialog manager 140.

[0036] One example of an objective of an interaction of a user 170 with the natural language understanding system 100 that is shown in FIG. 1 may be simply to allow the dialog manager 140 to collect a set of information from the user 170 to generate entities.

[0037] The entities may be determined based upon the nature of a communication transaction between the natural language understanding system 100 and the user 170, as well as, lists, grammars and models that may be employed by the recognizer 120 and labeler 130 which may communicate dynamically with the dialog manager 140 using link A.

[0038] Current automatic speech recognition and natural language understanding applications simplify the problem of representing and identifying by decomposing the complex data structures into simple entities in order to be able to recognize and label complex entities based upon a user's input.

[0039] For each of these entities, conventional systems represent and identify the entities in two steps. First, models for a search through a grammar or statistical language model are communicated to the recognizer 120 and the labeler 130 through link A and the user's input is decoded into a text format of recognized utterances using the grammar or statistical language model. This first step is called “recognition and search data-space representation.”

[0040] Second, the recognized utterances are constrained and labeled or parsed based upon their meaning. This second step identifies the salient or relevant pieces of information in the recognized utterances. Parsers and labelers typically perform this second step and sometimes it is performed using grammar based decoding.

[0041] Conventionally, grammars are employed for both recognition and labeling. As explained above, grammars may be of two types. The first type of grammar is called a “simple entity flat grammar” that may include a simple enumeration of simple entities. In the address example above, four separate simple entity grammars are required to represent a whole space of data having the address format: (1) a street-number grammar, (2) a street-name grammar, (3) a city grammar, and (4) a state grammar. The second type of grammar is called a “complex grammar” that provides an enumeration of the space of values of complex entities. For the above example, a U.S. address complex grammar would enumerate such values.

[0042] As mentioned above, complex grammars must be created manually and are laborious to update and maintain. Furthermore, complex grammars need to specify every possible combination and subset of entities that may be associated with a complex entity. Further, disambiguation strategies are extremely difficult to implement and handle using complex grammars.

[0043] On the other hand, conventional approaches to speech and natural language recognition systems that use flat (simple) grammars rely on interaction algorithms and methods that sequentially identify values for each of the conforming attributes. While sequential data capturing techniques are appropriate in some applications (like directed dialog voice interfaces), the main drawback of these techniques is that in a data structure with N attributes (e.g., N=4 in the U.S. address example) the interaction must take exactly 4 turns, and currently there is no known way to use this approach to efficiently reduce the number of turns or to efficiently manipulate the grammars. This conventional approach imposes the constraints on the hierarchy in a sequential fashion.

[0044] A markup language (or markup code) for a speech recognition system and/or natural language generation system tells a browser what steps are required to be executed in order to achieve an appropriate interaction with a user. A developer is required to write all of the grammars (simple, complex or both) and all of the markup language that will implement the grammars that are written. Such a process is extremely laborious.

[0045] In summary, there are many problems and disadvantages in the conventional state of the art. For example, there are a fixed number of interactions for simple entity grammars; there are order and subset problems for complex grammar multiple entities; manual grammar creation and maintenance is intensive; disambiguation is difficult to implement and handle; and directed and mixed initiative modalities require separate crafted grammars.

[0046] While the indexing, representation and manipulation of complex records in databases may be achieved through relational databases, such databases are not easily usable directly in speech recognition, speech dialog, web interface or any other form of client/server/user interaction. These relational databases may be useful for database query searches but are not useful for the capturing of complex entity data from a user in an application. Therefore, while some conventional database searching systems rely upon a relational database, conventional speech and natural language search and application systems have been limited to simple enumerative grammars.

[0047] An exemplary embodiment of the present invention addresses the problems of specifying, representing, manipulating, communicating and searching hierarchical composite data entities (e.g., data entities that may include multiple-attribute structures) in a concise, structured and efficient manner.

[0048] The inventors recognized that if the data that is used by the speech recognition system and/or natural language understanding system is hierarchical, then many advantages may be obtained by organizing that data into a hierarchical structure (or format), such as, for example, a tree.

[0049] In this manner, by organizing the hierarchical data into a hierarchical format, the data may be searched and/or processed using very regular mechanisms that drive the interaction with a user. Such mechanisms may include disambiguation and/or clarification mechanisms.

[0050] Such a hierarchical format is in stark contrast to the conventional method of using independent and un-correlated grammars.

[0051] The present invention, therefore, avoids requiring the development of an elaborate and numerous sets of simple grammars and/or a very lengthy and complex grammar. Further, since the grammars are not used, the markup language that has conventionally been written to implement those grammars also does not have to be written. In this manner, the present invention substantially reduces the amount of labor that is required to implement any particular application that operates upon hierarchical data.

[0052] Further, conventional speech recognition systems and natural language understanding systems have had to rely upon explicit disambiguation mechanisms. Such explicit disambiguation mechanisms have taken the form of simple and complex grammars and the implementing markup language that are written to explicitly disambiguate every possible recognized user utterance.

[0053] FIG. 2 illustrates a typical hardware configuration of a speech/natural language recognition system 200 for use with the invention and which preferably has at least one processor or central processing unit (CPU) 211.

[0054] The CPUs 211 are interconnected via a system bus 212 to a random access memory (RAM) 214, read-only memory (ROM) 216, input/output (I/O) adapter 218 (for connecting peripheral devices such as disk units 221 and tape drives 240 to the bus 212), user interface adapter 222 (for connecting a keyboard 224, mouse 226, speaker 228, microphone 232, and/or other user interface device to the bus 212), a communication adapter 234 for connecting an information handling system to a data processing network, the Internet, an Intranet, a personal area network (PAN), etc., and a display adapter 236 for connecting the bus 212 to a display device 238 and/or printer 240.

[0055] In addition to the hardware/software environment 200 described above, a different aspect of the invention includes a computer-implemented method for performing the above method. As an example, this method may be implemented in the particular environment discussed above.

[0056] Such a method may be implemented, for example, by operating a computer, as embodied by a digital data processing apparatus, to execute a sequence of machine-readable instructions. These instructions may reside in various types of signal-bearing media.

[0057] This signal-bearing media may include; for example, a RAM contained within the CPU 211, as represented by the fast-access storage for example. Alternatively, the instructions may be contained in another signal-bearing media, such as a magnetic data storage diskette 300 (FIG. 3), directly or indirectly accessible by the CPU 211.

[0058] Whether contained in the diskette 300, the computer/CPU 211, or elsewhere, the instructions may be stored on a variety of machine-readable data storage media, such as DASD storage (e.g., a conventional “hard drive” or a RAID array), magnetic tape, electronic read-only memory (e.g., ROM, EPROM, or EEPROM), an optical storage device (e.g. CD-ROM, WORM, DVD, digital optical tape, etc.), paper “punch” cards, or other suitable signal-bearing media including transmission media such as digital and analog and communication links and wireless. In an illustrative embodiment of the invention, the machine-readable instructions may comprise software object code, compiled from a language such as “C”, etc.

[0059] An exemplary embodiment of the present invention provides a method that represents a space of values of hierarchical composite data-structures (e.g., complex data entities) that may be used in speech and natural language understanding applications using trees that provide for easy representation, search, constraining and communication of this space.

[0060] In one example of an application in accordance with the present invention, data that identifies the location of airports may be organized based upon the hierarchical relationship of the data into a tree format.

[0061] For example, a user may utter “Springfield” and the system may recognize the utterance as corresponding to multiple nodes within the tree. A disambiguation mechanism may be used, if necessary, to infer the possible solution by enumerating the paths through each of the “Springfield” nodes to the resolving leaf nodes and further interact with the user to determine which of those inferred (implied) paths correspond to the airport that the user is seeking to identify. As an example, a disambiguation mechanism may be inferred based upon the hierarchical data format to enumerate each parent node of each path such as “Illinois,” “Ohio,” “Massachusetts,” etc. to allow the user to further determine which path is correct and which will iteratively lead to a specific leaf node that identifies with a specific airport.

[0062] For example, after receiving the user utterance “Springfield,” the system may then identify all possible paths which include a “Springfield” node and then back up (or down, if necessary) a level in the tree and ask the user to identify a state to disambiguate and/or clarify which “Springfield” corresponds to the correct airport.

[0063] In another example, a system may receive a recognized utterance of “New York State.” In that instance, the system recognizes that while the parent nodes for “New York State” are identified, the child nodes need to be disambiguated because there are several airports in “New York State.” In that example, the system may request the user to utter a county and/or city/town to further disambiguate the path that leads to the desired leaf node. Alternatively, the system may enumerate all of the child nodes and allow the user to select the appropriate child.

[0064] An exemplary embodiment of the present invention may rely upon graph interpolation mechanisms and/or tree interpolation mechanisms to perform the above-described disambiguation/clarification processes as well as other processes.

[0065] One exemplary tree representation in accordance with the present invention allows for an organized, hierarchical, and restrictive representation that is ideally suited for a recognizer, labeler and parser in a natural language understanding system (e.g., similar to that of FIG. 1) to achieve natural language interaction, representation, and disambiguation. The representation and mechanisms for restricting the space not only allow for the representation of the feature space in the recognizer and the parser, but also allow a dialog manager to efficiently operate on these data-structures.

[0066] For an N-order complex data entity, the depth of a tree representing this space for each of its leaves is “N” in accordance with an exemplary embodiment of the present invention. Each node in such a tree corresponds to the value of an attribute, and for a tree of depth N, any path from the root node to a leaf node determines exact values for each of those N attributes.

[0067] In a homogeneous tree in accordance with an exemplary embodiment of the present invention, each node of a given depth “M” will share the same attribute name “A_M.” Nodes may have homonym nodes, which are nodes having identical values (names), but which may have different prefix paths and, thus, different labels. Leaves have associated labels that may be presented to a dialog manager as the values of the attributes associated with such leaves.

[0068] Furthermore, with a tree representation in accordance with an exemplary embodiment of the present invention, a dialogue manager may execute restrictive searches (for example, for disambiguation or clarification) using restrictive directives that specify a sub-tree of the original tree. This representation is less restrictive to a grammar in the sense that, because the differentiating elements are clearly identified (e.g., the leaves), it is possible for a user to enunciate only the minimal amount of information that is required to identify each entity. Also this tree representation allows for a free order enunciation of the elements. In other words, the elements are not required to be enunciated in any particular order.

[0069] If homonym leafs and homonym nodes are collapsed, the tree may become a graph. Such a representation may be called a homonym graph representation. A homonym graph representation may be useful as a simple global space representation that may be unwrapped into a tree for the purpose of homonym disambiguation.

[0070] Disambiguation may be executed simply by identifying a set of homonym leaves and then identifying a set of differentiated paths that produce the set of homonym leaves using an exemplary embodiment of the present invention. The user may be queried by enumerating the set of paths.

[0071] A tree representation in accordance with an exemplary embodiment of the present invention may be easily implemented in markup language, graphically, as a data-structure, or any other associated representation.

[0072] In summary, the above described tree representation in accordance with an exemplary embodiment of the present invention may provide mechanisms for representing a set of hierarchical homogeneous named entities by means of a tree of depth N; the specification of intermediate or incomplete paths; specifying ambiguous paths (homonym leaves); identifying and communicating of such ambiguous paths; a user interaction for finding values for the N attributes of a data structure by expanding the above representation; basing the representation of hierarchies of grammars that are employed in automatic speech recognition and natural language understanding engines that contain constrained hierarchical knowledge of a domain, and that permit the enumeration of values for any attribute subsets in any order; representing hierarchical heterogeneous bodies of information using a single tree (i.e., not all the nodes of depth N, for every N, share the same attribute name); providing restrictive patterns; and for providing an algebra of restrictive patterns.

[0073] Consider the following set of addresses of a particular geography in the United States of a set of offices of a company called “Example Corp.”:

• [0074] Office A: Elmwood Street, Hawthorne, N.Y., US
• [0075] Office B: Broadway Street, Hawthorne, N.Y., US
• [0076] Office C: Broadway Street, Nyack, N.Y., US
• [0077] Office D: Fifth Avenue, Nyack, N.Y., US
• [0078] Office E: Fifth Avenue, Manhattan, N.Y., US
• [0079] Office F: Broadway Street, Manhattan, N.Y., US
• [0080] Office G: Madison Avenue, Albany, N.Y., US
• [0081] Office H: Park Avenue, Albany, N.Y., US

[0082] The above set of addresses represents a collection of records, each of which is a structure that includes named entities: a street name, a town or city name, a state name, and the country. In addition, a label identifies each record by its office name. This is called the label or annotation of the record. The above set is heterogeneous because not all the records include exactly the same set of attributes (e.g., Hawthorne is a town, while Albany is a City, and Manhattan is a Borough).

[0083] In a speech recognition application, if a user wants to identify a particular office, the user should give enough address information to produce an unambiguous identification of the record. This may be achieved in a directed dialog modality. For example, consider the following interaction:

• [0084] System: Which country?
• [0085] User: United States
• [0086] System: Which state?
• [0087] User. New York
• [0088] System: Which town or city?
• [0089] User: Hawthorne
• [0090] System: Which street?
• [0091] User: Broadway street
• [0092] System: The office you're looking for is Office B, in Broadway St. Hawthorne N.Y. USA.

[0093] In conventional speech systems, there are two approaches to representing the above set of complex named entities. The first approach uses an enumerative complex grammar and the second approach uses a union of a disjoint set of sub-grammars or flat grammars (e.g., a grammar for states, a grammar for cities, and a grammar for street names).

[0094] The following represents the above set of addresses as an enumerative grammar and annotations denoting the office name:

[0095]

	<ExampleCorp> = Elmwood Street, Hawthorne, NY, US {A}
	| Broadway Street, Hawthorne, NY, US {B}
	| Broadway Street, Nyack, NY, US {C}
	| Fifth Avenue, Nyack, NY, US {D}
	| Fifth Avenue, Manhattan, NY, US {E}
	| Broadway Street, New York, NY, US {F}
	| Madison Avenue, Albany, NY, US {G}
	| Park Avenue, Albany, NY, US {H};

• • [0096] The following represents the above set of addresses employing a disjointed set of grammars:

[0097]

	<ExampleCorp> = $Street $Town NY US;
	<Street> = Broadway {B,C,F}| Fifth {D,E} | Elmwood {A} |
	Madison {G} | Park {H};
	<Town> = Albany | Manhattan | Hawthorne | Nyack;

• • [0098] The following is an example of an interaction scenario in a complex grammar environment:
• [0099] System: Which Address?
• [0100] User: Broadway Street NY United States
• [0101] System: The office you are looking for is Office B.

[0102] While the interaction based on a complex grammar is more concise than an interaction based on flat grammars, building and maintaining complex grammars is substantially more laborious. Also, complex grammars are sensitive to input utterance word ordering.

[0103] Therefore, problems with conventional systems include: a need for explicit ambiguity resolution grammars because ambiguous leaves require explicit disambiguation grammars; these system are unrestrictive (e.g., “Fifth Avenue, Nyack” is syntactically permissible, but is a semantically incorrect utterance); heterogeneous sources are hard to integrate; enumerative grammars are inefficient and expensive; sufficient attribute subsets are not allowed; a fixed order is required because a variable order is exponentially difficult; a fixed number of interactions is required (for simple entity grammars); and manually intensive grammar creation and maintenance is required.

[0104] In stark contrast to these conventional systems and methods, an exemplary embodiment of the present invention provides a system and method that represents a set of labeled hierarchical complex named entities using a hierarchical tree. Each record in the list of labeled hierarchical complex named entities is associated with a leaf in the tree. Each leaf in the hierarchical tree is associated with its original label.

[0105] Each leaf i has a depth Di and, if all the leaves have the same depth and all the nodes j with depth Dj are associated to a single type of data, then the tree is said to be homogeneous. If any one of these conditions is not met, the tree is heterogeneous.

[0106] A path from a root node to a leaf node is an ordered set of connected nodes starting from the root node to the leaf node. An unambiguous sub-path is a subset of nodes of a path to a leaf node that exists in no other leaf node. A leaf name is an unambiguous sub-path if and only if no other leaf shares the same name (i.e., there are no homonyms).

[0107] An exemplary embodiment of the present invention represents a domain using the hierarchical tree described above, and allows for the efficient determination and identification of an unambiguous sub-path, homonyms, and disambiguation interactions.

[0108] As a tree, each node contains a “tag” attribute that corresponds to the attribute name of that node (for example “City”). A “tag.name” attribute has the value of such an attribute (for the same example, “Albany”). In addition, if a node is a leaf node, the attribute “tag.label” will also be associated to the node, and the value of the node will be the specific entity label.

[0109] FIG. 4 illustrates a hierarchical data model representation 400 of a homogeneous complex named entity domain in accordance with an exemplary embodiment of the present invention. In particular, FIG. 4 illustrates a tree 400 of a subset of the original domain that is described above. In this illustration only a homogeneous subset is illustrated where the attributes or tags are: country 402, state 404, county 406, town 408, and street 410.

[0110] A markup representation of a tree in accordance with an exemplary embodiment of the present invention includes tags whose names correspond to the values of the tag attributes in a corresponding tree representation. Then for each tag, the attribute name carries a value equal to the value of “tag.name” in the corresponding tree representation. For leaf nodes, the attribute label has the same value as the “tag.label” in the corresponding tree representation.

[0111] In extended markup language (XML markup), the complete (heterogeneous) hierarchical tree 400 is:

[0112]

	<tree name=“Offices of the Example Corp.”>
<country name =“US”>
	<statename =“NY”>
	<county name =“Westchester”>
	<town name =“Hawthorne”>
	<street name =“Broadway” label =“A” >
	<street name =“Elmwood” label =“B” >
	</town>
	</county>
	<county name =“Rockland”>
	<town name =“Nyack”>
	<street name =“Broadway” label=“C” >
	<street name =“Fifth avenue” label=“D” >
	</town>
	</county>
	<city name=“NYC”>
	<borough name=“Manhattan”>
	<street name=“Fifth Avenue” label=“E” >
	<street name=“Broadway” label=“F” >
	</borough>
	</city>
	<city name=“Albany”>
	<street name=“Madison” label=“G” >
	<street name=“Park” label=“H” >
	</city>
	</state>
</country>
	</tree>

[0113] Another exemplary embodiment of the present invention, in combination with the above representations, provides a method to restrict the search, or labeling of a domain into a smaller connected subset of nodes (i.e., a sub-tree). To achieve this, a restrict label is used to indicate an explicit sub-tree, a path, a sub-path, or simply a node that reduces the search space.

[0114] Specifically, restrictive directive formations may include an explicit, an implicit, or an algebraic restrictive directive formation. An explicit restrictive directive formation provides a complete sub-path from root to node set {Ni . . . Nj} and the sub-tree of all the children and descendants of this set is the sub-domain. An implicit restrictive directed formation does not provide a path from a root to node Ni. Rather, the prefix path is assumed (or implied). An algebraic restrictive directive formation first defines a set of operands (which are other trees or sub-trees) and then, using an operator attribute (see example below) manipulates these sets using set operations (union, complement, intersection) in a reverse polish notation way.

[0115] The following is an example of an explicit path restrictive directive:

[0116]

	<restrict tree=“Offices of the Example Corp.” name=“Outlets”>
<country name=“US”>
	<state name=“NY”>
	<county name=“Westchester”/>
	<county name=“Nyack”/>
	</state>
</country>
	</restrict>

[0117] The following is an example of an implicit path restrictive directive:

[0118]

	<restrict tree=“Offices of the Example Corp.” name=“Flagship”>
<street name=“Fifth Avenue” label=“E”/>
	</restrict>

[0119] The following is a first example of an algebraic restrictive directive:

[0120]

	<restrict tree=“Offices of the Example Corp.” name=“Set Alpha”
operator=Union>
	<operand name=“Outlets”/>
	<operand name=“Flagship”/>
	</restrict>

[0121] The following is another example of an algebraic restrictive directive:

[0122]

	<restrict tree=“Offices of the Example Corp.” name=“Set Beta”
operator=Complement>
	<operand name=“Set Alpha”/>
	</restrict>

[0123] FIG. 5 illustrates a hierarchical data model representation 500 of a heterogeneous hierarchical complex named entity domain in accordance with an exemplary embodiment of the present invention. FIG. 5 illustrates a complete heterogeneous tree 500 of the Example Corp. domain described above. Since FIG. 5 illustrates a heterogeneous tree, a null node should be used, since not all the nodes of depth N have the same “tag.name.”

[0124] The paths of the restrictive directive called “Outlets” (described above) are illustrated with solid black nodes. The leaves with vertical stripes represent the permissible labels of this restrictive directive. In horizontal stripes is a leaf node corresponding to a “Flagship” directive. A set “Alpha,” corresponds to a union of “Outlets” and “Flagship,” and include all of the non-white nodes, while the set “Beta,” described above corresponds to the non-colored nodes and their prefixes.

[0125] While the restrictive directive is described above as being used to identify sub-trees in a tree domain as an input mechanism, restrictive directives may also be used in output mechanisms.

[0126] The following description provides an example of how natural language generation may be mixed with tree representations and restrictive directives to identify sets of attributes that aid in disambiguation situations in accordance with the present invention.

[0127] FIG. 6 illustrates a homonym graph 600 of a heterogeneous complex named entity domain in accordance with an exemplary embodiment of the present invention. FIG. 6 illustrates the homonym graph representation 600 of the domain 500 of FIG. 5.

[0128] In this particular case, the homonym leaves (leaves with the same “tag.name” value) are collapsed. In addition, the city “New York City” 602 has been added in the state of “Mississippi” 604 (see the office with label I) 606, in order to illustrate that intermediate nodes may also collapse their homonym nodes. For this example, “New York City” 602 also has a “Broadway” street node 606 and a “Riverbank” street office node 608. In this case, the “Broadway” homonym leaf 606 has a list of labels in its “tag.label” attribute 610. Also note how a new null node 612 was added for the office label I.

[0129] An example of a communication transaction in which the graph that is illustrated by FIG. 6 is used in a natural language understanding system to disambiguate follows:

• [0130] System: Which office?
• [0131] User: The one in Broadway Avenue
• [0132] System: Select one: Hawthorne, Nyack, Manhattan or Albany?
• [0133] User: Nyack
• [0134] System: The office in Broadway avenue, in Nyack, N.Y., is office number C

[0135] In this example, the system identifies a set of labels {A,C,F,H,I} when the node 606 of “Broadway” is mentioned in the first interaction turn. Because “Broadway” 606 is a homonym node, disambiguation needs to take place, and, thus, a backoff to depth 3 is executed: note how the null nodes backed off another level to a non-null node.

[0136] In accordance with an exemplary embodiment of the present invention, trees and grammars are efficiently organized in a hierarchy.

[0137] In an exemplary embodiment of the invention, each layer of the hierarchy is associated with an attribute. A Tree/Grammar of order M has M layers (e.g., levels), and thus M attributes where M is the number of layers that need to be traversed in order to reach a leaf.

[0138] In an exemplary embodiment of the invention, leaves are terminal nodes and specify a “complete path.” In a complete path all of the M attributes have values. A complete path may be expressed as a list of M attribute value pairs. An unambiguously completable path contains a subset of the M attributes, including one non-ambiguous leaf node, which can be uniquely traced back to the root node, thus forming a completable path.

[0139] In another exemplary embodiment of the present invention, a “path prefix” specifies an incomplete path from the root to a given non-leaf node. A path-prefix or path segment of order N (N<M) may be uniquely specified by a sequence of attribute values for each successive node layer.

[0140] In yet another exemplary embodiment of the present invention, nodes may have duplicate names within the same hierarchy level, however, their path prefixes should differ in order to be distinguishable. Two leaf nodes are synonyms if they share the same name, but different prefixes.

[0141] In a further exemplary embodiment of the present invention, if a leaf node has a unique value, then its complete path may be unambiguously inferred.

[0142] In another exemplary embodiment of the present invention, if a leaf node has at least one duplicate value or synonym (R>1 synonyms), and R denotes the duplicity order, then there may be as many as R distinguishable path prefixes.

[0143] With an exemplary embodiment of the present invention, a set of R distinguishable path prefixes defines a sub-tree. In a disambiguation task, this sub-tree is called a disambiguation sub-tree of order R. When disambiguating a set of synonyms of order R, their set of distinguishable prefix paths defines a disambiguation sub-tree. A disambiguation strategy finds and utilizes the attribute that distinguishes them.

[0144] An exemplary embodiment of the present invention provides a method for decoding using a grammar as follows:

• • [0145] hierarchical grammar (1,2) is sent to the decoder. After capturing the user's input,
  • [0146] if the decoder identifies at least a terminal node then determine the set of
  • [0147] distinguishable paths from such terminal. If the user's input only provides an
  • [0148] incomplete path send to DM/Voice Browser. Prompt user with a disambiguation
  • [0149] prompt and activate only disambiguative subtree.
    • [0150] Prompt #1
      • [0151] Input is: (a) complete
        • [0152] a.1 complete and unambiguous
        • [0153] a.2 complete but R confusable
      • [0154] (b) incomplete
        • [0155] b.1 subpath is incomplete and unambiguous
        • [0156] b.2 subpath is incomplete and ambiguous

[0157] Another exemplary embodiment of the present invention provides a method for performing constrained searches using sub-tree templates or restrictive directives.

[0158] An exemplary embodiment of the present invention provides an algebra of such restrictive directives.

[0159] Another exemplary embodiment of the present invention provides a method for graph representation of homonym trees.

[0160] Yet another exemplary embodiment of the present invention provides a method for decoding any subset of attributes, in any order based on the graph representation mentioned above.

[0161] FIG. 7 illustrates a flowchart for a control routine 700 in accordance with an exemplary embodiment of the present invention. The control routine starts at step 710 and continues to step 720. In step 720, the control routine generates a hierarchical tree and continues to step 730. In step 730, the control routine initiates a dialog with a user by receiving an utterance from a user and continues to step 740. In step 740, the control routine recognizes the utterance and continues to step 750 where the control routine identifies all nodes that correspond to the recognized utterance. The control routine then continues to step 760 where the control routine determines whether there is any ambiguity in the particular leaf that corresponds to the recognized utterance. If, in step 760, the control routine determines that there is no ambiguity between leaf nodes, then the control routine outputs the identified leaf node in step 770 and continues to step 780 where the control routine returns control to the routine that called the control routine of FIG. 7.

[0162] If, however, in step 760, the control routine determines that there are ambiguous leaves that correspond to the recognized utterance, then the control routine continues to step 790. In step 790, the control routine infers a disambiguation mechanism based upon the hierarchical nature of the tree and returns to step 730 where another utterance is received in response to the inferred disambiguation mechanism.

[0163] It is understood by those of ordinary skill in the art that step 720 of generating the hierarchical tree may not be necessary as the hierarchical tree may have already been generated. In that instance, step 720 may be omitted.

[0164] It is also understood by those of ordinary skill in the art that the disambiguation mechanism that is inferred by step 790 may include any of the disambiguation mechanisms that have been described above, as well as other disambiguation mechanisms as long as the appropriate mechanism is inferred based upon the structure of the hierarchical format of the tree.

[0165] Further, while the above description has been provided in relation to speech and/or natural language systems, one of ordinary skill in the art understands that the hierarchical tree and the dialog interaction management that utilizes such a hierarchical tree is useful in any type of dialog, such as in a chat interaction, a speech recognition system, a natural language understanding system and the like.

[0166] While the invention has been described in terms of several exemplary embodiments, those skilled in the art will recognize that the invention can be practiced with modification.

[0167] Further, it is noted that, Applicants' intent is to encompass equivalents of all claim elements, even if amended later during prosecution.