Syntactic parser assisted semantic rule inference

BACKGROUND OF THE INVENTION

0001Achieved advances in speech processing and media technology have led to a wide use of automated user machine interaction across different applications and services. Using an automated user machine interaction approach, businesses may provide customer services and other services with relatively inexpensive cost.

SUMMARY OF THE INVENTION

0002Embodiments of the present invention generate annotated data for use in a natural language understanding (NLU) system. An example embodiment generates the annotated data by generalizing the semantic rules learned from an annotated sample by employing a syntactic parser.

0003According to at least one example embodiment, a method of the present invention generates annotated data for use in a NLU system by first parsing, by a computer device, an input annotated phrase. Next, a syntactic tree reflecting a grammatical structure of the parsed phrase is generated. The method according to such an embodiment concludes by generating one or more alternative versions of the input annotated phrase based on the generated syntactic tree in a manner preserving alignment between expressions and corresponding annotations in the input annotated phrase in the one or more alternative versions that are generated.

0004An alternative embodiment of the present invention further comprises validating the one or more alternative versions of the input annotated phrase. According to such an embodiment, validating the one or more alternative versions of the input annotated phrase comprises checking an alternative version, of the one or more versions, against a database of non-annotated phrases and validating the alternative version upon finding a match in the database of non-annotated phrases. According to yet another embodiment of the present invention, validating the one or more alternative versions of the input annotated phrase includes displaying the one or more versions of the input annotated phrase to a user for manual validation.

0005According to an embodiment of the present invention, generating the one or more alternative versions of the input annotated phrase includes applying one or more transformation rules to nodes of the generated syntactic tree. In such an embodiment of the present invention, applying one or more transformation rules to the nodes of the syntactic tree includes reordering expressions of the input annotated phrase within an alternative version of the one or more versions generated, the expressions associated with nodes of the generated syntactic tree. In yet another embodiment, applying one or more transformation rules to nodes of the syntactic tree includes omitting an expression of the input annotated phrase within an alternative version of the one or more versions generated, wherein the expression is again associated with one or more nodes of the generated syntactic tree. According to an embodiment that includes omitting an expression of the input annotated phrase within an alternative version of the one or more phrases generated, the one or more transformation rules may include a rule associated with a language structure. Yet further still, according to at least one example embodiment, applying the one or more transformation rules to nodes of the syntactic tree includes inserting an expression within a version of the one or more versions generated. According to an embodiment, the one or more transformation rules includes a transformation rule learned based on a database of annotated phrases. In yet another embodiment, the one or more transformation rules includes a rule associated with a language structure.

0006A further embodiment of the present invention is directed to an apparatus for generating annotated data for use in a NLU system. In such an embodiment the apparatus comprises a processor and a memory with computer code instructions stored thereon. The processor and the memory with the computer code instructions are configured to cause the apparatus to: parse an input annotated phrase, generate a syntactic tree reflecting a grammatical structure of the parsed phrase, and generate one or more alternative versions of the input annotated phrase based on the generated syntactic tree in a manner preserving alignment between expressions and corresponding annotations in the input annotated phrase in the one or more alternative versions that are generated.

0007In a further embodiment of the apparatus, the processor and the memory with the computer code instructions are further configured to cause the apparatus to validate the one or more alternative versions of the input annotated phrase. In such an embodiment, validating the one or more alternative versions of the input annotated phrase may comprise the processor and the memory with the computer code instructions being further configured to cause the apparatus to check an alternative version of the one or more versions against a database of non-annotated phrases and validate the alternative version upon finding a match in the database of non-annotated phrases. In yet another embodiment, the apparatus comprises computer code instructions that are further configured to cause the apparatus to validate the one or more alternative versions of the input annotated phrase by displaying the one or more versions of the input annotated phrase to a user for manual validation.

0008According to an embodiment of the apparatus, generating one or more alternative versions of the input annotated phrase, the processor and the memory with computer code instructions are further configured to cause the apparatus to apply one or more transformation rules to nodes of the syntactic tree. In such an embodiment, applying rules to nodes of the syntactic tree may comprise reordering expressions of the input annotated phrase within an alternative version of the one or more generated versions, wherein the expression is associated with nodes of the syntactic tree. Yet further still, in an apparatus configured to apply one or more transformation rules to nodes of the syntactic tree, the apparatus may be configured to omit an expression of the input annotated phrase within an alternative version of the one or more versions that are generated, wherein the expression is associated with nodes of the generated syntactic tree. According to at least one embodiment, in applying one or more transformation rules to nodes of the syntactic tree, the processor and the memory with the computer code instructions cause the apparatus to insert an expression within a version of the one or more generated versions.

