USE OF DECISIO TREE TO DETECT GTTM GROUP BOU DARIES
Yuji Miura, Masatoshi Hamanaka
University of Tsukuba
yuji@music.iit.tsukuba.ac.jp, hamanaka@iit.tsukuba.ac.jp
Keiji Hirata

Satoshi Tojo

NTT Communication Science
Laboratories
hirata@brl.ntt.co.jp

Japan Advanced Institute of
Science and Technology
tojo@jaist.ac.jp

ABSTRACTWe describe σGTTM that combines the generative theoryof tonal music (GTTM) and statistical learning. We
previously devised exGTTM, which has accommodated
the original GTTM to computer implementations. The
exGTTM has adjustable parameters, these parameters haveto be manually configured. Therefore, it is not perfectly
suited for automation. To make complete automation
possible, we combined statistical learning with GTTM tocreate σGTTM. To prevent the sparseness problem, weabstracted data properly by using the GTTM rules foranalyzing musical structures. We use the abstracted data toconstruct a decision tree, which is a model of decisions andtheir possible consequences. With σGTTM, we cansegment a melody automatically from the decision tree,
dependent on conditional probability. Experimental results
showed that σGTTM outperformed the baseline exGTTM.
1. I TRODUCTIOThe goal of our research is to develop a music system thatcan be used to output musical expressions in accordancewith the intention of a novice composer. Since current
music sequencers operate only on surface structure ofmusic such as notes and rests, they are not truly helpful for
novice composers. However, if deeper musical structures,such as the melody, rhythm, and harmony, could be
automatically analyzed on a computer, it would become
possible for musical novices to produce advanced musicalexpressions. Our research has the goal of automating music
structural analysis. For this, we have developed σGTTM,
which combines a music theory called the generative
theory of tonal music (GTTM) [5] with statistical learning.
Here, we show that σGTTM can be used to segment a
melody, the function that is the foundation of the structural
analysis of music.
Our method statistically learns the relationship between
an input score and an output melody segmentation.
However, if we were to deal with a score as it is, thenumber of the combinations of training data would be verylarge. For example, the pitch, length, etc., of each note aredescribed as absolute values. For this reason, it is possiblethat the pitches or lengths that are only slightly different
will be learned as completely different data. This leads to asparseness problem; the occurrence probabilities ofcombinations not in the training data are set to zero. To
avoid combinations outside the training data being set tozero, we abstracted training data by using GTTM. By
statistically learning the abstracted training data, themelody segmentation process can be automated.
2. RELATED WORKSMusic theory provides us with methodologies foranalyzing and transcribing musical knowledge, experiences,and skills from a musician’s way of thinking. Unlike othermusic theories [2, 6, 10], GTTM is based on structural
rules which clarify the relation in parts of a piece andpresent the whole organization in detail. Thus, we regard
the theory an adequate computational model of music.
GTTM is composed of four modules, each of whichassigns a separate structural description to a listener’s
understanding of a piece of music. These four modules
output a grouping structure, a metrical structure, a timespan tree, and a prolongational tree, respectively (Figure 1).
The detection of local grouping boundaries in the grouping
structure corresponds to melody segmentation. Whenpotential local grouping boundaries are detected, grouping
preference rules (GPRs 1, 2, and 3) are used for choosing
the most appropriate one [5]. Although GPRs indicate thesuperiority of one structure over another, in practice it is
known that there is a problem with conflict between rules.
Hamanaka developed exGTTM, an extended GTTM
that is suitable for computer implementation [3]. exGTTM
is premised on the data that any musical piece has morethan one correct musical interpretation, and it uses
parameters to eliminate as many ambiguities as possible.
The automatic time-span tree analyzer (ATTA) [3] wasalso developed to solve the conflict between rules.

Statistical learning
SparsenessproblemTime-span tree

Decision tree
B2na

1

…

Inappropriate
learning

GTTM

1

B2nb

0

1

0

B2na+1
0

