UAI 2009

WINGATE ET AL.

607

The Infinite Latent Events ModelDavid Wingate, Noah D. Goodman, Daniel M. Roy and Joshua B. Tenenbaum
Brain and Cognitive Sciences
Massachusetts Institute of Technology
Cambridge, MA 02139

Abstract
We present the Infinite Latent Events Model,
a nonparametric hierarchical Bayesian distribution over infinite dimensional Dynamic
Bayesian Networks with binary state representations and noisy-OR-like transitions.
The distribution can be used to learn structure in discrete timeseries data by simultaneously inferring a set of latent events, which
events fired at each timestep, and how those
events are causally linked. We illustrate themodel on a sound factorization task, a network topology identification task, and a video
game task.

1

INTRODUCTION

Inferring latent structure in temporal data is an important timeseries modeling problem. Consider the taskof using fMRI data to recognize coherent brain activity(latent events), discover which brain activity leads toother activity (causal structure), and determine the relationship between latent brain activity and observed
brain scans (observation model). As this example
suggests, sequences of high-dimensional observations
are often generated as the result of latent events inthe external world, where events at time t interact tocause events at time t + 1. Given the observations, wewish to recover a factored representation of the latentstate space and learn a structured representation of
the transition probabilities governing the evolution of
the state. Thus, we must simultaneously address thestate-space learning problem and the structure learning problem of factored probabilistic models.
For various reasons, traditional state space models are
inadequate for this setting. Many timeseries models
descend from the Hidden Markov Model (or HMM)[13], which assumes that an unobserved Markov chainof latent states exists, and that the observation at time
Copyright held by author/owner.

t is conditionally independent of all other observations
and states given the latent state at time t. A typical parametric Bayesian prior for an HMM fixes thenumber of latent states and places no restriction on
the structure of the transition probabilities, rendering these models ineffective for data sets where thenumber of latent states far exceeds the amount of observed data, as would be the case in the combinatorial
examples that motivate this work. The Hierarchical
Dirichlet Process (HDP) HMM [1, 14] relaxes the assumption of a fixed, finite number of states, instead
positing a countably infinite number of latent states
and a random transition kernel where transitions to a
finite number of states account for all but a tiny fraction of the probability mass. However, like parametric HMMs, the nonparametric HDP-HMM does notprovide adequate inductive bias in combinatorial state
spaces in the face of limited data.
This issue was one of the motivations behind the Factorial HMM [6], which assumes that the state spacefactors into K components that evolve as independent
Markov chains. The nonparametric Infinite Factorial
HMM (IFHMM) [4] eliminates the need to specify K.
While the additional structure in the Factorial HMM
produces a strong inductive bias and can significantly
reduce sample complexity, the independence assumption is inappropriate as we expect there to be interactions between the latent factors.
Instead, we wish to model structured causal interactions between latent events. Dynamic Bayesian Networks (DBNs) relax the independence assumption of
Factorial HMMs, assuming only that the distributionof states at time t + 1 factors when conditioned on thestate at time t.
We present the Infinite Latent Events Model (ILEM),
which can be seen as a nonparametric distribution overa restricted class of DBNs. We use the ILEM as a priorin a hierarchical Bayesian timeseries model to simultaneously address the state-space estimation problem
and the structure learning problem: MAP inference in608

WINGATE ET AL.

UAI 2009

causal link in the DBN that was heretofore unused.

Figure 1: The ILEM can learn timeseries structure.
Given observations (represented here as images) it infers latent events, actual causes, and prototypical latent observations.

