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
172 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
495 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 ...
3
votes
1answer
35 views

Query on another perspective on Deep Learning

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 ...
3
votes
0answers
23 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
142 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
1answer
22 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
45 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 ...
2
votes
1answer
50 views

How Dempster-Shafer theory work in AI?

How does Dempster-Shafer theory work in representing ignorance in AI field?
2
votes
0answers
43 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. $H$ consists of all hypotheses in two dimensions $h: R^2 → \{−1, +1 \}$, positive inside some square boxes and negative ...
2
votes
0answers
26 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 |\...
1
vote
2answers
68 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
107 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 ...