Martignon,L.F.
Schmitt,M.

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. Key words: algorithms, Bayesian networks, generalization, heuristics, linear models, NP-hardness 0. Introduction The term ‘versus’ in the title of this issue, simple inference heuristics versus complex decision machines, is deliberately provocative. The contraposition ‘simplicity/ complexity’ is one of those dualities that proliferate in our scientific milieu without being pinned down in rigorous definitions. Thus, simple heuristics can only be placed versus complex decision machines in order to provoke at least an attempt at explaining what is meant by simplicity and what is meant by complexity. A closer look at etymologies may be of help. The word simple has ancient roots: it is formed by the Indo-European root ‘sem’, which means ‘one’ and the Latin root Minds and Machines 9: 565–593, 1999. © 1999 Kluwer Academic Publishers. Printed in the Netherlands.

Martignon, L., & Schmitt, M. (1999). Simplicity and robustness of fast and frugal heuristics. Minds and Machines, 9, 565-593.

Publication year	1999
Document type:	Article
Publication status:	Published
External URL:
Categories:	Statistical InferenceAdaptive Toolbox
Keywords: