Error Limiting Reductions Between Classification Tasks

Keywords: supervised learning, reductions, classification

Abstract

We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most ϵ then the cost-sensitive classifier has cost at most 2ϵ times the expected sum of costs of all choices. Since cost-sensitve classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning.

1 Introduction

Supervised learning involves learning a function from supplied examples. There are many natural supervised learning tasks; classification alone comes in a number of different forms (e.g., binary, multi-class, costsensitive, importance weighted). Generally, there are two ways to approach a new task^{1}. The first is to solve it independently from other tasks. The second is to reduce it to a task that has already been thoroughly analyzed, automatically transferring existing theory and algorithms from well-understood tasks to new tasks. We investigate (and advocate) the latter approach.

Motivation. Informally, a reduction is a learning machine that solves one task using oracle (i.e., black-box) access to a solver for another task. Reductions present a powerful tool with a number of desirable properties:

1. They provide a formal way of comparing how relatively easy different tasks are. If task A reduces to task B, it is reasonable to say that A is not much harder than B. If in addition B also reduces to A, we can conclude that A and B are similar. The more restricted the notion of a reduction, the stronger the conclusions.

2. If A can be reduced to B, then techniques for solving B can be used to solve A, transferring results from one learning task to another. This saves both research and development effort.

3. Reductions allow one to study an entire class of tasks by focusing on a single primitive (they also help to identify such primitives). Any progress on the primitive immediately implies progress for every task in the class. It also simplifies the evaluation of different learning algorithms for effectiveness.

4. Viewed as negative statements, reductions imply relative lower bounds stating that progress on one task cannot be achieved without making progress on some primitive.

There is an essential discrepancy between theory and practice of supervised learning. On one hand, it is impossible to prove, without making any assumptions, that we can learn to predict well. (For example, in PAC-learning we might assume that all examples are sampled independently and the problem is predicting an unknown decision list.) On the other hand, learning algorithms are often succesfully used in practice.

Reductions give us a way to cope with this discrepancy. They provide us with a useful tool to show relative ability to learn – relative to basic tasks that are better understood. In other words, reductions allow us to make statements of the form “Good performance of the oracle on subproblems generated by the reduction translates into good performance on the original problem”. Such statements can be made without any assumptions that cannot be verified, or do not generally hold in practice.

We propose an analysis framework allowing us to prove such error transformation guarantees. Attempts to understand this framework in terms of sample complexity based models of learning (?; ?) will fail; it is important to understand that this is a different model of analysis.

To test the model, we consider learning machines which have oracle access to a solver for classification problems, and ask what can be done with such a machine. Section ?? presents a new reduction from cost-sensitive classification to binary classification and quantifies the way in which errors by the binary classification oracle induce errors in the original problem. Since cost-sensitve classification (see the definitions in Section ??) can express any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle.

1We use “task” instead of a more common “problem”

because we distinguish between them formally.

Preliminary work. Under review by the International Conference on Machine Learning (ICML). Do not distribute.

To give further evidence that the proposed framework allows for a tractable analysis, we show how to analyze several existing algorithms in this model (see Section ??).

In addition to the above theoretical motivations, there is significant empirical evidence (see (?), (?), (?)) that this style of analysis often produces learning algorithms that perform well in practice. Section ?? presents experimental results showing that our new reduction outperforms existing algorithms for multiclass cost-sensitive learning.

2 Basic Definitions

This section defines the basic concepts. Definition 1. A supervised learning task is a tuple (K, Y, ℓ), where K is the space of supervised advice available at training time, Y is a prediction space, and ℓ : K × Y → [0, ∞) is a loss function.

We assume that ℓ is nonconstant in both arguments, which is satisfied by any reasonable loss function. To test the definition, we instantiate it for common classification tasks. For binary classification, K = {0, 1} (the space of labels given for training examples), Y = {0, 1}, and ℓ(k, y) = I(k ≠ y), where I(·) is the indicator function which is 1 when the argument is true and 0 otherwise. A simple generalization to more than two labels gives multiclass classification with K = Y = {1, …, r} and ℓ(k, y) = I(k ≠ y).

