1
00:00:00,420 --> 00:00:03,040
Welcome back to Mining
of Massive Datasets.

2
00:00:03,040 --> 00:00:07,280
In the previous lecture we looked at
collaborative filtering approaches for

3
00:00:07,280 --> 00:00:08,810
recommender systems.

4
00:00:08,810 --> 00:00:12,530
In this section, we're going to look at
how to evaluate a recommender system,

5
00:00:12,530 --> 00:00:13,970
to make sure that it's doing a good job.

6
00:00:18,370 --> 00:00:19,420
Let's look at an example.

7
00:00:19,420 --> 00:00:22,960
Suppose we have a set of users and movies.

8
00:00:22,960 --> 00:00:25,790
Users on the y axis, movies on the x axis.

9
00:00:25,790 --> 00:00:29,210
And here's a utility matrix
that gives you know,

10
00:00:29,210 --> 00:00:33,650
so, where some of the rating values
are known and some are unknown.

11
00:00:33,650 --> 00:00:36,324
And ratings are a scale
from one through five.

12
00:00:37,980 --> 00:00:44,460
Now the common evaluation methodology
is to take a piece of the matrix and

13
00:00:44,460 --> 00:00:46,340
treat that as a test set.

14
00:00:47,550 --> 00:00:49,160
Now we know these ratings, but

15
00:00:49,160 --> 00:00:52,980
there going to withhold them from
the algorithm that they are going to use.

16
00:00:52,980 --> 00:00:56,880
So we'll call this the test data set,
or the withheld ratings.

17
00:00:56,880 --> 00:01:01,690
And we'll for the purposes of the of the
algorithm these are going to treated as

18
00:01:01,690 --> 00:01:05,110
the same as unknown ratings,
or the blank ratings.

19
00:01:05,110 --> 00:01:07,640
But in fact we know what
these ratings are, so

20
00:01:07,640 --> 00:01:10,680
we can use algorithms to
predict these ratings.

21
00:01:10,680 --> 00:01:13,200
And then compare them against
the actual ratings and

22
00:01:13,200 --> 00:01:14,640
see good the algorithm performed.

23
00:01:20,340 --> 00:01:24,780
So the the trick is to compare
the predictions against the withheld known

24
00:01:24,780 --> 00:01:26,500
ratings of the test set T.

25
00:01:26,500 --> 00:01:32,310
And the most common measure is is a
measure called the root-mean-square error,

26
00:01:32,310 --> 00:01:34,290
or RMSE for short.

27
00:01:34,290 --> 00:01:36,620
And it's very simply defined.

28
00:01:37,630 --> 00:01:40,730
You know as, you know, as the some of

29
00:01:40,730 --> 00:01:45,820
the squares of the deviations from the
actual ratings and the predicted ratings.

30
00:01:45,820 --> 00:01:52,640
So in this case Rxi star is the actual
rating for user X-N item i.

31
00:01:52,640 --> 00:01:56,210
Rxi is the rating that's predicted by,
by our algorithm.

32
00:01:56,210 --> 00:01:58,540
We're going to take the difference
between those two and square it,

33
00:01:58,540 --> 00:02:02,840
and sum of those squares across all the
withheld ratings, and divided by the total

34
00:02:02,840 --> 00:02:06,470
number of withheld ratings which is N,
and just take the square root of that.

35
00:02:06,470 --> 00:02:10,280
So, this is the root mean square error,
or RMSE and it's

36
00:02:10,280 --> 00:02:15,608
the most commonly used measure to evaluate
a, a collaborative filtering system.

37
00:02:15,608 --> 00:02:24,970
Now, while algorithm is a very very simple
measure, it does have a few, few problems.

38
00:02:26,080 --> 00:02:28,230
And, one of the,
one of the most common problems,

39
00:02:28,230 --> 00:02:32,030
is that there's this narrow focus on
accuracy, or RMSE sometimes misses

40
00:02:32,030 --> 00:02:36,560
the point of why we implement recommend,
recommend a system in the first place.

41
00:02:36,560 --> 00:02:42,020
But the goal of the recommended system
is not really to predict the the rating

42
00:02:42,020 --> 00:02:46,560
of a user for a given item, but
to recommend items to a user that the,

43
00:02:46,560 --> 00:02:51,070
the user might buy or
might view or might listen to.

44
00:02:51,070 --> 00:02:56,310
And therefore sometimes when you predict
just the, just the items with the highest

45
00:02:56,310 --> 00:03:00,370
Scores are the highest similarity
you might end up with problems.

