Answers.Body: <p>Given a hypothesis set <span class="math-container">$H$</span>, the set of all possible mappings from <span class="math-container">$X\to Y$</span> where <span class="math-container">$X$</span> is our input space and <span class="math-container">$Y$</span> are our binary mappings: <span class="math-container">$\{-1,1\}$</span>, the growth function, <span class="math-container">$\Pi_H(m)$</span>, is defined as the maximum number of dichotomies generated by <span class="math-container">$H$</span> on <span class="math-container">$m$</span> points. Here a dichotomy is the set of <span class="math-container">$m$</span> points in <span class="math-container">$X$</span> that represent a hypothesis. A hypothesis is just a way we classify our points. Therefore with two labels we know,</p>
  
  <p><span class="math-container">$$\Pi_H(m)\leq 2^m$$</span></p>
  
  <p>This is just counts every possible hypothesis. The VC dimension is then the largest <span class="math-container">$m$</span> where <span class="math-container">$\Pi_H(m)=2^m$</span>.</p>
  
  <p>Consider a 2D perceptron, meaning our <span class="math-container">$X$</span> is <span class="math-container">$\mathbb{R}^2$</span> and our classifying hyperlane is one-dimensional: a line. The VC dimension will be 3. This is because we can shatter (correctly classify) all dichotomies for <span class="math-container">$m=3$</span>. We can either have all points be the same colour, or one point be a different colour - which is <span class="math-container">$2^3=8$</span> dichotomies. You may ask what if the points we are trying to classify are collinear. This does not matter because we are concerned with resolving the dichotomies themselves, not the location of the points. We just need a set of points (wherever they may be located) that exhibits that dichotomy. In other words, we can pick the points such that they maximize the number of dichotomies we can shatter with one classifying hyperplane (a triangle): the VC dimension is a statement of the capacity of our model.</p>
  
  <p>To make this clear, consider <span class="math-container">$m=4$</span>. We can represent the truth table of the XOR gate as a dichotomy but this is not resolvable by the perceptron, no matter where we choose the location of the points (not linearly separable). Therefore, we can resolve a maximum of 8 dichotomies, so our VC dimension is 3. In general, the VC dimension of perceptrons is <span class="math-container">$d+1$</span> where <span class="math-container">$d$</span> is the dimension of <span class="math-container">$X$</span> and <span class="math-container">$d-1$</span> is the dimension of the classifying hyperplane. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T00:05:23.960Z
Answers.Text: If the 3 points are collinear, the perceptron cannot classify them, so it's not "any" dataset of 3 points. Apart from that, your answer seems correct
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T00:21:32.077Z
Answers.Text: Yeah, I believe that has to do with the growth function. In this case, it is $\Pi_H(m)=2^3$ and the growth function of a hypothesis set is defined to maximize the number of dichotomies so a collinear set of points wouldn't be applicable when talking about the VC dimension since that isn't classifiable with one plane - they need to be in a triangular layout. But that's a good point and I'll edit my answer to be more formal.
Answers.UserDisplayName: Archie Shahidullah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T08:11:13.183Z
Answers.Text: @ArchieShahidullah thanks for your answer! Maybe I did not format my question correctly, but it is not the answer I was looking for. I understand what you wanted to say, but I think other answers are more related to my actual question. Anyhow, thanks for the effort!
Answers.UserDisplayName: Stefan Radonjic
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T22:43:53.213Z
Answers.LastActivityDate: 2020-04-17T00:49:14.967Z
Answers.LastEditDate: 2020-04-17T00:49:14.967Z
Answers.UserDisplayName: Archie Shahidullah
Answers.Body: <p>The VC dimension represents the capacity (<a href="https://www.math.arizona.edu/~hzhang/math574m/Read/vapnik.pdf" rel="nofollow noreferrer">the same Vapnik, the letter V from VC, calls it the "capacity"</a>) of a model (or, in general, hypotheses class), so a model with a higher VC dimension has more capacity (i.e. it can represent more functions) than a model with a lower VC dimension. </p>
  
  <p>The VC dimension is typically used to provide theoretical bounds e.g. on the number of samples required for a model to achieve a certain <em>test error</em> with a given <em>uncertainty</em> or, similarly, to understand the quality of your estimation given a certain dataset. </p>
  
  <p>Just to give you an idea of how the bounds look like, have a look at the theorem on page 6 (of the pdf) of the paper <a href="https://www.math.arizona.edu/~hzhang/math574m/Read/vapnik.pdf" rel="nofollow noreferrer">An overview of statistical learning theory</a> (1999) by Vapnik.</p>
  
  <p>Have also a look at <a href="https://ai.stackexchange.com/a/17881/2444">this answer</a>, where I provide more info about the VC dimension, in particular, in the context of neural networks.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T00:11:32.990Z