In general, the space K of advice provided at training time need not equal the prediction space Y. We sometimes need this additional flexibility (also used in (?)) to provide some information to the learning algorithm about the loss of different choices. For example, in importance weighted classification, we want to specify that predicting some examples correctly is more important than predicting others, which is done by letting K = {1, …, r} × [0, ∞) and ℓ(⟨k_{1}, k_{2}⟩, y) = k_{2}I(k_{1} ≠ y). In cost-sensitive classification, K is used to associate a cost to each prediction y ∈ Y by setting K = [0, ∞)^{r} and ℓ(⟨k_{1}, …, k_{r}⟩, y) = k_{y}. In both examples above, the prediction space Y is {1, …, r}.

A task is (implicitly) a set of learning problems, each of which requires more information to be fully specified.

Definition 2. A supervised learning problem is a tuple (D, X, T ), where T = (K, Y, ℓ) is a supervised learning task, X is an arbitrary feature space, and D is a distribution over X × K.

The goal in solving a supervised learning problem is to find a hypothesis h : X → Y minimizing the expected loss E_{(x,k)∼D}ℓ(k, h(x)). Finding h is difficult because D is generally not known at training time. For any particular hypothesis h, the loss rate

h_{D} = E_{(x,k)∼D}ℓ(k, h(x))

is a fundamental quantity of interest.

Definition 3. A supervised learning algorithm for task (K, Y, ℓ) is a procedure mapping any finite set of examples in (X × K)^{∗} to a hypothesis h : X → Y.

We do not require that training and test examples are drawn from the same distribution. We also do not require the samples to agree with some hypothesis in a predetermined class, as in the PAC learning model.

We use these definitions in Section ?? to define the error limiting reductions model, mentioned informally in the introduction. Ultimately, the real test of a learning model is whether it allows for tractable analysis leading to useful learning algorithms. Thus to motivate the formulations of the model, we first show an example of what can be done with this model. In particular, we present a new reduction from cost-sensitive classification to binary classification and prove its errortransformation bounds. To give further evidence, Section ?? shows that the model captures several existing machine learning algorithms.

3 Reduction from Cost Sensitive Classification to Binary Classification

We present a new reduction, Weighted All-Pairs, from r-class cost sensitive classification to importance weighted binary classification. It can be composed with the Costing reduction (?) to yield a reduction to binary classification. Since cost sensitive classification can express any supervised learning task we consider, this implies that any such task can be solved using binary classification. (The reduction is defined for any feature space X, and we assume that X has been fixed and all distributions are over X × [0, ∞)^{r}.)

3.1 The Algorithm

For a given cost-sensitive example (x, k_{1}, …, k_{r}), let L(t) be the function L(t) = |{j | k_{j} ≤ t}|, for t ∈ [0, ∞). By shifting, we may assume that the minimum cost k_{min} = 0, so that t ≥ 0 implies L(t) ≥ 1. Optimizing the loss of the shifted problem is equivalent to optimizing the loss of the original problem. To define the reduction, we need values v_{i} defined by

v_{i} = ∫_{0}^{k_{i}} 1/L(t)dt.

Note that the values are order-preserving: k_{i} < k_{j} iff v_{i} < v_{j} for all i and j.

The algorithms specifying the reduction are given below.

1 WAP-Train (Set of r-class cost sensitive examples S, importance weighed binary classifier learning algorithm B)

Set S′ = ∅. for all examples (x, k_{1}, …, k_{r}) in S do

for all pairs (i, j) with 1 ≤ i < j ≤ r do Add an importance weighted example (⟨x, i, j⟩, I(k_{i} < k_{j}), |v_{j} − v_{i}|) to S′.

end for end for Return h = B(S′).

We say that label i beats label j for input x if either i < j and h(⟨x, i, j⟩) = 1, or i > j and h(⟨x, j, i⟩) = 0.

2 WAP-Test (classifier h, example x)

for all pairs (i, j) with 1 ≤ i < j ≤ r do

Evaluate h(⟨x, i, j⟩) end for Output argmax_{i}|{j | i beats j}|.

