Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

Cognitive Similarity Grounded by Tree Distancefrom the Analysis of K.265/300e
Keiji Hirata1 , Satoshi Tojo2 , and Masatoshi Hamanaka3
1

Future University Hakodate
2
JAIST
3
University of Tsukuba
hirata@fun.ac.jp

Abstract. Lerdahl and Jackendoﬀ’s theory employed a tree in a representation of internal structure of music. In order for us to claim that sucha tree is a consistent and stable representation, we argue that the diﬀerence of trees should correctly reﬂect our coginitive similarity of music. We
report our experimental result concerning the comparison of similarity
among variations on Ah vous dirai-je, maman, K. 265/300e by Mozart.
First we measure the theoretical distance between two variations by thesum of the lengths of time-spans, and then we compare the result withthe human psychological resemblance. We show the statistical analysis,
and discuss the adequacy of the distance as a metric of similarity, which
moreover becomes a metrics of theory.
Keywords: Time-span tree, Generative Theory of Tonal Music, join/meet
operations, cognitive similarity

1

Introduction

Music theory gives us methodology to analyze music written on scores, andclariﬁes their inherent features in a comprehensive way. There have been many
attempts to embody a music theory onto a computer system and to build amusic analyzer. In particular, some music theories employ trees to represent the
deep structure of a musical piece [10, 6, 11, 15, 1], and such a tree representation
seems a promising way to automatize the analyzing process. It is, however, widely
recognized that there are intrinsic diﬃculties in this; (i) how we can formalize
ambiguous or missing concepts and (ii) how we can assess the consistency andstability of a fomalized music theory.
For (i), the approaches include the externalization of those hidden features ofmusic. For example, Lerdahl and Jackendoﬀ [10] (the generative theory of tonal
music; GTTM hereafter) speciﬁed many rules to retrieve such information in music to obtain a time-span tree, though they proposed only heuristics and missed
fully explicit algorithms. Thus, to formalize this theory, we have complemented
necessary parameters to clarify the process of time-span reduction [8]. Pearceand Wiggins [14] build a model to derive as many features as possible from thescores; these features contain the properties of potentially non-contiguous events.

CMMR2013 - 415

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

2

K. Hirata, S. Tojo, and M. Hamanaka

For (ii), we do not think there is an agreeable solution yet, but we propose toassess the consistency and the stability of a formalized music theory based on our
cognitive reality. If the tree representation derived by a formalized music theory
is suﬃciently stable and consistent, the distance between those representations
must reﬂect our human intuition on diﬀerence in music. Hence, if it is allowed
to compare the tree distance and our psychological diﬀerence and/or similarity,
we can evaluate the consistency and the stability of a formalized music theory.
Here, we look back at the studies on similarity in music. In music information
research, the similarity has been drawing attention of many researchers [19, 9].
Some of the reseachers are motivated by engineering demands such as music
retrieval, classiﬁcation, and recommendation, [13, 7, 16] and others by modelingthe cognitive processes of musical similarity [4, 5]. Several types of similarity havebeen proposed, including melodic similarity, e.g., van Kranenburg (2010) [18]and harmonic similarity, e.g., de Haas (2012) [3]. The song similarity in MIREXof every year is recognized as an important category in the contest [12]. All
these viewpoints suggest the importance of quantitative comparison, and thus
we employ a numeric distance in measuring the cognitive similarity.
We have proposed a notion of distance among the time-span trees [17], however, in this research there lacked the discussion on the perception of similarity.
As a result, it was diﬃcult for us to explain that the distance could be a metricof similarity [9, 13, 18, 3]. The contribution of this paper is that we have actuallyconducted a psychological experiment on the similarity among 12 variations in C
major on Ah vous dirai-je, maman, K. 265/300e by Wolfgang Amadeus Mozart,in comparison with the corresponding time-span distance.
This paper is organized as follows: in Section 2 we brieﬂy summarize thenotion of time-span tree and reduction. In Section 3, we introduce our notionof distance in time-span trees. Then, to apply the notion to arbitrary two music pieces, we generalize the distance in Section 4. In Section 5, we report ourexperimental result. First we measure the distance between two variations by
the tree distance, and then we compare the result with the human psychologicalresemblance. We show the statistical analysis, and discuss the adequacy of ourmeasure as a metric of similarity 6. Finally we conclude in Section 7.

2

Time-Span Tree and Reduction

Time-span reduction in Lerdahl and Jackendoﬀ’s Generative Theory of Tonal
Music (GTTM; hereafter) [10] assigns structural importance to each pitch eventsin the hierarchical way. The structural importance is derived from the grouping
analysis, in which multiple notes compose a short phrase called a group, and fromthe metrical analysis, where strong and weak beats are properly assigned on eachpitch event. As a result, a time-span tree becomes a binary tree constructed inbottom-up and top-down manners by comparison between the structural importance of adjacent pitch events at each hierarchical level. Although a pitch
event means a single note or a chord, we restrict our interest to monophonicanalysis in this paper, as the method of chord recognition is not included in the

