Machine Learning-II Unit -1 BAI702

INTRODUCTION
Syllabus:
Introduction: Well posed learning problems, Designing a Learning system, Perspective and
Issues in Machine Learning.
Concept Learning and the General-to-Specific Ordering: A Concept Learning Task, Concept
Learning as Search, Find-S: Finding a Maximally Specific Hypothesis, Version Spaces and the
Candidate-Elimination Algorithm, Remarks on Version Spaces and Candidate-Elimination,
Inductive Bias.

Ever since computers were invented, we have wondered whether they might be made to
[Link] we could understand how to program them to learn-to improve automatically with
experience-the impact would be dramatic.
 Imagine computers learning from medical records which treatments are most
effectivefor new diseases
 Houses learning from experience to optimize energy costs based on the particular
usagepatterns of their occupants.
 Personal software assistants learning the evolving interests of their users in
order tohighlight especially relevant stories from the online morning newspaper

A successful understanding of how to make computers learn would open up many new
usesof computers and new levels of competence and customization

Some successful applications of machine learning

 Learning to recognize spoken words
 Learning to drive an autonomous vehicle
 Learning to classify new astronomical structures
 Learning to play world-class backgammon

Why is Machine Learning Important?

 Some tasks cannot be defined well, except by examples (e.g., recognizing people).
 Relationships and correlations can be hidden within large amounts of data.
MachineLearning/Data Mining may be able to find these relationships.
 Human designers often produce machines that do not work as well as desired in
theenvironments in which they are used.
 The amount of knowledge available about certain tasks might be too large for
explicitencoding by humans (e.g., medical diagnostic).
 Environments change over time.
 New knowledge about tasks is constantly being discovered by humans. It may
bedifficult to continuously re-design systems “by hand”.

1 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

WELL-POSED LEARNING PROBLEMS

Definition: A computer program which learns from experience is called a machine learning
program or simply a learning program. Such a program is sometimes also referred to as a
learner.
Tom Mitchell provides a more modern definition: A computer program is said to learn
from experience E with respect to some class of tasks T and performance measure P, if its
performance at tasks in T, as measured by P, improves with experience E.

In general to have a Well Posed learning Problems, we must identify 3 features:

1. The class of tasks(T)
2. The measure of performance to be improved(P)
3. The source of experience(E)

Examples
1. Checkers game: A computer program that learns to play checkers might improve its
performance as measured by its ability to win at the class of tasks involving playing
checkers games, through experience obtained by playing games against itself.

Fig: Checker game board

A checkers learning problem:
 Task T: playing checkers
 Performance measure P: percent of games won against opponents
 Training experience E: playing practice games against itself
2. A handwriting recognition learning problem:
 Task T: recognizing and classifying handwritten words within images
 Performance measure P: percent of words correctly classified
 Training experience E: A database of handwritten words with given
classifications
3. A robot driving learning problem:
 Task T: driving on public four-lane highways using vision sensors
 Performance measure P: average distance travelled before an error (as
judged by human overseer)
 Training experience E: a sequence of images and steering commands
recorded while observing a human driver

2 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

4. Spam Mail detection learning problem:

 Task T: To recognize and classify mails into 'spam' or 'not spam'.
 Performance measure P: Total percent of mails being correctly classified as
'spam' (or 'not spam’) by the program.
 Training experience E: A set of mails with given labels ('spam' / 'not spam').

DESIGNING A LEARNING SYSTEM

The basic design issues and approaches to machine learning are illustrated by designing a
program to learn to play checkers, with the goal of entering it in the world checkers
tournament
1. Choosing the Training Experience
2. Choosing the Target Function
3. Choosing a Representation for the Target Function
4. Choosing a Function Approximation Algorithm
a) Estimating training values
b) Adjusting the weights
5. The Final Design

1. Choosing the Training Experience

 The first design choice is to choose the type of training experience from which the
system will learn.
 The type of training experience available can have a significant impact on success or
failure of the learner.
 There are 3 Key attributes which impact on success or failure of the learner:
a) Whether the training experience provides direct or indirect feedback regarding the
choices made by the performance system.
b) The degree to which the learner controls the sequence of training examples.
c) How well it represents the distribution of examples over which the final system
performance P must be measured.
a) Whether the training experience provides Direct or Indirect Feedback regarding
the choices made by the performance system.
Direct training Feedback
a. One key attribute is whether the training experience provides direct or indirect
feedback regarding the choices made by the performance system.
b. Mostly, learning from direct training feedback is typically easier than learning
from indirect feedback.
c. In learning to play checkers, the system might learn from direct training
examples consisting of individual checkers board states and the correct
move for each.
d. For each board state, set of possible moves are given

3 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Indirect training Feedback

 Indirect training examples consisting of the move sequences and final outcomes of
various games played.
 The information about the correctness of specific moves early in the game must be
inferred indirectly from the fact that the game was eventually won or lost.
 Here the learner faces an additional problem of credit assignment, or determining
the degree to which each move in the sequence deserves credit or blame for the final
outcome.
 Credit assignment can be a particularly difficult problem because the game can be
lost even when early moves are optimal, if these are followed later by poor moves.

b) The degree to which the learner controls the sequence of training examples.
 The learner might depends on the teacher to select informative board states and to
provide the correct move for each.
 The learner might itself propose board states that it finds particularly confusing and
ask the teacher for the correct move.

4 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 The learner may have complete control over both the board states and (indirect)
training classifications, as it does when it learns by playing against itself with no
teacher present.

c) How well it represents the distribution of examples over which the final system
performance P must be measured.
 A third important attribute of the training experience is how well it represents the
distribution of examples over which the final system performance P must be
measured.
 In checkers learning scenario, the performance metric P is the percent of games the
system wins in the world tournament.
 If its training experience E consists only of games played against itself, there is a
danger that this training experience might not be fully representative of the
distribution of situations over which it will later be tested.
 It is necessary to learn from a distribution of examples that is different from those
on which the final system will be evaluated.

2. Choosing the Target Function

 The next design choice is to determine exactly what type of knowledge will be
learned and how this will be used by the performance program.
 Let’s consider a checkers-playing program that can generate the legal moves from
any board state.
 The program needs only to learn how to choose the best move from among these
legal moves. We must learn to choose among the legal moves, the most obvious
choice for the type of information to be learned is a program, or function, that
chooses the best move for any given board state.
 Let ChooseMove be the target function and the notation is
ChooseMove : B→ M
which indicate that this function accepts as input any board from the set of legal
board states B and produces as output some move from the set of legal moves M.
 ChooseMove is a choice for the target function in checkers example, but this
function will turn out to be very difficult to learn given the kind of indirect training
experience available to our system.
 An alternative target function is an evaluation function that assigns a numerical
score to any given board state.

5 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 Let the target function V and the notation

V:B→R
which denote that V maps any legal board state from the set B to some real value.
Intend for this target function V to assign higher scores to better board states. If the
system can successfully learn such a target function V, then it can easily use it to
select the best move from any current board position.
 Let us define the target value V(b) for an arbitrary board state b in B, as follows:
 If b is a final board state that is won, then V(b) = 100
 If b is a final board state that is lost, then V(b) = -100
 If b is a final board state that is drawn, then V(b) = 0
 If b is a not a final state in the game, then V(b) = V(b' ),
Where b' is the best final board state that can be achieved starting from b and playing
optimally until the end of the game.
 Except for the trivial cases (cases 1-3) in which the game has already ended,
determining the value of V(b) for a particular board state requires (case 4) searching
ahead for the optimal line of play, all the way to the end of the game.
 Case-4 can be accomplished by generating the successor board state produced by
every legal move, then using V to choose the best successor state and therefore the
best legal move.

3. Choosing a Representation for the Target Function

Let’s choose a simple representation - for any given board state, the function c will
becalculated as a linear combination of the following board features:
 xl: the number of black pieces on the board
 x2: the number of red pieces on the board
 x3: the number of black kings on the board
 x4: the number of red kings on the board
 x5: the number of black pieces threatened by red (i.e., which can be captured
on red's next turn)
 x6: the number of red pieces threatened by black

6 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Thus, learning program will represent as a linear function of the form

Where,
 w0 through w6 are numerical coefficients, or weights, to be chosen by the
learningalgorithm.
 Learned values for the weights w1 through w6 will determine the relative
importance of the various board features in determining the value of the board
 The weight w0 will provide an additive constant to the board value.

4. Choosing a Function Approximation Algorithm

 In order to learn the target function f we require a set of training examples, each
describing aspecific board state b and the training value Vtrain(b) for b.

 Each training example is an ordered pair of the form (b, Vtrain(b)).

 For instance, the following training example describes a board state b in which black
has won the game (note x2 = 0 indicates that red has no remaining pieces) and for
which the target function value Vtrain(b) is therefore +100.

((x1=3, x2=0, x3=1, x4=0, x5=0, x6=0), +100)

Function Approximation Procedure

a) Derive training examples from the indirect training experience available to the learner
b) Adjusts the weights wi to best fit these training examples

