conformal-prediction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9a6cea41-9c51-4c33-80df-72737d5226ac",
   "metadata": {},
   "source": [
    "# Conformal Prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28a0a438-801b-4321-9ae0-68aad0dab4ff",
   "metadata": {},
   "source": [
    "References:\n",
    "\n",
    "+ Angelopoulos, A.N., S. Bates, A. Fisch, L. Lei, T. Schuster, 2022. Conformal Risk Control, https://arxiv.org/abs/2208.02814\n",
    "+ Barber, R.F., E.J. Candes, A. Ramdas, and R.J. Tibshirani, 2022. Conformal prediction beyond exchangeability, https://arxiv.org/abs/2202.13415\n",
    "+ Papadopoulos, H., K. Proedrou, V. Vovk, and A. Gammerman, 2002. Inductive Confidence Machines for Regression. In: Elomaa, T., Mannila, H., Toivonen, H. (eds) Machine Learning: ECML 2002. ECML 2002. Lecture Notes in Computer Science, vol 2430. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36755-1_29\n",
    "+ Shafer and Vovk, 2008. A Tutorial on Conformal Prediction, _Journal of Machine Learning Research, 9_, 371-421."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55011588-d3a8-4df5-9553-3dbebbf1a9e1",
   "metadata": {},
   "source": [
    "Basic problem set up: we observe items sequentially. Each item has a label, $y$, which could be numerical or categorical.\n",
    "There is some black-box model that makes a prediction $\\hat{y}$ of the value of $y$ for the next item, \n",
    "generally using side information $x$ (e.g., covariates).\n",
    "The predictor can \"learn\" from previous cases (also called _examples_): it does not have to stay the same over time.\n",
    "After each prediction $\\hat{y}$ is made, the true label $y$ is revealed.\n",
    "Thus,  $(x_1, y_1), \\ldots, (x_{n−1}, y_{n−1})$ and $x_n$ are available to predict $y_n$.\n",
    "\n",
    "Given an acceptable error probability $\\epsilon$, the goal is to construct a \"prediction region\" $\\Gamma^\\epsilon$ of labels that contains the label of the next item with probability at least $1-\\epsilon$.\n",
    "A $1-\\epsilon$ prediction region is _valid_ if it contains the truth at least $1-\\epsilon$ of the time.\n",
    "\n",
    "Conformal prediction works for any prediction method: regression, Bayesian modeling, support-vector machines, neural networks, etc. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5a3e699-1582-48f4-91e2-ca372bfc95ef",
   "metadata": {},
   "source": [
    "Recall [the definition of a _multiset_ or _bag_](./math-foundations.ipynb#Multisets): like a set, a bag is a collection of things, but unlike a set, it can contain multiple copies of the same thing. It amounts to an unordered list.\n",
    "We will use $\\llcorner \\cdot \\lrcorner$ to denote a bag."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9fc7066-b694-49da-8e58-4662f59dcc02",
   "metadata": {},
   "source": [
    "The basic assumption of conformal prediction is that the cases are _exchangeable_, which is true if they are IID, but not quite as restrictive as IID. \n",
    "(There has been work on weakening that assumption: see, e.g., Foygel et al., 2022.)\n",
    "\n",
    "One definition of exchangability of a finite set of random variables $\\{Z_1, \\ldots, Z_n\\}$ is that their joint probability distribution is invariant under permutations of the labels. That is, the distribution of $(Z_1, \\ldots, Z_n)$ is the same as the distribution $(Z_{\\pi_1}, \\ldots, Z_{\\pi_n})$ for every permutation $\\pi$ of $\\{1, \\ldots, n\\}$.\n",
    "An infinite series of random variables $Z_1, Z_2, \\ldots$ is exchangable if the finite collection $\\{Z_1, \\ldots, Z_n\\}$\n",
    "is exchangeable for every $n$.\n",
    "\n",
    "Shafer & Vovk also define exchangeability using a betting protocol, as follows.\n",
    "\n",
    "### Backward-Looking Betting Protocol (Shaver & Vovk, 2008)\n",
    "\n",
    "Two players, Alice & Bob.\n",
    "+ $\\mathcal{K}_N := 1$.\n",
    "+ Alice announces a bag $\\mathcal{B}_N$ of size $N$.\n",
    "+ for $n = N, N−1, \\ldots, , 2, 1$:\n",
    "    + Bob bets on $z_n$ at odds set by $\\mathbb{P} \\{z_n = a || \\mathcal{B}_n = \\llcorner a_1, \\ldots, a_n \\lrcorner \\} = k/n$, where $k$ is the number of times $a$ occurs in $\\mathcal{B}_n$.\n",
    "    + Alice announces $z_n \\in \\mathcal{B}_n$\n",
    "    + $\\mathcal{K}_{n−1} :=  \\mathcal{K}_n$ plus Bob's winnings on $z_n$\n",
    "    + $\\mathcal{B}_{n−1} := \\mathcal{B}_n \\setminus \\llcorner z_n \\lrcorner$\n",
    "Bob's moves are constrained to guarantee that his capital $\\mathcal{K}_n$ will be nonnegative for all $n$, no matter how Alice\n",
    "moves.\n",
    "\n",
    "Shafer & Vovk define exchangeability as saying that Bob will not multiply his initial capital $\\mathcal{K}_N$ by a\n",
    "large factor in this game."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "760a552e-4964-468d-a814-8d1a593ba1ee",
   "metadata": {},
   "source": [
    "Shafer & Vovk consider two cases, one of which is a special case of the other:\n",
    "\n",
    "1. Predict using old examples alone. Just before observing $z_n$,  predict it \n",
    "using the previous examples $(z_1, \\ldots , z_{n−1})$.\n",
    "\n",
    "2. Predict using features (covariates) of the new example. Each example $z_i = (x_i, y_i)$, where $x_i$ is side information\n",
    "and $y_i$ is a label. The data are $x_1, y_1, \\ldots , x_N, y_N$. Just before observing $y_n$, we predict it from $x_n$ and $(z_i)_{i=1}^{n-1}$. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ee08515-8dd8-49ea-8945-b8f01fad7185",
   "metadata": {},
   "source": [
    "An essential ingredient in conformal prediction is a measure of _nonconformity_ between an _example_ $z$ and a bag $\\mathcal{B}$ of other examples, a real-valued function $A(\\mathcal{B}, z)$.\n",
    "If there is a distance function defined on examples, $d(z, z')$, the nonconformity measure could be \n",
    "defined using the distance between a point estimator $\\hat{z}$ and the example:\n",
    "\\begin{equation}\n",
    "A(\\mathcal{B}, z) := d(\\hat{z}(\\mathcal{B}), z).\n",
    "\\end{equation}\n",
    "In general, the precision of prediction regions (\"size\") depends on the nonconformity measure, but the _validity_ of the prediction regions (the chance the regions contain the next observation) will not.\n",
    "Moreover, the prediction regions generated by conformal prediction are invariant under monotone increasing\n",
    "transformations of $A$.\n",
    "Hence, in this approach to constructing a nonconformity measure, the particular choice of distance measures $d(\\cdot, \\cdot)$ \n",
    "is less important than the choice of point predictors $\\hat{z}$.\n",
    "\n",
    "If the labels are real numbers, one\n",
    "could define $A(\\mathcal{B}, z)$ in a number of simple ways, such as\n",
    "\\begin{equation}\n",
    " A(\\mathcal{B}, z) := |\\bar{z}_{\\mathcal{B}} - z|,\n",
    "\\end{equation}\n",
    "where $\\bar{z}_{\\mathcal{B}} := (\\sum_{a \\in {\\mathcal{B}}} a)/|{\\mathcal{B}}|$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26ddbb71-c507-4282-936f-6f805ce9d572",
   "metadata": {},
   "source": [
    "## Conformal prediction algorithm without covariates (Shafer & Vovk)\n",
    "\n",
    "Input: Nonconformity measure $A$, significance level $\\epsilon$, examples $z_1, \\ldots, z_{n-1}$,\n",
    "example $z$.\n",
    "\n",
    "Task: Decide whether to include $z$ in $\\gamma^\\epsilon(z_1, \\ldots, z_{n−1})$.\n",
    "\n",
    "Algorithm:\n",
    "1. Provisionally set $z_n := z$.\n",
    "2. For $i = 1, \\ldots,n$, set $\\alpha_i := A( \\llcorner z_1, \\ldots ,z_n \\lrcorner \\setminus \\llcorner z_i \\lrcorner, ,z_i)$.\n",
    "3. Set $p_z := \\frac{1}{n}\\left | \\left \\{i \\in \\{1, \\ldots, n\\}: \\alpha_i \\ge \\alpha_n \\right \\} \\right |$.\n",
    "4. Include $z$ in $\\gamma^\\epsilon(z_1, \\ldots ,z_{n−1})$ iff $p_z > \\epsilon$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93ea2841-9233-47f2-9e6c-d7796ad0eaf1",
   "metadata": {},
   "source": [
    "## Conformal prediction with covariates (Shafer & Vovk)\n",
    "\n",
    "Input: Nonconformity measure $A$, significance level $\\epsilon$, examples $z_1, \\ldots, z_{n-1}$,\n",
    "object $x_n$, example $z$.\n",
    "\n",
    "Task: Decide whether to include $z$ in $\\Gamma^\\epsilon(z_1, \\ldots, z_{n−1})$.\n",
    "\n",
    "Algorithm:\n",
    "1. Provisionally set $z_n := z$.\n",
    "2. For $i = 1, \\ldots,n$, set $\\alpha_i := A( \\llcorner z_1, \\ldots ,z_n \\lrcorner \\setminus \\llcorner z_i \\lrcorner, ,z_i)$.\n",
    "3. Set $p_z := \\frac{1}{n}\\left | \\left \\{i \\in \\{1, \\ldots, n\\}: \\alpha_i \\ge \\alpha_n \\right \\} \\right |$.\n",
    "4. Include $z$ in $\\Gamma^\\epsilon(z_1, \\ldots ,z_{n−1})$ iff $p_z > \\epsilon$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6d25d55-a43b-466d-bcba-db5ee52962e9",
   "metadata": {},
   "source": [
    "The proof that conformal prediction sets have their claimed coverage probability\n",
    "is at its core the same argument we've used to show that (hits$+1$)/(reps$+1$) is a valid $P$-value in permutation tests: if the data are exchangeable, every permutation of the nonconformance values (including the value for the final observation, which uses $z$ as a trial value) is equally likely.\n",
    "If that value of $z$ would make the last point's nonconformance value be too far in the tails to be plausible--that is, if the $P$-value of the hypothesis of exchangability based on the nonconformance values using that value of $z$ is too small--don't include that value of $z$ in the prediction set."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39d7f773-1abe-445c-a5c5-b578fb5c7ff4",
   "metadata": {},
   "source": [
    "## Optimality of conformal prediction (Shafer & Vovk, 2008)\n",
    "\n",
    "Conformal prediction regions have a number of properties:\n",
    "\n",
    "1. The predictions are invariant with respect to the ordering of previous examples: they depend on the nonconformity measure, the confidence level, and the _bag_ of previous examples.\n",
    "\n",
    "2. The probability that the prediction includes the truth is at least the nominal confidence level. \n",
    "For every integer $n>0$ and every exchangeable probability distribution for $z_1, \\ldots, z_n$, \n",
    "\\begin{equation}\n",
    "\\mathbb{P} \\{z_n \\in \\gamma^\\epsilon(\\llcorner z_1, \\ldots, z_{n-1} \\lrcorner) \\} \\ge 1-\\epsilon.\n",
    "\\end{equation}\n",
    "3. The prediction regions are nested: If $\\epsilon_1 \\le \\epsilon_2$, $\\gamma^{\\epsilon_1}(B) \\subset \\gamma^{\\epsilon_2}(B)$. \n",
    "\n",
    "**Lemma.** (Shafer & Vovk, Lemma 1)  \n",
    "Suppose $\\gamma$ is a procedure for creating prediction regions that satisfies the three conditions above, that $\\llcorner a_1, \\ldots , a_n \\lrcorner$ is a bag of examples, and \n",
    "$0 < \\epsilon \\le 1$. \n",
    "Then $n\\epsilon$ or fewer of the $n$ elements of the bag satisfy\n",
    "\\begin{equation}\n",
    "    a_i \\notin \\gamma^\\epsilon(\\llcorner a_1, \\ldots , a_n \\lrcorner \\setminus \\llcorner a_i \\lrcorner). \n",
    "    \\tag{1} \\label{lemma:1}\n",
    "\\end{equation}\n",
    "\n",
    "**Proof.**  \n",
    "Consider the unique exchangeable probability distribution for $(z_1, \\ldots, z_n)$ that gives probability\n",
    "1 to the bag $\\llcorner z_1, \\ldots, z_n \\lrcorner = \\llcorner a_1, \\ldots, a_n \\lrcorner$. \n",
    "For that distribution, each element of $\\llcorner a_1, \\ldots, a_n\\lrcorner$ is equally likely to be $z_n$,\n",
    "and (\\ref{lemma:1}) is an error if it occurs.\n",
    "Since the second condition says that the chance of an error is at most $\\epsilon$, the\n",
    "fraction of elements of $\\llcorner a_1, \\ldots , a_n \\lrcorner \\setminus \\llcorner a_i \\lrcorner$ for which (\\ref{lemma:1}) occurs cannot exceed $\\epsilon$. $\\Box$\n",
    "\n",
    "### Tightening conformal prediction regions\n",
    "\n",
    "The lemma provides a way to show how to alter a nonconformity measure to get tighter prediction regions.\n",
    "Suppose we have a prediction region $\\gamma^\\epsilon$.\n",
    "If $z \\notin \\gamma^\\delta(B)$, it means that the predictor has confidence at least $1-\\delta$ that $z$ is different enough from $B$ that it won't be the next value.\n",
    "We can measure nonconformity using that \"confidence.\"\n",
    "The largest $1−\\delta$ for which $z \\notin \\gamma^\\delta(B)$ is a natural nonconformity measure:\n",
    "\\begin{equation}\n",
    "A(B,z) := \\sup \\{1−\\delta | z \\notin \\gamma^\\delta(B) \\}.\n",
    "\\end{equation}\n",
    "Consider the prediction set $\\gamma_A^\\epsilon$ based on that nonconformity measure.\n",
    "Then $\\gamma_A^\\epsilon(B) \\subset \\gamma^\\epsilon(B)$.\n",
    "To see that, suppose $z \\in \\gamma_A^\\epsilon(\\llcorner z_1, \\ldots, z_{n-1} \\lrcorner)$.\n",
    "That means that when the algorithm sets $z_n := z$, strictly more than\n",
    "$n\\epsilon$ of the scores \n",
    "\\begin{equation}\n",
    "    \\alpha_i := \\sup\\{1−\\delta | z_i \\notin \\gamma^\\delta( \\llcorner z_1, \\ldots, z_n \\lrcorner ) \\}, \\;\\; \n",
    "    i=1, \\ldots, n\n",
    "\\end{equation}\n",
    "are greater than or equal to $\\alpha_n$.\n",
    "Since the prediction regions $\\gamma$ produces are nested by confidence level, if $z_n \\notin \\gamma^\\epsilon(\\llcorner z_1, \\ldots, z_{n-1} \\lrcorner)$, then $z_i \\notin \\gamma^\\epsilon( \\llcorner z_1, \\ldots, z_n \\lrcorner \\setminus \\llcorner z_i \\lrcorner )$ for strictly more than $n\\epsilon$ of the elements of $\\llcorner z_i \\lrcorner_{i=1}^n$, contradicting the lemma."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "353b5f85-3a4c-4d4f-97c4-713d56df87a9",
   "metadata": {},
   "source": [
    "## Extensions of conformal prediction\n",
    "\n",
    "+ Weakening assumptions: assuming only exchangeability within labels (Shafer & Vovk, 2008)\n",
    "\n",
    "+ Split conformal prediction (Papadopoulos et al., 2002)\n",
    "    - It's computationally expensive to re-fit the model after each example.\n",
    "    - Instead, split the sample into a training set (used to fit the model) and a calibration set (used to approximate the distribution of the nonconformity measure).\n",
    "    \n",
    "+ Balancing errors on subgroups \n",
    "    - Ensure, for instance, that the chance that the prediction set does not contain the true label is controlled for each possible value of the true label, or that the chance that the prediction set does not contain the true label is controlled for different subsets of the covariates.\n",
    "\n",
    "+ Conformal _risk_ control. (Angelopoulos et al., 2022) \n",
    "    - Instead of guaranteeing $\\mathbb{P} \\{ z_n \\in \\gamma(\\llcorner z_1, \\ldots, z_{n-1} \\lrcorner) \\} \\ge 1-\\epsilon$, guarantee that $\\mathbb{E} \\ell(\\gamma(\\llcorner z_1, \\ldots, z_{n-1} \\lrcorner), z_n) \\le \\epsilon$ for any bounded _loss function_ $\\ell$ that decreases as $\\gamma$ grows. \n",
    "\n",
    "+ Conformal prediction without exchangeability (Barber et al., 2022). Uses weights on examples. The coverage is approximate, not conservative, but they bound the error in the confidence level in terms of the total variation distance between the distribution of the bag of previous examples and the distributuion of the current example.\n",
    "    - distributional drifts: give more weight to more recent examples\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be5d66bf-a8cc-4857-9fa5-7d8799f9e449",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}