Version space learning

A version space in concept learning is the subset of all hypotheses that are consistent with the observed training examples (Mitchell 1997). This set contains the hypotheses that have not yet been eliminated as a result of being in conflict with observed data.

In settings where which there is a generality ordering on hypotheses, it is possible to represent the version space by just two hypothes: (1) the most specific consistent hypothese, and (2) the most general consistent hypothesis, where "consisrent" indicates agreement with observed data. The most specific hypothesis is the hypothesis that covers the observed positive training examples, and as little else as possible. This minimal hypothesis essentially claims that the true concept is defined just by the postive data already obseved. The most general hypothesis is that which covers the observed postive training examples, but that also covers as much of the remaining feature space without including any negative training examples. Thus, during the learning process, the version space (which itself is a set – possibly infinite – conatining all consistent hypotheses) is represented by just its lower and upper bounds.

The notion of Version Spaces was introduced by Mitchell as a framework for understanding the basic problem of supervised learning as a problmem of solution search. Alsthough the basic solution search method that accompanies the Version Space framework is not a popular learning algorithm, there some practical implementations have been developed.

See Also

• Rough set

References

• Mitchell, Tom M. (1997). Machine Learning. Boston: McGraw-Hill.