1
00:00:00,260 --> 00:00:04,790
So far, we saw our singular value
decomposition on this small users to

2
00:00:04,790 --> 00:00:09,350
movies example, where what we saw was
basically we took this regional matrix and

3
00:00:09,350 --> 00:00:12,780
we were able to represent it as
a product of three matrices.

4
00:00:12,780 --> 00:00:17,790
And there, we talked about the sci-fi
concept, the romance concept, and

5
00:00:17,790 --> 00:00:20,460
then there was this, also,
the third column that we kind of

6
00:00:20,460 --> 00:00:24,950
had very low strength, right, the third
concept that had very small strength.

7
00:00:24,950 --> 00:00:28,350
That we kind of brushed under the rug and
didn't really talk about.

8
00:00:28,350 --> 00:00:31,710
So what I want to do now is actually
talk about, how do we really do di,

9
00:00:31,710 --> 00:00:32,810
dimensionality reduction?

10
00:00:32,810 --> 00:00:37,720
In a sense, how do we discover that our,
movie data, really had only two real kind

11
00:00:37,720 --> 00:00:41,910
of strong concept and the, the, the last
third concept, was more like noise.

12
00:00:41,910 --> 00:00:46,830
And it was okay to, to kind of remove
it from our analysis and discussion.

13
00:00:46,830 --> 00:00:49,930
So the idea is, how do we,
what is SVD really doing and

14
00:00:49,930 --> 00:00:52,980
how do we think about it in terms
of dimensionality reduction?

15
00:00:52,980 --> 00:00:54,800
And, what SVD is really trying to do,

16
00:00:54,800 --> 00:00:59,380
it basically, in some sense it gives us,
the best axis to project on.

17
00:00:59,380 --> 00:01:02,830
So what do we mean by this is that the,
the best means that,

18
00:01:02,830 --> 00:01:07,300
the sum of the squared
projection errors is minimized.

19
00:01:07,300 --> 00:01:09,310
Okay.
So in some sense, we want,

20
00:01:09,310 --> 00:01:15,030
we want small set of xs such that we,
if we represent our data in terms of that,

21
00:01:15,030 --> 00:01:18,600
of that axis we get the minimum
reconstruction error.

22
00:01:18,600 --> 00:01:23,360
And a simple example how see this, would
be in this two-dimensional example, where

23
00:01:23,360 --> 00:01:29,610
imagine every different axis is a separate
movie, and we have users ranking movies.

24
00:01:29,610 --> 00:01:32,150
And every point is now a user.

25
00:01:32,150 --> 00:01:37,400
And the x position of this mark is how
much they, they rated use Movie 1 and

26
00:01:37,400 --> 00:01:39,690
y position is how much they rated Movie 2.

27
00:01:39,690 --> 00:01:43,700
And assume that our data lies in
this kind of, in this kind of shape.

28
00:01:43,700 --> 00:01:45,630
So then if you think of of it and say,

29
00:01:45,630 --> 00:01:49,130
okay, we are only given one coordinate
to be able to represent this data.

30
00:01:49,130 --> 00:01:51,940
So not two coordinates, but
I only give you one coordinate.

31
00:01:51,940 --> 00:01:56,450
What is the best, axis, along which
you want to represent this data.

32
00:01:56,450 --> 00:01:59,710
So for example in this case,
this would be the best axis.

33
00:01:59,710 --> 00:02:04,560
And now every data point, we can represent
as a single number, which is simply,

34
00:02:04,560 --> 00:02:08,916
the position or the projection of
a given data point on, on this slide.

35
00:02:08,916 --> 00:02:13,240
So for example, the, the,
the data point that I'm just drawing the,

36
00:02:13,240 --> 00:02:18,910
the red data point here would project to
this line to this particular, location.

37
00:02:18,910 --> 00:02:21,750
And now, my goal is that when
I now represent these two

38
00:02:21,750 --> 00:02:25,240
dimensional points simply by the,
by their position on,

39
00:02:25,240 --> 00:02:30,040
along my red line, the sum of
the squared errors of the locations.

40
00:02:30,040 --> 00:02:34,330
So basically the dis, the distance
between, its true position in the,

41
00:02:34,330 --> 00:02:38,520
in the position a,
along the line should be minimal, and

42
00:02:38,520 --> 00:02:40,300
this is exactly what SVD does.

43
00:02:40,300 --> 00:02:44,170
So, what SVD does is finds
the best vectors, or axis,

44
00:02:44,170 --> 00:02:48,810
on which to project the data, such that
the reconstruction error is minimized.

45
00:02:48,810 --> 00:02:51,420
So let me give you an example
of what do I mean by this.

46
00:02:51,420 --> 00:02:55,250
And now for example, also the question is,
given this two-dimensional data,

47
00:02:55,250 --> 00:02:58,950
how do I discover the best,
the best axis on which to project?

48
00:02:58,950 --> 00:03:00,700
And how do I really do
dimensionality reduction?

