MIREX Wiki - User contributions [en]

2013:Discovery of Repeated Themes & Sections Results

2013-10-30T19:06:12Z

David Meredith: /* Ground Truth and Algorithms */

== Introduction ==

The task: algorithms take a piece of music as input, and output a list of patterns repeated within that piece. A pattern is defined as a '''set of ontime-pitch pairs''' that occurs twice (i.e., is repeated at least once) in a piece of music. The second, third, etc. occurrences of the pattern will likely be shifted in time and/or transposed, relative to the first occurrence. Ideally an algorithm will be able to discover all exact and inexact occurrences of a pattern within a piece, so in evaluating this task we are interested in both:
*(1) to what extent an algorithm can discover one occurrence, up to time shift and transposition, and;
*(2) to what extent it can find all occurrences.
The metrics '''establishment recall''', establishment precision and establishment F1 address (1), and the metrics '''occurrence recall''', occurrence precision, and occurrence F1 address (2).

== Contribution ==

Existing approaches to music structure analysis in MIR tend to focus on segmentation (e.g., Weiss & Bello, 2010). The contribution of this task is to afford access to the note content itself (please see the example in Fig. 1A), requiring algorithms to do more than label time windows (e.g., the segmentations in Figs. 1B-D). For instance, a discovery algorithm applied to the piece in Fig. 1A should return a pattern corresponding to the note content of <math>P_1</math> and <math>P_2</math>, as well as a pattern corresponding to the note content of <math>Q_1</math>. This is because <math>Q_1</math> occurs again independently of the accompaniment in bars 19-22 (not shown here). The ground truth also contains nested patterns, such as <math>P_1</math> in Fig. 1A being a subset of the sectional repetition <math>S_1</math>, reflecting the often-hierarchical nature of musical repetition. While we recognise the appealing simplicity of linear segmentation, in the ''Discovery of Repeated Themes & Sections'' task we are demanding analysis at a greater level of detail, and have built a ground truth that contains overlapping and nested patterns.

[[File:mozartK282Mvt2.png|500px]]

'''Figure 1.''' Pattern discovery v segmentation. (A) Bars 1-12 of Mozart’s Piano Sonata in E-flat major K282 mvt.2, showing some ground-truth themes and repeated sections; (B-D) Three linear segmentations. Numbers below the staff in Fig. 1A and below the segmentation in Fig. 1D indicate crotchet beats, from zero for bar 1 beat 1.

For a more detailed introduction to the task, please see [[2013:Discovery_of_Repeated_Themes_&_Sections]].

== Ground Truth and Algorithms ==

The ground truth, called the '''Johannes Kepler University Patterns Test Database''' (JKUPTD-Aug2013), is based on motifs and themes in Barlow and Morgenstern (1953), Schoenberg (1967), and Bruhn (1993). Repeated sections are based on those marked by the composer. These annotations are supplemented with some of our own where necessary. A Development Database (JKUPDD-Aug2013) released in March enabled participants to try out their algorithms. For each piece in the Development and Test Databases, symbolic and synthesised audio versions are crossed with monophonic and polyphonic versions, giving four versions of the task in total: symPoly, symMono, audPoly, and audMono. Algorithms submitted to the task are are shown in Table 1.

{| border="1" cellspacing="0" style="text-align: left; width: 800px;"
|- style="background: yellow;"
! width="80" | Sub code
! width="200" | Submission name
! width="80" style="text-align: center;" | Abstract
! width="440" | Contributors
|-
|- style="background: green;"
! Task Version
! symPoly
!
!
|-
! NF2
| motives_poly || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/NF2.pdf PDF] || [http://files.nyu.edu/onc202/public/ Oriol Nieto], [http://www.nyu.edu/projects/farbood/ Morwaread Farbood]
|-
! DM10
| SIATECCompressSegment || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM10.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM9
| SIATECCompressRaw || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM9.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM8
| SIATECCompressBB || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM8.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM7
| COSIATECSegment || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM7.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM6
| COSIATECRaw || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM6.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM5
| COSSIATECBB || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM5.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|- style="background: green;"
! Task Version
! symMono
!
!
|-
! NF1
| motives_mono || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/NF1.pdf PDF] || [http://files.nyu.edu/onc202/public/ Oriol Nieto], [http://www.nyu.edu/projects/farbood/ Morwaread Farbood]
|-
! DM10
| SIATECCompressSegment || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM10.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM9
| SIATECCompressRaw || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM9.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM8
| SIATECCompressBB || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM8.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM7
| COSIATECSegment || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM7.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM6
| COSIATECRaw || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM6.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM5
| COSSIATECBB || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM5.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|- style="background: green;"
! Task Version
! audPoly
!
!
|-
! NF4
| motives_audio_poly || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/NF4.pdf PDF] || [http://files.nyu.edu/onc202/public/ Oriol Nieto], [http://www.nyu.edu/projects/farbood/ Morwaread Farbood]
|- style="background: green;"
! Task Version
! audMono
!
!
|-
! NF3
| motives_audio_mono || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/NF3.pdf PDF] || [http://files.nyu.edu/onc202/public/ Oriol Nieto], [http://www.nyu.edu/projects/farbood/ Morwaread Farbood]
|}

'''Table 1.''' Algorithms submitted to DRTS.

== Results ==

For mathematical definitions of the various metrics, please see [[2013:Discovery_of_Repeated_Themes_&_Sections#Evaluation_Procedure]].

=== In Brief ===

To avoid a bias toward the more numerous submissions of Meredith (2013), DM10 was preselected for comparison with Nieto and Farbood's (2013) submissions, based on reported performance for the Development Database. Figure 2 shows establishment recall results on a per-pattern basis for the symbolic-polyphonic version of the task. DM10 outperforms NF2 according to Friedman's test (<math>\chi^2(1) = 12.7368,\ p < .001</math>), suggesting the former is preferable for discovering at least one occurrence of each ground truth pattern. This result addresses point (1) from the introduction.

Figure 3 shows occurrence recall results on a per-pattern basis for the symbolic-polyphonic version of the task. Again, DM10 outperforms NF2 according to Friedman's test (<math>\chi^2(1) = 11.2667,\ p < .001</math>), suggesting the former is preferable for retrieving all occurrences of a discovered ground truth pattern. This result addresses point (2) from the introduction.

It should be noted, however, that according to Friedman's test, algorithm NF2 is significantly faster than DM10 (<math>\chi^2(1) = 4.000,\ p < .05</math>), suggesting the former is preferable for rapid summarisation.

Results were similar but somewhat closer for the symbolic-monophonic version of the task. According to Friedman's test (<math>\chi^2(1) = 2.9512,\ p = .0858</math>, ns), NF1 and DM10 show no significant difference for establishment recall on a per-pattern basis (please see Figure 14). This result relates to point (1) from the introduction. Figure 15 shows occurrence recall results on a per-pattern basis for the symbolic-monophonic version of the task. DM10 outperforms NF1 according to Friedman's test (<math>\chi^2(1) = 11.6364,\ p < .001</math>), suggesting the former is preferable for retrieving all occurrences of a discovered ground truth pattern. This result relates to point (2) from the introduction.

For the audio versions of the task, algorithms NF3 (audMono) and NF4 (audPoly) were the only submissions. Nieto and Farbood (2013) are credited with being the first to define an algorithm for discovering repeated note content in a synthesised audio file that is time-locked to a symbolic representation. We include some results from these task versions, with future comparisons in mind (Figs. 26-49). Evidently the audio task was more challenging (cf. Figs. 2 and 26).

=== symPoly ===

[[File:01symPolyEstRecPerPatt.png|600px]]

'''Figure 2.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:04symPolyOccRecPerPatt.png|600px]]

'''Figure 3.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:01symPolyEstRec.png|400px]]

'''Figure 4.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:02symPolyEstPrec.png|400px]]

'''Figure 5.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:03symPolyEstF1.png|400px]]

'''Figure 6.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:04symPolyOccRecP75.png|400px]]

'''Figure 7.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:05symPolyOccPrecP75.png|400px]]

'''Figure 8.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:06symPolyOccF1P75.png|400px]]

'''Figure 9.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:07symPolyR3.png|400px]]

'''Figure 10.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:08symPolyP3.png|400px]]

'''Figure 11.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:09symPolyTLF.png|400px]]

'''Figure 12.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:10symPolyRuntime.png|400px]]

'''Figure 13.''' Log runtime of the algorithm for each piece/movement.

=== symMono ===

''(Poor performance here for algorithm NF1 on piece 2 is likely due to rounding errors in the discovery phase; not anything musically interesting. The task captain tried in vain to identify a workaround.)''

[[File:11symMonoEstRecPerPatt.png|600px]]

'''Figure 14.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:14symMonoOccRecPerPatt.png|600px]]

'''Figure 15.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:11symMonoEstRec.png|400px]]

'''Figure 16.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:12symMonoEstPrec.png|400px]]

'''Figure 17.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:13symMonoEstF1.png|400px]]

'''Figure 18.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:14symMonoOccRecP75.png|400px]]

'''Figure 19.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:15symMonoOccPrecP75.png|400px]]

'''Figure 20.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:16symMonoOccF1P75.png|400px]]

'''Figure 21.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:17symMonoR3.png|400px]]

'''Figure 22.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:18symMonoP3.png|400px]]

'''Figure 23.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:19symMonoTLF.png|400px]]

'''Figure 24.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:20symMonoRuntime.png|400px]]

'''Figure 25.''' Log runtime of the algorithm for each piece/movement.

=== audPoly ===

[[File:21audPolyEstRecPerPatt.png|600px]]

'''Figure 26.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:24audPolyOccRecPerPatt.png|600px]]

'''Figure 27.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:21audPolyEstRec.png|400px]]

'''Figure 28.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:22audPolyEstPrec.png|400px]]

'''Figure 29.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:23audPolyEstF1.png|400px]]

'''Figure 30.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:24audPolyOccRecP75.png|400px]]

'''Figure 31.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:25audPolyOccPrecP75.png|400px]]

