Esquemas de reamostragem e degeneração

Posição no roteiroMódulo 2 de 3 · Tópico 3 de 5

2.3 Esquemas de reamostragem e degeneração

—Nota do lab— / 100XP total—Sequência—

Quando os pesos colapsam

Os pesos se multiplicam de um dia para o outro. Uma partícula que explica mal algumas observações recebe um peso minúsculo, e pesos minúsculos nunca se recuperam. Depois de dias suficientes uma partícula carrega quase todo o peso e as demais são trabalho perdido. É a degeneração dos pesos, que o tamanho amostral efetivo $1/\sum\tilde w^{2}$ mede. No SPY com $1000$ partículas e sem reamostragem, ele vale $960$ após o primeiro dia, $368$ após dez, $52$ após cinquenta e cerca de $1{,}3$ após $250$ dias. Um filtro reduzido a uma partícula é um único palpite, não uma nuvem.

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

A reamostragem cura a degeneração: sorteia-se uma nuvem nova de $N$ partículas na qual uma partícula de peso $\tilde w_i$ aparece em média $N\tilde w_i$ vezes, e dá-se a cada cópia o mesmo peso $1/N$ . Há várias formas de sortear. O multinomial sorteia $N$ uniformes independentes. O sistemático sorteia um único uniforme $u$ e usa $N$ ponteiros igualmente espaçados $(u+i)/N$ sobre os pesos acumulados. O estratificado sorteia um uniforme em cada uma das $N$ fatias iguais. O residual dá primeiro a cada partícula suas cópias inteiras, $\lfloor N\tilde w_i\rfloor$ , e só sorteia o resto. O sistemático é o mais barato e o mais usado.

Reamostragem sistemática à mãoTomemos quatro partículas em

-1,0,1,2

com pesos

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

. Os pesos acumulados são

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

. Sorteemos

u=0{,}3

. Os ponteiros são

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

. O ponteiro

0{,}075

cai na segunda casa,

0{,}325

0{,}575

na terceira,

0{,}825

na quarta. A nuvem nova é

0,1,1,2

: a partícula em

-1

sumiu e a pesada em

1

foi copiada duas vezes, perto das

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

cópias esperadas. Caso perigoso: com pesos

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

o tamanho amostral efetivo é

1{,}06

e qualquer conjunto de ponteiros escolhe só a primeira partícula, então a nuvem se reduz a um valor distinto.

Reamostrar quando o ESS é baixo: regra comum $\mathrm{ESS}<N/2$ . Reamostrar todo dia desperdiça diversidade.
O sistemático usa um único número aleatório: ponteiros $(u+i)/N$ sobre os pesos acumulados dão um sorteio barato e de pouco ruído.
O preço é o empobrecimento: muitas cópias de poucas partículas deixam a nuvem com pouca variedade, que o próximo passo de propagação precisa reconstruir.

Lab: o que é avaliado

Cópias esperadas15 pts
Um ponteiro sistemático10 pts
Pesos colapsados15 pts
Sobreviventes distintas10 pts
Devemos reamostrar hoje10 pts
Reamostragem sistemática10 pts
Associar os esquemas15 pts
Por que reamostrar15 pts

0/ 8 respondidas

1Resposta numérica15 ptsSem resposta

Com $N=4$ partículas, uma partícula com peso normalizado $0{,}426$ aparece em média $N\tilde w$ vezes após a reamostragem. Quanto é esse número? Dê duas casas decimais.

n =

aceito: ± 0.02

2Resposta numérica10 ptsSem resposta

A reamostragem sistemática com $N=4$ e $u=0{,}3$ usa os ponteiros $(u+i)/N$ . Quanto vale o segundo ponteiro, $i=1$ ? Dê três casas decimais.

p =

aceito: ± 0.001

3Resposta numérica15 ptsSem resposta

Os pesos normalizados são $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ . Quanto vale o tamanho amostral efetivo $1/\sum\tilde w^{2}$ ? Dê duas casas decimais.

ess =

aceito: ± 0.01

4Resposta numérica10 ptsSem resposta

Os pesos são $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ e a reamostragem sistemática usa $N=4$ ponteiros com $u=0{,}5$ . Quantas partículas originais diferentes aparecem na nova nuvem?

k =

aceito: ± 0.01

5Escolha10 ptsSem resposta

Há $N=1000$ partículas e o tamanho amostral efetivo de hoje é $620$ . Com a regra «reamostrar se ESS < N/2», o que você faz?

6Ordenar os passos10 ptsSem resposta

Coloque em ordem os passos da reamostragem sistemática.

Arraste para reordenar, ou foque um item, Espaço para levantá-lo, setas para movê-lo e Espaço para soltá-lo.

1Para cada ponteiro, tomar a primeira partícula cujo peso acumulado o alcança
2Somar os pesos em pesos acumulados
3Colocar N ponteiros igualmente espaçados (u + i) / N
4Sortear um único número uniforme u
5Dar a cada cópia o peso 1 / N

7Associar15 ptsSem resposta

Associe cada esquema de reamostragem à sua forma de sortear.

Escolha o par de cada item da esquerda.

Multinomial

Sistemático

Estratificado

Residual

8Explicar com palavras15 ptsSem resposta

Em uma ou duas frases, explique por que um filtro de partículas precisa de reamostragem e quanto ela custa.

Avaliado por:Sem ela poucas partículas ficam com quase todo o peso e as demais são desperdiçadasO preço é a perda de diversidade, pois restam muitas cópias de poucas partículas e acrescenta-se aleatoriedade0 / 400 caracteres

Modo matemáticaEntrada por teclado ou LaTeXTarefa 1 de 8 · Ctrl ⏎ para verificar

Esquemas de reamostragem e degeneração

Posição no roteiroMódulo 2 de 3 · Tópico 3 de 5

2.3 Esquemas de reamostragem e degeneração

—Nota do lab— / 100XP total—Sequência—

Quando os pesos colapsam

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

Reamostragem sistemática à mãoTomemos quatro partículas em

-1,0,1,2

com pesos

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

. Os pesos acumulados são

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

. Sorteemos

u=0{,}3

. Os ponteiros são

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

. O ponteiro

0{,}075

cai na segunda casa,

0{,}325

0{,}575

na terceira,

0{,}825

na quarta. A nuvem nova é

0,1,1,2

: a partícula em

-1

sumiu e a pesada em

1

foi copiada duas vezes, perto das

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

cópias esperadas. Caso perigoso: com pesos

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

o tamanho amostral efetivo é

1{,}06

e qualquer conjunto de ponteiros escolhe só a primeira partícula, então a nuvem se reduz a um valor distinto.

Reamostrar quando o ESS é baixo: regra comum $\mathrm{ESS}<N/2$ . Reamostrar todo dia desperdiça diversidade.
O sistemático usa um único número aleatório: ponteiros $(u+i)/N$ sobre os pesos acumulados dão um sorteio barato e de pouco ruído.
O preço é o empobrecimento: muitas cópias de poucas partículas deixam a nuvem com pouca variedade, que o próximo passo de propagação precisa reconstruir.

Lab: o que é avaliado

Cópias esperadas15 pts
Um ponteiro sistemático10 pts
Pesos colapsados15 pts
Sobreviventes distintas10 pts
Devemos reamostrar hoje10 pts
Reamostragem sistemática10 pts
Associar os esquemas15 pts
Por que reamostrar15 pts

0/ 8 respondidas

1Resposta numérica15 ptsSem resposta

Com $N=4$ partículas, uma partícula com peso normalizado $0{,}426$ aparece em média $N\tilde w$ vezes após a reamostragem. Quanto é esse número? Dê duas casas decimais.

n =

aceito: ± 0.02

2Resposta numérica10 ptsSem resposta

A reamostragem sistemática com $N=4$ e $u=0{,}3$ usa os ponteiros $(u+i)/N$ . Quanto vale o segundo ponteiro, $i=1$ ? Dê três casas decimais.

p =

aceito: ± 0.001

3Resposta numérica15 ptsSem resposta

Os pesos normalizados são $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ . Quanto vale o tamanho amostral efetivo $1/\sum\tilde w^{2}$ ? Dê duas casas decimais.

ess =

aceito: ± 0.01

4Resposta numérica10 ptsSem resposta

Os pesos são $0{,}97,\ 0{,}01,\ 0{,}01,\ 0{,}01$ e a reamostragem sistemática usa $N=4$ ponteiros com $u=0{,}5$ . Quantas partículas originais diferentes aparecem na nova nuvem?

k =

aceito: ± 0.01

5Escolha10 ptsSem resposta

Há $N=1000$ partículas e o tamanho amostral efetivo de hoje é $620$ . Com a regra «reamostrar se ESS < N/2», o que você faz?

6Ordenar os passos10 ptsSem resposta

Coloque em ordem os passos da reamostragem sistemática.

Arraste para reordenar, ou foque um item, Espaço para levantá-lo, setas para movê-lo e Espaço para soltá-lo.

1Para cada ponteiro, tomar a primeira partícula cujo peso acumulado o alcança
2Somar os pesos em pesos acumulados
3Colocar N ponteiros igualmente espaçados (u + i) / N
4Sortear um único número uniforme u
5Dar a cada cópia o peso 1 / N

7Associar15 ptsSem resposta

Associe cada esquema de reamostragem à sua forma de sortear.

Escolha o par de cada item da esquerda.

Multinomial

Sistemático

Estratificado

Residual

8Explicar com palavras15 ptsSem resposta

Em uma ou duas frases, explique por que um filtro de partículas precisa de reamostragem e quanto ela custa.

Modo matemáticaEntrada por teclado ou LaTeXTarefa 1 de 8 · Ctrl ⏎ para verificar

Esquemas de reamostragem e degeneração

Quando os pesos colapsam

Lab: o que é avaliado

Entre para executar o seu código.

Esquemas de reamostragem e degeneração

Quando os pesos colapsam

Lab: o que é avaliado

Entre para executar o seu código.