0009Yet another embodiment of the present invention is directed to a cloud computing implementation for generating annotated data for use in a NLU system. Such an embodiment is directed to a computer program product executed by a server in communication across a network with one or more clients. In such an embodiment, the computer program product comprises a computer readable medium that comprises program instructions which, when executed by a processor causes: parsing an input annotated phrase, generating a syntactic tree reflecting a grammatical structure of the parsed phrase, and generating one or more alternative versions of the input annotated phrase based on the generated syntactic tree in a manner preserving alignment between expressions and corresponding annotations in the input annotated phrase in the one or more alternative versions that are generated.

BRIEF DESCRIPTION OF THE DRAWINGS

0010The foregoing will be apparent from the following more particular description of example embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments of the present invention.

0011<figref idref="DRAWINGS">FIG. 1A</figref> is a simplified block diagram of a system implementing an example embodiment of the present invention.

0012<figref idref="DRAWINGS">FIG. 1B</figref> is a flowchart depicting a method of generating annotated data for use in a natural language understanding (NLU) system according to an embodiment of the present invention.

0013<figref idref="DRAWINGS">FIG. 2</figref> depicts a syntactic tree that may be generated in performing an embodiment of the present invention.

0014<figref idref="DRAWINGS">FIG. 3</figref> illustrates an alternative phrase generated using a swap that may be determined according to an example embodiment.

0015<figref idref="DRAWINGS">FIG. 4</figref> is a visual depiction of an annotation tree that may be utilized in an embodiment of the present invention.

0016<figref idref="DRAWINGS">FIG. 5</figref> illustrates example grammar rules generated from the annotation tree of <figref idref="DRAWINGS">FIG. 4</figref>.

0017<figref idref="DRAWINGS">FIG. 6</figref> is a visual depiction of an annotated phrase generated according to an embodiment of the present invention.

0018<figref idref="DRAWINGS">FIG. 7A</figref> depicts an example annotated sentence that may be utilized in an embodiment of the present invention.

0019<figref idref="DRAWINGS">FIG. 7B</figref> is syntactic tree generated in carrying out an example embodiment.

0020<figref idref="DRAWINGS">FIG. 7C</figref> is an example of an alternative sentence generated according to at least one embodiment.

0021<figref idref="DRAWINGS">FIG. 7D</figref> is a visual depiction of laying the generated alternative sentence of <figref idref="DRAWINGS">FIG. 7C</figref> on the semantic annotation of <figref idref="DRAWINGS">FIG. 7A</figref>.

0022<figref idref="DRAWINGS">FIG. 8A</figref> is a visual depiction of an annotation tree.

0023<figref idref="DRAWINGS">FIG. 8B</figref> is a syntactic parse tree generated using the annotated dialog of <figref idref="DRAWINGS">FIG. 8A</figref>.

0024<figref idref="DRAWINGS">FIG. 8C</figref> is a proposed alternative sentence based upon the annotation tree in <figref idref="DRAWINGS">FIG. 8A</figref> and the syntactic parse tree of <figref idref="DRAWINGS">FIG. 8B</figref>.

0025<figref idref="DRAWINGS">FIG. 9</figref> is a simplified block diagram of a computer system in which the present invention may be embodied.

0026<figref idref="DRAWINGS">FIG. 10</figref> is a simplified diagram of a computer network environment in which an embodiment of the present invention may be implemented.

DETAILED DESCRIPTION OF THE INVENTION

0027A description of example embodiments of the invention follows.

0028Natural language understanding (NLU) engines perform better when they are trained with a very large amount of data. However, large amounts of training data is not always available. Embodiments of the present invention overcome the shortcomings of prior art methods and increase a NLU engine's performance when little training data is available. Embodiments of the present invention generalize the semantic rules learned from an annotated sample by employing a syntactic parser. This enables the NLU engine to learn more from each training sentence, and the NLU engine's performance increases even when little training data is available. One or more embodiments of the present invention combine the simplicity of semantic annotations with the power of a syntactic parser, thus using both a syntactic and semantic approach to increase NLU engine performance.

