# Questions tagged [vc-dimension]

The VC dimension (for Vapnik–Chervonenkis dimension) is a measure of the capacity (complexity, expressive power, richness, or flexibility) of a statistical classification algorithm, defined as the cardinality of the largest set of points that the algorithm can shatter.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
83 views

1 vote
279 views

### VC Dimension of A Set of Hypothesis

I am confused about what does a VC dimension of a set of hypothesis means. I have two hypothesis, say $H_1$ with VC dimension of $x$, and $H_2$ of VC dimension of $y$. Does this automatically mean ...
1 vote
200 views

### Sample Complexity for Real-Valued PAC-Learnable Functions

Can anyone shed some light on how the VC Dimension affects the sample complexity bounds of infinite hypothesis classes with real-valued outputs in PAC learning, or how to calculate the sample ...
1 vote
193 views

### If one hypothesis class is a proper subset of another, what is the relation of their VC dimensions?

Assume two hypotheses classes $H_A\subset H_B$ defined over the same instance space $\delta$. Assume also $VC(H_A)=d$, does this mean $VC(H_B)\geq d$ ? where $VC$ is the VC dimension. We can use the ...
1 vote
228 views

### VC dimension of 1-NN classifier for discrete metric space?

We know VC dimension of 1-NN classifier is infinite for continuous metric space. Is there any proof of VC dimension of 1-NN classifier if the metric space is discrete?
40 views

Hello everyone I am new to the site, I have a question that was in the test and did not understand the parts that are in the question. This question from a test I failed to pass, in a machine learning ...
144 views

### VC dimension of a combination of two hypothesis classes

I have found this exercise and I cannot solve it: In $X=\mathbb R^2$, let's observe two models $H_1$ (rectangle with sides parallel to the coordinate axes) and $H_2$ (lines). We define a model $H_3$ ...
This is a problem of VC that I've been trying to solve. Any help is appreciated. Let's assume hypothesis classes $H_{\mathit{init}}$ of initial segments over domain $X = \mathbb R$ and \$H_{\mathit{...