Description
For theory part, please make sure you have detailed steps. Final grades are given based on steps not the nal answer. Various starter les are provided in the ipythonnotebook. Your report should be a PDF le containing:
Page 1: Problem 1
Page 2: Problem 2
Page 3: Problem 3
Pages 4 & 5: Problem 4 (c)
Page 6 and onwards: PDF rendering of completed ipython notebook, which will contain your answers to Problems 4(a), 4(b), 5, 6.
1. Maximum Likelihood [5 pts]
The Poisson distribution is a discrete probability distribution that expresses the probability of a number of events occurring in a xed period of time if these events occur with a known average rate and independently of the time since the last event. Assume we obtain m i.i.d.
samples x^{(1)}; : : : ; x^{(m)} distributed according to the Poisson distribution P (x = k) = ^{k}^{e} for
k!

= 0; 1; 2; 3; : : :. What is the maximum likelihood estimate of as a function of x^{(1)}; : : : ; x^{(m)}?
2. Linearity of Expectation, Positive Semide niteness [5 pts]
A matrix A 2 R^{nxn} is positive semide nite (often denoted by A 0) if and only if:
^{A}ij ^{=} ^{A}ji
8z 2 R^{n} : z^{>}Az 0
If A is also symmetric, prove that covariance matrices, i.e., matrices of the form = E[(X EX)(X EX)^{>}] are guaranteed to be positive semide nite.

The gaussian integral and completion of squares trick [10 pts] Let A 2 R^{n n} be a positive de nite matrix, b 2 R^{n}, and c 2 R. Prove that,

^{I}_{x2R}n
n
2
T
T
jAj2
exp(c
_{2}^{1} b^{T} A ^{1}b)
1
(2 )2
exp(
x
Ax
x b c) dx =
1
Hint: You can directly use the fact that the integral of a multivariate Gaussian equals 1.

CS287 Homework #4
2
4. Kalman Filtering, Smoothing, EM

Implementation of Kalman Filtering [10 pts]
In this question you will implement a Kalman Filter. Look at Homework4 Q.ipynb for more detailed instructions. Results should be included in the completed ipython notebook.

Implementation of Smoothing [10 pts]
In this question you will implement a Kalman Smoother. Look at Homework4 Q.ipynb for more detailed instructions. Results should be included in the completed ipython notebook.

Implementation EM. [10 pts]
In this question you will implement the EM algorithm to estimate the covariance matrices. Look at Homework4 Q.ipynb for more detailed instructions. Results should be included in the completed ipython notebook.

Application to Species Population Size Estimation from Observations of Total Population Size.[10 pts]
Consider three species U; V; W that grow independently of each other, exponentially with growth rates: U grows 2% per hour, V grows 6% per hour, and C grows 11% per hour. The goal is to estimate the initial size of each population based on the measurements of total population.
Let x_{U} (t) denote the population size of species U after t hours, for t = 0; 1; : : :, and similarly for x_{V} (t) and x_{W} (t), so that
x_{U} (t + 1) = 1:02x_{U} (t); x_{V} (t + 1) = 1:06x_{V} (t); x_{W} (t + 1) = 1:11x_{W} (t):
The total population measurements are y(t) = x_{U} (t) + x_{V} (t) + x_{W} (t) + v(t), where v(t) are IID, N (0; 0:36). (Thus the total population is measured with a standard deviation of 0.6).
The prior information is that x_{U} (0); x_{V} (0); x_{W} (0) (which are what we want to estimate) are IID N (6; 2). (Obviously the Gaussian model is not completely accurate since it allows the initial populations to be negative with some small probability, but we’ll ignore that.)
How do you formulate this problem as a Kalman ltering problem by providing your A; B; C; d; Q; R. How long will it be (in hours) before we can estimate x_{U} (0) with a variance less than 0.01?
How long for x_{V} (0)? How long for x_{W} (0)? Starter code can be found in Homework4 Q.ipynb.
Results should be included in the completed ipython notebook.

Correlated Noise. [10 pts]
In many practical situations the noise is not independent. Consider the following stochastic system, for which the noise is not independent:
CS287 Homework #4
x_{0} N( _{0}; _{0})
x_{t+1} = Ax_{t} + w_{t}
w_{t} = 0:3w_{t} _{1} + 0:2w_{t} _{2} + p_{t}
p_{t} N (0; _{pp})
y_{t} = Cx_{t} + v_{t}
v_{t} = 0:8v_{t} _{1} + q_{t} _{1}
q_{t} N (0; _{qq})
p _{1} = q _{1} = v _{1} = w _{1} = w
3
1
_{2} = 0
Describe how, by choosing the appropriate state representation, the above setup can be molded into a standard Kalman ltering setup. In particular, describe the state, the dynamics model, and the measurement model such that the problem is transformed into the standard Kalman ltering setup with uncorrelated noise.
5. Sensor Selection [10 pts]
We consider the following linear system:

^{x}t+1
=
Ax_{t} + w_{t}
z_{t}
=
C_{t}x_{t} + v_{t}
where A 2 R^{n n} is constant, but C_{t} can vary with time. The noise contributions are independent, and
x_{0} N (0; _{0}); w_{t} N (0; _{w}) v_{t} N (0; _{v}):
Here is the twist: the measurement matrix C_{t} at each time comes from the set S = fS_{1}; : : : ; S_{K} g.
In other words, at each time t, we have C_{t} = S_{i}_{t} . The sequence i_{0}; i_{1}; i_{2}; : : : speci es which of
the K possible measurements is taken at time t. For example the sequence 2; 2; 2; : : : means
that C_{t} = S_{2} for all t. The sequence 1; 2; : : : ; K; 1; 2; : : : ; K; : : : is called roundrobin: we cycle through the possible measurements, in order, over and over again.
Here is the interesting part: you get to choose the measurement sequence i_{0}; i_{1}; i_{2}; : : :.
You will work with the following speci c system:

2
3
0:6
0:8
0:5
A = ^{4} _{1}0_{:1}:1
1:5
1:1
5
2
; _{w} = I; _{v} = 0:1 ; _{0}
= I
0:4
0:2
and K = 3 with
0:64 ; S_{2} = 0:37 0:86 0:37 ; S_{3} = 0 0 1 :
S_{1} = 0:74 0:21

Using One Sensor. Plot trace( _{tj0:t}) versus t for the three special cases when C_{t} = S_{1} for all t, C_{t} = S_{2} for all t, and C_{t} = S_{3} for all t.

Roundrobin. Plot trace( _{tj0:t}) versus t using the roundrobin sensor sequence 1; 2; 3; 1; 2; 3; : : :.

Greedy Sensor Selection. Plot trace( _{tj0:t}) versus t using greedy sensor selection. In
greedy sensor selection at time t the choice of i_{0}; i_{1}; : : : ; i_{t} _{1} has already been made and it
has determined _{tj0:t} _{1}. Then _{tj0:t} depends on i_{t} only, i.e., which of S_{1}; : : : ; S_{K} is chosen
as C_{t}. Among these K choices you pick the one that minimizes trace( _{tj0:t}).

CS287 Homework #4
4
See Homework4 Q.ipynb part 3 and look for Your code here for the parts that you need to ll in. Results should be included in the completed ipython notebook.
Note none of these require knowledge of the measurements z_{0}; z_{1}; : : :.
6. Extended Kalman Filter (EKF)[20 pts]
In this question you get to implement an extended Kalman Filter (EKF) for state estimation for nonlinear dynamics and observation models.
Notes: Let x 2 R^{xDim} be the system state, u 2 R^{uDim} denote the control input applied to the system, and z 2 R^{zDim} be the vector of observations obtained about the system state using sensors. We are given a discretetime stochastic dynamics model that describes how the system state evolves and an observation model that relates the obtained observations to the state, given here in statetransition notation:

^{x}t+1
= f(x_{t}; u_{t}; q_{t});
q_{t} N (0; Q);
(1)
^{z}t
= h(x_{t}; r_{t});
r_{t} N (0; R):
(2)
Given the current state estimate x^_{t}, control input u_{t}, covariance _{t}, and observation z_{t+1}, the
EKF update equations are given by:

^{x^}t+1
= f(x^_{t}; u_{t}; 0) + K_{t}(z_{t+1}
h(f(x^_{t}; u_{t}; 0); 0));
(3a)
t+1
= (I
^{K}t^{H}t^{)} _{t+1}
(3b)
where A_{t}
=
@f
(x^_{t}; u_{t}; 0);
M_{t} =
@f
(x^_{t}; u_{t}; 0);
(3c)
@x
@q
^{H}t
=
@h
(f(x^_{t}; u_{t}; 0); 0);
N_{t} =
@h
(f(x^_{t}; u_{t}; 0); 0);
(3d)
@x
@r
t+1
= A_{t t}A^{T} + M_{t}QM^{T} ;
K_{t} =
H^{T} (H_{t}
t+1
H^{T} + N_{t}RN^{T} ) ^{1}
:
(3e)
t
t
t+1
t
t
t
Q. See Homework4 Q.ipynb part 4 and look for Your code here for the parts that you need to ll in. Use the routine provided in numerical jac function to compute the required Jacobians (Eqs. (3c), (3d)). The script considers a twodimensional nonlinear system de ned by:

^{x}t+1
[1]
= 0:1 (x_{t}[1])^{2} 2 x_{t}[1] + 20 + q_{t}[1];
x_{t+1}[2]
= x_{t}[1] + 0:3 x_{t}[2] 3 + 3 q_{t}[2]
and z_{t}[1]
= x_{t}^{T} x_{t} + sin(5 r_{t}[1]);
z_{t}
[2]
= 3 (x_{t}[2])^{2}=x_{t}[1] + r_{t}[2];
where dynamics noise q_{t} and the measurement noise r_{t} are assumed to be drawn from a Gaussian distribution with zero mean and speci ed variances Q = [ ^{2}_{0} ^{0}_{2} ] and R = [ ^{1}_{0 10}^{0} ], respectively.
For verifying correctness, starting from an initial state x_{0} N ([ ^{10}_{10} ] ; [ ^{1}_{0} ^{0}_{1} ]), a random trajectory X_{1:50} was generated and corresponding observations Z_{1:50} were collected.
The provided code plots the ground truth value of the state X_{1:50} along each dimension and also plots the state estimate given by the EKF (blue dotted line) and plots 3standard deviations of the variance corresponding to each dimension. It also prints out the state estimate x^_{50} and covariance _{50} at the nal time step to help you verify correctness of your implementation. Results should be included in the completed ipython notebook.