Proceedings ICMC|SMC|2014

14-20 September 2014, Athens, Greece

METHOD TO DETECT GTTM LOCAL GROUPINGBOUNDARIES BASED ON
CLUSTERING AND STATISTICAL LEARNING
Kouhei Kanamori
University of Tsukuba

Masatoshi Hamanaka
Kyoto University

Junichi Hoshino
University of Tsukuba

kouhei@music.iit.tsukuba.ac.jp

masatosh@kuhp.kyoto-u.ac.jp

jhoshino@esys.tsukuba.ac.jp

ABSTRACTIn this paper, we describe σGTTMⅡ, a method that
detects local grouping boundaries of the generative theory of tonal music (GTTM) based on clustering and statistical learning. It is difficult to implement GTTM on acomputer because rules of GTTM often conflict witheach other and cannot detect music structure as samemanner. Previous methods have successfully implemented GTTM on a computer by introducing adjustable parameters or acquiring the priority of the rules by statistical learning. However, the values of the parameters andthe priority of the rules are different depending on a pieceof music. Considering these problems, we focused on thepriority of the rules and we hypothesized that there aresome tendency of rules which have more strong influencethan other rules by the case of music. To ensure this hypothesis, we tried to classify each piece of music andtried to find the tendency of rules. Through the experiment, we found some tendency of rules and then we acquired some detectors which can analyze each piece ofmusic more appropriately by reiterating clustering music
and statistical learning.

1. INTRODUCTION
Our purpose of this research is to develop a music analysis system, which we call σGTTMⅡ, that can semiautomatically detect music structure based on the generative theory of tonal music (GTTM) by reiterating clustering and statistical learning [1]. In this paper, we describe
how the local grouping boundaries of GTTM can be detected by choosing most appropriate detector.
GTTM is a music theory that enables comprehensive
analysis of the structure of a piece of music, such as thegrouping of melody (grouping structure) or the rhythm ofmusic (metrical structure). GTTM analysis can also be
used to obtain a time-span tree, which can express thepriority of notes, thus enabling us to operate music structure deeply.
There has been previous research on using time-span
Copyright: © 2014 Kouhei Kanamori et al. This is an open-access article
dis- tributed under the terms of the Creative Commons Attribution
License 3.0 Unported, which permits unrestricted use, distribution, andreproduction in any medium, provided the original author and source arecredited.

tree to deeply analyze music structure [2], to realize musical expression [3—5] and to obtain abstracted melody [6].
However, due to GTTM’s ambiguous rules, these studies[2—6] require a time-span tree that has already been madeby musicologists.
In order to acquire this time-span tree in the viewpointof computational music theory, there has been a study
that proposed extended GTTM, called exGTTM, inwhich the ambiguity of GTTM rules is covered by parameterization. This exGTTM was implemented on acomputer as an Automatic Time-span Tree Analyzer(ATTA) [7], which can acquire time-span tree by adjusting parameters. ATTA enables us to interpret music
structure more flexibly by adjusting parameters, but adjusting the parameters is difficult because there are somany of them.
In another study, 100 pieces of music structure data
were analyzed by a musicologist on the basis of GTTM
and to identify the priority of the rules of GTTM by statistical learning. This system is called σGTTM, which
can detect local grouping boundaries automatically [8].
However, this system sometimes outputs unnatural localgrouping boundaries because there are a lot of tendencies
of being local grouping boundaries and this system could
reflect only one tendency among them.
To overcome these problems, the purpose of our research is to detect possible music structures automaticallyand then determine the most appropriate structure fromamong them by following method. First, we classify 100
pieces of music data into various clusters and then determine the priority of the rules per cluster by statisticallearning. Next, we again divided the data reiteratively
into various clusters based on the priority of rules andconstructed gradually the clusters and detectors of localgrouping boundaries that best suited each piece of music.
We think that the system should be able to choose potential music structures by user because we think that theuser’s preference of music structure should be reflected in
the system. Experimental results demonstrated that the
proposed system outperformed the previous system inchoosing the most appropriate detector.

2. GTTM MUSIC THEORY AND ITS AMBIGUOUS RULESThe Generative Theory of Tonal Music (GTTM) was
formed by F. Lerdahl and R. Jackendoff in 1983. GTTM

