Version space

In machine learning, the version space is that subset of the hypothesis space that contains all consistent and complete hypotheses with respect to a set of learning examples. A hypothesis is called consistent if it does not classify any negative training examples as positive. A hypothesis is called complete if all positive examples of a hypothesis are correctly classified. ${\displaystyle D}$

The version space learning method (Mitchell 1982) is an incremental machine learning method for learning a concept . In the event that the training examples are not noisy and the desired target concept is contained in the hypothesis space, the version space learning method provides a compact representation of the version space.

Generality in the hypothesis space

The algorithm is based on a partial order that allows hypotheses to be differentiated according to generality. A hypothesis is called more special than if the following applies to all x from the set of possible target concepts: ${\displaystyle h_{k}}$ ${\displaystyle h_{\ell }}$

${\displaystyle h_{k}(x)=1\;\;\Rightarrow \;\;h_{\ell }(x)=1}$

Version space learning procedure

The version space learning method is a machine method in the field of AI to teach the computer to correctly assess previously unknown information.

algorithm

Initially, the version space contains all possible hypotheses, i.e. it matches the hypothesis space. By sequentially adding positive and negative training examples, it is restricted further and further until, ideally, it only consists of one element. The version space is represented by two sets named S and G ("specific" and "general"). S is the set of the most special hypotheses and contains all hypotheses that are consistent with the training examples, i.e. classify them correctly. Furthermore, none of the hypotheses in S must be more general than another hypothesis in the version space. Similarly, G contains the most general hypotheses that are consistent with the training data.

Initially, S contains the most specific hypothesis, i.e. the hypothesis that classifies each target concept negatively, and G the most general hypothesis, i.e. the hypothesis that classifies each target concept positively. Then the set of all training examples is iterated over and S and G are adjusted so that the above requirements for S and G are met.

advantages and disadvantages

The first advantage of the version space learning method is the implicit representation of the version space. Old examples do not have to be saved, which means that there is less memory overhead to display the version space. Another advantage is the ability to independently recognize a sufficiently large number of training examples (stop if S = G). The speed of learning is increased if hypotheses can be generated and added to S or G, for example created by experts. In this case, the algorithm can select examples that separate the version space into parts of the same size as possible. Learning such an example ensures a quick reduction in the version space size.

example

The example demonstrates how a specific version space is created using examples.

Before the examples are classified in the version space, the quantities and are initially assigned . ${\displaystyle S_{0}}$ ${\displaystyle G_{0}}$

Start allocation

• ${\displaystyle S_{0}=\{\}}$
• ${\displaystyle G_{0}=\{(?,?,?,?,?)\}}$

Positive example

• ${\displaystyle h_{1}=}$(Football, team, outside, national, Saturday)
• ${\displaystyle S_{1}=\{(}$Football, team, outside, national, Saturday ${\displaystyle )\}}$
• ${\displaystyle G_{1}=\{(}$?,?,?,?,? ${\displaystyle )\}}$

Explanation

${\displaystyle S_{0}}$does not contain the example . generalized around . still allows all examples. ${\displaystyle h_{1}}$ ${\displaystyle S_{0}}$ ${\displaystyle h_{1}}$ ${\displaystyle G_{1}}$

Positive example

• ${\displaystyle h_{2}=}$(Hockey, team, outside, national, Saturday)
• ${\displaystyle S_{2}=\{(}$?, Team, outside, national, Saturday ${\displaystyle )\}}$
• ${\displaystyle G_{2}=\{(}$?,?,?,?,? ${\displaystyle )\}}$

Explanation

${\displaystyle S_{1}}$does not include the new example . Therefore it is generalized to include. As and differ only in the sport, replacing football through the wildcard symbol ? ${\displaystyle h_{2}}$ ${\displaystyle S_{2}}$ ${\displaystyle h_{2}}$ ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$

Negative example

• ${\displaystyle h_{3}=}$(Floor exercise, single, indoor, world, Saturday)
• ${\displaystyle S_{3}=\{(}$?, Team, outside, national, Saturday ${\displaystyle )\}}$
• ${\displaystyle G_{3}=\{}$(?, Team,?,?,?), (?,?, Outside,?,?), (?,?,?, National,?) ${\displaystyle \}}$

Explanation

${\displaystyle S_{2}}$does not contain the negative example, therefore remains unchanged. must be specialized by listing all cases that prevent it from being recognized as a valid example. At the same time, it must be general enough that the previous examples allow it. ${\displaystyle S_{2}}$ ${\displaystyle G_{2}}$ ${\displaystyle h_{3}}$ ${\displaystyle G_{3}}$

Positive example

• ${\displaystyle h_{4}=}$ (Handball, team, indoor, national, Saturday)
• ${\displaystyle S_{4}=\{(}$?, Team,?, National, Saturday ${\displaystyle )\}}$
• ${\displaystyle G_{4}=\{}$(?, Team,?,?,?), (?,?,?, National,?) ${\displaystyle \}}$

Explanation

${\displaystyle S_{3}}$does not contain the current example and must therefore be expanded. would reject the current example, so you have to specialize. ${\displaystyle G_{3}}$ ${\displaystyle G_{3}}$

Negative example

• ${\displaystyle h_{5}=}$(Decathlon, singles, outside, world, Sunday)
• ${\displaystyle S_{5}=\{(}$?, Team,?, National, Saturday ${\displaystyle )\}}$
• ${\displaystyle G_{5}=\{}$(?, Team,?,?,?), (?,?,?, National,?) ${\displaystyle \}}$

Explanation

As the example rejects is . Also the example does not allow, that is . ${\displaystyle S_{4}}$ ${\displaystyle S_{5}=S_{4}}$ ${\displaystyle G_{4}}$ ${\displaystyle G_{4}=G_{5}}$

literature

• Tom M. Mitchell: Machine Learning , McGraw Hill . 1997. ISBN 0071154671
• Christoph Beierle, Gabriele Kern-Isberner: Methods of knowledge-based systems: fundamentals, algorithms, applications. , 4th edition. Vieweg + Teubner Verlag , 2008, p. 128ff. ISBN 3834805041

Individual evidence

1. ↑ Example of a concept learning task. (No longer available online.) Archived from the original on March 4, 2016 ; accessed on June 16, 2016 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.