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
2
votes
1answer
20 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 ...
3
votes
1answer
30 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
30 views

Show that if $H$ is PAC learnable (in the standard one-oracle model), then $H$ is also learnable in the two-oracle model

Consider a variant of the PAC model in which there are two example oracles: one that generates positive examples and one that generates negative examples, both according to the underlying distribution ...
2
votes
1answer
39 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
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 ...
1
vote
0answers
35 views

How Dempster-Shafer theory work in AI?

How does Dempster-Shafer theory work in representing ignorance in AI field?
1
vote
1answer
93 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 ...
3
votes
0answers
137 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 ...
6
votes
2answers
471 views

What are the limits to what can be learnt using a backpropagation neural network?

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