lectures/02_LMs-text-preprocessing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/575_banner.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lecture 2: Applications of Markov Models  and Text Preprocessing\n",
    "\n",
    "UBC Master of Data Science program, 2023-24\n",
    "\n",
    "Instructor: Varada Kolhatkar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Imports "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Intel MKL WARNING: Support of Intel(R) Streaming SIMD Extensions 4.2 (Intel(R) SSE4.2) enabled only processors has been deprecated. Intel oneAPI Math Kernel Library 2025.0 will require Intel(R) Advanced Vector Extensions (Intel(R) AVX) instructions.\n",
      "Intel MKL WARNING: Support of Intel(R) Streaming SIMD Extensions 4.2 (Intel(R) SSE4.2) enabled only processors has been deprecated. Intel oneAPI Math Kernel Library 2025.0 will require Intel(R) Advanced Vector Extensions (Intel(R) AVX) instructions.\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import re\n",
    "import string\n",
    "import sys\n",
    "import time\n",
    "from collections import Counter, defaultdict\n",
    "\n",
    "import IPython\n",
    "import nltk\n",
    "import numpy as np\n",
    "import numpy.random as npr\n",
    "import pandas as pd\n",
    "from IPython.display import HTML\n",
    "from nltk.corpus import stopwords\n",
    "from nltk.tokenize import sent_tokenize, word_tokenize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "###  Learning outcomes <a name=\"lo\"></a>\n",
    "\n",
    "By the end of this class you will be able to \n",
    "- Explain learning of Markov models. \n",
    "- Given sequence data, estimate the transition matrix from the data. \n",
    "- Build a Markov model of language. \n",
    "- Generalize Markov model of language to consider more history. \n",
    "- Explain states, state space, and transition matrix in Markov models of language. \n",
    "- Explain and calculate stationary distribution over states in Markov models of language. \n",
    "- Generate text using Markov model of language. \n",
    "- Explain the intuition of the PageRank algorithm. \n",
    "- Carry out basic text preprocessing using `nltk` and `spaCy`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recap "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- In this course, we explore models specifically designed to model sequences effectively.\n",
    "- We started simple with Markov models.\n",
    "  \n",
    "- **Markov assumption: The future is conditionally independent of the past given present**\n",
    "\n",
    "![](img/bigram-ex.png)\n",
    "$$\n",
    "P(\\text{everything} \\mid \\text{a crack in}) \\approx P(\\text{everything}\\mid\\text{in})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Markov model definition**\n",
    "\n",
    "- A set of $n$ states: $S = \\{s_1, s_2, ..., s_n\\}$\n",
    "- A set of discrete initial probability distribution over states $\\pi_0 = \\begin{bmatrix} \\pi_0(s_1) & \\pi_0(s_2) & \\dots & \\pi_0(s_n) \\end{bmatrix}$\n",
    "\n",
    "- Transition probability matrix $T$, where each $a_{ij}$ represents the probability of moving from state $s_i$ to state $s_j$, such that $\\sum_{j=1}^{n} a_{ij} = 1, \\forall i$ \n",
    "\n",
    "\n",
    "$$ T = \n",
    "\\begin{bmatrix}\n",
    "    a_{11}       & a_{12} & a_{13} & \\dots & a_{1n} \\\\\n",
    "    a_{21}       & a_{22} & a_{23} & \\dots & a_{2n} \\\\\n",
    "    \\dots \\\\\n",
    "    a_{n1}       & a_{n2} & a_{n3} & \\dots & a_{nn}\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "- In our weather toy example:\n",
    "  \n",
    "![](img/Markov_chain_small.png)\n",
    "\n",
    "$$S = \\{\\text{HOT, COLD, WARM}\\}, \\pi_0 = \\begin{bmatrix} 0.5 & 0.3 & 0.2 \\end{bmatrix}$$\n",
    "\n",
    "$$T = \\begin{bmatrix}\n",
    "0.5 & 0.2 & 0.3\\\\\n",
    "0.2 & 0.5 & 0.3\\\\\n",
    "0.3 & 0.1 & 0.6\\\\    \n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Markov model tasks:**\n",
    "We can do a number of things with Markov chains\n",
    "- Estimate the probability of a sequence:\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "P(\\textrm{COLD, COLD, WARM}) \\approx & P(\\text{COLD}) \\times P(\\text{COLD} \\mid \\text{COLD}) \\times P(\\text{WARM} \\mid \\text{COLD})\\\\\n",
    "\\end{split}\n",
    "\\end{equation}\n",
    "\n",
    "- Estimate the probability of being in a particular state at time $t$.\n",
    "  $$\\pi_0 \\times T^{t}$$\n",
    "  \n",
    "- Estimate stationary distribution which is a probability distribution that remains unchanged ($\\pi T = \\pi$) in the Markov chain as time progresses.\n",
    "    - Use power method or eigenvalue decomposition\n",
    "- Generate a sequence of states. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**An intuitive example in the context of MDS**\n",
    "- We want to plan adequate working spaces for MDS students.\n",
    "  \n",
    "- We consider three popular locations: Orchard Commons (OC), the Bullpen (B), and X860. These locations represent the three states in our Markov model. At the beginning of the year, students distribute themselves evenly across these rooms, resulting in an initial state probability distribution of $\\begin{bmatrix}\n",
    "1/3 & 1/3 & 1/3\\\\\n",
    "\\end{bmatrix}$\n",
    "\n",
    "- As students move according to their study groups or to use specific amenities (e.g., playing pingpong 🏓), their movements can be represented by a transition matrix. This matrix reflects the likelihood of moving from one location to another based on these preferences. Here are some made up numbers for the transition matrix. \n",
    "\n",
    "$$T = \\begin{bmatrix}\n",
    "OC \\lvert OC & B \\lvert OC & X860 \\lvert OC\\\\\n",
    "OC \\lvert B & B \\lvert B & X860 \\lvert B\\\\\n",
    "OC \\lvert X860 & B \\lvert X860 & X860 \\lvert X860\\\\\n",
    "\\end{bmatrix} =  \\begin{bmatrix}\n",
    "0.2 & 0.3 & 0.5\\\\\n",
    "0.3 & 0.4 & 0.3\\\\\n",
    "0.25 & 0.25 & 0.5\\\\    \n",
    "\\end{bmatrix}$$\n",
    "\n",
    "- Our goal is to understand the long-term behavior of this system—specifically, which rooms will be most crowded. In other words, we want to understand the long-term proportion of students in each location, assuming the current movement patterns continue indefinitely. This will help us with resource allocation (e.g., extra chairs, desks). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "pi_0 = np.array([1/3., 1/3., 1/3.])\n",
    "MDS_T = np.array([[0.2, 0.3, 0.5],[0.3, 0.4, 0.3],[0.25, 0.25, 0.5]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.25281   , 0.30899333, 0.43819667])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_0 @ np.linalg.matrix_power(MDS_T, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.25280899, 0.30898876, 0.43820225])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_0 @ np.linalg.matrix_power(MDS_T, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.25280899, 0.30898876, 0.43820225])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_0 @ np.linalg.matrix_power(MDS_T, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on this made-up transition matrix, in the long run, X860 will be the most populated, followed by the Bullpen and then Orchard Commons. So more treats and probably a coffee machine ☕️ in X860!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 1. More Markov models "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Learning Markov models "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example with daily activities as states**\n",
    "\n",
    "![](img/activity-seqs.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- What's $\\pi_0$(😴)?\n",
    "- What's $\\pi_0$(🍎)?\n",
    "- What is P(🍎|📚)? \n",
    "    - $\\frac{\\text{number of times we moved from 📚 to 🍎}}{\\text{number of times we moved from 📚 to anything}}$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Similar to naive Bayes, learning Markov models is just counting.\n",
    "- Given $n$ samples ($n$ sequences), MLE for homogeneous Markov model is:\n",
    "    * Initial: $P(s_i) = \\frac{\\text{number of times we start in } s_i}{n} $\n",
    "    * Transition: $P(s_j \\mid s_{i}) = \\frac{\\text{number of times we moved from } s_{i} \\text{ to } s_j}{\\text{number of times we moved from } s_{i} \\text{ to } anything}$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "- Suppose you want to learn a Markov chain for words in a corpus of $k$ documents.\n",
    "- Set of states is the set of all unique words in the corpus.\n",
    "- Calculate the initial probability distribution $\\pi_0$\n",
    "    - For all states (unique words) $w_i$, compute $\\frac{\\text{number of times a document starts with } w_i}{k}$  \n",
    "- Calculate transition probabilities for all state combinations $w_i$ and $w_j$\n",
    "    - $\\frac{\\text{number of times } w_i \\text{ precedes } w_j}{\\text{number of times } w_i \\text{ precedes anything}}$    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 1.2 n-gram language model\n",
    "\n",
    "- In NLP, a Markov model of language is also referred to as **an n-gram language model**. \n",
    "- So far we have been talking about approximating the conditional probability $P(s_{t+1} \\mid s_{1}s_{2}\\dots s_{t})$ using only the current state $P(s_{t+1} \\mid s_{t})$. \n",
    "- So we have been talking about n-gram models where $n=1$, i.e., we only consider the current state in predicting the future.    \n",
    "- Such a model is referred to as a **2-gram (bigram) language model**, because in such a model, we only consider 2 state sequences at a time, the current state to predict the next state. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Markov assumption: The future is conditionally independent of the past given present**\n",
    "\n",
    "![](img/bigram-ex.png)\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/bigram-ex.png\" height=\"500\" width=\"500\"> -->\n",
    "<!-- </center> -->\n",
    "\n",
    "$$\n",
    "P(\\text{everything} \\mid \\text{a crack in}) \\approx P(\\text{everything}\\mid\\text{in})\n",
    "$$\n",
    "\n",
    "- How do we estimate the probabilities? \n",
    "$$P(\\text{everything} \\mid\\text{in}) = \\frac{Count(\\text{in everything})}{Count(\\text{in \\{any word\\}})}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Let's try this out on a toy corpus. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The birds they sang\n",
      "At the break of day\n",
      "Start again\n",
      "I heard them say\n",
      "Don't dwell on what\n",
      "Has passed away\n",
      "Or what is yet to be\n",
      "Yeah the wars they will\n",
      "Be fought again\n",
      "The holy dove\n",
      "She will be caught again\n",
      "Bought and sold\n",
      "And bought again\n",
      "The dove is never free\n",
      "Ring the bells (ring the bells) that still can ring\n",
      "Forget your perfect offering\n",
      "There is a crack in everything (there is a crack in everything)\n",
      "That's how the light gets in\n",
      "We asked for signs\n",
      "The signs were sent\n",
      "The birth betrayed\n",
      "The marriage spent\n",
      "\n"
     ]
    }
   ],
   "source": [
    "toy_data = open(\"data/cohen_poem.txt\")\n",
    "toy_corpus = toy_data.read()\n",
    "print(toy_corpus[0:512])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Let's calculate word bigram frequencies. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>birds</th>\n",
       "      <th>break</th>\n",
       "      <th>wars</th>\n",
       "      <th>holy</th>\n",
       "      <th>dove</th>\n",
       "      <th>bells</th>\n",
       "      <th>light</th>\n",
       "      <th>signs</th>\n",
       "      <th>birth</th>\n",
       "      <th>marriage</th>\n",
       "      <th>...</th>\n",
       "      <th>out</th>\n",
       "      <th>loud</th>\n",
       "      <th>but</th>\n",
       "      <th>like</th>\n",
       "      <th>summoned</th>\n",
       "      <th>up</th>\n",
       "      <th>going</th>\n",
       "      <th>from</th>\n",
       "      <th>me</th>\n",
       "      <th>wo</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>the</th>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>birds</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>they</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>sang</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>at</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>heart</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>love</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>come</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>like</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>refugee</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>115 rows × 115 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "         birds  break  wars  holy  dove  bells  light  signs  birth  marriage  \\\n",
       "the        1.0    1.0   1.0   1.0   1.0    6.0    6.0    1.0    1.0       1.0   \n",
       "birds      0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "they       0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "sang       0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "at         0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "...        ...    ...   ...   ...   ...    ...    ...    ...    ...       ...   \n",
       "heart      0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "love       0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "come       0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "like       0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "refugee    0.0    0.0   0.0   0.0   0.0    0.0    0.0    0.0    0.0       0.0   \n",
       "\n",
       "         ...  out  loud  but  like  summoned   up  going  from   me   wo  \n",
       "the      ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "birds    ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "they     ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "sang     ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "at       ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "...      ...  ...   ...  ...   ...       ...  ...    ...   ...  ...  ...  \n",
       "heart    ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "love     ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "come     ...  0.0   0.0  1.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "like     ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "refugee  ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "\n",
       "[115 rows x 115 columns]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toy_corpus_tokens = nltk.word_tokenize(toy_corpus.lower())\n",
    "\n",
    "frequencies = defaultdict(Counter)\n",
    "for i in range(len(toy_corpus_tokens) - 1):\n",
    "    frequencies[toy_corpus_tokens[i : i + 1][0]][toy_corpus_tokens[i + 1]] += 1\n",
    "\n",
    "freq_df = pd.DataFrame(frequencies).transpose()\n",
    "freq_df = freq_df.fillna(0)\n",
    "freq_df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Let's calculate the transition matrix. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>birds</th>\n",
       "      <th>break</th>\n",
       "      <th>wars</th>\n",
       "      <th>holy</th>\n",
       "      <th>dove</th>\n",
       "      <th>bells</th>\n",
       "      <th>light</th>\n",
       "      <th>signs</th>\n",
       "      <th>birth</th>\n",
       "      <th>marriage</th>\n",
       "      <th>...</th>\n",
       "      <th>out</th>\n",
       "      <th>loud</th>\n",
       "      <th>but</th>\n",
       "      <th>like</th>\n",
       "      <th>summoned</th>\n",
       "      <th>up</th>\n",
       "      <th>going</th>\n",
       "      <th>from</th>\n",
       "      <th>me</th>\n",
       "      <th>wo</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>the</th>\n",
       "      <td>0.04</td>\n",
       "      <td>0.04</td>\n",
       "      <td>0.04</td>\n",
       "      <td>0.04</td>\n",
       "      <td>0.04</td>\n",
       "      <td>0.24</td>\n",
       "      <td>0.24</td>\n",
       "      <td>0.04</td>\n",
       "      <td>0.04</td>\n",
       "      <td>0.04</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>birds</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>they</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>sang</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>at</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>heart</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>love</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>come</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>like</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>refugee</th>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>0.00</td>\n",
       "      <td>...</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>115 rows × 115 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "         birds  break  wars  holy  dove  bells  light  signs  birth  marriage  \\\n",
       "the       0.04   0.04  0.04  0.04  0.04   0.24   0.24   0.04   0.04      0.04   \n",
       "birds     0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "they      0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "sang      0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "at        0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "...        ...    ...   ...   ...   ...    ...    ...    ...    ...       ...   \n",
       "heart     0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "love      0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "come      0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "like      0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "refugee   0.00   0.00  0.00  0.00  0.00   0.00   0.00   0.00   0.00      0.00   \n",
       "\n",
       "         ...  out  loud  but  like  summoned   up  going  from   me   wo  \n",
       "the      ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "birds    ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "they     ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "sang     ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "at       ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "...      ...  ...   ...  ...   ...       ...  ...    ...   ...  ...  ...  \n",
       "heart    ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "love     ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "come     ...  0.0   0.0  1.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "like     ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "refugee  ...  0.0   0.0  0.0   0.0       0.0  0.0    0.0   0.0  0.0  0.0  \n",
       "\n",
       "[115 rows x 115 columns]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trans_df = freq_df.div(freq_df.sum(axis=1), axis=0)\n",
    "trans_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Conditional probability P(everything | in) =  0.5714285714285714\n"
     ]
    }
   ],
   "source": [
    "print(\"Conditional probability P(everything | in) = \", trans_df.loc[\"in\"][\"everything\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**State space**\n",
    "\n",
    "- The states in our model are unique words in our corpus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "States: [\"'re\" \"'s\" \"'ve\" '(' ')' ',' 'a' 'add' 'again' 'all' 'and' 'asked' 'at'\n",
      " 'away' 'be' 'bells' 'betrayed' 'birds' 'birth' 'bought' 'break' 'but'\n",
      " 'ca' 'can' 'caught' 'come' 'crack' 'crowd' 'day' 'do' 'dove' 'drum'\n",
      " 'dwell' 'every' 'everything' 'for' 'forget' 'fought' 'free' 'from' 'gets'\n",
      " 'going' 'government' 'has' 'have' 'hear' 'heard' 'heart' 'high' 'holy'\n",
      " 'how' 'i' 'in' 'is' 'killers' 'lawless' 'light' 'like' 'loud' 'love'\n",
      " 'march' 'marriage' 'me' 'more' \"n't\" 'never' 'no' 'of' 'offering' 'on'\n",
      " 'or' 'out' 'parts' 'passed' 'perfect' 'places' 'prayers' 'refugee' 'ring'\n",
      " 'run' 'sang' 'say' 'see' 'sent' 'she' 'signs' 'sold' 'spent' 'start'\n",
      " 'still' 'strike' 'sum' 'summoned' 'that' 'the' 'their' 'them' 'there'\n",
      " 'they' 'thundercloud' 'to' 'up' 'wars' 'we' 'were' 'what' 'while'\n",
      " 'widowhood' 'will' 'with' 'wo' 'yeah' 'yet' 'you' 'your']\n",
      "Number of states: 115\n"
     ]
    }
   ],
   "source": [
    "states = np.unique(list(toy_corpus_tokens))\n",
    "print(\"States:\", states)\n",
    "S = len(states)\n",
    "print(\"Number of states:\", S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Text generation using Markov models of language**\n",
    "\n",
    "- How can we predict next word given a sequence of words? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "THE GENERATED SEQUENCE:  in everything ( ring the bells ( ring the bells ) that 's how the killers in ring the widowhood of every government signs for all to see i ca n't have the sum you can ring ( ring ) that 's how the bells ) that still can ring\n"
     ]
    }
   ],
   "source": [
    "seed = \"in\"\n",
    "seq_len = 50\n",
    "seq = \"\"\n",
    "word = seed \n",
    "for i in range(seq_len):\n",
    "    seq += \" \" + word\n",
    "    next_word = npr.choice(\n",
    "        trans_df.columns.tolist(),\n",
    "        p=trans_df.loc[\n",
    "            word,\n",
    "        ].values.flatten(),\n",
    "    )\n",
    "    word = next_word\n",
    "print(\"THE GENERATED SEQUENCE:\", seq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "In practice, the corpus (dataset) is huge. For example, the full Wikipedia or the text available on the entire Internet, or all the New York Times articles from the last 20 years. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 1.3 Incorporating more context\n",
    "\n",
    "- So far we have been talking about models where we only consider the current word when predicting the next word.\n",
    "  \n",
    "- If we want to predict future accurately, it's probably a good idea to incorporate more history.\n",
    "  \n",
    "- Can we generalize n-gram language model ($n=1$) so that we can incorporate more history in the model ($n \\gt 1$). \n",
    "\n",
    "![](img/bigram-ex.png)\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/bigram-ex.png\" height=\"500\" width=\"500\"> -->\n",
    "<!-- </center> -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- One way to incorporate more history is by extending the definition of a state.\n",
    "  \n",
    "    - Instead of defining state space as unique words in the corpus, we can define it as unique two-word, three-word, ($n-1$)-word sequences of the unique\n",
    "  words in the corpus.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "- Example: \n",
    "    - With $n=2$\n",
    "$$\n",
    "P(\\text{everything} \\mid \\text{there is a crack in}) \\approx P(\\text{everything} \\mid \\text{crack in})\n",
    "$$\n",
    "    - With $n=3$\n",
    "$$\n",
    "P(\\text{everything} \\mid \\text{there is a crack in}) \\approx P(\\text{everything} \\mid \\text{a crack in})\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Example ($n=2$)**\n",
    "\n",
    "- The state space would be all 2-word combinations of unique words in the corpus. \n",
    "    - What would be the size of the state space in our toy corpus? \n",
    "- Not all transitions would be valid transitions. \n",
    "    - Example: _is a_ $\\rightarrow$ _crack in_ is not a valid transition\n",
    "- Some valid transitions are:\n",
    "    - _is a_ $\\rightarrow$ _a crack_\n",
    "    - _a crack_ $\\rightarrow$ _crack in_\n",
    "  \n",
    "![](img/trigram-ex.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/trigram-ex.png\" height=\"500\" width=\"500\"> -->\n",
    "<!-- </center> -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Example ($n=3$)**\n",
    "- The state space would be all 3-word combinations of unique words in the corpus. \n",
    "    - What would be the size of the state space in our toy corpus?\n",
    "      \n",
    "- An invalid transition is:\n",
    "    - _is a crack_ $\\rightarrow$ _crack in everything_\n",
    "\n",
    "- A valid transition is:\n",
    "    - _is a crack_ $\\rightarrow$ _a crack in_\n",
    "\n",
    "\n",
    "![](img/4-gram-ex.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/4-gram-ex.png\" height=\"500\" width=\"500\"> -->\n",
    "<!-- </center> -->\n",
    "\n",
    "- Now we are able to incorporate more history, without really changing the math of Markov models! \n",
    "- We can calculate probability of sequences, predict the state at a given time step, or calculate the stationary distribution the same way. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 1.4 Evaluating language models \n",
    "\n",
    "**Perplexity**\n",
    "\n",
    "- The best way to evaluate the performance of a language model is to embed it in an application and measure how much the application improves. This is called **extrinsic evaluation**. \n",
    "    - For example, embed it in Speech Recognition and measure how much it improves.  \n",
    "- Often it is expensive to run NLP systems end-to-end and it's helpful to have a metric which can be used to quickly evaluate the improvements in a language model. \n",
    "- The most commonly used **intrinsic evaluation metric** in the context of language models is **perplexity**.\n",
    "  \n",
    "- The **perplexity** of a language model on a test set is the inverse probability of the test set, normalized by the number of words.\n",
    "- For a test set: $W = w_1w_2 \\dots w_N$\n",
    "  $$\\text{perplexity}(W) = P(w_1w_2 \\dots w_N)^{-1/N} =  \\sqrt[n]{\\frac{1}{P(w_1w_2 \\dots w_N)}}$$ \n",
    "\n",
    "- For a Markov model of language with `n=1`, we approximate $P(w_1w_2 \\dots w_N)$ as $\\prod_{i=1}^N P(w_i|w_{i-1})$. So the perplexity of the corpus is: \n",
    "  $$\\text{perplexity}(W) = \\sqrt[n]{\\prod_{i=1}^N\\frac{1}{P(w_i \\lvert w_{i-1})}}$$\n",
    "- We use the entire sequence in the test set when calculating perplexity.\n",
    "- Perplexity is a function of corpus $W$ and the language model being used. Different language models will have different perplexities on a given test set. So we can use this metric to roughly evaluate the performance of our language model.   \n",
    "    - A lower perplexity $\\rightarrow$ the language model is a better predictor of the words in the test set\n",
    "    - A higher perplexity $\\rightarrow$ the language model is not a good predictor of the words in the test set. (It's surprised by the text in the test set.)\n",
    "- We'll revisit perplexity when we discuss neural language models.\n",
    "\n",
    "- Check out [this link]([https://web.stanford.edu/~jurafsky/slp3/3.pdf]) for more details. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Are n-grams a good model of language?**\n",
    "\n",
    "- In many cases, we can get by with ngram models.\n",
    "    - Spam filtering\n",
    "    - Keyword extraction\n",
    "    - Authorship detection\n",
    "    - ...    \n",
    "- But in general, is it a good assumption that the next word that I utter will be dependent on the last 3 words or 4 words?\n",
    "\n",
    "<blockquote>\n",
    "    I am studying data science at the University of British Columbia in Vancouver because I want to build a career in ___. \n",
    "</blockquote>    \n",
    "\n",
    "- Language has long-distance dependencies.  \n",
    "- We can extend it to $3$-grams, $4$-grams, or even $10$-grams. But then there is sparsity problem. The state space explodes and the estimated probabilities are not very reliable. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Language models with word embeddings**\n",
    "\n",
    "- N-gram models are great but we are representing context as the exact word.\n",
    "- Suppose in your training data you have the sequence \"feed the cat\" but you do not have the sequence \"feed the dog\".\n",
    "\n",
    "<blockquote>\n",
    "I have to make sure to feed the cat.\n",
    "</blockquote>\n",
    "\n",
    "- Trigram model: $P(\\text{dog} \\mid \\text{feed the}) = 0$\n",
    "- If we represent words with word embeddings instead, we will be able to generalize to dog even if we haven't seen it in the corpus.\n",
    "- We'll come back to this when we learn about Recurrent Neural Networks (RNNs). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "**(Optional) [Google n-gram viewer](https://books.google.com/ngrams)**\n",
    " \n",
    "- All Our N-gram are Belong to You\n",
    "    - https://ai.googleblog.com/2006/08/all-our-n-gram-are-belong-to-you.html\n",
    "\n",
    "<blockquote>\n",
    "Here at Google Research we have been using word n-gram models for a variety\n",
    "of R&D projects, such as statistical machine translation, speech recognition,\n",
    "spelling correction, entity detection, information extraction, and others.\n",
    "That's why we decided to share this enormous dataset with everyone. We\n",
    "processed 1,024,908,267,229 words of running text and are publishing the\n",
    "counts for all 1,176,470,663 five-word sequences that appear at least 40\n",
    "times. There are 13,588,391 unique words, after discarding words that appear\n",
    "less than 200 times.”\n",
    "</blockquote>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"1000\"\n",
       "            height=\"800\"\n",
       "            src=\"https://books.google.com/ngrams/\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "            \n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.IFrame at 0x14641a810>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import IPython\n",
    "url = \"https://books.google.com/ngrams/\"\n",
    "IPython.display.IFrame(url, width=1000, height=800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ❓❓ Questions for you"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.1: Select all of the following statements which are **True** (iClicker)\n",
    "**iClicker join link: https://join.iclicker.com/ZTLY**\n",
    "\n",
    "- (A) Building a transition matrix for a Markov model means calculating the proportion of how often sequences of states occur in your data. \n",
    "- (B) In our setup, when n=3, each state has 3 letters. So given a three letter sequence, we predict the next three letter sequence. \n",
    "- (C) Suppose you have two corpora from completely different domains. You build two word-based n-gram models one for each corpus. The stationary distribution would be the same for both n-gram models.\n",
    "- (D) Suppose you are building an n-gram model of language with characters on a corpus with vocabulary $V = 100$ and $n=4$ in our n-gram model setup. The dimensionality of the transition matrix in this case would be $100 \\times 100$.\n",
    "- (E) In Markov models, increasing the value of $n$ typically leads to a decrease in perplexity. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 2.1: V's Solutions! \n",
    ":class: tip, dropdown\n",
    "- (A) True\n",
    "- (B) False. Although each state would have 3 letters, you will still only predict one letter. Just that you have access to more history or context in the sequence instead of just one preceding character.\n",
    "- (C) False. Two corpora would have different word n-gram frequencies.\n",
    "- (D) False. \n",
    "- (E) Increasing the value of `n` in Markov models usually results in lower perplexity. That said, if `n` becomes too large in Markov models, the model may overfit the training data, leading to poor generalization on test data and potentially higher perplexity.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.2: Questions for class discussion\n",
    "\n",
    "- In our setup, n=1 means a bigram model. I'm not sure if our implementation would work with n=0. But think about what does it mean and how would you generate text when n=0.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 2.1: V's Solutions! \n",
    ":class: tip, dropdown\n",
    "For n=0, the next characters will be generated randomly without taking into account any context/history.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Break\n",
    "\n",
    "![](img/eva-coffee.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Applications of Markov models"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 2.1 Markov’s own application of his chains\n",
    "\n",
    "- Markov studied the sequence of 100,000 letters in S. T. Aksakov's novel \"The Childhood of Bagrov, the Grandson\".\n",
    "    * $S = \\{\\text{vowel, consonant}\\}$ \n",
    "    * \n",
    "    $ T = \n",
    "    \\begin{bmatrix}\n",
    "    0.552 & 0.448\\\\\n",
    "    0.365 & 0.635\\\\\n",
    "    \\end{bmatrix}\n",
    "    $\n",
    "\n",
    "|               | vowel     | consonant |\n",
    "| ------------- |:---------:| -----:|\n",
    "| vowel         | 0.552       | 0.448   |\n",
    "| consonant     | 0.365       | 0.635   |\n",
    "\n",
    "- He provided the stationary distribution for vowels and consonants based on his counting. \n",
    "    * $\\pi = [0.449,0.551]$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Stationary distribution in the context of text**\n",
    "\n",
    "- In n-gram models of language, a stationary distribution can be thought of as the long-term distribution of word/character frequencies in a corpus of text, and it can be calculated as how often each state occurs in the corpus. \n",
    "- What does it represent? \n",
    "    - Intuitively, it represents the distribution of words that would be observed if the text were generated according to the n-gram model.\n",
    "- In Markov's example above, the stationary distribution for the states **vowel** and **consonant** is calculated as: \n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    \\frac{\\text{\\# vowel occurrences}}{\\text{total number of letters}} & \\frac{\\text{\\# consonant occurrences} }{\\text{total number of letters}}\\\\\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Let's check whether we get $\\pi T = \\pi$ with this stationary distribution.     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi = np.array([0.449, 0.551]) # stationary distributed calculated by Markov\n",
    "T = np.array([[0.552, 0.448], [0.365, 0.635]])\n",
    "np.allclose(pi @ T, pi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.448963 0.551037]\n",
      "[0.44895608 0.55104392]\n",
      "[0.44895479 0.55104521]\n",
      "[0.44895449 0.55104551]\n",
      "[0.44895449 0.55104551]\n"
     ]
    }
   ],
   "source": [
    "print(pi @ T)\n",
    "print(pi @ np.linalg.matrix_power(T, 2))\n",
    "print(pi @ np.linalg.matrix_power(T, 3))\n",
    "print(pi @ np.linalg.matrix_power(T, 6))\n",
    "print(pi @ np.linalg.matrix_power(T, 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "- The state probabilities are not quite the same but they are pretty close. \n",
    "- Note that Markov calculated the stationary distribution **by hand** and probably he rounded off the probabilities after 3 decimal places. (Tedious calculation!!) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ❓❓ Questions for you"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.3 Select all of the following statements which are **True**\n",
    "\n",
    "- (A) It might be possible to identify rare words or characters in a corpus of text using stationary distribution because these words are likely to have lower state probabilities in the observed stationary distribution. \n",
    "- (B) The stationary distribution on two corpora: Bob Dylan's poetry vs. biomedical text are likely to be different. \n",
    "- (C) The stationary distribution can be used to evaluate the quality of an n-gram language model by comparing its predicted distribution to the observed stationary distribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 2.3: V's Solutions!\n",
    ":class: tip, dropdown\n",
    "- A, B, C\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 2.2 PageRank "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- One of the primary algorithms used by Google Search to rank web pages in their search engine results.\n",
    "- Graph-based ranking algorithm, which assigns a rank to a webpage.\n",
    "- The rank indicates a relative score of the page's importance and authority.\n",
    "- Intuition\n",
    "    - Important webpages are linked from other important webpages.\n",
    "    - Don't just look at the number of links coming to a webpage but consider who the links are coming from. \n",
    "\n",
    "![](img/wiki_page_rank.jpg)\n",
    "\n",
    "<!-- <center>     -->\n",
    "<!-- <img src=\"img/wiki_page_rank.jpg\" height=\"300\" width=\"300\">  -->\n",
    "<!-- </center> -->\n",
    "\n",
    "[Credit](https://en.wikipedia.org/wiki/PageRank#/media/File:PageRanks-Example.jpg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "**PageRank: scoring**\n",
    "\n",
    "- Imagine a surfer doing a random walk \n",
    "    - At time t=0, start at a random webpage.\n",
    "    - At time t=1, follow a random link on the current page.\n",
    "    - At time t=2, follow a random link on the current page. \n",
    "    \n",
    "- Intuition\n",
    "    - In the \"steady state\" each page has a long-term visit rate, which is the page's score (rank). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**PageRank as a Markov chain**\n",
    "\n",
    "- A state is a web page.\n",
    "- Transition probabilities represent probabilities of moving from one page to another.\n",
    "- We derive these from the adjacency matrix of the web graph\n",
    "    - Adjacency matrix $M$ is a $n \\times n$ matrix, if $n$ is the number of states (web pages)\n",
    "    - $M_{ij} = 1$ if there is a hyperlink from page $i$ to page $j$.   \n",
    "- (Optional) If you want to know more details, check out [AppendixA-PageRank](AppendixA-PageRank.ipynb).    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To effectively use a Markov chain and calculating stationary distribution, we need a connected graph. But with billions of webpages, it's very unlikely that this graph will be connected. So at a high-level, we follow the steps below to create a transition matrix:\n",
    "\n",
    "- To make the web connected, we add $\\epsilon$ to each entry in the transition matrix. \n",
    "- Normalize so that each row sums to 1.0.\n",
    "- Find the stationary distribution of the transition matrix. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Calculate page rank: power iteration method**\n",
    "\n",
    "- Start with a random initial probability distribution $\\pi_0$.\n",
    "- Multiply $\\pi_0$ by powers of the transition matrix $T$ until the product looks stable.  \n",
    "    - After one step, we are at $\\pi T$\n",
    "    - After two steps, we are at $\\pi T^2$\n",
    "    - After three steps, we are at $\\pi T^3$\n",
    "    - Eventually (for a large $k$), $\\pi T^k$ we get a stationary distribution.      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happens when we search for a keywork on Google? \n",
    "- It finds all the webpages containing the keywords and orders them based on their ranks, i.e., state probabilities from stationary distribution. \n",
    "- This is the core algorithm behind Google search to rank webpages. \n",
    "- On the top of this algorithm, they add fudge factors: \n",
    "    - Wikipedia $\\rightarrow$ move up\n",
    "    - If someone is giving them lots of money $\\rightarrow$ move up 🙁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**(Optional) Modern ranking methods are more advanced:**\n",
    "- Guarding against methods that exploit algorithm.\n",
    "- Removing offensive/illegal content.\n",
    "- Supervised and personalized ranking methods.\n",
    "- Take into account that you often only care about top rankings.\n",
    "- Also work on diversity of rankings:\n",
    "    - E.g., divide objects into sub-topics and do weighted \"covering\" of topics.\n",
    "- Persistence/freshness as in recommender systems (news articles)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 3. Basic text preprocessing [[video](https://www.youtube.com/watch?v=7W5Q8gzNPBc)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Why do we need preprocessing?\n",
    "    - Text data is unstructured and messy. \n",
    "    - We need to \"normalize\" it before we do anything interesting with it. \n",
    "- Example:     \n",
    "    - **Lemma**: Same stem, same part-of-speech, roughly the same meaning\n",
    "        - Vancouver's &rarr; Vancouver\n",
    "        - computers &rarr; computer \n",
    "        - rising &rarr; rise, rose, rises    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 3.1 Tokenization\n",
    "\n",
    "- Sentence segmentation: Split text into sentences\n",
    "      \n",
    "- Word tokenization: Split sentences into words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Sentence segmentation**\n",
    "\n",
    "<blockquote>\n",
    "MDS is a Master's program at UBC in British Columbia. MDS teaching team is truly multicultural!! Dr. Beuzen did his Ph.D. in Australia. Dr. Timbers, Dr. Ostblom, Dr. Rodríguez-Arelis, and Dr. Kolhatkar did theirs in Canada. Dr. George did his in Scotland. Dr. Gelbart did his PhD in the U.S.\n",
    "</blockquote>\n",
    "\n",
    "- How many sentences are there in this text? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[\"MDS is a Master's program at UBC in British Columbia\", ' MDS teaching team is truly multicultural!! Dr', ' Beuzen did his Ph', 'D', ' in Australia', ' Dr', ' Timbers, Dr', ' Ostblom, Dr', ' Rodríguez-Arelis, and Dr', ' Kolhatkar did theirs in Canada', ' Dr', ' George did his in Scotland', ' Dr', ' Gelbart did his PhD in the U', 'S', '']\n"
     ]
    }
   ],
   "source": [
    "### Let's do sentence segmentation on \".\"\n",
    "text = (\n",
    "    \"MDS is a Master's program at UBC in British Columbia. \"\n",
    "    \"MDS teaching team is truly multicultural!! \"\n",
    "    \"Dr. Beuzen did his Ph.D. in Australia. \"\n",
    "    \"Dr. Timbers, Dr. Ostblom, Dr. Rodríguez-Arelis, and Dr. Kolhatkar did theirs in Canada. \"\n",
    "    \"Dr. George did his in Scotland. \"\n",
    "    \"Dr. Gelbart did his PhD in the U.S.\"\n",
    ")\n",
    "\n",
    "print(text.split(\".\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- In English, period (.) is quite ambiguous. (In Chinese, it is unambiguous.)\n",
    "    - Abbreviations like Dr., U.S., Inc.  \n",
    "    - Numbers like 60.44%, 0.98\n",
    "      \n",
    "- ! and ? are relatively ambiguous.\n",
    "- How about writing regular expressions? \n",
    "- A common way is using off-the-shelf models for sentence segmentation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[\"MDS is a Master's program at UBC in British Columbia.\", 'MDS teaching team is truly multicultural!!', 'Dr. Beuzen did his Ph.D. in Australia.', 'Dr. Timbers, Dr. Ostblom, Dr. Rodríguez-Arelis, and Dr. Kolhatkar did theirs in Canada.', 'Dr. George did his in Scotland.', 'Dr. Gelbart did his PhD in the U.S.']\n"
     ]
    }
   ],
   "source": [
    "### Let's try to do sentence segmentation using nltk\n",
    "from nltk.tokenize import sent_tokenize\n",
    "\n",
    "sent_tokenized = sent_tokenize(text)\n",
    "print(sent_tokenized)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Word tokenization**\n",
    "\n",
    "<blockquote>\n",
    "MDS is a Master's program at UBC in British Columbia. \n",
    "</blockquote>\n",
    "\n",
    "- How many words are there in this sentence?  \n",
    "- Is whitespace a sufficient condition for a word boundary?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<blockquote>\n",
    "MDS is a Master's program at UBC in British Columbia. \n",
    "</blockquote>\n",
    "\n",
    "- What's our definition of a word?\n",
    "    - Should British Columbia be one word or two words? \n",
    "    - Should punctuation be considered a separate word?\n",
    "    - What about the punctuations in `U.S.`?\n",
    "    - What do we do with words like `Master's`?\n",
    "- This process of identifying word boundaries is referred to as **tokenization**.\n",
    "- You can use regex but better to do it with off-the-shelf ML models.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Splitting on whitespace:  [['MDS', 'is', 'a', \"Master's\", 'program', 'at', 'UBC', 'in', 'British', 'Columbia.'], ['MDS', 'teaching', 'team', 'is', 'truly', 'multicultural!!'], ['Dr.', 'Beuzen', 'did', 'his', 'Ph.D.', 'in', 'Australia.'], ['Dr.', 'Timbers,', 'Dr.', 'Ostblom,', 'Dr.', 'Rodríguez-Arelis,', 'and', 'Dr.', 'Kolhatkar', 'did', 'theirs', 'in', 'Canada.'], ['Dr.', 'George', 'did', 'his', 'in', 'Scotland.'], ['Dr.', 'Gelbart', 'did', 'his', 'PhD', 'in', 'the', 'U.S.']]\n",
      "\n",
      "\n",
      "\n",
      "Tokenized:  [['MDS', 'is', 'a', 'Master', \"'s\", 'program', 'at', 'UBC', 'in', 'British', 'Columbia', '.'], ['MDS', 'teaching', 'team', 'is', 'truly', 'multicultural', '!', '!'], ['Dr.', 'Beuzen', 'did', 'his', 'Ph.D.', 'in', 'Australia', '.'], ['Dr.', 'Timbers', ',', 'Dr.', 'Ostblom', ',', 'Dr.', 'Rodríguez-Arelis', ',', 'and', 'Dr.', 'Kolhatkar', 'did', 'theirs', 'in', 'Canada', '.'], ['Dr.', 'George', 'did', 'his', 'in', 'Scotland', '.'], ['Dr.', 'Gelbart', 'did', 'his', 'PhD', 'in', 'the', 'U.S', '.']]\n"
     ]
    }
   ],
   "source": [
    "### Let's do word segmentation on white spaces\n",
    "print(\"Splitting on whitespace: \", [sent.split() for sent in sent_tokenized])\n",
    "\n",
    "### Let's try to do word segmentation using nltk\n",
    "from nltk.tokenize import word_tokenize\n",
    "\n",
    "word_tokenized = [word_tokenize(sent) for sent in sent_tokenized]\n",
    "# This is similar to the input format of word2vec algorithm\n",
    "print(\"\\n\\n\\nTokenized: \", word_tokenized)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 3.2 Word segmentation \n",
    "\n",
    "For some languages you need much more sophisticated tokenizers. \n",
    "\n",
    "- For languages such as Chinese, there are no spaces between words.\n",
    "    - [jieba](https://github.com/fxsjy/jieba) is a popular tokenizer for Chinese.      \n",
    "- German doesn't separate compound words.\n",
    "    * Example: _rindfleischetikettierungsüberwachungsaufgabenübertragungsgesetz_\n",
    "    * (the law for the delegation of monitoring beef labeling)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Types and tokens**\n",
    "- Usually in NLP, we talk about \n",
    "    - **Type** an element in the vocabulary\n",
    "    - **Token** an instance of that type in running text \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exercise for you \n",
    "\n",
    "<blockquote>    \n",
    "UBC is located in the beautiful province of British Columbia. It's very close \n",
    "to the U.S. border. You'll get to the USA border in about 45 mins by car.     \n",
    "</blockquote>  \n",
    "\n",
    "- Consider the example above. \n",
    "    - How many types? (task dependent)\n",
    "    - How many tokens? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 3.3 Other commonly used preprocessing steps\n",
    "\n",
    "- Punctuation and stopword removal\n",
    "- Stemming and lemmatization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Punctuation and stopword removal**\n",
    "\n",
    "- The most frequently occurring words in English are not very useful in many NLP tasks.\n",
    "    - Example: _the_ , _is_ , _a_ , and punctuation\n",
    "- Probably not very informative in many tasks "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['shan', 'ain', \"wouldn't\", 'below', \"hasn't\", 'most', 'does', 'not', 'shouldn', 'me', 'an', 'than', 'up', 'is', \"she's\", \"wasn't\", 'isn', 'or', 'all', 'had', 'them', 'again', 'these', 'the', 'off', 'ours', \"haven't\", 'their', 'what', 'this', 'any', 'they', 'which', 'such', 'each', 'mightn', 'hasn', 'during', 'themselves', 'am', \"should've\", 'under', 'y', 'our', 'before', 'in', 'd', 'yours', 'as', 're', 'here', 'through', 'my', 'being', 'weren', 'should', 'i', 'from', 'very', 'didn', 'above', 'hadn', \"shouldn't\", 'don', 'aren', 'both', 'when', 'further', 'hers', 'against', 'to', 'mustn', 'won', 'that', \"weren't\", 't', 'a', 'of', 'at', 'on', 'just', 'll', \"mightn't\", 'over', 'once', 'no', 'after', \"you've\", 'having', 'haven', \"aren't\", \"doesn't\", 'he', 'it', 'myself', 'are', 'nor', 'for', 'needn', 'o', 'did', 'down', 'by', 'there', 'where', \"mustn't\", 'until', \"you'll\", 'too', 'whom', 'why', 'theirs', \"couldn't\", 'about', 'and', 'were', 'doing', 'his', 'itself', 'more', \"shan't\", 'can', 'himself', 'her', 'your', 'now', \"it's\", 'so', \"didn't\", 'between', \"don't\", 'been', 'was', 'but', 'him', 'out', 'we', 's', 'because', \"won't\", \"that'll\", 'while', 'has', 'she', 'have', \"needn't\", 'herself', 've', 'ma', 'same', 'you', 'own', 'be', 'only', 'will', 'few', \"you'd\", 'couldn', 'yourselves', 'how', \"isn't\", 'm', 'if', \"you're\", 'yourself', 'into', \"hadn't\", 'wasn', 'do', 'doesn', 'who', 'those', 'some', 'with', 'wouldn', 'its', 'other', 'then', 'ourselves', '!', '\"', '#', '$', '%', '&', \"'\", '(', ')', '*', '+', ',', '-', '.', '/', ':', ';', '<', '=', '>', '?', '@', '[', '\\\\', ']', '^', '_', '`', '{', '|', '}', '~']\n"
     ]
    }
   ],
   "source": [
    "# Let's use `nltk.stopwords`.\n",
    "# Add punctuations to the list.\n",
    "stop_words = list(set(stopwords.words(\"english\")))\n",
    "import string\n",
    "\n",
    "punctuation = string.punctuation\n",
    "stop_words += list(punctuation)\n",
    "# stop_words.extend(['``','`','br','\"',\"”\", \"''\", \"'s\"])\n",
    "print(stop_words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['mds', 'master', \"'s\", 'program', 'ubc', 'british', 'columbia', 'mds', 'teaching', 'team', 'truly', 'multicultural', 'dr.', 'beuzen', 'ph.d.', 'australia', 'dr.', 'timbers', 'dr.', 'ostblom', 'dr.', 'rodríguez-arelis', 'dr.', 'kolhatkar', 'canada', 'dr.', 'george', 'scotland', 'dr.', 'gelbart', 'phd', 'u.s']\n"
     ]
    }
   ],
   "source": [
    "### Get rid of stop words\n",
    "preprocessed = []\n",
    "for sent in word_tokenized:\n",
    "    for token in sent:\n",
    "        token = token.lower()\n",
    "        if token not in stop_words:\n",
    "            preprocessed.append(token)\n",
    "print(preprocessed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Lemmatization**\n",
    "\n",
    "- For many NLP tasks (e.g., web search) we want to ignore morphological differences between words\n",
    "    - Example: If your search term is \"studying for ML quiz\" you might want to include pages containing \"tips to study for an ML quiz\" or \"here is how I studied for my ML quiz\"\n",
    "- Lemmatization converts inflected forms into the base form. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package wordnet to /Users/kvarada/nltk_data...\n",
      "[nltk_data]   Package wordnet is already up-to-date!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import nltk\n",
    "\n",
    "nltk.download(\"wordnet\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package omw-1.4 to /Users/kvarada/nltk_data...\n",
      "[nltk_data]   Package omw-1.4 is already up-to-date!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nltk.download(\"omw-1.4\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Lemma of studying:  study\n",
      "Lemma of studied:  study\n"
     ]
    }
   ],
   "source": [
    "# nltk has a lemmatizer\n",
    "from nltk.stem import WordNetLemmatizer\n",
    "\n",
    "lemmatizer = WordNetLemmatizer()\n",
    "print(\"Lemma of studying: \", lemmatizer.lemmatize(\"studying\", \"v\"))\n",
    "print(\"Lemma of studied: \", lemmatizer.lemmatize(\"studied\", \"v\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Stemming**\n",
    "\n",
    "- Has a similar purpose but it is a crude chopping of affixes \n",
    "    * _automates, automatic, automation_ all reduced to _automat_.\n",
    "- Usually these reduced forms (stems) are not actual words themselves.  \n",
    "- A popular stemming algorithm for English is PorterStemmer. \n",
    "- Beware that it can be aggressive sometimes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before stemming:  UBC is located in the beautiful province of British Columbia... It's very close to the U.S. border.\n",
      "\n",
      "\n",
      "After stemming:  ubc is locat in the beauti provinc of british columbia ... it 's veri close to the u.s. border .\n"
     ]
    }
   ],
   "source": [
    "from nltk.stem.porter import PorterStemmer\n",
    "\n",
    "text = (\n",
    "    \"UBC is located in the beautiful province of British Columbia... \"\n",
    "    \"It's very close to the U.S. border.\"\n",
    ")\n",
    "ps = PorterStemmer()\n",
    "tokenized = word_tokenize(text)\n",
    "stemmed = [ps.stem(token) for token in tokenized]\n",
    "print(\"Before stemming: \", text)\n",
    "print(\"\\n\\nAfter stemming: \", \" \".join(stemmed))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 3.4 Other tools for preprocessing \n",
    "\n",
    "- We used [Natural Language Processing Toolkit (nltk)](https://www.nltk.org/) above\n",
    "    - You already have used it in 571 and 573  \n",
    "- Many available tools    \n",
    "- [spaCy](https://spacy.io/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**[spaCy](https://spacy.io/)**\n",
    "\n",
    "- We already have used spaCy before in 573 and 563. \n",
    "- Industrial strength NLP library. \n",
    "- Lightweight, fast, and convenient to use. \n",
    "- spaCy does many things that we did above in one line of code! \n",
    "- Also has [multi-lingual](https://spacy.io/models/xx) support. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !python -m spacy download en_core_web_md"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import spacy\n",
    "\n",
    "# Load the model\n",
    "nlp = spacy.load(\"en_core_web_md\")\n",
    "text = (\n",
    "    \"MDS is a Master's program at UBC in British Columbia. \"\n",
    "    \"MDS teaching team is truly multicultural!! \"\n",
    "    \"Dr. Nguyen and Dr. George obtained their Ph.D. degrees in United Kingdom. \"\n",
    "    \"Dr. D'Andrea obtained her Ph.D. degree in Argentina. \"        \n",
    "    \"Dr. Timbers, Dr. Ostblom, Dr. Rodríguez-Arelis, and Dr. Kolhatkar obtained their Ph.D. degrees in Canada. \"\n",
    "    \"Dr. Gelbart obtained his Ph.D. degree in the U.S.\"\n",
    ")\n",
    "\n",
    "doc = nlp(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Tokens:  [MDS, is, a, Master, 's, program, at, UBC, in, British, Columbia, ., MDS, teaching, team, is, truly, multicultural, !, !, Dr., Nguyen, and, Dr., George, obtained, their, Ph.D., degrees, in, United, Kingdom, ., Dr., D'Andrea, obtained, her, Ph.D., degree, in, Argentina, ., Dr., Timbers, ,, Dr., Ostblom, ,, Dr., Rodríguez, -, Arelis, ,, and, Dr., Kolhatkar, obtained, their, Ph.D., degrees, in, Canada, ., Dr., Gelbart, obtained, his, Ph.D., degree, in, the, U.S.]\n",
      "\n",
      "Lemmas:  ['mds', 'be', 'a', 'Master', \"'s\", 'program', 'at', 'UBC', 'in', 'British', 'Columbia', '.', 'mds', 'teaching', 'team', 'be', 'truly', 'multicultural', '!', '!', 'Dr.', 'Nguyen', 'and', 'Dr.', 'George', 'obtain', 'their', 'ph.d.', 'degree', 'in', 'United', 'Kingdom', '.', 'Dr.', \"D'Andrea\", 'obtain', 'her', 'ph.d.', 'degree', 'in', 'Argentina', '.', 'Dr.', 'Timbers', ',', 'Dr.', 'Ostblom', ',', 'Dr.', 'Rodríguez', '-', 'Arelis', ',', 'and', 'Dr.', 'Kolhatkar', 'obtain', 'their', 'ph.d.', 'degree', 'in', 'Canada', '.', 'Dr.', 'Gelbart', 'obtain', 'his', 'ph.d.', 'degree', 'in', 'the', 'U.S.']\n",
      "\n",
      "POS:  ['NOUN', 'AUX', 'DET', 'PROPN', 'PART', 'NOUN', 'ADP', 'PROPN', 'ADP', 'PROPN', 'PROPN', 'PUNCT', 'NOUN', 'NOUN', 'NOUN', 'AUX', 'ADV', 'ADJ', 'PUNCT', 'PUNCT', 'PROPN', 'PROPN', 'CCONJ', 'PROPN', 'PROPN', 'VERB', 'PRON', 'NOUN', 'NOUN', 'ADP', 'PROPN', 'PROPN', 'PUNCT', 'PROPN', 'PROPN', 'VERB', 'PRON', 'NOUN', 'NOUN', 'ADP', 'PROPN', 'PUNCT', 'PROPN', 'PROPN', 'PUNCT', 'PROPN', 'PROPN', 'PUNCT', 'PROPN', 'PROPN', 'PUNCT', 'PROPN', 'PUNCT', 'CCONJ', 'PROPN', 'PROPN', 'VERB', 'PRON', 'NOUN', 'NOUN', 'ADP', 'PROPN', 'PUNCT', 'PROPN', 'PROPN', 'VERB', 'PRON', 'NOUN', 'NOUN', 'ADP', 'DET', 'PROPN']\n"
     ]
    }
   ],
   "source": [
    "# Accessing tokens\n",
    "tokens = [token for token in doc]\n",
    "print(\"\\nTokens: \", tokens)\n",
    "\n",
    "# Accessing lemma\n",
    "lemmas = [token.lemma_ for token in doc]\n",
    "print(\"\\nLemmas: \", lemmas)\n",
    "\n",
    "# Accessing pos\n",
    "pos = [token.pos_ for token in doc]\n",
    "print(\"\\nPOS: \", pos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 3.5 Other typical NLP tasks \n",
    "In order to understand text, we usually are interested in extracting information from text. Some common tasks in NLP pipeline are: \n",
    "- Part of speech tagging\n",
    "    - Assigning part-of-speech tags to all words in a sentence.\n",
    "- Named entity recognition\n",
    "    - Labelling named “real-world” objects, like persons, companies or locations.    \n",
    "- Coreference resolution\n",
    "    - Deciding whether two strings (e.g., UBC vs University of British Columbia) refer to the same entity\n",
    "- Dependency parsing\n",
    "    - Representing grammatical structure of a sentence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### 3.5.1 Extracting named-entities using spaCy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span class=\"tex2jax_ignore\"><div class=\"entities\" style=\"line-height: 2.5; direction: ltr\">\n",
       "<mark class=\"entity\" style=\"background: #7aecec; padding: 0.45em 0.6em; margin: 0 0.25em; line-height: 1; border-radius: 0.35em;\">\n",
       "    University of British Columbia\n",
       "    <span style=\"font-size: 0.8em; font-weight: bold; line-height: 1; border-radius: 0.35em; vertical-align: middle; margin-left: 0.5rem\">ORG</span>\n",
       "</mark>\n",
       " is located in the beautiful province of \n",
       "<mark class=\"entity\" style=\"background: #feca74; padding: 0.45em 0.6em; margin: 0 0.25em; line-height: 1; border-radius: 0.35em;\">\n",
       "    British Columbia\n",
       "    <span style=\"font-size: 0.8em; font-weight: bold; line-height: 1; border-radius: 0.35em; vertical-align: middle; margin-left: 0.5rem\">GPE</span>\n",
       "</mark>\n",
       ".</div></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Named entities:\n",
      " [('University of British Columbia', 'ORG'), ('British Columbia', 'GPE')]\n",
      "\n",
      "ORG means:  Companies, agencies, institutions, etc.\n",
      "GPE means:  Countries, cities, states\n"
     ]
    }
   ],
   "source": [
    "from spacy import displacy\n",
    "\n",
    "doc = nlp(\n",
    "    \"University of British Columbia \"\n",
    "    \"is located in the beautiful \"\n",
    "    \"province of British Columbia.\"\n",
    ")\n",
    "displacy.render(doc, style=\"ent\")\n",
    "# Text and label of named entity span\n",
    "print(\"Named entities:\\n\", [(ent.text, ent.label_) for ent in doc.ents])\n",
    "print(\"\\nORG means: \", spacy.explain(\"ORG\"))\n",
    "print(\"GPE means: \", spacy.explain(\"GPE\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### 3.5.2 Dependency parsing using spaCy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span class=\"tex2jax_ignore\"><svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" xml:lang=\"en\" id=\"cad1874c1ca444bf97b9c0b815d63c9a-0\" class=\"displacy\" width=\"575\" height=\"224.5\" direction=\"ltr\" style=\"max-width: none; height: 224.5px; color: #000000; background: #ffffff; font-family: Arial; direction: ltr\">\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"134.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"50\">I</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"50\">PRON</tspan>\n",
       "</text>\n",
       "\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"134.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"225\">like</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"225\">VERB</tspan>\n",
       "</text>\n",
       "\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"134.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"400\">cats</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"400\">NOUN</tspan>\n",
       "</text>\n",
       "\n",
       "<g class=\"displacy-arrow\">\n",
       "    <path class=\"displacy-arc\" id=\"arrow-cad1874c1ca444bf97b9c0b815d63c9a-0-0\" stroke-width=\"2px\" d=\"M70,89.5 C70,2.0 225.0,2.0 225.0,89.5\" fill=\"none\" stroke=\"currentColor\"/>\n",
       "    <text dy=\"1.25em\" style=\"font-size: 0.8em; letter-spacing: 1px\">\n",
       "        <textPath xlink:href=\"#arrow-cad1874c1ca444bf97b9c0b815d63c9a-0-0\" class=\"displacy-label\" startOffset=\"50%\" side=\"left\" fill=\"currentColor\" text-anchor=\"middle\">nsubj</textPath>\n",
       "    </text>\n",
       "    <path class=\"displacy-arrowhead\" d=\"M70,91.5 L62,79.5 78,79.5\" fill=\"currentColor\"/>\n",
       "</g>\n",
       "\n",
       "<g class=\"displacy-arrow\">\n",
       "    <path class=\"displacy-arc\" id=\"arrow-cad1874c1ca444bf97b9c0b815d63c9a-0-1\" stroke-width=\"2px\" d=\"M245,89.5 C245,2.0 400.0,2.0 400.0,89.5\" fill=\"none\" stroke=\"currentColor\"/>\n",
       "    <text dy=\"1.25em\" style=\"font-size: 0.8em; letter-spacing: 1px\">\n",
       "        <textPath xlink:href=\"#arrow-cad1874c1ca444bf97b9c0b815d63c9a-0-1\" class=\"displacy-label\" startOffset=\"50%\" side=\"left\" fill=\"currentColor\" text-anchor=\"middle\">dobj</textPath>\n",
       "    </text>\n",
       "    <path class=\"displacy-arrowhead\" d=\"M400.0,91.5 L408.0,79.5 392.0,79.5\" fill=\"currentColor\"/>\n",
       "</g>\n",
       "</svg></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "doc = nlp(\"I like cats\")\n",
    "displacy.render(doc, style=\"dep\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Spacy is a powerful tool \n",
    "- All my Capstone groups last year used this tool. \n",
    "- You can build your own rule-based searches. \n",
    "- You can also access word vectors using spaCy with bigger models. (Currently we are using `en_core_web_sm` model.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ❓❓ Questions for you"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.4: Discuss the following questions with your neighbours \n",
    "\n",
    "1. Why your text might become unreadable after stemming? \n",
    "2. What's the difference between sentence segmentation and word tokenization? Which step would you carry out first: sentence segmentation or word tokenization?\n",
    "3. Tokenize the following sentence and identify named entities in the sentence manually. Compare your annotations with what you get with spaCy. \n",
    "\n",
    "> The MadeUpOrg founder John Fakename lists his Point Grey penthouse for $15 million.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 2.4: V's Solutions!\n",
    ":class: tip, dropdown\n",
    "\n",
    "1. Stemming carries out crude chopping of affixes and converts words to reduced forms called stems. Often these reduced forms are not actual words. For instance, in the example we saw, _located_ was reduced to _locat_ and _beautiful_ was reduced to _beauti_. So after applying stemming the text might become unreadable. \n",
    "2. Sentence segmentation is about identifying sentence boundaries and splitting text into sentences whereas word tokenization is about identifying word boundaries and splitting sentences into words. The general practice is to carry out sentence segmentation before word tokenization. \n",
    "3. Manual NER: \n",
    "The [MadeUpOrg ORGANIZATION] founder [John Fakename PERSON] lists his [POINT Grey LOCATION] penthouse for [$15 million MONEY] . \n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span class=\"tex2jax_ignore\"><div class=\"entities\" style=\"line-height: 2.5; direction: ltr\">The MadeUpOrg founder \n",
       "<mark class=\"entity\" style=\"background: #aa9cfc; padding: 0.45em 0.6em; margin: 0 0.25em; line-height: 1; border-radius: 0.35em;\">\n",
       "    John Fakename\n",
       "    <span style=\"font-size: 0.8em; font-weight: bold; line-height: 1; border-radius: 0.35em; vertical-align: middle; margin-left: 0.5rem\">PERSON</span>\n",
       "</mark>\n",
       " lists his \n",
       "<mark class=\"entity\" style=\"background: #7aecec; padding: 0.45em 0.6em; margin: 0 0.25em; line-height: 1; border-radius: 0.35em;\">\n",
       "    Point Grey\n",
       "    <span style=\"font-size: 0.8em; font-weight: bold; line-height: 1; border-radius: 0.35em; vertical-align: middle; margin-left: 0.5rem\">ORG</span>\n",
       "</mark>\n",
       " penthouse for \n",
       "<mark class=\"entity\" style=\"background: #e4e7d2; padding: 0.45em 0.6em; margin: 0 0.25em; line-height: 1; border-radius: 0.35em;\">\n",
       "    $15 million\n",
       "    <span style=\"font-size: 0.8em; font-weight: bold; line-height: 1; border-radius: 0.35em; vertical-align: middle; margin-left: 0.5rem\">MONEY</span>\n",
       "</mark>\n",
       ".</div></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from spacy import displacy\n",
    "\n",
    "doc = nlp(\n",
    "    \"The MadeUpOrg founder John Fakename lists his Point Grey penthouse for $15 million.\"\n",
    ")\n",
    "displacy.render(doc, style=\"ent\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "spaCy was not able to identify ORGANIZATION and LOCATION entities in the sentence.   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Final comments, summary, and reflection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Summary: Language models  \n",
    "\n",
    "- A model that computes the probability of a sequence of words (or characters) or the probability of an upcoming word (or character) is called a **language model**.\n",
    "- Language models are central to many NLP applications such as smart compose, spelling correction, machine translations, voice assistants. \n",
    "- Markov models or **n-gram models** are language models with a long history. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Summary: Markov models \n",
    "\n",
    "- Markov models are the class of probabilistic models which assume that we can predict the probability of being in a particular state in future without looking too far into the past. \n",
    "- We looked at two applications of Markov models in language.\n",
    "    - N-gram language models\n",
    "    - PageRank\n",
    "- We can build character-based or word-based n-gram models.\n",
    "- We build a bigram model of language by assuming unique words or characters as states. \n",
    "- We can extend a bigram model by extending the definition of a state.     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Summary: PageRank\n",
    "- Another application of Markov chains in language is the PageRank algorithm. \n",
    "    - The intuition is that important webpages are linked from other important webpages."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Preprocessing\n",
    "\n",
    "- Preprocessing is an important step when you deal with text data.\n",
    "- Some common preprocessing steps include:\n",
    "    - Sentence segmentation\n",
    "    - Word tokenization\n",
    "    - Lemmatization\n",
    "    - Stemming\n",
    "- Some common tasks in NLP pipeline are:\n",
    "    - POS tagging\n",
    "    - Named-entity recognition\n",
    "    - Coreference resolution\n",
    "    - Dependency parsing "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Resources\n",
    "\n",
    "- [GPT-3 AI Automation](https://www.nytimes.com/2020/07/29/opinion/gpt-3-ai-automation.html)\n",
    "- [spaCy's Python for data science cheat sheet](http://datacamp-community-prod.s3.amazonaws.com/29aa28bf-570a-4965-8f54-d6a541ae4e06)\n",
    "\n",
    "- [Regular Expressions, Text Normalization, Edit Distance](https://web.stanford.edu/~jurafsky/slp3/2.pdf)\n",
    "- [Try preprocessing using unix shell](https://web.stanford.edu/class/cs124/lec/124-2020-UnixForPoets.pdf)\n",
    "- [Flair](https://github.com/flairNLP/flair) is another library with state-of-the-art NLP tools.  "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python [conda env:575]",
   "language": "python",
   "name": "conda-env-575-py"
  },
  "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.12.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}