Musical Phrase Segmentation via Grammatical Induction

1 Introduction

Procedural generation exploits the fact that complex structures can be created by iteratively applying a set of transformation rules R to some axiom a, possibly verifying the output against constraints C. We can describe an algorithm for procedural generation as a function f : R× A × C → Ω that maps a set of rules R ∈ R, an axiom a ∈ A, and a set of constraints C ∈ C to an output artifact o ∈ Ω. 1 For example, R could be rules that govern tree branch growth, a a sapling, C restrictions on the length of branches, and o a rendered image of a tree; or, R could represent path transitions to different story lines, a an initial plot, C detection of continuity errors, and o the backstory for an NPC in a video game.

Popular implementations of f including probabilistic context-free grammars and genetic algorithms are capable of producing impressive results across a variety of domains, including visual arts and video games [M¨uller et al., 2006; ˇSt'ava et al., 2010; Talton et al., 2012; Ritchie et al., 2015; Ritchie et al., 2018; Rowe, 2016], narrative stories [Mason et al., 2019], and musical sequences [McCormack, 1996; Steedman, 1984; Bod, 2001; Bryden, 2006; Cilibrasi et al., 2004; Dalhoum et al., 2008; Fox, 2006; Gilbert and Conklin, 2007; Kitani and Koike, 2010]. We are primarily concerned with the latter category - procedural generation algorithms for symbolic musical sequences. As a thought exercise, we propose a generator f that is capable of procedurally generating musical exercises. We would to like to be able to leverage the power of existing procedural generation algorithms to generate new musical exercises, and so we must supply our musical exercise generator f with a careful choice of R, a, and C.

1 Often a random seed σ is included as a parameter, but we omit this for simplicity. Additionally, R may be paramaterized by a vector of probabilities θ, but for notational clarity we omit this as well.

Ignoring for a moment the exact details of such a system, we must ask ourselves how might R be derived. In the instances of procedural generation algorithms cited above, there are two general approaches to this problem: either R is manually created via experimentation or it is derived in some manner from a dataset of examples D. The latter option is more appealing when designing an autonomous creative system since it removes one degree of hardcoded human intervention. In order for this technique to succeed, however, the dataset D must contain examples that are implicitly "tokenized" - that is, examples that are imbued with some kind of structural metadata. This allows an induction technique I to infer the set of rules R from D. For example, in [Talton et al., 2012] the authors use a dataset of 3D spaceship models in conjunction with Bayesian optimization and Monte Carlo sampling in order to produce R. The results are visually stunning but are also invariably predicated upon the fact that their dataset D is populated with labeled component hierarchies. This is a crucial caveat-an induction algorithm I that derives R from a dataset D of examples presupposes that those examples are encoded as (possibly hierarchical) labeled components. Unfortunately for our purposes, it is not obvious how to apply a given induction technique I to a set of musical examples because musical sequences lack explicit structural semantics.

This is not to say, of course, that musical sequences lack structure. Indeed, music libraries are filled with publications that offer an interpretation of the structure and salient motifs of musical sequences [Barlow and Morgenstern, 1953; Bruhn, 1993; Schoenberg et al., 1967], and developing the skills to recognize and operate within musical structure is an integral part of musical education. Additionally, there have been many attempts to formalize the exact process of inducing structure from a musical sequence in an algorithmic fashion, e.g. Schenkarian analysis [Neumeyer, 2018]. If we wish to leverage the power afforded by state-of-the-art procedural generation algorithms in our musical exercise generator, we must utilize a second induction process I2 that is capable of partitioning a musical sequence into meaningful, labeled segments for use as examples in the dataset D. Without I2, the parent induction process I, which generates the set of rules R, would not function correctly as it requires examples di ∈ D to have labeled structure. It is important to note that I and I2 generally serve different purposes within the context of a procedural generation algorithm: I finds a set of rules R that generalize over multiple sequences; I2 emits a "structural annotation" that categorizes each element in a single sequence.

Here we evaluate five grammar induction algorithms as candidates for implementing the induction process I2: LZ78 [Ziv and Lempel, 1978], REPAIR [Larsson and Moffat, 1999], LONGESTFIRST [Wolff, 2011], MOSTCOMPRESSIVE [Nevill-Manning and Witten, 2000], and SEQUITUR [NevillManning and Witten, 1997]. One important aspect to consider is how musical sequences should be represented to these algorithms since there is no standard way to encode a musical sequence into symbolic form. We analyze several combinations of musical viewpoints [Conklin and Bergeron, 2008] and their effect on the behavior of each algorithm. We evaluate the performance of these algorithms and viewpoint combinations against three separate datasets which contain musical sequences with manually annotated phrase segments. 2,3

2 Methodology

Our goal is to evaluate grammatical induction algorithms on the task of musical phrase segmentation. Here we provide a summary of the datasets used in our evaluation and the form of the musical sequences that will be used as input for the algorithms as well as ground truth annotations that we use to quantitatively evaluate an algorithm's performance. Additional detail may be found in [Perkins and Ventura, 2024].

2.1 Data

The musical sequences and annotations for our experiments are sourced from three different datasets: the Johannes Kepler University Patterns Development Dataset, the Essen Folksong Collection, and the Latter-day Saint Hymns Annotation Collection. Each dataset differs in the average length of their musical sequences, the genre of music they contain, and how their annotations were collected.

The Johannes Kepler University Patterns Development Dataset (JKUPDD) is the product of the Department of Computational Perception at Johannes Kepler University. 4 It consists of five classical piano pieces - one each from the composers Mozart, Bach, Chopin, Gibbons, and Beethovan. Labeled phrase annotations for each piece are sourced from expert musical analysis found in [Barlow and Morgenstern, 1953; Schoenberg et al., 1967; Bruhn, 1993]. The JKUPDD contains representations of each piece in the visual, audio, and symbolic domains. In addition, there are polyphonic and monophonic versions of the audio and symbolic representations. We use only the symbolic monophonic sequences and encode them into our intermediate representation (Sec. 2.2).

The Essen Folksong Collection (Essen), in its current form, is a collection of around 10,000 monophonic melodies from several different areas of the world [Schaffrath, 1995]. The Essen dataset was originally encoded in a custom format 5 , although we use a version of the dataset that has been encoded into ABC notation which allows for easier parsing. 6 The standard convention in the literature maintains that visual line breaks of an encoded tune in the Essen dataset represent unlabeled phrase boundaries [Bod, 2001; Brinkman, 2020], so we employ the following steps to obtain labeled phrase segment annotations from the raw data:

2 Extended preprint available: https://arxiv.org/abs/2405.18742

3 All code and data can be found at https://github.com/reedperki ns/grammatical-induction-phrase-segmentation

4 See https://www.tomcollinsresearch.net/mirex-pattern-discove ry-task.html for an overview of the JKUPDD

1. Merge tunes from each subcategory file into a single file.
2. For each tune, apply the following steps:
3. (a) Split the tune based on visual line breaks. Each line is considered a phrase occurrence.
4. (b) Group equivalent phrase occurrences together. Phrase equality is determined by comparing the midi pitch value and duration of each note.
5. (c) Assign each phrase group a unique label.

This procedure yields 3,718 tunes (∼ 36% of the total dataset size) that contain at least one repeated pattern. We use this subset of tunes in our experiments.

Finally, we include the Latter-day Saint Hymns Annotation Collection (Hymn dataset). 7 The Hymns dataset was constructed by randomly sampling 20 hymns that conformed to standard SATB voicing from the 1985 edition of The Hymnbook of the Church of Jesus Christ of Latter-day Saints [1985]. To create a repository of monophonic sequences, the soprano voice line (consisting of midi pitch values and duration values) was extracted from each hymn. These sequences were then presented to university music students as annotation assignments where each student was tasked with formally annotating the phrase segments of 2 different sequences. Each of the 20 musical sequences received 5 phrase segment annotations from different annotators.

2.2 Sequences and Annotations

We extract from each dataset a series of (ωE i , Pi) pairs, where each ωE i is a monophonic musical sequence and Pi is a corresponding ground truth annotation created by human annotators. The raw musical sequences contained in each dataset are encoded in different formats and the total amount of musical information conveyed by a given sequence is limited as a result of its encoding format and other factors. For example, tunes in the Essen dataset have sporadic metadata with respect to key signature and time signature information that is, in some cases, incorrect or missing completely. The raw XML for the Hymns dataset contains correct time signature information and note ornamentations (such as fermatas, slurs, etc.) but also contains errors in the key signature data across all hymns. To reconcile the differences between these formats and their representational limits, we convert the musical sequences in each dataset into sequences of 3-tuples (o, p, d), which we will refer to as note events, where o, p and d represent the onset

5 http://www.esac-data.org/

6 https://ifdo.ca/∼seymour/runabc/esac/esacdatabase.html

7 The Hymns dataset can be found at https://github.com/reedper kins/hymns-dataset

Algorithm 1 LZ78 Algorithm for Generic Sequences

Require: A sequence ω 1: procedure LZ78(ω) 2: G← {Ns → ()} 3: β ← () 4: for t in ω do 5: β ← β ⊕ t 6: if ∃r ∈ G s.t. rhs(r) = β then 7: β ←lhs(r) 8: else 9: G←G/{Ns →α}∪{Ns →α ⊕ Nβ}∪{Nβ → β} 10: β ← () 11: G←G/{Ns →α} ∪ {Ns →α ⊕ β} 12: return G

time, the midi pitch value, and duration (in quarter notes). Extra information such as ornamentation and key and time signature is not included. For example, the sequence of note events for Hymn 5 from the Hymns data set begins (0.0, 60, 1.0), (1.0, 65, 1.0), (2.0, 63, 1.0), (3.0, 68, 1.0) . . . .

In addition to extracting musical sequences from each dataset, we also extract a ground truth annotation P for each sequence. An annotation P is a set of phrases, each of which is a contiguous subsequence of note events that are grouped under the same semantic label (supplied by the annotator). More formally, an individual phrase p ∈ P is defined as a set O of occurrences, where each occurrence o ∈ O is equivalent to the range [x1, x2] such that x1 < x2 ∈ N. A dataset D is a list of 2-tuples di = (ωE i , Pi ) where ωE i ∈ E ∗ is a sequence of note events with the corresponding ground truth annotation Pi. We use the terms "phrases" and "annotation(s)" interchangeably.

3 Algorithms

The grammatical induction algorithms we use fall into two classes: online algorithms that process a sequence token by token and emit a grammar at each step, and offline algorithms that perform a transformation on the entire sequence according to some global optimization function. Traditionally, each of these algorithms were designed to consume sequences of Unicode characters for data compression applications. We regard the actual contents of an input sequence to be an implementation detail, and generalize these algorithms to work on sequences of arbitrary elements, including feature vectors created from musical viewpoints (see Section 4 for details).

3.1 LZ78

The LZ78 algorithm [Ziv and Lempel, 1978] is an online compression algorithm that utilizes a special lookup table to substitute previously seen phrases in the input with a shorter representation. We present a slightly altered version of the algorithm that operates on a grammar directly, making it a proper grammatical induction algorithm, in Algorithm 1. It processes the input in a single pass as follows. First, a rule is created with Ns as the left-hand side and an empty sequence as the right-hand side and added to an empty grammar G (Line 2). Next, while there is still input left to process, the

Algorithm 2 Sequitur Algorithm for Generic Sequences

Require: A sequence ω

1: procedure SEQUITUR(ω) 2: G← {Ns → ()} 3: for t in ω do 4: G←G/{Ns →α} ∪ {Ns →α ⊕ t} 5: done ←False 6: while not done do 7: done ← True 8: dgrams ← {d | d ∈ repeats(G) ∧ len(d) = 2} 9: for d in dgrams do 10: done ← F alse 11: G←Gd⇒Nd ∪ {Nd → d} 12: dgrams ← {d | d ∈ repeats(G) ∧len(d) = 2} 13: unused ← {r | r ∈ G∧ count(lhs(r),G) < 2} 14: for ρ in unused do 15: done ← F alse 16: G←Glhs(ρ)⇒rhs(ρ) 17: G←G/{ρ} 18: unused ← {r | r ∈ G ∧ count(lhs(r), G) < 2} 19: return G

current token t is appended to a buffer β (Line 5). If the contents of the buffer match the right-hand side of any rule in G, the buffer is replaced with the left-hand side of that rule and the algorithm continues (Lines 6-7). Otherwise, a new nonterminal symbol Nβ is appended to the right-hand side of the start rule Ns and a new rule using Nβ as the left-hand side and β as the right-hand side is added to G (Line 9) and the buffer is cleared (Line 10). After the input sequence is completely consumed, the contents of the buffer (which may be empty) is appended to right-hand side of the start rule (Line 11). This formulation of LZ78 makes use of two additional functions: lhs : R → N returns the left-hand side of a rule; rhs : R→ {T ∪N}∗ returns the right-hand side of a rule.

3.2 Sequitur

SEQUITUR [Nevill-Manning and Witten, 1997] is another algorithm in the family of online compression algorithms that iteratively builds a context-free grammar as it consumes an input sequence ω ∈ T ∗ . Unlike LZ78, SEQUITUR employs a set of transformations that ensure two constraints are met:

1. No pair of symbols occurs more than once in the righthand side of any rule (digram uniqueness).
2. Every non-terminal that appears in the right-hand side of each rule appears at least twice (rule utility).

These constraints ensure that every non-terminal captures a repeated pattern in the original input sequence, and that any repeated pattern will be represented by a rule in the grammar.

Algorithm 2 gives pseudocode for SEQUITUR that makes use of several auxiliary functions. The functions lhs and rhs are defined in Section 3.1. We define a function len : {T ∪N}∗ →N that simply returns the length of a sequence of symbols ω ∈ {T ∪N}∗ . The function repeats : G → P({T ∪ N}∗ ) maps a grammar G ∈ G to the set of nonoverlapping subsequences that occur more than once in the right-hand sides of G. The function count : {T ∪ N}∗ × G → N returns the number of non-overlapping occurrences of a sequence ω ∈ {T ∪ N}∗ in the right-hand sides of a grammar G ∈ G. We define a substitution operator Gx⇒y which replaces all xs with ys in right-hand sides of G.

SEQUITUR works as follows. 8 First, a rule is created with Ns as the left-hand side and an empty sequence as the righthand side and added to an empty grammar G (Line 2). Then, while there is still input to process, the following actions are performed. The current token t is appended to the end of the right-hand side of the start rule (Line 4). To ensure that G meets the first constraint of digram uniqueness, the set of non-overlapping repeated phrases of length 2 are computed and stored in a variable digrams (Line 8). Beginning with the first of these digrams, d, a new non-terminal symbol Nd is created, after which all occurrences of d are substituted with Nd (denoted as Gd⇒Nd ), and, finally, a new rule using Nd as the left-hand side and d as the right-hand side is added to G (Line 11). The substitution process will change the number of occurrences of some digrams, and thus digrams will need to be recomputed (Line 12). This process is repeated until there are no digrams in the right-hand sides of G that occur more than once, which satisfies the first constraint.

Next, to ensure that G meets the second constraint of digram utility, the set of rules in G whose left-hand side nonterminal symbol occurs at most once in the right-hand sides of G are computed and stored in a variable unused (Line 13). These rules are under-utilized. The first of these rules, ρ, is removed by first substituting all occurrences (that is, the single occurrence) of ρ's left-hand side non-terminal symbol with its right-hand side (Line 16). Afterwards, ρ is removed from G (Line 17). This substitution will also change the number of occurrences of some digrams, and therefore unused will also need to be recomputed (Line 18). Additionally, the backsubstitution that occurs in Line 16 could cause some digrams to occur more than once, which would place G in violation of the first constraint. After the second constraint is met, Lines 9-18 will need to be repeated until no changes to G are made. After this point, G has met both constraints and the next token in the input sequence can be processed. When the input sequence is exhausted, G is returned (Line 19).

3.3 Repair, Most Compressive, Longest First

In contrast to the online algorithms introduced above, offline algorithms work by operating on the entire input sequence and substituting subsequences with non-terminal symbols until no new productions can be made. Carrasscosa grouped three offline grammatical induction algorithms into a unified framework known as the Iterative Repeat Replace (IRR) algorithm [Carrascosa et al., 2010]. We present our version of the algorithm in Algorithm 3. We implement all three versions of IRR where each instance uses a different objective function. The first objective function uses the auxiliary

8 The original formulation of SEQUITUR is more complex and guarantees linear time complexity. Because we are dealing with sequences that are only hundreds of elements long (SEQUITUR was originally designed to handle millions), we provide an alternative description of SEQUITUR that sacrifices worst-case asymptotic performance for a more straightforward implementation.

Algorithm 3 IRR Algorithm for Generic Sequences

Require: A sequence ω and a score function f

• 1: procedure IRR(ω, f)
• 2: G← {Ns →ω}
• 3: while ∃ω′ s.t. ω′ ← argmaxω′∈repeats(G) f(ω′ ,G)

• 5: return G

functions repeats and count (defined in Section 3.2) and yields the subsequence ω′ ∈ {T ∪N}∗ that occurs most frequently in the right-hand sides of G:

IRR instantiated with Equation (1) is also known as REPAIR [Larsson and Moffat, 1999]. The second objective function returns the longest non-overlapping repeated subsequence in the right-hand sides of G and is known as LONGESTFIRST [Wolff, 2011]:

The third objective function returns the non-overlapping repeated subsequence that, when replaced with a non-terminal, would result in the largest reduction in the size of G:

Equation 3, which is the objective function used in MOSTCOMPRESSIVE [Nevill-Manning and Witten, 2000], calculates the number of symbols that will be replaced by a nonterminal, plus the cost of adding a non-terminal in each "hole" and creating a new rule in the grammar.

IRR will continue to run while the objective function returns a valid subsequence ω′ and the total size of the grammar after substituting all occurrences of ω′ with a new nonterminal symbol in the grammar, denoted by |Gω′⇒Nω′ |, is smaller than the size of current grammar, denoted by |G|. We follow [Carrascosa et al., 2010] in defining the size of a grammar G to be equivalent to the length of the sequence formed by joining the right-hand sides of each rule in the grammar with a special delimiter symbol.

4 Viewpoints

Viewpoints are functions that convert a note event e ∈ E (defined in Section 2.2) into a singular value [Conklin and Bergeron, 2008]. For example, the pitch viewpoint, denoted by the function pitch : E → {0, 1, . . . , 127}, returns the midi pitch value for a note event e ∈ E. The duration viewpoint function duration : E → R+ computes the duration (in quarter notes) of a note event e ∈ E. The pitch and duration viewpoint functions are both unary functions, and we define additional binary viewpoints that compute inter-onset interval (ioi), pitch contour (pitchC), and pitch interval (pitchI) between consecutive note events e1, e2 as follows:

where ⊥ represents the null value. We define a function transform : V × E ∗ → Φ∗ that converts an n-length sequence of note events ωE ∈ E ∗ into a sequence of feature vectors ωΦ ∈ Φ∗ by applying a viewpoint combination (i.e. a set V ∈ V of multiple viewpoint functions) to each note event in the sequence. More specifically, each note event e0, e1, ..., en-1 ∈ ωE is mapped to its corresponding feature vector ϕ0, ϕ1, ..., ϕn-1 ∈ ωΦ, where each ϕi ∈ {⊥ ∪ N}|V | is formed by applying the constituent viewpoint functions of V ∈ V to ei (e.g. v1(ei), v2(ei), . . . , v|V |(ei)) and concatenating the results into a |V |-dimensional feature vector. In our experiments, V = P({ pitch, duration, ioi, pitchI, pitchC }) where P denotes the powerset. For example, for Hymn 5, e0 = (0.0, 60, 1.0) and e1 = (1.0, 65, 1.0) so for Viewpoint Combination Index (VCI) 31, ϕ0 = (60, 1.0,⊥,⊥,⊥) and ϕ1 = (65, 1.0, 1.0, 1, 5). Each of the algorithms described in this section consumes as input a sequence of feature vectors ωΦ ∈ Φ∗ produced by the transform function.

5 Experimental Setup

Our goal is to see which algorithms and viewpoint combinations produce the best labeled segments for different genres of musical sequences. We run |D × V × A| simulations, where D is the union of all three datasets, V is the set of viewpoint combinations, and A is the set of algorithms. 9 Recalling our definition from Section 2.2, a dataset D comprises 2-tuples di = (ωE i , Pi) that each contain a note event sequence ωE i and a corresponding set Pi of ground truth patterns. Each simulation involves running an algorithm a ∈ A over a viewpointtransformed sequence ωΦ i = transform(ωE i , V ) for some V ∈ V and then extracting a set of discovered patterns Q from the resulting grammar G = a(ωΦ i ). We extract Q from

9 The JKUPDD and the Hymns dataset contain 5 and 20 musical sequences, respectively. Due to computational resource constraints, we only used 1,000 sequences from the Essen dataset, which we sampled from a uniform random distribution. In total this amounted to (1000 + 5 + 20) ∗ 31 ∗ 5 = 158, 875 simulations.

Algorithm 4 Fuzzy Intersection

Require: Sets P and Q of patterns, a sequence of feature vectors ωΦ, and a threshold value τ .

Output: The tuple (|A|, |B|) where |A| and |B| are the number of elements in P that matched elements in Q with a score greater than or equal to τ , and vice versa.

G by recursively expanding all non-terminals in the righthand side of the G's start rule-each distinct non-terminal Nj expands into a subsequence ωΦ j , which we interpret as a musical phrase with label j. Occurrences of phrase j are discovered by finding the starting and ending indices of each subsequence ωΦ j .

Pattern similarity between a ground truth annotation P and a discovered annotation Q is measured by |P ∩ Q|. Computing the intersection of P and Q based on strict equality, however, would unfairly penalize algorithms that produce segmentations that are very close to the ground truth but do not match it exactly. Instead, we define the FUZZYINTERSECTION algorithm (Algorithm 4) that computes P ∩ Q by matching patterns p ∈ P with q ∈ Q based on a similarity measure. The similarity between patterns P and Q is determined by computing the maximum similarity score over all combinations of the occurrences of p ∈ P and q ∈ Q. We can evaluate the similarity of two occurrences op and oq by first extracting from ωΦ i the subsequences they demarcate, which we will refer to as ωp and ωq, and then comparing ωp and ωq using generic sequence comparision algorithms. The extraction process is accomplished using the function extract : N2 × Φ∗ → Φ∗ which returns the subsequence of a feature vector sequence ωΦ ∈ Φ∗ spanned by a pair of integer indices. We implement similarity using the Levenshtein edit distance algorithm:

where Lev computes the Levenshtein edit distance between two generic sequences-in this case, sequences of feature vectors produced by viewpoint combinations. We use the unit cost of 1 for all edit distance operations. In summary, we compute P ∩ Q by running FUZZYINTERSECTION with arguments P , Q, ωΦ i and τ = 0.7. 10

10 For notational simplicity, we assume that FUZZYINTERSECTION maintains global references to similarity, and extract.

With Algorithm 4 in place, we are able to compute precision and recall scores for the set of patterns Q discovered by an algorithm against a set of ground truth patterns P :

We unify the precision and recall scores of an algorithm into a single number by computing their harmonic mean, also known as the F1 score:

6 Results

Here we present quantitative and qualitative results for the experiments described in Section 5.

6.1 Experiment Results

On the Essen dataset the ranking of each algorithm by maximum F1 score over all viewpoint combinations is as follows: LONGESTFIRST (maximum F1 score 0.35), followed by MOSTCOMPRESSIVE, SEQUITUR, REPAIR, and LZ78. This ordering is the same for the JKUPDD and the Hymns dataset as well and also applies in each case when considering the average F1 score. When given the correct viewpoint combination, LONGESTFIRST performs the best on each dataset.

The choice of viewpoint combination has a substantial impact on an algorithm's F1 score. On the Hymns dataset, VCI-2 ({ duration }) and VCI-3 ({ ioi }) produced the highest F1 scores for each algorithm. On the Essen dataset, VCI-2 produced the maximum F1 score for each algorithm. On the JKUPDD, the story is much more varied. The viewpoint that generated the maximum F1 score was VCI-5 ({ pitchI }) for LZ78, VCI-2 for REPAIR, VCI-18 ({ duration, pitch, pitchI }) for MOSTCOMPRESSIVE and SEQUITUR, and VCI-12 ({ duration, pitchI }) for LONGESTFIRST. We conclude from these results that the duration viewpoint, either by itself or combined with other viewpoints, is the most important viewpoint to consider when using the grammatical induction algorithms.

The fact that pitchI was a component viewpoint for each of the highest scoring viewpoint combinations per algorithm on the JKUPDD suggests that the JKUPDD contains pattern occurrences that are transpositions of a canonical pattern. The pitch viewpoint precludes an algorithm from capturing transposed patterns, but pitchI is invariant to transposition.

The content of the datasets themselves affects the F1 score of each algorithm. All algorithms received the highest maximum and average F1 score on the JKUPDD. This is likely due to the fact that the JKUPDD contains patterns with more (and longer) occurrences than the Essen and Hymns datasets.

This phenomenon can be observed quantitatively by studying the variance of F1 scores over the viewpoint combinations for a given algorithm on the dataset. LONGESTFIRST on the JKUPDD has the highest average F1 score (µ = 0.58) and the lowest variance (σ = 0.04). In contrast, the same algorithm on the Hymns dataset has the highest variance (σ = 0.12). On the JKUPDD, almost every VCI has a good chance of scoring highly, whereas on the Hymns and Essen datasets the choice of viewpoint is much more important.

6.2 Qualitative Analysis

For the Hymns dataset, we can also qualitatively compare the output of the five algorithms with the annotations produced by the five human annotators, revealing not only information about algorithm performance but also the degree to which the human annotators were in agreement. As an example, we arbitrarily chose Hymn 2 to analyze.

The ground truth annotations for Hymn 2 reveal interesting discrepancies between annotators. Each annotator produced phrase labels that covered the entire sequence. However, Annotators 2-5 chose to segment the sequence into four 4-bar segments whereas Annotator 1 divided the sequence into eight 2-bar segments. These divisions carry important implications. Annotator 1, for example, focused on identifying smaller patterns - they identified that bars 3-4 and 7-8 are exact repetitions of one another, and subsequently gave these segments the same label. Additionally, they identified bars 13-14 as an embellishment of the first two opening bars. In total, Annotator 1 identified eight phrases as well as two patterns. The rest of the annotators, on the other hand, were more concerned with phrase identification on a broader scale. In contrast with Annotator 1, Annotators 2-5 identified four 4-bar phrases that spanned bars 1-4, bars 5-8, bars 9-12, and bars 13-16. There was a high level of consensus among these four annotators; Annotators 2 and 5 agreed that bars 1-4 and 4-8 were repeated phrases and Annotators 3 and 4 produced the exact same annotation. The bifurcation of the annotators on this particular sequence becomes more apparent when we compare the F1 scores between their annotations as determined using Algorithm 4 with τ = 0.7. The annotations provided by Annotator 1 failed to match any of those given by Annotators 2-5 and all the phrase boundaries produced by Annotators 2-5 were determined to match (though the labeling differs slightly).

The annotations produced by the grammatical induction algorithms both align with and diverge from the human annotators (and each other) in interesting ways. It is immediately clear that the phrases identified by LZ78 do not appear to be musically significant compared to those found by the other annotators and algorithms. In concordance with Annotator 1, on the other hand, REPAIR identified bars 3-4 and 7-8 as the first two instances of Pattern 2, which match the phrases included in Pattern B (for Annotator 1). However, REPAIR also included bars 11-12 in Pattern 2, whereas Annotator 1 labeled bars 11-12 as the singleton Phrase E. It is likely that Annotator 1 was interpreting Phrase E in the context of the underlying chord progression, whereas REPAIR in this case is only seeing the duration values of each note event. Using the duration viewpoint allowed REPAIR to capture one of Ns → N1,N1,N2,N3,N4,N5,N2, ⟨1.0⟩,N6,N6,N3

N1 → N2,N2,N4

N2 → N7,N7

N3 → N7, ⟨2.0⟩

N4 → N5,N9, ⟨1.0⟩, ⟨2.0⟩

N5 → N8,N9

N6 → N8,N8

N7 → ⟨1.0⟩, ⟨1.0⟩

N8 → ⟨0.5⟩, ⟨0.5⟩

N9 → N8, ⟨1.0⟩

Figure 1: The grammar G for Hymn 2 generated by SEQUITUR using the duration viewpoint. Numbers encased in angle brackets are the feature vectors ϕi which each contain a single duration value. These feature vectors are also the terminal symbols for G.

the patterns identified by Annotator 1, at the cost of possibly over-estimating the number of occurrences by one additional phrase. Furthermore, the phrases produced by REPAIR exhibit some interesting characteristics; each of Annotator 1's phrase boundaries are either captured directly (e.g. Phrase B ≈ Phrase 2) or by composition (e.g. Phrase F ≈ Phrase 4 + Phrase 3) in REPAIR's annotation. Examining the pairwise F1 scores between all the annotations for Hymn 2 shows that, despite this, the match score between REPAIR and Annotator 1 (0.31) was lower than that of LONGESTFIRST and Annotator 1 (0.57). In this case, REPAIR is not able to score as high as LONGESTFIRST because most of the phrases it found are by themselves too small to match the phrases from Annotator 1.

On the other hand, SEQUITUR, MOSTCOMPRESSIVE, and LONGESTFIRST matched much more closely with Annotators 2-5, at least in the first eight bars. Each of these algorithms divided the first eight bars into two 4-bar segments and assigned the same phrase label to each. This allowed them to match the phrases in bars 1-4 and 5-8 discovered by Annotators 2-5. In bars 9-16 however, these algorithms failed to capture any of the longer 4-bar phrases that were identified by Annotators 2-5. This phenomenon demonstrates one of the tradeoffs of using these particular grammatical induction algorithms for musical phrase segmentation: these algorithms can efficiently detect patterns and encode them in a humanreadable way, but each occurrence of a repeated pattern must contain the exact same number of notes. The use of musical viewpoints is intended to mitigate the rigidity of this constraint to some degree with respect to transposition, but one hard limitation is that melodic embellishment, either by expansion or reduction, will remain undetected. According to Annotator 5, bars 13-16 can be seen as an embellishment of bars 1-4 and 5-8, but LONGESTFIRST, for example, would not be able to include bars 13-16 as an occurrence of Pattern 1 because that phrase contains more notes than the first two occurrences of Pattern 1. This is why SEQUITUR, MOSTCOMPRESSIVE, and LONGESTFIRST are unable to find the longer phrases in bars 9-16 identified by Annotators 2-5 (although SEQUITUR did manage to identify Phrase 4 which matched Annotator 1's Phrase E).

Thus far, we have only analyzed the performance of grammatical induction algorithms with respect to ground truth data. Our method of extracting annotations from the grammars produced by each of the grammatical induction algorithms involves expanding only the non-terminals that are found in the right-hand side of the start rule - this was done to ensure that the annotations emitted by a grammatical induction algorithm would consist of disjoint phrases. In doing so, we actually overlook one of the most interesting properties of grammatical induction algorithms: their ability to produce hierarchical structures. Figure 1 shows the grammar G emitted by SEQUITUR on Hymn 2 using the duration viewpoint. Visualizing the full grammar produced by SEQUITUR reveals how the final phrase annotations demarcated by the non-terminals in the right-hand side of Ns are actually composed from smaller phrases or musical motifs. Unfortunately, most ground truth data for musical sequence annotations contains disjoint phrase labels, which is why we based the musical phrase segmentation task as well as our evaluation metrics on the assumption that the annotations we extracted from the grammatical induction algorithms would contain disjoint phrases. That said, a future procedural generation algorithm could leverage the fact that grammatical induction algorithms expose the compositional nature of musical phrases.

7 Conclusion

Our goal was to evaluate the performance of grammatical induction algorithms on the task of musical sequence segmentation using five different algorithms that infer context-free grammars from musical sequences. We created a set of 31 different viewpoint combinations out of 5 distinct viewpoint functions so that we could measure the degree to which the representation of a musical sequence affects the performance of an algorithm. The sequences for this experiment were sourced from three separate datasets. Finally, we performed an experiment by running all five grammatical induction algorithms over every sequence in the dataset, transforming each sequence by all 31 viewpoint combinations. We measured the performance of a given algorithm and viewpoint-transformed sequence by comparing the patterns output by the grammar against a corresponding set of ground truth patterns.

It would be natural to assume that perhaps more information, in the form of larger combinations of viewpoints, would be correlated with better performance by the grammatical induction algorithms on the musical segmentation task. On the contrary, the results of our experiments show that the best viewpoint combination index was VCI-2, which consists solely of the duration viewpoint. Notably, this suggests that the annotators themselves were also heavily influenced by the rhythmic patterns in the musical sequences that we studied. If a musical sequence contains patterns which are likely to be transposed, VCI-2 works well when combined with VCI-5. Initially we supposed that SEQUITUR might perform best of all the algorithms because, unlike the others, it requires additional transformations that constrain the output grammar G to be parsimonious with respect to the number of rules created. In reality, LONGESTFIRST was the best performing algorithm on all datasets when given sequences transformed by the (dataset-)optimal VCI, attaining a maximum F1 score (averaged over all sequences) of 0.35 with VCI-2 on Essen, 0.58 with VCI-12 on JKUPDD, and 0.50 with VCI-3 on Hymns.