Q5: Filtering – Fundamentals of Sensing, Tracking, and Autonomy 1

%T: 𝑋ₖ₊₁([0,1]) = [1,3] %F: 𝑋ₖ₊₁([−1,1]) = [−1,1] %T: 𝑓(𝑓(𝑓(1))) = 15 %F: 𝑋ₖ₊₁(𝑋ₖ₊₁([−1,1])) = [−1,1] %T: 𝑋ₖ₊₁(ℝ) = ℝ %T: 𝑋ₖ₊₁(∅) = ∅ %F: 𝑋ₖ₊₁(∅) = {0} %T: 𝑋ₖ₊₁(𝑋ₖ₊₁([−1,1])) = [−1,7] %T: 𝑋ₖ₊₁({−1}) = {−1} %F: 𝑓(𝑓([0,1])) = 𝑓(𝑓(𝑓(𝑓([0,1]))))

Question 1: Deterministic state flow¶

Let 𝑋 = ℝ be the state space. Let 𝑓 : 𝑋 → 𝑋 be the deterministic state flow defined as 𝑓(𝑥) = 2𝑥 + 1.

Let

X_{k+1}(X_k) = \{x_{k+1} \in X \mid x_k \in X_k \text{ and } x_{k+1} = f(x_k) \}. \\\

%T: 𝑓(0) = [−1,1] %F: 𝑓(1) = [−1,1] %F: 𝑋ₖ₊₁([−2,2]) = [−4,4] %T: 𝑋ₖ₊₁([−1,1]) = [−2,2] %T: If 𝐴 ⊂ 𝐵, then 𝑓(𝐴) ⊂ 𝑓(𝐵) %T: If 𝐴 ⊂ 𝐵, then 𝑋ₖ₊₁(𝐴) ⊂ 𝑋ₖ₊₁(𝐵) %F: 𝑋ₖ₊₁([0,∞)) = ℝ %F: 𝑋ₖ₊₁(𝑋ₖ₊₁((−1,1))) = [−4.4] %F: 𝑋ₖ₊₁({0}) = [0,1] %F: 𝑋ₖ₊₁([−1,0]) = 𝑋ₖ₊₁([0,1])

Question 2: Nondeterministic state flow¶

Let 𝑋 = ℝ be the state space. Let 𝑓 : 𝑋 → pow(𝑋) be the nondeterministic state flow defined as:

f(x) = \{x + d \in X \;|\; d \in [-1,1] \}. \\\

Let

X_{k+1}(X_k) = \{x_{k+1} \in X \mid x_k \in X_k \text{ and } x_{k+1} \in f(x_k) \}. \\\

% F: The preimage of 0 yields ℎ⁻¹(0) = [−1/2, 1/2]. % F: The preimage of 0 yields ℎ⁻¹(0) = (−1/2, 1/2). % T: The preimage of 0 yields ℎ⁻¹(0) = [−1/2, 1/2). % F: The preimage of 0 yields ℎ⁻¹(0) = (−1/2, 1/2). % T: If 𝑋ₖ = [0, 1] and the next observation is 𝑦ₖ₊₁ = 1, then 𝑋ₖ₊₁ = [1/2, 3/2). % F: If 𝑋ₖ = [0, 1] and the next observation is 𝑦ₖ₊₁ = 1, then 𝑋ₖ₊₁ = (1/2, 3/2). % T: If 𝑋ₖ = [0, 1/2] and the next observation is 𝑦ₖ₊₁ = 2, then 𝑋ₖ₊₁ = {3/2}. % F: If 𝑋ₖ = [0, 1/2] and the next observation is 𝑦ₖ₊₁ = 2, then 𝑋ₖ₊₁ = ∅. % F: If 𝑋ₖ = [0, 1] and the next observation is 𝑦ₖ₊₁ = 2, then 𝑋ₖ₊₁ = [5/2, 2]. % T: If 𝑋ₖ = ℝ, then 𝑋ₖ₊₁ = ℎ⁻¹(𝑦ₖ₊₁).

Question 3: Nondeterministic temporal filtering¶

Consider the same setup as in the previous problem, but now include a sensor mapping ℎ : 𝑋 → 𝑌 defined by:

y = \lfloor x + \tfrac{1}{2} \rfloor, \\\

in which ⌊·⌋ denotes the floor function (equivalent to the floor function in Python).

The preimage of 0 yields ℎ⁻¹(0) = [−1/2, 1/2].

The preimage of 0 yields ℎ⁻¹(0) = (−1/2, 1/2).

The preimage of 0 yields ℎ⁻¹(0) = [−1/2, 1/2).

The preimage of 0 yields ℎ⁻¹(0) = (−1/2, 1/2).

If 𝑋ₖ = [0, 1] and the next observation is 𝑦ₖ₊₁ = 1, then 𝑋ₖ₊₁ = [1/2, 3/2).

If 𝑋ₖ = [0, 1] and the next observation is 𝑦ₖ₊₁ = 1, then 𝑋ₖ₊₁ = (1/2, 3/2).

If 𝑋ₖ = [0, 1/2] and the next observation is 𝑦ₖ₊₁ = 2, then 𝑋ₖ₊₁ = {3/2}.

If 𝑋ₖ = [0, 1/2] and the next observation is 𝑦ₖ₊₁ = 2, then 𝑋ₖ₊₁ = ∅.

If 𝑋ₖ = [0, 1] and the next observation is 𝑦ₖ₊₁ = 2, then 𝑋ₖ₊₁ = [5/2, 2].

If 𝑋ₖ = ℝ, then 𝑋ₖ₊₁ = ℎ⁻¹(𝑦ₖ₊₁).

Warning: You have not logged in. You cannot answer.

% T: If 𝑝(𝑎∣𝑏) ≠ 𝑝(𝑎) and 𝑝(𝑏∣𝑎) ≠ 𝑝(𝑏), but 𝑝(𝑎,𝑏∣𝑐) = 𝑝(𝑎∣𝑐)𝑝(𝑏∣𝑐), then 𝑎 and 𝑏 are conditionally independent given 𝑐 % F: Independence without conditioning does not imply conditional independence % T: 𝑝(𝑎∣𝑏)𝑝(𝑏) = 𝑝(𝑎)𝑝(𝑏∣𝑎) % F: For any 𝑎 and 𝑏, 𝑃(𝑎 | 𝑏) ≥ 𝑃(𝑎). % T: If 𝑎 and 𝑏 are independent, then 𝑝(𝑎,𝑏) = 𝑝(𝑎)𝑝(𝑏) % F: 𝑝(𝑎∣𝑏,𝑐) = 𝑝(𝑎∣𝑏) % T: 𝑝(𝑎∣𝑏,𝑐) = 𝑝(𝑎∣𝑐)

Question 4: Discrete probability statements¶

Select ALL correct statements:

Bayes’ rule states that 𝑃(𝑎 | 𝑏) 𝑃(𝑏) = 𝑃(𝑎) 𝑃(𝑏 | 𝑎).

For any 𝑎 and 𝑏, 𝑃(𝑎 | 𝑏) ≥ 𝑃(𝑎).

If 𝑎 and 𝑏 are independent, then 𝑃(𝑎, 𝑏) = 𝑃(𝑏) 𝑃(𝑎).

If 𝑎 and 𝑏 are conditionally independent given 𝑐, then 𝑃(𝑎 | 𝑏, 𝑐) = 𝑃(𝑎 | 𝑏).

If 𝑎 and 𝑏 are conditionally independent given 𝑐, then 𝑃(𝑎 | 𝑏, 𝑐) = 𝑃(𝑎 | 𝑐).

Warning: You have not logged in. You cannot answer.

% T: By marginalization, 𝑝(𝑎) = ∑ᵦ 𝑝(𝑎∣𝑏) p(b) % T: By marginalization, 𝑝(𝑎∣𝑐) = ∑ᵦ 𝑝(𝑎∣𝑏,𝑐) p(b|c) % F: 𝑝(𝑎∣𝑏) = 𝑝(𝑏∣𝑎) % T: If 𝑎 and 𝑏 are independent, then 𝑃(𝑎 | 𝑏) = 𝑃(𝑎). % T: If 𝑎 and 𝑏 are independent, then 𝑃(𝑏 | 𝑎) = 𝑃(𝑏). % T: If 𝑃(𝑎 | 𝑐) = 𝑃(𝑎), then 𝑎 and 𝑐 are independent. % F: If 𝑃(𝑎, 𝑏) = 0, then at least one of 𝑃(𝑎) or 𝑃(𝑏) must be 0.

