Chapitre 5: Les arbres de décision

A.U. 2016-2017

CHAPITRE 5

ARBRE DE DÉCISION

(DE RAIFFA)

[email protected]

II3

Université de La Manouba – ENSI – 2016/2017

Quelques rappels sur les probabilités

(cid:1) Axiomes élémentaires

(cid:1) 0 < P(A) < 1

(cid:1) P(A) = 1 événement toujours réalisé

(cid:1) P(A) = 0 événement impossible

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Événements mutuellement exclusifs

(cid:1) Les événements A et B ne peuvent se produire simultanément.

Pour tous couples (A,B) l'ensemble A* B est vide.

(cid:1) P(A ou B) = P(A + B) = P(A U B) = P(A) + P(B)

(cid:1) Exemple : probabilité d'extraire un cœur ou un carreau =

P(Cœur ou Carreau) = 0,25 + 0,25 = 0,5.

(cid:1) Généralisation P(A+B+C) = P(A)+P(B)+P(C)

(cid:1) Si 2 événements sont mutuellement exclusifs (mort-vivant)

on a P(A)+P(B) = 1 => P(A) = 1-P(B)

Événements non nécessairement exclusifs

(cid:1) Les événements peuvent se produire simultanément :

exemples « avoir un infarctus du myocarde »,

« être diabétique ».

(cid:1) P(A ou B) = P(B ou A) = P(A) + P(B) - P(A et B)

(cid:1) Ceci se déduit des relations :

(cid:1) P(A ou B) = P(A sans B) + P(B sans A) + P(A et B)

(cid:1) P (A sans B) = P(A) - P(A et B)

(cid:1) P(B sans A) = P(B) - P(A et B)

(cid:1) En conclusion

(cid:1) P(A ou B) < P(A) + P(B)

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Indépendance

(cid:1) L'événement A est dit indépendant de B si la

probabilité de voir se réaliser A ne dépend pas de la

réalisation ou de la non réalisation de B.

P(A/B) = P(A/non B) = P(A)

(cid:1) Si, et seulement si, A et B sont indépendants, on a :

P(A et B) = P(A) * P(B)

(cid:1) Exemple de phénomènes a priori indépendants : état

des pneus de la voiture et pluie.

(cid:1) Exemple de phénomènes a priori liés : état des pneus

de la voiture et accident.

Théorème de Bayes

(cid:1) Probabilité conditionnelle de A sachant B, dénotée

P(A|B) :

P(A|B) = P(A ∩ B) /P(B)

P(A ∩ B) = P(A|B) . P(B) = P(B ∩ A) = P(B|A) . P(A)

Théorème de Bayes (1)

P(A|B) =

|P(B

. A)

(

P(A)

)

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Formule des probabilités totales

Probabilités totales

Théorème de Bayes

(cid:1) En combinant l’équation du théorème de Bayes (1)

avec la formule des probabilités totales on obtient:

Théorème de Bayes (2)

Permet de réviser ses

croyances concernant

l’occurrence d’un

événement A en fonction

d’une nouvelle

information B

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Notation& signification

(cid:1) On appelle généralement:

(cid:1) P(A): probabilité a priori

(cid:1) P(A|B): probabilité a posteriori

Probabilité (Exemple)

(cid:1) Vous souhaitez lancer un nouveau produit.

(cid:1) A priori vous pensez P(marché favorable) = 0,6

(cid:1) Afin d'obtenir plus d'information vous avez commandé une

étude de marché à un cabinet de conseil que vous

connaissez bien.

(cid:1) Votre expérience passée avec ce cabinet vous permet

d'affirmer que les résultats de ses enquêtes sont fiables à

80%, c'est à dire que :

(cid:1) P(étude favorable|marché favorable) = P(EF|MF) = 0,8

(cid:1) P(étude défavorable|marché défavorable) = P(ED|MD) = 0,8

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Probabilité (Exemple)

(cid:1) Vous recevez le rapport d'étude où l'on vous

indique que le marché sera « favorable» à

votre produit. Sachant cette nouvelle

