BAYESIAN NONPARAMETRIC MUSIC PARSER
Masahiro Nakano, Yasunori Ohishi, Hirokazu Kameoka, Ryo Mukai, Kunio Kashino
NTT Communication Science Laboratories, NTT Corporation
3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japannakano.masahiro@lab.ntt.co.jp

ABSTRACTƚŝŵĞThis paper proposes a novel representation of music that can be used
for similarity-based music information retrieval, and also presents amethod that converts an input polyphonic audio signal to the proposed representation. The representation involves a 2-dimensional
tree structure, where each node encodes the musical note and the dimensions correspond to the time and simultaneous multiple notes,
respectively. Since the temporal structure and the synchrony of simultaneous events are both essential in music, our representation reflects them explicitly. In the conventional approaches to music representation from audio, note extraction is usually performed prior to
structure analysis, but accurate note extraction has been a difficult
task. In the proposed method, note extraction and structure estimation is performed simultaneously and thus the optimal solution is
obtained with a unified inference procedure. That is, we propose
an extended 2-dimensional infinite probabilistic context-free grammar and a sparse factor model for spectrogram analysis. An efficient
inference algorithm, based on Markov chain Monte Carlo samplingand dynamic programming, is presented. The experimental results
show the effectiveness of the proposed approach.
Index Terms— infinite probabilistic context-free grammar (infinite PCFG), nonnegative matrix factorization (NMF), Markov chain
Monte Carlo (MCMC), hierarchical Dirichlet process (HDP)
1. INTRODUCTION
The analysis of musical audio signals has been a very active area of
research. One of the tasks most frequently addressed in the field has
been automatic music transcription, where the music audio is represented as a score [1, 2]. However, transcription from polyphonicmusic audio signals has continued to be a difficult task. On the other
hand, it is widely known that music can be perceived within a hierarchical structure over time, namely, frequent motifs, phrases, melodic
themes, or larger sections such as verses or chorus parts, where dominant elements contain subordinate elements. Since such a structure
and multiple note events are both essential elements embedded inmusic, these problems should be addressed simultaneously.
This paper proposes a novel hierarchical representation of music, and a parser, which is a method of obtaining the proposed representation from an input polyphonic music audio signal. The representation involves a 2-dimensional tree-structure. Each node encodes the musical note, and the dimensions correspond to the timeand simultaneous multiple notes, respectively. Applications of theparser and the representation we have in mind include content-based
music information retrieval systems. For example, even when thetempo, style, and instrumentation of the songs vary in a cover songidentification task, the trees directly give us a clue to the frequent978-1-4673-0046-9/12/$26.00 ©2012 IEEE

461

dŝŵĞͲƐƉĂŶ
ƉƌŽĚƵĐƚŝŽŶ
^ǇŶĐŚƌŽŶŝƐŵ

dŝŵĞͲƐƉĂŶ
ƉƌŽĚƵĐƚŝŽŶ

䊶ZĞĂůŝƐƚŝĐƉƌŽĚƵĐƚŝŽŶƐ

hŶƌĞĂůŝƐƚŝĐƉƌŽĚƵĐƚŝŽŶƐ

䊶䊶䊶
䊶䊶䊶

