What's the deal with Deno? We talk with a major contributor to find out. Listen now.

Questions tagged [learning-theory]

For questions related to computational learning theory (or, in short, learning theory), which is a research subfield of artificial intelligence devoted to studying the design and mathematical analysis of machine learning algorithms. Computational learning theory (COLT) is largely concerned with computational and data efficiency. A seminal paper in COLT is Valiant's "A theory of the learnable" (1984).

Filter by
Sorted by
Tagged with
11
votes
1answer
251 views

What are the state-of-the-art results on the generalization ability of deep learning methods?

I've read a few classic papers on different architectures of deep CNNs used to solve varied image-related problems. I'm aware there's some paradox in how deep networks generalize well despite ...
8
votes
2answers
539 views

What are the learning limitations of neural networks trained with backpropagation?

In 1969, Seymour Papert and Marvin Minsky showed that Perceptrons could not learn the XOR function. This was solved by the backpropagation network with at least one hidden layer. This type of ...
8
votes
3answers
214 views

Why can neural networks generalize at all?

Neural networks are incredibly good at learning functions. We know by the universal approximation theorem that, theoretically, they can take the form of almost any function - and in practice, they ...
7
votes
1answer
517 views

Can neural networks with a sigmoid as the activation function of the output layer approximate continuous functions?

Neural networks are commonly used for classification tasks, in fact from this post it seems like that's where they shine brightest. However, when we want to classify using neural networks, we often ...
7
votes
2answers
134 views

Can we teach an artificial intelligence through sentences?

Could we teach an AI with sentences such as "ants are small" and "the sky is blue"? Is there any research work that attempts to do this?
6
votes
3answers
297 views

Are there any rules of thumb for having some idea of what capacity a NN model needs to have for a given problem?

To give an example. Let's just consider the MNIST dataset of handwritten digits. Here are some things which might have an impact on the optimum model capacity: There are 10 output classes The inputs ...
5
votes
4answers
512 views

How does size of the dataset depend on VC dimension?

This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in this video prof. is trying to explain how we should interpret VC dimension in terms ...
5
votes
1answer
132 views

Are PAC learning and VC dimension relevant to machine learning in practice?

Are PAC learning and VC dimension relevant to machine learning in practice? If yes, what is their practical value? To my understanding, there are two hits against these theories. The first is that ...
5
votes
1answer
125 views

Is there a way of converting a neural network to another one that represents the same function?

I have read the paper Neural Turing Machines and the paper On the Computational Power of Neural Nets about the computational power of neural networks. However, it isn't still clear to me one thing. ...
4
votes
1answer
415 views

What are some resources on computational learning theory?

Pretty soon I will be finishing up Understanding Machine Learning: From Theory to Algorithms by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only ...
4
votes
2answers
260 views

How to estimate the capacity of a neural network?

Is it possible to estimate the capacity of a neural network model? If so, what are the techniques involved?
4
votes
2answers
124 views

Mathematical foundations of the ability to learn

I am an undergraduate student in applied mathematics with an interest in artificial intelligence. I am currently exploring topics where I could do research. Coming from a mathematical background I am ...
4
votes
2answers
169 views

Are PAC learnability and the No Free Lunch theorem contradictory?

I am reading the Understanding Machine Learning book by Shalev-Shwartz and Ben-David and based on the definitions of PAC learnability and No Free Lunch Theorem, and my understanding of them it seems ...
4
votes
1answer
70 views

In deep learning, do we learn a continuous distribution based on the training dataset?

At least at some level, maybe not end-to-end always, but deep learning always learns a function, essentially a mapping from a domain to a range. The domain and range, at least in most cases, would be ...
4
votes
2answers
95 views

Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?

Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning? I came across this statement in the section 5.2 of the book "understanding machine learning: from theory to ...
3
votes
2answers
705 views

How can generalization error be estimated?

How would you estimate the generalisation error? What are the methods of achieving this?
3
votes
1answer
110 views

What is the maximum number of dichotomies in a square?

