INTERACTIVE ARRANGEMENT OF CHORDS AND MELODIESBASED ON A TREE-STRUCTURED GENERATIVE MODEL
Hiroaki Tsushima
Eita Nakamura
Katsutoshi Itoyama
Kazuyoshi Yoshii
Graduate School of Informatics, Kyoto University, Japan{tsushima, enakamura}@sap.ist.i.kyoto-u.ac.jp, {itoyama, yoshii}@kuis.kyoto-u.ac.jp

ABSTRACTWe describe an interactive music composition system thatassists a user in refining chords and melodies by generating chords for melodies (harmonization) and vice versa(melodization). Since these two tasks have been dealt withindependently, it is difficult to jointly estimate chords andmelodies that are optimal in both tasks. Another problem
is developing an interactive GUI that enables a user to partially update chords and melodies by considering the latent tree structure of music. To solve these problems, we
propose a hierarchical generative model consisting of (1) aprobabilistic context-free grammar (PCFG) for chord symbols, (2) a metrical Markov model for chord boundaries,(3) a Markov model for melody pitches, and (4) a metrical Markov model for melody onsets. The harmonic functions (syntactic roles) and repetitive structure of chords arelearned by the PCFG. Any variables specified by a user canbe optimized or sampled in a principled manner according
to a unified posterior distribution. For improved melodization, a long short-term memory (LSTM) network can also
be used. The subjective experimental result showed the effectiveness of the proposed system.
1. INTRODUCTION
Music composition is a highly intelligent task that has been
considered to be done only by musically trained people.
To help musically untrained people create their own musical pieces, automatic music composition has actively beenstudied (e.g., [4, 8, 19, 31]). While conventional studies
have aimed at full automation of music composition, inthe process of music composition, melodies (sequences ofmusical notes) and chord sequences are partially and incrementally refined by trial and error until the resulting musical piece has musically appropriate structure. Our aim is todevelop an interactive arrangement system that can assist
unskillful people to take such a process for reflecting theirpreference in creating melodies and chord sequences.
It is non-trivial to reflect user’s preference to a musicalpiece in a consistent and unified framework of statisticalc Hiroaki Tsushima, Katsutoshi Itoyama, Eita Nakamura,⃝Kazuyoshi Yoshii. Licensed under a Creative Commons Attribution 4.0
International License (CC BY 4.0). Attribution: Hiroaki Tsushima,
Katsutoshi Itoyama, Eita Nakamura, Kazuyoshi Yoshii. “An Interactive
System for Generating Chords and Melodies Based on a Tree-Structured
Model”, 19th International Society for Music Information Retrieval Conference, Paris, France, 2018.

Figure 1: Our interactive music arrangement system basedon a tree-structured generative model.
modeling. This problem is hard to solve especially when ablack-box method (e.g., neural end-to-end learning) is used
for music generation. To incrementally refine a musicalpiece, one may iteratively use a harmonization method forgenerating a chord sequence from a melody [4, 19, 24, 28]
and a melodization method for generating a melody from achord sequence [3,7,8,15,22,30,31]. This approach, however, cannot enable a user to partially and incrementally refine melodies and chords in consideration of the optimalityof the whole musical piece because each task has a uniqueevaluation criterion.
Since music is typically well-characterized by chords
and melodies, it is important to be aware of complicatedstructures within and between chords and melodies. when
composing a musical piece. To generate a musically appropriate sequence of chords, the harmonic functions ofchords, which typically consist of three categories, i.e.,
tonic (T), dominant (D), and subdominant (SD), should
be considered because such functions represent syntacticroles in the same way as parts of speech in written texts. In
addition, a sequence of harmonic functions of chords has atree structure [21, 26]. For example, a chord sequence (C,Dm, G, Am, C, F, G, C) can be interpreted as (((T, SD),
(D, T)), ((T, SD), (D, T))), where subtrees such as (T, SD),
(D, T), and ((T, SD), (D, T)) appear repeatedly in a hierarchical manner. Therefore, it is desirable to consider suchthe hierarchical tree structure of chord sequences when wecomputationally help people to create a new music.
In this paper we propose an interactive music arrangement system that enables musically untrained users to create a melody and a chord sequence (Fig. 1). To partiallyand incrementally refine the piece, users can choose several types of operations that are often exploited by musically trained people. Specifically, the entire chord se-

145

146

