R2017

CP4252 MACHINE LEARNING L T P C 3 0 2

4

UNIT I INTRODUCTION AND MATHEMATICAL FOUNDATIONS 9

What is Machine Learning? Need –History – Definitions – Applications - Advantages, Disadvantages &
Challenges -Types of Machine Learning Problems – Mathematical Foundations - Linear Algebra &
Analytical Geometry -Probability and Statistics- Bayesian Conditional Probability -Vector Calculus &
Optimization - Decision Theory - Information theory

UNIT II SUPERVISED LEARNING 9 Introduction-Discriminative and Generative Models -Linear

Regression - Least Squares -Under-fitting / Overfitting -Cross-Validation – Lasso Regression- Classification
- Logistic Regression- Gradient Linear Models -Support Vector Machines –Kernel Methods -Instance based
Methods - K-Nearest Neighbors - Tree based Methods –Decision Trees –ID3 – CART - Ensemble Methods
–Random Forest - Evaluation of Classification Algorithms

UNIT III UNSUPERVISED LEARNING AND REINFORCEMENT LEARNING 9 Introduction -

Clustering Algorithms -K – Means – Hierarchical Clustering - Cluster Validity -Dimensionality Reduction
–Principal Component Analysis – Recommendation Systems - EM algorithm. Reinforcement Learning –
Elements -Model based Learning – Temporal Difference Learning

UNIT IV PROBABILISTIC METHODS FOR LEARNING 9 Introduction -Naïve Bayes Algorithm

-Maximum Likelihood -Maximum Apriori -Bayesian Belief Networks -Probabilistic Modelling of Problems
-Inference in Bayesian Belief Networks – Probability Density Estimation - Sequence Models – Markov
Models – Hidden Markov Models

UNIT V NEURAL NETWORKS AND DEEP LEARNING 9 Neural Networks – Biological Motivation-
Perceptron – Multi-layer Perceptron – Feed Forward Network – Back Propagation-Activation and Loss
Functions- Limitations of Machine Learning – Deep Learning– Convolution Neural Networks – Recurrent
Neural Networks – Use cases
CP4252 MACHINE LEARNING
UNIT I INTRODUCTION AND MATHEMATICAL FOUNDATIONS
What is Machine Learning? Need –History – Definitions – Applications - Advantages, Disadvantages
& Challenges -Types of Machine Learning Problems – Mathematical Foundations - Linear Algebra &
Analytical Geometry -Probability and Statistics- Bayesian Conditional Probability -Vector Calculus &
Optimization - Decision Theory - Information theory

What is Machine Learning?

UNIT-I Page 1 of 40
 UNIT-I
Page 2 of 40
History of Machine Learning

As a scientific endeavour, machine learning grew out of the quest for artificial intelligence. Already in
the early days of AI as an academic discipline, some re-searchers were interested in having machines
learn from data. They attempted to approach the problem with vari-ous symbolic methods, as well as
what were then termed "neural networks"; these were mostly perceptrons and other models that were
later found to be reinventions of the generalized linear models of statistics. Probabilistic reasoning was
also employed, especially in automated medical diagnosis.[10]:488

However, an increasing emphasis on the logical, knowledge-based approach caused a rift between AI
and machine learning. Probabilistic systems were plagued by theoretical and practical problems of
data acquisition and representation.[10]:488 By 1980, expert systems had come to dominate AI, and
statistics was out of favor.[11] Work on symbolic/knowledge-based learning did con-tinue within AI,
leading to inductive logic programming, but the more statistical line of research was now out-side the
field of AI proper, in pattern recognition and information retrieval.[10]:708–710; 755 Neural
networks re-search had been abandoned by AI and computer science around the same time. This line,
too, was continued out-side the AI/CS field, as "connectionism", by researchers from other
disciplines including Hopfield, Rumelhart and Hinton. Their main success came in the mid-1980s
with the reinvention of backpropagation.[10]:25

Machine learning, reorganized as a separate field, started to flourish in the 1990s. The field changed
its goal from achieving artificial intelligence to tackling solvable prob-lems of a practical nature. It
shifted focus away from the symbolic approaches it had inherited from AI, and toward methods and
models borrowed from statistics and probability theory.[11] It also benefited from the increas-ing
availability of digitized information, and the possibil-ity to distribute that via the internet.

Machine learning and data mining often employ the same methods and overlap significantly. They can
be roughly distinguished as follows:
• Machine learning focuses on prediction, based on known properties learned from the training
data.
• Data mining focuses on the discovery of (previously) unknown properties in the data. This is the
analysis step of Knowledge Discovery in Databases.

The two areas overlap in many ways: data mining uses many machine learning methods, but often
with a slightly different goal in mind. On the other hand, machine learning also employs data mining
methods as “unsupervised learning” or as a pre-processing step to improve learner accuracy. Much of
the confusion between these two research communities (which do often have sepa-rate conferences
and separate journals, ECML PKDD being a major exception) comes from the basic assump-tions
they work with: in machine learning, performance is usually evaluated with respect to the ability to
re-produce known knowledge, while in Knowledge Discov-ery and Data Mining (KDD) the key task
is the discov ery of previously unknown knowledge. Evaluated with respect to known knowledge, an
uninformed (unsuper-vised) method will easily be outperformed by supervised methods, while in a
typical KDD task, supervised meth-ods cannot be used due to the unavailability of training data.

Machine learning also has intimate ties to optimization: many learning problems are formulated as
minimization of some loss function on a training set of examples. Loss functions express the
discrepancy between the predic-tions of the model being trained and the actual prob-lem instances (for
example, in classification, one wants to assign a label to instances, and models are trained to correctly
predict the pre-assigned labels of a set ex-amples). The difference between the two fields arises from
the goal of generalization: while optimization algo-rithms can minimize the loss on a training set,
machine learning is concerned with minimizing the loss on unseen samples.[12]

UNIT-I Page 3 of 40
Advantages, Disadvantages & Challenges

Every coin has two faces, each face has its own property and features. It’s time to uncover the
faces of ML. A very powerful tool that holds the potential to revolutionize the way things work.

Advantages of Machine learning

1. Easily identifies trends and patterns
Machine Learning can review large volumes of data and discover specific trends and patterns
that would not be apparent to humans. For instance, for an e-commerce website like Amazon, it serves
to understand the browsing behaviors and purchase histories of its users to help cater to the right
products, deals, and reminders relevant to them. It uses the results to reveal relevant advertisements to
them.
2. No human intervention needed (automation)
With ML, you don’t need to babysit your project every step of the way. Since it means giving
machines the ability to learn, it lets them make predictions and also improve the algorithms on their
own. A common example of this is anti-virus softwares; they learn to filter new threats as they are
recognized. ML is also good at recognizing spam.
3. Continuous Improvement
As ML algorithms gain experience, they keep improving in accuracy and efficiency. This lets
them make better decisions. Say you need to make a weather forecast model. As the amount of data
you have keeps growing, your algorithms learn to make more accurate predictions faster. 4. Handling
multi-dimensional and multi-variety data
Machine Learning algorithms are good at handling data that are multi-dimensional and multi
variety, and they can do this in dynamic or uncertain environments.
5. Wide Applications
You could be an e-tailer or a healthcare provider and make ML work for you. Where it does
apply, it holds the capability to help deliver a much more personal experience to customers while also
targeting the right customers.

Disadvantages of Machine Learning

With all those advantages to its powerfulness and popularity, Machine Learning isn’t perfect. The
following factors serve to limit it:
1. Data Acquisition
Machine Learning requires massive data sets to train on, and these should be
inclusive/unbiased, and of good quality. There can also be times where they must wait for new data to
be generated.
2. Time and Resources
ML needs enough time to let the algorithms learn and develop enough to fulfill their purpose
with a considerable amount of accuracy and relevancy. It also needs massive resources to function.
This can mean additional requirements of computer power for you.
3. Interpretation of Results
Another major challenge is the ability to accurately interpret results generated by the
algorithms. You must also carefully choose the algorithms for your purpose.
4. High error-susceptibility
 UNIT-I Page 4 of 40
Machine Learning is autonomous but highly susceptible to errors. Suppose you train an
algorithm with data sets small enough to not be inclusive. You end up with biased predictions coming
from a biased training set. This leads to irrelevant advertisements being displayed to customers. In the
case of ML, such blunders can set off a chain of errors that can go undetected for long periods of time.
And when they do get noticed, it takes quite some time to recognize the source of the issue, and even
longer to correct it.

