10
votes
Accepted
What are some resources on computational learning theory?
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 ...
- 39.7k
7
votes
How to estimate the capacity of a neural network?
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 ...
- 39.7k
7
votes
Accepted
What's the difference between estimation and approximation error?
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 ...
- 39.7k
6
votes
Is there actually a lack of fundamental theory on deep learning?
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 ...
- 4,205
6
votes
Accepted
How can the generalization error be estimated?
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 ...
- 2,099
6
votes
Accepted
What are other examples of theoretical machine learning books?
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 ...
- 39.7k
6
votes
Accepted
How can I estimate how many photos I need to train ResNet-50 for image classification?
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 ...
- 39.7k
5
votes
Accepted
What are the state-of-the-art results on the generalization ability of deep learning methods?
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 ...
- 39.7k
5
votes
Accepted
What does "hard for AI" look like?
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 ...
- 9,207
5
votes
Accepted
Are PAC learnability and the No Free Lunch theorem contradictory?
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 ...
- 261
4
votes
Is there a way of converting a neural network to another one that represents the same function?
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. ...
- 416
4
votes
Is there actually a lack of fundamental theory on deep learning?
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.
...
- 181
4
votes
Is there actually a lack of fundamental theory on deep learning?
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 ...
- 470
4
votes
Are PAC learning and VC dimension relevant to machine learning in practice?
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 ...
- 39.7k
4
votes
Accepted
Mathematical foundations of the ability to learn
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 ...
- 39.7k
3
votes
Accepted
How do you distinguish between a complex and a simple model in machine learning?
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 ...
- 7,443
3
votes
Accepted
In deep learning, do we learn a continuous distribution based on the training dataset?
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 ...
3
votes
Accepted
What is the difference between a learning algorithm and a hypothesis?
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 ...
- 39.7k
3
votes
Will a neural network always predict the correct label if it sees the exact same input during training and testing?
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...
...
- 10.1k
3
votes
Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?
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 ...
- 1,751
3
votes
What are the learning limitations of neural networks trained with backpropagation?
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, ...
- 410
3
votes
Accepted
Can neural networks with a sigmoid as the activation function of the output layer approximate continuous functions?
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 ...
- 39.7k
3
votes
How does size of the dataset depend on VC dimension of the hypothesis class?
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 ...
3
votes
Accepted
How does size of the dataset depend on VC dimension of the hypothesis class?
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\...
- 1,751
3
votes
Accepted
How can a machine learning problem be reduced as a communication problem?
Information-theoretic view of Bayesian learning
I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?
Yes, this is ...
- 39.7k
3
votes
How would you intuitively but rigorously explain what the VC dimension is?
Shattered set. First we need a concept of a shattered set. I'll work from a shattered set example in Wikipedia adjusting it to your notation.
The statement that $\mathcal{H}$ shatters $C$ means that ...
- 2,426
3
votes
How would you intuitively but rigorously explain what the VC dimension is?
Trying to explain the idea of VC to some of my colleagues I've discovered quite an intuitive way of laying out the basic idea. Without going through lots of math and notation as I've done in my other ...
- 2,426
3
votes
To what extent are neural networks stable across multiple training runs?
If you want determinism make sure you program it in
A machine learning model will be deterministic to the same extent as any other computer program.
It is entirely based the stability of the inputs ...
- 223
2
votes
What are the learning limitations of neural networks trained with backpropagation?
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 ...
- 7,226
Only top scored, non community-wiki answers of a minimum length are eligible