Content deleted Content added
No edit summary |
Added major changes from Yongyi781/sandbox Tag: nowiki added |
||
Line 1:
{{Machine learning bar}}
In [[machine learning]], the '''sample complexity''' of a machine learning algorithm is, roughly speaking, the number of
There are two variants of sample complexity. The weak variant fixes a particular input-output distribution, and the strong variant takes the worst-case sample complexity over all input-output distributions. A natural question in statistical learning is to ask, for a given hypothesis space, whether the sample complexity is finite in the strong sense, that is, there is a bound on the number of samples needed so that an algorithm can approximately solve all possible learning problems on a particular input-output space no matter the distribution of data over that space. The No Free Lunch Theorem, discussed below, says that this is always impossible if the hypothesis space is not constrained<ref name=":0" />.
==Definition==
Let ''X'' be a space which we call the input space, and ''Y'' be a space which we call the output space, and let ''Z'' denote the product {{Math|''X'' × ''Y''}}. For example, in the setting of binary classification, ''X'' is typically a finite-dimensional vector space and ''Y'' is the set {{Math|{-1,1<nowiki>}</nowiki>}}.
\mathcal R(f) = \mathbb E_\rho[V(f(x),y)],▼
Fix a hypothesis space <math>\mathcal H</math> of functions <math>f\colon X\to Y</math>. A learning algorithm over <math>\mathcal H</math> is a computable map from <math>Z^*</math> to <math>\mathcal H</math>. In other words, it is an algorithm that takes as input a finite sequence of training samples and outputs a function from ''X'' to ''Y''. Typical learning algorithms include empirical risk minimization and empirical risk minimization with [[Tikhonov regularization]].
Fix a loss function <math>V\colon Y\times Y\to\R_{\geq 0}</math>, for example, the square loss <math>
V(y,y')=(y-y')^2
</math>. For a given distribution ''ρ'' on {{Math|''X'' × ''Y''}}, the expected risk of a function <math>f\in\mathcal H</math> is
In our setting, we have <math>f=A(S_n)</math> where ''A'' is a learning algorithm and <math>S_n = ((x_1,y_1),\ldots,(x_n,y_n))\sim \rho^n</math> is a sequence of vectors which are all drawn independently from ''ρ''. Define the optimal risk<math display="block">
</math>Set <math>f_n=A(S_n)</math> for each ''n''. Note that {{Math|''f<sub>n</sub>''}} is a random variable and depends on the random variable {{Math|''S<sub>n</sub>''}}, which is drawn from the distribution {{Math|''ρ<sup>n</sup>''}}. The algorithm ''A'' is called consistent if <math>
\mathcal E(f_n)
</math> probabilistically converges to <math>
\mathcal E_\mathcal H^*
</math>, in other words, for all ''ε'', ''δ'' > 0, there exists a positive integer ''N'' such that for all ''n'' ≥ ''N'', we have<math display="block">
\
</math>The sample complexity of ''A'' is then the minimum ''N'' for which this holds, as a function of ''ρ'', ''ε'', and ''δ''. We write the sample complexity as ''N''(''ρ'', ''ε'', ''δ'') to emphasize that this value of ''N'' depends on ''ρ'', ''ε'', and ''δ''. If ''A'' is not consistent, then we set ''N''(''ρ'', ''ε'', ''δ'') = ∞. If there exists an algorithm for which ''N'' is finite, then we say that the hypothesis space <math>
\mathcal H
</math> is '''learnable'''.
In words, the sample complexity
In [[Probably approximately correct learning|probabilistically approximately correct (PAC) learning]], one is concerned with whether the sample complexity is ''polynomial'', that is, whether ''N''(''ρ'', ''ε'', ''δ'') is bounded by a polynomial in 1/''ε'' and 1/''δ''. If ''N''(''ρ'', ''ε'', ''δ'') is polynomial for some learning algorithm, then one says that that the hypothesis space <math>
\mathcal H
</math> is '''PAC-learnable'''. Note that this is a stronger notion than being learnable.
One can ask whether there exists a learning algorithm so that the sample complexity is finite in the strong sense, that is, there is a bound on the number of samples needed so that the algorithm can learn any distribution over the input-output space with a specified target error. More formally, one asks whether there exists a learning algorithm ''A'' such that, for all ''ε'', ''δ'' > 0, there exists a positive integer ''N'' such that for all ''n'' ≥ ''N'', we have<math display="block">
▲\mathbb P_{S_n}(\mathcal R(f_n) - \mathcal R^*_\mathcal{H} > \epsilon) < \delta.
\
\sup_\rho\left(\Pr_{\rho^n}[\mathcal E(f_n) - \mathcal E^*_\mathcal{H}\geq\varepsilon]\right),
</math>one must either▼
*constrain the space of probability distributions <math>\rho</math>, e.g. via a parametric approach, or▼
The latter approach leads to concepts such as [[VC dimension]] and [[Rademacher complexity]] which control the complexity of the space <math>\mathcal H</math>. A smaller hypothesis space introduces more bias into the inference process, meaning that <math>\mathcal
It is a theorem from [[Vapnik–Chervonenkis theory|VC theory]] that the following three statements are equivalent for a hypothesis space <math>\mathcal H</math>:
▲In words, the sample complexity <math>n(\rho,\epsilon,\delta)</math> defines the rate of consistency of the algorithm: given a desired accuracy <math>\epsilon</math> and confidence <math>\delta</math>, one needs to sample at most <math>n(\rho,\epsilon,\delta)</math> data points to guarantee that the risk of the output function is within <math>\epsilon</math> of the best possible, with probability at least <math>1-\delta</math>.<ref name = "Rosasco">{{citation |last = Rosasco | first = Lorenzo | title = Consistency, Learnability, and Regularization | series = Lecture Notes for MIT Course 9.520. | year = 2014 }}</ref>
# <math>\mathcal H</math> is PAC-learnable.
# The VC dimension of <math>\mathcal H</math> is finite.
# <math>\mathcal H</math> is a uniform [[Glivenko-Cantelli class]].
This gives a nice way to prove that certain hypothesis spaces are PAC learnable, and by extension, learnable.
== An example of a PAC-learnable hypothesis space ==
▲==No Free Lunch Theorem (Machine Learning)==
Let ''X'' = '''R'''<sup>''d''</sup>, ''Y'' = {-1, 1}, and let <math>\mathcal H</math> be the space of affine functions on ''X'', that is, functions of the form <math>x\mapsto \langle w,x\rangle+b</math> for some <math>w\in\R^d,b\in\R</math>. This is the linear classification with offset learning problem. Now, note that four coplanar points in a square cannot be shattered by any affine function, since no affine function can be positive on two diagonally opposite vertices and negative on the remaining two. Thus, the VC dimension of <math>\mathcal H</math> is 3, in particular finite. It follows by the above characterization of PAC-learnable classes that <math>\mathcal H</math> is PAC-learnable, and by extension, learnable.
▲Optimistically one could hope for a stronger notion of sample complexity that is independent of the distribution <math>\rho</math> on the input and output spaces. However, it has been shown that without restrictions on the hypothesis class <math>\mathcal H</math>, there always exists "bad" distributions for which the sample complexity is arbitrarily large.<ref>{{citation |last = Vapnik | first = Vladimir | title = Statistical Learning Theory | place = New York | publisher = Wiley. | year = 1998}}</ref> Thus in order to make statements about the rate of convergence of the quantity
▲\underset{\rho}{\sup}\ \mathbb P_{S_n}(\mathcal R(f_n) - \mathcal R^*_\mathcal{H} > \epsilon),
▲one must either
▲*constrain the space of probability distributions <math>\rho</math>, e.g. via a parametric approach, or
▲*constrain the space of hypotheses <math>\mathcal H</math>, as in distribution free approaches.
▲The latter approach leads to concepts such as [[VC dimension]] and [[Rademacher complexity]] which control the complexity of the space <math>\mathcal H</math>. A smaller hypothesis space introduces more bias into the inference process, meaning that <math>\mathcal R^*_\mathcal{H}</math> may be greater than the best possible risk in a larger space. However, by restricting the complexity of the hypothesis space it becomes possible for an algorithm to produce more uniformly consistent functions. This trade-off leads to the concept of [[regularization (mathematics)|regularization]].<ref name = "Rosasco" />
==Other Settings==
In addition to the supervised learning setting, sample complexity is relevant to [[semi-supervised learning]] problems including [[active learning]],<ref name
==References==
| |||