MACHINE LEARNING UNIT-1 B.

Tech-III-I,ECE
UNIT I: Introduction: Definition of learning systems, Goals and applications of machine
learning, Aspects of developing a learning system: training data, concept representation,
function approximation. Inductive Classification: The concept learning task, Concept
learning as search through a hypothesis space, General-to-specific ordering of hypotheses,
Finding maximally specific hypotheses, Version spaces and the candidate elimination
algorithm, Learning conjunctive concepts, The importance of inductive bias.
Introduction to Machine learning
In the real world, we are surrounded by humans who can learn everything from their
experiences with their learning capability, and we have computers or machines which
work on our instructions. But can a machine also learn from experiences or past data like
a human does, So here comes the role of Machine Learning.
***A machine can learn if it can gain more data to improve its performance.***

Features of Machine learning

• Machine learning is data driven technology. Large amount of data generated by
organizations on daily bases. So, by notable relationships in data, organizations
make better decisions.
• Machine can learn itself from past data and automatically improve.
• From the given dataset it detects various patterns on data.
• For the big organizations branding is important and it will become more easy to
target relatable customer base.
• It is similar to data mining because it is also deals with the huge amount of data.

How does Machine Learning work

1. A machine learning system builds prediction models, learns from previous data, and
predicts the output of new data whenever it receives it.
2. The amount of data helps to build a better model that accurately predicts the
output, which in turn affects the accuracy of the predicted output.
3. Our perspective on the issue has changed as a result of machine learning.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
Applications of Machine learning
1. Image Recognition:(FACEBOOK)

Image recognition is one of the most common applications of machine learning, The
popular use case of image recognition and face detection is, Automatic friend tagging
suggestion.

2. Speech Recognition:(Google assistant, Siri, Cortana, and Alexa)

While using Google, we get an option of "Search by voice," it comes under speech
recognition, and it's a popular application of machine learning.

3. Traffic prediction:( Google Map)

If we want to visit a new place, we take help of Google Maps, which shows us the correct
path with the shortest route and predicts the traffic conditions.

4. Product recommendations: (Amazon, Netflix)

Machine learning is widely used by various e-commerce and entertainment companies.

Google understands the user interest using various machine learning algorithms and
suggests the product as per customer interest.

5. Self-driving cars:( Tesla)

One of the most exciting applications of machine learning is self-driving cars. Machine
learning plays a significant role in self-driving cars.

6. Email Spam and Malware Filtering:

Whenever we receive a new email, it is filtered automatically as important, normal, and

spam. We always receive an important mail in our inbox with the important symbol and
spam emails in our spam box, and the technology behind this is Machine learning.

7. Virtual Personal Assistant:

We have various virtual personal assistants such as Google

assistant, Alexa, Cortana, Siri. As the name suggests, they help us in finding the
information using our voice instruction.

8. Online Fraud Detection:

Machine learning is making our online transaction safe and secure by detecting fraud
transaction. fraudulent transaction can take place such as fake accounts, fake ids,
and steal money in the middle of a transaction.

9. Stock Market trading:

Machine learning is widely used in stock market trading. In the stock market, there is
always a risk of up and downs in shares, so for this machine learning's long short term
memory neural network is used for the prediction of stock market trends.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
10. Medical Diagnosis:

In medical science, machine learning is used for diseases diagnoses. With this, medical
technology is growing very fast and able to build 3D models that can predict the exact
position of lesions in the brain.

11. Automatic Language Translation:

Nowadays, if we visit a new place and we are not aware of the language then it is not a
problem at all, Google's GNMT (Google Neural Machine Translation) provide this feature,
which is a Neural Machine Learning that translates the text into our familiar language,
and it called as automatic translation.

Machine learning Life cycle

Machine learning has given the computer systems the abilities to automatically
learn without being explicitly programmed.
Machine learning life cycle is a cyclic process to build an efficient machine learning
project. The main purpose of the life cycle is to find a solution to the problem or
project.

1. Gathering Data:

Data Gathering is the first step of the machine learning life cycle. The goal of this step is
to identify and obtain all data-related problems. The data can be collected from various
sources such as files, database, internet, or mobile devices. The quantity and quality of
the collected data will determine the efficiency of the output.

This step includes the below tasks:

o Identify various data sources

o Collect data
o Integrate the data obtained from different sources

2. Data preparation

