7
$\begingroup$

What is the advantage of kalman filters as an online update mechanism instead of the stochastic gradient descent?

$\endgroup$
0

5 Answers 5

6
$\begingroup$

Both of these things can be used in an online manner, but they do this in different ways. So they are not competitors.

The Kalman filter has two purposes. First, for a batch of data, it will yield the log-likelihood of all your observed data, assuming you are estimating a Linear-Gaussian state space model. The log-likelihood is a function of the parameters, assuming your observed data are known. Second, for online data, if you know the parameters, it will recursively compute distributions of your hidden states. When used in an online manner, it recursively calculates statistical distributions for states, assuming parameters are known.

SGD is an algorithm that takes as an input a log-likelihood function. It doesn't care what model you are using, so long as you can calculate a gradient of a loss (the loss is the negative of the log-likelihood). It is a procedure for finding your parameters that maximize (or minimize the negative of) this function. When used in an online fashion, it adjusts parameters as it sees new data. The word "stochastic" refers to the fact that it doesn't use all the data to calculate a likelihood, not to the fact that it recursively computes statistical distributions.

So both can be used in an online manner. But here the KF computes distributions of the hidden states given parameters, and SGD adjusts the parameters to become more suitable.

$\endgroup$
2
  • $\begingroup$ by parameters do you mean the transition matrix? $\endgroup$
    – JTicker
    Commented Jun 20, 2017 at 21:03
  • $\begingroup$ @JTicker the parameters possibly include the state transition matrix, the observation matrix, the state noise covariance matrix, the observation covariance matrix, and sometimes input matrices for both the state and observation equation. Frequently many of these quantities are assumed known, however. $\endgroup$
    – Taylor
    Commented Jun 20, 2017 at 21:18
4
$\begingroup$

The Kalman filter is a model based optimization algorithm that assumes linear dynamics and Gaussian noise. If these assumptions hold, it is guaranteed to converge to the optimum and should be used instead of SGD.

SGD is a model free heuristic which (hopefully) converges to a local optimum. It 'works' for non-linear dynamics, and is often used when the dynamics are not even explicitly represented. Since it is model free and relies on noisy measurements of the gradient, it tends to be slow. Vanilla SGD is not very fast - more recent variants such as Adam and RMSProp tend to work better since they incorporate momentum, which can be thought of as smoothing out the gradient estimate.

$\endgroup$
1
$\begingroup$

With time varying parameters, only the Kalman filter can be used. (Unless you find an innovative way to use SGD).

Let's look at a situation where both algorithms would make sense: linear regression $Y=\beta X+\epsilon$. Call $n$ the length of vector $X$.

SGD (for MLE) assumes a fixed $\beta$ and will just find it. It is an online method but does not handle time dependence at all. First, you must go over the dataset several times, most efficiently in a random order, which breaks time dependence. And you can't expect it will "forget" the influence of the past lines in a way you can control easily.

The Kalman filter assumes time varying $\beta(t)$ that is called a "state" instead of parameter. The "parameters" here are the variance of $\epsilon$ and possibly how $\beta(t)$ is allowed to change with time: typically the variance of a step if it is a Gaussian random walk or Brownian motion. The Kalman filter computes an estimate for $\beta$ and a covariance matrix for this estimation at each time $t$. It goes over the dataset only once and importantly in an ordered time fashion.

When $\beta$ is fixed, the Kalman filter is essentially useless, because it will just find the usual MLE estimation of $\beta$ that could be found easily with matrix inversion. One could argue that the Kalman filter has the advantage to be an online method but since you need to store an $n\times n$ matrix... it's infeasible with big $n$ where online methods are usually needed. And operations on the matrix are costly anyway.

To summarize:

  • Time varying $\beta(t)$: Kalman filter. Infeasible with big $n$.
  • big $n$ : SGD. Infeasible with time varying parameter.

The Kalman filter is also used in advanced learning with NN but I don't much about it. People are researching ways to mix the two algorithms but it does not seem very mature for the moment. (as far as I know). The Kalman filter with big $n$ is being researched, with advanced Bayesian method for weather forecast.

$\endgroup$
1
$\begingroup$

Stochastic gradient descent is an optimization algorithm. It is a variant of gradient descent. It is used to find minima or maxima of functions. The difference between SGD and vanilla gradient descent is that SGD works on samples of the objective function, while vanilla gradient descent works on the exact objective function. In statistical learning, for example, you want to find a parameter vector which maximizes the likelihood function of the data. The parameters are assumed static.

Kalman filter is a type of online Bayesian learning. It can be used to learn states that varies with time in a nonstationary or stationary way. For this, Kalman filter assumes a model which describes the dynamics of the states over time. States can be any variable you want, including time-varying parameters of a statistical model. In a dynamic linear regression model, you must assume a model of how the parameters of linear regression are varying over time. A very simple model is to assume that the parameters vary as a random walk.

At any time, a prior probability distribution synthesizes knowledge about the states (in your case, parameters of a model). With observation of data, you use Bayes rule to update to a posterior distribution. In the Kalman filter, both prior and posterior are Gaussians. Kalman filter has been shown to be optimal in the sense that it minimizes the mean squared error of the real unobserved state and its prediction. A closely related method is recursive least squares, which is a particular case of the Kalman filter.

In summary, Kalman filter is an online algorithm and SGD may be used online. Kalman filter assumes a dynamic model of your parameters, while SGD assumes the parameters do not vary over time. SGD will not be optimal in a dynamic setting, specially because it relies on the stepsize parameter, which must be set by the modeler and must follow some theoretical conditions to converge. The Kalman filter also has an equivalent of the stepsize parameter, which is called "the Kalman gain", which automatically adapts to the data.

$\endgroup$
0
$\begingroup$

There is an alternative at all theses methods which unifies both : It is the relaxc controller concept: https://www.researchgate.net/publication/347510415_Relaxc_vs_Kalman

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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