4
votes
Are PAC learning and VC dimension relevant to machine learning in practice?
Yes, PAC learning can be relevant in practice. There's an area of research that combines PAC learning and Bayesian learning that is called PAC-Bayesian (or PAC-Bayes) learning, where the goal is to ...
- 39.7k
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 ...
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,751
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 ...
- 39.7k
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,751
2
votes
Accepted
Understanding relation between VC Symmetrization Lemma and Generalization Bounds
Let $\varepsilon$ in (17) is equal to $\sqrt{\frac{4}{n}\left(\log{(2\mathsf{N}(\mathcal{F},n))}-\log{\delta}\right)}$. We have:
$$
P\left(\sup_{f\in\mathcal{F}}|R(f)-R_{emp}(f)| > \sqrt{\frac{4}{...
- 1,751
2
votes
Accepted
Is the VC Dimension meaningful in the context of Reinforcement Learning?
Yes, it is. This article (Approximate Planning in Large POMDPs via Reusable Trajectories) explain about it by means of the trajectory tree:
A trajectory tree is a binary tree in which each node is ...
- 1,751
1
vote
Accepted
Is there a measure of model complexity?
Yes. There are at least 2 measures of model complexity studied and used in learning theory: VC dimension and Rademacher complexity. If you're new to learning theory, you could take a look at this ...
- 39.7k
1
vote
Accepted
What do we mean by saying "VC dimension gives a LOOSE, not TIGHT bound"?
But, the literature (i.e. Learning from Data) states that VC gives a loose bound and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher ...
- 39.7k
1
vote
If a neural network is a universal function approximator, can it have any prior beliefs?
I think your deduction is mostly correct.
Neural networks of depth are universal function approximators. This means that in principal, for any function of the form you describe, there's a NN that ...
- 9,207
1
vote
Can feature engineering change the selection of the model according to the minimum description length?
I think the wrong assumption here is that you've forgotten the cost of encoding the new features!
MDL should be considered relative to the original or raw dataset. The idea is that you want to find ...
- 9,207
Only top scored, non community-wiki answers of a minimum length are eligible