Note that if h makes no errors and k_{i} ≠ k_{j}, then label i beats label j exactly when k_{i} < k_{j}. WAP-Test outputs the label which beats the maximum number of other labels, with ties broken arbitrarily.

Before stating the error transform, we must first define the distribution induced by the reduction on the importance-weighted binary classifier (to which the reduction makes a single call). To draw a sample from this distribution, we first draw a cost sensitive sample (x, k_{1}, …, k_{r}) from the input distribution D and then apply WAP-Train to the singleton set \{(x, k_{1}, …, k_{r})\} to get a sequence of \binom{r}{2} examples for the binary classifier. Now we just sample uniformly from this set. We overload and denote the induced distribution by WAP-Train(D). Recall that the loss rate of classifier h on distribution D is denoted by h_{D}. Theorem 1. (WAP error efficiency) For all importance weighted binary learning algorithms B and costsensitive datasets S, let h = WAP-Train(S, B). Then for all cost-sensitive test distributions D,

WAP-Test(h)_{D} ≤ 2h_{WAP-Train(D)}.

This theorem states that the cost sensitive loss is bounded by twice the importance weighted loss on the induced importance weighted learning problem.

Theorem ?? and the Costing reduction (Theorem ?? in Section ??) imply the following efficiency guarantess:

Theorem 2. For all cost sensitive test distributions D, let D′ be the binary classification problem induced by WAP-Train and Costing, and h be the learned binary classifier. Then

WAP-Test(h)_{D} ≤ 2h_{D′}E_{⟨x,k_{1},...,k_{r}⟩∼D} ∑_{i=1}^{r} k_{i}.

For notational simplicity, assume that k_{1} ≤ ⋯ ≤ k_{r}. Note that no generality is lost since the algorithm does not distinguish between the labels. The following insight is the key to the proof.

Lemma 1. Suppose label i is the winner. Then, for every j ∈ {1, …, i − 1}, there must be at least ⌈j/2⌉ pairs (a, b), where a ≤ j < b, and b beats a.

Proof. (Lemma ??) Consider the restricted tournament on {1, …, j}.

Case 1: Suppose that some w beats at least ⌈j/2⌉ of the others. If no label b > j beats any label a ≤ j, then w would beat at least ⌈j/2⌉ + 1 more labels than any b > j; in particular, w would beat at least ⌈j/2⌉ + 1 more labels than i. Thus, in order to have label i beat as many labels as w, at least ⌈j/2⌉ edges of the form (w, b), b > j or (a, i), a ≤ j must be reversed.

Case 2: There is no label w ∈ {1, …, j} beating ⌈j/2⌉ of the rest of {1, …, j}. This can only happen if j is odd and there is a j-way tie with (j − 1)/2 losses per label in {1, …, j}. In this case, although every label beats (j+1)/2 more labels than any b > j, in particular i, it is still necessary to reverse at least (j + 1)/2 ≥ ⌈j/2⌉ edges, in order to ensure that i > j beats as many labels as each of {1, …, j}.

Proof. (Theorem ??) Suppose that our algorithm chooses the wrong label i for a particular example (x, k_{1}, …, k_{r}). We show that this requires the adversary to incur a comparable loss.

Lemma ?? and the definition of v_{i} imply that the penalty incurred to make label i win is at least

∫_{0}^{k_{i}} \frac{⌈L(t)/2⌉}{L(t)}dt ≥ ∫_{0}^{k_{i}} \frac{1}{2}dt = \frac{k_{i}}{2} .

On the other hand, the total importance assigned to queries for this instance equals

∑_{i<j} v_{j} − v_{i} = ∑_{i<j} ∫_{k_{i}}^{k_{j}} \frac{1}{L(t)}dt = ∫_{0}^{k_{r}} \frac{L(t)R(t)}{L(t)}dt

= ∫_{0}^{k_{r}} R(t)dt = ∑_{i=1}^{r} ∫_{0}^{k_{i}} dt = ∑_{i=1}^{r} k_{i},

where R(t) = r − L(t) is the number of labels whose value is greater than t and the second equality follows from switching the order of summation and counting the number of time a pair (i, j) satisfies i < t < j. The second to last equality follows by writing R(t) as a sum of the r indicator functions for the events {k_{j} > t}, and then switching the order of summation.