0029<figref idref="DRAWINGS">FIG. 1A</figref> is a simplified block diagram illustrating a system <b>15</b> implementing an example embodiment of the present invention. The system <b>15</b> comprises a syntactic parser <b>16</b>, an alternative sentence generator <b>17</b>, and a NLU engine <b>18</b>. The various components of the system <b>15</b> are communicatively coupled and function to generate alternative annotated phrases <b>21</b> for use by the NLU engine <b>18</b>. The syntactic parser <b>16</b> receives a sentence and the sentence's semantic annotation <b>19</b>. The syntactic parser <b>16</b> decomposes the sentence <b>19</b> into its syntactic parts, i.e., verb phrases; noun phrases, prepositional phrases, etc., and generates a syntactic tree <b>20</b> using the same. Next, after receiving the syntactic tree <b>20</b>, the alternative sentence generator <b>17</b> performs transformations to the syntactic tree <b>20</b>, e.g., swaps or removals of some syntactic subtrees, in order to generate multiple alternative formulations of the original sentence. The alternative sentence generator <b>17</b> may also receive the annotated phrase <b>19</b> and use the same in generating the alternative sentences. For each of these alternative sentences, the same syntax transformations are repeated onto the original sentence's semantic annotation by the alternative sentence generator <b>17</b> in order to infer the alternative sentence's annotation. In this way a single annotated sentence is used to generate multiple alternative sentences <b>21</b>, each of them with their appropriate semantic annotations. The alternative annotated phrases <b>21</b> are then provided to the NLU engine <b>18</b>, to be used for such things as training the NLU engine <b>18</b>. The terms modify, transform, transduce, and any forms thereof may be used interchangeably herein.

0030<figref idref="DRAWINGS">FIG. 1B</figref> illustrates a flowchart of an example method <b>100</b> for generating annotated data for use in a NLU system. The method <b>100</b> begins by parsing, by a computer device, an input annotated phrase (<b>110</b>). The annotated phrase may be annotated in any way as is known in the art. For example, the annotation may be in the form of an annotation tree as depicted in <figref idref="DRAWINGS">FIG. 4</figref> and described hereinbelow. The annotated phrase may be obtained through any means known in the art. For example, if the method <b>100</b> is being performed by a computing device, the annotated phrase may be obtained from a local disk, a remote storage device, and/or a database. Further, in such an example, the annotated phrase may be obtained in response to a user command or may be obtained automatically, semi-automatically, or on some periodic basis. Further still, the data may be obtained from any point or combination of points communicatively coupled, via any means known in the art, to a computing device executing the method <b>100</b>.

0031After parsing the input annotated phrase (<b>110</b>), next, a syntactic tree is generated that reflects the grammatical structure of the parsed phrase (<b>111</b>). The generated syntactic tree may be as shown in <figref idref="DRAWINGS">FIG. 2</figref>. Further, the syntactic tree may be generated (<b>111</b>) using a parser, such as the syntactic parser <b>16</b>. The parser can be internal, external, or even remotely located in relation to a tool executing the method <b>100</b>.

0032The final operation of the example method <b>100</b> is to generate one or more alternative versions of the input annotated phrase based on the generated syntactic tree (<b>112</b>). When generating the alternative versions (<b>112</b>), alignment between expressions and corresponding annotations in the input annotated phrase are preserved in the one or more alternative versions that are generated. In such a way, an expression and its associated annotation are maintained in the newly generated input annotated phrases. For example, if the expression “Boston” is annotated as “DEPARTURE” in the original sentence, the expression “Boston” will keep the annotation “DEPARTURE” in the alternative version of the original sentence that is generated. According to an embodiment, generated alternative phrases may be added to a database or other storage device that is accessible to a NLU system for training.

0033According to an embodiment of the method <b>100</b>, the one or more alternative versions of the input annotated phrases are generated (<b>112</b>) by first modifying the syntactic tree generated at block <b>111</b> to generate an alternative sentence. The same modification is then applied to the annotation of the original sentence to generate the annotation of the alternative sentence.

0034The method <b>100</b> may further comprise generating grammar rules, such as the grammar rules illustrated in <figref idref="DRAWINGS">FIG. 5</figref>, for the annotated phrase, and/or alternative versions of the annotated phrase that are generated. These grammar rules may be generated using an annotation tree associated with the phrase and a NLU system that comprises a collection of processes that, compared to manually building NLU systems, greatly speeds up building NLU systems and also produces a more accurate NLU system by exploiting various statistical inferences, automatic quality checks, and automatic generation of NLU grammars and statistical engines. Such a collection of processes may be referred to herein as a QuickNLU™. Generating such grammar rules may be done as described in U.S. patent application Ser. No. 13/941,783, the contents of which are herein incorporated by reference.

