The discovery of structural form

October 5, 2008

Charles Kemp and Joshua Tenenbaum have published (or have in press) a series of beautiful papers concerned with using Bayesian inference.  Their recent PNAS article opens with this sentence:

Discovering the underlying structure of a set of entities is a fundamental challenge for scientists and children alike. (Kemp PNAS)

The paper is focused on showing that discoveries about structural form can be understood computationally as probabilistic inferences about the organizing principles of a dataset.

Most structure-learning algorithms search for a structure of a single form that is assumed to be known in advance:

Clustering or competitive-learning algorithms search for a partition of the data into disjoint groups, algorithms for hierarchical clustering or phylogenetic reconstruction search for a tree structure, and algorithms for dimensionality reduction or multidimensional scaling search for a spatial representation of the data. (Kemp PNAS)

In the PNAS paper, they use graph grammars as a unifying language for expressing a wide range of structural forms.  This grammar provides a method for generating different kinds of structural forms (F).  Therefore, given a dataset (D) they can find the best form (F) and structure (S) of that form which best captures the relationships inherent between entities within the dataset P(S, F|D) ∝ P(D|S)P(S|F)P(F).   They use a uniform prior on P(F), a prior on P(S|F) which appropriately favors simpler forms, and constraints on P(D|S) which captures the intuitive expectation of data smoothness along the structure.    They then demonstrate that this model can accurately capture the intuitive structural form for a broad range of diverse datasets.

Holyoak, in a commentary on their PNAS paper, describe their work as “induction as model selection”.  It is therefore instructive to read Kemp and Tenenbaum’s Psychological Review paper (in press), where they discuss in some detail their perspective on inductive inference.  The Bayesian framework for probabilistic inference provides a general approach to understanding how problems of induction can, in principle, be solved.  Structured models are needed to capture the knowledge that drives induction.  Statistical inference is necessary to explain how this knowledge is acquired and used for inference in the presence of noise and uncertainty.  Bayesian methods therefore provide a principled framework for making “inherently under constrained inferences from impoverished data in an uncertain world.” (Griffiths, to appear)

In more detail, a learner must have both a recipe for specifying a prior and an engine for inductive inference.  The prior can be thought of simply as a priori knowledge about a problem.  Strong inductive bias is useful because it constrains the inferences a model is prepared to make.  (Constrains, however, only help if they guide in the right direction.)  Reasoning about a problem requires two kinds of knowledge.  First, one must have a structural representation which captures the kinds of relationships between entities, categories, or datum.   For example, a tree may be a good representation for evolution but a linear ordering may better describe body mass.  Note that enforcing a structure is equivalent to regularizing (or “cleaning up”) the data. Second, one must define a stochastic process to capture how the data depend on the structure.  Example processes include diffusion, drift, or causal transmission.  In other words, your process describes how you expect the data to change over the course of traversing your structure.

Kemp and Tenenbaum study high-level cognition, a field far from my own expertise.   While their efforts may not ground breaking to those in machine learning, their writing is remarkably readable, lucid, clear and thought provoking.

C. Kemp, J. B. Tenenbaum (2008). The discovery of structural form Proceedings of the National Academy of Sciences, 105 (31), 10687-10692 DOI: 10.1073/pnas.0802631105

K.J. Holyoak (2008). Induction as model selection. Proceedings of the National Academy of Sciences, 105 (31), 10687-10692 DOI: 10.1073/pnas.0805910105

C. Kemp, J. B. Tenenbaum (in press). Structured statistical models of inductive reasoning. Psychological Review. From Tenenbaum’s website.

T. L. Griffiths, C. Kemp, and J.B. Tenenbaum (to appear) Bayesian models of cognition. In Ron Sun (ed.), Cambridge Handbook of Computational Cognitive Modeling. Cambridge University Press. From Tenenbaum’s website.


One Response to “The discovery of structural form”

  1. son1 Says:

    I guess we’ve given up on having a reading group this semester?

    I’ll complain to Shaun.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: