Chap 1 Schémas de Représentation de Connaissances [PDF]

Zitiervorschau

Modèles de connaissances incertaines

Chapitre I : Schémas de représentation de connaissances

Chapitre I Schémas de représentation de connaissances

1. Introduction La science en général est un ensemble de méthodes systématiques pour acquérir des connaissances. Il existe néanmoins de nombreuses formes de connaissances qui, sans être scientifiques, n'en sont pas moins parfaitement adaptées à leur objet : le savoir-faire (l'artisanat, savoir nager, etc.), le savoir technique, la connaissance des langues, la connaissance des traditions, légendes, coutumes ou idées d'une culture particulière, la connaissance qu'ont les individus de leur propre histoire (connaître son propre nom, ses parents, son passé), ou encore les connaissances communes d'une société donnée ou de l'humanité (savoir à quoi sert un marteau, savoir que l'eau éteint le feu, etc). 2. Types de connaissances et techniques de représentation de connaissances 2.1. Types de connaissances Qu’il s’agisse du domaine purement cognitif, du domaine affectif, social, sensoriel ou moteur, la psychologie cognitive considère qu’il y a fondamentalement trois catégories de connaissances : les connaissances déclaratives, procédurales et conditionnelles. a. Connaissances déclaratives Les connaissances déclaratives correspondent essentiellement à des connaissances théoriques, aux connaissances qui, à une certaine période, furent reconnues comme des savoirs. Il s’agit, selon Gagné (1985), de la connaissance de faits, de règles, de lois, de principes. Par exemple, la connaissance des capitales de tous ou de quelques pays constitue une connaissance déclarative. Il est à noter que les connaissances déclaratives sont fondamentalement des connaissances plutôt statiques que dynamiques et qu’elles doivent, pour permettre l’action, être traduites en procédures et en conditions, en connaissances procédurales ou conditionnelles. b. Connaissances procédurales Les connaissances procédurales correspondent au comment de l’action, aux étapes pour réaliser une action, à la procédure permettant la réalisation d’une action. Fréquemment, dans les écrits pédagogiques, ces connaissances sont décrites comme des savoir-faire. Les connaissances procédurales se différencient des connaissances déclaratives car il s’agit de connaissances de l’action, de connaissances dynamiques. Ces connaissances sont exclusivement des séquences d’actions. c. Connaissances conditionnelles Les connaissances conditionnelles se rapportent aux conditions de l’action. Elles correspondent souvent à des classifications, des catégorisations. Sans elles, les connaissances déclaratives restent des connaissances essentiellement « inertes », et les connaissances procédurales ne peuvent être activées ou le sont à mauvais escient. Elles concernent le quand et le pourquoi. A quel moment et dans quel contexte est-il approprié d’utiliser telle ou telle stratégie, telle ou telle démarche, d’engager telle ou telle action ? Pourquoi estce adéquat d’employer cette stratégie, cette démarche, de réaliser cette action ? I. SOUICI @ 2015 / 2016

1

Modèles de connaissances incertaines

Chapitre I : Schémas de représentation de connaissances

d. Connaissances heuristiques Un très grand nombre de méthodes existent en recherche opérationnelle (RO) et en intelligence artificielle (IA) pour résoudre différentes sortes de problèmes tels que les problèmes d'optimisation combinatoire. Ces méthodes peuvent être classées sommairement en deux grandes catégories : les méthodes exactes (complètes) qui garantissent la complétude de la résolution et les méthodes approchées (incomplètes) qui perdent la complétude pour gagner en efficacité. Le principe essentiel d'une méthode exacte consiste généralement à énumérer, souvent de manière implicite, l'ensemble des solutions de l'espace de recherche. Les méthodes exactes ont permis de trouver des solutions optimales pour des problèmes de taille raisonnable. Malgré les progrès réalisés (notamment en matière de la programmation linéaire en nombres entiers), et comme le temps de calcul nécessaire pour trouver une solution risque d'augmenter exponentiellement avec la taille du problème, les méthodes exactes rencontrent généralement des difficultés face aux applications de taille importante. Les méthodes approchées constituent une alternative très intéressante pour traiter les problèmes d'optimisation de grande taille si l'optimalité n'est pas primordiale. Depuis une dizaine d'années, des progrès importants ont été réalisés avec l’apparition d’une nouvelle génération de méthodes approchées puissantes et générales, souvent appelées métaheuristiques. Une métaheuristique est constituée d’un ensemble de concepts fondamentaux (par exemple, la liste tabou et les mécanismes d’intensification et de diversification pour la métaheuristique tabou), qui permettent d'aider à la conception de méthodes heuristiques pour un problème d'optimisation. Ainsi les métaheuristiques sont adaptables et applicables à une large classe de problèmes. Avec l'émergence de stratégies des solutions plus générales, y compris les métaheuristiques telles que la recherche taboue, algorithmes génétiques, recuit simulé, le principal défi est devenu l'adaptation des métaheuristiques à un problème particulier ou une catégorie de problème. Cela nécessite généralement beaucoup moins de travail que de développer une heuristique spécialisée pour une application spécifique, ce qui rend les métaheuristiques un choix attrayant pour la mise en œuvre dans les logiciels à usage général. En outre, une bonne mise en œuvre de métaheuristique est susceptible de fournir des solutions quasi optimales en temps de calcul raisonnables. Ainsi, une métaheuristique est définie de manière similaire à une heuristique (qui est une méthode conçue pour un problème d'optimisation donné et qui produit une solution non nécessairement optimale lorsqu'on lui fournit une instance de ce problème), mais à un niveau d'abstraction plus élevé. Pour résumer, la définition suivante semble être la plus appropriée : « Une métaheuristique est un processus maître itératif qui guide et modifie les opérations d'heuristiques subordonnées pour produire efficacement des solutions de haute qualité. Il peut manipuler une solution unique complète (ou incomplète) ou un ensemble de solutions à chaque itération. Les heuristiques subordonnées peuvent être des procédures de niveau élevé (ou faible), ou une recherche locale simple, ou tout simplement une méthode de construction. La famille de métaheuristiques comprend, mais n'est pas limitée à, des procédures de mémoire d'adaptation, de recherche tabou, des systèmes de fourmis, de recherche à voisinage variable, des méthodes évolutionnaires, des algorithmes génétiques, des réseaux neuronaux, de recuit simulé, et leurs hybrides ".

I. SOUICI @ 2015 / 2016

2

Modèles de connaissances incertaines

Chapitre I : Schémas de représentation de connaissances

2.2. Techniques de représentation de connaissances La représentation des connaissances est l’un des traitements qui peuvent être appliqués sur les connaissances. Nous pouvons citer, entre autres, l'acquisition des connaissances, la mise en oeuvre des raisonnements sur ces connaissances, le contrôle des raisonnements, l'explication des raisonnements, la révision de connaissances, etc. Le problème de la représentation des connaissances consiste à trouver une correspondance entre un monde extérieur et un système symbolique qui doit être effectuées selon des modèles aussi généraux que possible, aussi indépendants des traitements que possible et suffisamment sémantiques pour que l'acquisition des connaissances soit aisée. En ce qui suit, nous présenterons deux modes de représentation à savoir la représentation graphique et la représentation structurée. a. Représentation graphique Ce sont des modèles généralement probabilistes pour la représentation des connaissances, fondés sur une description graphique des variables aléatoires. Idée : prendre en compte les dépendances et indépendances conditionnelles entre les variables Deux grandes classes s’inscrivent sous cette catégorie : Les Réseaux Bayésiens : C’est une représentation asymétrique des dépendances qui modélise bien les relations causales (diagnostic), Les Champs de Markov : C’est une représentation symétrique des dépendances souvent utilisées pour modéliser les dépendances spatiales (analyse d’image). Ces modèles permettent de capturer des connaissances incertaines sur un système au travers d'une représentation compacte d'une distribution de probabilités. Ils sont largement utilisés pour la représentation et le raisonnement dans l'incertain en analyse d'image ou en bioinformatique par exemple. Il est essentiel dans ces modèles de pouvoir exploiter la connaissance capturée dans le modèle graphique en répondant à des requêtes générales (quelle est la probabilité qu'un événement se réalise, quel est le modèle qui représente le mieux mes observations...). Tous ces problèmes d'inférence se ramènent à un même type de problème, souvent trop lourd pour être résolu de façon exacte. b. Représentation structurée Etant données que les connaissances que les ordinateurs manipulent habituellement sont d'ordre numérique, alors, les connaissances symboliques (i.e. qui utilisent des symboles) sont stockées dans des fichiers texte. Par exemple, la phrase " Mohamed est allé à Alger " peut être représentée comme une simple chaîne de caractères ou d'une manière plus structurée. Chaîne de caractères : Le résultat de cette représentation sera stocké dans des fichiers de texte. Un problème se présente lorsqu'on cherche des informations pour répondre à une question, comme par exemple : "Qui est allé à Alger ?". Il est difficile de répondre à cette question parce que la représentation retenue n'intègre pas des informations sur l'action "aller" ni aucune compréhension de la chaîne de caractères. Représentation plus structurée : Cette représentation inclue des éléments de signification de la phrase.

I. SOUICI @ 2015 / 2016

3

Modèles de connaissances incertaines

Chapitre I : Schémas de représentation de connaissances

Exemple : ACTION : aller AGENT : Mohamed SOURCE : ? DESTINATION : Alger TEMPS : passé MOYEN : ? On remarque que cette représentation est beaucoup plus "appropriée" que la précédente pour répondre à des questions sur les faits enregistrés. De même qu'il n'y a pas de langage universel de programmation, il n'existe pas de formalisme "idéal" pour représenter les connaissances. On dénombre ainsi dans la littérature plusieurs formalismes de représentation des connaissances : les frames : mis en évidence par les chercheurs en psychologie dans le cadre de la perception et la vision des objets. Donc, un frame est un assemblage des objets pour décrire une scène ; les scripts : Un assemblage des objets pour décrire une séquence des événements ; les réseaux sémantiques : utilisés par les linguistes pour représenter la sémantique des phrases ... Le principe de base de ce formalisme est la distinction explicite entre les connaissances déclaratives et les connaissances procédurales. Dans la programmation classique (programmation procédurale, de type Pascal), ces deux catégories de connaissances sont "mélangées" entre elles. Démonstration : Nous allons illustrer cette différence entre les deux catégories de connaissances à travers la modélisation du domaine médical. Les connaissances sur les maladies peuvent être représentées selon deux approches : Approche classique : on définit des procédures de type : Procédure maladieA début vérifier symptôme1 ... vérifier symptômem fin. où le principe de modélisation consiste, donc, à intégrer au sein de la même procédure, les connaissances sur la maladie (i.e la "maladieA" concerne les symptômes1, etc.) et la manière de diagnostiquer les maladies (vérifier tel but avant tel autre, etc). Nouvelle approche (approche déclarative) : Le principe de base consiste à séparer les connaissances sur la maladieA des connaissances sur la manière d'apporter un diagnostic :

I. SOUICI @ 2015 / 2016

4

Modèles de connaissances incertaines

Chapitre I : Schémas de représentation de connaissances

- Etape 1 : définir les connaissances du domaine d'application (informations descriptives) : C1 : Si symptôme1 & .... & symptômem Alors maladieA ... Cn : ..... - Etape 2 : définir les procédures d'exploitation de ces connaissances descriptives : Pour "vérifier" un but X faire début "chercher l'ensemble" des Ci tel que symptômei1 & ... symptômeim -> X "choisir" un Cj approprié "vérifier" les nouveaux buts (symptômejk) de Cj fin Les avantages immédiats d'un tel style de programmation, basé sur les spécifications ("quoi") plutôt que sur la manière de trouver la solution ("comment"), sont : - les mises à jour des connaissances sans remise en cause de la structure globale du système : on peut ajouter des informations sur des maladies ou modifier celles qui existent sans pour autant modifier les procédures d'interprétation qui sont tout à fait générales (indépendantes du domaine) - la possibilité d'offrir des explications : la caractéristique fondamentale de ces "nouveaux systèmes" est la possibilité de proposer des explications de leurs raisonnements. Dans l'approche classique, l'explication d'un résultat d'exécution de procédures est quasi impossible (peut-être comme un enchaînement de commentaires associés aux procédures!). Dans cette nouvelle approche, les procédures d'interprétation utilisent les connaissances du domaine d'application pour produire une trace. Cette dernière est utilisée pour la production des explications en utilisant des techniques de filtrage. Donc, pour représenter ces connaissances du domaine, il est nécessaire d'avoir des langages plus "évolués" que Fortran ou Pascal, qui ne permettent pas d'exprimer des concepts de niveaux relativement élevés (but, sous-buts). La représentation des connaissances est actuellement un sujet de recherche pluridisciplinaire qui touche les domaines suivants: - les sciences cognitives - la psychologie - la linguistique - les mathématiques - l'informatique: bases de données, systèmes experts, graphes conceptuels, programmation logique, intelligence artificielle en général,... Trois principaux types d'approche pour la représentation de connaissances sont actuellement utilisés: l'approche logique : dont le principe de base est d'utiliser la logique mathématique comme outil de la représentation des connaissances l'approche sémantique : utilisée à l'origine par les linguistes pour représenter la sémantique des phrases une approche hybride entre la sémantique et la logique : avec par exemple la notion de "frame" (schéma).

