Tag Info

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

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 ...
Accepted

• 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 ...
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