Proceedings of the 19th ISMIR Conference, Paris, France, September 23-27, 2018quence and the corresponding tree structure can be refined
jointly for a melody; the onset time of a specified chord canbe refined; two adjacent chords forming a subtree can bemerged into a single chord or a chord can be split into twochords; and melody notes in the region of a specified chord
can be refined. All a user needs to do is to specify where
to update the piece and it is not necessary to manually edit
individual musical elements.
To optimize a chord sequence and a melody in a unified
criterion, we propose a tree-structured hierarchical generative model that consists of (i) a probabilistic contextfree grammar (PCFG) generating chord symbols [28], (ii) a
metrical Markov model generating chord rhythms, and (iii)a Markov model generating melody pitches conditionallyon the chord sequence, and (iv) a metrical Markov model
generating melody rhythms (Fig. 2). The rule probabilities of the PCFG are learned from chord sequences, withthe expectation that the syntactic roles of chords are captured by the non-terminal symbols [29]. The other models are also learned from chord and/or note sequences. To
improve the melodization process, a long short-term memory (LSTM) network can be used instead of the Markov
models (iii) and (iv) for capturing the long-term characteristic of a melody. Using the generative model trained inadvance, we can estimate any “missing” variables, i.e., an
unpleasant part of chords or musical notes specified by theuser, in a statistical manner.
The major contribution of this study is the realization ofa directability-aware music composition/arrangement system based on a unified probabilistic model. This systemprovides a user with an easy-to-use GUI that shows otherpossibilities for an unpleasant part of the piece and all operations on the GUI are implemented as posterior inference
based on the probabilistic model. Our contribution lies in
the marriage of AI and human creativity.
2. RELATED WORKThis section reviews related studies on automatic harmonization and melodization.
2.1 Automatic Harmonization
Many studies have been conducted for automatic harmonization for given melodies. Some studies aim to generate a sequence of chord symbols (as in this paper), andothers aim to generate several (typically four) voices ofmusical notes. In the former type of research, Chuan and
Chew [4] proposed a method consisting of three processes:
selecting musical notes that might form chords from given
melodies with a support vector machine (SVM), constructing triad chords from the selected notes, and generating
chord progressions by using a rule-base method. Simon
et al. [24] proposed a commercial system MySong basedon hidden Markov models (HMMs) with Markovian chordtransitions. Raczyński et al. [20] proposed similar Markov
models in which chords are conditioned by melodies andtime-varying keys. Tsushima et al. [28] proposed a harmonization method that considers the hierarchical repetitive structure of sequences of chord symbols obtained by

1SPCBCJMJTUJDDPOUFYUGSFFHSBNNBS 1$'(GPSDIPSETZNCPMT

$

'

"N

