Architecture for generating responses to search engine queries

• US 8,666,983 B2
• Filed: 06/13/2003
• Issued: 03/04/2014
• Est. Priority Date: 06/13/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Brill, Eric D., Ray, Soumya
• Primary Examiner(s): DWIVEDI, MAHESH H
• Application Number:
  US10/460,955
• Publication Number:
  US 20040254917A1
• Time in Patent Office: 3,917 Days
• Field of Search: 707/3, 707/5, 707/102, 707/736, 707/737
• US Class Current: 707/737
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems

Abstract

Architecture for generating responses to search engine queries. Question/answer pairs are used to provide a predefined question hierarchy to facilitate a search. Informative terms and one or more questions are associated with each question node of the hierarchy. A question posed is mapped into the hierarchy to the most similar question class node, as determined by passages of the question and/or comparing the informative terms of the question and the question/answer node. Weighted informative terms associated with that node are then returned, and can be used by an automatic question answering system to more effectively find an answer to a question.

Claims

1. A system, comprising:

one or more processors; and

one or more media storage devices storing a plurality of components, each component of the plurality of components comprising instructions that are executable by the one or more processors, the plurality of components including;

an input component to receive a query;

an abstraction component to;

map the query to an abstraction hierarchy according to a distribution of terms found in potential answer passages for the query by calculating a similarity value between the query and each of a plurality of queries in the abstraction hierarchy; and

group the query with a most similar query in the abstraction hierarchy based on the similarity value; and

an identification component to map data pairs comprising query-response pairs to the abstraction hierarchy to identify informative terms for a set of nodes in the abstraction hierarchy by determining using a Dunning measure a term-by-occurrence contingency data structure for each term found in possible answer passages for each question in each of the query-response pairs.

2. The system of claim 1, wherein the abstraction hierarchy includes at least one node of the set of nodes that is associated with the query.

3. The system of claim 1, wherein the abstraction hierarchy includes at least one node of the set of nodes associated with an informative term.

4. The system of claim 1, the abstraction component mapping the query into the abstraction hierarchy by comparing informative terms of the query with informative terms of at least one node of the set of nodes.

5. The system of claim 1, the abstraction component mapping the query into the abstraction hierarchy by comparing terms of the query with question terms of at least one question of the abstraction hierarchy.

6. The system of claim 1, wherein the abstraction component restructures the abstraction hierarchy to include the query.

7. The system of claim 1, the abstraction component initiating construction of a new hierarchy when the query cannot be mapped into the abstraction hierarchy.

8. The system of claim 1, the abstraction component clustering the abstraction hierarchy with other hierarchies that are determined to be similar thereto.

9. The system of claim 1, further comprising a classifier component for implicit and explicit learning, the classifier component implemented using a support vector machine.

10. The system of claim 1, further comprising a classifier component for implicit and explicit learning, the classifier component implemented using a decision tree.

11. The system of claim 9, the classifier component prioritizing abstraction hierarchies for clustering.

12. The system of claim 9, the classifier component prioritizing at least one of the query and informative terms of the query for processing.

13. The system of claim 1 further comprising a learning component that learns at least one of a term of the query and informative terms of the query.

14. The system of claim 13, the learning component using at least one of the term of the query and the informative terms of the query to improve the accuracy of an answer for a new query.

15. The system of claim 1, the abstraction component using the informative terms at a node of the abstraction hierarchy to weight one or more terms of the query.

16. A method comprising:

under control of one or more processors configured with instructions that are executable to perform acts comprising;

receiving, by the one or more processors, a query;

processing, by the one or more processors, the query for informative terms;

mapping, by the one or more processors, the query into an abstraction hierarchy in accordance with a distribution of potential answer terms by calculating a similarity value between the query and each query in the abstraction hierarchy to discriminate between a first set of potential answer terms in the abstraction hierarchy that include answers from a second set of potential answer terms in the abstraction hierarchy that do not include the answers;

grouping the query with a most similar query in the existing abstraction hierarchy based on the similarity value; and

mapping data pairs comprising query-response pairs to the abstraction hierarchy to identify informative terms for a set of nodes in the abstraction hierarchy by determining, using a Dunning measure, a term-by-occurrence contingency data structure for each term found in possible answer passages for each question in each of the query-response pairs.

17. The method of claim 16, the abstraction hierarchy including at least one node that is associated with an informative term.

18. The method of claim 16, wherein the query is mapped into the abstraction hierarchy by comparing the informative terms of the query with informative terms of at least one node of the abstraction hierarchy.

