Hidden markov model tutorial

hmm_tutorial.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "A tutorial on hidden markov models",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "metadata": {
        "id": "WxOwdGpwIYpt",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# A tutorial on hidden markov models\n",
        "\n",
        "The following reviews the hidden markov model (HMM) model, the problems it addresses, its methodologies and applications.  The seminal paper on the model was published by Rabiner (1989) which reviews the mathematical foundations and specific application to speech recognition.  For decades, the model has been applied to numerous data best represented as a sequence such as protein and DNA sequences, natural language processing and handwriting recognition.\n",
        "\n",
        "First we will simulate an HMM process, generating emitted outcomes, generating train and test datasets.  Next, we will employ an implementation of the hmm model to fit our training data.  Finally we will evaluate the performance of our model using the test data. "
      ]
    },
    {
      "metadata": {
        "id": "5wBtQL1PLHz2",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Imports"
      ]
    },
    {
      "metadata": {
        "id": "aJhtkhb8LFJ8",
        "colab_type": "code",
        "outputId": "7479c2db-103a-46c3-82e4-3282a0e3f567",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 107
        }
      },
      "cell_type": "code",
      "source": [
        "!pip install hmmlearn\n",
        "!pip install sklearn\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "from hmmlearn import hmm\n",
        "from sklearn.model_selection import train_test_split\n",
        "from sklearn.model_selection import KFold"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Requirement already satisfied: hmmlearn in /usr/local/lib/python3.6/dist-packages (0.2.1)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.6/dist-packages (from hmmlearn) (1.14.6)\n",
            "Requirement already satisfied: scikit-learn>=0.16 in /usr/local/lib/python3.6/dist-packages (from hmmlearn) (0.19.2)\n",
            "Requirement already satisfied: sklearn in /usr/local/lib/python3.6/dist-packages (0.0)\n",
            "Requirement already satisfied: scikit-learn in /usr/local/lib/python3.6/dist-packages (from sklearn) (0.19.2)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "idkVjIf7LOON",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Data\n",
        "\n",
        "To generate data, we will simulate probably the simplist of models involving a hidden coin flipping experiment.  Rabiner (1989) sets up this experiment by imagining a man behind a curtain flipping a biased coin (i.e. p(H) != 0.5) from which we only see the outcome of the flips.\n",
        "\n",
        "```\n",
        "O: {H, H, H, T, T, ...}\n",
        "```\n",
        "\n",
        "The following models the underlying states of the experiment, heads or tails, with the probability of transition between them, p(H) and 1 - p(H), respectively.  The \"hidden\" aspect of the model is the p(H) which is unknown.\n",
        "\n",
        "## Coin Flip Model (Courtesy: Rabiner 1989)\n",
        "\n",
        "![coin flip experiment](https://docs.google.com/drawings/d/e/2PACX-1vTcnlcjrmCjHuhfpxpa0b6fHztPpa7QLe3AqBJUlVBSsTNS5mLURkT8JZOH1ThBo8SYS1id260KtilP/pub?w=131&h=83)\n",
        "\n"
      ]
    },
    {
      "metadata": {
        "id": "CMxvjzBtQuTE",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# constant size\n",
        "size = 10000\n",
        "# Set p(H) apriori for simulation as a biased coin.\n",
        "p_h = 0.7\n",
        "\n",
        "# Model experiment as a single biased coin flipped 1000 times.\n",
        "data = np.random.binomial(1, p_h, size=size)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "s9HRXqv9r2jg",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# HMM modeling and implementation\n",
        "\n",
        "To model the hidden transition state between a single coin flip, the `hmmlearn` library was employed.  The codebase for this library was originally part of the `sklearn` API but was subsequently transitioned into its own repository.  The reason for this is that its API deviates from that of `sklearn`.\n",
        "\n",
        "Briefly described, the `hmmlearn` library fits and predicts an HMM using either a Gaussian or Multinomial distributions.  As discussed in Rabiner (1989), an HMM solves the following two problems:\n",
        "\n",
        "1.   What is the most likely sequence of observations given a set of parameters.\n",
        "2.   What are the most likely parameters given a set of observations?\n",
        "\n",
        "`hmmlearn` solves the aforementioned problems with the `predict` and `fit` methods, respectively.  The `predict` method uses the Viterbi algorithm.  The `fit` method uses the EM algorithm.  These algorithms are reviewed in the Rabiner (1989) paper.  \n",
        "\n",
        "Note that we will be using the `sample` method as our prediction engine when evaluating the fit our of our model.  This is equivalent to the `predict` methods in operation as with other `sklearn` models.  The different nomenclature is probably one reason why the `hmmlearn` library was factored out of the original codebase.\n",
        "\n"
      ]
    },
    {
      "metadata": {
        "id": "mcWCQz1xrZI0",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Scoring methodology\n",
        "\n",
        "Before training and validating our model, it would be important to establish a scoring methodology to evalute the performance of the model.  Since we are modeling a categorical outcome, we will minimize: (E - O)^2 / E, where E and O are the expected and resulting count of getting heads, respectively.\n",
        "\n",
        "**A score of 0 indicates a perfect model fit**"
      ]
    },
    {
      "metadata": {
        "id": "p4onRhyNRYmH",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def score(expected: int, outcome: int) -> float:\n",
        "    return pow((expected - outcome), 2) / expected"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "54dOwAZdRouO",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# test score\n",
        "assert score(5,10) == 5"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "webDmvF-VRBW",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Split into test and train datasets."
      ]
    },
    {
      "metadata": {
        "id": "5AEYBogkVpj0",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "train, test = train_test_split(data, test_size=0.2)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "FUQvL5bEWr6K",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Train binomial hidden markov model with k-fold cross validation.\n",
        "\n",
        "Using k-fold cross validation, we find the transition state parameters that minimize the score using the aforementioned methodology."
      ]
    },
    {
      "metadata": {
        "id": "ZML0zGJSW3Nj",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "kf = KFold(n_splits=5)\n",
        "final_model = None\n",
        "p_h_est = []\n",
        "s_est = []\n",
        "min_s = float(\"inf\")\n",
        "\n",
        "for train_group, test_group in kf.split(train):\n",
        "  model = hmm.MultinomialHMM(n_components=2)\n",
        "  model.fit(train[train_group].reshape(-1,1))\n",
        "  expected = sum(train[test_group])\n",
        "  _, seq = model.sample(len(test_group))\n",
        "  outcome = sum(seq)\n",
        "  s = score(expected, outcome)\n",
        "  s_est.append(s)\n",
        "  p_h_est.append(model.transmat_[1][1])\n",
        "  if s < min_s:\n",
        "    min_s = s\n",
        "    final_model = model\n",
        "  \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "HWv11ZEReMi6",
        "colab_type": "code",
        "outputId": "11e7351f-3054-4a37-a0ce-1bb22694ba81",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 404
        }
      },
      "cell_type": "code",
      "source": [
        "# plot p(H) estimation vs score\n",
        "\n",
        "transmat = final_model.transmat_\n",
        "plt.scatter(p_h_est, s_est)\n",
        "plt.ylabel(\"Score\")\n",
        "plt.xlabel(\"p(H)\")\n",
        "_ = plt.title(\"HMM estimation of probability of heads.\\nMinimizes to p(H) = %.2f\" % transmat[1][1], fontsize=20)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfIAAAGDCAYAAADQ75K0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJzs3Xl0TPf/P/BnMpNFJCJhQhGqmFFk\nIyhii6jYKgTRENVqLUW11dqqdmqpWhJLaYtYQyRqT6po7T4qVbSaoqggmySTRSbb/f2R38w3I5PJ\nJDIZN56Pc5xj7r1z5zXvO5Pnve/3nXvNBEEQQERERKJkbuoCiIiIqPwY5ERERCLGICciIhIxBjkR\nEZGIMciJiIhEjEFOREQkYgxyEp2goCAoFApTl1HMi1pXSa5du4Z+/fqhZcuWGDt2rKnL0RIREQGF\nQoGIiIgKX7dCoUBQUJBBy3p7e8Pb21tvXc8u8yK4f/8+AgIC0KpVK/Tv37/E5S5evAiFQoGNGzdW\nYnWGe/DgARQKBaZPn27qUl5oDHITUP8x0PflSUxM1PkHR6FQQKFQ4LPPPtP7Gjdv3tQsW/SPjvq1\nFQoFzp07p3cdixcv1ixrKidPnsTx48e1pk2aNAmrV682UUWFXtS6ymLevHm4c+cOJk+ejJEjR5q6\nnBfSnDlzMGfOnDIv8+OPP+LixYvGLE2vFStW4Pfff8c777yDyZMnm6wOqhxSUxdAZSeVSnH8+HFk\nZGTA1tZW5zKRkZGQSCTIz88vcR0RERHo2LGjzvl5eXk4dOiQ3nVUhu+//x4NGjSAj4+PZlq7du1M\nVo/ai1pXWfz99994/fXXMWbMGFOX8sLq2rVruZZZtWoVBg0ahPbt2xujrFL9/fffcHBwwOeff26S\n16fKxSNyEWrdujWePn2Ko0eP6pyvDmE3Nze961DvDOhy+vRpJCcn612HsRUUFODGjRsme/2SvKh1\nlVVOTg5sbGxMXUaVk5ycjIcPH5q0Bm7blwuDXITq16+PZs2aYd++fTrnnzlzBklJSXrH7bp164an\nT5/iyJEjOudHRkaiSZMmaNSokcF1PX36FCtXrkSvXr3QqlUrtG3bFqNGjcKvv/5abNnjx48jKCgI\nHTt2hIuLC7p3745Zs2Zp/gBGRETg9ddfR1ZWFiIjI6FQKBAcHAyg+Fi0epxv3bp1+OWXX/DWW2/B\n1dUV3t7e2LFjB4DCHZNBgwbBzc0NPXr0wKpVq/Ds1Ynv3LmD6dOnw8vLCy1btoSXlxfGjBmDP/74\nQ7NMWeoCCkM/NDQUfn5+cHNzg5ubG9566y18//33yMvL0yynHgv84osv8M8//+D999+Hp6cnXF1d\nMXz4cFy/ft2gbZCWloYlS5bAx8cHrVq1Qps2bRAUFKQ1DBAcHKyp89KlS6WOGauHY3bs2IEDBw6g\nf//+cHFxQYcOHTBnzhytncGi2+K7775Dx44d8dFHH5Wpvmft27cP/fr1g4uLCzp27Ii5c+cW2wFV\nKpVYuXIl3nzzTbRq1Qrt2rXD0KFDcfjw4RLXe/v2bXzwwQdo06YN3N3dERQUpLWtAcPGv4suExwc\nrOnlCgkJgUKhwObNm+Hi4lLiWPWRI0egUCgQEhKi93VUKhVCQkLQp08fuLq6wsPDA0OGDMHevXs1\ny6i3VVxcHOLi4qBQKAwev798+TKGDRsGd3d3eHp6YvLkyXjy5Emx5cLDwzF48GC4ubnBw8MDAwcO\nxLZt21BQUKC1XE5ODjZu3Ih+/frB1dUVrVu3hp+fH3bs2KGzly80NFTzt6Nr165YsWIFcnNziy2X\nm5uLLVu2wM/PD56envDw8ECfPn2wZs0a5OTkGPReqxp2rYuUr68vgoODcffuXbz66qta8/bv3496\n9erBxcWlxOe3atUKzs7OiIiIwNChQ7XmKZVKnDx5Eu+//z4ePXpkUD05OTl499138eeff2Lw4MFw\ndXVFamoqwsPDMWbMGCxZsgR+fn4ACv9wffLJJ3Bzc8PEiRNhZ2eHO3fuIDQ0FGfOnMHhw4fRvn17\nzJkzB/PmzUO7du0wfPhwNG3aVG8Nf/75JyIiIjBixAhYWFhg06ZNmD9/PrKzs7F9+3YEBQXB1tYW\noaGhWL9+PRQKBXr37g0AiI+PR2BgIAoKCvDee++hfv36iI+Px7Zt2xAYGIhdu3bBxcWlzHXNmjUL\n+/btQ+fOnTFkyBBIJBL88ssvWLZsGf766y98/fXXWssnJCTg3XffRd++fdG3b1/ExsYiNDQU48aN\nw4kTJ2BpaVniaz19+hQjRozArVu3MGTIELi6uiIjIwMRERGYMGECFixYgKFDh6J3795o1qwZJk+e\njKZNm2LSpElwdHQsdRv//PPPuHfvHt5++23IZDKcPHkSu3fvxuPHj/Htt99qLfvHH3/gwYMH+Oyz\nz/DKK6+Uqb6ijh07hvv372PQoEFwcHDAqVOnsGvXLsTHx2P9+vWa5caMGYOrV68iMDAQbm5uyMzM\nRGRkJD799FMkJycXOwdAqVRi7Nix6NatG3x9fXHv3j1s27YNo0aNwqFDh1CvXr1S20OX3r17w8zM\nDMHBwfD19UXv3r3h4uKCa9eu4fDhw7h+/TpatWql9ZwjR47AzMxM8/3QpaCgAOPGjcO5c+fQt29f\njBo1Cjk5OTh27BhmzZqFBw8e4JNPPkH79u2xevVqzJs3D0Dh+H21atVKrfuff/7Brl27MHToUAQG\nBuL48eM4duwYpFIpVqxYoVluyZIl2Lx5M3r06IGAgADk5eXh5MmTWLhwIW7evIlFixZplp0+fToO\nHz6M/v374/3330dubi6ioqIwf/583L9/HzNmzNAsGxoaikWLFqF58+b4/PPPIZVKceLECVy7dq1Y\nrQsXLsTu3bvRt29fBAUFQSKR4H//+x/WrVuH2NjYUneIqiSBKt2+ffsEuVwurFmzRkhLS9P5786d\nO4JcLhdGjBih9Vy5XC5MmzZNuH//vqBQKIQVK1ZozVcqlYKLi4vwzTffCBcuXBDkcrmwb9++Yq99\n4cIFITg4WJDL5cKdO3e01rFr1y5BLpcL//77rzBt2jRBLpeX+p62bt0qyOVy4ciRI1rTMzIyhO7d\nuwvt27cXcnJyBEEQhHHjxglyuVxITk7WWvbXX38VRo8eLVy7dk0QBEH477//NO+3qBEjRmjVpH6f\nr7/+unDv3j3N9CNHjghyuVxo3ry5cOvWLc30q1evCnK5XPj88881006fPi2MHDlSOHjwYLGa5HK5\nMHPmTM00Q+v6/fffBblcLrz33ntCQUGB1rJjxowR5HK58Pvvv2utU1cbzpgxQ5DL5cK5c+cEfb79\n9ltBLpcLGzZs0Jqenp4udOrUSfD09BSys7M103V9vnRRf2ZcXFyEBw8eaM0LCgoS5HK58NdffwmC\n8H/bokWLFsWWLUt96tds166d1uekoKBACAwMFORyuRAbGysIgiA8fvxYGD16tLB06VKt9SqVSqFV\nq1aCj4+P1nR1O+/du1dr+p49ewS5XC4sWbJEM6179+5C9+7di7VF0e/Us8uo22DNmjWaaWfPnhXk\ncrkwf/58rdfMyMgQXFxchKCgIEGfw4cPC3K5XPjyyy+1pufm5gpvvfWW8PrrrwuPHz8usaaSqGt1\ncXER7t+/rzWvV69eQsuWLYW8vDxBEAThr7/+EuRyuTB37txi65k0aZIgl8uFGzduCIIgCCqVShg3\nbpzWd0xdb9euXQVXV1dBpVIJgiAIeXl5whtvvCG0adNGSElJ0SxbUFAgvPPOO8W+a61btxb69u1b\nrIZvv/1WmDBhgpCZmVnq+65q2LVuQiEhIWjbtq3Of76+vnqf6+zsjLZt2+LHH3/U6tI6cuQIVCqV\n3r17NT8/P5iZmSEyMlJr+v79++Hh4VHsSF+fI0eOwNbWFp06dYJSqdT8y8/PR7du3ZCSkoJ//vkH\nQOGJdgBw5coVrXV07twZ3333XbEjFkO1adMGDRs21Dxu3rw5AMDV1RVNmjQpNj0xMVEzzcvLC1u3\nbkW/fv0AAFlZWVAqlZojs7i4uDLX89NPPwEAhg0bBjMzM615gwYNAlB49ntRdevW1fQSqKl7VorW\nq8vx48dhZmaGgIAArem2trbo1asXlEplsTYvi06dOqF+/fpa0958800AwP/+979iNT+7bHnq69mz\np1ZvgZmZmea7oT4rvE6dOvjuu+8wdepUAIVd0EqlEoIgoE6dOjq3XbVq1fDWW29pTVMfTRvjbPMO\nHTqgQYMGOHTokFb374kTJ6BSqTSfh5IU/SwVJZVKMWDAAOTn5+scwjJU9+7d4ezsrDVNoVAgNzcX\nKSkpAKA5J6dPnz5a33GlUolevXoBKByqAQBLS0usX78ey5YtA1DYY6dUKpGVlQVnZ2dkZ2druu3/\n/vtvPHnyBF5eXqhZs6bm9XV9VtTvOT4+Hg8ePNCaPmbMGISEhLyU5wawa92Ehg4dqgmOZ6WlpWHS\npEl6nz9o0CBMnz4d586dg5eXF4DCEHZ3d0fjxo2RkJCg9/kNGjTQ7Ax8/PHHMDc3x7179xATE6Pp\nmjPU7du3kZGRgbZt25a4zMOHD9GiRQuMHj0ap0+fxsSJE9G6dWt07twZHTt2hKura7HAK4sGDRpo\nPbawsACAYoGi7p4uOkYNFO6MbN26FbGxscjKytKaV54z9+/cuQMAaNasWbF5jRs3BgDcvXtXa3rR\nHRE1KysrnfXqej2ZTKb1x/DZ1/v333/RoUOH0ovXQdf7cHJyAoBiJ3c92+blrU/Xa6oDp2hAX79+\nHSEhIYiJiUFqamqp7+XVV18tNkxha2uLmjVrGuVENTMzMwwaNAhr1qzByZMnNcF39OhRVK9eXfO4\nJOrPkq5hnJI+S2Wh61wYdZd8dnY2AODWrVsAgBEjRpS4nqJtd+/ePaxZswYXLlxAcnJysXNS1J/n\n//77r8Qaiu6Aq02YMAGLFi1C79690aVLF3Ts2BFeXl5lOp+nqmGQm5Czs3OJP08p7egLAHr16oX5\n8+cjIiICXl5euH//Pq5cuYK5c+caXIO/vz+mTZuGs2fPonPnzti/fz8sLS3Rp08fg9cBAJmZmahd\nuza++eabEpdRfynd3d2xb98+/PDDDzh+/Dh+++03rFq1Cg0aNMC0adM0R3llpQ7uZ+kbV1bbu3cv\nZs2ahVdeeQUTJ05E06ZNYW1tbdAOVUnUOwO6xiitra0BFI4bl7VWfa9Xq1YtnfPUOwPPvl5Z6DrS\nUf/88dmTjKpXr14h9elaj3pZlUoFAIiNjUVgYCCAwpBp3bo17OzsAADTpk3TeZ6HrvUC0GxzY/D3\n90dISAgiIyPRq1cvZGRk4PTp0+jfv3+p49hZWVmwsLDQ+fko6bNUFiV9d4rKzMwEAHzzzTeoXbu2\nzmVkMhmAwr9fAQEBSE1NRUBAADp16oQaNWrAzMwMy5cv1xr7Vtet73tS1MiRI9GkSROEhobi9OnT\nmhMlW7dujblz54rqokwVhUEuYjY2NvD19cXhw4eRnp6OH3/8scwh/Oabb2LevHmIjIyEl5cXfvzx\nR/To0QM1atQoUy3Vq1dHRkaGwb+bbdKkCRYtWoQFCxbg+vXr+Omnn7Bjxw589NFH2L59Ozw9Pcv0\n+s/rhx9+gEQiwebNmzVHOMD/HQmVhzr4nj26LzqtpEAp7+up/9g+S/3H8nleT1dQpKenAwAcHByM\nUp/6aFDXNPUf+R07dkClUmHRokUYPHiw1rIl9WKUFHpPnz7VGR4VoW7duvDy8sKZM2eQlpaGkydP\nIicnp9RudaCw7XJzc5GTk1MszI3xWdJFvX5nZ2e4urrqXTYyMhIpKSn48MMPi12QRiKRaD1Wt7d6\nx6woXd8doHCYp1OnTsjOzsalS5dw6NAhHDhwAO+88w6io6PL/PdL7DhGLnKDBg2CSqXCL7/8gkOH\nDqF79+6wt7c3+PnqnYFTp07h4sWLiIuLM2h8/VlNmzZFdnY2/vzzz2LzUlJSinWrqZmbm8PV1RVT\npkzB8uXLIQgCoqOjy/z6z+vBgweoW7euVogDhT/JKS91N2hsbGyxebdv3wYAvPbaa+Vev67XS0xM\n1PmTIXW3qK6uSkPp2qlRj1Oqu9gruj51OxV17949AP/Xxa6u4dkhg7t375bYs3Xv3r1iwyVKpRKp\nqanFxoor0pAhQ5Cbm4vo6GgcOnQIjRo1Mmin1ZDP0vNsW0Ooa9B1nkVmZqZWEJe0TdLS0oq9B/V5\nKOou9qJ0vd+irK2t0aVLFyxbtgzvvPMOUlJSNOP0LxMGuch5enqiYcOG2LVrF+7evYuBAweWeR3+\n/v7IzMxEcHAwateurRlvLwv1CVo//PCD1vScnBy899576N+/PwoKCpCdnY2hQ4di2rRpxdah7qZV\nH3Go99x17alXtNq1ayMlJUXrSO3Ro0fYtm0bAO0jQ0PrUo97hoWFae3ICIKAPXv2AEC5hxF0UZ8E\nFhYWpjU9JSUFUVFRkMlk8PDwKPf6z5w5g/j4eK1p6pOw2rRpY5T6oqKioFQqNY8FQcCxY8cAAG+8\n8QYAaLp5i46Zq1QqLFy4UHNk9uyRfUZGRrELKql/c17ecwjU9H0+unfvDkdHR4SFheH8+fMGf1/V\nbbd7926t6Tk5OYiMjISVlZVBV6F7Hurv+K5du4q15/Lly/HGG2/g/v37AHRvk4KCAixZskTTja9u\nn9dffx12dnY4c+aM1vUBCgoKtH4jDxSeC9GrVy/N96eoZ/9+AIU7Obp2EKoadq2LnPr3p2vWrEGt\nWrXQuXPnMq9DvTNw+fJlvPvuu5qzysti2LBhOHjwIA4ePAiVSoUePXogIyMD+/btw59//omFCxfC\n3Nwc1tbWaNmyJXbu3AmlUolu3bqhevXqiIuLw86dO2FjY6Ppaqxduzasra1x+vRpfPvtt2jUqFGp\nZ/OXV+/evfH9999j0qRJ6NevHxISEhAaGoqZM2fiq6++wl9//YVdu3ahW7duBtfVsmVLBAYGYufO\nnRg3bhy8vb2Rl5eHEydO4MKFC3j33Xchl8sr7D0EBgbiwIEDCA4ORkJCAlxdXfHkyROEh4cjPT0d\nq1evLte2VXN1dcWIESMwZMgQODk54eeff0ZMTAx8fX0NOhosT30tWrTA22+/jYEDB6JGjRqa1+zb\nt6+m96RPnz7Yv38/vvzyS4wePRp5eXkIDw+Hu7s77O3tcejQIaxevVpzgxigMDxWrlyJ69evQy6X\n486dO9i2bRvs7e0xfPjwcrcRUHiin5mZGQ4ePAgHBwcoFArNzrGFhQX8/Pzwww8/wNzc3ODeLx8f\nH3Tr1g179+6FSqVC+/btkZmZicOHD+POnTv44osvDBreeB7NmzfHO++8g61bt+Ltt99GQEAApFIp\nfvnlF0RHR+Ott97SnKzZq1cvrF+/HitWrEBmZiasrKxw8OBBVKtWDcOGDcO3336LjRs3YsiQIfD0\n9MR7772H1atXY9SoURgwYADMzc3x888/Fzsvo3nz5rCyssL8+fNx8+ZNtGrVChKJBDdv3sT27dvR\nrFkzzQ4eUPjZaNy4sWbnr6pikFcBAwcOREhICPr161fuP9QDBw7E6tWry9WtDhTuBW/ZsgUbN27E\nsWPHcPLkSVhYWKBly5YICQlBz549NcvOnj0br732Gvbv34+vv/4aWVlZcHR0RLt27TB+/HhNd7OF\nhQWmT5+OVatWYd26dRg6dKjRgnzSpEnIyclBdHQ05s2bh2bNmmHevHno0aMHsrKysGzZMnzzzTdo\n2rQpXnnlFYPrmj17Npo0aYI9e/Zg0aJFMDc3R9OmTbFw4UIMGTKkQt+DpaUlQkNDERISgujoaOzd\nuxfVqlWDm5sb5s+fr/cXBYbo1KkTGjRogI0bN+L27duws7NDUFAQpkyZYrT6hg0bhpSUFGzevBn/\n/fcfatSoUew1u3btijlz5mDr1q1YtGgR6tatiyFDhuC9997DX3/9hatXr2LHjh1wdHTUBHm9evUw\nZcoULF68GHv27EFBQQHc3d0xY8YMg4YJ9HnllVcwbtw4bNu2DSEhIZg0aZJWL9fAgQPxww8/oEOH\nDpqL5ZRGfZGZTZs24eDBgzh69CgsLS3RokULrF27Vuua/8Y0c+ZMNGvWDGFhYfjqq69QUFCAV199\nFZ9//jlGjRqlWU6hUGDVqlUICQnB8uXLUatWLfTt2xeTJk1CYmIiTp48qfnJqqenJ8aPHw+pVIqw\nsDAsXboUtWrVQp8+fTB27Fit826kUil27NiB9evX4+eff0ZkZCRyc3NRv359DB8+HOPGjXuuE0bF\nykwoafCSiAiFl/2cMWMGpkyZwhusVIBDhw5hypQplRrAVLVxjJyIqJJkZGQgODgYr7322gt3D3MS\nL3atExEZ2dWrVxEbG4vt27fj/v37CA0Nhbk5j6OoYjDIiYiMbN++fdi7dy8aNmyINWvWPPf5CkRF\ncYyciIhIxNi3Q0REJGIMciIiIhFjkFOVoFAoEBQUVK7nRkREQKFQICIiosLqefDgARQKBaZPn15h\n63wZLFiwAC4uLjov9WuoNWvWoFWrVvjtt98qsDKiFxeDnExOHaQKhQLnzp3Tu+zixYs1yxa1evXq\nct+lrH379li9erXBN3wxRK1atbB69ernvkqYsT1+/BjBwcGmLgNA4e+rt2/fjmnTpqFFixYAgKCg\nICgUCr13A9y4caPWjtikSZPg4eGBjz/+2Gh3MtMnMjIS/v7+cHd3h4eHB4KCgnDmzJkyreOXX37B\niBEj4OHhgbZt22LkyJE4f/58qc8LDw9/rp1aEicGOb0wpFKp3qPivLw8HDp0qNjdk4DCa1G3a9eu\nXK9bv359+Pr66ryHdnlVq1YNvr6+cHFxqbB1GsPZs2cREhJi6jKQmZmJBQsWwN3dXe/9rg1hZmaG\n+fPn48mTJ1i+fHkFVWiYdevWYfr06ahevTpmzZqF6dOnIzMzEx988AGioqIMWkd4eLjmwjtffPEF\nJk6ciAcPHuCDDz7AxYsXS3xeUlISli1bViHvg8SFQU4vjNatW+P48eNaN04o6vTp00hOToabm1sl\nV1Z1Fb0vtCnt2LEDqamp+PDDDytkfY0bN8Zbb72Fffv2ae6WZmwPHz7EunXr4O7ujs2bN2Pw4MEI\nCAhAaGgonJycMH/+fOTm5updR2JiIhYtWoSOHTsiNDQUgwcP1lzfvEaNGjh16lSJz120aBGsrKxK\nvFc4VV0McnphdOvWDU+fPsWRI0d0zo+MjESTJk3QqFGjYvOe7U4MDg6GQqHA5cuXER4ejr59+8LF\nxQUdOnTA7Nmzte5ypmuM3NvbGz179kRSUhImTZoET09PtG3bFh9//DHS09ORnJyMTz/9FO3atUP7\n9u3xwQcf4PHjx5rnPztGrn5c0r9nr/L15MkTLFy4EN7e3mjVqhXat2+P8ePH4+rVq1rLCYKAffv2\nYejQoWjfvj3c3NzQs2dPLF68uNRuZYVCgV27dmn+X7QGlUqFkJAQ9OnTB66urvDw8MCQIUOK3Y2q\nJOou8eTkZMybNw9eXl5wcXFBv379sH//fq1lCwoKEBoaitdee61C7+A1ZMgQFBQUFLvbmi4ZGRlQ\nKpV6/5W0g6l26NAh5ObmYvjw4Vq9Rra2tvDz80NSUhLOnj2rdx2RkZHIysrCxIkTtS4Y4+zsjHPn\nzum8ayAAnDp1CkeOHMHkyZNhZWVV6vulqoUXhKEXRqtWreDs7IyIiAgMHTpUa55SqcTJkyfx/vvv\n49GjRwavc8+ePbh69SoCAgJgZ2eHgwcPIiwsDNbW1pg5c6be5+bn5+PDDz+Eq6srZs6ciePHj+Po\n0aOwtrbG33//DTc3N8yYMQOXLl1CREQEZs+ejY0bN+pcl3rM/Fm//fYbQkNDtcb809LSMGzYMDx5\n8gQBAQFo1qwZEhISsGvXLgwfPhybNm3S3Gpz06ZNWLFiBby8vPDZZ5/B0tISf/75J3bs2IHLly9j\n3759MDMz01nT6tWrERwcjFu3bmH16tWoVq0agMJgHTduHM6dO4e+ffti1KhRyMnJwbFjxzBr1iw8\nePAAn3zyiUHt//nnn8Pa2hqTJ09GTk4OQkNDMW3aNFhbW2tuNPPXX38hMTERffr0MWidhnJzc9Pc\nHnPq1Kl6l33rrbe0brmpS/369XHixIkS56t7N3TdKlbdi3T16lV069atxHWcO3cO1atX16wjPz8f\n+fn5em8EkpmZiXnz5sHT0xP+/v5Yt26d3vdBVQ+DnF4ofn5+CA4Oxr///qu5TSUAHDlyBDk5ORgw\nYAA2bNhg8PrOnTuHo0ePws7ODkDhbQ27dOmC6OjoUoM8Li4OgwYNwsSJEwEA/fr1g5eXFyIjIzF2\n7Fh8+umnAArvZvXHH3/g7NmzyMnJ0flHVz1mXlRSUhIWLlyIV155BYsXL9ZMX7duHf777z/s3r1b\naxhhwIAB6Nu3L7766iscOHAAQOFRoK2tLTZu3Kg5ChwwYAAUCgWio6Px6NEj1KtXT+f78/X1xY4d\nOzT/Vzt27BjOnTuHgIAAzJ8/XzN92LBh8Pf3x6ZNmxAYGIg6derobT8AMDc31wqWLl26oFevXtiw\nYYPmNdUncem7D3hGRkaJR5ol3RdeIpGgXbt2OHHiBJ48eQJHR8cS1//NN9+Uen/50o501TsCutpF\nvQ1Kuzf2nTt30LBhQ/z111/46quvcOXKFeTn56NZs2YYP348+vbtW+w5K1euRGJiIr777rsSd9qo\namOQ0wvFz88PISEhiIyM1AQlAOzfvx8eHh549dVXy7S+wYMHa0IcAKpXr44mTZrgxo0bBj1/4MCB\nmv9bWlritddeQ0xMTLHbvTZv3hy3bt1CSkqKQQGXn5+PTz75BKmpqdixY4fWvaSPHDmCJk2aoHHj\nxlAqlZrp1apVg6enJ06ePIm0tDTY29tDKpUiKysLN2/e1NyiEwAGDRqkua97Wf30008ACoO7KKlU\nigEDBmDp0qX49ddfDboNa0BAgNZjZ2dnNG/eHDdu3EBGRgZsbW1x//59ANA5ZKJW3tvXNmrUCIIg\n4P79+3qD3N3dvVzrLyozMxMSiaTEHTn1MvqkpaVBKpVi7NixGDRoEEaPHo24uDhs3LgRn376KbKy\nsrTa/Y8//sCOHTswbtw4g+5cIp6OAAAgAElEQVQJT1UTg5xeKA0aNEDbtm3x448/4uOPP4a5uTnu\n3buHmJgYzJs3r8zra9iwYbFpVlZWyMvLK/W5Eomk2P2iLSwsNHXqml7ayUxqq1atwqVLl/Dll19q\nHXWnp6cjISEBCQkJeq/H/ejRI9jb22P8+PGYPHkyhgwZgg4dOqBTp07o1KlTsZ/nlcWdO3cAAE2b\nNi02T91LcvfuXYPWpWsdTk5OuHHjBh4+fAi5XI6UlBQA0NqZeVZwcDDs7e11zjt06BD27Nmjc16t\nWrUAQPMaL7rc3FzExcXh66+/Rv/+/TXTu3btij59+mDlypUYNGgQJBIJcnNz8cUXX6Bhw4YYP368\nCasmU2OQ0wvH398f06ZNw9mzZ9G5c2fs378flpaW5RpDfZ4TfyQSSYl3qNI3ZlmakydPYtOmTejT\np0+xn1qpj9iaN2+ut+tf/VO5nj17Yvfu3fjhhx/w66+/an6vLJfL8eWXX5brJ3lZWVmwsLDQ+R6t\nra0BQOtkQX1sbGyKTbO1tQUA5OTkAIDmJLKiPSfP8vDwgEwm0znv2RMAi6pRowaAwh0kfdLS0pCf\nn693GYlEUuLOBFDY25Ofn69zeCUrKwvA/733ktjY2CAnJ6dYF7qzszPat2+P06dP4/bt25DL5fju\nu+8QGxuLrVu3PtfnkcSPQU4vnDfffBPz5s1DZGQkvLy88OOPP6JHjx6aP8pi9uDBA0ybNg2NGzfG\nwoULi82vXr06gMIjM0MvUOPq6opVq1YhNzcXv//+O44dO4awsDCMHj0ahw8f1tkroY+NjQ1yc3P1\nBpK6ztJkZ2cXm6YObvURuDrc0tPT9R6Vl4d6aELfTgJQOITyvCe7OTs748aNG3j8+HGxNlevW9/w\ngfo1bt++rXOeunchIyMDd+/exfr169GrVy+8+uqrWr+YUO9MPH78GJaWlnqHFKhqYJDTC8fGxga+\nvr6IiorCxYsXERcXh9mzZ5u6rOeWk5ODyZMnIzc3F8HBwTrD0M7ODnXq1MG9e/eQnJys+eOtpu+k\nLQsLC7Rt2xZt27ZFo0aNsGjRIpw8eRLvvPNOmeps2rQpbt68idjYWLRq1UprnjpkDB2PvX37drHw\nevDgAczNzTW/d1aHd2pqaoUH+ZMnT7ReoyQVcbKbh4cHjh07hitXrhQLcvXlYtu0aaN3He7u7rh5\n8yZu3boFuVyuNe/hw4cAgLp16+LChQtQqVSIiorSeaGZx48fo2vXrmjXrh22bdum9zVJ/Pg7cnoh\n+fv7IzMzE8HBwahduza8vLxMXdJzW7RoEa5fv4758+frHDtW6927N/Ly8hAaGqo1PS0tDX5+fnj/\n/fcBAPHx8ejfvz9WrVpVbB3qo9zSulzVQwdFQ0x9Ytnu3bu1ls3JyUFkZCSsrKwM/r33s1fqu337\nNv755x+4uLhoglEdesa4cMu9e/dgZmYGZ2dnvcu5u7ujffv2ev+VdkJcv379YG1tjW3btmmdg5GS\nkoLIyEg0bNhQq5clISEBt2/f1mp79QmKISEhKHqH6Zs3b+Ly5ctQKBSoV68eOnbsiA0bNuj8V6tW\nLcjlcmzYsEHrhFGqunhETi8kT09PNGzYEJcvX8a7774LqVTcH9Xo6Gjs3r0bLVq0gIWFBY4dO1Zs\nmXbt2sHR0RHjx4/Hzz//jG+//RbJyclo27YtkpOTsXv3biQnJ2PkyJEACn/m9Morr2DDhg14+PAh\n2rVrBysrK/z777/Ytm0bZDIZevXqpbcu9Ul7c+bMwWuvvYZRo0bBx8cH3bp1w969e6FSqdC+fXtk\nZmbi8OHDuHPnDr744guDj5zT09MxYcIEdOnSBXl5edi8eTMAaJ2c9cYbbwAo/Bmavt9Yl1V+fj4u\nXbqEZs2aFevZMIbatWvjs88+w8KFC/Huu+/Cz88PKpUKO3bsQEZGBlauXKl1zsU333yDyMhIhIWF\naXYS3NzcEBQUhG3btmH8+PHw9fXFw4cPsXXrVkgkEnzxxRcACo/K69atq7MOa2tr1KxZE927dzf6\ne6YXg7j/OlKVNnDgQKxevbrYT73E6O+//wYA/Pnnn5g8ebLOZUJDQ9G+fXvUrFkTe/bswdq1a3Hy\n5Ens378f1apVg5ubGxYuXKh1AltISAg2bdqEY8eO4fjx41CpVKhTpw58fX3x4Ycfljo++v777+Pa\ntWs4dOgQZDIZRo4cCTMzMwQHB2PTpk04ePAgjh49CktLS7Ro0QJr166Fj4+Pwe974cKFCA0NRUhI\nCFJSUtC4cWOsXLlSK2RatGiB2rVrl/nGIqX5448/oFQqMXjw4Apdrz5BQUFwcHDAli1bMH/+fEgk\nEri7u2PBggVo3bq1Qev44osv0KRJE+zevRuzZ8+GpaUlWrdujYkTJ8LV1dXI74DEyEwo2n9DRFQB\ngoKCcOnSJZw5c6bEs82L2rhxI1asWIGNGzdW2GVaZ8yYgf379+Po0aNlvv4AkZhwjJyITG748OGo\nWbMm1q9fXyHr+/fff3HgwAH4+/szxKnKY5ATkclVr14dX375JWJiYrB9+/bnWpcgCJg9ezYcHBzw\n2WefVVCFRC8ujpET0QuhX79+iImJwdKlS9GmTRu8/vrr5VpPcHAwYmJisHXrVtSsWbOCqyR68XCM\nnIiISMTYtU5ERCRiouxaT0zUf93kF4mDgw1SUrJMXcZLi+1vetwGpsX2N62Kan+ZrOTLDPOI3Mik\nUompS3ipsf1Nj9vAtNj+plUZ7c8gJyIiEjEGORERkYgxyImIiESMQU5ERCRiDHIiIiIRY5ATERGJ\nGIOciIhIxBjkz0GVm4+ElCyocvNNXQoREb2kRHllN1PLLyhA2IlbiIlNxBOlCo41rOAhlyHAuykk\n5tw3IiKiysMgL4ewE7dw/PIDzeNkpUrzONBHbqqyiIjoJcTDxzJS5eYjJjZR57yY2CR2sxMRUaVi\nkJdRWoYKT5QqnfNS0rORlqF7HhERkTEwyMvI3tYKjjWsdM5zsLOGva3ueURERMbAIC8jKwsJPOQy\nnfM85LVhZcE7DRERUeXhyW7lEODdFEDhmHhKejYc7KzhIa+tmU5ERFRZGOTlIDE3R6CPHP5dmyAt\nQwV7WyseiRMRkUkwyJ+DlYUETg42pi6DiIheYhwjJyIiEjEGORERkYgZNchjY2Ph4+OD7du3a00/\nffo0FAqF5vGBAwfg7++PIUOGYO/evcYsiYiIqEox2hh5VlYWFixYgA4dOmhNV6lU2LhxI2QymWa5\ntWvXIjw8HBYWFhg8eDB69uyJmjVrGqs0IiKiKsNoR+SWlpbYtGkTnJyctKZv2LABgYGBsLS0BABc\nvXoVLi4usLOzg7W1NVq3bo0rV64YqywiIqIqxWhH5FKpFFKp9ur//fdf3Lx5E5MnT8by5csBAElJ\nSXB0dNQs4+joiMRE3dcyV3NwsIFUKp6fe8lkdqYu4aXG9jc9bgPTYvublrHbv1J/fvbVV19h1qxZ\nepcRBKHU9aSkZFVUSUYnk9khMTHd1GW8tNj+psdtYFpsf9OqqPbXtzNQaWetx8fH486dO/jss88w\ndOhQJCQkYMSIEXByckJSUpJmuYSEhGLd8URERKRbpR2R16lTB8ePH9c89vb2xvbt25GdnY1Zs2ZB\nqVRCIpHgypUrmDlzZmWVRUREJGpGC/Lr169j6dKliIuLg1QqRVRUFIKDg4udjW5tbY0pU6Zg9OjR\nMDMzw4QJE2Bnx/EcIiIiQ5gJhgxKv2DENN7D8SnTYvubHreBabH9TatKjZETERFRxWOQExERiRiD\nnIiISMQY5ERERCLGICciIhIxBjkREZGIMcjJqFS5+UhIyYIqN9/UpRARVUmVeq11ennkFxQg7MQt\nxMQm4olSBccaVvCQyxDg3RQSc+4/EhFVFAY5GUXYiVs4fvmB5nGyUqV5HOgjN1VZRERVDg+NqMKp\ncvMRE6v7VrQxsUnsZiciqkAMcqpwaRkqPFGqdM5LSc9GWobueUREVHYMcqpw9rZWcKxhpXOeg501\n7G11zyMiorJjkFOFs7KQwEMu0znPQ14bVhaSSq6IiKjq4sluZBQB3k0BFI6Jp6Rnw8HOGh7y2prp\nRERUMRjkZBQSc3ME+sjh37UJ0jJUsLe14pE4EZERMMjJqKwsJHBysDF1GUREVRbHyImIiESMQU5E\nRCRiDHIiIiIRY5ATERGJGIOciIhIxBjkREREIsYgJyIiEjEGORERkYgxyImIiESMQU5ERCRiDHIi\nIiIRY5ATERGJGIOciIhIxBjkREREImbUII+NjYWPjw+2b98OAHj06BFGjRqFESNGYNSoUUhMTAQA\nHDhwAP7+/hgyZAj27t1rzJKIiIiqFKMFeVZWFhYsWIAOHTpopq1atQpDhw7F9u3b0bNnT2zevBlZ\nWVlYu3YttmzZgm3btmHr1q1ITU01VllERERVitGC3NLSEps2bYKTk5Nm2pw5c9CrVy8AgIODA1JT\nU3H16lW4uLjAzs4O1tbWaN26Na5cuWKssoiIiKoUowW5VCqFtbW11jQbGxtIJBLk5+dj586d6N+/\nP5KSkuDo6KhZxtHRUdPlTkRERPpJK/sF8/PzMXXqVLzxxhvo0KEDDh48qDVfEIRS1+HgYAOpVGKs\nEiucTGZn6hJeamx/0+M2MC22v2kZu/0rPchnzJiBRo0aYeLEiQAAJycnJCUlaeYnJCTA3d1d7zpS\nUrKMWmNFksnskJiYbuoyXlpsf9PjNjAttr9pVVT769sZqNSfnx04cAAWFhb46KOPNNPc3Nxw7do1\nKJVKZGZm4sqVK/D09KzMsoiIiETLaEfk169fx9KlSxEXFwepVIqoqCgkJyfDysoKQUFBAIAmTZpg\n7ty5mDJlCkaPHg0zMzNMmDABdnbsBiIiIjKEmWDIoPQLRkzdROzWMi22v+lxG5gW29+0qlzXOhER\nEVUsBjkREZGIMciJiIhEjEFOREQkYgxyIiIiEWOQExERiRiDnIiISMQY5FRmqtx8JKRkQZWbb+pS\niIheepV+rXUSr/yCAoSduIWY2EQ8UargWMMKHnIZArybQmLOfUIiIlNgkJPBwk7cwvHLDzSPk5Uq\nzeNAH7mpyiIieqnxMIoMosrNR0ys7vvEx8QmsZudiMhEGORkkLQMFZ4oVTrnpaRnIy1D9zwiIjIu\nBjkZxN7WCo41rHTOc7Czhr2t7nlERGRcDHIyiJWFBB5ymc55HvLasLKQVHJFREQE8GQ3KoMA76YA\nCsfEU9Kz4WBnDQ95bc10IiKqfAxyMpjE3ByBPnL4d22CtAwV7G2teCRORGRiDHIqMysLCZwcbExd\nBhERgWPkREREosYgJyIiEjEGORERkYgxyImIiESMQU5ERCRiDHIiIiIRY5ATERGJGIOciIhIxBjk\nREREIsYgJyIiEjEGORERkYgxyImIiESMQU5ERCRiDHIiIiIRM2qQx8bGwsfHB9u3bwcAPHr0CEFB\nQQgMDMTkyZORk5MDADhw4AD8/f0xZMgQ7N2715glERERVSlGC/KsrCwsWLAAHTp00Exbs2YNAgMD\nsXPnTjRq1Ajh4eHIysrC2rVrsWXLFmzbtg1bt25FamqqscoiIiKqUowW5JaWlti0aROcnJw00y5e\nvIgePXoAALp3747z58/j6tWrcHFxgZ2dHaytrdG6dWtcuXLFWGURERFVKVKjrVgqhVSqvfqnT5/C\n0tISAFCrVi0kJiYiKSkJjo6OmmUcHR2RmJhorLKIiIiqFKMFeWkEQSjT9KIcHGwglUoquiSjkcns\nTF3CS43tb3rcBqbF9jctY7d/pQa5jY0NsrOzYW1tjfj4eDg5OcHJyQlJSUmaZRISEuDu7q53PSkp\nWcYutcLIZHZITEw3dRkvLba/6XEbmBbb37Qqqv317QxU6s/POnbsiKioKABAdHQ0OnfuDDc3N1y7\ndg1KpRKZmZm4cuUKPD09K7MsIiIi0TLaEfn169exdOlSxMXFQSqVIioqCl9//TWmT5+OsLAw1KtX\nD35+frCwsMCUKVMwevRomJmZYcKECbCzYzcQERGRIcwEQwalXzBi6iZit5Zpsf1Nj9vAtNj+plXl\nutaJiIioYjHIiYiIRIxBTkREJGIMciIiIhFjkBMREYkYg5yIiEjEGOREREQixiAnIiISMQY5ERGR\niDHIiYiIRIxBTkREJGIMciIiIhFjkBMREYkYg5yIiEjEGOREREQixiAnIiISMQY5ERGRiDHIiYiI\nRIxBTkREJGIMciIiIhFjkBMREYkYg5yIiEjEGOREREQixiAnIiISMQY5ERGRiDHIiYiIRIxBTkRE\nJGIMciIiIhEzOMhjY2Nx/PhxAIBSqTRaQURERGQ4qSELbdmyBYcOHUJOTg58fHywbt061KhRAx9+\n+KGx6yMiIiI9DDoiP3ToEPbs2QN7e3sAwNSpU3Hq1Clj1kVEREQGMOiIvHr16jA3/7/MNzc313ps\nqMzMTEybNg1paWnIzc3FhAkTIJPJMHfuXACAQqHAvHnzyrxeIiKil5VBQd6wYUOEhIRAqVQiOjoa\nR44cQZMmTcr8YpGRkWjcuDGmTJmC+Ph4vPPOO5DJZJg5cyZcXV0xZcoU/PLLL+jatWuZ101ERPQy\nMuiwevbs2ahWrRrq1KmDAwcOwM3NDXPmzCnzizk4OCA1NRVA4QlzNWvWRFxcHFxdXQEA3bt3x/nz\n58u8XiIiopeVmSAIQmkL7du3D/7+/hXygqNHj8b9+/ehVCqxfv16zJ8/H/v37wcAnD9/HuHh4Vix\nYoXedeTl5UMqlVRIPURERGJmUNf6Tz/9hDfffBN2dnbP9WI//vgj6tWrh++//x43b97EhAkTtNZp\nwD4FACAlJeu56qhMMpkdEhPTTV3GS4vtb3rcBqbF9jetimp/mazk/DUoyLOzs+Ht7Y3GjRvDwsJC\nM33Hjh1lKuTKlSvw8vICADRv3hwqlQp5eXma+fHx8XBycirTOomIiF5mBgV5Rf1evFGjRrh69Sp6\n9eqFuLg4VK9eHfXr18fly5fh6emJ6OhoBAUFVchrERERvQwMCvJ27drh8uXLuHbtGszMzODm5gYP\nD48yv1hAQABmzpyJESNGIC8vD3PnzoVMJsPs2bNRUFAANzc3dOzYsczrJSIielkZdLLb6tWrcfbs\nWbRp0wYAcOnSJbz55psYO3as0QvURUzjPRyfMi22v+lxG5gW29+0Xpgx8osXL2L37t2ai8Dk5eVh\nxIgRJgtyIiIiKmTQ78gLCgq0ruQmlUphZmZmtKKIiIjIMAYdkbdq1Qrjxo3TjF+fO3cOLi4uRi2M\niIiISmdQkM+cORNHjx7F1atXYWZmhgEDBsDX19fYtREREVEpDP4duZmZGWbOnAkA2LVrF7KyslC9\nenWjFkdERET6GTRGPm3aNCQlJWkeZ2dnY+rUqUYrioiIiAxjUJCnpqZi5MiRmsfvvvsulEql0Yoi\nIiIiwxgU5Lm5ubh9+7bm8fXr15Gbm2u0ooiIiMgwBo2Rz5gxAx9++CHS09NRUFAABwcHLFu2zNi1\nERERUSn0HpFnZGRgy5YtcHNzQ1RUFEaMGAGZTIZmzZrhlVdeqawaiYiIqAR6g3z27NlITk4GAPz7\n77/YsmULZs6ciU6dOmHRokWVUiARERGVTG+Q//fff5gyZQoAICoqCr6+vujQoQMCAgK0zmInIiIi\n09Ab5DY2Npr/X7p0CW+88YbmMS/RSkREZHp6gzw/Px/Jycm4f/8+YmJi0KlTJwBAZmYmnj59WikF\nEhERUcn0nrX+wQcfoE+fPsjOzsbEiRNhb2+P7OxsBAYGYujQoZVVIxEREZVAb5B37doVZ86cgUql\ngq2tLQDA2toan3/+Oby8vCqlQCIiIipZqb8jt7CwgIWFhdY0hjgREdGLwaAruxEREdGLiUFOREQk\nYgxyIiIiEWOQExERiRiDnIiISMQY5ERERCLGICciIhIxBjkREZGIMciJiIhEjEFOREQkYgxyIiIi\nEWOQExERiRiDnIiISMRKvftZRTtw4AC+++47SKVSfPTRR1AoFJg6dSry8/Mhk8mwfPlyWFpaVnZZ\nREREolSpR+QpKSlYu3Ytdu7ciQ0bNuDnn3/GmjVrEBgYiJ07d6JRo0YIDw+vzJKIiIhErVKD/Pz5\n8+jQoQNsbW3h5OSEBQsW4OLFi+jRowcAoHv37jh//nxllkRUYVS5+UhIyYIqN9/UpRDRS6RSu9Yf\nPHiA7OxsjBs3DkqlEpMmTcLTp081Xem1atVCYmJiZZZE9NzyCwoQduIWYmIT8USpgmMNK3jIZQjw\nbgqJOU9DISLjqvQx8tTUVISEhODhw4cYOXIkBEHQzCv6f30cHGwglUqMVWKFk8nsTF3CS83Y7b9p\n/zUcv/xA8zhZqcLxyw9gU80SH/i5GPW1xYLfAdNi+5uWsdu/UoO8Vq1a8PDwgFQqRcOGDVG9enVI\nJBJkZ2fD2toa8fHxcHJyKnU9KSlZlVBtxZDJ7JCYmG7qMl5axm5/VW4+zl6N0znv7NWH6N3OGVYW\n4tnpNAZ+B0yL7W9aFdX++nYGKrXfz8vLCxcuXEBBQQFSUlKQlZWFjh07IioqCgAQHR2Nzp07V2ZJ\nRM8lLUOFJ0qVznkp6dlIy9A9j4ioolTqEXmdOnXQq1cvDB06FAAwa9YsuLi4YNq0aQgLC0O9evXg\n5+dXmSURPRd7Wys41rBCso4wd7Czhr2tlQmqIqKXSaWPkQ8bNgzDhg3TmrZ58+bKLoOoQlhZSOAh\nl2mNkat5yGu/9N3qRGR8lR7kRFVNgHdTAEBMbBJS0rPhYGcND3ltzXQiImNikBM9J4m5OQJ95PDv\n2gRpGSrY21rxSJyIKg2DnKiCWFlI4ORgY+oyiOglw6tVEBERiRiDnIiISMQY5ERERCLGICciIhIx\nBjkREZGIMciJiIhEjEFOREQkYgxyIiIiEWOQExERiRiDnIiISMQY5ERERCLGICciIhIxBjkREZGI\nMciJiIhEjEFOREQkYgxyIiIiEWOQExERiRiDnIiISMQY5ERERCLGICciIhIxBjkREZGIMciJiIhE\njEFOREQkYgxyIiIiEWOQExERiRiDnIiISMQY5ERERCLGICciIhIxkwR5dnY2fHx8EBERgUePHiEo\nKAiBgYGYPHkycnJyTFESERGRKJkkyNevXw97e3sAwJo1axAYGIidO3eiUaNGCA8PN0VJREREolTp\nQX779m3cunUL3bp1AwBcvHgRPXr0AAB0794d58+fr+ySiIiIRKvSg3zp0qWYPn265vHTp09haWkJ\nAKhVqxYSExMruyQiIiLRklbmi+3fvx/u7u5wdnbWOV8QBIPW4+BgA6lUUpGlGZVMZmfqEl5qbH/T\n4zYwLba/aRm7/Ss1yE+dOoX//vsPp06dwuPHj2FpaQkbGxtkZ2fD2toa8fHxcHJyKnU9KSlZlVBt\nxZDJ7JCYmG7qMl5abH/T4zYwLba/aVVU++vbGajUIF+1apXm/8HBwahfvz5iYmIQFRWFAQMGIDo6\nGp07d67MkoiIiETN5L8jnzRpEvbv34/AwECkpqbCz8/P1CURERGJRqUekRc1adIkzf83b95sqjKI\niIhEzeRH5ERERFR+DHIiIiIRY5ATERGJGIOciIhIxBjkREREIsYgJyIiEjEGORERkYgxyImIiESM\nQU5ERCRiDHIiIiIRY5ATERGJGIOciIhIxBjkREREIsYgJyIiEjEGORERkYgxyImIiESMQU5ERCRi\nDHIiIiIRY5ATERGJGIOciIhIxBjkREREIsYgJyIiEjEGORERkYgxyImIiESMQU5ERCRiDHIiIiIR\nY5ATERGJGIOciIhIxBjkREREIsYgJyIiEjEGORERkYhJK/sFly1bht9++w15eXkYO3YsXFxcMHXq\nVOTn50Mmk2H58uWwtLSs7LKIiIhEqVKD/MKFC/jnn38QFhaGlJQUDBw4EB06dEBgYCB69+6Nb775\nBuHh4QgMDKzMsoiIiESrUrvW27Zti9WrVwMAatSogadPn+LixYvo0aMHAKB79+44f/58ZZZEREQk\napV6RC6RSGBjYwMACA8PR5cuXXDmzBlNV3qtWrWQmJhY6nocHGwglUqMWmtFksnsTF3CS43tb3rc\nBqbF9jctY7d/pY+RA8Dx48cRHh6OH374AW+++aZmuiAIBj0/JSXLWKVVOJnMDomJ6aYu46XF9jc9\nbgPTYvubVkW1v76dgUo/a/306dPYsGEDNm3aBDs7O9jY2CA7OxsAEB8fDycnp8ouiYiISLQqNcjT\n09OxbNkyfPvtt6hZsyYAoGPHjoiKigIAREdHo3PnzpVZEhERkahVatf6kSNHkJKSgo8//lgzbcmS\nJZg1axbCwsJQr149+Pn5VWZJREREomYmGDow/QIR03gPx6dMi+1vetwGpsX2N60qOUZOREREFYdB\nTkREJGIMciIiIhFjkBMREYkYg5yIiEjEGOREREQixiAnIiISMQY5ERGRiDHIiYiIRIxBTkREJGIM\nciIiIhFjkBMREYkYg5yIiEjEGORERETPUOXmIyElC6rcfFOXUqpKvR85ERHRiyy/oABhJ24hJjYR\nT5QqONawgodchgDvppCYv5jHvgxyIiKi/y/sxC0cv/xA8zhZqdI8DvSRm6osvV7M3QsiIqJKpsrN\nR0xsos55MbFJL2w3O4OciIgIQFqGCk+UKp3zUtKzkZahe56pMciJiIgA2NtawbGGlc55DnbWsLfV\nPc/UGOREREQArCwk8JDLdM7zkNeGlYWkkisyDE92IyIi+v8CvJsCKBwTT0nPhoOdNTzktTXTX0QM\nciIiov9PYm6OQB85/Ls2QVqGCva2Vi/skbgag5yIiOgZVhYSODnYmLoMg3CMnIiISMQY5ERERCLG\nICciIhIxBjkREZGIMciJiIhEjEFOREQkYgxyIiIiEWOQExERiZiZIAiCqYsgIiKi8uERORERkYgx\nyImIiESMQU5ERCRiDE+c2toAAAXGSURBVHIiIiIRY5ATERGJGIOciIhIxHg/8ue0ePFiXL16FWZm\nZpg5cyZcXV2LLbNixQr8/vvv2LZtGy5evIjJkyejWbNmAAC5XI4vv/yyssuuMvS1v7e3N+rWrQuJ\nRAIA+Prrr1GnTh2DthkZpqztf/fuXX7+K5C+9n/06BE+/fRT5ObmokWLFpg/f36pz6GyK+s2MEoG\nCFRuFy9eFMaMGSMIgiDcunVLGDp0aLFl/vnnHyEgIEAYMWKEIAiCcOHCBWHSpEmVWmdVVVr7d+/e\nXcjIyCjTc8hw5Wl/fv4rTmnt/9FHHwnR0dGCIAjC3Llzhbi4OH7+K1h5toExvgPsWn8O58+fh4+P\nDwCgSZMmSEtLQ0ZGhtYyS5YswSeffGKK8qo8Q9q/Ip5DurEtTUtf+xcUFOC3336Dt7c3AGDOnDmo\nV68et1kFK882MAYG+XNISkqCg4OD5rGjoyMSExM1jyMiItCuXTvUr19f63m3bt3CuHHj8Pbbb+Ps\n2bOVVm9VU1r7A4Vfnrfffhtff/01BEEw6DlkmPK0P8DPf0XR1/5PnjxB9erV8dVXX+Htt9/GihUr\nSn0OlV15tgFQ8d8BjpFXIKHI1W5TU1MRERGBzZs3Iz4+XjP91VdfxcSJE9G7d2/8999/GDlyJKKj\no2FpaWmKkqsU4ZmrDX/00Ufo3Lkz7O3tMWHCBERFRZX6HCo/Q9rfw8ODn38jKdr+giAgPj4eI0eO\nRP369TFmzBicOnVK73Po+RmyDV5//fUK/w7wiPw5ODk5ISkpSfM4ISEBMpkMAHDhwgU8efIEw4cP\nx8SJE3Hjxg0sXrwYderUQZ8+fWBmZoaGDRuidu3aWkFPhtPX/gDg5+eHWrVqQSqVokuXLoiNjS31\nOWS48rQ/P/8VR1/7Ozg4oF69emjYsCEkEgk6dOiAf/75h5//ClaebWCM7wCD/Dl06tRJc5R348YN\nODk5wdbWFgDg6+uLI0eOYM+ePQgJCUHLli0xc+ZMHDhwAN9//z0AIDExEcnJyahTp47J3oOY6Wv/\n9PR0jB49Gjk5OQCA//3vf2jWrJne51DZlKf9+fmvOPraXyqVwtnZGXfv3tXMb9y4MT//Faw828AY\n3wF2rT+H1q1bo2XLlhg2bBjMzMwwZ84cREREwM7ODj179tT5HG9vb3z22Wf4+eefkZubi7lz57Jb\nsZxKa/8uXbogICAAVlZWaNGiBXx9fWFmZlbsOVQ+5Wn/zMxMfv4rSGntP3PmTEyfPv3/tXeHrqlG\ncRjHnxkWDGIRBI1isQkrshWT/gcaLILNpgiyvDZFWFgZaNNkfQ1romIwimCwCTLbyxRM3iB7uRP1\nei/Ty4Hvp53Xw48fvL48nBPO0Xa7VTgcVjwel8vl4v//g/7lHazX6x//BrjGFAAAg7G1DgCAwQhy\nAAAMRpADAGAwghwAAIMR5AAAGIwgB3BSuVxWp9NRu91WsVj89ttwOFQ6nZZt20qlUhzuAvwHBDmA\noyzL0mazUSKRODnP4/Eon8/r8fHxSp0B+EKQA3BW1oVCQalUSrlcTp+fn3p9fVU2mz2rxv39vZbL\npSaTyYW7BfA7ghyApN0RkqVSSa1WS16vV41GQ8vlUpFI5OwasVhM3W73gl0C2McRrQAkSaFQyDnz\nORqNyrIs+f1+3dzcOHP6/b4ymYwztm1bbrfbGQcCAU2n0+s1DYAgB7CzfwXjofOfY7GYnp+fnfFw\nOFStVrtKfwAOY2sdgCRpNpvp4+NDkjQajXR3d6fFYvFXNebzuYLB4CXaA3AEQQ5A0m5rvVqtKp1O\na7VaKZPJyOfzaTwen11jMBjo4eHhgl0C2MftZwCcLfJms/ntuWVZen9/V6VS+WONXq+ner2ut7e3\nS7UJ4ABW5ACOSiaTur29VafTOTnPtm29vLzo6enpSp0B+MKKHAAAg7EiBwDAYAQ5AAAGI8gBADAY\nQQ4AgMEIcgAADEaQAwBgsF+y8i58eL7z9AAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<matplotlib.figure.Figure at 0x7fe65f3ca550>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "metadata": {
        "id": "ek89ecPhZ4Zn",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Evaluate on the test dataset.\n"
      ]
    },
    {
      "metadata": {
        "id": "2y-vPWCkbLU2",
        "colab_type": "code",
        "outputId": "95e2f917-d40c-468a-8c5f-af43864afa68",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "cell_type": "code",
      "source": [
        "_, seq = final_model.sample(len(test))\n",
        "outcome = sum(seq)\n",
        "expected = sum(test)\n",
        "print(score(expected, outcome))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "9.99364855328158\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "apjKsI9ecNRq",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Conclusion\n",
        "\n",
        "We witnessed even with a simple coin flip experiment a local minimum solution when modeling the transition state probability.  The simulation of a random binomial where the p(H) = 0.7, minimized to ~0.6 when emplying the hmm implementation.  Subsequent improvements to modeling sequential data were developed since the 1989 publication."
      ]
    },
    {
      "metadata": {
        "id": "WO1f9ednHt-6",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# References\n",
        "\n",
        "L. R. Rabiner, \"A tutorial on hidden Markov models and selected applications in speech recognition,\" in Proceedings of the IEEE, vol. 77, no. 2, pp. 257-286, Feb. 1989."
      ]
    },
    {
      "metadata": {
        "id": "K_HHHm-hIpM6",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}