Resampling-Verfahren und Degeneration

Position in der SkillModul 2 von 3 · Thema 3 von 5

2.3 Resampling-Verfahren und Degeneration

—Lab-Punkte— / 100XP gesamt—Serie—

Wenn die Gewichte kollabieren

Gewichte multiplizieren sich von Tag zu Tag. Ein Partikel, das ein paar Beobachtungen schlecht erklärt, bekommt ein winziges Gewicht, und winzige Gewichte erholen sich nie. Nach genug Tagen trägt ein Partikel fast das ganze Gewicht, und der Rest ist vergeudete Arbeit. Das ist die Gewichtsdegeneration, die die effektive Stichprobengröße $1/\sum\tilde w^{2}$ misst. Beim SPY mit $1000$ Partikeln und ohne Resampling beträgt sie $960$ nach dem ersten Tag, $368$ nach zehn, $52$ nach fünfzig und etwa $1{,}3$ nach $250$ Tagen. Ein auf ein Partikel zusammengebrochener Filter ist eine einzige Vermutung, keine Wolke.

\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)

Resampling heilt die Degeneration: Man zieht eine neue Wolke aus $N$ Partikeln, in der ein Partikel mit Gewicht $\tilde w_i$ erwartungsgemäß $N\tilde w_i$ -mal vorkommt, und gibt jeder Kopie dasselbe Gewicht $1/N$ . Für das Ziehen gibt es mehrere Wege. Multinomial zieht $N$ unabhängige Gleichverteilte. Systematisch zieht eine einzige Gleichverteilte $u$ und nutzt $N$ gleich verteilte Zeiger $(u+i)/N$ auf den kumulierten Gewichten. Stratifiziert zieht je eine in jedem der $N$ gleichen Abschnitte. Residual gibt zuerst jedem Partikel seine ganzen Kopien, $\lfloor N\tilde w_i\rfloor$ , und zieht nur den Rest. Systematisch ist am billigsten und am gebräuchlichsten.

Systematisches Resampling von HandNehmen wir vier Partikel bei

-1,0,1,2

mit den Gewichten

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

. Die kumulierten Gewichte sind

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

. Wir ziehen

u=0{,}3

. Die Zeiger sind

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

. Zeiger

0{,}075

fällt ins zweite Fach,

0{,}325

und

0{,}575

ins dritte,

0{,}825

ins vierte. Die neue Wolke ist

0,1,1,2

: Das Partikel bei

-1

ist weg, das schwere bei

1

wurde zweimal kopiert, nah an den erwarteten

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

Kopien. Gefahrenfall: Bei den Gewichten

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

ist die effektive Stichprobengröße

1{,}06

, und jede Zeigermenge wählt nur das erste Partikel, die Wolke schrumpft auf einen einzigen Wert.

Neu ziehen, wenn die ESS niedrig ist: übliche Regel $\mathrm{ESS}<N/2$ . Jeden Tag neu zu ziehen verschwendet Vielfalt.
Systematisch nutzt eine einzige Zufallszahl: Zeiger $(u+i)/N$ auf den kumulierten Gewichten liefern eine billige, rauscharme Ziehung.
Der Preis ist die Verarmung: Viele Kopien weniger Partikel lassen die Wolke wenig vielfältig zurück, was der nächste Propagationsschritt wieder aufbauen muss.

Lab: Was bewertet wird

Erwartete Kopien15 Pkt.
Ein systematischer Zeiger10 Pkt.
Kollabierte Gewichte15 Pkt.
Verschiedene Überlebende10 Pkt.
Sollen wir heute neu ziehen10 Pkt.
Systematisches Resampling10 Pkt.
Verfahren zuordnen15 Pkt.
Warum überhaupt neu ziehen15 Pkt.

0/ 8 beantwortet

1Numerische Antwort15 Pkt.Nicht beantwortet

Bei $N=4$ Partikeln erscheint ein Partikel mit dem normierten Gewicht $0{,}426$ nach dem Neuziehen erwartungsgemäß $N\tilde w$ -mal. Wie groß ist diese Zahl? Geben Sie zwei Dezimalstellen an.

n =

akzeptiert: ± 0.02

2Numerische Antwort10 Pkt.Nicht beantwortet

Systematisches Resampling mit $N=4$ und $u=0{,}3$ nutzt die Zeiger $(u+i)/N$ . Wie groß ist der zweite Zeiger, $i=1$ ? Geben Sie drei Dezimalstellen an.

p =

akzeptiert: ± 0.001

3Numerische Antwort15 Pkt.Nicht beantwortet

Die normierten Gewichte sind $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ . Wie groß ist die effektive Stichprobengröße $1/\sum\tilde w^{2}$ ? Geben Sie zwei Dezimalstellen an.

ess =

akzeptiert: ± 0.01

4Numerische Antwort10 Pkt.Nicht beantwortet

Die Gewichte sind $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ , und das systematische Resampling nutzt $N=4$ Zeiger mit $u=0{,}5$ . Wie viele verschiedene ursprüngliche Partikel erscheinen in der neuen Wolke?

k =

akzeptiert: ± 0.01

5Auswahl10 Pkt.Nicht beantwortet

Es gibt $N=1000$ Partikel, und die effektive Stichprobengröße heute beträgt $620$ . Was tun Sie nach der Regel „neu ziehen, wenn ESS < N/2“?

6Schritte ordnen10 Pkt.Nicht beantwortet

Bringen Sie die Schritte des systematischen Resamplings in die richtige Reihenfolge.

Zum Umsortieren ziehen, oder ein Element fokussieren, mit Leertaste anheben, mit Pfeiltasten bewegen und mit Leertaste ablegen.

1Für jeden Zeiger das erste Partikel nehmen, dessen kumuliertes Gewicht ihn erreicht
2Die Gewichte zu kumulierten Gewichten aufaddieren
3N gleichmäßig verteilte Zeiger (u + i) / N setzen
4Eine einzige Gleichverteilte u ziehen
5Jeder Kopie das Gewicht 1 / N geben

7Zuordnen15 Pkt.Nicht beantwortet

Ordnen Sie jedem Resampling-Verfahren seine Art des Ziehens zu.

Wähle den Partner für jedes Element links.

Multinomial

Systematisch

Stratifiziert

Residual

8In Worten erklären15 Pkt.Nicht beantwortet

Erklären Sie in ein bis zwei Sätzen, warum ein Partikelfilter Resampling braucht und was es kostet.

Bewertet nach:Ohne es tragen wenige Partikel fast das ganze Gewicht, und der Rest ist vergeudetDer Preis ist verlorene Vielfalt, weil viele Kopien weniger Partikel bleiben und zusätzlicher Zufall entsteht0 / 400 Zeichen

Mathe-ModusEingabe per Tastatur oder LaTeXAufgabe 1 von 8 · Strg ⏎ zum Prüfen

Resampling-Verfahren und Degeneration

Position in der SkillModul 2 von 3 · Thema 3 von 5

2.3 Resampling-Verfahren und Degeneration

—Lab-Punkte— / 100XP gesamt—Serie—

Wenn die Gewichte kollabieren

\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)

Systematisches Resampling von HandNehmen wir vier Partikel bei

-1,0,1,2

mit den Gewichten

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

. Die kumulierten Gewichte sind

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

. Wir ziehen

u=0{,}3

. Die Zeiger sind

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

. Zeiger

0{,}075

fällt ins zweite Fach,

0{,}325

und

0{,}575

ins dritte,

0{,}825

ins vierte. Die neue Wolke ist

0,1,1,2

: Das Partikel bei

-1

ist weg, das schwere bei

1

wurde zweimal kopiert, nah an den erwarteten

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

Kopien. Gefahrenfall: Bei den Gewichten

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

ist die effektive Stichprobengröße

1{,}06

, und jede Zeigermenge wählt nur das erste Partikel, die Wolke schrumpft auf einen einzigen Wert.

