Method and system of classification in a natural language user interface

• US 10,387,410 B2
• Filed: 07/19/2012
• Issued: 08/20/2019
• Est. Priority Date: 07/19/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Maluuba Inc. (Microsoft Corporation)
• Inventors: Suleman, Kaheer, Pantony, Joshua R., Hsu, Wilson, Wu, Zhiyuan, Tregenza, Phil, Pasupalak, Sam
• Primary Examiner(s): Mishra, Richa
• Application Number:
  US14/233,640
• Publication Number:
  US 20150039292A1
• Time in Patent Office: 2,588 Days
• Field of Search: None
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 3/16 Sound input; Sound output speech processing G10L
• CPC Class Codes: G06F 3/167 Audio in a user interface, e.g. using voice commands for navigating, audio feedback
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G06F 40/56 Natural language generation
• CPC Class Codes: G06F 40/58 Use of machine translation, e.g. for multi-lingual retrieval, for server-side translation for client devices or for real-time translation
• CPC Class Codes: G06Q 30/0601 Electronic shopping [e-shopping]
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue

Abstract

A method and system are provided for processing natural language user queries for commanding a user interface to perform functions. Individual user queries are classified in accordance with the types of functions and a plurality of user queries may be related to define a particular command. To assist with classification, a query type for each user query is determined where the query type is one of a functional query requesting a particular new command to perform a particular type of function, an entity query relating to an entity associated with the particular new command having the particular type of function and a clarification query responding to a clarification question posed to clarify a prior user query having the particular type of function. Functional queries may be processed using a plurality of natural language processing techniques and scores from each technique combined to determine which type of function is commanded.

Claims

1. A computer-implemented method of processing queries for performing one or more functions, the method comprising:

receiving a first query of a plurality of user queries, by a communication system, wherein the first query defines at least one command, wherein the at least one command is classified as a type of function;

after receiving the first query, receiving a second query of a plurality of user queries, by the communication system, wherein the second query includes at least one entity;

determining the type of function for the at least one command of the first query by ranking candidate types of functions for the at least one command;

identifying a template based on the type of function for the at least one command, wherein the template comprises the at least one command and at least one placeholder for an entity associated with performing the at least one command;

identifying, by the communication system, an association between the at least one extracted entity from the second query and the at least one placeholder in the template for the at least one command of the first query;

substituting, by the communication system, the at least one placeholder in the template with the at least one extracted entity from the second query based on the association; and

performing, by the communication system, the at least one command from the first query based at least in part on the at least one extracted entity from the second query according to the template.

2. The computer-implemented method of claim 1, comprising providing the at least one command to invoke a function.

3. The computer-implemented method of claim 1, wherein for a third query received following a posing of a clarification question:

performing keyword analysis on the third query to determine whether the third query is responsive to the clarification question; and

classifying the third query as a clarification query for the at least one command in response to the keyword analysis.

4. The computer-implemented method of claim 3, wherein keyword analysis is performed in accordance with term frequency-inverse document frequency (TF-IDF) techniques on keywords in the third query which are associated with the clarification question posed.

5. The computer-implemented method of claim 3, wherein for a fourth query received following the posing of the clarification question, wherein the fourth query is unresponsive to the clarification question posed, further comprising:

determining whether the fourth query is one of an entity query and a functional query.

6. The computer-implemented method of claim 5, wherein determining whether the fourth query is one of the entity query and the functional query is performed using a support vector machine.

7. The computer-implemented method of claim 5, further comprising:

when the fourth query is a functional query, analyzing the fourth query to determine a second command by performing a plurality of natural language processing techniques to determine a rank of candidate commands and selecting the second command in response.

8. The computer-implemented method of claim 7, wherein the natural language processing techniques include one or more of random forest processing, naive Bayes classifier processing, a plurality of support vector machines processing, or previous query score processing.

9. The computer-implemented method of claim 7, wherein the rank is derived from the plurality of natural language processing techniques via a two layer neural network responsive to an output of each of the plurality of natural language processing techniques.