Fig. 1. Generative process of a 2-dimensional hierarchical tree (left)
and time-spanning productions (right).
motifs or melodic themes. Moreover, the representation can potentially be used to accelerate the music audio search because efficient
search techniques can be applied to the tree structure.
Conventionally, the generative theory of tonal music (GTTM)[3] is a well-known approach with which to understand musical intuitions [4]. “Time-span tree” [3] is used to represent a hierarchicalstructure of events. While their methods are mainly based on the empirical rules for constructing trees, we aim to obtain production rules
even in a probabilistic framework. Moreover, we also discuss a treestructured representation for polyphonic scores, although a “timespan tree” has generally been applied to monophonic scores.
Based on a Bayesian nonparametric framework, the proposedparser runs with little previous knowledge, and simultaneously optimizes both the estimated structure and the estimated notes through a
unified inference algorithm. As described in the following sections,the method comprises an extended 2-dimensional infinite probabilistic context-free grammar (PCFG) [5] and a sparse factor model forspectrogram analysis [1, 6], and employs Markov chain Monte Carlosampling and dynamic programming for inference.
2. BAYESIAN NONPARAMETRIC MUSIC PARSERMusic has a 2-dimensional hierarchical structure. Frequent motifs,
phrases or melodic themes consists of a hierarchy, which can be expressed as time-span trees. In addition, polyphony often has multiple
independent voices. That is, we can consider that music consists ofa time-spanning structure and the synchronization of multiple eventsat several levels of a hierarchy. We present a Bayesian model of
2-dimensional tree structures as a representation of music.
As shown in Fig. 1, the 2-dimensional tree-structured representation can be regarded as a possible generative model. Note that wehave not yet determined the pitch or timbral information for eachnote (discussed in Section 3). Fig. 1 shows the generative processof 1 bar. A whole note is first divided into two half notes, which
are expressed as the time-span production. The former half noteis then copied into the same location, which represents a two-note
chord. Note that chords require the concept of the “synchronization” of multiple notes. The latter half note is also divided into aquaver and a dotted quarter note. Such processes are also applied

ICASSP 2012to several levels of hierarchy. For another instance, the whole entity is divided into “verse”, “bridge”, and “chrous” (time-spanningstructure). The “chorus” part includes the counterpoint between two
voices (synchronism).
Such a hierarchy can be modeled with an extension of PCFG,
analogous to natural language processing. Since we hope that ourmodel will be applicable to all possible music signals, and parsimonious grammars should be automatically learned depending on input
data, we use a Bayesian nonparametric approach for modeling all
possible syntactic tree structures. Here, we first review the conventional Bayesian nonparametric PCFG, known as the infinite PCFG[5], to build up an understanding of our model. For simplicity, thispaper focuses only on Chomsky normal form grammars, which have
two types of rules: emissions and binary productions. A PCFG isa pair consisting of a context-free grammar (a set of symbols andproductions of the form A → B C or A → w, where A, B, and C
are nonterminal symbols and w is a terminal symbol) and production probabilities, and defines a probability distribution over trees ofsymbols. The parameters of each symbol consist of (1) a distribution over rule types, (2) an emission distribution over terminal symbols, and (3) a binary production over pairs of symbols. The infinite
PCFG has tackled the question of how to find an adequate numberof symbols. It is defined as having an infinite number of symbols bya hierarchical Dirichlet process (HDP) prior.
 We place the Dirichlet
process (DP) prior over symbols: G0 = ∞k=1 βk δφk ∼ DP(γ, I)
where I is a base measure over symbols and γ is a concentration parameter of DP. β shows symbol probabilities, and φk (k = 1, 2, . . . )are their atoms. The binary production distributions are drawn froma DP centeredon ββ T : Gk ∼ DP(α, G0 ) (k = 1, 2, . . . ) , whereG0 = i,j βi βj δ(φi ,φj ) . Each Gk can be intuitively regarded as
the infinite-dimensional multinomial distribution over children (thepairs of an unlimited number of symbols) whose parent is indexedby k. All Gk (k = 1, 2, . . . ) share the atoms (the pairs of symbols)
drawn from the top-level DP. The PCFG using HDP thus defines thetrees consisting of an infinite number of symbols.
In this paper we develop a 2-dimensional infinite PCFG with“length”-embedded symbols to express 2-dimensional hierarchicalstructures of music. The key difference is that we introduce biased
rules into the infinite PCFG. As shown in Fig. 1, time-span productions divide a parent’s region into two children’s region on thetime axis. For example, a half note can be divided into “crotchetand crotchet”, or “semiquaver and dotted quarter note”. However,
it is strange for a half note to be divided into “triplet and triplet”.
In other words, each node of the trees has its length on the timeaxis, and the production rules preferably maintain the total lengthof time in parent-child relationships (Fig. 1). The following strategy is inspired by the HDP with a correlation structure [7]. Since
the standard infinite PCFG inherently cannot model time-span structures, we relate the latent “length” on the time axis to each symbol.
The production probabilities are modified by their latent lengths.
A top-level Dirichlet process is first drawn with a product basemeasure:∞βk δ(φk ,Lk ) ∼ DP(γ, I × F ) ,
(1)
G0 =
k=1

