5

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 complexity, which is the number of training instances that the model (or learner) must be exposed to in order to be reasonably certain of the accurateness of the ...


3

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\right)-\log{\left(\frac{\eta}{4}\right)}}{m}}\right) \geqslant 1-\eta $$ $R$ is the test error, $R_{emp}$ is the training error, $m$ is the size of the training ...


3

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 maximum number of dichotomies generated by $H$ on $m$ points. Here a dichotomy is the set of $m$ points in $X$ that represent a hypothesis. A hypothesis is just ...


3

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 find PAC-like bounds for Bayesian estimators. For example, Theorem 1 (McAllester’s bound) of the paper A primer on PAC-Bayesian learning (2019) by Benjamin ...


2

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 many hidden layers and nodes?), from which you may be able to derive your rules of thumb, depending on your problem, etc. Result 1 The paper Learning ...


2

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 regularizations, module replacements, etc. But in general, it gives you a good starting ground.


2

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}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \leqslant 2\mathcal{N}(\mathcal{F},n) e^{\frac{-n}{4}\left(\frac{4}{n}\left(\log{(2\...


2

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 $\mathcal{VC}$ dimension of $\mathcal H$ over the domain $X$ is $d=2$. Although $A = \{3\} \subset X$, whose size is smaller than the $\mathcal{VC}$ dimension, i....


2

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 capacity (i.e. it can represent more functions) than a model with a lower VC dimension. The VC dimension is typically used to provide theoretical bounds e.g. ...


2

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 labeled by a state and observation pair, and has a child for each of the two actions. Additionally, each link to a child is labeled by a reward, and the tree's ...


1

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 answer. Imagine a following game between two players $\alpha$ and $\beta$ : First, player $\alpha$ plots $d=4$ points on a piece of paper. She may place the ...


1

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 for every subset $A \subset C$ there is a set $B\in\mathcal{H}$ such that $B$ "separates" $A$ from $C \backslash A$. Writing this formally: $$\text{...


1

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 VC dimension. It's true that people often use techniques such as regularisation to avoid over-parametrized models. However, I think it's dangerous to say that,...


1

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 Wikipedia article, which briefly describes the fundamental concept of shattering. See also my answer to the question How to estimate the capacity of a neural ...


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