AA-Cours

Julien Chauveau

Informations

• Publié par: Utto
• Nombre de lectures: 13
• Langue: Français

Extrait

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