The Use of MDL to Select among Computational Models of Cognition
Authors: In Jae Myung, Mark A. Pitt, Shaobo Zhang, Vijay Balasubramanian
Published in: Advances in Neural Information Processing Systems 13  (NIPS 2000) (Main Conference Track), 2000

Abstract: How  should  we  decide  among  competing  explanations  of  a  cognitive  process  given  limited  observations?  The  problem  of  model  selection  is  at  the  heart of progress  in  cognitive  science.  In  this paper, Minimum Description Length (MDL) is introduced as a  method  for  selecting  among  computational  models  of  cognition.  We  also  show  that  differential  geometry  provides  an  intuitive  understanding  of  what  drives  model  selection  in  MDL.  Finally,  adequacy  of  MDL  is  demonstrated  in  two  areas  of  cognitive  modeling. 
1  Model  Selection  and  Model  Complexity 
The development and  testing of computational models  of cognitive processing are  a  central focus in cognitive science.  A model embodies a solution to  a problem whose  adequacy  is  evaluated by  its  ability  to  mimic  behavior by  capturing  the  regularities  underlying  observed data.  This enterprise  of model  selection is  challenging because  of the  competing  goals  that  must be  satisfied.  Traditionally,  computational  models  of  cognition  have  been  compared  using  one  of  many  goodness-of-fit  measures.  However, use  of such a measure can result in the choice of a model that over-fits the  data,  one that captures idiosyncracies in  the particular data set (i.e.,  noise) over and  above  the  underlying regularities  of interest.  Such models  are  considered  complex,  in that the  inherent flexibility  in  the  model enables it to  fit  diverse patterns of data.  As a group,  they can be characterized as having many parameters that are combined  in  a  highly  nonlinear fashion  in  the  model  equation.  They do  not  assume  a  single  structure in  the data. Rather,  the model  contains  multiple  structures; each  obtained  by finely  tuning the parameter values of the  model,  and thus can fit a wide range of  data patterns. In  contrast, simple models,  frequently  with few  parameters, assume a  specific structure in the data, which will manifest itself as a narrow range of similar  data  patterns.  Only  when  one  of these  patterns  occurs  will  the  model  fit  the  data  well. 
The  problem  of over-fitting data due  to  model complexity  suggests that the goal  of  model selection should instead be to select the model that generalizes best to all data  samples  that  arise  from  the  same  underlying  regularity,  thus  capturing  only  the  regularity,  not  the  noise.  To  achieve  this  goal,  the  selection  method  must  be  sensitive  to  the  complexity  of  a  model.  There  are  at  least  two  independent  dimensions  of  model  complexity.  They  are  the  number  of  free  parameters  of  a 
model and  its functional form,  which refers to the way the parameters are combined  in  the  model  equation.  For  instance,  it  seems  unlikely  that  two  one-parameter  models,  y  =  ex and  y  =  x9,  are equally complex in their ability to  fit data.  The two  dimensions  of model  complexity  (number  of parameters  and  functional  form)  and  their interplay can improve a  model's fit  to  the  data,  without necessarily improving  generalizability. 
The trademark of a good model  selection procedure, then, is  its ability to  satisfy two  opposing  goals.  A  model  must be sufficiently complex  to  describe  the  data  sample  accurately,  but  without  over-fitting  the  data  and  thus  losing  generalizability.  To  achieve this end, we need a theoretically well-justified measure of model  complexity  that takes into account the number of parameters and the functional form  of a model.  In  this  paper, we  introduce Minimum  Description Length  (MDL)  as  an  appropriate  method  of selecting  among  mathematical  models  of cognition.  We  also  show  that  MDL  has  an  elegant  geometric  interpretation  that  provides  a  clear,  intuitive  understanding of the meaning of complexity in  MDL.  Finally, application examples  of MDL are presented in two areas of cognitive modeling. 
1.1  Minimum  Description  Length 
The central thesis of model  selection is the estimation of a model's generalizability.  One  approach  to  assessing  generalizability  is  the  Minimum  Description  Length  (MDL)  principle  [1].  It  provides  a  theoretically  well-grounded  measure  of  complexity that is sensitive to both dimensions of complexity and also lends itself to  intuitive,  geometric interpretations.  MDL was developed  within  algorithmic coding  theory  to  choose  the  model  that permits  the  greatest  compression of data.  A  model  family f  with  parameters e assigns  the  likelihood f(yle)  to  a  given  set  of observed  data y . The full  form  of the MDL measure for  such a model family is  given below. 
MDL = -In! (yISA) + ~ln( ; ) + In f dS.jdetl(S) 
where SA is  the  parameter  that  maximizes  the  likelihood,  k  is  the  number  of  parameters  in  the  model,  N  is  the  sample  size  and  I(e)  is  the  Fisher  information  matrix.  MDL  is  the  length  in  bits  of the  shortest  possible  code  that  describes  the  data with  the  help  of a  model.  In  the context of cognitive modeling,  the  model that  minimizes  MDL  uncovers  the  greatest  amount  of  regularity  (i.e.,  knowledge)  underlying  the  data  and  therefore  should  be  selected.  The  first,  maximized  log  likelihood term  is  the  lack-of-fit measure,  and  the second and third  terms constitute  the  intrinsic  complexity  of  the  model.  In  particular,  the  third  term  captures  the  effects of complexity due to functional form,  reflected through I(e).  We will call the  latter  two  terms  together  the  geometric  complexity  of  the  model,  for  reasons  that  will  become clear in the remainder of this paper. 
MDL arises  as  a  finite  series  of terms  in  an  asymptotic  expansion  of the  Bayesian  posterior probability  of a  model  given  the  data for  a  special  form  of the  parameter  prior  density  [2] .  Hence  in  essence,  minimization  of  MDL  is  equivalent  to  maximization  of  the  Bayesian  posterior  probability.  In  this  paper  we  present  a  geometric  interpretation  of  MDL,  as  well  as  Bayesian  model  selection  [3],  that  provides an  elegant and  intuitive framework for  understanding model complexity, a  central concept in model  selection. 
2  Differential  Geometric  Interpretation of MDL 
From  a  geometric  perspective,  a  parametric  model  family  of  probability  distributions forms  a Riemannian manifold embedded in  the space of all  probability 
distributions  [4].  Every  distribution  is  a  point  in  this  space,  and  the  collection  of  points created by  varying  the  parameters of the model  gives rise  to  a  hyper-surface  in  which  "similar"  distributions  are  mapped  to  "nearby" points.  The infinitesimal  distance  between  points  separated  by  the  infinitesimal  parameter differences  de;  is  given by  ds 2  = Y' k.  g .. (8 )d8 ; d8  j  where g ij(e) is the Riemannian metric tensor. The  Fisher information,  lij(e),  is  the natural  metric  on  a manifold of distributions in the  context of statistical inference [4].  We argue that the MDL measure of model fitness  has an  attractive interpretation in  such  a geometric context.