Consequently, for every example (x, k_{1}, …, k_{r}), the total importance assigned to queries for x equals ∑_{i} k_{i}, and the cost incurred by our algorithm on instance x is at most twice the importance of errors made by the binary classifier on instance x. Averaging over the choice of x shows that the cost is at most 2.

This method of assigning importances is provably near-optimal.

Theorem 3. (Lower bound) For any other assignments of importances w_{i,j} to the points (x, i, j) in the above algorithm, there exists a distribution with expected cost ϵ/2.

Proof. Consider examples (x, 0, \frac{1}{r−1}, …, \frac{1}{r−1}). Suppose that we run our algorithm using some w_{i,j} as the importance for the query (x, i, j). Any classifier which errs on (x, 1, i) and (x, 1, j), where i ≠ j, causes our algorithm to choose label 2 as the winner, thereby giving a cost of 1/(r − 1), out of the total cost of 1. The importance of these two errors is w_{1,i} + w_{1,j}, out of the total importance of ∑_{i,j} w_{i,j}. Choosing i and j so that w_{1,i} + w_{1,j} is minimal, the adversary’s penalty is at most 2 ∑_{i=2}^{r} w_{1,i}/(r − 1), and hence less than 2/(r − 1) times the total importance for x. This shows that the cost of the reduction cannot be reduced below 1/2 merely by improving the choice of weights.

3.2 Experiments

We conducted experiments comparing the weighted all-pairs reduction to the original all-pairs reduction (?) (which ignores the costs and attempts to predict the label with minimal cost) and to a state-of-the-art multi-class cost-sensitive learning algorithm called MetaCost (?). We used Boosted Naive Bayes (?) as the oracle classifier learner and applied the methods to five UCI multiclass datasets. Since these datasets do not have costs associated with them, we generated artificial costs in the same manner that was done in the MetaCost paper (except that we fixed the cost of classifying correctly at zero). We repeated the experiments for 20 different settings of the costs. The average and standard error of the test set costs obtained with each method are shown in the table below. Note that we often observe order-of-magnitude improvements in performance.

We present results for two versions of this reduction. One is the exact version used in the proof above. In the other version, we learn one classifier per pair as is done in the original all-pairs reduction. More specifically, for each i and j (with i < j) we learn a classifier using the following mapping to generate training examples:

(x, k_{1}, …, k_{r}) ↦ (x, I(k_{i} < k_{j}), |v_{i} − v_{j}|).

In the results, we see that the first version appears to work well for some problems and badly for others, while the second version is more stable. Perhaps this is because the training examples given to the learner in the first version are not drawn i.i.d. from a fixed distribution as learning algorithms often expect.

Dataset  All-Pairs  MetaCost
splice  59.8 ± 24  49.8 ± 3.05
solar  3989 ± 1415 5317 ± 390
anneal  310 ± 205  207 ± 43
kdd-99  234 ± 62  49.4 ± 9.3
satellite  137 ± 33  104 ± 6.4
WAP v.1  WAP v.2
splice  197 ± 23  46.5 ± 3.5
solar  24.7 ± 2.0  36.8 ± 11
anneal  29.9 ± 3.0  164 ± 43
kdd-99 0.956 ± 0.12 1.76 ± 0.66
satellite  428 ± 21  148 ± 8.5

4 Error-Limiting Reductions

Informally, a reduction R from task T = (K, Y, l) to another task T′ = (K′, Y′, l′) is a procedure that uses oracle access to a learning algorithm for T′ to solve T , and guarantees that good performance of the oracle on subproblems generated by the reduction translates into good performance on the original problem.

To formalize this statement, we need to define a mapping from a measure D over prediction problems in (X × K)^{∗} to a measure D′ over generated subproblems in (X′ × K′)^{∗}.

In order to call the oracle, the reduction must take as input some training set S from (X × K)^{∗} and create some S′ from (X′ ×K′)^{∗}. We can think of this process as inducing a mapping from D to D′ according to

D′(S′) = E_{S∼D}Pr_{R}(S′),

where the probability of generating S′ is over the random bits used in the reduction on input S.

