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

• US 20060142995A1
• Filed: 10/12/2005
• Published: 06/29/2006
• Est. Priority Date: 10/12/2004
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Marcu, Daniel, Knight, Kevin, Galley, Michel, Hopkins, Mark, Thayer, Ignacio
• Granted Patent: US 8,600,728 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• 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 method comprising:

using 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 where the rules include parts of trees as parts of the rules; and

using said rules including said parts of trees for a text to text application.

2. A method as in claim 1, wherein said rules including parts of trees are translation rules in a subtree to substring rule form for a machine translation, and are associated with probabilities for the rules.

3. A method as in claim 2, further comprising obtaining a string to be translated, compiling sets of different possible translation trees using said rules, and determining which of those translation trees represents probable translations.

4. A method as in claim 2, wherein said training uses parameter estimation techniques.

5. A method as in claim 4, wherein said training uses an expectation maximization technique.

6. A method as in claim 2, further comprising flattening the trees to enable reordering of phrases.

7. A method as in claim 3, further comprising aligning a target word with a source word if the target word was created during a same process as that in which the source word is replaced.

8. A method as in claim 3, wherein said compiling set comprises compiling a complete set of derivation steps in any derivation of source, target and alignment.

9. A method as in claim 8, wherein at least some of the elements in the tree are variables whose contents are defined by other trees.

10. A method as in claim 1 further comprising forming an alignment graph which represents a conversion between source, target and alignment, and converting fragments of the alignment graph into rules.

11. A method as in claim 10, wherein said fragments include sub strings, and said rules include trees.

12. A method as in claim 9, wherein said alignment graph is used to determine an alignment by aligning source parts of a training corpora with target parts of said training corpora, but only when said source part is created during the same step as that in which the source part is replaced.

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

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

15. A method as in claim 12, wherein said alignment graph is analyzed to determine a smallest set of information that can form the set of rules.

16. A method as in claim 15, wherein said smallest set of information includes frontier information.

17. A method as in claim 3, wherein said decoding comprises finding individual words, first finding rules which apply to said individual words, then finding combinations of said individual words and finding rules which apply to said combinations of individual words.

18. A method as in claim 3, wherein said decoding comprises decoding using both of an n-gram language model and a syntax-based language model.

19. A method as in claim 1, wherein said using comprises extracting translation rules from word aligned pairs.

20. A method as in claim 19, wherein said word aligned pairs comprise word aligned pairs including a tree in a first language, and a string in a second language.

21. A method, comprising:

aligning items of information in first and second different languages to form aligned information, where at least said information in said first language is in a tree form; and

extracting rules from said aligned information.

22. A method as in claim 21, wherein said information in both the said first and second languages are in said tree form.

23. A method as in claim 21, further comprising forming tree based information into an alignment graph which aligns between said first language and said second language, and extracting rules from the alignment graph.

24. A method as in claim 23, further comprising, prior to said extracting rules, forming a reduced set of fragments of said alignment graph.

25. A method, comprising:

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

using at least one rule set which includes both rules that include at least parts of subtrees and also include probabilities, along with at least an ngram language model and a syntax based language model, to translate said string into said target language.

26. A method as in claim 25, wherein said translating comprises first applying rules to individual words, and then applying rules to combinations of words.

27. A method as in claim 25, further comprising outputting trees as the translation.

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

29. A system comprising:

a training part, receiving a corpora of string-based training information to create a plurality of rules that are based on the training information, and where the rules include parts of trees as components of the rules; and

a text to text application portion, using said rules including said parts of trees for a text to text application.

30. A system as in claim 29, further comprising a memory storing said rules including parts of trees are translation rules in a subtree to substring rule form for a machine translation, and also storing probabilities for the rules.

31. A system as in claim 30, wherein said application portion operates to obtain a string to be translated, compile sets of different possible translation trees using said rules, and determine which of those translation trees represents probable translations.

32. A system as in claim 29, wherein said training part forms an alignment graph which represents a conversion between source, target and alignment, and converts fragments of the alignment graph into rules.

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

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

35. A system as in claim 31, wherein said application portion includes and uses both of an n-gram language model and a syntax-based language model.

36. A system, comprising:

A training part, aligning a items of information in first and second different languages to form aligned information, where at least said information in said first language is in a tree form, and extracting rules from said aligned information.

37. A system as in claim 36, wherein said information in both the said first and second languages are in said tree form.

38. A system as in claim 36, wherein said training part forms tree based information into an alignment graph which aligns between said first language and said second language, and extracting rules from the alignment graph.

39. A system as in claim 36, further comprising, prior to said extracting rules, forming a reduced set of fragments of said alignment graph.

40. A system, comprising

a memory, storing at least one rule set which includes both rules that include at least parts of subtrees and also include probabilities, and

a decoding part, obtaining a string in a source language to be translated into a target language, and receiving said at least one rule set and using said at least one rule set along with at least both of an ngram language model and a syntax based language model, to translate said string into said target language.

41. A system as in claim 40, wherein said decoding part first applies rules to individual words, and then applies rules to combinations of words.

42. A system as in claim 40, wherein said decoding part outputs trees as the translation.

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