'''Figure 32.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:26audPolyOccF1P75.png|400px]]

'''Figure 33.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:27audPolyR3.png|400px]]

'''Figure 34.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:28audPolyP3.png|400px]]

'''Figure 35.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:29audPolyTLF.png|400px]]

'''Figure 36.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:30audPolyRuntime.png|400px]]

'''Figure 37.''' Log runtime of the algorithm for each piece/movement.

=== audMono ===

[[File:31audMonoEstRecPerPatt.png|600px]]

'''Figure 38.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:34audMonoOccRecPerPatt.png|600px]]

'''Figure 39.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:31audMonoEstRec.png|400px]]

'''Figure 40.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:32audMonoEstPrec.png|400px]]

'''Figure 41.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:33audMonoEstF1.png|400px]]

'''Figure 42.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:34audMonoOccRecP75.png|400px]]

'''Figure 43.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:35audMonoOccPrecP75.png|400px]]

'''Figure 44.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:36audMonoOccF1P75.png|400px]]

'''Figure 45.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:37audMonoR3.png|400px]]

'''Figure 46.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:38audMonoP3.png|400px]]

'''Figure 47.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:39audMonoTLF.png|400px]]

'''Figure 48.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:40audMonoRuntime.png|400px]]

'''Figure 49.''' Log runtime of the algorithm for each piece/movement.

== Discussion ==

If an occurrence of a ground-truth pattern contains forty or more notes then, according to Fig. 2, it is likely that SIATECSegment (DM10, Meredith, 2013) and motives_poly (NF2, Nieto & Farbood, 2013) will return a pattern rated as at least 75% similar. When we restrict attention to these successful discoveries and ask to what extent can the algorithms retrieve all exact and inexact occurrences, we find that SIATECSegment performs relatively well (see nonzero entries for the black line in Fig. 3), with the exception of the first patterns in pieces 1 and 2. We conclude, therefore, that the discovery of repeated sections has been addressed well by the current submissions, but that the discovery of themes and motifs requires more attention in future iterations of this task.

When assembling the ground truth, it was remarkable that most often a motif occurs as a subset of a theme or repeated section, which is not surprising given Drabkin’s (2001) definition of a motif as ‘the shortest subdivision of a theme or phrase that still maintains its identity as an idea’. One suggestion for future work is to apply a discovery algorithm to find repeated sections, and then '''apply the algorithm again''' but to the '''output sections only''', in order to retrieve these nested and important musical motifs.

''(More detailed, per-piece feedback for each submission to follow.)''

== Tabular Versions of Plots ==

=== symPoly ===

<csv p=3>2013/drts/symPolyResults.csv</csv>

'''Table 2.''' Tabular version of Figures 4-13.

<csv p=3>2013/drts/symPolyResultsPerPatt.csv</csv>

'''Table 3.''' Tabular version of Figures 2 and 3.

=== symMono ===

''(Poor performance here for algorithm NF1 on piece2 is likely due to rounding errors in the discovery phase; not anything musically interesting. The task captain tried in vain to identify a workaround.)''

<csv p=3>2013/drts/symMonoResults.csv</csv>

'''Table 4.''' Tabular version of Figures 16-25.

<csv p=3>2013/drts/symMonoResultsPerPatt.csv</csv>

'''Table 5.''' Tabular version of Figures 14 and 15.

=== audPoly ===

<csv p=3>2013/drts/audPolyResults.csv</csv>

'''Table 6.''' Tabular version of Figures 28-37.

<csv p=3>2013/drts/audPolyResultsPerPatt.csv</csv>

'''Table 7.''' Tabular version of Figures 26 and 27.

=== audMono ===

<csv p=3>2013/drts/audMonoResults.csv</csv>

'''Table 8.''' Taublar version of Figures 40-49.

<csv p=3>2013/drts/audMonoResultsPerPatt.csv</csv>

'''Table 9.''' Tabular version of Figures 38 and 39.

== References ==

*Harold Barlow and Sam Morgenstern. (1948). ''A dictionary of musical themes''. Crown Publishers, New York.
*Siglind Bruhn. (1993). ''J.S. Bach's Well-Tempered Clavier: in-depth analysis and interpretation''. Mainer International, Hong Kong.
*William Drabkin. Motif. (2001). In S. Sadie and J. Tyrrell (Eds), ''The new Grove dictionary of music and musicians''. Macmillan, London, UK, 2nd ed.
*David Meredith. (2013). COSIATEC and SIATECCompress: Pattern discovery by geometric compression. ''10th Annual Music Information Retrieval eXchange (MIREX'13)'', Curitiba, Brazil.
*Oriol Nieto and Morwaread Farbood. (2013). Discovering musical patterns using audio structural segmentation techniques. ''10th Annual Music Information Retrieval eXchange (MIREX'13)'', Curitiba, Brazil.
*Arnold Schoenberg. (1967). ''Fundamentals of Musical Composition''. Faber and Faber, London.
*Ron J. Weiss and Juan Pablo Bello. (2010). Identifying repeated patterns in music using sparse convolutive non-negative matrix factorization. In ''Proc. ISMIR'' (pp. 123-128), Utrecht, The Netherlands.

2013:Discovery of Repeated Themes & Sections Results

2013-10-30T18:12:29Z

David Meredith: /* Ground Truth and Algorithms */

== Introduction ==

The task: algorithms take a piece of music as input, and output a list of patterns repeated within that piece. A pattern is defined as a '''set of ontime-pitch pairs''' that occurs twice (i.e., is repeated at least once) in a piece of music. The second, third, etc. occurrences of the pattern will likely be shifted in time and/or transposed, relative to the first occurrence. Ideally an algorithm will be able to discover all exact and inexact occurrences of a pattern within a piece, so in evaluating this task we are interested in both:
*(1) to what extent an algorithm can discover one occurrence, up to time shift and transposition, and;
*(2) to what extent it can find all occurrences.
The metrics '''establishment recall''', establishment precision and establishment F1 address (1), and the metrics '''occurrence recall''', occurrence precision, and occurrence F1 address (2).

== Contribution ==

Existing approaches to music structure analysis in MIR tend to focus on segmentation (e.g., Weiss & Bello, 2010). The contribution of this task is to afford access to the note content itself (please see the example in Fig. 1A), requiring algorithms to do more than label time windows (e.g., the segmentations in Figs. 1B-D). For instance, a discovery algorithm applied to the piece in Fig. 1A should return a pattern corresponding to the note content of <math>P_1</math> and <math>P_2</math>, as well as a pattern corresponding to the note content of <math>Q_1</math>. This is because <math>Q_1</math> occurs again independently of the accompaniment in bars 19-22 (not shown here). The ground truth also contains nested patterns, such as <math>P_1</math> in Fig. 1A being a subset of the sectional repetition <math>S_1</math>, reflecting the often-hierarchical nature of musical repetition. While we recognise the appealing simplicity of linear segmentation, in the ''Discovery of Repeated Themes & Sections'' task we are demanding analysis at a greater level of detail, and have built a ground truth that contains overlapping and nested patterns.

[[File:mozartK282Mvt2.png|500px]]

'''Figure 1.''' Pattern discovery v segmentation. (A) Bars 1-12 of Mozart’s Piano Sonata in E-flat major K282 mvt.2, showing some ground-truth themes and repeated sections; (B-D) Three linear segmentations. Numbers below the staff in Fig. 1A and below the segmentation in Fig. 1D indicate crotchet beats, from zero for bar 1 beat 1.

For a more detailed introduction to the task, please see [[2013:Discovery_of_Repeated_Themes_&_Sections]].

== Ground Truth and Algorithms ==

The ground truth, called the '''Johannes Kepler University Patterns Test Database''' (JKUPTD-Aug2013), is based on motifs and themes in Barlow and Morgenstern (1953), Schoenberg (1967), and Bruhn (1993). Repeated sections are based on those marked by the composer. These annotations are supplemented with some of our own where necessary. A Development Database (JKUPDD-Aug2013) released in March enabled participants to try out their algorithms. For each piece in the Development and Test Databases, symbolic and synthesised audio versions are crossed with monophonic and polyphonic versions, giving four versions of the task in total: symPoly, symMono, audPoly, and audMono. Algorithms submitted to the task are are shown in Table 1.

{| border="1" cellspacing="0" style="text-align: left; width: 800px;"
|- style="background: yellow;"
! width="80" | Sub code
! width="200" | Submission name
! width="80" style="text-align: center;" | Abstract
! width="440" | Contributors
|-
|- style="background: green;"
! Task Version
! symPoly
!
!
|-
! NF2
| motives_poly || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/NF2.pdf PDF] || [http://files.nyu.edu/onc202/public/ Oriol Nieto], [http://www.nyu.edu/projects/farbood/ Morwaread Farbood]
|-
! DM10
| SIATECCompressSegment || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM10.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM9
| SIATECCompressRaw || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM9.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM8
| SIATECCompressBB || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM8.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM7
| COSIATECSegment || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM7.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM6
| COSIATECRaw || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM6.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM5
| COSSIATECBB || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM5.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|- style="background: green;"
! Task Version
! symMono
!
!
|-
! NF1
| motives_mono || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/NF1.pdf PDF] || [http://files.nyu.edu/onc202/public/ Oriol Nieto], [http://www.nyu.edu/projects/farbood/ Morwaread Farbood]
|-
! DM10
| SIATECSegment || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM10.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM9
| SIATECCompressRaw || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM9.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM8
| SIATECCompressBB || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM8.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM7
| COSIATECSegment || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM7.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM6
| COSIATECRaw || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM6.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|-
! DM5
| COSSIATECBB || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/DM5.pdf PDF] || [http://www.titanmusic.com/ David Meredith]
|- style="background: green;"
! Task Version
! audPoly
!
!
|-
! NF4
| motives_audio_poly || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/NF4.pdf PDF] || [http://files.nyu.edu/onc202/public/ Oriol Nieto], [http://www.nyu.edu/projects/farbood/ Morwaread Farbood]
|- style="background: green;"
! Task Version
! audMono
!
!
|-
! NF3
| motives_audio_mono || style="text-align: center;" | [https://www.music-ir.org/mirex/abstracts/2013/NF3.pdf PDF] || [http://files.nyu.edu/onc202/public/ Oriol Nieto], [http://www.nyu.edu/projects/farbood/ Morwaread Farbood]
|}

'''Table 1.''' Algorithms submitted to DRTS.

== Results ==

For mathematical definitions of the various metrics, please see [[2013:Discovery_of_Repeated_Themes_&_Sections#Evaluation_Procedure]].

=== In Brief ===

To avoid a bias toward the more numerous submissions of Meredith (2013), DM10 was preselected for comparison with Nieto and Farbood's (2013) submissions, based on reported performance for the Development Database. Figure 2 shows establishment recall results on a per-pattern basis for the symbolic-polyphonic version of the task. DM10 outperforms NF2 according to Friedman's test (<math>\chi^2(1) = 12.7368,\ p < .001</math>), suggesting the former is preferable for discovering at least one occurrence of each ground truth pattern. This result addresses point (1) from the introduction.

Figure 3 shows occurrence recall results on a per-pattern basis for the symbolic-polyphonic version of the task. Again, DM10 outperforms NF2 according to Friedman's test (<math>\chi^2(1) = 11.2667,\ p < .001</math>), suggesting the former is preferable for retrieving all occurrences of a discovered ground truth pattern. This result addresses point (2) from the introduction.

It should be noted, however, that according to Friedman's test, algorithm NF2 is significantly faster than DM10 (<math>\chi^2(1) = 4.000,\ p < .05</math>), suggesting the former is preferable for rapid summarisation.

Results were similar but somewhat closer for the symbolic-monophonic version of the task. According to Friedman's test (<math>\chi^2(1) = 2.9512,\ p = .0858</math>, ns), NF1 and DM10 show no significant difference for establishment recall on a per-pattern basis (please see Figure 14). This result relates to point (1) from the introduction. Figure 15 shows occurrence recall results on a per-pattern basis for the symbolic-monophonic version of the task. DM10 outperforms NF1 according to Friedman's test (<math>\chi^2(1) = 11.6364,\ p < .001</math>), suggesting the former is preferable for retrieving all occurrences of a discovered ground truth pattern. This result relates to point (2) from the introduction.

For the audio versions of the task, algorithms NF3 (audMono) and NF4 (audPoly) were the only submissions. Nieto and Farbood (2013) are credited with being the first to define an algorithm for discovering repeated note content in a synthesised audio file that is time-locked to a symbolic representation. We include some results from these task versions, with future comparisons in mind (Figs. 26-49). Evidently the audio task was more challenging (cf. Figs. 2 and 26).

=== symPoly ===

[[File:01symPolyEstRecPerPatt.png|600px]]

'''Figure 2.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:04symPolyOccRecPerPatt.png|600px]]

'''Figure 3.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:01symPolyEstRec.png|400px]]

'''Figure 4.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:02symPolyEstPrec.png|400px]]

'''Figure 5.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:03symPolyEstF1.png|400px]]

'''Figure 6.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:04symPolyOccRecP75.png|400px]]

'''Figure 7.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:05symPolyOccPrecP75.png|400px]]

