Efficient agnostic PAC-learning with simple hypothesis
Published 1 January 1994Open access
Wolfgang Maass
Citations54
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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, and an approximation algorithm is exhibited that can compute nearly optimal hypotheses for much larger datasets.
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.
Keywords
Computer Science
Programs for Machine Learning
5,794 Citations1994Steven L. Salzberg, Alberto M. Segre
In his new book, C4.5: Programs for Machine Learning, Quinlan has put together a definitive, much needed description of his complete system, including the latest developments, which will be a welcome addition to the library of many researchers and students.
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Computational geometry. an introduction
2,369 Citations1985Franco P. Preparata, Michael Ian Shamos
Machine LearningVery Simple Classification Rules Perform Well on Most Commonly Used Datasets
1,798 Citations1993Robert C. Holte
On most datasets studied, the best of very simple rules that classify examples on the basis of a single attribute is as accurate as the rules induced by the majority of machine learning systems.
Information and ComputationDecision theoretic generalizations of the PAC model for neural net and other learning applications
871 Citations1992David Haussler
Theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H are given, and it is shown how this implies learnability with bounded sample size, disregarding computational complexity.
Machine LearningLearning From Noisy Examples
667 Citations1988Dana Angluin, Philip Laird
This paper shows that when the teacher may make independent random errors in classifying the example data, the strategy of selecting the most consistent rule for the sample is sufficient, and usually requires a feasibly small number of examples, provided noise affects less than half the examples on average.
Machine LearningAn Empirical Comparison of Pruning Methods for Decision Tree Induction
631 Citations1989John Mingers
This paper compares five methods for pruning decision trees, developed from sets of examples, and shows that three methods—critical value, error complexity and reduced error—perform well, while the other two may cause problems.
An empirical comparison of pattern recognition, neural nets, and machine learning classification methods
470 Citations1989Sholom M. Weiss, Ioannis Kapouleas
For these problems, which have relatively few hypotheses and features, the machine learning procedures for rule induction or tree induction clearly performed best.
SIAM Journal on ComputingLearning in the Presence of Malicious Errors
350 Citations1993Michael Kearns, Ming Li
Toward efficient agnostic learning
347 Citations1992Michael Kearns, Robert E. Schapire +1 more
Machine LearningA Further Comparison of Splitting Rules for Decision-Tree Induction
220 Citations1992Wray Buntine, Tim Niblett
The results indicate that random splitting leads to increased error and are at variance with those presented by Mingers.
Artificial IntelligenceMaximizing the predictive value of production rules
71 Citations1990Sholom M. Weiss, Robert S. Galen +1 more
P predictive value maximization (PVM), a heuristic search procedure through the hypothesis space of conjunctions and disjunctions of variables and their cutoff values, is outlined, where the goal is to find the best combination of tests for making a diagnosis.
Statistical queries and faulty PAC oracles
53 Citations1993Scott E. Decatur
This paper shows that efficient learning with statistical queries is sufficient for learning in the PAC model with malicious error rate proportional to the required statistical query accuracy, and develops a new lower bound for tolerable malicious error in learning monomials of k literals.
Robust trainability of single neurons
47 Citations1992Klaus-Uwe Höffgen, Hans Ulrich Simon
It is shown that a neuron cannot efficently find its probably almost optimal adjustment (unless RP = NP) and neither heuristical learning nor learning by sigmoidal neurons with a constant reject-rate is efficiently possible.
Computing the rectangle discrepancy
12 Citations1994David Dobkin, Dimitrios Gunopulos
This is the animation of an algorithm that computes the rectangle discrepancy of a two-dimensional point set using supersampling, one of the most general ways of attacking antialiasing.