Rademacher complexity provides a method of quantifying a model's complexity to ensure that a training set is representative of the population. This is done by calculating the probability distribution of the training set from the sample and the potential classifiers with their related error functions.

University of Michigan - Ann Arbor

A model’s capacity is its ability to ﬁt a wide variety of functions.
The model $\hat{f}$ that we estimate by choosing a functional form and training, is just an approximation and almost never match the true unknown $f$. To have a closer estimate, we can choose more flexible functional forms with more parameters to estimate.
Machine learning algorithms will generally perform best when their capacity is appropriate for the true complexity of the task they need to perform and the amount of training data they are provided with.
Models with insuﬃcient capacity are unable to solve complex tasks. Models with high capacity can solve complex tasks, but when their capacity is higher than needed to solve the present task, they may overﬁt.

Supervised Statistical Model Flexibility (Capacity/Complexity)

Domingos, P. (2012). A few useful things to know about machine learning. Communications of the ACM, 55(10), 78-87. doi:10.1145/2347736.2347755

A few useful things to know about machine learning

Increasing the flexibility of a supervised statistical model may result in overfitting, such that the trained model $\hat{f}$ gets prone to the noise or errors in the observations (training data) rather than approximating the true $f$.
So, when choosing a functional form and training a supervised statistical model, we should always consider a trade-off between the flexibility and overfitting of $\hat{f}$.

Models that re too complex for the amount of training data available are said to **overfit** and are not likely to generalize well to new examples.

Overfitting a supervised statistical model

Typically, when training a machine learning model, we have access to a training set; we can compute some error measure on the training set, called the training error; and we reduce this training error. 

What separates machine learning from optimization is that we want the generalization error, also called the test error, to be low as well. The test error is deﬁned as the expected value of the error on a new input. Here the expectation is taken across diﬀerent possible inputs, drawn from the distribution of inputs we expect the system to encounter in practice. 

We typically estimate the test error of a machine learning model by measuring its performance on a test set of examples that were collected separately from the training set.

Training Error and Test Error

Generalizability refers to an algorithm's ability to give accurate predictions for new, previously unseen data.

Generalizability of a supervised statistical model

Models that are too simple that don't even do well on the training data, are said to **underfit** and are not likely to generalize well to new examples.

Underfitting a supervised statistical model

Measuring Model Complexity: Rademacher complexity

Bias is an error that occurs when a model is unable to accurately represent the true $f$ as a result of underlying assumptions made to simplify the model. For example, using linear regression for a relationship that is not linear in nature has a large amount of bias since no linear estimate will result in a model that accurately captures the non-linear nature of $f$. Its flexibility is limited and often underfits the data. More flexible methods result in less bias since it is able to more accurately represent the true $f$.

Bias of Supervised Models in Statistical Learning

Variance refers to the sensitivity of a model ($ \hat{f} $) to different training data sets. In other words, it is the difference in the fits of $ \hat{f} $ between different training data sets. When we use data sets to fit our statistical learning method, each one will produce a different $ \hat{f} $; we want an $ \hat{f} $ that varies very little between them. High variance means $ \hat{f} $ is often more flexible and captures the points of that particular data set well, but changing points for a different training data set will result in large changes in $ \hat{f} $ due to overfitting. Lower variance results in less flexibility, but does not change $ \hat{f} $ as much between different training data sets.

Variance of Supervised Models in Statistical Learning

In machine learning, model complexity can be analyzed through Karl Popper's scientific criterion of falsifiability. An overly complex model class that can perfectly fit any arbitrary dataset—including randomly assigned labels—acts like an unfalsifiable theory that explains every possible observation, failing to guarantee that a true pattern has been discovered. Conversely, if a model class is restrictive enough that it could not possibly fit arbitrary labels, yet it successfully fits the actual training data, we can more confidently conclude it has learned a generalizable pattern.

Falsifiability of Machine Learning Models

Determining an appropriate measure for model complexity is nuanced and varies across different classes of machine learning models. While complexity is frequently associated with the number of parameters—since models with more parameters can typically fit more arbitrarily assigned labels—this is not always true. For example, kernel methods can operate in spaces with an infinite number of parameters, yet their complexity is controlled through other mechanisms. A more useful notion of complexity often involves the range of values that parameters can take; a model whose parameters can take arbitrary values is considered more complex. Consequently, comparing complexity between substantially different model classes, such as decision trees and neural networks, can be difficult.

Notions of Model Complexity

The amount of available training data dictates the appropriate level of model complexity. For a fixed task and data distribution, model complexity should not increase more rapidly than the dataset size. With fewer training samples, a model is highly susceptible to overfitting, making simpler models difficult to beat. However, as dataset size increases, generalization error typically decreases, allowing for the successful training of more complex architectures like deep neural networks.

Learn Before

Related