Artificial Intelligence

An Introduction to
Discrete BAYES Filter & Kalman Filter

6/3/2014 Dr.Eng.Abdellatif BABA - ababa@thk.edu.tr 1

 Remember
An Introduction to
Discrete BAYES Filter & Kalman Filter
Basic concepts in probability
Let X denote a random variable and x denote a specific event that X might take on.

Example of a random variable is that of a coin flip, where X can take on the values:
Head or Tail.

If the space of all values that X can take on is discrete, as is the case if X is the
outcome of a coin flip, we write:
p(X = x)
1
p(X = head) = p(X = tail) =
2

p(X = x) = 1
𝑥

• Probabilities are always non-negative, that is, p(X = x)≥0.

• To simplify p(x) will be used instead of p(X = x).
 Remember
An Introduction to
Discrete BAYES Filter & Kalman Filter
Basic concepts in probability
Most of random variables possess probability density functions (PDFs).
A common density function is that of the one dimensional normal
distribution with mean μ and variance 𝜎 2 .

This distribution is given by the following Gaussian function

 Remember
An Introduction to
Discrete BAYES Filter & Kalman Filter
Basic concepts in probability
The joint distribution of two random independent variables x and y is given by

Often, random variables carry information about other random variables.

Supposing that we would like to know the probability that
value (x) is conditioned on the fact (y)
Such a probability is called conditional probability

If p(y) > 0, then the conditional probability is defined as

If x and y are independent, we have

In other words, if x and y are independent, y tells us nothing about the value of x
 Remember
An Introduction to
Discrete BAYES Filter & Kalman Filter
Basic concepts in probability
Total probability

Bayes rule,

Which relates conditionals of the type p(x | y) to their “inverse” p(y | x).

; p(y) > 0
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Basic concepts in probability

p(x) is called the prior probability distribution,

y is called the data (e.g., a sensor measurement).
• The distribution p(x) summarizes the knowledge we have regarding x prior to
incorporating the data y.

• The probability p(x I y) is called the posterior probability distribution which will be
calculated using the invers conditional probability p(y I x)
• In other words, if we are interested in inferring a quantity x from sensor data y, Bayes
rule specifies the probability of data y assuming that x was the case. (e.g. how state
variables x cause sensor measurements y)

• The factor 𝑝(𝑦)−1 is often considered as a normalizer variable, and generically

denoted: η
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Basic concepts in probability
Measurement data provides information about a momentary state of the environment.
Will be denoted by 𝑧𝑡

Control data carry information about the change of state in the environment.
Will be denoted by 𝑢𝑡

Belief Distributions A belief reflects the agent’s internal knowledge about the state of
the environment. This belief will be represented through conditional probability
distributions.

The probability distribution over the state 𝑥𝑡 at time t, conditioned on all past
measurements 𝑧1:𝑡 and all past controls 𝑢1:𝑡

Predicts the state at time t based on the previous state, before incorporating the
measurement at time t.
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
It is a general and primitive algorithm for calculating beliefs, from measurement
and control data.

Two phases:
1. Prediction : The product of
• The probability of inducing the transition from state (x) at moment (t-1) to the state (x)
at moment (t) by applying the control “the action” (u) at moment (t)
• And the belief of the state (x) at moment (t-1) .
Thus it a recursive process.
2. Correction : The product of belief calculated in the last step and the probability that the
measurement (z) at moment (t) was observed. While, is a normalization constant.
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter

𝑢𝑡

Prediction
𝑏𝑒𝑙(𝑥𝑡 ) 𝑏𝑒𝑙(𝑥 ) 𝑏𝑒𝑙(𝑥𝑡−1 )
𝑡

Correction

𝑧𝑡
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
Example 2 :

One company in Ankara financial market is planning to achieve a commercial act

for the actual day activities. But it wants to study the probability of having high
prices for their financial pointers depending on the following data :
𝑏𝑒𝑙(𝑀0 = ℎ𝑖𝑔ℎ)=0.45
𝑏𝑒𝑙(𝑀0 = 𝑙𝑜𝑤 )=0.55

