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").