1
00:00:00,460 --> 00:00:04,290
So talking about
Latent Factor Recommender Systems.

2
00:00:04,290 --> 00:00:07,830
The, the main idea of
the Latent Factor Recommender Systems,

3
00:00:07,830 --> 00:00:12,810
is that we will think of recommendations
as an optimization problem.

4
00:00:12,810 --> 00:00:15,030
And the way we think of this
as an optimization problem,

5
00:00:15,030 --> 00:00:18,450
is that we think of recommendations
as a rating prediction.

6
00:00:18,450 --> 00:00:22,530
And then the optimization is that we
want to find the method that gives us

7
00:00:22,530 --> 00:00:24,590
best rating predictions.

8
00:00:24,590 --> 00:00:26,860
So here's, here's the global idea.

9
00:00:26,860 --> 00:00:30,960
The global idea, or the goal is that
we want to make good recommendations.

10
00:00:30,960 --> 00:00:34,340
The way we talked about
the goodness of recommendations,

11
00:00:34,340 --> 00:00:36,260
was using the root mean square data.

12
00:00:36,260 --> 00:00:38,160
Right, the idea is the smaller the root,

13
00:00:38,160 --> 00:00:43,040
the root mean square data of recommender
systems the better the recommendations.

14
00:00:43,040 --> 00:00:46,100
Of course, what we would really
want is that we would want to

15
00:00:46,100 --> 00:00:50,478
make good recommendations on items
that people haven't yet seen.

16
00:00:50,478 --> 00:00:54,590
Right, basically want to predict in
the future what people are going to like.

17
00:00:54,590 --> 00:00:58,050
Of course, we cannot really do
this because we are not prophets.

18
00:00:58,050 --> 00:00:59,430
We don't know that future.

19
00:00:59,430 --> 00:01:03,810
So what we will kind of have to be
satisfied with is the second point, right?

20
00:01:03,810 --> 00:01:06,960
We, we want to build
a system that is able to

21
00:01:06,960 --> 00:01:10,560
predict the ratings that
we already have well.

22
00:01:10,560 --> 00:01:14,020
In a sense, what do I mean by this,
is that we have our rating matrix.

23
00:01:14,020 --> 00:01:16,440
We will hide a few entries from it, and

24
00:01:16,440 --> 00:01:19,540
our goal would be to
predict those ratings well.

25
00:01:19,540 --> 00:01:22,410
And hopefully, by doing that,
if we then go and

26
00:01:22,410 --> 00:01:27,600
take this recommender system and release
it, let's say live on the Netflix website,

27
00:01:27,600 --> 00:01:32,560
that, that system would also work well for
the truly unknown ratings.

28
00:01:33,990 --> 00:01:34,830
Right?
So the way we

29
00:01:34,830 --> 00:01:40,020
think about rating prediction for
recommender systems is the following.

30
00:01:40,020 --> 00:01:44,990
We have our rating matrix R with users and
movies.

31
00:01:44,990 --> 00:01:49,470
And our goal is that we want to make
a system that predicts well the,

32
00:01:49,470 --> 00:01:50,940
the hidden ratings.

33
00:01:50,940 --> 00:01:54,490
What do I mean by this, is that we
will take some of the ratings from,

34
00:01:54,490 --> 00:01:59,490
from our rate utility matrix and
we will hide them.

35
00:01:59,490 --> 00:02:03,690
And our goal will be to build a system
that for each of these cells,

36
00:02:03,690 --> 00:02:07,290
kind of exactly predicts
the value that is in that cell.

37
00:02:07,290 --> 00:02:08,270
Right?
So we want to

38
00:02:08,270 --> 00:02:11,240
kind of hide the known things and
then predict it.

39
00:02:11,240 --> 00:02:15,840
And the idea is that the, the system
that is able to make the smaller root

40
00:02:15,840 --> 00:02:18,000
mean square error between
the true ratings and

41
00:02:18,000 --> 00:02:20,930
the predicted one,
that's the best system we have.

42
00:02:22,540 --> 00:02:27,420
Now, how do we approach the rating
predict, prediction problem?

43
00:02:27,420 --> 00:02:31,210
The way we will approach this
is through matrix factorization.

44
00:02:31,210 --> 00:02:35,010
And this is why these models
are called latent factor models,

45
00:02:35,010 --> 00:02:38,880
because we basically go and
factorize the matrix.

46
00:02:38,880 --> 00:02:42,550
In some sense, we will be applying
singular value decomposition, or

47
00:02:42,550 --> 00:02:47,230
a version of singular value decomposition
to the Netflix utility matrix.

48
00:02:47,230 --> 00:02:49,440
And the way we will do
this is the following.

49
00:02:49,440 --> 00:02:51,100
So, we are given our matrix,

50
00:02:51,100 --> 00:02:56,150
R, and we will try to represent our
matrix R as a product of two matrices.

51
00:02:56,150 --> 00:02:59,000
Matrix Q and matrix P, right?

52
00:02:59,000 --> 00:03:06,170
So, we will say that matrix R
equals matrix Q times matrix P.

53
00:03:06,170 --> 00:03:08,200
The difference here is the following,
right?

54
00:03:08,200 --> 00:03:13,820
So if you think of the matrix R as items
to users or movies to users, then we can

55
00:03:13,820 --> 00:03:19,410
think of matrices P and Q as kind of
thin and very long matrices, right.

56
00:03:19,410 --> 00:03:25,660
So for example, we will think of
matrix Q to have the one row per item.

57
00:03:25,660 --> 00:03:31,430
And it will have k columns, or k factors,
where k is some value that we will decide.

58
00:03:31,430 --> 00:03:34,410
And usually you can think of this
K as maybe 100, 200, 300, right?

59
00:03:34,410 --> 00:03:42,200
So something much smaller than what is
the total number of users in our data set.

60
00:03:42,200 --> 00:03:46,980
And similarly, matrix B will be this
kin d of also very thin matrix,

61
00:03:46,980 --> 00:03:50,310
where we have one column per user, and

62
00:03:50,310 --> 00:03:55,574
it has KUO, where again K is this
parameter that, that we choose.

63
00:03:55,574 --> 00:04:01,160
Right, so for now let's just assume
that we can approximate our matrix R

64
00:04:01,160 --> 00:04:07,260
simply as a product of two theme,
or narrow matrices, Q and P, okay?

65
00:04:07,260 --> 00:04:11,630
And there is only issue that R really
has missing or unknown entries.

66
00:04:11,630 --> 00:04:16,320
Right, that there are these regions
of matrix R that are all unknown.

67
00:04:16,320 --> 00:04:18,600
But for now, let's ignore them, okay.

68
00:04:18,600 --> 00:04:22,770
So what we did is we, we kind of
automatically assumed that we can take R

69
00:04:22,770 --> 00:04:28,640
and factorize it into this two as
a product of these two matrices.

70
00:04:28,640 --> 00:04:33,420
Okay, what this really does to,
to to the data is the following.

71
00:04:33,420 --> 00:04:38,560
The way we can think of every
row of our matrix Q, or

72
00:04:38,560 --> 00:04:43,010
every column of our matrix P,
is that basically every item and

73
00:04:43,010 --> 00:04:46,960
every user gets mapped into
this three dimensional space.

74
00:04:46,960 --> 00:04:49,160
Right?
So we can think of every row or

75
00:04:49,160 --> 00:04:54,205
our column of P simply as a,
as a three, let's say,

76
00:04:54,205 --> 00:04:59,810
three-dimensional representation of
a given user or of a given movie, right?

77
00:04:59,810 --> 00:05:03,880
So what this really means is that we
took this big utility matrix R, and

78
00:05:03,880 --> 00:05:08,690
now we took all the movies and
all the users and map them into this.

79
00:05:08,690 --> 00:05:12,720
In as, I showed in the previous slide in
this kind of three dimensional space.

80
00:05:12,720 --> 00:05:19,670
And this is why in this axis of this
latent subspace are called factors.

81
00:05:19,670 --> 00:05:22,840
Right, so
kind of the idea is that now movies and

82
00:05:22,840 --> 00:05:26,960
also users get mapped
into this into this space

83
00:05:26,960 --> 00:05:32,360
where basically this axis that we
find here are the axis of variation.

84
00:05:32,360 --> 00:05:34,320
Right?
So maybe just hypothetically,

85
00:05:34,320 --> 00:05:38,720
imagine that what our factorization
would discover is that we have,

86
00:05:38,720 --> 00:05:41,650
our space has too many axis of variation.

87
00:05:41,650 --> 00:05:44,600
There are movies that
are geared towards females.

88
00:05:44,600 --> 00:05:46,660
And there are kind of the guy's movies.

89
00:05:46,660 --> 00:05:48,720
And then there are you know,
the serious movies.

90
00:05:48,720 --> 00:05:50,340
And then there are funny movies.