where F provides a distribution over “length” space (∈ R). Lθ (θ =1, 2, . . . ) denotes the length embedded in the θ-th symbol. We canconsider G0 to be a probabilistic measure over symbols with latent
lengths. As in the infinite PCFG, we draw from the following process:
βi βj δ((φi ,Li ),(φj ,Lj )) , Gk ∼ DP(α, G0 ) .
(2)
G0 =
i,j

462

Second, the distributions over binary productions are formulated byscaling the probabilities of the Dirichlet process: (L − L − L )2 
i
j
k
(k)
(k)
, Gk (i, j) ∝ wi,j Gk (i, j) .
wi,j = exp −σ2(k)Intuitively, wi,j represents the similarity between the parent’s length
Lk and the sum of the children’s Li +Lj . With this, we can explicitly
give priority to the binary productions maintaining the total length oftime on parent-child relationships.
The remaining problem is how to generate the 2-dimensionalarchitecture of trees. As shown in Fig. 1, we can consider eachtree node as the dominant region on the time axis, which contains
smaller elements. First, each node should have not only “length” butalso “onset” to mark its placement. Such onset propagations provide
more flexibility for tempo fluctuation. Next, to express a synchronyof multiple notes, we introduce a binary indicator bm into each tree
node (indexed by m) : bm ∼ Bernoulli(aB ). When bm = 1, them-th binary production is chosen from Gk . Otherwise, a special
production related to “synchronization” is selected, which makes apair of the copy of the parent’s symbol and puts them in the same
location as the parent’s. We place the prior Beta(χ1 , χ2 ) on aB .
We now turn to a constructive representation of the proposedmodel. Various constructions of DP, HDP, and their extensions
have been proposed. The normalized Gamma process representation has a high affinity with our model [7]. We use the following finite approximation as the top-level Dirichlet process:β ∼ Dirichlet(γ/K, . . . , γ/K) where K works as the truncation level. As K increases, our approximation improves. Each
distribution over binary productions on the time axis is generated asa modification of the normalized Gamma process representation of
the Dirichlet process:
(k)

Zi,j

Gk

∼
=

(k)

(3)

δ((φi ,Li ),(φj ,Lj )) .

(4)

Gamma(α(ββ T )i,j , 1/wi,j ) ,

i,j



(k)
Zi,j
(k)
i ,j  Zi ,j Note that the Gamma distribution is parameterized by a shape parameter and a rate (inverse-scale) parameter. The generative processof a tree is based on the following rules:Childleft , Childright | Parent = k
⎧ 

(k)
Z
⎨
. . . ,  i,j (k) , . . .
(bm = 1)∼
(5)
i ,j  Zi ,j ⎩
(bm = 0)δ(k,k)
tl ∼ δ t p , t r ∼Normal(tp + LChildleft , ρ2 )
δt p

(bm = 1)
(bm = 0)(6)

