NLP2122_Practical1_Jesse_Lizzy.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "NLP2122_Practical1_Jesse_Lizzy.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "display_name": "Python 3 (ipykernel)",
      "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.9.7"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1-aRiOgl4nHg"
      },
      "source": [
        "------\n",
        "**You cannot save any changes you make to this file, so please make sure to save it on your Google Colab drive or download it as a .ipynb file.**\n",
        "\n",
        "------\n",
        "\n",
        " "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lIZrAUx57vsM"
      },
      "source": [
        "Practical 1: Sentiment Detection in Movie Reviews\n",
        "========================================\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "J4kXPMhyngZW"
      },
      "source": [
        "This practical concerns detecting sentiment in movie reviews. This is a typical NLP classification task.\n",
        "In [this file](https://gist.githubusercontent.com/bastings/d47423301cca214e3930061a5a75e177/raw/5113687382919e22b1f09ce71a8fecd1687a5760/reviews.json) (80MB) you will find 1000 positive and 1000 negative **movie reviews**.\n",
        "Each review is a **document** and consists of one or more sentences.\n",
        "\n",
        "To prepare yourself for this practical, you should\n",
        "have a look at a few of these texts to understand the difficulties of\n",
        "the task: how might one go about classifying the texts? You will write\n",
        "code that decides whether a movie review conveys positive or\n",
        "negative sentiment.\n",
        "\n",
        "Please make sure you have read the following paper:\n",
        "\n",
        ">   Bo Pang, Lillian Lee, and Shivakumar Vaithyanathan\n",
        "(2002). \n",
        "[Thumbs up? Sentiment Classification using Machine Learning\n",
        "Techniques](https://dl.acm.org/citation.cfm?id=1118704). EMNLP.\n",
        "\n",
        "Bo Pang et al. introduced the movie review sentiment\n",
        "classification task, and the above paper was one of the first papers on\n",
        "the topic. The first version of your sentiment classifier will do\n",
        "something similar to Pang et al.'s system. If you have questions about it,\n",
        "you should resolve you doubts as soon as possible with your TA.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cb7errgRASzZ"
      },
      "source": [
        "**Advice**\n",
        "\n",
        "Please read through the entire practical and familiarise\n",
        "yourself with all requirements before you start coding or otherwise\n",
        "solving the tasks. Writing clean and concise code can make the difference\n",
        "between solving the assignment in a matter of hours, and taking days to\n",
        "run all experiments.\n",
        "\n",
        "## Environment\n",
        "\n",
        "All code should be written in **Python 3**. \n",
        "This is the default in Google Colab."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "SaZnxptMJiD7",
        "outputId": "ee5c55a4-ca9b-4863-e780-d77763d61a72"
      },
      "source": [
        "!python --version"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Python 3.7.12\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BYZyIF7lJnGn"
      },
      "source": [
        "If you want to run code on your own computer, then download this notebook through `File -> Download .ipynb`.\n",
        "The easiest way to\n",
        "install Python is through downloading\n",
        "[Anaconda](https://www.anaconda.com/download). \n",
        "After installation, you can start the notebook by typing `jupyter notebook filename.ipynb`.\n",
        "You can also use an IDE\n",
        "such as [PyCharm](https://www.jetbrains.com/pycharm/download/) to make\n",
        "coding and debugging easier. It is good practice to create a [virtual\n",
        "environment](https://docs.python.org/3/tutorial/venv.html) for this\n",
        "project, so that any Python packages don’t interfere with other\n",
        "projects. \n",
        " \n",
        "\n",
        "**Learning Python 3**\n",
        "\n",
        "If you are new to Python 3, you may want to check out a few of these resources:\n",
        "- https://learnxinyminutes.com/docs/python3/\n",
        "- https://www.learnpython.org/\n",
        "- https://docs.python.org/3/tutorial/"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hok-BFu9lGoK"
      },
      "source": [
        "import math\n",
        "import os\n",
        "import sys\n",
        "from subprocess import call\n",
        "from nltk import FreqDist\n",
        "from nltk.util import ngrams\n",
        "from nltk.stem.porter import PorterStemmer\n",
        "import sklearn as sk\n",
        "import pickle\n",
        "import json\n",
        "\n",
        "import collections\n",
        "from collections import Counter\n",
        "# import requests\n",
        "\n",
        "import matplotlib.pyplot as plt\n",
        "import numpy as np\n",
        "\n",
        "# extra imports\n",
        "from dataclasses import dataclass\n",
        "import copy"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bXWyGHwE-ieQ"
      },
      "source": [
        "## Loading the data\n",
        "\n",
        "**Download the sentiment lexicon and the movie reviews dataset.**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lm-rakqtlMOT",
        "outputId": "94aef15e-1db4-48c6-9204-937c7e86f550"
      },
      "source": [
        "# download sentiment lexicon\n",
        "if not os.path.exists('./reviews.json'):\n",
        "    !wget https://gist.githubusercontent.com/bastings/d6f99dcb6c82231b94b013031356ba05/raw/f80a0281eba8621b122012c89c8b5e2200b39fd6/sent_lexicon\n",
        "    # download review data\n",
        "    !wget https://gist.githubusercontent.com/bastings/d47423301cca214e3930061a5a75e177/raw/5113687382919e22b1f09ce71a8fecd1687a5760/reviews.json"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "--2021-11-17 16:52:54--  https://gist.githubusercontent.com/bastings/d6f99dcb6c82231b94b013031356ba05/raw/f80a0281eba8621b122012c89c8b5e2200b39fd6/sent_lexicon\n",
            "Resolving gist.githubusercontent.com (gist.githubusercontent.com)... 185.199.111.133, 185.199.109.133, 185.199.108.133, ...\n",
            "Connecting to gist.githubusercontent.com (gist.githubusercontent.com)|185.199.111.133|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 662577 (647K) [text/plain]\n",
            "Saving to: ‘sent_lexicon’\n",
            "\n",
            "sent_lexicon        100%[===================>] 647.05K  --.-KB/s    in 0.05s   \n",
            "\n",
            "2021-11-17 16:52:54 (13.9 MB/s) - ‘sent_lexicon’ saved [662577/662577]\n",
            "\n",
            "--2021-11-17 16:52:54--  https://gist.githubusercontent.com/bastings/d47423301cca214e3930061a5a75e177/raw/5113687382919e22b1f09ce71a8fecd1687a5760/reviews.json\n",
            "Resolving gist.githubusercontent.com (gist.githubusercontent.com)... 185.199.111.133, 185.199.109.133, 185.199.108.133, ...\n",
            "Connecting to gist.githubusercontent.com (gist.githubusercontent.com)|185.199.111.133|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 83503869 (80M) [text/plain]\n",
            "Saving to: ‘reviews.json’\n",
            "\n",
            "reviews.json        100%[===================>]  79.63M   166MB/s    in 0.5s    \n",
            "\n",
            "2021-11-17 16:52:55 (166 MB/s) - ‘reviews.json’ saved [83503869/83503869]\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AkPwuHp5LSuQ"
      },
      "source": [
        "**Load the movie reviews.**\n",
        "\n",
        "Each word in a review comes with its part-of-speech tag. For documentation on POS-tags, see https://catalog.ldc.upenn.edu/docs/LDC99T42/tagguid1.pdf.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "careEKj-mRpl",
        "outputId": "390cf2ed-7d16-41b3-ff71-2f52c6031825"
      },
      "source": [
        "# file structure:\n",
        "# [\n",
        "#  {\"cv\": integer, \"sentiment\": str, \"content\": list} \n",
        "#  {\"cv\": integer, \"sentiment\": str, \"content\": list} \n",
        "#   ..\n",
        "# ]\n",
        "# where `content` is a list of sentences, \n",
        "# with a sentence being a list of (token, pos_tag) pairs.\n",
        "\n",
        "\n",
        "with open(\"reviews.json\", mode=\"r\", encoding=\"utf-8\") as f:\n",
        "  reviews = json.load(f)\n",
        "  \n",
        "print(\"Total number of reviews:\", len(reviews), '\\n')\n",
        "\n",
        "def print_sentence_with_pos(s):\n",
        "  print(\" \".join(\"%s/%s\" % (token, pos_tag) for token, pos_tag in s))\n",
        "\n",
        "for i, r in enumerate(reviews):\n",
        "  print(r[\"cv\"], r[\"sentiment\"], len(r[\"content\"]))  # cv, sentiment, num sents\n",
        "  print_sentence_with_pos(r[\"content\"][0])\n",
        "  if i == 4: \n",
        "    break\n",
        "    \n",
        "c = Counter()\n",
        "for review in reviews:\n",
        "  for sentence in review[\"content\"]:\n",
        "    for token, pos_tag in sentence:\n",
        "      c[token] += 1\n",
        "      \n",
        "print(\"\\nNumber of word types:\", len(c))\n",
        "print(\"Number of word tokens:\", sum(c.values()))\n",
        "\n",
        "print(\"\\nMost common tokens:\")\n",
        "for token, count in c.most_common(20):\n",
        "  print(\"%10s : %8d\" % (token, count))\n",
        "  "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Total number of reviews: 2000 \n",
            "\n",
            "0 NEG 29\n",
            "Two/CD teen/JJ couples/NNS go/VBP to/TO a/DT church/NN party/NN ,/, drink/NN and/CC then/RB drive/NN ./.\n",
            "1 NEG 11\n",
            "Damn/JJ that/IN Y2K/CD bug/NN ./.\n",
            "2 NEG 24\n",
            "It/PRP is/VBZ movies/NNS like/IN these/DT that/WDT make/VBP a/DT jaded/JJ movie/NN viewer/NN thankful/JJ for/IN the/DT invention/NN of/IN the/DT Timex/NNP IndiGlo/NNP watch/NN ./.\n",
            "3 NEG 19\n",
            "QUEST/NN FOR/IN CAMELOT/NNP ``/`` Quest/NNP for/IN Camelot/NNP ''/'' is/VBZ Warner/NNP Bros./NNP '/POS first/JJ feature-length/JJ ,/, fully-animated/JJ attempt/NN to/TO steal/VB clout/NN from/IN Disney/NNP 's/POS cartoon/NN empire/NN ,/, but/CC the/DT mouse/NN has/VBZ no/DT reason/NN to/TO be/VB worried/VBN ./.\n",
            "4 NEG 38\n",
            "Synopsis/NNPS :/: A/DT mentally/RB unstable/JJ man/NN undergoing/VBG psychotherapy/NN saves/VBZ a/DT boy/NN from/IN a/DT potentially/RB fatal/JJ accident/NN and/CC then/RB falls/VBZ in/IN love/NN with/IN the/DT boy/NN 's/POS mother/NN ,/, a/DT fledgling/NN restauranteur/NN ./.\n",
            "\n",
            "Number of word types: 55384\n",
            "Number of word tokens: 1512359\n",
            "\n",
            "Most common tokens:\n",
            "         , :    77842\n",
            "       the :    64890\n",
            "         . :    59027\n",
            "         a :    36338\n",
            "       and :    33467\n",
            "        of :    33230\n",
            "        to :    31202\n",
            "        is :    25765\n",
            "        in :    19715\n",
            "        's :    17863\n",
            "      that :    15174\n",
            "        it :    12666\n",
            "     -RRB- :    11768\n",
            "     -LRB- :    11670\n",
            "        as :    10329\n",
            "      with :    10286\n",
            "       The :     9945\n",
            "      film :     9326\n",
            "        '' :     9282\n",
            "       for :     9247\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E6PWaEoh8B34"
      },
      "source": [
        "# Lexicon-based approach (3.5pts)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JsTSMb6ma4E8"
      },
      "source": [
        "A traditional approach to classify documents according to their sentiment is the lexicon-based approach. To implement this approach, you need a **sentiment lexicon**, i.e., a list of words annotated with a sentiment label (e.g., positive and negative, or a score from 0 to 5).\n",
        "\n",
        "In this practical, you will use the sentiment\n",
        "lexicon released by Wilson et al. (2005).\n",
        "\n",
        "> Theresa Wilson, Janyce Wiebe, and Paul Hoffmann\n",
        "(2005). [Recognizing Contextual Polarity in Phrase-Level Sentiment\n",
        "Analysis](http://www.aclweb.org/anthology/H/H05/H05-1044.pdf). HLT-EMNLP.\n",
        "\n",
        "Pay attention to all the information available in the sentiment lexicon. The field *word1* contains the lemma, *priorpolarity* contains the sentiment label (positive, negative, both, or neutral), *type* gives you the magnitude of the word's sentiment (strong or weak), and *pos1* gives you the part-of-speech tag of the lemma. Some lemmas can have multiple part-of-speech tags and thus multiple entries in the lexicon. The path of the lexicon file is `\"sent_lexicon\"`.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "akIcwv0lzjeP"
      },
      "source": [
        "def map_sentences(data, fn):\n",
        "    result = []\n",
        "    for datapoint in data:\n",
        "        new_data_point = {key: value for key, value in datapoint.items()}\n",
        "        new_data_point['content'] = fn(datapoint['content'])\n",
        "        result.append(new_data_point)\n",
        "    \n",
        "    return result\n",
        "\n",
        "def sentences_to_lower_case(sentences):\n",
        "    return [[(word.lower(), pos) for word, pos in sentence] for sentence in sentences]\n",
        "\n",
        "reviews = map_sentences(reviews, sentences_to_lower_case)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ogq0Eq2hQglh",
        "outputId": "1ffbb546-2183-4f19-fba7-3b1aafcfb377"
      },
      "source": [
        "with open(\"sent_lexicon\", mode=\"r\", encoding=\"utf-8\") as f:\n",
        "  line_cnt = 0\n",
        "  for line in f:\n",
        "    print(line.strip())\n",
        "    line_cnt += 1\n",
        "    if line_cnt > 10:\n",
        "      break"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "type=weaksubj len=1 word1=abandoned pos1=adj stemmed1=n priorpolarity=negative\n",
            "type=weaksubj len=1 word1=abandonment pos1=noun stemmed1=n priorpolarity=negative\n",
            "type=weaksubj len=1 word1=abandon pos1=verb stemmed1=y priorpolarity=negative\n",
            "type=strongsubj len=1 word1=abase pos1=verb stemmed1=y priorpolarity=negative\n",
            "type=strongsubj len=1 word1=abasement pos1=anypos stemmed1=y priorpolarity=negative\n",
            "type=strongsubj len=1 word1=abash pos1=verb stemmed1=y priorpolarity=negative\n",
            "type=weaksubj len=1 word1=abate pos1=verb stemmed1=y priorpolarity=negative\n",
            "type=weaksubj len=1 word1=abdicate pos1=verb stemmed1=y priorpolarity=negative\n",
            "type=strongsubj len=1 word1=aberration pos1=adj stemmed1=n priorpolarity=negative\n",
            "type=strongsubj len=1 word1=aberration pos1=noun stemmed1=n priorpolarity=negative\n",
            "type=strongsubj len=1 word1=abhor pos1=anypos stemmed1=y priorpolarity=negative\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Mml4nOtIUBhn"
      },
      "source": [
        "Lexica such as this can be used to solve\n",
        "the classification task without using Machine Learning. For example, one might look up every word $w_1 ... w_n$ in a document, and compute a **binary score**\n",
        "$S_{binary}$ by counting how many words have a positive or a\n",
        "negative label in the sentiment lexicon $SLex$.\n",
        "\n",
        "$$S_{binary}(w_1 w_2 ... w_n) = \\sum_{i = 1}^{n}\\text{sign}(SLex\\big[w_i\\big])$$\n",
        "\n",
        "where $\\text{sign}(SLex\\big[w_i\\big])$ refers to the polarity of $w_i$.\n",
        "\n",
        "**Threshold.** On average, there are more positive than negative words per review (~7.13 more positive than negative per review) to take this bias into account you should use a threshold of **8** (roughly the bias itself) to make it harder to classify as positive.\n",
        "\n",
        "$$\n",
        "\\text{classify}(S_{binary}(w_1 w_2 ... w_n)) = \\bigg\\{\\begin{array}{ll}\n",
        "        \\text{positive} & \\text{if } S_{binary}(w_1w_2...w_n) > threshold\\\\\n",
        "        \\text{negative} & \\text{otherwise}\n",
        "        \\end{array}\n",
        "$$\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tOFnMvbeeZrc"
      },
      "source": [
        "#### (Q1.1) Implement this approach and report its classification accuracy. (1 pt)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ED2aTEYutW1-",
        "outputId": "76f61bff-8ce6-4836-f5ae-b002ce62f6d6"
      },
      "source": [
        "def parse_lexicon():\n",
        "  result = dict()\n",
        "  with open(\"sent_lexicon\", mode=\"r\", encoding=\"utf-8\") as lexicon_file:\n",
        "    for line in lexicon_file:\n",
        "      [type_elem, _, word, pos, _, priorpolarity] = [elem.split('=')[1] for elem in line.split(' ')]\n",
        "      result[word] = (type_elem, priorpolarity[:-1])\n",
        "  \n",
        "  return result\n",
        "    \n",
        "def classify_sbinary(sentences, lexicon_dict):\n",
        "    sbinary = 0\n",
        "    for sentence in sentences:\n",
        "        for token, pos in sentence:\n",
        "            type_and_priorpolairty = lexicon_dict.get((token))\n",
        "            \n",
        "            # print(type_and_priorpolairty)\n",
        "            \n",
        "            if type_and_priorpolairty is not None:\n",
        "                _, priorpolairty = type_and_priorpolairty\n",
        "            \n",
        "                # print(priorpolairty)\n",
        "            \n",
        "                if priorpolairty == \"negative\":\n",
        "                    sbinary -= 1\n",
        "                elif priorpolairty == \"positive\":\n",
        "                    sbinary += 1\n",
        "\n",
        "    \n",
        "                    \n",
        "    return sbinary >= 8\n",
        "\n",
        "lexicon_dict = parse_lexicon()\n",
        "\n",
        "correct = 0\n",
        "total = 0\n",
        "for review in reviews:\n",
        "    sentiment_positive = review['sentiment'] == 'POS'\n",
        "    prediction_positive = classify_sbinary(review['content'], lexicon_dict)\n",
        "    \n",
        "    total += 1\n",
        "    if sentiment_positive == prediction_positive:\n",
        "        correct += 1\n",
        "        \n",
        "\n",
        "print(correct, '/', total)\n",
        "print(correct / total)  "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1358 / 2000\n",
            "0.679\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iy528EUTphz5",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "daa37c6e-1146-4219-e10e-33551f044137"
      },
      "source": [
        "# token_results should be a list of binary indicators; for example [1, 0, 1, ...] \n",
        "# where 1 indicates a correct classification and 0 an incorrect classification.\n",
        "\n",
        "reals = [review['sentiment'] == 'POS' for review in reviews]\n",
        "\n",
        "token_results = [\n",
        "    classify_sbinary(review['content'], lexicon_dict)\n",
        "    for\n",
        "    review in reviews\n",
        "]\n",
        "token_accuracy = sum((real == prediction for real, prediction in zip(reals, token_results))) / len(token_results)\n",
        "print(\"Accuracy: %0.2f\" % token_accuracy)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Accuracy: 0.68\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Twox0s_3eS0V"
      },
      "source": [
        "As the sentiment lexicon also has information about the **magnitude** of\n",
        "sentiment (e.g., *“excellent\"* has the same sentiment _polarity_ as *“good\"* but it has a higher magnitude), we can take a more fine-grained approach by adding up all\n",
        "sentiment scores, and deciding the polarity of the movie review using\n",
        "the sign of the weighted score $S_{weighted}$.\n",
        "\n",
        "$$S_{weighted}(w_1w_2...w_n) = \\sum_{i = 1}^{n}SLex\\big[w_i\\big]$$\n",
        "\n",
        "\n",
        "Make sure you define an appropriate threshold for this approach.\n",
        "\n",
        "#### (Q1.2) Now incorporate magnitude information and report the classification accuracy. Don't forget to use the threshold. (1pt)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qG3hUDnPtkhS"
      },
      "source": [
        "def classify_sweighted(sentences, lexicon_dict, weak_strength=0.2, strong_strength=1, threshold=6):\n",
        "    sbinary = 0\n",
        "    for sentence in sentences:\n",
        "        for token, pos in sentence:\n",
        "            type_and_priorpolairty = lexicon_dict.get((token))\n",
        "                        \n",
        "            if type_and_priorpolairty is not None:\n",
        "                strength_type, priorpolairty = type_and_priorpolairty\n",
        "                            \n",
        "                strength = weak_strength if strength_type == 'weaksubj' else strong_strength\n",
        "                            \n",
        "                if priorpolairty == \"negative\":\n",
        "                    sbinary -= strength\n",
        "                elif priorpolairty == \"positive\":\n",
        "                    sbinary += strength\n",
        "    \n",
        "    return sbinary >= threshold\n",
        "\n",
        "def best_params(fn, weak_strengths, thresholds):\n",
        "    reals = [review['sentiment'] == 'POS' for review in reviews]\n",
        "    \n",
        "    best = (None, None)\n",
        "    best_accuracy = -100\n",
        "\n",
        "    for weak_strength in weak_strengths:\n",
        "        for threshold in thresholds:\n",
        "            token_results = [\n",
        "                fn(review['content'], lexicon_dict, weak_strength, 1, threshold)\n",
        "                for\n",
        "                review in reviews\n",
        "            ]\n",
        "            token_accuracy = sum((real == prediction for real, prediction in zip(reals, token_results))) / len(token_results)\n",
        "            \n",
        "            if token_accuracy > best_accuracy:\n",
        "                best_accuracy = token_accuracy\n",
        "                best = (weak_strength, threshold)\n",
        "                \n",
        "            print(token_accuracy, weak_strength, threshold)\n",
        "    return best, best_accuracy\n",
        "\n",
        "if False:\n",
        "    print(best_params(classify_sweighted, [0.1, 0.15, 0.2, 0.5, 0.7], [2, 4, 6, 8, 10, 12, 14]))\n",
        "    "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9vVk7CvDpyka",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3a2c7189-2b8c-4c30-e8e9-ff3ae2803bfe"
      },
      "source": [
        "reals = [review['sentiment'] == 'POS' for review in reviews]\n",
        "magnitude_results = [\n",
        "    classify_sweighted(review['content'], lexicon_dict)\n",
        "    for\n",
        "    review in reviews\n",
        "]\n",
        "magnitude_accuracy = sum((real == prediction for real, prediction in zip(reals, magnitude_results))) / len(token_results)\n",
        "print(\"Accuracy: %0.2f\" % magnitude_accuracy)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Accuracy: 0.70\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h9SHoGPfsAHV"
      },
      "source": [
        "#### (Q.1.4) Make a barplot of the two results (0.5pt)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8LgBcYcXsEk3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 282
        },
        "outputId": "83ff8ba9-14f1-49aa-c8f7-ed4cbf3b010f"
      },
      "source": [
        "plt.bar(['Token accuracy', 'Magnitude accuracy'], [token_accuracy, magnitude_accuracy])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<BarContainer object of 2 artists>"
            ]
          },
          "metadata": {},
          "execution_count": 35
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAARkElEQVR4nO3df5BdZ13H8feHhFB+FIRmQc0PEiGg4ceArMEZHUQBJ5UxAUEnUcAySgY1iiKOYWQyUMQfFWHECQMRi4CWUFB0kWiEQnUEwSxQWpIa2AmBJI5DKBVFLSX49Y97Vg63u9m7yd1s+/T9mrkz53nOc8/5pvvsp889996zqSokSXd991juAiRJ42GgS1IjDHRJaoSBLkmNMNAlqRErl+vEq1evrg0bNizX6SXpLuljH/vYF6tqYq59yxboGzZsYHp6erlOL0l3SUk+N98+L7lIUiMMdElqhIEuSY0w0CWpEQa6JDVipEBPsjXJsSQzSfbMsf+1SW7oHp9O8u/jL1WSdC4LfmwxyQpgH/A04BRwOMlUVR2dHVNVv9Ib/4vA45egVknSOYyyQt8CzFTV8aq6HTgAbD/H+J3A28dRnCRpdKME+hrgZK99quu7gyQPBTYCH7jw0iRJizHub4ruAN5VVV+fa2eSXcAugPXr14/51NKdx4Y9713uEnQnduJ3nr4kxx1lhX4aWNdrr+365rKDc1xuqar9VTVZVZMTE3PeikCSdJ5GCfTDwKYkG5OsYhDaU8ODknwn8EDgn8ZboiRpFAsGelWdBXYDh4CbgWur6kiSK5Ns6w3dARwo/0ipJC2Lka6hV9VB4OBQ396h9svHV5YkabH8pqgkNWLZ7od+IfwEgc5lqT5BIN3ZuUKXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGjFSoCfZmuRYkpkke+YZ8xNJjiY5kuSa8ZYpSVrIgn8kOskKYB/wNOAUcDjJVFUd7Y3ZBLwU+L6qujXJg5eqYEnS3EZZoW8BZqrqeFXdDhwAtg+NeQGwr6puBaiqL4y3TEnSQkYJ9DXAyV77VNfX9wjgEUk+lOQjSbbOdaAku5JMJ5k+c+bM+VUsSZrTuN4UXQlsAp4M7AT+KMm3DA+qqv1VNVlVkxMTE2M6tSQJRgv008C6Xntt19d3Cpiqqq9V1WeBTzMIeEnSRTJKoB8GNiXZmGQVsAOYGhrzlwxW5yRZzeASzPEx1ilJWsCCgV5VZ4HdwCHgZuDaqjqS5Mok27phh4BbkhwFPgj8WlXdslRFS5LuaMGPLQJU1UHg4FDf3t52AS/uHpKkZeA3RSWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaMVKgJ9ma5FiSmSR75th/RZIzSW7oHj87/lIlSeeycqEBSVYA+4CnAaeAw0mmquro0NB3VNXuJahRkjSCUVboW4CZqjpeVbcDB4DtS1uWJGmxRgn0NcDJXvtU1zfsWUluTPKuJOvmOlCSXUmmk0yfOXPmPMqVJM1nXG+KvgfYUFWPBd4HvGWuQVW1v6omq2pyYmJiTKeWJMFogX4a6K+413Z9/6+qbqmqr3bNNwFPGE95kqRRjRLoh4FNSTYmWQXsAKb6A5J8W6+5Dbh5fCVKkkax4Kdcqupskt3AIWAFcHVVHUlyJTBdVVPALyXZBpwFvgRcsYQ1S5LmsGCgA1TVQeDgUN/e3vZLgZeOtzRJ0mL4TVFJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDVipEBPsjXJsSQzSfacY9yzklSSyfGVKEkaxYKBnmQFsA+4HNgM7EyyeY5xlwIvAj467iIlSQsbZYW+BZipquNVdTtwANg+x7hXAr8L3DbG+iRJIxol0NcAJ3vtU13f/0vy3cC6qnrvuQ6UZFeS6STTZ86cWXSxkqT5XfCboknuAbwG+NWFxlbV/qqarKrJiYmJCz21JKlnlEA/Dazrtdd2fbMuBR4NXJ/kBPC9wJRvjErSxTVKoB8GNiXZmGQVsAOYmt1ZVV+uqtVVtaGqNgAfAbZV1fSSVCxJmtOCgV5VZ4HdwCHgZuDaqjqS5Mok25a6QEnSaFaOMqiqDgIHh/r2zjP2yRdeliRpsfymqCQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjRgr0JFuTHEsyk2TPHPtfmOSmJDck+cckm8dfqiTpXBYM9CQrgH3A5cBmYOccgX1NVT2mqh4HXAW8ZuyVSpLOaZQV+hZgpqqOV9XtwAFge39AVf1Hr3lfoMZXoiRpFCtHGLMGONlrnwKeODwoyS8ALwZWAT8014GS7AJ2Aaxfv36xtUqSzmFsb4pW1b6qehjw68DL5hmzv6omq2pyYmJiXKeWJDFaoJ8G1vXaa7u++RwAnnEhRUmSFm+UQD8MbEqyMckqYAcw1R+QZFOv+XTgM+MrUZI0igWvoVfV2SS7gUPACuDqqjqS5EpguqqmgN1Jngp8DbgV+OmlLFqSdEejvClKVR0EDg717e1tv2jMdUmSFslvikpSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREjBXqSrUmOJZlJsmeO/S9OcjTJjUmuS/LQ8ZcqSTqXBQM9yQpgH3A5sBnYmWTz0LBPAJNV9VjgXcBV4y5UknRuo6zQtwAzVXW8qm4HDgDb+wOq6oNV9d9d8yPA2vGWKUlayCiBvgY42Wuf6vrm8zPA31xIUZKkxVs5zoMleQ4wCfzAPPt3AbsA1q9fP85TS9Ld3igr9NPAul57bdf3TZI8FfgNYFtVfXWuA1XV/qqarKrJiYmJ86lXkjSPUQL9MLApycYkq4AdwFR/QJLHA29kEOZfGH+ZkqSFLBjoVXUW2A0cAm4Grq2qI0muTLKtG/Z7wP2Adya5IcnUPIeTJC2Rka6hV9VB4OBQ397e9lPHXJckaZH8pqgkNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSI0YK9CRbkxxLMpNkzxz7n5Tk40nOJnn2+MuUJC1kwUBPsgLYB1wObAZ2Jtk8NOzzwBXANeMuUJI0mpUjjNkCzFTVcYAkB4DtwNHZAVV1otv3v0tQoyRpBKNcclkDnOy1T3V9i5ZkV5LpJNNnzpw5n0NIkuZxUd8Urar9VTVZVZMTExMX89SS1LxRAv00sK7XXtv1SZLuREYJ9MPApiQbk6wCdgBTS1uWJGmxFgz0qjoL7AYOATcD11bVkSRXJtkGkOR7kpwCfhx4Y5IjS1m0JOmORvmUC1V1EDg41Le3t32YwaUYSdIy8ZuiktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY0YKdCTbE1yLMlMkj1z7L9Xknd0+z+aZMO4C5UknduCgZ5kBbAPuBzYDOxMsnlo2M8At1bVw4HXAr877kIlSec2ygp9CzBTVcer6nbgALB9aMx24C3d9ruApyTJ+MqUJC1k5Qhj1gAne+1TwBPnG1NVZ5N8GbgM+GJ/UJJdwK6u+ZUkx86naN3Baob+W9+dxdeHd0bO0Z4LnKMPnW/HKIE+NlW1H9h/Mc95d5Bkuqoml7sOaT7O0YtjlEsup4F1vfbarm/OMUlWAg8AbhlHgZKk0YwS6IeBTUk2JlkF7ACmhsZMAT/dbT8b+EBV1fjKlCQtZMFLLt018d3AIWAFcHVVHUlyJTBdVVPAHwNvSzIDfIlB6Ovi8TKW7uycoxdBXEhLUhv8pqgkNcJAl6RGGOiLkOSyJDd0j39LcrrXXjU09kSS1ctVq9qQpJL8aa+9MsmZJH+9BOd6YZLnddtXJPn28ziG834ZXdTPod/VVdUtwOMAkrwc+EpVvXpZi1oCSVZW1dnlrkMA/Bfw6CT3rqr/AZ7GHT82PBZV9YZe8wrgU8C/LsW5Lra7y5x2hX6BkjwlySeS3JTk6iT3Gtp/7yR/k+QFSe7bjfnn7jnbuzFXJPmLJH+b5DNJrprnXHuTHE7yqST7Z2+vkOThSd6f5JNJPp7kYV3/r3d1fTLJ73R91yeZ7LZXJznRq2EqyQeA65LcL8l13fFumq21G/u8JDd2x31bkkuTfDbJPbv99++3dcEOAk/vtncCb5/dkWRLkn/q5tOHkzyy679PkmuTHE3y7u6mebM/968keVX38/tIkod0/S9P8pIkzwYmgT/rXn3eu7/yTjKZ5Ppu+7Ikf5fkSJI3AenV9pxurt+Q5I0Z3Bfqmzinx6yqfJzHA3g58DIGtzx4RNf3VuCXu+0TwAbg/cDzur7fAp7TbX8L8GngvgxWQ8cZfCHrEuBzwLo5zvmg3vbbgB/ttj8KPLPbvgS4D4ObqX0YuE//ucD1wGS3vRo40W1fweC2DrPjVgL3742bYfDL+qiu7tVDx30z8Ixuexfw+8v9M2rhAXwFeCyDeyRdAtwAPBn4627//YGV3fZTgT/vtl8CvLHbfjRwtvdzr97cuQp4WW9Ov2R4nvTm8+zPfBK4vtt+HbC32356d+zVwHcB7wHu2e17/ezvgXN66R6u0C/MCuCzVfXprv0W4Em9/X8FvLmq3tq1fxjYk+QGBpPwEmB9t++6qvpyVd0GHGXu+zX8YLfSugn4IeBRSS4F1lTVuwGq6raq+m8Gv9xv7rapqi+N8O95X29cgN9KciOD/ymtAR7SnfedVfXFoeO+CXh+t/18Br8MGoOqupHB4mAng9V63wOAdyb5FIM7nT6q6/9+BjfSo6o+BdzYe87twOw1+I91xz5fTwL+tDvPe4Fbu/6nAE8ADnfz/SnAd8zxfOf0GHkNfWl9CNia5Joa/G8+wLOq6ptuSpbkicBXe11fZ+hnk+QSBqucyao6mcE1/EvOo6azfONS2/Dz/6u3/VPABPCEqvpa9zJ23vNV1YeSbEjyZGBFFyIanyng1QxW55f1+l8JfLCqnpnB3yG4foRjfa2bjzDHXJvHuebNXAK8papeOu8A5/TYuUK/MF8HNiR5eNd+LvD3vf17GaxY9nXtQ8Av9q4TPn4R55qdeF9Mcj8Gt1igqv4TOJXkGd0x75XkPsD7gOd32yR5UPf8EwxWTsweYx4PAL7QTfwf5BuvGD4A/HiSy4aOC4NLTtdwF1jJ3AVdDbyiqm4a6n8A33iT9Ipe/4eAnwDI4O8XPGaR5/tP4NJe+wTfmDfP6vX/A/CT3XkuBx7Y9V8HPDvJg7t9D0oy/KrTOT1mBvqFuY3BS7F3di8Z/xd4w9CYFwH3zuCNzlcC9wRuTHKka4+kqv4d+CMGnzw4xOAeO7OeC/xS91Lyw8C3VtXfMljVTXcveV/SjX018HNJPsHgOuJ8/gyY7P5dzwP+pavjCPAq4O+TfBJ4zdBzHkjvTTuNR1WdqqrXzbHrKuC3u59nf6X9emAiyVHgN4EjwJcXcco/Ad4w+6Yo8ArgD5JMM1jIzHoF8KRuPv8Y8Pmu3qMM3mP6u25evg/4tqF/k3N6zPzqv8Ymg09HbK+q5y53LXd33SdK7llVt3WfEHk/8Mga/JEajeiuNqe9hq6xSPKHDD6F8CPLXYuAwadCPth9zC7Azxvmi3NXnNOu0CWpEV5Dl6RGGOiS1AgDXZIaYaBLUiMMdElqxP8BY3vUbn4bKucAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sNhS8OCVxMHd"
      },
      "source": [
        "#### (Q1.3) A better threshold (1pt)\n",
        "Above we have defined a threshold to account for an inherent bias in the dataset: there are more positive than negative words per review.\n",
        "However, that threshold does not take into account *document length*. Explain why this is a problem and implement an alternative way to compute the threshold."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xo7gk1I-omLI"
      },
      "source": [
        "The threshold of 8 is an absolute value, which can result in classification difficulties when we don't account for document length. If a review, for example, only has one sentence with 10 words, it is very hard to classify this review as positive as it needs at least 8 positive words. A review with less than 8 words will in this case never be classified as positive (even if the review says \"Best movie ever. This is amazing.\" The other way around, if a review is very long and contains 800 words, only 1% of those words have to get a positive polarity for the review to get a positive classification (even if the other 99% is negative). In other words, the shorter the document, the harder it is to be classified as positive and the longer the document the easier it is to be classified as positive. It is therefore a problem if we don't account for document length. The length of the document must not influence the probability of the review being classified as either positive or negative.\n",
        "\n",
        "To account for *document length*, we could use a different threshold and compare it against $\\frac{s_{weighted}}{n}$ where $n$ is the number of recognised words."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Dwt0B8h8aKjr",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4642c06a-2b28-48ff-bfc7-58c8bc67104f"
      },
      "source": [
        "def classify_sweighted_better_threshold(sentences, lexicon_dict, weak_strength=0.2, strong_strength=1, threshold=6):\n",
        "    sbinary = 0\n",
        "    known_tokens = 0\n",
        "    for sentence in sentences:\n",
        "        for token, pos in sentence:\n",
        "            type_and_priorpolairty = lexicon_dict.get(token)\n",
        "                        \n",
        "            if type_and_priorpolairty is not None:\n",
        "                known_tokens += 1\n",
        "                \n",
        "                strength_type, priorpolairty = type_and_priorpolairty\n",
        "                strength = weak_strength if strength_type == 'weaksubj' else strong_strength\n",
        "                            \n",
        "                if priorpolairty == \"negative\":\n",
        "                    sbinary -= strength\n",
        "                elif priorpolairty == \"positive\":\n",
        "                    sbinary += strength\n",
        "    \n",
        "    return sbinary / known_tokens >= threshold\n",
        "\n",
        "if False:\n",
        "    print(best_params(classify_sweighted_better_threshold, [0.1, 0.15, 0.2, 0.3], [-0.1, 0.03, 0.04, 0.05, 0.07, 0.1, 0.3, 0.5]))\n",
        "\n",
        "\n",
        "reals = [review['sentiment'] == 'POS' for review in reviews]\n",
        "threshold_results = [\n",
        "    classify_sweighted(review['content'], lexicon_dict)\n",
        "    for\n",
        "    review in reviews\n",
        "]\n",
        "threshold_accuracy = sum((real == prediction for real, prediction in zip(reals, threshold_results))) / len(token_results)\n",
        "print(\"Accuracy: %0.2f\" % magnitude_accuracy)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Accuracy: 0.70\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LibV4nR89BXb"
      },
      "source": [
        "# Naive Bayes (9.5pts)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fnF9adQnuwia"
      },
      "source": [
        "\n",
        "Your second task is to program a simple Machine Learning approach that operates\n",
        "on a simple Bag-of-Words (BoW) representation of the text data, as\n",
        "described by Pang et al. (2002). In this approach, the only features we\n",
        "will consider are the words in the text themselves, without bringing in\n",
        "external sources of information. The BoW model is a popular way of\n",
        "representing texts as vectors, making it\n",
        "easy to apply classical Machine Learning algorithms on NLP tasks.\n",
        "However, the BoW representation is also very crude, since it discards\n",
        "all information related to word order and grammatical structure in the\n",
        "original text—as the name suggests.\n",
        "\n",
        "## Writing your own classifier (4pts)\n",
        "\n",
        "Write your own code to implement the Naive Bayes (NB) classifier. As\n",
        "a reminder, the Naive Bayes classifier works according to the following\n",
        "equation:\n",
        "$$\\hat{c} = \\operatorname*{arg\\,max}_{c \\in C} P(c|\\bar{f}) = \\operatorname*{arg\\,max}_{c \\in C} P(c)\\prod^n_{i=1} P(f_i|c)$$\n",
        "where $C = \\{ \\text{POS}, \\text{NEG} \\}$ is the set of possible classes,\n",
        "$\\hat{c} \\in C$ is the most probable class, and $\\bar{f}$ is the feature\n",
        "vector. Remember that we use the log of these probabilities when making\n",
        "a prediction:\n",
        "$$\\hat{c} = \\operatorname*{arg\\,max}_{c \\in C} \\Big\\{\\log P(c) + \\sum^n_{i=1} \\log P(f_i|c)\\Big\\}$$\n",
        "\n",
        "You can find more details about Naive Bayes in [Jurafsky &\n",
        "Martin](https://web.stanford.edu/~jurafsky/slp3/). You can also look at\n",
        "this helpful\n",
        "[pseudo-code](https://nlp.stanford.edu/IR-book/html/htmledition/naive-bayes-text-classification-1.html).\n",
        "\n",
        "*Note: this section and the next aim to put you in a position to replicate\n",
        "    Pang et al.'s Naive Bayes results. However, your numerical results\n",
        "    will differ from theirs, as they used different data.*\n",
        "\n",
        "**You must write the Naive Bayes training and prediction code from\n",
        "scratch.** You will not be given credit for using off-the-shelf Machine\n",
        "Learning libraries.\n",
        "\n",
        "The data contains the text of the reviews, where each document consists\n",
        "of the sentences in the review, the sentiment of the review and an index\n",
        "(cv) that you will later use for cross-validation. The\n",
        "text has already been tokenised and POS-tagged for you. Your algorithm\n",
        "should read in the text, **lowercase it**, store the words and their\n",
        "frequencies in an appropriate data structure that allows for easy\n",
        "computation of the probabilities used in the Naive Bayes algorithm, and\n",
        "then make predictions for new instances.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vEpyQSBSkb33"
      },
      "source": [
        "#### (Q2.1) Unseen words (1pt)\n",
        "The presence of words in the test dataset that\n",
        "have not been seen during training can cause probabilities in the Naive Bayes classifier to equal $0$.\n",
        "These can be words which are unseen in both positive and negative training reviews (case 1), but also words which are seen in reviews _of only one sentiment class_ in the training dataset (case 2). In both cases, **you should skip these words for both classes**.  What would be the problem instead with skipping words only for one class in case 2? "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BanFiYYnoxDW"
      },
      "source": [
        "**(Q2.1) Answer:**\n",
        "Skipping the word is equivalent to adding 0. If you would add a word that is seen in only one sentiment class to the likelihood of that class the likelihood will decrease. This happend because each conditional probability for that word will be less than 1, resulting in a negative log-probability (thus, decreasing the likelihood). Consequently, the likelihood of the class the word did occur in will decrease more than the likelihood of the class the word did not occur in. This is exactly the opposite of what should happen!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gsZRhaI3WvzC"
      },
      "source": [
        "#### (Q2.2) Train your classifier on (positive and negative) reviews with cv-value 000-899, and test it on the remaining (positive and negative) reviews cv900–cv999.  Report results using classification accuracy as your evaluation metric. Your  features are the word vocabulary. The value of a feature is the count of that feature (word) in the document. (2pts)\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "G7zaJYGFvIJ3",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "02115575-d5f7-4937-8290-59fed125503e"
      },
      "source": [
        "def class_index(class_name): return 0 if class_name == 'NEG' else 1\n",
        "def flat(list_of_lists): return (item for list_ in list_of_lists for item in list_)\n",
        "\n",
        "def unique_words(data, include_pos=False):\n",
        "    result = set()\n",
        "\n",
        "    for datapoint in data:\n",
        "        for sentence in datapoint['content']:\n",
        "            for word, pos in sentence:\n",
        "                if include_pos:\n",
        "                    result.add((word, pos))\n",
        "                else:\n",
        "                    result.add(word)\n",
        "    \n",
        "    return result\n",
        "\n",
        "@dataclass\n",
        "class NaiveBayesClassifier():\n",
        "    word_class_count: dict\n",
        "    total_words: list\n",
        "    class_count: list\n",
        "        \n",
        "\n",
        "def train_naive_bayes(data, skip_if_missing=False):\n",
        "    if(skip_if_missing):\n",
        "        unique_positive = unique_words((r for r in data if r['sentiment'] == 'POS'))\n",
        "        unique_negative = unique_words((r for r in data if r['sentiment'] == 'NEG'))\n",
        "    word_class_count = Counter()\n",
        "    total_words = [0, 0]\n",
        "    class_count = [0, 0]\n",
        "    \n",
        "    for review in data:\n",
        "        sentiment = review['sentiment']\n",
        "        sentiment_index = class_index(sentiment)\n",
        "        class_count[sentiment_index] += 1\n",
        "        \n",
        "        for word, pos in flat(review['content']):\n",
        "            word_lower = word\n",
        "            if skip_if_missing and not (word_lower in unique_positive and word_lower in unique_negative):\n",
        "                continue\n",
        "            word_class_count[word_lower, sentiment_index] += 1\n",
        "            total_words[sentiment_index] += 1\n",
        "            \n",
        "    return NaiveBayesClassifier(word_class_count, total_words, class_count)\n",
        "\n",
        "\n",
        "def test_naive_bayes(data, classifier, word_probability):\n",
        "    correct = 0\n",
        "    total = len(data)\n",
        "    \n",
        "    for datapoint in data:\n",
        "        log_ps = [log_p(flat(datapoint['content']), class_index, classifier, word_probability) for class_index in [0, 1]]\n",
        "        \n",
        "        prediction = 0 if log_ps[0] > log_ps[1] else 1\n",
        "        real = class_index(datapoint['sentiment'])\n",
        "        \n",
        "        correct += prediction == real\n",
        "        \n",
        "    return correct, total\n",
        "\n",
        "\n",
        "def log_p(sentence, class_idx, classifier, word_probability):\n",
        "    result = 0\n",
        "    \n",
        "    class_count = classifier.class_count[class_idx]\n",
        "    total_amount_of_sentences = sum(classifier.class_count)\n",
        "    \n",
        "    result += math.log2(class_count / total_amount_of_sentences)\n",
        "    \n",
        "    for word, pos in sentence:\n",
        "        result += word_probability(classifier, word, pos, class_idx)\n",
        "            \n",
        "    return result\n",
        "        \n",
        "\n",
        "def probability_or_zero(classifier, word, pos, class_idx):\n",
        "    count = classifier.word_class_count[word, class_idx]\n",
        "\n",
        "    if count == 0 or classifier.word_class_count[word, 1 - class_idx] == 0:\n",
        "        return 0\n",
        "    else:\n",
        "        return math.log2(count / classifier.total_words[class_idx])\n",
        "    \n",
        "\n",
        "def filter_review_range(min, max, reviews):\n",
        "    return [r for r in reviews if min <= r['cv'] < max]\n",
        "\n",
        "train = filter_review_range(0, 900, reviews)\n",
        "test = filter_review_range(900, 1000, reviews)\n",
        "\n",
        "def evaluate_data(train, test, word_probability, skip_if_missing=False):\n",
        "    classifier = train_naive_bayes(train, skip_if_missing)\n",
        "    results = test_naive_bayes(test, classifier, word_probability)\n",
        "\n",
        "    print(results)\n",
        "    print(\"Accuracy:\", results[0] / results[1])\n",
        "    \n",
        "evaluate_data(train, test, probability_or_zero, True)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(167, 200)\n",
            "Accuracy: 0.835\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0INK-PBoM6CB"
      },
      "source": [
        "#### (Q2.3) Would you consider accuracy to also be a good way to evaluate your classifier in a situation where 90% of your data instances are of positive movie reviews? (1pt)\n",
        "\n",
        "Simulate this scenario by keeping the positive reviews\n",
        "data unchanged, but only using negative reviews cv000–cv089 for\n",
        "training, and cv900–cv909 for testing. Calculate the classification\n",
        "accuracy, and explain what changed."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oFbcsYlipBAw"
      },
      "source": [
        "**(Q2.3) Answer:**\n",
        "In the case that 90% of our data instances are of positive movie reviews, accuracy would not be a good way to evaluate the classifier. This is due to the fact that the data is very skewed in this case. If we would predict POS all the time, our accuracy would be 90% without making any useful predictions.\n",
        "\n",
        "By applying this, we expect the accuracy to improve, because the classification becomes easier. The prior probability of class POS becomes very high (0.9), which will result in a bias towards predicting POS labels. These predictions would also be correct most of the time. Moreover, because the class NEG is very small and we skip words that don't occur in both of the classes, we skip many words when we make predictions. This leads to the conditional probability of the word being less representative of the actual distributions of the words in the classes.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GWDkt5ZrrFGp",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "731ad31a-9ac2-4307-e786-548c2e77a844"
      },
      "source": [
        "positive = [r for r in reviews if r['sentiment'] == 'POS']\n",
        "negative = [r for r in reviews if r['sentiment'] == 'NEG']\n",
        "\n",
        "train_biased = filter_review_range(0, 90, negative) + filter_review_range(0, 900, positive)\n",
        "test_biased = filter_review_range(900, 910, negative) + filter_review_range(900, 1000, positive)\n",
        "\n",
        "evaluate_data(train_biased, test_biased, probability_or_zero, True)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(98, 110)\n",
            "Accuracy: 0.8909090909090909\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6wJzcHX3WUDm"
      },
      "source": [
        "## Smoothing (1pt)\n",
        "\n",
        "As mentioned above, the presence of words in the test dataset that\n",
        "have not been seen during training can cause probabilities in the Naive\n",
        "Bayes classifier to be $0$, thus making that particular test instance\n",
        "undecidable. The standard way to mitigate this effect (as well as to\n",
        "give more clout to rare words) is to use smoothing, in which the\n",
        "probability fraction\n",
        "\n",
        "$ \\frac{\\text{count}(w_i, c)}{\\sum\\limits_{w\\in V} \\text{count}(w, c)} $\n",
        "\n",
        "for a word\n",
        "$w_i$ becomes\n",
        "$$\\frac{\\text{count}(w_i, c) + \\text{smoothing}(w_i)}{\\sum\\limits_{w\\in V} \\text{count}(w, c) + \\sum\\limits_{w \\in V} \\text{smoothing}(w)}$$\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PBNIcbwUWphC"
      },
      "source": [
        "#### (Q2.4) Implement Laplace feature smoothing (1pt)\n",
        "Implement Laplace smoothing, i.e., smoothing with a constant value ($smoothing(w) = \\kappa, \\forall w \\in V$), in your Naive\n",
        "Bayes classifier’s code, and report the impact on performance. \n",
        "Use $\\kappa = 1$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "g03yflCc9kpW",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "92cd5ff5-cd80-42dc-b29e-25e725080ab7"
      },
      "source": [
        "def laplace_smooth_probability(k):\n",
        "    def result(classifier, word, pos, class_idx):\n",
        "        return math.log2(\n",
        "             (classifier.word_class_count[word, class_idx] + k)\n",
        "             /\n",
        "             (classifier.total_words[class_idx] + k * len(classifier.word_class_count))\n",
        "        )\n",
        "\n",
        "    return result\n",
        "\n",
        "evaluate_data(train, test, laplace_smooth_probability(1))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(164, 200)\n",
            "Accuracy: 0.82\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L03GFZvAzjgt"
      },
      "source": [
        "It appears that smoothing decreases the performance accuracy of out Naive Bayes classifier from 0.835 to 0.82. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZiGcgwba87D5"
      },
      "source": [
        "## Cross-Validation (1.5pts)\n",
        "\n",
        "A serious danger in using Machine Learning on small datasets, with many\n",
        "iterations of slightly different versions of the algorithms, is ending up with Type III errors, also called the “testing hypotheses\n",
        "suggested by the data” errors. This type of error occurs when we make\n",
        "repeated improvements to our classifiers by playing with features and\n",
        "their processing, but we don’t get a fresh, never-before seen test\n",
        "dataset every time. Thus, we risk developing a classifier that gets better\n",
        "and better on our data, but only gets worse at generalizing to new, unseen data. In other words, we risk developping a classifier that overfits.\n",
        "\n",
        "A simple method to guard against Type III errors is to use\n",
        "Cross-Validation. In **N-fold Cross-Validation**, we divide the data into N\n",
        "distinct chunks, or folds. Then, we repeat the experiment N times: each\n",
        "time holding out one of the folds for testing, training our classifier\n",
        "on the remaining N - 1 data folds, and reporting performance on the\n",
        "held-out fold. We can use different strategies for dividing the data:\n",
        "\n",
        "-   Consecutive splitting:\n",
        "  - cv000–cv099 = Split 1\n",
        "  - cv100–cv199 = Split 2\n",
        "  - etc.\n",
        "  \n",
        "-   Round-robin splitting (mod 10):\n",
        "  - cv000, cv010, cv020, … = Split 1\n",
        "  - cv001, cv011, cv021, … = Split 2\n",
        "  - etc.\n",
        "\n",
        "-   Random sampling/splitting\n",
        "  - Not used here (but you may choose to split this way in a non-educational situation)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8OeLcbSauGtR"
      },
      "source": [
        "#### (Q2.5) Write the code to implement 10-fold cross-validation using round-robin splitting for your Naive Bayes classifier from Q2.4 and compute the 10 accuracies. Report the final performance, which is the average of the performances per fold. If all splits perform equally well, this is a good sign. (1pt)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3KeCGPa7Nuzx",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c2a270d3-1dba-498d-e5e5-246c6780b02a"
      },
      "source": [
        "def round_robin(data, fold_count, fold_idx, is_test):\n",
        "    return [\n",
        "        datapoint for datapoint in data if (datapoint['cv'] % fold_count == fold_idx) == is_test\n",
        "    ]\n",
        "\n",
        "def k_fold(k, data):\n",
        "    accuracies = []\n",
        "    \n",
        "    for fold_idx in range(k):\n",
        "        test = round_robin(data, k, fold_idx, True)\n",
        "        train = round_robin(data, k, fold_idx, False)\n",
        "        \n",
        "        classifier = train_naive_bayes(train)\n",
        "        correct, total = test_naive_bayes(test, classifier, laplace_smooth_probability(1))\n",
        "        \n",
        "        accuracies.append(correct / total)\n",
        "        \n",
        "    accuracy_avg = sum(accuracies) / k\n",
        "    accuracy_sds = ((accuracy - accuracy_avg) ** 2 for accuracy in accuracies)\n",
        "    accuracy_sd = sum(accuracy_sds) / k\n",
        "    \n",
        "    return accuracy_avg, accuracy_sd\n",
        "\n",
        "accuracy_avg, accuracy_sd = k_fold(10, reviews)\n",
        "\n",
        "print(\"Accuracy:\", accuracy_avg)\n",
        "print(\"Variance:\", accuracy_sd)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Accuracy: 0.8185\n",
            "Variance: 0.0005602499999999987\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "otdlsDXBNyOa"
      },
      "source": [
        "#### (Q2.6) Report the variance of the 10 accuracy scores. (0.5pt)\n",
        "\n",
        "**Please report all future results using 10-fold cross-validation now\n",
        "(unless told to use the held-out test set).**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZoBQm1KuNzNR",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fafbf20e-f1b2-482e-ae0e-c43465b63050"
      },
      "source": [
        "print(\"Variance:\", accuracy_sd)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Variance: 0.0005602499999999987\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s6A2zX9_BRKm"
      },
      "source": [
        "## Features, overfitting, and the curse of dimensionality\n",
        "\n",
        "In the Bag-of-Words model, ideally we would like each distinct word in\n",
        "the text to be mapped to its own dimension in the output vector\n",
        "representation. However, real world text is messy, and we need to decide\n",
        "on what we consider to be a word. For example, is “`word`\" different\n",
        "from “`Word`\", from “`word`”, or from “`words`\"? Too strict a\n",
        "definition, and the number of features explodes, while our algorithm\n",
        "fails to learn anything generalisable. Too lax, and we risk destroying\n",
        "our learning signal. In the following section, you will learn about\n",
        "confronting the feature sparsity and the overfitting problems as they\n",
        "occur in NLP classification tasks."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EKK8FNt8VtcZ"
      },
      "source": [
        "### Stemming (1.5pts)\n",
        "\n",
        "To make your algorithm more robust, use stemming and hash different inflections of a word to the same feature in the BoW vector space. Please use the [Porter stemming\n",
        "    algorithm](http://www.nltk.org/howto/stem.html) from NLTK.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NxtCul1IrBi_"
      },
      "source": [
        "# YOUR CODE HERE\n",
        "stemmer = PorterStemmer()\n",
        "\n",
        "def stem_words(data):\n",
        "    stemmed_data = copy.deepcopy(data)\n",
        "    \n",
        "    for datapoint in stemmed_data:\n",
        "        datapoint['content'] = [\n",
        "            [(stemmer.stem(word), pos) for word, pos in sentence]\n",
        "            for sentence in datapoint['content']\n",
        "        ]\n",
        "\n",
        "    return stemmed_data\n",
        "\n",
        "train_stemmed = stem_words(train)\n",
        "test_stemmed = stem_words(test)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6SrJ1BeLXTnk"
      },
      "source": [
        "#### (Q2.7): How does the performance of your classifier change when you use stemming on your training and test datasets? (1pt)\n",
        "Use cross-validation to evaluate the classifier. \n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYqKBOiIrInT",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4b4a3d27-ad6a-4415-8794-39cb867f67e6"
      },
      "source": [
        "evaluate_data(train_stemmed, test_stemmed, laplace_smooth_probability(1))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(164, 200)\n",
            "Accuracy: 0.82\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JkDHVq_1XUVP"
      },
      "source": [
        "#### (Q2.8) What happens to the number of features (i.e., the size of the vocabulary) when using stemming as opposed to (Q2.4)? (0.5pt)\n",
        "Give actual numbers. You can use the held-out training set to determine these."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MA3vee5-rJyy",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "01fbd07e-f7d4-4fa5-ca8c-fbbec9f81f0c"
      },
      "source": [
        "unique_words_unstemmed = unique_words(train)\n",
        "unique_words_stemmed = unique_words(train_stemmed)\n",
        "        \n",
        "print(len(unique_words_unstemmed)) # The number of words in the vocabulary reduces from 45348\n",
        "print(len(unique_words_stemmed))   # to 32404"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "45348\n",
            "32404\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SoazfxbNV5Lq"
      },
      "source": [
        "### N-grams (1.5pts)\n",
        "\n",
        "A simple way of retaining some of the word\n",
        "order information when using bag-of-words representations is to use **n-gram** features. \n",
        "\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OHjy3I7-qWiu"
      },
      "source": [
        "#### (Q2.9) Retrain your classifier from (Q2.4) using **unigrams+bigrams** and **unigrams+bigrams+trigrams** as features. (1pt)\n",
        "Report accuracy and compare it with that of the approaches you have previously implemented. You are allowed to use NLTK to build n-grams from sentences."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eYuKMTOpq9jz",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c0b35d31-2a63-460c-a291-861411f23343"
      },
      "source": [
        "sentence_break = ['<s>', '<s>']\n",
        "\n",
        "def augment_n_gram(data, n):\n",
        "    result = copy.deepcopy(data)\n",
        "    for datapoint in result:\n",
        "        for sentence in datapoint['content']:\n",
        "            old_sentence = sentence[:]\n",
        "            if n >= 2:\n",
        "                for ((word1, pos1), (word2, pos2)) in zip([['<s>', '<s>']] + old_sentence, old_sentence + [['<s>', '<s>']]):\n",
        "                    sentence.append([word1 + ',' + word2, pos1 + ',' + pos2])\n",
        "            if n >= 3:\n",
        "                for ((word1, pos1), (word2, pos2), (word3, pos3)) in zip(\n",
        "                    [sentence_break] + old_sentence + [sentence_break],\n",
        "                    [sentence_break, sentence_break] + old_sentence,\n",
        "                    old_sentence + [sentence_break, sentence_break],\n",
        "                ):\n",
        "                    sentence.append([word1 + ',' + word2 + ',' + word3, pos1 + ',' + pos2 + ',' + pos3])\n",
        "            if n >= 4:\n",
        "                raise NotImplemented('Only up to n=3 is implemented')\n",
        "    return result\n",
        "        \n",
        "\n",
        "train_data_2_gram = augment_n_gram(train[:], 2)\n",
        "test_data_2_gram = augment_n_gram(test[:], 2)\n",
        "\n",
        "train_data_3_gram = augment_n_gram(train[:], 3)\n",
        "test_data_3_gram = augment_n_gram(test[:], 3)\n",
        "\n",
        "evaluate_data(train_data_2_gram, test_data_2_gram, laplace_smooth_probability(1))\n",
        "evaluate_data(train_data_3_gram, test_data_3_gram, laplace_smooth_probability(1))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(170, 200)\n",
            "Accuracy: 0.85\n",
            "(174, 200)\n",
            "Accuracy: 0.87\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RX6zwNQm8SJ5"
      },
      "source": [
        "The accuracy improves for both the unigrams+bigrams and unigrams+bigrams+trigrams compared to our previous Naive Bayes classifier."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dVrGGArkrWoL"
      },
      "source": [
        "\n",
        "#### Q2.10: How many features does the BoW model have to take into account now? (0.5pt)\n",
        "How would you expect the number of features to increase theoretically (e.g., linear, square, cubed, exponential)? How does this number compare, in practice, to the number of features at (Q2.8)?\n",
        "\n",
        "Use the held-out training set once again for this.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yEGZ9SV8pPaa"
      },
      "source": [
        "**(Q2.10) Answer:**\n",
        "In theory, the number of features increases exponentially with the size of the n-gram. If there are $v$ words in the vocabulary, and you use an $n$-gram, there are $v^n$ possible $n$-grams. However, in practice not all of these combinations actually occur in the train data because not all combinations of words are possible, and the data is usually limited. Therefore, you would not need to store all of them."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_z8sAJeUrdtM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fef38727-e8b0-4799-cce1-c067c014d48e"
      },
      "source": [
        "words_2_gram = len(unique_words(train_data_2_gram))\n",
        "words_3_gram = len(unique_words(train_data_3_gram))\n",
        "\n",
        "print(len(unique_words(train)))\n",
        "print(words_2_gram)\n",
        "print(words_3_gram)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "45348\n",
            "470258\n",
            "1390260\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CHWKDL3YV6vh"
      },
      "source": [
        "# Support Vector Machines (4pts)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hJSYhcVaoJGt"
      },
      "source": [
        "Though simple to understand, implement, and debug, one\n",
        "major problem with the Naive Bayes classifier is that its performance\n",
        "deteriorates (becomes skewed) when it is being used with features which\n",
        "are not independent (i.e., are correlated). Another popular classifier\n",
        "that doesn’t scale as well to big data, and is not as simple to debug as\n",
        "Naive Bayes, but that doesn’t assume feature independence is the Support\n",
        "Vector Machine (SVM) classifier.\n",
        "\n",
        "You can find more details about SVMs in Chapter 7 of Bishop: Pattern Recognition and Machine Learning.\n",
        "Other sources for learning SVM:\n",
        "* http://web.mit.edu/zoya/www/SVM.pdf\n",
        "* http://www.cs.columbia.edu/~kathy/cs4701/documents/jason_svm_tutorial.pdf\n",
        "* https://pythonprogramming.net/support-vector-machine-intro-machine-learning-tutorial/\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "Use the scikit-learn implementation of \n",
        "[SVM](http://scikit-learn.org/stable/modules/svm.html) with the default parameters. (You are not expected to perform any hyperparameter tuning, but feel free to do it if you think it gives you good insights for the discussion in question 5.)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0LnzNtQBV8gr"
      },
      "source": [
        "#### (Q3.1): Train SVM and compare to Naive Bayes (2pts)\n",
        "\n",
        "Train an SVM classifier (sklearn.svm.LinearSVC) using the features collected for Naive Bayes. Compare the\n",
        "classification performance of the SVM classifier to that of the Naive\n",
        "Bayes classifier with smoothing.\n",
        "Use cross-validation to evaluate the performance of the classifiers.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JBscui8Mvoz0",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5364da79-3311-4522-9895-3426e2ba472a"
      },
      "source": [
        "def token_ids(data, include_pos=False):\n",
        "    result = collections.defaultdict(lambda: 0)\n",
        "\n",
        "    tokens = unique_words(data, include_pos)\n",
        "\n",
        "    for i, token in enumerate(tokens):\n",
        "        result[token] = i + 1\n",
        "\n",
        "    return result\n",
        "\n",
        "def to_svm_features(data, token_ids, include_pos=False):\n",
        "    input_size = len(token_ids) + 1\n",
        "\n",
        "    inputs = []\n",
        "    outputs = []\n",
        "\n",
        "    for datapoint in data:\n",
        "        input = [0] * input_size\n",
        "        for sentence in datapoint['content']:\n",
        "            for token, pos in sentence:\n",
        "\n",
        "                if include_pos:\n",
        "                    idx = token, pos\n",
        "                else:\n",
        "                    idx = token\n",
        "                input[token_ids[idx]] += 1\n",
        "        output = class_index(datapoint['sentiment'])\n",
        "\n",
        "        inputs.append(input)\n",
        "        outputs.append(output)\n",
        "    \n",
        "    return inputs, outputs\n",
        "\n",
        "def print_progress(iter, max_iter):\n",
        "    print(\"\\r[\" + \"=\" * iter + \" \" * (max_iter - iter) + \"]\", iter, \"/\", max_iter, end='')\n",
        "\n",
        "\n",
        "def k_fold_svm(k, data, include_pos=False):\n",
        "    accuracies = []\n",
        "    \n",
        "    for fold_idx in range(k):\n",
        "        print_progress(fold_idx, k)\n",
        "\n",
        "        test = round_robin(data, k, fold_idx, True)\n",
        "        train = round_robin(data, k, fold_idx, False)\n",
        "\n",
        "        svm_token_ids = token_ids(train, include_pos)\n",
        "        svm_train_x, svm_train_y = to_svm_features(train, svm_token_ids, include_pos)\n",
        "\n",
        "        svm = sk.svm.LinearSVC(max_iter=10000)\n",
        "        svm.fit(svm_train_x, svm_train_y)\n",
        "\n",
        "        svm_test_x, svm_test_y = to_svm_features(test, svm_token_ids, include_pos)\n",
        "        \n",
        "        accuracies.append(svm.score(svm_test_x, svm_test_y))\n",
        "\n",
        "    print_progress(k, k)\n",
        "    print()\n",
        "        \n",
        "    accuracy_avg = sum(accuracies) / k\n",
        "    accuracy_sds = ((accuracy - accuracy_avg) ** 2 for accuracy in accuracies)\n",
        "    accuracy_sd = sum(accuracy_sds) / k\n",
        "    \n",
        "    return accuracy_avg, accuracy_sd\n",
        "\n",
        "acc, sd = k_fold_svm(10, reviews)\n",
        "\n",
        "print('Accuracy =', acc)\n",
        "print('Standard deviation of accuracy =', sd)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[==========] 10 / 10\n",
            "Accuracy = 0.8320000000000001\n",
            "Standard deviation of accuracy = 0.0005959999999999991\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ifXVWcK0V9qY"
      },
      "source": [
        "### POS disambiguation (2pts)\n",
        "\n",
        "Now add in part-of-speech features. You will find the\n",
        "movie review dataset has already been POS-tagged for you ([here](https://catalog.ldc.upenn.edu/docs/LDC99T42/tagguid1.pdf) you find the tagset). Try to\n",
        "replicate the results obtained by Pang et al. (2002).\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xA3I82o4oWGu"
      },
      "source": [
        "#### (Q3.2) Replace your features with word+POS features, and report performance with the SVM. Use cross-validation to evaluate the classifier and compare the results with (Q3.1). Does part-of-speech information help? Explain why this may be the case. (1pt)\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NOvjYe-t2Br6",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "dc06f4c3-5291-4353-f9f9-097d68fc741d"
      },
      "source": [
        "acc, sd = k_fold_svm(10, reviews, True)\n",
        "\n",
        "print('Accuracy =', acc)\n",
        "print('Standard deviation of accuracy =', sd)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[=======   ] 7 / 10"
          ]
        },
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/sklearn/svm/_base.py:1208: ConvergenceWarning: Liblinear failed to converge, increase the number of iterations.\n",
            "  ConvergenceWarning,\n"
          ]
        },
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[==========] 10 / 10\n",
            "Accuracy = 0.8380000000000001\n",
            "Standard deviation of accuracy = 0.00037099999999999975\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L0dt_oQupUNe"
      },
      "source": [
        "**(Q3.1) Answer:**\n",
        "Adding parts of speech information barely helped. This might be because the POS tag does not influence whether a word is positive or negative."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Su-3w87eMW0w"
      },
      "source": [
        "#### (Q3.3) Discard all closed-class words from your data (keep only nouns, verbs, adjectives, and adverbs), and report performance. Does this help? Use cross-validation to evaluate the classifier and compare the results with (Q3.2). Are closed-class words detrimental to the classifier? Explain why this may be the case. (1pt)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CCUPlPozCYUX",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "90eaf464-4ce3-45f7-8757-5bc8ea045029"
      },
      "source": [
        "def filter_pos_sentences(sentences):\n",
        "    keep_pos = ['NN', 'VB', 'JJ', 'RB']\n",
        "    return [\n",
        "        [(word, pos) for word, pos in sentence if pos[:2] in keep_pos]\n",
        "        for sentence in sentences\n",
        "    ]\n",
        "\n",
        "def filter_pos(data):\n",
        "    return map_sentences(data, filter_pos_sentences)\n",
        "\n",
        "filter_pos_data = filter_pos(reviews)\n",
        "\n",
        "\n",
        "acc, sd = k_fold_svm(10, filter_pos_data, True)\n",
        "\n",
        "print('Accuracy =', acc)\n",
        "print('Standard deviation of accuracy =', sd)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[==========] 10 / 10\n",
            "Accuracy = 0.849\n",
            "Standard deviation of accuracy = 0.00035900000000000065\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YaxCVrs8pWSp"
      },
      "source": [
        "**(Q3.2) Answer:**\n",
        "The accuracy increased when removing all closed-class words. An explanation is that many closed-class words don't influence whether the review is positive or negative, and that removing these reduces overfitting."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nfwqOciAl2No"
      },
      "source": [
        "# (Q4) Discussion (max. 500 words). (5pts)\n",
        "\n",
        "> Based on your experiments, what are the effective features and techniques in sentiment analysis? What information do different features encode?\n",
        "Why is this important? What are the limitations of these features and techniques?\n",
        " \n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZYuse5WLmekZ"
      },
      "source": [
        "In this movie review sentiment analysis, we have performed three major analyses: a lexicon-based approach, Naïve Bayes (NB) classification and Support Vector Machines (SVM). We can immediately conclude that the NB and SVM both outperform the lexicon-based approach, that “only” has a maximum accuracy of 0.70 when taking the magnitude of sentiment into account.\n",
        "\n",
        "The results indicate that the NB and SVM models perform approximately equally well for the sentiment analysis, with accuracies of 0.835 and 0.832 respectively. Both methods use bag-of-words (BoW) features, which have its semantical limitations regarding sentence structure. However, our results indicate that none of the proposed techniques to overcome this limitation showed very high improvements of accuracy.\n",
        "\n",
        "In the NB model, we first applied stemming to make the algorithm more robust. After stemming, our classifier performed with an accuracy of 0.82. Stemming reduces different forms of a word to a common base form. With this, stemming results in a relatively small reduction in feature-space, but does not gain us any meaningful information about the sentiment of the stemmed word. This might be a reason why the classifier accuracy does not improve after stemming, but even worsens a little bit. Secondly, we applied N-grams to our NB model with Laplace smoothing. N-grams features attempts to retrain word order information of the BoW. This did improve our accuracy to 0.85 for 2-grams and 0.87 for 3-grams, but also increased the feature-space substantially.\n",
        "\n",
        "For the SVMs we applied POS disambiguation, which identifies words with their Part of Speech (POS) tags. The intuition here was that POS-tags possibly carry information about the sentiment of the word. However, as our accuracy barely improved, we can conclude that the POS-tags do not carry any sentiment information of the words. Afterwards, we discarded all closed-class words from the data, which did result in an increase of accuracy. Similar to stemming, this technique reduces the feature-space, which could explain part of the increase in accuracy. However, as mentioned in Q3.2, closed-class words do not influence the final predictions of sentiment of the reviews, so most sentiment information can still be acquired from the nouns, adjectives, and adverbs. \n",
        "\n",
        "Overall, we can conclude that primarily the words themselves capture meaningful sentiment information. For example, the word “amazing” would in most cases imply a positive sentiment. The attempts to improve accuracy by adding sentence structure thus barely improved the model accuracy.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iwaKwfWQhRk_"
      },
      "source": [
        "# Submission \n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aOUeaET5ijk-"
      },
      "source": [
        "# Write your names and student numbers here:\n",
        "# Student 1 Jesse Maas #113932284\n",
        "# Student 2 Lizzy Da Rocha Bazilio #11426594"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3A9K-H6Tii3X"
      },
      "source": [
        "**That's it!**\n",
        "\n",
        "- Check if you answered all questions fully and correctly. \n",
        "- Download your completed notebook using `File -> Download .ipynb` \n",
        "- Check if your answers are all included in the file you submit.\n",
        "- Submit your .ipynb file via *Canvas*. One submission per group. "
      ]
    }
  ]
}