Information extraction using a trainable grammar

• US 20060253273A1
• Filed: 11/07/2005
• Published: 11/09/2006
• Est. Priority Date: 11/08/2004
• Status: Abandoned Application

• Current Assignee: ClearForest Ltd
• Original Assignee: ClearForest Ltd
• Inventors: Liberzon, Yair, Rosenfeld, Benjamin, Feldman, Ronen
• Application Number:
  US11/269,475
• Publication Number:
  US 20060253273A1
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

A computer-implemented method for information extraction includes defining a stochastic context free grammar (SCFG) including symbols and rules applicable to the symbols, the symbols including at least one output concept. The SCFG is trained on a tagged training corpus so as to determine probabilities of the rules and of one or more of the symbols. A document is parsed using the rules and symbols responsively to the probabilities so as to extract occurrences of the at least one output concept from the document.

Claims

1. A computer-implemented method for information extraction, comprising:

defining a stochastic context free grammar (SCFG) comprising symbols and rules applicable to the symbols, the symbols comprising at least one output concept;

training the SCFG on a tagged training corpus so as to determine probabilities of the rules and of one or more of the symbols; and

parsing a document using the rules and symbols responsively to the probabilities so as to extract occurrences of the at least one output concept from the document.

2. The method according to claim 1, wherein the symbols in the SCFG comprise a termlist symbol, which comprises a collection of terms from a single semantic category.

3. The method according to claim 1, wherein the symbols in the SCFG comprise an ngram symbol, such that when the ngram symbol is used in one of the rules, it can expand to any single token.

4. The method according to claim 3, wherein training the SCFG comprises computing the probabilities of different expansions of the ngram symbol.

5. The method according to claim 4, wherein computing the probabilities comprises finding conditional probabilities of the different expansions depending upon a context of the ngram symbol.

6. The method according to claim 5, wherein computing the probabilities comprises interpolating over a bigram probability model depending upon the context of the ngram symbol and a unigram probability model of the ngram symbol.

7. The method according to claim 3, wherein the ngram symbol comprises an unknown symbol, and wherein parsing the document comprises applying the probabilities determined with respect to the unknown symbol in parsing an unknown token in the document.

8. The method according to claim 1, wherein defining the SCFG comprises defining a dependence of at least one of the rules on a context of a symbol to which the at least one of the rules is to apply, and wherein training the SCFG comprises finding a conditional probability of the at least one of the rules depending upon the context of the symbol.

9. The method according to claim 1, wherein parsing the document comprises applying an external feature generator in order to identify features of tokens in the document, and extracting the occurrences of the at least one output concept responsively to the features.

10. The method according to claim 1, and comprising, after parsing the document, enhancing the SCFG by performing at least one of adding a further rule to the SCFG and further tagged tokens to the training corpus.

11. A computer software product, comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive a definition of a stochastic context free grammar (SCFG) comprising symbols and rules applicable to the symbols, the symbols comprising at least one output concept, to train the SCFG on a tagged training corpus so as to determine probabilities of the rules and of one or more of the symbols, and to parse a document using the rules and symbols responsively to the probabilities so as to extract occurrences of the at least one output concept from the document.

12. The product according to claim 11, wherein the symbols in the SCFG comprise a termlist symbol, which comprises a collection of terms from a single semantic category.

13. The product according to claim 11, wherein the symbols in the SCFG comprise an ngram symbol, such that when the ngram symbol is used in one of the rules, it can expand to any single token.

14. The product according to claim 13, wherein the instructions cause the computer to compute the probabilities of different expansions of the ngram symbol.

15. The product according to claim 14, wherein the probabilities of the different expansions comprise conditional probabilities depending upon a context of the ngram symbol.

16. The product according to claim 15, wherein the instructions cause the computer to compute the probabilities by interpolating over a bigram probability model depending upon the context of the ngram symbol and a unigram probability model of the ngram symbol.

17. The product according to claim 13, wherein the ngram symbol comprises an unknown symbol, and wherein the instructions cause the computer to apply the probabilities determined with respect to the unknown symbol in parsing an unknown token in the document.

18. The product according to claim 11, wherein the SCFG defines a dependence of at least one of the rules on a context of a symbol to which the at least one of the rules is to apply, and wherein the instructions cause the computer to find a conditional probability of the at least one of the rules depending upon the context of the symbol.

19. The product according to claim 11, wherein the instructions cause the computer to apply an external feature generator in order to identify features of tokens in the document, and to extract the occurrences of the at least one output concept responsively to the features.

20. The product according to claim 11, wherein the product causes the computer, after parsing the document, to enable a user to enhance the SCFG by performing at least one of adding a further rule to the SCFG and further tagged tokens to the training corpus.

21. Apparatus for information extraction (IE), comprising:

an input interface, which is coupled to receive a definition of a stochastic context free grammar (SCFG) comprising symbols and rules applicable to the symbols, the symbols comprising at least one output concept; and

an IE processor, which is adapted to train the SCFG on a tagged training corpus so as to determine probabilities of the rules and of one or more of the symbols, and to parse a document using the rules and symbols responsively to the probabilities so as to extract occurrences of the at least one output concept from the document.

22. The apparatus according to claim 21, wherein the symbols in the SCFG comprise a termlist symbol, which comprises a collection of terms from a single semantic category.

23. The apparatus according to claim 21, wherein the symbols in the SCFG comprise an ngram symbol, such that when the ngram symbol is used in one of the rules, it can expand to any single token.

24. The apparatus according to claim 21, wherein the SCFG defines a dependence of at least one of the rules on a context of a symbol to which the at least one of the rules is to apply, and wherein the processor is adapted to find a conditional probability of the at least one of the rules depending upon the context of the symbol.