Research proposal: Grammars of music

2.1.1 Classic formal languages

The studies of languages as objects of mathematical curiosity have roots in formal logic (e.g. 🚧TODO🚧 clarify). These theorists created various approaches to understanding how strings of symbols, analogous to words or to letters, could be operated upon by various transformations, as a way of understanding how mathematical or logical propositions could interact in the process of logic itself. Among these systems, the most fully-featured ones, such as Turing’s universal machine, are posited to be capable of representing any symbolic calculation in mathematics.

The various abstract systems were combined in the modern setting by the framework of the linguist Noam Chomsky, who created a hierarchy of such systems in terms of their expressive power, ranging from simple deterministic robots up to full-powered general-purpose computing systems. The Chomsky hierarchy was developed in the hope of quantifying the complexity of “natural,” which is to say, typical human languages, on this scale of expressive power but has found far wider application.

In Chomsky’s formalism, a grammar is a tuple of:

• a finite set of terminal symbols, which is also called an alphabet
• a finite set of preterminal symbols
• a finite set of production rules which instruct how a given combination of symbols can be rewritten as a different set.
• a start symbol

A language is a list of all permitted strings of terminal symbols.

A given grammar is said to generate all the sentences in its corresponding language. By this we mean, a sentence belongs to a given language if, and only if, it may be constructed by applying the rules in that language’s grammar. In a given human language, such as English, the elements of the grammar correspond to

• A dictionary of words or, more properly, morphemes
• A set of phrase types, such as “Noun Phrase,” “Verb Phrase” and “Sentence”
• The rules of English grammar. So, we might have the rule \(Sentence \rightarrow Noun Phrase + Verb Phrase\)
• The root symbol in human languages is taken to be a “Sentence”

The language, English, in this formalism, is the list of all permissible English sentences.

By putting different restrictions on the type of rules in a given language’s grammar, we may constrain the complexity of that language, and it is this tactic that induces Chomsky’s hierarchy. In his system, for example, the most highly constrained class of languages, the regular languages, may only possess production rules of the form \(A\rightarrow a\) or \(A\rightarrow aB\). (Here preterminal symbols are written in capitals, and terminal symbols in lower case, and arbitrary lists of each are written as Greek letters).

As a concrete example, we can define a simple regular language, with just two rules:

• \(A \rightarrow aA\)
• \(A \rightarrow b\)

From the start symbol \(A\), this grammar can generate all the strings \(b, ab, aab, aaab, aaaab…\) by repeated application of the rules.

Some thought reveals, however, that no regular grammar can recognise language that looks like this: \(ab, aabb, aabb, aaabbb, aaaabbbb…\). i.e. we cannot find a finite number of rules that include all (and only) the strings of so-many a followed by the same number of b. To generate such a language, we need a more powerful class of grammar, the “context-sensitive” grammar, which allows any rule of the form \(A\rightarrow \gamma\). Then we may choose the following rules, where \(\lambda\) is, by convention, an empty string:

• \(A \rightarrow aAb\)
• \(A \rightarrow \lambda\)

More generally, Chomsky’s hierarchy contains 4 Types, with the regular languages, and the context-free languages as Type 4 and Type 3 respectively.

Formal language theory is closely linked to the complementary field automata theory, the study of abstract mathematical machines that transform one string of symbols into another.

For every language type in the hierarchy there is a corresponding automaton, an abstract mathematical machine, which can recognise the language — that is, which can answer the question of whether a given sentence belongs to the language of a given grammar, or not. Equivalently, such an automaton may generate permissible sentences from that language.

The most famous class of automata is likely the Turing machine, although there are many more. Generalisations of these basic automata to discrete systems other than strings exist, most famously cellular automata.

In terms of automata theory, the question: “How powerful a grammar is needed to represent a given language?” may be transformed into an equivalent question: “How powerful an automaton is needed to correctly recognise whether or not a sentence belongs to a given language?” or, “How powerful an automaton is needed to generate all the sentences in a given language?”

There exist many theorems linking particular automata constructions to particular grammatical constructions, and many questions that may be answered within either formalism.

Throughout this document, the equivalences of these systems will be taken as given except where noted, and the most convenient terminology for the topic in hand will be used.

The classic Chomsky hierarchy is summarised in the following table:

