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 Filters/Occupancy Grid Methods 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$$ (3.41)

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)$$ (3.42)

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'Importance Sampling (IS) è campionare la distribuzione $p(x)$ in regioni “importanti” in modo da massimizzare l'efficienza computazionale.

L'idea dell'Importance 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 (3.42) in

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

dove

$$W_i = \frac{p(x_i)}{q(x_i)}$$

rappresenta un peso correttivo, detto peso di importanza (importance weight), per convertire la distribuzione di supporto $q$ in quella reale $p$. I pesi vengono quindi normalizzati

$$w_i = \frac{W_i} {\sum_{j=1}^{N} W_j}$$ (3.44)

in modo che

$$\sum_{i=1}^{N} w_i = 1.$$

Più la distribuzione $q(x)$ è vicina a $p(x)$ nelle regioni a maggiore probabilità, minore sarà la varianza dei pesi e più efficiente sarà la stima. 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 (3.43) 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 Importance 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 ) }$$ (3.45)

Ad ogni iterazione le particelle vengono propagate secondo la distribuzione proposta $q(\cdot)$ e i loro pesi $w_i$ vengono aggiornati ricorsivamente secondo l'equazione (3.45).

Quando possibile è conveniente usare come Importance 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} )$$ (3.46)

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

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

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