Answers.Body: <p>Consider a target function <span class="math-container">$f: x \mapsto f(x)$</span>.</p>
  <p>A hypothesis refers to an approximation of <span class="math-container">$f$</span>. A <strong>hypothesis space</strong> refers to the set of possible approximations that an algorithm can create for <span class="math-container">$f$</span>. The hypothesis space consists of the set of functions the model is limited to learn. For instance, linear regression can be limited to linear functions as its hypothesis space, or it can be expanded to learn polynomials.</p>
  <p>The <strong>representational capacity</strong> of a model determines the flexibility of it, its ability to fit a variety of functions (i.e. which functions the model is able to learn), at the same. It specifies the family of functions the learning algorithm can choose from.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-23T08:43:48.130Z
Answers.Text: Does it mean that the set of functions described by the representational capacity is strictly included in the hypothesis space ? By definition, is it possible to have functions in the hypothesis space NOT described in the representational capacity ?
Answers.UserDisplayName: Qwarzix
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-09T13:09:53.087Z
Answers.Text: It's still pretty confusing to me. Most sources say that a "model" is an instance (after execution/training on data) of a "learning algorithm". How, then, can a model specify the family of functions the learning algorithm can choose from? It doesn't make sense to me. The authors of the book should've explained these concepts in more depth.
Answers.UserDisplayName: Talendar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-23T07:32:50.863Z
Answers.LastActivityDate: 2020-08-12T23:22:55.973Z
Answers.LastEditDate: 2020-08-12T23:22:55.973Z
Answers.UserDisplayName: Saurav Joshi
Answers.Body: <p>A <strong>hypothesis space/class</strong> is the <strong>set</strong> of functions that the learning algorithm considers when picking one function to minimize some risk/loss functional.</p>
  <p>The <strong>capacity</strong> of a hypothesis space is a <strong>number</strong> or <strong>bound</strong> that quantifies the size (or richness) of the hypothesis space, i.e. the number (and type) of functions that can be represented by the hypothesis space. So a hypothesis space <strong>has</strong> a capacity. The two most famous measures of capacity are VC dimension and Rademacher complexity.</p>
  <p>In other words, the hypothesis class is the <em>object</em> and the capacity is a <em>property</em> (that can be measured or quantified) of this object, but there is not a big difference between hypothesis class and its capacity, in the sense that a hypothesis class naturally defines a capacity, but two (different) hypothesis classes could have the same capacity.</p>
  <p>Note that <em>representational capacity</em> (not <em>capacity</em>, which is common!) is not a standard term in computational learning theory, while <em>hypothesis space/class</em> is commonly used. For example, <a href="https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf" rel="nofollow noreferrer">this famous book</a> on machine learning and learning theory uses the term <em>hypothesis class</em> in many places, but it never uses the term <em>representational capacity</em>.</p>
  <p>Your book's definition of <em>representational capacity</em> is <em>bad</em>, in my opinion, if <em>representational capacity</em> is supposed to be a synonym for <em>capacity</em>, given that that definition also coincides with the definition of hypothesis class, so your confusion is understandable.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-09T13:18:22.030Z
Answers.Text: I agree with you. The authors of the book should've explained these concepts in more depth. Most sources say that a "model" is an instance (after execution/training on data) of a "learning algorithm". How, then, can a model specify the family of functions the learning algorithm can choose from? Also, as you pointed out, the definition of the terms "hypothesis space" and "representational capacity" given by the authors are practically the same, although they use the terms as if they represent different concepts.
Answers.UserDisplayName: Talendar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-12T23:20:29.090Z
Answers.LastActivityDate: 2020-08-14T11:34:39.377Z
Answers.LastEditDate: 2020-08-14T11:34:39.377Z
Answers.UserDisplayName: nbro
Body: <p>I am reading <a href="http://www.deeplearningbook.org" rel="nofollow noreferrer">Goodfellow et al Deeplearning Book</a>. I found it difficult to understand the difference between the definition of the hypothesis space and representation capacity of a model. </p>
  
  <p>In <a href="http://www.deeplearningbook.org/contents/ml.html" rel="nofollow noreferrer">Chapter 5</a>, it is written about hypothesis space:</p>
  
  <blockquote>
    <p>One way to control the capacity of a learning algorithm is by choosing its hypothesis space, the set of functions that the learning algorithm is allowed to select as being the solution.</p>
  </blockquote>
  
  <p>And about representational capacity:</p>
  
  <blockquote>
    <p>The model speciﬁes which family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective. This is called the representational capacity of the model.</p>
  </blockquote>
  
  <p>If we take the linear regression model as an example and allow our output <span class="math-container">$y$</span> to takes polynomial inputs, I understand the hypothesis space as the ensemble of quadratic functions taking input <span class="math-container">$x$</span>, i.e <span class="math-container">$y = a_0 + a_1x + a_2x^2$</span>.</p>
  
  <p>How is it different from the definition of the representational capacity, where parameters are <span class="math-container">$a_0$</span>, <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span>?</p>
  
Tags: <machine-learning><terminology><computational-learning-theory><hypothesis-class><capacity>
Title: What is the difference between hypothesis space and representational capacity?
UserDisplayName: Qwarzix
ThreadText: # What is the difference between hypothesis space and representational capacity?
  
  (Asked by: username_0 on 2018-08-23)
  
  I am reading [Goodfellow et al Deeplearning Book](http://www.deeplearningbook.org). I found it difficult to understand the difference between the definition of the hypothesis space and representation capacity of a model.
  
  In [Chapter 5](http://www.deeplearningbook.org/contents/ml.html), it is written about hypothesis space:
  
  > One way to control the capacity of a learning algorithm is by choosing its hypothesis space, the set of functions that the learning algorithm is allowed to select as being the solution.
  
  And about representational capacity:
  
  > The model speciﬁes which family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective. This is called the representational capacity of the model.
  
  If we take the linear regression model as an example and allow our output $y$ to takes polynomial inputs, I understand the hypothesis space as the ensemble of quadratic functions taking input $x$, i.e $y = a\_0 + a\_1x + a\_2x^2$.
  
  How is it different from the definition of the representational capacity, where parameters are $a\_0$, $a\_1$ and $a\_2$?
  
  **Tags:** machine-learning, terminology, computational-learning-theory, hypothesis-class, capacity
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2018-08-23. Score: 1 | Accepted answer
  
  Consider a target function $f: x \mapsto f(x)$.
  
  A hypothesis refers to an approximation of $f$. A **hypothesis space** refers to the set of possible approximations that an algorithm can create for $f$. The hypothesis space consists of the set of functions the model is limited to learn. For instance, linear regression can be limited to linear functions as its hypothesis space, or it can be expanded to learn polynomials.
  
  The **representational capacity** of a model determines the flexibility of it, its ability to fit a variety of functions (i.e. which functions the model is able to learn), at the same. It specifies the family of functions the learning algorithm can choose from.
  
  > **Comments:**
  > **username_0**: Does it mean that the set of functions described by the representational capacity is strictly included in the hypothesis space ? By definition, is it possible to have functions in the hypothesis space NOT described in the representational capacity ?  
  > **username_2**: It's still pretty confusing to me. Most sources say that a "model" is an instance (after execution/training on data) of a "learning algorithm". How, then, can a model specify the family of functions the learning algorithm can choose from? It doesn't make sense to me. The authors of the book should've explained these concepts in more depth.  
  
  ---
  
  ### Answer by username_3 on 2020-08-12. Score: 2
  
  A **hypothesis space/class** is the **set** of functions that the learning algorithm considers when picking one function to minimize some risk/loss functional.
  
  The **capacity** of a hypothesis space is a **number** or **bound** that quantifies the size (or richness) of the hypothesis space, i.e. the number (and type) of functions that can be represented by the hypothesis space. So a hypothesis space **has** a capacity. The two most famous measures of capacity are VC dimension and Rademacher complexity.
  
  In other words, the hypothesis class is the *object* and the capacity is a *property* (that can be measured or quantified) of this object, but there is not a big difference between hypothesis class and its capacity, in the sense that a hypothesis class naturally defines a capacity, but two (different) hypothesis classes could have the same capacity.
  
  Note that *representational capacity* (not *capacity*, which is common!) is not a standard term in computational learning theory, while *hypothesis space/class* is commonly used. For example, [this famous book](https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf) on machine learning and learning theory uses the term *hypothesis class* in many places, but it never uses the term *representational capacity*.
  
  Your book's definition of *representational capacity* is *bad*, in my opinion, if *representational capacity* is supposed to be a synonym for *capacity*, given that that definition also coincides with the definition of hypothesis class, so your confusion is understandable.
  
  > **Comments:**
  > **username_2**: I agree with you. The authors of the book should've explained these concepts in more depth. Most sources say that a "model" is an instance (after execution/training on data) of a "learning algorithm". How, then, can a model specify the family of functions the learning algorithm can choose from? Also, as you pointed out, the definition of the terms "hypothesis space" and "representational capacity" given by the authors are practically the same, although they use the terms as if they represent different concepts.  
  
  ---
  
  