0035In an alternative embodiment, an alternative phrase generated at block <b>112</b> of the method <b>100</b> may be used in the method <b>100</b> to generate additional alternative phrases. In such an embodiment, the generated alternative phrase is provided, as feedback, to a computing device executing the method <b>100</b> and additional phrases are generated using said alternative phrase.

0036An embodiment of the method <b>100</b> further comprises validating the one or more versions of the input annotated phrase. According to such an embodiment of the method <b>100</b>, validating the one or more versions comprises checking an alternative version of the one or more versions against non-annotated phrases and considering the alternative version validated upon finding a match in the database of non-annotated phrases. In such an embodiment, the non-annotated phrases may be stored on a database or any other storage device known in the art. Thus, a generated alternative phrase is considered valid if such a phrase is found in the database. Such an embodiment may further comprise adding one or more validated phrases to a database or other storage device that can be accessed or provided to a NLU system for training. Further, while the term “database” is used herein, embodiments of the present invention may store data, such as the generated annotated phrases, in any format on any device known in the art.

0037In an alternative embodiment of the method <b>100</b>, validating the one or more alternative versions of the input annotated phrase comprises displaying the one or more versions of the input annotated phrase to a user for manual validation. In such an embodiment, the phrase may be displayed to a user via any means known in the art. For example, the one or more versions may be presented to a user in a graphical user interface (GUI) on a display device that is communicatively coupled to a computing device that is executing the method <b>100</b>. In such an embodiment, the generated phrases may be displayed via a display device that is located remotely or locally in relation to said computing device.

0038According to an embodiment of the method <b>100</b>, generating the one or more alternative versions of the input annotated phrase (<b>112</b>) includes applying one or more transformation rules to nodes of the syntactic tree generated at block <b>111</b> of the method <b>100</b>. In an example embodiment, applying one or more transformation rules may comprise reordering expressions of the input annotated phrase within an alternative version of the one or more versions. In such an embodiment, the expressions are associated with nodes of the syntactic tree. Reordering expressions may comprise swapping one or more expressions with another expression to generate the alternative version of the input annotated phrase. In yet another embodiment, applying one or more transformation rules to nodes of the syntactic tree to generate the one or more alternative versions of the input annotated phrase includes omitting an expression of the input annotated phrase. In such an embodiment, the expressions are associated with a node of the syntactic tree that was generated at block <b>111</b> of the method <b>100</b>. In a further embodiment of the method <b>100</b>, the one or more transformation rules may include a rule that is associated with a language structure. In such an embodiment, the language structure rules may be any rules associated with the language as are known in the art. In yet another embodiment of the method <b>100</b> that comprises applying transformation rules to nodes of the syntactic tree, applying one or more transformation rules comprises inserting an expression within a version of the one or more versions that are generated. In such an embodiment, the inserted expressions may come from a database and/or local storage device that is communicatively coupled to a computing device executing the method <b>100</b>. For example, an insertion transformation rule may add an adverb, adjective, or conjunctive phrase (“and” and “or”). The insertion rule may be used if there is a certain pattern in the syntactic tree. While numerous transformation rules have been described herein, these rules are merely examples, and transformation rules can be quite arbitrary and do not necessarily only include insertion, deletion, or swapping. Transformation rules may be based on any pattern in a syntactic tree. Further, the transformation rules may be “rewriting rules” and may pertain to more complex examples, such as “right node raising.” For example, the sentence, “I want to go to Montreal” may be transformed into “I want to but she doesn't want to go to Montreal.”

0039In another embodiment of the method <b>100</b>, the one or more transformation rules comprise(s) a transformation rule learned based on a database of annotated phrases. In other words, a transformation rule is learned from analyzing other annotated phrases. According to such an embodiment, the method <b>100</b> may include determining one or more transformation rules based upon annotated phrases that are stored on a database or any other storage device.

0040According to an embodiment, the input annotated phrase (<b>110</b>) may be obtained from a database of phrases, i.e., a corpus. In another embodiment, the one or more generated alternative phrases may be added to a corpus. According to such an embodiment, a generated alternative phrase may not be added to the corpus until the sentence is validated. A further embodiment of the method <b>100</b> may comprise training a NLU engine using the generated alternative version of the input annotated phrase.

