7

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 appropriate models to use, for example, the degree of complexity. The second is that the bounds are very bad, where a deep learning network would take an astronomical amount of data to reach said bounds.

nbro
  • 39,006
  • 12
  • 98
  • 176
FourierFlux
  • 783
  • 1
  • 4
  • 14
  • 1
    both of these started out many years before ML theory in (theoretical) computer science and are more abstract. they interrelate to ML theory but are rarely cited by practitioners. VC dimension seems a rough measure of entropy and might correlate somewhat with "total size of model". think it is useful for ML practitioners to have some basic knowledge of TCS & its povs. however knowledge of them might be more relevant to those who are attempting to build new more effective models in the sense of research into ML & not as much tuning individual models for max performance (aka kaggle competitions) – vzn Dec 29 '19 at 16:26
  • 1
    Possibly relevant: https://cs.stackexchange.com/q/75327/755 – D.W. Dec 31 '19 at 07:04

1 Answers1

4

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 Guedj, who provides a nice overview of the topic, shows a certain bound that can be used to design Bayesian estimators. An advantage of PAC-Bayes is that you get bounds on the generalization ability of the Bayesian estimator, so you do not necessarily need to test your estimator on a test dataset. Sections 5 and 6 of the paper go into the details of the real-world applications of PAC-Bayes.

See e.g. Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm (2015) by P. Germain et al. for a specific application of PAC-Bayes. There's also the related Python implementation.

See also these related slides and this blog post (by the same author and John Shawe-Taylor) that will point you to their video tutorials about the topic.

The VC dimension can also be useful in practice. For example, in the paper Model Selection via the VC Dimension (2019) M. Mpoudeu et al. describe a method for model selection based on the VC dimension.

nbro
  • 39,006
  • 12
  • 98
  • 176