The session covered the prediction step of the algorithm as shown in the sessions structure.
To get there we learned about iterated maps, and propagated small perturbations (error propagation) over these maps. The end result was that for a noisy iterated map $$ x_k = A x_{k-1} + B u_{k-1} + \epsilon_{k} $$
the iterated maps for the mean and the covariance are
$$ m_k = A m_{k-1} + B u_{k-1} \qquad P_k = A P_{k-1} A^\top + Q_{k-1} $$
which came out directly of propagating the gaussian noise through the iterated map.
There were a couple of things that did not go according to my original plan:
-
I did not cover ordinary differential equations, nor its discretization.
This was something good, because there was more than enough material for the session anyways. I think we will do this on the beginning of the last session. Then we will consider ODEs not as a main topic, but as an application of the method, i.e. you can do ODEs as well!
-
We did batch linear regression and wrote the recursive form of a straight line
This is is also discussed in detail in the reference book of the workshop. We went a little more into the implementation detail of batch linear regression, as shown below. You will not find this in the slides, that’s why it is here. It will be added in slides of future iterations of the workshop.
All in all, I think the first session went well. I am looking forward to the feedback from the participants.
Linear regression
We took a detour to discuss batch linear regression, and write the dynamic model that represent a straight line.
The problem is: given some examples of a line (two would suffice)
$$ \left\lbrace (t_i, y_i)\right\rbrace $$
Find the slope and intercept of a straight line that goes through the points.
$$ a t_i + b = y_i $$
In the batch version of the solution one builds the design matrix (also data matrix, and for polynomial regression Vandermonde matrix) and multiplies it by the unknown coefficients to get the values in the data:
$$ D \begin{bmatrix}a \\ b\end{bmatrix} = \boldsymbol{y} $$
where the design matrix is
$$ D = \begin{bmatrix}t_1 & 1\\ \vdots & \vdots \\ t_n & 1\end{bmatrix} $$
By solving the problem with, e.g. least squares one recovers the coefficients of the line.
In code python this would look like (there are other solves that could be used, e.g. scipy or scikit-learn)
import numpy as np
# Generate data
t = np.linspace(0, 1, 10)
y = 2 * t - 1
# Solve regression
D = np.vander(t, 2)
coef = np.pinv(D) @ y
or in GNU Octave code
# Generate data
t = linspace (0, 1, 10).';
y = 2 * t - 1;
# Solve regression
D = vander(t, 2);
coef = D \ y
which result in the expected values for the slope (2) ad the intercept (-1). The design matrix can be built with any feature (function) of the regressor, e.g. polynomial regression would look just like this, alas with a wider Vandermonde matrix.
One issue with the batch approach is that the more data we get the worst is the conditioning of the design matrix. Also the independent variable might grow to very large numbers. Hence this solution is not the best choice for an online algorithm.
Since in this session we covered only the dynamic model used in the prediction step, we proceeded to write the dynamic model of the straight line. The only insight needed is that if we get a point already on the line, a neighboring point is obtained by
$$ y_k = y_{k-1} + a \Delta t_k \qquad \Delta t_k = t_k - t_{k-1} $$
where the time step is not expected to grow indefinitely (like the independent variable in the batch regression). You can get this insight by looking at the two points
$$ y_{k-1} = a t_{k-1} + b $$
$$ y_k = a t_k + b $$
The iteration above, defines the dynamic and measurement model
$$ x_k = x_{k-1}, \qquad x_0 = \begin{bmatrix}a \\ y_0\end{bmatrix} $$ $$ y_k = H_k x_k, \qquad H_k = \begin{bmatrix}\Delta t_k & 1\end{bmatrix} $$
What would be the measurement matrix for polynomial regression?
That’s where we left it. Next session will take it from there to see how we update the mean of the states and their covariance when the observations are uncertain.
Slides
To download a PDF file with the slides and notes click the image below!
