Method and apparatus for full natural language parsing
View Patent ↗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.
1. A method executed by a processor in communication with a memory storing a computer process tagger program that when executed by the processor generates a linguistic parse tree for a sentence, the method comprising the steps of:
predicting by the computer process tagger a first level of chunk tags for the sentence; and
predicting by the computer process at least a second level of chunk tags for the sentence using the first level or a previous level of chunk tags;
from the predicted chunk tags, determining a sum of scores S in a graph G for a tag path [t] 1 N for words [w] 1 N as
S
(
[
w
]
1
N
,
[
t
]
1
N
,
θ
)
=
∑
n
=
1
N
(
A
t
n
-
1
t
n
+
s
(
x
n
)
t
n
)
,
where N is the number of words, θ represents trained parameters of a neural network of the tagger with a fixed-sized word dictionary W, trained parameter matrices M 1 and M 2 , and transition score A, each node G tn is assigned a score s(x n ) t n from the neural network of the tagger, and given a pair of nodes G tn and G um , an edge is added with a transition score A tu on the graph; and
outputting a graph with network scores provided for each G tn of the graph and additional transition scores for the edges of the graph.
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 and a memory, the memory embodying instructions that when executed by the processor cause the processor to perform the functions of:
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;
from the predicted chunk tags, determining a sum of scores S in a graph G for a tag path [t] 1 N for words [w] 1 N as
S
(
[
w
]
1
N
,
[
t
]
1
N
,
θ
)
=
∑
n
=
1
N
(
A
t
n
-
1
t
n
+
s
(
x
n
)
t
n
)
,
where N is the number of words, θ represents trained parameters of a neural network of a tagger with a fixed-sized word dictionary W, trained parameter matrices M 1 and M 2 , and transition score A, each node G tn is assigned a score s(x n ) t n from the neural network of the tagger, and given a pair of nodes G tn and G um , an edge is added with a transition score A tu on the graph; and
outputting a graph with network scores provided for each G tn of the graph and additional transition scores for the edges of the graph.
17. An apparatus for generating a linguistic parse tree for a sentence, the apparatus comprising: a processor and a memory, the memory embodying code that when executed by the processor causes the processor to perform the functions of:
code for predicting, via a Graph Transformer Network (GTN), a first level of chunk tags for the sentence, and
code for predicting at least a second level of chunk tags for the sentence using the first level or a previous level of chunk tags;
code for determining a sum of scores S from the predicted chunk tags in a graph G for a tag path [t] 1 N for words [w] 1 N as
S
(
[
w
]
1
N
,
[
t
]
1
N
,
θ
)
=
∑
n
=
1
N
(
A
t
n
-
1
t
n
+
s
(
x
n
)
t
n
)
,
where N is the number of words, θ represents trained parameters of a neural network of a tagger with a fixed-sized word dictionary W, trained parameter matrices M 1 and M 2 , and transition score A, each node G tn is assigned a score s(x n ) t n from the neural network of the tagger, and given a pair of nodes G tn and G um , an edge is added with a transition score A tu on the graph; and
outputting a graph with network scores provided for each G tn of the graph and additional transition scores for the edges of the graph.
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.