Découverte automatique de régularités dans les séquences et application à l'analyse musicale

P.-Y. Rolland

LIP6 1998/045: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
335 pages - Juillet/July 1998 - French document.

PostScript : 2470 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Apprentissage et Acquisition de Connaissances

Titre français : Découverte automatique de régularités dans les séquences et application à l'analyse musicale
Titre anglais : Automated Discovery of Regularities in Sequences and its Application to Music Analysis

Résumé : La découverte de régularités dans les séquences (DRS) est un problème très général intervenant dans un large éventail de domaines d'application : biologie moléculaire, finance, télécommunications, analyse musicale, etc.
Nous nous intéressons plus particulièrement à la localisation et à l'extraction de patterns séquentiels -- un tel pattern correspond à un ensemble, appelé bloc, de facteurs (segments de séquences) soit identiques, soit "équipollents", c'est à dire significativement similaires. L'équipollence entre facteurs est définie a l'aide d'un modèle numérique de similitude (ou de dissimilitude) entre facteurs, qui joue un rôle centraldans la DRS.
Le premier volet du travail de thèse a été de montrer, expérimentations à l'appui, les limitations principales des approches existantes dans un domaine d'application comme la musique. Ces limitations se rapportent principalement à la représentation des séquences (et de leurs éléments), aux modèles de similitude entre facteurs employés (distance de Hamming ou distance d'édition a coûts constants par exemple), et aux algorithmes combinatoires de DRS eux-mêmes.
Pour pallier ces limitations, nous proposons : (1) l'insertion, au sein du processus de DRS, d'une phase d'enrichissement (ou de changement) de la représentation, partiellement ou totalement automatique. A partir de connaissances du domaine, on adjoint aux descriptions de base des séquences et de leurs éléments une hiérarchie éventuellement redondante de descriptions traduisant des propriétés supplémentaires, structurelles, locales ou globales ; (2) un nouveau modèle général de similitude entre séquences ou facteurs, le modèle d'édition valué multi-descriptions (MEVM). Ce modèle, généralisant la notion de distance d'édition, peut intégrer simultanément, de façon pondérée, un nombre arbitraire de descriptions issues en particulier de la phase d'enrichissement de la représentation ; et (3) un nouvel algorithme combinatoire d'extraction de patterns, appelé FlExPat, utilisant notre modèle de similitude. FlExPat comprend deux phases algorithmiques : la première phase, dite "d'appariement de facteurs", permet d'obtenir, a partir d'un ensemble (corpus) de séquences un graphe, appelé graphe de similitude, dont chaque sommet représente un facteur et chaque arête, un lien d'équipollence entre deux facteurs. La seconde, dite "phase de catégorisation", permet d'extraire des patterns à partir de ce graphe.
Notre logiciel Imprology implémente le modèle d'édition valué multi-descriptions et FlExPat. Imprology, implémenté en Smalltalk-80, intègre des fonctionnalités d'enrichissement automatique de la représentation des séquences et de leurs éléments. Les résultats expérimentaux obtenus sur des séquences musicales (mélodies), en particulier sur un corpus constitué d'environ 150 transcriptions de jazz improvisé, illustrent très clairement la validité de nos concepts et algorithmes. Ceux-ci sont généraux, et applicables à d'autres domaines que la musique.

Abstract : 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.

Mots-clés : Intelligence artificielle, Extraction de connaissances à partir des données, Fouille de données, Analyse de séquences, Programmation dynamique, Représentation de connaissances, Musique, Jazz improvisé, Smalltalk-80, Reconnaissance des formes

Key-words : Artificial Intelligence, Knowledge Discovery in Databases, Data Mining, Sequence Analysis, Dynamic Programming, Knowledge Representation, Music, Improvised Jazz, Smalltalk-80, Shape Recognition

Publications internes LIP6 1998 / LIP6 research reports 1998

Responsable Éditorial / Editor
webmaster@lip6.fr