19. The method of claim 16, wherein the query is mapped into the abstraction hierarchy by comparing the terms of the query with terms of at least one question of the abstraction hierarchy.

20. The method of claim 16, wherein the query is mapped into the abstraction hierarchy, in response to which the abstraction hierarchy is restructured to include the query.

21. The method of claim 16, further comprising reconstructing, by the one or more processors, the abstraction hierarchy after the query is mapped into the abstraction hierarchy.

22. The method of claim 16, further comprising clustering, by the one or more processors, the abstraction hierarchy with other hierarchies that are determined to be similar thereto such that the query is processed against the clustered hierarchies.

23. The method of claim 16, further comprising mapping, by the one or more processors, data pairs to the abstraction hierarchy to facilitate identifying informative terms for a set of nodes in the abstraction hierarchy.

24. The method of claim 23, the data pairs are question/answer pairs.

25. The method of claim 16, further comprising clustering nodes of the abstraction hierarchy with other nodes that are determined to be similar thereto such that the query is processed against the clustered nodes.

26. The method of claim 16, the abstraction hierarchy including a node associated with at least one query.

27. The method of claim 16, the abstraction hierarchy including a node having associated therewith weighted informative terms that are returned and used by an automatic question answering system to find an answer to the query.

28. A method comprising:

under control of one or more processors configured with instructions that are executable to perform acts comprising;

receiving a question;

extracting a term from the question;

generating a term-by-occurrence contingency data structure of potential answers from a question/answer hierarchy by calculating a similarity value between the question and questions in the question/answer hierarchy, the term-by-occurrence contingency data structure including the potential answers in which the term occurs;

testing the data structure of potential answers for a discriminating term;

storing the discriminating term as an informative term using a Dunning measure;

ranking a plurality of the informative terms by relevance to a potential answer to the question based on the similarity value; and

utilizing one of the informative terms to find the potential answer.

29. The method of claim 28, the discriminating term is found by testing that the statistics of a fragment containing the answer is different from the statistics of a fragment not containing the answer.

30. A memory storage device including instructions executable by one or more processors to perform acts comprising:

receiving an existing abstraction hierarchy of nodes of questions and corresponding informative terms;

receiving a new question;

generating informative terms for the new question;

calculating a similarity value between the new question and every question in the existing abstraction hierarchy, the similarity value discriminating between a first set of questions in the existing abstraction hierarchy that include similar questions to the new question from a second set of questions in the existing abstraction hierarchy that do not include similar questions to the new question;

mapping data pairs comprising question-answer pairs to the existing abstraction hierarchy to identify informative terms for a set of nodes in the abstraction hierarchy by determining, using a Dunning measure, a term-by-occurrence contingency data structure for each term found in possible answer passages for each question in each of the question-answer pairs; and

grouping the new question with the most similar question in the existing abstraction hierarchy based on the similarity value.

31. The memory storage device of claim 30, further comprising rebuilding the existing abstraction hierarchy according to predetermined criteria.

32. The memory storage device of claim 30, further comprising replacing the new question and most similar question with a representative hierarchical structure at that node.

33. A system comprising:

one or more processors; and

one or more media storage devices storing instructions that are executable by the one or more processors to perform acts comprising;

receiving a query;

processing the query to identify informative terms;

mapping the query into an abstraction hierarchy in accordance with a plurality of potential answers for the query;

grouping the query with a most similar query in the abstraction hierarchy based on the similarity value; and

mapping data pairs comprising query-response pairs to the abstraction hierarchy to identify informative terms for a set of nodes in the abstraction hierarchy by determining, using a Dunning measure, a term-by-occurrence contingency data structure for each term found in possible answer passages for each question in each of the query-response pairs.

34. The system of claim 33, the abstraction hierarchy including at least one node that is associated with an informative term.

35. The system of claim 33, wherein the query is mapped into the abstraction hierarchy by comparing the informative terms of the query with informative terms of at least one node of the abstraction hierarchy.

36. The system of claim 33, wherein the query is mapped into the abstraction hierarchy, in response to which the abstraction hierarchy is restructured to include the query.

37. The system of claim 33, further comprising clustering the abstraction hierarchy with other hierarchies that are determined to be similar thereto such that the query is processed against the clustered hierarchies.

38. The system of claim 33, further comprising mapping data pairs to the abstraction hierarchy to identify informative terms for a set of nodes in the abstraction hierarchy.

39. The system of claim 38, the data pairs are query response pairs.

40. The system of claim 38, the data pairs are question/answer pairs.