Andreas J. Stuhlmüller

Learning Compositional Representations

A thesis submitted in partial fulfillment of the requirements
for the degree of Bachelor of Science
Department of Cognitive Science
University of Osnabrück

First Supervisor: Noah Goodman, Ph.D.
Second Supervisor: Prof. Dr. Kai-Uwe Kühnberger
Submitted: August 27, 2009

2

Declaration
I hereby declare that this submission is my own work and that I
have not used any other resources or auxiliaries except for thosewhere due acknowledgment has been made in the text.
Osnabrück, August 27, 2009.................................................................
Andreas Stuhlmüller (Matrikel 928118)

Hiermit erkläre ich, dass ich die vorliegende Arbeit eigenständig
verfasst habe und keine anderen Quellen und Hilfsmittel als die
im Text angegebenen verwendet habe.
Osnabrück, 27. August 2009.................................................................
Andreas Stuhlmüller (Matrikel 928118)

3

4

Abstract
How could an agent learn and reason in a complexly structured,stochastic world? This problem is at the center of both artificial intelligence and psychology. One candidate answer to thisquestion is that both learning and reasoning can be explained asprobabilistic inference over a language-like hypothesis space forgenerative models. The goal of this thesis is to describe whatmakes this approach plausible and to demonstrate the learning ofgenerative models from structured observations in a simple worldconsisting of stochastic, tree-generating programs. In order tomake program inference feasible, I derive a new class of adaptive
importance sampling algorithms for probabilistic programs that
let us compute the likelihood of structured observations under agiven generative model. Using this algorithm in combination with
Markov Chain Monte Carlo methods, I quantitatively show that
we can reliably infer generative models from observations in ourdemonstration world.

5

Contents
1 Introduction

7

2 Background
2.1 Representationalism . . . . . . . . . . . . . . . . .
2.2 A Language of Thought . . . . . . . . . . . . . . .
2.3 Generative Models . . . . . . . . . . . . . . . . . .
2.4 Probabilistic Inference . . . . . . . . . . . . . . . .

13
13
14
16
18

3 Model23

4 Inference
4.1 Importance Sampling . . . . . . . . . . . . . . . . .
4.2 Adaptive Importance Sampling . . . . . . . . . . .
4.3 Markov Chain Monte Carlo . . . . . . . . . . . . .

27
29
37
47

5 Setup
5.1 A Structured World . . . . . . . . . . . . . . . . .
5.2 A Probabilistic Representation Language . . . . .

53
53
55

6 Learning
6.1 Method . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Illustration . . . . . . . . . . . . . . . . . . . . . .
6.3 Quantitative Experiments . . . . . . . . . . . . . .

57
57
59
62

7 Discussion
7.1 Interpretation . . . . . . . . . . . . . . . . . . . . .
7.2 Related Work . . . . . . . . . . . . . . . . . . . . .
7.3 Future Research . . . . . . . . . . . . . . . . . . .

69
69
70
71

8 Conclusion

75

Bibliography

78

Appendix82

6

Chapter 1

Introduction
As part of our project of understanding the human mind, we would
like to explain how physical systems can exhibit what we call learning and reasoning. In order to solve problems that are difficult
given our current technologies and knowledge, we would like tobuild systems that learn and reason. These are the two motivations I have in mind when I talk about an explanation of learningand reasoning, and the success of such an explanation shall be
determined by its contribution to these larger endeavors.
I take it as a working hypothesis that any such explanationmust be a reductive explanation. What I mean by a reductive
explanation is an explanation that shows how more elementarybuilding blocks must be combined to create a system that exhibits the properties in question. An explanation of a mental
phenomenon like learning and reasoning can be reductive only if
it explains intentional terms like belief using more basic, welldefined vocabulary.
In the following, I will first illustrate the abilities I want to
explain in my current and future work, then outline the approachto understanding learning and reasoning that I take and describe
the extent of the present work.
The question I want to answer is this: How could a system,
be it a human or a machine, learn and reason in as complex aworld as ours? How do we discover and make use of structure in
raw sensory data? What we see is not a mess of colored pixels,
what we hear is not a rush of uninterpreted sound waves — what
we perceive carries meaning. Our perceptions have connotations
7and make sense not in isolation but only when placed into a larger
model of the world. Phrasing my question in a way that carries
more assumptions, I ask: How can a system acquire — learn —such a model of the world from sensory data, and how can thismodel be used to make predictions about how the world works andto judge which statements about the world are true and which are
not — to reason?
Examples abound. Children learn to recognize and categorize objects. They reason about how objects behave using naive
physics and knowledge about causality, both of which might belearned from sensory data. They grasp the concept of a number,learn about social relations, and learn the principles of language
understanding and production. Not unlike children, we scientists
infer the principles of our fields from experimental data. Using
concepts we create to transfer knowledge across situations, wereason about the behavior even of systems we never observe inperson. The predictions of both children and scientists fare better than those of any artificial system we have constructed so far,and they do so systematically: information processing that leads
to successful learning and reasoning has method. What is thismethod?

1 By “incremental learning”, I referto learning that in some way builds
on what has been learned before.

In order to learn more about this method, I will look at simple
systems and explore how incremental1 learning can take place insuch systems. For example, it is obvious that the trees in each row
of figure 1.1 belong to the same class. What is the method we use
to determine that this is the case? The formal basis I build on toanswer questions like these will be Bayesian probability. Before I
say more about the extent of the current work, I will explain why
I have chosen the approach of looking at simple systems.
It is an almost tautological truth that we cannot understandcomplex systems as long as we do not understand simple systems.
Therefore, the practical part of this work is limited to learningand reasoning in a simple toy world that we do understand completely. There is another reason for choosing a simple system,and this one is based on the idea of reductive explanation. If
simple and complex systems that learn and reason are composedof similar building blocks, composed in a similar manner, thenunderstanding simple systems will bring us a long way towards
understanding more complex ones. The constructive counterpartof (iterated) reductive explanation is stratified design. Stratified
8design denotes the idea that complex systems should be designed
as a sequence of layers, where each layer is described by a language appropriate to that level of detail. If understanding a simple system helps to understand more complex ones, then building
a simple one may be useful for building more complex ones if thesequence of layers is similar. This approach is fundamental to thepractical part of this work, where I first extend the probabilistic
programming language Church, then use this language to describe
program inference.
Research on learning and reasoning blurs the separation between methodology and content. Not only do we approach the
problem by looking at the building blocks that are part of thelarger solution, but the idea of using building blocks — the ideaof compositionality — becomes a building block itself. The moregeneral idea of incremental learning will be one of the key featuresof my approach. Children’s learning takes time. For example,
when children learn the number words (which tends to start at
an age of two), they spend approximately six months in a oneknower stage during which they know that one means one and if
asked to give one item, they give one, otherwise a handful. They
then spend about nine months in a two-knower stage, about threemonth in a three-knower stage and then usually make the inductive leap and use counting to give you any number of items you
request ([Wyn90, Wyn92, PGT]). It is not a far-fetched hypothesis that each step builds on what has been learned before andreuses that which does not need to be changed. There is morethan one way to be incremental: Learning can be incremental in
the sense that, in the construction of new mental models, existingmodels can be used either as the basis that is being modified oras a building block. More generally, inference can be incremental
in the sense that, over time, a learner can accumulate proceduralknowledge on how to best learn and reason in certain situations.
In my work, I want to formalize both ways of being incremental.
Any attempt at a reductive explanation must be built on a firmbasis or it cannot succeed. Words need to have precise meanings
and where this is not possible, programs and mathematics need toprovide clarity. The foundation my approach builds on is Bayesian
probability theory and, more specifically, probabilistic inference ingenerative models, a notion that I will explain and justify in the
background chapters.
9Taken together, the approach to learning and reasoning that
I consider is the following: Compositional representations thatmirror the compositional structure of the world are learned incrementally, with each step building on the components that werelearned before. On a computational level, probabilistic inference
explains the principles behind both learning and reasoning. Thesethoughts are not new (as will become clear in the backgroundchapters and in the discussion of related work), but I believe thatan exploration of these principles using a simple learner in a interestingly structured toy world will nonetheless prove insightful.
I will now state the extent of the current work using terminology introduced by Marr [Mar82]. He distinguishes three levels
that can be used to analyze a computation: The computational
level that describes the goal of a computation and the logic behind
its strategy, the algorithmic level that describes the representation of input and output and the algorithm itself, and the levelof implementation that describes how the computation is realized
physically.
There are two sides to this work and, consequently, two sides
to its claims. Any claims about the human mind are to be taken
as claims on the computational level, i.e. about what the overall
strategy is that the human mind uses when it engages in learningand reasoning. When I talk about how artificial systems could
learn and reason, my claims are not only computational-, but also
algorithmic-level claims: I will describe specific algorithms and in
as far as I claim that these may constitute part of systems thatlearns and reasons about interesting problems, these claims shouldbe evaluated literally, not just as claims about the more generalprinciples behind the algorithms.
In the next chapter, I will describe the philosophical, statisticaland computational background that provides the foundation onwhich the actual model of learning and reasoning will be built,
and which sheds light on the scientific context that gave rise tothis approach.

10Figure 1.1: Examples for structured observations

11

12

Chapter 2

Background
2.1

Representationalism

In his encyclopedic introduction to cognitive science, Paul Thagard [Tha08] suggests that the central hypothesis of the field is“that thinking can best be understood in terms of representational
structures in the mind and computational procedures that operate on those structures”. Cognitive scientists disagree about thenature of this representation, about the extent to which it is implicit and explicit, and about what exactly “implicit”, “explicit”
and “representation” mean in the first place. However, the basic
idea is clear: In order for a system to systematically derive true
statements about an object that is out there in the world andthat is not currently perceived, the information that is necessary
to derive true statements must be found somewhere within thatsystem1 . In order to think about something, there must be somemental intermediary of the object of thought. This is what I willcall the representation of the object.
This notion of representation is a very broad one. The reasonsfor choosing this interpretation are that it includes all the moreconstrained versions as a subset, that my primary concern is tolearn which constraints there are on any thinking system, andthat I therefore do not want to prematurely exclude systems thatprocess information in a way that differs from how humans do
it. In the next section, we will see that there are much stronger
constraints on which kinds of representations are suitable to serveas the objects of thought in worlds like ours.
13

1 As a consequence, if we want tofind out more about what isrepresented, we can look at thetypes of true statements that canbe derived systematically inabsence of perception. The
information that is necessary to
make these statements must thenbe part of the internal
representation.

2 By using the term “external world”,

I do not want to exclude the agent
that has these representations; it
may well represent itself.

By representational medium, I will refer to a structure that
contains representations, that is, information about the external
world2 . We can talk about these structures on different levelsof abstraction, and depending on which system we are talking
about, we might prefer different views. For example, we mighttalk about how neurotransmitter levels represent something, i.e.
talk about the implementational level, we might talk about how
the connection weights in an artificial neural network represent
something, i.e. talk about the algorithmic level, or we might talkabout how certain data structures represent something, i.e. talkabout the computational level. My considerations in the next
section will mainly be on a computational level, because the constraints I want to talk about can be expressed most clearly using
computational language.

2.2

A Language of Thought

What do we know about how these representations look like forhuman beings, and what can we infer about what they shouldlook like in any thinking system? This is the question this section
deals with, and in doing so I will follow [Fod76] and [Fod07].
There are at least three properties that any representational
medium needs to have in order to entertain complex thoughts
about the real world and to use them in reasoning: Semanticity,
productivity, and systematicity. I will first describe what each ofthese refers to, then show how another property, compositionality,
explains productivity and systematicity, and argue that it is reasonable to call any representational medium that exhibits theseproperties a language.
Semanticity means that the medium must have a capacity todescribe real and possible states of affairs, that is, it must have ameans for truth and reference. If there is no way for the medium
to represent what is real or possible, then thinking about what isreal and possible cannot be done using this medium.

3 We can always form new sentencesfrom components:
The boy who likes a girl smiles.
The boy who likes a girl who likes
a boy smiles.
The boy who likes a girl who likes
a boy who likes a girl smiles.
The boy who likes a girl who likes
a boy who likes a girl who likes aboy smiles.
...

Productivity means that there must be no in-principle, i.e.
computational-level, upper bound on the complexity of a thoughtthat can be expressed in the representational medium, just likethere is no in-principle upper bound on the complexity of a sentence in natural language3 . This captures the intuition that a
cognitive agent needs to have the competence to think any one
14

of the infinitely many distinct thoughts that it could potentiallythink. Any in-principle boundary on the complexity of thoughts
would give rise to the question what it is that makes thoughtsthat are only a little more complex suddenly unthinkable.
Systematicity means that the ability to entertain certain thoughts
must be intrinsically connected to the ability to entertain certain
others. For example, if I can entertain the thought that Spockdoes not like Italian food, then I must also be able to entertain
the thought that Spock likes Italian food, otherwise it is questionable whether I can understand what the negated version of
the thought means. Likewise, if I can entertain the thought that
Gillian likes wales, I must also be able to entertain the thoughtthat wales like Gillian.
In thinking about what it is that makes a representational
medium productive and systematic, our current best (and only)
explanation is that there is another property that a representational system suitable for thought must have and that underlies
these two phenomena: namely, that the semantics of the representations is (to some extent) compositional.
Compositionality usually denotes the claim that the meaningof a complex expression in a representational medium is (up toa limited number of exceptions) fully determined by its structure
and by the meanings of its constituents [Sza08]. However, it isdoubtful that compositionality alone can fully explain the meaning of an expression in use [Cow]. In many situations, it seems
to be the inferential role of an expression (i.e. how the expression is used) that determines its meaning. Therefore, I will takecompositionality only to mean that the meaning of a compound
expression is determined, among other things, by the meanings of
its constituents4 .

4 “The meaning of x” may not be a

Systematicity is connected to the concept of compositionality
through the fact that thoughts that are so related seem to becomposed partly out of the same semantic elements.

coherent notion. It may be that
we always need to state a context(e.g. “the meaning of x for
inference”) if we want to make thisnotion precise.

It is not clear that systematicity and productivity entail compositionality; the inference here is an “inference to the best explanation” that is supported by other phenomena, e.g. the fact that
descriptions — compound symbols where each term contributes
property specifications to the overall meaning — work the way
they do [Fod07]. What we do know is that language is systematicand productive, and that this is the case because sentences have15

constituent structure, i.e. sentences are made of smaller units thatcarry meaning. If thoughts, too, are systematic and productive,
it is reasonable to suppose that this is due to their constituent
structure — in particular if we do not know of any other explanation.

5 Although it might be more

Taken together, what we require of a representational medium
for thought is that thoughts can be combined in a productive
way, that complex thoughts have constituents which, among otherfactors, determine the meaning of the complex (or compound)thought, that the relation between compound and constituent
thoughts is a systematic relation, and that thoughts can express
both real and possible states of affairs. This is close enough toa description of the properties that both natural and programming languages have for us to call any medium that fulfills theseproperties a language of thought 5 .

accurate to talk about a languageof computation, since we do not
distinguish conscious andunconscious thought [Fod76].

2.3

Generative Models

