View
109
Download
1
Category
Preview:
Citation preview
EGC-03.
Apprentissage supervisé Apprentissage supervisé et non supervisé et non supervisé
sur les sur les données INDANAdonnées INDANA
A. Cornuéjols (LRI)
Éric Bréchemier, Claire Lequeux
Matthieu Manceny & Natanel Sadres (CNAM-IIE)
INDANA (rapport AC) 10/03/03 2/34 © Antoine Cornuéjols
Apprentissage supervisé avec ré-équilibrageApprentissage supervisé avec ré-équilibrage
Utilisation de différents algorithmes d’apprentissage supervisé disponibles sur Weka
J48.48 (arbre de décision)
PMC (Perceptron Multi-Couche)
SVM
Boosting (sauf sur PMC)
Avec techniques de ré-équilibrage des classes event / ¬event Par matrice de coûts
Par bruitage des données event
INDANA (rapport AC) 10/03/03 3/34 © Antoine Cornuéjols
RésultatsRésultats (avec matrice de coûts) (avec matrice de coûts)
Utilisation de matrices de coût Option minimizeExpectedCost=False de weka
Courbe ROC-like
(0,834 %)
INDANA (rapport AC) 10/03/03 4/34 © Antoine Cornuéjols
RésultatsRésultats (avec matrice de coûts) (avec matrice de coûts)
INDANA (rapport AC) 10/03/03 5/34 © Antoine Cornuéjols
RésultatsRésultats (avec bruitage) (avec bruitage)
1ère méthode :
event¬event
bruitage, x10base d’apprentissage
Validation croisée (10 x)
Bruitage : Un seul attribut numérique
± 10 %
INDANA (rapport AC) 10/03/03 6/34 © Antoine Cornuéjols
RésultatsRésultats (avec bruitage) (avec bruitage)
INDANA (rapport AC) 10/03/03 7/34 © Antoine Cornuéjols
RésultatsRésultats (avec bruitage) (2) (avec bruitage) (2)
Même bruit
2ème méthode :
2/3 event (71)1/2 ¬event (1062)
bruitage, x15base d’apprentissage
Test sur les (1/3 event / 1/2 ¬ event) restants
INDANA (rapport AC) 10/03/03 8/34 © Antoine Cornuéjols
RésultatsRésultats (avec bruitage) (2) (avec bruitage) (2)
INDANA (rapport AC) 10/03/03 9/34 © Antoine Cornuéjols
PerspectivesPerspectives
Améliorer le bruitage Bruit gaussien
Simultanément sur plusieurs attributs
Y compris sur attributs symboliques
Avec dépendance sur la nature des attributs
Modifier le protocole …
INDANA (rapport AC) 10/03/03 10/34 © Antoine Cornuéjols
EM sur les données INDANAEM sur les données INDANA
MotivationEssayer de faire de la régression malgré l’absence d’étiquette temporelle
(deathcv) après délai seuil (~ 6 ans)
Démarche S’appuyer sur une méthode d’apprentissage semi-supervisée : EM
La développer pour le cas de la régression sans étiquette temporelle
INDANA (rapport AC) 10/03/03 11/34 © Antoine Cornuéjols
EM sur les données INDANAEM sur les données INDANA
Résultats
L’extension de EM à la régression est conçue
Mais l’obtention de résultats requiert : avoir l’enveloppe temporelle des dates de décès pour la population générale
que des classes de patients se dégagent suffisamment clairement dans les données
étiquetées
Étapes
1.1. Développer EM standard et chercher des groupes de données dans les données Développer EM standard et chercher des groupes de données dans les données
étiquetéesétiquetées
2. Tester le nouvel algorithme sur des données artificielles
3. L’essayer sur les données INDANA
INDANA (rapport AC) 10/03/03 12/34 © Antoine Cornuéjols
Rappels sur EMRappels sur EM
Expectation/Maximization
Algorithme d’estimation de maximum de vraisemblance par itération successive de deux étapes
Introduit par Dempster, Laird et Rubin en 1978
INDANA (rapport AC) 10/03/03 13/34 © Antoine Cornuéjols
Le principe du maximum de vraisemblanceLe principe du maximum de vraisemblance
Soit S = {x1,x2, …, xm} un échantillon de données
gouverné par une distribution pX(x|)
Alors par hypothèse i.i.d. :
p(S | ) p(x i | ) L( | S)
i1
m
On cherche :
ou encore :
* Argmax
L ( | S)
* Argmax
log L ( | S)
INDANA (rapport AC) 10/03/03 14/34 © Antoine Cornuéjols
Le principe du maximum de vraisemblanceLe principe du maximum de vraisemblance
Parfois facile à résoudre
E.g. estimation d’une seule gaussienne : (, 2)
Parfois difficile
Augmentation de données
INDANA (rapport AC) 10/03/03 15/34 © Antoine Cornuéjols
ML par EMML par EM
On suppose :
• Sobs = {xobs1,xobs
2,…,xobsm} un échantillon de données observéesdonnées observées
• Sc = {xc1,xc
2,…,xcm} un échantillon correspondant de données cachéesdonnées cachées
• St = (Sobs, Sc) = {(xobs1, xc
1), (xobs2, xc
2),…,(xobsm, xc
m)} : les données totalesdonnées totales
L ( | St) L( | Sobs, Sc ) p(Sobs,Sc |)
L ( | Sobs,Sc ) hSobs, (Sc )
Fonction de vraisemblance des données totalesFonction de vraisemblance des données totales :
Variable aléatoire car Sc est inconnue et gouvernée par une distribution cachée
INDANA (rapport AC) 10/03/03 16/34 © Antoine Cornuéjols
ML par EMML par EM
On cherche donc :
Mais L(|Sobs,Sc) est une variable aléatoire en Sc
On va donc éliminer ce caractère aléatoire en passant par l’espérance de L(|Sobs,Sc) (ou de son logarithme)
par rapport aux données cachées
Ed. les données observées et l’estimation courante du paramètre
* Argmax
log L ( | Sobs ,Sc )
Q( |k ) E log p(Sobs,Sc |) Sobs ,k
log p(Sobs,sc |) . sc Xc
m p(sc | Sobs,) dsc
INDANA (rapport AC) 10/03/03 17/34 © Antoine Cornuéjols
L’algorithme EML’algorithme EM
Étape d’expectationexpectation (E_étape) :
Étape de maximisationmaximisation (M_étape) :
Q( |k ) E log p(Sobs,Sc |) Sobs ,k
k 1 Argmax
Q( |k )
k := k+1 ; jusqu’à convergence
Initialisation de 0 et de Sc
INDANA (rapport AC) 10/03/03 18/34 © Antoine Cornuéjols
L’algorithme EML’algorithme EM
EM intéressant seulement si Q(’) est plus facile à calculer que L(|S)
Les étapes E et M
Ne sont pas toujours faciles à calculer
(mais généralement plus faciles que L(|S) )
Mais ont une solution analytique pour une grande famille de fonctions paramétrées (e.g. les
distributions exponentielles)
Mélanges de gaussiennes
HMMs
…
INDANA (rapport AC) 10/03/03 19/34 © Antoine Cornuéjols
EM : l’ « intuition »EM : l’ « intuition »
Étape_E
Étape_M
EEM
Paramètres des données complètes
Par
amèt
res
des
mod
èles
0.10.30.50.7
0.9
Contours de la log-vraisemblance
de la probabilité jointep(,Sc)
INDANA (rapport AC) 10/03/03 20/34 © Antoine Cornuéjols
EMEM : Cas des mélanges de gaussiennes : Cas des mélanges de gaussiennes
On suppose un mélange de N gaussiennes :
p(x |) jj1
N
p j (x | j )
La log-vraisemblance des données incomplètes est alors :
… qui est très difficile à optimiser
log L( | Sobs ) log p(xobs
i | )i1
m
log jj1
N
p j (xobsi | j)
i1
m
INDANA (rapport AC) 10/03/03 21/34 © Antoine Cornuéjols
EMEM : Cas des mélanges de gaussiennes : Cas des mélanges de gaussiennes
On augmente les données en ajoutant un ensemble de variables
latentes
Chaque xci correspond à la responsabilité présumée de la gaussienne
xci {1,…,N} pour la donnée
log L ( | Sobs, Sc ) log p(Sobs, Sc | ) log p(xobsi | xc
i ).p(xc) i1
m
log xc
i .pxci (xobs
i |xc
i ) i1
m
Sc xci
1im
xobsi
INDANA (rapport AC) 10/03/03 22/34 © Antoine Cornuéjols
EMEM : Cas des mélanges de gaussiennes : Cas des mélanges de gaussiennes
Après calculs (…) :
lnew
1
m p (l |
i1
m
xobsi ,k )
lnew
xobsi p(l | xobs
i ,k ) i1
mp( l | xobs
i ,k ) i1
m
lnew
p(l | xobsi ,k ) (xobs
i lnew) (xobs
i lnew )
i1
mp(l | xobs
i ,k ) i1
m
INDANA (rapport AC) 10/03/03 23/34 © Antoine Cornuéjols
Application de EM aux mélanges de GaussiennesApplication de EM aux mélanges de Gaussiennes
Soit le relevé des tailles d’un échantillon de personnes
S’explique-t-il par un mélange de gaussiennes ?
INDANA (rapport AC) 10/03/03 24/34 © Antoine Cornuéjols
Application de EM aux mélanges de GaussiennesApplication de EM aux mélanges de Gaussiennes
Résultat de EM après 10 itérations
INDANA (rapport AC) 10/03/03 25/34 © Antoine Cornuéjols
Application de EM aux données INDANAApplication de EM aux données INDANA
Problèmes Données en dimension > 2
Nécessite des calculs de vecteurs moyenne de variance (matrice de variance-covariance) d’écart-type (racine carrée de matrice : décomposition par méthode de Cholesky)
Malédiction de la dimensionnalité : croissance exponentielle du nombre de données requis en fct du nb de dimensions
Des attributs numériques et symboliques on traite les attributs symboliques comme des attributs numériques
Des problèmes de calcul dues aux probabilités très faibles Organiser les calculs Beaucoup de tests en cours d’éxécution
INDANA (rapport AC) 10/03/03 26/34 © Antoine Cornuéjols
Application de EM aux données INDANAApplication de EM aux données INDANA
Problèmes généraux Initialisation des gaussiennes
Initialisation centrée, puis … Placement itératif des N gaussiennes
Choix du nombre de Gaussiennes Méthode par dichotomie successive
Mesure de la qualité du mélange obtenu (pour arrêter l’algorithme) Mesure de précision de Gaussienne
La max des écart-types de G1 ≤ max des écart-types de G2 Mieux vaut des Gaussiennes précises Mais plus de Gaussiennes => plus de précision
Mesure de proximité entre Gaussiennes On mesure d(i,j)= max[p(centre Gi|Gj), p(centre Gi|Gj)] Les Gaussiennes sont d’autant plus éloignées que cette mesure est faible On estime que les Gaussiennes Gi et Gj sont légitimes si d(i,j) ≈ 0
INDANA (rapport AC) 10/03/03 27/34 © Antoine Cornuéjols
Application de EM aux données INDANAApplication de EM aux données INDANA
Initialisation des Gaussiennes
INDANA (rapport AC) 10/03/03 28/34 © Antoine Cornuéjols
Application de EM aux données INDANAApplication de EM aux données INDANA
Initialisation des Gaussiennes
INDANA (rapport AC) 10/03/03 29/34 © Antoine Cornuéjols
Expériences réaliséesExpériences réalisées
Sur la 1ère base : 2230 patients
Chaque variable a été bruitée avec une loi normale d’écart-type 0.1
Expériences répétées 5 fois (pour vérifier la stabilité)
Pour 2, 3, 5 et 10 gaussiennes
Mise en œuvre Initialisation telle que décrit plus haut Attribution stochastique des classes dans l’étape E
INDANA (rapport AC) 10/03/03 30/34 © Antoine Cornuéjols
EM sur INDANA : résultats (2 classes)EM sur INDANA : résultats (2 classes)
Deux Gaussiennes :
INDANA (rapport AC) 10/03/03 31/34 © Antoine Cornuéjols
EM sur INDANA : résultats (3 classes)EM sur INDANA : résultats (3 classes)
INDANA (rapport AC) 10/03/03 32/34 © Antoine Cornuéjols
EM sur INDANA : résultats (5 classes)EM sur INDANA : résultats (5 classes)
INDANA (rapport AC) 10/03/03 33/34 © Antoine Cornuéjols
EM sur INDANA : résultats (10 classes)EM sur INDANA : résultats (10 classes)
INDANA (rapport AC) 10/03/03 34/34 © Antoine Cornuéjols
EM sur INDANA : bilanEM sur INDANA : bilan
Précautions Résultats à confirmer
Il faudrait répéter davantage les expériences Tester sur le reste des données INDANA
Perspectives Les classes « aberrantes » correspondent-elles à un phénomène intéressant?
de protection naturelle (origine génétique) contre AVC ? … ?
EM pour la régression Espoir très faible (avec ce type de données)
Recommended