where Childleft and Childleft denote indexes of symbols, tl andtr show their onsets, and tp is the onset of their parent node. If
the symbol indexed by k is assigned to the m-th node and bm =
(k) 
(k)
1, the weight Zi,j / i ,j  Zi ,j  of Gk gives the probability thatChildleft = i and Childleft = j are chosen.
3. FULL GENERATIVE MODEL FROM PARSING TREETO MUSIC SPECTROGRAM
In the previous section, we constructed a generative model for a 2dimensional tree structure. It can be used as a prior distribution on aBayesian model for music audio signals. Bayesian hierarchical approaches have the advantage that probabilistic values are inferred inunified frameworks. We apply it to sparse factor models, and in particular Bayesian nonnegative matrix factorization (NMF) [1]. The
conventional NMF applied to audio signal analysis is based on a music signal model where the magnitude or power spectrogram Y =(Yω,t )Ω×T ∈ R≥0 , where ω = 1, . . . , Ω is a frequency bin index,
and t = 1, . . . , T is a time frame index, is factorized into nonnegative parameters, spectral bases H = (Hω,n )Ω×N and time-varying
gains U = (Un,t )N ×T : Yω,t ≈n Hω,n Un,t . A generativemodel can be written as follows [6]: Yω,t = n Cω,t,n , Cω,t,n ∼Poisson(Hω,n Un,t ) , where C n denotes the n-th hidden component. This implies that a number of events that have a similar spectral pattern are extracted as one component. (For example, when A
is played three times on a piano in the input audio signal, the three
events can be expected to be learned as one component. ) In contrast, we want to construct a note-level model that makes use of thesymbolic tree-structured prior.
We assume that each note event consists of one spectral basis, its
total gain, a temporal envelope pattern (corresponding to one event),
and its onset time. The n-th note event chooses the dn -th spectral
pattern (Hω,dn )Ω×1 by the multinomial distribution over the dictionary of spectral patterns (Hω,d )Ω×D . Note that though the spectral bases including timbral information may be learned from input
data on the same principle as NMF, we, in this paper, train themin advance for simplicity. Similarly, the temporal envelope patternindexed by en , (Oen ,t )1×T  , is chosen from the pre-trained dictionary of temporal envelope patterns (Oe,t )E×T  , where T  denotes
the temporal size. In this paper, we manually fix the sizes of dictionaries, D and E, and the temporal size of envelope patterns T  at the
pre-trained stage. We can consider the following generative process
for the n-th event:(7)
Cω,t,n ∼ Poisson(Hω,dn Vn Oen ,t−τn ) ,where Vn denotes the gain, and the onset time is represented as τn .
Each τn is generated from the onset time tn of the corresponding
terminal symbol: τn ∼ Normal(tn , φ). Instead of finding an adequate number of events in advance, we introduce the Gamma process
prior for the overall gain of the corresponding source similarly to[1, 6]: Vn ∼ Gamma(η/N, ηλ), where N is the truncated numberof events.
4. INFERENCE
Our inference strategy is based on an improvement of combined dynamic programming and Markov chain Monte Carlo (a weak-limit
sampler using Metropolis-Hastings within Gibbs sampling). Due tolimitations of space, we discuss only the core techniques.
Sampling the parsing trees
Since the parse trees propagate the continuous value “onset times”
of symbols, standard dynamic programming is complicated for ourmodel. We thus derive computationally tractable approximations bytime discretization. “Onset times” are quantized by the truncationlevel. (We choose the window width of the short-time Fourier transform. ) With this, we can describe the following Gibbs sampler
using a dynamic programming algorithm [8]. First, we construct the“inside” table, which is similar to the standard Inside-Outside algorithm:(k) (t − t − L )2 

Zk ,k
1
r
kl
aB  l r(k) √exp −pn,n ,k,t ∝
2
2ρ
2πρ
Z
s,kl ,kr ,tri,j i,j·ps,n ,kl ,t pn,N −s+2,kr ,tr +(1 − aB )ps,n ,k,t pn,N −s+2,k,t .
s

463

where pn,n ,k,t denotes the sum of the probabilities of all trees
whose root node is labeled k, kl and kr show Childleft and Childleft
respectively, the onset time is t, and the terminals are from n -th ton-th series. Next, we obtain the sampling algorithm based on thefollowing multinomial distribution:p(s, kl , kr , tl , tr )p(k → (kl , kr ), t → (tl , tr ))ps,n ,kl ,tl pn,N −s+2,kr ,tr(8)=pn,n ,k,t
where s is the possible “split” position andp(k → (kl , kr ), t → (tl , tr ))(k) (t − t − L )2 
Zk ,k
1
r
kl
= aB  l r(k) √
exp −
2
2ρ
2πρ
Z
i,j i,j+(1 − aB )δ(kl = k, kr = k)δ(tr = t).

