# Tag Info

## Hot answers tagged learning-theory

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

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

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

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

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

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

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

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

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

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

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 use continuous activation functions in each neuron, therefore, the output is ...

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

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

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

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

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

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\... 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 ... 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 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 ... 1 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. 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 @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 ...

1

This is a commonly used notation in theoretical computer science. $[m]$ is not the variable $m$, but is instead the set of integers from $1$ to $m$ inclusive. The empirical error equation thus reads in English: The cardinality of a set consisting of the elements $i$ of the set of integers $[m]$ such that the hypothesis given input $x_i$ disagrees with ...

1

Dempster-Shafer Theory was studied fairly seriously in AI through the 70's and 80's. However, Dempster-Shafer theory has some serious shortcomings, that will cause an agent that uses it to make irrational decisions. These were uncovered by Pearl and others in the 80's, with more problems emerging in later years. See Cheeseman for a summary of the arguments ...

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