System, representation, and method providing multilevel information retrieval with clarification dialog

• US 7,089,226 B1
• Filed: 06/28/2001
• Issued: 08/08/2006
• Est. Priority Date: 06/28/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dumais, Susan T., Horvitz, Eric J.
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US09/893,827
• Time in Patent Office: 1,867 Days
• Field of Search: 707/5, 707/4, 707/3, 707/1, 707/101, 707/102, 707/103.Y, 707/104.1, 715/705, 379/88.01
• US Class Current: 707/740
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An information retrieval system, including a learning and real-time classification methodology, is provided in accordance with the present invention. The system includes a hierarchal analysis component that receives a query and processes probabilities associated with N categories, each category having one or more topics, wherein N is an integer. An interactive component drives clarification dialog that is derived from the query and the probabilities associated with the N categories and the one or more topics. The clarification dialog, driven by a rule-based policy, a decision-theoretic analysis considering the costs of dialog to focus the results versus the costs of browsing larger lists, or combinations of rules and decision-theoretic analysis is employed when valuable to determine at least one category of the N categories to facilitate retrieval of at least one of the topics.

Claims

1. An information retrieval system, comprising:

a hierarchal analysis component that receives a query and processes probabilities associated with N categories that are collectively assigned a top-level classifier and individually assigned sublevel classifiers, each category having one or more topics, N being an integer, at least one of the one or more topics associated with a prior probability defined prior to receipt of the query, the prior probability indicating a likelihood that a particular topic is desired absent additional information; and

an interactive component that provides feedback derived from the query, the probabilities associated with the N categories, and the prior probability associated with the at least one topic, the feedback utilized to determine at least one category of the N categories to facilitate retrieval of at least one of the one or more topics.

2. The system of claim 1, the top-level classifier and sublevel classifiers are provided by at least one of a Support Vector Machine, Naï

ve Bayes, Bayes Net, decision tree, similarity-based, vector-based and a Bayesian-based classification model.

3. The system of claim 2, further comprising an automatic classifier construction component that employs a learning model to build the classifiers.

4. The system of claim 3, the learning model is associated with a Support Vector Machine and employs Sequential Minimal Optimization (SMO) to train the classifiers.

5. The system of claim 3, further comprising a data structure that includes a mapping of I possible queries and one or more associated topics, I being an integer, to enable learning for the classifiers.

6. The system of claim 5, the data structure is updated via at least one of implicit and explicit user actions associated with a query to facilitate improved learning models.

7. The system of claim 5, the data structure is centrally located and retains monitored implicit and explicit user actions associated with queries from a plurality of users to facilitate improved learning models.

8. The system of claim 1, the top-level classifier is employed to drive the sublevel classifiers at run time to form a hierarchical classification structure.

9. The system of claim 8, the query and the top-level classifier are employed to determine the most likely of the N categories.

10. The system of claim 9, further comprising a context disambiguation component that utilizes the query and the top-level classifier to determine the feedback.

11. The system of claim 10, the context disambiguation component utilizes the query and the feedback to drive the sublevel classifiers in order to determine a desired topic.

12. The system of claim 10, the context disambiguation component further comprises a presentation component for interfacing to a user and an analytical component to facilitate feedback and decision-making related to the feedback.

13. The system of claim 12, the analytical component includes a cost-benefit analysis considering the cost of the dialog with the information value of the dialog.

14. The system of claim 12, the analytical component includes a decision analysis for determining the nature and quantity of a clarification dialog.

15. The system of claim 12, the analytical component includes a computation of the value of information associated with feedback gained during a clarification dialog to guide the nature and quantity of the clarification dialog.

16. The system of claim 12, the analytical component employs at least one of a rule-based policy and an expected utility policy that controls if and how dialog is invoked based on the distribution of probabilities assigned to topics at one or more layers of a classification scheme.

17. The system of claim 16, the analytical component analyzes probabilistic weights associated with each category and related subtopic for determining feedback and presentation to the user.

18. The system of claim 16, the analytical component analyzes probabilistic weights as a spread across each category and related subtopic for determining feedback and presentation to the user.

19. The system of claim 12, the presentation component includes a ranked display of most likely N categories.

20. The system of claim 19, at least one of the most likely N categories is selected to provide a ranked display of one or more topics.

21. The system of claim 1, information is retrieved as part of a help system.

22. The system of claim 1, information is retrieved from a network-based system.

23. The system of claim 1, the probabilities are determined via a hand-crafted analysis.

24. The system of claim 1, further comprising L levels of N categories, each category having one or more topics, wherein L and N are integers.

25. A computer-readable medium storing the computer-executable components of claim 1.

26. A method providing information retrieval from a database, comprising:

assigning prior probabilities to one or more topics prior to receipt of a query, the prior probabilities relate to a likelihood that a particular topic is desired by a user absent additional information;

determining probabilities associated with one or more categories that are associated with the one or more topics upon receipt of a query through employment of a top-level classifier assigned collectively to a plurality of categories that include the one or more categories and sublevel classifiers individually assigned to each category within the plurality of categories;

providing feedback that is derived from the query, the prior probabilities, and the determined probabilities associated with the one or more categories and the one or more topics; and

resolving at least one category of the one or more categories based upon the feedback to facilitate retrieval of at least one of the one or more associated topics.

27. The method of claim 26, the classifiers are at least one of a vector-based and a Bayesian-based model.

28. The method of claim 27, further comprising,

mapping I possible queries and associated topics within a data structure, I being an integer, to enable learning of the classifiers.

29. The method of claim 28, further comprising,

monitoring implicit and explicit user actions associated with a query to facilitate improved learning models.

30. The method of claim 28, further comprising,

monitoring a central data location for implicit and explicit user actions associated with queries from a plurality of users to facilitate improved learning models.

31. The method of claim 26, the top-level classifier is employed to drive the sublevel classifiers at run time to form a hierarchical classification structure.

32. The method of claim 31, the query and the top-level classifier are employed to determine the most likely of the one or more categories.

33. The method of claim 32, further comprising, utilizing the query and the top-level classifier to determine the feedback.

34. The method of claim 33, further comprising,

utilizing the query and the feedback to drive the sublevel classifiers in order to determine a desired topic.

35. The method of claim 26, further comprising,

utilizing at least one of a cost benefit analysis and a decision analysis for determining the feedback.

36. The method of claim 33, further comprising,

utilizing rule-based policies and expected-utility policies for establishing probabilistic thresholds associated with the feedback.

38. A computer-readable medium comprising instructions for performing the method of claim 26.

37. A system providing information retrieval, comprising:

means for assigning prior probabilities to one or more topics prior to receipt of a query, the prior probabilities relate to a likelihood that a particular topic is desired by a user absent additional information;

means for determining probabilities associated with N categories upon receipt of a query, each category having at least one of the one or more topics, N being an integer greater than one, the probabilities are determined through employment of a top-level classifier collectively assigned to the N categories and sublevel classifiers individually assigned to each of the N categories, the top-level classifier and sublevel classifiers are provided by at least one of a Support Vector Machine, Naive Bayes, Bayes Net decision tree, similarity-based, vector-based and a Bayesian-based classification model;

means for providing feedback that is derived from a query, the prior probabilities, and the probabilities associated with the N categories; and

means for determining at least one category of the N categories based upon the feedback to facilitate retrieval of at least one of the one or more topics.