the ILEM learns a latent state sequence and its properties, including the number of relevant latent factors
in the state space, the values of those factors at eachtimestep, and the causal structure between those factors. The ILEM combines elements of classical models and their nonparametric counterparts: we assume
that observations are generated through a combination of latent events (like an IFHMM), which are coupled through a hierarchy of Dirichlet processes (like the
HDP-HMM), and that there is a factored dependence
structure relating successive events (like a DBN).
The problem of structure learning in DBNs is a difficult one. Ghahramani [5], for example, assumes thatthe dependencies between states is known and discusses learning maximum likelihood parameter estimates of HMM, factorial and tree-structured latentstate spaces using variational, sampling and EM algorithms; more recent work has focused on learning
the structure itself [10], but most algorithms assume
that data is fully observed [3, 2].
Our contribution is a novel perspective on what itmeans to learn causal structure. In contrast to othermethods which explicitly attempt to describe a transition network that holds between t and t + 1 for all t,
we leave the causal network latent, and instead reason
about causality in actual cause form: we explicitly
represent which actual event at time t caused which
actual event at time t + 1, implicitly integrating out
the latent causal network.
This has the effect of introducing more latent variables(there is now one for each possible cause/effect relationship at every timestep), which we couple together
via a hierarchy of Dirichlet processes (DPs). The DPs
allow the variables to share statistical strength, andtheir distributed nature softens inference and allows
for emergent causal structure. Our model uses a hierarchy of DPs to capture the idea that there is always the possibility of a new dimension in the state
representation that was heretofore unknown, or a newThis addresses an important open question for manytimeseries models: how to infer their dimension (e.g.,
the number of latent states (HMM), chains (Factorial HMM), or factors (DBN)). While the dimensionof the latent space under this nonparametric prior iscountably infinite, the model balances its preference
to utilize as few dimensions as possible with the needto explain the data. Given data, we can determine the
distribution of the number of dimensions actually usedby the observed data.

2

THE INFINITE LATENT
EVENTS MODEL

The ILEM is a nonparametric distribution over a state
sequence with a latent causal structure governing statetransitions. States are represented as binary vectors,
with each active bit representing an event. Transition probabilities between states are defined by bitwise
noisy-ORs, with parent events causing child events (oreffects). The ILEM is a distribution p(X, C) over two
objects: X, representing events, and C, representing
actual causes. Figure 1 illustrates this: observations
are shown as images, states are represented as a binary vectors, and actual causes are represented as thearrows between events.
2.1

THE LATENT EVENTSEvents are represented as a matrix X ∈ {0, 1}T ×∞ ,where Xt,i indicates whether or not event i was active
at time t (similar to the IFHMM and the Indian Buffet process (IBP) [7]). The total number of triggered
events is potentially unbounded. As an example, thematrix
1 0 0 1
 1 0 1 0
X =  1 1 0 1 ···  0 1 1 0

0 0 0 1
represents the latent events in Fig. 1 with T = 5. Only
four latent events are observed here.
2.2

THE CAUSAL STRUCTURE

To represent actual causes, we use a tensor C ∈NT ×∞×∞ , where Ct,i,j represents the number of times
event i triggered event j, causing event j to be active
at time t. C is constrained such that Ct,i,j > 0 iff
Xt,i = 1 and Xt+1,j = 1. Importantly, note that C
does not specify a connection topology in the usual
sense—entries in C should not be considered edges
in a graphical model which govern state transitions.
Rather, they should be viewed as evidence of an edge.

WINGATE ET AL.

Graphical Model for theILEM

The HDP-HMM

βπk∼ GEM(αbase )∼ DP(αtrans , β)πbkg
Nt,bkg∼ DP(αbkg , β)
∼ Poisson(λbkg )Nt,kDt,k,i∼ Poisson(λbase )
∼ πk

Nt,k
Dt,k,i

= 1
∼ πk

Ct,k
X1

