3
$\begingroup$

A concept class $C$ is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least $(1-\delta)$ (the "probably" part), and an error that is less than $\epsilon$ (the "approximately" part), in time that is polynomial in $1/\epsilon$, $1/\delta$, $n$ and $|C|$.

Tom Mitchell defines an upper bound for the sample complexity, $m >= 1/\epsilon (ln(|H|) + ln(1/\delta))$ for the finite hypotheses. Based on this bound, he classifies whether target concepts are PAC-learnable or not. For example, $n$ conjunction boolean literal concept class.

It seems to me that PAC-learnability seeks to act more like a classification of certain concept classes.

Are there any practical purposes for knowing whether a concept class is PAC-learnable?

Improve this question
$\endgroup$
2
  • $\begingroup$ Seeing another way, a more useful formulation would be, whether the concept class is PAC learnable by your hypothesis class. Then you may play with your $H$. Also note PAC learnable is a very special case and it goes on to build on realistic cases like agnostic PAC, NUL, etc, etc. $\endgroup$
    – user9947
    Commented May 17, 2020 at 8:53
  • $\begingroup$ but wouldn't determining whether the concept class is PAC learnable means going through the process that i described in the post ? $\endgroup$
    – calveeen
    Commented May 17, 2020 at 9:49

1 Answer 1

Reset to default
1
$\begingroup$

Is there any practical application of knowing whether a concept class is PAC-learnable?

If you know that a concept class is PAC-learnable (i.e. its VC dimension is finite), then there's a possibility that you can design an algorithm that can find a function (or concept) that is arbitrarily close to your target (or desired) function.

This is not really an application, but a consequence, which can lead to applications.

However, note that asking if PAC learning is useful in practice is like asking if special relativity is useful in practice. Yes, they are useful, but in the sense that they can be used to predict the outcomes of an experiment or explain the rules in their specific context. In the case of machine learning, PAC learning can be used to explain e.g. the probably required number of data points needed to learn a concept (a target function) approximately.

See also Are PAC learning and VC dimension relevant to machine learning in practice? for more concrete "applications" of PAC-learning and the VC dimension.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .