# Learning and Compositionality: a Unification Attempt via Connectionist
Probabilistic Programming

Ximing Qiao
Duke University
<EMAIL_ADDRESS>
&Hai Li
Duke University
<EMAIL_ADDRESS>

###### Abstract

We consider learning and compositionality as the key mechanisms towards
simulating human-like intelligence. While each mechanism is successfully
achieved by neural networks and symbolic AIs, respectively, it is the
combination of the two mechanisms that makes human-like intelligence possible.
Despite the numerous attempts on building hybrid neuralsymbolic systems, we
argue that our true goal should be unifying learning and compositionality, the
core mechanisms, instead of neural and symbolic methods, the surface
approaches to achieve them. In this work, we review and analyze the strengths
and weaknesses of neural and symbolic methods by separating their forms and
meanings (structures and semantics), and propose Connectionist Probabilistic
Programs (CPPs), a framework that connects connectionist structures (for
learning) and probabilistic program semantics (for compositionality). Under
the framework, we design a CPP extension for small scale sequence modeling and
provide a learning algorithm based on Bayesian inference. Although challenges
exist in learning complex patterns without supervision, our early results
demonstrate CPP’s successful extraction of concepts and relations from raw
sequential data, an initial step towards compositional learning.

##  1 Introduction

Simulating human-like intelligence requires two essential mechanisms of
learning and compositionality, while most existing algorithms only process one
side well. First, learning collects basic building blocks of knowledge from
raw observational data. Deep learning methods based on neural networks excel
at learning. Recent large language models absorb terabytes of text as training
data, and memorize everything from language structures to commonsense
knowledge [1]. Second, compositionality allows combination of the above
building blocks, which enables generalization much beyond direct observation.
Given rules such as $A\rightarrow B$ and $B\rightarrow C$, we infer that
$A\rightarrow C$ by combining them, with no actual experience on $A$ and $C$.
This process is captured by symbolic AIs. Inference engines based on logic
and/or probability achieve human-level question answering accuracy, given
enough domain-specific knowledge bases [2].

However, it is the hybrid of the two mechanisms that makes human-like
intelligence possible. Sticking with one mechanism alone cannot go very far.
On one side, the early failure of symbolic AIs show the obvious limitation of
AIs that cannot learn. In logic-based expert systems, hand-writing all of
commonsense as rules is obviously impossible. Later systems such as Bayesian
networks and probabilistic programs support certain parameter learning, but
still rely on human-specified core knowledge (causal relations, variable
dependency, etc.) [3]. On the other side, deep learning starts to hit walls,
revealing the limit of learning-only systems. Without compositionality, neural
networks only learn though direct experience, which leads to costly data
collection and prolonged training. Models like GPT-3 still struggle to answer
seemingly simple questions like “solve for x: x + 40000 = 100000”, when the
numbers are never covered during training [4]. From a linguistics perspective,
the model never truly understands the “meaning” of these numbers and
computations.

There has been extended works on merging neural and symbolic methods (namely,
neuralsymbolic AIs [5]), but this path is challenging. At a fundamental level,
the two methods express data as either distributed vectors or localized
symbols, which do not fuse in any obvious ways. As a result, successful
neuralsymbolic systems generally fall to one of the two categories: the first
is to have a neural representation as the core, and organize neural modules as
symbols to simulate symbolic computation at a higher level [6, 7, 8]; the
second is to have a symbolic representation as the core, and wrap them by
neural networks (with vector embeddings) for continuous optimization [9, 10,
11]. However, these methods still inherit the limitations of their neural or
symbolic components. Symbolic organization of the neural modules cannot be
efficiently learned (other than guided search), and neural-based optimization
needs direct experience of all corner cases. We still do not see learning and
composition working together.

A true hybrid system should unify learning and compositionality, the core
mechanisms, instead of neural and symbolic methods, which are merely surface
approaches to achieve them. In this work, we make an initial attempt towards
this direction. The central idea is to breakdown neural and symbolic methods
to their fundamental building blocks, then select and recombine the useful
blocks. In Section 2, we review and analyze the strengths and weaknesses of
neural and symbolic methods by separating their forms and meanings (structures
and semantics), and propose Connectionist Probabilistic Programs (CPPs), a
framework that combines a connectionist structure (for learning) with a
probabilistic program semantics (for compositionality). In Section 3, we
extend the CPP focusing on a special task of sequence modeling, and provide a
Bayesian inference algorithm to learn CPPs from small scale sequential data,
in a compositional way. Section 4 covers initial experimental results, which
reveal some challenges of learning complex patterns without supervision, but
successfully demonstrate CPPs’ capability to extract concepts and relations
from raw data. In Section 5 and 6, we discuss related works and conclude the
paper.

##  2 Connectionist probabilistic programs (CPPs)

###  2.1 Structure and semantics

To motivate the design of CPPs, we first review neural and symbolic methods,
and try to understand the exact components that make them good or bad. The
method is to analyze them through separate lenses of form and meaning.
Specifically, we denote form as structure, referring to the data-structure
stored in computer memory; we denote meaning as semantics, referring to the
input-output relations of functions and procedures.

For neural networks, their structures are given by weighted graphs with real-
valued parameters. Conventionally called connectionist networks, this type of
structure is especially suited for learning due to the efficient optimization
of continuous parameters. Semantics of neural networks is given by
transformations in high-dimensional vector spaces. While stacking a sequence
of transformations gives high expressiveness, the order of stacking is fixed
by the network architecture, which prohibits flexible symbolic manipulation.
The translation from the connectionist structure to the vector-space semantics
is given by the McCulloch-Pitts [12] and Perceptron [13] style neuron models.
Weights are interpreted as multiplicands to activations, and nodes are
interpreted as places to perform summations and non-linear activations.

For symbolic AIs, the structure is given by symbols and links (pointers) that
connect them, for example databases, causal graphs, and abstract syntax trees.
These structures are discrete, difficult to optimize, and hard to
incrementally learn. Semantics of symbolic AIs is given by mappings between
symbols, capturing their relations. Deterministically or probabilistically, we
can always build new mappings by connecting existing ones (e.g., composing two
functions gives a new function). The connection between the symbol-link
structure and the relational semantics is driven by the need of human
readability and programmability. Symbols and links are the easiest ways for
human to encode their expert knowledge to a machine readable form.

