Mical

Mical est une bibliothèque d'inférence grammaticale régulière implementée en C++. Elle s'appuie sur Vaucanson pour la manipulation des automates.

Mical propose aussi bien les algorithmes classiques d'inférence avec échantillon négatif que sans échantillon négatif. Toutefois c'est surtout les services/primitives proposé(e)s pour l'implémentation des algorithmes d'inférence avec échantilon négatif qui constitue le cœur de Mical. En effet Mical propose un pattern spécifique pour définir un cadre de travail au sein duquel l'utilisateur pourra pratiquer l'inférence de son choix.

News

• 19/07/2003 : Some benchmarks ... available here
• 10/07/2003 : Mical version 0.1 realeased

Principaux services proposés dans Mical 0.1

Echantillons (1)

• Type de données :
  • échantillon simple (positif ou négatif)
  • présentation (échantillons positif et négatif):
    • à données fixées
    • pour inférence incrémentale
    • pour inférence semi-incrémentale
• Services :
  • noyau d'un langage (pour un automate canonique donné)
  • ensemble des préfixes courts d'un langage (pour un automate canonique donné)
  • fournir un échantillon caractéristique (pour un automate canonique donné)
  • fournir un échantillon structurellement complet (pour un automate donné)
  • vérifier si un échantillon est structurellement complet (pour un automate donné)
• Divers:
  • Chargement à partir d'un fichier d'un(e) échantillon/présentation

Services 'internes' (1)

• fusion d'états
• compatibilité d'un automate vis-à-vis d'une présentation (de son échantillon négatif)
• création du MCA à partir d'une présentation
• création du PTA à partir d'une présentation
• conversion MCA -> PTA
• renumerotation (des états d'un automate):
  • selon l'ordre standard
  • selon l'ordre de fréquence de passage au-travers des états
• primitives sur les automates (find_suffix, quotient, ...)

Cadres de travail

• Espace de recherche proposés:
  • treillis ayant pour élément nul le MCA
  • treillis ayant pour élément nul le PTA
  • demi-treillis supérieur des automates déterministes (ayant pour élément nul le PTA)

• Type d'inférences proposées:
  • à données fixées
  • incrémentale (à terminer dans Mical 0.2)
  • semi-incrémentale (à terminer dans Mical 0.2)

• Primitives proposées au sein du cadre de travail (2):
  • fusion
  • fission
  • est un élément de l'ensemble frontière
  • est l'élément universel (du treillis)
  • est l'élément nul (du treillis)
  • est (toujours / encore) un élément du treillis
  • génération d'un vrai automate (manipulable ie pas seulement en mode lecture) à partir de l'élément du treillis considéré (3)
  • ... (cf le code)

• Implémentation sous-jacente: (1)
  • partitions
  • services sur les partitions (distance, ...)
  • 'Vue' d'un automate à travers une partition

Algorithmes proposés :

• K-TSSI
• K-RI
• MGGI
• parcours du treillis:
  • évaluation lazy de l'ensemble frontière d'un espace de recherche donné (à terminer dans Mical 0.2 avec le système d'historique)
  • RIG (sans redondance des éléments énumérés)
• fusion pour déterminisation
• RPNI (version 'classique' à données fixées)

(1) : l'utilisateur n'a pas à les utiliser directement, leur utilisation est implicite à travers le cadre de travail choisi

(2) : le choix de la bonne implémentations de ces primitives (qui varient selon le choix du cadre de travail) est automatiquement géré par Mical

(3) : les éléments du treillis (hypothèses) considérés sont en fait proche du cadre théorique : on manipule des partitions (rapidité des opérations élémentaires (fusion/fission), économie de mémoire) et on 'regarde' l'élément nul du treillis à travers cette partition pour considérer notre hypothèse comme un automate.

Services attendus pour Mical 0.2

• rajouter du sucre
• terminer support général pour l'inférence incrémental / semi-incrémental
• rajouter du sucre dans la manipulation du Framework (cadre de travail):
  • système d'historique (des déplacements dans le treillis)
  • nouvelle implémentation de partitions plus légère (bitsets)
  • manipulation de la Vue plus aisée
• RPNI avec suppression de finales
• RPNI version incrémentale
• algorithme EDSM
• algorithme Blue-fringe
• test-suite (beaucoup) plus conséquente

Téléchargements

• Sources :
  • mical-0.1.0.tar.gz : Mical 0.1
  • Coming soon : Mical 0.2

• Documentation :
  • Rapport interne : Mical, une bibliothèque d'inférence grammaticale régulière (fin juillet 2003)
  • Séminaire du 04/06/2003 : slides

Contacts

• Maxime Rey : max@lrde.epita.fr

-- MaximeRey^? - 09 Jul 2003
to top