Answers.Body: <p><strong>Shattered set.</strong> First we need a concept of a shattered set. I'll work from a shattered set <a href="https://en.wikipedia.org/wiki/Shattered_set#Example" rel="nofollow noreferrer">example in Wikipedia</a> adjusting it to your notation.</p>
  <p>The statement that <span class="math-container">$\mathcal{H}$</span> shatters <span class="math-container">$C$</span> means that for every subset <span class="math-container">$A \subset C$</span> there is a set <span class="math-container">$B\in\mathcal{H}$</span> such that <span class="math-container">$B$</span> &quot;separates&quot; <span class="math-container">$A$</span> from <span class="math-container">$C \backslash A$</span>. Writing this formally:</p>
  <p><span class="math-container">$$\text{shatters}(\mathcal{H},C) = \forall A \subset C\; \exists B\in\mathcal{H}\;.\;A = B\,\cap A $$</span></p>
  <p>As an example consider the set <span class="math-container">$C$</span> of four points on <span class="math-container">$\mathcal{X} = \mathbb{R}^2$</span>:</p>
  <p><span class="math-container">$$C = \left\{(0,0); (0,1); (1,0); (1,1)\right\}$$</span></p>
  <p>And the classification class <span class="math-container">$\mathcal{H}$</span> being all possible 2D discs on <span class="math-container">$\mathcal{X} =\mathbb{R}^2$</span>. (Notice that people use the world &quot;<a href="https://en.wikipedia.org/wiki/Class_(set_theory)" rel="nofollow noreferrer">class</a>&quot; here, because we are dealing with &quot;set-of-sets&quot; stuff and that might get <a href="https://en.wikipedia.org/wiki/Class_(set_theory)#Paradoxes" rel="nofollow noreferrer">tricky</a>). Note that a disk can be represented as the set of all points inside the circle.</p>
  <p>Now, it turns out that this <span class="math-container">$\mathcal{H}$</span> doesn't shatter <span class="math-container">$C$</span>. The counterexample would be the subset <span class="math-container">$A$</span> of &quot;diagonal&quot; points:</p>
  <p><span class="math-container">$$A = \left\{(0,0); (1,1)\right\} \subset C$$</span></p>
  <p>There is no 2D disk <span class="math-container">$B\in\mathcal{H}$</span> (in the context of learning theory, an element/set of the hypothesis class is a <em>hypothesis</em>, which can also be viewed as a function) that satisfies <span class="math-container">$A = B\,\cap A$</span>.  Intuitively, this means that you cannot use a 2D disk to classify your pair of points <span class="math-container">$A$</span> from the rest of the set <span class="math-container">$C$</span>.</p>
  <p><strong>The <a href="https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension" rel="nofollow noreferrer">VC dimension</a></strong> of <span class="math-container">$\mathcal{H}$</span> is the maximal cardinality <span class="math-container">$d$</span> of the set <span class="math-container">$C$</span> that it can shatter. For <span class="math-container">$d=3$</span>, we can provide tree points <span class="math-container">$C'$</span> for which we can easily find all discs that cover all eight possible subsets of <span class="math-container">$C'$</span>:</p>
  <p><span class="math-container">$$C' = \left\{(0,0); (0,1); (1,0)\right\}$$</span></p>
  <p>Above we've shown that for a particular set <span class="math-container">$C$</span> of <span class="math-container">$d=4$</span> points <span class="math-container">$\text{shatters}(\mathcal{H}, C)$</span> is false. But we need to prove that it is false <em>for all 4-point sets</em>. To prove this, we  consider a convex hull of an arbitrary set of four points <span class="math-container">$C = \left\{a;b;c;d\right\}$</span>. In general position, the convex hull is either a triangle or a quad:</p>
  <p><a href="https://i.sstatic.net/Igk5q.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Igk5q.png" alt="enter image description here" /></a></p>
  <p>In the case of a triangle, we choose the outermost three points as a counterexample set <span class="math-container">$A$</span>. So, with this (labeling) configuration, you cannot find a disk that covers (i.e. classifies) the outermost three points correctly while excluding the point inside the triangle. In the case of a quad, we choose the pair on the longest diagonal. If any three points lay on a single line, then we choose the pair of outermost points.</p>
  <p>This sketches a proof that no <span class="math-container">$d=4$</span> point set can be shattered by <span class="math-container">$\mathcal{H}$</span>, but we've shown that there is a <span class="math-container">$d=3$</span> set <span class="math-container">$C'$</span> that can be. Concluding that <span class="math-container">$VCdim(\mathcal{H}) = 3$</span></p>
  <p><strong>Another example</strong> is considered on the next page (pg. 71) of the book you've referenced. It again considers 2D plane  <span class="math-container">$\mathcal{X} =\mathbb{R}^2$</span> and the classification class <span class="math-container">$\mathcal{H}$</span> is all possible axis-aligned rectangles. Authors show a configuration <span class="math-container">$C$</span> of four points that can be shattered by <span class="math-container">$\mathcal{H}$</span> on the left of figure 6.1. And then provide a proof that no <span class="math-container">$d=5$</span> points can be shattered by axis-aligned rectangles. Concluding that VC dimension of their  <span class="math-container">$\mathcal{H}$</span> is four.</p>
  <p>Hope these examples help. (BTW, note that, it seems <a href="https://cs.stackexchange.com/questions/75327/why-is-deep-learning-hyped-despite-bad-vc-dimension">that Deep Learning has quite bad VC dimension</a> but it still works somehow - which is rather puzzling).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-11T18:25:48.990Z
Answers.Text: Regarding the VC dimension of neural networks, I am not really an expert in this topic, but you may be interested in [my answer here](https://ai.stackexchange.com/a/17881/2444). Essentially, as far as I know, the VC dimension of neural networks is often expressed as a bound rather than a specific number. Given it's often a loose bound, the actual VC dimension may be actually quite big.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-11T18:25:50.810Z
Answers.Text: Moreover, the adversarial examples show that neural networks can actually be fooled. I need to think about how the VC dimension is related to this (I suspect that we are estimating the expected risk is the wrong way), but I think it's misleading to say that "VC dimension of neural networks is low, but neural networks 'work', so the VC dimension is useless", which is a conclusion I've already heard (just to clarify, I had already come across that post on CS SE).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-11T17:04:35.297Z
Answers.LastActivityDate: 2021-05-12T08:35:15.643Z
Answers.LastEditDate: 2021-05-12T08:35:15.643Z
Answers.UserDisplayName: Kostya
Answers.Body: <p>Trying to explain the idea of VC to some of my colleagues I've discovered quite an intuitive way of laying out the basic idea. Without going through lots of math and notation as I've done in <a href="https://ai.stackexchange.com/a/27756/20538">my other answer</a>.</p>
  <p>Imagine a following game between two players <span class="math-container">$\alpha$</span> and <span class="math-container">$\beta$</span> :</p>
  <ol>
  <li>First, player <span class="math-container">$\alpha$</span> plots <span class="math-container">$d=4$</span> points on a piece of paper. She may place the points however she likes.</li>
  <li>Next, player <span class="math-container">$\beta$</span> marks several of the drawn points.</li>
  <li>Finally, player <span class="math-container">$\alpha$</span> should draw a circle such that all the marked points are inside the circle, and all the unmarked points - outside. (Points on the boundary considered &quot;inside&quot;.)</li>
  </ol>
  <p>The player <span class="math-container">$\alpha$</span> wins if she can draw such a circle at step #3. The player <span class="math-container">$\beta$</span> wins if making such circle is impossible.</p>
  <p>If you try to analyze this game then you'll notice that the player <span class="math-container">$\beta$</span> has a winning strategy. For any <span class="math-container">$d=4$</span> points on a plane, there is always a subset such that player <span class="math-container">$\alpha$</span> is unable to draw a required circle. ( I don't want to go into the detailed proof of the strategy - it is straightforward, but cumbersome - I've sketched it <a href="https://ai.stackexchange.com/a/27756/20538">my other answer</a>). If we now change the number of points to <span class="math-container">$d=3$</span> then the game suddenly becomes winnable by player <span class="math-container">$\alpha$</span> - for three points that are not on the same line any subset can be separated by a circle.</p>
  <p>The largest number <span class="math-container">$d$</span> at which the game is winnable by player <span class="math-container">$\alpha$</span> is called the VC dimension of our classification set. So, in the case of 2D discs (insides of a circle) the VC dimension is 3. If one changes the rules to use rectangles instead of circles, then the maximum number of points winnable by <span class="math-container">$\alpha$</span> would be 4 - thus, the VC dimension of rectangular classification sets is 4.</p>
  <p>Restoring our the mathematical notation, we denote <span class="math-container">$\mathcal{X} = \mathbb{R}^2$</span> our two-dimensional plane. <span class="math-container">$C$</span> is the subset of cardinality <span class="math-container">$|C| = d$</span> that the player <span class="math-container">$\alpha$</span> selects. And <span class="math-container">$\mathcal{H}$</span> is a class (a &quot;set-of-sets&quot;) of the subsets of <span class="math-container">$\mathcal{X}$</span> that one should use as a classification boundary.  Formally, the statement that the game above is winnable by <span class="math-container">$\alpha$</span>  can be written as:</p>
  <p><span class="math-container">$$ \exists\;C\subset\mathcal{X}.|C|=d \Rightarrow\forall\; A\subset C\; \exists\; B\in\mathcal{H}\;. A = B\,\cap\,A  $$</span></p>
  <p>The maximal <span class="math-container">$d$</span> at which this statement is true would be the VC dimension. (I actually worked backwards from noticing the alternating quantifiers <span class="math-container">$\exists\,\forall\,\exists$</span> in the VC definition - which is typical in game playing, so I worked back from the definition to make the game above.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-12T08:09:32.213Z
Answers.Text: I think both your answers would benefit from having images of the _disks_ (the "models" in our context) and the points that we want to classify (some configuration of the points you already show in the other answer), although they will be longer. In any case, this answer is interesting.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-11T23:21:38.350Z
Answers.LastActivityDate: 2021-05-12T08:00:50.753Z
Answers.LastEditDate: 2021-05-12T08:00:50.753Z
Answers.UserDisplayName: Kostya
Answers.Body: <p>This may be lacking some rigour, but this is how I have explained it in the past:</p>
  <blockquote>
  <p>The VC Dimension is the maximum number of inputs such that for any
  subset of these inputs, it is possible for the model to classify the
  subset as true and the rest as false.</p>
  </blockquote>
  <p>I am aware that this definition still uses the term subset, but in my experience even people who are not familiar with set theory understand the concept of a subset.</p>
  <p>The part about this that tends to confuse most people is the notion of a subset unable to be induced by a model. This can be nicely illustrated by picking a really simply hypothesis, such as a closed interval, and showing how  it cannot express non-contiguous positive inputs, or using a linear classifier and showing how it cannot express XOR.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-11T16:43:48.097Z
Answers.Text: This answer is not really what I was looking for. I was looking for an answer that is rigorous but intuitive, i.e. an answer with an illustration of an example that is described in detail. So, it's ok to just stick to an example to explain the concept, but here you're talking about other concepts (which I personally know, but not everyone will), such as the closed-interval example, but just mentioning them. I also don't think your definition is correct. You're allowed to rearrange the points, but the model should classify them correctly for **any** possible labelling.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-11T16:45:50.030Z
Answers.Text: So, what I was looking for was, _for example_, a detailed description of the XOR and how a line cannot solve it (in that example, you would describe what $H$, $C$ and $X$ are, and what it means to shatter, etc.)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-11T16:08:33.583Z
Answers.LastActivityDate: 2021-05-11T16:08:33.583Z
Answers.UserDisplayName: chessprogrammer
Body: <p>The VC dimension is a very important concept in computational/statistical learning theory. However, the first time you read its definition, you may not immediately understand what it really represents or means, as it involves other concepts, such as <em>shattering</em>, <em>hypothesis class</em>, <em>learning</em> and sets. For example, let's take a look at <a href="https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=70" rel="nofollow noreferrer">the definition given by Shai Shalev-Shwartz and Shai Ben-David (p. 70)</a></p>
  <blockquote>
  <p>DEFINITION <span class="math-container">$6.5$</span> (VC-dimension) The VC-dimension of a hypothesis class <span class="math-container">$\mathcal{H}$</span>, denoted <span class="math-container">$\operatorname{VCdim}(\mathcal{H})$</span>, is the maximal size of a set <span class="math-container">$C \subset \mathcal{X}$</span> that can be shattered by <span class="math-container">$\mathcal{H}$</span>. If <span class="math-container">$\mathcal{H}$</span> can shatter sets of arbitrarily large size we say that <span class="math-container">$\mathcal{H}$</span> has infinite VC-dimension.</p>
  </blockquote>
  <p>Without knowing what a hypothesis class is, or what the specific <span class="math-container">$C$</span>, <span class="math-container">$X$</span> and <span class="math-container">$H$</span> in this definition are, it's difficult to understand this definition. Even if you are familiar with what a hypothesis class is (i.e. a set of sets, i.e. our set of functions/hypotheses/models, e.g. the set of all possible neural networks with a specific topology) and you know that <span class="math-container">$C$</span> and <span class="math-container">$X$</span> are sets of input points, it should still not be clear what the VC dimesion really is or represents.</p>
  <p>So, how would you intuitively and rigorously explain the exact definition of the VC dimension?</p>
  <p>Note that I am not asking for answers like</p>
  <blockquote>
  <p>The VC dimension represents the <em>complexity</em> (or <em>expressive power, richness</em>, or <em>flexibility</em>) of your model/hypothesis class.</p>
  </blockquote>
  <p>Of course, this is easy to memorize, but it's quite vague. So, I am <strong>not</strong> looking for vague/general answers. I am looking for answers that rigorously but intuitively describe the mathematical definition of the VC dimension. For example, you could provide an <strong>illustration</strong> that shows what the VC dimension is, and, in your <em>example</em> (e.g. the XOR problem cannot be solved by a set of lines), you can describe what <span class="math-container">$H$</span>, <span class="math-container">$C$</span>, and <span class="math-container">$X$</span> are, and how they relate to the typical concepts you will find an introductory course to machine learning, but you should not forget to describe the concept of <em>shattering</em>. If you have other ideas of how to illustrate this concept memnomically, feel free to provide an answer.</p>
  
Tags: <machine-learning><definitions><computational-learning-theory><vc-dimension>
Title: How would you intuitively but rigorously explain what the VC dimension is?
UserDisplayName: nbro
ThreadText: # How would you intuitively but rigorously explain what the VC dimension is?
  
  (Asked by: username_0 on 2021-05-11)
  
  The VC dimension is a very important concept in computational/statistical learning theory. However, the first time you read its definition, you may not immediately understand what it really represents or means, as it involves other concepts, such as *shattering*, *hypothesis class*, *learning* and sets. For example, let's take a look at [the definition given by Shai Shalev-Shwartz and Shai Ben-David (p. 70)](https://www.cs.huji.ac.il/%7Eshais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=70)
  
  > DEFINITION $6.5$ (VC-dimension) The VC-dimension of a hypothesis class $\mathcal{H}$, denoted $\operatorname{VCdim}(\mathcal{H})$, is the maximal size of a set $C \subset \mathcal{X}$ that can be shattered by $\mathcal{H}$. If $\mathcal{H}$ can shatter sets of arbitrarily large size we say that $\mathcal{H}$ has infinite VC-dimension.
  
  Without knowing what a hypothesis class is, or what the specific $C$, $X$ and $H$ in this definition are, it's difficult to understand this definition. Even if you are familiar with what a hypothesis class is (i.e. a set of sets, i.e. our set of functions/hypotheses/models, e.g. the set of all possible neural networks with a specific topology) and you know that $C$ and $X$ are sets of input points, it should still not be clear what the VC dimesion really is or represents.
  
  So, how would you intuitively and rigorously explain the exact definition of the VC dimension?
  
  Note that I am not asking for answers like
  
  > The VC dimension represents the *complexity* (or *expressive power, richness*, or *flexibility*) of your model/hypothesis class.
  
  Of course, this is easy to memorize, but it's quite vague. So, I am **not** looking for vague/general answers. I am looking for answers that rigorously but intuitively describe the mathematical definition of the VC dimension. For example, you could provide an **illustration** that shows what the VC dimension is, and, in your *example* (e.g. the XOR problem cannot be solved by a set of lines), you can describe what $H$, $C$, and $X$ are, and how they relate to the typical concepts you will find an introductory course to machine learning, but you should not forget to describe the concept of *shattering*. If you have other ideas of how to illustrate this concept memnomically, feel free to provide an answer.
  
  **Tags:** machine-learning, definitions, computational-learning-theory, vc-dimension
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2021-05-11. Score: 3
  
  **Shattered set.** First we need a concept of a shattered set. I'll work from a shattered set [example in Wikipedia](https://en.wikipedia.org/wiki/Shattered_set#Example) adjusting it to your notation.
  
  The statement that $\mathcal{H}$ shatters $C$ means that for every subset $A \subset C$ there is a set $B\in\mathcal{H}$ such that $B$ "separates" $A$ from $C \backslash A$. Writing this formally:
  
  $$\text{shatters}(\mathcal{H},C) = \forall A \subset C\; \exists B\in\mathcal{H}\;.\;A = B\,\cap A $$
  
  As an example consider the set $C$ of four points on $\mathcal{X} = \mathbb{R}^2$:
  
  $$C = \left\{(0,0); (0,1); (1,0); (1,1)\right\}$$
  
  And the classification class $\mathcal{H}$ being all possible 2D discs on $\mathcal{X} =\mathbb{R}^2$. (Notice that people use the world "[class](https://en.wikipedia.org/wiki/Class_(set_theory))" here, because we are dealing with "set-of-sets" stuff and that might get [tricky](https://en.wikipedia.org/wiki/Class_(set_theory)#Paradoxes)). Note that a disk can be represented as the set of all points inside the circle.
  
  Now, it turns out that this $\mathcal{H}$ doesn't shatter $C$. The counterexample would be the subset $A$ of "diagonal" points:
  
  $$A = \left\{(0,0); (1,1)\right\} \subset C$$
  
  There is no 2D disk $B\in\mathcal{H}$ (in the context of learning theory, an element/set of the hypothesis class is a *hypothesis*, which can also be viewed as a function) that satisfies $A = B\,\cap A$. Intuitively, this means that you cannot use a 2D disk to classify your pair of points $A$ from the rest of the set $C$.
  
  **The [VC dimension](https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension)** of $\mathcal{H}$ is the maximal cardinality $d$ of the set $C$ that it can shatter. For $d=3$, we can provide tree points $C'$ for which we can easily find all discs that cover all eight possible subsets of $C'$:
  
  $$C' = \left\{(0,0); (0,1); (1,0)\right\}$$
  
  Above we've shown that for a particular set $C$ of $d=4$ points $\text{shatters}(\mathcal{H}, C)$ is false. But we need to prove that it is false *for all 4-point sets*. To prove this, we consider a convex hull of an arbitrary set of four points $C = \left\{a;b;c;d\right\}$. In general position, the convex hull is either a triangle or a quad:
  
  [![enter image description here](https://i.sstatic.net/Igk5q.png)](https://i.sstatic.net/Igk5q.png)
  
  In the case of a triangle, we choose the outermost three points as a counterexample set $A$. So, with this (labeling) configuration, you cannot find a disk that covers (i.e. classifies) the outermost three points correctly while excluding the point inside the triangle. In the case of a quad, we choose the pair on the longest diagonal. If any three points lay on a single line, then we choose the pair of outermost points.
  
  This sketches a proof that no $d=4$ point set can be shattered by $\mathcal{H}$, but we've shown that there is a $d=3$ set $C'$ that can be. Concluding that $VCdim(\mathcal{H}) = 3$
  
  **Another example** is considered on the next page (pg. 71) of the book you've referenced. It again considers 2D plane $\mathcal{X} =\mathbb{R}^2$ and the classification class $\mathcal{H}$ is all possible axis-aligned rectangles. Authors show a configuration $C$ of four points that can be shattered by $\mathcal{H}$ on the left of figure 6.1. And then provide a proof that no $d=5$ points can be shattered by axis-aligned rectangles. Concluding that VC dimension of their $\mathcal{H}$ is four.
  
  Hope these examples help. (BTW, note that, it seems [that Deep Learning has quite bad VC dimension](https://cs.stackexchange.com/questions/75327/why-is-deep-learning-hyped-despite-bad-vc-dimension) but it still works somehow - which is rather puzzling).
  
  > **Comments:**
  > **username_0**: Regarding the VC dimension of neural networks, I am not really an expert in this topic, but you may be interested in [my answer here](https://ai.stackexchange.com/a/17881/2444). Essentially, as far as I know, the VC dimension of neural networks is often expressed as a bound rather than a specific number. Given it's often a loose bound, the actual VC dimension may be actually quite big.  
  > **username_0**: Moreover, the adversarial examples show that neural networks can actually be fooled. I need to think about how the VC dimension is related to this (I suspect that we are estimating the expected risk is the wrong way), but I think it's misleading to say that "VC dimension of neural networks is low, but neural networks 'work', so the VC dimension is useless", which is a conclusion I've already heard (just to clarify, I had already come across that post on CS SE).  
  
  ---
  
  ### Answer by username_1 on 2021-05-11. Score: 3
  
  Trying to explain the idea of VC to some of my colleagues I've discovered quite an intuitive way of laying out the basic idea. Without going through lots of math and notation as I've done in [my other answer](https://ai.stackexchange.com/a/27756/20538).
  
  Imagine a following game between two players $\alpha$ and $\beta$ :
  
  1. First, player $\alpha$ plots $d=4$ points on a piece of paper. She may place the points however she likes.
  2. Next, player $\beta$ marks several of the drawn points.
  3. Finally, player $\alpha$ should draw a circle such that all the marked points are inside the circle, and all the unmarked points - outside. (Points on the boundary considered "inside".)
  
  The player $\alpha$ wins if she can draw such a circle at step #3. The player $\beta$ wins if making such circle is impossible.
  
  If you try to analyze this game then you'll notice that the player $\beta$ has a winning strategy. For any $d=4$ points on a plane, there is always a subset such that player $\alpha$ is unable to draw a required circle. ( I don't want to go into the detailed proof of the strategy - it is straightforward, but cumbersome - I've sketched it [my other answer](https://ai.stackexchange.com/a/27756/20538)). If we now change the number of points to $d=3$ then the game suddenly becomes winnable by player $\alpha$ - for three points that are not on the same line any subset can be separated by a circle.
  
  The largest number $d$ at which the game is winnable by player $\alpha$ is called the VC dimension of our classification set. So, in the case of 2D discs (insides of a circle) the VC dimension is 3. If one changes the rules to use rectangles instead of circles, then the maximum number of points winnable by $\alpha$ would be 4 - thus, the VC dimension of rectangular classification sets is 4.
  
  Restoring our the mathematical notation, we denote $\mathcal{X} = \mathbb{R}^2$ our two-dimensional plane. $C$ is the subset of cardinality $|C| = d$ that the player $\alpha$ selects. And $\mathcal{H}$ is a class (a "set-of-sets") of the subsets of $\mathcal{X}$ that one should use as a classification boundary. Formally, the statement that the game above is winnable by $\alpha$ can be written as:
  
  $$ \exists\;C\subset\mathcal{X}.|C|=d \Rightarrow\forall\; A\subset C\; \exists\; B\in\mathcal{H}\;. A = B\,\cap\,A $$
  
  The maximal $d$ at which this statement is true would be the VC dimension. (I actually worked backwards from noticing the alternating quantifiers $\exists\,\forall\,\exists$ in the VC definition - which is typical in game playing, so I worked back from the definition to make the game above.)
  
  > **Comments:**
  > **username_0**: I think both your answers would benefit from having images of the _disks_ (the "models" in our context) and the points that we want to classify (some configuration of the points you already show in the other answer), although they will be longer. In any case, this answer is interesting.  
  
  ---
  
  ### Answer by username_2 on 2021-05-11. Score: 0
  
  This may be lacking some rigour, but this is how I have explained it in the past:
  
  > The VC Dimension is the maximum number of inputs such that for any
  > subset of these inputs, it is possible for the model to classify the
  > subset as true and the rest as false.
  
  I am aware that this definition still uses the term subset, but in my experience even people who are not familiar with set theory understand the concept of a subset.
  
  The part about this that tends to confuse most people is the notion of a subset unable to be induced by a model. This can be nicely illustrated by picking a really simply hypothesis, such as a closed interval, and showing how it cannot express non-contiguous positive inputs, or using a linear classifier and showing how it cannot express XOR.
  
  > **Comments:**
  > **username_0**: This answer is not really what I was looking for. I was looking for an answer that is rigorous but intuitive, i.e. an answer with an illustration of an example that is described in detail. So, it's ok to just stick to an example to explain the concept, but here you're talking about other concepts (which I personally know, but not everyone will), such as the closed-interval example, but just mentioning them. I also don't think your definition is correct. You're allowed to rearrange the points, but the model should classify them correctly for **any** possible labelling.  
  > **username_0**: So, what I was looking for was, _for example_, a detailed description of the XOR and how a line cannot solve it (in that example, you would describe what $H$, $C$ and $X$ are, and what it means to shatter, etc.)  
  
  ---
  
  