In fact, modern automata theory admits of many categories of automata between the classic types listed here, which can recognise, in turn, languages intermediate in complexity between these. For the current purposes the classic Chomsky hierarchy gives us enough landmarks to locate the complexity of a given production system of interest, and we will not attempt to exhaustively document every class of automaton considered by modern theory, except to note that various sub-types will turn out to be important in later applications, and that these will be introduced as necessary. (But see 🚧TODO🚧 clarify and 🚧TODO🚧 clarify for overviews.)

We are concerned not only with the use of automata to recognise languages, but also automata to produce examples of a language — that is, with constructing machines whose output is a valid “sentence” in our language of choice. General automata capable of such general processes as not simply accepting or rejecting a sentence but outputting arbitrary output such as whole new sentences are referred to as “transducers” in the literature.

I will not make much of this distinction here, however, as there exist reasonably straightforward translations between recognising and transducing automata.

The further one descends the hierarchy, the more powerful the class of automaton that is required to recognise it. Specifically, the lower one is on the hierarchy, the higher the upper bound on the memory required by that recognising automaton relative to the size of the input.

A regular language may be recognised by an automaton with no memory other than its current state.

Recognising a context-free language requires a “stack,” an internal list of states. Recognising a context-sensitive language requires storage capacity proportional to the length of the input sentence. And to recognise a general recursively enumerable language can require the unbounded storage capacity of a Turing machine.

Thus, in the study of human language, to recognise a sentence as, say, a valid English utterance, one has to know not only that the words within it are valid English words, but that the sentence may be “parsed” into a legal application of the grammatical rules of English.

Thus, if we posit that the following are grammatical rules in English:

• \(S \rightarrow NP VP\)
• \(N \rightarrow NAME\)
• \(N \rightarrow DET N\)
• \(VP \rightarrow V NP\)

If we further stipulate that “John” is of lexical type NAME, “fed” is of type V, “the” is of type DET and “numbat” is of type N, then the sentence “John fed the numbat” is in the English language, since it may be parsed according to those rules as follows:

By the same token, “the numbat fed John” is also permissible, but not, on the other hand, “numbat John the fed.”

The terminal symbols need not be words or classes of words, but all grammars possess these basic structures, and musical grammars are typically similar in appearance. Here, for example, is part of the musical grammar of de Haas’s model used on harmonic similarity of jazz tunes:

• \(Piece \rightarrow P+\)
• \(P \rightarrow PCP\)
• \(P \rightarrow HCP\)
• \(PCP \rightarrow d t+\)
• \(PCP \rightarrow t d t\)
• \(HCP \rightarrow t+ d\)
• …

In this grammar, d and t are taken to indicate, approximately, dominant and tonic chords, rather than words, but the linear structure of the piece is posited to be understandable in terms of a hierarchical parse much like an English sentence.

For brevity, throughout this document I will use “parse” to mean “inferring a permissible application of grammatical rules for a given production using a given grammar,” without presupposing a particular degree of complexity for the grammar in question. That is, although “parse trees” are often used to imply that the grammar in question is at least context-free in power, I will not assume so here.

I will also use variously “production,” “sentence” or “piece” synonymously to indicate entities contained within a language. “Production” is the most general, but when I wish to emphasise grammars for natural language, or for music, the latter two terms are useful as well.

2.1.2 Stochastic Formal Languages

Generalising all these grammars are probabilistic, or stochastic, versions where production rules in the system are decorated with weights which give the probability that any matching rule will be chosen. These generalised systems are ascendant in modern machine processing of language for many reasons such as ease of inference from data and graceful degradation under poor input. Moreover, they are the foundational tool upon which this thesis hopes to improve over established work in the field, and so they will be expanded at length here.

We can assign explicit probabilities to each transition within a grammar (or, alternatively, to each possible generated string).

The field was formalised in modern terms for regular languages by Rabin and for general grammars by Booth and Salomaa. but practical uses of such probabilistic automata predate those. Notably, Shannon’s mathematical theory of communication

used finite-alphabet Markov processes, corresponding to stochastic finite-state automata, in his approximating models for human language (following Markov’s 1913 lead applying Markov process to analysing Pushkin).

Later, an influential paper by von Neumann

considered the problem of constructing deterministic machines from probabilistic ones.

The use of such objects has only proliferated since then, as has terminology to describe them. Vidal et al. identify a huge number of formally equivalent terms used to describe these objects, depending on the discipline and whether one wishes to emphasise, for example, recognition, generation, or inference.