(

.FUSJDBM.BSLPWNPEFM
GPSDIPSEPOTFUT.FUSJDBM.BSLPWNPEFMGPSNFMPEZPOTFUT.BSLPWNPEFMGPSNFMPEZQJUDIFT

$

4
4

"N

'



(



Figure 2: A tree-structured hierarchical generative model
for chord symbols and melodies.
PCFGs and pitch transitions conditioned by chord symbols
with Markov models. De Prisco et al. [19] proposed a harmonization method for only a base line of the input witha distinctive network that models the dependencies amongbass notes, the previous chord, and the current chord.
In the latter type of research, Ebcioğlu [6] proposeda rule-based method for generating four-part chorales in
Bach’s style. Several methods of using variants of genetic
algorithms (GAs) based on music theories have also been
proposed [17, 18, 27]. Allan and Williams [2] proposed
an HMM-based method that represents chords as hidden
states and musical notes as observed outputs. A hidden
semi-Markov model (HSMM) [11] has been used for explicitly representing the durations of chords. Paiement etal. [16] proposed a hierarchical tree-structured model that
describes chord movements from the viewpoint of hierarchical time scales by dividing the notations of chords. To
generate highly convicting four-part chorales, a deep recurrent neural network has also been used for capturing thelong-term characteristic of a melody and a harmony [12].
2.2 Automatic Melodization
There have been many studies on automatic melodization[3,8,15,22,30,31]. Fukayama et al. [8] developed a system
named Orpheus that generates a melody for a given lyric
in a way that the prosody of the lyric matches the dynamics of the melody. Roig et al. [22] proposed a method ofgenerating a monophonic melody by using a probabilistic
model of rhythm patterns and pitch contours.
Recent studies have applied deep learning techniques.
In Magenta project [30], for example, recurrent neural networks (RNNs) are used for learning long-term dependencyof music. Yang et al. [31] proposed a novel method forgenerating diverse monophonic melodies by combining agenerative adversarial network (GAN) with a convolutional
neural network (CNN). To generate diverse melodies, Mogren [15] proposed adversarial training of an RNN thatworks on continuous sequential data. The method basedon a restricted Boltzmann machine (RBM) conditioned on
RNNs that models temporal dependency has been proposedto generate polyphonic music [3]. In addition, Eck et al. [7]have proposed an LSTM-based method for generating both
melodies and chords by capturing the characteristic of noteby-note transitions and the mutual dependency between
musical notes and chord symbols.

Proceedings of the 19th ISMIR Conference, Paris, France, September 23-27, 2018147

3. USER INTERFACE
The proposed system, which is implemented as a web service based on HTML5, enables a user to incrementally refine a chord sequence and a melody on a GUI (Fig. 1). To
use a system, a user is asked to upload a melody of eightbars. The system then estimates a chord sequence that harmonizes with the melody. The chord onsets are located at
the bar lines. Supported arrangement operations are:• Updating the chord symbols: The chord symbols
and the latent tree structure behind the chord symbols are jointly optimized for the current melody.
• Updating a chord onset: One of the chord onsets(boundaries) specified by a user is optimized.
• Splitting a chord: One of the chords specified by auser is split into two adjacent chords.
• Merging chords: Two adjacent chords that form asubtree are merged into a single chord.
• Updating the melody: Melody notes in the regionof a chord specified by a user are updated while keeping consistency with neighboring measures.
4. PROBABILISTIC MODELINGThis section explains a unified probabilistic model that represents the hierarchical generative process of a chord sequence and a melody. The proposed model consists of four
sub-models, which are trained independently.
4.1 Mathematical Notation

!""

!"
!"#%

!""

!"#$

'"

!""

!""
'"#%
!""

!""
!""

'"#$

!""

GVMMZDPOOFDUFE
MBZFS

!""

!""

GVMMZDPOOFDUFE-45.MBZFS

!""
!""
!"#%

!"&%

!"

!""

Figure 3: Configuration of the LSTM network
by a set of non-terminal symbols V that are expected torepresent the hierarchical structure and syntactic roles ofchords, a set of terminal symbols (chord symbols) Σ, a
set of rule probabilities R, and a start symbol S (a nonterminal symbol located on the root of a syntax tree). There
are three types of rule probabilities. θA→BC is the probability that a non-terminal symbol A ∈ V branches to
non-terminal symbols B ∈ V and C ∈ V . ηA→α is theprobability that A ∈ V emits terminal symbol α ∈ Σ. A
non-terminal symbol A ∈ V emits a terminal symbol witha probability of 0 < λA < 1 and otherwise it branches.
These probabilities are normalized as follows:∑∑
θA→BC = 1,
ηA→α = 1.
(1)
B,C∈V

α∈Σ

We let θ A = {θA→BC }B,C∈V and η A = {ηA→α }α∈Σ .
4.2.2 Metrical Markov Models for ϕ and ψ
The metrical Markov model for chord onsets ϕ on the regular 16th-note-level grid is defined byp(ϕn |ϕn−1 ) = πϕn−1 mod16,ϕn −ϕn−1 ,(2)

We assume that chord and melody onsets are on the 16thnote-level grid. Let L be the number of measures of a musical piece (L = 8 in this paper) and T = 16L be thetotal number of time units. A sequence of chord symbols
Nand that of chord onsets are denoted by z = {zn }n=1N
and ϕ = {ϕn }n=1 , respectively, where N is the numberof chords and ϕn takes an integer in [0, T ). Similarly, asequence of melody pitches and that of melody onsets innthe region of chord zn is denoted by pn = {pn,i }Ii=1andnψ n = {ψn,i }Ii=1, respectively, where In is the number ofmusical notes in that time span, pn,i is a MIDI note number from 32 to 93, and ψn,i takes an integer in [ϕn , ϕn+1 ).
N
The whole melody is denoted by p = {pn }n=1 and ψ =∑N{ψ n }N
n=1 , where I =n=1 In is the number of melody
notes.
Let t be a latent tree that derives z according to a PCFG
and tm:n be an inside part (subtree) of t that derives zm:n .
Thus t = t1:N . We often use tm:n to indicate the root nodeof the subtree for simplicity. Let t¬m:n be an outside partof t that derives z1:m−1 , tm:n , and zn+1:N .

where ρa,b indicates the probability that a musical note
starts at the a-th position in a measure (0 ≤ a < 16) andcontinues for the duration of b time units (0 < b ≤ T ).

4.2 Model Formulation

4.2.4 Bayesian Integration of Four Sub-models

We formulate a unified probabilistic model that represents
the generative process of a latent tree t, chord symbols z,
chord onsets ϕ, melody pitches p, and melody onsets ψ.

Letting Ω = {t, z, ϕ, p, ψ} be a set of the external randomvariables and Θ = {θ, η, λ, π, ρ, τ } be a set of the model
parameters, the unified model is given by

4.2.1 Probabilistic Context-Free Grammar for t and zp(Ω, Θ) = p(t, z|θ, η, λ)p(ϕ|π)p(ψ|τ )p(p|z)p(Θ), (6)A derivation tree t and chord symbols z are generated inthis order according to a PCFG G = (V, Σ, R, S), definedwhere p(Θ) = p(θ)p(η)p(λ)p(π)p(ρ)p(τ ) is a prior distribution over Θ. To make Bayesian inference tractable,

where πa,b indicates the probability that a chord starting at
the a-th position in a measure (0 ≤ a < 16) continues forthe duration of b time units (0 < b ≤ T ).
A similar model for melody onsets ψ is defined byp(ψn,1 |ψn−1,In−1 ) = ρψn−1,In−1 mod16,ψn,1 −ψn−1,In−1 ,p(ψn,i |ψn,i−1 ) = ρψn,i−1 mod16,ψn,i −ψn,i−1 (1 < i), (3)4.2.3 Markov Model for p Conditioned on z
The Markov model for melody pitches p conditioned by achord sequence given by z is defined bynp(pn,1 |pn−1,In−1 , zn ) = τpzn−1,I

n−1,pn,1 ,np(pn,i |pn,i−1 , zn ) = τpzn,i−1,pn,i (2 ≤ i ≤ In ),

(4)
(5)

c
where τa,b
is the transition probability from pitch a to pitchb under chord symbol c.

148

Proceedings of the 19th ISMIR Conference, Paris, France, September 23-27, 2018
we use conjugate Dirichlet and beta priors as follows:(7)

π a ∼ Dir(β a ), ρa ∼ Dir(γ a ), τ ca ∼ Dir(δ ca ),(8)

4QMJUBDIPSE%"

where ξ A , ζ A , ιA , β a , γ a , and δ ca are hyperparameters.
4.2.5 LSTM Network for x Conditioned on c
In melody arrangement, we can also use an LSTM modelthat can learn complicated long-term dynamics of melodies.
Let x = {xt }Tt=1 be another representation of the entire
melody, where xt takes a MIDI note number at the t-th
position (0 ≤ t < T ) if the note onset is at that positionand otherwise takes 0. Let c = {ct }Tt=1 be another representation of the entire chord sequence given by z andϕ, where ct indicates a chord symbol at the t-th position.
Given a sequence of musical notes x1:t = {xi }ti=1 andthat of chord symbols c1:t = {ci }ti=1 , the LSTM model
determines the probability of the next musical note givenby p(xt+1 |x1:t , c1:t ) (Fig. 3).
4.3 Model Training
Our goal is to obtain the maximum a posteriori (MAP) estimates of the model parameters Θ = {θ, η, λ, π, ρ, τ }.
To estimate the parameters θ, η, and λ of the PCFG froma chord sequence z (multiple sequences are used in practice) in an unsupervised manner, we use an inside-filteringoutside-sampling algorithm [13,28] for generating samples
from the true posterior distribution p(θ, η, λ, t|z). Morespecifically, the latent tree t and the parameters θ, η, and λare alternately sampled from the conditional posterior distributions p(t|θ, η, λ, z) and p(θ, η, λ|t, z), respectively.
The parameters π, τ and ρ of the Markov models arelearned independently. Given a sequence of chord onsets ϕand a sequence of melody onsets ψ, the posterior distribution of π and that of ρ can be calculated, respectively, because of the conjugacy between the Dirichlet and categorical distributions. Similarly, given a sequence of melody
pitches p associated with a chord sequence specified by z
and ϕ, the posterior distribution of τ can be calculated.
The LSTM network is also trained from the same data.
5. CHORD AND MELODY ARRANGEMENT
This section explains how to leverage the unified model described in Section 4 for implementing the five operations
described in Section 3. Let Ω = {t, z, ϕ, p, ψ} be a setof random variables. To estimate a “missing” part χ ⊂ Ω,
we take a principled statistical approach based on the conditional posterior distribution p(χ|Ω¬χ , Θ), where A¬B
indicates a subset of A obtained by removing the elementsof B from A. Note that full automatic music composition
can be achieved by sampling Ω from p(Ω|Θ).
5.1 Updating the Chord Symbols
When the melody pitches p are fixed, the chord symbols z
and the latent tree t can be optimized by maximizing theconditional posterior distribution p(t, z|p, Θ). Since botht and z are latent variables in this operation, we extend theViterbi algorithm to infer t and z from p. First, the inside

'"

'"()

'"

!"#"()!"#"()!"#"!"#"

θ A ∼ Dir(ξ A ), η A ∼ Dir(ζ A ), λA ∼ Beta(ιA ),.FSHFDIPSET
!"$

!"&

!"#"

!*+,#*+,

%"$

%"&

%"

%"()

' '"()'"'"()'"(-

%

'"

'"(-

Figure 4: Split and merge operations.
probabilities are recursively calculated from the layer ofterminal symbols z to the start symbol S according topA
n,n = λA max ηA→z p(pn |z),
z∈Σ

(9)

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

where p(pn |zn ) is the probability that a pitch subsequencepn is generated conditionally on chord zn :p(pn |zn ) =In∏p(pn,i |pn,i−1 , zn ),

(11)

i=1

where pn,0 = pn−1,In−1 . The most likely t and z are obtained by recursively back-tracking the most likely paths
from the start symbol S.
5.2 Updating a Chord Onset
When the melody pitches p and the melody onsets ψ aregiven and the chord symbols z are fixed, a chord onset ϕncan be optimized by maximizing the conditional posterior
distribution given byp(ϕn |z, ϕ¬n , p, ψ, Θ)∝ p(pn−1 |zn−1 )p(pn |zn )p(ϕn |ϕn−1 )p(ϕn+1 |ϕn ), (12)where ϕn is restricted such that ψn−1,1 ≤ ϕ ≤ ψn,In .
5.3 Splitting a Chord and Merging Chords
The chord symbols z and the chord onsets ϕ can be locallyrefined by splitting a chord into adjacent chords or merging
adjacent chords into another chord (Fig. 4). A subtree of t
is updated accordingly. The split operation can be applied
to any chord zn while the merge operation is restricted toadjacent chords zn:n+1 forming a subtree tn:n+1 .
A chord zn associated with a non-terminal symbol tn:n
is split at a 16th-note-level position ϕ into two new chords
RznL and znR associated with two new symbols tLn and tn
by maximizing the conditional posterior distribution given
R L R
by p(tLn , tn , zn , zn , ϕ|t¬n:n , z ¬n , ϕ, p, ψ, Θ). This operation makes a new subtree that has tn:n as its root node,
R
L
R
derives tLn and tn , and generates zn and zn . To do this, we
use the extended Viterbi algorithm for estimating the most
likely subtree from pn . First, the inside probabilities arerecursively calculated from the layer of terminal symbols
znL and znR to the root node tn:n according to
αϕA = λA max ηA→z p(pL
n |z, ϕ),(13)

βϕA = λA max ηA→z p(pR
n |z, ϕ),

(14)

z∈Σ
z∈Σ

ptϕn:n = max θtn:n →BC αϕB βϕC p(ϕ|ϕn )p(ϕn+1 |ϕ), (15)B,C∈V

Proceedings of the 19th ISMIR Conference, Paris, France, September 23-27, 2018
R
where pLn and pn are the subsequences of pitches obtainedby splitting pn with a boundary ϕ. The most likely znL , znR ,RtLn , tn , and ϕ are obtained by recursively back-tracking themost likely paths from tn:n .
Two adjacent chords zn and zn+1 associated with nonterminal symbols tn:n and tn+1:n+1 are merged into a single chord z associated with a non-terminal symbol tn:n+1
by maximizing the conditional posterior distribution givenby p(z|t¬n:n+1 , z ¬n:n+1 , ϕ¬n+1 , p, ψ, Θ). The most likely
z is obtained as follows:z = arg max ηtn:n+1 →z′ p(pn |z ′ )p(pn+1 |z ′ ).
z ′ ∈Σ

(16)

5.4 Updating the Melody
When a chord symbol zn , the last pitch pn−1,In−1 in the region of the previous chord zn−1 , and the first pitch pn+1,1
in the region of the next chord zn+1 are given, a sequenceof musical notes in the region of zn (between ϕn and ϕn+1 )is obtained by maximizing the conditional posterior distribution p(pn |zn , pn−1,In−1 , pn+1,1 , Θ). To do this, we
propose an efficient algorithm based on dynamic programming. Let αyt ,dt be the marginal likelihood that a note at
the pitch yt is located on the score time t and the durationof the previous note is dt on a chord zn :αyt ,dt = p(yt , dt |zn )(17)This probability can be calculated recursively in the scoretime t ∈ {ϕn , ..., ϕn+1 , ψn+1,1 }.
∑nαyt ,dt = ρt−dt ,tαyt−dt ,dt−dt τyzt−dt ,yt
yt−dt , dt−dt

In each score time t, dt can take values in {1, ..., t, t −ψn−1,In−1 }. By using this probability, we can recursively
sample pn from the beat score time ψn+1,1 to ψn−1,In−1 .
Another improved way of partially updating the melody
is to use the LSTM model. Suppose that we aim to update
xi:j in the whole melody x. Given a chord sequence c
and melody segments x1:i−1 and xj+1:T , the missing partxi:j can be sampled from the conditional posterior distribution p(xi:j |c, x1:i−1 , xj+1:T ) ∝ p(x|c). First, the pitches
x1:i−1 and chords c1:i−1 are fed to the network to update
the hidden states. The missing part xi:j is then sampled
sequentially according to the probability p(xt+1 |x1:t , c1:t )learned by the LSTM. This enables us to evaluate p(x|c).
Among a sufficient number of generated samples of x1:i−1 ,a sample with the highest p(x|c) is selected.
6. EVALUATIONThis section reports objective and subjective evaluations on
the user interface and the music arrangement method.
6.1 Experimental Conditions
To train the PCFG, we used 705 chord sequences of musical sections (e.g., verse, bridge, and chorus) from 468
pieces of popular music included in the SALAMI dataset[25]. Only chord sequences with a length between 8 and
32 measures were chosen. The vocabulary of chord symbols was limited to the combinations of the 12 root notes{C, C#, ..., B} and the 2 chord types {major, minor}. The

149

number of kinds of non-terminal symbols of the PCFG was
set to 12. The values of the hyperparameter ιA were all set
to 1.0 and those of the other parameters were all set to 0.1.
To train the three Markov models, we used 9902 pairs of
melodies and the corresponding chord sequences from 194
pieces of popular music included in Rock Corpus [5]. To
train the LSTM, we used 9265 melodies associated withchord sequences from pieces of popular music included inRock Corpus and Nottingham Database [1]. Note that allof the data used in our experiments were transposed to the
C major or C minor key. The number of the hidden units
was 50 and the softmax-cross-entropy was used as a loss
function. The parameters of the LSTM were optimized byusing Adam [14]. The number of samples generated by the
LSTM (described in Section 5.4) was 50.
6.2 Objective Evaluation of Melody Arrangement
We evaluated the function of updating a melody in termsof the note density of the generated musical notes via 10fold cross validation on the Rock Corpus and Nottingham
Database. For the region of each chord zn , a sequence of
melody pn is arranged by using the two methods based on
the Markov model and the LSTM described in Section 5.4.
We measured the mean squared error (MSE) between thenote density per measure of the generated musical notes
and the mean value of the density of other regions given
by
∑
}2
N−1{
1 ∑
16In∗
m̸=n 16Im
MSE =
−∑
,
N −1 n=1 ϕn+1 −ϕnm̸=n (ϕm+1 −ϕm )where In∗ and In were the number of generated musicalnotes and that of the original musical notes, respectively.
The average MSE was calculated over all melodies. The
average MSE obtained by the LSTM model was 5.52 whilethat obtained by the Markov model was 6.42. This indicates that the LSTM-based method is a little more effective for updating a partial melody in consideration of thenote density of the whole melody because it can capture
the long-term dependency.
6.3 Subjective Evaluation of the Proposed System
We conducted the subjective evaluation of the system1 interms of usability and effectiveness in interactive chord andmelody arrangement. Five melodies of 8 measures wereextracted from the RWC music database [9, 10]. We asked
11 subjects to test our system. Four subjects who had
the experience of playing musical instruments for morethan five years were regarded as people with musical backgrounds. Each subject was asked to interactively make amusical piece by using each of the five melodies as an initial seed and then grade the system on a 5-point Likert scale(from “strongly agree (1)” to “strongly disagree (5)”) interms of the following 15 criteria:• The chord sequences obtained were suitable for the
melodies (I).
• The chord sequences obtained by the split or merge
operation were musically natural (II, III).
1 The interface used in this experiment is available online:
http://sap.ist.i.kyoto-u.ac.jp/members/tsushima/ismir2018/

150

Proceedings of the 19th ISMIR Conference, Paris, France, September 23-27, 2018
)PXOBUVSBM


*

**

***

*7

)PXJOUFSFTUJOH
7

7*

7**

7***

*9

)PXVTFGVM
9 9* 9** 9*** 9*7 97





































