Information processing apparatus, natural language analysis method, program and recording medium

• US 8,793,121 B2
• Filed: 08/30/2012
• Issued: 07/29/2014
• Est. Priority Date: 03/03/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tsuboi, Yuta, Unno, Yuya
• Primary Examiner(s): ALBERTALLI, BRIAN LOUIS
• Application Number:
  US13/599,588
• Publication Number:
  US 20130060562A1
• Time in Patent Office: 698 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

An apparatus and method for calculating a score of matching a sentence with a query pattern having a dependency structure. The apparatus includes: an input unit acquiring an analysis target sentence, a query pattern and an index value indexing how a linguistic unit in the sentence tends to modify another; and a score calculation unit calculating a matching score indexing the degree of matching of the sentence with the query pattern. The matching score is represented by a function having an index value with which a dependency relation included in the query pattern is associated. The score is calculated by attempting association between a substructure of the query pattern and a range in the sentence and by performing recursive calculation in the substructure and the range while storing partial calculation result of the function in a memory area for reuse.

Claims

1. A natural language analysis method for calculating a score of matching of a sentence written in a natural language with a pattern having a dependency structure, the method comprising:

receiving as inputs a sentence to be analyzed, an index value indexing how a linguistic unit in said sentence tends to modify another, and a query pattern;

storing said inputs in a storage area; and

calculating a matching score indexing the degree of matching of said sentence with said query pattern by a processor, said matching score being represented by a function having at least a variable, said variable being an index value with which a dependency relation included in said query pattern is associated;

wherein

said calculating comprises a step of recursively calling a substep of attempting association between a substructure of said query pattern and a range in said sentence and performing a calculation while storing a partial calculation result of said function in a memory area for reusing said result, in said substructure and said range.

2. The natural language analysis method according to claim 1, wherein:

said function representing said matching score is a function that includes a product of the associated index values;

said partial calculation result of said function is a partial score represented by said function that includes a product of index values associated with dependency relations in said substructure of said query pattern in a case where said substructure is associated with said range in said sentence; and

said structure of said query pattern is followed by said recursive call step.

3. A computer program product for calculating a score of matching of a sentence with a pattern on a computer system, the computer program product comprising:

a computer readable storage medium having computer readable non-transient program code embodied therein, the computer readable program code comprising computer readable program code configured to perform the steps of a method according to claim 1.

4. A computer program product for calculating a score of matching of a sentence with a pattern on a computer system, the computer program product comprising:

a computer readable storage medium having computer readable non-transient program code embodied therein, the computer readable program code comprising computer readable program code configured to perform the steps of a method according to claim 2.

5. An information processing apparatus for calculating a score of matching a sentence with a pattern, the apparatus comprising:

an input unit receiving as inputs a sentence to be analyzed, an index value indexing how a linguistic unit in said sentence tends to modify another, and a query pattern; and

a score calculation unit calculating a matching score indexing the degree of matching of said sentence with said query pattern, said matching score being represented by a function having at least a variable, said variable being an index value with which a dependency relation included in said query pattern is associated;

wherein said score calculation unit calculates said score by attempting association between a substructure of said query pattern and a range in said sentence and performing recursive calculation in said substructure and said range while storing a partial calculation result of said function in a memory area for reusing said result.

6. The information processing apparatus according to claim 5, wherein:

said function representing said matching score includes a product of the associated index values;

said partial calculation result of said function is a partial score represented by said function, wherein said function includes a product of index values associated with dependency relations in said substructure of said query pattern at the time in a case where said substructure is associated with said range in said sentence; and

said score calculation unit follows the structure of said query pattern by said recursive calculation.

7. The information processing apparatus according to claim 6, wherein:

said index value is a marginal probability of dependency between said linguistic units in said sentence;

said matching score is a marginal probability of pattern of a candidate having said query pattern as a subtree being generated among analysis candidates of said sentence;

said function representing said matching score is a product of the associated marginal probabilities of dependency, and said function approximates said marginal probability of pattern;

said partial score is a local maximum value of a product of said marginal probabilities of dependency associated with the dependency relations in said substructure; and

said score calculation unit globally maximizes said marginal probability of pattern by said recursive calculation, following the structure of said query pattern.

8. The information processing apparatus according to claim 6, wherein:

said index value is a weight indexing how one linguistic unit in a language unit pair in said sentence tends to modify the other;

said matching score is an expected value of the number of pattern appearances that means an expectation that said query pattern appears as a subtree in analysis candidates of said sentence;

said function representing said matching score is a sum total of products for analysis candidates in which said query pattern appears, said product being a product of a probability of each analysis candidate in which said query pattern appears and the number of appearances, said probability of said analysis candidate being represented by normalizing a product of weights of dependency relations included in the analysis candidate;

said partial score is a sum total of products for association pairs inside said range in said sentence, said product being a product of the weights of each association pair; and

said score calculation unit calculates said expected value of the number of pattern appearances by counting up events of appearance of said query pattern by the recursive calculation while following the structure of said query pattern and the structure of said sentence, and adding the probability of the analysis candidate in which said query pattern appears.

9. The information processing apparatus according to claim 6, wherein:

said query pattern constitutes a tree structure including nodes to be matched with linguistic units and edges indicating dependency relations; and

said score calculation unit includes, as a group of functions for performing said recursive calculation, a first-type function of associating a substructure between an end of the descendants, on the side opposite of a parent of a first node of interest and the parent node in said query pattern with a first range in said sentence, and giving, for each attempt position at which said first node of interest is to be matched, the index value associated with a dependency relation from the attempt position to a position of said parent node as well as recursively calling said first-type function in a forward direction for a range on the side opposite to said parent, with the attempt position of said first range as a boundary to output said partial score for all the attempt positions.

10. The information processing apparatus according to claim 9, wherein:

said score calculation unit further includes, as the group of functions for performing said recursive calculation, a second-type function of associating a substructure between a second node of interest and a parent node in said query pattern with a second range in said sentence, recursively calling, for each attempt position separating descendants of a parent-side end child node and a sibling node of said second node of interest, said first-type function in an opposite direction for a range on the side opposite to said parent with the attempt position of said second range as a boundary and recursively calling said first-type function in the forward direction for a parent-side range to output a partial score for all the attempt positions; and

said first-type function recursively calls said forward-direction first-type function as well as recursively calling said second-type function in a forward direction for the parent-side range with the attempt position of said first range as a boundary.

11. The information processing apparatus according to claim 10, wherein:

said first-type function gives an end child node on the side opposite to said parent of said first node of interest when calling said forward-direction first-type function and gives said first node of interest when calling said forward-direction second-type function; and

said second-type function gives said parent-side end child node of said second node of interest when calling said opposite-direction first-type function and gives said sibling node of said second node of interest when calling said forward-direction first-type function.

12. The information processing apparatus according to claim 10, wherein:

said score calculation unit further includes, as the group of functions for performing said recursive calculation, a third-type function of associating a substructure between an end of descendants of a parent node of a third node of interest and said parent node in said query pattern with a third range in said sentence, recursively calling, for each attempt position separating an end of descendants on the side opposite to the parent of said third node of interest, said forward-direction first-type function for a parent-side range with the attempt position of said third range as a boundary to output a partial score for all the attempt positions; and

said first-type function recursively calls, for each attempt position in the case where said first node of interest does not match, said third-type function in a forward direction for said parent-side range with the attempt position of said first range as a boundary.

13. The information processing apparatus according to claim 12, wherein:

said first-type function gives an end child node on the side opposite to said parent of said first node of interest when calling said forward-direction first-type function and gives said first node of interest when calling said forward-direction second-type function;

said second-type function advances the process into said substructure of said query pattern, gives the parent-side end child node of said second node of interest when calling said opposite-direction first-type function and gives said sibling node of said second node of interest when calling said forward-direction first-type function; and

said third-type function does not advance the process into said substructure of said query pattern but gives said third node of interest when calling said forward-direction first-type function.

14. The information processing apparatus according to claim 9, wherein:

said group of functions includes left-direction functions such that a parent node of a node of interest is positioned on the right end of said substructure of said query pattern and right-direction functions such that said parent node of said node of interest is positioned on the left end of said substructure of said query pattern.

15. The information processing apparatus according to claim 5, wherein

said sentence to be analyzed is given as an element of a set of sentences that includes multiple sentences;

and

said information processing apparatus further comprises an information search interface outputting such an element that a matching score acquired satisfies a search condition, among said elements of said set of sentences, as a search result in response to a search request.

16. The information processing apparatus according to claim 15, wherein said information search interface accepts said search condition.

17. The information processing apparatus according to claim 5, wherein:

said sentence to be analyzed is given as an element of a set of sentences that includes multiple sentences; and

said information processing apparatus further comprises a function unit determining and outputting a sum total of matching scores acquired for said elements of said set of sentences.

18. The information processing apparatus according to claim 5, wherein said sentence to be analyzed is at least one of a projective two-way and one-way sentence, and said query pattern is a subtree of a projective dependency tree.

19. An information processing apparatus for calculating a score of matching of a sentence with a pattern, the apparatus comprising:

an input unit receiving as inputs a sentence to be analyzed, a marginal probability of dependency between linguistic units, and a query pattern; and

a score calculation unit calculating a marginal probability of pattern of a candidate having the query pattern as a subtree being generated among analysis candidates of the sentence as the score, the marginal probability of pattern being represented by a function of the marginal probability of dependency with which each dependency relation specified in the query pattern is associated;

wherein the score calculation unit calculates the marginal probability of pattern by attempting association between a substructure of the query pattern and a range in the sentence and performing recursive calculation inside said substructure and said range while storing a partial calculation result of the function in a memory area for reusing the result.

20. The information processing apparatus according to claim 19, wherein:

said function representing said marginal probability of pattern is a product of said marginal probabilities of dependency, and said function approximates said marginal probability of pattern;

said partial calculation result of said function is a local maximum value of a product of marginal probabilities of dependency with which dependency relations in said substructure of said query pattern in a case where said substructure is associated with said range in said sentence are associated; and

said score calculation unit globally maximizes said marginal probability of pattern by said recursive calculation.