Answers.Body: <p>In general if the function behaves differently in different regions of the input space of high dimensions, it becomes hopeless to describe it with limited data. The number of examples needed to capture the variations increases exponentially with the number of dimensions, making it difficult to cover the function’s behavior adequately with a finite set of training examples.</p>
  <p>However, if dependencies between regions are introduced through assumptions about the data generating process as <em>inductive bias</em> then it becomes hopeful. For example, for a 256x256 image with 65,536 dimensions, to capture all variations in such high dimensions, a traditional method would require an impractically large number of examples. CNNs introduce dependencies between regions via additional assumptions about their underlying data generating distribution to learning convolutional kernel filters that detect edges, shapes, and textures in a hierarchical fashion, and these filters are shared across the image allowing the network to generalize from a much smaller number of examples. Similar additional dependency assumptions are used in other deep learning models such as RNNs, transformers, diffusion models, etc.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-01T08:45:09.083Z
Answers.LastActivityDate: 2024-07-01T08:45:09.083Z
Answers.UserDisplayName: cinch
Body: <p>I am reading the section 5.11.2 from the <a href="https://www.deeplearningbook.org/" rel="nofollow noreferrer">Deep Learning book</a> where the authors explain Deep Learning can deal with high dimensionality data in contrast to classical machine learning algorithms. However, I can't follow the bold part of the excerpt.</p>
  <p>Can someone elaborate what the authors mean?</p>
  <blockquote>
  <p>The smoothness assumption and the associated non-parametric learning
  algo- rithms work extremely well so long as there are enough examples
  for the learning algorithm to observe high points on most peaks and
  low points on most valleys of the true underlying function to be
  learned. This is generally true when the function to be learned is
  smooth enough and varies in few enough dimensions. In high dimensions,
  even a very smooth function can change smoothly but in a diﬀerent way
  along each dimension. If the function additionally behaves diﬀerently
  in diﬀerent regions, it can become extremely complicated to describe
  with a set of training examples. If the function is complicated (we
  want to distinguish a huge number of regions compared to the number of
  examples), is there any hope to generalize well?</p>
  <p>The answer to both of
  these questions—whether it is possible to represent a complicated
  function eﬃciently, and whether it is possible for the estimated
  function to generalize well to new inputs—is yes. <strong>The key insight is
  that a very large number of regions, e.g., <span class="math-container">$\mathcal{O}(2^k)$</span>, can be deﬁned with
  <span class="math-container">$\mathcal{O}(k)$</span> examples, so long as we introduce some dependencies between the
  regions via additional assumptions about the underlying data
  generating distribution.</strong></p>
  </blockquote>
  
Tags: <deep-learning><books>
Title: Clarification on why Deep Learning works from Goodfellow's book
UserDisplayName: Antonios Sarikas
ThreadText: # Clarification on why Deep Learning works from Goodfellow's book
  
  (Asked by: username_0 on 2024-06-30)
  
  I am reading the section 5.11.2 from the [Deep Learning book](https://www.deeplearningbook.org/) where the authors explain Deep Learning can deal with high dimensionality data in contrast to classical machine learning algorithms. However, I can't follow the bold part of the excerpt.
  
  Can someone elaborate what the authors mean?
  
  > The smoothness assumption and the associated non-parametric learning
  > algo- rithms work extremely well so long as there are enough examples
  > for the learning algorithm to observe high points on most peaks and
  > low points on most valleys of the true underlying function to be
  > learned. This is generally true when the function to be learned is
  > smooth enough and varies in few enough dimensions. In high dimensions,
  > even a very smooth function can change smoothly but in a diﬀerent way
  > along each dimension. If the function additionally behaves diﬀerently
  > in diﬀerent regions, it can become extremely complicated to describe
  > with a set of training examples. If the function is complicated (we
  > want to distinguish a huge number of regions compared to the number of
  > examples), is there any hope to generalize well?
  >
  > The answer to both of
  > these questions—whether it is possible to represent a complicated
  > function eﬃciently, and whether it is possible for the estimated
  > function to generalize well to new inputs—is yes. **The key insight is
  > that a very large number of regions, e.g., $\mathcal{O}(2^k)$, can be deﬁned with
  > $\mathcal{O}(k)$ examples, so long as we introduce some dependencies between the
  > regions via additional assumptions about the underlying data
  > generating distribution.**
  
  **Tags:** deep-learning, books
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-07-01. Score: 2
  
  In general if the function behaves differently in different regions of the input space of high dimensions, it becomes hopeless to describe it with limited data. The number of examples needed to capture the variations increases exponentially with the number of dimensions, making it difficult to cover the function’s behavior adequately with a finite set of training examples.
  
  However, if dependencies between regions are introduced through assumptions about the data generating process as *inductive bias* then it becomes hopeful. For example, for a 256x256 image with 65,536 dimensions, to capture all variations in such high dimensions, a traditional method would require an impractically large number of examples. CNNs introduce dependencies between regions via additional assumptions about their underlying data generating distribution to learning convolutional kernel filters that detect edges, shapes, and textures in a hierarchical fashion, and these filters are shared across the image allowing the network to generalize from a much smaller number of examples. Similar additional dependency assumptions are used in other deep learning models such as RNNs, transformers, diffusion models, etc.
  
  
  ---
  
  