- 1193 -Proceedings ICMC|SMC|2014

14-20 September 2014, Athens, Greece

was constructed more strictly than other music theories
and it can treat the structure of each piece of music comprehensively. However, when it comes to implementing it
on a computer, there is problem with the ambiguity of its
rules. In this section, we describe a method of analyzing
music structure by GTTM in section 2.1 and discuss the
problem with ambiguous rules in section 2.2.
2.1 Method of analyzing music structure in GTTM
In GTTM, there are four steps to analyze music structure:
Step 1: Analysis of grouping structure, in which music is
divided into some groups.
Step 2: Analysis of metrical structure, in which therhythm structure of music is detected.
Step 3: Analysis of time-span reduction, in which thepriority of each note in the music is detected and thenexpressed in a tree structure.
Step 4: Analysis of prolongational reduction, in which thetension and relaxation structure of the music is expressedin a tree structure.
An example of analysis by GTTM is shown in Figure 1.
Time-span tree

Metrical structureGrouping structure
Local grouping boundary

Figure 1. Example of analysis by GTTM.

Each step constructs well-formedness rules and preference rules. Well-formedness rules construct the initialframework of a music structure and preference rules detect more preferable music structures in the framework.
Each music structure is hierarchical. The regular order ofa GTTM music structure is constructed by analyzing eachstep. In this work, we treat the first step, grouping structure.
The well-formedness rules of the grouping structure arecalled grouping well-formedness rules (GWFR) and thepreference rules are called grouping preference rules(GPR). GPR can classify two types of structure: one fortreating the lowest (local) grouping structure (GPR1, 2, 3)
and the other for treating the higher grouping structure.
The interval between notes in which the local GPR isapplied has the possibility of grouping boundary. An ex-

ample of analyzing local grouping structure is shown in
Figure 2.
2.2 Problems with ambiguous rules in GTTM
When we analyze music structure by GTTM, we may
deal with a conflict between preference rules, since preference rules do not have any individual priority among
themselves. Originally preference rules are formed todeal with human’s preference, but that conflict between
preference rules causes some difficulty when it comes toimplementing GTTM on a computer. At that situation, we
think that the analysis of the local grouping structure wetreat in this paper has mainly two problems.
The first problem is conflict between rules. In the example of analysis shown in Figure 2, GPR2a and GPR2b are
applied between notes 17 and 18 and GPR3a is applied
between notes 18 and 19. GPR2a is applied when there isa rest or at the end of a slur, GPR2b is applied when there
is a relatively higher duration, and GPR3a is applied
when there is relatively higher difference of pitch between notes. In this case, we cannot detect that both 17—
18 and 18—19 are grouping boundaries because of GPR1,
which means that the grouping of one note must be
avoided. This means we have to choose either 17—18 or
18—19 as the boundary, but in GTTM there are no rules
for making this choice.
The second problem is that grouping boundary is notalways applied in the same manner as local GPR. In Figure 2, GPR3a is applied between 5—6 and 23—24 andthere are local grouping boundaries, but there is no local
boundary in spite of the presence of GPR3a in 11—12 and18—19 and 29—30 and 32—33. This problem cannot be
resolved in GTTM.

3. CONSTRUCTION OF σGTTMⅡWe hypothesize that each piece of music has some tendency about priority of GTTM rules, which mean localgrouping preference rules (local GPR) in this paper. If we
can find that priority from some analysis of GTTM, we
can analyze each piece of music more appropriately. Thus
we use statistical learning for extracting that priority.
Considering that the priority of local GPR cannot finduntil applying statistical learning, we reiteratively classify
each piece of music into various clusters and constructdetectors of local grouping structure gradually by applying statistical learning per cluster.

Note number
12

4 5 6 7 89

10 11 12 1327

28 29 30 31

32 33 34

<

<

<

2a
2b
3a

2a 3a
2b

3a

2a
2b
3a

3a

2a 3a
2b

Local grouping structure

Figure 2. Example of analyzing local grouping structure.

- 1194 -<<3a

18 19 20 21 22 23 24 25 26

<
<

2a
2b
3a

14 15 16 17

<

<

3a

<

<

Appliedlocal GPR

3

35

