Melody recognition with learned edit distances

Amaury Habrard, José Manuel Iñesta, David Rizo, Marc Sebban2013

TL;DR

This paper tackles the challenge of accurately recognizing melodies by learning the "cost" of different musical transformations (like note changes) directly from data, rather than relying on human-defined rules. They demonstrate that probabilistic learning models significantly outperform traditional fixed-cost methods and even genetic algorithms in both accuracy and, crucially, in providing an interpretable understanding of melodic similarity.

What Problem Does This Paper Address?

In music information retrieval, a common task is to identify a melody by comparing it to a library of known tunes. This comparison relies on a similarity measure. A popular approach uses "edit distances," which quantify the effort needed to transform one sequence (like a melody represented as a string of notes) into another. Traditionally, the costs associated with basic edit operations (insertion, deletion, substitution of notes) are fixed based on intuition or prior knowledge. However, this fixed approach might not capture the nuances of how humans perceive melodic similarity, especially when dealing with variations, performance errors, or stylistic differences. The paper aims to bridge this gap by learning these edit costs automatically from data, leading to more accurate and insightful melody recognition.

Methods

The core of this paper is the application and comparison of different methods for learning edit distances, moving beyond fixed costs.

  • Classical Edit Distance: This is the baseline, using pre-defined costs for insertion, deletion, and substitution of notes.
  • Genetic Algorithm (GA) Cost Fitting: This approach uses a genetic algorithm to search for the optimal set of insertion, deletion, and substitution costs. The algorithm evolves a population of "chromosomes" (each representing a set of costs) by evaluating their performance in a melody classification task. The fitness function is based on classification accuracy.
  • Probabilistic Learning Model: This is the paper's main contribution. Instead of learning discrete costs, this method learns probabilities of edit operations. It uses a probabilistic framework where the similarity between two melodies is assessed by estimating the probability of generating one melody from another using edit operations. This is framed as learning conditional probabilities $p(Y|X)$, where $X$ is the input melody and $Y$ is the output. The paper highlights that this approach, particularly using memoryless transducers, offers a more interpretable model than the GA.

The paper applies these methods to both string and tree representations of melodies.

Datasets

The authors used a corpus of 420 monophonic melodies. These were derived from 20 well-known tunes, with each original score having 20 variations created by musicians to simulate performance errors and embellishments. This dataset was used for both training and evaluating the different learning models.

Key Insights and Ideas

  • Learned Costs Outperform Fixed Costs: The most significant finding is that automatically learning edit costs from data leads to demonstrably better melody recognition accuracy compared to using pre-defined, fixed costs.
  • Probabilistic Models Offer Interpretability: While genetic algorithms can improve accuracy, the learned cost matrices are often opaque. The probabilistic approach, however, yields cost matrices that are more interpretable, reflecting underlying melodic similarity phenomena. This is a crucial advantage for understanding why certain melodies are considered similar.
  • Understanding Melodic Variation: The learned probabilistic models can capture common melodic variations, such as semitone changes, insertions, and deletions, by assigning them lower "costs" (higher probabilities). This provides insights into how melodies are transformed while remaining recognizable.
  • String vs. Tree Representations: The paper explores both string and tree representations of melodies. While both benefit from learned edit distances, the improvement is noted to be even more significant for tree-based representations.

Key Results

  • Accuracy Improvement: Both the genetic algorithm and the probabilistic learning models significantly outperformed the classical edit distance with fixed costs. For strings, the error rates were reduced, and for trees, the improvement was even more substantial.
  • Probabilistic Model Superiority in Interpretability: The learned cost matrices from the probabilistic model were found to be more readable and understandable. For instance, the diagonal (representing self-substitution) was clearly visible, and insertions/deletions reflected common melodic changes. In contrast, the genetic algorithm's learned costs were less informative about the underlying similarity structure.
  • Specific Findings on Learned Matrices:
    • Genetic Algorithm: Showed a clear diagonal for string substitutions but lacked other discernible patterns. For trees, the diagonal was not even clearly identifiable.
  • Stochastic Algorithm: For strings, the diagonal, insertion row, and deletion column were evident, reflecting changes in note onset and duration. Values close to the diagonal (semitone changes) had higher probabilities. For trees, the learned costs showed a similar scheme, though the diagonal was less pronounced, attributed to the nature of subtree operations in the learning algorithm.

Limitations and Future Work

  • Interpretability of GA: The paper notes that the genetic algorithm approach, while improving accuracy, does not provide an interpretable model, acting more like a "blackbox."
  • Corpus Size: While the probabilistic approach is shown to be more capable of capturing knowledge even with a smaller corpus, the authors suggest that a larger corpus might lead to more precise parameter estimation for stochastic learning.
  • Future Work:
    • Polyphonic Music: Extending the approach to polyphonic music (multiple notes played simultaneously) is a key future direction, as tree representations are particularly suited for this.
  • Alternative Pitch Representations: Exploring other pitch representations like contour, high-definition contour, pitch classes, and intervals to evaluate their suitability for melody matching.

Summary updated

Abstract

In a music recognition task, the classification of a new melody is often achieved by looking for the closest piece in a set of already known prototypes. The definition of a relevant similarity measure becomes then a crucial point. So far, the edit distance approach with a-priori fixed operation costs has been one of the most used to accomplish the task. In this paper, the application of a probabilistic learning model to both string and tree edit distances is proposed and is compared to a genetic algorithm cost fitting approach. The results show that both learning models outperform fixed-costs systems, and that the probabilistic approach is able to describe consistently the underlying melodic similarity model. Key words: Edit distance learning, music similarity, genetic algorithms, probabilistic models 1
BibTeX
@misc{habrard2013melody,
  author = {Amaury Habrard and José Manuel Iñesta and David Rizo and Marc Sebban},
  title = {{Melody recognition with learned edit distances}},
  year = {2013},
}
Figure