Dynamic Natural Language Understanding

• US 20070112556A1
• Filed: 11/21/2006
• Published: 05/17/2007
• Est. Priority Date: 03/13/2001
• Status: Active Grant

• Current Assignee: Intelligate, Ltd. (AskMeNow, Inc.)
• Original Assignee: Intelligate, Ltd. (AskMeNow, Inc.)
• Inventors: Auerbach, Gadiel, Persky, Eldad, Lavi, Ofer
• Granted Patent: US 7,840,400 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Methods and systems for dynamic natural language understanding. A hierarchical structure of semantic categories is exploited to assist in the natural language understanding. Optionally, the natural language to be understood includes a request.

Claims

1. A method of training at least two classifiers to understand a natural language text, comprising:

introducing entries into a database, said entries belonging to at least two semantic categories of different hierarchical levels;

defining examples of natural language texts, wherein at least some of said examples include embedded syntactic tokens based on said entries; and

training at least two classifiers for said at least two semantic categories using said examples or a form thereof.

2. The method of claim 1, further comprising:

transforming said examples into n-grams, wherein said n-grams are said form used in said training.

3. The method of claim 2, wherein said n-grams are sparse.

4. A module for use in a system for natural language understanding, comprising:

at least one classifier or pseudo classifier configured to extract values belonging to a semantic category from a natural language text or a form thereof; and

an action resolver configured if a result of extracting values of said semantic category complies with a predetermined criterion to employ based on said result at least one classifier or pseudo classifier to extract values belonging to another semantic category of a different hierarchical level, and configured if said result does not comply with a predetermined criterion to perform at least one action from a group of actions including;

employing based on said result a dialog management module and giving up on understanding said natural language text.

5. The module of claim 4, further comprising:

at least two classifiers or pseudo classifiers configured to extract values belonging to another semantic category;

wherein said action resolver is configured to select based on said result less than all said at least two classifiers or pseudo classifiers for said another semantic category and to employee said selected less than all for extracting said values belonging to said another semantic category.

6. The module of claim 4, further comprising:

at least one classifiers or pseudo classifiers configured to extract values belonging to another semantic category;

wherein said action resolver is configured to embed syntactic tokens based on said result into at least one restatement of said text and to employ said at least one classifier or pseudo classifier for said another semantic category for extracting said values belonging to said another semantic category from said at least one restatement with embedded syntactic tokens or a form thereof.

7. The module of claim 4, further comprising:

a text pre-processing module configured to transform said natural language text including any embedded tokens into sparse n-grams, said sparse n-grams constituting said form, and wherein classifiers extract values from said form.

8. The module of claim 4, further comprising:

a dialog management module;

wherein said dialog management module poses a question to a submitter of said natural language text whose content depends on said result.

9. A system for natural language understanding, comprising:

at least two classifiers or pseudo classifiers configured to extract values belonging to at least two semantic categories on different hierarchical levels from a natural language text or a form thereof;

a dialog management module configured to dialog with a submitter of said natural language text;

at least one evaluation module configured to evaluate values belonging to said at least two semantic categories;

and an action resolver configured to cause said text to be understood by (i) employing, if a result of extracting values of a semantic category complies with a predetermined criterion and said semantic category is not a last to be processed semantic category, a classifier or pseudo classifier based on said result to extract values belonging to another semantic category, by (ii) employing, if said result does not comply with a predetermined criterion and said semantic category is not a last to be processed semantic category, a dialog management module and then employing, based on said result as augmented by at least one answer received from said submitter by said dialog management module, a classifier or pseudo classifier to extract values belonging to another semantic category, and by (iii) employing said evaluation module to evaluate said values of said at least two semantic categories in relation to one another in order to determine if said values are sufficient to understand said text and if said values are not sufficient employing said dialog management module to determine at least one value, said at least one value in conjunction with said values being sufficient to understand said text.

10. The system of claim 9, further comprising a request implementation module;

wherein said text includes a request and said request implementation module implements said request as understood.

11. A system for training classifiers for natural language understanding, comprising:

a real time database including entries related to semantic categories on at least two different hierarchical levels;

classifiers for said semantic categories; and

a knowledge work tool configured to develop syntactic tokens from said entries, embed said tokens in examples and train said classifiers at least partially on said examples.

12. A method for understanding a natural language text, comprising performing the following in a selectively statical manner;

receiving a natural language text;

extracting at least one parameter value from said text or a form thereof;

identifying at least one parameter type related to each extracted parameter value;

providing at least one restatement of said received text, each at least one restatement having embedded within, at least one of said identified parameter types;

extracting at least one overall category value from said at least one restatement or a form thereof;

selecting a subcategory extractor corresponding to one of said extracted at least one overall category, and using said selected subcategory extractor to extract at least one subcategory value;

choosing one of said at least one extracted subcategory values;

evaluating said at least one identified parameter type in relation to said chosen subcategory value; and

concluding that said natural language text is understood.

13. The method of claim 12, further comprising:

providing at least one n gram from said received text, wherein said extracting at least one parameter value from said form is from said at least one n-gram; and

providing a set of at least one n-gram for each at least one restatement, wherein said extracting at least one overall category from said form is from said sets of said at least one n-gram.

14. The method of claim 13, wherein said n-grams are sparse n grams.

15. The method of claim 12, wherein said at least one overall category value is a domain, and said at least one subcategory value is an operation.

16. The method of claim 12, wherein said text is understood if one value for said overall category, one value for said subcategory, and any corresponding required parameter values have been determined.

17. The method of claim 12, wherein said selecting a subcategory extractor includes:

if at least two overall category values are extracted, selecting one of said at least two overall category values based on associated grades thereof and using a subcategory extractor corresponding to said selected one overall category value to extract said at least one subcategory value.

