View
34
Download
1
Category
Preview:
Citation preview
INF442 : Traitement des données massives
A3 : La lassi� ation supervisée ave les k-plus pro hes voisins
Frank Nielsen
X2013
22 avril 2015
Frank Nielsen A3-1
Le programme pour aujourd'hui
◮quelques révisions sur MPI
◮la lassi� ation = apprentissage supervisé
◮les pointeurs et les référen es en C++ !
Frank Nielsen A3-2
HPC & MPI
Frank Nielsen A3-3
Terminologie : les �ma hines parallèles�, les super-ordinateurs
◮Super- al ulateur ve toriel (Cray) : travaille sur des ve teurs
(A = B + C ), parallélisme à petits grains (SIMD) sur les
oordonnées : for parallel i , Ai = Bi + Ci (forpar)
◮Cluster de ma hines (Beowulf) : ensemble de ma hines
inter onne tées en LAN par Ethernet TCP/IP. Pour augmenter la
bande passante et diminuer la laten e, matériel réseau optimisé (Myrinet,
In�niBand, Gigabit Ethernet, et .). Parallélisme à gros grains (MPMD)
◮Grille de ma hines : ma hines inter onne tées ave une faible
bande passante et grande laten e. → Appli ations distribuées ave
�parallélisme embarrassant� (embarassingly parallel) omme SETI�home,
Folding�home ave peu de ommuni ations
◮Multi-pro esseur symétrique (Symmetri Multi-Pro essor,
SMP) à mémoire partagée, bus d'inter onnexion ( ontentions,
grande bande passante)
◮Pro esseur multi- ÷ur (multi- ore) : plusieurs unité de al ul
sur la même pu e : IBM Power
R© 4 à 1 GHz en 2001 , Playstation
R© 3
en 2006
Frank Nielsen A3-4
Comment mesurer le temps d'exé ution des programmes ?
Pi : pro essus pour i ∈ {0, ...,P − 1}
t(Pi ) : temps d'exé ution du i -ème pro essus, makespan =stop
time - start time
Que veut-on mesurer omme temps d'exé ution d'un programme
parallèle ?
◮mini∈{0,...,P−1} t(Pi) (pro . le plus rapide)
◮maxi∈{0,...,P−1} t(Pi ) (pro . le plus lent)
◮maxi∈{0,...,P−1} t(Pi )−mini∈{0,...,P−1} t(Pi) (l'é art de temps
entre les pro .)
Deux types de méthode :
◮Mesure externe : on utilise une ommande UNIX/shell
omme time, times (shell). Faire man times pour le manuel !
◮Mesure interne : on ode à l'intérieur du programme en
utilisant gettimeofday() (UNIX) ou mieux en ore
MPI_Wtime()
Frank Nielsen A3-5
Mesure externe ave time et times
[ fran e MPI ℄$ time mpirun -np 2 -host hollande , allemagne piMonteCarlo442 .exe
pi appro he par le pro . 1 ave 10000000 points = 3.141130 e+00 erreur :4.626536 e
-04
pi appro he par le pro . 0 ave 10000000 points = 3.141130 e+00 erreur :4.626536 e
-04
[ a umulation ℄ pi appro he ave 20000000 points = 3.141130 e+00
erreur d' approximation : 4.626536 e -04
real 0m1 .133 s
user 0m0 .091 s
sys 0m0 .034 s
[ fran e MPI ℄$ times mpirun -np 2 -host hollande , allemagne piMonteCarlo442 .exe
0m0 .075 s 0m0 .020 s
0m1 .867 s 0m0 .432 s
malheureusement pas très pré is ±0.5 se , mais utile pour les
programmes lents.
man times : built-in shell ommand
Frank Nielsen A3-6
Le par de ma hines dans les salles informatiques
169× 8 = 1352 ÷urs, 2.5 TB de mémoire vive !
◮(50x) CPU : Intel Core i7-2600 CPU � 3.40GHz, MEM : 12Gb
◮(69x) CPU : Intel Core i7-3770 CPU � 3.40GHz, MEM : 16Gb
◮(50x) CPU : Intel Xeon E3-1240 V2 � 3.40GHz, MEM : 16Go
À vos projets !
Validation des projets demain (23 avril) : onta tez
dambrosio�lix.polyte hnique.fr
Date limite de soumission des projets avant soutenan e : le
22 mai 2015 (par moodle)
Frank Nielsen A3-7
Connaître les spé i� ations de sa ma hine en TD
more /pro / puinfo
pro essor : 0
vendor_id : GenuineIntel
pu family : 6
model : 60
model name : Intel(R) Xeon(R) CPU E3-1271 v3 � 3.60GHz
stepping : 3
pu MHz : 800.000
a he size : 8192 KB
...
pro essor : 7
...
Frank Nielsen A3-8
Connaître les spé i� ations de sa ma hine en TD
Par exemple, sur la ma hine fran e, tapez ls pu :
Ar hite ture : x86_64
CPU op - mode (s): 32- bit , 64- bit
Byte Order : Little Endian
CPU (s): 32
On - line CPU (s) list : 0-31
Thread(s) per ore : 2
Core (s) per so ket: 8
So ket(s): 2
NUMA node (s): 2
Vendor ID: GenuineIntel
CPU family: 6
Model : 45
Stepping : 7
CPU MHz : 2593.601
BogoMIPS : 5188.92
Virtualization : VT -x
L1d a he : 32K
L1i a he : 32K
L2 a he : 256 K
L3 a he : 20480 K
NUMA node0 CPU (s): 0-7,16-23
NUMA node1 CPU (s): 8 -15 ,24 -31
⇒ 2 �ls/ ÷ur physique ( ÷ur logique ave la te hnologie
hyperthreading). 32 ÷urs !
Frank Nielsen A3-9
MPI : Communi ations/opérations globales
◮ ommuni ations point à point , bloquante ou non-bloquante
◮di�usion (un vers tous) et rédu tion (tous vers un =
di�usion inverse)
◮di�usion personnalisée, s atter
◮rassemblement (personnalisé), gather
◮somme pré�xe (rédu tion), et opérations de pré�xes parallèles,
s an
◮di�usion totale tous vers tous, total ex hange
◮di�usion totale tous vers tous personnalisée, le ommérage
◮plein d'autres modes dans MPI : explorer la do umentation
d'OpenMPI !
Frank Nielsen A3-10
La di�usion : broad ast
int MPI_B ast(void *buffer, int ount,
MPI_Datatype datatype,
int root, MPI_Comm omm)
https://www.open-mpi.org/do /v1.5/man3/MPI_B ast.3.php
Programme parallèle SPMD en MPI : tous les pro essus exé utent
le même ode. On distingue la partie des instru tions pour les
pro essus grâ e à leur rang.
Frank Nielsen A3-11
La di�usion : pro essus/mémoire lo ale
Programme parallèle SPMD en MPI : tous les pro essus exé utent
le même ode. On distingue la partie des instru tions pour les
pro essus grâ e à leur rang.
#i n l u d e <mpi . h>
#i n l u d e <s t d i o . h>
// Quand on appelle mpirun tous les pro essus exé utent ette fon tion main
i n t main ( i n t arg , har ∗∗ argv ) {
i n t rank ;
i n t n ;
on s t i n t r oo t =0;
MPI_Init (&arg , &argv ) ;
MPI_Comm_rank(MPI_COMM_WORLD, &rank ) ;
// i i, on donne du ode parti ulier pour le pro essus P0
i f ( rank == roo t ) {n = 442 ; }
p r i n t f ( "[%d ℄ : avant B ast , n=%d\n" , rank , n ) ;
// i i tout le monde appelle B ast !
MPI_B ast(&n , 1 , MPI_INT , root , MPI_COMM_WORLD) ;
// et tout le monde a� he à la onsole
p r i n t f ( "[%d ℄ : ap r e s B ast , n=%d\n" , rank , n ) ;
MPI_Fina l i ze ( ) ;
r e t u r n 0 ; }
Pour les programmes de type maître/es laves, on hoisit le ode du
maître, P0
, des autres grâ e à :
if (rang==0) odeMaitre(); else odeEs lave();
Frank Nielsen A3-12
La di�usion personnalisée : s atter
Toujours, l'ordre sour e puis destination dans les arguments.
int MPI_S atter(void *sendbuf, int send ount, MPI_Datatype
sendtype, void *re vbuf, int re v ount,
MPI_Datatype re vtype, int root, MPI_Comm omm)
https://www.open-mpi.org/do /v1.5/man3/MPI_S atter.3.php
Frank Nielsen A3-13
Le rassemblement : gather
int MPI_Gather(void *sendbuf, int send ount, MPI_Datatype
sendtype, void *re vbuf, int re v ount,
MPI_Datatype re vtype, int root, MPI_Comm omm)
https://www.open-mpi.org/do /v1.5/man3/MPI_Gather.3.php
Frank Nielsen A3-14
La rédu tion : redu e
int MPI_Redu e(void *sendbuf, void *re vbuf, int ount,
MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm omm)
https://www.open-mpi.org/do /v1.5/man3/MPI_Redu e.3.php
Frank Nielsen A3-15
La rédu tion : Allredu e
int MPI_Allredu e(void *sendbuf, void *re vbuf, int ount,
MPI_Datatype datatype, MPI_Op op, MPI_Comm omm)
https://www.open-mpi.org/do /v1.5/man3/MPI_Allredu e.3.php
Frank Nielsen A3-16
Communi ation sur l'anneau orienté
P0
PP−1
anneau
oriente
Pro essus P0
envoie un message au dernier pro essus (n÷ud)
PP−1
... Une di�usion
◮Topologie logique (virtuelle) du groupe de ommuni ation
(pour les algorithmes parallèles)
◮Topologie physique (le réseau matériel qui n'est pas
for ément un anneau)
Frank Nielsen A3-17
Communi ation sur l'anneau ave send et re eive
bloquants
#i n l u d e <mpi . h>
i n t main ( i n t arg , har ∗argv [ ℄ ) {
i n t rank , va lue , s i z e ;
MPI_Status s t a t u s ;
MPI_Init (&arg , &argv ) ;
MPI_Comm_rank(MPI_COMM_WORLD, &rank ) ;
MPI_Comm_size (MPI_COMM_WORLD, &s i z e ) ;
i f ( rank == 0) {
va l u e =442;
// n÷ud appelant envoie seulement
MPI_Send ( &va lue , 1 , MPI_INT , rank + 1 , 0 , MPI_COMM_WORLD) ;
}
e l s e {
// les autres n÷uds envoient et reçoivent
MPI_Re v ( &va lue , 1 , MPI_INT , rank − 1 , 0 , MPI_COMM_WORLD, &s t a t u s
) ;
i f ( rank < s i z e − 1) {
MPI_Send ( &va lue , 1 , MPI_INT , rank + 1 , 0 , MPI_COMM_WORLD) ;
}
p r i n t f ( " p r o e s s %d a r e u %d\n" , rank , v a l u e ) ;
}
MPI_Fina l i ze ( ) ;
r e t u r n 0 ;
}
Frank Nielsen A3-18
La lassi� ation =
apprentissage supervisé
Le regroupement plat =
trouver les lasses
apprentissage
non supervisé
Frank Nielsen A3-19
La lassi� ation : un apprentissage supervisé
◮un jeu d'entraînement = des données étiquettées : {(xi , yi)}iave yi = l(xi) = ±1, les étiquettes pour deux lasses C−1
et
C+1
(�l� pour label ). Considérons les xi ∈ Rd.
◮pour de nouvelles requêtes {x ′i }i d'un jeu de test (exemples
pas en ore lassés), on her he à determiner leurs étiquettes :
y ′i = l(x ′i ).
Questions :
◮Comment apprendre un lassi�eur , 'est-à-dire une fon tion
de lassi� ation l(·) ?
prédi tion / estimation notée aussi yi = l(xi )
◮Comment évaluer la performan e d'un tel lassi�eur ? quelles
hypothèses ? (apprentissage statistique)
Frank Nielsen A3-20
La règle du plus pro he voisin (NN rule)
PPV = Plus Pro he Voisin
NN = Nearest Neighbour
◮Soit une base d'apprentissage ( training set ) T = {(xi , yi )}
ti=1
◮La règle du plus pro he voisin donne omme étiquette l(x) à x
elle de son plus �pro he� voisin dans T :
m = arg min
i∈[t]D(x , xi ), l(x) = ym
◮la proximité est dé�nie en fon tion d'une distan e appropriée
D(·, ·) entre deux éléments quel onques.
On note [t] = {1, ..., t}.
Frank Nielsen A3-21
Classi� ation : la règle du plus pro he voisin
Frank Nielsen A3-22
Les fon tions de distan e : données numériques/ atégoriques
◮Distan e eu lidienne : D(p, q) =
√
∑di=1
(pi − qi)2. Pour des
requêtes NN, on peut prendre de façon équivalente la distan e
eu lidienne au arré (le arg min ne hange pas) :
D2(p, q) =∑d
i=1
(pi − qi )2 = ‖p − q‖2.
◮Si on pré- al ule les normes au arré
nrm
2(p) = 〈p, p〉 =∑d
i=1
p2i en O(dn), alors on al ule plus
rapidement D2(p, q) = nrm
2(p) + nrm
2q − 2〈p, q〉 pour denombreuses requêtes.
◮Pour les données atégorielles (non-numériques, ou ordinales),
on peut utiliser la distan e de Hamming :
Hamming(p, q) =
d∑
i=1
(1− δpi (qi )) =
d∑
i=1
1[pi 6=qi ],
δx(y) = 1 si et seulement si y = x , 0 autrement.
→ Hamming(p, q) ompte le nombre d'attributs di�érents
Frank Nielsen A3-23
La règle du plus pro he voisin : diagrammes de Voronoï
Pour un jeu d'apprentissage T , Rdest partitionné en lasse
d'équivalen e pour la fon tion d'étiquettage.
→ Diagramme de Voronoï,
ellules de proximité à arg min onstant
Frank Nielsen A3-24
La règle du plus pro he voisin : frontières de Voronoï
Générateurs bi- ouleurs (2 lasses, C±1
) pour Voronoï, et frontières
de lassi� ation. de ision boundary
Linéaire par morçeau pour la distan e Eu lidienne (ou son arré).
Frank Nielsen A3-25
Frank Nielsen A3-26
Démo
Frank Nielsen A3-27
La règle de lassi� ation k-NN pour m lasses
On hoisit la lasse majoritaire des k plus pro hes voisins d'une
requête q.
i i, k = 20 et m = 2...
on préfère un nombre impair pour k quand m = 2 (pas de
tie-breaking )
Frank Nielsen A3-28
Comparons la règle des 15-PPVs vs. la règle du PPV (=1-PPV)
15-PPVs 1-PPV
Frank Nielsen A3-29
Évaluation du lassi�eur k-PPV/k-NN
◮le taux d'erreur sur un jeu de données Test omportant n
données (di�érent de elui pour l'apprentissage) est :
Erreur =#mal lassé
n
◮pas très dis riminant lorsque les ( ardinalités des) lasses sont
très déséquilibrées.
◮par exemple, lasser des messages en C
spam
et Cham
(non-spam). On a souvent moins de spams, et il est préférable
alors de lasser le tout en non-spam (= ham) et ainsi obtenir
un bon taux d'erreur global...
Frank Nielsen A3-30
Évaluation du lassi�eur : matri e de onfusion
La matri e de onfusion M = [mi ,j ] pour m lasses :
mi ,j = P(x lassé Ci | x ∈ Cj)
La diagonale montre le taux de réussite sur la lasse donnée.
Terminologie spé iale quand m = 2 : lassi� ation binaire
Label prédit
C+1
C−1
Vrai label
C+1
True Positive (TP) False Negative (FN)
C−1
False Positive (FP) True Negative (TN)
True la prédi tion est juste (Label prédit = Vrai label)
False la prédi tion est fausse (Label prédit 6= Vrai label)
Positive la prédi tion est C+1
Negative la prédi tion est C−1
Frank Nielsen A3-31
Performan e : l'exa titude
A ura y (exa titude) = Proportion de lassi� ations orre tes
(sur les n exemples de la base Test) :
A ura y =TP+ TN
n
ave n = TP+ TN+ FP+ FN.
→ ratio of orre tly predi ted observations. Ce qu'on a bien lassé
(T=true) !
Frank Nielsen A3-32
Performan e : la pré ision
Rapport entre le nombre de vrais positifs et la somme des vrais
positifs et des faux positifs :
Pré ision =TP
TP+ FP
0 ≤ Pré ision ≤ 1
→ pré ision de 1 quand toutes les données lassées vraies C+1
appartiennent vraiment à C+1
, pas de vrais mal lassées.
Informellement : la pré ision 'est le pour entage de han e
d'être orre t quand on répond positif !
Frank Nielsen A3-33
Performan e : le rappel (re all)
Re all, taux de déte tion
Rapport entre le nombre de vrais positifs et la somme des vrais
positifs et des faux négatifs (= eux qu'on a loupé, qui devraient
être positifs) :
Rappel =TP
TP+ FN
→ Sensitivité, C+1
= TP+ FN relevant elements (de même,
C1
= TN+ FP)
0 ≤ Rappel ≤ 1
Un rappel/re all de 1 signi�e que tous les exemples positifs ont été
trouvés.
Informellement : le rappel 'est le pour entage d'exemples
positifs orre tement trouvé !
http://en.wikipedia.org/wiki/Pre ision_and_re all
Frank Nielsen A3-34
Performan e : le F -s ore
On her he une mesure qui ombine les faux positifs (FP) ave les
faux négatifs (FN) ...
Donne autant de poids aux faux positifs qu'aux faux négatifs :
F-s ore =2× Pre ision× Re all
Pre ision+ Re all
→ la moyenne harmonique de Pré ision et Rappel.
En ore appelé F -measure ou F1.
Frank Nielsen A3-35
La lassi� ation Bayésienne
Cadre : apprentissage statistique supervisé
◮On fait l'hypothèse d'un apprentissage statistique : les
observations proviennent de deux distributions X−1
∼ p−1
(x)et X+1
∼ p+1
(x) (variables aléatoires ave
P(X±1
= x) = p±1
(x)) ave des probabilités a priori
w−1
= P(l(x) = −1) et w+1
= P(l(x) = 1) = 1− w−1
. On
note p±1
les probabilités onditionnelles des lasses.
◮Modèle de mélange en statistique pour les observations :
P(X = x) = p(x) = w−1
p−1
(x) + w+1
p+1
(x)
◮N'importe quel lassi�eur fera un taux d'erreur non nul
puisque les distributions de X±1
ont le même support X , et
don P(X ∈ C±1
) > 0. On ne peut don jamais être ertain à
100% de la provenan e de x !
◮On appelle probabilité d'erreur, Pe , le taux minimum
moyen d'erreur d'un lassi�eur (risque/erreur de Bayes)
Frank Nielsen A3-36
Cas où w+1
= w−1
= 1
2
Frank Nielsen A3-37
Rappel : le théorème de Bayes et sa preuve
Fa ile à démontrer :
P(A ∩ B) = P(A)P(B |A) = P(B)P(A|B)
P(A|B) =P(A)P(B |A)
P(B)
◮ P(A) : probabilité a priori
◮ P(B |A) = P(A∩B)P(A) : probabilité onditionnelle
◮ P(A|B) : probabilité a posteriori de A sa hant B
Frank Nielsen A3-38
Théorie Bayesienne de la dé ision
Pe(R) = P(error) =
∫
p(x)× P(error|x ,R)dx
P(error|x ,R) =
{
P(C+1
|x) la règle R a dé idé C−1
,
P(C−1
|x) la règle R a dé idé C+1
→ évident par dé�nition
Frank Nielsen A3-39
Règle du Maximum A Posteriori (MAP)
◮R=MAP : La règle optimale pour la lassi� ation bayésienne
qui minimise l'erreur. On hoisit la lasse la plus probable en
al ulant les probabilités a posteriori :
P(C+1
|x) =P(x |C+1
)P(C+1
)
p(x)
p(x) = P(C−1
)P(x |C−1
) = P(C+1
)P(x |C+1
) =w−1
p−1
(x) + w+1
p+1
(x).◮
Di� ile de al uler Pe(MAP) =∫
p(x)× P(error|x ,MAP)dxen formule lose !
◮ Pe = Pe(MAP) donne une borne inférieure pour les
lassi�eurs (notamment pour la règle des k-PPVs)
Un lassi�eur ne pourra jamais battre l'erreur de Bayes
obtenue par la règle du Maximum A Posteriori (MAP).
En pratique, on ne onnait ni les lois onditionnelles ni elles des
lasses a priori... (mais on peut faire des simulations en générant
des é hantillons à partir de modèles : random variates )
Frank Nielsen A3-40
training set = 200, test test = 10000 grâ e à un modèle
probabiliste onnu (→ erreur de Bayes al ulable)
Frank Nielsen A3-41
Apprentissage statistique
Évaluons la performan e d'un lassi�eur l(·) (�l� pour label) :
E[Y − l(X )]
Alors la prédi tion optimale est l'espéran e onditionnelle :
l(x) = E[Y |X = x ]
Pour la lassi� ation par k-PPV
lPPV
(x) = Moyenne(yi |xi ∈ PPVk(x)) ≈ E[Y |X = x ]
et on a
lim
n,k→∞,kn→0
lPPV
(x) = E[Y |X = x ]
Montrons maintenant omment on dérive la règle des k-PPV sous
apprentissage Bayésien.
Frank Nielsen A3-42
Estimation de densités non-paramètriques
Loi paramètrique P(x |θ) : θ le ve teur paramètre de dimension �nie
(estimation θ en utilisant le maximum de vraisemblan e). Loi
non-paramètrique = dimension de θ dépend de la taille des
é hantillons.
On ne onnaît ni les distributions onditionnelles p±1
(x), ni lesdistributions a priori. Par ontre, on peut les estimer simplement
ave l' estimateur �ballon� :
p(x) ≈k
nV (x)=
k
ncd rdk(x)
où V est le volume de la boule englobante des k-NN entrés en x :
V (x) = πd2
Γ( d2
+1)rdk (x) = cd r
dk (x)
Deux options :
◮Soit on hoisit r de la boule entrée en x (on a don V ) et on
al ule k ,◮
Soit on hoisit k , et on en déduit le rayon de la boule r = r(k) entrée en x , puis on obtient V .
Frank Nielsen A3-43
MAP et la règle du k-NN
◮probabilité a priori (prior probability) :
P(C±1
) ≈ w±1
=n±1
n
◮probabilité onditionnelle ( lass- onditional probability) :
P(x |C±1
) ≈ki
n±1
Vk
◮probabilité a posteriori (règle de Bayes) :
P(C±1
|x) =P(x |C±1
)P(C±1
)
P(x)≈
k±1
n±1
Vk
n±1
n
knVk
≈k±1
k
⇒ la règle du vote majoritaire pour le k-PPVs est la
règle MAP pour les densités non-paramétriques estimées ...
Frank Nielsen A3-44
Classi� ation statistique et k-NN aymptotique (1967)
Soit n la taille du jeu d'apprentissage et du jeu de test.
Quand n → +∞, l'erreur de la règle 1-PPV est au pire deux fois
elle de la règle optimale (MAP si on onnaissait w±1
et p±1
(x)) :
Pe ≤ Pe(règle 1-PPV) ≤ 2Pe
Pour m > 2 lasses ave la règle 1-PPV :
Pe ≤ Pe(règle 1-PPV) ≤ Pe
(
2−m
m − 1
Pe
)
Cette borne est serrée (tight !).
Frank Nielsen A3-45
Cal ul des k-plus pro hes voisins (k-NN)
Pour une requête q ∈ Rd, on doit trouver les k-PPVs dans un jeu
d'entraînement de taille n :
◮naïf en O(dkn) (brute for e)
◮naïf mais en utilisant la bibliothèque MPI ou le GPGPU
(aujourd'hui, TD3 !)
◮stru tures de données pour les requêtes k-NNs (arbres k-D,
arbres 2-boules, arbres vantage points)
◮En général, un
problème fondamental mais dur en grandes dimensions qui
reste d'a tualité dans le monde de la re her he !
Frank Nielsen A3-46
Le lassi�eur k-NNs : résumé des avantages et in onvénients
lassi�eur k-PPVs : petit biais, grande varian e...
◮Avantages :
◮Simple à mettre en ÷uvre
◮Bonnes performan es asymptotiques (sous ondition
d'apprentissage statistique)
◮Fa ile à paralléliser...
◮In onvénients :
◮Demande beau oup de mémoire (le jeu d'apprentissage)
◮Les grandes dimensions... asymptotique, requêtes k-NN,
�éau des grandes dimensions ( urse of dimensionality), f.
TD 5 sur le théorème de Johnson-Lindenstrauss
◮Choix de k pour la règle k-PPV.Trouver un juste milieu entre :
◮grand k : frontière des lasses plus lisse, estimation
non-paramétrique plus �able
◮mais... plus oûteux en temps de requêtes k-NN, estimation
moins lo ale...
Frank Nielsen A3-47
La règle k-NN en al ul distribué
◮Tout omme
min(x1
, x2
, x3
, x4
) = min(min(x1
, x2
),min(x3
, x4
)), la requête
des k plus pro hes voisins de x est dé omposable : pour
X = X1
⊎
X2
une partition de X ensous-ensembles disjoints
X1
et X2
, nous avons :
NNk(x ,X ) = NNk (x ,NNk(x ,X1
) ∪ NNk(x ,X2
))
◮Pour p pro esseurs, on partitionne don X en p paquets Xi de
taille
np, et on fait la requête NNk(x ,Xi ) dans haque paquet
en parallèle.
◮Le pro esseur maître P
0
reçoit kp élements , et fait une
requête des k plus pro hes voisins sur elui i :
NNk(x ,X ) = NNk
(
x ,
p⊎
i=1
NNk(x ,Xi )
)
◮On passe de O(dnk) pour p = 1 (séquentiel) à
O‖(dknp) + O(dkkp) = O‖(dk
np) quand p = O(
√
nk).
Frank Nielsen A3-48
Utile : Programmer en MPI un (min, arg min) ave une rédu tion
#i n l u d e <mpi . h>
#i n l u d e <s t d i o . h>
#de f i n e N 1000
i n t main ( i n t arg , har ∗∗ argv ) {
i n t rank , npro s , n , i ; on s t i n t r oo t =0;
MPI_Init (&arg , &argv ) ;
MPI_Comm_size (MPI_COMM_WORLD, &np ro s ) ; MPI_Comm_rank(MPI_COMM_WORLD,
&rank ) ;
f l o a t v a l [N℄ , m inva l ; // tableau lo al de valeurs
i n t myrank , minrank , min index ;
// on remplit le tableau de valeurs aléatoires
s rand (442+ rank ) ;
f o r ( i =0; i <N; i ++) { v a l [ i ℄= drand48 ( ) ; }
// Une dé laration de stru ture omposée
s t r u t { f l o a t v a l u e ; i n t i nd ex ; } in , out ;
// on her he d'abord lo alement la valeur minimale
i n . v a l u e = v a l [ 0 ℄ ; i n . i n d e x = 0 ;
f o r ( i =1; i <N; i ++)
i f ( i n . v a l u e > v a l [ i ℄ ) {
i n . v a l u e = v a l [ i ℄ ; i n . i n d e x = i ;
}
// on indique le rang global de l'index
i n . i n d e x = rank∗N + i n . i nd ex ;
// maintenant on re her he globalement la valeur minimale
MPI_Redu e ( ( vo i d ∗) &in , ( vo i d ∗) &out , 1 , MPI_FLOAT_INT , MPI_MINLOC ,
root , MPI_COMM_WORLD ) ;
// la réponse se trouve sur le pro essus root
i f ( rank == roo t ) {
minva l = out . v a l u e ; minrank = out . i nd ex / N; min index = out . i nd ex %
N;
p r i n t f ( " v a l e u r min ima le %f su r pro . %d a l a p o s i t i o n %d\n" , minval ,
minrank , min index ) ; }
MPI_Fina l i ze ( ) ; }
Frank Nielsen A3-49
Classi�eur moins
gourmand en mémoire
ombinant les
r-moyennes ave la règle
des k-PPVs
Frank Nielsen A3-50
Classi�eur multi- lasse optimisé
On ne veut pas garder les n entrées du jeu d'entraînement qui sont
utilisées par le lassi�eur des k-PPVs. Soit m lasses.
◮Pour haque lasse, on fait un regroupement ave les
r -moyennes pour trouver r prototypes. En tout, m × r
prototypes étiquetés qui interviennent dans la fon tion l du
lassi�eur.
◮Pour une requête q, on lasse ave la règle des k-PPVs sur les
m × r ≪ n prototypes.
Frank Nielsen A3-51
Frank Nielsen A3-52
Frank Nielsen A3-53
Presque tout sur les
pointeurs et les
référen es
Frank Nielsen A3-54
Le ompilateur C++
[fran e ~℄$ g++ --version
g++ (GCC) 4.1.2 20080704 (Red Hat 4.1.2-55)
Copyright (C) 2006 Free Software Foundation ,
In .
This is free software ; see the sour e for
opying onditions. There is NO
warranty ; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.
⇒ existe de nombreuses versions de g++ (C++98, C++11 ; et .)
STL par défaut dans C++98
Frank Nielsen A3-55
Pourquoi manipuler des pointeurs ?
Pointeur = variable qui sauvegarde la référen e d'une autre
variable.
Valeur d'un pointeur = adresse mémoire
i n t va r1 =442; va r2 = 2015 ;
i n t ∗ Ptr1 , ∗ Ptr2 ;
Ptr1 = &var1 ; Ptr2 = &var2 ;
Fa ilite l'implémentation de
stru tures de données dynamiques (listes haînees, arbres,
et .)
En C++/C, les pointeurs permettent :
◮d'allouer de la mémoire pour une variable en retournant un
pointeur sur ette zone
◮d'a éder à la valeur de la variable par déréféren ement :
*Ptr1
◮de libérer de la mémoire manuellement
◮de faire de l'arithmétique de pointeurs : Ptr1++
* : opérateur de déréféren e = � valeur pointée par �
Frank Nielsen A3-56
Sémantiques di�érentes dé laration/ ode
Sémantiques di�érentes = sour e de onfusion !
◮Dé larations de variables :
◮T* ptrVar : variable de type �pointeur sur type T� passée par
valeur=adresse mémoire
◮T& refVar : variable de type T passée par référen e
◮T*& refPtrVar : variable de type �pointeur sur type T� passée
par référen e
◮Dans la partie instru tions de ode :
◮&Var : retourne l'adresse utilisée pour sto ker la valeur de Var
◮*Var : si type de Var est �pointeur sur�, retourne la valeur
sto kée à l'adresse ontenue dans Var (valeur de Var)
Mer i beau oup Leo ! Si pas (en ore) lair, demandez lui !
Frank Nielsen A3-57
#i n l u d e <ios t ream>
us i n g namespa e s td ;
i n t main ( ) {
i n t v a l 1 = 2015 , v a l 2 = 442 ;
i n t ∗ p1 , ∗ p2 ;
p1 = &va l 1 ; // p1 = adresse de val1
p2 = &va l 2 ; // p2 = adresse de val2
∗p1 = 2016 ; // valeur pointée par p1 = 2016
∗p2 = ∗p1 ; // valeur pointée par p2 = valeur pointée par p1
p1 = p2 ; // p1 = p2 (valeur du pointeur opiée)
∗p1 = 441 ; // valeur pointée par p1 = 441
out << " va l 1=" << va l 1 << end l ; // a� he 2016
out << " va l 2=" << va l 2 << end l ; // a� he 441
r e t u r n 0 ;
}
Frank Nielsen A3-58
int val1 = 2015, val2 = 442;
int * p1, * p2;
p1 = &val1; // p1 = adresse de val1
p2 = &val2; // p2 = adresse de val2
*p1 = 2016;
*p2 = *p1;
&val2&val1
2016 2016
p1 p2
Frank Nielsen A3-59
p1 = p2;
&val2&val1
2016 2016
p1 p2
Frank Nielsen A3-60
*p1 = 441;
&val2&val1
2016 441
p1 p2
Frank Nielsen A3-61
Pointeurs et tableaux
La valeur d'une variable tableau tab est l'adresse mémoire de son
premier élément
i n t tab [ 4 4 2 ℄ ;
i n t ∗ p t r ;
Le pointeur ptr est une variable qui sto ke une adresse mémoire
pour un int (4 o tets = 32 bits). On peut don faire :
p t r=tab ;
Un tableau est onsidéré omme un pointeur onstant . Il est don
interdit de faire :
tab=p t r ; // pas autorisé
Frank Nielsen A3-62
Amusons nous ! si si...
#i n l u d e <ios t ream>
us i n g namespa e s td ;
i n t main ( )
{
i n t tab [ 5 ℄ ;
i n t ∗ p ;
p = tab ; ∗p = 10 ;
p++; ∗p = 20 ;
p = &tab [ 2 ℄ ; ∗p = 30 ;
// arithmétique de pointeurs !
p = tab + 3 ; ∗p = 40 ;
// arithmétique de pointeurs déréféren ée !
p = tab ; ∗( p+4) = 50 ;
f o r ( i n t n=0; n<5; n++)
out << tab [ n ℄ << " " ;
r e t u r n 0 ; } // 10 20 30 40 50
Frank Nielsen A3-63
L'arithmétique de pointeurs
Soit T un type primitif ou un type objet
Un pointeur ptr de type T* est une variable sur une zone mémoire
de taille sizeof(T).
Lorsqu'on in rémente ptr (en faisant ptr++), on ajoute à la valeur
mémoire sizeof(T) :
doub l e tabd [5 ℄={1 ,2 , 3 , 4 , 5} , ∗ p t rd=tabd ;
har tab [5 ℄={ 'A ' , 'B ' , 'C ' , 'D ' , 'E ' } , ∗ p t r =tab
;
// a� he 8 (64 bits) et 1
e r r<< s i z e o f ( doub le ) <<" " << s i z e o f ( har ) <<
end l ;
// a� he 4 et E (attention aux indi es)
e r r<< ∗( tabd+3)<<" " << ∗( tab +4)<<end l ;
Frank Nielsen A3-64
L'arithmétique de pointeurs
T type objet
// Ma hine : 1 mot=8 o tets=64 bits
// 3 mots = 24 o tets
l a s s E l e v e { p u b l i :
s t r i n g nom , prenom ;
i n t groupe ;
} ;
// 2 mots=16=2x8 o tets
l a s s ma442{ p u b l i :
i n t nbE l e v e s ;
E l e v e ∗ p t r E l e v e ;
} ;
. . .
out<<s i z e o f ( E l e v e )<< ' '<<s i z e o f (ma442 )<<end l ;
Frank Nielsen A3-65
l a s s E l e v e { p u b l i :
s t r i n g nom , prenom ;
i n t g roupe ;
E l e v e ( s t r i n g n , s t r i n g p , i n t g )
{nom=n ; prenom=p ; groupe=g ; }
f r i e n d s t d : : o s t ream& ope r a t o r<< ( s td : : o s t ream& stream , on s t E l e v e& e )
{ s t ream <<e . nom<<" "<< e . prenom <<" " << e . groupe ; r e t u r n s t ream ;}
} ;
i n t main ( )
{
E l e v e l a s s e [2℄={ E l e v e ( "Frank " , " N i e l s e n " ,1) , E l e v e ( " C l aud i a " , "D '
Ambros io" ,2) } ;
E l e v e ∗ p t r= l a s s e ;
out<< ∗ p t r << end l << ∗( p t r++)<<end l ;
r e t u r n 0 ;
}
Frank Nielsen A3-66
L'arithmétique de pointeurs
Un ompilateur interpréte de manière non ambigüe le ode.
Order de priorité pour les opérateurs (revient à parenthéser
expli itement) :
++ est prioritaire sur *
-> est prioritaire sur *
Rappel : ptr-> hamps est équivalent à (*ptr). hamps
Que veut dire *ptr++ ?
⇒ *(ptr++)
Que veut dire *p++=*q++ ?
⇒ *p=*q; p=p+1; q=q+1;
Frank Nielsen A3-67
Les pointeurs de pointeurs
Rappel : Pointeur = variable qui a omme valeur la référen e
mémoire d'une autre variable.
doub le a ;
doub le ∗ b ;
doub le ∗∗ ;
doub le ∗∗∗ d ;
a=3.14159265;
b=&a ;
=&b ;
d=& ;
out<<b<<' \n '<< <<endl<<d<<<<end l ;
Frank Nielsen A3-68
Les pointeurs de pointeurs
double a;
double* b;
double** c;
double*** d;
a=3.14;
b=&a;
c=&b;
d=&c;
a b c
3.14 0x22aac0
0x22aac0
0x22aab8
0x22aab8
0x22aab0
0x22aab0 &d
d
Frank Nielsen A3-69
Les pointeurs void
Syntaxe : void *ptrVoid
◮un type spé ial de pointeurs : pointe sur une zone mémoire
non typée
◮pratique ar on peut pointer sur n' importe quel type de
variable (int, string, T)
◮... mais on peut pas déféren er ni même faire de l'arithmétique
de pointeurs (puisqu'on ne onnait pas sizeof(T)). Pour e
faire, on doit faire de la oer ion ( type asting ) : T*
ptrT=(T *)ptrVoid;
doub le tabd [5 ℄={1 ,2 , 3 , 4 , 5} , ∗ p t rd=tabd ;
e r r<< ∗( tabd+3)<<end l ; // a� he 4
har ∗ p t r 2=( har ∗) tabd ;vo i d ∗ d= ( p t r 2+3∗ s i z e o f ( doub le ) ) ; e r r <<(∗( doub le ∗) ( d ) )<<end l ; // // a� he 4
Frank Nielsen A3-70
Les pointeurs void
Utile lorsqu'on manipule des hièrar hies de lasses,
polymorphisme dynamique .
#i n l u d e <s t d l i b . h>
#i n l u d e <ios t ream >
us i ng namespa e s t d ;
doub le rand442 ( )
{ r e t u r n ( doub le ) rand ( ) / RAND_MAX;}
l a s s Polygon { p u b l i : i n t n ; s t r i n g name ; } ;
l a s s T r i a n g l e : p u b l i Polygon { p u b l i : T r i a n g l e ( ) {n=3;name=" t r i a n g l e "
; } } ;
l a s s Car re : p u b l i Polygon { p u b l i : Car re ( ) {n=4;name=" a r r e " ; } } ;
i n t main ( )
{
Polygon ∗ p t r ;
s rand ( t ime (NULL) ) ;
i f ( rand442 ( ) <0.5) p t r=new Car re ( ) ;
e l s e p t r=new T r i a n g l e ( ) ;
out<<" o t e s ="<< ptr−>n ;
r e t u r n 0 ; }
Frank Nielsen A3-71
Les pointeurs void
Utile lorsqu'on manipule des hièrar hies de lasses, passage de
pointeurs non-typées dans les fon tions, et .
#i n l u d e <s t d l i b . h>
#i n l u d e <ios t ream >
us i ng namespa e s t d ;
doub le rand442 ( )
{ r e t u r n ( doub le ) rand ( ) / RAND_MAX;}
l a s s Polygon { p u b l i : i n t n ; s t r i n g name ; } ;
l a s s T r i a n g l e : p u b l i Polygon { p u b l i : T r i a n g l e ( ) {n=3;name=" t r i a n g l e "
; } } ;
l a s s Car re : p u b l i Polygon { p u b l i : Car re ( ) {n=4;name=" a r r e " ; } } ;
i n t main ( )
{
vo i d ∗ p t r ;
s rand ( t ime (NULL) ) ;
i f ( rand442 ( ) <0.5) p t r=new Car re ( ) ;
e l s e p t r=new T r i a n g l e ( ) ;
Polygon ∗ p t r P o l y ;
p t rP o l y=(Polygon ∗) p t r ;
out<<" o t e s ="<< ptrPo ly−>n ;
r e t u r n 0 ; }
Frank Nielsen A3-72
Le pointeur NULL
◮ne pointe pas sur une référen e valide or une adresse mémoire :
double * ptr=NULL;
... else return new Noeud("feuille", NULL, NULL);
◮utile dans la onstru tion ré ursive de stru tures de données
(listes, arbres, graphes, matri es reuses, et .)
◮attention aux segmentation faults :
T ∗ p t r ; p t r=maFon t ionSuper442 ( ) ;
out<< (∗T)<<end l ;
Frank Nielsen A3-73
Les pointeur de fon tions
Un ode (disons une formule) est un � hier texte omme une
poésie ou un livre. Le ompilateur doit faire une analyse lexi ale
(mots lefs omme sin, exp ) puis syntaxique (véri�er que la formule
soit bien formée), et onstruit un arbre abstrait pour l'évaluation.
On pourrait rajouter au fur et à mesure des opérateur binaires
( omme des plugs-ins).
// pointeur de fon tions
i n t a d d i t i o n ( i n t a , i n t b )
{ r e t u r n ( a+b ) ; }
i n t s o u s t r a t i o n ( i n t a , i n t b )
{ r e t u r n ( a−b ) ; }
i n t o p e r a t e u r B i n a i r e ( i n t x , i n t y , i n t (∗f u n t o a l l ) ( i n t , i n t ) )
{ r e t u r n (∗ f u n t o a l l ) ( x , y ) ; }
Frank Nielsen A3-74
#i n l u d e <ios t ream>
us i n g namespa e s td ;
i n t a d d i t i o n ( i n t a , i n t b )
{ r e t u r n ( a+b ) ; }
i n t s o u s t r a t i o n ( i n t a , i n t b )
{ r e t u r n ( a−b ) ; }
i n t o p e r a t e u r B i n a i r e ( i n t x , i n t y , i n t (∗f u n t o a l l ) ( i n t , i n t ) )
{ r e t u r n (∗ f u n t o a l l ) ( x , y ) ; }
i n t main ( )
{ i n t m, n ;
m = o p e r a t e u r B i n a i r e (7 , 5 , a d d i t i o n ) ;
n = o p e r a t e u r B i n a i r e (20 , m, s o u s t r a t i o n ) ;
out <<n ;
r e t u r n 0 ; }
Frank Nielsen A3-75
Les dangers des pointeurs : dangling pointer
Un pointeur qui ne pointe sur rien : dangling pointer
i n t main ( )
{ i n t ∗ a r r a yP t r 1 ;
i n t ∗ a r r a yP t r 2 = new i n t [ 4 4 2 ℄ ;
a r r a yP t r 1 = a r r a yP t r 2 ;
d e l e t e [ ℄ a r r a yP t r 2 ;
// si on a de la han e quelque hose sinon
// une segmentation fault, dépend du tas
out << a r r a yP t r 1 [ 4 4 1 ℄ ;
r e t u r n 0 ; }
Nombreux e�ets de bords imprévisibles possibles : dépend de
l'historique de l'utilisation du tas (heap)
Frank Nielsen A3-76
Les dangers des pointeurs : zones non-a essibles
On peut réserver des zones mémoires qui ne seront plus a essibles :
i n t ∗ Ptr1= 2015 ;
i n t ∗ Ptr2 = 442 ;
Ptr1 = Ptr2 ;
Imaginez maintenant :
i n t ∗ Ptr1= new i n t [ 2 0 1 5 ℄ ;
i n t ∗ Ptr2 = 442 ;
Ptr1 = Ptr2 ;
out of memory !
Outil de visualisation dynamique et de suivi de la mémoire lors de
l'exé ution de programmes. http://valgrind.org/
Frank Nielsen A3-77
Les référen es et les alias
i n t v a l 1 =442;
i n t v a l 2 =2015;
// alias
i n t & r e fV a l 1=va l 1 ;
out<< r e fV a l 1 <<end l ; //442
r e f V a l 1=va l 2 ;
// i-dessous, le phénomène d'alias
out<< va l 1 <<end l ; //2015
Frank Nielsen A3-78
Passage par valeurs et passage par référen es
vo i d swap ( i n t& x , i n t& y )
{ i n t temp = x ; x = y ; y = temp ;}
vo i d swapPtr ( i n t ∗ Ptr1 , i n t ∗ Ptr2 )
{ i n t ∗ Ptr ; Pt r=Ptr1 ; Pt r1=Ptr2 ; Pt r2=Ptr ; }
vo i d swapGoodPtr ( i n t ∗ x , i n t ∗ y )
{ i n t temp = ∗x ; ∗x = ∗y ; ∗y = temp ;}
i n t main ( )
{
i n t a = 2 , b = 3 ;
swap ( a , b ) ; out<<a<<" "<<b<<end l ; // OK
a=2; b=3; i n t ∗ Ptra =&a ,∗ Ptrb =&b ;
swapPtr ( Ptra , Ptrb ) ;
out<<∗Ptra<<" "<<∗Ptrb<<end l ; // non !
swapGoodPtr ( Ptra , Ptrb ) ;
out<<∗Ptra<<" "<<∗Ptrb<<end l ; // oui !
Frank Nielsen A3-79
Pointeurs et référen es
◮une référen e est toujours dé�nie, d'un type donné, et ne peux
jamais hanger. Pas d'arithmétique de référen es ni de
oer ion.
◮en C++, passage par valeur ou par référen e : Si la valeur est
un pointeur, la fon tion pourra hanger le ontenu des ases
mémoires pointées, mais au retour de la fon tion, les pointeurs
arguments restent in hangés.
◮Passage par référen e ne opie pas l'objet sur la pile d'appel
des fon tions :
i n t f o n t i o nPa s sa g ePa rRe f ( on s t MaClasse&
l a s s eOb j e t ) { . . . }
Frank Nielsen A3-80
Un mauvais exemple d'utilisation des référen es
dangling referen e
i n t& v a r i a b l e L o a l e ( )
{ i n t x=442; r e t u r n x ; }
Ça ompile ave un message d'alerte (warning) :
I n f u n t i o n i n t& v a r i a b l e L o a l e ( ) :
p t r 12 . pp : 5 : 6 : a t t e n t i o n : r e f e r e n e to l o a l
v a r i a b l e x r e t u r n e d [−Wreturn−l o a l−addr ℄
{ i n t x=442; r e t u r n x ; }
Pour transformer es alertes en erreur de ompilation, faire g++
-Werror
Frank Nielsen A3-81
Pointeurs sur des stru tures en C (et par in lusion C++)
s t r u t monPoint { doub le x , y ; } ;
s t r u t monPoint p ; p . x=23; p . y =0.5 ;
s t r u t monPoint q = p ; /∗ op i e des
e n r e g i s t r eme n t s ∗/
On utilise souvent un typedef :
t y p e d e f s t r u t { doub le x , y ; } monPoint ;
monPoint p = {1 ,3} ;
Et on peut utiliser les pointeurs et les référen es sur les stru tures :
monPoint ∗ r = &p ;
(∗ r ) . x = 8 ;
r−>x = 8 ;
Frank Nielsen A3-82
Exer i e : la fon tion magique !
#i n l u d e <s t d i o . h>
i n t a = 23 ;
i n t f on t i onMag i que ( i n t b , i n t ∗p1 , i n t ∗p2 , i n t x ) {
i n t e ;
e = 14 ;
a = 15 ;
x = 16 ;
∗p1 = 17 ;
b = 18 ;
p2 = &b ;
∗p2 = 19 ;
r e t u r n b ;
}
i n t main ( ) {
i n t b = 10 , = 11 , d = 12 , e = 13 , f ;
f = fon t i onMag i que (b , & , &d , a ) ;
p r i n t f ( "%d\ t%d\ t%d\ t%d\ t%d\ t%d\n" , a , b , , d , e , f ) ;
// 15 10 17 12 13 19
r e t u r n 0 ;
}
Frank Nielsen A3-83
Résumé sur les pointeurs et référen es
& : opérateur de référen e = � adresse de �
* : opérateur de déréféren e = � valeur pointée par �
◮pointeurs : les valeurs = adresses mémoires. Sauvegarde une
référen e sur une autre variable.
◮pointeurs et tableaux (→ pointeurs onstants), pointeurs de
pointeurs, ...
◮arithmétique de pointeurs (ptr++, sizeof, ++ avant *)
◮pointeurs void pointe sur n'importe quel type mais ne
peut-être déréféren ée (→ oer ion, type asting)
◮pointeurs NULL
◮pointeurs de fon tions
◮pointeurs et mémoire du tas : dangling pointers (mémoire
désallouée → segmentation fault), plus a essible (garbage)
◮référen es : utile pour le passage d'arguments aux fon tions.
Pas d'arithmétique de référen es, de asting. Une référen e ne
hange jamais et ne peut être NULL
Frank Nielsen A3-84
Résumé A3
�X La lassi� ation : lasser des nouvelles données non-étiquetées
en apprenant un lassi�eur sur un jeu d'entraînement étiqueté.
�X Le lassi�eur ave la règle des k Plus Pro hes Voisins (PPVs) :
frontières de dé ision
�X évaluation : matri e de onfusion, pré ision, re all et F -s ore
�X l'apprentissage statistique (les Big Data !) : erreur de Bayes par
la règle optimale MAP (et la frontière de Bayes) , et l'analyse
asymptotique de la règle du PPV (au pire deux fois pire que
Bayes)
�X lassi�eur moins �gros� en taille mémoire, en O(drc) au lieu de
O(dn), en utilisant les r -moyennes sur haque lasse
�X Presque tout sur les pointeurs et référen es !
Pour la pro haine fois : lire le hapitre 9 et re-re-lire le hapitre
2 sur le MPI du poly opié
Frank Nielsen A3-85
Recommended