>> [MUSIC PLAYING]
>> BRAIN SCASSELLATI: Welcome to the CS50 AI series.
My name is Scass, and today we're going to talk about recommender systems.
Now recommender systems sounds like kind of an odd name.
It sounds like maybe it should be recommendation systems,
and I kind of agree with you.
But these are the systems that help select out similar things whenever
you select something online.
Netflix, for example will suggest other movies that you might want to watch.
Or Pandora will suggest different songs that you might want to listen to.
Amazon will suggest what kinds of other products you might want to buy.
Facebook will even suggest some of the other friends
that you might want to add.
Each of these systems operate using the same basic kind of algorithm,
and that's what we're going to talk about today.
>> Now these algorithms are surprisingly big business.
Netflix a few years ago in 2009 offered a $1 million
prize if you could improve their recommendation system by just 10%.
That 10%, though, represents a substantial amount of business.
Estimates are hard to come by, but many people
believe that these recommendation systems for an online purchasing
system like Amazon lead to somewhere between 10% and 25% increased revenue.
So you can imagine the kind of volume that you're
talking about when we think about even these little algorithms.
>> So let's get some examples.
How is it that these systems really work?
There are two basic kinds of algorithms that
are at play when we talk about generating recommendations.
The first ones are called content based filtering.
And content based filtering relies upon similarities between the items
themselves, that is between two movies or two songs or two purchased items.
We're going to use movies as an example, but this
could apply, really, to any type of object that we're looking for.
>> So if I think about some movies from the last year,
I saw Inside Out with my kids, they loved it.
But we also had a choice.
We could have gone to see Minions, we could seen Age of Ultron,
or we could have seen Ant Man in the theaters.
>> For any of these movies, we could imagine
generating a list of features or qualities about those different movies.
So for example, I could consider which of those movies are animated.
Well, both Inside Out and Minions are animated.
Neither Age of Ultron nor Ant Man are animated movies.
And I could imagine building up a structure, a table that
lists each of these properties.
Are they animated or not?
I could then add more features to this table
by adding more rows into this structure.
I could ask whether or not they're Marvel movies.
Well, Inside Out and Minions are not Marvel movies,
Age of Ultron and Ant Man certainly are.
>> And I could ask any kinds of different qualities
that I wanted, any kinds of features that might be important to me.
Do they have a super villain?
Well, there's no super villain in Inside Out, but there are ones in Minions
and in, obviously, the two superhero movies.
>> I could also ask things like, well, do they pass the Bechdel test?
Are there two named female characters who
spend some significant amount of time having a conversation that
doesn't involve men in the cast?
Well, in this case, Inside Out passes the test, Minions fails, Age of Ultron
passes the test, and Ant Man fails.
Any one of these features I could think about
as being important for some people.
>> I could also ask things like are there any people in these movies that
are alumni from let's say, Parks and Recreation, one of my favorite shows.
Well, Inside Out has Amy Poehler, that's an Alumni.
That counts.
Jon Hamm was in Minions.
Paul Rudd was in Ant Man, but no one in Age of Ultron was in Parks and Req
as well.
So I can build up this list of features, and they could really
be anything about the movies.
They could be about what aspect ratio they were shot in,
it could be how many seats they sold on their opening weekend.
Any feature that I want to generate I can put into this table.
>> Now, in this case, I've built all sort of Bullion values,
yes or no, pass or fail, but they could be anything.
They could be arbitrary values.
For content based filtering, what we're going to do
is we're going to consider two columns in this table
and see how similar they are.
So for example, if I went to see Inside Out,
I might ask, what are the other movies that I might be willing to go see.
That is, what willing to spend my money to go see.
And I can compare this by just taking the two columns, one from Inside Out
and one from any of the other movies, and just seeing
how many of their features match.
So if I compare Inside Out with Minions, well, there's
three things here that match.
They're both animated, neither of them are Marvel movies, and both of them
have Parks and Req alumni.
So I could count up how many matches there were,
and in this case there'd be three.
>> If I then compare Inside Out with let's say Age of Ultron,
I can look down the list and say, well, there's
only one thing that matches there.
They both pass the Bechtel test, so that's going to be a score of one.
And between Inside Out and Ant Man, again I
can compare line by line how many things match between the two of them.
Well, one's animated, one's not.
One's a Marvel movie, one's not.
One's got a super villain, the other doesn't.
One passes the Bechtel test, one fails it,
but they both have Parks and Req alumni, so again, it gets a score of one.
>> So if I were looking for movies that were similar to Inside Out,
I could look for the movies that have the highest score within this content
filtering scheme.
So in this case, I would consider Minions
to be closer and more likely to be something
that I would spend money to see than Age of Ultron or Ant Man.
>> These content based filtering systems rely just
on the properties of the movies, and so I
can build these just by knowing something about the products
that I have.
I can use any kinds of features that I'd like,
and I can build more complex features that
involve more complex test of a quality as I go along.
In fact, I can even view this table not as being one static object,
but rather as being dimensions within a larger state space.
And I can start talking about the distances between different movies.
These are all things that we know how they
do using the kinds of data structures that we've already seen in CS50.
So I could imagine building a data structure for a movie.
There's a struct that I've constructed called movie,
and it has five Boolean entries in it.
Is it animated, is it a Marvel movie, does it have a super villain,
does it pass the Bechdel test, and are there Parks and Rec alumni in it?
And each of these is a data structure that I
can occupy for that particular movie.
>> Then compute whether two movies are similar or not,
what their score is, I could write out a set of pseudocode that
generates that same function.
That is, given some movie M1, I can find the most similar movie to it
by following the pseudocode.
I consider which is the best scoring system that I've found,
the best comparison that I've found.
For every other movie I'm going to go through,
I'll set a match score equal to 0.
And I'll go through that movie, an M1, the movie
I started with, I'll check each and every feature
that they have to see if there's a match.
If there's a match, I'll increment the match score.
And if at the end the match score that I have is better than the current best
score, then I'll remember that best score,
and this is the best match that I have.
At the end, whatever movie is sitting in best match,
that's the closest I've been able to come.
So these content based filtering systems,
they all have this basic structure.
They rely upon the item in question and nothing
about any of the user preferences.
>> The other mechanism that we use in order to build recommendation systems
is called collaborative filtering.
Collaborative filtering relies upon not the qualities of the object itself,
but how people, other users that is, how they've
responded to these same objects.
So to continue with my movie example, I might take a bunch of my friends
and survey them about whether or not they liked particular movies.
Now different places will generate this data in different ways.
You can directly survey your users, or you could just
see what they choose if you're, for example Netflix.
Which movies did they watch?
>> I might question some of my friends here and find out
that Jason liked every movie he saw, not surprising there.
Andy only liked Minions and Aunt Man.
Sarah liked Inside Out and Avengers, the opposite of Andy.
And Sam, well, Sam liked all of the superhero movies,
but none of the animated movies.
>> I could then query for some new individual, some other user like myself
and ask, well, if I liked one of these movies,
can you make a prediction about which other movies I might like.
That is, if I liked Inside Out, which other movies
am I likely to also want to see based on what similar people did?
That is, I'll go through an I'll filter through this list
and find just the individuals who also liked
Inside Out, who matched my preferences.
Well, that means that Andy and Sam, they didn't like Inside Out,
so I'm not going to consider them.
I'm going to get rid of their data for this comparison.
>> I can then look at what Jason and Sarah thought and tally
up which of the movies that they saw that I didn't, whether they liked them
or not.
I could just count up, let's say votes.
So Minions, for example might have one vote for it, because Jason liked it.
Both Jason and Sarah liked Avengers, so it would have two votes.
And only Jason liked Ant Man, so it would get one vote.
So if I had to then recommend for myself which of these movies
I might be most likely to watch, I would have to choose Age of Ultron: Avengers.
>> So for any of these systems, now I'm using
data that was generated not about the movie itself, but about the preferences
from other users.
This has some difficulties of course.
What if you don't have any other users?
Well, that's called startup problem.
You have to have some quantity of data before you're
able to start making these recommendations.
The flip side of it is once you start collecting data,
if you can collect more and more and more data,
you'll get better and better and better recommendations.
>> Now we could translate this into code as well.
We can define a different kind of structure,
in this case we'll call it a user.
And it's got features about which movies this user liked.
Did they like Inside Out, Minions, Avengers, and Ant Man.
We could then generate some pseudocode to follow
the same procedure that I used before.
That is, given a particular user x, let's recommend a movie
that x might like.
We can go through and for all of the movies,
we can initialize a score for that movie to be 0.
And then we can find all of the other users who
have the same preferences as x.
And then for every movie that they liked,
we'll increment the score of that movie.
Whichever movie in the end has the highest score,
that's the one I should recommend.
>> None of this is really obscure.
None of this is challenging.
These are all basic algorithms that you could implement today.
>> Now with real recommender systems, you run into some problems.
What if there's nobody who matches exactly your preferences?
What if there are users who are exactly your preferences,
but then deviate drastically from what you like?
I like classic Godzilla movies, but my wife doesn't.
I like to watch them, my Netflix account contains them.
Her's doesn't.
What happens when we start mixing data like this?
These are all challenges that you can overcome,
they just take slightly more complex algorithms.
>> Now in the real world, which are actually operational,
do we use content based filtering or do we use collaborative filtering?
And the answer is we use both of them.
Almost all of the major users in this case, Amazon, Facebook, Netflix,
Pandora, they all use a combination of these different recommendation systems.
And when we combine the choices from each, we call them hybrid systems.
They in some way depend upon the features of the object itself,
and in some ways they depend upon the preferences of other users.
These hybrid systems, they're big business,
and they're what's current today.
>> So thanks very much for joining me.
I hope you've gotten a little bit of an understanding of what
makes these systems work.
Next time you're online, remember that not only you influencing your choices,
but potentially everyone else's as well.
Thanks again.