An Efficient Method for the Minimum Description Length Evaluation of Deterministic Cognitive Models

An Eﬃcient Method for the Minimum Description Length Evaluation of Deterministic Cognitive Models Michael D. Lee (michael.lee@adelaide.edu.au) Department of Psychology, University of Adelaide South Australia, 5005,  The ability to evaluate competing models against noisy data is central to progress in cognitive science. In general, this requires advanced model selection criteria, such as the Minimum Description Length (MDL) criterion, that balance goodness­of­ﬁt with model complexity. One limiting property of many of these criteria, however, is that they cannot read­ ily be applied to deterministic models. A solution to this problem, developed by Gr¨ unwald (1999), involves a process called ‘entropiﬁcation’ that associates de­ terministic models with probability distributions, and allows MDL criteria to be calculated. However, a po­ tential practical diﬃculty with this approach is that it requires a multidimensional summation over the data space that can be prohibitively computationally ex­ pensive in realistic situations. This paper derives a simpler version of the MDL criterion for deterministic models in the important special case of 0­1 loss func­ tions that is computationally feasible. Two concrete applications of the simpler MDL criterion are pre­ sented, demonstrating its ability to consider model ﬁt and complexity in selecting between competing mod­ els of cognitive processes. The ﬁrst application in­ volves three diﬀerent heuristics for a problem solving task, while the second involves three diﬀerent models of forced­choice decision making.  To a large extent, progress in cognitive science relies on the development of better models of cognitive phe­ nomena. Models provide a formalized representation of theoretical explanations, and make predictions that can be tested empirically. For this reason, the ability to evaluate competing cognitive models against noisy data in a complete and meaningful way has been a cen­ tral concern recently in mathematical psychology (e.g., Myung & Pitt 1997; Myung, Balasubramanian & Pitt 2000; Myung, Forster, & Browne 2000; Pitt, Myung, & Zhang 2002). In particular, there has been a strong (and overdue) focus on balancing the goodness­of­ﬁt of models with their complexity. These ideas have been applied to core topics in cognitive science such as models of psy­ chophysical discrimination (e.g., Myung et al. 2000), stimulus representation (e.g., Lee 2001;  in press), inference and generalization (e.g., Tenenbaum & Griﬃths 2001), and decision­making (e.g., Myung & Pitt 1997). Probabilistic Models For the most part, however, these recent development have been restricted to considering probabilistic cogni­ tive models. This class of models has the property that any parameterization (or, more generally, any probability distribution over the parameter space) cor­ responds to a probability distribution over the data. That is, the model corresponds to a parametric family of probability distributions over the data. This means that considering a probabilistic model at a particular set of parameter values makes some data quantiﬁably more likely than others. In turn, for probabilistic mod­ els the likelihood of any observed data having arisen under the model at any parameterization of interest can be evaluated. Many cognitive models are probabilistic in this way. For example, models of memory retention (e.g., Ru­ bin & Wenzel 1996) usually consist of parameterized functions that specify the probability an item will be recalled correctly after a period of time. As another ex­ ample, the ALCOVE model of category learning (Kr­ uschke 1992) also produces a probability, that depends upon the values of a number of parameters, for each possible category response on any trial. For these mod­ els, their probabilistic nature allows likelihood to be measured against any pattern of observed data. Many advanced model selection criteria, such as Bayes Factors (e.g., Kass & Raftery 1995), Minimum Description Length (MDL: e.g., Gr¨ unwald 2000), Sto­ chastic or Geometric Complexity (Myung, Balasubra­ manian & Pitt 2000; Rissanen 1996), and Normalized Maximum Likelihood (Rissanen 2001), rely on this property. This is because they integrate the proba­ bilities of the data across the parameter space of the models, or the maximum likelihoods across all possible data sets, and so require non­zero probabilities over a subset of the parameter space that has measure greater than zero to be meaningful.