5.Transition-Based Dependency Parser.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "accelerator": "GPU",
    "colab": {
      "name": "HW_5.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/asliakalin/NLP/blob/master/5.Transition-Based%20Dependency%20Parser.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tyClcLuqjKb8"
      },
      "source": [
        "# Homework 5: Transition-Based Dependency Parser\n",
        "\n",
        "**Due April 6, 2020 at 11:59pm**\n",
        "\n",
        "In this homework, you will be implementing parts of a transition-based dependency parser."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aJLC8xn_jKcA"
      },
      "source": [
        "**Before beginning, please switch your Colab session to a GPU runtime** \n",
        "\n",
        "Go to Runtime > Change runtime type > Hardware accelerator > GPU\n",
        "\n",
        "## ALSO, REMEMBER TO UPLOAD THE DATASET!\n",
        "\n",
        "Click the Files icon > Upload > Upload `train.projective.short.conll` and `dev.projective.conll` that you have downloaded from bCourses:Files/HW_5"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4iICR_E0jKcC"
      },
      "source": [
        "### Setup"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "X1TYSGJVjKcD"
      },
      "source": [
        "import sys\n",
        "import re\n",
        "import numpy as np\n",
        "import torch.nn as nn\n",
        "import torch\n",
        "import torch.optim as optim"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rNQBqiH3jKcH",
        "outputId": "c6ae4f99-2f95-46a5-a45f-aaaf6eb2a303",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# if this cell prints \"Running on cpu\", you must switch runtime environments\n",
        "# go to Runtime > Change runtime type > Hardware accelerator > GPU\n",
        "device = torch.device(\"cuda\" if torch.cuda.is_available() else \"cpu\")\n",
        "print(\"Running on {}\".format(device))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Running on cuda\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o0t2Z1vRjKcL"
      },
      "source": [
        "### Download pretrained word embeddings\n",
        "\n",
        "In this assignment, we will still be using [GloVe](https://nlp.stanford.edu/projects/glove/) pretrained word embeddings.\n",
        "\n",
        "**Note**: this section will take *several minutes*, since the embedding files are large. Files in Colab may be cached between sessions, so you may or may not need to redownload the files each time you reconnect. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0u26MFsgjKcM",
        "outputId": "f0b1cd0c-105b-4141-d8dc-7207bc58e7db",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 354
        }
      },
      "source": [
        "!wget http://nlp.stanford.edu/data/glove.6B.zip\n",
        "!unzip glove*.zip"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "--2020-04-15 01:48:14--  http://nlp.stanford.edu/data/glove.6B.zip\n",
            "Resolving nlp.stanford.edu (nlp.stanford.edu)... 171.64.67.140\n",
            "Connecting to nlp.stanford.edu (nlp.stanford.edu)|171.64.67.140|:80... connected.\n",
            "HTTP request sent, awaiting response... 302 Found\n",
            "Location: https://nlp.stanford.edu/data/glove.6B.zip [following]\n",
            "--2020-04-15 01:48:15--  https://nlp.stanford.edu/data/glove.6B.zip\n",
            "Connecting to nlp.stanford.edu (nlp.stanford.edu)|171.64.67.140|:443... connected.\n",
            "HTTP request sent, awaiting response... 301 Moved Permanently\n",
            "Location: http://downloads.cs.stanford.edu/nlp/data/glove.6B.zip [following]\n",
            "--2020-04-15 01:48:15--  http://downloads.cs.stanford.edu/nlp/data/glove.6B.zip\n",
            "Resolving downloads.cs.stanford.edu (downloads.cs.stanford.edu)... 171.64.64.22\n",
            "Connecting to downloads.cs.stanford.edu (downloads.cs.stanford.edu)|171.64.64.22|:80... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 862182613 (822M) [application/zip]\n",
            "Saving to: ‘glove.6B.zip.1’\n",
            "\n",
            "glove.6B.zip.1        8%[>                   ]  71.91M  3.83MB/s    eta 2m 20s ^C\n",
            "Archive:  glove.6B.zip\n",
            "replace glove.6B.50d.txt? [y]es, [n]o, [A]ll, [N]one, [r]ename: N\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "njKMNfHmjKcR"
      },
      "source": [
        "### Question 1. Checking for Projectivity\n",
        "In this question, you are supposed to implement the `is_projective` function below.\n",
        "* A tree structure is said to be [projective](https://en.wikipedia.org/wiki/Discontinuity_(linguistics)) if there are no crossing dependency edges and/or projection lines. \n",
        "* The function should take a sentence as input and returns True if and only if the tree is projective."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fME7S_whjKcT"
      },
      "source": [
        "def is_projective(toks):\n",
        "    \"\"\"\n",
        "    params: toks is a list of (idd, tok, pos, head, lab) for a sentence\n",
        "    return True if and only if the sentence has a projective dependency tree\n",
        "    \"\"\"\n",
        "\n",
        "    # Implement your code below\n",
        "    \n",
        "    ##################\n",
        "    # YOUR CODE HERE\n",
        "\n",
        "    isok = True\n",
        "    def check_arcs(start, end, head):\n",
        "      nonlocal isok\n",
        "      for i in range(start, end, 1 if start<end else -1):\n",
        "        while True:\n",
        "          if i == head:\n",
        "            break;\n",
        "          if i not in saved:\n",
        "            isok = False\n",
        "            return;\n",
        "          i = saved[i]\n",
        "      \n",
        "    saved = {}\n",
        "    for t in toks:\n",
        "      saved[t[0]] = t[3]\n",
        "\n",
        "    for i in toks:\n",
        "      if isok:\n",
        "        check_arcs(i[0], i[3], i[3])\n",
        "      else:\n",
        "        break;\n",
        "    \n",
        "    return isok\n",
        "\n",
        "    ##################\n",
        "    #{1: 3, 2: 3, 3: 4, 4: 0, 5: 6, 6: 4, 7: 4}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ccPr3IevJFd8",
        "outputId": "ae6b5cf2-3040-4303-aeca-674b5ac0d348",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def sanity_check_is_projective():\n",
        "    \"\"\"\n",
        "    Sanity check for the function is_projective()\n",
        "    \"\"\"\n",
        "    # \"From the AP comes this story:\" should be projective\n",
        "    proj_toks = [(1, 'From', 'IN', 3, 'case'), \n",
        "                  (2, 'the', 'DT', 3, 'det'), \n",
        "                  (3, 'AP', 'NNP', 4, 'obl'), \n",
        "                  (4, 'comes', 'VBZ', 0, 'root'), \n",
        "                  (5, 'this', 'DT', 6, 'det'), \n",
        "                  (6, 'story', 'NN', 4, 'nsubj'), \n",
        "                  (7, ':', ':', 4, 'punct')]\n",
        "    assert is_projective(proj_toks) == True\n",
        "    \n",
        "    # \"I saw a man today who is tall\" should not be projective\n",
        "    non_proj_toks = [(1, 'I', 'PRP', 2, 'nsubj'), \n",
        "                      (2, 'saw', 'VBD', 0, 'root'), \n",
        "                      (3, 'a', 'DT', 4, 'det'), \n",
        "                      (4, \"man\", 'NN', 2, 'obj'), \n",
        "                      (5, 'today', 'NN', 2, 'nmod'), \n",
        "                      (6, 'who', 'WP', 8, 'nsubj'), \n",
        "                      (7, 'is', 'VBZ', 8, 'cop'), \n",
        "                      (8, 'tall', 'JJ', 4, 'acl:relcl')]\n",
        "    assert is_projective(non_proj_toks) == False\n",
        "    print(\"Congrats! You have passed the basic sanity check of is_projective().\")\n",
        "    \n",
        "sanity_check_is_projective()    "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Congrats! You have passed the basic sanity check of is_projective().\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eCZUcO60jKcW"
      },
      "source": [
        "### Question 2.a.\n",
        "Implement the first helper function `perform_shift` to achieve the SHIFT operation.\n",
        "* The SHIFT Operation removes the word from the front of the input buffer and pushes it onto stack."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CFzJksVqjKcX"
      },
      "source": [
        "import copy\n",
        "def perform_shift(wbuffer, stack, arcs,\n",
        "                  configurations, gold_transitions):\n",
        "    \"\"\"\n",
        "    perform the SHIFT operation\n",
        "    \"\"\"\n",
        "\n",
        "    # Implement your code below\n",
        "    # your code should:\n",
        "    # 1. append the latest configuration to configurations\n",
        "    # 2. append the latest action to gold_transitions\n",
        "    # 3. update wbuffer, stack and arcs accordingly\n",
        "    # hint: note that the order of operations matters\n",
        "    # as we want to capture the configurations and transition rules\n",
        "    # before making changes to the stack, wbuffer and arcs\n",
        "    \n",
        "    ##################\n",
        "    # YOUR CODE HERE\n",
        "  \n",
        "    configurations.append((copy.deepcopy(wbuffer), copy.deepcopy(stack), copy.deepcopy(arcs)))\n",
        "    gold_transitions.append(\"SHIFT\")\n",
        "    stack.append(wbuffer.pop(-1))\n",
        "  \n",
        "    ##################\n",
        "    "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Nt_K4zkCJRcV",
        "outputId": "4b66d144-fb42-4dfc-8458-5d3639afd475",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def sanity_check_perform_shift():\n",
        "    \"\"\"\n",
        "    Sanity check for the function perform_shift()\n",
        "    \"\"\"    \n",
        "    # Before perform SHIFT\n",
        "    wbuffer = [3, 2, 1]\n",
        "    stack = [0]\n",
        "    arcs = []\n",
        "    configurations = []\n",
        "    gold_transitions = []\n",
        "\n",
        "    # Perform SHIFT\n",
        "    perform_shift(wbuffer, stack, arcs, configurations, gold_transitions)\n",
        "\n",
        "    # After perform SHIFT\n",
        "    assert wbuffer == [3, 2], \"The result for wbuffer is not correct\"\n",
        "    assert stack == [0, 1], \"The result for stack is not correct\"\n",
        "    assert arcs == [], \"The result for arcs is not correct\"\n",
        "    assert configurations == [([3, 2, 1], [0], [])], \"The result for configurations is not correct\"\n",
        "    assert gold_transitions == ['SHIFT'], \"The result for gold_transitions is not correct\"\n",
        "    print(\"Cool! You have passed the basic sanity check of perform_shift().\")\n",
        "    \n",
        "sanity_check_perform_shift()    "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Cool! You have passed the basic sanity check of perform_shift().\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JxqIrNnzjKcb"
      },
      "source": [
        "### Question 2.b.\n",
        "Implement the second helper function `perform_arc` to achieve the ARC operation.\n",
        "\n",
        "* LEFT-ARC (label): assert relation between head at $stack_1$ and dependent at $stack_2$: remove $stack_2$\n",
        "* RIGHT-ARC (label): assert relation between head at $stack_2$ and dependent at $stack_1$; remove $stack_1$ "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NW9_Y2fyjKcc"
      },
      "source": [
        "def perform_arc(direction, dep_label,\n",
        "                wbuffer, stack, arcs,\n",
        "                configurations, gold_transitions):\n",
        "    \"\"\"\n",
        "    params:\n",
        "        - direction: {\"LEFT\", \"RIGHT\"}\n",
        "        - dep_label: label for the dependency relations\n",
        "    Perform LEFTARC_ and RIGHTARC_ operations\n",
        "    \"\"\"\n",
        "    #Implement your code below\n",
        "    # your code should:\n",
        "    # 1. append the latest configuration to configurations\n",
        "    # 2. append the latest action to gold_transitions\n",
        "    # 3. update wbuffer, stack and arcs accordingly\n",
        "    # hint: note that the order of operations matters\n",
        "    # as we want to capture the configurations and transition rules\n",
        "    # before making changes to the stack, wbuffer and arcs\n",
        "\n",
        "    ##################\n",
        "    # YOUR CODE HERE\n",
        "    configurations.append((copy.deepcopy(wbuffer), copy.deepcopy(stack), copy.deepcopy(arcs)))\n",
        "    gold_transitions.append(str(direction)+\"ARC_\"+str(dep_label))\n",
        "    if direction == \"LEFT\":\n",
        "      arcs.append((dep_label, stack[-1], stack[-2]))\n",
        "      stack.pop(-2)\n",
        "    else:\n",
        "      arcs.append((dep_label, stack[-2], stack[-1]))\n",
        "      stack.pop(-1)\n",
        "    ##################\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YbvwB7kkJV95",
        "outputId": "fa45eb88-d915-44e8-9c1e-ce14bafd29e2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def sanity_check_perform_arc():\n",
        "    \"\"\"\n",
        "    Sanity check for the function perform_arc()\n",
        "    \"\"\"\n",
        "    # Before perform ARC\n",
        "    direction = 'RIGHT'\n",
        "    dep_label = 'punct'\n",
        "    wbuffer = [5, 4, 3]\n",
        "    stack = [0, 1, 2]\n",
        "    arcs = []\n",
        "    configurations = [([5, 4, 3, 2, 1], [0], []), \n",
        "                      ([5, 4, 3, 2], [0, 1], [])]\n",
        "    gold_transitions = ['SHIFT', 'SHIFT']\n",
        "\n",
        "    # Perform ARC\n",
        "    perform_arc(direction, dep_label, wbuffer, stack, arcs, configurations, gold_transitions)\n",
        "\n",
        "    # After perform ARC\n",
        "    assert wbuffer == [5, 4, 3], \"The result for wbuffer is not correct\"\n",
        "    #print(stack)\n",
        "    assert stack == [0, 1], \"The result for stack is not correct\"\n",
        "    assert arcs == [('punct', 1, 2)], \"The result for arcs is not correct\"\n",
        "    assert configurations == [([5, 4, 3, 2, 1], [0], []), \n",
        "                              ([5, 4, 3, 2], [0, 1], []), \n",
        "                              ([5, 4, 3], [0, 1, 2], [])], \"The result for configurations is not correct\"\n",
        "    assert gold_transitions == ['SHIFT', 'SHIFT', 'RIGHTARC_punct'], \"The result for gold_transitions is not correct\"\n",
        "    print(\"You have passed the basic sanity check of perform_arc().\")\n",
        "\n",
        "sanity_check_perform_arc()    "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "You have passed the basic sanity check of perform_arc().\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mmDSyQpqjKcg"
      },
      "source": [
        "### Question 2.c.\n",
        "Now, since we have implemented the helper functions, let's use them to complete `tree_to_actions`.\n",
        "\n",
        "`tree_to_actions` takes wbuffer, stack, arcs and deps as input, returns configuration of the parser and action for the parser."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pFTfAwLWjKcm"
      },
      "source": [
        "def isvalid(stack, wbuffer, action):\n",
        "    \"\"\"\n",
        "    Helper function that returns True only if an action is\n",
        "    legal given the current states of the stack and wbuffer\n",
        "    \"\"\"\n",
        "    if action == \"SHIFT\" and len(wbuffer) > 0:\n",
        "        return True\n",
        "    if action.startswith(\"RIGHTARC\") and len(stack) > 1 and stack[-1] != 0:\n",
        "        return True\n",
        "    if action.startswith(\"LEFTARC\") and len(stack) > 1 and stack[-2] != 0:\n",
        "        return True\n",
        "\n",
        "    return False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9HeTVArDjKci"
      },
      "source": [
        "def tree_to_actions(wbuffer, stack, arcs, deps):\n",
        "    \"\"\"\n",
        "    params:\n",
        "    wbuffer: a list of word indices; the top of buffer is at the end of the list\n",
        "    stack: a list of word indices; the top of buffer is at the end of the list\n",
        "    arcs: a list of (label, head, dependent) tuples\n",
        "    Given wbuffer, stack, arcs and deps, return configurations and gold_transitions (actions)\n",
        "    \"\"\"\n",
        "    # configurations: A list of tuples of lists [(wbuffer1, stack1, arcs1), (wbuffer2, stack2, arcs2), ...]: Keeps tracks of the states at each step\n",
        "    configurations=[]\n",
        "    # gold_transitions: A list of action strings, e.g [\"SHIFT\", \"LEFTARC_nsubj\"]: Keeps tracks of the actions at each step\n",
        "    gold_transitions=[]\n",
        "\n",
        "    # 1. configurations[i] and gold_transitions[i] should correspond to the states of the wbuffer, stack, arcs and action to take at step i\n",
        "    # 2. you should call perform_shift and perform_arc in your code\n",
        "    ##################\n",
        "    # YOUR CODE HERE\n",
        "    #print(wbuffer == None)\n",
        "   \n",
        "    perform_shift(wbuffer, stack, arcs, configurations, gold_transitions)\n",
        "    while (stack != [0]):\n",
        "      \n",
        "      #print(wbuffer, stack, arcs, gold_transitions)\n",
        "      \n",
        "      if ((len(stack) < 2) and (wbuffer != [])):\n",
        "        perform_shift(wbuffer, stack, arcs, configurations, gold_transitions)\n",
        "        continue;\n",
        "      \n",
        "      # check for left arc\n",
        "      if isvalid(stack, wbuffer, \"LEFTARC\"):\n",
        "        #print(\"second\")\n",
        "        if (stack[-1] in deps) and ((stack[-1], stack[-2]) in deps[stack[-1]]):\n",
        "          #print(len(stack))\n",
        "          label = deps[stack[-1]][(stack[-1],stack[-2])]\n",
        "          removableL = True\n",
        "          if stack[-2] in deps:\n",
        "            for pair in deps[stack[-2]].keys():\n",
        "              if (deps[stack[-2]][pair], pair[0], pair[1]) not in arcs:\n",
        "                removableL = False\n",
        "          if removableL:\n",
        "            perform_arc(\"LEFT\", label, wbuffer, stack, arcs, configurations, gold_transitions)\n",
        "            continue;\n",
        "      \n",
        "      #print(\"one\")\n",
        "      if isvalid(stack, wbuffer, \"RIGHTARC\"):\n",
        "        #print(\"two\")\n",
        "        if (stack[-2] in deps) and ((stack[-2], stack[-1]) in deps[stack[-2]]):\n",
        "          #print(\"three\")\n",
        "          # check for right arc\n",
        "          label =deps[stack[-2]][(stack[-2],stack[-1])]\n",
        "          removableR = True\n",
        "          if stack[-1] in deps:\n",
        "            for pair in deps[stack[-1]].keys():\n",
        "              if (deps[stack[-1]][pair], pair[0], pair[1]) not in arcs:\n",
        "                removableR = False\n",
        "          if removableR:\n",
        "            #print(stack)\n",
        "            perform_arc(\"RIGHT\", label, wbuffer, stack, arcs, configurations, gold_transitions)\n",
        "            #print(stack)\n",
        "            continue;\n",
        "        \n",
        "        # shift\n",
        "        if isvalid(stack, wbuffer, \"SHIFT\"):\n",
        "          perform_shift(wbuffer, stack, arcs, configurations, gold_transitions)\n",
        "          continue;\n",
        "    \n",
        "\n",
        "    return configurations, gold_transitions\n",
        "    ##################\n",
        "    "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fYpLgArZJb1X",
        "outputId": "4150fbbc-b05b-498e-9485-6840be432a49",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def sanity_check_tree_to_actions():\n",
        "    \"\"\"\n",
        "    Sanity check for the function tree_to_actions()\n",
        "    \"\"\"\n",
        "    # Before tree_to_actions \n",
        "    wbuffer = [9, 8, 7, 6, 5, 4, 3, 2, 1]\n",
        "    stack = [0]\n",
        "    arcs = []\n",
        "    deps = {5: {(5, 9): 'punct', (5, 8): 'obl', (5, 4): 'advmod', (5, 3): 'aux:pass', (5, 2): 'nsubj:pass'},\n",
        "            8: {(8, 7): 'det', (8, 6): 'case'}, 0: {(0, 5): 'root'}, 2: {(2, 1): 'nmod:poss'}}\n",
        "\n",
        "    tree_to_actions(wbuffer, stack, arcs, deps)\n",
        "\n",
        "    # After tree_to_actions\n",
        "    #print(wbuffer)\n",
        "    assert wbuffer == [], \"The result for wbuffer is not correct\"\n",
        "    assert stack == [0], \"The result for stack is not correct\"\n",
        "    assert arcs == [('nmod:poss', 2, 1), ('advmod', 5, 4), ('aux:pass', 5, 3), ('nsubj:pass', 5, 2), \n",
        "                     ('det', 8, 7), ('case', 8, 6), ('obl', 5, 8), ('punct', 5, 9), ('root', 0, 5)], \\\n",
        "                        \"The result for arcs is not correct\"\n",
        "    assert deps == {5: {(5, 9): 'punct', (5, 8): 'obl', (5, 4): 'advmod', (5, 3): 'aux:pass', (5, 2): 'nsubj:pass'}, \n",
        "                     8: {(8, 7): 'det', (8, 6): 'case'}, 0: {(0, 5): 'root'}, 2: {(2, 1): 'nmod:poss'}}, \\\n",
        "                    \"The result for deps is not correct\"\n",
        "    print(\"You have passed the basic sanity check of tree_to_actions()! One more function to go.\")   \n",
        "     \n",
        "sanity_check_tree_to_actions()    "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "You have passed the basic sanity check of tree_to_actions()! One more function to go.\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IlLh-Q_sjKcl"
      },
      "source": [
        "### Question 3. Tree Parsing with Predictions\n",
        "Implement action_to_tree, which will update the dependency tree based on the action predictions.\n",
        "* Don't forget to use `isvalid` to check the validity of the possible actions!"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RH_vzMzRjKcp"
      },
      "source": [
        "def action_to_tree(tree, predictions, wbuffer, stack, arcs, reverse_labels):\n",
        "    \"\"\"\n",
        "    tree: a dictionary of dependency relations (head, dep_label)\n",
        "        {child1: (head1, dep_lebel1),\n",
        "         child2: (head2, dep_label2), ...}\n",
        "    predictions: a numpy column vector of probabilities for different dependency labels as ordered by the variable reverse_labels\n",
        "                  predictions.shape = (1, total number of dependency labels)\n",
        "    wbuffer: a list of word indices; top of buffer is at the end of the list\n",
        "    stack: a list of word indices; top of stack is at the end of the list\n",
        "    arcs: a list of (label, head, dependent) tuples\n",
        "\n",
        "    \"\"\"\n",
        "    # Implement your code below\n",
        "    # 1. the predictions contains the probability distribution for all possible actions for a single step, and you should choose one\n",
        "    # and update the tree only once\n",
        "    # 2. some actions predicted are not going to be valid (e.g., shifting if nothing is on the buffer) so sort probs and keep going until you find one that is valid.\n",
        "    ##################\n",
        "    # YOUR CODE HERE'\n",
        "    combos = [(predictions[0][i], reverse_labels[i]) for i in range(len(predictions[0]))]\n",
        "    combos = sorted(combos, key=lambda c: c[0], reverse = True)\n",
        "    #print(combos)\n",
        "    \n",
        "    index = 0\n",
        "    acted = False\n",
        "    while not acted:\n",
        "      action = combos[index][1]\n",
        "      if isvalid(stack,wbuffer,action):\n",
        "        acted = True\n",
        "        #print(combos, action)\n",
        "        if action.startswith(\"RIGHTARC\"):\n",
        "          label = action.split(\"_\")[1]\n",
        "          dep = stack[-1]\n",
        "          hed = stack[-2]\n",
        "          arcs.append((label, hed, dep))\n",
        "          tree[dep] = (hed, label)\n",
        "          stack.pop(-1)\n",
        "        \n",
        "        elif action.startswith(\"LEFTARC\"):\n",
        "          label = action.split(\"_\")[1]\n",
        "          dep = stack[-2]\n",
        "          hed = stack[-1]\n",
        "          arcs.append((label, hed, dep))\n",
        "          tree[dep] = (hed, label)\n",
        "          stack.pop(-2)\n",
        "        \n",
        "        else:\n",
        "          # shift\n",
        "          stack.append(wbuffer.pop(-1))\n",
        "        break;\n",
        "      else:\n",
        "        index += 1\n",
        "    ##################\n",
        "      "
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "W7ZoAad9JiPF",
        "outputId": "431e233b-adb3-403a-d083-650fe612f7fe",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "def sanity_check_action_to_tree():\n",
        "    \"\"\"\n",
        "    Sanity check for the function action_to_tree()\n",
        "    \"\"\"    \n",
        "    # Before action\n",
        "    tree = {}\n",
        "    predictions = np.array([[ 8.904456  ,  2.1306312 , -0.6716528 , -0.37662476, -0.01239625,-3.3660867 , -2.1345713 ,  1.4581618 , \n",
        "                             -0.1688145 , -0.61321   , 0.40860286, -2.7569351 , -0.69548404, -0.7809651 ,  0.7595304 ,-2.770731  , \n",
        "                             -0.97373027, -2.70085   , -0.26645675, -1.2353135 ,-1.4289687 , -1.3272284 , -2.4956157 , -1.0178847 , \n",
        "                             -1.7484616 , 1.7610879 ,  0.301237  , -0.71727145, -1.9370077 , -1.3722429 , 0.9516849 , -2.6749346 , \n",
        "                             -1.4604743 , -1.6903474 , -2.5261753 ,-0.88417345, -0.50328434, -0.21296862, -3.4296887 , -3.3282495 ,\n",
        "                             -4.300956  , -2.12365   , -3.3637137 , -5.570282  , -3.8983932 ,-3.0985348 , -5.818429  , -1.5155774 , \n",
        "                             -3.4247532 , -2.7098398 ,-4.799152  , -4.020282  , -3.5505116 , -2.7114115 , -4.1488724 ,-4.7484784 , \n",
        "                             -4.0955606 , -2.994336  , -4.9744525 , -4.3390574 ,-2.782462  , -4.615161  , -4.6250424 , -4.4105268 , \n",
        "                             -4.856515  ,-3.5684056 , -4.6808653 , -4.882898  , -4.3673973 , -5.379696  ]])\n",
        "    \n",
        "    reverse_labels = ['SHIFT', 'RIGHTARC_punct', 'RIGHTARC_flat', 'LEFTARC_amod', 'LEFTARC_nsubj', 'LEFTARC_det', 'RIGHTARC_appos', \n",
        "                      'RIGHTARC_obj', 'LEFTARC_case', 'RIGHTARC_nmod', 'RIGHTARC_obl', 'RIGHTARC_parataxis', 'RIGHTARC_root', 'LEFTARC_aux', \n",
        "                      'LEFTARC_punct', 'RIGHTARC_iobj', 'LEFTARC_mark', 'RIGHTARC_acl', 'RIGHTARC_compound:prt', 'LEFTARC_nummod', \n",
        "                      'RIGHTARC_ccomp', 'LEFTARC_aux:pass', 'LEFTARC_nsubj:pass', 'LEFTARC_compound', 'LEFTARC_nmod:poss', 'LEFTARC_cc', \n",
        "                      'RIGHTARC_conj', 'LEFTARC_advmod', 'RIGHTARC_xcomp', 'LEFTARC_advcl', 'RIGHTARC_advmod', 'RIGHTARC_acl:relcl', \n",
        "                      'RIGHTARC_advcl', 'LEFTARC_expl', 'RIGHTARC_nsubj', 'LEFTARC_obl', 'LEFTARC_cop', 'RIGHTARC_fixed', 'RIGHTARC_nummod', \n",
        "                      'LEFTARC_det:predet', 'RIGHTARC_obl:npmod', 'RIGHTARC_obl:tmod', 'LEFTARC_obl:tmod', 'RIGHTARC_nmod:tmod', \n",
        "                      'RIGHTARC_amod', 'LEFTARC_csubj', 'LEFTARC_csubj:pass', 'RIGHTARC_case', 'RIGHTARC_det', 'LEFTARC_obj', \n",
        "                      'LEFTARC_nmod:tmod', 'LEFTARC_nmod', 'RIGHTARC_cop', 'RIGHTARC_expl', 'RIGHTARC_aux', 'RIGHTARC_vocative', \n",
        "                      'RIGHTARC_csubj', 'LEFTARC_obl:npmod', 'RIGHTARC_nmod:npmod', 'RIGHTARC_list', 'LEFTARC_ccomp', 'LEFTARC_discourse', \n",
        "                      'LEFTARC_parataxis', 'LEFTARC_xcomp', 'RIGHTARC_csubj:pass', 'LEFTARC_cc:preconj', 'RIGHTARC_flat:foreign', \n",
        "                      'RIGHTARC_compound', 'LEFTARC_acl:relcl', 'RIGHTARC_discourse']\n",
        "\n",
        "    wbuffer = [4,3,2,1]\n",
        "    stack = [0]\n",
        "    arcs = []\n",
        "    # Perform action\n",
        "    action_to_tree(tree, predictions, wbuffer, stack, arcs, reverse_labels)\n",
        "\n",
        "    # After action (the action is SHIFT for this step)\n",
        "    assert not tree, \"The tree should be {} after the SHIFT\"\n",
        "    assert wbuffer == [4,3,2], \"wbuffer should be [4,3,2] after the SHIFT\"\n",
        "    assert stack == [0, 1], \"stack should be [0, 1] after the SHIFT\"\n",
        "    assert arcs == [], \"arcs should be [] after the SHIFT\"\n",
        "    print(\"You have passed the basic sanity check of action_to_tree()!\")\n",
        "    \n",
        "sanity_check_action_to_tree()    "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "You have passed the basic sanity check of action_to_tree()!\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pJsWiPY5jKcu"
      },
      "source": [
        "### Implemented for you\n",
        "Now since you have the configuration $x$ and action $y$, we can now train a supervised model to predict an action $y$ given a configuration $x$. We are using a simplified version model of [A Fast and Accurate Dependency Parser using Neural Networks](https://nlp.stanford.edu/pubs/emnlp2014-depparser.pdf).\n",
        "\n",
        "* This model is alreadly implemented for you, please `train` the model, and report the evaluation and test results by calling the function `evaluate` and `test`"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vlx_IRrJjKcv"
      },
      "source": [
        "# ============================================================\n",
        "# THE FOLLOWING CODE IS PROVIDED\n",
        "# ============================================================\n",
        "def get_oracle(toks):\n",
        "    \"\"\"\n",
        "    Return pairs of configurations + gold transitions (actions)\n",
        "    from training data\n",
        "    configuration = a list of tuple of:\n",
        "        - buffer (top of buffer is at the end of the list)\n",
        "        - stack (top of buffer is at the end of the list)\n",
        "        - arcs (a list of (label, head, dependent) tuples)\n",
        "    gold transitions = a list of actions, e.g. SHIFT\n",
        "    \"\"\"\n",
        "\n",
        "    stack = [] # stack\n",
        "    arcs = [] # existing list of arcs\n",
        "    wbuffer = [] # input buffer\n",
        "\n",
        "    # deps is a dictionary of head: dependency relations, where\n",
        "    # dependency relations is a dictionary of the (head, child): label\n",
        "    # deps = {head1:{\n",
        "    #               (head1, child1):dependency_label1,\n",
        "    #               (head1, child2):dependency_label2\n",
        "    #              }\n",
        "    #         head2:{\n",
        "    #               (head2, child3):dependency_label3,\n",
        "    #               (head2, child4):dependency_label4\n",
        "    #              }\n",
        "    #         }\n",
        "    deps = {}\n",
        "\n",
        "    # ROOT\n",
        "    stack.append(0)\n",
        "\n",
        "    # initialize variables\n",
        "    for position in reversed(toks):\n",
        "        (idd, _, _, head, lab) = position\n",
        "\n",
        "        dep = (head, idd)\n",
        "        if head not in deps:\n",
        "            deps[head] = {}\n",
        "        deps[head][dep] = lab\n",
        "\n",
        "        wbuffer.append(idd)\n",
        "\n",
        "    # configurations:\n",
        "    # A list of (wbuffer, stack, arcs)\n",
        "    # Keeps tracks of the states at each step\n",
        "    # gold_transitions:\n",
        "    # A list of action strings [\"SHIFT\", \"LEFTARC_nsubj\"]\n",
        "    # Keeps tracks of the actions at each step\n",
        "    configurations, gold_transitions = tree_to_actions(wbuffer, stack, arcs, deps)\n",
        "    return configurations, gold_transitions\n",
        "\n",
        "def featurize_configuration(configuration, tokens, postags, vocab, pos_vocab):\n",
        "\n",
        "    def get_id(word, vocab):\n",
        "        word=word.lower()\n",
        "        if word in vocab:\n",
        "            return vocab[word]\n",
        "        return vocab[\"<unk>\"]\n",
        "\n",
        "    \"\"\"\n",
        "    Given configurations of the stack, input buffer and arcs,\n",
        "    words of the sentence and POS tags of the words,\n",
        "    return some features\n",
        "\n",
        "    The current features are the word ID and postag ID at the \n",
        "    first three positions of the stack and buffer.\n",
        "    \"\"\"\n",
        "\n",
        "    wbuffer, stack, arcs = configuration\n",
        "\n",
        "    word_features=[]\n",
        "    pos_features=[]\n",
        "\n",
        "    if len(stack) > 0: \n",
        "        word_features.append(get_id(tokens[stack[-1]], vocab))\n",
        "        pos_features.append(get_id(postags[stack[-1]], pos_vocab))\n",
        "    else: \n",
        "        word_features.append(get_id(\"<NONE>\", vocab))\n",
        "        pos_features.append(get_id(\"<NONE>\", pos_vocab))\n",
        "\n",
        "    if len(stack) > 1: \n",
        "        word_features.append(get_id(tokens[stack[-2]], vocab))\n",
        "        pos_features.append(get_id(postags[stack[-2]], pos_vocab))\n",
        "    else: \n",
        "        word_features.append(get_id(\"<NONE>\", vocab))\n",
        "        pos_features.append(get_id(\"<NONE>\", pos_vocab))\n",
        "\n",
        "    if len(stack) > 2: \n",
        "        word_features.append(get_id(tokens[stack[-3]], vocab))\n",
        "        pos_features.append(get_id(postags[stack[-3]], pos_vocab))\n",
        "    else: \n",
        "        word_features.append(get_id(\"<NONE>\", vocab))\n",
        "        pos_features.append(get_id(\"<NONE>\", pos_vocab))\n",
        "\n",
        "    if len(wbuffer) > 0: \n",
        "        word_features.append(get_id(tokens[wbuffer[-1]], vocab))\n",
        "        pos_features.append(get_id(postags[wbuffer[-1]], pos_vocab))\n",
        "    else: \n",
        "        word_features.append(get_id(\"<NONE>\", vocab))\n",
        "        pos_features.append(get_id(\"<NONE>\", pos_vocab))\n",
        "       \n",
        "    if len(wbuffer) > 1: \n",
        "        word_features.append(get_id(tokens[wbuffer[-2]], vocab))\n",
        "        pos_features.append(get_id(postags[wbuffer[-2]], pos_vocab))\n",
        "    else: \n",
        "        word_features.append(get_id(\"<NONE>\", vocab))\n",
        "        pos_features.append(get_id(\"<NONE>\", pos_vocab))\n",
        "\n",
        "    if len(wbuffer) > 2: \n",
        "        word_features.append(get_id(tokens[wbuffer[-3]], vocab))\n",
        "        pos_features.append(get_id(postags[wbuffer[-3]], pos_vocab))\n",
        "    else: \n",
        "        word_features.append(get_id(\"<NONE>\", vocab))\n",
        "        pos_features.append(get_id(\"<NONE>\", pos_vocab))\n",
        "\n",
        "    return word_features, pos_features\n",
        "\n",
        "\n",
        "def get_oracles(filename, vocab, tag_vocab):\n",
        "    \"\"\"\n",
        "    Get configurations, gold_transitions from all sentences\n",
        "    \"\"\"\n",
        "    with open(filename) as f:\n",
        "        toks, tokens, postags = [], {}, {}\n",
        "        tokens[0] = \"<ROOT>\"\n",
        "        postags[0] = \"<ROOT>\"\n",
        "\n",
        "        # a list of all features for each transition step\n",
        "        word_feats = []\n",
        "        pos_feats = []\n",
        "        # a list of labels, e.g. SHIFT, LEFTARC_DEP_LABEL, RIGHTARC_DEP_LABEL\n",
        "        labels = []\n",
        "\n",
        "        save = 0\n",
        "        for line in f:\n",
        "            cols = line.rstrip().split(\"\\t\")\n",
        "            \n",
        "            if len(cols) < 2: # at the end of each sentence\n",
        "                if len(toks) > 0:\n",
        "                    if is_projective(toks): # only use projective trees\n",
        "                        # get all configurations and gold standard transitions\n",
        "                        configurations, gold_transitions = get_oracle(toks)\n",
        "                        save += 1\n",
        "                        for i in range(len(configurations)):\n",
        "                            word_feat, pos_feat = featurize_configuration(configurations[i], tokens, postags, vocab, tag_vocab)\n",
        "                            label = gold_transitions[i]\n",
        "                            word_feats.append(word_feat)\n",
        "                            pos_feats.append(pos_feat)\n",
        "                            labels.append(label)\n",
        "\n",
        "                    # reset vars for the next sentence\n",
        "                    toks, tokens, postags = [], {}, {}\n",
        "                    tokens[0] = \"<ROOT>\"\n",
        "                    postags[0] = \"<ROOT>\"\n",
        "                    \n",
        "                continue\n",
        "\n",
        "            if cols[0].startswith(\"#\"):\n",
        "                continue\n",
        "\n",
        "            # construct the tuple for each word in the sentence\n",
        "            # for each word in the sentence\n",
        "            # idd: index of a word in a sentence, starting from 1\n",
        "            # tok: the word itself\n",
        "            # pos: pos tag for that word\n",
        "            # head: parent of the dependency\n",
        "            # lab: dependency relation label\n",
        "            idd, tok, pos, head, lab = int(cols[0]), cols[1], cols[4], int(cols[6]), cols[7]\n",
        "            toks.append((idd, tok, pos, head, lab))\n",
        "\n",
        "            # feature for training to predict the gold transition\n",
        "            tokens[idd], postags[idd] = tok, pos\n",
        "        print(\"projective trees: \" + str(save))\n",
        "        return word_feats, pos_feats, labels\n",
        "\n",
        "def load_embeddings(filename):\n",
        "    # 0 idx is for padding\n",
        "    # 1 idx is for <UNK>\n",
        "    # 2 idx is for <NONE>\n",
        "    # 3 idx is for <ROOT>\n",
        "\n",
        "    # get the embedding size from the first embedding\n",
        "    vocab_size=4\n",
        "    with open(filename, encoding=\"utf-8\") as file:\n",
        "        for idx, line in enumerate(file):\n",
        "            if idx == 0:\n",
        "                word_embedding_dim=len(line.rstrip().split(\" \"))-1\n",
        "            vocab_size+=1\n",
        "        \n",
        "\n",
        "    vocab={\"<pad>\":0, \"<unk>\":1, \"<none>\":2, \"<root>\":3}\n",
        "    print(\"word_embedding_dim: %s, vocab size: %s\" % (word_embedding_dim, vocab_size))\n",
        "\n",
        "    embeddings=np.zeros((vocab_size, word_embedding_dim))\n",
        "\n",
        "    with open(filename, encoding=\"utf-8\") as file:\n",
        "        for idx,line in enumerate(file):\n",
        "\n",
        "            if idx + 4 >= vocab_size:\n",
        "                break\n",
        "\n",
        "            cols=line.rstrip().split(\" \")\n",
        "            val=np.array(cols[1:])\n",
        "            word=cols[0]\n",
        "            embeddings[idx+4]=val\n",
        "            vocab[word]=idx+4\n",
        "\n",
        "    return torch.FloatTensor(embeddings), vocab\n",
        "\n",
        "class ShiftReduceParser(nn.Module):\n",
        "\n",
        "    def __init__(self, embeddings, hidden_dim, tagset_size, num_pos_tags, pos_embedding_dim):\n",
        "        super(ShiftReduceParser, self).__init__()\n",
        "        self.hidden_dim = hidden_dim\n",
        "        self.num_labels=tagset_size\n",
        "\n",
        "        _, embedding_dim = embeddings.shape\n",
        "\n",
        "        self.input_size=embedding_dim*6 + pos_embedding_dim*6\n",
        "        \n",
        "        self.dropout_layer = nn.Dropout(p=0.25)\n",
        "\n",
        "        self.word_embeddings = nn.Embedding.from_pretrained(embeddings)\n",
        "        self.pos_embeddings = nn.Embedding(num_pos_tags, pos_embedding_dim)\n",
        "        self.tanh = nn.Tanh()\n",
        "        self.W1 = nn.Linear(self.input_size, self.hidden_dim)\n",
        "        self.W2 = nn.Linear(self.hidden_dim, self.num_labels)\n",
        "\n",
        "    def forward(self, words, pos_tags, Y=None):\n",
        "        \n",
        "        words=words.to(device)\n",
        "        pos_tags=pos_tags.to(device)\n",
        "\n",
        "        if Y is not None:\n",
        "            Y=Y.to(device)\n",
        "\n",
        "        word_embeds = self.word_embeddings(words)\n",
        "        postag_embeds = self.pos_embeddings(pos_tags)\n",
        "\n",
        "        embeds=torch.cat((word_embeds, postag_embeds), 2)\n",
        "\n",
        "        embeds=embeds.view(-1, self.input_size)\n",
        "\n",
        "        embeds=self.dropout_layer(embeds)\n",
        "\n",
        "        hidden = self.W1(embeds)\n",
        "        hidden = self.tanh(hidden)\n",
        "        logits = self.W2(hidden)\n",
        "\n",
        "        if Y is not None:\n",
        "            loss_fct = nn.CrossEntropyLoss()\n",
        "            loss = loss_fct(logits.view(-1, self.num_labels), Y.view(-1))\n",
        "            return loss\n",
        "        else:\n",
        "            return logits\n",
        "\n",
        "def get_batches(W, P, Y, batch_size):\n",
        "    batch_W=[]\n",
        "    batch_P=[]\n",
        "    batch_Y=[]\n",
        "\n",
        "    i=0\n",
        "    while i < len(W):\n",
        "        batch_W.append(torch.LongTensor(W[i:i+batch_size]))\n",
        "        batch_P.append(torch.LongTensor(P[i:i+batch_size]))\n",
        "        batch_Y.append(torch.LongTensor(Y[i:i+batch_size]))\n",
        "        i+=batch_size  \n",
        "\n",
        "    return batch_W, batch_P, batch_Y\n",
        "\n",
        "def train(word_feats, pos_feats, labels, embeddings, vocab, postag_vocab, label_vocab):\n",
        "    \"\"\"\n",
        "\n",
        "    Train transition-based parser to predict next action (labels)\n",
        "    given current configuration (featurized by word_feats and pos_feats)\n",
        "    Return the classifier trained using Chen and Manning (2014), \"A Fast \n",
        "    and Accurate Dependency Parser using Neural Networks\"\n",
        "\n",
        "    \"\"\"\n",
        "\n",
        "    # dimensionality of linear layer\n",
        "    HIDDEN_DIM=100\n",
        "    # dimensionality of POS embeddings\n",
        "    POS_EMBEDDING_SIZE=50\n",
        "\n",
        "    # batch size for training\n",
        "    BATCH_SIZE=32\n",
        "\n",
        "    # number of epochs to train for\n",
        "    NUM_EPOCHS=10\n",
        "\n",
        "    # learning rate for Adam optimizer\n",
        "    LEARNING_RATE=0.001\n",
        "\n",
        "    num_labels=[]\n",
        "    for i, y in enumerate(labels):\n",
        "        num_labels.append(label_vocab[y])\n",
        "\n",
        "    batch_W, batch_P, batch_Y = get_batches(word_feats, pos_feats, num_labels, BATCH_SIZE)\n",
        "\n",
        "    model = ShiftReduceParser(embeddings, HIDDEN_DIM, len(label_vocab), len(postag_vocab), POS_EMBEDDING_SIZE)\n",
        "    model.to(device)\n",
        "\n",
        "    optimizer = optim.Adam(model.parameters(), lr=LEARNING_RATE)\n",
        "\n",
        "    for epoch in range(NUM_EPOCHS):\n",
        "        model.train()\n",
        "\n",
        "        bigloss=0.\n",
        "        for b in range(len(batch_W)):\n",
        "            model.zero_grad()\n",
        "\n",
        "            loss = model.forward(batch_W[b], batch_P[b], Y=batch_Y[b])\n",
        "            bigloss+=loss.item()\n",
        "\n",
        "            loss.backward()\n",
        "            optimizer.step()\n",
        "\n",
        "        print(\"loss: \", bigloss)\n",
        "\n",
        "\n",
        "    return model\n",
        "\n",
        "\n",
        "def parse(toks, model, vocab, tag_vocab, reverse_labels):\n",
        "    \"\"\"\n",
        "    parse sentence with trained model and return correctness measure\n",
        "    \"\"\"\n",
        "    tokens, postags = {}, {}\n",
        "    tokens[0] = \"<ROOT>\"\n",
        "    postags[0] = \"<ROOT>\"\n",
        "\n",
        "    wbuffer, stack, arcs = [], [], []\n",
        "    stack.append(0)\n",
        "\n",
        "    #print(\"parsing:\")\n",
        "    for position in reversed(toks):\n",
        "\n",
        "        (idd, tok, pos, head, lab) = position\n",
        "        tokens[idd] = tok\n",
        "        postags[idd] = pos\n",
        "\n",
        "        # update buffer\n",
        "        wbuffer.append(idd)\n",
        "\n",
        "    tree = {}\n",
        "    #print(\"creating tree.\")\n",
        "    while len(wbuffer) >= 0:\n",
        "        \n",
        "        if len(wbuffer) == 0 and len(stack) == 0: break\n",
        "        #print(\"stack length != 0\")\n",
        "        if len(wbuffer) == 0 and len(stack) == 1 and stack[0] == 0: break\n",
        "        #print(\"stack != [0]\")\n",
        "        #print(stack)\n",
        "        word_feats, pos_feats = (featurize_configuration((wbuffer, stack, arcs), tokens, postags, vocab, tag_vocab))\n",
        "\n",
        "       \n",
        "        predictions=model.forward(torch.LongTensor([word_feats]), torch.LongTensor([pos_feats]))\n",
        "\n",
        "        predictions=predictions.detach().cpu().numpy()\n",
        "        #print(\"action_to_tree step\")\n",
        "        # your function will be called here\n",
        "        action_to_tree(tree, predictions, wbuffer, stack, arcs, reverse_labels)\n",
        "\n",
        "    return tree\n",
        "\n",
        "def parse_and_evaluate(toks, model, vocab, tag_vocab, reverse_labels):\n",
        "    \"\"\"\n",
        "    parse sentence with trained model and return correctness measure\n",
        "    \"\"\"\n",
        "\n",
        "    heads, labels = {}, {}\n",
        "\n",
        "    for position in reversed(toks):\n",
        "        (idd, tok, pos, head, lab) = position\n",
        "\n",
        "        # keep track of gold standards for performance evaluation\n",
        "        heads[idd], labels[idd] = head, lab\n",
        "\n",
        "    #print(\"going to parse\")\n",
        "    tree = parse(toks, model, vocab, tag_vocab, reverse_labels)\n",
        "    #print(\"done parsing\")\n",
        "    # correct_unlabeled: total number of correct (head, child) dependencies\n",
        "    # correct_labeled: total number of correctly *labeled* dependencies\n",
        "    correct_unlabeled, correct_labeled, total = 0, 0, 0\n",
        "\n",
        "    for child in tree:\n",
        "        (head, label) = tree[child]\n",
        "        if head == heads[child]:\n",
        "            correct_unlabeled += 1\n",
        "            if label == labels[child]: correct_labeled += 1\n",
        "        total += 1\n",
        "\n",
        "    return [correct_unlabeled, correct_labeled, total]\n",
        "\n",
        "def get_label_vocab(labels):\n",
        "    tag_vocab={}\n",
        "    num_labels=[]\n",
        "    for i, y in enumerate(labels):\n",
        "        if y not in tag_vocab:\n",
        "            tag_vocab[y]=len(tag_vocab)\n",
        "        num_labels.append(tag_vocab[y])\n",
        "\n",
        "    reverse_labels=[None]*len(tag_vocab)\n",
        "    for y in tag_vocab:\n",
        "        reverse_labels[tag_vocab[y]]=y\n",
        "\n",
        "    return tag_vocab, reverse_labels\n",
        "\n",
        "\n",
        "def get_pos_tag_vocab(filename):\n",
        "    tag_vocab={\"<none>\":0, \"<unk>\":1}\n",
        "    with open(filename) as file:\n",
        "        for line in file:\n",
        "            cols=line.rstrip().split(\"\\t\")\n",
        "            if len(cols) < 3:\n",
        "                continue\n",
        "            pos=cols[4].lower()\n",
        "            if pos not in tag_vocab:\n",
        "                tag_vocab[pos]=len(tag_vocab)\n",
        "    return tag_vocab\n",
        "\n",
        "def test(model, vocab, tag_vocab, reverse_labels):\n",
        "    \"\"\"\n",
        "    Evaluate the performance of a parser against gold standard\n",
        "    \"\"\"\n",
        "\n",
        "    model.eval()\n",
        "\n",
        "    toks=[\"I\", \"bought\", \"a\", \"book\"]\n",
        "    pos=[\"NNP\", \"VBD\", \"DT\", \"NN\"]\n",
        "\n",
        "    data=[]\n",
        "    # put it in format parser expects\n",
        "    for i, tok in enumerate(toks):\n",
        "        data.append((i+1, tok, pos[i], \"_\", \"_\"))\n",
        "\n",
        "    tree=parse(data, model, vocab, tag_vocab, reverse_labels)\n",
        "\n",
        "    for child in sorted(tree.keys()):\n",
        "        (head, label) = tree[child]\n",
        "        headStr=\"<ROOT>\"\n",
        "        if head > 0: # child and head indexes start at 1; 0 denotes the <ROOT>\n",
        "            headStr=toks[head-1]\n",
        "\n",
        "        print(\"(%s %s) -> (%s %s) %s\" % (child, toks[child-1], head, headStr, label))\n",
        "  \n",
        "\n",
        "\n",
        "def evaluate(filename, model, vocab, tag_vocab, reverse_labels):\n",
        "    \"\"\"\n",
        "    Evaluate the performance of a parser against gold standard\n",
        "    \"\"\"\n",
        "\n",
        "    model.eval()\n",
        "\n",
        "    with open(filename) as f:\n",
        "        toks=[]\n",
        "        totals = np.zeros(3)\n",
        "        for line in f:\n",
        "            cols=line.rstrip().split(\"\\t\")\n",
        "\n",
        "            if len(cols) < 2: # end of a sentence\n",
        "                if len(toks) > 0:\n",
        "                    if is_projective(toks):\n",
        "                        #print(\"so far so good\")\n",
        "                        tots = np.array(parse_and_evaluate(toks, model, vocab, tag_vocab, reverse_labels))\n",
        "                        totals += tots\n",
        "                        \n",
        "                    toks = []\n",
        "                continue\n",
        "\n",
        "            if cols[0].startswith(\"#\"):\n",
        "                continue\n",
        "\n",
        "            idd, tok, pos, head, lab = int(cols[0]), cols[1], cols[4], int(cols[6]), cols[7]\n",
        "            toks.append((idd, tok, pos, head, lab))\n",
        "        \n",
        "        print (\"UAS: %.3f, LAS:%.3f\" % (totals[0]/totals[2], totals[1]/totals[2]))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ax1VrekKjKcy"
      },
      "source": [
        "### Train and evaluate the model\n",
        "\n",
        "- NOTICE: Because you are not implementing the model or the training process, You will **NOT** be graded based on the performance of the model!\n",
        "\n",
        "- You are only graded based on the correctness of each of the implemented functions.\n",
        "\n",
        "- If all the required functions are implemented correctly, you should expect a UAS in a range of [0.64, 0.67], a LAS in a range of [0.56, 0.59] without changing the parameters of the neural model or the whole training process."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9PweOgvvjKc0",
        "outputId": "13181c69-f852-42c7-a431-ca673c9387c4",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        }
      },
      "source": [
        "embeddingsFile = \"glove.6B.50d.txt\"\n",
        "trainFile = \"train.projective.short.conll\"\n",
        "devFile = \"dev.projective.conll\"\n",
        "\n",
        "embeddings, vocab=load_embeddings(embeddingsFile)\n",
        "pos_tag_vocab=get_pos_tag_vocab(trainFile)\n",
        "word_feats, pos_feats, labels = get_oracles(trainFile, vocab, pos_tag_vocab)\n",
        "\n",
        "label_vocab, reverse_labels=get_label_vocab(labels)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "word_embedding_dim: 50, vocab size: 400004\n",
            "projective trees: 425\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lFN4U_1ojKc5",
        "outputId": "7043179f-8054-4bba-dad5-844c40c208fa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 336
        }
      },
      "source": [
        "print(\"train\")\n",
        "model = train(word_feats, pos_feats, labels, embeddings, vocab, pos_tag_vocab, label_vocab)\n",
        "print(\"evaluate\")\n",
        "evaluate(devFile, model, vocab, pos_tag_vocab, reverse_labels)\n",
        "print(\"test\")\n",
        "test(model, vocab, pos_tag_vocab, reverse_labels)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "train\n",
            "loss:  684.2674526572227\n",
            "loss:  391.0914507955313\n",
            "loss:  322.6748860627413\n",
            "loss:  285.38710452616215\n",
            "loss:  263.61934116482735\n",
            "loss:  242.33986954391003\n",
            "loss:  227.16836595535278\n",
            "loss:  211.945775821805\n",
            "loss:  199.81846357882023\n",
            "loss:  191.12096133828163\n",
            "evaluate\n",
            "UAS: 0.656, LAS:0.580\n",
            "test\n",
            "(1 I) -> (2 bought) nsubj\n",
            "(2 bought) -> (0 <ROOT>) root\n",
            "(3 a) -> (4 book) det\n",
            "(4 book) -> (2 bought) obl\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zSJqNCZPPZ6E"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}