In the last section, considerations on what thoughts need to beable to express and which principles must hold for what they can
express led us to the conclusion that any representational medium
for thought must exhibit certain language-like properties. In orderto learn more about what such a language of thought must look
like, I will now consider how it is used in thinking about the world.
Assume I give you a machine that prints money. There is apaper tray that contains some empty paper on the left, a funnel
for liquid color on the right, three rusty iron buttons with labels“$10”, “$100”, “$1000” on top, and a money tray on the bottom.
I explain to you that you first put paper in the paper tray, thenpress your button of choice, one sheet of paper gets sucked into themachine, you pour color into the funnel, the color is used to print
your note onto the sheet of paper, and a few seconds later, thenote lands in the money tray on the bottom. If everything works
right — I mention that the machine is from the last century andnot as reliable as the fancy new money printing machines.
You decide that our economy suffers from deflation and that
this is as good an opportunity as any to change that. Your firstattempt results in two notes, but each only has color on one side,
the other side is plain white. Not yet discouraged, you try again.
You follow my instructions, choose the $100 button, pour a bit of16

liquid into the funnel, and shortly after, look at your brand newnote. It does not look quite right — the green is much lighter than
it is supposed to be. “This is my last try,” you say, choose $10,
notice that the paper tray is empty, add some paper you brought,
and what you get is indeed a $10 note, but it is much larger than
the notes you know and it looks like the reason for this is thatit has a white margin around the actual print. What might havegone wrong in each of these cases?
Which properties must your representation of the machine I
just described have such that you can reason — make informed
guesses — about what went wrong in each of these cases?
First, your representation must contain the relevant information about how the system works, i.e. it must contain information
about the causal structure of the system. If your representation of
the money making machine does not contain the information thatthe liquid you put into the funnel is used as a print color, then it
is hard to figure out that you might need to put more liquid into
the machine if the print is too light. Your representation cannot
just be blank black box placeholder for the machine. It must be
a model with internal structure.
Second, you must be able to use this information to think
about how this causal structure gives rise to observations. If theinformation on how the machine works is there, e.g. because yourrepresentation contains the sequence of letters that made up my
instruction sentences, but not in a form that can be used for computation, then your representation will be of little advantage toyou. The details of how the machine works must be contained
within your representation — your model of the machine — in a
way that lets you estimate the sequence of events that lead to acertain outcome. If there is uncertainty in this generative process,then your model needs to define a probability distribution over thedifferent mechanisms that could take place and, as a consequence,over the different outcomes of these mechanisms.
Third, you must be able to invert this model, i.e. given an
observed outcome, you must be able to use it to infer what thegenerative process under this model looked like6 . Such a processoften contains hidden variables (or states), and it is often useful
to be able to infer these hidden variables, since they explain thecorrelations and dependencies in the observations [Man09]. In thecase of the money making machine, what happens between your17

6 Your model need not accurately

mirror reality; given an
observation, you need to be able toinvert your generative model, butwhat you inferred by inverting it
can be mistaken.

input and the output is a hidden variable. If you could guess
what exactly caused the failure, you could use your guess to youradvantage. If there are multiple ways that could result in thesame outcome and you are uncertain about which one actually
took place, then your representation needs to take this into account such that you can reason probabilistically. As we will see insubsequent chapters, the problem of inverting a model is the maindifficulty posed by learning and reasoning in a complex, stochastic
world.
Taken together, if a model mirrors the causal structure of someprocess in a way that lets us generate observations from the modeland that lets us invert the model to infer hidden variables, then we
will call it a generative model. In our world where there is much
uncertainty and possibly true stochasticity, stochastic generativemodels — generative models with mechanisms that contain random choices — will be of particular interest.
We have derived the properties of stochastic generative models
by thinking about what a representation needs to look like inorder to enable reasoning about complex processes like the money
making machine. It is therefore reasonable to assume that any
representational medium appropriate for thought in a world withcausal structure not unlike our own not only needs to have thelanguage-like features described in the last section, but that it
will also need the ability to concisely specify stochastic, generativemodels of the external world.

2.4

7 This is not uncontested, but as

explained in this chapter, there aregood reasons to believe it.

Probabilistic Inference

There are two related questions that need to be answered before
we can make use of the notion of a stochastic generative model
to explain learning and reasoning: First, how can we make ourtalk about generative models and, more specifically, about reasoning and learning with such models precise? Second, what are
the rules that reasoning must obey in order to systematically arrive at true beliefs? The short answer is that we can formally talkabout generative models using probability theory and probabilistic programs, and that the Bayesian interpretation of probability
theory is the normative theory for reasoning under uncertainty7 .
The long answer is the remainder of this section.
18

The laws of Boolean logic provide a normative theory of reasoning when all beliefs are either absolutely true or absolutelyfalse. Boolean logic constrains rational belief and reasoning in two
ways [Tal08]: First, enforcing deductive consistency constrains
which beliefs can be held together at any one point. Second, thedeductive rules of inference constrain admissible changes in belief.
For instance, the rule of modus ponens requires that from premises
P and P → Q, one infers Q.
If Boolean logic is the normative theory for reasoning undercertainty, then the Bayesian probability calculus is the normative
theory for reasoning under uncertainty. A central assumption of
the Bayesian probability calculus is that one’s degree of belief ina proposition x can be represented by a real number p(x) thatis between 0 and 1, with 0 meaning “x is completely false” and1 meaning “x is completely true”. For this reason, this view isalso called the subjective interpretation of probability. Together
with the two desiderata that, first, reasoning with these degrees
qualitatively corresponds to common sense and that, second, thisreasoning is consistent, the rules of the probability calculus are
uniquely determined. Only one set of mathematical operations forthe manipulation of plausibilities has all these properties [JB03].
Besides this line of reasoning8 , there are others that come to thesame conclusion, the most notable being the ’Dutch book’ argument. This argument suggests that any violation of the laws ofprobability leads to bad choices. For example, one might thenaccept combinations of gambles that each appear fair when takenon their own, but which guarantee a loss when taken together[CTY06]. In summary, the Bayesian probability calculus seems tobe the natural extension of the normative laws of Boolean logic
to the realm of uncertain reasoning.
What do the laws of probability tell us about how to reason
and, in particular, about how to reason with generative models?
A useful concept will be the notion of a hypothesis space. In
a given situation and for a given model, the hypothesis space
includes all the hypotheses the model can entertain. Intuitively,
if you think about a particular event before you have observed its
outcome, then your hypothesis space of possible outcomes includes
all the outcomes you can conceive, with some being more likely,
some less. Likewise, if you think about a particular process andhave observed its outcome but how exactly the process gave rise
19

8 This line of reasoning is formalized

in the derivation of the Bayesian
probability calculus from Cox’
axioms.

to the outcome was hidden from you, then your hypothesis space
for the hidden mechanism includes all the ways the process could
have conceivably led to that outcome, with some ways being more
likely, some less.
An idea central to the probability calculus is the evaluation of
conditional probabilities ([CTY06], [TR99]). In many cases we areinterested in the probability p(hi |d), i.e. the degree of belief in aparticular hypothesis hi (about the state of reality) given that wehave observed some data d. If we can compute this quantity for
different hypotheses hi , we can compare hypotheses and judge how
likely each is given our observations and given our prior knowledge.
We could then use this result to choose our actions such that theytake into account the different hypotheses to a differing degree. In
many cases, we can compute this quantity: Bayes’ rule (which canbe derived from the definition of conditional probability) states
how p(hi |d) can be calculated from quantities that are often known
or can be approximated:p(hi |d) =9 In particular, this problem will be

the main motivation for
introducing a new class ofadaptive importance samplingalgorithms later on.

10 As long as we are only interested

in comparing different hypotheses,
we do not need to worry about thedenominator, p(d), since it is thesame for all hi . It serves to enforce
the constraint that theprobabilities on the right add up to1, i.e. define a proper distribution.

p(d|hi )p(hi )
p(d)

(2.1)

The likelihood p(d|hi ) denotes the probability that we would
observe data d if hi were in fact the true hypothesis. In the following, we will almost always write down our hypotheses aboutcomplex processes as stochastic generative models, and the problem of estimating the likelihood of observing data d given some
generative model will be of great importance.9
The prior probability p(hi ) denotes how probable we think itis that hi is the true hypothesis before we have observed the data
d. A particularly useful type of prior are formalizations of Occam’s razor: If the notion of simplicity can be formalized, simpler
hypotheses can be given an a priori higher probability.
The posterior probability p(hi |d) denotes our belief in h after
we have observed data d. In computing this quantity, we havegiven a formal answer to the problem of inverting a generativemodel that came up in the last section. Given an observed outcome, we can compute the posterior probability of different generative models and thereby infer what the true generative model
is likely to have looked like.10
If we can formalize our beliefs within the Bayesian probability
calculus — that, as we have seen above, can be derived from20

relatively weak common sense and consistency assumptions —then Bayes’ rule normatively determines how these beliefs need
to be updated in light of new data. Before we can implement anagent that can learn and reason with representations of interestingprocesses while following the normative rules that the probability
calculus imposes on inference, there is at least one more thing weneed to do: We need to show how we can formally write down
complex generative models.
Programming languages are our best tools for the formalization of processes that generate values. Therefore, when I formallytalk about stochastic generative processes, I will use a probabilistic programming language called Church.

Interlude: Church
Church provides a computationally universal11 notation for stochastic processes and the distributions over return values that they
induce ([GMR+ 08], [Man09]). Using Church, we can simulate(i.e. generate samples from) the generative processes expressed in
the language both conditionally and unconditionally. A stochastic generative process is represented by a procedure that makes
stochastic choices; by executing the procedure, we simulate fromthe process and sample a value from the distribution on return
values induced by the process. By generalizing functions to distributions and evaluation to sampling, Church contains the pure12
subset of Scheme, a dialect of Lisp.
In the following, I will first introduce a few concepts related to
Church that we will make use of later on, then demonstrate themusing a very simple Church program.
A Church expression describes a generative process: the meaning of an expression is specified through the primitive procedureseval, which samples from the process, and query, which samples
from the process conditionally. A Church environment is a list ofpairs, with each pair consisting of a variable symbol and a value[GMR+ 08]. A Church expression together with an environment
defines a probability distribution over return values. We denote
this distribution by µexpr,env and the probability density of a particular return value v by µexpr,env (v).
Primitive procedures are deterministic functions that are boundin from the underlying Scheme that is used to implement Church
21

11 Turing completeness: Church

programs can compute every
function computable by a Turingmachine.

12 pure = side-effect freeand that are therefore a kind of black box to Church; Church
cannot introspect the evaluation process that happens when sucha procedure is applied to its arguments. Examples for primitive
procedures are the logical operators and, or and not, operatorsthat deal with data structures like pair and list and arithmetic
operators like +, - and *.
Elementary random procedures (erps) are the stochastic equivalents of primitive procedures. As was the case for primitive
procedures, Church does not introspect the evaluation processof erps. Each elementary random procedure is associated witha scoring function that returns the probability of a return value
given an environment and operand settings. Examples for erps
are flip (which throws a fair coin or, if given an argument,a weighted coin), sample-integer, beta, gamma, uniform andgaussian (which draw from the respective distributions).
A generative history for a (expr, env) pair is a sequence ofrecursive calls to eval, and their return values, made by (evalexpr env). A (expr, env) pair thus defines a distribution overgenerative histories. The distribution over return values then results from binning all histories that result in the same return value.
(2.2)(and (flip) (flip))

In this example, we use the primitive procedure and and theelementary random procedure flip. The expression (and (flip)(flip)) describes a generative process: First flip two fair coins,then return true if both come up true, otherwise return false.
There are four possible generative histories, one for each combination of return values for the flips. We get the distribution overreturn values by binning the histories: There are three histories
that result in the return value false, one that results in true, andeach history has a probability of .25. Therefore, the distribution
on return values has probability .75 for false and probability .25
for true.
In this section, I have shown a precise way to talk about learning and reasoning with generative models. Probabilistic programs
formalize the notion of a generative model and the Bayesian probability calculus imposes normative constraints on inference. In thenext chapter, I will connect these ideas to the idea of a representational language of thought and describe on a computational level
what this implies for learning and reasoning
22

Chapter 3

Model
In the last chapter, we have seen that thought requires a representational medium that allows compositional, systematic, productive representations that can represent both real and possible
states of affairs. A representational medium for thought is likely tohave the ability to express stochastic models with internal structure that explains the causal process that results in observations
and that can be used to reason backwards from observations to thehidden causes that are out there in the world. The Bayesian probability calculus provides a normative theory for reasoning and, inparticular, for reasoning with generative models.
In this chapter, I will formally tie together these observations
to explain, on a computational level, how reasoning and learning
can occur in a complex world. This entails that we first formalize
the language-like representational medium, then explain learningand reasoning as probabilistic inference, and finally show using
probabilistic programming how these two connect.
The representational medium can be formalized as a grammar
for probabilistic programs. Every program that can be expressedin this grammar defines a generative model. For the purpose ofthis chapter, we will assume that this grammar defines infinitely
many generative models m1 , m2 , ... and that at least one of these
programs captures the causal structure of whatever process weare trying to learn well enough to be useful in predicting future
observations1 . If we want to ensure that this is the case in practiceand if we do not know what the true generative process looks
like, one solution would be to use a grammar that includes allcomputable programs.
23

1 In Bayesian reasoning, if the priordistribution does not assign
nonzero probability to any
hypothesis that comes close to thetrue hypothesis, the posterior will
not do so either.

By means of our grammar, we have specified the extent of the
hypothesis space. If the grammar includes production probabilities, then we have also specified the prior distribution on hypotheses, i.e. which hypotheses are more likely a priori. For example,
if our grammar is a probabilistic context-free grammar, we haveinduced a sort of Occam’s razor prior: Hypotheses that are expressed by shorter programs are considered more likely a priori.
In the background chapter, we have encountered Bayesian inference as a means to make talk about reasoning under uncertainty
precise and as a normative theory of this kind of reasoning. However, we have not yet made an attempt to specify what exactly ismeant by “learning” and “reasoning” when expressed in this precise
language.
Formally, what it means to learn a generative model, i.e. aprobabilistic program, from observations d = (d1 , d2 , ..., dn ) is tocompute (or estimate) the posterior distribution p over all (infinitely many) generative models m1 , m2 , ... that can be expressed
within our language of thought, with the probability of each model
being p(mi |d) ∝ p(mi )p(d|mi ).

2 This approach is called MAP,

Maximum A Posteriori

Hereby, p(mi ) specifies the prior probability we assign to thegenerative model mi and p(d|mi ) specifies the likelihood that thismodel assigns to the observed data d. After this computation isdone, we know for each model mi how probable we think it is that
this one truly generated the data we have observed. When we wantto make predictions using what we have learned, we can use either
the generative model with the highest posteriori probability2 or
we can average the predictions of all generative models with eachbeing weighted according to its posterior probability. The MAP
approach is easier to compute, but, in many cases, disregards
much of what we could learn from the data and therefore we will
strive to use the fully Bayesian approach whenever possible.
By reasoning, I denote the process of determining whether aparticular proposition x is true in a real or counterfactual worldor, equivalently, whether such a world has a particular property.
When we want to reason with the posterior distribution p over generative models that we learned from our observations, we again
have two possibilities. We can either choose the less precise MAP
approach that reasons using the generative model that has thehighest posterior probability, or we can average over all models in
our hypotheses space, with each model contribution to the overall
24

