home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / doc / techrepo / 229 < prev    next >
Encoding:
Internet Message Format  |  1993-01-05  |  3.1 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!howland.reston.ans.net!usc!cs.utexas.edu!sun-barr!olivea!hal.com!darkstar.UCSC.EDU!golding
  2. From: jean@cse.ucsc.edu (Jean McKnight)
  3. Newsgroups: comp.doc.techreports
  4. Subject: UCSC TR:  On Weak Learning
  5. Message-ID: <1ic5atINNkav@darkstar.UCSC.EDU>
  6. Date: 5 Jan 93 14:18:05 GMT
  7. Organization: University of California, Santa Cruz (CE/CIS Boards)
  8. Lines: 57
  9. Approved: compdoc-techreports@ftp.cse.ucsc.edu
  10. NNTP-Posting-Host: oak.ucsc.edu
  11. Originator: golding@oak
  12.  
  13.  
  14.           University of California at Santa Cruz
  15. Baskin Center for Computer Engineering and Information Sciences 
  16.  
  17. The following technical report is available electronically or as
  18. a paper copy.  Instructions for getting either follow the abstract.
  19.  
  20.  
  21. UCSC-CRL-92-54  (available electronically as ucsc-crl-92-54.ps.Z)
  22. ON WEAK LEARNING
  23. David P. Helmbold and Manfred K. Warmuth
  24. December 1992, 37 pages ($7.00)
  25.  
  26. Abstract:  An algorithm is a weak learning algorithm if with some
  27. small probability it outputs a hypothesis with error slightly below
  28. 50%.  This paper presents relationships between weak learning, weak
  29. prediction (where the probability of being correct is slightly larger 
  30. than 50%), and consistency oracles (which decide whether or not a given 
  31. set of examples is consistent with a concept in the class).  Our main 
  32. result is a simple polynomial prediction algorithm which makes only a 
  33. single query to a consistency oracle and whose predictions have a 
  34. polynomial edge over random guessing.  We compare this prediction
  35. algorithm with several of the standard prediction techniques, deriving
  36. an improved worst case bound on Gibbs Algorithm in the process.  We use 
  37. our algorithm to show that a concept class is polynomially learnable if 
  38. and only if there is a polynomial probabilistic consistency oracle for 
  39. the class.  Since strong learning algorithms can be built from weak 
  40. learning algorithms, our results also characterizes strong learnability.
  41.  
  42.  
  43. This technical report is available electronically through either 
  44. of the following methods:
  45. 1.  through anonymous ftp from ftp.cse.ucsc.edu, in /pub/tr. Log in 
  46.     as "anonymous", use your email address as your password, specify 
  47.     "binary" before getting the file.  Uncompress before printing.
  48. 2.  by mail to automatic mail server rnalib@ftp.cse.ucsc.edu.
  49.     Put this command on the subject line or in the body of the message:
  50.     @@ send ucsc-crl-92-54.ps.Z from tr
  51.     To get the index or abstract list:
  52.     @@ send INDEX from tr
  53.     @@ send ABSTRACTS.1992 from tr
  54.     To get the list of the tr directory:
  55.     @@ list tr
  56.     To get the list of commands and their syntax:
  57.     @@ help commands
  58.  
  59. Order paper copies from:  Technical Library, Baskin Center for Computer 
  60. Engineering & Information Sciences, UCSC, Santa Cruz  CA  95064.
  61. Purchase orders are not accepted.  Checks or money orders must be
  62. for U.S. dollars, payable through a U.S. bank, and made out to 
  63. "UC Regents".
  64.  
  65. Questions:  jean@cse.ucsc.edu
  66.  
  67. ===========================================================================
  68. Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
  69.         compdoc-techreports-request@ftp.cse.ucsc.edu
  70.