JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech IV MACHINE LEARNING Previous Question Paper (December - 2020 - R15)

The Probably Approximately Correct (PAC) hypothesis provides a theoretical framework for analyzing the learnability of a concept class. It defines learning as the ability of an algorithm to produce a hypothesis that is likely (with probability 1-δ) to have a low generalization error (at most ε) given a sufficient number of training samples.

Key components include:

• Sample Complexity: The number of training examples required to achieve the desired accuracy ε and confidence 1-δ. It must be polynomial in 1/ε, 1/δ, and the complexity of the concept class.
• PAC Learnability: A concept class is PAC learnable if there exists an algorithm that can learn any concept in the class in polynomial time, regardless of the underlying probability distribution.

The hypothesis essentially bridges the gap between empirical training error and true error, ensuring that with enough data, the learner converges to a hypothesis that is close to the target concept.

The Mistake Bound Model evaluates a learning algorithm based on the total number of classification errors it makes during a sequential learning process. Unlike PAC learning, which focuses on sample complexity, this model focuses on the online learning performance.

In this framework:

• The learner receives a sequence of instances one by one.
• For each instance, the learner must predict the label before the true label is revealed.
• The algorithm is evaluated by the cumulative number of mistakes made before it converges to the correct hypothesis.

A concept class is considered learnable in the mistake bound model if there exists an algorithm that makes a finite number of mistakes (the bound) for any target concept in the class. A classic example is the Halving Algorithm, which maintains a version space of all consistent hypotheses and predicts based on the majority vote, guaranteeing a mistake bound of log2(|C|), where |C| is the size of the concept class.