Answers.Body: <p>You can look at the VC-Dimension like a measure of <em>capacity</em> (like richness, expressive power, flexibility, complexity) of the hypotesis space <span class="math-container">$H$</span> of a model: with it, we can extend the PAC Analysis to problems having infinite hypotesis space.</p>
  <p>Intuitively, you can think about <span class="math-container">$VC(H)$</span> as the cardinality of the largest set of points (your instance space <span class="math-container">$X$</span>) the algorithm itself can <a href="https://en.wikipedia.org/wiki/Shattered_set" rel="nofollow noreferrer">shatter</a>. This special ability the algorithm has is strictly connected to the concept of inductive bias embedded in <span class="math-container">$H$</span>. That's the neat part: why?</p>
  <p>Imagine having a bias-free learner, i.e. a learner that makes no real prior assumptions about the target concept: obviously there won't be any rationale behind its classification of new, unseen instances.
  Injecting the inductive bias, we are effectively converting our learner into a <em>deductive</em> system, one thatjumps to logical <em>conclusions</em> entailed by the <em>premises</em> of our training examples from the assumed hypotesis in H. Now the learner can define a new policy for generalising beyond observed data in a non-procedural way starting from what he learnt about the training examples.</p>
  <p>Now: an unbiased <span class="math-container">$H$</span> is one that shatter the instance space <span class="math-container">$X$</span>, but we want a biased <span class="math-container">$H$</span>, so we are almost certainly losing the power to shatter the whole instance space <span class="math-container">$X$</span>.</p>
  <p>But what about a <span class="math-container">$Q \subset X$</span>? Moreover, given that the learner can shatter this subset <span class="math-container">$Q$</span> of <span class="math-container">$X$</span>, what does it can tell us about <span class="math-container">$H$</span>? Surely we can say that the expressiviness of <span class="math-container">$H$</span> is directly proportional to the <em>size</em> of <span class="math-container">$Q$</span>, i.e. how large <span class="math-container">$Q$</span> is. How do we measure this expressiviness?</p>
  <p>With VC-Dimension. That's it: <span class="math-container">$VC(H)$</span> is, for <span class="math-container">$H$</span> defined over <span class="math-container">$X$</span>, the size of the largest finite subset <span class="math-container">$Q \subset X$</span>  that can be shattered by <span class="math-container">$H$</span>.</p>
  <p>Two details:</p>
  <ol>
  <li>If the size of <span class="math-container">$Q$</span> is arbitrarily large and still <span class="math-container">$H$</span> can shatter it, then <span class="math-container">$VC(H) = \infty$</span></li>
  <li>For any finite <span class="math-container">$H$</span>, <span class="math-container">$VC(H) \leq \log_2(|H|)$</span>, clearly because <span class="math-container">$H$</span> needs <span class="math-container">$2^n$</span> different hypoteses to shatter <span class="math-container">$n$</span> instances if <span class="math-container">$VC(H) = n$</span>, but it's not an upper bound: matter of fact, you can have <span class="math-container">$|H| \geq 2^n$</span>, that's why <span class="math-container">$log_2(|H|) \geq VC(H) = n$</span>.</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-04T23:04:42.607Z
Answers.LastActivityDate: 2024-06-04T23:07:08.350Z
Answers.LastEditDate: 2024-06-04T23:07:08.350Z
Answers.UserDisplayName: Nope
Body: <p>Courtesy link: <a href="https://ai.stackexchange.com/questions/27754/how-would-you-intuitively-but-rigorously-explain-what-the-vc-dimension-is">How would you intuitively but rigorously explain what the VC dimension is?</a></p>
  <blockquote>
  <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.  &gt; 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>
  </blockquote>
  <p><a href="https://link.springer.com/chapter/10.1007/978-3-030-83047-2_2" rel="nofollow noreferrer">This chapter discusses frameworks for analyzing learning algorithms, such as the Probably Approximately Correct (PAC) and Vapnik–Chervonenkis (VC) theories, with relevance to deep learning.</a></p>
  <p>How can I look at the VC-Dimension like a measure of capacity?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-06T11:27:41.527Z
Comments.Text: How is this question different from [the linked question](https://ai.stackexchange.com/q/27754/2444) (which I had asked a few years ago)?
Comments.UserDisplayName: nbro
Tags: <computational-learning-theory>
Title: What is the formula for $VC(H)$ in Computational Learning Theory?
UserDisplayName: Arunabh
ThreadText: # What is the formula for $VC(H)$ in Computational Learning Theory?
  
  (Asked by: username_0 on 2024-06-04)
  
  Courtesy link: [How would you intuitively but rigorously explain what the VC dimension is?](https://ai.stackexchange.com/questions/27754/how-would-you-intuitively-but-rigorously-explain-what-the-vc-dimension-is)
  
  > 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.)
  
  [This chapter discusses frameworks for analyzing learning algorithms, such as the Probably Approximately Correct (PAC) and Vapnik–Chervonenkis (VC) theories, with relevance to deep learning.](https://link.springer.com/chapter/10.1007/978-3-030-83047-2_2)
  
  How can I look at the VC-Dimension like a measure of capacity?
  
  **Tags:** computational-learning-theory
  
  > **Comments:**
  > **username_1**: How is this question different from [the linked question](https://ai.stackexchange.com/q/27754/2444) (which I had asked a few years ago)?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-06-04. Score: 2 | Accepted answer
  
  You can look at the VC-Dimension like a measure of *capacity* (like richness, expressive power, flexibility, complexity) of the hypotesis space $H$ of a model: with it, we can extend the PAC Analysis to problems having infinite hypotesis space.
  
  Intuitively, you can think about $VC(H)$ as the cardinality of the largest set of points (your instance space $X$) the algorithm itself can [shatter](https://en.wikipedia.org/wiki/Shattered_set). This special ability the algorithm has is strictly connected to the concept of inductive bias embedded in $H$. That's the neat part: why?
  
  Imagine having a bias-free learner, i.e. a learner that makes no real prior assumptions about the target concept: obviously there won't be any rationale behind its classification of new, unseen instances.
  Injecting the inductive bias, we are effectively converting our learner into a *deductive* system, one thatjumps to logical *conclusions* entailed by the *premises* of our training examples from the assumed hypotesis in H. Now the learner can define a new policy for generalising beyond observed data in a non-procedural way starting from what he learnt about the training examples.
  
  Now: an unbiased $H$ is one that shatter the instance space $X$, but we want a biased $H$, so we are almost certainly losing the power to shatter the whole instance space $X$.
  
  But what about a $Q \subset X$? Moreover, given that the learner can shatter this subset $Q$ of $X$, what does it can tell us about $H$? Surely we can say that the expressiviness of $H$ is directly proportional to the *size* of $Q$, i.e. how large $Q$ is. How do we measure this expressiviness?
  
  With VC-Dimension. That's it: $VC(H)$ is, for $H$ defined over $X$, the size of the largest finite subset $Q \subset X$ that can be shattered by $H$.
  
  Two details:
  
  1. If the size of $Q$ is arbitrarily large and still $H$ can shatter it, then $VC(H) = \infty$
  2. For any finite $H$, $VC(H) \leq \log\_2(|H|)$, clearly because $H$ needs $2^n$ different hypoteses to shatter $n$ instances if $VC(H) = n$, but it's not an upper bound: matter of fact, you can have $|H| \geq 2^n$, that's why $log\_2(|H|) \geq VC(H) = n$.
  
  
  ---
  
  