information, vous révisez vos croyances.

(cid:2) Ce qui nous intéresse c'est:

P(marché favorable/étude favorable)

soit P(MF/EF).

Probabilité (Exemple)

(cid:1) Nous ne l'avons pas, mais nous pouvons la calculer

simplement. En effet, les événements (marché favorable) et

(marché défavorable) forment une partition de l'ensemble

des événements.

(cid:1) Calculer P(EF) avec les probabilités totales:

(cid:1) P(EF) = [P(EF/MF).P(MF)+P(EF/MD).P(MD)]

= 0,8x0,6+0,2x0,4 = 0,56

(cid:1) On peut alors appliquer le théorème de Bayes et poser :

(cid:1) P(MF/EF) = P(EF/MF).P(MF) / P(EF)

(cid:1) P(MF/EF) = 0,8x0,6 / 0.56= 6/7 = 0,85

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Arbre de décision (de Raiffa)

Les arbres de décision (de hasard)

(cid:1) La représentation graphique la plus populaire des

modèles de décision

(cid:1) Proposés par Raiffa in 1968

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Introduction – Raiffa

« l'esprit de l'analyse de la décision est diviser pour régner »

(cid:1) La décomposition impliquée par cette analyse est:

l'arbre de décision (de hasard) - ADH.

(cid:1) Modéliser des séquences de décisions et d’événements.

(cid:1) Un scénario:

(cid:1) séquence de choix/ événements

(cid:1) représenté par une branche de l’arbre.

(cid:1) La modélisation par arbre décision permet

comparaison de scenarii face à un problème de décision

donnée.

Terminologie

(cid:3) Décision :

(cid:2) Une décision relève d’un choix délibéré du décideur même si

certaines conséquences sont incertaines.

(cid:3) Evénement:

(cid:2) Un événement se réalise ou ne se réalise pas en dehors du

contrôle du décideur.

Il s’impose à lui dès lors que celui-ci

s’est mis dans une situation de nature à lui faire supporter cet

événement

(cid:3) Probabilité :

(cid:2) Il peut

s’agir d’une probabilité subjective estimée par

l’expert ou objective issue d’enquête adéquate (probabilité

empirique) permettant souvent de modéliser le phénomène

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Arbre de décision

(cid:1) C’est la représentation graphique de la succession,

chronologique, de décision/événements

(cid:1) Pour que ce schéma soit cohérent il faut :

(cid:1) L’exhaustivité : Tous les événements et les décisions doivent

être déterminés y compris celle de ne rien faire

(cid:1) L’exclusivité : Les décisions et les événements s’excluent

mutuellement. Les conséquences d’un événement doivent

pouvoir être mesurées de manière non ambiguë

Arbre de décision –

composante graphique

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Arbre de décision –

composante graphique

Un arbre de décision comporte:

(cid:1) Nœud décision (cid:4) : symbolise un choix,

(cid:1) Nœud hasard (ou de chance ou de probabilité) (cid:5):

symbolise des événements pouvant survenir

Arbre de décision-

composante numérique

(cid:1) La composante numérique d’un arbre de décision

consiste à évaluer les arcs sortant des noeuds

hasard.

(cid:1) Cette évaluation se fait en utilisant les distributions

de probabilité pour formaliser le risque/

l’incertidude (cid:2) critère de décision: Utilité Esperée

(EU)

(cid:1) Stratégie retenue: Utilité Esperée Maximum (MEU)

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Arbre de décision et stratégies

(cid:1) Résoudre un arbre de décision corresponds à

construire une startégie

(cid:1) Une stratégie : un ensemble de règles de décision

Principe de la méthode

Identifier l’ensemble des choix possibles face à des

événements

2) Disposer d’un critère de décision pour le partage

entre les décisions alternatives

3) Représenter l’enchaînement des décisions et

événements sous forme d’un graphe logique: arbre

de décision

4) Évaluer

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Exemple

(cid:1) On considère une campagne de forage pétrolier sur

une zone donnée.

(cid:1) Sur chaque site de forage potentiel de la zone, on peut

