# Tag Info

## Hot answers tagged pac-learning

6

Although I have only partially read (or not read at all) some of the following resources and some of these resources may not cover more advanced topics than the ones presented in the book you are reading, I think they can still be useful for your purposes, so I will share them with you. I would also like to note that if you understand the contents of the ...

4

There is no contradiction. First, agnostic PAC learnable doesn't mean that the there is a good hypothesis in the hypothesis class; it just means that there is an algorithm that can probably approximately do as well as the best hypothesis in the hypothesis class. Also, these NFL theorems have specific mathematical statements, and hypothesis classes for ...

3

Yes, PAC learning can be relevant in practice. There's an area of research that combines PAC learning and Bayesian learning that is called PAC-Bayesian (or PAC-Bayes) learning, where the goal is to find PAC-like bounds for Bayesian estimators. For example, Theorem 1 (McAllester’s bound) of the paper A primer on PAC-Bayesian learning (2019) by Benjamin ...

2

Definitely, you can find the proof in different resources (for example, in these notes or in the paper that originally proposed PAC learnability, A Theory of the Learnable). However, the intuition behind your question is when the size of the hypothesis increases, if you do not change anything, you can't see more part of the space. Hence, the estimation error ...

1

If I understand your question correctly, the significance of this is due to the fact that $s'$ is random. In the RHS of the equation it is assumed that $V(\cdot)$ is known for each state, but the quantity is measuring the expected value of the next state given the current state and action.

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

1

In the paper Generalization in Unsupervised Learning (2015), Abou-Moustafa and Schuurmans develop an approach to assess the generalization of an unsupervised learning algorithm $A$ on a given dataset $S$ and how to compare the generalization ability of two unsupervised learning algorithms $A_1$ and $A_2$, for the same learning task. They first provide a ...

Only top voted, non community-wiki answers of a minimum length are eligible