//img.uscri.be/pth/751c4afe7df2a52840c080fb0ae348405f58281d
La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

AA-Cours

De
16 pages
La valeur de l’attribut peut être quelconqueCiel = Ø => Aucune valeur possible< Soleil, ?, ?, Fort, ?, Idem > h = ( Ciel = Soleil ) ( Vent = Fort ) ( Prev = Idem )Exempleh = (soleil, ...
Voir plus Voir moins
La valeur de l’attribut peut être quelconque Ciel = Ø => Aucune valeur possible < Soleil, ?, ?, Fort, ?, Idem > h = ( Ciel = Soleil ) ( Vent = Fort ) ( Prev = Idem ) Exemple h = (soleil, froide, norm., fort, froide, change)1 couv(h ) = contient un seul ex.1 h2 = (soleil, ?, norm., fort, ? change) couv(h ) = tous les exemples tels que2 Ciel = soleil Humide = norm. Vent = fort Prev = change e = (soleil, froide, norm., fort, chaude, change) couv(h )2 e’ = (soleil, froide, norm., fort, froide, c )2 ≤ induit un ordre partiel sur l’ensemble des hypothèses h = (Soleil, ?, norm., fort, chaude, idem) h’ = (?, chaude, norm., fort, c h et h’ sont non comparables h” = (Soleil, ?, norm., fort, chaude, change) h et h” sont non comparables Remarque Si on exprime les hypothèses par des conjonctions de littéraux, on passe de h à une hypo- thèse plus générale que h en effaçant un ou plusieurs littéraux dans h. h = ( Ciel = soleil ) ( Vent = fort ) ( Eau = chaude ) h ≤ h’ = ( Ciel = soleil ) ( Vent = fort ) M1 Info 2005 / 2006 — Université d’Angers — Apprentissage artificiel 2 ƒ “ “ ƒ ƒ ‰ Généralisation, spécialisation L’espace des hypothèses est borné par : l’hypothèse la plus générale ( ? , ? , ? , ? , ? , ? ) ?• ( toute instance vérifie le concept ) l’hypothèse la plus spécifique ( Ø , Ø , Ø , Ø , Ø , Ø ) Ø• ( aucune instance ne vérifie le concept ) < ? , ? , ? , ? , ? , ? > < soleil , ? , ? , ? , ? , ? > < ? , chaude , ? , ? , ? , ? > < pluie , ? , ? , ? , ? , ? > … < soleil , chaude , ? , ? , ? , ? > … … … < soleil , chaude , norm. , fort , chaude , idem > … … Ø Déroulement de Gen_Spec sur l’ensemble D des 4 exemples Initialisation• h = ( Ø , Ø , Ø , Ø , Ø , Ø )0 On considère e• 1 h = ( soleil, chaude, norm., fort, chaude, idem ) 1• 2 hhaude, ? , fort, chaude, idem ) 2 e négatif n’est pas pris en compte,• 3 on considère e4 h = ( soleil, chaude, ? , fort, ? , ? ) 3 On retourne h• 3 Avec cet algorithme, la définition pour le concept Sport est : ( Ciel = soleil ) ( Temp = chaude ) ( Vent = fort ) Est-ce que ( Ciel = soleil ) ( Temp. = chaude ) est aussi une définition possible ? On a bien h’(x) = c(x) pour tout x D M1 Info 2005 / 2006 — Université d’Angers — Apprentissage artificiel 3 Espace des versions — cf. page 12 Incohérence dans les données : un même exemple représenté deux fois, étiqueté + et - X – – h retournée par Gen_Spec – + –+ + Le concept cherché ( ) peut être plus général – que l'hypothèse retournée par Gen_Spec– Cette propriété sera admise dans ce cours. S : Hypothèses consistantes avec les exemples de D et qui ne peuvent pas être spécialisées en une hypothèse consistante avec les exemples de D G : vec tous les exemples de D et qui ne peuvent pas être géné- ralisées en une hvec D. Exemple hypothèse non consistante avec D car ne couvre pas e +2 + spécifique < soleil , chaude , norm. , fort , ? , ? > S: { < soleil , chaude , ? , fort , ? , ? > } < soleil , ? , ? , fort , ? , ? > < soleil , chaude , ? , ? , ? , ? > < ? , chaude , ? , fort , ? , ? > G: { < soleil , ? , ? , ? , ? , ? > , < ? , chaude , ? , ? , ? , ? > } + général < ? , ? , ? , ? , ? , ? > hypothèse non consistante avec D car couvre e –3 M1 Info 2005 / 2006 — Université d’Angers — Apprentissage artificiel 4 + spécifique Algorithme d’élimination des candidats — cf. page 13 et 14 Initialisation S = { < Ø , Ø , Ø , Ø , Ø , Ø > }0 G = { < ? , ? , ? , ? , ? , ? > }0 Ex1 = < soleil, chaude, normale, fort, chaude, idem > + S0 ↓ S = { < soleil, chaude, normale, fort, chaude, idem > }1 G = G = { < ? , ? , ? , ? , ? , ? > }1 0 Ex2 = < soleil, chaude, élevée, fort, chaude, idem > + S = { < soleil, chaude, normale, fort, chaude, idem > }1 ↓ Shaude, ? , fort, c2 G = G = { < ? , ? , ? , ? , ? , ? > } 2 1 Ex3 = < pluie, froide, élevée, fort, chaude, change > – S = S = { < soleil, chaude, ? , fort, chaude, idem > }3 2 G = { < soleil , ? , ? , ?, ? , ? > , < ? , chaude , ? , ? , ? , ? > , < ? , ? , ? , ? , ? , idem > }3 ↑ G = { < ? , ? , ? , ? , ? , ? > }2 Ex4 = < soleil, chaude, élevée, fort, froide, change > + S = { < soleil, chaude, ? , fort, chaude, idem > }3 ↓ S = { < soleil, chaude, ? , fort, ? , ? >4 G = { < soleil , ? , ? , ?, ? , ? > , < ? , chaude , ? , ? , ? , ? > }4 ↑ Ghaude , ? , ? , ? , ? > , < ? , ? , ? , ? , ? , idem > }3 Remarques VS définit les hypothèses de H consistantes avec D.VS peut contenir une seule hypothèse H,D ou plusieurs hypothèses (concept partiellement appris). Comment se servir de VS ? On veut utiliser VS pour la prise de décision, c’est-à-dire pour décider si un nouvel exemple vérifie le concept ou non. Par exemple, la situation météo < soleil, chaude, normal, fort, froide, change > est-elle favorable pour faire du sport ? Cet exemple est classé + par les 6 hy- pothèses de VS donc oui, c’est une situation favorable pour faire du sport. Par contre, la situa- tion météo < pluie, froide, normal, faible, chaude, idem > est classé – par les 6 hypothèses de VS donc est non favorable. Enfin, pour l’exemple < soleil, chaude, normal, faible, chaude, idem >, il y a 3 hypothèses de VS qui le classe + et 3 hypothèses de VS qui le classe – donc il sera difficile de prendre une décision. Si cet exemple est le prochain exemple dans D alors la M1 Info 2005 / 2006 — Université d’Angers — Apprentissage artificiel 5 Très froid • 2 < Temp ≤ 8 -> Froid • 8 < Temp ≤ 16 -> Doux • 16 < Temp ≤ 33 -> Chaud L’algorithme des arbres de décision peut traiter directement et dynamiquement les valeurs numériques. Si A est un attribut à valeurs continues Tre [8,25] 11° 8 -> OUI 18° 11 -> OUI 15° 15 -> NON 8° 18 -> 19° 19 -> OUI 25° 25 -> OUI 2 seuils potentiels : s1 = 13 et s2 = 18,5 Ts1 Ts2 Tre < 13 Tre > 13 Tre < 18,5 Tre > 18,5 2 attributs binaires potentiels que l’on attribue comme les autres avec le gain d’entropie. M1 Info 2005 / 2006 — Université d’Angers — Apprentissage artificiel 8 Arbre profond Un arbre surajusté est un arbre profond qui a des feuilles pures (ou presque) mais ces feuilles concernent peu d’exemples. 2000 ex. 2000 ex. 23+Décision 5– 9+ 1– 9+ 1– Pour évaluer la qualité de l’arbre en prédiction, on peut évaluer l’arbre sur un autre jeu de données étiquetées (données pour lesquelles la classe est connue) on applique l'algo de un arbreEA = D construction de l'arbre sur EA de décisionDonnées initiales on applique A pour prédire la classe de chaqueET exemple de ET et on compare à la classe connue SurapprentissageEA Précision 61% Taux de bonnes réponse Taille de l'arbre (nombre de nœuds) Le gain d’entropie est toujours > 0 donc l’algorithme considérera toujours que le choix d’un attribut supplémentaire pour continuer la construction l’arbre est pertinent. On peut donc imaginer de calculer une autre mesure pour évaluer si l’attribut que l’on considère est en lien corrélé avec la classe. M1 Info 2005 / 2006 — Université d’Angers — Apprentissage artificiel 9 Apprentissage de règles On s’intéresse dans ce chapitre à apprendre la définition d’un concept à parti d’exemple po- sitifs et négatifs. On cherche ici à apprendre un ensemble de règles qui définissent le concept. Chaque règles est une formule conjonctive : A ∧ A ∧…∧ A → Concept 1 2 n La notion de couverture du monde clos Cette notion a été définie dans le premier chapitre (espace des versions). La couverture d’une hypothèse est l’ensemble des exemples qui satisfont cette hypothèse. La forme des hypothèses cherchées ici est de la forme : Att = Valeur∧ Att'= Valeur'∧…→ Concept = OUI( ) Conjonction de littéraux de la forme Att = Valeur Un exemple est couvert par une telle hypothèse s’il vérifie la conjonction de littéraux qui forme la partie prémisse de la règle. Couverture séquentielle Une règle de bonne précision = une règle qui ne commet pas (ou peu) d’erreurs, c’est à dire qui ne couvre pas d’exemples négatifs. De couverture quelconque : la règle couvre un certain nombre d’exemples positifs mais pas forcément un grand nombre. 2ème règle 1ère règle – + + + + – – –+– + – –++ – 2ème règle Cette algorithme est facile à mettre en œuvre car il ramène le problème de l’apprentissage au problème de l’apprentissage d’une seule règle. La recherche d’une règle se fait par une exploration des règles possibles du plus général au plus spécifique. La règle la plus générale que l’on peut envisagée est : → Concept Aucune condition M1 Info 2005 / 2006 — Université d’Angers — Apprentissage artificiel 10