B3nd

1

0

1

0

0

1

End Node
n −1
2b

B

1

n
3d

B

n−1
3c

B
0

1

B3nc

0

…

…

…

…
…

0

…

§3.2

b=0

1

…

b=0

GPR

B2nb

1

B3nc−1

b =1

…

・
・
・・
・
・
・
・
・
・

・
・
・・
・
・
・
・
・
・

Metrical structure

§3.3

0

Splitting Test

Score data

Abstraction

Grouping structure

B2na , B2nb ,⋅ ⋅ ⋅Abstracted
data

Local grouping boundary

Figure 1. Grouping structure, metrical structure, and timespan tree.

Conditional
Conditional
Conditional
Probability
Conditional
Probability
Probability
probability

Appropriate
learning§3.1

Conflict between rules

GPR1 analysis§3.4

However, ATTA needs a difficult manual configuration offifteen parameters. The full automatic time-span tree
analyzer (FATTA) can automatically estimate the optimal
parameters on the basis of the stability of the time-spantree [4]. However, FATTA is not able to outperform themanual configuration of ATTA; because there are so many
parameters and also many of them are dependent eachother, we cannot optimize them easily.
Conventional melody segmentation methods such asGrouper of the Melisma Music Analyzer by Temperly [11],LBDM by Cambouropoulos [1] require the user to makemanual adjustments to the parameters, and hence are notcompletely automatic. Although Temperly [12] has also
employed probabilistic model, it was not applied for
melody segmentation. The unsupervised learning model(IDyOM) proposed by Pearce et al. makes no use of rulesof music theory with regard to melodic phrases, and it
performed as well as Grouper, LBDM, and separate GPRs
did [7]. However, as σGTTM learns all GPRs statisticallyand collectively, we expect that σGTTM performs better
than a model that uses only statistical learning does.

Detection of local grouping boundaries
Figure 2. σGTTM: System for automatically detecting
local grouping boundaries.
Moreover, melody segmentation can be automated by
calculating the conditional probability that a local groupingboundary exists from the decision tree. The whole σGTTM
system is shown in Figure 2.
Statistical learning requires training data in which GPR
and the correct boundaries are applied to the score. We
used the correct data for evaluating exGTTM as thetraining data [3]. We asked musicology experts to analyze
a hundred 8-bar monophonic pieces of classical music.
They were asked to analyze them in strict accordance with
GTTM. Three other experts crosschecked these manually
produced results.
3.1. Conflict between Rules
Because there is no strict order for applying GPRs, theconflict between rules often occurs when applying GPRs
and results in ambiguities in analysis. An example analysisof the local grouping structure extracted from the training
data is shown in Figure 3. In a state showing the
distribution of the rule on a score, statistical learning wasused to automatically detect the same local grouping

3. USE OF DECISIO TREE TO RESOLVE
CO FLICT BETWEE RULES
Using the abstracted training data, conflict between rules
can be resolved by constructing a decision tree, which is amodel of decisions and their possible consequences.

Local grouping boundary (correct data)
Note number 1

2 3 4

Λ
3d

5

Λ
2a
3a

6 7 8

Λ
3d

Λ Λ
3d 2a
3a

9

10 11 12

Λ
3d

14 15

13

Λ
3a

Λ
2a
2b

16

17 18 19

Λ
2b

Λ
3d

21 22 23

20

Λ
2a

Λ
3d

Figure 3. Example analysis of local grouping boundaries.

Λ Λ
3d 2a

24

25 26 27

Λ
3d

28

