| Titre : | Compilation et Apprentissage dans les Réseaux de Contraintes | | Type de document : | texte imprimé | | Auteurs : | H. CROS, Auteur | | Année de publication : | 2003 | | Langues : | Français (fre) | | Tags : | RESEAUX DE CONTRAINTES COMPILATION DE CONNAISSANCES APPRENTISSAGE INSTANCE BASED LEARNING CASE BASED LEARNING RESEAUX DE CONTRAINTES COMPILATION DE CONNAISSANCES COMPILATION APPROXIMATIVE APPRENTISSAGE INSTANCE BASED LEARNING CASE BASED LEARNING CONSTRAINT NETWORKS KNOWLEDGE COMPILATION APPROXIMATION LEARNING INSTANCE BASED LEARNING CASE BASED LEARNING | | Index. décimale : | THE Thèses de doctorat | | Résumé : | Cette thèse porte sur la compilation des réseaux de contraintes. Tout d'abord nous définissons et rangeons dans les classes de complexité de compilation les requêtes qui peuvent être posées sur un réseau de contraintes. Ensuite, puisque les requêtes intéressantes ne s'avèrent pas compilables, nous examinons deux voies détournées pour traiter ces requêtes : la compilation approximative, et l'apprentissage. La compilation approximative consiste à altérer le réseau de contraintes de façon à ce que sa résolution devienne polynomiale. Nous examinons donc deux approches complémentaires de l'altération du réseau : l'altération de sa structure, puis celle de sa sémantique. Ces deux approches s'avèrent complémentaires tant dans la qualité que dans le dénombrement de leurs bornes, ce qui laisse présager qu'une compilation hybride serait probablement plus efficace. Cependant, bien que pour certaines des bornes nous garantissons l'optimalité, l'analyse des bornes laisse apparaître un encadrement trop grossier du réseau de contraintes pour qu'il soit possible d'envisager une application de cette technique dans un cas réel. Nous nous sommes alors orientés vers une approche totalement différente qui, elle, s'appuie sur l'apprentissage. En réalisant un système mixte, qui à la fois tire partie de la souplesse de l'apprentissage et en même temps de la force reconnue des algorithmes de résolution de réseaux de contraintes, nous parvenons à gagner du temps sur le traitement ``on-line'' des requêtes. Ce gain de temps montre bien l'utilité de la phase ``off-line'', phase durant laquelle le système a pu apprendre des solutions et contre-solutions.
In this study, we define and classify queries that can be asked to a constraint network. Since most interesting queries are not compilable, we investigate two paradigms to handle these queries: approximation and learning. In the setting of approximate compilation, we focus on two techniques: the structural approach and the semantic approach. These techniques are shown to be complementary in the quality and the number of solutions; this analysis opens the door to the notion of hybrid compilation. In the context of learning-based compilation, we have designed and implemented a system that combines the flexibility of learning with the power of constraint algorithms. Based on experimental results, we notably show that our system is particularly efficient for tackling queries that are hard to handle directly by constraint solvers. This demonstrates the utility of the off-line step in compilation, used here to learn solutions and counter-solutions. | | Directeur(s) de thèse : | QUINQUETON J. | | Co-directeur(s) de thèse : | KORICHE F. | | Rapporteur(s) : | CHOURAQUI E.;MEPHU NGUIFO E. | | Examinateur(s) : | BESSIERE C.;CERRI S. | | Invité(s) : | SALLANTIN J. | | Date de soutenance : | 18/12/2003 |
Compilation et Apprentissage dans les Réseaux de Contraintes [texte imprimé] / H. CROS, Auteur . - 2003. Langues : Français ( fre) | Tags : | RESEAUX DE CONTRAINTES COMPILATION DE CONNAISSANCES APPRENTISSAGE INSTANCE BASED LEARNING CASE BASED LEARNING RESEAUX DE CONTRAINTES COMPILATION DE CONNAISSANCES COMPILATION APPROXIMATIVE APPRENTISSAGE INSTANCE BASED LEARNING CASE BASED LEARNING CONSTRAINT NETWORKS KNOWLEDGE COMPILATION APPROXIMATION LEARNING INSTANCE BASED LEARNING CASE BASED LEARNING | | Index. décimale : | THE Thèses de doctorat | | Résumé : | Cette thèse porte sur la compilation des réseaux de contraintes. Tout d'abord nous définissons et rangeons dans les classes de complexité de compilation les requêtes qui peuvent être posées sur un réseau de contraintes. Ensuite, puisque les requêtes intéressantes ne s'avèrent pas compilables, nous examinons deux voies détournées pour traiter ces requêtes : la compilation approximative, et l'apprentissage. La compilation approximative consiste à altérer le réseau de contraintes de façon à ce que sa résolution devienne polynomiale. Nous examinons donc deux approches complémentaires de l'altération du réseau : l'altération de sa structure, puis celle de sa sémantique. Ces deux approches s'avèrent complémentaires tant dans la qualité que dans le dénombrement de leurs bornes, ce qui laisse présager qu'une compilation hybride serait probablement plus efficace. Cependant, bien que pour certaines des bornes nous garantissons l'optimalité, l'analyse des bornes laisse apparaître un encadrement trop grossier du réseau de contraintes pour qu'il soit possible d'envisager une application de cette technique dans un cas réel. Nous nous sommes alors orientés vers une approche totalement différente qui, elle, s'appuie sur l'apprentissage. En réalisant un système mixte, qui à la fois tire partie de la souplesse de l'apprentissage et en même temps de la force reconnue des algorithmes de résolution de réseaux de contraintes, nous parvenons à gagner du temps sur le traitement ``on-line'' des requêtes. Ce gain de temps montre bien l'utilité de la phase ``off-line'', phase durant laquelle le système a pu apprendre des solutions et contre-solutions.
In this study, we define and classify queries that can be asked to a constraint network. Since most interesting queries are not compilable, we investigate two paradigms to handle these queries: approximation and learning. In the setting of approximate compilation, we focus on two techniques: the structural approach and the semantic approach. These techniques are shown to be complementary in the quality and the number of solutions; this analysis opens the door to the notion of hybrid compilation. In the context of learning-based compilation, we have designed and implemented a system that combines the flexibility of learning with the power of constraint algorithms. Based on experimental results, we notably show that our system is particularly efficient for tackling queries that are hard to handle directly by constraint solvers. This demonstrates the utility of the off-line step in compilation, used here to learn solutions and counter-solutions. | | Directeur(s) de thèse : | QUINQUETON J. | | Co-directeur(s) de thèse : | KORICHE F. | | Rapporteur(s) : | CHOURAQUI E.;MEPHU NGUIFO E. | | Examinateur(s) : | BESSIERE C.;CERRI S. | | Invité(s) : | SALLANTIN J. | | Date de soutenance : | 18/12/2003 |
|
Affiner la recherche Interroger des sources externesCompilation et Apprentissage dans les Réseaux de Contraintes / H. CROS
