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\...
- 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 ...
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 $\...
- 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 ...
- 41.1k
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 ...
- 41.1k
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 $...
- 167
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 ...
- 126
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 ...
- 41.1k
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$. ...
- 189
Only top scored, non community-wiki answers of a minimum length are eligible