Probability-based state modification for query dialogues

Patent metadata

Field	Value
Publication number	US-9607046-B2
Application number	US-201213715060-A
Country	US
Kind code	B2
Filing date	Dec 14, 2012
Priority date	Dec 14, 2012
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

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

First claim

What is claimed is:

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 furt

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Hakkani-Tur Dilek
• Tur Gokhan
• Heck Larry
• Fidler Ashley
• Celikyilmaz Fehtiye Asli

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F16/2457

  with adaptation to user needs · CPC title

• G06Q10/02 Primary

  Reservations, e.g. for tickets, services or events · CPC title

• G06F16/24534 Primary

  Query rewriting; Transformation · CPC title

• G06F17/30522 Primary

  Physics · mapped topic