UNIT1-INTRODUCTION

Machine Learning – Types of Machine Learning –

Supervised Learning – Unsupervised Learning – Basic
Concepts in Machine Learning – Machine Learning
Process – Weight Space – Testing Machine Learning
Algorithms – A Brief Review of Probability Theory –
Turning Data into Probabilities – The Bias-Variance
Trade-off, FIND–S Algorithm, Candidate Elimination
Algorithm
What is 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.

Machine Learning is said as a subset of artificial intelligence that is mainly concerned

with the development of algorithms which allow a computer to learn from the data
and past experiences on their own. The term machine learning was first introduced
by Arthur Samuel in 1959. We can define it in a summarized way as:

Machine learning enables a machine to automatically learn from data, improve performance from
experiences, and predict things without being explicitly programmed.

With the help of sample historical data, which is known as training data, machine
learning algorithms build a mathematical model that helps in making predictions or
decisions without being explicitly programmed. Machine learning brings computer
science and statistics together for creating predictive models. Machine learning
constructs or uses the algorithms that learn from historical data. The more we will
provide the information, the higher will be the performance.

A machine has the ability to learn if it can improve its performance by gaining
more data.

How does Machine Learning work

A Machine Learning system learns from historical data, builds the prediction
models, and whenever it receives new data, predicts the output for it. The
accuracy of predicted output depends upon the amount of data, as the huge amount
of data helps to build a better model which predicts the output more accurately.

Suppose we have a complex problem, where we need to perform some predictions, so

instead of writing a code for it, we just need to feed the data to generic algorithms,
and with the help of these algorithms, machine builds the logic as per the data and
predict the output. Machine learning has changed our way of thinking about the
problem. The below block diagram explains the working of Machine Learning
algorithm:
Features of Machine Learning:
o Machine learning uses data to detect various patterns in a given dataset.
o It can learn from past data and improve automatically.
o It is a data-driven technology.
o Machine learning is much similar to data mining as it also deals with the huge amount
of the data.

Need for Machine Learning

The need for machine learning is increasing day by day. The reason behind the need
for machine learning is that it is capable of doing tasks that are too complex for a
person to implement directly. As a human, we have some limitations as we cannot
access the huge amount of data manually, so for this, we need some computer systems
and here comes the machine learning to make things easy for us.

We can train machine learning algorithms by providing them the huge amount of data
and let them explore the data, construct the models, and predict the required output
automatically. The performance of the machine learning algorithm depends on the
amount of data, and it can be determined by the cost function. With the help of
machine learning, we can save both time and money.

The importance of machine learning can be easily understood by its uses cases,
Currently, machine learning is used in self-driving cars, cyber fraud detection, face
recognition, and friend suggestion by Facebook, etc. Various top companies such
as Netflix and Amazon have build machine learning models that are using a vast
amount of data to analyze the user interest and recommend product accordingly.

Following are some key points which show the importance of Machine Learning:

o Rapid increment in the production of data

o Solving complex problems, which are difficult for a human
o Decision making in various sector including finance
 o Finding hidden patterns and extracting useful information from data.

CLASSIFICATION OF MACHINE LEARNING

At a broad level, machine learning can be classified into three types:

1. Supervised learning
2. Unsupervised learning
3. Reinforcement learning

1) Supervised Learning
Supervised learning is a type of machine learning method in which we provide sample
labeled data to the machine learning system in order to train it, and on that basis, it
predicts the output.

The system creates a model using labeled data to understand the datasets and learn
about each data, once the training and processing are done then we test the model
by providing a sample data to check whether it is predicting the exact output or not.

The goal of supervised learning is to map input data with the output data. The
supervised learning is based on supervision, and it is the same as when a student learns
things in the supervision of the teacher. The example of supervised learning is spam
filtering.

Supervised learning can be grouped further in two categories of algorithms:

 o Classification
o Regression

2) Unsupervised Learning
Unsupervised learning is a learning method in which a machine learns without any
supervision.

The training is provided to the machine with the set of data that has not been labeled,
classified, or categorized, and the algorithm needs to act on that data without any
supervision. The goal of unsupervised learning is to restructure the input data into new
features or a group of objects with similar patterns.

In unsupervised learning, we don't have a predetermined result. The machine tries to

find useful insights from the huge amount of data. It can be further classifieds into two
categories of algorithms:

o Clustering
o Density Estimation
o Dimensionality Reduction

3) Reinforcement Learning
Reinforcement learning is a feedback-based learning method, in which a learning
agent gets a reward for each right action and gets a penalty for each wrong action.
The agent learns automatically with these feedbacks and improves its performance. In
reinforcement learning, the agent interacts with the environment and explores it. The
goal of an agent is to get the most reward points, and hence, it improves its
performance.

The robotic dog, which automatically learns the movement of his arms, is an example
of Reinforcement learning.
APPLICATIONS OF MACHINE LEARNING
Machine learning is a buzzword for today's technology, and it is growing very rapidly day by
day. We are using machine learning in our daily life even without knowing it such as Google
Maps, Google assistant, Alexa, etc. Below are some most trending real-world applications of
Machine Learning:
Image Recognition: Image recognition is one of the most common applications of machine
learning. It is used to identify objects, persons, places, digital images, etc. The popular use case
of image recognition and face detection is, Automatic friend tagging suggestion:
Facebook provides us a feature of auto friend tagging suggestion. Whenever we upload a photo
with our Facebook friends, then we automatically get a tagging suggestion with name, and the
technology behind this is machine learning's face detection and recognition algorithm.
It is based on the Facebook project named "Deep Face," which is responsible for face
recognition and person identification in the picture.
Speech Recognition: 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.
Speech recognition is a process of converting voice instructions into text, and it is also known
as "Speech to text", or "Computer speech recognition." At present, machine learning algorithms
are widely used by various applications of speech recognition. Google assistant, Siri, Cortana,
and Alexa are using speech recognition technology to follow the voice instructions.
Traffic prediction: 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.
It predicts the traffic conditions such as whether traffic is cleared, slow-moving, or heavily
congested with the help of two ways:
o Real Time location of the vehicle form Google Map app and sensors
o Average time has taken on past days at the same time.
Everyone who is using Google Map is helping this app to make it better. It takes information
from the user and sends back to its database to improve the performance.
Product recommendations: Machine learning is widely used by various e-commerce and
entertainment companies such as Amazon, Netflix, etc., for product recommendation to the
user. Whenever we search for some product on Amazon, then we started getting an
advertisement for the same product while internet surfing on the same browser and this is
because of machine learning.
Google understands the user interest using various machine learning algorithms and suggests
the product as per customer interest.
As similar, when we use Netflix, we find some recommendations for entertainment series,
movies, etc., and this is also done with the help of machine learning.
Self-driving cars: One of the most exciting applications of machine learning is self-driving
cars. Machine learning plays a significant role in self-driving cars. Tesla, the most popular car
manufacturing company is working on self-driving car. It is using unsupervised learning
method to train the car models to detect people and objects while driving.
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. Below are some spam filters used by Gmail:
o Content Filter
o Header filter
o General blacklists filter
o Rules-based filters
o Permission filters
ISSUES IN MACHINE LEARNING.
a. Poor Quality of Data

Data plays a significant role in the machine learning process. One of the significant
issues that machine learning professionals face is the absence of good quality data. Unclean
and noisy data can make the whole process extremely exhausting. We don’t want our
algorithm to make inaccurate or faulty predictions. Hence the quality of data is essential to
enhance the output. Therefore, we need to ensure that the process of data preprocessing which
includes removing outliers, filtering missing values, and removing unwanted features, is done
with the utmost level of perfection.
b. Underfitting of Training Data

This process occurs when data is unable to establish an accurate relationship between
input and output variables. It simply means trying to fit in undersized jeans. It signifies the
data is too simple to establish a precise relationship. To overcome this issue:
 Maximize the training time
 Enhance the complexity of the model
 Add more features to the data
 Reduce regular parameters
 Increasing the training time of model
 c. Overfitting of Training Data

Overfitting refers to a machine learning model trained with a massive amount of data
that negatively affect its performance. It is like trying to fit in Oversized jeans. Unfortunately,
this is one of the significant issues faced by machine learning professionals. This means that
the algorithm is trained with noisy and biased data, which will affect its overall performance.
Let’s understand this with the help of an example. Let’s consider a model trained to
differentiate between a cat, a rabbit, a dog, and a tiger. The training data contains 1000 cats,
1000 dogs, 1000 tigers, and 4000 Rabbits. Then there is a considerable probability that it will
identify the cat as a rabbit. In this example, we had a vast amount of data, but it was biased;
hence the prediction was negatively affected.
It can be solved with:
 Analyzing the data with the utmost level of perfection
 Use data augmentation technique
 Remove outliers in the training set
 Select a model with lesser features
d. Machine Learning is a Complex Process

The machine learning industry is young and is continuously changing. Rapid hit and
trial experiments are being carried on. The process is transforming, and hence there are high
chances of error which makes the learning complex. It includes analyzing the data, removing
data bias, training data, applying complex mathematical calculations, and a lot more. Hence
it is a really complicated process which is another big challenge for Machine learning
professionals.
e. Lack of Training Data

The most important task you need to do in the machine learning process is to train the
data to achieve an accurate output. Less amount training data will produce inaccurate or too
biased predictions. A machine-learning algorithm needs a lot of data to distinguish. For
complex problems, it may even require millions of data to be trained. Therefore we need to
ensure that Machine learning algorithms are trained with sufficient amounts of data.
f. Slow Implementation
This is one of the common issues faced by machine learning professionals. The
machine learning models are highly efficient in providing accurate results, but it takes a
tremendous amount of time. Slow programs, data overload, and excessive requirements
usually take a lot of time to provide accurate results. Further, it requires constant monitoring
and maintenance to deliver the best output.
g. Imperfections in the Algorithm When Data Grows

So you have found quality data, trained it amazingly, and the predictions are really
concise and accurate. The best model of the present may become inaccurate in the coming
Future and require further rearrangement. So we need regular monitoring and maintenance to
keep the algorithm working. This is one of the most exhausting issues faced by machine
learning.
 MACHINE LEARNING WORKFLOW | PROCESS STEPS

We have discussed-
 Machine learning is building machines that can adapt and learn from experience.
 Machine learning systems are not explicitly programmed.

In this article, we will discuss machine learning workflow.

Machine Learning Workflow

Machine learning workflow refers to the series of stages or steps involved in the
process of building a successful machine learning system.

The various stages involved in the machine learning workflow are-

1. Data Collection
2. Data Preparation
3. Choosing Learning Algorithm
4. Training Model
5. Evaluating Model
6. Predictions

Let us discuss each stage one by one.

1. Data Collection-

In this stage,
 Data is collected from different sources.
 The type of data collected depends upon the type of desired project.
 Data may be collected from various sources such as files, databases etc.
 The quality and quantity of gathered data directly affects the accuracy of the desired
system.

2. Data Preparation-

In this stage,
 Data preparation is done to clean the raw data.
 Data collected from the real world is transformed to a clean dataset.
 Raw data may contain missing values, inconsistent values, duplicate instances etc.
 So, raw data cannot be directly used for building a model.

Different methods of cleaning the dataset are-

 Ignoring the missing values
 Removing instances having missing values from the dataset.
 Estimating the missing values of instances using mean, median or mode.
 Removing duplicate instances from the dataset.
 Normalizing the data in the dataset.

This is the most time consuming stage in machine learning workflow.

3. Choosing Learning Algorithm-

In this stage,
 The best performing learning algorithm is researched.
 It depends upon the type of problem that needs to solved and the type of data we have.
 If the problem is to classify and the data is labeled, classification algorithms are used.
 If the problem is to perform a regression task and the data is labeled, regression
algorithms are used.
 If the problem is to create clusters and the data is unlabeled, clustering algorithms are
used.

The following chart provides the overview of learning algorithms-

4. Training Model-

In this stage,
 The model is trained to improve its ability.
 The dataset is divided into training dataset and testing dataset.
 The training and testing split is order of 80/20 or 70/30.
 It also depends upon the size of the dataset.
 Training dataset is used for training purpose.
 Testing dataset is used for the testing purpose.
 Training dataset is fed to the learning algorithm.
 The learning algorithm finds a mapping between the input and the output and generates
the model.

5. Evaluating Model-

In this stage,
 The model is evaluated to test if the model is any good.
 The model is evaluated using the kept-aside testing dataset.
 It allows to test the model against data that has never been used before for training.
 Metrics such as accuracy, precision, recall etc are used to test the performance.
 If the model does not perform well, the model is re-built using different hyper parameters.
 The accuracy may be further improved by tuning the hyper parameters.

6. Predictions-

In this stage,
 The built system is finally used to do something useful in the real world.
 Here, the true value of machine learning is realized.
WEIGHT SPACE
TESTING MACHINE LEARNING
ALGORITHMS
TURNING DATA INTO
PROBABILITIES
 Preliminaries 2 7

P(X)

FIGURE 2.10 A histogram of feature values (r) against their probability for two classes

2.3 TURNING DATA INTO PROBABILITIES

Take a look at the plot in Figure 2.10. It shows the measurements of some feature : for
two classes, Ch and Ca. Members of class Cy teud to have larger values of ature r than
members of class C, but there is some overlap between the two classes. The correct class is
fairly easy to predict at the extremes of the rauge, but what to do in the middle is uuclear.
Suppose that we are trying to classify writiug of the letters 'a' and b' based on their height
(as shown in Figure 2.11). Must peojple write then a's sller thn their b s but 1ot
evervbody However, in this example, we lve secret weapon. We know that in Pnglish
text, the leiter a is mueh more common than the letter (we callel this t inalaee
ciataset earlior). lf we see a letter tlat is eitier an 'a or a b iu normal writing, then there
is a 75% chance that it is an a We are using prior knowledge, to estimate the probability
that the letter is an a': in this example, P(C1) == 0.75, P(C2) 0.25. If we weren't allowed
to see the letter at all, and just had to classify it, then if we picked a every tine, we d be
right 75% of the time
However, when we are asked to make a classification we are also given the value of .
It would be pretty silly to just use the value of P(C1) and ignore the value of a if it might
help! In fact. we are given a training set of valnes of and the class that cteh exenmpla
belongs to. This lets us calculate the value of P(C1) (we just count how nmany times out of
the total the class Was Ci and divide by tle total umber of examples), and also another
useful measurenent: tlhe conditional probability of C1 giveu that has value X: P(CX)
The conditional probability tells us how likelyit is that the class is Ci given that tlie ilue
of r is X. So in Figure 2.10 the value of P(C|X) will be much larger for s1mall values of X
than for large values. Clearly, this is exaetly what we want to calenkite in ornler to perlorn
classification. The question is how to get to this conditional probability., since we can't read
it direetly from tlhe histogum
The first thing that we need to do to 20t these values is to quantise the measurement
t, which just nieus that we put it iuto oue of a diserete set of valuesSA such as the
bins in a histogranm. This is exactly what is plotted in Figure 2.10. Now, if we have lots of
examples of the two classes, and the histogram bins that tlheir measureuents fall into, we
can compute P(C,, X,), wliiclh is the joint probability, and tells us how olteu a neasuremeut
of C; fell into histogram bin X,. We do lhisty looking in histogram bin X. countiug the
mumber of examples of class C that are in it, and diviling by the total mmber of oxamples
(of any elass)
We can also defiue P(X,IC). wlhiclh 1s a different conditional probability, and tells us

Jit Prbiltyrmeau ton On evetocun t dai

Grbr prbuhlty
28 \achine .eaming: An Algorithmic Perspeetive

FIGURE 2.11 The letters 'a and 'b' in pixel form.

how often (in the training set) there is a neasurement of X given that the example 1s a
member of class C. Again. we can just get this information from the
histogram by couting
the ummber of exauples of class C in histogram biu X, aud dividiug by the mumber of
Nples of that cass there are (in any bin). Flopefully, this has just been revision for
you from a statistics course at some stage; ii not, and you don't follow it, get hold of any
3troductory probability book.
So we have now worked out two things trom our training data: the
joint probability
PIC. X,and the conditional probability P C). Since we actually want to compute
PCA, we need to kuow how to liuk these iiings together. As some of you may already
know. the answer is Bayes rule, which is what we are now going to derive. There is a link
between the joint probability and the conditional probability. It is:

P(CN)PX,C)P(C), (2.10)
or equivalently:

PCX) PCX,)PX,) (2.11)

Clearly. the right-hand side of these two equations must be equal to each other, since
1hey are both equal to P(C,, A), and so witi one division we can write:

P(C: X,)PX,C)P(C;) oue Can P

Psbability bug t claus P(X)
This is Baves rule. If you don 1 alreadly kuow it, learm it: it is the moat
in n e i e learning. I relates the
important equation
posterior probability P(CA)with tie prior probability
PC) and class-conditional probability P'A,C). The denominator (the term on the bottom
of the fraction) acts to normalise everything, so that all the
not be clear how to compute this term.
probabilities sum to 1. It might
However, if we notice that any observation Xp has
to belong to some class i, then we can
marginalise over the classes to
(ht o eatuu compute:
ndituonoP PCNC)PC) AD ften
(2.13)g6 IN
I
a p p e a iK
L e a c h clovss
OUs t s a i n i n g s e
Pato
PlCi)=PCjlc).pCC;
A
Peta ass
PRohabilTy

Po&L&ioh
PC ormal1L
atl pao
Sum to 1
PRedICtoa PRio PR0L
 Preliminaries 29

PClx)

FIGURE 2.12 The posterior probabilities of the two classes C and C2 for feature .

The reason why Bayes rule is so inportant is that it lets us obtain the posterior
probability-which is what we actually want-by calculating things that are much eas-
ier to compute. VWe can estimate the prior probabilities by looking at how oftern each class
appears in our training set, and we can get the class-conditional probabilities from the his-
togram of the values of the feature for tlhe training set. We can use the posterior probability
(Figure 2.12) to assign each new observation to one of the classes by picking tlie class
where:

PC;x)> P(C;|x) Yi/j. (2.14

where x is a vector of feature valiies insteadd of just on feature. This is known as the
maximum a posteriori or MAP hypothesis, and it gives us a way to choose which class to
choose as the output one. The question is whether this is the right thing to do. There has
been quite a lot of research in both the statistical and niachine learning literatures into
what is the right question to ask about our data to
perform classihication, but we are going
to skate Over it very lightly.
The MAP question is what is the most likely class given the training data? Suppose that
there are three possible output classes, and tor a particular input the
posterior probabilities
of the classes are P(Ci|x)= 0.35, P(C2 x)=0.45, P(C3x) = 0.2. The MAP hypothesis
therefore tells us that this input is in class C2, because that is the class with tle
higlest
posterior probability. Now suppOse that, based on the class that the data is in. ve want
to do something. If the class is C1 or C% then we do action 1. and if the class is C then
we do action 2. As an example, suppose that the inputs are the results of a blood test,
the three classes are different possible diseases, and the output is whether or not to treat
with a particular antibiotic. The MAP metlhod has told us that the output is C2, and so
we will ot treat
the discas. But wliat is the Drobabilit that it does uot eloug to ass
C2. and so should lhave been treated witlh tlhe autibiotic? It is P(C)0.55. So the
MAP prediction socnis to be wroug: we slhouikl treat witli untibiotC. because
more likely. This nethod where we take into account the final
Overal it 1s
outcomes of all of the classes
is called the Bayes Optimal Classification. lt ninimises the
probability of uisclassilication
rather than maximising the posterior probability.
 30 Machine Learming: An Algorithmie Perspective

2:3.1 Minimising Risk

ln the medicnl example we just sAW it Ade sense to classily based on minimising the
probability of mielaseification, We Can also (onsider the risk that is involved in the mis-
clasilicalion Tho risk from miselasilying oieone as ihealthy when they are healthy is
usually smaller than the other way aromd, but nof necessarily always: there are plenty
of treatmneuts that have naxty wide offect, nd yol would1't want to suffer from those if
Or didhu ave 1lie diseaNC Tn caN 1ike fis we c Creat n loss matrix tliat specifies the
risk involved in classifying an example of clas C as class C. It looks like the confusion
matrix we saw in Section 2.2, except that a loss matrix
always contains eros on the leading
diagonal since there should never be a lows fro1 getting the classification correct! Once we
have the loss matrix, we just extend our classifier to minimise risk by multiplying each case
by tie 1elevant loss mber.

2.3.2 The Naive Bayes' Classifier

Were now going fo retrn to performing classification, without worrying about the ont
comes, so that we are back to caleulating the MAP outcome, Equation (2.14). We can
conputo this exaetly as deseribed albove, d it will work fine, However, suppose that
the vector of feature values had nany elerIents, so that there were lots of different fea
Tures that were 11easurcd. How would this ffeet the classifier We are trying to etinate
P(X, C)P(X, X X|C;) (where tlhe superscripts index the elements of the vector)
bylooking at the histograni of all of our traiing data. As the dimensionality of X increases
(s ets larger). the amonyf of data in each hith of the histogram shrinks. This is the curse
of dimensionality again
(Section 2.1.2), and ineaiis that we need 1nuch more data as the
dimensionality increases.
There is one simplifying assuuption that we can make. We can assume that the
elemeuts
of tlie feature vector are couditionally
indepencdent of eacl1 other, given the classification. So
e the class C t e valiues of thc differep featurcs do not affect cach other. This is inc
naiveté in the nane of the classifier, since it ofter: doesn't make much
the features are independent of each other. if we were to
sense it tells us that
try to classify coins it would say
that the weight and the diameter of the coin are independent of each
isn't tre lowever. it does nmean that fhe
other, which clearly
[Link] of getting the string of feature values
PX a1. X a2, X aCi) is just cqual to the product of multiplying together
all of the individual probabilities:

PXa|C,) P(Xa C)x x

P(X= an C)=||PXa C), (2.15)
wehich is e h casier to conpute, and rednces flie
severity of the curse of dimensionality.
So the classifier rule for the naive Bayes' cliassifier is to select the
class C for which the
following computation is the maximum:

PC)|POXa,C). (2.16)
This is clearly a great simplification over evaluating
the full probability, so it
as a surprise
that the naive Bayes classifier has been shown to might come
have comparable results to
other classification methods in certain
domais. Where the simplilication is true, so that
the leatues Are coiditionally
indepedent of each otlier, the naive Bayes classilier produces
exactly the MAP classification
THE BIAS-VARIANCE TRADEOFF
 Bias Vs Variance

uS
u s aa b
boou
ut h ou
u wel
c ell
varnance Letly
S and
during 7raining 2 festina
Our per-forms
C algorithm

Side bf Home 3
Sze o f Home

Si e o Hame
tOratO22
polynomial
)
o-f m g h v a r i a n c e

Cdegree,

High bias Lgenera tized Cover frLJ

modet
(72aining> accu racy
Cunder-fit) ue ma
Tesng not get
Sum of ccuracy

Trainin error:
4he
am
get)
CPrediceð
oP
) a .error

[Link]
sampes
22
Mcv
Cross validation

error
8mcv 1E
CTesing error )

Underfi t
bias
High
esina Training Testina
e r r o r

ill be hiah.
error
v a r i a n C e

