{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-classification-md-1 fw=all -->\n",
    "\n",
    "# Generalization in Classification\n",
    "\n",
    "\n",
    "So far, we have focused on how to tackle multiclass classification problems\n",
    "by training (linear) neural networks with multiple outputs and softmax functions.\n",
    "Interpreting our model's outputs as probabilistic predictions,\n",
    "we motivated and derived the cross-entropy loss function,\n",
    "which calculates the negative log likelihood\n",
    "that our model (for a fixed set of parameters)\n",
    "assigns to the actual labels.\n",
    "And finally, we put these tools into practice\n",
    "by fitting our model to the training set.\n",
    "However, as always, our goal is to learn *general patterns*,\n",
    "as assessed empirically on previously unseen data (the test set).\n",
    "High accuracy on the training set means nothing.\n",
    "Whenever each of our inputs is unique\n",
    "(and indeed this is true for most high-dimensional datasets),\n",
    "we can attain perfect accuracy on the training set\n",
    "by just memorizing the dataset on the first training epoch,\n",
    "and subsequently looking up the label whenever we see a new image.\n",
    "And yet, memorizing the exact labels\n",
    "associated with the exact training examples\n",
    "does not tell us how to classify new examples.\n",
    "Absent further guidance, we might have to fall back\n",
    "on random guessing whenever we encounter new examples.\n",
    "\n",
    "A number of burning questions demand immediate attention:\n",
    "\n",
    "1. How many test examples do we need to give a good estimate of the accuracy of our classifiers on the underlying population?\n",
    "1. What happens if we keep evaluating models on the same test repeatedly?\n",
    "1. Why should we expect that fitting our linear models to the training set\n",
    "   should fare any better than our naive memorization scheme?\n",
    "\n",
    "\n",
    "Whereas that section introduced\n",
    "the basics of overfitting and generalization\n",
    "in the context of linear regression,\n",
    "this chapter will go a little deeper,\n",
    "introducing some of the foundational ideas\n",
    "of statistical learning theory.\n",
    "It turns out that we often can guarantee generalization *a priori*:\n",
    "for many models,\n",
    "and for any desired upper bound\n",
    "on the generalization gap $t$,\n",
    "we can often determine some required number of samples $n$\n",
    "such that if our training set contains at least $n$\n",
    "samples, our empirical error will lie\n",
    "within $t$ of the true error,\n",
    "*for any data generating distribution*.\n",
    "Unfortunately, it also turns out\n",
    "that while these sorts of guarantees provide\n",
    "a set of intellectual building blocks,\n",
    "they are of limited practical utility\n",
    "to the deep learning practitioner.\n",
    "In short, these guarantees suggest\n",
    "that ensuring generalization\n",
    "of deep neural networks *a priori*\n",
    "requires an absurd number of examples\n",
    "(perhaps trillions or more),\n",
    "even when we find that, on the tasks we care about,\n",
    "deep neural networks typically generalize\n",
    "well with far fewer examples (thousands).\n",
    "Thus deep learning practitioners often forgo\n",
    "*a priori* guarantees altogether,\n",
    "instead employing methods\n",
    "that have generalized well\n",
    "on similar problems in the past,\n",
    "and certifying generalization *post hoc*\n",
    "through empirical evaluations.\n",
    "When we get to that section,\n",
    "we will revisit generalization\n",
    "and provide a light introduction\n",
    "to the vast scientific literature\n",
    "that has sprung in attempts\n",
    "to explain why deep neural networks generalize in practice.\n",
    "\n",
    "## The Test Set\n",
    "\n",
    "Since we have already begun to rely on test sets\n",
    "as the gold standard method\n",
    "for assessing generalization error,\n",
    "let's get started by discussing\n",
    "the properties of such error estimates.\n",
    "Let's focus on a fixed classifier $f$,\n",
    "without worrying about how it was obtained.\n",
    "Moreover suppose that we possess\n",
    "a *fresh* dataset of examples $\\mathcal{D} = {(\\mathbf{x}^{(i)},y^{(i)})}_{i=1}^n$\n",
    "that were not used to train the classifier $f$.\n",
    "The *empirical error* of our classifier $f$ on $\\mathcal{D}$\n",
    "is simply the fraction of instances\n",
    "for which the prediction $f(\\mathbf{x}^{(i)})$\n",
    "disagrees with the true label $y^{(i)}$,\n",
    "and is given by the following expression:\n",
    "\n",
    "$$\\epsilon_{\\mathcal{D}}(f) = \\frac{1}{n}\\sum_{i=1}^n \\mathbf{1}(f(\\mathbf{x}^{(i)}) \\neq y^{(i)}).$$\n",
    "\n",
    "By contrast, the *population error*\n",
    "is the *expected* fraction\n",
    "of examples in the underlying population\n",
    "(some distribution $P(X,Y)$  characterized\n",
    "by probability density function $p(\\mathbf{x},y)$)\n",
    "for which our classifier disagrees\n",
    "with the true label:\n",
    "\n",
    "$$\\epsilon(f) =  E_{(\\mathbf{x}, y) \\sim P} \\mathbf{1}(f(\\mathbf{x}) \\neq y) =\n",
    "\\int\\int \\mathbf{1}(f(\\mathbf{x}) \\neq y) p(\\mathbf{x}, y) \\;d\\mathbf{x} dy.$$\n",
    "\n",
    "While $\\epsilon(f)$ is the quantity that we actually care about,\n",
    "we cannot observe it directly,\n",
    "just as we cannot directly\n",
    "observe the average height in a large population\n",
    "without measuring every single person.\n",
    "We can only estimate this quantity based on samples.\n",
    "Because our test set $\\mathcal{D}$\n",
    "is statistically representative\n",
    "of the underlying population,\n",
    "we can view $\\epsilon_{\\mathcal{D}}(f)$ as a statistical\n",
    "estimator of the population error $\\epsilon(f)$.\n",
    "Moreover, because our quantity of interest $\\epsilon(f)$\n",
    "is an expectation (of the random variable $\\mathbf{1}(f(X) \\neq Y)$)\n",
    "and the corresponding estimator $\\epsilon_{\\mathcal{D}}(f)$\n",
    "is the sample average,\n",
    "estimating the population error\n",
    "is simply the classic problem of mean estimation,\n",
    "which you may recall from that section.\n",
    "\n",
    "An important classical result from probability theory\n",
    "called the *central limit theorem* guarantees, under its standard conditions,\n",
    "that for independent, identically distributed samples $a_1, ..., a_n$\n",
    "with finite mean $\\mu$ and finite standard deviation $\\sigma$,\n",
    "then, as the number of samples $n$ approaches infinity,\n",
    "the sample average $\\hat{\\mu}$ approximately\n",
    "tends towards a normal distribution centered\n",
    "at the true mean and with standard deviation $\\sigma/\\sqrt{n}$.\n",
    "Already, this tells us something important:\n",
    "as the number of examples grows large,\n",
    "our test error $\\epsilon_{\\mathcal{D}}(f)$\n",
    "should approach the true error $\\epsilon(f)$\n",
    "at a rate of $\\mathcal{O}(1/\\sqrt{n})$.\n",
    "Thus, to estimate our test error twice as precisely,\n",
    "we must collect four times as large a test set.\n",
    "To shrink the uncertainty in our estimate a hundredfold,\n",
    "we must collect ten thousand times as large a test set.\n",
    "(Note that more test data never reduces the error itself,\n",
    "only our uncertainty about its value.)\n",
    "In general, such a rate of $\\mathcal{O}(1/\\sqrt{n})$\n",
    "is often the best we can hope for in statistics.\n",
    "\n",
    "Now that we know something about the asymptotic rate\n",
    "at which our test error $\\epsilon_{\\mathcal{D}}(f)$ converges to the true error $\\epsilon(f)$,\n",
    "we can zoom in on some important details.\n",
    "Recall that the random variable of interest\n",
    "$\\mathbf{1}(f(X) \\neq Y)$\n",
    "can only take values $0$ and $1$\n",
    "and thus is a Bernoulli random variable,\n",
    "characterized by a parameter\n",
    "indicating the probability that it takes value $1$.\n",
    "Here, $1$ means that our classifier made an error,\n",
    "so the parameter of our random variable\n",
    "is actually the true error rate $\\epsilon(f)$.\n",
    "The variance $\\sigma^2$ of a Bernoulli\n",
    "depends on its parameter (here, $\\epsilon(f)$)\n",
    "according to the expression $\\epsilon(f)(1-\\epsilon(f))$.\n",
    "A little investigation of this function\n",
    "reveals that our variance is highest\n",
    "when the true error rate is close to $0.5$\n",
    "and can be far lower when it is\n",
    "close to $0$ or close to $1$.\n",
    "This tells us that the asymptotic standard deviation\n",
    "of our estimate $\\epsilon_{\\mathcal{D}}(f)$ of the error $\\epsilon(f)$\n",
    "(over the choice of the $n$ test samples)\n",
    "cannot be any greater than $\\sqrt{0.25/n}$.\n",
    "\n",
    "If we ignore the fact that this rate characterizes\n",
    "behavior as the test set size approaches infinity\n",
    "rather than when we possess finite samples,\n",
    "this tells us that if we want our test error $\\epsilon_{\\mathcal{D}}(f)$\n",
    "to approximate the population error $\\epsilon(f)$\n",
    "such that one standard deviation corresponds\n",
    "to an interval of $\\pm 0.01$,\n",
    "then we should collect roughly 2500 samples.\n",
    "If we want to fit two standard deviations\n",
    "in that range and thus be 95% confident\n",
    "that $\\epsilon_{\\mathcal{D}}(f) \\in \\epsilon(f) \\pm 0.01$,\n",
    "then we will need 10,000 samples!\n",
    "\n",
    "This turns out to be the size of the test sets\n",
    "for many popular benchmarks in machine learning.\n",
    "You might be surprised to find out that thousands\n",
    "of applied deep learning papers get published every year\n",
    "making a big deal out of error rate improvements of $0.01$ or less.\n",
    "Of course, when the error rates are much closer to $0$,\n",
    "then an improvement of $0.01$ can indeed be a big deal.\n",
    "\n",
    "\n",
    "One pesky feature of our analysis thus far\n",
    "is that it really only tells us about asymptotics,\n",
    "i.e., how the relationship between $\\epsilon_{\\mathcal{D}}$ and $\\epsilon$\n",
    "evolves as our sample size goes to infinity.\n",
    "Fortunately, because our random variable is bounded,\n",
    "we can obtain valid finite sample bounds\n",
    "by applying an inequality due to @Hoeffding.1963,\n",
    "proved in that section:\n",
    "\n",
    "$$P\\left(|\\epsilon_{\\mathcal{D}}(f) - \\epsilon(f)| \\geq t\\right) < 2\\exp\\left( - 2n t^2 \\right).$$\n",
    "\n",
    "Solving for the smallest dataset size\n",
    "that would allow us to conclude\n",
    "with 95% confidence that the distance $t$\n",
    "between our estimate $\\epsilon_{\\mathcal{D}}(f)$\n",
    "and the true error rate $\\epsilon(f)$\n",
    "does not exceed $0.01$,\n",
    "you will find that roughly 18,500 examples are required,\n",
    "as compared with the 10,000 examples suggested\n",
    "by the asymptotic analysis above.\n",
    "If you go deeper into statistics\n",
    "you will find that this trend holds generally.\n",
    "Guarantees that hold even in finite samples\n",
    "are typically slightly more conservative.\n",
    "Note that in the scheme of things,\n",
    "these numbers are not so far apart,\n",
    "reflecting the general usefulness\n",
    "of asymptotic analysis for giving\n",
    "us ballpark figures even if they are not\n",
    "guarantees we can take to court.\n",
    "\n",
    "All of the above is pencil-and-paper reasoning,\n",
    "but it is also one short simulation away from being visible.\n",
    "Fix a classifier whose true error is $\\epsilon(f) = 0.1$\n",
    "and draw many hypothetical test sets:\n",
    "each per-example indicator is a Bernoulli$(0.1)$ coin,\n",
    "so a size-$n$ test set produces an estimate\n",
    "$\\epsilon_{\\mathcal{D}}(f) \\sim \\mathrm{Binomial}(n, 0.1)/n$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-classification-the-test-set-1"
   },
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "from d2l import torch as d2l"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-classification-md-2 fw=all -->\n",
    "\n",
    "We simulate 1000 such test sets at each size $n$, record the empirical spread\n",
    "(standard deviation) of the resulting error estimates, and compare it with the\n",
    "two envelopes derived above: the CLT prediction\n",
    "$\\sqrt{\\epsilon(1-\\epsilon)/n}$ and the 95% Hoeffding radius\n",
    "$\\sqrt{\\log(2/0.05)/(2n)}$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-classification-the-test-set-2"
   },
   "source": [
    "rng = np.random.default_rng(0)\n",
    "eps, trials = 0.1, 1000\n",
    "ns = np.array([100, 300, 1000, 3000, 10000])\n",
    "spread = np.array([(rng.binomial(n, eps, trials) / n).std() for n in ns])\n",
    "clt = np.sqrt(eps * (1 - eps) / ns)           # CLT standard deviation\n",
    "hoeff = np.sqrt(np.log(2 / 0.05) / (2 * ns))  # 95% Hoeffding radius\n",
    "d2l.plot(ns, [spread, clt, hoeff], 'test set size n', 'spread of the estimate',\n",
    "         legend=['simulated sd', 'CLT sd', 'Hoeffding 95% radius'],\n",
    "         xscale='log', yscale='log')"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"253.878125pt\" height=\"183.35625pt\" viewBox=\"0 0 253.878125 183.35625\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:40:40.678624</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 183.35625 \nL 253.878125 183.35625 \nL 253.878125 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 51.378125 145.8 \nL 246.678125 145.8 \nL 246.678125 7.2 \nL 51.378125 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 60.255398 145.8 \nL 60.255398 7.2 \n\" clip-path=\"url(#p397ee9d1cb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"mf9012837a1\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mf9012837a1\" x=\"60.255398\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- $\\mathdefault{10^{2}}$ -->\n      <g transform=\"translate(51.455398 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 149.028125 145.8 \nL 149.028125 7.2 \n\" clip-path=\"url(#p397ee9d1cb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#mf9012837a1\" x=\"149.028125\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- $\\mathdefault{10^{3}}$ -->\n      <g transform=\"translate(140.228125 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 237.800852 145.8 \nL 237.800852 7.2 \n\" clip-path=\"url(#p397ee9d1cb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#mf9012837a1\" x=\"237.800852\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- $\\mathdefault{10^{4}}$ -->\n      <g transform=\"translate(229.000852 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <defs>\n       <path id=\"m001166aec2\" d=\"M 0 0 \nL 0 2 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"51.652432\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"56.19338\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"86.978651\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_7\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"102.610753\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"113.701905\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_9\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"122.304871\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_10\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"129.334006\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_11\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"135.277056\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_12\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"140.425159\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_13\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"144.966108\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_14\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"175.751379\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_15\">\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"191.38348\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_16\">\n     <g id=\"line2d_19\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"202.474632\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_17\">\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"211.077599\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_18\">\n     <g id=\"line2d_21\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"218.106734\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_19\">\n     <g id=\"line2d_22\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"224.049783\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_20\">\n     <g id=\"line2d_23\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"229.197886\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_21\">\n     <g id=\"line2d_24\">\n      <g>\n       <use xlink:href=\"#m001166aec2\" x=\"233.738835\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_4\">\n     <!-- test set size n -->\n     <g transform=\"translate(114.154688 174.076563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-7a\" d=\"M 353 3500 \nL 3084 3500 \nL 3084 2975 \nL 922 459 \nL 3084 459 \nL 3084 0 \nL 275 0 \nL 275 525 \nL 2438 3041 \nL 353 3041 \nL 353 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(100.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(152.832031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(192.041016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(223.828125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(275.927734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(337.451172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(376.660156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(408.447266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(460.546875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-7a\" transform=\"translate(488.330078 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(540.820312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(602.34375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(634.130859 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_25\">\n      <path d=\"M 51.378125 99.711206 \nL 246.678125 99.711206 \n\" clip-path=\"url(#p397ee9d1cb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_26\">\n      <defs>\n       <path id=\"m40e089a8cd\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m40e089a8cd\" x=\"51.378125\" y=\"99.711206\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- $\\mathdefault{10^{-2}}$ -->\n      <g transform=\"translate(20.878125 103.510425) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-2212\" d=\"M 678 2272 \nL 4684 2272 \nL 4684 1741 \nL 678 1741 \nL 678 2272 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-2212\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(186.855469 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_27\">\n      <path d=\"M 51.378125 23.615564 \nL 246.678125 23.615564 \n\" clip-path=\"url(#p397ee9d1cb)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_28\">\n      <g>\n       <use xlink:href=\"#m40e089a8cd\" x=\"51.378125\" y=\"23.615564\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- $\\mathdefault{10^{-1}}$ -->\n      <g transform=\"translate(20.878125 27.414782) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-2212\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.855469 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_29\">\n      <defs>\n       <path id=\"m7b85582412\" d=\"M 0 0 \nL -2 0 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"139.5\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_30\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"129.992707\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_31\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"122.618277\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_32\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"116.592929\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_33\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"111.49857\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_34\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"107.085636\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_9\">\n     <g id=\"line2d_35\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"103.193152\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_10\">\n     <g id=\"line2d_36\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"76.804135\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_11\">\n     <g id=\"line2d_37\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"63.404358\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_12\">\n     <g id=\"line2d_38\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"53.897064\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_13\">\n     <g id=\"line2d_39\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"46.522635\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_14\">\n     <g id=\"line2d_40\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"40.497287\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_15\">\n     <g id=\"line2d_41\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"35.402928\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_16\">\n     <g id=\"line2d_42\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"30.989993\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_17\">\n     <g id=\"line2d_43\">\n      <g>\n       <use xlink:href=\"#m7b85582412\" x=\"51.378125\" y=\"27.097509\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_7\">\n     <!-- spread of the estimate -->\n     <g transform=\"translate(14.798438 133.330469) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \nL 1159 -1331 \nL 581 -1331 \nL 581 3500 \nL 1159 3500 \nL 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nz\nM 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-66\" d=\"M 2375 4863 \nL 2375 4384 \nL 1825 4384 \nQ 1516 4384 1395 4259 \nQ 1275 4134 1275 3809 \nL 1275 3500 \nL 2222 3500 \nL 2222 3053 \nL 1275 3053 \nL 1275 0 \nL 697 0 \nL 697 3053 \nL 147 3053 \nL 147 3500 \nL 697 3500 \nL 697 3744 \nQ 697 4328 969 4595 \nQ 1241 4863 1831 4863 \nL 2375 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-68\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(115.576172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(154.439453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(215.962891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(277.242188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(340.71875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(372.505859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(433.6875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(468.892578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(500.679688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(539.888672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(603.267578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(664.791016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(696.578125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(758.101562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(810.201172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(849.410156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(877.193359 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(974.605469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(1035.884766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1075.09375 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_44\">\n    <path d=\"M 60.255398 63.749058 \nL 102.610753 80.531322 \nL 149.028125 102.422054 \nL 191.38348 120.02945 \nL 237.800852 139.043737 \n\" clip-path=\"url(#p397ee9d1cb)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_45\">\n    <path d=\"M 60.255398 63.404358 \nL 102.610753 81.557782 \nL 149.028125 101.452179 \nL 191.38348 119.605603 \nL 237.800852 139.5 \n\" clip-path=\"url(#p397ee9d1cb)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_46\">\n    <path d=\"M 60.255398 13.5 \nL 102.610753 31.653424 \nL 149.028125 51.547821 \nL 191.38348 69.701245 \nL 237.800852 89.595642 \n\" clip-path=\"url(#p397ee9d1cb)\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 51.378125 145.8 \nL 51.378125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 246.678125 145.8 \nL 246.678125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 51.378125 145.8 \nL 246.678125 145.8 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 51.378125 7.2 \nL 246.678125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"legend_1\">\n    <g id=\"patch_7\">\n     <path d=\"M 99.5375 59.234375 \nL 239.678125 59.234375 \nQ 241.678125 59.234375 241.678125 57.234375 \nL 241.678125 14.2 \nQ 241.678125 12.2 239.678125 12.2 \nL 99.5375 12.2 \nQ 97.5375 12.2 97.5375 14.2 \nL 97.5375 57.234375 \nQ 97.5375 59.234375 99.5375 59.234375 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_47\">\n     <path d=\"M 101.5375 20.298438 \nL 111.5375 20.298438 \nL 121.5375 20.298438 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_8\">\n     <!-- simulated sd -->\n     <g transform=\"translate(129.5375 23.798438) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(79.882812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(177.294922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(240.673828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(268.457031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(329.736328 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(368.945312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(430.46875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(493.945312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(525.732422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(577.832031 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_48\">\n     <path d=\"M 101.5375 34.976563 \nL 111.5375 34.976563 \nL 121.5375 34.976563 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_9\">\n     <!-- CLT sd -->\n     <g transform=\"translate(129.5375 38.476563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-43\" d=\"M 4122 4306 \nL 4122 3641 \nQ 3803 3938 3442 4084 \nQ 3081 4231 2675 4231 \nQ 1875 4231 1450 3742 \nQ 1025 3253 1025 2328 \nQ 1025 1406 1450 917 \nQ 1875 428 2675 428 \nQ 3081 428 3442 575 \nQ 3803 722 4122 1019 \nL 4122 359 \nQ 3791 134 3420 21 \nQ 3050 -91 2638 -91 \nQ 1578 -91 968 557 \nQ 359 1206 359 2328 \nQ 359 3453 968 4101 \nQ 1578 4750 2638 4750 \nQ 3056 4750 3426 4639 \nQ 3797 4528 4122 4306 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-4c\" d=\"M 628 4666 \nL 1259 4666 \nL 1259 531 \nL 3531 531 \nL 3531 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-54\" d=\"M -19 4666 \nL 3928 4666 \nL 3928 4134 \nL 2272 4134 \nL 2272 0 \nL 1638 0 \nL 1638 4134 \nL -19 4134 \nL -19 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-43\"/>\n      <use xlink:href=\"#DejaVuSans-4c\" transform=\"translate(69.824219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-54\" transform=\"translate(111.787109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(172.871094 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(204.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(256.757812 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_49\">\n     <path d=\"M 101.5375 49.654688 \nL 111.5375 49.654688 \nL 121.5375 49.654688 \n\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #008000; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_10\">\n     <!-- Hoeffding 95% radius -->\n     <g transform=\"translate(129.5375 53.154688) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-48\" d=\"M 628 4666 \nL 1259 4666 \nL 1259 2753 \nL 3553 2753 \nL 3553 4666 \nL 4184 4666 \nL 4184 0 \nL 3553 0 \nL 3553 2222 \nL 1259 2222 \nL 1259 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-39\" d=\"M 703 97 \nL 703 672 \nQ 941 559 1184 500 \nQ 1428 441 1663 441 \nQ 2288 441 2617 861 \nQ 2947 1281 2994 2138 \nQ 2813 1869 2534 1725 \nQ 2256 1581 1919 1581 \nQ 1219 1581 811 2004 \nQ 403 2428 403 3163 \nQ 403 3881 828 4315 \nQ 1253 4750 1959 4750 \nQ 2769 4750 3195 4129 \nQ 3622 3509 3622 2328 \nQ 3622 1225 3098 567 \nQ 2575 -91 1691 -91 \nQ 1453 -91 1209 -44 \nQ 966 3 703 97 \nz\nM 1959 2075 \nQ 2384 2075 2632 2365 \nQ 2881 2656 2881 3163 \nQ 2881 3666 2632 3958 \nQ 2384 4250 1959 4250 \nQ 1534 4250 1286 3958 \nQ 1038 3666 1038 3163 \nQ 1038 2656 1286 2365 \nQ 1534 2075 1959 2075 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-25\" d=\"M 4653 2053 \nQ 4381 2053 4226 1822 \nQ 4072 1591 4072 1178 \nQ 4072 772 4226 539 \nQ 4381 306 4653 306 \nQ 4919 306 5073 539 \nQ 5228 772 5228 1178 \nQ 5228 1588 5073 1820 \nQ 4919 2053 4653 2053 \nz\nM 4653 2450 \nQ 5147 2450 5437 2106 \nQ 5728 1763 5728 1178 \nQ 5728 594 5436 251 \nQ 5144 -91 4653 -91 \nQ 4153 -91 3862 251 \nQ 3572 594 3572 1178 \nQ 3572 1766 3864 2108 \nQ 4156 2450 4653 2450 \nz\nM 1428 4353 \nQ 1159 4353 1004 4120 \nQ 850 3888 850 3481 \nQ 850 3069 1003 2837 \nQ 1156 2606 1428 2606 \nQ 1700 2606 1854 2837 \nQ 2009 3069 2009 3481 \nQ 2009 3884 1853 4118 \nQ 1697 4353 1428 4353 \nz\nM 4250 4750 \nL 4750 4750 \nL 1831 -91 \nL 1331 -91 \nL 4250 4750 \nz\nM 1428 4750 \nQ 1922 4750 2215 4408 \nQ 2509 4066 2509 3481 \nQ 2509 2891 2217 2550 \nQ 1925 2209 1428 2209 \nQ 931 2209 642 2551 \nQ 353 2894 353 3481 \nQ 353 4063 643 4406 \nQ 934 4750 1428 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-48\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(75.195312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(136.376953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(197.900391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(233.105469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(268.310547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(331.787109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(359.570312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(422.949219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(486.425781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-39\" transform=\"translate(518.212891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(581.835938 0)\"/>\n      <use xlink:href=\"#DejaVuSans-25\" transform=\"translate(645.458984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(740.478516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(772.265625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(813.378906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(874.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(938.134766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(965.917969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(1029.296875 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p397ee9d1cb\">\n   <rect x=\"51.378125\" y=\"7.2\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-classification-md-3 fw=all -->\n",
    "\n",
    "On log--log axes all three curves are parallel lines of slope $-\\frac{1}{2}$:\n",
    "the $\\sqrt{n}$ law made visible. The simulated spread sits right on top of the\n",
    "CLT prediction, but the two envelopes are not measured on the same footing:\n",
    "the CLT curve is one standard deviation, while the Hoeffding curve is a\n",
    "two-sided 95% radius. Converting the CLT curve to its own 95% radius\n",
    "($1.96\\sigma$) closes most of the gap; the Hoeffding radius still runs about\n",
    "$2.3\\times$ above it, which is the price of a bound valid at every finite $n$\n",
    "rather than only asymptotically.\n",
    "\n",
    "## Test Set Reuse\n",
    "\n",
    "In some sense, you are now set up to succeed\n",
    "at conducting empirical machine learning research.\n",
    "Nearly all practical models are developed\n",
    "and validated based on test set performance\n",
    "and you are now a master of the test set.\n",
    "For any fixed classifier $f$,\n",
    "you know how to evaluate its test error $\\epsilon_{\\mathcal{D}}(f)$,\n",
    "and know precisely what can (and cannot)\n",
    "be said about its population error $\\epsilon(f)$.\n",
    "\n",
    "So let's say that you take this knowledge\n",
    "and prepare to train your first model $f_1$.\n",
    "Knowing just how confident you need to be\n",
    "in the performance of your classifier's error rate\n",
    "you apply our analysis above to determine\n",
    "an appropriate number of examples\n",
    "to set aside for the test set.\n",
    "Moreover, let's assume that you took the lessons from\n",
    "that section to heart\n",
    "and made sure to preserve the sanctity of the test set\n",
    "by conducting all of your preliminary analysis,\n",
    "hyperparameter tuning, and even selection\n",
    "among multiple competing model architectures\n",
    "on a validation set.\n",
    "Finally you evaluate your model $f_1$\n",
    "on the test set and report an unbiased\n",
    "estimate of the population error\n",
    "with an associated confidence interval.\n",
    "\n",
    "So far everything seems to be going well.\n",
    "However, that night you wake up at 3am\n",
    "with a brilliant idea for a new modeling approach.\n",
    "The next day, you code up your new model,\n",
    "tune its hyperparameters on the validation set\n",
    "and get your new model $f_2$ working;\n",
    "its error rate appears to be much lower than $f_1$'s.\n",
    "However, the thrill of discovery suddenly fades\n",
    "as you prepare for the final evaluation.\n",
    "You do not have a test set!\n",
    "\n",
    "Even though the original test set $\\mathcal{D}$\n",
    "is still sitting on your server,\n",
    "you now face two formidable problems.\n",
    "First, when you collected your test set,\n",
    "you determined the required level of precision\n",
    "under the assumption that you were evaluating\n",
    "a single classifier $f$.\n",
    "However, if you get into the business\n",
    "of evaluating multiple classifiers $f_1, ..., f_k$\n",
    "on the same test set,\n",
    "you must consider the problem of false discovery.\n",
    "Before, you might have been 95% sure\n",
    "that $\\epsilon_{\\mathcal{D}}(f) \\in \\epsilon(f) \\pm 0.01$\n",
    "for a single classifier $f$\n",
    "and thus the probability of a misleading result\n",
    "was a mere 5%.\n",
    "With $k$ classifiers in the mix,\n",
    "it can be hard to guarantee\n",
    "that there is not even one among them\n",
    "whose test set performance is misleading.\n",
    "With 20 classifiers under consideration,\n",
    "you might have no power at all\n",
    "to rule out the possibility\n",
    "that at least one among them\n",
    "received a misleading score.\n",
    "This problem relates to multiple hypothesis testing,\n",
    "which despite a vast literature in statistics,\n",
    "remains a persistent problem plaguing scientific research.\n",
    "\n",
    "\n",
    "If that is not enough to worry you,\n",
    "there is a special reason to distrust\n",
    "the results that you get on subsequent evaluations.\n",
    "Recall that our analysis of test set performance\n",
    "rested on the assumption that the classifier\n",
    "was chosen absent any contact with the test set\n",
    "and thus we could view the test set\n",
    "as drawn randomly from the underlying population.\n",
    "Here you are testing multiple functions, and\n",
    "the subsequent function $f_2$ was chosen\n",
    "after you observed the test set performance of $f_1$.\n",
    "Once information from the test set has leaked to the modeler,\n",
    "it can never be a true test set again in the strictest sense.\n",
    "This problem is called *adaptive overfitting* and has recently emerged\n",
    "as a topic of intense interest to learning theorists and statisticians\n",
    "[@dwork2015preserving].\n",
    "Fortunately, while it is possible\n",
    "to leak all information out of a holdout set,\n",
    "and the theoretical worst case scenarios are bleak,\n",
    "these analyses may be too conservative.\n",
    "In practice, take care to create real test sets,\n",
    "to consult them as infrequently as possible,\n",
    "to account for multiple hypothesis testing\n",
    "when reporting confidence intervals,\n",
    "and to dial up your vigilance more aggressively\n",
    "when the stakes are high and your dataset size is small.\n",
    "When running a series of benchmark challenges,\n",
    "it is often good practice to maintain\n",
    "several test sets so that after each round,\n",
    "the old test set can be demoted to a validation set.\n",
    "\n",
    "How bad can it get? A simulation makes the false-discovery half of the problem\n",
    "concrete in its purest form. Take one binary test set of $n = 1000$ examples\n",
    "and evaluate $k$ \"classifiers\" that ignore the inputs entirely and guess\n",
    "labels uniformly at random, so that every one of them has true accuracy\n",
    "exactly $0.5$. We track the best test accuracy seen so far as $k$ grows:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-classification-test-set-reuse-1"
   },
   "source": [
    "n, k = 1000, 10000\n",
    "labels = rng.integers(0, 2, n)                 # one fixed test set\n",
    "guesses = rng.integers(0, 2, (k, n))           # k random-guess classifiers\n",
    "best = np.maximum.accumulate((guesses == labels).mean(axis=1))\n",
    "d2l.plot(np.arange(1, k + 1), best, 'number of models evaluated',\n",
    "         'best test accuracy so far', xscale='log')"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"252.64375pt\" height=\"183.35625pt\" viewBox=\"0 0 252.64375 183.35625\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:40:41.089870</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 183.35625 \nL 252.64375 183.35625 \nL 252.64375 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 50.14375 145.8 \nL 245.44375 145.8 \nL 245.44375 7.2 \nL 50.14375 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 59.021023 145.8 \nL 59.021023 7.2 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"me662040bef\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#me662040bef\" x=\"59.021023\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(50.221023 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 103.407386 145.8 \nL 103.407386 7.2 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#me662040bef\" x=\"103.407386\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- $\\mathdefault{10^{1}}$ -->\n      <g transform=\"translate(94.607386 160.398438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 147.79375 145.8 \nL 147.79375 7.2 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#me662040bef\" x=\"147.79375\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- $\\mathdefault{10^{2}}$ -->\n      <g transform=\"translate(138.99375 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 192.180114 145.8 \nL 192.180114 7.2 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#me662040bef\" x=\"192.180114\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- $\\mathdefault{10^{3}}$ -->\n      <g transform=\"translate(183.380114 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_9\">\n      <path d=\"M 236.566477 145.8 \nL 236.566477 7.2 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#me662040bef\" x=\"236.566477\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- $\\mathdefault{10^{4}}$ -->\n      <g transform=\"translate(227.766477 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_11\">\n      <defs>\n       <path id=\"m38e5adc04c\" d=\"M 0 0 \nL 0 2 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"52.145488\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_7\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"54.71954\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"56.990014\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_9\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"72.38265\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_10\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"80.1987\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_11\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"85.744276\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_12\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"90.04576\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_13\">\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"93.560327\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_14\">\n     <g id=\"line2d_19\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"96.531852\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_15\">\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"99.105903\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_16\">\n     <g id=\"line2d_21\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"101.376378\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_17\">\n     <g id=\"line2d_22\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"116.769013\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_18\">\n     <g id=\"line2d_23\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"124.585064\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_19\">\n     <g id=\"line2d_24\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"130.13064\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_20\">\n     <g id=\"line2d_25\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"134.432123\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_21\">\n     <g id=\"line2d_26\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"137.946691\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_22\">\n     <g id=\"line2d_27\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"140.918215\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_23\">\n     <g id=\"line2d_28\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"143.492267\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_24\">\n     <g id=\"line2d_29\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"145.762741\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_25\">\n     <g id=\"line2d_30\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"161.155377\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_26\">\n     <g id=\"line2d_31\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"168.971428\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_27\">\n     <g id=\"line2d_32\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"174.517004\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_28\">\n     <g id=\"line2d_33\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"178.818487\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_29\">\n     <g id=\"line2d_34\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"182.333054\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_30\">\n     <g id=\"line2d_35\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"185.304579\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_31\">\n     <g id=\"line2d_36\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"187.878631\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_32\">\n     <g id=\"line2d_37\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"190.149105\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_33\">\n     <g id=\"line2d_38\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"205.54174\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_34\">\n     <g id=\"line2d_39\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"213.357791\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_35\">\n     <g id=\"line2d_40\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"218.903367\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_36\">\n     <g id=\"line2d_41\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"223.20485\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_37\">\n     <g id=\"line2d_42\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"226.719418\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_38\">\n     <g id=\"line2d_43\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"229.690943\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_39\">\n     <g id=\"line2d_44\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"232.264994\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_40\">\n     <g id=\"line2d_45\">\n      <g>\n       <use xlink:href=\"#m38e5adc04c\" x=\"234.535469\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_6\">\n     <!-- number of models evaluated -->\n     <g transform=\"translate(75.585938 174.076563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-62\" d=\"M 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\nM 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2969 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-66\" d=\"M 2375 4863 \nL 2375 4384 \nL 1825 4384 \nQ 1516 4384 1395 4259 \nQ 1275 4134 1275 3809 \nL 1275 3500 \nL 2222 3500 \nL 2222 3053 \nL 1275 3053 \nL 1275 0 \nL 697 0 \nL 697 3053 \nL 147 3053 \nL 147 3500 \nL 697 3500 \nL 697 3744 \nQ 697 4328 969 4595 \nQ 1241 4863 1831 4863 \nL 2375 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-76\" d=\"M 191 3500 \nL 800 3500 \nL 1894 563 \nL 2988 3500 \nL 3597 3500 \nL 2284 0 \nL 1503 0 \nL 191 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-6e\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(63.378906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(126.757812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(224.169922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(287.646484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(349.169922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(390.283203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(422.070312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(483.251953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(518.457031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(550.244141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(647.65625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(708.837891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(772.314453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(833.837891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(861.621094 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(913.720703 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(945.507812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-76\" transform=\"translate(1007.03125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(1066.210938 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(1127.490234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(1155.273438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(1218.652344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(1279.931641 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(1319.140625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(1380.664062 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_46\">\n      <path d=\"M 50.14375 128.543478 \nL 245.44375 128.543478 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_47\">\n      <defs>\n       <path id=\"m8d4e6d7cec\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m8d4e6d7cec\" x=\"50.14375\" y=\"128.543478\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 0.50 -->\n      <g transform=\"translate(20.878125 132.342697) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_48\">\n      <path d=\"M 50.14375 92.021739 \nL 245.44375 92.021739 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_49\">\n      <g>\n       <use xlink:href=\"#m8d4e6d7cec\" x=\"50.14375\" y=\"92.021739\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 0.52 -->\n      <g transform=\"translate(20.878125 95.820958) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_50\">\n      <path d=\"M 50.14375 55.5 \nL 245.44375 55.5 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_51\">\n      <g>\n       <use xlink:href=\"#m8d4e6d7cec\" x=\"50.14375\" y=\"55.5\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 0.54 -->\n      <g transform=\"translate(20.878125 59.299219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_52\">\n      <path d=\"M 50.14375 18.978261 \nL 245.44375 18.978261 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_53\">\n      <g>\n       <use xlink:href=\"#m8d4e6d7cec\" x=\"50.14375\" y=\"18.978261\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 0.56 -->\n      <g transform=\"translate(20.878125 22.77748) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n       <use xlink:href=\"#DejaVuSans-36\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_11\">\n     <!-- best test accuracy so far -->\n     <g transform=\"translate(14.798438 138.376563) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-79\" d=\"M 2059 -325 \nQ 1816 -950 1584 -1140 \nQ 1353 -1331 966 -1331 \nL 506 -1331 \nL 506 -850 \nL 844 -850 \nQ 1081 -850 1212 -737 \nQ 1344 -625 1503 -206 \nL 1606 56 \nL 191 3500 \nL 800 3500 \nL 1894 763 \nL 2988 3500 \nL 3597 3500 \nL 2059 -325 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-62\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(177.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(216.308594 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(248.095703 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(287.304688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(348.828125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(400.927734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(440.136719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(471.923828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(533.203125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(588.183594 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(643.164062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(706.542969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(747.65625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(808.935547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(863.916016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(923.095703 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(954.882812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(1006.982422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1068.164062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(1099.951172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(1135.15625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(1196.435547 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_54\">\n    <path d=\"M 59.021023 139.5 \nL 72.38265 137.673913 \nL 80.1987 102.978261 \nL 85.744276 102.978261 \nL 90.04576 97.5 \nL 93.560327 97.5 \nL 96.531852 90.195652 \nL 99.105903 90.195652 \nL 101.376378 81.065217 \nL 130.606633 81.065217 \nL 131.071156 75.586957 \nL 135.188171 75.586957 \nL 135.555358 71.934783 \nL 144.432783 71.934783 \nL 144.660913 53.673913 \nL 191.231885 53.673913 \nL 191.352996 37.23913 \nL 220.270558 37.23913 \nL 220.382464 31.76087 \nL 221.71867 31.76087 \nL 221.83078 20.804348 \nL 231.799179 20.804348 \nL 231.912398 13.5 \nL 236.566477 13.5 \nL 236.566477 13.5 \n\" clip-path=\"url(#p23526705b0)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 50.14375 145.8 \nL 50.14375 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 245.44375 145.8 \nL 245.44375 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 50.14375 145.8 \nL 245.44375 145.8 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 50.14375 7.2 \nL 245.44375 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p23526705b0\">\n   <rect x=\"50.14375\" y=\"7.2\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-classification-md-4 fw=all -->\n",
    "\n",
    "The best apparent accuracy climbs steadily, exceeding $0.56$ after ten\n",
    "thousand tries, even though *nothing was learned*: the models are coin flips,\n",
    "and the climb (which grows like $\\sqrt{\\log(k)/(2n)}$, by the same Hoeffding\n",
    "bound applied to $k$ events at once) is pure selection. Whenever you pick the\n",
    "best of many models by their score on one shared test set, some of the\n",
    "apparent improvement is exactly this effect; and an adaptive modeler, who\n",
    "steers each new model *toward* what scored well before, can climb faster\n",
    "still.\n",
    "\n",
    "\n",
    "## Statistical Learning Theory\n",
    "\n",
    "Put simply, *test sets are all that we really have*,\n",
    "and yet this fact seems strangely unsatisfying.\n",
    "First, we seldom possess a *true test set*: unless\n",
    "we are the ones creating the dataset,\n",
    "someone else has probably already evaluated\n",
    "their own classifier on our ostensible \"test set\".\n",
    "And even when we have first dibs,\n",
    "we soon find ourselves frustrated, wishing we could\n",
    "evaluate our subsequent modeling attempts\n",
    "without the gnawing feeling\n",
    "that we cannot trust our numbers.\n",
    "Moreover, even a true test set can only tell us *post hoc*\n",
    "whether a classifier has in fact generalized to the population,\n",
    "not whether we have any reason to expect *a priori*\n",
    "that it should generalize.\n",
    "\n",
    "With these misgivings in mind,\n",
    "you might now be sufficiently primed\n",
    "to see the appeal of *statistical learning theory*,\n",
    "the mathematical subfield of machine learning\n",
    "whose practitioners aim to elucidate the\n",
    "fundamental principles that explain\n",
    "why/when models trained on empirical data\n",
    "can/will generalize to unseen data.\n",
    "One of the primary aims\n",
    "of statistical learning researchers\n",
    "has been to bound the generalization gap,\n",
    "relating the properties of the model class\n",
    "to the number of samples in the dataset.\n",
    "\n",
    "Learning theorists aim to bound the difference\n",
    "between the *empirical error* $\\epsilon_{\\mathcal{S}}(f_{\\mathcal{S}})$\n",
    "of a learned classifier $f_{\\mathcal{S}}$,\n",
    "both trained and evaluated\n",
    "on the training set $\\mathcal{S}$,\n",
    "and the true error $\\epsilon(f_{\\mathcal{S}})$\n",
    "of that same classifier on the underlying population.\n",
    "This might look similar to the evaluation problem\n",
    "that we just addressed but there is a major difference.\n",
    "Earlier, the classifier $f$ was fixed\n",
    "and we only needed a dataset\n",
    "for evaluative purposes.\n",
    "And indeed, any fixed classifier does generalize:\n",
    "its error on a (previously unseen) dataset\n",
    "is an unbiased estimate of the population error.\n",
    "But what can we say when a classifier\n",
    "is trained and evaluated on the same dataset?\n",
    "Can we ever be confident that the training error\n",
    "will be close to the testing error?\n",
    "\n",
    "\n",
    "Suppose that our learned classifier $f_{\\mathcal{S}}$ must be chosen\n",
    "from some pre-specified set of functions $\\mathcal{F}$.\n",
    "Recall from our discussion of test sets\n",
    "that while it is easy to estimate\n",
    "the error of a single classifier,\n",
    "things get hairy when we begin\n",
    "to consider collections of classifiers.\n",
    "Even if the empirical error\n",
    "of any one (fixed) classifier\n",
    "will be close to its true error\n",
    "with high probability,\n",
    "once we consider a collection of classifiers,\n",
    "we need to worry about the possibility\n",
    "that *just one* of them\n",
    "will receive a badly estimated error.\n",
    "The worry is that we might pick such a classifier\n",
    "and thereby grossly underestimate\n",
    "the population error.\n",
    "Moreover, even for linear models,\n",
    "because their parameters are continuously valued,\n",
    "we are typically choosing from\n",
    "an infinite class of functions ($|\\mathcal{F}| = \\infty$).\n",
    "\n",
    "One ambitious solution to the problem\n",
    "is to develop analytic tools\n",
    "for proving uniform convergence, i.e.,\n",
    "that with high probability,\n",
    "the empirical error rate for every classifier in the class $f\\in\\mathcal{F}$\n",
    "will *simultaneously* converge to its true error rate.\n",
    "In other words, we seek a theoretical principle\n",
    "that would allow us to state that\n",
    "with probability at least $1-\\delta$\n",
    "(for some small $\\delta$)\n",
    "no classifier's error rate $\\epsilon(f)$\n",
    "(among all classifiers in the class $\\mathcal{F}$)\n",
    "will be misestimated by more\n",
    "than some  small amount $\\alpha$.\n",
    "Clearly, we cannot make such statements\n",
    "for all model classes $\\mathcal{F}$.\n",
    "Recall the class of memorization machines\n",
    "that always achieve empirical error $0$\n",
    "but never outperform random guessing\n",
    "on the underlying population.\n",
    "\n",
    "In a sense the class of memorizers is too flexible.\n",
    "No such uniform convergence result could possibly hold.\n",
    "On the other hand, a fixed classifier is useless: it\n",
    "generalizes perfectly, but fits neither\n",
    "the training data nor the test data.\n",
    "The central question of learning\n",
    "has thus historically been framed as a trade-off\n",
    "between more flexible (higher variance) model classes\n",
    "that better fit the training data but risk overfitting,\n",
    "versus more rigid (higher bias) model classes\n",
    "that generalize well but risk underfitting.\n",
    "A central question in learning theory\n",
    "has been to develop the appropriate\n",
    "mathematical analysis to quantify\n",
    "where a model sits along this spectrum,\n",
    "and to provide the associated guarantees.\n",
    "\n",
    "In a series of papers,\n",
    "Vapnik and Chervonenkis extended\n",
    "the theory on the convergence\n",
    "of relative frequencies\n",
    "to more general classes of functions\n",
    "[@VapChe64; @VapChe68; @VapChe71; @VapChe74b; @VapChe81; @VapChe91].\n",
    "One of the key contributions of this line of work\n",
    "is the Vapnik--Chervonenkis (VC) dimension,\n",
    "which measures (one notion of)\n",
    "the complexity (flexibility) of a model class.\n",
    "Moreover, one of their key results bounds\n",
    "the difference between the empirical error\n",
    "and the population error as a function\n",
    "of the VC dimension and the number of samples:\n",
    "\n",
    "$$P\\left(\\epsilon(f_{\\mathcal{S}}) - \\epsilon_{\\mathcal{S}}(f_{\\mathcal{S}}) < \\alpha\\right) \\geq 1-\\delta\n",
    "\\ \\textrm{ for }\\ \\alpha \\geq c \\sqrt{(\\textrm{VC} - \\log \\delta)/n}.$$\n",
    "\n",
    "Here $\\delta > 0$ is the probability that the bound is violated,\n",
    "$\\alpha$ is the upper bound on the generalization gap,\n",
    "and $n$ is the dataset size.\n",
    "Lastly, $c > 0$ is a constant that depends\n",
    "only on the scale of the loss that can be incurred.\n",
    "One use of the bound might be to plug in desired\n",
    "values of $\\delta$ and $\\alpha$\n",
    "to determine how many samples to collect.\n",
    "A class *shatters* a set of points if, for every possible $\\pm$ labeling\n",
    "of them, some model $f$ in the class agrees with that labeling.\n",
    "The VC dimension is the largest number of points the class can shatter.\n",
    "For example, linear models on $d$-dimensional inputs\n",
    "have VC dimension $d+1$.\n",
    "As the figure illustrates,\n",
    "a line in the plane can realize *every* labeling\n",
    "of three points in general position,\n",
    "while no line can realize the XOR labeling of four points,\n",
    "which already shows that lines cannot shatter *these* four points;\n",
    "the general upper bound, and hence a VC dimension of exactly $3$\n",
    "for two-dimensional linear classifiers (matching $d+1$ with $d=2$),\n",
    "comes from Radon's theorem below.\n",
    "The general statement holds in both directions, and neither is deep.\n",
    "For the lower bound, the $d+1$ points\n",
    "$\\{\\mathbf{0}, \\mathbf{e}_1, \\ldots, \\mathbf{e}_d\\}$\n",
    "can be shattered by weights that are simply *read off* the desired labels;\n",
    "exercise 5 walks you through it.\n",
    "For the upper bound, *no* set of $d+2$ points can be shattered:\n",
    "by Radon's theorem [@Radon.1921], any $d+2$ points in $\\mathbb{R}^d$\n",
    "can be partitioned into two subsets whose convex hulls intersect,\n",
    "and no halfspace can put two intersecting hulls on opposite sides.\n",
    "\n",
    "![A linear classifier in two dimensions shatters any 3 points in general position (all $2^3$ labelings are realizable by a halfplane) but cannot shatter 4 points (the XOR labeling, with one class on each diagonal, has no linear separator). Hence the VC dimension of lines in the plane is 3.](../img/mdl-clf-shattering.svg)\n",
    "\n",
    "Unfortunately, the theory tends to be\n",
    "overly pessimistic for more complex models\n",
    "and obtaining this guarantee typically requires\n",
    "far more examples than are actually needed\n",
    "to achieve the desired error rate.\n",
    "Note also that fixing the model class and $\\delta$,\n",
    "our error rate again decays\n",
    "with the usual $\\mathcal{O}(1/\\sqrt{n})$ rate.\n",
    "It seems unlikely that we could do better in terms of $n$.\n",
    "However, as we vary the model class,\n",
    "VC dimension can present\n",
    "a pessimistic picture\n",
    "of the generalization gap.\n",
    "\n",
    "\n",
    "## Summary\n",
    "\n",
    "The most straightforward way to evaluate a model\n",
    "is to consult a test set comprised of previously unseen data.\n",
    "Test set evaluations provide an unbiased estimate of the true error\n",
    "and converge at the desired $\\mathcal{O}(1/\\sqrt{n})$ rate as the test set grows.\n",
    "We can provide approximate confidence intervals\n",
    "based on exact asymptotic distributions\n",
    "or valid finite sample confidence intervals\n",
    "based on (more conservative) finite sample guarantees.\n",
    "Test set evaluation is central\n",
    "to modern machine learning research.\n",
    "However, test sets are seldom true test sets\n",
    "(used by multiple researchers again and again).\n",
    "Once the same test set is used\n",
    "to evaluate multiple models,\n",
    "controlling for false discovery can be difficult.\n",
    "This can cause huge problems in theory.\n",
    "In practice, the significance of the problem\n",
    "depends on the size of the holdout sets in question\n",
    "and whether they are merely being used to choose hyperparameters\n",
    "or if they are leaking information more directly.\n",
    "Nevertheless, it is good practice to curate real test sets (or multiple)\n",
    "and to be as conservative as possible about how often they are used.\n",
    "\n",
    "\n",
    "Hoping to provide a more satisfying solution,\n",
    "statistical learning theorists have developed methods\n",
    "for guaranteeing uniform convergence over a model class.\n",
    "If indeed every model's empirical error simultaneously\n",
    "converges to its true error,\n",
    "then we are free to choose the model that performs\n",
    "best, minimizing the training error,\n",
    "knowing that it too will perform similarly well\n",
    "on the holdout data.\n",
    "Crucially, any one of such results must depend\n",
    "on some property of the model class.\n",
    "Vladimir Vapnik and Alexey Chervonenkis\n",
    "introduced the VC dimension,\n",
    "presenting uniform convergence results\n",
    "that hold for all models in a VC class.\n",
    "The training errors for all models in the class\n",
    "are (simultaneously) guaranteed\n",
    "to be close to their true errors,\n",
    "and guaranteed to grow even closer\n",
    "at $\\mathcal{O}(1/\\sqrt{n})$ rates.\n",
    "Following the discovery of VC dimension,\n",
    "numerous alternative complexity measures have been proposed,\n",
    "each facilitating an analogous generalization guarantee.\n",
    "One such measure, *Rademacher complexity*, is developed in full\n",
    "in that section,\n",
    "which also reproduces from scratch (as *double descent*)\n",
    "the surprisingly benign behavior of overparametrized models\n",
    "that we are about to describe.\n",
    "See @boucheron2005theory for a detailed discussion\n",
    "of several advanced ways of measuring function complexity.\n",
    "Unfortunately, while these complexity measures\n",
    "have become broadly useful tools in statistical theory,\n",
    "they turn out to be powerless\n",
    "(as straightforwardly applied)\n",
    "for explaining why deep neural networks generalize [@zhang2021understanding].\n",
    "Deep neural networks often have millions of parameters (or more),\n",
    "and can easily assign random labels to large collections of points.\n",
    "Nevertheless, they generalize well on practical problems\n",
    "and, surprisingly, they often generalize better,\n",
    "when they are larger and deeper,\n",
    "despite incurring higher VC dimensions.\n",
    "We revisit generalization in the context of deep learning\n",
    "in that section.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. If we wish to estimate the error of a fixed model $f$\n",
    "   to within $0.0001$ with probability greater than 99.9%,\n",
    "   how many samples do we need?\n",
    "1. Suppose that somebody else possesses a labeled test set\n",
    "   $\\mathcal{D}$ and only makes available the unlabeled inputs (features).\n",
    "   Now suppose that you can only access the test set labels\n",
    "   by running a model $f$ (with no restrictions placed on the model class)\n",
    "   on each of the unlabeled inputs\n",
    "   and receiving the corresponding error $\\epsilon_{\\mathcal{D}}(f)$.\n",
    "   How many models would you need to evaluate\n",
    "   before you leak the entire test set\n",
    "   and thus could appear to have error $0$,\n",
    "   regardless of your true error?\n",
    "1. What is the VC dimension of the class of fifth-order polynomials?\n",
    "1. What is the VC dimension of axis-aligned rectangles on two-dimensional data?\n",
    "1. Prove the lower bound VC $\\geq d+1$ for linear classifiers\n",
    "   $f(\\mathbf{x}) = \\operatorname{sign}(\\mathbf{w}^\\top \\mathbf{x} + b)$ on $\\mathbb{R}^d$\n",
    "   by shattering the $d+1$ points $\\{\\mathbf{0}, \\mathbf{e}_1, \\ldots, \\mathbf{e}_d\\}$\n",
    "   (the origin and the standard unit vectors). Given any desired labels\n",
    "   $\\sigma_0, \\sigma_1, \\ldots, \\sigma_d \\in \\{\\pm 1\\}$, set $b = \\sigma_0 / 2$\n",
    "   and read the weights off the labels as $w_i = \\sigma_i - b$. Verify that\n",
    "   $f(\\mathbf{0}) = \\sigma_0$ and $f(\\mathbf{e}_i) = \\sigma_i$ for every $i$.\n",
    "   Combined with the Radon argument in the text for the upper bound, this\n",
    "   proves VC $= d+1$ exactly.\n",
    "1. In the figure the three shattered points are in\n",
    "   *general position* (not collinear). Show that three collinear points can\n",
    "   *not* be shattered by halfplanes: which labeling is unrealizable? Explain\n",
    "   why this does not contradict the VC dimension of lines in the plane being\n",
    "   $3$. (Hint: the VC dimension asks whether *some* set of a given size can be\n",
    "   shattered, not whether *every* set can.)\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/6829)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
