# Candidate Elimination Algorithm

``````G0 = {<?, ?, ?>}
S0 = {<0, 0, 0>}
``````

When you are presented with a negative example, you need to remove from S any hypothesis inconsistent with the current observation and replace any inconsistent hypothesis in G with its minimal specializations that are consistent with the observation but still more general than some member of S.

So for your first (negative) example, `(big, red, circle)`, the minimal specializations would make the new hypothesis space

``````G1 = {<small, ? , ?>, <?, blue, ?>, <?, ?, triangle>}
S1 = S0 = {<0, 0, 0>}
``````

Note that S did not change. For your next example, `(small, red, triangle)`, which is also negative, you will need to further specialize G. Note that the second hypothesis in G1 does not match the new observation so only the first and third hypotheses in G1 need to be specialized. That would yield

``````G2 = {<small, blue, ?>, <small, ?, circle>, <?, blue, ?>, <big, ?, triangle>, <?, blue, triangle>}
``````

However, since the first and last hypotheses in G2 above are specializations of the middle hypothesis (`<?, blue, ?>`), we drop those two, giving

``````G2 = {<small, ?, circle>, <?, blue, ?>, <big, ?, triangle>}
S2 = S1 = S0 = {<0, 0, 0>}
``````

For the positive `(small, red, circle)` observation, you must generalize S and remove anything in G that is inconsistent, which gives

``````G3 = {<small, ?, circle>}
S3 = {<small, red, circle>}
``````

`(big, blue, circle)` is the next negative example. But since it in not consistent with G, there is nothing to do so

``````G4 = G3 = {<small, ?, circle>}
S4 = S3 = {<small, red, circle>}
``````

Lastly, you have the positive example of `(small, blue, circle)`, which requires you to generalize S to make it consistent with the example, giving

``````G5 = {<small, ?, circle>}
S5 = {<small, ?, circle>}
``````

Since G and S are equal, you have learned the concept of “small circles”.