Hgh Variance Overfi

bias
Trainng error 5low
Tvaining
error
* Testirg error Verthigh.
d1 d d-3
degree o polynomia
 d i f f ererd pa
rw as
seon
ns

bad for dif( ererd

mede an b
A
w
weetl '
malch
accuraie
doesn'
no
J
bias
af variati on
not
hot very precise & o

variance"

E C- h(*))'| noie voriance 4 bios

CONCEPT LEARNING AS SEARCH ( Introduction)

 Concept learning can be viewed as the task of searching through a large space of
hypotheses implicitly defined by the hypothesis representation.
 The goal of this search is to find the hypothesis that best fits the training examples.

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

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

General-to-Specific Ordering of Hypotheses

Consider the two hypotheses

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

 Consider the sets of instances that are classified positive by hl and by h2.
 h2 imposes fewer constraints on the instance, it classifies more instances as positive. So,any
instance classified positive by hl will also be classified positive by h2. Therefore, h2 is more
general than hl.

Given hypotheses hj and hk, hj is more-general-than or- equal do hk if and only if any instancethat
satisfies hk also satisfies hi

Definition: Let hj and hk be Boolean-valued functions defined over X. Then hj is more general-than-
or-equal-to hk (written hj ≥ hk) if and only if

) [(hk (x) = 1) → (hj (x) = 1)]

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

FIND-S: FINDING A MAXIMALLY SPECIFIC HYPOTHESIS

FIND-S Algorithm

1. Initialize h to the most specific hypothesis in H

2. For each positive training instance x
For each attribute constraint a in h
i
If the constraint a is satisfied by x
i
Then do nothing
Else replace a in h by the next more general constraint that is satisfied by x
i
3. Output hypothesis h
To illustrate this algorithm, assume the learner is given the sequence of training examplesfrom
the EnjoySport task

Example Sky AirTemp Humidity Wind Wate Forecast EnjoySpor

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

 The first step of FIND-S is to initialize h to the most specific hypothesis in H

h - (Ø, Ø, Ø, Ø, Ø, Ø)

 Consider the first training example

x1 = <Sunny Warm Normal Strong Warm Same>, +

Observing the first training example, it is clear that hypothesis h is too specific. None of the
"Ø" constraints in h are satisfied by this example, so each is replaced by the nextmore general
constraint that fits the example
h1 = <Sunny Warm Normal Strong Warm Same>

 Consider the second training example

x2 = <Sunny, Warm, High, Strong, Warm, Same>, +

The second training example forces the algorithm to further generalize h, this time
substituting a "?" in place of any attribute value in h that is not satisfied by the newexample
h2 = <Sunny Warm ? Strong Warm Same>

 Consider the third training example

x3 = <Rainy, Cold, High, Strong, Warm, Change>, -

Upon encountering the third training the algorithm makes no change to h. The FIND-S
algorithm simply ignores every negative example.
h3 = < Sunny Warm ? Strong Warm Same>

 Consider the fourth training example

x4 = <Sunny Warm High Strong Cool Change>, +

The fourth example leads to a further generalization of h

h4 = < Sunny Warm ? Strong ? ? >
The key property of the FIND-S algorithm
 FIND-S is guaranteed to output the most specific hypothesis within H that is consistentwith the
positive training examples
 FIND-S algorithm’s final hypothesis will also be consistent with the negative examplesprovided
the correct target concept is contained in H, and provided the training examplesare correct.

Unanswered by FIND-S

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

2. Why prefer the most specific hypothesis?
3. Are the training examples consistent?
4. What if there are several maximally specific consistent hypotheses?
 VERSION SPACES AND THE CANDIDATE-ELIMINATION ALGORITHM

The key idea in the CANDIDATE-ELIMINATION algorithm is to output a description of theset of all
hypotheses consistent with the training examples

Representation

Definition: consistent- A hypothesis h is consistent with a set of training examples D if and

only if h(x) = c(x) for each example (x, c(x)) in D.

Consistent (h, D x, c(x D) h(x) = c(x))

Note difference between definitions of consistent and satisfies

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

Definition: version space- The version space, denoted V S with respect to hypothesis space
H, D
H and training examples D, is the subset of hypotheses from H consistent with the training
examples in D
VS h H | Consistent (h, D)}
H, D

List-Then-Eliminate algorithm

Steps in List-Then-Eliminate Algorithm

1. VersionSpace = a list containing every hypothesis in H

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

Example1 :

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

Example2 :

Version Space: (A, X), (A, Y), (A, ?), (B, X), (B, Y), (B, ?), (?, X), (?, Y) (?, ?), (ø, ø), •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

CANDIDATE-ELIMINATION LEARNING ALGORITHM

The CANDIDATE-ELIMINTION algorithm computes the version space containing allhypotheses

from H that are consistent with an observed sequence of training examples.

Initialize G to the set of maximally general hypotheses in H

Initialize S to the set of maximally specific hypotheses in HFor
each training example d, do
• If d is a positive example
• Remove from G any hypothesis inconsistent with d
• For each hypothesis s in S that is not consistent with d
• Remove s from S
• Add to S all minimal generalizations h of s such that
• h is consistent with d, and some member of G is more general than h
 • Remove from S any hypothesis that is more general than another hypothesis in S

• If d is a negative example
• Remove from S any hypothesis inconsistent with d
• For each hypothesis g in G that is not consistent with d
• Remove g from G
• Add to G all minimal specializations h of g such that
• h is consistent with d, and some member of S is more specific than h
• Remove from G any hypothesis that is less general than another hypothesis in G

CANDIDATE- ELIMINTION algorithm using version spaces

An Illustrative Example

Example Sky AirTemp Humidity Wind Wate Forecast EnjoySpor

r t
1 Sunny Warm Normal Strong Warm Same Yes
2 Sunny Warm High Strong Warm Same Yes
3 Rainy Cold High Strong Warm Change No
4 Sunny Warm High Strong Cool Change Yes
CANDIDATE-ELIMINTION algorithm begins by initializing the version space to the set ofall
hypotheses in H;

Initializing the G boundary set to contain the most general hypothesis in H

G0 ?, ?, ?,

Initializing the S boundary set to contain the most specific (least general) hypothesis
S0

 When the first training example is presented, the CANDIDATE-ELIMINTION algorithm checks
the S boundary and finds that it is overly specific and it fails to cover the positive example.
 The boundary is therefore revised by moving it to the least more general hypothesis that covers this
new example
 No update of the G boundary is needed in response to this training example because G o correctly
covers this example
 When the second training example is observed, it has a similar effect of generalizing Sfurther
to S2, leaving G again unchanged i.e., G2 = G1 = G0

 Consider the third training example. This negative example reveals that the G boundaryof the
version space is overly general, that is, the hypothesis in G incorrectly predicts that this new
example is a positive example.
 The hypothesis in the G boundary must therefore be specialized until it correctly classifies this
new negative example
Given that there are six attributes that could be specified to specialize G2, why are there only three new
hypotheses in G3?
For example, the hypothesis h = (?, ?, Normal, ?, ?, ?) is a minimal specialization of G 2 that
correctly labels the new example as a negative example, but it is not included in [Link] reason
this hypothesis is excluded is that it is inconsistent with the previously encountered positive
examples

 Consider the fourth training example.

 This positive example further generalizes the S boundary of the version space. It alsoresults
in removing one member of the G boundary, because this member fails to cover the new
positive example

After processing these four examples, the boundary sets S4 and G4 delimit the version spaceof all
hypotheses consistent with the set of incrementally observed training examples.
BASIC CONCEPTS IN MACHINE LEARNING

Parametric vs non-parametric models

We will be focussing on probabilistic models of the form p(y|x) or p(x), depending on whether we are
interested in supervised or unsupervised learning respectively. There are many ways to define such
models, but the most important distinction is this: does the model have a fixed number of parameters, or
does the number of parameters g

row with the amount of training data? The former is called a parametric model, and the latter is called a
nonparametric model. Parametric models have the advantage of often being faster to use, but the
disadvantage of making stronger assumptions about the nature of the data distributions. Nonparametric
models are more flexible, but often computationally intractable for large datasets.

A simple non-parametric classifier: K-nearest neighbors

o K-Nearest Neighbour is one of the simplest Machine Learning algorithms based on Supervised
Learning technique.
o K-NN algorithm assumes the similarity between the new case/data and available cases and put the
new case into the category that is most similar to the available categories.
o K-NN algorithm stores all the available data and classifies a new data point based on the
similarity. This means when new data appears then it can be easily classified into a well suite
category by using K- NN algorithm.
o K-NN algorithm can be used for Regression as well as for Classification but mostly it is used for
the Classification problems.
o K-NN is a non-parametric algorithm, which means it does not make any assumption on
underlying data.
o It is also called a lazy learner algorithm because it does not learn from the training set
immediately instead it stores the dataset and at the time of classification, it performs an action on
the dataset.
o KNN algorithm at the training phase just stores the dataset and when it gets new data, then it
classifies that data into a category that is much similar to the new data.
o Example: Suppose, we have an image of a creature that looks similar to cat and dog, but we want
to know either it is a cat or dog. So for this identification, we can use the KNN algorithm, as it
works on a similarity measure. Our KNN model will find the similar features of the new data set
to the cats and dogs images and based on the most similar features it will put it in either cat or
dog category.

The curse of dimensionality

The KNN classifier is simple and can work quite well, provided it is given a good distance metric and has
enough labeled training data. In fact, it can be shown that the KNN classifier can come within a factor of
2 of the best possible performance if N → ∞ (Cover and Hart 1967). However, the main problem with
KNN classifiers is that they do not work well with high dimensional inputs. The poor performance in high
dimensional settings is due to the curse of dimensionality.
Curse of Dimensionality refers to a set of problems that arise when working with high-dimensional data.
The dimension of a dataset corresponds to the number of attributes/features that exist in a dataset. A
dataset with a large number of attributes, generally of the order of a hundred or more, is referred to as
high dimensional data. Some of the difficulties that come with high dimensional data manifest during
analyzing or visualizing the data to identify patterns, and some manifest while training machine learning
models. The difficulties related to training machine learning models due to high dimensional data is
referred to as ‘Curse of Dimensionality’

Parametric models for classification and regression

The main way to combat the curse of dimensionality is to make some assumptions about the nature of the
data distribution (either p(y|x) for a supervised problem or p(x) for an unsupervised problem). These
assumptions, known as inductive bias, are often embodied in the form of a parametric model, which is a
statistical model with a fixed number of parameters.

Linear regression

Linear Regression is an algorithm that belongs to supervised Machine Learning. It tries to apply relations
that will predict the outcome of an event based on the independent variable data points. The relation is
usually a straight line that best fits the different data points as close as possible. The output is of a
continuous form, i.e., numerical value. For example, the output could be revenue or sales in currency, the
number of products sold, etc. In the above example, the independent variable can be single or multiple.

1. Linear Regression Equation

Linear Regression Line

Linear regression can be expressed mathematically as:

y= β0+ β 1x+ ε

Here,
  Y= Dependent Variable
 X= Independent Variable
 β 0= intercept of the line
 β1 = Linear regression coefficient (slope of the line)
 ε = random error
The last parameter, random error ε, is required as the best fit line also doesn't include the data points
perfectly.

2. Linear Regression Model

Since the Linear Regression algorithm represents a linear relationship between a dependent (y) and one or
more independent (y) variables, it is known as Linear Regression. This means it finds how the value of
the dependent variable changes according to the change in the value of the independent variable. The
relation between independent and dependent variables is a straight line with a slope.

Types of Linear Regression

Linear Regression can be broadly classified into two types of algorithms:

1. Simple Linear Regression

A simple straight-line equation involving slope (dy/dx) and intercept (an integer/continuous value) is
utilized in simple Linear Regression. Here a simple form is:

y=mx+c where y denotes the output x is the independent variable, and c is the intercept when x=0. With
this equation, the algorithm trains the model of machine learning and gives the most accurate output

2. Multiple Linear Regression

When a number of independent variables more than one, the governing linear equation applicable to
regression takes a different form like:

y= c+m1x1+m2x2… mnxn where represents the coefficient responsible for impact of different
independent variables x1, x2 etc. This machine learning algorithm, when applied, finds the values of
coefficients m1, m2, etc., and gives the best fitting line.

3. Non-Linear Regression

When the best fitting line is not a straight line but a curve, it is referred to as Non-Linear Regression.

Logistic regression

o Logistic regression is one of the most popular Machine Learning algorithms, which comes under
the Supervised Learning technique. It is used for predicting the categorical dependent variable
using a given set of independent variables.
 o Logistic regression predicts the output of a categorical dependent variable. Therefore the outcome
must be a categorical or discrete value. It can be either Yes or No, 0 or 1, true or False, etc. but
instead of giving the exact value as 0 and 1, it gives the probabilistic values which lie between 0
and 1.
o Logistic Regression is much similar to the Linear Regression except that how they are used.
Linear Regression is used for solving Regression problems, whereas Logistic regression is used
for solving the classification problems.
o In Logistic regression, instead of fitting a regression line, we fit an "S" shaped logistic function,
which predicts two maximum values (0 or 1).
o The curve from the logistic function indicates the likelihood of something such as whether the
cells are cancerous or not, a mouse is obese or not based on its weight, etc.
o Logistic Regression is a significant machine learning algorithm because it has the ability to
provide probabilities and classify new data using continuous and discrete datasets.
o Logistic Regression can be used to classify the observations using different types of data and can
easily determine the most effective variables used for the classification. The below image is
showing the logistic function:

Overfitting

Overfitting occurs when our machine learning model tries to cover all the data points or more than the
required data points present in the given dataset. Because of this, the model starts caching noise and
inaccurate values present in the dataset, and all these factors reduce the efficiency and accuracy of the
model. The overfitted model has low bias and high variance.
The chances of occurrence of overfitting increase as much we provide training to our model. It means the
more we train our model, the more chances of occurring the overfitted model.

Overfitting is the main problem that occurs in supervised learning.

Example: The concept of the overfitting can be understood by the below graph of the linear regression
output:

As we can see from the above graph, the model tries to cover all the data points present in the scatter plot.
It may look efficient, but in reality, it is not so. Because the goal of the regression model to find the best
fit line, but here we have not got any best fit, so, it will generate the prediction errors.

How to avoid the Overfitting in Model :

Both overfitting and underfitting cause the degraded performance of the machine learning model. But the
main cause is overfitting, so there are some ways by which we can reduce the occurrence of overfitting in
our model.

 Cross-Validation
 Training with more data
 Removing features
 Early stopping the training
 Regularization
 Ensembling

Model selection

Model selection is the process of selecting one final machine learning model from among a collection of
candidate machine learning models for a training dataset.
Model selection is a process that can be applied both across different types of models (e.g. logistic
regression, SVM, KNN, etc.) and across models of the same type configured with different model
hyperparameters (e.g. different kernels in an SVM).

When we have a variety of models of different complexity (e.g., linear or logistic regression models with
different degree polynomials, or KNN classifiers with different values of K), how should we pick the right
one?

For example, we may have a dataset for which we are interested in developing a classification or
regression predictive model. We do not know beforehand as to which model will perform best on this
problem, as it is unknowable. Therefore, we fit and evaluate a suite of different models on the problem.

Model selection is the process of choosing one of the models as the final model that addresses the
problem.
Model selection is different from model assessment.
For example, we evaluate or assess candidate models in order to choose the best one, and this is model
selection. Whereas once a model is chosen, it can be evaluated in order to communicate how well it is
expected to perform in general; this is model assessment.

No free lunch theorem

The No Free Lunch Theorem is often used in optimization and machine learning, with little
comprehension of what it means or implies.
The theory asserts that when the performance of all optimization methods is averaged across all
conceivable problems, they all perform equally well. It indicates that no one optimum optimization
algorithm exists. Because of the strong link between optimization, search, and machine learning, there is
no one optimum machine learning method for predictive modelling tasks like classification and
regression.
They all agree on one point: there is no “best” algorithm for specific kinds of algorithms, since they all
perform similarly on average. Mathematically, the computing cost of finding a solution is the same for
any solution technique when averaged across all problems in the class. As a result, no solution provides a
shortcut.
According to the “No Free Lunch” theory, there is no one model that works best for every situation.
Because the assumptions of a great model for one issue may not hold true for another, it is typical in
machine learning to attempt many models to discover the one that performs best for a specific problem.
This is especially true in supervised learning, where validation or cross-validation is frequently used to
compare the prediction accuracy of many models of various complexity in order to select the optimal
model. A good model may also be trained using several methods — for example, linear regression can be
learned using normal equations or gradient descent.
 UNIT 2- SUPERVISED LEARNING
Linear Models for Regression – Linear Basis Function Models –
The Bias-Variance Decomposition – Bayesian Linear
Regression – Common Regression Algorithms – Simple Linear
Regression – Multiple Linear Regression – Linear Models for
Classification – Discriminant Functions – Probabilistic
Generative Models – Probabilistic Discriminative Models –
Laplace Approximation – Bayesian Logistic Regression –
Common Classification Algorithms – k-Nearest Neighbors –
Decision Trees – Random Forest model – Support Vector
Machines
 3
Linear
Models for
Regression

The focus so far in this book has been on unsupervised learning, including topics
such as density estimation and data clustering. We turn now to a discussion of super-
vised learning, starting with regression. The goal of regression is to predict the value
of one or more continuous target variables t given the value of a D-dimensional vec-
tor x of input variables. We have already encountered an example of a regression
problem when we considered polynomial curve fitting in Chapter 1. The polynomial
is a specific example of a broad class of functions called linear regression models,
which share the property of being linear functions of the adjustable parameters, and
which will form the focus of this chapter. The simplest form of linear regression
models are also linear functions of the input variables. However, we can obtain a
much more useful class of functions by taking linear combinations of a fixed set of
nonlinear functions of the input variables, known as basis functions. Such models
are linear functions of the parameters, which gives them simple analytical properties,
and yet can be nonlinear with respect to the input variables.

137
138 3. LINEAR MODELS FOR REGRESSION

Given a training data set comprising N observations {xn }, where n = 1, . . . , N ,

together with corresponding target values {tn }, the goal is to predict the value of t
for a new value of x. In the simplest approach, this can be done by directly con-
structing an appropriate function y(x) whose values for new inputs x constitute the
predictions for the corresponding values of t. More generally, from a probabilistic
perspective, we aim to model the predictive distribution p(t|x) because this expresses
our uncertainty about the value of t for each value of x. From this conditional dis-
tribution we can make predictions of t, for any new value of x, in such a way as to
minimize the expected value of a suitably chosen loss function. As discussed in Sec-
tion 1.5.5, a common choice of loss function for real-valued variables is the squared
loss, for which the optimal solution is given by the conditional expectation of t.
Although linear models have significant limitations as practical techniques for
pattern recognition, particularly for problems involving input spaces of high dimen-
sionality, they have nice analytical properties and form the foundation for more so-
phisticated models to be discussed in later chapters.

3.1. Linear Basis Function Models

The simplest linear model for regression is one that involves a linear combination of
the input variables

y(x, w) = w0 + w1 x1 + . . . + wD xD (3.1)

where x = (x1 , . . . , xD )T . This is often simply known as linear regression. The key
property of this model is that it is a linear function of the parameters w0 , . . . , wD . It is
also, however, a linear function of the input variables xi , and this imposes significant
limitations on the model. We therefore extend the class of models by considering
linear combinations of fixed nonlinear functions of the input variables, of the form


M −1
y(x, w) = w0 + wj φj (x) (3.2)
j =1

where φj (x) are known as basis functions. By denoting the maximum value of the
index j by M − 1, the total number of parameters in this model will be M .
The parameter w0 allows for any fixed offset in the data and is sometimes called
a bias parameter (not to be confused with ‘bias’ in a statistical sense). It is often
convenient to define an additional dummy ‘basis function’ φ0 (x) = 1 so that


M −1
y(x, w) = wj φj (x) = wT φ(x) (3.3)
j =0

where w = (w0 , . . . , wM −1 )T and φ = (φ0 , . . . , φM −1 )T . In many practical ap-

plications of pattern recognition, we will apply some form of fixed pre-processing,
 3.1. Linear Basis Function Models 139

or feature extraction, to the original data variables. If the original variables com-
prise the vector x, then the features can be expressed in terms of the basis functions
{φj (x)}.
By using nonlinear basis functions, we allow the function y(x, w) to be a non-
linear function of the input vector x. Functions of the form (3.2) are called linear
models, however, because this function is linear in w. It is this linearity in the pa-
rameters that will greatly simplify the analysis of this class of models. However, it
also leads to some significant limitations, as we discuss in Section 3.6.
The example of polynomial regression considered in Chapter 1 is a particular
example of this model in which there is a single input variable x, and the basis func-
tions take the form of powers of x so that φj (x) = xj . One limitation of polynomial
basis functions is that they are global functions of the input variable, so that changes
in one region of input space affect all other regions. This can be resolved by dividing
the input space up into regions and fit a different polynomial in each region, leading
to spline functions (Hastie et al., 2001).
There are many other possible choices for the basis functions, for example

(x − µj )2
φj (x) = exp − (3.4)
2s2

where the µj govern the locations of the basis functions in input space, and the pa-
rameter s governs their spatial scale. These are usually referred to as ‘Gaussian’
basis functions, although it should be noted that they are not required to have a prob-
abilistic interpretation, and in particular the normalization coefficient is unimportant
because these basis functions will be multiplied by adaptive parameters wj .
Another possibility is the sigmoidal basis function of the form
x − µ 
j
φj (x) = σ (3.5)
s
where σ(a) is the logistic sigmoid function defined by
1
σ(a) = . (3.6)
1 + exp(−a)
Equivalently, we can use the ‘tanh’ function because this is related to the logistic
sigmoid by tanh(a) = 2σ(a) − 1, and so a general linear combination of logistic
sigmoid functions is equivalent to a general linear combination of ‘tanh’ functions.
These various choices of basis function are illustrated in Figure 3.1.
Yet another possible choice of basis function is the Fourier basis, which leads to
an expansion in sinusoidal functions. Each basis function represents a specific fre-
quency and has infinite spatial extent. By contrast, basis functions that are localized
to finite regions of input space necessarily comprise a spectrum of different spatial
frequencies. In many signal processing applications, it is of interest to consider ba-
sis functions that are localized in both space and frequency, leading to a class of
functions known as wavelets. These are also defined to be mutually orthogonal, to
simplify their application. Wavelets are most applicable when the input values live
140 3. LINEAR MODELS FOR REGRESSION

1 1 1

0.5 0.75 0.75

0 0.5 0.5

−0.5 0.25 0.25

−1 0 0
−1 0 1 −1 0 1 −1 0 1
Figure 3.1 Examples of basis functions, showing polynomials on the left, Gaussians of the form (3.4) in the
centre, and sigmoidal of the form (3.5) on the right.