This rule defines D′ for a single invocation of the oracle. If the reduction makes several sequential calls, we need to define D′ for each invocation. Suppose that the first invocation produces h′. We replace this invocation with the oracle that always returns h′, and use the above definition to find D′ for the next invocation.

Now, suppose that we have a test example (x, k) drawn from some arbitrary distribution D over X × K. (We can think of D as being a distribution over (X × K)^{∗} having all probability mass on one-element sequences of examples.) The reduction maps this to a new measure D′ using the argument above.

We can now state the formal definition.

Definition 4. An error-limiting reduction R(S, A) from task (K, Y, ℓ) to task (K′, Y′, ℓ′) takes as input a finite set of examples S ∈ (X × K)^{∗} and a learning algorithm A for task (K′, Y′, ℓ′), and outputs a hypothesis h : X → Y that uses a collection of sub-hypotheses returned by A. For every such sub-hypothesis h′, and every measure D over X × K, the reduction induces a measure D′ over the inputs to h′, as described above. For all X × K and D, the reduction must satisfy

h_{D} ≤ g(max_{h′,D′} h′_{D′})

for some continuous monotone nondecreasing function g : [0, ∞) → [0, ∞) with g(0) = 0. We call g the errorlimitation function of the reduction.

For this definition, we use the convention that max_{∅} = 0, where max_{∅} is the maximum over the empty set. Note again that none of the above definitions require that examples be drawn i.i.d. Analysis in this model is therefore directly applicable to all real-world problems which satisfy the type constraint.

Notice that we do not stipulate that the training set and the test example (x, k) come from the same distribution. In fact, the definition is only dependent on the training distribution through the set of training examples S used to construct examples for the oracle.

Perspective It is useful to consider an analogy with Turing reductions in complexity theory. In both cases, a reduction from task A to task B is a procedure that solves A using a solver for B as a black box. There are several differences, the most important being that complexity-theoretic reductions are often viewed as negative statements providing evidence that a problem is intractable. Here we view reductions as positive statements allowing us to solve new problems.

It should be noted that not all reductions in the learning literature are black box. For example, Allwein et al. (?) give a reduction from multi-class to binary classification that uses a “margin,” which is a heuristic form of prediction confidence that can be extracted from many (but not all) classifiers. It is natural to wonder if there are inherent limitations in using learning algorithms as black boxes. Regardless of the answer, however, a black-box type of analysis is interesting for reasons listed in the introduction.

Metrics of success We consider several ways to measure reductions. The metric essential to the definition of an error limiting reduction is the error efficiency of the reduction for a given example, defined as the maximum ratio of the loss of the hypothesis output by the reduction on this example and the total loss of the oracle hypotheses on the examples generated by the reduction. We also want the transformation to be computationally efficient assuming that all oracle calls take unit time. We quantify how extensively a reduction uses its oracle based on (1) the number of oracle calls it makes; (2) whether the calls are adaptive (i.e., depend on the answers to previous queries) or parallel (i.e., all queries can be asked before any of them are answered). For example, the reduction in Section ?? takes O(r^{2}) time while using just a single oracle call.

Note that there is a general transformation turning parallel calls into a single call to the oracle learning algorithm. To make one call, we can augment the feature space with the name of the call and then learn a classifier on the union of all training data.

5 The Structure of Error Limiting Reductions

In this section we discuss some properties of error limiting reductions.

5.1 Easy Directions and Completeness

The learning tasks we consider have an easy direction for reduction related to whether a particular task is (trivially) expressible as another task. For example, solving binary classification with importance weighted binary classification is easy, because importance weighted binary classification with k_{2} = 1 is identical to binary classification. The figure below shows the easy direction for these reductions.

Note that all supervised learning tasks we consider can be embedded into cost-sensitive classification using the mapping K′ = ℓ(K, Y) for the task (K, Y, ℓ). Section ?? shows that cost-sensitive classification is reducible to binary classification. Thus binary classification is complete for the set of supervised learning tasks considered here in the sense that a learning machine with an oracle for binary classification learning can solve any supervised learning task.

5.2 Properties of Reductions