(9)

Sampling the weight Z and length L
As for the weight of the Gamma process, we choose the approximated conditional distributions as the proposal distributions. We(k)use a first-order Taylor expansion − log i,j Zi,j ≥ − log ζ (k) −

(k)
(k)
( i,j Zi,j /ζ ) + 1 on the log posterior. The conditional distribu(k)tion on Zi,j is approximated by the following distribution:


(k)
(k)
(k)
(k)
q(Zi,j ) = Gamma αβi βj + Ni,j , 1/wi,j + Ni,j /ζ (k) (10)(m)

where Ni,j denotes the number of times that the corresponding bi
(k)nary production is drawn. ζ (k) = i,j wi,j approximates the log(k)posterior well. When wi,j is close to zero, the large value of theinverse scale parameter practically destabilizes the sampling procedure. To avoid numerical issues, we choose instead to use theNormal distribution (truncated to hold nonnegativity) with the samemean equal to the above Gamma distribution, and apply an acceptance/rejection scheme based on the Metropolis-Hastings algorithm.
The latent lengths embedded in the symbols are also sampled by
the Metropolis-Hastings algorithm. We use the Normal distribution
as the proposal distribution, whose mean is given by Lθ −η·∂L/∂Lθ
where L is the log-posterior and η is the step size of the gradientdescent.
5. EXPERIMENTS
We now present some example that we undertook with the proposed
method. Audio data were downmixed to mono and downsampled
to 16 kHz. A magnitude spectrogram was computed using the shorttime Fourier transform with a 32 ms long Hanning window and a
16 ms overlap. As discussed in Section 3, adequate spectral bases
and temporal envelopes were trained by using certain state-of-theart NMF techniques, namely, harmonic constraints for spectral bases[2], different prior distributions to the tonal and percussive signals[9], and Bayesian nonparametrics [1].√ We set the hyperparameters
as follows: α = γ = 1, 
ρ = 1, φ = 2, σ = 1, η = 0.1, χ1 = 3,
χ2 = 2, and λ = ΩT / ω,t Yω,t . For the base measures of HDP,
we set I as the uniform distribution and F as the non-informative
Gamma distribution.
For the first experiment, we used two segments (bars 2-4 andbars 8-10) extracted manually from the classic song (RWC-MDB-C2001 No. 24A) [10]. The observation times for each segment were
the same length. We applied the proposed algorithm to them (twoparsing trees and the shared parameters) with truncation N=40 and! "$#&%'





# $
!"











 

 

 

 
 
    

 


















  



 








 

    









 

 




   







