Solution Examen final
Intelligence Artificielle II (IFT-17587)
Mercredi 30 avril 2003
De 12h30 à 15h20 en salles PLT-2341
• Tout document est permis.
• Le nombre de points accordés à chacune des questions est inscrit entre parenthèses.
• Le questionnaire a 7 questions sur 4 pages.
------------------------------------------------------------------------
1 (25 pts) Supposons une machine à trois registres A, B et C. Initialement, ils contiennent les
valeurs 1, 2 et 3 respectivement. Il y a une seule instruction, appelée Assigner(x,y) qui
copie la valeur du registre x dans le registre y. Le seul prédicat est Valeur(x, v), qui dit
que le registre x contient la valeur v. Nous voulons utiliser un algorithme de
planification partiellement ordonné pour construire un plan pour inverser les contenus
des registres A et B. Pour les questions b), c), d), e) et f), tous les changements apportés
au plan doivent être indiqués clairement.
a) En utilisant la notation graphique pour les opérateurs STRIPS, décrivez
l’opérateur Assigner avec ses préconditions et ses effets.
Valeur(x, v1), Valeur(y, v2)
Assigner(x,y)
Valeur(y, v1), ¬Valeur(y, v2)
b) Dessinez le plan initial du problème en utilisant la notation graphique.
Valeur(A, 1)
Valeur(A, 2)
Départ Valeur(B, 2) Fin
Valeur(B, 1)
Valeur(C, 3)
1
c) Maintenant, le planificateur décide d’accomplir la condition du but qui dit que B
doit avoir la valeur 1. Ajoutez dans le plan l’action Assigner pour que cette
condition soit satisfaite. Effectuez toutes les assignations de variables nécessaires.
Valeur(A, 1) Valeur(A, 2)
Départ Valeur(B, 2) Fin
Valeur(B, 1)
Valeur(C, 3)
Valeur(x, 1) Valeur(B, 1)
Valeur(B, v2) Assigner(x,B) ¬Valeur(B, v2)
d) Maintenant, supposons que le planificateur décide d’accomplir les préconditions
de l’action Assigner en la connectant à l’étape Départ. Mettre à jour votre plan en
effectuant toutes les assignations nécessaires.
Valeur(A, 1) Valeur(A, 2)
Départ Valeur(B, 2) Fin
Valeur(B, 1)
Valeur(C, 3)
Valeur(B, 1)
Valeur(A, 1)
Valeur(B, 2) Assigner(A,B) ¬Valeur(B, 2)
e) Maintenant, le planificateur décide d’accomplir l’autre condition du but, c’est-à-
dire que A contienne la valeur 2. Expliquez les différentes étapes lors de l’ajout
d’une autre action Assigner pour accomplir cette précondition. Dessinez votre
plan avec cette nouvelle action.
2
Valeur(x, 2) ¬Valeur(A, v2)
Valeur(A, v2) Assigner(x,A) Valeur(A, 2)
Valeur(A, 1) Valeur(A, 2)
Départ Valeur(B, 2) Fin
Valeur(B, 1)
Valeur(C, 3)
Valeur(A, 1) Valeur(B, 1)
Valeur(B, 2) Assigner(A,B) ¬Valeur(B, 2)
f) Expliquez les étapes pour compléter le plan et complétez votre plan.
Valeur(C, 2) ¬Valeur(A, 1)
Valeur(A, 1) Assigner(C,A) Valeur(A, 2)
Valeur(B, 2)
Valeur(C, 3) Assigner(B,C) Valeur(C, 2)
¬Valeur(C, 3)
Valeur(A, 1) Valeur(A, 2)
Départ Valeur(B, 2) Fin
Valeur(B, 1)
Valeur(C, 3)
Valeur(A, 1) Valeur(B, 1)
Valeur(B, 2) Assigner(A,B) ¬Valeur(B, 2)
g) Représentez votre plan final en donnant toutes les composantes du plan sous
forme d’ensembles. Les quatre ensembles sont : actions, liens d’ordonnancement,
liens causaux et préconditions ouvertes.
Actions : {Assigner(A,B), Assigner(B,C), Assigner(C,A), Départ, Fin}
Liens d’ordonnancement : {Assigner(B,C) < Assigner(A,B), Assigner(A,B) <
Assigner(C,A), Départ < Assigner(B,C), Départ < Assigner(A,B), Départ <
Assigner(C,A), Départ < Fin, Assigner(B,C) < Fin, Assigner(A,B) < Fin,
Assigner(C,A) < Fin}
3
Liens causaux : {Départ ÆValeur(A,1) Assigner(A,B), Départ ÆValeur(B,2)
Assigner(A,B), Départ ÆValeur(A,1) Assigner(C,A), Départ ÆValeur(B,2)
Assigner(B,C), Départ ÆValeur(C,3) Assigner(B,C), Assigner(B,C) ÆValeur(C,2)
Assigner(C,A), Assigner(C,A) ÆValeur(A,2) Fin, Assigner(A,B) ÆValeur(B,1) Fin }
Préconditions ouvertes : {}
2 (21 pts) Considérez le réseau bayésien suivant.
P(H)
0,1 H
H P(S)
S T 0,3
H S P(T) F 0,9
T T 0,9 T
T F 0,5
F T 0,8
T P(E)
F F 0,2
E T 0,6
F 0,1
a) Selon la structure du réseau, est-ce que les équations suivantes sont vrais ou fausses,
expliquez?
i) P(H,S) = P(H)P(S)
Faux, parce que S est dependant de H.
ii) P(E|T,H) = P(E|T)
Vrai, parce qu’un noeud est conditionnellement indépendant de ses
non décendants sachant ses parents.
b) Calculez les probabilités suivantes en montrant les calculs :
i) P(e, h, s, t)
P(e, h, s, t) = P(e|t)P(t|h,s)P(s|h)P(h) = 0,6 * 0,9 * 0,3 * 0,1 = 0,0162
ii) P(¬e, h, s, t)
P(¬e, h, s, t) = P(¬e|t)P(t|h,s)P(s|h)P(h) = 0,4 * 0,9 * 0,3 * 0,1 = 0,0108
4
iii) P(e, h, s, ¬t)
P(e, h, s, ¬t) = P(e|¬t)P(¬t|h,s)P(s|h)P(h) = 0,1 * 0,1 * 0,3 * 0,1 = 0,0003
iv) P(¬e, h, s, ¬t)
P(¬e, h, s, ¬t) = P(¬e|¬t)P(¬t|h,s)P(s|h)P(h) = 0,9 * 0,1 * 0,3 * 0,1 = 0,0027
c) Calculez P(E| h,s) en montrant les calculs.
P(E| h,s) = α P(E, h, s, T) = α (P(E, h, s, t) + P(E, h, s, ¬t)) = α (<0.0162, 0.0108> +
<0.0003, 0.0027>) = α (<0.0165, 0.0135>) = <0.55, 0.45>
Où α = 1/(0.0165 + 0.0135) = 33.33333333
3 (10 pts) Après avoir passé un test de dépistage du SRAS, le médecin de John lui dit que le test
de dépistage a retourné qu’il était atteint du SRAS. Le test de dépistage est précis à 90%
(ce qui veut dire que la probabilité de tester positif lorsque l’on est atteint du SRAS est
de 90% et que la probabilité de tester négatif si l’on a pas le SRAS est de 90%). La
maladie ne touche qu’une personne sur 20000. Quelle est la probabilité que John soit
atteint du SRAS?
P(tp|s) = 0.9
P(tn|¬s) = 0.9
P(s) = 0.00005
P(s|tp) = (P(tp|s) * P(s)) / (P(tp|s)P(s) + P(tp|¬s)P(¬s)) = (0.9 * 0.00005) / (0.9*0.00005
+ 0.1*0.99995) = 0.0004498
4 (15 pts) Supposons un problème de classification consistant à déterminer la classe
d’appartenance de chacune des instances. Le domaine de valeurs des classes possibles
est : {1, 2, 3}. Selon la base de connaissance suivante, déterminez la classe de l’instance
< 3, 12, 4, 7, 8 > à l’aide de l’algorithme des k-voisins les plus proches avec distances
pondérées. Montrez tous les calculs.
Instances A1 A2 A3 A4 A5 Classe
X1 3 5 4 6 1 1
X2 4 6 10 3 2 2
X3 8 3 4 2 6 3
5
X4 2 1 4 3 6 3
X5 2 5 1 4 8 2
Dist(Y, X1)2 = 99, Dist(Y, X2)2 = 125, Dist(Y, X3)2 = 135, Dist(Y, X4)2 = 142, Dist(Y, X5)2 = 68
Pour la valeur 1, la somme donne : 1/99 = 0.0101
Pour la valeur 2, la somme donne : 1/125 + 1/68 = 0.0227
Pour la valeur 3, la somme donne : 1/135 + 1/142 = 0.01445
La plus grande somme est pour la valeur 2, donc la classe retournée est la classe 2.
5 (7 pts) Construisez un réseau de neurones retournant la fonction majorité pour 5 attributs en
entrée. Les attributs peuvent avoir les valeurs 0 ou 1. La fonction majorité retourne 1 si
au moins la moitié des entrées sont à 1.
Les cinq entrées sont connectées au même neurone. Les poids sont tous de valeur 1. La borne de la
fonction d’activation est de 2.5. Donc, le neurone retourne 1 si la somme est plus grande que 2.5, ce
qui survient uniquement lorsque plus de la moitié des entrées sont à 1.
6 (7 pts) Expliquez brièvement (2 à 4 phrases) l’utilisation d’un ensemble d’entraînement et d’un
ensemble de test lors de l’évaluation d’un programme d’apprentissage.
Lorsque l’on veut évaluer un programme avec un ensemble fixe d’exemples, normalement, on le
divise en deux ensembles, un ensemble d’entraînement et un ensemble de test ou de validation. Le
programme utilise l’ensemble d’entraînement pour l’apprentissage. Par la suite, on teste l’efficacité
du programme sur l’ensemble de test. En faisant cela, on s’assure que le programme n’apprend pas
uniquement les exemples, mais qu’il apprend le concept sous jacent.
6
7 (15 pts) Vrai ou Faux?
a) On peut dire qu’un agent qui apprend est un agent qui ajuste son standard de
performance pour améliorer son efficacité.
Faux
b) Les agents apprenants n’utilisent pas toujours le comportement appris pour
choisir leurs actions.
Vrai
c) Lorsque l’on utilise l’apprentissage par renforcement, l’agent ne sait pas ce qu’il
doit apprendre.
Vrai
d) Pour tous les plans partiellement ordonnés avec aucune précondition non
satisfaite et aucun conflit, il existe au moins une linéarisation du plan qui est une
solution correcte.
Vrai
e) L’architecture la plus utilisée en robotique est l’architecture de subsomption.
Faux
f) Dans les systèmes multiagents, tous les agents doivent coopérer ensemble pour
atteindre un but.
Faux
g) Une architecture réflective est une architecture permettant à l’agent de délibérer
sur ses propres composantes de calculs.
Vrai
h) Un algorithme en tout temps (de type « anytime ») peut retourner le meilleur
plan n’importe quand.
Faux
i) Il n’y a qu’une décomposition possible par action lorsque l’on utilise la
décomposition hiérarchique pour la planification.
Faux
j) En planification conditionnelle, l’agent a un plan pour toutes les situations
possibles.
Vrai