Schémas de rééchantillonnage et dégénérescence

Position dans le parcoursModule 2 sur 3 · Sujet 3 sur 5

2.3 Schémas de rééchantillonnage et dégénérescence

—Score du lab— / 100XP total—Série—

Quand les poids s'effondrent

Les poids se multiplient d'un jour à l'autre. Une particule qui explique mal quelques observations reçoit un poids minuscule, et les poids minuscules ne remontent jamais. Après assez de jours, une particule porte presque tout le poids et les autres sont du travail perdu. C'est la dégénérescence des poids, que mesure la taille d'échantillon effective $1/\sum\tilde w^{2}$ . Sur SPY avec $1000$ particules et sans rééchantillonnage, elle vaut $960$ après le premier jour, $368$ après dix, $52$ après cinquante et environ $1{,}3$ après $250$ jours. Un filtre réduit à une particule est une seule hypothèse, pas un nuage.

\mathrm{ESS}=\frac{1}{\sum_i\tilde w_i^{2}},\qquad \mathrm{ESS}<\frac N2,\qquad \frac{u+i}{N},\ \ i=0,\dots,N-1

(1)

Le rééchantillonnage guérit la dégénérescence : on tire un nouveau nuage de $N$ particules où une particule de poids $\tilde w_i$ doit apparaître $N\tilde w_i$ fois en moyenne, puis on donne à chaque copie le même poids $1/N$ . Il y a plusieurs façons de tirer. Le multinomial tire $N$ uniformes indépendants. Le systématique tire un seul uniforme $u$ et utilise $N$ pointeurs régulièrement espacés $(u+i)/N$ sur les poids cumulés. Le stratifié tire un uniforme dans chacune des $N$ tranches égales. Le résiduel donne d'abord à chaque particule ses copies entières, $\lfloor N\tilde w_i\rfloor$ , et ne tire que le reste. Le systématique est le moins cher et le plus utilisé.

Le rééchantillonnage systématique à la mainPrenons quatre particules en

-1,0,1,2

de poids

0{,}058,\ 0{,}258,\ 0{,}426,\ 0{,}258

. Les poids cumulés sont

0{,}058,\ 0{,}316,\ 0{,}742,\ 1

. Tirons

u=0{,}3

. Les pointeurs sont

(0{,}3+i)/4=0{,}075,\ 0{,}325,\ 0{,}575,\ 0{,}825

. Le pointeur

0{,}075

tombe dans la deuxième case,

0{,}325

0{,}575

dans la troisième,

0{,}825

dans la quatrième. Le nouveau nuage est

0,1,1,2

: la particule en

-1

a disparu et la lourde en

1

est copiée deux fois, proche de ses

4\times0{,}426=1{,}7

copies attendues. Cas dangereux : avec des poids

0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01

, la taille d'échantillon effective est

1{,}06

, et tout jeu de pointeurs ne choisit que la première particule : le nuage se réduit à une seule valeur.

Rééchantillonner quand l'ESS est basse : règle courante $\mathrm{ESS}<N/2$ . Rééchantillonner chaque jour gaspille de la diversité.
Le systématique utilise un seul nombre aléatoire : les pointeurs $(u+i)/N$ sur les poids cumulés donnent un tirage économique et peu bruité.
Le prix est l'appauvrissement : beaucoup de copies de quelques particules laissent le nuage peu varié, ce que l'étape de propagation suivante doit reconstruire.

Lab : ce qui est noté

Copies attendues15 pts
Un pointeur systématique10 pts
Poids effondrés15 pts
Survivantes distinctes10 pts
Faut-il rééchantillonner aujourd'hui10 pts
Rééchantillonnage systématique10 pts
Associer les schémas15 pts
Pourquoi rééchantillonner15 pts

0/ 8 traités

1Réponse numérique15 ptsSans réponse

Avec $N=4$ particules, une particule de poids normalisé $0{,}426$ doit apparaître $N\tilde w$ fois après rééchantillonnage. Que vaut ce nombre ? Donnez deux décimales.

n =

accepté : ± 0.02

2Réponse numérique10 ptsSans réponse

Le rééchantillonnage systématique avec $N=4$ et $u=0{,}3$ utilise les pointeurs $(u+i)/N$ . Que vaut le deuxième pointeur, $i=1$ ? Donnez trois décimales.

p =

accepté : ± 0.001

3Réponse numérique15 ptsSans réponse

Les poids normalisés sont $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ . Que vaut la taille d'échantillon effective $1/\sum\tilde w^{2}$ ? Donnez deux décimales.

ess =

accepté : ± 0.01

4Réponse numérique10 ptsSans réponse

Les poids sont $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ et le rééchantillonnage systématique utilise $N=4$ pointeurs avec $u=0{,}5$ . Combien de particules d'origine différentes apparaissent dans le nouveau nuage ?

k =

accepté : ± 0.01

5Choix10 ptsSans réponse

Il y a $N=1000$ particules et la taille d'échantillon effective du jour est $620$ . Avec la règle « rééchantillonner si ESS < N/2 », que faites-vous ?

6Remettre les étapes dans l'ordre10 ptsSans réponse

Mettez dans l'ordre les étapes du rééchantillonnage systématique.

Faites glisser pour réordonner, ou placez le focus sur un élément, Espace pour le soulever, les flèches pour le déplacer et Espace pour le déposer.

1Pour chaque pointeur, prendre la première particule dont le poids cumulé l'atteint
2Additionner les poids en poids cumulés
3Placer N pointeurs régulièrement espacés (u + i) / N
4Tirer un seul nombre uniforme u
5Donner à chaque copie le poids 1 / N

7Associer15 ptsSans réponse

Associez chaque schéma de rééchantillonnage à sa façon de tirer.

Choisissez le partenaire de chaque élément de gauche.

Multinomial

Systématique

Stratifié

Résiduel

8Expliquer avec des mots15 ptsSans réponse

En une ou deux phrases, expliquez pourquoi un filtre particulaire a besoin du rééchantillonnage et ce que cela coûte.

Noté sur :Sans cela quelques particules finissent avec presque tout le poids et les autres sont gaspilléesLe prix est une perte de diversité, car il reste beaucoup de copies de quelques particules et du hasard s'ajoute0 / 400 caractères

Mode mathsSaisie au clavier ou en LaTeXExercice 1 sur 8 · Ctrl ⏎ pour vérifier

Schémas de rééchantillonnage et dégénérescence

Position dans le parcoursModule 2 sur 3 · Sujet 3 sur 5

2.3 Schémas de rééchantillonnage et dégénérescence

—Score du lab— / 100XP total—Série—

Quand les poids s'effondrent

\mathrm{ESS}=\frac{1}{\sum_i\tilde w_i^{2}},\qquad \mathrm{ESS}<\frac N2,\qquad \frac{u+i}{N},\ \ i=0,\dots,N-1

(1)

Le rééchantillonnage systématique à la mainPrenons quatre particules en

-1,0,1,2

de poids

0{,}058,\ 0{,}258,\ 0{,}426,\ 0{,}258

. Les poids cumulés sont

0{,}058,\ 0{,}316,\ 0{,}742,\ 1

. Tirons

u=0{,}3

. Les pointeurs sont

(0{,}3+i)/4=0{,}075,\ 0{,}325,\ 0{,}575,\ 0{,}825

. Le pointeur

0{,}075

tombe dans la deuxième case,

0{,}325

0{,}575

dans la troisième,

0{,}825

dans la quatrième. Le nouveau nuage est

0,1,1,2

: la particule en

-1

a disparu et la lourde en

1

est copiée deux fois, proche de ses

4\times0{,}426=1{,}7

copies attendues. Cas dangereux : avec des poids

0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01

, la taille d'échantillon effective est

1{,}06

, et tout jeu de pointeurs ne choisit que la première particule : le nuage se réduit à une seule valeur.

Rééchantillonner quand l'ESS est basse : règle courante $\mathrm{ESS}<N/2$ . Rééchantillonner chaque jour gaspille de la diversité.
Le systématique utilise un seul nombre aléatoire : les pointeurs $(u+i)/N$ sur les poids cumulés donnent un tirage économique et peu bruité.
Le prix est l'appauvrissement : beaucoup de copies de quelques particules laissent le nuage peu varié, ce que l'étape de propagation suivante doit reconstruire.

Lab : ce qui est noté

Copies attendues15 pts
Un pointeur systématique10 pts
Poids effondrés15 pts
Survivantes distinctes10 pts
Faut-il rééchantillonner aujourd'hui10 pts
Rééchantillonnage systématique10 pts
Associer les schémas15 pts
Pourquoi rééchantillonner15 pts

0/ 8 traités

1Réponse numérique15 ptsSans réponse

Avec $N=4$ particules, une particule de poids normalisé $0{,}426$ doit apparaître $N\tilde w$ fois après rééchantillonnage. Que vaut ce nombre ? Donnez deux décimales.

n =

accepté : ± 0.02

2Réponse numérique10 ptsSans réponse

Le rééchantillonnage systématique avec $N=4$ et $u=0{,}3$ utilise les pointeurs $(u+i)/N$ . Que vaut le deuxième pointeur, $i=1$ ? Donnez trois décimales.

p =

accepté : ± 0.001

3Réponse numérique15 ptsSans réponse

Les poids normalisés sont $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ . Que vaut la taille d'échantillon effective $1/\sum\tilde w^{2}$ ? Donnez deux décimales.

ess =

accepté : ± 0.01

4Réponse numérique10 ptsSans réponse

k =

accepté : ± 0.01

5Choix10 ptsSans réponse

Il y a $N=1000$ particules et la taille d'échantillon effective du jour est $620$ . Avec la règle « rééchantillonner si ESS < N/2 », que faites-vous ?

6Remettre les étapes dans l'ordre10 ptsSans réponse

Mettez dans l'ordre les étapes du rééchantillonnage systématique.

Faites glisser pour réordonner, ou placez le focus sur un élément, Espace pour le soulever, les flèches pour le déplacer et Espace pour le déposer.

1Pour chaque pointeur, prendre la première particule dont le poids cumulé l'atteint
2Additionner les poids en poids cumulés
3Placer N pointeurs régulièrement espacés (u + i) / N
4Tirer un seul nombre uniforme u
5Donner à chaque copie le poids 1 / N

7Associer15 ptsSans réponse

Associez chaque schéma de rééchantillonnage à sa façon de tirer.

Choisissez le partenaire de chaque élément de gauche.

Multinomial

Systématique

Stratifié

Résiduel

8Expliquer avec des mots15 ptsSans réponse

En une ou deux phrases, expliquez pourquoi un filtre particulaire a besoin du rééchantillonnage et ce que cela coûte.

Mode mathsSaisie au clavier ou en LaTeXExercice 1 sur 8 · Ctrl ⏎ pour vérifier

Schémas de rééchantillonnage et dégénérescence

Quand les poids s'effondrent

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.

Schémas de rééchantillonnage et dégénérescence

Quand les poids s'effondrent

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.