A study of grammar-based compression in application to music analysis

Music is an important phenomenon in human civilization, about which we understand surprisingly little. In 2014, the Computational Music Research Group of the School of Computer Science, Cardiff University, demonstrated the utility of computing compressive context-free straight-line grammars as a powerful framework for symbolic analysis of music (with applications in structure analysis, error detection/spell-checking, and high-level editing). This work explores the hypotheses that (a) constructing grammars from music data is a viable method of music analysis, with the smallest grammar producing the most significant representation, and (b) it is possible to improve upon analytical effectiveness by increasing substring similarity in order to produce smaller models. Many studies have presented computational models of musical structure, particularly as logically coded algorithms or deep learning models, as an important aspect of musicological analysis. However, the attempt to use grammar-based compression to automatically perform musicological tasks (such as pattern discovery) is a relatively new and already promising technique. Using a publicly available collection of nearly 8000 digital scores, this thesis represents an extensive investigation detailing the performance of grammars against a range of compressors, when applied to error detection, classification and segmentation tasks, and detailing a novel method of transcription error location, where grammars outperform the algorithms tested. Despite making no use of specific domain knowledge, grammar-based compressors are demonstrated to be a competitive tool for musicological investigation. Increasing the coverage a single production rule can provide within the encoding of a grammar is a technique proven to be effective in increasing compression. However, the use of domain-specific structures may provide an advantage over more general or constrained approaches to modelling equivalence. Using a novel method of increasing similarity which is fully adaptable to include general, specific or domain-based modification or production rules, this study demonstrates the possibility of leveraging an additional dimension in the substring search space in order to produce smaller models. Experiments confirm that even with stringent constraints the production of smaller encodings is possible, and, particularly with regard to musical data, even minor reductions are able to produce better results for analytical applications. The study also presents a novel method of selecting substrings for inclusion in a grammar under construction, using a heuristic which loosely approximates the ability of a candidate production rule to best reduce a grammar's encoding. Some background theory is provided as the basis development, after which the effectiveness of the heuristic is explored empirically. A conclusion is reached, showing that a logarithmic decrease in grammar production complexity is possible, but that a strong performance boost may result in a failure to explore the search space sufficiently to produce more compact grammars overall when the modification of production rules is included. Nonetheless, it is shown to be effective in producing more compact grammars than a standard method which does not allow rule modification, and in a fraction of the time possible when using that method to explore the extended search space. The work presented in this thesis builds on existing studies, as follows: 1. New applications of standard grammar-based compressors are investigated, including the automatic identification and reversal of data errors, classification of music into similarity based groups, and division of the musical surface into analytically significant segments. 2. Development and investigation of a novel method of grammar encoding is conducted, which allows increased substring similarity to enable the production of smaller grammars, and aims to leverage this ability against existing musical and non-musical applications. 3. A novel heuristic which reduces production complexity is developed and investigated, which allows complex grammars to be constructed more quickly than is currently possible with standard methods. 4. Where possible, empirical results are obtained for all methods and applications presented in this study, and these are rigorously compared to produce an evaluation of their effectiveness in each specific case. 5. A set of considerations and recommendations for future work are provided, using experimental observations to highlight promising areas of investigation by which the ideas presented in this study may be further explored and improved. Overall, this study represents an exploration of leveraging straight-line grammars against analytical tasks, specifically given data from musical scores, and presents methods which allow the inclusion of domain knowledge to produce smaller models with strongly decreased computational complexity.