Sample complexity

Machine learning and data mining

Problems Classification Clustering Regression Anomaly detection Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Supervised learning (classification • regression) Decision trees Ensembles (Bagging, Boosting, Random forest) k-NN Linear regression Naive Bayes Neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH Hierarchical k-means Expectation-maximization (EM) DBSCAN OPTICS Mean-shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA t-SNE
Structured prediction Graphical models (Bayes net, CRF, HMM)
Anomaly detection k-NN Local outlier factor
Neural nets Autoencoder Deep learning Multilayer perceptron RNN Restricted Boltzmann machine SOM Convolutional neural network
Reinforcement Learning Q-Learning SARSA Temporal Difference (TD)
Theory Bias-variance dilemma Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine learning venues NIPS ICML ML JMLR ArXiv:cs.LG
Related articles List of datasets for machine learning research Outline of machine learning
Machine learning portal

The sample complexity of a machine learning algorithm represents the number of training-samples that it needs in order to successfully learn a target function.

More precisely, the sample complexity is the number of training-samples that we need to supply to the algorithm, so that the function returned by the algorithm is within an arbitrarily small error of the best possible function, with probability arbitrarily close to 1.

There are two variants of sample complexity:

The weak variant fixes a particular input-output distribution;
The strong variant takes the worst-case sample complexity over all input-output distributions.

The No Free Lunch theorem, discussed below, proves that, in general, the strong sample complexity is infinite. I.e, there is no algorithm that can learn the globally-optimal target function using a finite number of training samples.

However, if we are only interested in a particular class of target functions (e.g, only linear functions) then the sample complexity is finite, and it depends linearly on the VC dimension on the class of target functions. ^[1]

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 $X\times Y$ . For example, in the setting of binary classification, $X$ is typically a finite-dimensional vector space and $Y$ is the set $\{-1,1\}$ .

Fix a hypothesis space ${\mathcal {H}}$ of functions $h\colon X\to Y$ . A learning algorithm over ${\mathcal {H}}$ is a computable map from $Z^{*}$ to ${\mathcal {H}}$ . 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, without or with Tikhonov regularization.

Fix a loss function $Loss\colon Y\times Y\to \mathbb {R} _{\geq 0}$ , for example, the square loss $Loss(y,y')=(y-y')^{2}$ . For a given distribution $\rho$ on $X\times Y$ , the expected risk of a hypothesis (a function) $h\in {\mathcal {H}}$ is

{\mathcal {E}}(h):=\mathbb {E} _{\rho }[Loss(h(x),y)]=\int _{X\times Y}Loss(h(x),y)\,d\rho (x,y)

In our setting, we have $h=ALG(S_{n})$ where $ALG$ is a learning algorithm and $S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}$ is a sequence of vectors which are all drawn independently from $\rho$ . Define the optimal risk

{\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h).

Set $h_{n}=Alg(S_{n})$ for each $n$ . Note that

$h_{n}$ is a random variable and depends on the random variable $S_{n}$ , which is drawn from the distribution $\rho ^{n}$ . The algorithm $ALG$ is called consistent if ${\mathcal {E}}(h_{n})$ probabilistically converges to ${\mathcal {E}}_{\mathcal {H}}^{*}$ , in other words, for all ε, δ > 0, there exists a positive integer N such that for all n ≥ N, we have

\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .

The sample complexity of $ALG$ is then the minimum N for which this holds, as a function of ρ, ε, and δ. We write the sample complexity as $N(\rho ,\epsilon ,\delta )$ to emphasize that this value of N depends on ρ, ε, and δ. If $ALG$ is not consistent, then we set $N(\rho ,\epsilon ,\delta )=\infty$ . If there exists an algorithm for which $N(\rho ,\epsilon ,\delta )$ is finite, then we say that the hypothesis space ${\mathcal {H}}$ is learnable.

In words, the sample complexity $N(\rho ,\epsilon ,\delta )$ defines the rate of consistency of the algorithm: given a desired accuracy ε and confidence δ, one needs to sample $N(\rho ,\epsilon ,\delta )$ data points to guarantee that the risk of the output function is within ε of the best possible, with probability at least 1 - δ.^[2]

In probabilistically approximately correct (PAC) learning, one is concerned with whether the sample complexity is polynomial, that is, whether $N(\rho ,\epsilon ,\delta )$ is bounded by a polynomial in 1/ε and 1/δ. If $N(\rho ,\epsilon ,\delta )$ is polynomial for some learning algorithm, then one says that the hypothesis space ${\mathcal {H}}$ is PAC-learnable. Note that this is a stronger notion than being learnable.

Unrestricted hypothesis space: infinite sample complexity

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 $ALG$ such that, for all ε, δ > 0, there exists a positive integer N such that for all n ≥ N, we have

\sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,