Challenges
1. Not enough training data :
Let’s say for a child, to make him learn what an apple is, all it takes for you to point to an apple and
say apple repeatedly. Now the child can recognize all sorts of apples.
Well, machine learning is still not up to that level yet; it takes a lot of data for most of the algorithms
to function properly. For a simple task, it needs thousands of examples to make something out of it,
and for advanced tasks like image or speech recognition, it may need lakhs(millions) of examples.

2. Poor Quality of data:

Obviously, if your training data has lots of errors, outliers, and noise, it will make it impossible for
your machine learning model to detect a proper underlying pattern. Hence, it will not perform well.
So put in every ounce of effort in cleaning up your training data. No matter how good you are in
selecting and hyper tuning the model, this part plays a major role in helping us make an accurate
machine learning model.
“Most Data Scientists spend a significant part of their time in cleaning data”.
There are a couple of examples when you’d want to clean up the data :
• If you see some of the instances are clear outliers just discard them or fix them manually. • If
some of the instances are missing a feature like (E.g., 2% of user did not specify their age), you
can either ignore these instances, or fill the missing values by median age, or train one model
with the feature and train one without it to come up with a conclusion.
3. Irrelevant Features:
“Garbage in, garbage out (GIGO).”
“Garbage in, garbage out (GIGO).”

Image Source
In the above image, we can see that even if our model is “AWESOME” and we feed it with garbage
data, the result will also be garbage(output). Our training data must always contain more relevant
and less to none irrelevant features.
The credit for a successful machine learning project goes to coming up with a good set of features on
which it has been trained (often referred to as feature engineering ), which includes feature selection,
extraction, and creating new features which are other interesting topics to be covered in upcoming
blogs.

4. Nonrepresentative training data:

To make sure that our model generalizes well, we have to make sure that our training data should be
representative of the new cases that we want to generalize to.
If train our model by using a nonrepresentative training set, it won’t be accurate in predictions it will
be biased against one class or a group.
For E.G., Let us say you are trying to build a model that recognizes the genre of music. One way to
build your training set is to search it on youtube and use the resulting data. Here we assume that
youtube’s search engine is providing representative data but in reality, the search will be biased
towards popular artists and maybe even the artists that are popular in your location(if you live in India
you will be getting the music of Arijit Singh, Sonu Nigam or etc).
So use representative data during training, so your model won’t be biased among one or two classes
when it works on testing data.

UNIT-I Page 5 of 40
5. Overfitting and Underfitting:
What is overfitting?
Let’s start with an example, say one day you are walking down a street to buy something, a dog comes
out of nowhere you offer him something to eat but instead of eating he starts barking and chasing you
but somehow you are safe. After this particular incident, you might think all dogs are not worth
treating nicely.
So this overgeneralization is what we humans do most of the time, and unfortunately machine
learning model also does the same if not paid attention. In machine learning, we call this overfitting
i.e model performs well on training data but fails to generalize well.
Overfitting happens when our model is too complex.
Things which we can do to overcome this problem:
1. Simplify the model by selecting one with fewer parameters.
2. By reducing the number of attributes in training data.
3. Constraining the model.
4. Gather more training data.
5. Reduce the noise.
What is underfitting?
Yes, you guessed it right underfitting is the opposite of overfitting. It happens when our model is too
simple to learn something from the data. For E.G., you use a linear model on a set with
multi-collinearity it will for sure underfit, and the predictions are bound to be inaccurate on the
training set too. Things which we can do to overcome this problem:
1. Select a more advanced model, one with more parameters.
2. Train on better and relevant features.
3. Reduce the constraints.

Types of Machine Learning Problems

 UNIT-I Page 6 of 40

Mathematical Foundations - Linear Algebra

UNIT-I Page 7 of 40
UNIT-I Page 8 of 40
UNIT-I Page 9 of 40

UNIT-I
Page 10 of 40
UNIT-I Page 11 of 40
 Analytic geometry is a study in which we learn the data (point) position using an
ordered pair of coordinates. This study is concerned with defining and representing
geometrical shapes numerically and extracting numerical information from the shapes
numerical definitions and representations. We project the data into the plane in a simpler
term, and we receive numerical information from there.

Cartesian Coordinate (Image by Author)

Above is an example of how we acquired information from the data point by projecting the
dataset into the plane. How we acquire the information from this representation is the heart
of Analytical Geometry. To help you start learning this subject, here are some important
terms you might need.

• Distance Function
A distance function is a function that provides numerical information for the distance
between the elements of a set. If the distance is zero, then elements are equivalent. Else, they
are different from each other.
An example of the distance function is Euclidean Distance which calculates the linear
distance between two data points.

Euclidean Distance Equation (Image by Author)

• Inner Product
The inner product is a concept that introduces intuitive geometrical concepts, such as the
length of a vector and the angle or distance between two vectors. It is often denoted
as ⟨x,y⟩ (or occasionally (x,y) or ⟨x|y⟩).
UNIT-I Page 12 of 40
UNIT-I Page 13 of 40
UNIT-I Page 14 of 40
UNIT-I Page 15 of 40
UNIT-I Page 16 of 40
 UNIT-I
Page 17 of 40
UNIT-I Page 18 of 40
Probability and Statistics
Probability is a study of uncertainty (loosely terms). The probability here can be thought of as a time
where the event occurs or the degree of belief about an event's occurrence. The probability
distribution is a function that measures the probability of a particular outcome (or probability set of
outcomes) that would occur associated with the random variable. The common probability
distribution function is shown in the image below.

Normal Distribution Probability Function

Probability theory and statistics are often associated with a similar thing, but they concern different
aspects of uncertainty:
• In math, we define probability as a model of some process where random variables capture the
underlying uncertainty, and we use the rules of probability to summarize what happens. • In
statistics, we try to figure out the underlying process observe of something that has happened and
tries to explain the observations.
When we talk about machine learning, it is close to statistics because its goal is to construct a model
that adequately represents the process that generated the data.

UNIT-I Page 19 of 40
UNIT-I Page 20 of 40
 Most people have an intuitive understanding of degrees of probability, which is why
we use words like “probably” and “unlikely” in our daily conversation, but we will talk about
how to make quantitative claims about those degrees [1].
In probability theory, an event is a set of outcomes of an experiment to which a
probability is assigned. If E represents an event, then P(E) represents the probability that
Ewill occur. A situation where E might happen (success) or might not happen (failure) is
called a trial.
This event can be anything like tossing a coin, rolling a die or pulling a colored ball
out of a bag. In these examples the outcome of the event is random, so the variable that
represents the outcome of these events is called a random variable.
Let us consider a basic example of tossing a coin. If the coin is fair, then it is just as
likely to come up heads as it is to come up tails. In other words, if we were to repeatedly toss
the coin many times, we would expect about about half of the tosses to be heads and and half
to be tails. In this case, we say that the probability of getting a head is 1/2 or 0.5 .
The empirical probability of an event is given by number of times the event occurs divided
by the total number of incidents observed. If forntrials and we observe ssuccesses, the
probability of success is s/n. In the above example. any sequence of coin tosses may have
more or less than exactly 50% heads.
Theoretical probability on the other hand is given by the number of ways the
particular event can occur divided by the total number of possible outcomes. So a head can
occur once and possible outcomes are two (head, tail). The true (theoretical) probability of a
head is 1/2.

Joint Probability
Probability of events A and B denoted byP(A and B) or P(A ∩ B)is the probability
that events A and B both occur. P(A ∩ B) = P(A). P(B) . This only applies if Aand Bare
independent, which means that if Aoccurred, that doesn’t change the probability of B, and
vice versa.
Conditional Probability
Let us consider A and B are not independent, because if A occurred, the probability of
B is higher. When A and B are not independent, it is often useful to compute the conditional
probability, P (A|B), which is the probability of A given that B occurred: P(A|B) = P(A ∩ B)/
P(B).
The probability of an event A conditioned on an event B is denoted and defined
P(A|B) = P(A∩B)/P(B)
 UNIT-I Page 21 of 40
Similarly, P(B|A) = P(A ∩ B)/ P(A) . We can write the joint probability of as A and B as
P(A ∩ B)= p(A).P(B|A), which means : “The chance of both things happening is the chance
that the first one happens, and then the second one given the first happened.” Bayes’
Theorem
Bayes’s theorem is a relationship between the conditional probabilities of two events. For
example, if we want to find the probability of selling ice cream on a hot and sunny day,
Bayes’ theorem gives us the tools to use prior knowledge about the likelihood of selling ice
cream on any other type of day (rainy, windy, snowy etc.).

