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
0 votes
1 answer
51 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. $...
Tran Khanh's user avatar
2 votes
2 answers
58 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 ...
Tran Khanh's user avatar
2 votes
1 answer
630 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$ (...
calveeen's user avatar
  • 1,261
5 votes
4 answers
2k 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 ...
Stefan Radonjic's user avatar
2 votes
1 answer
619 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}$ ...
user avatar
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,...
Qwarzix's user avatar
  • 83