After collecting the data, we need to prepare it for further steps. Data preparation is a step
where we put our data into a suitable place and prepare it to use in our machine learning
training.

This step can be further divided into two processes:

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
Data exploration:
It is used to understand the nature of data that we have to work with. We need to
understand the characteristics, format, and quality of data.
A better understanding of data leads to an effective outcome. In this, we find Correlations,
general trends, and outliers.
Data pre-processing:
Now the next step is preprocessing of data for its analysis.
3. Data Wrangling
Data wrangling is the process of cleaning and converting raw data into a useable format.
It is the process of cleaning the data, selecting the variable to use, and transforming the
data in a proper format to make it more suitable for analysis in the next step.
4. Data Analysis

The cleaned and prepared data is passed on to the analysis step. This step involves:

o Selection of analytical techniques

o Building models
o Review the result

The aim of this step is to build a machine learning model to analyze the data using various
analytical techniques and review the outcome. In real-world applications, collected data
may have various issues, including:

5. Train Model

The next step is to train the model, in this step we train our model to improve its
performance for better outcome of the problem. Training a model is required so that it can
understand the various patterns, rules, and, features.

6. Test Model

Machine learning model has been trained on a given dataset, then we test the model. In
this step, we check for the accuracy of our model by providing a test dataset to it. Testing
the model determines the percentage accuracy of the model as per the requirement of
project or problem.

7. Deployment

The last step of machine learning life cycle is deployment, where we deploy the model in
the real-world system. The above-prepared model is producing an accurate result as per
our requirement with acceptable speed, then we deploy the model in the real system.

o Missing Values
o Duplicate data
o Invalid data
o Noise

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
Design a Learning System:

According to Arthur Samuel “Machine Learning enables a Machine to Automatically

learn from Data, improve performance from an Experience and predict things
without explicitly programmed.” In Simple Words, when we fed the Training Data to
Machine Learning Algorithm, this algorithm will produce a mathematical model and with
the help of the mathematical model, the machine will make a prediction and take a
decision without being explicitly programmed, as shown in above figure . Also, during
training data, the more machine will work with it the more it will get experience and the
more it will get experience the more efficient result is produced.
EXAMPLE: In Driverless Car, the training data is fed to Algorithm like how to Drive Car
in Highway, Busy and Narrow Street with factors like speed limit, parking, stop at signal
etc. After that, a Logical and Mathematical model is created based on that and after that,
the car will work according to the logical model. Also, the more data the data is fed the
more efficient output is produced.
Designing a Learning System in Machine Learning: According to Tom Mitchell, “A
computer program is said to be learning from experience (E), with respect to some task
(T). Thus, the performance measure (P) is the performance at task T, which is measured
by P, and it improves with experience E.”
Example: In Spam E-Mail detection, Task, T: To classify mails into Spam or Not Spam.
Performance measure, P: Total percent of mails being correctly classified as being “Spam”
or “Not Spam”. Experience, E: Set of Mails with label “Spam”
TRAINING VERSUS TESTING
Training data and test data are two important concepts in machine learning.
Training Data: The observations in the training set form the experience that the
algorithm uses to learn. In supervised learning problems, each observation consists of an
observed output variable and one or more observed input variables.
Test Data: The test set is a set of observations used to evaluate the performance of the
model using some performance metric. It is important that no observations from the
training set are included in the test set. If the test set does contain examples from the
training set, it will be difficult to assess whether the algorithm has learned to generalize
from the training set or has simply memorized it.
Steps for Designing Learning System

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

1. Choosing the Training Experience

The type of training experience chosen has a considerable amount of impact on our
algorithm. The training data’s characteristics need to be similar to that of the total
data set’s characteristics. consider these three attributes,

a) Type of Feedback: Check whether the training experience provides direct or

indirect feedback to the algorithm based on the choices of the performance
system.
b) Degree: The degree of a training experience refers to the extent up to which
the learner can control the sequence of training. For example, the learner
might rely on constant feedback about the moves played or it might itself
propose a sequence of actions and only ask for help when in need.
c) The representation of the distribution of samples across which performance
will be tested is the third crucial attribute.

2. Choosing the target function: The next design decision is to figure out
exactly what kind of knowledge will be acquired and how the performance
software will put it to use. Let’s take the classic example of the checkers game
to understand better. The program only needs to learn how to select the best
moves out of the legal moves(Set of all possible moves is called legal moves).