The model of their ‘’financial sensing’’ (depends on political, social and different
factors) is given :

𝑝 𝑍𝑡 = 𝑔𝑜𝑖𝑛𝑔 𝑢𝑝 𝑀𝑡 = ℎ𝑖𝑔ℎ = 0.7

𝑝 𝑍𝑡 = 𝑔𝑜𝑖𝑛𝑔 𝑑𝑛 𝑀𝑡 = ℎ𝑖𝑔ℎ = 0.3
𝑝 𝑍𝑡 = 𝑔𝑜𝑖𝑛𝑔 𝑢𝑝 𝑀𝑡 = 𝑙𝑜𝑤 = 0.1
𝑝 𝑍𝑡 = 𝑔𝑜𝑖𝑛𝑔 𝑑𝑛 𝑀𝑡 = 𝑙𝑜𝑤 = 0.9
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
Example 2 :

Let us suppose the following historic statistics :

𝑝 𝑀1 = ℎ𝑖𝑔ℎ 𝑈1 = 𝑎𝑐𝑡; 𝑀0 = ℎ𝑖𝑔ℎ = 0.6

𝑝 𝑀1 = 𝑙𝑜𝑤 𝑈1 = 𝑎𝑐𝑡; 𝑀0 = ℎ𝑖𝑔ℎ = 0.4
𝑝 𝑀1 = ℎ𝑖𝑔ℎ 𝑈1 = 𝑎𝑐𝑡; 𝑀0 = 𝑙𝑜𝑤 = 0.5
𝑝 𝑀1 = 𝑙𝑜𝑤 𝑈1 = 𝑎𝑐𝑡; 𝑀0 = 𝑙𝑜𝑤 = 0.5

Finally 𝑍1 = 𝑔𝑜𝑖𝑛𝑔 𝑢𝑝 is given

 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
Example 2 :

𝑏𝑒𝑙 𝑀1 = ℎ𝑖𝑔ℎ =
P 𝑀1 = ℎ𝑖𝑔ℎ|𝑈1 = 𝐴𝑐𝑡; 𝑀0 = ℎ𝑖𝑔ℎ bel(𝑀0 = ℎ𝑖𝑔ℎ)+
P 𝑀1 = ℎ𝑖𝑔ℎ|𝑈1 = 𝐴𝑐𝑡; 𝑀0 = 𝑙𝑜𝑤 bel(𝑀0 = 𝑙𝑜𝑤)

𝑏𝑒𝑙 𝑀1 = ℎ𝑖𝑔ℎ = 0.6*0.45+0.5*0.55=0.545

𝑏𝑒𝑙 𝑀1 = 𝑙𝑜𝑤 =
P 𝑀1 = 𝑙𝑜𝑤|𝑈1 = 𝐴𝑐𝑡; 𝑀0 = ℎ𝑖𝑔ℎ bel(𝑀0 = ℎ𝑖𝑔ℎ)+
P 𝑀1 = 𝑙𝑜𝑤|𝑈1 = 𝐴𝑐𝑡; 𝑀0 = 𝑙𝑜𝑤 bel(𝑀0 = 𝑙𝑜𝑤)

𝑏𝑒𝑙 𝑀1 = 𝑙𝑜𝑤 = 0.4*0.45+0.5*0.55=0.455

 An Introduction to
Discrete BAYES Filter & Kalman Filter
Discrete BAYES Filter
Example 2 :

𝑏𝑒𝑙 𝑀1 = ℎ𝑖𝑔ℎ = ɳ 𝑝 𝑍𝑡 = 𝑔𝑜𝑖𝑛𝑔 𝑢𝑝 𝑀1 = ℎ𝑖𝑔ℎ 𝑏𝑒𝑙 𝑀1 = ℎ𝑖𝑔ℎ

= ɳ 0.7*0.545

𝑏𝑒𝑙 𝑀1 = 𝑙𝑜𝑤 = ɳ 𝑝 𝑍𝑡 = 𝑔𝑜𝑖𝑛𝑔 𝑢𝑝 𝑀1 = 𝑙𝑜𝑤 𝑏𝑒𝑙 𝑀1 = 𝑙𝑜𝑤