conclusion in proportion to its posterior probability. In the firstcase, we compute p(x|mj ) with mj = arg maxmi p(mi |d). In thePsecond case, we compute the weighted average i p(x|mi )p(mi |d).
This takes care of both deductive and inductive reasoning, withdeductive reasoning being only a special case of inductive reasoning.
I will now use the probabilistic programming language Church
to formally describe how to connect a language-like representational medium with Bayesian inference such that we get a modelthat takes some data d1 , d2 , ..., dn as input and learns how thegenerating process out there in the world looks like3 :used to reason about thegenerating process, but this is notshown here.

; The true observations are fixed:(define true-observations(list ...)); The representational medium is specified; as an arbitrary stochastic procedure from; which we can sample expressions for; generative models:(define sample-expression(lambda () ...)); The main inference loop. Church’s query samples; conditionally from the random world that is its; first argument, returns what is given as its; second argument and conditions on the third; argument evaluating to true:(query; The generative model ’in the head’:((define hyp-expression (sample-expression))(define hyp-observations(repeat(length true-observations)(lambda () (eval hyp-expression (get-env)))))); What we want to know:
hyp-expression; What must be true for any models; we want to sample:(equal? hyp-observations true-observations)(get-env))(3.1)

Two questions are left open: First, does this work in practice?
25

3 The learned models can then beIs there a simple model for which we know that this kind of representation learning works? This is the question I want to answer
affirmatively in the remainder of this thesis. Second, this looks
computationally expensive, even for a simple example – how canthis work in practice? This is the question on which method to use
to compute the posterior distribution, and I am going to tackle itin the next chapter.

26

Chapter 4

InferenceIn the last chapter, we have seen that the problem of finding
models that explain our observations well can be modeled as computing the posterior distribution over all generative models conditioned on them generating the data, i.e. p(m|d). When we
make predictions, we can then weigh the prediction each individual model makes by how likely each model is under that distribution. One way to look at the task of sampling from the distribution
over generative models is to see it as composed of the two subproblems of model scoring and model space exploration. In thesesubproblems, the two questions we ask are: First, if we have any
given model m and data d, how can we compute p(m|d)? Second,
how can we move from model to model such that what we get are
actual samples from the distribution over models? As a precursor
to the two methods described in this chapter, importance sampling and Markov Chain Monte Carlo, I will now look at thesetwo questions in sequence:
Given observations and a model, how can we score the model?
More formally, what is the posterior probability of a certain model
m given data d? Bayes’ rule tells us that p(m|d) ∝ p(d|m)p(m),which means that we can again decompose our problem, namely
into finding p(m), the prior probability of the model, and findingp(d|m), the likelihood of the data under our model. Since what wewould like to use our score for is to compare different models, itdoes not matter that p(d|m)p(m) is only proportional to the true
posterior probability and that we do not know the normalization
constant that would turn this into the true posterior.
How do we explore the space of possible models efficiently? We
27

Scoring

Exploration

express our models in a representation language that exhibits productivity (through compositionality), therefore there are infinitely
many possible models. Consequently, enumeration is not an option. If what we want to do is to find the model with the highest
posterior score, we are looking at an optimization problem witha discrete (but not finite) set of solutions and thus can employ
search and combinatorial optimization techniques. On the other
hand, we might want to reason using the full posterior distribution over models. For example, in the case where we have two or
more models which are approximately equally likely, we might not
want to completely disregard one of the two models but use bothin our judgements and weigh their influences accordingly. In thiscase, what we need to to is to represent the posterior distribution
over models in a way that gives us an efficient method of gettingat those models that make up the bulk of the probability mass.
In the next two sections, I will present an answer to these questions. I will first describe adaptive importance sampling, an algorithm that — among other uses — can be used to efficiently compute the likelihood of observations given a model, then Markov
Chain Monte Carlo, an algorithm that can be used to sample
from the posterior distribution over models given that a method
is available to compute the likelihood of the observations.

Notation

1 i.e. vectors of random variables

Sans-serif letters, such as x, y, z, denote one-dimensional randomvariables unless stated otherwise. Bold sans-serif letters, such asx, y, z, denote multi-dimensional random variables1 . Letters in
regular, serifed fonts denote instantiations of random variables.
For example, x = x means that xi = xi for all one-dimensional
components xi of the multi-dimensional random variable x. When
we want to say that a random variable x is distributed according
to a distribution p, we write x ∼ p. By px , we then denote theprobability mass function for x if x is discrete, and the probability
density function if x is continuous. By px (x) we denote the probability mass (or density) of the value x under distribution px . By
hf (x)i we denote the expected value of function f when applied
to random variable x. The set of possible values that xi can takeis denoted by Ωxi and the set of possible values that x can take isndenoted by Ωx = i=1 Ωxi .



28

4.1

Importance Sampling

In this section, I describe importance sampling, an inference methodthat — among other uses — lets us estimate how likely an observed value is a priori under some generating distribution evenif we cannot sample from this distribution directly.

4.1.1

Introduction

Importance sampling is a technique for solving the following problem: We are given a target distribution px for which we would liketo compute or estimate the expectation of a function f : Ωx → R[Mac03, Gog09]. Examples of properties we can estimate this way
are the mean, the variance, and the prior and posterior score ofcertain values. Ideally, we would always compute the exact value
φ of the expectation:Z +∞φ := hf (x)i =f (x)px (x)dx

(4.1)

−∞

If we do not know the analytical expression for px or cannot
compute the exact expectation for other reasons, we can still estimate the expectation from samples x(1) , x(2) , ..., x(n) if we know
how to sample from the target distribution2 :
n

φ̂ =

1X
f (x(n) )
n i=1

(4.2)

However, let us assume that we do not know how to sample
from the target distribution px , but that we do know how to compute the probability of any particular value using px 3 . In thissituation, we can use importance sampling to estimate the expectation.
The main idea behind importance sampling is to use a proposal
distribution qy instead of the target distribution px to generatesamples and then, since some values will occur more often thanthey would if we could sample from px , and some less often, toreweight each sample when estimating the statistic. Therefore, wewould like to choose a proposal distribution that is as close to px
as possible. However, the only true constraint that we must not
violate in order for importance sampling to give valid estimates isthat qy is a valid importance distribution for px :29

2 This method of estimation isjustified by the laws of large
numbers which state that the
sample average converges to the
expected value.

3 For almost all interesting inference

problems, we cannot easily
generate samples from the
distribution of interest. Here, thenumber of values in Ωx is usually
very high. By definition, correct
samples will mostly consist ofx ∈ Ωx for which px (x) is high –but how can we know where px (x)is high without looking at allvalues (which might be
intractable)? [Mac03]

4 One way to formalize the notion“easy to sample from” is to saythat the distribution can be
expressed in a product form and,in this form, can be specified inpolynomial space (depending on
the number of random variables).
[Gog09]Definition 4.1 qy is a valid importance distribution for px if we
can sample4 from qy , if for all y ∈ Ωy , we can compute qy (y) and
if for all x ∈ Ωx , if px (x) > 0, then qy (x) > 0.
We will now derive how to estimate the expectation hf (x)ifrom samples drawn from qy , first for normalized densities, thenfor the more general case of unnormalized densities. Given a value
y drawn from qy , we define its importance weight as follows:
w(y) :=

px (y)qy (y)(4.3)

Using this definition, we rewrite the expression for the expectation hf (x)i:Z +∞φ=w(y)f (y)qy (y)dy

(4.4)

−∞

We can now estimate the expectation φ by using samples
y , y (2) , ..., y (n) from the proposal distribution qy adjusted bytheir importance weights5 :(1)

5 This is justified by the fact that

formula 4.4 denotes an expectation
and by the laws of large numbers,
as before.

6 For Bayesian inference, this is acommon situation since thecomputationally most difficult
part is to compute the normalizing
sum in the denominator:p(h|d) = Pn1Xw(y (i) )f (y (i) )
φ̂ =
n i=1

(4.5)

What if we know px and qy only up to a multiplicative constant6 ? It turns out that we can adjust our estimator for this case[Ber]. By p∗x , qy∗ , and w∗ , we denote the unnormalized versions ofpx , qy , and w. zp and zy denote the normalization constants. We
start out by rewriting our estimator 4.5 using this terminology:p(d|h)p(h)i p(d|hi )p(hi )n

1 X px (y (i) )φ̂ =f (y (i) )n i=1 qy (y (i) )

(4.6)

n

=

=

1 X p∗x (y (i) ) zq
f (y (i) )n i=1 qy∗ (y (i) ) zp
Pn p∗x (y(i) )1(i)i=1 q ∗ (y (i) ) f (y )nyzp zq

(4.7)

(4.8)

All that is left to do is to show that we can estimate the denominator from samples drawn from qy :
30

zp
=
zq

R +∞
−∞

zq
Z +∞

=
−∞
Z +∞

=
≈

p∗x (x)dx(4.9)

p∗x (x) qy∗ (x)dxqy∗ (x) zq(4.10)w∗ (x)qy (x)dx(4.11)−∞nXw∗ (y (i) )(4.12)

i=1

We can now estimate expectations using importance samplingeven without normalized densities:

φ̂ =

Pn
w∗ (y (i) )f (y (i) )
i=1
Pn
∗
(i)
i=1 w (y )(4.13)

In summary: If we have some valid importance distribution
and if we can compute the unnormalized score of the samples
under the posterior, then we can use importance sampling to estimate arbitrary expectations for the posterior distribution.

31

4.1.27 This section require someunderstanding of how the Church
evaluator works. For backgroundon metacircular evaluation in
Scheme, see [ASS]; for Church, see[GMR+ 08].

8 By *, we denote the wildcard, i.e.

Probabilistic Programs

We will now describe how to apply importance sampling to probabilistic programs7 . We first state what we want to accomplish
illustrated by an example, then describe a simple algorithm that
accomplishes it, followed by an algorithm that accomplishes thesame goal much more efficiently.
We presented importance sampling as a means to estimate a
expectation f : Ωx → R for a target distribution px . Now, let
our target distribution be the conditional distribution defined by
the following program constrained to the return value (pair true*)8 :an unconstrained return value.

((lambda (x y) (pair (and x y) x))(flip 0.01)(flip 0.01))(4.14)

If we repeatedly run this program without constraint, the mostsequence of samples we get is likely to start with (pair false
false) (pair false false) (pair false false). The numberof samples that fulfill the constraint (pair true *) is likely to
be very small. As a consequence, if we want to efficiently sample
from this distribution, running the program forward and rejecting
all samples that are no good is very inefficient.
Let us assume that we are not interested in the samples themselves, but that we want to compute some expectation for thistarget distribution. In other words, we want to compute a function of the sampled values from this program but we are interested
only in those values where the first value of the returned pair isequal to true. As was the case in the importance sampling setup
described above, it is not clear how to sample from the target
distribution I just described. However, if we could sample from adifferent distribution and reweight each sample according to theratio of true score and actual score, then we could estimate expectation such that the result is as if we could sample from thetrue distribution.
A starting point for this idea is to take samples from the unconstrained program and then reweighting the samples according
to the ratio of constrained program score to unconstrained score.
This approach — sampling from the prior and reweighting accordingly — is called likelihood weighting. In order to reweightthe samples, we need to know the probabilities of return values
32under the (constrained) target distribution up to a multiplicative constant. Since all samples that do not fulfill the constraint
have probability 0 and since we do not need to renormalize, we
can directly use the probabilities we get from evaluating the unconstrained program, which means that all weights end up being
either 0 or 1 and that all we do in this case is to reject samples
that do not fulfill the constraint. This has the same problemsnaïve rejection sampling has, namely that we cannot use many of
the samples we take and thus waste computation time. In our example, we discard all samples where not both of the two (flip)s
happen to return true. For programs where most of the values
sampled from the prior distribution have probability 0 in the posterior distribution, we need better proposal distributions than theprior.
In order to devise a better proposal distribution, let us go backto program 4.14 and go through the sequence of evaluation steps
that would need to happen if we wanted to sample from the target
distribution where all values fulfill the constraint (pair true *):1. The first step in the evaluation is the application of the operator with expression (lambda (x y) (pair (and x y) x))
to the two operands with expressions (flip) and (flip).
Like Scheme, Church9 is an applicative-order language. Thismeans that at procedure applications, the operands are evaluated before the operator is applied. Before we have started
to apply the operator to the operands, we do not know how
to constrain the operands such that we get the return value(pair true *) out of the application. Therefore, we needto delay the evaluation of the operands until they are required.
2. Next in sequence, we evaluate the procedure body of (lambda(x y) <body>) with x bound to the delayed value for the
first (flip), y bound to the delayed value for the second(flip), and the constraint (pair true *) on the wholeexpression. This means that we evaluate (pair x (and xy)), an application of the primitive procedure pair. What
we need to do in order to sample from the distribution where
all values match the pattern (pair true *) is to invert theprimitive procedure pair to find out which operand values
result in the return value that matches this pattern. Suchan inversion would tell us that the first operand can be any
33

9 More precisely: MIT-Church

without importance-eval isapplicative-order.

value and that the second operand must be true. Withknowledge about how the operands must look like, we cango on evaluating the operands.
3. We evaluate the first operand of (pair (and x y) x), theexpression (and x y), with constraint true, notice that it
is a primitive procedure application and therefore we needto invert the procedure. Since the only operand values forwhich and can return true are true for both operands, weknow what to do: We need to evaluate both operands withconstraint true. Both operands are variable lookups, andfor both operands the value has been delayed. We force
both operands with the constraint true, and in doing so
apply the elementary random procedure (flip) with constraint true twice. If we want to sample from the target
distribution for the overall expression, we know that the two
applications both need to return true, therefore we set theelementary random procedures to true. Having evaluatedboth operands, we now apply the primitive procedure andwhich results in the desired value true.
4. We evaluate the second operand of (pair (and x y) x),
the expression x, notice that it is a variable lookup which
has already been forced and therefore look up and return its
value true.
5. Having evaluated both operands for (pair (and x y) x),
we apply pair to the returned values true and true which
results in the overall result (pair true true) — a valuethat matches our constraint (pair true *)!

We will now review the three ways in which we had to modify the evaluation of the program in order to get a sample that
fulfills the constraint, i.e. a sample that does not have probability 0 under the posterior distribution. In particular, we willshow how these modifications fulfill the criteria we have posed
for a valid importance sampler in the last section: That we canalways compute the probability of a return value under the proposal distribution and that, if the probability under the posterior
distribution is greater than 0, the probability under the proposal
distribution is greater than 0, too.
34

