🚀 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-92-54  (available electronically as ucsc-crl-92-54.ps.Z)
ON WEAK LEARNING
David P. Helmbold and Manfred K. Warmuth
December 1992, 37 pages ($7.00)

Abstract:  An algorithm is a weak learning algorithm if with some
small probability it outputs a hypothesis with error slightly below
50%.  This paper presents relationships between weak learning, weak
prediction (where the probability of being correct is slightly larger 
than 50%), and consistency oracles (which decide whether or not a given 
set of examples is consistent with a concept in the class).  Our main 
result is a simple polynomial prediction algorithm which makes only a 
single query to a consistency oracle and whose predictions have a 
polynomial edge over random guessing.  We compare this prediction
algorithm with several of the standard prediction techniques, deriving
an improved worst case bound on Gibbs Algorithm in the process.  We use 
our algorithm to show that a concept class is polynomially learnable if 
and only if there is a polynomial probabilistic consistency oracle for 
the class.  Since strong learning algorithms can be built from weak 
learning algorithms, our results also characterizes strong learnability.


This technical report is available electronically through either 
of the following methods:
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-92-54.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 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