What the examples leave open.
Twelve objects, four attributes, one binary label. Choose the positives and negatives; the lab enumerates all 441 rules in the language and shows the version space — the rules that survive, the two boundaries, and the objects the examples do not decide.
The rule-induction lab
The dataset
Each row is an object with four attributes and a label. A rule in this lab allows a subset of values for each attribute; an object is covered when every attribute value is allowed. The language contains 7 × 7 × 3 × 3 = 441 such rules.
| Object | Colour | Shape | Size | Material | Label | Version space |
|---|
Click P, N, or ? to relabel an object. Every change re-enumerates the hypothesis space. The verdict column is not the true label; it is what the current version space implies — if all consistent rules agree.
Loading the version space.
Version space
A greedy learner
Sequential covering, top-down. Start from the most general rule; add one equality test at a time, preferring the test that keeps the most uncovered positives while excluding at least one negative; stop when the rule is pure; remove the positives it covers; repeat.
Three boundaries, one lesson.
The most specific rule
S is the least general generalization of the positives: the rule that commits to every attribute value the positives share. It is the safest rule, and usually the least useful on unseen objects.
The most general rules
G contains the rules that cannot be generalized further without covering a negative. There can be several, and they can disagree on unlabelled objects. That disagreement is the ambiguity the examples leave open.
Between S and G
Every consistent rule lies between a most specific and a most general boundary. The gap is not noise; it is the exact shape of what the data does not determine. More examples shrink it — or expose that the language cannot express the rule.
It shows an exhaustive version space for a finite, attribute-value language: 441 rules, all checked against the labels. It does not show that the true rule is in the language, that the labels are correct, or that a consistent rule will generalize. A relational or program language would be larger, and the same logic would apply. The guide takes the same example apart and connects it to ILP and program synthesis.
← Read the version-space section · Back to Lecture 13 · Slides →