Training tree transducers for probabilistic operations

• US 7,698,125 B2
• Filed: 03/15/2005
• Issued: 04/13/2010
• Est. Priority Date: 03/15/2004
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: Language Weaver, Inc. (RWS Holdings Plc)
• Inventors: Graehl, Jonathan, Knight, Kevin
• Primary Examiner(s): Opsasnick; Michael N
• Application Number:
  US11/082,216
• Publication Number:
  US 20050234701A1
• Time in Patent Office: 1,855 Days
• Field of Search: 704/5, 704/9, 704/254, 704/255
• US Class Current: 704/5
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

Tree transducers can be trained for use in probabilistic operations such as those involved in statistical based language processing. Given sample input/output pairs as training, and given a set of tree transducer rules, the information is combined to yield locally optimal weights for those rules. This combination is carried out by building a weighted derivation forest for each input/output pair and applying counting methods to those forests.

Claims

1. A method for performing probabilistic operations with trained tree transducers, the method comprising:

through execution of instructions stored in memory, obtaining tree transducer information including input/output pair information and transducer information;

through execution of instructions stored in memory, converting said input/output pair information and said transducer information into a set of values in a weighted tree grammar; and

through execution of instructions stored in memory, using said weighted tree grammar to solve a problem that requires information from the input/output pair information and transducer information.

2. A method as in claim 1, wherein said tree transducer information includes an input tree and an output tree as said input/output pair.

3. A method as in claim 1, wherein said tree transducer information includes an input tree and an output string as said input/output pair.

4. A method as in claim 1, further comprising, through execution of instructions stored in memory, converting said tree transducer information into a derivation forest.

5. A method as in claim 1, wherein said training further comprises maximizing an expectation of decisions.

6. A method as in claim 1, wherein said using comprises training a linguistic engine which solves a linguistic problem.

7. A method as in claim 6, wherein said linguistic problem includes training of a linguistic engine of a type that converts from one language to another.

8. A method as in claim 1, wherein said set of values represents information about the tree transducer information and transducer information in a specified grammar, associated with a weight for each of a plurality of entries.

9. A method as in claim 8, wherein said set of values are in a weighted regular tree grammar.

10. A method as in claim 9, wherein said converting comprises storing the set of values as a weighted regular tree grammar, and returning certain stored information instead of recomputing said certain stored information.

11. A method as in claim 1, further comprising, through execution of instructions stored in memory, further processing the set of values to sum weights based on information learned from said tree transducer information and said transducer information.

12. A method as in claim 11, wherein said further processing comprises using an inside-outside algorithm to observe counts and determine each time a rule gets used and to adjust said rule weights based on said observing.

13. A method as in claim 11, wherein said further processing comprises observing counts and determining each time a rule gets used, and increasing a probability of that rule each time the rule gets used.

14. A method as in claim 1, wherein said training further comprises computing a sum of all the counts for rules having the same state, to provide model weights for one of a joint or conditional probability distribution of the tree transducer information.

15. A method as in claim 1, wherein said using comprises solving a logic problem.

16. A method as in claim 15, wherein said logic problem is a problem that uses a machine to analyze and the aspect of at least one language.

17. A method for training tree transducers for probabilistic operations, the method comprising:

using a computer to obtain information in the form of a first-tree, second information corresponding to said first tree, and transducer information; and

using said computer to automatically distill information from said first tree, from said second information, and from said transducer information into a list of information in a specified tree grammar with weights associated with entries in the list and to produce locally optimal weights for said entries.

18. A method as in claim 17, wherein said automatically distill comprises observing when a specified rule in said list of information is used, and increasing said weight associated with said specified rule when said specified rule is used.

19. A method as in claim 17, further comprising using said list of information in said computer to solve a problem.

20. A method as in claim 19, wherein said problem is a linguistic problem.

21. A method as in claim 17, wherein said automatically distill comprises parsing the information from a first portion to a second portion.

22. A method as in claim 21, wherein said second information comprises a second tree.

23. A method as in claim 21, wherein said second information comprises a string.