Music information retrieval (MIR) is small, but fast growing discipline. It aims at extraction of relevant information from music in order to improve the work with multimedia information systems. A popular approach in MIR is to apply signal processing techniques to extract low-level features from a musical piece. However, in order to create helpful applications, high-level concepts, such as music harmony, need to be examined as well. In this paper, we present a new model for understanding music harmony in computer systems. The proposed model takes the challenge of lling the gap between music theory and mathematical structures. Inspired by the computational complexity, we then derive a new term, harmonic complexity, that can be evaluated for a musical piece, and we test it on a genre classi cation problem.
A massive distribution of digital media has made music information retrieval
(MIR) a wanted eld of study. Musicians and non-musicians both bene t from
applications that ease their work with music, such as notation software or
internet radios. One of the recent challenges has been to develop an intelligent
retrieval of musical piece based on user preferences (Schonfuss [
Content-based recommendation or classi cation can be addressed using rules
of music acoustics, by computing the Discrete Fourier Transform (DFT), and
dealing with the frequency-domain features (Li [
Tonal harmony. Music theory is a highly developed eld that provides us
with a framework for working with musical structures. In our work, we choose
music theory, and in particular, tonal harmony (TH), to help us understand
one of the important aspects in music. Our focus on tonal harmony comes from
understanding, that acoustic sounds (tones) sounding simultaneously form
structures, which even listeners without explicit musical training implicitly recognize
(Krumhansl [
We are motivated by the fact, that although TH is a stable theory based
on music acoustics (e.g. Schonberg [
To summarize, the main contributions of this paper are: De ning a new term, harmonic complexity, that can be used as a new musical feature to aid the content-based music recommendation and music classi cation tasks Proposing a mathematical model based on tonal harmony, reusable for future harmony-related tasks Testing the proposed model and harmony complexity evaluations on a music classi cation problem
After providing de nitions of TH, we summarize the results of the related work in Section 3. We then describe our model of harmonic complexity in Section
4. Afterwards, we propose its usefulness for music classi cation challenge in Section 5. In the end we provide conclusion and discuss the future work, as well as the connection of our research to music recommendation task. 2
In this section we provide brief de nitions of TH, based on Schonberg [
We further make use of the concept of basic harmonic functions
characteristic for each key. The harmony in music usually starts in the tonic, a function
of harmonic steadiness and release. Optionally, it deviates to the subdominant.
Finally, the harmonic movement culminates in the dominant, a function
representing the maximal tension, requiring a transition back to the tonic. According
to Zika [
In addition to the three basic harmonic functions, there are also variants, or
parallels of the basic harmonic functions. We provide a simpli ed de nition of a
function parallel based on the original de nition by Riemann [
An example parallels for the C major chord c, e, g are c, e, a or b, e, g.
We also add a de nition from one of the modern interpretations of TH,
described by Volek [
An example of a chord with an added dissonance is c, e, f , g, with the tone f added to the original C major chord c, e, g.
Some well-known tunes have a simple harmonic structure, for example Happy Birthday : T { D { T { S { T { D { T . However, more complex compositions, such as Smetana's Vltava from Ma vlast can be interpreted as: T { SP (D) { TP (T ) { S { T { D { T . We can notice the use of the function parallels. Moreover, some functions can have multiple meanings, if we consider switching to a di erent key (functions in the parentheses). We capture this principle in the next section. 3
In this section we provide the summary of the work most related to ours.
De Haas, Magalh~aes, and Wiering [
Lots of works have been done on tonal tension (see Lerdahl and Krumhansl
[
Finally, the works on chord distance are closely related to our research. In
his inspiring work, Lerdahl [
If new concepts are to be designed, they need to be in accordance with previous research.
The basic idea of our model is simple: The use of basic harmonic functions does not increase harmonic complexity. However, every single use of a parallel or added dissonances increase the complexity of a musical piece. We can recognize the use of complex harmonies by evaluating each pair of succeeding chords { evaluating their harmonic transition. If we shape the three basic transitions (between T , S, D) in a triangle, the idea of increasing complexity can be illustrated as in the Figure 2.
We base our model on the overtone series and consequent harmony rules by
Schonberg [
We also merge the concepts of a function parallel and a chord with an added dissonance de ned in Section 2, since both are a way to modify the basic harmonic function. The aim here is to generalize the process of creating complex harmonies, while focus on speci c aspects will be a subject of our future work. 4.1
We now want to evaluate the transition from the basic harmonic function to its parallel (e.g. T ! TP ) and in between the parallels (e.g. TP ! SP ). That alone can give us information how much the music deviates from the simplest progression and translates to harmonic complexity. We use a linguistic approach to evaluate these transitions.
First of all, let us consider the simplest case: T ! TP . We wish to create a parallel either by adding a tone or modifying a tone. Formally, we de ne a sentential form as a form of chord notation and two di erent parametric rules to modify the sentential form: add(t) and alter(t,alt).
De nition 3. A chord is written in sentential form t1t2:::tn if it consists of the tones t1; t2; : : : ; tn, and for i 6= j: ti 6= tj , moreover t1 : : : tn are ordered in the order of the chromatic scale.
The sentential form is therefore only an ordered enumeration of chord's tones,
neglecting the duplicity (working in one octave). We further de ne the transition
rules between the sentential forms in the same fashion as Hopcroft, Motwani,
and Ullman [
De nition 4. The add(t) rule between two sentential forms h and g is de ned as follows: h add(!t) g , (h = t1; t2; : : : tn) ^ (g = t1; : : : tj ; t; tj+1; : : : tn), where t belongs to the same key as t1 : : : tn, and 8i : t 6= ti.
We wish to simulate both adding dissonances and creating Riemann's
parallels. We choose an approach which can be confusing at rst { both
transformations can be achieved using the add rule. If we set, that the basic harmonic
function that we start with does not necessarily need to contain 3 tones, but
possibly also a single tone or two tones (substituting the basic harmonic function),
using add rule we can indeed get a Riemann's function parallel. For example,
we can get a parallel cea as ce + a, where ce substitutes the tonic ceg in C
major. The alter rule will therefore have a di erent role { moving the tone outside
the key, and so creating sharp dissonances and alterations in the way that TH
describes them [
De nition 5. The alter(t,alt) rule between two sentential forms h and g is de ned as follows: h alter(t;al!t) g , (h = t1; : : : :::ti; t; ti+1; : : : tn) ^ (g = t1; : : : ti; talt; ti+1; : : : tn); where t belongs to the same key as t1 : : : tn, talt does not belong to that key, and talt is created from t by augmentation (alt = ]) or diminution (alt = [) by a semitone. Moreover, t can not be one of the tones of the original basic harmonic function of h (the basic harmonic function that the whole derivation started with).
The constrains we cast on the add and alter rules yield the rules of TH. First
of all, we can not modify the original tones, because we do not want to lose the
sense of the basic harmonic function. If we wish to weaken the basic harmonic
functions, we always have the possibility to start with only a subset if its tones.
Secondly, we can add the tones, but only from the same key. And thirdly, we
can alter the tones to a di erent key, but only after they have been added. Such
hierarchy agrees with Lerdahl's de nition of tonal pitch space [
Note that, using add and alter rules we are able to create arbitrary harmonies. The only thing we need to keep in mind is, that given a sentential form h, we rst have to nd out, which key h belongs to. There are 24 possibilities, comprising 12 major and 12 minor keys. Then we can apply the add and alter rules. Remark 1. In a simple example we derive the tonic parallel (TP ) cef ]g] from the original tonic (T ) ce, in the key C major : ce add(f!) cef alter(f;]!) cef ] add(g!) cef ]g alter(g;]!) cef ]g].
We rst de ne a chord complexity for a simple chord. Then we proceed to de ne a transition complexity between two chords.
De nition 6. A chord complexity (in the given key) c(h) of chord h is the minimal length of derivation of the chord's sentential form (in the given key). Remark 2. For our example tonic parallel: cef ]g], the chord complexity in the key C major is 4. However, overall chord complexity for this chord can be even lower. If we choose the key G major and treat the form ce as a subdominant in G major, we will have 3 as the resulting chord complexity (due to the fact that the tone f ] can be added in one step { it is a part of the key G major.
Understanding that the chord h can be treated in multiple keys, have multiple derivations and multiple chord complexities, we always use the shortest derivation (lowest complexity) to de ne the chord. We label such chord complexity c(h). We use similar approach in our nal de nition { chord transition complexity.
De nition 7. Let us have the sentential form of chord h1 and the sentential form of chord h2. We de ne a chord transition complexity tc(h1; h2). We differentiate between these possibilities: 1. Let us assume, that there is a common ancestor in both derivations of h1 and h2 { a sentential form a, that h1 and h2 can be both derived from, h1 in k1 steps, and h2 in k2 steps. Then if k1 +k2 c(h1)+c(h2), the chord transition complexity tc(h1; h2) equals to k1 + k2. Otherwise, tc(h1; h2) = c(h1) + c(h2). 2. Let us assume, that there is no such common ancestor. 9r1; r2; kh1; kh2 : h1 can be derived from an original basic harmonic function r1 in kh1 steps, h2 can be derived from an original basic harmonic function r2 in kh2 steps. (a) Let us assume that r1, r2 are such basic harmonic functions, that are from the same key and the sum kh1 + kh2 is minimal. Then the chord transition complexity tc(h1; h2) equals to kh1 + kh2. (b) The common key for r1 and r2 does not exist. Then the chord transition complexity tc(h1; h2) equals to u1 + u2, where u1 is the number of steps required to derive h1 from the empty sentential form, and u2 is the number of steps required to derive h2 from the empty sentential form.
In other words, we de ne the transition complexity between two chords as the amount of steps needed to disassemble the rst chord into its basic harmonic function (rolling back the derivation), then we switch the function and count the number of steps to assemble the new chord. The resulting number of steps is the transition complexity. If there is a common ancestor in derivations, closer than the basic harmonic function, we disassemble and assemble only to and from this common ancestor. Finally, if no common key can be found for the two harmonies, we choose to disassemble the rst chord all the way to an empty sentential form, and construct the second chord from an empty sentential form.
In all of these cases, it is only a simple constructing and destructing the chords, using our derivation rules. This is when the analogy with computational complexity comes in { the chord transition complexity can be understood as the computational complexity of reconstructing the chord h1 to h2. The illustration of chord transition complexity can be found in the Figure 3.
Fig. 3. Chord transition complexity: The chords SP 1 and SP 2 have a common ancestor in the derivation, and are assigned a chord transition complexity of 5. The chords SP 2 and DP do not have a common ancestor in derivation, therefore their chord transition complexity is equal to the sum of their chord complexities. 4.2
Finally, we can proceed to evaluation of harmonic complexity for a whole piece. We have a musical piece M . We can use di erent algorithms (some of them are described in the Section 5) to extract the sequence of chords fCigi l of the length l. Keeping in mind the analogy with the computational complexity, we are interested in obtaining an average number of steps needed to construct a chord from the basic harmonic functions. We average the values because we want to abstract from the length of the progression, in the same fashion as the computational complexity theory abstracts from the length of the input. Other interesting statistical values for harmonic complexity will be the subject of our future work.
De nition 8. An average transition complexity (ATC) for a musical piece M , a sequence of chords fCigi l of the length l and a sequence of its transition complexities ftigi l 1 is de ned as follows: l 1
P ti AT C(M ) = i=0 l 1 4.3
Understanding that, for a given chord, multiple basic harmonic functions can be found, along with multiple di erent keys, the model can become di cult to implement. We propose two methods of implementation, based on internal representation of musical data: 1. Query method { The fundamental rules of TH (keys, basic harmonic functions) are saved in a database and a number of queries precedes the calculation of transition complexity for chords. 2. Graph method { We can also abstract from the ambiguity of keys and functions and avoid complicated queries. Working within the bounded space of all possible sets of tones in the octave, we have designed our derivation rules in such fashion, that for a given chord it is easy to calculate all chords with transition complexity of 1 from a given chord. That approach can result in constructing a graph representation of the problem, with edges representing a transition complexity of 1. On such a graph, queries can be easily implemented using the breadth- rst search algorithm. 5
In our experiments, we focused on determination, whether the newly de ned concept of harmonic complexity can be a good descriptor for music classi cation task. The aim is to show that ATC values (see De nition 8) can distinguish the di erent genres, artists in one genre, or even the songs from the same artist.
The dataset was selected from the top 5 best-selling artists in 2013, according to renowned worldwide music charts and separate for each genre: Rock and Pop5, Jazz6 and Classical music7. In each genre, 25 di erent pieces were analyzed.
For obtaining a chord sequence, Vamp-plugins NNLS Chroma and Chordino8
version 0.2.1 by Mauch [
We split the experiments into 3 parts. 1. First we measure the mean ATC for di erent genres. Since the Classical music developed historically and particular music periods are known to obey certain composition styles, we show the same type of analysis for music periods of Classical music. 2. Second we measure the mean ATC for di erent artists from the Rock genre. 3. Third we measure the ATC found for di erent songs selected from the 2 artists of Rock music: The Beatles and Queen.
The Figure 4 shows the result of the analysis. ATC values around 1 means that the transitions were not complex and aligned with the basic tonal harmony theory. On the other hand, values above 3 meant that the transitions needed on average more than 3 steps. We can see how our model gives the highest ranking to the Jazz music. Rock music averaged around 2 and the lowest rankings were assigned to Pop songs. This aligns with the expectations. There is an ambiguity between Rock and Pop genres, that is understandable, because the genres may overlap.
In Classical music periods we can observe how the music has developed through the centuries. This also corresponds with the theoretical knowledge, knowing that after Romanticism, the composers began to break the established harmony rules.
We have also discovered some interesting results about the concrete artists and songs. Queen songs were analyzed to be considerably more complex than the rest of the Rock artists, that can be attributed to their famous ensembles sounding together in an unusual way. Some particular songs have the ATC value that is out of the area where the songs of the same genre belong to with high probability (highlighted). In one particular case (Radio Ga Ga by Queen), we can conclude that, in correspondence with our results, the harmonic movements of the song are really considered to be less complex, since the song is known to have more popular genre than the rest of Queen's production. The song Let It Be by The Beatles is also known for its repetitive chorus containing 4 basic chords.
In this paper we have proposed a new term that can be evaluated for a musical piece { harmonic complexity. We have presented a mathematical model based on tonal harmony, for evaluating harmonic complexity. Lastly, we have successfully conducted a series of experiments to prove that the new feature is relevant for music classi cation task. The results correspond with the expectations. Knowing that our model can evaluate the harmonic movements precisely we propose using this technique to obtain music descriptors for future music classication attempts.
In the discussion we would also like to propose an idea of content-based music
recommendation based on harmonic complexity. As Zanette pointed out [
For future work, we propose music classi cation experiments with the use of harmonic complexity as one of the music features. We also realize that harmonic complexity as described is only one of the possible implementations of the broad term of complexity in music and much can be done in specifying other similar measures (space complexity, complexity of modulations, the use of seventh chords, etc.). We hope that by showing this point of view we have induced some new ideas for the future research.
Acknowledgments. The study was supported by the Charles University in Prague, project GA UK No. 708314.