Answers.Body: <blockquote>
    <p>Is there any practical application of knowing whether a concept class is PAC-learnable?</p>
  </blockquote>
  
  <p>If you know that a concept class is PAC-learnable (i.e. <a href="https://dl.acm.org/doi/pdf/10.1145/76359.76371#page=2" rel="nofollow noreferrer">its VC dimension is finite</a>), 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.</p>
  
  <p>This is not really an application, but a consequence, which can lead to applications. </p>
  
  <p>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.</p>
  
  <p>See also <a href="https://ai.stackexchange.com/q/17291/2444">Are PAC learning and VC dimension relevant to machine learning in practice?</a> for more concrete "applications" of PAC-learning and the VC dimension.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-18T13:44:03.130Z
Answers.LastActivityDate: 2020-05-18T13:54:49.370Z
Answers.LastEditDate: 2020-05-18T13:54:49.370Z
Answers.UserDisplayName: nbro
Body: <p>A concept class <span class="math-container">$C$</span> is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least <span class="math-container">$(1-\delta)$</span> (the "probably" part), and an error that is less than <span class="math-container">$\epsilon$</span> (the "approximately" part), in time that is polynomial in <span class="math-container">$1/\epsilon$</span>, <span class="math-container">$1/\delta$</span>, <span class="math-container">$n$</span> and <span class="math-container">$|C|$</span>. </p>
  
  <p><a href="http://www.cs.cmu.edu/~tom/mlbook.html" rel="nofollow noreferrer">Tom Mitchell</a> defines an upper bound for the sample complexity, <span class="math-container">$m &gt;= 1/\epsilon (ln(|H|) + ln(1/\delta))$</span> for the finite hypotheses. Based on this bound, he classifies whether target concepts are PAC-learnable or not. For example, <span class="math-container">$n$</span> conjunction boolean literal concept class. </p>
  
  <p>It seems to me that PAC-learnability seeks to act more like a classification of certain concept classes. </p>
  
  <p>Are there any practical purposes for knowing whether a concept class is PAC-learnable? </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-17T09:49:57.260Z
Comments.Text: but wouldn't determining whether the concept class is PAC learnable means going through the process that i described in the post ?
Comments.UserDisplayName: calveeen
Tags: <applications><computational-learning-theory><pac-learning><sample-complexity><hypothesis-class>
Title: Is there any practical application of knowing whether a concept class is PAC-learnable?
UserDisplayName: calveeen
ThreadText: # Is there any practical application of knowing whether a concept class is PAC-learnable?
  
  (Asked by: username_0 on 2020-05-17)
  
  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](http://www.cs.cmu.edu/~tom/mlbook.html) 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?
  
  **Tags:** applications, computational-learning-theory, pac-learning, sample-complexity, hypothesis-class
  
  > **Comments:**
  > **username_0**: but wouldn't determining whether the concept class is PAC learnable means going through the process that i described in the post ?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-05-18. Score: 1
  
  > 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](https://dl.acm.org/doi/pdf/10.1145/76359.76371#page=2)), 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?](https://ai.stackexchange.com/q/17291/2444) for more concrete "applications" of PAC-learning and the VC dimension.
  
  
  ---
  
  