$

• The melodies obtained were suitable for the chord sequences (IV).
• The melodies obtained were musically natural (V).
• The musical pieces obtained by updating chord symbols, splitting a chord, merging chords, or updating a
melody were interesting (VI, VII, VIII, IX).
• The function of updating chord symbols, splitting achord, merging chords, or updating a melody was useful (X, XI, XII, XIII, XIV).
• The user interface has the capability of helping users
make musical pieces (XV).
We also asked the subjects to tell us how each of them felt
about the system.
The results of this user study is shown in Fig 5. In termsof the naturalness and the interestingness, the two operations, updating chord symbols and updating melodies, obtained the slightly high mean ratings of 3.67 in criterion (I),3.69 in criterion (IV), and 3.51 in criterion (VI). As seen in
the score for the criterion (V), the subjects with musicalbackgrounds, compared with the others, tended to feel thatthe updated melodies were less musically natural.As seenin the score for the criterion (IX), the subjects with musicalbackgrounds tended to feel that the updated melodies weremore interesting. In terms of the usefulness of each operation, each operation obtained the reasonably high mean
ratings (from 3.27 to 3.91).
We obtained the following opinions on the usability of
our system:• It was interesting that even a user without any experiences in music composition can edit a musical pieceby iterating several operations.
• An operation that updates one chord symbol is necessary for more freely editing a chord sequence.
We also obtained the following opinions on the problemsof some operations:• The chord sequences obtained were almost always appropriate for all samples of melodies but the systemtended to generate only basic chords (e.g., C major).
• The updated melodies were often unnatural when an
original melody has some repeated sections.
The reason for the former problem may be that the chordsymbols are updating by using the Viterbi algorithm. The
reason for the latter problem is probably that the LSTM
cannot capture the global repetitive structure of a melody.

