Method for unsupervised learning of grammatical parsers

• US 9,460,076 B1
• Filed: 11/16/2015
• Issued: 10/04/2016
• Est. Priority Date: 11/18/2014
• Status: Active Grant

• Current Assignee: Lexalytics, Inc. (InMoment, Inc.)
• Original Assignee: Lexalytics, Inc. (InMoment, Inc.)
• Inventors: Barba, Paul F.
• Primary Examiner(s): AZAD, ABUL K
• Application Number:
  US14/941,724
• Time in Patent Office: 323 Days
• Field of Search: 704 1- 10
• US Class Current: 1/1
• CPC Class Codes: C12N 9/6427 Chymotrypsins (3.4.21.1; 3.4.21.2); Trypsin (3.4.21.4)
• CPC Class Codes: C12Y 304/21004 Trypsin (3.4.21.4)
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/088 Non-supervised learning, e.g. competitive learning

Abstract

The invention comprises a core algorithm to use language regularity in large collections of human created textual documents, as well as optimization techniques to make the algorithm tractable. The core algorithm includes receiving tuples of text units that may be grammatically linked and processing a stream of such tuples to discover language regularities. After this learning is completed, the algorithm'"'"'s output is used to evaluate the perceived likelihood that different interpretations of novel sentences would have been intended by a speaker of the language.

Claims

1. A method for unsupervised learning of a grammatical parser and the use thereof, wherein the method comprises:

providing a processor on a computer, wherein the processor runs a content acquisition system to obtain a corpus of text documents over a computer network;

storing the corpus of text documents from the content acquisition system on a storage device;

providing a processor on the computer which runs a text analytics engine, wherein the text analytics engine comprise a core algorithm, and a factorization algorithm;

using the core algorithm to;

divide the corpus of text documents into a plurality of sentences;

divide the sentences from the plurality of sentences into a plurality of text units;

join the text units from the plurality of text units into a plurality of grammatical links; and

using the factorization algorithm to factorize a matrix or a tensor for each of the grammatical links of the plurality of grammatical links to respectively generate a plurality of factorized matrices or a plurality of factorized tensors; and

additionally using the core algorithm to;

generate parses from a corpus of a novel document, comprising;

divide the corpus from the novel document into a plurality of sentences;

divide the sentences from the plurality of sentences from the novel document into a plurality of text units;

identify a subset of all possible grammatical links from the plurality of text units from the novel document; and

determine the relative likelihood of the grammatical links in the corpus of the novel document by using the factorized matrices or the factorized tensors to compute a score representing the likelihood of the grammatical links.

2. The method of claim 1, wherein the text units from the plurality of text units from the corpus of text documents are individual words in the sentences from the plurality of sentences of the corpus of text documents.

3. The method of claim 1, further comprising speech tagging the text units from the plurality of text units from the corpus of text documents into phrases.

4. The method of claim 3, further comprising storing the phrases in a respective factorized matrix or a factorized tensor as a first and a last word of the phrase.

5. The method of claim 1, further comprising classifying the text units from the plurality of text units from the corpus of the novel document against a human generated set of rules to narrow down the number of possible grammatical links.

6. The method of claim 1, further comprising updating the factorized matrix as new content is processed, wherein updating the factorized matrix includes use of an online factorization algorithm.

7. The method of claim 1, comprising both factorization of a matrix and a tensor, wherein factorizing the tensor includes encoding verbs from the text units of the plurality of text units from the corpus of text documents into a tensor with subjects and objects, and wherein factorizing the matrix includes encoding non-verbs from the text units of the plurality of text units from the corpus of text documents.

8. The method of claim 1, further comprising using a minimum spanning tree to combine the scored text unit links into a single parse.

9. The method of claim 1, further comprising providing a cutoff, wherein scores above the cutoff are used to determine the relative likelihood of a grammatical link.

10. The method of claim 1, further comprising generating features of the text units from the plurality of text units from the corpus of the novel document, and placing those features as additional rows and columns in the factorized matrix or the factorized tensor.

11. The method of claim 10, wherein the features of the text units are generated by an autoencoder.

12. The method of claim 10, wherein the features are an output of a semantic representation algorithm.

13. The method of claim 1, wherein the tensor to be factorized is a triple of the linked text units from the plurality of text units from the corpus of the documents being matched and a representation of the context in which the linked text units appear.

14. The method of claim 13, further comprising generating a plurality of semantic word vectors from the plurality of sentences from the corpus document, and wherein the representation of the context is a sum of the plurality of semantic word vectors.

15. The method of claim 14, wherein generating the plurality of semantic word vectors includes using a latent semantic analysis algorithm.

16. The method of claim 1, further comprising sorting the corpus of text documents into individual document classes, and generating a factorized matrix or a factorized tensor from each of the individual document classes, sorting the corpus of the novel document into individual document classes, and using the factorized matrix or the factorized tensor generated from each of the individual document classes to parse the novel document.

17. The method of claim 1, wherein the identification of grammatical links in the corpus of the novel document is restricted to follow grammatically sound rules provided by a human.

18. The method of claim 1, wherein the identification of grammatical links in the corpus of the novel document is restricted to follow a set of grammatically sound rules learned via a classifier on an annotated sample of document parses.