Questions tagged [pac-learning]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
20 views

the VCdim of class of double parameter threshold functions

Let $H$ be a family of classifiers such that $H=\{ h_{a,b} : a,b\in \mathbb{R}\}$ where $h_{a,b}(x,y)=1$ iff $x\geq a$ and $y\geq b$. I've proved that for $C=\{m=(x,y)\}$, $H$ shatters $C$. However, ...
Aishgadol's user avatar
  • 101
0 votes
1 answer
195 views

VC- dimension calculate

Let X = {1, 2, 3, ... , 100}. Let H be the class of all subsets of X that contain at least 20 and at most 80 elements. What is the VC-dimension of H?
tomkeruse's user avatar
0 votes
1 answer
38 views

Finding the tightest (smallest) triangle that fits all points

I'm supposed to find an algorithm that, given a bunch of points on the Euclidean plane, I have to return the tightest (smallest) origin centered upright equilateral triangle that fits all the given ...
MathCurious's user avatar
0 votes
0 answers
68 views

VC Dimension of a Countably Infinite Class

I know that there are many examples of classes where the VC Dimension is finite/infinite even though the size of the class is Uncountably Infinite. However, I could not argue if the VC Dimension of a ...
Chen Reddy Sundeep's user avatar
2 votes
1 answer
112 views

Why does PAC learning focus on learnability of the hypothesis class and not the target function?

The definition of PAC learning is roughly An algorithm is a PAC learning algorithm if it given enough data, for any target function, it asymptotically does as well as it possibly could given the ...
Jack M's user avatar
  • 265
1 vote
1 answer
37 views

Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered

Today in the lecture the lecturer said something I found peculiar, and I felt very inconvenient when I heard it: He claimed, that if the maximal VCdim of some hypothesis class is $n\in\mathbb N$, then ...
C.H.'s user avatar
  • 11
2 votes
1 answer
820 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, ...
learning machine's user avatar
4 votes
1 answer
145 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): $$\...
learning machine's user avatar
2 votes
1 answer
149 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(...
learning machine's user avatar
2 votes
1 answer
85 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. ...
Nadav Schweiger's user avatar
4 votes
4 answers
682 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 ...
Aran's user avatar
  • 41
2 votes
1 answer
208 views

PAC Learnability - Notation

The following is from Understanding Machine Learning: Theory to Algorithm textbook: Definition of PAC Learnability: A hypothesis class $\mathcal H$ is PAC learnable if there exist a function $m_H : (...
tkj80's user avatar
  • 139
2 votes
1 answer
780 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/...
Tommaso Bendinelli's user avatar
2 votes
0 answers
156 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$, ...
JoeVictor's user avatar
  • 101
3 votes
1 answer
1k 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 ...
Green Falcon's user avatar
3 votes
1 answer
4k views

Generalization Error Definition

I was reading about PAC framework and faced the definition of Generalization Error. The book defined it as: Given a ...
Green Falcon's user avatar
37 votes
5 answers
58k 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 ...
user2966197's user avatar