Why can G contain several hypotheses?

The generality ordering is usually partial. Two consistent rules can each be maximally general without either containing the other.

What is the relationship to S?

S marks the most specific consistent boundary; G marks the most general. Together they can characterize the version space under the relevant assumptions.

Does G assign probabilities?

No. Standard boundary membership records consistency and generality, not a probability distribution over hypotheses.

AI Glossary / Graphs and symbolic AI / Advanced

G-set

Definition

The G-set is the general boundary of a version space in concept learning. It contains the maximally general hypotheses that remain consistent with all observed training examples, relative to the chosen hypothesis language and generality ordering.

What it means

A version space contains every candidate hypothesis that correctly classifies the examples seen so far. Instead of listing all candidates, some learning methods represent the space using two boundaries: the most general consistent hypotheses in G and the most specific consistent hypotheses in S.

General means accepting at least all the instances accepted by a more specific hypothesis. It does not mean being more accurate, more probable or expressed with fewer words. Several hypotheses can be incomparable, so G can contain more than one member.

This entry uses the machine-learning meaning found in version-space methods. The same notation has unrelated meanings elsewhere, including a set equipped with a group action in mathematics.

How it works

Begin with the allowed hypothesis space. In a simple conjunction language, each attribute can specify a particular value or a wildcard that accepts any value. The all-wildcard hypothesis is maximally general, if the language includes it.

As labeled examples arrive, candidate elimination updates the boundaries. Positive examples remove G members that reject them. Negative examples force overly general G members to be replaced by appropriate minimal specializations, while respecting consistency and the S boundary.

Redundant boundary members are removed. Under the version-space representation assumptions, the surviving hypotheses lie between members of S and G in the generality ordering. An empty space means no allowed hypothesis fits every observation; this can result from inconsistent labels or an inadequate hypothesis language. It does not prove that the real-world task has no underlying pattern.

Three practical examples

A teaching system shows which general classification rules remain possible after a small sequence of labeled examples.
A rule-discovery prototype exposes alternative explanations that all fit the current records rather than prematurely selecting one.
An interactive learning exercise chooses a new example on which surviving hypotheses disagree, illustrating how additional labels reduce uncertainty.

Think of it this way

Think of several broad explanations that still fit the evidence. The G-set marks those that cannot be made any broader without contradicting an observation or leaving the allowed explanation language.

The analogy does not turn the surviving explanations into probabilities. Their presence means consistency with the examples, not that each has equal likelihood or that any is guaranteed to classify future cases correctly.

Worked example

Watching the general boundary change

Use two attributes: color is red or blue, and shape is circle or square. A hypothesis is a conjunction of attribute constraints, with a wildcard meaning any value. Include an empty concept for initialization.

After the positive example red circle, the specific boundary is red AND circle, while the general boundary remains any color AND any shape.

Now observe the negative example blue square. The all-wildcard hypothesis is inconsistent. Its relevant minimal consistent specializations are red with any shape, and any color with circle. Thus G contains two members: red/* and */circle. The more specific red/circle hypothesis remains in the version space but is not a G member because consistent hypotheses generalize it.

A third observation, positive red square, eliminates */circle. It also generalizes S to red/*. G and S now both contain red/*, leaving one concept in this hypothesis language.

This does not establish that color alone determines the true concept outside the examples. A richer language or future evidence could change the learning problem and its conclusions.

Illustrative case study

The fictional Maple Rules team demonstrates version-space learning on labeled product examples. Its first display presents the broadest surviving rule as the answer, hiding that another incomparable general rule also fits the data.

The team changes the display to show both G members and selects an example where they disagree. After an expert supplies the label, one alternative disappears. Later, a contradictory label for an identical feature description empties the version space.

Rather than inventing a surviving rule, Maple reviews label quality and the adequacy of the recorded attributes. The scenario demonstrates explicit hypothesis uncertainty and its limitations; it does not claim that exact candidate elimination is a robust solution for noisy production data.

Common misconceptions and mistakes

G is the set of all consistent hypotheses. It contains only the maximally general boundary members.
The most general hypothesis must be the best predictor. Generality and predictive performance are different properties.
A positive example always specializes G. It removes inconsistent G members; specialization is associated with rejecting negative examples in the standard update.
An empty G-set proves the examples are meaningless. The chosen language or exact-consistency assumption may be the problem.

Business use

The concept helps explain why limited examples can support several distinct rules. It is useful for transparent learning demonstrations, knowledge elicitation and understanding the role of a hypothesis language.

For practical projects, examine noise tolerance, representation size and whether the true concept is expressible. Boundary sets can grow large, and exact consistency is fragile when labels conflict. Treat the G-set as a precise representation within stated assumptions, rather than a ready-made confidence measure or a guarantee of future correctness.

Check your understanding

After red circle is positive and blue square is negative in the worked example, is red/circle a member of G?

Answer: No. It is consistent but not maximally general: both red/* and */circle are more general consistent hypotheses. It remains represented inside the version space.

Related terms

Version space
S-set
Hypothesis space
Inductive bias
candidate elimination
concept learning
generality ordering
consistent hypothesis

Learn next

Before adding the third example, predict what each G member says about blue circle and red square. Identify which labels would distinguish the alternatives, then explain how a contradictory duplicate label affects an exact-consistency learner.

Sources

Russell's author-hosted treatment explains G and S boundaries and their limitations: https://aima.eecs.berkeley.edu/~russell/papers/hpc-machine-learning.pdf

Mitchell's institutional course material gives the boundary representation and candidate-elimination updates: https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/46838-s98/classnotes/ch2_4page.pdf

The author's original dissertation is available at https://www.cs.cmu.edu/afs/cs/usr/mitchell/ftp/pubs/VERSION_SPACES_MitchellPhDthesis.pdf

The color-shape sequence and Maple Rules case are original illustrations. The dissertation is supplied for further reading; its full proof development was not independently audited.

Previous: G-prior Next: Gabbay's separation theorem