Données massives et statistiqueen haute dimension

Christine De Mol

Université Libre de BruxellesDept Math. et ECARES

Conférence “Savoir pour agir”Luxembourg, 20 octobre 2015

Un déluge ou tsunami de données

Un tsunami de données

Trouver une aiguille dans une botte de foin

Combien de données?

Des millions, des billions, des trillionset des fraccillions!

(Ravel et Colette, 1925, L’enfant et les sortilèges)

Quantifions ...

• Unité: 1 bit (b) (0 ou 1)

• 1 byte (B) (= octet) = 8 bits

On suppose que tout est encodé de façon binaire,par des zéros et des uns

... la folie des grandeurs

• 1 kB = 1 kilobyte (kilooctet) = 1000 bytes

• 1 MB = 1 megabyte (mégaoctet) = 1000 kB = 106 Byte(million)

• 1 GB = 1 gigabyte (gigaoctet) = 1000 MB = 109 Byte(milliard)

• 1 TB = 1 terabyte (téraoctet) = 1000 GB = 1012 Byte(billion)

• 1 PB = 1 petabyte (pétaoctet) = 1000 TB = 1015 Byte(billiard)

• Préfixes suivants: exa (1018), zetta (1021), yotta (1024)trillion, trilliard, quadrillion

Exemples: l’ère du petabyte

• bytes : 1 byte ∼ 1 lettre (caractère ascii)

• kilobytes : 1 kB ∼ 1 page,1 article en pdf (50-500 kB) , 1 petite image

• megabytes : 1 livre

• gigabytes : 1 CD Audio (700 MB), 1 DVD (5 GB),une bibliothèque personnelle

• terabytes : une bibliothèque collectiveLOC (20 TB) (digital content of U.S. Library of Congress)

• petabytes : Quantité de données traitées par les serveursde Google en une heure (1 PB)

Tout augmente!

• 90 % des données enregistrées l’ont été au coursdes deux dernières années!!!

• La plupart le sont sous forme digitale (nombres)(1 % en 1986, 25 % en 2000, 94% en 2007)

• En 2007, ∼ 300 exabytes de données stockées(61 CD-ROM par personne, soit en tout une pile quidépasserait la lune!)

• et ∼ 2 zettabytes de données échangées!

(M. Hilbert, P. López, Science 2011)

Capacités de stockage

Flux de données

Flux/Stockage

Puissance de calcul

Mathematics Awareness Month April 2012

Intelligent design to exploit them!

Du pain sur la planche ...

pour les

• mathématiciens

• statisticiens

• informaticiens, ingénieurs, etc.

afin de développer des stratégies automatiques d’extraction del’information utile dans d’immenses quantités de données.

→ développement rapide de (nouvelles) disciplines:

• Vision assistée par ordinateur (“Computer vision”)

• “Data Mining”

• Apprentissage statistique (“Machine Learning”)

• Bioinformatique, etc.

... dans tous les domaines

Notamment en

• PhysiqueLe LHC (Large Hadron Collider) (CMS) au CERN recueillepar seconde 1 Petabyte de données brutes (600 millions decollisions à 1 MB chacune), réduit à ∼ 100 000 par le“trigger”, puis à ∼ 100 par seconde par le “grid” (→ 15 PBde données enregistrées par an)

• AstronomieLe “Sloane Digital Sky Survey” (SDSS), avec 200 GB parnuit, a recueilli en quelques semaines plus que toutes lesdonnées de l’histoire de l’astronomie (déjà 71 TB)!

• GéophysiqueRéseaux de sismographes fonctionnant en permanencepour ausculter la terre. Par exemple, le “US Array” recueillepar jour 4.9 GB (déjà au total 12 TB)

... dans tous les domaines

• Biologie (surtout la génomique, protéomique)Votre génome personnel sous le sapin pour quelquespoignées de dollars?

• Economie et finance(“tick-by-tick data”)

• Sciences socialesEtudes, développement du “Data Journalism”

• PolitiqueLa campagne d’Obama a employé plus de 100statisticiens, mathématiciens, ingénieurs, etc.

Une nouvelle revue scientifique

Une nouvelle profession?

Une nouvelle statistique

