56
$\begingroup$

What is the relationship, if any, between Kalman filtering and (repeated, if necessary) least squares polynomial regression?

$\endgroup$
  • $\begingroup$ Right off the bat, with kalman filtering we dont have access to future values, (hence the predict part), whereas in poly fitting we have the entire data set in front of us to which to best fit the data. Great question nonetheless! +1. $\endgroup$ – Spacey May 13 '12 at 19:45
  • $\begingroup$ @Mohammad : Where do you see a requirement to feed the two methods different (subsets of) data points? $\endgroup$ – hotpaw2 May 14 '12 at 0:01
  • $\begingroup$ @Mohammad polynomial regression CAN extrapolate and hence can be used for future prediction. $\endgroup$ – Dipan Mehta May 14 '12 at 4:32
  • $\begingroup$ @DipanMehta /@hotpaw2 Hmm, I guess I was not aware of that. AFAIK for poly we need to have access to the entire data set prior, in order to compute a best fit. (offline processing). Although now that I think of it, I suppose an on-line version can also work ... we would solve for the best fit all over again every time a new sample comes in. But where would the 'prediction' be? $\endgroup$ – Spacey May 14 '12 at 4:44
  • $\begingroup$ @Mohammad not getting deep in math - but basically this is true for any regression. Support you have training vector $X_t$ and you applied $Y_t$ and discovered the model parameters $\alpha[i]$ now you have another $X_k$ which is at extrapolated length you can get best estimation of $Y_K$ applying the same model as above which is nothing but prediction. When you actually measure $Y_K'$ based on error, you have a chance to update/improve the model. $\endgroup$ – Dipan Mehta May 14 '12 at 4:58
49
$\begingroup$

1. There is a Difference in terms of optimality criteria

Kalman filter is a Linear estimator. It is a linear optimal estimator - i.e. infers model parameters of interest from indirect, inaccurate and uncertain observations.

But optimal in what sense? If all noise is Gaussian, the Kalman filter minimizes the mean square error of the estimated parameters. This means, that when underlying noise is NOT Gaussian the promise no longer holds. In case of nonlinear dynamics, it is well-known that the problem of state estimation becomes difficult. In this context, no filtering scheme clearly outperforms all other strategies. In such case, Non-linear estimators may be better if they can better model the system with additional information. [See Ref 1-2]

Polynomial regression is a form of linear regression in which the relationship between the independent variable x and the dependent variable y is modeled as an nth order polynomial.

$$ Y = a_0 + a_1x + a_2x^2 + \epsilon $$

Note that, while polynomial regression fits a nonlinear model to the data, these models are all linear from the point of view of estimation, since the regression function is linear in terms of the unknown parameters $a_0, a_1, a_2$. If we treat $x, x^2$ as different variables, polynomial regression can also be treated as multiple linear regression.

Polynomial regression models are usually fit using the method of least squares. In the least squares method also, we minimize the mean squared error. The least-squares method minimizes the variance of the unbiased estimators of the coefficients, under the conditions of the Gauss–Markov theorem. This theorem, states that ordinary least squares (OLS) or linear least squares is the Best Linear Unbaised Estimator (BLUE) under following conditions:

a. when errors have expectation zero i.e. $E(e_i) = 0 $
b. have equal variances i.e. $ Variance(e_i) = \sigma^2 < \infty $
c. and errors are uncorrelated i.e. $ cov(e_i,e_j) = 0 $

NOTE: that here, errors don't have to be Gaussian nor need to be IID. It only needs to be uncorrelated.

2. Kalman Filter is an evolution of estimators from least square

In 1970, H. W. Sorenson published an IEEE Spectrum article titled "Least-squares estimation: from Gauss to Kalman." [See Ref 3.] This is a seminal paper that provides great insight about how Gauss' original idea of least squares to today's modern estimators like Kalman.