For Type-3 probabilistic automata, we can refer to probabilistic finite-state automata, stochastic regular grammars, Markov chains, n-grams, probabilistic suffix trees, deterministic stochastic or probabilistic automata, or weighted automata.

Such grammars not only distinguish whether a given sentence is a possible production of a given grammar, but they also supply us with some notion of the probability that such a sentence could have been produced by one or another grammar. Or, upon our observation of a particular sentence with multiple possible parses, we can calculate the relative probability the sentence resulted from each of the possible candidate parses.

Regular Languages and Context-Free Languages, and their associated automata, Markov machines, and Stochastic Stack Automata, occur regularly in the study of languages. Stochastic generalisations can equally apply to more general automata, and even Turing machines have fully probabilistic formulations. More powerful machines are capable of general stochastic calculation just as their non-stochastic peers are capable of non-stochastic calculation, and one may even emulate the other.

These general versions are rarely used in a grammatical inference context because of the difficulties in general inference and will accordingly not be discussed further here.

Recently, stochastic automata and languages have received attention from outside linguistics, in the study of stochastic dynamical systems, in a field frequently called “computational mechanics”.

Dynamical systems include such objects as classic chaotic attractors like the Lorenz “butterfly”, the value of an American option in the Black-Scholes model, or the stochastic predator-prey model.

Classical, real-valued dynamical systems may be quantised into “finite alphabet” processes and modelled as outputs of stochastic automata. Such a quantisation can in certain cases be statistically equivalent to even a continuous measured process. For our purposes, a key point is to note this field has produced additional automated procedures for inferring such automata from the data,

and that such methods are frequently more parsimonious than those of the natural language literature, avoiding such complexities as phonetics and lexicons, while still being informed by the same underlying theoretical principles.

2.2.1 L-systems

Named in honour of their originator, botanist Aristid Lindenmayer, L-systems,

have been influential as a compact representation of the growth and morphology of plants. Recently, they have been commercially successful in computer graphics as design systems for trees, and for, e.g. architectural design processes.

These systems form a parallel hierarchy of formal languages with close relations to the Chomsky hierarchy. They differ in details; L-systems make no distinction between terminal and preterminal symbols, and their rules are applied in parallel, simultaneously transforming all symbols by the matching rules rather than sequentially applying them as in Chomsky grammars.

There are also subtle terminological differences; a “deterministic” L-system (or “D0L-system”) is a non-stochastic L-system, rather than a deterministic automaton in the computer science sense. There are several formulations of the L-systems at different levels of grammatical complexity.

The original “D0L” formulation is closely related to, though slightly more general than, a Context-Free Grammar, while the “D1L, D2L, D3L…” versions support stronger degrees of context-sensitivity. They are associated with two other features of relevance to our purposes here which are less often seen in classic grammars:

Firstly, L-systems typically concern themselves not only with rewriting operations upon a string of symbols, but, in addition, the interpretation of such symbols. Typically, terminal symbols are expressed as instructions to a turtle.

Turtles are a convention in computer graphics, originating in the work of Seymour Papert on the Logo teaching programming language. Some symbols draw particular shapes, such as a leaf or petal, and others are, for example, instructions to rotate, scale, or alter the colour of subsequent drawing instructions.

The result is that while the symbol string might indicate the structure of a synthesised plant, it is this interpretation which determines the shape and appearance of the image representing it. In the study of musical grammars, although the interpretation of symbols must necessarily be different, the issue of choosing meaningful interpretations remains pertinent.

Secondly, L-systems possess a variant with no equivalent in automata-based languages, the bracketed form. Bracketed L-Systems bless a particular pair of symbols, typically the square brackets, as instructions to push or pop a graphics context stack, enabling the turtle cursor to draw one component of the L-system before returning to a prior location to draw another. These constructions are usually used to draw branches in branching systems, such as models of trees.

In classic sequential automata operating on linear strings, which have no notion of concurrent expression of rules, such constructions are unnecessary. In grammars intended to, potentially, express multiple concurrent streams of symbols, say, a melody and percussion line, in which the order in which the string is interpreted as graphical instructions changes the output, such constructions are important.

2.2.2 Shape Grammars

Related to the parallel literature in L-system synthesis, there exists a further parallel literature on grammars having elements other than abstract symbols. The so-called “shape grammars” operate upon geometric shapes and were conceived as an aid to generating novel shapes in design. Exemplars of this tradition include originators, Gips and Steiny,

who applied them to two-dimensional geometry,

who interpreted terminals as subdivisions of n-dimensional volumes, and Leyton

