Method and Apparatus for Full Natural Language Parsing

• US 20110301942A1
• Filed: 06/01/2011
• Published: 12/08/2011
• Est. Priority Date: 06/02/2010
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Collobert, Ronan, Bai, Bing
• Granted Patent: US 8,874,434 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

The method and apparatus for discriminative natural language parsing, uses a deep convolutional neural network adapted for text and a structured tag inference in a graph. In the method and apparatus, a trained recursive convolutional graph transformer network, formed by the deep convolutional neural network and the graph, predicts “levels” of a parse tree based on predictions of previous levels.

Claims

1. A method for generating a linguistic parse tree for a sentence, the method comprising the steps of:

predicting in a computer process a first level of chunk tags for the sentence; and

predicting in a computer process at least a second level of chunk tags for the sentence using the first level or a previous level of chunk tags.

2. The method of claim 1, wherein the predicting steps are performed by a Graph Transformer Network (GTN).

3. The method of claim 2, wherein the GTN includes a deep convolutional neural network (CNN).

4. The method of claim 3, wherein the CNN generates scores for potential chunk tags for words of the sentence.

5. The method of claim 2, wherein for each level, further comprising the step of combining chunk tag scores of each word of a sequence words of the sentence, and transition scores between chunk tags of a pair of consecutive words to evaluate the score for the chunk tags of the sequence of words.

6. The method of claim 5, wherein the combining step is performed with a Viterbi algorithm.

7. The method of claim 2, wherein each of the predicting steps comprises the steps of:

finding vectors for different features of words of the sentence; and

combining the vectors as a whole feature vector.

8. The method of claim 2, wherein each of the predicting steps uses long range dependency in the form of a lookup table.

9. The method of claim 1, wherein the step of predicting at least a second level of chunk tags is performed so that any chunk at a level overlapping a chunk at the at least the second level must span at least this over-lapped chunk, and be larger.

10. The method of claim 1, wherein the determining steps are performed with a deep convolutional neural network (CNN).

11. The method of claim 10, wherein the CNN generates scores for potential chunk tags for words of the sentence.

12. The method of claim 1, wherein for each level, further comprising the step of combining chunk tag scores of each word of a sequence words of the sentence, and transition scores between chunk tags of a pair of consecutive words to evaluate the score for the chunk tags of the sequence of words.

13. The method of claim 12, wherein the combining step is performed with a Viterbi algorithm.

14. The method of claim 1, wherein each of the predicting steps comprises the steps of:

finding vectors for different features of words of the sentence; and

combining the vectors as a whole feature vector.

15. The method of claim 1, wherein each of the predicting steps uses long range dependency in the form of a lookup table.

16. An apparatus for generating a linguistic parse tree for a sentence, the apparatus comprising:

a processor executing instructions for;

predicting a first level of chunk tags for the sentence; and

predicting at least a second level of chunk tags for the sentence using the first level or a previous level of chunk tags.

17. An apparatus for generating a linguistic parse tree for a sentence, the apparatus comprising a Graph Transformer Network (GTN) for predicting a first level of chunk tags for the sentence, and predicting at least a second level of chunk tags for the sentence using the first level or a previous level of chunk tags.

18. The apparatus of claim 17, wherein the GTN includes a deep convolutional neural network (CNN) for generating scores for potential chunk tags for words of the sentence.

19. The apparatus of claim 17, wherein for each level, the GTN combines chunk tag scores of each word of a sequence words of the sentence, and transition scores between chunk tags of a pair of consecutive words to evaluate the score for the chunk tags of the sequence of words.

20. The apparatus of claim 17, wherein the GTN predicts the levels of chunk tags by finding vectors for different features of words of the sentence;

and combining the vectors as a whole feature vector.

21. The apparatus of claim 17, wherein GTN uses long range dependency in the form of a lookup table to predict the levels of chunk tags.