View source for Version space learning

[[Image:Version space.png|thumb|right|300px|Version space for a "rectangle" hypothesis language in two dimensions.  Green pluses are positive examples, and red circles are negative examples.  GB is the maximally '''general''' positive hypothesis boundary, and SB is the maximally '''specific''' positive hypothesis boundary.  The intermediate (thin) rectangles represent the hypotheses in the version space.]]
'''Version space learning''' is a [[Symbolic artificial intelligence|logical]] approach to [[machine learning]], specifically [[binary classification]]. Version space learning algorithms search a predefined space of [[hypothesis|hypotheses]], viewed as a set of [[Sentence (logic)|logical sentences]]. Formally, the hypothesis space is a [[Logical disjunction|disjunction]]<ref name="aima">{{Cite AIMA|2|pages=683–686}}</ref>

:<math>H_1 \lor H_2 \lor ... \lor H_n</math>

(i.e., one or more of hypotheses 1 through {{mvar|n}} are true). A version space learning algorithm is presented with examples, which it will use to restrict its hypothesis space; for each example {{mvar|x}}, the hypotheses that are [[Consistency|inconsistent]] with {{mvar|x}} are removed from the space.<ref name="Mitchel-1982"/> This iterative refining of the hypothesis space is called the '''candidate elimination''' algorithm, the hypothesis space maintained inside the algorithm, its ''version space''.{{r|aima}}

==The version space algorithm==
In settings where there is a generality-ordering on hypotheses, it is possible to represent the version space by two sets of hypotheses: (1) the '''most specific''' consistent hypotheses, and (2) the '''most general''' consistent hypotheses, where "consistent" indicates agreement with observed data.

The most specific hypotheses (i.e., the specific boundary '''SB''') cover the observed positive training examples, and as little of the remaining [[feature (machine learning)|feature space]] as possible.  These hypotheses, if reduced any further, ''exclude'' a ''positive'' training example, and hence become inconsistent.  These minimal hypotheses essentially constitute a (pessimistic) claim that the true concept is defined just by the ''positive'' data already observed: Thus, if a novel (never-before-seen) data point is observed, it should be assumed to be negative.  (I.e., if data has not previously been ruled in, then it's ruled out.)

The most general hypotheses (i.e., the general boundary '''GB''') cover the observed positive training examples, but also cover as much of the remaining feature space without including any negative training examples.  These, if enlarged any further, ''include'' a ''negative'' training example, and hence become inconsistent.  These maximal hypotheses essentially constitute a (optimistic) claim  that the true concept is defined just by the ''negative'' data already observed: Thus, if a novel (never-before-seen) data point is observed, it should be assumed to be positive. (I.e., if data has not previously been ruled out, then it's ruled in.)

Thus, during learning, the version space (which itself is a set – possibly infinite – containing ''all'' consistent hypotheses) can be represented by just its lower and upper bounds (maximally general and maximally specific hypothesis sets), and learning operations can be performed just on these representative sets.

After learning, classification can be performed on unseen examples by testing the hypothesis learned by the algorithm. If the example is consistent with multiple hypotheses, a majority vote rule can be applied.{{r|aima}}

==Historical background==
The notion of version spaces was introduced by Mitchell in the early 1980s{{r|Mitchel-1982}} as a framework for understanding the basic problem of supervised learning within the context of [[state space search|solution search]].  Although the basic "'''candidate elimination'''" search method that accompanies the version space framework is not a popular learning algorithm, there are some practical implementations that have been developed (e.g., Sverdlik & Reynolds 1992, Hong & Tsang 1997, Dubois & Quafafou 2002).

A major drawback of version space learning is its inability to deal with noise: any pair of inconsistent examples can cause the version space to ''collapse'', i.e., become empty, so that classification becomes impossible.{{r|aima}} One solution of this problem is proposed by Dubois and Quafafou that proposed the Rough Version Space,<ref name="Dubois Quafafou 2002"/> where rough sets based approximations are used to learn certain and possible hypothesis in the presence of inconsistent data.

==See also==
*[[Formal concept analysis]]
*[[Inductive logic programming]]
*[[Rough set]]. [The rough set framework focuses on the case where ambiguity is introduced by an impoverished '''feature set'''. That is, the target concept cannot be decisively described because the available feature set fails to disambiguate objects belonging to different categories.  The version space framework focuses on the (classical induction) case where the ambiguity is introduced by an impoverished '''data set'''.  That is, the target concept cannot be decisively described because the available data fails to uniquely pick out a hypothesis.  Naturally, both types of ambiguity can occur in the same learning problem.]
*[[Inductive reasoning]]. [On the general problem of induction.]

==References==
<references>
<ref name="Mitchel-1982">
{{cite journal
  | last = Mitchell
  | first = Tom M.
  | title = Generalization as search
  | journal = Artificial Intelligence
  | volume = 18
  | issue = 2
  | pages = 203–226
  | year = 1982
  | doi = 10.1016/0004-3702(82)90040-6}}
</ref>
<ref name="Dubois Quafafou 2002">
{{cite conference
  | first = Vincent 
  | last = Dubois
  |author2=Quafafou, Mohamed
  | title = Concept learning with approximation: Rough version spaces
  | book-title = Rough Sets and Current Trends in Computing: Proceedings of the Third International Conference, RSCTC 2002.    
  | pages = 239–246 
  | year = 2002
  | location = Malvern, Pennsylvania| doi = 10.1007/3-540-45813-1_31
 }}
</ref>
</references>

*{{cite journal
  | last = Hong      
  | first = Tzung-Pai 
  |author2=Shian-Shyong Tsang 
   | title = A generalized version space learning algorithm for noisy and uncertain data
  | journal = IEEE Transactions on Knowledge and Data Engineering   
  | volume = 9
  | issue = 2
  | pages = 336–340 
  | year = 1997 
  | doi = 10.1109/69.591457| s2cid = 29926783 
 }}
*{{cite book
  | last = Mitchell
  | first = Tom M.
  | title = Machine Learning
  | publisher = McGraw-Hill
  | year = 1997
  | location = Boston}}
*{{cite conference
  | first = W.
  | last = Sverdlik     
  |author2=Reynolds, R.G.
   | title = Dynamic version spaces in machine learning
  | book-title = Proceedings, Fourth International Conference on Tools with Artificial Intelligence (TAI '92)   
  | pages = 308–315 
  | year = 1992
  | location = Arlington, VA}}

[[Category:Machine learning]]