Training tree transducers

• US 20050234701A1
• Filed: 03/15/2005
• Published: 10/20/2005
• Est. Priority Date: 03/15/2004
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Graehl, Jonathan, Knight, Kevin
• Granted Patent: US 7,698,125 B2
• Time in Patent Office: Days
• US Class Current: 704/2
• 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

Training using tree transducers is described. 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, comprising:

obtaining tree transducer information including input/output pair information and transducer information;

converting said input/output pair information and said transducer information into a set of values in a weighted tree grammar; and

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 using comprises training a linguistic engine which solves a linguistic problem.

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

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

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

6. A method as in claim 1, further comprising converting said tree transducer information into a derivation forest.

7. 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.

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

9. A method as in claim 8, 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.

10. A method as in claim 1, further comprising further processing the set of values to sum weights based on information learned from said tree transducer information and said transducer information.

11. A method as in claim 10, 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.

12. A method as in claim 10, 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.

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

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 training apparatus comprising:

an input part which includes tree transducer information that includes input samples and output samples, and includes transducer information;

a processor that processes said tree transducer information and said transducer information and produces an output table indicative of said tree transducer information and said transducer information, said output table including a set of values, and weights for said set of values.

18. A training apparatus as in claim 17, further comprising a linguistic engine, receiving said output tables, addressing a linguistic problem based on said output tables.

19. A training apparatus as in claim 17, further comprising using an inside-outside algorithm to observe counts and determine each time a rule gets used and to adjust said rule weights based on the observing.

20. A training apparatus as in claim 17, wherein said input part is a tree transducer.

21. A training apparatus as in claim 20, wherein said output part is a tree transducer.

22. A training apparatus as in claim 20, wherein said output of part is a string transducer.

23. A training apparatus as in claim 17, wherein said output table stores a set of values as a regular tree grammar that is weighted with weights related to a number of times that each rule is used.

24. A training apparatus as in claim 23, wherein said processor is also operative to adjust said weights.

25. A training apparatus as in claim 17, further comprising a logic engine that analyzes at least one logical problem based on said output table.

26. A computer readable storage medium containing a set of instructions to enable a computer to carry out a function, the set of instructions including instructions to:

obtain tree transducer information including at least an input tree, output information corresponding to said input tree, and transducer information;

convert said tree transducer information into a weighted set of values indicative of said tree transducer information and said transducer information; and

use said set of values to solve a problem.

27. A storage medium as in claim 26, wherein said output information within said tree transducer information includes an output tree.

28. A storage medium as in claim 26, wherein said output information within said tree transducer information includes an output string.

29. A storage medium as in claim 26, wherein said instructions to convert include instructions to maximize an expectation that a rule will be used.

30. A 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, said from said second information, and 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.

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

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

33. A method as in claim 32, wherein said second information comprises a second tree.

34. A method as in claim 32, wherein said second information comprises a string.

35. A method as in claim 30, 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.

36. A method as in claim 31, wherein said problem is a linguistic problem.