LIP6 1998/045

  • Thèse
    Découverte automatique de régularités dans les séquences et application à l'analyse musicale
  • P.-Y. Rolland
  • 335 pages - 20/07/1998- document en - http://www.lip6.fr/lip6/reports/1998/lip6.1998.045.ps.gz - 2,530 Ko
  • Contact : Pierre-Yves.Rolland (at) nulllip6.fr
  • Ancien Thème : APA
  • 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.
  • 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
  • Directeur de la publication : Valerie.Mangin (at) nulllip6.fr
 Mentions légales
Carte du site |