Introduction to Probability

Jacky Baltes

Educational Robotics Center

National Taiwan Normal University

jacky.baltes@ntnu.edu.tw

http://www.google.com/sites/jackybaltes

Probabilistic Robotics

• Probabilities
• Review
• Conditional probability
• Bayes Reasoning
• Bayes Rule
• Bayes Filter

• SLAM
• Kalman Filter
• Particle Filter
• Visual SLAM
• Features
• Edges
• SIFT, SURF
• Bundle adjustment

Probabilistic Robotics

• First attempts at localization and mapping
• Dead reckoning
• Feedback from the environment
• Sensor fusion => Kalman filters
• Key idea
• Explicitly model uncertainty using calculus of probabilities
• Perception = state estimate
• Action = utility optimization

Axioms of Probability Theory

• Pr(A) denotes the probability that proposition A is true

​

• for all events e

​

• ​

​

• If A and B are mutually exclusive, then

​

(Kolmogorov 1933)

​

​

Axiom 3

B

A

B

Lemmas

And:

​

​

​

​

If A and B are statistically independent (PB|A)=P(B)

​

​

Discrete Random Variables

X denotes a random variable.

X can take on a countable number of values in {x1, x2, …, xn}.

P(X=xi), or P(xi), is the probability that the random variable X takes on value xi.

P( ) is called probability mass function.�

E.g.

​

Discrete Random Variables

P(sum=xi): probability of sum s when rolling a pair of fair dices�

​

Continuous Random Variables

• X takes on values in the continuum.
• p(X=x), or p(x), is a probability density function.�
• E.g.

x

p(x)

Joint And Conditional Probabilities

P(X=x and Y=y) = P(x,y)

​

If X and Y are independent then � P(x,y) = P(x) P(y)

P(x | y) is the probability of x given y� P(x | y) = P(x,y) / P(y)� P(x,y) = P(x | y) P(y)

If X and Y are independent then� P(x | y) = P(x)

Law of Total Probability, Marginals

Discrete case

Continuous case

Question

• There are three doors. One door has a bag of gold. The other two doors have tigers behind them. The king asks you to select a door. If you open the door with the bag of gold behind it, you can leave with the gold. Otherwise you are lunch for the tigers. You select the left door. The king opens the middle door and shows you a caged tiger.
• The king asks you again, which door you want to choose. Should you change and pick the left door?

Monty's Dilemma

• Assume gold is behind the first door
• Strategy 1: Player picks one door and stays with it
• Door A 1/3
• King opens Door B
• Player keeps Door A -> Gold: 1/3 * ½
• King opens Door C
• Player keeps Door A -> Gold: 1/3 * ½

Monty's Dilemma

• Door B 1/3
• King opens Door C
• Player keeps Door B -> Tiger: 1/3
• Door C 1/3
• King opens Door B
• Player keeps Door A -> Tiger: 1/3

Monty's Dilemma

• Assume gold is behind the first door
• Strategy 2: Player switches doors
• Door A 1/3
• King opens Door B
• Player switches Door C -> Tiger: 1/3 * ½
• King opens Door C
• Player switches Door B -> Tiger: 1/3 * ½
• Door B 1/3
• King opens Door C
• Player switches Door A -> Gold: 1/3
• Door C 1/3
• King opens Door B
• Player switches Door A -> Gold: 1/3

Basic Probability and Bayes Theorem

• Mr. Smith who is correct 75% of the time claims that event X will not occur
• Mr. Jones who is correct 60% of the time claims that event X will occur
• What is p(X)?

Basic Probability and Bayes Theorem

• This problem is underspecified (3 Variables)

Basic Probability and Bayes Theorem

• p0+p1+p2+...p7 = 1
• Since Smith is correct 75% of the time
• p0 + p2 + p5 + p7 = 0.75
• Since Jones is correct 60% of the time
• p0 + p3+p4+p7 = 0.60
• p(X) = p(R=y|S=N and J=Y) =p3/(p2+p3)

Basic Probability and Bayes Theorem

• Let A=p0+p7, B=p1+p6, C=p2+p5, and D=p3+p4, the conditions can

A+B+C+D = 1.00

A +C = 0.75

A +D = 0.60

• Three linear equations with four unknowns.
• Infinitely many solutions.
• A=0.5, B=0.25, C=0.15, D=0.10
• A=0.6, B=0.25, C=0.15, D=0.00

Basic Probability and Bayes Theorem

• Even if we arbitrarily select one of these solutions, there are still infinitely many ways of partitioning C and D to give the values of p2 and p3.
• Reasonable assumption to solve this problem?

Basic Probability and Bayes Theorem

