Department of CSE MRCET

MODULE 1

UNIT-I

Machine Learning
is the field of study that gives computers the capability to learn without
being explicitly programmed. ML isTextone of the most exciting technologies
that one would have ever come across. As it is evident from the name, it
gives the computer that makes it more similar to humans: The ability to
learn. Machine learning is actively being used today, perhaps in many more
places than one would expect.

Machine Learning is broadly categorized under the following headings:

Machine learning evolved from left to right as shown in the above diagram.
• Initially, researchers started out with Supervised Learning. This is the
case of housing price prediction discussed earlier

. • This was followed by unsupervised learning, where the machine is made

to learn on its own without any supervision.
• Scientists discovered further that it may be a good idea to reward the
machine when it does the job the expected way and there came the
Reinforcement Learning.
• Very soon, the data that is available these days has become so humongous
that the conventional techniques developed so far failed to analyse the big
data and provide us the predictions.

1
Department of CSE MRCET

• Thus, came the deep learning where the human brain is simulated in the
Artificial Neural Networks (ANN) created in our binary computers.
• The machine now learns on its own using the high computing power and
huge memory resources that are available today.
• It is now observed that Deep Learning has solved many of the previously
unsolvable problems.
• The technique is now further advanced by giving incentives to Deep
Learning networks as awards and there finally comes Deep Reinforcement
Learning.
Let us now study each of these categories in more details

Supervised Learning:
Supervised learning is analogous to training a child to walk. You will hold
the child’s hand, show him how to take his foot forward, walk yourself for a
demonstration and so on, until the child learns to walk on his own.

Regression:
Similarly, in the case of supervised learning, you give concrete known
examples to the computer. You say that for given feature value x1 the output
is y1, for x2 it is y2, for x3 it is y3, and so on. Based on this data, you let the
computer figure out an empirical relationship between x and y. Once the
machine is trained in this way with a sufficient number of data points, now
you would ask the machine to predict Y for a given X. Assuming that you
know the real value of Y for this given X, you will be able to deduce whether
the machine’s prediction is correct. Thus, you will test whether the machine
has learned by using the known test data. Once you are satisfied that the
machine is able to do the predictions with a desired level of accuracy (say 80
to 90%) you can stop further training the machine. Now, you can safely use
the machine to do the predictions on unknown data points, or ask the
machine to predict Y for a given X for which you do not know the real value
of Y. This training comes under the regression that we talked about earlier.

2
Department of CSE MRCET

Classification:
You may also use machine learning techniques for classification problems. In
classification problems, you classify objects of similar nature into a single
group. For example, in a set of 100 students say, you may like to group them
into three groups based on their heights - short, medium and long. Measuring
the height of each student, you will place them in a proper group. Now, when
a new student comes in, you will put him in an appropriate group by
measuring his height. By following the principles in regression training, you
will train the machine to classify a student based on his feature – the height.
When the machine learns how the groups are formed, it will be able to
classify any unknown new student correctly. Once again, you would use the
test data to verify that the machine has learned your technique of
classification before putting the developed model in production. Supervised
Learning is where the AI really began its journey. This technique was
applied successfully in several cases. You have used this model while doing
the hand-written recognition on your machine. Several algorithms have been
developed for supervised learning. You will learn about them in the
following chapters.

Unsupervised Learning:
In unsupervised learning, we do not specify a target variable to the machine,
rather we ask machine “What can you tell me about X?”. More specifically,
we may ask questions such as given a huge data set X, “What are the five
best groups we can make out of X?” or “What features occur together most
frequently in X?”. To arrive at the answers to such questions, you can
understand that the number of data points that the machine would require to
deduce a strategy would be very large. In case of supervised learning, the
machine can be trained with even about few thousands of data points.
However, in case of unsupervised learning, the number of data points that is
reasonably accepted for learning starts in a few millions. These days, the data
is generally abundantly available. The data ideally requires curating.
However, the amount of data that is continuously flowing in a social area
network, in most cases data curation is an impossible task. The following
figure shows the boundary between the yellow and red dots as determined by
unsupervised machine learning. You can see it clearly that the machine

3
Department of CSE MRCET

would be able to determine the class of each of the black dots with a fairly
good accuracy.