18. The method of claim 12, wherein at least two overall category values are extracted, said selecting a subcategory extractor including:

asking a question to a submitter of said natural language text;

receiving a response to said question from said submitter;

extracting one overall category value from said response; and

using a subcategory extractor corresponding to said extracted one overall category to extract said at least one subcategory value.

19. The method of claim 12, further comprising:

if at least one parameter value is extracted which corresponds to a parameter type of which at least two values are defined for said chosen subcategory value, evaluating a relationship between said at least one extracted parameter value and said at least two values defined for said subcategory value.

20. The method of claim 12, wherein said choosing one of said at least one extracted subcategory values include:

evaluating said extracted at least one parameter value in relation to said extracted at least one subcategory value; and

if said extracted at least one parameter value does not correspond to one of said at least one extracted subcategory values, asking a question to a submitter of said natural language text;

receiving a response to said question from said submitter, extracting at least one subcategory value from said response, and evaluating said extracted at least one parameter value values in relation to said at least one subcategory value extracted from said response in order to choose one subcategory value from among said at least one extracted subcategory values.

21. The method of claim 12, wherein said choosing one of said at least one extracted subcategory values include:

if at least two subcategory values are extracted, choosing one of said at least two subcategory values based on associated grades thereof.

22. The method of claim 12, wherein said evaluating said at least one identified parameter type in relation to said chosen subcategory value includes:

if said at least one identified parameter type does not correspond to all parameter types required by said chosen subcategory value without default parameter values, asking a question to a submitter of said natural language text;

receiving a response to said question from said submitter, extracting at least one parameter value from said response, evaluating parameter types related to said extracted at least one parameter value in order to achieve identification of said all required parameter types without default values.

23. The method of claim 12, further comprising:

asking a question to a submitter of said natural language text, wherein a content of said question is dependent on when during said method said question is asked.

24. The method of claim 23, wherein said asking includes:

formulating said content on the fly.

25. The method of claim 23, wherein said asking includes:

modifying a predefined question to generate said content.

26. A system for understanding a natural language text, comprising:

one classifier configured to extract an overall category value from a natural language text or a form thereof;

a different classifier corresponding to each overall category value configured to extract subcategory values from a natural language text or a form thereof;

one classifier configured to extract parameter values from a natural language text or a form thereof;

a dialog management module configured to dialog with a submitter of said natural language text;

at least one evaluation component configured to evaluate extracted values; and

an action resolver configured to employ different parts of the system in turn in order to understand said natural language text, including employing said one classifier for parameter values before said one overall category classifier and employing said overall category classifier before said corresponding subcategory classifier.

27. The system of claim 26, further comprising:

a text preprocessing module configured to construct n-grams from natural language text.

28. The system of claim 26, further comprising:

at least one pseudo classifier configured to extract parameter values.

29. A computer program product comprising a computer useable medium having computer readable program code embodied therein for understanding a natural language text, the computer program product comprising:

computer readable program code for causing the computer to receive a natural language text;

computer readable program code for causing the computer to process each at least two semantic categories, said each on a different hierarchical level, by performing the following selectively in a statistical manner;

computer readable program code for causing the computer to (i) attempt to determine at least one value belonging to said each semantic category through extraction, wherein if said each semantic category is not a first processed of said at least two semantic categories, then said attempting is based on results of previously processed semantic categories; and

computer readable program code for causing the computer to (ii) if said each semantic category is not a last processed of said at least two semantic categories, and a result of said attempting does not comply with a predetermined criterion, dialog with a submitter of said text and receive at least one answer from said submitter, wherein at least one value determined from said at least one answer augments said result so as to comply with said predetermined criterion and allow extraction attempts for other of said at least two semantic categories to be subsequently processed; and

computer readable program code for causing the computer to;

evaluate values determined for said at least two semantic categories with respect to one another to determine whether said values are sufficient to understand said text, and if said values are not sufficient;

dialog with said submitter, receive at least one answer from said submitter, determine from said at least one answer at least one value belonging to at least one of said at least two semantic categories, said at least one value in conjunction with earlier determined values being sufficient to understand said text.

30. A computer program product comprising a computer useable medium having computer readable program code embodied therein for training at least two classifiers to understand a natural language text, the computer program product comprising:

computer readable program code for causing the computer to introduce entries into a database, said entries belonging to at least two semantic categories of different hierarchical levels;

computer readable program code for causing the computer to define examples of natural language texts, wherein at least some of said examples include embedded syntactic tokens based on said entries; and

computer readable program code for causing the computer to train at least two classifiers for said at least two semantic categories using said examples or a form thereof.

31. A computer program product comprising a computer useable medium having computer readable program code embodied therein for understanding a natural language text, the computer program product comprising:

computer readable program code for causing the computer to perform the following in a selectively statistical manner;

computer readable program code for causing the computer to receive a natural language text;

computer readable program code for causing the computer to extract at least one parameter value from said text or a form thereof;

computer readable program code for causing the computer to identify at least one parameter type related to each extracted parameter value;

computer readable program code for causing the computer to provide at least one restatement of said received text, each at least one restatement having embedded within, at least one of said identified parameter types;

computer readable program code for causing the computer to extract at least one overall category value from said at least one restatement or a form thereof;

computer readable program code for causing the computer to select a subcategory extractor corresponding to one of said extracted at least one overall category, and use said selected subcategory extractor to extract at least one subcategory value;

computer readable program code for causing the computer to choose one of said at least one extracted subcategory values;

computer readable program code for causing the computer to evaluate said at least one identified parameter type in relation to said chosen subcategory value; and

computer readable program code for causing the computer to conclude that said natural language text is understood.