Syntactic classification of natural language sentences with respect to a targeted element

• US 10,133,724 B2
• Filed: 08/22/2016
• Issued: 11/20/2018
• Est. Priority Date: 08/22/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bethard, Sean L., Katz, Edward G., Phipps, Christopher
• Primary Examiner(s): Spooner, Lamont
• Application Number:
  US15/242,779
• Publication Number:
  US 20180052817A1
• Time in Patent Office: 820 Days
• Field of Search: 704 1, 704 9, 704 10
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 40/14 Tree-structured documents parsing G06F40/205; validation G06F40/226
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A grammatically diverse test set of natural language sentences for a deep question answering system is provided by analyzing a given sentence to characterize its syntactical classification, and adding the sentence to the test set if its classification is sufficiently different from other sentences already in the test set. A particular sentence may be selected for inclusion according to a desired syntactic distribution. Multiple sentences having the exact same classification may be allowed subject to a maximum number of such sentences. The test set is adapted to an element of interest by characterizing each syntactical classification relative to the element of interest. The analysis derives a parse tree, identifies a particular node of the tree corresponding to the element of interest, and extracts syntactic information by traversing the tree starting at the particular node and ending at the root node of the tree according to different traversal schemes.

Claims

1. A method of syntactically classifying a natural language sentence comprising:

receiving the natural language sentence in computer-readable form, by executing first instructions in a computer system;

parsing the natural language sentence to derive a parse tree having a plurality of nodes, by executing second instructions in the computer system;

identifying a particular one of the nodes that corresponds to an element of interest in the natural language sentence, by executing third instructions in the computer system;

extracting syntactic information from the parse tree relative to the particular node corresponding to the element of interest, by executing fourth instructions in the computer system;

recording the syntactic information as a classification for the natural language sentence, by executing fifth instructions in the computer system;

determining that the classification for the natural language sentence is different from classifications of other natural language sentences in a test set according to at least one predetermined similarity criterion related to the syntactic information, by executing sixth instructions in the computer system, wherein the predetermined similarity criterion allows two given sentences to be deemed similar even when the two given sentences have different classifications; and

responsive to said determining, adding the natural language sentence to the test set, by executing seventh instructions in the computer system.

2. The method of claim 1 wherein:

the parse tree nodes include a root node, one or more interior nodes, and a plurality of terminal nodes representing linguistic elements of the natural language sentence, the particular node corresponding to the element of interest being one of the terminal nodes;

each of the parse tree nodes has an associated linguistic identifier;

said extracting includes traversing the parse tree along a traversal path starting at the particular terminal node corresponding to the element of interest and ending at the root node; and

the syntactic information includes a sequence of linguistic identifiers associated with respective nodes of the traversal path in order of traversal.

3. The method of claim 2 wherein:

the parse tree includes a first node having a linguistic identifier with a semantic argument numeric index, and includes a second node associated with a linguistic element of the natural language sentence having a semantic argument corresponding to the numeric index; and

the traversal path includes a discontinuous jump of the parse tree from the first node directly to the second node.

4. The method of claim 2 wherein:

the parse tree includes a first node corresponding to a linguistic element of the natural language sentence which is a form of the verb “

to be” and

has a semantic role, and includes a second node associated with a linguistic element of the natural language sentence having a semantic argument index corresponding to the semantic role; and

the traversal path includes a discontinuous jump of the parse tree from the first node directly to the second node.

5. The method of claim 1 wherein the element of interest is an interrogative element.

6. The method of claim 1 wherein the particular node corresponding to the element of interest is identified by scanning the parse-tree for the element in a top-down, left-to-right, depth-first order.

7. The method of claim 1 wherein the predetermined similarity criterion allows the two given sentences to be deemed similar when their respective classifications are comprised of sequentialization labels having no more than a known number of different elements.

8. A computer system comprising:

one or more processors which process program instructions;

a memory device connected to said one or more processors; and