Reinforcement Learning:
Consider training a pet dog, we train our pet to bring a ball to us. We throw
the ball at a certain distance and ask the dog to fetch it back to us. Every time
the dog does this right, we reward the dog. Slowly, the dog learns that doing
the job rightly gives him a reward and then the dog starts doing the job right
way every time in future. Exactly, this concept is applied in “Reinforcement”
type of learning. The technique was initially developed for machines to play
games. The machine is given an algorithm to analyse all possible moves at
each stage of the game. The machine may select one of the moves at random.
If the move is right, the machine is rewarded, otherwise it may be penalized.
Slowly, the machine will start differentiating between right and wrong moves
and after several iterations would learn to solve the game puzzle with a better
accuracy. The accuracy of winning the game would improve as the machine
plays more and more games.
The entire process may be depicted in the following diagram:

4
Department of CSE MRCET

Deep Learning:
The deep learning is a model based on Artificial Neural Networks (ANN),
more specifically Convolutional Neural Networks (CNN)s. There are several
architectures used in deep learning such as deep neural networks, deep belief
networks, recurrent neural networks, and convolutional neural networks.
These networks have been successfully applied in solving the problems of
computer vision, speech recognition, natural language processing,
bioinformatics, drug design, medical image analysis, and games. There are
several other fields in which deep learning is proactively applied. The deep
learning requires huge processing power and humongous data, which is
generally easily available these days. We will talk about deep learning more
in detail in the coming chapters.

Deep Reinforcement Learning:

The Deep Reinforcement Learning (DRL) combines the techniques of both
deep and reinforcement learning. The reinforcement learning algorithms like
Q learning are now combined with deep learning to create a powerful DRL
model. The technique has been with a great success in the fields of robotics,
video games, finance and healthcare. Many previously unsolvable problems
are now solved by creating DRL models. There is lots of research going on
in this area and this is very actively pursued by the industries. So far, you
5
Department of CSE MRCET

have got a brief introduction to various machine learning models, now let us
explore slightly deeper into various algorithms that are available under these
models.

Well posed learning problems:

A computer program is said to learn from experience E in context to some

task T and some performance measure P, if its performance on T, as was
measured by P, upgrades with experience E.
Any problem can be segregated as well-posed learning problem if it has three
traits –
• Task
• Performance Measure
• Experience
Certain example that efficiently defines the well-posed learning problems
are:

1. To better filter emails as spam or not

• Task – Classifying emails as spam or not
• Performance Measure – The fraction of emails accurately classified as spam
or not spam
• Experience – Observing you label emails as spam or not spam
2. A checkers learning problem
• Task – Playing checkers game
• Performance Measure – percent of games won against opposer
• Experience – playing implementation games against itself
3. Handwriting Recognition Problem
• Task – Acknowledging handwritten words within portrayal
• Performance Measure – percent of words accurately classified
• Experience – a directory of handwritten words with given classifications
4. A Robot Driving Problem
• Task – driving on public four-lane highways using sight scanners
• Performance Measure – average distance progressed before a fallacy
• Experience – order of images and steering instructions noted down while
observing a human driver
5. Fruit Prediction Problem

6
 Department of CSE MRCET

• Task – forecasting different fruits for recognition

• Performance Measure – able to predict maximum variety of fruits
• Experience – training machine with the largest datasets of fruits images

6. Face Recognition Problem

• Task – predicting different types of faces
• Performance Measure – able to predict maximum types of faces
• Experience – training machine with maximum amount of datasets of
different face images
7. Automatic Translation of documents
• Task – translating one type of language used in a document to other language
• Performance Measure – able to convert one language to other efficiently
• Experience – training machine with a large dataset of different types of
languages

Design of a learning system:

Just now we looked into the learning process and also understood the goal
of the learning. When we want to design a learning system that follows the
learning process, we need to consider a few design choices. The design
choices will be to decide the following key components:
1. Type of training experience
2. Choosing the Target Function
3. Choosing a representation for the Target Function
4. Choosing an approximation algorithm for the Target Function
5. The final Design
We will look into the game - checkers learning problem and apply the above
design choices. For a checkers learning problem, the three elements will be,
• Task T: To play checkers
• Performance measure P: Total present of the game won in the tournament.
• Training experience E: A set of games played against itself.

