Concept Learning as a Search

What is Machine Learning Introduction Well-Posed Learning Problems Designing a Learning System Steps for Designing Learning System Are Perspectives and Issues in Machine Learning Concept Learning and the General to Specific Ordering Concept Learning Task Concept Learning as a Search Important Representation Inductive Bias

Decision Tree Learning Types of Decision Tree Strengths and Weakness of Decision Tree Approach Appropriate Problems in Decision Tree Learning Issues in Decision Tree Learning What is Hypothesis Types of Hypothesis ID3 Information Gain for Each Feature

Artificial Neural Networks I Biological Motivation Neural Network Representations Appropriate Problems for Neural Network Learning Perceptron Genetic Algorithms Application Areas What is Reinforcement Learning Terms Used in Reinforcement Learning Approaches to Implement Reinforcement Learning Temporal Difference Learning EM Algorithm GIBS Algorithm

Concept Learning as a Search

Previous Page

Next Page

Concept Learning as a Search

Concept learning can be viewed as the task of searching through a large space of hypotheses implicitly defined by the hypothesis representation. The goal of this search is to find the hypothesis that best fits the training examples. It is important to note that by selecting a hypothesis representation, the designer of the learning algorithm implicitly defines the space of all hypotheses that the program can ever represent and therefore can ever learn.

Consider, for example, the instances X and hypotheses H in the EnjoySport learning task.Given that the attribute Sky has three possible values, and that AirTemp, Humidity, Wind, Water, and Forecast each have two possible values, the instance space X contains exactly 3.2.2.2.2.2 = 96 distance instances. A similar calculation shows that there are 5.4-4 -4 -4.4 = 5120 syntactically distinct hypotheses within H.

General-to-Specific Ordering of Hypotheses

Many algorithms for concept learning organize the search through the hypothesis space by relying on a very useful structure that exists for any concept learning problem: A general-tospecific ordering of hypotheses. By taking advantage of this naturally occurring structure over the hypothesis space, we can design learning algorithms that exhaustively search even infinite hypothesis spaces without explicitly enumerating every hypothesis. To illustrate the general-to-specific ordering, consider the two hypotheses.

H1 = (Sunny,?,?, Strong, ?, ?)

H2 = (Sunny,?,?,?,?,?)

FIND-S algorithm:

The find-S algorithm is a basic concept learning algorithm in machine learning. The find-S algorithm finds the most specific hypothesis that fits all the positive examples. We have to note here that the algorithm considers only those positive training example. The find-S algorithm starts with the most specific hypothesis and generalizes this hypothesis each time it fails to classify an observed positive training data. Hence, the Find-S algorithm moves from the most specific hypothesis to the most general hypothesis.

Previous Page

Next Page

Concept Learning as a Search

MACHINE LEARNING

DECISION TREE LEARNING

ARTIFICIAL NEURAL NETWORKS-I

Concept Learning as a Search