on a regular lattice, such as the successive time points in a temporal sequence, or the
pixels in an image. Useful texts on wavelets include Ogden (1997), Mallat (1999),
and Vidakovic (1999).
Most of the discussion in this chapter, however, is independent of the particular
choice of basis function set, and so for most of our discussion we shall not specify
the particular form of the basis functions, except for the purposes of numerical il-
lustration. Indeed, much of our discussion will be equally applicable to the situation
in which the vector φ(x) of basis functions is simply the identity φ(x) = x. Fur-
thermore, in order to keep the notation simple, we shall focus on the case of a single
target variable t. However, in Section 3.1.5, we consider briefly the modifications
needed to deal with multiple target variables.

3.1.1 Maximum likelihood and least squares

In Chapter 1, we fitted polynomial functions to data sets by minimizing a sum-
of-squares error function. We also showed that this error function could be motivated
as the maximum likelihood solution under an assumed Gaussian noise model. Let
us return to this discussion and consider the least squares approach, and its relation
to maximum likelihood, in more detail.
As before, we assume that the target variable t is given by a deterministic func-
tion y(x, w) with additive Gaussian noise so that

t = y(x, w) +  (3.7)

where  is a zero mean Gaussian random variable with precision (inverse variance)
β. Thus we can write

p(t|x, w, β) = N (t|y(x, w), β −1 ). (3.8)

Recall that, if we assume a squared loss function, then the optimal prediction, for a
Section 1.5.5 new value of x, will be given by the conditional mean of the target variable. In the
case of a Gaussian conditional distribution of the form (3.8), the conditional mean
 3.1. Linear Basis Function Models 141

will be simply 
E[t|x] = tp(t|x) dt = y(x, w). (3.9)

Note that the Gaussian noise assumption implies that the conditional distribution of
t given x is unimodal, which may be inappropriate for some applications. An ex-
tension to mixtures of conditional Gaussian distributions, which permit multimodal
conditional distributions, will be discussed in Section 14.5.1.
Now consider a data set of inputs X = {x1 , . . . , xN } with corresponding target
values t1 , . . . , tN . We group the target variables {tn } into a column vector that we
denote by t where the typeface is chosen to distinguish it from a single observation
of a multivariate target, which would be denoted t. Making the assumption that
these data points are drawn independently from the distribution (3.8), we obtain the
following expression for the likelihood function, which is a function of the adjustable
parameters w and β, in the form


N
p(t|X, w, β) = N (tn |wT φ(xn ), β −1 ) (3.10)
n=1

where we have used (3.3). Note that in supervised learning problems such as regres-
sion (and classification), we are not seeking to model the distribution of the input
variables. Thus x will always appear in the set of conditioning variables, and so
from now on we will drop the explicit x from expressions such as p(t|x, w, β) in or-
der to keep the notation uncluttered. Taking the logarithm of the likelihood function,
and making use of the standard form (1.46) for the univariate Gaussian, we have


N
ln p(t|w, β) = ln N (tn |wT φ(xn ), β −1 )
n=1
N N
= ln β − ln(2π) − βED (w) (3.11)
2 2
where the sum-of-squares error function is defined by

1
N
ED (w) = {tn − wT φ(xn )}2 . (3.12)
2
n=1

Having written down the likelihood function, we can use maximum likelihood to
determine w and β. Consider first the maximization with respect to w. As observed
already in Section 1.2.5, we see that maximization of the likelihood function under a
conditional Gaussian noise distribution for a linear model is equivalent to minimizing
a sum-of-squares error function given by ED (w). The gradient of the log likelihood
function (3.11) takes the form


N
 
∇ ln p(t|w, β) = tn − wT φ(xn ) φ(xn )T . (3.13)
n=1
142 3. LINEAR MODELS FOR REGRESSION

Setting this gradient to zero gives

N 

N 
0= tn φ(xn ) − w
T T
φ(xn )φ(xn )T
. (3.14)
n=1 n=1

Solving for w we obtain

−1
wML = ΦT Φ ΦT t (3.15)
which are known as the normal equations for the least squares problem. Here Φ is an
N ×M matrix, called the design matrix, whose elements are given by Φnj = φj (xn ),
so that ⎛ ⎞
φ0 (x1 ) φ1 (x1 ) · · · φM −1 (x1 )
⎜ φ0 (x2 ) φ1 (x2 ) · · · φM −1 (x2 ) ⎟
Φ=⎜ ⎝ .. .. .. .. ⎟.
⎠ (3.16)
. . . .
φ0 (xN ) φ1 (xN ) · · · φM −1 (xN )
The quantity
−1
Φ† ≡ ΦT Φ ΦT (3.17)
is known as the Moore-Penrose pseudo-inverse of the matrix Φ (Rao and Mitra,
1971; Golub and Van Loan, 1996). It can be regarded as a generalization of the
notion of matrix inverse to nonsquare matrices. Indeed, if Φ is square and invertible,
then using the property (AB)−1 = B−1 A−1 we see that Φ† ≡ Φ−1 .
At this point, we can gain some insight into the role of the bias parameter w0 . If
we make the bias parameter explicit, then the error function (3.12) becomes

1 
N M −1
ED (w) = {tn − w0 − wj φj (xn )}2 . (3.18)
2
n=1 j =1

Setting the derivative with respect to w0 equal to zero, and solving for w0 , we obtain

M −1
w0 = t − wj φj (3.19)
j =1

where we have defined

1  1 
N N
t= tn , φj = φj (xn ). (3.20)
N N
n=1 n=1

Thus the bias w0 compensates for the difference between the averages (over the
training set) of the target values and the weighted sum of the averages of the basis
function values.
We can also maximize the log likelihood function (3.11) with respect to the noise
precision parameter β, giving

1 
N
1
= {tn − wML
T
φ(xn )}2 (3.21)
βML N
n=1
THE BIAS-VARIANCE DECOMPOSITION
Bias and variance are negatively related, therefore it is essentially difficult to have
an ML model with both a low bias and a low variance. The bias-variance
decomposition is a useful theoretical tool for understanding a learning
algorithm‘s performance characteristics. Certain algorithms have a large bias and
a low variance by design, and vice versa. Bias-variance is a reducible error, in
this article, we will be understanding the concept with ways to decompose the
mean squared error.

What is Bias-Variance Decomposition?

The bias is defined as the difference between the ML model’s prediction of the
values and the correct value. Biasing causes a substantial inaccuracy in both
training and testing data. To prevent the problem of underfitting, it is advised that
an algorithm be low biased at all times.

The data predicted with high bias is in a straight-line format, which does not fit
the data in the data set adequately. Underfitting of data is a term used to describe
this type of fitting. This occurs when the theory is overly simplistic or linear in
form.
The variance of the model is the variability of model prediction for a particular
data point, which tells us about the dispersion of the data. The model with high
variance has a very complicated fit to the training data and so is unable to fit
correctly on new data.

As a result, while such models perform well on training data, they have large error
rates on test data. When a model has a large variance, this is referred to as
Overfitting of Data. Variability should be reduced to a minimum while training a
data model.
Bias and variance are negatively related, therefore it is essentially difficult to have
an ML model with both a low bias and a low variance. When we alter the ML
method to better match a specific data set, it results in reduced bias but increases
variance. In this manner, the model will fit the data set while increasing the
likelihood of incorrect predictions.
The same is true when developing a low variance model with a bigger bias. The
model will not fully fit the data set, even though it will lower the probability of
erroneous predictions. As a result, there is a delicate balance between biases and
variance.

When to use bias-variance decomposition

Since bias and variance are connected to underfitting and overfitting,
decomposing the loss into bias and variance helps us understand learning
algorithms. Let’s understand certain attributes.
Low Bias: Tends to suggest fewer implications about the target function’s shape.
High-Bias: Suggests additional assumptions about the target function’s shape.
Low Variance: Suggests minor changes to the target function estimate when the
training dataset changes.
High Variance: Suggests that changes to the training dataset cause considerable
variations in the target function estimate.
Theoretically, a model should have low bias and low variance but this is
impossible to achieve. So, an optimal bias and variance are acceptable. Linear
models have low variance but high bias and non-linear models have low bias but
high variance.

How does this work?

The total error of a machine learning algorithm has three components: bias,
variance and noise. So decomposition is the process of derivation of total error in
this case we are taking Mean Squared Error (MSE).
Total error = Bias2 + Variance + Noise
Suppose we have a regression problem where we take in vectors and try to make
predictions of a single value. Suppose for the moment that we know the absolute
true answer up to an independent random noise. The noise should be independent
of any randomness inherent in the vector and should have a mean of zero, so that
function is the best possible guess.

In the above function “R(h)” which is the cost function of the algorithm also
known as the risk function. When the risk function is loss it is the squared error.
The expected function which is represented by “E” in the above equation contains
the random variables. Calculate the average of the probability distributions for
hypothesis “h”.
The data x and y are derived from the probability distribution on which the learner
will be trained. Since the weights are selected based on the training data, the
weights that define h are also obtained from the probability distribution. It can be
difficult to determine this distribution, but it does exist. The expectation function
consolidates the losses of all potential weight values.

Image source
In the above image after doing all the mathematical derivation, we can observe
that at last the three components are derived bias, variance and irreducible error
or noise.
Let’s understand this with an example.

In this example, we’re attempting to match a sine wave with lines, which are
obviously not realistic. On the left, we produced 50 distinct lines. The red line in
the top right corner represents the anticipated hypothesis which is an average of
infinitely many possibilities. The black curve depicts test locations along with the
true function.
Because lines do not match sine waves well, we notice that most test points have
a substantial bias. Here the bias is the squared difference between the black and
red curves.
Some of the test locations, however, exhibit a slight bias, where the sine wave
crosses the red line. The variance in the middle represents the predicted squared
difference between a random black line and the red line. The irreducible error is
the predicted squared difference between a random test point and the sine wave
.
DECLSION TREE

used inree Sttucturedeassi4icatioo

Repression
pataset Alg> ClassifIes_the ddta
Cdecision tree alg)-
Loan sm
Cdecice ip the loan shud e appoealejelted)

employed)
Yes
D2
Credit
Store2 Tnceme)
High ow Louu

R
 Algoithm CID3
t h e given datasetL choose a target atnbu
LIn

2 Calculate_Intormation gain of targe E aLHbt.

PtN
P
p+N N0a (PtN
PtN
N

For remaining attambutes, find entrep

Cnrop
Entropy Ta Probabiliy
ECA) 2*Ni I N
P+N

Calculate Gain TG-ELA)

a1ed
ON aSed
 e
Lompeietion Iy Pe Profi
Jes DOun
NO slw Douon
Old

old
NO hlw Down
mid
Ses Sw DOun

mid
Yes hlu Down

mid
No blw Op
NO
mid

new
yeS
No b)uw
neu NO Sw p

SLep
Target Attaibute =Pacit

Tntormatiorn gain

T P log
PtN
N02tpN
PtN
N

P cCount (docwn)5 Tog,a ml

N:CDun lup)=

5 to logt
tog,)+4 tog,(3) )
aer (-lg, x-lo9.2)
 x i tx-1
(-D=L

T
Calulate entropy for remainn9 att

E CA) + I (e, N) obabilit

PtN
Age)
i
Prepare a tabe for each atr
us- values e under baken attt
Lold, mid, new)
LelumnsNalues of target
attr
down p
Ldn up)
old 3
Entrop lGxProbabilik
mid 2 2

3
P down count
Deu N up COuDt

oba bily 3
LO

Entropy Cotd)- ox3

amid)- 28}+2

log4) ogl)
2

Prohability:tl1o Entropynid)-1x4

Taneu)a2lg{g}3a
pobability340 EntopyCneu):0x2

Enropy[Aqe) = ECo)+ £CM) +E(N)

0:44

aain TG-E (A)

0.4
= 0.6
Gain: 0.6

doyae
 In the Same uay lal. Gain f Other
0tber atth

qain LCompeLition)= O D4
aain (THpe)= _O
eain (Age) o.

Hiqhest gain root node-

CAge)-
Aqe
old new
Mid
down up
CompeERionnear highust
yes NO

DOun Up

Dld > alldewn

mid Some up LSome down_
neu all up

upe2 gain a eVen in dr ako no regui

TL Can be ianored.

aed
ON a8ed
 Learning with Trees  261

The information measure can be changed in another way, which is to add a weight to
the misclassifications. The idea is to consider the cost of misclassifying an instance of class
i as class j (which we will call the risk in Section 2.3.1) and add a weight that says how
important each datapoint is. It is typically labelled as λij and is presented as a matrix, with
element λij representing the cost of misclassifying i as j. Using it is simple, modifying the
Gini impurity (Equation (12.8)) to be:
X
Gi = λij N (i)N (j). (12.10)
j6=i

We will see in Section 13.1 that there is another benefit to using these weights, which
is to successively improve the classification ability by putting higher weight on datapoints
that the algorithm is getting wrong.

12.3.2 Regression in Trees

The new part about CART is its application in regression. While it might seem strange to
use trees for regression, it turns out to require only a simple modification to the algorithm.
Suppose that the outputs are continuous, so that a regression model is appropriate. None
of the node impurity measures that we have considered so far will work. Instead, we’ll go
back to our old favourite—the sum-of-squares error. To evaluate the choice of which feature
to use next, we also need to find the value at which to split the dataset according to that
feature. Remember that the output is a value at each leaf. In general, this is just a constant
value for the output, computed as the mean average of all the datapoints that are situated
in that leaf. This is the optimal choice in order to minimise the sum-of-squares error, but
it also means that we can choose the split point quickly for a given feature, by choosing
it to minimise the sum-of-squares error. We can then pick the feature that has the split
point that provides the best sum-of-squares error, and continue to use the algorithm as for
classification.

12.4 CLASSIFICATION EXAMPLE

We’ll work through an example using ID3 in this section. The data that we’ll use will be a
continuation of the one we started the chapter with, about what to do in the evening.
When we want to construct the decision tree to decide what to do in the evening, we
start by listing everything that we’ve done for the past few days to get a suitable dataset
(here, the last ten days):

Deadline? Is there a party? Lazy? Activity

Urgent Yes Yes Party
Urgent No Yes Study
Near Yes Yes Party
None Yes No Party
None No Yes Pub
None Yes No Party
Near No No Study
Near No Yes TV
Near Yes Yes Party
Urgent No No Study
262  Machine Learning: An Algorithmic Perspective

To produce a decision tree for this problem, the first thing that we need to do is work
out which feature to use as the root node. We start by computing the entropy of S:

Entropy(S) = −pparty log2 pparty − pstudy log2 pstudy

− ppub log2 ppub − pTV log2 pTV
5 5 3 3 1 1 1 1
= − log2 − log2 − log2 − log2
10 10 10 10 10 10 10 10
= 0.5 + 0.5211 + 0.3322 + 0.3322 = 1.6855 (12.11)

and then find which feature has the maximal information gain:

|Surgent |
Gain(S, Deadline) = 1.6855 − Entropy(Surgent )
10
|Snear | |Snone |
− Entropy(Snear ) − Entropy(Snone )
10  10 
3 2 2 1 1
= 1.6855 − − log2 − log2
10 3 3 3 3
 
4 2 2 1 1 1 1
− − log2 − log2 − log2
10 4 4 4 4 4 4
 
3 1 1 2 2
− − log2 − log2
10 3 3 3 3
= 1.6855 − 0.2755 − 0.6 − 0.2755
= 0.5345 (12.12)

 
5 5 5
Gain(S, Party) = 1.6855 − − log2
10 5 5
 
5 3 3 1 1 1 1
− − log2 − log2 − log2
10 5 5 5 5 5 5
= 1.6855 − 0 − 0.6855
= 1.0 (12.13)

 
6 3 3 1 1 1 1 1 1
Gain(S, Lazy) = 1.6855 − − log2 − log2 − log2 − log2
10 6 6 6 6 6 6 6 6
 
4 2 2 2 2
− − log2 − log2
10 4 4 4 4
= 1.6855 − 1.0755 − 0.4
= 0.21 (12.14)

Therefore, the root node will be the party feature, which has two feature values (‘yes’
and ‘no’), so it will have two branches coming out of it (see Figure 12.6). When we look at
the ‘yes’ branch, we see that in all five cases where there was a party we went to it, so we
just put a leaf node there, saying ‘party’. For the ‘no’ branch, out of the five cases there are
three different outcomes, so now we need to choose another feature. The five cases we are
looking at are:
 Learning with Trees  263

FIGURE 12.6 The decision tree after one FIGURE 12.7 The tree after another
step of the algorithm. step.

Deadline? Is there a party? Lazy? Activity

Urgent No Yes Study
None No Yes Pub
Near No No Study
Near No Yes TV
Urgent No Yes Study

We’ve used the party feature, so we just need to calculate the information gain of the
other two over these five examples:

 
2 2 2
Gain(S, Deadline) = 1.371 − − log2
5 2 2
   
2 1 1 1 1 1 1 1
− − log2 − log2 − − log2
5 2 2 2 2 5 1 1
= 1.371 − 0 − 0.4 − 0
= 0.971 (12.15)
 
4 2 2 1 1 1 1
Gain(S, Lazy) = 1.371 − − log2 − log2 − log2
5 4 4 4 4 4 4
 
1 1 1
− − log2
5 1 1
= 1.371 − 1.2 − 0
= 0.1710 (12.16)

This leads to the tree shown in Figure 12.7. From this point it is relatively simple to
complete the tree, leading to the one that was shown in Figure 12.1.

FURTHER READING
For more information about decision trees, the following two books are of interest:

• J.R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, San Fran-
cisco, CA, USA, 1993.
• L. Breiman, J.H. Friedman, R.A. Olshen, and C.J. Stone. Classification and Regression
Trees. Chapman & Hall, New York, USA, 1993.
250  Machine Learning: An Algorithmic Perspective

FIGURE 12.1 A simple decision tree to decide how you will spend the evening.

might make you study, but otherwise you’ll be slumped in front of the TV indulging your
secret love of Shortland Street (or other soap opera of your choice) rather than studying.
Of course, near the start of the semester when there are no assignments to do, and you are
feeling rich, you’ll be in the pub.
One of the reasons that decision trees are popular is that we can turn them into a set of
logical disjunctions (if ... then rules) that then go into program code very simply—the
first part of the tree above can be turned into:
• if there is a party then go to it
• if there is not a party and you have an urgent deadline then study
• etc.

That’s all that there is to using the decision tree. Compare it to the previous use of this
data, with the Naïve Bayes Classifier in Section 2.3.2. The far more interesting part is how
to construct the tree from data, and that is the focus of the next section.

12.2 CONSTRUCTING DECISION TREES

In the example above, the three features that we need for the algorithm are the state of
your energy level, the date of your nearest deadline, and whether or not there is a party
tonight. The question we need to ask is how, based on those features, we can construct the
tree. There are a few different decision tree algorithms, but they are almost all variants of
the same principle: the algorithms build the tree in a greedy manner starting at the root,
choosing the most informative feature at each step. We are going to start by focusing on
the most common: Quinlan’s ID3, although we’ll also mention its extension, known as C4.5,
and another known as CART.
There was an important word hidden in the sentence above about how the trees work,
which was informative. Choosing which feature to use next in the decision tree can be thought
of as playing the game ‘20 Questions’, where you try to elicit the item your opponent is
thinking about by asking questions about it. At each stage, you choose a question that
gives you the most information given what you know already. Thus, you would ask ‘Is it
an animal?’ before you ask ‘Is it a cat?’. The idea is to quantify this question of how much
 UNIT IV L EARNING
Probability basics - Bayes Rule and its Applications - Bayesian Networks – Exact and Approximate
Inference in Bayesian Networks - Hidden Markov Models - Forms of Learning - Supervised Learning
- Learning Decision Trees – Regression and Classification with Linear Models - Artificial Neural
Networks – Nonparametric Models - Support Vector Machines - Statistical Learning - Learning with
Complete Data - Learning with Hidden Variables- The EM Algorithm – Reinforcement Learning

BAYESIAN THEORY

Bayes’ theorem (Bayes’ law or Bayes' rule) describes the probability of an event, based on prior
knowledge of conditions that might be related to the event.
For example, if diabetic is related to age, then, using Bayes’ theorem, a person’s age can be used
to more accurately assess the probability that they have diabetic, compared to the assessment of the
probability of diabetic made without knowledge of the person's age. It is the basis of uncertain reasoning
where the results are unpredictable.

Bayes Rule
𝑃(𝐷|ℎ)𝑃(ℎ)
𝑃(ℎ|𝐷) =
𝑃(𝐷)
P(h)- prior probability of hypothesis h
P(D)prior probability of data D, the evident
P(h|D)-posterior probability (prob. Of h based on given evident)
P(D|h)- likelihood of D given h (Prob. of evident based on h)

Axioms of probability
1. All probabilities are between 0 and 1 ie0≤P(A) ≤1
2. P(True)=1 and P(false)=0
3. P(AB)=P(A)+P(B)-P(AB)

BAYESIAN NETWORK
• A Bayesian network is a probabilistic graphical model that represents a set of variables and their
probabilistic independencies. Otherwise known as Bayes net, Bayesian belief Network or simply
Belief Networks. A Bayesian network specifies a joint distribution in a structured form. It represents
dependencies and independence via a directed graph. Networks of concepts linked with conditional
probabilities.
• Bayesian network consists of
– Nodes = random variables
– Edges = direct dependence
• Directed edges => direct dependence
• Absence of an edge => conditional independence
• Requires that graph is acyclic (no directed cycles)
• 2 components to a Bayesian network
– The graph structure (conditional independence assumptions)
– The numerical probabilities (for each variable given its parents)

For eg, evidence says that lab produces 98% accurate results. It means that a person X has 98%
malaria or 2% of not having malaria. This factor is called uncertainty factor. This is the reason that we
go for Bayesian theory. Bayesian theory is also known as probability learning.

The probabilities are numeric values between 0 and 1 that represent uncertainties.
i) Simple Bayesian network

p(A,B,C) = p(C|A,B)p(A)p(B)
ii) 3-way Bayesian network (Marginal Independence)

p(A,B,C) = p(A) p(B) p(C)

iii) 3-way Bayesian network (Conditionally independent effects)

p(A,B,C) = p(B|A)p(C|A)p(A)
B and C are conditionally independent Given A
iv) 3-way Bayesian network (Markov dependence)

p(A,B,C) = p(C|B) p(B|A)p(A)

Problem 1
You have a new burglar alarm installed. It is reliable about detecting burglary, but responds to minor
earth quakes. Two neighbors (John, Mary) promise to call you at work when they hear the alarm. John
always calls when hears alarm, but confuses with phone ringing. Mary likes loud music and
sometimes misses alarm. Find the probability of the event that the alarm has sounded but neither a
burglary nor an earth quake has occurred and both Mary and John call.
Consider 5 binary variables
B=Burglary occurs at your house
E=Earth quake occurs at your home
A=Alarm goes off
J=John calls to report alarm
M=Mary calls to report the alarm
Probability of the event that the alarm has sounded but neither a burglary nor an earth quake has
occurred and both Mary and John call
P(J,M,A, E, B)=P(J|A).P(M|A).P(A|E, B).P(E).P(B)
=0.90*0.70*0.001*0.99*0.998
=0.00062
Problem 2
Rain influences sprinkler usage. Rain and sprinkler influences whether grass is wet or not. What is the
probability that rain gives grass wet?

