Learning by Managing Multiple Models (Version Space)

• An elegant way to use positive and negative examples.

  To create a version space ¥ A space of concepts.

• Version Space Representation

  • There is a specialization tree and a generalization tree.

  • Each node is connected to a model.

  • One node in the generalization tree is connected to a model that matches everything.

  • One node in the specialization tree is connected to a model that matches only one thing.

    
    

  • Links between nodes denote generalization and specialization relations between their models.

• The version-space procedure can learn quickly as long as:

  • there is a stream of noise-free positive and negative examples

  • there is a fixed number of attributes, and

  • a class-characterizing model can be expressed as a combination of values for these attributes.
    
    
    

• Initialization:

  • the most general possible model ¥ that matches everything

  • the very specific model ¥ that match only the 1^st +ve example

• Perform generalization and specialization:

  • perform specialization on the general models so that it does not match a negative example.

  • Perform generalization on the special model so that they matches more positive examples.

• When a specific model matches a negative example, eliminate it.

  When a general model does not match a positive example, eliminate it.

  • Proceed until the two models converges.

• Need to define the generalization and specialization operator:

  • Example:
    Generalization Specific Object « ?
    Specialization ? « Specific Object

  

  or find the least upper bound (lub) and greatest lower bound (glb) in a lattice.
  
  There should be no cycles in the generalization and specialization process.

Example:

Consider the following cases:

To summarize, to respond to positive and negative examples using a version space,

• If the example is positive,

  • Generalize all specific models to match the positive example, but ensure the following,

    • The new specific models involve minimal changes

    • Each new specific model is a specialization of some general model

    • No new specific model is a generalization of some other model.

  • Prune away all general models that fail to match the positive example.

• If the example is negative,

  • Specialize all general models to prevent match with the negative example, but ensure the following,

    • The new general models involve minimal changes.

    • Each new general model is a generalization of some specific model.

    • No new general model is a specialization of some other general model.

  • Prune away all specific models that match the negative examples.