to deformation curves of plastic objects. This field has now, however, been largely absorbed on one side into the study of L-systems and on the other into Iterated Function systems, and will not be treated further here.

2.2.3 Iterated Function Systems and Superfractals

Equivalent in the limit to deterministic L-systems,

but constructed using formalism with some surface differences, the fractal forms of Iterated Function Systems or IFS

are also design grammars. The class of IFS includes the classic Barnsley Fern and a broad class of systems using iterative application of transformations on the basis of a design grammar. More recently, a generalised IFS called the “V-Variable fractal”, related to the random fractal,

has been introduced which has the same formal relation to stochastic L-systems as does its non-probabilistic peer to non-probabilistic L-systems. While much work has gone into the rapid production of L-systems, it is IFSs that have dominated the efforts of research into inference, and thus they are both deserving of coverage in this proposal.

2.3.1 Learning grammars from interpreted productions

All the aforementioned grammatical inference techniques operate on simple symbol strings. There is a more general inference problem, which is to infer the grammar of the system after the symbol string representing it has been interpreted as some kind of, e.g. graphical instruction set, as in the case of L-systems, or, as in the case of this project, as a musical score. In a complex case, such as inferring a grammar for a 3-dimensional object from a two-dimensional projection, even basic parsing can become challenging. This particular problem is an active area of research in computational architecture (that is, in designing built structures using computers) where design schema are inferred from photos.

The inverse operation to interpretation is by convention encoding, and while there are a limited set of conventions for this in L-systems, in music, there exist many different conventions for doing so, e.g.

.

Given a sufficiently well-behaved interpretation, such as an isomorphic map, encoding and interpretation may both be well defined and equally easy. In the case that we are not given the encoding, but have to infer it as well, the situation is more difficult.

The domain of problems where one must not only infer the grammar, but also select the interpretation/encoding schema used is large and poorly understood. In L-system-based modelling of plants this problem is usually solved manually. A researcher hard-codes interpretations by assigning a conventional set of graphic operations to symbols output by the grammatical rules, such as mapping the symbol + to a turtle instruction such as “turn right 30 degrees”. (See, however,

for an example of a limited attempt to automate this.) Such sets of transformations are generally chosen by hand to be those most intuitively “natural” seeming for the system under consideration; for example, if branches frequently leave the trunk in a given tree at an angle of 30 degrees, it seems reasonable to have a symbol interpreted as a 30-degree turn.

Early work in the inference area is dominated by the problem of encoding images as Iterated Function Systems, typically for use in image compression.

For many limited classes of inference, efficient algorithms are known; so Davis

showed that a restricted version of Jacquin’s fractal encoder

using only affine transformations of image kernels, was equivalent to a Haar wavelet sub-tree quantisation, and could be solved by the well-known, and efficient, techniques of wavelet analysis. Or, to turn that idea on its head, for some classes of IFS we may infer the image grammar and terminal interpretation simultaneously as the output of an appropriate wavelet transform.

Alternatively, on the problem of inferring generating grammars of three-dimensional forms where we do not have guarantees of strictly affine transforms, solutions can be found by applying other strong constraints to the search space, for example by limiting terminal shapes to line segments and by disallowing recursion. Alternatively, by limiting production rules to rectangular surfaces, grammar induction can be handled by reinforcement learning.

Or, by assuming a near-Markovian form for a potentially context-free grammar, Bayesian inference using Markov-chain Monte Carlo methods can be made to converge rapidly with more general geometric transformations. Many other such constrained schemes are known and are used in object classification

and in the subcategory of machine vision known as syntactic pattern recognition.

For problems without convenient restrictions, less rapid search techniques such as genetic programming of the interpretations and rules are required, often concurrent evolution of both. In genetically programmed systems, pre-processing of the source data can still reduce the complexity of the search. There have been experiments in using alternate representations of the source data, such as wavelet transforms and Fourier-domain representation,

or images preprocessed for useful features.

More recently, work has been done in speeding search simply by harnessing the easy parallelisation of both L-systems and of evolutionary search on GPU.

None of these image-based techniques generalize immediately to the musical domain, but they each provide suggestive hints toward classes of techniques that might be applied; thus, for example, while the wavelet transform of an image is rather unlike the wavelet transform of any musical event signal, a simplified version of the former might be a useful step toward the latter.

2.3.2 Learning music grammar from music events