%N

#

$

"N

$

$

%N

#

%N

#

6QEBUFNFMPEZ

6QEBUFNFMPEZ

$

"N

%N

#

"N

%N

#

4QMJU$IPSE

$

$

%N

'

#

$
.FSHF$IPSET$

Figure 5: Results for people with musical backgrounds(top) and those for people without musical backgrounds(bottom). The middle bars indicate the mean value.

$

$

%N

'

#

$

"N

#

Figure 6: Example operation for interactive generation ofchord sequences and melodies.
6.4 Example of Chord and Melody Arrangement
Fig. 6 shows how the proposed method generates chord sequences and melodies. The score (melodies and chords) at
the top shows an initial state in which the chord symbols
were optimized for the melody in the input file (the chord
onsets were located at the bar lines). The second scoreshows the state in which the two regions of the melody under the 3rd and 6th chords were updated in order. The third
chord sequence shows the state in which the 4th chord, B♭
major, was split into F major and B♭ major. The fourthchord sequence shows the state in which the 7th chord, A
minor, and the 8th chord, D minor, were merged into A
minor. This indicates that the proposed method can successfully help a user partially update a melody while keeping the consistency of the whole melody and that it cangenerate a chord sequence by considering the latent tree
structure behind the chord sequence.
7. CONCLUSION
This paper presented an interactive music arrangement system that enables a user to incrementally refine a chord sequence and a melody. The experimental results showedthat the proposed system has a great potential to help auser create his or her original musical pieces.
There would be much room for improving our method.
To improve the diversity of generated chord symbols, theuse of some sampling or beam-search method would be effective. To improve the naturalness of generated melodies,
the use of a bidirectional LSTM [23] would be effective forconsidering the repetitive structures of melodies.
For more specific studies on the effectiveness of our system, we plan to measure how well test users can incrementally refine a musical piece compared with the conventional
methods, by counting the number of necessary operations
to make musical pieces meet their satisfaction. We alsoplan to conduct large-scale user studies of the system on
the Web. Collecting time-series data of users’ operations
and created pieces, it would be possible to infer their musical preference and improve the model by reinforcement
learning. Using the same data, it would be possible to reveal the process of music creation by humans in terms ofedit operations and optimization strategies.
Acknowledgements: This study was partially supported by JST ACCEL
No. JPMJAC1602, JSPS KAKENHI No. 26700020 and No. 16H01744,
and Grant-in-Aid for JSPS Research Fellow No. 16J05486.

