1
00:00:00,520 --> 00:00:03,530
So, given that these are the applications,
let me now tell you

2
00:00:03,530 --> 00:00:07,080
the first data dimensionality reduction
technique we will talk about.

3
00:00:07,080 --> 00:00:11,770
And this, this is called the SVD or
the singular value decomposition.

4
00:00:11,770 --> 00:00:15,470
And the way we think about this is that
the input to our method is a matrix.

5
00:00:15,470 --> 00:00:17,720
We will call this the input data matrix.

6
00:00:17,720 --> 00:00:25,280
That has it's, is of size m by n, which
means that it has m rows and n columns.

7
00:00:25,280 --> 00:00:27,090
So the way I can think of this is,
for example,

8
00:00:27,090 --> 00:00:32,620
if I think of this matrix A as a document
matrix, I can think of every row,

9
00:00:32,620 --> 00:00:36,970
representing a document and every column,
representing a different word.

10
00:00:36,970 --> 00:00:40,730
So now every document is represented
as a long, vector of zeros and

11
00:00:40,730 --> 00:00:45,660
ones, when zero means, that the word
does not appear in the document and

12
00:00:45,660 --> 00:00:48,430
one means, that the given
word appears in the document.

13
00:00:48,430 --> 00:00:52,820
I could also think, for example,
of this data matrix as a set of,

14
00:00:52,820 --> 00:00:56,030
as we will talk about later of movies and
users, right.

15
00:00:56,030 --> 00:00:58,540
So I can think of every row
as a different user and

16
00:00:58,540 --> 00:01:00,740
I can think of every column
as a different movie.

17
00:01:00,740 --> 00:01:03,543
And I can have, a value of one in a give,

18
00:01:03,543 --> 00:01:07,940
column row pair,
if a given user watched a given movie.

19
00:01:07,940 --> 00:01:09,610
So, this is my imput.

20
00:01:09,610 --> 00:01:12,740
Data matrix and what I want to do is,
I want to do the following, I want to

21
00:01:12,740 --> 00:01:18,140
take this matrix and I want to represent
it as a product of three matrices.

22
00:01:18,140 --> 00:01:20,570
I will call them U, sigma, and V.

23
00:01:20,570 --> 00:01:21,090
Okay?
And

24
00:01:21,090 --> 00:01:23,290
this is called the singular
value decomposition.

25
00:01:23,290 --> 00:01:25,000
So I take my regional matrix and

26
00:01:25,000 --> 00:01:28,620
I represent it, using a product
of three different matrices.

27
00:01:28,620 --> 00:01:31,340
And these three different matrices
have some constraints on them.

28
00:01:31,340 --> 00:01:33,260
So let, so let me explain those to you.

29
00:01:33,260 --> 00:01:40,330
So first, we say that our matrix A is a
product of U Sigma V, where the column U,

30
00:01:40,330 --> 00:01:45,760
the matrix U, is of size m times r,
so it has m rows and r columns.

31
00:01:45,760 --> 00:01:50,530
And this matrix, we will call it
stores left singular vectors so,

32
00:01:50,530 --> 00:01:54,730
its of size m times r right and and
we can think of this r as concepts or

33
00:01:54,730 --> 00:01:59,820
topics, I'll, I'll give examples later but
for now the important thing is that r,

34
00:01:59,820 --> 00:02:02,030
we can think of r as a very small number.

35
00:02:02,030 --> 00:02:02,820
Okay?

36
00:02:02,820 --> 00:02:06,410
Then, I have, so I have the matrix
of left singular vectors.

37
00:02:06,410 --> 00:02:07,780
Then I have a special matrix.

38
00:02:07,780 --> 00:02:08,640
I call it sigma.

39
00:02:08,640 --> 00:02:11,570
This is the vec matrix of singular values.

40
00:02:11,570 --> 00:02:15,670
And this is a diagonal matrix, basically
that ha, that is of size r times r.

41
00:02:15,670 --> 00:02:19,760
And basically it has it has its zeros
everywhere except on the diagonal.

42
00:02:19,760 --> 00:02:22,650
Okay so only,
basically this matrix is full of

43
00:02:22,650 --> 00:02:25,590
zeros only on the diagonal
that are non-zero elements.

44
00:02:25,590 --> 00:02:28,690
And these non-zero elements I call,
singular values.

45
00:02:28,690 --> 00:02:31,770
And what we'll also assume is that
these singular values are sorted in

46
00:02:31,770 --> 00:02:32,750
the decreasing order.

47
00:02:32,750 --> 00:02:35,410
So the,
the largest singular value comes first and

48
00:02:35,410 --> 00:02:37,660
then the second largest and so on.

49
00:02:37,660 --> 00:02:42,160
And then, the last matrix that
we have is the matrix V and

50
00:02:42,160 --> 00:02:47,130
this is the matrix that we will call, that
it stores the, the right singular vectors.

51
00:02:47,130 --> 00:02:51,940
So the size of this matrix will n times r,
where n is the number of columns in our

52
00:02:51,940 --> 00:02:57,044
original matrix A and again r in this case
is some small number we can think of this,

53
00:02:57,044 --> 00:03:01,130
r as basically being the,
the rank of the matrix A.

54
00:03:01,130 --> 00:03:06,342
So, what we have so far is, we, we have a
way, or atleast conceptually we have a way

55
00:03:06,342 --> 00:03:11,553
to take our matrix A and represent it,
as a product of three different matrices

56
00:03:11,553 --> 00:03:17,150
where the matrix sigma has this special
structure, that is dia, diagonal matrix.

57
00:03:17,150 --> 00:03:18,760
So, what do I mean this diagonal matrix?

58
00:03:18,760 --> 00:03:22,990
As I said it only has,
the non-zero values, on the diagonal and

59
00:03:22,990 --> 00:03:26,080
everything else is full of zeros.

60
00:03:26,080 --> 00:03:30,020
So I just gave you the,
a mathematical way of looking at how,

61
00:03:30,020 --> 00:03:32,930
matrix A can be represented as
a product of three matrices.

62
00:03:32,930 --> 00:03:34,765
But now let's look at
it kind of graphically.

63
00:03:34,765 --> 00:03:37,380
So, the way this looks,
works is the following,

64
00:03:37,380 --> 00:03:42,840
I'm giving the input data matrix A,
that has m rows and n columns.

65
00:03:42,840 --> 00:03:46,020
And I want to represent this matrix,
as a product of three matrices,

66
00:03:46,020 --> 00:03:48,590
U sigma and V transpose.

67
00:03:48,590 --> 00:03:52,040
Where I can think of
the matrix U as very thin.

68
00:03:52,040 --> 00:03:53,900
So, very few columns.

69
00:03:53,900 --> 00:03:56,320
But m rows matrix.

70
00:03:56,320 --> 00:03:58,480
So something that's, thin and long.

71
00:03:58,480 --> 00:04:00,670
Then, I have this special matrix sigma,

72
00:04:00,670 --> 00:04:05,690
that only has el, values on the diagonal
elements and the rest is zero.

73
00:04:05,690 --> 00:04:09,080
And then I have this
other matrix V transpose,

74
00:04:09,080 --> 00:04:14,970
that has a small number of rows r rows,
but it has n columns.

75
00:04:14,970 --> 00:04:18,920
So, basically, what we did in a sense,
is we will take this big matrix A and

76
00:04:18,920 --> 00:04:21,200
then represent it as a product of a theme.

77
00:04:21,200 --> 00:04:23,860
And not all matrix, are diagonal matrix.

78
00:04:23,860 --> 00:04:29,270
And a very long and
of low height matrix V.

79
00:04:29,270 --> 00:04:33,160
So, this is one way how to look at this in
terms of the product of three matrices,

80
00:04:33,160 --> 00:04:35,290
here is again a different
way of looking at it.

81
00:04:35,290 --> 00:04:39,870
So, now I can think of this as that
matrix A is a sum of different matrices,

82
00:04:39,870 --> 00:04:42,230
where basically I took the same
thing as I had before, but

83
00:04:42,230 --> 00:04:46,110
now I'm representing it as other
products of different vectors, right?

84
00:04:46,110 --> 00:04:49,160
So I'm, in some sense taking
the left singular vector,

85
00:04:49,160 --> 00:04:51,770
multiplying it with the singular value,
value and

86
00:04:51,770 --> 00:04:57,100
then the right singular vector and then I
add to it the second left singular vector,

87
00:04:57,100 --> 00:05:01,460
the singular value and
the second right singular vector.

88
00:05:01,460 --> 00:05:03,950
Right, and the colors between the two
slides correspond to each other so

89
00:05:03,950 --> 00:05:09,020
all, I basically did in this
representation is I, took the red rows and

90
00:05:09,020 --> 00:05:13,370
columns and put them, to the first product
and then I took the green, but O and

91
00:05:13,370 --> 00:05:17,430
column and the sin, singular value and
I put it to the second outer product.

92
00:05:17,430 --> 00:05:21,110
So, so, this is what we're
trying to do graphically.

93
00:05:21,110 --> 00:05:27,420
And that is the theorem the SVD theorem
that says that it is always possible,

94
00:05:27,420 --> 00:05:32,880
to decompose a real matrix A into this
product of matrix, of matrices U,

95
00:05:32,880 --> 00:05:34,580
sigma, and V transposed.

96
00:05:34,580 --> 00:05:37,820
And when I say a real matrix I mean,
a matrix where,

97
00:05:37,820 --> 00:05:40,100
where its values are, are real numbers.

98
00:05:40,100 --> 00:05:42,790
Right.
So not complex numbers, but real numbers.

99
00:05:42,790 --> 00:05:44,950
And what,
what this theorem says is the following,

100
00:05:44,950 --> 00:05:47,890
first it says,
that this is always possible.

101
00:05:47,890 --> 00:05:52,950
And by this we mean that it, it, for
any possible matrix A we can find this

102
00:05:52,950 --> 00:05:56,080
decomposition, more over this
decomposition is unique.

103
00:05:56,080 --> 00:06:00,350
Which means there is only one,
set of values or

104
00:06:00,350 --> 00:06:06,270
one matrix A that gets decomposed
into exactly one matrix U,

105
00:06:06,270 --> 00:06:11,110
a unique matrix sigma, a unique matrix V,
so that's the first thing.

106
00:06:11,110 --> 00:06:16,470
The second thing is that matrices U and V
are what is called column orthogonal which

107
00:06:16,470 --> 00:06:21,250
means the columns of U,
and we have length one.

108
00:06:21,250 --> 00:06:23,920
So the sum of the squared values of the,

109
00:06:23,920 --> 00:06:27,200
in each column of these
two matrixes equals one.

110
00:06:27,200 --> 00:06:31,610
And then the other one is that these
columns are orthogonal, which means that

111
00:06:31,610 --> 00:06:36,310
if I take two columns of U, or if I take
two columns of V and I multiplied them

112
00:06:36,310 --> 00:06:40,110
with each other, if I [INAUDIBLE]
with each other, I get a zero, right?

113
00:06:40,110 --> 00:06:42,675
So, in,
what this means is that both U and V,

114
00:06:42,675 --> 00:06:46,119
for, in some sense, form a basis,
which means that I have,

115
00:06:46,119 --> 00:06:51,520
each each column has [INAUDIBLE] one, this
is called, this is part the, the normal.

116
00:06:51,520 --> 00:06:55,470
And orthogonal,
orthogonality is that the unit product is

117
00:06:55,470 --> 00:06:58,770
zero between different columns of a,
of a given matrix.

118
00:06:58,770 --> 00:07:01,730
So that's the first important thing
about the structure of columns U and

119
00:07:01,730 --> 00:07:04,720
V and the, important thing
about the structure of the,

120
00:07:04,720 --> 00:07:09,170
of the, of the matrix sigma is that it's
diagonal, which means that the entries,

121
00:07:09,170 --> 00:07:14,560
of matrix sigma, which we call
singular values, are all positive and

122
00:07:14,560 --> 00:07:17,800
they are sorted in the decreasing order,
which means that sigma one, is

123
00:07:17,800 --> 00:07:22,370
greater than equal to sigma two, to sigma
three and they are all greater than zero.

124
00:07:22,370 --> 00:07:26,030
So, what do we know is that,
for any given matrix A,

125
00:07:26,030 --> 00:07:29,140
there is a unique set of matrices U,
V and sigma that, are in,

126
00:07:29,140 --> 00:07:32,960
that we are able to compute in
order to decompose A, that U and

127
00:07:32,960 --> 00:07:37,750
V that are in the columns of it are
orthonormal, which means, unit length and

128
00:07:37,750 --> 00:07:42,530
orthogonal and matrix sigma,
is diagonal matrix with

129
00:07:42,530 --> 00:07:45,750
non non-zero elements when it's always
giving the singular values on it.

130
00:07:47,030 --> 00:07:50,480
Let me give you now an example of
how we can think about this, so

131
00:07:50,480 --> 00:07:53,470
let's think about the users
to movies matrix right so,

132
00:07:53,470 --> 00:07:58,430
let's think of our we have we
are a Netflix or user review website or

133
00:07:58,430 --> 00:08:01,830
we can think our set,
of ourselves as a movie selling business.

134
00:08:01,830 --> 00:08:06,340
And what we do is the following, we have a
set of people and we have a set of movies.

135
00:08:06,340 --> 00:08:10,460
Right and every, every person goes and
watches some set of movies and

