Lesson5.8. List-then-eliminate Algorithm

-

 Introduction
The List-Then-Eliminate algorithm is a concept learning strategy used in machine learning and artificial intelligence to systematically search through a hypothesis space to find hypotheses that are consistent with a set of training examples. The algorithm operates under the principle of representational completeness, meaning it considers every possible hypothesis that can be constructed from the attributes in the training data.
 At its core, the List-Then-Eliminate algorithm begins with the assumption that any hypothesis could be the true one, and it incrementally refines this set by eliminating any hypothesis that fails to correctly classify the training examples. It uses a version space approach, where the version space is defined as the subset of the hypothesis space that is consistent with all the observed training examples.

 The algorithm can be summarized as follows:

 1. Initialize Version Space: 

Begin with a Version Space that contains every possible hypothesis in the hypothesis space ( H ). The hypothesis space ( H ) is the set of all hypotheses that can be formed from the given attributes and their values.

2. Process Each Training Example: 

For each training example ( (x, c(x)) ), where ( x ) is the instance and (c(x)) is the classification (or concept) of that instance, do the following:
   - Eliminate Inconsistent Hypotheses: 
Remove from the Version Space any hypothesis (h) for which (h(x) != c(x) ). In other words, if a hypothesis does not correctly predict the classification of the training example, it is eliminated. This step gradually narrows down the Version Space to include only those hypotheses that are consistent with all the observed training examples.

3. Output Remaining Hypotheses: 

After processing all the training examples, output the list of hypotheses remaining in the Version Space. These are the hypotheses that are consistent with all the training examples provided.

Advantages and Disadvantages

The strength of the List-Then-Eliminate algorithm lies in its exhaustive and systematic approach, ensuring that no potential hypothesis is overlooked. However, this strength is also its weakness; the algorithm is computationally intensive and often impractical for all but the smallest datasets with a very limited number of attributes. Despite this, it serves as a valuable educational tool, offering clear insights into how machines can learn from data and the challenges involved in developing efficient learning algorithms. It also lays the groundwork for more sophisticated learning algorithms that seek to balance the trade-off between representational completeness and computational practicality.

Example

For the List-Then-Eliminate algorithm, we start with a hypothesis space that contains all possible combinations of attribute values. We then eliminate hypotheses based on the training instances.
 Consider the following hypothetical dataset with 2 features. It is impractical to explain with more features. 

Climate

Type

Label

Warm

Urban

Yes

Warm

Rural

Yes

Cold

Urban

No
Given the three possible kinds of values for each attribute in the hypothesis: 
- "?" (any value of the attribute is acceptable)
- A specific value (e.g., "Urban", "Rural")
- "0" (no value is acceptable)
Let's apply the List-Then-Eliminate algorithm to the training dataset:

 Initial Hypothesis Space:

Initially, the version space contains all possible hypotheses. Since we have two possible values for each attribute ("?", specific value, "0"), for two attributes, the initial hypothesis will be
H = VersionSpace
{<0,0>, 
<warm, urban> <warm, rural>, <warm, ?>, <warm, 0>
<cold, urban> <cold, rural>, <cold, ?>, <cold, 0>
<?, rural>, <?, urban>, <0, rural>, <0,urban>
<?, ?>

Explanation For h

Most Specific Hypothesis: 

<0,0> (Neither feature1 nor feature2 has any specific value assigned).

 Specific Hypotheses: 

These specify one of the features while leaving the other as either 0 (any value) or as specific values.

<warm, 0>, <cold, 0>, <0, rural>, <0, urban>

Hypotheses Specifying Both Features:

<warm, rural>, <warm, urban>, <cold, rural>, <cold, urban>

More General Hypotheses: 

These replace one of the specific values with ?, which represents a more general state than 0.

 <warm, ?>, <cold, ?>, <?, rural>, <?, urban>

Most General Hypothesis: 

<?, ?> (Both features can take any value).

1. Process Instance 1 (Positive Instance): <warm, urban, yes>

When the instance is checked, the hypothesis that predicts "No" will be eliminated.
Eg. When we pass <warm, urban> through hypothesis <warm, rural>, it sees mismatch in 2nd attribute and returns 'No'
When we pass <warm, urban> through hypothesis <warm, ?>, it sees that ? accepts both rural/urban in 2nd attribute and returns 'Yes'.
VersionSpace = 
{<0,0>, 
<warm, urban> <warm, rural>, <warm, ?>, <warm, 0>
<cold, urban> <cold, rural>, <cold, ?>, <cold, 0>
<?, rural>, <?, urban>, 
<?, ?>

2. Process Instance 2 (Positive Instance): <warm, rural, yes>

VersionSpace = 
   {
<warm, urban>,  <warm, ?>,  <?, urban>, 
<?, ?>
}

3. Process Instance 3 (Negative Instance): <cold, urban, no>

When we pass <cold, urban> through hypothesis <warm, ?>, it sees mismatch in 1st attribute and returns 'No'. So it is acceptable.
When we pass <cold, urban> through hypothesis <?, ?>, it sees sees no mismatch and returns 'Yes'. But it is a negative instance and so the hypothesis is not acceptable.
VersionSpace = {<warm, ?>}

 Conclusion:

The version space after applying the List-Then-Eliminate algorithm will have multiple hypotheses that are all consistent with the positive examples of the training dataset and have not been eliminated by the negative examples. The specific hypotheses will vary based on the attributes that can take "?" to allow for the variability seen in the positive instances.
 

Comments

Post a Comment

Popular posts from this blog

ANN Series - 10 - Backpropagation of Errors

-
Image
Watch the video to understand the forward pass in an ANN. Backpropagation, short for "backward propagation of errors," is a fundamental algorithm used for training artificial neural networks. It efficiently computes the gradient of the loss function with respect to the weights of the network, which is essential for adjusting the weights and minimizing the loss through gradient descent or other optimization techniques. The process involves two main phases: a forward pass and a backward pass.     Forward Pass   1. Input Layer:  The input features are fed into the network. 2. Hidden Layers:  Each neuron in these layers computes a weighted sum of its inputs (from the previous layer or the input layer) plus a bias term. This sum is then passed through an activation function to produce the neuron's output. This process repeats layer by layer until the output layer is reached. 3. Output Layer:  The final output of the network is computed, which is then used to calculate the loss
Read more

Regression 10 - Pseudo-Inverse Matrix Approach - Relationship between MLE and LSA - Derivation

-
Pseudo-Inverse Matrix Approach: The pseudo-inverse matrix approach is essentially the OLS approach. It provides a solution to the linear regression problem by minimizing the sum of squared residuals between the observed and predicted values. This approach is a direct algebraic method that does not make any probabilistic assumptions about the residuals; it simply finds the best fit in the least squares sense.   For simple linear regression, the MLE estimates of the coefficients will actually be the same as the Ordinary Least Squares (OLS) estimates, which are also the same as what you get from the pseudo-inverse matrix method, under the assumption of i.i.d. normal errors. In this blog we show how to prove that  Maximization of likelihood function under conditional Gaussian noise for a linear model is similar to the minimization of the sum of the squares error function.  The complete derivation along with formulae used are provided. Ensure that you go through the previous blogs to get a
Read more

Regression 9 - Maximum Likelihood Estimation(MLE) Approach for Regression - Derivation

-
  MLE Approach: When performing linear regression using MLE under the assumption that the residuals (errors) are independently and identically distributed (i.i.d.) with a normal distribution, we estimate the regression coefficients that maximize the likelihood of observing the given data. In this blog we see how to perform regression on a dataset that applies MLE for model fitting. The mathematical assumptions and derivations are given in detail.   The MLE approach gives you point estimates for the coefficients (mean of the likelihood distribution), and you can also compute the variance-covariance matrix of these estimates, which gives you the variances (and covariances) of the estimates. These variances are a measure of the uncertainty or the spread of the likelihood distribution of the parameter estimates. For simple linear regression, the MLE estimates of the coefficients will actually be the same as the Ordinary Least Squares (OLS) estimates, which are also the same as what you get
Read more