Proceedings of the 19th ISMIR Conference, Paris, France, September 23-27, 2018
8. REFERENCES[1] ABC version of the Nottingham music database.
http://abc.sourceforge.net/NMD/.
[2] M. Allan and C. Williams. Harmonising chorales by
probabilistic inference. In NIPS, pages 25–32, 2005.
[3] N. Boulanger-Lewandowski, Y. Bengio, and P. Vincent. Modeling temporal dependencies in highdimensional sequences: Application to polyphonicmusic generation and transcription. In ICML, 2012.
[4] C. H. Chuan and E. Chew. A hybrid system for automatic generation of style-specific accompaniment. In
IJWCC, pages 57–64, 2007.
[5] T. D. Clercq and D. Temperley. A corpus analysis ofrock harmony. Popular Music, 30(01):47–70, 2011.
[6] K. Ebcioğlu. An expert system for harmonizing fourpart chorales. Computer Music Journal, 12(3):43–51,
1988.
[7] D. Eck and J. Schmidhuber. A first look at music composition using LSTM recurrent neural networks. IDSIA, 103(07-02), 2002.
[8] S. Fukayama et al. Orpheus: Automatic composition system considering prosody of Japanese lyrics. In
ICMC, pages 309–310. Springer, 2009.
[9] M. Goto. AIST annotation for the RWC music
database. In ISMIR, pages 359–360, 2006.
[10] M. Goto, H. Hashiguchi, T. Nishimura, and R. Oka.
RWC music database: Popular, classical and jazz music databases. In ISMIR, pages 287–288, 2002.
[11] R. Groves. Automatic harmonization using a hidden
semi-Markov model. In AIIDE, pages 48–54, 2013.
[12] G. Hadjeres and F. Pachet. DeepBach: A steerable
model for Bach chorales generation. In ICML, pages
1362–1371, 2017.
[13] M. Johnson, T. L. Griffiths, and S. Goldwater. Bayesianinference for PCFGs via Markov chain Monte Carlo. In
NAACL-HLT, pages 139–146, 2007.
[14] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICMR, pages 1–15, 2014.
[15] O. Mogren. C-RNN-GAN: Continuous recurrent neural networks with adversarial training. In Constructive
Machine Learning Workshop (NIPS 2016), 2016.
[16] J. F. Paiement, D. Eck, and S. Bengio. Probabilistic melodic harmonization. In CSCSI, pages 218–229,
2006.
[17] 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.

