Answers.Body: <p>The measure that you are talking about actually has a name. It is called the &quot;Popper dimension&quot; -- it was introduced by <a href="https://en.wikipedia.org/wiki/Karl_Popper" rel="nofollow noreferrer">Karl Popper</a> in his &quot;<a href="https://en.wikipedia.org/wiki/The_Logic_of_Scientific_Discovery" rel="nofollow noreferrer">Logic of scientific discovery</a>&quot;.</p>
  <p>Popper's idea of <em>falsifiability</em> was, as Vladimir Vapnik himself admits, the inspiration behind their work on the VC dimension. The VC dimension of the hypothesis set <span class="math-container">$\mathcal{H}$</span> measures the &quot;complexity&quot; of the set by looking at how easy would it be to falsify it. The hypothesis sets with higher VC dimension should be harder to falsify. With limiting case of infinite VC dimension which is unfalsifiable for almost any data.</p>
  <p>VC dimension and Popper dimension are different in exactly the way you are describing. This quote from the <a href="https://link.springer.com/article/10.1007%2Fs10838-009-9091-3" rel="nofollow noreferrer">philosophy paper</a> that Vapnik co-authored states it rather succinctly:</p>
  <blockquote>
  <p>The VC-dimension is the largest number of points one can shatter, the Popper dimension is one less than the smallest number of points one can not shatter.</p>
  </blockquote>
  <p>This paper goes on trying to reconcile the two definitions but I didn't find their  exposition satisfactory (or even meaningful). I've found much more harsh take on this is in the <a href="https://dl.acm.org/doi/book/10.5555/1296167" rel="nofollow noreferrer">&quot;Learning from data&quot;</a> book (second edition, Section 4.7) :</p>
  <blockquote>
  <p>Now we can contrast the VC dimension and Popper’s dimension, and conclude that Popper’s definition is not meaningful, as it does not lead to any useful conditions for generalization. In fact, for linear estimators the Popper’s dimension is at most 2, regardless of the problem dimensionality, as a set of hyperplanes cannot shatter three collinear points.</p>
  </blockquote>
  <p>Which looks fair to me.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T02:05:15.110Z