“The coming century is surely the century of data. A combination ofblind faith and serious purpose makes our society invest massively inthe collection and processing of data of all kinds, on scalesunimaginable until recently. Hyperspectral Imagery, Internet Portals,Financial tick-by-tick data, and DNA Microarrays are just a few of thebetter known sources, feeding data in torrential streams into scientificand business databases worldwide. In traditional statistical dataanalysis, we think of observations of instances of particularphenomena (e.g. instance, human being), these observations being avector of values we measured on several variables (e.g. bloodpressure, weight, height,...). In traditional statistical methodology, weassumed many observations and a few, well chosen variables. Thetrend today is towards more observations but even more so, toradically larger numbers of variables - voracious, automatic, systematiccollection of hyper-informative detail about each observed instance.”David L. Donoho

Une nouvelle statistique/économétrie

• Traditionnellement, beaucoup d’observations (n)sur un petit nombre de variables (p)

• Statistique “moderne”: relativement peu d’observations (n)sur un grand nombre nombre de variables (p)

(“large p, small n paradigm”)

• Ceci requiert le développement de nouvelles méthodologies(sélection de variables, régularisation, etc.)

• Statistique en haute dimension

Exemple: régression linéaire

• On mesure/observe les valeurs de p variables (variablesexplicatives, prédicteurs) pour n cas ou individus,rangées dans une matrice n×p notée X

• On observe les valeurs d’une variable dépendante ouréponse, combinaisons linéaires des valeurs de ces variables,pour chacun de ces n cas, rangées dans un vecteur n×1 noté y

• Par conséquenty = Xβ

où β est le vecteur p×1 des coefficients de régression

Deux problèmes distincts

• Prédictionprédire la réponse y

• Identification (sélection de variables)déterminer le vecteur β des coefficients de régressioncàd identifier le modèle et les prédicteurs significatifs

ou les SELECTIONNER si beaucoup de ces coefficientssont nulscàd si β est EPARS (“SPARSE”) ou “parcimonieux”

Essentiel pour l’interprétation des résultats!

NB. En économétrie, le plus souvent, macro ∼ prédiction,micro ∼ identification (causalité)

OLS et BLUE

• Erreurs sur les données: y = Xβ + e

• → minimiser

Λ(β) = ‖y−Xβ‖22 (‖y‖2 =

√∑

i|yi |2 = norme L2)

• Si X T X est de rang maximum, le minimum est fourni parl’estimateur des moindres carrés (“Ordinary Least Squares”ou OLS)

βols = (X T X)−1X T y

• Sous les hypothèses usuelles: OLS = BLUE(meilleur estimateur linéaire NON BIAISE)

• Statistique classique: consistance/asymptotiquepour n→ ∞ (et p fixé)

Problèmes avec OLS

• N’a pas de sens si X T X n’est pas de rang maximum,càda la valeur propre zéro (en particulier, dès que p > n)

• Si p > n ou si p >> n, le minimisateur n’est pas unique,mais on peut éventuellement se contenter de sélectionnerla solution de norme minimale, orthogonale au noyau de X(OK pour la prédiction, mais pas pour l’identification!)

• De plus X T X peut avoir des valeurs propres proches dezéro −→ X T X a un grand “nombre de conditionnement”(= rapport entre la plus grande et la plus petite des valeurspropres non nulles) −→ problème mal conditionné etsolution instable (trop grande variance/volatilité):malédiction de la dimensionalité

• Asymptotique pour n→ ∞ et p→ ∞ ?

Un remède: la régression pénalisée

• Pour stabiliser la solution (estimateur), on utilise descontraintes supplémentaires ou on ajoute un terme depénalité aux moindres carrés, ce qui permet de réduire ladimensionalité du problème (“régularisation”)

• càd on introduit un biais pour diminuer la variance

(“OUT of the BLUE” !!)

Régression Ridge

(Hoerl and Kennard 1970 ou régularisation de Tikhonov)• On pénalise la norme L2 de β:

βridge = argminβ

[‖y−Xβ‖2

2 + λ‖β‖22

]= (X T X + λ Id)−1X T y

(λ > 0 = “paramètre de régularisation”)• Cas particulier: prédicteurs orthogonaux (X T X = Id)

βridge =1

1 + λX T y

(tous les coefficients sont retrécis uniformément vers zéro)• Les pénalités quadratiques de ce type donnent des

solutions (estimateurs) qui dépendent linéairement de ymais ne permettent pas la sélection de variables(typiquement tous les coefficients sont differents de zéro)

Régression Lasso

(Tibshirani 1996)• On pénalise la norme L1 de β:

βlasso = argminβ

[‖y−Xβ‖2

2 + τ‖β‖1]

où ‖β‖1 = ∑pj=1 |βj |

• Cas particulier: prédicteurs orthogonaux (X T X = Id)

[βlasso]j = Sτ([X T y ]j)

