10 votes
Accepted

What are some resources on computational learning theory?

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 ...
nbro's user avatar
  • 40.2k
6 votes
Accepted

Are PAC learnability and the No Free Lunch theorem contradictory?

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 ...
Anon's user avatar
  • 271
4 votes

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

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 ...
nbro's user avatar
  • 40.2k
3 votes

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

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 ...
OmG's user avatar
  • 1,816
1 vote
Accepted

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

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 ...
harwiltz's user avatar
  • 1,126
1 vote

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

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 ...
nbro's user avatar
  • 40.2k
1 vote
Accepted

Is there a notion of generalization in unsupervised learning?

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 $...
nbro's user avatar
  • 40.2k
1 vote

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)})$

Here's a rough proof sketch that might be clearer, but is probably less precise, than the solution you already have. We have a sequence of hypotheses classes, but the problem actually only asks us to ...
John Doucette's user avatar

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