= {Dt,k,i : i ≤ Nt,k }= C1,bkg
[
=
Ct,k

Ct,k
X1

= {Dt,k,i : i ≤ Nt,k }
∼ β
[
=
Ct,k

Xt

k∈Xt−1 ∪{bkg}β∼ GEM(αbase )πk∼ DP(αtrans , β)

Xt

αbase

β

α transπk

α bkgk∈Xt−1

λ base , λ bkg

N1,bkg

N2,k
8

The ILEM

609

8

UAI 2009

X1

X2

Y1

Y2

...

Figure 2: Generative processes for the ILEM (left) and HDP-HMM (middle), and graphical model of the ILEM
(right). Here β is drawn from a GEM distribution, which is a distribution over the integers [12]; πk are theindividual transition DPs for each possible latent event, Nt,k are the counts of the number of child events caused
by each parent event k at each time t, and {Dt,k,i }i≥0 is the set of all possible events generated by event k attime t. The derived random variables Ct,k and Xt select the actual causes and events at every time t.
2.3

THE STOCHASTIC GENERATIVEPROCESS FOR THE ILEM

We now describe p(X, C) via its generative process(see Fig. 2 for the graphical model). In the following,
we assume that there is a distinguished background
event, which is always active and which has its own
hyperparameters, but which is otherwise identical toall other events.
Imagine that we have generated a sequence of latentstates X1 , · · · , Xt−1 , recording which events caused
which other events in the C tensor. To generate Xt ,we iterate over each active event i at time t − 1 andsample child events as follows:• Sample Nt,i ∼ Poisson(λbase ), which is the numberof child events that i actually causes at time t.
• Sample Nt,i child events from a private Dirichlet
process for parent event i.
To sample child events from event i’s private DP:• Sample an event from a multinomial distribution
over previously caused events. With probability
Ci,j /(Ci + αtrans ), cause event j, which event i has
previously caused Ci,j times. The total
P number of
events previously caused by i is Ci = j Ci,j .

• With probability αtrans /(Ci + αtrans ), cause a newevent.
To cause a new event:• With probability Bj /(B + αbase ), parent i causes
an event that has been previously caused by otherevents (or the background). Bj is the numberof events which have ever caused j, so that B =P

j Bj is the number of events caused by any latent event.

• With probability αbase /(B + αbase ), parent i causes
a new event that has never been caused by anyother event or the background.
Finally, we increment Ct,i,j every time event j triggers
event i. We set Xt,i = 1 if Ct,i,j ≥ 1 for any event
j. (Note that C can be more than 1, which could
be interpreted in different ways for different causation
and/or observation models; most likely, it would represent a strength of causation. We will only consider
observations models that depend on X.)
Thus, like the HDP-HMM and other stochastic processes based on DPs, each latent event prefers to cause
events which it has already caused before, but there isalways some probability it will cause a new event which
others have caused, or a completely new event which
has never been caused before.
The parameters of the model are the concentration
parameters αbase , αtrans and αbkg , which govern theDPs, and the Poisson parameters λbase and λbkg .
2.4

PROPERTIES OF THE PARAMETERS

The ILEM can exhibit qualitatively different inductive
biases depending on the hyperparameter settings. For
example, the three concentration parameters αbase ,αtrans and αbkg each control different DPs. For any
given DP and its parameter α, the expected numberof distinct values sampled is proportional to α.
This implies that we can control how much the model
favors determinism by setting αtrans to be small. This610

WINGATE ET AL.

effectively controls the number of unique successor
events for any given latent factor xi . We can similarly influence how many unique events are allowed
to be used overall (via αbase ) and how many are explained by the background (via αbkg ). The parameterλbase influences the expected number of child events
caused by a given latent factor at any time t, while
λbkg similarly controls the expected number of child
events caused by the background.
2.5

COMPUTING THE LIKELIHOOD

Given the generative process described previously, thejoint probability density of a particular X and C is:p(X, C) =KY!

CRP(Bk , αbase ) CRP(Cbkg,k , αbkg )

k=1
K Y
K
Y

!

CRP(Ci,k , αtrans )(1)

Poisson(Nt,bkg , λbkg )!

i=1 k=1
T
Y

t=1

Y

Poisson(Nt,i , λbase )i∈Xtwhere K is the total number of latent events used,
active(t) is the set of active events at time t, Nt,i isthe number of child events of parent event i at time t,Nt,bkg is the number of child events of the background
event at time t, andCRP(x, α) = αK

K
Y
Γ(α)
P
Γ(xi )
Γ(α + i xi ) i=1

is the likelihood of a set of counts under a Chinese
Restaurant process with concentration parameter α.
Like other causal models, the sequence of latent events
is not fully exchangeable in time; rather it is Markov
exchangeable [1], meaning that events and their actual
causes can only be exchanged if they do not change theDP counts. However, a weaker property of exchangeability is preserved: the posterior predictive transition
probabilities only depend on counts of observed transitions, and not when those transitions occurred.

UAI 2009

not have a background event, and second, the HDPHMM sets Nt,k = 1. This implies that the HDP-HMM
models the evolution of a single sequence of states.
By sampling multiple effects for each event, the ILEM
naturally extends this to modeling the evolution of afactored state sequences, with flexible causal dependencies between successive states.
Noisy-OR DBNs. If any active parent event Xt,i
triggers event j, then Xt+1,j is activated. By taking
the stick-breaking view on the events’ private DPs, we
can view the ILEM as a noisy-OR DBN with an infinite set of binary nodes at each timestep, each fully
connected to the nodes at the next timestep. Using
the CRP representation of the DP implicitly integrates
out all of these connections, leaving just a few hyperparameters. This relationship to noisy-OR DBN’s
is formalized in Appendix A; similar connections between DPs, IBPs and noisy-OR models are describedby Wood et al. [16].
2.7

OBSERVATION MODELS

To complete the generative model, we must specify anobservation model p(Y |X, C). We now describe one
possible choice: the linear-Gaussian observation model
used by Griffiths & Ghahramani [7].
In this model, an observation yt is generated froma Gaussian with mean Axt and covariance matrix
ΣY = σY2 I. Assuming D-dimensional observations,the matrix A is D × K (where K is the maximum
number of events which are ever used). Each column
Ai can be thought of as a prototypical observation associated with latent event xi ; the observation yt is alinear combination of these prototypical observations
plus noise. In an image modeling context, for example,
each column Ai would correspond to a prototypical
sprite associated with latent event xi .
The prototypical representations are unknown, and so
the model places a matrix Gaussian prior (with vari2
ance σA) on A, and then integrates out A. This yields
the following marginal density:
1
1p(Y|X) = exp − 2 tr(YT (I − XM−1 XT )Y)
Z
2σY
ND

D
(N −K)D KD
σA |M| 2

where Z = (2π) 2 σY
2.6

RELATIONSHIP TO OTHER MODELSThe ILEM is closely related to two existing dynamicalsystem models: the HDP-HMM, and noisy-OR DBNs.
The HDP-HMM. The ILEM can be seen as a generalization of the HDP-HMM. For comparison purposes,
Fig. 2 gives the generative model of the HDP-HMM
alongside the ILEM. There are two major differences
between the two models: first, the HDP-HMM doesis the Gausσ2

sian normalization constant and M = XT X + σY2 I.
AUnder this observation model (see [7]), the means of
the Gaussians associated with each latent event can berecovered in closed form as:
E[A|Y, X] = (XT X +σY2 −1 T
X Y
2 I)
σA

Later, we use this equation to recover the prototypicallatent observations associated with each event.

UAI 2009
2.8

WINGATE ET AL.

INFERENCE

We now describe our MCMC inference algorithm for
the ILEM using the linear-Gaussian observation model(see Sec. 2.7).
To begin, we make a simplifying approximation. It isthe case that the linear-Gaussian observation is conditionally independent of the actual cause matrix C
given the the binary event matrix X. Specifically, howmany times event i triggers event j has no effect on
the likelihood—only whether the event was triggeredor not affects the observation. To make inference efficient, we constrain our sampler to explore only the
space where C is binary-valued, sampling, in effect,from a conditional distribution of the model. We stillscore with Eq. 1, which is now only proportional to thejoint density; this presents no difficulty for the MCMC
sampler.
In order to explore the latent space, we use acombination of single-site Gibbs sampling steps andMetropolis-Hastings (MH) moves. In particular, we
sample each entry in the event matrix and actual cause
matrix using Gibbs updates, because the conditional
distributions have trivial closed forms given our binary assumption above. Changes to X and C onlychange a few sufficient statistics within each DP andPoisson, so changes to the likelihood can be computed
incrementally. Often, such incremental changes canbe propagated to the observation model; in the case of
the linear-Gaussian model, efficient rank-one updates
can be applied to the necessary matrix inverses anddeterminants.
We found that certain MH moves improved mixing
considerably. One particularly useful MH move randomly rewrites a candidate event Xt,i as a different
event Xt,k , rewiring causes and effects to the event’s
new label. For this move, we consider all possible
rewrites for all active latent events at a particular
timestep. Another useful MH move swaps parent
events, turning off Ct,i,k and turning on Ct,j,k simultaneously. Finally, we annealed the sampler during
burn-in using a geometric temperature schedule. For
MAP estimates, we continued to anneal the temperature towards zero.

3

EXPERIMENTS

We evaluate the ILEM on three different data sets designed to illustrate different properties of the model:
a causal soundscape factorization task; a simple
video game task, and a network topology discovery
task. In each, our goal is to identify the maximum aposteriori parameter estimates of p(X, C|Y ) ∝p(Y |X, C) p(X, C).

3.1

611
CAUSAL SOUNDSCAPE
FACTORIZATION

The linear-Gaussian observation is appropriate in situations where latent prototypical observations combine
linearly to produce a composite observation, which istrue of sound data. This is illustrated graphically inthe top of Figure 3. For this experiment, we constructed a simple “jungle soundscape,” in which different jungle sounds caused other jungle sounds: jaguars
howling caused birds to twitter, elephants trumpeting
caused frogs to croak, crickets tended to stay on or
off for long periods of time, etc. 52 observations weregenerated, each of which was an 8K sound sample.
This problem is closely related to blind source separation tasks, except that we are additionally interested
in the latent causal structure.
Figure 3 shows the results. The bottom left shows theground truth for which events were active at whichtimes, and the bottom right shows the learned eventsand causal structure. In this case, the ILEM correctlydiscovers the latent dimensionality of the data, thecausal network, and an almost perfect set of latent
events.
We chose this problem to illustrate a simple example
where the HMM would fail to find the correct structure because it was unable to represent the factored
nature of the state space and learn from only a limited
amount of data. A factorial HMM with independent
binary-valued Markov chains would also be unable torepresent the structure of the data because different
events interact.
3.2

SPACE INVADERS

Next, we experimented on a stylized version of space
invaders. A single alien travels back and forth while asingle turret moves back and forth, shooting bullets at
the alien. If the bullet hits the alien, the alien explodes
and resets to an initial position. Figure 4 on the left
shows typical images from the data set.
This problem was chosen to illustrate the need for bothfactored state representations and flexible causal structure. In this case, we expect the HMM to fail becauseof the combinatorics of the latent space, and we expecta factorial HMM to fail because the different latent
factors interact with one another.
There are approximately 25 latent events in the data
set: there are six positions for the alien, three for theturret, nine different bullet positions, three different
explosion positions, and four action indicators (represented as bars on the bottom of the image). Observations are 15x15 binary images. The ILEM was trainedon 400 observations. A good initialization greatly

612

WINGATE ET AL.

UAI 2009

1

* 1
0
...

...

A x t = yt

Figure 3: On the top: setup for the causal soundscape factorization task. Sound events are linearly combined toform a composite observation. On the bottom left: the ground truth showing which events were active at whichtimes. Each row represents a single sound, such as a bird, elephant, tiger, etc. On the bottom right: the inferredlatent events and actual causes. Cricket (row 2) and frog (row 4) sounds evolve independently, lions roaring (row7) cause birds to screech (row 1), elephants trumpeting (row 6) cause monkeys to howl (row 9), etc.
accelerated learning, so we initialized with a nonnegative matrix factorization algorithm [11], which initialized both the X matrix and the A matrix with 30
different events. Of the 30 events, 13 of them did notcorrespond neatly to a single object – they lumped
multiple objects or parts of objects together. It wasthen up to the ILEM to clean this up, by determining
exactly how many objects there were, and infer thecausal structure relating them.
We evaluated the results in two ways. First, we examined the learned prototypical observations associatedwith the latent events. Several of these prototypicalobservations are shown in the upper-right of Fig. 4.
They correspond to objects in the world: an eventfor the explosion in each position (top row), different
events for the different positions of the bullets (middlerow), and different events for the alien (bottom row).
We also examined the inferred causal network. On thebottom of Fig. 4 are two chains of causal structure.
The top shows the alien looping from the upper-left
to the upper right and back again. The model successfully distinguishes the fact that the alien stays in
the upper-right corner for two successive timesteps (although it does not make the same prediction for theupper-left corner). Just below is shown the progressionof events as a bullet is fired from the middle position.
3.3

NETWORK TOPOLOGY DISCOVERYFor these experiments, the ILEM was tasked with discovering a causal network topology based loosely on
the SysAdmin problem [8]. In the SysAdmin problem,a sysadmin must keep a network of computers working.
Machines crash periodically; when they do, they causea cascade of failures, which is governed by a network

topology. Our version of the problem is to discover the
network topology, given only the crash data.
We chose this problem to clearly illustrate how we caninfer latent nodes in a DBN, while also inferring thecausal structure of the network. We again expect the
IFHMM and HMM to fail for reasons similar to those
discussed previously.
We represent the data as a binary matrix with T rows,
and K columns, where T is the number of timepoints,
and K is the number of machines, and Xt,k = 1 iff
machine k has failed at time t.
First variant: known machines. For this variant,the number of latent events is known – we have one foreach machine. We therefore fix that parameter of the
ILEM, and only attempt to infer the network topology.
(A nonparametric approach is still useful because we
do not know the number or strength of the edges.)
We tested the ILEM on four topologies: the threeshown in Figure 5, and a special fourth topology (explained below). For the three small topologies, we used
400 data points. The ILEM discovers almost perfect
topologies: for the four-node ring, the ILEM correctly
identifies 12/12 of the existing and missing links; forthe five-node star, it identifies 19/20 existing and missing links; for the seven-node tree, the ILEM identifies
40/42 existing and missing links. Note that the matrices of one-step co-occurrence statistics is often largely
uninformative, as shown in the bottom of Figure 5. Inorder to discover a reasonable causal network, we need
the ILEM’s bias towards a sparse connectivity.
For the fourth topology, we generated a randomly
connected network among 100 machines (with about
99.5% sparsity), and generated 1,000 data points.
The best network derived from the posterior ILEM

UAI 2009

WINGATE ET AL.

613

Figure 5: Setup and results for the SysAdmin problem. Top: network topologies tested. Bottom: cooccurrence statistics (left) and the ILEM’s learnt networks (right).
and the causal structure connecting them.
Figure 4: Results on space invaders. Top left: typicalobservations. Top right: several of the prototypicalobservations associated with each event: the top row
shows explosions, the middle row shows some bullet
events, and the bottom row shows the alien. Bottom figure: two chains of causal events inferred by themodel. The alien moves back and forth, and a bullet
moves upward after being fired from the ship.
correctly inferred 9,982/10,000 existing and missing
links; in contrast, the best network inferred from cooccurrence statistics missed twice that many.
Second variant: unknown machines. For thisvariant, we hid one of the machines in each small network (modeling a rogue machine that the system administrator is unaware of; shown as a shaded node in
Fig. 5), and attempted to infer a complete network.
Now, both the number of machines and the topology
are unknown. The results were encouraging: for all
three networks, the ILEM was able to correctly infer that a single rogue machine existed, and was able
to infer almost perfect network topologies; there weremore extraneous entries in the C tensor, representing
more uncertainty about the exact underlying network,
but the correct links almost always had the strongest
evidence for their existence.

4

CONCLUSIONS

We have presented the Infinite Latent Events Model,
a nonparametric Bayesian model capable of capturing factored causal structure in timeseries data withrich observations. The centerpiece of our model is anactual-cause approach which leaves the DBN structurelatent. Using a Gibbs sampler to perform inference ofa hierarchy of Dirichlet processes, we have shown thatthe model can infer an appropriate set of latent events

Efficient inference in the ILEM on large data sets remains an important open research problem; we believethat some combination of slice sampling and dynamic
programming—like that employed for the IFHMMs(see [4])—and/or particle filtering (e.g., Beal’s infinite
state particle filter [1]) are promising options. Froma modeling perspective, inhibitory (and more general)causal link models, hierarchical structure, and semiMarkov extensions appear to be straightforward ways
to extend the applicability of the ILEM to a wider
range of new data. For many timeseries data, especially those acquired by autonomous agents, we believethat natural models will require a notion of objects; aflexible prior with such an inductive bias is an important next step.

A

RELATION TO NOISY-OR DBNs

The active events Xt at time t are given by the union
over Poisson independent draws from πk for each active event k ∈ Xt−1 . Let Q denote the conditional
distribution of Xt given Xt−1 (treating the {πk } distributions as nonrandom). We show that Q is equivalent to the marginal distribution of a random, infinitedimensional noisy-OR DBN. For each event i ≥ 0, let
pi = (pi→1 , pi→2 , . . . ), where pi→j is the probability
that event i causes event j at the next timestep, giventhat event i is currently active.
Let Xt ⊆ N be the set of events active at time t. For
each event j ∈ N at time t, let the probability thatevent j is active (i.e. j ∈ Xt ) beY1−
(1 − pi→j ),i∈Xt−1 ∪{0}where we have assumed that a distinguished background event i = 0 is always active. The above alternative conditional distribution of Xt given Xt−1 isa noisy-OR DBN parameterized by {pi }i≥0 .

614

WINGATE ET AL.

Theorem A.1. There is a distribution on probabilities {pi }i≥0 such that the conditional distribution of
Xt given Xt−1 is Q.
Proof. We will show that a transformed beta process prior [9] on pi achieves the desired result. Let{qx }x∈R ∼ BP(c, λB0 ) be a draw from a beta processwith concentration parameter c = 1, mass parameter
λ = λbase and continuous base distribution B0 (x) on
R. Then qx ∈ [0, 1] for all x ∈ R with probability one.
The set of random probabilities {qx }x∈R have the following relevant properties [15]: Let F = {x ∈ R :qx > 0} be the set of x ∈ R assigned positive probability. Then F is a random, countably infinite subsetof R. Furthermore, the elements of F are themselves
i.i.d. draws from B0 and independent of the probability values qx . Finally, let G ⊂ R be the random set of
successes among independent Bernoulli(qx ) trials foreach x ∈ F . Then the mass parameter λ is the mean
number of successes |G|. In fact, the number of successes has a Poisson(λ) distribution.
Fix an event k ≥ 0 and let πk be the corresponding
measure on events and let B0 be the uniform distribution on [0, 1]. There exists a measurable mappingρk : R → N such that B0 ◦ ρ−1= πk . Becausekeach x ∈ G is i.i.d. B0 , (ρ(x))x∈G are Poisson(λ)many independent draws from πk . This describes Q
and, furthermore, this process is equivalent to sampling from the
Q noisy-OR network with probabilities
pk→j = 1 − x∈ρ−1 (j) (1 − qx ).

Acknowledgments

We thank the anonymous reviewers for their helpful comments. The authors also gratefully acknowledge the financial support of NTT Communication Sciences Lab, AFOSR (grant #FA9550-07-1-0075), ONR(grant #N00014-07-1-0937), NSF (GRFP for D. Roy),ARO (grant #W911NF-08-1-0242), and the James
S. McDonnell Foundation Causal Learning Collaborative.

References[1] M. J. Beal, Z. Ghahramani, and C. E. Rasmussen. The
infinite hidden Markov model. In Neural Information
Processing Systems (NIPS), 2002.
[2] T. Choudhury, J. Rehg, V. Pavlovic, and A. Pentland.
Boosting and structure learning in dynamic Bayesian
networks for audio-visual speaker detection. International Conference on Pattern Recognition, 3:789–794,
2002.
[3] N. Friedman, K. Murphy, and S. Russell. Learning
the structure of dynamic probabilistic networks. In
Uncertainty in Artificial Intelligence (UAI), 1998.

UAI 2009[4] J. V. Gael, Y. W. Teh, and Z. Ghahramani. The
infinite factorial hidden Markov model. In Neural Information Processing Systems (NIPS), 2008.
[5] Z. Ghahramani. Learning dynamic Bayesian networks. In Adaptive Processing of Sequences and Data
Structures, pages 168–197. Springer-Verlag, 1998.
[6] Z. Ghahramani and M. I. Jordan. Factorial hidden
Markov models. Machine Learning, 29:245–273, 1997.
[7] T. L. Griffiths and Z. Ghahramani. Infinite latent feature models and the Indian buffet process. In Neural
Information Processing Systems (NIPS), 2006.
[8] C. Guestrin, D. Koller, R. Parr, and S. Venkataraman.
Efficient solution algorithms for factored MDPs. Journal of Artificial Intelligence Research (JAIR), 19:399–
468, 2003.
[9] N. L. Hjort. Nonparametric Bayes estimators basedon beta processes in models for life history data. The
Annals of Statistics, 18(3):1259–1294, 1990.
[10] H. Lahdesmaki and I. Shmulevich. Learning the structure of dynamic Bayesian networks from time series
and steady state measurements. Machine Learning,
71(2-3):185–217, 2008.
[11] D. D. Lee and H. S. Seung. Learning the parts ofobjects by non-negative matrix factorization. Nature,
401:788–791, 1999.
[12] J. Pitman. Poisson-dirichlet and gem invariant distributions for split-and-merge transformations of an interval partition. Combinatorics, Probability and Computing, 11:501514, 2002.
[13] L. R. Rabiner and B. H. Juang. An introduction tohidden Markov models. IEEE Acoustic Speech Signal
Processing Magazine, 3:4–16, 1986.
[14] Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei.
Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101:1566–1581, 2006.
[15] R. Thibaux and M. I. Jordan. Hierarchical beta processess and the indian buffet process. In Proceedingsof the Eleventh International Conference on Artificial
Intelligence and Statistics, 2007.
[16] F. Wood, T. L. Griffiths, and Z. Ghahramani. A
non-parametric Bayesian method for inferring hiddencauses. In Uncertainty in Artificial Intelligence (UAI),
pages 536–543, 2006.