The topic of this lecture is metric
learning and it's going to be
building on some of the ideas that
we presented earlier, about linear
dimensionality reduction.
We're also going to be looking mostly at
linear approaches here, but,
we're going to start taking into account
class structure as well, so
the actual class of a different data
points and this leads
us into a new corner of the field known as
metric learning.
All right, the main objectives of this
presentation will be to help you
understand the Mahalanobis distance, which
is probably
the most important class of distance
metrics.
And then we'll know how to apply metric
learning
to a classification problem to get a
pretty improved performance.
All right, so here's a, I mean, just a
real simple example to motivate
why we might be interested in learning
distance metrics and it involves
predicting heart attacks.
So here we've got a table of attributes
for different individuals with, with
different at numerical
attributes, so we've encoded gender as
either zero
or one we've included the age as well,
the,
the individual's weight which might be
relevant to
whether they're going to have a heart
attack
or not and we've also included their,
their
income, right, which might or might not be
relevant.
So one thing to note about this, this
particular formulation is that all of
these different attributes have wildly
different scales,
right, so, Income could differ widely by
thousands
where as weight is probably going to
differ by ten at most, and age maybe by
just ten or so years, gender is never
going to differ by very much at all.
So these attributes are all,um, they all
have different scalings
in this input space but there's nothing in
the data that
would indicate that, right, so if we just
throw, our
standard pattern recognition algorithms at
this, our standard dimensionality
reduction algorithms.
They might be unduly influenced by a
feature like income, right,
which is going to have very high variance
relative to the others.
So, an, another related problem is that
there may be
correlations you can imagine, as we add
more features on
there, there could be spurious
correlations in the data set
that make different, attributes totally
redundant with each other as well.
So, what particularly for nearest neighbor
methods and methods like that that rely
on calculating distances within the
attribute space,
those are definitely going to be biased
by the income attribute as opposed to some
of the others that might not
actually be relevant to the heart attack
problem, so how do we solve this?
Well, a traditional solution to resolving
this might be
to apply some sort of preprocessing
strategy, we can
do normalization, maybe standardize
things, so, they have mean
zero and standard deviation one, that's a
fairly common approach.
There's all sorts of preprocessing methods
that we
can apply but the intuition behind metric
learning
is that maybe if we incorporate some class
information from our training set, we can
do
even better and we can define distances
into
space, that are actually more relevant to
the
task at hand than we would if we
simply relied on intrinsic properties of
the data itself.
All right, so to summarize, measuring
distance is
a really critical part of pattern
recognition, this is
not just for local methods too, this is
for all sorts of parametric methods for
classification regression.
Until now, we've sort of been letting the
data itself define our, our distances but
there are challenges with this that we
noted
before and additionally, recall that
Euclidean distances are
less meaningful in high dimensions anyway,
so
even if our data is perfectly isotropic
and,
and, and uncorrelated with each other and
all
distances mean the same thing along all
attributes,.
Those Euclidean distances are going to be
less, valuable
to us, as we start moving to high
dimensions
just because of the curious geometry of
these high
dimensional spaces, so, how can we resolve
this problem?
Well, metric learning is based on the idea
that we can, define new distance metrics
new
rulers for measuring distance in higher
dimensional spaces
that are based on properties of the data
itself.
These are non-isotropic distances that
reflect some intrinsic structure
in the data, right, so this, is a really
elegant
depiction of, of what we're talking about
that involves
moving from, Euclidean isotropic distances
to a Mahalanopi distance metric.
So, on the left side you see a data set
of, I
guess, six points they're sure the data's
point color represents their class,
so you can see that the, the yellow points
are all of
one class, and they're sort of of
distributed more or less along a line.
And there also a couple of, of points have
different class values to the north and
south of them.
Note that if we're, if we're trying to
classify the query point in
the center and we want to enclose the
entire training data set of yellow
points, we have to look out far enough
that we're actually, the end
ball is encompassing all of our data
including the, the blue and the red.
So really what this suggest is that the
the, the Euclidean data, or,
I'm sorry, the Euclidean distance metric,
which
is the same in all directions, really
doesn't reflect, the class structure in
the data, that's, tends to be distributed
along this, this line, so Mahalanobis
distance
metric is more akin to, say, ellipsoid.
And that's what's portrayed at the, in the
panel at right here we're looking at a,
a Mahalanobis distance, and here it, the,
end
ball in this Mahalanobis distance measure
encloses all
of the, the yellow points while avoiding
the,
the data points of different classes, so,
there
now are are a ruler in this space actually
reflects the, the structure of the data.
So, how do you calculate a Mahalanobis
distance?
Well, we know how to calculate a Euclidean
distance, right?
It's just the, squared basically the, the
square sum of differences, take
the, the sum of square differences and
then take the square root.
The Mahalanobis distance metric is almost
the same, except in there, there's a an
inverse positive, semi-definite matrix
that I've indicated here with this sigma.
So, the, and you maybe note an analogy
with the, the co-variance
matrix from data sets that we've seen
before, saying that in the PCA
lecture that preceded this one and that's
not an accident, because actually
you can easily use a covariance matrix
here to, to whiten your data.
Just take it's inverse and scale all the,
the dimensions and correlations
appropriately to basically undo the
covariance
properties of the original data set.
And this gives, this whitens the data, it
makes everything isotropic so that the
distance we
calculate will be now adequate with, it
will
reflect the, the correlations in sigma,
the sigma matrix.
It, you, one can easily show that this
expression is
actually equivalent to a linear pre
transformation of the data.
So here we define the, we define this this
matrix sigma as V transpose V and push it
through some algebra, and reveal
on the, the bottom line there the
expression that is actually
equivalent to pre-multiplying all of our
data by a new basis V.
So really what this means is that in order
to calculate
a Mahalanobis distance we can just take
some trans, some linear
transformation of the data and then apply
our Euclidean distance in
that space and it's the same as the, the
Mahalanobis distance metric.
And note that you can calculate
this decomposition for any positive
semi-definite matrix,
It's possible to decompose it into the, to
the V as we're done here.
So there's a natural relationship between
the Mahalanobis distance metric, or the
ellipsoidal
distance and the the linear dimensionality
reduction
strategies that we've explored in previous
lectures.
All right, this leads me to the wild and
woolly topic of
metric learning which is an area of a lot
of active research.
Most modern metric learning research that
is work to, to learn
these, these distance measures treat it as
a convex optimization problem.
So they take a Mahalanobis distance, and
then have some
constraints on that based on the class
structure in the data,
such as, data points having similar class
must be close
together, data points having different
class must be far apart, right.
And then treat it as an optimization
problem and
apply techniques from operational research
and, and other disciplines
in order to tune that Mahalanobis distance
metric that
sigma matrix to best, separate the
different classes, right.
And there, there are challenges there of
course in, keeping the,
the nature positive semi definite which it
must be in order to
be a valid Mahalanobis metric but that's
the, part of the, the
research that's going on but there are
lots of applications of this.
Which include computer vision, information
retrieval where
you can be looking in databases, right,
to find something that's similar to your
query, which could be expressed as an
image
or a document with a bunch of text, right,
which would have potentially thousands of
different word attributes or in biometrics
where
you're looking at, at gene expression
information, right.
You could easily get data points of
thousands or tens of thousands of
attributes there.
So, it becomes important if you're doing
similarity queries in those sorts of
settings
that you have an effective distance metric
on which to, to do that query.
So yeah, so this is the, the modern topic
of, of metric learning, and here are a
couple
of examples of the different methods that
have been
proposed in the literature for learning
these distance metrics.
Most of this this list are Mahalanobis
distance metrics or linear
pre-transformations of the data, this list
is formed by Herbert and Saban
et al, and it simply gives you some
intuition for the,
the breadth of different algorithms that
are available to do metric learning.
Now we're going to do we're going to, put
most of this, aside for now and
instead talk about an oldie but a goodie,
that is a classical approach for a metric
learning that works in many cases and
has, the additional property that's pretty
robust and
reliable and pretty easy and cheap to
implement,
that is pretty Is simple to, to implement.
I think I, I mentioned this already
once before, the relationship with linear
dimensionality reduction,
that is, if this pre-linear
pre-transformation is
it, it represents a subspace of the data.
That is the, the covariance matrix isn't
full rank or V has
fewer columns than the, the full space of
the data and this
actually equates to a dimensionality
reduction and in that case, it's akin
to PCA or some of the other methods that
we've shown previously.
The only difference being that here, the,
the dimensionality reduction is taking the
class structure into account and trying to
separate the different classes from each
other.
Okay, so here's our, our classical
approach to metric learning, this is
a method that dates back to
Fisher, I believe, It's multi-class
discriminant analysis.
It's a generalization of Fisher's linear
discriminant, to the case where we have
different, like many different classes, up
to K different classes in this case.
So we start with our data set of, of data
points that's labeled with, with up to K
different values the
idea is to learn a Mahalanobis distance
metric that best
separates these classes from each other,
where we'll define separation, shortly.
the, output of this procedure is a linear
projection of the dimensionality up to K
minus 1.
Right, so we'll also reduce the
dimensionality of our,
of our input space, and like I said, if we
just use a, a single, a 1-D case with,
with two classes, that's equivalent to
Fischer's linear discriminant analysis.
All right, so here are some definitions to
get us started first,
I'm going to define the class mean, as the
mean of all
the data points having a certain class
label ascribed to them, so
we have a class mean for each one of our K
different classes.
We're also going to define scatter
matrices to represent the
spread of the data here we define the
within class
scatter matrix and fashion similar to the,
the sample covariance
matrix, so we're just looking at squared
distances against the mean.
And we do that for each class
independently
if you take the sum of all the
within class scatter matrices then you get
the
total within class scatter matrix for that
data set.
And here I, I've just represented this
graphically on the right side as ellipsoid
so each ellipse here has it's own, it
represents data, from a different class in
our data set, and the, within class
scatters are represented by the blue
lines,
right, so basically that measures how
compact
all of these different class distributions
are, right.
We're also going to define cla, matrix
known as the between class scatter
matrix, which measures how well these
different ellipses are separated from each
other.
So we take the mean of the entire data
set, that is
mu, and look at the, the difference
between that and the mean of
all of the classes independently, so this
is represented in the image
by the green arrows that show
the, the separation between the different
ellipsoids.
So we have two measures of scatter here,
the within class scatter and the between
class scatter.
So if we want to improve the separation of
the classes
in our projective space, the idea is to,
come up the projection
that shrinks the within class scatter that
is we want all the
class distributions to be as compact as
possible, in the projected representation.
The same time we want to increase the
between class scatter, we want the classes
to be well separated from each other,
right
and so,he said, how do you define this?
Well, we, we measure the determinant of
the scatter matrices, which you can think
of
as, sort of a measure of, of volume
in high dimensions for these positive,
semi-definite matrices.
So here's our objective, we find the
projection V to maximize
the ratio of these determinants, that is
the ratio of the between
class scatter over the within class
scatter, we're trying to increase the
numerator and decrease the denominator,
this is known as the Rayleigh coefficient.
And there exist lots of, of
straightforward ways to calculate this,
but the,
probably the most common one is the
to simply solve this generalized
eigenvalue problem.
Where you have the within and between
class scatter matrices on
either sides of this expression and then
the vector of, of
eigenvectors which is or the, I'm sorry,
the matrix of eigenvectors
which is the and and then eigenvalues
represented here by lambda.
So solving this generalized eigenvalue
problem with standard
numerical software will give you the, the
projection,
that best separates the classes according
to that
criterion that we established in the last
slide.
All right, so I want to close the quick
example
of how this can actually be used in
practice.
so, here we're going to look at
application
in automated image analysis, so we're
looking at
analysis of geologic images in particular
this is
work by Francis et al and ISAIRAS of 2014.
The ideas is to perform segmentation of
images, he may, be familiar with
image segmentation problems and here we're
looking at, at basically clustering data
points,
but we want to cluster data points in a
way that's, that's relevant to
the task at hand, that is, relevant to the
Geologic content of the images.
So, then we're going to assume that our
data cloud is, made up of points
which are vectors of pixel attributes,
which might
include color attributes as well as
texture attributes.
And the objective here is to learn a
projection that improves the quality
of our image segmentation, that is, we
want some distance where er, I'm
sorry, we want some distance matrix, where
distance in a, in a productive
space represents a sort of geologic
distance in the in the image space.
So here's an example of, what the
automated clustering should look like,
so here's an example of our, a k-means
clustering, with just two clusters.
You can see, we have a rock outcrop on
the,
the left, and we've applied unsupervised
clustering to that, and it
nicely splits the image into two different
classes, at right, and
this corresponds quite well with the
geologist, interpretation of the scene.
And so we'd like to, to do this for, for
all sorts of, of, outcrop images, but it
doesn't always work.
You can see that, often the pixel
values themselves don't actually reflect
the geologic content.
So this is quite obvious in this image
where we have fractures that are a lot
darker than everything else, but they
aren't, so
these fractures aren't necessarily
geologically interesting and they
don't correspond with the, the composition
of the
rock that we're trying to recover, but,
k-mean
clustering is biased by the, the, the
values
of those, those feat, or of those pixels.
That is, the extreme attributes the
extreme,
dark intensity of those pixels, right,
which cause
it to be very distant from everything
else,
so the fractures appear as their own
cluster.
Right, we'd like to avoid that we
different distance metric, that will
allow the, the k-mean segmentation to
overlook, some of these incidental
features
like fractures and instead focus on the
features that are most relevant,
that is the color and texture cues that
will tell us, where composition
is actually changing.
So, Francis et al applied, the multi-class
discriminant analysis to this problem
and here you see a production of data
points from rock outcrops.
This rock outcrop had three different
classes and you can see
that they MDA production, that is the
multi-class discriminant analysis does
a much better job of project, of
separating these classes than
traditional PCA or indeed clustering on
the, the raw feature space would.
So by training on, labelled examples from
one image, and then applying that distance
metric to another image we can actually
teach the system how to perform clustering
better.
In order to recover geologic classes as
part of the cluster, so
here's a visual example on that image that
I showed you before.
The fractures in, instead of getting their
own cluster after
we learn the distance metric
appropriately, we can get the
system to, actually recover autonomously
recover the, the compositional differences
in the rock and and avoid the, the
fracture confusion.
So, this is just one of many examples
where a
multi-class discriminant analysis can
improve
unsupervised clustering, so, this, this
pre-transformation that we've trained on
label data can be used
to improve a totally unsupervised
clustering approach on future images.
Okay, so a quick summary of what we've
covered in this lecture
we talked about Mahalanobis distance
metrics which are sort of an ellipsoidal,
generalization of the Euclidean distance,
it,
applying them or measuring Mahalanobis
distance
is equivalent to applying a linear
transformation on the original data set.
Metric learning can outperform purely
unsupervised
dimensionality reduction by accounting for
the, the
structure of classes, and we've
additionally shown
how multi-class discriminant analysis is a
particularly
useful, form of metric learning that
can provide projections of dimensionality
up to
k minus 1, where k is the number of
classes in your data set.