What is the difference between concept class and hypothesis

Question

Formal definition that I have seen of concept class is

class of all true functions

mathematically :

$f:X \rightarrow\{0,1\}$

and that of hypothesis is:

$h:X \rightarrow\{0,1\}$

But most of the times they are used together. For example in definition of PAC

A concept class 𝐶 is PAC learnable by a learner 𝐿 using hypothesis space 𝐻 if for all concepts 𝑐∈𝐶, distributions over 𝑋, true error probability 0≤𝜖≤1/2, failure probability 0≤𝛿≤1/2, learner 𝐿 outputs a hypothesis ℎ∈𝐻 such that

True error less than or equal to 𝜖

Computational time is polynomial in 1/𝜖,1/𝛿, representation size of data object, and representation size of concept

What is the difference?

Answer 1

A concept class C is a set of true functions f. Hypothesis class H is the set of candidates to formulate as the final output of a learning algorithm to well approximate the true function f. Hypothesis class H is chosen before seeing the data (training process). C and H can be either same or not and we can treat them independently.

Answer 2

If one requires that $H = C$, then this is called the "proper PAC" framework compared to "PAC prediction" where we don't care about the representation of $h$ as long as the prediction error is small enough (i.e. we allow $H$ to be the class of all time-polynomial programs).

You can think of a concept as the set of inputs that produce the same label (e.g. all the images that show a chair form the concept "chair" or all the points in the same half space form the concept "true/false").