(PDF) le hasard au service des algorithmes …membres-timc.imag.fr/Olivier.Francois/MPA_Cours1.pdfLois gaussiennes I Mélange de gaussiennes.Les composantes du mélanges sont des lois normales

Modèles probabilistes pour l'apprentissage

le hasard au service des algorithmes

olivier.francois@grenoble-inp.fr olivier.francois@imag.fr

Qu'entend-t-on par apprentissage?

I Méthodes qui permettent à une � machine � d'évoluer grâce à

un processus automatique

I Principe : Modéliser la réponse d'un système à partir des

variables d'entrées et des données empiriques recueillies pour

ce système

I Adaptatif et �exible, prenant en compte l'évolution de la base

d'information des comportements enregistrés

Histoire

I 1943 : McCulloch et Pitts, Turing, von Neuman, considérent

les fonctions mentales comme des fonctions mathématiques

auto-régulées.

A Logical Calculus of Ideas Immanent in Nervous Activity, 1943,

Bull. Math. Biophys. 5:115-133.

I 1957 : Perceptron de Rosenblatt (Mark 1) �The fundamental

laws of organization which are common to all information

handling systems, machines and men included, may eventually

be understood�

Applications

I Reconnaissance des formes, reconnaissance vocale, vision par

ordinateur

I Aide au diagnostic, détection de fraude, d'anomalies, de

spams, analyse �nancière, bio-informatique

I Sites web adaptatifs : Recommandation de produits (Amazon,

Net�ix)

I Moteurs de recherche

Contenu de cet exposé

I Principes d'analyse bayésienne

I Recherche d'un objet

I Estimation d'une probabilité

I Reconnaître des groupes dans les données

I Prédire vos préférences cinématographiques

Objectifs d'une analyse bayésienne

I Apprentissage : Mettre à jour l'information disponible sur un

phénomène à partir d'observations de ce phénomène

I Quanti�er l'incertitude sur les paramètres expliquant le

phénomène

I Prédire les valeurs de nouvelles données et évaluer l'incertitude

de cette prédiction

The blind men and the elephant

Lien avec �la� statistique

I En statistique, l'objectif est généralement de tester une

hypothèse et de déterminer la zone de rejet du test

I L'incertitude sur le paramètre à tester n'est pas modélisée. La

seule source d'incertitude prise en compte provient de

l'échantillonnage.

La formule de Bayes

I Soit A,B des événements de probabilité non-nulle

P(B|A) =P(A|B)P(B)

P(A)∝ P(A|B)P(B)

Exemple 1 : Recherche d'un objet

I Un exemple élémentaire où l'observation permet de (re)mettre

à jour des connaissances a priori.

USS ne répond plus

I Uss Scorpion (SSN-589): un sous-marin nucléaire américain

qui a coulé dans l'océan atlantique en 1968

I L'épave a été retrouvée au bout de 5 mois de recherche à l'aide

de signaux sonores et d'une méthode de recherche bayésienne

I Principe ?

Recherche d'un objet

Cartes de probabilité

I Carte a priori :

pi = P(Uss est dans la cellule i)

I Probabilité d'erreur de mesure = 1− q

I Supposons que le résultat de la recherche dans la cellule i est

infructueux

I Mise à jour des probabilités

P(Uss est dans la cellule i |Resultat negatif) =(1− q)pi1− qpi

.

Jour 0

Jour 1

Jour 5

Jour 13

Jour 37

Jour 57

Jour 67

Modèle probabiliste pour l'analyse bayésienne

I Paramètre θ = (θ1, . . . , θJ), J ≥ 1.

I Données y = (y1, . . . , yn), n ≥ 1.

I Un modèle est décrit par une loi de probabilité jointe :

p(y , θ) = p(y |θ)p(θ)

Modèle probabiliste pour l'analyse bayésienne

I p(θ) est la loi a priori. Elle peut être informative ou

non-informative.

I p(y |θ) est la vraisemblance. Elle décrit la manière dont sont

générées les données observées dans le modèle.

p(y , θ) = p(y |θ)p(θ)

Inférence bayésienne

I On utilise la formule de Bayes pour calculer la loi a posteriori

p(θ|y) =p(y |θ)p(θ)

p(y)

où p(y) =∫p(y |θ)p(θ)dθ est la loi marginale.

I En général, on cherche à éviter le calcul de la loi marginale et

on écrit

p(θ|y) ∝ p(y |θ)p(θ)

Exemple 2 : Sondage

I Une source émet des signaux binaires, xi , et on cherche à

estimer la probabilité d'émettre un 1.

I On note cette probabilité θ

p(xi = 1|θ) = θ

I Puis on observe une suite de signaux émis par la source :

1, 0, 1, . . .

Apprentissage : x = 1, 0, 1, · · ·

Etape 1:

p(θ|x1 = 1) ∝ p(x1 = 1|θ)p(θ) = θ (p(θ) = 1)

Etape 2:

p(θ|x2 = 0, x1 = 1) ∝ p(x2 = 0|θ)p(θ|x1 = 1) = (1− θ)θ

Etape 3:

p(θ|x3 = 1, x2 = 0, x1 = 1) ∝ p(x3 = 1|θ)(1− θ)θ = (1− θ)θ2

Apprentissage

0.0 0.2 0.4 0.6 0.8 1.0

0.6

0.8

1.0

1.2

1.4

Loi a priori

dbet

a(u,

1, 1

)

0.0 0.2 0.4 0.6 0.8 1.0

0.0

0.5

1.0

1.5

2.0

Donnée = 1db

eta(

u, 2

, 1)

0.0 0.2 0.4 0.6 0.8 1.0

0.0

0.5

1.0

1.5

Donnée = 0

dbet

a(u,

2, 2

)

0.0 0.2 0.4 0.6 0.8 1.0

0.0

0.5

1.0

1.5

Donnée = 1

dbet

a(u,

3, 2

)

Probabilité

Loi Beta(θ) ∝ θα−1(1− θ)β−1

0.0 0.2 0.4 0.6 0.8 1.0

24

68

10

α = β = 1/2

x0.0 0.2 0.4 0.6 0.8 1.0

0.6

0.8

1.0

1.2

1.4

α = β = 1

x0.0 0.2 0.4 0.6 0.8 1.0

0.0

0.5

1.0

1.5

2.0

2.5

α = 2 β = 5

x

I Espérance et mode de la loi Beta

E[θ] =α

α + βMode(θ) =

α− 1

α + β − 2

Modèle Beta-binomial

I La loi a priori est uniforme θ ∼ beta(1,1).

I Données: On observe y =∑

xi = 9 fois la valeur 1 dans un

échantillon de n = 20 répétitions (fréquence = .45)

I Vraisemblance

p(y |θ) = binom(n, θ)(y) ∝ θy (1− θ)n−y

I Loi a posteriori

p(θ|y) = beta(y + 1, n + 1− y)(θ)

Remarques

I Estimateur bayésien

E[θ|y ] =y + 1

n + 2≈ y

n, lorsque n→∞

I Intervalle de crédibilité, I , tel que Pr(θ ∈ I |y) = .95

I = (0.25, 0.65)

Loi jointe

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

● ●

●

●●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

● ●

●

●●

●

●●

●

●●

●

● ●

●●

●

●●

●

● ●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

● ●

●

●●

●

● ●

●

●●

●

●●

●

●●

● ●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

● ●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●

●●

●

●●

●

●●

●

● ●●

●

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

● ●

●

●●

●

●● ●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

● ●

●

●●

●

● ●

●

●● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

● ●

●

●●

●

● ●

●

●●

●

● ●

●

● ●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

● ●●

●

●●

●

●●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

● ●

●●

●

● ●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●●

●

●●

●

●● ●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

● ●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

● ●

●

●●

●

●●

●

●●

●

●●

● ●

●

●●

●

● ●

●

●●

●

●●

●

0 5 10 15 20

0.0

0.2

0.4

0.6

0.8

1.0

Y.sim

thet

a

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●

●●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●

●

●●●●

●

●●

●

●●

●

●●

●

●●

●

●●●

●

●●

●

●●

●

●●●

●●

●

●●●●

●

●●

●

●●

●

●●

●

Simuler la loi a posteriori

I Algorithme de rejet :

Repeat

theta <- unif(0,1)

y.s <- binom(n,theta)

Until (y.s == y)

return(theta)

I De manière générale, cet algorithme produit des simulations

selon la loi a posteriori p(θ|y)

py (θ) =∞∑s=1

(1− p(y))s−1p(y , θ) = p(θ|y).

Résultat de la simulation

0.0 0.2 0.4 0.6 0.8 1.0

01

23

Posterior distribution

u

Fre

quen

cy

posterior predictive distribution

y.rep

Den

sity

5 10 150.

000.

040.

080.

12

Exemple 3 : Classi�cation non-supervisée

I Une observation, y ∈ R, est supposée provenir d'un mélange

de K sources.

I Combinaison convexe de densités. Soit (pk)k=1,...,K , tels que∑Kk=1 pk = 1, et θ = (θk)k=1,...,K .

I On appelle mélange le modèle suivant

p(y |θ) =K∑

k=1

pkp(y |θk)

Lois gaussiennes