CMMR2013 - 416

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

Cognitive Similarity Grounded by Tree DistanceOrdering of
reduction
proceeded

3

6

Surface structure
Reduction?

Fig. 1. Reduction hierarchy of chorale ‘O Haupt voll Blut und Wunden’ in St.
Matthew’s Passion by J. S. Bach [10, p.115]

original theory. Fig. 1 shows an excerpt from [10] demonstrating the concept of
reduction.
In the sequence of reductions, each reduction should sound like a simpliﬁcation of the previous one. In other words, the more reductions proceed, eachsounds dissimilar to the original. Reduction can be regarded as abstraction, but
if we could ﬁnd a proper way of reduction, we can retrieve a basic melody lineof the original music piece. The key idea of our framework is that reduction is
identiﬁed with the subsumption relation, which is the most fundamental relationin knowledge representation.

CMMR2013 - 417

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

4

3

K. Hirata, S. Tojo, and M. Hamanaka

Strict Distance in Time-Span Reduction

In the section, the basic formalization of time-span trees is given as a prerequisite
for extending our framework to be described later. Since the contents presented
in the section overlap some of those in [17] and contain rather mathematicalstuﬀ, the readers who ﬁrst want to comprehend an outline of the contributions
could move onto the experimental section. Then, the readers would come backhere afterward.
3.1

Subsumption, Join, and MeetFirst we deﬁne the notion of subsumption. Let σ1 and σ2 be tree structures. σ2
subsumes σ1 , that is, σ1  σ2 if and only if for any branch in σ1 there is acorresponding branch in σ2 .
Deﬁnition 1 (Join and Meet) Let σA and σB be tree structures for music A
and B, respectively. If we can ﬁx the least upper bound of σA and σB , that is,
the least y such that σA  y and σB  y is unique, we call such y the join of σAand σB , denoted as σA  σB . If we can ﬁx the greatest lower bound of σA andσB , that is, the greatest x such that x  σA and x  σB is unique, we call suchx the meet of σA and σB , denoted as σA  σB .
We illustrate join and meet in a simple example in Fig. 2. The ‘’ (join)
operation takes quavers in the scores to ﬁll dtrs value, so that missing note in
one side is complemented. On the other hand, the ‘’ (meet) operation takes ⊥for mismatching features, and thus only the common notes appear as a result.

‰q  ‰ q =
q
e
q
q e
q ee
qe

‰q 

Œq
‰ q =
e
q
q

Fig. 2. Join and meet

Obviously from Deﬁnitions 1, we obtain the absorption laws: σA x = σA andσA x = x if x  σA . Moreover, if σA  σB , xσA  xσB and xσA  xσB
for any x.
We can deﬁne σA  σB and σA  σB in recursive functions. In the processof uniﬁcation between σA and σB , when a single branch is uniﬁable with a tree,

CMMR2013 - 418

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

Cognitive Similarity Grounded by Tree Distance5

σA  σB chooses the tree while σA  σB chooses the branch, in a recursive way.
Because there is no alternative action in these procedures, σA  σB and σA  σB
exist uniquely. Thus, the partially ordered set of time-span trees becomes alattice.
3.2

Maximal Time-Span and Reduction Distance

In GTTM, a listener is supposed to construct mentally pitch hierarchies (reductions) that express maximal importance among pitch relations [10, p.118]. We
here observe a time-span becomes longer as the level of time-span hierarchy goeshigher. Then, we can suppose that a longer time-span contains more information,and it is therefore regarded more important.
Based on the above consideration, we hypothesize:
If a branch with a single pitch event is reduced, the amount of information
corresponding to the length of its time-span is lost.
We call a sequence of reductions of a music piece reduction path. We regard thesum of the length of such lost time-spans as the distance of two trees, in the
reduction path. Thereafter, we generalize the notion to be feasible, not only ina reduction path but in any direction in the lattice.
We presuppose that branches are reduced only one by one, for the convenience
to sum up distances. A branch is reducible only in the bottom-up way, i.e., areducible branch possesses no other sub-branches except a single pitch eventat its leaf. In the similar way, we call the reverse operation elaboration; we canattach a new sub-branch when the original branch consists only of a single event.
The head pitch event of a tree structure is the most salient event of thewhole tree. Though the event itself retains its original duration, we may regard
its saliency is extended to the whole tree. The situation is the same as each
subtree. Thus, we consider that each pitch event has the maximal length ofsaliency.
Deﬁnition 2 (Maximal Time-Span) Each pitch event has the maximal timespan within which the event becomes most salient, and outside the time-span thesalience is lost.
In Fig. 3 (a), there are four contiguous pitch events, e1, e2, e3, and e4; eachhas its own temporal span (duration on surface), s1, s2, s3, and s4, denoted thinlines. Fig. 3 (b) depicts time-span trees and corresponding maximal time-spanhierarchies, denoted gray thick lines. The relationships between spans in (a) andmaximal time-spans in (b) as follows. At the lowest level in the hierarchy, thelength of a span is equal to that of a maximal time-span; mt2 = s2, mt3 = s3.
At the higher levels, mt1 = s1 + mt2, and mt4 = mt1 + mt3 + s4 = s1 + s2 +s3 + s4. That is, every span extends itself by concatenating the span at a lower
level along the conﬁguration of a time-span tree. When all subordinate spansare concatenated up into a span, the span reaches the maximal time-span.
Only the events at the lowest level in the hierarchy are reducible; the otherevents cannot be reduced. In Fig. 3 (b), for the leftmost time-span tree σ1, either

