Abstract
Intractability and optimality are two sides of one coin: Optimal models are often intractable, that is, they tend to be excessively complex, or NP-hard. We explain the meaning of NP-hardness in detail and discuss how modem computer science circumvents intractability by introducing heuristics and shortcuts to optimality, often replacing optimality by means of sufficient sub-optimality. Since the principles of decision theory dictate balancing the cost of computation against gain in accuracy, statistical inference is currently being reshaped by a vigorous new trend: the science of simplicity. Simple models, as we show for specific cases, are not just tractable, they also tend to be robust. Robustness is the ability of a model to extract relevant information from data, disregarding noise.
Recently, Gigerenzer, Todd and the ABC Research Group (1999) have put forward a collection of fast and frugal heuristics as simple, boundedly rational inference strategies used by the unaided mind in real world inference problems. This collection of heuristics has suggestively been called the adaptive toolbox. In this paper we will focus on a comparison task in order to illustrate the simplicity and robustness of some of the heuristics in the adaptive toolbox in contrast to the intractability and the fragility of optimal solutions. We will concentrate on three important classes of models for comparison-based inference and, in each of these classes, search for that to be used as benchmarks to evaluate the performance of fast and frugal heuristics: lexicographic trees, linear modes and Bayesian networks. Lexicographic trees are interesting because they are particularly simple models that have been used by humans throughout the centuries. Linear models have been traditionally used by cognitive psychologists as models for human inference, while Bayesian networks have only recently been introduced in statistics and computer science. Yet it is the Bayesian networks that are the best possible benchmarks for evaluating the fast and frugal heuristics, as we will show in this paper.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akaike, H. (1973), ‘Information Theory and an Extension of the Maximum Likelihood Principle’ in B.N. Petrov and F. Csaki, eds., 2nd International Symposium on Information Theory, Budapest: Akademiai Kiado, pp. 267–281
Albers, W. (1997), Foundations of a Theory of Prominence in the Decimal System, Working papers (No. 265–271) University of Bielefeld, Germany: Institute of Mathematical Economics.
Breiman, L., Friedman, J. H., Olshen, R. A. and Stone, C. J. (1993), Classification and Regression Trees, New York: Chapman and Hall.
Calonghi, F. (1962), Dizionario Latino-Italiano etimologico, Turin: Rosemberg and Sellier.
Casti, J. (1994), Complexification: Explaining a Paradoxical World through the Science of Surprise. New York: Harper Collins.
Clemen, R. (1986), Making Hard Decisions: An Introduction to Decision Analysis, Boston: PWS Kent Publishing Co.
Cooper, G. (1990), ‘The Computational Complexity of Probabilistic Inference using Bayesian Belief Networks’ Artificial Intelligence 42, pp. 393–405.
Cooper, G. and Herskovits, E. (1992), ‘A Bayesian Method for the Introduction of Probabilistic Networks from Data’ Machine Learning 9, pp. 309–347.
Cover, T.M. and Thomas, J.A. (1991), Elements of Information Theory, New York: Wiley.
Czerlinski, J., Gigerenzer, G. and Goldstein, D. G. (in press), ‘Pushing Fast and Frugal Heuristics to the Limits: More Data Sets and More Competitions’ in G. Gigerenzer, P. Todd, and the ABC Research Group, Simple Heuristics that make Us Smart, New York: Oxford University Press.
Dawes, R. M. (1979), ‘The Robust Beauty of Improper Linear Models in Decision Making’ American Psychologist 34, pp. 571–582.
Einhorn, H. J. and Hogarth, R. M. (1975), ‘Unit Weighting Schemes for Decision Making’ Organizational Behavior and Human Performance 13, pp. 171–192.
Forster, M. R. (in press), ‘Key Concepts in Model Selection: Performance and Generalizability’ Journal of Mathematical Psychology.
Friedman, N. and Goldszmit, M. (1996), ‘Learning Bayesian Networks with Local Structure’ in Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence (UAI), Portland, OR/San Mateo, CA: Morgan Kaufmann, 12, pp. 252–262
Garey, M.R. and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco, CA: W. H. Freeman.
Gigerenzer, G. and Goldstein, D.G. (1996), ‘Reasoning the Fast and FrugalWay:Models of Bounded Rationality’ Psychological Review 103, pp. 650–669.
Gigerenzer, G. and Hoffrage, U. (1995), ‘How to Improve Bayesian Reasoning without Instruction: Frequency Format’ Psychological Review 102, pp. 684–704.
Gigerenzer, G., Czerlinski, J. and Martignon, L. (in press), ‘How Good are Fast and Frugal Heuristics?’ In J. Shanteau, B. Mellers and D. Schum, eds. Decision Research from Bayesian Approaches to Normative Systems: Reflections on the Contributions of Ward Edwards, Norwell,MA: Kluwer Academic Publishers.
Gigerenzer, G., Todd P.M. and the ABC Research Group (in press), Simple Heuristics that make Us Smart, New York: Oxford University Press.
Goldstein, D.G. and Gigerenzer, G. (1999), ‘The Recognition Heuristic: How Ignorance makes Us Smart’ in G. Gigerenzer, P.M. Todd and the ABC Research Group, Simple Heuristics that make Us Smart, New York: Oxford University Press.
Harries, C. and Dhami, M. K. (1998), ‘The Fast and Frugal Fetish: Fructiferous Freethinking or Futile Fracas?’ Paper presented at the 14th Annual International Invitational Meeting of the Brunswik Society, November 21, Dallas, TX.
Hertwig, R., Hoffrage, U. and Martignon, L. (in press), ‘Quick Estimation: Letting the Enviroment do Some of theWork’ in G. Gigerenzer, P.M. Todd and the ABC Research Group, Simple Heuristics that make Us Smart, New York: Oxford University Press.
Hochbaum, D. S. (1997), Approximation Algorithms for NP-Hard Problems. Boston, MA: PWS Publishing Company.
Hogarth, R. M. (1978), ‘A Note on Aggregating Opinions’ Organizational Behavior and Human Performance 21, pp. 40–46.
Kass, R. and Raftery, A. (1995), ‘Bayes Factors’ Journal of the American Statistical Association 90 p. 430.
Krauss, S., Martignon, L. and Hoffrage, U. (1998), ‘Simplifying Bayesian Inference’ in Conference on Model-Based Reasoning in Scientific Discovery, Pavia, Italy.
Martignon, L. and Hoffrage U. (1999a), ‘Where and Why is Take The Best Fast, Frugal and Fit? A Case Study in Ecological Rationality’ in G. Gigerenzer, P.M. Todd and the ABC Research Group, Simple Heuristics that make Us Smart, New York: Oxford University Press.
Martignon, L. and Hoffrage U. (1999b), Take The Best is Fast, Frugal, and Fit manuscript submitted for publication, Max Planck Institute for Human Development, Berlin.
Martignon, L. and Laskey, K. (in press), ‘Taming Wilder Agents: Bayesian Benchmarks for Fast and Frugal Heuristic’ in G. Gigerenzer, P.M. Todd and the ABC Research Group, Simple Heuristics that make Us Smart, New York: Oxford University Press.
Pearl, J. (1988), Probabilistic Reasoning in Intelligent Systems, San Francisco, CA: Morgan Kaufmann.
Poincare, H. (1952), Science and Hypotheses, [1905] NY: Dover.
Schmitt, M. and Martignon, L. (1999), ‘Complexity of Lexicographic Strategies on Binary Cues’ unpublished manuscript.
Tversky, A. and Kahneman, D. (1974), ‘Judgment under Uncertainty: Heuristics and Biases’ Science 185, pp. 1124–1131.
Waldrop, M. (1992), Complexity: The Emerging Science at the Edge of Chaos, New York: Simon and Schuster.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Martignon, L., Schmitt, M. Simplicity and Robustness of Fast and Frugal Heuristics. Minds and Machines 9, 565–593 (1999). https://doi.org/10.1023/A:1008313020307
Issue Date:
DOI: https://doi.org/10.1023/A:1008313020307