The choice of the target function is a key feature in designing the entire system. The target
function V: B -> R. This notation denotes that V maps any legal board state from set B to
a real value. Assigning value to target function in a checkers game,

1. V(b) = 100 if b is the final board state that is won.

2. V(b) = -100 if b is the final board state that is lost.
3. V(b) = 0 if b is the final board state that is drawn.
4. V(b) = V(b’) if b is not a final state, and b’ is the best final board state that can
be achieved starting from b and playing optimally until the end of the game.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
3. Choosing Representation for Target function: Once done with choosing the
target function now we have to choose a representation of this target function,
When the machine algorithm has a complete list of all permitted movements, it may
pick the best one using any format, such as linear equations, hierarchical graph
representation, tabular form, and so on. Out of these moves, the Next Move
function will move the Target move, which will increase the success rate. For
example, if a chess machine has four alternative moves, the computer will select
the most optimal move that will lead to victory.
4. Choosing a Function Approximation Algorithm: In this step, we choose a
learning algorithm that can approximate the target function chosen. This step
further consists of two sub-steps, a. Estimating the training value, and b. Adjusting
the weights. To estimate a training example, we consider the successor move, and
in the case of adjusting the weights, one uses certain algorithms like LMS, to find
weights of linear functions.
5. The Final Design:

The final design consists of four modules, as described in the picture.

i. The performance system: The performance system solves the given performance
task.
ii. Critic: The critic takes the history of the game and generates training examples.
iii. Generalizer: It outputs the hypothesis that is its estimate of the target function.
iv. Experiment Generator: It creates a new problem after taking in the hypothesis for
the performance system to explore.

Traditional Programming

Traditional programming is a manual process—meaning a person (programmer)

creates the program. But without anyone programming the logic, one has to
manually formulate or code rules.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
Machine Learning Programming

machine learning is an automated process. It can increase the value of your

embedded analytics in many areas, including data prep, natural language interfaces,
automatic outlier detection, recommendations, and causality and significance
detection

Types of Machine Learning

Machine learning is a subset of AI, which enables the machine to automatically learn from
data, improve performance from past experiences, and make predictions.These ML
algorithms help to solve different business problems like Regression, Classification,
Forecasting, Clustering, and Associations, etc.Based on the methods and way of learning,
machine learning is divided into mainly four types, which are:

1. Supervised Machine Learning

2. Unsupervised Machine Learning
3. Reinforcement Learning

1.Supervised Machine Learning

Supervised machine learning is based on supervision. It means in the supervised learning
technique, we train the machines using the "labelled" dataset, and based on the training,
the machine predicts the output. Here, the labelled data specifies that some of the inputs
are already mapped to the output.
Example: Suppose we have an input dataset of cats and dog images. So, first, we will
provide the training to the machine to understand the images, such as the shape & size
of the tail of cat and dog, Shape of eyes, colour, height (dogs are taller, cats are smaller),
etc. The main goal of the supervised learning technique is to map the input variable(x)
with the output variable(y). Some real-world applications of supervised learning are Risk
Assessment, Fraud Detection, Spam filtering, etc.
Categories of Supervised Machine Learning

Supervised machine learning can be classified into two types of problems, which are given
below:

o Classification
o Regression

Classification algorithms are used to solve the classification problems in which the output
variable is categorical, such as "Yes" or No, Male or Female, Red or Blue, etc.
Some popular classification algorithms are given below:

❖ Random Forest Algorithm

❖ Decision Tree Algorithm
❖ Logistic Regression Algorithm
❖ Support Vector Machine Algorithm

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
b) Regression

Regression algorithms are used to solve regression problems in which there is a linear
relationship between input and output variables Some popular Regression algorithms are
given below:

❖ Simple Linear Regression Algorithm

❖ Multivariate Regression Algorithm
❖ Decision Tree Algorithm
❖ Lasso Regression

Advantages and Disadvantages of Supervised Learning

Advantages:

o Since supervised learning work with the labelled dataset so we can have an exact
idea about the classes of objects.
o These algorithms are helpful in predicting the output on the basis of prior
experience.

Disadvantages:

o These algorithms are not able to solve complex tasks.

o It may predict the wrong output if the test data is different from the training data.
o It requires lots of computational time to train the algorithm.

Applications of Supervised Learning

Some common applications of Supervised Learning are given below:

o Image Segmentation: Supervised Learning algorithms are used in image