Fig. 4. Piano roll as the ground truth of note events (top) and estimated tree (bottom).







 











  
!("(#)%, 

Fig. 2. Piano roll asthe ground truth of note events (left) and estimated note events n Vn Oen ,t−τn (right). We trained 13 spectral
bases and 5 envelope patterns in advance. The proposed method
captured the nearly adequate number of notes and their pitch information.
!(" #*%+! "(#)% %









    





6. DISCUSSION



Fig. 3. Two examples of parsing trees corresponding to bars 2-4
of RWC-MDB-C-2001 No. 24A (shown in Fig. 2). Each row indicates the region (onset time and length) of each node of the estimatedparsing tree on the time axis. Since 2-dimensional tree structures are
too complicated to draw, parent-child relationships are not explicitly
presented. For instance, with the left sample, the 28-th node is divided into the 36 and 37-th nodes using “synchrony” production. As
for the right sample, the 32-nd and 33-rd nodes are generated fromthe 21-st node using “time-spanning” production.
K =15. The greatest length embedded in the symbols was fixed at
the time length of segments. Fig. 2 shows that the proposed method
decomposes audio signals into a nearly adequate number of active
events with their pitch information. As shown in Fig. 3, the proposed sampler shows a meaningful hierarchical structure related totime-span associations and simultaneous events. Since the MCMC
sampler gives us the estimated posterior distribution on parsing trees,
the clue can be directly applied to automatic music transcription: forexample the left sample implies that the opening four notes are simultaneous events in the form of an arpeggiated chord (played in
rapid succession) in the music score.
For the second experiment we applied the proposed algorithm(truncation level: K = 20) to two segments (bars 10-13 and bars 1821) extracted manually from a jazz song consisting of piano, bass,
and drums (RWC-MDB-J-2001 No. 16) [10]. It is very difficult todecompose these signals into individual note events. We thus set thesufficient number of events at N = 100, and the parsing tree was estimated using the mainly effective 60 events that had a larger volume
Vn . Because 40 smaller events contributed nothing to the parsing
tree and their parameters, their onsets were estimated based only on
Eq. (7) at the next iteration. Fig. 4 shows one example sampled by the
proposed MCMC. The higher level captures the five frequent groups.
“Swinging” rhythmics are captured in deeper layers. We confirmedthat the proposed method could capture frequent patterns and simultaneous active events at several levels of hierarchy. Although instrumental information (pitch information) does not depend on tree
structures in this paper, it must provide more meaningful representations of music signals. For example, we plan to learn frequent drum
patterns and rhythmic structures of melodic voices simultaneously
in the future.

464

We proposed a parser for music signals and the resulting music representation. It is based on Bayesian nonparametric sparse factor
analysis and PCFG. We also presented an efficient inference algorithm using MCMC and dynamic programming. Our experiments
showed that the proposed method successfully captured the multiple hierarchical structures of music signals. Concerning computational costs, for the first experiment, each MCMC iteration requires
approximately ten seconds with 2.5 GHz CPU, in non-optimized
MatlabTM . In the future, more sophisticated inference methods
will be considered, such as collapsed sampling [8], slice sampler[11], and retrospective sampling [12].
7. REFERENCES[1] M. D. Hoffman, D. M. Blei, and P. R. Cook, “Bayesian nonparametricmatrix factorization for recorded music,” in ICML, 2010, pp. 439–446.
[2] S. Raczynski, N. Ono, and S. Sagayama, “Multipitch analisys with harmonic nonnegative matrix approximation,” in ISMIR, 2007, pp. 381–
386.
[3] F. Lerdahl and R. Jackendoff, “A Generative Theory of Tonal Music,”
MIT Press, 1983.
[4] M. Hamanaka and S. Tojo, “Interactive GTTM analyzer,” in ISMIR,
2009, pp. 291–296.
[5] P. Liang, S. Petrov, M. I. Jordan, and D. Klein, “The infinite PCFG
using hierarchical Dirichlet processes,” in EMNLP, 2007, pp. 688–697.
[6] M. Nakano, J. Le Roux, H. Kameoka, T. Nakamura, N. Ono, and
S. Sagayama, “Bayesian nonparametric spectrogram modeling basedon infinite factorial infinite hidden Markov model,” in WASPAA, 2011.
[7] J. Paisley, C. Wang, and D. Blei, “The Discreate infinite logistic Normal
distribution for mixed-membership modeling,” in AISTATS, 2011.
[8] M. Johnson, T. Griffiths, and S. Goldwater, “Bayesian inference for
PCFGs via Markov chain Monte Carlo,” in NAACL, 2007, pp. 139–
146.
[9] O. Dikman and A. T. Cemgil, “Unsupervised single-channel source
separation using Bayesian NMF,” in WASPAA, 2009, pp. 93–96.
[10] M. Goto, H. Hashiguchi, T. Nishimura, and R. Oka, “RWC music
database: Popular, classical, and jazz music database,” in ISMIR, 2002,
pp. 287–288.
[11] M. Kalli, J. E. Griffin, and S. G. Walker, “Slice sampling mixture
models,” Statistics and Computing, vol. 21, no. 1, pp. 93–105, 2011.
[12] O. Papaspiliopoulos and G. O. Roberts, “Retrospective Markov
chain Monte Carlo methods for Dirichlet process hierarchical models,”
Biometrika, pp. 169–186, 2008.