Candidate elimination algorithm Welcome to the lecture series on machine learning. This session we are going to concentrate on version spaces and the candidate elimination algorithm of concept learning. Candidate elimination algorithm normally finds all hypotheses that are consistent with the training examples using a more general-than-partial-ordering strategy. In the earlier algorithm, Finders, there was a flaw, which we listed at the end of the illustration: some negative examples will never be considered by the Finder, so nothing is learned from them. However, candidate elimination considers that also. Another difference is that Finders will finally generate only one consistent hypothesis, but there could be many that are always ignored by the Finders algorithm. On the other hand, candidate elimination looks at all possible consistent hypotheses, including negative examples. It usually evaluates through the definition. The description given here for the candidate elimination algorithm can be written in a standard way, which says that a hypothesis H is set to be consistent with a given training set of examples D if and only if, when it is applied to each and every example of the training set, it must return the target concept C of X. Right, so that is internally written as: consistent(H, D) will be equivalent to for all examples and their target concepts present in the training sample D, where H of X must be C of X. This is the definition for the candidate elimination algorithm. The key difference between the definition of consistent and satisfies condition: an example X is set to be satisfied by the hypothesis H whenever it results in one. But whereas the hypothesis H is said to be consistent, it depends on the target concept if it satisfies the target concept C of X. Now look at the version space definition. The version space is defined to be a subset of all consistent hypotheses with respect to the hypothesis space H and the training example D. By definition, in a standard way, the version space, which is denoted as VSH, suffixed H, D, this H represents the hypothesis space, D represents the training examples, with respect to hypothesis space H and training example D is the subset of hypotheses from H consistent with the training example D. So, the version space is the set of all hypotheses, whichever is consistent with the training example. So, it can be written as VSH, D is equivalent to small h ∈ capital H, which is consistent in the form, the H, P. So, that is an algorithm, a very simple algorithm called the list-then-eliminate algorithm, which actually helps us to find out the version space. The list-then-eliminate algorithm is the simplest algorithm used to understand how the version space is constructed. Here, all the inconsistent hypotheses in the hypothesis space are going to be eliminated, and only the consistent hypotheses are kept. That is what the major logic behind the list-then-eliminate algorithm is. So, that is what is explained in this algorithm. In the version space, there is a list of hypotheses for each training example. You have to check every hypothesis and whether they are consistent with it or not. If they are consistent, they may result in a target concept. So, by the way, the consistent hypothesis will be H of X equal to C of X. Suppose if it is not equal to C of X, then that hypothesis is an inconsistent one, so we have to eliminate that hypothesis. That is what the list-then-eliminate algorithm does. Right now, candidate elimination algorithm is simply works as per the principle that was explained in the earlier list-then-eliminate algorithm, and this is the algorithm that represents the version space by storing only its most general members that are labeled as G and its most specific members labeled as S. And given only these two sets, S and G, the candidate elimination algorithm makes it possible to eliminate all the members of the version space as needed by generating the hypothesis which lies between these two sets. That means, in the general-to-specific partial ordering over hypothesis, general to specific partial ordering over hypothesis. So, let’s see how this is the algorithm, candidate elimination algorithm. So, just to have a look at once, you understand the example. The algorithm is so simple for you to write by yourself, okay? So, let’s begin the candidate elimination algorithm by simply initializing the two boundaries, that is called G boundary and S boundary. Now, that is to be initialized: G boundary and S boundary. And G boundary initially, because this is the most general boundary, so initially G not will be all question marks for all the attributes. This is actually for our ENOYSport example. Let there be six different attributes in there. For all attributes, any value it’s ready to accept. So, initially, G is all question marks. But S boundary, I said it is more specific boundary. G stands for General, and S stands for Specific. You please remember in such a way, S boundary set is consisting of most specific cases, no hypotheses. So, S boundary is started with most specific values, so that all attributes will be null, right? So, every other hypothesis in H is both more general than S0 and more specific than G0. With that assumption, we are moving, right? We set a boundary where G is most general, S is most specific. So, whatever the rest, whatever hypotheses we find, will be between these two, so that the hypothesis H will be more general than S, S0, more specific than G0.