A related set of problems is to infer an underlying grammar when the production to be interpreted is a musical piece. There is a large body of work on applying to the analysis of music, but rather less on the inference of those rules.

Of those that do attempt to infer rules in an unsupervised fashion, most assume both Markovian grammars and essentially monophonic input. (e.g.

and

). Recently,

and

have extended analyses to restricted types of polyphony but have kept the Markovian restriction. On the other hand,

has successfully trained probabilistic CFGs on the Essen Folk-song collection but remained restricted to strict monophony.

This process is complicated to an extent by the necessity of choosing not just a symbol sequence, but an interpretation of that symbol sequence, as in general L-system inference problems. As with L-systems, the expression of a musical grammar must include not only a hierarchical tree parsed from the symbol string but a list of interpretations of symbols. Convention also supplies a stock of such interpretations in musical grammar studies, such as note transpositions and chord tension.

For the newer area of music, there is the choice of either examining the problem of inferring such interpretations by hand or using one of the default interpretations.

On one hand, the default interpretations are easy to infer, being natural, simple, and easy. On the other, they have been chosen largely on the basis of convenience and are heavily imbued with the presuppositions of Western music theory, and can only encode a limited subset of music data, being essentially monophonic and sequential.

A more general approach to inference might consider interpretations of symbols analogous to those inferred in IFS work, where affine, projective, or even general non-linear contracting maps are used.

In the spirit of such analogies, we would consider interpreting symbols not just as a pitch or time interval, or a relative degree of tension in a chord, but as a transformation upon a musical motif. Rules could encode, for example:

• a tempo-doubling
• a transposition with respect to a particular scale
• transposition some number of semitone steps
• a chord inversion
• a phrase truncation

Given the complexity of inferring arbitrary encodings and interpretations of grammatical symbols, I will experiment with a hand-selected set of such encodings but do not plan to infer them without presupposing a limited set of forms for the rules at this stage.

2.3.3 Simplicity in grammatical inference

A crucial problem in grammatical inference is deciding what is meant by inferring a “better” grammar; there are many answers to this. Intuitively, if a smaller number of rules can describe the same corpus, or if the same number of rules can describe more of the corpus, then it might seem that we have found a “better” grammar. For example, one may easily infer a language that has a single rule for every example, and thus, trivially, every sentence in the language may be expressed within it. But this grammar would not be ideal, since it has a huge number of complex rules, one per input datum, and yet cannot generalize to new data at all. On the other hand, a grammar that accepted every piece would have massively overgeneralised and yet told us little. We wish to avoid over-fitting by degenerate rules such as \(S\rightarrow\) Beethoven’s Moonlight Sonata. The question is, rather, what order of language succeeds in both generalising, and in more compactly expressing, a given musical structure, by some metric. Concretely, if we can relax the common presumption that musical grammars must be Markovian, and infer, rather, a context-free grammar over some corpus, and then describe that corpus more effectively, then we might feel that this challenge has been met; it turns out that this can be formalised as the Minimum Description Length (MDL) principle,

This is a formalisation of the earlier idea of Kolmogorov-Chaitin complexity,

which measures the complexity of a phenomenon by the length of the description of that phenomenon. Historically, this idea has been associated with Solomonoff’s formal theory of inference. This idea is, loosely, the idea that we can formalize scientific inference as a process of finding and quantifying the patterns in phenomena.

Practically, Kolmogorov-Chaitin complexity in its original form is not often used; it is in general uncomputable, and has other deficiencies such as being dominated by the random component of stochastic processes. The MDL idea formalises a calculable measure of the complexity of the system; roughly the “coding” of the system, which quantifies how complex an automaton can describe the data, where both the description of the automaton and its parameters are included in this measure of “complexity”. It also provides us with the normative principle that it is this description length that we should aim to minimise.

This is closely related to the stochastic complexity of Crutchfield’s \(\epsilon\)-machines.

MDL techniques are fully developed, and have such attractive features as being able to gracefully handle sparse data; practically, if we have a complex model, but not enough data to learn it, then we are impelled to choose a simpler model which may fit the data better.

In practice, MDL procedures are already used in grammatical inference and have even been employed in the musical domain for Hidden Markov Models. Using them should therefore be straightforward.

There are other techniques available to select model classes; standard cross-validation techniques and standard model selection tasks, for example, can be used to similar ends.

The attraction of this case is description length is a natural fit to the framing of this research in terms of automata. It captures in an intuitive fashion the idea that the project will be successful if a small increase in the complexity of grammar, from Markov to probabilistic context-free, enables a more compact representation of the complexity of the patterns in music.

