Pattern recognition – Computer exercices

Pattern recognition – Computer exercices
V. Vigneron
[email protected]
Univ. Evry Val d’Essonne
Feb.-March 2014
Les comptes-rendus de TP sont à rendre le 24/03
par mail. Si certaines questions vous sont posées dans le texte du TP, écrivez vos réponses
personnelles dans le compte-rendu. Au début de ce TP, vous apprendrez quelques manipulations de base sous MATLAB que vous pourrez employer pour faciliter la rédaction de vos
comptes-rendus.
Un mot sur les comptes-rendus de TP
1
TP1 – Classification linéaire
Exercice 1
Générer un échantillon qui suit une distribution normale spécifiée par
4 4
n = 2, N = 100, M = (1, 2) Σ =
0 9
Afficher l’échantillon généré.
ˆ et Σ.
ˆ
Calculer le vecteur moyen et la matrice de variance-covariance estimés M
Répéter l’expérience 10 fois en recalculant le vecteur moyen et la matrice de variance-covariance.
Répéter pour N = 10, 20 et 40 et examiner les effets de la taille de l’échantillon.
Exercice 2 classification binaire.
Soient 2 distributions équiprobables
(π1 =π2 = 1/2), de moyennes µ1 = (0, 0)T , µ2 = (2, −2)T , et de matrice
1.0
0.
de variance-covariance Σ =
.
0 0.5652
1. Générer des points appartenant aux 2 distributions (randn()).
2. Montrer que la frontière de décision a pour équation:
5.56 − 2.0x1 + 3.56x2 = 0.0
Exercice 3
suivant :
Un éleveur de chats dispose de 2 races A et B. Il a noté les poids respectifs dans le tableau
Poids en kg
race A
race A
3
1
4
2
5
2
6
4
7
5
1
8
9
3
9
10
4
10
8
7
11
5
10
12
4
7
13
1
5
14
15
3
1
1. Si on choisit un chat au hasard, quelle est la probabilité a priori qu’il soit de la race A (resp. de la
race B).
2. Calculer le poids moyen pour chaque race ainsi que l’écart-type.
3. Est-il raisonnable de considérer les distributions de poids dans chaque race comme des distributions
gaussiennes?
4. Si on choisit un chat au hasard, Comment estimer sa race d’appartenance ? Proposer un algorithme
très simple.
5. Notons m1 , m2 les moyennes empiriques et σ1 , σ2 les écarts-types empiriques des 2 races A et B,
calculées à la question 2).
• Donner l’expression du rapport de vraisemblance Λ(x) =
P (x|m2 )
P (x|m1 ) .
• Représenter graphiquement les régions de décision X1 et X2 où X1 = {x|P (x|m1 ) > P (x|m2 )} et
X2 = {x|P (x|m1 ) < P (x|m2 )}.
• Est-il vraisemblable de décider qu’un chat de 10,5 kg est de race A ?
2
[email protected]
Exercice 4 Ecrire un code qui génère un échantillon de Bernouilli de paramètre p, et le code qui calcule
pˆ à partir de l’échantillon.
Recommencer l’opération pour une distribution normale N(m, σ).
Exercice 5
Que vaut le taux de vraisemblance
p(x|w1 )
p(x|w2 )
dans le cas de densités Gaussiennes N2 (m2 , σ2 ) et N1 (m1 , σ1 ) univarié ?
Exercice 6 En compression d’image, on peut utiliser les centres mobiles de la façon suivante. L’image
est divisée en fenêtre sans recouvrement de dimensions c × c qui forment notre échantillon. On réalise
un clustering de type centres mobiles pour former K classes, ou K ≈ 4 ou 6. Les vecteurs moyens c’està-dire les centres de ces classes sont nos vecteurs de références. Ils regroupent autour deux les vecteursimagettes. Les fenêtres se voient attribués un label en référence à leur centre de classe. Chaque imagette i
est repérée par un indice qui correspond à une position (xi , yi ) dans l’image globale, par exemple la position du
centre de l’imagette. Plutôt que d’envoyer l’image complète, trop lourde, nous n’enverrons qu’une partie de
l’information: les indices des imagettes ainsi que leur label sur un canal de communication. A la réception,
l’image est reconstruite en recomposant l’image avec les imagettes de reférence selon leurs position dans
l’image.
• Écrire le programme informatique qui réalise ceci.
• Pour chaque cas, calculer l’erreur de reconstruction et le taux de compression (proposer votre critère
d’erreur)
• tester votre algorithme en faisant varier c, K.
Figure 1: Principe des centres mobiles.
3
[email protected]
TP2 – RÉGRESSION LINÉAIRE
Exercice 7 Supposons qu’on dispose de 2 variables x1 et x2 et qu’on veut faire un ajustement quadratique
à partir de ces variables :
f (x1 , x2 ) = w0 + w1 x1 + w2 x2 + w3 x1 x2 + w4 x21 + w3 w22
• Comment trouver wi , i = 1, . . . , 5 à partir d’un échantillon X = (xi1 , xi2 ; ri ). Proposer un programme.
• transformer cette implémentation en un algorithme itératif adaptatif.
Exercice 8 Récupérer les données Computer-activity1 et disponibles dans l’archive Dataset.data.gz.
Préparer les données en normalisant les variables pour éviter des problèmes numériques dans le calcul des
coefficients. Ecrire une fonction Matlab :
function [X Y] = extraction(data,liste_variables,nb_exemples)
qui extrait de la matrice data précédente les variables fournies par la liste liste_variables pour nb_exemples
tirés au hasard dans la base. (la matrice X devra prendre en compte la “variable constante” de la régression.
Programmer un code qui calcule :
1. Les coefficients de régression du modèle multivarié
Pn ∗
1
2. Les paramètres (moyenne et variance) de l’erreur s2 = n−2
ˆi )2 , où y ∗ est la valeur attendue
i (yi − y
et yˆ la valeur calculée (estimée)
Pn ∗
Pn
ˆi )2
(ˆ
yi − y¯)2
variance expliquée
i (yi − y
i
2
2
P
ou
R
=
1
−
3. Le coefficient de corrélation R = Pn ∗
=
n
∗
variance des points
¯)2
¯)2
i (yi − y
i (yi − y
4. La courbe des résidus r = y ∗ − yˆ = f (X),
5. La courbe yˆ (y calculé) vs. y ∗ (y attendu),
6. Testez ce programme. Pour un nombre fixé d’exemples, avec chaque variable fournie par les données
du début. S’il fallait choisir une variable, laquelle prendriez vous ?
Exercice 9
Dear Sir,
Our geology students have collected the following data: ` = thickness of a local bed of sedimentary rock,
d = diameter of the area.
1 Measures
of a of system activity in a multi-processor, multiuser computer system.
4
[email protected]
`
960
564
261
1227
284
89
705
168
431
104
1184
907
117
104
284
1322
449
615
1479
143
d
35
27
21
36
24
17
30
19
24
18
38
32
16
36
23
40
27
31
49
18
Could you suggest a suitable way of predicting ` from d ?
Yours Sincerely,
Trevor Jones
5
[email protected]
TP3 – Perceptron multicouches
Exercice 10 Rétropropagation du gradient
Générez un ensemble d’apprentissage de taille n = 100 constitué de deux classes en dimension d = 2 avec le
programme generation_dataBP.m :
• La première est une classe Gaussienne de dimension deux, de moyenne µ = (0; 6).
• La seconde est une classe en forme de banane avec la première variable x1 tirée suivant une loi uniforme
sur [−3, 3], et la seconde variable x2 égale au carré de la première plus un bruit gaussien réduit (cf.
Fig. 2)
Figure 2: Le problème “jouet”.
Définition du MLP et de l’algorithme de rétropropagation.
Construisez les fonctions :
1. function [w1 w2] = mlpinit(m)
qui initialise les poids d’un perceptron multicouche à m neurones dans la couche cachée,
2. function [y] = mlpval(x, w1, w2)
qui calcule la sortie d’un perceptron multicouche défini par ces matrices de paramètres w1 et w2,
3. function [w1 w2] = mlpfit(xi, yi, w1, w2)
qui estime les paramètres d’un perceptron multicouche à partir de l’échantillon (xi, yi). Estimez les
paramètres du réseau avec m variant de 1 à 10. Que concluez vous2 ?
4. Pour le problème de classification, calculer le Lambda de Wilks :
Λk =
2 Affichez
det(W )
det(W + B)
à chaque fois: le nombre d’itérations, l’erreur quadratique moyenne et le taux de bonne classification
6
[email protected]
où W =
J
X
X
j
(xi − µj )T (xi − µj ) est la corrélation intraclasse et B =
xi ∈Cj
J
X
nj (µ − µj )T (µ − µj ) est
j
la corrélation interclasses.
Calculer la spécificité et la sensibilité du modèle. Programmer les équations de mise a jour des poids pour
Figure 3: Algorithme de la backpropagation.
des unités cachées qui utilisent tanh au lieu de la fonction sigmoidal. Utiliser le fait que
tanh0 = (1 − tanh2 )
Figure 4: Perceptron multi-couches capable de résoudre le problème du XOR.
Problème du XOR
• Simuler la fonction ET avec des poids fixes et sans apprentissage. Les paramètres du Perceptron sont les
suivants : w1 = 0.2, w2 = 0.1etS = −0.2. Les exemples de comportement à vérifier (ET) sont rappelés
7
[email protected]
sur la table suivante :
x1
0
0
1
1
x2
0
1
0
1
y
0
0
0
1
• Pour la même base d’apprentissage, réaliser l’apprentissage (ne pas oublier la modification du seuil).
Le choix des conditions initiales est confié au hasard.
• Essayer d’apprendre le XOR.
• calculer une matrice de confusion. Générer 2 nuages de points gaussiens autours les 4 points précédents
avec une matrice de variance
Enfin, appliquer la rétropropagation à la classification de cellules collagènes ou PAI.
8
[email protected]
TP4 –Carte de Kohonen
Exercice 11 Programmer une carte de Kohonen La quantification vectorielle est l’une des méthodes
de compression d’image parmi les plus employées. Nous allons réaliser cette quantification en utilisant
des cartes auto-organisatrices. Les images qui proviennent de la télévision, de visioconférence, de satellite,
ou d’applications médicales . . . quelles qu’elles soient, représentent une quantité énorme de données après
digitalisation. Diminuer les coûts de transmission ou de stockage est d’un intérêt très ancien (par exemple, le
code Morse). En ce qui concerne les applications aux communications, le but recherché est alors de minimiser
la durée de transmission d’un certain volume d’informations. Ceci apporte à la fois une économie sur le coût,
une diminution des risques d’erreurs, une plus grande ergonomie et une plus grande performance, puisque
les données sont acheminées en un temps plus court. Les diverses méthodes de compression sont basées
sur les techniques de prédiction, de transformation, ou de quantification vectorielle, avec des possibilités de
combinaisons entre elles. Elles sont de deux types. Si la transformation réalisée est réversible, la réduction
utilise la redondance d’informations et aucune information n’est perdue. Dans l’autre cas, la transformation
est irréversible. C’est une réduction d’entropie et il y a perte d’informations. Les performances de la
compression sont mesurées par la MSE (Mean Square Error) qui représente la différence entre l’image initiale
et l’image reconstituée. La quantification vectorielle est l’une des méthodes de compression d’image parmi
les plus employées. Nous allons réaliser cette quantification en utilisant des cartes auto-organisatrices. Les
images qui proviennent de la télévision, de visioconférence, de satellite, ou d’applications médicales . . . quelles
qu’elles soient, représentent une quantité énorme de données après digitalisation. Diminuer les coûts de
transmission ou de stockage est d’un intérêt très ancien (par exemple, le code Morse). En ce qui concerne
les applications aux communications, le but recherché est alors de minimiser la durée de transmission d’un
certain volume d’informations. Ceci apporte à la fois une économie sur le coût, une diminution des risques
d’erreurs, une plus grande ergonomie et une plus grande performance, puisque les données sont acheminées en
un temps plus court. Les diverses méthodes de compression sont basées sur les techniques de prédiction, de
transformation, ou de quantification vectorielle, avec des possibilités de combinaisons entre elles. Elles sont
de deux types. Si la transformation réalisée est réversible, la réduction utilise la redondance d’informations
et aucune information n’est perdue. Dans l’autre cas, la transformation est irréversible. C’est une réduction
d’entropie et il y a perte d’informations. Les performances de la compression sont mesurées par la MSE
(Mean Square Error) qui représente la différence entre l’image initiale et l’image reconstituée.
Le nombre de mots du dictionnaire est égal à la taille du réseau (nombre de neurones). Le dictionnaire
est donc composé des blocs les plus représentatifs de l’image.
Tester sur les images de cellules qui vous seront fournies et démontrer qu’on améliorer la quantiifcation.
9
[email protected]
Figure 5: Principe de la quantification vectorielle par carte auto-organisatrice.(1) Construction du dictionnaire : la carte sélectionne les mots du dictionnaire à partir des blocs les plus représentatifs de l’image. (2)
Codage de l’image (par le dictionnaire) : la carte sélectionne pour le bloc de l’image qui lui est présenté le
numéro du mot du dictionnaire le plus proche. (3) Transmission : le numéro des vecteurs est transmis par
le canal. (4) Décodage (reconstitution).
10
[email protected]