91
00:05:50,340 --> 00:05:55,590
Right and now every user is is a data
point somewhere in this space, and

92
00:05:55,590 --> 00:05:59,410
also every movie is a data
point in this space, right?

93
00:05:59,410 --> 00:06:00,360
And some users and

94
00:06:00,360 --> 00:06:05,550
movies are closer together than some
other pairs of movies and users.

95
00:06:05,550 --> 00:06:09,140
Right, so that's kind of what latent
factor recommender system is doing.

96
00:06:09,140 --> 00:06:13,420
In some sense, it's finding this low
dimensional representation of users and

97
00:06:13,420 --> 00:06:16,500
movies, such that kind of
people that like those

98
00:06:16,500 --> 00:06:19,360
movies are are close
together with each other.

99
00:06:20,620 --> 00:06:25,500
So now, assuming that we can do
this take the matrix out and,

100
00:06:25,500 --> 00:06:28,160
and represent it as matrix, matrix P and

101
00:06:28,160 --> 00:06:33,450
Q, the question is, how do we estimate
the missing rating of the matrix R?

102
00:06:33,450 --> 00:06:36,540
Right, so for example,
what is our prediction for

103
00:06:36,540 --> 00:06:39,000
a given cell of the matrix R.

104
00:06:40,020 --> 00:06:41,020
That is very easy.

105
00:06:41,020 --> 00:06:42,690
All we have to do is to say a-ha!

106
00:06:42,690 --> 00:06:47,170
We are making a prediction for
user number four and item number two.

107
00:06:47,170 --> 00:06:52,620
So all this means is we have to take
the corresponding row from the matrix Q,

108
00:06:52,620 --> 00:06:54,890
and the corresponding
column from matrix P.

109
00:06:54,890 --> 00:06:59,820
And now what we do, is basically we dot
product these two vectors with each other.

110
00:06:59,820 --> 00:07:03,490
Right?
So basically we do weighted combination or

111
00:07:03,490 --> 00:07:05,530
inner product between these two vectors.

112
00:07:05,530 --> 00:07:07,740
And if we would, if we were to go and

113
00:07:07,740 --> 00:07:11,990
multiply these two vectors together,
the prediction we will get is 2.4.

114
00:07:11,990 --> 00:07:15,570
Right, and so
the prediction about user four liking

115
00:07:17,870 --> 00:07:22,495
movie number two, basically,
predicting the rating, would be 2.4.

116
00:07:23,800 --> 00:07:27,150
So, what this really does,
as I mentioned before, is that,

117
00:07:27,150 --> 00:07:31,790
that the whole method discovers these
latent factors or these latent dimensions.

118
00:07:31,790 --> 00:07:36,090
In which the movies can be mapped
according to the matrix Q and

119
00:07:36,090 --> 00:07:41,410
also people can be mapped into the same
space according to the matrix B.

120
00:07:41,410 --> 00:07:44,736
Right?
So what would happen under this this view

121
00:07:44,736 --> 00:07:49,984
is that users are pointing this space,
movies are pointing this space, and

122
00:07:49,984 --> 00:07:56,566
then the prediction basically means is
that what users are close to what movies.

123
00:07:56,566 --> 00:08:00,645
Of course, this also very nicely relates
to the singular value decomposition that

124
00:08:00,645 --> 00:08:02,430
we already know about.

125
00:08:02,430 --> 00:08:04,680
So let me remind you about the SVD.

126
00:08:05,960 --> 00:08:11,210
What SVD does right, in that lecture we
said let's assume we have some matrix A,

127
00:08:11,210 --> 00:08:15,970
and we want to represent this matrix as
a product of three matrices U, Sigma, and

128
00:08:15,970 --> 00:08:17,740
V transpose, right?

129
00:08:17,740 --> 00:08:23,440
And we, we called the matrix U to be
the matrix of left singular vectors.

130
00:08:23,440 --> 00:08:27,690
Matrix Sigma,
is the diagonal matrix of singular values.

131
00:08:27,690 --> 00:08:32,118
And the matrix V, is the matrix
of right singular vectors, right.

132
00:08:32,118 --> 00:08:35,985
And we showed in that lecture that this
can be done for any matrix, and so

133
00:08:35,985 --> 00:08:37,370
on and so forth, right?

134
00:08:37,370 --> 00:08:41,060
So in some sense,
SVD is already doing what we want, right?

135
00:08:41,060 --> 00:08:45,310
So, if we take our matrix R and
perform SVD of it,