I Mélange de gaussiennes. Les composantes du mélanges sont

des lois normales de paramètres θk = (mk , σ2

k)

p(y |θk) = N(mk , σ2

k)(y)

Questions principales

I Combien de groupes peut on distinguer dans les données ?

I Quelles sont les moyennes et les variances des groupes ?

I Pour un individu donné, quelle est la probabilité pour qu'il

provienne du groupe k ?

Exemple de mélange (K = 2)

Histogram of y

y

Den

sity

−2 0 2 4 6

0.00

0.05

0.10

0.15

0.20

Histogram of y

yD

ensi

ty

−2 0 2 4 6

0.00

0.05

0.10

0.15

0.20

pjaune = 30% pbleu = 70%

Modèle de mélange

I Pour un échantillon : y = (y1, . . . , yn)

I Vraisemblance

p(y |θ) =n∏

i=1

(K∑

k=1

pkp(yi |θk)

)

I Mélange gaussien: Pour tout i = 1, . . . , n,

p(yi |θk) = N(mk , σ2

k)(yi ) .

Les mélanges vus comme modèles hiérarchiques

I Introduisons une variable latente (non observée) représentant

une étiquette de classe zi ∈ {1, . . . ,K} pour tout yiI Pour tout i = 1, . . . , n, considérons

p(yi |θ, zi ) = p(yi |θzi) = N(mzi

, σ2zi)(yi )

I Avec cette représentation, nous retrouvons le mélange

p(yi |θ) =K∑

k=1

p(yi |θk)p(zi = k)

Classi�cation bayésienne

I Classer consiste à estimer l'étiquette de classe zi , pour tout i .

I On atteint cet objectif en calculant la loi marginale a posteriori

p(zi |y),

I à partir de la loi jointe a posteriori

p(θ, z |y) ∝ p(y |θ, z)p(θ)p(z)

Lois marginales a posteriori des étiquettes de classe p(zi |y)

Histogram of y

y

Den

sity

−2 0 2 4 6

0.00

0.05

0.10

0.15

0.20

0.0

0.6

Lois marginales a posteriori des étiquettes de classe p(zi |y)

Histogram of y

y

Den

sity

−2 0 2 4 6

0.00

0.05

0.10

0.15

0.20

0.0

0.2

0.4

0.6

0.8

1.0

Illustration numérique : Iris de Fisher

Exemple 4 : Systèmes de recommandation

I Un ensemble de n utilisateurs peut accéder à L ressources (par

exemple, des �lms) et indiquer ses appréciations au système

I Au fur et à mesure qu'un utilisateur entre ses appréciations, le

système lui suggère de nouvelles ressources, susceptibles de lui

plaire.

I Filtrage collaboratif

I Concours Net�ix

Matrices de données

I n individus, L �lms, chacun noté par une partie des n individus

seulement

I yi` = note de préférence entre 0 et 10, ou manquante.

Mov1 Mov2 Mov3

ind1 10 8 �

ind2 2 � 4

...

Factorisation de matrice

I Modèle :

yi` = µ` +K∑

k=1

uikvk` + εi`

I εi` est un bruit de variance σ2.

I Les vecteurs V` sont indépendants et de loi N(0, IdK )(orthogonaux).

I Ces vecteurs représentent K axes factoriels principaux.

I En termes matriciels

Y = µ+ UTV + ε

Facteurs latents

Koren et al. 2009

Vraisemblance

I Soit C = UUT + σ2Id

ln p(y |U, σ2, µ) = −n2

(L ln(2π) + ln |C |+ tr(C−1S)

)I où S est la matrice de covariance empirique

S =1

n

n∑i=1

(yi − µ)(yi − µ)T

Maximum de vraisemblance : SVD (Tipping et Bishop 1999)

I Projection sur les axes factoriels:

Umax = UK (ΛK − σ2Id)1/2R

I UK est la matrice (L× K ) formée des K premiers vecteurs

propres de la matrice de covariance empirique S

I ΛK est une matrice diagonale (K × K ) contenant les K plus

grandes valeurs propres de S

I R est une matrice de rotation arbitraire.

Projections sur les axes principaux

Koren et al. 2009

Aparté: Application en génétique humaine

yi` = variant génétique (Novembre et al. 2008)

Prédire les préférences des utilisateurs d'un site web

I Pour la recommandation : la loi prédictive peut être approchée

par

