608 lines
29 KiB
Plaintext
608 lines
29 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "4eec6672",
|
|
"metadata": {
|
|
"origin_pos": 0
|
|
},
|
|
"source": [
|
|
"# Generalization in Classification\n",
|
|
"\n",
|
|
":label:`chap_classification_generalization`\n",
|
|
"\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 :numref:`sec_generalization_basics` 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 $\\epsilon$,\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 $\\epsilon$ 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 profound 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",
|
|
"remarkably 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 :numref:`chap_perceptrons`,\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 :numref:`sec_prob`.\n",
|
|
"\n",
|
|
"An important classical result from probability theory\n",
|
|
"called the *central limit theorem* guarantees\n",
|
|
"that whenever we possess $n$ random samples $a_1, ..., a_n$\n",
|
|
"drawn from any distribution with mean $\\mu$ and 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 reduce our test error by a factor of one hundred,\n",
|
|
"we must collect ten thousand times as large a test set.\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",
|
|
"While $\\epsilon(f)$ is initially unknown,\n",
|
|
"we know that it cannot be greater than $1$.\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",
|
|
"\n",
|
|
"$$P(\\epsilon_\\mathcal{D}(f) - \\epsilon(f) \\geq t) < \\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 15,000 examples are required\n",
|
|
"as compared to 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",
|
|
"## 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",
|
|
":numref:`sec_generalization_basics` 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 not only are you getting your new model $f_2$ to work\n",
|
|
"but 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, not only are you testing multiple functions,\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",
|
|
":cite:`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",
|
|
"\n",
|
|
"\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 a 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 seminal papers,\n",
|
|
"Vapnik and Chervonenkis extended\n",
|
|
"the theory on the convergence\n",
|
|
"of relative frequencies\n",
|
|
"to more general classes of functions\n",
|
|
":cite:`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(R[p, f] - R_\\textrm{emp}[\\mathbf{X}, \\mathbf{Y}, f] < \\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",
|
|
"The VC dimension quantifies the largest\n",
|
|
"number of data points for which we can assign\n",
|
|
"any arbitrary (binary) labeling\n",
|
|
"and for each find some model $f$ in the class\n",
|
|
"that agrees with that labeling.\n",
|
|
"For example, linear models on $d$-dimensional inputs\n",
|
|
"have VC dimension $d+1$.\n",
|
|
"It is easy to see that a line can assign\n",
|
|
"any possible labeling to three points in two dimensions,\n",
|
|
"but not to four.\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",
|
|
"\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",
|
|
"Indeed test set evaluation is the bedrock\n",
|
|
"of 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 Chernovenkis\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 revolutionary discovery of VC dimension,\n",
|
|
"numerous alternative complexity measures have been proposed,\n",
|
|
"each facilitating an analogous generalization guarantee.\n",
|
|
"See :citet:`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.\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",
|
|
"In the next chapter, we will revisit generalization\n",
|
|
"in the context of deep learning.\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",
|
|
"\n",
|
|
"[Discussions](https://discuss.d2l.ai/t/6829)\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
},
|
|
"required_libs": []
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
} |