where Hand E are events, P(H|E) is the conditional probability that event H occurs given that
event E has already occurred. The probability P(H) in the equation is basically frequency
analysis; given our prior data what is the probability of the event occurring. The P(E|H) in
the equation is called the likelihood and is essentially the probability that the evidence is
correct, given the information from the frequency analysis. P(E) is the probability that the
actual evidence is true.
Let H represent the event that we sell ice cream and Ebe the event of the weather. Then we
might ask what is the probability of selling ice cream on any given day given the type of
weather? Mathematically this is written as P(H=ice cream sale | E= type of weather) which is
equivalent to the left hand side of the equation. P(H) on the right hand side is the expression
that is known as the prior because we might already know the marginal probability of the
sale of ice cream. In our example this is P(H = ice cream sale), i.e. the probability of selling
ice cream regardless of the type of weather outside. For example, I could look at data that
said 30 people out of a potential 100 actually bought ice cream at some shop somewhere. So
my P(H = ice cream sale) = 30/100 = 0.3, prior to me knowing anything about the weather.
This is how Bayes’ Theorem allows us to incorporate prior information [2].

A classic use of Bayes’s theorem is in the interpretation of clinical tests. Suppose that during
a routine medical examination, your doctor informs you that you have tested positive for a
rare disease. You are also aware that there is some uncertainty in the results of these tests.
Assuming we have a Sensitivity (also called the true positive rate) result for 95% of the
patients with the disease, and a Specificity (also called the true negative rate) result for 95%
of the healthy patients.
If we let “+” and “−” denote a positive and negative test result, respectively, then the test
accuracies are the conditional probabilities : P(+|disease) = 0.95, P(-|healthy) = 0.95, In
Bayesian terms, we want to compute the probability of disease given a positive test,
P(disease|+).
P(disease|+) = P(+|disease)* P(disease)/P(+)

How to evaluate P(+), all positive cases ? We have to consider two possibilities,
P(+|disease) and P(+|healthy). The probability of a false positive, P(+|healthy), is the
complement of the P(-|healthy). Thus P(+|healthy) = 0.05.
 UNIT-I Page 22 of 40

Importantly, Bayes’ theorem reveals that in order to compute the conditional

probability that you have the disease given the test was positive, you need to know the
“prior” probability you have the diseaseP(disease), given no information at all. That is, you
need to know the overall incidence of the disease in the population to which you belong.
Assuming these tests are applied to a population where the actual disease is found to be 0.5%,
P(disease)= 0.005 which means P(healthy) = 0.995.
So, P(disease|+) = 0.95 * 0.005 /(0.95 * 0.005 + 0.05 * 0.995) = 0.088
In other words, despite the apparent reliability of the test, the probability that you
actually have the disease is still less than 9%. Getting a positive result increases the
probability you have the disease. But it is incorrect to interpret the 95 % test accuracy as the
probability you have the disease.

Descriptive Statistics
Descriptive statistics refers to methods for summarizing and organizing the information in a
data set. We will use below table to describe some of the statistical concepts [4].

Elements: The
entities for which information is collected are called the elements. In the above table, the
elements are the 10 applicants. Elements are also called cases or subjects. Variables: The
characteristic of an element is called a variable. It can take different values for different
elements.e.g., marital status, mortgage, income, rank, year, and risk. Variables are also called
attributes.
Variables can be either qualitative or quantitative.
Qualitative: A qualitative variable enables the elements to be classified or categorized
according to some characteristic. The qualitative variables are marital status, mortgage, rank,
and risk. Qualitative variables are also called categorical variables.
Quantitative: A quantitative variable takes numeric values and allows arithmetic to be
meaningfully performed on it. The quantitative variables are income and year. Quantitative
variables are also called numerical variables.
Discrete Variable: A numerical variable that can take either a finite or a countable number of
values is a discrete variable, for which each value can be graphed as a separate point, with
space between each point. ‘year’ is an example of a discrete variable..
Continuous Variable: A numerical variable that can take infinitely many values is a
continuous variable, whose possible values form an interval on the number line, with no
space between the points. ‘income’ is an example of a continuous variable.
Population: A population is the set of all elements of interest for a particular problem. A
parameter is a characteristic of a population.
Sample: A sample consists of a subset of the population. A characteristic of a sample is called
a statistic.
Random sample: When we take a sample for which each element has an equal chance of
being selected.

UNIT-I Page 23 of 40
Measures of Center: Mean, Median, Mode, Mid-range
Indicate where on the number line the central part of the data is
located. Mean
The mean is the arithmetic average of a data set. To calculate the mean, add up the values and
divide by the number of [Link] sample mean is the arithmetic average of a sample, and is
denoted x̄ (“x-bar”). The population mean is the arithmetic average of a population, and is
denoted 끫븎 (“myu”, the Greek letter for m).
Median
The median is the middle data value, when there is an odd number of data values and the data
have been sorted into ascending order. If there is an even number, the median is the mean of
the two middle data values. When the income data are sorted into ascending order, the two
middle values are $32,100 and $32,200, the mean of which is the median income, $32,150.
Mode
The mode is the data value that occurs with the greatest frequency. Both quantitative and
categorical variables can have modes, but only quantitative variables can have means or
medians. Each income value occurs only once, so there is no mode. The mode for year is
2010, with a frequency of 4.
Mid-range
The mid-range is the average of the maximum and minimum values in a data set. The
mid-range income is:
mid-range(income) = (max(income) + min(income))/2 = (48000 + 24000)/2 =
$36000 Measures of Variability: Range, Variance, Standard Deviation
Quantify the amount of variation, spread or dispersion present in the data.
Range
The range of a variable equals the difference between the maximum and minimum values.
The range of income is:
range(income) = max (income) − min (income) = 48,000 − 24,000 =$24000 Range only
reflects the difference between largest and smallest observation, but it fails to reflect how data
is centralized.
Variance
Population variance is defined as the average of the squared differences from the Mean,
denoted as 끫븜² (“sigma-squared”):

Larger Variance means the data are more spread out.

The sample variance s² is approximately the mean of the squared deviations, with N replaced
by n-1. This difference occurs because the sample mean is used as an approximation of the
true population mean.

Standard Deviation
The standard deviation or sd of a bunch of numbers tells you how much the individual
numbers tend to differ from the mean.
The sample standard deviation is the square root of the sample variance: sd = √ s². For
example, incomes deviate from their mean by $7201.
The population standard deviation is the square root of the population variance: sd= √ 끫븜².

UNIT-I Page 24 of 40

Three different data distributions with same mean (100) and different standard
deviation (5,10,20)
The smaller the standard deviation, narrower the peak, the data points are closer to the mean.
The further the data points are from the mean, the greater the standard deviation. Measures of
Position: Percentile, Z-score, Quartiles
Indicate the relative position of a particular data value in the data
distribution. Percentile
The pth percentile of a data set is the data value such that p percent of the values in the data
set are at or below this value. The 50th percentile is the median. For example, the median
income is $32,150, and 50% of the data values lie at or below this value.
Percentile rank
The percentile rank of a data value equals the percentage of values in the data set that are at or
below that value. For example, the percentile rank. of Applicant 1’s income of $38,000 is
90%, since that is the percentage of incomes equal to or less than $38,000.

Interquartile Range (IQR)

 The first quartile (Q1) is the 25th percentile of a data set; the second quartile (Q2) is
the 50th percentile (median); and the third quartile (Q3) is the 75th percentile. The IQR
measures the difference between 75th and 25th observation using the formula: IQR = Q3 −
Q1.
A data value x is an outlier if either x ≤ Q1 − 1.5(IQR), or x ≥ Q3 + 1.5(IQR).

UNIT-I Page 25 of 40
Z-score
The Z-score for a particular data value represents how many standard deviations the
data value lies above or below the mean.

So, If z is positive, it means that the value is above the average. For Applicant 6, the Z-score
is (24,000 − 32,540)/ 7201 ≈ −1.2, which means the income of Applicant 6 lies 1.2 standard
deviations below the mean.
Uni-variate Descriptive Statistics
Different ways you can describe patterns found in uni-variate data include central
tendency : mean, mode and median and dispersion: range, variance, maximum, minimum,
quartiles , and standard deviation.

Pie chart [left] & Bar chart [right] of Marital status from loan applicants table. The
various plots used to visualize uni-variate data typically are Bar Charts, Histograms, Pie
Charts. etc.
Bi-variate Descriptive Statistics
Bi-variate analysis involves the analysis of two variables for the purpose of determining the
empirical relationship between them. The various plots used to visualize bi-variate data
typically are scatter-plot, box-plot.
Scatter Plots
The simplest way to visualize the relationship between two quantitative variables , x and y.
For two continuous variables, a scatter-plot is a common graph. Each (x, y) point is graphed
on a Cartesian plane, with the x axis on the horizontal and the y axis on the vertical. Scatter
plots are sometimes called correlation plots because they show how two variables are
correlated.
Correlation
A correlation is a statistic intended to quantify the strength of the relationship between two
variables. The correlation coefficient r quantifies the strength and direction of the linear
relationship between two quantitative variables. The correlation coefficient is defined as:
 where sx and sy represent the standard deviation of the x-variable and the y-variable,
respectively. −1 ≤ r ≤ 1.
If r is positive and significant, we say that x and y are positively correlated. An increase in x is
associated with an increase in y.
If r is negative and significant, we say that x and y are negatively correlated. An increase in x
is associated with a decrease in y.

UNIT-I Page 26 of 40

Positive correlation (r > 0), Negative correlation (r < 0), No correlation (r = 0) Box Plots
A box plot is also called a box and whisker plot and it’s used to picture the distribution of
values. When one variable is categorical and the other continuous, a box-plot is commonly
used. When you use a box plot you divide the data values into four parts called quartiles.
You start by finding the median or middle value. The median splits the data values into
halves. Finding the median of each half splits the data values into four parts, the quartiles.
Each box on the plot shows the range of values from the median of the lower half of the
values at the bottom of the box to the median of the upper half of the values at the top of the
box. A line in the middle of the box occurs at the median of all the data values. The
whiskers then point to the largest and smallest values in the data.

The five-number summary of a data set consists of the minimum, Q1, the median, Q3, and
the maximum.
Box plots are especially useful for indicating whether a distribution is skewed and whether
there are potential unusual observations (outliers) in the data set. The left whisker extends
down to the minimum value which is not an outlier. The right whisker extends up to the
maximum value that is not an outlier. When the left whisker is longer than the right whisker,
then the distribution is left-skewed and vice versa. When the whiskers are about equal in
length, the distribution is symmetric.
Bayesian Conditional Probability

UNIT-I Page 27 of 40
 UNIT-I Page 28 of 40

Optimization
UNIT-I Page 29 of 40
UNIT-I Page 30 of 40
UNIT-I Page 31 of 40
 UNIT-I Page 32 of 40
Decision Theory
UNIT-I Page 33 of 40
 UNIT-I Page 34 of 40
Information Theory

Knowledge discovery is a process that helps you engineer features or attributes in a

base dataset to improve the performance of the machine learning models. Information theory
has a lot of 'information measures' or metrics that can help you evaluate the importance and
relevance of each new attribute that you develop. For instance, if you develop new attributes
in a dataset, you should use measures like mutual information and conditional entropy to
evaluate how significant an explanatory variable is with respect to the target or the dependent
variable.
We have already seen in the sections above that conditional entropy determines how
two variables are correlated. If H(Y|X=xi) represents the conditional entropy of a variable 'Y'
given X=xi. Let us assume that 'Y' represents the target variable in a machine learning model
and 'X' is an explanatory variable, say a categorical variable with several labels (xi) where 'i'
specifies the number of unique labels of the variable 'X'. In this case, we need to ensure that
H(Y|X=xi) when aggregated for all 'i' is close to zero. This is because H(Y|X)=0 if and only if
the value of 'Y' is completely determined by the value of X. The value of conditional entropy
H(Y|X) is equal to H(Y) if and only if 'Y; and 'X' are independent random variables. Our aim
while designing and collecting variables is to achieve a conditional entropy value of close to
'0'. In terms of mutual information, we need to collate and engineer features such that the
mutual information between 'Y' and 'X' is maximized. Below is a table of some important
information measures that we have already covered so far, that can be used for this purpose.

Figure 20: Information Measures that can be used as learning and content measures

An automated, relatively new of method of deriving and creating features is feature

learning. It helps you automatically discover (or learn) the data transformations and
representations needed for feature detection in a dataset. You can conduct two types of feature
learning techniques: 1) Supervised: where features are learned using labeled input data, and 2)
Unsupervised: where features are learned with unlabeled input data. Rate distortion theory is
widely used in feature learning- both supervised and unsupervised. If X is the instance in your
dataset and Z represents the feature, the objective is to optimize the mutual information
between X and Z such that I(X,Z) is bounded by a minimum value of a distortion function.
This means that we could design a distortion function d(X,Z) that quantifies the quality of the
feature map I(X,Z) and place lower bounds on the same to ensure that the loss of
compression/data transformation is minimal.

Introduction
Information can be represented as bits. One bit of information allows us to choose
between two equally probable, or equiprobable, alternatives. In other words, in a scenario with
2 equiprobable choices, if you get an instruction to choose one of the choices, that is one bit of
information. Say, each instruction can be represented as a binary digit (0='choice 1' and
1='choice 2') then this binary digit provides you with one bit of information. In the case of 'n'

UNIT-I Page 35 of 40
n
sequential forks, with 'm' final choices (destinations), then m= 2 . In other words, n= log2m.
Information is thus, an ordered symbol of sequences to interpret its meaning. Please note: A
binary digit is the value of a binary variable, whereas a bit is an amount of information. A
binary digit (when averaged over both of its possible states) can convey between zero and one
bit of information.
By now, we know what information means. It is a mathematical representation of
uncertainty. Let us now understand what information theory is.

Figure 1: A
binary symmetric channel showing probability of incorrect transmission of message
given the transmitted symbol is x and the received symbol is y

When we transmit data, for instance, a string of bits, over a communication channel or
any computational medium, there is a probability (say 'p') that the received message will not
be identical to the transmitted message. An ideal channel is where this probability (p) is zero
(or almost 0). However, most real world channels have a non zero probability 'f' of incorrect
transmission of information and a probability of (1 minus f) that each bit of information will
be transmitted correctly. Given this probability of error, one needs to find solutions to reduce
the same in order to transmit information with minimum error. One can use the 'physical
solution' where one needs to revamp the physical attributes of the communication channel, for
instance the circuitry. However, this might increase the operational cost. An alternative
solution is to update the system using 'information theory' and 'coding theory'. Under these
solutions, we accept the given noisy physical channel in its current form. We then add
communication systems to it so that we can detect and correct the errors introduced by the
channel. This system normally comprises of an encoder and decoder. The 'system' solutions
can help you design a reliable communication channel with the only additional cost of
computations of an encoder and a decoder. While coding theory helps you design the
appropriate decoder and encoder, information theory helps you define the quality of
information or content you can transmit. It can help you study the theoretical limitations and
potentials of a system.

Information theory treats information as a physical entity, like energy or mass. It deals
with theoretical analyses of how information can be transmitted over any channel: natural or
man-made. Thus, it defines a few laws of information. Let us assume a basic system for
information flow as follows:

Figure 2:
Information Channel: A message (data) is encoded before being fed into a communication
channel, which adds noise. The channel output has the encoded message with noise that is
decoded by a receiver to recover the message.
There are a few laws on information that can be derived from the above channel: • There is a
definite upper limit, the channel capacity, to the amount of information that can be
communicated through that channel.
• This limit shrinks as the amount of noise in the channel increases.
• This limit can very nearly be reached by judicious packaging, or encoding, of data.

UNIT-I Page 36 of 40
Essentially, information theory entails two broad techniques:
1. Data Compression (source coding): More frequent events should have shorter
encodings
2. Error Correction (channel coding): Should be able to infer encoded event even if
message is corrupted by noise

Both these methods require you to build probabilistic models of the data sources. This is
why information theory is relevant to machine learning and data analytics. It not only helps
you measure the accuracy of information contained in a data source, but also helps you
improve results of predictive models that might be built on this data. Before we study how
information theory can be applied to, let us study a few basic terms.

Few important terms of Information Theory and Machine Learning

Codewords
Information theory represents data in the form of codewords. These codewords are
representation of the actual data elements in the form of sequence of binary digits or bits.
There are various techniques to map each symbol (data element) with the corresponding
codeword.

Variable Length Codes

One traditional way of assigning codewords to data elements would be to assign codes
with fixed lengths, or every data element gets assigned a code of the same code length. Let us
look at a visual representation of the same. If we have 4 values of a given variable, say
'Discount type' with the following 4 values: 'Promotion', 'Priority Customer', 'Repeat buy' and
'None'. If we assume that the 4 types of discounts are equally probable, they can safely be
mapped to codewords of equal length, say 00, 01, 10 and 11, as shown in the image below:

