Error-Correcting Output Codes: A General Method for Improving Multiclass Inductive Learning Programs

Multiclass learning problems involve finding a definition for an unknown function f(x) whose range is a discrete set containing Ic > 2 values (i. e. , k “classes”). The definition is acquired by studying large collections of training examples of the form (xi, f(xi)). Existing approaches to this problem include (a) direct application of multiclass algorithms such as the decision-tree algorithms ID3 and CART, (b) application of binary concept learning algorithms to learn individual binary functions for each of the Ic classes, and (c) application of binary concept learning algorithms with distributed output codes such as those employed by Sejnowski and Rosenberg in the NETtalk system. This paper compares these three approaches to a new technique in which BCH error-correcting codes are employed as a distributed output representation. We show that these output representations improve the performance of ID3 on the NETtalk task and of backpropagation on an isolated-letter speech-recognition task. These results demonstrate that error-correcting output codes provide a general-purpose method for improving the performance of inductive learning programs on multiclass problems.

Authors

• Thomas G. Dietterich

Keywords

No keywords are indexed for this paper.