'''Figure 8.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:06symPolyOccF1P75.png|400px]]

'''Figure 9.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:07symPolyR3.png|400px]]

'''Figure 10.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:08symPolyP3.png|400px]]

'''Figure 11.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:09symPolyTLF.png|400px]]

'''Figure 12.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:10symPolyRuntime.png|400px]]

'''Figure 13.''' Log runtime of the algorithm for each piece/movement.

=== symMono ===

''(Poor performance here for algorithm NF1 on piece 2 is likely due to rounding errors in the discovery phase; not anything musically interesting. The task captain tried in vain to identify a workaround.)''

[[File:11symMonoEstRecPerPatt.png|600px]]

'''Figure 14.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:14symMonoOccRecPerPatt.png|600px]]

'''Figure 15.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:11symMonoEstRec.png|400px]]

'''Figure 16.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:12symMonoEstPrec.png|400px]]

'''Figure 17.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:13symMonoEstF1.png|400px]]

'''Figure 18.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:14symMonoOccRecP75.png|400px]]

'''Figure 19.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:15symMonoOccPrecP75.png|400px]]

'''Figure 20.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:16symMonoOccF1P75.png|400px]]

'''Figure 21.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:17symMonoR3.png|400px]]

'''Figure 22.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:18symMonoP3.png|400px]]

'''Figure 23.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:19symMonoTLF.png|400px]]

'''Figure 24.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:20symMonoRuntime.png|400px]]

'''Figure 25.''' Log runtime of the algorithm for each piece/movement.

=== audPoly ===

[[File:21audPolyEstRecPerPatt.png|600px]]

'''Figure 26.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:24audPolyOccRecPerPatt.png|600px]]

'''Figure 27.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:21audPolyEstRec.png|400px]]

'''Figure 28.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:22audPolyEstPrec.png|400px]]

'''Figure 29.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:23audPolyEstF1.png|400px]]

'''Figure 30.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:24audPolyOccRecP75.png|400px]]

'''Figure 31.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:25audPolyOccPrecP75.png|400px]]

'''Figure 32.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:26audPolyOccF1P75.png|400px]]

'''Figure 33.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:27audPolyR3.png|400px]]

'''Figure 34.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:28audPolyP3.png|400px]]

'''Figure 35.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:29audPolyTLF.png|400px]]

'''Figure 36.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:30audPolyRuntime.png|400px]]

'''Figure 37.''' Log runtime of the algorithm for each piece/movement.

=== audMono ===

[[File:31audMonoEstRecPerPatt.png|600px]]

'''Figure 38.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:34audMonoOccRecPerPatt.png|600px]]

'''Figure 39.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:31audMonoEstRec.png|400px]]

'''Figure 40.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:32audMonoEstPrec.png|400px]]

'''Figure 41.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:33audMonoEstF1.png|400px]]

'''Figure 42.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:34audMonoOccRecP75.png|400px]]

'''Figure 43.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:35audMonoOccPrecP75.png|400px]]

'''Figure 44.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:36audMonoOccF1P75.png|400px]]

'''Figure 45.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:37audMonoR3.png|400px]]

'''Figure 46.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:38audMonoP3.png|400px]]

'''Figure 47.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:39audMonoTLF.png|400px]]

'''Figure 48.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:40audMonoRuntime.png|400px]]

'''Figure 49.''' Log runtime of the algorithm for each piece/movement.

== Discussion ==

If an occurrence of a ground-truth pattern contains forty or more notes then, according to Fig. 2, it is likely that SIATECSegment (DM10, Meredith, 2013) and motives_poly (NF2, Nieto & Farbood, 2013) will return a pattern rated as at least 75% similar. When we restrict attention to these successful discoveries and ask to what extent can the algorithms retrieve all exact and inexact occurrences, we find that SIATECSegment performs relatively well (see nonzero entries for the black line in Fig. 3), with the exception of the first patterns in pieces 1 and 2. We conclude, therefore, that the discovery of repeated sections has been addressed well by the current submissions, but that the discovery of themes and motifs requires more attention in future iterations of this task.

When assembling the ground truth, it was remarkable that most often a motif occurs as a subset of a theme or repeated section, which is not surprising given Drabkin’s (2001) definition of a motif as ‘the shortest subdivision of a theme or phrase that still maintains its identity as an idea’. One suggestion for future work is to apply a discovery algorithm to find repeated sections, and then '''apply the algorithm again''' but to the '''output sections only''', in order to retrieve these nested and important musical motifs.

''(More detailed, per-piece feedback for each submission to follow.)''

== Tabular Versions of Plots ==

=== symPoly ===

<csv p=3>2013/drts/symPolyResults.csv</csv>

'''Table 2.''' Tabular version of Figures 4-13.

<csv p=3>2013/drts/symPolyResultsPerPatt.csv</csv>

'''Table 3.''' Tabular version of Figures 2 and 3.

=== symMono ===

''(Poor performance here for algorithm NF1 on piece2 is likely due to rounding errors in the discovery phase; not anything musically interesting. The task captain tried in vain to identify a workaround.)''

<csv p=3>2013/drts/symMonoResults.csv</csv>

'''Table 4.''' Tabular version of Figures 16-25.

<csv p=3>2013/drts/symMonoResultsPerPatt.csv</csv>

'''Table 5.''' Tabular version of Figures 14 and 15.

=== audPoly ===

<csv p=3>2013/drts/audPolyResults.csv</csv>

'''Table 6.''' Tabular version of Figures 28-37.

<csv p=3>2013/drts/audPolyResultsPerPatt.csv</csv>

'''Table 7.''' Tabular version of Figures 26 and 27.

=== audMono ===

<csv p=3>2013/drts/audMonoResults.csv</csv>

'''Table 8.''' Taublar version of Figures 40-49.

<csv p=3>2013/drts/audMonoResultsPerPatt.csv</csv>

'''Table 9.''' Tabular version of Figures 38 and 39.

== References ==

*Harold Barlow and Sam Morgenstern. (1948). ''A dictionary of musical themes''. Crown Publishers, New York.
*Siglind Bruhn. (1993). ''J.S. Bach's Well-Tempered Clavier: in-depth analysis and interpretation''. Mainer International, Hong Kong.
*William Drabkin. Motif. (2001). In S. Sadie and J. Tyrrell (Eds), ''The new Grove dictionary of music and musicians''. Macmillan, London, UK, 2nd ed.
*David Meredith. (2013). COSIATEC and SIATECCompress: Pattern discovery by geometric compression. ''10th Annual Music Information Retrieval eXchange (MIREX'13)'', Curitiba, Brazil.
*Oriol Nieto and Morwaread Farbood. (2013). Discovering musical patterns using audio structural segmentation techniques. ''10th Annual Music Information Retrieval eXchange (MIREX'13)'', Curitiba, Brazil.
*Arnold Schoenberg. (1967). ''Fundamentals of Musical Composition''. Faber and Faber, London.
*Ron J. Weiss and Juan Pablo Bello. (2010). Identifying repeated patterns in music using sparse convolutive non-negative matrix factorization. In ''Proc. ISMIR'' (pp. 123-128), Utrecht, The Netherlands.

2013:Discovery of Repeated Themes & Sections Results

2013-10-29T08:09:14Z

David Meredith: /* Ground Truth and Algorithms */

== Introduction ==

The task: algorithms take a piece of music as input, and output a list of patterns repeated within that piece. A pattern is defined as a '''set of ontime-pitch pairs''' that occurs twice (i.e., is repeated at least once) in a piece of music. The second, third, etc. occurrences of the pattern will likely be shifted in time and/or transposed, relative to the first occurrence. Ideally an algorithm will be able to discover all exact and inexact occurrences of a pattern within a piece, so in evaluating this task we are interested in both:
*(1) to what extent an algorithm can discover one occurrence, up to time shift and transposition, and;
*(2) to what extent it can find all occurrences.
The metrics '''establishment recall''', establishment precision and establishment F1 address (1), and the metrics '''occurrence recall''', occurrence precision, and occurrence F1 address (2).

== Contribution ==

Existing approaches to music structure analysis in MIR tend to focus on segmentation. The contribution of this task is to afford access to the note content itself (please see the example in Fig. 1A), requiring algorithms to do more than label time windows (e.g., the segmentations in Figs. 1B-D). For instance, a discovery algorithm applied to the piece in Fig. 1A should return a pattern corresponding to the note content of <math>P_1</math> and <math>P_2</math>, as well as a pattern corresponding to the note content of <math>Q_1</math>. This is because <math>Q_1</math> occurs again independently of the accompaniment in bars 19-22 (not shown here). The ground truth also contains nested patterns, such as <math>P_1</math> in Fig. 1A being a subset of the sectional repetition <math>S_1</math>, reflecting the often-hierarchical nature of musical repetition. While we recognise the appealing simplicity of linear segmentation, in the ''Discovery of Repeated Themes & Sections'' task we are demanding analysis at a greater level of detail, and have built a ground truth that contains overlapping and nested patterns.

[[File:mozartK282Mvt2.png|500px]]

'''Figure 1.''' Pattern discovery v segmentation. (A) Bars 1-12 of Mozart’s Piano Sonata in E-flat major K282 mvt.2, showing some ground-truth paterns; (B-D) Three linear segmentations. Numbers below the staff in Fig. 1A and below the segmentation in Fig. 1D indicate crotchet beats, from zero for bar 1 beat 1.

For a more detailed introduction to the task, please see [[2013:Discovery_of_Repeated_Themes_&_Sections]].

== Ground Truth and Algorithms ==

The ground truth, called the Johannes Kepler University Patterns Test Database (JKUPTD-Aug2013), is based on motifs and themes in Barlow and Morgenstern (1953), Schoenberg (1967), and Bruhn (1993). Repeated sections are based on those marked by the composer. These annotations are supplemented with some of our own where necessary. A Development Database (JKUPDD-Aug2013) released in March enabled participants to try out their algorithms. For each piece in the Development and Test Databases, symbolic and synthesised audio versions are crossed with monophonic and polyphonic versions, giving four versions of the task in total: symPoly, symMono, audPoly, and audMono. Algorithms submitted to the task are are shown in Table 1.

<table border="1">
<tr>
<th>Code</th>
<th>Researcher(s)</th>
<th>Algorithm</th>
</tr>
<tr>
<td colspan="3" align="left"><i>Task Version: symPoly</i></td>
</tr>
<tr>
<td>NF2</td>
<td>Nieto and Farbood (2013)</td>
<td>motives_poly</td>
</tr>
<tr>
<td>DM10</td>
<td>Meredith (2013)</td>
<td>SIATECCompressSegment</td>
</tr>
<tr>
<td>DM9</td>
<td>Meredith (2013)</td>
<td>SIATECCompressRaw</td>
</tr>
<tr>
<td>DM8</td>
<td>Meredith (2013)</td>
<td>SIATECCompressBB</td>
</tr>
<tr>
<td>DM7</td>
<td>Meredith (2013)</td>
<td>COSIATECSegment</td>
</tr>
<tr>
<td>DM6</td>
<td>Meredith (2013)</td>
<td>COSIATECRaw</td>
</tr>
<tr>
<td>DM5</td>
<td>Meredith (2013)</td>
<td>COSIATECBB</td>
</tr>
<tr>
<td colspan="3" align="left"><i>Task Version: symMono</i></td>
</tr>
<tr>
<td>NF1</td>
<td>Nieto and Farbood (2013)</td>
<td>motives_mono</td>
</tr>
<tr>
<td>DM10</td>
<td>Meredith (2013)</td>
<td>SIATECSegment</td>
</tr>
<tr>
<td>DM9</td>
<td>Meredith (2013)</td>
<td>SIATECCompressRaw</td>
</tr>
<tr>
<td>DM8</td>
<td>Meredith (2013)</td>
<td>SIATECCompressBB</td>
</tr>
<tr>
<td>DM7</td>
<td>Meredith (2013)</td>
<td>COSIATECSegment</td>
</tr>
<tr>
<td>DM6</td>
<td>Meredith (2013)</td>
<td>COSIATECraw</td>
</tr>
<tr>
<td>DM5</td>
<td>Meredith (2013)</td>
<td>COSIATECBB</td>
</tr>
<tr>
<td colspan="3" align="left"><i>Task Version: audPoly</i></td>
</tr>
<tr>
<td>NF4</td>
<td>Nieto and Farbood (2013)</td>
<td>motives_audio_poly</td>
</tr>
<tr>
<td colspan="3" align="left"><i>Task Version: audMono</i></td>
</tr>
<tr>
<td>NF3</td>
<td>Nieto and Farbood (2013)</td>
<td>motives_audio_mono</td>
</tr>
</table>

'''Table 1.''' Algorithms submitted to DRTS.

== Results ==

For mathematical definitions of the various metrics, please see [[2013:Discovery_of_Repeated_Themes_&_Sections#Evaluation_Procedure]].

=== In Brief ===

To avoid a bias toward the more numerous submissions of Meredith (2013), DM10 was preselected for comparison with Nieto and Farbood's (2013) submissions, based on reported performance for the Development Database. Figure 2 shows establishment recall results on a per-pattern basis for the symbolic-polyphonic version of the task. DM10 outperforms NF2 according to Friedman's test (<math>\chi^2(1) = 12.7368,\ p < .001</math>), suggesting the former is preferable for discovering at least one occurrence of each ground truth pattern. This result addresses point (1) from the introduction.

Figure 3 shows occurrence recall results on a per-pattern basis for the symbolic-polyphonic version of the task. Again, DM10 outperforms NF2 according to Friedman's test (<math>\chi^2(1) = 11.2667,\ p < .001</math>), suggesting the former is preferable for retrieving all occurrences of a discovered ground truth pattern. This result addresses point (2) from the introduction.

It should be noted, however, that according to Friedman's test, algorithm NF2 is significantly faster than DM10 (<math>\chi^2(1) = 4.000,\ p < .05</math>), suggesting the former is preferable for rapid summarisation.

The results are closer for the symbolic-monophonic version of the task. According to Friedman's test (<math>\chi^2(1) = 2.9512,\ p = .0858</math>, ns), NF1 and DM10 show no significant difference for establishment recall on a per-pattern basis (please see Figure 14). This result relates to point (1) from the introduction. Figure 15 shows occurrence recall results on a per-pattern basis for the symbolic-monophonic version of the task. DM10 outperforms NF1 according to Friedman's test (<math>\chi^2(1) = 11.6364,\ p < .001</math>), suggesting the former is preferable for retrieving all occurrences of a discovered ground truth pattern. This result relates to point (2) from the introduction.

For the audio versions of the task, algorithms NF3 (audMono) and NF4 (audPoly) were the only submissions. Nieto and Farbood (2013) are credited with being the first to define an algorithm for discovering repeated note content in a synthesised audio file that is time-locked to a symbolic representation. We include the results for these versions of the task, with a view to comparison in future years.

=== symPoly ===

[[File:01symPolyEstRecPerPatt.png|700px]]

'''Figure 2.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:04symPolyOccRecPerPatt.png|700px]]

'''Figure 3.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:01symPolyEstRec.png|400px]]

'''Figure 4.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:02symPolyEstPrec.png|400px]]

'''Figure 5.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:03symPolyEstF1.png|400px]]

'''Figure 6.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:04symPolyOccRecP75.png|400px]]

'''Figure 7.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:05symPolyOccPrecP75.png|400px]]

'''Figure 8.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:06symPolyOccF1P75.png|400px]]

'''Figure 9.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:07symPolyR3.png|400px]]

'''Figure 10.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:08symPolyP3.png|400px]]

'''Figure 11.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:09symPolyTLF.png|400px]]

'''Figure 12.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:10symPolyRuntime.png|400px]]

'''Figure 13.''' Log runtime of the algorithm for each piece/movement.

=== symMono ===

''(Poor performance here for algorithm NF1 on piece 2 is likely due to rounding errors in the discovery phase; not anything musically interesting. The task captain tried in vain to identify a workaround.)''

[[File:11symMonoEstRecPerPatt.png|700px]]

'''Figure 14.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:14symMonoOccRecPerPatt.png|700px]]

'''Figure 15.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:11symMonoEstRec.png|400px]]

'''Figure 16.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:12symMonoEstPrec.png|400px]]

'''Figure 17.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:13symMonoEstF1.png|400px]]

'''Figure 18.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:14symMonoOccRecP75.png|400px]]

'''Figure 19.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:15symMonoOccPrecP75.png|400px]]

'''Figure 20.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:16symMonoOccF1P75.png|400px]]

'''Figure 21.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:17symMonoR3.png|400px]]

'''Figure 22.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:18symMonoP3.png|400px]]

'''Figure 23.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:19symMonoTLF.png|400px]]

'''Figure 24.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:20symMonoRuntime.png|400px]]

'''Figure 25.''' Log runtime of the algorithm for each piece/movement.

=== audPoly ===

