SEDiL: Software for Edit Distance Learning

Laurent Boyer, Yann Esposito, Amaury Habrard, José Oncina, Marc Sebban

Introduction

In machine learning and computational linguistics, measuring the similarity between structured objects—such as genomic sequences, musical scores, or tree-like hierarchies—is fundamental. This is typically achieved through Edit Distance (ED), which calculates the minimum cost of operations (insertion, deletion, and substitution) required to transform one object into another.

Traditionally, these edit costs are assigned fixed values (e.g., a cost of 1 for any change). However, this "one-size-fits-all" approach fails to capture domain-specific nuances. For instance, in a spell-checker, substituting 'a' for 's' is more probable than 'a' for 'z' due to keyboard proximity. In molecular biology, specific DNA mutations occur with varying frequencies. Manually tuning these costs for complex datasets is impractical. SEDiL (Software for Edit Distance Learning) addresses this by providing an open-source Java platform that automates the learning of optimal, probabilistic parameters for string and tree edit distances.

Methodological Framework

SEDiL serves as a unified toolbox for several state-of-the-art learning algorithms, primarily utilizing adaptations of the Expectation-Maximization (EM) algorithm. The software allows researchers to move from heuristic cost-setting to a statistically grounded model where distance is defined as $d_s(X,Y) = -\log p(X,Y)$.

The platform supports two primary modeling approaches:

  1. Memoryless State Machines: These learn a 2D matrix of probabilities where the cost of an operation depends solely on the characters involved (e.g., the probability of $a \to b$).
  2. Non-memoryless State Machines: These account for context, using 3D matrices to model how a symbol change might be influenced by its position or surrounding sequence.
The SEDiL learning interface displaying joint and conditional probability matrices derived from sequence data.

One of SEDiL's unique strengths is its ability to handle both strings and trees. While trees are significantly more complex to process, SEDiL implements stochastic tree edit distances that manage deletions and insertions on both subtrees and individual nodes. Users can choose between learning a joint distribution (modeling the likelihood of a pair's existence) or a conditional distribution (modeling the likelihood of $Y$ given $X$), offering flexibility for either generative modeling or discriminative classification.

Practical Applications and Datasets

Rather than focusing on a single benchmark, SEDiL has been validated across diverse real-world domains:

  • Molecular Biology: Used in the ANR BINGO Project to identify regularities in promoter sequences.
  • Music Recognition: Employed by the University of Alicante for structural music analysis.
  • Handwriting Recognition: Utilized by the company A2IA to model graphical distortions in handwritten characters, demonstrating the software's industrial viability.
  • Synthetic Data: The tool includes visualization features for simple alphabets to help researchers understand how probability matrices evolve during the learning process.

Key Results and Evaluation

SEDiL successfully integrates five distinct learning algorithms into a single, accessible Java-based GUI. A critical feature of the software is its integrated k-Nearest Neighbor (k-NN) classifier. This allows users to immediately validate their learned distance metrics by testing classification accuracy against standard fixed-cost edit distances.

The classification interface showing a k-Nearest Neighbor setup and performance metrics using learned distances.

By providing a graphical interface to visualize transformations and results, SEDiL lowers the barrier to entry for researchers who need sophisticated distance metrics but lack the resources to implement complex EM-based algorithms from scratch. The software's adoption by industrial partners like A2IA highlights its effectiveness in handling noisy, real-world graphical data.

Future Directions

While SEDiL represents a significant step forward, the authors have identified several areas for future development. Currently, while string models can be context-aware (non-memoryless), the tree models remain memoryless. Expanding context-aware capabilities to tree structures is a primary goal. Additionally, the team plans to incorporate Conditional Random Fields (CRFs) and constrained state machines to allow users to inject background knowledge and specific rules into the learning process, further refining the accuracy of the learned distances.

Summary updated

Abstract

In this paper, we present SEDiL, a Software for Edit Distance Learning. SEDiL is an innovative prototype implementation grouping together most of the state of the art methods [1{4] that aim to automatically learn the parameters of string and tree edit distances. This work was funded by the French ANR Marmota project, the Pascal Network of
BibTeX
@inproceedings{boyer2008sedil,
  author = {Laurent Boyer and Yann Esposito and Amaury Habrard and José Oncina and Marc Sebban},
  title = {{SEDiL: Software for Edit Distance Learning}},
  booktitle = {ECML/PKDD},
  year = {2008},
  doi = {10.1007/978-3-540-87481-2\_45},
}
Figure