Setting of elementary random procedures
If we encounter an elementary random procedure application like(flip) and know that our target distribution has a certain return
value for this application, e.g. true, we set the application to
the desired value. We know both the posterior score10 and the
proposal score, whereby the latter is 1 if we can successfully set
the value. If we cannot set the value because the elementary
random procedure assigns probability 0 to it (and therefore needto assign a proposal score of 0), we know that this is also the caseunder the posterior distribution. Since only these two cases are
possible, both criteria are fulfilled.
Inversion of primitive procedures
At applications of primitive procedures like pair and and where
we have a constraint on the return value, we invert the procedure
to find out which operand values can result in the desired return
value. For each primitive procedure, we therefore store an inverse
procedure that, given a return value, returns a list of n possible
operands. We uniformly draw one operand choice and go on withthe operand constraints being equal to the chosen operand values11 . This adds a factor of n1 to the proposal score for this sample. Since we know that our inverses contain all possible operandvalues that could lead to a certain return value, we know that weare not excluding any value that has a probability greater than 0
under the posterior.
Delayed evaluation
Instead of evaluating operands before applying compound procedures, we delay the evaluation until the value is actually needed.
Delaying the evaluation allows us to push constraints further down
the evaluation than would be possible otherwise, where we would
have to evaluate the operands of compound procedures without
constraints which could result in many samples with probability
0 under the posterior distribution.
What connects these three ideas is that we push the available
evidence — the constraint — down the evaluation branches inorder to sample from a distribution that is close to the posterior
and in particular does not return samples that have probability 0
under the posterior, since these samples are useless for estimating
the expectation we care about. In the next section, we will see how
we can do even better by adapting the proposal distribution step
35

10 Given an arbitrary value, anelementary random procedure canreturn its likelihood.

11 Whereas one solution is torandomly choose one of these
inverses and then constrain theoperands to have the desired
values, this will result in a
proposal distribution that is not as
close to the prior distribution as
we might wish. We can use
sequential inverses as a remedy:
We first choose a sequence on theoperands, then evaluate insequence all operands as long as
there are inverses that can matchany operand choice. When this is
no longer the case, we pick an
inverse at random that matches
our initial operands and force theremaining operands to the desired
inverse values.

by step such that even in those cases where pushing the evidence
was not sufficient to avoid a sample with probability 0 under theposterior, we can learn to avoid making the same mistake in futuresamples.

36

4.2

Adaptive Importance Sampling

In this section, I describe a version of importance sampling that
improves over time. By learning from the samples it takes something about the distribution it is sampling from, this method canincrementally achieve lower rates of rejected and low-probability
samples and thus it can result in more accurate estimates.

4.2.1

Introduction

Adaptive importance sampling denotes a version of importancesampling where we do not take all our samples from the same
proposal distribution qy , but instead sample from a sequence of
(1)
(2)
(n)
distributions qy , qy , . . . , qy . This is of particular interest if
each sample gives us information about how the posterior distribution looks like, such that we can improve our proposal distribution(i)qy in the following step.
According to [RC04], it is possible to keep the original importance weights in this setup and still produce an estimate thatconverges to the true estimate. This means that our estimator is
stillPnw(y (i) )f (y (i) )Pnφ̂ = i=1(i)
i=1 w(y )(4.15)

with the weights being defined as follows:px (y)

w(y) :=(i)(4.16)qy (y)(i)

Here, qy refers to the proposal distribution that was used togenerate sample y.
However, there is reason to look into modified estimators inorder to arrive at more stable estimates [CMMR09]. In particular, if the (unnormalized) weights from one proposal distribution
are very large, they will dominate the other samples in the final
approximation, no matter how efficient the other proposal distributions are.
37

4.2.2

Probabilistic Programs

I will now describe how to apply adaptive importance sampling
to probabilistic programs. We have seen that the goal of adaptation is to change the distribution we are sampling from suchthat we get samples that are distributed more like those fromthe posterior and less like those from the initial, possibly inefficient importance distribution. We also know that we must always
maintain a valid importance distribution to keep the guaranteethat our estimated expectations approximate the true value. In
the following, I present a framework for adaptive importance sampling with probabilistic programs that can accommodate different
adaptation policies and, at the same time, makes it easy to ensurethat we maintain a valid importance distribution.
I will proceed as follows: First, I define what I mean by a valid
adaptation policy and shortly review the programming language
constructs that will play a central role in our adaptation policies
for probabilistic programs. I then formally characterize the classof adaptation policies that are possible within this framework. I
define the concept of an importance table and, using this concept,
characterize a class of valid adaptation policies for probabilistic
programs and prove that any policy within this class maintains avalid importance distribution.
Definition 4.2 π is a valid adaptation policy if, given a valid im(t)portance distribution qy for the target distribution px and some(t)information i, π(qy , i) returns a new valid importance distribu(t+1)
tion qy.
We will see that, in our framework, adaptation always happens when functions are applied. Therefore, the two language
constructs that are at the center of adaptation are both functions: primitive procedures and elementary random procedures.
We have seen both constructs in our introduction to Church.
Primitive procedures are deterministic functions like and, or, andpair. For many primitive procedures, inverses exist. This meansthat a primitive procedure p is associated with another primitive
procedure inv-p that, given a desired return value, returns the listof operand assignments that would result in this return value if p
was applied to any of the assignments. Elementary random procedures are stochastic functions like flip, sample-integer andgaussian; they do not have inverses, but they do have a scoring38

function that returns the probability of a return value given an
environment and operand settings.
I will now characterize the class of adaptation policies that arepart of the framework I am about to describe. As first introducedin the section on importance sampling for probabilistic programs,
we are still in a setup where we try to push information about thetarget value of the evaluation as far down the evaluation tree as
possible. This means that at each evaluation, we have information
on what the target value of this evaluation should be, be it a fixedvalue or the wildcard setting that does not constrain the return
value.
One way of looking at any adaptation policy is to see it as
separated into information collection (what information on how
the posterior looks like is stored during the evaluation process),
information propagation (what additional information is deduced
from what is collected), and information usage (how the stored
information is used to change the importance distribution). I will
first introduce the data structure that is used to store information,
the importance table, then describe when and how information isstored, propagated, and used.
The importance table is a hash table that uses (expr, r-env)
pairs as keys and association lists12 ((v1 , w1 ), (v2 , w2 ), ..., (vn , wn ))as values. In the introduction to Church, we have seen that an expression together with an environment defines a distribution overreturn values. This distribution does not depend on the complete
environment, but only on part of it (i.e. those variables within
the environment that are actually used in the expression). These
distributions are what we will store information on; in particular,
we will store information on what values these distribution can return and how probable the values are. This is why the hash table
keys each consist of an expression and an relevant environment,
and this is why the hash table values are association lists of return
values associated with weights13 .
By ωexpr,env (v), I denote the function that looks up the importance table entry for the pair (expr, r-env) and returns theweight that is associated with the value v in the association list
for this pair. If no entry is found in the importance table for this(expr, r-env, val) triple, then ω returns a default score d as
defined by the active adaptation policy14 .

12 An association list is a list ofpairs. The first element of the pairis called the key, the rest of thepair is called the datum.

13 There are adaptation policies forwhich it is useful to store morethan a single real number. For
example, one might want to store alist of importance weights for each(expr, r-env, val) triple. I limit
my analysis to those that store asingle real-numbered weight

14 We might want to use adaptation

In our framework, information collection happens at the eval39

policies that specify more about
the weight lookup function thanjust the default value. For
example, for continuous values it
could be useful to take into accountclose neighbors of the value that islooked up. I will not talk about
these kinds of extensions here.

uation of erp applications, whereas information propagation andusage happen when primitive procedures are applied. In the following, I will first explain these three policy elements, then describe more formally what our class of adaptation policies looks
like:Collecting Information
After the application of an elementary random procedure withtarget value v (which may be a wildcard), we have new information: We now have another pair of (unnormalized) posterior scoreand (unnormalized) importance score for this return value in thecontext of a particular expression and environment. At this point,
we use a function f that is supplied by the policy to compute the
new weight of this target value for the (expr, env) pair that wejust evaluated:

w = f (p, q)(4.17)= f ((p1 , ..., pn ), (q1 , ..., qn ))(4.18)

Here, pn is the score of the return value under the target distribution and qn is the score of the return value under the importance
distribution. Since adaptation policies might take into accountearlier evaluations of (expr, env) that resulted in v, we not only
allow the function that computes the weight to depend on thelatest scores, but on all previous scores. The weight w that isreturned by f must be a real number between 0 and 1. We thenadd (v, w) to the association list that is stored in the importance
table for the current (expr, r-env) pair.
Propagating Information
At the application of a primitive procedure with a fixed target value v, we propagate information from the operand expressions to the overall expression. We first get a list of all inverses(inv1 , ..., invn ) that lead to this target value, with each inverse
invi consisting of a list of operand values (op1 , ..., opm ). Using
these values and the importance table, we compute the overall
weight of the (expr, env) pair that we are currently evaluating
as follows:
40

w=

n Y
m
X

ωexprj ,env (invi,j )(4.19)

i=1 j=1

We then add (v, w) to the association list that is stored in theimportance table for the current (expr, r-env) pair.
This propagation policy assumes that the operand values are independent, i.e. that evaluating one operand does not affect theevaluation of other operands. When we use delayed evaluation,
this is no longer true. For example, when we evaluate ((lambda(x) (pair x x)) (flip)) constrained to the return value (pairtrue false) with the operand (flip) delayed, this policy cannot
learn that the pair application cannot return (pair true false).
This is not a problem for the current project for two reasons.
First, it does not result in an invalid propagation mechanism,
only in a less efficient one. When we choose the wrong inverse, theresulting sample gets rejected and does not factor into expectation
computations. Second, when we later apply our methods to learn
programs, we limit ourselves to simple programs without lambdas(since the required methods to switch between programs without
lambdas and those with lambdas are not implemented yet; I will
explain this in more detail later on).
Using Information
Our goal is to sample each inverse with a probability proportional
to its total posterior score, i.e. we want to use each operandassignment as frequently as it would be used under the posterior distribution. Therefore, it is at the application of primitive
procedures with a fixed target value v that we allow our adaptation policies to use stored information. We look up all inverses(inv1 , ..., invn ) and thus know the operand settings (op1 , ..., opm )for each inverse. We use this to compute a weight wi for each
inverse:

wi =

m
Y

ωexprj ,env (invi,j )(4.20)

j=1

We then sample the inverse that we are going to use from the
distribution over inverses where each inverse has a probability
proportional to its weight. Thus, an adaptation policy can change
the relative frequency of different inverses and, ideally, change it
41

in a way that makes the inverse usage close to that under theposterior distribution.
We can now say more precisely what an adaptation policy
consists of:Definition 4.3 Within our framework, an adaptation policy π
is a tuple (f, d), where f is a function (P , Q) → [0, 1] and d
is a default weight that is used when no weight is stored in theimportance table for an (expr, r-env, v) triple. Both p ∈ P
and q ∈ Q are unnormalized probabilities.
What remains to be shown is under which conditions sucha policy is valid, i.e. under which conditions the policy creates a
new valid importance distribution if applied to a valid importance
distribution.
Theorem 4.1 π is a valid adaptation policy if π is a policy (f, d)with the property that f (p, q) > 0 if any pi > 0, and that d > 0.
Before we can prove that this statement is true, we need to review the concept of a generative history and to introduce conceptof a valid importance table.

15 In our analysis, we assume that

inverses are complete, i.e. containat least all operand settings thatcan lead to a return value v.

In our introduction to Church, we have seen that a generative
history for a (expr, env) pair is a sequence of recursive calls
to eval, and their return values, and that a (expr, env) pairthus defines a distribution over generative histories. This gives
us another way to think of inverses: When we invert a primitive
procedure to get all the operand settings that can result in a return
value v, we effectively partition the space of generative histories forthe expression that contains the primitive procedure applicationby the different ways to get the desired value v.15
Definition 4.4 A valid importance table is an importance table
where (v, 0) is stored in the association list for (expr, r-env)
only if no generative history we get from evaluating expr in r-env
results in value v.

42

Proof Structure
Let µ be an adaptation policy with f (p, q) > 0 whenever any pi >0, and d > 0. The proof that shows that µ is a valid adaptation
policy will proceed as follows:
1. If we have a valid importance table t and a valid proposal
distribution q, then µ constructs a new valid proposal distribution q + using the information in the importance table.
2. The importance table ti+1 that µ constructs from a valid importance table t by information collection and propagation
is a valid importance table.
∴ If we start out with a valid importance table ti and a valid
proposal distribution qi , µ constructs a new valid proposal
distribution qi+1 via importance table ti+1 . Therefore, µ isa valid adaptation policy.
Note that the empty importance table is a valid importance
table, that we can therefore always start with a valid importance
table and that we need not make the availability of such a table part of the requirements of a valid adaptation policy as described in theorem 4.1. Similarly, note that — as seen in likelihood
weighting — that the prior distribution for a program is a valid
importance distribution.

43

Importance
Prior
Table
Distributionttt

Proposal
Distribution

1

q

q

2

q

q

3

q

q

1

2

3

Proof, Part 1: Constructing Valid Proposal Distributions
Assume that we have a valid proposal distribution q for a certain
program, i.e. a distribution over generative histories where eachhistory that is possible under the posterior distribution p is also
possible under q. Further assume that we have a valid importance
table t.
We will now show that the adaptation policy µ uses the importance table t to construct an adapted proposal distribution q +that is valid :1. If an (expr, env) pair is in the importance table t with avalue v and a weight 0, then no generative history we getfrom evaluating expr in env results in value v.
2. If there is no generative history for a (expr, env) pair that
returns v, then there is no generative history in the posterior
distribution over histories that includes a subhistory where(expr, env) evaluates to v.
3. If h is a generative history that is impossible under the posterior, and if q + is equal to valid q except for the fact thath is excluded from the set of possible generative histories,
then q + is a valid proposal distribution.
∴ If we have a valid importance table t and a valid proposal
distribution q, then µ constructs a new valid proposal distribution q + .
Statement 1 is true by the definition of “valid importance table”, statement 2 follows from subset reasoning and statement 3
follows from the definition of “valid proposal distribution”.

44Proof, Part 2: Constructing Valid Importance Tables
Assume that we have a valid importance table ti . We will now
show that the adaptation policy µ uses the information it collects
and propagates to construct an importance table ti+1 that is again
valid.
1. The importance table ti+1 is equal to ti except for updates
two adaptation rules.
2. Rule 1: Information collection at elementary random procedures:i As a consequence of the rules for the weight computation function f , we only update ti+1 with (expr,env), value v, weight 0 if an erp application returns
the score 0 for v.
ii If the erp application returns the score 0 for v in thecurrent environment, we know that there is no generative history for (expr, env) that results in v (since
this is what a score of 0 means).
∴ Adaptation at elementary random procedures preserves
importance table validity.
3. Rule 2: Information propagation at primitive procedures:i As a consequence of the sum-product propagation rule,
we only update ti+1 with (expr, env), value v, weight0 if ti tells us that each possible combinations of operandvalues that could lead to v (as determined by the appropriate inverse procedure) has weight 0 in the current
environment. If this is the case, then, since ti is valid,
no combination of operand settings has a generative
history under the posterior.
ii If all operand assignments that could lead to the return
value v are impossible under the posterior distribution,then we know that the return value itself is impossible under the posterior distribution for (expr, env),
i.e. no generative history for (expr, env) exists that
results in v.
∴ Adaptation at primitive procedures preserves importance table validity.
∴ The importance table ti+1 is valid.
45

