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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
63 views

What is the relevance of the concept size to the time constraints in PAC learning?

My question is about the relevance of concept size to the polynomial-time/example constraints in efficient PAC-learning. To ask my question precisely I must first give some definitions. Definitions: ...
user avatar
1 vote
0 answers
16 views

Characterize the high probability bound for learning algorithm

Suppose we have a dataset $S = (x_1, \dots x_n)$ drawn i.i.d from distribution $D$, a learning algorithm $A$ and error function $err$. The performance of $A$ is therefore defined by the error/...
user avatar
  • 111
1 vote
1 answer
50 views

What is the expectation of an empirical model in model based RL?

In the paper - "Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems", on page 1083, on the 6th line from the bottom, the authors define ...
user avatar
  • 78
2 votes
1 answer
213 views

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$ (...
user avatar
  • 1,241
2 votes
0 answers
75 views

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)?
user avatar
2 votes
1 answer
114 views

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 ...
user avatar
  • 123
6 votes
1 answer
1k views

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 ...
user avatar
  • 218
6 votes
3 answers
558 views

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 ...
user avatar
2 votes
0 answers
495 views

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 ...
user avatar
  • 181
2 votes
0 answers
72 views

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}\...
user avatar
  • 181
7 votes
1 answer
400 views

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 ...
user avatar
3 votes
0 answers
137 views

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 |\...
user avatar
  • 133
1 vote
1 answer
221 views

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 ...
user avatar
  • 133
4 votes
2 answers
130 views

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 ...
user avatar
  • 133