IA-Cours

Julien Chauveau

Informations

• Publié par: Mothug
• Nombre de lectures: 97
• Langue: Français

Extrait

Intelligence artificielle
Références
“Intelligence artificielle — Artificial Intelligence”, PH Winston, Addison Wesley
“La représentation des connaissances”, D. Kayser, Hermes
“Artificial Intelligence”, H. Rich, Addison Wesley
Historique
La préhistoire 1945 - 1955
Traduction automatique.
Les débuts 1955 - 1970
Apparition du mot Intelligence artificielle
Conférence de Dartmouth aux Etats-Unis (Août 1956)
Claude Shannon, John McCarthy (LISP, 1958), Marvin Lee Minsky
Postulat de John McCarthy :
“Toute activité intelligente est modélisable et reproductible par une machine”
Premier programme d’IA : “The Logic Theorist” 1956, démonstrateur de théorèmes.
Autres programmes : A.M. (Automated Mathematician) de Douglas Lenat 1974 est un
programme de découverte, Eurisko ou MACISTE de Jacques Pitrat
Systèmes généraux de résolution de problèmes — General Problem Solver (GPS)
Newell, Analyse fins-moyens — “means ends analysis” : Etat initial → Etat finaloperateurs
Caractériser les opérateurs en tant que réducteur de différences, entre états.
Programmes de jeux d’échecs
“What Computers Can’t Do” Herbert L. Dreyfus, 1972, MIT Press
1958-1960 : Création de LISP par John McCarthy
La spécialisation 1970-1980
J.A. Robinson (1965) : principe de résolution à la base de PROLOG
Alain Colmerauer, Robert Kowalski
L’intelligence artificielle se scinde en différentes branches :
• La compréhension (traitement) du langage naturel
• La démonstration automatique de théorèmes
• Les jeux
• La résolution de problèmes généraux : Metaheuristique, Problèmes à satisfaction de
contraintes (CSP)
• La résolution de problèmes experts
• La représentation des connaissances
• La perception : reconnaissance des formes, paroles
• L’apprentissage
La reconnaissance 1980-1990
Projet japonais de la cinquième génération d’ordinateurs
Conception de machines adaptées aux tâches intelligentes
M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle 1Les différentes approches de l’intelligence artificielle
L’approche cognitive : l’IA est la réalisation de programmes qui imitent l’esprit humain dans •
leur fonctionnement (approche pluridisciplinaire)
L’approche pragmative : On cherche à utiliser au mieux la machine de façon à obtenir de •
meilleurs résultats que les humains pour résoudre une même tâche — cf. Test de Turing,
Résolution de problèmes par recherche heuristique
L’approche connexioniste : Réseaux de neurones, Perceptron, Franck Rosenblatt (1957)•
Principaux points du cours
Systèmes à base de règles (systèmes experts) utilisés en diagnostic, tâche de conception…•
Raisonnement sur des connaissances incomplètes, vagues…•
Recherche heuristique, Algorithmes A* et AO*, Applications aux jeux (MinMax, AlphaBeta)•
M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle 2Les systèmes experts — systèmes à base(s) de connaissances
Le terme apparaît dans les années 1970
Idée de base : séparation nette entre les connaissances et la façon de les utiliser
Exemples
X = Y + 70
Trois cas d’utilisations :
1) Calcul de X connaissant Y
2) Calcul de Y connaissant X
3) Vérification d’une contrainte
Base de Si Conditions Alors Actions
connaissances Prémisses Conclusion
Règles Interpréteur de règles
Composants d’un Système Expert
1) Langage d’expression des connaissances
Langage correspondant à la logique des propositions
Système (langage) d’ordre Zéro.
Langage susceptible de comporter des variables (ou attributs)
Système d’ordre Unariables ayant un ensemble de valeurs possibles
+Système d’ordre Zéro
Langage attribut valeur
exemples : TEMP = 15 ; carre(x)
2) Une base de connaissance
Conjonction de formules atomiques
Base de faits permanents
exemple : en diagnostic automobile : alimenter ( batterie, démarreur )
Base de faits liés à un problème particulier
exemple : ¬ alimenter (démarreur)
Une base de règles est un ensemble de formules de la forme :
SI Antécédent ALORS Conséquent
Prémisse Conclusion
SI condition ALORS conclusion (ou action)
M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle 3<{
SI le spectre possède 2 pics aux masses m1 et m2 tels que
- m1 + m2 = m + 28
- et m1 - 28 est un pic élevé
- et m2 - 28 est un pic élevé
- et au moins m1 ou m2 est élevé
ALORS la molécule contient un groupe Céton pic_élevé(x) x ≥ 36
Quand les conclusions sont des faits, système dit analytique•
Quand les conclusions sont des actions, système dit synthétique•
3) Moteur d’inférences (interpréteur de règle)
Il réalise des cycles comportant les phases suivantes :
- sélection d’un sous-ensemble de règles applicables
(ensemble de conflits : sous-ensemble de règles applicables)
- résolution des conflits : choix d’une règle à déclencher dans l’ensemble des conflits
- exécution (déclenchement) de la règle choisie
Le moteur d’inférence fonctionne selon différentes stratégies :
- chaînage avant : les règles qui sont déclenchées dans le sens
“partie prémisses” → “partie conséquence(s)”
- chaînage arrière (inverse)
- contrôle par des méta-règles (règles qui indiquent comment utiliser les connaissances
Base de faitsMOTEUREXPLICATIONS
d'inférences
Base de règles
APPRENTISSAGE
INTERFACE utilisateur
Les déductions peuvent être effectuées en :
“chaînage avant” : à partir des faits initiaux, on déclenche itérativement toutes les règles qui
peuvent l’être, jusqu’à satisfaction d’un but donné ou saturation complète de la base de faits
“chaînage arrière” : à partir d’un but donné par l’expert ou choisi par le système, on remonte
récursivement vers les faits initiaux. On décrit ainsi un arbre de recherche ET - OU (un fait
peut être démontré de plusieurs façons s’il est en partie droite de plusieurs règles → noeud
OU ; tous les faits en partie gauche d’une règle doivent être démontrés pour affirmer la partie
droite → nœud ET).
Dans les deux cas, le système ou moteur d’inférences peut poser des questions à l’expert
pour tenter de compléter la base de faits initiale.
M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle 4" Pattern-matching "
ou filtrage
règles applicables
(ensemble des conflits) Certains système
comportent une
étape de restrictionSélection de la règle suivante qui consiste à(résolution de conflit) réduire l'ensemble
des règles filtrées
(ex : niveaux)
Règle à appliquer
Application de la règle
MAJ de la base de faits
Nouvelle base de faits
phase 2 : EXECUTIONphase 1 : EVALUATION
RESTRICTION
Exécution des actionsfournit :
R1 inclus dans BR
des règles de R3F1 inclus dans BF
BF et, éventuellement, BR
FILTRAGE
fournit, peuvent être modifiés
par comparaison
entre R1 et F1 d'autres effets
R2 inclus dans R1 sont possibles
(vers l'environnement du
RESOLUTION système par exemple)
DE CONFLITS
fournit,
R3 inclus dans R2
Eventuellement : Eventuellement :
arrêt ou retour-arrière ou autre arrêt ou retour-arrière ou autre
effets sur le contrôle du moteur effets sur le contrôle du moteur
BR et BF désignent respectivement les bases de règles et faits telles qu'elles sont au début de
l'EVALUATION. Le moteur commande l'enchainement des étapes de la phase d'EVALUATION
M1 Info 2005 / 2006 — Université d’Angers — Intelligence artificielle 5‰
‰
<t
‡
‰
‰
‰
<|
‰
A C B H
Si A et B et C Alors D
Si B et H Alors D
D
B HSi B ou H Alors D
!
Si B Alors D
Si H D
Ordre partiel sur la règle : R < R si une conséquence de R apparaît dans la prémisse de Ri j i j
Faits déductibles (apparaissent dans la partie conclusion d’une ou plusieurs règles)
Faits donnés (initialement dans la base de faits)
Faits démontrables (les autres)
CHAINÂGE AVANT
- On sature la BF
- Version de base onn boucle sur BR (sans ordre partiel)
- On vérifie qu’on fait au moins une inférence par cycle sinon c’est fini
- Variables globales :
BR = ensemble de règles
Demandables = ensemble de faits
BF = ensemble des faits initiaux
VF(f) = valeur de f dans BF
VA(m,r) = affirmation ou négation du mot m dans Ant.(r), r BR
VC(m,r) = affirmation ou négation du mot m dans Cons.(r),