Question 5: More discrete probability statements¶

Select ALL correct statements:

By marginalization, 𝑃(𝑎) is obtained by summing 𝑃(𝑎 | 𝑏) 𝑃(𝑏) over all values of 𝑏.

By marginalization, 𝑃(𝑎 | 𝑐) is obtained by summing 𝑃(𝑎 | 𝑏,𝑐) 𝑃(𝑏 | 𝑐) over all values of 𝑏.

𝑃(𝑎 | 𝑏) = 𝑃(𝑏 | 𝑎).

If 𝑎 and 𝑏 are independent, then 𝑃(𝑎 | 𝑏) = 𝑃(𝑎).

If 𝑎 and 𝑏 are independent, then 𝑃(𝑏 | 𝑎) = 𝑃(𝑏).

If 𝑃(𝑎 | 𝑐) = 𝑃(𝑎), then 𝑎 and 𝑐 are independent.

If 𝑃(𝑎, 𝑏) = 0, then at least one of 𝑃(𝑎) or 𝑃(𝑏) must be 0.

Warning: You have not logged in. You cannot answer.

%T: 𝜇₁ = 𝜇 + 1. %T: 𝜇₂ = 2𝜇. %F: 𝜇₂ = 2𝜇₁ − 1. %F: 𝜇₁ = 𝜇₂. %F: 𝜎₁ = 𝜎 + 1. %T: 𝜎₁ = 𝜎. %T: 𝜎₂ = 2𝜎. %F: 𝜎₂ = 4𝜎. %F: 𝜇₁ = 𝜇 + 1 only if the samples are drawn from a Gaussian distribution. %F: 𝜇₂ = 2𝜇 only if the samples are drawn from a Gaussian distribution.

Question 6: Gaussians and sampling¶

Let 𝑆 ⊂ ℝ be a collection of 10,000 distinct samples that have mean 𝜇 and variance 𝜎².

Make a set 𝑆₁ = { 𝑥 ∈ ℝ ∣ 𝑥 − 1 ∈ 𝑆 } by adding 1 to all of the samples. Make another set 𝑆₂ = { 𝑥 ∈ ℝ ∣ 𝑥 / 2 ∈ 𝑆 } by multiplying all of the samples by 2. Let 𝜇ᵢ and 𝜎ᵢ² denote the mean and variance, respectively, of 𝑆ᵢ for 𝑖 = 1, 2.

%T: 𝑝(𝑥ₖ₊₁ ∣ 𝑦̃ₖ) is the pdf of the state at stage 𝑘+1, given observations up to stage 𝑘. %F: 𝑝(𝑥ₖ₊₁ ∣ 𝑦̃ₖ) is the pdf of the state at stage 𝑘+1, given the observation at stage 𝑘. %T: 𝑝(𝑥ₖ₊₁ ∣ 𝑥ₖ, 𝑦̃ₖ) = 𝑝(𝑥ₖ₊₁ ∣ 𝑥ₖ, 𝑦̃ₖ) because 𝑥ₖ₊₁ is assumed to be conditionally independent of 𝑦̃ₖ, given 𝑥ₖ. %F: 𝑝(𝑥ₖ₊₁ ∣ 𝑥ₖ, 𝑦̃ₖ) = 𝑝(𝑥ₖ₊₁ ∣ 𝑥ₖ) because 𝑥ₖ₊₁ is assumed to be conditionally independent of 𝑥ₖ, given 𝑦̃ₖ. %T: When 𝑦ₖ₊₁ is taken into account, the probabilistic sensing model is (𝑦ₖ₊₁ ∣ 𝑥ₖ₊₁).

Question 7: Probabilistic filters¶