= ɳ 0.1*0.455

ɳ = (0.7∗0.545+0.1∗0.455)−1 = 2.34

𝑏𝑒𝑙 𝑀1 = ℎ𝑖𝑔ℎ = 0.89

𝑏𝑒𝑙 𝑀1 = 𝑙𝑜𝑤 = 0.1
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter

As we have already clarified; in general:

𝑢𝑘

Prediction
(𝑥𝑘 ) + (𝑥𝑘 ) − 𝑥𝑘−1

Correction

𝑧𝑘
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
The simplified meaning of KF

Let’s start from the following simplified equation, where the state is a
scalar value; matrices are dropped out

Current estimation Previous estimation

(Our purpose is to estimate Kalman gain Measured value Already known
this value for each moment K) (not perfect values)
(the Key of this
approach) Already known
Unknown; has to be
calculated for each
moment K

K: Discrete time moments, such as k=1,2...etc.

Slide 37
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
Building a Model
The most important step.
We must be sure that, Kalman filtering conditions fit to our problem.

The Kalman filters are based on linear dynamic systems discretized in the time
domain. The two equations of Kalman Filter is as follows:

It means that each state X is a linear combination of its previous value plus a control
signal U and a process noise.

To tell us that any measurement value (which we are not sure about its accuracy) is a
linear combination of the state value X and the measurement noise.

Wk and Vk are considered to be Gaussian and independent

 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
Start the Process
You have to determine the necessary parameters and the initial values.

F 𝐹𝑇

• The matrices F, B and H have to be defined

• Qk, the covariance of the process noise;
• Rk, the covariance of the observation noise;
• Pk, The estimate covariance (a priori / a posteriori)

• We always need to initialize x0, and P0.

 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
Iterate
We can iterate through the estimates. Keep in mind that the previous estimates will be the
input for the current state.

Measurment Update
(Correction)
Time Update
(Prediction)

F 𝐹𝑇

x0, and P0.

 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter

Measurment Update
(Correction)
Time Update
(Prediction)

F 𝐹𝑇

x0, and P0.

Here, is the prior estimate which means the rough estimate before the measurement update
correction (x0 will be used at moment k = 0)
And also is the prior error covariance (P0 will be used at moment k = 0)
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
A simple example
Let's try to estimate a scalar random constant, such as a "voltage reading" from a
source.
So let's assume that it has a constant value of a (volts), but we have some noisy readings
above and below a volts.
And we assume that the variance of the measurement (observation) noise is 0.1 V.

Let's build our model:

• We have a 1 dimensional signal problem, so every entity in our model is a numerical value,
not a matrix.
• We have no such control signal uk
• As the signal is a constant value, F is just 1, because we already know that the next value
will be same as the previous one.
• The value H = 1, because we know that the measurement is composed of the state value
and some noise.
 An Introduction to Example
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter

Let's assume that we have the following measurement values:

TIME 1 2 3 4 5 6 7 8 9 10
(ms)
VALUE 0.39 0.50 0.48 0.29 0.25 0.32 0.34 0.48 0.41 0.45
(V)

We should start from somewhere, such as k=0.

We should find or assume some initial state.
Let's assume estimate of X0 = 0, and P0 = 1.
Then why didn't we choose P0 = 0 for example? If we do that; (there's no noise in the
environment) and this assumption would lead all the consequent to be zero (remaining
as the initial state). So we choose P0 something other that zero.
 An Introduction to Example
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
Let's write the Time Update and Measurement Update equations.

F 𝐹𝑇

We have already supposed

F= H = 1
U= 0
Now, let's calculate the values for each iteration.. Example

Supposed
 An Introduction to Example
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter

+ +
+ + + +
+ + +
+

Solid line represents the real value, the starts are the estimated values

The chart shows that the Kalman Filter algorithm converges to the true voltage value.
The first 10 iterations are illustrated and we clearly see the signs of convergence.
In 50 or more iterations, it'll converge better.