136
00:08:45,310 --> 00:08:50,240
then we could simply take the matrix U and
call it as matrix Q.

137
00:08:50,240 --> 00:08:55,520
And we would, we could take the product
of sigma times V transposed and call, and

138
00:08:55,520 --> 00:08:58,560
call this part our P transposed.

139
00:08:58,560 --> 00:09:00,790
Right?
So, in some sense,

140
00:09:00,790 --> 00:09:05,380
SVD is already kind of doing what it
seems it's doing what you want, right?

141
00:09:05,380 --> 00:09:10,510
So that R equals Q times P transposed.

142
00:09:10,510 --> 00:09:13,110
And SVD is able to compute this for us.

143
00:09:13,110 --> 00:09:16,010
However, even though it seems we are done,
we are not really done.

144
00:09:17,300 --> 00:09:20,790
Before I tell you why we are not
really done, let me tell you kind of

145
00:09:20,790 --> 00:09:24,820
one more good thing that kind
of comes from SVD for free.

146
00:09:24,820 --> 00:09:27,365
So one thing that we
know about SVD is that,

147
00:09:27,365 --> 00:09:30,566
SVD gives us minimum reconstruction error,
right?

148
00:09:30,566 --> 00:09:31,865
SVD gives us the,

149
00:09:31,865 --> 00:09:37,497
the minimum sum of squared errors between
the true value of the, of in an entry

150
00:09:37,497 --> 00:09:44,020
of the matrix versus the approximated
value of that entering the matrix, right?

151
00:09:44,020 --> 00:09:49,880
This is the Aij is the entering the data
matrix, and sigma U times sigma

152
00:09:49,880 --> 00:09:55,270
times V transposed is basically the, the
value the approximation coming from SVD.

153
00:09:55,270 --> 00:09:58,260
And we already know that SVD gives us,

154
00:09:58,260 --> 00:10:01,820
in some sense, is the solution to
this minimization problem, right?

155
00:10:01,820 --> 00:10:07,110
Finding the three matrices such that
the approximation is as good as possible.

156
00:10:08,250 --> 00:10:09,990
What is there to note?

157
00:10:09,990 --> 00:10:13,180
First thing to note is that
this sum of squared errors,

158
00:10:13,180 --> 00:10:16,280
is basically the same as
the root mean squared error, or

159
00:10:16,280 --> 00:10:19,110
is related to the moo,
root mean squared error, right?

160
00:10:19,110 --> 00:10:19,960
If the sum of square,

161
00:10:19,960 --> 00:10:24,000
squared errors is small, the root
mean square error will also be small.

162
00:10:24,000 --> 00:10:25,030
Why?
Because the two

163
00:10:25,030 --> 00:10:27,130
are monotonically related, right?

164
00:10:27,130 --> 00:10:31,420
Root mean square error is nothing
else than sum of squared errors,

165
00:10:31,420 --> 00:10:32,820
the square root of that, and

166
00:10:32,820 --> 00:10:37,890
then multiplied by some constant,
1 over the number of data points, right?

167
00:10:37,890 --> 00:10:39,690
What this basically means is that,

168
00:10:39,690 --> 00:10:43,190
SVD is already minimizing the root
mean square error, right?

169
00:10:43,190 --> 00:10:48,380
Actually SVD is able to find the product
that the three matrices that

170
00:10:48,380 --> 00:10:51,790
give us the best possible root
mean square error, right?

171
00:10:51,790 --> 00:10:52,700
Which is great.

172
00:10:52,700 --> 00:10:56,528
So, it seems SVD that I
think to do in this case.

173
00:10:56,528 --> 00:11:00,490
However, there is one slight complication,
and this is, this I write here.

174
00:11:00,490 --> 00:11:01,100
Right?

175
00:11:01,100 --> 00:11:08,240
The complication is that SVD assumes that
the matrix A, has all the entries given.

176
00:11:08,240 --> 00:11:11,770
Right?
The summation here, ij over A,

177
00:11:11,770 --> 00:11:14,780
goes over all the entries of matrix A.

178
00:11:14,780 --> 00:11:15,360
Right?

179
00:11:15,360 --> 00:11:17,820
The matrix A is kind of
completely filled in.

180
00:11:17,820 --> 00:11:20,620
But our matrix R, is not filled in.

181
00:11:20,620 --> 00:11:22,540
Right?
Most of the matrix is empty.

182
00:11:22,540 --> 00:11:25,950
Meaning for most of, for
most part of that matrix,

