Lecture Notes

Introduction

• Good morning, welcome back.
• Questions about the candidate elimination algorithm and its boundaries (G and S).
  • Q: Will S always have one hypothesis in the most specific boundary?
  • A: Yes, only if the hypothesis space is conjunctive concepts.

Candidate Elimination Algorithm

• Candidate elimination is more general than just conjunctive concepts.
• In general, there can be multiple hypotheses.
• Focus on theoretical analysis of algorithms in upcoming classes.

Analyzing Algorithms

• Need to understand how to analyze algorithms: performance definitions.
• Current practice often lacks rigorous performance analysis.
• Performance can vary drastically across different datasets and problems.

Concept Space

• Data represented as d-dimensional vectors with binary features.
• The number of binary concepts is 2^(size of X), where X is defined by d binary features.
• Learning in concept space can be hard; need assumptions (inductive bias).
• Defined spaces can be conjunctive or disjunctive concepts.

Types of Concepts

• Conjunctive Concepts: All features must be satisfied (e.g., circular AND large).
• Disjunctive Concepts: At least one feature must be satisfied (e.g., circular OR large).
• Different classes can present varying levels of difficulty in learning.

Complexity of Problem Classes

• Complexity can be defined in multiple ways:
  1. Amount of data needed.
  2. Resources required (CPU cycles).
  3. Number of mistakes made during learning (focus of this lecture).

Online Learning

• Data represented as binary feature vectors.
• Learner predicts a class for each data point.
• Updates hypothesis based on mistakes made.
• Objective: Minimize mistakes.

Measuring Mistakes in Learning

• ML(c, D): Number of mistakes made by the learning algorithm to learn concept c using dataset D.
• Generalization to worst-case scenario: finding how many mistakes can be made for the hardest training dataset.
• Need to evaluate across all possible datasets.

Complexity Analysis

• OPT(C): The best possible number of mistakes for the hardest concept within a concept class.
• Importance of defining learning complexities for different problem types (e.g., conjunctive vs disjunctive).
• Challenge lies in finding precise bounds for optimal mistakes.

Halving Algorithm

• Theoretical algorithm for establishing tighter bounds.
• Involves defining sets based on current version space and making predictions.
• Predict, check for mistakes, and reduce the version space accordingly.
• Mistake Bound: Takes log base 2 of size of concept class to learn the target concept.

Winnow Algorithm

• Simplified and implementable algorithm compared to the halving algorithm.
• Focuses on monotone disjunctive concepts with restrictions on number of features.
• Provides a pathway to understanding perceptrons and neural networks.

Conclusion

• Programming assignment to be released on Monday.
• Further discussions and implementations to follow in the next classes.