0041<figref idref="DRAWINGS">FIG. 2</figref> illustrates a syntactic tree <b>220</b> that may be generated according to an embodiment of the present invention. The syntactic tree <b>220</b> is generated using the example sentence “I would like to go from Montréal to New York tomorrow.” The syntactic tree <b>220</b> illustrates the aforementioned sentence broken down into its various parts of speech and the relationship between these various components. The syntactic tree <b>220</b> shows that from the root <b>221</b> the sentence “I would like to go from Montréal to New York tomorrow” is composed of the noun phrase (NP) <b>223</b> and the verb phrase (VP) <b>222</b>. The noun phrase <b>223</b> is further broken down to contain the personal pronoun (PRP) <b>225</b>. The verb phrase <b>222</b> is then broken into the modal verb (MD) <b>226</b> and the additional verb phrases as shown in <figref idref="DRAWINGS">FIG. 2</figref>. The sentence and its various components are further broken down into their constituent parts to form the syntactic tree <b>220</b>. As shown in <figref idref="DRAWINGS">FIG. 2</figref>, the portions, IN (preposition or subordinating conjunction) <b>228</b>, JJ (adjective) <b>227</b>, and NN (singular noun) <b>224</b> further illustrate various constituent parts of the sentence that form the syntactic tree <b>220</b>. Other various constituent parts of a syntactic tree may include a VB (base form verb), PP (prepositional phrase), or TO (to Just to), amongst others.

0042As described hereinabove, the method <b>100</b> comprises parsing an input annotated phrase (<b>110</b>). <figref idref="DRAWINGS">FIG. 2</figref> illustrates components of a sentence that may be determined when parsing (<b>110</b>) the sentence “I would like to go from Montréal to New York tomorrow.” The method <b>100</b> further comprises generating a syntactic tree reflecting a grammatical structure of the parsed phrase (<b>111</b>). The syntactic tree <b>220</b> is an example of a syntactic tree that illustrates the grammatical structure of a sentence, in this case, “I would like to go from Montréal to New York tomorrow,” that may be generated at block <b>111</b> of the method <b>100</b>.

0043A syntactic parsing and associated syntactic tree can be used to generate alternatives of a sentence. Embodiments of the present invention can use defined lists of modifications, e.g., permutations or removals, on a generated syntactic tree to generate alternatives of a sentence. For example, an embodiment may swap a prepositional phrase and a noun phrase when they are alone on a branch within a potential starting verb phrase. In another example embodiment, a prepositional phrase or noun phrase may be erased (omitted). For example, the aforementioned rules may be used on the sentence of the syntactic tree <b>220</b> to generate the following alternative sentences: “I would like to go tomorrow from Montréal to New York,” “I would like to go tomorrow to New York from Montréal,” “I would like to go to New York from Montréal tomorrow,” “I would like to go tomorrow from Montréal,” “I would like to go tomorrow to New York,” “I would like to go tomorrow to New York from Montréal,” “I would like to go to New York tomorrow,” “I would like to go to New York,” “I would like to go tomorrow,” amongst others. In this manner, multiple new sentences can be generated by applying modifications to a syntactic tree.

0044Further, embodiments of the present invention may trace the modifications, e.g., swaps and removals, that were done on the initial sentence to generate the alternative sentence. For example, the alternative sentence, “I would like to go tomorrow from Montréal to New York,” may be represented by the form shown in <figref idref="DRAWINGS">FIG. 3</figref>. <figref idref="DRAWINGS">FIG. 3</figref> illustrates the alternative sentence <b>330</b> generated using the original sentence <b>331</b>. The alternative sentence <b>330</b> is depicted as the original sentence <b>331</b> with the swap <b>332</b>. The swap <b>332</b> illustrates that the original sentence <b>331</b> is transformed into the alternative sentence <b>330</b> “I would like to go tomorrow from New York to Montréal.” Thus, embodiments of the present invention generate alternative sentences and may track the modifications used to generate said alternative sentences. These alternative sentences and corresponding modifications may be stored using any means known in the art, for example, such information may be stored in the memory of a computing device executing an embodiment of the present invention.