• Smith is smarter than Jones. So Smith is correct whenever Jones is correct.
• p3 = 0, p4 = 0. p2 > 0
• So p(X) = 0
• Assume strong correlation between Smith and Jones' answers.

Basic Probability and Bayes Theorem

• Assume that the correctness of the answers are statistically independent.
• Each one of them is likely to be correct independent of whether the other one is correct or not
• 0.6 = (p0+p7)/(p0+p2+p5+p7)=(p3+p4)/(p1+p3+p4+p6)
• 0.75=(p0+p7)/(p0+p3+p4+p7)=(p2+p5)/(p1+p2+p5+p6)

Basic Probability and Bayes Theorem

• Let u = 0.6 and v=0.75, then
• p0+p7 = uv = 9/20
• p1+p6 = (1-u)(1-v) = 2/20
• p2+p5 = (1-u)v = 6/20
• p3+p4 = u(1-v) = 3/20
• Still not enough to calculate p(X)=p3/(p2+p3)
• Assume symmetry between Y and N
• p0=p7, p1=p6,p2=p5, and p3=p4
• Prior probability of X is 0.5 and probability of correctness between predicting Y and N is the same

Basic Probability and Bayes Theorem

• p2 = 6/40, p3=3/40 => p(X)=p3/(p2+p3) = 0.33
• Assume that you know that the probability of X a priori is x
• p0 = uv(1-x) p7 = uvx
• p1 = (1-u)(1-v)x p6 = (1-u)(1-v)(1-x)
• p2 = (1-u)v(1-x) p5 = (1-u)vx
• p3 = u(1-v)x p4 = u(1-v)(1-x)
• Then p(X) = p3/(p2+p3)=u(1-v)x/((1-u)v(1-x)+u(1-v)x)
• Can be extended to more than two predictions
• p(X)=(pA*pB*pC)/((pA*pB*pC)+(1-pA)(1-pB)(1-pC))

Bayes Formula

Normalization

Algorithm:

Conditioning

• Total probability

Conditioning

• Total probability:
• Bayes rule and background knowledge:

Simple Example of State Estimation

• Suppose a robot obtains measurement z
• What is P(doorOpen|z)?

Causal vs Diagnostic Reasoning

• P(open|z) is diagnostic.
• P(z|open) is causal.
• Often causal knowledge is easier to obtain.
• Bayes rule allows us to use causal knowledge:

count frequencies!

Example

• P(z|open) = 0.6 P(z|¬open) = 0.3
• P(open) = P(¬open) = 0.5

• z raises the probability that the door is open.

• Combining Evidence

• Suppose our robot obtains another observation z₂.
• How can we integrate this new information?
• More generally, how can we estimate�P(x| z₁...z_n )?

• Recursive Bayesian Updating

Markov assumption: z_n is independent of z₁,...,z_n-1 if we know x.

• Example: Second Measurement

• P(z₂|open) = 0.5 P(z₂|¬open) = 0.6
• P(open|z₁)=2/3

• z₂ lowers the probability that the door is open.

• Bayes Filters: Framework

• Given:
• Stream of observations z and action data u:
• Sensor model P(z|x).
• Action model P(x|u,x’).
• Prior probability of the system state P(x).
• Wanted:
• Estimate of the state X of a dynamical system.
• The posterior of the state is also called Belief:

• Markov Assumption

Underlying Assumptions

• Static world
• Independent noise
• Perfect model, no approximation errors

X_t-1

X_t

X_t+1

Z_t-1

Z_t

Z_t+1

u_t-1

u_t

• Bayes Filters

Bayes

z = observation

u = action

x = state

Markov

Markov

Total prob.

• Bayes Filter Algorithm

1. Algorithm Bayes_filter( Bel(x),d ):
2. η=0
3. If d is a perceptual data item z then
4. For all x do
7. For all x do
9. Else if d is an action data item u then
10. For all x do
12. Return Bel’(x)

• Bayes Filters for Robot Localization

• Dynamic Environments

• Two possible locations x₁ and x₂
• P(x₁)=0.99
• P(z|x₂)=0.09 P(z|x₁)=0.07

• Bayes Filters are Familiar!

• Kalman filters
• Particle filters
• Hidden Markov models
• Dynamic Bayes networks
• Partially Observable Markov Decision Processes (POMDPs)

• Summary

• Bayes rule allows us to compute probabilities that are hard to assess otherwise.
• Under the Markov assumption, recursive Bayesian updating can be used to efficiently combine evidence.
• Bayes filters are a probabilistic tool for estimating the state of dynamic systems.

References

• Lecture slides taken from Dieter Fox (University of Washington) course on probabilistic robotics