Answers.Body: <h1>VC dimension</h1>
  <p>A rigorous measure of the capacity of a neural network is the <a href="https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension" rel="nofollow noreferrer"><strong>VC dimension</strong></a>, which is <em>intuitively</em> a number or <strong>bound</strong> that quantifies the difficulty of learning from data.</p>
  <p>The <strong>sample complexity</strong>, which is the number of training instances that the model (or learner) must be exposed to in order to be reasonably certain of the accurateness of the predictions made given some data, is proportional to this number.</p>
  <p>The paper <a href="http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a> (1998) by Eduardo D. Sontag provides a good introduction to the VC dimension of neural networks (even though these concepts are quite abstract and you may need to read them several times to fully grasp them). The information in this answer is highly based on that paper.</p>
  <h2>Shattering and VC dimension</h2>
  <p>In section 2, <strong>Concepts and VC Dimension</strong>, he describes the basic concepts behind the VC dimension (not only for neural networks), such as the concept of <strong>shattering</strong> (i.e. what does it mean for a set of sets to shatter another set?), which is a well-known concept in <a href="https://ai.stackexchange.com/a/17842/2444">computational learning theory</a> and is used to define the VC dimension (see definition 2), so you definitely need to get familiar with this concept to understand the VC dimension and, therefore, the capacity of a neural network (calculated with the VC dimension).</p>
  <h2>VC dimension of functions and neural networks</h2>
  <p>He then provides an equivalent definition of the VC dimension but for functions (equation 6). Given that neural networks represent functions, then we can also define the VC dimension of a neural network. A specific combination of weights of neural networks represents a specific function, for which the VC dimension can be defined. To be more precise, a parametrized function (and a neural network) can be denoted as</p>
  <p><span class="math-container">$$
  \beta : \mathbb{W} \times \mathbb{U} \rightarrow \mathbb{R}
  $$</span></p>
  <p>where <span class="math-container">$\mathbb{W} = \mathbb{R}^p$</span> and <span class="math-container">$p$</span> is the number of weights (or parameters) of the neural network, <span class="math-container">$\mathbb{U}$</span> is the input space and <span class="math-container">$\mathbb{R}$</span> the output space. So, in this case, <span class="math-container">$\beta$</span> can also represent a neural network, with a certain parameter space <span class="math-container">$\mathbb{W}$</span>, an input space <span class="math-container">$\mathbb{U}$</span> and an output space <span class="math-container">$\mathbb{R}$</span>.</p>
  <p>The vector <span class="math-container">$\mathbf{w} = (w_1, \dots, w_p) \in \mathbb{W}$</span> represents a specific combination of weights of the neural network, so it represents a specific function. The set of all functions for each choice of this weight vector can be denoted as</p>
  <p><span class="math-container">$$
  \mathcal{F}_{\beta} = \{ \beta(\mathbf{w}, \cdot) \mid \mathbf{w} \in \mathbb{W} \}
  $$</span></p>
  <p>The VC dimension (VCD) of <span class="math-container">$\beta$</span> can then be defined as</p>
  <p><span class="math-container">$$
  \text{VCD}(\beta) := \text{VCD}(\mathcal{F}_{\beta})
  $$</span></p>
  <p>Therefore, the VC dimension is a measure of the capacity of a neural network with a <strong>certain</strong> architecture. Moreover, the VC dimension is equivalently defined for a certain set of functions associated with a neural network.</p>
  <h2>How to calculate the VC dimension?</h2>
  <p>To calculate the actual VC dimension of a neural network, it takes a little bit of more creativity. Therefore, I will just report the VC dimension of some neural networks. For more details, you should fully read the cited paper (more than once) and other papers and books too (especially, the ones described in <a href="https://ai.stackexchange.com/a/17842/2444">this answer</a>, which provide an introduction to CLT concepts).</p>
  <h3>VC dimension of a perceptron</h3>
  <p>The VC dimension of a perceptron is <span class="math-container">$m + 1$</span>, where <span class="math-container">$m$</span> is the number of inputs. Given that a perceptron represents a linear and affine function, the VC dimension of the perceptron is also equal to the number of parameters. However, note that, even though the VC dimension of the perceptron is linear in the number of parameters and inputs, it doesn't mean the perceptron can learn any function. In fact, perceptrons can only represent linear functions. See section 3.1 of <a href="http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a> for more details.</p>
  <h3>VC dimension of a single hidden layer neural network</h3>
  <p>Let <span class="math-container">$n$</span> be the number of hidden units, then the VC dimension of a single hidden layer neural network is less than or equal to <span class="math-container">$n+1$</span>. See section 3.2 of <a href="http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a> for more details.</p>
  <h3>VC dimension of multi-layer neural networks with binary activations</h3>
  <p>The VC dimension of multi-layer neural networks (MLPs) with binary activations and <span class="math-container">$p$</span> weights (or parameters) is <span class="math-container">$\mathcal{O}(p \log p)$</span>. See theorem 4 (and related sections) of the paper <a href="http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a> for more details.</p>
  <h3>VC dimension of MLPs with real-valued activations</h3>
  <p>The VC dimension of MLPs with real-valued activations is no longer bounded by <span class="math-container">$\mathcal{O}(p \log p)$</span> and can be exponential in the number of parameters. See section 5.3 of <a href="http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a>.</p>
  <h3>VC dimension of MLPs with linear activations</h3>
  <p>The VC dimension of MLPs with linear activations is <span class="math-container">$\mathcal{O}(p^2)$</span>.  See theorem 5 of the paper <a href="http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a>.</p>
  <h2>Notes</h2>
  <p>The VC dimension is often expressed as a bound (e.g. with big-O notation), which may <strong>not</strong> be strict.</p>
  <p>In any case, the VC dimension is useful because it provides some guarantees. For example, if you use the VC dimension to describe an upper bound on the number of samples required to learn a certain task, then you have a precise mathematical formula that guarantees that you will not need more samples than those expressed by the bound in order to achieve a small generalization error, but, in practice, you may need fewer samples than those expressed by the bound (because these bounds may not be strict or the VC dimension may also not be strict).</p>
  <h2>Further reading</h2>
  <p>There is a more recent paper (published in 2017 in MLR) that proves new and tighter upper and lower bounds on the <strong>VC dimension of deep neural networks with the ReLU activation function</strong>: <a href="http://proceedings.mlr.press/v65/harvey17a/harvey17a.pdf" rel="nofollow noreferrer">Nearly-tight VC-dimension bounds for piecewise linear neural networks</a>. So, you probably should read this paper first.</p>
  <p>The paper <a href="https://arxiv.org/pdf/1802.04443.pdf" rel="nofollow noreferrer">On Characterizing the Capacity of Neural Networks using Algebraic Topology</a> may also be useful and interesting. See also section 6, Algebraic Techniques, of the paper I have been citing: <a href="http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a>.</p>
  <p>The capacity of a neural network is clearly related to the number of functions it can represent, so it is strictly related to the universal approximation theorems for neural networks. See <a href="https://ai.stackexchange.com/a/13319/2444">Where can I find the proof of the universal approximation theorem?</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-25T07:15:52.840Z
