# Musical Phrase Segmentation via Grammatical Induction

Reed Perkins &Dan Ventura Computer Science Department
Brigham Young University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We outline a solution to the challenge of musical phrase segmentation that
uses grammatical induction algorithms, a class of algorithms which infer a
context-free grammar from an input sequence. We analyze the performance of
five grammatical induction algorithms on three datasets using various musical
viewpoint combinations. Our experiments show that the LongestFirst algorithm
achieves the best F1 scores across all three datasets and that input encodings
that include the duration viewpoint result in the best performance.

##  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:\pazocal{R}\times
A\times\pazocal{C}\rightarrow\Omega$ that maps a set of rules
$R\in\pazocal{R}$, an axiom $a\in A$, and a set of constraints
$C\in\pazocal{C}$ to an output artifact $o\in\Omega$.111Often a random seed
$\sigma$ is included as a parameter, but we omit this for simplicity.
Additionally, $R$ may be paramaterized by a vector of probabilities
$\bm{\theta}$, but for notational clarity we omit this as well. 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üller et al.
(2006); Št’ava et al. (2010); Talton et al. (2012); Ritchie et al. (2015,
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$.

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 $\pazocal{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 $\pazocal{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 $\pazocal{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 $\pazocal{D}$ is populated with labeled component hierarchies. This is
a crucial caveat—an induction algorithm $I$ that derives $R$ from a dataset
$\pazocal{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 $I_{2}$
that is capable of partitioning a musical sequence into meaningful, labeled
segments for use as examples in the dataset $\pazocal{D}$. Without $I_{2}$,
the parent induction process $I$, which generates the set of rules $R$, would
not function correctly as it requires examples $d_{i}\in\pazocal{D}$ to have
labeled structure. It is important to note that $I$ and $I_{2}$ generally
serve different purposes within the context of a procedural generation
algorithm: $I$ finds a set of rules $R$ that generalize over multiple
sequences; $I_{2}$ 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 $I_{2}$: LZ78 Ziv and Lempel (1978), Repair
Larsson and Moffat (1999), LongestFirst Wolff (2011), MostCompressive Nevill-
Manning and Witten (2000), and Sequitur Nevill-Manning 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.222All code and data can be found at
https://github.com/reedperkins/grammatical-induction-phrase-segmentation

##  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.

###  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.333See https://www.tomcollinsresearch.net/mirex-pattern-discovery-
task.html for an overview of the JKUPDD 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
format444http://www.esac-data.org/, although we use a version of the dataset
that has been encoded into ABC notation which allows for easier
parsing.555https://ifdo.ca/~seymour/runabc/esac/esacdatabase.html 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:

  1. 1.

Merge tunes from each subcategory file into a single file.

  2. 2.

For each tune, apply the following steps:

    1. (a)

Split the tune based on visual line breaks. Each line is considered a phrase
occurrence.

    2. (b)

Group equivalent phrase occurrences together. Phrase equality is determined by
comparing the midi pitch value and duration of each note.

    3. (c)

Assign each phrase group a unique label.

This procedure yields 3,718 tunes ($\sim 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).666The Hymns dataset can be found at
https://github.com/reedperkins/hymns-dataset 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 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 $(\omega{E}_{i},P_{i})$ pairs, where
each $\omega{E}_{i}$ is a monophonic musical sequence and $P_{i}$ 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 time, the midi pitch value, and duration (in quarter
notes). Extra information such as ornamentation and key and time signature is
not included. As an example, Figure 2 in the Appendix depicts the note event
sequence $\omega{E}\in\pazocal{E}^{*}$ that contains each note event
$e_{1},e_{2},...,e_{n}\in\pazocal{E}$ for Hymn 5 from the Hymns dataset.

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\in P$ is defined as a set $O$ of
occurrences, where each occurrence $o\in O$ is equivalent to the range
$[x_{1},\ x_{2}]$ such that $x_{1}<x_{2}\in\mathbb{N}$. As an example, Figure
3 in the Appendix shows a ground truth phrase annotation for Hymn 2. A dataset
$\pazocal{D}$ is a list of 2-tuples $d_{i}=\left(\omega{E}_{i},P_{i}\right)$
where $\omega{E}_{i}\in\pazocal{E}^{*}$ is a sequence of note events with the
corresponding ground truth annotation $P_{i}$. 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

Algorithm 1 LZ78 Algorithm for Generic Sequences

1:A sequence $\omega$

2:procedure LZ78($\omega$)

3: $G\leftarrow\\{N_{s}\rightarrow()\\}$

4: $\beta\leftarrow()$

5: for $t$ in $\omega$ do

6: $\beta\leftarrow\beta\bigoplus t$

7: if $\exists r\in G\text{ s.t. }\texttt{rhs}(r)=\beta$ then

8: $\beta\leftarrow\texttt{lhs}(r)$

9: else

10: $G\leftarrow
G/\\{N_{s}\rightarrow\alpha\\}\cup\\{N_{s}\rightarrow\alpha\bigoplus
N_{\beta}\\}\cup\\{N_{\beta}\rightarrow\beta\\}$

11: $\beta\leftarrow()$

12: $G\leftarrow
G/\\{N_{s}\rightarrow\alpha\\}\cup\\{N_{s}\rightarrow\alpha\bigoplus\beta\\}$

13: return $G$

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 $N_{s}$ 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
current token $t$ is appended to a buffer $\beta$ (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 non-terminal symbol $N_{\beta}$ is appended to
the right-hand side of the start rule $N_{s}$ and a new rule using $N_{\beta}$
as the left-hand side and $\beta$ 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:
$\texttt{lhs}:\pazocal{R}\rightarrow\pazocal{N}$ returns the left-hand side of
a rule;
$\texttt{rhs}:\pazocal{R}\rightarrow\\{\pazocal{T}\cup\pazocal{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 $\omega\in\pazocal{T}^{*}$. Unlike
Lz78, Sequitur employs a set of transformations that ensure two constraints
are met:

  1. 1.

No pair of symbols occurs more than once in the right-hand side of any rule
(digram uniqueness).

  2. 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 Sequitur Algorithm for Generic Sequences

1:A sequence $\omega$

2:procedure Sequitur($\omega$)

3: $G\leftarrow\\{N_{s}\rightarrow()\\}$

4: for $t$ in $\omega$ do

5: $G\leftarrow
G/\\{N_{s}\rightarrow\alpha\\}\cup\\{N_{s}\rightarrow\alpha\bigoplus t\\}$

6: $done\leftarrow False$

7: while not $done$ do

8: $done\leftarrow True$

9: $dgrams\leftarrow\\{d\mid
d\in\texttt{repeats}(G)\wedge\texttt{len}(d)=2\\}$

10: for $d$ in $dgrams$ do

11: $done\leftarrow False$

12: $G\leftarrow G_{d\Rightarrow N_{d}}\cup\\{N_{d}\rightarrow d\\}$

13: $dgrams\leftarrow\\{d\mid
d\in\texttt{repeats}(G)\wedge\texttt{len}(d)=2\\}$

14: $unused\leftarrow\\{r\mid r\in
G\wedge\texttt{count}(\texttt{lhs}(r),G)<2\\}$

15: for $\rho$ in $unused$ do

16: $done\leftarrow False$

17: $G\leftarrow G_{\texttt{lhs}(\rho)\Rightarrow\texttt{rhs}(\rho)}$

18: $G\leftarrow G/\\{\rho\\}$

19: $unused\leftarrow\\{r\mid r\in
G\wedge\texttt{count}(\texttt{lhs}(r),G)<2\\}$

20: return $G$

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
$\texttt{len}:\\{\pazocal{T}\cup\pazocal{N}\\}^{*}\rightarrow\mathbb{N}$ that
simply returns the length of a sequence of symbols
$\omega\in\\{\pazocal{T}\cup\pazocal{N}\\}^{*}$. The function
$\texttt{repeats}:\pazocal{G}\rightarrow\mathscr{P}(\\{\pazocal{T}\cup\pazocal{N}\\}^{*})$
maps a grammar $G\in\pazocal{G}$ to the set of non-overlapping subsequences
that occur more than once in the right-hand sides of $G$. The function
$\texttt{count}:\\{\pazocal{T}\cup\pazocal{N}\\}^{*}\times\pazocal{G}\rightarrow\mathbb{N}$
returns the number of non-overlapping occurrences of a sequence
$\omega\in\\{\pazocal{T}\cup\pazocal{N}\\}^{*}$ in the right-hand sides of a
grammar $G\in\pazocal{G}$. We define a substitution operator $G_{x\Rightarrow
y}$ which replaces all $x$s with $y$s in right-hand sides of $G$.

Sequitur works as follows.777The 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. First, a rule is created with $N_{s}$ as the
left-hand side and an empty sequence as the right-hand 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
$N_{d}$ is created, after which all occurrences of $d$ are substituted with
$N_{d}$ (denoted as $G_{d\Rightarrow N_{d}}$), and, finally, a new rule using
$N_{d}$ 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 non-terminal 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,
$\rho$, is removed by first substituting all occurrences (that is, the single
occurrence) of $\rho$’s left-hand side non-terminal symbol with its right-hand
side (Line 16). Afterwards, $\rho$ 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 back-substitution 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

Algorithm 3 IRR Algorithm for Generic Sequences

1:A sequence $\omega$ and a score function $f$

2:procedure IRR($\omega$, $f$)

3: $G\leftarrow\\{N_{s}\rightarrow\omega\\}$

4: while $\exists\omega^{\prime}\text{ s.t.
}\omega^{\prime}\leftarrow\mathop{\mathrm{argmax}}\nolimits_{\omega^{\prime}\in\texttt{repeats}(G)}f(\omega^{\prime},G)$
$\wedge\text{ }|G_{\omega^{\prime}\Rightarrow N_{\omega^{\prime}}}|<|G|$ do

5: $G\leftarrow G_{\omega^{\prime}\Rightarrow
N_{\omega^{\prime}}}\cup\\{N_{\omega^{\prime}}\rightarrow\omega^{\prime}\\}$

6: return $G$

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 functions repeats and count
(defined in Section 3.2) and yields the subsequence
$\omega^{\prime}\in\\{\pazocal{T}\cup\pazocal{N}\\}^{*}$ that occurs most
frequently in the right-hand sides of $G$:

$\omega^{\prime}=\mathop{\mathrm{argmax}}\nolimits_{\omega^{\prime}\in\texttt{repeats}(G)}\texttt{count}(\omega^{\prime},G)$
(1)

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):

$\omega^{\prime}=\mathop{\mathrm{argmax}}\nolimits_{\omega^{\prime}\in\texttt{repeats}(G)}|\omega^{\prime}|$
(2)

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$:

$\omega^{\prime}=\mathop{\mathrm{argmax}}\nolimits_{\omega^{\prime}\in\texttt{repeats}(G)}|\omega^{\prime}|\cdot\texttt{count}(\omega^{\prime},G)\\\
-|\omega^{\prime}|-\texttt{count}(\omega^{\prime},G)-1$ (3)

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 non-terminal, 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 $\omega^{\prime}$ and the total size of the grammar after
substituting all occurrences of $\omega^{\prime}$ with a new non-terminal
symbol in the grammar, denoted by $|G_{\omega^{\prime}\Rightarrow
N_{\omega^{\prime}}}|$, 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\in\pazocal{E}$ (defined
in Section 2.2) into a singular value Conklin and Bergeron (2008). For
example, the pitch viewpoint, denoted by the function
$\texttt{pitch}:\pazocal{E}\rightarrow\\{0,1,\dots,127\\}$, returns the midi
pitch value for a note event $e\in\pazocal{E}$. The duration viewpoint
function $\texttt{duration}:\pazocal{E}\rightarrow\mathbb{R}^{+}$ computes the
duration (in quarter notes) of a note event $e\in\pazocal{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 two note events as
follows:

$\displaystyle\texttt{ioi}(e_{i-1},e_{i})$
$\displaystyle=\begin{cases}\bot\quad\text{ if $e_{i-1}$ is $\bot$}\\\
\texttt{duration}(e_{i})-\texttt{duration}(e_{i-1})\\\
\quad\quad\text{otherwise}\end{cases}$ (4)
$\displaystyle\texttt{pitchC}(e_{i-1},e_{i})$
$\displaystyle=\begin{cases}\bot&\text{if $e_{i-1}$ is $\bot$}\\\ 1&\text{if
$\texttt{pitch}(e_{i})>\texttt{pitch}(e_{i-1})$}\\\ 0&\text{if
$\texttt{pitch}(e_{i})=\texttt{pitch}(e_{i-1})$}\\\ -1&\text{if
$\texttt{pitch}(e_{i})<\texttt{pitch}(e_{i-1})$}\\\ \end{cases}$ (5)
$\displaystyle\texttt{pitchI}(e_{i-1},e_{i})$
$\displaystyle=\begin{cases}\bot\quad\ \text{ if $e_{i-1}$ is $\bot$}\\\
\texttt{pitch}(e_{i})-\texttt{pitch}(e_{i-1})\\\ \quad\quad\text{otherwise}\\\
\end{cases}$ (6)

where $e_{i}$ and $e_{i-1}$ represent note events at sequence indices $i$ and
$i-1$, respectively, and $\bot$ represents the null value. We define a
function
$\texttt{transform}:\pazocal{V}\times\pazocal{E}^{*}\rightarrow\Phi^{*}$ that
converts an $n$-length sequence of note events $\omega{E}\in\pazocal{E}^{*}$
into a sequence of feature vectors $\omega^{\Phi}\in\Phi^{*}$ by applying a
viewpoint combination (i.e. a set $V\in\pazocal{V}$ of multiple viewpoint
functions) to each note event in the sequence. More specifically, each note
event $e_{1},e_{2},...,e_{n}\in\omega{E}$ is mapped to its corresponding
feature vector $\phi_{1},\phi_{2},...,\phi_{n}\in\omega^{\Phi}$, where each
$\phi_{i}\in\\{\bot\cup\mathbb{N}\\}^{|V|}$ is formed by applying the
constituent viewpoint functions of $V\in\pazocal{V}$ to $e_{i}$ (e.g.
$v_{1}(e_{i})$, $v_{2}(e_{i})$, …, $v_{|V|}(e_{i})$) and concatenating the
results into a $|V|$-dimensional feature vector. In our experiments,
$\pazocal{V}=\mathscr{P}(${ pitch, duration, ioi, pitchI, pitchC }$)$ where
$\mathscr{P}$ denotes the powerset. Figure 4 in the Appendix shows the result
of transform supplied with the note event sequence of Hymn 5 from the Hymns
dataset and Viewpoint Combination Index (VCI) 31. Each of the algorithms
described in this section consumes a sequence of feature vectors
$\omega^{\Phi}\in\Phi^{*}$ produced by the transform function as input.

##  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
$|\pazocal{D}\times\pazocal{V}\times\pazocal{A}|$ simulations, where
$\pazocal{D}$ is the union of all three datasets, $\pazocal{V}$ is the set of
viewpoint combinations, and $\pazocal{A}$ is the set of algorithms.888The
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. Recalling our
definition from Section 2.2, a dataset $\pazocal{D}$ comprises 2-tuples
$d_{i}=(\omega{E}_{i},P_{i})$ that each contain a note event sequence
$\omega{E}_{i}$ and a corresponding set $P_{i}$ of ground truth patterns. Each
simulation involves running an algorithm $a\in\pazocal{A}$ over a viewpoint-
transformed sequence $\omega^{\Phi}_{i}=\texttt{transform}(\omega{E}_{i},V)$
for some $V\in\pazocal{V}$ and then extracting a set of discovered patterns
$Q$ from the resulting grammar $G=a(\omega^{\Phi}_{i})$. We extract $Q$ from
$G$ by recursively expanding all non-terminals in the right-hand side of the
$G$’s start rule—each distinct non-terminal $N_{j}$ expands into a subsequence
$\omega^{\Phi}_{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 $\omega^{\Phi}_{j}$.

Algorithm 4 Fuzzy Intersection

Require: Sets $P$ and $Q$ of patterns, a sequence of feature vectors
$\omega^{\Phi}$, and a threshold value $\tau$.
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
$\tau$, and vice versa.

1:procedure FuzzyIntersection($P$, $Q$, $\omega^{\Phi}$, $\tau$)

2: $A\leftarrow\\{\\}$

3: $B\leftarrow\\{\\}$

4: for $(p,q)\in P\times Q$ do

5: for $(o_{p},o_{q})\in p\times q$ do

6: $\omega_{p}\leftarrow\texttt{extract}(o_{p},\omega^{\Phi})$

7: $\omega_{q}\leftarrow\texttt{extract}(o_{q},\omega^{\Phi})$

8: if $\texttt{similarity}(\omega_{p},\omega_{q})\geq\tau$ then

9: $A\leftarrow A\cup\\{p\\}$

10: $B\leftarrow B\cup\\{q\\}$

11: return $|A|,|B|$

Pattern similarity between a ground truth annotation $P$ and a discovered
annotation $Q$ is measured by $|P\cap 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\cap Q$ by matching patterns $p\in P$ with $q\in
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\in P$ and $q\in Q$. We can evaluate the similarity of
two occurrences $o_{p}$ and $o_{q}$ by first extracting from
$\omega^{\Phi}_{i}$ the subsequences they demarcate, which we will refer to as
$\omega_{p}$ and $\omega_{q}$, and then comparing $\omega_{p}$ and
$\omega_{q}$ using generic sequence comparision algorithms. The extraction
process is accomplished using the function
$\texttt{extract}:\mathbb{N}^{2}\times\Phi^{*}\rightarrow\Phi^{*}$ which
returns the subsequence of a feature vector sequence
$\omega^{\Phi}\in\Phi^{*}$ spanned by a pair of integer indices. We implement
similarity using the Levenshtein edit distance algorithm:

$\texttt{similarity}(\omega_{p},\omega_{q})=1-\frac{\texttt{Lev}(\omega_{p},\omega_{q})}{\max(|\omega_{p}|,|\omega_{q}|)}$
(7)

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\cap Q$ by running FuzzyIntersection with arguments $P$,
$Q$, $\omega^{\Phi}_{i}$ and $\tau=0.7$.999For 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$:

$\texttt{precision}(P,Q)=\frac{|P\cap Q|}{|Q|}$ (8)

$\texttt{recall}(P,Q)=\frac{|P\cap Q|}{|P|}$ (9)

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:

$\displaystyle\texttt{F1}(P,Q)$
$\displaystyle=\frac{2}{\frac{1}{\texttt{precision}(P,Q)}+\frac{1}{\texttt{recall}(P,Q)}}$
(10)
$\displaystyle=2\cdot\frac{\texttt{precision}(P,Q)\cdot\texttt{recall}(P,Q)}{\texttt{precision}(P,Q)+\texttt{recall}(P,Q)}$
(11)

##  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 ($\mu=0.58$) and
the lowest variance ($\sigma=0.04)$. In contrast, the same algorithm on the
Hymns dataset has the highest variance ($\sigma=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. See Figure 5 in the
Appendix for additional detail.

###  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. (Figure 6 in the Appendix shows ten annotations for
Hymn 2: five from human annotators and five from the grammatical induction
algorithms.)

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 $\tau=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). See Figure 7 in the Appendix for
details.

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 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 $\approx$
Phrase 2) or by composition (e.g. Phrase F $\approx$ 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. See Figure 7 in the Appendix for
detail.

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 human-readable 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).

$N_{s}\rightarrow$ | $N_{1},N_{1},N_{2},N_{3},N_{4},N_{5},N_{2},\langle 1.0\rangle,N_{6},N_{6},N_{3}$
---|---
$N_{1}\rightarrow$ | $N_{2},N_{2},N_{4}$
$N_{2}\rightarrow$ | $N_{7},N_{7}$
$N_{3}\rightarrow$ | $N_{7},\langle 2.0\rangle$
$N_{4}\rightarrow$ | $N_{5},N_{9},\langle 1.0\rangle,\langle 2.0\rangle$
$N_{5}\rightarrow$ | $N_{8},N_{9}$
$N_{6}\rightarrow$ | $N_{8},N_{8}$
$N_{7}\rightarrow$ | $\langle 1.0\rangle,\langle 1.0\rangle$
$N_{8}\rightarrow$ | $\langle 0.5\rangle,\langle 0.5\rangle$
$N_{9}\rightarrow$ | $N_{8},\langle 1.0\rangle$
Figure 1: The grammar $G$ for Hymn 2 generated by Sequitur using the duration
viewpoint. Numbers encased in angle brackets are the feature vectors
$\phi_{i}$ which each contain a single duration value. These feature vectors
are also the terminal symbols for $G$.

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 $N_{s}$ are actually composed from
smaller phrases or musical motifs (See Figure 8 in the Appendix for a visual
interpretation of $G$ superimposed on the Hymn 2). 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.

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. LongestFirst was the best performing algorithm on
all datasets when given sequences transformed by the optimal VCI, attaining a
maximum F1 score (averaged over all sequences) of 0.35 with VCI-2 on the Essen
dataset, 0.58 with VCI-12 on the JKUPDD, and 0.50 with VCI-3 on the Hymns
dataset.

## References

  * Barlow and Morgenstern [1953] Harold Barlow and Sam Morgenstern.  A Dictionary of Musical Themes.  Crown, New York, 1953.
  * Bod [2001] Rens Bod.  Probabilistic Grammars for Music.  In Proceedings of the Belgian-Dutch Conference on Artificial Intelligence, page 8, 2001.
  * Bodily and Ventura [2021] Paul Bodily and Dan Ventura.  Inferring structural constraints in musical sequences via multiple self-alignment.  In Proceedings of the 43rd Annual Meeting of the Cognitive Science Society, pages 1112–1118, 2021.
  * Brinkman [2020] Andrew Brinkman.  Exploring the Structure of Germanic Folksong.  Doctoral Dissertation, Ohio State University, OhioLINK Electronic Theses and Dissertations Center, 2020.
  * Bruhn [1993] Siglind Bruhn.  J.S. Bach’s Well-Tempered Clavier: In-depth Analysis and Interpretation.  Mainer, Hong Kong, 1993.
  * Bryden [2006] K. Bryden.  Using a Human-in-the-Loop Evolutionary Algorithm to Create Data-Driven Music.  In Proceedings of the 2006 IEEE World Congress on Computational Intelligence, pages 2065–2071, Vancouver, CA, 2006.
  * Carrascosa et al. [2010] Rafael Carrascosa, François Coste, Matthias Gallé, and Gabriel Infante-Lopez.  Choosing Word Occurrences for the Smallest Grammar Problem.  In Proceedings of the 4th International Conference on Language and Automata Theory and Applications, volume LNCS 6031, pages 154–165, 2010.
  * Cilibrasi et al. [2004] Rudi Cilibrasi, Paul Vitányi, and Ronald de Wolf.  Algorithmic Clustering of Music Based on String Compression.  Computer Music Journal, 28(4):49–67, 2004.
  * Conklin and Bergeron [2008] Darrell Conklin and Mathieu Bergeron.  Feature Set Patterns in Music.  Computer Music Journal, 32(1):60–70, 2008.
  * Dalhoum et al. [2008] Abdel Latif Abu Dalhoum, Manuel Alfonseca, Manuel Cebrián Ramos, Rafael Sánchez-Alfonso, and Alfonso Ortega.  Computer-Generated Music Using Grammatical Evolution.  In Proceedings of the 9th Middle Eastern Simulation Multiconference, pages 55–61, 2008.
  * Fox [2006] Charles Fox.  Genetic Hierarchical Music Structures.  In Proceedings of the Nineteenth International Florida Artificial Intelligence Research Society Conference, pages 243–247, 2006.
  * Gilbert and Conklin [2007] Edouard Gilbert and Darrell Conklin.  A Probabilistic Context-Free Grammar for Melodic Reduction.  In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, pages 83–94, 2007.
  * Green [1965] Douglass M Green.  Form in Tonal Music: An Introduction to Analysis.  Holt, Rinehart, and Winston, New York, 1965.
  * Guan et al. [2018] Yixing Guan, Jinyu Zhao, Yiqin Qiu, Zheng Zhang, and Gus Xia.  Melodic Phrase Segmentation by Deep Neural Networks., 2018.  Available online: https://arxiv.org/abs/1811.05688.
  * Hernandez-Olivan et al. [2021] Carlos Hernandez-Olivan, Jose R. Beltran, and David Diaz-Guerra.  Music Boundary Detection using Convolutional Neural Networks: A Comparative Analysis of Combined Input Features.  International Journal of Interactive Multimedia and Artificial Intelligence, 7(2), 2021.
  * Kitani and Koike [2010] Kris Makoto Kitani and Hideki Koike.  ImprovGenerator: Online Grammatical Induction for On-the-Fly Improvisation Accompaniment.  In Proceedings of the International Conference on New Interfaces for Musical Expression, pages 469–472, 2010.
  * Larsson and Moffat [1999] N.J. Larsson and A. Moffat.  Offline Dictionary-based Compression.  In Proceedings of the Data Compression Conference, pages 296–305, Snowbird, UT, USA, 1999.
  * Lattner et al. [2015] Stefan Lattner, Maarten Grachten, Kat Agres, and Carlos Eduardo Cancino Chacón.  Probabilistic Segmentation of Musical Sequences Using Restricted Boltzmann Machines.  In Proceedings of the 5th International Conference on Mathematics and Computation in Music, volume LNCS 9110, pages 323–334, 2015.
  * Louboutin and Meredith [2016] Corentin Louboutin and David Meredith.  Using General-purpose Compression Algorithms for Music Analysis.  Journal of New Music Research, 45(1):1–16, 2016.
  * Mason et al. [2019] Stacey Mason, Ceri Stagg, and Noah Wardrip-Fruin.  Lume: A System for Procedural Story Generation.  In Proceedings of the 14th International Conference on the Foundations of Digital Games, pages 1–9, 2019.
  * McCormack [1996] Jon McCormack.  Grammar Based Music Composition.  Complex Systems, 3:321–336, 1996.
  * Meredith et al. [2002] David Meredith, Kjell Lemström, 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.
  * Meredith [2013] David Meredith.  COSIATEC and SIATECCompress: Pattern Discovery by Geometric Compression.  In Proceedings of the Music Information Retrieval Evaluation eXchange, pages 48–54, Curitiba, Brazil, 2013.
  * Meredith [2015] David Meredith.  Music Analysis and Point-Set Compression.  Journal of New Music Research, 44(3):245–270, 2015.
  * Müller et al. [2006] Pascal Müller, Peter Wonka, Simon Haegler, Andreas Ulmer, and Luc Van Gool.  Procedural Modeling of Buildings.  ACM Transactions on Graphics, 25(3):614–623, 2006.
  * Neumeyer [2018] David Neumeyer.  A Guide to Schenkerian Analysis.  The University of Texas at Austin, 2018.
  * Nevill-Manning and Witten [1997] C. G. Nevill-Manning and I. H. Witten.  Identifying Hierarchical Structure in Sequences: A Linear-time Algorithm.  Journal of Artificial Intelligence Research, 7:67–82, 1997.
  * Nevill-Manning and Witten [2000] C. G. Nevill-Manning and I. H. Witten.  On-line and Off-line Heuristics for Inferring Hierarchies of Repetitions in Sequences.  Proceedings of the IEEE, 88(11):1745–1755, 2000.
  * Nieto and Farbood [2014] Oriol Nieto and Morwaread M Farbood.  Identifying Polyphonic Patterns From Audio Recordings Using Music Segmentation Techniques.  In Proceedings of the 15th International Society for Music Information Retrieval Conference, pages 411–416, Taipei, Taiwan, 2014.
  * Ritchie et al. [2015] Daniel Ritchie, Ben Mildenhall, Noah D. Goodman, and Pat Hanrahan.  Controlling Procedural Modeling Programs with Stochastically-ordered Sequential Monte Carlo.  ACM Transactions on Graphics, 34(4), 2015.  Article 105.
  * Ritchie et al. [2018] Daniel Ritchie, Sarah Jobalia, and Anna Thomas.  Example-based Authoring of Procedural Modeling Programs with Structural and Continuous Variability.  Computer Graphics Forum, 37(2):401–413, 2018.
  * Rowe [2016] Brian Rowe.  Inspired Space: Inside the Development of Astroneer, 2016.  Available at: https://www.unrealengine.com/en-US/developer-interviews/inspired-space-inside-the-development-of-astroneer.
  * Schaffrath [1995] Helmut Schaffrath.  The Essen Folksong Collection.  Center for Computer Assisted Research in the Humanities, 1995.
  * Schoenberg et al. [1967] Arnold Schoenberg, Gerald Strang, and Leonard Stein.  Fundamentals of Musical Composition.  Faber and Faber, London, 1967.
  * Steedman [1984] Mark J. Steedman.  A Generative Grammar for Jazz Chord Sequences.  Music Perception: An Interdisciplinary Journal, 2(1):52–77, 1984.
  * Talton et al. [2012] Jerry Talton, Lingfeng Yang, Ranjitha Kumar, Maxine Lim, Noah Goodman, and Radomír Měch.  Learning Design Patterns with Bayesian Grammar Induction.  In Proceedings of the 25th Annual ACM Symposium on User Interface, Software, and Technology, pages 63–74, Cambridge, Massachusetts, USA, 2012.
  * The Church of Jesus Christ of Latter-day Saints [1985] The Church of Jesus Christ of Latter-day Saints.  Hymns of the Church of Jesus Christ of Latter-day Saints.  The Church of Jesus Christ of Latter-day Saints, Salt Lake City, 1985.
  * Wolff [2011] J Wolff.  An Algorithm for the Segmentation of an Artificial Language Analogue.  British Journal of Psychology, 66:79 – 90, 2011.
  * Zeng and Lau [2021] Te Zeng and Francis C. M. Lau.  Automatic Melody Harmonization via Reinforcement Learning by Exploring Structured Representations for Melody Sequences.  Electronics, 10(20), 2021.  Article 2469.
  * Ziv and Lempel [1978] Jacob Ziv and Abraham Lempel.  Compression of Individual Sequences via Variable-rate Coding.  IEEE Transactions on Information Theory, 24(5):530–536, 1978.
  * Št’ava et al. [2010] O. Št’ava, B. Beneš, R. Měch, D. G. Aliaga, and P. Krištof.  Inverse Procedural Modeling by Automatic Generation of L-systems.  Computer Graphics Forum, 29(2):665–674, 2010.

## Appendix

##  Appendix A Background and Related Work

Techniques for segmenting musical sequences into labeled components can
roughly be divided into four algorithmic families: clustering algorithms that
operate on self-similarity matrices, multidimensional pattern matching
techniques, optimization via deep neural networks, and grammatical induction.
We begin with a formal description of the musical phrase segmentation task and
then describe previous work related to each of the areas mentioned above.

###  A.1 Problem Formulation

The musical phrase segmentation task involves assigning identifying labels to
contiguous regions of a musical sequence where each region delimits a musical
phrase. We define a musical phrase to be a short passage of music that forms a
distinct musical thought Green [1965]. If similar phrases are instances of a
repeated pattern, then they will share the same identifying label. The task of
musical phrase segmentation can be stated more formally as follows: Given an
input sequence of tokens $\omega$, output a set of discovered phrases
$Q=\\{q_{1},q_{2},\dots\\}$ such that $|Q|\leq|\omega|$ and each pattern
$q_{i}\in Q$ is a set of occurrences $O$. An occurrence $o\in O$ is pair of
integers that define the starting and ending indices of a contiguous
subsequence in $\omega$. Identifying labels can be created manually or
automatically by enumerating $Q$ and assigning each $q_{i}\in Q$ the label
$i$.

Our definition for the musical phrase segmentation task is related to two
similar tasks sponsored by the Music and Information Retrieval Exchange
(MIREX) organization. The first task is called the _structural segmentation
task_ , and is defined as follows: Given a musical sequence $\omega$,
partition $\omega$ into phrases with identifying labels such that similar
phrases receive the same label and the entire sequence is
covered.101010https://www.music-ir.org/mirex/wiki/2017:Structural_Segmentation
The second task, known as the _discovery of repeated themes and sections task_
, poses a similar problem: Given a musical sequence $\omega$, produce a set of
repeated patterns, including overlapping and nested
patterns.111111https://www.music-
ir.org/mirex/wiki/2017:Discovery_of_Repeated_Themes_%26_Sections The musical
phrase segmentation task defined above can be thought of as a hybrid of these
two MIREX tasks. Like the _structural segmentation task_ , the musical phrase
segmentation task requires an algorithm to partition $\omega$ into phrases
with identifying labels; however, these phrase partitions need not cover the
entire sequence. Additionally, we do not require phrases to be instances of a
repeated pattern nor do we allow for overlapping or nested patterns, both of
which are features of the _discovery of repeated themes and sections task_.
This new formulation captures the intuition that a musical sequence can
contain singleton phrases in addition to repeated patterns and, furthermore,
that not all subsequences are musically interesting enough to constitute a
phrase — phrase segmentation algorithms should identify salient phrases
without necessarily partitioning the entire sequence into labeled chunks.
Additionally, an overwhelming amount of ground truth annotation data consists
of disjoint rather than overlapping or nested phrase boundaries, thus we
constrain the labels assigned by a musical segmentation algorithm to cover
disjoint regions.

###  A.2 Clustering Algorithms Using Self-Similarity Matrices

One popular approach to phrase segmentation involves the use of the self-
similarity matrices. A self-similarity matrix is a matrix $M$ computed from a
sequence $\omega^{\Phi}$ of feature vectors of length $n$ such that

$\begin{array}[]{cc}M_{i,j}=d(\omega^{\Phi}_{i},\omega^{\Phi}_{j}),&i,j\in(1,...,n)\end{array}$
(12)

where the function $d$ computes the distance between individual elements
(feature vectors) of $\omega^{\Phi}$ (here we are using the subscript
$\omega^{\Phi}_{i}$ to denote the $i$-th elements of $\omega^{\Phi}$).
Repeated patterns in a sequence will appear as contiguous diagonal “stripes”
in the upper triangular portion of $M$ and are discovered using a clustering
algorithm. Nieto and Farbood [2014] propose MotivesExtractor, an algorithm
which uses chromagraphs of audio sequences to generate $M$. Pattern
occurrences are grouped together by first choosing a canonical stripe based on
length and distance from the diagonal and then scanning the remaining columns
for stripes that match the canonical stripe against a threshold. Although
originally intended to work with audio data, the clustering technique can be
converted to work with symbolic music sequences by constructing $M$ from a
sequence of appropriate feature vectors derived from a symbolic musical
sequence. Bodily and Ventura [2021] improve on this technique by
parameterizing the distance function $d$ with a vector of weights
$\bm{\theta}$ that is learned via a genetic algorithm. Pattern annotations are
produced by using a threshold to locate several maximal points in $M$ and then
backtracking along paths produced by the Smith-Waterman algorithm to find
pattern occurrences.

###  A.3 Multidimensional Pattern Matching

Meredith et. al. were the first to apply point-set algorithms to the problem
of musical sequence segmentation with the introduction of the SIATEC algorithm
Meredith et al. [2002], which works as follows. First, a symbolic musical
sequence $\omega$ is converted into a sequence of feature vectors
$\omega^{\Phi}$. Next, a translation vector is computed for every pair of
feature vectors in the dataset via vector subtraction. Minuends from the
previous step that produced the same translation vector are grouped together
into a set. Each of these sets, which now comprises a subset of the original
dataset, are termed Maximally Translatable Patterns (MTPs) and interpreted as
patterns in the original musical sequence. Occurrences for each pattern,
termed Translation Equivalence Classes (TECs), are derived by grouping all
vectors that map to the same MTP. SIATEC was designed to handle both
monophonic and polyphonic musical sequences with feature vectors of arbitrary
dimension. Further iterations of this approach can be found in Meredith [2013,
2015]; Louboutin and Meredith [2016].

###  A.4 Machine Learning

There are many approaches to generating musical sequences using deep neural
networks, but applying deep learning techniques specifically to the task of
partitioning a musical sequence into labeled sections is a relatively nascent
innovation. In the audio domain, convolutional neural networks (CNNs) are
capable of producing musical phrase boundaries when given spectrograms of
musical sequences Hernandez-Olivan et al. [2021]. In Zeng and Lau [2021], the
authors cast the phrase segmentation problem in terms of a reinforcement
learning task where an agent is given a state — represented as a note event
$e_{i}$ — and decides whether or not $e_{i}$ is a phrase boundary according to
a learned policy $\pi$. Guan et al. [2018] perform a comparison of different
types of deep learning architectures, including CNNs and Long-Short Term
Memory networks, on symbolic musical data and find that CNNs combined with
conditional random field techniques yield the best results. Other efforts in
this algorithm family include the use of Restricted Boltzmann Machines Lattner
et al. [2015].

###  A.5 Grammatical Induction

When properly interpreted, context-free grammars provide a viable solution to
the musical phrase segmentation problem because they have the ability to
organize repeated patterns into compact, labeled representations. Unlike the
methods described above, they also have the potential to unveil the
hierarchical nature of musical sequences. A context-free grammar $G$ is
formally defined as a tuple $(\pazocal{N},\pazocal{T},\pazocal{R},N_{s})$
where $\pazocal{N}$ is a set of non-terminal symbols and $\pazocal{T}$ is the
set of terminal symbols such that $\pazocal{N}\cap\pazocal{T}=\varnothing$.
Additionally, $\pazocal{R}$ is a set of transformation rules (also called
productions) that define symbol substitutions of the form
$\pazocal{N}\rightarrow{\\{\pazocal{T}\cup\pazocal{N}\\}^{*}}$ and
$N_{s}\in\pazocal{N}$ is a non-terminal symbol that is designated as the start
symbol. Given two sequences of symbols121212Unless otherwise noted, we use the
term symbol to refer to both terminal and non-terminal symbols $\alpha,\
\beta\in\\{\pazocal{T}\cup\pazocal{N}\\}^{*}$, $\alpha$ is said to be derived
from $\beta$ if and only if a finite number of applications of $\pazocal{R}$
to $\alpha$ can produce $\beta$, denoted by
$\alpha\xrightarrow[]{\pazocal{R}}\beta$. The language $L_{G}$ generated by a
grammar $G$ is defined as $\\{\omega\in\pazocal{T}^{*}\mid
N_{s}\xrightarrow[]{\pazocal{R}}\omega\\}$. When $\omega$ is a musical
sequence, the non-terminals in a context-free grammar $G$ can be interpreted
as identifiers of musical phrases — each appearance of a non-terminal $N_{i}$
in the right-hand side of $G$’s start rule corresponds to an occurrence of the
phrase $\\{\omega_{i}\in\pazocal{T}^{*}\mid
N_{i}\xrightarrow[]{\pazocal{R}}\omega_{i}\\}$ with $N_{i}$ serving as the
phrase label. We can obtain $G$ via the process of grammatical induction.

A grammatical induction algorithm $f:\pazocal{T}^{*}\rightarrow{\pazocal{G}}$
infers a context-free grammar $G\in\pazocal{G}$ from an input sequence
$\omega\in\pazocal{T}^{*}$ such that $f(\omega)=G$. We focus specifically on
“lossless”, non-probabilistic grammatical induction algorithms that add the
additional stipulation $L_{G}=\\{\omega\\}$ — that is, the language generated
by the resulting grammar is precisely the original input sequence $\omega$ —
due to their efficacy as data compression algorithms. In the literature,
approaches to this kind of grammatical induction algorithm fall into two
categories: online algorithms that process $\omega$ one token at a time while
producing a new grammar $G$ at each step Nevill-Manning and Witten [1997]; Ziv
and Lempel [1978], and offline algorithms which consume the entirety of
$\omega$ upfront and then selectively create production rules that optimize
$G$ according to some objective function Larsson and Moffat [1999]; Wolff
[2011]; Nevill-Manning and Witten [2000]. Traditionally, these algorithms
operate on sequences of strings, individual characters, or bytes, but we
employ generalized implementations that are able to operate on generic
sequences. In our experiments we run the grammatical induction algorithms on
sequences of feature vectors created by musical viewpoint combinations Conklin
and Bergeron [2008].

This study would not mark the first time that grammatical induction algorithms
have been used to identify musical phrases. Kitani and Koike [2010], for
example, encode cajon performances as sequences of duration values and then
feed the resulting sequences into Sequitur Nevill-Manning and Witten [1997] to
infer musical phrases. It is unclear, however, as to why they chose that
particular algorithm and viewpoint; it is possible that a different algorithm
and choice of viewpoints may have produced better results. In addition to
Sequitur, we evaluate four other grammatical induction algorithms and 31
unique viewpoint combinations to see which produce the best labeled sequences
when compared to human annotations. The induction algorithms we study are
well-known for their data compression attributes, and we are hoping to
discover that their success in one domain can yield viable solutions for the
musical phrase segmentation task.

(a) Visual representation

Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Onset | 0.0 | 1.0 | 2.0 | 3.0 | 4.0 | 5.0 | 6.0 | 8.0 | 9.0 | 9.5 | 10.0 | 11.0 | 12.0 | 13.0 | 14.0 | 16.0 | 17.0 | 18.0 | 19.0 | 20.0 | 21.0 | 22.0 | 24.0 | 25.0 | 26.0 | 27.0 | 27.5 | 28.0 | 29.0 | 30.0
Pitch | 60 | 65 | 63 | 68 | 70 | 70 | 72 | 73 | 72 | 70 | 72 | 68 | 67 | 65 | 63 | 70 | 63 | 65 | 67 | 68 | 70 | 72 | 73 | 70 | 68 | 65 | 68 | 70 | 70 | 68
Duration | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 0.5 | 0.5 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 1.0 | 1.0 | 0.5 | 0.5 | 1.0 | 1.0 | 2.0
(b) Note event representation

Figure 2: Representation of the note event sequence $\omega{E}$ for Hymn 5.
(a) shows a visual rendering of the musical sequence and (b) shows the note
event representation. A column in (b) shows the note event $e_{i}$ that is
equivalent to the 3-tuple $(o,p,d)$ where $o$, $p$ and $d$ represent the onset
time, the midi pitch value, and duration (in quarter notes). A note event
sequence $\omega{E}$ is comprised of note events $e_{1},e_{2},...,e_{n}$.

⬇ Phrase A: Occ 1: [0,7] Occ 2: [53,62] Phrase B: Occ 1: [8,17] Occ 2: [26,35]
Phrase C: Occ 1: [18,25] Phrase D: Occ 1: [36,42] Phrase E: Occ 1: [43,52]
Phrase F: Occ 1: [63,73]
---
(a) Textual representation

(b) Visual representation

Figure 3: Ground truth phrase annotation $P$ for Hymn 2 given by Annotator 1
represented textually (a) and visually (b). Each phrase $p\in P$ was given an
identifying label and contains one or more occurrences. Each occurrence $o$ of
the phrase $p_{i}$ is equivalent to the range $[x_{1},\ x_{2}]$ such that
$x_{1}<x_{2}\in\mathbb{N}$, where $x_{1}$ and $x_{2}$ represent the starting
and ending indices of that particular phrase occurrence. In (b), each distinct
notehead represents a note event $e_{i}$ at index $i$ (0-based). Phrases that
contain 2 or more occurrences are known as patterns — in this example, Phrases
A and B are considered patterns.

(a) Visual representation

Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Onset | 0.0 | 1.0 | 2.0 | 3.0 | 4.0 | 5.0 | 6.0 | 8.0 | 9.0 | 9.5 | 10.0 | 11.0 | 12.0 | 13.0 | 14.0 | 16.0 | 17.0 | 18.0 | 19.0 | 20.0 | 21.0 | 22.0 | 24.0 | 25.0 | 26.0 | 27.0 | 27.5 | 28.0 | 29.0 | 30.0
Pitch | 60 | 65 | 63 | 68 | 70 | 70 | 72 | 73 | 72 | 70 | 72 | 68 | 67 | 65 | 63 | 70 | 63 | 65 | 67 | 68 | 70 | 72 | 73 | 70 | 68 | 65 | 68 | 70 | 70 | 68
Duration | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 0.5 | 0.5 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 1.0 | 1.0 | 0.5 | 0.5 | 1.0 | 1.0 | 2.0
(b) Note event representation

Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
pitch | 60 | 65 | 63 | 68 | 70 | 70 | 72 | 73 | 72 | 70 | 72 | 68 | 67 | 65 | 63 | 70 | 63 | 65 | 67 | 68 | 70 | 72 | 73 | 70 | 68 | 65 | 68 | 70 | 70 | 68
duration | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 0.5 | 0.5 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 1.0 | 1.0 | 0.5 | 0.5 | 1.0 | 1.0 | 2.0
ioi | $\bot$ | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 0.5 | 0.5 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 2.0 | 1.0 | 1.0 | 1.0 | 0.5 | 0.5 | 1.0 | 1.0
pitchC | $\bot$ | 1 | -1 | 1 | 1 | 0 | 1 | 1 | -1 | -1 | 1 | -1 | -1 | -1 | -1 | 1 | -1 | 1 | 1 | 1 | 1 | 1 | 1 | -1 | -1 | -1 | 1 | 1 | 0 | -1
pitchI | $\bot$ | 5 | -2 | 5 | 2 | 0 | 2 | 1 | -1 | -2 | 2 | -4 | -1 | -2 | -2 | 7 | -7 | 2 | 2 | 1 | 2 | 2 | 1 | -3 | -2 | -3 | 3 | 2 | 0 | -2
(c) Viewpoint representation (VCI-31)

Figure 4: Representation of VCI-31, which is equal to { pitch, duration, ioi,
pitchC, pitchI }, for Hymn 5. The top (a) and middle (b) figures are repeated
from Figure 2. A column in (c) shows each element of the feature vector
$\phi_{i}$, where $i$ is indicated by the index. For example,
$\phi_{0}=\langle 60,1.0,\bot,\bot,\bot\rangle$ and $\phi_{9}=\langle
70,0.5,0.5,-1,-2\rangle$. An algorithm is given an entire sequence of feature
vectors $\omega^{\Phi}=\phi_{0},\phi_{1},...,\phi_{n}$ as input. Figure 5:
Summary of F1 scores for each algorithm and dataset. Each individual plot
shows the average F1 score (y axis) obtained by a given algorithm on a given
dataset when using each viewpoint combination (x axis). Each plot is annotated
with the mean — denoted as $\mu$ and the dashed black line — and variance
(denoted as $\sigma$) of all F1 scores across all viewpoints for that
particular algorithm and dataset combination. The columns of the figure
correspond to the dataset used, and the rows correspond to the algorithm used.
Figure 6: Ground truth and discovered annotations for Hymn 2. The first column
contains annotations from five different annotators and the second column
contains annotations generated by each grammatical induction algorithm. Figure
7: Heat map showing the F1 scores generated using FuzzyIntersection ($\tau$ =
0.7) for all ground truth and discovered patterns of Hymn 2 using the duration
viewpoint, which corresponds with the annotations shown in Figure 6. Scores
below the main diagonal are not shown. Figure 8: A visual representation of
the grammar shown in Figure 1 in the main text generated for Hymn 2 by
Sequitur using the duration viewpoint, with rule names omitted for visual
clarity. Each “box” represents a non-terminal in the grammar (the box which
represents $N_{s}$ is not shown). For example, the boxes that represent rule
$N_{1}$ are the outermost boxes that span bars 1–4 and 5–8 (these are exactly
the same boxes that correspond to Sequitur’s Pattern 1 in Figure 6, because
Pattern 1 was extracted from $N_{1}$). They each contain (as direct
descendants) three nested boxes: two for rule $N_{2}$ and one for rule
$N_{4}$. The occurrences of rule $N_{5}$ are highlighted as a visual
reference. Because we are only using the outermost boxes to designate phrase
boundaries, the nested occurrences of $N_{5}$ are subsumed in the annotation
process.