Type of training experience:

During the design of the checker's learning system, the type of training
experience available for a learning system will have a significant effect on
the success or failure of the learning.
7
Department of CSE MRCET

Direct or Indirect training experience:

In the case of direct training experience, an individual board states and
correct move for each board state are given. In case of indirect training
experience, the move sequences for a game and the final result (win, lose or
draw) are given for a number of games. How to assign credit or blame to
individual moves is the credit assignment problem.

1. Teacher or Not:
Supervised:
The training experience will be labelled, which means, all the board states
will be labelled with the correct move. So the learning takes place in the
presence of a supervisor or a teacher.
Un-Supervised:
The training experience will be unlabelled, which means, all the board
states will not have the moves. So the learner generates random games and
plays against itself with no supervision or teacher involvement.

Semi-supervised:
Learner generates game states and asks the teacher for help in finding
the correct move if the board state is confusing.
2. Is the training experience good:

Do the training examples represent the distribution of examples over

which the final system performance will be measured? Performance is best
when training examples and test examples are from the same/a similar
distribution.
The checker player learns by playing against oneself. Its experience is
indirect. It may not encounter moves that are common in human expert play.
Once the proper training experience is available, the next design step will be
choosing the Target Function.
Choosing the Target Function:
When you are playing the checkers game, at any moment of time, you make
a decision on choosing the best move from different possibilities. You think
and apply the learning that you have gained from the experience. Here the
learning is, for a specific board, you move a checker such that your board

8
Department of CSE MRCET

state tends towards the winning situation. Now the same learning has to be
defined in terms of the target function.
Here there are 2 considerations — direct and indirect experience.
• During the direct experience the checkers learning system, it needs only
to learn how to choose the best move among some large search space. We
need to find a target function that will help us choose the best move among
alternatives.
Let us call this function Choose Move and use the notation Choose Move: B
→M to 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.
• When there is an indirect experience it becomes difficult to learn such
function. How about assigning a real score to the board state.

So the function be V: B →R indicating that this accepts as input any board

from the set of legal board states B and produces an output a real score. This
function assigns the 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 board position.
Let us therefore define the target value V(b) for an arbitrary board state b in
B, as follows:
9
Department of CSE MRCET

1. if b is a final board state that is won, then V(b) = 100

2. if b is a final board state that is lost, then V(b) = -100
3. if b is a final board state that is drawn, then V(b) = 0

4. 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.
The (4) is a recursive definition and to determine the value of V(b) for a
particular board state, it performs the search ahead for the optimal line of
play, all the way to the end of the game. So this definition is not efficiently
computable by our checkers playing program, we say that it is a non-
operational definition.

Choosing a representation for the Target Function:

Now that we have specified the ideal target function V, we must choose a
representation that the learning program will use to describe the function ^V
that it will learn. As with earlier design choices, we again have many options.
We could, for example, allow the program to represent using a large table
with a distinct entry specifying the value for each distinct board state. Or we
could allow it to represent using a collection of rules that match against
features of the board state, or a quadratic polynomial function of predefined
board features, or an artificial neural network. In general, this choice of
representation involves a crucial trade off. On one hand, we wish to pick a
very expressive representation to allow representing as close an
approximation as possible to the ideal target function V.
On the other hand, the more expressive the representation, the more training
data the program will require in order to choose among the alternative
hypotheses it can represent. To keep the discussion brief, let us choose a
simple representation: for any given board state, the function ^V will be
calculated as a linear combination of the following board features:
• x1(b) — number of black pieces on board b
• x2(b) — number of red pieces on b
• x3(b) — number of black kings on b
10
Department of CSE MRCET

• x4(b) — number of red kings on b

• x5(b) — number of red pieces threatened by black • x6(b) — number of
black pieces threatened by red
^V = w0 + w1 · x1(b) + w2 · x2(b) + w3 · x3(b) + w4 · x4(b) +w5 · x5(b) + w6 · x6(b)

Where w0 through w6 are numerical coefficients or weights to be obtained

