So we are starting a new
module in this class.
The module is about large
scale machine learning.
So what we will talk about is a class,
class of methods for
working with data that falls under
the umbrella of machine learning.
Where the idea is that based on, we want
to analyze the data so that based on
the features of the data we want to
predict certain properties of items or
data points that we haven't yet seen, or
that we are going to see in the future.
And the simplest method that we
will talk about today is called
Nearest Neighbor, classifier.
And based on this idea of Nearest Neighbor
classifiers, we will then
develop this into more complicated and
more advanced Machine Learning, models.
The idea of Machine Learning or what is
known also as Supervised Learning is that,
we would like to learn, a function that
is basically making predictions for us.
So in, in an abstract way,
we would like to estimate based on
the data a function f of x so
that given f, we can predict y.
Now, of course,
the question is what is x and what is y.
Most generally, there kind of two way,
two separate things what y can represent.
If y represent a real number,
then this is what is known as regression.
Based on some value of x,
I want to predict a real number y.
So for example if I would want to,
given someone's age and
someone's, ethnicity and so on,
maybe I would want to predict their life
expectancy then this would be
an example of, a regression problem.
However y can also be our
categorical variable, right?
Which, you can think of it as a binary
variable or something like that.
Right?
This predicting of
the categorical variable is known
as a problem of classification.
Right, so for example, one, one case of
classification would be that I give you
a document, and I, or an email, and I want
to ask you, is this spam email or not?
Right, so given a document you want
to decide, return a binary var,
variable, 0 or 1,
where 0 means not spam, and
1 means yes this is spam,
let's discard this email.
Of course you can also predict
kind of more complex objects.
For example you can sometimes
y could be a ranking.
An ordering of things.
Or it could be for
example if you are working with sentences.
Y could be a whole Parse tree.
But what we focus on in our lecture
is mostly on classification.
So basically, given a set of Xs,
decide what is the label,
the binary label of every x.
And, what is, why do we call this
whole thing supervised learning is
because we think of our data as labeled.
We are thinking that we are getting
a set of many pairs, x and y.
Where x is, is,
x is the data that we are getting and
y is the variable or
the class that we want to predict.
So we can think of x as a vector
of binary categorical or
real, valued features and
y as the class, let's say plus 1,
minus 1, or a real number if you
are working with regression.
And if you think about this case
basically we can think of x as a set of
features representing our data point and
y is the property of the data
point we want to predict.
So, if I want to predict, spam then for
example x could be a set
of words in the email.
And y is a a binary variable that tells
us whether that email is spam or not.
If I would want to for example,
model, human diseases.
I could, x could be a set of, symptoms or
set of characteristics of a patient and
y could be whether that patient
suffers from that disease or not.
So this is the first idea.
The idea of having a set of features, and
then having the dependant variable
that you want to predict.
Based on that set of features
using our function F.
Another important idea is that we will
think of our daytime sometimes as
coming as this big matrix, right.
Where we can take our features, feature
vectors, and stack them together in
a matrix and then we can think of,
our depend dependent variable's Y, so
the class value that TBN could
predict has a long thin vector.
And of course, what you can also do then
is to say, based on this what have been
called training data, we want to estimate
our function F, so that whenever,
we ob,
we observe some new unseen data x prime,
we will able to predict what
are the associated class values.
With this unseen data, right?
So the idea is that if you want
to learn our function F based on
the training data set that is labeled in
a sense that we have both x's and y's, and
then in the future,
our hope is that we will,
we will get this new data set,
this we call it a testing data set.
Where we only know x's and from x's
we will try to predict, these y's.
So we will always kind of think about the
training stage of our category system and
then the testing or
application state of our algorithm.
So in this module, we will talk about
several different, machine learning at,
methods where we will be kind
of focusing on large scale data.
In particular, we will talk today about,
k-Nearest neighbor, which is in,
which is something that a method in
a class of instance based learning.
And then we will also talk about support
vector machines and decision trees.
And kind of the main question when
working with machine learning methods is,
how do we efficiently train?
Or build a model based on
the based on the data?
So in a sense the main question that
arises in machine learning is how do I
find this function f.
That takes the input features and
predicts the, the class variable.
Right?
So, learning or
estimating this function F is
the hardest part of of machine learning.
So an example of instance based learning,
the idea here is that we want
to use existing in, instances or
resisting data points to make predictions
about unknown or unlabeled data points.
So the example of such a method
is called nearest neighbor.
Right, where the idea is,
we take all our training data, all our x,
y pairs, lets say in memory or
on the disk, and then whenever a new,
new query example, let's call it q comes,
we find other examples, x,
x prime that are, that are, similar to it.
And then based on the value, the labels of
those examples, we also predict the value,
y, y* for the, for
the given query point q.
So what is interesting about
nearest neighbor, is that is,
that it works both for
regression and classification.
And if we think about recommended systems,
in particular, collaborative filtering.
Collaborative filtering is an example of
a nearest neighbor classifier, right?
There, there the idea was
that when a user comes,
we find k most similar users
to our given query user q.
Then we look at what this
other k most similar users,
what are the movies they like.
And based on the movies
these other users like.
We are making a recommendation
to our creative user queue.
So this is exactly an example of our
nearest neighbor, where a query arrives.
We find nearest data points based on
the labels of the nearest data points,
we kind of try to combine those labels, to
talk about the label of the created point.
The simplest of all nearest
neighbor classifiers is what is
called a one nearest neighbor classifier.
Right?
Where the idea is that whenever we want to
make, a, decide on a label of a given,
of a given data point, we simply find the,
the point most similar to it and,
and use that label as a prediction.
So in a par, in particular when we want
to, em, du, implement the nearest neighbor
classifier, there are several
things we have to decide on.
First, is we have to decide on
the distance metric, right.
How do we measure the similarities or
distances between data points?
So for example,
in the case I will show you here is let's
assume we are using euclidean distance.
And then another thing we have to decide
is how many neighbors are we looking at?
Are we looking at one nearest neighbor,
five nearest neighbors?
How many nearest points
do we want to examine?
So in our case,
let's look at one nearest neighbor.
Another important thing is,
how are we weighing this different
neighbors that we are combining together?
Right?
So in this case that I'll show you,
we won't worry about this just yet.
And then another important,
question is how do I then,
take all these nearest neighbors and
combine the, their values into a single
point that I can use as prediction?
And in our case because we are just using
one nearest neighbor, all we have to do
is just predict the same output as at is,
as is the value of the nearest neighbor.
For example, now if I, show you how
this works, here I have a simple two
dimensional data set where I can think
of the x axis as the input feature, and
the y axis is the value
I would like to predict.
And, blue points are my data points, and
the black line shows the output of one,
nearest neighbor classifier.
You basically see that for
around every point we exactly just
predict the value, of that point.
And then if our data set is noisy, our,
our prediction jumps around, quite a lot.
If our data set is nice and
smooth, we are basically predicting
this almost like, a step function.
So, this seems to be working quite
well in this simple example, but
we are seeing the,
what the method is suffering from.
It is making lots of very, er, spiky, or
sharp decisions, because we are only
looking at the one nearest neighbor.
So we want to generalize this, and
maybe try to kind of use more
nearest neighbors to average better.
So let's look at how that works.
Right?
So if we want,
want to generalize now our method
according to k nearest neighbor,
then now the idea is I,
I'm able to use the Euclidean distance.
Now how many, neighbors should we look at.
Will we look k?
When k is some number chosen by the user.
And then how do we combine
the labels of all the k neigh,
neighbors into the, into one label?
For example right now let's just say
that our output will be the average out,
the average of the, the classes
of the k nearest neighbors, so,
very simply for example here is our,
data sets from the previous slide.
We are using here k equals 9, which means
we are averaging together the y value
of the 9 nearest points
to our query point.
And given the blue data, this is
the predicted value that we would make.
For example notice that now
our predicted function,
our function f of x in,
in some sense if you like.
Is much smoother than what is was before.
While nearest neighbor
is a very simple method.
One thing that we haven't yet discussed
is actually how do we got, go and
find nearest neighbors.
So our, the task here is basically
given a set of points, in, in some,
in some space, so
this is basically our data set.
Our goal is to find a,
another set of points that
are close to our created point, Q.
And, there are two types of
queries we may want to ask,
one type of query to say give me
nearest K points to our, point Q,
and another way to ask a query
would be the range search where he
would say give me all the points
that are inside some distance of Q.
In both of these cases, a [INAUDIBLE]
solution would require a linear pass over
the data, so it would take linear time,
but we already know how to do this better.
For example, using locality
sensitive hashing, we could,
we could find, nearest neighbors in near,
in near constant time.
So that would be a good way how
to really make nearest neighbor
classifiers scale to large scale data.