Solution
Let S= Sprinkler
R=Rain
G=Grass wet
P(G,S,R)=P(G|S,R).P(S|R).P(R)
=0.99*0.01*0.2
=0.00198
Problem 3
Bayesian Classifier: Training Dataset
Class:
C1:buys_computer = ‘yes’
C2:buys_computer = ‘no’
Data sample
X = (age <=30, Income = medium, Student = yes Credit_rating = Fair)
 age income student credit_ratingbuys_computer
<=30 high no fair no
<=30 high no excellent no
31…40 high no fair yes
>40 medium no fair yes
>40 low yes fair yes
>40 low yes excellent no
31…40 low yes excellent yes
<=30 medium no fair no
<=30 low yes fair yes
>40 medium yes fair yes
<=30 medium yes excellent yes
31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no
Solution
• P(Ci):
P(buys_computer = “yes”) = 9/14 = 0.643
P(buys_computer = “no”) = 5/14= 0.357
• Compute P(X|Ci) for each class
P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222
P(age = “<= 30” | buys_computer = “no”) = 3/5 = 0.6
P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444
P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4
P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667
P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2
P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667
P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4
• X = (age <= 30 , income = medium, student = yes, credit_rating = fair)

P(X|Ci) :
P(X|buys_computer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044
P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019
P(X|Ci)*P(Ci) :
P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028
P(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007
Therefore, X belongs to class (“buys_computer = yes”)

Problem 4
Did the patient have malignant tumour or not?
A patient takes a lab test and the result comes back positive. The test returns a correct positive
result in only 98% of the cases in which a malignant tumour actually present, and a correct negative
result in only 97% of the cases in which it is not present. Furthermore, o.oo8 of the entire population
have this tumour.
Solution:
P(tumour)=0.008 P(tumour)=0.992
P(+|tumour)=0.98 P(-|tumour)=0.02
P(+|tumour)=0.03 P(-|tumour)=0.97
 𝑃(+|𝑡𝑢𝑚𝑜𝑢𝑟)𝑃(𝑡𝑢𝑚𝑜𝑢𝑟)
𝑃(𝑡𝑢𝑚𝑜𝑢𝑟)|+) =
𝑃(+)
0.98 ∗ 0.008
=
𝑃(+)
𝑃(+|𝑡𝑢𝑚𝑜𝑢𝑟)𝑃(𝑡𝑢𝑚𝑜𝑢𝑟)
𝑃(𝑡𝑢𝑚𝑜𝑢𝑟)|+) =
𝑃(+)
0.3∗0.992
=
𝑃(+)

0.98 ∗ 0.008 0.3 ∗ 0.992

+ =1
𝑃(+) 𝑃(+)
𝑃(+) = 0.98 ∗ 0.008 + 0.3 ∗ 0.992 = 0.305
0.98 ∗ 0.008
𝑃(𝑡𝑢𝑚𝑜𝑢𝑟)|+) = = 0.025
0.305
0.3 ∗ 0.992
𝑃(𝑡𝑢𝑚𝑜𝑢𝑟)|+) = = 0.975
0.305
The probability of not having tumour is high. So the person is not having malignant tumour.

Case 2:
Hypothesis: Did the patient have malignant tumour if the result reports negative.

Solution:
P(tumour)=0.008 P(tumour)=0.992
P(+|tumour)=0.98 P(-|tumour)=0.02
P(+|tumour)=0.03 P(-|tumour)=0.97

P(tumour|-) = p(-|tumour) p(tumour) / p(-)

= (0.02)(0.008)/p(-)

P(┐tumour|-) = p(-|┐tumour) p(┐tumour) / p(-)

= (0.97)(0.992)/p(-)
(0.02)(0.008)/p(-) + (0.97)(0.992)/p(-) = 1
(0.002)(0.008) + (0.97)(0.992) =p(-)
0.000016+0.96=p(-)
Hence p(-)=0.96

Substitute the value of p(-)

P(tumour|-) = (0.02)(0.008)/p(-) = (0.02)(0.008)/0.96= 0.00015

P(┐tumour|-) = (0.97)(0.992)/0.96 = 0.99985

The probability of not having tumour is high. So the person is not having malignant tumour.

HIDDEN MARKOV MODEL

Markov process is a simple stochastic process in which the distribution of future states depends only
on the present state and not on how it arrived in the present state. A random sequence has the Markov
property if its distribution is determined solely by its current state. Any random process having tis
property is called Markov random process. For observable state sequences, this leads to a Markov chain
model. For non-observable state, this leads to a Hidden Markov chain model.

MARKOV MODEL
Markov model is a discrete finite system with N distinct states. It begins (at time t=1) in some initial
states. At each time step (t=1,2,..) the system moves from current to next state according to transition
probabilities associated with current state. This kind of system is called a finite or discrete Markov
model.
Markov property (Memory less property): The state of the system at time t+1 depends only on the
state of the system at time t. Future is independent of past given present. Three basic information to
define a Markov model
 Parameter space
 State space
 State transition probability

Stationary Assumption: in general, a process is called stationary if transition probabilities are

independent of t, namely for all t, P[Xt+1=xj|Xt=xi]=pij

Set of states {S1, S2,…,SN}

• Process moves from one state to another generating a sequence of states: Si1, Si2,…,Sik,..
• Markov chain property: probability of each subsequent state depends only on what was the previous
state: P (Sik|Si1, Si2,…,Sik-1)=P(Sik| Sik-1)
• To define Markov model, the following probabilities have to be specified: transition probabilities
aij=P(Si|Sj) and initial probabilities π i=P(Si).
Example 1: Weather prediction
Tomorrow’s weather depends on today’s weather.
Tomorrow
Today Rainy Cloudy Sunny
Rainy 0.4 0.3 0.3
Cloudy 0.2 0.6 0.2
Sunny 0.1 0.1 0.8

What is the probability that the weather for the next 7 days will be “sun-sun-rain-rain-sun-cloudy-sun”
when today is sunny?
S1: rain, S2: cloudy, S3: sunny
P(O|model)=P(S3, S3, S3, S1, S1, S3, S2,S3|model)
=P(S3)*P(S3|S3)* P(S3|S3)* P(S1|S3)* P(S1|S1)* P(S3|S1)* P(S2|S3)* P(S3|S2)
= π 3*a33*a33*a31*a11*a11*a13*a32*a23
=1*0.8*0.8*0.1*0.4*0.3*0.1*0.2
=1.536x10-4
Initial sate probability matrix
0.5
π =( π i)=[0.2]
0.3
Sate transition probability matrix
0.6 0.2 0.2
A={aij}=[0.5 0.3 0.2]
0.4 0.1 0.5
What is the probability of 5 consecutive up days?
P(1,1,1,1,1)= π 1*a11*a11*a11*a11=0.5*(0.6)4= 0.0648

HIDDEN MARKOV MODEL

A hidden Markov model is an extension of a Markov model in which the input symbols are not the
same as the states. This means that we don’t know which state we are in. Often we face scenarios where
states cannot be directly observed. So there is a need of Hidden Markov Model.

aij are state transition probabilities, bik are observation (output) probabilities.

Set of states {S1, S2,…,SN}

• Process moves from one state to another generating a sequence of states: Si1, Si2,…,Sik,..
• Markov chain property: probability of each subsequent state depends only on what was the previous
state: P (Sik|Si1, Si2,…,Sik-1)=P(Sik| Sik-1)
• States are not visible, but each state randomly generates one of M observations (or visible states) {v1,
v2,…, vM}
• To define hidden Markov model, the following probabilities have to be specified: matrix of transition
probabilities A=(aij), aij= P(si|sj) , matrix of observation probabilities B=(bi(vm)), bi(vm)= P(vm|si) and a
vector of initial probabilities π=(πi), πi = P(si) . Model is represented by M=(A, B, π).

Example 1:

Number of states: N=3

Number of observation M=3
V={R,G,B}
Initial state distribution π=[1, 0, 0]
Sate transition probability distribution
0.6 0.2 0.2
A={aij}=[0.5 0.3 0.6]
0.3 0.1 0.6
Observation symbol probability distribution
3/6 2/6 1/6
B={bi(vk)}= [1/6 3/6 2/6]
1/6 1/6 4/6
Consider n urns containing color balls with m distinct colors. Each urn contains different number of
color balls.
Sequence generating algorithm
1. Pick initial urn according to some random process
2. Randomly pick a ball from the urn and then replace it.
3. Select another urn according to a random selection process.
4. Repeat steps 2 & 3.
Here, what is hidden? We can just see the chosen balls. We can’t see which urn is selected at a time.
So, urn selection (state transition) information is hidden.

Main issues of Hidden Markov Model

1. Evaluation Problem
Given the HMM M= (A, B, π) and the observation sequence O=o1 o2 ... oK , calculate the
probability that model M has generated sequence O.
Solution: Use Forward-Backward HMM algorithms for efficient calculations.
Forward Recursion for HMM: Define the forward variable αk(i) as the joint probability of
the partial observation sequence o1,o2 ... ok and that the hidden state at time k is si : αk(i)= P(o1,o2,
... ok, qk= si).
Backward Recursion for HMM: Define the forward variable βk(i) as the joint probability of
the partial observation sequence ok+1,ok+2 ... ok given that the hidden state at time k is si : βk(i)=
P(ok+1,ok+2, ... ok|qk= si).

2. Decoding Problem
Given the HMM M= (A, B, π) and the observation sequence O=o1 o2 ... oK, calculate the most
likely sequence of hidden states Si that produced this observation sequence O.
Solution: Use efficient Viterbi algorithm
Define variable δk(i) as the maximum probability of producing observation sequence o1, o2 ...
ok when moving along any hidden state sequence q1… qk-1 and getting into qk= si .
δk(i) = max P(q1… qk-1 , qk= si , o1 o2 ... ok) where max is taken over all possible paths q1… qk-1.

3. Learning Problem
Given some training observation sequences O=o1 o2 ... oK and general structure of HMM
(number of hidden and visible states), determine HMM parameters M= (A, B, π) that best fit
training data.
Solution: Use iterative expectation-maximization algorithm to find local maximum of P(O|M)
- Baum-Welch algorithm
Expected number of transitions from state sj to state si
aij= Expected number of transitions out of state sj

ExpectExpected number of times observation vm occurs in state si

bi(vM)= Expected number of times in state si

Advantages of HMM on Sequential Data

 Natural model structure: doubly stochastic process
 Efficient and good modelling tool for sequences with temporal constraints, spatial variability
along the sequence and real world complex processes.
 Mathematically strong and computationally efficient

Application areas of HMM

 Online handwriting recognition
 Speech recognition
Conditional Independence
— The Backbone of Bayesian Networks
In probability theory, conditional independence describes situations wherein
an observation is irrelevant or redundant when evaluating the certainty of a
hypothesis. Conditional independence is usually formulated in terms of
conditional probability, as a special case where the probability of the
hypothesis given the uninformative observation is equal to the probability
without. If A is the hypothesis, and B and C are observations, conditional
independence can be stated as an equality:

1. The intuition of Conditional Independence

Let’s say A is the height of a child and B is the number of words that the
child knows. It seems when A is high, B is high too.
There is a single piece of information that will make A and B completely
independent. What would that be?
The child’s age.
The height and the # of words known by the kid are NOT independent, but
they are conditionally independent if you provide the kid’s age.

2. Mathematical Form
A: The height of a child
B: The # of words that the child knows
C: The child's age
A better way to remember the expression:

Conditional independence is basically the concept of independence P(A ∩ B)

= P(A) * P(B) applied to the conditional model.
Why is P(A|B ∩ C) = P(A|C) when (Aㅛ B)|C?

Here goes the proof.

The gist of conditional independence: Knowing C makes A and B
independent.
P(A,B|C) = P(A|C) * P(B|C)
Conditional Independence in Bayesian Network (aka Graphical Models)
A Bayesian network represents a joint distribution using a graph.
Specifically, it is a directed acyclic graph in which each edge is a conditional
dependency, and each node is a distinctive random variable. It has many
other names: belief network, decision network, causal network, Bayes(ian) model or
probabilistic directed acyclic graphical model, etc.
It looks like so:

In order for the Bayesian network to model a probability distribution, it

relies on the important assumption: each variable is conditionally
independent of its non-descendants, given its parents.
For instance, we can simplify P(Grass Wet|Sprinkler, Rain) into P(Grass
Wet|Sprinkler) since Grass Wet is conditionally independent of its non-
descendant, Rain, given Sprinkler.
Using this property, we can simplify the whole joint distribution into the
formula below:

Markov random fields

Bayesian networks are a class of models that can compactly represent many
interesting probability distributions. However, we have seen in the previous
chapter that some distributions may have independence assumptions that
cannot be perfectly represented by the structure of a Bayesian network.
In such cases, unless we want to introduce false independencies among the
variables of our model, we must fall back to a less compact representation
(which can be viewed as a graph with additional, unnecessary edges). This
leads to extra, unnecessary parameters in the model, and makes it more
difficult to learn these parameters and to make predictions.
There exists, however, another technique for compactly representing and
visualizing a probability distribution that is based on the language
of undirected graphs. This class of models (known as Markov Random Fields
or MRFs) can compactly represent independence assumptions that directed
models cannot represent. We will explore the advantages and drawbacks of
these methods in this chapter.
Markov Random Fields

Undirected graphical representation of a joint probability of voting

preferences over four individuals. The figure on the right illustrates the
pairwise factors present in the model.
As a motivating example, suppose that we are modeling voting preferences
among persons A,B,C,DA,B,C,D. Let’s say
that (A,B)(A,B), (B,C)(B,C), (C,D)(C,D), and (D,A)(D,A) are friends, and
friends tend to have similar voting preferences. These influences can be
naturally represented by an undirected graph.
One way to define a probability over the joint voting decision
of A,B,C,DA,B,C,D is to assign scores to each assignment to these variables
and then define a probability as a normalized score. A score can be any
function, but in our case, we will define it to be of the form
When normalized, we can view ϕ(A,B)ϕ(A,B) as an interaction that
pushes BB’s vote closer to that of AA. The term ϕ(B,C)ϕ(B,C) pushes BB’s
vote closer to CC, and the most likely vote will require reconciling these
conflicting influences.
Note that unlike in the directed case, we are not saying anything about how
one variable is generated from another set of variables (as a conditional
probability distribution would do). We simply indicate a level of coupling
between dependent variables in the graph. In a sense, this requires less prior
knowledge, as we no longer have to specify a full generative story of how
the vote of BB is constructed from the vote of AA (which we would need to
do if we had a P(B∣A)P(B∣A) factor). Instead, we simply identify dependent
variables and define the strength of their interactions; this in turn defines an
energy landscape over the space of possible assignments and we convert this
energy to a probability via the normalization constant.
Formal definition
A Markov Random Field (MRF) is a probability distribution pp over
variables x1,…,xnx1,…,xn defined by an undirected graph GG in which
nodes correspond to variables xixi. The probability pp has the form

Thus, given a graph GG, our probability distribution may contain

factors whose scope is any clique in GG, which can be a single node,
an edge, a triangle, etc. Note that we do not need to specify a factor for
each clique. In our above example, we defined a factor over each edge
(which is a clique of two nodes). However, we chose not to specify any
unary factors, i.e., cliques over single nodes.
Comparison to Bayesian networks

Examples of directed models for our four-variable voting example. None of

them can accurately express our prior knowledge about the dependency
structure among the variables.
In our earlier voting example, we had a distribution
over A,B,C,DA,B,C,D that
satisfied A⊥C∣{B,D}A⊥C∣{B,D} and B⊥D∣{A,C}B⊥D∣{A,C} (because only
friends directly influence a person’s vote). We can easily check by counter-
example that these independencies cannot be perfectly represented by a
Bayesian network. However, the MRF turns out to be a perfect map for this
distribution.
More generally, MRFs have several advantages over directed models:
 They can be applied to a wider range of problems in which there is no
natural directionality associated with variable dependencies.
 Undirected graphs can succinctly express certain dependencies that
Bayesian nets cannot easily describe (although the converse is also
true)
They also possess several important drawbacks:
 Computing the normalization constant ZZ requires summing over a
potentially exponential number of assignments. We will see that in the
general case, this will be NP-hard; thus many undirected models will
be intractable and will require approximation techniques.
 Undirected models may be difficult to interpret.
 It is much easier to generate data from a Bayesian network, which is
important in some applications.
It is not hard to see that Bayesian networks are a special case of MRFs with
a very specific type of clique factor (one that corresponds to a conditional
probability distribution and implies a directed acyclic structure in the
graph), and a normalizing constant of one. In particular, if we take a directed
graph GG and add side edges to all parents of a given node (and removing
their directionality), then the CPDs (seen as factors over a variable and its
ancestors) factorize over the resulting undirected graph. The resulting
process is called moralization.
A Bayesian network can always be converted into an undirected network
with normalization constant one. The converse is also possible, but may be
computationally intractable, and may produce a very large (e.g., fully
connected) directed graph.

Thus, MRFs have more power than Bayesian networks, but are more difficult
to deal with computationally. A general rule of thumb is to use Bayesian
networks whenever possible, and only switch to MRFs if there is no natural
way to model the problem with a directed graph (like in our voting
example).
 -CollPCron

Bayes eheorem A
*
on
based
Classifier not a bingle alg, butfamiloE al
Naive Rayes Share
common pmnap
a

beiDg claASIA
e eve
iS_indo
QLofeature
f eaOh e t t a
aProbablistc
A naie Baus claSSifier is
coseificatontassk
ML Model haLs Used for
Hat
Bayes Thapaun
PLa B PLBIA) .P) O- PoRmuna
PL8)
Featis

the_pooablity of
sing D e_an £ind
Occcarebce e A VenB

B Evidence
A> tPothesis

NaI e Paues features are independlen2E

Example
EEs au oe bave a leature " headache" klCol

[Link]): PCead ache fever )x P (old fever)x

PGtever
PCheadache) X PCcold

Ln the "tever" lg_depenolnt on" headache62

Cold but these taofeaturs are not_depndent
oneach othd to Cause fevey"
 MAed tex ClasSf t ( t v ha r hacdee high
S m t1ern tien, entmorn1alA(monAio
tian
Chce he rtass fy arti les
Qne,Naive"

Let X eplesent [Link] Lures where

n Po
P A o p oh t

CTas
aeneralixing utetiko
Phohahilit

P( 2a, n: P(ly)x Plraly). xPlzl9) xPly)_

POstert o probability Pla Dx p(2) x PCz2)x. P(n)

PALdictor_paioipRobabi lity
xFor all _entria in a data set the denaminator
does not Change Jt Can be removed

P Lalx1 2n)_d PCyDT P(xily)

Let's 0orkout using a small datasel

SDo TYPe Lengtby SuweeE Helou TOER
Banana LOO 350 450 500
2 orange 30
0 300
Ohers oo 56 20 O
3
total 650 too

PLeananoa|Lengthy SweeL, delloo)=

P(sweet[Banana)X
PCtengthy Banana) x PCHeltouwl Banana) XPlerr

ON8ed
PClengty) xP(sweel) x pCyello) y
 Lets uOk outL tach factor s in

o0o 0 8
PLenghy l8anana
P (Swee| 31500= 7
PgellawI 495D0
PCeanaDa )
500 Lo00 = 055
PCLengthy)
PCSweet) 6GD looO -0 65
PLyellow) 1ooo= O8
in
Subsutuitingall the above values
=0.62 0.94

O.8 X O1X0.9 X O:h

O.65
5 X O65 X 08

thy,DeeEgRlaL
Plorangel Leng
No
N De need +o find
lororngs
Pengtylotange)
xD[swee lorarge)xPLHell
xPCorange)

PLlengthy)xPcweet)x Plyella)
L

Sin Ce pCLengtbylozange)=6
PLorangel lengthy sweet yellow =6

oN -doyla1ea
 t i n d tor

of othersLengthy,_weet, yellao = O.0722|

We ASsign the
classwhich has maX._pogbability
which S gn b eq
m an m u u m

arg ma PLH)T P(zily) 289

PBarmna 1engthy, SweetHellao)= 0.96
P_Corange
P Cothers E p.021|

The classBanana" bag maimum paokabi lty

heretore the fruit with featue Lengthyueet
yelle' is_classified as eanana
X
 QUsSian Mi
inear
s s i a n s

0f Gau
-posiion
Super
(n
dIs
é)
GaUssaN

T N (z ]HK
multi-varnate

P2)- N O r m a l

f ea
ore
tor ac
chh
Neiqhlage
(Oepficient: Saussian dist
Mixing
NO of Gaussians
reaure
N o r m a x l i z a t i o n
& Positi
v
i ty

O TTk , TT =
(onsidler loq-Likelihoed N

Plxn)= 2 n N(2nHk
n P(xIM, 4,T) =á4n rom )

no. Of insLaN Ce
form Son
ML doesnot uwork bere athere is no clased

parameters an be Calculated uSing

EXPECTATTON MAXI MIZATION EM) E e c h n i u e aver

Miture o f
3 6au6siaN

Obtain
frog
05
sa
(sam clA)

Catter matiX

probabili
POstEriOr
Late varia be
as P71Or
thin of the miing Co-ePfîCients
We an
Compenents
for the
Proba b i l i i e s
can e v a l u at e the
the
we
of x,
For a gn. va lue Called vesponbilii
pos&eior probabilities,
Correspondi m
 M)
qaasSian Mixture model GMN

The Gaussian Disembiton

on
Gaussian Dise Mbut
* U n i v a i Q Le

G(2|Hor= 4 2

2 2

2T
Man Varnance

*Multvaiate qaussian DiStTbutcn

NCa , » eN p x - 4 ' t 2 - w )

mean Co-variance

parameLers2, H)
of a
We need to etimate thesa
distibution:
£s Emato
*one method- Marimum Likelihood CML)
s
ML method for estimating Parame
diStrTbution
* Consider log of Gaussi an
(x-)
2n
Pla]H á): an(a) -arn |El -L(1-H
Zero
deMYatiVe & e¢uate
Take t h e

n P(|E)=o enPlzHE)

N 2ML tp-HML) (D-HM

MML N
Zn
where N no. of samples o r datapts.

mi ture of GaUSSIans ?
What f we have

Gaus s i a n Mixture
 Proro Baya Yule,

P(K|«) - PCk) Pla]k)

Ca) =

LQtent
Px NoOfampls
fbr pa tHC uhr
variablE
e lass

T N Ca HE , é whor e, T=Nx
N
T N (a|Hj£j)
No of
sampS
pts qssGNEd
Interpet k as the effective no. of
to Cluster k

ExPECTATION MAxI MIZATION

optimizatan
tech.
wheh
's
an iterative
a g . is
Operated locally

Estimation élep: can

compute the
we
Paameter Values
tor a Gn variable
latent
values Of the miksPg valeS
expected
modlel baas
seed
d on
o n
Xaximization sEEP moolel
b
ou
O ur
r
the
he parameberS of
Of
paates ML m e t h o d .
calcala ted
ucig
Vriable
the atent

EM lg for GMM
ikelihoad m
maximize -the
a MM, the goal is to ico-variances

Co.r.t Parameters Comprising the mean

coefficients
the2 Compaonenis
Of the
Of the2 mixing

