Question answering system, data search method, and computer program

• US 7,418,443 B2
• Filed: 12/14/2005
• Issued: 08/26/2008
• Est. Priority Date: 06/03/2005
• Status: Active Grant

• Current Assignee: Fujifilm Business Innovation Corp. (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Masuichi, Hiroshi, Yoshimura, Hiroki, Sugihara, Daigo, Ohkuma, Tomoko
• Primary Examiner(s): Vy; Hung T
• Application Number:
  US11/302,226
• Publication Number:
  US 20060277165A1
• Time in Patent Office: 986 Days
• Field of Search: 707 2- 6, 707/100, 707/101, 704/4, 704/9, 704/231, 706/231
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A question answering system includes a question answering unit, an analysis unit, a tree structure generation unit, a feature extraction unit, an evaluation unit and a re-ranking unit. The question answering unit executes search processing based on an input question and acquires answer candidates to the question. The analysis unit executes syntactic analysis processing or syntactic and semantic analysis processing on a passage obtained as a result of the search processing. The tree structure generation unit generates a tree structure based on an analysis result. The feature extraction unit extracts a relation between a search word applied in the search processing and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure. The evaluation unit determines an evaluation value of each answer candidate based on the feature extracted. The re-ranking unit re-ranks the answer candidates based on the evaluation values.

Claims

1. A question answering system comprising:

a CPU;

a question answering unit that executes search processing on a basis of an input question and acquires answer candidates to the question;

an analysis unit that executes syntactic analysis processing or syntactic and semantic analysis processing on a passage obtained as a result of the search processing executed by the question answering unit to generate an analysis result holding a case relation between words of the passage to be analyzed;

a tree structure generation unit that generates a tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of the analysis result of the analysis unit;

a feature extraction unit that extracts a relation between a search word applied in the search processing executed by the question answering unit and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure generated by the tree structure generation unit;

an evaluation unit that determines an evaluation value of each answer candidate on a basis of the feature extracted by the feature extraction unit;

a re-ranking unit that re-ranks the answer candidates on a basis of the evaluation values determined by the evaluation unit;

a tree structure database that stores data of the tree structure generated by the tree structure generation unit in association with the passage based on which the data of the tree structure is generated; and

a passage search unit that executes search processing of the tree structure database on a basis of the passage input from the question answering unit, the question answering unit, analysis unit, tree structure generation unit, feature extraction unit, evaluation unit, re-ranking unit, and passage search unit being executed by the CPU,

wherein if the search processing executed by the passage search unit finds a passage in the tree structure database, the tree structure generation processing executed by the tree structure generation unit is skipped and the tree structure stored in association with the passage found from the tree structure database is used.

2. The question answering system according to claim 1, wherein the evaluation unit executes evaluation processing, to which a machine learning technique is applied, on the feature extracted by the feature extraction unit to determine the evaluation value of each answer candidate.

4. The question answering system according to claim 1, wherein the evaluation unit comprises:

a plurality of evaluation unit that execute evaluation processing, to which different machine learning techniques are applied, on the feature extracted by the feature extraction unit; and

an evaluation integration unit that integrates a plurality of evaluation results of the plurality of evaluation unit to determine a final evaluation value of each answer candidate.

3. A question answering system comprising:

a CPU;

a question answering unit that executes search processing on a basis of an input question and acquires answer candidates to the question;

an analysis unit that executes syntactic analysis processing or syntactic and semantic analysis processing on a passage obtained as a result of the search processing executed by the question answering unit to generate an analysis result holding a case relation between words of the passage to be analyzed;

a tree structure generation unit that generates a tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of the analysis result of the analysis unit;

a feature extraction unit that extracts a relation between a search word applied in the search processing executed by the question answering unit and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure generated by the tree structure generation unit;

an evaluation unit that determines an evaluation value of each answer candidate on a basis of the feature extracted by the feature extraction unit; and

a re-ranking unit that re-ranks the answer candidates on a basis of the evaluation values determined by the evaluation unit,

wherein;

the analysis unit executes the syntactic analysis processing on the passage,

the tree structure generation unit generates a syntactic tree on a basis of a result of the syntactic analysis processing executed by the analysis unit, the feature extraction unit executes processing of extracting number of predicates between the search word and each answer candidate as the feature on a basis of the syntactic tree, and

the question answering unit, analysis unit, tree structure generation unit, feature extraction unit, evaluation unit, and re-ranking unit are executed by the CPU.

5. A data search method comprising:

executing search processing on a basis of an input question and acquiring answer candidates to the question;

executing syntactic analysis processing or syntactic and semantic analysis processing on a passage obtained as a result of the search processing to generate an analysis result holding a case relation between words of the passage to be analyzed;

generating a tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of a result of the analysis;

extracting a relation between a search word applied in the search processing and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure generated;

determining an evaluation value of each answer candidate on a basis of the feature extracted;

searching a tree structure database storing data of the tree structure in association with the passage based on which the data of the tree structure is generated with using the passage acquired as queries;

executing feature extraction processing using a tree structure stored in association with the passage found from the tree structure database if the searching of the tree structure database finds a passage in the tree structure database, and

re-ranking the answer candidates on a basis of the evaluation values determined.

6. The data search method according to claim 5, wherein the determining of the evaluation value comprises executing evaluation processing, to which a machine learning technique is applied, on the feature extracted to determine the evaluation value of each answer candidate.

7. The data search method according to claim 5, wherein the determining of the evaluation value comprises:

executing a plurality of evaluation processings, to which different machine learning techniques are applied, on the feature extracted; and

integrating a plurality of evaluation results to determine a final evaluation value of each answer candidate.

8. A data search method comprising:

executing search processing on a basis of an input question and acquiring answer candidates to the question;

executing syntactic analysis processing or syntactic and semantic analysis processing on a passage obtained as a result of the search processing to generate an analysis result holding a case relation between words of the passage to be analyzed;

generating a tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of a result of the analysis;

extracting a relation between a search word applied in the search processing and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure generated;

determining an evaluation value of each answer candidate on a basis of the feature extracted; and

re-ranking the answer candidates on a basis of the evaluation values determined,

wherein;

the executing of the syntactic analysis processing or the syntactic and semantic analysis processing comprises executing the syntactic analysis processing on the passage,

the generating of the tree structure comprises generating a syntactic tree on a basis of a result of the syntactic analysis processing, and the extracting comprises executing processing of extracting number of predicates between the search word and each answer candidate as the feature on a basis of the syntactic tree.

9. A computer-readable medium storing a program for causing a computer to execute a data search processing comprising:

executing search processing on a basis of an input question and acquires answer candidates to the question;

executing syntactic analysis processing on a passage obtained as a result of the search processing to generate an analysis result holding a case relation between words of the passage to be analyzed;

generating a syntactic tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of the syntactic analysis;

extracting a relation between a search word applied in the search processing and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure generated;

determining an evaluation value of each answer candidate on a basis of the feature extracted;

searching a tree structure database storing data of the tree structure in association with the passage based on which the data of the tree structure is generated with using the passage acquired as queries;

executing feature extraction processing using a tree structure stored in association with the passage found from the tree structure database if the searching of the tree structure database finds a passage in the tree structure database, and

re-ranking the answer candidates on a basis of the evaluation values determined.

10. A question answering system comprising:

a CPU;

a question answering unit that executes search processing on a basis of an input question and acquires answer candidates to the question;

an analysis unit that executes syntactic and semantic analysis processing on a passage obtained as a result of the search processing executed by the question answering unit to generate a f-structure holding a case relation between words of the passage to be analyzed;

a tree structure generation unit that generates a tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of the f-structure of the analysis unit;

a feature extraction unit that extracts the case relation between a search word applied in the search processing executed by the question answering unit and each acquired answer candidate as a feature corresponding to each answer candidate on the basis of the tree structure generated by the tree structure generation unit;

an evaluation unit that determines an evaluation value of each answer candidate on a basis of the feature extracted by the feature extraction unit; and

a re-ranking unit that re-ranks the answer candidates on a basis of the evaluation values determined by the evaluation unit,

wherein the question answering unit, analysis, unit, tree structure generation unit, feature extraction unit, evaluation unit, and re-ranking unit are executed by the CPU.

11. A data search method comprising:

executing search processing on a basis of an input question and acquiring answer candidates to the question;

executing syntactic and semantic analysis processing on a passage obtained as a result of the search processing to generate a f-structure holding a case relation between words of the passage to be analyzed;

generating a tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of the f-structure;

extracting a relation between a search word applied in the search processing and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure generated;

determining an evaluation value of each answer candidate on a basis of the feature extracted; and

re-ranking the answer candidates on a basis of the evaluation values determined.

12. A computer-readable medium storing a program for causing a computer to execute a data search processing comprising:

executing search processing on a basis of an input question and acquiring answer candidates to the question;

executing syntactic and semantic analysis processing on a passage obtained as a result of the search processing to generate a f-structure holding a case relation between words of the passage to be analyzed;

generating a tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of the f-structure;

extracting a relation between a search word applied in the search processing and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure generated;

determining an evaluation value of each answer candidate on a basis of the feature extracted; and

re-ranking the answer candidates on a basis of the evaluation values determined.

13. A computer-readable medium storing a program for causing a computer to execute a data search processing comprising:

executing search processing on a basis of an input question and acquires answer candidates to the question;

executing syntactic analysis processing on a passage obtained as a result of the search processing to generate an analysis result holding a case relation between words of the passage to be analyzed;

generating a syntactic tree structure based on predicate-argument structure explicitly expressing the case relation on a basis of the syntactic analysis;

extracting a relation between a search word applied in the search processing and each acquired answer candidate as a feature corresponding to each answer candidate from the tree structure generated;

determining an evaluation value of each answer candidate on a basis of the feature extracted; and

re-ranking the answer candidates on a basis of the evaluation values determined,

wherein;

the executing of the syntactic analysis processing or the syntactic and semantic analysis processing comprises executing the syntactic analysis processing on the passage,

the generating of the tree structure comprises generating a syntactic tree on a basis of a result of the syntactic analysis processing, and

the extracting comprises executing processing of extracting number of predicates between the search word and each answer candidate as the feature on a basis of the syntactic tree.