Importance
Prior
Table
Distributionttt

Proposal
Distribution

1

q

q

2

q

q

3

q

q

1

2

3

4.2.3

A Constraint Propagation Policy

Having established a class of valid adaptation policies, it is now
easy to describe the constraint propagation policy that we will use
to efficiently score observations from tree-generating programs. I
start by introducing some terminology, then describe the actual
policy.

16 SAT: The Boolean satisfiability

problem

If a value v is never returned by the distribution induced bya given (expr, r-env) and we are evaluating this pair with constraint v, then we call this situation a dead-end. We call therecorded fact that this (expr, r-env) pair cannot return thisvalue a nogood (both based on terminology used in the SAT16 community). Using this terminology, the goal of our constraint
propagation policy is to store knowledge about the return values of (expr, r-env) pairs and to use this knowledge to avoid
dead-ends.
This is a formal description of such a policy:1 if any p > 0if (p, q) =
0 otherwise
d=1(4.21)(4.22)

Since this policy fulfills the requirements that that f (p, q) > 0
if any pi > 0, and that d > 0, it is a valid policy.
In the last sections, we have derived a class of importancesampling algorithms for probabilistic programs that can be used
to efficiently compute expectations. In particular, we have specified one algorithm in this class, a constraint propagation algorithm, that propagates information about which values cannot
be returned by elementary random procedures up at applications
and thus avoids ahead of time the choosing inverses that containthese values. Using this algorithm, we will be able to computethe likelihood of observations under tree-generating programs byquickly excluding all those configurations of the program from ourconsiderations that could not have given rise to the observations.

46

4.3

Markov Chain Monte Carlo

Before I introduce the practical setup we use to demonstrate structure learning, I will shortly describe the second class of inference
methods we will employ, Markov Chain Monte Carlo (MCMC),
and how they are used in Church for conditional sampling.

4.3.1

Introduction

In contrast to importance sampling methods, we are now not onlyinterested in computing the expectation of some function applied
to samples from a complex probability distribution, but we wantto (approximately) sample from the distribution17 . I will first
introduce some background concepts, then explain the idea behind
MCMC.
A Monte Carlo algorithm is an algorithm that arrives at its
result by repeatedly sampling from a probability distribution.
A Markov chain is a sequence of random variables where eachvariable is independent of all of its predecessors given its immediate predecessor. Under certain conditions18 , this chain converges
to a stationary distribution as its length increases, i.e. the probability that a variable in the chain takes on a certain value converges to a fixed quantity [GY06]. Hereby, it does not matter fromwhich state we start, given that we wait long enough for the chain
to converge.
The main idea behind MCMC methods is to construct a Markov
chain that has as its stationary (or long-run) distribution the distribution we want to sample from and that is cheap to compute.
Then, by recording the sequence of states we visit when simulating the Markov Chain, we accumulate (correlated) samples fromthe target distribution. If we want to sample according to theprobability under the distribution of interest, this stochastic walkthrough state space must be such that we spend most of the time
producing samples from high-probability regions.

4.3.2

The Metropolis-Hastings Algorithm

The Metropolis-Hastings (MH) algorithm is the most popularmethod to construct a Markov Chain that has the properties
required to converge to the target distribution, and most other47

17 Typically, it is very difficult tosample from the distribution
directly because the state space islarge and we do not know whichparts of the state space containhigh-probability values. MCMC
methods are used to overcome thisdifficulty.

18 Convergence of a Markov chain

with transition kernel K to the
distribution p requires two things:
First, p is an invariant (orstationary) distribution for K, i.e.
p = pK. Second, K must be
ergodic. A kernel is ergodic if it isirreducible (any state can bereached from any other state) andaperiodic (the stochastic walk does
not get stuck in cycles). [Bon]MCMC algorithms can be seen as special cases or extensions of
this method [AdFD03].
The main ingredient for MH is a proposal distribution thatspecifies how to sample a candidate next state given the current
state of the Markov chain. Starting from this proposal distribution, MH constructs an acceptance function. Together, proposal
distribution and acceptance function specify a Markov chain thathas the desired target distribution as its stationary distribution.
Just as was the case for importance sampling, the choice ofthe proposal distribution is crucial: If the probability is very lowthat we propose a sequence of steps that lead to a region that has
high probability under our target distribution, then it can takea long time until the chain converges and, consequently, until we
get samples that accurately represent the target distribution.
The acceptance function gives the probability of accepting thiscandidate as the actual next state. If the candidate is rejected, thecurrent state becomes the next state. If the target distribution isp and the proposal distribution q, then the acceptance probabilityof going from current state s to candidate state s∗ is given by∗)q(s|s∗ )A(s, s∗ ) = min{1, p(sp(s)q(s∗ |s) }. The normalization constant for
p and q cancels, therefore all we need to know about the target
distribution is some quantity proportional to the probability of avalue under this distribution for all values.

4.3.3

19 The question whether adaptive

importance/rejection sampling on
its own is an useful method forprogram learning is still open.

MCMC and MH in Church

We have already seen that the probabilistic programming language Church contains a language construct for sampling fromconditional distributions, query. In the MIT-Church implementation, mh-query samples conditionally by using the MetropolisHastings algorithm. In light of the fact that this is currently the
only universal inference algorithm that works reasonably well for
program learning19 , I will now give an overview on how the universal mh-query works.
Before we start, I will give a simple example that illustrates
how mh-query is used in Church. Assume I have flipped an unfair coin ten times and saved the resulting sequence of heads(encoded by true) and tails (encoded by false) into a variable48

true-coin-flips:(define true-coin-flips(list false false true true false
false false true false false))(4.23)

Now I would like to infer how biased the coin was – the weightof the coin – but without thinking about a special-purpose way to
do inference. What I would like to do is to let Church construct
a Markov chain such that visiting the states of this chain is (inthe limit) equivalent to sampling from a distribution over weights
conditioned on coin flipping returning the results as specified intrue-coin-flips. Here is how to write this down in Church:(repeated-mh-query 10; Random world:’((define hyp-coin-weight (uniform 0 1))(define hyp-coin-flips(repeat 10 (lambda () (flip hyp-coin-weight)))))(4.24); What we want to know:’hyp-coin-weight; Condition:’(equal? hyp-coin-flips true-coin-flips)(get-env))

Using (repeated-mh-query 10 ...), we first instruct Church
to take ten samples from the conditional distribution we are about
to describe. Then we write down a generative model for our observations, the results of the coin flipping. The query part contains
the one variable of the generative model that we are actually interested in, i.e. that we would like to sample: the hypothetical coinweight that is inferred by conditioning the observations generated
by the generative model to equal the true observations. Running
this results in an output that looks like this:(0.106 0.335 0.174 0.443 0.381
0.584 0.416 0.312 0.467 0.529)(4.25)

What we got are ten approximate samples of the coin weightin the generative model conditioned on our generative model resulting in the actual observations.
Having seen how mh-query can be used to conditionally sample from generative models, I will now relate this to the previous sections by explaining how the Markov chain looks like that49

Church constructs in order to compute samples. In order to doso, I will answer three questions (following [GMR+ 08], [Man09]):First, what is the state space of the Markov chain? Second, whatis the initial state? And third, what is the proposal distribution?

20 More formally, the computation

trace is a directed acyclic graphcomposed of two directed trees,
one tree for the environment
structure of the program, and one
tree for the evaluation structure,
where an evaluation node points toa subnode for each recursive callto eval.

21 Depending on the program, we

may have to force it into a state
where the predicate is true, anddepending on the program, thismay be difficult without a method
similar to the constraint
propagation policy of our adaptive
importance sampler.

22 How well MCMC performs

depends strongly on how good the
proposed states are, i.e. how
quickly they explore thehigh-probability regions of thestate space. Using adaptation to
construct better MCMC proposals
is an issue that deserves future
research.

Intuitively, one could imagine that the state space is exactly
the space of possible return values, since at each step of theMetropolis-Hastings algorithm, we want to sample one value. For
example, for the query above that returns coin weights, this would
be the interval [0, 1] of real numbers. In fact, the state space ofthe Markov chain that mh-query constructs is the space of computation traces of the Church program defined by the query, i.e.
not only the space of return values, but the space of return values
augmented by information on how the return values were constructed20 . Each state contains the dependency structure of thecomputation and, in particular, contains information on how the
return value depends on the stochastic choices that were madeduring the evaluation.
We get the initial state, i.e. the initial trace, by executing thequery expression and recording the recursive calls to eval and theenvironment structure along the way21 .
Knowing what the state space is (the space of all computation
traces that lead to return values for which the condition predicate
is true) and what our initial state is (a single trace that we get byevaluating the query program), all that is left to specify to makethis a complete Markov chain is how we get from state to state,i.e. how we propose new candidate states.
In order to create a new trace, we first randomly select22 aplace in the current trace where a random choice was made andthen re-evaluate the choice. In order to keep the trace consistent,
i.e. a valid evaluation history, we then propagate the changes inthe values of subexpressions and bound symbols along the trace.
The Metropolis-Hastings rule then tells us whether to accept thecandidate trace or whether to reject and keep the old trace; if thecondition predicate is false, we always reject.
Taken together, universal conditional sampling in Church is
implemented using a stochastic walk over computation traces thathas the distribution of interest as its long-run distribution.
Now that we have seen two inference methods that can be used
to score generative models given some observations and to explore
the space of generative models, we can describe the circumstances
50

under which we will apply these methods to show how learning
generative models with language-like representations can work.

51

52

Chapter 5

Setup
The general setup for our demonstration of inductive learning will
be as follows: A structured world generates observations and thetask of the learner is to construct a generative model of the worldthat closely mimics the actual world and that therefore can beused in reasoning about the world. I have described both thegeneral idea and and a specific algorithm for learning such models
in previous chapters; now I want to demonstrate how this turns
out in practice. This requires that we determine what the world
should look like to make the demonstration meaningful and what
the representation language should be.

5.1

A Structured World

I start by describing the four desiderata for a world in which a
suitable demonstration of the kind of representation learning I
have described so far can take place.
First and foremost, the world must contain interesting structure. What I want to demonstrate is the incremental learning ofstructured representations. If the world itself does not containinteresting structure, accurate representations of the world will
not contain structure either. What makes structure interesting?
More precisely: What makes us say that a program that generates
observations contains interesting structure? Most fundamentally,
the program must be shorter than the variety of observations it
generates: There must be some way in which it compresses thedata it generates, some way in which it abstracts from the data. At
53the same time, the generating program itself must contain at least
some information: If the generating program can be expressed too
concisely, e.g. as is the case for observations that consist of a longsequence of only 0s, we would not call it interestingly structured
either.
Second, the observations must be such that it is possible torecover the underlying structure to an interesting extent. Thisentails two requirements, one based on in-principle considerations,
one based on considerations of computational efficiency. Since theefficiency requirement is better seen as a constraint on the learnerand its representation language and inductive bias, we are goingto use than on the actual world, I will deal with it in the next
section. However, what is relevant here is that the observationmust contain sufficient information to probabilistically identify
the correct hypothesis (or some small set of likely hypotheses)
in principle. If an observation contains only one bit, it can, on
average, eliminate at most half the probability mass.
Third, the process that generates observations from hidden
structure must be stochastic. If the process were deterministic,
the same hidden structure would always result in the same observations, we would make one observation and then search throughour representational medium, looking for the shortest programthat results in the observed value. On the other hand, if theprocess is stochastic, then making additional observations can result in additional information about the structure of the generative process. For example, it can help us to probabilisticallydistinguish the generative process (lambda (a a) (flip)) from(lambda () (flip) (flip)). This tells us something else: The
stochasticity of the process must not be limited to noise that is
added after the observations have been generated, not just noiseat the bottom, but stochasticity that is added within the generative
process. Otherwise, we cannot gain additional information about
the internal structure of the generative process from additional
observations.
Fourth, the world must be simple. We are going to use theprobabilistic programming language Church, therefore simple isdefined relative to this language: The longer the shortest complete
description we can give for a world, the more complex it is. Our
goal is to have worlds that are simple by this measure and thatnonetheless satisfy the criteria given above.
54

Since Church is based on Scheme, its fundamental data structure are lists1 . One natural choice both for the internal structureof the generative processes that define our world and for the observations is to make them lists of lists – trees, in other words.
If the world consists of tree-generating programs with stochastic choices and abstraction, and the observations consist of thetrees generated by these programs, then all of the requirements
we named above are satisfied. In particular, this choice has thedesirable property that the structure of the observations mirrors
the structure of the generative process to some extent, thereby
providing information that helps to infer from observations what
the underlying process looks like.
Formally, the syntax for tree-generating programs looks likethis:tree ::= branchbranch ::= ’((lambda (’ var ’) ’ branch ’) ’ branch ’))’ |’(if (flip) ’ branch branch ’)’ |’(list ’ label branch* ’)’ |
(5.1)
var
var ::= symbol
label ::= ’(sample-label)’ | ’(quote ’ symbol ’)’symbol ::= [’A’-’Z’ ’a’-’z’].*

This defines which kinds of worlds we are going to consider.
Intuitively, each world is a program drawn from this grammar. If
we put weights on the productions, we can actually draw worlds
and what we have defined here is a distribution on worlds.

5.2

A Probabilistic Representation Language

What does a representation language look like that can efficiently
represent worlds like the one described above? And what should
the prior distribution on worlds look like that the learner in ourdemonstration will use?
Clearly, the ideal representation language can represent exactly all possible worlds and no impossible worlds; it is equal to
the language defined by the grammar for tree-generating programs
that we specified in the last section. Equally clearly, the best priordistribution over worlds assigns exactly as much probability mass
55

1 Pairs, actually. Lists are built outof pairs.

to each world as is the case for the true distribution from whichworlds are drawn. What I would like to show is how reasoning andlearning can take place given that we have a accurate language toformally write down models of the world and given that we have areasonable prior distribution over what the world is like (e.g. that
simpler worlds are more likely). Therefore, I will use the ideal
representation language and prior for our learner.
In the last section, I mentioned that the observations must
not only allow us to approximately recover the true underlying
structure from an information-theoretic point of view, but theymust allow us to do so in a computationally efficient way. Thismeans that in order to find the best hypothesis, it must not benecessary to look at all hypotheses. The hypothesis space must be
structured such that from looking at the observations and at somehypotheses, we get information on which hypotheses to examine
next. This is an instance of partial credit.
For tree-generating programs, partial credit can be achievedby augmenting the representation language of the learner suchthat each tree-generating program expressed in this language can,with some small probability, generate an arbitrary tree. In particular, we can achieve this by first specifying a tree-generating
program that can generate every tree and then allowing at eachnode that the generating process switches with some small probability from the “real” program to the program that can generate
any tree. Thus, in inference, common root structure is used as far
as possible, but if the desired observed tree could otherwise notbe generated from the current hypothesis, the all-including smallprobability process is used. Thereby, the probability of an arbitrary observed tree being generated from some hypothesis treegenerating process is not automatically 0 if the hypothesis only
gets the observation partially right.
In this chapter, I have described the setup of the demonstration we use to show how learning of generative models can work.
We have chosen a world that consists of simple, stochastic, treegenerating programs with the observations being trees with colored nodes and, for the learner, a matching representation language an bias. In the next chapter, I will show what the actual
implementation of the learner looks like and how it fares in thisworld.

