{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Introduction\n\nHi, I'm George and based on this fantastic [notebook](https://www.kaggle.com/debarshichanda/understanding-mean-average-precision) I'll try to **optimize** \nthe **Mean Average Precision @ K**\n\n**Please feel free to comment and/or upvote!**\n\nCheers!\n\n\n## TLDR\n- Two optimization versions are proposed in order to calculate the MAP@K.\n- The baseline approach can be found below and in the original notebook.\n\n#### The execution times of the three versions can be found in the next table. \n\n\n| **Sample Size**  | **Baseline (V1) Time** | **V2 Time** | **V3 Time** |\n|--------------------------|------------------------|-------------|-------------|\n| 1.000                    | 463 ms                 | 43.9 ms     | 21 ms       |\n| 10.000                   | 4.53 sec               | 430 ms      | 210 ms      |\n| 100.000                  | 46.5 sec               | 4.35 sec    | 2.1 sec     |\n\n\n\n## Baseline\n**At first I'll try to execute the code in the aforementioned notebook to set a baseline.**\n\n**The following snippets were taken directly from there.**","metadata":{}},{"cell_type":"code","source":"import numpy as np\n\ndef precision_at_k_v1(y_true, y_pred, k=12):\n    \"\"\" Computes Precision at k for one sample\n    \n    Parameters\n    __________\n    y_true: np.array\n            Array of correct recommendations (Order doesn't matter)\n    y_pred: np.array\n            Array of predicted recommendations (Order does matter)\n    k: int, optional\n       Maximum number of predicted recommendations\n            \n    Returns\n    _______\n    score: double\n           Precision at k\n    \"\"\"\n    intersection = np.intersect1d(y_true, y_pred[:k])\n    return len(intersection) / k\n\n\ndef rel_at_k_v1(y_true, y_pred, k=12):\n    \"\"\" Computes Relevance at k for one sample\n    \n    Parameters\n    __________\n    y_true: np.array\n            Array of correct recommendations (Order doesn't matter)\n    y_pred: np.array\n            Array of predicted recommendations (Order does matter)\n    k: int, optional\n       Maximum number of predicted recommendations\n            \n    Returns\n    _______\n    score: double\n           Relevance at k\n    \"\"\"\n    if y_pred[k-1] in y_true:\n        return 1\n    else:\n        return 0\n    \ndef average_precision_at_k_v1(y_true, y_pred, k=12):\n    \"\"\" Computes Average Precision at k for one sample\n    \n    Parameters\n    __________\n    y_true: np.array\n            Array of correct recommendations (Order doesn't matter)\n    y_pred: np.array\n            Array of predicted recommendations (Order does matter)\n    k: int, optional\n       Maximum number of predicted recommendations\n            \n    Returns\n    _______\n    score: double\n           Average Precision at k\n    \"\"\"\n    ap = 0.0\n    for i in range(1, k+1):\n        ap += precision_at_k_v1(y_true, y_pred, i) * rel_at_k_v1(y_true, y_pred, i)\n        \n    return ap / min(k, len(y_true))\n\ndef mean_average_precision_v1(y_true, y_pred, k=12):\n    \"\"\" Computes MAP at k\n    \n    Parameters\n    __________\n    y_true: np.array\n            2D Array of correct recommendations (Order doesn't matter)\n    y_pred: np.array\n            2D Array of predicted recommendations (Order does matter)\n    k: int, optional\n       Maximum number of predicted recommendations\n            \n    Returns\n    _______\n    score: double\n           MAP at k\n    \"\"\"\n    return np.mean([average_precision_at_k_v1(gt, pred, k) for gt, pred in zip(y_true, y_pred)])","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:05:09.858719Z","iopub.execute_input":"2022-02-23T19:05:09.859286Z","iopub.status.idle":"2022-02-23T19:05:09.875696Z","shell.execute_reply.started":"2022-02-23T19:05:09.859191Z","shell.execute_reply":"2022-02-23T19:05:09.874891Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Baseline Execution","metadata":{}},{"cell_type":"code","source":"gtruth = np.array(['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l', 'm'])\npreds =  np.array(['a', 'f', 'c', 'g', 'b', 'k', 'o', 'n', 'x', 'l', 'q', 'i'])","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:05:09.877356Z","iopub.execute_input":"2022-02-23T19:05:09.878346Z","iopub.status.idle":"2022-02-23T19:05:09.891857Z","shell.execute_reply.started":"2022-02-23T19:05:09.878287Z","shell.execute_reply":"2022-02-23T19:05:09.890745Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct a \"large\" dataset \nn_samples = 1_000\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:05:09.893502Z","iopub.execute_input":"2022-02-23T19:05:09.894286Z","iopub.status.idle":"2022-02-23T19:05:09.907923Z","shell.execute_reply.started":"2022-02-23T19:05:09.894237Z","shell.execute_reply":"2022-02-23T19:05:09.907022Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Baseline Benchmark @ 1.000\n\n%timeit mean_average_precision_v1(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:05:09.910782Z","iopub.execute_input":"2022-02-23T19:05:09.911536Z","iopub.status.idle":"2022-02-23T19:05:13.606520Z","shell.execute_reply.started":"2022-02-23T19:05:09.911493Z","shell.execute_reply":"2022-02-23T19:05:13.605467Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct a \"larger\" dataset \nn_samples = 10_000\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:05:13.607948Z","iopub.execute_input":"2022-02-23T19:05:13.608266Z","iopub.status.idle":"2022-02-23T19:05:13.616514Z","shell.execute_reply.started":"2022-02-23T19:05:13.608223Z","shell.execute_reply":"2022-02-23T19:05:13.615220Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Baseline Benchmark @ 10.000\n%timeit mean_average_precision_v1(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:05:13.618037Z","iopub.execute_input":"2022-02-23T19:05:13.618358Z","iopub.status.idle":"2022-02-23T19:05:50.540922Z","shell.execute_reply.started":"2022-02-23T19:05:13.618314Z","shell.execute_reply":"2022-02-23T19:05:50.539962Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct an even \"larger\" dataset \nn_samples = 100_000\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:05:50.542155Z","iopub.execute_input":"2022-02-23T19:05:50.542403Z","iopub.status.idle":"2022-02-23T19:05:50.550494Z","shell.execute_reply.started":"2022-02-23T19:05:50.542373Z","shell.execute_reply":"2022-02-23T19:05:50.549557Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Baseline Benchmark @ 100.000\n\n%timeit mean_average_precision_v1(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:05:50.552306Z","iopub.execute_input":"2022-02-23T19:05:50.552584Z","iopub.status.idle":"2022-02-23T19:12:03.146265Z","shell.execute_reply.started":"2022-02-23T19:05:50.552552Z","shell.execute_reply":"2022-02-23T19:12:03.145277Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Let's make it faster!","metadata":{}},{"cell_type":"markdown","source":"### At first we will work with our initial 2 vectors and go step by step","metadata":{}},{"cell_type":"code","source":"print(gtruth)\nprint(preds)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.147479Z","iopub.execute_input":"2022-02-23T19:12:03.147753Z","iopub.status.idle":"2022-02-23T19:12:03.153259Z","shell.execute_reply.started":"2022-02-23T19:12:03.147720Z","shell.execute_reply":"2022-02-23T19:12:03.152651Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Let's now say that we want to calculate @K\n# The first thing to do is to take the K first items from the recommended items (ranking)\nK = 12\ny_pred = preds[:K]\ny_pred","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.154342Z","iopub.execute_input":"2022-02-23T19:12:03.155179Z","iopub.status.idle":"2022-02-23T19:12:03.170482Z","shell.execute_reply.started":"2022-02-23T19:12:03.155117Z","shell.execute_reply":"2022-02-23T19:12:03.169511Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Using the function np.intersect1d you can the intersected items between the 2 vectors\nprint(np.intersect1d(gtruth, y_pred))","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.172187Z","iopub.execute_input":"2022-02-23T19:12:03.172862Z","iopub.status.idle":"2022-02-23T19:12:03.182255Z","shell.execute_reply.started":"2022-02-23T19:12:03.172813Z","shell.execute_reply":"2022-02-23T19:12:03.181221Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"**BUT** if you check the documentation about [np.intersect1d](https://numpy.org/doc/stable/reference/generated/numpy.intersect1d.html) you may \ndiscover two other parameters:\n- assume_unique=True\n- return_indices=True","metadata":{}},{"cell_type":"code","source":"# 3 things are returned here\n# - The common items between the two vectors\n# - The indexes of the common items in the first vector (truth vector)\n# - The indexes of the common items in the second vector (ranking/recommendations vector)\nnp.intersect1d(gtruth, y_pred, assume_unique=True, return_indices=True)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.183599Z","iopub.execute_input":"2022-02-23T19:12:03.183905Z","iopub.status.idle":"2022-02-23T19:12:03.196411Z","shell.execute_reply.started":"2022-02-23T19:12:03.183862Z","shell.execute_reply":"2022-02-23T19:12:03.195440Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# We will only need the indexes for the ranking vector\n_, _, pred_indexes = np.intersect1d(gtruth, y_pred, assume_unique=True, return_indices=True)\n\npred_indexes","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.199943Z","iopub.execute_input":"2022-02-23T19:12:03.200221Z","iopub.status.idle":"2022-02-23T19:12:03.211919Z","shell.execute_reply.started":"2022-02-23T19:12:03.200190Z","shell.execute_reply":"2022-02-23T19:12:03.210999Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We cannot use this vector as it is. We'll transform it in a way that it will be a bit more intuitive\n\n- We will create a mask for these positions by instantiating a vector with Os\n- and then fill the indexes from the aforementioned vector with 1s. ","metadata":{"execution":{"iopub.status.busy":"2022-02-16T19:49:24.536548Z","iopub.execute_input":"2022-02-16T19:49:24.537176Z","iopub.status.idle":"2022-02-16T19:49:24.539798Z","shell.execute_reply.started":"2022-02-16T19:49:24.537143Z","shell.execute_reply":"2022-02-16T19:49:24.539237Z"}}},{"cell_type":"code","source":"x = np.zeros(len(y_pred), dtype=int)\nx[pred_indexes] = 1\n\nx","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.213004Z","iopub.execute_input":"2022-02-23T19:12:03.213782Z","iopub.status.idle":"2022-02-23T19:12:03.223432Z","shell.execute_reply.started":"2022-02-23T19:12:03.213749Z","shell.execute_reply":"2022-02-23T19:12:03.222717Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"#### If you think it through the aforementioned calculation provides the **Relevance @ K** vector\n\nSo let's re-write it with a  more readable naming convention","metadata":{}},{"cell_type":"code","source":"rel_at_k = np.zeros(len(y_pred), dtype=int)\nrel_at_k[pred_indexes] = 1","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.224870Z","iopub.execute_input":"2022-02-23T19:12:03.225651Z","iopub.status.idle":"2022-02-23T19:12:03.234560Z","shell.execute_reply.started":"2022-02-23T19:12:03.225576Z","shell.execute_reply":"2022-02-23T19:12:03.233867Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### The next step is to try to calculate the precision at each K up to 12. \n\nTo do that we need to count **how many common items** we have **at each step**.\n\nThis can be easily calculated by calculating **the Cumulative Sum over the Relative@K Vector**\n\n\nLet's check:","metadata":{"execution":{"iopub.status.busy":"2022-02-16T19:57:21.115247Z","iopub.execute_input":"2022-02-16T19:57:21.115711Z","iopub.status.idle":"2022-02-16T19:57:21.121221Z","shell.execute_reply.started":"2022-02-16T19:57:21.115667Z","shell.execute_reply":"2022-02-16T19:57:21.120037Z"}}},{"cell_type":"code","source":"# As you may see, the second row shows the number of intersected items \n# with our ground truth vector at each step K (index)\n\n# initial Relative@K vector\nprint(rel_at_k)\n\n# The cumulative of the Relative@K vector\nprint(rel_at_k.cumsum())","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.235986Z","iopub.execute_input":"2022-02-23T19:12:03.236548Z","iopub.status.idle":"2022-02-23T19:12:03.248012Z","shell.execute_reply.started":"2022-02-23T19:12:03.236510Z","shell.execute_reply":"2022-02-23T19:12:03.247114Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# We assign the instesection counts to this variable\nintersection_count_at_k = rel_at_k.cumsum()","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.249373Z","iopub.execute_input":"2022-02-23T19:12:03.250054Z","iopub.status.idle":"2022-02-23T19:12:03.259730Z","shell.execute_reply.started":"2022-02-23T19:12:03.250015Z","shell.execute_reply":"2022-02-23T19:12:03.258678Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Having the **Intersection Counts**, and the **Relative Scores** at each K, all we need\nis to compute the actual **Precision** at each K\n\nTo do this we'll need the denominator for each step.\n\nThis can be obtained by creating a vector being [1...12]","metadata":{}},{"cell_type":"code","source":"ranks = np.arange(1, len(y_pred) + 1, 1)\nranks","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.261098Z","iopub.execute_input":"2022-02-23T19:12:03.261437Z","iopub.status.idle":"2022-02-23T19:12:03.275417Z","shell.execute_reply.started":"2022-02-23T19:12:03.261399Z","shell.execute_reply":"2022-02-23T19:12:03.274417Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Now we divide the Intersection Counts with the Ranks to obtain\n# the Precision@K\nprecisions_at_k = intersection_count_at_k / ranks\nprecisions_at_k","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.277164Z","iopub.execute_input":"2022-02-23T19:12:03.277482Z","iopub.status.idle":"2022-02-23T19:12:03.289789Z","shell.execute_reply.started":"2022-02-23T19:12:03.277440Z","shell.execute_reply":"2022-02-23T19:12:03.288448Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# As a next step we will need to multiply the Precision@K with the Relevance@K.\n\n# This will zero out the positions where we did not have a matching item\nprecisions_at_k = precisions_at_k * rel_at_k\nprecisions_at_k","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.291666Z","iopub.execute_input":"2022-02-23T19:12:03.292034Z","iopub.status.idle":"2022-02-23T19:12:03.301639Z","shell.execute_reply.started":"2022-02-23T19:12:03.291986Z","shell.execute_reply":"2022-02-23T19:12:03.300858Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### As a final step in order to calculate the **Average Precision @K** we need to take the average of the **precisions_at_k** variable","metadata":{"execution":{"iopub.status.busy":"2022-02-16T21:32:24.447951Z","iopub.execute_input":"2022-02-16T21:32:24.448642Z","iopub.status.idle":"2022-02-16T21:32:24.453501Z","shell.execute_reply.started":"2022-02-16T21:32:24.448604Z","shell.execute_reply":"2022-02-16T21:32:24.452307Z"}}},{"cell_type":"code","source":"avg_precision_at_k = precisions_at_k.mean()\n\navg_precision_at_k","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.302995Z","iopub.execute_input":"2022-02-23T19:12:03.303843Z","iopub.status.idle":"2022-02-23T19:12:03.316654Z","shell.execute_reply.started":"2022-02-23T19:12:03.303799Z","shell.execute_reply":"2022-02-23T19:12:03.315728Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Mean Average Precision at K (MAP@K)\n\nHaving calculated the Average Precision @ K for a single (ground truth, recommendations) pair, all we have to do is to **loop over all the other pairs** and **compute the final average step**\n\nSince this is rather simple to show it step by step, I'll simply write the two two functions that calculate\n- avg_precision_at_k\n- mean_average_precision (@K)","metadata":{"execution":{"iopub.status.busy":"2022-02-16T21:34:59.561946Z","iopub.execute_input":"2022-02-16T21:34:59.56226Z","iopub.status.idle":"2022-02-16T21:34:59.566873Z","shell.execute_reply.started":"2022-02-16T21:34:59.562226Z","shell.execute_reply":"2022-02-16T21:34:59.5657Z"}}},{"cell_type":"code","source":"def avg_precision_at_k_v2(y_true, y_pred, max_k=12, adjust_with_rel=True):\n    \"\"\"\n    Computes the Average Precision at K in a more efficient way\n\n    Parameters\n    ----------\n    y_true: np.array\n        Array of correct recommendations (Order doesn't matter)\n    y_pred: np.array\n        Array of predicted recommendations (Order does matter)\n    max_k: int, optional\n        Maximum number of predicted recommendations\n    adjust_with_rel: bool\n        Whether you want to multiplicate the precisions with the Rel@K\n        \n    Returns\n    _______\n    score: float\n        Precision at k\n    \"\"\"\n    y_pred = y_pred[:max_k]\n\n    _, _, pred_indexes = np.intersect1d(\n        y_true, y_pred, assume_unique=True, return_indices=True)\n\n    rel_at_k = np.zeros(len(y_pred), dtype=int)\n    rel_at_k[pred_indexes] = 1\n\n    intersection_count_at_k = rel_at_k.cumsum()\n    ranks = np.arange(1, len(y_pred) + 1, 1)\n    precisions_at_k = intersection_count_at_k / ranks\n\n    if adjust_with_rel:\n        precisions_at_k = precisions_at_k * rel_at_k\n\n    return precisions_at_k.mean()\n\ndef mean_average_precision_v2(y_true, y_pred, k=12):\n    \"\"\"\n    Computes the Mean Average Precision @K (MAP@K) in a more\n    efficient way\n\n    Returns\n    -------\n\n    \"\"\"\n    scores = []\n    \n    \n    for gt, pred in zip(y_true, y_pred):\n        scores.append(avg_precision_at_k_v2(gt, pred, k))\n\n    return np.mean(scores)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.318140Z","iopub.execute_input":"2022-02-23T19:12:03.318574Z","iopub.status.idle":"2022-02-23T19:12:03.330486Z","shell.execute_reply.started":"2022-02-23T19:12:03.318529Z","shell.execute_reply":"2022-02-23T19:12:03.329685Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct a \"large\" dataset \nn_samples = 1_000\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.332199Z","iopub.execute_input":"2022-02-23T19:12:03.332438Z","iopub.status.idle":"2022-02-23T19:12:03.347768Z","shell.execute_reply.started":"2022-02-23T19:12:03.332407Z","shell.execute_reply":"2022-02-23T19:12:03.346937Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# V2 Benchmark @ 1.000\n\n# The V1 benchmark at 1.000 pairs is: 479 ms ± 17.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n\n%timeit mean_average_precision_v2(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:03.348956Z","iopub.execute_input":"2022-02-23T19:12:03.350019Z","iopub.status.idle":"2022-02-23T19:12:06.981237Z","shell.execute_reply.started":"2022-02-23T19:12:03.349981Z","shell.execute_reply":"2022-02-23T19:12:06.980417Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct a \"larger\" dataset \nn_samples = 10_000\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:06.982722Z","iopub.execute_input":"2022-02-23T19:12:06.983330Z","iopub.status.idle":"2022-02-23T19:12:06.991745Z","shell.execute_reply.started":"2022-02-23T19:12:06.983280Z","shell.execute_reply":"2022-02-23T19:12:06.990697Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# V2 Benchmark @ 10.000\n\n# The V1 benchmark at 10.000 pairs is: 4.44 s ± 49.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n\n%timeit mean_average_precision_v2(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:06.993346Z","iopub.execute_input":"2022-02-23T19:12:06.993691Z","iopub.status.idle":"2022-02-23T19:12:10.541201Z","shell.execute_reply.started":"2022-02-23T19:12:06.993647Z","shell.execute_reply":"2022-02-23T19:12:10.540119Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct an even \"larger\" dataset \nn_samples = 100_000\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:10.542962Z","iopub.execute_input":"2022-02-23T19:12:10.543278Z","iopub.status.idle":"2022-02-23T19:12:10.551864Z","shell.execute_reply.started":"2022-02-23T19:12:10.543236Z","shell.execute_reply":"2022-02-23T19:12:10.550861Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Current Benchmark @ 100.000 items\n\n# The baseline benchmark at 100.000 pairs is: 44.5 s ± 1.14 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n\n%timeit mean_average_precision_v2(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:10.553339Z","iopub.execute_input":"2022-02-23T19:12:10.553581Z","iopub.status.idle":"2022-02-23T19:12:46.269505Z","shell.execute_reply.started":"2022-02-23T19:12:10.553553Z","shell.execute_reply":"2022-02-23T19:12:46.268569Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Are the Two implementations (baseline & V2) the same?","metadata":{}},{"cell_type":"markdown","source":"### Let's check the Average Precision At K implementations","metadata":{"execution":{"iopub.status.busy":"2022-02-16T22:05:15.50827Z","iopub.execute_input":"2022-02-16T22:05:15.508712Z","iopub.status.idle":"2022-02-16T22:05:15.512395Z","shell.execute_reply.started":"2022-02-16T22:05:15.508653Z","shell.execute_reply":"2022-02-16T22:05:15.511645Z"}}},{"cell_type":"code","source":"gtruth = np.array(['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l', 'm'])\npreds =  np.array(['a', 'f', 'c', 'g', 'b', 'k', 'o', 'n', 'x', 'l', 'q', 'i'])\ngtruth.shape","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:46.271004Z","iopub.execute_input":"2022-02-23T19:12:46.271310Z","iopub.status.idle":"2022-02-23T19:12:46.279768Z","shell.execute_reply.started":"2022-02-23T19:12:46.271271Z","shell.execute_reply":"2022-02-23T19:12:46.278870Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"for i in range(1, 13):\n    baseline = average_precision_at_k_v1(gtruth, preds, k=i)\n    v2 = avg_precision_at_k_v2(gtruth, preds, max_k=i)\n    \n    print(f'Avg Precision @ {i} | Baseline (v1): {baseline} | V2: {v2} | Are equal: {baseline==v2}')\n    assert baseline == v2\n\n# So, it seems that the two implementations fetch the same results","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:46.281277Z","iopub.execute_input":"2022-02-23T19:12:46.281695Z","iopub.status.idle":"2022-02-23T19:12:46.298935Z","shell.execute_reply.started":"2022-02-23T19:12:46.281652Z","shell.execute_reply":"2022-02-23T19:12:46.297877Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Let's check the MAP@K implementations","metadata":{}},{"cell_type":"code","source":"# Construct a dataset \nn_samples = 10\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:46.300720Z","iopub.execute_input":"2022-02-23T19:12:46.300941Z","iopub.status.idle":"2022-02-23T19:12:46.308868Z","shell.execute_reply.started":"2022-02-23T19:12:46.300915Z","shell.execute_reply":"2022-02-23T19:12:46.307901Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"for i in range(1, 13):\n    baseline = mean_average_precision_v1(y_true, y_pred, k=i)\n    v2 = mean_average_precision_v2(y_true, y_pred, k=i)\n\n    print(f'MAP @ {i} | Baseline (v1): {baseline} | V2: {v2} | Are equal: {baseline==v2}')\n    assert baseline == v2\n\n# So, it seems that the two implementations for MAP@K fetch the same results","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:46.310384Z","iopub.execute_input":"2022-02-23T19:12:46.310820Z","iopub.status.idle":"2022-02-23T19:12:46.362636Z","shell.execute_reply.started":"2022-02-23T19:12:46.310776Z","shell.execute_reply":"2022-02-23T19:12:46.361706Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# V3 Implementation!\n\nThis implementation tries to beat V2 by taking into account **1 critical assumption**.\n\nThe assumption is that the **number of recommendations for all samples is the same**","metadata":{}},{"cell_type":"code","source":"def mean_average_precision_v3(y_true, y_pred, k=12):\n    \n    # compute the Rel@K for all items     \n    rel_at_k = np.zeros((len(y_true), k), dtype=int)\n    \n    # collect the intersection indexes (for the ranking vector) for all pairs\n    for idx, (truth, pred) in enumerate(zip(y_true, y_pred)):\n        _, _, inter_idxs = np.intersect1d(truth, pred[:k], assume_unique=True, return_indices=True)         \n        rel_at_k[idx, inter_idxs] = 1\n    \n    # Calculate the intersection counts for all pairs     \n    intersection_count_at_k = rel_at_k.cumsum(axis=1)\n    \n    # we have the same denominator for all ranking vectors     \n    ranks = np.arange(1, k + 1, 1)\n    \n    # Calculating the Precision@K for all Ks for all pairs     \n    precisions_at_k = intersection_count_at_k / ranks\n    # Multiply with the Rel@K for all pairs     \n    precisions_at_k = precisions_at_k * rel_at_k\n\n    # Calculate the average precisions @ K for all pairs\n    average_precisions_at_k = precisions_at_k.mean(axis=1)\n    \n    # calculate the final MAP@K\n    map_at_k = average_precisions_at_k.mean()\n\n    return map_at_k","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:46.364010Z","iopub.execute_input":"2022-02-23T19:12:46.364244Z","iopub.status.idle":"2022-02-23T19:12:46.373135Z","shell.execute_reply.started":"2022-02-23T19:12:46.364216Z","shell.execute_reply":"2022-02-23T19:12:46.372353Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct a \"large\" dataset \nn_samples = 1_000\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:46.374500Z","iopub.execute_input":"2022-02-23T19:12:46.374776Z","iopub.status.idle":"2022-02-23T19:12:46.393230Z","shell.execute_reply.started":"2022-02-23T19:12:46.374746Z","shell.execute_reply":"2022-02-23T19:12:46.392326Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# V3 Benchmark @ 1.000\n\n# V1 benchmark at 1.000 pairs is: 479 ms ± 17.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) (baseline)\n# V2 benchmark at 1.000 pairs is: 29.6 ms ± 617 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n%timeit mean_average_precision_v3(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:46.394871Z","iopub.execute_input":"2022-02-23T19:12:46.395860Z","iopub.status.idle":"2022-02-23T19:12:48.195221Z","shell.execute_reply.started":"2022-02-23T19:12:46.395823Z","shell.execute_reply":"2022-02-23T19:12:48.194361Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct a \"larger\" dataset \nn_samples = 10_000\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:48.196464Z","iopub.execute_input":"2022-02-23T19:12:48.196721Z","iopub.status.idle":"2022-02-23T19:12:48.204455Z","shell.execute_reply.started":"2022-02-23T19:12:48.196689Z","shell.execute_reply":"2022-02-23T19:12:48.203561Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# V3 Benchmark @ 10.000\n\n# V1 benchmark at 10.000 pairs is: 4.44 s ± 49.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n# V2 benchmark at 10.000 pairs is: 329 ms ± 52.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n%timeit mean_average_precision_v3(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:48.206852Z","iopub.execute_input":"2022-02-23T19:12:48.207204Z","iopub.status.idle":"2022-02-23T19:12:49.956010Z","shell.execute_reply.started":"2022-02-23T19:12:48.207158Z","shell.execute_reply":"2022-02-23T19:12:49.955093Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# Construct an even \"larger\" dataset \nn_samples = 100_000\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:49.957728Z","iopub.execute_input":"2022-02-23T19:12:49.958039Z","iopub.status.idle":"2022-02-23T19:12:49.967096Z","shell.execute_reply.started":"2022-02-23T19:12:49.957996Z","shell.execute_reply":"2022-02-23T19:12:49.966113Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# V3 Benchmark @ 100.000 items\n\n# V1 benchmark at 100.000 pairs is: 44.5 s ± 1.14 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n# V2 benchmark at 100.000 pairs is: 3.15 s ± 388 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n%timeit mean_average_precision_v3(y_true, y_pred, k=12)","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:12:49.968476Z","iopub.execute_input":"2022-02-23T19:12:49.968727Z","iopub.status.idle":"2022-02-23T19:13:07.384659Z","shell.execute_reply.started":"2022-02-23T19:12:49.968692Z","shell.execute_reply":"2022-02-23T19:13:07.383624Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"\n","metadata":{}},{"cell_type":"code","source":"# Finally we check whether V1, V2 and V3 have the same results\n\n# Construct a dataset \nn_samples = 10\n\ny_true = [gtruth] * n_samples\ny_pred = [preds] * n_samples\n\nlen(y_true), len(y_pred)\n\nfor i in range(1, 13):\n    baseline = mean_average_precision_v1(y_true, y_pred, k=i)\n    v2 = mean_average_precision_v2(y_true, y_pred, k=i)\n    v3 = mean_average_precision_v3(y_true, y_pred, k=i)\n    \n    print(f'MAP @ {i} | Baseline (v1): {baseline} | V2: {v2}  | V3: {v3} | Are equal: {baseline==v2}, {baseline==v3}')\n    assert baseline == v2\n    assert baseline == v3\n\n# So, it seems that the two implementations for MAP@K fetch the same results","metadata":{"execution":{"iopub.status.busy":"2022-02-23T19:13:07.388948Z","iopub.execute_input":"2022-02-23T19:13:07.389241Z","iopub.status.idle":"2022-02-23T19:13:07.445886Z","shell.execute_reply.started":"2022-02-23T19:13:07.389205Z","shell.execute_reply":"2022-02-23T19:13:07.444863Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Thank you for your time!\n\n### Feel free to comment and/or upvote!","metadata":{}}]}