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.
Similarity and Neighborhood Predictor
Loading...
来自 Princeton University 的课程
网络：朋友、金钱和比特
61 个评分
从本节课中
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
This is a long lecture,
the longest in the entire course and one of the most mathematical.
But finally, we have arrived at the point of introducing neighborhood method.
Up to this point, everything we talked about is about an individual row or
individual column in the movie user rating table or matrix.
But now, we are ready to go into the global structures.
And the way we go into the global structure is by defining
a neighborhood L_i for each, say, movie i.
Or we can also look at this from a user point of view.
We'll instead just focus on the movie-movie correlation.
So you can think of two columns representing
the two movies and we want to look at how different they are,
in other words, define a pairwise statistical correlation between the two movies.
And then, we look at another pair of movie,
still movie i, but instead of comparing with movie j,
we'll compare with movie k and look at the ratings between this and these two columns.
And then we're going to pick up all those movies that are
somehow very similar or very dissimilar compared to movie i.
And both kinds of movies would be very useful.
So this is what we're going to do.
We'll first define a similarity metric
between two movies and then we will search through all the movies
out there and then pick up a subset of those that are
either very similar or very dissimilar
compared to movie i and call that the neighborhood L_i,
and we'll leverage that global information in making predictions
about users liking or disliking this movie i.
So, this idea can be illustrated quite nicely through a simple picture.
Suppose we got just two movies and two users,
so we can easily compare two points on 2D grid.
The two points are the movies A and B,
and we've got two users one and two.
The points are the movies and the axes are the users.
So movie A is getting a rating of five from user one and one from user two.
So, movie A is getting a five star and then a one star from these two users,
whereas movie B is getting a two star and a five star from these two users, respectively.
As you can tell that these two movies are kind of very different.
OK. They are basically liked or disliked in opposite polarity by these two users.
And indeed, this means that this angle theta is kind of big. What is this angle?
This is the angle between two straight lines: one is the line from
the origin to this movie's coordinate,
and the other is from the origin to this movie's coordinate.
And if these two coordinates are far apart,
one quantification of that is the angle theta here.
We measure the cosine of that angle and that is
a particular number and we use that number to
describe how similar or dissimilar A and B movies are.
This is called cosine coefficient.
It is a particular instance of a similarity metric that we'll be using here.
So how do we write down the cosine coefficient here?
I'm going to say the cosine coefficient between two movies i and j is called d_ij and,
if you remember from basic geometry, analytic geometry,
it's really this point viewed as a vector from origin to that point.
Call that the vector r_i,
it's a vector, transpose r_j, that is,
this point viewed as a vector from the origin to that point,
divided by the normalizations, that is,
the size of i,
L2 norm, and the size of j, also L2 norm.
So we can view these two ratings for two different movies as two
vectors r_i and r_j and the cosine of the angle is the standard formula,
which is just the inner product normalized by the sizes.
And this, in the longer form,
it just means r_ui and r_uj,
summing over all the u's who have rated both movies i and j, that is.
That is the inner product of these two vectors,
divided by the square root of,
just by the definition of L2 norm of the two vectors, r_ui-squared,
summing over all the u's,
the same set of u's here in the numerator,
and just summing over the same set of u, r_uj-squared.
That's just the L2 norm of these two vectors.
So, this d_ij is the cosine coefficient
defined as such geometrically as
the cosine of the angle theta and algebraically defined as such.
Now because we have already shifted
the r data from r to r minus the baseline predictor r,
for each ui pair,
we called this our tilde ui at the end for the last segment of the video.
So, strictly speaking, we should put tilde here,
so all looking at our tilde value that has already subtracted the influence
of the baseline predictor.
So now, what we need to do is to look at all the pairs of movies i,j,
except movie i,i back to itself,
and then compute this relationship.
So, at this point,
we have for each movie i computed the d_ij for all the j's out there.
We've got a list of numbers.
Let's arrange these in descending orders.
OK. These are the d_ij values,
and maybe movies five,
eight, 10, two and so on with respect to movie,
say, i=1, the first movie.
OK? All right, very good.
If you look at these and say some of these are real big numbers,
some of these are real small numbers, real negative numbers.
Again, remember, this actually can be either a positive or a negative value.
So we will say those that are very positive and those that are very
negative are both useful because they are very similar or very dissimilar movies.
So let's just look at the absolute value of d_ij's,
and we want those that are big to be included.
So I'll pick the top, say,
five movies, top either meaning they are really big here or really big here.
OK. And that will define what we call the neighborhood,
a list of other movies with respect to this given movie i.
So for example, L_1 could be movies five and eight,
and I say there's a movie 21 down here, 21.
OK. I say, who determines how big the set is?
How long is the list?
Who determines basically the cutoff threshold of the d_ij value?
Well, the one that would be determining those is you, OK, the recommender.
So there are quite a few rules and guidelines in determining how big is this list.
If you make it too big,
then you are indeed incorporating
the comparative information with respect to many other movies,
but some of them are so weakly coupled with this movie that it doesn't quite matter.
So, just adding too much noise.
On the other hand, if you include too few neighborhood movies,
then you're not fully leveraging all the information and then you are
losing precious information about other movies,
so that's not good either.
We won't have time to go into the exact art of picking the right size,
and that's indeed part of the reasons why it took
many computation for these teams to compete in the Netflix Prize.
But roughly speaking, the idea is that if you like a movie,
say, "Schindler's List" and,
say, "Life is Beautiful Life" then maybe you'll like "Doctor Zhivago".
If you dislike "E.T."
or dislike "Lion King" then maybe you also dislike,
say, "Toy Story". So that's the idea.
The idea is that we're going to look at all these movies as points in a space.
Those that are very close by this cosine theta metric,
we'll call them neighbors.
And therefore for each movie i,
we will define a neighborhood by the absolute value of these cosine coefficient values.
So now that we have defined what is the metric cosine similarity,
and from there we have defined what is a neighborhood for each movie,
we can finally define
the predictor based on that information called the neighborhood predictor.
So the neighborhood predictor,
it will be denoted as r-hat_ui,
but we have already used that symbol to represent the baseline predictor,
let's add a sup N. This N does not mean the number of users or movies,
it's a shorthand for neighborhood.
OK? So, we want to find out what is our r-hat_sub_ui^sup^N.
This is basically the original baseline predictor
now plus what we learn from these neighbors.
We learn from these neighbors that if
a neighbor movie j in the shifted rating r-tilde,
OK. Again, r-tilde is just r minus r-hat.
In this shifted space,
depending on whether j
is positively correlated with movie i or negative correlated with movie i,
it's going to give us some information.
So we want to add up those information,
summing across all the movies j,
indexed by j, in the set L_i.
So, we have to weigh each such rating by a neighbor movie j in some way.
What should the weight be?
One choice is just let weight be the cosine coefficient itself, d_ij.
Now, this may not be the best choice.
We just don't have time to go into optimizing this particular choice of weight.
Let's say it's just d_ij.
So if d_ij is positive,
we're adding to the prediction.
If it's negative, we're subtracting from that.
And then we have to normalize somehow because
we might be adding a lot of these movies in the neighborhood.
So we have to divide that by the magnitude of the weights.
The weights can be,
it's just d_ij absolute,
summing over j in the neighborhood of movie i, L_i.
Now, why do we put absolute sign here but not here?
Well because in normalization,
if you don't put absolute value,
the positive and negative d_ij's will cancel each other,
so that's not intention to count their size.
But in the numerator,
if we add absolute value,
then we get confused whether j is very similar to I or very dissimilar to i.
That's why when we calculate the influenced by neighborhood movies j,
we use the actual d_ij which could be a positive or negative,
but when we normalize by the size,
we have to use the absolute value of d_ij's.
Now you can make it even simpler by just making the weights one.
You simply just count or add up the
r-tilde's and divide it by the size of the neighborhood.
That's it. That turns out not to be performing very well,
so we use a slightly more involved weights here.
All right, so this is what we have been looking for in the last, what, 80 minutes.
This is the neighborhood predictor that will enable you
to get quite far ahead in the Netflix Prize competition.
It composed of two parts.
One part is the baseline predictor.
Again, how do we get to the baseline predictor?
Very simple, by solving the least square problems involving these b_u's and b_i's,
because the baseline predictor r-hat is
just the lazy average predictor plus b_u plus b_i for each u,i pair.
OK? So solve least square based on the ground truth,
train your parameters b_i*, b_u*,
stick it into the predictor, you get r-hat.
The second term in the neighborhood predictor is the actual neighborhood information.
Again, we use the cosine coefficient as the metric.
Then for each movie i, we define a neighborhood of a certain size.
And then, based on that,
we say all those movies j in that neighborhood set
will be weighted with a certain weight,
for example, the d_ij themselves, and then normalized.
This is the total influence in the prediction of ui.
So now, let's summarize what we have at this point.
The neighborhood predictor for collaborative filtering in Netflix consists of five steps.
The first step is train your baseline predictor.
r-hat equals r-bar plus b_u plus b_i.
I don't know what should b_u, b_i be,
so I'm going to look at this prediction with the actual ui,
r_ui, and then look at the difference squared,
solve the least squares problem,
that will give me the b_u, b_i,
and therefore the baseline predictor.
OK. Once I have the baseline predictor,
let's call that r-hat,
then we can subtract r from r-hat and get this shifted r-tilde,
which could be positive or negative depending on what's your r-hat.
And then from the r-tilde,
we can compute a similarity metric.
If we collect all these into a matrix,
big R-tilde, and from this big R-tilde,
we get another matrix D where each i,j entry of big D
is simply the d_ij that we computed as a function of these r-tilde's.
Once we have computed this d_ij,
we can define a neighborhood L_i for each movie i,
consisting of a bunch of movies very similar or very dissimilar from movie i.
And once that's done, we can now plug everything into
the r-hat^N_ui formula which we just
shown on the previous page because we have now all the ingredients,
including the baseline, the b's, and the r-tilde's.
And that will give us the final predictor which we
can collect all the ui entries into a particular table or matrix R-hat^sup^N,
N for neighborhood method.
