{"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":"# What is Mean Average Precision MAP? MAP@k metric explained with code.\n\n- __Author__ - [Nandeshwar Gupta](https://nandeshwar.in/)\n- __Date__ - 19Feb2022\n- __Link__ - [Kaggle](https://www.kaggle.com/nandeshwar) || [Github](https://github.com/nandesh553)","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19"}},{"cell_type":"markdown","source":"# Evaluation metrics mentioned in this competition.\n\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.
\nWe will slowly build towards the final function, bit by bit","metadata":{}},{"cell_type":"markdown","source":"\n\"MAP@k\"\n","metadata":{}},{"cell_type":"markdown","source":"
\n\n---\n\n
\n\n# What is MAP@k? Evaluating Recommender Systems.\n\n**MAP@k** is a commonly used metric, especially in the use cases where **information retrieval** is done and **ranking of documents is equally important**. It is usually used in following\n\n- Recommender Systems\n- Ranking Models\n- Search based Models (Google search)\n\n> \"k\" is not a hyperparameter as it is determined by business & stakeholders.\n\nIf you are using MAP metric in recommender systems then you are implying that you treating recommendation as a ranking model. This seems to be right because often recommendations are provided as a list and users watch the items on top of the list!\n\nMAP metric rewards the model on getting relevant recommendations and also emphasizes rewarding them more for having ranked first on the list.\n\n**Keep in mind**\n1. We can recommend **k** items for each user.\n2. Because there is no penalty for poor recommendations, it is better to recommend all **k** recommendations.\n3. Rank or Order of the recommendation matters a lot as it is better to show better suggestions first to the user.\n\n
\n\n---\n\n
\n\n### Explanation\nLet us break down MAP first. M denotes **mean**, so it says Mean of AP where AP is Average Precision. This implies if we have 2500 users, then the sum of Average Precisions for each user divided by 2500 is equal to MAP.\n\nIn order to understand MAP one should first understand Precision and Recall. More specifically Precision@k and Recall@k.\n\n#### Precision\nPrecision is the percentage of true positives in the retrieved results. Precision is a good measure to determine when the costs of False Positive are high. Hence:\n$$\nprecision = \\frac{tp}{tp+fp} \\tag{1}\n$$\n\n#### Recall\nRecall is the number of true positives divided by the total number of true positives and false negatives (all the positives even which are not recommended).\n$$\nrecall = \\frac{tp}{tp+fn} \\tag{2}\n$$\n\n#### Precision@k (P@k)\nIn our case $tp+fp$ are the retrieved results hence it can be **k** where k is equal to the number of images received $(tp + fn)$. Using this in equation 1\n$$\nprecision@k = \\frac{tp}{k} \\tag{3}\n$$\n\n> P@k is generally calculated for one recommendation\n\n#### Average Precision@k (AP@k)\nAbove we saw the definition of Precision. Now Average Precision refers, as the name says an average of all the values from P@i for i= 1,2,3, ., k. For Eg. to calculate AP@k: sum of(P@1, P@2, P@3 . . ., P@k).\n\n>AP@k is typically calculated for one user from all recommendations by averaging P@1 to P@k\n\n#### Mean Average Precision@k (MAP@k)\nComing to the last piece ie Mean of AP. It simply implies **mean of AP@k** for all the users.\nIn order to do this, we divide the sum of all APs by **m where m is min(k, a)** *where **a** is the number of actual relevant recommendations while our algorithm is supposed to recommend **k**.*\n\n> 1/min(k, a) adds the normalization factor, which prevents AP scores from being unfairly suppressed when the number of recommendations couldn't possibly capture all the correct ones.\n\n
\n\n---\n\n
\n\n**For eg.** \nConsider, there are 5 relevant recommendations (_m_), we are making 10 recommendations (_N_) as follows — 1 0 1 0 0 1 0 0 1 1. Let’s calculate the mean average precision here.\n\nMAP@10:\n$$\n(1 * 1+0.5 * 0+0.67 * 1+0.5 * 0+0.4 * 0+0.5 * 1+0.42 * 0+0.375 * 0+0.44 * 1+0.5 * 1) / 5 = 0.62\n$$\n\n#### Proof - MAP is formulated to reward better ranked recommendations highly\nImagine there are two types of predictions and 8 possible recommendations\n1. rec_a = 1 0 0 0 0 1 1\n2. rec_b = 1 1 1 0 0 0 0 \n\nHere $k=7$ and $a=8$ hence we divide by $min(k, a) = 7$ as mentioned above\n\nLet us calculate *MAP@7* for rec_a\n$$\n(1*1 + 1/2*0 + 1/3*0 + 1/4*0 + 1/5*0 + 2/6*1 + 3/7*1) / 7 = 0.25\n$$\nSimilarly, Let us calculate *MAP@7* for rec_b\n$$\n(1*1 + 2/2*1 + 3/3*1 + 3/4*0 + 3/5*0 + 3/6*0 + 3/7*0) / 7 = 0.42\n$$\nMAP@7 for rec_a = 1.76 &\nMAP@7 for rec_b = 3\n\nClearly rec_b has better score hence providing better recommendations","metadata":{}},{"cell_type":"markdown","source":"# Code\nRefering to [Benhamner's](https://github.com/benhamner/Metrics/blob/master/Python/ml_metrics/average_precision.py) code","metadata":{}},{"cell_type":"code","source":"import numpy as np\n\ndef apk(actual, predicted, k=10):\n \"\"\"\n Computes the average precision at k.\n This function computes the average prescision at k between two lists of\n items.\n Parameters\n ----------\n actual : list\n A list of elements that are to be predicted (order doesn't matter)\n predicted : list\n A list of predicted elements (order does matter)\n k : int, optional\n The maximum number of predicted elements\n Returns\n -------\n score : double\n The average precision at k over the input lists\n \"\"\"\n if not actual:\n return 0.0\n\n if len(predicted)>k:\n predicted = predicted[:k]\n\n score = 0.0\n num_hits = 0.0\n\n for i,p in enumerate(predicted):\n # first condition checks whether it is valid prediction\n # second condition checks if prediction is not repeated\n if p in actual and p not in predicted[:i]:\n num_hits += 1.0\n score += num_hits / (i+1.0)\n\n return score / min(len(actual), k)\n\ndef mapk(actual, predicted, k=10):\n \"\"\"\n Computes the mean average precision at k.\n This function computes the mean average prescision at k between two lists\n of lists of items.\n Parameters\n ----------\n actual : list\n A list of lists of elements that are to be predicted \n (order doesn't matter in the lists)\n predicted : list\n A list of lists of predicted elements\n (order matters in the lists)\n k : int, optional\n The maximum number of predicted elements\n Returns\n -------\n score : double\n The mean average precision at k over the input lists\n \"\"\"\n return np.mean([apk(a,p,k) for a,p in zip(actual, predicted)])","metadata":{"execution":{"iopub.status.busy":"2022-02-18T11:13:04.808613Z","iopub.execute_input":"2022-02-18T11:13:04.809008Z","iopub.status.idle":"2022-02-18T11:13:04.838271Z","shell.execute_reply.started":"2022-02-18T11:13:04.808901Z","shell.execute_reply":"2022-02-18T11:13:04.837463Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"References\n- https://sdsawtelle.github.io/blog/output/mean-average-precision-MAP-for-recommender-systems.html\n- https://sanchom.wordpress.com/2011/09/01/precision-recall/\n","metadata":{}}]}