Answers.Text: I finally had the opportunity to read the paper "_Falsificationism and Statistical Learning Theory: Comparing the Popper and Vapnik-Chervonenkis Dimensions_" that you mention. There, Vapnik does not admit that the VC dimension was inspired by Popper's dimension, which Popper calls the "_**characteristic number** of a theory_". I agree with your conclusion that this paper and the authors' arguments are not very meaningful or, better, clear. It's not even clear how Popper's definition of a **characteristic number** of a scientific theory is related to the VC dimension.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T02:16:16.017Z
Answers.Text: Popper writes about a theory as a set of statements; then talks about statements in that theory... It's not clear how the authors of this paper drew all those conclusions from the description of a characteristic number (section 3.2). It might be that, if I read the paper again, I understand more their points. As you point out, they say the VC dimension of a hyperplane can be $d+1$, so the Popper's dimension would be $d$ in this case.  However, in another example, they say that the Popper's dimension is $2$, rather than $3$, which is one less than the VC dimension in that other example.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T02:22:34.010Z
Answers.Text: So, the paper seems to be inconsistent, or maybe they are just showing us how Popper was actually inconsistent, but, to me, their interpretations of Popper's quotes are not clear. One example that they give that is consistent with the concept of "falsification (of a theory)" is that of women's and men's measurements, where, after you have found a single man or woman with different measurements than the ones you believed men and women had, then you immediately falsify your theory. That makes sense to me.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T11:55:11.977Z
Answers.Text: In any case, after having read that paper, your statement "_Popper's idea of *falsifiability* was, as Vladimir Vapnik himself admits, the inspiration behind their work on the VC dimension. The VC dimension of the hypothesis set $\mathcal{H}$ measures the "complexity" of the set by looking at how easy would it be to falsify it. The hypothesis sets with higher VC dimension should be harder to falsify._" seems misleading because the definition of "falsification" that you're giving here, in the case of VC dimension, is different than the definition of falsification by Popper.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T11:58:52.170Z
Answers.Text: More specifically, if you cannot label one ordering/configuration of the same number of points $n$, it's fine, as long as you are able to label correctly at least one ordering of the same $n$ points. If you're not able to label any configuration of $n+1$ points, then, in a way, you falsify this hypothesis test, in the sense that you show that you cannot find a hypothesis that solves the classification problem for any of the possible labels of $n+1$ points. So, the VC dimension is $n$. Saying this does not imply that you will be able to solve all classification problems of $n$ points!
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T12:00:22.963Z
Answers.Text: So, this notion of falsification is really different than Popper's notion of falsification of a theory, where, as far as I understand, a single (or a set of) contradictory statement(s) to your theory would falsify it (although he talks about d-tuples of statements). So, I think that saying the VC dimension is related to falsification, especially in the context of Popper's ideas, is misleading, because Popper had a different idea of falsification, which is stronger/stricter than the VC dimension, but I am not even sure if it makes sense to compare Popper's ideas with the VC dimension.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-28T12:19:58.323Z
Answers.Text: I would upvote this answer because Popper's ideas and the paper that you provided are relevant to what I was asking, but I don't think saying that last quote makes sense is fair. To me, it doesn't make sense. Popper was talking about a different problem, i.e. the one of falsifying a theory as a way of providing that it's wrong and he thought that you could not prove a general theory is true. So, why would Popper's dimension not be meaningful? It's meaningful, but in another context. People seem to just misinterpret Popper and I am not even sure why Popper pops up in the context of ML.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-29T09:32:20.170Z
Answers.Text: @nbro It is hard reading such a long aside across several long comments. As I understand, this is not how this site is supposed to work. I trust that I did give a helpful answer. You might disagree with it on philosophical grounds. If you can formulate a pointed follow-up question(s) - I (or somebody else) would try and answer it. Otherwise, this doesn't sound too constructive and useful.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-29T11:46:50.060Z
Answers.Text: I don't have any follow-up question right now. My direct feedback to you is that, although it's relevant, your answer doesn't fully address my question and I disagree with something that you wrote, so I cannot upvote/accept it. If you're willing to read my comments above, then maybe you would be able to change your answer to fix what I think is wrong. Anyway, it's true, comments are not meant for long discussions, and I could have summarised what I wanted to say in fewer comments. Later, I will move these comments into a chat. But note that comments can be used to ask for clarifications.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-29T13:17:52.413Z
Answers.Text: @nbro Did you have a chance to look at the "Learning from data. Ch. 4.7" reference I've provided? It looks like it gives a detailed exposé on the matters you are trying to formulate in your comments.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-29T17:23:19.047Z
Answers.Text: I don't have access to that book right now.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-20T17:58:58.893Z
Answers.LastActivityDate: 2021-05-20T17:58:58.893Z
Answers.UserDisplayName: Kostya
Answers.Body: <p>I would say, that meaning of VC dimension is at least a possibility to implement any function on the given number of points for some case, not an express any function on <span class="math-container">$n$</span> points.</p>
  <p>Yes, you are right, that this definition, unfortunately, is not very useful in practice.</p>
  <p>Say, family of functions <span class="math-container">$\text{sign}(\sin(ax))$</span> has infinite <span class="math-container">$\text{VC}$</span> dimension. There exists an infinite sequence <span class="math-container">$x_n$</span>, such that by tuning the parameter <span class="math-container">$a$</span> one can implement any logical function <span class="math-container">$0 1 0 \ldots 1$</span> on these points. However, this doesn't make this class of functions an outstanding ML algorithm.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-20T09:21:34.410Z