I. SOUICI @ 2015 / 2016

5

Modèles de connaissances incertaines

Chapitre I : Schémas de représentation de connaissances

3. Représentation en logique Le principe consiste à utiliser la logique mathématique comme outil pour la représentation des connaissances. Les chefs de file de cette approche sont les concepteurs et les utilisateurs de PROLOG. Les connaissances du domaine sont construites à partir des prédicats de base assemblés en clauses ou en règles. 3.1. Règle de production Elle est de la forme : Si P1 et P2 et ... et Pm alors C1 et C2 et ... et Cn. Les prémisses (Pi) décrivent une certaine situation et les conclusions (Ci) sont un ensemble d'actions à entreprendre si les prémisses sont satisfaites. Les prémisses ou conditions sont normalisées sous forme de quadruplets : . Ce formalisme sous forme de règles de production n'est que la représentation externe de la connaissance. La plupart des systèmes « compilent » l'ensemble des règles pour obtenir une représentation interne efficace. La représentation interne a pour effet de structurer la connaissance en groupant en listes (au sens de LISP) les règles et les prémisses. Exemple de règles de production : règle1 : fleur et graine => phanérogame règle 2 : phanérogame et graine nue => sapin .... Ces règles sont mises sous forme déclarative afin que les procédures d'interprétation puissent les utiliser. On peut rajouter une nouvelle règle (règle 3) sans mettre en cause toute la structure globale du système. règle 3 : si phanérogame et rhizome => muguet Dans l'approche classique, le rajout de cette nouvelle règle est possible en modifiant la procédure correspondante, ce qui impliquera la remise en cause de la procédure (ordre d'ajout, ...). Ces règles sont assez proches du modèle de représentation des connaissances humaines, qui est largement utilisé dans les approches de modélisation des connaissances. L'ensemble des règles est appelé base de règles. L'un des premiers systèmes qui a utilisé ce mode de représentation est MYCIN. Il a été développé à l'université de Stanford (1976). 3.2. Formalismes Logiques Le principe est celui du calcul de prédicats et consiste à utiliser les symboles de prédicats et les symboles de fonctions d'arité quelconque pour représenter les connaissances. Alors, soient des ensembles dénombrables disjoints : V : variables C : constantes Fj : symboles fonctionnels j-aires Pj : symboles relationnels j-aires Un terme (ou ensemble de termes) est le plus petit ensemble défini sur l'alphabet : V » C » ( » Fj ) » { ( } » { ) } » {; } tel que : Si t1, ..., tn sont des termes et f ∈ Fj alors f(t1,...,tn) est un terme I. SOUICI @ 2015 / 2016

6

Modèles de connaissances incertaines

Chapitre I : Schémas de représentation de connaissances

Exemple : x (variable), a (constante), f(a), g(a,x,f(x,a)) De la même manière se définissent un atome et une formule. Les techniques les plus répandues concernent la logique des prédicats dite du premier ordre et sont fondées sur l'emploi d'une seule règle d'inférence : principe de résolution de Robinson (1965), notamment utilisé dans PROLOG. Le vocable premier ordre signifie que les prédicats contiennent des variables, paramètres quantifiés universellement, qui peuvent être remplacés par n'importe quelle expression bien formée du langage. L'emploi de logiques d'ordre supérieur (logique d'ordre 2, ...) permet par exemple de faire porter les quantificateurs sur des prédicats ou des fonctions. Il existe aussi d'autres logiques : les logiques non monotones et les logiques non classiques. Les logiques non monotones ont attiré l'attention des chercheurs en tant que moyen de représenter le raisonnement en présence des connaissances évolutives. Elles violent le principe de la monotonie respecté par les systèmes logiques classiques selon lequel, si X et Y sont deux ensembles de formules et si X est inclus dans Y, tout théorème déductible de X est déductible de Y. Les logiques non classiques (en particulier les logiques modales et les logiques temporelles) ont été développées pour enrichir les capacités de représentation de la logique des prédicats, notamment en vue de formaliser la sémantique des langages naturels. Les concepts les plus étudiés en vue du développement de systèmes de déduction automatique sont : la nécessité, l'obligation, le temps, le savoir, la croyance. Par ailleurs on peut avoir à représenter et exploiter des connaissances sur les connaissances (méta-connaissances).

I. SOUICI @ 2015 / 2016

7