Training for a text-to-text application which uses string to tree conversion for training and decoding

• US 8,600,728 B2
• Filed: 10/12/2005
• Issued: 12/03/2013
• Est. Priority Date: 10/12/2004
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Knight, Kevin, Galley, Michel, Hopkins, Mark, Marcu, Daniel, Thayer, Ignacio
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): BAKER, MATTHEW H
• Application Number:
  US11/250,151
• Publication Number:
  US 20060142995A1
• Time in Patent Office: 2,974 Days
• Field of Search: 704 1- 10
• US Class Current: 704/2
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models
• CPC Class Codes: G06F 40/55 Rule-based translation

Abstract

Training and translation using trees and/or subtrees as parts of the rules. A target language is word aligned with a source language, and at least one of the languages is parsed into trees. The trees are used for training, by aligning conversion steps, forming a manual set of information representing the conversion steps and then learning rules from that reduced set. The rules include subtrees as parts thereof, and are used for decoding, along with an n-gram language model and a syntax based language mode.

Claims

1. A computer implemented method, comprising:

executing, by a processor, instructions stored in memory to use information that is based on corpora of string-based training information to create a plurality of rules that are based on the training information; and

performing source language string to target language tree translation using an n-gram language model, a syntax-based language model, and the plurality of rules for an executable text to text application stored in memory, the plurality of rules including syntactic translation rules that are each associated with a probability for a translation, wherein a syntactic translation rule is determined by analyzing an alignment graph that includes a source string, a target tree, and an alignment of the source string and the target tree.

2. A computer implemented method as in claim 1, further comprising:

obtaining a string to be translated;

executing instructions stored in memory to compile sets of different possible translation trees using the rules; and

executing instructions stored in memory to determine which of those translation trees represents probable translations.

3. A computer implemented method as in claim 2, further comprising executing instructions stored in memory to align a target word with a source word when the target word was created during a same process as that in which the source word is replaced.

4. A computer implemented method as in claim 2, wherein the compiling comprises:

executing instructions stored in memory to find individual words;

executing instructions stored in memory to find rules that apply to the individual words;

executing instructions stored in memory to find combinations of the individual words; and

executing instructions stored in memory to find rules that apply to the combinations of individual words.

5. A computer implemented method as in claim 2, wherein the compiling comprises compiling a complete set of derivation steps in any derivation of source string, target tree, and alignment.

6. A computer implemented method as in claim 5, wherein at least some elements in the trees are variables whose contents are defined by other trees.

7. A computer implemented method as in claim 6, wherein the alignment graph is used to determine an alignment by aligning source parts of a training corpora with target parts of the training corpora when the source part is created during the same step as that in which the source part is replaced.

8. A computer implemented method as in claim 7, wherein the alignment graph is analyzed to determine a smallest set of information that can form the set of rules.

9. A computer implemented method as in claim 8, wherein the smallest set of information includes frontier information.

10. A computer implemented method as in claim 1, further comprising executing instructions stored in memory to use parameter estimation techniques.

11. A computer implemented method as in claim 1, further comprising executing instructions stored in memory to flatten the trees to enable reordering of phrases.

12. A computer implemented method as in claim 1, further comprising:

executing instructions stored in memory to form an alignment graph that represents a conversion between nodes of the source string, leaves of the target tree, and alignment; and

executing instructions stored in memory to convert fragments of the alignment graph into rules.

13. A computer implemented method as in claim 12, wherein the fragments include substrings of the source string, and a span for the substring.

14. A computer implemented method as in claim 1, wherein the rules are formed by determining operations at which source symbols are replaced by target subtrees and by forming rules from the replacement process.

15. A computer implemented method as in claim 14, wherein an output of the rule is a symbol tree with at least some of its leaves labeled with variables rather than symbols from a target alphabet.

16. A computer implemented method as in claim 1, wherein using the information comprises extracting translation rules from word aligned pairs.

17. A computer implemented method as in claim 16, wherein the word aligned pairs comprise a tree in a first language and a string in a second language.

18. The method according to claim 1, further comprising resolving a syntactic crossing by:

generating a frontier set for the alignment graph by determining minimal frontier fragments for the alignment graph;

assembling together at least a portion of the minimal frontier fragments to form one or more frontier graph fragments; and

generating a lexical rule by performing multi-level reordering of nodes within at least one frontier graph fragment to resolve the syntactic crossing.

19. A computer implemented method, comprising:

executing, by a processor, instructions stored in memory to align items of information in first and second different languages to form aligned information, wherein at least the information in the first language is in a tree form; and

