Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks
Authors: Robert Lieck
Martin Alois Rohrmeier
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian networks
graphical models
probabilistic context-free grammars
structure learning
parsing
mixed discrete-continuous
sequence models
tree induction

Abstract: Probabilistic context-free grammars (PCFGs) and dynamic Bayesian networks (DBNs) are widely used sequence models with complementary strengths and limitations. While PCFGs allow for nested hierarchical dependencies (tree structures), their latent variables (non-terminal symbols) have to be discrete. In contrast, DBNs allow for continuous latent variables, but the dependencies are strictly sequential (chain structure). Therefore, neither can be applied if the latent variables are assumed to be continuous and also to have a nested hierarchical dependency structure. In this paper, we present Recursive Bayesian Networks (RBNs), which generalise and unify PCFGs and DBNs, combining their strengths and containing both as special cases. RBNs define a joint distribution over tree-structured Bayesian networks with discrete or continuous latent variables. The main challenge lies in performing joint inference over the exponential number of possible structures and the continuous variables. We provide two solutions: 1) For arbitrary RBNs, we generalise inside and outside probabilities from PCFGs to the mixed discrete-continuous case, which allows for maximum posterior estimates of the continuous latent variables via gradient descent, while marginalising over network structures. 2) For Gaussian RBNs, we additionally derive an analytic approximation of the marginal data likelihood (evidence) and marginal posterior distribution, allowing for robust parameter optimisation and Bayesian inference. The capacity and diverse applications of RBNs are illustrated on two examples: In a quantitative evaluation on synthetic data, we demonstrate and discuss the advantage of RBNs for segmentation and tree induction from noisy sequences, compared to change point detection and hierarchical clustering. In an application to musical data, we approach the unsolved problem of hierarchical music analysis from the raw note level and compare our results to expert annotations.

Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks
Robert Lieck
Martin Rohrmeier
Digital and Cognitive Musicology Lab
Digital and Cognitive Musicology Lab École Polytechnique Fédérale de Lausanne 1015 Lausanne, Switzerland martin. rwhrmeier@epll..ccmm ch
École Polytechnique Fédérale de Lausanne 1015 Lausanne, Switzerland researchhrobert-L1e com
Abstract
Probabilistic context-free grammars (PCFGs) and dynamic Bayesian networks (DBNs) are widely used sequence models with complementary strengths and limi- tations. While PCFGs allow for nested hierarchical dependencies (tree structures), their latent variables (non-terminal symbols) have to be discrete. In contrast, DBNs allow for continuous latent variables, but the dependencies are strictly sequential (chain structure). Therefore, neither can be applied if the latent variables are sumed to continuous and also to have a nested hierarchical dependency structure. In this paper, present Recursive Bayesian Networks (RBNs), which generalise and unify PCFGs and DBNs, combining their strengths and containing both as spe- cial cases. RBNs define joint distribution over tree-structured Bayesian networks with discrete or continuous latent variables. The main challenge lies performing the exponential number of possible structures and the contin- uous variables. We provide two solutions: 1) For arbitrary RBNs, we generalise inside and outside probabilities from PCFGs to the mixed discrete-continuous case, which allows for maximum posterior estimates of the continuous latent variables via gradient descent, while marginalising over network structures. 2) For Gaussian RBNs, we additionally derive an analytic approximation of the marginal data likeli- hood (evidence) and marginal posterior distribution, allowing for robust parameter optimisation and Bayesian inference. The capacity and diverse applications of RBNs are illustrated on two examples: data, we demonstrate and discuss the advantage of RBNs for segmentation and tree induction from noisy sequences, compared to change point detection and hierarchical clustering. In an application to musical data, we approach the unsolved problem of hierarchical music analysis from the raw note level and compare our results expert annotations.
joint inference
quantitative evaluation on synthetic
Introduction
Long-term dependencies with a nested hierarchical structure are one of the major challenges in modelling sequential data. This type of dependencies is common in many domains, such as natural
"corresponding author, code at attptpp://ggthhb..cc/rreeeeeeeee
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Structure
Lincar/Chain
Hierarchical/Tre
Discrete
Variables Discretef Only Continuous
Regular Grammars/
Probabilistic Context- Free Grammars
Hidden Markov Models
Dynamic Bayesian Networks
Recursive Bayesian Networks
Figure I: RBNs generalise PCFGs by allowing for continuous latent variables and DBNs by incorpo- rating nested hierarchical dependencies.
Two the most widely used probabilistic models for sequential data are probabilistic context-free grammars (PCFGs) and dynamic Bayesian networks (DBNs), both having complementary strengths.
language [. music 2 3 or decision making 4 5].
PCFGs well-established and widely used for modelling hierarchical long-term dependencies in 7
symbolic data [ 6
9 3 [0]. They generalise local (Markov) transition models by allowing for infinitely many levels of nested hierarchical dependencies and flexible number of latent variables. However, parsing methods such as the Cocke- Younger-Kast Kasami (CYK) algorithm rely the discrete nature of the rules and variables.
In contrast, DBNs are sequential models with a fixed set of random variables that reoccur at each time step [5 [6). The variables at each time step may be discrete continuous, latent observed, and may have an arbitrary non-cyclic dependency structure among each other, with additional links from the previous and to the next time slice. They comprise important model classes as special cases, such as hidden Markov models (HMMs) if there is only a single discrete latent variable or linear dynamical systems if all dependencies are linear Gaussians [17 18 [6]. However, DBNs only allow for a fixed chain of Markov dependencies between time slices and cannot represent nested hierarchical structures.
In this paper, we present Recursive Bayesian Networks (RBNs), a novel class of probabilistic models that combines the strengths of PCFGs and DBNs by allowing for nested hierarchical dependencies in combination with arbitrary discrete or continuous random variables (Figure I Our main contributions are follows:
1. With RBNs, we provide unified theoretical framework for large class of important sequence models, including PCFGs and DBNs.
2. We generalise inside and outside probabilities from PCFGs to continuous latent variables, allowing for maximum posterior (MAP) inference arbitrary RBNs.
3. For Gaussian RBNs, we derive an analytic approximation for the marginal likelihood and marginal posterior distribution, allowing for robust parameter optimisation and Bayesian inference.
4. We provide a quantitative evaluation on synthetic data and an application to the challenging task of hierarchical music analysis.
1.1 Related Work
PCFGs have long tradition for modelling nested hierarchical dependencies in symbolic data with variety of parsing algorithms for inferring the structure and variables' values [13]
6 14. Beyond
their application to sequential data, PCFGs have been generalised to graph structures 19 20
21 22
which readily transfers applications of RBNs. Latent vector grammars (LVeGs)
23 are an
extension of latent variable grammars (LVGs) 25 with continuous latent states. As for RBNs, approximate parsing is possible in the Gaussian case. However, both LVGs and LVeGs are special cases of RBNs and do not draw the connection graphical models. More recently, the availability of automatic differentiation libraries, such as PyTorch (26), has lead a number of applications where
gradients are propagated through the entire parsing process (27 28 29 30).

---

FFL:
x
y
30:3
#1:33
12-4
23:55
FF:TT
Figure 2: RBN Chomsky normal form. The non-terminal transition pN(2', x² x) and terminal transi-
#1:2
12:3
33:4
I:4:5
FEB:T
tion Pr 1z) are grouped into an RBN cell with structural distribu-
tion [2 x)) We use gates [58]
y1
y2
Us
3/4
Y/
y/
1/T
describe structural distributions and extended factor graph notation [black squares: [5] for conditional joint distributions. Considering all possible ways how n observations can be generated by recursively ap- plying the RBN cell produces an RBN chart, shown in Figure
Figure 3: Chart of an RBN in CNF for sequential data of length
n = 7. The network obtained by fixing one specific dependency structure is highlighted in blue; latent non-terminal variables that are not part of this particular structure are shown grey. Orange and red boxes, respectively, indicate the subsets Xo.3 and 0.33 latent non-terminal and observed terminal variables generated from T0:3-
The process of parsing PCFG or RBN can be formally rewritten sum-product network [SPN; 31 32 33
Factor graph grammars [FGGs; M generalise PCFGs, case-factor diagrams [35] and SPNs by using hyperedge replacement graph grammar
[19] to describe distribution over graph structures that is more general than that of RBNs (not only trees). However, none of the approaches addresses the problem of inference with continuous variables that are facing in RBNs
(exponentially many terms with exponentially many nested integrals).
A wide range of probabilistic and neural models operate with fixed graphical structure and are loosely related to RBNs. Hidden tree Markov models [36] generalise HMMs from chain to fixed tree structures. They model data at each node as observations of latent Markov process the underlying tree, which is part the input data. Additionally estimating the underlying tree structure has been addressed in [38 39 40). Recursive neural tensor networks [41] use PCFG for parsing a given sequence of symbols to obtain a tree structure, which then fixed and used as the backbone for neural network. More generally, there is number of methods for inferring
fixed structure for graphical models 422 16 43 44,, SPNs [45] 46, 47 48 32] 44), or graph neural
networks [50] 5 [2] All these methods have in common that fixed structure is either given or estimated but not treated in a probabilistic Bayesian manner.
Some approaches attempt Bayesian treatment of the unknown structure of graphical model or SPN via dynamic programming [53] (54 or Markov chain Monte-Carlo sampling (55] 56. [7). However,
the structure is assumed to be independent of the latent variables (they only become dependent conditional on the data) and the latent variables cannot be used to control the structure, as the case in RBNs. The challenge of continuous variables also remains unsolved.
2 Recursive Bayesian Networks
RBNs are template-based based graphical models that define a joint distribution over network structures and variables' values. The number of template variables is fixed, but the number of instantiated variables, their connectivity and values are governed by the joint distribution. thought of as DBNs that can not only be connected linearly to form a chain but also hierarchically to form tree structure. Alternatively, they can thought of PCFG in which each symbol is (possibly continuous) random variable.
a rough analogy, RBNs can be
3

---

2.1
Definition
RBNs have three types of template variables: latent non-terminal variables (discrete or continuous),
2) observed terminal variables (discrete or continuous), and 3) latent structural variables (always
discrete). the simplest case, illustrated in Figure 2 an RBN has one template variable of each type.
Formally, an RBN is defined follows:
Definition (Recursive Bayesian Network). An RBN a tuple (2.), with
X: set of latent non-terminal template variables
y: a set of observed terminal template variables
(2)
Z: set of latent structural template variables, paired up with the non-terminal variables
(3)
T: a set of transition distributions p(U1,...,, [1yla x)) from single non-terminal variable a E X
set of non-terminal and/or terminal variables uy,....uu XXUY
(4)
S: a set of structural distributions p(z x)), one for each non-termmina/ssrruttuaal pair
(5)
pr: a prior/start distribution for exactly one non-terminal variable.
(6)
The cardinality of a structural variable 2 E Z corresponds to the number of possible transitions from the associated non-terminal variable X) in is called the arity of the transition.
Generating with an RBN is straightforward. We start by sampling the value of the first non-terminal variable from the prior distribution (2))) and then repeat the following steps until no unprocessed non-terminal variables are left:
1. sample the value of the associated structural variable from p(= |x)
2. choose transition distribution p(u By a)) based on the structural variable's value
3. sample the variables U1,.... on from the transition distribution
4. for all newly generated non non-terminal variables, go to step
The major challenge and focus of this paper is to perform joint inference over the latent structure and non-terminal variables' values conditional on a given set of observations.
Chomsky Normal Form: In the simplest non-trivial case, an RBN has one latent non-terminal, one
observed terminal, and one latent structural template variable, with one non-terminal transition of arity 7 = 2 and one terminal transition of arity 1, as illustrated in Figures 2 and 3 It is defined by four distributions
(r())= prior/start distribution
(7)
PN (2', x" (x)) non-terminal transition
(8)
py () terminal transition
(9)
ps ()) termination probability.
(10)
In analogy to PCFGs, we call this the Chomsky normal form (CNF). Any RBN may be rewritten in CNF (see Appendix A.I for details).
RBN Chart: During inference, we will make use of an RBN chart, similar to the parse chart for layer the chart. For discrete variables. they store the actual distributions, while for continuous variables they either hold the point estimate (for MAP inference) or the parameters of the approximate distributions (for inference in Gaussian RBN). Different instances of the same template variable are identified by subscript indicating the span of data generated from them, which also corresponds to their position in the chart (see Figure 3). Sets of variables that are generated from specific latent non-terminal variable Tis are denoted by bold capital letter with a corresponding subscript (X Yok. Zisk:: omitting the subscript refers to all variables (X, Y, Z); for X and Z this also includes the root variables 20.n. and 20:n. respectively.
PCFGs 6
Each non-terminal variable is associated
The subscripts are to be interpreted as time intervals, that is, Y.,: is empty, Yo.1 = y1 is the first observation, Y, n- (yn-1, Vn.) are the last two observations etc.
Any PCFG can be rewritten an RBN two different ways, which we call abstraction and expansion (see Appendix A.2 for details). Abstraction of PCFG produces discrete RBN with one latent non-terminal and one observed terminal variable. The resulting RBN is exactly equivalent to the original PCFG but describes the same relations in more abstract and compact way. In contrast, expansion of PCFG considers the symbols of the grammar as random variables in their own right, thereby endowing them with additional (possibly continuous) degrees
Comparison PCFGs:

---

of freedom. The resulting RBN is therefore more powerful than the original PCFG. A PCFG is abstracted a discrete RBN by defining the start/prior, transition, and structural distributions
10
as
WS
W WA-BC
Pp (x==A) Σ WS-AA
(11) pN =B,'=BBx'' =C x-
(12)
Σ EB,0 W WA-B''C
Σ n.o WA-BC
if
WA
x WA-X
([y==b[=AA) = Σ,, WA-M
(13) ps(z A=
=
(14)
WA-s
Wa-x if ==
X
where is the grammar's 's start symbol, A, B, C' are non-terminal symbols, b is a terminal symbol, X is any right-hand side of a rule, = and z=TT indicate non-terminal and terminal transition, respectively, - is the weight PCFG are taken to have zero weight. In expansion, the PCFG is only used to define a "skeleton" for the RBN, while the specific random variables and the concrete transition distributions need to be additionally specified. This means that the resulting RBN model is more powerful than the original PCFG, as the symbols may, for instance, be expanded to continuous random variables.
the corresponding rule, and rules that do not exist in the original
2.2 Inference
The two main goals of inference in RBNs are to 1) train model parameters by maximising the marginal data likelihood and to 2) compute posterior distributions or maximum posterior (MAP) estimates of the network structure and non-terminal variables. In PCFGs, both is achieved by computing inside and outside probabilities [14] which will be the starting point for our generalisation to continuous variables.
Inside and Outside Probabilities: We define inside and outside probabilities, and a, for RBNs in analogy to how they are defined for PCFGs, the only difference being that the variables may be continuous. We thus have
3(xak) := p & (xak)
(15) and
a (IIAA == p(Y o:i. Tack Y kmn)
(16)
where n is the length of the sequence and Y is fixed (and therefore omitted as argument on the left-hand side). That is, 3(xaa)) the marginal likelihood of generating the sub-sequence Y conditional on the respective non-terminal variable Tick. while (xT::s) is the marginal likelihood of generating the two sub-sequences You and Y as well as the non-terminal variable Teck- In both cases, 3 and are functions of the corresponding non-terminal variable with the structure and the remaining variables being marginalised out. Based on the inside and outside probabilities, the marginal data likelihood and the marginal posterior distributions over non-terminal variables are
- (((zto)) pp(xo.n) dæo...
a: ((Zak)) ((Tak)
p(Y (
(17) and P(Eak Y)
(18)
PYY
respectively. P(ZEa Y) is an unnormalised probability distribution that specifies the probability of Teek to exist via the normalisation constant f p( Y) da while the normalised version corresponds to the marginal posterior distribution of 24:k for the case that it does exist.
Inside probabilities are recursively computed bottom-up. For an RBN CNF we start with the base case (19) for single observations and then iterate (20) to the top of the RBN chart
3(xaa11) = ps (= Faan) pr(y (as-1) 1
(19)
El PN (Tag. Tyakk (mak) ((raz) (17zkk dreg dr.:..
((Tak) ps
ps (= -N (ackk)
(20)
Outside probabilities are recursively computed top-down, while making use of the inside probabilities a(Fo:))= pe (zo.))
(21)
1-1
a(Tzak)= =
ps (2 Daak) pN (Trgg Tysk (aak) (((asss)) ( dre. drask) +
ps( [s(2)u=N mzaa pN (Z Deal (ya) (anga)) ((xraa) dæza drcd
(22)
1=
5

---

As for PCFGs, the two terms in (22) correspond to the possibility of 2 being generated as the right or the left child, respectively. The main conceptual difference PCFGs is that we treat the discrete structural part (marginalised out by the sums) separately from the potentially continuous variables (marginalised out by the integrals). For RBNs that are not in CNF, the equations have be adapted accordingly (see Appendix A.3 for the general case).
Computing the marginal data likelihood (17) and the marginal posterior distri- butions over non-terminal variables (18) requires to solve an exponential (w.r.t, the length n of the sequence) number of nested integrals special case of Gaussian RBNs, we provide an adaptive closed-fome approximation in Section 2.3 Moreover, marginalising only over the network structure for fixed assignment of the non-terminal variables X is straight forward and allows for maximum posterior (MAP) inference in general RBNs.
Marginalisation:
(19 22 which generally intractable. However, for the
Maximum Posterior Inference: For fixed assignment of all non-terminal variables X, we can compute the joint marginal likelihood p(X, Y) over observed terminal and latent non-terminal variables by only marginalising over the structure. This follows the same principle as above but uses the modified joint inside and outside probabilities
Bes : p(.: ss xx:k))
(23) and a= := := (x:j Yo.j 2j:k, X Y Ymm)
(24)
where all variables are fixed (and therefore omitted as arguments on the left-hand side). Analogously, the joint marginal likelihood and the marginal posterior probability of risk to exist then are
Gak BER p(X. Y)
p(X Y) Bora pr (1
(5)
and
Pi:k
(26)
where Pisk is the probability of Tus to exist for this specific assignment of X. The corresponding equations for the recursion differ from 19 22 only in that they do not integrate out the latent non- terminal variables (see Appendix A.3.3). As before, all computations can be efficiently performed via dynamic programming. Gradients w.r.t. the variables and/or parameters are readily obtained from libraries such as PyTorch (26). Optimising the values of the latent non-terminal variables X via gradient descent yields maximum posterior (MAP) estimates, while the structure marginalised out. MAP estimates for the structure (i.e. the best tree) conditional on an assignment for X can be computed (as for PCFGs) by replacing summation with maximisation
There are two caveats: First, due to marginalising over multiple (exponentially many) network struc- tures, p(X, X, Y) may be highly non-convex and optimising via gradient descent not guaranteed to find the global optimum. This is even the case for purely Gaussian RBNs, for which p(X, Y) is mixture of Gaussians (one for each structure). Second, we can optimise X while marginalising out the structure and we can optimise the structure for a fixed assignment of X. However, successively optimising X and the structure is not equivalent to jointly optimising both and the maximum of p(X, Y) may be unrelated to the maximum of the best structure (also see Figure/4). This means that generally, exact joint MAP inference over the latent variables and the structure hard. For Gaussian RBNs, we provide an approximate solution below.
2.3 Gaussian RBNs
In Gaussian RBN (GRBN), the prior, non-terminal, and terminal distributions are linear Gaussians and the termination probability (structural distribution) is constant
(x) (a;;; pr, Ep)
[prior]
(27)
(x(a', x x) = N(x'; 2 E ((";;,,, ΣNR)
[non-terminal]
(28)
Pr x)) NN x, Er)
[terminal]
(29)
[====T] x)) Peem
[terminationn/ttuctuuaa]
(30)
For clarity, we will show all derivations for GRBNs in this basic form. For evaluations and the application to music, we use a slightly extended version that includes linear transformations, mixtures of Gaussians, and multi-terminal transitions (Section 2.3.I). The derivations do not fundamentally change for the extended case (see Appendix A.4). In Appendix B, we show all calculations on a simple example.
Adaptive Approximation: If the structure of a GRBN was fixed, all variables would be jointly Gaussian distributed as in conventional Gaussian Bayesian network [16]. However, due to the

---

misture max Appros metion
2
Co components
W
T
y
π2
x
x"
Figure 4: Three Gaussians components, the resulting mixture (green), maximum (orange), and nooentt-mtching single Gaussian approx- imation (blue). Note that the maximum of the mixture (X), the best component (X), and the approximation (X) may be unrelated.
Figure 5: Graphical model of the Gaussian RBN for modelling music. The additional transposition vari- able r marginalised out during inference; the num- ber of jointly generated observations n is uniquely determined by the location the parse chart.
unknown structure, we effectively have a mixture of exponentially many Gaussians, one for each possible structure. While in principle all integrals can be solved analytically, the exponential growth makes exact inference intractable. Therefore, our goal is to derive a parsing strategy that retains tractability by adaptively applying local approximations to the Gaussian mixtures occurring in each recursion step. We will here focus on the simplest case approximating the mixtures with a single Gaussian (illustrated in Figure 4 details in Appendix A.4.2), which can be efficiently computed in The inside and outside probabilities are thus represented by simple Gaussian
closed form [88 61].
3(Izs:) Cick (Z Pis
(9)
(9) (1)
(31)
(a) a(Ij:)) O2 (I P 20())
(a)
(32)
and this form is reestablished in each iteration by approximating the occurring mixtures. Consequently,
the marginal posterior distributions over latent variables (18) are also simple Gaussians and the marginal data likelihood (17) can be computed in closed form. This approximation scheme can be extended and refined by using existing methods for approximating each Gaussian mixture by one
with fewer components 62 63
Marginalisation: In 20 and 222. have integrate over products of Gaussian distributions
marginalise out the latent variables. To solve these integrals, we make use of the fact that the product of two Gaussians over variable æ can be rewritten [see e.g. 64]
(1 pn, Nx) En) N U2, En + Nx;
(33)
with
and
a A= D MI + H2)
(34)
Hence, when integrating over x, only the first term on the rhs (33) remains. detailed step-by-step derivation of all results can be found in Appendix 1. With the latent variables being marginalised out, (20) and (22) become simple mixtures of Gaussians that can be easily approximated to retain the
simple analytic form of the inside and outside probabilities.
As described above, exact joint MAP inference over the continuous latent variables and the structure is generally intractable. Moreover, the maximum of the approximate posterior does not necessarily coincide with the maximum of the exact posterior or that of a particular structure (see Figure 4) Thus, first optimising X (based on the approximation) and then estimating the structure (conditional on the picked value of X) may lead to arbitrarily bad results for tree induction. Therefore, we leverage the adaptive character of our approximation scheme to compute local structure estimates each step, before loosing relevant information due to further approximations. Specifically, during the bottom-up up pass for computing inside probabilities, all structures are scored by the maximum of their marginal likelihood, based on its current approximation (3I). The best overall structure is then selected (as usual) in top-down pass (see Appendix A.4.3 and our example in Appendix B).
Tree Induction:
2.3.1 Gaussian RBNs for Music
For the application to music, we slightly extend the basic GRBN discussed so far by introducing transpositions and multi-termine terminal transitions (changes in the equations highlighted in blue). The
7

---

corresponding graphical model of the RBN cell is shown in Figure Furthermore, we describe how GRBNs can be applied to categorical data.
Transpositions: A transposition rotates the dimensions of the latent variable by a number of steps before generating the child. This is achieved by multiplying with an orthonormal transposition matrix T, that corresponds to the identity matrix with cyclicly rearranged columns. For the prior distribution, we assume uniform weighting of all possible transpositions
pp(x)==
Nz; T. Mp. 2p)
[prior]
(35)
where D is the dimensionality of the data (D = 12 for music in 12-tone equal temperament). For the non-terminal transitions, the probability for a specific transposition is determined by the weight parameter W
D-1 pN x" 12) = Σ p(r W) (NL,
(36)
Note that transpositions are only applied to the left child, because Western classical music is thought to be fundamentally goal directed [2 8 65). This means that the character of section largely determined by how it ends (the right child), which should also be reflected in the value of the parent node. In contrast, the role of the left child to harmonically prepare the ending (or prepare a preparation to the ending etc). We therefore allow for arbitrary transpositions in the left child and we will see below that our model indeed captures the most important type of preparation in Western classical music: the cadential dominant-tonic progression.
Multi- Termina Transitions: A multi-terminal transition generates multiple observed variables from a single latent variable. The variables are generated i.i.d. and their number is governed by a Poisson distribution with rate parameter A
Pr (yick meck) = Pois(k i 1 1 I Pekk ET)
tnulti-terminna]
(37)
j=i+1
Multi-terminal transitions do not conform to the CNF assumed so far and we need to add the term
((xak) + ps (2 24ak) pr (Mock (x.k)
(38)
...... + Ptemm pr (yick (1a.k)
[for GRBNs, see (30)
(39)
to 20 in order to account for the possibility to terminate from a higher-level variable. For t: i 1,
this term becomes the base case (19) of an RBN in CNF.
Multi-terminal transitions account for the situation where changes in the hierarchical structure occur at a lower rate than the time series is sampled. In between the structural changes, the data is assumed be generated from the same model, which could also be more elaborate than i.i.d. samples, long as the relevant model parameters are captured by the RBN's 's latent variables.
The observed variables of GRBN unconstrained real-valued, which poses problem if the data are categorical. This situation is comparable to using Gaussian processes (GPs) [66] for classification and can be approached with similar methods. In application to musical data, we observe one or more notes being played at any particular time and normalise these counts to obtain observations that correspond to the parameter of a categorical distribution. The natural likelihood function for this type of observations is a Dirichlet distribution. Therefore, we adapt the approach suggested in (67 for GPs, who assume Dirichlet likelihood, which is then approximated by a Gaussian likelihood in log-space. Since an observation from a Dirichlet distribution corresponds to a normalised sample from independent Gamma distributions, each Gamma distribution can be separately approximated by log-normal distribution, which results in a diagonal covariance matrix for the Gaussian likelihood in log-space. Matching the first and second moment yields (67
Categorical Data:
(1) = log v/ - _/10/2 /2
and
50) 1og(1/v/) +1).
(40)
where 0 ()) < 1 is the (th element (normalised count) of the 7th observation, V) is the corre-
x())
sponding mean of the approximate Gaussian likelihood in log-space, and 2n is the 1th element on the diagonal of the covariance matrix for the 7th observation. We thus have to replace Øj and 550) for y/ and Er in (37
55))
8

---

0.65
netled
methis
0.20
0.30
0.60
0.55
0.05
0.53
0.00
D2
A4
0:55
8:0
0.20
0.25
node
0.2
metee
10a
expert atrerston
0.7
HOOP
10
RBN ad5maae
0.4
10
13.43
(c)
40 50 400 120
140
00000
Figure 6: (a): Precision and recall w.r.t. the ground-truth trees of 500 sequences for different noise levels for the baseline (blue) and the maximum and marginal RBN estimates (orange, green): error bars indicate 95% confidence intervals from bootstrapping (see Appendix C.1 for technical details). (b): Prior mean learned by our GRBN for music comparison recent values from the literature 688. (c): Comparison of our model (orange/grey) to an expert annotation (bluc) for Johann Sebastian Bach's Prelude No. in major, BWV 846. The greyscale indicates the marginal probability of a node to exist at that particular location; the small numbers indicate the transposition in semitones for a left child; time indicated in beats (quarter notes); the piece was divided into two-beat (half note) intervals. The plot follows the idea of scape plots (69 70
Experiments
We performed a quantitative evaluation on synthetic data and applied our model to hierarchical music analysis of Bach preludes. We show that RBNs are superior change point detection (CPD) and hierarchical clustering (HC) for tree induction and our method is able to infer fundamental harmonic principles of Western classical music. Experiments were run on a 3.6 GHz Quad-Core Intel Core i7 processor with 32GB RAM. The model parameters were trained via gradient descent on the (approximate) marginal neg-log likelihood.
3.1 Quantitative Evaluation on Tree Induction
We performed a quantitative evaluation on synthetic data for the task of segmenting a noisy time series and inferring the underlying tree. For comparison, used the best-performing change point detection (CPD) method from the ruptures library [72) for segmenting the time series, combined with bottom-up hierarchical clustering (HC) for inferring the tree structure ("HC/CPD"). For details of the methodology, see Appendix C.I.
The evaluation results in Figure a()) show that the RBN tree estimates (Section 2.3 outperform the one from HC/CPD, in terms of both precision and recall (and thus also Fl measure). The marginal node probabilities show interesting performance pattern. They excel in terms of precision, which means that a node with high marginal probability is very likely to actually exist in the tree (low false-positive rate). However, they severely underestimate the overall node probabilities, which leads to recall falling far below the baseline. This means that a node with low marginal probability may in fact occur in the tree (high false-negatio rate).
consistently
We think that the poor recall measure of the marginal probabilities primarily due to (and the downside of) fully Bayesian treatment that quantifies uncertainty. Even if the marginal probabilities have a maximum the correct node location, probability mass will still spread around it and be allocated to number of less probable locations. While this is the desired behaviour of Bayesian

---

method, it inevitably results in a lower recall value. The high precision value confirms that uncertainty adequately quantified and not underestimated. That being said, the marginal probabilities provide an exceptionally rich basis for qualitative analyses. For instance, all ground-truth nodes are located at local maxima of the marginal probabilities and we can read off a number of other potential node locations, which essentially trace out the grid defined by the piece-wise constant segments (see Figure in Appendix C.I).
3.2 Hierarchical Music Analysis
Harmonies in Western classical music exhibit nested hierarchical structure that can be modeled by
PCFGs operating on abstract chord symbols [8 73 I0 3). While these grammars can be applied to expert annotations of musical score, hierarchical music analysis from the raw note level is an unsolved problem. We trained a GRBN (Section 2.3.1 on the 24 major preludes of Johann Sehastian
Bach's "Wohltemperiertes Klavier & II" (see Appendix C.2 for technical details and complete results).
Our first major finding is that the prior mean, shown in Figure bb), corresponds to major pitch profile (as could be expected from the training data) and in excellent agreement with recent Bayesian estimates from the literature [68]. The fact that the major profile appears in the prior (i.e. as the continuous equivalent of a grammar's 's start symbol) shows that our model picks up fundamentally important structures from the musical data. Our second finding is that only two transpositions have non-zero weights: the identity with weight of 78% and the fifth scale degree (7 semitones) with weight of 22%. This corresponds to the left child being generated as the dominant of the parent and realises the most important harmonic preparation dominant-tonic relation. A closer inspection of the expert analysis (Figure 10 in Appendix C.2) reveals that when considering the possible surface patterns (raw notes) of the labeled chords, most non-identity transitions can indeed be explained as (noisy) fifth transpositions. The strong weight of fifth transpositions in our model is a highly non-trivial empirical confirmation of the established music theoretical insight that Baroque music is fundamentally driven by dominant-tonic relations. While the estimated tree in Figure ([c) fails to reproduce the large-scale structure of the expert analysis (e.g. the separation into two main parts), it accurately captures the mcasure-wise harmonic changes on the bottom level.
Western classical music: the cadential
On the one hand, we see considerable room for improvement by integrating more advanced concepts. such as different modes (major/minor), diatonic in addition to chromatic transposition, or balancing of trees. On the other hand, our model was able to capture fundamental properties of Western classical music based on only 24 pieces. We therefore think that Gaussian RBNs are a highly promising approach for hierarchical music analysis from the raw note level, which should be further investigated.
4 Conclusion
We introduced Recursive Bayesian Networks (RBNs), a novel class of probabilistic models that unifies the strengths of probabilistic context-free grammars (PCFGs) and dynamic Bayesian networks (DBNs), generalising both model classes. We defined RBNs as a joint distribution over tree-structured Bayesian networks and their (discrete continuous) variables and described how to perform inference over both the model structure and the variables by leveraging parsing methods for PCFGs. The provided formalisation connects with the methods for formal grammar as well as with the versatile notation for graphical models. On two data sets, we demonstrated the potential of RBNs for modelling nested hierarchical dependencies in real-valued time series and musical data. The class of RBNs represents substantial contribution to the machine learning toolkit by unifying two of the most important approaches for modelling sequential data and bears a large potential for further development and applications.
Acknowledgments and Disclosure of Funding
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme under grant agreement No 760081 - PMSB. This project was conducted at the Latour Chair in Digital and Cognitive Musicology, generously funded by Mr. Claude Latour.
10

---

References
[1] Dan Jurafsky. Speech & Language Processing. Pearson Education India, 2000.
[2] Fred Lerdahl and Ray Jackendoff. A Generative Theory of Tonal Music. MIT press. 1983.
[3] Martin Rohrmeier, The Syntax of Jazz Harmony: Diatonic Tonality, Phrase Structure, and Form. Music Theory and Analysis (MTA), (1)):1633, April 2020, doi: 10.1 10.11116/MTA...I1
[4] Andrew G. Barto and Sridhar Mahadevan, Recent Advances Hierarchical Reinforcement Learning. Discrete Event Dynamic Systems, 13(4):341-379 2003. ISSN 0924-6703.
[5] Malik Ghallab, Dana Nau, and Paolo Traverso. Automated Planning and Acting. Cambridge University Press, 2016.
[6] Dick Grune and Ceriel JH Jacobs. Parsing techniques. Monographs in Computer Science. Springer, page 13, 2007.
[7] Christopher W. Geib and Robert P. Goldman. A probabilistic plan recognition algorithm based on plan tree grammars. Artificial Intelliennee 173(11):101-113 July 2009. ISSN 00043702. doi: 10. 10.10166j.artmm.22009
[8] Martin Rohrmeier: Towards generative syntax of tonal harmony, Journal of Mathematics and Music, 5 (1)33553,, March 2011, ISSN 1745-9737, 1745-9745. doi: 10. (1080/17459737.00 11111.55 1.573676.
[9] Florent Jacquemard, Pierre Donat- Sonat-Bouillud, and Jean Bresson. A structural theory of thythm notation based on tree representations and term rewriting. In International Conference on Mathematics and Computation in Music, pages 3-1 Springer, 2015.
[10] Daniel Harasim, Martin Rohrmeier, and Timothy J. O'Donnlll. A Generalized Parsing Framework for Generative Models of Harmonic Syntax. In Proceedings of the 19th International Society for Music Information Retrieval Conference, pages 152-1199, Paris, 2018. doi: (0.5281/zemodo.149) 1492367.
[11] Tadao Kasami, An efficient recognition and vyntax-analyee algorithm for context free languages. Coordi- nated Science Laboratory Report no. R-257, 1966.
[12] Daniel H Younger. Recognition and parsing of context-free languages in time n3. Information and control, 10(2):199-208, 1967.
[13] Joshua Goodman. Semiring parsing. Computational Linguistics, 25(4):573-605, 1999.
[14] Christopher Manning and Hinrich Schutze. Foundations of Statistical Natural Language Processing, MIT press, 1999.
[15] Kevin Patrick Murphy. Dynamic Bayesian Networks: Representation, Inference and Learning. PhD thesis, University of California, Berkeley, 2002.
[16] Daphne Koller and Nir Friedman. Probabilistic Gruphicul Models: Principles and Techniques. MIT press, 2009.
[17] Greg Welch and Gary Bishop, An introduction to the Kalman filter. Technical report, University of North Carolina, 1995.
[18] Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer, 1st ed. 2006. corr. 2nd printing edition, 2007.
[19] Frank Drewes, H.-J Kreowski, and Annegret Habel. Hyperedge replacement graph grammars. In Handbook Of Graph Grammars And Computing By Graph Transformation: Volume 1: Foundations, pages 95-162. World Scientific, 1997.
[20] Joost Engelfriet and Grzegorz Rozenberg. Node replacement graph grammaars. In Handbook Of Graph Grammars And Computing By Graph Transformation: Volume 1: Foundations, pages 1 1-94. World Scientific, 1997.
[21] Eric Golin. Parsing visual languages with picture layout grammars. Journal of Visual Languages Computing, 2(4):371-393, December 1991. ISSN 1045-926X. doi: 10.1016/S (24559660000))8000555
[22] Grzegorz Rozenberg. Handbook of Graph Grammars and Computing by Graph Transformation, volume 1.
World scientific, 1997.
[23] Yanpeng Zhao, Liwen Zhang, and Kewei Tu. Gaussian Mixture Latent Vector Grammars. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1181-1189 189, Melbourne, Australia, 2018. Association for Computational Linguistics. doi: 10. 18.18/ 11/918-1109.
[24] Richard Socher, John Bauer, Christopher D. Manning, and Andrew Y. Ng. Parsing with compositional vector grammars. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 465-465, 2013.

---

[25] Shay B. Cohen. Sadent-Variable PCFGs: Background and Applications. In Proceedings of the 15th London, Meeting on the Mathematics of Language, pages London, UK, 2017. Association for Computational Linguisties. doi: 10. 11118/////11133444
[26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary Vitioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochllle, A. Beygelzimer, F. dAlché-Bin Buc, F, Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 0024-8035. Curran Associates, Inc., 2019.
[27] Jason Eisner. Outisie and Forward- Forward-Backward Backward Algorithms Are Just Backprop (tutorial paper). In Proceedings of the Workshop on Structured Prediction for NLP, pages 1-17, Austin, TX, 2016. Association for Computational Linguistics. doi: 10. 18653/v1/W 16- 5901.
[28] Yoon Kim, Chris Dyer, and Alexander Rush. Compound Probabilistic Context-Free Grammars for Grammar Induction. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2369-2385, Florence, Italy, 2019. Association for Computational Linguistics. doi: 10. 18653/v1/P19- 1228.
[29] Yu Zhang, Houquan Zhou, and Zhenghua Li. Fast and accurate neural CRF constituency parsing. In Proceedings of IJCAI, pages 4046-4053, 2020. doi: 10.24963/jeei.22220555)
[30] Alexander M. Rush. Torch-Struct: Deep Structured Prediction Library. arXiv:2002.00877 [cs, stat]. February 2020.
[31] Hoifung Poon and Pedro Domingos. Sum-produe networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pages 689-690, 690, Barcelona, Spain, November 2011. IEEE. ISBN 978-1-4673--063-6 978-1-4673--002-- 978-1-4673-0061-2 doi: 10. 1090///C1.2001111111 1.6130311..
[32] Alejandro Molina, Antonio Vergari, Nicola Di Mauro, Sriraam Natarajan, Floriana Esposito, and Kristian Kersting. Mixed sum-product networks: deep architecture for hybrid domains. In Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
[33] Xiaoting Shao, Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Thomas Liebig, and Kris- tian Kersting. Conditional sum-product networks: Imposing structure on deep probabilistic architectures. In International Conference on Probabilistic Graphical Models, pages 401-412. PMLR, 2020.
[34] David Chiang and Darcey Riley. Factor Graph Grammars. Advances in Newral Information Processing Systems, 33, 2020.
[35] David McAllester, Michael Collins, and Fernando Percira. Case-factor diagrams for structured probabilistic modeling. Journal of Computer and System Sciences, 74(1 74(1):84-96, February 2008. doi: 10. 01.0.0
[36] Diligenti, P. Frasconi, and M. Gori. Hidden tree Markov models for document image classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(4):5195523, April 2003. ISSN 1939-3539. doi: 10. 10.1109/TPAMI.000 1000001119977 1990578.
[37] Davide Bacciu, Alessio Micheli, and Alessandro Sperduti. Compositional generative mapping for tree- structured data-Part I: Bottom-up probabilistic modeling trees. IEFE transactions on neural networks and learning systems, 23( (3);:):1 1987-202, 2012.
[38] Animashree Anandkumar, Kamalika Chaudhuri, Daniel Hsu, Sham M Kakade, Le Song, and Tong Zhang. Spectral methods for learning multivariate latent tree structure. In J. Shawe-Taylor, R. Zemel, Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates. Inc., 2011.
[39] Myung Jin Choi, Vincent YF Tan. Animashree Anandkumar, and Alan Willsky. Learning latent tree graphical models. Journal of Machine Learning Research, 12:1771-1812, 2011.
[40] Furong Huang, Niranjan Uma Naresh, loakeim Perros, Robert Chen, Jimeng Sun, and Anima Anandkumar. Guaranteed scalable learning of latent tree models. Uncertainty in Artificial Intelligence, pages 883-893 PMLR, 2020.
[41] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631-1642, 2013.
[42] David Heckerman, Dan Geiger, and David M. Chickering, Learning Bayesian networks: The combination of knowledge and statistical data. Machine learning, 20(3): 243, 1995.
[43] David Heckerman and Dan Geiger. Learning Bayesian networks: A unification for discrete and Gaussian domains. arXiv preprint arxiv: 102.::30. 2013.
12

---

[44] Mathias Drton and Marloes H. Maathuis. Structure Learning in Graphical Modeling. Annual Review of Statistics and Its Application, 3()):36,-393, March 2017. ISSN 2326-8298, 2326-831X. doi: 10.1 146/ annurev-statiisicc--00 16-053803.
[45] Robert Gens and Domingos Pedro. Learning the structure of sum-product networks. In International Conference on Machine Learning, pages 873-880. PMLR, 2013.
[46] Sang-Woo Lee, Min-Oh Heo, and Byoung-Tak Zhang. Online incremental structure learning of sum-product networks. In International Conference on Neural Information Processing, pages 220-227. Springer, 2013.
[47]
Amirmohammad Rooshenas and Daniel Lowd. Learning sum-product networks with direct and indirect variable interactions. In International Conference on Machine Learning, pages 710-718. 18. PMLR, 2014.
[48] Antonio Vergari. Nicola Di Mauro, and Floriana Esposito. Simplifying, regularizing and strengthening sum- product network structure learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 343-358. Springer, 2015.
[49] Antonio Vergari, Alejandro Molina, Robert Peharz, Zoubin Ghahramani, Kristian Kersting, and Isabel Valera. Automatic Bayesian density analysis. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 5207 0015-, 2019.
[50] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In International Conference on Machine Learning, pages 1972-1982. PMLR, 2019.
[51] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang. Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 66-74.22 2020.
[52] Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gan: Dag structure learning with graph neural networks. In International Conference on Machine Learning, pages 7154-7163. PMLR, 2019.
[53] Denver Dash and Gregory F. Cooper. Model averaging for prediction with discrete Bayesian networks. Journal of Machine Learning Research, S(Sep): 2004.
[54] Marina Meilä and Tommi Jaakkola. Tractable Bayesian learning of tree belief networks. Statisties and Computing, 16(1))77-92, 2006.
[55] Marco Grzegorczyk and Dirk Husmeier. Improving the structure MCMC sampler for Bayesian networks by introducing new edge reversal move. Machine Learning, 71(2-3):265, 2008.
[56] Daniel Eaton and Kevin Murphy, Bayesian structure learning using dynamic programming and MCMC. In Proceedings of the Twenty- Third Conference Uncertainty in Artificial Intelligence (UAI 2007). 2007.
[57] Martin Trapp. Robert Peharz, Hong Ge. Franz Pernkopf, and Zoubin Ghahramani. Bayesian Learning of Sum-Product Networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc. E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 6344 6355. Curran Associates, Inc., 2019.
[58] Tom Minka and John Winn. Gates. In Advances in Neural Information Processing Systems, pages 1073-1080, 2009.
[59] Brendan Frey. Extending factor graphs so as to unify directed and undirected graphical models. In Christopher Meek and Uffe Kjærulff, editors, UAI '03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence, Acapulco, Mexico, August 7-10 2003, pages 257-264. Morgan Kaufmann, 2003. ISBN 10-12-00666-3
[60] Liang Huang and David Chiang- Better k-best parsing. In Proceedings of the Ninth International Workshop on Parsing Technology Parsing '05, pages 53-64, Vancouver, British Columbia, Canada, 2005. Association for Computational Linguistics. doi: (1115///655444.55550000
[61] U. Orguner and M. Demurekter. Analysis of single Gaussian approximation of Gaussian mixtures in Bayesian filtering applied to mixed multiple-model estimation. International Journal of Control, 80(6): 952-967, June 2007. ISSN 0020-7179. doi: 10.1080/00207 01100000207170001100 170701261952.
[62] Marco F. Huber and Uwe D. Hanebeck. Progressive Gaussian mixture reduction. In 2008 11th International Conference on Information Fusion, pages 1-8, June 2008
[63] David F. Crouse, Peter Willett, Krishna Pattipati, and Lennart Svensson. A look at Gaussian mixture reduction algorithms. In 14th International Conference on Information Fusion, pages 1-8, IEEE, 2011.
[64] Kaare Brandt Petersen, Michael Syskind Pedersen, Jan Larsen, Korbinian Strimmer, Lars Christiansen, Kai Hansen, Liguo He, Loic Thibaut, Miguel Barão, Stephan Hattinger, Vasile Sima, and We The. The matrix cookbook. Technical report, 2006.
13

---

[65] Stefan Koelsch, Martin Rohrmeier. R. Torrecuso, and S. Jentschke. Processing of hierarchical syntactic structure in music. Proceedings of the National Academy Sciences, 110433):15443-14448,, September 2013, ISSN 0027-8424, 1091-6490. doi: 10. 1073/ppas.130022222
[66] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT Press, Cambridge, Massachusetts London, England, 2006.
[67] Dimitrios Milios, Raffaello Camoriano, Pietro Michiardi, Lorenzo Rosasco, and Maurizio Filippone. Dirichlct-based Gaussian processes for large-scale calibrated classification. In Advances in Neural Information Processing Systems, pages 6005-6015, 2018.
[68] Daniel Harasim, Fabian C. Moss, Matthias Ramirez, and Martin Rohrmeier. Exploring the founda- tions of tonality: Statistical cognitive modeling of modes in the history of Western classical music. Humamities and Social Sciences Communications, 8(1):1-11, January 2021. ISSN 2662-9992. doi:
10.
[69] Craig Stuart Sapp. Harmonic Visualizations of Tonal Music. In Proc. International Computer Music Conference (ICMC), Havana, Cuba, 2001.
[70] Meinard Müller and Nanzhu Jiang. Scape Plot Representation Visualizing Repetitive Structures of Music Recordings. In ISMIR, pages 97-102. Citeseer, 2012.
[71] Robert Lieck and Martin Rohrmeier. Modelling Hierarchical Key Structure With Pitch Scapes. In Proceedings of the 21st International Society for Music Information Retrieval Conference, pages 811-818, Montréal, Canada, 2020. doi:
[72] Charles Truong, Laurent Oudre, and Nicolas Vayatis. Selective review of offline change point detection methods. Signal Processing, 167:107299, February 2020. ISSN 01651684. doi: (0.1016)).igprr.2000 2019, 107299.
[73] Martin Rohrmeier and Marcus Pearce. Musical Syntax I: Theoretical Perspectives. In Rolf Bader, editor, Springer Handbook Systematic Musicology, pages 473-486. Springer Berlin Heidelherg, Berlin, Heidelberg, 2018. ISBN 978-3-662-55002-11 978-3-662-55004-5, doi: 0011077997833-62-555006
[74] Carol L. Krumhansl and Edward J. Kessler. Tracing the dynamic changes in perceived tonal organization in spatial representation of musical keys. Psychologicul review, 89(4):334, 1982.
[75] David Temperley and Elizabeth West Marvin. Pitch-Class Distribution and the Identification of Key. Music Perception, 2533)1193-21,, February 2008. ISSN 0730-7829. doi: 10.1525/mp 2t155/mp.200..... 2008.25.3.199
[76] Joshua D. Albrecht and David Huron. Statistical Approach to Tracing Historical Development of Major and Minor Pitch Distributions, 1400-1750. Music Perception, 31(3):223 243, February 2014. ISSN
0730-7829. doi: 10. 10.1525/mp.2014.3...3
14


Reviews:
[{"review_id": "KvQMW7kQng", "reviewer": "Reviewer_1oXa", "summary": "As the title indicates a new formalism: recursive Bayesian networks is\npresented which is basically the union of PCFGs and DBNs. RBNs are\nproperly defined and their relation to PCFGs and DBNs clearly\nexplained (with examples). Since RBNs have both (hierarchical)\ndiscrete structure and continuous variables and are not \"finite\"\n(since PCFGs alone are not), inference is quite tricky. An extension\nof inside-outside computation (for PCFGs) is extended to RBNs. A\nsubclass of RBNs - Gaussian RBNs -  are focused on, and\nGaussianRBN-specific inference methods are presented. Two sorts of\nexperiments are presented: tree induction on synthetic data and music\nanalysis.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well-written. The goals are ambitious since RBNs are\nindeed highly expressive. So, as ever, the question is whether they\nare too expressive. Although the (inference) methods are well-chosen\n(I certainly can't think of any better options!) and show some\nmathematical sophistication, I did not go away from the paper with a\nreal feel for how big a problem RBNs can be applied to.\n\nIn their approach to inference the authors have\nopted for analytical approximation (e.g. approximating a mixture of\nGaussians by a single Gaussian (by moment matching)). An alternative\noption might have been some sort of Monte Carlo method. I don't know\nwhether a good Monte Carlo (MC) method exists for RBNs but I think it\nworth exploring: one often sees MC methods in the various formalisms\ninvented in the SRL literature (perhaps because it is relatively\neasy!).\n\nThe authors promise to show us \"the capacity and diverse applications\nof RBNs\". The music analysis presented was certainly interesting, and\nthe trained GRBN captured some aspects of harmony, but, for all I\nknow, some much simpler method could also have done this. I think it\nis fair to say we do not yet have a \"killer application\" for RBNs.\n\nIn summary, I have yet to be convinced of important real-world\napplications of RBNs, but perhaps it is unreasonably early to expect\nthat. The authors have designed sensible inference methods for a\nhighly-expressive probabilistic formalism and moreover explained what\nthey are doing very well.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "These have not been addressed. Doing so would be difficult given that RBNs are only introduced here. As mentioned in the main review it is hard to predict their impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "E_EoFsBvb1X", "reviewer": "Reviewer_VzMU", "summary": "The paper presents Recursive Bayesian Networks (RBN) which combine the strengths of probabilistic context-free grammars and dynamic Bayesian networks into a new class of probabilistic models. Specially, RBNs allow nested structures over the latent variables as well both discrete and continuous variables. Inference in these models is cast as a generalisation of inside and outside probabilities from probabilistic context-free grammars. Experimental results on a real-world music application demonstrate the effectiveness of the proposed approach.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is fairly well written and organised. The quality of the presentation is overall fairly good. I have two main comments which I think need to be addressed.\n\n1. While I appreciate the effort the authors put in to carefully describe the technical details of the proposed approach, the paper is quite dense and without a more concrete accompanying running example it is not easy to follow all the details especially by readers that are not familiar with PCFGs. For instance, I found Figures 2 and 3 a little confusing as it was hard to connect them to the inference procedure from section 2.\n\n2. Sum-Product Networks (SPNs) and their more recent extensions (Mixed SPNs - MSPNs, Conditional SPNs - CSPNs) are probabilistic models that can in principle capture hierarchical (or nested) structures over both discrete and continuous variables. Therefore, I was wondering if there isn't a closer connections (relation) between these models and the proposed RBNs.\n\nH. Poon and P. Domingos. Sum-Product Networks: a new deep architecture. UAI 2011.\n\nA. Molina, A. Vergari, N. Di Mauro, S. Natarajan, F. Esposito, K. Kersting. Mixed Sum-Product networks: a deep architecture for hybrid domains. AAAI 2018\n\nX. Shao, A. Molina, A. Vergari, K. Stelzner, R. Peharz, T. Liebig, K. Kersting. Conditional Sum-Product Networks: imposing structure on deep probabilistic architectures. PGM 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in the paper and there is no potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "CFVDney9dO", "reviewer": "Reviewer_gxvj", "summary": "Author proposed a new probabilistic model, Recursive Bayesian networks, that describes the generative process of sequence of random variables. After the model definition, author further demonstrated multiple inference procedures (exact and approximate) (marginal and structural) for the model. Lastly, author demonstrated the application of the model in areas of change point detection and hierarchical music analysis.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nThe paper propose a novel probabilistic model that describes a the joint distribution of a sequence. The model not only describes the likelihood of each symbols in the sequence being generated, it also describes the likelihood of the underlying hierarchical structure, e.g. a chain or a balanced tree. As a result, this new model generalizes two previous sequence model, Probabilistic Context-Free Grammars (PCFGs) and Dynamic Bayesian Networks(DBNs), by supporting continuous latent variables (which was not supported in PCFG) and uncertainties in tree structures (which is not supported in DBNs) simultaneously. \n\nQuality:\nThe formulation of RBN and its inference algorithm seems correct to me.\n\nClarity:\nThere are abundant of results that authors are trying to present, and it somewhat makes the paper dense to read. For example, the demonstration of the inference algorithm currently consists of equations in its most general form. It would be nice that inference procedure can be demonstrated with some simple examples. For example, how the marginal probability of a non-terminal latent variable, and the probably of a structure given the sequence is computed.\n\nSignificance:\nThe work is significant. First, RBN generalizes two existing powerful sequence models, PCFGs and DBNs, and it can model problems that none of its processor can handle solely. Secondly, author demonstrates the applicability of the RBNs in multiple domains, i.e. change point detection and  hierarchical music analysis. In particular, it shows quantitative improvements on the task of change point detection compared to the existing dedicated solution.\n\nMinor Edits:\nln:92 \"The left-hand side l_i of a transition p_i\" It is unclear what the left-hand side means here.\nln:144 \"non-terminal variable alpha_i:k\" -> \"non-terminal variable a_i:k\"\nln:173  \"convex models such as Gaussian RBNs\" -> what does it mean that Gaussian RBNs are convex? Does that mean gradient descent can find the exact Maximum Posterior result for Gaussian RBN?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6CXgSdmSjoX", "reviewer": "Reviewer_K4dB", "summary": "This paper proposes the \"recursive Bayesian network\", which appears to be an extension of probabilstic context-free grammars (PCFGs) with non-terminals that correspond to continuous latent variables.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have some reservations, partially in how the paper is pitched and then presented.  The concept of a \"recursive Bayesian network\" is appealing and ambitious, but perhaps too aggressive considering the presented results.  Mainly, I am not sure if the experiments are sufficient for such a bold claim.\n\nThe fully Gaussian (prior,non-terminal,terminal) case is the main focus of the paper.  The fully discrete case corresponds to PCFGs.  It doesn't seem like hte mixed-case is considered in this paper, which to my knowledge would be challenging (as is the case with reasoning and learning with mixed discrete/continuous Bayesian networks).  So I think it is a bit of a stretch to say that RBNs generalize both PCFGs and continuous DBNs.  Figure 1, suggests a continuous PCFG would be a more apt label.\n\nThe synthetic experiment in Section 3.1 seems to simulate data from an RBN and then tries to learn the model back using an RBN compared to hierarchical clustring, which is ifine.  I would be more straightforward with saying the synthetic data was simulated by an RBN, as it was only mentioned in the appendix.\n\nI believe the significance of the music model needs to be expanded.  For example, as a non-expert in machine learning for music, with some elementary background in music and music theory, I could not see the significance of extracting the hierarchical tree structure of a song.  I would expect a simple time-series model (like an HMM or a DBN) would also capture a dominant-tonic progression, and perhaps even more complex chord sequences, e.g., the common I-IV-V-I.  Another latent variable model was previously proposed that also takes raw notes as input:\n\n  \"A probabilistic topic model for music analysis\"\n  by Hu & Saul, NIPS 2009\n\nand I imagine a dynamic/temporal extension would also be sufficient (perhaps even using just a dynamic topic model for text).  Further, it seemed like the data was discrete, so again I am not sure why we would want to use a Gaussian RBN in this case.\n\nTo summarize, I believe the paper oversells its claims unneccessarily.  Perhaps a continuous PCFG would be interesting enough, although even then the experiments do not seem well motivated for learning hierarchical models with latent continuous variables.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "ok", "review_text": "", "extra_scores": {"ethical_concerns": "ok", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There have been mixed opinions about the manuscript, even after the short discussion. The paper describes an interesting model, some properties and algorithms. I share some concerns of a reviewer who is unsatisfied about how the work is presented, as it can give the impression to do more than it actually does. Indeed there are many direction here that could be worth investigating, and the presentation and choices could be better. It is unclear to me how tractable and how general things really are: they do not seem as efficient/tractable/general as one gets the impression in the beginning. On the other hand, the remaining reviewers are positive, in particular because there is potential for RBNs to be an important model, and the steps described here may be enough for justifying publication at neurips 2021.
Decision: Accept (Poster)