P. M. Long and X. Wu.
Mistake bounds for maximum entropy discrimination. NIPS*04.
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 variants
of 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, which
takes a similar form to Winnow, achieves the same mistake bounds.
Related paper
Since we published our paper,
Yoram Singer
told us about the following related paper.
H.H. Bauschke
and P.L. Combettes. A
weak-to-strong convergence principle for Fejer-monotone Methods in
Hilbert spaces. Mathematics of Operations Research 26(2),
pp. 248-264, 2001.
That paper includes a description of a framework in the following
thesis:
Y. Haugazeau. Sur les inéquations variationnelles et la minimisation
de fonctionnelles convexes. Thèse, Université de Paris, 1968.
The ROME algorithm described in Section 5 of our paper is a special
case of this framework.