Version Space Learning Problem

[antmarakis]

I have a question regarding the Version Space Learning pseudocode. In particular, I am not sure I understand how the version updating subfunction works.

I have implemented the algorithm and run some tests, and it almost never returns a solution. There might be something wrong with my implementation, but after a quick amendment to the algorithm it works fine. I will give an example to help understand my doubts.

Say we have a version space V with two hypotheses:

H1 = A(True), B(True)
H2 = A(True), B(False)

Our examples:

E1 = A(True), B(True), Target(True)
E2 = A(True), B(False), Target(True)

First we update V on E1:

• E1 is consistent with H1 (predicted value == Target == True).
• E1 is not consistent with H2. H2 predicts a value of False for E1, while it is True. We have a False Negative. Since H2 is not consistent with E1, as per the pseudocode, we remove it. So V now only contains H1.

We move on to E2:

• E2 is not consistent with H1, so we remove H1 from V. Now V is empty.

We are left with an empty V, so we cannot continue. But the initial V is in fact a perfectly good solution. Both E1 and E2 would have been consistent with at least one hypothesis in the initial V which is the desired outcome, but as is the algorithm fails to find a solution.

---

I may have misunderstood the algorithm, but nevertheless after some thinking I found a solution to this and implemented it with great results.

When an example is True, we don't remove hypotheses from V. We just check if there is at least one hypothesis that is consistent with the example and move on. Since the hypotheses are strung together by disjunctions, it doesn't make a difference to True examples if we remove hypotheses that are not consistent. True examples need just one consistent hypothesis. For False examples, work as the pseudocode suggests, since they need to be assigned False values from all hypotheses.

That way we will certainly be left with a set of hypotheses that are consistent with all the examples (if such a set exists).

---

Please let me know if I have not understood the algorithm correctly, or if my thinking is correct.

[norvig]

It is correct that both H1 and H2 should be eliminated. The problem is that the original set should have contained more hypotheses, including "H3 = A(True)". That is the hypothesis that is consistent with both examples.

[antmarakis]

OK, got it. Thanks.