Sτ produit le seuillage “doux”

Sτ(x) =

x + τ/2 if x ≤−τ/2

0 if |x |< τ/2x− τ/2 if x ≥ τ/2

• Retrécissement non linéaire (dépend de la grandeur descoefficients) et le vecteur β est épars (sélection devariables)

Eloge de la parcimonie ou “sparsité” (sparsity)

“Entia non sunt multiplicanda sine necessitate”

William of Ockham (∼ 1288 - 1348)

Parcimonie et génétique

“biopuce” ou “microdamier”(“microarray” en anglais)

Parcimonie et génétique

• Matrice n×p avec niveaux d’expression de p gènes(plusieurs milliers) pour n patients ou cas (quelquescentaines)

• Pour chacun d’eux, on a une réponse soit binaire (maladeou non; pathologie A ou B, etc.), soit continue (temps desurvie, niveau de gravité de la maladie, etc.)

• But: identifier les gènes coupables (par une composantenon nulle dans le vecteur épars β) et prédire la réponsepour de nouveaux cas au vu des données de biopuces

(De Mol, Mosci, Traskine, Verri, J. Comp. Biol. 2009)

Parcimonie et “Computer Vision”

• Détection automatique de visages dans des images

• Utilisation d’un dictionnaire {φj} de 64000 “features”utilisés pour représenter chaque “imagette” (patch)de 19 x 19 pixels

• Se ramène à un problème de régression parcimonieuse

(Destrero, De Mol, Odone and Verri, IJCV 2009)

Parcimonie et “Computer Vision”

Parcimonie et “Computer Vision”

Parcimonie et finance

• Données X = matrice des “returns” de p actionsenregistrées au cours du temps (t = 1, . . . ,n)

• Comment choisir un petit nombre de ces actionsidéalement diversifiées de façon à minimiser le risque(cf. portefeuilles de Markowitz)?

• Solution via une technique de régression parcimonieuse

(Brodie, Daubechies, De Mol, Giannone, Loris, PNAS 2009)

Résultats empiriques: FF100Sh

arpe

Rat

io (i

n %

)

wpos

5 10 15 20 25 30 35 40 45 50 55 60

40

35

30

25

number of active positions

11−20

21−30

31−4041−50

51−60

1

w

w

wpos

bin

K

Parcimonie et séries temporelles

• Données = matrice X formée par un grand nombre p deséries temporelles (par exemple variablesmacroéconomiques et/ou financières)observées au cours du temps (t = 1, . . . ,n)

• Réponse y = série à prévoir sur la base de X

• Peut-on utiliser des techniques de régressionparcimonieuse et baser la prévision sur un petit nombrede ces séries?

• Sur des séries cross-corrélées (comme en macro), Lassone fait pas mieux que Ridge (et la sélection est instable)

(De Mol, Giannone, Reichlin, J. of Econometrics 2008)

Prévision IP (ridge & lasso vs PCR; least MSFE)

Jan1970 Jan1975 Jan1980 Jan1985 Jan1990 Jan1995 Jan2000 Jan2005−15

−10

−5

0

5

10

15

20

truePC: r= 10Bayesian: ν=290Lasso: 10

La fin des théories scientifiques?

La fin des théories scientifiques?

The End of Theory: The Data Deluge Makes the ScientificMethod ObsoletePetabytes allow us to say: "Correlation is enough." We can stoplooking for models. We can analyze the data without hypotheses aboutwhat it might show. We can throw the numbers into the biggestcomputing clusters the world has ever seen and let statisticalalgorithms find patterns where science cannot.[...] The new availability of huge amounts of data, along with thestatistical tools to crunch these numbers, offers a whole new way ofunderstanding the world. Correlation supersedes causation, andscience can advance even without coherent models, unified theories,or really any mechanistic explanation at all. There’s no reason to clingto our old ways. It’s time to ask: What can science learn from Google?

Chris Anderson (Wired Magazine 2008)

La fin des théories scientifiques?

La fin des théories: le déluge des données rend obsolète laméthode scientifique[...] La disponibilité d’énormes quantités de données, ainsi qued’outils statistiques pour traiter ces nombres, offre une toutenouvelle manière de comprendre le monde. La notion decorrélation supplante celle de causalité, et la science peut allerde l’avant même sans modèles cohérents, théories unifiées, niaucune explication mécaniste.Il n’y a pas de raison de nous accrocher à nos vieux schémas.Il est temps de se demander: qu’est ce que la science peutapprendre de Google?

Chris Anderson (Wired Magazine 2008)