Gauss' work not only introduced the least square framework but it was actually one of the earliest work that used a probabilistic view. While least squares evolved in the form of various regression methods, there was another critical work that brought filter theory to be used as an estimator.

The theory of filtering to be used for stationary time series estimation was constructed by Norbert Wiener during 1940s (during WW-II) and published in 1949 which is now known as Wiener filter. The work was done much earlier, but was classified until well after World War II). The discrete-time equivalent of Wiener's work was derived independently by Kolmogorov and published in 1941. Hence the theory is often called the Wiener-Kolmogorov filtering theory.

Traditionally filters are designed for the desired frequency response. However, in case of Wiener filter, it reduces the amount of noise present in a signal by comparison with an estimation of the desired noiseless signal. Weiner filter is actually an estimator. In an important paper, however, Levinson (1947) [See Ref 6] showed that in discrete time, the entire theory could be reduced to least squares and so was mathematically very simple. See Ref 4

Thus, we can see that Weiner's work gave a new approach for estimation problem; an evolution from using least squares to another well-established filter theory. However, the critical limitation is that Wiener filter assumes the inputs are stationary. We can say that Kalman filter is a next step in the evolution which drops the stationary criteria. In Kalman filter, state space model can dynamically be adapted to deal with non-stationary nature of signal or system.

The Kalman filters are based on linear dynamic systems in discrete time domain. Hence it is capable of dealing with potentially time varying signal as opposed to Wiener. As the Sorenson's paper draws parallel between Gauss' least squares and Kalman filter as

...therefore, one sees that the basic assumption of Gauss and Kalman are identical except that later allows the state to change from one time to next. The difference introduces a non-trivial modification to Gauss' problem but one that can be treated within the least squares framework.

3. They are same as far as causality direction of prediction is concerned; besides implementation efficiency

Sometimes it is perceived that Kalman filter is used for prediction of future events based on past data where as regression or least squares does smoothing within end to end points. This is not really true. Readers should note that both the estimators (and almost all estimators you can think of) can do either job. You can apply Kalman filter to apply Kalman smoothing.

Similarly, regression based models can also be used for prediction. Given the training vector, $X_t$ and you applied $Y_t$ and discovered the model parameters $α_0 ... a_K$ now for another sample $X_k$ we can extrapolate $Y_K$ based on the model.

Hence, both methods can be used in the form of smoothing or fitting (non-causal) as well as for future predictions (causal case). However, the critical difference is the implementation which is significant. In case of polynomial regression - with entire process needs to get repeated and hence, while it may be possible to implement causal estimation but it might be computationally expensive. [While, I am sure there must be some research by now to make things iterative].

On the other hand, Kalman filter is inherently recursive. Hence, using it for prediction for future only using on past data will be very efficient.

Here is another good presentation that compares several methods: Ref 5

References

  1. Best Introduction to Kalman Filter - Dan Simon Kalman Filtering Embedded Systems Programming JUNE 2001 page 72

  2. Presentation: Lindsay Kleeman Understanding and Applying Kalman Filtering

  3. H. W. Sorenson Least-squares estimation: from Gauss to Kalman IEEE Spectrum, July 1970. pp 63-68.

  4. Lecture Note MIT Course ware

  5. Presentation Simo Särkkä From Linear Regression to Kalman Filter and Beyond Helsinki University of Technology

  6. Levinson, N. (1947). "The Wiener RMS error criterion in filter design and prediction." J. Math. Phys., v. 25, pp. 261–278.

$\endgroup$
  • $\begingroup$ Very nice breakdown! $\endgroup$ – Spacey May 26 '12 at 22:27
  • 1
    $\begingroup$ 'Understanding and Applying Kalman Filtering' link is broken. I think this link is working : cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated3/… $\endgroup$ – Vinod Apr 19 '14 at 10:03
  • $\begingroup$ What a great answer. This is the reason this site is so great! $\endgroup$ – Royi Apr 19 '14 at 11:03
  • $\begingroup$ Fantastic answer, sometimes it's hard to find answers to simple yet fundamental questions such as this one $\endgroup$ – ZiglioUK Feb 22 '15 at 0:53
