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(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
([yy=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( 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
25)
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 N ((";;,,, Σ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 (9) (1)
(9)
(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 22). 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)):1663, 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-Bouillue 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 syntax-anaa analysis 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. Satent-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.613031...
[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 lcarning. 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-,21,2700 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ærulif, 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 01000000207170001100 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. 20.1525/mp.2014.3...3
14


Reviews:
[{"review_id": "o6BLp56qmVo", "reviewer": "Reviewer_dyhB", "summary": "This paper is about recursive Bayesian networks, in which a PCFG generates a set of graphical models, possibly with continuous random variables. The main application explored in this paper is music analysis, which involves some interesting modifications to the basic model.", "questions": "", "limitations": "", "rating": 4, "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": "Formalism\n\nThe definition of RBN allows a general CFG, but equations (18-21) assume that the CFG is in Chomsky normal form, and (35-36) extend them to rules of the form X -> a_1 ... a_m. Appendix A.1 partly describes how to convert a general CFG to Chomsky normal form, but it looks to me like two cases are missing: epsilon rules (of the form X -> \\epsilon) and unary cycles (of the form X_1 -> X_2, ..., X_2 -> X_m, X_m -> X_1). Please either amend the definition or the conversion so they match up.\n\nRBNs appear to be a special case of factor graph grammars (Chiang and Riley, NeurIPS 2020), although the present paper does far more to explore the case of inference with continuous random variables.\n\nModel\n\nTo make inference tractable, mixtures of Gaussians are approximated by a single Gaussian, which seems to me like a pretty big approximation. Is there any way to measure how much error is introduced by this approximation? For example, would it be possible to directly measure it on a toy example?\n\nLine 222: Are there other musical traditions where different assumptions would be more appropriate?\n\nExperiments\n\nIn Figure 6b, what metric is used to compare trees? In Appendix B.1 it appears that the synthetic data are generated from a simplified version of the RBN model itself, so it seems not that surprising that the RBN would perform better than the baseline HC/CPD method. Please correct me if I've misunderstood something about this experiment.\n\nIn a second experiment, the model is used to analyze music by Bach. Figure 6a shows that the model learns that all the preludes are in major keys, but aren't there much simpler methods that would tell you the same thing?\n\nIt also learns that all the transpositions are either trivial or transpose up by a fifth, which is more interesting. But I'm surprised that these two add up to 100%; shouldn't there be other transpositions as well?\n\nIn Figure 6c, what is the x-axis? What do the grayscale values mean? Is it possible to show the red and/or green tree with the transpositions included? The authors write that there are \"considerable deviations\" between the two trees, but to me it looks like this may be an understatement -- the two trees look wildly different.\n\nOverall, while acknowledging that it's difficult to communicate results to readers who may not know very much music theory, I believe that more could be done to validate the proposed RBN model. Perhaps experiments on a second task would be helpful.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would like to see more discussion of (1) the potential limitations introduced by approximating a mixture of Gaussians by a single Gaussian; (2) the relationship of the model used to generated the data in Figure 6b to the model used to learn from the data; and (3) the apparent failure of the model in Figure 6c to recover the ground-truth tree.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SVXWkXFegQy", "reviewer": "Reviewer_k7kf", "summary": "Good contribution, but very narrow domain for empirical validation. The paper presents Recursive BNs as an extension of classical DBNs based on PCFGs. The definition is almost straightforward, while inference might be critical. Yet, reasonable approximations are derived for the Gaussian case. The model is applied to music data (two data sets). Results are promising.", "questions": "", "limitations": "", "rating": 4, "confidence": 1, "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 class of models presented by the author(s) sound well motivated and perfectly reasonable. Yet, their practical advantages compared to simpler models are hard to evaluated with the current experiments. The considered domain (music) is very specific, while other contributions in the field also consider data about DNA, climatological, speech and many other, possibly more relavant, applications. For this simple reason, I think the paper might be not enough for being accepted at NeurIPS 2021. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think so.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "One hour."}, "extra_text": {}}, {"review_id": "PsQ-5D9Klv", "reviewer": "Reviewer_uEGL", "summary": "This paper presents an approach for hierarchical modelling where the structure of a model is a part of the model itself (similar e.g. to PCFGs). It is called Recursive Bayesian Networks (RBNs). An RBN model has a prior over its structure, and can consist of continuous and discrete latent (non-latent) and observable (terminal) variables. The authors consider this as an extension (generalisation) over PCFGs (and DBNs).\n\nTo explore the joint of the model, for the general case the authors extend the inside-outside algorithm for maximum a posteriori estimates of latent variables.\n\nThe authors also present a special case of RBNs, Gaussian RBNs (with some extensions) for hierarchical models (where structure inference is possible) with continuous variables. For this special case, the submission presents an analytic approach (that also uses inside and outside probabilities) for approximate estimation of a marginal likelihood and a marginal posterior.\n\nThe authors present two empirical experiments: (a) with some synthetic data compared to two other approaches; (b) with musical data for hierarchical music analysis (the analysis includes a comparison to the expert annotation performed by the authors).\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": "This is an extensive work and it covers quite a few things. Thanks a lot to the authors for it. This is important for the field of generative models and inference.\n\nThe paper is written generally well.\n\nSome relevant related work is covered. Based on that, generally the submission overall can be considered original. Some potentially relevant related work areas have not been covered, including: learning Bayesian networks for continuous/discrete variables (e.g. potentially ‘ “Ideal Parent” Structure Learning for Continuous Variable Bayesian Networks’ and ‘Structured Priors for Structure Learning’); and program synthesis/program induction of probabilistic programs that represent generative models.\n\nClarity:\n\nA. There are a lot of parts in this paper, but some parts are not covered in detail for full clarity (some parts are covered in the appendix, but some parts are not covered at all, to the best of my understanding). That limits an (easy) understanding of the paper (including for the purpose of a review). In particular:\n\nA1. More details, including an algorithm, and more detailed derivations, would be helpful for the lines 161-173 (“Maximum Posterior Inference” for the general case). In particular, what might be an exact algorithm? Can it be reasonably tractable (in terms of computations) and reliable (in terms of convergence)?\n\nA2. More details, in particular an exact algorithm, would be helpful for the lines 204-209 (“Tree Induction” for GRBNs). Can it be reliable (in terms of convergence/accuracy)?\n\nB. The positioning of the RBNs is not clear. In some parts of the paper, it is suggested that RBNs allow to express continuous and discrete variables (e.g. lines 87-89) (and that is the idea proposed in the paper in general), but in some parts it is suggested that RBNs are only for continuous variables (e.g. the position of RBNs in Figure 1; “also is” in line 84 (is “can also be” intended?)).\n\nC. Line 149 refers to the equation (17) as an unnormalised probability distribution but there is a denominator there in the equation; is it (partially) normalised, or is the denominator there for some other purpose? More clarification and maybe more details would help.\n\nD. I am sorry, The sentence in lines 171-173 is not fully clear:\n\nD1. (Just to double check, a minor point.) Is it right to read that the _exponential_ number of network structures is the reason for the “highly non-convex” property? (Just double checking.)\n\nD2. Not clear what is meant by “maybe be highly non-convex” “even for otherwise convex models”.\n\nE. (Just to double check, a minor point.) “the Appendix” in line 192 - is section A.4.2 meant? (A more precise reference might help.)\n\nF. Given that RBNs allow, by definition, different structures (e.g. that a non-terminal variable can have a different number of observed variables), it would be helpful to note/clarify why it is necessary to introduce/use “multi-terminal transitions” and why the “default” feature of RBNs can’t be exploited. (I appreciate that a reason might be that it is easier to advance the limited case of GRBNs with an additional feature because GRBNs allow, with some assumptions, some approximate analytical derivation; or/and because it is a more specific sub-model that might be expected to fit some problems well.)\n\nG. Similarly to the previous point (F), an GRBNs is extended to support categorical (discrete) data but the proposed general case of RBNs can support it “by default”. Some comments on why the GRBNs are extended in that way would be helpful.\n\nH. It would be helpful to clarify how exactly recall and precision are calculated in the experiments.\n\nI. Section 3.1 refers to “Figure 6(a)” (line 280) (but probably some other figure is meant?), and that is also referred to in section 3.2 (line 292) (likely correctly).\n\nJ. What is the “RBN estimate” in figure 6(c)? Is it the MAP?\n\nGiven the clarity points and the limitations described in another section of the review, although I think the authors have done a lot of work and that is appreciated, sadly I don’t feel comfortable at this point to recommend the submission’s acceptance, I am sorry. There is a chance though that: (a) I did misunderstand some points; (b) some points are obvious and they just were not mentioned (at all/in detail) in the submission; (c) or/and some points are valid and they can be addressed by the camera-ready version submission if the paper is accepted. Given the authors’ rebuttal, to which I am looking forward, there is a chance that the score might be adjusted.\n\nAll parts of the review are provided to the best of my understanding and knowledge. Mistakes/misunderstandings in the review are possible. I kindly ask to point me to them, if any, if possible, please.\n\n*\n\n**For the update, please, see my message dated the 2nd of September 2021 (GMT).**\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Acknowledged (at least partially) by the authors:\n\nA.1. It is unclear whether a continuous optimisation approach described in the section in lines 161-173 would be generally efficient.\n\nA.2. How reliable/limited is the approximation by a simple Gaussian as described in lines 191-193? \n\nA.3. The second empirical experiment results show that the model has not been able to match the expert annotations.\n\nA.4. The first experiment is based on synthetic data produced by a modified version of the model.\n\nA.5. The second experiment is using some annotations that (presumably) have not been independently reviewed (?).\n\nNot acknowledged (to the best of my understanding) by the authors:\n\nB.1. Empirical evaluation concerns only continuous variables (and not e.g. a combination of both continuous and discrete variables, which is the general case of RBNs).\n\nB.2. The general approach of RBNs, with continuous and discrete nodes (as per the definition of the RBN), is not tested fully. Only the case of Gaussian RBNs, with additional features, is tested.\n\nB.3. Experiments are limited: no comparison to existing methods on existing (i.e. independently of the paper) datasets (synthetic or not).\n\n*\n\nSocietal impact: there are potential huge positive impacts of the paper, and that is really appreciated. An obvious negative social impact might be if e.g. approximations do not fit a particular application (e.g. because of using a single Gaussian) and that might lead (unexpectedly) to (e.g. significantly) reduced accuracy (that might be not acceptable for some cases of a particular application); or an inference might not converge (and it might be not clear whether it has converged or not, and the model can be used nevertheless).\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "I have not tracked time. I generally conduct a review in a few sub-iterations, to be able to reflect (between them) on a submission/material under review for some time."}, "extra_text": {}}, {"review_id": "4G9R2SeAEMn", "reviewer": "Reviewer_c2bx", "summary": "The paper introduces the Recursive Bayesian Networks (RBN), which allows modelling nested hierarchical dependencies with continuous latent (non-terminal) symbols. Then, an inference procedure is derived to jointly optimize the latent structure and the model parameters. The inference procedure is the generalization of the inside-outside algorithm from PCFGs to the continuous case. \n \nThe authors also define a particular type of RBN which is based on Gaussian distributions: the Gaussian RBN (GRBN). The GBRN sets all the model continuous distributions as Gaussian distribution, obtaining a Gaussian Bayesian Network with an unknown structure. The missing structure implies a marginalization over all the possible structures that worsens the inference procedure. To keep the approach feasible, the authors introduce the “adaptive approximation” that allows approximating a mixture of Gaussian distributions with a single Gaussian.\n\nFinally, an experimental evaluation is performed on a synthetic and a real music dataset to assess the ability of the GRBN to infer both latent structures and distributions that are consistent with the tasks.", "questions": "", "limitations": "", "rating": 4, "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 proposes an interesting enhancement of recursive probabilistic models by allowing a continuous latent state-space. \n\nNevertheless, I have the following concerns:\n\n1) There is no citation/discussion on the Hidden Tree Markov Models (HTMMs) [1,2,3], which are commonly used to define a probability distribution over tree-structured data. The intrinsic recursiveness of HTMMs allows adapting on the structure of the data (that is not a priori defined and can be different for each sample). HTMMs are also related to Weighted Tree Automata (WTA), which in turn are connected to CFG. In fact, the set of all the derivation trees of a CFG is a regular tree language and therefore can be determined by a tree automata [4]. I believe that the aforementioned connections are of interest for the topic of the paper, even if they leverage a discrete latent state-space. In this regard, it is worth mentioning that Markov models for sequences with a continuous latent state-space have been already introduced in the literature [5]. Thus, I believe that the proposed RBNs are more related to the HTMMs (possibly with continuous latent state-space) rather than to the Deep Belief Networks (DBNs).  The paper would also benefit from placing the work properly in the context of the literature on latent tree estimation [6,7].\n\n2) Even if the paper is well-written and well-organised, the paper is not always easy to understand/follow:\n\n-\tfrom my understanding of the RBN definition, the structural variable S associated with the non-terminal symbol A is a categorical variable whose value indicates which transition distribution associated with A should be used to expand A. Nevertheless, in the rest of the paper, the value of S is True/False (because only two transitions are used: one to generate terminal symbols and one to generate non-terminal symbols), making it difficult to understand which is the transition associated with the value of S. It would be better if the value of S is an index (or better, a label) that uniquely identify the transition distribution. This becomes even more confusing in Equation (11-14) and (24-27) since:\n  + pT is used to indicate the only terminal transition distribution;\n  +  pN is used to indicate the only non-terminal transition distribution;\n  +  the variable S takes the values {T, F}, but the value T stands for True and not for “Terminal”. I believe that everything becomes more clear if S takes the values {T, N}, which are the label used to disambiguate the transition distributions. Also, the symbol pT denotes the set of all the transition distributions in RBN.\n\n-\tIn my opinion, some aspects deserve more attention in the paper to facilitate the understanding of the proposed model, such as the training algorithm and the procedure to induce the latent tree structure. In particular, it is not clear to me how the inside-outside probabilities computed are used to train the model parameters and to infer the latent tree structures. \n-\tIt is not clear why the transposition step is required for music data and what is its effect.\n\n3) The experimental evaluation is too limited:\n-\tthe paper highlights the need for probabilistic models with continuous latent state-space that also have a nested hierarchical dependency structure. Thus, I expected a comparison with models based on discrete latent variables to justify such a need. For example, why on music data do we need continuous latent variables?\n-\ta similar argument can be carried out for other design choices taken during the model definition. For example, a synthetic dataset could be used to assess the effectiveness of the “adaptive approximation” employed in the Gaussian RBN. Without such an analysis, it is hard to be convinced of the quality of the approximation since we lose the multi-modality of the original distribution;\n-\tthe proposed method is compared with only one model from the literature on one non-synthetic dataset. For example, PCFG are used in Natural Language Processing to obtain the latent structure of a sentence. Thus, it would be interesting to compare the proposed approach with other models in the literature currently employed in this domain (PCGF or neural).\n\n4)\tThere is no explicit discussion on the limitations of the proposed model. From my understanding, the main limitation could be the time complexity. It looks like that the inference procedure requires O(KN2) to compute the alpha-beta values, where N is the number of elements in the input sequence and K is the time required by the computation of Eq. (18-21). Also, it is worth mentioning that Eq. (18-21) require multiple marginalisations if no approximation is used.\n\nMinor concerns and typos:\n  + maybe there is a missing word after the distribution in Eq. (5);\n  + in the text between Eq. (15) and Eq. (17), I believe that the symbol “α” and the symbol “a” have been confused: “α” should refer only to the probabilities computes, while “a” should refer only to the latent variables;\n  + in the last paragraph of Section 3.1, there is a reference to Figure 6a which instead is related to hierarchical musical analysis. The discussion on that figure should be removed since it is not related to the figure that appears in the paper;\n  + “it” instead of “is in the last row of the caption of Figure 6.\n\nReferences:\n\n[1]\tM. Crouse, R. Nowak, and R. Baraniuk, “Wavelet-based statistical signal-processing using hidden markov-models,” IEEE Trans. Signal Process., vol. 46, no. 4, pp. 886–902, April 1998\n\n[2]\tM. Diligenti, P. Frasconi, and M. Gori, “Hidden tree markov models for document image classification,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 25, no. 4, pp. 519–523, 2003. \n\n[3]\tD. Bacciu, A. Micheli, and A. Sperduti, “Compositional generative mapping for tree-structured data - part I: Bottom-up probabilistic modeling of trees,” IEEE Trans. Neural Netw. Learning Syst., vol. 23, no. 12, pp. 1987–2002, 2012.\n\n[4]\tH. Comon and M. Dauchet and R. Gilleron and  C. Loding and F. Jacquemard and D. Lugiez and S. Tison and M. Tommasi, “Tree Automata Techniques and Applications”.\n\n[5]\tAinsleigh, Phillip L. Theory of continuous-state hidden Markov models and hidden Gauss-Markov models. NAVAL UNDERSEA WARFARE CENTER DIV NEWPORT RI, 2001.\n\n[6]\tAnandkumar et al Spectral Methods forLearning Multivariate Latent Tree Structure, NIPS 2011\n\n[7]\tChoi et al, Learning Latent Tree Graphical Models, JMLR 2011\n\n=== Post Rebuttal ===\n\nAfter reading through the other reviews and the Authors' responses it confirms that the paper as certainly some merit when it comes to addressing learning latent hierarchical structures with continuous latent variables. In this sense, the model is seemingly well founded and reasonable also in its strongest (motivated) approximations.\n\nOn the other hand, there seems to be little disposition towards connecting the work with existing literature and empirically comparing the approach to related (certainly less expressive) works.  A discussion of the relationships with HTMM and latent tree learning models seems needed. I reckon that HTMM do not learn a latent tree structure but are a more closely related model than DBN and HMM cited in the paper. Similarly, relationships with latent tree learning works such as [a] and latent graph structure learning [b] with deep NNs (hence inherenty continous in their representation) should be considered.  \n\nThe empirical analysis is too limited to be convincing on the potential impact of the model. If the model is addressing some relevant problem there should be certainly realistic tasks where it can be applied: if not, then this reduces the impact of the contribution. Also, while I reckon that there might not be other models in literature that work on raw polyphonic note sequences, the proposed approach could be applied to NLP tasks where other latent structure learning approaches have been benchmarked on (e.g. and where a continuous latent space might not be needed), to convince the reader that the proposed method can also perform well outside the single specific dataset presented in the work (in the end, the Authors are convincing in stating that the proposed method enlarges the breadth of application of existing models, so one might want to have empirical confirmation of this aspect).\n\nAll in all, I am fine in rasing a bit my score but I am still not convinced that the current content of the paper is sufficient to support acceptance.\n\n[a] F. Huang et al, Guaranteed Scalable Learning of Latent Tree Models, ICML 20\n[b] L. Franceschi et al, Learning Discrete Structures for Graph Neural Networks, ICML 19\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has no potential negative societal impact. Nevertheless, the authors do not explicitly mention the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Given the reviewer scores, after responses to the authors rebuttal, it is not possible to accept this paper.  For me the main issue is that the extension of Bayesian networks to PCFGs is an old issue with a large relevant literature. The primary innovation here seems to be the use of continuous random variables.  Continuous random variables in graphical models also has a very large literature. I think the reviewers were not convinced that putting these things together is sufficient for publication at NeurIPS.
Decision: Accept (Poster)