Minitarea2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2obO44rRIDIm"
   },
   "source": [
    "# Minitarea 2\n",
    "\n",
    "Nombre: Miguel Videla A."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JstKx3TiKcIp"
   },
   "source": [
    "---------------------------\n",
    "## Language Models (3 pts)\n",
    "Estas preguntas son teóricas y deben ser resueltas con desarrollo, pero sin código. Por favor usen $\\LaTeX$ para las fórmulas. El material del curso y los videos deberian ser suficientes para que puedan responder."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2hwW-07MrRpt"
   },
   "source": [
    "\n",
    "### Pregunta 1 (1 pt)\n",
    "Asuma que tiene un modelo de lenguaje de trigramas (simple) entrenado sobre un corpus C. Muestre cómo el modelo le asigna una probabilidad a la oración `el perro le ladra al gato` usando los parámetros estimados a partir del corpus  $q(w_i | w_{i-2}, w_{i-1})$ ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5VUjDx0NrYbg"
   },
   "source": [
    "**Respuesta:**\n",
    "\n",
    "Sea $\\mathcal{C}$ un conjunto finito de palabras, el modelo de lenguaje de trigramas queda definido como un **proceso de Markov a tiempo discreto de segundo orden**, es decir, dado un proceso estocástico a tiempo discreto $X=(X_n)_{n\\in \\mathbb{N}}$, $\\forall w_0,w_1,...,w_n\\in \\mathcal{C}$ se satisface la propiedad de Markov de segundo orden:\n",
    "\\begin{equation}\n",
    "P(X_{n+1}=w_{n+1}|X_0=w_0,X_1=w_1,...,X_n=w_n)=P(X_{n+1}=w_{n+1}|X_n=w_n,X_{n-1}=w_{n-1})\n",
    "\\label{eq:markov} \\tag{1}\n",
    "\\end{equation}\n",
    "\n",
    "Sea $(\\text{'el','perro','le','ladra','al','gato'})=(w_1,w_2,w_3,w_4,w_5)$, la probabilidad de ocurrencia de la oración \"*el perro le ladra al gato*\" $q(w_1,w_2,w_3,w_4,w_5)$, dada la propiedad de regla de la cadena en probabilidades y la propiedad (1), queda determinada por:\n",
    "\\begin{equation}\n",
    "q(w_1,w_2,w_3,w_4,w_5)=\\prod_{i=1}^{5}q(w_i|w_{i-2},w_{i-1})\n",
    "\\label{eq:trigram} \\tag{2}\n",
    "\\end{equation}\n",
    "\n",
    "con $w_0=w_{-1}=*$. Se observa que el modelo debe ser capaz de estimar probabilidades de secuencias de palabras de largo variable, por lo que dada la probabilidad de un trigrama $q(u|v,w)$, se tiene que $u\\in \\mathcal{C} \\cup \\{STOP\\}$ y $v,w\\in \\mathcal{C}\\cup \\{*\\}$, con $STOP$ el símbolo de término de una secuencia de palabras y $*$ el símbolo de inicio de secuencia, tal que $\\forall i\\in\\{1,2,...,|\\mathcal{C}|\\}$, $q(w_{i}|*,w_{i-1})=q(w_{i}|w_{i-1})$ y $q(w_{i}|*,*)=q(w_{i})$.\n",
    "\n",
    "Finalmente, la estimación empírica de las probabilides condicionales sobre $\\mathcal{C}$ se calcula como:\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "\\hat{q}_{ML}(w_i|w_{i-2},w_{i-1})&=\\frac{count(w_i,w_{i-1},w_{i-2})}{count(w_{i-1},w_{i-2})}\\\\\n",
    "\\hat{q}_{ML}(w_i|w_{i-1})&=\\frac{count(w_i,w_{i-1})}{count(w_{i-1})}\\\\\n",
    "\\hat{q}_{ML}(w_i)&=\\frac{count(w_i)}{|\\mathcal{C}|}\n",
    "\\end{split}\n",
    "\\label{eq:ml} \\tag{3}\n",
    "\\end{equation}\n",
    "\n",
    "los cuales corresponden a la **estimación de máxima verosimilitud** de los modelos trigramas, bigramas y unigramas, respectivamente."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "bwNkPIXure0C"
   },
   "source": [
    "### Pregunta 2 (1 pt)\n",
    "Muestre cómo se calcularía  $q(w_{i} | w_{i-2}, w_{i-1})$  usando un modelo que interpola un modelo de lenguajes de trigramas, bigramas, y unigrama."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zeLZAd0Tr9ne"
   },
   "source": [
    "**Respuesta:**\n",
    "\n",
    "El modelo interpolado corresponde a una **suma ponderada de las estimaciones de máxima verosimilitud** de cada modelo (3). De este modo, la probabilidad de $q(w_{i} | w_{i-2}, w_{i-1})$ del modelo ponderado resulta:\n",
    "\\begin{equation}\n",
    "q(w_{i} | w_{i-2}, w_{i-1}) = \\lambda_1\\cdot \\hat{q}_{ML}(w_{i} | w_{i-2}, w_{i-1})+\\lambda_2\\cdot \\hat{q}_{ML}(w_{i} | w_{i-1})+\\lambda_3\\cdot \\hat{q}_{ML}(w_{i})\n",
    "\\label{eq:interpolation_model} \\tag{4}\n",
    "\\end{equation}\n",
    "\n",
    "con $\\lambda_j\\geq 0$, $\\forall j\\in\\{1,2,3\\}$ y $\\lambda_1+\\lambda_2+\\lambda_3=1$.\n",
    "\n",
    "Los valores $\\lambda_j$ se obtienen mediante la resolución del siguinte problema de optimización:\n",
    "\\begin{equation}\n",
    "(\\lambda_1^*,\\lambda_2^*,\\lambda_3^*)=\\underset{\\lambda_1,\\lambda_2,\\lambda_3}{argmax} \\sum_{w_1,w_2,w_3\\in\\mathcal{C}_{validation}}c'(w_1,w_2,w_3)\\log q(w_{i} | w_{i-2}, w_{i-1})\n",
    "\\label{eq:L_lambda} \\tag{5}\n",
    "\\end{equation}\n",
    "\n",
    "sujeto a las restricciones anteriores, con $\\mathcal{C}=\\mathcal{C}_{train} \\dot\\cup \\mathcal{C}_{validation}$, $c'(w_1,w_2,w_3)$ la cantidad de ocurrencias de $(w_1,w_2,w_3)$ en $\\mathcal{C}_{validation}$ y $\\mathcal{C}_{train}$ el conjunto utilizado para estimar las probabilidades en (3)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "sHqcRJ7Vr_8x"
   },
   "source": [
    "### Pregunta 3 (1 pt)\n",
    "¿Qué ventajas tiene el modelo interpolado sobre el modelo de trigramas simple?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6F5R3Ji7sHjt"
   },
   "source": [
    "**Respuesta:**\n",
    "\n",
    "Dependiendo del corpus utilizado será preferible utilizar algún respectivo modelo n-grama. El modelo interpolado permite incorporar de manera óptima los distintos modelos n-gramas, ponderando la predicción de cada uno de acuerdo al conjuto de validación presentado, con el objetivo de minimizar la *perplexity* del modelo, y por tanto, robusteciendo su desempeño frente a nuevas muestras de *test*. Una menor *perplexity* implica una mayor certeza en la predicción de ejemplos de *test*, asignándole mayor probabilidad (el modelo está menos sorprendido al presentarle nuevas muestras a predecir).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rdmB-07ZKfaa"
   },
   "source": [
    "-----------------------\n",
    "## Naive Bayes (3 pts)\n",
    "En esta parte de la minitarea deberan programar Naive Bayes Multinomial usando Laplace Smothing. Las referencias las pueden encontrar en el material del curso y los videos del profesor.\n",
    "\n",
    "A continuacion se presentan un conjunto de documentos de training divididos en 2 categorias distintas. Ustedes deberan clasificar los documentos del test set usando Naive Bayes con Laplace Smothing.\n",
    "\n",
    "Por favor, documenten su codigo. Escriban que hacen las funciones, que reciben, que entregan, etc. Si en algun lugar de su codigo hacen algo que creen que debe ser explicado, pongan comentarios, son bienvenidos. \n",
    "\n",
    "\n",
    "**Underflow prevention:** En vez de hacer muchas multiplicacions de `float`s, reemplacenlas por sumas de logaritmos para prevenir errores de precision. Revisen la diapo 69 de las slides. \n",
    "\n",
    "NOTA: Sobre las `namedtuple`s. Es el tipo de los documentos. Son objetos inmutable que tienen dos atributos: `words` donde estan las palabras del documento y `class_` donde se guarda la clase de ese documento. Estos objetos son inmutables, lo que quiere decir que si quieren modificar un documento y cambiarle la clase, tienen que crear otro documento. Otra cosa es que son tuplas como cualquier otra, es decir se pueden acceder usando indices como `doc[0]` o `doc[1]`. Son libres de implementar su solucion como quieran, si no les gusta este tipo de dato usen otro.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 225
    },
    "colab_type": "code",
    "id": "HLi8PxdV2VQX",
    "outputId": "efd50e50-3317-454b-c74f-222458249c48"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train documents:\n",
      "(document(words=('w03', 'w01', 'w02', 'w06', 'w02', 'w08', 'w07'), class_=0),\n",
      " document(words=('w05', 'w04', 'w00', 'w06', 'w09', 'w07', 'w06', 'w09', 'w05'), class_=1),\n",
      " document(words=('w07', 'w06', 'w00', 'w08', 'w01', 'w08', 'w08', 'w09', 'w02'), class_=0),\n",
      " document(words=('w08', 'w09', 'w02', 'w06', 'w05', 'w08', 'w07'), class_=1),\n",
      " document(words=('w09', 'w08', 'w05', 'w08', 'w05', 'w00', 'w08'), class_=1),\n",
      " document(words=('w05', 'w05', 'w06', 'w01', 'w06', 'w08', 'w02'), class_=1),\n",
      " document(words=('w04', 'w03', 'w07', 'w05', 'w04', 'w00', 'w02'), class_=0),\n",
      " document(words=('w01', 'w00', 'w01', 'w04', 'w09', 'w02', 'w04', 'w07'), class_=1))\n",
      "\n",
      "Test documents:\n",
      "(document(words=('w02', 'w09', 'w06', 'w01', 'w05', 'w04', 'w03', 'w03'), class_=None),)\n"
     ]
    }
   ],
   "source": [
    "from pprint import pprint\n",
    "from collections import namedtuple\n",
    "document = namedtuple(\n",
    "    \"document\", (\"words\", \"class_\")  # avoid python's keyword collision\n",
    ")\n",
    "\n",
    "train_set = (\n",
    "    document(words=('w03', 'w01', 'w02', 'w06', 'w02', 'w08', 'w07'), class_=0),\n",
    "    document(words=('w05', 'w04', 'w00', 'w06', 'w09', 'w07', 'w06', 'w09', 'w05'), class_=1),\n",
    "    document(words=('w07', 'w06', 'w00', 'w08', 'w01', 'w08', 'w08', 'w09', 'w02'), class_=0),\n",
    "    document(words=('w08', 'w09', 'w02', 'w06', 'w05', 'w08', 'w07'), class_=1),\n",
    "    document(words=('w09', 'w08', 'w05', 'w08', 'w05', 'w00', 'w08'), class_=1),\n",
    "    document(words=('w05', 'w05', 'w06', 'w01', 'w06', 'w08', 'w02'), class_=1),\n",
    "    document(words=('w04', 'w03', 'w07', 'w05', 'w04', 'w00', 'w02'), class_=0),\n",
    "    document(words=('w01', 'w00', 'w01', 'w04', 'w09', 'w02', 'w04', 'w07'), class_=1)\n",
    ")\n",
    "print(\"Train documents:\")\n",
    "pprint(train_set)\n",
    "\n",
    "\n",
    "test_set = (document(words=('w02', 'w09', 'w06', 'w01', 'w05', 'w04', 'w03', 'w03'), class_=None),)\n",
    "print(\"\\nTest documents:\")\n",
    "pprint(test_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Predictions:\n",
      "[0]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "class MultinomialNaiveBayes():\n",
    "    \"\"\"Multinomial Naive Bayes language model with smoothing\"\"\"\n",
    "    def __init__(self, smoothing_factor=0):\n",
    "        \"\"\"\n",
    "        Initializes the class attributes\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        smoothing_factor : float\n",
    "            Smoothing factor of estimated maximum likelihood probability \n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        None      \n",
    "        \"\"\"\n",
    "        self.smoothing_factor = smoothing_factor\n",
    "        self.docs = None\n",
    "        self.docs_classes = None\n",
    "        self.classes = None\n",
    "    \n",
    "    def fit(self, corpus):\n",
    "        \"\"\"\n",
    "        Set the class attributes according to a corpus\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        corpus : tuple(document)\n",
    "            A tuple with the documents(words, class_) of the corpus\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        None  \n",
    "        \"\"\"\n",
    "        self.docs = []\n",
    "        self.docs_classes = []\n",
    "        for doc, class_ in corpus:\n",
    "            self.docs.append(np.array(doc))\n",
    "            self.docs_classes.append(class_)\n",
    "        self.docs = np.array(self.docs)\n",
    "        self.docs_classes = np.array(self.docs_classes)\n",
    "        self.classes = np.unique(self.docs_classes)\n",
    "            \n",
    "    def get_vocabulary(self, class_=None, return_counts=False):\n",
    "        \"\"\"\n",
    "        Return the vocabulary according to the documents array class attribute\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        class_ : int, optional\n",
    "            If is not None returns the vocabulary of the documents array class attribute of the given class\n",
    "        return_counts : bool, optional\n",
    "            If true return a tuple with vocabulary and the number of ocurrences\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        array(str)\n",
    "            Corpus vocabulary\n",
    "        \"\"\"\n",
    "        vocab = []\n",
    "        for i in range(len(self.docs)):\n",
    "            if (self.docs_classes[i] == class_) or (class_ is None):\n",
    "                vocab += list(self.docs[i])\n",
    "        return np.unique(vocab, return_counts=return_counts)\n",
    "        \n",
    "    def prior(self, class_):\n",
    "        \"\"\"\n",
    "        Calculates the estimated prior probability\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        class_ : int\n",
    "            A class of corpus documents\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        float\n",
    "            Number of documents of a class in the corpus divided by the total number of documents\n",
    "        \"\"\"\n",
    "        return (self.docs_classes == class_).sum() / len(self.docs)\n",
    "    \n",
    "    def likelihood(self, word, class_):\n",
    "        \"\"\"\n",
    "        Calculates the estimated likelihood probability\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        word : str\n",
    "            An input word\n",
    "        class_ : int\n",
    "            A class of corpus documents\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        float\n",
    "            Number of occurences of the input word in the corpus divided by the number of words in the \n",
    "            documents of the corpus with class equals to the input class (smoothed)\n",
    "        \"\"\"\n",
    "        vocab = self.get_vocabulary()\n",
    "        class_vocab, class_ocurrences = self.get_vocabulary(class_, True)\n",
    "        ocurrence_idxs = np.argwhere(class_vocab == word)\n",
    "        if len(ocurrence_idxs) == 0:\n",
    "            word_ocurrences = 0\n",
    "        else:   \n",
    "            word_ocurrences = class_ocurrences[ocurrence_idxs[0][0]]\n",
    "        return (word_ocurrences + self.smoothing_factor) / (class_ocurrences.sum() + self.smoothing_factor * len(vocab))\n",
    "    \n",
    "    def log_posterior(self, doc, class_):\n",
    "        \"\"\"\n",
    "        Calculates the estimated log-posterior probability according to the Bayes theorem\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        doc : array(str)\n",
    "            Input document\n",
    "        class_ : int\n",
    "            A class of corpus documents\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        float\n",
    "            Class log prior plus sum of log likelihood of each word in document\n",
    "        \"\"\"\n",
    "        log_post = np.log(self.prior(class_))\n",
    "        for word in doc:\n",
    "            log_post += np.log(self.likelihood(word, class_))\n",
    "        return log_post\n",
    "    \n",
    "    def class_prediction(self, doc):\n",
    "        \"\"\"\n",
    "        Return the class prediction of a given document according to the maximum a posteriri estimation\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        doc : array(str)\n",
    "            Input document\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        int\n",
    "            Predicted class\n",
    "        \"\"\"\n",
    "        return self.classes[np.argmax([self.log_posterior(doc, class_) for class_ in self.classes])]\n",
    "\n",
    "    def predict(self, doc_tuples):\n",
    "        \"\"\"\n",
    "        Return the class predictions of each document of the input corpus\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        doc_tuples : tuple(documents)\n",
    "            Input document\n",
    "\n",
    "        Returns\n",
    "        -------\n",
    "        array(int)\n",
    "            Predicted class for each document\n",
    "        \"\"\"\n",
    "        return np.array([self.class_prediction(doc_tuple[0]) for doc_tuple in doc_tuples])\n",
    "\n",
    "# Class initialization\n",
    "nb = MultinomialNaiveBayes(smoothing_factor=1)\n",
    "# Training corpus set fitting\n",
    "nb.fit(train_set)\n",
    "# Test corpus set prediction\n",
    "predictions = nb.predict(test_set)\n",
    "print(\"Predictions:\\n{}\".format(predictions))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "minitarea2.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}