La compilation de connaissances est une famille d'approches en intelligence artificielle qui aborde l'intractabilité computationnelle du raisonnement avec des modèles propositionnels. Au lieu de répondre directement aux requêtes sur un modèle potentiellement complexe, le modèle est transformé en une phase hors ligne en une représentation compilée qui prend en charge des requêtes spécifiques en temps polynomial. Ce processus en deux étapes - compilation suivie de réponse aux requêtes - échange un effort computationnel initial contre une inférence plus rapide et plus prévisible à l'exécution.
Le défi central réside dans le choix d'une représentation compilée appropriée, car différentes représentations offrent différents compromis. Les trois propriétés principales qui caractérisent une représentation compilée sont sa compacité (avec quelle concision elle représente le modèle original), l'ensemble de requêtes qu'elle prend en charge en temps polynomial, et les transformations qui peuvent être effectuées sur elle en temps polynomial. Aucune représentation unique n'excelle dans ces trois aspects, donc les praticiens choisissent une représentation en fonction des requêtes qu'ils doivent répondre et des contraintes de taille de leur application.
Classes de représentations
Les représentations compilées se répartissent en plusieurs grandes catégories. Les classes de diagrammes incluent les arbres de décision, les diagrammes de décision binaires ordonnés (OBDD), les diagrammes de décision binaires libres (FBDD), les OBDD non déterministes, et les diagrammes de décision multi-valués (MDD). Ces structures graphiques représentent des fonctions booléennes sous forme de graphes acycliques dirigés, où chaque chemin correspond à une affectation de variables.
Les classes de formules incluent la forme normale disjonctive (DNF) et la forme normale conjonctive (CNF). Bien que la CNF soit un format d'entrée courant pour de nombreuses tâches de raisonnement, elle ne prend pas en charge toutes les requêtes efficacement, ce qui motive la compilation vers d'autres formes. Les classes de circuits incluent la forme normale de négation (NNF), la NNF décomposable (DNNF), la DNNF déterministe (d-DNNF), et les diagrammes de décision sententiels (SDD). Ces circuits imposent des contraintes structurelles qui permettent des opérations en temps polynomial pour certaines requêtes, comme la vérification de cohérence ou le comptage de modèles.
Compilateurs de connaissances
Plusieurs outils logiciels ont été développés pour effectuer automatiquement la compilation de connaissances. Le compilateur c2d prend en charge la compilation vers d-DNNF, une représentation qui permet le comptage de modèles et la vérification de cohérence en temps polynomial. Le compilateur d4 cible également d-DNNF et est connu pour son efficacité sur de grandes instances. miniC2D compile vers SDD, une représentation plus récente qui prend en charge une gamme plus large de requêtes et de transformations. KCBox prend en charge la compilation vers OBDD, OBDD[AND], et CCDD, offrant une flexibilité à travers différentes classes de diagrammes.
Ces compilateurs sont utilisés dans des applications telles que le raisonnement probabiliste, la planification, et la gestion de configuration, où une réponse répétée aux requêtes est requise. En compilant un modèle une fois, les systèmes peuvent répondre rapidement à de nombreuses requêtes, ce qui est critique dans des contextes en temps réel ou interactifs.
Compromis et critères de sélection
Le choix d'une représentation compilée dépend des exigences spécifiques de l'application. Par exemple, les OBDD sont compacts pour de nombreuses fonctions pratiques et prennent en charge le test d'équivalence en temps polynomial, mais ils peuvent exploser de manière exponentielle pour certaines fonctions. Les DNNF et d-DNNF sont plus succincts en général mais prennent en charge moins de requêtes. Les SDD offrent un juste milieu, prenant en charge à la fois le comptage de modèles et le conditionnement en temps polynomial tout en maintenant des propriétés structurelles qui facilitent la compilation.
Les transformations comptent également. Certaines applications nécessitent de modifier la représentation compilée, comme le conditionnement sur des preuves ou la conjonction avec des contraintes supplémentaires. Les représentations qui prennent en charge ces transformations en temps polynomial sont préférées dans des environnements dynamiques, même si elles sont moins compactes que des alternatives.
Relation avec l'apprentissage automatique
La compilation de connaissances est conceptuellement distincte de l'apprentissage automatique et du apprentissage profond, qui se concentrent sur l'apprentissage de motifs à partir de données plutôt que sur la transformation de modèles logiques. Cependant, les représentations compilées ont été explorées comme un moyen de rendre les modèles appris plus interprétables ou d'intégrer le raisonnement symbolique avec des approches neuronales. Par exemple, les diagrammes de décision peuvent être utilisés pour représenter les frontières de décision d'un réseau de neurones entraîné sous une forme qui prend en charge la vérification formelle.
Des travaux récents ont également examiné les connexions avec le raisonnement des grands modèles de langage, où des bases de connaissances compilées pourraient fournir des connaissances de fond structurées pour augmenter les modèles génératifs. Bien que ces efforts soient encore naissants, ils soulignent la pertinence continue de la compilation de connaissances comme outil pour combler l'IA symbolique et subsymbolique.
Directions actuelles
La recherche en compilation de connaissances continue de se concentrer sur le développement de nouvelles classes de représentations avec de meilleurs compromis, l'amélioration de l'évolutivité des compilateurs, et l'extension de la compilation à des langages logiques plus riches au-delà de la logique propositionnelle. Il y a aussi un intérêt pour l'apprentissage de représentations compilées directement à partir de données, ce qui brouillerait la ligne entre compilation et apprentissage automatique. Alors que les systèmes d'IA deviennent plus complexes, la capacité de raisonner efficacement sur des connaissances structurées reste un défi critique, et la compilation de connaissances offre un cadre principiel pour l'aborder.
Références
- Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research, 17, 229-264.
- Huang, J., & Darwiche, A. (2007). On compiling system models to faster SAT solvers. In Proceedings of the National Conference on Artificial Intelligence.
- Muise, C., McIlraith, S., Beck, J. C., & Hsu, E. (2012). Dsharp: Fast d-DNNF compilation with sharpSAT. In Canadian Conference on Artificial Intelligence.