Learnability
Learnability asks whether this selected hypothesis can remain accurate beyond the particular sample used to choose it.
From Samples to Hypotheses
A learning algorithm receives a training sample and must choose a hypothesis from a hypothesis class. The hypothesis is the rule the learner uses after training. Learnability asks whether this selected hypothesis can remain accurate beyond the particular sample used to choose it.
The learning rule is not the hypothesis itself. It is the mapping that uses the sample to produce the hypothesis.
Consistency and Its Quantifiers
Consistency evaluates whether a learning rule reaches a required performance level with high probability once the sample is sufficiently large. The guarantee is described relative to an accuracy level, a confidence level, a hypothesis class, and a family of data-generating distributions.
Reading a Consistency Statement
Suppose a learning rule is evaluated using an accuracy level epsilon, a confidence parameter delta, a hypothesis class, and a data-generating distribution.
- 1Identify the input
The training sample is drawn from the data-generating distribution.
- 2Apply the rule
The learning rule maps that sample to a hypothesis from the hypothesis class.
- 3Interpret the threshold
The sample must be at least as large as a permitted threshold. That threshold may depend on the particular distribution.
- 4Interpret the probability
The required performance condition holds with the stated high probability over the random training sample.
Consistency is a conditional guarantee: once the sample reaches the permitted size for the situation, the selected hypothesis reaches the required performance with high probability.
Distribution-Dependent Requirements
A consistency requirement allows the necessary sample size to depend on the underlying probability distribution that generated the data. This is different from demanding one universal sample-size bound that works equally across every possible data source.
| Question | Distribution-dependent consistency | Uniform sample-size requirement |
|---|---|---|
| May the threshold vary with the data source? | Yes | No |
| What remains fixed in the statement? | The other specified inputs, such as the accuracy and confidence levels | The bound is required to work across distributions |
| What is the key distinction? | The rule eventually meets the requirement for the particular situation | One sample-size bound is demanded across the distributions under consideration |
The distinction concerns how the sample-size threshold is allowed to depend on the distribution.
Generated example: Imagine evaluating the same learning rule under two different data-generating distributions. A distribution-dependent consistency statement permits the sufficient sample size for the first distribution to differ from the sufficient sample size for the second. This example illustrates the logical permission in the definition; it does not claim that either named distribution is inherently easier or harder.
PAC Accuracy and Confidence
PAC means probably approximately correct: a hypothesis has bounded error with high confidence.
Approximately correct refers to the accuracy requirement, represented by an error tolerance such as epsilon. Probably refers to the probability guarantee, represented through a confidence parameter such as delta. The guarantee is probabilistic because the training sample is random. It does not claim that every possible sample produces the desired accuracy; it says that the desired accuracy holds with probability at least 1 minus delta over samples of the required size.
What do you think happens?
A PAC guarantee is stated for samples of the required size. Does it promise that every possible training sample gives an accurate hypothesis?
Reveal answer
No, the accuracy guarantee holds with high probability over random samples.
The guarantee concerns the random choice of the training sample. It does not say that every possible sample gives the required performance.
ERM over a Finite Class
Empirical risk minimization, or ERM, chooses a hypothesis with minimum empirical risk from a finite hypothesis class. Empirical risk is the hypothesis's performance as measured on the training sample. ERM therefore compares the available hypotheses on that sample and selects one whose training-sample risk is smallest.
A Simple ERM Selection
A finite hypothesis class contains three candidate hypotheses. On the training sample, their empirical risks are represented as low, medium, and high.
- 1List candidates
ERM considers the hypotheses in the finite hypothesis class.
- 2Evaluate the sample
Each candidate is assessed using its empirical risk on the training sample.
- 3Compare results
The empirical risks are compared with one another.
- 4Select
ERM chooses a hypothesis with minimum empirical risk.
The selected hypothesis is an ERM hypothesis because it has minimum empirical risk within the finite class.
ERM describes the selection rule, not a claim that the selected hypothesis is automatically accurate on unseen data. The PAC guarantee requires additional conditions, including a sufficiently large sample and realizability.
Realizability and the PAC Result
Realizability requires at least one zero-risk hypothesis in the hypothesis class.
The realizability assumption says that the target labeling rule is represented by some hypothesis in the class. In this setting, the class contains at least one hypothesis with zero risk. This matters because the finite-class PAC result is stated for distributions and labeling functions for which such a zero-risk hypothesis exists.
The finite-class result connects three ideas. Realizability describes what the hypothesis class can represent. ERM describes how the learner selects a hypothesis from that class. A sufficiently large sample makes it possible to state that every ERM hypothesis is probably approximately correct under realizability.
Common Misreadings
Common mistake Treating consistency as a guarantee for every sample size.
What it looks likeAssuming that the required accuracy must hold even when the sample is smaller than the permitted threshold.
Why it failsThe statement is conditional on the sample being sufficiently large.
Do this insteadCheck the sample-size condition before applying the performance guarantee.
Common mistake Assuming consistency requires one universal sample size across all distributions.
What it looks likeReading the requirement as though the same threshold must work equally for every possible data source.
Why it failsConsistency allows the threshold to depend on the data-generating distribution.
Do this insteadDistinguish a distribution-dependent threshold from a uniform bound across distributions.
Common mistake Interpreting PAC as correctness on every possible training sample.
What it looks likeClaiming that no random sample can produce a hypothesis outside the required error level.
Why it failsThe PAC guarantee is probabilistic over the random training sample.
Do this insteadState that the required accuracy holds with high probability, at least 1 minus delta.
Common mistake Confusing ERM with the PAC guarantee itself.
What it looks likeSaying that choosing minimum empirical risk automatically proves accuracy beyond the training sample.
Why it failsERM specifies how a hypothesis is selected. The finite-class PAC result also relies on a sufficiently large sample and realizability.
Do this insteadSeparate the selection rule from the conditions that support its PAC guarantee.
Common mistake Ignoring realizability.
What it looks likeApplying the stated finite-class PAC result when no zero-risk hypothesis exists in the class.
Why it failsThe result is stated for distributions and labeling functions for which a zero-risk hypothesis exists.
Do this insteadCheck that the target labeling rule is represented by some hypothesis in the class.
Check Your Understanding
A finite hypothesis class contains a zero-risk hypothesis. A learning rule receives a training sample and selects a minimum-empirical-risk hypothesis. Explain which additional sample-related condition is needed before you can describe the selected hypothesis as probably approximately correct, and explain what the probability in that statement refers to.
Hints
- Use the meanings of realizability, ERM, and PAC.
- Remember that the training sample is random.
- Mention both sufficiently large sample size and high-probability accuracy.
Practice Answer
Explain when the ERM hypothesis can receive the finite-class PAC interpretation.
- 1Check representation
The hypothesis class must satisfy realizability: it contains at least one zero-risk hypothesis.
- 2Check selection
ERM selects a hypothesis with minimum empirical risk from the finite class.
- 3Check sample size
The sample must be sufficiently large for the stated finite-class result.
- 4Interpret probability
The desired accuracy holds with high probability over the random training sample, rather than for every possible sample.
Under realizability and a sufficiently large sample, the finite-class ERM hypothesis is probably approximately correct.
Key Takeaways
- 1A learning rule maps a training sample to a hypothesis from a hypothesis class.
- 2Consistency asks whether the required performance is reached with high probability once the sample is sufficiently large.
- 3The sample-size threshold in a consistency statement may depend on the data-generating distribution.
- 4PAC means bounded error with high confidence; its probability statement concerns random training samples.
- 5For a finite hypothesis class, ERM selects a minimum-empirical-risk hypothesis, and under realizability with a sufficiently large sample, every ERM hypothesis is probably approximately correct.
At a glance
- Learnability studies whether a learning rule can produce a hypothesis that meets a required performance level with high probability.
- Consistency permits the sufficient sample size to depend on the distribution that generated the data.
- PAC combines an accuracy requirement with a high-probability guarantee over random training samples.
- ERM chooses a minimum-empirical-risk hypothesis from a finite class.
- Realizability and a sufficiently large sample support the finite-class PAC guarantee for ERM.