day_2/exercise_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sequence Models\n",
    "## Day 2 of the summerschool\n",
    "\n",
    "\n",
    "\n",
    "| Exercise | Requires coding | What to code (if anything) | What should you learn (or practice)    | Done it! |\n",
    "|----------|-----------------|----------------------------|----------------------------------------|----------|\n",
    "| 2.1      | No             |                             | Sequence data                            | No       |\n",
    "| 2.2      | No              |                            | HMM probabilities                             | No       |\n",
    "| 2.3      | No              |                            | HMM trellis                                   | No       |\n",
    "| 2.4      | No              |                            |logsumexp trick                        | No       |\n",
    "| 2.5      | No             |                         | Forward Backward algorithm                               | No       |\n",
    "| 2.6      | No              |                            | Posterior decoding | No       |\n",
    "| 2.7      | No              |                            | More Posterior decoding  | No       |\n",
    "| 2.8      | Yes              |     viterbi algorithm                       | viterbi agorithm for  decoding | No       |\n",
    "| 2.9      | No              |                            | smoothing importance | No       |\n",
    "| 2.10      | Yes              |    EM algorithm              | EM algorithm | No       |\n",
    "| 2.11      | No              |                             | test EM algorithm | No       |\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Summary \n",
    "\n",
    "- We will train the models in pairs $(x,y)$ where $x$ and $y$ will be sequences.\n",
    "- Once the model is trained, given an input sequence $x$ the model will predict\n",
    "  a target sequence $y$.\n",
    "  \n",
    "In order to do so we will implement...\n",
    "  \n",
    "-  one inference algorithm for Hidden Markov Models.\n",
    "    - We will use it to find the most likely hidden state sequence given an observation sequence. \n",
    "    \n",
    "\n",
    "\n",
    "### Notation\n",
    "\n",
    "#### Set of Words $\\Sigma$ and set of states $\\Lambda$\n",
    "This notebook will use the following notation.\n",
    "\n",
    "- $\\Sigma := \\{w_1,\\ldots,w_J\\}$ is the set of words (or vocabulary).\n",
    "- $\\Lambda:= \\{c_1,\\ldots, c_K\\}$ is the set of labels.\n",
    "\n",
    "A sentence is an element of the Kleene clousure of $\\Sigma$, denoted by $\\Sigma^*$.\n",
    "The Kleene clousure of $\\Sigma$, is defined as the set containing all possible sentences of arbitrary lengt that can be created using the words in $\\Sigma$. More formally,\n",
    "\n",
    "$$\n",
    "\\Sigma^* := \\{\\varepsilon\\} \\cup \\Sigma \\cup \\Sigma^2 \\cup \\ldots\n",
    "$$\n",
    "where  $\\{\\varepsilon\\}$ is an \"empty word\". In other words, inputs are observation sequences, $x = x_1 x_2 \\ldots x_N$,  where each $x_i \\in \\Sigma$. \n",
    "\n",
    "Given such an $x$, we seek the corresponding state sequence, $y = y_1 y_2 \\ldots y_N$, \n",
    "where each $y_i \\in \\Lambda$. We also consider two special states: the ${\\tt start}$ symbol,\n",
    "which starts the sequence, and the ${\\tt stop}$ symbol, which ends the sequence. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 2.1\n",
    "Consider a person who is only interested in four activities.\n",
    "- walking in the park $({\\tt walk})$,\n",
    "- shopping (${\\tt shop}$),\n",
    "- cleaning the apartment (${\\tt clean}$)\n",
    "- playing tennis (${\\tt tennis}$).\n",
    "\n",
    "Also, consider that the choice of what the person does on a given day is determined exclusively by the weather on that day, which can be either ${\\tt rainy}$ or ${\\tt sunny}$. \n",
    "\n",
    "Now, supposing that we observe what the person did on a sequence of days, the question is: \n",
    "can we use that information to predict the weather on each of those days? \n",
    "\n",
    "To tackle this problem, we assume  that the weather behaves as a discrete Markov chain (with markov property 1): the weather on a given day depends only on the weather on the previous day. The entire system can be described as an HMM.\n",
    "\n",
    "In this example \n",
    "\n",
    "$$\n",
    "\\begin{array}\n",
    "\\hline\n",
    "\\Sigma := \\{ {\\tt walk},{\\tt shop},{\\tt clean},{\\tt tennis}\\}\\\\\n",
    "\\Lambda: = \\{ {\\tt rainy},{\\tt sunny} \\} \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "\n",
    "Let us assume that we are given access to three different sequences of days, containing both the activities performed by the person and the weather on those days.\n",
    "\n",
    "The information given has the form $(x,y) = (x_i / y_i)$ where $x_i$ is a word in our vocabulary ( ${\\tt walk},{\\tt shop},{\\tt clean},{\\tt tennis}$) and $y_i$ is a state (${\\tt rainy},{\\tt sunny}$). The whole train set is:\n",
    "\n",
    "- (${\\tt walk/rainy, walk/sunny, shop/sunny, clean/sunny}$)\n",
    "- (${\\tt walk/rainy, walk/rainy, shop/rainy, clean/sunny}$)\n",
    "- (${\\tt walk/sunny, shop/sunny, shop/sunny, clean/sunny}$)\n",
    "\n",
    "We will use this information  to train our model.\n",
    "\n",
    "Now assume we are asked to predict the weather conditions on two different\n",
    "sequences of days. During these two sequences, we observed the person performing the following activities: \n",
    "\n",
    "- $({\\tt walk, walk, shop, clean})$\n",
    "- $({\\tt clean, walk, tennis, walk})$\n",
    "\n",
    "\n",
    "The following image represents the first training sequence which starts with  ${\\tt start}$ symbol, and ends with ${\\tt stop}$.\n",
    "\n",
    "<img src=\"../images_for_notebooks/day_2/hmm_new.pdf\">\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The autoreload extension is already loaded. To reload it, use:\n",
      "  %reload_ext autoreload\n"
     ]
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "# We will this append to ensure we can import lxmls toolking\n",
    "sys.path.append('../../lxmls-toolkit')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import lxmls\n",
    "import lxmls.readers.simple_sequence as ssr\n",
    "import scipy\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2.1, Getting in touch with the provided classes\n",
    "\n",
    "The objective of this exercises is to get in touch with the classes used to store the sequences, you will need this for the next exercise.\n",
    "\n",
    "We will use\n",
    "\n",
    "- class ``Sequence`` in ``lxmls/sequences/sequence.py`` file\n",
    "- class ``LabelDictionary`` in ``lxmls/sequences/label_dictionary.py`` file\n",
    "- class ``SequenceList`` in ``lxmls/sequences/sequence_list.py`` file\n",
    "\n",
    "- class ``_SequenceIterator`` in ``lxmls/sequences/sequence_list.py`` file\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# We could put the code of the classes here with no need to import anything from lxmls-toolkit\n",
    "from lxmls.sequences.label_dictionary import LabelDictionary\n",
    "from lxmls.sequences.sequence import Sequence\n",
    "from lxmls.sequences.sequence_list import SequenceList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following class will implement the train and test data from example 2.1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class SimpleSequence:\n",
    "\n",
    "    def __init__(self):\n",
    "        # Observation set.\n",
    "        self.x_dict = LabelDictionary(['walk', 'shop', 'clean', 'tennis'])\n",
    "        \n",
    "        # State set.\n",
    "        self.y_dict = LabelDictionary(['rainy', 'sunny'])\n",
    "        \n",
    "        # Generate training sequences.\n",
    "        train_sequences = SequenceList(self.x_dict, self.y_dict)\n",
    "        train_sequences.add_sequence(['walk', 'walk', 'shop', 'clean'], ['rainy', 'sunny', 'sunny', 'sunny'])\n",
    "        train_sequences.add_sequence(['walk', 'walk', 'shop', 'clean'], ['rainy', 'rainy', 'rainy', 'sunny'])\n",
    "        train_sequences.add_sequence(['walk', 'shop', 'shop', 'clean'], ['sunny', 'sunny', 'sunny', 'sunny'])\n",
    "\n",
    "        # Generate test sequences.\n",
    "        test_sequences = SequenceList(self.x_dict, self.y_dict)\n",
    "        test_sequences.add_sequence(['walk', 'walk', 'shop', 'clean'], ['rainy', 'sunny', 'sunny', 'sunny'])\n",
    "        test_sequences.add_sequence(['clean', 'walk', 'tennis', 'walk'], ['sunny', 'sunny', 'sunny', 'sunny'])\n",
    "\n",
    "        self.train = train_sequences\n",
    "        self.test = test_sequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that x_dict and y_dict are ``LabelDictionary``\n",
    "\n",
    "**``LabelDictionary`` objects are instanciated with a list of strings **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the data in ``train_sequences`` and ``test_sequences`` are instanciated as ``SequenceList`` objects. \n",
    "\n",
    "**``SequenceList`` objects are instanciated with**\n",
    "\n",
    "- ``x_dict``  containing all possible words $\\Sigma$\n",
    "- ``y_dict``  containing all possible states $\\Lambda$\n",
    "- ``seq_list`` list containing the data (if nothing is passed it starts with an empty list)\n",
    "\n",
    "\n",
    "**``SequenceList`` objects have a method ``add_sequence`` which recieves as input two lists of strings**\n",
    "- ``SequenceList.add_sequence`` appends the given sequence with labels $x,y$ as a ``Sequence`` object.\n",
    "\n",
    "**``Sequence`` objects are instanciated with **:\n",
    "\n",
    "- `` x`` list of observations\n",
    "- `` y`` list of states\n",
    "- `` nr`` length of x and y\n",
    "- ``sequence_list`` \n",
    "      \n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Now we will load the data from Example 2.1 and look at the training and test set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "walk/rainy walk/sunny shop/sunny clean/sunny \n",
      "walk/rainy walk/rainy shop/rainy clean/sunny \n",
      "walk/sunny shop/sunny shop/sunny clean/sunny \n"
     ]
    }
   ],
   "source": [
    "simple = ssr.SimpleSequence()\n",
    "for sequence in simple.train.seq_list: \n",
    "    print(sequence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[walk/rainy walk/sunny shop/sunny clean/sunny , walk/rainy walk/rainy shop/rainy clean/sunny , walk/sunny shop/sunny shop/sunny clean/sunny ]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simple.train"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "walk/rainy walk/sunny shop/sunny clean/sunny \n",
      "clean/sunny walk/sunny tennis/sunny walk/sunny \n"
     ]
    }
   ],
   "source": [
    "for sequence in simple.test.seq_list: \n",
    "    print(sequence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "lxmls.sequences.sequence.Sequence"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(simple.train.seq_list[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'nr': 0,\n",
       " 'sequence_list': [walk/rainy walk/sunny shop/sunny clean/sunny , walk/rainy walk/rainy shop/rainy clean/sunny , walk/sunny shop/sunny shop/sunny clean/sunny ],\n",
       " 'x': [0, 0, 1, 2],\n",
       " 'y': [0, 1, 1, 1]}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simple.train.seq_list[0].__dict__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "lxmls.sequences.sequence_list.SequenceList"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(simple.train.seq_list[0].sequence_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 1, 2]\n",
      "[0, 0, 1, 2]\n",
      "[0, 1, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "for sequence in simple.train.seq_list:\n",
    "    print(sequence.x)"
   ]
  }
 ],
 "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}