Data+leakages.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Version 1.0.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this programming assignment we will illustrate a very severe data leakage, that can often be found in competitions, where the pairs of object should be scored, e.g. predict $1$ if two objects belong to the same class and $0$ otherwise. \n",
    "\n",
    "The data in this assignment is taken from a real competition, and the funniest thing is that *we will not use training set at all* and achieve almost 100% accuracy score! We will just exploit the leakage.\n",
    "\n",
    "Now go through the notebook and complete the assignment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd \n",
    "import scipy.sparse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Load the data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's load the test data. Note, that we don't have any training data here, just test data. Moreover, *we will not even use any features* of test objects. All we need to solve this task is the file with the indices for the pairs, that we need to compare."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's load the data with test indices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>pairId</th>\n",
       "      <th>FirstId</th>\n",
       "      <th>SecondId</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>1427</td>\n",
       "      <td>8053</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>17044</td>\n",
       "      <td>7681</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>19237</td>\n",
       "      <td>20966</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>8005</td>\n",
       "      <td>20765</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>16837</td>\n",
       "      <td>599</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>5</td>\n",
       "      <td>3657</td>\n",
       "      <td>12504</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>6</td>\n",
       "      <td>2836</td>\n",
       "      <td>7582</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>7</td>\n",
       "      <td>6136</td>\n",
       "      <td>6111</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>8</td>\n",
       "      <td>23295</td>\n",
       "      <td>9817</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>9</td>\n",
       "      <td>6621</td>\n",
       "      <td>7672</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   pairId  FirstId  SecondId\n",
       "0       0     1427      8053\n",
       "1       1    17044      7681\n",
       "2       2    19237     20966\n",
       "3       3     8005     20765\n",
       "4       4    16837       599\n",
       "5       5     3657     12504\n",
       "6       6     2836      7582\n",
       "7       7     6136      6111\n",
       "8       8    23295      9817\n",
       "9       9     6621      7672"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test = pd.read_csv('../readonly/data_leakages_data/test_pairs.csv')\n",
    "test.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, we can think that there is a test dataset of images, and each image is assigned a unique `Id` from $0$ to $N-1$ (N -- is the number of images). In the dataframe from above `FirstId` and `SecondId` point to these `Id`'s and define pairs, that we should compare: e.g. do both images in the pair belong to the same class or not. So, for example for the first row: if images with `Id=1427` and `Id=8053` belong to the same class, we should predict $1$, and $0$ otherwise. \n",
    "\n",
    "But in our case we don't really care about the images, and how exactly we compare the images (as long as comparator is binary).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**We suggest you to try to solve the puzzle yourself first.** You need to submit a `.csv` file with columns `pairId` and `Prediction` to the grader. The number of submissions allowed is made pretty huge to let you explore the data without worries. The returned score should be very close to $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**If you do not want to think much** -- scroll down and follow the instructions below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# EDA and leakage intuition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we already know, the key to discover data leakages is careful EDA. So let's start our work with some basic data exploration and build an intuition about the leakage."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, check, how many different `id`s are there: concatenate `FirstId` and `SecondId` and print the number of unique elements. Also print minimum and maximum value for that vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of unique elements:  368509\n",
      "Max combined Id:  2632312000\n",
      "Min combined Id:  137\n"
     ]
    }
   ],
   "source": [
    "# YOUR CODE GOES HERE\n",
    "test['Id_combined'] = test['FirstId'].astype('str') + test['SecondId'].astype('str')\n",
    "test['Id_combined'] = test['Id_combined'].astype(int)\n",
    "\n",
    "print('Number of unique elements: ', len(test.Id_combined.unique()))\n",
    "print('Max combined Id: ', test.Id_combined.max())\n",
    "print('Min combined Id: ', test.Id_combined.min())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and then print how many pairs we need to classify (it is basically the number of rows in the test set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "368550"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# YOUR CODE GOES HERE\n",
    "len(test.pairId)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now print, how many distinct pairs it would be possible to create out of all \"images\" in the dataset?   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of unique pairs from all the images  in test dataset:  346489650\n"
     ]
    }
   ],
   "source": [
    "# YOUR CODE GOES HERE\n",
    "import math\n",
    "\n",
    "def nCr(n,r):\n",
    "    f = math.factorial\n",
    "    return f(n) // f(r) // f(n-r)\n",
    "\n",
    "a =len(np.union1d(test['FirstId'].unique() , test['SecondId'].unique())) ## Unique number of images in test dataset.\n",
    "print('Number of unique pairs from all the images  in test dataset: ',nCr(a ,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So the number of pairs we are given to classify is very very small compared to the total number of pairs. \n",
    "\n",
    "To exploit the leak we need to **assume (or prove)**, that the total number of positive pairs is small, compared to the total number of pairs. For example: think about an image dataset with $1000$ classes, $N$ images per class. Then if the task was to tell whether a pair of images belongs to the same class or not, we would have $1000\\frac{N(N-1)}{2}$ positive pairs, while total number of pairs was $\\frac{1000N(1000N - 1)}{2}$.\n",
    "\n",
    "Another example: in [Quora competitition](https://www.kaggle.com/c/quora-question-pairs) the task was to classify whether a pair of qustions are duplicates of each other or not. Of course, total number of question pairs is very huge, while number of duplicates (positive pairs) is much much smaller."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Finally, let's get a fraction of pairs of class `1`. We just need to submit a constant prediction \"all ones\" and check the returned accuracy. Create a dataframe with columns `pairId` and `Prediction`, fill it and export it to `.csv` file. Then submit to grader and examine grader's output. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# YOUR CODE GOES HERE\n",
    "sub = pd.DataFrame({'pairId': test.pairId})\n",
    "sub['Prediction'] = 1\n",
    "sub.to_csv('submission.csv', index=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, we assumed the total number of pairs is much higher than the number of positive pairs, but it is not the case for the test set. It means that the test set is constructed not by sampling random pairs, but with a specific sampling algorithm. Pairs of class `1` are oversampled.\n",
    "\n",
    "Now think, how we can exploit this fact? What is the leak here? If you get it now, you may try to get to the final answer yourself, othewise you can follow the instructions below.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Building a magic feature"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section we will build a magic feature, that will solve the problem almost perfectly. The instructions will lead you to the correct solution, but please, try to explain the purpose of the steps we do to yourself -- it is very important."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Incidence matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we need to build an [incidence matrix](https://en.wikipedia.org/wiki/Incidence_matrix). You can think of pairs `(FirstId, SecondId)` as of edges in an undirected graph. \n",
    "\n",
    "The incidence matrix is a matrix of size `(maxId + 1, maxId + 1)`, where each row (column) `i` corresponds `i-th` `Id`. In this matrix we put the value `1` to the position `[i, j]`, if and only if a pair `(i, j)` or `(j, i)` is present in  a given set of pais `(FirstId, SecondId)`. All the other elements in the incidence matrix are zeros.   \n",
    "\n",
    "**Important!** The incidence matrices are typically very very sparse (small number of non-zero values). At the same time incidence matrices are usually huge in terms of total number of elements, and it is **impossible to store them in memory in dense format**. But due to their sparsity incidence matrices **can be easily represented as sparse matrices**. If you are not familiar with sparse matrices, please see [wiki](https://en.wikipedia.org/wiki/Sparse_matrix) and [scipy.sparse reference](https://docs.scipy.org/doc/scipy/reference/sparse.html). Please, use any of `scipy.sparse` constructors to build incidence matrix. \n",
    "\n",
    "For example, you can use this constructor: `scipy.sparse.coo_matrix((data, (i, j)))`. We highly recommend to learn to use different `scipy.sparse` constuctors, and matrices types, but if you feel you don't want to use them, you can always build this matrix with a simple `for` loop. You will need first to create a matrix using `scipy.sparse.coo_matrix((M, N), [dtype])` with an appropriate shape `(M, N)` and then iterate through `(FirstId, SecondId)` pairs and fill corresponding elements in matrix with ones. \n",
    "\n",
    "**Note**, that the matrix should be symmetric and consist only of zeros and ones. It is a way to check yourself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = test.FirstId.append(test.SecondId)\n",
    "\n",
    "cols = test.SecondId.append(test.FirstId)\n",
    "\n",
    "rows_cols = pd.concat([rows, cols], axis=1)\n",
    "\n",
    "rows_cols = rows_cols.drop_duplicates()\n",
    "\n",
    "data = np.ones(rows_cols.shape[0], dtype=int)\n",
    "\n",
    "inc_mat = scipy.sparse.coo_matrix((data, (rows_cols[0], rows_cols[1])), dtype=int) # YOUR CODE GOES HERE (but probably you will need to write few more lines before)\n",
    "\n",
    "# Sanity checks\n",
    "assert inc_mat.max() == 1\n",
    "assert inc_mat.sum() == 736872"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is convenient to have matrix in `csr` format eventually."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "inc_mat = inc_mat.tocsr()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Now build the magic feature"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why did we build the incidence matrix? We can think of the rows in this matix as of representations for the objects. `i-th` row is a representation for an object with `Id = i`. Then, to measure similarity between two objects we can measure similarity between their representations. And we will see, that such representations are very good."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now select the rows from the incidence matrix, that correspond to `test.FirstId`'s, and `test.SecondId`'s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Note, scipy goes crazy if a matrix is indexed with pandas' series. \n",
    "# So do not forget to convert `pd.series` to `np.array`\n",
    "# These lines should normally run very quickly \n",
    "\n",
    "\n",
    "rows_FirstId   = inc_mat[test.FirstId.values,:]# YOUR CODE GOES HERE\n",
    "rows_SecondId  = inc_mat[test.SecondId.values,:]# YOUR CODE GOES HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our magic feature will be the *dot product* between representations of a pair of objects. Dot product can be regarded as similarity measure -- for our non-negative representations the dot product is close to 0 when the representations are different, and is huge, when representations are similar. \n",
    "\n",
    "Now compute dot product between corresponding rows in `rows_FirstId` and `rows_SecondId` matrices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Note, that in order to do pointwise multiplication in scipy.sparse you need to use function `multiply`\n",
    "# regular `*` corresponds to matrix-matrix multiplication\n",
    "\n",
    "f = rows_FirstId.multiply(rows_SecondId)  # YOUR CODE GOES HERE\n",
    "\n",
    "f = f.sum(axis=1)\n",
    "\n",
    "f = np.squeeze(np.asarray(f))\n",
    "# Sanity check\n",
    "assert f.shape == (368550, )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That is it! **We've built our magic feature.** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# From magic feature to binary predictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But how do we convert this feature into binary predictions? We do not have a train set to learn a model, but we have a piece of information about test set: the baseline accuracy score that you got, when submitting constant. And we also have a very strong considerations about the data generative process, so probably we will be fine even without a training set. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may try to choose a thresold, and set the predictions to 1, if the feature value `f` is higer than the threshold, and 0 otherwise. What threshold would you choose? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How do we find a right threshold? Let's first examine this feature: print frequencies (or counts) of each value in the feature `f`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[14 15 19 20 21 28 35]\n"
     ]
    }
   ],
   "source": [
    "# For example use `np.unique` function, check for flags\n",
    "\n",
    "print (np.unique(f))# YOUR CODE GOES HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do you see how this feature clusters the pairs? Maybe you can guess a good threshold by looking at the values? \n",
    "\n",
    "In fact, in other situations it can be not that obvious, but in general to pick a threshold you only need to remember the score of your baseline submission and use this information. Do you understand why and how?  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Choose a threshold below: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "pred = f > 15# SET THRESHOLD HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Finally, let's create a submission"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "submission = test.loc[:,['pairId']]\n",
    "submission['Prediction'] = pred.astype(int)\n",
    "\n",
    "submission.to_csv('submission.csv', index=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now submit it to the grader! It is not possible to submit directly from this notebook, as we need to submit a `csv` file, not a single number (limitation of Coursera platform). \n",
    "\n",
    "To download `submission.csv` file that you've just produced <a href='./submission.csv'>click here</a> (if the link opens in browser, right-click on it and shoose \"Save link as\"). Then go to [assignment page](https://www.coursera.org/learn/competitive-data-science/programming/KsASv/data-leakages/submission) and submit your `.csv` file in 'My submission' tab.\n",
    "\n",
    "\n",
    "If you did everything right, the score should be very high."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Finally:** try to explain to yourself, why the whole thing worked out. In fact, there is no magic in this feature, and the idea to use rows in the incidence matrix can be intuitively justified."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bonus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interestingly, it is not the only leak in this dataset. There is another totally different way to get almost 100% accuracy. Try to find it!"
   ]
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}