Select all correct statements:

𝑃(𝑥ₖ₊₁ | 𝑦̃ₖ) is the pdf of the state at stage 𝑘 + 1, given observations up to stage 𝑘.

𝑃(𝑥ₖ₊₁ | 𝑦̃ₖ) is the pdf of the state at stage 𝑘 + 1, given the observation at stage 𝑘.

𝑃(𝑥ₖ₊₁ | 𝑥ₖ, 𝑦̃ₖ) = 𝑃(𝑥ₖ₊₁ | 𝑥ₖ, 𝑦̃ₖ) because 𝑥ₖ₊₁ is assumed to be conditionally independent of 𝑦̃ₖ, given 𝑥ₖ.

𝑃(𝑥ₖ₊₁ | 𝑥ₖ, 𝑦̃ₖ) = 𝑃(𝑥ₖ₊₁ | 𝑥ₖ) because 𝑥ₖ₊₁ is assumed to be conditionally independent of 𝑥ₖ, given 𝑦̃ₖ.

When 𝑦ₖ₊₁ is taken into account, the probabilistic sensing model is 𝑃(𝑦ₖ₊₁ | 𝑥ₖ₊₁).

Warning: You have not logged in. You cannot answer.

%T: 𝑃(𝑦ₖ₊₁ ∣ 𝑥ₖ₊₁, 𝑦̃ₖ) = 𝑃(𝑦ₖ₊₁ ∣ 𝑥ₖ₊₁) because 𝑦ₖ₊₁ is assumed to be conditionally independent of 𝑦̃ₖ, given 𝑥ₖ₊₁. %F: 𝑃(𝑦ₖ₊₁ ∣ 𝑥ₖ₊₁, 𝑦̃ₖ) = 𝑃(𝑦ₖ₊₁ ∣ 𝑥ₖ₊₁) because 𝑦ₖ₊₁ is assumed to be conditionally independent of 𝑥ₖ₊₁, given 𝑦̃ₖ. %F: If 𝑋 = {1,2,3,4,5,6,7}, then the dimension of 𝑰ₚᵣₒᵦ is 7. %T: If 𝑋 = {1,2,3,4,5,6,7}, then the dimension of 𝑰ₚᵣₒᵦ is 6. %F: We must always have that 𝑝(𝑥ₖ ∣ 𝑦̃ₖ) > 0 for all 𝑘, 𝑥ₖ, and 𝑦̃ₖ.

Question 8: More probabilistic filters¶

Select all correct statements:

𝑃(𝑦ₖ₊₁ | 𝑥ₖ₊₁, 𝑦̃ₖ) = 𝑃(𝑦ₖ₊₁ | 𝑥ₖ₊₁) because 𝑦ₖ₊₁ is assumed to be conditionally independent of 𝑦̃ₖ, given 𝑥ₖ₊₁.

𝑃(𝑦ₖ₊₁ | 𝑥ₖ₊₁, 𝑦̃ₖ) = 𝑃(𝑦ₖ₊₁ | 𝑥ₖ₊₁) because 𝑦ₖ₊₁ is assumed to be conditionally independent of 𝑥ₖ₊₁, given 𝑦̃ₖ.

If 𝑋 = {1, 2, 3, 4, 5, 6, 7}, then the dimension of 𝑰ₚᵣₒᵦ is 7.

If 𝑋 = {1, 2, 3, 4, 5, 6, 7}, then the dimension of 𝑰ₚᵣₒᵦ is 6.

We must always have that 𝑃(𝑥ₖ | 𝑦̃ₖ) > 0 for all 𝑘, 𝑥ₖ, and 𝑦̃ₖ.

Warning: You have not logged in. You cannot answer.

Lovelace

QUIZ 5: Filtering¶

Question 1: Deterministic state flow¶

Question 2: Nondeterministic state flow¶

Question 3: Nondeterministic temporal filtering¶

Question 4: Discrete probability statements¶

Question 5: More discrete probability statements¶

Question 6: Gaussians and sampling¶

Question 7: Probabilistic filters¶

Question 8: More probabilistic filters¶

Authors¶

Give feedback on this content