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.