7 votes

How to estimate the capacity of a neural network?

VC dimension A rigorous measure of the capacity of a neural network is the VC dimension, which is intuitively a number or bound that quantifies the difficulty of learning from data. The sample ...
nbro's user avatar
  • 40.2k
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 ...
nbro's user avatar
  • 40.2k
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,816
3 votes

How would you intuitively but rigorously explain what the VC dimension is?

Trying to explain the idea of VC to some of my colleagues I've discovered quite an intuitive way of laying out the basic idea. Without going through lots of math and notation as I've done in my other ...
Kostya's user avatar
  • 2,516
3 votes

How would you intuitively but rigorously explain what the VC dimension is?

Shattered set. First we need a concept of a shattered set. I'll work from a shattered set example in Wikipedia adjusting it to your notation. The statement that $\mathcal{H}$ shatters $C$ means that ...
Kostya's user avatar
  • 2,516
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
3 votes
Accepted

Are there any rules of thumb for having some idea of what capacity a neural network needs to have for a given problem?

Theoretical results Rather than providing a rule of thumb (which can be misleading, so I am not a big fan of them), I will provide some theoretical results (the first one is also reported in paper How ...
nbro's user avatar
  • 40.2k
2 votes

Are there any rules of thumb for having some idea of what capacity a neural network needs to have for a given problem?

This may sound counter intuitive but one of the biggest rules of thumb for model capacity in deep learning: IT SHOULD OVERFIT. Once you get a model to overfit, its easier to experiment with ...
mshlis's user avatar
  • 2,359
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,816
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}{...
OmG's user avatar
  • 1,816
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 ...
OmG's user avatar
  • 1,816
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.2k
1 vote

Why was the VC dimension not defined for all configurations of $d$ points?

The measure that you are talking about actually has a name. It is called the "Popper dimension" -- it was introduced by Karl Popper in his "Logic of scientific discovery". Popper's ...
Kostya's user avatar
  • 2,516
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 ...
nbro's user avatar
  • 40.2k
1 vote

How can neural networks approximate any continuous function but have $\mathcal{VC}$ dimension only proportional to their number of parameters?

VC Dimension of Neural Networks establishes VC bounds depending on the number of weights, whereas the UAT refers to a class of neural networks in which the number of weights a particular network can ...
Dani's user avatar
  • 36
1 vote

How does the number of stacked LSTM layers or units in each layer affect the model complexity?

In computational learning theory, the VC dimension is a formal measure of the capacity of a model. The VC dimension is defined in terms of the concept of shattering, so have a look at the related ...
nbro's user avatar
  • 40.2k

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