{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "# Regression metrics\n",
    "from sklearn.metrics import mean_absolute_error, mean_squared_error, r2_score\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "np.random.seed(17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Intro"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Leaderboard probing ** - it's a competition specific technick tightly connected with data leakages. There are two tipes of LB probing:\n",
    "* extraction ground thruth from public part of LB by changing small subset of predictions in submission;\n",
    "* extraction information about private part of LB by submitting to public LB (based on consistent categories).\n",
    "\n",
    "In this tutorial we will concentrate on the first type of probing. In some cases specific exploit makes possible to find all y-values of the public leaderboard (LB) score. In other cases we can obtain some imformation about public LB y-values distribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating test environment functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we are going to create some functions, which will help us in testing exploits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_leaderboards(values):\n",
    "    \"\"\"\n",
    "    Generate public and private leaderboard from values.\n",
    "    \"\"\"\n",
    "    df = pd.DataFrame(values, columns=[\"target\"])\n",
    "    public_lb, private_pb = train_test_split(df, test_size=0.3, shuffle=False)\n",
    "\n",
    "    return public_lb, private_pb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_submission(values, leaderboard):\n",
    "    \"\"\"\n",
    "    Generate sample submission from values for leaderboard.\n",
    "    \"\"\"\n",
    "    sample_submission = pd.DataFrame(leaderboard, copy=True)\n",
    "    sample_submission[\"target\"] = values\n",
    "\n",
    "    return sample_submission"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_data(values):\n",
    "    \"\"\"\n",
    "    Generate experimental environment: public and private leaderboards, zero sample submissio from values.\n",
    "    \"\"\"\n",
    "    public_lb, private_pb = generate_leaderboards(values)\n",
    "    zero_submission = generate_submission(0, public_lb)\n",
    "    n = public_lb.size\n",
    "\n",
    "    return public_lb, private_pb, zero_submission, n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_submission(predicted_values, metric, leaderboard):\n",
    "    \"\"\"\n",
    "    Evaluate predicted values with metric for leaderboard.\n",
    "    \"\"\"\n",
    "    return metric(leaderboard[\"target\"], predicted_values[\"target\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regression evaluation metrics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We gonna iterate through several main regression metrics and find some vulnerabilities related to each of them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. MAE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's start with mean absolute error metric:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{MAE(y, \\hat{y}) = \\frac{\\sum_{i=1}^n |y_i - \\hat{y}_i|}{n} }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "where \n",
    "- $y$ - vector with true components;\n",
    "- $y_i$ - true y-value; \n",
    "- $\\hat{y}$ - vector with predicted (i.e. submitted) values;\n",
    "- $\\hat{y_i}$ - predicted y-value;\n",
    "- $n$ - number of data points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In case of all target values are **non negative** we can make zero submission to **obtain mean target value**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{MAE(y, 0) = \\frac{\\sum_{i=1}^n |y_i - 0|}{n} = \\frac{\\sum_{i=1}^n y_i}{n} }$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate environment with non negative target values\n",
    "target_values = np.random.randint(0, 10, size=1000)\n",
    "public_lb, private_lb, sample_submission, n = generate_data(target_values)\n",
    "\n",
    "sample_submission.head(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make zero submission\n",
    "p_z = make_submission(sample_submission, mean_absolute_error, public_lb)\n",
    "print(\"Zero submission score:\", p_z)\n",
    "print(\"Public leaderbord target mean:\", public_lb[\"target\"].mean())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using this information we can modify our predictions to improve public LB score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. MSE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next probing method makes possible to **find all y-values** for all data points used in computation of public LB score. Now we will talk about mean squared error:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "$$\\large{ MSE(y, \\hat{y}) = \\frac{\\sum_{i=1}^n (y_i - \\hat{y}_i)^2}{n} }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At first, let's make all zeros submission and denote result score as $p_z$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ p_{z} = \\frac{\\sum_{i=1}^n (y_i - 0)^2}{n} } = \\frac{(y_1 - 0)^2}{n} + \\frac{\\sum_{i=2}^n (y_i - 0)^2}{n}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate environment\n",
    "target_values = np.random.randint(-10, 10, size=1000)\n",
    "public_lb, private_lb, sample_submission, n = generate_data(target_values)\n",
    "\n",
    "sample_submission.head(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make zero submission\n",
    "p_z = make_submission(sample_submission, mean_squared_error, public_lb)\n",
    "print(\"Zero submission score:\", p_z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Other submissions will contain exactly one value differs from zero submission. Here we will change first y-value from 0 to 100:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Set first y-value to 100\n",
    "sample_submission[\"target\"][0] = 100\n",
    "sample_submission.head(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We make a new submission where 1st y-value set to 100 and denote result score as $p^1_{100}$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ \\large{ p_{100}^{1} = \\frac{(y_1 - 100)^2}{n} + \\frac{\\sum_{i=2}^n (y_i - 0)^2}{n} }$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p_1_100 = make_submission(sample_submission, mean_squared_error, public_lb)\n",
    "print(\"Submission score:\", p_1_100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we have a system of last two equations ($p_z$ and $p^1_{100}$) which can be solved over $y_1$, by subtracting one from another:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ y_1 = \\frac{100^2 - n*(p_{100}^1 - p_{z})}{2*100}  }$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate y_1\n",
    "y1 = (100 ** 2 - n * (p_1_100 - p_z)) / 200\n",
    "print(\"Obtained y_1:\", y1)\n",
    "print(\"Actual y_1:\", public_lb[\"target\"][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More generally we can obtain $y_i$ by this formula:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ y_i = \\frac{100^2 - n*(p_{100}^i - p_{z})}{2*100}  }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, for $y_2$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Set second y-value to 100\n",
    "sample_submission[\"target\"][0] = 0\n",
    "sample_submission[\"target\"][1] = 100\n",
    "\n",
    "# Make submission\n",
    "p_2_100 = make_submission(sample_submission, mean_squared_error, public_lb)\n",
    "\n",
    "# Calculate y_2\n",
    "y2 = (100 ** 2 - n * (p_2_100 - p_z)) / 200\n",
    "print(\"Obtained y_2:\", y2)\n",
    "print(\"Actual y_2:\", public_lb[\"target\"][1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, in this method we can use exactly one LB probe in order to get the true y-value (up to numerical accuracy) of one data point. It's worth mentioning, that applying such technic for mean absolute error metric (MAE) and root mean squared metric (RMSE) also makes possible to find all y-values for all data points used in computation of public LB score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. R squared (the coefficient of determination)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vulnerability related to $R^2$ metric allows us to find **variance of public LB** and **find all y-values** for all data points used in computation of public LB score. Metric definition:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ R^2(y, \\hat{y}) = 1 - \\frac{\\sum_{i=1}^n (y_i - \\hat{y}_i)^2}{\\sum_{i=1}^n (y_i - \\bar{y}_i)^2} }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The denominator in this formula is called total sum of squares, which proportional to the variance of the data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ S_{tot} = \\sum_{i=1}^n (y_i - \\bar{y}_i)^2 }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look on the variance formula:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ Var(y) = \\frac{\\sum_{i=1}^n (y_i - \\bar{y}_i)^2}{n} = \\frac{S_{tot}}{n} }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, if we can find $S_{tot}$ in $R^2$ metric, then we can obtain the variance of public LB."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As always, let's start with zero submission:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ p_z = 1 - \\frac{\\sum_{i=1}^n (y_i - 0)^2}{S_{tot}} = 1 - \\frac{y_1^2}{S_{tot}} - \\frac{\\sum_{i=2}^n (y_i - 0)^2}{S_{tot}} }$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Generate environment\n",
    "data = np.random.randint(-15, 15, size=1000)\n",
    "public_lb, private_pb, sample_submission, n = generate_data(data)\n",
    "\n",
    "sample_submission.head(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make zero submission\n",
    "p_z = make_submission(sample_submission, r2_score, public_lb)\n",
    "print(\"Zero submission score:\", p_z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Second probe will be with 1st y-value set to 100 (no suprise here):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ p^1_{100} = 1 - \\frac{(y_1 - 100)^2}{S_{tot}} - \\frac{\\sum_{i=2}^n (y_i - 0)^2}{S_{tot}} }$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Set first y-value to 100\n",
    "sample_submission[\"target\"][0] = 100\n",
    "sample_submission.head(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make submission\n",
    "p_1_100 = make_submission(sample_submission, r2_score, public_lb)\n",
    "print(\"Submission score:\", p_1_100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As in the previous example, now we have a system of last two equations ($p_z$ and $p^1_{100}$) which can be solved over $y_1$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ y_1 = \\frac{S_{tot}(p^1_{100} - p_z) + 100^2}{2*100} }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But, the only left unknown is $S_{tot}$, which can be calculated with one more submission. So we will make a submission with 1st y-value set to 200."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ p^1_{200} = 1 - \\frac{(y_1 - 200)^2}{S_{tot}} - \\frac{\\sum_{i=2}^n (y_i - 0)^2}{S_{tot}} }$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Set first y-value to 200\n",
    "sample_submission[\"target\"][0] = 200\n",
    "sample_submission.head(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make submission\n",
    "p_1_200 = make_submission(sample_submission, r2_score, public_lb)\n",
    "print(\"Submission score:\", p_1_200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then combine equation with $p_z$ and $p^1_{200}$ into system and solve it over $y_1$ (similary to provious step):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ y_1 = \\frac{S_{tot}(p^1_{200} - p_z) + 200^2}{2*200} }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we have two equations that can be solved over $S_{tot}$, by excluding $y_1$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ S_{tot} = \\frac{200^2 - 2*100^2}{2*p^1_{100} - p_z - p^1_{200}} }$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate total sum of squares\n",
    "s_tot = (200.0 ** 2 - 2 * 100.0 ** 2) / (2 * p_1_100 - p_z - p_1_200)\n",
    "print(\"Total sum of squares:\", s_tot)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we are ready to calculate the variance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate variance\n",
    "var_y = s_tot / n\n",
    "print(\"Obtained variance of public LB:\", var_y)\n",
    "print(\"Actual variance:\", public_lb[\"target\"].var(ddof=0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And $y_1$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate y_1\n",
    "y1 = (s_tot * (p_1_100 - p_z) + 100 ** 2) / (2 * 100.0)\n",
    "print(\"Obtained y_1:\", y1)\n",
    "print(\"Actual y_1:\", public_lb[\"target\"][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Having now $S_{tot}$ we can find $y_i$ by this formula:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\large{ y_i = \\frac{S_{tot}(p^i_{100} - p_z) + 100^2}{2*100} }$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So base idea behind all of described methods is to making submissions which defferent by one value from each other and then solving equations (mostly by substracting one from another).\n",
    "\n",
    "Knowledge obtained by described methods cannot be used to directly improve result in private LB, since we cannot probe the y-values from there. However if public and private LB data cames from the same distribution, obtained mean or variance of public LB can be useful.\n",
    "\n",
    "And, of course, obtaining all y-values methods are limited by some number of submissions per day."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. [Mean absolute error](https://en.wikipedia.org/wiki/Mean_absolute_error)\n",
    "2. [Mean squared error](https://en.wikipedia.org/wiki/Mean_squared_error)\n",
    "3. [Coefficient of determination](https://en.wikipedia.org/wiki/Coefficient_of_determination)\n",
    "4. [How to get the exact y-values of all data points used for the computation of the public leaderboard score in the ”Mercedes-Benz Greener Manufacturing” competition on Kaggle](https://crowdstats.eu/Kaggle_MercedesBenz_LBprobing.pdf)\n",
    "5. [How to Win a Data Science Competition: Learn from Top Kagglers (Week 2)](https://www.coursera.org/learn/competitive-data-science?specialization=aml)\n",
    "6. [The \"Perfect Score\" Script](https://www.kaggle.com/olegtrott/the-perfect-score-script)"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}