Remerciez-le!

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

Apprendre un arbre de décision M1 informatique 2018–2019 Intelligence Artiﬁciel

Apprendre un arbre de décision M1 informatique 2018–2019 Intelligence Artiﬁcielle Stéphane Airiau LAMSADE M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 1 Retour sur l’apprentissage supervisé on a des données (ensemble d’apprentissage) on peut les voir comme des couples (attribut, valeur) autrement dit : un table où chaque colonne correspond à un attribut, ligne est une observation à chaque observation, on a une étiquette hypothèse : il existe un fonction "objectif" f : observation 7→étiquette mais on ne connait pas cette fonction, on connait juste un nombre d’observations et d’étiquettes associées. But : trouver une fonction h qui approxime f étant donné notre ensemble d’appentissage simpliﬁcation par rapport à l’apprentissage "humain" on n’utilise aucune connaissance existente on fait l’hypothèse qu’on a accès aux données on fait l’hypothèse qu’on a des exemples qui sont donnés on fait l’hypothèse qu’on veut apprendre f (pourquoi ?) M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 2 Exemple : ajustement de courbe x f(x) les données sont les valeurs des abscisses les étiquettes sont les valeurs des ordonnées but : trouver une fonction qui pour n’importe quelle abscisse donne "la bonne" ordonnée M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 3 Exemple : ajustement de courbe x f(x) hypothèse la plus simple : une droite il y a quelques observations qui sont "loin" de notre fonction erreur dans les données ? mauvaise hypothèse ? M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 4 Exemple : ajustement de courbe x f(x) hypothèse simple : un polynôme de degré 2 plus d’observations sont mieux (ou parfaitement) traitées. il reste une observation qui n’est pas bien traitée M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 5 Exemple : ajustement de courbe x f(x) hypothèse un peu moins simple : un polynôme toutes les observations sont traitées correctement est-ce qu’on a bien appris ? M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 6 Exemple : ajustement de courbe x f(x) hypothèse farfelue ? toutes les observations sont traitées correctement M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 7 Exemple : ajustement de courbe x f(x) hypothèse farfelue ? toutes les observations sont traitées correctement Avec ces données, on ne peut pas dire quelle est la meilleure réponse ! M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 8 Exemple : ajustement de courbe x f(x) hypothèse farfelue ? toutes les observations sont traitées correctement Avec ces données, on ne peut pas dire quelle est la meilleure réponse ! Principe d’Ockham : on préfère l’hypothèse la plus simple qui reste a peu près cohérente avec les données. M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 9 Les données Les observations sont des couples (attribut, valeur). L’étiquette est un booléen (on peut parler de classiﬁcation) Exemple : vais-je attendre pour avoir une table dans un restaurant Example Attributes Target Alt Bar Fri Hun Pat Price Rain Res Type Est WillWait X1 T F F T Some $$$ F T French 0–10 T X2 T F F T Full $ F F Thai 30–60 F X3 F T F F Some $ F F Burger 0–10 T X4 T F T T Full $ F F Thai 10–30 T X5 T F T F Full $$$ F T French >60 F X6 F T F T Some $$ T T Italian 0–10 T X7 F T F F None $ T F Burger 0–10 F X8 F F F T Some $$ T T Thai 0–10 T X9 F T T F Full $ T F Burger >60 F X10 T T T T Full $$$ F T Italian 10–30 F X11 F F F F None $ F F Thai 0–10 F X12 T T T T Full $ F F Burger 30–60 T Alt : est-ce qu’il y a d’autres alternatives dans les parages ? Bar : est-ce qu’il y a une section bar pour attendre. Fri : est-ce que c’est vendredi ? Hun est-ce que j’ai très faim ? Pat est-ce qu’il y a beaucoup de monde ? Price niveau de prix ? Rain pleut-il ? Res Type quel est le type de cuisine ? Est estimation d’attente M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 10 Arbre de décision La vraie fonction de décision est représentée par un arbre : No Yes No Yes No Yes No Yes No Yes No Yes None Some Full >60 30−60 10−30 0−10 No Yes Alternate? Hungry? Reservation? Bar? Raining? Alternate? Patrons? Fri/Sat? WaitEstimate? F T F T T T F T T F T T F Quelle est ma décision s’il y a beaucoup de monde, que j’ai faim, qu’il y a d’autres possibilités et qu’il ne pleut pas ? Certains attributs ne sont pas présents dans l’arbre Dans ce cas, on sait qu’on peut représenter notre décision par un arbre de décisions M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 11 Expressivité Les arbres de décisions peuvent représenter n’importe quelle fonction entre les entrées et la sortie ! c’est trivial : il y a toujours un arbre cohérent avec les données (pour une fonction f déterministe en x) pour chaque observation, on aura un nouveau chemin le nombre de feuilles est égal au nombre d’observations ´ ces arbres ne vont pas forcément bien se généraliser à de nouvelles observations Principe d’Okham : on va préférer des arbres de décisions plus compacts M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 12 Espace des arbres Combien d’arbres de décisions peut-on construire avec n attributs booléens M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 13 Espace des arbres Combien d’arbres de décisions peut-on construire avec n attributs booléens c’est le nombre de fonctions booléennes c’est le nombre de table de vérités avec 2n lignes ´ 22n pour 6 attributs booléen, cela donne 18,446,744,073,709,551,616 arbres ! M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 14 Espace des arbres Combien d’arbres de décisions peut-on construire avec n attributs booléens c’est le nombre de fonctions booléennes c’est le nombre de table de vérités avec 2n lignes ´ 22n pour 6 attributs booléen, cela donne 18,446,744,073,709,551,616 arbres ! Quelle est le nombre de formules contenant au plus une fois chaque attributs et les symboles ∧(et logique) et ¬ (négation) ? représentation a priori moins riche (plus de contraintes du langage) M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 15 Espace des arbres Combien d’arbres de décisions peut-on construire avec n attributs booléens c’est le nombre de fonctions booléennes c’est le nombre de table de vérités avec 2n lignes ´ 22n pour 6 attributs booléen, cela donne 18,446,744,073,709,551,616 arbres ! Quelle est le nombre de formules contenant au plus une fois chaque attributs et les symboles ∧(et logique) et ¬ (négation) ? représentation a priori moins riche (plus de contraintes du langage) chaque attribut est positif / négatif / absent ´ 3n différentes expressions M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 16 Espace des arbres Combien d’arbres de décisions peut-on construire avec n attributs booléens c’est le nombre de fonctions booléennes c’est le nombre de table de vérités avec 2n lignes ´ 22n pour 6 attributs booléen, cela donne 18,446,744,073,709,551,616 arbres ! Quelle est le nombre de formules contenant au plus une fois chaque attributs et les symboles ∧(et logique) et ¬ (négation) ? représentation a priori moins riche (plus de contraintes du langage) chaque attribut est positif / négatif / absent ´ 3n différentes expressions plus notre représentation est expressive plus on a de chance que notre problème puisse être représenté plus le nombre de représentations cohérentes possibles est grand ´ on aura peut être de moins bonnes prédictions ! ´ il faut trouver un bon compromis M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 17 Apprendre un arbre de décision Fonction apprendAD(exemples, attributs, défaut) 1 Si observations est vide alors retourne défaut 2 sinon si tous les exemples ont la même classification 3 alors retourne la classification 4 sinon si attributs est vide alors retourne 5 sinon 6 bestAtt ←choisi-attribut(attributs, observations) 7 arbre ←nouvel arbre de décision dont la racine est bestAtt 8 pour chaque valeur vi de l’attribut bestAtt do 9 exemplei ←{ éléments d’observations donc bestAtt = vi} 10 sousArbre ←apprendAD(exemplesi, attributs \ {bestAtt }, défaut) 11 ajoute une branche à arbre avec étiquette vi et sous arbre sousArbre 12 retourne arbre 13 M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 18 Choisir un attribut Qu’est-ce qu’un bon attribut ? M1 informatique 2018–2019 Intelligence Artiﬁcielle– (Stéphane Airiau) Apprendre un arbre de décision 19 Choisir un attribut Qu’est-ce qu’un bon attribut ? idéalement, la valeur d’un bon attribut sépare toutes les observations po- uploads/Science et Technologie/ ia-10-dt.pdf