Binärer Bayesscher Filter
Einfache Sprache
Ein Binärer Bayesscher Filter ist ein Bayesscher Filter, der unter der Voraussetzung angewendet werden kann, dass der Zustand statisch ist, also das was geschätzt werden soll sich nicht verändert. So z.B. in einer statischen Belegungsgitterkarte der Belegungswert $m_i$.
Herleitung
Wir nehmen eine statische Zustand an, der entweder $x$ oder $\neg x$ annimmt und sich nicht verändert (deswegen kein Zeitindex). Dann ist der Belief nur von den Wahrnehmungen $z_{1:t}$ abhängig, die bist $t$ aufgezeichnet wurden. Also
$$\textrm{Bel}_t(x) = p(x\mid z_{1:t})$$Alternative Lösungsweg
Das Problem könnte mit einem Histogram-Filter gelöst werden, aber hier wird ein andere Ansatz verfolgt.
Der Belief wird in Abhängigkeit der log odds $l_t$ repräsentiert. Also
$$\text{Bel}_t(x) = 1-\frac{1}{1+\exp(l_t)}$$Ausgehend von der Filtergleichung des Bayes-Filter mit expliziter Normalisierung ergibt sich folgende Ableitung
$$\begin{align}p(x\mid z_{1:t}) &= \frac{p(z_t\mid x, z_{1:t-1})p(x\mid z_{1:t-1}) }{p(z_t\mid z_{1:t-1}) }&\Huge|\normalsize\text{Bayes-Filter}\\&= \frac{p(z_t\mid x)p(x\mid z_{1:t-1}) }{p(z_t\mid z_{1:t-1}) }&\Huge|\normalsize\text{Weglassen}\\&= \frac{p(x\mid z_t)p(z_t)p(x\mid z_{1:t-1}) }{p(x)p(z_t\mid z_{1:t-1}) }&\Huge|\normalsize\text{Satz von Bayes}\\\end{align}$$Für $\neg x$ ergibt sich analog
$$p(\neg x\mid z_{1:t}) = \frac{p(\neg x\mid z_t)p(z_t)p(\neg x\mid z_{1:t-1}) }{p(\neg x)p(z_t\mid z_{1:t-1}) }\;.$$Die odds ratio ergibt sich dann als
$$\begin{align}\frac{p(x\mid z_{1:t})}{p(\neg x\mid z_{1:t})} &= \frac{\frac{p(x\mid z_t)p(z_t)p(x\mid z_{1:t-1}) }{p(x)p(z_t\mid z_{1:t-1}) }}{\frac{p(\neg x\mid z_t)p(z_t)p(\neg x\mid z_{1:t-1}) }{p(\neg x)p(z_t\mid z_{1:t-1}) }} &\Huge|\normalsize\text{Def. \textit{odds ratio}}\\&= \frac{p(x\mid z_t)}{p(\neg x\mid z_t)}\frac{p(x\mid z_{1:t-1})}{p(\neg x\mid z_{1:t-1})} \frac{p(\neg x)}{p(x)}&\Huge|\normalsize\text{Umstellen}\\&= \frac{p(x\mid z_t)}{1- p(x\mid z_t)}\frac{p(x\mid z_{1:t-1})}{1- p(x\mid z_{1:t-1})} \frac{1-p(x)}{p(x)}&\Huge|\normalsize\text{$x$ is binär}\\\end{align}$$Im letzen Schritt von der odds ratio der Logarithmus genommen und man erhält die log odds.
$$\begin{align} l_t(x) &= \log\left(\frac{p(x\mid z_t)}{1- p(x\mid z_t)}\frac{p(x\mid z_{1:t-1})}{1- p(x\mid z_{1:t-1})} \frac{1-p(x)}{p(x)}\right)&\Huge|\normalsize\text{Def. \textit{log odds}}\\&= \log\frac{p(x\mid z_t)}{1- p(x\mid z_t)}+ \log\frac{p(x\mid z_{1:t-1})}{1- p(x\mid z_{1:t-1})} + \log\frac{1-p(x)}{p(x)}&\Huge|\normalsize\text{Logarithmusgesetz}\\&= \log\frac{p(x\mid z_t)}{1- p(x\mid z_t)}+ l_{t-1}(x) + \log\frac{1-p(x)}{p(x)}&\Huge|\normalsize\text{Rekursion}\\&= \log\frac{p(x\mid z_t)}{1- p(x\mid z_t)}+ l_{t-1}(x) -\log\frac{p(x)}{1-p(x)}&\Huge|\normalsize\text{Logarithmusgesetz}\\\end{align}$$Der Startbelief sei definiert als
$$l_0(x) = \log\frac{p(x)}{1-p(x)}\;.$$Algorithmus
Es ergibt sich folgender Algorithmus
1import math
2
3def binary_bayes_filter(l_prev, p_x_given_z, p_x):
4"""
5 Implements a Binary Bayes Filter to update belief in log-odds form.
6
7 Args:
8 l_prev: Previous belief state in log-odds (log(p/(1-p)))
9 z_t: Current measurement/observation value
10 p_x_given_z: Probability p(x|z) of state x given measurement z_t (sensor model)
11 p_x: Prior probability p(x) of state x
12
13 Returns:
14 float: Updated belief state in log-odds form
15
16 The filter updates the log-odds belief by incorporating new evidence (measurement)
17 using Bayes' rule. The log-odds form provides numerical stability and avoids
18 probability saturation near 0 or 1.
19 """
20 l_t = l_prev + math.log(p_x_given_z / (1 - p_x_given_z)) - math.log(p_x / (1 - p_x))
21 return l_t
\begin{algorithm}
\caption{Binärer Bayesscher Filter}
\begin{algorithmic}
\Input Letzer Belief in log odds $l_{t-1}$, Wahrnehmung $z_t$
\Procedure{binary-bayes-filter}{$l_{t-1}, z_t$}
\State $l_t \gets l_{t-1} + \log\frac{p(x\mid z_t)}{1- p(x\mid z_t)} - \log\frac{p(x)}{1- p(x)}$
\return $l_t$
\EndProcedure
\end{algorithmic}
\end{algorithm}