Answers.Body: <p>Learning algorithms (some others too, like search) aim at generating functions that get as close as possible to the &quot;shape&quot; of the training data (so we can then feed values to the generated functions and get outputs like, say, a prediction).</p>
  <p>In 2D, the &quot;shape&quot; may be easy to visualize. If the data in 2D seems to line up, learning algorithms generating linear/affine functions (e.g. <code>y = ax + b</code>), should fit fairly well. Their representational capacity extends to lines. If the data seems to form a parabola, a representational capacity bound to lines will do poorly. We then need more &quot;capable&quot; representations, which can cope with the quadratic terms.</p>
  <p>So this should be what the &quot;family of functions&quot; Goodfellow's book refers to. The &quot;training objective&quot; should not be in the definition (to me), as a line fitting solution is unable to represent, say, a parabola, whatever the training objective is. However the book definition may mean a line can be fit to a parabola, strictly speaking, although it will do so very poorly.</p>
  <p>The hypothesis space resembles the definition, perhaps (I have not checked it), but what matters is the &quot;mindset&quot;. I would draw a parallel with prior and posterior distributions in Statistics, where we usually make some hypothesis on the shape of the distribution.</p>
  <p>Concrete examples like linear regressions generate linear functions, as hinted by their names. Decision trees generate sets of linear functions, thus more complex and &quot;capable&quot;. SVM generates functions depending on its kernel. The <a href="https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html" rel="nofollow noreferrer">RBF kernel</a>, for example, allows generating functions that can map quite complex, non-linear data &quot;shapes&quot;. And arbitrary neural networks can map &quot;arbitrary&quot; data &quot;shape&quot; (easier written than actually done).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-11T00:56:38.350Z
Answers.Text: Could you also clarify how this differs from the hypothesis space of the learning algorithm?
Answers.UserDisplayName: curiousgeorge
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-11T00:51:13.947Z
Answers.LastActivityDate: 2020-08-11T01:05:34.680Z
Answers.LastEditDate: 2020-08-11T01:05:34.680Z
Answers.UserDisplayName: Eric Platon
Body: <p>The definition I see for representational capacity is &quot;the family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective.&quot; (Goodfellow's Deep learning book).</p>
  <p>However, to me this seems to be the same as the definition of the hypothesis space. Is the key difference the &quot;in order to reduce a training objective&quot; in that some functions may not be chosen in reducing a training objective? Or are these identical definitions.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-12T23:17:55.963Z
Comments.Text: I don't think there's any difference between representational capacity and hypothesis space.
Comments.UserDisplayName: nbro
Tags: <deep-learning><terminology><computational-learning-theory>
Title: What is the representational capacity of a learning algorithm?
UserDisplayName: curiousgeorge
ThreadText: # What is the representational capacity of a learning algorithm?
  
  (Asked by: username_0 on 2020-08-10)
  
  The definition I see for representational capacity is "the family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective." (Goodfellow's Deep learning book).
  
  However, to me this seems to be the same as the definition of the hypothesis space. Is the key difference the "in order to reduce a training objective" in that some functions may not be chosen in reducing a training objective? Or are these identical definitions.
  
  **Tags:** deep-learning, terminology, computational-learning-theory
  
  > **Comments:**
  > **username_1**: I don't think there's any difference between representational capacity and hypothesis space.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-08-11. Score: 0
  
  Learning algorithms (some others too, like search) aim at generating functions that get as close as possible to the "shape" of the training data (so we can then feed values to the generated functions and get outputs like, say, a prediction).
  
  In 2D, the "shape" may be easy to visualize. If the data in 2D seems to line up, learning algorithms generating linear/affine functions (e.g. `y = ax + b`), should fit fairly well. Their representational capacity extends to lines. If the data seems to form a parabola, a representational capacity bound to lines will do poorly. We then need more "capable" representations, which can cope with the quadratic terms.
  
  So this should be what the "family of functions" Goodfellow's book refers to. The "training objective" should not be in the definition (to me), as a line fitting solution is unable to represent, say, a parabola, whatever the training objective is. However the book definition may mean a line can be fit to a parabola, strictly speaking, although it will do so very poorly.
  
  The hypothesis space resembles the definition, perhaps (I have not checked it), but what matters is the "mindset". I would draw a parallel with prior and posterior distributions in Statistics, where we usually make some hypothesis on the shape of the distribution.
  
  Concrete examples like linear regressions generate linear functions, as hinted by their names. Decision trees generate sets of linear functions, thus more complex and "capable". SVM generates functions depending on its kernel. The [RBF kernel](https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html), for example, allows generating functions that can map quite complex, non-linear data "shapes". And arbitrary neural networks can map "arbitrary" data "shape" (easier written than actually done).
  
  > **Comments:**
  > **username_0**: Could you also clarify how this differs from the hypothesis space of the learning algorithm?  
  
  ---
  
  