where $h_{n}=ALG(S_{n})$ , with $S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}$ as above. The No Free Lunch Theorem says that without restrictions on the hypothesis space ${\mathcal {H}}$ , this is not the case, i.e., there always exist "bad" distributions for which the sample complexity is arbitrarily large.^[1]

Thus, in order to make statements about the rate of convergence of the quantity

\sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(f_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),

one must either

constrain the space of probability distributions $\rho$ , e.g. via a parametric approach, or
constrain the space of hypotheses ${\mathcal {H}}$ , as in distribution-free approaches.

Restricted hypothesis space: finite sample-complexity

The latter approach leads to concepts such as VC dimension and Rademacher complexity which control the complexity of the space ${\mathcal {H}}$ . A smaller hypothesis space introduces more bias into the inference process, meaning that ${\mathcal {E}}_{\mathcal {H}}^{*}$ 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.^[2]

It is a theorem from VC theory that the following three statements are equivalent for a hypothesis space ${\mathcal {H}}$ :

${\mathcal {H}}$ is PAC-learnable.
The VC dimension of ${\mathcal {H}}$ is finite.
${\mathcal {H}}$ is a uniform Glivenko-Cantelli class.

This gives a way to prove that certain hypothesis spaces are PAC learnable, and by extension, learnable.

An example of a PAC-learnable hypothesis space

Let X = R^d, Y = {-1, 1}, and let ${\mathcal {H}}$ be the space of affine functions on X, that is, functions of the form $x\mapsto \langle w,x\rangle +b$ for some $w\in \mathbb {R} ^{d},b\in \mathbb {R}$ . 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 ${\mathcal {H}}$ is $d+1$ , in particular finite. It follows by the above characterization of PAC-learnable classes that ${\mathcal {H}}$ is PAC-learnable, and by extension, learnable.

Sample-complexity bounds

Suppose ${\mathcal {H}}$ is a class of binary functions (functions to {0,1}). Then, ${\mathcal {H}}$ is $(\epsilon ,\delta )$ -PAC-learnable with a sample of size: ^[3]

N=O{\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}

where $VC({\mathcal {H}})$ is the VC dimension of ${\mathcal {H}}$ . Moreover, any $(\epsilon ,\delta )$ -PAC-learning algorithm for ${\mathcal {H}}$ must have sample-complexity:^[4]

N=\Omega {\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}

Thus, the sample-complexity is a linear function of the VC dimension of the hypothesis space.

Suppose ${\mathcal {H}}$ is a class of real-valued functions with range in [0,T]. Then, ${\mathcal {H}}$ is $(\epsilon ,\delta )$ -PAC-learnable with a sample of size: ^[5]^[6]

N=O{\bigg (}T^{2}{\frac {PD({\mathcal {H}})\ln {T \over \epsilon }+\ln {1 \over \delta }}{\epsilon ^{2}}}{\bigg )}

where $PD({\mathcal {H}})$ is Pollard's pseudo-dimension of ${\mathcal {H}}$ .

Other Settings

In addition to the supervised learning setting, sample complexity is relevant to semi-supervised learning problems including active learning,^[7] where the algorithm can ask for labels to specifically chosen inputs in order to reduce the cost of obtaining many labels. The concept of sample complexity also shows up in reinforcement learning,^[8] online learning, and unsupervised algorithms, e.g. for dictionary learning.^[9]

References

1 2 Vapnik, Vladimir (1998), Statistical Learning Theory, New York: Wiley.
1 2 Rosasco, Lorenzo (2014), Consistency, Learnability, and Regularization, Lecture Notes for MIT Course 9.520.
↑ Steve Hanneke (2016). "The optimal sample complexity OF PAC learning".
↑ Ehrenfeucht, Andrzej; Haussler, David; Kearns, Michael; Valiant, Leslie (1989). "A general lower bound on the number of examples needed for learning". Information and Computation. 82 (3): 247. doi:10.1016/0890-5401(89)90002-3.
↑ Anthony, Martin; Bartlett, Peter L. (2009). Neural Network Learning: Theoretical Foundations. ISBN 9780521118620.
↑ On the Pseudo-Dimension of Nearly Optimal Auctions. NIPS. 2015. arXiv:1506.03684 .
↑ Balcan, Maria-Florina (2010). "The true sample complexity of active learning". Machine Learning. 80 (2–3): 111–139. doi:10.1007/s10994-010-5174-y.
↑ Kakade, Sham (2003), On the Sample Complexity of Reinforcement Learning (PDF), PhD Thesis, University College London: Gatsby Computational Neuroscience Unit.
↑ Vainsencher, Daniel; Mannor, Shie; Bruckstein, Alfred (2011). "The Sample Complexity of Dictionary Learning" (PDF). Journal of Machine Learning Research. 12: 3259–3281.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.