21 feb 2018

Overview

Source:

What does the Kalman filter do?

Kalman filtering, also known as linear quadratic estimation (LQE), is an algorithm that uses a series of measurements observed over time, containing statistical noise and other inaccuracies, and produces estimates of unknown variables that tend to be more accurate than those based on a single measurement alone, by using Bayesian inference and estimating a joint probability distribution over the variables for each timeframe. The filter is named after Rudolf E. Kálmán, one of the primary developers of its theory.

Source: WIKIPEDIA

The Kalman filter assumes that variables are random and Gaussian distributed. Each variable has a mean value \(\mu\), which is the center of the random distribution, and a variance \(\sigma^2\), which is the uncertainty.

Source: Bzarg

Also Kalman filtering assume the error in the measurement to be known and to be constant.

See it in action

Basic concept

Kalman process chart

3 step process

  1. Calculate Kalman gain
  2. Update estimate
  3. Update error in estimate

1. Kalman gain

\(\text{kalman gain} = KG = \frac{E_{EST}}{E_{EST} + E_{MEA}}\)

kalman.gain = current.estimate.error / ( current.estimate.error + current.measurement.error )

2. Update estimate

  • \(\text{measurement} = MEA\)
  • \(\text{current estimate} = EST_t\)
  • \(\text{previous estimate} = EST_{t-1}\)

\[{EST}_t = {EST}_{t-1} + KG [MEA - {EST}_{t-1} ]\]

current.estimate = previous.estimate + kalman.gain * (measurement - previous.estimate)

3. Update error in estimate

\[E_{EST_t} = \frac{E_{MEA}E_{EST_{t-1}}}{E_{MEA}+E_{EST_{t-1}}} \Rightarrow [1-KG] E_{EST_{t-1}}\]

current.estimate.error = ( current.measurement.error * previous.error ) / 
                         ( current.measurement.error + previous.error )
current.estimate.error = (1 - kalman.gain) * previous.error

KalmanFilter <- function(current.estimate, current.estimate.error, current.measurement, current.measurement.error) {
  # Apply Kalman filter. Calculates new estimate
  # and error of estimation
  #
  # Args:
  #   current.estimate          : Current estimation of the variable of interest
  #   current.estimate.error    : Current error in the estimation
  #   current.measurement       : Measured value
  #   current.measurement.error : Constant error of measurement instrument
  #
  # Returns:
  #   updated.estimate       : Updated estimate of variable of interest
  #   updated.estimate.error : Updated error of the estimate
  
  # Calculate Kalman gain
  kalman.gain = current.estimate.error / ( current.estimate.error + current.measurement.error )
  
  # Update estimate
  updated.estimate = current.estimate + kalman.gain * (current.measurement - current.estimate)
  
  # Update error in estimate
  updated.estimate.error = (1 - kalman.gain) * current.estimate.error
  
  # Create return list
  return( list(updated.estimate       = updated.estimate,
               updated.estimate.error = updated.estimate.error)
        )
}

Example

Temperature

Use Kalman filter to estimate the true temperatur of 72 degrees F with error of 4.

  • Measurement
  • Original estimate
  • Original error in estimate
current.measurement       <- 75
current.measurement.error <- 4
current.estimate          <- 68
current.estimate.error    <- 2

Apply Kalman filter once

KalmanFilter(current.estimate, current.estimate.error, current.measurement, current.measurement.error) 
## $updated.estimate
## [1] 70.33333
## 
## $updated.estimate.error
## [1] 1.333333

Apply Kalman filter

current.estimate          <- 15
current.estimate.error    <- 1
current.measurement.error <- 2

mu.temp    <- rep(c(15,20,25), each=20)
sigma.temp <- rep(c(2,1,1),    each=20)

temperatures <- rnorm(length(mu.temp),mu.temp, sigma.temp)
n            <- length(temperatures)

# Store results
results <- data.frame(mu.temp, sigma.temp, temperatures, estimate = NA, error = NA)

for (i in 1:n) {
  
  # Set current measurement
  current.measurement <- temperatures[i]
  
  # Store result
  results[i,c('estimate', 'error')] <- c(current.estimate, current.estimate.error)
  
  kalman.filter.results <- KalmanFilter(current.estimate, current.estimate.error, current.measurement, current.measurement.error)

  current.estimate          <- kalman.filter.results$updated.estimate
  current.estimate.error    <- kalman.filter.results$updated.estimate.error

}

Results

Comparisons

Compare Kalman gain to:

Method Equation
Kalman gain \(EST_t = EST_{t-1} + KG [MEA - EST_{t-1} ]\)
Gradient descent \(b_t = b_{t-1} + LR (Y - \hat{Y})\)
Elo rating \(\text{Rating}_t = \text{Rating}_{t-1} + K (S - \hat{S} )\)

Youtube resource

END