hypothesis space
In plain wordsThe full menu of possible models a learning method is allowed to choose from — for example, all straight lines. Learning means picking the item on the menu that best fits the data.
The set of candidate functions (hypotheses) that a learning algorithm can output, fixed by the choice of model family and its constraints — all linear classifiers over given features, all decision trees of depth at most five, or all functions computable by a network of a given architecture. Learning is a search through this set for a hypothesis consistent with, or best fitting, the training data, as in empirical risk minimizationempirical risk minimization, n.: The basic recipe of most machine learning: from the models on offer, pick the one with the smallest errors on the training examples, trusting that score as a guide to how it will do on new data.. Its choice is the restrictive part of a learner's inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases.: too small a space may contain no good approximation (underfittingunderfitting, n.: When a model is too simple, or trained too little, to capture the real pattern in the data, so it does poorly even on the examples it learned from.), while too rich a space admits hypotheses that fit noise (overfittingoverfitting, n.: When a model learns its training examples too well — quirks and noise included — so it does great on data it has seen but poorly on anything new, like a student who memorizes answers without understanding.). Learning theory measures richness with quantities such as cardinality, VC dimensionVC dimension, n.: A measure of how flexible a family of prediction rules is: the largest number of points it can label in every possible way. More flexible families need more data to learn reliably. and Rademacher complexity, which govern how much data is needed to generalize, as in PAC learningPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right.. In concept learning, the version space is the subset of hypotheses consistent with every example seen so far.
Restricting the hypothesis space to monotone functions made the credit model both safer and easier to audit.
Origin
The view of learning as search through a space of hypotheses was set out in Tom Mitchell's work on version spaces (1977) and 'Generalization as Search' (Artificial Intelligence, 1982); Leslie Valiant's PAC model (1984) and Vapnik–Chervonenkis theory made the hypothesis class the central object of learning theory.
Usage note
Unrelated to the hypotheses of statistical significance testing (see p-valuep-value, n.: A number saying how surprising your data would be if nothing interesting were going on. A small p-value hints at a real effect, but it is not the probability that the effect is real.). For deep networks, the functions actually reachable depend on the optimizer and training budget, not only on the architecture (see implicit regularizationimplicit regularization, n.: The hidden preferences of a training method itself: even with no explicit rule against complexity, the way a model is trained tends to steer it toward simpler solutions.).
Related
- inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases.
- PAC learningPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right.
- VC dimensionVC dimension, n.: A measure of how flexible a family of prediction rules is: the largest number of points it can label in every possible way. More flexible families need more data to learn reliably.
- empirical risk minimizationempirical risk minimization, n.: The basic recipe of most machine learning: from the models on offer, pick the one with the smallest errors on the training examples, trusting that score as a guide to how it will do on new data.
- overfittingoverfitting, n.: When a model learns its training examples too well — quirks and noise included — so it does great on data it has seen but poorly on anything new, like a student who memorizes answers without understanding.
- no free lunch theoremno free lunch theorem, n.: A mathematical result saying that no learning or search method is best for every possible problem: any method that wins on some problems must lose on others.
Sources
- Mitchell, T. M. (1982). Generalization as Search. Artificial Intelligence, 18(2), 203–226.
Mentioned in
empirical risk minimizationempirical risk minimization, n.: The basic recipe of most machine learning: from the models on offer, pick the one with the smallest errors on the training examples, trusting that score as a guide to how it will do on new data.