How to recursively filter sequential predictions of binary classifier?

Question

Problem

My goal is to estimate binary state using entire observation history. Observations are coming sequentially with fixed interval (~1 sec). I have xgboost model which predicts the state given a single observation; I treat this prediction directly as conditional probability $P(x_t = 1 | z_t)$.

Observations are noisy, so each prediction alone does not tell much about real situation. Important point is that state can change with time.

What is the best theoretical way to estimate $x_t$ knowing $P(x_t | z_t)$ and $z_{1:t}$? I tried discrete bayes filter, but it has some not obvious parameters: aprior distribution of states and probability of transition between states, is there a method not requiring knowledge of this?

Current work

I used discrete bayes filter algorithm from "Probabilistic robotics" book

Assume following notation

• $x_t \in \{0, 1\}$ - state at time $t$
• $z_t$ - observation at time $t$
• $P_{k,t} = P(x_t = k | z_{1:t})$ - result of filter, $P_{k,0} = P(x_0 = k)$
• $\hat{P}_{k,t} = P(x_t = k | z_{1:t-1})$
• $P(x_t = 1 | z_t)$ - prediction of xgboost model $$ \hat{P}_{0,t} = P(x_{t} = 0 | x_{t-1} = 0) P_{0,t-1} + P(x_{t} = 0 | x_{t-1} = 1) P_{1,t-1} \tag{1} $$ $$ \hat{P}_{1,t} = P(x_{t} = 1 | x_{t-1} = 0) P_{0,t-1} + P(x_{t} = 1 | x_{t-1} = 1) P_{1,t-1} \tag{2} $$ $$ P_{0,t} = \alpha P(z_t | x_t = 0) \hat{P}_{0,t} \tag{3} $$ $$ P_{1,t} = \alpha P(z_t | x_t = 1) \hat{P}_{1,t} \tag{4} $$ $$ \alpha \text{ is a normalization constant such that } P_{0,t} + P_{1,t} = 1 $$

To use this algorithm with $P(x_t = 1 | z_t)$ I need to modify it using bayes rule $$ P(z_t | x_t = 1) = \frac{P(x_t = 1 | z_t)P(z_t)}{P(x_t = 1)} \tag{5} $$

Now $$ P_{0,t} = \alpha \frac{P(x_t = 0 | z_t)P(z_t)}{P(x_t = 0)} \hat{P}_{0,t} \tag{6} $$ $$ P_{1,t} = \alpha \frac{P(x_t = 1 | z_t)P(z_t)}{P(x_t = 1)} \hat{P}_{1,t} \tag{7} $$

To cancel $P(z_t)$ $$ \frac{P_{1,t}}{1 - P_{1,t}} = \frac{P(x_t = 1 | z_t) P(x_t = 0) \hat{P}_{1,t}}{P(x_t = 0 | z_t) P(x_t = 1) \hat{P}_{0,t}} = K \tag{8} $$

$$ P_{1,t} = \frac{K}{1 + K} \tag{9} $$

Are my derivations correct? Seems strange that the bigger $P(x_t = 0)$ is, the bigger $P_{1,t}$ will be.

This algorithm is not very convenient as soon as it requires many parameters ($P(x_t)$, $P(x_t | x_{t-1})$) and also does not give any confidence estimate, are there better examples of such algorithms?

Answer 1

So it might be helpful to explain in words what is happening in equations $(1)$ and $(2)$ above. These two equations are essentially applying the Law of Total Probability to split up your probabilities into the two terms in each sum, and then applying the (probability) Chain Rule to expand each term into a product of conditional probabilities - essentially a chain of repeated applications of Bayes' Rule.

The recursive nature of $(1)$ and $(2)$ implies that the probability of the state $x_{T}$ at any time $T$ depends on all previous states $x_{t}$ for $t < T$ and observations $z_{t}$ for $t \leq T$. Your algebra substituting $(6)$ and $(7)$ into $(8)$ seems fine to me. $(8)$ clearly shows $P_{0, t}$ and $P_{1, t}$ are inversely proportional to each other for fixed $K$. In fact, if you find the equation for $P_{0, t}$ which corresponds to equation $(9)$ for $P_{1, t}$ by using $P_{0, t} + P_{1, t} = 1$, we have $$ P_{0, t} = \frac{1}{1 + K} \tag{10} $$

To address your confusion about $P(x_{t} = 0)$ seemingly counterintuitive effect on $P_{1, t}$, again it's helpful to think about what each term is quantifying. $P(x_{t} = 0)$ is the unconditional probability of observing the state $x_{t} = 0$ at time $t$, without any influence from observations $z_{1:t}$. If this probability is high, you wouldn't be surprised to find that in fact $x_{t} = 0$. What really matters is how $P(x_{t} = 0)$ relates to $P(x_{t} = 0 | z_{t})$. The conditional probabilty $P(x_{t} = 0 | z_{t})$ quantifies how informative observation $z_{t}$ is about the state $x_{t}$. If $P(x_{t} = 0 | z_{t}) \ll P(x_{t} = 0)$, then we have learned a lot of surprising information from $z_{t}$, so that we drastically change our opinion of the state $x_{t}$. If we instead have $P(x_{t} = 0) \approx P(x_{t}=0|z_{t})$, then $z_{t}$ doesn't really tell us much to change our minds about the state $x_{t}$. This idea of surprise/informativity can be seen if you look at $(5)$ and $(4)$. Increasing the magnitude of $P(x_{t} = 0)$ causes a corresponding decrease in $P(x_{t} = 1)$. Then the rarer state $x_{t} = 1$ is more informative than the mundane state $x_{t} = 0$. The denominator of $(5)$ decreases in this case, and the value of $P(z_{t} | x_{t} = 1)$ correspondingly increases - the rarity of $x_{t} = 1$ means that it carries more information than the more mundane $x_{t} = 0$ about the observation $z_{t}$, and we have a corresponding increase in $P_{1, t}$ as seen in $(4)$. To reiterate, $P(x_{t}=0) \approx 1$ means that any variation in $z_{t}$ is not tightly coupled to the state $x_{t} = 0$ - $x_{t} = 0$ likely occurs with equal frequency for all possible values of $z_{t}$. The fact that this forces $P(x_{t} = 1) \approx 0$ means that because the state $x_{t} = 1$ occurs so infrequently, it is by that very property highly likely to be unevenly co-occuring with different values of $z_{t}$, and thus is in a sense highly informative about $z_{t}$. If $z_{t}$ has $100$ possible values, and $x_{t} = 0$ occurs with $99.99\%$ probability, then any value of $z_{t}$ is likely to occur with $x_{t} = 0$. However, this means that on the rare occasion $x_{t} = 1$ does occur, it most likely only does so with some smaller subset of values of $z_{t}$.

As I mentioned above, your complaint about requiring many parameters is valid, and stems from the recursive nature of the system. There are alternative models that weaken this dependence on all previous times $t<T$ by imposing some kind of Markov property. Another alternative is to use something like a Kalman Filter, which basically lets you only keep track of a set of variables of fixed size at each time step, as opposed to a set of variables increasing in size with $t$. As for confidence bounds on your estimates, you're actually getting the whole probability distribution, so you actually already have those. The dependence on your prior diminishes with time as you gather more observations, so that shouldn't really be an issue.