56

Chapter 6

Learning
How does an example of concept induction in a simple world look
like? This is the question I want to answer in this chapter. In
the last chapter, we have seen a toy world that consists of structured, tree-generating programs. The learner — who has the job
to infer the true structure of the world from observations — uses
a representation language with primitives and inductive bias both
matched to the tree world. We have already seen a formalizationof the problem of learning and reasoning in a structured world, andwe have also seen two inference mechanisms that, in combination,
can be used to learn representations from structured observations.
In this chapter, I will show what this kind of structure learning
looks like for the tree world.

6.1

MethodIn the chapter on inference, we have seen that the problem of finding a good model for one’s observations can be decomposed into
the subproblems of model scoring and model space exploration.
Subsequently, we have looked at adaptive importance sampling,
an inference algorithm that can be used to efficiently score models, and Markov Chain Monte Carlo, an inference algorithm thatcan be used sample from the posterior distribution over models.
As was the case in the model chapter, it is still our goal tosample from the distribution over hypothetical model expressions
conditioned on the observations generated from the hypotheticalmodel being equal to the true observations. The more likely our57hypothetical model is to have generated the observations, the moreprobable it needs to be that we sample this model. At the sametime, not only the likelihood of the observations should factor into
the total score of a model, but also the random choices that weremade when the model was generated: The more random choices
were made, the less likely the model is a priori, the less probable
we want it to be under the posterior.
We achieve this goal by writing down a generative model thatfirst generates an expression and, subsequently, scores the true
observations under the program defined by this expression. Using
Church’s universal mh-query, we condition the output on the estimated score, thus making those models most probable that bestaccount for the observations. At the same time, the randomness
that went into generating the expression factors into the posterior
distribution through the generative model: the MH algorithm isless likely to go sample states that have lower prior probability,
which is the case for more complex expressions.
For each observed tree, we estimate the likelihood that the
program defined by the expression hyp-expression returns thistree using our adaptive importance sampler. Then, the total likelihood of the observations under the current hypothesis is the
product of the individual observation likelihoods. Since we are
not only interested in sampling expressions for hypothetical models of the observed data, but also in the estimated likelihood of
the data under each hypothetical model, we query on both, i.e.
let our samples contain pairs of model expression and likelihoodof observations.
In code:(mh-query; The generative model ’in the head’:((define hyp-expression (sample-expression))(define observation-likelihoods(map (lambda (tree)(ais-estimate-prior hyp-expression tree))observed-trees))(define logscore (sum observation-likelihoods))); What we want to know:(pair hyp-expression logscore); Condition:(log-flip logscore)(get-env))

58

(6.1)

(a)

(b)

Figure 6.1: Observed trees for which we want to find a generators.

6.2

Illustration

In the following, I will illustrate a sequence of programs that stepby step have a higher estimated likelihood for the observation pictured in figure 6.1. This is for two reasons: First, this showsthat computing the likelihood of the observations by adaptive importance and using our tree grammar results in a very intuitive
sequence of likelihoods in the following sense: Programs for which
the likelihood of the observations is rated as high are actually those
programs that intuitively seem likely to have generated the observations. The second reason for showing this sequence of programs
is to give an idea of the way mh-query would sample hypotheticalprograms given observations.
In contrast to the following sequence, a sequence of MH samples usually looks less like the result of a hill climbing algorithm
than the following illustration1 . However, starting from an expression for which the observations have low likelihood, the stepby-step construction of an expression with higher likelihood looks
very similar if done by MH sampling.
On the left of the following illustration, the program is presented in a way that exposes its structure. Programs are not
identical to trees; as we have seen in the previous chapter, every
program can give rise to any tree in order to allow the computationof a meaningful partial-credit carrying likelihood for all observations. However, for a program like (node ’a), all trees but theone that carries only a single node of the appropriate color havevery low probability.
On the right, the estimated loglikelihood of the observations isshown, with the likelihood of observation 1 making up the left
side of the bar and that of observation 2 the right side. The
smaller the bar is for a program, the larger is the loglikelihod of
the observations under this program.
59

1 Since MH accepts samples

proportional to their posterior
score, going from a sample with ahigh score to a lower-scoring
sample is perfectly possible — it
only happens proportionally lessoften than going to anotherhigh-scoring sample.

Program

Loglikelihood of Observations

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

60

Programt

Loglikelihood of Observations

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

−250

−200

−150

−100

−50

0

t

λ(t)

t

t

?

λ(t)

t

t

?

λ(t)

In code, the final program looks like this:((lambda (t) (node ’a t t))(node ’b(if (flip)(node ’c (node ’d) (node ’d))(node ’b (node ’b)))(node ’a)))(6.2)

Lambda abstraction captures the duplication of tree structure
in a concise way and the stochastic choice (if (flip) ...) takes
care of partial variation in the observations.
There are two reasons why our learner will prefer the programusing lambda abstraction to an analogous program without abstraction, and only the first one is captured in the plots above:
The observed data is more likely under this program since fewer
random choices have to be made to generate the data. By du61

plicating a branch using abstraction, all the randomness in thisbranch factors only once into the likelihood computation insteadof twice. The other reason is that the program itself is shorterand thus more likely a priori, since fewer random choices have to
be made in generating this program from the distribution overprograms.
Having seen qualitatively how a program can be constructed
step by step by looking at which changes improve the likelihoodof the observations that this program is supposed to give rise to,
we will now take a more quantitative approach and look at how
the Metropolis-Hastings inference algorithm (code 6.1) performs
when run on randomly generated expressions and observations.

6.3

Quantitative Experiments

The goal of this section is to show that learning tree-generating
programs from observations reliably works if we use the methods
described in the previous chapters. I will first describe the learning setup including which statistics I collect, then show some of
the results (with all of them being in the appendix) and someaggregate statistics. Finally, I discuss what we can and cannot
conclude from the data we have collected.
Before we can design our demonstration, we need to define ourmeasure of success: What does it mean that learning generating
programs for observations works? One option for such a measureis the successful recovery of the program that originally generated
the observations — the actual structure out there in the world. If alearner is given a few observations and then systematically assigns
high probability to the true generator, then it is clearly a successful
learner. However, since we only get to look at a few observations,the true structure may not always be the best explanation. The
best explanation of an observation is the explanation that, acrossall situations that could give rise to this observation and weighted
by how often the situations occur, most accurately reflects thetrue distribution over situations.
In the sequence of programs that was illustrated in the last section, the best explanation was one that used lambda abstraction
to account for recurring structure. In contrast, our quantitative
experiments will not include lambda abstraction, neither in thetrue programs that generate observations nor in the grammar that62

is available for inference. The reason for this constraint is that,in order to efficient MCMC inference over the space of programs
that includes lambda abstraction, there must be proposals thatallow the algorithm to switch between a program without lambda
abstraction to a program with lambda abstraction and vice versa.
Moreover, in order to stochastically walk through the space ofprograms that includes lambda abstraction in a way that resultsin efficient inference, there must not only be a way to constructprograms with lambdas, but these states must be reachable fromsimilar programs that do not use lambdas. For example, there
must be a way to go from(node ’b(node ’a (node ’b) (node ’c))(node ’a (node ’b) (node ’c)))

(6.3)