The above analysis delivers two key messages. First, the learning capability
is given by the connectionist structure, and compositionality comes from the
relational semantics. Second, although the vector-space semantics and symbol-
link structure are helpful, they are not necessary. Neither is multiply-and-
add the only model to interpret a network of weighted edges, nor symbolic
expressions the only form to represent symbolic relations. These messages
motivate us to combine neural and symbolic methods at a much lower level,
beneath typical neuralsymbolic approaches.

Figure 1: The structure-semantics view of CPPs and an example on logic and
arithmetic.

###  2.2 Formal definition of CPPs

As summarized in Figure 1(a), the design goal of CPPs is to drop the
conventional structure-semantics connections in neural and symbolic methods,
and establish a new bridge between the connectionist structure and relational
semantics. In this work, we choose the semantics of probabilistic programs
over other formal systems for its close relation to human cognition [14],
solid theoretical foundation [15], and well-studied inference algorithms [16,
17]. Here we present the definition of CPP’s structure, which includes five
types of nodes/symbols and three types of weighted edges (with positivity and
normalization constraints):

######  Definition 1 (CPP structure)

A CPP is a 5-tuple $\mathcal{G}=\langle Q,T,W_{Cn},W_{Fn},W_{Cm}\rangle$,
where

  * •

$Q$ is a finite set of symbols;

  * •

$T:Q\rightarrow\\{Id,Cn,Fn,S2,P21\\}$ is a function that maps symbols to
types, where $Id$ means identity functions, $Cn$ means constant functions,
$Fn$ means standard functions, and $S2,P21$ are two types of combinators;

  * •

$W_{Cn}:\\{q\in Q:T(q)=Cn\\}\rightarrow\mathbb{R}^{|Q|}_{\geq 0}$ defines a
probability distribution on $Q$ for every $Cn$-type symbols, and $\forall
q,\|W_{Cn}(q)\|_{1}=1$;

  * •

$W_{Fn}:\\{q\in Q:T(q)=Fn\\}\rightarrow\mathbb{R}^{|Q|\times|Q|}_{\geq 0}$
defines a conditional probability distribution from $Q$ to $Q$ for every
$Fn$-type symbols, and $\forall q,W_{Fn}(q)$ is right stochastic;

  * •

$W_{Cm}:\\{q\in
Q:T(q)\in\\{S2,P21\\}\\}\rightarrow\mathbb{R}^{|Q|\times|Q|}_{\geq 0}$ defines
a probability distribution on $Q\times Q$ for every combinator-type symbols
(abbreviated as $Cm$), and $\forall q,\|W_{Cm}(q)\|_{1,1}=1$.

Unlike in neural networks, these weights define probabilistic symbolic
relations (in the form of conditional probability distributions), instead of
vector-space transformations. The exact definition is given as follows (here
$\delta$ refers to the Kronecker delta, and the naming of $S2$ and $P21$
originates from Figure 2(c)):

######  Definition 2 (CPP declarative semantics)

For $\mathcal{G}=\langle Q,T,W_{Cn},W_{Fn},W_{Cm}\rangle$, each symbol $q\in
Q$ has a semantics $[\\![q]\\!]_{\mathcal{G}}:Q\times Q\rightarrow[0,1]$ such
that:

$[\\![q]\\!]_{\mathcal{G}}(i,j)=\begin{cases}\delta_{i,j},&\text{if}\
T(q)=Id.\\\ [W_{Cn}(q)]_{j},&\text{if}\ T(q)=Cn.\\\
[W_{Fn}(q)]_{i,j},&\text{if}\ T(q)=Fn.\\\
\sum_{f,g}[W_{Cm}(q)]_{f,g}\llbracket f\triangleright
g\rrbracket_{\mathcal{G}}(i,j),&\text{if}\ T(q)=S2.\\\
\sum_{f,g}[W_{Cm}(q)]_{f,g}\llbracket f\bowtie
g\rrbracket_{\mathcal{G}}(i,j),&\text{if}\ T(q)=P21.\end{cases}$ (1)

where

$\displaystyle\llbracket f\triangleright g\rrbracket_{\mathcal{G}}(i,j)=$
$\displaystyle\sum\nolimits_{k}[\\![f]\\!]_{\mathcal{G}}(i,k)[\\![g]\\!]_{\mathcal{G}}(k,j),$
(2) $\displaystyle\llbracket f\bowtie g\rrbracket_{\mathcal{G}}(i,j)=$
$\displaystyle\sum\nolimits_{k,l}[\\![f]\\!]_{\mathcal{G}}(i,k)[\\![g]\\!]_{\mathcal{G}}(i,l)[\\![l]\\!]_{\mathcal{G}}(k,j).$
(3)

A symbol $q$ is understood as a probabilistic function, that randomly maps an
input symbol $i$ to an output symbols $j$, with probability
$[\\![q]\\!]_{\mathcal{G}}(i,j)$ (we always have
$\sum_{j}[\\![q]\\!]_{\mathcal{G}}(i,j)\leq 1$, and if a function has
$\sum_{j}[\\![q]\\!]_{\mathcal{G}}(i,j)<1$, it may not terminate). To specify
these distributions, we either directly store a probability mass function as
weights in $\mathcal{G}$, as in $Cn$ and $Fn$-type symbols, or indirectly via
composing other distributions, as in $S2$ and $P21$-type symbols. Output
distributions of $Cn$-type symbols (constant functions) are not sensitive to
the input $i$, thus given by $W_{Cn}(q)$. Output distributions of $Fn$-type
symbols (standard functions) are sensitive to $i$, therefore given by
$[W_{Fn}(q)]_{i,\cdot}$. For $S2$-type symbols, we define the composition of
$f$ and $g$ (execute function $g$ after $f$) as $f\triangleright g$, and let
$[\\![q]\\!]_{\mathcal{G}}(i,j)$ be a weighted mixture of all $f$’s and $g$’s,
with weights $[W_{Cm}(q)]_{f,g}$. For $P21$-type symbols, $f\bowtie g$ defines
another form of composition assuming $g$ is a higher-order function (a
function that returns a function): first, execute $f$ and $g$ with a shared
input $i$ to return $k$ and $l$; then execute $l$ as a function with input $k$
to return $j$. Algorithm 1 provides an alternative view of Definition 2. For a
symbol $q$ and an input $i$, $\textsc{Sample}(q,i)$ returns $j$ with
probability $[\\![q]\\!]_{\mathcal{G}}(i,j)$.

