4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ take a look at here $\endgroup$ – Media Jan 9 '18 at 14:33
1
$\begingroup$

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

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

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

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