SYSTEM AND METHOD FOR COMPILING RULES CREATED BY MACHINE LEARNING PROGRAM

• US 20090063375A1
• Filed: 10/31/2008
• Published: 03/05/2009
• Est. Priority Date: 11/08/2004
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Bangalore, Srinivas
• Granted Patent: US 7,778,944 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A system, a method, and a machine-readable medium are provided. A group of linear rules and associated weights are provided as a result of machine learning. Each one of the group of linear rules is partitioned into a respective one of a group of types of rules. A respective transducer for each of the linear rules is compiled. A combined finite state transducer is created from a union of the respective transducers compiled from the linear rules.

Claims

1. A method for compiling a plurality of linear rules created by machine learning for use in natural language processing, the method comprising:

compiling a respective transducer for each one of a plurality of types of rules obtained by partitioning a plurality of linear rules;

creating a combined finite state transducer from a union of the respective transducers compiled from the plurality of linear rules; and

processing natural language speech using the combined finite state transducer.

2. The method of claim 1, wherein the plurality of linear rules have associated weights and are provided as a result of machine learning.

3. The method of claim 2, wherein partitioning of the plurality of linear rules further comprises partitioning each of the plurality of the linear rules into a respective one of the plurality of types of rules.

4. The method of claim 3, wherein the machine learning comprises assigning weights to the plurality of linear rules based on using a boosting algorithm.

5. The method of claim 3, wherein the partitioned plurality of linear rules comprises weighted rewrite rules.

6. The method of claim 1, wherein the plurality of types of rules comprise:

a first rule type for testing a feature of a word or a sentence,

a second rule type for testing a feature of a left context, and

a third rule type for testing a feature of a right context.

7. The method of claim 1, further comprising:

applying an input to the combined finite state transducer;

searching for a best path for the input with respect to the finite state transducer; and

determining a best classification result based on the best path.

8. The method of claim 1, wherein creating a combined finite state transducer from a union of the respective transducers for the plurality of linear rules further comprises:

adding weights of paths having both a same input label and a same output label.

9. The method of claim 1, wherein compiling a respective transducer for each of the plurality of linear rules comprises:

compiling each of the respective transducers from a set of five transducers.

10. A machine-readable medium having instructions recorded therein for at least one processor to process natural language, the machine-readable medium comprising:

instructions for providing a plurality of linear rules and associated weights as a result of machine learning;

instructions for partitioning each of the plurality of linear rules into a respective one of a plurality of types of rules;

instructions for compiling a respective transducer for each of the types of rules with the associated partitioning from the plurality of linear rules;

instructions for creating a combined finite state transducer from a union of the respective transducers compiled from the plurality of linear rules; and

instructions for processing natural language speech using the combined finite state transducer.

11. The machine-readable medium of claim 10, wherein the plurality of linear rules have associated weights and are provided as a result of machine learning.

12. The machine-readable medium of claim 11, wherein partitioning of the plurality of linear rules further comprises partitioning each of the plurality of the linear rules into a respective one of the plurality of types of rules.

13. The machine-readable medium of claim 12, wherein the machine learning comprises assigning weights to the plurality of linear rules based on using a boosting algorithm.

14. The machine-readable medium of claim 12, wherein the partitioned plurality of linear rules comprise weighted rewrite rules.

15. The machine-readable medium of claim 10, wherein the plurality of types of rules comprise:

a first rule type for testing a feature of a word or a sentence,

a second rule type for testing a feature of a left context, and

a third rule type for testing a feature of a right context.

16. The machine-readable medium of claim 10, further comprising:

applying an input to the combined finite state transducer;

searching for a best path for the input with respect to the finite state transducer; and

determining a best classification result based on the best path.

17. The machine-readable medium of claim 10, wherein creating a combined finite state transducer from a union of the respective transducers for the plurality of linear rules further comprises:

adding weights of paths having both a same input label and a same output label.

18. The method of claim 10, wherein compiling a respective transducer for each of the plurality of linear rules comprises:

compiling each of the respective transducers from a set of five transducers.

19. A system is configured to compile respective transducer for each one of a plurality of linear rules created by machine learning, the plurality of linear rules for use in natural language processing, the system comprising:

at least one processor;

a memory;

a bus to permit communications between the at least one processor and the memory, wherein;

the system is configured to;

compile a respective transducer for each of the types of rules with the associated partitioning from the plurality of linear rules;

create a combined finite state transducer from a union of the respective transducers compiled from the plurality of linear rules; and

process natural language speech using the combined finite state transducer.

20. A system for compiling a plurality of linear rules created by machine learning for use in natural language processing, the system comprising:

means for compiling a respective transducer for each of the types of rules with the associated partitioning from the plurality of linear rules;

means for creating a combined finite state transducer from a union of the respective transducers compiled from the plurality of linear rules; and

means for processing natural language speech using the combined finite state transducer.