2.3.4 Classification using inferred grammars

One of the most foundational purposes of stochastic grammars is the classification of productions, and techniques exist to, for example, automatically infer which language a given sentence belongs to using such systems, e.g. Such systems are well-developed and in frequent commercial use in, e.g. Google Translate.

Less well-developed, there are a number of attempts to use generating automata to classify musical pieces using generating automata.

The simplest of these simply classify given pieces based on the probability that they were generated by a particular grammar. For grammars inferred from several different corpora, a given piece is simply supposed to belong to the grammar that was most likely to have produced it. More generally, the form of a grammar can be used as a source of additional features with which to train any other classifier system, such as a support vector machine, and providing better structural features is likely to produce better results in music classification tasks.

Such elaborations will not be considered further here, as the basic probability estimates are sufficient for a simple verification step.

2.4.1 Markov processes and regular languages

Starting with the least powerful languages, we note early work attempted to place the theory of harmony on an information-theoretic basis in the fifties and, soon after, Markov models were applied to composer style identification.

Taking things further, composers such as Xenakis actively employed Markov models in their compositions. Xenakis’s Analogique A and B, as described in his book ‘Formalized Music’, were based around such processes. Ames provides a summary of various works, including several algorithmic scores created using Markov models.

More recently, Pachet has created a real-time Markovian jazz improvisation system based on Markov models.

Recently there has been interest in using such systems as models of the state transition structure of the Markov graph to quantify song structure complexity in birds.

2.4.2 Partially Observable and Hidden Markov Models

A modest generalisation of the Markov model, but still more tractable than context-free systems in full generality, is the partially observable Markov model. This has received attention for its use in modelling birdsong, and the suppositions about the cognitive basis for such song.

has showed that one such language can explain the most complex birdsong, such as that of the Benegalese Finch, and workers such as Fee et al and Jin have tied this to the underlying neural and physiological mechanisms within the birds.

Authors such as Mavromatis and Noland have used Markov models in musical inference and generation, for key estimation.

Cruz-Alcázar and Vidal have identified melodic style and musical key using such systems.

2.4.3 Context-Free Grammars

Although Markovian models have been successful in some aspects of musical analysis by virtue of their simplicity and ease of use, it is likely that they fail to capture much of the structure of music, and much effort has been spent in applying higher-complexity systems. Rohrmeier argues that super-Markovian complexity rules are required to handle harmonic progressions in Western tonal music.

Accordingly, many schemes have been proposed.

In general, the grammars used as models of musical structure have been hand-designed. For example, Steedman designed a context-free grammar specifically for the delimited domain of Blues chord progressions, later extended by Chemillier for real-time use.

More exotic schemes, such as using context-free grammars to partition time and pitches, have also been employed.

There have been many models besides these — notably even Leonard Bernstein has weighed in. However, the most prominent at this date seems to be Lerdahl and Jackendoff’s Generative Theory of Tonal Music (GTTM). Their approach parses music sequential data as in classic grammars, and thus is essentially monophonic. However, it does offer a model of a parse tree with chords rather than single nodes as the leaves, when augmented with a theory of consonance. Lerdahl’s later Tonal Pitch Space is the preferred model for this.

Recently, parsing under this system has been partially automated. Hamanaka has developed software capable of parsing a given piece of music using Lerdahl’s GTTM grammar.

However, as the grammar in this case is supplied a priori, there is no attempt to solve the grammatical inference problem in generality. Notably, also, the grammar is not a probabilistic one, but a set of grammatical rules supplemented with a preference ordering over alternative parses; different parse trees cannot be assigned, for example, a likelihood in the system as envisaged by its creators, though such an extension would presumably be straightforward.

There have been many attempts to solve specific sub-problems in this grammatical inference domain with a more general grammatical model. The work of Bod et al on folk song melody databases uses a full probabilistic inference system recognisable from probabilistic NLP.

Though the model used can handle only melodies rather than chords, it has the most in common with the approaches discussed in this proposal. Bod et al argue that in inferring such grammars, similar regularisation parameters are necessary for probabilistic parsers both for natural language and for musical inference; such a coincidence, they argue, is suggestive of parallels between the mechanisms involved in each activity.

2.4.4 Constraint programming

