Draft:MEC

• Comment: Most citations predate the first apparent use of the term. Largely referenced. Apparent significant COI. Stuartyeates (talk) 20:37, 21 January 2024 (UTC)

---

Memory-equivalent Capacity (MEC) is a measure of a model's intellectual capacity, derived from the number of functions a machine learning model can represent (memorize). It provides an upper bound on the intellectual capacity needed to solve a task, such as memorizing a training set or a game tree. The measure uses the unit bits. MEC is usually defined through the number of parameters used in a model as well its topology.

Definition

A model is said to have an MEC of $n$ bits, when the model is able to represent all $2^{n}$ binary labeling functions of $n$ points. MEC can be extended to $n$-ary classification problems and regression tasks, providing a unified capacity view on all models..

Relationship to VC Dimension

MEC and VC Dimension are directly connected but not equivalent. If a model can represent all $2^{n}$ binary labeling functions of $n$ arbitrarily-distributed points, its VC dimension is $D_{VC}=n$. However, the VC-Dimension can be larger than the MEC for a concrete set of points if the model is able to generalize. For example, VC Dimension can be infinite. MEC requires all possible functions of $n$ points to be representable. This allows to assign MEC the unit of bits. Since every model has functions that it cannot generalize (see Lossless compression, No Free Lunch Theorem, Pigeonhole Principle Principle, and others), MEC is always finite.

Relationship to Information Capacity

MEC is not equivalent to information capacity from information theory, which depends on the dimensionality of the data and the type of separation function used. As a consequence, information capacity can only be measured approaching infinity. For example, the information capacity of a linear classifier model is 2 bits per parameter for binary classification, as the number of parameters approaches infinity. The MEC of a linear separator is 1 bit per parameter, no matter the number of parameters or the dimensionality of the input

Applications

MEC can be used to determine the maximum size of a machine learner before overfitting becomes a risk. For example, if the MEC is larger than the number of instances in a balanced-binary binary classification problem, the machine learner is too big and may memorize every training-set instance directly (that is, overfit).

MEC also helps to understand the upper bound of the intellectual capacity needed to solve a task. For example, a binary decision tree with 19 levels can perfectly play Tic-Tac-Toe, and the MEC for chess is approximately 400 bits. That is, one instance of a perfect game can be represented in 400 bits. These examples demonstrate how MEC can be used to quantify the upper-limit size required for a machine learners for specific tasks based on their difficulty: So the MEC for training a chess model should ideally be much smaller than 400 times the number of games in the training set to guarantee generalization to unseen games. A model could still generalize with a larger MEC but there is no guarantee. Most importantly, ignoring MEC, it is not measurable how well a model generalizes, it can only be tested anecdotally using validations samples from a test set. This leaves models vulnerable to adversarial examples.

The use of the unit bits allows the use of MEC to compare the complexity of machine learning models against each other, independent of task. MEC also allows for optimizing models for deployment in environments with limited memory resources. Last but not least, it serves as an educational tool in understanding machine learning model limits and capabilities.

Challenges

Exact capacity calculations on machine learning models can be complex, particularly due to the stochastic nature of many training algorithms (such as stochastic gradient descent or gradient boosting).

To calculate the VC Dimension, one has to know the structure of the data which is usually modeled as a function (see for example, ). In other words, one has to have a model of the data to calculate the VC dimension. Since the practical purpose of a capacity measurement is to estimate the complexity of the problem before creating a model, this needs to be considered a catch 22. Calculating the exact information capacity requirement of a model can be challenging as the information capacity is a function of the intrinsic dimensionality of the data. Algorithms for this are known, for example total correlation, but they usually take exponential time. Furthermore, models below information capacity can still overfit as information capacity is usually larger than MEC.

The calculation of MEC, at least as an upper bound, is more practical than the calculation of VC Dimension or information capacity. However, while an upper-bound MEC for neural networks and Hopfield Networks is known, MEC calculations for other algorithms, such as XGBoost, Gaussian Mixture Models, RBF-kernel Support Vector Machines, or recursive models are yet to be found. Similarly, since the intrinsic dimensionality of data is not known a-priori, estimating the MEC requirement for a given training set can only be done as an upper-bound. Note that memory capacity requirements are usually understood as upper bounds.

See Also

• Intelligence
• Artificial Intelligence
• Machine Learning
• Information Theory
• Computational Learning Theory