Figure 3: Fixed Length Encoding: Every data element here is assumed to have equal
likelhood of occurrence. Hence, every code word have equal and fixed length (i.e. 2)

Now, if we know that discounts under 'Promotion' are more frequent than the rest and have
been assigned the following probability values.

Figure 4: Varying probabilities of each data element indicating the likelihood of occurrence
of the event
 UNIT-I Page 37 of 40
We can then, design codes weighted according to these probability values. We design
the code to reduce the total length of the message. Since one would transmit the most frequent
terms (data elements) most number of times, you would want to associate the least length with
the most frequent term. Hence, we design a code with the least number of bits for the most
frequent data element. Let us look at an example of the same.

Figure 5:
Variable Length Encoding: Every data element has been mapped to a sequence of binary
codes of varying length according to the probability of occurrence

This variable-length code will now represent each data element in a unique and
exclusive manner. Moreover, if you consider the vertical axis to visualize the probability of
each word, p(x), and the horizontal axis to visualize the length of the corresponding
codeword, L(x), let us compute the area covered by the encoding. This amounts to 1.75 bits,
which is a reduction from a fixed-length encoding of 2 bits each for all the above terms. The
fixed-length encoding would amount to 2 bits.

Optimal Encoding
The most optimal encoding has to strike a balance between the length of the message
and the cost of the codeword. Let us look at how one affects the other. The cost of buying a
codeword of length 0 is 1. This is because you are buying all possible codewords, and hence,
if you want to have a codeword of length 0, you can’t have any other codeword. The cost of a
codeword of length 1, like "0" or "1", is (1/2) because half of possible codewords start with
"0" or "1" respectively. The cost of a codeword of length 2, like “01”, is (1/4) because a
quarter of all possible codewords start with “01”. In general, the cost of codewords decreases
exponentially with the length of the codeword.

Refer to the image below:

Figure 6: Cost of a codeword as a function of the length of the codeword

We know that the average length of the total code string is the function of the
probability of each word and the length of the corresponding codeword. It can be represented
as p(x)∗L(x). This average length contribution is related to the cost through the length of the
codeword. The amount we pay decides the length of the codeword. The length of the
codeword controls how

UNIT-I Page 38 of 40
much it adds to the average message length. We can picture the two of these together in the
following way:

Figure 7: Relationship between Average Length Contribution and Cost of the Codeword

Thus, we can clearly establish that shorter codewords cost higher and vice versa.

Figure 8: Costs of long and short codewords

Shannon Information Content

Let us consider a set of discrete random variables 'X' which contains a possible set of
events {ai} where 'i' represents the range of elements contained in the set 'X'. Shannon
Information Content or Information Content is the measure of information contained in the
event: X=ai. Information content actually quantifies the surprisal of each outcome of any
experiment. Higher the surprisal of an outcome, higher is the information content.
Thus, the information you can gain when an event occurs which had some probability
value associated with it, can be represented as:
h(X=ai)=log2(1/p(X=ai)) (1)
The above equation will show that as the value of probability 'p' increases, the information
content decreases. You get a curve that looks something like this:

Figure 9: The information content function versus probability values

The information content is measured in bits. It is also known as self information.
Entropy
While designing an optimal codeword for our data elements above, we see that the
average length contribution of a message and the cost of the same line up well. In other words,

UNIT-I Page 39 of 40
the height of the rectangle denoting the average length contribution of messages is almost
equal to the maximum height of the exponential curve denting the cost of the codeword.
Thus, if we slightly increase the length of the codeword, the message length contribution will
increase in proportion to its height at the boundary, while the cost will decrease in proportion
to its height at the boundary.

Figure 10: Proportionality of cost with the height of the message length contribution

We can also say that the cost to make the codeword for a data element 'a' shorter is
p(a). Now, let us generalize this to any message 'X'. For a message 'X' with the likelihood of
occurrence p(X), the cost can be approximated as p(X) too. We also know that the cost of a
message of length 'L' is 1/2L. If we invert this to obtain the length of a message that costs a
given amount (cost), we get: L=log(1/cost). If we substitute the value of cost by p(X), we
derive 'L' as log(1/p(X)). Thus, the length of a message 'X' can be denoted in terms of its
probability in the following equation:
L(X)=log2(1/p(X))
As we discussed earlier, there is a limit to how short an average message can get to
communicate events effectively, from a particular probability distribution 'p' of events 'X'.
This limit, the average message length using the best possible code, is called the entropy or
Shannon entropy of 'p', H(X). In other words, entropy is a measure of unpredictability of the
state (X), or equivalently, of its average information content. The formula to represent
entropy is as follows:

H(X) can also be denoted by H(p) where 'p' is the vector containing probabilities of
each of the discrete events. Entropy is measured in bits too.

Conditional Entropy
The average uncertainty about the output value (say 'Y') given an input value ('X') is
the conditional entropy H(Y|X). Here, H(Y|X) is, ‘the residual uncertainty (entropy) of 'Y'
given that we know the value of 'X'’. Let us assume a channel with noise η and input 'X' and
output 'Y'. In this case, H(Y|X) can also be represented as H(η). It can be represented in the
following form:

The above equation can further be condensed into the following form:
You could modify this equation for a given value of the input, say X=ai in the following
manner:

UNIT-I Page 40 of 40
CP4252 MACHINE LEARNING
UNIT II SUPERVISED LEARNING
Introduction-Discriminative and Generative Models -Linear Regression - Least Squares -Under-fitting
/ Overfitting -Cross-Validation – Lasso Regression- Classification - Logistic Regression- Gradient
Linear Models -Support Vector Machines –Kernel Methods -Instance based Methods - K-Nearest
Neighbors - Tree based Methods –Decision Trees –ID3 – CART - Ensemble Methods –Random Forest
- Evaluation of Classification Algorithms

1. Introduction - Generative And Discriminative Models

Intro
Recently I gave a presentation at work, where I explained how I solved some problem using
Conditional Random Fields (CRF). And, since CRF was not so much known to my colleagues, I had a
couple of slides devoted to the theory behind this algorithm. As I prepared the theory slides, I felt a
duty to compare CRF with a conceptually similar algorithm, Hidden Markov Model (HMM). CRF is
known to be a discriminative model and HMM is a generative model. I had to refresh my knowledge
about this categorisation of supervised machine learning methods, especially generative models. Now
I would like to share my understanding of the difference between generative and discriminative
models in simple terms.
Generative models are a wide class of machine learning algorithms which make predictions
by modelling joint distribution P(y, x).
Discriminative models are a class of supervised machine learning models which make
predictions by estimating conditional probability P(y|x).
In order to use a generative model, more unknowns should be solved: one has to estimate
probability of each class and probability of observation given class. These probabilities are used to
compute joint probability, and finally, joint probability can be used as a substitute for conditional
probability to make predictions.

The discriminative model takes a shorter way: it simply estimates conditional probability
directly.
There are many pros and cons to each of the models. I just note that generative model can be
used to generate new samples, but it requires more data. Discriminative model often superior than
generative model, given the same amount of data, but it does not know about dependencies between
features, because it is irrelevant for prediction. Therefore discriminative model can not generate new
samples. Now let’s take a closer look at the concept of generative models.

Generative model
As I showed earlier, to make predictions, conditional distribution P(y|x) is enough. But since
P(y|x) = P(y, x) / P(x), where P(x) is constant for the given x and all possible y, it is valid to use joint
distribution P(y, x) to make predictions.
By modelling joint distribution P(y, x) is meant that for each pair (yᵢ, xᵢ) a probability P(yi, xi)
is known (modelled). At the beginning it was a bit difficult for me to understand how it is even
possible

UNIT-II Page 1 of 43
— the range of possible values of X might be enormous, so it’s gonna be unrealistic to suggest
probabilities for each xi, leave alone pair (yi, xi). How is it supposed to be done? First. Bayes
theorem! It breaks computation of joint probability P(y,x) into computation of two other types of
probabilities: probability of class, P(y), and probability of observation given class, P(x|y). P(y, x) =
P(y) * P(x|y)
What benefits does it give? This way it is at least easier to figure out probability P(y), because it can
be estimated from the dataset by computing class frequencies. P(x|y) is trickier, because usually x is
not just one feature, but a set of features: x = xi, …, xn, which might have dependencies between each
other. P(x|y) = П P(xi|y, x1, xi-1, xi+1, xn)

Often the dependencies between the features are not known, especially when they appear in
complex constellations (y, x1, xi-1, xi+1, xn).
So what should be done to estimate P(x|y)? For this, there is the following trick:

