La valeur de l’attribut peut être quelconqueCiel = Ø => Aucune valeur possible< Soleil, ?, ?, Fort, ?, Idem > h = ( Ciel = Soleil ) ( Vent = Fort ) ( Prev = Idem )Exempleh = (soleil, ...
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 3Espace 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écifiqueAlgorithme 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