a) Estimating training values

 A simple approach for estimating training values for intermediate board states is to
assign the training value of Vtrain(b) for any intermediate board state b to be
V̂ (Successor(b))
 Where , V̂ is the learner's current approximation to V
 Successor(b) denotes the next board state following b for which it is again the
program's turn to move .

7 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Rule for estimating training values

Vtrain(b) ← V̂ (Successor(b))
b) Adjusting the weights
 Specify the learning algorithm for choosing the weights wi to best fit the set of
training examples {(b, Vtrain(b))}
 A first step is to define what we mean by the best fit to the training data.
 One common approach is to define the best hypothesis, or set of weights, as that
which minimizes the squared error E between the training values and the values
predicted by the hypothesis.

 Several algorithms are known for finding weights of a linear function that minimize
E. One such algorithm is called the least mean squares, or LMS training rule.
 For each observed training example it adjusts the weights a small amount in the
direction that reduces the error on this training example. 
 The LMS algorithm is defined as follows:

Working of weight update rule

 When the error (Vtrain(b)- V̂ (b)) is zero, no weights are changed.
 When (Vtrain(b) - V̂ (b)) is positive (i.e., when V̂ (b) is too low), then each
weightis increased in proportion to the value of its corresponding feature. This
will raise the value of V̂ (b), reducing the error.
 If the value of some feature xi is zero, then its weight is not altered regardless
ofthe error, so that the only weights updated are those whose features actually
occur on the training example board.

8 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

5. The Final Design

The final design of checkers learning system can be described by four distinct program
modules that represent the central components in many learning systems

1. The Performance System is the module that must solve the given performance task
by using the learned target function(s). It takes an instance of a new problem (new
game) as input and produces a trace of its solution (game history) as output.

2. The Critic takes as input the history or trace of the game and produces as output a
set of training examples of the target function

3. The Generalizer takes as input the training examples and produces an output
hypothesis that is its estimate of the target function. It generalizes from the specific
training examples, hypothesizing a general function that covers these examples and
other cases beyond the training examples.

4. The Experiment Generator takes as input the current hypothesis and outputs a
new problem (i.e., initial board state) for the Performance System to explore. Its role
is to pick new practice problems that will maximize the learning rate of the overall
system.

9 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

The sequence of design choices made for the checkers program is summarized in below
figure:

PERSPECTIVES AND ISSUES IN MACHINE LEARNING

 One useful perspective on machine learning is that it involves searching a very large
space of possible hypotheses to determine one that best fits the observed data and any
prior knowledge held by the learner.
Issues in Machine Learning
The field of machine learning, and much of this book, is concerned with answering
questions such as the following
 What algorithms exist for learning general target functions from specific
training examples? In what settings will particular algorithms converge to the
desired function, given sufficient training data? Which algorithms perform best
for which types of problems and representations?

10 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 How much training data is sufficient? What general bounds can be found to relate
the confidence in learned hypotheses to the amount of training experience and the
character of the learner's hypothesis space?
 When and how can prior knowledge held by the learner guide the process of
generalizing from examples? Can prior knowledge be helpful even when it is only
approximately correct?
 What is the best strategy for choosing a useful next training experience, and how
does the choice of this strategy alter the complexity of the learning problem?
 What is the best way to reduce the learning task to one or more function
approximation problems? Put another way, what specific functions should the
system attempt to learn? Can this process itself be automated?
 How can the learner automatically alter its representation to improve its ability
to represent and learn the target function?

11 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

CONCEPT LEARNING
 A Concept is a subset of objects or events defined over a larger set.
 For example, we refer to the set of everything ( i.e. all objects) as the set of things.
 Animals are a subset of things, and birds are subset of animals.
 In more technical terms, a Concept is a Boolean valued function defined over this
larger set.
 For example, a function defined over all animals whose value is true for birds and false for
every other animal.

 Concept learning can be formulated as a problem of searching through a predefined space

of potential hypotheses for the hypothesis that best fits the training examples.
 Target Function (that we assume exists) that can best map inputs to outputs on all possible
observations from the problem domain is called a hypothesis in machine learning.

Formal Definition for Concept learning - Inferring a Boolean-valued function from training
examples of its input and output

A CONCEPT LEARNING TASK

Consider the example task of learning the target concept "Days on which Aldo enjoys his
favorite water sport”
Example Sky AirTemp Humidity Wind Water Forecast EnjoySport

