Summary CANDIDATE ELIMINATION ALGORITHM

.
Machine Learning

Version Spaces

Prof. Dr. Martin Riedmiller
AG Maschinelles Lernen und Natürlichsprachliche Systeme
Institut für Informatik
Technische Fakultät
Albert-Ludwigs-Universität Freiburg



Acknowledgment Slides were adapted from slides provided by
Tom Mitchell, Carnegie-Mellon-University
and Peter Geibel, University of Osnabrück




Martin Riedmiller, Albert-Ludwigs-Universität Freiburg, Machine Learning 1

, Overview of Today’s Lecture: Version Spaces
read T. Mitchell, Machine Learning, chapter 2

• Learning from examples
• General-to-specific ordering over hypotheses
• Version spaces and candidate elimination algorithm
• Picking new examples
• The need for inductive bias

Note: simple approach assuming no noise, illustrates key concepts




Martin Riedmiller, Albert-Ludwigs-Universität Freiburg, Machine Learning 2

, Introduction

• Assume a given domain, e.g. objects, animals, etc.
• A concept can be seen as a subset of the domain, e.g. birds⊆animals
• → Extension of concept
• Task: acquire intensional concept description from training examples
• Generally we can’t look at all objects in the domain




Martin Riedmiller, Albert-Ludwigs-Universität Freiburg, Machine Learning 3

, Training Examples for EnjoySport

• Examples: “Days at which my friend Aldo enjoys his favorite water sport”
• Result: classifier for days = description of Aldo’s behavior
Sky Temp Humid Wind Water Forecst EnjoySpt
Sunny Warm Normal Strong Warm Same Yes
Sunny Warm High Strong Warm Same Yes
Rainy Cold High Strong Warm Change No
Sunny Warm High Strong Cool Change Yes
What is the general concept?




Martin Riedmiller, Albert-Ludwigs-Universität Freiburg, Machine Learning 4