0045Embodiments of the present invention utilize an annotated sentence to generate one or more alternative annotated sentences. <figref idref="DRAWINGS">FIG. 4</figref> illustrates an example of an annotated sentence, annotated in the form of an annotation tree <b>440</b>. <figref idref="DRAWINGS">FIG. 4</figref> illustrates the annotation tree <b>440</b> of the sentence “I would like to go from Montréal to New York tomorrow” <b>442</b>. The annotation tree <b>440</b> illustrates that the category I_TRAVEL <b>441</b> comprises the sentence <b>442</b>. The sentence <b>442</b> is further annotated with the DEPARTURE_LOCATION annotation <b>443</b>, ARRIVAL_LOCATION annotation <b>447</b>, and WHEN annotation <b>451</b>. The annotation tree <b>440</b> further breaks down the DEPARTURE_LOCATION annotation <b>443</b> into the LOCATION annotation <b>444</b> and CITY annotation <b>445</b>, and indicates that the DEPARTURE_LOCATION, LOCATION, and CITY annotations apply to the expression Montréal <b>446</b> in the sentence <b>442</b>. The ARRIVAL_LOCATION annotation <b>447</b> is similarly broken down in the annotation tree <b>440</b> to include the LOCATION annotation <b>448</b> and CITY annotation <b>449</b>, which are all annotations of the expression New York <b>450</b> in the sentence <b>442</b>. The annotation tree <b>440</b> further indicates that the term “tomorrow” <b>452</b> has the corresponding annotation WHEN <b>451</b>.

0046An ontology may be used to generate alternative sentences. For example, an ontology may provide information on what is a date expression, e.g., WHEN. The information may then be used to generate an alternative sentence so the alternative sentence does not have to include the word “tomorrow,” and may instead use any date expression from the ontology.

0047<figref idref="DRAWINGS">FIG. 5</figref> illustrates grammar rules <b>555</b> that can be generated according to principles known in the art, such as those described in U.S. patent application Ser. No. 13/941,783, using the annotation tree <b>440</b>. For example, the grammar rules <b>555</b> may be generated using the QuickNLU™ as described hereinabove.

0048The process for generating alternative sentences of an input annotated phrase, according to several embodiments of the present invention, is described hereinabove. However, these alternative sentences, generated by making modifications to the syntactic tree, need corresponding annotations. <figref idref="DRAWINGS">FIG. 6</figref> illustrates the annotated sentence <b>660</b> generated according to principles of the present invention. The annotation is developed by laying the alternative sentence <b>330</b> on top of the annotation tree <b>440</b>, thereby performing the same modification, e.g. swap <b>332</b>, to the annotation tree <b>440</b> that was used to generate the alternative sentence <b>330</b>, thus generating the annotated sentence <b>660</b>. This process may be performed at block <b>112</b> of the method <b>100</b>.

0049From the initial sentence annotation, embodiments of the present invention generate the annotation of the new sentences and, thus, can generate the semantic grammar rules of example alternative sentences. Embodiments of the present invention may employ a process to determine if there are permutations within the annotated mentions that preserve the inner mention order, but comply to the edition of the alternative sentence. For example, the alternative sentence <b>330</b> laying on top of the annotation of the permutation of the alternative <b>440</b>, does not break any annotation sub-tree and is, therefore, an accepted edit. Thus, the new annotation is given by the permutation shown in <figref idref="DRAWINGS">FIG. 6</figref>.

0050Methods used in embodiments of the present invention can be generalized when swap shall invoke swap at multi-level (but not across level swaps). Such an example is described herein below in relation to <figref idref="DRAWINGS">FIGS. 7A-D</figref>. While a relatively simple example is described herein, i.e. the swap of the expression “tomorrow,” this example yields many non-trivial alternatives and the door is open to use the semantic annotation with, in the background, the power of an ontology and a syntactic parser.

0051An alternative embodiment may also generate one grammar rule from all alternatives using the semantic rule, such as grxml, syntax, as shown in <figref idref="DRAWINGS">FIG. 5</figref>, such as <one-of>, etc. This may yield more condensed and powerful grammars. Further still, embodiments of this invention may be performed on the fly, i.e., during run time, or may utilize pre- and/or post-processing. The example annotated alternative sentences described herein may be utilized to train NLU systems; however, embodiments of the present invention are not so limited and may be used train other engines, e.g., a statistical engine. Embodiments of the present invention may be used to help training models that generalize better, especially at low levels of training. For example, embodiments of the present invention may be used to train a statistical classifier that identifies the intention of a speaker of a sentence. Additional data created in this way likely results in a better classifier.