by a learning algorithm. Weights w1 to w6 will determine the relative
importance of different board features.
Specification of the Machine Learning Problem at this time: Till now we
worked on choosing the type of training experience, choosing the target
function and its representation. The checkers learning task can be
summarized as below.

• Task T: Play Checkers

• Performance Measure: % of games won in world tournament
• Training Experience E: opportunity to play against itself
• Target Function: V: Board → R
• Target Function Representation: ^V = w0 + w1 · x1(b) + w2 · x2(b) + w3 ·
x3(b) + w4 · x4(b) +w5 · x5(b) + w6 · x6(b)
The first three items above correspond to the specification of the learning
task, where as the final two items constitute design choices for the
implementation of the learning program.

Choosing an approximation algorithm for the Target Function:

Generating training data — To train our learning program, we need a set of
training data, each describing a specific board state b and the training value
V_train (b) for b. Each training example is an ordered pair <b,v_train(b)>.

11
Department of CSE MRCET

Temporal difference (TD) learning is a concept central to reinforcement

learning, in which learning happens through the iterative correction of your
estimated returns towards a more accurate target return.
V_train(b) ← ^V(Successor(b))

Final Design for Checkers Learning system:

The final design of our checkers learning system can be naturally described
by four distinct program modules that represent the central components in
many learning systems.
1. The performance System: Takes a new board as input and outputs a trace of
the game it played against itself.
2. The Critic: Takes the trace of a game as an input and outputs a set of training
examples of the target function.
3. The Generalizer: Takes training examples as input and outputs a hypothesis
that estimates the target function. Good generalization to new cases is
crucial.
4. The Experiment Generator: Takes the current hypothesis (currently learned
function) as input and outputs a new problem (an initial board state) for the
performance system to explore.

Issues in Machine Learning:

12
Department of CSE MRCET

Our checkers example raises a number of generic questions about 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?
• 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?

CONCEPT LEARNING:

• Inducing general functions from specific training examples is a main issue of

machine learning.
• Concept Learning: Acquiring the definition of a general category from
given sample positive and negative training examples of the category.
• Concept Learning can see as a problem of searching through a predefined
space of potential hypotheses for the hypothesis that best fits the training
examples.
• The hypothesis space has a general-to-specific ordering of hypotheses, and
the search can be efficiently organized by taking advantage of a naturally
occurring structure over the hypothesis space.
A Formal Definition for Concept Learning:
13
 Department of CSE MRCET

Inferring a Boolean-valued function from training examples of its input and

output.
• An example for concept-learning is the learning of bird-concept from the
given examples of birds (positive examples) and non-birds (negative
examples).

• We are trying to learn the definition of a concept from given examples.

A Concept Learning Task: Enjoy Sport Training Examples

A set of example days, and each is described by six attributes. The task is to
learn to predict the value of Enjoy Sport for arbitrary day, based on the
values of its attribute values.

Concept Learning as 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.
• 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.

14
 Department of CSE MRCET

FIND-S:
• FIND-S Algorithm starts from the most specific hypothesis and generalize it
by considering only positive examples.
• FIND-S algorithm ignores negative example
: As long as the hypothesis space contains a hypothesis that describes the
true target concept, and the training data contains no errors, ignoring
negative examples does not cause to any problem.
• FIND-S algorithm finds the most specific hypothesis within H that is
consistent with the positive training examples. – The final hypothesis will
also be consistent with negative examples if the correct target concept is in
H, and the training examples are correct.
FIND-S Algorithm:
1. Initialize h to the most specific hypothesis in H
2. For each positive training instance x For each attribute
constraint a, in h
If the constraint a, is satisfied by x
Then do nothing
3. Else replace a, in h by the next more general constraint that is satisfied by
x 4. Output hypothesis h
FIND-S Algorithm – Example:
Important-Representation:

1. ? indicates that any value is acceptable for the attribute.

2. specify a single required value (e.g., Cold) for the attribute.
3. Φ indicates that no value is acceptable.
4. The most general hypothesis is represented by: {?, ?, ?, ?, ?, ?}
5. The most specific hypothesis is represented by: {ϕ, ϕ, ϕ, ϕ, ϕ, ϕ}

Steps Involved in Find-S:

1. Start with the most specific hypothesis. h = {ϕ, ϕ, ϕ, ϕ, ϕ, ϕ}

15
Department of CSE MRCET

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 a 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 use to classify the new examples. Example: Consider
the following data set having the data about which particular seeds are
poisonous.

First, we consider the hypothesis to be a more specific hypothesis. Hence,

our hypothesis would be: h = {ϕ, ϕ, ϕ, ϕ, ϕ, ϕ}

Consider example 1:
The data in example 1 is {GREEN, HARD, NO, WRINKLED}. We see that
our initial hypothesis is more specific and we have to generalize it for this
example.
Hence, the hypothesis becomes:
h = {GREEN, HARD, NO, WRINKLED}
Consider example 2:
16
Department of CSE MRCET

Here we see that this example has a negative outcome. Hence we neglect
this example and our hypothesis remains the same. h = {GREEN,
HARD, NO, WRINKLED}
Consider example 3:
Here we see that this example has a negative outcome. hence we neglect
this example and our hypothesis remains the same. h = {GREEN,
HARD, NO, WRINKLED}
Consider example 4:
The data present in example 4 is {ORANGE, HARD, NO, WRINKLED}.
We
compare every single attribute with the initial data and if any mismatch is
found we replace that particular attribute with a general case (“ ?”). After
doing the process the hypothesis becomes: h = {?, HARD, NO,
WRINKLED }
Consider example 5:
The data present in example 5 is {GREEN, SOFT, YES, SMOOTH}. We
compare every single attribute with the initial data and if any mismatch is
found we replace that particular attribute with a general case ( “?” ). After
doing the process the hypothesis becomes:
h = {?, ?, ?, ? }
Since we have reached a point where all the attributes in our hypothesis
have the general condition, example 6 and example 7 would result in the
same hypothesizes with all general attributes. h = {?, ?, ?, ? }
Hence, for the given data the final hypothesis would be:
Final Hypothesis: h = { ?, ?, ?, ? }.

Version Spaces
Definition(Version space). A concept is complete if it covers all positive
examples.
A concept is consistent if it covers none of the negative examples. The
version space is the set of all complete and consistent concepts. This set is
convex and is fully defined by its least and most general elements.

Candidate-Elimination Learning Algorithm

17
 Department of CSE MRCET

The CANDIDATE-ELIMINTION algorithm computes the version space

containing all hypotheses from H that are consistent with an observed
sequence of training examples.
Initialize G to the set of maximally general hypotheses in H Initialize S to
the set of maximally specific hypotheses in H For each training example d,
do

• If d is a positive example
• Remove from G any hypothesis inconsistent with d
• For each hypothesis s in S that is not consistent with d
• Remove s from S • Add to S all minimal generalizations h of s such that h is
consistent with d, and some member of G is more general than h
• Remove from S any hypothesis that is more general than another hypothesis
in S
• If d is a negative example
• Remove from S any hypothesis inconsistent with d
• For each hypothesis g in G that is not consistent with d
• Remove g from G 18\
• Add to G all minimal specializations h of g such that
• h is consistent with d, and some member of S is more specific than h
• Remove from G any hypothesis that is less general than another hypothesis
in G.
CANDIDATE- ELIMINTION algorithm using version spaces An
Illustrative Example:

18
 Department of CSE MRCET

CANDIDATE-ELIMINTION algorithm begins by initializing the version

space to the set of all hypotheses in H;
boundary set to contain the most general hypothesis in H, G0 ?, ?, ?, ?, ?,
When the first training example is presented, the
CANDIDATEELIMINTION 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.
• 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

19
 Department of CSE MRCET

• Consider the third training example. This negative example reveals that the
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.

Given that there are six attributes that could be specified to specialize G2,
why are there only three new hypotheses in G3?

For example, the hypothesis h = (?, ?, Normal, ?, ?, ?) is a minimal

specialization of G2 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.

20
 Department of CSE MRCET

• 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 S4 and G4 delimit the version space of all
hypotheses consistent with the set of incrementally observed training
examples.
• After processing these four examples, the boundary sets S4 and G4 delimit
the version space of all hypotheses consistent with the set of incrementally
observed training examples.

Inductive bias:

21