136
00:08:10,460 --> 00:08:12,440
they tell us whether they
like that movie or not.

137
00:08:12,440 --> 00:08:15,870
So well, a value of one means that they
didn't like the movie that much and

138
00:08:15,870 --> 00:08:18,040
five means, they really enjoyed the movie.

139
00:08:18,040 --> 00:08:18,690
Okay?
So

140
00:08:18,690 --> 00:08:21,470
every column in this matrix
corresponds to a different movie.

141
00:08:21,470 --> 00:08:23,820
And every row corresponds
to a different user.

142
00:08:23,820 --> 00:08:24,800
Right?
So what this means is for

143
00:08:24,800 --> 00:08:27,130
example there is this particular user.

144
00:08:27,130 --> 00:08:28,520
Let's call it the user number three.

145
00:08:29,600 --> 00:08:33,800
That watched only the movies
matrix alien and sere, serenity.

146
00:08:33,800 --> 00:08:35,130
They really liked those movies.

147
00:08:35,130 --> 00:08:38,030
While they didn't like the Casablanca and
Amelie for example.

148
00:08:38,030 --> 00:08:38,560
Right?

149
00:08:38,560 --> 00:08:40,100
And now with given this kind of matrix.

150
00:08:40,100 --> 00:08:41,489
This is our matrix A.

151
00:08:41,489 --> 00:08:45,432
Our goal is to decompose this matrix,
using the singular value decomposition.

152
00:08:45,432 --> 00:08:50,170
So we want to decompose it in terms of
this long and, and narrow matrix U.

153
00:08:50,170 --> 00:08:54,300
The diagonal matrix sigma and
the, matrix width.

154
00:08:54,300 --> 00:08:59,500
So, if we, if we do this, the way we can
think of, of this different elements

155
00:08:59,500 --> 00:09:03,750
of this matrix, is that basically in
some sense we want to discover concepts.

156
00:09:03,750 --> 00:09:07,440
Right in some sense we would like to
discover that in, the matrix that I

157
00:09:07,440 --> 00:09:11,030
gave you that basically we have this
set of science fiction movies and

158
00:09:11,030 --> 00:09:15,350
we have also a set of users who like
science fiction movies and I, I have a,

159
00:09:15,350 --> 00:09:17,490
we have a set of other users.

160
00:09:17,490 --> 00:09:21,520
Right the, the bottom three users
that all like romance movies.

161
00:09:21,520 --> 00:09:25,360
And they don't really like
the Sci-Fi movies, so

162
00:09:25,360 --> 00:09:30,720
in some sense, movies break into group
into two groups one group is about Sci-Fi,

163
00:09:30,720 --> 00:09:34,440
the other one is about romance and
also users break into the two

164
00:09:34,440 --> 00:09:39,630
groups into the kind of Sci-Fi lovers and
the romance movie lovers.

165
00:09:39,630 --> 00:09:43,810
So now, basically, this is what
SVD will allow us to figure out.

166
00:09:43,810 --> 00:09:47,950
So, if you take this matrix,
let's say type it into Matlab and

167
00:09:47,950 --> 00:09:50,750
do the singular value decomposition,
this is what we obtain.

168
00:09:50,750 --> 00:09:52,600
So we obtain our matrix U.

169
00:09:52,600 --> 00:09:54,430
We obtain our matrix Sigma.

170
00:09:54,430 --> 00:09:57,670
And we obtain our matrix V transpose.

171
00:09:57,670 --> 00:10:02,180
And here is how,
how we can think about the,

172
00:10:02,180 --> 00:10:05,370
the what we learned from
the singular value decomposition.

173
00:10:05,370 --> 00:10:08,055
So the first thing is, the columns of U.

174
00:10:08,055 --> 00:10:10,360
We can think of this as concepts right so
for

175
00:10:10,360 --> 00:10:15,100
example the first column of U, corresponds
to the, to the Sci-Fi concept and

176
00:10:15,100 --> 00:10:18,790
the second column of U,
corresponds to the romance concept.

177
00:10:18,790 --> 00:10:21,680
So, what is,
what we learn from here is that for

178
00:10:21,680 --> 00:10:26,430
example the first five users readily
strongly belong to the Sci-Fi concept and

179
00:10:26,430 --> 00:10:31,740
the second five users second three users,
correspond heavily to the romance concept.

180
00:10:32,840 --> 00:10:36,930
In terms of,
this we can think of in some sense that

181
00:10:38,200 --> 00:10:42,470
of matrix U as a user to concept
matrix right so every entry here,