10. The computer-implemented method of claim 7, wherein previous query score processing comprises:

performing statistical analysis to provide candidate commands for the fourth query, the analysis responsive to keywords of the fourth query and prior user queries having associated respective commands previously determined for each of the prior user queries.

11. The computer-implemented method of claim 10, comprising maintaining a data store of prior user queries and respective commands.

12. The computer-implemented method of claim 11, wherein the prior user queries are responsive to clarification questions posed to individual users to provide user-centric preferences for commands.

13. The computer-implemented method of claim 1, comprising posing a clarification question in response to a previous user query, the clarification question associated with the type of function.

14. The computer-implemented method of claim 13, wherein a feature set is used to extract entities for particular types of functions associated with the at least one command, and wherein the feature set comprises a feature associated with the clarification question posed.

15. The computer-implemented method of claim 14, wherein the feature set includes one feature corresponding to each clarification question in a repository of clarification questions.

16. The computer-implemented method of claim 1, comprising using a genetic algorithm to define optimized features sets with which to extract entities for particular types of functions.

17. The computer-implemented method of claim 16, wherein defining optimized features sets comprises:

performing, by a communication system, at least one round of genetic selection to identify the optimized feature sets, wherein one round of genetic selection comprises;

identifying at least one initial feature set;

generating a plurality of random permutations from the at least one initial feature set;

testing the plurality of random permutations using a dataset of test queries;

determining a performance measure for each of the plurality of random permutations; and

selecting a subset of the plurality of random permutations at least in part based on the performance measure of each respective random permutation.

18. The computer-implemented method of claim 17, wherein the performance measure comprises an accuracy measure and a computational efficiency measure.

19. The computer-implemented method of claim 18, comprising further performing additional rounds of genetic selection after the first round of genetic selection has been performed, each additional round of genetic selection including the step of setting the subset of the plurality of random permutations as the at least one initial feature set.

20. The computer-implemented method of claim 18, comprising selecting one of the subset of random permutations to be a feature vector for a particular domain.

21. The computer-implemented method of claim 1, wherein the user queries comprise voice signals and the method further comprises converting the voice signals to text.

22. A computing device comprising:

at least one processor; and

at least one memory storing computer-executable instructions that when executed by the at least one processor cause the computing device to;

receive, by a communication system, a first query of a plurality of user queries, wherein the first query defines at least one command for controlling the user interface, wherein the at least one command is classified as a type of function;

after receiving the first query, receive, by the communication system, a second query of a plurality of user queries, wherein the second query includes at least one entity;

determine the type of function for the at least one command of the first query by ranking candidate types of functions for the at least one command;

identify a template based on the type of function for the at least one command, wherein the template comprises the at least one command and at least one placeholder for an entity associated with performing the at least one command;

identify, by the communication system, an association between the at least one extracted entity from the second query and the at least one placeholder in the template for the at least one command of the first query;

substitute, by the communication system, the at least one placeholder in the template with the at least one extracted entity from the second query based on the association; and

perform, by the communication system, the at least one command from the first query based at least in part on the at least one extracted entity from the second query according to the template.

23. A tangible computer storage medium storing computer-executable instructions that when executed by at least one processor cause a computing device to:

receive, by a communication system, a first query of a plurality of user queries, wherein the first query defines at least one command, wherein the at least one command is classified as a type of function;

after receiving the first query, receive, by the communication system, a second query of a plurality of user queries, wherein the second query includes at least one entity;

determine the type of function for the at least one command of the first query by ranking candidate types of functions for the at least one command;

identify a template based on the type of function for the at least one command, wherein the template comprises the at least one command and at least one placeholder for an entity associated with performing the at least one command;

identify, by the communication system, an association between the at least one extracted entity from the second query and the at least one placeholder in the template for the at least one command of the first query;

substitute, by the communication system, the at least one placeholder in the template with the at least one extracted entity from the second query based on the association; and

perform, by the communication system, the at least one command from the first query based at least in part on the at least one extracted entity from the second query according to the template.