8. Monte Carlo, Importance sampling

Monte Carlo metody

Monte Carlo metody jsou široká třída algoritmů, které využívají opakované náhodné vzorkování k odhadu numerických výsledků. Tyto metody jsou zásadní pro řešení problémů, které jsou analyticky neřešitelné nebo příliš komplexní.

SIS

Sequential Importance Sampling (SIS) je pokročilá metoda pro sekvenční odhad stavů v dynamických systémech. Tato metoda je obzvláště užitečná v situacích, kde modely nejsou lineární a kde tradiční metody jako Extended Kalman Filter (EKF) nebo Unscented Kalman Filter (UKF) nemusí poskytovat přesné výsledky. SIS využívá konceptu importance sampling, což je technika, která umožňuje efektivnější vzorkování z rozdělení pravděpodobnosti.

Klíčové Komponenty SIS

1. Stavové Modely:

   • Stav systému ($x_t$): Toto je neznámá proměnná, kterou chceme odhadnout.
   • Model vývoje ($f_t$): Určuje, jak se stav mění v čase.
   • Pozorování ($y_t$): Jsou to data, která máme k dispozici a která souvisí se stavem systému.
   • Model pozorování ($h_t$): Popisuje vztah mezi stavem systému a pozorováními.

2. Empirická Distribuce:

   • Zahrnuje soubor vzorků (reprezentace stavu systému) a jejich váhy, které odrážejí důležitost každého vzorku.

Algoritmus

1. Inicializace:

   • Vytvoření vzorků: Vygenerujeme počáteční vzorky stavu systému.
   • Rovnoměrné váhy: Každému vzorku přiřadíme stejnou váhu.

2. Iterace pro každý časový krok:

   • Predikce: Aktualizujeme vzorky na základě modelu vývoje.
   • Update: Upravíme váhy vzorků podle toho, jak dobře vzorky odpovídají pozorováním.
   • Normalizace vah: Upravíme váhy tak, aby jejich součet byl roven 1.

3. Výsledný odhad:

   • Na základě váženého průměru vzorků získáme odhad aktuálního stavu systému.

Limitace

• Problém degenerace vah:

  • Většina vzorků získává velmi nízké váhy.
  • Několik málo vzorků dominuje s vysokými vahami.
  • Vede to k nepřesné reprezentaci stavu systému.

• Důsledky degenerace:

  • Snížení efektivnosti a přesnosti odhadu.
  • Omezená schopnost algoritmu správně reagovat na nová data.

SIR

Sequential Importance Resampling (SIR), známý také jako particle filter, je významným rozšířením Sequential Importance Sampling (SIS) metody. Hlavním přínosem SIR je řešení problému degenerace vah, který je typický pro SIS. Degenerace vah nastává, když většina vah konverguje k nule a několik málo vzorků dominuje. Tento jev vede ke snížené efektivitě vzorkování a může způsobit, že odhadované distribuce neodráží skutečný stav systému.

Resampling v Particle Filtru

Resampling je klíčovým krokem v SIR a je způsob, jakým filtr řeší problém degenerace vah. Resampling spočívá v selektivním vzorkování z aktuální sady částic na základě jejich vah, což zajišťuje, že částice s vyššími váhami mají vyšší šanci být vybrány, zatímco částice s nízkými váhami jsou pravděpodobně zahozeny.

Algoritmus

1. Inicializace:

   • Vytvoření vzorků: Vygenerujeme počáteční vzorky stavu systému, stejně jako v SIS.
   • Rovnoměrné váhy: Každému vzorku přiřadíme stejnou váhu na začátku procesu.

2. Iterace pro každý časový krok:

   • Resampling: Provedeme resampling vzorků na základě jejich vah. Vzorky s vyššími váhami mají větší šanci být vybrány, zatímco ty s nižšími váhami mohou být zahozeny.
   • Predikce: Aktualizujeme vzorky na základě modelu vývoje, podobně jako v SIS.
   • Update: Upravíme váhy vzorků podle toho, jak dobře vzorky odpovídají novým pozorováním.
   • Normalizace vah: Převedeme váhy na rozdělení pravděpodobnosti tak, aby jejich součet byl roven 1.

3. Výsledný odhad:

   • Opět získáme odhad aktuálního stavu systému na základě váženého průměru vzorků po resampling.