choisir de forer (ou non).

(cid:1) Selon le niveau des réserves sur chaque site, les

résultats de l’exploitation varient :

(cid:1) réserves nulles → exploitation nulle,

(cid:1) réserves limitées → exploitation faible,

(cid:1) réserves élevées → exploitation forte,

Arbre de décision correspondante

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Arbre de décision

Evaluation d’un arbre de décision

(cid:1) Règles de calcul dans un arbre de décision :

(cid:1) Des feuilles vers la racine (ROLL-BACK)

(cid:1) Si le nœud est un nœud événement (ou chance) : on

calcule une espérance (utilité ésperée)

(cid:1) Si le nœud est un nœud de décision : on conserve le

maximum

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Quelle décision on doit prendre?

(cid:1) On considère que les probabilités de chaque

état sont connues :

p(e1) = 0.43, p(e2) = 0.3 et p(e3) = 0.27

E(forer) = 0.43(400)+0.3250+0.27*-500= 112

E(ne pas forer) = 1*0 = 0

(cid:2) Décision: forer

Arbre de décision et réduction de

loterie

(cid:1) Supposons que vous devez jouer un jeu sur deux niveau.

(cid:1) Dans un premier temps, il y a 25% de chance que vous

aurez 0$ et donc 75% de chance que vous passez au

deuxième niveau du jeu. ,

(cid:1) Dans le second niveau, vous pouvez:

(cid:1) A: gagner de facon certaine $300

(cid:1) B: jouer et vous avez 80% de chance de gagner $450,

$0 sinon

1) Modéliser ce problème avec un arbre de décision

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Arbre de décision

2) Réduire cette loterie, en proposant un arbre équivalent, vous devez choisir A

ou B avant de connaitre le résultat du premier niveau.

Probabilité combinée

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Séquence de décisions

(cid:1) Plusieurs décisions s’enchaînent les unes à la suite

des autres

(cid:1) Entre deux décisions Di et Di+1, on possède de

nouvelles observations (des nœuds de chance)

Suite exemple

(cid:1) Il est possible d’effectuer un sondage sismique (coût

sondage: cs) donnant des indications sur la nature

des réserves en pétrole.

(cid:1) Les “réponses” du sondage peuvent être :

(cid:1) s1 : “bon” (réserves probablement abondantes),

(cid:1) s2 : “mauvais” (réserves probablement faibles),

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Suite exemple – Notation

(cid:1) S = {s1, s2} signaux du sondage sismique.

(cid:1) A = {a1, a2} décisions (a1: “forer”, a2 : “ne pas

forer”).

(cid:1) E = {e1, e2, e3} états de la nature

(cid:1) e1 : “beaucoup de pétrole”,

(cid:1) e2 : “peu de pétrole”,

(cid:1) e3 : “pas de pétrole”.

Suite exemple

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Attention!

(cid:1) L’information véhiculée par le sondage affecte la

décision.

(cid:1) On passe d’une information a priori sur le gisement, p(ei):

(cid:1) p(e1) = 0.43, p(e2) = 0.3 et p(e3) = 0.27

(cid:1) À une information conditionnelle sur le sondage étant

donné le gisement, p(sj|ei), i=1,2,3, j=1,2.

P(si|ej)

s1: bon

s2: mauvais

e1: beaucoup de pétrole

e2:peu de pétrole

e3: pas de pétrole

0.44

0.56

0.60

0.40

0.81

0.19

(cid:1) Quel est la probabilité que le sondage soit:

(cid:1) Bon? p(s1)

(cid:1) Mauvais? p(s2)

(cid:1) On peut calculer p(s1) et p(s2).

(cid:1) p(s1) = p(s1/e1)p(e1) + p(s1/e2)p(e2) + p(s1/e3)p(e3)

=0.44 × 0.43+0.6 ×0.3+0.81 × 0.27

= 0.59

(cid:1) p(s2) = p(s2/e1)p(e1) + p(s2/e2)p(e2) + p(s2/e3)p(e3)

= 0.56 × 0.43 + 0.40 × 0.30 + 0.19 × 0.27

