Logistic Regression, AdaBoost and Bregman Distances.
We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this framework allows us to design and analyze algorithms for both simultaneously, and to easily adapt algorithms designed for one problem to the other. For both problems, we give new algorithms and explain their potential advantages over existing methods. These algorithms are iterative and can be divided into two types based on whether the parameters are updated sequentially (one at a time) or in parallel (all at once). We also describe a parameterized family of algorithms that includes both a sequential- and a parallel-update algorithm as special cases, thus showing how the sequential and parallel approaches can themselves be unified. For all of the algorithms, we give convergence proofs using a general formalization of the auxiliary-function proof technique. As one of our sequential-update algorithms is equivalent to AdaBoost, this provides the first general proof of convergence for AdaBoost. We show that all of our algorithms generalize easily to the multiclass case, and we contrast the new algorithms with the iterative scaling algorithm. We conclude with a few experimental results with synthetic data that highlight the behavior of the old and newly proposed algorithms in different settings.
INTRODUCTION
We give a unified account of boosting and logistic regression
in which we show that both learning problems can be cast in
terms of optimization of Bregman distances. In our frame-
work, the two problems become extremely similar, the only
real difference being in the choice of Bregman distance: un-normalized
relative entropy for boosting, and binary relative
entropy for logistic regression.
The fact that the two problems are so similar in our frame-work
allows us to design and analyze algorithms for both si-
multaneously. We are now able to borrow methods from the
maximum-entropy literature for logistic regression and apply
them to the exponential loss used by AdaBoost, especially
convergence-proof techniques. Conversely, we can now easily
adapt boosting methods to the problem of minimizing the
logistic loss used in logistic regression. The result is a family
of new algorithms for both problems together with convergence
proofs for the new algorithms as well as AdaBoost.
For both AdaBoost and logistic regression, we attempt
to choose the parameters or weights associated with a given
family of functions called features or weak hypotheses. AdaBoost
works by sequentially updating these parameters one
by one, whereas methods for logistic regression,most notably
iterative scaling [9, 10], are iterative but update all parameters
in parallel on each iteration.
Our first new algorithm is a method for optimizing the
exponential loss using parallel updates. It seems plausible
that a parallel-update method will often converge faster than
a sequential-update method, provided that the number of
features is not so large as to make parallel updates infeasible.
Some preliminary experiments suggest that this is the case.
Our second algorithm is a parallel-update method for the
logistic loss. Although parallel-update algorithms are well
known for this function, the updates that we derive are new,
and preliminary experiments indicate that these new updates
may also be much faster. Because of the unified treatment
we give to the exponential and logistic loss functions, we are
able to present and prove the convergence of the algorithms
for these two losses simultaneously. The same is true for the
other algorithms presented in this paper as well.
We next describe and analyze sequential-update algorithms
for the two loss functions. For exponential loss, this
algorithm is equivalent to the AdaBoost algorithm of Freund
and Schapire [13]. By viewing the algorithm in our frame-
work, we are able to prove that AdaBoost correctly converges
to the minimum of the exponential loss function. This is a
new result: Although Kivinen and Warmuth [16] and Mason
et al. [19] have given convergence proofs for AdaBoost,
their proofs depend on assumptions about the given minimization
problem which may not hold in all cases. Our proof
holds in general without assumptions.
Our unified view leads instantly to a sequential-update
algorithm for logistic regression that is only a minor modification
of AdaBoost and which is very similar to one proposed
by Duffy and Helmbold [12]. Like AdaBoost, this algorithm
can be used in conjunction with any classification algorithm,
usually called the weak learning algorithm, that can accept
a distribution over examples and return a weak hypothesis
with low error rate with respect to the distribution. How-
ever, this new algorithm provably minimizes the logistic loss
rather than the arguably less natural exponential loss used by
AdaBoost.
Another potentially important advantage of this new algorithm
is that the weights that it places on examples are
bounded in [0; 1]. This suggests that it may be possible to use
the new algorithm in a setting in which the boosting algorithm
selects examples to present to the weak learning algorithm by
filtering a stream of examples (such as a very large dataset).
As pointed out by Watanabe [22] and Domingo and Watanabe
[11], this is not possible with AdaBoost since its weights
may become extremely large. They provide a modification
of AdaBoost for this purpose in which the weights are truncated
at 1. The new algorithm may be a viable and cleaner
alternative.
We next describe a parameterized family of iterative algorithms
that includes both parallel- and sequential-update
algorithms and that also interpolates smoothly between the
two extremes. The convergence proof that we give holds for
this entire family of algorithms.
Although most of this paper considers only the binary
case in which there are just two possible labels associated
with each example, it turns out that the multiclass case requires
no additional work. That is, all of the algorithms
and convergence proofs that we give for the binary case turn
out to be directly applicable to the multiclass case without
modification.
For comparison,we also describe the generalized iterative
scaling algorithm of Darroch and Ratcliff [9]. In rederiving
this procedure in our setting, we are able to relax one of the
main assumptions usually required by this algorithm.
The paper is organized as follows: Section 2 describes
the boosting and logistic regression models as they are usually
formulated. Section 3 gives background on optimization
using Bregman distances, and Section 4 then describes
how boosting and logistic regression can be cast within this
framework. Section 5 gives our parallel-update algorithms
and proofs of their convergence, while Section 6 gives the
sequential-update algorithms and convergence proofs. The
parameterized family of iterative algorithms is described in
Section 7. The extension to multiclass problems is given
in Section 8. In Section 9, we contrast our methods with
iterative scaling. In Section 10, we give some preliminary
experiments.
Previous work. Variants of our sequential-update algorithms
fit into the general family of "arcing" algorithms presented
by Breiman [4, 3], as well as Mason et al.'s ``AnyBoost''
family of algorithms [19]. The information-geometric view
that we take also shows that the algorithms we study, including
AdaBoost, fit into a family of algorithms described in
1967 by Bregman [2] for satisfying a set of constraints.
Our work is based directly on the general setting of Laf-
ferty, Della Pietra and Della Pietra [18] in which one attempts
to solve optimization problems based on general Bregman
distances. They gave a method for deriving and analyzing
parallel-update algorithms in this setting through the use of
auxilliary functions. All of our algorithms and convergence
proofs are based on this method.
Our work builds on several previous papers which have
compared boosting approaches to logistic regression. Fried-
man, Hastie and Tibshirani [14] first noted the similarity between
the boosting and logistic regression loss functions, and
derived the sequential-update algorithm LogitBoost for the
logistic loss. However, unlike our algorithm, theirs requires
that the weak learner solve least-squares problems rather
than classification problems. Another sequential-update algorithm
for a different but related problem was proposed by
Cesa-Bianchi, Krogh and Warmuth [5].
Duffy and Helmbold [12] gave conditions under which a
loss function gives a boosting algorithm. They showed that
minimizing logistic loss does lead to a boosting algorithm
in the PAC sense, which suggests that our algorithm for this
problem, which is very close to theirs, may turn out also to
have the PAC boosting property.
Lafferty [17] went further in studying the relationship
between logistic regression and the exponential loss through
the use of a family of Bregman distances. However, the
setting described in his paper apparently cannot be extended
to precisely include the exponential loss. The use of Bregman
distances that we describe has important differences leading
to a natural treatment of the exponential loss and a new view
of logistic regression.
Our work builds heavily on that of Kivinen and Warmuth
[16] who, along with Lafferty, were the first to make
a connection between AdaBoost and information geometry.
They showed that the update used by AdaBoost is a form of
"entropy projection." However, the Bregman distance that
they used differed slightly from the one that we have chosen
(normalized relative entropy rather than unnormalized relative
entropy) so that AdaBoost's fit in this model was not quite
complete; in particular, their convergence proof depended on
assumptions that do not hold in general. Kivinen and Warmuth
also described updates for general Bregman distances
including, as one of their examples, the Bregman distance
that we use to capture logistic regression.
BOOSTING, LOGISTIC MODELS AND
LOSS FUNCTIONS
be a set of training examples
where each instance x i belongs to a domain or instance
space X , and each label y
We assume that we are also given a set of real-valued functions
on Following convention in the MaxEnt
literature, we call these functions features; in the boosting
literature, these would be called weak or base hypotheses.
We study the problem of approximating the y i 's using a
linear combination of features. That is, we are interested in
the problem of finding a vector of parameters - 2 R n such
that f -
"good approximation" of
y i . How we measure the goodness of such an approximation
varies with the task that we have in mind.
For classification problems, it is natural to try to match
the sign of f - that is, to attempt to minimize
where is true and 0 otherwise. Although minimization
of the number of classification errors may be a
worthwhile goal, in its most general form, the problem is
intractable (see, for instance, [15]). It is therefore often
advantageous to instead minimize some other nonnegative
loss function. For instance, the boosting algorithm AdaBoost
[13, 20] is based on the exponential loss
exp
\Gammay
It can be verified that Eq. (1) is upper bounded by Eq. (2);
however, the latter loss is much easier to work with as demonstrated
by AdaBoost. Briefly, on each of a series of rounds,
AdaBoost uses an oracle or subroutine called the weak learning
algorithm to pick one feature (weak hypothesis) h j , and
the associated parameter - j is then updated. It has been noted
by Breiman [3, 4] and various later authors that both of these
steps are done in such a way as to (approximately) cause the
greatest decrease in the exponential loss. In this paper, we
show for the first time that AdaBoost is in fact a provably effective
method for finding parameters - which minimize the
exponential loss (assuming the weak learner always chooses
the "best" h j ).
We also give an entirely new algorithm for minimizing exponential
loss in which, on each round, all of the parameters
are updated in parallel rather than one at a time. Our hope
is that this parallel-update algorithm will be faster than the
sequential-update algorithm; see Section 10 for preliminary
experiments in this regard.
Instead of using f - as a classification rule, we might
instead postulate that the y i 's were generated stochastically
as a function of the x i 's and attempt to use f - (x) to estimate
the probability of the associated label y. A very natural and
well-studied way of doing this is to pass f - through a logistic
function, that is, to use the estimate
The likelihood of the labels occuring in the sample then is
Y
\Gammay
Maximizing this likelihood then is equivalent to minimizing
the log loss of this model
\Gammay
Generalized and improved iterative scaling [9, 10] are
popular parallel-update methods for minimizing this loss. In
this paper, we give an alternative parallel-update algorithm
which we compare to iterative scaling techniques in preliminary
experiments in Section 10.
In this section, we give background on optimization using
Bregman distances. This will form the unifying basis for
our study of boosting and logistic regression. The particular
set-up that we follow is taken primarily from Lafferty, Della
Pietra and Della Pietra [18].
R be a continuously differentiable and
strictly convex function defined on a closed, convex set D '
. The Bregman distance associated with F is defined for
to be
For instance, when
BF is the (unnormalized) relative entropy
DU
It can be shown that, in general, every Bregman distance
is nonnegative and is equal to zero if and only if its two
arguments are equal.
There is a natural optimization problem that can be associated
with a Bregman distance, namely, to find the vector
that is closest to a given vector q 0 2 D subject to a set
of linear constraints. These constraints are specified by an
m \Theta n matrix M and a vector -
D. The vectors p satisfying
these constraints are those for which
the problem is to find
arg min
where
The "convex dual" of this problem gives an alternative
formulation. Here, the problem is to find the vector of a
particular form that is closest to a given vector -
p. The form
of such vectors is defined via the Legendre transform, written
simply v ffi q when F is clear from context):
Using calculus, this can be seen to be equivalent to
For instance, when BF is unnormalized relative entropy, it
can be verified using calculus that
(v
From Eq. (6), it is useful to note that
For a given m \Theta n matrix M and vector q 0 2 D, we
consider vectors obtained by taking the Legendre transform
of a linear combination of columns of M with the vector q 0 ,
that is, vectors in the set
The dual optimization problem now can be stated to be the
problem of finding
arg min
where Q is the closure of Q.
The remarkable fact about these two optimization problems
is that their solutions are the same, and, moreover, this
solution turns out to be the unique point at the intersection
of P and Q. We take the statement of this theorem from
Lafferty, Della Pietra and Della Pietra [18]. The result appears
to be due to Csisz- ar [6, 7] and Topsoe [21]. A proof for
the case of (normalized) relative entropy is given by Della
Pietra, Della Pietra and Lafferty [10]. See also Csisz- ar's
survey article [8].
Theorem 1 Let -
and Q be as above.
Assume BF
1. Then there exists a unique
2. BF
\Delta for any
3.
4. q
Moreover, any one of these four properties determines q ?
uniquely.
This theorem will be extremely useful in proving the
convergence of the algorithms described below. We will
show in the next section how boosting and logistic regression
can be viewed as optimization problems of the type given
in part 3 of the theorem. Then, to prove optimality, we only
need to show that our algorithms converge to a point in P "Q.
REGRESSION REVISITED
We return now to the boosting and logistic regression problems
outlined in Section 2, and show how these can be cast
in the form of the optimization problems outlined above.
Recall that for boosting, our goal is to find - such that
exp@ \Gammay i
is minimized, or, more precisely, if the minimum is not attained
at a finite -, then we seek a procedure for finding a
sequence which causes this function to converge
to its infimum. For shorthand, we call this the ExpLoss problem

To view this problem in the form given in Section 3, we
all 0's and all 1's vectors). We
which it follows that (M-)
. Finally, we take F
to be as in Eq. (4) so that BF is the unnormalized relative
entropy.
As noted earlier, in this case, v ffi q is as given in Eq. (7).
In particular, this means that
Furthermore, it is trivial to see that
DU
so that DU
\Delta is equal to Eq. (10). Thus,
minimizing DU
equivalent to minimizing
Eq. (10). By Theorem 1, this is equivalent to finding
satisfying the constraints
Logistic regression can be reduced to an optimization
problem of this form in nearly the same way. Recall that here
our goal is to find - (or a sequence of -'s) which minimize
For shorthand, we call this the LogLoss problem. We define
and M exactly as for exponential loss. The vector q 0 is still
constant, but now is defined to be (1=2)1, and the space D
is now restricted to be [0; 1] m . These are minor differences,
however. The only important difference is in the choice of
the function F , namely,
The resulting Bregman distance is
Trivially,
For this choice of F , it can be verified using calculus that
(v
so that
\Delta is
equal to Eq. (13) so minimizing DB
is equivalent to minimizing Eq. (13). As before, this is the
same as finding q 2 Q satisfying the constraints in Eq. (12).
In this section, we describe a new algorithm for the
ExpLoss and LogLoss problems using an iterative method
in which all weights - j are updated on each iteration. The
algorithm is shown in Fig. 1. The algorithm can be used
with any function F satisfying certain conditions described
below; in particular, we will see that it can be used with
the choices of F given in Section 4. Thus, this is really a
single algorithm that can be used for both loss-minimization
problems by setting the parameters appropriately. Note that,
without loss of generality, we assume in this section that for
all instances i,
The algorithm is very simple. On each iteration, the
vector ffi t is computed as shown and added to the parameter
vector - t . We assume for all our algorithms that the inputs
are such that infinite-valued updates never occur.
This algorithm is new for both minimization problems.
Optimization methods for ExpLoss, notably AdaBoost, have
Parameters: D
Assumptions 1 and 2
such that BF
lim
For
ffl For
ffl Update parameters: -

Figure

1: The parallel-update optimization algorithm.
generally involved updates of one feature at a time. Parallel-
update methods for LogLoss are well known (see, for exam-
ple, [9, 10]). However, our updates take a different form from
the usual updates derived for logistic models.
A useful point is that the distribution q t+1 is a simple
function of the previous distribution q t . By Eq. (8),
This gives
for ExpLoss and LogLoss respectively.
We will prove next that the algorithm given in Fig. 1 converges
to optimality for either loss. We prove this abstractly
for any matrix M and vector q 0 , and for any function F
satisfying the following assumptions:
Assumption 1 For any v 2 R m , q 2 D,
Assumption 2 For any c ! 1, the set
is bounded.
We will show later that the choices of F given in Section
4 satisfy these assumptions which will allow us to prove
convergence for ExpLoss and LogLoss.
To prove convergence,we use the auxiliary-function technique
of Della Pietra, Della Pietra and Lafferty [10]. Very
roughly, the idea of the proof is to derive a nonnegative lower
bound called an auxiliary function on how much the loss
decreases on each iteration. Since the loss never increases
and is lower bounded by zero, the auxiliary function must
converge to zero. The final step is to show that when the
auxiliary function is zero, the constraints defining the set P
must be satisfied, and therefore, by Theorem 1, we must have
converged to optimality.
More formally, we define an auxiliary function for a sequence
M to be a continuous function
satisfying the two conditions:
and
Before proving convergence of specific algorithms, we
prove the following lemma which shows, roughly, that if a
sequence has an auxiliary function, then the sequence converges
to the optimum point q ? . Thus, proving convergence
of a specific algorithm reduces to simply finding an auxiliary
function.
A be an auxiliary function for
matrix M. Assume the q t 's lie in a compact subspace of Q
where Q is as in Eq. (9); in particular, this will be the case if
Assumption 2 holds and BF
lim
Proof: By condition (18), BF
\Delta is a nonincreasing
sequence which is bounded below by zero. Therefore, the sequence
of differences BF
must
converge to zero. By condition (18), this means that A(q t )
must also converge to zero. Because we assume that the q t 's
lie in a compact space, the sequence of q t 's must have a sub-sequence
converging to some point -
D. By continuity of
A, we have A( -
where P is as in Eq. (5). On the other hand, -
q is the limit of
a sequence of points in Q so -
by Theorem 1.
This argument and the uniqueness of q ? show that the
have only a single limit point q ? . Suppose that the entire
sequence did not converge to q ? . Then we could find an
open set B containing q ? such that fq 1 contains
infinitely many points and therefore has a limit point which
must be in the closed set so must be different from
q ? . This, we have already argued, is impossible. Therefore,
the entire sequence converges to q ? .
We can now apply this lemma to prove the convergence
of the algorithm of Fig. 1.
Theorem 3 Let F satisfy Assumptions 1 and 2, and assume
that BF
1. Let the sequences -
generated by the algorithm of Fig. 1. Then
lim
where Q is as in Eq. (9). That is,
lim
Proof: Let
so that W
We claim that
the function
is an auxiliary function for Clearly, A is continuous
and nonpositive.
We can upper bound the change in
\Delta on round t by A(q t ) as follows:
Eqs. (20) and (21) follow from Eq. (16) and Assumption 1,
respectively. Eq. (22) uses the fact that, for any x j 's and for
by Jensen's inequality applied to the convex function e x .
Eq. (23) uses the definitions of W
t;j and W \Gamma
t;j , and Eq. (24)
uses our choice of ffi t (indeed, ffi t was chosen specifically to
minimize Eq. (23)).
If
j (q), that is,
Thus, A is an auxiliary function for :. The theorem
now follows immediately from Lemma 2.
To apply this theorem to the ExpLoss and LogLoss prob-
lems, we only need to verify that Assumptions 1 and 2 are
satisfied. For ExpLoss, Assumption 1 holds with equality.
For LogLoss,
The first and second equalities use Eqs. (14) and (15), respec-
tively. The final inequality uses 1
Assumption 2 holds trivially for LogLoss since
is bounded. For ExpLoss, if DU
which clearly defines a bounded subset of R
.
6 SEQUENTIAL ALGORITHMS
In this section, we describe another algorithm for the same
minimization problems described in Section 4. However,
unlike the algorithm of Section 5, the one that we present
now only updates the weight of one feature at a time. While
the parallel-update algorithm may give faster convergence
when there are not too many features, the sequential-update
algorithm can be used when there are a very large number
of features using an oracle for selecting which feature to
update next. For instance, AdaBoost, which is essentially
equivalent to the sequential-update algorithm for ExpLoss,
uses an assumed weak learning algorithm to select a weak
hypothesis, i.e., one of the features. The sequential algorithm
that we present for LogLoss can be used in exactly the same
way. The algorithm is shown in Fig. 2.
Theorem 4 Given the assumptions of Theorem 3, the algorithm
of Fig. 2 converges to optimality in the sense of
Theorem 3.
Proof: For this theorem, we use the auxiliary function
Parameters: (same as in Fig. 1)
Output: (same as in Fig. 1)
For
ae ff t if
else
ffl Update parameters: -

Figure

2: The sequential-update optimization algorithm.
This function is clearly continuous and nonpositive. We have
that
where Eq. (27) uses the convexity of e \Gammaff t x , and Eq. (29)
uses our choice of ff t (as before, we chose ff t to minimize
the bound in Eq. (28)).
If
so
Thus, A is an auxiliary function
for and the theorem follows immediately from
Lemma 2.
As mentioned above, this algorithm is essentially equivalent
to AdaBoost, specifically, the version of AdaBoost first
presented by Freund and Schapire [13]. In AdaBoost, on
each iteration, a distribution D t over the training examples
is computed and the weak learner seeks a weak hypothesis
with low error with respect to this distribution. The algorithm
presented in this section assumes that the space of weak hypotheses
consists of the features h and that the
learner always succeeds in selecting the feature with
lowest error (or, more accurately, with error farthest from
1=2). Translating to our notation, the weight D t (i) assigned
to example AdaBoost is exactly equal to q t;i =Z t ,
and the weighted error of the t-th weak hypothesis is equal
Theorem 4 then is the first proof that AdaBoost always
converges to the minimum of the exponential loss (assuming
an idealized weak learner of the form above). Note that when
theorem also tells us the exact form of lim D t .
However, we do not know what the limiting behavior of D t
is when q nor do we know about the limiting behavior
of the parameters - t (whether or not q
We have also presented in this section a new algorithm for
logistic regression. In fact, this algorithm is the same as one
given by Duffy and Helmbold [12] except for the choice of
ff t . In practical terms, very little work would be required to
alter an existing learning system based on AdaBoost so that
it uses logistic loss rather than exponential loss-the only
difference is in the manner in which q t is computed from - t .
We can even do this for systems based on "confidence-rated"
boosting [20] in which ff t and j t are chosen together on each
round to minimize Eq. (26) rather than an approximation of
this expression as used in the algorithm of Fig. 2. (Note that
the proof of Theorem 4 can easily be modified to prove the
convergence of such an algorithm using the same auxiliary
7 A PARAMETERIZED FAMILY OF
ITERATIVE ALGORITHMS
In previous sections, we described separate parallel- and
sequential-update algorithms. In this section, we describe a
parameterized family of algorithms that includes the parallel-
update algorithm of Section 5 as well as a sequential-update
algorithm that is different from the one in Section 6. This
family of algorithms also includes other algorithms that may
be more appropriate than either in certain situations as we
explain below.
The algorithm, which is shown in Fig. 3, is similar to
the parallel-update algorithm of Fig. 1. On each round, the
quantities
t;j and W \Gamma
t;j are computed as before, and the
vector d t is computed as ffi t was computed in Fig. 1. Now,
however, this vector d t is not added directly to - t . Instead,
another vector a t is selected which provides a "scaling" of
the features. This vector is chosen to maximize a measure
of progress while restricted to belong to the set AM . The
allowed form of these scaling vectors is given by the set A,
a parameter of the algorithm; AM is the restriction of A to
those vectors a satisfying the constraint that for all i,
a
The parallel-update algorithm of Fig. 1 is obtained by
choosing assuming that
all i. (Equivalently, we can make no such assumption, and
choose
Parameters: (same as in Fig. 1)
A ' R n
m\Thetan satisfying the condition that
a
Output: (same as in Fig. 1)
For
ffl For
d t;j =2
ffl a
a j
ffl Update parameters: -

Figure

3: A parameterized family of iterative optimization
algorithms.
We can obtain a sequential-update algorithm by choosing
A to be the set of unit vectors (i.e., with one component equal
to 1 and all others equal to 0), and assuming that M ij 2
j. The update then becomes
ae
d t;j if
else
where
Another interesting case is when we assume that
all i. It is then natural to choose
which ensures that A. Then the maximization over
AM can be solved analytically giving the update
. (This idea generalizes
easily to the case in which
any dual norms p and q.)
A final case is when we do not restrict the scaling vectors
at all, i.e., we choose A = R
. In this case, the maximization
problem that must be solved to choose each a t is a linear
programming problem with n variables and m constraints.
We now prove the convergence of this entire family of
algorithms.
Theorem 5 Given the assumptions of Theorem 3, the algorithm
of Fig. 3 converges to optimality in the sense of
Theorem 3.
Proof: We use the auxiliary function
a j
are as in Theorem 3. This function is
continuous and nonpositive. We can bound the change in
using the same technique given in Theorem 3:
a t;j d
a
a t;j
a t;j
Finally, if
a j
0:
Since for every j there exists a 2 AM with a j ? 0, this
implies
Applying Lemma 2 completes the theorem.
In this section, we show how all of our results can be extended
to the multiclass case. Because of the generality of the preceding
results, we will see that no new algorithms need be
devised and no new convergence proofs need be proved for
this case. Rather, all of the preceding algorithms and proofs
can be directly applied to the multiclass case.
In the multiclass case, the label set Y has cardinality k.
Each feature is of the form h In logistic
regression, we use a model
e f- (x;y)
'6=y e f- (x;')\Gammaf - (x;y)
y). The loss on a training
set then is
e f-
We transform this into our framework as follows: Let
fy i gg:
The vectors p, q, etc. that we work with are in R
. That is,
they are 1)m-dimensional and are indexed by pairs in
B. Let -
. The convex function F that we
use for this case is
which is defined over the space
The resulting Bregman distance is
'6=y
Clearly,
It can be shown that
(v
Assumption 1 can be verified by noting that
(i;')2B
Now let M
(1=k)1. Plugging in these definitions gives that
\Delta is equal to Eq. (31). Thus, the algorithms
of Sections 5, 6 and 7 can all be used to solve this
minimization problem, and the corresponding convergence
proofs are also directly applicable.
There are several multiclass versions of AdaBoost. Ada-
Boost.M2 [13] (a special case of AdaBoost.MR [20]), is
based on the loss function
(i;')2B
exp
For this loss, we can use a similar set up except for the choice
of F . We instead use
(i;')2B
for
. In fact, this is actually the same F used
for (binary) AdaBoost. We have merely changed the index
set to B. Thus, as before,
(i;')2B
and
(v
Choosing M as we did for multiclass logistic regression and
we have that BF
\Delta is equal to the
loss in Eq. (33). We can thus use the preceding algorithms
to solve this multiclass problem as well. In particular, the
sequential-update algorithm gives AdaBoost.M2.
AdaBoost.MH [20] is another multiclass version of Ada-
Boost. For AdaBoost.MH, we replace B by the index set
and for each example i and label ' 2 Y , we define
ae
The loss function for AdaBoost.MH is
exp
We now let M
use again the same F
as in binary AdaBoost with q to obtain this multiclass
version of AdaBoost.
9 A COMPARISON TO ITERATIVE
In this section, we describe the generalized iterative scaling
(GIS) procedure of Darroch and Ratcliff [9] for comparison
to our algorithms. We largely follow the description of GIS
given by Berger, Della Pietra and Della Pietra [1] for the
multiclass case. To make the comparison as stark as possible,
we present GIS in our notation and prove its convergence
using the methods developed in previous sections. In doing
so, we are also able to relax one of the key assumptions
traditionally used in studying GIS.
We adopt the notation and set-up used for multiclass logistic
regression in Section 8. (To our knowledge, there is no
analog of GIS for the exponential loss so we only consider
the case of logistic loss.) We also extend this notation by
defining q i;y
so that q i;' is now defined for all
Moreover, it can be verified that q
defined in Eq. (30) if
In GIS, the following assumptions regarding the features
are usually made:
In this section, we prove that GIS converges with the second
condition replaced by a milder one, namely, that
Since, in the multiclass case, a constant can be added to
all features h j without changing the model or loss function,
and since the features can be scaled by any constant, the two
assumptions we consider clearly can be made to hold without
loss of generality. The improved iterative scaling algorithm
of Della Pietra, Della Pietra and Lafferty [10] also requires
only these milder assumptions but is much more complicated
to implement, requiring a numerical search (such as Newton-
Raphson) for each feature on each iteration.
GIS works much like the parallel-update algorithm of
Section 5 with F , M and q 0 as defined for multiclass logistic
regression in Section 8. The only difference is in the computation
of the vector of updates ffi t , for which GIS requires
direct access to the features h j . Specifically, in GIS, ffi t is
defined to be
where
Clearly, these updates are quite different from the updates
described in this paper.
Using more notation from Sections 5 and 8, we can re-formulate
our framework as follows:
\Theta h j

(i;')2B
We can now prove the convergence of these updates using
the usual auxiliary function method.
Theorem 6 Let F , M and q 0 be as above. Then the modified
GIS algorithm described above converges to optimality in the
sense of Theorem 3.
Proof: We will show that
is an auxilliary function for the vectors q computed
by GIS. Clearly, A is continuous, and the usual nonnegativity
properties of unnormalized relative entropy imply that
From Eq. (35), H only if W
Thus, implies that the constraints q T
the proof of Theorem 3. All that remains to be shown is that
where
We introduce the notation
and then rewrite the gain as follows using Eq. (32):
Plugging in definitions, the first term of Eq. (38) can be
written as
Next we derive an upper boundon the second term of Eq. (38):
0.9training loss
i.s.
seq
seq2
par
40.30.50.70.9training loss
i.s.
seq
seq2
par

Figure

4: The training logistic loss on data generated by a noisy hyperplane with many (left) or few (right) relevant features.
Eq. (40) follows from the log bound ln x - x \Gamma 1. Eq. (42)
uses Eq. (25) and our assumption on the form of the h j 's.
Eq. (43) follows from our definition of the update ffi.
Finally, combining Eqs. (36), (38), (39) and (44) gives
Eq. (37) completing the proof.
It is clear that the differences between GIS and the updates
given in this paper stem from Eq. (38), which is derived from
on the i'th term
in the sum. This choice of C effectively means that the log
bound is taken at a different point (ln
1). In this more general case, the bound is
exact at varying C varies where the bound
is taken, and thereby varies the updates.
In this section, we briefly describe some experiments using
synthetic data. These experiments are preliminary and
are only intended to suggest the possibility of these algo-
rithms' having practical value. More systematic experiments
are clearly needed using both real-world and synthetic data,
and comparing the new algorithms to other commonly used
procedures.
We first tested how effective the methods are at minimizing
the logistic loss on the training data. In the first ex-
periment, we generated data using a very noisy hyperplane.
More specifically, we first generated a random hyperplane
in 100-dimensional space represented by a vector w 2 R 100
(chosen uniformly at random from the unit sphere). We then
chose 300 points x 2 R
100 where each point is normally
distributed x - N(0; I). We next assigned a label y to each
point depending on whether it fell above or below the chosen
hyperplane, i.e., After each label was
chosen, we perturbed each point x by adding to it a random
amount " where " - N(0; 0:8 I). This had the effect of
causing the labels of points near the separating hyperplane
to be more noisy than points that are farther from it. The
features were identified with coordinates of x.
We ran the parallel- and sequential-update algorithms of
Sections 5 and 6 (denoted "par" and "seq" in the figures)
on this data. We also ran the sequential-update algorithm
that is a special case of the parameterized family described
in Section 7 (denoted "seq2"). Finally, we ran the iterative
scaling algorithm described in Section 9 ("i.s.
The results of this experiment are shown on the left of
Fig. 4 which shows a plot of the logistic loss on the training
set for each of the four methods as a function of the number
of iterations. (The loss has been normalized to be 1 when
of our methods do very well in comparison
to iterative scaling. The parallel-update method is clearly
the best, followed closely by the second sequential-update
algorithm. The parallel-update method can be as much as
times faster (in terms of number of iterations) than iterative
scaling.
On the right of Fig. 4 are shown the results of a similar
experiment in which all but four of the components of
w were forced to be zero. In other words, there were only
four relevant variables or features. In this experiment, the
sequential-update algorithms, which perform a kind of feature
selection, initially have a significant advantage over the
test error
log seq
exp seq
log par
exp par

Figure

5: The test misclassification error on data generated
by a noisy hyperplane with Boolean features.
parallel-update algorithm, but are eventually overtaken.
In the last experiment, we tested how effective the new
competitors of AdaBoost are at minimizing the test misclassification
error. In this experiment, we chose a separating
hyperplane w as in the first experiment. Now, however, we
chose 1000 points x uniformly at random from the Boolean
hypercube f\Gamma1; +1g 100 . The labels y were computed as
before. After the labels y were chosen, we flipped each coordinate
of each point x independently with probability 0:05.
This noise model again has the effect of causing examples
near the decision surface to be noisier than those far from it.
For this experiment, we used the parallel- and sequential-
update algorithms of Sections 5 and 6 (denoted "par" and
"seq"). In both cases, we used variants based on exponential
loss ("exp") and logistic loss ("log"). (In this case, the
sequential-update algorithms of Sections 6 and 7 are identi-
cal.)
Fig. 5 shows a plot of the classification error on a separate
test set of 5000 examples. There is not a very large difference
in the performance of the exponential and logistic variants of
the algorithms. However, the parallel-update variants start
out doing much better, although eventually all of the methods
converge to roughly the same performance level.

ACKNOWLEDGMENTS

Many thanks to Manfred Warmuth for first teaching us about
Bregman distances and for many comments on an earlier
draft. Thanks also to Nigel Duffy, David Helmbold and Raj
Iyer for helpful discussions and suggestions. Some of this
research was done while Yoram Singer was at AT&T Labs.



--R

Della Pietra
The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming.
Arcing the edge.
Prediction games and arcing classifiers.




Generalized iterative scaling for log-linear models
Inducing features of random fields.
Scaling up a boosting- based learner via adaptive sampling
Potential boosters?
A decision-theoretic generalization of on-line learning and an application to boosting
Additive logistic regression: a statistical view of boosting.

Boosting as entropy projection.
Additive models
Statistical learning algorithms based on Bregman dis- tances
Functional gradient techniques for combining hypothe- ses
Improved boosting algorithms using confidence-rated predictions
Information theoretical optimization techniques.
From computational learning theory to discovery science.
--TR

--CTR
Stefan Riezler, New Developments in Parsing Technology, Computational Linguistics, v.32 n.3, p.439-442, September 2006
Nir Krause , Yoram Singer, Leveraging the margin more carefully, Proceedings of the twenty-first international conference on Machine learning, p.63, July 04-08, 2004, Banff, Alberta, Canada
Hoiem , Alexei A. Efros , Martial Hebert, Automatic photo pop-up, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
Zhihua Zhang , James T. Kwok , Dit-Yan Yeung, Surrogate maximization/minimization algorithms for AdaBoost and the logistic regression model, Proceedings of the twenty-first international conference on Machine learning, p.117, July 04-08, 2004, Banff, Alberta, Canada
Cynthia Rudin , Ingrid Daubechies , Robert E. Schapire, The Dynamics of AdaBoost: Cyclic Behavior and Convergence of Margins, The Journal of Machine Learning Research, 5, p.1557-1595, 12/1/2004
Steven J. Phillips , Miroslav Dudk , Robert E. Schapire, A maximum entropy approach to species distribution modeling, Proceedings of the twenty-first international conference on Machine learning, p.83, July 04-08, 2004, Banff, Alberta, Canada
Amir Globerson , Terry Y. Koo , Xavier Carreras , Michael Collins, Exponentiated gradient algorithms for log-linear structured prediction, Proceedings of the 24th international conference on Machine learning, p.305-312, June 20-24, 2007, Corvalis, Oregon
Zhihua Zhang , James T. Kwok , Dit-Yan Yeung, Surrogate maximization/minimization algorithms and extensions, Machine Learning, v.69 n.1, p.1-33, October   2007
Taneli Mielikinen , Evimaria Terzi , Panayiotis Tsaparas, Aggregating time partitions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Joshua Goodman, Sequential conditional Generalized Iterative Scaling, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania
Stefano Merler , Bruno Caprile , Cesare Furlanello, Parallelizing AdaBoost by weights dynamics, Computational Statistics & Data Analysis, v.51 n.5, p.2487-2498, February, 2007
Gokhan Tur, Extending boosting for large scale spoken language understanding, Machine Learning, v.69 n.1, p.55-74, October   2007
Hoiem , Alexei A. Efros , Martial Hebert, Recovering Surface Layout from an Image, International Journal of Computer Vision, v.75 n.1, p.151-172, October   2007
W. John Wilbur , Lana Yeganova , Won Kim, The Synergy Between PAV and AdaBoost, Machine Learning, v.61 n.1-3, p.71-103, November  2005
Heinz H. Bauschke, Duality for Bregman projections onto translated cones and affine subspaces, Journal of Approximation Theory, v.121 n.1, p.1-12, March
Joseph Turian , I. Dan Melamed, Advances in discriminative parsing, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.873-880, July 17-18, 2006, Sydney, Australia
Michael Collins, Parameter estimation for statistical parsing models: theory and practice of distribution-free methods, New developments in parsing technology, Kluwer Academic Publishers, Norwell, MA, 2004
Michael Collins , Terry Koo, Discriminative Reranking for Natural Language Parsing, Computational Linguistics, v.31 n.1, p.25-70, March 2005
Ron Meir , Gunnar Rtsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
logistic regression;maximum-entropy methods;boosting;iterative scaling;convex optimization;information geometry;adaboost;bregman distances