2_evaluation_metrics_ir.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Evaluation for IR\n",
    "\n",
    "Here we are only going to look at offline evaluation metrics. We won't cover online evaluation techniques like click-through rate or running A/B tests where a subset of users are presented results from a newer test system.\n",
    "\n",
    "## Offline evaluation\n",
    "\n",
    "The idea behind these evaluations is to quantitatively compare multiple IR models. Typically we have a labeled dataset where we have queries mapped to relevant documents. The documents could either be graded or non-graded(binary). For example, a graded relevance score could be on a scale of 0-5 with 5 being the most relevant.\n",
    "\n",
    "Labeled data typically comes form manual annotations or click data.\n",
    "\n",
    "It's also not necessary to have just 1 document tagged as relevant for each query. TREC collections have 100s of documents tagged as relevant per query. On the other hand MSMARCO has ~1 document tagged as relevant per query. This tends to be quite noisy but easy to scale hence more variability in the queries."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary labels\n",
    "\n",
    "### Precision@k\n",
    "\n",
    "Precision@k corresponds to the number of relevant documents among top k retrieved documents.\n",
    "\n",
    "$$ Precision@k = \\frac{TP@k}{TP@k + FP@k} $$\n",
    "\n",
    "| ![](assets/precision@k.png) | \n",
    "|:--:| \n",
    "| Fig. 1. Illustration of Precision@k for evaluating IR models. |\n",
    "\n",
    "Precision fails to take into account the ordering of the relevant documents. For example consider the models A and B (Fig 2) where model A outputs `[1,1,1,0,0](first 3 relevant)` and model B outputs `[0,0,1,1,1](indices 3-5 relevant)`; both the models get the same score `Precision@5=3/5`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MAP@k: Mean Average Precision\n",
    "\n",
    "*Average Precision(AP)* evaluates whether all the relevant items selected by the model are ranked higher or not.\n",
    "Every time we find a relevant document, we look at the full picture of what came before.\n",
    "\n",
    "MAP squeezes complex evaluation into a single number. It's essentially the mean of AP over all the queries.\n",
    "\n",
    "$$ AP@k(q) = \\frac{\\sum_{i=1}^k P(q)@i * rel(q)_i}{|rel(q)|} $$\n",
    "\n",
    "$$ MAP@k(Q) = \\frac{1}{|Q|} * \\sum_{q\\in Q} AP@k(q) $$\n",
    "\n",
    "|Q| - Number of queries<br>\n",
    "𝑃(𝑞)@𝑖 - Precision of query q after first i documents<br>\n",
    "𝑟𝑒𝑙(𝑞)𝑖 - Binary relevance of doc at position i<br>\n",
    "|𝑟𝑒𝑙(𝑞)| - Number of relevant documents\n",
    "\n",
    "| ![](assets/ap.png) | \n",
    "|:--:| \n",
    "| Fig. 2. Illustration of AveragePrecision@k for evaluating IR models. |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MRR: Mean Reciprocal Rank\n",
    "\n",
    "MRR puts focus on the first relevant document. It's applicable when the system needs to return only the top matching document or the user only cares about the top result.\n",
    "\n",
    "$$ MRR(Q) = \\frac{1}{|Q|} * \\sum_{q\\in Q} \\frac{1}{FirstRank(q)} $$\n",
    "\n",
    "|Q| - Number of queries<br>\n",
    "*FirstRank(q)* - Returns the rank of first relevant dcuments for 1 query\n",
    "\n",
    "MRR(for 1 query) for different positions can be seen below. Notice the sharp fall in the values beyond the top few places."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA6IAAAEvCAYAAABfSXyoAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAsO0lEQVR4nO3deXhc9X3v8fdXsmwZ2xhjm1UGm2AghrAqhD0GAhhCzDYuoUmzkIbShBZS7m1o0qRpL+3NJW2WpikJJNRNS6EsZgmELU6A0LDZ7MY4GMIiNhvMDsbb7/5xRtHiGWm0zZmR3q/nOc/MnHM087Fsa+aj8zu/EyklJEmSJEmqloa8A0iSJEmSRhaLqCRJkiSpqiyikiRJkqSqsohKkiRJkqrKIipJkiRJqiqLqCRJkiSpqkbl9cJTpkxJ06dPz+vlJUmSJElDaPHixS+nlKaW2pZbEZ0+fTqLFi3K6+UlSZIkSUMoIp4ut82huZIkSZKkqrKISpIkSZKqyiIqSZIkSaqq3M4RlSRJkqSRau3atbS1tbF69eq8owxYc3MzLS0tNDU1Vfw1FlFJkiRJqrK2tjYmTJjA9OnTiYi84/RbSolXXnmFtrY2ZsyYUfHXOTRXkiRJkqps9erVTJ48ua5LKEBEMHny5D4f2bWISpIkSVIO6r2EtuvPn6PXIhoRF0XEioh4pMz2iIh/jojlEfFQROzd5xSSJEmSpKo79dRT2WKLLdhtt926rL/zzjv5/Oc/P2SvW8kR0fnAnB62Hw3MLC6nAecPPJYkSZIkaah95jOf4cYbb9xo/Y033sicOT3VwIHptYimlG4HVvWwy3HAT1PmLmCziNh6sALmYc0auPRSWLQo7ySSJEmSNHQOOeQQNt98843WL1y4kI985CN8+9vf5tRTTwXg4YcfZrfdduOdd94Z8OsOxjmi2wLPdnrcVly3kYg4LSIWRcSilStXDsJLD42U4PTT4Qc/yDuJJEmSJFXXyy+/TFNTExMnTuSss85i+fLlXHXVVXz2s5/lRz/6EZtsssmAX2MwLt9S6szUVGrHlNIFwAUAra2tJfepBWPGwNy5cPXV8KMfwejReSeSJEmSNFyddRY88MDgPueee8J3v9u/r7355ps58sgjAWhoaGD+/Pnsvvvu/Mmf/AkHHnjgoOQbjCOibcC0To9bgOcH4XlzVSjAa6/Br36VdxJJkiRJqp4bbrihy/mhjz/+OOPHj+f55wev5g3GEdFrgTMi4lLgQ8DrKaUXBuF5c3XkkTB+PFxxBRx1VN5pJEmSJA1X/T1yORRSSjz00EPsueeeALz++uuceeaZ3H777ZxxxhlcccUVFAqFAb9OJZdvuQS4E9g5Itoi4nMRcXpEnF7c5efAk8By4ELgCwNOVQOam+FjH4OrroJ16/JOI0mSJEmD75RTTmH//fdn2bJltLS0cN5557HXXnv9/tqgX/rSl/jCF77ATjvtxE9+8hPOOeccVqxYMeDX7fWIaErplF62J+CLA05SgwoFuOQSuO02OPzwvNNIkiRJ0uC65JJLujw+99xzuwzLveiii35/f9q0aSxfvnxQXncwhuYOW0cfDePGZcNzLaKSJEmShru//uu/rsrrDMZkRcPW2LHw0Y/CggWwfn3eaSRJkiRpeLCI9qJQgBUr4I478k4iSZIkScODRbQXRx+dHRm94oq8k0iSJEkaTrLpdupff/4cFtFejB+fldErr4QNG/JOI0mSJGk4aG5u5pVXXqn7MppS4pVXXqG5ublPX+dkRRUoFLLzRO+8Ew48MO80kiRJkupdS0sLbW1trFy5Mu8oA9bc3ExLS0ufvsYiWoGPfhTGjIHLL7eISpIkSRq4pqYmZsyYkXeM3Dg0twKbbgpHHeXwXEmSJEkaDBbRChUK0NYG99yTdxJJkiRJqm8W0Qp97GPQ1OTsuZIkSZI0UBbRCm22GRxxRFZE63xiK0mSJEnKlUW0DwoFePppWLw47ySSJEmSVL8son1w3HEwapTDcyVJkiRpICyifbD55nD44Q7PlSRJkqSBsIj2UaEATzwBDz6YdxJJkiRJqk8W0T46/nhobHR4riRJkiT1l0W0j6ZMgdmz4fLLHZ4rSZIkSf1hEe2HQgF++1tYsiTvJJIkSZJUfyyi/XDCCRCRHRWVJEmSJPWNRbQfttwSDjnE80QlSZIkqT8sov1UKMCjj2aLJEmSJKlyFtF+OvHE7PbKK/PNIUmSJEn1xiLaT9tsAwce6PBcSZIkSeori+gAFArw0EPZDLqSJEmSpMpYRAfgpJOyW4fnSpIkSVLlLKIDMG0a7Lefw3MlSZIkqS8sogNUKMB998GTT+adRJIkSZLqg0V0gByeK0mSJEl9YxEdoOnTobXV4bmSJEmSVCmL6CAoFOCee+Dpp/NOIkmSJEm1zyI6CByeK0mSJEmVs4gOgh13hD33dHiuJEmSJFXCIjpICgW4805oa8s7iSRJkiTVNovoICkUstsFC/LNIUmSJEm1ziI6SHbeGXbbzeG5kiRJktQbi+ggKhTgjjvghRfyTiJJkiRJtcsiOojmzYOU4Kqr8k4iSZIkSbXLIjqIZs2C97/f4bmSJEmS1BOL6CArFOC222DFiryTSJIkSVJtsogOskIBNmyAq6/OO4kkSZIk1SaL6CD7wAdg5kyH50qSJElSORbRQRaRHRX95S/h5ZfzTiNJkiRJtcciOgQKBVi/Hq65Ju8kkiRJklR7KiqiETEnIpZFxPKIOKfE9okR8bOIeDAilkTEZwc/av3Yay+YMcPhuZIkSZJUSq9FNCIagR8ARwOzgFMiYla33b4IPJpS2gOYDfxTRIwe5Kx1o3147i9+Aa++mncaSZIkSaotlRwR3RdYnlJ6MqW0BrgUOK7bPgmYEBEBjAdWAesGNWmdKRRg3Tq49tq8k0iSJElSbamkiG4LPNvpcVtxXWf/ArwfeB54GDgzpbSh+xNFxGkRsSgiFq1cubKfkevDBz8I06Y5PFeSJEmSuqukiEaJdanb46OAB4BtgD2Bf4mITTf6opQuSCm1ppRap06d2seo9aV9eO7NN8Prr+edRpIkSZJqRyVFtA2Y1ulxC9mRz84+CyxImeXA74BdBidi/Zo3D9asgeuuyzuJJEmSJNWOSorovcDMiJhRnIDo40D3Mx+fAQ4HiIgtgZ2BJwczaD360Idg220dnitJkiRJnfVaRFNK64AzgJuApcBlKaUlEXF6RJxe3O3/AAdExMPAQuDLKaWXhyp0vWhogJNOghtugDffzDuNJEmSJNWGSKn76Z7V0dramhYtWpTLa1fTr38NhxwCl14KJ5+cdxpJkiRJqo6IWJxSai21rZKhuRqAAw6ArbZyeK4kSZIktbOIDrHGRjjxRLj+enj77bzTSJIkSVL+LKJVUCjAu+9m54pKkiRJ0khnEa2Cgw+GqVMdnitJkiRJYBGtilGj4IQTsuuJvvtu3mkkSZIkKV8W0SopFLJzRG+6Ke8kkiRJkpQvi2iVzJ4Nm2/u8FxJkiRJsohWSVMTHH88XHstvPde3mkkSZIkKT8W0SqaNw/efBNuuSXvJJIkSZKUH4toFR12GGy2mcNzJUmSJI1sFtEqGj0ajjsOrrkG1qzJO40kSZIk5cMiWmWFArz2Gvzyl3knkSRJkqR8WESr7IgjYMIEh+dKkiRJGrksolU2ZgzMnQtXXQVr1+adRpIkSZKqzyKag0IBVq2CW2/NO4kkSZIkVZ9FNAdHHQXjxjk8V5IkSdLIZBHNwdixcOyx2fDcdevyTiNJkiRJ1WURzUmhACtXwq9/nXcSSZIkSaoui2hOjj46OzLq8FxJkiRJI41FNCfjxsExx8CCBbB+fd5pJEmSJKl6LKI5mjcPXnwRfvObvJNIkiRJUvVYRHN0zDHQ3OzwXEmSJEkji0U0RxMmwJw5cOWVsGFD3mkkSZIkqTosojkrFOC55+Duu/NOIkmSJEnVYRHN2bHHwujRDs+VJEmSNHJYRHM2cSIceWRWRFPKO40kSZIkDT2LaA0oFOCZZ+Dee/NOIkmSJElDzyJaA+bOhVGjHJ4rSZIkaWSwiNaASZPgIx9xeK4kSZKkkcEiWiMKBfjd7+D++/NOIkmSJElDyyJaI447DhobHZ4rSZIkafiziNaIKVPgsMPg8ssdnitJkiRpeLOI1pBCAZYvh4cfzjuJJEmSJA0di2gNOf54aGhweK4kSZKk4c0iWkO22AI+/GGLqCRJkqThzSJaYwoFWLoUHn007ySSJEmSNDQsojXmhBMgIpu0SJIkSZKGI4tojdl6azjoIIfnSpIkSRq+LKI1qFCARx6Bxx7LO4kkSZIkDT6LaA068cTs9sor880hSZIkSUPBIlqDWlpg//0dnitJkiRpeLKI1qhCAR54AJYvzzuJJEmSJA0ui2iNOumk7NbhuZIkSZKGm4qKaETMiYhlEbE8Is4ps8/siHggIpZExG2DG3Pk2X572Hdfh+dKkiRJGn56LaIR0Qj8ADgamAWcEhGzuu2zGfCvwNyU0q7AvMGPOvIUCrBoETz1VN5JJEmSJGnwVHJEdF9geUrpyZTSGuBS4Lhu+/whsCCl9AxASmnF4MYcmRyeK0mSJGk4qqSIbgs82+lxW3FdZzsBkyLi1ohYHBGfKvVEEXFaRCyKiEUrV67sX+IRZIcdYO+9HZ4rSZIkaXippIhGiXWp2+NRwD7AR4GjgK9FxE4bfVFKF6SUWlNKrVOnTu1z2JGoUIC77oJnn+19X0mSJEmqB5UU0TZgWqfHLcDzJfa5MaX0dkrpZeB2YI/BiTiyOTxXkiRJ0nBTSRG9F5gZETMiYjTwceDabvtcAxwcEaMiYhPgQ8DSwY06Mu20E+y+u8NzJUmSJA0fvRbRlNI64AzgJrJyeVlKaUlEnB4Rpxf3WQrcCDwE3AP8OKX0yNDFHlkKBfif/4Hnnss7iSRJkiQNXKTU/XTP6mhtbU2LFi3K5bXrzdKlMGsWfP/7cMYZeaeRJEmSpN5FxOKUUmupbZUMzVXO3v/+rIg6PFeSJEnScGARrROFAtx+O7z0Ut5JJEmSJGlgLKJ1olCAlOCqq/JOIkmSJEkDYxGtE7vtBjvv7PBcSZIkSfXPIlonIrKjorfeCitX5p1GkiRJkvrPIlpHCgVYvx6uuSbvJJIkSZLUfxbROrLHHvC+9zk8V5IkSVJ9s4jWkfbhuQsXwqpVeaeRJEmSpP6xiNaZQgHWrXN4riRJkqT6ZRGtM/vsA9tv7/BcSZIkSfXLIlpn2ofn3nILvPZa3mkkSZIkqe8sonWoUIC1a+FnP8s7iSRJkiT1nUW0Du27L7S0ODxXkiRJUn2yiNahhgY46SS46SZ4442800iSJElS31hE61ShAO+9B9dfn3cSSZIkSeobi2idOuAA2Hprh+dKkiRJqj8W0TrVPjz35z+Ht97KO40kSZIkVc4iWscKBVi9Gm64Ie8kkiRJklQ5i2gdO+gg2GILh+dKkiRJqi8W0TrW2AgnngjXXQfvvJN3GkmSJEmqjEW0zp1ySlZCTzsN1q/PO40kSZIk9c4iWucOOQT+/u/h4ovh1FMto5IkSZJq36i8A2jgvvKVrIB+/eswahRceGE2q64kSZIk1SKL6DDxta/BunXwd3+XnTv6wx9aRiVJkiTVJovoMPKNb2Rl9B/+ISuj//qvEJF3KkmSJEnqyiI6jETAuedmZfS887Jhuv/8z5ZRSZIkSbXFIjrMRMA3v5mdM/pP/5QdGf3OdyyjkiRJkmqHRXQYioBvfSs7Mvq972VHRr/1LcuoJEmSpNpgER2mIrIjoZ2PjH7zm5ZRSZIkSfmziA5jEdk5ouvXd5wzeu65llFJkiRJ+bKIDnMR8C//0jGbblNTNruuJEmSJOXFIjoCNDRk1xVdtw7+9m+zYbpf+1reqSRJkiSNVBbREaKhAS68MBum+/WvZ2X0K1/JO5UkSZKkkcgiOoI0NsJFF2Vl9Ktfzc4Z/cu/zDuVJEmSpJHGIjrCNDbC/PlZGf3yl7My+hd/kXcqSZIkSSOJRXQEGjUK/uM/sjJ69tlZOT3zzLxTSZIkSRopLKIj1KhRcPHFWRk966zs8Re/mHcqSZIkSSNBQ94BlJ+mJrjkEjjuODjjjGxmXUmSJEkaahbREW70aLjsMjj2WPjTP81m1pUkSZKkoWQRFaNHwxVXwNFHw2mnZTPrSpIkSdJQsYgKgDFjYMECOPJI+OM/hp/+NO9EkiRJkoYri6h+r7kZrr4aDjsMPvOZbDIjSZIkSRpsFlF1MXYsXHstzJ4Nn/oUXHpp3okkSZIkDTcVFdGImBMRyyJieUSc08N+H4yI9RFRGLyIqrZNNoGf/QwOOgg++Um4/PK8E0mSJEkaTnotohHRCPwAOBqYBZwSEbPK7Pf/gJsGO6Sqb9w4uP562G8/OOWU7PxRSZIkSRoMlRwR3RdYnlJ6MqW0BrgUOK7Efn8GXAmsGMR8ytH48XDDDbDvvnDyyXDNNXknkiRJkjQcVFJEtwWe7fS4rbju9yJiW+AE4Ic9PVFEnBYRiyJi0cqVK/uaVTmYMCEro3vvDfPmwXXX5Z1IkiRJUr2rpIhGiXWp2+PvAl9OKa3v6YlSSheklFpTSq1Tp06tMKLyNnEi3HQT7LEHnHRSVkwlSZIkqb8qKaJtwLROj1uA57vt0wpcGhFPAQXgXyPi+MEIqNqw2WZw882w665wwgnZfUmSJEnqj0qK6L3AzIiYERGjgY8D13beIaU0I6U0PaU0HbgC+EJK6erBDqt8TZoEt9wCu+wCxx0Hv/hF3okkSZIk1aNei2hKaR1wBtlsuEuBy1JKSyLi9Ig4fagDqrZMnpwV0JkzYe5c+NWv8k4kSZIkqd5ESt1P96yO1tbWtGjRolxeWwO3ciUceij87nfZOaOHHJJ3IkmSJEm1JCIWp5RaS22rZGiutJGpU2HhQthuOzjmGPif/8k7kSRJkqR6YRFVv225Jfzyl7DttjBnDtx5Z96JJEmSJNUDi6gGZOuts/NEt94ajjoK7r4770SSJEmSap1FVAO2zTbZkdGpU7My6qm/kiRJknpiEdWgaGnJjoxuvjkccQTcd1/eiSRJkiTVKouoBs1222VldOLErIw++GDeiSRJkiTVIouoBtX222fDdMeNg8MPh4cfzjuRJEmSpFpjEdWg22GHrIw2N2dldMmSvBNJkiRJqiUWUQ2JHXfMhumOGgWHHQZLl+adSJIkSVKtsIhqyMycmZXRiKyMLluWdyJJkiRJtcAiqiG1887ZMN0NG+DQQ+Hxx/NOJEmSJClvFlENuVmzYOFCWLsWDjgAvvMdePfdvFNJkiRJyotFVFWx225w222wxx7wF38B73sffP/7sHp13skkSZIkVZtFVFUzaxb84hdw663Z+aN//ufZpEbnnw/vvZd3OkmSJEnVYhFV1X34w1kZXbgwu+7oF74AO+0EF16YDd+VJEmSNLxZRJWL9pl077gDbroJtt4aTjstK6QXXQTr1uWdUJIkSdJQsYgqVxFw5JFw551w/fUweTJ87nOwyy7w059aSCVJkqThyCKqmhABxxwD994L11wDEybApz8Nu+4K//VfsH593gklSZIkDRaLqGpKBMydC4sXw4IFMGYMfOIT8IEPwGWXZdcjlSRJklTfLKKqSQ0NcMIJ8MADWQGNgJNPzi7/smCBhVSSJEmqZxZR1bSGBpg3Dx56KBuiu3YtnHQS7LNPNoQ3pbwTSpIkSeori6jqQmMjnHIKLFkC//Ef8NZbcPzx8MEPZpMcWUglSZKk+mERVV1pbIRPfhKWLoV/+zdYtQqOPRb22y+7DIyFVJIkSap9FlHVpVGj4DOfgWXL4MIL4cUXYc4cOOgg+MUvLKSSJElSLbOIqq41NcEf/zE8/jicfz488wwccQTMng233ZZ3OkmSJEmlWEQ1LIweDaefnhXS738/u509Gw47DO64I+90kiRJkjqziGpYaW6GM86AJ56A734XHn0UDj4YjjwS7rwz73SSJEmSwCKqYWrsWDjzTHjySfjHf8yuR3rAAXDMMXDvvXmnkyRJkkY2i6iGtU02gbPPzgrpN78Jd98N++4Lc+fC/ffnnU6SJEkamSyiGhHGj4cvfxl+9zs491z49a9h773hxBPhoYfyTidJkiSNLBZRjSibbgpf/So89RR84xuwcCHssQfMmwdLluSdTpIkSRoZLKIakSZOhL/5m6yQfu1rcNNN8IEPwCmnwGOP5Z1OkiRJGt4sohrRJk2Cv/u7bMjuOefAz34Gu+4Kf/RHcN99kFLeCSVJkqThxyIqAZMnwz/8Q1ZIzz4brrwS9tkHtt8+uxzMzTfDe+/lnVKSJEkaHiyiUidTp8J558Ezz8BPfpJNaHTRRXDUUdm2P/gD+M//hFdeyTupJEmSVL8i5TT2sLW1NS1atCiX15b64t13s0mNrr02G7r74ovQ0AAHHZRdBmbuXJg5M++UkiRJUm2JiMUppdaS2yyiUuU2bIDFi7NSeu21HZd+2WWXjlK6337Q2JhvTkmSJClvFlFpiDz1VHaU9Npr4dZbYd06mDIFjj02K6VHHJFdw1SSJEkaaSyiUhW8/jrceGNWSn/+c3jtNRgzBg4/PCulxx4L226bd0pJkiSpOiyiUpWtXQt33NExhPfJJ7P1ra0dQ3h33x0i8s0pSZIkDRWLqJSjlGDp0o5Setdd2brttoOPfSwrpbNnw+jReSeVJEmSBo9FVKohL70E11+fldKbb85m5Z0wAebMyUrpMcfA5pvnnVKSJEkaGIuoVKNKXRqmsbHrpWF23DHvlJIkSVLf9VREGyp8gjkRsSwilkfEOSW2fyIiHiouv4mIPQYaWhoJxo7NJjG64AJ47jm4+2445xxYtQrOPju7PumsWdm63/wG1q/PO7EkSZI0cL0eEY2IRuC3wBFAG3AvcEpK6dFO+xwALE0pvRoRRwPfSCl9qKfn9Yio1LNSl4aZOrXrpWHGjcs7pSRJklTagIbmRsT+ZMXyqOLjvwJIKf3fMvtPAh5JKfV4oQqLqFS53i4Nc/DBsPPO2bBeSZIkqRb0VERHVfD12wLPdnrcBvR0tPNzwA1lgpwGnAaw3XbbVfDSkgAmToSTT86WzpeGueaarJhCdnR0772zS8S0LzvuCA0VDcCXJEmSqqeSIlrqSoclD6NGxKFkRfSgUttTShcAF0B2RLTCjJI6aWqCQw/Nlm9/G5Ytg3vugUWLsuX882H16mzfTTeFffbpWk5nzPD6pZIkScpXJUW0DZjW6XEL8Hz3nSJid+DHwNEppVcGJ56knkTALrtky6c+la1btw4efbSjmC5aBN/7HqxZk22fNKlrMW1thWnTLKeSJEmqnkrOER1FNlnR4cBzZJMV/WFKaUmnfbYDfgl8KqX0m0pe2HNEpepZswYeeaRrOX344ay0QjYJUmtr16On22xjOZUkSVL/Dfg6ohFxDPBdoBG4KKX09xFxOkBK6YcR8WPgJODp4pesK/eC7SyiUr5Wr4aHHoLFizvK6ZIlHZeI2WqrjY+cbrllvpklSZJUPwZcRIeCRVSqPe+8Aw8+2PXI6dKl0P5joqWlazHdZx+YMiXfzJIkSapNA501V9IIsckmsP/+2dLurbfg/vu7ltOrr+7YPn1613K6997ZeaiSJElSORZRST0aPz67TunBB3ese/11uO++ruX0iis6tu+4Y9dyutde2Qy+kiRJElhEJfXDxIkdl5Bpt2pVdr5p+zmnd94Jl16abYuAnXfOjpbutBPMnNmxbLZZLn8ESZIk5chzRCUNmZUru06GdP/98OyzHeecQjZjb+di2nkZPz6/7JIkSRoYJyuSVDNWr4YnnoDHH994ee65rvtutdXGR1BnzsyG/o4dm09+SZIkVcbJiiTVjOZm2HXXbOnu7bdh+fKNC+p118FLL3Xdt6Wlo5h2Lqs77ABjxlTnzyJJkqT+sYhKqhnjxsEee2RLd2+8Ufoo6pVXwiuvdOzX0ADbbbfxUdSddspm+G1qqtofR5IkSWVYRCXVhU03za5bus8+G2979dWslP72t11L6sUXZzP8tmtshBkzSp+Puv322XZJkiQNPYuopLo3aRLsu2+2dJYSvPxyRzHtXFRvvz0bCtyuqSkb1ts+zHeHHbLhv+3L1KnZ0VZJkiQNnEVU0rAVkRXIqVPhgAO6bksJXnxx46G+v/0t3HJLNqlSZ01NsM02XctpSwtsu23H/a23hlH+VJUkSeqVH5kkjUgRWXHcems45JCu2zZsgBUroK0tm8m3ra3rsngxXHPNxmW1oSGb6bd7Qe28bLNNNmGTJEnSSGYRlaRu2gvlVltBa8kJx7Mjqq++2rWgdi6ty5bBwoXZJEvdTZnS85HVlhavoSpJkoY3i6gk9UMEbL55tuy+e/n93nyz9FHV9nV33ZWdx9rdxInlj6y2r5s0KcshSZJUbyyikjSEJkyAXXbJlnJWr+4opqVK6yOPwAsvZEdhOxs7NiukW22VnQe7xRbZUur+5ps7K7AkSaodFlFJyllzM7zvfdlSztq12eRKpYYBv/QSPPZYNhPwK69sXFghG248eXLPZbXz/c0282irJEkaOhZRSaoDTU0wbVq29GT9+qyMrlgBK1d2ve18/4EHsvuvvlr+9aZMqby4jh9vcZUkSZWziErSMNLY2FESK7FmTXaOaqmy2vn+k09mt2++Wfp5mpt7L6tTp2ZDhCdNys6BdaiwJEkjl0VUkkaw0aOzS8pss01l+69e3XtpXbECHn00u3333dLPE5GV0UmTOspp+9L5can7EyZ49FWSpHpnEZUkVay5ubIhwpCdq/r2212HCK9alQ0HfvXVje+3tXXcX7u2/PM2NnYtrpWU1/Zlk00ssZIk1QKLqCRpSERk546OHw8zZlT+dSnBO++ULqul7r/6KjzxRMf9DRvKP/fo0ZUV1vbhw5tu2nUZPXrg3xdJkmQRlSTVmAgYNy5bWlr69rUbNmTnsfZWXtvvv/ACLFmS3X/99d6ff8yY0gV10037tn7MmP59byRJGi4sopKkYaOhISt+EyfC9Ol9+9r16+G11zrK6ptvwhtvZMvrr3fc777u6ae7rlu3rvfXGj168AqtQ40lSfXIIipJEtm5p5MnZ0t/pZRN6FSutPa07tlnO9ZXWmibmrLJm9qHQLcv48ZtvK7S9ZtskhV6SZKGkkVUkqRBEgFjx2bLllv2/3lSgvfe67nItq9/662Nl1Wruj5+++3sOSvVXkxLFdf+llyP3kqSOrOISpJUYyKyGYqbmyu/JmxPUsoupdO9sL79duXr3ngDnn++67pyl+cppbExO9o6lMvYsV6fVpLqhUVUkqRhLqKjrA1GsW23fn3X4tpbsX3nndLLyy9vvO7tt3ueAbmcMWMGp9Q2N3cc3W6/3/m2udkhzJI0EBZRSZLUL42NHRMnDbaUsuvJliuv/VlWrdp4XV+O6nY3enTXglqutJa67e++Y8ZYgCUNDxZRSZJUcyKyojd6NGy22dC9zoYN2QRT3Qvq6tVZSX333Y773W972/b66+X3GYgxY7qW1fbHnW9LretpW3/295xfSQNhEZUkSSNWQ0PHcNxqaZ+Mqq/lttw+773X9fbNN7Phzt23td+vZEbmSowe3bcC275/+23n+4N129hoQZbqhUVUkiSpijpPRpWH9eu7FtPu98sV2P7s/+abHY/XrMnud75du3Zw/2wRg1dsm5o6jsoP9HH3baNGWZgli6gkSdII0nkG47xt2JCV0e4FtRq3b7xRflt7pr5c9qiveiqqfdnWfSm3vtzS1/3bF4u0BsoiKkmSpFw0NHQM061F69dnpXTNmo4juO33uz8eym3vvAOvvVZ629q1Xe+vX1+d782oUX0vu+1fU+52KLb19esbGizZ1WIRlSRJkkpobMyWvIZR90f7jNPlls7ldaD79eW51q3Lzmtety5b137b+X6pbUN5VLqc9mLa01LJPn3dtz/POXv20MxcXg0WUUmSJGmY6Dzj9HDQPny7LwW20pLb09eXW3rb3n4Eu5J9uz9nf66dvGQJzJo1+N/3arCISpIkSapJtT58ezBt2JANre5LEZ4xI+/U/WcRlSRJkqScNTRkS1NT3kmqoyHvAJIkSZKkkcUiKkmSJEmqKouoJEmSJKmqLKKSJEmSpKqyiEqSJEmSqsoiKkmSJEmqKouoJEmSJKmqLKKSJEmSpKqyiEqSJEmSqsoiKkmSJEmqqkgp5fPCESuBp3N58cpNAV7OO0QF6iUnmHWo1EvWeskJZh0q9ZK1XnKCWYdCveQEsw6VeslaLznBrEOhHnJun1KaWmpDbkW0HkTEopRSa945elMvOcGsQ6VestZLTjDrUKmXrPWSE8w6FOolJ5h1qNRL1nrJCWYdCvWSsxyH5kqSJEmSqsoiKkmSJEmqKotozy7IO0CF6iUnmHWo1EvWeskJZh0q9ZK1XnKCWYdCveQEsw6VeslaLznBrEOhXnKW5DmikiRJkqSq8oioJEmSJKmqLKIlRMRFEbEiIh7JO0tPImJaRPwqIpZGxJKIODPvTOVERHNE3BMRDxaz/m3emXoSEY0RcX9EXJd3lp5ExFMR8XBEPBARi/LO05OI2CwiroiIx4r/ZvfPO1MpEbFz8fvZvrwREWflnauUiPhS8f/TIxFxSUQ0552pnIg4s5hzSa19P0v9zI+IzSPiloh4vHg7Kc+M7cpknVf8vm6IiJqYPbFMzm8V//8/FBFXRcRmOUb8vTJZ/08x5wMRcXNEbJNnxnY9fT6JiP8VESkipuSRrbsy39dvRMRznX6+HpNnxmKmkt/TiPiziFhW/L91Xl75OivzPf3vTt/PpyLigRwj/l6ZrHtGxF3tn1kiYt88MxYzlcq5R0TcWfx89bOI2DTPjO3Kfe6v1ferSlhES5sPzMk7RAXWAWenlN4P7Ad8MSJm5ZypnPeAw1JKewB7AnMiYr98I/XoTGBp3iEqdGhKac86mL77e8CNKaVdgD2o0e9vSmlZ8fu5J7AP8A5wVb6pNhYR2wJ/DrSmlHYDGoGP55uqtIjYDfg8sC/Z3/2xETEz31RdzGfjn/nnAAtTSjOBhcXHtWA+G2d9BDgRuL3qacqbz8Y5bwF2SyntDvwW+KtqhypjPhtn/VZKaffiz4HrgK9XO1QZ8ynx+SQipgFHAM9UO1AP5lP6s9R32n/GppR+XuVMpcynW86IOBQ4Dtg9pbQr8I855CplPt2yppRO7vSedSWwIIdcpcxn47//84C/LWb9evFx3uazcc4fA+eklD5A9v7/v6sdqoxyn/tr9f2qVxbRElJKtwOr8s7Rm5TSCyml+4r33yT7YL9tvqlKS5m3ig+biktNnqAcES3AR8l+EGkQFH+beAjwE4CU0pqU0mu5hqrM4cATKaWn8w5SxihgbESMAjYBns85TznvB+5KKb2TUloH3AackHOm3yvzM/844N+L9/8dOL6amcoplTWltDSltCynSCWVyXlz8e8f4C6gperBSiiT9Y1OD8dRI+9XPXw++Q7wl9RITqirz1Klcv4p8M2U0nvFfVZUPVgJPX1PIyKAPwAuqWqoMspkTUD70cWJ1MB7VpmcO9Pxi71bgJOqGqqMHj731+T7VSUsosNEREwH9gLuzjlKWcXhrg8AK4BbUkq1mvW7ZG/oG3LOUYkE3BwRiyPitLzD9GAHYCXwb5ENef5xRIzLO1QFPk6NvKl3l1J6juy39M8ALwCvp5RuzjdVWY8Ah0TE5IjYBDgGmJZzpt5smVJ6AbI3f2CLnPMMN6cCN+QdoicR8fcR8SzwCWrniOhGImIu8FxK6cG8s1TojOKw54tqeAjhTsDBEXF3RNwWER/MO1AFDgZeSik9nneQHpwFfKv4/+ofqZ1REd09Aswt3p9HDb5fdfvcX7fvVxbRYSAixpMNxzir229xa0pKaX1xOEYLsG9xuF5NiYhjgRUppcV5Z6nQgSmlvYGjyYZoHJJ3oDJGAXsD56eU9gLepsaHjkTEaLI3osvzzlJK8QPcccAMYBtgXER8Mt9UpaWUlgL/j+w3yzcCD5INMdIIFBFfJfv7vzjvLD1JKX01pTSNLOcZeecppfiLna9Sw0W5m/OB95GdovMC8E+5pilvFDCJbPjj/wYuKx5xrGWnUKO/OO3kT4EvFf9ffYniKKkadCrZZ6rFwARgTc55uqiXz/2VsIjWuYhoIvvHeHFKqVbOC+hRcUjmrdTmebgHAnMj4ingUuCwiPjPfCOVl1J6vni7guw8htxP/C+jDWjrdBT8CrJiWsuOBu5LKb2Ud5AyPgL8LqW0MqW0luy8oANyzlRWSuknKaW9U0qHkA2DquXf2gO8FBFbAxRva2JoXr2LiE8DxwKfSPVz/bj/okaG5pXwPrJfRj1YfN9qAe6LiK1yTVVGSuml4i+lNwAXUtvvWQuKpxXdQzZCqiYmgSqleHrGicB/552lF5+m4xzWy6nRv/+U0mMppSNTSvuQlfsn8s7Urszn/rp9v7KI1rHib+d+AixNKX077zw9iYip7TMkRsRYsg/Rj+UaqoSU0l+llFpSStPJhmX+MqVUk0eZImJcRExovw8cSTacpOaklF4Eno2InYurDgcezTFSJWr9t8vPAPtFxCbFnwWHU6MTQAFExBbF2+3IPjDV8vcW4FqyD00Ub6/JMcuwEBFzgC8Dc1NK7+SdpyfdJtOaSw2+XwGklB5OKW2RUppefN9qA/Yu/sytOe0flotOoEbfs4CrgcMAImInYDTwcp6BevER4LGUUlveQXrxPPDh4v3DqNFfSHZ6v2oA/hr4Yb6JMj187q/b96tReQeoRRFxCTAbmBIRbcDfpJRqcfjAgcAfAQ93mq77KzUyC113WwP/HhGNZL8AuSylVNOXRqkDWwJXFUcLjQL+K6V0Y76RevRnwMXFIa9PAp/NOU9ZxeFuRwB/kneWclJKd0fEFcB9ZMMc7wcuyDdVj66MiMnAWuCLKaVX8w7UrtTPfOCbZMPxPkdW+ufll7BDmayrgO8DU4HrI+KBlNJR+aUsm/OvgDHALcWfW3ellE7PLWRRmazHFH9xtgF4Gsg9J9TV55Ny39fZEbEn2fwGT1EDP2PL5LwIuKh4SY81wKdr4Qh+D3//NTefQZnv6+eB7xWP4K4Gcp/bokzO8RHxxeIuC4B/yyledyU/91Oj71eViBr4fyVJkiRJGkEcmitJkiRJqiqLqCRJkiSpqiyikiRJkqSqsohKkiRJkqrKIipJkiRJqiqLqCRJkiSpqiyikiRJkqSqsohKkiRJkqrq/wO1kcABVtVEkQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 1152x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "N = 20\n",
    "plt.figure(figsize=(16, 5));\n",
    "plt.plot(range(1, N+1), [1/n for n in range(1, N+1)], c=\"b\", label=\"1/x\");\n",
    "plt.legend();\n",
    "plt.xticks(range(1, N+1, 1));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Note that the metrics related to **Recall** are not used in general because it is easy to achieve a recall of 100% by returning all documents for a query."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graded labels\n",
    "\n",
    "### nDCG@k: Normalized Discounted Cumulative Gain\n",
    "\n",
    "To understand nDCG, first let's look at CG i.e. Cumulative Gain. We simply add up the relevance scores for top k documents returned for a query.\n",
    "\n",
    "$$ CG@k(q) = \\sum_{i=1}^k rel(q)_i $$\n",
    "\n",
    "| ![](assets/cg@k.png) | \n",
    "|:--:| \n",
    "| Fig. 3. Illustration of CumulativeGain@k for evaluating IR models. |\n",
    "\n",
    "Note that CG does not take into account the position of the document. For example consider the models A and B where model A outputs `[5,2,4,0,1]` and model B outputs `[2,0,5,1,4]`; both the models get the same score `CG@5=12`.\n",
    "\n",
    "DCG i.e. Discounted Cumulative Gain improves on CG by adding a discounting factor for each position.\n",
    "\n",
    "$$ DCG@k(q) = \\sum_{i=1}^k \\frac{rel(q)_i}{log_2(i+1)} $$\n",
    "\n",
    "𝑟𝑒𝑙(𝑞)𝑖 - Graded relevance of doc at position i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from typing import List\n",
    "\n",
    "import pandas as pd\n",
    "\n",
    "\n",
    "def _get_dcg_at_k(scores: List[int]) -> pd.DataFrame:\n",
    "    cols = [\"position(i)\", \"relevance(i)\", \"log2(i+1)\", \"relevance(i) / log2(i+1)\"]\n",
    "\n",
    "    data = []\n",
    "    for i, score in enumerate(scores):\n",
    "        position = i + 1\n",
    "        data.append((position, score, math.log2(position+1), score / math.log2(position+1)))\n",
    "\n",
    "    return pd.DataFrame(data, columns=cols)\n",
    "\n",
    "\n",
    "def get_dcg_at_k(scores: List[int]) -> None:\n",
    "    df = _get_dcg_at_k(scores)\n",
    "    \n",
    "    dcg_so_far = \"\"\n",
    "    for i, dcg in enumerate(df[\"relevance(i) / log2(i+1)\"]):\n",
    "        if not dcg_so_far:\n",
    "            dcg_so_far = f\"{dcg:2.2f}\"\n",
    "        else:\n",
    "            dcg_so_far = f\"{dcg_so_far} + {dcg:2.2f}\"\n",
    "        print(f\"DCG@{i+1} = {dcg_so_far:<32} = {eval(dcg_so_far):2.2f}\")\n",
    "    \n",
    "    return df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can compare the results from the two models A and B we mentioned earlier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DCG@1 = 5.00                             = 5.00\n",
      "DCG@2 = 5.00 + 1.26                      = 6.26\n",
      "DCG@3 = 5.00 + 1.26 + 2.00               = 8.26\n",
      "DCG@4 = 5.00 + 1.26 + 2.00 + 0.00        = 8.26\n",
      "DCG@5 = 5.00 + 1.26 + 2.00 + 0.00 + 0.39 = 8.65\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>position(i)</th>\n",
       "      <th>relevance(i)</th>\n",
       "      <th>log2(i+1)</th>\n",
       "      <th>relevance(i) / log2(i+1)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>5.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1.584963</td>\n",
       "      <td>1.261860</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>2.000000</td>\n",
       "      <td>2.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "      <td>2.321928</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>2.584963</td>\n",
       "      <td>0.386853</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   position(i)  relevance(i)  log2(i+1)  relevance(i) / log2(i+1)\n",
       "0            1             5   1.000000                  5.000000\n",
       "1            2             2   1.584963                  1.261860\n",
       "2            3             4   2.000000                  2.000000\n",
       "3            4             0   2.321928                  0.000000\n",
       "4            5             1   2.584963                  0.386853"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_dcg_at_k([5, 2, 4, 0, 1])  # model A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DCG@1 = 2.00                             = 2.00\n",
      "DCG@2 = 2.00 + 0.00                      = 2.00\n",
      "DCG@3 = 2.00 + 0.00 + 2.50               = 4.50\n",
      "DCG@4 = 2.00 + 0.00 + 2.50 + 0.43        = 4.93\n",
      "DCG@5 = 2.00 + 0.00 + 2.50 + 0.43 + 1.55 = 6.48\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>position(i)</th>\n",
       "      <th>relevance(i)</th>\n",
       "      <th>log2(i+1)</th>\n",
       "      <th>relevance(i) / log2(i+1)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>2.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "      <td>1.584963</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>5</td>\n",
       "      <td>2.000000</td>\n",
       "      <td>2.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>2.321928</td>\n",
       "      <td>0.430677</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>4</td>\n",
       "      <td>2.584963</td>\n",
       "      <td>1.547411</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   position(i)  relevance(i)  log2(i+1)  relevance(i) / log2(i+1)\n",
       "0            1             2   1.000000                  2.000000\n",
       "1            2             0   1.584963                  0.000000\n",
       "2            3             5   2.000000                  2.500000\n",
       "3            4             1   2.321928                  0.430677\n",
       "4            5             4   2.584963                  1.547411"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_dcg_at_k([2, 0, 5, 1, 4])  # model B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DCG solves the problem with CG but it also has a drawback, it can't be used to compare queries/models that return different number of results.\n",
    "For example consider query A and B where query A returns `[5,2,4]` query B returns `[5,2,4,0,1]`;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DCG@1 = 5.00                             = 5.00\n",
      "DCG@2 = 5.00 + 1.26                      = 6.26\n",
      "DCG@3 = 5.00 + 1.26 + 2.00               = 8.26\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>position(i)</th>\n",
       "      <th>relevance(i)</th>\n",
       "      <th>log2(i+1)</th>\n",
       "      <th>relevance(i) / log2(i+1)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>5.00000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1.584963</td>\n",
       "      <td>1.26186</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>2.000000</td>\n",
       "      <td>2.00000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   position(i)  relevance(i)  log2(i+1)  relevance(i) / log2(i+1)\n",
       "0            1             5   1.000000                   5.00000\n",
       "1            2             2   1.584963                   1.26186\n",
       "2            3             4   2.000000                   2.00000"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_dcg_at_k([5, 2, 4])  # query A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DCG@1 = 5.00                             = 5.00\n",
      "DCG@2 = 5.00 + 1.26                      = 6.26\n",
      "DCG@3 = 5.00 + 1.26 + 2.00               = 8.26\n",
      "DCG@4 = 5.00 + 1.26 + 2.00 + 0.00        = 8.26\n",
      "DCG@5 = 5.00 + 1.26 + 2.00 + 0.00 + 0.39 = 8.65\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>position(i)</th>\n",
       "      <th>relevance(i)</th>\n",
       "      <th>log2(i+1)</th>\n",
       "      <th>relevance(i) / log2(i+1)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>5.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>1.584963</td>\n",
       "      <td>1.261860</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>2.000000</td>\n",
       "      <td>2.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "      <td>2.321928</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>2.584963</td>\n",
       "      <td>0.386853</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   position(i)  relevance(i)  log2(i+1)  relevance(i) / log2(i+1)\n",
       "0            1             5   1.000000                  5.000000\n",
       "1            2             2   1.584963                  1.261860\n",
       "2            3             4   2.000000                  2.000000\n",
       "3            4             0   2.321928                  0.000000\n",
       "4            5             1   2.584963                  0.386853"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_dcg_at_k([5, 2, 4, 0, 1])  # query B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Query B got higher DCG because it returned 5 documents whereas query A only returned 3. We can't say that query B was better than query A.\n",
    "nDCG fixes this issue by adding a normalization factor on top of DCG.\n",
    "\n",
    "$$ nDCG@k(Q) = \\frac{1}{|Q|} * \\sum_{q\\in Q} \\frac{DCG@k(q)}{DCG@k(sorted(rel(q)))} $$\n",
    "\n",
    "|Q| - Number of queries\n",
    "\n",
    "The normalization factor 𝐷𝐶𝐺@𝑘(𝑠𝑜𝑟𝑡𝑒𝑑(𝑟𝑒𝑙(𝑞))) is the Ideal DCG@k. This is calculated by sorting the graded relevance scores returned for a query and then calculating the DCG@k. nDCG@k always lie between 0 and 1.\n",
    "\n",
    "Now we can compare queries/models with different number of results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DCG@1 = 5.00                             = 5.00\n",
      "DCG@2 = 5.00 + 2.52                      = 7.52\n",
      "DCG@3 = 5.00 + 2.52 + 1.00               = 8.52\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>position(i)</th>\n",
       "      <th>relevance(i)</th>\n",
       "      <th>log2(i+1)</th>\n",
       "      <th>relevance(i) / log2(i+1)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>5.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>4</td>\n",
       "      <td>1.584963</td>\n",
       "      <td>2.523719</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2.000000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   position(i)  relevance(i)  log2(i+1)  relevance(i) / log2(i+1)\n",
       "0            1             5   1.000000                  5.000000\n",
       "1            2             4   1.584963                  2.523719\n",
       "2            3             2   2.000000                  1.000000"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_dcg_at_k(sorted([5, 2, 4], reverse=True))  # Ideal DCG@k for query A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "nDCG@3 for query A = 8.26 / 8.52 = 0.9694"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DCG@1 = 5.00                             = 5.00\n",
      "DCG@2 = 5.00 + 2.52                      = 7.52\n",
      "DCG@3 = 5.00 + 2.52 + 1.00               = 8.52\n",
      "DCG@4 = 5.00 + 2.52 + 1.00 + 0.43        = 8.95\n",
      "DCG@5 = 5.00 + 2.52 + 1.00 + 0.43 + 0.00 = 8.95\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>position(i)</th>\n",
       "      <th>relevance(i)</th>\n",
       "      <th>log2(i+1)</th>\n",
       "      <th>relevance(i) / log2(i+1)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>5</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>5.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>4</td>\n",
       "      <td>1.584963</td>\n",
       "      <td>2.523719</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>2</td>\n",
       "      <td>2.000000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>2.321928</td>\n",
       "      <td>0.430677</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>0</td>\n",
       "      <td>2.584963</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   position(i)  relevance(i)  log2(i+1)  relevance(i) / log2(i+1)\n",
       "0            1             5   1.000000                  5.000000\n",
       "1            2             4   1.584963                  2.523719\n",
       "2            3             2   2.000000                  1.000000\n",
       "3            4             1   2.321928                  0.430677\n",
       "4            5             0   2.584963                  0.000000"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_dcg_at_k(sorted([5, 2, 4, 0, 1], reverse=True))  # Ideal DCG@k for query B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "nDCG@5 for query B = 8.65 / 8.95 = 0.9664"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## References\n",
    "\n",
    "[1] Sebastian Hofstätter. \"[Advanced Information Retrieval 2021 @ TU Wien](https://www.youtube.com/playlist?list=PLSg1mducmHTPZPDoal4m59pPxxsceXF-y)\"\n",
    "\n",
    "[2] Amit Chaudhary. https://amitness.com/2020/08/information-retrieval-evaluation"
   ]
  }
 ],
 "metadata": {
  "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}