Neu ziehen, wenn die ESS niedrig ist: übliche Regel $\mathrm{ESS}<N/2$ . Jeden Tag neu zu ziehen verschwendet Vielfalt.
Systematisch nutzt eine einzige Zufallszahl: Zeiger $(u+i)/N$ auf den kumulierten Gewichten liefern eine billige, rauscharme Ziehung.
Der Preis ist die Verarmung: Viele Kopien weniger Partikel lassen die Wolke wenig vielfältig zurück, was der nächste Propagationsschritt wieder aufbauen muss.

Lab: Was bewertet wird

Erwartete Kopien15 Pkt.
Ein systematischer Zeiger10 Pkt.
Kollabierte Gewichte15 Pkt.
Verschiedene Überlebende10 Pkt.
Sollen wir heute neu ziehen10 Pkt.
Systematisches Resampling10 Pkt.
Verfahren zuordnen15 Pkt.
Warum überhaupt neu ziehen15 Pkt.

0/ 8 beantwortet

1Numerische Antwort15 Pkt.Nicht beantwortet

Bei $N=4$ Partikeln erscheint ein Partikel mit dem normierten Gewicht $0{,}426$ nach dem Neuziehen erwartungsgemäß $N\tilde w$ -mal. Wie groß ist diese Zahl? Geben Sie zwei Dezimalstellen an.

n =

akzeptiert: ± 0.02

2Numerische Antwort10 Pkt.Nicht beantwortet

Systematisches Resampling mit $N=4$ und $u=0{,}3$ nutzt die Zeiger $(u+i)/N$ . Wie groß ist der zweite Zeiger, $i=1$ ? Geben Sie drei Dezimalstellen an.

p =

akzeptiert: ± 0.001

3Numerische Antwort15 Pkt.Nicht beantwortet

Die normierten Gewichte sind $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ . Wie groß ist die effektive Stichprobengröße $1/\sum\tilde w^{2}$ ? Geben Sie zwei Dezimalstellen an.

ess =

akzeptiert: ± 0.01

4Numerische Antwort10 Pkt.Nicht beantwortet

k =

akzeptiert: ± 0.01

5Auswahl10 Pkt.Nicht beantwortet

Es gibt $N=1000$ Partikel, und die effektive Stichprobengröße heute beträgt $620$ . Was tun Sie nach der Regel „neu ziehen, wenn ESS < N/2“?

6Schritte ordnen10 Pkt.Nicht beantwortet

Bringen Sie die Schritte des systematischen Resamplings in die richtige Reihenfolge.

Zum Umsortieren ziehen, oder ein Element fokussieren, mit Leertaste anheben, mit Pfeiltasten bewegen und mit Leertaste ablegen.

1Für jeden Zeiger das erste Partikel nehmen, dessen kumuliertes Gewicht ihn erreicht
2Die Gewichte zu kumulierten Gewichten aufaddieren
3N gleichmäßig verteilte Zeiger (u + i) / N setzen
4Eine einzige Gleichverteilte u ziehen
5Jeder Kopie das Gewicht 1 / N geben

7Zuordnen15 Pkt.Nicht beantwortet

Ordnen Sie jedem Resampling-Verfahren seine Art des Ziehens zu.

Wähle den Partner für jedes Element links.

Multinomial

Systematisch

Stratifiziert

Residual

8In Worten erklären15 Pkt.Nicht beantwortet

Erklären Sie in ein bis zwei Sätzen, warum ein Partikelfilter Resampling braucht und was es kostet.

Mathe-ModusEingabe per Tastatur oder LaTeXAufgabe 1 von 8 · Strg ⏎ zum Prüfen

Resampling-Verfahren und Degeneration

Wenn die Gewichte kollabieren

Lab: Was bewertet wird

Melde dich an, um deinen Code auszuführen.

Resampling-Verfahren und Degeneration

Wenn die Gewichte kollabieren

Lab: Was bewertet wird

Melde dich an, um deinen Code auszuführen.