-1
$\begingroup$

In the wikipedia Kalman filter link, the state variable $x_k$ takes a continuous value say a floating point number, but what if the values are integer say symbols from an alphabet set, then how does one apply the Kalman filter? I have the following confusions and doubt and shall be obliged for an answer with some examples, if any.

DOubt 1: Kalman filter is called continuous filter because the state values and covariance etc all take real-valued numbers. But, these are discrete-in time $k$ varies from $1,2,\ldots$ and continuously. Is my understanding correct?

Doubt 2: I count not find any information or any working example on the case when the state variables take discrete values. What if they are symbols from DNA strings? Could somebody please throw some light into this case?

$\endgroup$
1
$\begingroup$

#1. Yes, although you can discretize time and make some limit arguments to design a continuous time Kalman filter. For a more general non-linear filter that allows time to be continuous, you can look at the section about the Kalman-Bucy filter on the Kalman Filter Wikipedia page.

#2. Recall that a Kalman filter produces estimates of the hidden states which are optimal in a minimum-mean squared error sense. Since the posterior distribution is symmetric (linear Gaussian measurement model) this is equivalent to finding the maximum a posteriori (MAP) estimate of the hidden states. In other words, because the posterior distribution is symmetric, the mean and mode are identical.

If your random variables are integer valued (+/- 1 in your case), a Kalman filter measurement/transition model is not applicable. But you can still find an optimal MAP estimate. With the knowledge of your measurement model that generates $y_k$'s from $x_k$'s and a state transition model a.k.a. transition probability matrix that describes the state transitions $x_k \rightarrow x_{k+1}$, you can compute the posterior probability mass function $p(x_{1:N}|y_{1:N})$. The MAP estimate must maximize this as a function of $x_{1:N}$, where $N$ is the number of observations.

An impractical brute force approach would be to work through all elements of $\{-1,1\}^N$. A more practical approach involves writing a dynamic programming algorithm that finds the optimal sequence of $x_k$'s, the idea being very similar to traversing a trellis in Viterbi decoding. (Shameless plug: See section 3.1 here.)

$\endgroup$
  • $\begingroup$ Thank you for your answer. I think MAP is different from Kalman filter, is it different from Kalman filter? Also, I did a quick googling and found that Viterbi is a search algorithm but Baum-Welch is another name for Expectation Maximization. Can you please correct and/ or confirm these. $\endgroup$ – Ria George Aug 5 '17 at 4:15
  • $\begingroup$ @RiaGeorge please see my edited answer and let me know if it answers your questions. $\endgroup$ – Atul Ingle Aug 5 '17 at 19:30
  • $\begingroup$ Thank you so much......and for the paper. What an interesting research work. Aside from Kalman filter, I have a general question which is: can the task or problem of parameter estimation (without using machine learning methods such as Neural network or support vector machines etc) be called as learning in general? $\endgroup$ – Ria George Aug 6 '17 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.