to
((lambda (x) (node ’b x x))(node ’a (node ’b) (node ’c))

(6.4)

and back2 . If the programs with lambda abstraction are not reachable from similar programs without lambdas, the inference algorithm will not efficiently explore the different modes of the distribution over programs and instead mostly be stuck in one or theother — it will not “mix well”. Lambda learning will allow us toinfer more interesting and varied programs from observed data,
but its implementation remains future work.
The basic idea of the setup we will use to quantitatively demonstrate program learning is to randomly generate programs andthen test how well our inference algorithm performs on observations generated from these programs, measured by how likely theobservations are under the inferred programs compared to the true
generating programs. In sequence:
1. We first sample a random tree-generating program from theprobabilistic grammar that defines which tree worlds are
possible.
2. By running this program, we sample structured observations, i.e. trees.
3. We estimate the likelihood of these observations under thetrue generating program.
63

2 This type of proposal has been

proposed by Noah Goodman, who
named it “inverse inlining”.

4. We run the inference algorithm (MCMC with AIS scoring) on these observations, thus sampling programs that
could have generated the observations, together with the estimated likelihood of the observations under each program.
5. We plot the true likelihood of the observations together withthe estimated likelihood under the programs that were inferred from the observations.

3 together with the likelihood of the

In total, I have run the sequence described above 79 times,
thus creating 79 tree-generating programs, 79 worlds. From eachof these, 5 observations have been sampled. Using these observations, the inference algorithm was run for 2000 MH steps, i.e.
2000 programs3 were learned in each of the 79 worlds.

observations under these programs

Figure 6.2 shows the result of the first twelve runs. The estimated true likelihood is shown with a green line, the likelihoodof the observations under each of the 2000 sampled programs isshown in black. The plots show that the MCMC algorithm starts
out with a program that does not explain the observations very
well, but after a short time samples from a region of the state
space where most of the programs do explain the observations
well. For a complete listing of the results, including information
on what the generating programs were, see the appendix.
Figure 6.3 summarizes these results by showing how the (estimated) likelihood of the observations under the true generation program relates to the highest (estimated) likelihood for all
learned programs. As illustrated by the fact that the best learned
likelihood is often as high as or higher than the true likelihood(i.e. many points are on or above the middle line in the rescoredfigure), the learned programs do well at explaining the observed
data.
The fact that there are several programs which do not explain
the observations well can be explained by looking at the list ofexperimental results and programs in the appendix. Those observations that were not explained well within 2000 MH samples arealmost always those generated by complex programs, and it is reasonable to suggest that running the inference engine for a longer
amount of time would result in programs being learned for theseobservations, too. It is nonetheless worthwhile to ask how the inference algorithm scales with the length of the smallest programs
64that can explain the data well; this task, however, is beyond thegoals of this thesis.
In the last sections, we have seen the tree world as a practical example of how programs can be learned from observations.
We started by looking at the (fully general) basic idea of using
a combination of Markov Chain Monte Carlo methods to explore
the space of possible programs together with adaptive importancesampling to score how likely any given observation is under agiven program. We have then first given an illustration of how
small changes to a program can lead to a sequential increase in
the likelihood of the observation, thus allowing for a smooth trajectory from programs that do not explain the observations wellto those that do. Finally, I have argued that this works reliably
in the tree domain by showing how explanations can be learnedfor observations created from randomly generated programs.
In the remainder of this thesis, I will discuss what the resultsin this chapter mean and what the adaptive importance samplingalgorithm can be used for more generally, which related work there
is and what future research looks most promising. Finally, I willconclude by reviewing the content of this thesis by summing up
the main points from each chapter.

65

1500

2000

0

500

−5 0
−15

1000

program 11

program 12

2000

2000

−20

500

mh steps

1500

1500

−50
0

mh steps

1000

2000

0

program 10

mh steps

1500

0

1000

program 9

2000

2000

−50

500

mh steps

1500

1500

−200

estimated log score0

mh steps

1000

2000

−20

1000

program 8

2000

1500

−50

500

program 7

1500

2000

−10 0
0

mh steps

1000

1500

−25

estimated log score

2000

mh steps

estimated log score

500

1000

program 6

1500

2000

−20

0

500

program 5

1000

1500

−80

500

0

mh steps

estimated log score0

estimated log score

−20

1000
mh steps

−150

500

1000

program 4

0

0

500

program 3

−60

500

0

mh steps−500estimated log score

0−60 −30

2000−30

estimated log score

1500

−70

estimated log score

1000
mh steps−5

estimated log score

500

−20

estimated log score

0−50

estimated log scoreprogram 2−200

estimated log scoreprogram 1

0

500

1000
mh steps

Figure 6.2: MCMC results for a few programs. For the complete statistics, see theappendix.

66

0
−5
−10
−15

Loglikelihood of Observations Under Best Learned Model

True vs Learned Score

−15

−10

−5

0

Loglikelihood of Observations Under True Model

0
−5
−10
−15

Loglikelihood of Observations Under Best Learned Model

True vs Learned Score (Rescored)

−15

−10

−5

0

Loglikelihood of Observations Under True Model

Figure 6.3: MCMC results summarized. Rescoring the sampled programs with 300
importance samples instead of the 30 that were used at each MH step exposes cluster
structure (programs with one flip, two flips) and removes the selection bias present in thefirst figure (with high estimation variance in the scores, selecting the learned programwith the best score results in scores that are only accidentally high).

67

68

Chapter 7

Discussion
7.1

Interpretation

Given that most chapters already discuss their respective findings,
I will only discuss two questions here that strike me as particularly
important. First, what do the results in the chapter on learning
actually show? Second, to what extent is the class of adaptive
importance sampling algorithms that we have derived generally
useful rather than problem-specific?
Starting with the results in the chapter on learning in a simple toy world: What do they show beyond the immediate resultthat in this world generative models can be recovered from observations? One generalization of this result is that, if you canefficiently estimate the likelihood of observations under any given
generative model, and if you can explore the space of generativemodels efficiently, then you can find programs that explain the observations well. We used two main ingredients to make these two
operations efficient: Adaptive importance sampling to score models and a representation language that expresses models such thatthey can generate any observation with nonzero, graded probability. Lessons one might learn are that sampling algorithms should
use any information about the posterior distribution to generatebetter samples (here: evidence pushing, adaptation) and samples
should provide information on where to look for better samples(partial credit).
To what extent is the class of adaptive importance sampling algorithms that we have derived generally useful rather than problem69

specific? In its current form, the information propagation ruleof the algorithm assumes that the operands are evaluated independently, an assumption that clashes with the idea of delayed
evaluation that we used to push the evidence through compoundprocedure applications. As a consequence, the current algorithm
suffers from inefficiencies when applied to programs containing
compound procedures and is best seen as a preliminary versionof the final algorithm. However, there is a natural extension wecall “sequential inverses” that will allow us to combine delayed
evaluation and adaptation at primitive procedures. Once the information propagation rule is extended to its more general form,
this algorithm can be used to sample solutions to logical satisfiability problems, to parse the yield from grammars, even fromthose that do not fall inside the class of context-free or contextsensitive grammars, and to solve similar problems where large
parts of the (prior) state space are impossible under the posterior
distribution. A closer examination of the capabilities of the classof algorithms will only be possible once the proposed extension
has been completed.

7.2

Related WorkAn important part of the related work has already been mentioned in the chapter describing the philosophical, statistical andcomputational background of our approach. In particular, thisincludes the idea of a language of thought (due to Fodor [Fod76])
and the Bayesian approach to probabilistic inference (promoted
by Jaynes, among others [JB03]). However, there are two research programs that have been relevant to this project, but not
sufficiently exposed so far. The first is the psychological research
program built on the exploration of a hypothesized probabilistic
language of thought, the second is the prior research on adaptive
importance sampling algorithms.
The Probabilistic Language of Thought research program headedby Noah Goodman provides the scientific context that gave riseto this work, and most of the ideas that are part of this work areideas developed within this research program. In [GTFG08], aBayesian model of concept learning is presented and tested usinga grammatically structured hypothesis space. One way of looking
at the current work is to see it as a generative and more com70

putational version of this discriminative, more psychological, andmore empirical work. [KGT08] makes use of a compositional language of thought to explain the learning of intuitive theories on
a computational level. This research program also gave rise to
the probabilistic programming language Church [GMR+ 08] thatwas fundamental to the implementation of our project. The next
bigger context that subsumes both this work and the probabilistic language of thought program is the Bayesian, computational
approach to concept learning and to cognitive science in general[TR99].
There are a few inference algorithms that are in the same spirit
as our adaptive importance sampler for probabilistic programs.
The most similar algorithm known to me is SampleSearch [GD07]
which, in contrast to our algorithm, is based on backtracking instead of adaptation and which is only asymptotically unbiased,
whereas our algorithm results in unbiased estimates. In addition,
like AIS-BN [CD00] and Ortiz and Kaelbling’s adaptive importance sampler [OK00], these algorithms are written for graphicalmodels and do not make use of the more intricate structure ofprobabilistic programs. Systematic Stochastic Search [MRJT] is asequential rejection sampler that has the same property. Whereas
our algorithm conditions only on the relevant environment of an
expression when learning how to sample from it, this algorithm
conditions on the complete prior evaluation history and thus does
not generalize from its adaptations. Pfeffer [Pfe07] presents animportance sampling algorithm for probabilistic programs, whichmakes use of delayed evaluation and of checking ahead of time
what values an expression can return. However, in contrast to
our algorithm, this algorithm is not adaptive.

7.3

Future Research

Due to the broad nature of the approach to learning and reasoningthat we took, and due to the broad nature of the topic itself, there
are many directions future research could take. I will limit myself
to sketching those that are both exciting and realizable in the nearterm.
Instead of having the learner passively infer the structure of theworld from observations that cannot be influenced by the learner,
we could consider an active setting. Here, an agent interacts with71

the environment in a goal-directed way; what and how to learn
might then not be based on considerations of epistemic accuracy,
but instead on utilitarian considerations. We might look at setups similar to those used in reinforcement learning, but consider
structured generative models as more interesting, useful and realistic representations for world model, goals, and actions than the
representations that are commonly used.
The programs that were learned in the demonstration are composed of more elementary parts, and the learning happens in a
stepwise fashion, but there is an even more interesting element to
the idea of compositionality that we did not make use of: The ideaof reusing programs that were itself learned, an idea that enables
a learner to gain expressive power with each new concept in its
knowledge repository. This idea is tied to a number of proposals
for future research, the overarching theme being the idea of learning systems of concepts. Technically, one might achieve this byallowing inverse inlining proposals, i.e. proposals that move fromprograms without lambda abstraction to programs with lambda
abstraction. Both sequential learning and simultaneous learning
are interesting from a computational and from a psychological perspective. In sequential learning tasks, concepts that are learned
earlier on are reused in the compositional structure of subsequentconcepts if this allows the world model to be expressed more concisely. This makes the ordering of the learning data significant.
A similar idea is to make the world itself change such that thelearner step by step accumulates evidence that his current theory
is no longer accurate until a theory revision is justified. In simultaneous learning, multiple concepts need to be extracted fromobservations at once, and which conceptual properties make thiseasy, which make it hard, and how exactly this can be done by either humans or machines is a question that future research needs
to answer.
I have presented probabilistic inference over structured generative models as a computational theory of both learning andreasoning, but in the actual demonstration, I have only shown
learning. Clearly, accurate beliefs are of very limited use if one
cannot use them to reason about the world, and a demonstration of a computational model of reasoning, in particular if it
combines inductive and deductive reasoning in an elegant way,
will be an important task for future research. Exploiting the fact
72

that what our model of learning infers is a richly structured generative model, a natural extension to reasoning is the following:
Conditional sampling from the generative world model allows thelearner to make inductive predictions about any property of theworld that can be expressed within the representation language.
By giving no special treatment to deduction, but instead taking
it to be just a limiting case of induction, approximate deductive
reasoning becomes feasible within the framework of probabilistic
inference. How productive this view on deduction is, both from a
psychological and from a machine learning perspective, is an open
question.
How could we test whether the characterization of concept
learning as program induction is an adequate description of what
humans do? Building on the research that has already been
done on modeling concept learning as Bayesian inference over alanguage-like hypotheses space [GTFG08], we might consider asequence of experiments to test in how far a hypothesis space
defined by a language for generative model predicts human performance. Starting with the tree visualizations developed in thisthesis, we can compare the generalization performance first fortree-generating programs without lambda abstraction, then forprograms that use lambda abstraction to enable reuse of branches
and finally for those that use higher-order functions. One particularly interesting test would be to determine whether a language
based on generative models makes better predictions in this task
than a discriminative classifier based on surface features.
Simple versions of problems are often amenable to methods
that cannot be used to solve more complex and more data-intensive
versions. If we want to infer more complex programs from observations, what needs to change to make our approach scale?
If the same basic model of partitioning the problem into exploration and scoring is maintained, then we need to make sure thatboth are efficient for larger programs. For the exploration part,
if we keep MCMC as the query implementation, then efficiency
means that we need to explore the high-probability regions of ourhypothesis space quickly, which, for large hypotheses spaces, depends on making good proposals. Here, one idea would be torandomly choose any node in the program trace (not necessarily
an erp) and then to use adaptive importance sampling to regenerate a trace that fulfills the constraint at this node. However, in73how far this can be used to make efficient proposals for program
learning is an empirical question, and we might find out that a
yet unknown alternative to MCMC results in more efficient inference. For the scoring part, if we keep the adaptive importancesampler, the efficiency will depend on the exact features used by
the program to be learned (e.g. random operators might result indifficulties), on the number of likely parses per observation and on
the state of the algorithm (e.g. on whether soft adaptation is implemented and if yes, what its convergence properties are). Thereis no in-principle reason why scoring would not work efficiently
for larger programs, however the exact scaling properties remain
the realm of future work.
More generally, exploiting incremental learning might be crucial to learning complex programs. If abstraction can be used
to first learn simple programs that can be combined into more
complex programs later on, then the fact that jumps between
different complex programs require only small variations in the
combinations of constituent programs might enable more efficient
inference. The other side of incremental learning is what could becalled “learning to learn”: By using the adaptive importance sampler for a long time, the importance table will accumulate useful
information on which values are how likely under which expressions and in which environments. A large importance table thatpersists across program runs might help to more quickly learneven complex programs. Due to the easy way to merge a large
number of weighted samples from different distributions into one
estimate, adaptive importance sampling is very easy to parallelize
across computers. Such a parallelization, possibly together witha shared importance table, might help to solve the problem oflearning complex programs if the algorithms used are not in thewrong complexity class for this task. This, too, is an interestingquestion for future research.

74

Chapter 8

Conclusion
We started out with the question how an agent could learn andreason in a structured, probabilistic world. In the following, I will
review the progress that we have made, first by giving an overview,
then by explaining more precisely what has been achieved in eachof the chapters.
After first philosophical considerations on what the propertiesof a medium of thought must look like, we presented a formalization of learning and reasoning as probabilistic inference. In orderto give a practical example of this formalization for a simple but
interesting world, we first described two methods of inference,
one of them being a new class of importance sampling algorithms
for probabilistic programs. After describing the desiderata for a
simple example of learning programs from observations, we firstillustrated what learning looks like in this example, then quantitatively showed that inferring programs from observations reliably
works. I will now describe these steps one by one.
As a first step, we considered what an informational substrateof thought might look like. If an agent systematically derives true
statements about an object that is out there in the world andthat is no currently perceived, then the information that is necessary to derive these statements must be found somewhere withinthat agent: The object must have a representation. The informational structure that is used to store representations must havecertain properties: Representations must be able to be combinedin a productive way, the meaning of compound representations
must (among other factors) be determined by the constituents,
the relation between compounds and constituents must be a sys75

tematic one, and both real and possible states of affairs must be
expressible in this medium. One kind of representation that isparticularly useful are (stochastic) generative models, i.e. models
that mirror the causal structure of some process in a way that lets
us generate observations from the model and that lets us invert
the model to infer hidden properties of the process.
Having established the properties of mental representations,the next step in our process of reductive explanation was to find away to formally talk about these kinds of representations and to
give a formal account of what it means to learn and reason withthese kinds of representations. Probability theory is our best tool
to formally talk about uncertainty, and programming languages
are our best tools for the formalization of processes that generate values, therefore, I have used the probabilistic programming
language Church to formally talk about stochastic generative processes. If, using this language, we can formalize beliefs within theBayesian probability calculus, which itself can be derived from
relatively weak common sense and consistency assumptions, thenBayes’ rule normatively determines how these beliefs need to be
updated in light of new data. On a computational level, bothlearning (formalized as inferring a model from observations) andreasoning (formalized as determining whether a proposition is truein a given model) can then be interpreted as probabilistic inference.
In order to move towards a practical demonstration of learning generative models, we needed to solve the problem of how to
do inference over generative models. We have decomposed the
problem of learning these models into two parts: First, given observations and a model, how can we score the model? Second, how
do we explore the space of possible models efficiently? In order tosolve the first question, we have derived a new class of adaptive
importance algorithms for probabilistic programs that rely on two
principles: When evaluating a program, push the evidence as far
down the evaluation as possible, thus sampling from a distributionthat is close to the posterior distribution p(model|data). Aftereach evaluation, adapt the distribution we are sampling from, using any information we have learned during the evaluation about
what values can and cannot be returned by subexpressions. The
second inference method we use is called Markov Chain Monte
Carlo; here, the main idea is to construct a Markov chain that76

has as its long-run distribution the distribution we want to sample from. Taken together, these two inference methods let us inferprograms from observations.
The setup of the actual learning demonstration was as follows: A structured world generates observations, and the task of
the learner is to construct a generative model of the world thatclosely mimics the actual world. Of our demo world, we requiredthat it contains interesting structure, that this structure can be(approximately) recovered from observations, and that the worldis stochastic and simple. The world that we chose is one thatconsists of a stochastic tree-generating program, with the observations being trees with colored nodes. For the learner, we chosea representation language that offers an inductive bias over worldsthat closely matches that of the true world-generating process andthat can be used with partial credit, i.e. that, when we computethe likelihood of observations under a model that is almost right,
this likelihood is higher than for a model that is completely wrong.
In our demonstration of structure learning for the tree world,
I have first described how to combine Markov Chain Monte Carlowith adaptive importance sampling such that we can explore thespace of possible programs. I have then demonstrated how small
improvements to a program can lead to a sequential increase in
the likelihood of the observations, thus allowing for a smooth trajectory from programs that do not explain the observations wellto those that do. Finally, I have argued that this works reliably
in the tree domain by showing how explanations can be learnedfor observations created from randomly generated programs.
There is a variety of directions one could take to further extend this work. On the learning side, the most notable are an
extension to learning with lambda abstraction, learning in an active setting, and learning systems of concepts. On the algorithmic side, more intelligent procedure inversion and parallelizing theadaptive importance sampler promise the most immediate benefits. The framework of learning and reasoning with generativemodels expressed in a probabilistic language of thought promises
to offer solutions to a large number of open questions in psychology and artificial intelligence, and one goal of this work has been
to illustrate this possibility using the simplest example that could
do.

77

78

Bibliography[AdFD03]

Christophe Andrieu, Nando de Freitas, and Arnaud Doucet. An introduction
to mcmc for machine learning. Mar 2003.

[ASS]

Harold Abelson, Julie Sussman, and Jerry Sussman. Structure and interpretation of computer programs.

[Ber]

Kasper K Berthelsen. Importance sampling for unnormalized densities.

[Bon]

KA Bonawitz. Composable probabilistic inference with blaise.

[CD00]J Cheng and MJ Druzdzel. Ais-bn: An adaptive importance sampling algorithm for evidential reasoning in large bayesian networks. Journal of Artificial Intelligence Research, 2000.

[CMMR09] Jean-Marie Cornuet, Jean-Michel Marin, Antonietta Mira, and Christian
Robert. Adaptive multiple importance sampling. arXiv, stat.CO, Jan 2009.
[Cow]

J Cowley. Compositionality in inferential-role semantics.

[CTY06]

Nick Chater, Joshua B Tenenbaum, and Alan Yuille. Probabilistic modelsof cognition: Conceptual foundations. pages 1–5, Oct 2006.

[Fod76]

Jerry A Fodor. The language of thought. page 214, Jan 1976.

[Fod07]

Jerry A Fodor. Concepts - where cognitive science went wrong. pages 1–186,
Dec 2007.

[GD07]V Gogate and R Dechter. Samplesearch: A scheme that searches for consistent samples. AISTATS 2007, Jan 2007.

[GMR+ 08] Noah D Goodman, Vikash Mansinghka, Daniel M Roy, KA Bonawitz, andJoshua B Tenenbaum. Church: a language for generative models. Proceedingsof the 24th Conference in Uncertainty in Artificial Intelligence, pages 220–
229, 2008.
[Gog09]Vibhav Gogate. Sampling algorithms for probabilistic graphical models withdeterminism. 2009.
79

[GTFG08] Noah D Goodman, Joshua B Tenenbaum, Jacob Feldman, and Thomas L
Griffiths. A rational analysis of rule-based concept learning. Cognitive Science, 32(1):108–154, 2008.
[GY06]T Griffiths and A Yuille. Technical introduction: A primer on probabilistic
inference. Department of Statistics, Jan 2006.

[JB03]ET Jaynes and GL Bretthorst. Probability theory: the logic of science. 2003.

[KGT08]Charles Kemp, Noah D Goodman, and Joshua B Tenenbaum. Theory acquisition and the language of thought. Proceedings of Thirtieth Annual Meetingof the Cognitive Science Society, 2008.

[Mac03]David MacKay. Information theory, inference and learning algorithms. 2003.

[Man09]Vikash Mansinghka. Natively probabilistic computing. pages 1–129, Mar
2009. Notes.

[Mar82]

D Marr. Vision: A computational investigation into the human representation and processing of visual information. Henry Holt and Co., Inc. New
York, NY, USA, Jan 1982.

[MRJT]

Vikash Mansinghka, Daniel Roy, Eric Jonas, and Joshua B Tenenbaum. Exact and approximate sampling by systematic stochastic search.

[OK00]LE Ortiz and LP Kaelbling. Adaptive importance sampling for estimationin structured domains. Uncertainty in artificial intelligence, pages 446–454,
2000.

[Pfe07]

Avi Pfeffer. A general importance sampling algorithm for probabilistic programs. 2007.

[PGT]

Steven T. Piantadosi, Noah D Goodman, and Joshua B Tenenbaum. A
formal model of number word acquisition (under revision).

[RC04]

Christian P. Robert and George Casella. Monte carlo statistical methods.
page 645, Jan 2004.

[Sza08]

Zoltán Gendler Szabó. Compositionality. 2008.

[Tal08]William Talbott. Bayesian epistemology. 2008.

[Tha08]Paul Thagard. Cognitive science. 2008.

[TR99]

Joshua B Tenenbaum and WA Richards. A bayesian framework for concept
learning. Department of Artificial Intelligence, Edinburgh University, 1999.

[Wyn90]K Wynn. Children’s understanding of counting. Cognition, Jan 1990.

[Wyn92]

K Wynn. Addition and subtraction by human infants. nature.com, Jan 1992.

80

81

Appendix
Experimental Results

1500

2000

500

−5 0
−15

1000

program 11

program 12

2000

2000

−20

500

mh steps

1500

1500

−50
0

mh steps

1000

2000

0

program 10

mh steps

1500

0

1000

program 9

2000

2000

−20

500

mh steps

1500

1500

−50
0

mh steps

1000

2000

−200

estimated log score

2000

1500

−50

1000

program 8

1500

2000

−10 0

500

program 7

82

0

0

mh steps

1000

1500

−25

estimated log score

2000

mh steps

estimated log score

500

1000

program 6

1500

2000

−20

0

500

program 5

1000

1500

−80

500

0

mh steps

estimated log score0

estimated log score

−20

1000
mh steps

−150

500

1000

program 4

0

0

500

program 3

−60

500

0

mh steps−500estimated log score

0−60 −30

2000−30

estimated log score

1500

−70

estimated log score

1000
mh steps−5

estimated log score

500

−20

estimated log score

0−50

estimated log scoreprogram 2−200

estimated log scoreprogram 1

0

500

1000
mh steps

1500

2000

2000

0

500

0
−15
−35

500

1000

program 23

program 24
0

mh steps

2000

0

500

1000
mh steps

83

2000

−20 0
0

mh steps

1500

1500

−50

estimated log scoreprogram 22

1000

2000

0

1000

program 21

mh steps

1500

0

500

mh steps

2000

2000

−40
0

mh steps

1500

1500

−100

estimated log scoreprogram 20

1000

2000

−60

1000

program 19

2000

1500

−140

500

mh steps

1500

2000

−5
0

mh steps

1000

1500

−20

estimated log score

1500

2000

−20

500

1000

program 18

1000

1500

−40

0

500

program 17

estimated log score

500

0mh steps−150

estimated log score

−5

1000
mh steps

−35

500

1000

program 16

−50

0

500

program 15

−20

500

0

mh steps00

estimated log score

−50
−150

2000

−150

estimated log score

1500

0

estimated log score

1000
mh steps−10

estimated log score

500

−20

estimated log score

00

estimated log scoreprogram 14−40 −20

estimated log scoreprogram 13

1000

1500

2000

2000

0

500

−10 0
−25

1000

500

1000
mh steps

program 35

program 36

1500

2000

0

500

1000
mh steps

84

1500

2000

−40
0

mh steps

1000

2000

−10

program 34
estimated log scoreprogram 33

mh steps

1500

0

500

mh steps

2000

2000

−20
0

mh steps

1500

1500

−50

estimated log scoreprogram 32

1000

2000

−100

1000

program 31

2000

1500

−400

500

mh steps

1500

2000

−10
0

mh steps

1000

1500

−40

estimated log scoreprogram 30

1500

2000

0

500

1000

program 29

1000

1500

−60 −30

0500

mh steps

estimated log score

500

0mh steps−2000estimated log score

0
−4

500

1000

program 28

−50

0

500

program 27

−10

500

0

mh steps−250 −1000estimated log score

−100
−500

2000

0

estimated log score

1500

−10

estimated log score

1000
mh steps−25

estimated log score

500

0estimated log score

0−30

estimated log scoreprogram 26−60

estimated log scoreprogram 25

1500

2000

2000

0

500

−100 −40
0

500

1000
mh steps

program 47

program 48

2000

0

500

1000
mh steps

85

2000

−20
0

mh steps

1500

1500

−40

estimated log scoreprogram 46

1000

2000

−20 0

1000

program 45

mh steps

1500

0

500

mh steps

2000

2000

−4
0

mh steps

1500

1500

−10

estimated log scoreprogram 44

1000

2000

−50

1000

program 43

2000

1500

0

500

mh steps

1500

2000

−60
0

mh steps

1000

1500

−140

estimated log score

1500

2000

−5

500

1000

program 42

1000

1500

−20

0

500

program 41

estimated log score

500

0mh steps−300
0estimated log score

0
−20

1000
mh steps

−20

500

1000

program 40

−100

0

500

program 39

−40

500

0

mh steps−50

estimated log score

−40 0
−100

2000

0

estimated log score

1500

−15

estimated log score

1000
mh steps−35

estimated log score

500

0estimated log score

0−10

estimated log scoreprogram 38−20

estimated log scoreprogram 37

1500

2000

0

500

0
−60
−140

1000

program 58

500

1000
mh steps

program 59

program 60

1000

1500

2000

0

500

1000
mh steps

86

2000

1500

2000

−100
0

mh steps

mh steps

1500

−40 0

program 57

2000

2000

−10

500

mh steps

1500

1500

−30

estimated log score0

mh steps

1000

2000

−20

1000

program 56

2000

1500

−80

500

program 55

1500

2000

−5 0
0

mh steps

1000

1500

−15

estimated log score

2000

mh steps

estimated log score

500

1000

program 54

1500

2000

−100

0

500

program 53

1000

1500

−400

500

0

mh steps

estimated log score0

estimated log score

−20 0

1000
mh steps

−100

500

1000

program 52

−20

0

500

program 51

−50

500

0

mh steps−40 00estimated log score

−20
−80

2000

−60

estimated log score

1500

0

estimated log score

1000
mh steps−30

estimated log score

500

−60

estimated log score

0

−10 0

estimated log scoreprogram 50−25estimated log scoreprogram 49

1500

2000

1500

2000

0

500

0
−20
−50

1000

500

1000

program 70

2000

500

1000

program 71

program 72

1500

2000

2000

1500

2000

−40
0

500

1000
mh steps

87

1500

0

mh steps

1000

2000

−150
0

mh steps

mh steps

1500

−50

program 69
estimated log score

mh steps

1500

2000

−60
0

mh steps

1000

1500

−20

program 68
estimated log scoreprogram 67

2000

2000

−100

500

mh steps

1500

1500

−300
0

mh steps

1000

2000

−150 −50

estimated log score

1000

1500

−80

500

1000

program 66

estimated log score

0500

program 65

−40

500

0

mh steps−30
0estimated log score

−10

1000
mh steps

−100

500

1000

program 64

−10

0

500

program 63

−40

500

0

mh steps00

estimated log score

0
−40
−100

2000

0

estimated log score

1500

−20

estimated log score

1000
mh steps−50

estimated log score

500

0estimated log score

0−60

estimated log scoreprogram 62−140

estimated log scoreprogram 61

1500

2000

500

1500

2000

1500

2000

0
−40

1000

1500

2000

88

−10
−30

1500

2000

1500

2000

−10
−40
0

500

1000
mh steps

mh steps

2000

−10

1000

program 78

1000

1500

−30

500

program 77−100

estimated log score0

mh steps

program 79

500

estimated log score

1000
mh steps

mh steps

01000

program 76

estimated log score

0500

program 75

−10

500

0

mh steps−25
0

estimated log score

−100
−300

1000
mh steps

0

500

0

estimated log score

0−30

estimated log scoreprogram 74−60

estimated log scoreprogram 73

Sampled Programs
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

Program(lambda () (node ’a (node ’a)))(lambda () (if (flip) (node ’d (node ’b)) (node ’a)))(lambda () (node ’a (node ’b)))(lambda () (node ’a (node ’d)))(lambda () (if (flip) (node ’a (node ’c (node ’d (node ’c)) (node ’d))) (node ’b (node ’c) (if(flip) (node ’b (if (flip) (node ’b) (node ’c))) (node ’b)))))(lambda () (if (flip) (node ’a) (node ’d (node ’a))))(lambda () (if (flip) (node ’a (if (flip) (node ’b) (node ’c))) (node ’a (node ’d (node ’c (if(flip) (node ’a) (node ’a)) (node ’b))))))(lambda () (node ’b (if (flip) (node ’b) (node ’c)) (node ’c) (if (flip) (node ’d) (node ’b))(node ’a) (node ’d))) a) (d)))(lambda () (if (flip) (node ’c) (node ’c)))(lambda () (if (flip) (node ’a (if (flip) (node ’a) (node ’b))) (node ’b)))(lambda () (node ’c (node ’c) (if (flip) (node ’a) (node ’c)) (if (flip) (node ’c) (node ’a))(node ’b)))(lambda () (node ’a (node ’d) (if (flip) (node ’d) (node ’d))))(lambda () (node ’d (node ’c) (if (flip) (node ’a) (node ’a))))(lambda () (node ’c (node ’b))) b)) (c (b)))(lambda () (node ’a (node ’b))) b)) (a (b)))(lambda () (node ’a (if (flip) (node ’b) (node ’b)) (if (flip) (node ’b) (node ’c)) (node ’b)))(lambda () (node ’b (if (flip) (node ’a) (node ’d))))(lambda () (node ’c (node ’b))) b)) (c (b)))(lambda () (if (flip) (node ’d (node ’c) (if (flip) (node ’b) (node ’d)) (node ’d) (node ’b (node’d)) (node ’c) (node ’c)) (node ’a)))(lambda () (node ’a (node ’a) (node ’c))) (a) (c)) (a (a) (c)))(lambda () (node ’b (node ’b))) b)) (b (b)))(lambda () (node ’d (node ’d))) d)) (d (d)))(lambda () (if (flip) (node ’d) (node ’d)))(lambda () (node ’b (if (flip) (node ’c) (node ’b))))(lambda () (node ’b (node ’a) (node ’b (if (flip) (node ’b) (node ’c (node ’a))) (node ’b) (node’d) (if (flip) (node ’a) (node ’c))) (node ’a) (node ’a))) (b (a) (b (c (a)) (b) (d) (a)) (a)(a)))(lambda () (node ’b (node ’c))) c)) (b (c)))(lambda () (if (flip) (node ’b) (node ’d)))(lambda () (node ’c (node ’b (node ’b (if (flip) (node ’a) (node ’c)))) (if (flip) (node ’d)(node ’b)) (node ’a) (node ’a (if (flip) (node ’b) (node ’c)) (node ’d))))(lambda () (node ’c (node ’d (node ’d)) (node ’b (if (flip) (node ’c) (node ’a (node ’b))) (if(flip) (node ’a) (node ’a)))))(lambda () (node ’b (node ’a) (node ’b)))(lambda () (node ’c (node ’c (node ’a) (node ’c) (if (flip) (node ’d) (node ’b)))))(lambda () (node ’a (if (flip) (node ’a) (node ’a))))(lambda () (node ’a (node ’d))) d))(lambda () (node ’b (if (flip) (node ’b (node ’d)) (node ’a))))(lambda () (node ’b (node ’c)))(lambda () (if (flip) (node ’a) (node ’d)))(lambda () (if (flip) (node ’b (node ’a)) (node ’b (node ’a (node ’a)))))(lambda () (node ’a (node ’d (if (flip) (node ’d (if (flip) (node ’d (node ’c)) (node ’c))) (node’c)))))(lambda () (node ’a (node ’d (node ’d))))(lambda () (node ’a (if (flip) (node ’b (node ’d)) (node ’b))))(lambda () (if (flip) (node ’c) (node ’b (node ’a) (node ’b))))(lambda () (if (flip) (node ’a) (node ’d (node ’c) (node ’d (node ’b)))))(lambda () (node ’a (node ’b (node ’c)) (node ’d) (node ’d) (node ’c) (node ’b)))(lambda () (if (flip) (node ’c) (node ’b)))(lambda () (node ’c (node ’d))) d))

