# What is the difference between concept class and hypothesis

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?

• take a look at here – Media Jan 9 '18 at 14:33

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