Selecting Hyperparameters.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Selecting Hyperparameters\n",
    "\n",
    "We can't select the hyperparmeters using standard gradient descent as this will reveal private information about the training data. It is most likely that a form of Bayesian Optimisation might be optimal in selecting the hyperparameters.\n",
    "\n",
    "## Proposed solution\n",
    "\n",
    "We perform cross-validation using hyperparameters $\\lambda$ and $(\\varepsilon, \\delta)$-DP noise. Either by;\n",
    "- repeatedly sample from DP to get an estimate of its error\n",
    "- more efficiently we should compute the RMSE directly but include the DP noise in the error computation\n",
    "- (alternatively compute the log marginal likelihood, incorporating the DP noise).\n",
    "\n",
    "Regardless of what we do above the result is a value. For this value we need to bound the global sensitivity. If we consider the RMSE, we reason as follows:\n",
    "- We want to protect both the training and test(aka validation) data, so the method described in Kusner et al. (2015) doesn't work (that only protects the validation data).\n",
    "- The expression for the RMSE:\n",
    "\n",
    "$$ \\left(\\frac{1}{N} \\sum_{i=1}^{N}{(f_i-y_i)^2} \\right)^{\\frac{1}{2}} $$\n",
    "\n",
    "where $f$ and $y$ are the predictions and actual values for the validation set.\n",
    "\n",
    "We need to consider then how much effect the training data can have on the predictions $f_i$; this we already know as we add DP noise scaled accordingly. Specifically a change in a training point $j$ will cause $d \\mathbf{c}_j$ changes in the predictions. What effect will this have on the RSE? The RSE is effectively the distance between $\\mathbf{f}$ and $\\mathbf{y}$. The largest change in the distance will occur if the perturbation of $f$ occurs in the direction of $y$. The length of that perturbation is the length of $d \\mathbf{c}_j$. So we just need to find the longest vector $\\max_{k}  \\sqrt{\\sum_i d c_{ki}^2}$. The test points can also change, each by as a much as $d$. The worst case effect of these is to change the RSE by $d$.\n",
    "\n",
    "So the RSE can change by *either* as much as $\\max_{k}  \\sqrt{\\sum_i d c_{ki}^2}$ or $d$ (whichever's greater). We only are protecting one data point at a time, hence it is one or the other of these options.\n",
    "\n",
    "> Aside on BO: I don't see how to do BO as we want to make all the RSE value private to an extent, rather than just one... The problem is to do this the DP composition doesn't take into account the correlations between these points.\n",
    "\n",
    "Instead we'll compute the RSE for a series of lengthscales, then use the exponential mechanism to select the best.\n",
    "\n",
    "### Cross validation adjustment to the above\n",
    "\n",
    "The above reasoning was for one training set and one test set. If we know we're cross-validating a dataset, then we can make the following logical steps.\n",
    "\n",
    "1. First we restate the DP assumption that one data point has changed.\n",
    "2. This point will only have been included as a test point in one fold of the x-validation\n",
    "3. In this case it could cause up to $d$ change in the RSE.\n",
    "4. In the other cases it can cause $s = \\max_{k}  \\sqrt{\\sum_i d c_{ki}^2}$ - this is a different value for each fold\n",
    "5. We should therefore pick, of the K-folds, the $K-1$ largest (i.e. discard the smallest) values of s.\n",
    "6. We should add this to the effect it can have on the situation in which it is in the test set (so add $d$).\n",
    "\n",
    "This would be the total sensitivity of the sum of the RSEs from the K folds.\n",
    "\n",
    "### Exponential Mechanism Recap\n",
    "\n",
    "Utility function (in our case this is the RSE) $u(x,r)$, where $x$ is the database and $r$ is an item in the range that we're interested in. E.g. the price we are querying. We only care about the sensitivity of the utility function wrt the database, it doesn't care about the range argument (the values over which you're testing).\n",
    "\n",
    "$$\\Delta u \\triangleq max_{r \\in R} max_{x,y} |u(x,r)-u(y,r)|$$ (where $x$ and $y$ are neighbouring databases).\n",
    "\n",
    "The exponential mechanism selects an element $r$ with probability proportional to:\n",
    "\n",
    "$$\\exp \\left( \\frac{\\varepsilon u(x,r)}{2 \\Delta u} \\right)$$\n",
    "\n",
    "## Summary\n",
    "\n",
    "We can immediately apply the exponential mechanism to the values of RSE and their sensitivities to pick a lengthscale.\n",
    "\n",
    "> ! I'm a bit confused by using RSE rather than RMSE - in particular that the number of folds will affect the RSE (but I guess not the RMSE), which is probably not ideal. I maybe should rework through the sensitivity analysis for RMSE instead, and use that."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alternative solutions\n",
    "\n",
    "### Compute Log marginal likelihood with DP noise\n",
    "\n",
    "- instead of LOO X-validated RMSE, we should computing log (marginal) likelihoods of the model fit, incorporating the DP noise into the likelihood \"data fit\" term (first term);\n",
    "\n",
    "$$\\log p(\\mathbf{y}|X,\\mathbf{y}) = -\\frac{1}{2}\\mathbf{y}^\\top K_y^{-1} \\mathbf{y} - \\frac{1}{2} \\log \\left|K_y \\right| - \\frac{n}{2} \\log {2 \\pi}$$\n",
    "\n",
    "where $K_y = K_f + \\sigma_n^2 I$. This could, presumably be done, by modifying $K_y$? \n",
    "\n",
    "So we note that we found the above log likelihood by combining, $y | f \\sim N(f, \\sigma_n I)$ and $f | X \\sim N(0, K)$. So we can extend this by noting that y is now $N(f, \\sigma_n I) + c N(0, M)$ where $M$ is the covariance in the DP noise. So we could make the datafit term above $-\\frac{1}{2}\\mathbf{y}^\\top \\left(K_y + c M \\right)^{-1} \\mathbf{y}$. Is this correct??\n",
    "\n",
    "\n"
   ]
  },
  {
   "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}