89

#
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

Program(lambda () (node ’b (node ’c) (node ’b)))(lambda () (node ’b (node ’c)))(lambda () (if (flip) (node ’d) (node ’b)))(lambda () (node ’b (node ’d) (node ’c)))(lambda () (node ’d (node ’d) (node ’c) (node ’b)))(lambda () (node ’b (node ’c) (if (flip) (node ’b) (node ’d (if (flip) (node ’a) (node ’c))))))(lambda () (node ’a (if (flip) (node ’d (node ’a) (node ’d)) (node ’a))))(lambda () (node ’d (node ’d (node ’a)) (if (flip) (node ’d) (node ’a (node ’d) (node ’b)))))(lambda () (if (flip) (node ’a) (node ’c)))(lambda () (if (flip) (node ’a (node ’c)) (node ’d (node ’d) (if (flip) (node ’d) (node ’a)) (if(flip) (node ’b) (node ’c)))))(lambda () (if (flip) (node ’d (node ’c)) (node ’a)))(lambda () (node ’c (node ’d) (node ’d)))(lambda () (node ’d (node ’b (node ’b))))(lambda () (if (flip) (node ’a (node ’a)) (node ’d)))(lambda () (node ’d (if (flip) (node ’c) (node ’d)) (node ’b) (node ’b) (node ’d) (if (flip)(node ’c) (node ’a)) (if (flip) (node ’a) (node ’a (node ’a))) (node ’a)))(lambda () (node ’c (node ’d (if (flip) (node ’d) (node ’b)))))(lambda () (if (flip) (node ’d) (node ’d (node ’a) (node ’d))))(lambda () (node ’c (if (flip) (node ’b) (node ’a (node ’a)))))(lambda () (node ’d (node ’b (node ’c)) (node ’c (node ’b) (node ’d)) (if (flip) (node ’a) (node’d (node ’d))) (node ’c)))(lambda () (node ’c (node ’c) (node ’b)))(lambda () (if (flip) (node ’d (node ’c (if (flip) (node ’a) (node ’d)) (node ’c (node ’c)))(node ’d)) (node ’a (if (flip) (node ’d) (node ’b (if (flip) (node ’b) (node ’b)))))))(lambda () (node ’d (node ’d)))(lambda () (if (flip) (node ’b) (node ’b (node ’a) (node ’b))))(lambda () (node ’c (if (flip) (node ’c) (node ’c))))(lambda () (node ’b (if (flip) (node ’a (node ’a)) (node ’a)) (node ’d) (if (flip) (node ’c (node’c (node ’c))) (node ’c))))(lambda () (node ’b (node ’b (node ’a) (node ’d))))(lambda () (node ’b (node ’a (if (flip) (node ’d) (node ’c)))))(lambda () (node ’b (node ’c) (node ’d (node ’b) (if (flip) (node ’b) (node ’c)) (node ’b))))(lambda () (if (flip) (node ’b (node ’c)) (node ’b)))(lambda () (node ’d (if (flip) (node ’d) (node ’a (node ’b) (node ’a))) (node ’d)))(lambda () (if (flip) (node ’d) (node ’b (node ’c))))(lambda () (node ’c (node ’c) (node ’d)))(lambda () (node ’c (node ’a) (node ’d)))(lambda () (node ’b (if (flip) (node ’c (if (flip) (node ’a) (node ’d))) (node ’a (node ’c) (if(flip) (node ’d) (node ’d))))))

90