Introduction to PAC Learning

From Examples to a Guarantee

PAC learning is a precise way to describe when a hypothesis class H can be learned by an algorithm. It does not merely say that an algorithm performs well on some examples. It specifies how many labeled examples are needed, how accurate the returned hypothesis should be, and how confident we should be in that accuracy.

The central process is this: examples come from a distribution D over an instance space X and receive labels from a target function f. A learning algorithm receives enough labeled examples and returns a hypothesis h from the hypothesis class H. PAC learnability requires a guarantee about the loss of h, not just its behavior on the examples used for training.

The PAC Symbols

Each symbol in the definition has a distinct job. H is the hypothesis class: the collection of hypotheses the learning system can consider. The function m_H determines the sample threshold. For chosen accuracy epsilon and confidence delta, the learner must receive at least m_H(epsilon, delta) examples. D is a distribution over the instance space X, and f is the labeling function that supplies the labels. The algorithm returns h, the learned hypothesis.

Following the Guarantee

Why Realizability Matters

The realizable assumption is a condition connecting H, D, and f. It says that the target labeling situation is compatible with the hypothesis class being considered. Under this assumption, the class contains a hypothesis capable of representing the target labeling behavior, so a hypothesis with zero training error can exist for the labeled examples.

This condition matters because the stated PAC guarantee is made for the realizable setting. Without it, a learner might be asked to find a hypothesis in H that agrees with labels that no hypothesis in H can represent. In that situation, zero training error is not guaranteed to be achievable, so the definition would need a different assumption or guarantee.

Feature Learning as Representation

A machine learning method cannot work directly with an unspecified instance space. It needs instances to be expressed in a feature representation. Feature learning addresses this preparation step by learning a function psi that maps instances from X into d-dimensional feature vectors.

Before the mapping, an item is described only as an element of X. After the mapping, the same item is available as a vector with d coordinates. The learned function psi is therefore a transformation that creates a usable description of each instance. The purpose is to produce a representation that supports a suitable hypothesis class for the task.

Learning Versus Selecting Features

Feature selection and feature transformation assume that a feature space has already been designed. Selection chooses among available features, while transformation changes individual features. Feature learning starts one step earlier: it learns how instances from X should be represented in the first place.

Polynomial Features

Polynomial regression illustrates the general pattern of constructing features first and training a linear predictor on top of them. An input x can be mapped into the constructed feature vector consisting of 1, x, x squared, and continuing through x to the power of d. The monomial construction supplies the representation; the later linear predictor operates on that representation.

Common Misreadings

• Treating PAC learning as a statement about one fixed dataset.

  The guarantee is stated relative to every allowed distribution D and every allowed target function f under the realizable assumption.

  Fix: Track the distribution, target function, accuracy, confidence, sample threshold, and returned hypothesis together.

• Confusing epsilon with delta.

  Epsilon bounds the permitted loss, while delta controls the probability associated with the guarantee.

  Fix: Remember: epsilon describes accuracy and delta describes confidence.

• Assuming m_H is automatically a numerical sample count.

  m_H is the function that supplies the threshold for the chosen epsilon and delta.

  Fix: State the condition m at least m_H(epsilon, delta) unless a specific bound has been provided.

• Calling feature selection feature learning.

  Selection starts with an existing feature space, while feature learning learns a mapping from instances into a feature vector space.

  Fix: Ask whether the procedure begins with instances in X or with a feature space already defined.

• Treating the polynomial predictor as the feature mapping.

  The monomial construction creates the representation; the predictor acts after that representation exists.

  Fix: Separate the mapping step from the prediction step.

Practice Check

Key Takeaways

1. PAC learnability combines a hypothesis class H, a sample-complexity function m_H, and a learning algorithm.
2. When m is at least m_H(epsilon, delta), the returned hypothesis h must have loss at most epsilon with probability at least 1 minus delta.
3. The guarantee is stated for distributions D and target functions f under the realizable assumption.
4. Feature learning learns a mapping psi from instances in X into d-dimensional feature vectors, unlike selection or transformation within a predefined feature space.
5. Polynomial regression separates feature construction, such as 1, x, x², ..., xᵈ, from the later linear prediction step.