Sets and Lattices
   

     In this section on induction, the idea of a set is often used to speak of the space of inductive hypotheses. The table above describes some of the algebraic properties of the operations of union and intersection that are defined over sets. (In the figure above union is represented by the U-shaped symbol and intersection by a upside down U-shaped symbol.)

     Recall that a set is simply a collection of things. For example, the letters a, b, s could be grouped together as a set which would be expressed as {a,b,s} where the curly braces are used to enclose the items that constitute a set. In addition to the set {a,b,s} we define the sets {b,a} and {c,t,q}. The union operation can then be illustrated as:

{a,b,s} U {b,a} = {a,b,s}

{a,b,s} U {c,t,q} = {a,b,s,c,t,q}

and the intersection operation as:

{a,b,s} I {b,a} = {a,b}

{a,b,s} I {c,t,q} = {}

where {} is the empty set. The empty set is referred to as ø in the above figure.

     Finally, we can define a relation between two sets in order to make this all a bit more interesting. The relation is referred to as 'subset of' and is often represented as a 'U' on its side with a line underneath and the open portion of the 'U' to the right. In the example above the set {b,a} is a subset of the set {a,b,s} since every element of the set {b,a} is in the set {a,b,s}. It is also true that the set {b,a} is a subset of the set {b,a}; that is, it is a subset of itself.

     Sometimes the inverse of 'subset of' is also sometimes used and is read as 'contains'. Again this relation is represented as a 'U' on its side with a line underneath ( ) but in this case the open portion of the 'U' is to the left. In the example above the set {a,b,s} contains the set {b,a} since every element of the set {b,a} is in the set {a,b,s}.

The subset (or the contains) relation can be used to partially order a set of sets. If some set A is a subset of a set B then these sets are partially ordered with respect to each other. If a set A is not a subset of another set B and B is not a subset of A then these two sets are not ordered with respect to each other. Thus, this relation can be used to partially order a set of sets. Partial orders are so popular with computer scientists and mathematicians that they have given them a nickname - POsets.

   

     Sets become more interesting when they can be shown to possess some additional structural or algebraic properties. The figure above defines a particular kind of structure that is referred to as a lattice. The next two figures below provide additional definitions and properties related to lattices using the 'contains' relation. Before you become too enthralled with the technical details provided here, step back and consider the implications of this structure for concept learning. Recall that one of the problems in inductive tasks is to determine how to revise a hypothesis in response to new evidence. Usually there are many different ways to revise the hypotheses, and there is no obvious way in which to choose one revision over another. And, all of the revisions usually cannot be followed because there are often too many of them.

     With this in mind, simply recall that a lattice is a partially ordered set where for any pair of sets (hypotheses) there is a least upper bound and greatest lower bound. Now let our current hypothesis be H and the current training example E. If E is a subset of H, then no change of H is required. If E is not a subset of H, then H must be changed. The minimal generalization of H is the least upper bound of E and H, and the minimal specialization of H is the greatest lower bound of E and H. Thus, the lattice serves as a kind of map that allows us to locate out current hypothesis,H, with reference to the new information, E. The example lattice referred to below will help to illustrate this general idea.

 

 
 
 
An example of the lattice that is formed from the power set of the set {a,b,c} is provided and an examination of its structure should clarify these ideas.
 
 
     The figure above shows the correspondence that exists between the algebra of propositional logic and the algebra of sets. Recall that we have referred to a hypotheses as either a logical expression or rule that defines a concept or as a subset of the possible instances constructible from some set of dimensions. It is because of this correspondence that we can use either language to refer to a concept definition. Note that disjunction corresponds to union, negation to set complement (everything that is not in a set), and conjunction to intersection. And. recall that union and intersection were the important operators used to define a lattice. Now, it should come as no surprise that the expressions in propositional logic can also be organized into a corresponding lattice. It is this correspondence that is used in the version space concept learning approach that we examined.
Induction,Concepts, Uncertainty