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


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


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

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

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

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

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

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 approximates it. However, a particular NN architecture of fixed width and depth, with fixed connections is not a universal approximator for all functions. Only ...


1

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 an expression you could send to someone else that encodes the structure of the dataset in terms of the original variables. If you define new features, you need ...


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