Day 19 - Forward Algorithm & Backward Algorithm/Starter/notebook.ipynb

{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-f78a23d2e0af544e",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "# Day 19 notebook\n",
                "\n",
                "The objectives of this notebook are to practice \n",
                "\n",
                "* adding values in log space\n",
                "* computing the forward matrix for a sequence and HMM\n",
                "* calculating posterior probabilities for a sequence and HMM"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "collapsed": true,
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-d5859c1bfc173e35",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "outputs": [],
            "source": [
                "# Modules used in this activity\n",
                "import math      # for log\n",
                "import functools # for reduce\n",
                "import random    # for simulations"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-fa4a9f9eb5ce8826",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "## A `HiddenMarkovModel` class\n",
                "\n",
                "In this activity, we will continue to expand on the `HiddenMarkovModel` class that we developed in the last activity.  Specifically, we will add four new methods to this class:\n",
                "\n",
                "1. `forward_matrix` (Problem 2)\n",
                "2. `backward_matrix` (provided for you)\n",
                "3. `posterior_matrix` (Problem 3)\n",
                "4. `log_probability` (provided for you)"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "collapsed": true
            },
            "outputs": [],
            "source": [
                "class HiddenMarkovModel:\n",
                "    def __init__(self, states, chars, \n",
                "                 transition_prob_matrix, initial_probs, emission_prob_matrix):\n",
                "        \"\"\"Initializes a HiddenMarkovModel\n",
                "        \n",
                "        Models represented by this class do not explicitly represent a begin state and do\n",
                "        not allow for an end state.\n",
                "        \n",
                "        Args:\n",
                "            states: a string giving the characters representing the hidden states\n",
                "                of the model (1 character per state)\n",
                "            chars: a string giving the set of characters possibly emitted by the\n",
                "                states of the model\n",
                "            transition_prob_matrix: a list of lists of probabilities representing a\n",
                "                transition probability matrix. transition_prob_matrix[s][t] should equal \n",
                "                P(pi_i = t | pi_{i-1} = s). Row s is thus the conditional probability \n",
                "                distribution P(pi_i | pi_{i-1} = s). The indices in this matrix correspond \n",
                "                to the indices of the states in the states argument\n",
                "            initial_probs: a list of probabilities representing the initial state \n",
                "                probabilities. Entry s of this list is P(pi_1 = s), i.e., the probability that\n",
                "                the first hidden state in the chain is s.  The indices of this list correspond to the\n",
                "                indices of the states in the states argument.\n",
                "            emission_prob_matrix: a list of lists of probabilities representing an emission\n",
                "                probability matrix.  emission_prob_matrix[s][c] should equal \n",
                "                P(X_i = c | pi_i = s), i.e., the probability of state s emitting character c. \n",
                "                Row s is thus the conditional probability distribution P(X_i | pi_i = s).\n",
                "                The row indices of this matrix correspond to the indices of the states in\n",
                "                the states argument.  The column indices of the matrix correspond to the \n",
                "                indices of the characters in the chars argument.\n",
                "        \n",
                "        \"\"\"\n",
                "        self.states = states\n",
                "        self.chars = chars\n",
                "        self.transition_prob_matrix = transition_prob_matrix\n",
                "        self.initial_probs = initial_probs\n",
                "        self.emission_prob_matrix = emission_prob_matrix\n",
                "        \n",
                "        # Precompute log-transformations of the model parameters\n",
                "        # to avoid computing these many times\n",
                "        self.log_transition_prob_matrix = log_transform_matrix(transition_prob_matrix)\n",
                "        self.log_initial_probs = log_transform_vector(initial_probs)\n",
                "        self.log_emission_prob_matrix = log_transform_matrix(emission_prob_matrix)\n",
                "    \n",
                "    def encode_states(self, state_sequence):\n",
                "        \"\"\"Encodes a string of state characters as a list of indices of the states.\"\"\"\n",
                "        return [self.states.index(char) for char in state_sequence]\n",
                "\n",
                "    def decode_states(self, indices):\n",
                "        \"\"\"Decodes a sequence of state indices into a string of the state characters.\"\"\"\n",
                "        return \"\".join(self.states[index] for index in indices)\n",
                "\n",
                "    def encode_sequence(self, sequence):\n",
                "        \"\"\"Encodes a string of observed characters as a list of indices of the characters.\"\"\"\n",
                "        return [self.chars.index(char) for char in sequence]\n",
                "\n",
                "    def decode_sequence(self, indices):\n",
                "        \"\"\"Decodes a sequence of observed character indices into a string of characters.\"\"\"\n",
                "        return \"\".join(self.chars[index] for index in indices)\n",
                "\n",
                "    def simulate(self, length):\n",
                "        \"\"\"Simulates a sequence of hidden states and emitted characters of\n",
                "        the given length from this HMM.\n",
                "        \n",
                "        Args:\n",
                "            length: the length of the sequence to simulate\n",
                "        Returns:\n",
                "            A tuple of the form (hidden_state_string, char_string) where hidden_state_string is a\n",
                "            string of state characters and char_string is a string of observed characters.\n",
                "        \"\"\"\n",
                "        state_indices = [None] * length\n",
                "        char_indices = [None] * length\n",
                "        for i in range(length):\n",
                "            state_probs = self.transition_prob_matrix[state_indices[i - 1]] if i > 0 else self.initial_probs\n",
                "            state_indices[i] = sample_categorical(state_probs)\n",
                "            char_indices[i] = sample_categorical(self.emission_prob_matrix[state_indices[i]])\n",
                "            \n",
                "        return (self.decode_states(state_indices), self.decode_sequence(char_indices))\n",
                "        \n",
                "    def log_joint_probability(self, hidden_state_string, char_string):\n",
                "        \"\"\"Calculates the (natural) log joint probability of a path of hidden states\n",
                "        and an observed sequence given this HMM.\n",
                "        \n",
                "        Args:\n",
                "            hidden_state_string: a string representing the sequence of hidden states (pi)\n",
                "            char_string: a string representing the sequence of observed characters (X)\n",
                "        Returns:\n",
                "            log(P(hidden_states, observed_chars))\n",
                "        \"\"\"\n",
                "        state_indices = self.encode_states(hidden_state_string)\n",
                "        char_indices = self.encode_sequence(char_string)\n",
                "\n",
                "        log_p = 0.0\n",
                "        last_state_index = None\n",
                "        for state_index, char_index in zip(state_indices, char_indices):\n",
                "            if last_state_index is None:\n",
                "                log_p += self.log_initial_probs[state_index]\n",
                "            else:\n",
                "                log_p += self.log_transition_prob_matrix[last_state_index][state_index]\n",
                "            log_p += self.log_emission_prob_matrix[state_index][char_index]\n",
                "            last_state_index = state_index\n",
                "        return log_p\n",
                "\n",
                "    def viterbi_matrix(self, char_string):\n",
                "        \"\"\"Computes the (log-transformed) Viterbi dynamic programming matrix V for\n",
                "        the given observed sequence.\n",
                "\n",
                "        Args:\n",
                "            char_string: a string representing the sequence of observed characters (X)\n",
                "        Returns:\n",
                "            A matrix (list of lists) representing the Viterbi dynamic programming matrix,\n",
                "            with rows corresponding to states and columns corresponding to positions in the\n",
                "            sequence.\n",
                "        \"\"\"\n",
                "        char_indices = self.encode_sequence(char_string)\n",
                "        \n",
                "        # Initialize the viterbi dynamic programming matrix\n",
                "        # the entry V[k][i] corresponds to the subproblem V_k(i+1)\n",
                "        # where i is a 0-based index (e.g., V[k][0] corresponds to the subproblem\n",
                "        # of the most probable path of the prefix of length = 1). We will not explicitly\n",
                "        # represent the begin or end states.  As a result, we will not explicitly store the\n",
                "        # initialization values described in the textbook and lecture.\n",
                "        V = matrix(len(self.states), len(char_string))\n",
                "        if not char_string: return V\n",
                "        \n",
                "        # initialization (first position in sequence)\n",
                "        for ell in range(len(self.states)):    # loop over hidden state indices\n",
                "            V[ell][0] = (self.log_initial_probs[ell] + \n",
                "                         self.log_emission_prob_matrix[ell][char_indices[0]])\n",
                "\n",
                "        # main fill stage\n",
                "        for i in range(1, len(char_string)):    # loop over positions\n",
                "            for ell in range(len(self.states)): # loop over hidden state indices\n",
                "                V[ell][i] = (self.log_emission_prob_matrix[ell][char_indices[i]] + \n",
                "                             max(V[k][i - 1] + self.log_transition_prob_matrix[k][ell]\n",
                "                                 for k in range(len(self.states))))\n",
                "\n",
                "        return V\n",
                "    \n",
                "    def viterbi_traceback(self, V):\n",
                "        \"\"\"Computes a most probable path given a (log) Viterbi dynamic programming matrix.\n",
                "        \n",
                "        Uses a traceback procedure that does not require traceback pointers.  In the case of\n",
                "        ties, this traceback prefers the state with the largest index.\n",
                "        \n",
                "        Args:\n",
                "            V: A matrix (list of lists) representing the Viterbi dynamic programming matrix\n",
                "               containing log-transformed values.\n",
                "        Returns:\n",
                "            A string representing a most probable sequence of hidden states\n",
                "        \"\"\"\n",
                "        L = len(V[0])               # deduce the length of the sequence from # columns in V\n",
                "        if L == 0: return \"\"        # empty string base case\n",
                "        state_indices = [None] * L  # initialize hidden state path\n",
                "        \n",
                "        # determine the state at the last position in a most probable path\n",
                "        max_prob, max_state = max((V[k][L - 1], k) for k in range(len(self.states)))\n",
                "        state_indices[L - 1] = max_state\n",
                "        \n",
                "        # traceback from this last state by redoing the recurrence calculation at each step\n",
                "        # the emission probabilities are not included in the calculations because they are\n",
                "        # irrelevant for determining the maximizing state\n",
                "        for i in range(L - 1, 0, -1):\n",
                "            max_prob, max_state = max((V[k][i - 1] + self.log_transition_prob_matrix[k][max_state], k)\n",
                "                                      for k in range(len(self.states)))\n",
                "            state_indices[i - 1] = max_state\n",
                "            \n",
                "        # return string representation of hidden state path\n",
                "        return self.decode_states(state_indices)        \n",
                "\n",
                "    def most_probable_path(self, char_string):\n",
                "        \"\"\"Computes a most probable path of hidden states for the observed sequence.\n",
                "\n",
                "        Args:\n",
                "            char_string: a string representing the sequence of observed characters (X)\n",
                "        Returns:\n",
                "            A string representing a most probable sequence of hidden states.\n",
                "        \"\"\"\n",
                "        V = self.viterbi_matrix(char_string)\n",
                "        return self.viterbi_traceback(V)    \n",
                "    \n",
                "    def forward_matrix(self, char_string):\n",
                "        \"\"\"Computes the (log-transformed) Forward dynamic programming matrix f for\n",
                "        the given observed sequence.\n",
                "\n",
                "        Args:\n",
                "            char_string: a string representing the sequence of observed characters (X)\n",
                "        Returns:\n",
                "            A matrix (list of lists) representing the Forward dynamic programming matrix,\n",
                "            with rows corresponding to states and columns corresponding to positions in the\n",
                "            sequence.\n",
                "        \"\"\"\n",
                "        char_indices = self.encode_sequence(char_string)\n",
                "        \n",
                "        # Initialize the forward dynamic programming matrix\n",
                "        # the entry f[k][i] corresponds to the subproblem f_k(i+1)\n",
                "        # where i is a 0-based index (e.g., f[k][0] corresponds to the subproblem\n",
                "        # of the probability of the prefix of length = 1 and ending in state k). We will \n",
                "        # not explicitly represent the begin or end states.  As a result, we will not\n",
                "        # explicitly store the initialization values described in the textbook and lecture.\n",
                "        f = matrix(len(self.states), len(char_string))\n",
                "        if not char_string: return f\n",
                "        \n",
                "        # initialization\n",
                "        for ell in range(len(self.states)):\n",
                "            f[ell][0] = (self.log_initial_probs[ell] +\n",
                "                         self.log_emission_prob_matrix[ell][char_indices[0]])\n",
                "\n",
                "        # main fill stage\n",
                "        for i in range(1, len(char_string)):\n",
                "            for ell in range(len(self.states)):\n",
                "                ###\n",
                "                ### YOUR CODE HERE\n",
                "                ###\n",
                "\n",
                "        return f\n",
                "    \n",
                "    def backward_matrix(self, char_string):\n",
                "        \"\"\"Computes the (log-transformed) Backward dynamic programming matrix f for\n",
                "        the given observed sequence.\n",
                "\n",
                "        Args:\n",
                "            char_string: a string representing the sequence of observed characters (X)\n",
                "        Returns:\n",
                "            A matrix (list of lists) representing the Backward dynamic programming matrix,\n",
                "            with rows corresponding to states and columns corresponding to positions in the\n",
                "            sequence.\n",
                "        \"\"\"\n",
                "        char_indices = self.encode_sequence(char_string)\n",
                "        \n",
                "        # Initialize the backward dynamic programming matrix\n",
                "        # the entry b[k][i] corresponds to the subproblem b_k(i+1)\n",
                "        # where i is a 0-based index. We will not explicitly represent the begin or end states.\n",
                "        # As a result, the initialization at last position sets the backward probability to 1 (0 in log space).\n",
                "        b = matrix(len(self.states), len(char_string))\n",
                "        if not char_string: return b\n",
                "        \n",
                "        # initialization\n",
                "        for ell in range(len(self.states)):\n",
                "            b[ell][len(char_string) - 1] = 0.0\n",
                "\n",
                "        # main fill stage\n",
                "        for i in range(len(char_string) - 2, -1, -1):\n",
                "            for k in range(len(self.states)):\n",
                "                b[k][i] = sum_log_probs(self.log_transition_prob_matrix[k][ell] +\n",
                "                                        self.log_emission_prob_matrix[ell][char_indices[i + 1]] +\n",
                "                                        b[ell][i + 1]\n",
                "                                        for ell in range(len(self.states)))\n",
                "        return b\n",
                "\n",
                "    def log_probability(self, char_string):\n",
                "        \"\"\"Calculates the (natural) log probability (log(P(char_string))) \n",
                "        of an observed sequence given this HMM\"\"\"\n",
                "        f = self.forward_matrix(char_string)\n",
                "        return sum_log_probs(f[k][-1] for k in range(len(self.states)))\n",
                "    \n",
                "    def posterior_matrix(self, char_string):\n",
                "        \"\"\"Computes the posterior probability matrix for the given observed sequence.\n",
                "\n",
                "        Args:\n",
                "            char_string: a string representing the sequence of observed characters (X)\n",
                "        Returns:\n",
                "            a matrix (list of lists) with the entry in the kth row and ith column (e.g., m[k][i]) \n",
                "            giving the posterior probability that state k emitted character i, i.e., P(pi_i = k| x)\n",
                "        \"\"\"\n",
                "        ###\n",
                "        ### YOUR CODE HERE\n",
                "        ###\n",
                "\n",
                "    def posterior_decoding_path(self, char_string):\n",
                "        \"\"\"Computes the posterior decoding path of hidden states for the observed sequence.\n",
                "\n",
                "        In the case that multiple states tie for the highest posterior probability\n",
                "        at a given position, the state with the highest index is chosen.\n",
                "        \n",
                "        Args:\n",
                "            char_string: a string representing the sequence of observed characters (X)\n",
                "        Returns:\n",
                "            A string representing a sequence of hidden states.\n",
                "        \"\"\"\n",
                "        p = self.posterior_matrix(char_string)\n",
                "        state_indices = [max((prob, i) for i, prob in enumerate(col))[1] for col in zip(*p)]\n",
                "        return self.decode_states(state_indices)            \n",
                "        \n",
                "def sample_categorical(distribution):\n",
                "    \"\"\"Randomly sample from a categorical distribution (a discrete distribution over K categories).\n",
                "    \n",
                "    Args:\n",
                "        distribution: a list of probabilities representing a discrete distribution over K categories.\n",
                "    Returns:\n",
                "        The index of the category sampled.\n",
                "    \"\"\"\n",
                "    r = random.random()\n",
                "    for i, prob in enumerate(distribution):\n",
                "        if r < prob:\n",
                "            return i\n",
                "        else:\n",
                "            r -= prob\n",
                "    # in case we encounter floating point issues return the last index\n",
                "    return len(distribution) - 1    \n",
                "\n",
                "def log_transform_vector(v):\n",
                "    \"\"\"Returns a new vector (a list) with log-transformed values\"\"\"\n",
                "    return list(map(math.log, v))\n",
                "\n",
                "def log_transform_matrix(m):\n",
                "    \"\"\"Returns a new matrix (a list of lists) with log-transformed values\"\"\"\n",
                "    return list(map(log_transform_vector, m))\n",
                "\n",
                "def round_matrix(m, digits=2):\n",
                "    \"\"\"Returns a new matrix (a list of lists) with rounded values\"\"\"\n",
                "    return [round_vector(v, digits) for v in m]\n",
                "    \n",
                "def round_vector(v, digits=2):\n",
                "    \"\"\"Returns a new vector (a list) with rounded values\"\"\"\n",
                "    return [round(x, digits) for x in v]\n",
                "\n",
                "def matrix(num_rows, num_cols, initial_value=None):\n",
                "    \"\"\"Constructs a matrix (a list of lists)\"\"\"\n",
                "    return [[initial_value] * num_cols for i in range(num_rows)]\n",
                "\n",
                "# Using the class above, we construct an HMM for the occasionally dishonest casino example\n",
                "# described in the lecture and textbook\n",
                "casino_states = \"FL\"     # F = fair die, L = loaded die\n",
                "casino_chars = \"123456\"  # the six sides of the die\n",
                "casino_initial_probs = [0.5, 0.5]\n",
                "casino_transition_prob_matrix = [\n",
                "    [0.95, 0.05],\n",
                "    [0.10, 0.90]\n",
                "]\n",
                "\n",
                "casino_emission_prob_matrix = [\n",
                "    [ 1\/6,  1\/6,  1\/6,  1\/6,  1\/6, 1\/6],\n",
                "    [1\/10, 1\/10, 1\/10, 1\/10, 1\/10, 1\/2]\n",
                "]\n",
                "casino_hmm = HiddenMarkovModel(casino_states, \n",
                "                               casino_chars, \n",
                "                               casino_transition_prob_matrix, \n",
                "                               casino_initial_probs,\n",
                "                               casino_emission_prob_matrix)"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-aa4f0365a433b307",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "## PROBLEM 1: Adding probabilities in log space (1 POINT)\n",
                "Recall that in the last activity we needed to implement the Viterbi algorithm in terms of log probabilities instead of raw probabilities for numerical reasons.  We will need to do the same for the Forward and Backward algorithms.  One complication with working in log space for the Forward and Backward algorithms is that adding values in log space is tricky.\n",
                "\n",
                "In section 3.6 of the textbook, a convenient equation is provided for computing the sum of probabilities in log space.  Suppose we wish to compute $\\tilde{r} = \\log(p + q)$ using the log probabilities $\\tilde{p} = \\log(p)$ and $\\tilde{q} = \\log(q)$.  This computation is accurately carried out using the following equation:\n",
                "\n",
                "$\\tilde{r} = \\tilde{p} + \\log(1+\\exp(\\tilde{q} - \\tilde{p}))$\n",
                "\n",
                "where $q$ is assumed to be less than $p$, without loss of generality.\n",
                "\n",
                "You are to implement this equation in the following function."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "collapsed": true
            },
            "outputs": [],
            "source": [
                "def add_log_probs(log_p, log_q):\n",
                "    \"\"\"Computes the sum of two probabilities in log space.\"\"\"\n",
                "    ###\n",
                "    ### YOUR CODE HERE\n",
                "    ###\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-1a7421e9f94a87d2",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "The function below, which uses the `add_log_probs` function, will be used in implementing the Forward and Backward algorithms."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "collapsed": true,
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-efa24fa0f2a17871",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "outputs": [],
            "source": [
                "def sum_log_probs(log_probs):\n",
                "    \"\"\"Computes the sum of an iterable of probabilities in log space\"\"\"\n",
                "    return functools.reduce(add_log_probs, log_probs)"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "collapsed": true,
                "nbgrader": {
                    "grade": true,
                    "grade_id": "add_log_probs",
                    "locked": true,
                    "points": 1,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "outputs": [],
            "source": [
                "# tests for add_log_probs\n",
                "assert round(add_log_probs(math.log(0.75), math.log(0.25)), 2) == 0.0\n",
                "assert round(add_log_probs(math.log(0.5), math.log(0.25)), 2) == round(math.log(0.75), 2)\n",
                "assert round(add_log_probs(math.log(0.1), math.log(0.00001)), 4) == -2.3025\n",
                "assert round(add_log_probs(-1000, -1000), 2) == -999.31\n",
                "assert round(add_log_probs(-2000, -3000), 2) == -2000\n",
                "assert round(add_log_probs(-3000, -2000), 2) == -2000"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-c9939a7e659607b3",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "## PROBLEM 2: Forward matrix (1 POINT)\n",
                "\n",
                "Implement the `forward_matrix` method of the `HiddenMarkovModel` class.  Note that this method should return a matrix of **log** probabilities."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "nbgrader": {
                    "grade": true,
                    "grade_id": "forward_matrix",
                    "locked": true,
                    "points": 1,
                    "schema_version": 1,
                    "solution": false
                },
                "scrolled": true,
                "editable": false,
                "deletable": false
            },
            "outputs": [],
            "source": [
                "# tests for forward_matrix\n",
                "assert round_matrix(casino_hmm.forward_matrix('6')) == [[-2.48], \n",
                "                                                        [-1.39]]\n",
                "assert round_matrix(casino_hmm.forward_matrix('1')) == [[-2.48], \n",
                "                                                        [-3.0]]\n",
                "assert round_matrix(casino_hmm.forward_matrix('16')) == [[-2.48, -4.27], \n",
                "                                                         [-3.0, -3.71]]\n",
                "assert round_matrix(casino_hmm.forward_matrix('165')) == [[-2.48, -4.27, -5.94], \n",
                "                                                          [-3.0, -3.71, -6.08]]\n",
                "assert round_matrix(casino_hmm.forward_matrix('666661111')) == [\n",
                "    [-2.48, -4.05, -5.37, -6.44, -7.34, -8.18, -9.72, -11.42, -13.19],\n",
                "    [-1.39, -2.17, -2.96, -3.75, -4.54, -6.95, -9.34, -11.71, -14.05]]\n",
                "assert round_matrix(casino_hmm.forward_matrix('4631262516')) == [\n",
                "    [-2.48, -4.27, -5.94, -7.7, -9.49, -11.3, -13.05, -14.84, -16.65, -18.47],\n",
                "    [-3.0, -3.71, -6.08, -8.43, -10.73, -11.35, -13.7, -16.01, -18.25, -18.81]]\n",
                "assert round(casino_hmm.log_probability('1' * 1000), 2) == -1835.97\n",
                "print(\"SUCCESS: forward_matrix passed all tests!\")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-c6f30553edf0b68a",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "## PROBLEM 3: Posterior probabilities (1 POINT)\n",
                "\n",
                "Implement the `posterior_matrix` method of the `HiddenMarkovModel` class.  Note that this should return a matrix with **raw** (not log-transformed) probabilities."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "nbgrader": {
                    "grade": true,
                    "grade_id": "posterior_matrix",
                    "locked": true,
                    "points": 1,
                    "schema_version": 1,
                    "solution": false
                },
                "scrolled": true,
                "editable": false,
                "deletable": false
            },
            "outputs": [],
            "source": [
                "# tests for posterior_matrix\n",
                "assert round_matrix(casino_hmm.posterior_matrix('6')) == [[0.25], \n",
                "                                                          [0.75]]\n",
                "assert round_matrix(casino_hmm.posterior_matrix('1')) == [[0.62], \n",
                "                                                          [0.38]]\n",
                "assert round_matrix(casino_hmm.posterior_matrix('16')) == [[0.4, 0.36], \n",
                "                                                           [0.6, 0.64]]\n",
                "assert round_matrix(casino_hmm.posterior_matrix('165')) == [[0.48, 0.47, 0.54], \n",
                "                                                            [0.52, 0.53, 0.46]]\n",
                "assert round_matrix(casino_hmm.posterior_matrix('666661111')) == [\n",
                "    [0.04, 0.03, 0.04, 0.07, 0.16, 0.44, 0.6, 0.67, 0.7],\n",
                "    [0.96, 0.97, 0.96, 0.93, 0.84, 0.56, 0.4, 0.33, 0.3]]\n",
                "assert round_matrix(casino_hmm.posterior_matrix('4631262516')) == [\n",
                "    [0.56, 0.55, 0.64, 0.68, 0.68, 0.64, 0.69, 0.69, 0.66, 0.58],\n",
                "    [0.44, 0.45, 0.36, 0.32, 0.32, 0.36, 0.31, 0.31, 0.34, 0.42]]\n",
                "print(\"SUCCESS: posterior_matrix passed all tests!\")"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-a7c9ce69c92c343d",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "### Exploration activity: how does posterior decoding compare to Viterbi?\n",
                "\n",
                "Now that you have successfully implemented the Forward algorithm and the computation of posterior probabilties, try some simluations to see how posterior decoding compares to the Viterbi algorithm.  The method `posterior_decoding_path` is provided for you to perform posterior decoding, once you have successfully implemented the `posterior_matrix` method.\n",
                "\n",
                "Where do the two approaches differ?  Which approach has higher accuracy?"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": [
                "###\n",
                "### YOUR CODE HERE\n",
                "###\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "scrolled": false
            },
            "outputs": [],
            "source": [
                "###\n",
                "### YOUR CODE HERE\n",
                "###\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "###\n",
                "### Your thoughts here\n",
                "###\n"
            ]
        }
    ],
    "metadata": {
        "celltoolbar": "Create Assignment",
        "kernelspec": {
            "display_name": "Python 3 [3.6]",
            "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.6.4"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}