System for answering natural language questions

• US 20040117352A1
• Filed: 04/30/2001
• Published: 06/17/2004
• Est. Priority Date: 04/28/2000
• Status: Abandoned Application

• Current Assignee: SAS Institute Incorporated
• Original Assignee: Global Information Research and Technologies LLC
• Inventors: Schabes, Yves, Roche, Emmanuel
• Application Number:
  US09/845,571
• Publication Number:
  US 20040117352A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/3344 using natural language analysis

Abstract

The present invention is a system for answering a natural language question. The system receives a question and transforms the question into one or more partially unspecified queries. The system then identifies matches for the queries in a body of information. The matches are optionally ranked, preferably based on the number of times each match is identified. The matches are provided as answers to the questions.

Claims

1. A method of answering a question based on information stored on a computer-readable medium comprising the steps of

receiving a question;

parsing the question to obtain an analyzed question;

matching the analyzed question to a set of predetermined question patterns to obtain matched question patterns;

transforming the matched question patterns into one or more partially unspecified statements, wherein each of the partially unspecified statements is missing a portion corresponding to an answer;

generating partially unspecified queries corresponding to the partially unspecified statements; and

obtaining answers by matching the partially unspecified queries to stored information.

2. The method of claim 1, wherein the transforming step further comprises:

transforming matched question patterns into one or more partially unspecified statements using syntactic frames.

3. The method of claim 1, further comprising the step of:

collecting answers from matching the partially unspecified queries across a plurality of documents in the stored information.

4. The method of claim 1, further comprising the step of:

ranking each obtained answer according to its frequency of matching.

5. The method of claim 1, wherein the stored information comprises a set of documents and an index identifying which documents within the set of documents contain terms or groups of terms answering the partially unspecified queries.

6. A method of answering a question based on documents stored on a computer-readable medium comprising the steps of:

storing contexts for terms, wherein a context occurs in a document;

receiving a question;

transforming the question into one or more partially unspecified queries; and

identifying a match or a set of matches for the one or more partially unspecified queries within the contexts, thereby providing an answer or a set of answers for the question.

7. A method for answering a question based on information stored on a computer-readable medium comprising the steps of:

receiving a question;

transforming the question into one or more partially unspecified queries; and

identifying a match or a set of matches within a body of information stored on a computer-readable medium for each of one or more of the partially unspecified queries, thereby providing an answer or a set of answers for the question.

8. The method of claim 7, wherein the partially unspecified query comprises a partially unspecified term.

9. The method of claim 7, wherein the question contains a question word or phrase and wherein the transforming step comprises:

replacing the question word or phrase with a partially unspecified term.

10. The method of claim 9, wherein the partially unspecified term comprises a restriction that is determined, at least in part, by the question word or phrase.

11. The method of claim 7, wherein the transforming step comprises:

transforming the question into one or more statement patterns; and

transforming one or more of the statement patterns into one or more partially unspecified queries.

12. The method of any of claims 7, 8, 9, 10, 11, further comprising the steps of:

generating additional partially unspecified queries by using a thesaurus; and

identifying a match or a set of matches within a body of information stored on a computer-readable medium for each of one or more of the additional partially unspecified queries.

13. The method of claim 12, wherein the thesaurus comprises a contextual thesaurus.

14. The method of any of claims 7, 12, or 13, wherein the identifying step comprises identifying a match or a set of matches for each of a plurality of partially unspecified queries, further comprising the step of:

combining the matches or sets of matches identified for each of a plurality of partially unspecified queries, thereby generating a combined result set for the question.

15. The method of any of claims 7, 12, or 13, wherein the identifying step comprises identifying a match or a set of matches for each of a plurality of partially unspecified queries, further comprising the steps of:

extracting a portion of each of a plurality of the identified matches; and

combining the extracted portions, thereby generating a combined result set for the question.

16. The method of claim 11, wherein the first transforming step comprises one or more of the following:

(a) analyzing the question, wherein the analyzing step comprises assigning a grammatical label to each of a plurality of elements in the question;

