week3_ann_user_representations_submission.ipynb

{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "a424b415-b8ef-47b3-84ee-7c40332e01ef",
        "outputId": "a4f9c3cf-50b7-4b1d-ac93-139e5675ef43"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Collecting faiss-cpu\n",
            "  Downloading faiss_cpu-1.7.2-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (8.6 MB)\n",
            "\u001b[K     |████████████████████████████████| 8.6 MB 10.3 MB/s \n",
            "\u001b[?25hInstalling collected packages: faiss-cpu\n",
            "Successfully installed faiss-cpu-1.7.2\n"
          ]
        }
      ],
      "source": [
        "!pip install faiss-cpu --no-cache"
      ],
      "id": "a424b415-b8ef-47b3-84ee-7c40332e01ef"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "837dcaa9-cc0b-4345-bbee-3a09683decf9"
      },
      "outputs": [],
      "source": [
        "import pickle\n",
        "import faiss\n",
        "import numpy as np\n",
        "from random import shuffle\n",
        "import time\n",
        "import pandas as pd\n",
        "import matplotlib.pyplot as plt"
      ],
      "id": "837dcaa9-cc0b-4345-bbee-3a09683decf9"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "41f1f7cb-9441-4fe1-962e-9e4cb3e3c192"
      },
      "source": [
        "# **Welcome to week 3 project!**\n",
        "\n",
        "Congratulations on making it to week 3! 👏 In the first week of this course, we covered the basics of how to design personalized recommendation systems. We then provided some system design examples for large scale recommenders from corporations like Spotify and YouTube, as well as techniques for candidate generation, specifically the two-tower model being used at Twitter and Pinterest.\n",
        "\n",
        "Last week, we covered details of ML approaches for recommendations: including multi-task recommenders and contextual bandits.\n",
        "\n",
        "In week 3, we covered various techniques for learning user representations.\n",
        "\n",
        "In this week's project, we will touch upon two key aspects related to representations:\n",
        "1. How do we query large amount of vectors in efficient time.\n",
        "2. How can we infer various user representations and see what their impact is on downstream task.\n",
        "\n",
        "Lets begin with Part A, which tells us how we could handle a large number of candidate items or user representations in an efficient manner. \n"
      ],
      "id": "41f1f7cb-9441-4fe1-962e-9e4cb3e3c192"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d0e01328-6834-4b11-85c1-03867e1d4860"
      },
      "source": [
        "# Part A: Approximate nearest neighbor search\n",
        "\n",
        "Often we are interested in finding nearest neighbors in a large space of vectors. To store embeddings for 400 million users and over 100 million items and querying them in real time is a challenging task. This is where approximate nearest neighbor approaches step in to help. Annoy, Faiss, ScaNN are typical libraries that are used for efficient vector similarity search at scale. They implement algorithms that search in sets of vectors of any size, up to ones that possibly do not fit in RAM.\n",
        "\n",
        "In the first part of this week's project, we will simulate embeddings of 1 million items and try to find k-nearest neighbours for an item of interest. We will implement a vanilla search function to fetch the top-k nearest neighbors and estimate the time it takes for us to do so. We will then compare this with FAISS -- Facebook's nearest neighbour search library, and compare the time it takes for us to get nearest neighbours from FAISS versus our own implementation."
      ],
      "id": "d0e01328-6834-4b11-85c1-03867e1d4860"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3fa2b438-be53-4f39-b990-859046a4a560"
      },
      "source": [
        "Lets first generate a simulated dataset of embeddings of 1 million items."
      ],
      "id": "3fa2b438-be53-4f39-b990-859046a4a560"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "8c36fc8b-a032-4b48-bbeb-3bff46624615"
      },
      "outputs": [],
      "source": [
        "d = 64                           # dimension\n",
        "nb = 1000000                     # database size\n",
        "nq = 10000                       # nb of queries\n",
        "np.random.seed(1234)             # make reproducible\n",
        "xb = np.random.random((nb, d)).astype('float32')\n",
        "xq = np.random.random((nq, d)).astype('float32')"
      ],
      "id": "8c36fc8b-a032-4b48-bbeb-3bff46624615"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "142c00a5-f36b-4a5f-9e27-4a3e38b467d7"
      },
      "source": [
        "Now that we have these items, lets take up the goal of finding the top-5 items closest to this specific item. Your goal is to implement your function to estimate the top-5 items and print the average distance of these top 5 items to the query item."
      ],
      "id": "142c00a5-f36b-4a5f-9e27-4a3e38b467d7"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "b2dd70b9-8d2c-4134-b866-ab09af43a47d"
      },
      "outputs": [],
      "source": [
        "k=5\n",
        "query_vector = xb[2:3]"
      ],
      "id": "b2dd70b9-8d2c-4134-b866-ab09af43a47d"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "84a94ee2-3131-44c5-ba95-ec67aa675048"
      },
      "outputs": [],
      "source": [
        "def find_top_k_nn(query_vector,k):\n",
        "    \"\"\"\n",
        "    in this function, implement your definition of top-k nearest neighbours, and return the distances\n",
        "    and indices of the these top-k items.\n",
        "    \"\"\"\n",
        "    distances = np.sqrt(((xb - query_vector)**2).sum(axis=1))\n",
        "    sorted_idx = np.argsort(distances)\n",
        "    return distances[sorted_idx][:k], sorted_idx[:k]\n",
        "\n",
        "class SimpleSearch():\n",
        "  def __init__(self, db):\n",
        "    self.db = db\n",
        "  \n",
        "  def search(self, query_vector, k):\n",
        "    \"\"\"\n",
        "    in this function, implement your definition of top-k nearest neighbours, and return the distances\n",
        "    and indices of the these top-k items.\n",
        "    \"\"\"\n",
        "    distances = np.sqrt(((self.db - query_vector)**2).sum(axis=1))\n",
        "    sorted_idx = np.argsort(distances)\n",
        "    return distances[sorted_idx][:k], sorted_idx[:k]\n",
        "\n",
        "index0 = SimpleSearch(xb)"
      ],
      "id": "84a94ee2-3131-44c5-ba95-ec67aa675048"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b8a895ce-4f0b-41a5-8243-90f18bff8d7b"
      },
      "source": [
        "With your top-k NN function implemented, call this function to get the top-k nearest neighbor items for the query_vector and print the average distance. Also, print the time it takes to run this function:"
      ],
      "id": "b8a895ce-4f0b-41a5-8243-90f18bff8d7b"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0df9e9f8-a854-4896-9ebd-fd74bad21690",
        "outputId": "f82affc4-1aa6-4442-b481-74422aaab85c"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "distances from the k nearest neighbor fetched: [0.        2.054384  2.0941474 2.1664221 2.2330663]\n",
            "indices from the k nearest neighbor fetched: [     2 379284 539651 400245 409413]\n",
            "average distance of the k- nearest neighbors fetched:  1.709604\n",
            "CPU times: user 273 ms, sys: 1.57 ms, total: 274 ms\n",
            "Wall time: 289 ms\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "D, I = find_top_k_nn(query_vector, k)\n",
        "print(\"distances from the k nearest neighbor fetched:\",D)\n",
        "print(\"indices from the k nearest neighbor fetched:\",I)\n",
        "print(\"average distance of the k- nearest neighbors fetched: \",D.mean())"
      ],
      "id": "0df9e9f8-a854-4896-9ebd-fd74bad21690"
    },
    {
      "cell_type": "code",
      "source": [
        "index0.search(query_vector, k)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lrq4dD311-d3",
        "outputId": "1a8d6338-a1bf-4d33-b110-80fdbba067c8"
      },
      "id": "lrq4dD311-d3",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(array([0.       , 2.054384 , 2.0941474, 2.1664221, 2.2330663],\n",
              "       dtype=float32), array([     2, 379284, 539651, 400245, 409413]))"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bd4452f5-ce17-43df-95f2-e9b58e8cad5e"
      },
      "source": [
        "Now lets switch to using Faiss https://github.com/facebookresearch/faiss\n",
        "\n",
        "Faiss is a library for efficient similarity search and clustering of dense vectors. It contains algorithms that search in sets of vectors of any size, up to ones that possibly do not fit in RAM. "
      ],
      "id": "bd4452f5-ce17-43df-95f2-e9b58e8cad5e"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b6427be9-53b2-446c-851b-b2f6b7db9fa6"
      },
      "source": [
        "### Similarity search in Faiss\n",
        "\n",
        "Given a set of vectors x_i in dimension d, Faiss builds a data structure in RAM. After the structure is constructed, when given a new vector x in dimension d it performs efficiently the operation:\n",
        "\n",
        "$i = argmin_i ||x - x_i||$\n",
        "\n",
        "where ||.|| is the Euclidean distance (L2).\n",
        "\n",
        "In Faiss terms, the data structure is an index, an object that has an add method to add x_i vectors. Note that the x_i's are assumed to be fixed. Computing the argmin is the search operation on the index.\n",
        "\n",
        "### Indexes used by Faiss\n",
        "\n",
        "1. The inverted file from “Video google: A text retrieval approach to object matching in videos.”, Sivic & Zisserman, ICCV 2003. This is the key to non-exhaustive search in large datasets. Otherwise all searches would need to scan all elements in the index, which is prohibitive even if the operation to apply for each element is fast\n",
        "\n",
        "\n",
        "2. The product quantization (PQ) method from “Product quantization for nearest neighbor search”, Jégou & al., PAMI 2011. This can be seen as a lossy compression technique for high-dimensional vectors, that allows relatively accurate reconstructions and distance computations in the compressed domain.\n",
        "\n",
        "\n",
        "3. The three-level quantization (IVFADC-R aka IndexIVFPQR) method from \"Searching in one billion vectors: re-rank with source coding\", Tavenard & al., ICASSP'11."
      ],
      "id": "b6427be9-53b2-446c-851b-b2f6b7db9fa6"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3e63810d-fd22-49ca-b4bd-423ebf348c5f"
      },
      "source": [
        "We will implement these three indexes from faiss and use each of these three to search the index, and get the top-k nearest neighbour vectors, and estimate the average distance.\n",
        "\n",
        "Lets first construct the three indexes: index1, index2, index3 based on Flat index, Inverted index and product quantization techniques:"
      ],
      "id": "3e63810d-fd22-49ca-b4bd-423ebf348c5f"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "76487ec4-a020-4ccd-aa33-f6ef25869048",
        "outputId": "1695c685-e7e9-49d5-a817-e919e275ba4b"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "total number of vectors indexed =  1000000\n",
            "CPU times: user 98.9 ms, sys: 727 µs, total: 99.6 ms\n",
            "Wall time: 99.8 ms\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "index1 = faiss.IndexFlatL2(d)   # build the index\n",
        "index1.add(xb)                  # add vectors to the index\n",
        "print(\"total number of vectors indexed = \",index1.ntotal)"
      ],
      "id": "76487ec4-a020-4ccd-aa33-f6ef25869048"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "55447035-57e2-4938-837b-9bf20bf66ff6",
        "outputId": "8b24597b-6dc0-4496-cbf1-872f8b4f33e9"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "total number of vectors indexed =  1000000\n",
            "CPU times: user 1.77 s, sys: 138 ms, total: 1.91 s\n",
            "Wall time: 1.08 s\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "nlist = 100\n",
        "quantizer = faiss.IndexFlatL2(d)  # the other index\n",
        "index2 = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)\n",
        "index2.train(xb)\n",
        "index2.add(xb)\n",
        "print(\"total number of vectors indexed = \",index2.ntotal)"
      ],
      "id": "55447035-57e2-4938-837b-9bf20bf66ff6"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "f04ebe3c-705d-49b2-aa7b-3602c111c754",
        "outputId": "254b82a6-f845-4a25-d4b2-d296443b2b84"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "total number of vectors indexed =  1000000\n",
            "CPU times: user 45.8 s, sys: 137 ms, total: 46 s\n",
            "Wall time: 41.5 s\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "nlist = 100\n",
        "m = 8\n",
        "k = 4\n",
        "quantizer = faiss.IndexFlatL2(d)  # this remains the same\n",
        "index3 = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)\n",
        "                                  # 8 specifies that each sub-vector is encoded as 8 bits\n",
        "index3.train(xb)\n",
        "index3.add(xb)\n",
        "print(\"total number of vectors indexed = \",index3.ntotal)"
      ],
      "id": "f04ebe3c-705d-49b2-aa7b-3602c111c754"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "047a6682-f771-4672-8998-307f4cfad5f5"
      },
      "source": [
        "Now that we have these three indexes, let us query these to fetch the top-k nearest neghbour for our query_vector and compute the average distance we obtain for each.\n",
        "\n",
        "We will also time these commands, to find out the trade-off between accuracy and latency."
      ],
      "id": "047a6682-f771-4672-8998-307f4cfad5f5"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2e54dc7d-5d15-47b2-85e4-c583f92d52a8",
        "outputId": "aba70889-c0cd-4823-9bb0-292d5488aecd"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "distances from the k nearest neighbor fetched: [[0.        4.2204943 4.3854527 4.6933837]]\n",
            "indices from the k nearest neighbor fetched: [[     2 379284 539651 400245]]\n",
            "average distance of the k- nearest neighbors fetched:  3.324833\n",
            "CPU times: user 66.9 ms, sys: 0 ns, total: 66.9 ms\n",
            "Wall time: 65.7 ms\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "D, I = index1.search(query_vector, k)\n",
        "print(\"distances from the k nearest neighbor fetched:\", D)\n",
        "print(\"indices from the k nearest neighbor fetched:\", I)\n",
        "print(\"average distance of the k- nearest neighbors fetched: \", D.mean())"
      ],
      "id": "2e54dc7d-5d15-47b2-85e4-c583f92d52a8"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "be8f1b17-6108-41fd-814c-caa996fb731d",
        "outputId": "e18eb996-af2e-4477-a621-7a16f4f6958b"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "distances from the k nearest neighbor fetched: [[0.        5.0635023 5.4133463 5.642405 ]]\n",
            "indices from the k nearest neighbor fetched: [[     2 859123 177280  74082]]\n",
            "average distance of the k- nearest neighbors fetched:  4.0298133\n",
            "CPU times: user 2.71 ms, sys: 0 ns, total: 2.71 ms\n",
            "Wall time: 4.48 ms\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "D, I = index2.search(query_vector, k)\n",
        "print(\"distances from the k nearest neighbor fetched:\", D)\n",
        "print(\"indices from the k nearest neighbor fetched:\", I)\n",
        "print(\"average distance of the k- nearest neighbors fetched: \", D.mean())"
      ],
      "id": "be8f1b17-6108-41fd-814c-caa996fb731d"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2b230291-517c-49c5-a634-f9d4d331e241",
        "outputId": "df013726-cab7-494f-9a11-ed95bcffbf3c"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "distances from the k nearest neighbor fetched: [[1.1111705 5.027693  5.1296997 5.1854224]]\n",
            "indices from the k nearest neighbor fetched: [[     2 351653 703885 841943]]\n",
            "average distance of the k- nearest neighbors fetched:  4.1134963\n",
            "CPU times: user 2.02 ms, sys: 0 ns, total: 2.02 ms\n",
            "Wall time: 2.91 ms\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "D, I = index3.search(query_vector, k)\n",
        "print(\"distances from the k nearest neighbor fetched:\", D)\n",
        "print(\"indices from the k nearest neighbor fetched:\", I)\n",
        "print(\"average distance of the k- nearest neighbors fetched: \", D.mean())"
      ],
      "id": "2b230291-517c-49c5-a634-f9d4d331e241"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c2c902e3-c9bf-408e-9052-11af5a3b069f"
      },
      "source": [
        "Running all these, we observe that the product quantization based index is an order of magnitude faster than the inverted index. In terms of accuracy, if we assume that the lower the distance the more accurate the result, FlatIndex gives us the least distance."
      ],
      "id": "c2c902e3-c9bf-408e-9052-11af5a3b069f"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "044a818f-19ab-4c26-8532-922c9aa1d673"
      },
      "source": [
        "### Goal 1 for this week: Implement your k-NN function and time it\n",
        "\n",
        "The main goal for this part of the project is to implement your vanilla nearest neighbor function and fetch the closest k nearest neighbours to the query vector. Important to note that your implementation will give an exact result, i.e., your implementation will find the exact closest k vectors that will give the minimum distance to the query_vector.\n",
        "\n",
        "Please compile the results in a table, and compare the average distance obtained and the time it took to query the 1 million vectors. A nice 2D plot would also give you a good idea of the speed-accuracy trade-off involved."
      ],
      "id": "044a818f-19ab-4c26-8532-922c9aa1d673"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "2e69dd09-6a21-49a8-8ca8-4d5164a7e674"
      },
      "outputs": [],
      "source": [
        "batch_size = 25\n",
        "\n",
        "def benchmark(index, batch_size, k):\n",
        "  idx = np.random.choice(nq, batch_size, replace=False)\n",
        "  batch = xq[idx]\n",
        "  running_accuracy = 0\n",
        "  running_time = 0\n",
        "  for query_vector in batch:\n",
        "    tic = time.time()\n",
        "    D, _ = index.search(query_vector.reshape(1, -1), k)\n",
        "    toc = time.time()\n",
        "    running_accuracy += D.mean()\n",
        "    running_time += (toc-tic)\n",
        "  return running_accuracy/batch_size, running_time/batch_size"
      ],
      "id": "2e69dd09-6a21-49a8-8ca8-4d5164a7e674"
    },
    {
      "cell_type": "code",
      "source": [
        "runs = 100\n",
        "batch_size = 25\n",
        "k = 5"
      ],
      "metadata": {
        "id": "FsAH51PYLQ65"
      },
      "id": "FsAH51PYLQ65",
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "performance0 = pd.DataFrame([benchmark(index0, batch_size, k) for _ in range(runs)], columns=['l2_norm', 'speed'])"
      ],
      "metadata": {
        "id": "mKv5L6UfMJad",
        "outputId": "1b54cc98-88a3-4366-bfe8-25ae02a92fde",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "id": "mKv5L6UfMJad",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 10min 24s, sys: 2.71 s, total: 10min 27s\n",
            "Wall time: 10min 32s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "performance1 = pd.DataFrame([benchmark(index1, batch_size, k) for _ in range(runs)], columns=['l2_norm', 'speed'])"
      ],
      "metadata": {
        "id": "5mqOMDaQL-eU",
        "outputId": "c1d68982-2ed0-4607-f0bc-6d82099173c4",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "id": "5mqOMDaQL-eU",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 2min 28s, sys: 109 ms, total: 2min 28s\n",
            "Wall time: 2min 29s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "performance2 = pd.DataFrame([benchmark(index2, batch_size, k) for _ in range(runs)], columns=['l2_norm', 'speed'])"
      ],
      "metadata": {
        "id": "Tkct_BINMNzD",
        "outputId": "565d4a9a-dae6-4c15-ffdc-1409b3302880",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "id": "Tkct_BINMNzD",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 1.97 s, sys: 13 ms, total: 1.99 s\n",
            "Wall time: 2.05 s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "performance3 = pd.DataFrame([benchmark(index3, batch_size, k) for _ in range(runs)], columns=['l2_norm', 'speed'])"
      ],
      "metadata": {
        "id": "uejm_yROMQkI",
        "outputId": "7db0331d-1181-40fe-b3c2-d7130a1c0697",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "id": "uejm_yROMQkI",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 443 ms, sys: 6.95 ms, total: 450 ms\n",
            "Wall time: 901 ms\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(performance0.head(), '\\n',performance1.head(), '\\n',performance2.head(), '\\n',performance3.head())"
      ],
      "metadata": {
        "id": "kbMT7nLLMS5J",
        "outputId": "ede42929-c900-4d35-da86-a07cd9695efd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "id": "kbMT7nLLMS5J",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "    l2_norm     speed\n",
            "0  2.190194  0.313924\n",
            "1  2.157110  0.334423\n",
            "2  2.176960  0.353611\n",
            "3  2.180655  0.326983\n",
            "4  2.171909  0.242454 \n",
            "     l2_norm     speed\n",
            "0  4.694341  0.056154\n",
            "1  4.782393  0.056382\n",
            "2  4.768839  0.061936\n",
            "3  4.689457  0.067657\n",
            "4  4.778566  0.056041 \n",
            "     l2_norm     speed\n",
            "0  5.332048  0.000818\n",
            "1  5.450793  0.000814\n",
            "2  5.362532  0.000804\n",
            "3  5.315014  0.000819\n",
            "4  5.254040  0.000802 \n",
            "     l2_norm     speed\n",
            "0  4.689858  0.000220\n",
            "1  4.613375  0.000409\n",
            "2  4.787968  0.000434\n",
            "3  4.727607  0.000134\n",
            "4  4.681655  0.000733\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "plt.rcParams['figure.figsize'] = (12, 8)\n",
        "plt.scatter(performance0['speed'], performance0['l2_norm'], label='naive')\n",
        "plt.scatter(performance1['speed'], performance1['l2_norm'], label='IndexFlatL2')\n",
        "plt.scatter(performance2['speed'], performance2['l2_norm'], label='IndexIVFFlat')\n",
        "plt.scatter(performance3['speed'], performance3['l2_norm'], label='IndexIVFPQ')\n",
        "plt.ylabel('L2Norm')\n",
        "plt.xlabel('Time')\n",
        "plt.title(\"Avg KNN Distance vs Retrieval Time\")\n",
        "plt.legend()\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "TZ7gh-SRPqeh",
        "outputId": "791e236e-cf13-4c4d-8ef6-a16ec365d000",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 513
        }
      },
      "id": "TZ7gh-SRPqeh",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<Figure size 864x576 with 1 Axes>"
            ],
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAtAAAAHwCAYAAACPE1g3AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nOzde3xU1bn/8e9DQBNFwdJYuaigpQRRCJjSqlURq2gRrwileKr1dqq1oqfHtmqhlNajPUXx0nN+Hiy12lKBclOKiLaCbbVeguEiIFUpKgQUsYBAggGe3x+zJwxhJjM7k52ZhM/79ZpXZvZee88zi2n9ZmXttc3dBQAAACAzrXJdAAAAANCcEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQANZGbHmNk2MyvIdS0tmZndYWa/ivg9upqZm1nrBhy73MwGRFAWgDxFgAaQNTNbaGb/MrODIzz/tQmvBwTv9/XgtZvZMjNrldDmZ2b2m+B5PBw9Xee8vzOzsSne8yoz2x0E5G1m9k8ze9TMvhBv4+7vuXtbd9+dpv6rzOxvDfns+a5OP201syVmdkGGxw4ws7Xp2rn7f7n7tenaRSXhO7DNzPaYWVXC65Hu3svdF+aqPgBNjwANICtm1lXS6ZJc0oVN8H7nSpot6VvuPiVhVydJX09z+JfM7NQQb/d3d28rqZ2kr0qqkrTIzE4MU/MBIN5P7SX9r6QpZta+MU7ckBHhxhb8ktQ2+IzvSRqSsG1yrusD0PQI0ACy9U1JL0v6jaQrJcnMDjazzYlB08yKg5G7I4PX3zez9WZWaWbXBiPEn6/vjYKRzWmSvuHus+vs/m9JP0kTuP5b0l1hP6C773b3d9z9RkkvSBob1LPPn/2D0djVZvZJMGI90sx6SnpY0inBiOXmoO1gM6sIRm3fTxwJTzjvlWb2npl9ZGZ3JuwvCKY1vBO81yIzOzrYV2Jmz5nZx2a2ysyGJftMZjbczMrrbLvVzJ4Knn/NzFYE519nZv+ZQT/tkfRbSYdK6h6c52AzGx98jg/M7GEzKzKzQyXNk9QpYTS3k5mNNbPpwV8Htkq6Ktj2u4Q6v2xmLwXfsSXx6RMZfKaUfZ4NM1tjZl8Nno81sz8E9X9isb+MfMHMbjezD4P3PTfh2HZmNin438I6i/3lhClBQJ4jQAPI1jclTQ4eg8zsc+6+U9JMSSMS2g2T9IK7f2hm50n6D8VGdT8vaUAG7zNEsXA21N2fTrJ/pqStkq6q5xz/K+kL8bDTQDMVG3HfRxAIH5R0vrsfJulUSYvdfaWkbysYpXX3+MjsdsX6rr2kwZJuMLOL65z2K5J6SDpb0pggjEuxvhsh6WuSDpd0taQdQQ3PSfq9pCMVG5H/XzM7IcnnmCOph5l1T9j2jeBYSZok6d+Dz3KipOfTdUwQ/L4lqUbSu8HmeyR9QVKpYv/WnSWNcfftks6XVJkwmlsZHHORpOlB3+wzwmtmnSXNlfQzSZ+R9J+SZphZcQafKZM+bwzx7+oRkiokzVfsv7edJY2T9H8JbX8jaZdifdNX0rmScjZdBUBmCNAAGszMviLpWEnT3H2RpHcUCyxSLLQkTqlIDDLDJD3q7svdfYeCEd00zpL0lqQXU+x3SaMljTazg1K0qVJsBPpnGbxfKpWKBbdk9kg60cyK3H29uy9PdRJ3X+juy9x9j7svlfSEpDPrNPuJu1e5+xJJSyT1CbZfK+lH7r7KY5a4+yZJF0ha4+6Puvsud6+QNEPS5Unef4ekJxX8khOEzhJJTwVNaiSdYGaHu/u/3P31evrky8HIerWk8ZKuCH5RMknXS7rV3T92908k/ZfST7X5u7vPDvqmqs6+KyQ97e5PB/ufk1Qu6WvpPlOGfd4Y/uru8919l6Q/SCqWdI+710iaIqmrmbU3s88p9kvQLe6+3d0/lDRB6fsHQI4RoAFk40pJz7r7R8Hr3wfbJGmBpEPM7EsWmyddKmlWsK+TpPcTzpP4PJXRknZKmm0pLlYMRqbXSvr3es7zK0mfM7MhGbxnMp0lfZzkvbdLGq7YaPN6M5trZiWpThL0ywIz22hmW4LjPlun2YaE5zsktQ2eH63YLyt1HavYPO/N8YekkZKOSlHG77X3rwTfkDQ7CKGSdJli4e5dM3vBzE5J9VkkvRyMrB+hWFiNj9AXSzpEsXnj8XqeCbbXp77vw7GSLq/zGb8iqWO6z5RhnzeGDxKeV0n6KOFC0/gvBG2Dz9JGse9L/LP8n2J/PQCQxwjQABrEzIoUG0k+08w2mNkGSbdK6mNmfYLAME2xMDNC0h+DEUhJWi+pS8Lpjs7gLbcrFujaSfqDmbVJ0e5OSXcoFtz24+6fSvqJpJ9Ksgzet65LJP01xbnnu/s5ioW5NyU9Et+VpPnvFQubR7t7O8XmSWdaz/uSjk+x/QV3b5/waOvuN6Q4z3OSis2sVLF/o/hfCOTur7n7RYqFudmK/VvWy923SbpB0r+ZWV9JHykWGHsl1NMuuBhPSt4v9W2Pf8bf1vmMh7r7Pek+k7Lr8yi8r9gvhZ9N+CyHu3uvHNYEIAMEaAANdbGk3ZJOUGx0uVRST8XC5TeDNr9XbFR2pPYNMtMkfcvMeprZIYqNLqcVBPDzFBsF/n2yi62C5cTe0N6R8GR+K6kwOFdaFrtor5uZPaTYfO2fJGnzOTO7KJiHvFPSNsWmdEixEckudaaWHCbpY3evNrP+2jv1JRO/kvRTM+tuMb3NrIOkPyo2x/vfzKxN8PhiwtzpfQRTCv4g6ReKTUt5LvgsB1nsAsh2QZutCZ+lXu7+cVDfmOCiwkckTbC9F492NrNBCf3Swczahfjsv5M0xMwGBf8uhRZbDq9LfZ8pkE2fNzp3Xy/pWUn3mtnhZtbKzI43syimlQBoRARoAA11pWLzmN9z9w3xh6RfShppZq3d/RXFRo47KbbigiTJ3ecpdsHdAklvK7aKhxQLnvVy982SzlHswrTHLWHt5wQ/Uup5ygpGx8fU1yZwipltUyxALlTsgr0vuvuyJG1bKXZxX6ViUzzOVGw0VopdgLdc0gYzi093uVHSODP7JKgl7QhvgvuC9s8GtU2SVBT8gnGuYnNoKxWbAvJzSfWtz/17xS7m/EMwZzfu3yStsdhKGN9W7JegTN0v6Wtm1lvSDxT8Gwfn+pNiF0bK3d9UbB7y6mAKQ6d0J3b39xW7yPAOSRsVG8W9Tfv+9yzVZ8qmz6PyTUkHSVoh6V+KXTzZsd4jAOScudf3lzIAiF4wQvqGpIPrBB4AAPIOI9AAcsLMLrHYGsFHKDZKOofwDABoDgjQAHLl3yV9qNhqEru1d7oDAAB5jSkcAAAAQAiMQAMAAAAhEKABAACAEFrnuoCwPvvZz3rXrl1zXQYAAABauEWLFn3k7vvdPbXZBeiuXbuqvLw812UAAACghTOzd5NtZwoHAAAAEAIBGgAAAAiBAA0AAACE0OzmQAMAALQkNTU1Wrt2raqrq3NdygGrsLBQXbp0UZs2bTJqT4AGAADIobVr1+qwww5T165dZWa5LueA4+7atGmT1q5dq27dumV0DFM4AAAAcqi6ulodOnQgPOeImalDhw6h/gJAgAYAAMgxwnNuhe1/AjQAAABCefjhh/X444/nuoycYQ40AAAAQvn2t7+d6xJyihFoAACAZmR2xTqdds/z6vbDuTrtnuc1u2Jd1udcs2aNevbsqeuuu069evXSueeeq6qqKj3yyCP64he/qD59+uiyyy7Tjh07JEljx47V+PHj9eabb6p///77nOekk06SJC1atEhnnnmmTj75ZA0aNEjr16/Pus58QYAGAABoJmZXrNPtM5dp3eYquaR1m6t0+8xljRKi33rrLX3nO9/R8uXL1b59e82YMUOXXnqpXnvtNS1ZskQ9e/bUpEmT9jmmpKREn376qf75z39KkqZOnarhw4erpqZG3/3udzV9+nQtWrRIV199te68886sa8wXTOEAAABoJn4xf5Wqanbvs62qZrd+MX+VLu7bOatzd+vWTaWlpZKkk08+WWvWrNEbb7yhH/3oR9q8ebO2bdumQYMG7XfcsGHDNHXqVP3whz/U1KlTNXXqVK1atUpvvPGGzjnnHEnS7t271bFjx6zqyycEaAAAgGaicnNVqO1hHHzwwbXPCwoKVFVVpauuukqzZ89Wnz599Jvf/EYLFy7c77jhw4fr8ssv16WXXiozU/fu3bVs2TL16tVLf//737OuKx8xhQMAAKCZ6NS+KNT2bH3yySfq2LGjampqNHny5KRtjj/+eBUUFOinP/2phg8fLknq0aOHNm7cWBuga2pqtHz58khqzIVIA7SZrTGzZWa22MzKk+wfYGZbgv2LzWxMlPUAAAA0Z7cN6qGiNgX7bCtqU6DbBvWI5P1++tOf6ktf+pJOO+00lZSUpGw3fPhw/e53v9OwYcMkSQcddJCmT5+uH/zgB+rTp49KS0v10ksvRVJjLpi7R3dyszWSytz9oxT7B0j6T3e/INNzlpWVeXn5flk8UnNXz9UDrz+gDds36KhDj9KofqM0+LjBTVoDAABomVauXKmePXtm3H52xTr9Yv4qVW6uUqf2RbptUI+s5z8j+b+DmS1y97K6bZkDncbc1XM19qWxqt4du73j+u3rNfalsZJEiAYAAE3u4r6dCcw5FvUcaJf0rJktMrPrU7Q5xcyWmNk8M+sVcT2hPfD6A7XhOa56d7UeeP2BHFUEAACAXIp6BPor7r7OzI6U9JyZvenuf0nY/7qkY919m5l9TdJsSd3rniQI39dL0jHHHBNxyftavz35ot+ptgMAAKBli3QE2t3XBT8/lDRLUv86+7e6+7bg+dOS2pjZZ5OcZ6K7l7l7WXFxcZQl76eVJe+iVNsBAADQskWWAs3sUDM7LP5c0rmS3qjT5igzs+B5/6CeTVHV1BB7fE+o7QAAAGjZopzC8TlJs4J83FrS7939GTP7tiS5+8OShkq6wcx2SaqS9HWPclmQBuh4aMek0zXaH9w+B9UAAAAg1yIbgXb31e7eJ3j0cve7gu0PB+FZ7v7LYF8fd/+yu+fdAoGj+o1SqyTdtHnnZv3s5Z/loCIAAIDG1bZt21DtFy5cqAsuyHgV4n2MHTtWnTt3VmlpqUpLS/XDH/5QkjRgwAClW6r4/vvv144dO2pfd+3aVR99tO9qyZMnT1bv3r110kkn6dRTT9WSJUsaVGd9mMibgT1KPl1j6qqpmrt6bhNXAwAA0LzdeuutWrx4sRYvXqx77rkn4+PqBuhkunXrphdeeEHLli3T6NGjdf31qRaCazgCdBrplqtjOTsAANCklk6TJpwojW0f+7l0WqOdeuHChRowYICGDh2qkpISjRw5UvHZtc8884xKSkrUr18/zZw5s/aY7du36+qrr1b//v3Vt29fPfnkk5KkUaNGady4cZKk+fPn64wzztCePZldQ3bDDTeorKxMvXr10o9//GNJ0oMPPqjKykqdddZZOuuss1Iee+qpp+qII46QJH35y1/W2rVrw3dEGgToNDZs35DVfgAAgEazdJo052Zpy/uSPPZzzs2NGqIrKip0//33a8WKFVq9erVefPFFVVdX67rrrtOcOXO0aNEibdiwN//cddddGjhwoF599VUtWLBAt912m7Zv3667775bU6dO1YIFC3TzzTfr0UcfVatWseg5YcKE2ikc8+fP36+Gu+66S+Xl5Vq6dKleeOEFLV26VDfffLM6deqkBQsWaMGCBRl9lkmTJun8889vnI5JQIBO46hDj8pqPwAAQKP58zippmrfbTVVse2NpH///urSpYtatWql0tJSrVmzRm+++aa6deum7t27y8x0xRVX1LZ/9tlndc8996i0tFQDBgxQdXW13nvvPR1yyCF65JFHdM455+imm27S8ccfX3tM4hSOQYMG7VfDtGnT1K9fP/Xt21fLly/XihUrQn+OBQsWaNKkSfr5z3/esI6oB7fyTuOMLmdo6qqpKfeP6jeqCasBAAAHtC0ppiOk2t4ABx98cO3zgoIC7dq1q9727q4ZM2aoR48e++1btmyZOnTooMrKyozf/5///KfGjx+v1157TUcccYSuuuoqVVdXpz8wwdKlS3Xttddq3rx56tChQ6hjM8EIdBrz1+z/Z4W4Q1ofosHHDW7CagAAwAGtXZdw2xtJSUmJ1qxZo3feeUeS9MQTT9TuGzRokB566KHaudIVFRWSpHfffVf33nuvKioqNG/ePL3yyisZvdfWrVt16KGHql27dvrggw80b9682n2HHXaYPvnkk3qPf++993TppZfqt7/9rb7whS+E+pyZYgQ6jc07N6fct2NX/VeBAgAANKqzx8TmPCdO42hTFNseocLCQk2cOFGDBw/WIYccotNPP702yI4ePVq33HKLevfurT179qhbt26aM2eOrrnmGo0fP16dOnXSpEmTdNVVV+m1115L+159+vRR3759VVJSoqOPPlqnnXZa7b7rr79e5513Xu1caEnq3bt37dzqYcOGaevWrdq0aZNuvPFGSVLr1q3TLo8XluXZfUvSKisr88buhPqc9NhJ9e5fduWyJqoEAAC0RCtXrlTPnj0zP2DptNic5y1rYyPPZ4+Reg+LrsADRLJ/BzNb5O5lddsyAp1Gu4PaacunW3JdBgAAQEzvYQTmHGMOdBrndTsv1yUAAAAgjxCg06jvIkIAAAAceAjQadR3ESEAAAAOPARoAAAAIAQCNAAAABACARoAAOAA17Zt21DtFy5cqAsuuKBB7zV27FiNHz9ejz32mEaMGLHPvo8++kjFxcXauXOnBgwYoB49eqi0tFSlpaWaPn26pNjdEePb4rcaz6SexYsX6+mnn25QzXWxjB0AAACa3CWXXKLvfe972rFjhw455BBJ0vTp0zVkyJDa24lPnjxZZWX7LsNcVFSkxYsX77NtzZo1ad9v8eLFKi8v19e+9rWsa2cEGgAAoBmZu3quzp1+rno/1lvnTj9Xc1fPbbRzL1y4UAMGDNDQoUNVUlKikSNH1t6i+5lnnlFJSYn69eunmTNn1h6zfft2XX311erfv7/69u2rJ598UpI0atQojRs3TpI0f/58nXHGGdqzZ0/tcYcffrjOPPNMzZkzp3bblClT9huVDuvVV1/VKaecor59++rUU0/VqlWr9Omnn2rMmDGaOnWqSktLNXXq1KzegxFoAACAZmLu6rka+9JYVe+uliSt375eY18aK0kafNzgRnmPiooKLV++XJ06ddJpp52mF198UWVlZbruuuv0/PPP6/Of/7yGDx9e2/6uu+7SwIED9etf/1qbN29W//799dWvflV33323vvjFL+r000/XzTffrKeffrr2lttxI0aM0OTJkzV8+HBVVlbqH//4hwYOHFi7f+TIkSoqKpIk/fnPf1aHDh1UVVWl0tJSSVK3bt00a9asfc5ZUlKiv/71r2rdurX+9Kc/6Y477tCMGTM0btw4lZeX65e//GXWfUSABgAAaCYeeP2B2vAcV727Wg+8/kCjBej+/furS5cuklQ7x7ht27bq1q2bunfvLkm64oorNHHiREnSs88+q6eeekrjx4+P1VNdrffee089e/bUI488ojPOOEMTJkzQ8ccfv997DR48WDfeeKO2bt2qadOm6bLLLlNBQUHt/kyncCTasmWLrrzySr311lsyM9XU1GTXIUkQoAEAAJqJDds3hNreEPH5x1Lsgr1du3bV297dNWPGDPXo0WO/fcuWLVOHDh1UWVmZ9NiioiKdd955mjVrlqZMmaL77rsvu+IljR49WmeddZZmzZqlNWvWaMCAAVmfsy7mQAMAADQTRx16VKjtjaWkpERr1qzRO++8I0l64oknavcNGjRIDz30UO1c6YqKCknSu+++q3vvvVcVFRWaN2+eXnnllaTnHjFihO677z598MEHOuWUU7KudcuWLercubMk6Te/+U3t9sMOO0yffPJJ1ueXCNBptTuoXa5LAAAAkCSN6jdKhQWF+2wrLCjUqH6jIn3fwsJCTZw4UYMHD1a/fv105JFH1u4bPXq0ampq1Lt3b/Xq1UujR4+Wu+uaa67R+PHj1alTJ02aNEnXXnutqqur9zv3Oeeco8rKSg0fPlxmlnWt3//+93X77berb9+++4yen3XWWVqxYkWjXERo8d8WmouysjIvLy9vsvfr93g/1XjquTPLrlzWZLUAAICWZ+XKlerZs2fG7eeunqsHXn9AG7Zv0FGHHqVR/UY12vznA1myfwczW+TuZXXbMgc6jfrCMwAAQFMbfNxgAnOOMYUDAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAAe4tm3bhmq/cOFCXXDBBQ16r7Fjx2r8+PF67LHHNGLEiH32ffTRRyouLtbOnTs1YMAA9ejRQ6WlpSotLdX06dMlxe6OWFpaqhNPPFGXX365duzYIUlau3atLrroInXv3l3HHXecbrrpJu3cubNBNaZDgE6j46Edc10CAABAi3PJJZfoueeeqw3AkjR9+nQNGTKk9nbikydP1uLFi7V48WINHTpUUuz234sXL9Ybb7yhgw46SA8//LDcXZdeeqkuvvhivfXWW3rrrbdUVVWl73//+5HUToBOI+o7+wAAAISxZc4cvTXwbK3seYLeGni2tsyZ02jnXrhwoQYMGKChQ4eqpKREI0eOrL1F9zPPPKOSkhL169dPM2fOrD1m+/btuvrqq9W/f3/17dtXTz75pCRp1KhRGjdunCRp/vz5OuOMM7Rnz57a4w4//HCdeeaZmpNQ/5QpU/Ybla7P6aefrrffflvPP/+8CgsL9a1vfUtSbJR6woQJevzxx7Vt27aGd0gKBGgAAIBmYsucOVo/eox2VVZK7tpVWan1o8c0aoiuqKjQ/fffrxUrVmj16tV68cUXVV1dreuuu05z5szRokWLtGHDhtr2d911lwYOHKhXX31VCxYs0G233abt27fr7rvv1tSpU7VgwQLdfPPNevTRR9Wq1b7Rc8SIEZoyZYokqbKyUv/4xz80cODA2v0jR46sncKxadOmfY7dtWuX5s2bp5NOOknLly/XySefvM/+ww8/XF27dtXbb7/daH0TR4BO44HXH8h1CQAAAJKkDyfcL6+u3mebV1frwwn3N9p79O/fX126dFGrVq1UWlqqNWvW6M0331S3bt3UvXt3mZmuuOKK2vbPPvus7rnnHpWWlmrAgAGqrq7We++9p0MOOUSPPPKIzjnnHN100006/vjj93uvwYMH68UXX9TWrVs1bdo0XXbZZSooKKjdnziFo0OHDpKkqqoqlZaWqqysTMccc4yuueaaRvvsmeJW3mms374+5b6igqImrAQAABzodq1PnktSbW+I+PxjKTYVYteuXfW2d3fNmDFDPXr02G/fsmXL1KFDB1VWViY9tqioSOedd55mzZqlKVOm6L777ktbX3wOdKITTjih9iLDuK1bt2rDhg1J68oWI9BptLLUXXTh5y9swkoAAMCBrnXH5IsbpNreWEpKSrRmzRq98847kqQnnniidt+gQYP00EMP1c6VrqiokCS9++67uvfee1VRUaF58+bplVdeSXruESNG6L777tMHH3ygU045pUH1nX322dqxY4cef/xxSdLu3bv1ve99TzfddJOKihp/wJMAncYe35Ny31/W/qUJKwEAAAe6I2+9RVZYuM82KyzUkbfeEun7FhYWauLEiRo8eLD69eunI488snbf6NGjVVNTo969e6tXr14aPXq03F3XXHONxo8fr06dOmnSpEm69tprVV1n+okknXPOOaqsrNTw4cNlZg2qz8w0a9YsTZ8+Xd27d1eHDh3UqlUr3XnnnQ3+zPW+X/y3heairKzMy8vLm+z9zp1+br3TOJZduazJagEAAC3PypUr1bNnz4zbb5kzRx9OuF+71q9X644ddeStt6jdkCERVtj8vPTSSxoxYoRmzZqlfv36ZXRMsn8HM1vk7mV12zIHOo0zupyhqaumptw/d/VcDT5ucBNWBAAADmTthgwhMKdx6qmn6t13343s/EzhSCPdNA1W6QAAADiwEKDT2LB9Q1b7AQAA0LIQoNM46tCjstoPAACQTnO7Jq2lCdv/BOg0RvUbpcKCwqT7CgsKudU3AADISmFhoTZt2kSIzhF316ZNm1RYmDzvJcNFhGnELxB84PUHtH77erWyVtrje9Tx0I4a1W8UFxACAICsdOnSRWvXrtXGjRtzXcoBq7CwUF26dMm4PcvYAQAAAEmkWsaOKRwAAABACARoAAAAIAQCNAAAABACARoAAAAIgQANAAAAhBBpgDazNWa2zMwWm9l+S2dYzINm9raZLTWzflHWAwAAAGSrKdaBPsvdP0qx73xJ3YPHlyT9v+AnAAAAkJdyPYXjIkmPe8zLktqbWccc1wQAAACkFHWAdknPmtkiM7s+yf7Okt5PeL022AYAAADkpaincHzF3deZ2ZGSnjOzN939L2FPEoTv6yXpmGOOaewaAQAAgIxFOgLt7uuCnx9KmiWpf50m6yQdnfC6S7Ct7nkmunuZu5cVFxdHVS4AAACQVmQB2swONbPD4s8lnSvpjTrNnpL0zWA1ji9L2uLu66OqCQAAAMhWlCPQn5P0NzNbIulVSXPd/Rkz+7aZfTto87Sk1ZLelvSIpBsjrKfBtsyZo7cGnq2VPU/QWwPP1pY5c3JdEgAAAHIksjnQ7r5aUp8k2x9OeO6SvhNVDY1hy5w5Wj96jLy6WpK0q7JS60ePkSS1GzIkl6UBAAAgB3K9jF3e+3DC/bXhOc6rq/XhhPtzVBEAAAByiQCdxq7KylDbAQAA0LIRoAEAAIAQCNAAAABACARooK6l06QJJ0pj28d+Lp2W64oAAEAeifpOhEDzsnSaNOdmqaYq9nrL+7HXktR7WO7qAgAAeYMRaCDRn8ftDc9xNVWx7QAAACJAZ4UbqjSRppxSsWVtuO0AAOCAQ4DOAmtBN4H4lIot70vyvVMqogrR7bqE254J5lQDANCiEKCzsGv9+lyX0PI19ZSKs8dIbYr23damKLa9IZr6FwAAABA5AnQWrF27XJfQ8jX1lIrew6QhD6GeGM0AAB3HSURBVErtjpZksZ9DHmz4BYTMqQYAoMVhFY5sfPpprito+dp1CUZvk2yPSu9hjbfiBnOqAQBocRiBzoLv2JHrElq+7ucm377j4+YxDaLoiOTbo/wFAAAARIoAjfy2ZEry7TXb838u8dJp0qfb9t/eqk3D51QDAICcYwpHFqx9+1yX0LItnRYLyqnE5xKnm26xdFqs3Zb3JSuQfHdsbvPZY6K9Ocqfx0m7k0zzOfgwbsoCAEAzRoDOQsc778h1CS3bvB+kb5NuLnHdOwv67uC4JrjDYKraqv4VzfsBAIAmwRSOLLQbMiTXJbRsVR+nb5NuLnGyVTDikq2G0ZhrNkexpjQAAMg5AjSat3RzidONUG95f29Ibuw1mxt7TWkAAJAXCNDIX0WfSd8m3fSLTEZ74yG5sddsbuw1pQEAQF5gDjTy1/k/l2Zel3n7pdNi86bjUz+sleR7JJkkT31cPCRHsWZzY64pDQAA8gIj0MhfYYLn0mnSzH/fd96074k/USxE12PL+/WMVnv286EBAECLQYBG/goTWOf9QNKeehp4bAqFFSTfbQXJ5yzHZTsfGgAAtBgEaOSvMHOPM1mxY8vavcvY1eW768xZTiKb+dAAAKDFIEAjf2Uz9ziZdl1Sh2MpNk1Dkm59QymnfDR2TY2lMZffAwAA9SJAI38VHZG+TTwopluxI758XKbTNJrTGs6NvfweAACoFwEazVt8SkWvS1K3SVw+LtNpGs1pDefGXn4PAADUi2XskL8yueX1lvdjP996Nvn+dkcHUzISxIP02PZKurzdlvf3rgASX96uXZdYeM7HJemiWH4PAACkRIBG/mrXZW9Ars/Ydqn31RciU57fYtMfmssazqk+Rz5ONwEAoAVgCgfyV2NMl0gWIuMX3KUM5968pj80p+kmAAC0AIxAI3/1HhbuToR1FRwkfbo9NlUjPgVDil1gV3fOcF3NafpDc5puAgBAC0CAzsKWOXPUbsiQXJeBVHZ/und96PjKFK2L0odnqflNf2gu000AAGgBmMKRhQ8n3J/rErCfem7ZXVOV2Q1XZLHA/ZPPxOZXs64yAABIQIDOwq7163NdAvaTZFWNTNTe4tv2niN+10LWVQYAAAkI0Flo3bFjrkto2aIIrEWfSX7B3SUPB2tDpwjgrKsMAAACBOgsHHnrLbkuoWVr7MDapkg6/+cJN1KxfW+yku7CweZ0YSEAAIgMFxFmgQsII9aYgdUKpD7f2HuhXbIL7tKtO93cLiwEAACRYAQa+ashgbXoMwm36U64oNB3S0t+n3payNJpsSXvUmFdZQAAECBAI3+FDazxKRq3vpF8PnOqecxLp8UuEqy7QocF//NInOYBAAAOeEzhQP7K5EYq7Y5OfvOQVNM/trwf3IUw4Zg/j0u+NvThnWNhHAAAIAEBGs1X0WdSB9yU85lt7/b48nSpbqzCRYMAACAJpnCg+Tr/56n3nT1m/+XqEtd4jqupSlgDug4uGgQAAEkQoNMpSBGuUm1H06lvTnLvYfsvV5dqjWffnXxtaC4aBAAASRCg02g/7PJQ25FHeg+LTfEYuznhwsIk4hcJJlsbGgAAoA7mQKfR8cc/liRtnvYHafduqaBA7YddXrsdESv6zP6rY8S3h3X2mP3nPMdHmnsPIzADAICMmHuKP2vnqbKyMi8vL891GWgqS6dJT35H2v3p3m0FB0kX/U/DAu/SabFVN5Kt3AEAAJDAzBa5e1nd7YxAI7/Fw21jhV5GmgEAQJYI0Mh/hF4AAJBHuIgQAAAACIEADQAAAIRAgAYAAABCiDxAm1mBmVWY2R+T7LvKzDaa2eLgcW3U9QAAAADZaIqLCEdJWinp8BT7p7r7TU1QBwAAAJC1SEegzayLpMGSfhXl+wAAAABNJeopHPdL+r6kPfW0uczMlprZdDNLca9lAAAAID9EFqDN7AJJH7r7onqazZHU1d17S3pO0mMpznW9mZWbWfnGjRsjqBYAAADITJQj0KdJutDM1kiaImmgmf0usYG7b3L3ncHLX0k6OdmJ3H2iu5e5e1lxcXGEJQMAAAD1iyxAu/vt7t7F3btK+rqk5939isQ2ZtYx4eWFil1sCAAAAOStJr+Vt5mNk1Tu7k9JutnMLpS0S9LHkq5q6noAAACAMMzdc11DKGVlZV5eXp7rMgAAANDCmdkidy+ru507EQIAAAAhEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAEAIBGgAAAAgBAI0AAAAEAIBGgAAAAiBAA0AAACEQIAGAAAAQiBAAwAAACEQoAEAAIAQCNAAAABACARoAAAAIAQCNAAAABACARoAAAAIgQANAAAAhECABgAAAEIgQAMAAAAhEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAEAIBGgAAAAgBAI0AAAAEAIBGgAAAAiBAA0AAACEQIAGAAAAQiBAAwAAACEQoAEAAIAQCNAAAABACARoAAAAIAQCNAAAABACARoAAAAIgQANAAAAhECABgAAAEIgQAMAAAAhEKABAACAECIP0GZWYGYVZvbHJPsONrOpZva2mb1iZl2jrgcAAADIRlOMQI+StDLFvmsk/cvdPy9pgqSfN0E9AAAAQINFGqDNrIukwZJ+laLJRZIeC55Pl3S2mVmUNQEAAADZiHoE+n5J35e0J8X+zpLelyR33yVpi6QOEdcEAAAANFhkAdrMLpD0obsvaoRzXW9m5WZWvnHjxkaoDgAAAGiYKEegT5N0oZmtkTRF0kAz+12dNuskHS1JZtZaUjtJm+qeyN0nunuZu5cVFxdHWDIAAABQv8gCtLvf7u5d3L2rpK9Let7dr6jT7ClJVwbPhwZtPKqaAAAAgGy1zrShmR2h2Ghx7THu/nrYNzSzcZLK3f0pSZMk/dbM3pb0sWJBGwAAAMhbGQVoM/uppKskvSMpPkLskgZmcry7L5S0MHg+JmF7taTLMy0WAAAAyLVMR6CHSTre3T+NshgAAAAg32U6B/oNSe2jLAQAAABoDjIdgb5bUoWZvSFpZ3yju18YSVUAAABAnso0QD+m2G22lyn1TVEAAACAFi/TAL3D3R+MtBIAAACgGcg0QP/VzO5WbN3mxCkcoZexAwAAAJqzTAN03+DnlxO2ZbyMHQAAANBSpA3QZlYg6Sl3n9AE9QAAAAB5Le0ydu6+W9KIJqgFAAAAyHuZTuF40cx+KWmqpO3xjcyBBgAAwIEm0wBdGvwcl7CNOdAAAAA44GQUoN39rKgLAQAAAJqDjG7lbWbtzOw+MysPHveaWbuoiwMAAADyTUYBWtKvJX0iaVjw2Crp0aiKAgAAAPJVpnOgj3f3yxJe/8TMFkdREAAAAJDPMh2BrjKzr8RfmNlpkqqiKQkAAADIX5mOQN8g6bFg3rNJ+ljSVVEVBQAAAOSrTFfhWCypj5kdHrzeGmlVAAAAQJ6qN0Cb2TdTbJckufvjEdQEAAAA5K10I9BfTLH9QkmdJRGgAQAAcECpN0C7+3fjzy027DxS0g8kvSzprmhLAwAAAPJP2jnQZtZasQsG/1Ox4DzU3VdFXBcAAACQl9LNgf6OpFGS/izpPHdf0xRFAQAAAPkq3Qj0Q5I+lPQVSafFLx5UbCk7d/feEdYGAAAA5J10Abpbk1QBAAAANBPpLiJ8t6kKAQAAAJqDem/lbWZHm9kUM/urmd1hZm0S9s2OvjwAAAAgv9QboCX9WtJCSd+V1FHSC2bWIdh3bIR1AQAAAHkp3RzoYnd/OHj+XTO7QtJfzOxCSR5taQAAAED+SReg25hZobtXS5K7/87MNkiaL+nQyKsDAAAA8ky6KRy/kvSlxA3u/idJl0t6I6qiAAAAgHyVbhWOCSm2V5jZ3GhKAgAAAPJXuhHo+vxHo1UBAAAANBPZBGhL3wQAAABoWbIJ0KzCAQAAgANOvXOgzewTJQ/KJqkokooAAACAPJbuIsLDmqoQAAAAoDnIZgoHAAAAcMAhQAMAAAAhEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAEAIBGgAAAAghMgCtJkVmtmrZrbEzJab2U+StLnKzDaa2eLgcW1U9QAAAACNoXWE594paaC7bzOzNpL+Zmbz3P3lOu2muvtNEdYBAAAANJrIArS7u6Rtwcs2wcOjej8AAACgKUQ6B9rMCsxssaQPJT3n7q8kaXaZmS01s+lmdnSU9QAAAADZijRAu/tudy+V1EVSfzM7sU6TOZK6untvSc9JeizZeczsejMrN7PyjRs3RlkyAAAAUK8mWYXD3TdLWiDpvDrbN7n7zuDlrySdnOL4ie5e5u5lxcXF0RYLAAAA1CPKVTiKzax98LxI0jmS3qzTpmPCywslrYyqHgAAAKAxRLkKR0dJj5lZgWJBfZq7/9HMxkkqd/enJN1sZhdK2iXpY0lXRVgPAAAAkDWLLZbRfJSVlXl5eXmuywAAAEALZ2aL3L2s7nbuRAgAAACEQIAGAAAAQiBAAwAAACEQoAEAAIAQCNAAAABACARoAAAAIAQCNAAAABACARoAAAAIgQANAAAAhECABgAAAEIgQAMAAAAhEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAEAIBGgAAAAgBAI0AAAAEAIBGgAAAAiBAA0AAACEQIAGAAAAQiBAAwAAACEQoAEAAIAQCNAAAABACARoAAAAIAQCNAAAABACARoAAAAIgQANAAAAhECABgAAAEIgQAMAAAAhEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAEAIBGgAAAAgBAI0AAAAEAIBGgAAAAiBAA0AAACEQIAGAAAAQogsQJtZoZm9amZLzGy5mf0kSZuDzWyqmb1tZq+YWdeo6gEAAAAaQ5Qj0DslDXT3PpJKJZ1nZl+u0+YaSf9y989LmiDp5xHWAwAAAGQtsgDtMduCl22Ch9dpdpGkx4Ln0yWdbWYWVU0AAABAtiKdA21mBWa2WNKHkp5z91fqNOks6X1JcvddkrZI6hBlTQAAAEA2Ig3Q7r7b3UsldZHU38xObMh5zOx6Mys3s/KNGzc2bpEAAABACE2yCoe7b5a0QNJ5dXatk3S0JJlZa0ntJG1KcvxEdy9z97Li4uKoywUAAABSinIVjmIzax88L5J0jqQ36zR7StKVwfOhkp5397rzpAEAAIC80TrCc3eU9JiZFSgW1Ke5+x/NbJykcnd/StIkSb81s7clfSzp6xHWAwAAAGQtsgDt7ksl9U2yfUzC82pJl0dVAwAAANDYuBMhAAAAEAIBGgAAAAiBAA0AAACEQIAGAAAAQiBAAwAAACEQoAEAAIAQCNAAAABACARoAAAAIAQCNAAAABACARoAAAAIgQANAAAAhECABgAAAEIgQAMAAAAhEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAEAIBGgAAAAgBAI0AAAAEAIBGgAAAAiBAA0AAACEQIAGAAAAQiBAAwAAACEQoAEAAIAQCNAAAABACARoAAAAIAQCNAAAABACARoAAAAIgQANAAAAhECABgAAAEIgQAMAAAAhEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAEAIBGgAAAAgBAI0AAAAEAIBGgAAAAghsgBtZkeb2QIzW2Fmy81sVJI2A8xsi5ktDh5joqoHAAAAaAytIzz3Lknfc/fXzewwSYvM7Dl3X1Gn3V/d/YII6wAAAAAaTWQj0O6+3t1fD55/ImmlpM5RvR8AAADQFJpkDrSZdZXUV9IrSXafYmZLzGyemfVKcfz1ZlZuZuUbN26MsFIAAACgfpEHaDNrK2mGpFvcfWud3a9LOtbd+0h6SNLsZOdw94nuXubuZcXFxdEWDAAAANQj0gBtZm0UC8+T3X1m3f3uvtXdtwXPn5bUxsw+G2VNAAAAQDaiXIXDJE2StNLd70vR5qigncysf1DPpqhqAgAAALIV5Socp0n6N0nLzGxxsO0OScdIkrs/LGmopBvMbJekKklfd3ePsCYAAAAgK5EFaHf/myRL0+aXkn4ZVQ0AAABAY+NOhAAAAEAIBGgAAAAgBAI0AAAAEAIBGgAAAAiBAA0AAACEQIAGAAAAQiBAAwAAACEQoAEAAIAQCNAAAABACARoAAAAIAQCNAAAABACARoAAAAIgQANAAAAhECABgAAAEIgQAMAAAAhEKABAACAEAjQAAAAQAgEaAAAACAEAjQAAAAQAgEaAAAACIEADQAAAIRAgAYAAABCIEADAAAAIRCgAQAAgBAI0AAAAEAIrXNdAAAACG92xTr9Yv4qVW6uUqf2RbptUA9d3LdzrssCDgjm7rmuIZSysjIvLy/PdRkAADSJZEFZkm6fuUxVNbtr27UpMB16UGttqaqpN1ATvIHMmdkidy/bbzsBGgCA/FA33J5VUqwZi9btE5RN0iEHFWj7p7tTn0hSUZsC3X3pSbq4b2fNrlinn8xZrn/tqNmvnUlySZ0J08B+CNAAAOSR+kJtXDzcNlQ8FN82fYlqdmd2pvZFbTT2wl4E6RzgrwP5hwANAECemF2xLlSozUaBmXY34L/1BOmmNbti3X7TchL/itAY5yech5cqQHMRIQAATewX81c1SXiW1KDwLEmbq2p0+8xlkkTQagK/mL9qn/AsSVU1u/WL+auy7v+64Xzd5qpm8W+bz6GfAA0AQBOr3FyV6xIyUlWzW9+btkRSfgetTORzGJNSfyca47sSZTiPSr6HftaBBgCgiXVqX5TrEjK22123z1ym2RXrcl1Kg8XD2LrNVXLtDWP59JlSfSca47vSkHA+u2KdTrvneXX74Vydds/zTd5X9YX+fECABgCgicWXomsu8im4NES+hzEp9p0oalOwz7aiNgWN8l0JG87z4ReOKEfkGwMBGgCAJpYPf4IOK1+CS0PkexiTYt+Juy89SZ3bF8kUW0GlsS4gDBvO8+EXjihH5BsDc6ABAMiBzu2LtC6PAlw6+RJcGqJTir7Ot890cd/OkfxyFT9npnPA8+EXjtsG9Ui6Kkm+/PWGAA0AQA4kCwj5Kp+CS0PkexhrCmHCeT78whE29Dc1AjQAADmQGBCyHYnuHNy18I9L1mtzVeobs6RjkiYML62tKx+DS0PkexjLN/nyC0dUI/KNgRupAACQB2ZXrNPYp5bvE4ATb2byo9nLNPnl9/a5M2GqG20kO1die0mR3rQDzV++L/vXVLgTIQAAzVzYUFNfewISkB4BGgAAAAghVYBmGTsAAAAgBAI0AAAAEAIBGgAAAAiBAA0AAACEQIAGAAAAQiBAAwAAACEQoAEAAIAQCNAAAABACARoAAAAIITIArSZHW1mC8xshZktN7NRSdqYmT1oZm+b2VIz6xdVPQAAAEBjaB3huXdJ+p67v25mh0laZGbPufuKhDbnS+oePL4k6f8FPwEAAIC8FNkItLuvd/fXg+efSFopqXOdZhdJetxjXpbU3sw6RlUTAAAAkK0mmQNtZl0l9ZX0Sp1dnSW9n/B6rfYP2TKz682s3MzKN27cGFWZAAAAQFqRB2gzaytphqRb3H1rQ87h7hPdvczdy4qLixu3QAAAACCESAO0mbVRLDxPdveZSZqsk3R0wusuwTYAAAAgL5m7R3NiM5P0mKSP3f2WFG0GS7pJ0tcUu3jwQXfvn+a8GyW928jlZuKzkj7KwfseCOjbaNCv0aBfo0G/RoN+jQb9Go187Ndj3X2/6Q9RBuivSPqrpGWS9gSb75B0jCS5+8NByP6lpPMk7ZD0LXcvj6SgLJlZubuX5bqOloi+jQb9Gg36NRr0azTo12jQr9FoTv0a2TJ27v43SZamjUv6TlQ1AAAAAI2NOxECAAAAIRCgMzcx1wW0YPRtNOjXaNCv0aBfo0G/RoN+jUaz6dfI5kADAAAALREj0AAAAEAIBGhJZnaema0ys7fN7IdJ9h9sZlOD/a8Ed1aM77s92L7KzAY1Zd35rqH9amZdzazKzBYHj4ebuvZ8lkG/nmFmr5vZLjMbWmfflWb2VvC4sumqzn9Z9uvuhO/rU01Xdf7LoF//w8xWmNlSM/uzmR2bsI/vawpZ9ivf13pk0LffNrNlQf/9zcxOSNhHJkihof2at5nA3Q/oh6QCSe9IOk7SQZKWSDqhTpsbJT0cPP+6pKnB8xOC9gdL6hacpyDXnykfHln2a1dJb+T6M+TjI8N+7Sqpt6THJQ1N2P4ZSauDn0cEz4/I9WfKh0c2/Rrs25brz5CPjwz79SxJhwTPb0j4/wG+rxH0a/Ca72t2fXt4wvMLJT0TPCcTRNOveZkJGIGW+kt6291Xu/unkqZIuqhOm4sUuymMJE2XdHawhvVFkqa4+053/6ekt4PzIbt+RWpp+9Xd17j7Uu1dfz1ukKTn3P1jd/+XpOcUW4Md2fUrUsukXxe4+47g5cuK3ZFW4vtan2z6FfXLpG+3Jrw8VFL8YjIyQWrZ9GteIkBLnSW9n/B6bbAtaRt33yVpi6QOGR57oMqmXyWpm5lVmNkLZnZ61MU2I9l85/i+ppZt3xSaWbmZvWxmFzduac1a2H69RtK8Bh57IMmmXyW+r/XJqG/N7Dtm9o6k/5Z0c5hjD1DZ9KuUh5kgshupAFlYL+kYd99kZidLmm1mver8dgrkk2PdfZ2ZHSfpeTNb5u7v5Lqo5sTMrpBUJunMXNfSkqToV76vWXL3/5H0P2b2DUk/ksQc/UaQol/zMhMwAi2tk3R0wusuwbakbcystaR2kjZleOyBqsH9Gvz5a5MkufsixeZNfSHyipuHbL5zfF9Ty6pv3H1d8HO1pIWS+jZmcc1YRv1qZl+VdKekC919Z5hjD1DZ9Cvf1/qF/d5NkRQfxec7m1qD+zVfMwEBWnpNUncz62ZmByl2MVvdq5Kf0t7fLodKet5jM9ufkvR1i60m0U1Sd0mvNlHd+a7B/WpmxWZWIEnBCEl3xS4gQmb9msp8Seea2RFmdoSkc4NtyKJfg/48OHj+WUmnSVoRWaXNS9p+NbO+kv5PsZD3YcIuvq+pNbhf+b6mlUnfdk94Ofj/t3fHrFEEcRjGnxcN2IuFnWhhEa2CRVKJnYoWmi9g/BhpgmCh2IhgKQh2diIYUQhiJygnR4qojYWofUQ0kLG4Ba8RMiEye5fnBwPLsgMzf/bu3tvb2QM+dttmgn/bdV17mwlar2LsQwMuAB8YfatZ7vbdYPTGA3AIeMxoQcAb4PhY3+Wu3wZwvvVc+tR2W1fgKrAODIB3wKXWc+lT20FdzzC6v+wHo19K1sf6LnX1/gRcaz2XPrXd1hVYAIaMVpUPgeut59KntoO6vgS+d6/3AfBkrK/n6x7X1fN1T2p7d+wzag2YHetrJtjjuvY1E/hPhJIkSVIFb+GQJEmSKhigJUmSpAoGaEmSJKmCAVqSJEmqYICWJEmSKhigJWkCJTmcZNC1b0m+dNubSe63Hp8kTTMfYydJEy7JCrBZSrnTeiyStB94BVqSpkiSs0medtsrSR4meZ3kc5IrSW4nGSZZTTLTHTeX5FWSt0meJznadhaS1G8GaEmabieAc8Bl4BGwVko5DfwELnYh+h6wWEqZAx4AN1sNVpImwcHWA5Ak/VfPSilbSYbAAWC12z8EjgEngVPAiyR0x3xtME5JmhgGaEmabr8ASinbSbbK34Uv24w+AwKsl1LmWw1QkiaNt3BI0v62ARxJMg+QZCbJbOMxSVKvGaAlaR8rpfwGFoFbSd4DA2Ch7agkqd98jJ0kSZJUwSvQkiRJUgUDtCRJklTBAC1JkiRVMEBLkiRJFQzQkiRJUgUDtCRJklTBAC1JkiRVMEBLkiRJFf4Ap2vRr7hgW3AAAAAASUVORK5CYII=\n"
          },
          "metadata": {
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "del xb, xq, performance0, performance1, performance2, performance3"
      ],
      "metadata": {
        "id": "aOYsWlHhUksF"
      },
      "id": "aOYsWlHhUksF",
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "e127987e-44f9-43b3-9219-1036edd0d14c"
      },
      "source": [
        "# Part B: User representations"
      ],
      "id": "e127987e-44f9-43b3-9219-1036edd0d14c"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "13c18e33-3a62-4afe-95af-9d33ef87917c"
      },
      "source": [
        "In the second part of this week's project, we wish to understand few ways of estimating user representations, and how it impacts the performance of downstream tasks.\n",
        "\n",
        "To this end, we will work on top of our H&M dataset, and develop a few different ways of representing users.\n",
        "\n",
        "The broader framework here will be -- we fix the article representations, and fix the downstream task, and then vary the user representations and see how the performance of the downstream task changes based on different user representation techniques.\n"
      ],
      "id": "13c18e33-3a62-4afe-95af-9d33ef87917c"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "dd824205-1569-4b54-8c48-fda93a59053d",
        "outputId": "dd28dd44-f37b-4ad2-866a-098c93d4aeaa",
        "scrolled": true
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Requirement already satisfied: lightgbm in /usr/local/lib/python3.7/dist-packages (2.2.3)\n",
            "Requirement already satisfied: scikit-learn in /usr/local/lib/python3.7/dist-packages (from lightgbm) (1.0.2)\n",
            "Requirement already satisfied: scipy in /usr/local/lib/python3.7/dist-packages (from lightgbm) (1.7.3)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.7/dist-packages (from lightgbm) (1.21.6)\n",
            "Requirement already satisfied: joblib>=0.11 in /usr/local/lib/python3.7/dist-packages (from scikit-learn->lightgbm) (1.1.0)\n",
            "Requirement already satisfied: threadpoolctl>=2.0.0 in /usr/local/lib/python3.7/dist-packages (from scikit-learn->lightgbm) (3.1.0)\n"
          ]
        }
      ],
      "source": [
        "!pip install lightgbm"
      ],
      "id": "dd824205-1569-4b54-8c48-fda93a59053d"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "251abdd1-1cd4-41f9-af70-23d22a1aa455"
      },
      "outputs": [],
      "source": [
        "import numpy as np # linear algebra\n",
        "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
        "import random\n",
        "import gc\n",
        "from sklearn.model_selection import train_test_split\n",
        "from sklearn.model_selection import StratifiedKFold\n",
        "from sklearn.model_selection import GroupShuffleSplit\n",
        "from sklearn.model_selection import GroupKFold\n",
        "from sklearn.preprocessing import LabelEncoder\n",
        "\n",
        "from sklearn.feature_extraction.text import TfidfVectorizer\n",
        "from sklearn.decomposition import TruncatedSVD\n",
        "import lightgbm as lgb\n",
        "import datetime\n",
        "import itertools\n",
        "import os\n",
        "from contextlib import redirect_stdout\n",
        "from tqdm.notebook import tqdm"
      ],
      "id": "251abdd1-1cd4-41f9-af70-23d22a1aa455"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "219f3784-220e-4889-ae88-09c80f556479"
      },
      "source": [
        "While we have used neural models so far, lets try a tree based model for this task. We use LightGBM library to train the main model. Lets set up few parameters for the lightgbm model, and specify some additional parameters:"
      ],
      "id": "219f3784-220e-4889-ae88-09c80f556479"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "21e76b18-8d9e-4a1b-bf84-a929c8f16c6f"
      },
      "outputs": [],
      "source": [
        "rand = 64\n",
        "lgb_params = {\n",
        "    \"objective\": \"binary\",\n",
        "    \"boosting\": \"gbdt\",\n",
        "    \"max_depth\": -1,\n",
        "    \"num_leaves\": 40,\n",
        "    \"subsample\": 0.8,\n",
        "    \"subsample_freq\": 1,\n",
        "    \"bagging_seed\": rand,\n",
        "    \"learning_rate\": 0.05,\n",
        "    \"feature_fraction\": 0.6,\n",
        "    \"min_data_in_leaf\": 100,\n",
        "    \"lambda_l1\": 0,\n",
        "    \"lambda_l2\": 0,\n",
        "    \"random_state\": rand,\n",
        "    \"metric\": \"auc\",#\"binary_logloss\",\n",
        "    \"verbose\": -1\n",
        "}\n",
        "\n",
        "tran_dtypes = {\"t_dat\":\"str\",\n",
        "               \"customer_id\":\"str\",\n",
        "               \"article_id\":\"int\",\n",
        "               \"product_code\":\"int\",\n",
        "               \"price\":\"float\",\n",
        "               \"sales_channel_id\":\"int\"}\n",
        "art_dtypes = {\"article_id\":\"int\",\n",
        "              \"product_code\":\"int\",\n",
        "              \"product_type_no\":\"int\",\n",
        "              \"graphical_appearance_no\":\"int\",\n",
        "              \"colour_group_code\":\"int\",\n",
        "              \"department_no\":\"int\",\n",
        "              \"index_code\":\"str\",\n",
        "              \"index_group_no\":\"int\",\n",
        "              \"section_no\":\"int\",\n",
        "              \"garment_group_no\":\"int\"}\n",
        "cust_dtypes = {\"customer_id\":\"str\"}\n",
        "\n",
        "obj = \"class\" # \"class\" or \"rank\"\n",
        "N = 15000\n",
        "n_iter = 2 # num of iteration\n",
        "idx_file = \"exp1\"\n",
        "n_round = 2000\n",
        "n_splits = 1\n",
        "nobuy = 20 # num of negative samples"
      ],
      "id": "21e76b18-8d9e-4a1b-bf84-a929c8f16c6f"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3df9c2e0-af9e-406d-a9c6-c38a87347728"
      },
      "source": [
        "While we vary the user represnetations, we will keep the article representation fixed. The code below reads the article.csv file and extracts a number of features to represent articles."
      ],
      "id": "3df9c2e0-af9e-406d-a9c6-c38a87347728"
    },
    {
      "cell_type": "code",
      "source": [
        "!gdown --folder https://drive.google.com/drive/folders/10LGZMgXRuz2qPr_QDbYdVVlKEcnQ25YL?usp=sharing -O ./"
      ],
      "metadata": {
        "id": "8LkPbjb9STz1",
        "outputId": "db08bce3-8483-40cb-ffac-3201044e9265",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "id": "8LkPbjb9STz1",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Retrieving folder list\n",
            "Processing file 1_jFxa2s7ONQ7nrhqFc1lARP6WChs2T4e data1.txt\n",
            "Processing file 1rEJFi98sLUTYj50Fh8ff33A7NKOoT87c hmdata.zip\n",
            "Processing file 1D3RyRBKBaw0KbLxpJUQDjVIt5CLpE2n9 log_mini.csv\n",
            "Processing file 1BELTuH4nBeyHna5EAGzJv-HWHKrbxPsf Spotify-dataset-description.pdf\n",
            "Processing file 1Z8N0Xf9M34PuN4V5G5uAxasvOCm6TVp4 tf_mini.csv\n",
            "Retrieving folder list completed\n",
            "Building directory structure\n",
            "Building directory structure completed\n",
            "Downloading...\n",
            "From: https://drive.google.com/uc?id=1_jFxa2s7ONQ7nrhqFc1lARP6WChs2T4e\n",
            "To: /content/data/data1.txt\n",
            "100% 158M/158M [00:02<00:00, 75.8MB/s]\n",
            "Downloading...\n",
            "From: https://drive.google.com/uc?id=1rEJFi98sLUTYj50Fh8ff33A7NKOoT87c\n",
            "To: /content/data/hmdata.zip\n",
            "100% 773M/773M [00:07<00:00, 109MB/s] \n",
            "Downloading...\n",
            "From: https://drive.google.com/uc?id=1D3RyRBKBaw0KbLxpJUQDjVIt5CLpE2n9\n",
            "To: /content/data/log_mini.csv\n",
            "100% 28.9M/28.9M [00:00<00:00, 98.3MB/s]\n",
            "Downloading...\n",
            "From: https://drive.google.com/uc?id=1BELTuH4nBeyHna5EAGzJv-HWHKrbxPsf\n",
            "To: /content/data/Spotify-dataset-description.pdf\n",
            "100% 176k/176k [00:00<00:00, 59.8MB/s]\n",
            "Downloading...\n",
            "From: https://drive.google.com/uc?id=1Z8N0Xf9M34PuN4V5G5uAxasvOCm6TVp4\n",
            "To: /content/data/tf_mini.csv\n",
            "100% 28.0M/28.0M [00:00<00:00, 167MB/s]\n",
            "Download completed\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# !ls data"
      ],
      "metadata": {
        "id": "SbdWgpajSXBM"
      },
      "id": "SbdWgpajSXBM",
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "!unzip data/hmdata.zip"
      ],
      "metadata": {
        "id": "tOhYQ6fqSeDd",
        "outputId": "e4d2bbab-916e-45f2-f408-baece3c0fb8a",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "id": "tOhYQ6fqSeDd",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Archive:  data/hmdata.zip\n",
            "   creating: hmdata/\n",
            "  inflating: hmdata/customers.csv.zip  \n",
            "  inflating: __MACOSX/hmdata/._customers.csv.zip  \n",
            "  inflating: hmdata/articles.csv.zip  \n",
            "  inflating: __MACOSX/hmdata/._articles.csv.zip  \n",
            "  inflating: hmdata/transactions_train.csv.zip  \n",
            "  inflating: __MACOSX/hmdata/._transactions_train.csv.zip  \n",
            "  inflating: hmdata/sample_submission.csv.zip  \n",
            "  inflating: __MACOSX/hmdata/._sample_submission.csv.zip  \n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# !ls hmdata"
      ],
      "metadata": {
        "id": "3x79VCe7ShRU"
      },
      "id": "3x79VCe7ShRU",
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fb93a7cd-a637-4960-9577-08449a57b55d",
        "outputId": "82f33866-12a7-4883-c88d-b043406e1dae"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/sklearn/utils/validation.py:598: FutureWarning: np.matrix usage is deprecated in 1.0 and will raise a TypeError in 1.2. Please convert to a numpy array with np.asarray. For more information see: https://numpy.org/doc/stable/reference/generated/numpy.matrix.html\n",
            "  FutureWarning,\n",
            "/usr/local/lib/python3.7/dist-packages/sklearn/utils/validation.py:598: FutureWarning: np.matrix usage is deprecated in 1.0 and will raise a TypeError in 1.2. Please convert to a numpy array with np.asarray. For more information see: https://numpy.org/doc/stable/reference/generated/numpy.matrix.html\n",
            "  FutureWarning,\n"
          ]
        }
      ],
      "source": [
        "df = pd.read_csv(\"hmdata/articles.csv.zip\")\n",
        "\n",
        "## Find categorical columns\n",
        "ohe_columns = []\n",
        "total = 0\n",
        "\n",
        "for col in df.columns:\n",
        "    if df[col].dtype == \"int64\" and len(df[col].unique()) <= 500:\n",
        "        ohe_columns.append(col)\n",
        "        total += len(df[col].unique())\n",
        "        \n",
        "## Do one hot encoding of the above categorical variables\n",
        "V = pd.get_dummies(df[ohe_columns], columns=ohe_columns).values\n",
        "\n",
        "\n",
        "## Get article features\n",
        "tfidf = TfidfVectorizer(min_df=3)\n",
        "V_desc = tfidf.fit_transform(df[\"detail_desc\"].fillna(\"nodesc\"))\n",
        "\n",
        "## Represent articles as vector of size 512\n",
        "EMB_SIZE = 64\n",
        "V = np.hstack([V.astype(\"float32\"), V_desc.todense()])\n",
        "svd = TruncatedSVD(n_components=EMB_SIZE, random_state=0)\n",
        "svd.fit(V)\n",
        "V = svd.transform(V)\n",
        "\n",
        "np.save(\"articles.npy\", V)"
      ],
      "id": "fb93a7cd-a637-4960-9577-08449a57b55d"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "64a3715e-de70-49d4-b057-e0b674ca65ff"
      },
      "outputs": [],
      "source": [
        "def item_representation_1(path):\n",
        "    df_art = pd.read_csv(path+\"articles.csv.zip\",dtype=art_dtypes)\n",
        "    le = LabelEncoder()\n",
        "    le.fit(df_art[\"index_code\"].unique())\n",
        "    df_art[\"index_code\"] = le.transform(df_art[\"index_code\"])\n",
        "    \n",
        "    dict_vec = {}\n",
        "    vec_art = np.load(\"articles.npy\")\n",
        "    df_vec = pd.concat([df_art[\"article_id\"],pd.DataFrame(vec_art)],axis=1)\n",
        "    for i in range(len(vec_art)):\n",
        "        dict_vec[df_art[\"article_id\"][i]] = vec_art[i]\n",
        "    del vec_art,df_vec\n",
        "    \n",
        "    return df_art, dict_vec\n",
        "    "
      ],
      "id": "64a3715e-de70-49d4-b057-e0b674ca65ff"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7cbe5f64-354c-451e-a9e0-eb114440f8f0"
      },
      "source": [
        "Taken together, the two cells above give us all the features we want to represent articles."
      ],
      "id": "7cbe5f64-354c-451e-a9e0-eb114440f8f0"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "f0c3082e-1da7-466f-8b9f-c777c8ef63cd"
      },
      "source": [
        "Now lets define some functions to extract user representations. The different functions will contain different ways of representing users.\n",
        "\n",
        "We bootstrap by providing a simple set of features to represent users in user_representation_1(). This function returns the dataframe of user features."
      ],
      "id": "f0c3082e-1da7-466f-8b9f-c777c8ef63cd"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "5de63a95-ef6c-4796-8e59-0cb33b9b948e"
      },
      "outputs": [],
      "source": [
        "def user_representation_1(path):\n",
        "    df_cust = pd.read_csv(path+\"customers.csv.zip\",dtype=cust_dtypes)\n",
        "    df_cust[\"age\"] = df_cust[\"age\"].fillna(df_cust[\"age\"].mean())\n",
        "    df_cust[[\"FN\",\"Active\"]] = df_cust[[\"FN\",\"Active\"]].fillna(0)\n",
        "    df_cust[\"club_member_status\"] = df_cust[\"club_member_status\"].apply(lambda x:1 if x == \"ACTIVE\" else 0)\n",
        "    df_cust[\"fashion_news_frequency\"] = df_cust[\"fashion_news_frequency\"].apply(lambda x:0 if x == \"NONE\" else 1)\n",
        "    df_cust = df_cust.drop([\"postal_code\"], axis=1)\n",
        "    return df_cust"
      ],
      "id": "5de63a95-ef6c-4796-8e59-0cb33b9b948e"
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "vHtj09vhRwQS"
      },
      "id": "vHtj09vhRwQS",
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "65dbcef5-701a-4999-b696-3d871ccb485d"
      },
      "outputs": [],
      "source": [
        "def user_representation_2(path):\n",
        "    \"\"\"\n",
        "    TODO -- compute user representations as the average\n",
        "    of the embeddings of the recently purchased articles\n",
        "    return user representation\n",
        "\n",
        "    Hint: You may find pd.DataFrame(item_representation_1()[1]).transpose() useful\n",
        "    \"\"\"\n",
        "    day_start = datetime.datetime(2019,9,23) - datetime.timedelta(days=6)\n",
        "    # print(day_start)\n",
        "    # path = 'hmdata/'\n",
        "    df_trans = pd.read_csv(path+\"transactions_train.csv.zip\",dtype=tran_dtypes)\n",
        "    # df_trans.head()\n",
        "    recentk = 5\n",
        "    collected_transactions = df_trans.query(f\"(t_dat < '{day_start}')\")[['t_dat', 'customer_id', 'article_id']].drop_duplicates().groupby('customer_id').apply(lambda x: x.sort_values('t_dat')['article_id'].tolist()[-recentk:])\n",
        "    collected_transactions = pd.DataFrame(zip(collected_transactions.index, collected_transactions.reset_index(drop=True)), columns=['customer_id', 'article_seq'])\n",
        "    df_art, dict_vec = item_representation_1(path=path)\n",
        "    del df_trans, df_art\n",
        "    gc.collect()\n",
        "    article_vector_sum = 0\n",
        "    for x in dict_vec.values():\n",
        "      article_vector_sum = article_vector_sum + x\n",
        "\n",
        "    avg_article_vector = article_vector_sum/len(dict_vec)\n",
        "\n",
        "    customer_vecs = pd.DataFrame(np.vstack(collected_transactions['article_seq'].apply(lambda x: np.vstack([dict_vec.get(x_, avg_article_vector).reshape(1, -1) for x_ in x]).mean(axis=0).reshape(1, -1)).values), columns=[f'vec_{x}' for x in range(EMB_SIZE)])\n",
        "    customer_vecs['customer_id'] = collected_transactions['customer_id']\n",
        "    del collected_transactions, dict_vec\n",
        "    gc.collect()\n",
        "    return customer_vecs\n",
        "\n",
        "def user_representation_3():\n",
        "    \"\"\"\n",
        "    OPTIONAL -- compute user representations as the output\n",
        "    of the doc2vec model.\n",
        "    https://cs.stanford.edu/~quocle/paragraph_vector.pdf\n",
        "    Doc2vec model is an embedding learning method\n",
        "    that enables us to learn representations of a document.\n",
        "    We treat each user as a document, and the set of articles\n",
        "    the user has purchased as the set of words in the document.\n",
        "    \"\"\"\n",
        "    return None"
      ],
      "id": "65dbcef5-701a-4999-b696-3d871ccb485d"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d39b7430-bf43-4f16-b7a8-a6edbd078e1d"
      },
      "source": [
        "As part of the goal for part B of this week's project, please use the above two functions to implement the two user representation techniques mentioned in the project jumpstart.\n",
        "\n",
        "You can run the rest of the notebook for now, and come back to these functions, implement them and re-run some of the code below and use user_representation_2() (and optionally user_representation_3()) to get the appropriate user features to use to train the model for the downstream task.\n",
        "\n",
        "Lets write a function that would read the transactions data and return the dataframes for the transactions within the dates we want to consider, along with the dataframes for articles features: df_art and dict_vec."
      ],
      "id": "d39b7430-bf43-4f16-b7a8-a6edbd078e1d"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "55c3e4dd-ce84-4199-9215-06490305db3c"
      },
      "outputs": [],
      "source": [
        "path = \"hmdata/\"\n",
        "def read_data(path, day_oldest):\n",
        "    df_trans = pd.read_csv(path+\"transactions_train.csv.zip\",dtype=tran_dtypes)\n",
        "    df_trans[\"t_dat\"] = pd.to_datetime(df_trans[\"t_dat\"],format=\"%Y-%m-%d\")\n",
        "\n",
        "    df_trans = df_trans.query(f\"t_dat >= '{day_oldest}'\").copy()\n",
        "    df_trans = df_trans.drop_duplicates([\"customer_id\",\"article_id\",\"t_dat\"])\n",
        "    df_art,dict_vec = item_representation_1(path)\n",
        "    df_trans = df_trans.merge(df_art[[\"article_id\",\"product_code\",\"product_type_no\",\"graphical_appearance_no\",\"colour_group_code\",\"department_no\",\"index_code\",\"index_group_no\",\"section_no\",\"garment_group_no\"]],how=\"left\",on=\"article_id\")\n",
        "\n",
        "    return df_trans, df_art, dict_vec"
      ],
      "id": "55c3e4dd-ce84-4199-9215-06490305db3c"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4128aa41-0a7c-405c-a2c2-02a3e19678f2"
      },
      "source": [
        "Now we have all the ingredients we need -- we have a basic version of user representations and we have the article representations, and transactions data on which we can train our downstream task.\n",
        "\n",
        "The downstream task we consider is the task of predicting whether or not a user will purchase an article. This is the same task that we have been dealing with in the past 2 weeks.\n",
        "\n",
        "Lets define a train() function that will consider the start and end dates and split data based on these, generate the training data, do random negative sampling and train the model."
      ],
      "id": "4128aa41-0a7c-405c-a2c2-02a3e19678f2"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "5e0c7a4f-8e4d-42f7-b379-1ebc870375d9"
      },
      "outputs": [],
      "source": [
        "def train(user_representation_fn=user_representation_1):\n",
        "    #### Transaction start date say it is from 2019/9/23 and say we take 1 week data\n",
        "    day_start = datetime.datetime(2019,9,23) - datetime.timedelta(days=6)\n",
        "    #### Transaction end date\n",
        "    day_end = datetime.datetime(2019,9,23) - datetime.timedelta(days=0)\n",
        "    \n",
        "    ######## Splitting data based on date ###########################\n",
        "    ####### Train date ###########################################\n",
        "    ## Let's consider the training data for 1 year\n",
        "    day_start_hist = day_start - datetime.timedelta(days=366)\n",
        "    day_end_hist = day_start - datetime.timedelta(days=1)\n",
        "    \n",
        "    df_trans, df_art, dict_vec = read_data(path=\"hmdata/\",day_oldest = datetime.datetime(2018,9,23))\n",
        "\n",
        "    df_cust = user_representation_fn(path='hmdata/')\n",
        "\n",
        "    query_date = f\"((t_dat >= '{day_start}') and (t_dat <= '{day_end}'))\"\n",
        "    top_art_all = df_trans.query(query_date ).groupby(\"article_id\")[\"t_dat\"].count().sort_values(ascending = False).index[:N].tolist()\n",
        "\n",
        "    \n",
        "    \n",
        "    \n",
        "    ############### Create training data #################################################################################\n",
        "    \n",
        "    \n",
        "    list_df_buy = []\n",
        "    list_cust =[]\n",
        "    \n",
        "    # make positive samples\n",
        "    list_df_buy = df_trans.query(f\"(t_dat >= '{day_start}') and (t_dat <= '{day_end}') and (article_id in @top_art_all)\").drop_duplicates([\"customer_id\",\"article_id\"])[[\"customer_id\",\"article_id\"]].copy()\n",
        "    list_df_buy[\"target\"] = 1\n",
        "    list_cust = list_df_buy[\"customer_id\"].unique().tolist()\n",
        "        \n",
        "        \n",
        "    # make negative samples (random selection)\n",
        "    \n",
        "    list_df_nobuy = pd.concat([pd.DataFrame({\"customer_id\":x,\"article_id\":random.sample(top_art_all,nobuy)}) for x in list_cust])\n",
        "    list_df_nobuy[\"target\"] = 0\n",
        "    list_train = pd.concat([list_df_buy,list_df_nobuy]).drop_duplicates([\"customer_id\",\"article_id\"])\n",
        "    del list_df_nobuy\n",
        "\n",
        "    # add feature\n",
        "    df_train = pd.DataFrame()\n",
        "    \n",
        "    ########## Merging item features with the transactions data ###################################################\n",
        "    list_train = list_train.merge(df_art[[\"article_id\",\"product_code\",\"product_type_no\",\"graphical_appearance_no\",\"colour_group_code\",\"department_no\",\"index_code\",\"index_group_no\",\"section_no\",\"garment_group_no\"]],how=\"left\",on=\"article_id\")\n",
        "    \n",
        "    ######### Merging customer data with the above data ######################################\n",
        "    list_train = list_train.merge(df_cust, how=\"left\", on=\"customer_id\")\n",
        "    df_train = df_train.append(list_train)\n",
        "    del list_train\n",
        "    gc.collect()\n",
        "    \n",
        "    \n",
        "    # now that we have all the data in place, lets train the lgbm model\n",
        "\n",
        "    # train lgbm\n",
        "    X_train = df_train.drop([\"customer_id\",\"product_code\",\"product_type_no\",\"department_no\",\"target\"],axis=1)\n",
        "    y_train = df_train[\"target\"]\n",
        "    del df_train\n",
        "    \n",
        "    X_tr, X_va, y_tr, y_va = train_test_split(X_train,y_train,stratify = y_train)\n",
        "    d_tr = lgb.Dataset(X_tr, label=y_tr,  free_raw_data=False)\n",
        "    d_va = lgb.Dataset(X_va, label=y_va,  free_raw_data=False)\n",
        "    lgbm_model = lgb.train(lgb_params, train_set=d_tr, num_boost_round=n_round, valid_sets=[d_tr,d_va], verbose_eval=500, early_stopping_rounds=100)\n",
        "    \n",
        "    # save model\n",
        "    pd.to_pickle(lgbm_model,\"lgbm_model.pkl\")\n",
        "    del X_train, y_train, X_tr, X_va, y_tr, y_va, d_tr, d_va\n",
        "    gc.collect()\n",
        "    del df_trans, df_art, df_cust\n",
        "    gc.collect()\n",
        "    return 0"
      ],
      "id": "5e0c7a4f-8e4d-42f7-b379-1ebc870375d9"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "afb1b72d-7f50-4dc8-a44c-95dcf9c537d2",
        "outputId": "1a4f2741-92a4-4523-ceab-5d666d6ca867"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Training until validation scores don't improve for 100 rounds.\n",
            "[500]\ttraining's auc: 0.809874\tvalid_1's auc: 0.805137\n",
            "[1000]\ttraining's auc: 0.824486\tvalid_1's auc: 0.816103\n",
            "[1500]\ttraining's auc: 0.833124\tvalid_1's auc: 0.821369\n",
            "[2000]\ttraining's auc: 0.839498\tvalid_1's auc: 0.824704\n",
            "Did not meet early stopping. Best iteration is:\n",
            "[2000]\ttraining's auc: 0.839498\tvalid_1's auc: 0.824704\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0"
            ]
          },
          "metadata": {},
          "execution_count": 17
        }
      ],
      "source": [
        "train(user_representation_1)"
      ],
      "id": "afb1b72d-7f50-4dc8-a44c-95dcf9c537d2"
    },
    {
      "cell_type": "code",
      "source": [
        "train(user_representation_2)"
      ],
      "metadata": {
        "id": "uhGiz9vGTD18",
        "outputId": "fefc5579-fb22-41dc-eab0-1470dc45bf49",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "id": "uhGiz9vGTD18",
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Training until validation scores don't improve for 100 rounds.\n",
            "[500]\ttraining's auc: 0.832779\tvalid_1's auc: 0.819536\n",
            "[1000]\ttraining's auc: 0.857439\tvalid_1's auc: 0.832974\n",
            "[1500]\ttraining's auc: 0.875191\tvalid_1's auc: 0.841275\n",
            "[2000]\ttraining's auc: 0.888704\tvalid_1's auc: 0.846595\n",
            "Did not meet early stopping. Best iteration is:\n",
            "[2000]\ttraining's auc: 0.888704\tvalid_1's auc: 0.846595\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0"
            ]
          },
          "metadata": {},
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2a4b63a5-56ee-4bd2-b7b8-2aebb5299b31"
      },
      "source": [
        "We have now trained a light gbm model using user_representation_1() function as the user representation technique. The key goals for part B of this week's project are to implement user_representation_2(), where we represent the user as the average of embeddings of their recently purchased articles.\n"
      ],
      "id": "2a4b63a5-56ee-4bd2-b7b8-2aebb5299b31"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4940f48d-08e5-4130-be2c-d15622012620"
      },
      "source": [
        "Once you have implemented the function, please note to change the line:\n",
        "\n",
        "df_cust = user_representation_1()\n",
        "\n",
        "to the appropriate function name and run re-train the model. Please report the performance numbers with each of the two user representations.\n",
        "\n",
        "This should complete the week 3 project!"
      ],
      "id": "4940f48d-08e5-4130-be2c-d15622012620"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ydLW7dPiuw-E"
      },
      "source": [
        "### Optional task 1: training a Doc2Vec model\n",
        "\n",
        "If you want an extra challenge, you can try implementing Doc2vec representations in user_representation_3(). The Doc2vec model is an embedding learning method\n",
        "    that enables us to learn representations of a document.\n",
        "    We treat each user as a document, and the set of articles\n",
        "    the user has purchased as the set of words in the document."
      ],
      "id": "ydLW7dPiuw-E"
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ce141145-f5af-4f2d-9d94-f4bb50e6208f"
      },
      "source": [
        "### Optional task 2: training a sequential LSTM model\n",
        "\n",
        "Another optional task here would be to implement user_representation_4() where user representations are learnt by a sequential LSTM model. The LSTM model will need to be trained on a task -- the task itself could be the downstream task of predicting whether or not a user would purchase a given article given a sequence of previous articles. The final hidden layer of the lstm model can be used as the user representation."
      ],
      "id": "ce141145-f5af-4f2d-9d94-f4bb50e6208f"
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "88eb3b58-062c-4c96-b3f0-2db4407ce1b3"
      },
      "outputs": [],
      "source": [
        ""
      ],
      "id": "88eb3b58-062c-4c96-b3f0-2db4407ce1b3"
    }
  ],
  "metadata": {
    "accelerator": "GPU",
    "colab": {
      "machine_shape": "hm",
      "name": "week3-ann-user-representations-submission.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "environment": {
      "kernel": "python3",
      "name": "tf2-gpu.2-6.m89",
      "type": "gcloud",
      "uri": "gcr.io/deeplearning-platform-release/tf2-gpu.2-6:m89"
    },
    "gpuClass": "standard",
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.12"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}