segmentation. In this process, image classification is performed on different image
data with pre-defined labels.
o Medical Diagnosis: Supervised algorithms are also used in the medical field for
diagnosis purposes. It is done by using medical images and past labelled data with
labels for disease conditions. With such a process, the machine can identify a
disease for the new patients.
o Fraud Detection - Supervised Learning classification algorithms are used for
identifying fraud transactions, fraud customers, etc. It is done by using historic data
to identify the patterns that can lead to possible fraud.
o Spam detection - In spam detection & filtering, classification algorithms are used.
These algorithms classify an email as spam or not spam. The spam emails are sent
to the spam folder.
o Speech Recognition - Supervised learning algorithms are also used in speech
recognition. The algorithm is trained with voice data, and various identifications can
be done using the same, such as voice-activated passwords, voice commands, etc.

2. Unsupervised Machine Learning

Unsupervised learning is different from the Supervised learning technique; there is no

need for supervision. It means, in unsupervised machine learning, the machine is trained

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
using the unlabeled dataset, and the machine predicts the output without any
supervision.

The main aim of the unsupervised learning algorithm is to group or categories the
unsorted dataset according to the similarities, patterns, and differences .

The images are totally unknown to the model, and the task of the machine is to find the
patterns and categories of the objects. So, now the machine will discover its patterns and
differences, such as colour difference, shape difference, and predict the output when it is
tested with the test dataset.

Advantages:

o These algorithms can be used for complicated tasks compared to the supervised
ones because these algorithms work on the unlabeled dataset.
o Unsupervised algorithms are preferable for various tasks as getting the unlabeled
dataset is easier as compared to the labelled dataset.

Disadvantages:

o The output of an unsupervised algorithm can be less accurate as the dataset is not
labelled, and algorithms are not trained with the exact output in prior.
o Working with Unsupervised learning is more difficult as it works with the unlabelled
dataset that does not map with the output.

Applications of Unsupervised Learning

o Network Analysis: Unsupervised learning is used for identifying plagiarism and
copyright in document network analysis of text data for scholarly articles.
o Recommendation Systems: Recommendation systems widely use unsupervised
learning techniques for building recommendation applications for different web
applications and e-commerce websites.
o Anomaly Detection: Anomaly detection is a popular application of unsupervised
learning, which can identify unusual data points within the dataset. It is used to
discover fraudulent transactions.
o Singular Value Decomposition: Singular Value Decomposition or SVD is used to
extract particular information from the database. For example, extracting
information of each user located at a particular location.

Categories of Unsupervised Machine Learning

Unsupervised Learning can be further classified into two types, which are given below:

o Clustering
o Association

1) Clustering: The clustering technique is used when we want to find the inherent groups
from the data. Some of the popular clustering algorithms are given below:

o K-Means Clustering algorithm

o Mean-shift algorithm
o DBSCAN Algorithm
o Principal Component Analysis

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
o Independent Component Analysis

4. Reinforcement Learning

Reinforcement learning works on a feedback-based process, in which an AI agent (A

software component) automatically explore its surrounding by hitting & trail, taking
action, learning from experiences, and improving its performance.

Advantages and Disadvantages of Reinforcement Learning

Advantages

o It helps in solving complex real-world problems which are difficult to be solved by

general techniques.
o The learning model of RL is similar to the learning of human beings; hence most
accurate results can be found.
o Helps in achieving long term results.

Disadvantage

o RL algorithms are not preferred for simple problems.

o RL algorithms require huge data and computations.
o Too much reinforcement learning can lead to an overload of states which can
weaken the results.

Concept Learning
“A task of acquiring potential hypothesis (solution) that best fits the given training
examples.”

Consider the example task of learning the target concept “days on which my friend
Prabhas enjoys his favorite water sport. ”Below Table describes a set of example days,
each represented by a set of attributes. The attribute Enjoy Sport indicates whether or
not Prabhas enjoys his favorite water sport on this day. The task is to learn to predict the
value of Enjoy Sport for an arbitrary day, based on the values of its other attributes.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

Concept Learning Task Example

Concept Learning Task Notation

Let us begin by considering a simple representation in which each hypothesis consists of

a conjunction of constraints on the instance attributes. each hypothesis be a vector of six
constraints, specifying the values of the six attributes Sky, AirTemp, Humidity, Wind,
Water, and Forecast. For each attribute, the hypothesis will either