At the highest level of generality and the lowest level of the Chomsky hierarchy, the arbitrarily powerful systems of context-sensitive grammar and constraint programming reside. Despite the challenges of such systems, their use in music is an expanding research area, since they make it easy to encode the rules of an a priori theory of music whose constraints must be satisfied, such as constraints on the consonance or dissonance of concurrently played notes, or weightings on bar boundaries.

For the above-mentioned reasons of difficulty of inference, however, there appear to be no attempts to infer rule sets for such systems empirically. In examples from this field, rules are typically constructed from hand-crafted theories of musical consonance or constraints. Despite the intuitive attractions of being able to directly express an explicit theory of music, it is an open question whether such complex systems are necessary to encode music in general. The trade-off for their generality and directness is extreme difficulty in inference, and these systems are riven with undecidability issues. This proposal attempts to make do with more parsimonious, and thus more falsifiable, means to model music. Whilst not ruling out the possibility of requiring general-purpose computing to be ascribed to musical sequences, it seems desirable to exhaust the possibilities of simpler systems first; moreover, the success in capturing so much of natural language with simple models leads us to suspect that such models might be similarly successful in music. As such, if we ultimately discover that no context-free model can adequately describe music, then we are left with a remarkable result inferring substantially different cognitive mechanisms might be at play in each.

2.4.5 L-systems

To return to the related L-system program, we find that they are in use in creating and analysing music in a diversity of fashions. On the microscopic scale, L-systems have been used in synthesis algorithms to create self-similar wave-forms. More commonly they are used to devise more macroscopic features, such as notes and phrases.

That said, the most active art form as regards the prominence of such models seems to be in architecture, where rule-based and procedural systems based on these are actively used both for individual buildings and for large-scale urban planning. In this context, they are prized for computational and storage efficiency with which they can generate architectural features.

3.2.1 Expressing a grammar as music

Expressing a musical grammar as music is reasonably straightforward; there exist many tools capable of handling reasonably complex stochastic grammatical expressions as music, such as the Smalltalk dialect SuperCollider, the Oz dialect Strasheela, or even non-musical systems such as Lisp-derivative Church.

I do not propose to presume any particular complexity class of grammar at this stage; as discussed earlier the increase in effort for expressing Turing-complete automata is only marginally greater than that of more basic systems. An ideal solution would be one that could be played audibly, to allow intuitive exploration, but which could also produce machine-readable output as input to other steps in the process and ideally, scores. All these goals appear straightforward with the tools to hand.

3.2.2 Pre-process musical event data into symbols

As discussed earlier, musical event data require an interpretation to map between sets of musical events and the strings of symbols that are the basis of grammatical inference theory.

Although there is much potential to explore inference techniques to deduce interpretations for grammars, at the initial stage I will focus on simple rules from the literature, such as the lists in @citation rather than inferring new rules, with an eye to exploring automatic interpretation inference at a later stage if the data merit it.

3.2.3 Parsing a musical piece using a musical grammar

Parsing is identifying the states that an automaton assumed in emitting a given production; that is, identifying which grammatical rules were responsible for each symbol in a production. In the case of a probabilistic grammar, this means identifying all likely possible states that could have produced a given piece, and their relative probabilities. Unlike expressing a grammar, parsing productions generated by more complex automata can be more computationally complex. It is this later step, of parsing, that will constrain the complexity class of grammars used in later stages, and which provides a motivation to avoid excessively complex models such as context-sensitive or unrestricted grammars.

For the classes of models here, the complexity of this step will be modest. To parse a production in full generality can be difficult, in the worst case. Inferring parse trees with, for example, unrestricted grammars, on general symbol strings can be a computationally, or even undecidable problem.

Fortunately, for more restricted systems, the problem is typically easy. For this project, where we hope to infer simple sequences of symbols from music, and context-free grammars for music, the problem is well-explored and in general computationally affordable.

For the moment, therefore, I proceed with the assumption that such simple parsers will be sufficient, and that using one of the many available parser-generators will be sufficient.

Creating and estimating likelihoods for probabilistic parses is a necessary pre-condition for inferring grammars; otherwise we cannot compare our predictions with our intuitions. For example, Bod was able to confirm the utility of his parser by comparing the emitted parse trees for folk songs in the Essen Dataset by comparing the parse-tree-inferred phrase structure with the manually-supplied annotations in the data set.

For other datasets under consideration, such as the Million Song Dataset, it might be necessary to supply a manually-annotated test-set, or to test the parse trees implicitly, by resynthesising new pieces using them, or comparing the effectiveness of the inferred rules as an input to grammatical inference. At this stage, no more complexity will be assumed for this step, though I note that the potential to revisit this assumption should the data necessitate it.