151[18] R. D. Prisco and R. Zaccagnino. An evolutionary music composer algorithm for bass harmonization. In Applications of Evolutionary Computing, pages 567–572.
Springer, 2009.
[19] R. De Prisco, A. Eletto, A. Torre, and R. Zaccagnino.
A neural network for bass functional harmonization.
In European Conference on the Applications of Evolutionary Computation, pages 351–360. Springer, 2010.
[20] 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.
[21] M. Rohrmeier. Mathematical and computational approaches to music theory, analysis, composition andperformance. Journal of Mathematics and Music,
5(1):35–53, 2011.
[22] C. Roig, L. J. Tardón, T. Barbancho, and A. M. Barbancho. Automatic melody composition based on aprobabilistic model of music style and harmonic rules.
Knowledge-Based Systems, 71:419–434, 2014.
[23] M. Schuster and K. K. Paliwal. Bidirectional recurrent
neural networks. IEEE Transactions on Signal Processing, 45(11):2673–2681, 1997.
[24] I. Simon, D. Morris, and S. Basu. Mysong: automatic accompaniment generation for vocal melodies.
In SIGCHI Conference on Human Factors in Computing Systems, pages 725–734. ACM, 2008.
[25] 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.
[26] M. J. Steedman. A generative grammar for jazz chord
sequence. Music Perception, 2(1):52–77, 1984.
[27] M. Towsey, A. Brown, S. Wright, and J. Diederich. Towards melodic extension using genetic algorithms. Educational Technology & Society, 4(2):54–65, 2001.
[28] H. Tsushima, E. Nakamura, K. Itoyama, and K. Yoshii.
Function- and rhythm-aware melody harmonization
based on tree-structured parsing and split-merge sampling of chord sequences. In ISMIR, pages 502–508,
2017.
[29] H. Tsushima, E. Nakamura, K. Itoyama, and K. Yoshii.
Generative statistical models with self-emergent grammar of chord sequences. Journal of New Music Research, 2018. To appear.
[30] E. Waite. Generating long-term structure in songs
and stories. https://magenta.tensorflow.org/2016/07/
15/lookback-rnn-attention-rnn.
[31] L. C. Yang, S. Y. Chou, and Y. H. Yang. MidiNet:
A convolutional generative adversarial network forsymbolic-domain music generation. In ISMIR, pages
324–331, 2017.