Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Rech. Intell. et Coop´ eration Apprentissage de r` egles et arbres de d´ ecisio

Rech. Intell. et Coop´ eration Apprentissage de r` egles et arbres de d´ ecision M2 IA&RF / IRR Sept.-Nov. 2015 Introduction Un agent dans une certaine situation / un certain ´ etat s doit prendre une d´ ecision • plusieurs d´ ecision possibles, quelle est la ( ( bonne ) ) ? • d´ epend de l’´ etat / de la situation Introduction : Exemples Un joueur artiﬁciel pour un jeu video ⇒Que faire du ballon ? (Passe, tir, dribble . . . ) D´ epends de la position du joueur sur le terrain, des positions de ses adversaires. . . 2D Simulation Leage – Robocup Introduction : Exemples Un banquier devant d´ ecider d’accorder ou non un prˆ et ⇒d´ epends du demandeur : ˆ age, profession, statut marital, biens immobiliers, salaire, montant du prˆ et, . . . Introduction : Exemples Un banquier devant d´ ecider d’accorder ou non un prˆ et ⇒d´ epends du demandeur : ˆ age, profession, statut marital, biens immobiliers, salaire, montant du prˆ et, . . . Un m´ edecin devant poser un diagnostique ⇒d´ epend du r´ esultats d’observations / tests / examens : ﬁ` evre, douleur, toux, rhinorrh´ ee, . . . Introduction • D´ ecision complexes : d´ ependent de nombreux facteurs • Comment repr´ esenter le mod` ele de d´ ecision ? on veut un mod` ele compr´ ehensible / interpr´ etable par un humain ⇒r` egles / arbres de d´ ecision • Comment apprendre automatiquement le mod` ele de d´ ecisio R` egles et arbres de d´ ecision • Situations / ´ etats d´ ecrits par n attributs X1, X2, . . . , Xn • pour chaque attribut Xi : Xi = dom(Xi) = ensemble des valeurs possibles pour Xi ⇒l’ensemble des situations / ´ etats possibles est S = Y Xi∈X dom(Xi) • un ensemble de d´ ecisions / classes possibles Y = {y1, . . .} • on veut repr´ esenter / apprendre une fonction c : S − →Y R` egles et arbres de d´ ecision : R` egles conjonctives De la forme si Xi1 = v1 et Xi2 = v2 et . . . Xik = vk alors yj Par exemple: R` egles et arbres de d´ ecision : R` egles conjonctives De la forme si Xi1 = v1 et Xi2 = v2 et . . . Xik = vk alors yj Par exemple: si position = devant but ∧pos gardien = a droite ∧. . . alors tirer a gauche R` egles et arbres de d´ ecision : R` egles conjonctives De la forme si Xi1 = v1 et Xi2 = v2 et . . . Xik = vk alors yj Par exemple: si position = devant but ∧pos gardien = a droite ∧. . . alors tirer a gauche si age ≤40 ∧proprietaire = oui ∧. . . alors pret ok R` egles et arbres de d´ ecision : R` egles conjonctives De la forme si Xi1 = v1 et Xi2 = v2 et . . . Xik = vk alors yj Par exemple: si position = devant but ∧pos gardien = a droite ∧. . . alors tirer a gauche si age ≤40 ∧proprietaire = oui ∧. . . alors pret ok Mais: • si age > 40 ? • si pos gardien ̸= a gauche ? ⇒une seule r` egle ne suﬃt pas R` egles et arbres de d´ ecision : Arbres Un arbre de d´ ecision pour X1, . . . , Xn est un arbre dont : • chaque nœud interne est ´ etiquet´ e par un test portant sur un ou plusieurs attributs; • les arˆ etes sous les ﬁls d’un nœud interne donn´ e sont ´ etiquet´ e par des r´ eponses possibles mutuellement exclusives au test port´ e par ce nœud; • les feuilles sont ´ etiquet´ ees par des d´ ecisions / classes de Y. R` egles et arbres de d´ ecision : Arbres Un arbre de d´ ecision pour X1, . . . , Xn est un arbre dont : • chaque nœud interne est ´ etiquet´ e par un test portant sur un ou plusieurs attributs; • les arˆ etes sous les ﬁls d’un nœud interne donn´ e sont ´ etiquet´ e par des r´ eponses possibles mutuellement exclusives au test port´ e par ce nœud; • les feuilles sont ´ etiquet´ ees par des d´ ecisions / classes de Y. Un arbre de d´ ecision A repr´ esente une fonction hA : S →Y, d´ eﬁnie de la mani` ere suivante : pour x ∈S, s’il existe une branche de l’arbre dont x v´ eriﬁe toutes les conditions, alors hA(x) est la valeur port´ ee par la feuille correspondante. R` egles et arbres de d´ ecision : Arbres Un arbre de d´ ecision pour X1, . . . , Xn est un arbre dont : • chaque nœud interne est ´ etiquet´ e par un test portant sur un ou plusieurs attributs; • les arˆ etes sous les ﬁls d’un nœud interne donn´ e sont ´ etiquet´ e par des r´ eponses possibles mutuellement exclusives au test port´ e par ce nœud; • les feuilles sont ´ etiquet´ ees par des d´ ecisions / classes de Y. Un arbre de d´ ecision A repr´ esente une fonction hA : S →Y, d´ eﬁnie de la mani` ere suivante : pour x ∈S, s’il existe une branche de l’arbre dont x v´ eriﬁe toutes les conditions, alors hA(x) est la valeur port´ ee par la feuille correspondante. Int´ erˆ et des arbres de d´ ecision: facile ` a lire / interpr´ eter ; repr´ esentation compacte R` egles et arbres de d´ ecision : Arbres revue −bancaire.fr– 28 Octobre 2014 R` egles et arbres de d´ ecision : Arbres allergies.org– 15 Septembre 2015 R` egles et arbres de d´ ecision : Arbres Propri´ et´ es • ` A chaque branche d’un arbre de d´ ecision correspond une r` egle conjonctive. ⇒on peut traduire un arbre en un ensemble de r` egles • Toute fonction S − →Y peut ˆ etre repr´ esent´ ee par un / plusieurs arbre(s) de d´ ecision au pire, une branche par ´ etat / situation ⇒taille potentiellement exponentielle Apprentissage supervis´ e Plutˆ ot que demander ` a un expert de construire l’enemble de r` egles ou l’arbre de d´ ecision, on peut : • lui demander la bonne d´ ecision dans certaines situations • induire un arbre / un ensemble de r` egles Apprentissage supervis´ e Plutˆ ot que demander ` a un expert de construire l’enemble de r` egles ou l’arbre de d´ ecision, on peut : • lui demander la bonne d´ ecision dans certaines situations • induire un arbre / un ensemble de r` egles On appelle exemple une paire (x, y) ∈S × Y : • x repr´ esente un ´ etat / une situation ; • y est la d´ ecision correspondante Apprentissage supervis´ e Plutˆ ot que demander ` a un expert de construire l’enemble de r` egles ou l’arbre de d´ ecision, on peut : • lui demander la bonne d´ ecision dans certaines situations • induire un arbre / un ensemble de r` egles On appelle exemple une paire (x, y) ∈S × Y : • x repr´ esente un ´ etat / une situation ; • y est la d´ ecision correspondante ´ Etant donn´ e un ensemble E d’exemples, on cherche h : S − →Y telle que y = h(x) pour tout (x, y) ∈E. Apprentissage supervis´ e : Une r` egle Pour la suite, on distingue une valeur y0 ∈Y ; pour simpliﬁer la pr´ esentation, on note y0 = +1. ⇒on cherche ` a apprendre des r` egles de la forme si Xi1 = v1 et Xi2 = v2 et . . . Xik = vk alors +1 qui permettront de pr´ edire si c(x) = +1 ou c(x) ̸= +1. Apprentissage supervis´ e : Une r` egle Notations et terminologie : • Pour une r` egle r = ( ( si Xi1 =v1 et Xi2 =v2 et . . . Xik =vk alors +1 ) ) on note : Cond(r) = ( ( Xi1 =v1 et Xi2 =v2 et . . . Xik =vk ) ) • Un exemple (x, y) ∈E est: positif si y = +1 ; n´ egatif sinon ; • La r` egle ( ( si Xi1 = v1 et Xi2 = v2 et . . . Xik = vk alors +1 ) ) couvre un exemple (x, y) si Xij(x) = vij pour j ∈1 . . . k. ´ Etant donn´ e un ensemble d’exemples E, on cherche donc ` a calculer une r` egle qui : • couvre autant d’exemples positifs que possible ; et • couvre aussi peu d’exemples n´ egatifs que possible. Apprentissage supervis´ e : Une r` egle Principe : • On part de la r` egle trivial ( ( Si vrai uploads/Sports/ ap-regles-diapos 1 .pdf