Apprentissage superviséà partir de séquences

DEA Génomique et Informatique

année 2000-2001

Francois.Coste@irisa.fr

Apprentissage par inductionApprentissage d'un concept C à partir

d'exemples (instances) appartenant au concept

• Choix de la description des exemples ?

• Choix de la description des hypothèses ?

• Apprentissage réussi ?

Apprentissagex1, …,xn

échantillon d’apprentissage X H C

hypothèse

Exemple 1

Apprentissage de l’arbre de décision « sortie en mer »

météo Skipper Décisioncalme amateur mertempête amateur terre agitée expérimenté mertempête expérimenté terreagitée amateur terre

Échantillon d’apprentissage Arbre de décision

météo = tempête

terreskipper = amateur

météo = agitée

terre

mer

mer

Apprentissage

Oui

Oui

Oui

Non

Non

Non

Apprentissage de classificationsConcept = fonction de classification c

• Objets à classer O = {o1,o2,…},

• Langage de description D = {d1,d2,…}

• Ensemble de classes [1,C]

Classification c : O [1,C] ( O [1,C])

Exemples = <description, classe> Apprentissage x1 , … , xn

<d1,c1> <dn,cn> h c

c

d

h

Remarques • Apprentissage « supervisé » : on connaît le

nombre de classes et la classe des exemples( clustering, cf. cours I.C. Lerman)

• Cas C = 2 (classes = [1,2]) : discrimination d’objets appartenant à la classe 1 / ceux qui n’y appartiennent pas ( dans classe 2). Apprentissage d’un concept à partir d’exemples et de contre-exemples. On notera = {+,-}

« exemples positifs, exemples négatifs »

Description des objets

• Ensemble d'attributs d = (a1, …, an)

– dans R (apprentissage numérique)– discrets (apprentissage symbolique)

• booléens

• Séquence sur un alphabet, etc...

Devrait permettre discrimination des exemplesc(o1) c(o2) d(o1) d(o2)

mais aussi un apprentissage "efficace"

Mixtes

Description des hypothèses

• Choix du type de fonctions considéré Espace d'hypothèse

• Espace d'hypothèse grand Favorise existence de h=c Plus difficile à explorer pour trouver la

(meilleure) solution

Espaces de description

Programme d'apprentissage cherche la "meilleure" solution dans l'espace d'hypothèses

par rapport à l'échantillon d'apprentissage

+++

+

+h

Espace de représentation Espace d’hypothèses

--

---

-

-- -

D H

Erreurs de classification

• Erreur de classification de h pour d :E(d) = P(c(o) h(d) / d(o) = d)

• Erreur de classification de h (à minimiser)E(h) = d D E(d) P(d(o) = d)

• Taux d’erreur apparent (sur l’échantillon)

Eapp (h) = err / n

n : nombre d’exempleserr : nombre d’erreurs de classification par H sur les exemples

E(h) = lim n Eapp(h)

Bien classer et bien prédire

• Minimisation Eapp Sur-spécialisation / X

Exple : Apprentissage par cœur, Eapp = 0Apprentissage ou mémorisation ?

Pouvoir prédictif ?!?

• But : au moins une meilleure prédiction que laRègle de la classification majoritaire

Critère de simplicité

• Rasoir d’Occam : Favoriser les hypothèses les plus

simples

• Minimum Description Length (MDL)hMDL = argmin hH L1(h)+L2(X/h)

(Minimiser longueur du codage de h et de ses exceptions)

Evaluation par ensemble de testNe pas utiliser les mêmes exemples pour apprendre

et pour évaluer la qualité du résultat !• Échantillon fourni divisé en échantillon d’apprentissage

et échantillon de test (Rapports usuels : 1/2,1/2 ou 2/3,1/3)

• Validation croisée– partition de X en p sous-ensembles

– p apprentissages sur p-1 sous-ensembles, test sur le sous-ensemble restant

• Bootstrap– Tirage avec remise de n exemples : ensemble d’apprentissage

– Test sur X

Apprentissage d’arbre de décision

Inférence grammaticale

Apprentissage de modèles probabilistes

Exemple 2

Apprendre concept « gens aisés » (revenu > moyenne)

• Objets à classer O : population française

• Description D : {répondeur, répondeur}

• Classes : {aisé, aisé}• Echantillon représentatif

40% pop. est aisée80% pop aisée a un répondeur, sinon seulement 45%

Classe k aisé aisé

P(k) 0,4 0,6

P(répondeur/k) 0,8 0,45

Règles de classification

• Majoritaireo, hmaj (o) = aisé

• Maximum de vraisemblancechoix de la classe pour laquelle la description est la plus probableargmax k[1,C] P(d/k)

hmaxv (répondeur) = aisé ; hmaxv (répondeur) = aisé

Pb : classification en {Télécom, Médecin, Ouvrier} avec P(répondeur/Télécom) = 1

hmaxv (répondeur) = Télécom

Classe k aisé aisé

P(k) 0,4 0,6

P(répondeur/k) 0,8 0,45

Règles de classification

• Bayesclasse de probabilité maximale pour la description

argmax k[1,C] P(k/d) = argmax k[1,C] P(d/k) P(k)

Rappel formule de Bayes P(k/d) =

P(répondeur/aisé) P(aisé) = 0,80,4 = 0,32P(répondeur/aisé) P(aisé) = 0,450,6 = 0,27P(répondeur/aisé) P(aisé) = 0,20,4 = 0,08P(répondeur/aisé) P(aisé) = 0,550,6 = 0,33

Nécessite connaissance de P(d/k) et P(k) !...

Classe k aisé aisé

P(k) 0,4 0,6

P(répondeur/k) 0,8 0,45

P(d/k) P(k)

P(d) indépendant de k

hBayes (répondeur) = aisé

hBayes (répondeur) = aisé

Propriétés du classificateur de BayesCBayes(d) = argmax k[1,C] P(k/d)

= argmax k[1,C] P(d/k) P(k)

• Si E(CBayes) = 0 alors c(o1) c(o2) d(o1) d(o2)(problème déterministe)

• Classification d’erreur minimale

h, E(CBayes) E(h) E(Majoritaire)

Mais nécessite connaissance de P(d/k) et P(k) !

Classificateur naïf de BayesApproximation de P(d/k) et P(k) inconnus

si D = A1 A2 ... Am

CBayes(d) = argmax k[1,C] P(<a1, ... , am>/k) P(k)

si valeurs des attributs indépendantes sachant k (!) P(<a1, ... , am>/k) = i[1,m] P(di/k)

alors en notant P(di/k) l'estimation de P(di/k) (proportion d'objets de classe k, ayant comme ième attribut di)

Hypothèses « fausses », mais bons résultats en pratique...

CNaiveBayes(d) = argmax k[1,C] i[1,m] P(di/k) P(k)^ ^

^

Apprentissage de HMM