Questions tagged [hypothesis-class]

For questions related to the concept of a hypothesis class in the context of computational learning theory. A hypothesis class can be defined as the set of hypotheses (i.e. functions) considered by the learning algorithm.

Filter by
Sorted by
Tagged with
2 votes
1 answer

Is there any practical application of knowing whether a concept class is PAC-learnable?

A concept class $C$ is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least $(1-\delta)$ (the "probably" part), and an error that is less than $\epsilon$ (...
  • 1,241
5 votes
4 answers

How does size of the dataset depend on VC dimension of the hypothesis class?

This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in this video prof. is trying to explain how we should interpret the VC dimension in ...
2 votes
1 answer

How do I prove that $\mathcal{H}$, with $\mathcal{VC}$ dimension $d$, shatters all subsets with size less than $d-1$?

If a certain hypothesis class $\mathcal{H}$ has a $\mathcal{VC}$ dimension $d$ over a domain $X$, how can I prove that $H$ will shatter all subsets of $X$ with size less than $d$, i.e. $\mathcal{H}$ ...
user avatar
8 votes
3 answers

What is the difference between hypothesis space and representational capacity?

I am reading Goodfellow et al Deeplearning Book. I found it difficult to understand the difference between the definition of the hypothesis space and representation capacity of a model. In Chapter 5,...
  • 83