We’re rewarding the question askers & reputations are being recalculated! Read more.

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

11 questions
Filter by
Sorted by
Tagged with
39 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 ...
23 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 ﬁnite VC-dimension $d$, and every subset $A$ of the domain,  \left|\mathcal{H}_{A}\right| \leq |\...
21 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 ...
34 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 ...
32 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 ...
40 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 ...
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 ...
39 views

### How Dempster-Shafer theory work in AI?

How does Dempster-Shafer theory work in representing ignorance in AI field?
101 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 ...