exercise_11_top_acc.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyMy3jVb45YceNTLzPkqbyHt",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/TurkuNLP/intro-to-nlp/blob/master/exercise_11_top_acc.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Exercise 11: Top-K accuracy\n",
        "\n",
        "In the lecture, we learned to align embedding spaces, which allowed us to \"compute\" word translations. We marveled at how well this worked, but did not\n",
        "really evaluate this properly, even though we do have a nice test set.\n",
        "\n",
        "In the exercise, your task will be to evaluate the method using the simple \"top-k accuracy\" metric. This is a simple metric, which measures whether the correct target is among the first K nearest neighbors. In other words for the pair of source-target words $w_{fin}, w_{eng}$ we consider the transfer successful, if $w_{eng}$ is among the K nearest neighbors of the embedding we obtain by transforming $w_{ fin}$ with the matrix $M$. Top K accuracy then is the proportion of successfully transferred pairs, out of all pairs, as a percentage.\n",
        "\n",
        "This can be achieved by a simple modification of the lecture code below."
      ],
      "metadata": {
        "id": "MxqCYdbBaz5Z"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "c3-FPp5MZjAS"
      },
      "outputs": [],
      "source": [
        "import gensim"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# I found this link in the NLPL repository\n",
        "# It refers to English model trained on the Gigaword corpus of news\n",
        "#!wget http://vectors.nlpl.eu/repository/20/12.zip\n",
        "# And this is Finnish, trained on a web crawl data we created back then: https://lindat.mff.cuni.cz/repository/xmlui/handle/11234/1-1989\n",
        "#!wget http://vectors.nlpl.eu/repository/20/42.zip\n",
        "\n",
        "## Try these if the download above is too slow, I mirrored these:\n",
        "!wget http://dl.turkunlp.org/TKO_7095_2023/12.zip\n",
        "!wget http://dl.turkunlp.org/TKO_7095_2023/42.zip\n"
      ],
      "metadata": {
        "id": "QRbTPYZGZuiJ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Somewhat awkwardly, these are numbered files and both\n",
        "# .zip files contain \"model.bin\"\n",
        "# Let's unzip and rename\n",
        "# -o means \"do not ask, overwrite by default\"\n",
        "!unzip -o 12.zip\n",
        "!mv model.bin en.bin\n",
        "!unzip -o 42.zip\n",
        "!mv model.bin fi.bin\n"
      ],
      "metadata": {
        "id": "AiV_3crkzBtI"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "\n",
        "*   Now we can load the embeddings\n",
        "*   These are huge, but they are sorted by frequency, so we can easily limit ourselves to the top 100,000 words, which will be plenty enough for us\n",
        "*   This is maybe good to note, now we enter the territory of NLP models which count in the gigabytes in size\n",
        "\n"
      ],
      "metadata": {
        "id": "lL1rXODZOCYi"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# This is how you load the trained embeddings\n",
        "# check the documentation\n",
        "# w2v embeddings are traditionlly distributed in one of two formats: a text form, and a binary form\n",
        "# The embeddings we downloaded above are in the binary form, so we need to indicate that when loading\n",
        "\n",
        "from gensim.models import KeyedVectors\n",
        "\n",
        "wv_emb_en=KeyedVectors.load_word2vec_format(\"en.bin\", limit=100000, binary=True)\n",
        "wv_emb_fi=KeyedVectors.load_word2vec_format(\"fi.bin\", limit=100000, binary=True)"
      ],
      "metadata": {
        "id": "4DbFt1VOaDCu"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "`KeyedVectors` documentation is here: https://radimrehurek.com/gensim/models/keyedvectors.html"
      ],
      "metadata": {
        "id": "mEsD37OxeP2C"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Cross-lingual transfer\n",
        "\n",
        "* Among the most impressive demonstrations of word embeddings\n",
        "* Given a list of word pairs between two languages (source and target), one can induce a mapping matrix $M$ which performs a linear transformation of the source language embeddings onto the target language embeddings\n",
        "* This basically \"aligns\" the source language embedding space onto the target language embedding space\n",
        "\n",
        "This is well worth testing! Let's try!"
      ],
      "metadata": {
        "id": "WlcN0CJif1-0"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Bilingual dictionaries\n",
        "\n",
        "* There are many sources, for example this one:\n",
        "* https://github.com/codogogo/xling-eval\n",
        "* The associated paper is here: https://aclanthology.org/P19-1070/"
      ],
      "metadata": {
        "id": "14hiMqfUGMZ4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Grab the data\n",
        "!wget https://raw.githubusercontent.com/codogogo/xling-eval/master/bli_datasets/en-fi/yacle.test.freq.2k.en-fi.tsv\n",
        "!wget https://raw.githubusercontent.com/codogogo/xling-eval/master/bli_datasets/en-fi/yacle.train.freq.5k.en-fi.tsv\n"
      ],
      "metadata": {
        "id": "FPzz9inbqY23"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "!cat yacle.test.freq.2k.en-fi.tsv | head -n 10"
      ],
      "metadata": {
        "id": "PHjpFdK5Gqqw"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "pairs_train=[] #These will be pairs of (source,target) i.e. (Finnish, English) words used to induce the matrix M\n",
        "pairs_test=[]  #same but for testing, so we should make sure there is absolutely no overlap between the train and test data\n",
        "               #let's do it so that not one word in the test is is seen in any capacity in the training data\n",
        "\n",
        "import csv\n",
        "\n",
        "def get_vectors(fname):\n",
        "    \"\"\"\n",
        "    Read the pairs from the file `fname`\n",
        "    \"\"\"\n",
        "    pairs=[]\n",
        "    with open(fname) as f:\n",
        "        r = csv.reader(f,delimiter=\"\\t\") #the file is a .tsv i.e. tab-separated-values\n",
        "        for en_word,fi_word in r:\n",
        "            #I will reverse the order here, go from Finnish as the source, to English as the target\n",
        "            #That way it will be easier to check how this works using English as the target, which we all understand\n",
        "            pairs.append((fi_word,en_word))\n",
        "        return pairs\n",
        "\n",
        "train_data=get_vectors(\"yacle.train.freq.5k.en-fi.tsv\")\n",
        "test_data=get_vectors(\"yacle.test.freq.2k.en-fi.tsv\")\n",
        "print(train_data[:10])\n",
        "print(len(train_data))\n",
        "print(test_data[:10])\n",
        "print(len(test_data))\n",
        "\n"
      ],
      "metadata": {
        "id": "mjUoV2lBpbJG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Get the embeddings\n",
        "\n",
        "* Now we have the word pairs\n",
        "* We need the embeddings, so we can build our S and T matrices\n",
        "* Not all words will be in our W2V embeddings\n",
        "* Plus, we want to be 100% sure there is absolutely no overlap between the training and test data\n",
        "* This means not one word seen in the training data will be in the test data\n",
        "* The general approach will be to gather the vectors into a list, and then vstack (vertical stack) these to get a 2D array, i.e. a matrix"
      ],
      "metadata": {
        "id": "ikK7jb1hHUGF"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy\n",
        "\n",
        "def build_arrays(pairs,emb1,emb2,avoid=set()):\n",
        "    \"\"\"\n",
        "    `pairs`: pairs of (fi,en) words\n",
        "    `emb1`: source side (here Finnish) embeddings\n",
        "    `emb2`: target side (here English) embeddings\n",
        "    `avoid`: a set of words to avoid/ignore (will be used when building test data, to avoid train data)\n",
        "    \"\"\"\n",
        "    vecs1,vecs2,filtered_pairs=[],[],[]  #vectors for source words, vectors for target words, and the word pairs themselves, i.e. three same-length lists\n",
        "    for w1,w2 in pairs: #Go over all pairs that we got\n",
        "        # check if both vectors are available, and none of the words is to be avoided\n",
        "        if w1 in emb1 and w2 in emb2 and w1 not in avoid and w2 not in avoid:\n",
        "            #passed!\n",
        "            vecs1.append(emb1[w1]) #source-side embedding, the KeyedVectors object can be queried as if it was a dictionary, returns the embedding as 1-dim array\n",
        "            vecs2.append(emb2[w2]) #target-side embeddings\n",
        "            filtered_pairs.append((w1,w2)) #remember the pair\n",
        "    #Now we vstack() which turns the lists of embeddings into 2-dim array\n",
        "    return numpy.vstack(vecs1),numpy.vstack(vecs2),filtered_pairs\n",
        "\n",
        "# Gather the train data first\n",
        "array_train_fi,array_train_en,pairs_train=build_arrays(train_data,wv_emb_fi,wv_emb_en)\n",
        "# Now build the set of all words seen in training, so we can avoid them when building the test set. Note that \"|\" is set union operator\n",
        "everything_in_train=set(s for s,t in pairs_train)|set(t for s,t in pairs_train)\n",
        "# Test data next, avoiding the words from the training data:\n",
        "array_test_fi,array_test_en,pairs_test=build_arrays(test_data,wv_emb_fi,wv_emb_en,avoid=everything_in_train)"
      ],
      "metadata": {
        "id": "L6zMmPGDz0pV"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Let's be super-sure there absolutely is no overlap of any kind!\n",
        "print(\"Overlap between train pairs and test pairs:\",len(set(pairs_train) & set(pairs_test))) # & is set intersection operator, intersection between train and test should be empty\n",
        "src_train=set(src_w for src_w,tgt_w in pairs_train) #train source words\n",
        "tgt_train=set(tgt_w for src_w,tgt_w in pairs_train) #train target words\n",
        "src_test=set(src_w for src_w,tgt_w in pairs_test)   #test source words\n",
        "tgt_test=set(tgt_w for src_w,tgt_w in pairs_test)   #test target words\n",
        "print(\"Overlap between train fi words and test fi words:\",len(src_train & src_test))\n",
        "print(\"Overlap between train en words and test en words:\",len(tgt_train & tgt_test))"
      ],
      "metadata": {
        "id": "ntsAk7U3-SoN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Mapping matrix\n",
        "* Next we need to induce the transformation matrix\n",
        "* I.e. implement the least-squares methods from the lecture\n",
        "* Surely GPT4 can write this for us:"
      ],
      "metadata": {
        "id": "DfeAUHJQJDu9"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# This code was written by GPT4, but in a bit of a twisted form, so I modified it\n",
        "# to better correspond to the formulae in the lecture\n",
        "\n",
        "def learn_transformation_matrix(source, target):\n",
        "    # Compute the pseudo-inverse of the source matrix\n",
        "    source_pseudo_inverse = numpy.linalg.pinv(source) # This implements (S^T S)^-1 S^T  needed in the least-squares formula in the lecture slides\n",
        "    # Compute the transformation matrix M using least squares method\n",
        "    M = numpy.matmul(source_pseudo_inverse,target)  #...and this multiplies by T from right completing the formula in the slides ... two lines(!)\n",
        "    return M\n",
        "\n",
        "# fi -> en matrix\n",
        "M=learn_transformation_matrix(array_train_fi,array_train_en)\n",
        "\n",
        "# Ha ha well that was easy"
      ],
      "metadata": {
        "id": "BW9-9iL11-0K"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "print(\"Source (fi) shape\",array_train_fi.shape)\n",
        "print(\"Target (en) shape\",array_train_en.shape)\n",
        "print(\"M shape\",M.shape)\n"
      ],
      "metadata": {
        "id": "D3wKwHKb2Umo"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# And now we transform the source (Finnish) test embeddings into the English embedding space\n",
        "# using the matrix M\n",
        "test_fi_transformed=numpy.matmul(array_test_fi,M) # This corresponds to SM in the lecture slides, i.e. source transformed by M to the target embedding space\n",
        "print(\"Transformed shape:\",test_fi_transformed.shape)\n",
        "numpy.square(numpy.subtract(test_fi_transformed, array_test_en)).mean() #This is the mean square error of the actual target, and the transformed source, looks small enough :)"
      ],
      "metadata": {
        "id": "BQLYDxra3bvW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "* So now we have the originally Finnish embeddings transformed into the English space\n",
        "* How can we evaluate?\n",
        "\n",
        "1. Go over the test word pairs (fi,en)\n",
        "2. Use the transformed Finnish embedding as a query into the English space\n",
        "3. List top-N English words which appear near this transformed embedding\n",
        "\n",
        "Conceptually, we go: \"Finnish word -> lookup to Finnish vector -> multiply by M to get English vector -> lookup English words nearby\""
      ],
      "metadata": {
        "id": "dFvVBgyuKBcs"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "for i,(w1,w2) in enumerate(pairs_test[:10]):\n",
        "    print(f\"{w1} (in English {w2}):\")\n",
        "    nearest_neighbors=wv_emb_en.similar_by_vector(test_fi_transformed[i]) #lookup the nearest\n",
        "    #nearest_neigbors will be tuples (word,similarity_value)\n",
        "    eng_words=[w for w, score in nearest_neighbors] #just grab the words\n",
        "    print(f\"   \",\", \".join(eng_words)) #...and print then ,-separated\n",
        "    print()\n",
        "\n",
        "# It cannot be stressed enough, that none of the words in the test data were seen\n",
        "# during the induction of the transformation matrix M\n",
        "# \n",
        "# We can observe some direct top-1 hits, and in general we see\n",
        "# the mapping maps the vector very close to the correct place\n",
        "# in my view, this is quite impressive :)"
      ],
      "metadata": {
        "id": "Pnb2qINM0wAN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Put your exercise code here\n",
        "\n",
        "* You can start by copying and repurposing the code above. After all, if you can print the target and the nearest neigbors, you can also count them :)"
      ],
      "metadata": {
        "id": "9lKMCAK6dS3G"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "########## YOUR CODE HERE #############\n",
        "\n",
        "######## evaluate for K=1,5,10,50 for example #######\n",
        "########  below is what I got #########\n",
        "##\n",
        "##Top-1 accurracy is 17.82101167315175%\n",
        "##Top-5 accurracy is 34.007782101167315%\n",
        "##Top-10 accurracy is 42.4124513618677%\n",
        "##Top-50 accurracy is 61.08949416342413%"
      ],
      "metadata": {
        "id": "ITca98IYdKIg"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}