Particle Filter

Gli approcci lineari e quasi lineari proposti da Kalman possono essere usati in quei problemi dove lo stato è gaussiano o quasi gaussiano con distribuzione unimodale: la stima dello stato all'istante di tempo $k$ è funzione diretta dell'unica stima dello stato all'istante di tempo $k-1$ e della covarianza di tale stima.

Quando è richiesto di ricavare la distribuzione di probabilità non gaussiana dello stato del sistema $p(x_k; u_{k-1}; z_{k})$ all'istante di tempo $k$, funzione degli ingressi e delle osservazioni, gli approcci di tipo Kalman non sono più soddisfacenti.

Gli approcci grid based sono adatti a quei problemi, di fatto poco comuni, dove lo stato è discretizzabile e finito. Gli approcci histogram based/occupacy grid si adattano a una classe di problemi maggiore che però, a causa del campionamento uniforme dello stato, scalano molto male con l'aumentare delle dimensioni.

Si consideri nuovamente il risultato espresso dall'equazione (2.4): per estrarre una generica statistica $h(\cdot)$ (per esempio media, o varianza) da una distribuzione di probabilità $p(x)$, si fa uso dell'espressione

$$\bar{h} \stackrel{def}{=} \int_X h(x) p(x) dx$$ (2.128)

Nel caso in cui tale stima non si possa ottenere per via analitica, è comunque possibile ricavarla per via indiretta, attraverso l'analisi di $x_i$ campioni indipendenti, con $1 \leq i \leq N$, estratti casualmente con distribuzione esattamente $p$.

Dati i campioni $x_i$ generati in questo modo, la stima Monte Carlo di $h(\cdot)$ è data da

$$\bar{h} \approx \frac{1}{N} \sum_{i=1}^{N} h(x_i)$$ (2.129)

Monte Carlo non risolve tutti i problemi né suggerisce come ottenere i campioni casuali in maniera efficiente. Il problema diventa sensibile nei casi multidimensionali dove le aree in cui la probabilità assume valori significativi sono estremamente esigue. L'obiettivo che si pone infatti l'Important Sampling (IS) è campionare la distribuzione $p(x)$ in regioni “importanti” in modo da massimizzare l'efficienza computazionale.

L'idea dell'Important Sampling è quella di prendere una più semplice distribuzione $q(x)$ (Importance density), al posto della vera $p(x)$ normalmente difficile da campionare (o da riprodurre), effettuando la sostituzione

$$\int_X h(x) p(x) dx = \int_X h(x) \frac{p(x)}{q(x)} q(x) dx = \int_X h(x) w(x) q(x) dx$$

avendo introdotto il sistema di pesi $w(x)$. Attraverso l'uso di adeguati pesi pertanto è possibile modificare l'equazione (2.129) in

$$\bar{h} \approx \frac{1}{N} \sum_{i=1}^{N} w_i h(x_i)$$ (2.130)

dove $w_i \propto W_i = p(x_i)/q(x_i)$ rappresenta un peso correttivo, fattore di importanza (important weights), per convertire la distribuzione di supporto $q$ a quella reale $p$. I pesi $W_i$ devono essere normalizzati

$$w_i = \frac{W_i}{\sum W_i}$$ (2.131)

per poter essere utilizzati.

Più la distribuzione $q(x)$ è simile alla $p(x)$, più la stima risulterà corretta. D'altra parte la distribuzione $q(x)$ deve essere molto semplice da campionare, scegliendo per esempio la distribuzione uniforme o gaussiana.

Data la conoscenza dei filtri bayesiani e con le tecniche Monte Carlo è possibile affrontare la teoria dei filtri particellari. Lo stato all'istante $k$ è rappresentato da un insieme di campioni (particles) e ogni campione è un ipotesi dello stato da vagliare. Si può parlare di una serie di particelle ottenute a priori dell'osservazione, applicando l'equazione (2.130) alla funzione di evoluzione dello stato.

Se si applica direttamente la teoria bayesiana ai campioni della distribuzione stimata è possibile modificare i pesi $w_i$ associati ai campioni usando contemporaneamente il modello del sistema e della percezione (Sequential Important Sampling):

$$w_{k,i} \propto w_{k-1,i} \frac{ p (z_k \vert x_{k,i} ) p (x_{k,i} \vert x_{k-1,i} ) } { q (x_{k,i} \vert x_{k-1,i}, z_k ) }$$ (2.132)

In questo modo i campioni iniziali sono sempre gli stessi, ma cambiano solo i pesi $w_i$ associati.

Quando possibile è conveniente usare come Important density la distribuzione a priori

$$q (x_{k,i} \vert x_{k-1,i}, z_k ) = p (x_{k,i} \vert x_{k-1,i} )$$ (2.133)

in modo che, introdotta in (2.132), si ottenga

$$w_{k,i} \propto w_{k-1,i} p (z_k \vert x_{k,i} )$$ (2.134)

Il problema dell'approccio SIS è che dopo poche iterazioni solo alcune particelle avranno il fattore peso non trascurabile (weight degeneracy).

BootStrap/Sequential Importance Resampling

Una soluzione più semplice è la Sequential Important Resampling dove i pesi non dipendono dalle iterazioni precedenti ma sono invece i campioni a cambiare, in seguito a una fase di resampling.

La fase di ricampionamento consiste nel generare un nuovo insieme di particelle $x'$ ricampionando $N_s$ volte una versione discreta approssimata di $p(\mathbf{x}_k \vert \mathbf{z}_k)$ data da

$$p( \mathbf{x}_k \vert \mathbf{z}_k ) \approx \sum_{i=1}^{N_s} w_{k,i} \delta (\mathbf{x}_k - \mathbf{x}_{k,i} )$$ (2.135)

avendo definito

$$w_{k,i} \propto p(\mathbf{z}_k \vert \mathbf{x}_k)$$ (2.136)

I filtri SIR non evitano il caso degenere (di fatto anzi eliminano definitivamente le particelle poco probabili), tuttavia portano a un notevole risparmio computazionale e concentrano la ricerca della soluzione intorno agli stati più probabili.

Esistono svariati algoritmi per eseguire il ricampionamento. Un'elenco, non sicuramente esaustivo, di tali algoritmi è: Simple Random Resampling, Roulette Wheel / Fitness proportionate selection, Stochastic universal sampling, Multinomial Resamping, Residual Resampling, Stratified Resampling, Systematic Resampling.