I am new to machine learning. I am reading this blog post on the VC dimension. $\mathcal H$ consists of all hypotheses in two dimensions $h: R^2 → \{−1, +1 \}$, positive inside some square boxes and ...
3
votes
1answer
74 views

How to show Sauer's Lemma when the inequalities are strict or they are equalities?

I have the following homework. We proved Sauer's lemma by proving that for every class $H$ of finite VC-dimension $d$, and every subset $A$ of the domain, $$ \left|\mathcal{H}_{A}\right| \leq |\...
3
votes
0answers
27 views

Batch PTA stopping condition

I am reviewing my Neural Network lectures and I have a doubt: My book's (Haykin) batch PTA describes a cost function which is defined over the set of the misclassified inputs. I have always been ...
3
votes
0answers
161 views

What is the relation between the definition of learnability of Vapnik and Gold and learnability of neural networks?

Gold showed that a language can be learned only if it contains a finite set of sentences. We know that deep neural networks can implement any function. Does this contradict the Gold's result? What ...
2
votes
4answers
459 views

How do you distinguish between a complex and a simple model in machine learning?

How do you distinguish between a complex and a simple model in machine learning? Which parameters control the complexity or simplicity of a model? Is it the number of inputs, or maybe the number of ...
2
votes
1answer
45 views

Is there any practical application of knowing whether a concept class is PAC-learnable?