Proceedings ICMC|SMC|2014

14-20 September 2014, Athens, Greece

In this section, we give an overview of proposed system σGTTMⅡin section 3.1, describe the method of
detecting local grouping structure in section 3.2 and themethod of detecting priority of local GPR used in previous research σGTTM in section 3.3.
3.1 Overview of σGTTMⅡ
Figure 3 shows an overview of proposed system σ
GTTMⅡ. The main idea of this system is to reiterate
clustering and statistical learning in order to classify eachpiece of music on the basis of priority of local GPR and
detect local grouping structure more appropriately andeasily. This system can classify each piece of music intosome clusters and output detector of local grouping structure per cluster. This means the system outputs somecandidates about local grouping structure reflected various priority of local GPR. Users can detect local groupingboundary more easily by choosing most preferable detector from among some candidates.
manually byMusic XML Analyzed
GTTM musicologist
<

<

<

<

<

<

<

3a

3a

3a

2b

3a

3a

2b
3a

Abstract data

Decision tree
(section 3.3.2)

1

…
…

0

1

…

0

…

Training data ()(section 3.3.1)

10

Reiterate
Clustering

Statistical Learning
・・・

generate detector
gradually per cluster

System Output
Detector A

・・・
1

0

1

…

…

…

1

…
…

…

0

…

0

1

…

0

In this work, we use method of obtaining abstracted data
(training data) and detecting priority of local GPR used inprevious research σGTTM. In this subsection, we givean overview of the method of abstracting musicXML in
subsection 3.3.1 and decision tree in subsection 3.3.2 anddetecting priority of local GPR in subsection 3.3.3.
3.3.1 Training data
100 musicXML was chosen as training data data of eachpiece of music, which is analyzed by GTTM musicologist
manually and checked by GTTM experts. The objective
value we want to know is the existence of local groupingboundary (is shown as b) so the value can be represented
by 1 or 0 (boundary exists or not). Local GPR also shouldbe abstracted because whether there is a boundary or not
is decided by the local GPR. Considering that there is arule in local GPR of avoiding single note grouping, notonly the checking interval n (between note n and noten+1), but also neighbor interval (interval n-1 and intervaln+1) should be checked. So the data was abstracted by
the form of. The superscript n means the checking
interval n. The subscript GPR means the kind of local
GPR. Local GPR we treat are 6 kinds (2a, 2b, 3a, 3b, 3c,3d) so the abstracted data of checking interval can be. Considering the,,,,shown as,neighbor interval, the total abstracted data can be shownby 18 elements. These elements have a value 1 or 0 (rules
exist or not). By the 18 elements the existence of localgrouping boundary (b) is decided.

Decision tree is one of statistical learning method. It canrepresent objective value and the priority of making decision as easy way to understand. It consists of mainly
leaves and branches and ramification and this tree is upside down. The principle to make decision is due to thevalue of each ramification. Through this decision tree
learning, the more the kind of ramification has influence
to making decision, the more that ramification get near toroot position.

10

3.3 Method of detecting priority of local GPR used inprevious research σGTTM

3.3.2 Decision Tree

Detector B

10grouping structure. The main reason of designing thissystem as flexible detecting method of local grouping
structure is to reflect user’s preference about local grouping structure. Preference is different by each user, so thissystem outputs the some detectors, which are designed toreflect various tendencies about priority of local GPR.

Figure 3. Overview of σGTTMⅡ.

3.2 Method of detecting local grouping structure
The way to detect local grouping structure is to choose
the detector you most preferred. When this system is used
to musicXML data which is not trained, system outputs
some candidates of local grouping structure about thatdata by some detectors which were already constructed.
Users can see there detectors, which mean you can see
the priority of local GPR of each candidates about local

3.3.3 Detecting priority of local GPR by decision tree
We chose C4.5, an algorithm developed by J. R. Quinlan[9] to construct the decision tree. Figure 4 shows an example of the constructed decision tree. From training data,
we can obtain the conditional probability of local grouping boundaries for each combination of local GPR. When

- 1195 -Proceedings ICMC|SMC|2014

14-20 September 2014, Athens, Greece

this conditional probability is 0.5 or more, we detect toexist a local grouping boundary (b = 1), and when it isless than 0.5, we do not detect to exist boundary (b = 0).
For the example in Figure 4, we detect a local groupingboundary exists in the case of.

