


Lehrstuhl
Mathematik & Informatik
Simplicity and Robustness of Fast and Frugal Heuristics 









Simplicity and Robustness of Fast and Frugal Heuristics 

Intractability and optimality are two sides of one coin: Optimal
models are often intractable, that is, they tend to be excessively
complex, or NPhard. We explain the meaning of NPhardness in detail
and discuss how modern computer science circumvents intractability by
introducing heuristics and shortcuts to optimality, often replacing
optimality by means of sufficient suboptimality. 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, 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 comparisonbased inference and, in each of these
classes, search for optimizing models that are 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 through 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.





