Realizable Learning
In the realizable case, the answer is guaranteed to be yes: at least one such rectangle exists.
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 Rn 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 Hn |
|---|---|---|
| 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 |
The defining distinction is the orientation of the sides.
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?
- 1Check 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.
- 2Check 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 Hn 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
Common mistake Treating an axis-aligned rectangle as any rectangle in Rn
What it looks likeA candidate rectangle is rotated, but its sides are not parallel to the coordinate axes.
Why it failsThe hypothesis class in this topic is the class of axis-aligned rectangles.
Do this insteadFirst verify that the candidate's sides are parallel to the axes.
Common mistake Checking only most of the training examples
What it looks likeA candidate agrees with all but one labeled example.
Why it failsConsistency requires h(x_i) = y_i for every training example.
Do this insteadInspect the complete training set and reject the candidate if even one example disagrees.
Common mistake Assuming the consistent rectangle must be unique
What it looks likeSeveral candidate rectangles have zero training error.
Why it failsThe ERM goal is to find one valid hypothesis; the source does not require a unique output.
Do this insteadAccept any member of H^n that agrees with every training label.
Common mistake Confusing the realizable assumption with an automatic answer
What it looks likeBecause the training set is realizable, every candidate rectangle is treated as correct.
Why it failsThe assumption guarantees that at least one consistent rectangle exists, not that every rectangle is consistent.
Do this insteadStill test each candidate against every labeled example.
Practice Check
A training set is known to be realizable for Hn. 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 Hn and have zero training error.
Practice Resolution
Use the stated properties of the two candidates to determine which one satisfies the ERM goal.
- 1Reject candidate A
Its one disagreement means it does not satisfy h(x_i) = y_i for every training example.
- 2Accept candidate B
It agrees with every label and is an axis-aligned rectangle, so it belongs to Hn and has zero training error.
Candidate B can be returned by the ERM rule.
Key Takeaways
- 1An axis-aligned rectangle in Rn has sides parallel to the coordinate axes.
- 2A training set is realizable when at least one axis-aligned rectangle agrees with every label.
- 3Consistency means h(x_i) = y_i for every training example, not merely for most examples.
- 4In the realizable case, ERM seeks a member of Hn with zero training error.
- 5A valid answer identifies one consistent rectangle; uniqueness is not required.
At a glance
- Axis-aligned rectangles are defined by sides parallel to the coordinate axes.
- Realizability guarantees that at least one hypothesis in Hn 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.