Answers.Body: <p>In computational learning theory, the <strong>VC dimension</strong> is a formal measure of the capacity of a model. The VC dimension is defined in terms of the concept of <strong>shattering</strong>, so have a look at the <a href="https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension#VC_dimension_of_a_set-family" rel="nofollow noreferrer">related Wikipedia article</a>, which briefly describes the fundamental concept of shattering. See also <a href="https://ai.stackexchange.com/a/17881/2444">my answer</a> to the question <a href="https://ai.stackexchange.com/q/17870/2444">How to estimate the capacity of a neural network?</a> for more details.</p>
  
  <p>The paper <a href="https://www.sciencedirect.com/science/article/pii/S0166218X98000146" rel="nofollow noreferrer">Vapnik-Chervonenkis dimension of recurrent neural networks</a> (1998), by Pascal Koirana and Eduardo D. Sontag, partially (because they do not take into account more advanced recurrent neural network architectures, such as the LSTM) answers your question. </p>
  
  <p>In the paper, the authors show and prove different theorems that state the VC dimension of (standard) recurrent neural networks (RNNs), with different activation functions, such as non-linear polynomials, piecewise polynomials and the sigmoid function.</p>
  
  <p>For example, <strong>Theorem 5</strong> (page 70) states</p>
  
  <blockquote>
    <p>Let <span class="math-container">$\sigma$</span> be an arbitrary sigmoid. The VC dimension of recurrent architectures with activation <span class="math-container">$\sigma$</span>, with <span class="math-container">$w$</span> weights and receiving inputs of length <span class="math-container">$k$</span>, is <span class="math-container">$\Omega(wk)$</span>. </p>
  </blockquote>
  
  <p>The proof of this theorem is given on page 75. </p>
  
  <p>What does this theorem intuitively tell you? If you are familiar with <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow noreferrer">big-O</a> notation, then you are also familiar with <a href="https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations" rel="nofollow noreferrer">the notation <span class="math-container">$\Omega(wk)$</span></a>, which means that <span class="math-container">$wk$</span> is, <a href="https://en.wikipedia.org/wiki/Asymptotic_analysis" rel="nofollow noreferrer"><strong>asymptotically</strong></a>, a lower bound on the capacity of the RNN. In other words, asymptotically, the capacity of an RNN with <span class="math-container">$w$</span> weights receiving inputs of length <span class="math-container">$k$</span> is at least <span class="math-container">$wk$</span>. How does the capacity of the RNN increase as a function of <span class="math-container">$w$</span>?</p>
  
  <p>Of course, this is a specific result, which only holds for RNNs with the sigmoid activation function. However, this at least gives you an idea of the potential capacity of an RNN. This theorem will hopefully stimulate your appetite to know more computational learning theory!</p>
  
  <p>The paper <a href="https://openreview.net/forum?id=Skf-oo0qt7" rel="nofollow noreferrer">On Generalization Bounds of a Family of Recurrent Neural Networks</a> may also be useful, although it has been rejected for ICLR 2019.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-12T02:15:04.893Z
Answers.Text: Hmm, so it scales with number of weights? Therefore, can we say VC-dim (RNN with k layers) = k * VC-dim (RNN with 1 layer)?
Answers.UserDisplayName: information_interchange
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-12T02:39:01.993Z
Answers.Text: Yes, it scales with weights and length of the input. But, again, note that $wk$ is a lower bound, so the capacity of the RNN may actually be higher (but only asymptotically).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-13T01:23:00.593Z
Answers.LastActivityDate: 2020-03-13T01:34:40.127Z
Answers.LastEditDate: 2020-03-13T01:34:40.127Z
Answers.UserDisplayName: nbro
Body: <p>I playing around <a href="https://www.tensorflow.org/tutorials/structured_data/time_series" rel="nofollow noreferrer">sequence modeling to forecast the weather</a> using LSTM. </p>
  
  <p>How does the number of layers or units in each layer exactly affect the model complexity (in an LSTM)? For example, if I increase the number of layers and decrease the number of units, how will the model complexity be affected? </p>
  
  <p>I am not interested in rules of thumb for choosing the number of layers or units. I am interested in theoretical guarantees or bounds.</p>
  
