Machine Learning Foundations

Professor. Harish Guruprasad Ramaswamy

Hello everyone and welcome to another lecture on machine learning foundations. In the last
lecture, we introduced the supervised learning paradigm and the important regression learning
problem. In today's lecture, we will take a look at the classification learning problem and some
examples.

(Refer Slide Time: 0:36)

A simple classification example, which we had already alluded to, is something like this, where
you want to predict if you are given the area and the price of a house and you want to predict if the
number of rooms in that house is greater than 3 or less than or equal to 3. So, that is the example
of a classification problem, because the prediction that you are making is just two possible values,
say that greater than 3 or less than or equal to 3.

The training data for such a thing would once again look similar to the regression case, you would
have xi, yi tuples, where xis belong to Rd. But the difference is that yis are no longer real valued,
but just, yi would just belong to either + 1 or - 1. That is the main difference in the training data
from the regression case where the instances xis are still d dimensional vectors. But the labels are
just either + 1 or - 1.
And the algorithm outputs of model f, which in this case is a function from Rd to + 1 or - 1. That
is an example classification model. And similar to the case of regression, you want, you need a
way to evaluate how good is this model. The ideal case would be that your f of xi would be equal
to yi for all i, f of x1 should be equal to y1, f of x2 would be equal to y2 and f of xn would be equal
to yn. So, that is the best case scenario. But in general, it might not be.

So, what you have here is the loss of a model f is simply the fraction of misclassified instances.
So, that is why you have the indicator, predicators, indicator of f of xi not equal to yi. So, this
particular term is going to be equal to 1 if f of xi is not equal to yi. And it is going to be equal to 0
if f of xi is indeed equal to yi. So, f of xi =yi means that you have made the right prediction. The f
has made the right prediction and it has no loss. So, you add up all the losses and divide/the number
of training points.

So, this essentially corresponds to the fraction of instances that are classified wrongly. So, that is
the fraction of misclassified instances. For the regression model, the most common
parameterization was you wanted to represent a real valued function and we just did a linear
parameterization. That is, we said f of x =w transpose x + b, but for a classification model that is
not possible, because you want a model which outputs just either + 1 or - 1.

And the most straightforward way to do that would be just use the same w transpose x + b, but
have a sign function on top of that. So, f of x =sign of w transpose x + b and such a model is called
a linear separator. This is a, I mean, this is not the only model/any means, but this is one of the
most common models and to just, to instantiate an example class of models in your head, so this
is the example.
(Refer Slide Time: 3:56)

So, we will have a very simple illustration of classification the same way that we had for
regression. And so now let us say we have a two dimensional data set, let us say, d =2. So, let us
say this is your data has, let us say, we have 6 data points, x, y, and let us say we have, (())(4:25).
Let us say we have 6 data points. Let us say the first data point is say 0 comma 0, the second data
point is 1 comma 0, the third data point is say 0 comma 1, the fourth data point is say 4 comma 4,
the fifth data point is 3 comma 4, the sixth data point is 4 comma 3.

So, you have 6 data points, each of them being two dimensional vectors. And that is the instances,
6 instances. You I have to give the labels for all of them. Let us say the training data is very simple.
So, it is + 1, + 1, + 1, - 1, - 1, - 1. The first three data points are positive, and the next three data
points are negative. That is the, let us illustrate this in the 2D case. So, the 2D case, let us see, this
is x1 axis, this is the x2 axis.

Note that this is the subscript which indicates the first coordinate and the second coordinate. So,
the first data point is 0 comma 0, which would be here, the second data point is 1 comma 0, which
would be here, the third data point is 0 comma 1, which would be here. So, these three points are
all labeled + 1. So, let us say the red color indicates + 1. Let us use some other color. Let us say
use blue to indicate the negative data points.

So, the fourth data point is 4 comma 4 which should be like this and 3 comma 4 and 4 comma 3.
So, these three points are labeled - 1 and we will call them as negative data points. So, this together
forms visualization of the data. Now, the classification learning algorithm would essentially take
this data and come up with the best model. It is the best model which maps from R2 to either + 1
or - 1. But in this illustration, we are going to do a much simpler task, where we are just going to
give two models and ask which of these two models would the learning algorithm pick?

Let us say the models, let us call the models f and g. Let us say, f of x is let us say sign of 2 - x1
and another model g of x is let us say sign of x1 - 2x2. So, these are the two models that we would
want the learning algorithm to evaluate. How would we do that? Well, simply, we can just compute
the loss of these two models f and g. And to do that, you just need to evaluate the function f on
the data points.

Well, if you do that, well, you would get sign of 2 - 0 is + 1, sign of 2 - 1 is also + 1, sign of 2 - 0
is also + 1, sign of 2 - 4 is - 1, sign of 2 - 3 is - 1, sign of 2 - 4 is also - 1. That is your f. And what
would your g look like, sign of x1 - 2 x2, sign of 0 is arbitrary.

