Mistake Bounds
for Maximum Entropy Discrimination
Philip M. Long
Center for Computational Learning Systems
Columbia University
plong@cs.columbia.edu

Xinyu Wu
Department of Computer Science
National University of Singapore
wuxy@comp.nus.edu.sg

Abstract
We establish a mistake bound for an ensemble method for classification
based on maximizing the entropy of voting weights subject to margin
constraints. The bound is the same as a general bound proved for the
Weighted Majority Algorithm, and similar to bounds for other variantsof Winnow. We prove a more refined bound that leads to a nearly optimal algorithm for learning disjunctions, again, based on the maximum
entropy principle. We describe a simplification of the on-line maximum
entropy method in which, after each iteration, the margin constraints are
replaced with a single linear inequality. The simplified algorithm, whichtakes a similar form to Winnow, achieves the same mistake bounds.

1 Introduction
In this paper, we analyze a maximum-entropy procedure for ensemble learning in the online learning model. In this model, learning proceeds in trials. During the tth trial, thealgorithm (1) receives xt ∈ {0, 1}n (interpreted in this work as a vector of base classifier
predictions), (2) predicts a class ŷt ∈ {0, 1}, and (3) discovers the correct class yt . During
trial t, the algorithm has access only to information from previous trials.
The first algorithm we will analyze for this problem was proposed by Jaakkola, Meila
and Jebara [14]. The algorithm, at each trial t, makes its prediction by taking a weighted
vote over the predictions of the base classifiers. The weight vector p t is the probability
distribution over the n base classifiers that maximizes the entropy, subject to the constraintthat pt correctly classifies all patterns seen in previous trials with a given margin γ. Thatis, it maximizes the entropy of pt subject to the constraints that pt ·xs ≥ 1/2+γ wheneverys = 1 for s < t, and pt · xs ≤ 1/2 − γ whenever ys = 0 for s < t.
We show that, if there is a weighting p∗ , determined with benefit of hindsight, that achievesnmargin γ on all trials, then this on-line maximum entropy procedure makes at most ln
2γ 2
mistakes.
Littlestone [19] proved the same bound for the Weighted Majority Algorithm [21], and asimilar bound for the Balanced Winnow Algorithm [19]. The original Winnow algorithm
was designed to solve the problem of learning a hidden disjunction of a small number
k out of a possible n boolean variables. When this problem is reduced to our general
setting in the most natural way, the resulting bound is Θ(k 2 log n), whereas Littlestone

