Research proposal: Grammars of music

2.1.1 Stochastic Formal Languages

Generalising all these grammars are probabilistic, or stochastic, version 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 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, then 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 of 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 and 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 making no distinction between terminal and preterminal symbols, and their rules are applied 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 symbol draw particular shapes, such as a leaf or petal, and others are for example, as instructions to rotate, scale or alter the colour of subsequent drawing instructions. .

The results 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 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 guarntees 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 is required

, often concurrent evolution of both . In genetically programmed systems, pre-processing of the source data can still to reduce the complexity of the search. There have been experiments in using alternate representations of the source data, such 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 generalise 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 are 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 the 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 been 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 taking examining the problem of inferring such interpretations by hand, of 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 the 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 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 generalise to new data at al. 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 in 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 phenomena by the length of the description of that phenomena. Historically, this idea has been associated with Solomonoff’s formal theory of inference . This idea is, loosely, the idea that we can formalise 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 will 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 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 an 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 a 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 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 such 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 — notable 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, prasing under 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, 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

has used L-systems 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 regard 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

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 wil 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 symbols 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 a many other 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 assumes 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 generalise 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 discussed 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. Thence 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 use related techniques — such as de la Higuera’s automated inference learning of Markovian musical grammars for classification.