6
$\begingroup$

The difference is quite huge, since they are two completely different models which can be used to tackle the same problem. Let's do a quick recap.

Polynomial regression is a way of function approximation. We have a data set of the form $\lbrace x_i, z_i \rbrace$ and wish to determine the functional relationship, which is often expressed by estimating the probability density $p(z|x)$. Under the assumption that this $p$ is a Gaussian, we get the least squares solution as a maximum likelihood estimator.

Kalman filtering is a special way of inference in a linear dynamical system. LDSs are a special case of state space models, in which we assume that the data we observe is generated by a the application of a linear transform to the subsequent steps of a Markov chain over Gaussian random variables. Thus what we actually do is to model $p(x_{1:T})$, which is the probability of a time series. The process of Kalman Filtering is then to predict the next value of a time series, e.g. maximize $p(x_{t+1}|x_{1:t})$. But the same model can be used to do inference on smoothing, interpolation and many more things.

Thus: polynomial regression does function approximation, Kalman filtering does time series prediction. Two totally different things, but time series prediction is a special case of function approximation. Also, both models base quite different assumptions on the data they observe.

$\endgroup$
  • $\begingroup$ What are the different assumptions about the observed data? $\endgroup$ – hotpaw2 May 17 '12 at 11:57
  • 1
    $\begingroup$ @hotpaw2, PR: data is generated by a polynomial with additional Gaussian noise. LDS: data is generated by an unobserved Markov chain of Gaussian distributed variables which relates linearly to the observed data. $\endgroup$ – bayer May 17 '12 at 13:47
5
$\begingroup$

Not an expert on kalman filters, however I believe traditional Kalman filtering presumes a linear relationship between the observable data, and data you wish to infer, in contrast to more intricate ones like the Extended Kalman filters that can assume non-linear relationships.

With that in mind, I believe that for a traditional Kalman filter, on-line linear regression, would be similar to Kalman in performance. However, a polynomial regression can also be used that would assume a non-linear relationship that a traditional Kalman might not be able to capture.

$\endgroup$
4
$\begingroup$

Kalman filtering gives multiple predictions for the next state, where an extrapolation of a regression would not.

The Kalman filters are also focused on including noise factors (based on Gaussian distributions).

$\endgroup$
  • $\begingroup$ Multiple predictions? Or a single multi-dimensional prediction vector? (Which a multi-dimensional linear or polynomial regression could provide?) $\endgroup$ – hotpaw2 May 14 '12 at 16:16
  • $\begingroup$ Multiple predictions for each dimension/variable (along with the certainty of that prediction being the right one). This is related to the way of incorporating noise into the prediction. $\endgroup$ – Geerten May 15 '12 at 6:51
  • $\begingroup$ Not entirely true. PR gives you a distribution as well, it's just not commonly used. Also, if you use polynomial regression with least squares for time series prediction, it's the exact same noise model as with a Kalman filter. $\endgroup$ – bayer May 17 '12 at 13:52
2
$\begingroup$

A lot has been said already, allow me to add some comments:

Kalman filters are an application of Bayesian probability theory, which means that "a priori information" or "prior uncertainty" can (and must) be specified. As I understand, this is not the case with traditional least-squares fitting. While observations (data) can be weighted with probabilities in LSQ fitting, prior knowledge of a solution cannot be readily taken into account.

In summary, solutions found by a KF will depend on

a) a model to provide 'predictions'

b) measurements which are 'observations'

c) uncertainty on predictions and observations

d) a priori knowledge of the solution.

"prior knowledge" is specified as a variance on the initial guess, but is not relevant or utilized to the same extent in every application.

As mentioned before, a common use of the KF is to reduce noise in real-time observations. Comparing observations with model predictions can help to estimate the 'true measurement' devoid of noise. This common application is why the KF is called a filter.