Second. Make wild assumptions! Or just some assumptions which make estimation of P(x|y)
tractable. Naive Bayes classifier can serve as a perfect example of a generative model with such
assumption, which makes computation of P(x|y) easier. Namely, it has independence assumption
between the features xi, …, xn.
P(x|y) = П P(xi|y)
With this relaxation, estimation of P(x|y) is tractable, because every P(xi|y) can be estimated either by
finding frequencies of discrete feature xi independently from other features or using Gaussian
distribution, if feature xi is continuous.

Conclusion
So now you can see that in order to use generative models one should be prepared to estimate
two types of probabilities P(y) and P(x|y). At the same time, discriminative models estimate
conditional probability P(y|x) directly, which often is more efficient because one does not estimate
dependencies between features, as these relationships don’t necessarily contribute to the prediction of
the target variable.

2. Linear Regression

Linear regression is one of the easiest and most popular Machine Learning algorithms.
It is a statistical method that is used for predictive analysis. Linear regression makes
predictions for continuous/real or numeric variables such as sales, salary, age, product
price, etc.
Linear regression algorithm shows a linear relationship between a dependent (y) and
one or more independent (y) variables, hence called as linear regression. Since linear
regression shows the linear relationship, which means it finds how the value of the dependent
variable is changing according to the value of the independent variable.
The linear regression model provides a sloped straight line representing the
relationship between the variables. Consider the below image:
 UNIT-II Page 2 of 43
Mathematically, we can represent a linear regression as:
y= a0+a1x+ ε
Here,
Y= Dependent Variable (Target Variable)
X= Independent Variable (predictor Variable)
a0= intercept of the line (Gives an additional degree of freedom)
a1 = Linear regression coefficient (scale factor to each input value).
ε = random error
The values for x and y variables are training datasets for Linear Regression model
representation.

Types of Linear Regression

Linear regression can be further divided into two types of the algorithm:
o Simple Linear Regression:
If a single independent variable is used to predict the value of a numerical dependent
variable, then such a Linear Regression algorithm is called Simple Linear Regression. o
Multiple Linear regression:
If more than one independent variable is used to predict the value of a numerical
dependent variable, then such a Linear Regression algorithm is called Multiple Linear
Regression.

Linear Regression Line

A linear line showing the relationship between the dependent and independent variables is
called a regression line. A regression line can show two types of relationship: o Positive
Linear Relationship:
If the dependent variable increases on the Y-axis and independent variable increases
on X-axis, then such a relationship is termed as a Positive linear relationship.

o Negative Linear Relationship:

If the dependent variable decreases on the Y-axis and independent variable increases
 on the X-axis, then such a relationship is called a negative linear relationship.

UNIT-II Page 3 of 43
Finding the best fit line:
When working with linear regression, our main goal is to find the best fit line that
means the error between predicted values and actual values should be minimized. The best fit
line will have the least error.
The different values for weights or the coefficient of lines (a0, a1) gives a different line
of regression, so we need to calculate the best values for a0 and a1 to find the best fit line, so to
calculate this we use cost function.

Cost function
o The different values for weights or coefficient of lines (a0, a1) gives the different line of
regression, and the cost function is used to estimate the values of the coefficient for the
best fit line.
o Cost function optimizes the regression coefficients or weights. It measures how a linear
regression model is performing.
o We can use the cost function to find the accuracy of the mapping function, which maps
the input variable to the output variable. This mapping function is also known as
Hypothesis function.

For Linear Regression, we use the Mean Squared Error (MSE) cost function, which is
the average of squared error occurred between the predicted values and actual values. It can be
written as:
For the above linear equation, MSE can be calculated as:

Where,
N=Total number of observation
Yi = Actual value
(a1xi+a0)= Predicted value.

Residuals: The distance between the actual value and predicted values is called residual. If
the observed points are far from the regression line, then the residual will be high, and so cost
function will high. If the scatter points are close to the regression line, then the residual will be
small and hence the cost function.

Gradient Descent:
o Gradient descent is used to minimize the MSE by calculating the gradient of the cost
function.
 o A regression model uses gradient descent to update the coefficients of the line by
reducing the cost function.
o It is done by a random selection of values of coefficient and then iteratively update the
values to reach the minimum cost function.

Model Performance:
The Goodness of fit determines how the line of regression fits the set of observations.
The process of finding the best model out of various models is called optimization. It can be
achieved by below method:

1. R-squared method:
o R-squared is a statistical method that determines the goodness of fit. o It measures the
strength of the relationship between the dependent and independent variables on a scale
of 0-100%.

UNIT-II Page 4 of 43
o The high value of R-square determines the less difference between the predicted values
and actual values and hence represents a good model.
o It is also called a coefficient of determination, or coefficient of multiple
determination for multiple regression.
o It can be calculated from the below formula:

Assumptions of Linear Regression

Below are some important assumptions of Linear Regression. These are some formal
checks while building a Linear Regression model, which ensures to get the best possible result
from the given dataset.
o Linear relationship between the features and target: Linear regression assumes the
linear relationship between the dependent and independent variables.
o Small or no multicollinearity between the features: Multicollinearity means high
correlation between the independent variables. Due to multicollinearity, it may
difficult to find the true relationship between the predictors and target variables. Or
we can say, it is difficult to determine which predictor variable is affecting the target
variable and which is not. So, the model assumes either little or no multicollinearity
between the features or independent variables.
o Homoscedasticity Assumption: Homoscedasticity is a situation when the error term is
the same for all the values of independent variables. With homoscedasticity, there
should be no clear pattern distribution of data in the scatter plot.
o Normal distribution of error terms: Linear regression assumes that the error term
should follow the normal distribution pattern. If error terms are not normally
distributed, then confidence intervals will become either too wide or too narrow, which
may cause difficulties in finding coefficients. It can be checked using the q-q plot. If
the plot shows a straight line without any deviation, which means the error is normally
distributed.
o No autocorrelations: The linear regression model assumes no autocorrelation in error
terms. If there will be any correlation in the error term, then it will drastically reduce
the accuracy of the model. Autocorrelation usually occurs if there is a dependency
between residual errors.
 3. Least Squares
The least square method is the process of finding the best-fitting curve or line of best fit for a
set of data points by reducing the sum of the squares of the offsets (residual part) of the points from
the curve. During the process of finding the relation between two variables, the trend of outcomes are
estimated quantitatively. This process is termed as regression analysis. The method of curve fitting is
an approach to regression analysis. This method of fitting equations which approximates the curves to
given raw data is the least squares.

It is quite obvious that the fitting of curves for a particular data set are not always unique.
Thus, it is required to find a curve having a minimal deviation from all the measured data points. This
is known as the best-fitting curve and is found by using the least-squares method.

Least Square Method Definition

The least-squares method is a crucial statistical method that is practised to find a regression
line or a best-fit line for the given pattern. This method is described by an equation with specific
parameters. The method of least squares is generously used in evaluation and regression. In
regression analysis, this method is said to be a standard approach for the approximation of sets of
equations having more equations than the number of unknowns.

UNIT-II Page 5 of 43
The method of least squares actually defines the solution for the minimization of the sum of
squares of deviations or the errors in the result of each equation. Find the formula for sum of squares
of errors, which help to find the variation in observed data.
The least-squares method is often applied in data fitting. The best fit result is assumed to
reduce the sum of squared errors or residuals which are stated to be the differences between the
observed or experimental value and corresponding fitted value given in the model.

There are two basic categories of least-squares problems:

• Ordinary or linear least squares
• Nonlinear least squares

These depend upon linearity or nonlinearity of the residuals. The linear problems are often seen in
regression analysis in statistics. On the other hand, the non-linear problems are generally used in the
iterative method of refinement in which the model is approximated to the linear one with each
iteration. Least Square Method Graph
In linear regression, the line of best fit is a straight line as shown in the following diagram:

The given data points are to be minimized by the method of reducing residuals or offsets of
each point from the line. The vertical offsets are generally used in surface, polynomial and hyperplane
problems, while perpendicular offsets are utilized in common practice.
Least Square Method Formula
The least-square method states that the curve that best fits a given set of observations, is said
to be a curve having a minimum sum of the squared residuals (or deviations or errors) from the given
data points. Let us assume that the given points of data are (x1, y1), (x2, y2), (x3, y3), …, (xn, yn) in
which all x’s are independent variables, while all y’s are dependent ones. Also, suppose that f(x) is
the fitting curve and d represents error or deviation from each given point.
Now, we can write:
d1 = y1 − f(x1)
d2 = y2 − f(x2)
d3 = y3 − f(x3)
…..
dn = yn – f(xn)

The least-squares explain that the curve that best fits is represented by the property that the
sum of squares of all the deviations from given values must be minimum, i.e:

UNIT-II Page 6 of 43

Sum = Minimum Quantity

Suppose when we have to determine the equation of line of best fit for the given data, then we
first use the following formula.

The equation of least square line is given by Y = a + bX

Normal equation for ‘a’:
∑Y = na + b∑X
Normal equation for ‘b’:

∑XY = a∑X + b∑X2

Solving these two normal equations we can get the required trend line equation.
Thus, we can get the line of best fit with formula y = ax + b

Solved Example
The Least Squares Model for a set of data (x1, y1), (x2, y2), (x3, y3), …, (xn, yn) passes through
the point (xa, ya) where xa is the average of the xi‘s and ya is the average of the yi‘s. The below example
explains how to find the equation of a straight line or a least square line using the least square method.
Question:
Consider the time series data given below:
 xi 8 3 2 10 11 3 6 5 6 8

yi 4 12 1 12 9 4 9 6 1 14

Use the least square method to determine the equation of line of best fit for the data. Then plot
the line.
Solution:
Mean of xi values = (8 + 3 + 2 + 10 + 11 + 3 + 6 + 5 + 6 + 8)/10 = 62/10 = 6.2
Mean of yi values = (4 + 12 + 1 + 12 + 9 + 4 + 9 + 6 + 1 + 14)/10 = 72/10 = 7.2
Straight line equation is y = a + bx.
The normal equations are
∑y = an + b∑x
∑xy = a∑x + b∑x2
x y x2 xy

8 4 64 32

3 12 9 36

2 1 4 2

10 12 100 120

11 9 121 99

3 4 9 12

UNIT-II Page 7 of 43
6 9 36 54

5 6 25 30

6 1 36 6

8 14 64 112

∑x = 62 ∑y = 72 ∑x2 = 468 ∑xy = 503

Substituting these values in the normal equations,

10a + 62b = 72….(1)
62a + 468b = 503….(2)
(1) × 62 – (2) × 10,
620a + 3844b – (620a + 4680b) = 4464 – 5030
-836b = -566
b = 566/836
b = 283/418
b = 0.677
Substituting b = 0.677 in equation (1),
10a + 62(0.677) = 72
10a + 41.974 = 72
 10a = 72 – 41.974
10a = 30.026
a = 30.026/10
a = 3.0026
Therefore, the equation becomes,
y = a + bx
y = 3.0026 + 0.677x

This is the required trend line equation.

Now, we can find the sum of squares of deviations from the obtained values as:
d1 = [4 – (3.0026 + 0.677*8)] = (-4.4186)
d2 = [12 – (3.0026 + 0.677*3)] = (6.9664)
d3 = [1 – (3.0026 + 0.677*2)] = (-3.3566)
d4 = [12 – (3.0026 + 0.677*10)] = (2.2274)
d5 = [9 – (3.0026 + 0.677*11)] =(-1.4496)
d6 = [4 – (3.0026 + 0.677*3)] = (-1.0336)
d7 = [9 – (3.0026 + 0.677*6)] = (1.9354)
d8 = [6 – (3.0026 + 0.677*5)] = (-0.3876)
d9 = [1 – (3.0026 + 0.677*6)] = (-6.0646)
d10 = [14 – (3.0026 + 0.677*8)] = (5.5814)
∑d2 = (-4.4186)2 + (6.9664)2 + (-3.3566)2 + (2.2274)2 + (-1.4496)2 + (-1.0336)2 + (1.9354)2 +
(-0.3876)2 + (-6.0646)2 + (5.5814)2 = 159.27990

Limitations for Least-Square Method

UNIT-II Page 8 of 43
The least-squares method is a very beneficial method of curve fitting. Despite many benefits,
it has a few shortcomings too. One of the main limitations is discussed here.
In the process of regression analysis, which utilizes the least-square method for curve fitting,
it is inevitably assumed that the errors in the independent variable are negligible or zero. In such
cases, when independent variable errors are non-negligible, the models are subjected to measurement
errors. Therefore, here, the least square method may even lead to hypothesis testing, where parameter
estimates and confidence intervals are taken into consideration due to the presence of errors occurring
in the independent variables.

4. Under-fitting / Overfitting -Cross-Validation

When we talk about the Machine Learning model, we actually talk about how well it performs and
its accuracy which is known as prediction errors. Let us consider that we are designing a machine
learning model. A model is said to be a good machine learning model if it generalizes any new input
data from the problem domain in a proper way. This helps us to make predictions about future data,
that the data model has never seen. Now, suppose we want to check how well our machine learning
model learns and generalizes to the new data. For that, we have overfitting and underfitting, which are
majorly responsible for the poor performances of the machine learning algorithms.
Before diving further let’s understand two important terms:
• Bias: Assumptions made by a model to make a function easier to learn. It is actually the error
rate of the training data. When the error rate has a high value, we call it High Bias and when
the error rate has a low value, we call it low Bias.
• Variance: The difference between the error rate of training data and testing data is called
variance. If the difference is high then it’s called high variance and when the difference of
errors is low then it’s called low variance. Usually, we want to make a low variance for
generalized our model.

Underfitting: A statistical model or a machine learning algorithm is said to have underfitting when it
cannot capture the underlying trend of the data, i.e., it only performs well on training data but
performs poorly on testing data. (It’s just like trying to fit undersized pants!) Underfitting destroys the
accuracy of our machine learning model. Its occurrence simply means that our model or the algorithm
does not fit the data well enough. It usually happens when we have fewer data to build an accurate
model and also when we try to build a linear model with fewer non-linear data. In such cases, the
rules of the machine learning model are too easy and flexible to be applied to such minimal data and
therefore the model will probably make a lot of wrong predictions. Underfitting can be avoided by
using more data and also reducing the features by feature selection.

In a nutshell, Underfitting refers to a model that can neither performs well on the training data nor
generalize to new data.

Reasons for Underfitting:

1. High bias and low variance
2. The size of the training dataset used is not enough.
3. The model is too simple.
4. Training data is not cleaned and also contains noise in it.

Techniques to reduce underfitting:

1. Increase model complexity
2. Increase the number of features, performing feature engineering
3. Remove noise from the data.
4. Increase the number of epochs or increase the duration of training to get better results.

Overfitting: A statistical model is said to be overfitted when the model does not make accurate
predictions on testing data. When a model gets trained with so much data, it starts learning from the
noise and inaccurate data entries in our data set. And when testing with test data results in High
variance.

UNIT-II Page 9 of 43
Then the model does not categorize the data correctly, because of too many details and noise. The
causes of overfitting are the non-parametric and non-linear methods because these types of machine
learning algorithms have more freedom in building the model based on the dataset and therefore they
can really build unrealistic models. A solution to avoid overfitting is using a linear algorithm if we
have linear data or using the parameters like the maximal depth if we are using decision trees.

In a nutshell, Overfitting is a problem where the evaluation of machine learning algorithms on training
data is different from unseen data.

Reasons for Overfitting are as follows:

1. High variance and low bias
2. The model is too complex
3. The size of the training data

Examples:
Techniques to reduce overfitting:
1. Increase training data.
2. Reduce model complexity.
3. Early stopping during the training phase (have an eye over the loss over the training period as
soon as loss begins to increase stop training).
4. Ridge Regularization and Lasso Regularization
5. Use dropout for neural networks to tackle overfitting.

Good Fit in a Statistical Model: Ideally, the case when the model makes the predictions with 0 error,
is said to have a good fit on the data. This situation is achievable at a spot between overfitting and
underfitting. In order to understand it, we will have to look at the performance of our model with the
passage of time, while it is learning from the training dataset.
With the passage of time, our model will keep on learning, and thus the error for the model on the
training and testing data will keep on decreasing. If it will learn for too long, the model will become
more prone to overfitting due to the presence of noise and less useful details. Hence the performance
of our model will decrease. In order to get a good fit, we will stop at a point just before where the
error starts increasing. At this point, the model is said to have good skills in training datasets as well
as our unseen testing dataset.

UNIT-II Page 10 of 43
Cross Validation
Unfortunately, things are a little bit more complicated than that, since we might also want to
know how well the algorithm is generalising as it learns: we need to make sure that we do enough
training that the algorithm generalises well. In fact, there is at least as much danger in over-training as
there is in under-training. The number of degrees of variability in most machine learning algorithms is
huge — for a neural network there are lots of weights, and each of them can vary. This is undoubtedly
more variation than there is in the function we are learning, so we need to be careful: if we train for
too long, then we will overfit the data, which means that we have learnt about the noise and
inaccuracies in the data as well as the actual function. Therefore, the model that we learn will be
much too complicated and won’t be able to generalise.
Figure shows this by plotting the predictions of some algorithm (as the curve) at two different
points in the learning process. On the left of the figure the curve fits the overall trend of the data well
(it has generalised to the underlying general function), but the training error would still not be that
close to zero since it passes near, but not through, the training data. As the network continues to learn,
it will eventually produce a much more complex model that has a lower training error (close to zero),
meaning that it has memorised the training examples, including any noise component of them, so that
is has overfitted the training data.
We want to stop the learning process before the algorithm overfits, which means that we need
to know how well it is generalising at each timestep. We can’t use the training data for this because we
wouldn’t detect overfitting, but we can’t use the testing data either, because we’re saving that for the
final tests. So we need a third set of data to use for this purpose, which is called the validation set
because we’re using it to validate the learning so far. This is known as cross-validation in statistics. It
is part of model selection: choosing the right parameters for the model so that it generalises as well as
possible.

5. Lasso Regression
Introduction
In this blog, we will see the techniques used to overcome overfitting for a lasso regression model.
Regularization is one of the methods widely used to make your model more generalized.

What is Lasso Regression?

Lasso regression is a regularization technique. It is used over regression methods for a more accurate
prediction. This model uses shrinkage. Shrinkage is where data values are shrunk towards a central
point as the mean. The lasso procedure encourages simple, sparse models (i.e. models with fewer
parameters). This particular type of regression is well-suited for models showing high levels of
multicollinearity or when you want to automate certain parts of model selection, like variable
selection/parameter elimination.

Lasso Regression uses L1 regularization technique (will be discussed later in this article). It is used
when we have more features because it automatically performs feature selection.

Lasso Meaning
The word “LASSO” stands for Least Absolute Shrinkage and Selection Operator. It is a statistical
formula for the regularisation of data models and feature selection.

Regularization
Regularization is an important concept that is used to avoid overfitting of the data, especially when the
trained and test data are much varying.

Regularization is implemented by adding a “penalty” term to the best fit derived from the trained data,
to achieve a lesser variance with the tested data and also restricts the influence of predictor variables
over the output variable by compressing their coefficients.

In regularization, what we do is normally we keep the same number of features but reduce the
magnitude of the coefficients. We can reduce the magnitude of the coefficients by using different
types of regression techniques which uses regularization to overcome this problem. So, let us discuss
them.

UNIT-II Page 11 of 43
Before we move further, you can also upskill with the help of online courses on Linear Regression in
Python and enhance your skills.

Lasso Regularization Techniques

There are two main regularization techniques, namely Ridge Regression and Lasso Regression. They
both differ in the way they assign a penalty to the coefficients. In this blog, we will try to understand
more about Lasso Regularization technique.
L1 Regularization
If a regression model uses the L1 Regularization technique, then it is called Lasso Regression.
If it used the L2 regularization technique, it’s called Ridge Regression. We will study more about
these in the later sections.
L1 regularization adds a penalty that is equal to the absolute value of the magnitude of the
coefficient. This regularization type can result in sparse models with few coefficients. Some
coefficients might become zero and get eliminated from the model. Larger penalties result in
coefficient values that are closer to zero (ideal for producing simpler models). On the other hand, L2
regularization does not result in any elimination of sparse models or coefficients. Thus, Lasso
Regression is easier to interpret as compared to the Ridge.

Mathematical equation of Lasso Regression

Residual Sum of Squares + λ * (Sum of the absolute value of the magnitude of coefficients)
• λ = 0 implies all features are considered and it
is equivalent to the linear regression where only
the residual sum of squares is considered to build
Where, a predictive model • λ = ∞ implies no feature is
considered i.e, as λ closes to infinity it eliminates
more and more features
• The bias increases with increase in λ
• λ denotes the amount of shrinkage. • variance increases with decrease in λ

6. Classification

UNIT-II Page 12 of 43
UNIT-II Page 13 of 43
7. Logistic Regression-

UNIT-II Page 14 of 43
UNIT-II Page 15 of 43
8. Gradient Linear Models

UNIT-II Page 16 of 43
9. Support Vector Machines
 UNIT-II Page 17 of 43

Machine learning involves predicting and classifying data and to do so we employ

various machine learning algorithms according to the dataset. SVM or Support Vector
Machine is a linear model for classification and regression problems. It can solve linear and
non-linear problems and work well for many practical problems. The idea of SVM is simple:
The algorithm creates a line or a hyperplane which separates the data into classes.
In this blog post I plan on offering a high-level overview of SVMs. I will talk about
the theory behind SVMs, it’s application for non-linearly separable datasets and a quick
example of implementation of SVMs in Python as well. In the upcoming articles I will
explore the maths behind the algorithm and dig under the hood.

THEORY
At first approximation what SVMs do is to find a separating line(or hyperplane)
between data of two classes. SVM is an algorithm that takes the data as an input and outputs a
line that separates those classes if possible. Lets begin with a problem. Suppose you have a
dataset as shown below and you need to classify the red rectangles from the blue ellipses(let’s
say positives from the negatives). So your task is to find an ideal line that separates this
dataset in two classes (say red and blue).

Not a big task, right? But, as you notice there isn’t a unique line that does the job. In fact, we
have an infinite lines that can separate these two classes. So how does SVM find the ideal
one??? Let’s take some probable candidates and figure it out ourselves.
 UNIT-II Page 18 of 43
We have two candidates here, the green colored line and the yellow colored line. Which line
according to you best separates the data?
If you selected the yellow line then congrats, because thats the line we are looking for. It’s
visually quite intuitive in this case that the yellow line classifies better. But, we need
something concrete to fix our line.
The green line in the image above is quite close to the red class. Though it classifies the
current datasets it is not a generalized line and in machine learning our goal is to get a more
generalized separator.

SVM’s way to find the best line

According to the SVM algorithm we find the points closest to the line from both the
[Link] points are called support vectors. Now, we compute the distance between the
line and the support vectors. This distance is called the margin. Our goal is to maximize the
margin. The hyperplane for which the margin is maximum is the optimal hyperplane.

Optimal Hyperplane using the SVM algorithm

Thus SVM tries to make a decision boundary in such a way that the separation
between the two classes(that street) is as wide as possible.
Simple, ain’t it? Let’s consider a bit complex dataset, which is not linearly separable.

Non-linearly separable data

This data is clearly not linearly separable. We cannot draw a straight line that can
classify this data. But, this data can be converted to linearly separable data in higher
dimension. Lets add one more dimension and call it z-axis. Let the co-ordinates on z-axis be
governed by the constraint,

UNIT-II Page 19 of 43
z = x²+y²
So, basically z co-ordinate is the square of distance of the point from origin. Let’s plot
the data on z-axis.

Dataset on higher dimension

Now the data is clearly linearly separable. Let the purple line separating the data in higher
dimension be z=k, where k is a constant. Since, z=x²+y² we get x² + y² = k; which is an
equation of a circle. So, we can project this linear separator in higher dimension back in
original dimensions using this transformation.

Decision boundary in original dimensions

Thus we can classify data by adding an extra dimension to it so that it becomes linearly
separable and then projecting the decision boundary back to original dimensions using
mathematical transformation. But finding the correct transformation for any given dataset isn’t
that easy. Thankfully, we can use kernels in sklearn’s SVM implementation to do this job.
 UNIT-II Page 20 of 43

[Link] Methods
UNIT-II Page 21 of 43
UNIT-II Page 22 of 43
 UNIT-II Page 23 of 43
[Link] based Methods
 UNIT-II Page 24 of 43
12.K-Nearest Neighbors
UNIT-II Page 25 of 43
UNIT-II Page 26 of 43
UNIT-II Page 27 of 43
 UNIT-II
Page 28 of 43
[Link] based Methods
Decision Trees

UNIT-II Page 29 of 43
UNIT-II Page 30 of 43
14. ID3

UNIT-II Page 31 of 43
UNIT-II Page 32 of 43
 UNIT-II Page 33 of 43
[Link]
UNIT-II Page 34 of 43
UNIT-II Page 35 of 43
 UNIT-II Page 36 of 43

[Link] Methods
UNIT-II Page 37 of 43
UNIT-II Page 38 of 43
UNIT-II Page 39 of 43