Skip to main content
3 votes
Accepted

How does size of the dataset depend on VC dimension of the hypothesis class?

From [1] we know that we have the following bound between the test and train error for i.i.d samples: $$ \mathbb{P}\left(R \leqslant R_{emp} + \sqrt{\frac{d\left(\log{\left(\frac{2m}{d}\right)}+1\...
OmG's user avatar
  • 1,826
3 votes

How does size of the dataset depend on VC dimension of the hypothesis class?

Given a hypothesis set $H$, the set of all possible mappings from $X\to Y$ where $X$ is our input space and $Y$ are our binary mappings: $\{-1,1\}$, the growth function, $\Pi_H(m)$, is defined as the ...
Archie Shahidullah's user avatar
2 votes
Accepted

How do I prove that $\mathcal{H}$, with $\mathcal{VC}$ dimension $d$, shatters all subsets with size less than $d-1$?

We can show that it is not true by a counterexample. For example, $X = \{1,2,3\}$ and $\mathcal H = \{\{\},\{1\},\{2\},\{1,2\}\}$ is the finite set hypothesis class. By definition, in this case, the $\...
OmG's user avatar
  • 1,826
2 votes

What is the difference between hypothesis space and representational capacity?

A hypothesis space/class is the set of functions that the learning algorithm considers when picking one function to minimize some risk/loss functional. The capacity of a hypothesis space is a number ...
nbro's user avatar
  • 40.9k
2 votes

How does size of the dataset depend on VC dimension of the hypothesis class?

The VC dimension represents the capacity (the same Vapnik, the letter V from VC, calls it the "capacity") of a model (or, in general, hypotheses class), so a model with a higher VC dimension has more ...
nbro's user avatar
  • 40.9k
1 vote
Accepted

Realizability Assumption: Why is that for every ERM hypothesis $L_{S}(h_{S})=0$

What I was missing is the condition in the definition: "S is labeled by a function $f$". Since $𝐿(\mathcal{𝐷},f)(ℎ^{\star})=0$ and $h^{\star}\in\mathcal{H}$, then for every ERM hypothesis $...
Tran Khanh's user avatar
1 vote
Accepted

Why any set of m data points with different features can be perfectly fit by a polynomial of degree n as long as n ≥ m

First, there's a mistake or typo in the quoted statement. The requirement should be $n \geq m-1,$ not $n \geq m.$ For instance, you can fit two points $(m=2)$ with a line $(n=1).$ Second, it's most ...
Justin Skycak's user avatar
1 vote

Is there any practical application of knowing whether a concept class is PAC-learnable?

Is there any practical application of knowing whether a concept class is PAC-learnable? If you know that a concept class is PAC-learnable (i.e. its VC dimension is finite), then there's a possibility ...
nbro's user avatar
  • 40.9k
1 vote
Accepted

What is the difference between hypothesis space and representational capacity?

Consider a target function $f: x \mapsto f(x)$. A hypothesis refers to an approximation of $f$. A hypothesis space refers to the set of possible approximations that an algorithm can create for $f$. ...
Saurav Joshi's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible