Course / Lectures / Lecture 13 / Lab Lab 13

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.

~10 min play 441 rules enumerated 3 presets No install · runs in the browser

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.

Twelve objects · P positive · N negative · ? unlabelled
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.

WHAT TO NOTICE

Three boundaries, one lesson.

BOUNDARY 01 · S

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.

BOUNDARY 02 · G

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.

BOUNDARY 03 · THE GAP

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.

What this shows — and what it does not

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 →