Compositionality, MDL Priors, and Object Recognition
Authors: Stuart Geman, Daniel Potter Elie Bienenstock
Published in: Advances in Neural Information Processing Systems 9  (NIPS 1996) (Main Conference Track), 1996

Abstract: Images  are ambiguous  at  each  of many  levels  of a  contextual  hi(cid:173) erarchy.  Nevertheless,  the high-level  interpretation of most  scenes  is  unambiguous,  as  evidenced  by the superior  performance of hu(cid:173) mans.  This observation argues for global vision models, such as de(cid:173) formable templates.  Unfortunately,  such  models are computation(cid:173) ally intractable for unconstrained problems.  We propose a composi(cid:173) tional model in which  primitives are recursively composed, subject  to syntactic restrictions, to form tree-structured objects and object  groupings.  Ambiguity  is  propagated up the hierarchy in  the form  of multiple interpretations, which are later resolved by a  Bayesian,  equivalently minimum-description-Iength,  cost functional. 
1  Bayesian decision theory and compositionaiity 
In  his  Essay  on  Probability,  Laplace  (1812)  devotes  a  short  chapter-his  "Sixth  Principle" -to what  we  call  today  the  Bayesian  decision  rule.  Laplace  observes  that  we  interpret  a  "regular  combination,"  e.g.,  an  arrangement  of objects  that  displays some particular symmetry, as having resulted from a  "regular cause"  rather  than arisen  by  chance.  It is  not,  he argues,  that a  symmetric configuration is  less  likely to happen by chance than another arrangement.  Rather, it is  that among all  possible  combinations,  which  are equally  favored  by chance,  there are very  few  of  the regular type:  "On a table  we  see  letters  arranged in this  order,  Constantinople,  and  we  judge  that  this  arrangement  is  not  the  result  of chance,  not  because  it  is  less  possible  than  the  others,  for  if this  word  were  not  employed  in  any  language 
Compositionality, MDL Priors, and Object Recognition 
839 
we  should  not suspect it came from  any particular  cause,  but this word  being  in use  amongst  us,  it  is  incomparably  more probable  that  some  person  has  thus  arranged  the  aforesaid letters than that this  arrangement is  due  to  chance." In this example,  regularity is not a mathematical symmetry.  Rather, it is a convention shared among  language users, whereby  Constantinople is  a word, whereas Jpctneolnosant,  a string  containing the same letters but arranged in a  random order,  is  not. 
Central  in  Laplace's argument is  the observation that the number of words in  the  language  is  smaller,  indeed  "incomparably"  smaller,  than  the  number  of possible  arrangements of letters.  Indeed,  if the collection  of 14-letter words  in  a  language  made up, say, half of all 14-letter strings- a rich language indeed-we would, upon  seeing the string  Constantinople on the table, be far less inclined to deem it a word,  and far  more inclined  to accept it as  a  possible coincidence.  The sparseness of al(cid:173) lowed combinations can be observed at all linguistic articulations (phonetic-syllabic,  syllabic-lexical, lexical-syntactic, syntactic-pragmatic, to use broadly defined levels),  and may be viewed  as a form of redundancy-by analogy to error-correcting codes.  This redundancy was likely devised by evolution to ensure efficient  communication  in  spite  of the  ambiguity of elementary  speech  signals.  The hierarchical  composi(cid:173) tional  structure of natural  visual  scenes  can also  be thought  of as  redundant:  the  rules  that  govern  the  composition  of edge  elements  into  object  boundaries,  of in(cid:173) tensities into surfaces etc., all the way to the assembly of 2-D  projections of named  objects, amount to a  collection of drastic combinatorial restrictions.  Arguably,  this  is why in all but a few-generally hand-crafted-cases, natural images have a unique  high-level interpretation in spite of pervasive low-level ambiguity-this being amply  demonstrated by the performances of our brains. 
In sum, compositionality appears to be a fundamental aspect of cognition (see also  von  der  Malsburg 1981,  1987;  Fodor and Pylyshyn 1988;  Bienenstock,  1991,  1994,  1996;  Bienenstock and Geman 1995).  We  propose here to account for  mental com(cid:173) putation  in  general  and  scene  interpretation in  particular in  terms  of  elementary  composition  operations,  and  describe a  mathematical framework  that  we  have de(cid:173) veloped  to this  effect.  The present  description is  a  cursory one,  and some notions  are illustrated on two simple examples rather than formally defined-for a  detailed  account, see  Geman et al.  (1996),  Potter (1997).  The  binary-image example refers  to an  N  x  N  array of binary-valued pixels,  while the  Laplace-Table  example refers  to a  one-dimensional array of length N, where each position can be filled  with  one  of the 26 letters of the alphabet or remain blank. 
2  Labels and  composition rules 
The  objects  operated  upon  are  denoted  Wi, i  =  1,2, ... , k.  Each  composite object  W  carries  a  label,  I  =  L(w),  and  the  list  of  its  constituents,  (Wt,W2,·· .).  These  uniquely  determine  w,  so  we  write W  =  I (WI, W2, .•. ) .  A  scene S  is  a  collection  of  primitive  objects.  In  the  binary-image  case,  a  scene  S  consists  of a  collection  of  black pixels in the N  x N  array.  All these primitives carry the same label,  L(w)  =  p  (for  "Point"), and a parameter 7r(w)  which is the position in the image.  In Laplace's  Table, a scene S  consists of an arrangement of characters on the table.  There are 26  primitive labels,  "A", "B" , ... , "Z" , and the parameter of a primitive W  is  its position  1 ~ 7r(w)  ~ N  (all primitives in such a  scene must have different  positions). 
An example of a composite W  in the binary-image case is an arrangement composed 
840 
E.  Bienenstock. S.  Geman and D.  Potter 
of a  black pixel at any position except on the rightmost column and another black  pixel  to  the  immediate  right  of the  first  one.  The  label  is  "Horizontal  Linelet,"  denoted  L(w)  =  hl,  and there are  N(N - 1)  possible horizontallinelets.  Another  non-primitive  label,  "Vertical  Linelet,"  or vl,  is  defined  analogously.  An  example  of a  composite  W  for  Laplace's  Table  is  an  arrangement  of 14  neighboring  primi(cid:173) tives  carrying the labels  "G", "0", "N", "S", ... , "E"  in  that order, wherever  that  arrangement will  fit.  We  then have L(w) = Ganstantinople, and there are N  - 13  possible Constantinople objects. 
The  composition  rule  for  label  type  1 consists  of a  binding  junction,  B"  and a  set  of allowed  binding-function  values,  or  binding  support,  S,:  denoting  by  0  the set  of  all  objects  in  the  model,  we  have,  for  any  WI, ' .. ,Wk  E  0,  B, (WI. ... ,Wk)  E  s,  ¢:} l(WI""  ,Wk)  E O.  In the binary-image example, Bhl(WI,W2)  =  Bv,(WI,W2)  =  (L(WI),L(W2),7I'(W2)  -7I'(WI)),  Sh'  =  {(P,p,(I,O))}  and Sv'  =  {(p,p,(O,I))}  define  the hl- and vl-composition rules, p+p -+  hl and p+p -+  vl.  In Laplace's Table, G +  0+· .. + E  -+ Ganstantinpole is an example of a 14-ary composition rule, where we  must check the label and position of each constituent.  One way to define the binding  function and support for  this rule is:  B(WI, ' "  ,WI4)  =  (L(WI),' "  ,L(WI4), 71'(W2)  - 71'(Wt} , 71'(W3)  - 71'(WI),"', 71'(W14)  - 71'(WI))  and S  =  (G,"', E, 1,2"",13). 
We now introduce recursive labels and composition rules:  the label of the composite  object is  identical to the label of one or more of its constituents, and the rule may  be applied  an arbitrary number of times,  to yield objects of arbitrary complexity.  In  the binary-image case,  we  use a  recursive label  c,  for  Curve,  and an associated  binding function which creates objects of the form  hl + p -+ c, vl + p -+ c,  c + p -+ c,  p + hl  -+  c,  p + vl  -+  c,  p + c  -+  c,  and  c + c  -+  c.  The  reader  may  easily  fill  in  the details,  i.e.,  define  a  binding function  and  binding  support  which  result  in  "c" -objects  being  precisely  curves  in  the  image,  where  a  curve  is  of length  at  In  the  previous  examples,  primitives  were  least  3  and  may  be  self-intersecting.  composed  into  compositions;  here  compositions  are  further  composed  into  more  complex  compositions.  In general,  an object W  is  a  labeled  tree,  where each  vertex  carries  the  name  of  an  object,  and  each  leaf is  associated  with  a  primitive  (the  association is  not necessarily one-to-one, as in the case of a  self-intersecting curve). 
Let  M  be  a  model-Le.,  a  collection  of labels  with  their  binding  functions  and  binding  supports-and  0  the  set  of  all  objects  in  M .  We  say  that  object  W  E  o  covers  S  if S  is  precisely  the  set  of  primitives  that  make  up  w's  leaves.  An  interpretation  I  of S  is  any  finite  collection  of objects  in  0  such  that  the  union  of the  sets  of primitives  they  cover  is  S.  We  use  the convention  that,  for  all  M  and S, 10  denotes the  trivial interpretation, defined  as the collection of (unbound)  primitives in S.  In most cases of interest, a model M  will allow many interpretations  for  a  scene  S .  For  instance,  given  a  long  curve  in  the binary-image model,  there  will  be  many  ways  to recursively  construct  a  "c"-labeled tree that covers  exactly  that curve. 
3  The MDL  formulation 
In  Laplace's  Table,  a  scene  consisting  of  the  string  Constantinople  admits,  in  addition  to  10 ,  the  interpretation  II  =  {WI},  where  WI  is  a  "G anstantinople" - object.  We  wish to define a probability distribution D  on interpretations such that  D(I1 )  »  D(Io), in order to realize Laplace's  "incomparably more probable".  Our 
Compositionality, MDL Priors, and Object Recognition 
841 
definition of D  will  be motivated by the following  use of the Minimum Description  Length  (MDL)  principle (Rissanen 1989).  Consider a  scene S and pretend we want  to transmit S  as  quickly as  possible through a  noiseless  channel,  hence  we  seek to  encode it as efficiently as possible, i.e., with the shortest possible binary code c.  We  can always use  the trivial interpretation 10:  the codeword  c(Io)  is a  mere list  of n  locations in S.  We  need not specify labels, since there is  only one primitive label in  this example.  The length, or cost,  of this code for  S  is  Ic(Io)1  =  nlog2 (N 2 ). 
Now  however  we  want  to  take  advantage of regularities,  in  the  sense  of Laplace,  that  we  expect to be present  in  S.  We  are specifically  interested in  compositional  regularities, where some arrangements that occur more frequently  than by chance  can  be  interpreted  advantageously  using  an  appropriate  compositional  model  M.  Interpretation I  is advantageous if Ic(I)1  < Ic(Io)l.  An example in the binary-image  case is a linelet scene S.  The trivial encoding of this scene costs us Ic(Io)1  =  2[log2 3+  log2(N2)]  bits,  whereas  the  cost  of the  compositional  interpretation  II  =  {wI}  is  Ic(Idl =  log2 3+log2 (N(N -1)), where WI  is an hI or vl object, as the case may be.  The first  log23  bits  encode the label  L(WI)  E  {p, hi, vi}, and  the rest  encodes  the  position in the image.  The compositional {p, hl, vl} model is therefore advantageous  for a  linelet scene,  since It affords us  a gain in encoding cost of about 2log2 N  bits.  In general, the gain realized by encoding {w}  =  {I (WI, W2)}  instead of {WI, W2}  may  be  viewed  as  a  binding  energy,  measuring  the  affinity  that WI  and  W2  exhibit  for  each  other as  they assemble into w.  This binding energy is c,  =  IC(WI)I  +  IC(W2)1  - I c( I (WI, W2) ) I,  and an efficient  M  is one that contains judiciously chosen cost-saving  composition  rules.  In  effect,  if,  say,  linelets  were  very  rare,  we  would  be  better  off  with  the  trivial  model.  The  inclusion  of non-primitive  labels  would  force  us  to add at least  one bit to the code  of every  object-to specify  its  label-and this  would increase the  average encoding cost, since the infrequent use of non-primitive  labels  would  not balance the extra small  cost  incurred  on primitives.  In practical  applications,  the  construction  of  a  sound  M  is  no  trivial  issue.  Note  however  the simple rationale for  including a  rule such  as  p +  p  --7  hl.  Giving  ourselves the  label hi renders redundant the independent encoding of the positions of horizontally  adjacent pixels.  In general, a good model should allow one to hierarchically compose  with each other frequently  occurring arrangements of objects. 
This use of MDL leads in a straightforward way to an equivalent Bayesian formula(cid:173) tion.  Setting P'(w)  =  2- lc(w)lj L:w'EO 2- lc(w')I  yields  a  probability distribution  P'  on n for  which c is approximately a Shannon code (Cover and Thomas 1991).  With  this definition,  the decision to include the label hl-or the label Con8tantinople(cid:173) would be viewed, in principle, as a statement about the prior probability of finding  horizontal linelets-or  Constantinople strings-in the scene to be interpreted. 
4  The observable-measure formulation 
The MDL formulation  however has a  number of shortcomings;  in  particular, com(cid:173) puting the  binding  energy for  composite objects  can  be  problematic.  We  outline  now  an alternative approach  (Geman et al.  1996,  Potter 1997),  where a  probabil(cid:173) ity distribution  P(w)  on n is  defined  through  a  family  of observable  measures Q,.  These measures assign probabilities to each possible binding-function value,  s E  S"  and also to the primitives.  We  require L:'EM L:sEsr Q,(8)  =  1,  where the notion of  binding function has been extended to primitives via Bprim (w)  =  7r(w)  for primitive 
842 
E.  Bienenstoc/c, S. Geman and D. Potter 
w.  The probabilities  induced  on  0  by  Q,  are  given  by  P(w)  =  Qprim(Bprim(w))  for  a  primitive w,  and P(w) =  Q,(B,(WI,W2))P2(WI,W2IB,(WI,W2))  for  a  composite  object w =  l(wI, W2).1  Here p 2  =  P  X  P  is  the product probability, i.e., the free,  or  not-bound, distribution for the pair (WI, W2)  E 0 2.  For instance, with C + ... + E  -?  Canstantinople,  p 14 (WI,W2,'"  ,w14IBcons ... (W1, ... ,W14)  =  (C, 0,···,13))  is  the  conditional  probability of observing  a  particular string  Constantinople,  under  the  free  distribution,  given  that  (WI, ... , W14)  constitutes such  a  string.  With the rea(cid:173) sonable  assumption  that,  under  Q,  primitives  are  uniformly  distributed  over  the  table,  this  conditional  probability  is  simply  the  inverse  of the  number of possible  Constantinople strings, Le.,  1/(N - 13). 
The  binding  energy,  defined,  by  analogy  to  the  MDL  approach,  as  [,  =  log2(P(w)/(P(wdP(w2))),  now  becomes  [,  =  log2(P  x  P(B'(Wl,W2)))'  Finally,  if I  is  the collection of all finite interpretations /  c 0, we  define the probability of /  E I  as D(/) = IIwElP(w)/Z, with Z  = L:I'EI IIwEl'P(w),  Thus, the probability of an interpretation containing several free objects is obtained  by assuming that these objects occurred in the scene independently of each  other.  Given a  scene S,  recognition is formulated  as the task of maximizing D  over all the  l's in I  that are interpretations of S. 
log2(Q,(B,(wI,w2)))  -
We  now illustrate the use of D  on our two examples.  In the binary-image example  with  model  M  =  {p, hi, vi}, we  use  a  parameter q, 0  ~ q  ~ 1,  to adjust  the prior  probability  of linelets.  Thus,  Qprim(Bprim(W))  =  (1  - q)/N2 for  primitives,  and  Qh'«P,p,O, 1)) = Qv'«P,p, 1,0)) =  q/2 for  linelets.  It is  easily seen that regardless  of  the  normalizing  constant  Z,  the  binding  energy  of two  adjacent  pixels  into  a  linelet  is  [h'  =  [v,  =  log2(q/2)  - log2[{lNf N(N - 1)].  Interestingly,  as  long  as  q =1=  0  and q  =1=  1,  the binding energy,  for  large N, is  approximately 2log2 N, which  is  independent of q.  Thus, the linelet interpretation is  "incomparably"  more likely  than  the  independent  occurrence  of two  primitives  at  neighboring  positions.  We  leave  it  to  the  reader  to  construct  a  prior  P  for  the  model  {p, hl, vI, c},  e.g.  by  distributing the Q-mass evenly between all  composition rules.  Finally, in  Laplace's  Table,  if there are M  equally likely non-primitive labels-say city names-and q  is  their total mass, the binding energy for  Constantinople is [Cons ...  =  log2  M(r! -13)  - log2[~~.&]14, and the  "regular"  cause is  again  "incomparably"  more likely. 
There are several advantages to this reformulation from codewords into probabilities  using  the  Q-parameters.  First,  the Q-parameters can  in  principle  be  adjusted  to  better account for  a  particular world of images.  Second,  we  get an explicit formula  for  the  binding energy,  (namely  log2 (Q / P  x  P)).  Of course,  we  need  to evaluate  the  product  probability  P  x  P,  and this  can be highly  non-trivial-one approach  is  through  sampling,  as  demonstrated  in  Potter  (1997).  Fi~ally,  this  formulation  is  well-suited  for  parameter estimation:  the Q's,  which  are the parameters of the  distribution P, are indeed observables, Le.,  directly available empirically. 
5  Concluding remarks 
The  approach  described  here  was  applied  by  X.  Xing  to  the  recognition  of  "on(cid:173) line"  handwritten characters, using a  binary-image-type model  as  above,  enriched 
IThis is actually an implicit definition.  Under reasonable conditions, it is well defined(cid:173)
see  Geman et al.  (1996). 
Compositionality, MDL Priors, and Object Recognition 
843 
with  higher-level  labels  including  curved  lines,  straight lines,  angles,  crossings,  T(cid:173) junctions,  L-junctions  {right  angles},  and  the  26  letters  of the alphabet.  In such  a  model,  the search for  an optimal  solution  cannot  be done  exhaustively.  We  ex(cid:173) perimented with a  number of strategies, including a  two-step algorithm which first  generates all possible objects in the scene, and then selects the  "best"  objects, Le.,  the objects with highest total binding energy, using a greedy method, to yield a final  scene interpretation.  (The total binding energy of W  is  the sum of the binding ener(cid:173) gies  £,  over all  the composition rules  I  used  in the composition of w.  Equivalently,  the total binding energy is  the log-likelihood ratio log2{P{w}/IIi P{Wi)),  where  the  product is  taken over all the primitives Wi  covered by w.} 
The first  step  of the  algorithm  typically  results  in  high-level  objects  partly over(cid:173) lapping on the set of primitives they cover,  i.e.,  competing for  the interpretation of  shared  primitives.  Ambiguity  is  thus  propagated  in  a  "bottom-up"  fashion.  The  ambiguity is  resolved  in  the second  "top-down"  pass,  when high-level  composition  rules are used to select the best compositions, at all levels including the lower ones.  A  detailed  account  of our experiments  will  be given  elsewhere.  We  found  the  re(cid:173) sults quite encouraging, particularly in view of the potential scope of the approach.  In effect,  we  believe  that this  approach  is  in principle capable of addressing unre(cid:173) stricted vision problems, where images are typically very ambiguous at lower levels  for  a  variety of reasons-including occlusion and mutual overlap of objects-hence  purely bottom-up segmentation is  impractical. 
Turning now  to  biological implications,  note that dynamic binding in  the nervous  system has been a subject of intensive research and debate in the last decade.  Most  interesting in the present context is  the suggestion, first  clearly articulated by von  der  Malsburg {1981},  that composition may be performed  thanks to a  dual  mech(cid:173) anism  of accurate  synchronization  of spiking  activity-not  necessarily  relying  on  periodic  firing-and  fast  reversible  synaptic  plasticity.  If there is  some  neurobio(cid:173) logical  truth to the model  described  in the present  paper,  the binding mechanism  proposed  by  von  der  Malsburg would  appear to be an attractive implementation.  In effect, the use of fine temporal structure of neural activity opens up a large realm  of possible high-order codes in  networks of neurons. 
In the present  model,  constituents  always  bind  in  the  service of a  new  object,  an  operation one may refer to as  triangular  binding.  Composite objects can engage in  further composition, thus giving rise to arbitrarily deep  tree-structured constructs.  Physiological evidence of triangular binding in the visual system can be found in Sil(cid:173) lito et al.  {1994}; Damasio {1989} describes an approach derived from neuroanatom(cid:173) ical  data and lesion  studies that is  largely consistent with  the formalism  described  here. 
An  important requirement for  the neural representation of the tree-structured ob(cid:173) jects  used  in  our model  is  that the doing and undoing of links  operating on  some  constituents, say Wi  and W2,  while affecting in some  useful way the high-order pat(cid:173) terns that represent these objects, leaves these patterns, as representations of Wi  and  W2,  intact.  A family of biologically plausible patterns that would appear to satisfy  this  requirement  is  provided  by  synfire  patterns  {Abeles  1991}.  We  hypothesized  elsewhere  {Bienenstock 1991,  1994,  1996}  that synfire chains could be dynamically  bound via weak synaptic couplings; such couplings would synchronize the wave-like  activities  of two  synfire  chains,  in  much  the same  way  as  coupled  oscillators  lock 
844 
E.  Bienenstock, S.  Geman and D.  Potter 
their  phases.  Recursiveness  of compositionality could,  in  principle,  arise from  the  further  binding of these composite structures. 
Acknow ledgements 
Supported by the Army Research Office (DAAL03-92-G-0115), the National Science  Foundation (DMS-9217655), and the Office of Naval  Research (N00014-96-1-0647).