Figure 1(b) presents an example of CPP on expressing Boolean logic and basic
arithmetic. Black arrows represent function outputs. In the blue region, $cT$
and $cF$ are constant functions (type $Cn$) that always output $T$ (logical
True) and $F$ (logical False), respectively. Gray arrows that point to the
black arrows represent function inputs. We have $and$ and $or$ as two standard
functions (type $Fn$) that output $cT$, $cF$, or $id$ (identity function with
type $Id$), depending on inputs $T$ or $F$. Following the above rules, a
expression $and(F)(T)$ will first reduce to $cF(T)$ (since $and(F)=cF$), and
then reduce to $F$ (since $cF(\cdot)=F$). Similarly in the yellow region, we
have numbers $1\sim 4$, $prev/next$ to define their order, and $=1$ to check
if a number is $1$. Next we introduce composite functions. With purple arrows
indicating $S2$-type composition, we have $+1=id\triangleright
next,+2=+1\triangleright next$, and $+3=+2\triangleright next$. With green
arrows denoting $P21$-type composition, we have $*1=id,*2=*1\bowtie+$, and
$*3=*2\bowtie+$ (here $+$ is a higher-order function with $+(1)=+1,+(2)=+2$,
and $+(3)=+3$). An example evaluation is
$*3(1)=+(1)(*2(1))=+1(+(1)(id(1)))=+1(+1(1))=+1(2)=3$. To simplify the
illustration, Figure 1(b) only includes binary weights, and all functions are
deterministic. With non-binary weights, these functions can be easily extended
to probabilistic versions.

Function  _Sample(_$q$ :symbol, $i$:input_)_:

switch  _$T(q)$_ do

case  _Id_ do

$j\leftarrow i$;

case  _Cn_ do

Draw $j\sim\text{Categorical}(W_{Cn}(q))$;

case  _Fn_ do

Draw $j\sim\text{Categorical}([W_{Fn}(q)]_{i,\cdot})$;

case  _S2_ do

Draw $(f,g)\sim\text{Categorical}(W_{Cm}(q))$;

$k\leftarrow$ Sample(_$f$ , $i$_);

$j\leftarrow$ Sample(_$g$ , $k$_);

case  _P21_ do

Draw $(f,g)\sim\text{Categorical}(W_{Cm}(q))$;

$k\leftarrow$ Sample(_$f$ , $i$_);

$l\leftarrow$ Sample(_$g$ , $i$_);

$j\leftarrow$ Sample(_$l$ , $k$_);

end case

end switch

return $j$;

end

Algorithm 1 CPP procedural semantics

Function  _Sample &Print(_$q$ :symbol, $i$:input_)_:

if  _$T(q)=Ob$_ then

$j\leftarrow i$; print $L(q)$;

else if  _$T(q)=Id$_ then

$j\leftarrow i$;

else if  _$T(q)=Cn$_ then

Draw $j\sim\text{Categorical}(W_{Cn}(q))$;

else if  _$T(q)=Fn$_ then

Draw $j\sim\text{Categorical}([W_{Fn}(q)]_{i,\cdot})$;

else

Draw $(f,g)\sim\text{Categorical}(W_{Cm}(q))$;

$k\leftarrow$ Sample&Print(_$f$ , $i$_);

$l\leftarrow$ Sample&Print(_$g$ , $T(q)\in\\{S1,S2,S12,S21\\}\ ?\ k:i$_);

if  _$T(q)\in\\{S1,P1\\}$_ then

$j\leftarrow k$;

else if  _$T(q)\in\\{S2,P2\\}$_ then

$j\leftarrow l$;

else if  _$T(q)\in\\{S12,P12\\}$_ then

$j\leftarrow$ Sample&Print(_$k$ , $l$_);

else if  _$T(q)\in\\{S21,P21\\}$_ then

$j\leftarrow$ Sample&Print(_$l$ , $k$_);

end if

end if

return $j$;

end

Algorithm 2 CPP-SO procedural semantics

##  3 Learning CPPs from sequential data

###  3.1 CPPs with sequential observations (CPP-SO)

Given the CPP as a general framework of defining complex probabilistic
functions on connectionist networks, here we address the learning problem. The
idea is to extend CPPs to produce observations, such that the learn problem
can be cast as Bayesian inference. For simplicity, and to mimic the process of
human obtaining knowledge from language, we focus on CPPs that generate
sequential observations (denoted as CPP-SO) on a finite, discrete alphabet.
For an alphabet $\Gamma$ and a CPP-SO $\mathcal{G}$, the goal is to specify a
probability distribution $p(x|\mathcal{G})$ for $x\in\Gamma^{*}$ (the Kleene
closure of $\Gamma$).

Our design of CPP-SO draws inspiration from probabilistic context-free
grammars (PCFGs), a classical method of sequence modeling. We first introduce
an additional type of observation ($Ob$) symbols, mimicking the terminal nodes
in PCFGs. These symbols behave like $Id$, but perform Print operations
(printing their labels) as side-effects. Next, we include eight types of
combinators to handle the extra complexity of the side-effects. As last, we
add $q_{0}$ and $q_{1}$ to help defining $p(x|\mathcal{G})$:

######  Definition 3 (CPP-SO structure)

A CPP-SO $\mathcal{G}=\langle
Q,\Gamma,T,L,q_{0},q_{1},W_{Cn},W_{Fn},W_{Cm}\rangle$ is a 9-tuple, where

  * •

$Q$ is a finite set of symbols; $\Gamma$ is a finite set of alphabet letters;

  * •

$T:Q\rightarrow\\{Ob,Id,Cn,Fn,S1,S2,S12,S21,P1,P2,P12,P21\\}$ maps symbols to
types, where $Ob$ means observations, $Id,Cn,Fn$ are functions, and the rest
are combinators;

  * •