Answers.Text: the value of n+1 for a single hidden layer neural network holds only if input weights and biases are constant. The model then becomes an affine function of output weights which is equal to n+1 (including bias term c0) ~ VC-dim = n+1
Answers.UserDisplayName: Maharshi Roy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-06T14:08:35.860Z
Answers.LastActivityDate: 2020-11-13T21:31:40.457Z
Answers.LastEditDate: 2020-11-13T21:31:40.457Z
Answers.UserDisplayName: nbro
Answers.Body: <p>Most methods for measuring the complexity of neural networks are fairly crude. One common measure of complexity is <a href="https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension" rel="nofollow noreferrer">VC dimension</a>, a discussion which can be found <a href="https://stats.stackexchange.com/questions/25952/calculating-vc-dimension-of-a-neural-network">here</a> and <a href="https://cs.stackexchange.com/questions/75327/why-is-deep-learning-hyped-despite-bad-vc-dimension">here</a>. For example, neural networks have a <a href="https://arxiv.org/pdf/1703.02930.pdf" rel="nofollow noreferrer">VC dimension that is too large</a> to give a strong upper bound on the number of training samples needed for a model (the upper bound provided by VC analysis is much higher than what we have observed neural networks to be able to generalize from).</p>
  
  <p>Another common measure of capacity is the number of parameters. We see in the paper "<a href="https://arxiv.org/pdf/1611.03530v2.pdf" rel="nofollow noreferrer">Understanding deep learning requires rethinking generalization</a>", published at ICLR with over 1400+ citations, that networks with more parameters than data often have the capacity to memorize the data. The paper provides compelling evidence that traditional approaches to generalization provided by statistical learning theory (VC dimension, Rademacher complexity) are unable to fully explain the apparent capacity of neural networks. In general, neural networks seem to have a large capacity, given the apparent good performance on certain tasks.</p>
  
  <p>Beyond these ideas, the universal approximation theorem tells us that the set of neural networks can approximate any continuous function arbitrarily well, which strongly suggests that any neural network has a large capacity.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-06T07:51:57.057Z
Answers.LastActivityDate: 2020-02-11T05:45:22.643Z
Answers.LastEditDate: 2020-02-11T05:45:22.643Z
Answers.UserDisplayName: Anon
Body: <p>Is it possible to estimate the capacity of a neural network model? If so, what are the techniques involved?</p>
  
Tags: <neural-networks><deep-learning><computational-learning-theory><vc-dimension><capacity>
Title: How to estimate the capacity of a neural network?
UserDisplayName: jaeger6
ThreadText: # How to estimate the capacity of a neural network?
  
  (Asked by: username_0 on 2020-02-06)
  
  Is it possible to estimate the capacity of a neural network model? If so, what are the techniques involved?
  
  **Tags:** neural-networks, deep-learning, computational-learning-theory, vc-dimension, capacity
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-02-06. Score: 7
  
  # VC dimension
  
  A rigorous measure of the capacity of a neural network is the [**VC dimension**](https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension), which is *intuitively* a number or **bound** that quantifies the difficulty of learning from data.
  
  The **sample complexity**, which is the number of training instances that the model (or learner) must be exposed to in order to be reasonably certain of the accurateness of the predictions made given some data, is proportional to this number.
  
  The paper [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf) (1998) by Eduardo D. Sontag provides a good introduction to the VC dimension of neural networks (even though these concepts are quite abstract and you may need to read them several times to fully grasp them). The information in this answer is highly based on that paper.
  
  ## Shattering and VC dimension
  
  In section 2, **Concepts and VC Dimension**, he describes the basic concepts behind the VC dimension (not only for neural networks), such as the concept of **shattering** (i.e. what does it mean for a set of sets to shatter another set?), which is a well-known concept in [computational learning theory](https://ai.stackexchange.com/a/17842/2444) and is used to define the VC dimension (see definition 2), so you definitely need to get familiar with this concept to understand the VC dimension and, therefore, the capacity of a neural network (calculated with the VC dimension).
  
  ## VC dimension of functions and neural networks
  
  He then provides an equivalent definition of the VC dimension but for functions (equation 6). Given that neural networks represent functions, then we can also define the VC dimension of a neural network. A specific combination of weights of neural networks represents a specific function, for which the VC dimension can be defined. To be more precise, a parametrized function (and a neural network) can be denoted as
  
  $$
  \beta : \mathbb{W} \times \mathbb{U} \rightarrow \mathbb{R}
  $$
  
  where $\mathbb{W} = \mathbb{R}^p$ and $p$ is the number of weights (or parameters) of the neural network, $\mathbb{U}$ is the input space and $\mathbb{R}$ the output space. So, in this case, $\beta$ can also represent a neural network, with a certain parameter space $\mathbb{W}$, an input space $\mathbb{U}$ and an output space $\mathbb{R}$.
  
  The vector $\mathbf{w} = (w\_1, \dots, w\_p) \in \mathbb{W}$ represents a specific combination of weights of the neural network, so it represents a specific function. The set of all functions for each choice of this weight vector can be denoted as
  
  $$
  \mathcal{F}\_{\beta} = \{ \beta(\mathbf{w}, \cdot) \mid \mathbf{w} \in \mathbb{W} \}
  $$
  
  The VC dimension (VCD) of $\beta$ can then be defined as
  
  $$
  \text{VCD}(\beta) := \text{VCD}(\mathcal{F}\_{\beta})
  $$
  
  Therefore, the VC dimension is a measure of the capacity of a neural network with a **certain** architecture. Moreover, the VC dimension is equivalently defined for a certain set of functions associated with a neural network.
  
  ## How to calculate the VC dimension?
  
  To calculate the actual VC dimension of a neural network, it takes a little bit of more creativity. Therefore, I will just report the VC dimension of some neural networks. For more details, you should fully read the cited paper (more than once) and other papers and books too (especially, the ones described in [this answer](https://ai.stackexchange.com/a/17842/2444), which provide an introduction to CLT concepts).
  
  ### VC dimension of a perceptron
  
  The VC dimension of a perceptron is $m + 1$, where $m$ is the number of inputs. Given that a perceptron represents a linear and affine function, the VC dimension of the perceptron is also equal to the number of parameters. However, note that, even though the VC dimension of the perceptron is linear in the number of parameters and inputs, it doesn't mean the perceptron can learn any function. In fact, perceptrons can only represent linear functions. See section 3.1 of [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf) for more details.
  
  ### VC dimension of a single hidden layer neural network
  
  Let $n$ be the number of hidden units, then the VC dimension of a single hidden layer neural network is less than or equal to $n+1$. See section 3.2 of [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf) for more details.
  
  ### VC dimension of multi-layer neural networks with binary activations
  
  The VC dimension of multi-layer neural networks (MLPs) with binary activations and $p$ weights (or parameters) is $\mathcal{O}(p \log p)$. See theorem 4 (and related sections) of the paper [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf) for more details.
  
  ### VC dimension of MLPs with real-valued activations
  
  The VC dimension of MLPs with real-valued activations is no longer bounded by $\mathcal{O}(p \log p)$ and can be exponential in the number of parameters. See section 5.3 of [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf).
  
  ### VC dimension of MLPs with linear activations
  
  The VC dimension of MLPs with linear activations is $\mathcal{O}(p^2)$. See theorem 5 of the paper [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf).
  
  ## Notes
  
  The VC dimension is often expressed as a bound (e.g. with big-O notation), which may **not** be strict.
  
  In any case, the VC dimension is useful because it provides some guarantees. For example, if you use the VC dimension to describe an upper bound on the number of samples required to learn a certain task, then you have a precise mathematical formula that guarantees that you will not need more samples than those expressed by the bound in order to achieve a small generalization error, but, in practice, you may need fewer samples than those expressed by the bound (because these bounds may not be strict or the VC dimension may also not be strict).
  
  ## Further reading
  
  There is a more recent paper (published in 2017 in MLR) that proves new and tighter upper and lower bounds on the **VC dimension of deep neural networks with the ReLU activation function**: [Nearly-tight VC-dimension bounds for piecewise linear neural networks](http://proceedings.mlr.press/v65/harvey17a/harvey17a.pdf). So, you probably should read this paper first.
  
  The paper [On Characterizing the Capacity of Neural Networks using Algebraic Topology](https://arxiv.org/pdf/1802.04443.pdf) may also be useful and interesting. See also section 6, Algebraic Techniques, of the paper I have been citing: [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf).
  
  The capacity of a neural network is clearly related to the number of functions it can represent, so it is strictly related to the universal approximation theorems for neural networks. See [Where can I find the proof of the universal approximation theorem?](https://ai.stackexchange.com/a/13319/2444).
  
  > **Comments:**
  > **username_2**: the value of n+1 for a single hidden layer neural network holds only if input weights and biases are constant. The model then becomes an affine function of output weights which is equal to n+1 (including bias term c0) ~ VC-dim = n+1  
  
  ---
  
  ### Answer by username_3 on 2020-02-06. Score: 0
  
  Most methods for measuring the complexity of neural networks are fairly crude. One common measure of complexity is [VC dimension](https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension), a discussion which can be found [here](https://stats.stackexchange.com/questions/25952/calculating-vc-dimension-of-a-neural-network) and [here](https://cs.stackexchange.com/questions/75327/why-is-deep-learning-hyped-despite-bad-vc-dimension). For example, neural networks have a [VC dimension that is too large](https://arxiv.org/pdf/1703.02930.pdf) to give a strong upper bound on the number of training samples needed for a model (the upper bound provided by VC analysis is much higher than what we have observed neural networks to be able to generalize from).
  
  Another common measure of capacity is the number of parameters. We see in the paper "[Understanding deep learning requires rethinking generalization](https://arxiv.org/pdf/1611.03530v2.pdf)", published at ICLR with over 1400+ citations, that networks with more parameters than data often have the capacity to memorize the data. The paper provides compelling evidence that traditional approaches to generalization provided by statistical learning theory (VC dimension, Rademacher complexity) are unable to fully explain the apparent capacity of neural networks. In general, neural networks seem to have a large capacity, given the apparent good performance on certain tasks.
  
  Beyond these ideas, the universal approximation theorem tells us that the set of neural networks can approximate any continuous function arbitrarily well, which strongly suggests that any neural network has a large capacity.
  
  
  ---
  
  