To enable the convergence in fewer steps, you should

• Model the system more elegantly
• Estimate the noise more precisely
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
Kalman filtering:

• The Kalman filter is an algorithm that implement a predictor/corrector type

estimator that is optimal in the sense that it minimizes the estimated error
covariance when some presumed conditions are met.

• In order to use the Kalman filter to estimate the internal state of any given
process. The process model has to be built in accordance with the framework of
the Kalman filter.
 An Introduction to To conclude
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
The Kalman filter model assumes the state at time k is evolved from the state at
(k − 1) according to

Where :
• Fk is the state transition model which is applied to the previous state xk−1;
• Bk is the control-input model which is applied to the control vector uk;
• wk is the process noise which is assumed to be drawn from a
zero mean Gaussian white noise with covariance Qk.

At time k an observation (or measurement) zk of the state xk is made according to

where Hk is the observation model which maps the state space into the observed space
and vk is the observation noise which is assumed to be zero mean Gaussian white
noise with covariance Rk.
 An Introduction to To conclude
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman Filter
The Kalman filter is a recursive estimator. This means; the estimated state from the
previous time step and the current measurement are needed to compute the estimate for
the current state

The Kalman filter is composed of two phases: "Prediction" and "Update".

• The predict phase (a priori prediction ) uses the state estimate from the previous
time step to produce an estimate of the state at the current time step.
This predicted state estimate does not include observation information from the
current time step.

Predicting (a priori) state estimate

Predicting (a priori) estimate covariance (represents a measurment accuracy of

state estimate)
 An Introduction to To conclude
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
• In the update phase, the current a priori prediction is combined with current
observation information to refine the state estimate.

Measurement residual

Residual covariance

Kalman gain

A posteriori state estimate

A posteriori estimate covariance

 An Introduction to To conclude
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter

2
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2:
Consider a simple situation showing a way to measure the level of water in a
tank. This is shown in the figure.
We are trying to estimate the level of water in the tank, which is unknown. The
measurements obtained are from the level of the “float”. This could be an electronic or a
simple mechanical device.
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2:

Let’s model the state process

• The state variable can be reduced to a scalar (i.e., 𝑥 = x where x is the estimate of L).
• We are assuming a constant model, therefore xk+1 = xk, so F = 1, for any t ≥ 0.
• Control variables B and u are not used (i.e., both = 0).
• The value we are measuring is a scaled measurement. For simplicity, we will assume that
the measurement is the exact same scale as our state estimate x (i.e., H = 1).
Let’s model the noise
• The measurement noise variance is R = r = 0.1
• The process is a scalar, therefore P = p
• And as the process noise variance is Q = q = 0.001 (we think we have an accurate
model).
Initialization
We initialize the state with an arbitrary number, with an extremely high variance as it is
completely unknown: x0 = 0 and p0 = 1000.
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2:

K 𝐾𝑡
0 - - - - 0 1000
1 0.000 1000.0001 0.9 0.9999 0.8999 0.1000 +𝑞
2 0.8999 0.1001 0.8 0.5002 0.8499 0.0500
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2:

Note:

After stabilization (about t = 4) the

estimated state is within 0.05 of the
“true” value, even though the
measurements are between 0.8 and 1.2

Conclusion:

If we create a model based on the true

situation, our estimated state will be
close to the true value, even when the
measurements are very noisy.

This is the main purpose of the Kalman filter.

But what happens if the true situation is different?
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2:
We will keep the same model (a static model). This time, the true situation is that the tank
is filling at a constant rate:
Lt = Lt-1 + f

• Let’s assume that the tank is filling at a rate of f = 0.1 per time frame,
• We start with an initialization of X0=L0 = 0.
• We will assume that the measurement and process noise remain the same
(q = 0.001 and r = 0.1).
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2: Let’s see what happens here:

