Realizable Learning
Axis-aligned rectangles are rectangles in R^n whose sides are parallel to the axes.
From Labels to a Rectangle
Realizable learning begins with a labeled training set and a hypothesis class. Here, the hypothesis class H^n consists of axis-aligned rectangles. The central question is whether one rectangle can agree with every label in the training set. In the realizable case, the answer is guaranteed to be yes: at least one such rectangle exists.
Write the training set as S = (x_1, y_1), ..., (x_m, y_m). A rectangle h is consistent with S when h(x_i) = y_i for every training example. The word every is essential. Matching most labels is not enough for consistency in the realizable setting.
What Axis-Aligned Means
An axis-aligned rectangle is a rectangle in R^n whose sides are parallel to the coordinate axes. The definition describes the rectangle by its orientation: its sides remain aligned with the axes rather than being rotated away from them.
| Candidate shape | Relationship to coordinate axes | Relevant to H^n |
|---|---|---|
| Axis-aligned rectangle | Its sides are parallel to the axes | Yes |
| Rectangle with a different orientation | Its sides are not parallel to the axes | Not an axis-aligned rectangle |
Checking a Candidate
To check a candidate rectangle, examine the training examples one at a time. For each x_i, determine the hypothesis value h(x_i) produced by the candidate and compare it with the example's label y_i. The candidate passes only if h(x_i) = y_i for every index i in the training set.
Testing Complete Consistency
A generated training set contains four labeled examples. Candidate rectangle A agrees with the labels of the first three examples but disagrees with the label of the fourth. Candidate rectangle B agrees with all four examples. Which candidate is consistent?
Check candidate A: The first three checks pass, but the fourth check fails. Because consistency must hold for every training example, candidate A is not consistent.
Check candidate B: All four checks pass, so h(x_i) = y_i for every example in this generated training set.
Candidate B is consistent with the complete training set. Candidate A is not.
The ERM Selection Goal
The ERM rule is applied here under the realizable-case assumption. Start with the labeled training set, consider the hypothesis class H^n of axis-aligned rectangles, and search for a member that agrees with every label. Since such a rectangle is known to exist, the desired output is a hypothesis with zero training error.
ERM does not require a uniquely determined rectangle in this setting. If several axis-aligned rectangles have zero training error, any one of them satisfies the stated goal, provided it belongs to H^n and obeys h(x_i) = y_i for all training examples.
Membership and Labels
The consistency condition connects a point's relationship to the candidate rectangle with its training label. For each point x_i, the candidate produces h(x_i). The candidate is acceptable only when that produced value matches y_i. Thinking in this point-by-point way prevents a common error: judging a rectangle by its overall appearance instead of checking its prediction on every labeled example.
Common Mistakes
Treating an axis-aligned rectangle as any rectangle in R^n
The hypothesis class in this topic is the class of axis-aligned rectangles.
Fix:
First verify that the candidate's sides are parallel to the axes.Checking only most of the training examples
Consistency requires h(x_i) = y_i for every training example.
Fix:
Inspect the complete training set and reject the candidate if even one example disagrees.Assuming the consistent rectangle must be unique
The ERM goal is to find one valid hypothesis; the source does not require a unique output.
Fix:
Accept any member of H^n that agrees with every training label.Confusing the realizable assumption with an automatic answer
The assumption guarantees that at least one consistent rectangle exists, not that every rectangle is consistent.
Fix:
Still test each candidate against every labeled example.
Practice Check
A training set is known to be realizable for H^n. You are given two candidate axis-aligned rectangles. Candidate A agrees with every label except one. Candidate B agrees with every label. Which candidate can be returned by the ERM rule, and what two conditions must your answer verify?
Hints
- Consistency is evaluated across the complete training set.
- The returned hypothesis must belong to H^n and have zero training error.
Practice Resolution
Use the stated properties of the two candidates to determine which one satisfies the ERM goal.
Reject candidate A: Its one disagreement means it does not satisfy h(x_i) = y_i for every training example.
Accept candidate B: It agrees with every label and is an axis-aligned rectangle, so it belongs to H^n and has zero training error.
Candidate B can be returned by the ERM rule.
Key Takeaways
- An axis-aligned rectangle in R^n has sides parallel to the coordinate axes.
- A training set is realizable when at least one axis-aligned rectangle agrees with every label.
- Consistency means h(x_i) = y_i for every training example, not merely for most examples.
- In the realizable case, ERM seeks a member of H^n with zero training error.
- A valid answer identifies one consistent rectangle; uniqueness is not required.
Key Takeaways
- Axis-aligned rectangles are defined by sides parallel to the coordinate axes.
- Realizability guarantees that at least one hypothesis in H^n agrees with the complete training set.
- To test a candidate, compare h(x_i) with y_i for every labeled example.
- The ERM rule returns one axis-aligned rectangle with zero training error.
- A single disagreement makes a candidate inconsistent.