Catalogue of Artificial Intelligence Techniques
Aliases: Version Space
Keywords: concept learning, lattices, learning
Author(s): Dave Plummer , Maarten van Someren
A technique utilised by concept learning programs to record knowledge about the concept that is being learnt and to facilitate the updating of this knowledge as more information becomes available to the program. For this method the description space must consist of a number of attributes that a given example might have. These are conceptually represented either as sets of descriptions or as lattices, each branch of which represents a possible value for the attribute. Using the later representation, the technique records information by placing marks in these lattices to indicate which possible attribute values are not included in the concept being learnt. Upper marks indicate that all parts of the tree above the mark are definitely outside the concept (i.e., this is the maximally general description) and a lower mark indicates that all parts of the tree below the mark are definitely inside the concept (i.e., this is the maximally specific description). Between these marks there could be a grey region which is the area that the program is uncertain about. As the program gains more information the marks are moved to update the knowledge: positive instances of a concept are used to make the maximally specific description more general by moving the lower marker up, whilst negative instances are used to make the maximally general description more specific by moving the upper mark down. Once the upper and lower marks on all of the description trees coincide, the concept is completely specified and the program can report completion. The program can also detect failure if the marks become crossed (i.e., a lower mark above an upper one). This technique can handle most conjunctive concepts well but encounters difficulty handling disjunction, these difficulties may be surmountable by using multiple copies of the description space.
- Bundy, A. and Silver, B., A critical survey of rule learning programs Proceedings of ECAI-82 (1982), 151--157.