Learnable function class

In statistical learning theory, a learnable function class is a set of functions for which an algorithm can be devised to asymptotically minimize the expected risk, uniformly over all probability distributions. The concept of learnable classes are closely related to regularization in machine learning, and provides large sample justifications for certain learning algorithms.

Definition

edit

Background

edit

Let   be the sample space, where   are the labels and   are the covariates (predictors).   is a collection of mappings (functions) under consideration to link   to  .   is a pre-given loss function (usually non-negative). Given a probability distribution   on  , define the expected risk   to be:

 

The general goal in statistical learning is to find the function in   that minimizes the expected risk. That is, to find solutions to the following problem:[1]

 

But in practice the distribution   is unknown, and any learning task can only be based on finite samples. Thus we seek instead to find an algorithm that asymptotically minimizes the empirical risk, i.e., to find a sequence of functions   that satisfies

 

One usual algorithm to find such a sequence is through empirical risk minimization.

Learnable function class

edit

We can make the condition given in the above equation stronger by requiring that the convergence is uniform for all probability distributions. That is:

  (1)

The intuition behind the more strict requirement is as such: the rate at which sequence   converges to the minimizer of the expected risk can be very different for different  . Because in real world the true distribution   is always unknown, we would want to select a sequence that performs well under all cases.

However, by the no free lunch theorem, such a sequence that satisfies (1) does not exist if   is too complex. This means we need to be careful and not allow too "many" functions in   if we want (1) to be a meaningful requirement. Specifically, function classes that ensure the existence of a sequence   that satisfies (1) are known as learnable classes.[1]

It is worth noting that at least for supervised classification and regression problems, if a function class is learnable, then the empirical risk minimization automatically satisfies (1).[2] Thus in these settings not only do we know that the problem posed by (1) is solvable, we also immediately have an algorithm that gives the solution.

Interpretations

edit

If the true relationship between   and   is  , then by selecting the appropriate loss function,   can always be expressed as the minimizer of the expected loss across all possible functions. That is,

 

Here we let   be the collection of all possible functions mapping   onto  .   can be interpreted as the actual data generating mechanism. However, the no free lunch theorem tells us that in practice, with finite samples we cannot hope to search for the expected risk minimizer over  . Thus we often consider a subset of  ,  , to carry out searches on. By doing so, we risk that   might not be an element of  . This tradeoff can be mathematically expressed as

  (2)

In the above decomposition, part   does not depend on the data and is non-stochastic. It describes how far away our assumptions ( ) are from the truth ( ).   will be strictly greater than 0 if we make assumptions that are too strong (  too small). On the other hand, failing to put enough restrictions on   will cause it to be not learnable, and part   will not stochastically converge to 0. This is the well-known overfitting problem in statistics and machine learning literature.

Example: Tikhonov regularization

edit

A good example where learnable classes are used is the so-called Tikhonov regularization in reproducing kernel Hilbert space (RKHS). Specifically, let   be an RKHS, and   be the norm on   given by its inner product. It is shown in [3] that   is a learnable class for any finite, positive  . The empirical minimization algorithm to the dual form of this problem is

 

This was first introduced by Tikhonov[4] to solve ill-posed problems. Many statistical learning algorithms can be expressed in such a form (for example, the well-known ridge regression).

The tradeoff between   and   in (2) is geometrically more intuitive with Tikhonov regularization in RKHS. We can consider a sequence of  , which are essentially balls in   with centers at 0. As   gets larger,   gets closer to the entire space, and   is likely to become smaller. However we will also suffer smaller convergence rates in  . The way to choose an optimal   in finite sample settings is usually through cross-validation.

Relationship to empirical process theory

edit

Part   in (2) is closely linked to empirical process theory in statistics, where the empirical risk   are known as empirical processes.[5] In this field, the function class   that satisfies the stochastic convergence

  (3)

are known as uniform Glivenko–Cantelli classes. It has been shown that under certain regularity conditions, learnable classes and uniformly Glivenko-Cantelli classes are equivalent.[1] Interplay between   and   in statistics literature is often known as the bias-variance tradeoff.

However, note that in [2] the authors gave an example of stochastic convex optimization for General Setting of Learning where learnability is not equivalent with uniform convergence.

References

edit
  1. ^ a b c Vladimir N. Vapnik (17 April 2013). The Nature of Statistical Learning Theory. Springer Science & Business Media. ISBN 978-1-4757-2440-0.
  2. ^ a b "Learnability, stability and uniform convergence". The Journal of Machine Learning Research.
  3. ^ "Learnability in Hilbert spaces with reproducing kernels". Journal of Complexity.
  4. ^ Andreĭ Nikolaevich Tikhonov; Vasiliĭ I︠A︡kovlevich Arsenin (1977). Solutions of ill-posed problems. Winston. ISBN 978-0-470-99124-4.
  5. ^ A.W. van der vaart; Jon Wellner (9 March 2013). Weak Convergence and Empirical Processes: With Applications to Statistics. Springer Science & Business Media. pp. 116–. ISBN 978-1-4757-2545-2.