Quasi-Ordering of Hypothesis Languages

In the concept learning/ILP setting we are looking for a concept, more general than any positive example, and more specific than any concept, covering positive as well as negative examples. So it is a good idea, to structure the hypotheses by their generality, and to generate more general or more specific hypotheses stepwise. The search in a structured search space of all hypotheses can be pruned, which is not possible in an unstructured search space.

In his book "Machine Learning" Tom Mitchell proposed a quasi-ordering for attribute-value hypothesis languages (partial ordering of the set of all hypotheses) based on the more-special-than (or more-general-than) relation:

A concept c₁ is more special than a concept c₂, if and only if every example covered by c₁ is covered by c₂ as well. A concept c₁ is strictly more special than c₂, if it is more special but distinct from c₂, which means that there is at least one instance covered by c₂, that is not covered by c₁ as well.

A concept c₁ is more general than c₂, if c₂ is more special than c₁. Concept c₁ is strictly more general than c₂, if c₂ is strictly more specific than c₁.

If concepts are characterized by attribute values, which can be arranged in a hierarchy according to a more-special-than relation, the search space (which can be seen as a cartesian product of the attribute value sets) can always be (partially) ordered.