{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-md-1 fw=all -->\n",
    "\n",
    "# Generalization\n",
    "\n",
    "Consider two college students diligently\n",
    "preparing for their final exam.\n",
    "Commonly, this preparation will consist\n",
    "of practicing and testing their abilities\n",
    "by taking exams administered in previous years.\n",
    "Nonetheless, doing well on past exams is no guarantee\n",
    "that they will excel when it matters.\n",
    "For instance, imagine a student, Extraordinary Ellie,\n",
    "whose preparation consisted entirely\n",
    "of memorizing the answers\n",
    "to previous years' exam questions.\n",
    "Even if Ellie were endowed\n",
    "with an extraordinary memory,\n",
    "and thus could perfectly recall the answer\n",
    "to any *previously seen* question,\n",
    "she might nevertheless freeze\n",
    "when faced with a new (*previously unseen*) question.\n",
    "By comparison, imagine another student,\n",
    "Inductive Irene, with comparably poor\n",
    "memorization skills,\n",
    "but a knack for picking up patterns.\n",
    "Note that if the exam truly consisted of\n",
    "recycled questions from a previous year,\n",
    "Ellie would handily outperform Irene.\n",
    "Even if Irene's inferred patterns\n",
    "yielded 90% accurate predictions,\n",
    "they could never compete with\n",
    "Ellie's 100% recall.\n",
    "However, even if the exam consisted\n",
    "entirely of fresh questions,\n",
    "Irene might maintain her 90% average.\n",
    "\n",
    "As machine learning scientists,\n",
    "our goal is to discover *patterns*.\n",
    "But how can we be sure that we have\n",
    "truly discovered a *general* pattern\n",
    "and not simply memorized our data?\n",
    "Most of the time, our predictions are only useful\n",
    "if our model discovers such a pattern.\n",
    "We do not want to predict yesterday's stock prices, but tomorrow's.\n",
    "We do not need to recognize\n",
    "already diagnosed diseases\n",
    "for previously seen patients,\n",
    "but rather previously undiagnosed\n",
    "ailments in previously unseen patients.\n",
    "This problem (how to discover patterns that *generalize*) is\n",
    "the fundamental problem of machine learning,\n",
    "and arguably of all of statistics.\n",
    "We might cast this problem as just one slice\n",
    "of a far grander question\n",
    "that engulfs all of science:\n",
    "when are we ever justified\n",
    "in making the leap from particular observations\n",
    "to more general statements?\n",
    "\n",
    "\n",
    "In real life, we must fit our models\n",
    "using a finite collection of data.\n",
    "The typical scales of that data\n",
    "vary wildly across domains.\n",
    "For many important medical problems,\n",
    "we can only access a few thousand data points.\n",
    "When studying rare diseases,\n",
    "we might be lucky to access hundreds.\n",
    "By contrast, the largest public datasets\n",
    "consisting of labeled photographs,\n",
    "e.g., ImageNet [@Deng.Dong.Socher.ea.2009],\n",
    "contain millions of images.\n",
    "And some unlabeled image collections\n",
    "such as the Flickr YFC100M dataset\n",
    "can be even larger, containing\n",
    "over 100 million images [@thomee2016yfcc100m].\n",
    "However, even at this extreme scale,\n",
    "the number of available data points\n",
    "remains infinitesimally small\n",
    "compared to the space of all possible images\n",
    "at a megapixel resolution.\n",
    "Whenever we work with finite samples,\n",
    "we must keep in mind the risk\n",
    "that we might fit our training data,\n",
    "only to discover that we failed\n",
    "to discover a generalizable pattern.\n",
    "\n",
    "The phenomenon of fitting closer to our training data\n",
    "than to the underlying distribution is called *overfitting*,\n",
    "and techniques for combatting overfitting\n",
    "are often called *regularization* methods.\n",
    "While it is no substitute for a proper introduction\n",
    "to statistical learning theory (that section\n",
    "gives a first, rigorous taste; see also @Vapnik98; @boucheron2005theory),\n",
    "we will give you just enough intuition to get going.\n",
    "We will revisit generalization in many chapters\n",
    "throughout the book,\n",
    "exploring both what is known about\n",
    "the principles underlying generalization\n",
    "in various models,\n",
    "and also heuristic techniques\n",
    "that have been found (empirically)\n",
    "to yield improved generalization\n",
    "on tasks of practical interest.\n",
    "\n",
    "\n",
    "## Training Error and Generalization Error\n",
    "\n",
    "\n",
    "In the standard supervised learning setting,\n",
    "we assume that the training data and the test data\n",
    "are drawn *independently* from *identical* distributions.\n",
    "This is commonly called the *IID assumption*.\n",
    "While this assumption is strong,\n",
    "absent any such assumption we would be dead in the water.\n",
    "Why should we believe that training data\n",
    "sampled from distribution $P(X,Y)$\n",
    "should tell us how to make predictions on\n",
    "test data generated by a *different distribution* $Q(X,Y)$?\n",
    "Making such leaps turns out to require\n",
    "strong assumptions about how $P$ and $Q$ are related.\n",
    "Later on we will discuss some assumptions\n",
    "that allow for shifts in distribution\n",
    "but first we need to understand the IID case,\n",
    "where $P(\\cdot) = Q(\\cdot)$.\n",
    "\n",
    "To begin with, we need to differentiate between\n",
    "the *training error* $R_\\textrm{emp}$,\n",
    "which is a *statistic*\n",
    "calculated on the training dataset,\n",
    "and the *generalization error* $R$,\n",
    "which is an *expectation* taken\n",
    "with respect to the underlying distribution.\n",
    "You can think of the generalization error as\n",
    "what you would see  if you applied your model\n",
    "to an infinite stream of additional data examples\n",
    "drawn from the same underlying data distribution.\n",
    "Formally the training error is expressed as an *average* over the finite training sample (with the same notation as that section):\n",
    "\n",
    "$$R_\\textrm{emp}[\\mathbf{X}, \\mathbf{y}, f] = \\frac{1}{n} \\sum_{i=1}^n l(\\mathbf{x}^{(i)}, y^{(i)}, f(\\mathbf{x}^{(i)})),$$\n",
    "\n",
    "\n",
    "while the generalization error (also called the *risk*) is expressed as an integral:\n",
    "\n",
    "$$R[P, f] = E_{(\\mathbf{x}, y) \\sim P} [l(\\mathbf{x}, y, f(\\mathbf{x}))] = \\int \\int l(\\mathbf{x}, y, f(\\mathbf{x})) p(\\mathbf{x}, y) \\;d\\mathbf{x} dy.$$\n",
    "\n",
    "Problematically, we can never calculate\n",
    "the generalization error $R$ exactly.\n",
    "Nobody ever tells us the precise form\n",
    "of the density function $p(\\mathbf{x}, y)$.\n",
    "Moreover, we cannot sample an infinite stream of data points.\n",
    "Thus, in practice, we must *estimate* the generalization error\n",
    "by applying our model to an independent test set\n",
    "constituted of a random selection of examples\n",
    "$\\mathbf{X}'$ and labels $\\mathbf{y}'$\n",
    "that were withheld from our training set.\n",
    "This consists of applying the same formula\n",
    "that was used for calculating the empirical training error\n",
    "but to a test set $\\mathbf{X}', \\mathbf{y}'$.\n",
    "\n",
    "\n",
    "Crucially, when we evaluate our model on the test set,\n",
    "we are working with a *fixed* model\n",
    "(it does not depend on the sample of the test set),\n",
    "and thus estimating its error\n",
    "is simply the problem of mean estimation.\n",
    "However the same cannot be said\n",
    "for the training set.\n",
    "Note that the model we wind up with\n",
    "depends explicitly on the selection of the training set\n",
    "and thus the training error will in general\n",
    "be a biased estimate of the true error\n",
    "on the underlying population.\n",
    "The central question of generalization\n",
    "is then when should we expect our training error\n",
    "to be close to the population error\n",
    "(and thus the generalization error).\n",
    "\n",
    "### Model Complexity\n",
    "\n",
    "In classical theory, when we have\n",
    "simple models and abundant data,\n",
    "the training and generalization errors tend to be close.\n",
    "However, when we work with\n",
    "more complex models and/or fewer examples,\n",
    "we expect the training error to go down\n",
    "but the *generalization gap* (the difference $R - R_\\textrm{emp}$\n",
    "between the generalization error and the training error) to grow.\n",
    "This should not be surprising.\n",
    "Imagine a model class so expressive that\n",
    "for any dataset of $n$ examples,\n",
    "we can find a set of parameters\n",
    "that can perfectly fit arbitrary labels,\n",
    "even if randomly assigned.\n",
    "In this case, even if we fit our training data perfectly,\n",
    "how can we conclude anything about the generalization error?\n",
    "For all we know, our generalization error\n",
    "might be no better than random guessing.\n",
    "\n",
    "In general, absent any restriction on our model class,\n",
    "we cannot conclude, based on fitting the training data alone,\n",
    "that our model has discovered any generalizable pattern [@vapnik1994measuring].\n",
    "On the other hand, if our model class\n",
    "was not capable of fitting arbitrary labels,\n",
    "then low training error is evidence that it has captured a real pattern,\n",
    "provided the sample is large relative to the class's capacity\n",
    "(that section).\n",
    "Learning-theoretic ideas about model complexity\n",
    "derived some inspiration from the ideas\n",
    "of Karl Popper, an influential philosopher of science,\n",
    "who formalized the criterion of falsifiability [@popper2005logic].\n",
    "According to Popper, a theory\n",
    "that can explain any and all observations\n",
    "is not a scientific theory at all!\n",
    "After all, what has it told us about the world\n",
    "if it has not ruled out any possibility?\n",
    "In short, what we want is a hypothesis\n",
    "that *could not* explain any observations\n",
    "we might conceivably make\n",
    "and yet nevertheless happens to be compatible\n",
    "with those observations that we *in fact* make.\n",
    "\n",
    "Now what precisely constitutes an appropriate\n",
    "notion of model complexity is a complex matter.\n",
    "For squared-error regression, with expectation taken over repeated training\n",
    "sets drawn by the same process, the classical *bias-variance decomposition*\n",
    "makes the trade-off precise: a model too simple to capture the signal makes a systematic error\n",
    "(high *bias*, i.e., underfitting), while a model flexible enough to chase the\n",
    "noise in a particular training set varies wildly from one dataset to the next\n",
    "(high *variance*, i.e., overfitting). Their sum, plus an irreducible noise floor\n",
    "$\\sigma^2$, is the expected test error, which traces the U-shaped curve of\n",
    "the figure; we derive the decomposition formally in\n",
    "that section.\n",
    "Often, models with more parameters\n",
    "are able to fit a greater number\n",
    "of arbitrarily assigned labels.\n",
    "However, this is not necessarily true.\n",
    "For instance, kernel methods operate in spaces\n",
    "with infinite numbers of parameters,\n",
    "yet their complexity is controlled\n",
    "by other means [@Scholkopf.Smola.2002].\n",
    "One notion of complexity that often proves useful\n",
    "is the range of values that the parameters can take.\n",
    "Here, a model whose parameters are permitted\n",
    "to take arbitrary values\n",
    "would be more complex.\n",
    "We will revisit this idea in the next section,\n",
    "when we introduce *weight decay*,\n",
    "your first practical regularization technique.\n",
    "It can be difficult to compare\n",
    "complexity among members of substantially different model classes\n",
    "(say, decision trees vs. neural networks).\n",
    "\n",
    "\n",
    "At this point, we must stress another important point\n",
    "that we will revisit when introducing deep neural networks.\n",
    "When a model is capable of fitting arbitrary labels,\n",
    "low training error does not necessarily\n",
    "imply low generalization error.\n",
    "*However, it does not necessarily\n",
    "imply high generalization error either!*\n",
    "All we can say with confidence is that\n",
    "low training error alone is not enough\n",
    "to certify low generalization error.\n",
    "Deep neural networks turn out to be just such models:\n",
    "while they generalize well in practice,\n",
    "they are too powerful to allow us to conclude\n",
    "much on the basis of training error alone.\n",
    "In these cases we must rely more heavily\n",
    "on our holdout data to certify generalization\n",
    "after the fact.\n",
    "Error on the holdout data, i.e., validation set,\n",
    "is called the *validation error*.\n",
    "\n",
    "This classical picture, in which more *capacity* (the richness of the model\n",
    "class) means more overfitting, is, however,\n",
    "*incomplete* for the heavily overparametrized models at the heart of modern deep\n",
    "learning. Once a model is large enough to *interpolate* its training data (drive\n",
    "training error to zero), pushing capacity even higher often makes test error\n",
    "*fall again* rather than rise: the *double descent* phenomenon\n",
    "[@Belkin.Hsu.Ma.ea.2019; @nakkiran2021deep]. We take up this modern story, and\n",
    "why the classical complexity intuition breaks down, in\n",
    "that section; for a quantitative treatment that\n",
    "reproduces the double-descent curve from scratch, see\n",
    "that section.\n",
    "\n",
    "## Underfitting or Overfitting?\n",
    "\n",
    "When we compare the training and validation errors,\n",
    "we want to be mindful of two common situations.\n",
    "First, we want to watch out for cases\n",
    "when our training error and validation error are both substantial\n",
    "but there is only a small gap between them.\n",
    "If the model is unable to reduce the training error,\n",
    "that could mean that our model is too simple\n",
    "(i.e., insufficiently expressive)\n",
    "to capture the pattern that we are trying to model.\n",
    "Moreover, since the generalization gap\n",
    "between our training and generalization errors is small,\n",
    "we have reason to believe that we could get away with a more complex model.\n",
    "This phenomenon is known as *underfitting*.\n",
    "\n",
    "On the other hand, as we discussed above,\n",
    "we want to watch out for the cases\n",
    "when our training error is significantly lower\n",
    "than our validation error, indicating severe *overfitting*.\n",
    "Note that overfitting is not always a bad thing.\n",
    "In deep learning especially,\n",
    "the best predictive models often perform\n",
    "far better on training data than on holdout data.\n",
    "Ultimately, we usually care about\n",
    "driving the generalization error lower,\n",
    "and only care about the gap insofar\n",
    "as it becomes an obstacle to that end.\n",
    "Note that if the training error is zero,\n",
    "then the generalization gap is precisely equal to the generalization error\n",
    "and we can make progress only by reducing the gap.\n",
    "\n",
    "### Polynomial Curve Fitting\n",
    "\n",
    "To illustrate some classical intuition\n",
    "about overfitting and model complexity,\n",
    "consider the following:\n",
    "given training data consisting of a single feature $x$\n",
    "and a corresponding real-valued label $y$,\n",
    "we try to find the polynomial of degree $d$\n",
    "\n",
    "$$\\hat{y}= \\sum_{i=0}^d x^i w_i$$\n",
    "\n",
    "for estimating the label $y$.\n",
    "This is just a linear regression problem\n",
    "where our features are given by the powers of $x$,\n",
    "the model's weights are given by $w_i$,\n",
    "and the bias is given by $w_0$ since $x^0 = 1$ for all $x$.\n",
    "Since this is just a linear regression problem,\n",
    "we can use the squared error as our loss function.\n",
    "\n",
    "\n",
    "A higher-order polynomial function is more complex\n",
    "than a lower-order polynomial function,\n",
    "since the higher-order polynomial has more parameters\n",
    "and the model function's selection range is wider.\n",
    "Fixing the training dataset,\n",
    "higher-order polynomial functions should always\n",
    "achieve lower (at worst, equal) training error\n",
    "relative to lower-degree polynomials.\n",
    "In fact, whenever each data example\n",
    "has a distinct value of $x$,\n",
    "a polynomial function with degree\n",
    "equal to the number of data examples\n",
    "can fit the training set perfectly.\n",
    "We compare the relationship between polynomial degree (model complexity)\n",
    "and both underfitting and overfitting in the figure.\n",
    "\n",
    "![Influence of model complexity on underfitting and overfitting: as complexity grows, squared bias falls while variance rises, and their sum (plus an irreducible noise floor) is the expected test error, which traces a U.](../img/mdl-prob-bias-variance-u-curve.svg)\n",
    "\n",
    "To see this concretely, let us generate data from a known cubic and fit\n",
    "polynomials of growing degree to a small training set."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-polynomial-curve-fitting-1"
   },
   "source": [
    "%matplotlib inline\n",
    "import math\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-md-2 fw=all -->\n",
    "\n",
    "We draw inputs $x$ uniformly from $[-1, 1]$, build a design matrix whose $i$-th\n",
    "column is $x^i$, and generate labels from a degree-3 target\n",
    "$y = 5 + 1.2 x - 3.4 x^2 + 5.6 x^3$ plus a little Gaussian noise. We deliberately\n",
    "keep the training set small so that high-degree models have room to overfit."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-polynomial-curve-fitting-2"
   },
   "source": [
    "np.random.seed(0)\n",
    "max_degree = 20                  # highest polynomial degree we will fit\n",
    "n_train, n_test = 20, 100        # few training points, so high degrees overfit\n",
    "true_w = np.zeros(max_degree)\n",
    "true_w[:4] = np.array([5, 1.2, -3.4, 5.6])\n",
    "\n",
    "x = np.random.uniform(-1, 1, size=n_train + n_test)\n",
    "poly = np.power(x.reshape(-1, 1), np.arange(max_degree))   # column i holds x**i\n",
    "labels = poly @ true_w + np.random.normal(scale=0.1, size=n_train + n_test)"
   ],
   "execution_count": 2,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-md-3 fw=all -->\n",
    "\n",
    "Fitting the first $d+1$ columns by least squares gives the best degree-$d$\n",
    "polynomial; we record its loss on both the training and the held-out test split."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-polynomial-curve-fitting-3"
   },
   "source": [
    "def fit_degree(d):\n",
    "    cols = slice(0, d + 1)\n",
    "    w, *_ = np.linalg.lstsq(poly[:n_train, cols], labels[:n_train], rcond=None)\n",
    "    err = poly[:, cols] @ w - labels\n",
    "    return (err[:n_train] ** 2).mean(), (err[n_train:] ** 2).mean()"
   ],
   "execution_count": 3,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-md-4 fw=all -->\n",
    "\n",
    "A degree-1 polynomial is too rigid to capture a cubic, so it errs on both splits\n",
    "(*underfitting*); degree 3 matches the true model, with low error on both; and a\n",
    "degree-19 polynomial has enough freedom to interpolate the 20 training points\n",
    "almost exactly, driving training error toward zero while test error explodes\n",
    "(*overfitting*)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-polynomial-curve-fitting-4"
   },
   "source": [
    "for name, d in [('underfitting (degree 1) ', 1),\n",
    "                ('just right   (degree 3) ', 3),\n",
    "                ('overfitting   (degree 19)', 19)]:\n",
    "    train_mse, test_mse = fit_degree(d)\n",
    "    print(f'{name}: train {train_mse:8.4f}   test {test_mse:12.4f}')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "underfitting (degree 1) : train   1.6698   test       1.7318\njust right   (degree 3) : train   0.0136   test       0.0129\noverfitting   (degree 19): train   0.0000   test 49271508224071.6328\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-md-5 fw=all -->\n",
    "\n",
    "Sweeping the degree from 1 to 19 traces out exactly the U-shaped test-error curve\n",
    "that the figure sketches: error first falls as the model\n",
    "gains the capacity to represent the signal, then rises as the surplus capacity is\n",
    "spent fitting noise. Training error, by contrast, only ever decreases."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-polynomial-curve-fitting-5"
   },
   "source": [
    "degrees = list(range(1, max_degree))\n",
    "mse = np.array([fit_degree(d) for d in degrees])\n",
    "d2l.plot(degrees, [mse[:, 0], mse[:, 1]], xlabel='polynomial degree',\n",
    "         ylabel='loss', legend=['train', 'test'], yscale='log')"
   ],
   "execution_count": 5,
   "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=\"258.278125pt\" height=\"187.00426pt\" viewBox=\"0 0 258.278125 187.00426\" 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:53.023340</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 187.00426 \nL 258.278125 187.00426 \nL 258.278125 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 55.778125 149.44801 \nL 251.078125 149.44801 \nL 251.078125 10.84801 \nL 55.778125 10.84801 \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 104.109943 149.44801 \nL 104.109943 10.84801 \n\" clip-path=\"url(#pf75825457d)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"m99a8df9262\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m99a8df9262\" x=\"104.109943\" y=\"149.44801\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 5 -->\n      <g transform=\"translate(100.928693 164.046447) scale(0.1 -0.1)\">\n       <defs>\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-35\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 153.428125 149.44801 \nL 153.428125 10.84801 \n\" clip-path=\"url(#pf75825457d)\" 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=\"#m99a8df9262\" x=\"153.428125\" y=\"149.44801\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 10 -->\n      <g transform=\"translate(147.065625 164.046447) 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\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 202.746307 149.44801 \nL 202.746307 10.84801 \n\" clip-path=\"url(#pf75825457d)\" 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=\"#m99a8df9262\" x=\"202.746307\" y=\"149.44801\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 15 -->\n      <g transform=\"translate(196.383807 164.046447) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_4\">\n     <!-- polynomial degree -->\n     <g transform=\"translate(106.795313 177.724572) 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-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-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-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       <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-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-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-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-20\" 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-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-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-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      </defs>\n      <use xlink:href=\"#DejaVuSans-70\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(124.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(152.441406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(211.621094 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(275 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(336.181641 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(433.59375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(461.376953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(522.65625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(550.439453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(582.226562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(645.703125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(707.226562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(770.703125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(809.566406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(871.089844 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_7\">\n      <path d=\"M 55.778125 128.575539 \nL 251.078125 128.575539 \n\" clip-path=\"url(#pf75825457d)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_8\">\n      <defs>\n       <path id=\"m75ef79b9d0\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m75ef79b9d0\" x=\"55.778125\" y=\"128.575539\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- $\\mathdefault{10^{-10}}$ -->\n      <g transform=\"translate(20.878125 132.374758) 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-31\" transform=\"translate(186.855469 39.046875) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(231.391602 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_9\">\n      <path d=\"M 55.778125 105.060275 \nL 251.078125 105.060275 \n\" clip-path=\"url(#pf75825457d)\" 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=\"#m75ef79b9d0\" x=\"55.778125\" y=\"105.060275\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- $\\mathdefault{10^{-5}}$ -->\n      <g transform=\"translate(25.278125 108.859494) 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-35\" transform=\"translate(186.855469 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_11\">\n      <path d=\"M 55.778125 81.545011 \nL 251.078125 81.545011 \n\" clip-path=\"url(#pf75825457d)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m75ef79b9d0\" x=\"55.778125\" y=\"81.545011\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(31.178125 85.34423) scale(0.1 -0.1)\">\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=\"ytick_4\">\n     <g id=\"line2d_13\">\n      <path d=\"M 55.778125 58.029747 \nL 251.078125 58.029747 \n\" clip-path=\"url(#pf75825457d)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m75ef79b9d0\" x=\"55.778125\" y=\"58.029747\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- $\\mathdefault{10^{5}}$ -->\n      <g transform=\"translate(31.178125 61.828966) 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-35\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_15\">\n      <path d=\"M 55.778125 34.514483 \nL 251.078125 34.514483 \n\" clip-path=\"url(#pf75825457d)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m75ef79b9d0\" x=\"55.778125\" y=\"34.514483\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- $\\mathdefault{10^{10}}$ -->\n      <g transform=\"translate(26.678125 38.313702) scale(0.1 -0.1)\">\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-31\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(172.739258 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_17\">\n      <path d=\"M 55.778125 10.999219 \nL 251.078125 10.999219 \n\" clip-path=\"url(#pf75825457d)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m75ef79b9d0\" x=\"55.778125\" y=\"10.999219\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- $\\mathdefault{10^{15}}$ -->\n      <g transform=\"translate(26.678125 14.798438) 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       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(172.739258 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_11\">\n     <!-- loss -->\n     <g transform=\"translate(14.798438 89.805822) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\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      </defs>\n      <use xlink:href=\"#DejaVuSans-6c\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(27.783203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(88.964844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(141.064453 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_19\">\n    <path d=\"M 64.655398 80.497759 \nL 74.519034 83.112088 \nL 84.38267 90.329937 \nL 94.246307 90.900782 \nL 104.109943 90.923326 \nL 113.97358 90.999697 \nL 123.837216 91.132572 \nL 133.700852 91.214059 \nL 143.564489 91.315322 \nL 153.428125 91.475814 \nL 163.291761 91.478411 \nL 173.155398 91.554824 \nL 183.019034 94.625583 \nL 192.88267 94.628952 \nL 202.746307 96.149063 \nL 212.609943 97.480117 \nL 222.47358 97.537264 \nL 232.337216 99.600397 \nL 242.200852 143.14801 \n\" clip-path=\"url(#pf75825457d)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_20\">\n    <path d=\"M 64.655398 80.423376 \nL 74.519034 81.78993 \nL 84.38267 90.435706 \nL 94.246307 88.672541 \nL 104.109943 88.72804 \nL 113.97358 89.251408 \nL 123.837216 86.777807 \nL 133.700852 88.78456 \nL 143.564489 88.428479 \nL 153.428125 85.03461 \nL 163.291761 84.246747 \nL 173.155398 78.473143 \nL 183.019034 65.901953 \nL 192.88267 65.607581 \nL 202.746307 60.370498 \nL 212.609943 54.294405 \nL 222.47358 49.6497 \nL 232.337216 35.945357 \nL 242.200852 17.14801 \n\" clip-path=\"url(#pf75825457d)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 55.778125 149.44801 \nL 55.778125 10.84801 \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 251.078125 149.44801 \nL 251.078125 10.84801 \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 55.778125 149.44801 \nL 251.078125 149.44801 \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 55.778125 10.84801 \nL 251.078125 10.84801 \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 62.778125 48.20426 \nL 118.053125 48.20426 \nQ 120.053125 48.20426 120.053125 46.20426 \nL 120.053125 17.84801 \nQ 120.053125 15.84801 118.053125 15.84801 \nL 62.778125 15.84801 \nQ 60.778125 15.84801 60.778125 17.84801 \nL 60.778125 46.20426 \nQ 60.778125 48.20426 62.778125 48.20426 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_21\">\n     <path d=\"M 64.778125 23.946447 \nL 74.778125 23.946447 \nL 84.778125 23.946447 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_12\">\n     <!-- train -->\n     <g transform=\"translate(92.778125 27.446447) 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      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(80.322266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(141.601562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(169.384766 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_22\">\n     <path d=\"M 64.778125 38.624572 \nL 74.778125 38.624572 \nL 84.778125 38.624572 \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_13\">\n     <!-- test -->\n     <g transform=\"translate(92.778125 42.124572) scale(0.1 -0.1)\">\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     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pf75825457d\">\n   <rect x=\"55.778125\" y=\"10.84801\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-md-6 fw=all -->\n",
    "\n",
    "So far we have *named* bias and variance; this experiment has everything we\n",
    "need to *compute* them. Because we know the noiseless target\n",
    "$f(x) = 5 + 1.2 x - 3.4 x^2 + 5.6 x^3$, we can redraw the training noise many\n",
    "times, refit the degree-$d$ polynomial on each draw, and ask two questions on\n",
    "the held-out inputs: how far is the *average* fit from the truth\n",
    "(squared bias), and how much does the fit *fluctuate* across draws (variance)?"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "generalization-bias-variance-decomposition"
   },
   "source": [
    "f = poly @ true_w                        # noiseless target on all inputs\n",
    "bias2, var = [], []\n",
    "for d in range(1, 15):\n",
    "    preds = []\n",
    "    for _ in range(200):                 # 200 fresh draws of training noise\n",
    "        y_tr = f[:n_train] + np.random.normal(scale=0.1, size=n_train)\n",
    "        w, *_ = np.linalg.lstsq(poly[:n_train, :d+1], y_tr, rcond=None)\n",
    "        preds.append(poly[n_train:, :d+1] @ w)\n",
    "    preds = np.stack(preds)\n",
    "    bias2.append(((preds.mean(0) - f[n_train:]) ** 2).mean())\n",
    "    var.append(preds.var(0).mean())\n",
    "d2l.plot(list(range(1, 15)), [bias2, var, np.array(bias2) + np.array(var)],\n",
    "         xlabel='polynomial degree', ylabel='error', yscale='log',\n",
    "         legend=['bias^2', 'variance', 'bias^2 + variance'])"
   ],
   "execution_count": 6,
   "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:53.301301</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 80.741412 145.8 \nL 80.741412 7.2 \n\" clip-path=\"url(#p6ef1de47fa)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"m7b372228b8\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m7b372228b8\" x=\"80.741412\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 2.5 -->\n      <g transform=\"translate(72.789849 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        <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-32\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 114.884768 145.8 \nL 114.884768 7.2 \n\" clip-path=\"url(#p6ef1de47fa)\" 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=\"#m7b372228b8\" x=\"114.884768\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 5.0 -->\n      <g transform=\"translate(106.933206 160.398438) scale(0.1 -0.1)\">\n       <defs>\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-35\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 149.028125 145.8 \nL 149.028125 7.2 \n\" clip-path=\"url(#p6ef1de47fa)\" 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=\"#m7b372228b8\" x=\"149.028125\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 7.5 -->\n      <g transform=\"translate(141.076562 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-37\" d=\"M 525 4666 \nL 3525 4666 \nL 3525 4397 \nL 1831 0 \nL 1172 0 \nL 2766 4134 \nL 525 4134 \nL 525 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-37\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 183.171482 145.8 \nL 183.171482 7.2 \n\" clip-path=\"url(#p6ef1de47fa)\" 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=\"#m7b372228b8\" x=\"183.171482\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 10.0 -->\n      <g transform=\"translate(172.038669 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       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(127.246094 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_9\">\n      <path d=\"M 217.314838 145.8 \nL 217.314838 7.2 \n\" clip-path=\"url(#p6ef1de47fa)\" 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=\"#m7b372228b8\" x=\"217.314838\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 12.5 -->\n      <g transform=\"translate(206.182026 160.398438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(127.246094 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_6\">\n     <!-- polynomial degree -->\n     <g transform=\"translate(102.395312 174.076563) 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-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-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-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       <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-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-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-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-20\" 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-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-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-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      </defs>\n      <use xlink:href=\"#DejaVuSans-70\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(124.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(152.441406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(211.621094 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(275 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(336.181641 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(433.59375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(461.376953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(522.65625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(550.439453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(582.226562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(645.703125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(707.226562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(770.703125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(809.566406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(871.089844 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_11\">\n      <path d=\"M 51.378125 123.192183 \nL 246.678125 123.192183 \n\" clip-path=\"url(#p6ef1de47fa)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_12\">\n      <defs>\n       <path id=\"m89efc13f03\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m89efc13f03\" x=\"51.378125\" y=\"123.192183\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- $\\mathdefault{10^{-4}}$ -->\n      <g transform=\"translate(20.878125 126.991402) 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        <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-2212\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(186.855469 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_13\">\n      <path d=\"M 51.378125 93.623486 \nL 246.678125 93.623486 \n\" clip-path=\"url(#p6ef1de47fa)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m89efc13f03\" x=\"51.378125\" y=\"93.623486\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- $\\mathdefault{10^{-2}}$ -->\n      <g transform=\"translate(20.878125 97.422705) scale(0.1 -0.1)\">\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_3\">\n     <g id=\"line2d_15\">\n      <path d=\"M 51.378125 64.054789 \nL 246.678125 64.054789 \n\" clip-path=\"url(#p6ef1de47fa)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m89efc13f03\" x=\"51.378125\" y=\"64.054789\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(26.778125 67.854008) scale(0.1 -0.1)\">\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=\"ytick_4\">\n     <g id=\"line2d_17\">\n      <path d=\"M 51.378125 34.486092 \nL 246.678125 34.486092 \n\" clip-path=\"url(#p6ef1de47fa)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m89efc13f03\" x=\"51.378125\" y=\"34.486092\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- $\\mathdefault{10^{2}}$ -->\n      <g transform=\"translate(26.778125 38.28531) scale(0.1 -0.1)\">\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=\"text_11\">\n     <!-- error -->\n     <g transform=\"translate(14.798437 88.602344) rotate(-90) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-65\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(61.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(100.886719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(139.75 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(200.931641 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_19\">\n    <path d=\"M 60.255398 60.450232 \nL 73.91274 64.579449 \nL 87.570083 139.5 \nL 101.227426 135.452962 \nL 114.884768 132.859665 \nL 128.542111 128.764486 \nL 142.199454 132.721366 \nL 155.856796 117.607019 \nL 169.514139 113.497006 \nL 183.171482 111.446921 \nL 196.828824 98.523914 \nL 210.486167 85.964651 \nL 224.14351 94.996004 \nL 237.800852 63.212368 \n\" clip-path=\"url(#p6ef1de47fa)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_20\">\n    <path d=\"M 60.255398 108.716524 \nL 73.91274 105.379465 \nL 87.570083 102.520132 \nL 101.227426 99.073142 \nL 114.884768 98.388788 \nL 128.542111 95.482486 \nL 142.199454 87.404064 \nL 155.856796 82.120909 \nL 169.514139 80.334597 \nL 183.171482 77.194635 \nL 196.828824 65.850951 \nL 210.486167 47.606524 \nL 224.14351 31.345549 \nL 237.800852 13.502787 \n\" clip-path=\"url(#p6ef1de47fa)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_21\">\n    <path d=\"M 60.255398 60.446743 \nL 73.91274 64.568293 \nL 87.570083 102.499919 \nL 101.227426 99.050953 \nL 114.884768 98.358935 \nL 128.542111 95.446577 \nL 142.199454 87.39854 \nL 155.856796 82.095413 \nL 169.514139 80.298015 \nL 183.171482 77.16375 \nL 196.828824 65.81148 \nL 210.486167 47.590212 \nL 224.14351 31.345231 \nL 237.800852 13.5 \n\" clip-path=\"url(#p6ef1de47fa)\" 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 58.378125 59.234375 \nL 183.373438 59.234375 \nQ 185.373438 59.234375 185.373438 57.234375 \nL 185.373438 14.2 \nQ 185.373438 12.2 183.373438 12.2 \nL 58.378125 12.2 \nQ 56.378125 12.2 56.378125 14.2 \nL 56.378125 57.234375 \nQ 56.378125 59.234375 58.378125 59.234375 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_22\">\n     <path d=\"M 60.378125 20.298438 \nL 70.378125 20.298438 \nL 80.378125 20.298438 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_12\">\n     <!-- bias^2 -->\n     <g transform=\"translate(88.378125 23.798438) scale(0.1 -0.1)\">\n      <defs>\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-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-5e\" d=\"M 2988 4666 \nL 4684 2925 \nL 4056 2925 \nL 2681 4159 \nL 1306 2925 \nL 678 2925 \nL 2375 4666 \nL 2988 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-62\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(91.259766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(152.539062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-5e\" transform=\"translate(204.638672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(288.427734 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_23\">\n     <path d=\"M 60.378125 34.976563 \nL 70.378125 34.976563 \nL 80.378125 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_13\">\n     <!-- variance -->\n     <g transform=\"translate(88.378125 38.476563) scale(0.1 -0.1)\">\n      <defs>\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-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      </defs>\n      <use xlink:href=\"#DejaVuSans-76\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(59.179688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(120.458984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(161.572266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(189.355469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(250.634766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(314.013672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(368.994141 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_24\">\n     <path d=\"M 60.378125 49.654688 \nL 70.378125 49.654688 \nL 80.378125 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_14\">\n     <!-- bias^2 + variance -->\n     <g transform=\"translate(88.378125 53.154688) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-2b\" d=\"M 2944 4013 \nL 2944 2272 \nL 4684 2272 \nL 4684 1741 \nL 2944 1741 \nL 2944 0 \nL 2419 0 \nL 2419 1741 \nL 678 1741 \nL 678 2272 \nL 2419 2272 \nL 2419 4013 \nL 2944 4013 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-62\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(91.259766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(152.539062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-5e\" transform=\"translate(204.638672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(288.427734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(352.050781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2b\" transform=\"translate(383.837891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(467.626953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-76\" transform=\"translate(499.414062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(558.59375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(619.873047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(660.986328 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(688.769531 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(750.048828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(813.427734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(868.408203 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p6ef1de47fa\">\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-md-7 fw=all -->\n",
    "\n",
    "The U-curve now *visibly decomposes*. Squared bias dominates for degrees below\n",
    "3 and collapses to essentially zero the moment the model class contains the\n",
    "truth; variance is tiny at first but grows relentlessly with surplus capacity,\n",
    "exploding as the polynomial gains the freedom to chase each draw's noise. Their\n",
    "sum (which, up to the irreducible noise floor $\\sigma^2 = 0.01$, is the\n",
    "expected test error) is lowest exactly where the two failure modes trade off,\n",
    "at degree 3. This is a numerical instance of the decomposition proved in\n",
    "that section.\n",
    "\n",
    "### Dataset Size\n",
    "\n",
    "Beyond model complexity,\n",
    "another big consideration\n",
    "to bear in mind is dataset size.\n",
    "Fixing our model, the fewer samples\n",
    "we have in the training dataset,\n",
    "the more likely (and more severely)\n",
    "we are to encounter overfitting.\n",
    "As we increase the amount of training data,\n",
    "the generalization error typically decreases when the learning procedure and\n",
    "data distribution are held fixed. This is a tendency, not a monotonic law:\n",
    "unstable procedures and interpolation thresholds can produce temporary\n",
    "increases, including the sample-wise double descent discussed later.\n",
    "For a fixed task and data distribution,\n",
    "model complexity should not increase\n",
    "more rapidly than the amount of data.\n",
    "Given more data, we might  attempt\n",
    "to fit a more complex model.\n",
    "Absent sufficient data, simpler models\n",
    "may be more difficult to beat.\n",
    "For many tasks, deep learning\n",
    "only outperforms linear models\n",
    "when many thousands of training examples are available.\n",
    "In part, the current success of deep learning\n",
    "owes considerably to the abundance of massive datasets\n",
    "arising from Internet companies, cheap storage,\n",
    "connected devices, and the broad digitization of the economy.\n",
    "\n",
    "## Model Selection\n",
    "\n",
    "Typically, we select our final model\n",
    "only after evaluating multiple models\n",
    "that differ in various ways\n",
    "(different architectures, training objectives,\n",
    "selected features, data preprocessing,\n",
    "learning rates, etc.).\n",
    "Choosing among many models is aptly\n",
    "called *model selection*.\n",
    "\n",
    "In principle, we should not touch our test set\n",
    "until after we have chosen all our hyperparameters.\n",
    "Were we to use the test data in the model selection process,\n",
    "there is a risk that we might overfit the test data.\n",
    "Then we would be in serious trouble.\n",
    "If we overfit our training data,\n",
    "there is always the evaluation on test data to keep us honest.\n",
    "But if we overfit the test data, how would we ever know?\n",
    "See @ong2005learning for an example of how\n",
    "this can lead to absurd results even for models where the complexity\n",
    "can be tightly controlled.\n",
    "\n",
    "Thus, we should never rely on the test data for model selection.\n",
    "And yet we cannot rely solely on the training data\n",
    "for model selection either because\n",
    "we cannot estimate the generalization error\n",
    "on the very data that we use to train the model.\n",
    "\n",
    "\n",
    "In practical applications, the picture gets muddier.\n",
    "While ideally we would only touch the test data once,\n",
    "to assess the very best model or to compare\n",
    "a small number of models with each other,\n",
    "real-world test data is seldom discarded after just one use.\n",
    "We can seldom afford a new test set for each round of experiments.\n",
    "In fact, recycling benchmark data for decades\n",
    "can have a significant impact on the\n",
    "development of algorithms, as documented when researchers rebuilt fresh test\n",
    "sets for long-standing benchmarks and watched accuracy drop\n",
    "[@Recht.Roelofs.Schmidt.ea.2019]. This effect is visible, e.g., for\n",
    "[image classification](https://paperswithcode.com/sota/image-classification-on-imagenet)\n",
    "and [optical character recognition](https://paperswithcode.com/sota/image-classification-on-mnist).\n",
    "\n",
    "The common practice for addressing the problem of *training on the test set*\n",
    "is to split our data three ways,\n",
    "incorporating a *validation set*\n",
    "in addition to the training and test datasets.\n",
    "The result is a murky business where the boundaries\n",
    "between validation and test data are worryingly ambiguous.\n",
    "Unless explicitly stated otherwise, in the experiments in this book\n",
    "we are really working with what should rightly be called\n",
    "training data and validation data, with no true test sets.\n",
    "Therefore, the accuracy reported in each experiment of the book is really\n",
    "the validation accuracy and not a true test set accuracy.\n",
    "\n",
    "### Cross-Validation\n",
    "\n",
    "When training data is scarce,\n",
    "we might not even be able to afford to hold out\n",
    "enough data to constitute a proper validation set.\n",
    "One popular solution to this problem is to employ\n",
    "$K$*-fold cross-validation*.\n",
    "Here, the original training data is split into $K$ non-overlapping subsets.\n",
    "Then model training and validation are executed $K$ times,\n",
    "each time training on $K-1$ subsets and validating\n",
    "on a different subset (the one not used for training in that round).\n",
    "Finally, the training and validation errors are estimated\n",
    "by averaging over the results from the $K$ experiments.\n",
    "The procedure is illustrated in the figure.\n",
    "\n",
    "![In $K$-fold cross-validation, each of the $K$ folds serves once as the validation set (orange) while the model trains on the remaining folds (blue); the final estimate averages the $K$ validation scores.](../img/mdl-mlp-kfold.svg)\n",
    "\n",
    "How should we choose $K$? The choice trades off bias, variance, and compute.\n",
    "Each fold's model is trained on only $(K-1)/K$ of the data. If the learning\n",
    "curve improves monotonically with sample size, its error is higher than that\n",
    "of the model finally trained on all the data, making the cross-validation\n",
    "estimate pessimistic. This conclusion is not guaranteed for unstable or\n",
    "non-monotone learning procedures.\n",
    "Taking $K = n$ (*leave-one-out* cross-validation) all but eliminates this bias,\n",
    "but at a steep price: it requires $n$ model fits, and the $n$ training sets\n",
    "are nearly identical, so the fold errors are highly correlated and their\n",
    "average tends to have higher variance; in fact no general unbiased estimator\n",
    "of the cross-validation variance exists [@Bengio.Grandvalet.2004].\n",
    "The standard compromise, $K = 5$ or $K = 10$, keeps the bias modest, averages\n",
    "over reasonably distinct training sets, and costs only $5$--$10$ fits, which is\n",
    "why these values dominate practice [@Kohavi.1995].\n",
    "(Exercises 4 and 5 ask you to reason through the cost and the bias.)\n",
    "\n",
    "\n",
    "## Summary\n",
    "\n",
    "This section explored some of the  underpinnings\n",
    "of generalization in  machine learning.\n",
    "Some of these ideas become complicated\n",
    "and counterintuitive when we get to deeper models; here, models are capable of overfitting data badly,\n",
    "and the relevant notions of complexity\n",
    "can be both implicit and counterintuitive\n",
    "(e.g., larger architectures with more parameters\n",
    "generalizing better).\n",
    "We leave you with a few rules of thumb:\n",
    "\n",
    "1. Use validation sets (or $K$*-fold cross-validation*) for model selection;\n",
    "1. More complex models often require more data;\n",
    "1. Relevant notions of complexity include both the number of parameters and the range of values that they are allowed to take;\n",
    "1. Keeping the learning procedure and data distribution fixed, more data usually improves generalization, but the curve need not be monotone;\n",
    "1. This entire talk of generalization is all predicated on the IID assumption. If we relax this assumption, allowing for distributions to shift between the train and testing periods, then we cannot say anything about generalization absent a further (perhaps milder) assumption.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. When can you solve the problem of polynomial regression exactly?\n",
    "1. Give at least five examples where dependent random variables make treating the problem as IID data inadvisable.\n",
    "1. Can you ever expect to see zero training error? Under which circumstances would you see zero generalization error?\n",
    "1. Why is $K$-fold cross-validation very expensive to compute?\n",
    "1. Why is the $K$-fold cross-validation error estimate biased?\n",
    "1. The VC dimension is defined as the maximum number of points that can be classified with arbitrary labels $\\{\\pm 1\\}$ by a function of a class of functions. Why might this not be a good idea for measuring how complex the class of functions is? Hint: consider the magnitude of the functions.\n",
    "1. Your manager gives you a difficult dataset on which your current algorithm does not perform so well. How would you justify to him that you need more data? Hint: you cannot increase the data but you can decrease it.\n",
    "1. Re-run the polynomial-fitting experiment above with `n_train` set to 10, 40, and 100. At what degree does the test loss start to climb in each case? Relate your finding to the rule of thumb that more complex models require more data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=generalization-md-8 fw=pytorch -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/97)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
