Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
MOIA
Méthodes et Outils pour
l’Intelligence Artificielle
F. BOUQUET
IUP Génie Informatique et Mathématiques
3ème année
http://lifc.univ-fcomte.fr/˜bouquet/Enseignement
MOIA Partie 1/3 – p.1/41
L’intelligence Artificielle
Philosophie : Logique, méthode de raisonnement, espritcomme système physique, apprentissage, lan-gage
Mathématiques : Représentation formelles et preuves, algo-rithmes (in)décidabilité, probabilité
Psychologie : Adaptation, phénomène de perception et decontrôle moteur, techniques expérimentales
Linguistique : Représentation des connaissances, grammaire
Neurosciences : Substrat physique de l’activité mentale
Théorie du contrôle : Systèmes asservis, stabilité, concept d’agent
MOIA Partie 1/3 – p.2/41
Plan1. Historique
2. Structuration de la connaissance
Langue naturelle, Semi-formelle, Formelle, Logique
3. Méthodes de résolution générales
Méthodes de base
Évolutions et Heuristiques
Satisfaction de contraintes
4. Domaine d’application
Système expert / Apprentissage
Jeux
Planification / Ordonnancement
Traitement du langage naturelle
MOIA Partie 1/3 – p.3/41
Historique 1/3
-3000 : Papyrus premières règles de production (médecine)
-350 : Aristote invente le syllogisme
1679 : Leibnitz invente l’arithmétique binaire
1854 : Boole et son algèbre
1938 : Shannon BInary digiT
1941 : I. Asimov écrit Robbie et les trois lois de la robotique
1943 : McCulloch & Pitts modélisation neurones et cerveau
1944 : ENIAC
1945 : J. Von Neumann et O. Morgenstein :
Solution théorique : jeux de stratégie / démo. automatique
“Intelligence Artificielle” 6= “Bêtise naturelle”
MOIA Partie 1/3 – p.4/41
Historique 2/3
1950 : "Computing Machinery and Intelligence" de Turing
1957 : Thème de l’IA : General Problem SolverN. Chomsky (MIT, linguiste) sémantique 6= syntaxe
J. Mac Carthy : Créé le premier laboratoire IA (MIT, 1958)Lisp (1958), Algorithme Alpha–Beta (1961)
1965 : Feigenbaum, Buchaman et Lederberg DENDRAL :
Mécanismes de raisonnement inductifs / empiriques
Problème consistant
J.A Robinson invente la procédure de résolutionELIZA (MIT) simule le dialogue avec un psychologue
1969 : Shakey 1er robot déplacer, percevoir, résoudre problèmes
MOIA Partie 1/3 – p.5/41
Historique 3/3
1972-74 : A. Colmerauer et P. Roussel écrive Prolog
1980 : Création de American Association Artificial Intelligence
1985 : Linguistique : Vocabulaire, reconnaissance du discourt, multi-utilisateur.
1990 : Recherche linguistique / Jeux de stratégie
1997 :
Deep Blue bat G. Kasparov
Premier match de football avec des robots
2000... :
Animaux de compagnie robot
Carneggie Mellon : les robots nomades (Antarctique)
MOIA Partie 1/3 – p.6/41
En résumé
Qu’est-ce les systèmes à base d’IA savent faire ?Jouer décemment au ping-pong
Conduire un véhicule sur une route de montagne / dans la circulation
Jouer aux cartes
Découvrir et prouver un nouveau théorème mathématiques
Inventer une histoire drôle (de façon intentionnelle)
Donner des conseils avisés dans des domaines pointus
Traduire des langues, parler une langue, parler en temps réel.
MOIA Partie 1/3 – p.7/41
Principe
Donner les moyens a l’ordinateur de :
Acquérir de l’information (connaissances)
Raisonner sur les informations
Donner les résultats
But :Transcrire le français pour l’ordinateur
Codage mémoire de l’information
Traitement
Retranscrire
MOIA Partie 1/3 – p.8/41
Français⇐⇒Machine
Logique Classique :
Logique propositionnelle
Calcul des prédicats
Logique non classique :
Default de Reiter
Logique Multi-valuée (logique floue)
Règle de production
Objets structurés :
Réseaux bayéseins
Chaînes de Markov
Réseaux de neurones
MOIA Partie 1/3 – p.9/41
Logique propositionnelle[Aristote à Boole]
Ensemble de formules :
Propositions : lettres majuscules
Connecteurs : ¬,→ (∧, ∨, ⊕...)
Parentheses : ( )
Axiomes :1. F → (G→ F )
2. (F → (G→ H))→ ((F → G)→ (F → H)
3. ((¬G)→ (¬F ))→ (F → G)
Regle(s) d’inference (Modus ponens/ Modus Tollens) :
Si (F et F → G) alors G Si (¬G et F → G) alors ¬F
MOIA Partie 1/3 – p.10/41
Logique des prédicats
Extension de la Logique propositionnelle [Kleene 72]
Extension des Formules :
Constantes, Variables
Fonctions, Prédicats
Extension des Axiomes :
4. Occurrence de x dans F liée, ∀x(F→ G)→ (F→ ∀xG)
5. Occurrence de x liée, ∀xF(x)→ F(t)
Quantificateur(s) :
Universel : ∀
Existentiel : ∃
MOIA Partie 1/3 – p.11/41
Formalisation du discours
Enoncé
Discours
énoncésLiaison entre
Propriétésdes objetsentre objets
CorrespondanceObjets
QuantificateursConnecteurs
PrédicatsFonctionsVariables Constantes
Termes
Atomes
Rep
rése
ntat
ion Formules
Rée
l
MOIA Partie 1/3 – p.12/41
Defaut [Reiter 79]
Extension de la Logique des predicats
Theorie des defauts, ∆ = (D,W) :
W : ensemble de faits, formules closes du 1er ordre
D : ensemble de défauts, règles d’inférence à contenu spécifique
Un defaut :Soient les formules du 1er ordre avec x comme variable libre :
u(x), prérequis
v(x), la justification
w(x), la conséquence
u(x) : v(x)
w(x)
MOIA Partie 1/3 – p.13/41
Multi-valuée [Kleene 38]
p q ¬p p→ q p ∨ q p ∧ q p ≡ q
0 0 1 1 0 0 1
0 12 1 1 1
2 0 0
0 1 1 1 1 0 012 0 1
212
12 0 0
12
12
12
12
12
12 1
12 1 1
2 1 1 12 0
1 0 0 0 1 0 0
1 12 0 1
2 1 12 0
1 1 0 1 1 1 1
I(¬p) = 1− I(p)
I(p ∨ q) = Max(I(p), I(q))
I(p ∧ q) = Min(I(p), I(q))
I(p→ q) = Max(1− I(p), I(q))
I(p ≡ q) = (I(q) = I(p))
Tiers exclu : p ∨ ¬p
Principe de non-contradiction¬(p ∧ ¬p)
↪→ ne sont pas des tautologies
MOIA Partie 1/3 – p.14/41
Règles de production
Si A alors B (0,8)
Une règle se décompose en 3 parties :
Condition d’application : A
Déduction obtenue : B
Facteur de certitude : 0,8
Calcul d’une transition AFC−→ B :
{
FC(source) = 1
FC(B) = Max(0, FC(A))× FC
MOIA Partie 1/3 – p.15/41
Objets structurés
Base sur les reseaux semantiques (graphe) :
Nœud représente des concepts
Arc traduit les relations entre concepts
↪→ Recherche de solutions dans graphe
Ajouter pour l’inference :
Règles de production
Opérateurs logiques
MOIA Partie 1/3 – p.16/41
Réseau Bayésein
Constitution :Graphe orienté acyclique:
Noeud représente une variable aléatoireArc les relations entre les variables
Série de distributions conditionnelles
Theoreme de Bayes : Prob(A|B) = Prob(B|A)×Prob(A)Prob(B)
Rapport de vraisemblance : λ(B|A) = Prob(B|A)
Prob(B|A)
Vraisemblance a priori : V (A) = Prob(A)
Prob(A|B)
Vraisemblance a posteriori :V (A|B) = Prob(A|B)
Prob(A|B)= λ(B|A)× V (A)
MOIA Partie 1/3 – p.17/41
Chaîne de Markov (Monte carlo)
Codage d’evolution/transition :
Probabilité déplacement de x→ y : p(x, y)
Distribution uniforme π(x) =∫
Pπ(y)× p(y, x)δy
Definir p(x,y) :
Echantillonneur de Gibbs
Algorithme de Metropolis-Hastings
Satisfait :• Réversibilité • Irréductible
• Apériodique • Récurrence
MOIA Partie 1/3 – p.18/41
Réseau de neurones
Σ
X1
Xn
X2
P1
P2
Pn
.
.
.
Y
Signal recu :
Sr = Σni=1(pi × xi)
Signal emis:{
1 si Sr ≥ θ
0 si Sr < θ
MOIA Partie 1/3 – p.19/41
Problème
Definitions :
Tout problème est relatif à un certain ensemble d’objets que l’on peutdécrire sous forme de variables d’etat du problème
Un etat du probleme est l’ensemble des valeurs que prennent sesvariables d’états à un instant donné.
L’espace d’etats d’un problème est l’ensemble des états possiblespour le problème considéré.
MOIA Partie 1/3 – p.20/41
Problème
Decrit par
État initial (Initialisation)
Transition (Règles)
Espace de recherche/états(atteignables)
État final (condition d’arrêt)
Resolution
Parcours de l’espace de recherche
Stratégies (Largeur, Profondeur ...)
Heuristiques (Best-First, Taboo,Recuit-simulé, Sac à dos ...)
A
C
BCA
BABC
B
AC
C
B
A
B
A
C
ABC
BAC
CBA
AB
C
C
AB
AC
B
ABC
C
C
A
B
B
A
MOIA Partie 1/3 – p.21/41
Parcours en profondeur
Principe : Explorer chemin par chemin
Instance d’entree : un nœud
de sortie : un chemin Sol (solution)
Si N est solution alors Sol← {N}
Sinon
Soit N1 un successeur de Net Sol1 menant à la solution à partir de N1
=⇒ Sol← {N, Sol1}
Probleme : Les cycles dans les graphes=⇒ Détection
J
A
CB
GFED
KIH
H I J K
D E F G
B C
A
MOIA Partie 1/3 – p.22/41
Parcours en profondeur bornée
Principe : Limiter la profondeur de la recherche
Instance d’entree : un nœud, une profondeur
de sortie : un chemin Sol (solution)
Si N est solution alors Sol← {N}
Sinon
Si profondeur ≥ 1 alors
· profondeur← profondeur - 1· Soit N1 un successeur de N· et Sol1 menant à la solution à partir
de N1
=⇒ Sol← {N, Sol1}
H I J K
D E F G
B C
A
MOIA Partie 1/3 – p.23/41
Parcours en largeur
Principe : Examiner tous les chemins en même temps
Instance d’entree : une liste de chemin
Instance de sortie : un chemin Sol (solution)
Si le nœud du chemin courant Ch estsolution alors Sol← Ch
Sinon
Calculer toutes les extensions de Ch
Ajouter les extensions en fin de liste H I J K
D E F G
B C
A
MOIA Partie 1/3 – p.24/41
Critères de comparaison
Completude : est-ce que la méthode garantit de trouverune solution si elle existe?
Complexite en temps : combien de temps faut-il pourtrouver la solution?
Complexite en espace : quel espace mémoire faut-il poureffectuer la recherche?
Optimalite : est-ce que la méthode trouve la meilleuresolution s’il en existe plusieurs?
MOIA Partie 1/3 – p.25/41
Comparaison
Méthode Complexité Optimal Complet
Temps Espace
Largeur O(bm) O(bm) oui oui
Largeur itératif O(bm) O(b×m) oui oui
Profondeur O(bm) O(m) non non
Profondeur bornée O(bl) O(l) non oui si l ≥ p
Bi-directionnal O(bm
2 ) O(bm
2 ) oui oui
b : facteur de branchement
m : profondeur maximal del’arbre
p : profondeur de la solution
l : limite de la profondeur derecherche
MOIA Partie 1/3 – p.26/41
Bilan sur les Parcours "aveugle"
3 méthodes explorent l’espace de recherche
Profondeur plus facile mais cycle (limiter recherche,marquage)
Largeur plus difficile à implanter et gestion liste
Problème d’optimisation : associer coût aux arcs(transitions)
Explosion combinatoire plus important pour la largeur=⇒ Utilisation Heuristique
MOIA Partie 1/3 – p.27/41
Heuristique
h : U −→ R+
But: Améliorer la convergence vs Exploration aveugle
Comment : prendre en compte des informations sur legrapheType d’heuristique :
Parfaite : ∀u, v h(u) = h(v)⇔ h∗(u) = h∗(v)
Presque parfaite : ∀u, v h(u) < h(v)⇒ h∗(u) < h∗(v)
Monotone/consistante : ∀u, ∀v, h(u)− h(v) ≤ k(u, v), v descendant de u
Minorante/admissible : ∀u, h(u) ≤ h∗(u)
h(u) : heuristique, coût entre u est état final ; k(u, v) : poids des arcs
MOIA Partie 1/3 – p.28/41
Heuristique et propriété
Une heurisitique est specifique au problème posé
Elle peut définir une relation ordre partiel
Elle peut définir une relation ordre complet
Si l’heuristique est parfaite, alors l’algorithme convergeimmédiatement vers le but
Si l’heuristique est minorante alors l’algorithme A∗
trouvera toujours le chemin optimal
Si l’heuristique est monotone est admissible et garantitque l’algorithme A∗ pour tout nœud développé calcul lechemin optimal.
MOIA Partie 1/3 – p.29/41
Stratégies de recherche
Deux types de developpement d’etats :Complètement développé
Partiellement développé
Trois types d’organisation des alternatives :LIFO
FIFO
Recherche ordonnée
MOIA Partie 1/3 – p.30/41
Les méthodes du gradient
Gradient : variation - progression vers la solution. Onessaie d’atteindre un optimum global par une successiond’optimums locaux.
Exemple : pour traverser une ville du nord au sud, onessaiera de minimiser ou maximiser l’écart par rapport àla direction.
Algorithme du simplex en programmation linéaire
Méthode par approximations successives en analyse numérique
Min-Max en programmation des jeux
Algorithme A* ...
MOIA Partie 1/3 – p.31/41
Best-Fisrt
But : heuristique pour converger le plus rapidement
Idee : continuer la recherche avec le meilleur candidatAlgorithme associe :
Gourmand (Greedy) ou Escalade (hill-climbing)
Algorithme A∗
Variantes de A∗ : IDA∗, SMA∗, AO∗...
MOIA Partie 1/3 – p.32/41
Exemple - Gourmand
U15
U16
U14
U13
U9
U11
U10U7
U5
U 6
U8
U4
3UU2
U0
U1
U12
0
0
7
2
9
7
6
11
1215
15
13
15 7
1617
4
5
2
3 228
156
41
1
8
9
10
12
4
2
6
5
9
4
37
6
86
3
5
1
8
296
9
1
3
3
4
5
Chemin solution : {U0, U5, U7, U10, U12, U13, U16},
Coût : f(U16) = 26
MOIA Partie 1/3 – p.33/41
Algorithme A∗
G← (u0); D ← ∅; f(u0)← 0Tant que G 6= ∅ faire
u← premier(G); G← G \ (u); D ← D ∪ (u)Si u 6∈ T alors
Tant que suivant(u) 6= ∅ fairev ← suivant(u)Si (v 6∈ D ∪G) ou (g(v) > g(u) + k(u, v)) alors
g(v)← g(u) + k(u, v)f(v)← g(v) + h(v)père(v)← u
insérer_selon_f(G, v)Fin faire
Fin faire MOIA Partie 1/3 – p.34/41
Exemple - A∗
U15
U16
U14
U13
U9
U11
U10U7
U5
U 6
U8
U4
3UU2
U0
U1
U12
0
0
7
2
9
7
6
11
1215
15
13
15 7
1617
4
5
2
3 228
156
41
1
8
9
10
12
4
2
6
5
9
4
37
6
86
3
5
1
8
296
9
1
3
3
4
5
Chemin solution : {U0, U1, U4, U9, U10, U12, U13, U16},
Coût : f(U16) = 22
MOIA Partie 1/3 – p.35/41
Terminaison de l’algorithme A∗
Pour toute h, application de U −→ R+, et pour tout G (graphe fini à valations
positives ou nulles) A∗ s’arrete. Soit sur un état terminal, soit faute d’état(G 6= ∅) s’il n’existe pas de chemin de u0 à T .
Si G et h vérifient les hypothèses suivantes :G est un δ-graphe fini ou infini à valuations positives ou nulles danslequel il existe au moins un chemin de longueur finie entre u0 et un étatterminal.
h est une application de U −→ R+ telle qu’il existe un majorant ν avec
h(ui) ≤ ν pour tout état ui sur un chemin optimal de u0 à un étatterminal.
alors A∗ s’arrête après un nombre fini d’étapes et fournit unchemin de u0 à T . MOIA Partie 1/3 – p.36/41
Complexité
Soit n le nombre d’états de l’espace d’états du problème.Pire des cas, la complexité est en 2n
Si h est une heuristique minorante, complexité n2 .
Si h est une heuristique monotone, complexité n.
Remarque : Même une complexité linéaire sur le nombred’états est souvent inutilisable dans la plupart des caspratiques
Exemple : Voyageur de commerce n = v! (v = nombre devilles).
MOIA Partie 1/3 – p.37/41
Variante A∗
Interative deepening A∗ : IDA∗
Recursif Best-First Search : RNFS
Algorithme AO∗ :
Développement
Mise à jour ascendante
Définition de la nouvelle meilleure solution
MOIA Partie 1/3 – p.38/41
Graphe ET-OU
Problèmes qui peuvent se décomposer en élémentsmutuellement independants
Heuristiques :
Lorsque u est un nœud ET
h(u) = Σv∈Successeur(u)(k(u, v) + h(v))
Lorsque u est un nœud OU
h(u) =
minv∈Successeur(u)(k(u, v) + h(v))
(p (q (r s)))
(q (r s))
(r s)
p
q
r s
MOIA Partie 1/3 – p.39/41
Algorithme AO∗
{Entree : u0, T, {S1, . . . , Sm}, couts k, fonction h}{Sortie : Solution G(u0) de cout f(u0)}
P ← {u0}; Q← ∅; f(u0)← h(u0); u← u0
Tant que (u 6= null) et (f(u0) 6=∞) faire
‖ P ← P \ {u}; Q← {u}
‖ Pour i ∈ I(u) faire
‖ | Pour v ∈ (Si(u) \ (P ∪Q)) faire
‖ | | P ← P ∪ {u}; f(v)← h(v)
‖ | fi(u)← k(u, i) + Σv∈Si(u)f(v)
‖ Fin pour
‖ Si I(u) = ∅ alors f(u)←∞
‖ Sinon f(u)← min{fi(u)|i ∈ I(u)}
‖ | Imin(u)← indice du minimum‖ A← S−1(u)
‖ Pour w ∈ S−1(u) faire
‖ | I ′(w)← {i inI(w)|u ∈ Si(w)}
‖ Tant que A 6= ∅ faire
‖ | Choisir v ∈ A tel que A ∩ S(v) = ∅
‖ | A← A \ {v}
‖ | Pour i ∈ I ′(v) faire
‖ | | fi(v)← k(v, i) + Σw∈si(v)f(w)
‖ | Si fImin(v) 6= min{fi(v)|i ∈ I(v)}
‖ | | alors Imin(v)← indice du minimum‖ | Si f(v) 6= fImin
(v) alors
‖ | | f(v)← fImin(v)
‖ | | A← A ∪ S−1(v)
‖ | | Pour w ∈ S−1(v) faire
‖ | | | I ′(w)← I ′(w)∪
‖ | | {i ∈ I(w)|v ∈ Si(w)}
‖ | Fin si
‖ | I ′(v)← ∅
‖ Fin tant que
‖ G(u0)← Définir_Solution(u0)
‖ u← Choisir_Etat(G(u0))
Fin tant que
MOIA Partie 1/3 – p.40/41
Exemple - AO∗
U 1
U6U 5
U11
U16
U 12 U 13
U 17 U 18
U0
U 2
U 19
U 3 U4
U 7 U8 U 9
U20
23U22U21U
U 14(4)
U10(14)
U 15(0)
(20)(40)(30)
(25)
(5) (11)
(10) (5) (10)
(30) (28)(15)(16)
(0)
(0)(0)(0)
(0)(0)
(0)4
5
4
20 4
19
38
5
99
15
2535
5
7
5 34
10
20 156
5
5
12
Chemin solution : {U0, U1, U2, U13, U17, U19, U22, U23},
Coût : f(U0) = 74
MOIA Partie 1/3 – p.41/41