1 Sunny Warm Normal Strong Warm Same Yes

2 Sunny Warm High Strong Warm Same Yes

3 Rainy Cold High Strong Warm Change No

4 Sunny Warm High Strong Cool Change Yes

Table: Positive and negative training examples for the target concept EnjoySport.

The task is to learn to predict the value of EnjoySport for an arbitrary day, based on the
values of its other attributes?

12 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

What hypothesis representation is provided to the learner?

 Let us begin by considering a simple representation in which each hypothesis consists of a
conjunction of constraints on the instance attributes.
 In particular, let each hypothesis be a vector of six constraints, specifying the values of the
six attributes
o Sky – (values: Sunny, Cloudy, Rainy),
o AirTemp – (values: Warm, Cold),
o Humidity – (values: Normal, High),
o Wind – (values: Strong, Weak),
o Water – (values: Warm, Cold),
o Forecast – (values: Same, Change).
 For each attribute, the hypothesis will either
o Indicate by a "?' that any value is acceptable for this attribute,
o Specify a single required value (e.g., Warm) for the attribute, or
o Indicate by a "Ø" that no value is acceptable.
 If some instance x satisfies all the constraints of hypothesis h, then h classifies x as a
positive example (h(x) = 1).
 To illustrate, the hypothesis that
– A person enjoys her favorite sport only on warm days with high humidity
(independent of the values of the other attributes) is represented by the
expression
<?, Warm, High, ?, ?, ?>
– The most general hypothesis -Everyday is positive example-is represented by
<?, ?,?, ?, ?, ? >
– The most specific possible hypothesis- No day is a positive example-is
represented by
<Ø, Ø, Ø, Ø, Ø, Ø>
Notation
 The set of items over which the concept is defined is called the set of instances, which is
denoted by X.
 Example: X is the set of all possible days, each represented by the attributes: Sky,
AirTemp, Humidity, Wind, Water, and Forecast. 
 The concept or function to be learned is called the target concept, which is denoted by c.
c can be any Boolean valued function defined over the instances X
c: X→ {O, 1}
 Example: In the current example, the target concept corresponds to the value of the
attribute EnjoySport. i.e.,
o c(x) = 1 if EnjoySport = Yes, and
o c(x) = 0 if EnjoySport = No.
 Instances for which c(x) = 1 are called positive examples, or members of the target concept.
 Instances for which c(x) = 0 are called negative examples, or non-members of the
target concept.

13 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 The ordered pair (x, c(x)) to describe the training example consisting of the instance x and
its target concept value c(x).
 D to denote the set of available training examples.
 The symbol H to denote the set of all possible hypotheses that the learner may consider
regarding the identity of the target concept. Each hypothesis h in H represents a Boolean-
valued function defined over X
h: X→{0, 1}
The goal of the learner is to find a hypothesis h such that h(x) = c(x) for all x in X.

Table: The EnjoySport concept learning task.

THE INDUCTIVE LEARNING HYPOTHESIS

 Inductive learning is a learning approach in which rules(hypothesis) are inferred from

the facts or data.
 Inductive learning algorithms can at best guarantee that the output hypothesis fits
the target concept over the training data.
 Assumption: an hypothesis that approximates well the training data will also
approximate the target function over unobserved examples. i.e. given a significant
training set, the output hypothesis is able to make predictions.
• The inductive learning hypothesis: Any hypothesis found to approximate the target
function well over a sufficiently large set of training examples will also approximate the
target function well over other unobserved examples.

14 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

CONCEPT LEARNING AS SEARCH

 Concept learning is a task of searching an hypotheses space.

 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.

Example:
Consider the instances X and hypotheses H in the EnjoySport learning task. The attribute
Sky has three possible values, and AirTemp, Humidity, Wind, Water, Forecast each have two
possible values, the instance space X contains exactly
[Link].2.2 = 96 distinct instances
[Link].4.4 = 5120 syntactically distinct hypotheses within H.

Every hypothesis containing one or more "Φ" symbols represents the empty set of
instances; that is, it classifies every instance as negative.
1 + ([Link].3.3) = 973. Semantically distinct hypotheses

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-to-specific 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, ?, ?, ?, ?, ?)
 Consider the sets of instances that are classified positive by hl and by h2.
 h2 imposes fewer constraints on the instance, it classifies more instances as positive. So,
any instance classified positive by hl will also be classified positive by h2. Therefore, h2
is more general than hl.
 Given hypotheses hj and hk, hj is more-general-than or- equal do hk if and only if any
instance that satisfies hk also satisfies hi

15 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 In the figure, the box on the left represents the set X of all instances, the box on the
right the set H of all hypotheses.
 Each hypothesis corresponds to some subset of X-the subset of instances that it
classifies positive.
 The arrows connecting hypotheses represent the more - general -than relation, with
the arrow pointing toward the less general hypothesis.
 Note the subset of instances characterized by h2 subsumes the subset characterized by
hl , hence h2 is more - general– than h1

FIND-S: FINDING A MAXIMALLY SPECIFIC HYPOTHESIS

 FIND-S Algorithm is used to find the Maximally Specific Hypothesis. Using the Find-S
algorithm gives a single maximally specific hypothesis for the given set of training
examples.
 FIND-S is guaranteed to output the most specific hypothesis within H that is consistent
with the positive training examples.
 One way is to begin with the most specific possible hypothesis in H, then generalize this
hypothesis each time it fails to cover an observed positive training example.

16 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Steps Involved In Find-S:

1. Start with the most specific hypothesis
h = <ϕ, ϕ, ϕ, ϕ, ϕ, ϕ>
2. Take the next example and if it is negative, then no changes occur to the
hypothesis.
3. If the example is positive and we find that our initial hypothesis is too
specific then we update our current hypothesis to general condition.
4. Keep repeating the above steps till all the training examples are complete.
5. After we have completed all the training examples we will have the final
hypothesis when can used to classify the new examples.

Important Representation:
 ? Indicates that any value is acceptable for the attribute.
 Specify a single required value ( e.g., Cold ) for the attribute.
 Φ indicates that no value is acceptable.
 The most general hypothesis is represented by: <?, ?, ?, ?, ?, ?>
 The most specific hypothesis is represented by : <ϕ, ϕ, ϕ, ϕ, ϕ, ϕ>

FIND-S Algorithm

17 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

To illustrate this algorithm, assume the learner is given the sequence of training
examplesfrom the EnjoySport task

Exampl Sky AirTemp Humidity Wind Water Forecast EnjoySport

e
1 Sunny Warm Normal Strong Warm Same Yes
2 Sunny Warm High Strong Warm Same Yes
3 Rainy Cold High Strong Warm Change No
4 Sunny Warm High Strong Cool Change Yes

 The first step of FINDS is to initialize h to the most specific hypothesis in H.
h0(Ø, Ø, Ø, Ø, Ø, Ø)
 By observing the first training example which is positive, but it does not satisfy
the hypothesis, so each Ø is replaced by the next more general constraint that fits
the example.
h1  (Sunny, Warm, Normal, Strong, Warm, Same)

 Consider the next training example (also positive in this case) forces the algorithm to
further generalize h, by substituting a "?' in place of any attribute value in h that is not
satisfied by the new example.
h2  (Sunny, Warm, ?, Strong, Warm, Same)
 Next is negative example, so need to consider.
h3  (Sunny, Warm, ?, Strong, Warm, Same)
 Next, the fourth example leads to further generalization of h
h4  (Sunny, Warm, ?, Strong, ?, ?)

18 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

The key property of the FIND-S algorithm

 FIND-S is guaranteed to output the most specific hypothesis within H that is consistent
with the positive training examples
 FIND-S algorithm’s final hypothesis will also be consistent with the negative examples
provided the correct target concept is contained in H, and provided the training examples
are correct.
 Problems:
o There can be more than one “most specific hypotheses”
o We cannot say if the learner converged to the correct target
o Why choose the most specific?
o If the training examples are inconsistent, the algorithm can be mislead: no tolerance
to rumor.
o Negative examples are not considered

Unanswered by FIND-S

1. Has the learner converged to the correct target concept?

2. Why prefer the most specific hypothesis?
3. Are the training examples consistent?
4. What if there are several maximally specific consistent hypotheses?

19 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

VERSION SPACES AND THE CANDIDATE-ELIMINATION ALGORITHM

Note difference between definitions of consistent and satisfies

 An example x is said to satisfy hypothesis h when h(x) = 1, regardless of whether x is
a positive or negative example of the target concept.
 An example x is said to consistent with hypothesis h iff h(x) = c(x)

Version Space
• Definition: The version space VSH,D is the subset of the hypothesis from H
consistent with the training example in D,

The LIST-THEN-ELIMINATION algorithm

 The LIST-THEN-ELIMINATE algorithm first initializes the version space to
