Examen final
Intelligence artificielle II (IFT-17587)
De 15h30 à 18h20 le 2 mai 2002, salle PLT-2341
Question 1 (15 points)
Transformer l’expression suivante, écrite en logique du premier ordre, pour qu’elle soit
en forme normale conjonctive.
(∀x∃y P(x) ⇒ (Q(x) ∧ M(y, x))) ∨ ¬ (∃x R(x) ∧ S(x))
Question 2 (30 points)
Un robot mécanique, constitué de 2 bras, doit déplacer des objets de boîte en boîte. Ses
deux bras se termine par une pince qu’il peut utiliser pour prendre des objets. Pour tenter
de diminuer les collisions possibles entre les deux bras, les concepteurs ont décidé qu’il
n’y aurais qu’un seul bras qui pourrait se déplacer à la fois. Ce robot a 5 actions à sa
disposition pour déplacer un objet d’une boîte à une autre :
• Prendre(O, P) pour prendre l’objet O avec la pince P. Bien entendu, il ne peut
prendre l’objet que si la pince est vide, l’objet est libre et que la pince et l’objet
sont à la même place.
• Soulever(O, P) permet au robot de soulever l’objet pour le sortir de la boîte. Bien
entendu, l’objet doit être déplaçable et le robot doit la tenir entre une de ses
pinces.
• Déplacer(O, P, l1, l2) déplace l’objet O avec la pince P de la position l1 à la
position l2. Pour déplacer l’objet, la pince doit tenir l’objet dans les airs, au dessus
des boîtes.
• DéplacerPince(P, l1, l2) déplace la pince P de la position l1 à la position l2.
• Déposer(O, P) dépose l’objet O avec la pince P dans une des boîtes.
• Relâcher(O, P) relâche l’objet O tenu par la pince P. Par sûreté, le robot ne peut
pas relâcher un objet s’il est dans les airs.
Page 1 de 4
a) (10 points) Vous devez définir les opérateurs STRIPS pour chacune de ces
actions. Pour ce faire, vous devez définir tous les prédicats nécessaires et donnez
une courte explication pour chacun.
b) (5 points) Construisez le plan partiel pour un robot qui voudrait déplacer deux
objets vers la boîte 3. Le premier objet est dans la boîte 1 et le deuxième objet est
dans la boîte 2. Les deux pinces commencent à des positions aléatoires.
c) (5 points) Combien y a-t-il de linéarisations possibles pour ce plan ?
d) (10 points) Supposons maintenant que le robot ne sait pas si les objets sont
déplaçables avec une seule pince. Si l’objet est trop lourd ou trop grand, le robot
doit utiliser ces deux pinces pour le soulever et le déplacer. Pour ce faire, le robot
doit avoir une autre action Vérifier(O), qui vérifie si l’objet peut être déplacé avec
une seule pince ou deux. En utilisant les actions précédentes et cette nouvelle
action, construisez un plan conditionnel partiellement ordonné pour déplacer un
objet d’une boîte à une autre. Les deux pinces commencent à des positions
aléatoires. Par ailleurs, si vous avez besoin de modifier les opérateurs existants,
indiquez-le.
Question 3 (15 points)
Un patient se rend chez son médecin parce qu’il a de la fièvre et qu’il ressent des douleur
dans le dos. Le médecin soupçonne que le patient a la maladie M. La probabilité d’avoir
la maladie M est de 1%. La probabilité d’avoir mal au dos si on a la maladie M est de
95%, tandis que la probabilité d’avoir mal au dos si on n’a pas la maladie M est de 30%.
La probabilité d’avoir de la fièvre si on a la maladie M est de 80%, tandis que la
probabilité d’avoir de la fièvre si on n’a pas la maladie M est de 40%. La probabilité
d’avoir mal au dos si on a de la fièvre est de 50%. Finalement, la probabilité d’avoir de la
fièvre si on a la maladie M et mal au dos est de 90%. Traduisez ce problème sous forme
de probabilités à priori et conditionnelles en utilisant les variables M(pour maladie),
F(pour fièvre) et D(pour mal au dos). Donnez la probabilité que le patient ait la maladie
M étant donné qu’il a mal au dos et qu’il a de la fièvre, c’est-à-dire P(M | F, D).
Page 2 de 4
Question 4 (15 points)
Sur votre nouvelle voiture, il y a un dispositif qui vous donne un avertissement s’il y a un
objet trop proche de votre voiture. Votre voiture utilise un détecteur d’objets, lui
permettant de voir les objets qui se trouve autour de votre voiture. En considérant la
vitesse de la voiture et la position des objets, ce dispositif d’avertissement se déclenchera
pour vous avertir du danger si un objet est trop proche de votre voiture. Considérons les
variables suivantes : V (vitesse de la voiture), CV (compteur de vitesse), CVD (compteur
de vitesse défectueux), DO (détecteur d’objets), O (objets), DOD (Détecteur d’objets
défectueux), SA (système d’avertissement) et SAD (système d’avertissement défectueux).
a) (8 points) Dessinez un réseau de croyance pour ce domaine, sachant que le
compteur de vitesse a tendance à être plus imprécis lorsque la vitesse augmente et
que le détecteur d’objet détecte plus difficilement les objets qui sont petits.
b) (7 points) Supposons qu’il n’y a que deux valeurs possibles pour la vitesse
(Normale ou Élevée) et que le compteur de vitesse donne la bonne vitesse x% du
temps lorsqu’il fonctionne, mais uniquement y% du temps lorsqu’il est
défectueux. Donnez alors la table de probabilités conditionnelles pour CV.
Question 5 (15 points)
Avec un de vos partenaires de bureau, vous effectuez des paris sur l’issue des parties de
votre équipe de hockey favorite. Toutefois, au lieu de tout simplement vous fiez à votre
instinct, vous avez décidé d’utiliser un arbre de décision pour vous aider à choisir. Pour
ce faire, vous avez enregistré les résultats des parties passées, en notant si les parties se
jouaient à l’extérieur ou à domicile, si votre gardien super vedette était partant et si
l’autre équipe était mieux positionnée dans le classement.
Page 3 de 4
No Endroit GSV partant Autre Équipe Gagné
1 Domicile Oui Meilleure Oui
2 Étranger Oui Meilleure Non
3 Domicile Oui Moins bonne Oui
4 Domicile Non Moins bonne Oui
5 Étranger Non Moins bonne Non
6 Domicile Oui Moins bonne Oui
7 Étranger Non Meilleure Non
8 Étranger Oui Moins bonne Non
9 Étranger Oui Meilleure Oui
10 Domicile Oui Moins bonne Oui
Construisez l’arbre de décision à partir de ces données. Donnez uniquement les deux
premiers niveaux de l’arbre, c’est à dire les trois premiers nœuds avec les ensembles
contenant les numéros de parties présents à chaque nœud. (4 points bonis pour ceux qui
terminent l’arbre avec tous les calculs).
Question 6 (10 points)
Construisez un réseau de neurones permettant de connaître la valeur de vérité de
l’expression suivante : (¬A ∨ B) ⇒ C. Vous devez spécifier tous les poids et toutes les
fonctions d’activation.
Page 4 de 4
Corriger Examen final
Intelligence artificielle II (IFT-17587)
De 15h30 à 18h20 le 2 mai 2002, salle PLT-2341
Question 1 (15 points)
Transformer l’expression suivante, écrite en logique du premier ordre, pour qu’elle soit
en forme normale conjonctive.
(∀x∃y P(x) ⇒ (Q(x) ∧ M(y, x))) ∨ ¬ (∃x R(x) ∧ S(x))
Réponse :
(∀x ∃y P(x) ⇒ (Q(x) ∧ M(y,x))) ∨ ¬(∃x R(x) ∧ S(x))
Élimination des implications
(∀x ∃y ¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ ¬(∃x R(x) ∧ S(x))
Déplacer les signes de négation sur les atomes
(∀x ∃y ¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ (∀x ¬(R(x) ∧ S(x)))
(∀x ∃y ¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ (∀x ¬R(x) ∨ ¬S(x))
Standardiser les variables
(∀x ∃y ¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ (∀z ¬R(z) ∨ ¬S(z))
Déplacer les quantificateurs à gauche
∀x ∃y ∀z (¬P(x) ∨ (Q(x) ∧ M(y,x))) ∨ (¬R(z) ∨ ¬S(z))
Skolemization
∀x ∀z (¬P(x) ∨ (Q(x) ∧ M(F(x),x))) ∨ (¬R(z) ∨ ¬S(z))
(¬P(x) ∨ (Q(x) ∧ M(F(x),x))) ∨ (¬R(z) ∨ ¬S(z))
Distribuer les ∧ par rapport au ∨
((¬P(x) ∨ Q(x)) ∧ (¬P(x) ∨ M(F(x),x))) ∨ (¬R(z) ∨ ¬S(z))
((¬P(x) ∨ Q(x)) ∨ (¬R(z) ∨ ¬S(z))) ∧ ((¬P(x) ∨ M(F(x),x)) ∨ (¬R(z) ∨ ¬S(z)))
Regrouper les ∧ et les ∨
(¬P(x) ∨ Q(x) ∨ ¬R(z) ∨ ¬S(z)) ∧ (¬P(x) ∨ M(F(x),x) ∨ ¬R(z) ∨ ¬S(z))
Page 1 de 17
Question 2 (30 points)
Un robot mécanique, constitué de 2 bras, doit déplacer des objets de boîte en boîte. Ses
deux bras se termine par une pince qu’il peut utiliser pour prendre des objets. Pour tenter
de diminuer les collisions possibles entre les deux bras, les concepteurs ont décidé qu’il
n’y aurais qu’un seul bras qui pourrait se déplacer à la fois. Ce robot a 5 actions à sa
disposition pour déplacer un objet d’une boîte à une autre :
• Prendre(O, P) pour prendre l’objet O avec la pince P. Bien entendu, il ne peut
prendre l’objet que si la pince est vide, l’objet est libre et que la pince et l’objet
sont à la même place.
• Soulever(O, P) permet au robot de soulever l’objet pour le sortir de la boîte. Bien
entendu, l’objet doit être déplaçable et le robot doit la tenir entre une de ses
pinces.
• Déplacer(O, P, l1, l2) déplace l’objet O avec la pince P de la position l1 à la
position l2. Pour déplacer l’objet, la pince doit tenir l’objet dans les airs, au dessus
des boîtes.
• DéplacerPince(P, l1, l2) déplace la pince P de la position l1 à la position l2.
• Déposer(O, P) dépose l’objet O avec la pince P dans une des boîtes.
• Relâcher(O, P) relâche l’objet O tenu par la pince P. Par sûreté, le robot ne peut
pas relâcher un objet s’il est dans les airs.
a) (10 points) Vous devez définir les opérateurs STRIPS pour chacune de ces
actions. Pour ce faire, vous devez définir tous les prédicats nécessaires et donnez
une courte explication pour chacun.
Réponse :
Prédicats :
• At(x, y) : L’objet ou la pince x est à la position y. Pour les objets, on
considère qu’ils sont à une certaine position uniquement s’ils ne sont pas
tenu par une pince. Si l’objet est tenu par une pince, c’est la position de la
pince qui est importante.
Page 2 de 17
• Libre(O) : L’objet O est libre, c’est-à-dire qu’il n’est pas tenu par une
pince.
• Vide(P) : La pince P ne tient aucun objet.
• Tient(P,O) : La pince P tient l’objet O.
• Déplaçable(O) : L’objet O est déplaçable.
• Enbas(P) : Indique que la pince est en bas, c’est-à-dire qu’elle est dans une
des boîtes et qu’elle peut donc soit saisir un objet ou en déposer un.
Opérateurs :
• OP(ACTION : Prendre(O,P,L), PRECOND : At(P,L) ∧ At(O,L) ∧ Libre(O) ∧
Vide(P) ∧ EnBas(P), EFFECT : ¬Libre(O) ∧ ¬Vide(P) ∧ Tient(P,O))
• OP(ACTION : Soulever(O,P), PRECOND : Déplaçable(O) ∧ Tient(P,O) ∧
EnBas(P), EFFECT : ¬EnBas(P))
• OP(ACTION : Déplacer(O,P, l1, l2), PRECOND : ¬EnBas(P) ∧ Tient(P,O) ∧
At(P,l1), EFFECT : At(P,l2) ∧ ¬At(P,l1))
• OP(ACTION : DéplacerPince(P, l1, l2), PRECOND : ¬EnBas(P) ∧ At(P,l1),
EFFECT : At(P,l2) ∧ ¬At(P,l1))
• OP(ACTION : Déposer(O,P), PRECOND : ¬EnBas(P) ∧ Tient(P,O),
EFFECT : EnBas(P))
• OP(ACTION : Relâcher(O,P,L), PRECOND : EnBas(P) ∧ Tient(P,O) ∧
At(P,L), EFFECT : ¬Tient(P,O) ∧ Libre(O) ∧ Vide(P) ∧ At(O,L))
b) (5 points) Construisez le plan partiel pour un robot qui voudrait déplacer deux
objets vers la boîte 3. Le premier objet est dans la boîte 1 et le deuxième objet est
dans la boîte 2. Les deux pinces commencent à des positions aléatoires.
Page 3 de 17
Début
¬EnBas(P1) ∧ At(P1,l1)
DéplacerPince(P1, l1, B1) ¬EnBas(P2) ∧ At(P2,l2)
DéplacerPince(P2, l2, B2)
At(P1,B1) ∧ At(O1,B1) ∧ Libre(O1) ∧ Vide(P1) ∧ EnBas(P1)
Prendre(O1,P1,B1) At(P2,B2) ∧ At(O2,B2) ∧ Libre(O2) ∧ Vide(P2) ∧ EnBas(P2)
Prendre(O2,P2,B2)
Déplaçable(O1) ∧ Tient(P1,O1) ∧ EnBas(P1)
Soulever(O1,P1) Déplaçable(O2) ∧ Tient(P2,O2) ∧ EnBas(P2)
Soulever(O2,P2)
¬EnBas(P1) ∧ Tient(P1,O1) ∧ At(P1,B1)
Déplacer(O1,P1, B1, B3) ¬EnBas(P2) ∧ Tient(P2,O2) ∧ At(P2,B2)
Déplacer(O2,P2, B2, B3)
¬EnBas(P1) ∧ Tient(P1,O1)
Déposer(O1,P1) ¬EnBas(P2) ∧ Tient(P2,O2)
Déposer(O2,P2)
EnBas(P1) ∧ Tient(P1,O1) ∧ At(P1,B3)
Relâcher(O1,P1,B3) EnBas(P2) ∧ Tient(P2,O2) ∧ At(P2,B3)
Relâcher(O2,P2,B3)
At(O1,B3) ∧ At(O2,B3)
Fin
c) (5 points) Combien y a-t-il de linéarisations possibles pour ce plan ?
Réponse : Il y a 12 actions à placer. Toutefois, les six actions pour chacun des objets
doivent rester dans le même ordre. Ce qui peut changer, c’est l’alternance entre les
actions pour l’objet 1 et celles pour l’objet 2. Pour un objet, il y a six actions. Il faut
donc choisir 6 positions possibles parmi 12. Par la suite, on remplit les positions
restantes avec les six actions de l’autre objet. Pour calculer le nombre de groupes de
six positions possibles parmi 12, on peut utiliser la formule suivante : C(12, 6) = 924.
Il y a donc 924 linéarisations possibles.
Page 4 de 17
d) (10 points) Supposons maintenant que le robot ne sait pas si les objets sont
déplaçables avec une seule pince. Si l’objet est trop lourd ou trop grand, le robot
doit utiliser ces deux pinces pour le soulever et le déplacer. Pour ce faire, le robot
doit avoir une autre action Vérifier(O), qui vérifie si l’objet peut être déplacé avec
une seule pince ou deux. En utilisant les actions précédentes et cette nouvelle
action, construisez un plan conditionnel partiellement ordonné pour déplacer un
objet d’une boîte à une autre. La deux pinces commencent à des positions
aléatoires. Par ailleurs, si vous avez besoin de modifier les opérateurs existants,
indiquez-le.
Réponse :
Pour les actions Soulever, Déplacer, Déposer et Relâcher, on doit ajouter un autre
argument pour la deuxième pince lorsque les deux pinces sont utilisées sur le même
objet.
Page 5 de 17
Début
DéplacerPince(P1, l1, B1)
Prendre(O1,P1,B1)
Vérifier(O1)
(Déplaçable(O1)) (¬Déplaçable(O1))
Soulever(O1,P1) DéplacerPince(P2, l2, B1)
Déplacer(O1,P1, B1, B3) Prendre(O1,P2,B1)
Déposer(O1,P1) Soulever(O1,P1, P2)
Relâcher(O1,P1,B3)
Déplacer(O1,P1, P2, B1, B3)
Fin Déposer(O1,P1, P2)
Relâcher(O1,P1,P2,B3)
Fin
Page 6 de 17
Question 3 (15 points)
Un patient se rend chez son médecin parce qu’il a de la fièvre et qu’il ressent des douleur
dans le dos. Le médecin soupçonne que le patient a la maladie M. La probabilité d’avoir
la maladie M est de 1%. La probabilité d’avoir mal au dos si on a la maladie M est de
95%, tandis que la probabilité d’avoir mal au dos si on n’a pas la maladie M est de 30%.
La probabilité d’avoir de la fièvre si on a la maladie M est de 80%, tandis que la
probabilité d’avoir de la fièvre si on n’a pas la maladie M est de 40%. La probabilité
d’avoir mal au dos si on a de la fièvre est de 50%. Finalement, la probabilité d’avoir de la
fièvre si on a la maladie M et mal au dos est de 90%. Traduisez ce problème sous forme
de probabilités à priori et conditionnelles en utilisant les variables M(pour maladie),
F(pour fièvre) et D(pour mal au dos). Donnez la probabilité que le patient ait la maladie
M étant donné qu’il a mal au dos et qu’il a de la fièvre, c’est-à-dire P(M | F, D).
Réponse :
P(M) = 0,01
P(¬M) = 0,99
P(D|M) = 0,95
P(D|¬M) = 0,3
P(F|M) = 0,8
P(F|¬M) = 0,4
P(D|F) = 0,5
P(F|M,D) = 0,9
Ce qu’il faut trouver: P(M|F,D) = P(F|M,D) * P(M|D) / P(F|D)
On a donc besoin de : P(M|D) = P(D|M) * P(M) / P(D) et P(F|D) = P(D|F) * P(F) / P(D)
On a donc besoin de : P(D) = P(D|M) * P(M) + P(D|¬M) * P(¬M)
= 0.95 * 0.01 + 0.3 * 0.99 = 0.3065
et de : P(F) = P(F|M) * P(M) + P(F|¬M) * P(¬M)
= 0.8 * 0.01 + 0.4 * 0.99 = 0.404
Donc, P(F|D) = P(D|F) * P(F) / P(D) = 0.5 * 0.404 / 0.3065 = 0.6591
Et, P(M|D) = P(D|M) * P(M) / P(D) = 0.95 * 0.01 / 0.3065 = 0.031
Page 7 de 17
Finalement, P(M|F,D) = P(F|M,D) * P(M|D) / P(F|D) = 0.9 * 0.031 / 0.6591 = 0.0423
Le patient a donc 4,2% de chance d’avoir la maladie M, sachant qu’il a mal au dos et
qu’il fait de la fièvre.
Question 4 (15 points)
Sur votre nouvelle voiture, il y a un dispositif qui vous donne un avertissement s’il y a un
objet trop proche de votre voiture. Votre voiture utilise un détecteur d’objets, lui
permettant de voir les objets qui se trouve autour de votre voiture. En considérant la
vitesse de la voiture et la position des objets, ce dispositif d’avertissement se déclenchera
pour vous avertir du danger si un objet est trop proche de votre voiture. Considérons les
variables suivantes : V (vitesse de la voiture), CV (compteur de vitesse), CVD (compteur
de vitesse défectueux), DO (détecteur d’objets), O (objets), DOD (Détecteur d’objets
défectueux), SA (système d’avertissement) et SAD (système d’avertissement défectueux).
a) (8 points) Dessinez un réseau de croyance pour ce domaine, sachant que le
compteur de vitesse a tendance à être plus imprécis lorsque la vitesse augmente et
que le détecteur d’objet détecte plus difficilement les objets qui sont petits.
V O
CVD DOD
CV DO
SAD
SA
b) (7 points) Supposons qu’il n’y a que deux valeurs possibles pour la vitesse
(Normale ou Élevée) et que le compteur de vitesse donne la bonne vitesse x% du
temps lorsqu’il fonctionne, mais uniquement y% du temps lorsqu’il est
défectueux. Donnez alors la table de probabilités conditionnelles pour CV.
Page 8 de 17
V = Normale V = Élevée
CVD ¬CVD CVD ¬CVD
CV = Normale y x 1-y 1-x
CV = Élevée 1-y 1-x y x
Question 5 (15 points)
Avec un de vos partenaires de bureau, vous effectuez des paris sur l’issue des parties de
votre équipe de hockey favorite. Toutefois, au lieu de tout simplement vous fiez à votre
instinct, vous avez décidé d’utiliser un arbre de décision pour vous aider à choisir. Pour
ce faire, vous avez enregistré les résultats des parties passées, en notant si les parties se
jouaient à l’extérieur ou à domicile, si votre gardien super vedette était partant et si
l’autre équipe était mieux positionnée dans le classement.
Page 9 de 17
No Endroit GSV partant Autre Équipe Gagné
1 Domicile Oui Meilleure Oui
2 Étranger Oui Meilleure Non
3 Domicile Oui Moins bonne Oui
4 Domicile Non Moins bonne Oui
5 Étranger Non Moins bonne Non
6 Domicile Oui Moins bonne Oui
7 Étranger Non Meilleure Non
8 Étranger Oui Moins bonne Non
9 Étranger Oui Meilleure Oui
10 Domicile Oui Moins bonne Oui
Construisez l’arbre de décision à partir de ces données. Donnez uniquement les deux
premiers niveaux de l’arbre, c’est à dire les trois premiers nœuds avec les ensembles
contenant les numéros de parties présents à chaque nœud. (4 points bonis pour ceux qui
terminent l’arbre avec tous les calculs).
Réponse :
Les probabilités de gagner ou non la partie sont:
P(G) = 3/5, P(¬G) = 2/5
Calculons l'information totale de la table:
3 3 2 2
I (Table) = − log 2 ( ) − log 2 ( )
5 5 5 5
3 2
= − (−0,737) − (−1,322)
5 5
= 0,971
Il faut maintenant calculer les gains d'information pour chaque attribut.
Endroit
L'attribut Endroit sépare les exemples en échantillons:
C1 = 1, 3, 4, 6, 10
C2 = 2, 5, 7, 8, 9
Page 10 de 17
Pour C1 on a: P(G) = 1 et P(¬G) = 0. Donc,
I (C1 ) = −1 log 2 (1) = 0
Pour C2 on a: P(G) = 1/5 et P(¬G) = 4/5. Donc,
1 1 4 4
I (C 2 ) = − log 2 − log 2
5 5 5 5
1 4
= − (−2,322) − (−0,322)
5 5
= 0,722
Ainsi, on peut calculer l’information espérée pour compléter l’arbre en choisissant
l’attribut Endroit:
1 1
E ( Endroit ) = I (C1 ) + I (C 2 )
2 2
1 1
= (0) + (0,722)
2 2
= 0,361
Le gain d’information en choisissant Endroit est donc :
gain( Endroit ) = I (Table) − E ( Endroit )
= 0,971 − 0,361
= 0,61
GSV partant
L'attribut GSV partant sépare les exemples en échantillons:
C1 = 1, 2, 3, 6, 8, 9, 10
C2 = 4, 5, 7
Pour C1 on a: P(G) = 5/7 et P(¬G) = 2/7. Donc,
5 5 2 2
I (C1 ) = − log 2 − log 2
7 7 7 7
5 2
= − (−0,485) − (−1,807)
7 7
= 0,863
Pour C2 on a: P(G) = 1/3 et P(¬G) = 2/3. Donc,
Page 11 de 17
1 1 2 2
I (C 2 ) = − log 2 − log 2
3 3 3 3
1 2
= − (−1,585) − (−0,585)
3 3
= 0,918
Ainsi, on peut calculer l’information espérée pour compléter l’arbre en choisissant
l’attribut GSV partant:
7 3
E (GSVpar tan t ) = I (C1 ) + I (C 2 )
10 10
7 3
= (0,863) + (0,918)
10 10
= 0,880
Le gain d’information en choisissant GSV partant est donc :
gain(GSVpar tan t ) = I (Table) − E (GSVpar tan t )
= 0,971 − 0,880
= 0,091
Autre Équipe
L'attribut Autre Équipe sépare les exemples en échantillons:
C1 = 1, 2, 7, 9
C2 = 3, 4, 5, 6, 8, 10
Pour C1 on a: P(G) = 1//2 et P(¬G) = 1//2. Donc,
1 1 1 1
I (C1 ) = − log 2 − log 2
2 2 2 2
1 1
= − (−1) − (−1)
2 2
=1
Pour C2 on a: P(G) = 2//3 et P(¬G) = 1//3. Donc,
2 2 1 1
I (C 2 ) = − log 2 − log 2
3 3 3 3
2 1
= − (−0,585) − (−1,585)
3 3
= 0,918
Ainsi, on peut calculer l’information espérée pour compléter l’arbre en choisissant
l’attribut Autre Équipe:
Page 12 de 17
2 3
E ( AutreÉquipe) = I (C1 ) + I (C 2 )
5 5
2 3
= (1) + (0,918)
5 5
= 0,951
Le gain d’information en choisissant Autre Équipe est donc :
gain( AutreÉquipe) = I (Table) − E ( AutreÉquipe)
= 0,971 − 0,951
= 0,02
On choisira donc l’attribut Endroit, car il offre le meilleur gain d’information.
On pose maintenant Endroit égale à Domicile et on cherche le deuxième nœud de
l’arbre.
Les probabilités de gagner ou non la partie sont:
P(G) = 1, P(¬G) = 0
Calculons l'information totale de la table:
I (Table) = −1log 2 (1) = 0
On a donc plus besoin de continuer.
On pose maintenant Endroit égale à Étranger et on cherche le troisième nœud de
l’arbre.
Les probabilités de gagner ou non la partie sont:
P(G) = 1/5, P(¬G) = 4/5
Calculons l'information totale de la table:
1 1 4 4
I (Table) = − log 2 − log 2
5 5 5 5
1 4
= − (−2,322) − (−0,322)
5 5
= 0,722
Il faut maintenant calculer les gains d'information pour chaque attribut restant.
GSV partant
Page 13 de 17
L'attribut GSV partant sépare les exemples en échantillons:
C1 = 2, 8, 9
C2 = 5, 7
Pour C1 on a: P(G) = 1/3 et P(¬G) = 2/3. Donc,
1 1 2 2
I (C1 ) = − log 2 − log 2
3 3 3 3
1 2
= − (−1,585) − (−0,585)
3 3
= 0,918
Pour C2 on a: P(G) = 0 et P(¬G) = 1. Donc,
I (C 2 ) = −1 log 2 (1) = 0
Ainsi, on peut calculer l’information espérée pour compléter l’arbre en choisissant
l’attribut GSV partant:
3 2
E (GSVpar tan t ) = I (C1 ) + I (C 2 )
5 5
3 2
= (0,918) + (0)
5 5
= 0,551
Le gain d’information en choisissant GSV partant est donc :
gain(GSVpar tan t ) = I (Table) − E (GSVpar tan t )
= 0,722 − 0,551
= 0,171
Autre Équipe
L'attribut Autre Équipe sépare les exemples en échantillons:
C1 = 2, 7, 9
C2 = 5, 8
Pour C1 on a: P(G) = 1/3 et P(¬G) = 2/3. Donc,
1 1 2 2
I (C1 ) = − log 2 − log 2
3 3 3 3
1 2
= − (−1,585) − (−0,585)
3 3
= 0,918
Page 14 de 17
Pour C2 on a: P(G) = 0 et P(¬G) = 1. Donc,
I (C 2 ) = −1 log 2 (1) = 0
Ainsi, on peut calculer l’information espérée pour compléter l’arbre en choisissant
l’attribut Autre Équipe:
3 2
E ( AutreÉquipe) = I (C1 ) + I (C 2 )
5 5
3 2
= (0,918) + (0)
5 5
= 0,551
Le gain d’information en choisissant Autre Équipe est donc :
gain( AutreÉquipe) = I (Table) − E ( AutreÉquipe)
= 0,722 − 0,551
= 0,171
Les deux nœuds ont le même gain d’information, donc on peut choisir un des deux. Le
troisième nœud est donc soit GSV partant ou Autre Équipe.
Pour les 4 points bonis, les étudiants devrons ajouter le nœud suivant et dire que l’on ne
peut pas trouver l’arbre de décision, car deux exemples ont exactement la même
description, mais avec une classification différente. Il y a donc du bruit dans les données.
Page 15 de 17
Endroit
Domicile Étranger
Oui: 1, 3, 4, 6, 10 Oui: 9
Non: Non: 2, 5, 7, 8
Oui GSV partant
Oui Non
Oui:
Oui: 9
Non: 5, 7
Non: 2, 8
Autre Équipe Non
Meilleure Moins bonne
Oui: 9 Oui:
Non: 2 Non: 8
Problème! Non
Question 6 (10 points)
Construisez un réseau de neurones permettant de connaître la valeur de vérité de
l’expression suivante : (¬A ∨ B) ⇒ C. Vous devez spécifier tous les poids et toutes les
fonctions d’activation.
Réponse :
Tout d’abord, on peut modifier l’expression de la manière suivante :
(¬A ∨ B) ⇒ C
¬(¬A ∨ B) ∨ C
(A ∧ ¬B) ∨ C
Dans le réseau de neurones, toutes les fonctions d’activation sont des fonctions à étage
(Step function) avec comme borne le nombre indiqué dans le nœud. La fonction d’entrée
est tout simplement la somme des entrées.
Page 16 de 17
1
A 1,5
1
-1 1
B -0,5
1
C 0,5
Page 17 de 17