We show that the definition of error limiting reductions is non-trivial (in the sense defined below).

Non-triviality of the definition

The proposition below states that every reduction must make a non-trivial use of its oracle.

Proposition 5.1. For every error-limiting reduction R, every training set S, and test example (x, k), there exists an oracle A such that

E_{R}[h(x)] = arg min_{y∈Y} ℓ(k, y) = 0,

where h is the hypothesis output by R(S, A), and the expectation is over the randomization used by R in forming h.

Proof. Recall that the error limitation property holds for all D, in particular for the deterministic D with all probability mass on (x, k). Thus if R just ignored its oracle we would have ℓ(k, h(x)) = g(max_{∅}) = g(0) = 0. The fact that ℓ(k, y) is nonconstant (in both arguments) implies that there exists (x, k) such that any h must satisfy ℓ(k, h(x)) > 0, a contradiction. Consequently, at least one call to the oracle must be made.

Next note that for all R, S, and (x, k), there exists an h′ (and thus an oracle A outputting h′) consistent with all examples induced by R on (x, k). If R is randomized, there exists a deterministic reduction R′ taking one additional argument (a randomly chosen string) with the same output behavior as R. Consequently, there exists an oracle A dependent on this random string which achieves error rate 0. Since g(0) = 0, this must imply that h(x) = arg min_{y∈Y} ℓ(k, y) = 0.

Note, however, that while the notion of error limiting reductions is non-trivial, it does not prevent a reduction from creating hard problems for the oracle.

Composition Since our motivation for studying reductions is to reduce the number of distinct problems which must be considered, it is natural to want to compose two or more reductions to obtain new ones. It is easy to see that reductions defined above compose.

Proposition 5.2. If R_{12} is a reduction from task T_{1} to T_{2} with error limitation g_{12} and R_{23} is a reduction from task T_{2} to T_{3} with error limitation g_{23}, then the composition R_{12}∘R_{23} is a reduction from T_{1} to T_{3} with error limitation g_{12} ∘ g_{23}.

Proof. Given oracle access to any learning algorithm A for T_{3}, reduction R_{23} yields a learning algorithm for T_{2} such that for any X_{2} and D_{2}, it produces a hypothesis with loss rate h′_{D_{2}} ≤ g_{23}(h′′_{D_{3}}), where h′′_{D_{3}} is the maximum loss rate of a hypothesis h′′ output by A (over all invocations). We also know that R_{12} yields a learning algorithm for T_{1} such that for all X_{1} and D_{1} we have h_{D_{1}} ≤ g_{12}(h′_{D_{2}}) ≤ g_{12}(g_{23}(h′′_{D_{3}})), where h′_{D_{2}} is the maximum loss rate of a hypothesis h′ output by R_{23}(A). Finally, notice that g_{12} ∘ g_{23} is continuous, monotone nondecreasing, and g_{12}(g_{23}(0)) = 0.

6 Examples of Reductions

Here, we show that the notion of an error-limiting reduction is both tractable for analysis and describes several standard machine learning algorithms.

6.1 Reduction from Importance Weighted Classification to Classification

In importance weighted classification, every example comes with an extra “importance” value which measures how (relatively) important a decision might be. This extra flexibility turns out to be useful in several applications, and as an intermediate step in several reductions.

The “Costing” (?) algorithm is a (very simple) reduction from importance weighted classification to classification based on rejection sampling. Given an importance weighted dataset S = (x, k_{1}, k_{2}) an unweighted dataset is produced using rejection sampling:

{(x, k_{1}) : (x, k_{1}, k_{2}) ∈ S and k_{2} < t ∼ U(0, w)}

where t ∼ U(0, w) is a uniform random draw from the interval [0, w] and w is greater than k_{2} for all examples. The classifier learner is applied to produce a classifier c for this new dataset^{2}.

Although this algorithm is remarkably simple, composing costing with a decision tree has been shown to yield superior performance (again, see (?) for details) on championship prediction problems.

Theorem 4. (Costing error efficiency) For all importance weighted problems (D, X, T ), if the classifiers have error rate ϵ, costing has loss rate at most

ϵE_{(x,k_{1},k_{2})∼D}k_{2}.

