# Questions tagged [pac-learning]

The tag has no usage guidance.

20 questions
Filter by
Sorted by
Tagged with
3 views

### Learning Theory - PAC learning, hypothesis class containing the true classifier

For a given hypothesis space $H$, assuming $f\in H$ where $f$ is the true classifier, you can choose a group $S~D$ where $D$ is a distribution, with a large enough sample complexity, such that the ...
• 111
7 views

### PAC-Learning, error estimation

I'm looking at this true/false question (currently in a ML course) and there's no given solution/explanation for this, I cant really understand what am I supposed to look for when facing this: "...
• 111
40 views

### VC-dimension proof for a family of classifiers

I've been working on determining the VC-dimension of a specific family of classifiers, and I would like to get some feedback on the proof I've come up with. The family of classifiers is defined as ...
27 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, ...
• 111
213 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?
52 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 ...
• 103
73 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 ...
124 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 ...
• 265
1 vote
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 ...
• 11
854 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, ...
148 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): \...
156 views

• 139
804 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/...
157 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$, ...
• 101
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 ...
• 14.1k
5k views

### Generalization Error Definition

I was reading about PAC framework and faced the definition of Generalization Error. The book defined it as: Given a ...
• 14.1k