Answers.Text: I will later update this answer to provide more relevant (to the question) bounds and maybe explain them. Alternatively, have a look at [this other answer](https://ai.stackexchange.com/a/20341/2444).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T08:11:54.437Z
Answers.Text: Thank you for the references. I am currently reading your answer on VC dimensions in the context of neural networks as we speak.
Answers.UserDisplayName: Stefan Radonjic
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T00:11:11.417Z
Answers.LastActivityDate: 2020-04-17T00:20:23.253Z
Answers.LastEditDate: 2020-04-17T00:20:23.253Z
Answers.UserDisplayName: nbro
Answers.Body: <p>From <a href="https://www.springer.com/gp/book/9780387987804" rel="nofollow noreferrer">[1]</a> we know that we have the following bound between the test and train error for i.i.d samples:</p>
  <p><span class="math-container">$$
  \mathbb{P}\left(R \leqslant R_{emp} + \sqrt{\frac{d\left(\log{\left(\frac{2m}{d}\right)}+1\right)-\log{\left(\frac{\eta}{4}\right)}}{m}}\right) \geqslant 1-\eta
  $$</span></p>
  <p><span class="math-container">$R$</span> is the test error, <span class="math-container">$R_{emp}$</span> is the training error, <span class="math-container">$m$</span> is the size of the training dataset, and <span class="math-container">$d$</span> is the hypothesis class's VC dimension. As you can see, the training and test errors have some relations to the dataset's size (<span class="math-container">$m$</span>) and <span class="math-container">$d$</span>.</p>
  <p>Now, in terms of PAC learnability, we want to find a (lower or upper) bound for <span class="math-container">$m$</span> such that the absolute difference between <span class="math-container">$R$</span> and <span class="math-container">$R_{emp}$</span> will be less than a given <span class="math-container">$\epsilon$</span> with a given probability of at least <span class="math-container">$1-\eta$</span>.  Hence, <span class="math-container">$m$</span> can be computed in terms of <span class="math-container">$\epsilon$</span>, <span class="math-container">$\eta$</span>, and <span class="math-container">$d$</span>. For example, it can be proved (<a href="https://dl.acm.org/doi/10.5555/2946645.2946683" rel="nofollow noreferrer">[2]</a>) to train a binary classifier with <span class="math-container">$\epsilon$</span> difference between test and train error with the probability of at least <span class="math-container">$1-\eta$</span>, we need <span class="math-container">$O\left(\frac{d + \log\frac{1}{\eta}}{\epsilon} \right)$</span> i.i.d sample data, i.e., <span class="math-container">$m = O\left(\frac{d + \log\frac{1}{\eta}}{\epsilon}\right)$</span>. See more example and references <a href="https://en.wikipedia.org/wiki/Sample_complexity" rel="nofollow noreferrer">here</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T00:26:45.523Z
Answers.LastActivityDate: 2020-12-07T22:06:37.550Z
Answers.LastEditDate: 2020-12-07T22:06:37.550Z
Answers.UserDisplayName: OmG
Body: <p>This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in <a href="https://www.youtube.com/watch?v=Dc0sr0kdBVI&amp;list=PLD63A284B7615313A&amp;index=7" rel="nofollow noreferrer">this</a> video prof. is trying to explain how we should interpret the VC dimension in terms of what it means in layman terms, and why do we need it in practice.</p>
  <p>The first part I think I understand, please correct me if I am wrong. VC Dimension dictates the number of effective parameters (i.e. degrees of freedom) that model has. In other words, the number of parameters the model needs in order to cover all possible label combinations for the chosen dataset. Now, the second part is not clear to me. The professor is trying to answer the question:</p>
  <blockquote>
  <p>How does knowing the VC dimension of the hypothesis class affect number of samples we need for training?</p>
  </blockquote>
  <p>Again, I apologize if all of this may be trivial, but I am new to the field and wish to learn as much as I can, so I can implement better and more efficient programs in practice.</p>
  
Tags: <computational-learning-theory><vc-dimension><vc-theory><sample-complexity><hypothesis-class>
Title: How does size of the dataset depend on VC dimension of the hypothesis class?
UserDisplayName: Stefan Radonjic
ThreadText: # How does size of the dataset depend on VC dimension of the hypothesis class?
  
  (Asked by: username_0 on 2020-04-16)
  
  This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in [this](https://www.youtube.com/watch?v=Dc0sr0kdBVI&list=PLD63A284B7615313A&index=7) video prof. is trying to explain how we should interpret the VC dimension in terms of what it means in layman terms, and why do we need it in practice.
  
  The first part I think I understand, please correct me if I am wrong. VC Dimension dictates the number of effective parameters (i.e. degrees of freedom) that model has. In other words, the number of parameters the model needs in order to cover all possible label combinations for the chosen dataset. Now, the second part is not clear to me. The professor is trying to answer the question:
  
  > How does knowing the VC dimension of the hypothesis class affect number of samples we need for training?
  
  Again, I apologize if all of this may be trivial, but I am new to the field and wish to learn as much as I can, so I can implement better and more efficient programs in practice.
  
  **Tags:** computational-learning-theory, vc-dimension, vc-theory, sample-complexity, hypothesis-class
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2020-04-17. Score: 3 | Accepted answer
  
  From [[1]](https://www.springer.com/gp/book/9780387987804) we know that we have the following bound between the test and train error for i.i.d samples:
  
  $$
  \mathbb{P}\left(R \leqslant R\_{emp} + \sqrt{\frac{d\left(\log{\left(\frac{2m}{d}\right)}+1\right)-\log{\left(\frac{\eta}{4}\right)}}{m}}\right) \geqslant 1-\eta
  $$
  
  $R$ is the test error, $R\_{emp}$ is the training error, $m$ is the size of the training dataset, and $d$ is the hypothesis class's VC dimension. As you can see, the training and test errors have some relations to the dataset's size ($m$) and $d$.
  
  Now, in terms of PAC learnability, we want to find a (lower or upper) bound for $m$ such that the absolute difference between $R$ and $R\_{emp}$ will be less than a given $\epsilon$ with a given probability of at least $1-\eta$. Hence, $m$ can be computed in terms of $\epsilon$, $\eta$, and $d$. For example, it can be proved ([[2]](https://dl.acm.org/doi/10.5555/2946645.2946683)) to train a binary classifier with $\epsilon$ difference between test and train error with the probability of at least $1-\eta$, we need $O\left(\frac{d + \log\frac{1}{\eta}}{\epsilon} \right)$ i.i.d sample data, i.e., $m = O\left(\frac{d + \log\frac{1}{\eta}}{\epsilon}\right)$. See more example and references [here](https://en.wikipedia.org/wiki/Sample_complexity).
  
  
  ---
  
  ### Answer by username_1 on 2020-04-16. Score: 3
  
  Given a hypothesis set $H$, the set of all possible mappings from $X\to Y$ where $X$ is our input space and $Y$ are our binary mappings: $\{-1,1\}$, the growth function, $\Pi\_H(m)$, is defined as the maximum number of dichotomies generated by $H$ on $m$ points. Here a dichotomy is the set of $m$ points in $X$ that represent a hypothesis. A hypothesis is just a way we classify our points. Therefore with two labels we know,
  
  $$\Pi\_H(m)\leq 2^m$$
  
  This is just counts every possible hypothesis. The VC dimension is then the largest $m$ where $\Pi\_H(m)=2^m$.
  
  Consider a 2D perceptron, meaning our $X$ is $\mathbb{R}^2$ and our classifying hyperlane is one-dimensional: a line. The VC dimension will be 3. This is because we can shatter (correctly classify) all dichotomies for $m=3$. We can either have all points be the same colour, or one point be a different colour - which is $2^3=8$ dichotomies. You may ask what if the points we are trying to classify are collinear. This does not matter because we are concerned with resolving the dichotomies themselves, not the location of the points. We just need a set of points (wherever they may be located) that exhibits that dichotomy. In other words, we can pick the points such that they maximize the number of dichotomies we can shatter with one classifying hyperplane (a triangle): the VC dimension is a statement of the capacity of our model.
  
  To make this clear, consider $m=4$. We can represent the truth table of the XOR gate as a dichotomy but this is not resolvable by the perceptron, no matter where we choose the location of the points (not linearly separable). Therefore, we can resolve a maximum of 8 dichotomies, so our VC dimension is 3. In general, the VC dimension of perceptrons is $d+1$ where $d$ is the dimension of $X$ and $d-1$ is the dimension of the classifying hyperplane.
  
  > **Comments:**
  > **username_2**: If the 3 points are collinear, the perceptron cannot classify them, so it's not "any" dataset of 3 points. Apart from that, your answer seems correct  
  > **username_1**: Yeah, I believe that has to do with the growth function. In this case, it is $\Pi_H(m)=2^3$ and the growth function of a hypothesis set is defined to maximize the number of dichotomies so a collinear set of points wouldn't be applicable when talking about the VC dimension since that isn't classifiable with one plane - they need to be in a triangular layout. But that's a good point and I'll edit my answer to be more formal.  
  > **username_0**: @ArchieShahidullah thanks for your answer! Maybe I did not format my question correctly, but it is not the answer I was looking for. I understand what you wanted to say, but I think other answers are more related to my actual question. Anyhow, thanks for the effort!  
  
  ---
  
  ### Answer by username_2 on 2020-04-17. Score: 2
  
  The VC dimension represents the capacity ([the same Vapnik, the letter V from VC, calls it the "capacity"](https://www.math.arizona.edu/~hzhang/math574m/Read/vapnik.pdf)) of a model (or, in general, hypotheses class), so a model with a higher VC dimension has more capacity (i.e. it can represent more functions) than a model with a lower VC dimension.
  
  The VC dimension is typically used to provide theoretical bounds e.g. on the number of samples required for a model to achieve a certain *test error* with a given *uncertainty* or, similarly, to understand the quality of your estimation given a certain dataset.
  
  Just to give you an idea of how the bounds look like, have a look at the theorem on page 6 (of the pdf) of the paper [An overview of statistical learning theory](https://www.math.arizona.edu/~hzhang/math574m/Read/vapnik.pdf) (1999) by Vapnik.
  
  Have also a look at [this answer](https://ai.stackexchange.com/a/17881/2444), where I provide more info about the VC dimension, in particular, in the context of neural networks.
  
  > **Comments:**
  > **username_2**: I will later update this answer to provide more relevant (to the question) bounds and maybe explain them. Alternatively, have a look at [this other answer](https://ai.stackexchange.com/a/20341/2444).  
  > **username_0**: Thank you for the references. I am currently reading your answer on VC dimensions in the context of neural networks as we speak.  
  
  ---
  
  