Exercise_04_representation_models.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Temporal and Spatial DataMining\n",
    "## Exercise 04 Representation Models"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1: HMM (Bonus task)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose there are four boxes, each with a different number of red and white balls inside, as follows:\n",
    "    \n",
    "          box1     box2     box3     box4\n",
    "\n",
    "    red:    5        3        6        8\n",
    "\n",
    "    white:  5        7        4        2\n",
    "\n",
    "Now take balls from these boxes for T times, record the color after each take, and put them back in the original box.\n",
    "\n",
    "The initial probability of selecting boxes is uniform distribution, i.g. [0.25, 0.25, 0.25, 0.25].\n",
    "\n",
    "Then select the next box after following these rules:\n",
    "\n",
    "* If currently box 1, select box 2\n",
    "* If it is currently box 2 or 3, the distribution selects the previous or latter box with probabilities of 0.4 and 0.6\n",
    "* If it is currently box 4, then each stays in box 4 or selects box 3 with a probability of 0.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)** According to the text, build the arrays for **initial probabilities ($\\pi$)**, **transition probabilities (A)**, and **output probabilities distributions (B)**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "pi = np.full((4), 0.25)\n",
    "A = np.array([[0, 1, 0, 0], [0.4, 0, 0.6, 0], [0, 0.4, 0, 0.6], [0, 0, 0.5, 0.5]])\n",
    "B = np.array([[0.5, 0.5], [0.3, 0.7], [0.6, 0.4], [0.8, 0.2]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** Implement the function **generate** in the class of HMM. (Only the **generate** function here.)\n",
    "\n",
    "**Hints** (Update on 12.05):\n",
    "\n",
    "(1). Add comments in the __init__() to explain the arguments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HMM(object):\n",
    "    def __init__(self, N, M, pi=None, A=None, B=None):\n",
    "        \"\"\"\n",
    "        N: the number of state values\n",
    "        M: the number of observation values\n",
    "        pi: initialization probabilities\n",
    "        A: transition probabilities between states\n",
    "        B: emission probabilities from a state to an observation\n",
    "        \"\"\"\n",
    "        self.N = N\n",
    "        self.M = M\n",
    "        self.pi = pi\n",
    "        self.A = A\n",
    "        self.B = B\n",
    "\n",
    "    def get_data_with_distribution(self, dist): \n",
    "        \"return the value based on a given probability distribution (dist)\"\n",
    "        \n",
    "        return np.random.choice(np.arange(len(dist)), p=dist)\n",
    "\n",
    "    def generate(self, T: int):\n",
    "        \"generate an observation sequence with the length of T\" \n",
    "        result = []\n",
    "        \n",
    "        i = self.get_data_with_distribution(self.pi)    # Generate the first state based on the initial probability distribution\n",
    "        o = self.get_data_with_distribution(self.B[i])  # Generate the first observations\n",
    "        result = [o]\n",
    "\n",
    "        z_t = i\n",
    "        \n",
    "        for t in range(T-1):\n",
    "            z_t = self.get_data_with_distribution(self.A[z_t])\n",
    "            o_t = self.get_data_with_distribution(self.B[z_t])\n",
    "            result.append(o_t)\n",
    "\n",
    "        return result\n",
    "    \n",
    "    def evaluate_forward(self, O):\n",
    "        '''\n",
    "        Calculate the probability of the sequence O with the given parameters A, B and Pi.\n",
    "        O: Observation sequence\n",
    "        \n",
    "        '''\n",
    "        alpha = self.pi * self.B[:, O[0]]\n",
    "        for t in range(1, len(O)):\n",
    "            alpha = np.sum(alpha.reshape(-1,1) * self.A * self.B[:, O[t]], axis=0)\n",
    "\n",
    "        return np.sum(alpha)\n",
    "\n",
    "    \n",
    "    def evaluate_backward(self, O): \n",
    "        beta = np.ones(self.N)\n",
    "        for t in reversed(range(1, len(O))):\n",
    "            beta = np.sum(self.A * self.B[:, O[t]] * beta, axis=1)\n",
    "\n",
    "        return np.sum(self.pi * beta * self.B[:, O[0]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)** Generate an observation sequence with the length of 10 using the class **HMM**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1, 0, 0, 0, 1, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "hmm = HMM(N=4, M=2, pi=pi, A=A, B=B)\n",
    "O = hmm.generate(10)\n",
    "print(O)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### HMM-Evaluation problem.\n",
    "Calculate the conditional probability $P(O|\\theta)$ when the parameter $\\theta = (\\pi, A, B)$ and the observation $O=(o_{1},o_{2},...,o_{T})$ are given.\n",
    "\n",
    "$P(O|\\theta)=P(o_{1},o_{2},...,o_{T}|\\theta)=\\sum_{Z}P(O,Z|\\theta)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)** [**Forward algorithm**](https://en.wikipedia.org/wiki/Forward_algorithm). (Update on 12.05)\n",
    "\n",
    "Define a forward probability: \n",
    "\n",
    "$\\alpha_{t}(i) = P(o_{1},o_{2},...,o_{t},z_{t}=s_{i}|\\theta)$\n",
    "\n",
    "which mean the joint probability of the hidden state $s_{i}$ at time t and the observation sequence $o_{1},o_{2},...,o_{t}$ with the given parameters.\n",
    "\n",
    "Therefore:\n",
    "\n",
    "$\\sum_{i}^{N}\\alpha_{T}(i)=\\sum_{i}^{N}P(O, z_{T}=s_{i}|\\theta)=P(O|\\theta)$\n",
    "\n",
    "**Proof**:\n",
    "1. $\\alpha_{1}(i)=\\pi_{i}b_{i}(o_{1})$\n",
    "2. $\\alpha_{t+1}(j) = \\sum_{i=1}^{N}a_{ij}b_{j}(o_{t+1})\\alpha_{t}(i)$, where $b_{j}(o_{t+1})=P(o_{t+1}|z_{t+1}=s_{j})$\n",
    "\n",
    "where $a_{ij}=P(z_{t+1}=s_{j}|z_{t}=s_{i})$, $b_{j}(o_{t+1}) = P(o_{t+1}|z_{t+1}=s_{j})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    " **---  Your Text Here ----** \n",
    "      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** Implement the function **evaluate_forward** in the class HMM and calculate the probability of the sequence (red, red, white, white, red).\n",
    "\n",
    "**Hints** (Update on 12.05):\n",
    "\n",
    "(1) Consider the relationship between the notations ($a_{ij}$, $b_{j}(o_{t+1})$) in the formulas and the attributes (self.A and self.B) of the class HMM\n",
    "\n",
    "(2) **T** in the formula refers to the length of the sequence.\n",
    "\n",
    "(3) **N** refers to the number of states.\n",
    "\n",
    "(4) For proof task, consider the independent observation assumption and the homogeneous markov assumption.\n",
    "\n",
    "(4) The probability of the sequence(red, red, white, white, red): **0.026862016000000002**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.026862016000000002\n"
     ]
    }
   ],
   "source": [
    "print(hmm.evaluate_forward([0,0,1,1,0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)** **Backward algorithm**\n",
    "\n",
    "Define a forward probability: \n",
    "\n",
    "$\\beta_{t}(i) = P(o_{T},o_{T-1},...o_{t+1}|z_{t}=s_{i},\\theta)$\n",
    "\n",
    "and the inital value $\\beta_{T}(1)=\\beta_{T}(2)=....=\\beta_{T}(N)=1$.\n",
    "\n",
    "So, $\\beta_{1}(i) = P(o_{T},o_{T-1},...o_{2}|z_{1}=s_{i},\\theta)$\n",
    "\n",
    "**Proof**:\n",
    "\n",
    "1. $\\beta_t(i) = \\sum_{j=1}^{N}a_{ij}b_{j}(o_{t+1})\\beta_{t+1}(j)$\n",
    "2. $P(O|\\theta)=P(o_{1},o_{2},...o_{T}|\\theta)=\\sum_{i=1}^{N}b_{i}(o_{1})\\pi_{i}\\beta_{1}(i)$\n",
    "3. $P(O|\\theta)=\\sum_{i=1}^{N}\\alpha_{t}(i)\\beta_{t}(i)$, for any $t$ with $1 \\leq t \\leq T$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    " **---  Your Text Here ----** \n",
    "      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d)** Implement the function **evaluation_backward** in the class HMM and calculate the probability of the sequence (red, red, white, white, red).\n",
    "\n",
    "**Hints** (Update on 12.05):\n",
    "\n",
    "(1) For proof task, consider the independent observation assumption.\n",
    "\n",
    "(2) The probability of the sequence(red, red, white, white, red): **0.026862016**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.026862016\n"
     ]
    }
   ],
   "source": [
    "print(hmm.evaluate_backward([0,0,1,1,0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### HMM-Learning Problem.\n",
    "Estimate the parameters $\\theta = (\\pi, A, B)$ of the HMM with the given observation $O=(o_{1},o_{2},...,o_{T})$ to get the maximal probability $P(O|\\theta)$.\n",
    "\n",
    "**a)** Proof of EM-algorithm/Baum-Welch algorithm:\n",
    "\n",
    "1. $\\pi_{i}^{(t+1)} = \\frac{\\alpha_{1}(i)\\beta_{1}(i)}{P(O|\\theta^{(t)})}$\n",
    "\n",
    "2. $a_{ij}^{(t+1)}=\\frac{\\sum_{t=1}^{T-1}\\alpha_{t}(i)\\beta_{t+1}(j)a_{ij}b_{j}(o_{t+1})}{\\sum_{t=1}^{T-1}\\alpha_{t}(i)\\beta_{t}(i)}$\n",
    "\n",
    "3. $b_{jk}^{(t+1)}=\\frac{\\sum_{t=1}^{T}\\alpha_{t}(j)\\beta_{t}(j)I(o_{t}=k)}{\\sum_{t=1}^{T}\\alpha_{t}(j)\\beta_{t}(j)}$\n",
    "\n",
    "**Hint**:\n",
    "\n",
    "* $\\alpha$ and $\\beta$ are defined in the forward/backward algorithms.\n",
    "* Subscript $t$ and superscript $(t)$ have different meanings. Subscript $t$ means the $t_{th}$ observation in the sequence. Superscript $(t)$ means the $t_{th}$ iteration in EM algorithm\n",
    "* $I(o_{t}=k)=1$ and $I(o_{t} \\neq k)=0$\n",
    "* $P(O|\\theta)=\\sum_{i=1}^{N}\\alpha_{t}(i)\\beta_{t}(i)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    " **---  Your Text Here ----** \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** Implement the function **generate** and **fit**. Refer to the formulars in (a) of **HMM-learning problem**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HMM(object):\n",
    "    def __init__(self, N, M, iteration=50):\n",
    "        self.N = N\n",
    "        self.M = M\n",
    "        self.iter = iteration\n",
    "        \n",
    "    def get_data_with_distribute(self, dist): \n",
    "        \"return the value based on a given probability distribution (dist)\"\n",
    "        \n",
    "        return np.random.choice(np.arange(len(dist)), p=dist)\n",
    "    \n",
    "    def generate(self, T: int):\n",
    "        \"generate an observation sequence with the length of T\" \n",
    "        result=[]\n",
    "        \n",
    "        i = self.get_data_with_distribute(self.pi)    # Generate the first state based on the initial probability distribution\n",
    "        o = self.get_data_with_distribute(self.B[i])  # Generate the first observations\n",
    "        result = [o]\n",
    "        \n",
    "        # Generate the remaining status and observation data in sequence\n",
    "        ####################\n",
    "    # Your Code Here   #\n",
    "    ####################        \n",
    "        return result\n",
    "    \n",
    "    def fit(self, O):\n",
    "        '''\n",
    "        Estimate the parameters\n",
    "        '''\n",
    "        # Initialize the parameters: pi, A, B\n",
    "        self.pi = np.random.sample(self.N)\n",
    "        self.A = np.ones((self.N,self.N)) / self.N\n",
    "        self.B = np.ones((self.N,self.M)) / self.M\n",
    "        self.pi = self.pi / self.pi.sum()\n",
    "        \n",
    "        T = len(O)\n",
    "        for it in range(self.iter):\n",
    "            # according to the formulars shown above(subtask a), update the parameters.\n",
    "            alpha, beta = self.get_alpha_beta(O)\n",
    "            ####################\n",
    "    # Your Code Here   #\n",
    "    ####################\n",
    "\n",
    "    def get_alpha_beta(self, O):\n",
    "        '''\n",
    "        Calculate the forward/backward probability alpha and beta\n",
    "        '''\n",
    "        T = len(O)\n",
    "        alpha = np.zeros((T,self.N))\n",
    "        alpha[0,:] = self.pi * self.B[:,O[0]]\n",
    "        for i in range(T-1):\n",
    "            o = O[i+1]\n",
    "            alpha[i+1,:] = np.sum(self.A * alpha[i].reshape(-1,1) * self.B[:,o].reshape(1,-1), axis=0)\n",
    "\n",
    "        beta = np.ones((T,self.N))\n",
    "        for j in range(T-1,0,-1):\n",
    "            for i in range(self.N):\n",
    "                beta[j-1,i] = np.sum(self.A[i,:] * self.B[:,O[j]] * beta[j])\n",
    "\n",
    "        return alpha, beta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**c)** Plot the original observation data and the generated observation data.\n",
    "\n",
    "**Hint**: (Update on 12.05)\n",
    "\n",
    "(1) The output figure is given. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "def triangle_data(T):\n",
    "    '''\n",
    "    generate the squence of triangular wave\n",
    "    '''\n",
    "    data = []\n",
    "    for x in range(T):\n",
    "        x = x % 6\n",
    "        data.append(x if x <= 3 else 6-x)\n",
    "    return data\n",
    "\n",
    "data = np.array(triangle_data(30))\n",
    "hmm = HMM(10, 4, 50)\n",
    "hmm.fit(data)               # Estimate the parameters according to the data\n",
    "gen_obs = hmm.generate(30)  # generate data based one the estimated parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.arange(30)\n",
    "####################\n",
    "# Your Code Here   #\n",
    "####################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**d)** Additional task: try to change the parameter **N**, **M**, **iteration_nr** in subtask c. What could you find? Why?\n",
    "\n",
    "**Hint** (Update on 12.05)\n",
    "\n",
    "(1) For example, try HMM(2, 4, 100) or HMM(10, 20, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "####################\n",
    "# Your Code Here   #\n",
    "####################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2: Kalman Filter\n",
    "\n",
    "Consider a car on a frictionless, infinitely long straight track. The car initially stopped at position 0.   \n",
    "We measure the position of the car every $\\Delta t$ seconds, but this measurement is inaccurate; we want to build a model about its position and speed.\n",
    "\n",
    "#### 1. Init phase\n",
    "The position and speed of the car can be described by the linear state space as follows:\n",
    "$$X_k = \\begin{bmatrix}x\\\\\\dot{X}\\end{bmatrix}$$\n",
    "\n",
    "Where $\\dot{x}$ is the velocity, which is the derivative of position with respect to time. Suppose the initial position is 0 and velocity is 1.\n",
    "$$X_k = \\begin{bmatrix}0\\\\1\\end{bmatrix}$$\n",
    "\n",
    "$\\textbf{P}$ is the process covariance matrix. Suppose we do not know exactly the initial position and velocity. In that case, the covariance matrix can be initialized as a matrix whose diagonal elements are B, and B takes an appropriate larger number. \n",
    "$$\\textbf{P}_{0} = \\begin{bmatrix} B & 0 \\\\ 0 & B \\end{bmatrix}$$\n",
    "\n",
    "If we know the exact initial position, and we give a covariance matrix:\n",
    "$$\\textbf{P}_{0} = \\begin{bmatrix} 0 & 0 \\\\ 0 & 0 \\end{bmatrix}$$\n",
    "\n",
    "In our case we set:\n",
    "$$\\textbf{P}_{0} = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix}$$\n",
    "\n",
    "#### 2. Prediction phase\n",
    "We assume that the relationship between time $k-1$ and time $k$ is as follows:\n",
    "$$\\textbf{X}^p_k = \\textbf{F X}_{k-1} + \\textbf{w}_k$$\n",
    "The superscript $p$ represents the prior prediction of $\\textbf{X}$ at time $k$.    \n",
    "$\\textbf{F}$ is state transistion matrix:\n",
    "$$\\textbf{F} = \\begin{bmatrix} 1 & \\Delta t \\\\ 0 & 1 \\end{bmatrix}$$\n",
    "Suppose we measure the state of the car every 1 second, then:\n",
    "$$\\textbf{F} = \\begin{bmatrix} 1 & 1 \\\\ 0 & 1 \\end{bmatrix}$$\n",
    "$\\textbf{w}_k$ (system output error) conforms to a normal distribution Q with a mean value of 0 and a standard deviation of $\\sigma_a$.  \n",
    "$$\\sigma_a = \\begin{bmatrix} 0.5 & 0 \\\\ 0 & 0.5 \\end{bmatrix}$$\n",
    "For process covariance matrix P, the relationship between time $k-1$ and time $k$ is as follows\n",
    "$$\\textbf{P}^p_k = \\textbf{F }\\textbf{P}_{k-1}\\textbf{ F}^T + \\textbf{Q}$$\n",
    "The superscript $p$ represents the prior prediction of $\\textbf{P}$  at time k\n",
    "\n",
    "#### 3. Measurement phase\n",
    "At every moment, we measure its position and velocity $\\textbf{Z}_{k}$, and the measurement is disturbed by noise $\\textbf{v}_{k}$:\n",
    "$$\\textbf{Z}_{k} = \\textbf{H X}_{k} + \\textbf{v}_{k}$$\n",
    "We assume that the noise $\\textbf{v}_{k}$ (measurement error) obeys a normal distribution R, with a mean value of 0 and a standard deviation of $\\sigma_z$.\n",
    "$$\\sigma_z = \\begin{bmatrix} 0.5 & 0 \\\\ 0 & 0.5 \\end{bmatrix}$$\n",
    "$\\textbf{H} $ is measurement function:\n",
    "$$\\textbf{H} = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix}$$\n",
    "\n",
    "#### 4. Update phase\n",
    "Calculate Kalman Gain Phase:\n",
    "$$\\textbf{K}_k = \\textbf{P}^p_k\\textbf{ H}^T \\textbf{S}_{k}^{-1}$$ \n",
    "$$\\textbf{S}_{k} = \\textbf{H}\\textbf{P}_{k}\\textbf{H}^{T} + \\textbf{R}$$\n",
    "The posterior estimate of $P_k$ is:\n",
    "$$\\textbf{P}_k = (\\textbf{I} - \\textbf{K}_k \\textbf{ H})\\textbf{P}^p_k$$\n",
    "The posterior estimate of $X_k$ is:\n",
    "$$\\textbf{X}_k = \\textbf{X}^p_k + \\textbf{K}_k [\\textbf{Z}_{k} - \\textbf{ H}\\textbf{ X}^p_k]$$\n",
    "\n",
    "#### 5. Repeat prediction, measurement and update phase\n",
    "$$\\textbf{X}_{k-1} =  \\textbf{X}_{k}$$\n",
    "$$\\textbf{P}_{k-1} =  \\textbf{P}_{k}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)** Implement the Kalman Filter manually with the help of above formulas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import numpy.random as rd\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#----------Init Phase----------- #\n",
    "\n",
    "x = np.matrix([[0.0],\n",
    "               [1.0]])                # The ground truth of initial position and velocity\n",
    "x_post= np.matrix([[0.0],   \n",
    "                   [1.0]])            # The posterior estimation of initial position and velocity\n",
    "\n",
    "Q = np.matrix([[0.5, 0.0],\n",
    "               [0.0, 0.5]])           # Process noise covariance matrix, constant\n",
    "R = np.matrix([[0.5, 0.0],\n",
    "               [0.0, 0.5]])           # Measurement noise covariance matrix, constant\n",
    "\n",
    "F = np.matrix([[1, 1],\n",
    "               [0, 1]])               # State transistion matrix, constant\n",
    "H = np.matrix([[1.0, 0.0],\n",
    "               [0.0, 1.0]])           # Measurement function, constant\n",
    "P = np.matrix([[1.0, 0.0],\n",
    "               [0.0, 1.0]])           # Process covariance matrix\n",
    "\n",
    "x_real_list = x                       # The list to save real positions and velocities\n",
    "z_list = np.matrix([[], []])          # The list to save the measurements of position and velocity\n",
    "x_prior_list = np.matrix([[], []])    # The list to save the prior estimations of position and velocity\n",
    "x_post_list = x_post                  # The list to save the posterior estimations of position and velocity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N_step = 30\n",
    "\n",
    "for i in range(0, N_step):\n",
    "    \n",
    "    #---- State transition of ground truth ----#\n",
    "    x = F*x\n",
    "    x_real_list = np.concatenate((x_real_list, x), axis=1)\n",
    "    \n",
    "    #------------ Prediction Phase ------------#\n",
    "    ####################\n",
    "    # Your Code Here   #\n",
    "    #################### \n",
    "    \n",
    "    #------------ Measurement Phase ------------#\n",
    "    ####################\n",
    "    # Your Code Here   #\n",
    "    #################### \n",
    "    \n",
    "    #--------------- Update Phase --------------#\n",
    "    ####################\n",
    "    # Your Code Here   #\n",
    "    #################### "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**b)** Compare the **true values**, **the measurements**, **the prior and posterior prediction** regarding the **position** and **velocity** in graphics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "legend_text = ['Real', 'Measure', 'Prior', 'Posterior']\n",
    "####################\n",
    "# Your Code Here   #\n",
    "#################### \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3: Orthogonal Polynomials for Shape-Space-Representation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**a)** What are the benefits of using a subspace representation (i.e. Shape Space Representation)?\n",
    "\n",
    "\n",
    " **---  Your Text Here ----** \n",
    "\n",
    "\n",
    "**b)** What kind of information can be reflected in the coefficients of the subspce polynomial shape?\n",
    "\n",
    "\n",
    " **---  Your Text Here ----** \n",
    "\n",
    "\n",
    "**c)** Derive the optimal Solution (in the least-squares sense) for the weight vector (coefficients) $\\mathbf{w}^{\\text{opt}}$ from the linear Problem:\n",
    "\n",
    "- $\\text{min}\\sum_{n=1}^{N}\\left(\\left(\\sum_{k=1}^{K}w_k\\cdot f_k(t_n) \\right)-y_n\\right)^2$\n",
    "\n",
    "\n",
    "**d)** What are the properties of the polynomials in the method presented as shape space represetation? (i.e. advantages compared to monomial-based approaches?)\n",
    "\n",
    "\n",
    " **---  Your Text Here ----** \n",
    "\n",
    "\n",
    "**e)** How is the measure of the similarity of the time series defined and what is the dimension of the subspace in which this measure is applied?\n",
    "\n",
    "\n",
    " **---  Your Text Here ----** \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}