Probability-based state modification for query dialogues

• US 9,607,046 B2
• Filed: 12/14/2012
• Issued: 03/28/2017
• Est. Priority Date: 12/14/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hakkani-Tur, Dilek, Tur, Gokhan, Heck, Larry, Fidler, Ashley, Celikyilmaz, Fehtiye Asli
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US13/715,060
• Publication Number:
  US 20140172899A1
• Time in Patent Office: 1,565 Days
• Field of Search: 707/758, 707/759, 707/769, 707/770
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events

Abstract

A device may facilitate a query dialog involving queries that successively modify a query state. However, fulfilling such queries in the context of possible query domains, query intents, and contextual meanings of query terms may be difficult. Presented herein are techniques for modifying a query state in view of a query by utilizing a set of query state modifications, each representing a modification of the query state possibly intended by the user while formulating the query (e.g., adding, substituting, or removing query terms; changing the query domain or query intent; and navigating within a hierarchy of saved query states). Upon receiving a query, an embodiment may calculate the probability of the query connoting each query state modification (e.g., using a Bayesian classifier), and parsing the query according to a query state modification having a high probability (e.g., mapping respective query terms to query slots within the current query intent).

Claims

1. A method of updating a query state according to a query received from a user of a device having a processor, the method comprising:

executing on the processor instructions configured to;

receive a query;

generate a query state based on the received query;

receive a follow-up query;

parse the follow-up query to identify at least zero query terms;

for each query state modification in a query state modification set, calculate a query state modification probability intended by the user for the follow-up query;

using the query state modification probabilities, identify at least two candidate query state modifications for modifying the query state;

among the at least two candidate query state modifications, identify a selected query state modification having a highest associated query state modification probability;

modify the query state according to the selected query state modification;

combine the follow-up query with the modified query state to create a modified follow-up query; and

provide search results based on the modified follow-up query.

2. The method of claim 1, wherein:

the query state comprises a current query domain selected from a query domain set; and

modifying the query state comprises;

identifying a selected query domain associated with the query; and

if the selected query domain associated with the query differs from the current query domain of the query state, associating the query state with the selected query domain.

3. The method of claim 2, wherein associating the query state with the selected query domain comprises:

calculating a selected query domain probability of the selected query domain associated with the query;

calculating a current query domain probability of the current query domain associated with the query state; and

if the selected query domain probability exceeds the current query domain probability, associating the query state with the selected query domain.

4. The method of claim 2, wherein:

the query state associated is with a current query intent within the query domain; and

modifying the query state comprises;

identifying a selected query intent associated with the query; and

if the selected query intent associated with the query differs from the current query intent of the query state, associating the query state with the selected query intent.

5. The method of claim 4, wherein:

respective query domains are associated with at least one query intent; and

identifying the selected query intent comprises;

identifying a selected query intent associated with the query from the query intents associated with the selected query domain.

6. The method of claim 5, wherein:

respective query intents comprise at least one query slot; and

modifying the query state comprises;

associating respective query slots of the selected query intent with at least one query term.

7. The method of claim 6, wherein:

respective query slots are associated with a query slot identifier; and

modifying the query state comprises associating respective query slots with a query term according to the query slot identifier of the query slot.

8. The method of claim 6, wherein the instructions are further configured to:

upon identifying at least one unfilled query slot, request a query term for respective unfilled query slots; and

upon receiving from the user a query term for an unfilled query slot, associate the query term with the unfilled query slot.

9. A system for modifying a query state using a query received from a user of a device having a processor, the system comprising:

a query term identifying component configured to identify query terms in the query and in a follow-up query;

a query state modification identifying component configured to;

identify a query state modification set comprising at least two candidate query state modifications respectively having a query state modification probability, and

from the query state modification set, identify a selected query state modification having a higher query state modification probability for the follow-up query than the query state modifications of other candidate query state modifications; and

a query state modifying component configured to modify the query state according to the selected query state modification and the query terms identified in the follow-up query.

10. The system of claim 9, wherein:

the system further comprises a query state modification training set;

the query state modification identifying component comprises a classifier;

the query state modification identifying component is further configured to train the classifier using the query state modification training set; and

selecting the query state modification set comprises;

after training the classifier, classifying respective queries into a query state modification selected from the query state modification set.

11. The system of claim 9, further comprising:

a query state saving component configured to;

upon the query state modifying component modifying the query state to generate a current query state, store the current query state; and

upon receiving a request to select a stored query state, select the stored query state as the current query state.

12. The system of claim 11, wherein:

the query state saving component comprises a query state hierarchy; and

receiving the request comprises;

receiving a request to navigate from a current query state to a stored query state that is related to the current query state in the query state hierarchy.

13. The system of claim 9, further comprising:

a query fulfilling component configured to;

evaluate the query state to identify a query result; and

present the query result to the user.

14. The system of claim 13, wherein the query fulfilling component is further configured to present the query state to the user with the query result.

15. A system comprising:

at least one processor; and

a memory storing instructions that, when executed by the at least one processor perform the following actions;

receive an initial query from a user;

generate an initial query state based on the initial query;

receive a follow-up query from a user; and

upon receiving the follow-up query;

parse the follow-up query to identify at least zero follow-up query terms;

calculate query state modification probabilities of the follow-up query for at least two candidate query state modifications in the query state modification set;

modify the query state according to the follow-up query terms and the query state modification having a highest query state modification probability among the candidate query state modifications; and

fulfill the query in view of the query state.

16. The system of claim 15, wherein the query state modification set comprises:

a query state initiating modification;

a query term adding state modification;

a query term substituting state modification;

a query term removing state modification;

a query state saving modification;

a query state sequence navigating modification;

a query state domain changing modification;

a query state intent changing modification; and

a query state resetting modification.

17. The system of claim 15, wherein:

the initial query is received in a first query modality; and

the follow-up query received after the previous query and in a second query modality that is different from the first query modality.

18. The system of claim 15:

the query state associated with at least one earlier query; and

the instructions further configured to, upon receiving a query identifiable by at least two query state modifications;

supplement the query with at least one earlier query to generate a supplemented query; and

recalculate the query state modification probabilities of the supplemented query for respective query state modifications in the query state modification set.

19. The system of claim 15, wherein the instructions are further configured to:

indicate to the user a query ambiguity of the follow-up query; and

upon receiving from the user a clarifying query addressing the query ambiguity;

supplement the follow-up query with the clarifying query to generate a supplemented query; and

recalculate the query state modification probabilities of the supplemented query for respective query state modifications in the query state modification set.

20. The system of claim 19, wherein:

indicating the query ambiguity to the user comprises;

for query state modifications identifiable for the follow-up query, presenting to the user a clarifying query option addressing the query ambiguity toward the respective query state modification; and

receiving the clarifying query comprises;

receiving from the user a selected clarifying query option.