{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.random.seed(2017)\n",
    "\n",
    "import torch\n",
    "torch.manual_seed(2017)\n",
    "\n",
    "from scipy.misc import logsumexp # Use it for reference checking implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Emissions:\n",
      "[[  9.   6.]\n",
      " [ 13.  10.]\n",
      " [  8.  18.]\n",
      " [  3.  15.]]\n",
      "Transitions:\n",
      "[[ 7.  8.]\n",
      " [ 0.  8.]]\n"
     ]
    }
   ],
   "source": [
    "seq_length, num_states=4, 2\n",
    "emissions = np.random.randint(20, size=(seq_length,num_states))*1.\n",
    "transitions = np.random.randint(10, size=(num_states, num_states))*1.\n",
    "print(\"Emissions:\", emissions, sep=\"\\n\")\n",
    "print(\"Transitions:\", transitions, sep=\"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def viterbi_decoding(emissions, transitions):\n",
    "    # Use help from: https://github.com/tensorflow/tensorflow/blob/master/tensorflow/contrib/crf/python/ops/crf.py\n",
    "    scores = np.zeros_like(emissions)\n",
    "    back_pointers = np.zeros_like(emissions, dtype=\"int\")\n",
    "    scores = emissions[0]\n",
    "    # Generate most likely scores and paths for each step in sequence\n",
    "    for i in range(1, emissions.shape[0]):\n",
    "        score_with_transition = np.expand_dims(scores, 1) + transitions\n",
    "        scores = emissions[i] + score_with_transition.max(axis=0)\n",
    "        back_pointers[i] = np.argmax(score_with_transition, 0)\n",
    "    # Generate the most likely path\n",
    "    viterbi = [np.argmax(scores)]\n",
    "    for bp in reversed(back_pointers[1:]):\n",
    "        viterbi.append(bp[viterbi[-1]])\n",
    "    viterbi.reverse()\n",
    "    viterbi_score = np.max(scores)\n",
    "    return viterbi_score, viterbi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(78.0, [0, 0, 1, 1])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viterbi_decoding(emissions, transitions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def viterbi_decoding_torch(emissions, transitions):\n",
    "    scores = torch.zeros(emissions.size(1))\n",
    "    back_pointers = torch.zeros(emissions.size()).int()\n",
    "    scores = scores + emissions[0]\n",
    "    # Generate most likely scores and paths for each step in sequence\n",
    "    for i in range(1, emissions.size(0)):\n",
    "        scores_with_transitions = scores.unsqueeze(1).expand_as(transitions) + transitions\n",
    "        max_scores, back_pointers[i] = torch.max(scores_with_transitions, 0)\n",
    "        scores = emissions[i] + max_scores\n",
    "    # Generate the most likely path\n",
    "    viterbi = [scores.numpy().argmax()]\n",
    "    back_pointers = back_pointers.numpy()\n",
    "    for bp in reversed(back_pointers[1:]):\n",
    "        viterbi.append(bp[viterbi[-1]])\n",
    "    viterbi.reverse()\n",
    "    viterbi_score = scores.numpy().max()\n",
    "    return viterbi_score, viterbi\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(78.0, [0, 0, 1, 1])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viterbi_decoding_torch(torch.Tensor(emissions), torch.Tensor(transitions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(78.0, [0, 0, 1, 1])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viterbi_decoding(emissions, transitions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def log_sum_exp(vecs, axis=None, keepdims=False):\n",
    "    ## Use help from: https://github.com/scipy/scipy/blob/v0.18.1/scipy/misc/common.py#L20-L140\n",
    "    max_val = vecs.max(axis=axis, keepdims=True)\n",
    "    vecs = vecs - max_val\n",
    "    if not keepdims:\n",
    "        max_val = max_val.squeeze(axis=axis)\n",
    "    out_val = np.log(np.exp(vecs).sum(axis=axis, keepdims=keepdims))\n",
    "    return max_val + out_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def score_sequence(emissions, transitions, tags):\n",
    "    # Use help from: https://github.com/tensorflow/tensorflow/blob/master/tensorflow/contrib/crf/python/ops/crf.py\n",
    "    score = emissions[0][tags[0]]\n",
    "    for i, emission in enumerate(emissions[1:]):\n",
    "        score = score + transitions[tags[i], tags[i+1]] + emission[tags[i+1]]\n",
    "    return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42.0"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "score_sequence(emissions, transitions, [1,1,0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7.0, 8.0, 8.0]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "correct_seq = [0, 0, 1, 1]\n",
    "[transitions[correct_seq[i],correct_seq[i+1]] for i in range(len(correct_seq) -1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23.0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([transitions[correct_seq[i], correct_seq[i+1]] for i in range(len(correct_seq) -1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(78.0, [0, 0, 1, 1])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "viterbi_decoding(emissions, transitions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "78.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "score_sequence(emissions, transitions, [0, 0, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def score_sequence_torch(emissions, transitions, tags):\n",
    "    score = emissions[0][tags[0]]\n",
    "    for i, emission in enumerate(emissions[1:]):\n",
    "        score = score + transitions[tags[i], tags[i+1]] + emission[tags[i+1]]\n",
    "    return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "78.0"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "score_sequence_torch(torch.Tensor(emissions), torch.Tensor(transitions), [0, 0, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0, 0, 0],\n",
       " [1, 0, 0, 0],\n",
       " [0, 1, 0, 0],\n",
       " [1, 1, 0, 0],\n",
       " [0, 0, 1, 0],\n",
       " [1, 0, 1, 0],\n",
       " [0, 1, 1, 0],\n",
       " [1, 1, 1, 0],\n",
       " [0, 0, 0, 1],\n",
       " [1, 0, 0, 1],\n",
       " [0, 1, 0, 1],\n",
       " [1, 1, 0, 1],\n",
       " [0, 0, 1, 1],\n",
       " [1, 0, 1, 1],\n",
       " [0, 1, 1, 1],\n",
       " [1, 1, 1, 1]]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_all_tags(seq_length, num_labels):\n",
    "    if seq_length == 0:\n",
    "        yield []\n",
    "        return\n",
    "    for sequence in get_all_tags(seq_length-1, num_labels):\n",
    "        #print(sequence, seq_length)\n",
    "        for label in range(num_labels):\n",
    "            yield [label] + sequence        \n",
    "list(get_all_tags(4,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0], [0, 1], [1, 0], [1, 1]]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_all_tags_dp(seq_length, num_labels):\n",
    "    prior_tags = [[]]\n",
    "    for i in range(1, seq_length+1):\n",
    "        new_tags = []\n",
    "        for label in range(num_labels):\n",
    "            for tags in prior_tags:\n",
    "                new_tags.append([label] + tags)\n",
    "        prior_tags = new_tags\n",
    "    return new_tags\n",
    "list(get_all_tags_dp(2,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[54.0, 67.0, 58.0, 78.0, 45.0, 58.0, 56.0, 76.0, 44.0, 57.0, 48.0, 68.0, 42.0, 55.0, 53.0, 73.0]\n"
     ]
    }
   ],
   "source": [
    "def brute_force_score(emissions, transitions):\n",
    "    # This is for ensuring the correctness of the dynamic programming method.\n",
    "    # DO NOT run with very high values of number of labels or sequence lengths\n",
    "    for tags in get_all_tags_dp(*emissions.shape):\n",
    "        yield score_sequence(emissions, transitions, tags)\n",
    "\n",
    "        \n",
    "brute_force_sequence_scores = list(brute_force_score(emissions, transitions))\n",
    "print(brute_force_sequence_scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "78.0"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(brute_force_sequence_scores) # Best score calcuated using brute force"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "78.132899613126483"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "log_sum_exp(np.array(brute_force_sequence_scores)) # Partition function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def forward_algorithm_naive(emissions, transitions):\n",
    "    scores = emissions[0]\n",
    "    # Get the log sum exp score\n",
    "    for i in range(1,emissions.shape[0]):\n",
    "        print(scores)\n",
    "        alphas_t = np.zeros_like(scores) # Forward vars at timestep t\n",
    "        for j in range(emissions.shape[1]):\n",
    "            emit_score = emissions[i,j]\n",
    "            trans_score = transitions.T[j]\n",
    "            next_tag_var = scores + trans_score\n",
    "            alphas_t[j] = log_sum_exp(next_tag_var) + emit_score\n",
    "        scores = alphas_t\n",
    "    return log_sum_exp(scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 9.  6.]\n",
      "[ 29.0000454   27.04858735]\n",
      "[ 44.00017494  55.13288499]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "78.132899613126483"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "forward_algorithm_naive(emissions, transitions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def forward_algorithm_vec_check(emissions, transitions):\n",
    "    # This is for checking the correctedness of log_sum_exp function compared to scipy\n",
    "    scores = emissions[0]\n",
    "    scores_naive = emissions[0]\n",
    "    # Get the log sum exp score\n",
    "    for i in range(1, emissions.shape[0]):\n",
    "        print(scores, scores_naive)\n",
    "        scores = emissions[i] + logsumexp(\n",
    "            scores_naive + transitions.T,\n",
    "            axis=1)\n",
    "        scores_naive = emissions[i] + np.array([log_sum_exp(\n",
    "            scores_naive + transitions.T[j]) for j in range(emissions.shape[1])])\n",
    "    print(scores, scores_naive)\n",
    "    return logsumexp(scores), log_sum_exp(scores_naive)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 9.  6.] [ 9.  6.]\n",
      "[ 29.0000454   27.04858735] [ 29.0000454   27.04858735]\n",
      "[ 44.00017494  55.13288499] [ 44.00017494  55.13288499]\n",
      "[ 58.14879707  78.13289961] [ 58.14879707  78.13289961]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(78.132899613126483, 78.132899613126483)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "forward_algorithm_vec_check(emissions, transitions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def forward_algorithm(emissions, transitions):\n",
    "    scores = emissions[0]\n",
    "    # Get the log sum exp score\n",
    "    for i in range(1, emissions.shape[0]):\n",
    "        scores = emissions[i] + log_sum_exp(\n",
    "            scores + transitions.T,\n",
    "            axis=1)\n",
    "    return log_sum_exp(scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "78.132899613126483"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "forward_algorithm(emissions, transitions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "tt = torch.Tensor(emissions)\n",
    "tt_max, _ = tt.max(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "  9   9\n",
       " 13  13\n",
       " 18  18\n",
       " 15  15\n",
       "[torch.FloatTensor of size 4x2]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tt_max.expand_as(tt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       " 33  49\n",
       "[torch.FloatTensor of size 1x2]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tt.sum(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "  9   6\n",
       " 13  10\n",
       "  8  18\n",
       "  3  15\n",
       "[torch.FloatTensor of size 4x2]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tt.squeeze(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "  9  13   8   3\n",
       "  6  10  18  15\n",
       "[torch.FloatTensor of size 2x4]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tt.transpose(-1,-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tt.ndimension()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def log_sum_exp_torch(vecs, axis=None):\n",
    "    ## Use help from: http://pytorch.org/tutorials/beginner/nlp/advanced_tutorial.html#sphx-glr-beginner-nlp-advanced-tutorial-py\n",
    "    if axis < 0:\n",
    "        axis = vecs.ndimension()+axis\n",
    "    max_val, _ = vecs.max(axis)\n",
    "    vecs = vecs - max_val.expand_as(vecs)\n",
    "    out_val = torch.log(torch.exp(vecs).sum(axis))\n",
    "    #print(max_val, out_val)\n",
    "    return max_val + out_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def forward_algorithm_torch(emissions, transitions):\n",
    "    scores = emissions[0]\n",
    "    # Get the log sum exp score\n",
    "    transitions = transitions.transpose(-1,-2)\n",
    "    for i in range(1, emissions.size(0)):\n",
    "        scores = emissions[i] + log_sum_exp_torch(\n",
    "            scores.expand_as(transitions) + transitions,\n",
    "            axis=1)\n",
    "    return log_sum_exp_torch(scores, axis=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       " 78.1329\n",
       "[torch.FloatTensor of size 1]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "forward_algorithm_torch(torch.Tensor(emissions), torch.Tensor(transitions))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The core idea is to find the sequence of states $y = \\{y_0, y_1, ..., y_N\\}$ which have the highest probability given the input $X = \\{X_0, X_1, ..., X_N\\}$ as follows:\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "p(y\\mid X) = \\prod_{i=0}^{N}{p(y_i\\mid X_i)p(y_i \\mid y_{i-1})}\\\\\n",
    "\\log{p(y\\mid X)} = \\sum_{i=0}^{N}{\\log{p(y_i\\mid X_i)} + \\log{p(y_i \\mid y_{i-1})}}\\\\\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "Now $\\log{p(y_i\\mid X_i)}$ and $\\log{p(y_i \\mid y_{i-1})}$ can be parameterized as follows:\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\log{p(y_i\\mid X_i)} = \\sum_{l=0}^{L}{\\sum_{k=0}^{K}{w_{k}^{l}*\\phi_{k}^{l}(X_i, y_i)}}\\\\\n",
    "\\log{p(y_i\\mid y_{y-1})} = \\sum_{l=0}^{L}{\\sum_{l'=0}^{L}{w_{l'}^{l}*\\psi_{l'}^{l}(y_i, y_{i-1})}}\\\\\n",
    "\\implies \\log{p(y\\mid X)} = \\sum_{i=0}^{N}{(\\sum_{l=0}^{L}{\\sum_{k=0}^{K}{w_{k}^{l}*\\phi_{k}^{l}(X_i, y_i)}}\n",
    "+ \\sum_{l=0}^{L}{\\sum_{l'=0}^{L}{w_{l'}^{l}*\\psi_{l'}^{l}(y_i, y_{i-1})}})}\\\\\n",
    "\\implies \\log{p(y\\mid X)} = \\sum_{i=0}^{N}{(\\Phi(X_i)W_{emission} + \\log{p(y_{i-1} \\mid X_{i-1})}W_{transition})}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "Where, \n",
    "\n",
    "* $N$ is the sequence length\n",
    "* $K$ is number of feature functions,\n",
    "* $L$ is number of states\n",
    "* $W_{emission}$ is $K*L$ matrix\n",
    "* $W_{transition}$ is $L*L$ matrix\n",
    "* $\\Phi(X_i)$ is a feature vector of shape $1*K$\n",
    "* $(\\Phi(X_i)W_{emission} + \\log{p(y_{i-1} \\mid X_{i-1})}W_{transition})$ gives the score for each label\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}