Hidden Markov Models.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hidden Markov Model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Hidden Marov Model HMM describes a time series as a hidden sequence of a finite number of states [1].\n",
    "\n",
    "![](https://upload.wikimedia.org/wikipedia/commons/8/8a/HiddenMarkovModel.svg)\n",
    "\n",
    "At each time point, the model estimates the probability $P(\\beta|\\alpha)$ of going from state $\\alpha$ to state $\\beta$. It is a Markov process as the knownledge about the past will not make the prediction of future states more or less accurate, but is only determined by the current state (1rst order Markov chain).\n",
    "\n",
    "The transition probabilities (how likely is to be in state j if we were in state i just before) are also estimated by the model.\n",
    "\n",
    ", where each state has its own model of the observed data (i.e., the observation model) and the probability of being at a given state at each time point depends on the state's assignment in the previous time point. \n",
    "\n",
    "The observation model that gives the name to the toolbox corresponds to a MAR model, which characterizes the behaviour of time series by linear historical interactions between the observed time series from different brain regions. In different words, a MAR model aims to predict the multichannel signal value at each time point as a linear combination of signal values at previous time points. MARs are able to characterize the frequency structure of the data, and by making the model multivariate, they are able to capture interactions (e.g., coherence) between multiple brain regions. Therefore, each state is related to a different set of multi-region autoregression coefficients describing the neural oscillations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mini forward algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ P(x_t) =  \\displaystyle\\sum\\limits_{x_{t-1}}P(x_t|x_ {t+1})P(x_{t-1}) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stationary distribution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The influence of the initial states tend to decrease over time and the final distribution is mostly independent of the initial one. Most of the Markov processes are end up with stationary distributions, which is the case when it satisfy:\n",
    "\n",
    "$$P_\\infty(X) = P_{\\infty+1}(X) = \\displaystyle\\sum\\limits_xP_{t+1|t}(X|x)P_\\infty(X)$$\n",
    "\n",
    "In other words, no matter how many states we add past infinity, the probability distribution will remain unchanged.\n",
    "\n",
    "If we want to think intuitively about that, there is only two way for this markov process to produce a *Sunny* state:\n",
    "- It can go from a rainny state to a sunny one.\n",
    "- It can go from a sunny state to another sunny state.\n",
    "\n",
    "Written formally, this gives:\n",
    "\n",
    "$$P_\\infty(SUN) = P_{t+1|t}(SUN|SUN)P_\\infty(SUN)+P_{t+1|t}(SUN|RAIN)P_\\infty(RAIN)$$\n",
    "$$P_\\infty(RAIN) = P_{t+1|t}(RAIN|SUN)P_\\infty(SUN)+P_{t+1|t}(RAIN|RAIN)P_\\infty(RAIN)$$\n",
    "\n",
    "Based on the previous transition probability matrice, we get:\n",
    "\n",
    "$$P_\\infty(SUN) = 0.9 * P_\\infty(SUN)+0.3 * P_\\infty(RAIN)$$\n",
    "$$P_\\infty(RAIN) = 0.1 * P_\\infty(SUN)+0.7 * P_\\infty(RAIN)$$\n",
    "\n",
    "Using linear algebra, we can then express these relation, also specifying that the sum of the probabilities must equal 1:\n",
    "\n",
    "$$x = 0.9x + 0.3y$$\n",
    "$$y = 0.1x + 0.7y$$\n",
    "$$x + y = 1$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.75, 0.25])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Solving linear equation\n",
    "a = np.array([[-0.1, 0.3], [1.1, 0.7]])\n",
    "b = np.array([0, 1])\n",
    "np.linalg.solve(a, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# References"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[1] https://en.wikipedia.org/wiki/Hidden_Markov_model\n",
    "\n",
    "[2] CS188 Artificial Intelligence UC Berkeley, Spring 2013. Prof. Pieter Abbeel. Retrieved from: https://www.youtube.com/watch?v=9dp4whVQv5s"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}