Cost-benefit approach to automatically composing answers to questions by extracting information from large unstructured corpora

• US 7,739,215 B2
• Filed: 04/03/2009
• Issued: 06/15/2010
• Est. Priority Date: 08/06/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dumais, Susan T., Brill, Eric D., Horvitz, Eric J., Azari, David R.
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US12/417,959
• Publication Number:
  US 20090192966A1
• Time in Patent Office: 438 Days
• Field of Search: 706/46
• US Class Current: 706/46
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The present invention relates to a system and methodology to facilitate extraction of information from a large unstructured corpora such as from the World Wide Web and/or other unstructured sources. Information in the form of answers to questions can be automatically composed from such sources via probabilistic models and cost-benefit analyses to guide resource-intensive information-extraction procedures employed by a knowledge-based question answering system. The analyses can leverage predictions of the ultimate quality of answers generated by the system provided by Bayesian or other statistical models. Such predictions, when coupled with a utility model can provide the system with the ability to make decisions about the number of queries issued to a search engine (or engines), given the cost of queries and the expected value of query results in refining an ultimate answer. Given a preference model, information extraction actions can be taken with the highest expected utility. In this manner, the accuracy of answers to questions can be balanced with the cost of information extraction and analysis to compose the answers.

Claims

1. A normalization system, comprising:

a processor;

a memory communicatively coupled to the processor, the memory having stored therein computer-executable instructions to implement the system, including;

an interface component that processes questions posed by users, the questions corresponding to a heterogeneous knowledge base;

a dialog component that requests users to reformulate questions based upon a cost-benefit analysis;

a normalization component that applies a utility model that predicts accuracy results to provide a regularized understanding of the knowledge base based on at least one of the processed questions or the reformulated questions; and

an answer composer component that employs the predicted accuracy of results to generate answers to the processed questions.

2. The system of claim 1, the utility model dynamically controls extraction of previously unknown or disassociated information from the knowledge base.

3. The system of claim 1, the utility model controls a number of queries submitted to the knowledge base given decision-theoretic considerations.

4. The system of claim 1, the knowledge base includes at least one of a local database, a file, a directory, an electronic encyclopedia, a dictionary, a remote database, or a remote web site.

5. The system of claim 1, the utility model applies a cost-benefit analysis to dynamically control the number and types of attempts made to acquire information or answers from the knowledge base in response to a question or questions.

6. The system of claim 5, the utility model includes an analysis of the costs of searching for information versus the benefits of obtaining more accurate answers to questions.

7. The system of claim 1, the cost-benefit analysis factors a benefit of reformulating a question versus expending effort on processing a query that is expensive in terms of searching for information from the knowledge base or is likely to yield inaccurate results.

8. The system of claim 7, the cost-benefit analysis factors a cost of delay resulting from reformulating the query and a likelihood that a reformulation would lead to an improved result.

9. The system of claim 1, further comprising a preference component that enables users to assess or select various parameters that influence the utility model.

10. The system of claim 9, the preference component processes at least one of a user setting for a cost, a value, or a language preference.

11. The system of claim 10, the preference component includes a model where a user assesses a parameter v, indicating a dollar value of receiving a correct answer to a question, and where a parameter c represents a cost of each query rewrite submitted to a search engine.

12. The system of claim 11, further comprising a value of receiving an answer expressed as a function of details of a current context, the value of the answer is linked to at least one of a type of question, an informational goal, or a time of day for a user.

13. The system of claim 11, further comprising determining a cost of submitting queries as a function of at least one of a current load sensed on a search engine or the numbers of queries being submitted by a user'"'"'s entire organization to a third-party search service.

14. The system of claim 13, further comprising determining the costs non-linearly with increasing numbers of queries.

15. A method to normalize a database, comprising:

employing a processor executing computer executable instructions embodied on a computer readable storage medium to perform the following acts;

receiving a question from a user;

automatically forming a set of queries from the question received from the user, each query is assigned a different weight;

performing a cost-benefit analysis on the set of queries to generate a query subset, wherein the cost-benefit analysis factors cost of a quantity of queries to include in the query subset versus the accuracy of the results returned from the quantity of queries included in the query subset;

executing the query subset on the database to provide a set of results; and

providing an answer to the user based upon the set of results.

16. The method of claim 15, further comprising automatically ranking the set of queries in an order of likelihood of providing a suitable answer.

17. The method of claim 15, further comprising automatically training at least one model to generate the query subset.

18. The method of claim 15, further comprising submitting the query subset to at least one search engine.

19. The method of claim 18, further comprising receiving the set of results from the at least one search engine and automatically composing the answer.

20. A system to facilitate database normalization, comprising:

a processor;

a memory communicatively coupled to the processor, the memory having stored therein computer-executable instructions to implement the system, including;

means for receiving a question from a user;

means for automatically forming a set of queries from the question received from the user;

means for generating query subset from the set of queries, wherein the means for generating the query subset dynamically determines a quantity of queries from the set of queries to include in a query subset based upon a cost-benefit analysis that factors cost of the quantity of queries to include in the query subset versus the accuracy of the results returned from the quantity of queries included in the query subset;

means for executing the query subset on the database to provide a set of results; and

means for providing an answer to the user based upon the set of results.