$L:\\{q\in Q:T(q)=Ob\\}\rightarrow\Gamma$ labels every $Ob$-type symbol with a
letter in $\Gamma$;

  * •

$q_{0}\in Q$ is an initial symbol; $q_{1}\in Q$ is an initial input;

  * •

$W_{Cn},W_{Fn},W_{Cm}$ follow the same definition in Definition 2.

For $q\in Q$ and CPP-SO $\mathcal{G}$, we denote the semantics of $q$ as
$\llparenthesis q\rrparenthesis_{\mathcal{G}}:Q\times\Gamma^{*}\times
Q\rightarrow[0,1]$. Following Algorithm 2, we define $\llparenthesis
q\rrparenthesis_{\mathcal{G}}(i,x,j)$ as the probability of
$\textsc{Sample\&Print}(q,i)$ to print $x$ and return $j$. To define the
observation distribution, we fix the initial symbol $q_{0}$ and input $q_{1}$,
then ignore the output. For an observation sequence $x\in\Gamma^{*}$, its
probability is given by $p(x|\mathcal{G})=\sum_{j}\llparenthesis
q_{0}\rrparenthesis_{\mathcal{G}}(q_{1},x,j)$.

Figure 2(a, b) gives two CPP-SO examples, each including a list of additional
rules added to Figure 1(b), a observation distribution defined by these rules,
and an execution trace of Algorithm 2. The execution traces are plotted as
trees. They are analogous to parse trees in PCFGs, but have extra annotations
of symbol types (green nodes and texts for $Cm$, blue nodes for $Cn,Fn,Id$,
and red nodes for $Ob$), inputs (the first values after tree nodes), and
outputs (the second values). Inputs and outputs of different tree nodes are
connected by combinators, as illustrated by the arrows in Figure 2(c).
Different combinators give different information flows. Each recursive call of
Sample&Print advances the tree depth by one, and the Print results (from red
nodes) are read from top to bottom.

We see that CPP-SO can produce much richer observation distributions than
standard PCFGs. The extra information flow of inputs and outputs allows a
parse tree to carry complex computations, many of them hidden from
observations. In the logic example, $q3$ reads an $F$ and passes it to $q4$,
which calls $and$ to produce a $cF$; then, another $q3$ reads a $T$, passes it
to the $cF$ to finish the computation (recall that $and(F)(T)=cF(T)=F$), and
lets $q0$ to print the final result. In the counting example, $q1$ first
generates a random number in $1\sim 4$, prints it, and passes it to $q2$; $q2$
subtracts the number by 1, prints it, compares it with 1, and calls itself to
start a recursion unless the number reaches 1.

Figure 2: CPP-SO examples of (a) Boolean logic, (b) counting, and (c) basic
combinators.

###  3.2 Learning as Bayesian inference (work in progress)

Given the model $p(x|\mathcal{G})$ defined above, learning becomes a Bayesian
inference problem of estimating $p(\mathcal{G}|\mathbf{x})\propto
p(\mathbf{x}|\mathcal{G})p(\mathcal{G})=\prod_{i=1}^{n}p(x_{i}|\mathcal{G})p(\mathcal{G})$,
where $\mathbf{x}$ is a dataset of $n$ i.i.d. observation sequences, and
$p(\mathcal{G})$ specifies the prior of $\mathcal{G}$’s parameters. We assume
that $Q,\Gamma,T,L,q_{0},q_{1}$ are fixed, and $W_{Cn},W_{Fn},W_{Cm}$ follow
Dirichlet distribution priors with a common concentration parameter $\alpha$.
Our inference algorithm is based on a collapsed Gibbs sampler originally
designed for PCFG learning [18], but we replace its Hastings sampler with
Particle Gibbs [19] to avoid the impractical dynamic programming parsing (it
can be derived that the complexity grows from $O(|x|^{3}|Q|^{2})$ for PCFGs to
an unacceptable $O(|x|^{4}|Q|^{6})$ for CPP-SO, where $|x|$ is the sequence
length and $|Q|$ is the number of symbols).

The first step is to introduce parse trees as auxiliary variables and collapse
the parameters of $\mathcal{G}$. For a dataset $\mathbf{x}$, we introduce
$\mathbf{t}$, a set of parse trees, where $t_{i}$ yields observation sequence
$x_{i}$. Thanks to the conjugate prior, $p(\mathbf{t}|\mathbf{x},\alpha)$
provides a sufficient statistics to $p(\mathcal{G}|\mathbf{x})$, such that we
only need to sample $p(\mathbf{t}|\mathbf{x},\alpha)$ without considering
$\mathcal{G}$. We have $p(W_{Cn}(q)|\mathbf{x})\sim
Dirichlet(\boldsymbol{\alpha}+N_{\mathbf{t}}^{Cn}(q,\cdot))$ where
$N_{\mathbf{t}}^{Cn}(q,j)$ is the number of times that a symbol $q$ produces
an output $j$ in $\mathbf{t}$, and $\boldsymbol{\alpha}$ is a vector of
$\alpha$’s. Likewise, $p([W_{Fn}(q)]_{i,\cdot}|\mathbf{x})\sim
Dirichlet(\boldsymbol{\alpha}+N_{\mathbf{t}}^{Fn}(q,i,\cdot))$ where
$N_{\mathbf{t}}^{Fn}(q,i,j)$ is the number of a symbol $q$ having an input $i$
and an output $j$. At last, $p(W_{Cm}(q)|\mathbf{x})\sim
Dirichlet(\boldsymbol{\alpha}+N_{\mathbf{t}}^{Cm}(q,\cdot,\cdot))$ where
$N_{\mathbf{t}}^{Cm}(q,f,g)$ is the number of a symbol $q$ having a pair of
children $f$ and $g$.

