Are boundary sets probability distributions?

No. They represent extremal consistent hypotheses without assigning probabilities.

Can a negative example change the general boundary?

Yes. It can force general candidates to specialize or be removed.

Does a unique remaining hypothesis guarantee future accuracy?

No. Its success depends on the data, representation and relationship to future cases.

AI Glossary / Graphs and symbolic AI / Intermediate

Boundary set

Definition

In version-space learning, a boundary set contains the most specific or most general hypotheses still consistent with the observed examples. The specific boundary S and general boundary G together describe the remaining candidate hypotheses through a general-to-specific ordering.

What it means

A learner may have several rules that explain all examples seen so far. Rather than choosing one immediately or listing every possibility, version-space learning represents the candidates using their outer limits in a defined hypothesis space.

A more general hypothesis labels at least every instance labeled positive by a more specific hypothesis, and possibly others. This is an ordering by coverage, not by confidence, accuracy or sentence length.

S contains consistent hypotheses that cannot be made more specific within the chosen space while retaining consistency. G contains those that cannot be made more general while retaining consistency. Either boundary can contain several incomparable hypotheses, so boundary set does not necessarily mean a single rule.

This sense differs from a geometric classification boundary separating points in a feature plot. It describes the limits of a set of possible rules.

How it works

Candidate elimination starts with boundaries representing the initial hypothesis space. Each labeled example removes hypotheses that disagree with it.

A positive example can require generalizing members of S so they cover the example, while removing members of G that fail to cover it. A negative example can require specializing members of G so they exclude it, while removing members of S that incorrectly cover it. Updates retain only candidates compatible with the opposite boundary and remove redundant boundary members.

When the boundaries are well defined, a hypothesis is in the version space if it lies between some specific-boundary member and some general-boundary member. The boundaries can therefore represent many internal candidates without storing them individually.

If all remaining hypotheses agree on a new instance, their shared prediction follows from the current version space. If they disagree, the data and hypothesis language have not resolved that case.

The classic method assumes consistent labels and an adequate hypothesis space. Contradictory examples or a target outside the allowed language can empty the version space. Boundary sets can also become large; compact representation is a possibility, not a universal small-memory guarantee.

Three practical examples

A teaching system tracks every simple product-selection rule still compatible with a sequence of accepted and rejected examples.
A rule-learning study uses disagreement among surviving hypotheses to identify informative examples for further labeling.
A specification exercise shows stakeholders how several different rules can agree with the current examples yet disagree on an unseen case.

Think of it this way

Think of keeping the tightest and loosest descriptions still permitted by a set of observations. Other permitted descriptions lie between them in what they accept.

The analogy is not a numerical confidence interval. Hypotheses can be only partially ordered, producing several boundary members, and the method does not assign a probability that the true rule lies between them.

Worked example

Learning a rule about two attributes

Suppose items have color {red, blue} and shape {round, square}. The hypothesis language uses conjunctions of attribute requirements, where ? means any value. Thus (red, ?) accepts every red item, while (?, round) accepts every round item.

After observing positive example (red, round), the specific boundary is S = {(red, round)} and the general boundary is G = {(?, ?)}. Several candidate rules remain, including (red, ?) and (?, round).

Now observe negative example (blue, round). To exclude it while retaining the positive example, the most general surviving rule is (red, ?). G becomes {(red, ?)}, while S remains {(red, round)}.

At this point, the two surviving hypotheses disagree on (red, square): the specific rule rejects it, and the general rule accepts it. The available examples therefore do not determine its label.

If (red, square) is then labeled positive, S generalizes to (red, ?), matching G. The version space has one hypothesis in this chosen language. That does not establish a universal truth about red objects; it identifies the unique rule consistent with these examples among the allowed candidates.

Illustrative case study

Fictional case: Cedar Selection gathers examples of items staff want included in a catalog. After two examples, a prototype presents one plausible rule as settled policy.

A version-space review exposes another consistent rule that differs on a square item. Staff label that case and discuss whether shape was ever intended to matter. The team also checks whether its simple conjunction language can express the actual policy's exceptions.

The lesson is that agreement with current examples can conceal unresolved alternatives. Boundary sets make that ambiguity visible without pretending to measure confidence in the staff's labels.

Common misconceptions and mistakes

S and G are necessarily single hypotheses. Each is a set and can contain incomparable members.
A more general hypothesis is more accurate. Generality concerns coverage, not quality.
Matching boundaries prove the rule is true in the world. They identify agreement within the selected hypothesis space and data.
An empty version space means learning is finished. It signals incompatibility that needs investigation.
Boundary representation is always tiny. Complex spaces can produce large boundaries.

Business use

Boundary sets are useful for explaining inductive uncertainty and for small, inspectable rule-learning exercises. They encourage teams to distinguish examples that merely confirm current agreement from examples that separate remaining possibilities.

Before applying the method, document the hypothesis language and label assumptions. Keep noisy or disputed examples visible. When predictions remain ambiguous, report that the candidate rules disagree and identify a case that could resolve the disagreement. Broader learning systems may need noise-tolerant alternatives rather than exact candidate elimination.

Check your understanding

S contains (red, round) and G contains (red, ?). Can the learner give a unanimous positive prediction for a red square?

Answer: No. The boundary hypotheses disagree on that instance, so the current version space does not determine a unanimous label.

Related terms

Learn next

Repeat the worked sequence but label the red square negative. Determine the new boundaries and compare the result. Then add two identical instances with opposite labels and explain why no deterministic hypothesis can satisfy both under the stated assumptions.

Sources

Tom Mitchell, Machine Learning, Chapter 2, version-space boundary definitions and candidate elimination, author-hosted text: https://www.cs.cmu.edu/~tom/files/MachineLearningTomMitchell.pdf

AIMA glossary, boundary set: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

The two-attribute learning sequence and fictional catalogue review are original illustrations.

Previous: Boundary leakage Next: Boundary tones