yi` ∼ µ` + N(0,UmaxUTmax) + εi`

I problème : L'analyse spectrale ne gère pas les (nombreuses)

données manquantes dans le tableau de données de départ.

Loi prédictive

I La loi prédictive a posteriori est dé�nie par

p(yrep|y) =

∫p(yrep|θ)p(θ|y)dθ

I Elle est obtenue concrètement de la manière suivanteI simuler θ selon p(θ|y)I simuler yrep selon p(yrep|θ)

Un algorithme stochastique pour la prédiction

I On simule des réalisations a posteriori des matrices U et V (U

gaussien)

I En alternant la simulation des lois conditionnelles U|V , y et

V |U, yI Elles sont calculables facilement car elles correspondent à des

régressions linéaires classiques

I Loi prédictive :

y ∼ µ+ UTpostVpost + ε

I Gestion des données manquantes!

THM

I Utilisation des probabilités pour l'analyse de données

I Approche par modèle, sans approximation asymptotique

I Quanti�cation de l'incertitude

I Données manquantes, données latentes

I Approches prédictives

Pour aller plus loin

I Gelman A et al. (2004) Bayesian Data Analysis, CRC Press.

I Bishop C (2007) Pattern Recognition and Machine Learning,

Springer.

I Hastie T et al. (2009) Elements of Statistical Learning,

Springer

http://www.stanford.edu/ hastie/

Derniers mots

It was six men of Indostan

To learning much inclined

Who went to see the Elephant

(Though all of them were blind)

That each by observation

Might satisfy his mind

à J.G. Saxe

And so these men of Indostan

Disputed loud and long,

Each in his own opinion

Exceeding sti� and strong,

Though each was partly in the right,

And all were in the wrong!

J.G. Saxe (1816 − 1887)

Merci pour votre attention!

le hasard au service des algorithmes …membres-timc.imag.fr/Olivier.Francois/MPA_Cours1.pdfLois...

Documents

MODELISATION BIOMECANIQUE POUR LA …membres-timc.imag.fr/Yohan.Payan/papers/Payan Mecamat 2016.pdf · d’indentation puis la modélisation par éléments finis de cette indentation

III. Activités EEG Normales - cinapse.org · Rythmes Theta •30% des sujets activités theta antérieures faible amplitude (

La dualité a commencé avec la Transformée par …membres-timc.imag.fr/Laurent.Desbat/ProjetsRecherches/ToRIID/Semin... · La dualité a commencé avec la Transformée par Polaires

MIRAGE : Méso-Informatique Répartie pour des Applications ...membres-timc.imag.fr/Laurent.Desbat/CIMENT/cs/cs... · Modélisation des calottes glaciaires (C. Ritz, C. Dumas, P

TS Ex sur les lois normales

Lois normales, intervalle de fluctuation, estimation

TP 3 ème Année Pharmacie Identification des cellules sanguines normales et anomalies des GR

Lois Normales

PAS TRÈS NORMALES ACTIVITÉS · 2013. 1. 22. · 2 SYNOPSIS Une maison isolée, un jeune couple, un vidéaste pervers, un muet. Le tout donnant lieu à des activités normales…

Bases de Données Avancées Formes Normales - … · A. Rôle de la normalisation ... d'une base de données. Janvier 2006 Bases de Données Avancées 28 III. Formes Normales

Hydarthrose récidivante du genou à radios normales Quelle est votre attitude ? 1

EXERCICE 3 Diagonalisation d’une matrice de M3 R Note ...membres-timc.imag.fr/Arnaud.Chauviere/mat405/distanciel/corrige_D… · EXERCICE 3 - Diagonalisation d’une matrice de

Formes Normales et Normalisation Anomalies et Redondance

Traitement et analyse des signaux biomédicauxperso.esiee.fr/~alanit/isbs/isbs_2.pdf05/12/2013 3 Les propriétés non gaussiennes peuvent être identifiés en consultant l'histogramme

Intérêt de l’échographie dans l’évaluation des entorses de cheville à radiographies normales :

Les modalités d'images médicales - membres-timc.imag.frmembres-timc.imag.fr/Vincent.Luboz/enseignement/modalitésImagerie... · • Principe de formation d’une image médicale

Analyse d’images numériques en microscopiemembres-timc.imag.fr/.../COURS/Analyse-Image-2-2006.pdfTutoriaux TNT La Grande Motte 2006 Traitement d’images cours 1 - 4 Yves Usson

Tensegrity and oscillations : exploring some constitutive and …membres-timc.imag.fr/Emmanuel.Promayon/pdf/TPS+02.pdf · tensegrity system is defined as an architectural construction

La baropodométrie en routine cliniquemembres-timc.imag.fr/Yohan.Payan/papers/Perrier Revue du... · 2015-06-17 · la plateforme baropodométrique de type Zebris ... La chaussure

Extensions non gaussiennes du filtre SEEK pour lassimilation de données dans les modèles couplés physico-biogéochimiques de locéan P. Brasseur, D. Béal,