You pick up your iPhone while waiting in line at a coffee shop. You google a not-so-famous actor, get linked to a Wikipedia entry listing his recent movies and popular YouTube clips of several of them. You check out user reviews on Amazon and pick one, download that movie on BitTorrent or stream that in Netflix. But suddenly the WiFi logo on your phone is gone and you're on 3G. Video quality starts to degrade, but you don't know if it's the server getting crowded or the Internet is congested somewhere. In any case, it costs you $10 per Gigabyte, and you decide to stop watching the movie, and instead multitask between sending tweets and calling your friend on Skype, while songs stream from iCloud to your phone. You're happy with the call quality, but get a little irritated when you see there're no new followers on Twitter. You may wonder how they all kind of work, and why sometimes they don't. Take a look at the list of 20 questions below. Each question is selected not just for its relevance to our daily lives, but also for the core concepts in the field of networking illustrated by its answers. This course is about formulating and answering these 20 questions.
The Baseline Predictor
Loading...
Из курса от партнера Princeton University
Networks: Friends, Money, and Bytes
59 оценки
Из урока
How Does Netflix Recommend Movies?
As a user of Netflix, you may have had movies recommended for you to watch. Behind the scenes, Netflix is leveraging powerful machine learning to determine which will be recommended to you specifically. In this lecture, we will study some of the fundamental algorithms that have been used for this purpose.
Познакомьтесь с преподавателями
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
So, we're going to go into neighborhood method now.
But, before we can do that, we first need to go through what's called a baseline
predictor. And before we can go through a baseline
predictor, we first want to talk about the general notion of parameterized model.
Now, we're going to see the parameterized model in a very different context in the
next chapter with Bayesian analysis. In general, we want to build a model that
is some mathematical representation of the problem we want to solve.
Sometimes, this model carries with it a bunch of parameters, we'll see a lot of
parameters today. And these model, parameterized models will
go into the so called training phase first.
Where you have some observations, but you also have the ground truth.
And you stake the observations, make prediction, and compare with ground truth.
But then, the difference is what something they want to minimize by tuning the model
parameters. After this step of training, you have
optimized model parameters. Then, you go into the actual real action,
which is the prediction step, where you take these optimized parameters in the
model, optimized by the training phase, with the known ground truth.
And then, you, you take the observation to make predictions.
Sometimes, other people have the ground truth, like Netflix had the ground truth
for the Netflix Prize, but you don't. So, training followed by prediction.
And training phase would train your parameter just like a voice recognition
system now on your computer or phone or car.
And you first train them by speaking certain known sentences.
These sentences are the ground truth, and then the computer will take in the
observation which is the recording of your voice, and then train the parameters
before going into the actual action of making predictions in the future for you.
All right. So, having said that, let's go into the
baseline predictor. This is the step number one before we can
afford to go to step number two and neighborhood predictor.
So, baseline predictor does not utilize the global structures of the user's hit
movies rating. We're going to start the baseline with the
baseline of the baseline, that's the laziest predictor that you can think of
the average predictor, let's call that r bar.
R bar is simply the summation of all the rui's across all the ui appears where
there is a rating and divided by the total number of set ratings.
That's it, simply the average. It turns out that Netflix's Prize training
data, 100 million data points, r hat is 3.6.
That is, over all these 100million ratings, the average is 3.6.
And we can say, well, that is our prediction.
We predict that all the users and movies interactions will be 3.6 stars in the
future. And clearly, this is a very lazy, we can
do a lot better than this. For example, we know that certain movies
are better and certain reviewers are harsher.
So, let's say, the predictor, r hat is r bar but with some bias terms.
So, b, bias terms with a regard to the user, and bias terms with regard to the
movie. So, r, r hat ui is the average predictor,
the laziest one plus biased term on the user, on a user and some biased term on
that movie. And now, we can look at the root mean
squared error. We can also take the square root of this
root. So, just look at the mean square error, if
it's, that doesn't change our answer of the optimal parameters.
So, we look at the summation of the difference squared, difference between ru,
ui, and r hat ui squared. We can also delete the step of dividing by
the total number of, of ratings because that's just a constant, it doesn't change
our answers. So, this is our objective function for the
minimization. Minimize over the set of bu's and bi's,
the summation of the square of the differences between the ground truth, rui,
which you have in the training phase, and the prediction r hat ui, where r hat ui
assumes this formula. Okay?
So, this is the function involving some squares of the bu and bi terms.
R hat is not a variable because it is just the average, say, 3.6 for Netflix, and the
bu, bi are your variables. That's an optimization problem, you've got
objective function which is the square. Definitely, not a linear programming
anymore, but we'll see if this is a nice nonlinear programming.
And, there's no constraints, okay? The variables are the bu, bi's, and the
given constants are the known truths, rui's, and this simple scalar, r bar that
describes the baseline predictor training optimization.
So, let's take a look at a particular example of this.
Maybe get rid of the r because we are effectively taking the square root of the
error, the mean square error minimization. Or, the total square error, since we're
not dividing by the number of ratings either.
Let's say, we have just two movies A, B, and we just have one user, one.
So, this is a ridiculously small example. In fact, it's so small that we have more
parameters than we have data points. We have three parameters, bA and for the
bias terms of the two movies, and the b1 which is bias term of, for, of this single
user here. We have three parameters and we have two
norm ratings from the ground truth, r1A and r1B.
And, what is our minimization problem? That is, looking at the square of the
difference between the prediction and the ground truth.
Since we have taken the square, it doesn't matter which way we write out the
different list say we write out r hat minus r, that is b1 plus ba plus r bar,
okay? This is our prediction.
R hat of 1A minus the actual 1A, and this thing squared plus the other error, which
is 1A, b1 plus, plus the average r bar minus the actual 1B rating squared.
So, this is the r1B hat minus r1B, this is the r1A hat minus the actual r1A, okay?
And we take the sum of the squares of the differences, and that is the object of
function. We want to minimize this object of
function subject in no constraints over the three optimization variables namely,
our three model parameters, bA, , b1. So, our question is, is this an easy
optimization or not? It's clearly not linear but it is an
unconstrained quadratic minimization over the variables.
It turns out it is a very easy problem. It is so called least squares problem,
okay? While minimizing the so called convex,
we'll come back to this in a minute. Convex quadratic function over no
constraints, and this is a very nice nulling optimization.
In general, we say, a least square problem is the minimization of the following
vectors, l2 norm. First of all, what is l2 norm?
So, given a given vector x1 to measure size, one standard way that is l2 norm is
the square root of the individual entry squared summing over all the entries.
We often don't like the square root thing, we take the square of the l2 norm.
So, square of the l2 norm is simply the sum of the xi squared over i.
It's a very standard way to measure the length of a vector, and we would like to,
in this square, minimize the l2 norm square, the length of the vector, Ab minus
c, where b is our variable, A is a known matrix, c is a known vector.
Say, if A is N by M, then b is M by one a column vector, and C is N by M by one,
another column vector. In the particular case we just saw, we can
also write this problem minimizing this expression in this the standard form.
It looks a little weird, but you sort of see, it's alright.
The matrix is one, one, zero, one, zero, one.
The variable vector we have is b1, bA, . And the constant vector term we have is
r1A minus r bar, and r1B minus r bar. This is our A, this is our b vector, this
is our c vector. Just to conform to the standard expression
that we want to minimize in the least squares problem.
You can easily check, minimizing this is this, l2 norm squared is the same as
minimizing this expression, okay? Example, this is just saying b1 + bA - r1A
+ r bar. And that's exactly this term, alright?
And then, you can write out the other term.
And then, just by definition of the square of the l2 norm, you see we are recovering
exactly the same object of function. So, we are, in the baseline predictor
problem solving a least square problem. So, the question is, how do we solve this
square problem in general? Okay?
Well, in general, we want to say, we want to minimize Ab minus c l2 norm squared
which can also be written out as Ab minus c transposed times Ab minus c.
Just it, multiplying itself in product in with itself.
You can write this out if you're not comfortable with the matrix notation in
scalar format. We can write out a little two by two
matrix A, you know one, two, three, four and a little vector b1, b2 minus little
vector c1, c2. And then, you can see that the derivation
coming up is no mystery. But, to save time, let's use the forehead
matrix notation. It's almost similar to our scalar
operation, okay? This will be Ab transpose times Ab minus
Ab transpose c minus another Ab transpose c and plus c transpose c.
And, this can in turn be written simply as by transpose rule, b transpose A transpose
Ab minus two times b transpose A transpose c plus c transposed c.
Okay? Now, we say, if we want to minimize this
expression over the variable which is b, for a given A matrix and c vector, you can
just take derivative of this with respect to b, okay?
It's just like taking derivative with respect to say, x of the quadratic scalar
function. Say, you know, x squared plus 2x minus
three, we take the derivative we get 2x plus two, right?
Here, we take the derivative with respect to b and we get the following.
Two, cuz there are two b's here, times A transpose A times b minus two.
Because of this two, take the derivative back to b, we've got A transpose c.
Alright. Now, we set it to be zero, we set this to
be zero. Now, why is setting the derivative to be
zero going to give us the right answer? We'll come back to that in a minute, okay?
It sounds intuitive. But, we will soon see that there's some
convex to the argument behind that. But, right now, let's just set it to zero.
And, that means A transpose A times b equals A transpose c.
This is the solution to our least square problem.
If you want to solve this problem by picking the right b, well, the right b is
the answer to this equation. What kind of equation is it for b?
It is a linear equation. A transpose A is just another matrix times
b equals another vector, which is A transpose c.
So, as long as we can solve this linear system of equation, we get the right
answer, b star that solves the least square problem.
This is a general thing that minimizing a convex quadratic function boils down to
solving linear equation cuz you take derivative ones, you get quadratic down to
linear equation. So, everything that we are talking about
eventually now boils down to a simple least square solution.
So, let's take a look at this one more time.
We say, our baseline predictor is the lazy r bar plus buyer's term for the users and
the movies. Then, you look at the difference between
the actual r and this r hat in the root mean square error sense, which means
you're looking at the square of the l2 norm.
And, you're minimizing over bu, bi that function.
It turns out picking the right bu, bi and therefore, completing this space-line
model, boils down to solving this kind of problem.
And this kind of problem is called least square in this format.
And the least square solution is simply the solution to this linear equation.
We'll go through a complete numeric example towards the end of the lecture,
but this is a quick summary of where we have been, okay?
Now, you may wonder, this is kind of complicated.
Why don't I just pick bu, bi to be the average rating of all, of course, all
movies for this user an, an average rating across all users for this movie?
That turns out, that's a reasonable guess but it does not necessarily minimize our
error metric which is root mean square error.
So, all we're doing is to say, if you believe in this model, stick it into our
error term. Then, you got to solve for least squares
problem which can be efficiently solved by solving linear equation, just like Google
PageRank solving linear equation. But, over there, it's a very different set
of equations. And then, once you get the optimal bu
star, bi star, stick it back in here, you get your predictor that minimizes RMSE.
It turns out that, that's almost a good, good idea, except you need something else.
We often encounter was called overfitting. This is in the textbook in the advance
material. But basically, it says, that you can add
so much parameters, all these bu's and bi's, and you can find tune them so well
based on the ground truth and the training data that it loses flexibility and
predictive power of the actual prediction. So, we want to somehow minimize the impact
of the parameters. We don't want to rely too much on
hindsight perfection, We want to leave some room for foresight cuz it's
ultimately foresight that matters in predicting or recommending.
One way to continue the weight of the parameter is to actually minimize the
size, say, l2 norm of these bu's formed as a vector and these bi's formed as a
vector. That's called the Regularized Least
Squares. If we use quadratic norm, then l2 norm is
still a least squares, it's just a bigger least squares problem.
But, it does try to contain to much reliance on too refined parameters based
on hindsight. So, after the baseline predictor, what we
have is the following. We got the actor rui, we've got the
baseline predictor r hat ui which is the same as rui minus r bar, the lazy average
plus the optimized bu and optimized bi, based on solving the least squares.
And we call this difference a shifted r, called r tilde ui, just a shorthand
notation. In other words, we have removed in this r
hat r tilde ui, the impact of the average and the impact of the per user bias, and
per movie bias. And we're going to take this as the
starting point into our neighborhood predictor to look at similarities across
movies and across users. But before we do that, just a very quick
detour for five minutes on the notion of convex optimization.
Now, we've seen linear programming which is a special case of convex optimization
where we minimize linear objective functions over linear constraints, linear
equations and inequalities. So, pictorially, that means, you use
linear in, inequalities to cut out the space of the variables into something
called the polytope with sharp corners. And then, you slide a bar, which is a
straight line cuz it's a linear function representing your objective function
across this constraint set. So, imagine an airplan, airplane flying
above this constraint set, okay? And we want to identify the minimal value
of this objective function over this kind of constraint set.
It turns out, what's really important is that you want your objective function to
be convex, like a convex quadratic function, such as x square over this space
of constraint set that is also convex like an oval or circle.
It's convexity that determines the watershed between easy and hard
optimization problems. So, what is convex optimization?
It refers to minimizing a convex objective function.
So, we've got to define what is a convex function, subject to a convex constraint
set. And, to be computationally useful, this
must be a convex constraint set that can be easily represented by some upper bound
inequalities on convex functions. So, we have to define what's a convex set
and what's a convex function. We will encounter other forms of convex
optimization in network economics, in internet pricing, in congestion control,
in routing, and so many other topics. This is our first brief, quick
introduction to this subject. And, we'll see in this and future lectures
that convex optimization is easy in both theory and in practice.
But, we just want to take three more minutes to introduce the basic notation
before we bring them back, just in time for the future applications in later
lectures. So, what's the convex set?
What's the convex function? We can actually go into a whole course on
nothing but convex analysis, and there are such courses in Math Department.
But for today's purpose, we just need to specify with some pictures.
A convex set is basically a set where you can pick any two element in the set, and
draw a line segment in between. And entire line segment also lies in the
convex, in the set. Then, we call this a convex set.
Say, well, this sounds like all sets of convex.
Well, no. Some sets, for example, like this set, you
can pick two points in the set but part of their line segment, this part, does not
lie inside the set. And, this is a kidney-shaped thing that is
a non-convex set. So, generally speaking, we say, a set is
convex if we pick any two points, a and b, that in this set, okay?
C, pick c. Then, the entire line segment between A
and B, which can be represented as theta a plus one minus theta times b.
For some theta between zero and one, for example, when theta is half, then it is
the midpoint between a and b also lies in c.
For all such theta, that's the key word, not for some theta but for all theta.
This is the representation mathematically of the line segment between point a and b.
And, by the way, say a, b are vectors in general, in, in dimensional space So,
pictorially, it just says that, a convex set is a set where the whole line segment
lies inside. It turns out the most important geometric
property of convex set is that any two convex set that don't touch each other can
be separated by a straight line. So, that one set lies on the one side and
the other lies on the other side. Let's say, will this be true for
non-convex set too? Not really.
For example, one set is convex, the other set is non-convex.
They don't touch each other and yet, you cannot separate them with a straight line.
Of course, you can separate them one way or another cuz they don't touch.
But, you can't separate them with a straight line.
It turns out that this is the most useful property of convex set, but we don't have
time to go through the implication of that in this lecture.
Now, having specified what's a convex set, we define what's a convex function.
A convex function intuitively is a function that curves upward, okay?
And some function, for example, curves upward before it curves downward.
Now, we know that if you look at a function f, its first derivative tells is
monotonous is increasing, is it decreasing function?
And the second derivative tells us whether it curves upward or downward.
Let's say, the function is a single variable function, f of, of scalar
variable x. Let's say, quadratic as well, we're
talking about quadratic today, is x squared, okay?
You can add a few other, a few other terms, say, 2x min, plus three, okay?
This, if you plot it, curves upwards. Or, another function, minus x square plus
2x plus three. If you plot it, it curves downward.
Both of them, quadratic function, one is a convex, the other is not.
In fact, the other, if you flip it minus f of x for this function is convex.
We call it function whose minus of that function is convex, a concave function.
So, this is convex function, this is a concave function.
And, of course, it doesn't have to be quadratic, and it doesn't have to
univariate. It could be a multivariate function.
But, the idea is that if it curves upward, it's convex, downward it's concave.
Some functions have convex and then concave like this sigmoidal function we'll
encounter in social network influence models later.
It starts out convex, at some point, so-called inflection point.
It starts to bend downward. So, this part, the second derivative is
positive. In this part, the second derivative is
negative. This curves up, this curves down, this
part is convex, this part is concave. The whole function, therefore, is neither
convex nor concave. Now, what kind of function is both convex
and concave? You say, wow.
That means you need the first, the second derivative to be both non-negative and
non-positive. The only possibility is that it is exactly
zero, that means it has no curvature. That's the only way to make it both
positive and negative. So, no curvature means it is a straight
line. It could be pointing up or pointing down
depending on the first derivative, but the second derivative is zero.
In other words, linear or affine function is the only function that's both convex
and concave. Now, these pictures are drawn on 2D,
therefore, they're talking about a single variable.
But, it's a multivariable function, now we have to talk about second derivative
slightly more evolved. Recall your multivariable calculus course.
Assume that you still remember, or can quickly brush up your memory about that.
If a function, let's say, of just say two variables, once you get hang of that, it's
the same as many variables is quadratic. X squared plus xy plus y squared, okay?
Xy are single variable but is a function of both variables.
Now, what is a second derivative of a, of a multivariable function is not a simple
expression anymore. It's not a number, it's a, it's a matrix.
With partial derivative of this function with respect to x squared and with respect
to y, twice, okay? And, with respect to both x and y, with
respect to both y and x. This is the matrix.
You have to take partial derivative with respect to x and y.
And in general, we say, given a function f of variables x1, x2, dot, dot, dot of xn.
If we look at a partial derivative, will direct to xi, and then respect to xj, this
is the ij-th entry of a matrix. That matrix is called the Hessian Matrix,
or in short, the Hessian of the function. So, in this particular case, it is very
simple. We take directive twice with respect to x,
we get two. Back to y, we get two.
With respect to x and then y, or y and then x the same thing for us is one, okay?
So, this two, one, one, two is the Hessian of this particular function, and this is
the general definition tight here. The ij-th entry of the matrix is partial
f, partial xi, and then partial f, partial xj.
So, how do we make sense out of saying that a matrix is positive?
It's not that the entries of the matrix are positive, but its about whether this
matrix eigenvalues are all positive or non-negative.
And, you can check that this matrix eigenvalues are all, not negative.
And therefore, this function is a convex function.
But in general, we say, a function is convex if it satisfy the secondary test
where the Hessian matrix that's defined is so called positive semi-definite.
And, a matrix being positive semi-definite means all the eigenvalues are positive or
non-negative. Now, you may wonder what if my function
does not have a second derivative? If Hessian matrix doesn't exist, some
function are now smooth enough that you can take derivative twice, or even once.
Well, it turns out that, that's fine too. I can have a function with a, like sharp
corner, okay? At this point, we don't have a second
derivative. But, we can still define a function as
convex or not and this will be a convex function.
However, since all our functions throughout entire course are smooth enough
that the Hessian matrix exist, we will just follow this definition, okay?
So, minimizing a convex function, which we know how to detect now, subject to a, a
convex set is a convex optimization, and least square is a special case because
least square minimizes a convex quadratic function subject to no constraints.
So, finally, we're done with the baseline predictor.
And now, we can move on to the proper subject of today's lecture, define
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