Answers.Text: Unfortunately, this does not really answer my question, which is: _**why** did VC define the VC dimension in this way?_ The answer can probably be found in the paper I am mentioning in the comment under my post above.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-20T09:27:09.940Z
Answers.Text: @nbro they defined it in this way because they can obtain some analytical results about it. The definition, you are asking for is more useful, but seems like one has not succeeded to develop some generic theory for it
Answers.UserDisplayName: spiridon_the_sun_rotator
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-20T09:30:20.360Z
Answers.Text: Could you please point me to the relevant part of the mentioned paper or any other resource that discusses this, i.e. the why? I didn't read the mentioned paper, but after having skimmed through it, I noticed that it mentions the _growth function_. It's probably also a good idea for you to edit your answer so that you focus on answering my question (if you really know the answer).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-20T08:50:22.933Z
Answers.LastActivityDate: 2021-05-20T09:24:51.247Z
Answers.LastEditDate: 2021-05-20T09:24:51.247Z
Answers.UserDisplayName: spiridon_the_sun_rotator
Body: <p>Let's start with a typical definition of the VC dimension (as described in <a href="https://mitpress.ublish.com/ereader/7093/?preview=#page/36" rel="nofollow noreferrer">this book</a>)</p>
  <blockquote>
  <p><strong>Definition <span class="math-container">$3.10$</span> (VC-dimension)</strong> The <span class="math-container">$V C$</span> -dimension of a hypothesis set <span class="math-container">$\mathcal{H}$</span> is the size of the largest set that can be shattered by <span class="math-container">$\mathcal{H}$</span> :
  <span class="math-container">$$
  \operatorname{VCdim}(\mathcal{H})= \max \left\{m: \Pi_{\mathcal{H}}(m)=2^{m}\right\}
  $$</span></p>
  </blockquote>
  <p>So, if there <strong>exists</strong> <em>some</em> set of size <span class="math-container">$d$</span> that <span class="math-container">$\mathcal{H}$</span> can shatter and it cannot shatter any set of size <span class="math-container">$d+1$</span>, then the <span class="math-container">$\operatorname{VCdim}(\mathcal{H}) = d$</span>.</p>
  <p>Now, my question is: why would we be just interested in the <strong>existence</strong> of <strong>some</strong> set of size <span class="math-container">$d$</span> and not <strong>all</strong> sets of size <span class="math-container">$d$</span>?</p>
  <p>For instance, if you consider one of the typical examples that are used to illustrate the concept of the VC dimension, i.e. <span class="math-container">$\mathcal{H}$</span> is the set of all rectangles, then we can show that <span class="math-container">$\operatorname{VCdim}(\mathcal{H}) = d = 4$</span>, given that there's a configuration of <span class="math-container">$d=4$</span> points that, for all possible labellings of those points, there's a hypothesis in <span class="math-container">$\mathcal{H}$</span> that correctly classifies those points. However, we can also easily show that, if the 4 points are collinear, there's some labelling of them (i.e. the 1st and 3rd are of colour <span class="math-container">$A$</span>, while the 2nd and 4th are of colour <span class="math-container">$B \neq A$</span>) that a rectangle cannot classify correctly.</p>
  <p>So, the class of all rectangles can shatter some sets of points, but not all, so we would need another class of hypotheses to classify all sets of four points correctly. The VC dimension does not seem to provide any intuition on which set of classes would do the trick.</p>
  <p>So, do you know why the VC dimension wasn't defined for all configurations of <span class="math-container">$d$</span> points? Was this just a need of Vapnik and Chervonenkis for the work they were developing (VC theory), or could have they defined it differently? So, if you know the rationale behind this specific definition, feel free to provide an answer. References to relevant work by Vapnik and Chervonenkis are also appreciated.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-19T11:06:45.333Z