Tags: <long-short-term-memory><computational-learning-theory><sequence-modeling><vc-dimension>
Title: How does the number of stacked LSTM layers or units in each layer affect the model complexity?
UserDisplayName: Manojk07
ThreadText: # How does the number of stacked LSTM layers or units in each layer affect the model complexity?
  
  (Asked by: username_0 on 2020-03-11)
  
  I playing around [sequence modeling to forecast the weather](https://www.tensorflow.org/tutorials/structured_data/time_series) using LSTM.
  
  How does the number of layers or units in each layer exactly affect the model complexity (in an LSTM)? For example, if I increase the number of layers and decrease the number of units, how will the model complexity be affected?
  
  I am not interested in rules of thumb for choosing the number of layers or units. I am interested in theoretical guarantees or bounds.
  
  **Tags:** long-short-term-memory, computational-learning-theory, sequence-modeling, vc-dimension
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-03-13. Score: 1
  
  In computational learning theory, the **VC dimension** is a formal measure of the capacity of a model. The VC dimension is defined in terms of the concept of **shattering**, so have a look at the [related Wikipedia article](https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension#VC_dimension_of_a_set-family), which briefly describes the fundamental concept of shattering. See also [my answer](https://ai.stackexchange.com/a/17881/2444) to the question [How to estimate the capacity of a neural network?](https://ai.stackexchange.com/q/17870/2444) for more details.
  
  The paper [Vapnik-Chervonenkis dimension of recurrent neural networks](https://www.sciencedirect.com/science/article/pii/S0166218X98000146) (1998), by Pascal Koirana and Eduardo D. Sontag, partially (because they do not take into account more advanced recurrent neural network architectures, such as the LSTM) answers your question.
  
  In the paper, the authors show and prove different theorems that state the VC dimension of (standard) recurrent neural networks (RNNs), with different activation functions, such as non-linear polynomials, piecewise polynomials and the sigmoid function.
  
  For example, **Theorem 5** (page 70) states
  
  > Let $\sigma$ be an arbitrary sigmoid. The VC dimension of recurrent architectures with activation $\sigma$, with $w$ weights and receiving inputs of length $k$, is $\Omega(wk)$.
  
  The proof of this theorem is given on page 75.
  
  What does this theorem intuitively tell you? If you are familiar with [big-O](https://en.wikipedia.org/wiki/Big_O_notation) notation, then you are also familiar with [the notation $\Omega(wk)$](https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations), which means that $wk$ is, [**asymptotically**](https://en.wikipedia.org/wiki/Asymptotic_analysis), a lower bound on the capacity of the RNN. In other words, asymptotically, the capacity of an RNN with $w$ weights receiving inputs of length $k$ is at least $wk$. How does the capacity of the RNN increase as a function of $w$?
  
  Of course, this is a specific result, which only holds for RNNs with the sigmoid activation function. However, this at least gives you an idea of the potential capacity of an RNN. This theorem will hopefully stimulate your appetite to know more computational learning theory!
  
  The paper [On Generalization Bounds of a Family of Recurrent Neural Networks](https://openreview.net/forum?id=Skf-oo0qt7) may also be useful, although it has been rejected for ICLR 2019.
  
  > **Comments:**
  > **username_2**: Hmm, so it scales with number of weights? Therefore, can we say VC-dim (RNN with k layers) = k * VC-dim (RNN with 1 layer)?  
  > **username_1**: Yes, it scales with weights and length of the input. But, again, note that $wk$ is a lower bound, so the capacity of the RNN may actually be higher (but only asymptotically).  
  
  ---
  
  