Lecture 24 : Part 1 - Machine Learning Algorithms-XVII

IIT Kanpur July 201
20 followers
Sep 6, 2024
[Music]
students welcome to lecture number 24 so
we have been discussing about different
types of machine learning algorithm and
I told you that we're going to move into
the deep learning aspects of this in the
materials engineering but before that
let us also finish something which were
need to be told so today we'll discuss
major part of this lecture on
unsupervised learning and then we'll at
the end we'll talk about some aspects of
deep learning at the next class onwards
we'll discuss different models of
digital learning and how they can be
implemented so first of all in the last
lecture I talked about clustering right
and in fact we have discussed a lot
about clustering clustering is a part of
unsupervised learning and it is used
wiely in material science
engineering in the sense that you can
have data obtained from different
sources to model some kind of a phase
diagram phase Evolution or even you want
to predict mechanical or functional you
know properties of materials and this
data will be such that you need to find
a correlation among the
data and for that you need to use
clustering so therefore as a part of
unsupervised learning we know that this
group of learning methods the interpret
data based on only
input in case of superv learning you
have both input and output that is what
is called variable and the target
values so in case of one supervis you
have only variables no target values
that means you have only input so for
each input you don't have any output
values that's what you work on and many
cases we have that kind of situations in
material science engineering and that's
why this algorithms are very much
important for you to know understand and
Implement in real life situations when
you'll do this modelings of different
kinds of behavior predict prediction
Properties or phase diagram or phase
Evolutions or even situations where you
have less number of data but you need to
use it to predict some kind of a phase
or micro structure therefore don't only
underestimate that only supervised
learning is used in alloy design yes it
is used quite a lot because you know
regression classification or even Ann
methods can be widely used in case of
allo Design Concepts or predicting
properties of alloys other materials but
at the same time on superv learning also
can be used for these kind of
predictions exactly not the same way but
you know wherever you have problem of
data or you have only input variables
you can use this so you know there have
different kinds of methods we already
discussed like can and we have discussed
couple of lectur or three lectures
before then we yesterday the last
lecture we talk about K means
clustering and also hierarchical
clustering so then we have also
discussed about neural networks or Ann
methods but there are many mors like
have PCA principal component analysis
independent compon I or you have also
app algorithms at singular value DEC
composition methods so I not get time to
discuss each of these techniques but you
know it is all available literature we
can go get into books or even internet
literature understand that but I'm
discussing only specifically few methods
so clustering is what what is a task of
grouping data points and how do you
group you group based on the similarity
with each other and that is what is
called clustering or cluster me
analysis this method is part of un
learning because you have only input
data and it aims to gain insights for
unlabeled data points unlevel again is
another word which is used for data for
which you don't have Target values so
the picture shows here in the bottom you
see there are three clusters present but
you can have many more clusters present
actually depending on your similarity
index what you're looking for but on a
broad scale you can have only have three
clusters you can see that we have put
together and this is the main aim is to
form clusters or groups of homogeneous
data points for a heterogeneous data
sets that's what is the aim is how does
it do evaluates the similarity based on
a matric it can be equan distance it can
be cosine similarities man distance or
then many others distances also I've
talked about it in one of the slides and
then it groups them based on this High
similarity score together that's what it
is so it calculate the distance of
certain kind of distance either equili
distance which you are more used to it
in coordinate geometry it can also talk
about Minon distance or cosine
similarities also many other similarity
parameters exist I'm not it put all all
them together but these are the more
important but most of us are more uh you
know accustomed to it or you habit with
is
ukian distance So based on this aspects
you can have two types of algorithm in
clustering one is a flat
algorithm and it basically starts the
random partitioning because you have you
know you understand that you have
hydrogen data sets you have to partition
into different clusters so initially it
starts with a random plat learning and
then redefine it interpretively K means
cing is one such model but you can also
have hierarchal algorithms because when
you have you know problems in using K
means algorithm because random partition
may not work in some cases and you may
not have you know P information about
how this data points are connected then
you have to use hierarchical algorithms
like at the bottom up or a top down or
divisive approach it is exactly same as
like a nanomaterial synthesis I talked
about in the last lecture it's a bottom
up or top down approach we'll talk much
more but you know basically broadly
putting together these two are the main
classification algorithms centroid
approach we gu centroid first a central
point of any cluster we assume that
actually and then assign point to the
cluster based on the nearest neighbor
distance
remember we talked about how to
calculate distance either idian distance
man distance or any other type of
distance you can think about it given in
the slides which I have already
discussed so you have to first find a
center a center point and that Center is
random remember that we don't actually
assume that Center to be fixed we put a
random Center and then try to calculate
distance from the center point to the
points nearby and whichever points have
nearest neighbor distance to the
centroid we put them together as a
cluster but in hierar that is the main
assumption in centroid class approach in
centroid approach you're assuming a
central point app right without assuming
that you cannot separate the data so in
a hierarchical approach you begin with
assuming each the point is a cluster by
itself that means if you have suppose
let's say th Points each point is
consider a cluster itself that's the
main difference between the centr and
the hierarchal approach once you do that
then you what you do repeatedly March
nearby clusters ising some kind of a
measure how close this cluster are like
distance or they how good a cluster the
resulting group would be many other
things are there but starting part Hier
clustering is that we assume every point
is a cluster and then we merge the
nearby points to that cluster and we can
use various kinds of means we can use
resistance as a means also you can use
also you know means of similarities
based on some other parameters like how
well they
are connected to each other like in a so
hierar approach lead to formation of tre
like structure or dendron and that's why
these things are connected it's like a
family
tree so therefore this Plastering
approaches are widely broadly speaking
used but you know we can also talk about
different means of algorithms like CID
bless we already understood what is it
is you can also density clustering and
know how dense the data points are in a
particular set or particular data set
how dense the data points are to a
particular position then you can cluster
them and as I told heral clustering is
nothing but a connectivity based
clustering lastly you can also bu
distribution based clustering like you
can use some kind normal distribution or
G distributions or any other
distribution space and that can be used
as a clustering means to Suppy the data
points so to talk about a little bit
more in details Cent clusters basically
are the most easiest clustering
algorithm all of you will use that so
they actually you know group data point
based on the closeness their closeness
of each other so we assume a centroid a
centrer point and then calculate
distance from centrer point to the
nearest points and based on the distance
we can put them clusters and I told you
right distance many things like
equilibrium distance all of you are used
to it root over x² - Y X squ + Y square
that is root over X1 - X2 square + y1 -
Y2 square right that's what is called
equ distance you a manaton distance or
Minos distance
also and and of density best clustering
they are actually you know based on the
density of data points so as compared to
centr base which requires number of
cluster to predicted and the sensitive
to initial data point of centroid
density clustering determine the number
of cluster automatically because this
talks about the number of points per
unit area or per unit volume right
that's what the density is therefore it
is less sensitive to beginning
assumptions or beginning positions so
there are good these are basically good
at handling clusters of different sizes
and forms making them ideally suited for
databases to regularly separate Laing
clusters Cent clusters you don't
actually do overlap clusters but here we
can actually do overlapping clusters
also connectivity clustering is very
simple as I talk specifically
hierarchical clustering this you know
method of assembling related data points
into hierarchal cluster is called high
clustering here each point is initially
considered as a cluster and then
subsequently they're combined with other
clusters and so that we can form a
similar lineage like in family trees so
distribution as a very simple mention it
can be basically based on certain kind
of a PO distribution function like gosan
binomial G any other distribution with
data points and uh distances all right I
not talk much this is what is your
equilibrium distance this is your magon
distance this is your max distance or L
Infinity Norm distance whatever you want
to use you can use depending on your you
know category of data so let's talk
about what the crin algorithm this is
the part of first first one is centroid
by clustering so we take K cluster
centroids you can see here there are
five points and what do we do so we have
suppose K is two so K means which K is a
number K can be assume anything 1 2 3 4
5 6 now how you do that basically you
simply put K two so one will be this
cluster one will be this cluster right
so you can put a CID here the distance
between the centroid and the data point
and then calculate the Cent and these
data points right similarly you can put
a center here calculate distance
distance and distance right and put them
into
clust but you you understand that
initialization is very important
initialization means it's putting the
centered so that's a big assumptions so
came in clustering assign data points to
one of the K clusters depending on the
distribution from the center of the
cluster so that's what Center is assumed
to be centroid that is already placed it
starts with by randomly assigning the
cluster centroid in the space and then
each point assigned to one of the
cluster based on the distance of the
centroid to the clust to the points
right and you know this perform best
when data are well separated remember
this if data are overlapped this problem
this will not be good one remember this
then you have to use density B
clustering and why it is used widely
because it's very fast comp any other
clustering techniques very very fast it
provides strong coupling between data
points uh but you know it doesn't
provide clear information regarding the
quality of the Clusters remember that
one but High clustering or Den
clustering can provide much better
information of the quality of the
Clusters it so C in clustering is just
like a to be lemon point of VI is a
rudimentary clustering technique is very
fast widely used that's why right
shopkeepers data can be easily separated
you know how which customer is buying
which kind of products what kind of
sampo they're buying easily can be
clusters using this kind of data so what
are the issues here first issue is that
we have to pick Point sufficiently far
away from the Cent right that's a major
problem is
initialization how do you point this put
this centroids okay I can put one way
you can put other way somebody else can
put other way right so as a
computational progresses one can decide
to split one cluster sometime you can
Marge when two to keep the total K
constant right so K is first assume give
the example like K was two so we can
assume K but K can be three also right a
test whether to do it or
not that's the biggest question so how
having located the centroids of K
clusters we can reassign All Points
since some points that are assigned
early may actually wind up closer
another centroids as compared to that
that's probably one way of taking care
of this first you do random assignments
of the centroids and then cluster them
and then you can actually reassign some
of the points to some other you know
other clusters which they might belong
to the problem is that it doesn't
provide any information of the quality
of cluster right that's why this issue
arises so now in order to they take care
of those problems that's why hierarchal
clustering came into picture it's a
connectivity based clustering technique
and you know here we assume every data
point is a
cluster and
therefore uh one then you actually try
to do find the similarity of of the
points based on some distance or some
other means and then assign them so in
the process you have to draw a
dendrogram or tree like figure produced
from clustering and that will defect
defects very well the hierarchal
relationship like relationship between a
grandfather to father to a son or a
daughter is very clearly defined in a
hierarchy family hierarchy same thing is
done here the indivual data points are
located at the bottom of the dendrogram
while the largest cluster which may
include paa points are look at the top
I'll show you some example I have
already talk in order toate the
different number of clusters Dam can be
even sliced at various Heights okay like
that you see the subjects is what is the
top that's the you know largest cluster
right it include all that are the top of
the level and indivual data points are
po at the bottom of the level like
agriculture biology physics computer
science space right you can see then
agriculture as diary crops forestry
Agronomy so these are the bottom level
and then your biology also same thing
physics also might clear this is taken
from Yahoo so now we can actually talk
about that if you want to generate
different number of clusters at
dendogram can be sliced at differents
you can slice it here the one here the
two arrows so basically it builds a tree
like structure a taxonomy that's why
it's called
dendrogram and you know this is very
widely used iard applications of for
applications of a partial uh clustering
algorithm widely used okay so dendrogram
is like this you can see here it's curly
this is what your top this is what is at
the end and they are like a Tre like
actions now there are two types of these
hierarchical
clusterings you to understand that one
is called agative clustering or top down
clustering at second one is called
divisive clustering but is called a
bottom up clustering so what is that a
agative clustering or
HC this is known as a bottom of approach
okay sorry this is bottom of approach I
I think I told you wrong agative is a
bottom up divisive is a top down
approach like a nanometal synthesis we
talked about right if you go back to the
synthesis of nanom materials either it
can be top down you can take take a uh
you know chalk break it down into M
pieces pieces P you will achieve a nanop
particles or you can start with the atom
and build on structures that is called a
bottom of approach so this is what is
done a structure is more informative
than unstructured set of clusters
returned by flat clustering that is what
is your K means clustering is this
clustering argument does not require us
to to specify the number of clusters
that we have already told you so this
algorithm teachs each data as a single
turn clusters at the outset then
successively aerate the pairs of
clusters until all clusters are marged
into a single cluster that contains all
the data that is like a
dendrogram on the other hand in case of
divisive clustering what it does it
doesn't require also need to specify
your prfi number of clusters this
requires a method of spitting the
Clusters instead of joining to the speed
in the cluster that contains the whole
data so therefore in top down you are
basically uh what is that you are SP
slicing the data or basically you are
doing the splitting the data that's what
you do in case of bottom of approach you
are putting them together that's what is
important in this case so HSC starts
with each dot in a separate cluster then
reply join the closest pair of clusters
and history of marging this forms a
binary right very simple on the other
hand divisive
clusters it parti data into two group
first and then does his recard simply
later Tri that's what it's done so we'll
not talk about much more things but in
at the end I want to show you the
different distance
matrixes I know we only talk about ukan
in our you know when you do mathematics
but there are many many such like MOSI
canbera you can see here no
CH by chip quadratic mandas It Is by
name of the Indian scientist PC Mand Bas
correlation based on certain kind of
probability functions G Square kendle
rank there are many more actually so I
just given you some charts and this this
this is very important you can use one
of these so now once so therefore I I
just wanted to give you a detailed
description of this that's what I took
about 15 20 minutes to describe
different kind of things so today we'll
talk about another important you know
algorithm which is called em
algorithm and this is also important
algorithm for unsupervised learning I
don't know this is used to find maximum
livelihood parameters of any statistical
model whose expectation can be shown
directly as you see here it's Bas
algorithm which can be used to handle
situation where some variables or
features are partially observable or are
they missing right suppose let's say you
have variable data some value are
missing how do you correlate them so
certain variables are observable we can
use them these instances to learn and
estimate their values once you learn
then we can predict the values those
variables which are not observable right
it's very difficult to be an example of
this in real typ situations you will
find there are many many kind of
phenomenon happen in which or will be
happening in which there are a lot of
features a lot of variables which are
directly not visible but output is
visible right something is happening you
can see that but what are the factors
controlling that output all of them may
not visible sometimes it is not possible
even to collect data from the that
experiments which can sign ify how many
number of variables how many number of
features are available so how do you do
that in those situations this algorithm
Works nicely this is why this algorithm
I wrote correctly it applied to Lattin
variables you know latent he right which
is not seen or not observed directly but
it is there similarly this is appliable
to Lattin variables which are variables
that are not directly observable but
infert from the value of the observed
variables many times you do that right
many times we infert some variables from
our calculations we don't see this
variable at the
beginning so in those cases this
algorithm will work nicely now listen
carefully so how do you do that so
basically is said by leveraging a known
general form of Po distribution it can
be any it can be cian it can be you know
Chi distribution it can be you know Bal
distributions you can take any of thems
which can govern these latent variables
El algorithm then predict the
values of the variables very accurately
but since some data are missing how do
you do that right that's why then how
can you you know form a distribution
functions fine whatever value available
to you you can form a distribution
functions and using this distribution
function you can basically predict the
other ones uh resonable accuracies here
is commonly used for all random variable
models and even can handle this
important missing data remember this
this is very important
so this is what is the basis of e em
algorithm now it has two steps one is
called Eep in which algorithm computes
the latent
variables expectation of the log
likelihood using current parameters
estimates so we'll talk about a little
bit second step is called M steps this
is where actually does maximization
maximize the expected log likelihood
obtained in the previous steps right and
then the model is parameters updated
based on that so let's let's try to
understand it a little more you know
what is it so and as I hope you
understood that this one this was
proposed in a very important paper in
1977 by three scientists Arthur
Dempster Nan L and Donal ruin and you
know this particular algorithm become
very famous because it is very useful in
statistical modeling and
estimation and as I said this is
applicable to all latent variables which
are variables that are not directly
observable but infert from the values of
The observed variables that's what it is
so let's talk about a little bit more on
these aspects on the
board and this is actually called also
called a problemistic algorithm so this
is also called a problemistic
algorithm so em estimat
estimation
right what em stands for expectation not
estimations I'm sorry expectation
maximization
expectation
right
algorithm
and basically it's nothing
but the such is a maximum likelihood
such a
maximum
likelihood
hypothesis this is what is important it
searches for the ma maximum High Li
hypothesis how does it do
by
repeatedly
reestablishing the
expected values of the
latent
variables let's spend couple of minutes
here so it search it
searches a maximum
lud
hypothesis hypothesis is something which
has no mathematical Foundation but it
searches for that and how does it do by
repeatedly reestablishing the EXP Ed
values of the latent
variables as I so told you right in real
life there be lot of problems where you
have some variables which are not seen
observable they are called latent
variables and if you want to find the
values or predict the values of those
latent variables this is the best way so
let's call these latent variables as
Jed
IG okay let's call that now
once you do that so what what is what is
what is done there are two steps
actually as I told you j i
j is
measured or found
out using some current
hypothesis any hypo hypothesis means
some formula okay it can be some
distribution function it can be some
algebraic formula this latent variable
is found out using that this is a random
Choice okay you can choose any you don't
have to worry about what is the partic
processes you can choose that okay and
this hypothesis is let's H and we can
write down H as like this mathematical
form H equal to mu1 and mu2 okay that's
what it is it's basically the this
latent variables initialization remember
this you found out using some current
hypothesis correct so that means H is a
function of mu1 and mu2 and what kind of
function it is it's up to you to decide
it can be alic function tonometric
function it can be even a distribution
function that's your
choice so and there mu1 mu2
are arbitrary initial data
initial initial
data so then this is what a step one is
then what does it
do then itly reestablish H
itely
iteratively EST
establishes reestablishes not
establishes okay let's try it
properly some of you might be taking
notes
reestablishes
H by H is a function which we assumed
initially based on initial data but that
was based on certain current hypothesis
or current function now how do I
do H
by it establish H by
calculating
e e as a function of G is expectation
that is your expectation okay
e of
J of each
latent
variables assuming
hypothesis okay so this will iteratively
establish H you can do lot of Loops H by
calculating EJ expectation of J that's
so EJ of each Lattin variables by using
this assum this hypothesis so you have
done
that okay so what you doing first first
is is your this is the lat variables
right and these latent variables are
found out using certain card hypothesis
correct so what do you do then after
that reestablishes H that H is the
correct one or not how do you know that
you have to itely do this calculations
that's a loop okay if and else Loop
probably and then you do that by simply
calculating this expectation function
this is the first step and second in
this case of second one okay this is the
most important step you are doing
expectation calculating e of the latent
variables assuming that hypothesis H
equal to mu1 mu2 right so you have done
that what the next step you do now
calculate this is very important step
calculate the new maximum
likelihood likelihood
new maximum liud okay new maximum means
what so basically you have to know that
this is the correct or not and in order
to know that you have to
maximize the the values right that's
what is this new maximum likelihood
hypothesis this term sometime may look
like a Hebrew but likee hypothesis is
very very s very very widely used in
mathematics statistics actually and that
can be H Prime is mu1 prime mu2 prime
okay I'm writing in
general assuming values taken from the
individual latent variables
individual latent
variable g j so therefore
EJ sorry e not e j is basically e within
bracket j i
j that's equal to
probability xal to x
i xal to x i this is how it is written
in statistics x = x I mu = to Mu
y divide by summation of all
probabilities N1
2 capital
n
p xal to x i
mu = to Mu
y so here you are calculating the
probability remember expectation
probability of this point x = to x
i satisfying the current hypothesis
divide by total probability because you
can have many current hypothesis
possible right that's why so this is the
main aspects of this algorithm so now
one can actually use uh we can convert
this equation to
uh what do I say convert the equation to
normal distribution EJ can be converted
to a normal distribution function very
easily if you want so I can actually do
that so I let just remove this point
here so this function what we have
written here this function whatever
written
here can be converted in terms
of exponent itial
minus remember this right all of you
should know that
x
i
minus
mu
Square IDE by
summation n = 1 to
n
right X exponential 1 by mu s x
I mu
s so if you convert this if you use a
normal distribution this will look like
this so what is doing is calculating the
probability distribution right total
prob summation probability and the
individual probability that's what it is
doing so that's why it is find out the
maximum
livelihood that this points will belong
to latent variable points will belong to
uh certain certain
cluster this is what is done so
therefore this is called This is called
E
step and this is called M
step right E and M let us write that e
step and this is called M
step this is what you
do so now let's come back here so
important terms first is it is doing the
Lattin variable Lattin variables trying
to prove and what it is doing it is
taking likelihood so likelihood log
means what like nothing but a log of the
likelihood
value I have suppose let's draw that
suppose I have a point here and I'm
going to you know see whether this is
Lattin variable points is belong to this
or not correct so I calculate the
location of these points right although
I don't know this because this is a
latent right so what I do I calculate I
just try to you know with this point I
try to find a function which is nothing
but mu let's say h mu y muj right and
then with in this function I try to see
whether this can also be part of this
can also be part of this function or not
if it is we re establish that if it is
not take another function and do that
and therefore the expectation
maximization tips I told you and
convergence is very fast here very very
fast here because of this algorithm
itself is such a nice things so let's
stop here I think we have taken
sufficient enough time to explain
expectation uh maximiz algorithm we'll
get back to you next part of the lecture
[Music]
[Music]
[Music]
