Groupe de Travail Graphes Conceptuels
Thème algorithmique et apprentissage
La liste des personnes impliquées dans ce thème
est la suivante :
Les problèmes algorithmiques traités dans ce thème
sont tous liés à la relation de
généralisation, celle-ci étant la notion
fondamentale pour tout raisonnement basé sur les graphes
conceptuels. Cette relation se calcule par l'opération de
projection qui, en termes de théorie des graphes, est un
morphisme de graphes étiquetés. Un graphe G est ainsi dit plus général qu'un graphe H (H <= G) s'il existe une projection de G dans H.
Ce thème a trois aspects:
1. Calcul de morphisme/projection
La notion de morphisme de graphes étiquetés permet
d'unifier, à un niveau algorithmique, différents
formalismes, dont les graphes conceptuels simples
et les problèmes de satisfaction de contraintes. En effet, des
travaux récents ont montré que la résolution d'un
problème de satisfaction de contraintes correspondait exactement
au calcul d'un morphisme de graphes étiquetés ou d'une
projection [Chein mugnier 95]. Ces résultats ouvrent
la voie à des recherches sur des transferts de cas polynomiaux
entre les deux problèmes, l'utilisation des nombreux travaux
algorithmiques sur les CSP pour le calcul de morphismes, ainsi que
l'exploitation de la transformation de CSP vers
morphisme, qui rend explicite la "microstructure" du CSP.
2. Structure de la relation de généralisation.
Des premiers résultats ont été obtenus sur la
structure de la relation de généralisation. cf. [Champesme 95] (dans le cadre de l'apprentissage) et [Chein Mugnier 95].
Les deux points précédents s'intéressent également à :
- La notion de projection injective (en termes de morphisme, le
problème de la comparaison de deux graphes devient le
problème "isomorphisme de sous-graphe"),
- Des classes de graphes particulières, comme les "graphes localement injectifs" [Brissac Liquiere 95], ou les "graphes conceptuels C-triés" [Cogis Guinaldo 95],
- Des objets de structure plus complexe, comme les graphes "imbriqués" [Mugnier Chein 95] ou les hypergraphes [Brissac Liquière 95].
3. Problèmes algorithmiques spécifiques à l'apprentissage.
Les problèmes algorithmiques rencontrés en
apprentissage sont fortement liés aux points
précédents, mais présentent des difficultés
spécifiques.
Typiquement, on recherche une hypothèse
généralisant un ensemble d'exemples d'un concept
(exemples et hypothèses sont ici décrits sous forme de
graphes conceptuels), cette hypothèse devant constituer une
"bonne" description du concept. Il s'agit alors de limiter la
complexité de la recherche et de définir des mesures de
la qualité d'une hypothèse. La recherche s'effectue
par parcours de l'ensemble des graphes, structuré par la
relation de généralisation. Dans ce cadre, nous nous
intéressons :
- aux opérations permettant le passage d'une
hypothèse à une autre (opérateurs de
spécialisation/généralisation),
- et aux critères permettant de réduire le nombre
d'hypothèses évaluées (critères de
sélection), aspects tous deux liés aux
propriétés structurelles de l'espace de recherche.
En ce qui concerne la mesure de la qualité d'une
hypothèse ou d'un ensemble d'hypothèses, nous
étudions des critères basés sur des notions de
compression de la
description des exemples. Ceci nous amène à
définir des objets plus complexes que les graphes simples
(hypergraphes évoqués au point 2).
Bibliographie
- Marc Champesme (1995), "Using empirical subsumption to reduce
the search space in learning", International Conference on Conceptual
Structures, ICCS'95, Santa-Cruz, Californie, USA, Aout 1995. PostScript
(100k) ici).