Sampling from $p(\mathbf{t}|\mathbf{x},\alpha)$ is achieved by Gibbs sampling,
where we iteratively sample $p(t_{i}|x_{i},\mathbf{t}_{-i},\alpha)$, with
$\mathbf{t}_{-i}=(t_{1},\dots,t_{i-1},t_{t+1},\dots,t_{n})$. Directly
computing $p(t_{i}|x_{i},\mathbf{t}_{-i},\alpha)$ is difficult, but we can
approximate it with Particle Gibbs. When data $x_{i}$ is newly encountered
with no known parse $t_{i}$, we instantiate a Particle Filter with $M$
particles. This includes $M$ independent instances of Algorithm 2 running in
parallel, and we execute them until all perform a Print operation. Then, we
compare the printed labels with $x_{i}$, kill the particles that produce wrong
observations, and duplicate the remaining particles to fill the pool of $M$
particles. This process is repeated until all particles terminate, and all
observations are matched. The remaining particles give an approximate
distribution of $p(t_{i}|x_{i},\mathbf{t}_{-i},\alpha)$, which we can draw
samples from. Once collecting an initial sample of $t_{i}$, later updates on
$t_{i}$ will be driven by Conditional Particle Filters, where the $t_{i}$
before an update will be kept in the particle pool for conditioning. This
overcomes the approximation error of standard Particle Filters and allows the
Gibbs sampler to mix to the target distribution
$p(\mathbf{t}|\mathbf{x},\alpha)$ for any $M>1$.

Note that the presented algorithm is designed for simplicity and practicality
first, and not optimized for efficiency. Left for future works, replacing the
top-down parser (Algorithm 2) with a bottom-up parser and adding ancestor
sampling [20] to Particle Gibbs should both significantly improve the
performance.

##  4 Results and discussion

Here we present the experimental results of some toy examples and discuss the
outcomes.

Figure 3: Dataset samples, parse tree samples in different training phases,
and training curves of (a) concept learning, (b) relation learning with a
curriculum, (c) relation learning without a curriculum.

Concept learning. The first step of learning is to abstract concepts from raw
signals. In CPP-SO, concepts are formulated as outputs of $Cn$-type nodes,
with can be used for further computations (as the $T,F,3,2,1$ in Figure 2).
However, learning such an abstraction is not straightforward, since when an
observation can be generated directly (as the $=,\&,|$ in Figure 2(a)), there
is no reason to use an extra $Cn$ node and a larger tree. To force the
abstraction, we design a dataset that includes sentences with repeating
elements. Let A, B be random words, the sentences all follow the form of
“ABA”. This is motivated by [21], where the authors use the same technique to
teach human infants to learn abstract patterns. Without loss of generality, we
use single-character words (digits in $0\sim 9$) to reduce the parsing
difficulty for faster learning.

From Figure 3(a), we see that in 100 epochs of Gibbs sampling, the model’s
training exhibits two phases, each having a sharp drop in predictive negative
log-likelihood (NLL). In phase 1, the model learns a context-free grammar to
capture the sentences, without realizing the connection between the first and
the last words. In phase 2, the model learns a more complex rule with a
$Cn$-type node $c1$, correctly identifying the “ABA” pattern.

Relation learning. The next step of learning is to discover relations among
the known concepts. In CPP-SO, relations are captures by input-output
distributions of $Fn$-type nodes. The challenge of relation learning is that
it happens only after concept learning. To achieve that, we resort to the
technique of Curriculum Learning [22], where we separate a dataset in to
multiple levels, and feed data progressively from lower levels to higher
levels.

Here our goal is to learn a function $f(x)=(x+1)\%10$ ($\%$ stands for
modulo). Figure 3(b) shows a model trained with 50 epochs of level-1 data (of
pattern “ABA”), 50 epochs of mixed data (level-1 data progressively replaced
by level-2 data), and 50 epochs of level-2 data (of pattern “ABf(A)”). After
some jitters in the initial data mixing period, we see that the model
correctly captures the $(x+1)\%10$ relation in a $Fn$-type node $f1$. However,
as seen from Figure 3(c), if we start directly with level-2 data without a
level-1 warm up, the model will fail to capture the correct relation (note the
higher NLL in (c) than in (b)).

Knowledge composition. At last, we consider how to compose existing relations
to new relations, and generalize to unseen cases. Here our target is to learn
$g(x)=(x+2)\%10=(f\triangleright f)(x)$. A naive attempt would be to introduce
a level-3 data of pattern “ABg(A)”, however, the learned model will not
generalize: it directly memorize $(x+2)\%10$ using a $Fn$ node, without using
a $Cm$ node to capture the composition. Then, if A is restricted to digits
$0\sim 6$ during training, the prediction will fail when letting $A=7\sim 9$
during testing. See Appendix for more discussions on challenges and solutions
to obtain the correct composition.

Discussion. The experiments reveal several limitations of our current learning
method. One issue is that since a model must master one level of curriculum
before advancing to the next level, if the curriculum is long, the model is
unlikely to pass all levels. This can be systematically solved by having a
“meta” Particle Filter over the Gibbs sampler: to simulate multiple MCMC
chains in parallel, and resample after each curriculum level. A deeper issue
is about the curriculum design, as can be observed from the complex datasets
used in the above experiments. A good curriculum must supply the right form of
data at the right level, and update smoothly to guide a model’s progress.
Without a good curriculum, the model either fails to learn, or learn the wrong
pattern.

We believe the curriculum design is an intrinsic challenge of learning complex
patterns without supervision. Human learners circumvent this issue by sensing
a wide range of non-language clues. Human infants learn numbers by seeing
visual objects, addition by counting fingers, multiplication by teachers’
instructions. By comparison, our text-only training is equivalent to a human
trying to learn math with exercise questions only: no teachers, no
discussions, even no textbooks. Perhaps a more natural approach of learning is
to begin with control instead of language problems, like how human infants
learn to move before to speak. Control problems have “built-in” curriculum
automatically generated by the progressive exploration of more complex
environments and actions.

Despite the limitations, our results show that CPP-SO includes all necessary
components for compositional learning, and works as a small scale functioning
prototype. A bigger lesson from CPP-SO it that we can jump out of the long-
standing dichotomy of neural and symbolic methods. Backpropagation through
matrix multiplications is not the only way to train connectionist networks:
probabilistic methods can be equally useful (as in Section 3.2). Symbolic
relations may not be limited in a human readable/programmable form: a
continuous relaxation can still maintain a well-defined semantics (as in
Definition 2). By freely recombining structures and semantics of existing
systems, we have a rich world of new models to explore.

##  5 Related works

