PAC-Learning from General Examples

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

View graph of relations

We study a novel view on the PAC learning model in which the examples are more complicated than in the standard model. There, an example usually is an element of the learning domain and its label indicates whether it belongs to the target concept. Here, the examples can be subsets and their labels indicate some relation to the target concept, e.g., whether they intersect it or not. We show how this setting can be easily transformed into the standard PAC model; however, for an analysis it is much more natural to stick to the original formulation. Then the central notion is that of the relative dimension of a target class with respect to a sample class, which replaces the Vapnik-Chervonenkis dimension (V.N. Vapnik and A.Y. Chervonenkis, 1971). The investigation of structural aspects of the relative dimension is followed by its applications to learning environments. It turns out that computing or bounding the relative dimension leads to interesting combinatorial problems even for simple target and sample classes. Sometimes the analysis is easier if one represents the concepts as unions or intersections of simpler ones. We present sharp bounds on the relative and the Vapnik-Chervonenkis dimension of the complicated class in terms of the simpler one
Original languageEnglish
JournalTheoretical Computer Science
Publication date1997
Volume172
Journal number1-2
Pages43-65
ISSN0304-3975
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: 2701473