Predicting (0, 1)-functions on randomly drawn points
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 100-109
- https://doi.org/10.1109/sfcs.1988.21928
Abstract
The authors consider the problem of predicting (0, 1)-valued functions on R/sup n/ and smaller domains, based on their values on randomly drawn points. Their model is related to L.G. Valiant's learnability model (1984), but does not require the hypotheses used for prediction to be represented in any specified form. The authors first disregard computational complexity and show how to construct prediction strategies that are optimal to within a constant factor for any reasonable class F of target functions. These prediction strategies use the 1-inclusion graph structure from N. Alon et al.'s work on geometric range queries (1987) to minimize the probability of incorrect prediction. They then turn to computationally efficient algorithms. For indicator functions of axis-parallel rectangles and halfspaces in R/sup n/, they demonstrate how their techniques can be applied to construct computational efficient prediction strategies that are optimal to within a constant factor. They compare the general performance of prediction strategies derived by their method to those derived from existing methods in Valiant's learnability theory.Keywords
This publication has 20 references indexed in Scilit:
- Equivalence of models for polynomial learnabilityInformation and Computation, 1991
- A general lower bound on the number of examples needed for learningInformation and Computation, 1989
- Learning decision trees from random examplesInformation and Computation, 1989
- Learning quickly when irrelevant attributes abound: A new linear-threshold algorithmMachine Learning, 1988
- Implicitly representing arrangements of lines or segmentsPublished by Association for Computing Machinery (ACM) ,1988
- Reductions among prediction problems: on the difficulty of predicting automataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- ɛ-nets and simplex range queriesDiscrete & Computational Geometry, 1987
- Occam's RazorInformation Processing Letters, 1987
- On the learnability of Boolean formulaePublished by Association for Computing Machinery (ACM) ,1987
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984