[[File:21audPolyEstRecPerPatt.png|700px]]

'''Figure 26.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:24audPolyOccRecPerPatt.png|700px]]

'''Figure 27.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:21audPolyEstRec.png|400px]]

'''Figure 28.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:22audPolyEstPrec.png|400px]]

'''Figure 29.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:23audPolyEstF1.png|400px]]

'''Figure 30.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:24audPolyOccRecP75.png|400px]]

'''Figure 31.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:25audPolyOccPrecP75.png|400px]]

'''Figure 32.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:26audPolyOccF1P75.png|400px]]

'''Figure 33.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:27audPolyR3.png|400px]]

'''Figure 34.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:28audPolyP3.png|400px]]

'''Figure 35.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:29audPolyTLF.png|400px]]

'''Figure 36.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:30audPolyRuntime.png|400px]]

'''Figure 37.''' Log runtime of the algorithm for each piece/movement.

=== audMono ===

[[File:31audMonoEstRecPerPatt.png|700px]]

'''Figure 38.''' Establishment recall on a per-pattern basis. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:34audMonoOccRecPerPatt.png|700px]]

'''Figure 39.''' Occurrence recall on a per-pattern basis. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:31audMonoEstRec.png|400px]]

'''Figure 40.''' Establishment recall averaged over each piece/movement. Establishment recall answers the following question. On average, how similar is the most similar algorithm-output pattern to a ground-truth pattern prototype?

[[File:32audMonoEstPrec.png|400px]]

'''Figure 41.''' Establishment precision averaged over each piece/movement. Establishment precision answers the following question. On average, how similar is the most similar ground-truth pattern prototype to an algorithm-output pattern?

[[File:33audMonoEstF1.png|400px]]

'''Figure 42.''' Establishment F1 averaged over each piece/movement. Establishment F1 is an average of establishment precision and establishment recall.

[[File:34audMonoOccRecP75.png|400px]]

'''Figure 43.''' Occurrence recall (<math>c = .75</math>) averaged over each piece/movement. Occurrence recall answers the following question. On average, how similar is the most similar set of algorithm-output pattern occurrences to a discovered ground-truth occurrence set?

[[File:35audMonoOccPrecP75.png|400px]]

'''Figure 44.''' Occurrence precision (<math>c = .75</math>) averaged over each piece/movement. Occurrence precision answers the following question. On average, how similar is the most similar discovered ground-truth occurrence set to a set of algorithm-output pattern occurrences?

[[File:36audMonoOccF1P75.png|400px]]

'''Figure 45.''' Occurrence F1 (<math>c = .75</math>) averaged over each piece/movement. Occurrence F1 is an average of occurrence precision and occurrence recall.

[[File:37audMonoR3.png|400px]]

'''Figure 46.''' Three-layer recall averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment recall), three-layer recall uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:38audMonoP3.png|400px]]

'''Figure 47.''' Three-layer precision averaged over each piece/movement. Rather than using <math>|P \cap Q|/\max\{|P|, |Q|\}</math> as a similarity measure (which is the default for establishment precision), three-layer precision uses <math>2|P \cap Q|/(|P| + |Q|)</math>, which is a kind of F1 measure.

[[File:39audMonoTLF.png|400px]]

'''Figure 48.''' Three-layer F1 (TLF) averaged over each piece/movement. TLF is an average of three-layer precision and three-layer recall.

[[File:40audMonoRuntime.png|400px]]

'''Figure 49.''' Log runtime of the algorithm for each piece/movement.

== Discussion ==

If an occurrence of a ground-truth pattern contains forty or more notes then, according to Fig. 2, it is likely that SIATECSegment (DM10, Meredith, 2013) and motives_poly (NF2, Nieto & Farbood, 2013) will return a pattern rated as at least 75% similar. When we restrict attention to these successful discoveries and ask to what extent can the algorithms retrieve all exact and inexact occurrences, we find that SIATECSegment performs relatively well (see nonzero entries for the black line in Fig. 3), with the exception of the first patterns in pieces 1 and 2. We conclude, therefore, that the discovery of repeated sections has been addressed well by the current submissions, but that the discovery of themes and motifs requires more attention in future iterations of this task.

When assembling the ground truth, it was remarkable that most often a motif occurs as a subset of a theme or repeated section, which is not surprising given Drabkin’s (2001) definition of a motif as ‘the shortest subdivision of a theme or phrase that still maintains its identity as an idea’. One suggestion for future work is to apply a discovery algorithm to find repeated sections, and then '''apply the algorithm again''' but to the '''output sections only''', in order to retrieve these nested and important musical motifs.

== Tabular Versions of Plots ==

=== symPoly ===

<csv p=3>2013/drts/symPolyResults.csv</csv>

'''Table 2.''' Tabular version of Figures 4-13.

<csv p=3>2013/drts/symPolyResultsPerPatt.csv</csv>

'''Table 3.''' Tabular version of Figures 2 and 3.

=== symMono ===

''(Poor performance here for algorithm NF1 on piece2 is likely due to rounding errors in the discovery phase; not anything musically interesting. The task captain tried in vain to identify a workaround.)''

<csv p=3>2013/drts/symMonoResults.csv</csv>

'''Table 4.''' Tabular version of Figures 16-25.

<csv p=3>2013/drts/symMonoResultsPerPatt.csv</csv>

'''Table 5.''' Tabular version of Figures 14 and 15.

=== audPoly ===

<csv p=3>2013/drts/audPolyResults.csv</csv>

'''Table 6.''' Tabular version of Figures 28-37.

<csv p=3>2013/drts/audPolyResultsPerPatt.csv</csv>

'''Table 7.''' Tabular version of Figures 26 and 27.

=== audMono ===

<csv p=3>2013/drts/audMonoResults.csv</csv>

'''Table 8.''' Taublar version of Figures 40-49.

<csv p=3>2013/drts/audMonoResultsPerPatt.csv</csv>

'''Table 9.''' Tabular version of Figures 38 and 39.

== References ==

2013:Discovery of Repeated Themes & Sections

2013-07-30T13:37:45Z

David Meredith: /* Available Code */

== Description ==

'''In brief''': algorithms that take a single piece of music as input, and output a list of patterns repeated within that piece. Also known as ''intra-opus discovery'' (Conklin & Anagnostopoulou, 2001).

We would be happy to receive ideas for improving aspects of this task. Researchers with wiki accounts are able to post comments below or to edit the relevant sections, and researchers without wiki accounts are welcome to email me directly: tom.collins(a)jku.at

'''In more detail''': for understanding and interpreting a musical work, the discovery of repeated patterns within that piece is a crucial step. Meredith, Lemström, and Wiggins (2002) cite Schenker (1954) as claiming repetition to be 'the basis of music as an art' (p. 5), and also Lerdahl and Jackendoff (1983), who observe that 'the importance of parallelism [i.e., repetition] in musical structure cannot be overestimated. The more parallelism one can detect, the more internally coherent an analysis becomes, and the less independent information must be processed and retained in hearing or remembering a piece' (p. 52).

On the very next page Lerdahl and Jackendoff (1983) acknowledge their 'failure to flesh out the notion of parallelism,' which is symptomatic of a more general failure in music psychology and music computing to address the discovery of repetition. Algorithms that take pieces of music as input, and output a list, visualisation, or summary of repeated patterns do exist (Chiu, Shan, Huang, & Li, 2009; Collins, Thurlow, Laney, Willis, & Garthwaite, 2010; Conklin & Anagnostopoulou, 2001; Forth & Wiggins, 2009; Hsu, Liu, & Chen, 2001; Knopke & Jürgensen, 2009; Lartillot, 2005; Meek & Birmingham, 2003; Meredith et al., 2002; Müller & Jiang, 2012; Nieto, Humphrey, & Bello, 2012; Peeters, 2007), but the pattern discovery task has received less attention than many other tasks in MIR. Until now!

===What is a Pattern?===

For the purposes of this task, a pattern is defined as a '''set of ontime-pitch pairs''' that occurs at least twice (i.e., is repeated at least once) in a piece of music. The second, third, etc. occurrences of the pattern will likely be shifted in time and perhaps also transposed, relative to the first occurrence. Ideally an algorithm would be able to discover all exact and inexact occurrences of a pattern within a piece, so in evaluating this task we are interested in both (1) whether an algorithm can discover one occurrence, up to time shift and transposition, and (2) to what extent it can find all occurrences. It has been pointed out by Lartillot and Toiviainen (2007) among others that as well as ontime-pitch patterns, there are various types of repeating pattern (e.g., ontimes alone, duration, contour, harmony, etc.). For the sake of simplicity, the current task is restricted to ontime-pitch pairs.

Some of the most recognisable riffs and motifs in music consist of as few as four ontime-pitch pairs (for example, the opening riff from 'Purple Haze' by Hendrix, or the opening of the first movement of Symphony no.5 in C minor by Beethoven). If, however, an algorithm returned all patterns consisting of four or more notes in a given piece, a lot of these patterns would not be perceptually salient or analytically interesting. Happily, solutions have been proposed for trying to determine which are the most noticeable and/or important patterns, which are of middling importance, and which have occurred by chance (Cambouropoulos, 2006; Conklin, 2010a, 2010b). Collins, Laney, Willis, & Garthwaite (2011) conducted a meta-analysis and experimental validation of many proposed solutions. More information about the differences between motif, theme, and repeated section can be found in answer to Question 6.6.

==Data==

My colleagues and I at the [http://www.cp.jku.at/ Department of Computational Perception], [http://www.jku.at/ Johannes Kepler University], are compiling a database of classical music annotated with repeated themes and sections (mainly from [http://kern.ccarh.org/ KernScores]; see also Flossmann, Goebl, Grachten, Niedemayer, & Widmer, 2010). To encourage participation in the pattern discovery task, we are offering a representative sample called the [https://dl.dropbox.com/u/11997856/JKU/JKUPDD-Jul2013.zip JKU Patterns Development Database (~340 MB, July 2013 version)]. (If you prefer, [https://dl.dropbox.com/u/11997856/JKU/JKUPDD-noAudio-Jul2013.zip here] is a smaller version with no audio, ~40 MB.) Symbolic and audio versions are crossed with monophonic and polyphonic versions, giving up to four versions of the task in total. Researchers are welcome to submit to more than one version of the task.

As a ground truth, we are basing motifs and themes on Barlow and Morgenstern's (1953) ''[http://www.multimedialibrary.com/barlow/index.asp Dictionary of Musical Themes]'', Schoenberg's (1967) ''Fundamentals of Musical Composition'', and Bruhn's (1993) ''[http://www-personal.umich.edu/~siglind/text.htm J. S. Bach’s Well-Tempered Clavier: In-depth Analysis and Interpretation]''. Repeated sections are based on those marked by the composer. For one of the pieces we created our own annotation. A paper that describes our construction of the Development Database and use of the sources is currently under preparation. No ground truth is perfect: we have chosen the sources as being relatively uncontroversial and transparent, but we would welcome ideas and suggestions from other researchers. As a quick example, [http://www.tomcollinsresearch.net/mirex-pattern-discovery-task.html#figure1 Figure 1] is an excerpt from Beethoven's op.2 no.1 mvt.3, with a ground-truth pattern marked as <math>P_1</math> (first occurrence) and <math>P_2</math> (second occurrence).

==Submission Format==

===Symbolic Version===

Participants are able to choose from a number of symbolic representations (MIDI, kern, csv with columns for ontime, MIDI note number, staff height, duration, and staff number), as there may be differing opinions about which aspects of a representation are most useful for discovering repeated patterns. This choice also reflects the importance of designing pattern discovery code that functions irrespective of the exact input format (Wiggins, 2007). For the purposes of standardised evaluation, participants will need to convert each occurrence of a discovered pattern to a point set consisting of event ontimes and MIDI note numbers. For instance, the point-set representation for <math>P_1</math> in [http://www.tomcollinsresearch.net/mirex-pattern-discovery-task.html#figure1 Figure 1] is

:<math>P_1 = \{(-1, 60),\ (-1, 68),\ (0, 61),\ (0, 70),\ (1, 58),\ (1, 67),\ (2, 53),</math>
:::<math>(3, 60),\ (3, 68),\ (4, 56),\ (4, 65),\ (5, 53),\ (5, 56),\ (5, 60),\ (5, 65),</math>
:::<math>(6, 55),\ (6, 58),\ (6, 60),\ (6, 64),\ (7, 53),\ (7, 56),\ (7, 60),\ (7, 65),</math>
::::<math>(8, 52),\ (8, 55),\ (8, 60),\ (8, 67),</math>
:::<math>(9, 53),\ (9, 56),\ (9, 60),\ (9, 70),\ (10, 68)\}.</math>

Sectional repetitions are expanded in all pieces, i.e. as the piece would be heard in a performance. In the monophonic version, pieces consisting of voiced polyphony (e.g., a fugue or choral work) are ''unfolded'', meaning each voice is extracted and re-encoded monophonically, one after the other in the order highest staff to lowest. For example, a fugue with upper, middle, and lower voices would be re-encoded with the upper voice heard first in isolation, followed by the middle voice, and then lower voice. In the monophonic version, pieces consisting of unvoiced polyphony are converted to monophony using the ''clipped skyline'' approach.

===Audio Version===

For the audio version of the task, participating algorithms will have to read audio in wav format, sample rate 44.1 KHz, 16 bit, mono. These wav files are rendered (synthesised) in a metronomically exact fashion from the corresponding symbolic data. Beats per minute (BPM) are different for different pieces, but this information is located in the corresponding kern file (e.g., in a kern file '*MM192' means 192 BPM).

As with the symbolic version of the task, for the purposes of standardised evaluation, participants will need to convert each occurrence of a discovered pattern to a point set consisting of event ontimes and MIDI note numbers. Even if your algorithm only returns a time interval <math>[a,\ b]</math> in seconds for an occurrence of a pattern, this conversion will be easy enough to do: convert <math>[a,\ b]</math> to an ontime interval <math>[c,\ d]</math> using the BPM provided, and then use the csv file for the piece to determine which ontime-MIDI pairs are sounding in <math>[c,\ d]</math>. (A downside to this approach is that the evaluations metrics will be slightly be punitive if not all ontime-pitch pairs sounding in <math>[c,\ d]</math> are part of the ground truth pattern.)

===Example Algorithm Output for a Ground-Truth Piece===

Regardless of symbolic/audio and polyphonic/monophonic task version, the output of your pattern discovery algorithm for a given piece should adhere to the following text file format:

pattern1
occurrence1
7.00000, 45.00000
7.00000, 48.00000
...
11.00000, 60.00000
occurrence2
31.00000, 57.00000
31.00000, 60.00000
...
35.00000, 72.00000
occurrence3
59.00000, 57.00000
59.00000, 60.00000
...
63.00000, 72.00000
pattern2
occurrence1
7.00000, 45.00000
7.00000, 48.00000
...
11.00000, 57.00000
occurrence2
27.00000, 48.00000
27.00000, 52.00000
...
59.00000, 60.00000
...
patternM
occurrence1
9.00000, 58.00000
9.50000, 52.00000
...
12.00000, 60.0000
...
occurrencem
100.00000, 62.00000
100.50000, 55.00000
...
103.00000, 61.00000

That is, ontimes are in the left-hand column and MIDI note numbers are in the right. Each occurrence of a discovered pattern is given before moving on to the next pattern. Occurrences do not have to be of the same length, nor do they have to be constrained to exact or transposed repetition (e.g., variations are permitted). Neither the patterns nor the occurrences of patterns need to be in temporal order: the evaluation metrics are robust to different orders.

Order does matter, however, in the following two respects: if possible (1) place the patterns in decreasing order of predicted perceptual salience/musical importance; (2) define ''occurrence1'' to be the ''prototypical'' occurrence of each pattern. Fulfilling point (1) is not essential (could defer to future work), but it concerns an application of discovery algorithms wherein a user browses the output patterns. It would be convenient for the user to be shown the most important patterns first, and one metric below (called first five target proportion) evaluates this aspect of algorithm performance. Fulfilling point (2) is important if your discovery method is capable of retrieving inexact occurrences. Some metrics below are designed for assessing the capability for retrieving inexact occurrences, but others are simply concerned with whether or not the prototypical occurrence is discovered. The evaluation code will consider ''occurrence1'' to be the ''prototype''.

==Evaluation Procedure==

'''In brief''': An implementation of the evaluation metrics and example code are bundled with the Development Database, to save participants having to implement the evaluation metrics themselves. (If you do wish to write your own evaluation code, please note that the appropriate annotation folders for the polyphonic task are 'bruhn', 'barlowAndMorgensternRevised', 'sectionalRepetitions', 'schoenberg', and 'tomCollins'; for the monophonic task it is 'bruhn', 'barlowAndMorgenstern', 'barlowAndMorgensternRevised', 'sectionalRepetitions', 'schoenberg', and 'tomCollins'.) Participating algorithms will be evaluated against the following metrics:
* precision, recall, and F1 score;
* establishment precision, establishment recall, and establishment F1 score;
* occurrence precision, occurrence recall, and occurrence F1 score;
* runtime, fifth return time, and first five target proportion.

===Precision, Recall, and F1 Score===

'''In more detail''': Denote the <math>n_{\mathcal{P}}</math> patterns in a ground truth by <math>\Pi = \{ \mathcal{P}_1, \mathcal{P}_2,\ldots, \mathcal{P}_{n_\mathcal{P}} \}</math>, and the <math>n_{\mathcal{Q}}</math> patterns in an algorithm’s output by <math>\Xi = \{ \mathcal{Q}_1, \mathcal{Q}_2,\ldots, \mathcal{Q}_{n_\mathcal{Q}} \}</math>. If the algorithm discovers <math>k</math> of the ground truth patterns, up to translation, then the ''precision'' of the algorithm is defined as <math>P = k/n_{\mathcal{Q}}</math>, the ''recall'' of the algorithm is defined as <math>R = k/n_{\mathcal{P}}</math>, and the ''F1 score'' as <math>F_1 = 2PR/(P + R).\ </math>

The above metrics, which were used by Collins et al. (2010) in one of the first evaluations of a pattern discovery task, are very strict: an output pattern <math>Q</math> may have only one point different from a large ground truth pattern <math>P</math>, but this will not count as a successful discovery. Therefore, we propose the following new metrics, which are robust to slight differences between output and ground truth patterns.

===Robust Versions of Precision, Recall, and F1 score===

====Symbolic Musical Similarity and the Score Matrix====

Suppose that in the ground truth there is a pattern <math>P</math> with occurrences <math>\mathcal{P} = \{ P_1, P_2,\ldots, P_{m_P} \}</math>, and in an algorithm's output there is a pattern <math>Q</math> with occurrences <math>\mathcal{Q} = \{ Q_1, Q_2,\ldots, Q_{m_Q} \}</math>. Central to evaluating an algorithm is measuring the extent to which <math>\mathcal{Q}</math> constitutes the discovery of <math>\mathcal{P}</math>. In order to measure this, we need to be able to compute the symbolic musical similarity of <math>P_i</math> and <math>Q_j</math>. We can use the simple ''cardinality score'' for symbolic musical similarity,
:<math>
s_c(P_i, Q_j) = |P_i \cap Q_j|/ \max \{ |P_i|, |Q_j| \},
</math>

or the slightly more involved ''normalised matching score'' <math>s_m(P_i, Q_j)</math>, after Arzt, Böck, and Widmer (2012). Some examples of cardinality and matching scores between original and mutant versions of the theme from Beethoven's op.2 no.2 mvt.3 are given in [http://www.tomcollinsresearch.net/mirex-pattern-discovery-task.html#figure2 Figure 2].

Either of these similarity measures, denoted <math>s(P_i, Q_j)</math>, can be recorded in a so-called ''score matrix'',
:<math>
s(\mathcal{P}, \mathcal{Q}) = \left(
\begin{array}{cccc}
s(P_1, Q_1) & s(P_1, Q_2) & \cdots & s(P_1, Q_{m_Q}) \\
s(P_2, Q_1) & s(P_2, Q_2) & \cdots & s(P_2, Q_{m_Q}) \\
\vdots & \vdots & \ddots & \vdots \\
s(P_{m_P}, Q_1) & s(P_{m_P}, Q_2) & \cdots & s(P_{m_P}, Q_{m_Q})
\end{array} \right).
</math>

The score matrix shows how all occurrences <math>\mathcal{Q} = \{ Q_1, Q_2,\ldots, Q_{m_Q} \}</math> of a pattern in an algorithm's output compare to all occurrences <math>\mathcal{P} = \{ P_1, P_2,\ldots, P_{m_P} \}</math> of a ground truth pattern.

====Establishment Precision, Establishment Recall, and Establishment F1 Score====

Summaries of the ''score matrix'' will be necessary for evaluating all of an algorithm's output against the whole ground truth for a piece. For instance, we may be interested in whether an algorithm is capable of ''establishing'' that a pattern <math>P</math> is repeated at least once during a piece, and less interested in whether the algorithm can retrieve all occurrences of <math>P</math> (exact and inexact). In this case, the maximum entry in the score matrix, denoted <math>S(\mathcal{P}, \mathcal{Q})</math>, is the appropriate summary. For a piece's ground truth <math>\Pi = \{ \mathcal{P}_1, \mathcal{P}_2,\ldots, \mathcal{P}_{n_\mathcal{P}} \}</math>, and an algorithm's entire output for that piece <math>\Xi = \{ \mathcal{Q}_1, \mathcal{Q}_2,\ldots, \mathcal{Q}_{n_\mathcal{Q}} \}</math>, it is now possible to record the algorithm's capability for ''establishing'' that patterns in <math>\Pi</math> are repeated at least once during the piece, using the so-called ''establishment matrix'',
:<math>
S(\Pi, \Xi) = \left(
\begin{array}{cccc}
S(\mathcal{P}_1, \mathcal{Q}_1) & S(\mathcal{P}_1, \mathcal{Q}_2) & \cdots & S(\mathcal{P}_1, \mathcal{Q}_{n_Q}) \\
S(\mathcal{P}_2, \mathcal{Q}_1) & S(\mathcal{P}_2, \mathcal{Q}_2) & \cdots & S(\mathcal{P}_2, \mathcal{Q}_{n_Q}) \\
\vdots & \vdots & \ddots & \vdots \\
S(\mathcal{P}_{n_P}, \mathcal{Q}_1) & S(\mathcal{P}_{n_P}, \mathcal{Q}_2) & \cdots & S(\mathcal{P}_{n_P}, \mathcal{Q}_{n_Q})
\end{array} \right).
</math>

The ''establishment precision'' can then be calculated according to
:<math>
P_{\text{est}} = \frac{1}{n_\mathcal{Q}} \sum_{j = 1}^{n_\mathcal{Q}}
\max \{ S(\mathcal{P}_i, \mathcal{Q}_j) \mid i = 1,\ldots, n_\mathcal{P} \}.
</math>

If an algorithm discovers <math>k</math> of the ground-truth patterns exactly, and misses the remaining <math>n_\mathcal{Q} - k</math> patterns completely, then the establishment precision is equal to standard precision (<math>= k/n_\mathcal{Q}</math>). The ''establishment recall'' is defined as
:<math>
R_{\text{est}} = \frac{1}{n_\mathcal{P}} \sum_{i = 1}^{n_\mathcal{P}}
\max \{ S(\mathcal{P}_i, \mathcal{Q}_j) \mid j = 1,\ldots, n_\mathcal{Q} \}.
</math>

The establishment F1 score is defined as above, but replacing precision with establishment precision, and recall with establishment recall.

====Occurrence Precision, Occurrence Recall, and Occurrence F1 Score====

As mentioned above, there is a difference between a pattern discovery algorithm (or listener) being able to establish the existence of a repeated pattern, and being able to retrieve all occurrences. We showed how to measure the extent to which an algorithm is capable of establishing that a pattern <math>P</math> is repeated at least once during a piece. Now we focus on an algorithm's ability to retrieve ''all'' occurrences of <math>P</math> (exact and inexact). These metrics will favour an algorithm that is strong at retrieving all occurrences of the patterns it discovers, even if the algorithm fails completely to discover many of the salient patterns in a piece.

The indices <math>I</math> of the estalishment matrix with values greater than or equal to some threshold (default value <math>c = .75</math>) indicate which ground truth patterns an algorithm is considered to have discovered. We will focus on these indices to define a so-called ''occurrence matrix''. Denoted <math>O(\Pi, \Xi)</math>, the ''occurrence matrix'' begins as an <math>n_\mathcal{P} \times n_\mathcal{Q}</math> zero matrix. Then for each index pair <math>(i, j) \in I</math>, we calculate the precision of the ''score matrix'' <math>s(\mathcal{P}_i, \mathcal{Q}_j)</math>, and record this scalar as element <math>(i, j)</math> of <math>O(\Pi, \Xi)</math>. The precision of <math>s(\mathcal{P}_i, \mathcal{Q}_j)</math> indicates the precision with which algorithm output <math>\mathcal{Q}_j</math> retrieved the ground truth item <math>\mathcal{P}_i</math>. The ''occurrence precision'', denoted <math>P_{\text{occ}}</math>, is then defined as the precision of the occurrence matrix <math>O(\Pi, \Xi)</math>, with the sum taken over nonzero columns. The ''occurrence recall'', denoted <math>R_{\text{occ}}</math>, is defined analogously, but replacing mentions of 'precision' and 'columns' above with 'recall' and 'rows.' The occurrence <math>F_1</math> score can be defined also.

===Runtime, Fifth Return Time, and First Five Target Proportion===

Overall runtime is an important metric. Those wishing to develop pattern discovery algorithms for on-the-fly browsing, however, may find it more relevant to know the time taken to return a smaller number of patterns. (E.g., while the user browses, the algorithm can continue to discover extra patterns.) Fifth return time (FRT) is the time taken for the first five patterns to be output by an algorithm. As these patterns are of little use if none of them are ground truth, we counterbalance FRT with another metric called first five target proportion (FFTP), which is the proportion of times that the first five output patterns contain a ground-truth pattern.

===Friedman Tests for the Pattern Discovery Task===

The Friedman test will be used to investigate whether any algorithms rank consistently higher or lower than the others, with regard to the F1 scores on individual pieces.

==Available Code==

Entering an existing MIREX task, where results have been improving for up to 7 years, can be a daunting prospect. The pattern discovery task, on the other hand, is new, and so is a great opportunity for Master's and PhD students to make their mark in MIR. To this end, it should be noted that the following code is freely available, and that students/researchers are very welcome to define pattern discovery algorithms by altering/extending this code, or to use it as a point of comparison with their own algorithms. Please feel free to ask questions, either via this wiki, or by email to authors of the relevant papers.
*[https://code.google.com/p/chromamorph/source/browse/#svn%2Ftrunk%2FPoints%2Fsrc%2Fcom%2Fchromamorph%2Fpoints018 Java implementation] of algorithms from Meredith et al. (2002) and Meredith (2006).
*[http://www.tomcollinsresearch.net/supporting-material.html Matlab implementation] of algorithms from Collins et al. (2010). (Agree to GNU licence and then download Patterns-Aug2012.zip.)
*If you would like to participate in the audio version but are missing an F0 estimator, then you could use the [http://mtg.upf.edu/technologies/melodia MELODIA plug-in] as described by Salamon and Gómez (2012).
*Please add links to more implementations here.
*...

==Questions and Comments==

===How Is Pattern Discovery Different to the [[2012:Structural_Segmentation]] Task?===

We expect structural segmentation algorithms to be adaptable to pattern discovery, so would really welcome segmentation researchers to submit to the pattern discovery task as well. The two tasks are different as follows: structural segmentation results in a list of labelled time intervals that cover an entire piece of music, such as

0.000 4.273 A
4.273 8.469 A
8.469 21.321 B
21.321 25.734 A
... ... ...
175.012 179.108 A

* The output of a pattern discovery algorithm will not necessarily cover an entire piece. A four-bar theme beginning in bar 1 might be the only output of a pattern discovery algorithm, even if the piece is much longer and contains other material.
* Whereas the output of a structural segmentation algorithm is non-overlapping, the output of a pattern discovery algorithm might be overlapping or even nested (hierarchical). For instance, the four-bar theme mentioned above might be output, as well as a sectional repetition that lasts from bars 1-8.

===How Is Pattern Discovery Different to Pattern Matching, Or the [[2012:Symbolic_Melodic_Similarity]] Task?===

In a typical pattern matching task, more or less exact instances of a ''given query'' are retrieved from some larger dataset, and ranked by an appropriate measure of relevance to the original query (e.g., Barton, Cambouropoulos, Iliopoulos, & Lipták, 2012). The setup of pattern discovery is fundamentally different: there are no queries given to begin with, just single pieces of music and the requirement to discover repeating patterns within each piece.

The melodic similarity task fits the pattern matching paradigm, and so is also different to pattern discovery. In the melodic similarity task, algorithms are given a melodic query, and retrieve a supposedly relevant melody from the database. The similarity of the query and the algorithm's match is assessed by human listeners.

===Why Not Just Use Optical Music Recognition to Detect Sectional Repetitions?===

One could use optical music recognition instead, although what we are trying
to understand and model is a listener's awareness of thematic material and
sectional repetitions, which often exists without access to staff notation. It would also be interesting to apply pattern discovery to music for which there is no staff notation.

===This Is Intra-Opus Discovery, But What About Inter-Opus Discovery?===

Inter-opus discovery, the discovery of patterns that recur across multiple pieces of music (Conklin & Anagnostopoulou, 2001), is an interesting problem, and one that we would be interested to see cast as a MIREX task in future.
Currently, lack of an appropriate ground truth is an issue here.

===There Are Some Issues With the MIDI Files, Please Can You Clarify?===

The MIDI files were created and are provided for the purposes of sonifying and checking the symbolic data, and are not intended to be used themselves for input to the pattern discovery algorithms (please see the folders called 'csv' and/or 'lisp' instead). They are not ideal for input for the following reasons: (1) correct pitch spelling is lost, whereas this is maintained by presenting MIDI note number and morphetic pitch number side by side in the 'csv' and 'lisp' folders; (2) each MIDI file is zeroed in the sense that it begins more or less immediately, even if the pattern occurrence it represents occurs halfway through a piece; (3) each MIDI file also contains one extra, very quiet, low note to avoid clipping in the sound file.

===What is the Difference Between a Motif, a Theme, and a Repeated Section?===

Dictionary definitions of '''motif''', '''theme''', and '''repeated section''' are given below. To make the definitions more concrete, I refer to the top system of [http://www.tomcollinsresearch.net/mirex-pattern-discovery-task.html#figure2 Figure 2]. In terms of ontime-pitch pairs, the motif here consists of {(2, C#5), (2.25, A4), (2.5, E5), (2.75, C#5), (3, A5)}, beginning on beat 3 of bar 2 and ending on beat 1 of bar 3. This is repeated an octave lower one bar later, and occurs with a slightly different intervallic configuration at the very beginning. The theme, according to Barlow and Morgenstern (1948), lasts from the upbeat of bar 1, to beat 2 of bar 4. Bars 5-8 are not shown in [http://www.tomcollinsresearch.net/mirex-pattern-discovery-task.html#figure2 Figure 2], but there is a repeated section consisting of bars 1-8. So one might infer from this example that typically a motif lasts less than one bar, a theme 4-8 bars, and a repeated section 8+ bars.

According to Drabkin (2001a), a "motif may be of any size, and is most commonly regarded as the shortest subdivision of a theme or phrase that still maintains its identity as an idea." A theme is the "musical material on which part or all of a work is based, usually having a recognizable melody and sometimes perceivable as a complete musical expression in itself" Drabkin (2001b). A repeated section is the "restatement of a portion of a musical composition of any length from a single bar to a whole section, or occasionally the whole piece. Since the Classical period, repeated passages have not usually been written out; instead they are enclosed within the signs ||: and :||" (Tilmouth, 2001).

==Time And Hardware Limits==

Depending on the number of participating algorithms, we may place a limit on analysis times.

==Potential Participants==

*Please add name and email here.
*...

==Acknowledgments==

Thank you to the following for feedback on this task description: Ashley Burgoyne, Emilios Cambouropoulos, Darrell Conklin, Stephen Downie, Morwaread Farbood, Jamie Forth, Nanzhu Jiang, Ian Knopke, Olivier Lartillot, David Meredith, Oriol Nieto, Eleanor Selfridge-Field, and Geraint Wiggins.

==References==

*Andreas Arzt, Sebastian Böck, and Gerhard Widmer. [http://www.cp.jku.at/research/papers/Arzt_etal_ISMIR_2012.pdf Fast identification of piece and score position via symbolic fingerprinting]. In F. Gouyon, P. Herrera, L.G. Martin, and M. Müller (Eds), ''Proc ISMIR'', pp. 433-438, Porto, 2012.

*Harold Barlow and Sam Morgenstern. ''A dictionary of musical themes''. Crown Publishers, New York, 1948.

*Siglind Bruhn. ''J.S. Bach's Well-Tempered Clavier: in-depth analysis and interpretation''. Mainer International, Hong Kong, 1993.

*Carl Barton, Emilios Cambouropoulos, Costas S. Iliopoulos, and Zsuzsanna Lipták. Melodic string matching via interval consolidation and fragmentation. In L. Iliadis, I. Maglogiannis, H. Papadopoulos, K. Karatzas, and S. Sioutas (Eds), ''Artificial Intelligence Applications and Innovations'', pp. 460-469. Springer, Berlin, 2012.

*Emilios Cambouropoulos. Musical parallelism and melodic segmentation: a computational approach. ''Music Perception'', 23(3):249-267, 2006.

*Shih-Chuan Chiu, Man-Kwan Shan, Jiun-Long Huang, and Hua-Fu Li. Mining polyphonic repeating patterns from music data using bit-string based approaches. In R. Radhakrishnan and R. Yan (Eds), ''Proc IEEE International Conference on Multimedia and Expo'', pp. 1170-1173, New York, 2009.

*Tom Collins, Jeremy Thurlow, Robin Laney, Alistair Willis, and Paul H. Garthwaite. [http://oro.open.ac.uk/21837/ A comparative evaluation of algorithms for discovering translational patterns in Baroque keyboard works]. In J.S. Downie and R. Veltkamp (Eds), ''Proc ISMIR'', pp. 3-8, Utrecht, 2010. [http://www.tomcollinsresearch.net/supporting-material.html Supporting material]

*Tom Collins, Robin Laney, Alistair Willis, and Paul H. Garthwaite. [http://oro.open.ac.uk/24818/ Modeling pattern importance in Chopin's mazurkas]. ''Music Perception'', 28(4):387-414, 2011. [http://www.tomcollinsresearch.net/supporting-material.html Supporting material]

*Darrell Conklin. Discovery of distinctive patterns in music. ''Intelligent Data Analysis'', 14(5):547-554, 2010a.

*Darrell Conklin. Distinctive patterns in the first movement of Brahms' String Quartet in C minor. ''Journal of Mathematics and Music'', 4(2):85-92, 2010b.

*Darrell Conklin and Christina Anagnostopoulou. Representation and discovery of multiple viewpoint patterns. In A. Schloss, R. Dannenberg, and P. Driessen (Eds), ''Proc ICMC'', pp. 479-485, Cuba, 2001.

*William Drabkin. Motif. In S. Sadie and J. Tyrrell (Eds), "The new Grove dictionary of music and musicians". Macmillan, London, UK, 2nd edition, 2001a.

*William Drabkin. Theme. In S. Sadie and J. Tyrrell (Eds), "The new Grove dictionary of music and musicians". Macmillan, London, UK, 2nd edition, 2001b.

*Sebastian Flossmann, Werner Goebl, Maarten Grachten, Bernhard Niedemayer, and Gerhard Widmer. [http://www.cp.jku.at/research/papers/flossmann_etal_jnmr_2010.pdf The Magaloff project: an interim report]. ''Journal of New Music Research'', 39(4):363-377, 2010.

*Jamie Forth and Geraint A. Wiggins. An approach for identifying salient repetition in multidimensional representations of polyphonic music. In J. Chan, J. Daykin, and M.S. Rahman (Eds), ''London algorithmics 2008: Theory and practice'', pp. 44-58. College Publications, London, 2009.

*Jia-Lien Hsu, Chih-Chin Liu, and Arbee L.P. Chen. Discovering nontrivial repeating patterns in music data. ''IEEE Transactions on Multimedia'', 3(3):311-325, 2001.

*Ian Knopke and Frauke Jürgensen. A system for identifying common melodic phrases in the masses of Palestrina. ''Journal of New Music Research'', 38(2):171-181, 2009.

*Olivier Lartillot. Efficient extraction of closed motivic patterns in multidimensional symbolic representations of music. In J.D. Reiss and G.A. Wiggins (Eds), ''Proc ISMIR'', pp. 191-198, London, 2005.

*Olivier Lartillot and Petri Toiviainen. Motivic matching strategies for automated pattern extraction. ''Musicae Scientiae'', Discussion Forum 4A:281-314, 2007.

*Fred Lerdahl and Ray Jackendoff. ''A generative theory of tonal music''. MIT Press, Cambridge, MA, 1983.

*Colin Meek and William P. Birmingham. Automatic thematic extractor. ''Journal of Intelligent Information Systems'', 21(1):9-33, 2003.

*David Meredith, Kjell Lemstr&oumlm, and Geraint A. Wiggins. Algorithms for discovering repeated patterns in multidimensional representations of polyphonic music. ''Journal of New Music Research'', 31(4):321-345, 2002.

*David Meredith. Point-set algorithms for pattern discovery and pattern matching in music. In T. Crawford and R. Veltkamp (Eds), ''Proc Dagstuhl Seminar on Content-Based Retrieval'', 23 pp., Dagstuhl, 2006.

*Meinard Müller and Nanzhu Jiang. A scape plot representation for visualizing repetitive structures of music recordings. In F. Gouyon, P. Herrera, L.G. Martin, and M. Müller (Eds), ''Proc ISMIR'', pp. 97-102, Porto, 2012.

*Oriol Nieto, Eric J. Humphrey, Juan Pablo Bello. Compressing music recordings into audio summaries. In F. Gouyon, P. Herrera, L.G. Martin, and M. Müller (Eds), ''Proc ISMIR'', pp. 313-318, Porto, 2012.

*Geoffroy Peeters. Sequence representation of music structure using higher-order similarity matrix and maximum-likelihood approach. In S. Dixon, D. Bainbridge, and R. Typke (Eds), ''Proc ISMIR'', pp. 35-40, Vienna, 2007.

*Justin Salamon and Emilia Gómez. Melody extraction from polyphonic music signals using pitch contour characteristics. ''IEEE Transactions on Audio, Speech and Language Processing'', 20(6):1759-1770, 2012.

*Heinrich Schenker. ''Harmony''. University of Chicago Press, London, 1954. (Translated by Elisabeth Mann Borgese and edited by Oswald Jonas. Original work published 1906 by Cotta, Stuttgart).

*Arnold Schoenberg. ''Fundamentals of Musical Composition''. Faber and Faber, London, 1967.

*Michael Tilmouth. Repeat. In S. Sadie and J. Tyrrell (Eds), "The new Grove dictionary of music and musicians". Macmillan, London, UK, 2nd edition, 2001.

*Avery Wang. An industrial strength audio search algorithm. In H.H. Hoos and D. Bainbridge (Eds), ''Proc ISMIR'', Baltimore, MD, 2003.

*Geraint A. Wiggins. Computer-representation of music in the research environment. In T. Crawford and L. Gibson (Eds), ''Modern methods for musicology: prospects, proposals and realities'', pp. 7-22. Ashgate, Oxford, UK, 2007.