optimal.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This document describes the optimal submission to [Kaggle's](https://www.kaggle.com) [Second Annual Data Science Bowl](https://www.kaggle.com/c/second-annual-data-science-bowl). The goal of this document is to minimize the [evaluation score](https://www.kaggle.com/c/second-annual-data-science-bowl/details/evaluation) of the competition, which is Continuous Ranked Probability Score (CRPS) assuming you some how have access to the real distribution of values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Finding the optimal submission without variational calculus\n",
    "Suppose the real distribution is $p_v$ of the $M$ (600) possible volume options. Such that (starting from 1 and not from 0)\n",
    "\n",
    "$\\sum^M_{v=1}p_v = 1$\n",
    "\n",
    "you want to make a submission $Q_n$ which can be written as sum of $q_j$\n",
    "\n",
    "$Q_n = \\sum^n_{j=1} q_j$\n",
    "\n",
    "in order for the submission to be valid you are constrained to have $q_j \\ge 0$ and\n",
    "\n",
    "$\\sum^M_{j=1}q_j = 1$\n",
    "\n",
    "the goal is to minimize the cost for a real value $v$\n",
    "\n",
    "$C_v = {1\\over M} \\sum_n \\left( Q_n - H(n \\ge v) \\right)^2$\n",
    "\n",
    "were $H(\\mbox{true}) = 1$ and $H(\\mbox{false}) = 0$.\n",
    "\n",
    "The $v$ values are distributed according to $p_v$ so without knowing the $v$ value we want to minimize\n",
    "\n",
    "$C = E_{p_v} (C_v)$\n",
    "\n",
    "we minimize $C$ by changing the $q_j$ values as long as the constraint is meet. For example we can change a specific location, $w$, in $q_j$ and see when the derivative vanish. You can argue that changing just one value will violate the constraint but this can be relaxed by adding a Lagrange multiplier, $\\lambda$, to the goal:\n",
    "\n",
    "$C = E_{p_v} (C_v) + \\lambda \\sum_j q_j$\n",
    "\n",
    "However, as we will soon see this addition cancels out so you can safely ignore it in this problem. So lets compute the derivative and set it to zero\n",
    "\n",
    "${ \\partial C \\over \\partial q_w } = E_{p_v} \\left( \\sum_n 2 (Q_n -H(n \\ge v )) H(n \\ge w)\\right) + \\lambda = 0$\n",
    "\n",
    "we can cancel out the $2$ if we re-write $\\lambda$ to include it and if we use $E_{p_v}(1) = 1$ we get\n",
    "\n",
    "$\\sum_{n=w} Q_n - E_{p_v} \\left( \\sum_n H(n \\ge v ) H(n \\ge w)\\right) + \\lambda = 0$\n",
    "\n",
    "using $\\sum_{n=1}^M H(n \\ge v ) H(n \\ge w) = M - \\max(v,w)$ we get\n",
    "\n",
    "$\\sum_{n=w} Q_n - M + \\sum_v \\left( p_v \\max(v,w) \\right) + \\lambda = 0$\n",
    "\n",
    "we can repeat this formila for $w+1$\n",
    "\n",
    "$\\sum_{n=w+1} Q_n - M + \\sum_v \\left( p_v \\max(v,w+1) \\right) + \\lambda = 0$\n",
    "\n",
    "and subtract the two equations to get\n",
    "\n",
    "$Q_w - \\sum_{v=1}^w p_v = 0$\n",
    "\n",
    "as promised $\\lambda$ disappeared and we are left with the result that the submission should be the cumulative distribution function (cdf) of whatever you think the true distribution is ($P_w = \\sum_{v=1}^w p_v$)\n",
    "\n",
    "\n",
    "$Q_w = P_w$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# code for generating optimal submission\n",
    "Without additional information about each example, the distribution could be derived directly from the values in the training set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "train = pd.read_csv('train.csv')\n",
    "def doHist(data):\n",
    "    h = np.zeros(600)\n",
    "    for j in np.ceil(data.values).astype(int):\n",
    "        h[j:] += 1\n",
    "    h /= len(data)\n",
    "    return h\n",
    "hSystole = doHist(train.Systole)\n",
    "hDiastole = doHist(train.Diastole)\n",
    "sub = pd.read_csv('sample_submission_validate.csv', index_col='Id')\n",
    "N = len(sub)//2\n",
    "X = np.zeros((2*N,600))\n",
    "for i in range(N):\n",
    "    X[2*i,:] = hDiastole\n",
    "    X[2*i+1,:] = hSystole\n",
    "sub[sub.columns] = X\n",
    "sub.to_csv('submission.csv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "which gave a score of $0.042738$ on the validation set, which just happens to be a very popular result on the leader board (as of December 16, 2015)\n",
    "\n",
    "![Leader Board](./kaggleLB.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}