Version space

A version area that subset of the hypothesis space is referred to machine learning, that contains all the hypotheses with respect to a consistent and complete set of training examples. A hypothesis is called consistent if it classifies no negative training examples positive. A hypothesis is called complete if all the positive examples are correctly classified from a hypothesis.

In the version space learning method ( Mitchell, 1982) is an incremental machine learning method for learning a concept. For the case that the training examples are not noisy, and the desired destination is included in the concept of hypothesis space, the release space learning procedure provides a compact representation of the release period.

  • 3.1 Positive Example 3.1.1 Statement
  • 3.2.1 Statement
  • 3.3.1 Statement
  • 3.4.1 Statement
  • 3.5.1 Statement

Generals in the hypothesis space

Basis of the algorithm is a partial order, which allows to distinguish between hypotheses by generals. One hypothesis is as special as designated, if the following applies to all x from the set of possible target concepts:

Version space learning method

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

Algorithm

Initially, the version space contains all possible hypotheses, that is consistent with the hypothesis space consistent. It is increasingly restricted until it consists of only one element in the ideal case by the sequential addition of positive and negative training examples. The representation of the version space by two quantities, called S and G ( "special" and "general "). S is the amount of the most specific hypotheses and contains all hypotheses are consistent with the training examples, that classify it correctly. Furthermore, none of the hypotheses in S may be more general than another hypothesis in the version space. G contains the analogous general hypotheses are consistent with the training data.

Initially, S contains the most specific hypothesis, so that hypothesis, the negative classifies each target concept, and G is the most common hypothesis, so that hypothesis, which classifies each target concept positively. Then iterates over the set of training examples, and S, and G are each adjusted so that the above demands for S and G are satisfied.

Advantages and Disadvantages

The first advantage of the version space learning method is the implicit representation of the version space. Old examples need not be stored and therefore, there is little memory overhead for representing the version space. Another advantage is the possibility to detect a sufficiently large set of training patterns independently ( Stops when W = G). An increase in the speed of learning is obtained if hypotheses are generated and are added to S or G, for example, created by experts. In this case, the algorithm can select examples that separate the version space as possible in equal parts. The learning of such an example provides a fast reduction of the version space size.

Example

Before the examples are classified in the version space, an Start allocation of quantities and.

Start allocation

Positive example

  • (Football, team, outdoor, national, Saturday)
  • Football, team, outdoor, national, Saturday
  • ?? ?? ?

Explanation

Does not contain the sample. generalized around. continues to let all of the examples.

Positive example

  • ( Hockey, Team, outdoors, national, Saturday)
  • ?, Team, outdoor, national, Saturday
  • ?? ?? ?

Explanation

Does not contain the new instance. Therefore, it is generalized in that it comprises. Because different and only in the sport, replacing football by the wildcard symbol?

Negative example

  • ( Gymnastics, individual, indoors, World, Saturday)
  • ?, Team, outdoor, national, Saturday
  • (? , Team,? ,? ,? ) (? ?, Outdoors,? ,? ) (? ?? , National,? )

Explanation

Containing the negative examples do not, therefore, remains unchanged. must be specialized by listing all the cases that prevent is recognized as a valid example. At the same time must be so general that it allows the previous examples.

Positive example

  • ( Handball, team, indoors, national, Saturday)
  • ?, Team,? , National, Saturday
  • (? , Team,? ,? ,? ) (? ?? , National,? )

Explanation

Does not contain the current example, and therefore has to be extended. would reject the current example, must therefore be specialized.

Negative example

  • ( Decathlon, single, out, world, Sunday)
  • ?, Team,? , National, Saturday
  • (? , Team,? ,? ,? ) (? ?? , National,? )

Explanation

Because the sample rejects is. The example does not allow, that is.

Concept (disambiguation)
801877
de