Applied GPRboundary as given by the correct data. However, detecting
the boundary of a local grouping is difficult because of aconflict between rules. As shown in the analysis of Figure
3, GPR3d is applied between 18th and 19th note as the ruleclaims the greater change in duration in neighboring notes
tends to be a boundary, while GPR2a is applied between
19th and 20th note which prioritizes the temporalproximity by slur and rest. However, the only one of themshould be applied here to prohibit the 19th to be a singleton.
Although GPR2a is applied in the example, the method ofchoosing which rule to apply is not clearly described in
GTTM.
3.2. Abstraction of Training Data
A decision tree expresses important knowledge about acertain attribute in the data (target attribute) that need to beobserved in the combination of the rules (conditional
attribute). In a decision tree, one suitable rule is chosen outof a set of conditional attributes, and data is divided into
two in accordance with the value of the rule. This division
is called a splitting test. A decision tree is built by
repeating these tests.
The data selected for constructing a decision tree
depend on the purpose. Our purpose is resolving ruleconflict between certain notes, and it is important toconsider whether GPR is applied between the notes





( 
, 
, 
, 
, 
,  ). If GPR1 is taken into
consideration, application of the rule between the previous





(
, 
, 
, 
, 
,  ) and the following





( ,  ,  ,  ,  ,  ) pairs of notes isalso important. The existence of these rules is defined as aconditional attribute. Furthermore, the existence of a localgrouping boundary ( ) is defined as target attribute. If a
local grouping boundary is between notes, we assign avalue of 1 to , otherwise = 0.
3.3. Construction of Decision Tree

!

| |
× ( ) .
||

(2)

The information gained by a test is strongly affected by the
number of outcomes. On the other hand, this split
information,/0*1(, ) = − 
!

| |
| |
× log  2
3
||
||

(3)

tends to increase with the number of outcomes of a test.
The gain ratio criterion is used to assess the desirability ofa test in terms of the ratio of its information gain to its split
information. The gain ratio of every possible test isdetermined, and thus the split with maximum gain ratio isselected.
Furthermore, C4.5 prunes the initial tree, identifying
subtrees that contribute little to predictive accuracy andreplacing each by a leaf (end node).
3.4. Detection of Local Grouping Boundaries
Part of a constructed decision tree is shown in Figure 4.
Each end node is labelled in accordance with a value witha large frequency of of the data classified into the node.
Therefore, the adequacy of a boundary location for a
combination of conditional attributes can be calculated.
When this conditional probability is 50 percent or more,
the system judges that there is a local grouping boundary( = 1). When this conditional probability is less than 50
percent and when data on the combination of conditional
attributes do not exist, the system judges that no localgrouping boundary exists ( = 0). For example, in Figure
4, if it is = 1 and = 1 , the local groupingboundary exists between n notes.
The system then analyses each musical piece unit
(Figure 5). When GPR1 is violated, that is, there areboundaries on both sides of one note, the local groupingboundary with the smaller probability is deleted.

B2na

1

0

Splitting test
1

B2nb

0

1

0

B2na+1B3nc−1

b =1

B2nb

1

0

B3nd

1

0

1

0

0

1

End nodeb=0

B2nb−1

b=0

1

B3nd

0

1

B3nc−1Figure 4. Part of constructed decision tree.

B3nc

0

…

…

…

0

…
…

1

…

!

(1)

()*(, ) = () − …

() = −  (, ) × log  ((, )),…

The decision tree is constructed by using a decision tree
generation algorithm, C4.5, derived by J. R. Quinlan [8].
The following algorithm generates a decision tree from aset  of cases. The tree for  has test  (splitting test) as
its root with one subtree for each outcome  that isconstructed by applying the same procedure recursively tothe cases in  . A family of possible tests is examined, andone of them is chosen to maximize the value of various
splitting criterion.
The splitting criterion used by C4.5 is the gain ratio.
The number of classes is defined as  and the proportion ofcases in  that belongs to the th class is defined as (, ).
The uncertainty of the class to which a case in  belongs is
expressed as

and the corresponding information gained by a test  with' outcomes asLocal grouping boundary (correct data)

Conditional probabilityof boundary existing [%]Note number 1

2 3 4

Λ
3d
100

5

Λ
2a
3a

6 7 8

Λ
3d

Λ
3d

10 11 12

9

Λ
2a
3a

Λ
3d

Λ
3a

16

14 15

13

17 18 19

Λ
2b

Λ
2a
2b

Λ
3d

21 22 23

20

Λ
2a

Λ
3d

Λ Λ
3d 2a

24

25 26 27

Λ
3d

28

Applied GPR

50
0Figure 5. Analysis of each musical piece.

4. EXPERIME TAL RESULTS
We evaluated the performance of the σGTTM systemusing the F-measure, which is given by the weighted
harmonic mean of precision 5 and recall 6.
5×6(4)789:;<9 = 2 ×
5+6
5 is the number of correct boundaries divided by that ofboundaries the system has suggested, while 6 is thenumber of retrieved correct boundaries divided by that of
all the truly correct boundaries.
We have evaluated the result by a 10-fold crossvalidation technique. Experimental results show that the
automatic local grouping boundary detection (σGTTM)
outperformed the baseline ATTA (Table 1).
Precision P Recall R F-measure
σGTTM

(new)
ATTA
(previous)

0.764

0.630

0.690

0.737

0.441

0.552

Table 1. Experimental results.

5. CO CLUSIO
We have described a method of using statistical learning toautomatically detect local grouping boundaries in GTTM.
This method has adequately solved the conflict between
rules by using a decision tree. Our experimental results
have shown that the σGTTM system outperformed thebaseline F-measure of ATTA. The σGTTM system will be
exhibited on the Web as CGI 1 . Therefore, a benchmark
with other melody segmentation methods is possible [9].
We plan to make it possible to construct a hierarchicalgrouping structure. Moreover, we plan to use statisticallearning to implement other analyses of GTTM (metricalstructure, time-span tree, and prolongational tree) on acomputer. We can already interpret the conditional
probability of boundary existing for each note as boundary
strength, and thus, we plan to investigate whether theboundary strength is applicable to other research on thecomposition of music.
6. REFERE CES[1] Cambouropoulos, E. “The Local Boundary Detection
Model (LBDM) and its application in the study of
expressive timing”, in Proceedings of theInternational Computer Music Conference, 2001, pp.
290-293.
[2] Cooper, G. and Meyer, L.B. The Rhythmic Structure ofMusic. Chicago: The University of Chicago Press,
1960.
[3] Hamanaka, M., Hirata, K., and Tojo, S.
“Implementing A Generative Theory of Tonal Music”,
in Journal of %ew Music Research, Vol. 35, No. 4, pp.
249-277, 2007.
[4] Hamanaka, M., Hirata, K., and Tojo, S. “FATTA: Full
Automatic Time-span Tree Analyzer”, in Proceedingsof the International Computer Music Conference,
2007, pp. 153-156.
[5] Lerdahl, F. and Jackendoff, R. A Generative Theory ofTonal Music. Cambridge: The MIT Press, 1983.
[6] Narmour, E. The Analysis and Cognition of Basic
Melodic Structure. Chicago: The University of
Chicago Press, 1990.
[7] Pearce, M. T., Müllensiefen, D., Wiggins, G. A. “A
comparison of statistical and rule-based models of
melodic segmentation”, in Proceedings of theInternational Conference on Music Information
Retrieval, 2008, pp.89-94.
[8] Quinlan, J. R. C4.5: Programs for Machine Learning.
Morgan Kaufman Publishers, 1993.
[9] Spevak, C., Thom, B., and Hothker, K. “Evaluating
Melodic Segmentation”, in Proceedings of theInternational Conference on Music and Artificial
Intelligence, 2002, pp. 168-182.
[10] Temperly, D. The Cognition of Basic Musical
Structure. Cambridge: The MIT Press, 2001.
[11] Temperly, D. The Melisma Music Analyzer.
http://www.link.cs.cmu.edu/music-analysis/, 2003.
[12] Temperly, D. Music and Probability. Cambridge: The
MIT Press, 2007.
1

http://music.iit.tsukuba.ac.jp/sigmagttm.html