49
00:03:00,700 --> 00:03:04,800
How do I discover the position
of the point on this given line?

50
00:03:04,800 --> 00:03:06,790
So the idea is the following.

51
00:03:06,790 --> 00:03:08,070
We are given our matrix A.

52
00:03:09,340 --> 00:03:10,560
And we want to,

53
00:03:10,560 --> 00:03:14,320
we represent it as a product of three
matrices, u sigma and v transpose.

54
00:03:14,320 --> 00:03:21,400
Where we think of V, as a movie-to-concept
matrix and U as a user-to-concept matrix.

55
00:03:21,400 --> 00:03:24,300
So what this means
immediately that we see that,

56
00:03:24,300 --> 00:03:27,930
V is a movie-to-concept matrix which means
that for example if you want to ask,

57
00:03:27,930 --> 00:03:32,350
what is this vector V1 along which it
is the best to represent the data,

58
00:03:32,350 --> 00:03:36,070
that is simply the first straw
of our matrix V transpose.

59
00:03:36,070 --> 00:03:38,860
All right, so
this is exactly the, the vector,

60
00:03:38,860 --> 00:03:44,910
That represents the the,
the 's of the highest variation.

61
00:03:44,910 --> 00:03:46,920
So, I, I have still my,

62
00:03:46,920 --> 00:03:53,150
our old example of users to [INAUDIBLE]
represented And SVD of this thing.

63
00:03:53,150 --> 00:03:56,110
And now the question is,
how do we do the dimensionality reduction?

64
00:03:56,110 --> 00:03:59,630
So for example the way, we do
dimensionality reduction is that we can

65
00:03:59,630 --> 00:04:04,802
think of the whole system the,
the following that our first right

66
00:04:04,802 --> 00:04:10,070
singular vector, gives us the, location
the axis on which we want to project.

67
00:04:10,070 --> 00:04:14,890
And then the, the corresponding singular
value, tells us the variance along that

68
00:04:14,890 --> 00:04:18,190
given dimension or the spread of
the values along that given dimension.

69
00:04:18,190 --> 00:04:20,940
So in our two dimensional case here,
the va,

70
00:04:20,940 --> 00:04:25,090
the values are really spread
around the first singular vector.

71
00:04:25,090 --> 00:04:29,400
They are spread around the bit,
the second singular vector a bit less.

72
00:04:29,400 --> 00:04:32,593
And they are not really spread
around the first singular vector.

73
00:04:32,593 --> 00:04:36,378
So the, strength of the import,
importance of that vector, is very small.

74
00:04:36,378 --> 00:04:42,740
So now what we can think of, we can
think of the locations as the following.

75
00:04:42,740 --> 00:04:45,790
So, so far I talk to you,
what defines the axis?

76
00:04:45,790 --> 00:04:48,940
Now, the next question is,
what defines the positions, or

77
00:04:48,940 --> 00:04:51,810
coordinates of the points in
this new then, new space?

78
00:04:51,810 --> 00:04:54,940
And the way we can, think of that is
that we simply take the matrix U,

79
00:04:54,940 --> 00:04:57,500
and multiply it with si, with sigma.

80
00:04:57,500 --> 00:04:58,340
Right.
And this gives us

81
00:04:58,340 --> 00:05:01,590
the coordinates of the points in,
on this projection axis.

82
00:05:01,590 --> 00:05:04,180
Right.
So, basically, how do they map down,

83
00:05:04,180 --> 00:05:05,260
to our length.

84
00:05:05,260 --> 00:05:08,100
Right.
So, for example, if I compute,

85
00:05:08,100 --> 00:05:13,490
given my matrix A,
I compute the product of U times sigma.

86
00:05:13,490 --> 00:05:18,830
Here is the, here is now the position
of every, of every user in this new,

87
00:05:18,830 --> 00:05:22,820
new space where, for example,
the first vector simply tells us what is

88
00:05:22,820 --> 00:05:28,070
the location of every user, along,
along the first right singular vector.

89
00:05:28,070 --> 00:05:29,630
And for example here you see that,

90
00:05:29,630 --> 00:05:32,710
the values vary quite
a lot along the first one.

91
00:05:32,710 --> 00:05:34,910
The vary quite a lot along the second one,
right?

92
00:05:34,910 --> 00:05:36,060
The range is very high.

93
00:05:36,060 --> 00:05:39,750
But for example the third one,
everything is kind of around 0 or

94
00:05:39,750 --> 00:05:43,870
the, the variation on the,
along the third column is much smaller.

95
00:05:43,870 --> 00:05:50,250
Which is why the, the third concept had a,
had a very small weight.

96
00:05:50,250 --> 00:05:54,770
So now, given that we have our matrix
A and again the singular value

97
00:05:54,770 --> 00:05:58,760
decomposition of it, the question is, how
do we really do dimensionality reduction?