= 0.41

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

0.31

0.59

P(ei|sj)

s1: bon

s2: mauvais

e1: beaucoup de pétrole

e2:peu de pétrole

e3:pas de pétrole

0.32

0.31

0.37

0.59

0.29

0.12

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Comment évaluer l’arbre?

(cid:1) On associe aux arcs issus de nœud hasard les

probabilités correspondantes.

(cid:1) On évalue l’arbre en “remontant” des feuilles à la

racine.

(cid:1) On remonte à un nœud hasard en calculant l’Espérance

Mathématique des gains (resp. Utilité espérée).

(cid:1) On remonte à un nœud décision par le maximum des

évaluations des nœuds fils.

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Forer ou ne pas forer?

112

113.48-cs

20-Cs

248-Cs

Valeur de l’information additionnelle

(cid:1) V0: Valeur espérée du gain avec information à

l’origine: l’espérance mathématique de la politique

optimale , déterminée sans information additionnelle.

(cid:1) V0= 0.27-500+0.3250+0.43*400=112

(cid:1) Va: Valeur espérée du gain avec info. additionnelle

(sans prendre en compte le cout de cette information)

(cid:1) Va: 0.5920+0.41248=11.8+101.68=113.48

(cid:1) Va-V0 est la valeur espérée de l’info. additionnelle

= 113.48-112=1.48

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Valeur espérée et aversion au risque

(cid:1) Supposons que cs = 5.

(cid:1) Sachant que la valeur de l’information est 1.48, un

décideur neutre vis-à-vis du risque ne sera pas

intéressé par le sondage.

Arbre de décision

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Exercice

Exercice (1)

(cid:1) Mouna organise un show spécial en plein air qui aura lieu le 15

Août. Les gains vont dépendre du temps qu’il fera. S’il pleut le

15 Aout alors, il y aura 20.000 $ de perte. Si c’est ensoleillée

le 15 Août , le spectacle va rapporter 15.000 $.

Historiquement, la probabilité qu'il pleut mi- Août est de 27% .

(cid:1) Supposons que aujourd'hui, on est le 31 Juillet . Mouna a la

possibilité d'annuler le spectacle à la fin de cette journée de

31 Juillet , mais si elle le fait , elle perdra alors le dépôt de

1000 $ fait sur les installations .

a) Quelle est la stratégie de décision optimale de Mouna?

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Stratégie optimale

Travail pratique(1) - Suite

(cid:1) Supposons que Mouna peut aussi annuler le spectacle le

14 Août , mais si elle attend jusqu’à là pour le faire,

elle doit payer une redevance de 10000 $ .

L'avantage d'attendre jusqu'au 14 Août , c'est qu'elle

peut écouter les prévisions météo pour le lendemain sur

la station de nouvelles locales. Selon les registres de la

station , le temps était prévu pour être ensoleillé à la mi

Août à 90% des cas selon les statistiques des années

précédentes. Aussi, quand le temps était prévu pour

être ensoleillé, il s'est avéré ensoleillé 80 % du temps .

Quand le temps était prévu pluvieux, il s'est avéré être

pluvieux 90 % du temps . Quelle est la stratégie de

décision optimale de Mouna dans ce cas ?

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Stratégie optimale

Exercice(2)

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Arbre de décision correspondante

évaluation

Tester, ne pas forer s’il se révèle qu’il n’y a pas de structure (ns), sinon de forer.

(cid:2) Le profit espéré avec cette stratégie est de 22500$

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

Exercice

(Examen Session principale 2013-2014)

II3 - ENSI

Chapitre 5: Les arbres de décision

A.U. 2016-2017

(cid:1) La stratégie optimale est :

(cid:1) Si le prix de l’étude est

supérieure à 38, alors ne

pas l’acheter et choisir de

cultiver une moyenne

surface.

(cid:1) Si le prix de l’étude

statistique est supérieure à

38, alors l’acheter et

cultiver une grande surface

si l’étude annonce une

demande croissante, sinon

cultiver une surface

moyenne.

II3 - ENSI