the priority of local GPR of the entire training data in acluster.

System Input(Training data)

10

Cluster A Cluster B

0

0

b=1

1

b=0

・・・

0

After

(A,B,C,…)(A’,B’,C’,…)Music No.
2,7,14,…

Music No.
12,14,34,…

1
b=1

Statistical learning

1

Detector B

b=1

0

1 0

1

…

…
…

…

1

・・・

The number of different
music is 1 or 0 in eachcluster?
(between A and A’, B and
B’, C and C’,…)

Evaluate each detector
by all training data

To classify each piece of music on the basis of priority of
local GPR, we reiterated clustering and statistical learning and generated detectors gradually. Figure 5 shows thedetails of clustering method. In this section, we describe
the details of this method in section 4.1, method of evaluating each piece of music in section 4.2 and discuss about
number of clusters in section 4.3.

Music No.

1
・
・
・

・
・
・

ExampleYes

System Output

Detector A
Detector B

2

・
・
・

(

)

Detector and musicin each cluster

If F-measure of music no. 1
is max in Detector B, music
no. 1 is reclassified tocluster B’.

4.1 Details of clustering method
First, we classify training data into some clusters. The
training data of each cluster is then trained by a decision
tree. After this training, a decision tree of GPR priority isconstructed. Detector means the constructed decision tree.
In figure 5 cluster and detector A, B, etc. means detector
A is constructed in cluster A and detector B is constructed in cluster B, etc. However, this part is problematic
because an irrelevant analyzed music structure might
exist in the same cluster due to the detectors of each cluster representing tendency of the entire music structure as
the same for each cluster.
To solve this problem, the system individually evaluates the performance of each detector as they are constructed and then reclassifies the training data into clusters which generated most performed detector. In figure 5
the clusters after reclassified are represented as A’, B’,etc. And then system compares the training data of eachcluster between before (A, B, etc.) and after reclassification (A’, B’, etc.). The less the training data in the clusterchanges, the more the detectors that are constructed cover
the tendency of the priority of local GPR of all training
data in the cluster.
After this comparison between clusters, if the total difference of training data before and after reclassification ismore than two, the system returns to constructing detectors again and if the total difference is less than one, or if
reclassification has been performed 150 times, the system
outputs training data and detectors of each cluster. Finally,
we construct the most appropriate detector on the basis of

10…

4. METHOD OF CLUSTERING MUSIC

0

No

1

0

1

…

Figure 4. Example of constructed decision tree.

0…
…

Reclassify

Detector A

b=0

Beforeb=1

b=00

Cluster C101

Compare music in eachcluster between before
and after reclassification

Clustering

Figure 5. details of clustering method.

4.2 Method of evaluating each detector
When the system reclassifies training data, system evaluates each detector by F-measure, which consists of precision (P) and recall (R). Precision is the ratio of corresponding to correct local grouping boundary in the outputof the system. Recall is the ratio of corresponding to the
output of the system in the correct local grouping boundary. The F-measure is represented as(1)
Each training data is reclassified by cluster which generates most high performed detector.
4.3 Number of clusters
When we classify each piece of music into some clusters
at first, we don’t know how many tendencies each pieceof music has. So, we changed the number of cluster atfirst classification from 1 to 100. This means at first the
number of input cluster of this system is 1 and system
outputs 1 detector, and then number of input cluster is 2
and system outputs 2 detectors. Thus the system runs 100
times through the input and output. At each runtime thesystem reiterating clustering and statistical learning manytimes until it gets ready to output detectors.

- 1196 -Proceedings ICMC|SMC|2014

14-20 September 2014, Athens, Greece

5. EXPERIMENTAL RESULTS
We implemented proposed system σGTTMⅡ and evaluated the performance of detectors constructed in clusters
by detecting the local grouping boundaries of 100 pieceof music. Figure 6 shows the results of this experiment.
The precision is the value when most appropriate detector
was chosen.

appropriate detector in the case of no trained data (Table2).
F-measure

σGTTM

0.467

0.736

0.571

σGTTMⅡ

0.684

0.916

0.783

Table 2. Evaluation experiment (open).
Precision

