Let's look at the problem of prediction from our framework that we define for
learning way back in the lecture on learn. Once again, we have many data points.
This time, we'll use a slightly different notation.
We have m data points, each having features, and we'll have n - one features
for each data point. There's a reason why we're going to have n
- one, it will become clear shortly. And, of course, with each set of features
or instance of features, we have an output variable, more than one possibly, which
will be the ones we want to predict. Just as before we have a large number of
data points each having a number of features.
And given a new data point, we would like to know it's value.
In the case of learning, we had categories that we wanted to predict whether this was
a buyer or a browser, a good comment or a negative comment.
But now, we have a situation where these are numbers.
The y's are numbers and we would like to predict the actual value of y.
For example, xi's could be features about certain products,
And the numbers, y, might be the price that they fetch in different markets.
Or the volume of sales that you might expect based on the actions that you might
have taken about each product. So, instead of trying to decide what class
a new instance is, you want to predict something about the instance, such as it's
price or how much it's going to sell, a value.
So, in this sense, there's a close relationship between learning and
prediction. But, we are actually trying to predict the value, rather than predict the
class. So, to a certain extent, what we study in
learning is also prediction but we were predicting categories as opposed to actual
values. And, when we talk about predict in this
lecture, we'll be predicting actual values.
There is, of course a close relationship that if you know that the class of
something that you observe, you can make predictions about what it would do in the
future based on your understanding of how other instances of that class behaves.
But, that requires a certain degree of reasoning and it's not directly coming
from the data. For example, if you found that somebody
was likely to be a buyer. You would naturally predict that they will
go and click on an ad or buy something. That's not something that was learned from
the data, it was something which was part of how the data has been quoted,
And involved some degree of reasoning and preparation of the data as well as
inference once one has observed that class.
It's a subtle but important point that one needs to understand,
Which is a distinction between prediction of values and learning categories.
In that sense, prediction, learning, reasoning will all come together later in
this lecture. But, for the moment, let's talk about simply trying to predict the
value y. In particular, we'll be talking about just
one y output variable, if you have knowledge about a large number of
instances where you have features and the y values.
The technique that we'll talk about is called linear prediction, or regression,
or least squares. And, follows fairly naturally from our
formulation of the learning problem in terms of finding the expected value of y
given an instance x. It turns out,
And this is very important for linear prediction,
That the function, f of x, which we are so familiar with from our previous lectures,
also minimizes the error between the predicted y and fX).
Of x. And, in particular, it minimizes the expected sum of squares of this error.
Now, the proof of this is not difficult but we won't go into this here.
Let's take it as given that if we want to find the expected value of y given x, we
might as well minimize the error, or rather the sum of squares of the error
values between y and f of x. It's important to clarify the notation
here because it could get a bit confusing. Bold x means one data point which may
consist of n - one different features. A bold x subscripted is not one of the
features, It's actually one particular instance, and
is one whole data point. We don't actually have many features as
far as output variables are concerned, We are only dealing with one output
variable. So, Bold y is just y, in this case.
Normal, un-bold y, you may think about it. And, y sub i is not any of these but is
actually the output variable for the i-th data point.
Now, let's take a look at what this means. For one particular data point, the
difference between the output variable and the predicted output variable which is f
of the data point, x sub i, is just this quantity.
We square it, And take the average of that square across
all the possible data points that we have. There are m different data points so we
take the sum of all these squared errors and divide by m to get the average error.
And that's nothing but the expected value, of the error as measured by the square of
the difference between y and the predicted y.
Even if we didn't get the relationship between the expected value and the sum of
squares, just think of it this way. We have a prediction,
F, which says that y should be f of x, And we have the actual values y, yi,.
And we just want to make sure that the difference isn't too large. And, the best
way we can think of to do that is to measure the differences and try to find an
f which minimizes the average distance, or difference between y and f of x.
Let's see what that looks like if we have a particular form of f.
We're dealing with linear predictions, so in some sense, we're saying that f is not
just any function, But it is a particular type of function,
which is a linear function. So, what f looks like is x times some set
of weights. If we look at this as a row vector, then x
consists of all the elements of that row vector, then we have a one because it'll
be a constant. And then, x, one transposed f is our
function. So, we're essentially taking a linear combination of the features.
That means, you know, f1 x1 + f2 x2, etc., for every feature,
Plus some f0 which is just a constant, and that's our function f.
And what we really want is that, the sum, the differences between the predicted f
and the actual y's are very small. So, in some sense, if you look at, if you
write this as a matrix, what that works out is that this matrix, X, capital X,
where each row of the matrix is just that particular data point.
That is they are in different columns in this matrix, each row has n features
corresponding to the n features in the data point,
Multiplied by f, which is one unknown vector that we're trying to find, gives
me, as close as possible the, i-th data point.
So, x1 transpose f is almost y1, X1 transpose f is almost y1, and so on.
We have this extra one there just to make sure that we don't just take the
combination of the features, but we also allow for a constant factor in this linear
combination. Please look through this matrix
formulation and convince yourself that what we're really trying to do is minimize
the difference between extra, xi transposed f and y1..
And, if you write it down on the matrix, we're really trying to find x times f is
almost equal to y. So, we are trying to find an f such that x
times f is almost equal to y. Well, some of you might have seen such
things, matrix equations before, and might wonder why we have this almost equal to.
Well, the reason is that, the number of rows in this matrix is much larger than
the number of columns because you have a few features, maybe a few dozen features.
And, you have maybe hundreds of thousands of data points that you may have observed,
And we can't solve this exactly because there are just too many rows and too few
columns, So we have to solve it approximately. Of
course, if this were m by, n by n, we could solve it exactly which is what you
learned in high school is how we solve systems of linear equations.
Instead, we'll have to solve it approximately using a technique called
Least Squares. And here's how that works.