|
NeuroCOLT
Technical Report NC-TR-94-020
Efficient Agnostic
PAC-Learning with Simple Hypotheses
Wolfgang
Maass
Institute for Theoretical Computer Science
Technische Universitaet Graz
Klosterwiesgasse 32/2
A-8010 Graz
Austria
Abstract
We exhibit efficient algorithms for agnostic PAC-learning with rectangles,
unions of two rectangles, and unions of $k$ intervals as hypotheses.
These hypothesis classes are of some interest from the point of view
of applied machine learning, because empirical studies show that hypotheses
of this simple type (in just one or two of the attributes) provide
good prediction rules for various real-world classification problems.
In addition, optimal hypotheses of this type may provide valuable
heuristic insight into the structure of a real-world classification
problem. The algorithms that are introduced in this paper make
it feasible to compute optimal hypotheses of this type for a training
set of several hundred examples. We also exhibit an approximation
algorithm that can compute near optimal hypotheses for much larger
datasets.
Download Compressed
Postscript
|