{"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":"# Understanding the Evaluation Metric\nThis notebook will follow the structure of [this great notebook](https://www.kaggle.com/pestipeti/explanation-of-map5-scoring-metric)","metadata":{}},{"cell_type":"markdown","source":"# Mean Average Precision (MAP)\nSubmissions are evaluated according to the Mean Average Precision @ 12 (MAP@12):\n\n$$MAP@12 = {1 \\over U} \\sum_{u=1}^{U} \\sum_{k=1}^{min(n,12)}P(k) \\times rel(k)$$\n\nwhere `U` is the number of images, `P(k)` is the precision at cutoff `k`, `rel(k)` is an indicator function equaling 1 if the item at rank `k` is a relevant (correct) label, zero otherwise and `n` is the number of predictions per image. <br>\nWe will slowly build towards the final function, bit by bit","metadata":{}},{"cell_type":"code","source":"import numpy as np\n\ngt = np.array(['a', 'b', 'c', 'd', 'e'])\n\npreds1 = np.array(['b', 'c', 'a', 'd', 'e'])\npreds2 = np.array(['a', 'b', 'c', 'd', 'e'])\npreds3 = np.array(['f', 'b', 'c', 'd', 'e'])\npreds4 = np.array(['a', 'f', 'e', 'g', 'b'])\npreds5 = np.array(['a', 'f', 'c', 'g', 'b'])\npreds6 = np.array(['d', 'c', 'b', 'a', 'e'])","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:18.955977Z","iopub.execute_input":"2022-02-08T15:25:18.956336Z","iopub.status.idle":"2022-02-08T15:25:18.988242Z","shell.execute_reply.started":"2022-02-08T15:25:18.956239Z","shell.execute_reply":"2022-02-08T15:25:18.987468Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Precision","metadata":{}},{"cell_type":"markdown","source":"Precision is the Positive Predictive Rate. In case of classification, precision is the number of True positives(i.e. the positive predictions by model that are actually positive) divided by all the positive predictions by the model (i.e. the sum of True positives and False positives)\n\n$$ P = { \\#\\ of\\ correct\\ predictions\\over \\#\\ of\\ all\\ predictions  } = {TP \\over (TP + FP)}$$\n\n<br>\nIn case of Information Retrieval, Precision is the fraction of the documents retrieved that are relevant to the user\n\n$${\\displaystyle {\\text{P}}={\\frac {|\\{{\\text{relevant documents}}\\}\\cap \\{{\\text{retrieved documents}}\\}|}{|\\{{\\text{retrieved documents}}\\}|}}}$$","metadata":{}},{"cell_type":"markdown","source":"# Precision at K","metadata":{}},{"cell_type":"markdown","source":"Precision at cutoff `k`, `P(k)`, is simply the precision calculated by considering only the subset of your predictions from rank 1 through `k`. <br>\nFor calculating this we take the top k recommendations and find it's precision with the ground truth.<br>\nExample 1:\nIf `gt=[a,b,c,d,e]` and `pred=[b,c,a,d,e]` then for `P@1` we only take the first recommendation from `pred` i.e.`b` and find it's `precision` with the `gt`. \n$${\\displaystyle {\\text{P}}={\\frac {|\\{{\\text{gt}}\\}\\cap \\{{\\text{pred[:1]}}\\}|}{|\\{{\\text{pred[:1]}}\\}|}}={\\frac {\\text{1}}{\\text{1}}}}$$ \n<br>\nExample 2:\nIf `gt=[a,b,c,d,e]` and `pred=[f,b,c,d,e]` then for `P@1` we only take the first recommendation from `pred` i.e.`f` and find it's `precision` with the `gt`. \n$${\\displaystyle {\\text{P}}={\\frac {|\\{{\\text{gt}}\\}\\cap \\{{\\text{pred[:1]}}\\}|}{|\\{{\\text{pred[:1]}}\\}|}}={\\frac {\\text{0}}{\\text{1}}}}$$\n<br>\nExample 3:\nIf `gt=[a,b,c,d,e]` and `pred=[a,f,e,g,b]` then for `P@2` we only take the top 2 recommendations from `pred` i.e.`[a,f]` and find it's `precision` with the `gt`. Intersection between the two sets is `1` since only `a` is present in the `gt`\n$${\\displaystyle {\\text{P}}={\\frac {|\\{{\\text{gt}}\\}\\cap \\{{\\text{pred[:2]}}\\}|}{|\\{{\\text{pred[:2]}}\\}|}}={\\frac {\\text{1}}{\\text{2}}}}$$\n<br>\n\nSome more Examples:\n\n| true  | predicted   | k  | P(k) |\n|:-:|:-:|:-:|:-:|\n| [a, b, c, d, e]  | [b, c, a, d, e]   | 1  | 1.0  |\n| [a, b, c, d, e]  | [a, b, c, d, e]   | 1  | 1.0  |\n| [a, b, c, d, e]  | [f, b, c, d, e]   | 1  | 0.0  |\n| [a, b, c, d, e]  | [a, f, e, g, b]   | 2  | $$1\\over2$$  |\n| [a, b, c, d, e]  | [a, f, c, g, b]   | 3  | $$2\\over3$$  |\n| [a, b, c, d, e]  | [d, c, b, a, e]   | 3  | $$3\\over3$$  |","metadata":{}},{"cell_type":"code","source":"def precision_at_k(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","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:18.989908Z","iopub.execute_input":"2022-02-08T15:25:18.990151Z","iopub.status.idle":"2022-02-08T15:25:18.996212Z","shell.execute_reply.started":"2022-02-08T15:25:18.990123Z","shell.execute_reply":"2022-02-08T15:25:18.995099Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"assert precision_at_k(gt, preds1, k=1) == 1.0\nassert precision_at_k(gt, preds2, k=1) == 1.0\nassert precision_at_k(gt, preds3, k=1) == 0.0\nassert precision_at_k(gt, preds4, k=2) == 1/2\nassert precision_at_k(gt, preds5, k=3) == 2/3\nassert precision_at_k(gt, preds6, k=3) == 3/3","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:18.997616Z","iopub.execute_input":"2022-02-08T15:25:18.997983Z","iopub.status.idle":"2022-02-08T15:25:19.012065Z","shell.execute_reply.started":"2022-02-08T15:25:18.997948Z","shell.execute_reply":"2022-02-08T15:25:19.010942Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Rel at K","metadata":{}},{"cell_type":"markdown","source":"`Rel(k)` is an indicator function equaling 1 if the item at rank k is a relevant (correct) label, zero otherwise.<br>\nExample 1:\nIf `gt=[a,b,c,d,e]` and `pred=[b,c,a,d,e]` then for `rel@1` we only take the first recommendation from `pred` i.e.`b` and check if it's relevant i.e. present in `gt`.\n$${\\displaystyle {\\text{rel(k)}}=1.0}$$\n<br>\nExample 2:\nIf `gt=[a,b,c,d,e]` and `pred=[f,b,c,d,e]` then for `rel@1` we only take the first recommendation from `pred` i.e.`f` and check if it's relevant i.e. present in `gt`.\n$${\\displaystyle {\\text{rel(k)}}=0.0}$$\n<br>\nExample 3:\nIf `gt=[a,b,c,d,e]` and `pred=[a,f,e,g,b]` then for `rel@2` we only take the second recommendation from `pred` i.e.`f` and check if it's relevant i.e. present in `gt`.\n$${\\displaystyle {\\text{rel(k)}}=0.0}$$\n<br>\n\nSome more Examples:\n\n| true  | predicted   | k  | rel(k) |\n|:-:|:-:|:-:|:-:|\n| [a, b, c, d, e]  | [b, c, a, d, e]   | 1  | 1.0  |\n| [a, b, c, d, e]  | [a, b, c, d, e]   | 1  | 1.0  |\n| [a, b, c, d, e]  | [f, b, c, d, e]   | 1  | 0.0  |\n| [a, b, c, d, e]  | [a, f, e, g, b]   | 2  | 0.0  |\n| [a, b, c, d, e]  | [a, f, c, g, b]   | 3  | 1.0  |\n| [a, b, c, d, e]  | [d, c, b, a, e]   | 3  | 1.0  |","metadata":{}},{"cell_type":"code","source":"def rel_at_k(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","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:19.014294Z","iopub.execute_input":"2022-02-08T15:25:19.014644Z","iopub.status.idle":"2022-02-08T15:25:19.024647Z","shell.execute_reply.started":"2022-02-08T15:25:19.014608Z","shell.execute_reply":"2022-02-08T15:25:19.023678Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"assert rel_at_k(gt, preds1, k=1) == 1.0\nassert rel_at_k(gt, preds2, k=1) == 1.0\nassert rel_at_k(gt, preds3, k=1) == 0.0\nassert rel_at_k(gt, preds4, k=2) == 0.0\nassert rel_at_k(gt, preds5, k=3) == 1.0\nassert rel_at_k(gt, preds6, k=3) == 1.0","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:19.025853Z","iopub.execute_input":"2022-02-08T15:25:19.026116Z","iopub.status.idle":"2022-02-08T15:25:19.039512Z","shell.execute_reply.started":"2022-02-08T15:25:19.026086Z","shell.execute_reply":"2022-02-08T15:25:19.038462Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Average Precision at K","metadata":{}},{"cell_type":"markdown","source":"This is simply the mean of the product of `P@k` and `rel(k)` for all values of `k`\n\n$${1\\over{{min(n,12)}}} {\\sum_{k=1}^{min(n,12)}P(k) \\times rel(k)}$$","metadata":{}},{"cell_type":"code","source":"def average_precision_at_k(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(y_true, y_pred, i) * rel_at_k(y_true, y_pred, i)\n        \n    return ap / min(k, len(y_true))","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:19.040784Z","iopub.execute_input":"2022-02-08T15:25:19.041050Z","iopub.status.idle":"2022-02-08T15:25:19.052738Z","shell.execute_reply.started":"2022-02-08T15:25:19.041019Z","shell.execute_reply":"2022-02-08T15:25:19.051887Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"assert average_precision_at_k(gt, preds1, k=1) == 1.0\nassert average_precision_at_k(gt, preds2, k=1) == 1.0\nassert average_precision_at_k(gt, preds3, k=1) == 0.0\nassert average_precision_at_k(gt, preds4, k=2) == 0.5\nassert average_precision_at_k(gt, preds5, k=3) == 0.5555555555555555\nassert average_precision_at_k(gt, preds6, k=3) == 1.0","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:19.054400Z","iopub.execute_input":"2022-02-08T15:25:19.055053Z","iopub.status.idle":"2022-02-08T15:25:19.072674Z","shell.execute_reply.started":"2022-02-08T15:25:19.055014Z","shell.execute_reply":"2022-02-08T15:25:19.071660Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Mean Average Precision at K","metadata":{}},{"cell_type":"markdown","source":"Take mean of Average Precision for all the users","metadata":{}},{"cell_type":"code","source":"def mean_average_precision(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(gt, pred, k) \\\n                    for gt, pred in zip(y_true, y_pred)])","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:19.074006Z","iopub.execute_input":"2022-02-08T15:25:19.076873Z","iopub.status.idle":"2022-02-08T15:25:19.083998Z","shell.execute_reply.started":"2022-02-08T15:25:19.076826Z","shell.execute_reply":"2022-02-08T15:25:19.083310Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"y_true = np.array([gt, gt, gt, gt, gt, gt])\ny_pred = np.array([preds1, preds2, preds3, preds4, preds5, preds6])","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:19.085298Z","iopub.execute_input":"2022-02-08T15:25:19.086026Z","iopub.status.idle":"2022-02-08T15:25:19.098238Z","shell.execute_reply.started":"2022-02-08T15:25:19.085988Z","shell.execute_reply":"2022-02-08T15:25:19.097596Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(average_precision_at_k(gt, preds1, k=4))\nprint(average_precision_at_k(gt, preds2, k=4))\nprint(average_precision_at_k(gt, preds3, k=4))\nprint(average_precision_at_k(gt, preds4, k=4))\nprint(average_precision_at_k(gt, preds5, k=4))\nprint(average_precision_at_k(gt, preds6, k=4))","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:19.100678Z","iopub.execute_input":"2022-02-08T15:25:19.101129Z","iopub.status.idle":"2022-02-08T15:25:19.117043Z","shell.execute_reply.started":"2022-02-08T15:25:19.101096Z","shell.execute_reply":"2022-02-08T15:25:19.115911Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"mean_average_precision(y_true, y_pred, k=4)","metadata":{"execution":{"iopub.status.busy":"2022-02-08T15:25:19.118454Z","iopub.execute_input":"2022-02-08T15:25:19.119331Z","iopub.status.idle":"2022-02-08T15:25:19.132588Z","shell.execute_reply.started":"2022-02-08T15:25:19.119277Z","shell.execute_reply":"2022-02-08T15:25:19.131421Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Thanks for reading","metadata":{}}]}