机器学习

The Error-Correcting Output Codes method is a technique that allows a multi-class classification
problem to be reframed as multiple binary classification problems, allowing the use of native binary
classification models to be used directly.
Unlike one-vs-rest and one-vs-one methods that offer a similar solution by dividing a multi-class
classification problem into a fixed number of binary classification problems, the error-correcting output
codes technique allows each class to be encoded as an arbitrary number of binary classification
problems. When an overdetermined representation is used, it allows the extra models to act as “error-
correction” predictions that can result in better predictive performance.
In error-correcting output codes (ECOC), the main classification task is defined in terms of a
number of subtasks that are implemented by the base-learners. The idea is that the original task of
separating one class from all other classes may be a difficult problem. Instead, we want to define a set
of simpler classification problems, each specializing in one aspect of the task, and combining these
simpler classifiers, we get the final classifier.
Base-learners are binary classifiers having output −1/ + 1, and there is a code matrix W of K × L whose K
rows are the binary codes of classes in terms of the L base-learners dj. For example, if the second row of
W is [−1,+1,+1,−1], this means that for us to say an instance belongs to C2, the instance should be on the
negative side of d1 and d4, and on the positive side of d2 and d3. Similarly, the columns of the code
matrix defines the task of the base-learners. For example, if the third column is [−1,+1,+1]T , we
understand that the task of the third base-learner, d3, is to separate the instances of C1 from the
instances of C2 and C3 combined. This is how we form the training set of the base-learners. For example
in this case, all instances labeled with C2 and C3 form X+3 and instances labeled with C1 form X− 3 , and d3 is
trained so that xt ∈ X+3 give output +1 and xt ∈ X− 3 give output −1.
The code matrix thus allows us to define a polychotomy (K > 2 classification problem) in terms of
dichotomies (K = 2 classification problem), and it is a method that is applicable using any learninalgorithm to implement the dichotomizer base-learners—for example, linear or multilayer perceptrons
(with a single output), decision trees, or SVMs whose original definition is for two-class problems.
The typical one discriminant per class setting corresponds to the diagonal code matrix where L = K. For
example, for K = 4,
we have
The problem here is that if there is an error with one of the baselearners, there may be a
misclassification because the class code words are so similar. So the approach in error-correcting codes
is to have L > K and increase the Hamming distance between the code words. One possibility is pairwise
separation of classes where there is a separate baselearner to separate Ci from Cj, for i < j. In this case, L
= K(K − 1)/2 and with K = 4, the code matrix is
where a 0 entry denotes “don’t care.” That is, d1 is trained to separate C1 from C2 and does not use the
training instances belonging to the other classes. Similarly, we say that an instance belongs to C 2 if d1 =
−1 and d4 = d5 = +1, and we do not consider the values of d2, d3, and d6. The problem here is that L is
O(K2), and for large K pairwise separation may not be feasible.
If we can have L high, we can just randomly generate the code matrix with −1/ + 1 and this will work
fine, but if we want to keep L low, we need to optimize W. The approach is to set L beforehand and
then find W such that the distances between rows, and at the same time the distances between
columns, are as large as possible, in terms of Hamming distance. With K classes, there are 2(K-1) − 1
possible columns, namely, two-class problems. This is because K bits can be written in 2K different ways
and complements (e.g., “0101” and “1010,” from our point of view, define the same discriminant)
dividing the possible combinations by 2 and then subtracting 1 because a column of all 0s (or 1s) is
useless. For example, when K = 4, we have
When K is large, for a given value of L, we look for L columns out of the 2(K-1 )−1. We would like these
columns of W to be as different as possible so that the tasks to be learned by the base-learners are as
different from each other as possible. At the same time, we would like the rows of W to be as different
as possible so that we can have maximum error correction in case one or more base-learners fail.
ECOC can be written as a voting scheme where the entries of W, wij , are considered as vote weights:
65
and then we choose the class with the highest yi . Taking a weighted sum and then choosing the
maximum instead of checking for an exact match allows dj to no longer need to be binary but to take a
value between −1 and +1, carrying soft certainties instead of hard decisions. Note that a value pj
between 0 and 1, for example, a posterior probability, can be converted to a value dj between −1 and +1
simply as
One problem with ECOC is that because the code matrix W is set a priori, there is no guarantee that the
subtasks as defined by the columns of W will be simple.