CMMR2013 - 419

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

6

K. Hirata, S. Tojo, and M. Hamanaka
e1

e2

e3

e4









s1 s2 s3 s4(a) Sequence of pitch events and their spans

σ1


mt1





σ2





mt2 mt3

mt4

mt1



σ3





mt3

mt4

mt1

σ4




mt4

mt4

(b) Reduction proceeds by removing a reducible maximal time-span

Fig. 3. Reduction of time-span tree and maximal time-span hierarchy; gray thick lines
denote maximal time-spans while thin ones pitch durations.

e2 or e3 is reducible; e2 is ﬁrst reduced then e3. For σ2, e3 is only reducible, not
e1 because e1 is not at the lowest level in the maximal time-span hierarchy.
Let ς(σ) be a set of pitch events in σ, ς(σ) be its cardinality, and se be themaximal time-span of event e. Since reduction is made by one reducible branch
at a time, a reduction path σ n , σ n−1 , . . . , σ 2 , σ 1 , σ 0 , such that σ n  σ n−1  . . . 
σ 2  σ 1  σ 0 , suﬃces ς(σ i+1 ) = ς(σ i ) + 1. If we put σA = σ 0 and σB = σ n ,σA  σB holds by transitivity. For each reduction step, when a reducible branchon event e disappears, its maximal time-span se is accumulated as distance.
Deﬁnition 3 (Reduction Distance) The distance d of two time-span trees
such that σA  σB in a reduction path is deﬁned byd (σA , σB ) = e∈ς(σB )\ς(σA ) se .
For example in Fig. 3, the distance between σ1 and σ4 becomes mt1 + mt2 +
mt3. Note that if e3 is ﬁrst reduced and e2 is subsequently reduced, the distanceis the same. Although the distance is a simple summation of maximal time-spansat a glance, there is a latent order in the addition, for reducible branches are
diﬀerent in each reduction step. In order to give a constructive procedure on thissummation, we introduce the notion of total sum of maximal time-spans.
Deﬁnition 4 (Total Maximal Time-Span) Given tree structure σ,tmt(σ) = e∈ς(σ) se .
When σA  σB , from Deﬁnition 3 and 4, d (σA , σB ) = tmt(σB ) − tmt(σA ).
As a special case of the above, d (⊥, σ) = tmt(σ).

CMMR2013 - 420

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

Cognitive Similarity Grounded by Tree Distance

3.3

7

Properties of Distance

Uniqueness of Reduction Distance: First, as there is a reduction path between
σA  σB and σA  σB , and σA  σB  σA  σB , d (σA  σB , σA  σB ) is computedby the diﬀerence of total maximal time-span. Because the algorithm returns aunique value, for any reduction path from σA  σB to σA  σB , d (σA  σB , σA 
σB ) is unique. This implies the uniqueness of reduction distance: if there exist
reduction paths from σA to σB , d (σA , σB ) is unique.
Next, from set-theoretical calculus,ς(σA  σB ) \ ς(σA ) = ς(σB ) \ ς(σA 
σB ). Then, d (σA , σA  σB ) = e∈ς(σA σB )\ς(σA ) se = e∈ς(σB )\ς(σA σB ) se =d (σA σB , σB ). Therefore, d (σA , σA σB ) = d (σA σB , σB ) and d (σB , σA 
σB ) = d (σA  σB , σA ).
Here let us deﬁne two ways of distances.
d (σA , σB ) = d (σA  σB , σA ) + d (σA  σB , σB )d (σA , σB ) = d (σA , σA  σB ) + d (σB , σA  σB )Then, we immediately obtain d (σA , σB ) = d (σA , σB ) by the uniqueness of
reduction distance.
For any σ  , σ  such that σA  σ   σA σB , σB  σ   σA σB , d (σA , σ  )+d (σ  , σ  ) + d (σ  , σB ) = d (σA , σB ). Ditto for the meet distance. Now thenotion of distance, which was initially deﬁned in the reduction path as d is
now generalized to d{,} , and in addition we have shown they have the samevalues. From now on, we omit {, } from d{,} , simply denoting ‘d’. Here,d(σA , σB ) is unique among shortest paths between σA and σB . Note that shortest
paths can be found in ordinary graph-search methods, such as branch and bound,
Dijkstra’s algorithm, best-ﬁrst search, and so on. As a corollary, we also obtaind(σA , σB ) = d(σA  σB , σA  σB ).
Triangle Inequality: Finally, as d(σA , σB ) + d(σB , σC ) becomes the sum of maximal time-spans in ς(σA σB )\ς(σA σB ) plus those in ς(σB σC )\ς(σB σC ) whiled(σA , σC ) becomes ς(σA  σC ) \ ς(σA  σC ), we obtain d(σA , σB ) + d(σB , σC ) ≥d(σA , σC ): the triangle inequality. For more details on the theoretical stuﬀ, see[17].
In Fig. 4, we have laid out various reductions originated from a piece. As we
can ﬁnd three reducible branches in A there are three diﬀerent reductions: B, C,
and D. In the ﬁgure, C (shown diluted) lies behind the lattice where three backside edges meet. The distances, represented by the length of edges, from A to B,
D to F , C to E, and G to H are the same, since the reduced branch is common.
Namely, the reduction lattice becomes parallelepiped,4 and the distances from A
to H becomes uniquely 2 + 2 + 2 = 6. We exemplify the triangle inequality; fromA through B to F , the distance becomes 2 + 2 = 4, and that from F throughD to G is 2 + 2 = 4, thus the total path length becomes 4 + 4 = 8. But, we canﬁnd a shorter path from A to G via either C or D, in which case the distance4