0052As described herein, embodiments of the present invention may utilize various transformation rules. These transformation rules may be used to modify the syntactic tree that is generated at block <b>111</b> of the method <b>100</b>. For example, various rules may include permutation of the verb phrase, prepositional phrase, and noun phrase siblings in the syntactic tree. Further transformation rules may include removal of one or more verb phrases, prepositional phrases, and noun phrases in the syntactic parse tree. Further still, embodiments of the present invention may allow permutations and removals of syntax sub-trees that correspond to top-level mentions only in the annotation tree. Such transformation rules may allow for a significant increase in performance when using the NLU engine assisted by the syntactic parser. Since the strength of the syntactic NLU engine is to add alternatives for sentences in the training set, one can expect both current and syntax-assisted engines to converge as the training set grows larger. However, the syntax-assisted engine risks over-generating invalid syntactic alternatives by removing a piece of a sentence that is essential to convey the original intent thereof. One potential method for overcoming such a problem is described hereinbelow in reference to <figref idref="DRAWINGS">FIGS. 8A-C</figref>.

0053The previous example described hereinabove showed an example of a top-level swap in an annotation tree. However, embodiments of the present invention can extend this process to lower levels of the annotation tree. <figref idref="DRAWINGS">FIGS. 7A-D</figref> illustrate the process of generating an alternative annotated sentence by employing a lower-level swap in the annotation tree. The example sentence used with reference to <figref idref="DRAWINGS">FIGS. 7A-D</figref> is “I want the earliest flight on Friday.” <figref idref="DRAWINGS">FIG. 7A</figref> illustrates an annotated sentence <b>770</b> with the top-level mention <b>771</b> and two lower level mentions <b>772</b> and <b>773</b>. According to embodiments using the principles of the present invention, the annotated sentence is then parsed, and a syntactic tree <b>774</b> is generated, as shown in <figref idref="DRAWINGS">FIG. 7B</figref>. <figref idref="DRAWINGS">FIG. 7C</figref> illustrates an alternative sentence <b>775</b> wherein the prepositional phrase “on Friday” <b>776</b> is removed <b>777</b>, yielding the alternative sentence “I want the earliest flight.” <figref idref="DRAWINGS">FIG. 7D</figref> illustrates the generated annotated phrase <b>778</b> for the alternative sentence <b>775</b>. The annotated alternative sentence <b>778</b> is obtained by mapping the modification <b>777</b> of the syntactic tree onto the original annotation tree. In this example, the upper level mention <b>771</b> and the first lower-level mention <b>772</b> are maintained while the second lower-level mention <b>773</b> is removed <b>777</b>, thus generating a valid annotation <b>778</b> of the sentence “I want the earliest flight.” This process can be repeated for other syntactic swaps or removals to generate other alternative sentences.

0054<figref idref="DRAWINGS">FIGS. 8A-C</figref> illustrate example risks of overgeneralizing a sentence by removing a key part of a sentence that conveys an intent. The example sentence used in <figref idref="DRAWINGS">FIGS. 8A-C</figref> is “show me my checks.” The sentence has an annotation tree <b>880</b> shown in <figref idref="DRAWINGS">FIG. 8A</figref>, which has the intent “INTENTION_REQUEST_CHECK <b>881</b>. According to an embodiment according principles of the present invention, the sentence is then parsed, and the syntactic tree <b>882</b>, with the clause with subject-verb inversion (SINV) comprising the verb phrase <b>883</b> and noun phrase <b>884</b>, is generated. <figref idref="DRAWINGS">FIG. 8C</figref> shows an alternative sentence <b>885</b> with the noun phrase <b>884</b> removed <b>886</b>. However, the resulting alternative sentence <b>885</b>, “show me,” has lost the original intent of INTENTION_REQUEST_CHECK <b>881</b> and is not a valid alternative. One way to prevent generation of this invalid alternative is to remove only syntactic subtrees that contain mentions in the annotation tree. One can assume that any word outside of the mentions is associated with the intent and only allow removal of the syntactic subtree if the annotation tree contains one or more mentions. Since there are no mentions in this example, then neither the verb phrase nor noun phrase subtrees can be removed to generate alternative sentences, and the false alternative would not be generated.

0055<figref idref="DRAWINGS">FIG. 9</figref> is a simplified block diagram of a computer-based system <b>990</b> that may be used to generate annotated data for use in a NLU system according to an embodiment according to the principles of the present invention. The system <b>990</b> comprises a bus <b>994</b>. The bus <b>994</b> serves as an interconnect between the various components of the system <b>990</b>. Connected to the bus <b>994</b> is an input/output device interface <b>993</b> for connecting various input and output devices such as a keyboard, mouse, display, speakers, etc. to the system <b>990</b>. A central processing unit (CPU) <b>992</b> is connected to the bus <b>994</b> and provides for the execution of computer instructions. Memory <b>996</b> provides volatile storage for data used for carrying out computer instructions. Storage <b>995</b> provides non-volatile storage for software instructions, such as an operating system (not shown). The system <b>990</b> also comprises a network interface <b>991</b> for connecting to any variety of networks known in the art, including wide area networks (WANs) and local area networks (LANs).

