/
VersionSpaceLearning.java
75 lines (68 loc) · 2.42 KB
/
VersionSpaceLearning.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package aima.core.learning.knowledge;
import java.util.List;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): Figure 19.2, page
* 771.<br>
* <br>
*
* <pre>
*
* function Version-Space-Learning(examples) returns a version space
* local variables: V, the version space: the set of all hypotheses
*
* V ← the set of all hypotheses
* for each example e in examples do
* if V is not empty then V ← Version-Space-Update(V, e)
* return V
*
* </pre>
* <pre>
* function Version-Space-Update(V, e) returns an updated version space
* V ← {h ∈ V : h is consistent with e}
* </pre>
* <p>
* Figure 19.3 The version space learning algorithm. It
* finds a subset of V that is consistent with all the examples.
* @author samagra
*/
public class VersionSpaceLearning {
/**
* function Version-Space-Learning(examples) returns a version space
* @param examples
* @return
*/
public VersionSpace versionSpaceLearning(List<LogicalExample> examples) {
// local variables: V, the version space: the set of all hypotheses
// V ← the set of all hypotheses
VersionSpace v = new VersionSpace();
// if V is not empty then V ← Version-Space-Update(V, e)
for (LogicalExample e :
examples) {
if (v != null) {
v = versionSpaceUpdate(v, e);
}
}
// return V
return v;
}
/**
* function Version-Space-Update(V, e) returns an updated version space
* @param v
* @param e
* @return
*/
private VersionSpace versionSpaceUpdate(VersionSpace v, LogicalExample e) {
// V ← {h ∈ V : h is consistent with e}
// False negative for S i : This means S i is too specific, so we replace it by all its immediate
//generalizations, provided they are more specific than some member of G.
if (e.getGoal() && !v.predictFromSpecialisedSet(e)) {
v.setMostSpecificSet(v.immediateGeneralisation(v.getMostSpecificSet(), e));
}
//False positive for G i : This means G i is too general, so we replace it by all its immediate
//specializations, provided they are more general than some member of S.
if (!e.getGoal() && v.predictFromGeneralisedSet(e)) {
v.setMostGeneralSet(v.immediateSpecialisation(v.getMostGeneralSet(), e));
}
return v;
}
}