executing, by a processor, instructions stored in memory to extract rules from the aligned information, the rules utilizable in conjunction with an n-gram model and a syntax based language model, the rules configured for use with performing source language string to target language tree translation using an n-gram language model, a syntax-based language model, and the plurality of rules for an executable text to text application stored in memory, the plurality of rules including syntactic translation rules that are each associated with a probability for a translation, wherein a syntactic translation rule is determined by analyzing an alignment graph that includes a source string, a target tree, and an alignment of the source string and the target tree.

20. A computer implemented method as in claim 19, wherein the information in both the first and second languages are in the tree form.

21. A computer implemented method as in claim 19, further comprising:

executing instructions stored in memory to form tree based information into an alignment graph that aligns between a string in the first language and a tree in the second language; and

executing instructions stored in memory to extract rules from the alignment graph.

22. A computer implemented method as in claim 21, further comprising executing instructions stored in memory to analyze a reduced set of fragments of the alignment graph prior to extracting the rules, wherein the rules are utilized to resolve crossings between a source string and a target tree.

23. A computer implemented method, comprising:

obtaining a string in a source language to be translated into a target language; and

executing, by a processor, instructions stored in memory to translate the string into the target language using at least one rule set, an n-gram language model, and a syntax based language model, wherein the at least one rule set comprises both rules that include at least parts of subtrees and probabilities, a rule set including translation rules in a subtree to substring rule form for a machine translation, the translation rules being associated with probabilities for the rules, wherein a translation rule is determined by analyzing an alignment graph that includes a source string, a target tree, and an alignment of the source string and the target tree.

24. A computer implemented method as in claim 23, wherein the translating comprises first applying rules to individual words, and then applying rules to combinations of words.

25. A computer implemented method as in claim 23, further comprising executing instructions stored in memory to output trees as the translation.

26. A computer implemented method as in claim 25, wherein the system produces a plurality of different trees as possible translations, and selects the best tree according to a highest probability.

27. A system comprising:

a training part executable by a processor and stored in memory, the training part receiving a corpora of string-based training information to create a plurality of rules that are based on the training information, the rules including parts of trees as components of the rules; and

a text to text application portion that uses an n-gram language model, a syntax-based language model, and the rules for a text to text application performing source language string to target language tree translation, the rules including translation rules in a subtree to substring rule form for a machine translation, the translation rules being associated with probabilities for the rules, wherein a translation rule is determined by analyzing an alignment graph that includes a source string, a target tree, and an alignment of the source string and the target tree.

28. A system as in claim 27, further comprising a memory that stores the rules including parts of trees that are translation rules in a subtree to substring rule form for a machine translation, and also stores probabilities for the rules.

29. A system as in claim 28, wherein the application portion obtains a string to be translated, compiles sets of different possible translation trees using the rules, and determines which of those translation trees represents probable translations.

30. A system as in claim 27, wherein the training part forms an alignment graph that represents a conversion between source, target, and alignment, and converts fragments of the alignment graph into rules.

31. A system as in claim 30, wherein the rules are formed by determining operations at which source symbols are replaced by target subtrees and forming rules from the replacement process.

32. A system as in claim 30, wherein the alignment graph is analyzed to determine a smallest set of information that can form the set of rules.

33. A system, comprising:

a training module, executable by a processor and stored in a memory, that aligns items of information in first and second different languages to form aligned information and extracts rules from the aligned information,

wherein at least the information in the first language is in a tree form, and the rules are utilizable in conjunction with an n-gram model and a syntax based language model, the tree form utilized in a source language string to target language tree translation, the rules including translation rules in a subtree to substring rule form for a machine translation, the translation rules being associated with probabilities for the rules, wherein a translation rule is determined by analyzing an alignment graph that includes a source string, a target tree, and an alignment of the source string and the target tree.

34. A system as in claim 33, wherein the information in both the first and second languages are in the tree form.

35. A system as in claim 33, wherein the training part forms tree based information into an alignment graph that aligns between the first language and the second language, and extracts rules from the alignment graph.

36. A system as in claim 33, wherein the training part forms a reduced set of fragments of the alignment graph prior to extracting the rules.

37. A system, comprising:

a memory that stores at least one rule set that comprises both rules that include at least parts of subtrees and probabilities; and

a decoding part that obtains a string in a source language to be translated into a target language, receives the at least one rule set, and uses the at least one rule set, an n-gram language model, and a syntax based language model to translate the string into the target language, the decoding part performing source language string to target language tree translation, a rule set including translation rules in a subtree to substring rule form for a machine translation, the translation rules being associated with probabilities for the rules, wherein a translation rule is determined by analyzing an alignment graph that includes a source string, a target tree, and an alignment of the source string and the target tree.

38. A system as in claim 37, wherein the decoding part first applies rules to individual words, and then applies rules to combinations of words.

39. A system as in claim 37, wherein the decoding part outputs trees as the translation.

40. A system as in claim 39, wherein the decoding part produces a plurality of different trees as possible translations, and selects the best tree according to a highest probability.