🚀 go-pugleaf

          University of California at Santa Cruz
  Baskin Center for Computer Engineering and Information Sciences 

The following technical report is available electronically or as
a paper copy.  Instructions for getting either follow the abstract.

UCSC-CRL-91-28  (available electronically as ucsc-crl-91-28.ps.Z)
THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16)
Nick Littlestone and Manfred K. Warmuth
October 1991, revised October 26, 1992, 35 pages (paper copy $7.00)

Abstract:  We study the construction of prediction algorithms in a
situation in which a learner faces a sequence of trials, with a
prediction to be made in each, and the goal of the learner is to make
few mistakes.  We are interested in the case that the learner has
reason to believe that one of some pool of known algorithms will
perform well, but the learner does not know which one.  A simple and
effective method, based on weighted voting, is introduced for
constructing a compound algorithm in such a circumstance.  We call this
method the Weighted Majority Algorithm.  We show that this algorithm is
robust in the presence of errors in the data. We discuss various versions
of the Weighted Majority Algorithm and prove mistake bounds for them
that are closely related to the mistake bounds of the best algorithms
of the pool.  For example, given a sequence of trials, if there is an
algorithm in the pool A that makes at most m mistakes then the Weighted
Majority Algorithm will make at most c(log |A| + m) mistakes on that
sequence, where  c  is fixed constant.
Keywords:  Prediction, mistake, mistake bounds, weighted majority,
absolute loss, on-line learning algorithm.


This technical report is available electronically through either 
of the following methods:  (There are 4 pages of diagrams not in the
postscript file - request trs@cse.ucsc.edu to send you paper copies
of these diagrams by regular mail.)

1.  through anonymous ftp from ftp.cse.ucsc.edu, in /pub/tr. Log in 
    as "anonymous", use your email address as your password, specify 
    "binary" before getting the file.  Uncompress before printing.
2.  by mail to automatic mail server rnalib@ftp.cse.ucsc.edu.
    Put this command on the subject line or in the body of the message:
    	@@ send ucsc-crl-91-28.ps.Z from tr
    To get the index or abstract list:
	@@ send INDEX from tr
	@@ send ABSTRACTS.1992 from tr
    To get the list of the tr directory:
	@@ list tr
    To get the list of commands and their syntax:
	@@ help commands

Order paper copies of entire tech report from:  Technical Library, 
Baskin Center for Computer Engineering & Information Sciences, UCSC, 
Santa Cruz  CA  95064.  Purchase orders are not accepted.  
Checks or money orders must be for U.S. dollars, payable through 
a U.S. bank, and made out to "UC Regents".

Questions:  jean@cse.ucsc.edu


===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu