SUR LE CALCUL DE LA FONCTION DE CHRISTOFFEL EMPIRIQUE … · 4 tran duy nghi benoÎt 15 10 30 80 210 460 950 950 950 1850 1850 1850 3570 3570 3570 6860 6860 6860 13810 13810 30670

SUR LE CALCUL DE LA FONCTION DE CHRISTOFFEL EMPIRIQUE

par

Tran Duy Nghi Benoît

Résumé. — On poursuit le travail effectué dans [4] et [5] en ce qui concerne l’utilisation de la fonction de Christoffelempirique à la détection de données aberrantes. Dans ces articles, l’inverse de la fonction de Christoffel empiriqueest utilisé comme score pour effectuer une détection de donnée aberrantes. Toutefois en grande dimension, le calculde la fonction de Christoffel empirique est impossible par inversion de la matrice des moments. Dans ce mémoire onrappelle d’abord comment la fonction Christoffel empirique, évaluée en un point, peut être vue comme la solutiond’un problème quadratique convexe sous une contrainte affine. Ensuite on présentera un algorithme de descente decoordonnées dans le but d’étendre les résultats numériques pour la détection de données aberrantes obtenus dans[4] et [5] à des dimensions où l’inversion de la matrice des moments n’est plus concevable.

Table des matières

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12. Notations et premières propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23. La fonction de Christoffel empirique en apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44. Une descente de coordonnées par blocs aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75. Application à la détection de données aberrantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136. Tentatives d’extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157. Note finale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Appendice A. Implémentations en Julia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1. Introduction

Dans les articles [4] et [5], Lasserre et Pauwels utilisent un nouvel outil, la fonction de Christoffel empirique,dans le contexte de l’apprentissage machine. Cette fonction peut être définie comme l’inverse d’une fonctionpolynômiale impliquant l’inverse (quand elle existe) d’une matrice de très grande taille, la matrice des moments.La propriété remarquable mais encore inexploitée avant ces articles est que les lignes de niveaux de la fonctionde Christoffel (empirique) semblent bien épouser la forme d’un nuage de points donné (voir la section 2).

Dans ces mêmes articles, Lasserre et Pauwels exhibent plusieurs pistes d’applications de leur approche, l’uned’entre elles étant la détection de données aberrantes. Dans [4], on montre qu’en un certain sens la valeur dela fonction de Christoffel (empirique) quantifie la proportion de la masse contenue dans un sous-niveau : cetteremarque a motivé les auteurs à utiliser la valeur de la fonction de Christoffel empirique en un point commescore servant à déterminer si ce point est une donnée aberrante ou non. Cette démarche a donné des résultatsintéressants pour des données de petites dimensions toutefois, nécessitant l’inversion de la matrice des moments(qui est de taille exponentielle en la dimension des données), cette approche est rapidement limité.

Dans ce mémoire, après avoir présenté plus en détails les différents objets mentionnés, on rappellera com-ment la fonction de Christoffel empirique évaluée en un point peut être vue comme la solution d’un problèmequadratique convexe de très grande taille.

L’apport de ce mémoire au sujet est le développement d’un algorithme de descente de coordonnées qui a laparticularité de minimiser exactement la fonction objectif en m coordonnées : l’inversion de la matrice momentsn’étant plus possible du fait de sa taille, on se ramènera à inverser une matrice de taille m, construite à partir de

2 TRAN DUY NGHI BENOÎT

la matrice des moments. Cette approche est évidemment sous-optimale dans les cas où l’inversion de la matricedes moments est possible mais permet d’étendre l’approche utilisée dans [4] et [5], lorsque cette inversion esttrop coûteuse.

Après avoir présenté en détail le dît algorithme, on effectuera une analyse de sa convergence, nouvelle maisfortement inspirée de [8] (voir la section 4). En section 5 on détaillera comment la fonction de Christoffelempirique est utilisée pour la détection de donnée aberrantes et on illustrera cette méthode sur un jeu dedonnées d’intrusion informatique de petites dimensions (aussi utilisé dans [4]) que l’on obtient après une premièreimplémentation de notre algorithme.

Cette première implémentation suppose en général qu’on est dans un régime intermédiaire où il est possiblede sauvegarder la matrice des moments mais où son inversion est trop coûteuse. Enfin nous verrons en section6 comment construire une seconde implémentation permettant d’attaquer le régime où il n’est plus possible desauvegarder la matrice des moments mais seulement quelques colonnes, on terminera sur quelques remarquesautour d’autres pistes d’extensions encore infructueuses.

2. Notations et premières propriétés

Dans ce qui suit p désignera un entier fixé, d un entier fixé, on notera s(d) la dimension de l’espace vectorielR[X]d des polynômes à p variables de degré total inférieur ou égal à d. Afin de représenter un élément de R[X]dpar un vecteur contenant ses coefficients, on commence par munir les monômes de R[X]d par une relation d’ordretotale.

Définition 2.1. — Avec les notations précédentes, on identifie un monôme à p variables de degré inférieur àd à son p-uplet de puissances. On notera Npd l’ensemble des p-uplets de somme inférieur à d, la relation binaire� définie pour tous monômes α, β ∈ Npd par

α � β ⇐⇒ |α|(1) > |β| ou (|α| = |β| et la première coordonnée non-nulle de α− β est strictement négative)

est une relation d’ordre totale sur les monômes à p-variables de degré inférieur à d appelée ordre lexicographiquegradué.

Exemple 2.2. — Pour p = 3 et d = 2, une énumération des monômes rangés par ordre croissant selon l’ordrelexicographique gradué est :

1 � X1 � X2 � X3 � X21 � X1X2 � X1X3 � X2

2 � X2X3 � X23 .

On représentera ainsi un polynôme P ∈ R[X]d par un vecteur p ∈ Rs(d) contenant ses coefficients où on aordonné les monômes selon l’ordre lexicographique gradué. En outre pour tout x ∈ Rp on notera vd(x) ∈ Rs(d)le vecteur contenant les évaluations des monômes (toujours rangés par le même ordre) : on peut ainsi écrire quepour tout x ∈ Rp,

P (x) = vd(x)Tp.

Un résultat essentiel pour la suite concerne la taille de ces vecteurs qui comme on va le voir, sont gigantesques.Une autre preuve de ce résultat, basée sur l’unicité du développement en série entière, se trouve dans [2, pages58-59].

Lemme 2.3. — La dimension de l’espace vectoriel R[X]d est égale à(p+dp

)=: s(d).

Démonstration. — Une base de R[X]d est formée des monômes à p variables de degré total inférieur ou égal àd. De plus, pour tous entiers p et k le nombre de monômes unitaires à p variables de degré égal à k est égal à(p+k−1p−1

)car l’application

{α ∈ Nn|∑ni=0 αi = k} −→ {Suites strictement croissantes de longueur n− 1 dans {0, 1, . . . , k + n− 2}}

α 7−→ (α1, α1 + α2 + 1, α1 + α2 + α3 + 2, . . . , α1 + . . .+ αn−1 + (n− 2)),

(1)Pour tout α ∈ Npd, |α| :=

∑pi=1 αi.

SUR LE CALCUL DE LA FONCTION DE CHRISTOFFEL EMPIRIQUE 3

est une bijection. On en déduit que s(d) =∑dk=0

(p+k−1p−1

)et on conclut par la formule de Pascal ainsi qu’une

récurrence immédiate :(p+ d

d

)=

(p+ d− 1

p− 1

)+

(p+ d− 1

p

)(Formule de Pascal)

=

(p+ d− 1

p− 1

)+

(p+ d− 2

p− 1

)+

(p+ d− 2

p

)(Formule de Pascal)

= . . .

=

d−1∑k=0

(p+ d− k − 1

p− 1

)+

(p

p

)

=

d∑u=0

(p+ u− 1

p− 1

)(Changement de variable u = d− k).

Maintenant considérons une mesure de probabilité µ sur Rp, la connaissance des moments de cette loi nousdonne des informations sur son comportement (en dimension p = 1 on définit ainsi la moyenne, l’écart-type,...)et un moyen commode de stocker cette information est de définir sa matrice des moments d’ordre d. On utiliserala notation usuelle des multi-indices : on écrira xα pour xα1

1 · · ·xαpp .

Définition 2.4. — On suppose que tous les moments de la mesure µ existent et sont finis. On définit la matricedes moments d’ordre d de la mesure µ par :

Mµ(d) := (Mα,β)α,β∈Npd

où Npd désigne l’ensemble des monômes à p variables de degré total inférieur à d rangés dans l’ordre lexicogra-phique gradué croissant et Mα,β :=

∫Rp x

α+β dµ(x) est le moment d’ordre α+ β de la mesure µ.

Par la suite, on se placera toujours sous l’hypothèse suivante pour la mesure µ et l’entier d.

Hypothèse 2.5. — On suppose que µ est une mesure de probabilité sur Rp telle que ses moments à tout ordresoient finis et telle que sa matrice des moments Mµ(d) soit symétrique définie positive.

Remarque 2.6. — L’hypothèse précédente est notamment vérifiée pour µ à support inclus dans un compactet qui est strictement positive sur un ouvert non-vide.

De l’inverse de la matrice des moments, sous réserve qu’elle existe, on définit une fonction polynomialecentrale dans ce qui suit ainsi que l’objet clef de ce mémoire, la fonction de Christoffel.

Définition 2.7. — Soit d un entier fixé. On suppose la matrice des moments Mµ(d) est inversible.On notera Qµ,d le polynôme de degré 2d définit pour tout x ∈ Rp par

Qµ,d(x) := vd(x)TMd(µ)−1vd(x).

De plus l’applicationΛµ,d : Rp −→ R

x 7−→ 1Qµ,d(x)

est appelée la d-ème fonction de Christoffel. On parlera parfois de la fonction de Christoffel sans préciser leparamètre d associé.

L’observation clef qui a motivé Lasserre et Pauwels à étudier la fonction de Christoffel est la suivante : soitz = (z1, . . . , zn) un n-échantillon tiré selon la loi µ, les lignes de niveaux du polynôme Qµ,d (l’inverse de lafonction de Christoffel) "épouse bien" la forume du nuage de points z.

Exemple 2.8. — Voici un exemple tiré de [4] pour p = 2 et d = 8. On observe que plus la ligne de niveaucorrespond à une valeur élevée de Qµ,d et plus le sous-niveau de cette même valeur contient de points del’échantillon.


15 10

30

80

210 460

950

950

950

1850

1850

185

0

3570

3570

357

0

6860

6860

686

0

13810

13810 138

10

30670

306

70

67380

673

80

146370

146

370

333340

333

340

Figure 1. 1000 points générés selon une même loi et en noir diverses lignes de niveaux de l’inverse dela fonction de Christoffel, en rouge la ligne de niveau associée à la valeur moyenne de cet inverse.

3. La fonction de Christoffel empirique en apprentissage

On conserve les notations précédemment introduites. Remarquons tout d’abord que l’application

〈·, ·〉µ : Rs(d) × Rs(d) −→ R(q1, q2) 7−→ qT1 Md(µ)q2

est un produit scalaire sur Rs(d) car sous l’hypothèse 2.5 la matrice Md(µ) est symétrique définie positive. Enremarquant maintenant que pour tous polynômes Q1, Q2 ∈ R[X]d, en notant q1, q2 ∈ Rs(d) les vecteurs decoefficients associés : ∫

RpQ1(x)Q2(x) dµ(x) = qT1 Md(µ)q2 = 〈q1, q2〉µ.

On en déduit facilement que :

〈·, ·〉µ : R[X]d × R[X]d −→ R(Q1, Q2) 7−→

∫Rp Q1(x)Q2(x) dµ(x)

définit aussi un produit scalaire sur R[X]d. On notera ainsi indifféremment 〈·, ·〉µ pour désigner le produitscalaire sur Rs(d) et celui sur R[X]d que l’on vient d’introduire.

Nous allons voir que le polynôme Qµ,d s’exprime comme une somme de carré de polynômes orthogonauxpour ce produit scalaire.

Proposition 3.1. — Il existe une unique famille de polynômes orthogonaux {Pα}α∈Npd ordonnée par l’ordrelexicographique gradué vérifiant pour tout α ∈ Npd

∀β ∈ Npd, 〈Pα, Pβ〉µ = δαβ ,(1)

∀β � α, 〈Pα, Xβ〉µ = 0,(2)〈Pα, Xα〉µ > 0.(3)


Démonstration. — D’après ce qui précède, 〈·, ·〉µ est un produit scalaire sur Rs(d). On en déduit par le théorèmede Gram-Schmidt [6, Théorème 13.4.22 et Remarque 13.4.23] appliqué à la base canonique (ei)1≤i≤s(d) de Rs(d)

l’existence d’une unique base (pi)1≤i≤s(d) telle que

(1) Pour tout i 6= j, on a 〈pi, pj〉µ = δij ,(2) Pour tout 1 ≤ k ≤ s(d), on a Vect(e1, . . . , ek) = Vect(p1, . . . , pk),(3) Pour tout 1 ≤ k ≤ s(d), on a 〈pk, ek〉µ > 0.

On conclut en considérant la famille de polynômes (Pα)α∈Npdassociés à (pi)1≤i≤s(d).

Lemme 3.2. — Sous l’hypothèse 2.5 le polynôme Qµ,d est la somme des polynômes orthogonaux {Pα} vérifiant(1), (2) et (3) :

Qµ,d =∑α∈Npd

P 2α.

Démonstration. — On retranscrit ici la preuve de [4, Lemme 2].Notons Dd(µ) ∈ Ms(d) (R) la matrice triangulaire inférieure dont les lignes sont formées des vecteurs pi,

1 ≤ i ≤ s(d) définis dans la preuve de la proposition 3.1. De même que dans cette proposition, on notera Pα lespolynômes associés rangés par l’ordre lexicographique gradué.

Des points 1, 2 et 3 on en déduit que la matrice Dd(µ) est bien triangulaire inférieure et qu’elle est de plusà coefficients strictement positifs sur sa diagonale, elle est donc inversible.

Remarquons que Dd(µ)Md(µ)Dd(µ)T = I, où I désigne la matrice identité deMs(d) car pour tous α, β ∈ Npddeux monômes quelconques (identifiés à leur p-uplet de puissances), on a par construction des polynômes Pα(

Dd(µ)Md(µ)Dd(µ)T)α,β

= 〈Pα, Pβ〉µ = δαβ .

On en déduit que Md(µ) = Dd(µ)−1(Dd(µ)T

)−1 et que Md(µ)−1 = Dd(µ)TDd(µ). Enfin, par définition ona pour tout x ∈ Rp, Qµ,d(x) = vd(x)TMd(µ)−1vd(x) et donc :

Qµ,d(x) =

s(d)∑i=1

(pTi vd(x)

)T (pTi vd(x)

)=∑α∈Npd

P 2α(x).

On obtient le résultat central dans le cadre de ce mémoire : la fonction de Christoffel évaluée en un pointpeut être vue comme la solution d’un problème d’optimisation quadratique convexe sous une contrainte affine.

Théorème 3.3. — Supposons que µ vérifie l’hypothèse 2.5. Fixons x ∈ Rp. On a

Λµ,d(x) = minP∈Rd[X]P (x)=1

∫RpP (x)2 dµ(x) = min

p∈Rs(d)pT vd(x)=1

pTMµ(d)p.

Démonstration. — On retranscrit ici la preuve de [4, Théorème 2].Fixons x ∈ Rp. Soit P ∈ R[X]d un polynôme tel que P (x) = 1. On utilisera encore la notation (Pα)α∈Npd

pour désigner la famille de polynôme définie dans la proposition 3.1. Notons aα les coefficients du polynômeP décomposé dans la base (Pα)α∈Npd

ordonnée par l’ordre lexicographique gradué. Pour tout α ∈ Npd on aaα = 〈P, Pα〉µ et par orthonormalité de la base (Pα)α∈Npd

:

〈P, P 〉µ =∑α∈Npd

a2α.


Enfin en notant a ∈ Rs(d) (respectivement b ∈ Rs(d)) le vecteur contenant les aα (respectivement les Pα(x))rangés par ordre lexicographique gradué, on a

1 = (P (x))2

=

∑α∈Npd

aαPα(x)

2

= 〈a, b〉2

≤ ‖a‖22 ‖b‖22 (Cauchy-Schwarz)

=

∑α∈Npd

a2α

∑α∈Npd

Pα(x)2

= 〈P, P 〉µQµ,d(x),

avec égalité si, et seulement si, a et b sont colinéaires, i.e. si, et seulement si pour tout α ∈ Npd,

aα =Pα(x)

Qµ,d(x).

On a donc montré que tout polynôme P ∈ R[X]d tel que P (x) = 1, vérifie la minoration∫RpP (x)2 dµ(x) = 〈P, P 〉µ ≥ 1,

et que cette minoration est une égalité pour le polynôme

P ∗ :=1

Qµ,d(x)

∑α∈Npd

Pα(x)Pα.

Remarque 3.4. — Si on note P ∗ la solution du problème de minimisation intervenant dans le théorème 3.3alors P ∗(x) = 1 et par l’inégalité de Markov

µ{x ∈ Rp |P ∗(x)2 ≤ 1

}= 1− µ

{x ∈ Rp |P ∗(x)2 > 1

}> 1− Λµ,d(x)

1.

On en déduit que plus l’inverse de la Christoffel en x est grand et plus la proportion de la masse de la mesurecontenue dans le sous-niveau {x ∈ Rp | P ∗(x)2 > 1} est élevée.

Dorénavant on se placera dans un contexte où on ne connait pas la loi µ directement mais qu’on a accès à unn-échantillon z = (z1, . . . , zn) tiré selon µ. On considère la mesure empirique associée, notée µn, définie par :

µn =1

n

n∑i=1

δzi ,

et on appelle fonction de Christoffel empirique la fonction de Christoffel associé à la mesure µn. Le théorèmesuivant fait un lien entre la fonction de Christoffel empirique et la fonction de Christoffel d’une mesure deprobabilité µ à support compact : uniformément en x ∈ Rp on a convergence presque sûre de la fonction deChristoffel empirique vers la fonction de Christoffel lorsque la taille n de l’échantillon tend vers l’infini.

Théorème 3.5. — Soit µ une mesure de probabilité sur Rp à support compact et soit un entier d tel que lamatrice des moments Mµ(d) soit inversible. On a

supx∈Rp

|Λµn,d(x)− Λµ,d(x)| p.s.−→n−→+∞

0.

Démonstration. — [5, Théorème 3.11].

Remarque 3.6. — Pour plus de détail quant à l’observation sur la forme bien adaptée des sous-niveaux parrapport au nuage de points, nous referons à [5] : on y montre notamment dans des cas particuliers de mesuresµ à support compact, qu’une certaine suite de sous-niveaux de la fonction de Christoffel tend, pour la distancede Haussdorf, vers le support de la mesure µ. Une application de ce résultat est l’utilisation de la fonction deChristoffel empirique pour estimer le support d’une mesure.


Toutefois le travail effectué durant ce stage s’est orienté sur une autre application de la fonction de Christoffelempirique, basée sur le théorème 3.3 et motivée par la remarque 3.4, la détection de données aberrantes. Dansles articles [4] et [5], Lasserre et Pauwels utilisent l’inverse de la fonction de Christoffel empirique comme scorepour effectuer de la détection de données aberrantes : les points ayant un score supérieur à un certain seuil sontclassés aberrants et ceux en dessous de ce seuil sont classés comme réguliers. On est donc amené à calculer lafonction de Christoffel en un point donné de Rp. Toutefois dans [4] et [5] ce calcul est effectué par inversion dela matrice des moments, aussi les résultats numériques obtenues ont seulement été obtenues pour des valeursde la dimension p inférieures à 3.

Nous présentons en section 3 un algorithme de descente de coordonnées utilisant le théorème 3.3 pour calculerla fonction de Christoffel empirique. Ensuite en section 4 nous présentons avec plus de détails le problème dedétection de données aberrantes et nous vérifions que le calcul de la fonction de Christoffel empirique par cetteméthode donne des résultats comparables à ce qui a été effectué par Lasserre et Pauwels. Enfin en section 5nous présentons deux tentatives, infructueuses, d’extension de l’algorithme de descente précédemment introduitqui auraient permis de généraliser les résultats de Lasserre et Pauwels à de grandes dimensions.

4. Une descente de coordonnées par blocs aléatoires

On veut calculer la fonction de Christoffel empirique définie dans la section précédente dans un contexte oùl’inversion de la matrice des moments n’est plus possible (dimension trop grande, mauvais conditionnement).Le théorème 3.3 nous suggère d’étudier le problème général suivant.

Soit N un entier, on considère le problème d’optimisation suivant

(P0) minxT v=1

f0(x) := xTAx,

où x désigne un élément de RN , v un élément fixé non-nul de RN tel que v1 = 1 et A = (aij)1≤i,j≤N−1une matrice symétrique définie positive d’ordre N telle que a11 = 1.

Problème (P0)

Remarque 4.1. — Ces hypothèses sur le vecteur v et la matrice A sont naturelles au vu de la section précé-dente, en effet :

– pour tout x ∈ Rp, la première composante de vd(x) est égale à 1,– la matrice des moments d’une mesure empirique est toujours symétrique et presque sûrement inversible si,

par exemple, la mesure associée est strictement positive sur un ouvert non-vide de Rp et qu’on tire indépen-damment plus de sd :=

(p+dp

)points.

Dans un premier temps on reformulera ce problème d’optimisation dans RN avec une contrainte affine commeun problème d’optimisation dans RN−1 sans contrainte, puis on définira et analysera un algorithme de descentepour attaquer la reformulation du problème.

4.1. Reformulation du problème. — Remarquons qu’à x ∈ RN fixé on a xT v = 1 si, et seulement si,x1 = 1 −

∑Ni=2 xivi. Autrement dit, un point x ∈ RN est admissible pour le problème (P0) si, et seulement si,

il existe y ∈ RN−1 tel que

x =

1−

∑N−1i=1 yivi+1

y1...

yN−1

.

De plus découpons la matrice A de la façon suivante :

A =

(a11 AT1A1 A

)où

– A1 ∈ RN−1 désigne la première colonne de la matrice A0 sans son premier coefficient A11,– A ∈ MN−1(R) désigne la matrice A privée de sa première ligne et colonne. Notons que la matrice A est

encore symétrique définie positive.– Rappelons qu’on a supposé a11 = 1.


On reformule le problème d’optimisation dans RN sous une contrainte affine (P0) en un problèmed’optimisation dans RN−1 sans contrainte :

(P ) miny∈RN−1

f(x) := 〈y, w〉+ yTBy.

où, en notant v = (v2, . . . , vN ) ∈ RN−1 :– w := 2 (A1 − v) est un vecteur de RN−1,– B := vvT + A− A1v

T − vAT1 est une matrice symétrique réelle d’ordre N − 1. On verra plus loin àla proposition 4.4 qu’elle est même définie positive.

Problème (P)

Remarque 4.2. — Par reformulation on entend ici :– qu’il existe une bijection entre l’ensemble des solutions du problème (P0) et les solutions du problème (P ),– que la valeur du problème (P0) s’obtient simplement en ajoutant 1 à la valeur du problème (P ).

Le fait que le problème (P ) est une reformulation du problème (P0) découle du lemme suivant.

Lemme 4.3. — Pour tout point x ∈ RN admissible pour le problème (P0), il existe un unique point y ∈ RN−1tel que

f0(x) = 1 + 〈y, w〉+ yTBy,

où– w := 2 (A1 − v) est un vecteur de RN−1,– B := vvT +A−A1v

T − vAT1 est une matrice symétrique réelle d’ordre N − 1.En outre le problème (P ) est une reformulation du problème (P0) au sens de la remarque 4.2.

Démonstration. — Pour tout point admissible x on a :

f0(x) = xTAx

=

(1−

N−1∑i=1

yivi+1, y1, . . . , yN−1

)A

(1−

N−1∑i=1

yivi+1, y1, . . . , yN−1

)T

=

(1−

N∑i=1

yivi+1

)2

+ yT Ay + 2

(1−

N−1∑i=1

yivi+1

)〈y,A1〉.

Rappelons que v := (v2, . . . , vN ) ∈ RN−1, on obtient :

f0(x) = (1− 〈y, v〉)2 + yT Ay + 2 (1− 〈y, v〉) 〈y,A1〉

= 1 + 〈y, 2 (A1 − v)〉+ yT(vvT + A− vTA1 − vAT1

)y

= 1 + 〈y, w〉+ yTBy.

Les deux fonctions valeurs du problème (P ) et du problème (P0) sont donc égales à l’addition ou soustractiond’un terme constant égal à 1. En outre l’application

φ : RN−1 −→ RN

y 7−→

1−

∑N−1i=1 yivi+1

y1...

yN−1

,

est une bijection entre les points admissibles du problème (P ) et les points admissibles du problème (P0), enparticulier c’est une bijection entre les solutions des deux problèmes.

Proposition 4.4. — Les fonctions objectifs f0 et f des problèmes (P0) et (P ) sont 2λmin(A)-fortement convexesavec λmin(A) désignant la plus petite valeur propre de A. En outre le problème (P0) (respectivement (P )) admetune unique solution que l’on notera x∗ (respectivement y∗) et la matrice B est symétrique définie positive.


Démonstration. — Montrons que la fonction f0 est 2λmin(A)-fortement convexe.Soit x1, x2 deux éléments distincts de RN , on a

〈∇f0(x2)−∇f0(x1), x2 − x1〉 = 2‖x2 − x1‖22 〈Ax2 − x1‖x2 − x1‖2

,x2 − x1‖x2 − x1‖2

〉

≥ 2λmin(A) ‖x2 − x1‖22,

d’où le résultat.Montrons que f est aussi, "au moins", 2λmin(A)-fortement convexe. L’idée est que f et f0 sont les fonctions

objectifs de deux reformulations d’un même problème, f prenant directement en compte la contrainte affine etnon f0. Plus précisément on a pour tout y ∈ RN−1, en utilisant la fonction φ définie dans la preuve du lemme4.3,

f0 (φ(y)) = 1 + f(y)⇐⇒ f(y) = f0 (φ(y))− 1.

On en déduit que pour tous y1 6= y2 ∈ RN−1, on a par différenciation des fonctions composées

〈∇f(y2)−∇f(y1), y2 − y1〉 = 〈∇f0 (φ(y2))−∇f0 (φ(y1)) , Dφ(y2 − y1) · (y2 − y1)〉= 〈2A (φ(y2)− φ(y1)) , φ(y2)− φ(y1)〉≥ 2λmin(A) ‖φ(y2)− φ(y1)‖22

= 2λmin(A)

(|N−1∑i=1

vi+1(y1,i − y2,i)|2 + ‖y2 − y1‖22

)≥ 2λmin(A) ‖y2 − y1‖22,

d’où le résultat.Enfin il reste à montrer que la matrice B est symétrique définie positive. Or, on vient de voir que la fonction

objectif f(y) = yTBy+ 〈w, y〉 du problème (P ) est une forme quadratique fortement convexe. En outre elle eststrictement convexe ce qui implique que B est symétrique définie positive.

4.2. Un algorithme pour résoudre le problème (P ). — L’algorithme suivant et son analyse sont forte-ment inspirés de ce qui est fait dans [8] pour la descente de coordonnée stochastique à des blocs de coordonnéesstochastiques.

L’idée est de démarrer du point admissible y0 = 0RN−1 puis à l’itération k ∈ N∗ de minimiser la fonctionobjectif f selon m-coordonnées, les autres étant fixées, tirées aléatoirement au point courant yk−1, où m ≥ 1est un entier fixé, et de considérer comme nouvelle itérée la solution de ce sous-problème.

Plus précisément, fixons dans ce qui suit un entier m ≥ 1. A l’itération k on effectue un tirage uniforme parmi{1, . . . , N} de m coordonnées distinctes indépendamment des tirages précédents. On note les coordonnées tiréesà l’itération k, ik1 , . . . ikm et on définit la matrice

Uk :=(eik1 | . . . | eikm

)∈MN×m(R),

qui est la concaténation de m vecteurs de la base canonique de RN−1. A l’itération k ≥ 1, on voudrait minimiserla fonction objectif f au point yk−1 selon les m coordonnées tirées, c’est-à-dire qu’on voudrait résoudre leproblème d’optimisation dans Rm suivant

(Pm(k)) minα∈Rm

f(yk−1 + Ukα

).

Maintenant pour tout α ∈ Rm un calcul direct donne :

f(yk−1 + Ukα

)= 〈yk−1 + Ukα,w〉+

(yk−1 + Ukα

)TB(yk−1 + Ukα

)= 〈yk−1, w〉+ 〈Ukα,w〉+ (yk−1)TByk−1 + (yk−1)TBUkα+ (Ukα)

TByk−1 + (Ukα)

TBUkα.

= f(yk−1

)+ 〈α, wk〉+ αT Bkα,

où on a posé– wt := UTk w+ 2UTk By

k−1, un vecteur de Rm composé de m composantes des vecteurs w et de la matrice Bdéfinissant le problème (P ),

– Bk := UTk BUk, la matrice symétrique d’ordre m qui est une troncature de la matrice B : on ne garde queles lignes et colonnes ik1 , . . . , ikm pour construire Bk.


Remarquons que la matrice B étant définie positive, Bk l’est aussi et en outre la fonction objectif du problème(Pm(k)) est strictement convexe.

On en déduit que le problème (Pm(k)) admet une unique solution et α∗k est la solution de (Pm(k)) si, etseulement si, 2Bkα

∗k + wk = 0 i.e. si, et seulement si,

α∗k = −1

2

(Bk

)−1wk.

On peut maintenant définir formellement notre algorithme de Descente de Coordonnées par Blocs Aléatoires(DC-BA) pour le problème (P ).

Algorithme 4.5 (Descente de Coordonnées par Blocs Aléatoires (DC-BA))On choisit un entier K ≥ 1 correspondant au nombre d’itérations qu’on effectuera.Pour k = 0,– Poser y0 := 0RN−1 .

Pour k allant de 1 à K,– Tirer uniformément parmi {1, . . . , N}, m coordonnées distinctes indépendamment des tirages précédents.– Calculer le vecteur wk := UTk w + 2UTk By

k−1 et la matrice Bk := UTk BUk.

– Calculer le pas optimal α∗k := − 12

(Bk

)−1wk.

– Poser :yk := yk−1 + Ukα

∗k,

avec Uk :=(eik1 | . . . | eikm

)∈ MN×m(R), qui est la concaténation de m vecteurs de la base canonique de RN−1.

Notez que cette opération ne mets à jour que m coordonnées du vecteur courant.Une implémentation de DC-BA est disponible en annexe A.1.

Analysons l’algorithme (DC-BA). Déjà remarquons que la forte convexité de la fonction objectif f donne lelemme suivant :

Lemme 4.6. — Il existe un réel R0 > 0 tel que

supy∈RN−1

{‖y − y∗‖ | f(y) ≤ f(y0)} ≤ R0.

Démonstration. — Posons C := {y ∈ RN−1 | f(y) ≤ f(y0)}. Montrons que C est fermé et borné dans RN−1 cequi montrera que C est compact.

– C est fermé car f est continue sur RN−1.– C est borné. Supposons par l’absurde que C n’est pas borné. La fonction f étant 2λmin(A)-fortement

convexe, pour tout y ∈ RN−1 on a,

f(y) ≥ f(y0)

+ 〈∇f(y0), y − y0〉+ λmin(A)‖y − y0‖22.

Le terme de droite tendant vers +∞ lorsque ‖y‖2 tend vers l’infini on obtient une contradiction.Enfin l’application y ∈ RN−1 7→ ‖y − y∗‖ ∈ R est continue sur le compact C, elle est donc bornée et atteint

ses bornes. D’où l’existence de R0 > 0 souhaité.

On a convergence linéaire de l’algorithme (DC-BA) vers la solution y∗ du problème (P ).

Théorème 4.7. — Soit R0 > 0 tel que supy∈RN−1{‖y − y∗‖ | f(y) ≤ f(y0)} ≤ R0. La suite (yk)k∈N de RN−1générée par l’algorithme (DC-BA) vérifie pour tout k ≥ 1 :

E[f(yk)]− f(y∗) ≤ 4Nλmax(B)R20

m· 1

k,(4)

E[f(yk)]− f(y∗)

E[f(yk−1)]− f(y∗)≤ 1− mλmin(B)

Nλmax(B),(5)

où l’espérance est prise sur tous les tirages de coordonnées.

Démonstration. — On va procéder en 5 étapes :Première étape - On va contrôler une itération de (DC-BA) en utilisant le fait que l’on sait contrôler une

itération d’un pas de gradient grâce à la formule de Taylor avec reste intégral.Deuxième étape - On va considérer le meilleur pas de gradient afin d’obtenir un contrôle sur une itération

de (DC-BA) indépendant du pas de gradient choisit.


Troisième étape - On utilise l’étape précédente pour construire une borne sur l’écart moyen entre les imagesde nos itérées et la valeur optimale du problème, faisant intervenir E[ ‖∇f

(yk−1

)‖22 ].

Quatrième étape - On utilise la convexité de f , le lemme 4.6 (qui utilise implicitement la forte convexitéde f) pour contrôler E[‖∇f

(yk−1

)‖] et en déduire (4) par l’inégalité de Jensen.

Cinquième étape - On utilise qu’on connaît explicitement la constante de forte convexité de f pour contrô-ler directement ‖∇f

(yk−1

)‖2 et en déduire (5).

Cette démonstration est une adaptation mineure de [8, Théorème 1] en remarquant qu’une minimisationexacte en m coordonnées est toujours meilleure qu’un pas de gradient en ces mêmes m coordonnées.

Première étape - Fixons un entier k ≥ 1. Par construction de (DC-BA), pour tout réel γk > 0 on a

(6) f(yk)

= f(yk−1 + Ukα

∗) ≤ f (yk−1 − γkUkUTk ∇f (yk−1)) .Puis on applique la formule de Taylor avec reste intégral à l’ordre 1 au terme de droite :

f

yk−1 − γkUkUTk ∇f (yk−1)︸︷︷︸:=h

= f(yk−1

)− 〈∇f

(yk−1

), h〉+

∫ 1

0

(1− s)k hT Hessf(yk−1 + sh

)︸︷︷︸=2B

hds

= f(yk−1

)− γk〈UTk ∇f

(yk−1

), UTk ∇f

(yk−1

)〉+

2

∫ 1

0

(1− s) ds · γ2k(UkU

Tk ∇f

(yk−1

))TB(UkU

Tk ∇f

(yk−1

))= f

(yk−1

)− γk‖UTk ∇f

(yk−1

)‖22 + γ2k〈UTk ∇f

(yk−1

), BkU

Tk ∇f

(yk−1

)〉

où la dernière égalité est obtenue en remplaçant UTk BUk par Bk. En notant λmax(Bk) la plus grande valeurpropre de la matrice symétrique réelle Bk on obtient l’inégalité

(7) f(yk−1 − γkUkUTk ∇f

(yk−1

))≤ f

(yk−1

)− γk‖UTk ∇f

(yk−1

)‖22 + λmax(Bk)γ2k‖UTk ∇f

(yk−1

)‖22.

Enfin en combinant les inégalités (6) et (7) on obtient pour tout entier k ≥ 1 et pour tout pas γk > 0,

f(yk)≤ f

(yk−1

)− γk‖UTk ∇f

(yk−1

)‖22 + λmax(Bk)γ2k‖UTk ∇f

(yk−1

)‖22.

Deuxième étape - Le terme de droite de l’inégalité précédente est un trinôme du second degré en γk decoefficient dominant strictement positif. On en déduit que ce terme est minimal pour

γk =‖UTk ∇f

(yk−1

)‖22

2λmax(Bk)‖UTk ∇f (yk−1) ‖22=

1

2λmax(Bk).cha

Et on obtient ainsi pour tout t ≥ 1,

(8) f(yk)≤ f

(yk−1

)− 1

4λmax(Bk)‖UTk ∇f

(yk−1

)‖22.

Troisième étape - En passant à l’espérance l’inégalité (8) sur les tirages à l’itération k conditionnellementaux tirages précédents on obtient (on note Ek cette espérance) :

Ek[ f(yk)

] ≤ f(yk−1

)− 1

4λmax(Bk)Ek[ ‖UTk ∇f

(yk−1

)‖22 ]

= f(yk−1

)− 1

4λmax(Bk)Ek[ ‖

m∑l=1

∇f(yk−1

)ikleikl ‖

22 ]

= f(yk−1

)− 1

4λmax(Bk)Ek[

m∑l=1

∇f(yk−1

)2ikl

]

= f(yk−1

)− 1

