Trial and Error: A new Approach to Space-Bounded Learning

Publication: Research - peer-reviewJournal article – Annual report year: 1996

View graph of relations

A pac-learning algorithm is d-space bounded, if it stores at most d examples from the sample at any time. We characterize the d-space learnable concept classes. For this purpose we introduce the compression parameter of a concept class 𝒞 and design our trial and error learning algorithm. We show: 𝒞 is d-space learnable if and only if the compression parameter of 𝒞 is at most d. This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches, for example, by Floyd, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes: all intersection closed concept classes with finite VC-dimension; convex n-gons in R/sup 2/ ; halfspaces in R/sup n/ ; unions of triangles in R/sup 2/ . We further relate the compression parameter to the VC-dimension, and discuss variants of this parameter
Original languageEnglish
JournalActa Informatica
Publication date1996
Volume33
Issue7
Pages621-631
ISSN0001-5903
StatePublished
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 2701019