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.
6 questions
0
votes
1
answer
151
views
Realizability Assumption: Why is that for every ERM hypothesis $L_{S}(h_{S})=0$
I'm quoting Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014:
Definition 2.1 (The Realizability Assumption). There exists $h^{\star} \in \mathcal{H}$ s.t. $...
- 167
2
votes
2
answers
62
views
Why any set of m data points with different features can be perfectly fit by a polynomial of degree n as long as n ≥ m
On p.36 in "Machine Learning: The Basics", Alexander Jung, Spinger, the author wrote:
The fundamental theorem of algebra tells us that any set of m data points with different features can ...
- 2,632
2
votes
1
answer
636
views
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}$ ...
- 41.4k
8
votes
3
answers
4k
views
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,...
- 41.4k
5
votes
4
answers
3k
views
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 ...
- 1,836
3
votes
1
answer
752
views
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$ (...
- 41.4k