System and method for compiling rules created by machine learning program

• US 7,451,125 B2
• Filed: 11/07/2005
• Issued: 11/11/2008
• Est. Priority Date: 11/08/2004
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Bangalore, Srinivas
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US11/268,203
• Publication Number:
  US 20060100971A1
• Time in Patent Office: 1,100 Days
• Field of Search: None
• US Class Current: 706/47
• 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:

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

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

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

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 machine learning comprises assigning weights to the plurality of linear rules based on using a boosting algorithm.

3. The method of claim 1, wherein the partitioned plurality of linear rules comprise weighted rewrite rules.

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

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

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

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

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

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

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

11. The machine-readable medium of claim 8, 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.

12. The machine-readable medium of claim 8, further comprising:

instructions for applying an input to the combined finite state transducer;

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

instructions for determining a best classification result based on the best path.

13. The machine-readable medium of claim 8, wherein the instructions for creating a combined finite state transducer from a union of the respective transducers for the plurality of linear rules further comprise:

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

14. The machine-readable medium of claim 8, wherein the instructions for compiling a respective transducer for each of the plurality of linear rules further comprise:

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

15. A system for compiling 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;

provide a plurality of linear rules and associated weights as a result of the machine learning,

partition each of the plurality of linear rules into a respective one of a plurality of types of rules,

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.

16. The system of claim 15, wherein the machine learning is configured to assign weights to the plurality of linear rules based on using a boosting algorithm.

17. The system of claim 15, wherein the partitioned plurality of linear rules comprise weighted rewrite rules.

18. The system of claim 15, 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.

19. The system of claim 15, wherein the system is further configured to:

apply an input to the combined finite state transducer;

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

determine a best classification result based on the best path.

20. The system of claim 15, wherein the system being configured to compile a respective transducer for each of the plurality of linear rules further comprises the system being configured to:

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

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

means for receiving a plurality of linear rules and associated weights as a result of the machine learning;

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

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.