.Dnitialize the me
j CDvaNiances z; &mixinG
Cintex likelihoo
Co-eff. T evalua te the initial value of Log
the curre
the responSi
billties usi ng
2. L
E-9Lep E v a l u a te
S ep: Pa a m e t e r values

J
 parameters uSng the
3 currerDe
M-SLep: Re-etima te the
esponSibilities
N N

2Can)

T (an)
Evaluabe log Liklihoobd
N
An P(x|H, £,TT ) =É n N(an]Hk) é)9
to SLep 2
TA there ìs return
no
Converqen ce, SuccesSve

in Aev Iteratons
P2TT no change
iterations
in Prev.
ciange
og lik lidvool
no

EM alg : EXample
L5
repeate L
EM Step

AecOupu e Ld
rRe Blue

20

Re

Blue
He archi cal Cluste inj
Jn this ue mrtitio the dala by
pproach,
9ouping i into a tree o CluCteIs or a

bierar chy
s ue
isu s sfeu
fll
dala
epresenlateN of
H1erar Chical visuali zati on.
visuali z a t t o n .
data zaUn
Summari
for
for
a n d divide
combinos
Hierar chical cluster ing alq. SLH
hierarchical
a
exis ing r u p s , Creating are
the o r d e r
in which a r o u p s
that Showcases

divided or mer ged

Ag9lomera tive
2tpess

Divisive
METHOD
CLSiERING

AGGLOME RATIVE
HtERARC HIC AL

iS used
approach
Bottom-up
Own
cluster.
-forms i-S
Each Object iLeratively mergin9
merging
The proceSS Converges by Leratively
a Lhe
l Lhe
all
c t u s t e r s , unti
ctusterS into larger terminaie
or a
etuster
are n a Single
objects
Conditon is reached

becomes the hierarchy

ctuster
The Single
root
sîmilar
operatîon
During the merging ,

aistance
C(usters are identi-fied using
ures & Combine d to form a
larger
meas
Ctuster
Per iteratlon , two clusters a
are
e met ged, uwhere

each cluster
one obect
Contains aLea
the
at most
I9lbmeraiive meth require

'niLera tions
Three tHpes
O Single link Lechnique
The dist blw tuwo ctusters is defind as

a in each cluster.
the shortest dist. bw PAs

o
Conmplete tink echnique
is dasina as the
the
the dist bluU w o ctusters

ongest disL. blw pAs n each cluste

S

Average tinKtechnique
Theavg
diSt blw each PE. In one cluSAer to everypl

in the Cther Cluster.

 (omplet link:
Pi C P2(15, 1s) P3 (5,5) P4 (3,42 Ps (414)
Pb (3,3.5)

Sep
Compute the dist. n a t i z
al tay)(aib)) =
Ca-a+(t-6
PIP2 P3 P4P5 P 6
PI

P2 1 o
P35664
P4 3.6 242 |2.24
PS24 3.53 4) |o
P
O

P 3.20|2.5 25 o.5 12

Step 2: clusters
Merging the & clasest members 0f
in dist. matma
fiod the. min. elemen t

min o5

Vpdate the dist natm a,

CP41PL),PI): man Cdl PHPD, d CP6, PI)

max (d 3.6
maa3 . 6 3.2)>
2.92
(a.q2, 2.5)=
(dC P4IP6), P2)
max - mar
2.5
(2.24, 2.5)=
ma (d CP4) P6), p3) ' = max

m a a Cd CP41 P%), P5) man C1o,112)=1.12

P3 P4P P5
P P2
PI

P2 o1 O
P3 564 4-9S|O
36 2 92 2.5 O
P4P6
O
I.4112
Ps 4.24 353
 Nou we (ombire PI&P2 d (P P3))
P3),
max (d (Ply P2) ,
P3)= maa/ d (Pl) b6
5 . 6 6 , 4 . 9 5 ) = t .

mar ( Pb
CP2 *|Pb
( Pl,Pu, Pt) ,
CaPlP2), (P41 PL)) = maa
3.6
2.4) =

maz ( 9.6,
3.53)
max Ca CPl P2) , P5) max CG.24,

2 4

P3 P4 P6 P5
Pl P2

CPl P2) O

5.66 O
P3
25
CP4 PL)
3.6
P5 2t 12

NOL ue Combine P41 Po P5

d l Pl) P2))= maa( P4P6) CPly P2

max la l P4, P6, Ps), P5, Pl, P2)
maa (g.6 24)= y.2
maa Cd CP4,P6) P5) P3) mar (p4, pb, P3), { D5;P3)
2.S
ma (2.5, 1.4D :

max Cd Cp: PGPLPs

PlP2 P3
Pl, P2
O
P3 S.66

P4 D6, Ps q.24 2.S

R P3
No we Combine P 4Pb Ps
(O4IP6, Ps)C PI, P2)
(dCPy,P&, P5, P3) SPl,P2))=
maa
max
P3, P!» P2)
. 6 6 ) = S66.
C 29
 (P, r2) A, Pb,Ps ,Pa
P, P2
Pa, p, Ps c.b

P4 PL P5 P3 P P2

Average gink:
as above
Same datapts.

AfLer al dlsL. m a t a i a

PIP P3P4Ps P
PI
P2 o7 o
P3 5.664
P4 3.6 |2.42 2.24
P5 424 353 | 41 |O
P6 8.202.5 | 2.5 D5112 O

9o Combne P4+) P6
Sc P4 P?), ( P6, PP)I
ava Cal P4, P6),
d ( PD) =
a9C

avg (3.6,3.2) > 3.4

avg CdlP4) Pé), d (Pn) avg Ca.q2,2.5)
= 2.7/

avg CdDerP6) , d (3) avgt2.24 ,2.5) = 2.37

avg Cd c PEPb) >d CPs) =
avg C t.0, 112 =1.06
 Opda t diSL matrid
PIP2 P3 Py P6 P5
P5
P

P2
o11 O
P3
5-66 445
P4 P6 3.4 2.71 2.37
Ps 424 3.53 41 06
No Combine PI4P2
dCp2,P3)DD
avg(a (PIy P2), Ps) =avg (d CP), P3D,
5.31
avg t5.66, 4.95)
=

av C CPI> P2), CPypt)) = avq (CP), Pu P6) ( P2,P4) P6P

2.46
avg C 9.4, 2 . 7 ) =
avg la C Pl> P2)5 P5) = P5))
avg Pl> P5) CP2,
aYg 4 2 4 , 3 53) 3 . &&9
P1 P2 P3 P4y Pb Ps
Pl, P2

P3 5.31
P4 P% 2.96 2.37

P5 3.89 t.41 06

NO Combine P4+ P6 &P5

CPI; P2)) =
avg ( Pl> P2) (P5, Pls P2)
P41 P6,
avg ld CP4) Pé, Ps)
avg a.9, 9.84) - 8.43

avg CaC P4)Ph> P5)(¬3)) -

P) Pby P3) CP5 P3)
qvq
avg ( 37, 41 - 196
 PI, Pa P3 P4 Pb P5

(Pl Pa
P3 S.31

P4,PbPs 3.4-3 6)

Nou Combine P4+ Pb Ps &P3

PIP2-
P3), CPlP2): ava(py, Po,Ps) (
avg (d (p4,Pb, P5,
CP3, PlyP2)
5-31) +37
avg (3.43,
PP2 P4 Pb PS P3

Pl, P2

P4) P6, P5, P3 431

P p
P PG P5 P3
 Sinale link
as above
*Same dala pS.

mataia
[Link] aat dist P% P
P2 P3 P4
PL

Pt
P2

P3 5.66 495

P4 3.6 2.92 2.24

P 424 3.53 4 .
P 3.2 25 2.5 0 1.2

Combine P P6.

P), CP&, Pi)

PID: min CPe
min (d LP4, P6), 82) .2
= min C 9.6 =

25
25)
min P¢P6),P2)
(at i n t a42,
9.5): 2. 24
min (dC P41 P6), P3) mim (a.2 4,
t
min(dc P4Pé), Ps)= min (1, 1.12)
date distmati«
PG P5
p2
P3 P4
P

P
P2

P3 5-66 4 O

PP P6 3-2 |2.5 2.24 O

P5
Ps 224 9.53 .41
 PIR P2
Combine

min CPl P3) ( P?) P3) }

min (dt Piy P2), P3) 4.95
min (5.66, 495)
P6)
P&) (P2 Py
min Ca CPl, P2), CP4IP6) =min Ply P4)
2 . 5
2.5)
min 8.2,

(4-24 j 3.53)
= 3.53
min CdC PIP2), Ps) min

OPdae;

P4 Pb P5
Pl Pa P 3
Pl P2

4-95 O
P3
P4 P 25 2:24

363I4l
Ps
P4, P6, P5
Combine P2)
min p4 P% Pl)
Pé, P), (Ply P2): CP5 Pl P2)3
min CdlP+
= 2.5
2.5/3.53)
min (
P3)
min (d CP4) Pb, P5, min , Pe, Pa)fs PD}
min (2.2 4, .4-1=t 41
Opdate Pl P2 P3 P Po Ps
Pl, P2
4. 9 5
P3

P4+, Po Ps 2.5
 P3
Combine P4 P6, P
minf(P4 Pb,Ps )(M,P)
(Pi, P2)) -
in (dC Py Pby Ps, P3),
(rgPIP) y
m i n ( 9 . 5 , 4.95)-2.5/

P3
Upodate Pb, P ,
P P2 P4

PI, P2
O

25
P4 Po P5, Pa

Dendogram

P6 p P P2
P
 DiviSive
Hie rarcbical cluserIn

op doun apNoaCh innt

too small
s mal
i
cluner
he
Partitin
re
e cusivey
cuusively
fom
toot

Sub-clustss lartin9 tVY)

P
prro
ecco
esss
s
arAioning
-the levet Contains ins
-

We (an stop levet

conda
l owest
louwesS are
ctuter at the cwithin C
c tl
u uS
sEer
each coi-tin
or the Obj
only one cbj to each other.
oimilar
Sufficienty

PROCESS cluseer
obj. in
one
atl
Start by placing
by
ctusters
have Single abet
have
Cuni atl t h e
2. Repeat
Repeat
maz
intr-cluster

cluster
wlth
a
a) selecE

distance to split CwHh

twHh the
cluster
Seected
the
b) Reptace
Sub- ClusterS
i minimum spanning tree

bisecting kmeans
Dvisive method

min mar cut techniques

K-means APPRO ACI

APPROACI
sPLITTING USNG BISCCTI NG

ProcesS R HS
Of
Points
P its c ltester
in aa cluASAer
in
he Set
OConsidr

Centroid
andom CL among the set of PLs
aa PL at
Setecte
pt. af CL
Construct ne PtCR a s the ymmetnC
[Link] centroid w Such that,
Co, cR)
distance Cw, CL)= d lstance
cluser it
in the
Seperate the other PES
to
ones ctosest to CR betong
betong
&groups
 closet

SubctuSLEr R, a n d the ones

Sub-Cluster L
belong to the
gubclusters RL
the
Reiterate Steps |to 5 for
6

Example
Consider datapts.
6(s13
(s,5), asC7, +),
a

aiCo,7),a2 (2,5), as l3 6), a4

ito 2 cluster.
splitit
+877+8/6=s
Soln (5,5)
2+2 3
7+5+6+5tYt 3/b *S
as
SComputed
Centroid w
O
to CL
o CL
be. assigned a5 coi{t be
Let a s (S,6) CL t o w,
stmmetiCitY
of
Basedd on
assigned o Ce,
Ca2,a3D, [a4a»
(a,a3D, la4\a
diSt, we see Cal, a3) ,
the
Evaluating
(a4a2), (a6, a 3)
Cal)a), Ca2,as))
Cabas,
a r e e t o s e r
to a3
alag aSs
closes E
clesest
to
t o a
are
aL
a4

al, a2, a3y Clusters are

Hence L
created.
 )
9PECTRA CLuSTEPIN
lhe clusterS
clusters
lhe

LS a bbott
a out inding
findin9
Spectra
rera
dusiering

10a qraph
connected Abgraphs 2
toFinoding
the mostky
clusters
the
there by identirjing

to cluste 9taph plerty

Plerty
Why of qraphs
are
form
Data in the the
t he inlinks
netuor ks Tracking
9ocia
c u t l i n ks f
e b paqes.
Can ha ve
text doccemntwords
In a formin
fbrmingg
a aJap
92mantic
connectian blwthem

SolO:
maximum
nmaximUm
no. e£
no. e witbi
whin5

Pinding Sub
graphs having blc c
C ll
u uss
te r
te
Pindin comecims
minimum
miimum no. a blw
Ctuser

Conecuons
graph GCVE)
undirected

Cwe have
Lets
Lets 9a4

Y3-
AAE
dsjoint qrouPS ALS
groups
nto
Hto 2a aSJoint
Tosk vertices of &
i d e -the

Y
 is a goed cluster J
Gaph cuts What
but hes e
e set
t af
af
is nothin9
A Cu h a 9raph
closter
cluster
the
one node in
ecges wHh only
only

o4 edae
Cut a)=
jée
ieA

as
Let asSSume te edge weigt
The cuL CA)= a

Pbm with c t SCore

cut SCore decide the cluster qualiy based on

the conneCtion.s outside the cluster than inside

cluster

See this Graph

cleustt
ADt

may alse
he
his
a Cct

metric alled
To overcome tnis oe go for
than ct"
Cond uctance"
the
Connectivit af the aroup to the r o s t of
the den sity a the goup
Ow retative to
shud know abt. volu me' me t1¢
 of nodo i
d e qee
vol (A di
iA

e . t o t a lwi f w r b a L l e s t one endpL

edgps
io A cluster

> outward Connetti on

ConduCiance = cuLCA)
vol CA)3 inter ton nection,

Spectral cluStering
3 man Steps
Pre- processing
-MatrinreP of a graph
De Co mpositor
- Compu &e
e igen valuee & eigm vectrs af m a t i x

epreepe26 map each L to a

louwer dim. rep.
Grouping 9
A 3sign points or nodes to Or more

Clusers ba sed CLpon neu representaton

Step- Pre processin9

*Build Laplacian matia L Of a graph

I.a Bulld adjaceng matai.

is Connecta-
Adjacene matriz tells how the graph
grap
The mataiz has a non-zero value in it there
S a Connection blw 2 verties , else it s
2eo.
 A ad matrn ef undileded Graph G.
A
jacency
adja cency
if Cij is a n edge
Alj=
else

Let's assume a vector

in raph 6
Xn)
no. or nodas
values| labels
a sa s t he
the values abels
vector
his
of
Thin k
Thin
node in Graph 6
each bit different Cway
in a
a =y
Think O values.
Vector R eigen
Let's tink Tigen
A a =

Eigen
Eige+or Value2

Spectral ctustering
bt the eigen rectors
is nothing
the mamitude ao
9pecerum magnitade af
ordered
aj of a graph,

their eigen values A

Let's See adaceng
EaamPe Matn ar Graph 6
5
6)
v a l u e S c o n n e c t e d ,

23 456 with
2,3, 5 . Hence

A
2

5
 let's find the
Rerfom LaplacIaN matrix,
matix
Degree 4 5 6
O O
D 3
2 2
O

O O
3 0
4o O

5 0 o3
2

Laplaiarn Matiz (L). D-A

23+||6 0 p a i ro f nodas

not ConNected
3
2 nodes
2 - Pair of
3 O that are

3 Connectad

with eigen vector

now when we Co-retate (L)
g0
S0,
IE s a proven face
2 Cl. .

1)
hat the dsmalle
in
L =o each row 2 eiqen value A he|ps
Co. adds Partition
the Graph
pto finding
Correspodin
*The eigen vector
the nede
Partitin
to A2
in such a uay (hat
a bels

B
 0
Eigen vecfor, 2

SO
+ ieA
eB

Remember he Lapla cian ma t i a s Sqmmetric

2
3
A,2,39 & group
af
eigen vector 3 Clus t s
+
5 3
6
Summary
Prepro Sing Matriq constr on
D e conposin9 Pindin elgen vectors/values

Grouping n9 Partionig/elusteving.
Dimensionality Reduction
The number of input features, variables, or columns present in a given dataset is known as
dimensionality, and the process to reduce these features is called dimensionality reduction.

A dataset contains a huge number of input features in various cases, which makes the predictive
modeling task more complicated. Because it is very difficult to visualize or make predictions for
the training dataset with a high number of features, for such cases, dimensionality reduction
techniques are required to use.

Dimensionality reduction technique can be defined as, "It is a way of converting the higher
dimensions dataset into lesser dimensions dataset ensuring that it provides similar
information." These techniques are widely used in machine learning for obtaining a better fit
predictive model while solving the classification and regression problems.

It is commonly used in the fields that deal with high-dimensional data, such as speech recognition,
signal processing, bioinformatics, etc. It can also be used for data visualization, noise reduction,
cluster analysis, etc.

The Curse of Dimensionality

Handling the high-dimensional data is very difficult in practice, commonly known as the curse of
dimensionality. If the dimensionality of the input dataset increases, any machine learning
algorithm and model becomes more complex. As the number of features increases, the number of
samples also gets increased proportionally, and the chance of overfitting also increases. If the
machine learning model is trained on high-dimensional data, it becomes overfitted and results in
poor performance.
Hence, it is often required to reduce the number of features, which can be done with dimensionality
reduction.

Benefits of applying Dimensionality Reduction

Some benefits of applying dimensionality reduction technique to the given dataset are given below:

o By reducing the dimensions of the features, the space required to store the dataset also gets
reduced.
o Less Computation training time is required for reduced dimensions of features.
o Reduced dimensions of features of the dataset help in visualizing the data quickly.
o It removes the redundant features (if present) by taking care of multicollinearity.

Disadvantages of dimensionality Reduction

There are also some disadvantages of applying the dimensionality reduction, which are given
below:

o Some data may be lost due to dimensionality reduction.

o In the PCA dimensionality reduction technique, sometimes the principal components
required to consider are unknown.

Approaches of Dimension Reduction

There are two ways to apply the dimension reduction technique, which are given below:

Feature Selection

Feature selection is the process of selecting the subset of the relevant features and leaving out the
irrelevant features present in a dataset to build a model of high accuracy. In other words, it is a
way of selecting the optimal features from the input dataset.

Three methods are used for the feature selection:

 Filters Methods

In this method, the dataset is filtered, and a subset that contains only the relevant features is taken.
Some common techniques of filters method are:

o Correlation
o Chi-Square Test
o ANOVA
o Information Gain, etc.
 Wrappers Methods
The wrapper method has the same goal as the filter method, but it takes a machine learning model
for its evaluation. In this method, some features are fed to the ML model, and evaluate the
performance. The performance decides whether to add those features or remove to increase the
accuracy of the model. This method is more accurate than the filtering method but complex to
work. Some common techniques of wrapper methods are:

o Forward Selection
o Backward Selection
o Bi-directional Elimination

 Embedded Methods: Embedded methods check the different training iterations of the
machine learning model and evaluate the importance of each feature. Some common
techniques of Embedded methods are:

o LASSO
o Elastic Net
o Ridge Regression, etc.

Feature Extraction:

Feature extraction is the process of transforming the space containing many dimensions into space
with fewer dimensions. This approach is useful when we want to keep the whole information but
use fewer resources while processing the information.

Some common feature extraction techniques are:

a. Principal Component Analysis

b. Linear Discriminant Analysis
c. Kernel PCA
d. Quadratic Discriminant Analysis

Common techniques of Dimensionality Reduction

a. Principal Component Analysis

b. Backward Elimination
c. Forward Selection
d. Score comparison
e. Missing Value Ratio
f. Low Variance Filter
g. High Correlation Filter
h. Random Forest
i. Factor Analysis
j. Auto-Encoder
Principal Component Analysis
Principal Component Analysis is an unsupervised learning algorithm that is used for the
dimensionality reduction in machine learning. It is a statistical process that converts the
observations of correlated features into a set of linearly uncorrelated features with the
help of orthogonal transformation. These new transformed features are called
the Principal Components. It is one of the popular tools that is used for exploratory data
analysis and predictive modeling. It is a technique to draw strong patterns from the given
dataset by reducing the variances.
PCA generally tries to find the lower-dimensional surface to project the high-dimensional
data.
PCA works by considering the variance of each attribute because the high attribute shows
the good split between the classes, and hence it reduces the dimensionality. Some real-
world applications of PCA are image processing, movie recommendation system,
optimizing the power allocation in various communication channels. It is a feature
extraction technique, so it contains the important variables and drops the least important
variable.
The PCA algorithm is based on some mathematical concepts such as:
o Variance and Covariance
o Eigenvalues and Eigen factors
Some common terms used in PCA algorithm:
o Dimensionality: It is the number of features or variables present in the given
dataset. More easily, it is the number of columns present in the dataset.
o Correlation: It signifies that how strongly two variables are related to each other.
Such as if one changes, the other variable also gets changed. The correlation value
ranges from -1 to +1. Here, -1 occurs if variables are inversely proportional to each
other, and +1 indicates that variables are directly proportional to each other.
o Orthogonal: It defines that variables are not correlated to each other, and hence
the correlation between the pair of variables is zero.
o Eigenvectors: If there is a square matrix M, and a non-zero vector v is given. Then
v will be eigenvector if Av is the scalar multiple of v.
o Covariance Matrix: A matrix containing the covariance between the pair of
variables is called the Covariance Matrix.
Principal Components in PCA
As described above, the transformed new features or the output of PCA are the Principal
Components. The number of these PCs are either equal to or less than the original features
present in the dataset. Some properties of these principal components are given below:
o The principal component must be the linear combination of the original features.
o These components are orthogonal, i.e., the correlation between a pair of variables
is zero.
 o The importance of each component decreases when going to 1 to n, it means the 1
PC has the most importance, and n PC will have the least importance.
Steps for PCA algorithm
1. Getting the dataset
Firstly, we need to take the input dataset and divide it into two subparts X and Y, where
X is the training set, and Y is the validation set.
2. Representing data into a structure
Now we will represent our dataset into a structure. Such as we will represent the two-
dimensional matrix of independent variable X. Here each row corresponds to the data
items, and the column corresponds to the Features. The number of columns is the
dimensions of the dataset.
3. Standardizing the data
In this step, we will standardize our dataset. Such as in a particular column, the features
with high variance are more important compared to the features with lower variance.
If the importance of features is independent of the variance of the feature, then we will
divide each data item in a column with the standard deviation of the column. Here we
will name the matrix as Z.
4. Calculating the Covariance of Z
To calculate the covariance of Z, we will take the matrix Z, and will transpose it. After
transpose, we will multiply it by Z. The output matrix will be the Covariance matrix of Z.
5. Calculating the Eigen Values and Eigen Vectors
Now we need to calculate the eigenvalues and eigenvectors for the resultant covariance
matrix Z. Eigenvectors or the covariance matrix are the directions of the axes with high
information. And the coefficients of these eigenvectors are defined as the eigenvalues.
6. Sorting the Eigen Vectors
In this step, we will take all the eigenvalues and will sort them in decreasing order, which
means from largest to smallest. And simultaneously sort the eigenvectors accordingly in
matrix P of eigenvalues. The resultant matrix will be named as P*.
7. Calculating the new features Or Principal Components
Here we will calculate the new features. To do this, we will multiply the P* matrix to the
Z. In the resultant matrix Z*, each observation is the linear combination of original
features. Each column of the Z* matrix is independent of each other.
8. Remove less or unimportant features from the new dataset.
The new feature set has occurred, so we will decide here what to keep and what to
remove. It means, we will only keep the relevant or important features in the new dataset,
and unimportant features will be removed out.

Example:
Let’s suppose that our data set is 2-dimensional with 2 variables x,y and that the eigenvectors and
eigenvalues of the covariance matrix are as follows:
 If we rank the eigenvalues in descending order, we get λ1>λ2, which means that the eigenvector
that corresponds to the first principal component (PC1) is v1 and the one that corresponds to the
second component (PC2) isv2.
After having the principal components, to compute the percentage of variance (information)
accounted for by each component, we divide the eigenvalue of each component by the sum of
eigenvalues. If we apply this on the example above, we find that PC1 and PC2 carry respectively
96% and 4% of the variance of the data.

Applications of Principal Component Analysis

o PCA is mainly used as the dimensionality reduction technique in various AI
applications such as computer vision, image compression, etc.
o It can also be used for finding hidden patterns if data has high dimensions. Some
fields where PCA is used are Finance, data mining, Psychology, etc.
Latent Dirichlet Allocation
Latent Dirichlet Allocation (LDA) is used as a topic modelling technique that can classify
text in a document to a particular topic. It uses Dirichlet distribution to find topics for each
document model and words for each topic model.
Johann Peter Gustav Lejeune Dirichlet was a German mathematician in the 1800s who
contributed widely to the field of modern mathematics. There is a probability distribution
named after him ‘Dirichlet Distribution’ which is the basis of LDA.
There are 2 parts in LDA:

 The words that belong to a document, that we already know.

 The words that belong to a topic or the probability of words belonging into
a topic, that we need to calculate.
THE ALGORITHM TO FIND THE LATTER
 Go through each document and randomly assign each word in the
document to one of k topics (k is chosen beforehand).
 For each document d, go through each word w and compute :
1. p(topic t | document d): the proportion of words in document d that are
assigned to topic t. Tries to capture how many words belong to the topic t
for a given document d. Excluding the current word.
If a lot of words from d belongs to t, it is more probable that word w belongs
to t.
( #words in d with t +alpha/ #words in d with any topic+ k*alpha)
2. p(word w| topic t): the proportion of assignments to topic t over all
documents that come from this word w. Tries to capture how many
documents are in topic t because of word w.
LDA represents documents as a mixture of topics. Similarly, a topic is a mixture of
words. If a word has high probability of being in a topic, all the documents having
w will be more strongly associated with t as well. Similarly, if w is not very
probable to be in t, the documents which contain the w will be having very low
probability of being in t, because rest of the words in d will belong to some other
topic and hence d will have a higher probability for those topic. So even if w gets
added to t, it won’t be bringing many such documents to t.
  Update the probability for the word w belonging to topic t, as
p(word w with topic t) = p(topic t | document d) * p(word w | topic t)

Assumptions of LDA for Topic Modelling:

Documents with similar topics use similar groups of words
Latent topics can then be found by searching for groups of words that frequently
occur together in documents across the corpus
Documents are probability distributions over latent topics which signifies certain
document will contain more words of a specific topic.
5 sentences, 2 topics:
o I like to eat broccoli and bananas.
o I ate a banana and spinach smoothie for breakfast.
o Chinchillas and kittens are cute.
o My sister adopted a kitten yesterday.
o Look at this cute hamster munching on a piece of broccoli.
Then he does some "calculations"
o Sentences 1 and 2: 100% Topic A
o Sentences 3 and 4: 100% Topic B
o Sentence 5: 60% Topic A, 40% Topic B
And take guesses of the topics:
o Topic A: 30% broccoli, 15% bananas, 10% breakfast, 10% munching, …
at which point, you could interpret topic A to be about food
o Topic B: 20% chinchillas, 20% kittens, 20% cute, 15% hamster, …
at which point, you could interpret topic B to be about cute animals

Your question is how did he come up with those numbers? Which words in these
sentences carry "information":
o broccoli, bananas, smoothie, breakfast, munching, eat
o chinchilla, kitten, cute, adopted, hampster
Now let's go sentence by sentence getting words from each topic:
o food 3, cute 0 --> food
o food 5, cute 0 --> food
o food 0, cute 3 --> cute
o food 0, cute 2 --> cute
o food 2, cute 2 --> 50% food + 50% cute
So my numbers, differ slightly from Chen's. Maybe he includes the word "piece"
in "piece of broccoli" as counting towards food.

We made two calculations in our heads:

o to look at the sentences and come up with 2 topics in the first place. LDA does this
by considering each sentence as a "mixture" of topics and guessing the parameters
of each topic.
 o to decide which words are important. LDA uses "term-frequency/inverse-
document-frequency" to understand this.

LDA Procedure

Step1: Go through each document and randomly assign each word in the document to one
of K topics (K is chosen beforehand)

Step2: This random assignment gives topic representations of all documents and word
distributions of all the topics, albeit not very good ones

So, to improve upon them: For each document d, go through each word w and compute:

 p(topic t | document d): proportion of words in document d that are assigned to topic t
 p(word w| topic t): proportion of assignments to topic t, over all documents d, that come
from word w
Step3: Reassign word w a new topic t’, where we choose topic t’ with probability

 p(topic t’ | document d) * p(word w | topic t’)

This generative model predicts the probability that topic t’ generated word w. we will iterate
this last step multiple times for each document in the corpus to get steady-state.

Solved calculation
Let's say you have two documents.

Doc i: “The bank called about the money.”

Doc ii: “The bank said the money was approved.”
After removing the stop words, capitalization, and punctuation.
Unique words in corpus: bank called about money boat
approved

Next then,
 After then, we will randomly select a word from doc i (word bank with topic assignment 1)
and we will remove its assigned topic and we will calculate the probability for its new
assignment.
For the
topic k=1
For the
topic k=2

Now we will calculate the product of those two probabilities as given

below:

Good fit for both document and word for topic 2 (area is greater) than topic 1. So, our new
assignment for word bank will be topic 2.
Now, we will update the count due to new
assignment.

Now we will repeat the same step of reassignment. and iterate through each word of the
whole
corpus.
 dimensioN from 2to
t
Ue PCA to teduce

teatue E2 EE3 E4 4

13

SLep
No Af featur& n= 2
No. af Samples NE
Step2
variables
Compule mean e
= 4 8_t 3 t 7 4 8S
8 5

t +4++5. +tt/4

Step3
CompLatia_Co-var Ma tri
EY
Ordered pairs Caz) (a1H) CY2)

