Artificial Intelligence Stack Exchange
Artificial Intelligence Stack Exchange

Questions tagged [pac-learning]

For questions related to Probably Approximately Correct (PAC) learning, a framework for mathematical analysis of machine learning algorithms, which was introduced in the paper "A Theory of the Learnable" (1984) by Leslie G. Valiant.

See A Theory of the Learnable (1984) by Leslie G. Valiant.

19 questions
10
votes
1 answer

What are some resources on computational learning theory?

Pretty soon I will be finishing up Understanding Machine Learning: From Theory to Algorithms by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble finding a book that…
PMaynard
  • 258
  • 2
  • 6
8
votes
1 answer

Are PAC learning and VC dimension relevant to machine learning in practice?

Are PAC learning and VC dimension relevant to machine learning in practice? If yes, what is their practical value? To my understanding, there are two hits against these theories. The first is that the results all are conditioned on knowing the…
FourierFlux
  • 847
  • 1
  • 7
  • 17
7
votes
4 answers

Are PAC learnability and the No Free Lunch theorem contradictory?

I am reading the Understanding Machine Learning book by Shalev-Shwartz and Ben-David and based on the definitions of PAC learnability and No Free Lunch Theorem, and my understanding of them it seems like they contradict themselves. I know this is…
Jonathan Azpur
  • 113
  • 4
5
votes
1 answer

Is PAC-unlearnability a fundamental limitation for LLM reasoning?

For simplicity, let’s focus on knowledge reasoning tasks with Yes/No answers. According to learning theory, even moderately complex knowledge reasoning tasks are PAC-unlearnable. This implies that no learning-based reasoning engine trained on a…
nova
  • 180
  • 6
4
votes
0 answers

How to show Sauer's Lemma when the inequalities are strict or they are equalities?

I have the following homework. We proved Sauer's lemma by proving that for every class $H$ of finite VC-dimension $d$, and every subset $A$ of the domain, $$ \left|\mathcal{H}_{A}\right| \leq |\{B \subseteq A: \mathcal{H} \text { shatters } B\} |…
Ben
  • 253
  • 1
  • 6
4
votes
2 answers

Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning?

Why does estimation error increase with $|H|$ and decrease with $m$ in PAC learning? I came across this statement in the section 5.2 of the book "understanding machine learning: from theory to algorithms". You just search "increases…
Ben
  • 253
  • 1
  • 6
3
votes
1 answer

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

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…
calveeen
  • 1,311
  • 9
  • 18
3
votes
1 answer

Is there a notion of generalization in unsupervised learning?

I've been learning a little bit about generalization theory, and in particular, the PAC (and PAC-Bayes) approach to thinking about this problem. So, I started to wonder if there is an analogous version of "generalization" in Unsupervised Learning?…
Marcel
  • 133
  • 3
2
votes
0 answers

What is the relationship between PAC learning and classic parameter estimation theorems?

What are the differences and similarities between PAC learning and classic parameter estimation theorems (e.g. consistency results when estimating parameters, e.g. with MLE)?
FourierFlux
  • 847
  • 1
  • 7
  • 17
2
votes
0 answers

A problem about the relation between 1-oracle and 2-oracle PAC model

This problem is about two-oracle variant of the PAC model. Assume that positive and negative examples are now drawn from two separate distributions $\mathcal{D}_{+}$ and $\mathcal{D}_{-} .$ For an accuracy $(1-\epsilon),$ the learning algorithm must…
j200932
  • 181
  • 1
  • 3
2
votes
0 answers

Convert a PAC-learning algorithm into another one which requires no knowledge of the parameter

This is part of the exercise 2.13 in the book Foundations of Machine Learning (page 28). You can refer to chapter 2 for the notations. Consider a family of concept classes $\left\{\mathcal{C}_{s}\right\}_{s}$ where $\mathcal{C}_{s}$ is the set of…
j200932
  • 181
  • 1
  • 3
2
votes
1 answer

Prove that in such cases, it is possible to find an ERM hypothesis for $H_n$ in the unrealizable case in time $O(mnm^{O(n)})$

Let $H_1$ , $H_2$ ,... be a sequence of hypothesis classes for binary classification. Assume that there is a learning algorithm that implements the ERM rule in the realizable case such that the output hypothesis of the algorithm for each class $H_n$…
Ben
  • 253
  • 1
  • 6
1
vote
1 answer

Why do learning paradigms overfit? (Machine Learning Theory) uniform convergence

I have been learning about agnostic PAC and uniform convergence with finite hypothesis classes. If we use a NN with $d$ parameters with $64$-bit precision $$ \frac{r^2(128d+2\ln(\frac{2}{\delta}))}{\epsilon^2} $$ should be an upper bound on the…
Joe Jameson
  • 21
  • 2
1
vote
1 answer

Using the definition of APAC learning and uniform convergence in practice

I am currently studying "Understanding Machine Learning from Theory to Practice" written by Shai Shalev-Shwartz and Shai Ben-David. I want to understand how i can use the Definitions and Results of the Theory he describes in Practice. Consider the…
MathAccount12
  • 11
  • 1
1
vote
0 answers

Where can I find the solutions to the problems in the book "An Introduction to Computational Learning Theory"?

I have been going through "An Introduction to Computational Learning Theory" (Kearns-Vazirani). I don't know if my solutions to the problems are correct and have no other way of checking my learning. How would I find solutions to compare to or…
aome
  • 111
  • 1
1
2