Answers.Body: <p>In the first case, the VC dimension of <span class="math-container">$H$</span> being infinite implies that <span class="math-container">$H$</span> is not (agnostic) PAC learnable (<a href="https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=48" rel="nofollow noreferrer">see p. 48 of Understanding Machine Learning: From Theory to Algorithms</a>). So, in general, your classifier is not guaranteed to succeed.</p>
  
  <p>In the second case, your division of <span class="math-container">$H$</span> implies that <span class="math-container">$H$</span> is nonuniformly learnable (<a href="https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=83" rel="nofollow noreferrer">chapter 7 of the cited book</a>). This implies that you can get a generalization bound by using structural risk minimization.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T17:14:23.620Z
Answers.LastActivityDate: 2020-04-16T17:48:34.203Z
Answers.LastEditDate: 2020-04-16T17:48:34.203Z
Answers.UserDisplayName: Dani
Body: <p>I have the following scenario. I have a binary classification problem, whose underlying function is a step function. The probability distribution of feature vectors is a uniform over the domain.</p>
  
  <p>Case 1: I have a classifier which fits the training samples perfectly, no matter what the size of the data. The space of functions <span class="math-container">$H$</span> has an infinite VC dimension. As the data points going to infinite, the hypothesized function converges pointwise to the underlying step function.</p>
  
  <p>Case 2: Here I have divided the same hypothesis space into a number of hierarchical subspaces <span class="math-container">$H_1 \subset H_2 \subset H_3 \subset \dots \subset H_n$</span> (<span class="math-container">$n$</span> goes to infinity). The VC dimension of each of the spaces is finite and grows with <span class="math-container">$n$</span> to infinity. Now, given any data of <span class="math-container">$n$</span> points, I compute the minimum number of VC dimension required to fit the data exactly, say, <span class="math-container">$d_n$</span> and use that space <span class="math-container">$H_{d_n}$</span> as the hypothesis. Do the same as data size <span class="math-container">$n$</span> goes to infinity, at each <span class="math-container">$n$</span> using the hypothesis space that just enough VC dimension to fit the data. In this approach also, as the data size goes to infinity, the hypothesized function converges pointwise to the underlying step function.</p>
  
  <p><em>Is the difference between these two approaches to the same problem? Is there any theoretical difference? Which method is any better than others, in some sense?</em></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-16T13:12:08.067Z
Comments.Text: If the domain of $H$ continuous, you can't construct a countable order, as we know the $\mathbb{R}$ is not countable!
Comments.UserDisplayName: OmG
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-16T13:16:57.960Z
Comments.Text: @OmG : $H$ consists of certain class of functions defined on a $m$ dimensional Torus. The functions are of the form $\mathbb{T}^m \to \mathbb{R}$ with some other properties. There can be countable ordered subspaces.
Comments.UserDisplayName: Rajesh D
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-16T13:27:11.300Z
Comments.Text: You need to clear this part by a concrete example.
Comments.UserDisplayName: OmG
Tags: <machine-learning><classification><supervised-learning><computational-learning-theory><vc-dimension>
Title: An infinite VC dimensional space vs using hierarchical subspaces of finite but growing VC dimensions
UserDisplayName: Rajesh D
ThreadText: # An infinite VC dimensional space vs using hierarchical subspaces of finite but growing VC dimensions
  
  (Asked by: username_0 on 2020-04-16)
  
  I have the following scenario. I have a binary classification problem, whose underlying function is a step function. The probability distribution of feature vectors is a uniform over the domain.
  
  Case 1: I have a classifier which fits the training samples perfectly, no matter what the size of the data. The space of functions $H$ has an infinite VC dimension. As the data points going to infinite, the hypothesized function converges pointwise to the underlying step function.
  
  Case 2: Here I have divided the same hypothesis space into a number of hierarchical subspaces $H\_1 \subset H\_2 \subset H\_3 \subset \dots \subset H\_n$ ($n$ goes to infinity). The VC dimension of each of the spaces is finite and grows with $n$ to infinity. Now, given any data of $n$ points, I compute the minimum number of VC dimension required to fit the data exactly, say, $d\_n$ and use that space $H\_{d\_n}$ as the hypothesis. Do the same as data size $n$ goes to infinity, at each $n$ using the hypothesis space that just enough VC dimension to fit the data. In this approach also, as the data size goes to infinity, the hypothesized function converges pointwise to the underlying step function.
  
  *Is the difference between these two approaches to the same problem? Is there any theoretical difference? Which method is any better than others, in some sense?*
  
  **Tags:** machine-learning, classification, supervised-learning, computational-learning-theory, vc-dimension
  
  > **Comments:**
  > **username_1**: If the domain of $H$ continuous, you can't construct a countable order, as we know the $\mathbb{R}$ is not countable!  
  > **username_0**: @username_1 : $H$ consists of certain class of functions defined on a $m$ dimensional Torus. The functions are of the form $\mathbb{T}^m \to \mathbb{R}$ with some other properties. There can be countable ordered subspaces.  
  > **username_1**: You need to clear this part by a concrete example.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-04-16. Score: 0
  
  In the first case, the VC dimension of $H$ being infinite implies that $H$ is not (agnostic) PAC learnable ([see p. 48 of Understanding Machine Learning: From Theory to Algorithms](https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=48)). So, in general, your classifier is not guaranteed to succeed.
  
  In the second case, your division of $H$ implies that $H$ is nonuniformly learnable ([chapter 7 of the cited book](https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=83)). This implies that you can get a generalization bound by using structural risk minimization.
  
  
  ---
  
  