Arc Consistency Projection: A New Generalization Relation for Graphs

Michel Liquière 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The projection problem (conceptual graph projection, homomorphism, injective morphism, θ-subsumption, OI-subsumption) is crucial to the efficiency of relational learning systems. How to manage this complexity has motivated numerous studies on learning biases, restricting the size and/or the number of hypotheses explored. The approach suggested in this paper advocates a projection operator based on the classical arc consistency algorithm used in constraint satisfaction problems. This projection method has the required properties : polynomiality, local validation, parallelization, structural interpretation. Using the arc consistency projection, we found a generalization operator between labeled graphs. Such an operator gives the structure of the classification space which is a concept lattice.
Type de document :
Communication dans un congrès
ICCS'07: International Conference on Conceptual Structures, Springer, pp.333-346, 2007, LNCS. 〈10.1007/978-3-540-73681-3_25〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00196399
Contributeur : Martine Peridier <>
Soumis le : mercredi 12 décembre 2007 - 16:31:14
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23

Identifiants

Collections

Citation

Michel Liquière. Arc Consistency Projection: A New Generalization Relation for Graphs. ICCS'07: International Conference on Conceptual Structures, Springer, pp.333-346, 2007, LNCS. 〈10.1007/978-3-540-73681-3_25〉. 〈lirmm-00196399〉

Partager

Métriques

Consultations de la notice

50