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

$\endgroup$
0
$\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.

$\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.