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.
Questions tagged [hypothesis-class]
4 questions
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, it is written about hypothesis space:
One way…
Qwarzix
- 83
- 1
- 4
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 terms of what it means in layman terms, and why do…
Stefan Radonjic
- 187
- 5
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$ (the "approximately" part), in time that is…
calveeen
- 1,251
- 7
- 17
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}$ will shatter $A \subset X$ where $|A| \leq d-1$?
user9947