a_erederee pairS
Co-Yar ap

Cov( ) N- C ie-2 (zjk-

Ch-8)t l8-s)+ C13-5-
 covC)-
4-81-8.5) +(8-8) (1-86)4
Ca-8(5-8 5) +(-4)CFR

23
( CO-Var mahia_ O sle hxn [Link]-
Cov(12) Covla)

t o v ) cov (H)|

-U

- -I 23

SEep 4
COn&Lrualeigen value eign vecke
Noxmalized_ eigen vecter
i g e nv a t t
i d o n h t m a - l n r

d claen value
d e t (s-XT)=o

dt| 23-
 Ct4-) C29-A) - C-12 (-u) to
vot

31At 20 6 ya
31

30. 3sy9 6151

>a2
PCE
targest elgen valtue

Elaen ector e A

t
23-A
U

4-A)u-lu2
-u + (23 - 2 4 2

-Au1lU20
T-
lu L23-A)Ua

u2
L-A

eigen ector U of t- 1)1

ON 38ed
- S-dayt 1.399
4-3o 38
 (I2 NOImalize
eign ve clor
11/Jb
- 16-38 9

Vi+(-6.38) 2
=05514
-O. 303

e2- . s303
to.sST4

Step 5 Derie nec dalag4

E3 E

PCh P2 P3 PIq
P e 8 Lo551-o. 903J.
-85

- 2052
8-8
P12 b:564 8303 3. 134
4-85

P3 5.L22s
P4 S-4238
ON 28ed Pc -4-3or233SL S
Introduction to latent variable models
lecture 1

Francesco Bartolucci
Department of Economics, Finance and Statistics
University of Perugia, IT
bart@[Link]
 [2/24]

Outline

• Latent variables and their use

• Some example datasets

• A general formulation of latent variable models

• The Expectation-Maximization algorithm for maximum likelihood

estimation

• Finite mixture model (with example of application)

• Latent class and latent regression models (with examples of

application)
Latent variables and their use [3/24]

Latent variable and their use

• A latent variable is a variable which is not directly observable and is

assumed to affect the response variables (manifest variables)

• Latent variables are typically included in an econometric/statistical

model (latent variable model) with different aims:

. representing the effect of unobservable covariates/factors and then

accounting for the unobserved heterogeneity between subjects
(latent variables are used to represent the effect of these
unobservable factors)

. accounting for measurement errors (the latent variables represent

the “true” outcomes and the manifest variables represent their
“disturbed” versions)
Latent variables and their use [4/24]

. summarizing different measurements of the same (directly)

unobservable characteristics (e.g., quality-of-life), so that sample
units may be easily ordered/classified on the basis of these traits
(represented by the latent variables)

• Latent variable models have now a wide range of applications,

especially in the presence of repeated observations, longitudinal/panel
data, and multilevel data

• These models are typically classified according to:

. nature of the response variables (discrete or continuous)

. nature of the latent variables (discrete or continuous)
. inclusion or not of individual covariates
Latent variables and their use [5/24]

Most well-known latent variable models

• Factor analysis model: fundamental tool in multivariate statistic to
summarize several (continuous) measurements through a small
number of (continuous) latent traits; no covariates are included

• Item Response Theory models: models for items (categorical

responses) measuring a common latent trait assumed to be
continuous (or less often discrete) and typically representing an
ability or a psychological attitude; the most important IRT model
was proposed by Rasch (1961); typically no covariates are included

• Generalized linear mixed models (random-effects models): extension

of the class of Generalized linear models (GLM) for continuous or
categorical responses which account for unobserved heterogeneity,
beyond the effect of observable covariates
Latent variables and their use [6/24]

• Finite mixture model: model, used even for a single response variable,
in which subjects are assumed to come from subpopulations having
different distributions of the response variables; typically covariates
are ruled out

• Latent class model: model for categorical response variables based on

a discrete latent variable, the levels of which correspond to latent
classes in the population; typically covariates are ruled out

• Finite mixture regression model (Latent regression model): version of

the finite mixture (or latent class model) which includes observable
covariates affecting the conditional distribution of the response
variables and/or the distribution of the latent variables
Latent variables and their use [7/24]

• Models for longitudinal/panel data based on a state-space

formulation: models in which the response variables (categorical or
continuous) are assumed to depend on a latent process made of
continuous latent variables

• Latent Markov models: models for longitudinal data in which the

response variables are assumed to depend on an unobservable Markov
chain, as in hidden Markov models for time series; covariates may be
included in different ways

• Latent Growth/Curve models: models based on a random effects

formulation which are used the study of the evolution of a
phenomenon across of time on the basis of longitudinal data;
covariates are typically ruled out
Latent variables and their use [8/24]

Some example datasets

• Dataset 1: it consists of 500 observations simulated from a model

with 2 components

• By a finite mixture model we can estimate separate parameters for

these components and classify sample units (model-based clustering)
Latent variables and their use [9/24]

• Dataset 2: it is collected on 216 subjects who responded to T = 4

items concerning similar social aspects (Goodman, 1974, Biometrika)

• Data may be represented by a 24-dimensional vector of frequencies

for all the response configurations
   
freq(0000) 42
   
 freq(0001)   23 
n=  ..
= 
  .. 
   
freq(1111) 20

• By a latent class model we can classify subjects in homogeneous

clusters on the basis of the tendency measured by the items
Latent variables and their use [10/24]

• Dataset 3: about 1,093 elderly people, admitted in 2003 to 11

nursing homes in Umbria (IT), who responded to 9 items about their
health status:
Item %

1 [CC1] Does the patient show problems in recalling what

recently happened (5 minutes)? 72.6
2 [CC2] Does the patient show problems in making decisions
regarding tasks of daily life? 64.2
3 [CC3] Does the patient have problems in being understood? 43.9
4 [ADL1] Does the patient need support in moving to/from lying position,
turning side to side and positioning body while in bed? 54.4
5 [ADL2] Does the patient need support in moving to/from bed, chair,
wheelchair and standing position? 59.0
6 [ADL3] Does the patient need support for eating? 28.7
7 [ADL4] Does the patient need support for using the toilet room? 63.5
8 [SC1] Does the patient show presence of pressure ulcers? 15.4
9 [SC2] Does the patient show presence of other ulcers? 23.1
Latent variables and their use [11/24]

• Binary responses to items are coded so that 1 is a sign of bad health

conditions

• The available covariates are:

. gender (0 = male, 1 = female)

. 11 dummies for the nursing homes
. age

• By a latent class regression model we can understand how the

covariates affect the probability of belonging to the different latent
classes (corresponding to different levels of the health status)
General formulation of latent variable models [12/24]

A general formulation of latent variable models

• The contexts of application dealt with are those of:
. observation of different response variables at the same occasion
(e.g. item responses)
. repeated observations of the same response variable at consecutive
occasions (longitudinal/panel data); this is related to the multilevel
case in which subjects are collected in clusters

• Basic notation:
. n: number of sample units (or clusters in the multilevel case)
. T : number of response variables (or observations of the same
response variable) for each subject
. yit: response variable of type t (or at occasion t) for subject i
. xit: corresponding column vector of covariates
General formulation of latent variable models [13/24]

• A latent variable model formulates the conditional distribution of the

response vector y i = (yi1, . . . , yiT )0, given the covariates (if there
are) in X i = (xi1, . . . , xiT ) and a vector ui = (ui1, . . . , uil)0 of
latent variables

• The model components of main interest concern:

. conditional distribution of the response variables given X i and ui

(measurement model): p(y i|ui, X i)
. distribution of the latent variables given the covariates (latent
model): p(ui|X i)

• With T > 1, a crucial assumption is typically that of (local

independence): the response variables in y i are conditionally
independent given X i and ui
General formulation of latent variable models [14/24]

• The marginal distribution of the response variables (manifest

distribution) is obtained as
Z
p(y i|X i) = p(y i|ui, X i)p(ui|X i)dui

• This distribution may be explicitly computed with discrete latent

variables, when the integral becomes a sum

• With continuous latent variables the integral may be difficult to

compute and quadrature or Monte Carlo methods are required

• The conditional distribution of the latent variables given the

responses (posterior distribution) is
p(y i|ui, X i)p(ui|X i)
p(ui|X i, y i) =
p(y i|X i)
General formulation of latent variable models [15/24]

Case of discrete latent variables

(finite mixture model, latent class model)

• Each vector ui has a discrete distribution with k support point

ξ 1, . . . , ξ k and corresponding probabilities π1(X i), . . . , πk (X i)
(possibly depending on the covariates)

• The manifest distribution is then

X
p(y i|X i) = πcp(y i|ui = ξ c, X i) without covariates
c
X
p(y i|X i) = πc(X i)p(y i|ui = ξ c, X i) with covariates
c

• Model parameters are typically the support points ξ c, the mass

probabilities πc and parameters common to all the distributions
General formulation of latent variable models [16/24]

Example: Finite mixture of Normal distributions

with common variance
• There is only one latent variable (l = 1) having k support points and
no covariates are included

• Each support point ξ c corresponds to a mean µc and there is a

common variance-covariance matrix Σ
P
• The manifest distribution of y i is: p(y i) = c πcφ(y i; µc, Σ)

. φ(y; µ, Σ): density function of the multivariate Normal distribution

with mean µ and variance-covariance matrix Σ

• Exercise: write down the density of the model in the univariate case
with k = 2 and represent it for different parameter values
General formulation of latent variable models [17/24]

Case of continuous latent variables

(Generalized linear mixed models)
• With only one latent variable (l = 1), the integral involved in the
manifest distribution is approximated by a sum (quadrature method):
X
p(y i|X i) ≈ πcp(y i|ui = ξc, X i)
c

• In this case the nodes ξc and the corresponding weights πc are a priori
fixed; a few nodes are usually enough for an adequate approximation

• With more latent variables (l > 1), the quadrature method may be
difficult to implement and unprecise; a Monte Carlo method is
preferable in which the integral is approximated by a mean over a
sample drawn from the distribution of ui
General formulation of latent variable models [18/24]

Example: Logistic model with random effect

• There is only one latent variable ui (l = 1), having Normal

distribution with mean µ and variance σ 2

• The distribution of the response variables given the covariates is

exp[yit(ui + x0itβ)]
p(yit|ui, X i) = p(yit|ui, xit) =
1 + exp(ui + x0itβ)

and local independence is assumed

• The manifest distribution of the response variables is

Z Y
p(y i|X i) = [ p(yit|ui, xit)]φ(ui; µ, σ 2)dui
t
General formulation of latent variable models [19/24]

• In order to compute the manifest distribution it is convenient to

reformulate the model as
exp(uiσ + x0itβ)
p(yit|ui, xit) = 0 ,
1 + exp(uiσ + xitβ)
where ui ∼ N (0, 1) and µ has been absorbed into the intercept in β

• The manifest distribution is computed as

X Y
p(y i|X i) = πc p(yit|ui = ξc, xit)
c t

. ξ1, . . . , ξk : grid of points between, say, -5 and 5

φ(ξc; 0, 1)
. π1, . . . , πk : mass probabilities computed as πc = P
d φ(ξd; 0, 1)

• Exercise: implement a function to compute the manifest distribution

with T = 1 and one covariate; try different values of µ and σ 2
Expectation-Maximization paradigm [20/24]

The Expectation-Maximization (EM) paradigm for

maximum likelihood estimation
• This is a general approach for maximum likelihood estimation in the
presence of missing data (Dempster et al., 1977, JRSS-B)

• In our context, missing data correspond to the latent variables, then:

. incomplete (observable) data: covariates and response variables
(X, Y )
. complete (unobservable) data: incomplete data + latent variables
(U , X, Y )

• The corresponding log-likelihood functions are:

X X
∗
`(θ) = log p(y i|X i), ` (θ) = log[p(y i|ui, X i)p(ui|X i)]
i i
Expectation-Maximization paradigm [21/24]

• The EM algorithm maximizes `(θ) by alternating two steps until

convergence (h=iteration number):

. E-step: compute the expect value of `∗(θ) given the current

parameter value θ (h−1) and the observed data, obtaining

Q(θ|θ (h−1)) = E[`∗(θ)|X, Y , θ (h−1)]

. M-step: maximize Q(θ|θ (h−1)) with respect to θ obtaining θ (h)

• Convergence is checked on the basis of the difference

`(θ (h)) − `(θ (h−1)) or kθ (h) − θ (h−1)k

• The algorithm is usually easy to implement with respect to

Newton-Raphson algorithms, but it is usually much slower
Expectation-Maximization paradigm [22/24]

Case of discrete latent variables

• It is convenient to introduce the dummy variables zic, i = 1, . . . , n,
c = 1, . . . , k, with (
1 if ui = ξ c
zic =
0 otherwise

• The compute log-likelihood may then be expressed as

XX
∗
` (θ) = zic log[πc(X i)p(y i|ui = ξ c, X i)]
i c

• The corresponding conditional expected value is then computed as

XX
(h−1)
Q(θ|θ )= ẑic log[πc(X i)p(y i|ui = ξ c, X i)]
i c

. ẑic: posterior expected value of ui = ξ c

Expectation-Maximization paradigm [23/24]

• The posterior expected value ẑic is computed as

(h−1) πc(X i)p(y i|ui = ξ c, X i)
ẑic = p(zic = 1|X, Y , θ̂ )=P
d πd(X i)p(y i|ui = ξ d, X i)

• The EM algorithm is much simpler to implement with respect to the

general case; its steps become:
. E-step: compute the expected values ẑic for every i and c
. M-step: maximize Q(θ|θ (h−1)) with respect to θ, obtaining θ (h)

• A similar algorithm may be adopted, as an alternative to a

Newton-Raphson algorithm, for a model with continuous latent
variables when the manifest distribution is computed by quadrature

• Exercise: show how to implement the algorithm for the finite mixture
of Normal distributions with common variance (try simulated data)
Latent class and latent regression model [24/24]

Latent class and latent regression model

• These are models for categorical response variables (typically binary)
based on a single discrete latent variable

• For each level ξc of the latent variable there is a specific conditional

distribution of yit

• In the latent regression version the mass probabilities (conditional

distribution of each yit) are allowed to depend on individual
covariates (e.g. multinomial logit parameterization)

• Exercise: write down the manifest distribution of the latent class

model for binary response variables and binary latent variable

• Exercise: implement the EM algorithm for the latent class model (try
on the Goodman (1974) dataset)
Latent class and latent regression model [25/24]

Latent regression model

• Two possible choices to include individual covariates:
1. on the measurement model so that we have random intercepts (via
a logit or probit parametrization):

λitc = p(yit = 1|ui = ξc, X i),

λitc
log = ξc + x0itβ, i = 1, . . . , n, t = 1, . . . , T, c = 1, . . . , k
1 − λitc
2. on the model for the distribution of the latent variables (via a
multinomial logit parameterization):
πic
πic = p(ui = ξc|X i), log = x0itβ c, c = 2, . . . , k
πi1
• Alternative parameterizations are possible with ordinal response
variables or ordered latent classes
Latent class and latent regression model [26/24]

• The models based on the two extensions have a different

interpretation:

1. the latent variables are used to account for the unobserved

heterogeneity and then the model may be seen as discrete version
of the logistic model with one random effect
2. the main interest is on a latent variable which is measured through
the observable response variables (e.g. health status) and on how
this latent variable depends on the covariates

• Only the M-step of the EM algorithm must be modified by exploiting

standard algorithms for the maximization of:

1. the weighed likelihood of a logit model

2. the likelihood of a multinomial logit model
Latent class and latent regression model [27/24]

• Exercise: write down the manifest distribution of the latent regression

model for binary response variables and binary latent variable

• Exercise: show how to implement (and implement) the EM algorithm

for a latent class model for binary response variables (try with the
elderly people dataset)
 UNIT V

ADVANCED LEARNING

Reinforcement Learning – Representation Learning – Neural Networks – Active

Learning – Ensemble Learning – Bootstrap Aggregation – Boosting – Gradient
Boosting Machines – Deep Learning

REINFORCEMENT LEARNING:

Reinforcement Learning is a feedback-based Machine learning

technique in which an agent learns to behave in an environment by performing
the actions and seeing the results of actions. For each good action, the agent gets
positive feedback, and for each bad action, the agent gets negative feedback or
penalty.
​In Reinforcement Learning, the agent learns automatically using feedbacks without
any labeled data, unlike supervised learning.
​Since there is no labeled data, so the agent is bound to learn by its experience only.
​RL solves a specific type of problem where decision making is sequential, and the
goal is long-term, such as game-playing, robotics, etc.
​ he agent interacts with the environment and explores it by itself. The primary goal
T
of an agent in reinforcement learning is to improve the performance by getting the
maximum positive rewards.
​The agent learns with the process of hit and trial, and based on the experience, it
learns to perform the task in a better way. Hence, we can say that "Reinforcement
learning is a type of machine learning method where an intelligent agent
(computer program) interacts with the environment and learns to act within
that." How a Robotic dog learns the movement of his arms is an example of
Reinforcement learning.
I​ t is a core part of Artificial intelligence, and all AI agent works on the concept of
reinforcement learning. Here we do not need to pre-program the agent, as it learns
from its own experience without any human intervention.
​Example: Suppose there is an AI agent present within a maze environment, and his
goal is to find the diamond. The agent interacts with the environment by performing
some actions, and based on those actions, the state of the agent gets changed, and it
also receives a reward or penalty as feedback.
​The agent continues doing these three things (take action, change state/remain in
the same state, and get feedback), and by doing these actions, he learns and
explores the environment.
​ he agent learns that what actions lead to positive feedback or rewards and what
T
actions lead to negative feedback penalty. As a positive reward, the agent gets a
positive point, and as a penalty, it gets a negative point.

Approaches to implement Reinforcement Learning:

There are mainly three ways to implement reinforcement-learning in ML, which are:

1. Value-based:
The value-based approach is about to find the optimal value function, which is
the maximum value at a state under any policy. Therefore, the agent expects
the long-term return at any state(s) under policy π.

2. Policy-based:
Policy-based approach is to find the optimal policy for the maximum future
rewards without using the value function. In this approach, the agent tries to
apply such a policy that the action performed in each step helps to maximize
the future reward.
The policy-based approach has mainly two types of policy:

○ Deterministic: The same action is produced by the policy (π) at any

state.

○ Stochastic: In this policy, probability determines the produced action.

3. Model-based: In the model-based approach, a virtual model is created for the

environment, and the agent explores that environment to learn it. There is no
particular solution or algorithm for this approach because the model
representation is different for each environment.

Reinforcement Learning Working:

To understand the working process of the RL, we need to consider two main things:
 ○ Environment: It can be anything such as a room, maze, football ground, etc.

○ Agent: An intelligent agent such as AI robot.

Let's take an example of a maze environment that the agent needs to explore.
Consider the below image:

In the above image, the agent is at the very first block of the maze. The maze is
consisting of an S6 block, which is a wall, S8 a fire pit, and S4 a diamond block.

The agent cannot cross the S6 block, as it is a solid wall. If the agent reaches the S4
block, then get the +1 reward; if it reaches the fire pit, then gets -1 reward point. It
can take four actions: move up, move down, move left, and move right.

The agent can take any path to reach to the final point, but he needs to make it in
possible fewer steps. Suppose the agent considers the path S9-S5-S1-S2-S3, so he
will get the +1-reward point.
The agent will try to remember the preceding steps that it has taken to reach the final
step. To memorize the steps, it assigns 1 value to each previous step. Consider the
below step:

Now, the agent has successfully stored the previous steps assigning the 1 value to
each previous block. But what will the agent do if he starts moving from the block,
which has 1 value block on both sides? Consider the below diagram:
It will be a difficult condition for the agent whether he should go up or down as each
block has the same value. So, the above approach is not suitable for the agent to
reach the destination. Hence to solve the problem, we will use the Bellman
equation, which is the main concept behind reinforcement learning.

The Bellman Equation:

The Bellman equation was introduced by the Mathematician Richard Ernest

Bellman in the year 1953, and hence it is called as a Bellman equation. It is
associated with dynamic programming and used to calculate the values of a decision
problem at a certain point by including the values of previous states.

It is a way of calculating the value functions in dynamic programming or

environment that leads to modern reinforcement learning.

The key-elements used in Bellman equations are:

 ○ Action performed by the agent is referred to as "a"

○ State occurred by performing the action "s."

○ The reward/feedback obtained for each good and bad action is "R."

○ A discount factor is Gamma "γ."

The Bellman equation can be written as:

1. V(s) = max [R(s,a) + γV(s`)]

Where,

V(s)= value calculated at a particular point.

R(s,a) = Reward at a particular state s by performing an action.

γ = Discount factor

V(s`) = The value at the previous state.

In the above equation, we are taking the max of the complete values because the
agent tries to find the optimal solution always.

So now, using the Bellman equation, we will find value at each state of the given
environment. We will start from the block, which is next to the target block.

For 1st block:

V(s3) = max [R(s,a) + γV(s`)], here V(s')= 0 because there is no further state to
move.

V(s3)= max[R(s,a)]=> V(s3)= max[1]=> V(s3)= 1.

For 2nd block:

V(s2) = max [R(s,a) + γV(s`)], here γ= 0.9(lets), V(s')= 1, and R(s, a)= 0, because
there is no reward at this state.

V(s2)= max[0.9(1)]=> V(s)= max[0.9]=> V(s2) =0.9

For 3rd block:

V(s1) = max [R(s,a) + γV(s`)], here γ= 0.9(lets), V(s')= 0.9, and R(s, a)= 0, because
there is no reward at this state also.

V(s1)= max[0.9(0.9)]=> V(s3)= max[0.81]=> V(s1) =0.81

For 4th block:

V(s5) = max [R(s,a) + γV(s`)], here γ= 0.9(lets), V(s')= 0.81, and R(s, a)= 0, because
there is no reward at this state also.

V(s5)= max[0.9(0.81)]=> V(s5)= max[0.81]=> V(s5) =0.73

For 5th block:

V(s9) = max [R(s,a) + γV(s`)], here γ= 0.9(lets), V(s')= 0.73, and R(s, a)= 0, because
there is no reward at this state also.

V(s9)= max[0.9(0.73)]=> V(s4)= max[0.81]=> V(s4) =0.66

Consider the below image:

Now, we will move further to the 6th block, and here agent may change the route
because it always tries to find the optimal path. So now, let's consider from the block
next to the fire pit.
Now, the agent has three options to move; if he moves to the blue box, then he will
feel a bump if he moves to the fire pit, then he will get the -1 reward. But here we are
taking only positive rewards, so for this, he will move upwards only. The complete
block values will be calculated using this formula. Consider the below image:
Types of Reinforcement learning:

There are mainly two types of reinforcement learning, which are:

○ Positive Reinforcement

○ Negative Reinforcement

Positive Reinforcement:

The positive reinforcement learning means adding something to increase the

tendency that expected behavior would occur again. It impacts positively on the
behavior of the agent and increases the strength of the behavior.

This type of reinforcement can sustain the changes for a long time, but too much
positive reinforcement may lead to an overload of states that can reduce the
consequences.

Negative Reinforcement:
The negative reinforcement learning is opposite to the positive reinforcement as it
increases the tendency that the specific behavior will occur again by avoiding the
negative condition.

It can be more effective than positive reinforcement depending on situation and

behavior, but it provides reinforcement only to meet minimum behavior.

Reinforcement Learning Algorithms:

Reinforcement learning algorithms are mainly used in AI applications and gaming

applications. The main used algorithms are:

○ Q-Learning:

○ Q-learning is an Off policy RL algorithm, which is used for temporal

difference Learning. The temporal difference learning methods are the
way of comparing temporally successive predictions.

○ It learns the value function Q (S, a), which means how good to take
action "a" at a particular state "s."

○ The below flowchart explains the working of Q- learning:

○ State Action Reward State action (SARSA):

○ SARSA stands for State Action Reward State action, which is an

on-policy temporal difference learning method. The on-policy control
method selects the action for each state while learning using a specific
policy.

○ The goal of SARSA is to calculate the Q π (s, a) for the selected

current policy π and all pairs of (s-a).

○ The main difference between Q-learning and SARSA algorithms is that

unlike Q-learning, the maximum reward for the next state is not
required for updating the Q-value in the table.

○ In SARSA, new action and reward are selected using the same policy,
which has determined the original action.

○ SARSA is named because it uses the quintuple Q(s, a, r, s', a'). Where,
s: original state
 a: Original action
r: reward observed while following the states
s' and a': New state, action pair.

○ Deep Q Neural Network (DQN):

○ As the name suggests, DQN is Q-learning using Neural networks.

○ For a big state space environment, it will be a challenging and complex

task to define and update a Q-table.

○ To solve such an issue, we can use a DQN algorithm. Where, instead of

defining a Q-table, neural network approximates the Q-values for each
action and state.

Now, we will expand Q-learning.

Q-Learning Explanation:

○ Q-learning is a popular model-free reinforcement learning algorithm based on

the Bellman equation.

○ The main objective of Q-learning is to learn the policy which can inform
the agent what actions should be taken for maximizing the reward under
what circumstances.

○ It is an off-policy RL that attempts to find the best action to take at a current

state.

○ The goal of the agent in Q-learning is to maximize the value of Q.

○ The value of Q-learning can be derived from the Bellman equation. Consider
the Bellman equation given below:
In the equation, we have various components, including reward, discount factor (γ),
probability, and end states s'. But there is no any Q-value is given so first consider the
below image:

In the above image, we can see there is an agent who has three values options, V(s1),
V(s2), V(s3). As this is MDP, the agent only cares for the current state and the future
state. The agent can go in any direction (Up, Left, or Right), so he needs to decide
where to go for the optimal path. Here the agent will take a move as per probability
bases and change the state. But if we want some exact moves, for this, we need to
make some changes in terms of Q-value. Consider the below image:
Q- represents the quality of the actions at each state. So instead of using a value at
each state, we will use a pair of state and action, i.e., Q(s, a). Q-value specifies which
action is more lubricated than others, and according to the best Q-value, the agent
takes his next move. The Bellman equation can be used for deriving the Q-value.

To perform any action, the agent will get a reward R(s, a), and also he will end up on
a certain state, so the Q -value equation will be:

Hence, we can say that, V(s) = max [Q(s, a)]

The above formula is used to estimate the Q-values in Q-Learning.

What is 'Q' in Q-learning?

The Q stands for quality in Q-learning, which means it specifies the quality of an
action taken by the agent.

Q-table:

A Q-table or matrix is created while performing the Q-learning. The table follows the
state and action pair, i.e., [s, a], and initializes the values to zero. After each action,
the table is updated, and the q-values are stored within the table.

The RL agent uses this Q-table as a reference table to select the best action based on
the q-values.

Reinforcement Learning Applications:

1. Robotics:

a. RL is used in Robot navigation, Robo-soccer, walking, juggling, etc.

2. Control:

a. RL can be used for adaptive control such as Factory processes,

admission control in telecommunication, and Helicopter pilot is an
example of reinforcement learning.

3. Game Playing:

a. RL can be used in Game playing such as tic-tac-toe, chess, etc.

4. Chemistry:

a. RL can be used for optimizing the chemical reactions.

5. Business:

a. RL is now used for business strategy planning.

6. Manufacturing:
 a. In various automobile manufacturing companies, the robots use deep
reinforcement learning to pick goods and put them in some containers.

7. Finance Sector:

a. The RL is currently used in the finance sector for evaluating trading

strategies.

REPRESENTATION LEARNING:

Representation learning is a very important aspect of machine learning which

automatically discovers the feature patterns in the data. When the machine is
provided with the data, it learns the representation itself without any human
intervention. The goal of representation learning is to train machine learning
algorithms to learn useful representations, such as those that are interpretable,
incorporate latent features, or can be used for transfer learning.

In representation learning, data is sent into the machine, and it learns the
representation on its own. It is a way of determining a data representation of the
features, the distance function, and the similarity function that determines how the
predictive model will perform. Representation learning works by reducing
high-dimensional data to low-dimensional data, making it easier to discover patterns
and anomalies while also providing a better understanding of the data’s overall
behaviour.

Basically, Machine learning tasks such as classification frequently demand input that
is mathematically and computationally convenient to process, which motivates
representation learning. Real-world data, such as photos, video, and sensor data, has
resisted attempts to define certain qualities algorithmically. An approach is to
examine the data for such traits or representations rather than depending on explicit
techniques.

Methods of Representation Learning

We must employ representation learning to ensure that the model provides invariant
and untangled outcomes in order to increase its accuracy and performance. In this
section, we’ll look at how representation learning can improve the model’s
performance in three different learning frameworks: supervised learning,
unsupervised learning.

Supervised Learning
This is referred to as supervised learning when the ML or DL model maps the input
X to the output Y. The computer tries to correct itself by comparing model output to
ground truth, and the learning process optimizes the mapping from input to output.
This process is repeated until the optimization function reaches global minima.

Even when the optimization function reaches the global minima, new data does not
always perform well, resulting in overfitting. While supervised learning does not
necessitate a significant amount of data to learn the mapping from input to output, it
does necessitate the learned features. The prediction accuracy can improve by up to
17 percent when the learned attributes are incorporated into the supervised learning
algorithm.

Using labelled input data, features are learned in supervised feature learning.
Supervised neural networks, multilayer perceptrons, and (supervised) dictionary
learning are some examples.

Unsupervised Learning
Unsupervised learning is a sort of machine learning in which the labels are ignored in
favour of the observation itself. Unsupervised learning isn’t used for classification or
regression; instead, it’s used to uncover underlying patterns, cluster data, denoise it,
detect outliers, and decompose data, among other things.

When working with data x, we must be very careful about whatever features z we use
to ensure that the patterns produced are accurate. It has been observed that having
more data does not always imply having better representations. We must be careful to
develop a model that is both flexible and expressive so that the extracted features can
convey critical information.
Unsupervised feature learning learns features from unlabeled input data by following
the methods such as Dictionary learning, independent component analysis,
autoencoders, matrix factorization, and various forms of clustering are among
examples.

In the next section, we will see more about these methods and workflow, how they
learn the representation in detail.

Supervised Methods

Supervised Dictionary Learning

Dictionary learning creates a set of representative elements (dictionary) from the
input data, allowing each data point to be represented as a weighted sum of the
representative elements. By minimizing the average representation error (across the
input data) and applying L1 regularization to the weights, the dictionary items and
weights may be obtained i.e., the representation of each data point has only a few
nonzero weights.

For optimizing dictionary elements, supervised dictionary learning takes advantage

of both the structure underlying the input data and the labels. The supervised
dictionary learning technique uses dictionary learning to solve classification issues
by optimizing dictionary elements, data point weights, and classifier parameters
based on the input data.

A minimization problem is formulated, with the objective function consisting of the

classification error, the representation error, an L1 regularization on the representing
weights for each data point (to enable sparse data representation), and an L2
regularization on the parameters of the classification algorithm.

Multi-Layer Perceptron
The perceptron is the most basic neural unit, consisting of a succession of inputs and
weights that are compared to the ground truth. A multi-layer perceptron, or MLP, is a
feed-forward neural network made up of layers of perceptron units. MLP is made up
of three-node layers: an input, a hidden layer, and an output layer. MLP is commonly
referred to as the vanilla neural network because it is a very basic artificial neural
network.

This notion serves as a foundation for hidden variables and representation learning.
Our goal in this theorem is to determine the variables or required weights that can
represent the underlying distribution of the entire data so that when we plug those
variables or required weights into unknown data, we receive results that are almost
identical to the original data. In a word, artificial neural networks (ANN) assist us in
extracting meaningful patterns from a dataset.

Neural Networks
Neural networks are a class of learning algorithms that employ a “network” of
interconnected nodes in various layers. It’s based on the animal nervous system, with
nodes resembling neurons and edges resembling synapses. The network establishes
computational rules for passing input data from the network’s input layer to the
network’s output layer, and each edge has an associated weight.

The relationship between the input and output layers, which is parameterized by the
weights, is described by a network function associated with a neural network.
Various learning tasks can be achieved by minimizing a cost function over the
network function (w) with correctly defined network functions.

Unsupervised Methods
Learning Representation from unlabeled data is referred to as unsupervised feature
learning. Unsupervised Representation learning frequently seeks to uncover
low-dimensional features that encapsulate some structure beneath the
high-dimensional input data.

K-Means Clustering
K-means clustering is a vector quantization approach. An n-vector set is divided into
k clusters (i.e. subsets) via K-means clustering, with each vector belonging to the
cluster with the closest mean. Despite the use of inferior greedy techniques, the
problem is computationally NP-hard.

K-means clustering divides an unlabeled collection of inputs into k groups before

obtaining centroids-based features. These characteristics can be honed in a variety of
ways. The simplest method is to add k binary features to each sample, with each
feature j having a value of one of the k-means learned jth centroid is closest to the
sample under consideration. Cluster distances can be used as features after being
processed with a radial basis function.

Local Linear Embedding

LLE is a nonlinear learning strategy for constructing low-dimensional
neighbour-preserving representations from high-dimensional (unlabeled) input.
LLE’s main goal is to reconstruct high-dimensional data using lower-dimensional
points while keeping some geometric elements of the original data set’s neighbours.

There are two major steps in LLE. The first step is “neighbour-preserving,” in which
each input data point Xi is reconstructed as a weighted sum of K nearest neighbour
data points, with the optimal weights determined by minimizing the average squared
reconstruction error (i.e., the difference between an input point and its reconstruction)
while keeping the weights associated with each point equal to one.
The second stage involves “dimension reduction,” which entails searching for vectors
in a lower-dimensional space that reduce the representation error while still using the
optimal weights from the previous step.

The weights are optimized given fixed data in the first stage, which can be solved as
a least-squares problem. Lower-dimensional points are optimized with fixed weights
in the second phase, which can be solved using sparse eigenvalue decomposition.

Unsupervised Dictionary Mining

For optimizing dictionary elements, unsupervised dictionary learning does not use
data labels and instead relies on the structure underlying the data. Sparse coding,
which seeks to learn basic functions (dictionary elements) for data representation
from unlabeled input data, is an example of unsupervised dictionary learning.

When the number of vocabulary items exceeds the dimension of the input data,
sparse coding can be used to learn overcomplete dictionaries. K-SVD is an algorithm
for learning a dictionary of elements that allows for sparse representation.

Deep Architectures Methods

Deep learning architectures for feature learning are inspired by the hierarchical
architecture of the biological brain system, which stacks numerous layers of learning
nodes. The premise of distributed representation is typically used to construct these
architectures: observable data is generated by the interactions of many diverse
components at several levels.

Restricted Boltzmann Machine (RBMs)

In multilayer learning frameworks, RBMs (restricted Boltzmann machines) are
widely used as building blocks. An RBM is a bipartite undirected network having a
set of binary hidden variables, visible variables, and edges connecting the hidden and
visible nodes. It’s a variant of the more general Boltzmann machines, with the added
constraint of no intra-node connections. In an RBM, each edge has a weight assigned
to it. The connections and weights define an energy function that can be used to
generate a combined distribution of visible and hidden nodes.
For unsupervised representation learning, an RBM can be thought of as a single-layer
design. The visible variables, in particular, relate to the input data, whereas the
hidden variables correspond to the feature detectors. Hinton’s contrastive divergence
(CD) approach can be used to train the weights by maximizing the probability of
visible variables.

Autoencoders
Deep network representations have been found to be insensitive to complex noise or
data conflicts. This can be linked to the architecture to some extent. The employment
of convolutional layers and max-pooling, for example, can be proven to produce
transformation insensitivity.

Autoencoders are therefore neural networks that may be taught to do representation

learning. Autoencoders seek to duplicate their input to their output using an encoder
and a decoder. Autoencoders are typically trained via recirculation, a learning process
that compares the activation of the input network to the activation of the
reconstructed input.

NEURAL NETWORKS:

A neural network is a method in artificial intelligence that teaches computers to

process data in a way that is inspired by the human brain. It is a type of machine
learning process, called deep learning, that uses interconnected nodes or neurons in a
layered structure that resembles the human brain. It creates an adaptive system that
computers use to learn from their mistakes and improve continuously. Thus, artificial
neural networks attempt to solve complicated problems, like summarizing documents
or recognizing faces, with greater accuracy.

How artificial neural networks work?

An ANN usually involves a large number of processors operating in parallel and

arranged in tiers. The first tier receives the raw input information -- analogous to
optic nerves in human visual processing. Each successive tier receives the output
from the tier preceding it, rather than the raw input -- in the same way neurons
further from the optic nerve receive signals from those closer to it. The last tier
produces the output of the system.

Each processing node has its own small sphere of knowledge, including what it has
seen and any rules it was originally programmed with or developed for itself. The
tiers are highly interconnected, which means each node in tier n will be connected to
many nodes in tier n-1 -- its inputs -- and in tier n+1, which provides input data for
those nodes. There may be one or multiple nodes in the output layer, from which the
answer it produces can be read.

Artificial neural networks are notable for being adaptive, which means they modify
themselves as they learn from initial training and subsequent runs provide more
information about the world. The most basic learning model is centered on weighting
the input streams, which is how each node weights the importance of input data from
each of its predecessors. Inputs that contribute to getting right answers are weighted
higher.

Simple neural network architecture

A basic neural network has interconnected artificial neurons in three layers:

Input Layer

Information from the outside world enters the artificial neural network from the input
layer. Input nodes process the data, analyze or categorize it, and pass it on to the next
layer.

Hidden Layer

Hidden layers take their input from the input layer or other hidden layers. Artificial
neural networks can have a large number of hidden layers. Each hidden layer
analyzes the output from the previous layer, processes it further, and passes it on to
the next layer.

Output Layer

The output layer gives the final result of all the data processing by the artificial
neural network. It can have single or multiple nodes. For instance, if we have a
binary (yes/no) classification problem, the output layer will have one output node,
which will give the result as 1 or 0. However, if we have a multi-class classification
problem, the output layer might consist of more than one output node.

Deep neural network architecture

Deep neural networks, or deep learning networks, have several hidden layers with
millions of artificial neurons linked together. A number, called weight, represents the
connections between one node and another. The weight is a positive number if one
node excites another, or negative if one node suppresses the other. Nodes with higher
weight values have more influence on the other nodes.
Theoretically, deep neural networks can map any input type to any output type.
However, they also need much more training as compared to other machine learning
methods. They need millions of examples of training data rather than perhaps the
hundreds or thousands that a simpler network might need.

Types of neural networks:

Artificial neural networks can be categorized by how the data flows from the input
node to the output node. Below are some examples:

Feedforward neural networks

Feedforward neural networks process data in one direction, from the input node to
the output node. Every node in one layer is connected to every node in the next layer.
A feedforward network uses a feedback process to improve predictions over time.

Backpropagation algorithm

Artificial neural networks learn continuously by using corrective feedback loops to

improve their predictive analytics. In simple terms, you can think of the data flowing
from the input node to the output node through many different paths in the neural
network. Only one path is the correct one that maps the input node to the correct
output node. To find this path, the neural network uses a feedback loop, which works
as follows:

1. Each node makes a guess about the next node in the path.

2. It checks if the guess was correct. Nodes assign higher weight values to paths
that lead to more correct guesses and lower weight values to node paths that
lead to incorrect guesses.
 3. For the next data point, the nodes make a new prediction using the higher
weight paths and then repeat Step 1.

Convolutional neural networks

The hidden layers in convolutional neural networks perform specific mathematical

functions, like summarizing or filtering, called convolutions. They are very useful for
image classification because they can extract relevant features from images that are
useful for image recognition and classification. The new form is easier to process
without losing features that are critical for making a good prediction. Each hidden
layer extracts and processes different image features, like edges, color, and depth.

Advantages of artificial neural networks

Advantages of artificial neural networks include:

● Parallel processing abilities mean the network can perform more than one
job at a time.

● Information is stored on an entire network, not just a database.

● The ability to learn and model nonlinear, complex relationships helps

model the real-life relationships between input and output.

● Fault tolerance means the corruption of one or more cells of the ANN will
not stop the generation of output.

● Gradual corruption means the network will slowly degrade over time,
instead of a problem destroying the network instantly.
 ● The ability to produce output with incomplete knowledge with the loss of
performance being based on how important the missing information is.

● No restrictions are placed on the input variables, such as how they should
be distributed.

● Machine learning means the ANN can learn from events and make
decisions based on the observations.

● The ability to learn hidden relationships in the data without commanding

any fixed relationship means an ANN can better model highly volatile data
and non-constant variance.

● The ability to generalize and infer unseen relationships on unseen data

means ANNs can predict the output of unseen data.

Disadvantages of artificial neural networks

The disadvantages of ANNs include:

● The lack of rules for determining the proper network structure means the
appropriate artificial neural network architecture can only be found through
trial and error and experience.

● The requirement of processors with parallel processing abilities makes

neural networks hardware-dependent.

● The network works with numerical information, therefore all problems

must be translated into numerical values before they can be presented to the
ANN.
 ● The lack of explanation behind probing solutions is one of the biggest
disadvantages in ANNs. The inability to explain the why or how behind the
solution generates a lack of trust in the network.

Applications of artificial neural networks

Image recognition was one of the first areas to which neural networks were
successfully applied, but the technology uses have expanded to many more areas,
including:

● Chatbots

● Natural language processing, translation and language generation

● Stock market prediction

● Delivery driver route planning and optimization

● Drug discovery and development

These are just a few specific areas to which neural networks are being applied today.
Prime uses involve any process that operates according to strict rules or patterns and
has large amounts of data. If the data involved is too large for a human to make sense
of in a reasonable amount of time, the process is likely a prime candidate for
automation through artificial neural networks.
ACTIVE LEARNING:

Active Learning is a special case of Supervised Machine Learning. This approach is

used to construct a high-performance classifier while keeping the size of the training
dataset to a minimum by actively selecting the valuable data points.

Active learning is the name used for the process of prioritising the data which needs

to be labelled in order to have the highest impact to training a supervised model.

Active learning can be used in situations where the amount of data is too large to be

labelled and some priority needs to be made to label the data in a smart way.

But, why don’t we just choose a random subset of data to manually label them?

Let’s look at a very simple example to motivate the discussion. Assume we have

millions of data points which need to be classified based on two features. The actual

solution is shown in the following plot:

 Model prediction if all data points were labelled

As one can see, both classes (red and purple) can quite nicely be separated by a

vertical blue line crossing at 0. The problem is that none of the data points are

labelled, so the data is given to us as in the following plot:

 Unlabelled data

Unfortunately, we don’t have enough time to label all of the data and we randomly

chose a subset of the data to label and train a binary classification model on it. The

result is not great, as the model prediction deviates quite a lot from the optimal

boundary.

Model trained on a random subset of labelled data points

This is where active learning can be used to optimise the data points chosen for

labelling and training a model based on them. The following plot shows an example

of training a binary classification model after choosing the training of the model

based on data points labelled after implementing active learning.

Model trained on a subset of data points chosen ho to be labelled using active
learning

Making a smart choice of which data points to prioritise when labelling can save data

science teams large amounts of time and computation

Active learning strategy

Steps for active learning

There are multiple approaches studied in the literature on how to prioritise data

points when labelling and how to iterate over the approach. We will nevertheless only

present the most common and straightforward methods.

The steps to use active learning on an unlabelled data set are:

 1. The first thing which needs to happen is that a very small subsample of

this data needs to be manually labelled.

2. Once there is a small amount of labelled data, the model needs to be

trained on it. The model is of course not going to be great but will help us

get some insight on which areas of the parameter space need to be labelled

first to improve it.

3. After the model is trained, the model is used to predict the class of each

remaining unlabelled data point.

4. A score is chosen on each unlabelled data point based on the prediction of

the model. In the next subsection we will present some of the possible

scores most commonly used.

5. Once the best approach has been chosen to prioritise the labelling, this

process can be iteratively repeated: a new model can be trained on a new

labelled data set, which has been labelled based on the priority score. Once

the new model has been trained on the subset of data, the unlabelled data

points can be ran through the model to update the prioritisation scores to

continue labelling. In this way, one can keep optimising the labelling

strategy as the models become better and better.

Prioritisation scores

There are several approaches to assign a priority score to each data point. Below we

describe the three basic ones.

Least confidence:

This is probably the most simple method. It takes the highest probability for each

data point’s prediction, and sorts them from smaller to larger. The actual expression

to prioritise using least confidence would be:

Let’s use an example to see how this would work. Assume we have the following

data with three possible classes:

Table 1: Example of probability predictions of a model on three different classes for

four different data points.
In this case, the algorithm would first chose the maximum probability for each data

point, hence:

● X1: 0.9

● X2: 0.87

● X3:0.5

● X4:0.99.

The second step is to sort the data based on this maximum probability (from smaller

to bigger), hence X3, X2, X1 and X4.

Margin sampling:

This method takes into account the difference between the highest probability and the

second highest probability. Formally, the expression to prioritise would look like:
The data points with the lower margin sampling score would be the ones labelled the

first; these are the data points the model is least certain about between the most

probably and the next-to-most probable class.

Following the example of Table 1, the corresponding scores for each data point are:

● X1: 0.9–0.07 = 0.83

● X2: 0.87–0.1 = 0.86

● X3: 0.5–0.3 = 0.2

● X4: 0.99–0.01 = 0.98

Hence the data points would be shown to label as follows: X3, X1, X2 and X4. As

one can see the priority in this case is slightly different to the least confident one.

Entropy:

Finally, the last scoring function that we are gonna present here is the entropy score.

Entropy is a concept that comes from thermodynamics; in a simple way, it can be

understood as a measure of disorder in a system, for instance a gas in a closed box.

The higher the entropy the more disorder there is, whereas if the entropy is low, it
means that the gas might be mainly in one particular area such as a corner of the box

(maybe when the experiment started, before expanding across the box).

This concept can be reused to measure the certainty of a model. If a model is highly

certain about a class for a given data point, it will probably have a high certainty for a

particular class, whereas all the other classes will have low probability. Isn’t this very

similar to having a gas in the corner of a box? In this case we have most of the

probability assigned to a particular class. In the case of high entropy it would mean

that the model distributes equally the probability for all classes as it is not certain at

all which class that data point belongs to, similarly to having the gas distributed

equally in all parts of the box. It is therefore straightforward to prioritise data points

with higher entropy to the ones with lower entropy.

Formally, we can define the entropy score prioritisation as follows:

If we apply the entropy score to the example in Table 1:

 ● X1: -0.9*log(0.9)-0.07*log(0.07)-0.03*log(0.03) = 0.386

● X2: -0.87*log(0.87)-0.03*log(0.03)-0.1*log(0.1) = 0.457

● X3: -0.2*log(0.2)-0.5*log(0.5)-0.3*log(0.3) =1.03

● X4: -0*log(0)-0.01*log(0.01)-0.99*log(0.99) = 0.056

Note that for X4, 0 should be changed for a small epsilon (e.g. 0.00001) for

numerical stability.

In this case the data points should be shown in the following order: X3, X2, X1 and

X4, which coincides with the order of the least confident scoring method.

ENSEMBLE LEARNING:

Ensemble learning helps improve machine learning results by combining several

models. This approach allows the production of better predictive performance
compared to a single model. Basic idea is to learn a set of classifiers (experts) and to
allow them to vote.
Advantage : Improvement in predictive accuracy.
Disadvantage : It is difficult to understand an ensemble of classifiers.
Why do ensembles work?
Dietterich(2002) showed that ensembles overcome three problems –
● Statistical Problem –
The Statistical Problem arises when the hypothesis space is too large for the
amount of available data. Hence, there are many hypotheses with the same
accuracy on the data and the learning algorithm chooses only one of them!
There is a risk that the accuracy of the chosen hypothesis is low on unseen
data!
● Computational Problem –
The Computational Problem arises when the learning algorithm cannot
guarantee finding the best hypothesis.
● Representational Problem –
The Representational Problem arises when the hypothesis space does not
contain any good approximation of the target class(es).

Main Challenge for Developing Ensemble Models?

The main challenge is not to obtain highly accurate base models, but rather to obtain
base models which make different kinds of errors. For example, if ensembles are
used for classification, high accuracies can be accomplished if different base models
misclassify different training examples, even if the base classifier accuracy is low.
Methods for Independently Constructing Ensembles –

● Majority Vote
● Bagging and Random Forest
● Randomness Injection
● Feature-Selection Ensembles
● Error-Correcting Output Coding

Methods for Coordinated Construction of Ensembles –

● Boosting
● Stacking

Reliable Classification: Meta-Classifier Approach

Co-Training and Self-Training

Types of Ensemble Classifier –

Bagging:

Bagging (Bootstrap Aggregation) is used to reduce the variance of a decision tree.

Suppose a set D of d tuples, at each iteration i, a training set Di of d tuples is sampled
with replacement from D (i.e., bootstrap). Then a classifier model Mi is learned for
each training set D < i. Each classifier Mi returns its class prediction. The bagged
classifier M* counts the votes and assigns the class with the most votes to X
(unknown sample).

Implementation steps of Bagging –

1. Multiple subsets are created from the original data set with equal tuples,
selecting observations with replacement.
 2. A base model is created on each of these subsets.
3. Each model is learned in parallel from each training set and independent of
each other.
4. The final predictions are determined by combining the predictions from all
the models.

5. Random Forest:Random Forest is an extension over bagging. Each classifier

in the ensemble is a decision tree classifier and is generated using a random
selection of attributes at each node to determine the split. During classification,
each tree votes and the most popular class is returned.

Implementation steps of Random Forest

1. Multiple subsets are created from the original data set, selecting observations
with replacement.
2. A subset of features is selected randomly and whichever feature gives the best
split is used to split the node iteratively.
3. The tree has grown to the largest.
4. Repeat the above steps and prediction is given based on the aggregation of
predictions from a number of trees.

BOOTSTRAP AGGREGATION:

Bagging, also known as bootstrap aggregation, is the ensemble learning method that
is commonly used to reduce variance within a noisy dataset. In bagging, a random
sample of data in a training set is selected with replacement—meaning that the
individual data points can be chosen more than once. After several data samples are
generated, these weak models are then trained independently, and depending on the
type of task—regression or classification, for example—the average or majority of
those predictions yield a more accurate estimate.

As a note, the random forest algorithm is considered an extension of the bagging

method, using both bagging and feature randomness to create an uncorrelated forest
of decision trees.

Ensemble learning

Ensemble learning gives credence to the idea of the “wisdom of crowds,” which
suggests that the decision-making of a larger group of people is typically better than
that of an individual expert. Similarly, ensemble learning refers to a group (or
ensemble) of base learners, or models, which work collectively to achieve a better
final prediction. A single model, also known as a base or weak learner, may not
perform well individually due to high variance or high bias. However, when weak
learners are aggregated, they can form a strong learner, as their combination reduces
bias or variance, yielding better model performance.

Ensemble methods are frequently illustrated using decision trees as this algorithm
can be prone to overfitting (high variance and low bias) when it hasn’t been pruned
and it can also lend itself to underfitting (low variance and high bias) when it’s very
small, like a decision stump, which is a decision tree with one level. Remember,
when an algorithm overfits or underfits to its training set, it cannot generalize well to
new datasets, so ensemble methods are used to counteract this behavior to allow for
generalization of the model to new datasets. While decision trees can exhibit high
variance or high bias, it’s worth noting that it is not the only modeling technique that
leverages ensemble learning to find the “sweet spot” within the bias-variance
tradeoff.

Bagging vs. boosting

Bagging and boosting are two main types of ensemble learning methods. The main
difference between these learning methods is the way in which they are trained. In
bagging, weak learners are trained in parallel, but in boosting, they learn sequentially.
This means that a series of models are constructed and with each new model
iteration, the weights of the misclassified data in the previous model are increased.
This redistribution of weights helps the algorithm identify the parameters that it
needs to focus on to improve its performance. AdaBoost, which stands for “adaptive
boosting algorithm,” is one of the most popular boosting algorithms as it was one of
the first of its kind. Other types of boosting algorithms include XGBoost,
GradientBoost, and BrownBoost.

Another difference in which bagging and boosting differ are the scenarios in which
they are used. For example, bagging methods are typically used on weak learners
which exhibit high variance and low bias, whereas boosting methods are leveraged
when low variance and high bias is observed.
How bagging works
In 1996, Leo Breiman introduced the bagging algorithm, which has three basic steps:

● Bootstrapping: Bagging leverages a bootstrapping sampling technique to

create diverse samples. This resampling method generates different subsets of the
training dataset by selecting data points at random and with replacement. This means
that each time you select a data point from the training dataset, you are able to select
the same instance multiple times. As a result, a value/instance repeated twice (or
more) in a sample.
● Parallel training: These bootstrap samples are then trained independently and
in parallel with each other using weak or base learners.
● Aggregation: Finally, depending on the task (i.e. regression or classification),
an average or a majority of the predictions are taken to compute a more accurate
estimate. In the case of regression, an average is taken of all the outputs predicted by
the individual classifiers; this is known as soft voting. For classification problems,
the class with the highest majority of votes is accepted; this is known as hard voting
or majority voting.

Benefits and challenges of bagging

There are a number of key advantages and challenges that the bagging method
presents when used for classification or regression problems. The key benefits of
bagging include:

​ ase of implementation: Python libraries such as scikit-learn (also known as sklearn)

E
make it easy to combine the predictions of base learners or estimators to improve
model performance. Their documentation (link resides outside IBM) lays out the
available modules that you can leverage in your model optimization.
​Reduction of variance: Bagging can reduce the variance within a learning algorithm.
This is particularly helpful with high-dimensional data, where missing values can
 lead to higher variance, making it more prone to overfitting and preventing accurate
generalization to new datasets.

The key challenges of bagging include:

​ Loss of interpretability: It’s difficult to draw very precise business insights through
bagging because of the averaging involved across predictions. While the output is
more precise than any individual data point, a more accurate or complete dataset
could also yield more precision within a single classification or regression model.
​ Computationally expensive: Bagging slows down and grows more intensive as the
number of iterations increases. Thus, it’s not well-suited for real-time applications.
Clustered systems or a large number of processing cores are ideal for quickly
creating bagged ensembles on large test sets.
​ Less flexible: As a technique, bagging works particularly well with algorithms that
are less stable. One that is more stable or subject to high amounts of bias do not
provide as much benefit as there’s less variation within the dataset of the model.

Applications of Bagging

The bagging technique is used across a large number of industries, providing insights
for both real-world value and interesting perspectives, such as in the GRAMMY
Debates with Watson. Key use cases include:

● Healthcare: Bagging has been used to form medical data predictions. For
example, ensemble methods have been used for an array of bioinformatics problems,
such as gene and/or protein selection to identify a specific trait of interest.
● IT: Bagging can also improve the precision and accuracy in IT systems, such
as ones network intrusion detection systems.
● Environment: Ensemble methods, such as bagging, have been applied within
the field of remote sensing.
● Finance: Bagging has also been leveraged with deep learning models in the
finance industry, automating critical tasks, including fraud detection, credit risk
evaluations, and option pricing problems.

BOOSTING:

Boosting is a method used in machine learning to reduce errors in predictive data

analysis. Data scientists train machine learning software, called machine learning
models, on labeled data to make guesses about unlabeled data. A single machine
learning model might make prediction errors depending on the accuracy of the
training dataset. For example, if a cat-identifying model has been trained only on
images of white cats, it may occasionally misidentify a black cat. Boosting tries to
overcome this issue by training multiple models sequentially to improve the accuracy
of the overall system.

Why is boosting important?

Boosting improves machine models' predictive accuracy and performance by

converting multiple weak learners into a single strong learning model. Machine
learning models can be weak learners or strong learners:

Weak learners

Weak learners have low prediction accuracy, similar to random guessing. They are
prone to overfitting—that is, they can't classify data that varies too much from their
original dataset. For example, if you train the model to identify cats as animals with
pointed ears, it might fail to recognize a cat whose ears are curled.

Strong learners

Strong learners have higher prediction accuracy. Boosting converts a system of weak
learners into a single strong learning system. For example, to identify the cat image,
it combines a weak learner that guesses for pointy ears and another learner that
guesses for cat-shaped eyes. After analyzing the animal image for pointy ears, the
system analyzes it once again for cat-shaped eyes. This improves the system's overall
accuracy.

How does boosting work?

To understand how boosting works, let's describe how machine learning models
make decisions. Although there are many variations in implementation, data
scientists often use boosting with decision-tree algorithms:

Decision trees

Decision trees are data structures in machine learning that work by dividing the
dataset into smaller and smaller subsets based on their features. The idea is that
decision trees split up the data repeatedly until there is only one class left. For
example, the tree may ask a series of yes or no questions and divide the data into
categories at every step.

Boosting ensemble method

Boosting creates an ensemble model by combining several weak decision trees

sequentially. It assigns weights to the output of individual trees. Then it gives
incorrect classifications from the first decision tree a higher weight and input to the
next tree. After numerous cycles, the boosting method combines these weak rules
into a single powerful prediction rule.

Boosting compared to bagging

Boosting and bagging are the two common ensemble methods that improve
prediction accuracy. The main difference between these learning methods is the
method of training. In bagging, data scientists improve the accuracy of weak learners
by training several of them at once on multiple datasets. In contrast, boosting trains
weak learners one after another.

How is training in boosting done?

The training method varies depending on the type of boosting process called the
boosting algorithm. However, an algorithm takes the following general steps to train
the boosting model:

Step 1

The boosting algorithm assigns equal weight to each data sample. It feeds the data to
the first machine model, called the base algorithm. The base algorithm makes
predictions for each data sample.

Step 2
The boosting algorithm assesses model predictions and increases the weight of
samples with a more significant error. It also assigns a weight based on model
performance. A model that outputs excellent predictions will have a high amount of
influence over the final decision.

Step 3

The algorithm passes the weighted data to the next decision tree.

Step 4

The algorithm repeats steps 2 and 3 until instances of training errors are below a
certain threshold.

What are the types of boosting?

The following are the three main types of boosting:

Adaptive boosting

Adaptive Boosting (AdaBoost) was one of the earliest boosting models developed. It
adapts and tries to self-correct in every iteration of the boosting process.

AdaBoost initially gives the same weight to each dataset. Then, it automatically
adjusts the weights of the data points after every decision tree. It gives more weight
to incorrectly classified items to correct them for the next round. It repeats the
process until the residual error, or the difference between actual and predicted values,
falls below an acceptable threshold.

You can use AdaBoost with many predictors, and it is typically not as sensitive as
other boosting algorithms. This approach does not work well when there is a
correlation among features or high data dimensionality. Overall, AdaBoost is a
suitable type of boosting for classification problems.
Gradient boosting

Gradient Boosting (GB) is similar to AdaBoost in that it, too, is a sequential training
technique. The difference between AdaBoost and GB is that GB does not give
incorrectly classified items more weight. Instead, GB software optimizes the loss
function by generating base learners sequentially so that the present base learner is
always more effective than the previous one. This method attempts to generate
accurate results initially instead of correcting errors throughout the process, like
AdaBoost. For this reason, GB software can lead to more accurate results. Gradient
Boosting can help with both classification and regression-based problems.

Extreme gradient boosting

Extreme Gradient Boosting (XGBoost) improves gradient boosting for computational

speed and scale in several ways. XGBoost uses multiple cores on the CPU so that
learning can occur in parallel during training. It is a boosting algorithm that can
handle extensive datasets, making it attractive for big data applications. The key
features of XGBoost are parallelization, distributed computing, cache optimization,
and out-of-core processing.

What are the benefits of boosting?

Boosting offers the following major benefits:

Ease of implementation

Boosting has easy-to-understand and easy-to-interpret algorithms that learn from

their mistakes. These algorithms don't require any data preprocessing, and they have
built-in routines to handle missing data. In addition, most languages have built-in
libraries to implement boosting algorithms with many parameters that can fine-tune
performance.

Reduction of bias

Bias is the presence of uncertainty or inaccuracy in machine learning results.

Boosting algorithms combine multiple weak learners in a sequential method, which
iteratively improves observations. This approach helps to reduce high bias that is
common in machine learning models.
Computational efficiency

Boosting algorithms prioritize features that increase predictive accuracy during

training. They can help to reduce data attributes and handle large datasets efficiently.

What are the challenges of boosting?

The following are common limitations of boosting modes:

Vulnerability to outlier data

Boosting models are vulnerable to outliers or data values that are different from the
rest of the dataset. Because each model attempts to correct the faults of its
predecessor, outliers can skew results significantly.

Real-time implementation

You might also find it challenging to use boosting for real-time implementation
because the algorithm is more complex than other processes. Boosting methods have
high adaptability, so you can use a wide variety of model parameters that
immediately affect the model's performance.

Gradient Boosting Machines

Gradient Boosting is a popular boosting algorithm. In gradient boosting, each

predictor corrects its predecessor’s error. In contrast to Adaboost, the weights of the
training instances are not tweaked, instead, each predictor is trained using the
residual errors of the predecessor as labels.
There is a technique called the Gradient Boosted Trees whose base learner is CART
(Classification and Regression Trees).
The below diagram explains how gradient boosted trees are trained for regression
problems.
 Gradient Boosted Trees for Regression

The ensemble consists of N trees. Tree1 is trained using the feature matrix X and the
labels y. The predictions labelled y1(hat) are used to determine the training set
residual errors r1. Tree2 is then trained using the feature matrix X and the residual
errors of Tree1 as labels. The predicted results r1(hat) are then used to determine the
residual r2. The process is repeated until all the N trees forming the ensemble are
trained.
Deep Learning
Deep learning is a subset of machine learning, which is essentially a neural network
with three or more layers. These neural networks attempt to simulate the behavior of
the human brain—albeit far from matching its ability—allowing it to “learn” from
large amounts of data.
Architectures :
1. Deep Neural Network – It is a neural network with a certain level of
complexity (having multiple hidden layers in between input and output
layers). They are capable of modeling and processing non-linear
relationships.
2. Deep Belief Network(DBN) – It is a class of Deep Neural Network. It is a
multi-layer belief network. Steps for performing DBN : a. Learn a layer of
features from visible units using the Contrastive Divergence algorithm. b.
 Treat activations of previously trained features as visible units and then
learn features of features. c. Finally, the whole DBN is trained when the
learning for the final hidden layer is achieved.
3. Recurrent (perform same task for every element of a sequence) Neural
Network – Allows for parallel and sequential computation. Similar to the
human brain (large feedback network of connected neurons). They are able
to remember important things about the input they received and hence
enables them to be more precise.
​
​