program instructions residing in said memory device for syntactically classifying a natural language sentence by receiving the natural language sentence, parsing the natural language sentence to derive a parse tree having a plurality of nodes, identifying a particular one of the nodes that corresponds to an element of interest in the natural language sentence, extracting syntactic information from the parse tree relative to the particular node corresponding to the element of interest, recording the syntactic information as a classification for the natural language sentence, determining that the classification for the natural language sentence is different from classifications of other natural language sentences in a test set according to at least one predetermined similarity criterion related to the syntactic information wherein the predetermined similarity criterion allows two given sentences to be deemed similar even when the two given sentences have different classifications, and responsively adding the natural language sentence to the test set.

9. The computer system of claim 8 wherein:

the parse tree nodes include a root node, one or more interior nodes, and a plurality of terminal nodes representing linguistic elements of the natural language sentence, the particular node corresponding to the element of interest being one of the terminal nodes;

each of the parse tree nodes has an associated linguistic identifier;

the extracting includes traversing the parse tree along a traversal path starting at the particular terminal node corresponding to the element of interest and ending at the root node; and

the syntactic information includes a sequence of linguistic identifiers associated with respective nodes of the traversal path in order of traversal.

10. The computer system of claim 9 wherein:

the parse tree includes a first node having a linguistic identifier with a semantic argument numeric index, and includes a second node associated with a linguistic element of the natural language sentence having a semantic argument corresponding to the numeric index; and

the traversal path includes a discontinuous jump of the parse tree from the first node directly to the second node.

11. The computer system of claim 9 wherein:

the parse tree includes a first node corresponding to a linguistic element of the natural language sentence which is a form of the verb “

to be” and

has a semantic role, and includes a second node associated with a linguistic element of the natural language sentence having a semantic argument index corresponding to the semantic role; and

the traversal path includes a discontinuous jump of the parse tree from the first node directly to the second node.

12. The computer system of claim 8 wherein the element of interest is an interrogative element.

13. The computer system of claim 8 wherein the particular node corresponding to the element of interest is identified by scanning the parse-tree for the element in a top-down, left-to-right, depth-first order.

14. The computer system of claim 8 wherein the predetermined similarity criterion allows the two given sentences to be deemed similar when their respective classifications are comprised of sequentialization labels having no more than a known number of different elements.

15. A computer program product comprising:

a computer readable storage medium; and

program instructions residing in said storage medium for syntactically classifying a natural language sentence by receiving the natural language sentence, parsing the natural language sentence to derive a parse tree having a plurality of nodes, identifying a particular one of the nodes that corresponds to an element of interest in the natural language sentence, extracting syntactic information from the parse tree relative to the particular node corresponding to the element of interest, recording the syntactic information as a classification for the natural language sentence, determining that the classification for the natural language sentence is different from classifications of other natural language sentences in a test set according to at least one predetermined similarity criterion related to the syntactic information wherein the predetermined similarity criterion allows two given sentences to be deemed similar even when the two given sentences have different classifications, and responsively adding the natural language sentence to the test set.

16. The computer program product of claim 15 wherein:

the parse tree nodes include a root node, one or more interior nodes, and a plurality of terminal nodes representing linguistic elements of the natural language sentence, the particular node corresponding to the element of interest being one of the terminal nodes;

each of the parse tree nodes has an associated linguistic identifier;

said extracting includes traversing the parse tree along a traversal path starting at the particular terminal node corresponding to the element of interest and ending at the root node; and

the syntactic information includes a sequence of linguistic identifiers associated with respective nodes of the traversal path in order of traversal.

17. The computer program product of claim 16 wherein:

the parse tree includes a first node having a linguistic identifier with a semantic argument numeric index, and includes a second node associated with a linguistic element of the natural language sentence having a semantic argument corresponding to the numeric index; and

the traversal path includes a discontinuous jump of the parse tree from the first node directly to the second node.

18. The computer program product of claim 16 wherein:

the parse tree includes a first node corresponding to a linguistic element of the natural language sentence which is a form of the verb “

to be” and

has a semantic role, and includes a second node associated with a linguistic element of the natural language sentence having a semantic argument index corresponding to the semantic role; and

the traversal path includes a discontinuous jump of the parse tree from the first node directly to the second node.

19. The computer program product of claim 15 wherein the element of interest is an interrogative element.

20. The computer program product of claim 15 wherein the predetermined similarity criterion allows the two given sentences to be deemed similar when their respective classifications are comprised of sequentialization labels having no more than a known number of different elements.