Learnability
Consistency evaluates whether a learning rule reaches a required performance level with high probability once the sample is sufficiently large.
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.
Identify the input: The training sample is drawn from the data-generating distribution.
Apply the rule: The learning rule maps that sample to a hypothesis from the hypothesis class.
Interpret the threshold: The sample must be at least as large as a permitted threshold. That threshold may depend on the particular distribution.
Interpret 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 |
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
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.
List candidates: ERM considers the hypotheses in the finite hypothesis class.
Evaluate the sample: Each candidate is assessed using its empirical risk on the training sample.
Compare results: The empirical risks are compared with one another.
Select: 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
Treating consistency as a guarantee for every sample size.
The statement is conditional on the sample being sufficiently large.
Fix:
Check the sample-size condition before applying the performance guarantee.Assuming consistency requires one universal sample size across all distributions.
Consistency allows the threshold to depend on the data-generating distribution.
Fix:
Distinguish a distribution-dependent threshold from a uniform bound across distributions.Interpreting PAC as correctness on every possible training sample.
The PAC guarantee is probabilistic over the random training sample.
Fix:
State that the required accuracy holds with high probability, at least 1 minus delta.Confusing ERM with the PAC guarantee itself.
ERM specifies how a hypothesis is selected. The finite-class PAC result also relies on a sufficiently large sample and realizability.
Fix:
Separate the selection rule from the conditions that support its PAC guarantee.Ignoring realizability.
The result is stated for distributions and labeling functions for which a zero-risk hypothesis exists.
Fix:
Check 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.
Check representation: The hypothesis class must satisfy realizability: it contains at least one zero-risk hypothesis.
Check selection: ERM selects a hypothesis with minimum empirical risk from the finite class.
Check sample size: The sample must be sufficiently large for the stated finite-class result.
Interpret 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
- A learning rule maps a training sample to a hypothesis from a hypothesis class.
- Consistency asks whether the required performance is reached with high probability once the sample is sufficiently large.
- The sample-size threshold in a consistency statement may depend on the data-generating distribution.
- PAC means bounded error with high confidence; its probability statement concerns random training samples.
- For 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.
Key Takeaways
- 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.