Comments.Text: For people interested in answering this question, the paper [On the uniform convergence of relative frequencies of events to their probabilities](https://courses.engr.illinois.edu/ece544na/fa2014/vapnik71.pdf) (1971) by VC is probably the one that you should read first.
Comments.UserDisplayName: nbro
Tags: <reference-request><definitions><computational-learning-theory><history><vc-dimension>
Title: Why was the VC dimension not defined for all configurations of $d$ points?
UserDisplayName: nbro
ThreadText: # Why was the VC dimension not defined for all configurations of $d$ points?
  
  (Asked by: username_0 on 2021-05-18)
  
  Let's start with a typical definition of the VC dimension (as described in [this book](https://mitpress.ublish.com/ereader/7093/?preview=#page/36))
  
  > **Definition $3.10$ (VC-dimension)** The $V C$ -dimension of a hypothesis set $\mathcal{H}$ is the size of the largest set that can be shattered by $\mathcal{H}$ :
  > $$
  > \operatorname{VCdim}(\mathcal{H})= \max \left\{m: \Pi\_{\mathcal{H}}(m)=2^{m}\right\}
  > $$
  
  So, if there **exists** *some* set of size $d$ that $\mathcal{H}$ can shatter and it cannot shatter any set of size $d+1$, then the $\operatorname{VCdim}(\mathcal{H}) = d$.
  
  Now, my question is: why would we be just interested in the **existence** of **some** set of size $d$ and not **all** sets of size $d$?
  
  For instance, if you consider one of the typical examples that are used to illustrate the concept of the VC dimension, i.e. $\mathcal{H}$ is the set of all rectangles, then we can show that $\operatorname{VCdim}(\mathcal{H}) = d = 4$, given that there's a configuration of $d=4$ points that, for all possible labellings of those points, there's a hypothesis in $\mathcal{H}$ that correctly classifies those points. However, we can also easily show that, if the 4 points are collinear, there's some labelling of them (i.e. the 1st and 3rd are of colour $A$, while the 2nd and 4th are of colour $B \neq A$) that a rectangle cannot classify correctly.
  
  So, the class of all rectangles can shatter some sets of points, but not all, so we would need another class of hypotheses to classify all sets of four points correctly. The VC dimension does not seem to provide any intuition on which set of classes would do the trick.
  
  So, do you know why the VC dimension wasn't defined for all configurations of $d$ points? Was this just a need of Vapnik and Chervonenkis for the work they were developing (VC theory), or could have they defined it differently? So, if you know the rationale behind this specific definition, feel free to provide an answer. References to relevant work by Vapnik and Chervonenkis are also appreciated.
  
  **Tags:** reference-request, definitions, computational-learning-theory, history, vc-dimension
  > **Comments:**
  > **username_0**: For people interested in answering this question, the paper [On the uniform convergence of relative frequencies of events to their probabilities](https://courses.engr.illinois.edu/ece544na/fa2014/vapnik71.pdf) (1971) by VC is probably the one that you should read first.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-05-20. Score: 1
  
  The measure that you are talking about actually has a name. It is called the "Popper dimension" -- it was introduced by [Karl Popper](https://en.wikipedia.org/wiki/Karl_Popper) in his "[Logic of scientific discovery](https://en.wikipedia.org/wiki/The_Logic_of_Scientific_Discovery)".
  
  Popper's idea of *falsifiability* was, as Vladimir Vapnik himself admits, the inspiration behind their work on the VC dimension. The VC dimension of the hypothesis set $\mathcal{H}$ measures the "complexity" of the set by looking at how easy would it be to falsify it. The hypothesis sets with higher VC dimension should be harder to falsify. With limiting case of infinite VC dimension which is unfalsifiable for almost any data.
  
  VC dimension and Popper dimension are different in exactly the way you are describing. This quote from the [philosophy paper](https://link.springer.com/article/10.1007%2Fs10838-009-9091-3) that Vapnik co-authored states it rather succinctly:
  
  > The VC-dimension is the largest number of points one can shatter, the Popper dimension is one less than the smallest number of points one can not shatter.
  
  This paper goes on trying to reconcile the two definitions but I didn't find their exposition satisfactory (or even meaningful). I've found much more harsh take on this is in the ["Learning from data"](https://dl.acm.org/doi/book/10.5555/1296167) book (second edition, Section 4.7) :
  
  > Now we can contrast the VC dimension and Popper’s dimension, and conclude that Popper’s definition is not meaningful, as it does not lead to any useful conditions for generalization. In fact, for linear estimators the Popper’s dimension is at most 2, regardless of the problem dimensionality, as a set of hyperplanes cannot shatter three collinear points.
  
  Which looks fair to me.
  
  > **Comments:**
  > **username_0**: I finally had the opportunity to read the paper "_Falsificationism and Statistical Learning Theory: Comparing the Popper and Vapnik-Chervonenkis Dimensions_" that you mention. There, Vapnik does not admit that the VC dimension was inspired by Popper's dimension, which Popper calls the "_**characteristic number** of a theory_". I agree with your conclusion that this paper and the authors' arguments are not very meaningful or, better, clear. It's not even clear how Popper's definition of a **characteristic number** of a scientific theory is related to the VC dimension.  
  > **username_0**: Popper writes about a theory as a set of statements; then talks about statements in that theory... It's not clear how the authors of this paper drew all those conclusions from the description of a characteristic number (section 3.2). It might be that, if I read the paper again, I understand more their points. As you point out, they say the VC dimension of a hyperplane can be $d+1$, so the Popper's dimension would be $d$ in this case.  However, in another example, they say that the Popper's dimension is $2$, rather than $3$, which is one less than the VC dimension in that other example.  
  > **username_0**: So, the paper seems to be inconsistent, or maybe they are just showing us how Popper was actually inconsistent, but, to me, their interpretations of Popper's quotes are not clear. One example that they give that is consistent with the concept of "falsification (of a theory)" is that of women's and men's measurements, where, after you have found a single man or woman with different measurements than the ones you believed men and women had, then you immediately falsify your theory. That makes sense to me.  
  > **username_0**: In any case, after having read that paper, your statement "_Popper's idea of *falsifiability* was, as Vladimir Vapnik himself admits, the inspiration behind their work on the VC dimension. The VC dimension of the hypothesis set $\mathcal{H}$ measures the "complexity" of the set by looking at how easy would it be to falsify it. The hypothesis sets with higher VC dimension should be harder to falsify._" seems misleading because the definition of "falsification" that you're giving here, in the case of VC dimension, is different than the definition of falsification by Popper.  
  > **username_0**: More specifically, if you cannot label one ordering/configuration of the same number of points $n$, it's fine, as long as you are able to label correctly at least one ordering of the same $n$ points. If you're not able to label any configuration of $n+1$ points, then, in a way, you falsify this hypothesis test, in the sense that you show that you cannot find a hypothesis that solves the classification problem for any of the possible labels of $n+1$ points. So, the VC dimension is $n$. Saying this does not imply that you will be able to solve all classification problems of $n$ points!  
  > **username_0**: So, this notion of falsification is really different than Popper's notion of falsification of a theory, where, as far as I understand, a single (or a set of) contradictory statement(s) to your theory would falsify it (although he talks about d-tuples of statements). So, I think that saying the VC dimension is related to falsification, especially in the context of Popper's ideas, is misleading, because Popper had a different idea of falsification, which is stronger/stricter than the VC dimension, but I am not even sure if it makes sense to compare Popper's ideas with the VC dimension.  
  > **username_0**: I would upvote this answer because Popper's ideas and the paper that you provided are relevant to what I was asking, but I don't think saying that last quote makes sense is fair. To me, it doesn't make sense. Popper was talking about a different problem, i.e. the one of falsifying a theory as a way of providing that it's wrong and he thought that you could not prove a general theory is true. So, why would Popper's dimension not be meaningful? It's meaningful, but in another context. People seem to just misinterpret Popper and I am not even sure why Popper pops up in the context of ML.  
  > **username_1**: @nbro It is hard reading such a long aside across several long comments. As I understand, this is not how this site is supposed to work. I trust that I did give a helpful answer. You might disagree with it on philosophical grounds. If you can formulate a pointed follow-up question(s) - I (or somebody else) would try and answer it. Otherwise, this doesn't sound too constructive and useful.  
  > **username_0**: I don't have any follow-up question right now. My direct feedback to you is that, although it's relevant, your answer doesn't fully address my question and I disagree with something that you wrote, so I cannot upvote/accept it. If you're willing to read my comments above, then maybe you would be able to change your answer to fix what I think is wrong. Anyway, it's true, comments are not meant for long discussions, and I could have summarised what I wanted to say in fewer comments. Later, I will move these comments into a chat. But note that comments can be used to ask for clarifications.  
  > **username_1**: @nbro Did you have a chance to look at the "Learning from data. Ch. 4.7" reference I've provided? It looks like it gives a detailed exposé on the matters you are trying to formulate in your comments.  
  > **username_0**: I don't have access to that book right now.  
  
  ---
  
  ### Answer by username_2 on 2021-05-20. Score: 0
  
  I would say, that meaning of VC dimension is at least a possibility to implement any function on the given number of points for some case, not an express any function on $n$ points.
  
  Yes, you are right, that this definition, unfortunately, is not very useful in practice.
  
  Say, family of functions $\text{sign}(\sin(ax))$ has infinite $\text{VC}$ dimension. There exists an infinite sequence $x\_n$, such that by tuning the parameter $a$ one can implement any logical function $0 1 0 \ldots 1$ on these points. However, this doesn't make this class of functions an outstanding ML algorithm.
  
  > **Comments:**
  > **username_0**: Unfortunately, this does not really answer my question, which is: _**why** did VC define the VC dimension in this way?_ The answer can probably be found in the paper I am mentioning in the comment under my post above.  
  > **username_2**: @nbro they defined it in this way because they can obtain some analytical results about it. The definition, you are asking for is more useful, but seems like one has not succeeded to develop some generic theory for it  
  > **username_0**: Could you please point me to the relevant part of the mentioned paper or any other resource that discusses this, i.e. the why? I didn't read the mentioned paper, but after having skimmed through it, I noticed that it mentions the _growth function_. It's probably also a good idea for you to edit your answer so that you focus on answering my question (if you really know the answer).  
  
  ---
  
  