In the case of Fig. 4, as all the edges have the length of 2, the lattice becomesequilateral.

CMMR2013 - 421

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

8

K. Hirata, S. Tojo, and M. Hamanaka

Fig. 4. Reduction lattice

becomes 2 + 2 = 4. Notice that the lattice represents the operations of join andmeet; e.g., F = B  D, D = F  G, H = E  F , and so on. In addition, thelattice is locally Boolean, being A and H regarded to be  and ⊥, respectively.
That is, there exists a complement,5 and E c = D, C c = F , B c = G, and so on.

4

Generalized Distance in Trees

In this section, we extend the notion of strict distance, to be applicable to two
diﬀerent music pieces, which may not necessarily share a common-ancestor musicpiece in terms of reduction. To this purpose, we need to relax the condition of
distance calculation.
4.1

Interval Semantics on Absolute Time Axis

In order to compare two diﬀerent melodies, we need to place those at proper
places in a common temporal axis. Two arbitrary music pieces are possibly different from each other with a large variety; for example, a music piece beginningwith auftakt or syncopation, containing hemiola, and being at a double tempo
with the same pitch sequence. To handle such cases, we may need various typesof adjustments of two music pieces for comparison; for example, alignment by
the endpoints of music pieces and/or bar lines, and by stretching or compressing
to make the two of same length.
At present, we take the simplest approach to the adjustment in which twomusic pieces are aligned only at the beginning bar line. Then, the join/meet operations are applied to maximal time-spans without stretching or compressing
them. That is, when two temporal intervals have a common length, the result ofa join operation encompasses the temporal union of the two intervals, and that5

For any member X of a set, there exists X c and X  X c =  and X  X c = ⊥.

CMMR2013 - 422

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

Cognitive Similarity Grounded by Tree Distance9of meet operation is exactly the temporal intersection (Fig. 5), where mt{1,2}means a maximal time-span, respectively. The decision is underlain by the following assumption: the longer a time-span is, the more informative it is, as theinterval semantics of temporal logic [21].

