Skip to content

Independent AI & deep-tech news

Data Science

Introduction to Computational Learning Theory

Introduction to Computational Learning Theory
On this page
  1. Key takeaways
  2. What is computational learning theory?
  3. What questions does it try to answer?
  4. How do PAC learning and the VC dimension compare?
  5. What is PAC learning?
  6. What is the VC dimension?
  7. Frequently asked questions
  8. Conclusion

Computational learning theory (CoLT) is the branch of machine learning that uses formal mathematical methods to study learning tasks and learning algorithms. It asks how hard a learning problem is, how much data a learner needs, and how well a fitted model can be expected to perform on new examples.

A practitioner does not need deep knowledge of this field to get good results on a wide range of problems. A high-level grasp of its main ideas still gives useful insight into what happens when a model is fit to data.

Key takeaways

  • Computational learning theory applies formal methods from theoretical computer science to learning tasks and learning algorithms.
  • PAC (probably approximately correct) learning quantifies how difficult a learning task is.
  • The VC dimension quantifies the capacity of a learning algorithm’s hypothesis space.
  • The theory is most often developed for supervised learning, and its theorems can be hard to apply directly to real problems.

What is computational learning theory?

Computational learning theory studies learning with the tools of theoretical computer science. Its goal is to characterize how difficult specific learning tasks are.

It is closely related to statistical learning theory (SLT), which also uses formal methods to study learning algorithms. A simple way to separate the two is shown below.

  • Computational learning theory: the formal study of learning tasks.
  • Statistical learning theory: the formal study of learning algorithms.

This split between tasks and algorithms is somewhat arbitrary, and in practice the two fields overlap a great deal.

The emphasis is usually on supervised learning. Because a rigorous analysis of real problems and real algorithms is difficult, theorists often simplify the setting, for example by focusing on binary classification or on simple rule-based models. As a result, the theorems can be hard to apply directly to real-world problems and algorithms.

What questions does it try to answer?

Typical questions include the following.

  • How can we tell whether a model is a good approximation of the target function?
  • Which hypothesis space should be used?
  • How can we tell whether a solution is locally or globally good?
  • How can overfitting be prevented?
  • How many data examples are needed?

The theory gives a useful grounding for what is happening when models are fit to data, and it can shed light on the methods involved. Two of the most widely discussed areas are PAC learning and the VC dimension.

How do PAC learning and the VC dimension compare?

Aspect PAC learning VC dimension
Focus The theory of learning problems The theory of learning algorithms
Core question How much effort and data are needed to find a good hypothesis? How expressive is the hypothesis space?
Developed by Leslie Valiant Vladimir Vapnik and Alexey Chervonenkis
Part of Computational learning theory Statistical learning theory (VC theory)

What is PAC learning?

PAC stands for “probably approximately correct.” It is a theoretical framework developed by Leslie Valiant and is often considered the main sub-field of computational learning theory.

In supervised learning, the goal is to approximate an unknown mapping from inputs to outputs. The true mapping is not known, but it is assumed to exist, and examples produced by it are available. PAC learning is concerned with how much computational effort is needed to find a hypothesis, meaning a fitted model, that closely matches this unknown target function.

A hypothesis is judged by its predictions on new data, which is its generalization error. A hypothesis that gets most predictions right has a small generalization error and is therefore a good approximation of the target function.

The name reflects this probabilistic language. A hypothesis tries to approximate the target function, and it is probably good if its generalization error is low. A PAC learning algorithm is one that returns such a hypothesis.

Using formal methods, a maximum acceptable generalization error can be set for a supervised learning task. The theory can then estimate how many samples from the problem domain are needed to find a PAC hypothesis. A hypothesis space, which is the set of models an algorithm can fit, is considered efficiently PAC learnable if an algorithm can find a PAC hypothesis in polynomial time.

What is the VC dimension?

Vapnik-Chervonenkis (VC) theory is a framework developed by Vladimir Vapnik and Alexey Chervonenkis. It seeks to quantify the capacity of a learning algorithm and is considered the main part of statistical learning theory. Its best-known component is the VC dimension.

The VC dimension measures the complexity of a hypothesis space, which is the set of models that could be fit given a representation and a learning algorithm. Rather than counting hypotheses, it measures how many examples from the problem the hypotheses in the space can discriminate between.

Formally, the VC dimension is the largest number of examples that the hypothesis space can “shatter.” A set of points is shattered when hypotheses in the space can separate them in every possible way, so the labels come out correct whatever those labels happen to be. Whether a set is shattered depends on the hypothesis space and the number of points.

A simple example with lines

A line can shatter three points on a two-dimensional plane. Any placement of three points with binary class labels (0 or 1) can be separated correctly by a line.

Some placements of four points with binary labels cannot be separated correctly by a single line, so a line cannot shatter four points. A different model, such as an ellipse, would be needed for those cases. The VC dimension is used within the PAC learning framework.

Frequently asked questions

Do machine learning practitioners need to know computational learning theory?

Not in great depth. A high-level understanding of the main ideas is enough to give useful context for fitting models to data.

What is the difference between PAC learning and the VC dimension?

PAC learning is the theory of learning problems, while the VC dimension is the theory of learning algorithms. The VC dimension is used as part of the PAC learning framework.

What does “shatter” mean?

A hypothesis space shatters a set of points if it can separate them correctly for every possible assignment of labels. The VC dimension is the size of the largest set it can shatter.

Why are the theorems hard to use on real problems?

Formal analysis is rigorous, so it is usually done on simplified cases such as binary classification. Applying the results to real problems and algorithms can be difficult.

Conclusion

Computational learning theory gives machine learning a mathematical foundation for asking how hard a learning task is and how much data it needs. PAC learning addresses learning problems, and the VC dimension addresses the capacity of learning algorithms.

Practitioners can succeed without mastering the details, but a working sense of these ideas helps explain why models generalize or fail to.

Written by

Manika Sharma

16 articles on DeepTechBytes