FUNCTION- AND RHYTHM-AWARE MELODY HARMONIZATIONBASED ON TREE-STRUCTURED PARSING AND
SPLIT-MERGE SAMPLING OF CHORD SEQUENCES
Hiroaki Tsushima1
Eita Nakamura1
Katsutoshi Itoyama1
Kazuyoshi Yoshii1,2
12Graduate School of Informatics, Kyoto University, JapanRIKEN AIP, Japan{tsushima, enakamura}@sap.ist.i.kyoto-u.ac.jp, {itoyama, yoshii}@kuis.kyoto-u.ac.jp

ABSTRACTThis paper presents an automatic harmonization method
that, for a given melody (sequence of musical notes), generates a sequence of chord symbols in the style of existing data. A typical way is to use hidden Markov models(HMMs) that represent chord transitions on a regular grid(e.g., bar or beat grid). This approach, however, cannot
explicitly describe the rhythms, harmonic functions (e.g.,
tonic, dominant, and subdominant), and the hierarchicalstructure of chords, which are supposedly important in traditional harmony theories. To solve this, we formulate a hierarchical generative model consisting of (1) a probabilistic context-free grammar (PCFG) for chords incorporating
their syntactic functions, (2) a metrical Markov model describing chord rhythms, and (3) a Markov model generating melodies conditionally on a chord sequence. To estimate a variable-length chord sequence for a given melody,
we iteratively refine the latent tree structure and the chordsymbols and rhythms using a Metropolis-Hastings sampler
with split-merge operations. Experimental results showthat the proposed method outperformed the HMM-based
method in terms of predictive abilities.
1. INTRODUCTION
Creation of chord sequences plays a key role in music composition and arrangement since harmony affects the moodof music and characterizes the impression of a certain musical style. Our aim is automatic melody harmonization, or
automatic generation of a sequence of chord symbols for agiven melody (a sequence of musical notes). In this paper,
we restricted our focus to the problem of harmonization in
the style of popular music. Instead of manually describing
music theories for the style such as jazz and classical music, we take a statistical approach to automatically learn
model architectures and parameters from a music corpus
and harmonize in the style of that data. We formulate aprobabilistic model that represents how likely a chord sequence is to be generated and another model that represents
c Hiroaki Tsushima, Eita Nakamura, Katsutoshi Itoyama,⃝
Kazuyoshi Yoshii. Licensed under a Creative Commons Attribution 4.0
International License (CC BY 4.0). Attribution: Hiroaki Tsushima,
Eita Nakamura, Katsutoshi Itoyama, Kazuyoshi Yoshii. “Function- andRhythm-Aware Melody Harmonization Based on Tree-Structured Parsing
and Split-Merge Sampling of Chord Sequences”, 18th International Society for Music Information Retrieval Conference, Suzhou, China, 2017.

Figure 1: The hierarchical generative model for chordsymbol, chord rhythms, and melodies.
how likely a melody is to be generated conditionally on achord sequence.
Since chord sequences are usually described by Markov
models [21, 25], a standard way to statistical harmonization is to use a hidden Markov model (HMM) that has alatent Markov chain of chord symbols and assumes a musical note sequence to be generated conditionally on thechords. This approach, however, does not consider thesyntactic roles and hierarchical structure of chords. In
traditional harmony theories (e.g., [14, 22]), such syntactic roles are often referred to as harmonic functions (e.g.,
tonic, dominant, and subdominant), which are similar toparts-of-speech in language theories. Another problem of
the conventional HMMs lies in the description of the chordrhythms (onset score times or durations of chords). Since
chord durations are described by self-transition probabilities on a regular time grid (e.g., beat or bar grid), the chordrhythms are not explicitly described.
To solve these problems, we propose a tree-structured
hierarchical generative model that consists of (1) a probabilistic context-free grammar (PCFG) that generates chordsymbols, (2) a metrical Markov model that generates chordrhythms, and (3) a Markov model that generates a melody
from a chord sequence (Fig. 1). The use of the PCFG was
inspired by Steedman’s pioneering work [27] that uses acontext-free grammar (CFG) for representing the hierarchical structure of chords. A key advantage of our study
is that the rule probabilities and tree structure of the PCFG
can jointly be estimated in an unsupervised manner froma corpus of chord sequences, expecting that the syntacticroles of chords are captured by the non-terminal symbols.

The metrical Markov model is used for explicitly describing transition probabilities between the onset beat positionsof succeeding chords.
Using the tree-structured hierarchical generative model,
we propose a statistical harmonization method based on a
sophisticated Metropolis-Hasting (MH) sampler with splitmerge operations. To estimate a variable-length chord sequence with appropriate chord rhythms for a given melody,
we stochastically search for the most likely latent tree
structure, symbols, and onset score times of chords fromtheir posterior distributions. In this search, our sampler has
four types of proposals: the whole latent tree structure is
updated using a variant of the Viterbi algorithm, one of thechords is split or two adjacent chords are merged according
to the latent tree structure, and one of the chord onset scoretime is moved back or forth. Such stochastic global or local updates can be interpreted as a repeated trial-and-error
process of finding an optimal chord sequence.
2. RELATED WORKThis section introduces related studies on the automatic
harmonization and on the music language model for chords
and notes.
2.1 Automatic Harmonization
Some studies on harmonization aim to generate sequencesof chord symbols (as in this paper) and other studies aim
to generate several (typically four) voices of musical notes.
In the former direction, Chuan and Chew [3] proposed a
hybrid method that consists of three processes: selectionof chord tones (constituent tones of chords) from given
melodies with a support vector machine (SVM), construction of triad chords from chord tones, and generation ofchord progressions by a rule-base method. Simon et al.
[25] developed a method based on HMMs in which chordtransitions are described by Markov models. This method
has been implemented in a commercial system MySong.
Raczyński et al. [21] proposed similar Markov models
in which chords are conditioned by melodies and timevarying keys. To our knowledge, PCFG has not been used
for melody harmonization.
In the latter direction, Ebcioğlu [5] proposed a rulebased method for generating four-part chorales in Bach’s
style. Methods by using variants of genetic algorithms(GAs) based on music theories have also been studied[18, 19, 28]. Allan and Williams et al. [1] proposed amethod based on HMMs which represent chords as hidden
states and musical notes as observed outputs. A hidden
semi-Markov model (HSMM) [9] has been used for explicitly representing the durations of chords. Paiement etal. [17] proposed a hierarchical tree-structured model that
describes chord movements from the viewpoint of hierarchical time scales by dividing the notations of chords.
2.2 Music Language Modeling
Several language models for musical notes have been studied for music structure analysis [10, 11, 13, 15]. According
to the Generative Theory of Tonal Music (GTTM) [13], anote sequence is assumed to have a hierarchical structurethat describes which notes are important. This theory consists of rules for recursively reducing a note sequence into asingle note. Computational implementation of GTTM andthe analysis of musical pieces using it have been studied[10, 11]. A probabilistic formulation of GTTM based on
PCFG has been proposed and enabled unsupervised learning of production rules directly from note sequences [15].
Various language models for chord sequences have been
proposed in the context of automatic chord recognition formusic audio signals [16, 24, 29], music analysis [23, 27],and music arrangement [6, 20]. The conventional language model for chord sequences is n-gram models [6,24].
To avoid the sparseness problem with a large value of n,smoothing methods have been studied for improving thepredictive ability of the language model [2]. Yoshii etal. [29] proposed a vocabulary-free infinity-gram model inwhich each chord depends on a variable-length history of
chords. Paiement et al. [16] introduced several hidden layers of state transitions that represent the hierarchical structure of chords. Some studies attempted to explicitly describe the generative grammar to represent the hierarchical structure of chords [20, 23, 27]. Steedman [27] andRohrmeier [23] proposed a description of the production
rules for chord sequences. A probabilistic extension is later
studied in the context of music arrangement and unsupervised learning of the probabilities has been performed [20].
In these studies, the lists of non-terminals and production
rules were manually given based on music theories or musical intuition.
3. PROBABILISTIC MODELINGThis section explains how to formulate and train our hierarchical generative model of chords and melodies. In
our model, the PCFG for chord symbols is trained byunsupervised learning from a corpus of chord sequences
while estimating the latent tree structures behind these sequences. The metrical Markov model for chord rhythms
is trained by supervised learning from a corpus including
chord rhythms. The Markov model for pitch sequencesis also trained by supervised learning from paired data of
melodies and chord sequences.
3.1 Model Formulation
The PCFG stochastically generates a sequence of chordN
symbols (or simply chords in the following) z = {zn }n=1
and the metrical Markov model generates the correspondNing onset score times ϕ = {ϕn }n=1 described in unit of
16th notes, where N is the number of chords. A subsen
in thequence of pitches in the melody xn = {xn,i }Ii=1time span of each chord zn is then generated, where In
is the number of pitches in that time span. Concatenating all such subsequences, the wholeof pitches∑sequenceNN
x = {xn }n=1 is obtained. I =Idenotesthenn=1
number of melody notes. Let ψn,i be the onset scoretime of the melody note corresponding to xn,i and letn}Nψ = {{ψn,i }Ii=1
n=1 . ϕn and ψn,i can take integer values from 0 to 16L − 1, where L is the total number ofmeasures in the whole melody. Although in the training
phase, we have multiple sequences of chords sequencesand melodies, we formulate here the case of a single sequence for notational simplicity. Extension for multiple
sequences is straightforward.
The PCFG G is defined by
G = (V, Σ, R, S),(1)

where V is a set of non-terminal symbols, which are
expected to represent hierarchical structure and syntacticroles of chords, Σ is a set of terminal symbols (chord symbols), R is a set of rule probabilities, and S is a start symbol (a non-terminal symbol located on the root of a syntax tree). Rule probabilities consist of the following three
types. θA→BC is the probability that a non-terminal symbol A ∈ V branches to non-terminal symbols B ∈ V andC ∈ V . ηA→α is the probability that A ∈ V emits terminal symbol α ∈ Σ. Each non-terminal symbol A ∈ V hasa coin-toss probability λA that stochastically determines
whether A emits (otherwise A branches). These probabilities should be normalized properly as follows:∑∑
θA→BC = 1,
ηA→α = 1.
(2)
B,C∈V

3.2 Bayesian Learning
We obtain the model parameters Θ = {θ, η, λ, π, τ } by
the maximum posterior (MAP) estimation. To estimate
the parameters θ, η, and λ of the PCFG, we use a variant of Gibbs sampling called the inside-filtering-outsidesampling algorithm [12]. We assume that a chord sequencez was derived from a latent syntactic tree t. t can be represented by a set of non-terminal nodes {tn:m }1≤n≤m≤N ,where tn:m is the root node of a subtree that derives a
subsequence of chords zn:m = {zn , zn+1 , · · · , zm }. The
latent tree t and the parameters θ, η, and λ are alternately sampled from the conditional posterior distributions p(t|θ, η, λ, z) and p(θ, η, λ|t, z). This algorithm isproven to yield samples of t, θ, η, λ following the true
posterior distribution p(θ, η, λ, t|z).
In the inside filtering step, we focus on the conditional
probability (inside probability) that a subsequence zn:m isderived from a subtree whose root node is A
pA
n,m = p(zn:m |tn:m = A).

(10)

α∈Σ

We define θ A = {θA→BC }B,C∈V , η A = {ηA→α }α∈Σ ,θ = {θ A }A∈V , η = {η A }A∈V , etc. Similar notations areused throughout this paper.
The metrical Markov model describes the transition
probabilities for chord onset beat positions (16th-note level
relative score time in a measure) asp(ϕn |ϕn−1 ) = πϕ̄n−1 ,ϕ̄n ,pA(11)n,n = λA ηA→zn ,
]
∑ [
∑
A
B
C
pn,n+k =(1−λA )θA→BC
pn,n+l−1 pn+l,n+k .
B,C∈V

1≤l≤k

(3)

where ϕ̄n = ϕn mod 16 and πab (0 ≤ a, b < 16) indicates
the transition probability from beat position k to beat position l. When ϕ̄n ≤ ϕ̄n−1 , we interpret that the onset ofchord n is in the next measure.
The Markov model is described with the following transition probability:np(xn,m |xn,m−1 , zn ) = τxzn,m−1,xn,m ,

This probability can be calculated recursively from the leaf
nodes to the root node as follows:(4)nwhere τxzn,m−1,xn,m is the transition probability from pitchxn,m−1 to pitch xn,m under chord zn . In addition, theprobability of the first pitch in xn is given by p(xn,1 |zn ).
We put conjugate priors on the parameters of the PCFG
as

In the outside sampling step, we recursively sample alatent tree t from a start symbol S to the leaf nodes according to p(t|θ, η, λ, z) by using the inside probabilities.
When a node tn:n+k = A is already sampled, the two nonterminal symbols B and C into which tn:n+k branches are
sampled as follows:p(l, B, C)= p(tn:n+l−1 = B, tn+l:n+k = C | tn:n+k = A, zn:n+k )CA= (1 − λA )θA→BC pBn,n+l−1 pn+l,n+k /pn,n+k ,(12)where 1 ≤ l ≤ k indicates a split position.
Finally, we sample parameters θ, η, and λ according top(θ, η, λ|t, z) = p(θ|t, z)p(η|t, z)p(λ|t, z) given byθ A ∼ Dirichlet(ξ A ),(5)

η A ∼ Dirichlet(ζ A ),(6)

θ A ∼ Dirichlet(ξ A + uA ),(13)

λA ∼ Beta(ιA ),(7)

η A ∼ Dirichlet(ζ A + v A ),(14)

λA ∼ Beta(ιA + wA ),(15)

where ξ A , ζ A and ιA are hyperparameters. Similarly, we
put conjugate priors on the parameters of the Markov models as follows:
π a ∼ Dirichlet(β),(8)τ zx ∼ Dirichlet(γ),(9)

where β and γ are hyperparameters.
To complete the generative model of chords andmelodies, we need to specify a model generating ψ. Thismodel can be formulated as for the model of ϕ and we omit
the details here since melodies are given as inputs for ourharmonization problem.

where uA→BC (vA→α ) is the number of times the binary
production rule θA→BC (the emission rule ηA→α ) is used
in t, and wA,0 (wA,1 ) is the number of times a non-terminal
symbol A branches (emits) and t.
The parameters π and τ of the Markov models are obtained by supervised learning. Given ϕ, the posterior distribution of π can be calculated easily because of the conjugacy between the Dirichlet and categorical distributions.
Similarly, given paired data of z, ϕ, x, and ψ, the posterior
distribution of τ can be calculated.

4. AUTOMATIC HARMONIZATIONThis section explains how to generate sequences of chords
for a given melody by using the model in Section 3.
4.1 Problem Specification
Given a melody with pitches x and onset score times ψ andtrained model parameters Θ, we aim to estimate a variablelength sequence of chords z and their onset score times ϕthat are not restricted to bar lines. Note that the number ofchords N is not fixed and should be estimated and that alatent tree t for chords is considered and estimated unlike
conventional harmonization methods.
4.2 Metropolis-Hastings Sampling
We propose a Metropolis-Hastings (MH) sampler withsplit-merge operations for generating samples of t, z, andϕ from the posterior distribution p(t, z, ϕ|x, ψ, Θ) basedon the following four types of proposals:• Global update: Update chords z and latent tree t
with a Viterbi algorithm for the PCFG, keeping thenumber and score times of chords unchanged.
• Split operation: Randomly choose one of thechords and split it into two adjacent chords.
• Merge operation: Randomly choose two adjacentchords in z that form a subtree with two leaves in t
and merge them.
• Rhythm update: Randomly choose one chord n
and move its onset score time ϕn back or forth.
Although it is more proper to use the inside-filteringoutside-sampling algorithm for the global update, theViterbi algorithm is used for efficient optimization in theposterior space.
In the MH sampling, one of these proposals is randomly
selected. More specifically, the sampler proposes a sample s∗ = (t, z, ϕ)∗ from a current sample s = (t, z, ϕ).
The sampler then judges whether s∗ is accepted as the next
sample or not according to the acceptance ratio given by{}p(s∗ )p(s|s∗ )g(s∗ , s) = min 1,,(16)p(s)p(s∗ |s)where p(s) is the complete joint likelihood of s based on
the proposed model and p(s∗ |s) is a proposal distributionthat should be set appropriately. If the proposal is rejected,t, z, and ϕ are not updated. In our method, there are three
types of proposal distributions for the second to fourth proposals in the above list. We estimate the most plausible z
and ϕ by iterating the MH sampling a sufficient number oftimes and then getting the latent variables that maximize
the likelihood of complete data.
4.3 Updating Chord Symbols
We describe how to update the chord symbols z and thecorresponding latent tree t according to the conditional
posterior distribution p(t, z|ϕ, x, ψ, Θ).
4.3.1 Viterbi Algorithm
Given a melody with pitches x and onset score times ψ,
we can efficiently sample a sequence of chord symbols z

Figure 2: The split-merge operations of the MH sampling.
and the corresponding latent tree t by using the Viterbi algorithm. Our algorithm differs from a standard Viterbi algorithm used for estimating t for a given z because both tand z are the latent variables to be estimated in this paper.
We first recursively calculate the inside probabilities
from the layer of terminal symbols z to the start symbol
S according topA
n,n = λA max ηA→c p(xn |c)
c∈Σ

1/In

,

(17)

B
C
pA
n,n+k = (1 − λA ) max θA→BC pn,n+l−1 pn+l,n+k ,
B,C∈V
1≤l≤k

where p(xn |c) is the probability that a pitch subsequencexn is generated conditionally on a chord c:p(xn |c) = p(xn,1 |c)In∏

p(xn,i |xn,i−1 , c).

(18)

i=2

The most likely t and z are obtained by recursively backtracking the most likely paths from the start symbol S.
4.3.2 Split-Merge Operations
Using the MH sampler, we can split a chord or merge adjacent chords by considering the underlying tree t and theemission probability of the melody. Note the split andmerge operations are inverse to each other and that the latent tree t is locally updated by these operations (Fig. 2).
In the split operation, a new sample s∗ is proposedby stochastically selecting a chord zn from z, splitting
zn into z L and z R , selecting the new onset score timeϕ∗ ∈ (ϕn , ϕn+1 ) = [ϕn + 1, ϕn+1 − 1], and splitting thenon-terminal symbol tn:n into two non-terminal symbols
tL and tR . The proposal distribution p(s∗ |s) is thus{θ
tn:n →tL tR ηtL →z L ηtR →z R
, ϕn+1 ≥ ϕn + 1;∗
N (ϕn+1 −ϕn −1)p(s |s) =0,otherwise.
(19)
The reverse proposal distribution p(s|s∗ ), on the other
hand, is same as the proposal distribution for the merge
operation in which a sample s is proposed by stochastically selecting a pair of adjacent chords z L and z R , merging those chords into zn , by selecting a chord zn according
to the probability ηtn:n →zn . Thus we havep(s|s∗ ) =ηtn:n →zn,
#MergeableNodes(s∗ )(20)where #MergeableNodes(s∗ ) is the number of pairs of adjacent chords that can be merged in s∗ , i.e., those chords
forming a subtree with two leaves.

The likelihood ratio of p(s∗ ) to p(s) is then given byp(s∗ ) (1 − λtn:n )θtn:n →tL tR λtL ηtL →zL λtR ηtR →zR=p(s)λtn:n ηtn:n →zn
L L
p(x |z )p(xR |z R )p(ϕ∗ |ϕn )p(ϕn+1 |ϕ∗ )·,p(xn |zn )p(ϕn+1 |ϕn )(21)
where xL and xR are the subsequences of pitches obtainedby splitting xn at the score time ϕ∗ . Using Eqs. (19), (20),and (21), we can calculate the acceptance ratio of s∗ according to Eq. (16).
In the merge operation, on the other hand, a new samples∗ is proposed in a similar way to the split operation. Morespecifically, the acceptance ratio of s∗ given by Eq. (16)can be calculate by exchanging s and s∗ in Eqs. (19), (20),and (21). Through the split-merge operations, the numberof chords N is optimized stochastically.
4.4 Updating Chord Rhythms
We describe how to update the chord rhythms ϕ according
to the conditional posterior distribution p(ϕ|t, z, x, ψ, Θ).
A new sample s∗ is proposed by stochastically selecting
a chord n and moving ϕn to a new score time ϕ∗n ∈(ϕn−1 , ϕn+1 ). The proposal distribution p(s∗ |s) and thereverse proposal distribution p(s|s∗ ) are given byp(s∗ |s) = p(s|s∗ ) =1
1.
N − 1 ϕn+1 − ϕn−1 − 1(22)

The likelihood ratio of p(s∗ ) to p(s) is given byp(x∗n−1 |zn−1 )p(x∗n |zn )p(ϕ∗n |ϕn−1 )q(ϕn+1 |ϕ∗n )p(s∗ )=,p(s)p(xn−1 |zn−1 )p(xn |zn )p(ϕn |ϕn−1 )p(ϕn+1 |ϕn )(23)
where x∗n−1 and x∗n are the subsequences of pitches in thetime spans of chords n−1 and n with the new onset scoretime ϕ∗n . Using Eqs. (22) and (23), we can calculate theacceptance ratio of s∗ according to Eq. (16).

To train the two Markov models in a supervised manner,
we extracted 9902 pairs of melodies and the corresponding chord sequences from 194 pieces of popular music included in Rock Corpus [4]. The values of the hyperparameters were all set to 0.1.
In the testing phase, we extracted 339 pairs of melodies
and the corresponding chord sequences as ground-truth
data for evaluation from 69 pieces of popular music included in the RWC music database [7, 8]. Note that all thedata (SALAMI, Rock Corpus, and RWC) were transposed
to C major or C minor.
5.2 Evaluating Ability of Melody Prediction
To evaluate the hierarchical generative model based on the
PCFG in terms of the ability of melody prediction, we calculated the marginal likelihood for the melodies extracted
from the RWC music database. The number of kinds of
non-terminal symbols, or the complexity of the PCFG, K
was changed from 1 to 20. In each of cases for K, we obtained different PCFG’s parameters with Gibbs sampling
and calculated the marginal likelihood for each parameter
set. The number of different parameter sets were between
37 and 50 depending on the computational complexity. We
assumed that the chord onsets were completely synchronized with bar lines such that the chord sequences were
marginalized analytically. The proposed model was compared with an HMM that learns the chord-symbol transition between adjacent units which were either musicalnotes or measures. When minimum time units were musical notes, each note was assumed to be generated conditionally on the chord symbol at the time. When minimum time units were musical measures, notes accompanying each chord were assumed to be generated according
to the probability described in Eq. (4).
The marginal likelihood of the trained model parameters Θ for an unseen melody X with ψ can be calculatedwith the inside algorithm in Section 3.2. To sum over all
possibilities of a latent chord sequence Z and a latent tree
T , pAi,i in Eq. (11) is replaced with
pA
i,i = λA∑ηA→c p(Xi |c),

(24)

c∈Σ

5. EVALUATIONIn this section, we report two experiments conducted toquantitatively evaluate the proposed generative model andthe proposed method of automatic harmonization based on
the model and discuss examples of chord sequences generated by the method.
5.1 Experimental Conditions
To learn the PCFG unsupervisedly, we extracted 1002
chord sequences corresponding to sections (e.g., verse,
bridge, and chorus) from 468 pieces of popular music included in the SALAMI dataset [26]. Only those sequenceswith a length between 8 and 32 were chosen. The vocabulary of chord symbols was given by the combinations of
12 root notes {C, C#, D, ..., B} and 2 chord types {major,
minor}, and a special “other”. The values of the hyperparameters were all set to 0.1.

where p(Xi |c) is given by Eq. (18). The average marginal
likelihood L per note for the melody is given byL=

1
1
log p(X|ψ, Θ) = log pS0,N −1 ,
I
I

(25)

where I (N ) is the number of notes (chords).
The experimental results are shown in Fig. 3. The proposed model outperformed the HMM, whether the minimum time unit is a musical note (L = −3.2813) or a measure (L = −2.3218). The likelihood tended to decrease as
the value of K increased to eight, and the likelihood tended
to increase as the value of K increased beyond eight.
5.3 Evaluating Predictive Ability of Chord Sequences
To evaluate the proposed harmonization method in termsof the predictive ability of unseen chord sequences, we
generated chord sequences for the melodies of the RWC

Figure 3: Marginal likelihood for melodies per note. In
this box plots, the red line, the black cross and red crosses
indicate the median, the mean and outliers, respectively.

Figure 4: Accuracy of harmonization per note. Indicatorsin this box plots are the same as those in Fig. 3
music database and calculated the accuracy at a 16th-notelevel compared with the ground-truth. The complexity of
the PCFG, K was changed from 1 to 20. The proposed
method was compared with a conventional HMM-based
method that represents chord transitions on a 16th-notelevel grid.
The experimental result are shown in Fig. 4. The
proposed model clearly outperformed the HMM-based
method with an accuracy of 16.6 %. While a certain rangeof K showed much higher accuracy (e.g., 26 %) than the
HMM-based method, there was little correlation between
K and the median values of accuracies.
5.4 Generated Example and Discussion
Fig. 5 shows how the proposed MH sampling method withsplit-merge operations worked for automatic harmonization1 . The number of kinds of non-terminal symbols, K,
was set to 12. The chord sequence at the top shows an initial sample in which the chord symbols were optimized by
the Viterbi algorithm, but the chord onsets were located at
the bar lines. The second chord sequence shows a sample proposed by moving the onset positions of 5th and6th chords (G major and C major). The third chord sequence shows a sample proposed by merging the 7th and8th chords (F major and C major) into one chord (C major). The bottom chord sequence shows the best sample
that maximizes the likelihood for the given melody. In
each of the processes, the likelihood increased. The result
indicates that the proposed method can successfully gen1 Some chord sequences generated in this experimental are available

online: http://anonym9329.github.io/demo.html

Figure 5: Sampling-based estimation of the most likely
chord sequence for a given melody.
erate a variable-length sequence of chords by considering
the latent tree structure behind the chord sequence.
We found some problems to be tackled in the future.
The proposed method tended to generate simple chords(e.g., C major and A minor). This is because the chordsymbols were refined by using the Viterbi algorithm. In
addition, the number of the most plausible chord sequences
selected in our experiment was rarely more than those initialized at the beginning of sampling. This is because theproposals of the split operation were accepted less frequently than the proposals of the merge operation.
6. CONCLUSION
This paper presented an automatic harmonization methodthat generates a variable-length chord sequence for a given
melody based on music rules hidden in corpora of popular
music. The experimental results showed that the proposedmodel outperformed the HMM-based method in terms ofpredictive ability and has a large potential for statisticalmusic composition or arrangement.
Since our method is based on statistical learning, it was
found to prefer simpler and basic chord sequences. Morespecifically, the number of generated chords tends to beless than the number of measures. This problem could be
solved by giving more chances to the split operation in
MCMC sampling. To increase the diversity of generated
chord symbols, a sampling or beam-search method is considered to be effective instead of the Viterbi algorithm thattends to find a popular chord sequence that has the highest
posterior probability from the statistical viewpoint.
We still need further studies on our model. In this paper, one measure with the time signature of 4/4 is divided
into 16 time units. It is therefore important to investigate
the best time resolution and extend the model to deal withother kinds of time signatures. In addition, to evaluate themusical appropriateness of generated chord sequences, weplan to conduct a subjective listening test and evaluate how
consistent our model is with music theories or musical intuition.
Acknowledgement: This study was partially supported by JSPS
KAKENHI Grant Numbers 26700020, 16H01744, and 16J05486
and JST ACCEL No. JPMJAC1602.

7. REFERENCES[1] M. Allan and C. Williams. Harmonising chorales by
probabilistic inference. In Advances in Neural Information Processing Systems (NIPS), pages 25–32, 2005.
[2] S. F. Chen and J. Goodman. An empirical study ofsmoothing techniques for language modeling. In Association for Computational Linguistics (ACL), pages
310–318, 1996.
[3] C. H. Chuan and E. Chew. A hybrid system for automatic generation of style-specific accompaniment. In
Proceedings of the 4th International Joint Workshop
on Computational Creativity, pages 57–64, 2007.
[4] T. D. Clercq and D. Temperley. A corpus analysis ofrock harmony. Popular Music, 30(01):47–70, 2011.
[5] K. Ebcioğlu. An expert system for harmonizing fourpart chorales. Computer Music Journal, 12(3):43–51,
1988.

[16] J. F. Paiement, D. Eck, and S. Bengio. A probabilistic
model for chord progressions. In ISMIR, pages 312–
319, 2005.
[17] J. F. Paiement, D. Eck, and S. Bengio. Probabilistic
melodic harmonization. In Conference of the Canadian Society for Computational Studies of Intelligence,
pages 218–229, 2006.
[18] G. Papadopoulos and G. Wiggins. AI methods for algorithmic composition: A survey, a critical view andfuture prospects. In AISB Symposium on Musical Creativity, pages 110–117, 1999.
[19] R. D. Prisco and R. Zaccagnino. An evolutionary music composer algorithm for bass harmonization. Applications of Evolutionary Computing, pages 567–572,
2009.
[20] D. Quick. Learning production probabilities for musical grammars. Journal of New Music Research,
45(4):295–313, 2016.

[6] S. Fukayama, K. Yoshii, and M. Goto. Chordsequence-factory: A chord arrangement system modifying factorized chord sequence probabilities. In ISMIR, 2013.

[21] S. A. Raczyński, S. Fukayama, and E. Vincent. Melody
harmonization with interpolated probabilistic models.
Journal of New Music Research, 42(3):223–235, 2013.

[7] M. Goto. Aist annotation for the RWC music database.
In ISMIR, pages 359–360, 2006.

[22] H. Riemann. Harmony Simplified: or, The Theory of
the Tonal Functions of Chords. Augener, 1896.

[8] M. Goto, H. Hashiguchi, T. Nishimura, and R. Oka.
RWC music database: Popular, classical and jazz music databases. In ISMIR, volume 2, pages 287–288,
2002.

[23] M. Rohrmeier. Mathematical and computational approaches to music theory, analysis, composition andperformance. Journal of Mathematics and Music,
5(1):35–53, 2011.

[9] R. Groves. Automatic harmonization using a hidden
semi-Markov model. In Proceedings of the Artificial Intelligence and Interactive Digital Entertainment
Conference (Boston, MA), pages 48–54, 2013.

[24] R. Scholz, E. Vincent, and F. Bimbot. Robust modeling of musical chord sequences using probablistic Ngrams. In IEEE ICASSP, pages 53–56, 2009.

[10] M. Hamanaka, K. Hirata, and S. Tojo. Implementing‘A generative theory of tonal music’. Journal of New
Music Research, 35(4):249–277, 2006.
[11] M. Hamanaka, K. Hirata, and S. Tojo. Musical structural analysis database based on GTTM. In ISMIR,
pages 325–330, 2014.
[12] M. Johnson, T. L. Griffiths, and S. Goldwater. Bayesianinference for PCFGs via Markov chain Monte Carlo. In
North American Chapter of the Association for Computational Linguistics Human Language Technologies(NAACL-HLT), pages 139–146, 2007.
[13] F. Lerdahl and R. Jackendoff. A Generative Theory ofTonal Music. MIT press, 1985.
[14] W. Maler. Beitrag zur Durmolltonalen Harmonielehre
I (7th ed.). F. E. C. Leuckart, 2007.
[15] E. Nakamura, M. Hamanaka, K. Hirata, and K. Yoshii.
Tree-structured probabilistic model of monophonicwritten music based on the generative theory of tonal
music. In IEEE ICASSP, pages 276–280, 2016.

[25] I. Simon, D. Morris, and S. Basu. Mysong: automatic
accompaniment generation for vocal melodies. In Proceedings of the SIGCHI Conference on Human Factors
in Computing Systems, pages 725–734. ACM, 2008.
[26] J. B. L. Smith, J. A. Burgoyne, I. Fujinaga, D. D.
Roure, and J. S. Downie. Design and creation of alarge-scale database of structural annotations. In ISMIR, pages 555–560, 2011.
[27] M. J. Steedman. A generative grammar for jazz chord
sequence. Music Perception, 2(1):52–77, 1984.
[28] M. Towsey, A. Brown, S. Wright, and J. Diederich. Towards melodic extension using genetic algorithms. Educational Technology & Society, 4(2):54–65, 2001.
[29] K. Yoshii and M. Goto. A vocabulary-free infinitygram model for nonparametric bayesian chord progression analysis. In ISMIR, pages 645–650, 2011.