On the Learnability and Design of Output Codes for Multiclass Problems.
Output coding is a general framework for solving multiclass categorization problems. Previous research on output codes has focused on building multiclass machines given predefined output codes. In this paper we discuss for the first time the problem of designing output codes for multiclass problems. For the design problem of discrete codes, which have been used extensively in previous works, we present mostly negative results. We then introduce the notion of continuous codes and cast the design problem of continuous codes as a constrained optimization problem. We describe three optimization problems corresponding to three different norms of the code matrix. Interestingly, for the l2 norm our formalism results in a quadratic program whose dual does not depend on the length of the code. A special case of our formalism provides a multiclass scheme for building support vector machines which can be solved efficiently. We give a time and space efficient algorithm for solving the quadratic program. We describe preliminary experiments with synthetic data show that our algorithm is often two orders of magnitude faster than standard quadratic programming packages. We conclude with the generalization properties of the algorithm.
Introduction
Many applied machine learning problems require assigning
labels to instances where the labels are drawn from a finite
set of labels. This problem is often referred to as multiclass
categorization or classification. Examples for machine learning
applications that include a multiclass categorization component
include optical character recognition, text classifica-
tion, phoneme classification for speech synthesis, medical
analysis, and more. Some of the well known binary classification
learning algorithms can be extended to handle multiclass
problem (see for instance [5, 19, 20]). A general approach
is to reduce a multiclass problem to a multiple binary
classification problem.
Dietterich and Bakiri [9] described a general approach
based on error-correcting codes which they termed error-correcting
output coding (ECOC), or in short output cod-
ing. Output coding for multiclass problems is composed
of two stages. In the training stage we need to construct
multiple (supposedly) independent binary classifiers each of
which is based on a different partition of the set of the labels
into two disjoint sets. In the second stage, the classification
part, the predictions of the binary classifiers are combined to
extend a prediction on the original label of a test instance.
Experimental work has shown that output coding can often
greatly improve over standard reductions to binary problems
[9, 10, 16, 1, 21, 8, 4, 2]. The performance of output coding
was also analyzed in statistics and learning theoretic contexts
[12, 15, 22, 2].
Most of the previous work on output coding has concentrated
on the problem of solving multiclass problems using
predefined output codes, independently of the specific application
and the class of hypotheses used to construct the
binary classifiers. Therefore, by predefining the output code
we ignore the complexity of the induced binary problems.
The output codes used in experiments were typically confined
to a specific family of codes. Several family of codes
have been suggested and tested so far, such as, comparing
each class against the rest, comparing all pairs of classes [12,
2], random codes [9, 21, 2], exhaustive codes [9, 2], and linear
error correcting codes [9]. A few heuristics attempting to
modify the code so as to improve the multiclass prediction
accuracy were suggested (e.g., [1]). However, they did not
yield significant improvements and, furthermore, they lack
any formal justification.
In this paper we concentrate on the problem of designing
a good code for a given multiclass problem. In Sec. 3 we
study the problem of finding the first column of a discrete
code matrix. Given a binary classifier, we show that finding
a good first column can be done in polynomial time. In con-
trast, when we restrict the hypotheses class from which we
choose the binary classifiers, the problem of finding a good
first column becomes difficult. This result underscores the
difficulty of the code design problem. Furthermore, in Sec. 4
we discuss the general design problem and show that given
a set of binary classifiers the problem of finding a good code
matrix is NP-complete.
Motivated by the intractability results we introduce in
Sec. 5 the notion of continuous codes and cast the design
problem of continuous codes as a constrained optimization
problem. As in discrete codes, each column of the code matrix
divides the set of labels into two subsets which are labeled
positive (+) and negative ( ). The sign of each entry
in the code matrix determines the subset association (+ or
) and the magnitude corresponds to the confidence in this
association. Given this formalism, we seek an output code
with small empirical loss whose matrix norm is small. We
describe three optimization problems corresponding to three
different norms of the code matrix: l 1 ; l 2 and l 1 . For l 1 and
l 1 we show that the code design problem can be solved by
linear programming (LP). Interestingly, for the l 2 norm our
formalism results in a quadratic program (QP) whose dual
does not depend on the length of the code. Similar to support
vector machines, the dual program can be expressed in
terms of inner-products between input instances, hence we
can employ kernel-based binary classifiers. Our framework
yields, as a special case, a direct and efficient method for
constructing multiclass support vector machine.
The number of variables in the dual quadratic problem
is the product of the number of samples by the number of
classes. This value becomes very large even for small datasets.
For instance, an English letter recognition problem with 1;000
training examples would require 26;000 variables. In this
case, the standard matrix representation of dual quadratic
problem would require more than 5 Giga bytes of mem-
ory. We therefore describe in Sec. 6.1 a memory efficient
algorithm for solving the quadratic program for code design.
Our algorithm is reminiscent of Platt's sequential minimal
optimization (SMO) [17]. However, unlike SMO, our algorithm
optimize on each round a reduced subset of the variables
that corresponds to a single example. Informally, our
algorithm reduces the optimization problem to a sequence
of small problems, where the size of each reduced problem
is equal to the number of classes of the original multiclass
problem. Each reduced problem can again be solved using
a standard QP technique. However, standard approaches
would still require large amount of memory when the number
of classes is large and a straightforward solution is also
time consuming. We therefore further develop the algorithm
and provide an analytic solution for the reduced problems
and an efficient algorithm for calculating the solution. The
run time of the algorithm is polynomial and the memory requirements
are linear in the number of classes. We conclude
with simulations results showing that our algorithm is at least
two orders of magnitude faster than a standard QP technique,
even for small number of classes.
be a set of m training
examples where each instance x i belongs to a domain X .
We assume without loss of generality that each label y i is
an integer from the set kg. A multiclass classifier
is a function that maps an instance x
into an element y of Y . In this work we focus on a frame-work
that uses output codes to build multiclass classifiers
from binary classifiers. A discrete output code M is a matrix
of size k  l over f1;+1g where each row of M correspond
to a class y 2 Y . Each column of M defines a partition
of Y into two disjoint sets. Binary learning algorithms
are used to construct classifiers, one for each column t of
M . That is, the set of examples induced by column t of M
is This set is fed as training
data to a learning algorithm that finds a hypothesis h
f1;+1g. This reduction yields l different binary classifiers
l . We denote the vector of predictions of these classifiers
on an instance x as
denote the rth row of M by
M r .
Given an example x we predict the label y for which the
row
M y is the "closest" to  h(x). We will use a general notion
for closeness and define it through an inner-product function
l  R
R. The higher the value of K(  h(x);
is the more confident we are that r is the correct label of x
according to the classifiers  h. An example for a closeness
function is K(u;
v. It is easy to verify that this
choice of K is equivalent to picking the row of M which
attains the minimal Hamming distance to  h(x).
Given a classifier H(x) and an example (x; y), we say
that H(x) misclassified the example if H(x) 6= y. Let
1 if the predicate  holds and 0 otherwise. Our goal is therefore
to find a classifier H(x) such that 1
small. We would like to note in passing that in this
paper we mainly focus on the empirical loss minimization
problem. As in more standard classification problems, the
loss on a separate test set (generalization error) can also be
theoretically bounded given appropriate assumptions using
uniform-convergence theory [3, 13, 23]. We leave this for
future research.
When l is small there might be more then one row of
which attains the maximal value according to the function
K. To accommodate such cases we will relax our definition
and define a classifier H(X) based on a code M
to be the mapping
fy j K(  h(x);
r )g. In this case we
will pick one of the labels in H(x) uniformly at random, and
use the expected error of H(x),
=m
(1)
In the context of output codes, a multiclass mapping H(x)
is thus determined by two parameters: the coding matrix M
and the set of binary classifiers
h(x). Assume that the binary
classifiers are chosen from some hypothesis
class H. The following natural learning problems arise: (a)
Given a matrix M , find a set  h which suffers small empirical
loss. (b) Given a set of binary classifiers  h, find a matrix M
which has small empirical loss. (c) Find both a matrix M
and a set  h which have small empirical loss.
Previous work has focused mostly on the first problem.
In this paper we mainly concentrate on the code design problem
(problem b), that is, finding a good matrix M . A summary
of the notation is given in Appendix A.
3 Finding the first column of an output code
Assume we are given a single binary classifier h 1 (x) and we
want to find the first (or the single) column of the matrix M
which minimizes the empirical loss  S (M;  h). For brevity,
let us denote by
the first column of M . We
now describe an efficient algorithm that finds
The algorithm's running time is polynomial in the size of the
label set and the sample size m. First, note that in
this case
Second, note that the sample can be divided into 2k equivalence
classes according to their labels and the classification
of h 1 (x). For
a b
to be the fraction of
the examples with label r and classification b (according to
denote by a
r=1 a b
r , and let
bgj be the number of elements in  u which
are equal to b. (For brevity, we will often use + and to
denote the value of b.) Let
We can assume without loss of generality that not all the elements
in  u are the same (otherwise,  S (M;
k , which is
equivalent to random guessing). Hence, the size of H(x) is :
Using Eqs. (2) and (4), we rewrite Eq. (3),
=m
=m
r
a r
Using Eq. (5) we now can expand  S (M;
h),
ur
a
r
ur
a r
ur
a
r
a r
a
r
a r
ur
a
r
a r
a
a
For a particular choice of w
maximized (and  S is minimized) by setting u at the
which attain the highest values for
r
a r
and set the rest w of the indices to 1. This can be done
efficiently in k log k time using sorting. Therefore, the best
choice of
u is found by enumerating all the possible values
choosing the value of w
which achieves the maximal value for Eq. (6). Since it takes
m operations to calculate a
r and a r , the total number of operations
needed to find the optimal choice for the first column
is O(m log k). We have proven the following theorem.
Theorem 1 Let be a set of
training examples, where each label is an integer from the
set kg. Let H be a binary hypothesis class. Given
an hypothesis h 1 (x) 2 H, the first column of an output code
which minimizes the empirical loss defined by Eq. (1) can be
found in polynomial time.
To conclude this section we use a reduction from SAT
to demonstrate that if the learning algorithm (and its corresponding
class of hypotheses from which h 1 can chosen
from) is of a very restricted form then the resulting learning
problem can be hard. Let
formula over the variables x i 2 f1;+1g where we interpret
to be the instance space. Let
1)g be a sample
of size the labels are taken from
1g. Define the learning algorithm L
as follows. The algorithm's input is a binary labeled sample
of the form f(x
. If
then the algorithm returns an hypothesis which is consistent
with the sample (the sample itself). Otherwise, the algorithm
returns the constant hypothesis, h(x)  1 or h(x)  0,
which agrees with the majority of the sample by choosing
Note that the
learning algorithm is non-trivial in the sense that the hypothesis
it returns has an empirical loss of less than 1=2 on the
binary labeled sample.
We now show that a multiclass learning algorithm that
minimizes the empirical loss  S over both the first column
u and the hypothesis h 1 (x) which was returned by the algorithm
L , can be used to check whether the formula is sat-
isfiable. We need to consider two cases. When
True and for all i y i y using the definition
from Eq. (3) we get
=m . If the above conditions do not hold (h(x) is constant), let
be the number of examples which the hypothesis
classifies correctly. Then, using Eq. (3) again we
obtain
. Thus, the minimum of  S is
achieved if and only if the formula is satisfiable. There-
fore, a learning algorithm for h 1 (x) and
can also be used
as an oracle for the satisfiability of .
While the setting discussed in this section is somewhat
superficial, these results underscore the difficulty of the prob-
lem. We next show that the problem of finding a good output
code given a relatively large set of classifiers  h(x) is in-
tractable. We would like to note in passing that efficient algorithm
for finding a single column might be useful in other
settings. For instance in building trees or directed acyclic
graphs for multiclass problems (cf. [18]). We leave this for
future research.
4 Finding a general discrete output code
In this section we prove that given a set of l binary classifiers
h(x), finding a code matrix which minimizes the empirical
loss  S (M;
is NP-complete. Given a sample
and a set of classifiers  h, let us denote
by ~
the evaluation of  h()
on the sample S, where  h i
is the predictions vector
for the ith sample. We now show that even when
the problem is NP-complete. (Clearly, the
problem remains NPC for k > 2). Following the notation of
previous sections, the output code matrix is composed of two
rows
2 and the predicted class for instance x i is
g. For the simplicity of the
presentation of the proof, we assume that both the code M
and the hypotheses' values  h i are over the set f0; 1g (instead
of f1;+1g). This assumption does not change the problem
since there is a linear transform between the two sets.
Theorem 2 The following decision problem is NP-complete.
Input: A natural number q, a labeled sample
~
Question: Does there exist a matrix M 2 f0; 1g 2l such
that the classifier H(x) based on an output code M makes
at most q mistakes on ~
S.
Proof: Our proof is based on a reduction technique introduced
by H-offgen and Simon [14]. Since we can check in
polynomial time whether the number of classification errors
for a given a code matrix M exceeds the bound q, the problem
is clearly in NP.
We show a reduction to Vertex Cover in order to prove
that the problem is NP-hard. Given an undirected graph
(V; E), we will code the structure of the graph as follows.
The sample ~
S will be composed of two subsets, ~
of size 2jEj and jV j respectively. We set Each
edge encoded by two examples (  h; y) in ~
We set for the first vector to h
elsewhere. We set the second vector to h
elsewhere. We set the label y of each example
in ~
to 1. Each example
encodes a node v i 2
set the label y of each example in ~
S V to 2 (second class).
We now show that there exists a vertex cover U  V with
at most q nodes if and only if there exists a coding matrix
that induces at most q classification errors on
the sample ~
S.
be a vertex cover such that jU j  q.
We show that there exists a code which has at most q mistakes
on ~
S. Let u 2 f0; 1g jV j be the characteristic function
of U , that is, u
Define the output code matrix to be
denotes the component-wise
logical not operator.
Since U is a cover, for each  h 2 ~
Therefore, for all the examples in ~
predicted label
equals the true label and we suffer 0 errors on these exam-
ples. For each example  h 2 ~
that corresponds to a node
Therefore, these examples are misclassified (Recall that the
label of each example in ~
S V is 2). Analogously, for each
example in ~
which corresponds to v 62 U we get
and these examples are correctly classified. We thus have
shown that the total number of mistakes according to M is
be a code which achieves at most q mistakes
on ~
S. We construct a subset U  V as follows. We
scan ~
S and add to U all vertices v i corresponding to misclassified
examples from ~
. Similarly, for each misclassified
example from ~
corresponding to an edge fv
either v i or v j at random and add it to U . Since we have at
most q misclassified examples in ~
S the size of U is at most
q. We claim that the set U is a vertex cover of the graph G.
Assume by contradiction that there is an edge fv for
which neither v i nor v j belong to the set U . Therefore, by
construction, the examples corresponding to the vertices v i
and v j are classified correctly and we get,
Summing the above equations yields that,
In addition, the two examples corresponding to the edge
are classified correctly, implying that
which again by summing the above equations yields,
Comparing Eqs. (7) and (8) we get a contradiction.
5 Continuous codes
The intractability results of previous sections motivate a relaxation
of output codes. In this section we describe a natural
relaxation where both the classifiers' output and the code
matrix are over the reals.
As before, the classifier H(x) is constructed from a code
matrix M and a set of binary classifiers  h(x). The matrix M
is of size k  l over R where each row of M corresponds to a
class y 2 Y . Analogously, each binary classifier h t (x) 2 H
is a mapping h t of M defines
a partition of Y into two disjoint sets. The sign of each element
of the tth column is interpreted as the set (+1 or -1)
to which the class r belongs and the magnitude jM r;t j is interpreted
as the confidence in the associated partition. Sim-
ilarly, we interpret the sign of h t (x) as the prediction of the
set (+1 or -1) to which the label of the instance x belongs and
the magnitude jh t (x)j as the confidence of this prediction.
Given an instance x, the classifier H(x) predicts the label
y which maximizes the confidence function K(
)g. Since the code is
over the reals, we can assume here without loss of generality
that exactly one class attains the maximum value according
to the function K. We will concentrate on the problem of
finding a good continuous code given a set of binary classifiers
h.
The approach we will take is to cast the code design problem
as constrained optimization problem. Borrowing the
idea of soft margin [7] we replace the discrete 0-1 multiclass
loss with the linear bound
r
This formulation is also motivated by the generalization analysis
of Schapire et al. [2]. The analysis they give is based on
the margin of examples where the margin is closely related
to the definition of the loss as given by Eq. (9).
Put another way, the correct label should have a confidence
value which is larger by at least one than any of the
confidences for the rest of the labels. Otherwise, we suffer
loss which is linearly proportional to the difference between
the confidence of the correct label and the maximum among
the confidences of the other labels. The bound on the empirical
loss is
We say that a
sample S is classified correctly using a set of binary classifier

h if there exists a matrix M such that the above loss is
equal to zero,
Denote by
Thus, a matrix M that satisfies Eq. (10) would also satisfy
the following constraints,
We view a code M as a collection of vectors and define
the norm of M to be the norm of the concatenation of the
vectors constituting M . Motivated by [24, 2] we seek a matrix
M with a small norm which satisfies Eq. (12). Thus,
when the entire sample S can be labeled correctly, the problem
of finding a good matrix M can be stated as the following
optimization problem,
subject to : 8i; r K(  h(x i );
Here p is an integer. Note that m of the constraints for
are automatically satisfied. This is changed in the following
derivation for the non-separable case. In the general case a
matrix M which classifies all the examples correctly might
not exist. We therefore introduce slack variables  i  0 and
modify Eq. (10) to be,
r
The corresponding optimization problem is,
subject to :
for some constant   0. This is an optimization problem
with "soft" constraints. Analogously, we can define an optimization
problem with "hard" constraints,
subject to :
The relation between the "hard" and "soft" constraints and
their formal properties is beyond the scope of this paper.
For further discussion on the relation between the problems
see [24].
5.1 Design of continuous codes using Linear
Programming
We now further develop Eq. (14) for the cases
We deal first with the cases which result in
linear programs. For the simplicity of presentation we will
assume that K(u;
For the case objective function of Eq. (14) become

i;r jM i;r j+
We introduce a set of auxiliary
variables  to get a standard linear programming
setting,
subject to
To obtain its dual program (see also App. B) we define one
variable for each constraint of the primal problem. We use
i;r for the first set of constraints, and
t;r for the second set.
The dual program is,
i;r
subject to : 8i;
r
t;r
The case of similar. The objective function of
Eq.
We introduce a
single new variable to obtain the primal
problem,
subject to
Following the technique for we get that the dual program
is,
i;r
subject to : 8i;
r
t;r
t;r
Both programs can be now solved using
standard linear program packages.
5.2 Design of continuous codes using Quadric
Programming
We now discuss in detail Eq. (14) for the case 2. For
convenience we use the square of the norm of the matrix
(instead the norm itself). Therefore, the primal program becomes

subject to
We solve the optimization problem by finding a saddle point
of the Lagrangian :
r
i;r  i;r
subject to :8i; r  i;r  0 (16)
The saddle point we are seeking is a minimum for the primal
variables (M; ), and the maximum for the dual ones (). To
find the minimum over the primal variables we require,
@
r
r
Similarly, for
M r we require,
@
@
i;r0
| {z }
Eq. (19) implies that when the optimum of the objective
function is achieved, each row of the matrix M is a linear
combination of  h(x i ). We say that an example i is a support
pattern for class r if the coefficient (- y i ;r  i;r ) of  h(x i )
in Eq. (19) is not zero. There are two settings for which an
example i can be a support pattern for class r. The first case
is when the label y i of an example is equal to r, then the ith
example is a support pattern if  i;r < 1. The second case is
when the label y i of the example is different from r, then the
ith pattern is a support pattern if  i;r > 0.
Loosely speaking, since for all i and r we have  i;r  0
and
r  the variable  i;r can be viewed as a distribution
over the labels for each example. An example i affects
the solution for M (Eq. (19)) if and only if   i in not a point
distribution concentrating on the correct label y i . Thus, only
the questionable patterns contribute to the learning process.
We develop the Lagrangian using only the dual variables.
Substituting Eqs. (17) and (19) into Eq. (16) and using various
algebraic manipulations, we obtain that the target function
of the dual program is,
r
i;r
(Details are omitted due to the lack of space.) Let  1 i be the
vector with all components zero, except for the ith component
which is equal to one, and let  1 be the vector whose
components are all one. Using this notation we can rewrite
the dual program in vector form as
subject to : 8r
where
It is easy to verify that Q() is strictly convex in . Since
the constraints are linear the above problem has a single optimal
solution and therefore QP methods can be used to solve
it. In Sec. 6 we describe a memory efficient algorithm for
solving this special QP problem.
To simplify the equations we denote by
the difference between the correct point distribution and the
distribution obtained by the optimization problem, Eq. (19)
becomes,
Since we look for the value of the variables which maximize
the objective function Q (and not the optimum of Q itself),
we can omit constants and write the dual problem given by
Eq. (20) as,
subject to : 8r   i   1 y i and   i
where
Finally, the classifier H(x) can be written in terms of the
variable  as,
r
h(x)

h(x)
#)
r
i;r
r
i;r
h(x)
As in Support Vector Machines, the dual program and
the classification algorithm depend only on inner products
of the form  h(x i )   h(x). Therefore, we can perform the
calculations in some high dimensional inner-product space
Z using a transformation
l ! Z . We thus replace
the inner-product in Eq. (22) and in Eq. (23) with a general
inner-product kernel K that satisfies Mercer conditions [24].
The general dual program is therefore,
subject to : 8i
and
and the classification rule H(x) becomes,
i;r K
The general framework for designing output codes using
the QP program described above, also provides, as a special
case, a new algorithm for building multiclass Support Vectors
Machines. Assume that the instance space is the vector
space R
n and define  h(x)
x (thus l = n), then the primal
program in Eq. (15) becomes
min
subject to
Note that for reduces to the primal program
of SVM, if we take
We
would also like to note that this special case is reminiscent
of the multiclass approach for SVM's suggested by Weston
and Watkins [25]. Their approach compared the confidence
y ) to the confidences of all other labels K(x;
and had m(k 1) slack variables in the primal problem. In
contrast, in our framework the confidence K(x;
y ) is compared
to max r 6=y K(x;
r ) and has only m slack variables
in the primal program.
In

Table

1 we summarize the properties of the programs
discussed above. As shown in the table, the advantage of
using l 2 in the objective function is that the number of variables
in the dual problem in only a function of on k and m
and does not depend on the number columns l in M . The
number of columns in M only affects the evaluation of the
inner-product kernel K.
The formalism given by Eq. (14) can also be used to construct
the code matrix incrementally (column by column).
We now outline the incremental (inductive) approach. How-
ever, we would like to note that this method only applies
when K(v;
u. In the first step of the incremental al-
gorithm, we are given a single binary classifier h 1 (x) and we
need to construct the first column of M . We rewrite Eq. (14)
in a scalar form and obtain,
subject to : 8i; r h 1
Here,   0 is a given constant and b
fore. For the rest of the columns we assume inductively that
have been provided and the first l columns
of the matrix M have been found. In addition, we are provided
with a new binary classifier h l+1 (x) for the
next column. We need to find a new column of M (indexed
l 1). We substitute the new classifier and the matrix in
Eq. (13) and get,
r
The constraints appearing in Eq. (14) now become
r
r
We now redefine b i;r to be [  h(x i )
. It is straightforward to verify that this definition of
b i;r results in an equation of the same form of Eq. (27). We
can thus apply the same algorithms designed for the "batch"
case. In the case of l 1 and l 1 , this construction decomposes
a single problem into l sub-problems with fewer variables
and constraints. However, for l 2 the size of the program remains
the same while we lose the ability to use kernels. We
therefore concentrate on the batch case for which we need to
find the entire matrix at once.
6 An efficient algorithm for the QP problem
The quadratic program presented in Eq. (24) can be solved
using standard QP techniques. As shown in Table 1 the dual
program depends on mk variables and has km
all together. Converting the dual program in Eq. (24)
to a standard QP form requires storing and manipulating a
matrix with (mk) 2 elements. Clearly, this would prohibit
applications of non-trivial size. We now introduce a memory
efficient algorithm for solving the quadratic optimization
problem given by Eq. (24).
Primal Variables m+ 2kl m+ kl m+ kl
0-Constraints
Constraints
Dual Variables km
0-Constraints
Constraints

Table

1: Summary of the sizes of the optimization problems
for different norms. (See Appendix B for the definitions of
the constraints in linear programming.)
First, note that the constraints in Eq. (24) can be divided
. The algorithm
we describe works in rounds. On each round it picks a
single set f i   1 y
modifies
so as to optimize
the reduced optimization problem. The algorithm is
reminiscent of Platt's SMO algorithm [17]. Note, however,
that our algorithm optimizes one example on each round, and
not two as in SMO.
Let us fix an example index p and write the objective
function only in terms of the variables
p . For brevity, let
. We isolate
p in Q.
where,
For brevity, we will omit the index p and drop constants
(that do not affect the solution). The reduced optimization
has k variables and k
subject to :
1 y and
Although this program can be solved using a standard QP
technique, it still requires large amount of memory when
k is large, and a straightforward solution is also time con-
suming. Furthermore, this problem constitutes the core and
inner-loop of the algorithm. We therefore further develop the
algorithm and describe a more efficient method for solving
Eq. (32). We write Q( ) in Eq. (32) using a completion to
quadratic form,
A
A
Since A > 0 the program from Eq. (32) becomes,
min
subject to :
D and
where,
A
A
In Sec. 6.1 we discuss an analytic solution to Eq. (33) and in
Sec. 6.2 we describe a time efficient algorithm for computing
the analytic solution.
6.1 An analytic solution
While the algorithmic solution we describe in this section
is simple to implement and efficient, its derivation is quite
complex. Before describing the analytic solution to Eq. (33),
we would like to give some intuition on our method. Let us
fix some vector
D and denote
1. First note that
D is not a feasible point since the constraint
D   1 1 is not satisfied. Hence for any feasible point some
of the constraints
D are not tight. Second, note that
the differences between the bounds D r and the variables  r
sum to one. Let us induce a uniform distribution over the
components of  . Then, the variance of   is
Since the expectation  is constrained to a given value, the
optimal solution is the vector achieving the smallest vari-
ance. That is, the components of of
should attain similar
values, as much as possible, under the inequality constraints
D. In Fig. 1 we illustrate this motivation. We picked
show plots for two different
feasible values for
. The x-axis is the index r of the point
and the y-axis designates the values of the components of
. The norm of   on the plot on the right hand side plot is
smaller than the norm of the plot on the left hand side. The
right hand side plot is the optimal solution for  . The sum
of the lengths of the arrows in both plots is
Since both sets of points are feasible, they satisfy the constraint
D   1 1. Thus, the sum of the lengths of the
"arrows" in both plots is one. We exploit this observation in
the algorithm we describe in the sequel.
We therefore seek a feasible vector
whose most of its
components are equal to some threshold . Given  we define
a vector
whose its rth component equal to the minimum
between  and D r , hence the inequality constraints are
satisfied. We define
D r

Figure

1: An illustration of two feasible points for the reduced
optimization problem with
The x-axis is the index of the point, and the y-axis denotes
the values
. The bottom plot has a smaller variance hence it
achieves a better value for Q.
We denote by
Using F , the equality constraint from Eq. (33) becomes
Let us assume without loss of generality that the components
of the vector   are given in a descending order, D 1
(this can be done in k log k time). Let D
1 and D To prove the main theorem of this section
we need the following lemma.
Lemma 3 F () is piecewise linear with a slope r in each
range (D r+1 ; D r ) for
Proof: Let us develop F ().
D r
F

Figure

2: An illustration of the solution of the QP problem
using the inverse of F () for
0:6). The
optimal value is the solution for the equation F
which is 0:5.
Note that if  > D r then  > D u for all u  r. Also, the
equality
holds for each  in the range
. Thus, for D r+1 <  < D r
the function F () has the form,
This completes the proof.
Corollary 4 There exists a unique  0  D 1 such that
Proof: From Eq. (35) we conclude that F () is strictly
increasing and continuous in the range   D 1 . Therefore,
F () has an inverse in that range, using the theorem that
every strictly increasing and continuous function has an in-
verse. Since F
1. Hence, the range of F for the interval (1;D 1
is the interval (1;
D   1] which clearly contains
Thus  0
needed. Uniqueness
of  0 follows the fact that the function F is a one-to-one
mapping onto (1;
We now can prove the main theorem of this section.
Theorem 5 Let  0 be the unique solution of F
Then   0 is the optimum value of the optimization problem
stated in Eq. (33).
The theorem tells us that the optimum value of Eq. (33) is
of the form defined by Eq. (34) and that there is exactly one
value of  for which the equality constraint F
holds. A plot of F () and the solution for  from
Fig. 1 are shown in Fig. 2.
Proof: Corollary 4 implies that a solution exists and is
unique. Note also that from definition of  0 we have that
the vector   0 is a feasible point of Eq. (33). We now
prove that
0 is the optimum of Eq. (33) by showing that
6=    .
Assume, by contradiction, that there is a vector
such
that kk 2  k 0 k 2 . Let
6=  0, and define
I
g. Since both   and
0 satisfy the equality constraint of Eq. (33), we have,
Since
is a feasible point we have
D. Also,
by the definition of the set I we have that
I . Combining the two properties we get,
r  0 for all r 2 I (37)
We start with the simpler case of  I . In
this case,   differs from
0 only on a subset of the coordinates
I . However, for these coordinates the components
of   0 are equal to  0 , thus we obtain a zero variance from
the constant vector whose components are all  0 . Therefore,
no other feasible vector can achieve a better variance. For-
mally, since  I , then the terms for r 2 I
cancel each other,
r=2I
r=2I
From the definition of
0 in Eq. (34) we get that  0
for all
I ,
r=2I
r=2I
r=2I
r=2I
We use now the assumption that  I and the
equality
to obtain,
and we get a contradiction since   6=
We now turn to prove the complementary case in which
r2I  r < 0, then there exists u 2 I
such that  u < 0. We use again Eq. (36) and conclude that
there exists also
2 I such that  v > 0. Let us assume
without loss of generality that  u
analogously by switching the roles of u and
v). Define   0 as follows,
r otherwise
The vector   0 satisfies the constraints of Eq. (33) since  0
and   0 are equal except for
their u and v components we get,
D.
Initialize
D.
Sort the components of
D, such that D i 1  D
While
Compute
r . Eq. (40)
For
Return  .

Figure

3: The algorithm for finding the optimal solution of
the reduced quadratic program (Eq. (33)).
Substituting the values for  0 u and  0 v from the definition of
0 we obtain,
Using the definition of
and   0 for
u and for
The first term of the bottom equation is negative since  u < 0
and  v > 0. Also u 2 I , hence  0 > D u and the second term
is also negative. We thus get,
which is a contradiction.
6.2 An efficient algorithm for computing the analytic
solution
The optimization problem of Eq. (33) can be solved using
standard QP methods, and interior point methods in particular
[11]. For these methods the computation time is
In this section we give an algorithm for solving that optimization
problem in O(k log time, by solving the equation
As before, we assume that the components of the vector
are given in a descending order, D 1  D
we denote D 1. The algorithm searches for the
interval [D r+1 ; D r ) which contains  0 . We now use simple
algebraic manipulations to derive the search scheme for  0 .
For convenience, we define the potential function
and obtain,
Choose f i g - a feasible point for Eq. (24).
Iterate.
Choose an example p
Eqs. (29) and (30)
Compute
Fig. 3
Ap Eq. (33)
Output the final hypothesis: Eq. (25)

Figure

4: A skeleton of the algorithm for finding a classifier
based on an output code by solving the quadratic program
defined in Eq. (24).
Also note that,
(D r )]g
(D r+1 )]g
Recall that the function F () is linear in each interval
(D r ) F (D r+1
To solve the equation F
D   1 1, we first find r
such that (r) > 0 and (r which implies that
Using Eq. (38) and the equation F (D 1
(D r
Using the linearity of F () we obtain,
(D r
therefore
r
The complete algorithm is described in Fig. 3. Since it
takes O(k log time to sort the vector
D and another O(k)
time for the loop search, the total run time is O(k log k).
We are finally ready to give the algorithm for solving
learning problem described by Eq. (24). Since the output
code is constructed of the supporting patterns we term our
algorithm SPOC for Support Pattern Output Coding. The
SPOC algorithm is described in Fig. 4. We have also developed
methods for choosing an example p to modify on each
round and a stopping criterion for the entire optimization al-
gorithm. Due to lack of space we omit the details which will
appear in a full paper.
We have performed preliminary experiments with synthetic
data in order to check the actual performance of our
algorithm. We tested the special case corresponding to multiclass
SVM by setting  x. The code matrices we test0 50 100 150 200 250 300
No. of training examples
Log10(run
time)
QP

Figure

5: Run time comparison of two algorithms for code
design using quadratic programming: Matlab's standard QP
package and the proposed algorithm (denoted SPOC). Note
that we used a logarithmic scale for the run-time (y) axis.
are of columns. We varied
the size of the training set size from
The examples were generated using the uniform distribution
1]. The domain [
partitioned into four quarters of equal
Each quarter
was associated with a different label. For each sample size
we tested, we ran the algorithm three times, each run used a
different randomly generated training set. We compared the
standard quadratic optimization routine available from Matlab
with our algorithm which was also implemented in Mat-
lab. The average running time results are shown in Fig. 5.
Note that we used a log-scale for the y (run-time) axis. The
results show that the efficient algorithm can be two orders of
magnitude faster than the standard QP package.
7 Conclusions and future research
In this paper we investigated the problem of designing output
codes for solving multiclass problems. We first discussed
discrete codes and showed that while the problem is intractable
in general we can find the first column of a code matrix in
polynomial time. The question whether the algorithm can be
generalized to l  2 columns with running time of O(2 l )
or less remains open. Another closely related question is
whether we can find efficiently the next column given previous
columns. Also left open for future research is further usage
of the algorithm for finding the first column as a subroutine
in constructing codes based on trees or directed acyclic
graphs [18], and as a tool for incremental (column by col-
umn) construction of output codes.
Motivated by the intractability results for discrete codes
we introduced the notion of continuous output codes. We
described three optimization problems for finding good continuous
codes for a given a set of binary classifiers. We have
discussed in detail an efficient algorithm for one of the three
problems which is based on quadratic programming. As a
special case, our framework also provides a new efficient algorithm
for multiclass Support Vector Machines. The importance
of this efficient algorithm might prove to be crucial
in large classification problems with many classes such as
Kanji character recognition. We also devised efficient implementation
of the algorithm. The implementation details
of the algorithm, its convergence, generalization properties,
and more experimental results were omitted due to the lack
of space and will be presented elsewhere. Finally, an important
question which we have tackled barely in this paper is
the problem of interleaving the code design problem with the
learning of binary classifiers. A viable direction in this domain
is combining our algorithm for continuous codes with
the support vector machine algorithm.

Acknowledgement

We would like to thank Rob Schapire
for numerous helpful discussions, to Vladimir Vapnik for his
encouragement and support of this line of research, and to
Nir Friedman and Ran Bachrach for useful comments and
suggestions.



--R

Cloud classification using error-correcting output codes
Reducing multi-class to binary: A unifying approach for margin classifiers
The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network.


Linear Programming.


Solving multiclass learning problems via error-correcting output codes
Machine learning bias
Practical Methods of Optimization.
Classification by pair-wise coupling
Decision theoretic generalizations of the PAC model for neural net and other learning applications.
Robust trainability of single neurons.
The error coding method and PiCT.

Fast training of Support Vector Machines using sequential minimal optimization.
Large margin dags for multiclass classification.

Learning internal representations by error propagation.
Using output codes to boost multiclass learning problems.
Improved boosting algorithms using confidence-rated predictions
Estimation of Dependences Based on Empirical Data.
Statistical Learning Theory.
Support vector machines for multi-class pattern recognition
--TR

--CTR
Eibe Frank , Stefan Kramer, Ensembles of nested dichotomies for multi-class problems, Proceedings of the twenty-first international conference on Machine learning, p.39, July 04-08, 2004, Banff, Alberta, Canada
Olivier Lzoray , Hubert Cardot, Comparing Combination Rules of Pairwise Neural Networks Classifiers, Neural Processing Letters, v.27 n.1, p.43-56, February  2008
Pawalai Kraipeerapun , Chun Che Fung , Kok Wai Wong, Multiclass classification using neural networks and interval neutrosophic sets, Proceedings of the 5th WSEAS International Conference on Computational Intelligence, Man-Machine Systems and Cybernetics, p.123-128, November 20-22, 2006, Venice, Italy
Rong Jin , Jian Zhang, Multi-Class Learning by Smoothed Boosting, Machine Learning, v.67 n.3, p.207-227, June      2007
Libin Shen , Aravind K. Joshi, Ranking and Reranking with Perceptron, Machine Learning, v.60 n.1-3, p.73-96, September 2005
Ryan Rifkin , Aldebaro Klautau, In Defense of One-Vs-All Classification, The Journal of Machine Learning Research, 5, p.101-141, 12/1/2004
Ana Carolina Lorena , Andr C. P. L. F. de Carvalho, Protein cellular localization prediction with Support Vector Machines and Decision Trees, Computers in Biology and Medicine, v.37 n.2, p.115-125, February, 2007
S. B. Kotsiantis , I. D. Zaharakis , P. E. Pintelas, Machine learning: a review of classification and combining techniques, Artificial Intelligence Review, v.26 n.3, p.159-190, November  2006
SVM;output coding;multiclass categorization