182
00:10:42,470 --> 00:10:47,200
tells us how much that a given user
correspond to a given to a given concept?

183
00:10:47,200 --> 00:10:50,260
So the first user corresponds heavily,
to the first concept,

184
00:10:50,260 --> 00:10:54,020
to the SciFi concept while for
example the fifth user

185
00:10:54,020 --> 00:10:59,350
corresponds heavily to the second
concept to the romance concept.

186
00:10:59,350 --> 00:11:01,425
So this in some sense matrix.

187
00:11:01,425 --> 00:11:05,590
We can think of it as a,
user to concept similarity matrix.

188
00:11:05,590 --> 00:11:09,330
Then we have the singular values Sigma.

189
00:11:10,540 --> 00:11:15,040
And here, what we think of this is
that every, every value is non-zero.

190
00:11:15,040 --> 00:11:17,540
And it's positive, right, non-negative.

191
00:11:17,540 --> 00:11:20,420
So we can think of this as,
the strength of every concept.

192
00:11:20,420 --> 00:11:26,480
So in our case, we would see that,
the strength of our Sci Fi-concept is

193
00:11:26,480 --> 00:11:30,230
higher than the strength of our,
romance concept, all right?

194
00:11:30,230 --> 00:11:34,350
And then we need to also explain,
the matrix V and the way we

195
00:11:34,350 --> 00:11:38,270
can think of matrix V is we can think of
it as a movie to concept matrix, right?

196
00:11:38,270 --> 00:11:43,362
In a sense that it tells us that, that the
first three movies heavily corresponds to

197
00:11:43,362 --> 00:11:48,601
the, belongs to the first concept, while
the last two movies heavily corresponds to

198
00:11:48,601 --> 00:11:53,505
the, to the se, to the second concept,
which we named, the romance concept.

199
00:11:53,505 --> 00:12:00,066
Of cour, of course, in both cases, we also
have this third concept that, that in some

200
00:12:00,066 --> 00:12:06,917
sense, has very low strength, so we can
kind of ignore it and it, it just okay?

201
00:12:06,917 --> 00:12:09,883
So this is one way how we,
basically we can already go and

202
00:12:09,883 --> 00:12:12,360
learn something from, from the SVD, right?

203
00:12:12,360 --> 00:12:15,350
We took some matrix of data points.

204
00:12:15,350 --> 00:12:16,880
And we performed the SVD.

205
00:12:16,880 --> 00:12:20,410
And very quickly we saw that basically
we have two, two concepts of the,

206
00:12:20,410 --> 00:12:23,140
of the main, of lots of strength.

207
00:12:23,140 --> 00:12:27,860
The first one we, we, we were able to
interpret as the concept of Sci-Fi movies.

208
00:12:27,860 --> 00:12:30,510
The second one is the concept
of romance movies and then for

209
00:12:30,510 --> 00:12:33,890
every user, we know how much they
belong to the, to each concept so for

210
00:12:33,890 --> 00:12:36,045
example the first user
heavily belongs to the,

211
00:12:36,045 --> 00:12:41,230
Sci-Fi concept and relatively very little
belongs to the, romance concept and

212
00:12:41,230 --> 00:12:45,660
then also for every movie, we know what
concept its belongs, it belongs to.

213
00:12:45,660 --> 00:12:49,220
So for example the, the first movie,
heavily belongs to the,

214
00:12:49,220 --> 00:12:52,840
to the first concept and
much less to the second concept.

215
00:12:52,840 --> 00:12:55,310
It also belongs quite heavily
to the third concept, but

216
00:12:55,310 --> 00:13:00,580
as we see from our matrix sigma, the third
concept has a very low overall strength,

217
00:13:00,580 --> 00:13:03,510
so it's not so
important in explaining the data.

218
00:13:03,510 --> 00:13:06,510
So, in, what is the first
interpretation of our SVD?

219
00:13:06,510 --> 00:13:10,920
Basically, the first interpretation is
that we can take this, let's say users,

220
00:13:10,920 --> 00:13:15,665
users to movie matrix and we can interpret
our, our data in terms of movies,users,

221
00:13:15,665 --> 00:13:18,860
and the concepts or
different genres, or topics right?

222
00:13:18,860 --> 00:13:21,910
So, we can think of U as user tool.

223
00:13:21,910 --> 00:13:26,840
Concept similarity Matrix,
V as a movie to concept similarity matrix.

224
00:13:26,840 --> 00:13:32,120
And then matrix sigma, or its diagonal
matri entries, the singular values,

225
00:13:32,120 --> 00:13:35,590
as the,
as modeling the strength of each concept.