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 ...
nbro's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
BlindKungFuMaster's user avatar
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 ...
rcpinto's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
John Doucette's user avatar
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 ...
Anon's user avatar
  • 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. ...
Greenstick's user avatar
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. ...
a.kief's user avatar
  • 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 ...
JahKnows's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
Douglas Daseeco's user avatar
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 ...
Mark C. F. Sousa's user avatar
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 ...
nbro's user avatar
  • 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... ...
Dennis Soemers's user avatar
  • 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 ...
OmG's user avatar
  • 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, ...
bpachev's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
Archie Shahidullah's user avatar
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\...
OmG's user avatar
  • 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 ...
nbro's user avatar
  • 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 ...
Kostya's user avatar
  • 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 ...
Kostya's user avatar
  • 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 ...
Bruce Adams's user avatar
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 ...
NietzscheanAI's user avatar

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