0.9

Performance

Recall R(Number of clusters is 10)

1

6. CONCLUSION

F-measure

0.8

Recall
0.7
0.6

0.5

0

20

40

60

Number of clusters

80

100

120

Figure 6. Performance of σGTTMⅡ.

As the initial clusters grew bigger, some clusters inwhich the number of music became 0 appeared, so there
were some cases in which the number of clusters outputted by the system differed from the initial clusters. The
relationship between the number of initial clusters and theoutput clusters is shown in Figure 7.
Number of output clusters

Precision P

30
25
20

15
10

In this paper, we described a method of semiautomatically detecting the local grouping boundaries of
GTTM by choosing the appropriate detector. In thismethod, we avoid conflicting GPR rules by using a decision tree and detecting local GPR priorities. Moreover,
we divide training data that have similar priorities of local GPR into various clusters and construct the detectors
most appropriate for each cluster. Experimental results
demonstrated that the proposed system outperforms aprevious system when it comes to choosing the most appropriate detector.
We expected that each piece of music in same cluster
has same feature about part of musical piece, but wecouldn’t find them at that point. Our next step is to try tofind some same feature in each piece of music in samecluster. Also we try to extend this system to higher
grouping structure, metrical structure, and time-span reduction.

5

0

0

20

40

60

80

100

7. REFERENCES

120

Number of initial clusters[1]
Figure 7. Transition of cluster numbers.

Next, we compared σGTTMⅡ with previous research
ATTA and σGTTM. The performance of σGTTMⅡ isthe value when the number of clusters was 10. Results
demonstrated that σGTTMⅡ outperformed the previous
research when it comes to choosing most appropriate
detector (Table 1). Precision and recall of ATTA cannot
be mentioned because they were not described in the previous study [7]. Also F-measure of ATTA is evaluatedunder the situation of treating higher grouping structure.
Precision P

Recall R

F-measure

ATTA

－

－

0.77

σGTTM

0.764

0.630

0.690

σGTTMⅡ

0.905

0.734

0.811

(Parameters are adjusted)(Number of clusters is 10)

[2]

[3]
[4]

[5]

[6]

[7]

Table 1. Evaluation experiment (closed).

To determine the performance of σGTTMⅡ with data that is not trained, we evaluated this system using correct data that was analyzed by a GTTM musicologist andchecked by three GTTM experts. We also evaluated previous research σGTTM in the same situation for comparison. Results show that σGTTMⅡoutperformed previous research σGTTM when it comes to choosing most

[8]

[9]

- 1197 -F. Lerdahl and R. Jackendoff, “A Generative Theory ofTonal Music”, Cambridge: The MIT Press, 1983.
K. Hirata and T. Aoyagi, “Computational Music
Representation based on the Generative theory of Tonal
Music and the Deductive Object-Oriented Database”,
Computer Music Journal 27(3), 73—89, 2003.
N. Todd, “A Model of Expressive Timing in Tonal Music”,
Musical Perception, 3:1, 33—58, 1985.
G. Widmer, “Understanding and Learning MusicalExpression”, Proceedings of International Computer
Music Conference, pp. 268—275, 1993.
K. Hirata and R. Hiraga, “Ha-Hi-Hun plays Chopin’s
Etude”, Working Notes of IJCAI-03 Workshop on
Methods for Automatic Music Performance and their
Applications in a Public Rendering Contest, pp. 72—73,
2003.
K. Hirata and S. Matsuda, “Interactive Music
Summarization based on GTTM”, In Proc. of ISMIR 2002,
pp. 86—93, 2002.
M. Hamanaka, K. Hirata and S. Tojo, “ATTA: AutomaticTime-span Tree Analyzer based on Extended GTTM”,
Proceedings of the 6th International Conference on Music
Information Retrieval conference (ISMIR2005), pp. 358—
365, September 2005.
Y. Miura, M. Hamanaka, K. Hirata, and S. Tojo, “Use ofDecision Tree to Detect GTTM Group Boundaries”,
Proceedings of the 2009 International Computer Music
Conference (ICMC2009), pp. 125—128, August 2009.
J. R. Quinlan, “C4.5: Programs for Machine Learning”,
Morgan Kaufman Publishers, 1993.