METHOD AND SYSTEM OF CLASSIFICATION IN A NATURAL LANGUAGE USER INTERFACE

• US 20150039292A1
• Filed: 07/19/2012
• Published: 02/05/2015
• Est. Priority Date: 07/19/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Maluuba Inc. (Microsoft Corporation)
• Inventors: Hsu, Wilson, Suleman, Kaheer, Pantony, Joshua R., Wu, Zhiyuan, Tregenza, Phil, Paspupalak, Sam
• Granted Patent: US 10,387,410 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• 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 user queries comprising natural language for a natural language-based user interface for performing one or more functions, the method comprising:

receiving at a computing device a plurality of user queries for defining one or more commands for controlling the user interface to perform particular types of functions; and

classifying, via the computing device, individual user queries in accordance with the types of functions to relate a subset of the plurality of user queries to define a particular command for invoking a particular type of function, determining a query type for each user query, the query type selected from a group comprising a functional query, an entity query and a clarification query;

wherein the functional query comprises a request for a particular new command to perform a particular type of function;

the entity query relates to an entity associated with the particular new command having the particular type of function; and

the clarification query is responsive to a clarification question posed to clarify a prior user query having the particular type of function.

2. The computer-implemented method of claim 1 comprising further processing the user queries in response to the particular type of function to define the particular command.

3. The computer-implemented method of claim 1 comprising providing the particular command to invoke the function.

4. The computer-implemented method of claim 1 wherein classifying comprises, for a user query received following a posing of a clarification question:

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

classifying the user query as a clarification query having the particular type of function in response to the keyword analysis.

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

6. The computer-implemented method of claim 4 comprising, for a user query received following a posing of a clarification question which is unresponsive to the question posed or for a user query received other than a user query received following a posing of a clarification question:

determining whether the user query is an entity query or a functional query and in response, perform one of;

classifying the user query as an entity query having the particular type of function of the particular command to which it relates; and

classifying the user query as a functional query, analyzing the user query to determine the particular type of function for the particular new command.

7. The computer-implemented method of claim 6 wherein determining whether the user query is an entity query or a functional query is performed using a support vector machine.

8. The computer-implemented method of claim 6 wherein analyzing the user query to determine the particular type of function comprises:

performing a plurality of natural language processing techniques to determine a rank of candidate types of functions and selecting the type of function in response.

9. The computer-implemented method of claim 8 wherein the natural language processing techniques include one or more of random forest processing, naï

ve Bayes classifier processing, a plurality of support vector machines processing, and previous query score processing.

10. The computer-implemented method of claim 8 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.

11. The computer-implemented method of claim 8 wherein previous query score processing comprises:

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

12. The computer-implemented method of claim 11 comprising maintaining a data store of prior user queries and respective types of functions.

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

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

15. The computer-implemented method of claim 14 wherein the feature sets with which to extract the entities for particular types of functions comprise a feature associated with the clarification question posed.

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

17. The computer-implemented method of claim 2 wherein processing comprises extracting entities from the user queries for the particular command using statistical modeling methods.

18. The computer-implemented method of claim 17 wherein the statistical modeling methods comprise using conditional random fields.

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

20. The computer-implemented method of claim 19 wherein defining optimized features sets comprises performing at least one round of genetic selection to identify optimized feature sets, 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 and determining a performance measure for each of the plurality of random permutations, selecting a subset of the plurality of random permutations at least in part based on the performance measure of each respective random permutation.

21. The computer-implemented method of claim 20 wherein the performance measure comprises an accuracy measure and a computational efficiency measure.

22. The computer-implemented method of claim 21 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.

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

24. 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.

25. A system comprising one or more processors and memory storing instructions and data for performing a method in accordance with claim 1.

26. A computer program product comprising a storage medium storing instructions and data for performing a method in accordance with claim 1.