REDUCING MULTICLASS CLASSIFICATION TO CLASSIFICATION

1. The problem

Given access to a box which can solve classification up to error rate ϵ, how can we optimally use it to solve multiclass classification? We first define the problems precisely, and then discuss several methods for reduction.

1.1. Binary classification. A binary classification problem is defined by a distribution D over an input space X and a binary output space Y = {0, 1}. A set of examples, (x, y)^{m} is fed to a classifier learning algorithm which produces a classifier c : X → Y. The goal of the learning algorithm is to find a classifier with a small error rate with respect to D:

min_{c} E_{x,y∼D}I(c(x) ≠ y)

1.2. Multiclass classification. A multiclass classification problem is defined by a distribution D over an input space X and a multiclass output space Y = {0, 1, ..., k}. A set of examples, (x, y)^{m} is fed to a classifier learning algorithm which produces a classifier c : X → Y. The goal of the learning algorithm is to find a classifier with a small error rate with respect to D:

min_{c} E_{x,y∼D}I(c(x) ≠ y)

2. Methods of reduction

There are several well known methods of reduction which we analyze for error transform efficiency.

2.1. The one-against-all reduction. In the one-against-all reduction, we learn k classifiers, one for each possible output label using data from the mapping:

(x, y) → ((x, l), I(y = l))

In order to construct a multiclass classifier from the k classifiers we use the following procedure:

Predict(h, x)

(1) If there exists a label l such that h(x, l) = 1 then predict l, breaking ties with randomization.

(2) Otherwise predict randomly.

Theorem 2.1. (One-against-all error efficiency) If the binary classifiers have error rate ϵ, the one-against-all reduction has error rate at most:

(\frac{k − 1}{2} + \frac{k − 1}{k})ϵ

Proof. (sketch) The worst case is when no example has more than one error. Most (k − 1 out of k) errors will be false positives which cause an error \frac{1}{2} of the time. For the false negative case, we get an error rate of \frac{k−1}{k}. □

2.2. The Tree Reduction. In the tree reduction we construct k − 1 classifiers which distinguish between the labels using a binary tree. The tree has depth log_{2} k, and each internal node is associated with a set of labels that can reach the node, assuming each classifier above it predicts correctly. The set of labels at that node is split into two sets of half the size, and a classifier is learned to distinguish between the two sets of labels.

Predictions are made by following the chain of classifications down to the leaves, which are associated with a unique label.

Theorem 2.2. (Tree error efficiency) If the binary classifiers have error rate ϵ, the tree reduction has error rate at most:

ϵ log_{2} k

Proof. An error occurs only if some classifier on the path from root to leaf errs. □

2.3. The error correcting output code (ECOC) reduction. In the (limiting) ECOC reduction, we learn a classifier for each of the 2^{k} subsets of labels. Any particular label will have a 2^{k} length binary vector associated with it corresponding to inclusion or not in the subset. Predictions are made by choosing the label with the largest dot product.

Theorem 2.3. (ECOC error efficiency) If the binary classifiers have error rate ϵ, the ECOC reduction has error rate at most:

2ϵ

Proof. The dot product between any two labels is 2^{k−1}. Consequently, in order for an error to occur on any one example, at least 2^{k−1} out of 2^{k} binary classifications must be incorrect. Since a multiclass error occurs only when \frac{1}{2} or more of the binary classifications are incorrect, the error rate is at most 2ϵ by the pigeonhole principle. □

Note: The ECOC reduction is typically applied to a subset of the powerset rather than the full powerset. The same basic result (with a worse constant) applies.

Note: Sometimes ECOC is analyzed assuming the errors are independent. This gives much better results, but seems less justifiable in practice. For example, in any setting with label noise, errors will be highly dependent.

3. Multilabel Classification to Binary Classification

Consider an extension of the multiclass classification problem where it is “ok” to predict any of a set of n labels out of k labels. This corresponds to a cost sensitive multilabel problem where the costs are discretized as either 0 or 1. This makes the problem easier than the multiclass classification problem. Can we take advantage of this extra ease? Many of the reductions above can be done in this new setting.

3.1. The One-against-all reduction. In the one-against-all reduction, we learn k classifiers, one for each possible output label using data from the mapping:

(x, y_{1}, y_{2}, ..., y_{n}) → ((x, l), I(l ∈ {y_{1}, ..., y_{n}}))

Suppose we use the same prediction function as in section 2.1. Then, we can prove the following theorem:

Theorem 3.1. (One-against-all n-of-k error efficiency) If the binary classifiers have error rate ϵ, the one-against-all reduction has error rate at most:

ϵ(\frac{k − n − 1}{n + 1} + \frac{k − n}{k} + max\{\frac{1}{n + 1}, \frac{n}{k}\})

Proof. (sketch) There are two forms of errors, false positive and false negative. For a false negative, the worst case is when all false negatives occur simultaneously (consuming n errors). If no false positives occur at the same time, then an error occurs with probability \frac{k−n}{k}. If a false positive also occurs (consuming n+1 errors), then an error occurs with probability 1.

For false positives when there are no false negatives, the worst case is when every error occurs seperately (since \frac{2}{n+2} < \frac{1}{n+1} + \frac{1}{n+1}). There are either k −n or k −n−1 possible false positives, and each has an error probability of \frac{1}{n+1}. Consequently, we get a total error probability of (\frac{k−n−1}{n+1} + 1)ϵ or (\frac{k−n}{n+1} + \frac{k−n}{k})ϵ. □

3.2. Tree reduction for multilabel classification. Use a tree of depth log_{2} k. In order to fail, you must be kicked into a subtree without a correct label. The exact number of errors required here is murky although certainly no worse than the single label case.

3.3. ECOC reduction for multilabel classification. In the ECOC reduction we again learn a classifier for every subset of the labels, rejecting samples in the subset and it’s complement?