Proof. Trivial. See (?).

6.2 Reductions from Multiclass Classification to Binary Classification

In this section we analyze several well known reductions for efficiency. Before we start, it is important to note that there are boosting algorithms for solving multiclass classification given weak binary importance weighted classification (see (?), (?)). Some of these methods require extra powerful classification algorithms, but others are genuine reductions, as defined here. A reductionist approach for creating a multiclass boosting algorithm is to simply compose any one of the following reductions with binary boosting.

2The actual costing algorithm repeats this process and predicts according to the majority on learned c.

The Tree Reduction In the tree reduction (which is well known, see chapter 15 of (?)), we construct r−1 binary classifiers distinguishing between the labels using a binary tree. The tree has depth log_{2} r, and each internal node is associated with a set of labels that can reach the node, assuming that each classifier above it predicts correctly. The set of labels at that node is split in half, and a classifier is trained to distinguish between the two sets of labels. The root node starts with the set of all labels {1, …, r} which are all indistinguishable at that point. Predictions are made by following a chain of classifications from the root down to the leaves, each of which is associated with a unique label. Note that instead of r−1 parallel, one could use log_{2} r adaptive queries. Theorem 5. (Tree error efficiency) For all multiclass problems (D, X, T ), if the binary classifiers have loss rate ϵ, the tree reduction has loss rate at most ϵ log_{2} r.

Proof. A multiclass error occurs only if some binary classifier on the path from the root to the leaf errs.

The Error Correcting Output Codes (ECOC) Reduction Let C ⊆ {0, 1}^{n} be an error-correcting code with l codewords a minimum distance of d apart. Let C_{i,j} denote the i’th bit of the j’th codeword of C. The ECOC reduction corresponding to C learns n classifiers: the i’th classifier predicts C_{i,y} where y is the correct label given input x. The loss rate for this reduction is at most 2nϵ/d, as we shall prove in Theorem ?? below.

We mention three codes of particular interest. The first is when the codewords form a subset of the rows of a Hadamard matrix (an n × n binary matrix with any two rows differing in exactly n/2 places). Such matrices exist and are easy to construct when n is a power of 2. Thus, for Hadamard codes, the number of classifiers needed is less than 2r (since a power of 2 exists between r and 2r), and the loss rate is at most 4ϵ. When the codewords correspond to binary representations of 0, 1, …, r − 1, the ECOC reduction is similar to (although not the same due to decoding differences) the tree reduction above. Finally, if the codewords form the r × r identity matrix, the ECOC reduction corresponds to the one-against-all reduction. Theorem 6. (ECOC ) For all multiclass problems (D, X, T ), if the binary classifiers have loss rate ϵ, the ECOC reduction has loss rate less than \frac{2n}{d}ϵ.

This theorem is identical to Lemma 2 of (?) (which was generalized in (?)), except that we generalize the statement to any distribution D generating (test) examples rather than the loss rate on a training set.

Proof. When the loss rate is zero, the correct label is consistent with all n classifiers, and wrong labels are consistent with at most n − d classifiers, since C has minimum distance d. In order to wrongly predict the multiclass label, at least d/2 binary classifiers must err simultaneously. Since every multiclass error implies at least a fraction d/2n of the binary classifiers erred, a binary loss rate of ϵ can yield at most a multiclass loss rate of 2nϵ/d.

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 are highly dependent.

We note that all reductions in this section preserve independence. Many common learning algorithms are built under the assumption that examples are drawn independently from some distribution, and it is a desirable property for reductions to preserve this independence when constructing datasets for the oracle.

7 Prior Work

There has been much work on reductions in learning. One of our goals is to give a unifying framework, allowing a better understanding of strengths and weaknesses in forms of reductions.

Boosting algorithms (?; ?) can be thought of as reductions from binary (or sometimes multiclass) classification with a small error rate to importance weighted classification with a loss rate of nearly \frac{1}{2}. Given this, it is important to ask: “Can’t a learning machine apply boosting to solve any classification problem perfectly?” The answer is “No” since it is impossible to always predict correctly whenever the correct prediction given features is not deterministic (i.e., is probabilistic). What this implies for a learning machine is that the loss rate becomes unbounded from \frac{1}{2} after some number of rounds of boosting.