3.2.4 Inferring a grammar from a corpus of pieces

Grammatical inference is the most computationally expensive component of this process. It is distinct from the problem of parsing; while parsing attempts to recover the states a given automaton assumed in producing a piece, inferring attempts to recover the automaton itself, given many pieces. In plain language, inferring a good grammar requires that we are able to produce a probabilistic grammar that is optimal in some sense — e.g. that uses the most parsimonious possible rule set or that provides the highest-likelihood parses of a given corpus.

Some inference strategies, such as candidate grammars to a learnable subset of all possible grammars, such as “substitutable” grammars, can ease the computational burden, as can accepting probabilistic error. Fortunately, a wide variety of off-the-shelf solutions for probabilistic grammatical inference, such as the Stanford Lexicalized Parser and the Bikel Parser, and many others besides. This step therefore reduces to the question of trying and evaluating these until one adequate for my purposes is identified, and choosing appropriate parameters for its learning algorithms based on the corpora that we have available.

3.2.5 Inferring symbol interpretations

These discussions of difficulty of parses assume that we are already given a symbol string to parse, which, in the case of monophonic input is a reasonable assumption. If, however, I attempt to generalize the algorithm to handle polyphony or polyrhythm, where two concurrent symbols might reasonably be expected to be expressions of two different symbolic rules, the parsing procedure can become substantially harder. With concurrent symbols, this problem becomes equivalent to the general problem of branched L-system parsing.

Unlike the general problem of parsing, say, a shape grammar from raw image input, musical event representations are already low dimensional, and, e.g. Cruz-Alcázar and Vidal argue that appropriate pre-processing of data can reduce the problem to one only marginally more complex than basic inference, contingent on some mild restrictions of the complexity of the grammar to parse. The investment of time in this component of the project will be contingent upon the success achieved with the simplest possible rule interpretations; if inference results are not sensitive to choices of rule set, there would be little purpose investing extra time in this step.

3.2.6 Comparing effectiveness of grammars induced by different corpora

Finally, the project requires using inferred grammars to produce measurable improvements to existing schemes of classification and inference about music. To this end, it will be necessary to choose metrics between parses, and/or grammars. The primary point of comparison will be comparing restricted (Markov) inferred grammars to less restricted (context-free) grammars.

There are subtle difficulties here; for one, even in grammars as simple as context-free, the general equivalence problem is undecidable — that is, we cannot know in general that two alternative inferred grammars have identified the same language.

Such problems are, in fact, worst-case problems. Whilst this research proposes expanding the power of grammars inferred, there is no reason to suppose that a well-regularised selection process will produce such pathological cases. If it did indeed do so, then I would further hope that the pathological grammars would cast light on ambiguity in the music itself or are in some way reflective of human cognitive constraints.

Moreover, we can avoid this to a degree by comparing in terms of “simplicity”; that is, in terms of the minimum description length. All this requires is a consistent definition of our coding system, and a consistent measure of how successfully our grammar has explained the data. Standard techniques exist for estimating success in the statistical natural language processing literature by, e.g. assigning a likelihood of the generation of a given piece by a given grammar.

This process gives us P-values, that is, standard significance tests, for given pieces to estimate their suitability to a given grammar, giving us a mean likelihood when averaged across the test data.

3.2.7 Validating results by use of inferred grammars in classification

Rather than staking all the verification of the model discussed here in this rather abstract procedure of measuring description lengths and so on, it is desirable to measure performance of the algorithm on at least one practical, real-world application if there is available time. Classification seems the most straightforward task here. As discussed earlier, there are many attempts to classify pieces using probabilistic automata, most directly by rating the “probability” of a given piece given a given grammar. For my purposes, a simple validation of the model, in addition to standard significance tests, would be training grammars on different corpora. For most of the datasets, for example, we might divide the dataset into different genre corpora using the dataset metadata and train genre-specific grammars on these. On these outputs, I can measure performance at classification both with simple Markov automata and my more complex grammar systems to evaluate how much, if any, improved accuracy has been gained. Then I may compare the efficacy of different degrees of grammatical complexity at this task in terms of test-data error. It is straightforward to compare the efficacy of such classification with other published research in the field that uses related techniques — such as de la Higuera’s automated inference learning of Markovian musical grammars for classification.