Questions tagged [pac-learning]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
46 views

Why is a lower bound necessary in proofs of VC-dimensions for various examples of hypotheses?

In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, ...
4
votes
1answer
66 views

A trick used in Rademacher complexity related Theorem

I am currently working on the proof of Theorem 3.1 in the book "Foundations of Machine Learning" (page 35, First edition), and there is a key trick used in the proof (equation 3.10 and 3.11): $$\...
2
votes
1answer
41 views

Generalization bound (single hypothesis) in “Foundations of Machine Learning”

I have a question about Corollary $2.2$: Generalization bound--single hypothesis in the book "Foundations of Machine Learning" Mohri et al. $2012$. Equation $2.17$ seems to only hold when $\hat{R}_S(...
1
vote
1answer
50 views

A question on realizable sample complexity

I came across the following exercise, and I just can't seem to crack it: Let $l$ be some loss function such that $l \leq 1$. Let $H$ be some hypothesis class, and let $A$ be a learning algorithm. ...
2
votes
2answers
180 views

Where does the “deep learning needs big data” rule come from

When reading about deep learning I often come across the rule that deep learning is only effective when you have large amounts of data at your disposal. These statements are generally accompanied by a ...
1
vote
0answers
35 views

PAC Learnability - Notation

the following is from Understanding Machine Learning: Theory to Algorithm textbook: Definition of PAC Learnability: A hypothesis class $H$ is PAC learnable if there exist a function $m_H : (0, 1)^2 \...
1
vote
1answer
70 views

Meaning of Instance Space and Concept Class, (PAC Learnable)

I'm studying Probably approximately correct learning, and I don't understand what an Instance Space and a Concept is. I have see that wikipedia https://en.wikipedia.org/wiki/...
1
vote
0answers
104 views

Intuition behind Occam's Learner Algorithm using VC-Dimension

So I'm learning about Occam's Learning algorithm and PAC-Learning where for a given hypothesis space $H$, if we want to have a model/hypothesis $h$ that has an True error of $error_D \leq \epsilon$, ...
3
votes
1answer
545 views

What is PAC learning?

I have seen here but I really cannot realize that. In this framework, the learner receives samples and must select a generalization function (called the hypothesis) from a certain class of possible ...
3
votes
1answer
3k views

Generalization Error Definition

I was reading about PAC framework and faced the definition of Generalization Error. The book defined it as: Given a ...
21
votes
5answers
23k views

Are decision tree algorithms linear or nonlinear

Recently a friend of mine was asked whether decision tree algorithms are linear or nonlinear algorithms in an interview. I tried to look for answers to this question but couldn't find any satisfactory ...