Adaptive semantic reasoning engine

• US 7,822,699 B2
• Filed: 11/30/2005
• Issued: 10/26/2010
• Est. Priority Date: 11/30/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Jun, Yao, Qi Steven, Katariya, Sanjeev, Ramsey, William D., Gao, Jianfeng
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Bharadwaj; Kalpana
• Application Number:
  US11/290,076
• Publication Number:
  US 20070124263A1
• Time in Patent Office: 1,791 Days
• Field of Search: 706/45, 704/4, 704/9, 707/3, 707/5
• US Class Current: 706/45
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries

Abstract

Provided is an adaptive semantic reasoning engine that receives a natural language query, which may contain one or more contexts. The query can be broken down into tokens or a set of tokens. A task search can be performed on the token or token set(s) to classify a particular query and/or context and retrieve one or more tasks. The token or token set(s) can be mapped into slots to retrieve one or more task result. A slot filling goodness may be determined that can include scoring each task search result and/or ranking the results in a different order than the order in which the tasks were retrieved. The token or token set(s), retrieved tasks, slot filling goodness, natural language query, context, search result score and/or result ranking can be feedback to the reasoning engine for further processing and/or machine learning.

Claims

1. A system that facilitates user intent to action mapping, the system comprising:

a processor; and

a memory storing computer executable instructions that, when executed by the processor, cause the system to;

receive a natural language input and a user context, the user context being information indicative of previous actions of a user, the natural language input and the user context associated with the user intent;

break the natural language input into a plurality of tokens;

retrieve a plurality of tasks, each task in the plurality of tasks being relevant to the natural language input, each task in the plurality of tasks having slots to hold pieces of information about the task;

generate semantic solutions for tasks in the plurality of tasks, a semantic solution for a task being a mapping of tokens in the plurality of tokens to the slots of the task;

use a ranking algorithm to rank the semantic solutions for tasks in the plurality of tasks;

output a slot-filled task, the slot-filled task being a task in the plurality of tasks whose slots contain a highest-ranked one of the semantic solutions for the task;

receive feedback from the user regarding the slot-filled task; and

train the ranking algorithm based on the feedback from the user.

2. The system of claim 1,

wherein the computer executable instructions, when executed by the processor, cause the system to reduce the plurality of tasks into a reduced plurality of tasks, the reduced plurality of tasks including fewer tasks than the plurality of tasks;

and

wherein the computer executable instructions, when executed by the processor, cause the system to use the ranking algorithm to generate semantic solutions for tasks in the reduced plurality of tasks exclusively.

3. The system of claim 1, wherein the computer executable instructions cause the system to use the ranking algorithm to rank the semantic solutions in part by causing the system to utilize one of the following to rank the semantic solutions:

Hidden Markov Model (HMM), Max Entropy Min Divergence (MEMD), and Information Retrieval (IR) technology.

4. The system of claim 1, wherein the computer executable instructions, when executed by the processor, cause the system to iteratively receive prior mapped actions as feedback to the mapping algorithm to adaptively train the mapping algorithm.

5. A method for reasoning an action based on a natural language input, the method comprising:

receiving, by a computer, a query, a user context, and feedback associated with prior slot assignments, the user context being information indicative of previous actions of a user;

transforming, by the computer, subsets of the query into tokens;

retrieving, by the computer, a plurality of tasks utilizing the tokens and the user context, each task in the plurality of tasks being relevant to the query, each task in the plurality of tasks having slots to hold pieces of information about the task;

scoring, by the computer, each task in the plurality of tasks to select a best task based at least on the query and the user context;

generating, by the computer, semantic solutions for the best task, the semantic solutions for the best task mapping ones of the tokens into the slots of the best task;

using a ranking algorithm to rank the semantic solutions for the best task based at least in part on the feedback;

outputting, by the computer, the best task and a best semantic solution, the best semantic solution being a highest-ranking one of the semantic solutions for the best task; and

employing, by the computer, the best semantic solution as feedback to train the ranking algorithm.

6. The method of claim 5, further comprising after receiving the query reducing, by the computer, the plurality of tasks into a reduced plurality of tasks, the reduced plurality of tasks including fewer tasks than the plurality of tasks;

and

using the ranking algorithm to score the tasks in the reduced plurality of tasks exclusively.

7. The method of claim 5,

wherein each task in the plurality of tasks is a search task;

and

wherein the method further comprises;

generating, by the computer, a search result list by executing the best task using the best semantic solution, the search result list comprising a plurality of search results, the search results in the search result list ordered in an original ranking, the original ranking based on relevance to the query;

output, by the computer, the search result list to the user;

receive, by the computer, feedback from the user indicating appropriateness of the original ranking; and

re-ranking, by the computer, the search results in the search result list based on the appropriateness of the original ranking such that the search results in the search result list are ranked differently if the original ranking is not appropriate.

8. The method of claim 5, further comprising:

receiving, by the computer, another context associated with a user action after the best task is output; and

using, by the computer, the other context to train the ranking algorithm.

9. The method of claim 5, wherein using the ranking algorithm to rank the semantic solutions comprises utilizing, by the computer, one of the following to rank the semantic solutions:

Hidden Markov Model, Naï

ve-Bayesian model, Max Entropy Min Divergence, or Information Retrieval (IR) technology.

11. The method of claim 5 wherein the best task is selected based at least on feedback received in connection with prior mappings of queries to tasks.

10. A computing device that converts a natural language input into an executed action, the computing device comprising:

a processor; and

a memory storing computer executable instructions that, when executed by the processor, cause the computing device to;

transform portions of a natural language inquiry into a plurality of tokens, the natural language inquiry received from a user, each token in the plurality of tokens being a string of characters, wherein the computing device transforms the portions of the natural language inquiry into the plurality of tokens by recognizing named entities in the natural language inquiry;

retrieve a plurality of search tasks, each search task in the plurality of search tasks being relevant to the natural language inquiry, each search task in the plurality of tasks having slots to hold pieces of information about the search task;

use a Hidden Markov Model to generate semantic solutions that map tokens in the plurality of tokens to slots of search tasks in the plurality of search tasks;

rank the semantic solutions for each search task in the plurality of search tasks;

generate an ordered action list that contains slot-filled search tasks, each of the slot-filled search tasks being a search task in the plurality of search tasks whose slots contain a highest-ranked one of the semantic solutions for the search task;

output the ordered action list to the user;

receive from the user a selection of a given search task in the ordered action list;

train the Hidden Markov Model based on the selection of the given search task;

output the semantic solutions for the given search task to the user;

receive from the user a selection of a given semantic solution for the given search task;

train the Hidden Markov Model based on the selection of the given semantic solutions;

generate a search result list by executing the given search task using the given semantic solution, the search result list comprising a plurality of search results, the search results in the search result list ordered based on relevance to the natural language inquiry;

output the search result list to the user;

receive a selection of a given search result in the search result list; and

train the Hidden Markov Model based on the selection of the given search result.