K
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2: Let’s see what happens here:
The estimated state is trailing behind
the true level!
This performance is not desired, as a
filter is supposed to remove noise, not
give an inaccurate reading.
In this case the estimated state has a
much greater error (compared to the
truth) than the noise from the
measurement process.
What is causing this?
There are two contributions:
• The model we have chosen.
• The reliability of our process model
(i.e., our chosen Q value).

The easiest thing to change is our Q value

 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2: Let’s set q = 0.01

So the benefits of increasing the error were beneficial. However the estimated state still
has more error than the actual measured noise.
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2: Let’s increase this value again! Let q = 0.1:

This is getting close to the true value, and has less error than the measurement noise.
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 2: Let’s try q = 1 to see what happens:

Now there is almost no difference to the measured value. There is minor noise removal,
but not much. There’s almost no point in having the filter in this case!
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter

Conclusion

So what has been learnt here?

If you have a badly defined model, you will not get a good
estimate.
But you can relax your model by increasing your estimated
measurement error Q.
This will let the Kalman filter rely more on the measurement
values, but still allow some noise removal.
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Conclusion
The Kalman filter model must be meaningful. It should be defined as follows:

1. Understand the situation: Look at the problem. Break it down to the mathematical basics. If you
don’t do this, you may end up doing unneeded work.
2. Model the state process: Start with a basic model. It may not work effectively at first, but this can
be refined later.
3. Model the measurement process: Analyze how you are going to measure the process. The
measurement space may not be in the same space as the state (e.g., using an electrical diode to
measure weight, an electrical reading does not easily translate to a weight).
4. Model the noise: This needs to be done for both the state and measurement process. The base
Kalman filter assumes Gaussian (white) noise, so make the variance and covariance (error)
meaningful (i.e., make sure that the error you model is suitable for the situation).
5. Test the filter: See if the filter is behaving as it should.
6. Refine filter: Try to change the noise parameters (filter), as this is the easiest to change. If
necessary go back further, you may need to rethink the situation.
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter

Example 3: Consider a truck on frictionless, straight rails. Initially, the truck is

stationary at position 0, but it is moving in all directions by random
uncontrolled forces. We measure the position of the truck every Δt seconds, but
these measurements are imprecise; we want to maintain a model of truck
position velocity. Thus let’s derive the model from which we create our Kalman
filter.

The position and velocity of the truck are described

by the linear state space
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 3:
We assume that between the (k − 1) and k time step uncontrolled forces cause a constant
acceleration of ak that is normally distributed, with mean 0 and standard deviation σa.
From Newton's laws of motion we conclude that
∆𝑡 2
𝑥𝑘 = 𝑥𝑘−1 + 𝑥𝑘−1 × ∆𝑡 + 𝑎 Where
2 𝑘
𝑥𝑘 = 𝑥𝑘−1 + ∆𝑡𝑎𝑘

Where
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Example 3:
At each time step, a noisy measurement of the true position of the truck is made.
Let us suppose the measurement noise vk is also normally distributed, with mean 0 and
standard deviation σz.

We know the initial starting state of the truck with perfect

precision, so we initialize

If we prefer to tell the filter that we know the exact position

and velocity, we give it a zero covariance matrix

1 1
Otherwise we may suupose; 1 1
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter

Filter System Probability

Distribution
Kalman Filter (KF) Linear systems Normal distribution
Extended Kalman Filter (EKF) Non-linear systems Normal distribution
Particle Filters Non-linear systems State and noise
distributions can
take any probability
distribution
 An Introduction to
Discrete BAYES Filter & Kalman Filter
Introduction to Kalman filter
Reference:

[1] Greg Welch, Gary Bishop, "An Introduction to the Kalman Filter", University of
North Carolina at Chapel Hill Department of Computer Science, 2001

[2] M.S.Grewal, A.P. Andrews, "Kalman Filtering - Theory and Practice Using
MATLAB", Wiley, 2001

[3] Sebastien Thrun, W. Burgard and D. Fox, "Probabilistic robotics"

[4] http://bilgin.esme.org/BitsAndBytes/KalmanFilterforDummies

[5] www.cs.unc.edu/˜welch/kalman/kftool/index.html