IA41 Concepts fondamentaux en Intelligence Artificielle et langages ddis CM #1
Introduction l'IA : dfinitions, gense, domaines, reprsentation des connaissances et langages ddis
Fabrice LAURI
Organisation d'IA41
Enseignants Fabrice Lauri Olivier Grunder Marina Piercy Claude Renaud [Link]@[Link]
Horaires Cours : Jeudi 8h-10h TD 1 : Jeudi 10h15-12h15 TD 2 : Mardi 10h15-12h15 TD 3 : Vendredi 8h-10h TD 4 : Lundi 8h-10h TD 5 : Vendredi 10h15-12h15 TP 1 : Mercredi 10h15-12h15 TP 2 : Mardi 14h-16h TP 3 : Vendredi 14h-16h TP 4 : Mardi 16h15-18h15 TP 5 : Lundi 10h15-12h15
Plan du cours
1. Dfinitions, gense, problmes typiques et domaines de recherche de l'IA 2. Dmarche gnrale pour la rsolution de problmes Modes de reprsentation des connaissances Rcursivit 3. Introduction aux langages ddis la rsolution de problmes d'IA : PROLOG et LISP
Dfinitions, gense, problmes typiques et domaines de recherche de l'Intelligence Artificielle
Question
Que doit possder chacun des systmes suivants :
Rponse
... une certaine once d'intelligence ! Mais qu'est-ce que l'intelligence ? Cela dpend qui on pose la question...
J. Piaget C. Darwin
H.E. Gardner
A. Binet
Rponses
L'intelligence, c'est selon : J. Piaget (psychologue, biologiste et logicien) : l'adaptation du sujet son milieu. Deux types d'intelligence : sensori-motrice et verbale ou rflchie.
C. Darwin (biologiste) : ce qui permet la survie de l'individu
A. Binet (pdagogue et psychologue) : ce que mesurent les tests d'intelligence...
Rponses
H.E. Gardner (psychologue) : thorie de l'intelligence multiple. Plusieurs types d'intelligence coexiste chez chaque tre humain : - logico-mathmatique, - visuo-spatiale, - verbo-linguistique, - corporelle-kinesthsique, - intrapersonnelle, - interpersonnelle, - naturaliste, - musicale, - existentielle ou spirituelle.
Mais encore...
Avant eux, d'autres philosophes, psychologues, biologistes, etc. ont galement voulu comprendre comment l'Homo sapiens sapiens pense, peroit, agit. Le domaine de l'IA s'inspire de ses travaux et les enrichit : en plus de vouloir comprendre l'intelligence, elle tente galement d'en construire. L'IA systmatise et automatise les tches intellectuelles.
Une brve gense de l'IA
La prhistoire : 1945-1955 Pendant la guerre : dcryptage Techniques de dcryptage traduction automatique Echec, mais : dcouverte de l'importance des connaissances non exprimes reprsentation des connaissances acquisition des connaissances
Une brve gense de l'IA
Les dbuts : 1955-1970 Acte de naissance : en 1956 une confrence au Dartmouth College par J. McCarthy Fondation : toute activit intelligente est modlisable et reproductible par une machine. 1956 : 1er programme d'IA, Logic Theorist, par Newell, Shaw et Simon pour la dmonstration automatique. 1957 : programme de jeu d'checs, NSS, et systme de rsolution de problmes gnraux, GPS. 1960 : dveloppement de LISP par McCarthy Dveloppement de DENDRAL, un des 1ers systmes experts
Une brve gense de l'IA
Les dbuts : 1955-1970 Hypothses fondatrices de l'IA symbolique par Simon et Newell : Tout systme de symboles possde les moyens ncessaires et suffisants pour une action intelligente de caractre gnral. et Un systme de symbole est une machine qui produit dans le temps un assemblage volutif de structures de symboles.
Une brve gense de l'IA
La spcialisation : 1970-1980 Premiers systmes base de connaissances 1965 : principe de rsolution par Robinson, la base de PROLOG. Intelligence Artificielle
Comprhension du langage naturel
Dmonstration automatique de thormes
Reprsentation de la connaissances
Rsolution de problmes
Apprentissage
Perception
Jeux
Une brve gense de l'IA
Une reconnaissance : 1980-1990 Projet Cinquime Gnration au Japon : dvelopper des technologies et des techniques efficaces des avances dans les architectures parallles, bases de donnes, langages de programmation, traitement des informations gntiques... Programme Strategic Computer Initiative par le DARPA : 1 milliards de dollars Ordinateur d'checs : DEEP THOUGHT Systmes experts : PROSPECTOR, R1/XCON
Qu'est-ce que l'Intelligence Artificielle ?
M. Minsky : ... the science of making machines do things that would require intelligence if done by humans.
J.L. Laurire : Tout problme pour lequel aucune solution algorithmique n'est connue, relve a priori de l'intelligence artificielle.
D. McDermott & E. Charniak : l'tude des facults mentales l'aide de modles de type calculatoire.
Qu'est-ce que l'Intelligence Artificielle ?
P. Winston : l'tude des ides qui permettent aux ordinateurs d'tre intelligents.
H. Prade : consiste donner des machines des capacits leur permettant d'effectuer des tches ou des activits rputes intelligentes (car jusqu' prsent uniquement ralises par des humains).
C. Pellegrini : ... une forme de raction l'affirmation longtemps admise stipulant que les ordinateurs ne peuvent pas raliser des tches requrant de l'intelligence.
Domaines typiques de l'IA
Les domaines typiques de l'IA ont deux caractristiques en commun :
manipulent des informations symboliques ou numriques : lettres, mots, signes, dessins, nombres...
impliquent des choix : certains instants, faire face plusieurs possibilits non dterminisme, composante essentielle de l'intelligence
Domaines typiques de l'IA
La perception et la reconnaissance des formes
Les mathmatiques et la dmonstration automatique de thormes
Les jeux La rsolution de problmes La comprhension du langage
Problmes typiques d'IA
Problmes entirement spcifiables et difficiles Exemples : problme du voyageur de commerce, tourne de vhicules, les jeux (puzzles, checs, dames...) Problmes couvrant un domaine prcis : systmes experts Description spcifiable partiellement Mais buts (trs) clairs Exemples : MYCIN, DENDRAL, R1/XCON
Rsolution non dterministe : la recherche de la solution est arborescente et non plus squentielle.
Exemples de systmes d'IA
Robots Programme d'checs Systme de reconnaissance vocale Systme de synthse de la parole Systme de traduction automatique Systme de reconnaissance de forme Systme de diagnostic mdical Programme de preuve de thorme Programme de mots croiss Programme d'laboration de tournes de facteurs ...
Les deux dimensions de l'IA
Systmatise et automatise les tches intellectuelles pour laborer des machines capables de :
Penser comme un humain (approche cognitive) Agir comme un humain (approche pragmatiste)
Penser rationnellement (approche base sur une logique mathmatique) Agir rationnellement (domaine de l'optimisation)
Penser comme un humain
Approche cognitive de l'IA : raliser des programmes imitant dans leur fonctionnement l'esprit humain. sciences cognitives Sciences cognitives : ont pour but de dcrire, expliquer et le cas chant, simuler les principales dispositions de l'esprit humain - langage, raisonnement, perception, coordination motrice, planification. Encyclopedia Universalis
Penser comme un humain
L'IA de la machine est alors construite partir de modles et techniques emprunts plusieurs domaines (psychologie, linguistique, philosophie, neuroscience...) : tats mentaux structures de mmoire apprentissage de symboles ...
Agir comme un humain
Approche pragmatiste de l'IA : dvelopper des thories permettant d'amliorer notre capacit programmer efficacement un ordinateur. Si possible, cherche obtenir de meilleurs rsultats que ceux que pourraient obtenir un tre humain. Une I.A. = bote noire manipulant les donnes d'entre pour obtenir des rsultats en sortie. Bote intelligente = si elle russit un certain nombre de tests, qui, russis par un tre humain, permettrait de dire qu'il est intelligent.
Agir comme un humain
Mthodologie : identifier une tche ou activit pour laquelle l'homme est meilleur que la machine la faire raliser par la machine Exemples : Prouver un thorme Jouer aux checs Diagnostiquer une maladie Planifier ses dplacements Se dplacer dans un btiment Test de Turing...
Agir comme un humain : le test de Turing
Penser / agir rationnellement
Objectif : Prendre toujours la meilleure dcision possible compte tenu des lments disponibles et connus (informations/connaissances, temps, ressources) Raisonnement logique lorsque : connaissances parfaites ressources illimites Rationnalit limite lorsque : connaissances imparfaites ressources limites
Techniques empruntes la recherche oprationnelle, la thorie du contrle, l'conomie. Ignore le rle de la conscience et des motions sur le processus de raisonnement
Penser rationnellement
Aristote : quels sont les processus corrects de la pense ? Logique mathmatique : permet de reprsenter des noncs du monde et de raisonner en les manipulant de manire formelle la base de systmes modernes de rsolution de problmes complexes Difficults : tous les comportements ne sont pas le rsultat de raisonnements logiques difficile d'exprimer le monde rel en terme de faits uniquement vrais ou faux
Agir rationnellement
Comportement rationnel = effectuer l'action correcte, la plus adquate tant donn ce que l'on sait de la situation actuelle. Action correcte : celle qui est suppose optimiser un objectif donn Comportement rationnel : ne requiert pas ncessairement le fait de penser (ex. : cligner des yeux) mais la pense doit tre au service de l'action rationnelle. Exemple : agent rationnel, rgit par une fonction f : P* A, qui en fonction des percepts reus choisit la meilleure action raliser.
Une entit intelligente
C. Pellegrini, 2005
Un agent intelligent
C. Pellegrini, 2005
Prdictions et ralit
Dans les annes 60, un clbre professeur du MIT disait : la fin de l't, on aura construit un oeil lectronique. En 2007, il n'y a toujours pas de systme de vision par ordinateur capable de comprendre une scne complexe. Mais des systmes informatiques effectuent quotidiennement : Surveillance de trafic routier, Reconnaissance de visages Analyse d'images mdicales ...
Prdictions et ralit
En 1958, H. Simon (CMU) prdisait que dans 10 ans, un programme informatique serait capable de battre le meilleur joueur aux checs. Cette prdiction s'est vrifie en 1997 : Deep Blue a battu Kasparov : 3,5 contre 2,5. Aujourd'hui, les ordinateurs ont gagn des titres de champion du monde aux jeux de dames, Othello, checs. Ils restent encore trs mauvais au jeu de Go, jeu hautement stratgique...
Prdictions et ralit
Dans les annes 1970, beaucoup croyaient que les robots informatiss seraient incontournables, prsents dans les usines aussi bien qu'au domicile. Aujourd'hui, quelques industries (automobiles, lectronique) sont trs robotises, mais les robots domestiques sont encore utopiques. Des robots ont explors Mars, d'autres ralisent des oprations chirurgicales (cerveau, coeur) et des robots humanodes sont disponibles la location au Japon.
(voir [Link]
Prdictions et ralit
Dmarche gnrale pour la rsolution de problmes, reprsentation des connaissances et notions de rcursivit
Caractristiques de l'nonc d'un problme
Qu'est-ce qu'un problme : Situation dans laquelle on ne voit pas immdiatement la suite d'actions effectuer pour atteindre un objectif. La plupart des problmes ne sont pas poss de manire formelle (rigoureuse), car exprims en langage naturel, qui est : Incomplet : nonc contient des informations implicites Ambigu Redondant : nonc peut insister sur des informations qui ne traduisent pas forcment les difficults du problme Incorrect
Dmarche gnrale pour la rsolution de problmes (1/2)
E1 : Comprhension de la totalit de l'nonc E2 : Infrences immdiates E3 : Identification de la difficult du problme E4 : Incubation (pause,distraction) E5 : Reformulation, choix d'une reprsentation E6 : Rsolution partielle (retour E2) ou totale E7 : Vrifier E8 : Gnraliser Concevoir un plan Excuter le plan Examiner la solution Comprendre
Dmarche gnrale pour la rsolution de problmes (2/2)
Gnraliser : 1) Peut-on appliquer la mthode propose sur une gnralisation du problme 2) Existe-t'il d'autres problmes o la mme mthode s'appliquerait avec succs ? 3) Existe-t'il d'autres mthodes pour ce problme ?
Les reprsentations
Une reprsentation ne vaut que par la facilit de mise en oeuvre des procdures de traitement. J.L. Laurire Un mode de reprsentation des connaissances inclut : une structure de donnes codant la connaissance un mcanisme d'exploitation de la connaissance code Un mode de raisonnement doit possder trois proprits : Clart, Puissance d'expression, Efficacit du mcanisme d'exploitation Reprsentation dclarative reprsentation procdurale
Quelques reprsentations
Plusieurs reprsentations en fonction du problme rsoudre :
Reprsentations logiques Rseaux smantiques Rgles de production Frames
Reprsentations logiques
Connaissance = formule construite selon une syntaxe prcise. Rgles de raisonnement : modus ponens, modus tollens, rsolution... Exemples : (A B) (A B) C (A B) C x f( x ) g( x ) x f( x ) g( x )
Rseaux smantiques
Hirarchie de concepts, dictionnaire sous forme de graphe Noeud = concept Arc = relation entre concepts Mcanisme d'hritage de proprits
Exemple : Clyde est un moineau. Un moineau est une sorte d'oiseau. Un oiseau a des ailes.
Rgles de production
Connaissance dclarative de la forme : Si <condition> Alors <conclusion> () Exemple : Si le moteur cale et l'allumage est correct et le rservoir d'essence n'est pas vide Alors vrifier la carburation.
Les Frames
Reprsentation d'expriences passes Granularit importante : connaissances structures relatives un objet, concept ou situation Exemple : <frame vin : sorte de : boisson appellation : (domaine : AOC/vin de pays) (dfaut: vin de pays) (si besoin : demander appellation) nature : (domaine : sec/demi-sec/doux/liquoreux/cors) degr alcool : (intervalle : 9 15) (dfaut : 12) producteur : (si besoin : trouver nom sur tiquette) robe : ... >
Notation des reprsentations
Notations linaires : infixes, prfixes, postfixes Notations non linaires : sous forme d'arbres sous forme de graphes
Dfinition de la rcursivit
La rcursivit est la possibilit de faire apparatre dans la dfinition d'une entit une rfrence elle-mme. Dans ce cas, on dit que l'entit possde une dfinition rcursive ou qu'elle est intrinsquement rcursive. En programmation, on distingue deux types d'entits rcursives : - les fonctions rcursives - fonction factorielle, fonction puissance - fonction de Fibonacci - les structures de donnes rcursives - les nombres - les listes - les arbres - les objets fractals...
Approche pour la construction d'algorithmes rcursifs (1/2)
Un problme se prte bien l'analyse rcursive lorsqu'il peut tre dcompos en sous-problmes de taille plus petite et de mme nature que le problme initial. L'analyse rcursive est constitue de trois tapes : 1) paramtrage du problme 2) recherche d'un cas trivial et de sa solution 3) dcomposition du cas gnral
Approche pour la construction d'algorithmes rcursifs (2/2)
1) Paramtrage du problme Il s'agit d'identifier tous les paramtres du problme, en particulier ceux dont la taille dcrot chaque appel rcursif. 2) Recherche d'un cas trivial et de sa solution Un cas trivial est un sous-problme qui peut tre rsolu SANS appel rcursif. Il correspond souvent au cas o la taille est nulle. 3) Dcomposition du cas gnral Cette tape a pour but de ramener le problme donn l'instant t vers un ou plusieurs sous-problmes que l'on suppose dj traits des instants prcdents et de taille plus petite.
Application de l'approche : dfinition de la fonction factorielle
Par exemple, dfinir la fonction factorielle revient spcifier les trois tapes suivantes : 1) Paramtrage (profil) de la fonction factorielle : N N 2) Cas trivial Pour n < 2, factorielle( n ) = 1 3) Cas gnral (appel rcursif) Pour n >= 2, factorielle( n ) = n * factorielle( n-1 )
Notations pour l'criture d'une fonction : exemple avec la fonction factorielle
1. Profil : factorielle : N N 2. Dfinition formelle de factorielle( n ) : {n<2} { n >= 2 } factorielle( n ) = 1 factorielle( n ) = n * factorielle( n-1 )
3. Jeu d'essais : factorielle( 3 ) = 3 * factorielle( 2 ) = 3 * 2 * factorielle( 1 ) = 3*2*1 = 6 (voir page suivante)
Excution d'une fonction rcursive : exemple avec la fonction factorielle
factorielle( 3 )
Excution d'une fonction rcursive : exemple avec la fonction factorielle
factorielle( 3 ) 3 * factorielle( 2 )
Excution d'une fonction rcursive : exemple avec la fonction factorielle
factorielle( 3 ) 3 * factorielle( 2 )
1
Appel rcursif
factorielle( 2 ) 2 * factorielle( 1 )
Excution d'une fonction rcursive : exemple avec la fonction factorielle
factorielle( 3 ) 3 * factorielle( 2 )
1
Appel rcursif Appel rcursif
factorielle( 2 ) 2 * factorielle( 1 )
2
factorielle( 1 ) 1
Excution d'une fonction rcursive : exemple avec la fonction factorielle
factorielle( 3 ) 3 * factorielle( 2 ) factorielle( 2 ) 2 * factorielle( 1 ) Valeur = 1 factorielle( 1 ) 1
1
Excution d'une fonction rcursive : exemple avec la fonction factorielle
factorielle( 3 ) 3 * factorielle( 2 ) Valeur = 2 factorielle( 2 ) 2 * factorielle( 1 )
2
Valeur = 1 factorielle( 1 ) 1
Excution d'une fonction rcursive : exemple avec la fonction factorielle
Valeur = 6 factorielle( 3 ) 3 * factorielle( 2 )
3
Valeur = 2 factorielle( 2 ) 2 * factorielle( 1 )
2
Valeur = 1 factorielle( 1 ) 1
Langages ddis la rsolution de problmes d'IA
Catgories de langages
Langages procduraux (Fortran, C, Pascal, ADA...) Programmation imprative : programme indique par son algo. quelles sont les tapes permettant d'aboutir une solution. Programme = donnes + actions Excution d'un programme = changement d'tat de la mmoire centrale Langages orients objets (Smalltalk, C++, Java...) Gnralement bass sur la programmation imprative Bass sur la notion de classes et d'objets (instances de classes) Encapsulation des donnes (attributs) et des fonctions (oprations) manipulant ces donnes Une classe n'est pas excutable : elle doit tre instancie La mme classe peut tre instancie plusieurs fois : les attributs des diffrentes instances peuvent alors avoir des valeurs diffrentes.
Catgories de langages
Langages logiques (Prolog) Programmation dclarative Programme = base de faits et rgles Aucune description du processus de rsolution Excution d'un programme = indication de but(s) sous forme de requte(s) Moteur d'infrences tente de satisfaire le(s) but(s) partir des faits et des rgles Bass sur la logique des prdicats du premier ordre Langages fonctionnels (Lisp, Caml) Programme = description d'une fonction qui, applique des arguments, retournera un rsultat. Possibilit de crer des fonctions d'ordre suprieur : fonctions acceptant des fonctions en arguments et retournant des fonctions comme rsultat. Bass sur le -calcul.
Exemple #1 de programme PROLOG
On dsire disposer d'une base de faits voquant les relations suivantes : Jean-Claude est le pre d'Andr La est la mre d'Andr Hugues est le pre de Jean-Claude Hugues est le grand-pere d'Andr Pour transformer ces noncs en PROLOG, il faut : identifier les objets identifier les relations entre objets. En PROLOG, ces relations s'appelle des prdicats. Un prdicat est soit vrai, soit faux.
Exemple #1 de programme PROLOG
On dsire disposer d'une base de faits voquant les relations suivantes : Jean-Claude est le pre d'Andr La est la mre d'Andr Hugues est le pre de Jean-Claude Hugues est le grand-pere d'Andr En vert : les objets En rouge : les relations.
Exemple #1 de programme PROLOG
Programme : L1 pere( 'jean-claude', andre ). L2 mere( lea, andre ). L3 pere( hugues, 'jean-claude' ). L4 grand_pere( X,Y ) :- pere( X, Z ), pere( Z, Y ). Faits Rgle
Signification : 'jean-claude', andre, lea et hugues sont des objets constants pere, mere et grand_pere sont des prdicats, c'est--dire des relations entre objets qui sont supposes vraies X, Y et Z sont des variables pouvant tre instancies par les constantes dfinies prcdemment.
Exemple #1 de programme PROLOG
Programme : L1 pere( 'jean-claude', andre ). L2 mere( lea, andre ). L3 pere( hugues, 'jean-claude' ). L4 grand_pere( X,Y ) :- pere( X, Z ), pere( Z, Y ). Faits Rgle
Signification : L1 : Jean-Claude est le pre d'Andr L2 : La est la mre d'Andr L3 : Hugues est le pre de J.-C. L4 : X est grand-pre de Y si il existe un Z tel que X est pre de Z et Z est pre de Y.
Exemple #2 de programme PROLOG
Programme : L1 factorielle( 0, 1 ). L2 fatorielle( 1, 1 ). L3 factorielle( N, R ) :- N > 1, N1 is N-1, factorielle( N1,R1 ), R is N*R1. Signification : factorielle est un prdicat qui relie un premier entier un autre Le premier entier reprsente le paramtre d'entre de la fonction Le second entier reprsente le rsultat de la factorielle L1 : la factorielle de 0 est 1 L2 : la factorielle de 1 est 1 L3 : si N > 1, la factorielle de N est R, avec R = N* (N-1)! is est un prdicat prdfini de PROLOG qui value le terme droite et affecte sa valeur la variable de gauche.
Exemple de programme LISP
Programme : L1 (setq personnes '("jean-claude" "andre" "lea" "hugues")) L2 (car personnes) L3 (car (cdr personnes)) L4 (+ 1 5 6 8) L5 (* (+ 5 2 3) (- 5 2)) Signification : L1 : personnes est une liste contenant les chanes de caractres... L2 : retourne le premier lment de la liste L3 : retourne le premier lment du reste de la liste L4 : calcule la somme de 1,5,6 et 8 et l'affiche L5 : affiche 30
Plan des cours
1. Introduction l'IA 2. Concepts fondamentaux des SBC et de PROLOG 3. Programmation PROLOG 4. Systmes formels et logique propositionnelle 5. Logique des prdicats du premier ordre 6. Introduction la thorie des langages formels 7. Introduction aux problmes de satisfaction de contraintes 8. Introduction au Lambda calcul et LISP 9. LISP 10. Planification et stratgie de recherche dans les graphes 11. Thorie des jeux et algorithmes 12. Pratique de la programmation d'IA dans les jeux 13. Introduction l'apprentissage automatique 14. Bilan des apports de l'IA et rfrences bibliographiques