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?

  • $\begingroup$ take a look at here $\endgroup$ Commented Jan 9, 2018 at 14:33

2 Answers 2


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.


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


Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.