Questions tagged [vc-theory]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2 votes
0 answers

VC Dimensions in Machine Learning

Hello I'm learning about VC dimensions in machine learning. The class of classifiers $H$ where $h \in H$ if $h \in \mathbb{R} \rightarrow \{0,1\}$ is what I believe is simply binary classifiers (with ...
M. Fire's user avatar
  • 21
2 votes
0 answers

Find VC dimension

I'm studying theoretical machine learning at university, and I have this problem in textbook, that I have no Idea how to start. In space $X=R^2$ are given two models $H_1$ (rectangle with sides ...
user779537's user avatar
2 votes
0 answers

Intuition behind Occam's Learner Algorithm using VC-Dimension

So I'm learning about Occam's Learning algorithm and PAC-Learning where for a given hypothesis space $H$, if we want to have a model/hypothesis $h$ that has an True error of $error_D \leq \epsilon$, ...
JoeVictor's user avatar
  • 101
2 votes
0 answers

How to determine the VC Dimension of axis-aligned, origin-centered ellipses?

I've been trying to determine the VC dimension of ellipses which are origin centered and axis aligned. My first approach was to find some equivalence to a threshold classifier function family of the ...
AlexFink's user avatar
1 vote
0 answers

Find VC dimension of 1D data

Tuhin Dutta's user avatar
0 votes
1 answer

VC- dimension calculate

Let X = {1, 2, 3, ... , 100}. Let H be the class of all subsets of X that contain at least 20 and at most 80 elements. What is the VC-dimension of H?
tomkeruse's user avatar
0 votes
0 answers

VC Dimension of a Countably Infinite Class

I know that there are many examples of classes where the VC Dimension is finite/infinite even though the size of the class is Uncountably Infinite. However, I could not argue if the VC Dimension of a ...
Chen Reddy Sundeep's user avatar
0 votes
0 answers

Growth function of the class of all circles in the plane

I know that the VC dimension for this problem is 3. My concern is about the growth function. The following bound is obtained using the VC dimension: $$m_{\mathcal{H}}(n)\le \sum_{k=0}^3\,{n\choose k}$$...
Ali Kara's user avatar