contain all hypotheses in H and then eliminates any hypothesis found
inconsistent with any training example.

 List-Then-Eliminate works in principle, as long as version space is finite.

 However, since it requires exhaustive enumeration of all hypotheses in practice it is not
feasible.

20 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Consistent hypothesis and version space, List-then-eliminate

algorithmExample
 Attrib1A,B
 Attrib2P,Q
 Here Attrib1 and Attrib2 are two features (attributes) with two possible values for each
feature or attribute.
 Instance Space: (A, P), (A, Q), (B, P), (B, Q) – 4 Examples
 Hypothesis Space:
(A, P), (A, Q), (A, ø), (A, ?), (B, P), (B, Q), (B, ø), (B, ?), (ø, P), (ø, Q), (ø, ø), (ø, ?), (?, P), (?, Q), (?, ø),
(?, ?) – 16 Hypothesis
 Semantically Distinct Hypothesis :
(A, P), (A, Q), (A, ?), (B, P), (B, Q), (B, ?), (?, P), (?, Q), (?, ?), (ø, ø) – 10

 Version Space:
– (A, P), (A, Q), (A, ?), (B, P), (B, Q), (B, ?), (?, P), (?, Q), (?, ?), (ø, ø)
 Training instances:
Attrib1 Attrib1 Target

A P YES

A Q YES

 Consistent Hypothesis are (Version Space):

(A, ?), (?, ?)

A More Compact Representation for Version Spaces

 The version space is represented by its most general and least general members. These
members form general and specific boundary sets that delimit the version space within
the partially ordered hypothesis space.

21 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Theorem: Version Space representation theorem

Theorem: Let X be an arbitrary set of instances and Let H be a set of Boolean-valued

hypotheses defined over X. Let c: X →{O, 1} be an arbitrary target concept defined over X,
and let D be an arbitrary set of training examples {(x, c(x))). For all X, H, c, and D such that S
and G are well defined,

VERSION SPACES AND THE CANDIDATE-ELIMINATION ALGORITHM

• Version Space: It is intermediate of general hypothesis and Specific hypothesis. It
not only just written one hypothesis but a set of all possible hypothesis based on
training data-set.
• The candidate elimination algorithm incrementally builds the version space given a
hypothesis space H and a set D of examples.
• The examples are added one by one; each example possibly shrinks the version space
by removing the hypotheses that are inconsistent with the example.
• The candidate elimination algorithm does this by updating the general and specific
boundary for each new example.
– You can consider this as an extended form of Find-S algorithm.
– Consider both positive and negative examples.
– Actually, positive examples are used here as Find-S algorithm (Basically they
are generalizing from the specification).
– While the negative example is specified from generalize form.

22 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

CANDIDATE-ELIMINATION Learning Algorithm

 The CANDIDATE-ELIMINTION algorithm computes the version space containing all
hypotheses from H that are consistent with an observed sequence of training examples.

An Illustrative Example

Example Sky AirTemp Humidity Wind Water Forecast EnjoySport

1 Sunny Warm Normal Strong Warm Same Yes
2 Sunny Warm High Strong Warm Same Yes
3 Rainy Cold High Strong Warm Change No
4 Sunny Warm High Strong Cool Change Yes

 CANDIDATE-ELIMINTION algorithm begins by initializing the version space to the set of

all hypotheses in H;
Initializing the G boundary set to contain the most general hypothesis in H
G0=<?, ?, ?, ?, ?, ?>
Initializing the S boundary set to contain the most specific (least general)
hypothesis
S0=< Ø, Ø, Ø, Ø, Ø, Ø>
 When the first training example is presented, the CANDIDATE-ELIMINTION algorithm
checks the S boundary and finds that it is overly specific and it fails to cover the positive
example.
 The boundary is therefore revised by moving it to the least more general hypothesis that
covers this new example

23 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 No update of the G boundary is needed in response to this training example because Go

correctly covers this example

 When the second training example is observed, it has a similar effect of generalizing S
further to S2, leaving G again unchanged i.e., G2 = G1 = G0

 Consider the third training example. This negative example reveals that the G boundary
of the version space is overly general, that is, the hypothesis in G incorrectly predicts
that this new example is a positive example.
 The hypothesis in the G boundary must therefore be specialized until it correctly
classifies this new negative example

24 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 Given that there are six attributes that could be specified to specialize G 2, why are
there only three new hypotheses in G3?
 For example, the hypothesis h = (?, ?, Normal, ?, ?, ?) is a minimal specialization of G 2
that correctly labels the new example as a negative example, but it is not included in G3.
The reason this hypothesis is excluded is that it is inconsistent with the previously
encountered positive examples
 Consider the fourth training example.

 This positive example further generalizes the S boundary of the version space. It also
results in removing one member of the G boundary, because this member fails to cover
the new positive example.
 After processing these four examples, the boundary sets S 4 and G4 delimit the version
space of all hypotheses consistent with the set of incrementally observed training
examples.

25 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

REMARKS ON VERSION SPACES AND CANDIDATE-ELIMINATION

1. Will the CANDIDATE-ELIMINATION algorithm converge to the correct hypothesis?
– The version space learned by the candidate-elimination algorithm will converge
toward the hypothesis that correctly describes the target concept, provided
(a) there are no errors in the training examples, and
(b) there is some hypothesis in H that correctly describes the target concept.
2. What Training Example Should the Learner Request Next?
- Examples provided by external
- Take an example on learner’s own
- Version space size is reduced with each new training example.
- log2|VS| training examples are required to get correct target concept if by each
example version space size is reduced by half.
- Otherwise more than log2|VS| training examples are required.
3. How Can Partially Learned Concepts Be Used?

 Even though the version space above still contains multiple hypotheses, indicating that the
target concept has not yet been fully learned, it is possible to classify certain examples with
the same degree of confidence as if the target concept had been uniquely identified.
 To illustrate, suppose the learner is asked to classify the four new instances shown in Table
below:

 Note that although instance A was not among the training examples, it is classified as a
positive instance by every hypothesis in the current version space.
 Similarly, instance B is classified as a negative instance by every hypothesis in the version
space. This instance can therefore be safely classified as negative, given the partially
learned concept.

26 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 Instance C presents a different situation. Half of the version space hypotheses classify it as
positive and half classify it as negative. Thus, the learner cannot classify this example with
confidence until further training examples are available.
 Finally, instance D is classified as positive by two of the version space hypotheses and
negative by the other four hypotheses. In this case we have less confidence in the
classification than in the unambiguous cases of instances A and B. Still, the vote is in favor
of a negative classification, and one approach we could take would be to output the
majority vote, perhaps with a confidence rating indicating how close the vote was.

INDUCTIVE BIAS

 The fundamental questions for inductive inference :

1. What if the target concept is not contained in the hypothesis space?
2. Can we avoid this difficulty by using a hypothesis space that includes every possible
hypothesis?
3. How does the size of this hypothesis space influence the ability of the algorithm to
generalize to unobserved instances?
4. How does the size of the hypothesis space influence the number of training
examples that must be observed?
 These fundamental questions are examined in the context of the CANDIDATE-
ELIMINTION algorithm.
 As we shall see, though, the conclusions we draw from this analysis will apply to any
concept learning system that outputs any hypothesis consistent with the training data.

A Biased Hypothesis Space

 Suppose the target concept c(x) is not contained in the hypothesis space H, then none of the
hypothesis of H will be consistent with a set of training examples D.
 The obvious solution is to enrich the hypothesis space to include every possible hypothesis.
 To illustrate, consider again the EnjoySport example in which we restricted the hypothesis
space to include only conjunctions of attribute values.

27 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

 Because of this restriction, the hypothesis space is unable to represent even simple
disjunctive target concepts such as “Sky = Sunny or Sky = Cloudy”.
 This hypothesis, although it is the maximally specific hypothesis from H that is consistent
with the first two examples, is already overly general.
 It incorrectly covers the third (negative) training example.
 The problem is that we have biased the learner to consider only conjunctive hypotheses. In
this case we require a more expressive hypothesis space.

An Unbiased Learner
 The solution to the problem of assuring that the target concept is in the hypothesis space H
is to provide a hypothesis space capable of representing every teachable concept that is
representing every possible subset of the instances X.
 The set of all subsets of a set X is called the power set of X.
 In the EnjoySport learning task the size of the instance space X of days described bythe six
attributes is 96 instances.
 Thus, there are 296 distinct target concepts that could be defined over this instance spaceand
learner might be called upon to learn.
 The conjunctive hypothesis space is able to represent only 973 of these - a biased
hypothesis space indeed.
 Let us reformulate the EnjoySport learning task in an unbiased way by defining a new
hypothesis space H' that can represent every subset of instances. 
 The target concept "Sky = Sunny or Sky = Cloudy" could then be described as
(Sunny, ?, ?, ?, ?, ?) ꓦ (Cloudy, ?, ?, ?, ?, ?)

The Futility of Bias-Free Learning

 The fundamental property of inductive inference —
“a learner that makes no a priori assumptions regarding the identity of the target
concept has no rational basis for classifying any unseen instances”
 Candidate elimination algorithm was able to generalize beyond the observed training
examples in our original formulation of the EnjoySport task is that it was biased by the
implicit assumption that the target concept could be represented by a conjunction of
attribute values.
 In cases where this assumption is correct (and the training examples are error-free), its
classification of new instances will also be correct.
 If this assumption is incorrect, however, it is certain that the candidate elimination
algorithm will miss-classify at least some instances from X.

28 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

The idea of Inductive Bias

 The key idea we wish to capture here is the policy by which the learner generalizes beyond
the observed training data, to infer the classification of new instances.
 Need to make assumptions
o Experience alone doesn’t allow us to make conclusions about unseen data instances.
 There are 2 types of bias:
o Restriction: limit the hypothesis space
o Preference: impose ordering on hypothesis space.
 A preference bias is more desirable than a restriction bias, because it allows the learner to
work within a complete hypothesis space that is assured to contain the unknown target
function.
INDUCTIVE BIAS
 The inductive bias (also known as learning bias) of a learning algorithm is the set of
assumptions that the learner uses to predict outputs of given inputs that it has not
encountered.
 In machine learning, the term inductive bias refers to a set of (explicit or implicit)
assumptions made by a learning algorithm in order to perform induction, that is, to
generalize a finite set of observation (training data) into a general model of the domain.
 Inductive reasoning is the process of learning general principles on the basis of specific
instances – in other words, it’s what any machine learning algorithm does when it produces
a prediction for any unseen test instance on the basis of a finite number of training
instances. Inductive bias describes the tendency for a system to prefer a certain set of
generalizations over others that are equally consistent with the observed data.
 Without inductive bias, a learner can’t generalize from observed examples to new examples
better than random guessing.

 Consider a concept learning algorithm L for the set of instances X. Let c be an arbitrary
concept defined over X, and let Dc = {<x,c(x)>} be an arbitrary set of training examples of c.
 After training, L is asked to classify a new instance xi.
 Let L(xi, Dc) denote the classification (e.g., positive or negative) that L assigns to xi after
learning from the training data Dc.
 We can describe this inductive inference step performed by L as :

 The symbol ≻ is called “inductively inferred from”

 For example, if we take L to be the candidate elimination algorithm, Dc, to be the training
data as below, and xi to be the first instance from test data as below, then the inductive
inference performed in this case concludes that L(xi, Dc) =(EnjoySport = yes).

29 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Inductive Bias-Advantage
 It provides a nonprocedural means of characterizing their policy for generalizing beyond
the observed data.
 It allows comparison of different learners according to the strength of the inductive bias
they employ.

30 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Modeling Inductive Systems by Equivalent Deductive Systems

The figure below explains Modeling inductive systems by equivalent deductive systems.

 The input-output behavior of the CANDIDATE-ELIMINATION algorithm using a hypothesis

space H is identical to that of a deductive theorem prover utilizing the assertion "H contains
the target concept." This assertion is therefore called the inductive bias of the CANDIDATE-
ELIMINATION algorithm.
 Characterizing inductive systems by their inductive bias allows modelling them by their
equivalent deductive systems. This provides a way to compare inductive systems according
to their policies for generalizing beyond the observed training data. 

31 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Questions on Unit-1
Chapter-1:

Chapter-2:

32 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

33 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Problems on FIND-S
Example-1

34 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

3. Apply the FIND-S algorithm by hand on the given training set. Consider the examples in the specified
order and write down your hypothesis each time after observing an example.

Example -2

Solution:

35 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Example-3

Solutions:

36 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

Problems on Candidate-Elimination Algorithm

1. Consider the Concept and instances given below, identify the hypothesis using
candidate-Elimination learning algorithm.

Solution:

The final version space:< many, ?, no, ?, ?>, <many,?,?,?,?>

37 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

2. Consider the “Japanese Economy Car” Concept and instances given below, identify the
hypothesis using candidate-Elimination learning algorithm.

Solution:

The final version space :<Japan, ?,?,?, Economy>

38 Dept. of CSE(AI&ML), RNSIT

Machine Learning-II Unit -1 BAI702

3. Consider the Concept and instances given below, identify the hypothesis using
candidate-Elimination learning algorithm.

Solution:

The final version space :<small, ?,circle>

39 Dept. of CSE(AI&ML), RNSIT