Page 168 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes
Example: It learned the concepts House, Tent and Arch.

 A near miss is an object that is not a case of the concept in query but that is very alike to
such instances.

Basic Approach of Winston’s Program

1. Start with a structural description of one recognized instance of the concept. Call that
description the concept definition.

2. Inspect descriptions of other recognized instances of the concepts. Generalize the definition
to include them.
3. Inspect the descriptions of near misses of the concept. Restrict the definition to exclude
these.

Version Spaces

 The objective of version spaces is to generate a description that is reliable with all positive
examples but no negative examples in the training set.

 This is another strategy to concept learning.
 Version spaces function by sustaining a set of possible descriptions and evolving that set
as new examples and near misses are displayed.

 The version space is just a set of descriptions, so an early idea is to maintain an explicit list
of those descriptions.

 Version space includes two subsets of the concept space.
 One subset known as G includes most general descriptions reliable with the training
examples The other subset includes the most particular descriptions reliable with the
training examples.
 The algorithm for narrowing the version space is known as the Candidate elimination
algorithm.

Algorithm: Candidate Elimination

 Given: A demonstration language and a set of positive and negative examples articulated
in that language.
 Compute: A concept description that is reliable with all the positive examples and none of
the negative examples.
1. Initialize G to enclose one element.
2. Initialize S to enclose one element: the first positive element.
3. Accept new training example. If it is a positive example, first remove from G any descriptions
that do not cover the example. Then modernize the set S to enclose most particular set of
descriptions in the version space that cover the example and the current elements of the
S set. Inverse actions for negative example.
4. If S and G are both singleton sets, then if they are indistinguishable, output their values
and halt.

162 LOVELY PROFESSIONAL UNIVERSITY