Jawaharlal Nehru Technological University Hyderabad B.Tech III Machine Learning Previous Question Paper (August/September - 2021 - R18)

A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E. A problem is considered well-posed if it clearly specifies these three components: the task, the performance measure, and the source of experience.

Four examples of well-posed learning problems include:

1. Playing Checkers: Task T is playing checkers, performance measure P is the percent of games won against opponents, and experience E is playing practice games against itself.
2. Handwriting Recognition: Task T is recognizing and classifying handwritten words, performance measure P is the percentage of words correctly classified, and experience E is a database of handwritten words with given classifications.
3. Spam Filtering: Task T is identifying spam emails, performance measure P is the accuracy of classification, and experience E is a set of emails labeled as spam or ham.
4. Autonomous Driving: Task T is driving on public highways, performance measure P is the average distance traveled without error, and experience E is a sequence of images and steering commands recorded from human drivers.

Candidate elimination is a machine learning algorithm used for concept learning that identifies the set of all hypotheses consistent with the training examples. Unlike the Find-S algorithm, which maintains only the most specific hypothesis, the candidate elimination algorithm maintains the version space, which represents the entire set of hypotheses consistent with the observed data.

The algorithm operates by maintaining two sets of boundary hypotheses:

1. Specific Boundary (S): The set of the most specific hypotheses consistent with the positive examples seen so far.
2. General Boundary (G): The set of the most general hypotheses consistent with the negative examples seen so far.

The process involves iterating through training examples and updating these boundaries:

• For each positive example, the algorithm generalizes the S boundary to include the example and removes any hypotheses in G that are inconsistent with the new positive example.
• For each negative example, the algorithm specializes the G boundary to exclude the example and removes any hypotheses in S that are inconsistent with the new negative example.

The algorithm terminates when the version space converges to a single hypothesis or when no consistent hypothesis remains. This approach is powerful because it explicitly tracks the uncertainty in the hypothesis space rather than committing to a single path.