Occam's two razors: the sharp and the blunt
Knowledge Discovery and Data MiningPublished 27 August 1998
Pedro Domingos
Citations73
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 balance is strongly against Occam's razor, and a version of the first razor more appropriate to KDD is proposed, and it is argued that continuing to apply the second razor risks causing significant opportunities to be missed.
Abstract
Occam's razor has been the subject of much controversy. This paper argues that this is partly because it has been interpreted in two quite different ways, the first of which (simplicity is a goal in itself) is essentially correct, while the (simplicity leads to greater accuracy) is not. The paper reviews the large variety of theoretical arguments and empirical evidence for and against the second razor, and concludes that the balance is strongly against it. In particular, it builds on the case of (Schaffer, 1993) and (Webb, 1996) by considering additional theoretical arguments and recent empirical evidence that the razor fails in most domains. A version of the first razor more appropriate to KDD is proposed, and we argue that continuing to apply the razor risks causing significant opportunities to be missed.
Keywords
NeuroscienceArts and Humanities
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
Elements of Information Theory
37,533 Citations2001Thomas M. Cover, Joy A. Thomas
Choice Reviews OnlineNeural networks for pattern recognition
18,687 Citations1994
This is the first comprehensive treatment of feed-forward neural networks from the perspective of statistical pattern recognition, and is designed as a text, with over 100 exercises, to benefit anyone involved in the fields of neural computation and pattern recognition.
AutomaticaModeling by shortest data description
5,944 Citations1978J. Rissanen
The number of digits it takes to write down an observed sequence x1,...,xN of a time series depends on the model with its parameters that one assumes to have generated the observed data.
Neural ComputationBayesian Interpolation
4,377 Citations1992David Mackay
The Bayesian approach to regularization and model-comparison is demonstrated by studying the inference problem of interpolating noisy data by examining the posterior probability distribution of regularizing constants and noise levels.
Machine LearningOn the Optimality of the Simple Bayesian Classifier under Zero-One Loss
3,072 Citations1997Pedro Domingos, Michael J. Pazzani
The Bayesian classifier is shown to be optimal for learning conjunctions and disjunctions, even though they violate the independence assumption, and will often outperform more powerful classifiers for common training set sizes and numbers of attributes, even if its bias is a priori much less appropriate to the domain.
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.
Neural ComputationThe Lack of A Priori Distinctions Between Learning Algorithms
1,646 Citations1996David H. Wolpert
It is shown that one cannot say: if empirical misclassification rate is low, the Vapnik-Chervonenkis dimension of your generalizer is small, and the training set is large, then with high probability your OTS error is small.
National Conference on Artificial IntelligenceBagging, boosting, and C4.S
1,262 Citations1996J. R. Quinlan
Information Processing LettersOccam's Razor
1,077 Citations1987Anselm Blumer, Andrzej Ehrenfeucht +2 more
It is shown that a polynomial learning algorithm, as defined by Valiant (1984), is obtained whenever there exists aPolynomial-time method of producing, for any sequence of observations, a nearly minimum hypothesis that is consistent with these observations.
Data Mining and Knowledge DiscoveryOn Bias, Variance, 0/1—Loss, and the Curse-of-Dimensionality
1,029 Citations1997Jerome H. Friedman
This work candramatically mitigate the effect of the bias associated with some simpleestimators like “naive” Bayes, and the bias induced by the curse-of-dimensionality on nearest-neighbor procedures.
The Computer JournalAn Information Measure for Classification
947 Citations1968Christopher S. Wallace, D. M. Boulton
It is suggested that the best classification is that which results in the briefest recording of all the attribute information, and the measurements of each thing are regarded as being a message about that thing.
Information and ComputationInferring decision trees using the minimum description lenght principle
665 Citations1989J. R. Quinlan, Ronald L. Rivest
The use of Rissanen's minimum description length principle for the construction of decision trees is explored and empirical results comparing this approach to other methods are given.
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.
Springer series in statisticsA Bayesian Analysis of the Minimum AIC Procedure
558 Citations1998Hirotugu Akaike
Artificial IntelligenceQuantifying inductive bias: AI learning algorithms and Valiant's learning framework
499 Citations1988David Haussler
It is shown that the notion of inductive bias in concept learning can be quantified in a way that directly relates to learning performance in the framework recently introduced by Valiant.
Elsevier eBooksA Conservation Law for Generalization Performance
341 Citations1994Cullen Schaffer
A proof of a basic mathematical result stating that positive performance in some learning situations must be offset by an equal degree of negative performance in others is presented.
Machine LearningEfficient Approximations for the Marginal Likelihood of Bayesian Networks with Hidden Variables
297 Citations1997David Maxwell Chickering, David Heckerman
Bayesian methods for model averaging and model selection among Bayesian-network models with hidden variables, and large-sample approximations for the marginal likelihood of naive-Bayes models in which the root node is hidden are examined.
Journal of ComplexityLearning from hints in neural networks
243 Citations1990Yaser S. Abu‐Mostafa
A method for incorporating any invariance hint about ƒ in any descent method for learning from examples is introduced and it is shown that learning in a neural network remains NP-complete with a certain, biologically plausible, hint about the network.
Lessons in neural network training: overfitting may be harder than expected
237 Citations1997Steve Lawrence, C. Lee Giles +1 more
The convergence of the backpropagation (BP) algorithm is investigated, and it is found that the optimal solution is typically not found, and networks larger than might be expected can result in lower training and generalization error.
Minds at UW (University of Wisconsin)Extracting comprehensible models from trained neural networks
234 Citations1996Mark Craven, Jude Shavlik
An algorithm, called Trepan, is an algorithm that overcomes the significant limitations of previous methods by taking a novel approach to the task of extracting comprehensible models from trained neural networks, and provides an appealing combination of strengths.
Machine LearningOverfitting Avoidance as Bias
228 Citations1993Cullen Schaffer
Overfitting avoidance strategies are not better or worse, but only more or less appropriate to specific application domains, suggesting that, as a research community, the authors are not making progress toward developing powerful, general methods for guarding against overfitting in inducing decision trees.
Machine LearningUnifying Instance-Based and Rule-Based Induction
218 Citations1996Pedro Domingos
In an extensive empirical study, RISE consistently achieves higher accuracies than state-of-the-art representatives of both its parent approaches, as well as a decision tree learner (C4.5).
Artificial IntelligenceTheory refinement combining analytical and empirical methods
158 Citations1994Dirk Ourston, Raymond J. Mooney
A comprehensive system for automatic theory (knowledge base) refinement combining analytical and empirical methods that applies to classification tasks employing a propositional Hornclause domain theory.
Oversearching and layered search in empirical learning
120 Citations1995J. R. Quinlan, R. M. Cameron-Jones
This work proposes an iterated search method that commences with greedy search extending its scope at each Iteration until a stopping criterion is satisfied, and is often found to produce theories that are more accurate than those obtained with either greedy search or moderately, extensive beam search.
Journal of Artificial Intelligence ResearchFurther Experimental Evidence against the Utility of Occam's Razor
110 Citations1996Geoffrey I. Webb
A systematic procedure derived by rejecting Occam's razor and instead attending to the assumption that similar objects are likely to belong to the same class increases a decision tree's complexity without altering the performance of that tree on the training data from which it is inferred.
[1990] Proceedings of the 2nd International IEEE Conference on Tools for Artificial IntelligenceRL4: a tool for knowledge-based induction
99 Citations2002Scott H. Clearwater, Foster Provost
The induction program RL4 is used as an induction tool, and several examples of its past and present uses are presented, and the directions in which RL4 can go in the future are considered.
International Journal of General SystemsON THE CONNECTION BETWEEN THE COMPLEXITY AND CREDIBILITY OF INFERRED MODELS
97 Citations1978Judea Pearl
This paper derives formal relationships between n, c and the probability of ambiguous predictions by examining three modeling languages under binary classification tasks: perceptrons, Boolean formulae, and Boolean networks.
Lookahead and pathology in decision tree induction
92 Citations1995Sreerama K. Murthy, Steven L. Salzberg
An alternative approach in which the algorithms use one-level lookahead to decide what test to use at a node is studied, which consistently produced trees that were just as at accurate as trees produced with the much more expensive lookahead step.
Why does bagging work? a Bayesian account and its implications
90 Citations1997Pedro Domingos
This paper empirically test two alternative explanations for why bagging works: it is an approximation to the optimal procedure of Bayesian model averaging, with an appropriate implicit prior, and it effectively shifts the prior to a more appropriate region of model space.
Elsevier eBooksUsing Qualitative Models to Guide Inductive Learning
64 Citations1993Peter E. Clark, Stan Matwin
Surprisingly, in addition to achieving explainability the classificational accuracy of the induced rules is also increased and the value of the qualitative models can be quantified in terms of their equivalence to additional training examples.
Elsevier eBooksFor Every Generalization Action, Is There Really an Equal and Opposite Reaction? Analysis of the Conservation Law for Generalization Performance
59 Citations1995R. Bharat Rao, Diana F. Gordon +1 more
An improved vehicle rear-view mirror assembly of the type in which the mirror support arm is carried by means of at least one movable joint from the mounting part of the mirror assembly which is adapted to be secured to the bodywork of the vehicle includes a shroud of a resilient and flexible material mounted on the back of the Mirror.
Elsevier eBooksConcept Simplification and Prediction Accuracy
53 Citations1988Douglas Fisher, Jeffrey C. Schlimmer
Experiments using Quinlan's learning from examples system, ID3, and Fisher's conceptual clustering system, COBWEB, suggest that the benefits of simplification vary with the amount of training and with the statistical dependence of concept members on defining attributes.
Beyond concise and colorful: learning intelligible rules
52 Citations1997Michael J. Pazzani, Subramani Mani +1 more
It is shown that one factor that influences the intelligibility of learned models is consistency with existing knowledge and a learning algorithm is described that creates concepts with this goal in mind.
CancerA new metric-based approach to model selection
48 Citations1997Dale Schuurmans
A new approach to model selection is introduced that performs better than the standard complexity-penalization and hold-out error estimation techniques in many cases and dramatically outperform previous approaches in experimental studies of classical polynomial curve fitting.
Machine LearningKnowledge-Based Learning in Exploratory Science: Learning Rules to Predict Rodent Carcinogenicity
41 Citations1998Yong‐Won Lee, Bruce G. Buchanan +1 more
A multi-year collaboration among computer scientists, toxicologists, chemists, and a statistician, in which the RL induction program was used to assist toxicologists in analyzing relationships among various features of chemical compounds and their carcinogenicity in rodents demonstrated the utility of knowledge-based rule induction.
Elsevier eBooksIn Defense of C4.5: Notes on Learning One-Level Decision Trees
30 Citations1994Tapio Elomaa
The implications of Holte's recently-published article, which demonstrated that on the most commonly used data very simple classification rules are almost as accurate as decision trees produced by Quinlan's C4.5, are considered.
Elsevier eBooksLearning Prototypical Concept Descriptions
30 Citations1995Piew Datta, Dennis Kibler
PL, the algorithm for learning prototypical concept descriptions, is described and it is demonstrated that these descriptions can, in some situations, classify more accurately than standard Machine Learning algorithms.
International Joint Conference on Artificial IntelligenceDecision tree grafting
29 Citations1997Geoffrey I. Webb
The use of both pruning and grafting in conjunction is demonstrated to provide the best general predictive accuracy over a representative selection of learning tasks.
Knowledge Discovery and Data MiningVisualizing bagged decision trees
28 Citations1997J. Sunil Rao, William John Potts
It is shown that bagging's complexity can be better understood by a simple graphical technique that allows visualizing the bagged decision boundary in low-dimensional situations and can be heuristically motivated as a method to enhance local adaptivity of the boundary.
A Process-Oriented Heuristic for Model Selection
22 Citations1998Pedro Domingos
The paper develops the necessary theoretical framework, and applies it to one type of learning: rule induction, and develops a process-oriented version of the CN2 rule learner, which is empirically compared with the default CN2.
Adjusting for multiple comparisons in decision tree pruning
18 Citations1997David Jensen, Matt Schmill
In experiments with artificial and realistic datasets, Bonferroni pruning produces smaller trees that are at least as accurate as trees pruned using other common approaches.
Induction of condensed determinations
14 Citations1996Pat Langley
CONDET is described, an algorithm that uses feature selection to construct determinations from training data, augmented by a condensation process that collapses rows to produce simpler structures.
arXiv (Cornell University)Exploring the Decision Forest: An Empirical Investigation of Occam's Razor in Decision Tree Induction
13 Citations1994Patrick M. Murphy, Michael J. Pazzani
Characterizing the generalization performance of model selection strategies
8 Citations1997Dale Schuurmans, Lyle Ungar +1 more
It is shown that if the variance profile grows too rapidly in relation to the biases, then standard model selection techniques become prone to significant errors and a new model selection strategy is discussed that dramatically outperforms standard complexity-penalization and hold-out methods on these hard tasks.