Typically, you can define a convention where sign of 0 is + 1 and sign of 1 - 2, which is - 1, sign
of - 2 which is, sign of 1 - 0 is + 1, sign of 0 - 2 is - 1, sign of 4 - 8 is - 1, sign of 3 - 8 is also - 1,
sign of 4 - 6 is also - 1. So this is, if you evaluate g on the six data points, you will get this.

Now, you can compute the loss of f. Loss of f is simply 1/6 × the number of instances that your f
got wrong. And you can see clearly see that your f got all the 6 data points right. So, + 1 + 1 + 1 +
1 + 1 + 1 + 1 - 1 - 1, and so on. So, this particular loss will actually be 0. What about loss of g?
Loss of g is 1/6 × how many of the 6 data points did your g get right, did your g get wrong?

Well, out of all the 6x data points, there is only one data point which it got wrong, which is this.
The truth was + 1, but you got - 1 instead. So, that is 1/6× 1 which is 1/6. So, the loss of f is 0, loss
of g is 1/6. So, your learning algorithm would prefer f over g. So, in this very simple case, what
your learning algorithm could do is just return f, because it is just choosing among the two
functions.

In general, however, your learning algorithm would just take this training data and return a function
from scratch that is essentially it would return the best function among all possible functions are
something similar to that. In this case, once again, it is very easy to visualize f, because a common
way to visualize a classifier is as separate regions, because a classifier can take f, a classifier model
can take only two possible values. It is either + 1 or - 1. So, every region of the input is either + 1
or - 1.

So, if you do that for f, what is the set of inputs which f would classify as positive? So, if some
future input comes which, when would it be classified as positive? When it will be classified as
positive, if sign of 2 - x1 is greater than 0 which means that these would classify f as positive
versus f as negative.

And you can clearly see that based on this, this is the reason why this particular model has 0 loss,
because you can see that in the negative region of f you have all the negative data points and in the
positive region of f you have all the positive data points. And because of this, this particular model
f has 0 loss on the training data.

Let us do the same thing for g. If you do that, here I cannot draw a straight line, something like
this. I am purposefully offsetting it/0 because it should ideally pass through 0 and because we have
defined sign of 0 to be equal to + 1, I am just moving in a little bit. So, this is the g thing. So, this
everything to the right of the bottom right would be, would classified/g as positive and everything
above would be classified/g as negative. We can see that this function has a loss of 1, because it
classifies this particular data point as negative, even though it is actually positive. So, that is the
reason why loss of g is 1/6.

You can argue whether are these the only functions, no, obviously not. There are several possible
classifiers. And real classification algorithm would actually find the best classification model out
of all such functions. But in this particular simple case, we are just interested in finding out which
of the two is a better classifier, f or g and in this case, f is the better classifier.
(Refer Slide Time: 12:07)

So, now let us do one slightly more complicated example. I mean, it is pretty much the same
complexity just that it is more real in nature that is corresponds to a data which we can understand.
Let us do that. So, let us consider the, let us consider three models in this case. Let us consider the
first model f as f of x is simply sign of area - 10. So, this is the same dataset that we saw earlier,
where you want to classify the rooms as number of rooms, is it 3 or lesser or is it greater than 3.

So, we are doing an encoding here where we are converting all the rooms with either 1 or 2 or 3,
we will call that as - 1, the label for that is - 1 and all rooms where the number of rooms is greater
than 3 we will call that as + 1, because we are only interested in predicting whether the number of
rooms is greater than 3 or less than or equal to 3. We are not interested in anything else. So, we
can just convert the 1 or 2 or 3 to - 1 and 3 as + 1. You could do it the other way around also. It is
equivalent.

So, we want to predict whether, from the area on price, whether the number of rooms is greater
than 3 or less than or equal to 3. So, one possibility is, well, we can say f of x is sign of area - 10.
So, what does this say? This says that if area is greater than 10, then your house has more than 3
rooms. If it is less than 10, then it has 3 or lesser rooms. That is what your model f is saying.

And another example would be, another example model would be let us say g of x =sign of price
- 6, another model would be h of x would be sign of price - 9. Let us give f, g and h for the 6 data
points, sign of area - 10 which all of these 6, the 6 houses with all houses have area greater than
10. Well, the last four have area greater than 10. So, you can clearly see that sign of f, the f would
simply be - 1, - 1, + 1, + 1, + 1, + 1. This is the predictions made/f on the training data.

Similarly, what predictions would g make? Sign of price - 6, which all houses have price greater
than 6, well, once again, it is the last four houses. So, once again, how sign of price 6 would be -
1, - 1, + 1, + 1, + 1, + 1. Similarly, you can do the same thing for h which is sign of price - 9, which
would be - 1, - 1, - 1, + 1, - 1, - 1, only the fourth house has price greater than 9, everything else
has price less than 9. So, everything else will be - 1.

Now, we can easily compute what is the loss of f. We can see loss of f =0, because it exactly the
true pattern is - 1, - 1, + 1, + 1, + 1, + 1 and it is captured exactly/f. Similarly, loss of g is also
equal to 0. But loss of h is not 0. Loss of h is in fact =1, 2, 3, it is 3/6. Out of the 6 data points, it
got three of them wrong. So, it is loss of h is 3/6.

