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


6

There is a paper called Why does Deep Learning work so well?. However, it is still not fully understood why deep learning works so well. In contrast to GOFAI (“good old-fashioned AI”) algorithms that are hand-crafted and fully understood analytically, many algorithms using artificial neural networks are understood only at a heuristic level, where we ...


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


5

Nice Question! This is a perennial topic of discussion among AI researchers. The short answer is "we don't really know which topics are hard in general, but we do know which we haven't got good techniques for yet." Let's start by explaining why AI is not concerned with notions of computational complexity like NP-Completeness. AI researchers figured out in ...


5

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


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


4

This is very much the case. Deep learning models even shallow ones such as stacked autoencoders and neural networks are not fully understood. There are efforts to understand what is happening to the optimization process for such a complex variable intensive function. But, this is a difficult task. One way that researchers are using to discover how deep ...


4

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


4

Computational learning theory (or just learning theory, abbreviated as CLT, COLT, or LT) 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. ...


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

What you want to calculate/estimate is known as the sample complexity in computational learning theory. If you knew the VC dimension of the neural network, you may be able to estimate the sample complexity, but your estimate (bound) may not be very tight anyway (maybe because the estimate of the VC dimension is also not tight). Here is more info about the VC ...


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

In computational learning theory, a learning algorithm (or learner) $A$ is an algorithm that chooses a hypothesis (which is a function) $h: \mathcal{X} \rightarrow \mathcal{Y}$, where $\mathcal{X}$ is the input space and $\mathcal{Y}$ is the target space, from the hypothesis space $H$. For example, consider the task of image classification (e.g. MNIST). You ...


3

No, Neural Networks do not have such a guarantee. In fact, I don't believe any kind of classifier in the entire field of Machine Learning has such a guarantee, though some may be slipping my mind... For an easy counterexample, consider what happens if you have two instances with precisely identical inputs, but different output labels. If your classifier is ...


3

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


3

It probably depends on what one means by "fundamental theory", but there is no lack of rigorous quantitative theory in deep learning, some of which is very general, despite claims to the contrary. One good example is the work around energy-based methods for learning. See e.g. Neal & Hinton's work on variational inference and free energy: http://www.cs....


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


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

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

Some of the books that you mention are often used as reference books in introductory courses to machine learning or artificial intelligence. For example, if I remember correctly, in my introductory course to machine learning, the professor suggested the book Pattern Recognition And Machine Learning (2006) by Bishop, although we never used it during the ...


3

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) and, in particular, in the context of the bias-complexity tradeoff (which is strictly related to the bias-variance tradeoff). 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 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

After training, all standard models are deterministic (the process each input goes thru is set). In essence, during training the model attempts to learn the distribution of the training dataset. Whether it is able to depends on the size of the model, if it is big enough, it can simply "memorize" all the training samples and result in perfect accuracy on ...


2

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


2

For standard NNs, their extrapolation behavior an important aspect for financial applications cannot be controlled due to complex functional forms typically involved. Neural Networks with Asymptotics Control discuss how they overcome this significant limitation and develop a new type of neural networks that incorporate large-value asymptotics, when known, ...


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


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