proved a bound of ek ln n for Winnow. We prove more refined bounds for a wider familyof maximum-entropy algorithms, which use thresholds different than 1/2 (as proposed in[14]) and class-sensitive margins. A mistake bound of ek ln n for learning disjunctions is aconsequence of this more refined analysis.
The optimization needed at each round can be cast as minimizing a convex function subject
to convex constraints, and thus can be solved in polynomial time [25]. However, the same
mistake bounds hold for a similar, albeit linear-time, algorithm. This algorithm, after eachtrial, replaces all constraints from previous trials with a single linear inequality. (This isanalogous to modification of SVMs leading to the ROMMA algorithm [18].) The resulting
update is similar in form to Winnow.
Littlestone [19] analyzed some variants of Winnow by showing that mistakes cause a reduction in the relative entropy between the learning algorithm’s weight vector, and that of
the target function. Kivinen and Warmuth [16] showed that an algorithm related to Winnow trades optimally in a sense between accommodating the information from new data,
and keeping the relative entropy between the new and old weight vectors small. Blum [4]identified a correspondence between Winnow and a different application of the maximum
entropy principle, in which the algorithm seeks to maximize the average entropy of theconditional distribution over the class designations (the yt ’s) subject to constraints arisingfrom the examples, as proposed in [2]. Our proofs have a similar structure to the analysis
of ROMMA [18]. Our problems fall within the general framework analyzed by Gordon[11]; while Gordon’s results expose interesting relationships among learning algorithms,
applying them did not appear to be the most direct route to solving our concrete problem,
nor did they appear likely to result in the most easily understood proofs. As in related analyses like mistake bounds for the perceptron algorithm [22], Winnow [19] and the Weighted
Majority Algorithm [19], our bound holds for any sequence of (x t , yt ) pairs satisfying theseparation condition; in particular no independence assumptions are needed. Langford,
Seeger and Megiddo [17] performed a related analysis, incomparable in strength, using
independence assumptions. Other related papers include [3, 20, 5, 15, 26, 13, 8, 27, 7].
The proofs of our main results do not contain any calculation; they combine simple geometric arguments with established information theory. The proof of the main result proceeds
roughly as follows. If there is a mistake on trial t, it is corrected with a large margin by
pt+1 . Thus pt+1 must assign a significantly different probability to the voters predicting
1 on trial t than pt does. Applying an identity known as Pinsker’s inequality, this meansthat the relative entropy from pt+1 and pt is large. Next, we exploit the fact that the constraints satisfied by pt , and therefore by pt+1 , are convex to show that moving from pt to
pt+1 must take you away from the uniform distribution, thus decreasing the entropy. The
theorem then follows from the fact that the entropy can only be reduced by a total of ln n.
The refinement leading to a ek ln n bound for disjunctions arises from the observation that
Pinsker’s inequality can be strengthened when the probabilities being compared are small.
The analysis of this paper lends support to a view of Winnow as a fast, incremental approximation to the maximum entropy discrimination approach, and suggests a variant of
Winnow that corresponds more closely to the inductive bias of maximum entropy.

2 Preliminaries

Let n be the number of base classifiers. To avoid clutter, for the rest of the paper, “probability distribution” should be understood to mean “probability distribution over {1, ..., n}.”2.1 Margins
For u ∈ [0, 1], define σ(u) = 1 to be 1 if u ≥ 1/2, and 0 otherwise. For a feature vectorx ∈ {0, 1}n and a class designation y ∈ {0, 1}, say that a probability distribution p iscorrect with margin γ if σ(p · x) = y, and |p · x − 1/2| ≥ γ. If x and y were encounteredin a trial of a learning algorithm, we say that p is correct with margin γ on that trial.
2.2 Entropy, relative entropy, and variation
Recall that, for a probability distributions p = (p1 , ..., pn ) and q = (q1 , ..., qn ),P• the entropy of p, denoted by H(p), is defined by ni=1 pi ln(1/pi ),• thePn relative entropy between p and q, denoted by D(p||q), is defined by
i=1 pi ln(pi /qi ), and• the variation distance between p and q, denoted by V (p, q), is defined to be themaximum difference between the probabilities that they assign to any set:n

1X|pi − qi |.
V (p, q) = max n p · x − q · x =x∈{0,1}2 i=1(1)Relative entropy and variation distance are related in Pinsker’s inequality.
Lemma 1 ([23]) For all p and q, D(p||q) ≥ 2V (p, q)2 .
2.3 Information geometry
Relative entropy obeys something like the Pythogarean Theorem.
Lemma 2 ([9]) Suppose q is a probability distribution, C is a convex set of probability
distributions, and r is the element of A that minimizes D(r||q). Then for any p ∈ C,
D(p||q) ≥ D(p||r) + D(r||q).
If C can be defined by a system of linear equations, thenD(p||q) = D(p||r) + D(r||q).

3 Maximum Entropy with Margin
In this section, we will analyze the algorithm OMEγ (“on-line maximum entropy”) that at
the tth trial• chooses pt to maximize the entropy H(pt ), subject to the constraint that it iscorrect with margin γ on all pairs (xs , ys ) seen in the past (with s < t),• predicts 1 if and only if pt · xt ≥ 1/2.
In our analysis, we will assume that there is always a feasible pt .
The following is our main result.
Theorem 3 If there is a fixed probability distribution p∗ that is correct with margin γ onn
all trials, OMEγ makes at most ln
2γ 2 mistakes.

Proof: We will show that a mistake causes the entropy of the hypothesis to drop by at least2γ 2 . Since the constraints only become more restrictive, the entropy never increases, andso the fact that the entropy lies between 0 and ln n will complete the proof.
Suppose trial t was a mistake. The definition of pt+1 ensures that pt+1 · xt is on the correctside of 1/2 by at least γ. But pt · xt was on the wrong side of 1/2. Thus |pt+1 · xt − pt ·xt | ≥ γ. Either pt+1 · xt − pt · xt ≥ γ, or the bitwise complement c(xt ) of xt satisfies
pt+1 · c(xt ) − pt · c(xt ) ≥ γ. Thus V (pt+1 , pt ) ≥ γ. Therefore, Pinsker’s Inequality(Lemma 1) implies thatD(pt+1 ||pt ) ≥ 2γ 2 .
(2)Let Ct be the set of all probability distributions that satisfy the constraints in effect when
pt was chosen, and let u = (1/n, ..., 1/n). Since pt+1 is in Ct (it must satisfy the constraints that pt did), Lemma 2 implies D(pt+1 ||u) ≥ D(pt+1 ||pt ) + D(pt ||u) and thusD(pt+1 ||u) − D(pt ||u) ≥ D(pt+1 ||pt ) which, since D(p||u) = (ln n) − H(p) for all p,
implies H(pt )−H(pt+1 ) ≥ D(pt+1 ||pt ). Applying (2), we get H(pt )−H(pt+1 ) ≥ 2γ 2 .
As described above, this completes the proof.
Because H(pt ) is always at least H(p∗ ), the same analysis leads to a mistake bound of(ln n − H(p∗ ))/(2γ 2 ). Further, a nearly identical proof establishes the following (details
are omitted from this abstract).
Theorem 4 Suppose OMEγ is modified so that p1 is set to be something other than theuniform distribution, and each pt minimizes D(pt ||p1 ) subject to the same constraints.
If there is a fixed p∗ that is correct with margin γ on all trials, the modified algorithm∗
1)makes at most D(p2γ||pmistakes.
2

4 Maximum Entropy for Learning Disjunctions
In this section, we show how the maximum entropy principle can be used to efficiently
learn disjunctions.
For a threshold b, define σb (x) to be 1 if x ≥ b and 0 otherwise. For a feature vectorx ∈ {0, 1}n and a class designation y ∈ {0, 1}, say that p is correct at threshold b with
margin γ if σb (p · x) = y, and |p · x − b| ≥ γ.
The algorithm OMEb,γ+ ,γ− analyzed in this section, on the tth trial• chooses pt to maximize the entropy H(pt ), subject to the constraint that it iscorrect at threshold b with margin γ+ on all pairs (xs , ys ) with ys = 1 seen in
the past (with s < t), and correct at threshold b with margin γ− on all such pairs(xs , ys ) with ys = 0, then• predicts 1 if and only if pt · xt ≥ b.
Note that the algorithm OMEγ considered in Section 3 can also be called OME1/2,γ,γ .
For p, q ∈ [0, 1], define d(p||q) = D((p, (1−p))||(q, (1−q))), often called “entropic loss.”
Lemma 5 If there is an x ∈ {0, 1}n such that p · x = p and q · x = q, then D(p||q) ≥d(p||q).
Proof: Application of Lagrange multipliers, together with the fact that D is convex [6],implies that D(p||q) is minimized, subject to the constraints that p · x = p and q · x = q,
when (1) pi is the same for all i with xi = 1, (2) qi is the same for all i with xi = 1,
(3) pi is the same for all i with xi = 0, (4) qi is the same for all i with xi = 0. The

above four properties, together with the constraints, are enough to uniquely specify p andq. Evaluating D(p||q) in this case gives the result.
Theorem 6 Suppose there is a probability distribution p∗ that is correct at threshold b,
with a margin γ+ on all trials t with yt = 1, and with margin γ− on all trials with yt = 0.
nThen OMEb,γ+ ,γ− makes at most min{d(b+γ+ln||b),d(b−γ− ||b)} mistakes.
Proof: The outline of the proof is similar to the proof of Theorem 3. We will show that
mistakes cause the entropy of the algorithm’s hypothesis to decrease.
Arguing as in the proof of Theorem 3, H(pt+1 ) ≤ H(pt ) − D(pt+1 ||pt ). Lemma 5 thenimplies thatH(pt+1 ) ≤ H(pt ) − d(pt+1 · xt ||pt · xt ).
(3)
If there was a mistake on trial t for which yt = 1, then pt · xt ≤ b, and pt+1 · xt ≥ b + γ+ .
Thus in this case d(pt+1 · xt ||pt · xt ) ≥ d(b + γ+ ||b). Similarly, if there was a mistakeon trial t for which yt = 0, then d(pt+1 · xt ||pt · xt ) ≥ d(b − γ− ||b).
Once again, these two bounds on d(pt+1 · xt ||pt · xt ), together with (3) and the fact thatthe entropy is between 0 and ln n, complete the proof.
The analysis of Theorem 6 can also be used to prove bounds for the case in which mistakesof different types have different costs, as considered in [12].
Theorem 6 improves on Theorem 3 even in the case in which γ + = γ− and b = 1/2. For
example, if γ = 1/4, Theorem 6 gives a bound of 7.65 ln n, where Theorem 3 gives an
8 ln n bound.
Next, we apply Theorem 6 to analyze the problem of learning disjunctions.
Corollary 7 If there are k of the n features, such that each yt is the disjunction of thosefeatures in xt , then algorithm OME1/(ek),1/k−1/(ek),1/(ek) makes at most ek ln n mistakes.
Proof Sketch: If the target weight vector p∗ assigns equal weight to each of the variablesin the disjunction, when y = 1, the weight of variables evaluating to 1 is at least 1/k,
and when y = 0, it is 0. So the hypothesis of Theorem 6 is satisfied when b = 1/(ek),γ+ = 1/k − b and γ− = b. Plugging into Theorem 6, simplifying and overapproximatingcompletes the proof.
To get a more readable, but weaker, variant of Theorem 6, we will use the following bound,
implicit in the analysis of Angluin and Valiant [1] (see Theorem 1.1 of [10] for a more
explicit proof, and [24] for a closely related bound). It improves on Pinsker’s inequality(Lemma 1) when n = 2, p is small, and q is close to p.
2

Lemma 8 ([1]) If 0 ≤ p ≤ 2q, d(p||q) ≥ (p−q)
3q .
The following is a direct consequence of Lemma 8 and Theorem 6. Note that in the case of
disjunctions, it leads to a weaker 6k ln n bound.
Theorem 9 If there is a probability distribution p∗ that is correct at threshold b with amargin γ on all trials, then OMEb,γ,γ makes at most 3bγln2 n mistakes.

5 Relaxed on-line maximum entropy algorithms
Let us refer the halfspace of probability distributions that satisfy the constraint of trial t
as Tt and the associated separating hyperplane by Jt . Recall that Ct is the set of feasible

Figure 1: In ROME, the constraints Ct in effect before the tth round are replaced by thehalfspace St .
solutions to all the constraints in effect when pt is chosen. So pt+1 maximizes entropy
subject to membership in Ct+1 = Tt ∩ Ct .
Our proofs only used the following facts about the OME algorithm: (a) p t+1 ∈ Tt , (b) pt
is the maximum entropy member of Ct , and (c) pt+1 ∈ Ct .
Suppose At is the set of weight vectors with entropy at last that of pt . Let Ht be thehyperplane tangent to At at pt . Finally, let St be the halfspace with boundary Ht containing
pt+1 . (See Figure 1.) Then (a), (b) and (c) hold if Ct is replaced with St . (The least obvious
is (b), which follows since Ht is tangent to At at pt , and the entropy function is strictly
concave.)Also, as previously observed by Littlestone [19], the algorithm might just as well not respond to trials in which there is not a mistake. Let us refer to an algorithm that does bothof these as a Relaxed On-line Maximum Entropy (ROME) algorithm.
A similar observation regarding an on-line SVM algorithm, led to the simple ROMMA
algorithm [18]. In that case, it was possible to obtain a simple close-form expression for
the new weight vector. Matters are only slightly more complicated here.
Proposition 10 If trial t is a mistake, and q maximizes entropy subject to membership in
St ∩ Tt , then it is on the separating hyperplane for Tt .
Proof: Because q and p both satisfy St , any convex combination of the two satisfies St .
Thus, if q was on the interior of Tt , we could find a probability distribution with higher
entropy that still satisfies both St and Tt by taking a tiny step from q toward p. This would
contradict the assumption that q is the maximum entropy member of S t ∩ Tt .
This implies that the next hypothesis of a ROME algorithm is either on Jt (the separating
hyperplane Tt ) only, or on both Jt and Ht (the separating hyperplane of St ). The following
theorem will enable us to obtain a formula in either case.
Lemma 11 ([9] (Theorem 3.1)) Suppose q is a probability distribution, and C is a set defined by linear constraints as follows: for an m × n real matrix A, and a m-dimensional

column vector b, C = {r : Ar = b}. Then if r is the member of C minimizing
D(r||q), thenPm there are scalar constants Z, c1 , ..., cm such that for all i ∈ {1, ..., n},ri = exp( j=1 cj aj,i )qi /Z.

If the next hypothesis pt+1 of a ROME algorithm is on Ht , then by Lemma 2, it and allother members of Ht satisfy D(pt+1 ||u) = D(pt+1 ||pt ) + D(pt ||u). Thus, in this case,pt+1 also minimizes D(q||pt ) from among the members q of Ht ∩ Jt . Thus, Lemma 11
implies that pt+1,i /pt,i is the same for all i with xi = 1, and the same for all i with xi = 0.
This implies that, for ROMEb,γ+ ,γ− , if there was a mistake on a trial t, (b+γ )p+t,i
if xt,i = 1 and yt = 1

pt ·xt (1−(b+γ+ ))pt,i if x = 0 and y = 1t,it
1−(pt ·xt )(4)
pt+1,i =(b−γ− )pt,i

if
x
=
1
and
y
t,i
t =0

pt ·xt (1−(b−γ+ ))pt,i if x = 0 and y = 0.
t,it1−(pt ·xt )Note that this updates the weights multiplicatively, like Winnow and Weighted Majority.

If pt+1 is not on the separating hyperplane for St , then it must maximize entropy subject tomembership in Tt alone, and therefore subject to membership in Jt . In this case, Lemma 11
implies (b+γ )+
if xt,i = 1 and yt = 1
|{j:xt,j =1}| (1−(b+γ+ )) if xt,i = 0 and yt = 1|{j:xt,j =0}|.
pt+1,i =(5)(b−γ+ )
if xt,i = 1 and yt = 0
|{j:xt,j =1}| (1−(b−γ+ )) if x = 0 and y = 0t,it|{j:xt,j =0}|.
If this is the case, then pt+1 defined as in (5) should be a member of St .

How to test for membership in St ? Evaluating the gradient of H at pt , and simplifying a
bit, we can see that
(
)
n
X
1
St = q :qi ln≤ H(p) .
pt,i
i=1
Summing up, a way to implement a ROME algorithm with the same mistake bound as thecorresponding OME algorithm is to• try defining pt+1 as in (5), and check whether the resulting pt+1 ∈ St , if so use
it, and• if not, then define pt+1 as in (4) instead.

Acknowledgements
We are grateful to Tony Jebara and Tong Zhang for helpful conversations, and an anonymous referee for suggesting a simplification of the proof of Theorem 3.

References[1] D. Angluin and L. Valiant. Fast probabilistic algorithms for Hamiltonion circuits andmatchings. Journal of Computer and System Sciences, 18(2):155–193, 1979.
[2] A. L. Berger, S. Della Pietra, and V. J. Della Pietra. A maximum entropy approach tonatural language processing. Computational Linguistics, 22(1):39–71, 1996.

[3] D. Blackwell. An analog of the minimax theorem for vector payoffs. Pac. J. Math.,
6:1–8, 1956.
[4] A. Blum, 2002. http://www-2.cs.cmu.edu/∼avrim/ML02/lect0418.txt.
[5] N. Cesa-Bianchi, A. Krogh, and M. Warmuth. Bounds on approximate steepest descent for likelihood maximization in exponential families. IEEE Transactions on
Information Theory, 40(4):1215–1218, 1994.
[6] T. Cover and J. Thomas. Elements of Information Theory. Wiley, 1991.
[7] K. Crammer, O. Dekel, S. Shalev-Shwartz, and Y. Singer. Online passive-aggressivealgorithms. NIPS, 2003.
[8] Koby Crammer and Yoram Singer. Ultraconservative online algorithms for multiclassproblems. In COLT, pages 99–115, 2001.
[9] I. Csiszár. I-divergence geometry of probability distributions and minimization problems. Annals of Probability, 3:146–158, 1975.
[10] D. P. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms, 1998. Monograph.
[11] Geoffrey J. Gordon. Regret bounds for prediction problems. In Proc. 12th Annu.
Conf. on Comput. Learning Theory, pages 29–40. ACM Press, New York, NY, 1999.
[12] D. P. Helmbold, N. Littlestone, and P. M. Long. On-line learning with linear loss
constraints. Information and Computation, 161(2):140–171, 2000.
[13] M. Herbster and M. K. Warmuth. Tracking the best linear predictor. Journal of
Machine Learning Research, 1:281–309, 2001.
[14] T. Jaakkola, M. Meila, and T. Jebara. Maximum entropy discrimination. NIPS, 1999.
[15] J. Kivinen and M. Warmuth. Boosting as entropy projection. COLT, 1999.
[16] J. Kivinen and M. K. Warmuth. Additive versus exponentiated gradient updates forlinear prediction. Information and Computation, 132(1):1–63, 1997.
[17] J. Langford, M. Seeger, and N. Megiddo. An improved predictive accuracy bound for
averaging classifiers. ICML, pages 290–297, 2001.
[18] Y. Li and P. M. Long. The relaxed online maximum margin algorithm. Machine
Learning, 46(1-3):361–387, 2002.
[19] N. Littlestone. Mistake Bounds and Logarithmic Linear-threshold Learning Algorithms. PhD thesis, UC Santa Cruz, 1989.
[20] N. Littlestone, P. M. Long, and M. K. Warmuth. On-line learning of linear functions.
Computational Complexity, 5:1–23, 1995. Preliminary version in STOC’91.
[21] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information
and Computation, 108:212–261, 1994.
[22] A. B. J. Novikoff. On convergence proofs on perceptrons. In Proceedings of the
Symposium on the Mathematical Theory of Automata, pages 615–622, 1962.
[23] M. S. Pinsker. Information and Information Stability of Random Variables and Processes. Holden-Day, 1964.
[24] F. Topsoe. Some inequalities for information divergence and related measures of
discrimination. IEEE Trans. Inform. Theory, 46(4):1602–1609, 2001.
[25] P. Vaidya. A new algorithm for minimizing convex functions over convex sets. FOCS,
pages 338–343, 1989.
[26] T. Zhang. Regularized winnow methods. NIPS, pages 703–709, 2000.
[27] T. Zhang. A sequential approximation bound for some sample-dependent convex
optimization problems with applications in learning. COLT, pages 65–81, 2001.