98
00:05:58,760 --> 00:06:01,170
All right, so so far I just
showed you how we can represent,

99
00:06:01,170 --> 00:06:05,220
the regional data points in this
new in this new projected space.

100
00:06:05,220 --> 00:06:07,820
But the question is, how do we
really do dimensionality reduction.

101
00:06:07,820 --> 00:06:09,650
And that turns out to be very simple.

102
00:06:09,650 --> 00:06:12,040
All basically we need to do,
is we need to go, and

103
00:06:12,040 --> 00:06:15,310
set a given set of singular values to 0.

104
00:06:15,310 --> 00:06:17,780
And basically we take the smallest,
if we want to preserve,

105
00:06:17,780 --> 00:06:21,780
preserve K dimensions,
then basically we take R minus K singular,

106
00:06:21,780 --> 00:06:24,480
smallest singular values,
and set them to 0.

107
00:06:24,480 --> 00:06:28,340
So for example in our case here,
if we want to do dimensionality reduction

108
00:06:28,340 --> 00:06:31,930
from this three dimensional space,
to a two dimensional space,

109
00:06:31,930 --> 00:06:36,330
all we need to do is take the small,
the small singular value, set it to 0.

110
00:06:36,330 --> 00:06:43,290
Which in some sense means, we that now
we also take the third column of U and

111
00:06:43,290 --> 00:06:46,700
third row of V transpose and
set them to 0.

112
00:06:46,700 --> 00:06:52,540
So, the way we can do dimensionality
reduction is to now take U, then

113
00:06:52,540 --> 00:06:57,690
you sigma and then you retranspose where
we took the last singular value, the last

114
00:06:57,690 --> 00:07:02,770
singular vector, and the last right
singular vector, we set all of those to 0.

115
00:07:02,770 --> 00:07:07,666
So if we would now, for example go, and
take, take the three new matrices that,

116
00:07:07,666 --> 00:07:12,370
that are now smaller right,
they only have two columns and two rows.

117
00:07:12,370 --> 00:07:14,250
And multiply this thing together.

118
00:07:14,250 --> 00:07:15,920
Here is the matrix we would obtain.

119
00:07:15,920 --> 00:07:18,700
Right, so here is our ori,
original matrix A.

120
00:07:18,700 --> 00:07:21,230
Here is our, new matrix A.

121
00:07:21,230 --> 00:07:24,540
Call it A prime or let's give it a name B.

122
00:07:24,540 --> 00:07:28,470
And what you notice is that, A and
B are very similar to each other.

123
00:07:28,470 --> 00:07:32,710
So what do I mean by similar to each
other is that if I take a given element.

124
00:07:32,710 --> 00:07:36,570
For example this number 5 here, and
I compare it to this value here,

125
00:07:36,570 --> 00:07:40,300
to the same axis in to
the same cell in matrix B.

126
00:07:40,300 --> 00:07:42,340
We see that the difference is very small.

127
00:07:42,340 --> 00:07:45,030
Right?
Or, for example, I can take this 0 here,

128
00:07:45,030 --> 00:07:48,930
correspond it compare it to
the corresponding element in B,

129
00:07:48,930 --> 00:07:52,040
and again I see
the difference is very small.

130
00:07:52,040 --> 00:07:57,500
So what we basically did is we took in the
previous slide we took our original matrix

131
00:07:57,500 --> 00:08:03,800
A representative, did SVD and we were
able now to exactly reconstruct it.

132
00:08:03,800 --> 00:08:08,860
Now we actually took removed
a few col last column from U and

133
00:08:08,860 --> 00:08:12,360
the last column from V, and
we removed the singular value.

134
00:08:13,378 --> 00:08:17,640
Now we represent everything as a,
as a, as a smaller set of matrices.

135
00:08:17,640 --> 00:08:19,670
So these matrices are now smaller.

136
00:08:19,670 --> 00:08:25,790
If we multiply the three matrices
together now the new matrix we obtained,

137
00:08:25,790 --> 00:08:28,550
was very similar to the original matrix A.

138
00:08:28,550 --> 00:08:31,840
And when I say very similar,
we can quantify the similarity of

139
00:08:31,840 --> 00:08:35,160
two matrices using what is called
the Frobenius norm, right.

140
00:08:35,160 --> 00:08:39,410
And the Frobenius norm of
two matrices is simply the,

141
00:08:39,410 --> 00:08:41,700
the sum of the differences
of their entries, right?

142
00:08:41,700 --> 00:08:45,470
So if I say I have matrix A,
I have matrix B.

143
00:08:45,470 --> 00:08:48,008
So their distance, their Frobenius norm,

144
00:08:48,008 --> 00:08:51,035
is simply,
I take a summation over all the entries.

145
00:08:51,035 --> 00:08:55,496
I take the difference of the entry
values sum them square the top

146
00:08:55,496 --> 00:09:00,114
sum those entries together and
take a square root and that's my distance.