Methods to distribute multi-class classification learning on several processors

• US 7,552,098 B1
• Filed: 12/30/2005
• Issued: 06/23/2009
• Est. Priority Date: 12/30/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Haffner, Patrick
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US11/324,011
• Time in Patent Office: 1,271 Days
• Field of Search: None
• US Class Current: 706/20
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/34 Adaptation of a single recogniser for parallel processing, e.g. by use of multiple processors or cloud computing

Abstract

The time taken to learn a model from training examples is often unacceptable. For instance, training language understanding models with Adaboost or SVMs can take weeks or longer based on numerous training examples. Parallelization thought the use of multiple processors may improve learning speed. The invention describes effective methods to distributed multiclass classification learning on several processors. These methods are applicable to multiclass models where the training process may be split into training of independent binary classifiers.

Claims

1. A method for applying a model for an interactive voice response system comprising:

a) receiving a training data set at a first computing unit;

b) sorting classes of the training data set by frequency distribution at the first computing unit;

c) distributing the sorted classes as a plurality of S groups across a plurality of S processors using a round robin partition, wherein each group includes classes different from classes in each other group, and each group is distributed to a different processor of the plurality of S processors, each of the S processors being located within a different computing unit;

d) for each processor, processing the distributed group of sorted classes to produce learning data;

e) for each processor, distributing the learning data to each of the other processors;

f) merging results of the processing into a model at a second computing unit; and

g) outputting the model to cache operatively connected to the second computing unit; and

h) applying the model to an interactive voice response system.

2. The method of claim 1, wherein prior to b), the method further comprises determining if at least two training data in the training data set are identical, and merging identical data.

3. The method of claim 2, wherein merging identical data includes:

defining an order relationship for all data of the identical data;

sorting all of the data by the defined ordered relationship;

merging consecutive data that are equivalent; and

re-weighting the merged consecutive data.

4. The method of claim 3, wherein sorting all of the data includes a quick sort sorting routine.

5. The method of claim 1, wherein prior to b) the method further comprises transposing the training data set.

6. The method of claim 1, wherein prior to b) the method further comprises storing in cache memory previously processed classes of the training set data for each of the plurality of S processors.

7. The method of claim 1, wherein the frequency distribution of sorted classes within the groups is similar.

8. A method for applying a model for an interactive voice response system comprising:

a) receiving a training data set at a first computing unit;

b) splitting the training data sets along examples at the first computing device;

c) splitting the split training data sets from a) along classes at the first computing device;

d) separating the split training data sets from c) as a training set S into S subsets of equal size at the first computing device;

e) distributing the S subsets in d) across a plurality of S processors, wherein one subset is distributed to one processor, each of the S processors being located within a different computing unit;

f) for each of the plurality of S processors, determining all the classifiers of the distributed subset;

g) merging results of the processing into a model at a second computing unit;

h) outputting the model to cache operatively connected to the second computing unit; and

i) applying the model to an interactive voice response system.

9. The method of claim 8, wherein the method further comprises determining if at least two training data in the training data set are identical, and merging identical data.

10. The method of claim 8, wherein the method further comprises transposing the training data set.

11. The method of claim 8, the method further comprises storing in cache memory previously processed classes of the training set data for each of the plurality of S processors.