46
00:03:00,370 --> 00:03:03,880
The first problem we run into,
is the problem of prediction diversity,

47
00:03:03,880 --> 00:03:06,970
which means that all the predictions
are too similar to each other.

48
00:03:06,970 --> 00:03:10,970
For example, let's say the user
liked the first Harry Potter movie.

49
00:03:10,970 --> 00:03:15,760
Now the set of most similar items or
the set of items with

50
00:03:15,760 --> 00:03:18,880
the best scores might be the,
the other Harry Potter movies.

51
00:03:18,880 --> 00:03:22,000
So all the predictions might
therefore be Harry Potter movies.

52
00:03:22,000 --> 00:03:26,130
Which is you know rather a non
diverse set of recommendations and

53
00:03:26,130 --> 00:03:29,080
might not introduce the user to
any new and interesting items.

54
00:03:31,260 --> 00:03:34,220
The second problem is one of context.

55
00:03:35,440 --> 00:03:42,940
Now, the user might be the same user might
be operating in different contexts and

56
00:03:42,940 --> 00:03:45,440
might want different items in those,
in those contexts.

57
00:03:45,440 --> 00:03:51,620
For example, let's say a user
is travelling to to Patagonia.

58
00:03:51,620 --> 00:03:55,170
He might end up shopping for
lots of travel books on Patagonia.

59
00:03:55,170 --> 00:03:59,910
Then once he, once he's back from
Patagonia the s the set of is similar,

60
00:03:59,910 --> 00:04:04,010
the set of recommended items will include
bo you know more books on Patagonia.

61
00:04:04,010 --> 00:04:05,970
But the user is not
interested in any more,

62
00:04:05,970 --> 00:04:07,820
because the user is in
a very different context.

63
00:04:10,870 --> 00:04:14,770
Finally, the order of predictions also
turns out to be hugely important.

64
00:04:14,770 --> 00:04:17,140
For example,
when there's a series of books or

65
00:04:17,140 --> 00:04:21,870
movies you want to predict, you want
to recommend items that are earlier in

66
00:04:21,870 --> 00:04:25,510
the sequence are ahead of items
that are later in the sequence.

67
00:04:26,890 --> 00:04:31,060
Note also that in practice,
we only care to predict high ratings.

68
00:04:31,060 --> 00:04:33,740
Right?
So, we've sort of set up this whole

69
00:04:33,740 --> 00:04:40,810
problem of, predicting the,
rating of a user X for an item I.

70
00:04:40,810 --> 00:04:46,220
But in practice we don't really care
what the rating of user x for item i is.

71
00:04:46,220 --> 00:04:49,370
And that rating value is low and
the user really doesn't like the item.

72
00:04:49,370 --> 00:04:53,440
We are only going to recommend items to
the user that the user really cares about.

73
00:04:53,440 --> 00:04:58,120
And so we only care to predict high
ratings, not to predict low ratings.

74
00:04:58,120 --> 00:05:02,200
And the RMSE that we've sort of,
defined, routine square error,

75
00:05:02,200 --> 00:05:05,720
actually doesn't distinguish between
high ratings and low ratings.

76
00:05:05,720 --> 00:05:08,950
It only looks at the difference
between the actual ratings and

77
00:05:08,950 --> 00:05:10,150
the predicted ratings.

78
00:05:10,150 --> 00:05:13,180
So, in fact we might come up
with a method that works well in

79
00:05:13,180 --> 00:05:16,770
practice that recommends
very good items to users.

80
00:05:16,770 --> 00:05:22,100
But actually mix bad errors on items
that the user doesn't really like.

81
00:05:22,100 --> 00:05:24,660
Now this algorithm might work
really well in practice, but

82
00:05:24,660 --> 00:05:27,670
it's root being square error
evaluation would look really bad.

83
00:05:30,650 --> 00:05:35,050
So an alternate method that
actually captures this idea is to

84
00:05:35,050 --> 00:05:37,320
use a method called precision at top k.

85
00:05:39,450 --> 00:05:45,110
So let's say the user we, we look at
the withheld ratings of the user,

86
00:05:45,110 --> 00:05:51,150
but only look at the the highest k ratings
in the withheld set for a given user.

87
00:05:51,150 --> 00:05:57,200
And see whether our algorithm can
correct a large fraction of those items.

88
00:05:57,200 --> 00:06:00,030
So the position at top k
is just a percentage of

89
00:06:00,030 --> 00:06:03,650
the predictions that are the user's
top k withheld ratings.