LIP6 1998/045

  • Thesis
    Découverte automatique de régularités dans les séquences et application à l'analyse musicale
  • P.-Y. Rolland
  • 335 pages - 07/20/1998- document en - - 2,530 Ko
  • Contact : Pierre-Yves.Rolland (at)
  • Ancien Thème : APA
  • Discovery of regularities in sequences (DRS) is a very general problem appearing in a broad range of application domains, including molecular biology, finance, telecommunications, and music analysis. We focus on discovering sequential patterns, defined by sets ('blocks') of identical or 'equipollent' sequence segments, where equipollent means significantly similar. Equipollence criteria are based on models of similarity between (pairs of) sequence segments. The first part of our Ph.D. work has been to evidence, basing on experimental results, main limitations of existing approaches in such an application domain as music. These limitations chiefly pertain to the representation of sequences and of their elements, to the segment pair similarity models used (e.g. Hamming distance) and to the combinatorial DRS algorithms themselves.
    To overcome these limitations, we propose: (1) inserting into the DRS process a representation enrichment (or change) phase, which may be partially or totally automated. From domain knowledge, basic descriptions of sequences and of their elements are supplemented with a possibly redundant hierarchy of descriptions corresponding to additional properties - structural, local and global; (2) a new general sequence [segment] pair similarity model, the multi-description valued edit model (MVEM), which can integrate, using a weighted paradigm, an arbitrary number of descriptions; and (3) a new combinatorial DRS algorithm named FlExPat ('FlExible Extraction of Patterns') which uses the MVEM.
    Our Imprology software system implements the MVEM and FlExPat. Experimental results obtained with Imprology on musical sequences (corpuses of improvised jazz solo transcriptions) evidence the validity of our concepts and algorithms with much clarity. These concepts and algorithms are general and thus applicable to domains other than music.
  • Keywords : Artificial Intelligence, Knowledge Discovery in Databases, Data Mining, Sequence Analysis, Dynamic Programming, Knowledge Representation, Music, Improvised Jazz, Smalltalk-80, Shape Recognition
  • Publisher : Valerie.Mangin (at)