Deepak Chawla, Lin Li, and Stephen D. Scott. Efficiently approximating weighted sums with exponentially many terms. In Proceedings of the Fourteenth Annual Conference on Computational Learning Theory, pages 82–98, Trippenhuis, Amsterdam, the Netherlands, July 2001.
Abstract

Abstract

We explore applications of Markov chain Monte Carlo methods for weight estimation over inputs to the Weighted Majority (WM) and Winnow algorithms. This is useful when there are exponentially many such inputs and no apparent means to efficiently compute their weighted sum. The applications we examine are pruning classifier ensembles using WM and learning general DNF formulas using Winnow. These uses require exponentially many inputs, so we define Markov chains over the inputs to approximate the weighted sums. We state performance guarantees for our algorithms and present preliminary empirical results.

To Stephen D. Scott's home page

Last modified 23 May 2001.