Bagging (?) can be seen as a self-reduction of classification to classification, which turns learning algorithms with high “variance” (i.e., dependence on the exact examples seen) into a classifier with lower “variance”. Bagging performance sometimes suffers because the examples fed into the classifier learning algorithm are not necessarily independently distributed according to the original distribution.

The ECOC reduction (?) generalizes the tree reduction (?) and the one-against-all reduction (?) from multiclass to binary classification. The “Costing” algorithm (?) is a reduction of importance weighted classification to classification. The “Probing” algorithm (?) is a reduction of class probability estimation to binary classification.

Pitt and Warmuth (?) also introduced a form of a reduction between classification problems called prediction-preserving reducibility. There are several important differences between this notion and the notion presented here: (1) prediction-preserving reductions are typically used to show negative, nonpredictability results, while we show positive results transferring learning algorithms between tasks; (2) reductions presented here are representation independent; (3) prediction-preserving reducibility is a computational notion, while the reductions here are informational. Reductions presented here are also more general in the sense that they are between arbitrary learning tasks rather than between restricted sets of classification problems.

8 Conclusion

We introduced the analysis model of error-limiting reductions in learning. This model has several nice properties (often not shared with other methods of learning analysis). First, the analysis in this model does not depend upon any unprovable (or unobservable) assumptions such as independence. Error-limiting reductions often have tractable analysis and capture several common machine learning algorithms. They also often work well in practice.

To test the model, we constructed, proved, and empirically tested an error-limiting reduction from multiclass cost-sensitive classification to binary classification. Since cost sensitive classification can express any supervised learning task considered here, this reduction can be used to reduce any such task to binary classification.

References

Allwein, E., Schapire, R., & Singer, Y. (2001). Reducing multiclass to binary: A unifying approach for margin classifiers. J. of Machine Learning Research, 1, 113–141. Breiman, L. (1996). Bagging predictors. Machine Learning, 26, 123–140. Dietterich, T. G., & Bakiri, G. (1995). Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2, 263–286. Domingos, P. (1999). Metacost: A general method for making classifiers cost-sensitive. Proceedings of the 5th KDD Conference (pp. 155–164). Elkan, C. (1997). Boosting and naive bayesian learning (Technical Report CS97-557). UC San Diego. Fox, J. (1997). Applied regression analysis, linear models, and related methods. Sage Publications. Freund, Y., & Schapire, R. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. J. of Comp. and Sys. Sci., 55, 119–139.

Guruswami, V., & Sahai, A. (1999). Multiclass learning, boosting, and error-correcting codes. Proceedings of the 12th Annual Conference on Computational Learning Theory (COLT) (pp. 145–155). Hastie, T., & Tibshirani, R. (1997). Classification by pairwise coupling. Advances in Neural Information Processing Systems 10 (NIPS) (pp. 507–513). Haussler, D. (1992). Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and Computation, 100, 78–150. Kalai, A., & Servedio, R. (2003). Boosting in the presence of noise. Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC) (pp. 195–205). Langford, J., & Zadrozny, B. (2005). Estimating class membership probabilities using classifier learners. Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics. Pitt, L., & Warmuth, M. (1990). Prediction-preserving reducibility. J. of Comp. and Sys. Sci., 41, 430–467. Rifkin, R., & Klautau, A. (2004). In defense of one-vs-all classification. Journal of Machine Learning Research, 5, 101–141. Schapire, R. (1997). Using output codes to boost multiclass learning problems. Proceedings of the 14th International Conference on Machine Learning (ICML) (pp. 313–321). Schapire, R., & Singer, Y. (1999). Improved boosting using confidence-rated predictions. Machine Learning, 37, 297–336. Valiant, L. (1984). A theory of the learnable. Communications of the ACM, 27, 1134–1142. Vapnik, V. N., & Chevonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of probability and its applications, 16, 264–280. Zadrozny, B., Langford, J., & Abe, N. (2003). Cost sensitive learning by cost-proportionate example weighting. Proceedings of the 3rd ICDM Conference.