mt1
mt2
time
join(mt1, mt2)
meet(mt1 mt2)
meet(mt1,
Fig. 5. Generalized join and meet operations to maximal time-spans

4.2

Meet-Oriented Distance

In Section 3.3, we have shown that the distance via the meet and that via the join
become the same in the lattice of strict descendents of one common music piece.
However, when we are to apply two music pieces without a common ancestor, one
serious problem is that such equality of join/meet distance may not be promised.
First of all, we cannot calculate the join operation for all cases at present; forexample, if the supremacy of the heads of two trees do not match, the result of
the join operation is not deﬁned (Fig. 6). In contrast, the result of meet operation
can be calculated in any case. Therefore, in this paper, we decide to calculate
the distance using the path via the meet d in Section 3.3.

join(

SubtreeA

SubtreeB,

SubtreeA’

SubtreeB’)Fig. 6. Case of undeﬁned result in join operation

Fig. 7 shows the excerpt from the Prolog program implementing the generalized join and meet operations. The join/meet operations are recursively appliedin the top-down manner. In the Prolog program, a node in a time-span tree isrepresented by data structure (Tp > Ts ) or (Ts > Tp ), where Tp and Ts denote
subtrees (Fig. 8). Subscripts ‘p’ and ‘b’ represent that a branch is primary or
secondary, and the temporal order between them is shown by ‘<’ or ‘>’.

CMMR2013 - 423

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 201310

K. Hirata, S. Tojo, and M. Hamanaka
join(X,Y,Join) :X = (Xp > Xs),
Y = (Yp > Ys),!,join(Xp,Yp,Mp),join(Xs,Ys,Ms),
Join = (Mp > Ms).
join(X,Y,Join) :X = (Xs < Xp),
Y = (Ys < Yp),!,join(Xp,Yp,Mp),join(Xs,Ys,Ms),
Join = (Ms < Mp).
join(X,Y,Join) :X = ( > ),Y = ( < ),!,
Join = undefined.
join(X,Y,Join) :X = ( < ),Y = ( > ),!,
Join = undefined.

meet(X,Y,Meet) :X = (Xp > Xs),
Y = (Yp > Ys),!,meet(Xp,Yp,Mp),meet(Xs,Ys,Ms),
Meet = (Mp > Ms).
meet(X,Y,Meet) :X = (Xs < Xp),
Y = (Ys < Yp),!,meet(Xp,Yp,Mp),meet(Xs,Ys,Ms),
Meet = (Ms < Mp).
meet(X,Y,Meet) :X = (Xp > ),Y = ( < Yp),!,meet(Xp,Yp,Meet).
meet(X,Y,Meet) :X = ( < Xp),
Y = (Yp > ),!,
meet(Xp,Yp,Meet).

Fig. 7. Prolog implementation of generalized join and meet operations (recursion part)

ns 

 np

np 
mtp

mts



mttp

(ns < np)ns
mts

(np > ns)Fig. 8. Representation of time-span tree node in Prolog program

5

Experiment

We conduct two experiments using the same set of pieces: a similarity assessmentby human listeners and the calculation by the proposed framework. Set pieceis the Mozart’s variations K.265/300e ‘Ah, vous dirai-je, maman’, also known
as ‘Twinkle, twinkle little star’. The piece consists of the famous theme andtwelve variations of it. In our experiment, we excerpt the ﬁrst eight bars (Fig.
9). Although the original piece includes multiple voices, our framework can only
treat monophony; therefore, the original piece is arranged into a monophony. We

CMMR2013 - 424

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

Cognitive Similarity Grounded by Tree DistancedŚĞŵĞ2&4 œ œ

œ œ

œ œ

œ œ

œ œ

œ œ

11

œ œ. œ ˙sĂƌŝĂƚŝŽŶƐ

œœ
2
œ
œ
& 4 œœ œ œ œ œœ# œœœœœœ b œn œœœ œœœ œœ œœœœ œœ œœœœœ œœœœœœœœ œ œ œ ˙œ œ œœ2 œœœœœœœ œœœœœœœ œœœœœœœ œœœœœœœ œœb n œ œœœ œb œn œ œœœ œ# œœ
b n œ œœEŽ͘Ϯ & 4
œ
œ
œ
œ
œ œ
œ
œ œœ
œ
œ
œ
œ
œ
œ
œ
œ œ œœœ œœ3œ œ œ œ œ œ œb œn œ œ œ œ œ# œœœ œ
œœœ
œ
œœœ
2
œ
œ
œ ˙
EŽ͘ϯ & 4
œ
œ
œ 3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
œ
2
œ œ œ œ œ œ œ œ œ œ œ œ œ œ œ b œn œ b œn œ œœ b œn œ œ # œœ œ œEŽ͘ϰ & 4œœœœ 3 œœ 3 œ 3 œœ 3 œ œ œ œ
œœ
œ
œ
œ
œ
œ œ
œ œ œ œ œ œ œ œ œœœ? 2 œœœœœœœœ œ œ œ œ
EŽ͘ϱ
œ
4
œ œ
œ
b n œœœœœ œœœœœœ
2œœœœœœœœ œœœEŽ͘ϲ & 4œ
b n œœ œœœ œ# œœ
œ
œ
œ
œ
œ
œ
œ
œ
œ œ œœ œœœœœœœœœ œœœœœœ œ
œ
œ
œ
œ
œ
œ œœ# œœ œœœ œn œ œ œ œœ œ œ œ œ
œ
œ
œ
œ
#
œ
n
œ
œ
œ
œ
2
EŽ͘ϳ & 4œœ œœœ
r r r rœ œ rœ œ rœ œ rœ œœœœœœœ œ œ #œ œ˙œ nœbb 2 œ œ œ œ œ œ œ œ œ œ œ œ œ œ œ n œ ˙bEŽ͘ϴ &
4
EŽ͘ϭ

œ œ

œ œ

œ œ

œ œ

œ œœ œœœœ ˙
JJ
2 r œ œ œR œ œR œ œR œ œR œ œR œ brœœn œ rœ# œœ b œn œn œ rœ n œb œœ œ œ œEŽ͘ϭϬ & 4œ œr œ œ œ r œrœ œœrn œ œ œœ œ œRœœœ œ œ œ œ œ œ œ œ œ œ# œ
#œ
œ
œ
œ
œ
œ œ œ#. œœ .œœœœn œœœœœ œ
2 œ . œ œ Jœ œJ œ Jœ Jœ œ Jœ œœœ .
œ
.
œœ œ
œ
E ϭϭ & 4 œ . œ œ J
EŽ͘ϭϭ
œ
J
2
EŽ͘ϵ & 4 œ œœ œ œ ˙ œ . #œ œ #˙ nœ . œ œ ˙
˙
3
œ
.
˙
œ
.
œ
œ
œ. œœ œ œ œ ˙.
œœEŽ͘ϭϮ & 4
Fig. 9. Monophonic melodies arranged for experimentextract salient pitch events from each one of two voices, choosing a prominent
note from a chord, and disregard the diﬀerence of octave so that the resultant

CMMR2013 - 425

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 201312

K. Hirata, S. Tojo, and M. Hamanaka

melody is heard smoothly. In total, we have the theme and twelve variations(eight bars long) and obtain 78 pairs to be compared (13 C2 = 78).
For the similarity assessment by human listeners, eleven university students
participate in our study, seven out of whom have experiences in playing music
instruments more or less. An examinee listens to all pairs m1 , m2 in the random
order without duplication, where m{1,2} is either themeor variations No.1 to 12.
Every time he/she listens to it, he/she is asked “how similar is m1 to m2 ?”, andranks it in one of ﬁve grades among quite similar = 2, similar = 1, neutral = 0,
not similar = −1, and quite diﬀerent = −2. At the very beginning, for cancellingthe cold start bias, every examinee hears the theme and twelve variations (eightbars long) through without ranking them. In addition, when an examinee listens
to and rank pair m1 , m2 , he/she should try the same pair later to avoid theorder eﬀect. Finally, the average rakings are calculated within an examinee andthen for all the examinees.
For the calculation by the proposed framework, we use the meet-oriented
distance introduced in Section 4.2. From Deﬁnitions 3 and 4, the distance ismeasured by a note duration, we set the unit of distance to one third of thesixteenth note duration so that a music piece not only in quadruple time but
also in triple time can be represented. The correct time-span trees of the theme
and twelve variations are ﬁrst created by the authors and are next cross-checkedto each other. Note that the meet operation takes into account only the conﬁguration of a time-span tree, not pitch events; it is obvious from Deﬁnitions 3
and 4.

6

Results and Analysis

The experimental results are shown in the distance-matrix (Table 1). The theoretical estimation (a) means the results of calculation by the meet operation,and the human listeners (b) means the psychological resemblance by examinees.
In (a), since the values of meet(m1 ,m2 ) and meet(m2 ,m1 ) are exactly the same,
only the upper triangle is shown. In (b), if an examinee, for instance, listen to
Theme and variation No.1 in this order, the ranking made by an examinee isfound at the ﬁrst row, the second column cell (-0.73). The values in (b) are theaverages over all the examinees.
It is diﬃcult to examine the correspondence between the results of calculatedby the meet operation (a) and the psychological resemblance by examinees (b)in this distance-matrix. Then, we employ multidimensional scaling (MDS) [20]to visualize the correspondence. MDS takes a distance matrix containing dissimilarity values or distances among items, identiﬁes the axes to discriminate items
most prominently, and plots items on the coordinate system of such axes [20].
Putting it simply, the more similar items are, the closer they are plotted on acoordinate plane.
First, we use the Torgerson scaling of MDS to plot the proximity among the
13 melodies, however, it is still diﬃcult to ﬁnd a clear correspondence. Therefore,
we restrict plotting melodies to the theme and variations No.1 to 9 (Fig. 10).

CMMR2013 - 426

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

Cognitive Similarity Grounded by Tree Distance

13

Table 1. Calculation by meet operation and psychological resemblance(a) Theoretical estimation
No.1 No.2 No.3 No.4 No.5 No.6 No.7 No.8 No.9 No.10 No.11 No.12
Theme 183 177 195 183 117 249 162 15 21 363 262.5 246
No.1 – 228 332 326 264 360 219 174 204 456 409.5 421
No.2 –– 264 216 246 282 105 168 186 438 391.5 423
No.3 ––– 252 262 320 259 188 198 462 334.5 379
No.4 –––– 238 246 213 176 186 424 387.5 399
No.5 ––––– 276 243 114 108 414 298.5 325
No.6 –––––– 291 234 264 378 409.5 449
No.7 ––––––– 153 171 429 376.5 400
No.8 –
–
–
–
–
–
–
–
30 348 259.4 255
No.9 –
–
–
–
–
–
–
–
–
378 277.5 261
No.10 –
–
–
–
–
–
–
–
–
– 406.5 403
No.11 –
–
–
–
–
–
–
–
–
–
– 298.5(b) Rankings by human listeners (listening in row→column order)
Theme No.1 No.2 No.3 No.4 No.5 No.6 No.7 No.8 No.9 No.10 No.11 No.12
Theme– -0.73 -0.91 -1.09 -0.82 1.18 -1.00 -1.45 -0.64 1.36 0.64 0.73 1.00
No.1 -1.00– -0.82 -0.73 -0.91 -0.64 0.36 -0.64 -1.45 -0.82 -0.82 -1.00 -0.64
No.2 -0.91 -0.36– -0.64 -0.27 -0.82 -0.45 -0.55 -1.55 -0.91 -0.09 -0.64 -0.91
No.3 -0.82 -0.45 -0.82–
0 -0.91 -1.00 -0.36 -1.36 -0.73 -0.64 -0.73 -0.91
No.4 -1.00 -0.82 -0.73 0.18
– -0.73 -0.82 -0.82 -1.73 -0.91 -0.45 -1.27 -1.00
No.5
1.27 -1.18 -0.91 -0.91 -0.64– -0.82 -1.09 -1.00 0.73 0.55 0.36 0.73
No.6 -1.18 0.27 -0.27 -0.45 -0.82 -0.64– -0.36 -1.64 -0.91 -0.55 -0.64 -0.91
No.7 -1.18 -0.64 -0.45 -0.18 -0.82 -0.73 -0.64– -1.18 -0.73 -0.36 -0.64 -0.73
No.8 -0.73 -1.27 -1.36 -1.55 -1.27 -0.73 -1.00 -1.36– -0.09 -1.09 -0.64 -0.91
No.9
1.27 -0.91 -0.91 -0.73 -1.09 0.91 -1.27 -0.82 -0.18–
0.55 0.45 1.00
No.10
0.55 -0.82 -0.27 -0.64 -0.36 0.73 -0.45 -0.82 -1.00 0.73–
0.18 0.45
No.11
0.64 -0.82 -0.91 -0.73 -0.91 0.55 -0.91 -1.09 -0.73 0.64 0.27
–
1.00
No.12
1.09 -1.18 -1.09 -1.00 -1.00 0.91 -1.00 -1.18 -0.91 1.09 0.36 0.82–

Theme and No.i in the ﬁgure correspond to those in Fig. 9, respectively (i = 1..9).
The contributions in MDS are as follows: (a) Theoretical estimation: ﬁrst axis
(horizontal) = 0.23, second = 0.21; (b) Human listeners: ﬁrst axis (horizontal)= 0.33, second = 0.17.
In the ﬁgure, we can ﬁnd an interesting correspondence between (a) and (b)in terms of positional relationships among 10 melodies. In both (a) and (b), we
ﬁnd that Theme, No.5, No.8, and No.9 make a cluster; so No.3 and No.4 do; so
No.2 and No.7 do. The positional relationship among the cluster of Theme, No.5,
No.8 and No.9, that of No.2 and No.7, and that of No.3 and No.4 resembles eachother. The positional relationship between No.1 and the others, except for No.6,
resembles, too. Since the contributions in the ﬁrst axis of (a) are considered close
to the second, by rotating the axes of (a) −90 degrees (counter clockwise), a moreintuitive correspondence may be obtained. On the other hand, the discrepancy
between (a) and (b) is seen, too; the positional relationship between No.6 andCMMR2013 - 427

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 201314

K. Hirata, S. Tojo, and M. Hamanaka

Fig. 10. Relative distances among melodies in mutidimensional scaling

the others is signiﬁcantly diﬀerent. rom the above, we argue that the operations
on time-span trees of our framework are viable to a certain extent.

7

Concluding Remarks

We assumed that cognitive similarity should reside in the similarity of time-spantrees, that is, the reduction ordering in time-span trees were heard similarly inthe order of resemblance to human ears. Based on this assumption, we proposeda framework for representing time-span trees and processing them in the algebraic manner. In this paper, we examined the validity of the framework throughthe experiments to investigate the correspondence of theoretical similarity withpsychological similarity. The experimental results supported the convincing correspondence to some extent.
Here we have four open problems. Firstly, we exclude variations No.10 to 12
for visualization in Fig. 10. Here, we need to consider why variations No.10 to
12 could not achieve a higher correspondence. As possible reasons, we speculate No.10 contains reharmonization, No.11 features ornamental 32nd notes andNo.12 is a music piece in triple time. Thus, we are interested in an even moregeneralized distance that is robust to these variations.
Secondly, in terms of the contributions in MDS, the third axis in theoreticalestimation which is not depicted in Fig. 10 is 0.17, and that in human listeners
0.16. Since the third axis is still relatively signiﬁcant, the dimension may reveal
another hidden grouping among 13 music pieces.
Thirdly, at present, our framework disregards matching of pitch events; themeet/join operations use only the conﬁguration of time-span trees. When timespan trees have been constructed, however, it is supposed that the relationshipamong pitches within a music piece inﬂuences the conﬁguration of a time-span

CMMR2013 - 428

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 2013

Cognitive Similarity Grounded by Tree Distance

15

tree being constructed. Thus, even without matching of pitch events, the resultof meet/join operation more or less reﬂects the relationship among pitches indirectly. To achieve the similarity that truly coincides with our cognition, we
should formalize the operations on pitch events.
Fourthly, in several cases, the join operation could not be calculated as waspointed out in Fig. 6. Besides, polyphonic melodies could not be handled by
our framework. Since these limitations degrade the applicability of our framework, we should extend the representation method of a music piece and tolerate
the condition of the join operation, preserving the consistency with the meet
operation and vice versa.
Further, future work includes building a large corpus that contains more diverse melodies and conducting experiments for us to investigate the correspondence of theoretical similarity with psychological similarity in more detail. For
the purpose of reproducing and rechecking the experiments by other researchers,
we are preparing to distribute the Prolog program shown in Section 4.2.
Acknowledgments.
This work was supported by JSPS KAKENHI Grant Number 23500145. The
authors would like to thank the anonymous reviewers for their constructive comments to improve the quality of the paper.

References
1. Bod, R.: A Uniﬁed Model of Structural Organization in Language and Music. Journal of Artiﬁcial Intelligence Research 17, 289–308 (2002)
2. Carpenter, B.: The Logic of Typed Feature Structures. Cambridge University Press(1992)
3. de Haas, W.B.: Music Information Retrieval Based on Tonal Harmony. Ph.D. thesis,
Utrecht University (2012)
4. ESCOM: 2007 Discussion Forum 4A. Similarity Perception in Listening to Music.
MusicæScientiæ
5. ESCOM: 2009 Discussion Forum 4B. Musical Similarity. Musicae Scientiae
6. Forte, A., Gilbert, S.E.: Introduction to Schenkerian Analysis. Norton. New York(1982)
7. Grachten,
M.,
Arcos,
J.-L.,deMantaras,
R.L.:
MelodyretrievalusingtheImplication/Realization
model.
2005
MIREX.
http://www.music-ir.org/evaluation/mirexresults/articles/similarity/
grachten.pdf, Accessed on June 25 (2013)
8. Hamanaka, M., Hirata, K., Tojo, S.: Implementing “A Generative Theory of Tonal
Music”. Journal of New Music Research 35(4), 249–277 (2007)
9. Hewlett, W.B., Selfridge-Field E. (Eds): Melodic Similarity - Concepts, Procedures,and Applications. The MIT Press, Computing in Musicology 11 (1998)
10. Lerdahl, F., Jackendoﬀ, R.: A Generative Theory of Tonal Music. The MIT Press,
Cambridge (1983)
11. Marsden, A.: Generative Structural Representation of Tonal Music. Journal of New
Music Research 34(4), 409–428 (2005)

CMMR2013 - 429

Proc. of the 10th International Symposium on Computer Music Multidisciplinary Research, Marseille, France, October 15-18, 201316

K. Hirata, S. Tojo, and M. Hamanaka

12. MIREX HOME. http://www.music-ir.org/mirex/wiki/MIREX HOME, Accessedon June 25 (2013)
13. Pampalk, E.: Computational Models of Music Similarity and their Application inMusic Information Retrieval. PhD Thesis, Vienna University of Technology (March
2006)
14. Pearce, M.T. and Wiggins, G.A.: Expectation in Melody: The Inﬂuence of Context
and Learning. Music Perception, Vol.23, Issue 5, pp. 377–405 (2006)
15. Rizo-Valero, D.: Symbolic Music Comparison with Tree Data Structure. Ph.D.
Thesis, Universitat d’ Alacant, Departamento de Lenguajes y Sistemas Informatı́cos(2010)
16. Schedl, M., Knees, P., Böck, S.: Investigating the Similarity Space of Music Artists
on the Micro-Blogosphere. In: Proceedings of ISMIR 2011, 323–328
17. Tojo, S., Hirata, K.: Structural Similarity Based on Time-Span Tree. In: 10th
International Symposium on Computer Music Multidisciplinary Research (CMMR),
pp. 645–660 (2012)18. van Kranenburg, P.: A Computational Approach to Content-Based Retrieval of
Folk Song Melodies. Ph.D. thesis. Utrecht University (2010)
19. Volk, A., Wiering, F.: Tutorial Musicology, Part 3: Music Similarity. 12th
International Society for Music Information Retreival Conference (ISMIR 2011)
http://ismir2011.ismir.net/tutorials/ISMIR2011-Tutorial-Musicology.pdf,
Accessed on June 15 (2013)
20. Wikipedia, Multidimensional scaling.
http://en.wikipedia.org/wiki/Multidimensional scaling, Accessed on June 15(2013)
21. Wikipedia, Temporal Logic. http://en.wikipedia.org/wiki/Temporal logic,
Accessed on June 25 (2013)
22. Wilson, R.A., Keil, F. (Eds): The MIT Encyclopedia of the Cognitive Sciences.
The MIT Press (1999)

CMMR2013 - 430