En la teoría del aprendizaje computacional ( aprendizaje automático y teoría de la computación ), la complejidad de Rademacher , que lleva el nombre de Hans Rademacher , mide la riqueza de una clase de funciones de valor real con respecto a una distribución de probabilidad .
Definiciones
Complejidad Rademacher de un conjunto
Dado un conjunto , la complejidad de Rademacher de A se define de la siguiente manera: [1] [2] : 326
dónde son variables aleatorias independientes extraídas de la distribución de Rademacher, es decir, por , y . Algunos autores toman el valor absoluto de la suma antes de tomar el supremo, pero sies simétrico, esto no hace ninguna diferencia.
Complejidad de Rademacher de una clase de función
Dada una muestra y una clase de funciones de valor real definidas en un espacio de dominio , dónde es la función de pérdida de un clasificador , la complejidad empírica de Rademacher de dado Se define como:
Esto también se puede escribir usando la definición anterior: [2] : 326
dónde denota la composición de la función , es decir:
Dejar ser una distribución de probabilidad sobre . La complejidad de Rademacher de la clase de función con respecto a para el tamaño de la muestra es:
donde la expectativa anterior se toma sobre una muestra distribuida de manera idéntica independientemente (iid) generado de acuerdo con .
Ejemplos de
1. contains a single vector, e.g., . Then:
The same is true for every singleton hypothesis class.[3]:56
2. contains two vectors, e.g., . Then:
Usando la complejidad de Rademacher
The Rademacher complexity can be used to derive data-dependent upper-bounds on the learnability of function classes. Intuitively, a function-class with smaller Rademacher complexity is easier to learn.
Bounding the representativeness
In machine learning, it is desired to have a training set that represents the true distribution of some sample data . This can be quantified using the notion of representativeness. Denote by the probability distribution from which the samples are drawn. Denote by the set of hypotheses (potential classifiers) and denote by the corresponding set of error functions, i.e., for every hypothesis , there is a function , that maps each training sample (features,label) to the error of the classifier (note in this case hypothesis and classifier are used interchangeably). For example, in the case that represents a binary classifier, the error function is a 0–1 loss function, i.e. the error function returns 1 if correctly classifies a sample and 0 else. We omit the index and write instead of when the underlying hypothesis is irrelevant. Define:
- – the expected error of some error function on the real distribution ;
- – the estimated error of some error function on the sample .
The representativeness of the sample , with respect to and , is defined as:
Smaller representativeness is better, since it provides a way to avoid overfitting: it means that the true error of a classifier is not much higher than its estimated error, and so selecting a classifier that has low estimated error will ensure that the true error is also low. Note however that the concept of representativeness is relative and hence can not be compared across distinct samples.
The expected representativeness of a sample can be bounded above by the Rademacher complexity of the function class:[2]:326
Bounding the generalization error
When the Rademacher complexity is small, it is possible to learn the hypothesis class H using empirical risk minimization.
For example, (with binary error function),[2]:328 for every , with probability at least , for every hypothesis :
Limitando la complejidad de Rademacher
Since smaller Rademacher complexity is better, it is useful to have upper bounds on the Rademacher complexity of various function sets. The following rules can be used to upper-bound the Rademacher complexity of a set .[2]:329–330
1. If all vectors in are translated by a constant vector , then Rad(A) does not change.
2. If all vectors in are multiplied by a scalar , then Rad(A) is multiplied by .
3. Rad(A + B) = Rad(A) + Rad(B).[3]:56
4. (Kakade & Tewari Lemma) If all vectors in are operated by a Lipschitz function, then Rad(A) is (at most) multiplied by the Lipschitz constant of the function. In particular, if all vectors in are operated by a contraction mapping, then Rad(A) strictly decreases.
5. The Rademacher complexity of the convex hull of equals Rad(A).
6. (Massart Lemma) The Rademacher complexity of a finite set grows logarithmically with the set size. Formally, let be a set of vectors in , and let be the mean of the vectors in . Then:
In particular, if is a set of binary vectors, the norm is at most , so:
Let be a set family whose VC dimension is . It is known that the growth function of is bounded as:
- for all :
This means that, for every set with at most elements, . The set-family can be considered as a set of binary vectors over . Substituting this in Massart's lemma gives:
With more advanced techniques (Dudley's entropy bound and Haussler's upper bound[4]) one can show, for example, that there exists a constant , such that any class of -indicator functions with Vapnik–Chervonenkis dimension has Rademacher complexity upper-bounded by .
The following bounds are related to linear operations on – a constant set of vectors in .[2]:332–333
1. Define the set of dot-products of the vectors in with vectors in the unit ball. Then:
2. Define the set of dot-products of the vectors in with vectors in the unit ball of the 1-norm. Then:
The following bound relates the Rademacher complexity of a set to its external covering number – the number of balls of a given radius whose union contains . The bound is attributed to Dudley.[2]:338
Suppose is a set of vectors whose length (norm) is at most . Then, for every integer :
In particular, if lies in a d-dimensional subspace of , then:
Substituting this in the previous bound gives the following bound on the Rademacher complexity:
Complejidad gaussiana
Gaussian complexity is a similar complexity with similar physical meanings, and can be obtained from the Rademacher complexity using the random variables instead of , where are Gaussian i.i.d. random variables with zero-mean and variance 1, i.e. . Gaussian and Rademacher complexities are known to be equivalent up to logarithmic factors.
Eqivalence of Rademacher and Gaussian complexity
Given a set then it holds that:
Where is the Gaussian Complexity of A
Referencias
- ^ Balcan, Maria-Florina (November 15–17, 2011). "Machine Learning Theory – Rademacher Complexity" (PDF). Retrieved 10 December 2016.
- ^ a b c d e f g Chapter 26 in Shalev-Shwartz, Shai; Ben-David, Shai (2014). Understanding Machine Learning – from Theory to Algorithms. Cambridge University Press. ISBN 9781107057135.
- ^ a b Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Foundations of Machine Learning. USA, Massachusetts: MIT Press. ISBN 9780262018258.
- ^ Bousquet, O. (2004). Introduction to Statistical Learning Theory. Biological Cybernetics, 3176(1), 169–207. http://doi.org/10.1007/978-3-540-28650-9_8
- Peter L. Bartlett, Shahar Mendelson (2002) Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research 3 463–482
- Giorgio Gnecco, Marcello Sanguineti (2008) Approximation Error Bounds via Rademacher's Complexity. Applied Mathematical Sciences, Vol. 2, 2008, no. 4, 153–176