# Tag Info

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 ...
• 37.1k

### 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,127
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,059

### 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 ...
• 37.1k
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 ...
• 37.1k
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 ...
• 37.1k
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,037
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
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 ...
• 37.1k

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

### 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. ...
• 171

### 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 ...
• 460

### 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 ...
• 37.1k
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 ...
• 37.1k
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 ...
• 37.1k
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 ...
• 37.1k
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,385

### 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... ...
• 9,804
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 ...

### 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
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 ...
• 37.1k

### 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 ...
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,723

### 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,176

### What is the difference between hypothesis space and representational capacity?

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 ...
• 37.1k

### 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,723
Accepted

### What does the notation $[m]=\{1, \ldots, m\}$ mean in the equation of the empirical error?

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 ...
• 9,037