So, in this particular case, the learning algorithm is slightly stumped, because you have given two
models which, both of which have the same loss which is 0. So, in principle, the learning algorithm
can pick either. It can either pick f or it can pick g. As far as the training data is concerned, it is,
they are both equally good. In fact, they are equally perfect. They get all the six points correct. It
would just not pick h because h is a bad one. Both f and g are good classification models for this
particular dataset.

Of course, once again, I have been emphasizing again and again the real, any real classification
algorithm would not be choosing among some finite number of choices, but rather it would be
choosing the best classification model from an infinite variety, infinite choice. How to do that is
something which we will not be addressing right now. So this, with this, we can wrap up the
example of classification.
(Refer Slide Time: 17:05)

So, now, we will move to another part which I have slightly glossed over with this. You have these
models that say you have picked model f based on the training data or picked model g based on
training data. How do you evaluate this model? You, here is the main thing. You are not supposed
to use the training data itself to evaluate, the learning model here. Let us say, you have learned,
you have decided to use model f based on a training data x1, y1, x2 y2, xn, yn, how would you
evaluate this model? I am saying that you should not do that based on the training that itself. We
should use test data which is not in the training data for evaluating the model.

Why is that? Well, here is a simple counter example I will give you. Let us take the classification
example, first example that we had. So, we had three positive and three negative examples. So,
these are the three positive and you had three negative examples. Now, consider this new model I
am going to give you which is let us say f of x =+ 1 if x =0, 0, + 1 if x =1, 0, + 1 if x =0, 1 and - 1,
otherwise.

So, what does this model exactly do? It essentially, this is what it does. It for almost all of the
inputs, it is going to, for almost all of the inputs, it is going to be - 1. Just for the three special
cases, it is going to predict + 1. On the training data, this particular model f has 100 percent, it has
0 loss, because it gets all the training points. It has 0 loss. But that is not the main reason why we
even do machine learning. The main reason we do machine learning is how to use the training data
to get a model which will perform well on future data.
Let us say, for example, you are trying to learn to predict the price of a house from its area and
number of rooms and distance to metro and so on, you have a data set. Your goal is to not do well
on the already existing data set. Your goal is to learn the principles. And when someone comes to
the new house which is not in the data set, you should use the model that you have learned to make
a good prediction and you should do well on that house. That is how you should evaluate the
model, whether you have learned a good model or not./evaluating the model and the training data
itself, you are going to get an overoptimistic estimate of how good the model is.

Here is an example. Here this particular example, the model has zero loss on the training set. But
on the test, I mean, because this is a very unlikely model, so we can have a new data point. Let us
say you have a new data point, let us say like this. We have a new data point. This based on logic
you would guess that this new data point is likely positive. But according to your model, it is going
to be negative.

According to your learned model, it is going to be negative, because it goes against intuition and
because of that your model f, even though it has zero loss on the training set, it is going to perform
quite badly on unseen data. So, this is not a good model. But if you used your training data set,
you would say it is a good model. That is the reason why you should not use the training data for
evaluating the model. You should use some held out data which is a test data, which is called test
data that is not in the training data for evaluating the model.

In practice, for example, let us say you are using past hoses, let us say you are using the price of
hoses from 1990 to 2020 to learn a new price model, how well you are going to be doing, how
well your model does is evaluated based on future houses. So, some new house comes on the
market on 2021, if your model does a good job of predicting the price of the house, then it is a
good model.

Predicting the price of a house in 1990 accurately is not useful, because you have already seen
that. That is the main idea we will have to keep in mind that is learn models or evaluate it on data
which is distinct from the training data set, which is called a test data set.
(Refer Slide Time: 22:10)

Very often, you also have one more part of the data that is distinct from the training data and test
data, which is called the validation data. And where is used, because this comes from one of the
things that I mentioned earlier that is the learning algorithm just finds the best model in the
collection of models given/the human. For example, you might say the class of models that you
are looking at is linear models. So, let us say a × price, a × rooms + b × area + c × distance, that is
your model. Your learning algorithm will find the best a, b and c, but why is that. So, why not do
something else?

For example, you might just as well say price is a × let us say area/rooms + b × distance square +
c × distance/area. So, you could have something like this also. Why did we not do this and did a ×
area + b × rooms + c × distance, why did we do that and not this. In fact, there is no reason for us
to not do this. This is also perfectly valid you could argue.

So, this particular part of choosing the parameterization is not part of the learning algorithm and
that is part of a process called model selection. And how do, this is generally done/humans. So,
this is done based on common sense. You decide the price can linearly depend on area, distance
and the number of rooms. So, this is something which is set intuitively/humans. But there are
several multiple intuitive choices that can be made here.

And typically what is done is you choose among these collections separately and you decide which
of these collections the best using a held out data set called the validation data. We will not really
go into great detail on this, but just keep in mind that the finding the right collection of models is
done using validation data, finding the best model within the collection is done using train data
and evaluating a learned model is done using test data.

With that, we can wrap up supervised learning, and in the next class we can start unsupervised
learning.