183
00:11:25,950 --> 00:11:29,560
we don't know how much does
a given user like a given movie.

184
00:11:29,560 --> 00:11:31,950
So if we were just to ignore those parts,

185
00:11:31,950 --> 00:11:37,160
basically what that mean is that no
rating is integrated as zero rating.

186
00:11:37,160 --> 00:11:39,480
Which is clearly wrong in our case.

187
00:11:39,480 --> 00:11:40,540
Right?
So this me,

188
00:11:40,540 --> 00:11:43,370
really means that R has missing entries,
and

189
00:11:43,370 --> 00:11:47,540
SVD is not able to accurately account for
the missing entries.

190
00:11:47,540 --> 00:11:50,250
So, we have to kind of be a bit smarter.

191
00:11:50,250 --> 00:11:53,240
We have to take, think of the SVD,
but change it a bit.

192
00:11:54,480 --> 00:11:58,820
So, the way we change the SVD is,
is the following, right?

193
00:11:58,820 --> 00:12:03,210
What, what we know is that
SVD isn't defined when for

194
00:12:03,210 --> 00:12:04,890
the entries that are missing.

195
00:12:04,890 --> 00:12:07,724
So, what we need to do,
is we need to basically,

196
00:12:07,724 --> 00:12:11,820
we will have to use special meth,
specialized methods to find P and Q.

197
00:12:11,820 --> 00:12:13,762
In particular, we will, we will do,

198
00:12:13,762 --> 00:12:16,450
we will solve the following
optimization problem.

199
00:12:16,450 --> 00:12:19,172
Right?
Recommendations as optimizations,

200
00:12:19,172 --> 00:12:22,138
in the sense that we want
to find matrices P and

201
00:12:22,138 --> 00:12:26,840
Q that minimize the sum of squared errors,
but now the errors, right?

202
00:12:26,840 --> 00:12:30,410
The, the, they only go over
the entities of matrix r.

203
00:12:30,410 --> 00:12:33,460
Meaning, we only go over
the yellow entries of matrix R,

204
00:12:33,460 --> 00:12:36,330
and not all the cells of the matrix.

205
00:12:36,330 --> 00:12:36,900
Right?

206
00:12:36,900 --> 00:12:39,010
And what, what this is saying
is the following, right?

207
00:12:39,010 --> 00:12:43,530
So, I want to find matrices P and
Q, such that, when I sum over all

208
00:12:43,530 --> 00:12:49,260
the known ratings, the, the value of
that rating minus my predicted rating,

209
00:12:49,260 --> 00:12:54,860
that difference,
squared is as small as possible, right?

210
00:12:54,860 --> 00:12:58,350
So, now, the game is kind of,
it's very clear.

211
00:12:58,350 --> 00:13:01,910
I want to find matrices P and
Q that minimize this expression,

212
00:13:01,910 --> 00:13:07,820
that are basically best able to predict
known, known ratings in my matrix R.

213
00:13:07,820 --> 00:13:11,195
And I hope that by being able
to find such matrices P and Q,

214
00:13:11,195 --> 00:13:16,700
I'll be also able to predict well the may,
the ratings that I don't even know.

215
00:13:16,700 --> 00:13:17,920
So the unknown ratings.

216
00:13:19,130 --> 00:13:21,120
A few things to note here.

217
00:13:21,120 --> 00:13:25,470
First is the difference with SVD,
is that here, for P and

218
00:13:25,470 --> 00:13:27,230
Q are kind of completely arbitrary.

219
00:13:27,230 --> 00:13:32,400
So we don't require that
columns are orthonormal meaning

220
00:13:32,400 --> 00:13:35,430
that vectors are unit length, and
they are orthogonal to each other.

221
00:13:36,730 --> 00:13:41,880
As I mentioned before, we can think of
matrices P and Q as mappings of users,

222
00:13:41,880 --> 00:13:46,580
ma, mappings of movies into
this low dimensional space.

223
00:13:46,580 --> 00:13:48,340
And what is interesting is that this was,

224
00:13:48,340 --> 00:13:52,390
if there was kind of one big
breakthrough in the Netflix challenge,

225
00:13:52,390 --> 00:13:56,840
then these latent factor recommander
systems were the most widely used.

226
00:13:56,840 --> 00:14:01,870
And also the most successful
method in the whole competition.

227
00:14:01,870 --> 00:14:06,270
So what we will do next now, is we will
learn how to actually go and solve

228
00:14:06,270 --> 00:14:12,190
this latent factor optimization problem,
so the equation I have written here