3. Distributed Word Embeddings.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "HW_3.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/asliakalin/ML/blob/master/Distributed_Word_Embeddings.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2y5cwPLm6Lyw",
        "colab_type": "text"
      },
      "source": [
        "# Homework 3: Word Embeddings\n",
        "In this homework, we will try to approximate a Skip-gram word embedding via positive pointwise mutual information (PPMI) and truncated singular value decomposition (SVD). "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EMnCOKC26Gzj",
        "colab_type": "text"
      },
      "source": [
        "## The setup\n",
        "Let's import the required libraries and load the data for preparing our word vectors. We are going to load a list of movie plot summaries (http://www.cs.cmu.edu/~ark/personas/) and use that as our corpus. You do not need to modify them."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nRKoyqtb0QL_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# This code gets the data file from github and imports them into Colab\n",
        "%%capture\n",
        "!wget https://raw.githubusercontent.com/dbamman/nlp20/master/HW_3/plot_summaries_tokenized.csv"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_yWaVJn30NBk",
        "colab_type": "code",
        "outputId": "e9dc9bd8-f808-4b05-b571-0c34f3e6d747",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 72
        }
      },
      "source": [
        "import numpy as np\n",
        "import pandas as pd\n",
        "from string import punctuation\n",
        "from collections import Counter, defaultdict\n",
        "from math import log2\n",
        "from scipy.sparse import csc_matrix\n",
        "from scipy.sparse.linalg import svds\n",
        "\n",
        "def load_data():\n",
        "    \"\"\"\n",
        "    Loads the data and returns tokenized summaries.\n",
        "    \n",
        "    :return summaries_tokenized: a list that contains tokenized summaries text\n",
        "    \"\"\"\n",
        "    df = pd.read_csv(\"plot_summaries_tokenized.csv\")\n",
        "    summaries_tokenized = list(df['SUMMARY'].apply(lambda text: text.split()))\n",
        "    return summaries_tokenized\n",
        "\n",
        "summaries = load_data()\n",
        "num_summaries = len(summaries)\n",
        "print(\"There are {} summaries.\".format(num_summaries))\n",
        "print(\"Example tokenized summary:\", summaries[0])"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "There are 42303 summaries.\n",
            "Example tokenized summary: ['Shlykov', 'a', 'hardworking', 'taxi', 'driver', 'and', 'Lyosha', 'a', 'saxophonist', 'develop', 'a', 'bizarre', 'lovehate', 'relationship', 'and', 'despite', 'their', 'prejudices', 'realize', 'they', 'arent', 'so', 'different', 'after', 'all']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ikv9DyqR7xoG",
        "colab_type": "text"
      },
      "source": [
        "We have ~42000 summaries containing ~13000000 words. We will now proceed by creating a vocabulary and will limit its size to something computationally feasible. You may find python's collections.Counter function useful. You may not import any additional libraries."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jWP4hmGG7--v",
        "colab_type": "text"
      },
      "source": [
        "# 1. Create Vocabulary\n",
        "We will start from creating our vocabulary. Vocabulary contains unigrams and their counts."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ksw96WHvEoJx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "###################\n",
        "# Do not modify\n",
        "###################\n",
        "min_count = (1 / 100) * len(summaries)\n",
        "max_count = (1 / 10) * len(summaries)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Sum1rnZN54-V",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def create_vocabulary(tokenized_documents, min_count, max_count):\n",
        "    \"\"\"\n",
        "    This function takes in tokenized documents and returns a\n",
        "    vocabulary and word <-> index lookup dictionary of some frequently appearing words.\n",
        "    \n",
        "    :param tokenized_documents: a list of tokenized strings\n",
        "    :param min_count: minimum unigram count\n",
        "    :param max_count: maximum unigram count\n",
        "    :return vocab: a Counter where vocab[word] = count of word's occurences in all the documents\n",
        "    :return word2idx: a word -> index lookup Dictionary for words in vocab.\n",
        "    :return idx2word: a index -> word lookup Dictionary for words in vocab.\n",
        "    \"\"\"\n",
        "    # 1a. Compute unigram counts. A unigram is a single word, e.g. foo\n",
        "    vocab = Counter()\n",
        "    ##################################\n",
        "    # Your code here\n",
        "    for doc in tokenized_documents:\n",
        "      for w in doc:\n",
        "        vocab[w] += 1\n",
        "    #print(vocab)\n",
        "    ##################################\n",
        "    # 1b. Remove unigrams that has #(unigram) < min_count or #(unigram) > max_count\n",
        "    # to eliminate unigrams occurring very frequently or infrequently. \n",
        "    # This will limit its size to something computationally feasible.\n",
        "    print('%d vocabs before' % len(vocab))\n",
        "    ##################################\n",
        "    # Your code here\n",
        "    erase = []\n",
        "    for el in vocab:\n",
        "      #print(el)\n",
        "      if vocab[el] > max_count or vocab[el] < min_count:\n",
        "        erase.append(el)\n",
        "    \n",
        "    for item in erase:\n",
        "      #print(item, vocab[item])\n",
        "      del vocab[item]\n",
        "\n",
        "    ##################################\n",
        "    print('%d vocabs after' % len(vocab))\n",
        "          \n",
        "    # 1c. Build word <-> index lookup for words in vocab.\n",
        "    word2idx, idx2word = {}, {}\n",
        "    ##################################\n",
        "    # Your code here\n",
        "    ids = np.arange(len(vocab.keys()))\n",
        "    words = list(vocab.keys())\n",
        "    for i in range(len(ids)):\n",
        "      word2idx[words[i]] = ids[i]\n",
        "      idx2word[ids[i]] = words[i]\n",
        "\n",
        "    ##################################\n",
        "    return vocab, word2idx, idx2word"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "71G0q8l_51CH",
        "colab_type": "code",
        "outputId": "f090d203-665d-4571-abd3-bfc5c36ac085",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        }
      },
      "source": [
        "vocab, word2idx, idx2word = create_vocabulary(summaries, min_count, max_count)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "214147 vocabs before\n",
            "2750 vocabs after\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JtzGp1vi_Poi",
        "colab_type": "code",
        "outputId": "89fab42f-6d9b-4884-81d8-26b70f560191",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "word2idx[\"eye\"]"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "356"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 88
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "w9BYo-eU_iIQ",
        "colab_type": "code",
        "outputId": "0af3f00e-5923-4cb6-d73d-887ff5186071",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "idx2word[356]"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'eye'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 89
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "W7NAbmvO75v7",
        "colab_type": "code",
        "outputId": "6c6fb4d1-b585-408c-c597-4b923c4259db",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "len(vocab)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2750"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 90
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0NwfhahT_tRd",
        "colab_type": "text"
      },
      "source": [
        "# 2. Build Term-Context Matrix"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HQ-tvqGE1ykI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "###################\n",
        "# Do not modify\n",
        "###################\n",
        "window_size = 3"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WOmvgcNPHKng",
        "colab_type": "code",
        "outputId": "9ef36462-fa7e-4a26-f52c-091a7e12873f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        }
      },
      "source": [
        "a = [[\"a\", \"b\", \"c\"], [\"d\", \"e\", \"f\"]]\n",
        "pad = [None] * 3\n",
        "for item in a:\n",
        "  padded = pad + item + pad\n",
        "  print(padded)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[None, None, None, 'a', 'b', 'c', None, None, None]\n",
            "[None, None, None, 'd', 'e', 'f', None, None, None]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NQvXB-MZ_VqD",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def build_term_context_matrix(tokenized_documents, vocab, window_size):\n",
        "    \"\"\"\n",
        "    This function returns a `word_pair_count` Counter with each \n",
        "    word_pair_count[(w, c)] = number of times the word `c` occurs in the context of word `w`. \n",
        "    (where `w`, `c` belong to the vocab)\n",
        "    To make it efficient, instead of building the sparse term-context matrix, \n",
        "    we will build 3 separate Counters: \n",
        "        word_pair_count, \n",
        "        w_count, \n",
        "        c_count\n",
        "    You may find python's Counter useful here\n",
        "\n",
        "    :param tokenized_documents: a list of tokenized strings\n",
        "    :param vocab: vocabulary Counter\n",
        "    :param window_size: context window size\n",
        "    :return word_pair_count: a Counter where word_pair_count[(w, c)] = count of c's occurences in w's context window, i.e. #(w, c)\n",
        "    :return w_count: a Counter where w_count[w] = the number of times w occured in the documents, i.e. #(w)\n",
        "    :return c_count: a Counter where c_count[c] = the number of times c occured in the documents, i.e. #(c)\n",
        "    \"\"\"\n",
        "    word_pair_count = Counter()  \n",
        "    w_count = Counter()\n",
        "    c_count = Counter()\n",
        "    ##################################\n",
        "    # Your code here\n",
        "\n",
        "    pad = [None] * window_size\n",
        "    for doc in tokenized_documents:\n",
        "      padded = pad + doc + pad\n",
        "      for i in range(window_size, window_size+len(doc)):\n",
        "        w = padded[i]\n",
        "        if w in vocab:\n",
        "          context = padded[i-window_size:i] + padded[i+1:i+window_size+1]\n",
        "          for c in context:\n",
        "            if (c in vocab):\n",
        "              c_count[c] += 1\n",
        "              w_count[w] += 1\n",
        "              word_pair_count[(w,c)] += 1\n",
        "\n",
        "    ##################################\n",
        "    return word_pair_count, w_count, c_count"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gBxi0t1y2jQ_",
        "colab_type": "code",
        "outputId": "c5bcfff4-c47d-4536-b706-af118342554b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "word_pair_count, w_count, c_count = build_term_context_matrix(summaries, vocab, window_size)\n",
        "print(\"There are {} word-context pairs\".format(len(word_pair_count)))\n",
        "\n",
        "# The number of w_count and c_count should match your number of vocab\n",
        "assert len(w_count) == len(vocab)\n",
        "assert len(c_count) == len(vocab)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "There are 1917545 word-context pairs\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EFPQ1awg7wBK",
        "colab_type": "code",
        "outputId": "63933ce9-bd78-49f0-e4bf-6c7ea57702d6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "len(vocab)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2750"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 95
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vSR6cRvCObxs",
        "colab_type": "code",
        "outputId": "b890c062-bd28-41c1-b3c6-64e7047572dc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "word_pair_count[(\"apple\", \"orange\")] == word_pair_count[(\"orange\", \"apple\")]"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 112
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Um3tRY4yOqPj",
        "colab_type": "code",
        "outputId": "4ba99c6d-e546-49e6-e09d-8861954de33a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "w_count[\"doctor\"] == c_count[\"doctor\"]"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 114
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xeaZoasi3m5r",
        "colab_type": "text"
      },
      "source": [
        "# 3. Build Positive Pointwise Mutual Information (PPMI) Matrix\n",
        "In this part, you will build a PPMI matrix using Scipy's Compressed Sparse Column matrix to save storage space. (https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html)\n",
        "\n",
        "Sparse matrix is a matrix which contains very few non-zero elements. When a sparse matrix is represented with a 2-dimensional array, we waste a lot of space to represent that matrix. In NLP application, it's quite common to use sparse matrix since the size of vocabulary is usually very large. \n",
        "\n",
        "Below is an example of how to build a sparse matrix where `data`, `row` and `col` satisfy the relationship `M[row[k], col[k]] = data[k]`.\n",
        "\n",
        "```python\n",
        ">>> row = np.array([0, 2, 2, 0, 1, 2])\n",
        ">>> col = np.array([0, 0, 1, 2, 2, 2])\n",
        ">>> data = np.array([1, 2, 3, 4, 5, 6])\n",
        ">>> M = csc_matrix((data, (row, col)))\n",
        ">>> M.toarray()\n",
        "array([[1, 0, 4],\n",
        "       [0, 0, 5],\n",
        "       [2, 3, 6]])\n",
        "```\n",
        "\n",
        "Recall that\n",
        "$$\n",
        "\\begin{gather*}\n",
        "  \\text{PMI}(w, c) = \\log_2 \\frac{P(w, c)}{P(w)P(c)} \\\\\n",
        "  \\text{PPMI}(w, c) = \\max(0, \\text{PMI}(w, c))\n",
        "\\end{gather*}\n",
        "$$\n",
        "You should use `log2` function from the math package that is alreadly imported for you."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FIYharDm38G1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def build_PPMI_matrix(word_pair_count, w_count, c_count, word2idx):\n",
        "    \"\"\"\n",
        "    This function returns a PPMI matrix represented by a csc sparse matrix.\n",
        "\n",
        "    :params word_pair_count: a Counter where word_pair_count[(w, c)] = count of c's occurences in w's context window\n",
        "    :params w_count: a Counter where w_count[w] = the number of times w occured in the documents\n",
        "    :params c_count: a Counter where c_count[c] = the number of times c occured in the documents\n",
        "    :params word2idx: a word -> index lookup Dictionary for words in vocab\n",
        "    :return PPMI: PPMI csc sparse matrix\n",
        "    \"\"\"\n",
        "    data, rows, cols = [], [], []\n",
        "    total_occurences = sum(word_pair_count.values())\n",
        "    for (w, c), n in word_pair_count.items():\n",
        "      ##################################\n",
        "      # Your code here\n",
        "      # data, row_ind and col_ind satisfy the relationship a[row_ind[k], col_ind[k]] = data[k].\n",
        "\n",
        "      pwc = n/total_occurences\n",
        "      pw = w_count[w]/total_occurences\n",
        "      pc = c_count[c]/total_occurences\n",
        "\n",
        "      ppmi_val = max(0, log2(pwc/(pw*pc)))\n",
        "\n",
        "      data.append(ppmi_val)\n",
        "      rows.append(word2idx[w])\n",
        "      cols.append(word2idx[c])\n",
        "\n",
        "      ##################################\n",
        "\n",
        "    PPMI = csc_matrix((data, (rows, cols)))\n",
        "    return PPMI"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ADuP5FPV8-XQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "PPMI = build_PPMI_matrix(word_pair_count, w_count, c_count, word2idx)\n",
        "\n",
        "# The shape of PPMI matrix should match your number of vocab\n",
        "assert PPMI.shape == (len(vocab), len(vocab))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oxBYdP3p7ptD",
        "colab_type": "code",
        "outputId": "ca0ce4bd-01d1-48a9-8ed8-e122593c983e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "PPMI.shape"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(2750, 2750)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 98
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VBZe79ReO0pG",
        "colab_type": "code",
        "outputId": "7f522d9d-1ca4-400f-e448-657206a1b947",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "PPMI[15, 13] == PPMI[13, 15]"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 117
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dLUHCDzN9PGF",
        "colab_type": "text"
      },
      "source": [
        "# 4. Truncated SVD\n",
        "In this part, we will obtain a dense low-dimensional vectors via truncated (rank-k) SVD. You should use `svds` function from Sicpy that is already imported for you to obtain the SVD factorization.\n",
        "(https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.svds.html)\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZEh5rynC9-UR",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "###################\n",
        "# Do not modify\n",
        "###################\n",
        "rank = 20"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BLtCNz5Z9U8c",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\"\"\"\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "from string import punctuation\n",
        "from collections import Counter, defaultdict\n",
        "from math import log2\n",
        "from scipy.sparse import csc_matrix\n",
        "from scipy.sparse.linalg import svds\n",
        "\"\"\"\n",
        "def get_embeddings(PPMI, rank):\n",
        "    \"\"\"\n",
        "    Reutrns the left singular vectors as word embeddings via truncated SVD\n",
        "\n",
        "    :params PPMI: PPMI csc sparse matrix\n",
        "    :params rank: number of singular values and vectors to compute\n",
        "    :return u: left sigular vectors from sprase SVD\n",
        "    :return s: the singular values from sparse SVD\n",
        "    \"\"\"\n",
        "    ##################################\n",
        "    # Your code here\n",
        "    u, s, vt = svds(PPMI, rank)\n",
        "    # PPMI shape MxN\n",
        "    # u has shape mxk: Unitary matrix having left singular vectors as columns. \n",
        "    # s : The singular values. shape (k,)\n",
        "    # vt has shape kxN: Unitary matrix having right singular vectors as rows.\n",
        "    ##################################\n",
        "    return u, s"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lmjoP5KF91O0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "embeddings, _ = get_embeddings(PPMI, rank)\n",
        "embeddings /= np.linalg.norm(embeddings, axis=1, keepdims=True)  # Normalize embeddings matrix\n",
        "\n",
        "# The shape of the embeddings matrix should be (# vocab, rank)\n",
        "assert embeddings.shape == (len(vocab), rank)\n",
        "\n",
        "# Make sure embeddings is normalized\n",
        "assert True == np.isclose(np.linalg.norm(embeddings[0]), 1)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OQ_Te9917TVk",
        "colab_type": "code",
        "outputId": "9eaab165-bacd-4536-dde7-1d833c2c1b6c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "len(embeddings)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2750"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 102
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bJMXc0zD7kBb",
        "colab_type": "code",
        "outputId": "78f1c300-5ab9-434b-ab96-578653b2df3a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "len(vocab)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2750"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 103
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9o2i7wwT7lwa",
        "colab_type": "code",
        "outputId": "c7c41af5-77df-43d1-fcb2-20e759ba5d8e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "a = [5,10,2,3,4,20,1,7,23,17]\n",
        "k = 7\n",
        "best = np.argpartition(a, -k)[-k:]\n",
        "best"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([4, 0, 5, 1, 7, 8, 9])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 104
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rQUUfS0N-Lyc",
        "colab_type": "text"
      },
      "source": [
        "# 5. Evaluate Word Embeddings via Cosine Similarity\n",
        "\n",
        "Using cosine similarity as a measure of distance [§6.4 Jurafsky & Martin](https://web.stanford.edu/~jurafsky/slp3/6.pdf), we will now find the closest words to a certain word. We define cosine similarity as, $$cosine(\\overrightarrow{v},\\overrightarrow{w}) = \\frac{\\overrightarrow{v} \\cdot \\overrightarrow{w}}{\\vert v \\vert \\vert w \\vert}$$\n",
        "\n",
        "Please complete the function below that calculates the 'K' closest words from the vocabulary. You may not use any additional libraries."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "D9Zf_us2AFkx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "###################\n",
        "# Do not modify\n",
        "###################\n",
        "num_neighbors = 5"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "f_l55j98-NvY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\"\"\"\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "from string import punctuation\n",
        "from collections import Counter, defaultdict\n",
        "from math import log2\n",
        "from scipy.sparse import csc_matrix\n",
        "from scipy.sparse.linalg import svds\n",
        "\"\"\"\n",
        "def cosine_distances(matrix, vector):\n",
        "    \"\"\"\n",
        "    The function takes in a matrix and a vector (both normalized) \n",
        "    and returns the cosine distances for this vector against all others.\n",
        "    The pretrained embeddings are normalized.\n",
        "\n",
        "    :params matrix: word embeddings matrix\n",
        "    :params vector: word vector for a particular word\n",
        "    :return distances: a cosine distances vector\n",
        "    \"\"\"\n",
        "    ##################################\n",
        "    # Your code here\n",
        "    distances = []\n",
        "    for i in range(matrix.shape[0]):\n",
        "      word_vec = matrix[i]\n",
        "      #since both vectors are normalized, no need to divide by vector lenght\n",
        "      similarity = np.dot(word_vec, vector)\n",
        "      #add the distance of vector wrt to word in i'th index to the i'th index of distances vector\n",
        "      distances.append(similarity)\n",
        "\n",
        "    ##################################\n",
        "    return  distances\n",
        "\n",
        "\n",
        "def nearest_neighbors(embeddings, word, k, word2idx, idx2word):\n",
        "    \"\"\"\n",
        "    For each query word, this function returns the k closest words from the vocabulary.\n",
        "\n",
        "    :params embeddings: word embedding matrix\n",
        "    :params word: query word\n",
        "    :params k: number of cloest words to return\n",
        "    :params word2idx: a word -> index lookup dictionary\n",
        "    :params idx2word: a index -> word lookup dictionary\n",
        "    :return nearest_neighbors: a list of cloest words\n",
        "    \"\"\"\n",
        "    vector = embeddings[word2idx[word]]\n",
        "    distances = cosine_distances(embeddings, vector)\n",
        "    nearest_neighbors = []\n",
        "    ##################################\n",
        "    # Your code here\n",
        "    # it'll be most similar to itself \n",
        "    # but we should ignore that and get the next best k neighbors\n",
        "    k += 1\n",
        "    nearest_indices = np.argpartition(distances, -k)[-k:]\n",
        "    for index in nearest_indices:\n",
        "      if idx2word[index] != word:\n",
        "        nearest_neighbors.append(idx2word[index])\n",
        "\n",
        "    ##################################\n",
        "    \n",
        "    return nearest_neighbors"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FJjPuVPe_oGq",
        "colab_type": "code",
        "outputId": "fc775859-576d-4b53-d241-3a9a0c6d9707",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        }
      },
      "source": [
        "query_words = [\"doctor\", \"zombie\", \"robot\", \"eat\", \"bus\"]\n",
        "for word in query_words:\n",
        "    print(word, nearest_neighbors(embeddings, word, num_neighbors, word2idx, idx2word))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "doctor ['Anna', 'Christine', 'doctors', 'priest', 'Sophie']\n",
            "zombie ['vampire', 'infected', 'vampires', 'creatures', 'zombies']\n",
            "robot ['demon', 'machine', 'weapon', 'alien', 'creature']\n",
            "eat ['sit', 'wear', 'sleep', 'throw', 'stand']\n",
            "bus ['river', 'airport', 'truck', 'boat', 'road']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KfxaNuBjAiiY",
        "colab_type": "text"
      },
      "source": [
        "# 6. Evaluate Word Embeddings via Analogous Tasks\n",
        "\n",
        "The embedding space is known to capture the semantic context of words. An example of it is $\\overrightarrow{woman} - \\overrightarrow{man} \\simeq \\overrightarrow{queen} - \\overrightarrow{king}$. Use the `cosine_distances()` function you wrote above to find such relations."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YZQCzP-FCRb5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def relation(embeddings, query_words, word2idx, idx2word):\n",
        "    \"\"\"\n",
        "    Takes in 3 words and returns the closest word (in terms of cosine similarity)\n",
        "    to the normalized algebraic addition of the three vectors.\n",
        "    The parameters follow this order : word_vec1 - word_vec2 ~ closest - word_vec3\n",
        "\n",
        "    :params embeddings: word embedding matrix\n",
        "    :params query_words: a list of query words in the following order: [word1, word2, word3]\n",
        "    :params word2idx: a word -> index lookup dictionary\n",
        "    :params idx2word: a index -> word lookup dictionary\n",
        "    :return closet_word: the closest word for the relation\n",
        "    \"\"\"\n",
        "    word1, word2, word3 = query_words\n",
        "    if all(word in vocab for word in query_words):\n",
        "      ##################################\n",
        "      # Your code here\n",
        "\n",
        "      # get indices of each word\n",
        "      one = word2idx[word1]\n",
        "      two = word2idx[word2]\n",
        "      three = word2idx[word3]\n",
        "\n",
        "\n",
        "      #get vector representation of each word\n",
        "      v_1 = embeddings[one]\n",
        "      v_2 = embeddings[two]\n",
        "      v_3 = embeddings[three]\n",
        "\n",
        "      #the vector closest to the target:\n",
        "      target = v_1 - v_2 + v_3\n",
        "\n",
        "      # normalize\n",
        "      normalized = target/np.linalg.norm(target)\n",
        "\n",
        "      # get distances with respect to the target\n",
        "      dist = cosine_distances(embeddings, normalized)\n",
        "\n",
        "      #get index of highest distance/closest \n",
        "      wanted = np.argpartition(dist, -2)[-2:]\n",
        "\n",
        "      # get the word from the index\n",
        "      for w in wanted:\n",
        "        if idx2word[w]!=word3:\n",
        "          closest_word = idx2word[w]\n",
        "\n",
        "      ##################################\n",
        "      \n",
        "      return closest_word\n",
        "    else:\n",
        "      missing = [w for w in query_words if w not in vocab]\n",
        "      raise Exception(\"missing {} from vocabulary\".format(\", \".join(missing)))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lF3mtHMjHue-",
        "colab_type": "code",
        "outputId": "1d64b3c4-8b3f-4cd7-aaf6-a1b0b13fe4b7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        }
      },
      "source": [
        "queries = [[\"doctor\", \"nurse\", \"king\"], [\"robot\", \"weapon\", \"bus\"], [\"sing\", \"song\", \"justice\"], [\"elderly\", \"kids\", \"teenager\"], [\"soldier\", \"wound\", \"telephone\"]]\n",
        "for query in queries:\n",
        "  closet_word = relation(embeddings, query, word2idx, idx2word)\n",
        "  print(\"{} - {} ~= {} - {}\".format(query[0], query[1], closet_word, query[2]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "doctor - nurse ~= Emperor - king\n",
            "robot - weapon ~= road - bus\n",
            "sing - song ~= defend - justice\n",
            "elderly - kids ~= widow - teenager\n",
            "soldier - wound ~= agent - telephone\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pSW2ME84N1Ng",
        "colab_type": "code",
        "outputId": "cf26397f-6f7d-43b9-8996-01956a6e7ccc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "queries = [[\"doctor\", \"king\", \"king\"]]\n",
        "for query in queries:\n",
        "  closet_word = relation(embeddings, query, word2idx, idx2word)\n",
        "  print(\"{} - {} ~= {} - {}\".format(query[0], query[1], closet_word, query[2]))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "doctor - king ~= doctor - king\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fGr7Oa63KcIg",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}