0056It should be understood that the example embodiments described herein may be implemented in many different ways. In some instances, the various methods and machines described herein may each be implemented by a physical, virtual, or hybrid general purpose computer, such as the computer system <b>990</b>. The computer system <b>990</b> may be transformed into the machines that execute the methods described herein, for example, by loading software instructions into either memory <b>996</b> or non-volatile storage <b>995</b> for execution by the CPU <b>992</b>.

0057The system <b>990</b> and its various components may be configured to carry out any embodiments of the present invention described herein. For example, the system <b>990</b> may be configured to carry out the method <b>100</b> described hereinabove in relation to <figref idref="DRAWINGS">FIG. 1B</figref>. In such an example, the CPU <b>992</b> and the memory <b>996</b> with computer code instructions stored on the memory <b>996</b> and/or storage device <b>995</b> configure the apparatus <b>990</b> to parse an input annotated phrase, generate a syntactic tree reflecting the grammatical structure of the parsed phrase, and generate one or more alternative versions of the input annotated phrase based on the generated syntactic tree in a manner preserving alignment between expressions and corresponding annotations in the input annotated phrase in the one or more alternative versions that are generated. In such an embodiment, the original annotated phrase may be obtained by the system <b>990</b> via the network interface <b>991</b> and/or input/output device interface <b>993</b>, from any point communicatively coupled thereto. Further, the original phrase may be loaded from the storage device <b>995</b> or memory <b>996</b>.

0058<figref idref="DRAWINGS">FIG. 10</figref> illustrates a computer network environment <b>1000</b> in which the present invention may be implemented. In the computer network environment <b>1000</b>, the server <b>1001</b> is linked through communications network <b>1002</b> to clients <b>1003</b><i>a</i>-<i>n</i>. The environment <b>1000</b> may be used to allow the clients <b>1003</b><i>a</i>-<i>n </i>alone or in combination with the server <b>1001</b> to execute the various methods described hereinabove. In an example embodiment, the client <b>1003</b><i>a </i>sends an annotated phrase, shown by the data packets <b>1005</b>, via the network <b>1002</b> to the server <b>1001</b>. In response, the server <b>1001</b> uses the annotated phrase <b>1005</b> to generate alternative annotated phrases, which may then be transferred back to the client <b>1003</b><i>a</i>, shown by the data packets <b>1004</b>, via the network <b>1002</b>. In another embodiment, a method according to the principles described herein is executed on the server <b>1001</b> and accessed by the clients <b>1003</b><i>a</i>-<i>n </i>via the network <b>1002</b>.

0059It should be understood that the example embodiments described above may be implemented in many different ways. In some instances, the various methods and machines described herein may each be implemented by a physical, virtual, or hybrid general purpose computer, or a computer network environment such as the computer environment <b>1000</b>.

0060Embodiments or aspects thereof may be implemented in the form of hardware, firmware, or software. If implemented in software, the software may be stored on any non-transient computer readable medium that is configured to enable a processor to load the software or subsets of instructions thereof. The processor then executes the instructions and is configured to operate or cause an apparatus to operate in a manner as described herein.

0061Further, firmware, software, routines, or instructions may be described herein as performing certain actions and/or functions of the data processors. However, it should be appreciated that such descriptions contained herein are merely for convenience and that such actions in fact result from computing devices, processors, controllers, or other devices executing the firmware, software, routines, instructions, etc.

0062It should also be understood that the flow diagrams, block diagrams, and network diagrams may include more or fewer elements, be arranged differently, or be represented differently. But it further should be understood that certain implementations may dictate the block and network diagrams and the number of block and network diagrams illustrating the execution of the embodiments be implemented in a particular way.

0063Accordingly, further embodiments may also be implemented in a variety of computer architectures, physical, virtual, cloud computers, and/or some combination thereof, and, thus, the data processors described herein are intended for purposes of illustration only and not as a limitation of the embodiments.

0064While this invention has been particularly shown and described with references to example embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention encompassed by the appended claims.