A concept class $C$ is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least $(1-\delta)$ (the "probably" part), and an error that is less than $\epsilon$ (...
2
votes
1answer
99 views

How to prove $\mathcal H$ with VC dimension $d$ shatter all subsets with size less than $d-1$?

I was wondering that if a certain hypothesis class $H$ has a VC dimension $d$ over domain $X$ how to prove that $H$ will shatter all subsets of $X$ with size less than $d$ i.e $H$ will shatter $A \...
2
votes
1answer
57 views

How does the number of stacked LSTM layers or units in each layer affect the model complexity?

I playing around sequence modeling to forecast the weather using LSTM. How does the number of layers or units in each layer exactly affect the model complexity (in an LSTM)? For example, if I ...
2
votes
1answer
27 views

Understanding the equation of the empirical error

The empirical error equation given in the book Understanding Machine Learning: From Theory to Algorithms is My intuition for this equation is: total wrong predictions divided by the total number of ...
2
votes
1answer
63 views

How Dempster-Shafer theory work in AI?

How does Dempster-Shafer theory work in representing ignorance in AI field?
2
votes
1answer
41 views

A model for each sub-problem vs one model for the whole problem

Let's say one wants to use a neural net to learn some function $g(x)$. Let's say that we know that $g$ is a combination of two functions (or two sub-problems), $g(x)=f_2(f_1(x))$, and that we have two ...
2
votes
1answer
64 views

An infinite VC dimensional space vs using hierarchical subspaces of finite but growing VC dimensions

I have the following scenario. I have a binary classification problem, whose underlying function is a step function. The probability distribution of feature vectors is a uniform over the domain. Case ...
2
votes
1answer
97 views

How can neural networks approximate any continuous function but have $\mathcal{VC}$ dimension only proportional to their number of parameters?

Neural networks typically have $\mathcal{VC}$ dimension that is proportional to their number of parameters and inputs. For example, see the papers Vapnik-Chervonenkis dimension of recurrent neural ...
2
votes
0answers
46 views

Are No Free Lunch theorem and Universal Approximation theorem contradictory in the context of neural networks?

To my understanding NFL states that, we cannot have an hypothesis (let's assume it is an approximator like NN in this case) class that can't achieve certain accuracy parameters $\leq \epsilon$ with ...
2
votes
0answers
36 views

How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$?

How can I show that the VC dimension of the set of all closed balls in $\mathbb{R}^n$ is at most $n+3$? For this problem, I only try the case $n=2$ for 1. When $n=2$, consider 4 points $A,B,C,D$ and ...
2
votes
0answers
150 views

A problem about the relation between 1-oracle and 2-oracle PAC model

This problem is about two-oracle variant of the PAC model. Assume that positive and negative examples are now drawn from two separate distributions $\mathcal{D}_{+}$ and $\mathcal{D}_{-} .$ For an ...
2
votes
0answers
38 views

How can we prove this inequality, related to the generalization error, without using the Rademacher complexity?

This is an inequality on page 36 of the book Foundations of Machine Learning, but the author only states it without proof. $$ \mathbb{P}\left[\left|R(h)-\widehat{R}_{S}(h)\right|>\epsilon\right] \...
2
votes
0answers
31 views

Convert a PAC-learning algorithm into another one which requires no knowledge of the parameter

This is part of the exercise 2.13 in the book Foundations of Machine Learning (page 28). You can refer to chapter 2 for the notations. Consider a family of concept classes $\left\{\mathcal{C}_{s}\...
1
vote
1answer
68 views

VC Dimension of Reinforcement Learning (RL)

Is the VC dimension meaningful for the reinforcement learning (RL) as a machine learning (ML) method? How?
1
vote
1answer
63 views

Understanding relation between VC Symmetrization Lemma and Generalization Bounds

I am new in the field of Machine Learning so I wanted to start of by reading more about mathematics and history behind it. I am currently reading, in my opinion, a very good and descriptive paper on ...
1
vote
1answer
72 views

Does this $\max$ mean that we need to maximize the regret in this regret formula?

I found that the regret in Online Machine Learning is stated as: $$\operatorname{Regret}_{T}(h)=\sum_{t=1}^{T} l\left(p_{t}, y_{t}\right)-\sum_{t=1}^{T} l\left(h(x), y_{t}\right),$$ where $p_t$ is the ...
1
vote
1answer
49 views

Why is probability that at least one hypothesis out of $k$ being consistent with $m$ training examples $k(1- \epsilon)^m$?

My question is actually related to the addition of probabilities. I am reading on computational learning theory from Tom Mitchell's machine learning book. In chapter 7, when proving the upper bound ...
1
vote
1answer
67 views

What do we mean by saying “VC dimension gives a LOOSE, not TIGHT bound”?

From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice. But, the literature (i.e. Learning from Data)...
1
vote
1answer
45 views

Can feature engineering change the selection of the model according to the minimum description length?

The definition of MDL according to these slides is: The minimum description length (MDL) criteria in machine learning says that the best description of the data is given by the model which ...
1
vote
1answer
42 views

Why does the discrepancy measure involve a supremum over the hypothesis space?

I am referring specifically to the disc defined by Kuznetsov and Mohri in https://arxiv.org/pdf/1803.05814.pdf This is a kind of worst case path dependent generalization error. But what is the ...
1
vote
2answers
186 views

What is the difference between a learning algorithm and a hypothesis?

What's the distinction between a learning algorithm $A$ and a hypothesis $f$? I'm looking for a few concrete examples, if possible. From what I understand, one way to vary the hypothesis $f$ would be ...
1
vote
1answer
132 views

Minimum number of perceptrons for an n-bit truth table?

Suppose I have a Boolean function that maps N bits to one bit. If I understand correctly, this function will have 2^2^N possible configurations of its truth table. What is the minimum number of ...
1
vote
1answer
36 views

What is the representational capacity of a learning algorithm? [duplicate]

The definition I see for representational capacity is "the family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective." (...
1
vote
0answers
35 views

How estimate the minimum size of an autoencoder to overfit the training data?

Given e.g. $1$M vectors of $1000$ floating points each, where every point in vectors is sampled from a uniform distribution between $-1$ to $1$, how to estimate the minimum network size required ...
1
vote
0answers
49 views

What is the relationship between PAC learning and classic parameter estimation theorems?

What are the differences and similarities between PAC learning and classic parameter estimation theorems (e.g. consistency results when estimating parameters, e.g. with MLE)?
0
votes
1answer
56 views

What are the prior beliefs in a neural network? (if any)

Let us confine ourselves to the case where we have a $n$ dimensional input and a $+1$ or $-1$ output. It can be shown that: For every $n$, there exists a dense NN of depth 2, such that it ...
0
votes
1answer
57 views

How can a machine learning problem be reduced as a communication problem?

I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?