Neuralsymbolic methods. Besides the two categories introduced in Section 1,
some neuralsymbolic methods do exhibit connectionist structures and relational
semantics. Tensor symbolic representation [23] use tensor products to capture
relations, at the cost of expensive computation (similar to Equation 3). We
circumvent the dense summation by particle-based sparse sampling and make the
algorithm computationally practical. Logical neural networks [24] use a first-
order logic semantics, which leads to different inference algorithms.

Probabilistic program synthesis. Our work is closely related to probabilistic
program synthesis [25, 26, 27], due to the similar semantics and inference
algorithms. However, existing works focus on solving problems in restricted
domains with domain-specific languages. Our method is designed for general
sequence modeling, which aims to potentially model general cognition and
human-like language-driven learning.

Probabilistic neuron models. Since the Bayesian brain hypothesis, there has
been numerous models of probabilistic interpretations of neural coding,
although the applications have been limited to simple perceptual and control
problems [28, 29]. Our connectionist formulation of probabilistic programs
might provide possible ways to bridge probabilistic neuron models to high
level reasoning.

Formal semantics theory. The design of CPP-SO is heavily inspired by the
semantics theory of natural language [30], in particular [31], where meaning
of (sub-)sentences is given by combinators and higher-order functions. We
extend the lexicalized grammar (where all functions are attached to words) to
support hidden computations (with non-observed sub-trees) for more flexible
modeling.

##  6 Conclusion

We present CPP and CPP-SO as methods to express and learn compositional
knowledge. Our initial experiments show their capability to extract concepts
and relations from raw sequential data. Although learning complex patterns is
limited by the difficult curriculum design, the functioning of our method
suggests the potential of rethinking and recombining the structural and
semantic components of classical algorithms. As for future works, we are
looking for efficient inference algorithm (based on bottom-up parsing) that
scales well to natural language processing. Meanwhile, by extending the
grammar to model observation-action sequences, we will apply it to
reinforcement learning and optimal control problems, which avoids the
curriculum design issue and moves closer to fully autonomous learning. In a
long term, it would be interesting to see if learning and compositionality are
sufficient to simulate human-like intelligence, or there are more necessary
elements to be included.

## References

  * [1] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [2] David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan, David Gondek, Aditya A Kalyanpur, Adam Lally, J William Murdock, Eric Nyberg, John Prager, et al.  Building watson: An overview of the deepqa project.  AI magazine, 31(3):59–79, 2010.
  * [3] Tomer D Ullman, Andreas Stuhlmüller, Noah D Goodman, and Joshua B Tenenbaum.  Learning physical parameters from dynamic scenes.  Cognitive psychology, 104:57–82, 2018.
  * [4] Luciano Floridi and Massimo Chiriatti.  Gpt-3: Its nature, scope, limits, and consequences.  Minds and Machines, 30(4):681–694, 2020.
  * [5] Md Kamruzzaman Sarker, Lu Zhou, Aaron Eberhart, and Pascal Hitzler.  Neuro-symbolic artificial intelligence: Current trends.  arXiv preprint arXiv:2105.05330, 2021.
  * [6] Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural turing machines.  arXiv preprint arXiv:1410.5401, 2014.
  * [7] Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein.  Neural module networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 39–48, 2016.
  * [8] Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou.  Neural logic machines.  arXiv preprint arXiv:1904.11694, 2019.
  * [9] Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow.  Deepcoder: Learning to write programs.  arXiv preprint arXiv:1611.01989, 2016.
  * [10] Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B Tenenbaum, and Jiajun Wu.  The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision.  arXiv preprint arXiv:1904.12584, 2019.
  * [11] Ameesh Shah, Eric Zhan, Jennifer Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri.  Learning differentiable programs with admissible neural heuristics.  Advances in neural information processing systems, 33:4940–4952, 2020.
  * [12] Warren S McCulloch and Walter Pitts.  A logical calculus of the ideas immanent in nervous activity.  The bulletin of mathematical biophysics, 5(4):115–133, 1943.
  * [13] Stephen I Gallant et al.  Perceptron-based learning algorithms.  IEEE Transactions on neural networks, 1(2):179–191, 1990.
  * [14] Noah D Goodman, Joshua B. Tenenbaum, and The ProbMods Contributors.  Probabilistic Models of Cognition.  http://probmods.org/v2, 2016.  Accessed: 2022-5-17.
  * [15] Johannes Borgström, Ugo Dal Lago, Andrew D Gordon, and Marcin Szymczak.  A lambda-calculus foundation for universal probabilistic programming.  ACM SIGPLAN Notices, 51(9):33–46, 2016.
  * [16] Frank Wood, Jan Willem Meent, and Vikash Mansinghka.  A new approach to probabilistic programming inference.  In Artificial Intelligence and Statistics, pages 1024–1032. PMLR, 2014.
  * [17] Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, and Frank Wood.  An introduction to probabilistic programming.  arXiv preprint arXiv:1809.10756, 2018.
  * [18] Mark Johnson, Thomas L Griffiths, and Sharon Goldwater.  Bayesian inference for pcfgs via markov chain monte carlo.  In Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pages 139–146, 2007.
  * [19] Nicolas Chopin and Sumeetpal S Singh.  On particle gibbs sampling.  Bernoulli, 21(3):1855–1883, 2015.
  * [20] Jan-Willem Meent, Hongseok Yang, Vikash Mansinghka, and Frank Wood.  Particle gibbs with ancestor sampling for probabilistic programs.  In Artificial Intelligence and Statistics, pages 986–994. PMLR, 2015.
  * [21] Alexa R Romberg and Jenny R Saffran.  Statistical learning and language acquisition.  Wiley Interdisciplinary Reviews: Cognitive Science, 1(6):906–914, 2010.
  * [22] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston.  Curriculum learning.  In Proceedings of the 26th annual international conference on machine learning, pages 41–48, 2009.
  * [23] Paul Smolensky.  Tensor product variable binding and the representation of symbolic structures in connectionist systems.  Artificial intelligence, 46(1-2):159–216, 1990.
  * [24] Ryan Riegel, Alexander Gray, Francois Luus, Naweed Khan, Ndivhuwo Makondo, Ismail Yunus Akhalwaya, Haifeng Qian, Ronald Fagin, Francisco Barahona, Udit Sharma, et al.  Logical neural networks.  arXiv preprint arXiv:2006.13155, 2020.
  * [25] Feras A Saad, Marco F Cusumano-Towner, Ulrich Schaechtle, Martin C Rinard, and Vikash K Mansinghka.  Bayesian synthesis of probabilistic programs for automatic data modeling.  Proceedings of the ACM on Programming Languages, 3(POPL):1–32, 2019\.
  * [26] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum.  Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning.  arXiv preprint arXiv:2006.08381, 2020.
  * [27] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum.  Human-level concept learning through probabilistic program induction.  Science, 350(6266):1332–1338, 2015.
  * [28] Kenji Doya, Shin Ishii, Alexandre Pouget, and Rajesh PN Rao.  Bayesian brain: Probabilistic approaches to neural coding.  MIT press, 2007.
  * [29] Wei Ji Ma and Mehrdad Jazayeri.  Neural coding of uncertainty and probability.  Annual review of neuroscience, 37:205–220, 2014.
  * [30] Elizabeth Coppock and Lucas Champollion.  Invitation to formal semantics.  Manuscript, Boston University and New York University. eecoppock. info/semantics-boot-camp. pdf, 2019.
  * [31] Mark Steedman and Jason Baldridge.  Combinatory categorial grammar.  Non-Transformational Syntax: Formal and Explicit Models of Grammar. Wiley-Blackwell, pages 181–224, 2011.

##  Appendix A Appendix

###  A.1 Concept learning

In this experiment we try to learn $Cn$ nodes with “ABA” pattern data.

Experiment setup:

  * •

Dataset design: the dataset includes 100 i.i.d. samples drawn by the following
algorithm: given an alphabet $\Gamma=\\{0,1,2,3,4,5,6,7,8,9\\}$, sample $A$
and $B$ independently and uniformly from $\Gamma$, and then return the
concatenation of $string(A)$, $string(B)$, and $string(A)$ (here $string()$
converts a number, e.g. $0$, to a string “0”).

  * •

Hyperparameter setting: in addition to 10 $Ob$-type nodes (one for each
alphabet letter), we include 3 nodes for $S2$ and $S12$ type each, 2 nodes for
$Cn$ and $Fn$ type each, and 1 node for type $Id$. Initial symbol $q_{0}$ and
input $q_{1}$ are both set to a $S2$-type node. The weights all follow
Dirichlet priors with $\alpha=0.1$, except for one special element in
$W_{Cm}$, as described next. The number of particles is 100.

  * •

Special initialization: denote a $S12$-type node $q_{4}$, a $Cn$-type node
$c_{1}$, the $Id$-type node $id$, we raise the $\alpha$ for
$[W_{Cm}(q_{4})]_{c_{1},id}$ to 100. This special initialization forces a high
initial probability for $q_{4}$ to expand to $c_{1}$ and $id$.

  * •

Training procedure: we train the model on the described dataset for 100
epochs.

  * •

Performance metric: we report the negative log likelihood (NLL) of the
observation sequence normalized by the sequence length. Note the NLL cannot be
computed directly, and we use the Particle Filter weights to get an unbiased
estimation. In the plots, we apply an exponential smoothing to the normalized
NLL with rate $0.9$.

Results: We show the NLL-epoch plots for 10 independent MCMC runs. Each run
takes around 15 seconds on a 4-core CPU. Despite the different shape of
learning curves, all models successfully captures the “ABA” pattern.

###  A.2 Relation learning

In this experiment we try to learn $Fn$ nodes with “ABf(A)” pattern data.

Experiment setup:

  * •

Dataset design: the level-1 dataset is the same as above. The level-2 dataset
includes 100 i.i.d. samples drawn by the following algorithm: given an
alphabet $\Gamma=\\{0,1,2,3,4,5,6,7,8,9\\}$, sample $A$ and $B$ independently
and uniformly from $\Gamma$, then return the concatenation of $string(A)$,
$string(B)$, and $string(f(A))$ (here $string()$ converts a number, e.g. $0$,
to a string “0”, and $f(x)=(x+1)\%10$).

  * •

Hyperparameter setting: the same prior distribution as above. The number of
particles is expanded to 400.

  * •

Special initialization: the same as above.

  * •

Training procedure: we first train the model on the level-1 dataset for 50
epochs. Then among the next 50 epochs of training, in each epoch we randomly
select 2 level-1 data entries and replace them with 2 level-2 data entries. At
last, we train the model on the fully replaced dataset (only including level-3
data) for another 50 epochs.

  * •

Performance metric: the same as above.

Results: We show the NLL-epoch plots for 10 independent MCMC runs. Each run
takes around 80 seconds on a 4-core CPU. Whether the model successfully learns
$f$ depends on the exact way it captures the level-1 data. The learning will
succeed if level-1 data are captured by a tree structure that include an $Id$
node outside of $q_{4}$ (e.g., the one in Figure 3(a), epoch 100), since this
$Id$ node can be replaced by an $Fn$ node during level-2 learning. For tree
structures that do not include an $Id$ node outside of $q_{4}$, the learning
will fail.

###  A.3 Relation learning (alternative method)

In this experiment we provide a more efficient (higher success rate) way to
learn $Fn$ nodes with “ABAf(A)” pattern data.

Experiment setup:

  * •

Dataset design: the level-1 dataset is the same as in Experiment A.1. The
level-2 dataset includes 100 i.i.d. samples drawn by the following algorithm:
given an alphabet $\Gamma=\\{0,1,2,3,4,5,6,7,8,9\\}$, sample $A$ and $B$
independently and uniformly from $\Gamma$, then return the concatenation of
$string(A)$, $string(B)$, $string(A)$, and $string(f(A))$ (here $string()$
converts a number, e.g. $0$, to a string “0”, and $f(x)=(x+1)\%10$).

  * •

Hyperparameter setting: the same as above.

  * •

Special initialization: the same as above.

  * •

Training procedure: the same as above.

  * •

Performance metric: the same as above.

Results: We show the NLL-epoch plots for 10 independent MCMC runs. Each run
takes around 100 seconds on a 4-core CPU. By use a longer observation sequence
to better guide the learning, we find an increased success rate of learning
the right relation (note that due to the longer sequence, the normalized NLLs
can be lower than those in Experiment A.2).