4λmax(Bk)

m∑l=1

Ek[∇f(yk−1

)2ikl

]

= f(yk−1

)− 1

4λmax(Bk)m

1

N

N∑i=1

∇f(yk−1

)2i

Ek[ f(yk)

] ≤ f(yk−1

)− m

4Nλmax(Bk)‖∇f

(yk−1

)‖22.


En soustrayant chaque membre de cette dernière inégalité par f(y∗), en passant à l’espérance sur tous les tirageson obtient par "tower rule"(2), pour tout k ≥ 1, en notant pour tout t ≥ 0, φk := E[ f

(yk)

]− f (y∗),

(9) φk ≤ φk−1 −m

4Nλmax(Bk)E[ ‖∇f

(yk−1

)‖22 ].

Quatrième étape - Par convexité de la fonction f on a :

f(yk−1

)− f (y∗) ≤ 〈∇f

(yt−1

), yk−1 − y∗〉

≤ ‖∇f(yk−1

)‖2 · ‖yk−1 − y∗‖2 (Cauchy-Schwarz)

Puis par une récurrence facile on montre par définition des problèmes (Pm(k)) que f(yk−1

)≤ f(y0) et par le

lemme 4.6 on obtient que ‖yk−1 − y∗‖ ≤ R0. En intégrant sur tous les tirages on en déduit que

E[ ‖∇f(yk−1

)‖2 ] ≥ 1

R0φk−1.

Donc en combinant cette inégalité avec (9) on obtient :

φk ≤ φk−1 −m

4Nλmax(Bk)‖E[∇f

(yk−1

)]‖22 (Inégalité de Jensen sur (9))

≤ φk−1 −m

4Nλmax(Bk)R20

φ2k−1.

On en déduit que φk−1 − φk ≥ m4Nλmax(Bk)R2

0

φ2k−1 et en remarquant que φk−1 ≤ φk on obtient pour toutk ≥ 1 :

1

φk− 1

φk−1=φk−1 − φkφkφk−1

≥ φk−1 − φkφ2k−1

≥ m

4Nλmax(Bk)R20

.

D’où par récurrence immédiate, pour tout k ≥ 1,1

φk≥ 1

φ0+

m

4Nλmax(Bk)R20

k.

Enfin puisque φ0 > 0 on obtient que pour tout k ≥ 1,1

φk≥ m

4Nλmax(Bk)R20

k.

En prenant les inverses de chacun des membres de cette dernière inégalité on obtient finalement (4) :

∀k ≥ 1, E[f(yk)]− f(y∗) ≤ 4Nλmax(Bk)R20

m· 1

k≤ 4Nλmax(B)R2

0

m· 1

k.

Cinquième étape - On a vu lors de la proposition 4.4 que la fonction f est 2λmin(B)-fortement convexe.On a donc pour tout k ≥ 1 et pour tout y ∈ RN−1,

f(y) ≥ f(yk−1

)+ 〈∇f

(yk−1

), y − yk−1〉+ λmin(B)‖y − yk−1‖22.

Minorons le terme de droite. Notons g : y ∈ RN−1 7→ f(yk−1

)+〈∇f

(yk−1

), y−yk−1〉+λmin(B)‖y−yk−1‖22 ∈ R,

c’est une fonction différentiable et convexe, la condition nécessaire d’optimalité du premier ordre ∇g(y) = 0 estaussi suffisante. De plus rappelons que B est symétrique définie positive, donc λmin(B) > 0 d’où :

∇g(y) = 0 ⇐⇒ ∇f(yk−1

)+ 2λmin(B)

(y − yk−1

)= 0

⇐⇒ 1

λmin(B)∇f

(yk−1

)= yk−1 − y

⇐⇒ y = yk−1 − 1

2λmin(B)∇f

(yk−1

).

On en déduit que pour tout k ≥ 1 et pour tout y ∈ RN−1, on a

f(y) ≥ f(yk−1

)− 1

2λmin(B)〈∇f

(yk−1

),∇f

(yk−1

)〉+

λmin(B)

4λmin(B)2‖∇f

(yk−1

)‖22.

En évaluant le terme de gauche en y∗ et en simplifiant le terme de droite on obtient,

f (y∗) ≥ f(yk−1

)−‖∇f

(yk−1

)‖22

4λmin(B)⇐⇒ 4λmin(B)

(f(yk−1

)− f (y∗)

)≥ ‖∇f

(yk−1

)‖22.

(2)EEk[ f(yk) ] = E[ f(yk)].


Enfin en remplaçant cette inégalité dans (9) on obtient que pour tout k ≥ 1,

φk ≤ φk−1 −m

4Nλmax(Bk)4λmin(B)φk−1 ⇐⇒ φk ≤ φk−1

(1− mλmin(B)

Nλmax(Bk)

).

On en déduit l’inégalité (5) :

E[f(yk)]− f(y∗)

E[f(yk−1)]− f(y∗)≤ 1− mλmin(B)

Nλmax(Bk)≤ 1− mλmin(B)

Nλmax(B).

Remarque 4.8. — Le théorème 4.7 est énoncé dans le cadre particulier du problème (P ), qui est une fonctionquadratique. Toutefois il se généraliserait sans peine à des fonctions fortement convexes de gradient lipschitziendont on connait explicitement la constante de forte convexité et une constante de Lipschitz pour le gradientavec une preuve similaire.

5. Application à la détection de données aberrantes

Avant de tester notre algorithme en dimensions où l’inversion de la matrice des moments n’est plus possible,on voudrait s’assurer numériquement que notre démarche est correcte au sens où on retrouve des résultatscomparables à ce qui a été obtenu dans [4] pour la détection de données aberrantes en petites dimensions.

5.1. Un classifieur basé sur l’inverse de la fonction de Christoffel empirique. — On suppose disposerde n points dans Rp de telle sorte à ce que µn soit la somme d’un échantillon tiré selon µ et d’une perturbation (lesdonnées aberrantes). On suppose que les données aberrantes sont peu nombreuses de sorte que la perturbationtende vers 0 et que µn tende vers µ en loi. On peut adapter le théorème 3.5 à ce cas.

Maintenant basé sur l’observation, que sous nos hypothèses,– l’inverse de la fonction de Christoffel quantifie la proportion de masse contenu dans un certain sous niveau

(voir la remarque 3.4),– et que la fonction de Christoffel associée à µn tend uniformément presque sûrement vers la fonction de

Christoffel,le critère simple que l’ont va considérer sera d’attribuer à chaque point à tester un score : la valeur de l’inversede la fonction de Christoffel empirique de paramètre d que l’on ajustera. Intuitivement, plus ce score sera grand,moins il est probable que notre point ait été tiré selon la loi µ.

Aussi pour décider si un point a été tiré selon µ, on calcule en ce point la d-ème fonction de Christoffelempirique associé à l’échantillon d’entrainement. Si cette valeur dépasse un seuil donné, par exemple 8/10-èmede la plus grande valeur obtenue lors de l’entrainement, alors notre point est considéré comme aberrant car ilest hors d’un ensemble contenant l’essentiel de la masse de la mesure µ.

5.2. Courbes Rappel-Précision. — Pour évaluer l’efficacité de notre classifieur, nous calculons l’aire sousla courbe Rappel-Précision, voir par exemple [1].

On considère que tous les points de Rp possèdent un label : s’ils sont tirés ou non selon µ. La précision estle rapport entre le nombre de points qui ont été correctement classés comme tirés selon µ et le nombre depoints qui ont été classés comme tirés selon µ. Le rappel est le rapport entre le nombre de points correctementclassés comme tirés selon µ et le nombre total de points tirés selon µ.

Ainsi à un seuil donné on associe un couple (rappel, précision). On fait varier le seuil pour obtenir le maximumde couples (rappel, précision) possibles et le graphe Rappel-Précision est le graphe affine par morceaux obtenuen reliant tous ces points par des segments. Une implémentation est disponible en annexe A.4

Intuitivement, plus un point de la courbe est proche du point (1, 1) et plus le seuil associé est bon.

Exemple 5.1. — La figure 2 présente un exemple de courbes Rappel-Précision pour un jeu de données dansR3. On a repris ici le jeu de données de l’article [4] qui est composé de vecteurs de R3 correspondant à desvariables intéressantes dans un contexte de détection d’intrusion informatique. L’essentiel de ces vecteurs sontassociés à un trafic normal et le jeu de données n’est composé que d’un faible nombre d’intrusions. Plus dedétails sur ce jeu de données se trouvent dans [4].

La courbe qui maximise l’aire sous la courbe Rappel-Précision est celle associé au paramètre d = 3 pour lafonction de Christoffel. Dans [4] les résultats obtenus ont été comparés à d’autres classifieurs.


0.00

0.25

0.50

0.75

1.00

0.0 0.2 0.4 0.6 0.8 1.0Recall

Pre

cisi

on

d (AUPR)

1 (0.08)

2 (0.18)

3 (0.18)

4 (0.16)

5 (0.15)

6 (0.13)

Figure 2. Courbe Rappel-Précision pour plusieurs valeurs de d où la d-ème fonction de Christoffelest calculée par inversion de la matrice des moments.

m = 8 m = 10 m = 12

m = 2 m = 4 m = 6

0.00 0.25 0.50 0.75 1.000.00 0.25 0.50 0.75 1.000.00 0.25 0.50 0.75 1.00

0.00

0.25

0.50

0.75

1.00

0.00

0.25

0.50

0.75

1.00

Recall

Pre

cisi

on

25

50

100

250

500

1000limite

Figure 3. Courbes Rappel-Précision pour le paramètre d = 3 avec différentes valeurs du paramètrem et du nombre total d’itérations de DC-BA, noté "limite".

Dans le but de se placer dans un futur cadre où le calcul de la fonction de Christoffel empirique n’est pluspossible par inversion de la matrice des moments, on considère maintenant comme score l’approximation dela Christoffel empirique en un point obtenue par un nombre fixé d’itérations de l’algorithme de descente dem-coordonnées défini en section 3.

Exemple 5.2. — La figure 3 présente des courbes Rappel-Précision pour le même jeu de données que l’exemple5.1 en fixant le paramètre d = 3 et en jouant sur la taille des blocs m et le nombre d’itérations maximal noté"limite". Naturellement, plus le nombre m de coordonnées utilisées pour effectuer nos descentes de coordonnéesest grand et plus la courbe obtenue est proche de celle obtenue par inversion de la matrice des moments. Demême, plus le nombre d’itérations maximal est grand et plus on se rapproche de la dite courbe. Toutefois unéquilibre entre grande valeur de m et de limite doit être trouvé comme mis en valeur dans la carte thermiquede la Figure 4.


2

4

6

8

10

12

25 50 100 250 500 1000

limite

m

10

12

14

16

18

AUPR

Figure 4. Carte thermique de l’AUPR ("Area Under the Precision-Recall curve") selon m et lenombre total d’itérations de DC-BA, noté "limite".

6. Tentatives d’extensions

Dans cette section nous donnerons des éléments d’extensions sur lesquels un travail a été effectué mais dontles résultats sont encore insuffisants.

Remarquons que pour assurer l’inversibilité de la matrice des moments, on considère que l’échantillon est detaille n ≥ s(d). Aussi le calcul de la matrice des moments nécessite au moins un O(s(d)3) opérations élémentairescar le calcul d’un moment en nécessite O(n).

On considère à partir de maintenant qu’on ne peut plus enregistrer la matrice des moments entièrement,notons que pour par exemple p = 30 et d = 5 on doit sauvegarder une matrice de taille s(d)2 ≈ 1, 05 · 1011,dépassant les capacités de stockage d’un ordinateur personnel.

C’est aussi dans l’objectif de réduire au maximum le coup d’une itération qu’une approche "simple" dedescente de coordonnée a été utilisée pour attaquer le problème (P0) plutôt que des méthodes du premier ordrecomme celle du gradient conjugué : le calcul du gradient de la fonction objectif nécessite O(s(d)2) opérationsélémentaires.

6.1. Une remarque sur l’ordre lexicographique gradué. — On suppose donc que nous sommes dansun contexte où il n’est pas concevable de mettre en mémoire la matrice des moments Md(µn), disons qu’on ap très grand et a fortiori s(d) :=

(p+dd

)aussi. Ainsi pour implémenter l’algorithme de descente par blocs de

coordonnée, il est important de pouvoir déterminer efficacement le monôme associé à un indice donné.Plus précisément, on considère la liste des monômes de degré total au plus d rangés par ordre croissant

en utilisant l’ordre (total) lexicographique gradué indexée par un entier k ∈ {1, 2, . . . , s(d)}. D’un entier k ∈{1, 2, . . . , s(d)} on voudrait déterminer le k-ème élément de cette liste. La proposition suivante établit le lieninverse : d’un monôme xα1

i · · ·xαpp , identifié à son p-uplet des puissances, α := (α1, . . . , αp), on peut déterminer

son indice kα dans la liste des monômes rangés. On rappelle que par convention la somme sur l’ensemble videest égale à 0.

Proposition 6.1. — Soit α := (α1, . . . , αp) ∈ Np tel que∑ni=1 αi =: |α| ≤ d et pour tout 1 ≤ i ≤ p on ait

0 ≤ αi ≤ |α|. Notons pour tout 1 ≤ i ≤ p, Si :=∑i−1j=1 αi. Posons pour tout 1 ≤ i ≤ p, en notant α0 = 0,

∀k ∈ N, mi,k :=

{0 si Si = |α|∑|α|−Si

l=k+1

((p−i)+(|α|−Si−l)−1

p−i−1)

sinon,

et

∀k ∈ N, Mi,k :=

{0 si Si = |α|∑k−1

l=0

((p−i)+(|α|−Si−l)−1

p−i−1)

sinon .


On a les encadrement suivant du rang kα du monôme α dans l’énumération des monômes à p variables de degréinférieur à d rangés par ordre lexicographique gradué croissant.(

p+ |α| − 1

p

)+ 1 ≤ kα ≤

(p+ |α|p

),(10)

∀ 1 ≤ j ≤ p− 1,

(p+ |α| − 1

p

)+

j∑i=1

mi,αi + 1 ≤ kα ≤(p+ |α|p

)−

j∑i=1

Mi,αi ,(11)

(p+ |α| − 1

p

)+

p∑i=1

mi,αi + 1 = kα =

(p+ |α|p

)−

p∑i=1

Mi,αi .(12)

Démonstration. — – Montrons l’encadrement (10). Le monôme α étant de degré |α|, par définition de l’ordrelexicographique gradué, il est strictement plus petit que tout monôme de degré |α|+1 et strictement plus grandque tout monôme de degré |α| − 1. Or il y a exactement

(p+|α|p

)monômes à p variables de degré inférieur |α|,

donc le plus petit monôme de degré |α| + 1 est le(p+|α|p

)+ 1 élément de la liste. On a donc kα ≤

(p+|α|p

). De

même, il y a exactement(p+|α|−1

p

)polynômes de degré inférieur |α| − 1, donc kα ≥

(p+|α|−1

p

)+ 1.

– Montrons les encadrements (11) par récurrence sur j ∈ {1, . . . , p − 1}, on se contentera de prouver lesminorations, les majorations se prouvant de manière analogue. Soit j = 1. Posons α1 + 1 ≤ l ≤ |α|. Pour toutmonôme β à p− 1 variables de degré |α| − l on a par définition de l’ordre lexicographique gradué

(l, β) � α.

Or il y a((p−1)+(|α|−l)−1

p−1−1)monômes β de cette forme et en notant que tous les monômes à p variables de la

forme (l, β) sont de degré |α| par construction, le choix de α1 + 1 ≤ l ≤ |α| étant arbitraire, on en déduit que(p+ |α| − 1

p

)+m1,α1

+ 1 ≤ kα.

Supposons les encadrements vérifiés à un rang 2 ≤ j − 1 ≤ p − 1. Posons αj + 1 ≤ l ≤ |α| − Sj . Pour toutmonôme β à p− j variables de degré |α| − Sj − l on a par définition de l’ordre lexicographique gradué

(α1, . . . , αj−1, l, β) � α.

Or il y a((p−j)+(|α|−Sj−l)−1

p−j−1)monômes β de cette forme et en remarquant que tous les monômes à p variables de

la forme (α1, . . . , αj−1, l, β) sont de degré |α| et supérieurs à tous les polynômes de la forme (l1, γ1), (α1, l2, γ2),..., (α1, . . . , αj−2, lj−1, γj−1) avec pour k variant de 1 à j − 1, αk + 1 ≤ lk ≤ |α| − Sk et γi un monôme à p− ivariables de degré |α| − α1 − . . .− αi−1. On en déduit que(

p+ |α| − 1

p

)+

j−1∑i=1

mi,αi +mj,αj + 1 ≤ kα.

– Montrons que(p+|α|−1

p

)+∑pi=1mi + 1 = kα. Découle du point précédent en remarquant que l’égalité (11)

pour un 1 ≤ i ≤ p force la valeur de αi.

Remarque 6.2. — Tout monôme dont le rang (dans le classement de l’énumération des monômes par ordrecroissant pour l’ordre lexicographique gradué) vérifie l’encadrement (10), i.e. s’il est minoré et majoré par lesmêmes bornes, alors il est nécessairement de même degré que α. De même, tout monôme dont le rang vérifie undes encadrement (11) pour un 1 ≤ j ≤ p− 1 possède les mêmes j premiers coefficients que le monôme α. Enfinsi le rang d’un monôme vérifie les égalités (12), alors ce monôme est α.

Cette dernière remarque suggère un algorithme permettant d’obtenir le k-ème monôme de notre liste demonôme rangés par ordre croissant, sans avoir besoin d’énumérer ces monômes.

Algorithme 6.3. — Soit α un monôme à p variables de degré inférieur ou égal à d, on notera encore α sonrang dans l’énumération des monômes à p variables de degré inférieur ou égal à d rangés dans l’ordre croissantpar l’ordre lexicographique gradué.

(1) On commence par déterminer son degré d0 :

d0 = min

{k ∈ {0, . . . , d} | kα ≥

(p+ k − 1

p

)+ 1

}.


(2) Puis on détermine ensuite ses coefficients successivement :– Pour 1 ≤ i ≤ p− 1, on a

αi = min

k ∈ {0, . . . , d0 − Si} |(p+ d0 − 1

p

)+

i−1∑j=1

mj,αj +mi,k + 1 ≤ kα ≤(p+ d0

p

)−

i−1∑j=1

Mj,αj +Mi,k

.

– Enfin on a αp = d0 − Sp.

Dans le pire des cas, cet algorithme effectue (p − 1)d comparaisons. Une implémentation est donnée enappendice A.2 et une implémentation de DC-BA ne sauvegardant plus en mémoire la matrice des moments setrouve en A.1.

6.2. Brèves remarques sur deux tentatives infructueuses d’extensions. — Toutefois l’algorithme DC-BA comme je l’ai implémenté en appendice A.1 ne permet que de dépasser légèrement les dimensions où le calculde la fonction de Christoffel empirique peut se faire par inversion de la matrice des moments.

Dans le but de réduire au maximum le coup d’une itération de DC-BA, j’ai tenté de sous-échantillonner, àchaque itération, l’échantillon pour faciliter le calcul des moments. Cette démarche était inspiré par la descentede gradient stochastique où à chaque itération, on estime le gradient de la fonction objectif par un estimateursans biais du gradient construit avec un seul point de l’échantillon.

Toutefois, les vecteurs wk utilisés dans DC-BA ne semblent pas avoir la même "robustesse" que le gra-dient : mes essais numériques semblent fonctionner pour certains sous-échantillonnage suffisamment gros maisne donnent pas les résultats attendus lors du cas extrême où on considère des sous-échantillons composés d’unseul point. Voir l’appendice A.5 pour un algorithme plus précis.

Enfin j’ai tenté de me rapprocher des résultats théoriques déjà existant, par exemple [3], en ce qui concernela descente de gradient stochastique. Dans DC-BA à chaque itération, on effectue une minimisation exacte enm coordonnées tandis que ce qui habituellement fait dans la littérature, par exemple [8] et [7], concerne des pasde gradients en m directions. Aussi, je suis revenu à la formulation du problème (P ) et après avoir observé quela fonction objectif peut être vu comme une somme finie séparée en les coordonnées, l’algorithme en appendiceA.6 est une nouvelle tentative pour associer descente de coordonnées avec l’idée de sous-échantillonner. Bienque le calcul du minimiseur se fait ainsi efficacement, la valeur associé ne l’est pas : et c’est bien elle qui nousintéresse.

7. Note finale

Dans ce mémoire nous avons pu voir que l’algorithme de descente par blocs de coordonnées développé ensection 4 donne les résultats attendus en dimension faible pour la détection de données aberrantes. Bien entendudans l’exemple traité en section 5, l’inversion de la matrice des moments étant possible, son intérêt pratique estlimité, toutefois cela reste une étape importante dans la validation de notre démarche tout en nous donnant unaperçu des performances de l’algorithme.

Il aurait fallu poursuivre ce travail sur un jeu de données en plus grande dimension, je n’ai pu faire ce travailà temps durant le stage, c’est un travail à poursuivre.

Enfin je profite de cette note pour remercier Jean-Bernard Lasserre et Edouard Pauwels qui m’ont guidé lorsde ce stage avec beaucoup de patience et bienveillance, pour tenter d’étendre leurs travaux effectués dans [4] et[5].

Malgré mon incapacité à résoudre le problème initial durant ce stage (calculer la fonction de Christoffel dansle régime où la matrice des moments n’est même plus stockable), j’ai pu découvrir le domaine encore jeune de lafonction de Christoffel empirique dans le contexte de "l’apprentissage machine" et j’ai pu me faire la main avecde nombreux outils utilisés dans ce cadre. Aussi c’est avec regret que je laisse sur cette note ce travail inachevéde stage.

Appendice AImplémentations en Julia

Julia est un langage "open-source" de haut niveau, dont la syntaxe est très proche de Matlab, réputé êtretrès efficace pour le calcul numérique donnant des résultats comparables à des implémentations en langage C.On mets ici à titre indicatif les implémentations, très commentées mais sûrement non optimales, qui ont étéutilisées durant ce mémoire.


A.1. Implémentation de DC-BA. — Cette implémentation de DC-BA enregistre la matrice des moments.C’est cette implémentation de DC-BA qui a donné les figures 3 et 4.

"""DC_ter(m, z, d, x)

Effectue une descente de m coordonnées pour déterminer la fonction de Christoffel.en un point x d’ordre d d’une mesure empirique construite sur un échantillon z.On suppose démarrer du points (1,0, ..., 0) de R^(s_d).Version de DC où on enregistre la matrice des moments."""function DC_ter(m, z, d, x; limite = 100)

p = length(z[:, 1]);s_d = binomial(p+d,d);n = length(z[1, :]);X = zeros(s_d, 1); # On démarre en (1, 0, ..., 0), point admissible.X[1] = 1;Y = zeros(s_d-1, 1);Valeurs = zeros(limite, 1);Valeurs[1] = 1.0;

# On calcule v qui contient l’évaluation de x dans la base des monômes.v = zeros(s_d, 1);for k in 1:s_d

v[k] = prod(x.^(coordonnees_monomes([k]’’, p, d)’));end

# On calcule la matrice des moments.Q = matrice_moments((1:s_d)’’, (1:s_d)’’, p, d, z, n);

# On calcule le vecteur Q_1, qui est la première colonne de la matrice des# moments sans le premier coefficient.Q_1 = Q[2:s_d, 1];

# On calcule w := 2(Q_1 - vtilde) \in R^(s_d-1)w = 2*(Q_1 - v[2:s_d]);

# Calcul de M := vtilde*vtilde’ + Qtronquée - 2*vtilde*Q_1’.M = v[2:s_d]*v[2:s_d]’ + Q[2:s_d,2:s_d] - Q_1*v[2:s_d]’ - v[2:s_d]*Q_1’;

# On a calculé toute les données indépendantes des tirages de coordonnees.for k in 2:(limite)

# On génère m coordonnées distinctes i1, ..., imcoord = zeros(Int64, m)coord[1] = rand(1:s_d-1);for i in 2:m

# 1:(s_d-1) privé de {précédents}tmp3 = filter(j -> !(j in coord[1:(i-1)]), 1:(s_d-1));coord[i] = rand(tmp3);

end

# On calcule wtilde := U’*w + 2*U’*M*Ywtilde = w[coord] + 2*M[coord,:]*Y;# Rappel : Mtilde = U’*M*U# On calcule le pas optimal alpha# alpha = -0.5*inv(M[coord,coord])*wtilde;


alpha = (2*M[coord,coord])\(-wtilde);# On met à jour X et Y et la valeur de la fonction de ChristoffelY[coord] += alpha;X[coord+1] += alpha;X[1] += (-alpha’*v[coord+1])[1];Valeurs[k] = Valeurs[k-1] + 0.5*(wtilde’*alpha)[1];

endreturn(Valeurs)

end

Dans cette version de DC-BA, on ne sauvegarde plus la matrice des moments. On a aussi optimisé, parrapport à la version précédente, le tirage aléatoires des coordonnées.using StatsBase"""

DC_BA(m, z, d, x)

Effectue une descente de m coordonnées pour déterminer la fonction de Christo.en un point x d’ordre d d’une mesure empirique construite sur un échantillon z.On suppose démarrer du points (1,0, ..., 0) de R^(s_d).Version de DC où on enregistre PAS la matrice des moments."""function DC_BA(m, z, d, x; limite = 100)

p = length(z[:, 1]);s_d = binomial(p+d,d);n = length(z[1, :]);X = zeros(s_d, 1); # On démarre en (1, 0, ..., 0), point admissible.X[1] = 1;Y = zeros(s_d-1, 1);Valeurs = zeros(limite, 1);Valeurs[1] = 1.0; # Après rescalling de la matmoment à 1 en haut à gauche.



# On calcule le vecteur Q_1, qui est la première colonne de la matrice des# moments sans le premier coefficient.Q_1 = matrice_moments((2:s_d)’’, [1]’’, p, d, z, n);

# On calcule w := 2(Q_1 - vtilde) \in R^(s_d-1)w = 2*(Q_1 - v[2:s_d]);# Calcul de M := vtilde*vtilde’ + Qtronquée - 2*vtilde*Q_1’.Mpartiel = v[2:s_d]*v[2:s_d]’ - Q_1*v[2:s_d]’ - v[2:s_d]*Q_1’;

# On a calculé toute les données indépendantes des tirages de coordonnees.for k in 2:(limite)

# On génère m coordonnées distinctes i1, ..., imcoord = sample(1:(s_d-1), m, replace = false);

# On calcule les m-lignes de M utiles :M_coord = Mpartiel[coord, :] +


(matrice_moments((2:s_d)’’, (coord+1)’’, p, d, z, n))’# On calcule wtilde := U’*w + 2*U’*M*Ywtilde = w[coord] + 2*M_coord*Y;

# Rappel : Mtilde = U’*M*U# On calcule le pas optimal alpha# alpha = -0.5*inv(M[coord,coord])*wtilde;alpha = (2*M_coord[:, coord])\(-wtilde); # Note : A \ b = A^(-1)*b

# On met à jour X et Y et la valeur de la fonction de ChristoffelY[coord] += alpha;X[coord+1] += alpha;X[1] += (-alpha’*v[coord+1])[1];Valeurs[k] = Valeurs[k-1] + 0.5*(wtilde’*alpha)[1];

endreturn(Valeurs)

end

A.2. Détermination du monôme associé à son classement. —"""

coordonnees_monomes(coordonnees,p,d)

Considérons une énumération (non explicitée ici) des monômes à p variables dedegré d rangés dans l’ordre lexicographique gradué.Cette fonction retourne les monômes associés aux indices contenus danscoordonnees, sans expliciter l’énumération en question."""function coordonnees_monomes(coordonnees::Matrix{Int64}, p::Int64, d::Int64)

Jacky = zeros(Int64, length(coordonnees), p); # Va contenir les monômes.

for i in 1:length(coordonnees);

d0::Int64 = 0 # Degré du monôme associé à coordonnees[i]while coordonnees[i] > (binomial(p+d0, p))

d0 += 1;end

Michou = binomial(p+d0, p); # On définit les bornesRoberta = binomial(p+d0-1, p);SommemPrecedents::Int64 = 0;SommeMPrecedents::Int64 = 0;

for j in 1:pSommeCoeffPrecedents = sum(Jacky[i,:]);if (SommeCoeffPrecedents == d0)

break #On s’arrête si on a déjà répartis tous les coeffs possibles.

elseif j == pJacky[i,j] = d0 - SommeCoeffPrecedents;

elseGeorgette = [binomial(p-j + (d0-SommeCoeffPrecedents-l)-1, p-j - 1)for l in 0:(d0-SommeCoeffPrecedents)] #Contient toutes les "bornes".m = sum(Georgette[2:(d0-SommeCoeffPrecedents+1)]); # "bornes minorantes"


M = 0; # "bornes majorantes"

while (Roberta + SommemPrecedents + m + 1 <= coordonnees[i]) &(coordonnees[i] <= Michou - M - SommeMPrecedents) == false

Jacky[i,j] += 1;m = sum( Georgette[(Jacky[i,j]+2):(d0-SommeCoeffPrecedents+1)] );M = sum( Georgette[1 : Jacky[i,j]]);

end

SommemPrecedents += m;SommeMPrecedents += M;

endend

endreturn(Jacky)

end

A.3. Génération de la matrice des moments. —"""matrice_moments(coord_x, coord_y, p, d, z,n)

Retourne une matrice (coord_x x coord_y) contenant les coefficients dela matrice des moments d’ordre d de la mesure empirique associée à unéchantillon z de taille n (contenu dans une matrice colonnes) d’éléments de R^p."""function matrice_moments(coord_x::Matrix{Int64}, coord_y::Matrix{Int64},

p::Int64, d::Int64, z, n::Int64)monomes_x = coordonnees_monomes(coord_x, p, d);monomes_y = coordonnees_monomes(coord_y, p, d);Q_partiel = zeros(Float64, length(coord_x), length(coord_y));

for k in 1:length(coord_x)for l in 1:length(coord_y)

Q_partiel[k,l] = 1/n * sum( prod( (z .^ (monomes_x[k,:])), 1).* prod((z .^ (monomes_y[l,:])) , 1) );# M_d(mu_n)_(alpha, beta) = 1/n * sum(from i=1 to n)(z_i^alpha * z_i^beta)

endend

return(Q_partiel)end

A.4. Calcul du rappel et de la précision. —"""

PR(score, label)

Retourne la "Precision" et le "Recall" de data, données dont on sait la nature.On suppose que label contient la nature des points (intrus=1 ou pas_intrus=0)."""function PR(score, label)

taille = length(score);


TPplusFN = sum(label); # ConstanteTPplusFP = 1:taille;TP = cumsum(label[sortperm(score, rev=true)], 1);

Precision = TP ./ TPplusFP ;Recall = TP / TPplusFN ;

return(hcat(Precision,Recall))

end

A.5. Descente de Coordonnées par Blocs avec Sous-Échantillonnage, (DC-BASE). —using StatsBase"""

DC_base(m, a, z, d, x; limite = 10)

Effectue une descente de m coordonnées pour déterminer la fonction de Christo.en un point x d’ordre d d’une mesure empirique construite sur un échantillon z.Considère des sous échantillon de taille a.On suppose démarrer du points (1,0, ..., 0) de R^(s_d).Version de DC qui doit tenir les moyennes dimensions (p = 15,20)."""

function DC_base(m, a, z, d, x, limite; b = 1, c = 1)

p = length(z[:, 1]);s_d = binomial(p+d,d);n = length(z[1, :]);X = zeros(s_d, 1); # On démarre en (1, 0, ..., 0), point admissible.X[1] = 1;Y = zeros(s_d-1, 1);Valeurs = zeros(limite, 1);Valeurs[1] = 1.0; # Après rescalling de la matmoment à 1 en haut à gauche.


v[k] = prod(x.^(coordonnees_monomes([k]’’, p, d)’));# v[k] = 1/n *

end

# On calcule le vecteur Q_1, qui est la première colonne de la matrice des# moments sans le premier coefficient.Q_1 = matrice_moments((2:s_d)’’, [1]’’, p, d, z, n);

# On calcule w := 2(Q_1 - vtilde) \in R^(s_d-1)w = 2*(Q_1 - v[2:s_d]);

# Morceau indé de M : un bout de M indépendant des tirages.Mpartiel = v[2:s_d]*v[2:s_d]’ - Q_1*v[2:s_d]’ - v[2:s_d]*Q_1’;

# On a calculé toute les données indépendantes des tirages de coordonnees.

for k in 2:(limite)display(k)


# On génère m coordonnées distinctes i1, ..., imcoord = sample(1:(s_d-1), m, replace = false);

# On génère un sous échantillon par échantillonnage de Bernoulli.coordbis = sample(1:n,a, replace = false);

# On calcule les i1, ... ,im -èmes lignes de M# v[2:s_d]*v[2:s_d]’ + Q[2:s_d,2:s_d] - Q_1*v[2:s_d]’ - v[2:s_d]*Q_1’;#ça doit être un vecteur ligne

M_coord = Mpartiel[coord, :] +(matrice_moments((2:s_d)’’, (coord+1)’’, p, d, z[:, coordbis],length(coordbis)))’;

# On calcule wtilde := U’*w + 2*U’*M*Ywtilde = w[coord] + 2*M_coord*Y;

# On calcule le pas optimal alpha# alpha = -0.5*inv(M[coord,coord])*wtilde;alpha = -0.5*pinv(M_coord[:, coord])*wtilde* (b / (k^c));# On met à jour X et Y et la valeur de la fonction de ChristoffelY[coord] += alpha;X[coord+1] += alpha;X[1] += (-alpha’*v[coord+1])[1];Valeurs[k] = Valeurs[k-1] + 0.5*(wtilde’*alpha)[1];endreturn(Valeurs)

end

A.6. Un algorithme de projection pour le problème (P). —using StatsBase

function algo(m, d, z, x, limite)

p = length(z[:,1]);s_d = binomial(p + d, d);n = length(z[1,:]);q = zeros(Float64, s_d); q[1] = 1;alpha = 1;Valeurs = zeros(Float64, n);Valeurs[1] = 1;



for k in 1:(limite-1)# Calcul du stepsizealpha = 1/k;

# Tirer les m coordonnees parmi {1, ..., s_d}coord = sample(1:(s_d), m, replace = false);


# Tirer les m éléments associés de {1, ..., n}sous_sample = sample(1:n, m, replace = false);

Z_eval = zeros(s_d, m);for j in 1:m

for i in 1:s_dZ_eval[i,j] = prod(z[:,coord[j]].^(coordonnees_monomes([i]’’, p, d)’));

endend

# Calculer les estimées des gradients partielstmp = zeros(m,1);for j in 1:m

tmp[j] = Z_eval[coord[j],j];endgrad_tilde = 2/m * (q’*Z_eval)’ .* tmp;

# Calcul de la nouvelle itéréeq[coord] -= alpha*grad_tilde;q -= (q’*v)[1]*v;

# Calcul de la nouvelle valeur coûte O(n*s_d) : échec...

end

end

Références

[1] J. Davis and M. Goadrich. The relationship between precision-recall and ROC curves. In Proceedings of the 23rdInternational Conference on Machine Learning, ICML ’06, pages 233–240, New York, NY, USA, 2006. ACM.

[2] C. Dunkl and Y. Xu. Orthogonal Polynomials of Several Variables. Encyclopedia of Mathematics and its Applications.Cambridge University Press, second edition, 2014.

[3] S. Lacoste-Julien, M. Schmidt, and F. Bach. A simpler approach to obtaining an O(1/t) convergence rate for theprojected stochastic subgradient method. ArXiv e-prints, December 2012.

[4] J.-B. Lasserre and E. Pauwels. Sorting out typicality with the inverse moment matrix SOS polynomial. ArXiv e-prints,June 2016.

[5] J.-B. Lasserre and E. Pauwels. The empirical Christoffel function in Statistics and Machine Learning. ArXiv e-prints,January 2017.

[6] D. Monasse. Cours de Mathématiques Spéciales. Spartacus-idh, 4 ème edition, 2015.[7] Y. Nesterov. Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems. SIAM Journal on

Optimization, 2010.[8] S. J. Wright. Coordinate Descent Algorithms. ArXiv e-prints, February 2015.

Tran Duy Nghi Benoît, • E-mail : [email protected]

Documents

SUR LE CALCUL DE LA FONCTION DE CHRISTOFFEL EMPIRIQUE … · 4 tran duy nghi benoÎt 15 10 30 80 210 460 950 950 950 1850 1850 1850 3570 3570 3570 6860 6860 6860 13810 13810 30670