Tag Info

3

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

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

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 or bound that quantifies the size (or richness) of the hypothesis space, i.e. the number (and type) of functions that can be represented by the hypothesis space. ...

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

1

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 that you can design an algorithm that can find a function (or concept) that is arbitrarily close to your target (or desired) function. This is not really an ...

1

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$. The hypothesis space consists of the set of functions the model is limited to learn. For instance, linear regression can be limited to linear functions as its ...

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