###  A.4 Knowledge composition (naive method, failed)

In this experiment we try to learn a relation $f$ with “ABf(A)” data first,
then learn $g$ with “ABg(A)” data where $g=f\triangleright f$. However, the
model directly memorizes the $g$ as a $Fn$ node without learning the
composition $f\triangleright f$.

Experiment setup:

  * •

Dataset design: the level-1 and level-2 datasets are the same as in Experiment
A.1 and A.2, respectively. The level-3 dataset includes 100 i.i.d. samples
drawn by the following algorithm: given an alphabet
$\Gamma=\\{0,1,2,3,4,5,6,7,8,9\\}$, sample $A$ and $B$ independently and
uniformly from $\Gamma$, then return the concatenation of $string(A)$,
$string(B)$, and $string(g(A))$ (here $string()$ converts a number, e.g. $0$,
to a string “0”, and $g(x)=(x+2)\%10$).

  * •

Hyperparameter setting: the same as above.

  * •

Special initialization: the same as above.

  * •

Training procedure: we first train the model on level-1 data for 50 epochs,
then mixed level-1 and 2 data for 50 epochs (following the same mixing policy
as in Experiment A.2), then level-2 data for 50 epochs, then mixed level-2 and
3 data for 50 epochs, at last level-3 data for 50 epochs.

  * •

Performance metric: the same as above.

Results: We show the NLL-epoch plots for 10 independent MCMC runs. Each run
takes around 150 seconds on a 4-core CPU. We see that if a model successfully
learns level-2 data, it will also succeeds level-3. However, by analyzing the
learned model’s weights, we find that once level-2 data are replace by level-3
data, the model forgets the relation $f$, and replaces it by the relation $g$.
Therefore, without a good dataset design, the model fails to learn the right
composition.

###  A.5 Knowledge composition (alternative method 1, failed)

In this experiment we try to provide a better guide to the learning with
“ABAf(A)” data first, and then “ABAf(A)g(f(A))” data later. However, the model
still cannot learn the composition.

Experiment setup:

  * •

Dataset design: the level-1 and level-2 datasets are the same as in Experiment
A.1 and A.3, respectively. The level-3 dataset includes 100 i.i.d. samples
drawn by the following algorithm: given an alphabet
$\Gamma=\\{0,1,2,3,4,5,6,7,8,9\\}$, sample $A$ and $B$ independently and
uniformly from $\Gamma$, then return the concatenation of $string(A)$,
$string(B)$, $string(A)$, $string(f(A))$, and $string(g(f(A)))$ (here
$string()$ converts a number, e.g. $0$, to a string “0”, and
$g(x)=(x+2)\%10$).

  * •

Hyperparameter setting: the same as above.

  * •

Special initialization: the same as above.

  * •

Training procedure: the same as above.

  * •

Performance metric: the same as above.

Results: We show the NLL-epoch plots for 10 independent MCMC runs. Each run
takes around 200 seconds on a 4-core CPU. The idea of this dataset design is
to force the model learn $g$ without forgetting $f$, since it must first apply
$f$ to produce $f(A)$, and then $g$ to produce $g(f(A))$. In theory, the model
should capture the composition $g=f\triangleright f$ if the MCMC chain mixes.
However, we do not observe that in practice. By analyzing the learned weights,
we see the model always learns two separate $Fn$ nodes, where one captures $f$
and the other captures $g$.

###  A.6 Knowledge composition (alternative method 2, failed)

In this experiment we directly encode $f$ to the prior. We find that the
failure of composition learning is due to the inefficient top-down parser from
Algorithm 2, instead of the dataset or curriculum design.

Experiment setup:

  * •

Dataset design: the same as in Experiment A.4.

  * •

Hyperparameter setting: the same as above.

  * •

Special initialization: in addition to the one in Experiment A.1, we select a
$Fn$-type node $f_{1}$, and set the prior of $W_{Fn}(f_{1})$ to capture the
relation $f(x)=(x+1)\%10$, i.e., the $\alpha$ of $[W_{Fn}(f_{1})]_{i,j}$ is
set to 100 if $L(j)=f(L(i))$, and 0.1 otherwise.

  * •

Training procedure: similar to Experiment A.2, but using level-1 and level-3
datasets, instead of level-1 and level-2.

  * •

Performance metric: the same as above.

Results: We show the NLL-epoch plots for 10 independent MCMC runs. Each run
takes around 100 seconds on a 4-core CPU. Here we simplify Experiment A.5 by
directly initialize the relation $f$ as a prior, without learning it from a
curriculum. However, learning the composition still fails in all 10 runs.

Our analysis shows that the top-down parser of Algorithm 2 is extremely
inefficient in identifying novel function compositions: it must guess the
first $f$ correctly by pure chance, then the second $f$ correctly by pure
chance again, until composing them to $g$. This implies that the probability
of making the correctly guess scales inverse-squared to the number of symbols.
Thus, although learning the correct composition should happen if we continue
the MCMC forever, we never see it happens in the first 100 epochs of Gibbs
sampling.

###  A.7 Knowledge composition (alternative method 3, succeeded)

As a temporary fix, here we adjust the prior to successful guide the
composition learning. Meanwhile, our initial analysis (not presented here)
shows that the working-in-progress bottom-up parser can systematically solve
this problem without relying to such ad-hoc prior adjustments. The difficulty
of composition learning found in the above experiments is not a fundamental
problem of the CPP-SO framework, and will be solved soon in future works.

Experiment setup:

  * •

Dataset design: the same as above.

  * •

Hyperparameter setting: the same as above.

  * •

Special initialization: in addition to the one in Experiment A.6, we select a
$S2$-type node $q_{2}$, and set the prior of $[W_{Cm}(q_{2})]_{f_{1},f_{1}}$
to 100, forcing it to capture the composition $f\triangleright f$.

  * •

Training procedure: the same as above.

  * •

Performance metric: the same as above.

Results: We show the NLL-epoch plots for 10 independent MCMC runs. Each run
takes around 100 seconds on a 4-core CPU. In this experiment, we adjust the
prior to force the symbol $q_{2}$ to have a high probability of composing two
$f_{1}$’s. The resulting model correctly learns the desired composition
whenever successfully modeling the data.