PAC-Learning from General Examples

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