{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ML E2020 - Week 10 - Theoretical Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graphical Models\n",
    "\n",
    "As explained in the note *Coditional probabilites and graphical*, a graphical model is a graphical notation to describe the dependency relationships when specifying a joint probility. \n",
    "\n",
    "### From graph to joint probability\n",
    "\n",
    "***Exercise 1***: For the following four graphs, write down the joint probabilty of the random variables.\n",
    "\n",
    "![Graphical models](graphical-models.png)\n",
    "\n",
    "### From joint probability to graph\n",
    "\n",
    "***Exercise 2***: Draw the following four joint probabilities as dependency graphs:\n",
    "\n",
    "$p(X)p(Y)p(Z)$\n",
    "\n",
    "$p(X)p(Y\\,|\\,X)p(Z\\,|\\,X)$\n",
    "\n",
    "$p(X)p(Y\\,|\\,X)p(Z\\,|\\,Y)p(W\\,|\\,X,Z)$\n",
    "\n",
    "$p(Z_1)p(X_1\\,|\\,Z_1)\\prod_{i=2}^{5}p(X_i\\,|\\,Z_i,X_{i-1})\\prod_{i=2}^{5}p(Z_i\\,|\\,Z_{i-1})$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hidden Markov Models"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Exercise 3***: Questions to slides *Hidden Markov Models - Terminology, Representation and Basic Problems*:\n",
    "\n",
    "1. How much time does it take to compute the joint probability $P({\\bf X}, {\\bf Z} | \\Theta)$ in terms of $N$ and $K$, where ${\\bf X} = {{\\bf x}_1, \\ldots, {\\bf x}_N }$, ${\\bf Z} = {{\\bf z}_1, \\ldots, {\\bf z}_N }$, and $K$ is the number of hidden states in the hidden Markov model $\\Theta$?\n",
    "\n",
    "2. How many terms are there in the sum on slide 34 for computing $P({\\bf X}|\\Theta)$? Why?\n",
    "\n",
    "3. How many terms are there in the maximization on slide 38 for computing the Viterbi decoding ${\\bf Z}^*$? Why?\n",
    "\n",
    "4. How many terms are there in the maximixation on slide 39 for computing ${\\bf z}^*_n$, i.e. the *n*th state in a posterior decoding? Why?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Exercise 4***: Questions to slides *Hidden Markov Models - Algorithms for decoding*:\n",
    "\n",
    "1. Where in the derivation of $\\omega({\\bf z}_n$) on slide 7 do we use that the fact that we are working with hidden Markov models? And how do we use it?\n",
    "\n",
    "2. Where in the derivation of $p({\\bf z}_n | {\\bf x}_1, \\ldots, {\\bf x}_N)$ on slide 16 do we use the fact that we are working with hidden Markov models? And how do we use it?\n",
    "\n",
    "3. Where in the derivation of $\\alpha({\\bf z}_n)$ and $\\beta({\\bf z}_n)$ on slide 20 and 26 do we use that the fact that we are working with hidden Markov models? And how do we use it?\n",
    "\n",
    "4. Why is $P({\\bf X}) = \\sum_{{\\bf z}_n} \\alpha({\\bf z}_n) \\beta({\\bf z}_n) = \\sum_{{\\bf z}_N} \\alpha({\\bf z}_N)$ as stated on slide 31?\n",
    "\n",
    "5. Algorithmic question: Slide 35 shows how to compute $P({\\bf X})$ from $\\alpha({\\bf z}_N)$ in time $O(K^2N)$, i.e. the time it takes to compute the last (rightmost) colummn in the $\\alpha$-table. How much space do you need to compute this column? Do you need to store the entire $\\alpha$-table?\n",
    "\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.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}