# Tag Info

7

Although I have only partially read (or not read at all) some of the following resources and some of these resources may not cover more advanced topics than the ones presented in the book you are reading, I think they can still be useful for your purposes, so I will share them with you. I would also like to note that if you understand the contents of the ...

6

Generalization error is the error obtained by applying a model to data it has not seen before. So, if you want to measure generalization error, you need to remove a subset from your data and don't train your model on it. After training, you verify your model accuracy (or other performance measures) on the subset you have removed since your model hasn't seen ...

5

Introduction The paper Generalization in Deep Learning provides a good overview (in section 2) of several results regarding the concept of generalisation in deep learning. I will try to describe one of the results (which is based on concepts from computational or statistical learning theory, so you should expect a technical answer), but I will first ...

4

As far as I know, the sigmoid is often used as the activation function of the output layer mainly because it is a convenient way of producing an output $p \in [0, 1]$, which can be interpreted as a probability, although that can be misleading or even wrong (if you interpret it as an uncertainty too). You may require the output of the neural network to be a ...

4

There is no contradiction. First, agnostic PAC learnable doesn't mean that the there is a good hypothesis in the hypothesis class; it just means that there is an algorithm that can probably approximately do as well as the best hypothesis in the hypothesis class. Also, these NFL theorems have specific mathematical statements, and hypothesis classes for ...

3

Computational learning theory (CLT) is devoted to the mathematical and computational analysis of machine learning algorithms, so it is concerned with the learnability (i.e. generalization, bounds, efficiency, etc.) of certain tasks, given a learner (or a learning algorithm), a hypothesis space, data, etc. CLT can be divided into (at least) two subfields: ...

3

The VC dimension The most common and 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 ...

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

Well, there are some questions here... Does it (Deep Learning) try to learn a continuous distribution based on the training-set and its corresponding mappings, and map unseen examples from this learned distribution? Yes. Talking about Deep Artificial Neural Networks, they try to learn continuous distribution using continuous activation functions in each ...

3

Consider a continuum of complexity in models. Trivial: $y = x + a$ Simple: $y = x \, \log \, (a x + b) + c$ Moderately complex: A wind turbine under constant wind velocity Very complex: Ray tracing of lit 3-D motion scenes to pixels Astronomically complex: The weather Now consider a continuum regarding the generality or specificity of models. Very ...

3

Multilayer Perceptron (MLP) can theoretically approximate any bounded, continuous function. There's no guarantee for a discontinuous function. There are plenty of important discontinuous functions, like, say, the prime counting function. The prime counting function pi(n) is simply equal to the number of primes less than or equal to n. It has a discontinuity ...

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

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

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$$ that $R$ is test error, $R_{emp}$ is training error, $m$ is the size of the training ...

2

To answer this, it's helpful to consider the notion of a neural network architecture – in this context, we can think of the architecture as being the network depth (i.e. number of layers), width (i.e. number of nodes in a layer), and some other structural aspects, such as recurrent layers, convolution layers, pool layers, etc. Theory In terms of the ...

2

While I'm not familiar with any explicit statements regarding what a Multilayer Perceptron (MLP) cannot learn, I can provide some further detail on the positive statements you made about MLP capabilities: A MLP with a single hidden layer is capable of what is commonly termed 'Universal Function Approximation', i.e. it can approximate any bounded continuous ...

2

Definitely, you can find the proof in different resources (for example, in these notes or in the paper that originally proposed PAC learnability, A Theory of the Learnable). However, the intuition behind your question is when the size of the hypothesis increases, if you do not change anything, you can't see more part of the space. Hence, the estimation error ...

2

A neural network is composed of continuous functions. Neural networks are regularized by adding an l2 penalty on the weights to the loss function. This means the neural network will try to make the weights as small as possible. The weights are also initiallized with a N(0, 1) distribution so the initial weights will also tend to be small. All of this means ...

2

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. I will be updating this answer, as I find more ...

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 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 ... 2 Section 5.2 Error Decomposition of the book Understanding Machine Learning: From Theory to Algorithms (2014) gives a description of the approximation error and estimation error in the context of empirical risk minimization (ERM), so in the context of learning theory. I will just summarise their definition. If you want to know more about these topics, I ... 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 the definition, \mathcal V \mathcal C dimension of \mathcal H over domain X is d=2. Although, A = \{3\} \subset X, whose size is smaller than the \mathcal V \mathcal C dimenion i.... 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 ... 1 The formula G=\mathbb{E}\left[ f(Z_{T+1}) \mid \mathbf{Z}_1^T\right] - \sum_{t=1}^Tq_t \mathbb{E}\left[ f(Z_t) \mid \mathbf{Z}_1^{t-1} \right] actually represents a set, for all possible values of f. Therefore, \text{disc}(\mathbf{q}) = \operatorname{sup}_{f \in \mathcal{F}} \left( \mathbb{E}\left[ f(Z_{T+1}) \mid \mathbf{Z}_1^T\right] - \sum_{t=1}^Tq_t ... 1 Most methods for measuring the complexity of neural networks are fairly crude. One common measure of complexity is VC dimension, a discussion which can be found here and here. For example, neural networks have a VC dimension that is too large to give a strong upper bound on the number of training samples needed for a model (the upper bound provided by VC ... 1 @nbro has already provided a great answer, so i'll just supplement his answer with two specific results: Minsky, in his 1969 book Perceptrons provided a mathematical proof that showed that certain types of neural networks (then called perceptrons) weren't able to compute a function called the XOR function, thus showing that the mind couldn't be implemented ... 1 A hypothesis is a statement that suggests an as yet unproven explanation of a relationship between two or more phenomena that you intend to test. An agronomist thinks that more nitrogen on canola will always increase the crop output$$Harvest = f(N), or a meteorologist thinks he can show that the path of a hurricane over the ocean can be determined by ...

1

The number of dichotomies of 4 data points will clearly be $2^4 = 16$. According to these slides the definition of dichotomy in context of Statistical Learning is: Different ‘hypotheses’ over the finite set of $N$ input points. Which basically means hypotheses with unique behaviours over the input points. Two or more different hypotheses can have same ...

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