• indicate by a “?’ that any value is acceptable for this attribute.

• specify a single required value (e.g., Warm) for the attribute.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
• 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).the hypothesis that Prabhas enjoys his favorite sport only on
cold days with high humidity (independent of the values of the other attributes) is
represented by the expression

(?, Cold, High, ?, ?, ?)

Most General and Specific Hypothesis

The most general hypothesis-that every day is a positive example-is represented by

(?, ?, ?, ?, ?, ?)
and the most specific possible hypothesis-that no day is a positive example-is represented
by(ø, ø, ø, ø, ø, ø)

A CONCEPT LEARNINGTASK – Search:

Concept learning can be viewed as the task of searching through a large space of
hypotheses implicitly defined by the hypothesis representation.
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.
Instance Space
Consider, for example, the instances X and hypotheses H in the Enjoy Sport learning task.
Given that the attribute Sky has three possible values, and that Air Temp, Humidity, Wind,
Water, and Forecast each have two possible values, the instance space X contains exactly
3 *2 *2 *2* 2 *2 = 96 distinct instances.
Example:
Let’s assume there are two features F1 and F2 with F1 has A and B as possibilities and
F2 as X and Y as possibilities. F1 – > (A, B )F2 – > (X, Y)

Instance Space: (A, X), (A, Y), (B, X), (B, Y) – 4 Examples

Hypothesis Space: (A, X), (A, Y), (A, ø), (A, ?), (B, X), (B, Y), (B, ø), (B, ?), (ø, X), (ø, Y),
(ø, ø), (ø, ?), (?, X), (?, Y), (?, ø), (?, ?) – 16

Hypothesis Space: (A, X), (A, Y), (A, ?), (B, X), (B, Y), (B, ?), (?, X), (?, Y (?, ?) – 10

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

Hypothesis Space

Similarly add two new attributes ?, ø. There are 5 *4 *4 *4 *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.
Therefore, the number of semantically distinct hypotheses is only 1 + (4 *3 *3 *3 *3
*3) = 973.

General-to-Specific Ordering of Hypotheses

the general-to-specific ordering, consider the two hypotheses

h1 = (Sunny, ?, ?, Strong, ?, ?) ;h2 = (Sunny, ?, ?, ?, ?, ?)

• consider the sets of instances that are classified positive by h1 and by h2. Because
h2 imposes fewer constraints on the instance, it classifies more instances as
positive.

• Any instance classified positive by h1 will also be classified positive by h2. Therefore,
h2 is more general than h1.

• For any instance x in X and hypothesis h in H, we say that x satisfies h if and only
if h(x) = 1.the more general than or equal to relation in terms of the sets of
instances that satisfy the two hypotheses.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

Finding maximally specific hypotheses

The S algorithm, also known as the Find-S algorithm, is a machine learning algorithm
that seeks to find a maximally specific hypothesis based on labeled training data. It starts
with the most specific hypothesis and generalizes it by incorporating positive examples.

Steps for Find-S Algorithm Machine Learning

Step1. Initialize h to the most specific hypothesis in H

step2. For each positive training instance x, For each attribute constraint ai in h
If (the contraint ai is satisfied by x)
then do nothing
else
replace ai in h by the next more general constraint that is satisfied by x
step3. Output the hypothesis h

Numerical example:

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

Step 2 of Find-S Algorithm First iteration

h0 = (ø, ø, ø, ø, ø, ø, ø)

X1 = <Sunny, Warm, Normal, Strong, Warm, Same>

h1 = <Sunny, Warm, Normal, Strong, Warm, Same>

Step 2 of Find-S Algorithm Second iteration

h1 = <Sunny, Warm, Normal, Strong, Warm, Same>

X2 = <Sunny, Warm, High, Strong, Warm, Same>

h2 = <Sunny, Warm, ?, Strong, Warm, Same>

Step 2 of Find-S Algorithm Third iteration

h2 = <Sunny, Warm, ?, Strong, Warm, Same>

X3 = <Rainy, Cold, High, Strong, Warm, Change> – No

X3 is Negative example Hence ignored

h3 = <Sunny, Warm, ?, Strong, Warm, Same>

Step 2 of Find-S Algorithm Fourth iteration

h3 = <Sunny, Warm, ?, Strong, Warm, Same>

X4 = <Sunny, Warm, High, Strong, Cool, Change>

h4 = <Sunny, Warm, ?, Strong, ?, ?>

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
Step 3

The final maximally specific hypothesis is <Sunny, Warm, ?, Strong, ?, ?>

Candidate Elimination Algorithm in Machine Learning

❖ FIND-S outputs a hypothesis from H, that is consistent with the training examples,
this is just one of many hypotheses from H that might fit the training data equally
well.
❖ The key idea in the Candidate-Elimination algorithm is to output a description of
the set of all hypotheses consistent with the training examples.
❖ Candidate-Elimination algorithm computes the description of this set without
explicitly enumerating all of its members.
❖ This is accomplished by using the more-general-than partial ordering and
maintaining a compact representation of the set of consistent hypotheses.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
Step1: Initialize G to the set of maximally general hypotheses in H
Initialize S to the set of maximally specific hypotheses in H
Step2:For each training example d, do:

If (d is positive example)

->Remove from G any hypothesis h inconsistent with d

For each hypothesis s in S not consistent with d:

Remove s from S

->Add to S all minimal generalizations of s consistent with d and having a

generalization in G

--Remove from S any hypothesis with a more specific h in S

If (d is negative example)

-> Remove from S any hypothesis h inconsistent with d

For each hypothesis g in G not consistent with d:

-> Remove g from G

Add to G all minimal specializations of g consistent with d and having a

specialization in S

--Remove from G any hypothesis having a more general hypothesis in G

Example Size Color Shape Class/Label

1 Big Red Circle No
2 Small Red Triangle No
3 Small Red Circle Yes
4 Big Blue Circle No
5 Small Blue Circle Yes

Sol:
Step1: S0: (0, 0, 0) Most Specific Boundary
G0: (?, ?, ?) Most Generic Boundary
Iteration1:The first example is negative, the hypothesis at the specific boundary is
consistent, hence we retain it, and the hypothesis at the generic boundary is inconsistent
hence we write all consistent hypotheses by removing one “?” at a time.

S1: (0, 0, 0)

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
G1: (Small, ?, ?), (?, Blue, ?), (?, ?, Triangle)

Iteration2:The second example is negative, the hypothesis at the specific boundary is

consistent, hence we retain it, and the hypothesis at the generic boundary is inconsistent
hence we write all consistent hypotheses by removing one “?” at a time.

S2: (0, 0, 0)

G2: (Small, Blue, ?), (Small, ?, Circle), (?, Blue, ?), (Big, ?, Triangle), (?, Blue, Triangle)

Iteration3:The third example is positive, the hypothesis at the specific boundary is

inconsistent, hence we extend the specific boundary, and the consistent hypothesis at the
generic boundary is retained and inconsistent hypotheses are removed from the generic
boundary.

S3: (Small, Red, Circle)

G3: (Small, ?, Circle)

Iteration4:The fourth example is negative, the hypothesis at the specific boundary is

consistent, hence we retain it, and the hypothesis at the generic boundary is inconsistent
hence we write all consistent hypotheses by removing one “?” at a time.

S4: (Small, Red, Circle)

G4: (Small, ?, Circle)

Iteration5:The fifth example is positive, the hypothesis at the specific boundary is

inconsistent, hence we extend the specific boundary, and the consistent hypothesis at the
generic boundary is retained and inconsistent hypotheses are removed from the generic
boundary.

S5: (Small, ?, Circle)

G5: (Small, ?, Circle)

Learned Version Space by Candidate Elimination Algorithm for given data set is:
S: G: (Small, ?, Circle)

Consistent Hypothesis

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

The key difference between this definition 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.
• However, whether such an example is consistent with h depends on the target concept,
and in particular, whether h(x) = c(x).
Version Spaces •
The Candidate-Elimination algorithm represents the set of all hypotheses consistent with
the observed training examples. • This subset of all hypotheses is called the version space
with respect to the hypothesis space H and the training examples D, because it contains
all plausible versions of the target concept.

Learning the concept of "Japanese Economy Car"

Features: ( Country of Origin, Manufacturer, Color, Decade, Type )

Example
Origin Manufacturer Color Decade Type
Type
Japan Honda Blue 1980 Economy Positive
Japan Toyota Green 1970 Sports Negative
Japan Toyota Blue 1990 Economy Positive
USA Chrysler Red 1980 Economy Negative
Japan Honda White 1980 Economy Positive
Solution:

1. Positive Example: (Japan, Honda, Blue, 1980, Economy)

Initialize G to a singleton set that

includes everything. G = { (?, ?, ?, ?, ?) }
Initialize S to a singleton set that S = { (Japan, Honda, Blue, 1980, Economy) }
includes the first positive example.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

These models represent the most general and the most specific heuristics one might learn.
The actual heuristic to be learned, "Japanese Economy Car", probably lies between them
somewhere within the version space.

2. Negative Example: (Japan, Toyota, Green, 1970, Sports)

Specialize G to exclude the negative example.

{ (?, Honda, ?, ?, ?),

(?, ?, Blue, ?, ?),
G=
(?, ?, ?, 1980, ?),
(?, ?, ?, ?, Economy) }
{ (Japan, Honda, Blue, 1980,
S=
Economy) }

Refinement occurs by generalizing S or specializing G, until the heuristic hopefully

converges to one that works well.

3. Positive Example: (Japan, Toyota, Blue, 1990, Economy)

Prune G to exclude descriptions inconsistent with the positive example.

Generalize S to include the positive example.

{ (?, ?, Blue, ?, ?),

G=
(?, ?, ?, ?, Economy) }
S= { (Japan, ?, Blue, ?, Economy) }

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE
4. Negative Example: (USA, Chrysler, Red, 1980, Economy)

Specialize G to exclude the negative example (but stay consistent with S)

{ (?, ?, Blue, ?, ?),

G=
(Japan, ?, ?, ?, Economy) }
S= { (Japan, ?, Blue, ?, Economy) }

5. Positive Example: (Japan, Honda, White, 1980, Economy)

Prune G to exclude descriptions inconsistent with positive example.

Generalize S to include positive example.

G = { (Japan, ?, ?, ?, Economy) }
S = { (Japan, ?, ?, ?, Economy) }

G and S are singleton sets and S = G.

Converged.No more data, so algorithm stops.

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

List-Then-Eliminate algorithm

Steps in List-Then-Eliminate Algorithm

step1. VersionSpace = a list containing every hypothesis in H

step2. For each training example, <a(x), c(x)> Remove from VersionSpace any
hypothesis h for which h(x) != c(x)
step3. Output the list of hypotheses in VersionSpace.

Example:

F1 – > (A, B);F2 – > (X, Y). Here F1 and F2 are two features (attributes) with two possible
values for each feature or attribute.

Instance Space: (A, X), (A, Y), (B, X), (B, Y) – 4 Examples
Hypothesis Space: (A, X), (A, Y), (A, ø), (A, ?), (B, X), (B, Y), (B, ø), (B, ?), (ø, X), (ø, Y),
(ø, ø), (ø, ?), (?, X), (?, Y), (?, ø), (?, ?) – 16 Hypothesis
Semantically Distinct Hypothesis : (A, X), (A, Y), (A, ?), (B, X), (B, Y), (B, ?), (?, X), (?, Y
(?, ?), (ø, ø) – 10
List-Then-Eliminate Algorithm Steps
Version Space: (A, X), (A, Y), (A, ?), (B, X), (B, Y), (B, ?), (?, X), (?, Y) (?, ?), (ø, ø),

Dept.of ECE SREC

MACHINE LEARNING UNIT-1 B.Tech-III-I,ECE

•Training Instances

F1 F2 Target

A X yes

A Y Yes

Consistent Hypothesis are (Version Space): (A, ?), (?, ?)

Problems with List-Then-Eliminate Algorithm

❖ The hypothesis space must be finite

❖ Enumeration of all the hypothesis, rather inefficient.

Inductive bias: a collection of (explicit or implicit) assumptions made by a learning

algorithm in order to conduct induction, or generalize a limited set of observations
(training data) into a general model of the domain.

Biased Hypothesis Space:

It does not include all types of training instances. The issue is that we have skewed
the learner’s thinking to only evaluate conjunctive possibilities. In this instance, a
more expressive hypothesis space is required.

Inductive Learning:
This basically means learning from examples, learning on the go. Consider input
samples (x) and output samples (f(x)) in the context of inductive learning, and the
objective is to estimate the function (f). The goal is to generalize from the samples
and map such that the output may be estimated for fresh samples in the future.
Deductive Learning:
Learners are initially exposed to concepts and generalizations, followed by particular
examples and exercises to aid learning.Already existing rules are applied to the
training examples.

Dept.of ECE SREC