The initial guess in this example would be the assumed solution at time zero from which the KF starts, with associated "prior uncertainty". Often you will have some unknown parameters in the predictive model, but which can be constrained by the measurements i.e. are "observable". The KF will improve its estimates of both those parameters and the "true measurements" as it moves through the time series of data. In that case the initial state is often specified to simply result in consistent filtering performance: defined as the actual estimation errors being within the uncertainty bounds that the KF provides with its solution. In this example, the prior uncertainty on the initial state may be specified to be large, giving the KF opportunity to correct any errors it contains. Small values may also be specified, to nudge the filter towards future estimates that make sense (are consistent with observations).

This area of KF design may involve trial and error, or engineering judgement, to come up with values of the initial state and its uncertainty that result in good performance. For this reason, this and other aspects of KF filter design which involve specifying uncertainties to result in good performance (be it numerical, estimation, prediction...) is often referred to as "filter tuning".

But in other applications, a more rigorous and useful approach to prior uncertainties can be adopted. The previous example was about real-time estimation (to filter noise out of uncertain measurements). The initial state and its variance (prior uncertainty) are almost a necessary evil to initialize the filter at an early time, after which the initial state becomes increasingly unimportant as future observations are used to improve estimates. Consider now a Kalman filter applied to measurements and model predictions at a specific time t_s. We have uncertain observations, an uncertain model, but we also have some prior knowledge about the solution we are looking for. Let's say we know its Gaussian PDF: mean and variance. In this case the solution could depend very strongly on the prior uncertainty, meaning item d) above, where the hope is that the added information improves the KF solution (smaller error and less uncertainty).

This feature, which is fundamental to Bayesian theory, allows the KF to solve stochastic problems while taking into account every kind of uncertainty/information that is typically available. Because the KF has been developed and applied for decades, its basic features are not always described in detail. In my experience, many papers and books focus on optimality and linearization (extended KF, unscented KF, and so on). But I've found great descriptions of the links between Bayesian theory and KF, by reading introductory papers and texts on "particle filters". Those are another and more recent implementation of Bayesian estimation, look them up if you're interested!

$\endgroup$
  • 1
    $\begingroup$ Could one get a similar Bayesian update effect (provided by using a Kalman filter) by adding some pre-pended a-priori/predicted/guessed (mean and variance) data points before the real data and then using iterative least-squares polynomial regression to update the prediction (and variance or regression coefficient) as the real data comes in? $\endgroup$ – hotpaw2 Jul 20 '17 at 19:37
  • $\begingroup$ While it is possible to nudge a function fit towards "a priori" data (which would be no different from any other data, apart from the name we give them), the proper way of combining uncertainties in a conditional setting (a priori + observations = a posteriori) is defined in Bayesian theory. I'm not saying it's impossible to reproduce a Bayesian result by other means, but data fitting and the Bayesian theorem are different things, and only the latter was conceived to produce correct statistics. I expect there is a difference between adding observations, and computing conditional probabilities. $\endgroup$ – Bart Van Hove Jul 20 '17 at 23:49
  • $\begingroup$ This solution does concentrate on usage so I upped it. $\endgroup$ – rrogers Jul 25 '17 at 19:40
  • $\begingroup$ You may find this StackExchange thread interesting as well, the question is very similar to yours but compares polynomial fitting with general Bayesian inference, of which the Kalman filter is an example. stats.stackexchange.com/questions/252577/… $\endgroup$ – Bart Van Hove Jul 27 '17 at 8:30
  • $\begingroup$ To give some more context: Kalman filters are a particular solution method for general Bayesian problems, and especially appropriate for problems involving data time series (e.g. online estimation). The topic I linked above considers general Bayesian treatment of a regression problem, where all data are used at once, which is more similar to polynomial fitting than online Kalman filtering as was mentioned in several answers here. $\endgroup$ – Bart Van Hove Jul 27 '17 at 8:38

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.