(b) simplifying the question;

(c) assigning an identifier to some or all of the grammatical labels in the question either before or after simplifying the question, thereby generating a processed question.

17. The method of claim 16, wherein a different identifier is assigned to each subject element, each object element, and each preposition element in the processed question, thereby uniquely identifying each subject element, each object element, and each preposition element in the processed question.

18. The method of claim 17, wherein the identifiers are numbers.

19. The method of claim 16, wherein the first transforming step comprises:

selecting one or more of a plurality of categories for the question or processed question, wherein a category comprises a set of sentence patterns that are grammatically related to one another, the sentence patterns each including one or more statement patterns; and

selecting one or more of the statement patterns from the one or more categories.

20. The method of claim 19, further comprising the steps of:

replacing a grammatical label in one or more of the selected sentence patterns with a partially unspecified term; and

replacing the remaining grammatical labels in the one or more selected sentence patterns with the corresponding elements from the question, thereby generating one or more partially unspecified queries.

21. The method of claim 19, further comprising the steps of:

adding grammatical labels indicating grammatically acceptable positions for modifiers to the selected sentence patterns;

replacing a grammatical label in one or more of the selected sentence patterns with a partially unspecified term; and

replacing the remaining grammatical labels in the one or more selected sentence patterns with the corresponding elements from the question, thereby generating one or more partially unspecified queries.

22. The method of claim 19, wherein the sentence patterns comprising a set of sentence patterns are grammatically related to one another in that each sentence pattern comprises a transformed version of a base sentence pattern, the base sentence pattern comprising one or more grammatical labels selected from the list consisting of subject elements, verb elements, object elements, and preposition elements and each transformed version comprises the same subject elements, verb elements, object elements, and preposition elements as the base sentence pattern.

23. The method of claim 22, wherein a transformed version is derivable from a base sentence pattern by subject the subject elements, verb elements, object elements, and preposition elements of the base sentence pattern to one or more of the following operations:

(a) permutation of the order of the elements;

(b) modification of the voice or aspect of a verb element; and

(c) addition of further grammatical labels, so as to generate a grammatically acceptable variant of the base sentence pattern.

24. The method of claim 16, wherein the simplifying step comprises performing one or more of the following operations on the question after analyzing the question:

(a) removing some or all auxiliary verbs and their corresponding grammatical identifiers;

(b) removing some or all words that appeared in the original question while retaining their corresponding grammatical identifiers; and

(c) (i) removing some or all words that form part of a noun phrase;

(ii) removing the grammatical identifiers for the words removed in step (i); and

(iii) retaining the grammatical identifier for the noun phrase.

25. The method of either of claims 14 or 15, further comprising the step of:

ranking the results in the combined result set.

26. The method of claim 25, further comprising the step of:

outputting some or all of the results in the combined result set in an order determined, at least in part, by the ranking.

27. The method of either of claims 14 or 15, further comprising the step of:

outputting an identifier or location of a document that contains a result.

28. The method of claim 25, further comprising the step of:

outputting an identifier or location of a document that contains a result.

29. An apparatus for answering a natural language question comprising:

a grammar comprising rules for constructing sentences for grammatical elements;

a parser employing the grammar in analyzing the natural language question and assigning a grammatical identifier to a plurality of grammatical elements in the question;

a set of predetermined question frames for transforming the analyzed question into one or more partially unspecified queries; and

a matching module for determining one or more answers to the natural language question by matching the one or more partially unspecified queries to information stored in a body of documents.

30. An apparatus for answering a natural language question comprising:

memory means to store a computer-executable process steps; and

a processor that executes computer-executable process steps so as

to receive a question,

to transform the question into one or more partially unspecified queries, and

to identify matches for the one or more partially unspecified queries in a body of information, thereby providing an answer to the question.

31. Computer-executable process steps stored on a computer-readable medium, the computer-executable process steps comprising:

code to receive a question;

code to transform the question into a partially unspecified query; and

code to identify a match for the partially unspecified query in a body of information, thereby providing an answer to the question.