1 00:00:00,240 --> 00:00:02,170 So, so far we discussed SVD and 2 00:00:02,170 --> 00:00:05,630 we will conclude our discussion of singular value decomposition by looking at 3 00:00:05,630 --> 00:00:09,960 an example of its usage, and then talk a bit more broadly about the method. 4 00:00:09,960 --> 00:00:11,480 So, here is the idea. 5 00:00:11,480 --> 00:00:13,540 Let's think about the following problem. 6 00:00:13,540 --> 00:00:18,400 Imagine we want to identify all the users who like our Matrix movie. 7 00:00:18,400 --> 00:00:25,140 So, the idea is we have this matri matrix now of values of users to movies. 8 00:00:25,140 --> 00:00:29,770 And now, we would like to identify all the users who liked the movie Matrix. 9 00:00:29,770 --> 00:00:34,740 And what we would like to learn from this task in a sense is that given that we 10 00:00:34,740 --> 00:00:39,700 saw that there are people who like SciFi movies, so maybe we would like to kind of 11 00:00:39,700 --> 00:00:44,880 find a person who didn't even see the movie Matrix yet, but 12 00:00:44,880 --> 00:00:49,970 we may want be able to say yes, but given that they like these other SciFi movies. 13 00:00:49,970 --> 00:00:53,000 The mal, they may also like the movie Matrix. 14 00:00:53,000 --> 00:00:56,520 And the question is, how can we do this using SVD? 15 00:00:56,520 --> 00:00:59,250 The answer to this question is that basically we want to map, 16 00:00:59,250 --> 00:01:02,350 map our query point into the concept space. 17 00:01:02,350 --> 00:01:07,680 We are given our data users to movies matrix A, right? 18 00:01:07,680 --> 00:01:11,260 We did, we do the SVD of it, so here's the SVD. 19 00:01:11,260 --> 00:01:14,390 And what we want to do now, is we are given our query point. 20 00:01:14,390 --> 00:01:18,440 Our query point q is simply we say, 21 00:01:18,440 --> 00:01:21,030 let's find all the users that like the movie Matrix. 22 00:01:21,030 --> 00:01:21,570 So, let's create, 23 00:01:21,570 --> 00:01:25,930 in some sense, this query, this query user, this artificial user that likes the. 24 00:01:27,310 --> 00:01:32,260 A movie matrix, and the idea is, we want to find other users who are close to this 25 00:01:32,260 --> 00:01:34,690 given user in the, in the concept space. 26 00:01:34,690 --> 00:01:38,846 So, what we'll do we have, we have our movies space, 27 00:01:38,846 --> 00:01:42,920 we have our data point q here, our query point. 28 00:01:42,920 --> 00:01:45,660 And we want to project it into our concept space. 29 00:01:45,660 --> 00:01:48,420 The way, the way we do this is that basically we simply do 30 00:01:48,420 --> 00:01:53,510 the inner product of our query point with each concept vector in vector v. 31 00:01:53,510 --> 00:01:58,330 Because vector V is movies to concepts vector right, so if we go if we 32 00:01:58,330 --> 00:02:04,250 go do this, y is taking the inner product a good idea, because of example q times 33 00:02:04,250 --> 00:02:09,700 the first singular vector will simply take, take our position of the point q. 34 00:02:09,700 --> 00:02:11,180 And tell and will tell it, 35 00:02:11,180 --> 00:02:16,280 tell us its location along the, the, the axis of the first singular vector. 36 00:02:16,280 --> 00:02:21,260 The second singular vector is orthogonal to the first one, so here it is the V2. 37 00:02:21,260 --> 00:02:23,820 And when I multiply q times V2. 38 00:02:23,820 --> 00:02:29,060 We will basically now get the projection of the data point and 39 00:02:29,060 --> 00:02:32,210 its position on the second singular vector. 40 00:02:32,210 --> 00:02:33,570 So, that's basically what will happen. 41 00:02:33,570 --> 00:02:36,830 So, if we, if you do our, our projection. 42 00:02:36,830 --> 00:02:42,400 So, we take our vector q multiplied with matrixVv we do the thing, 43 00:02:42,400 --> 00:02:44,160 and here is what we obtained. 44 00:02:44,160 --> 00:02:46,990 So, we obtained that this, for example, this particular user, 45 00:02:46,990 --> 00:02:51,590 now we are in this concept space, in this two, two-dimensional concept space, 46 00:02:51,590 --> 00:02:57,949 where the first column of V is SciFi, and the second column of V was romance. 47 00:02:59,290 --> 00:03:04,330 And once we do the inner product, we basically see that a lot, 48 00:03:04,330 --> 00:03:10,450 that, our query point in some sense corresponds heavily to the SciFi concept, 49 00:03:10,450 --> 00:03:14,940 and very low, has a very low coordinate value along the romance concept. 50 00:03:14,940 --> 00:03:19,540 So, this is now how we mo, do the query and kind of map it into the concept space. 51 00:03:19,540 --> 00:03:23,208 So, now for example, imagine I have some user, some user d. 52 00:03:23,208 --> 00:03:26,010 That we don't know what they think or 53 00:03:26,010 --> 00:03:28,890 they haven't told us anything about what they think about the movie matrix. 54 00:03:28,890 --> 00:03:32,860 But they didn't tell us they really like movies, Alien they haven't said anything. 55 00:03:32,860 --> 00:03:37,700 So, if we take this user and again multiply them by our vector V and 56 00:03:37,700 --> 00:03:40,410 basically move them to the concept space. 57 00:03:40,410 --> 00:03:44,270 Here are the coordinates of the position of that user in the concept space. 58 00:03:44,270 --> 00:03:47,090 So, what is, what is a good thing that happens? 59 00:03:47,090 --> 00:03:53,170 So, for example, if I now compare the positions of the original user and 60 00:03:53,170 --> 00:03:56,621 the query in the original space, and, the, the, 61 00:03:56,621 --> 00:03:59,810 the locations in the concert space, I find the following. 62 00:03:59,810 --> 00:04:05,930 So, the similarity between q and d in our original space is zero, 63 00:04:05,930 --> 00:04:11,068 right, in the sense that for Alien and Serenity, our query doesn't. 64 00:04:11,068 --> 00:04:11,850 doesn't want them. 65 00:04:11,850 --> 00:04:14,850 For our movie matrix, the user didn't tell us anything, so 66 00:04:14,850 --> 00:04:17,070 there is no similarity between these two vectors. 67 00:04:17,070 --> 00:04:20,580 But if I go back to my concept space, 68 00:04:20,580 --> 00:04:25,920 here I see that both of these data points, or both of these users, q and d, 69 00:04:25,920 --> 00:04:30,810 they actually share high values on the SciFi concept. 70 00:04:30,810 --> 00:04:33,530 And they share low values on the romance concept. 71 00:04:33,530 --> 00:04:36,960 So, in some sense, I may be able to identify or I may be able to 72 00:04:36,960 --> 00:04:42,100 put together that q and d, are actually close together in our space even though 73 00:04:42,100 --> 00:04:47,130 in the raw data representation they don't share any coordinates together. 74 00:04:47,130 --> 00:04:50,860 So, in some sense even though q and d have zero ratings in common, we are able to 75 00:04:50,860 --> 00:04:55,650 identify that they are similar, because SVD was a SVD was able to identify that 76 00:04:55,650 --> 00:05:01,910 kind of people who liked Alien and Serenity also liked the Matrix movie. 77 00:05:01,910 --> 00:05:06,800 So, this basically is how we can make use of Singular Value Decomposition. 78 00:05:06,800 --> 00:05:08,140 What I want to do now, 79 00:05:08,140 --> 00:05:12,960 now very briefly is to relate Singular Value Decomposition to another. 80 00:05:12,960 --> 00:05:18,490 Type of, decomposition of a matrix, that is called Eigen value decomposition. 81 00:05:18,490 --> 00:05:21,930 so, first, I will you what is the relationship between singular value 82 00:05:21,930 --> 00:05:25,800 decomposition and Eigen-decomposition, and then we will con, conclude. 83 00:05:25,800 --> 00:05:30,340 So, what we know so far is that SVD is, given a matrix, 84 00:05:30,340 --> 00:05:34,500 we represent it as a product of three matrices, using my retranspose. 85 00:05:34,500 --> 00:05:36,460 What is Eigen value decomposition? 86 00:05:36,460 --> 00:05:39,440 Eigen value decomposition is kind of, more constrained. 87 00:05:39,440 --> 00:05:45,680 It says, given sub matrix A, I want to represent it as a matrix x times the ma, 88 00:05:45,680 --> 00:05:49,060 ma, matrix capital lambda times x transposed again. 89 00:05:49,060 --> 00:05:55,158 So, here I only have kind of product of two matrixes, if you like, lambda and x. 90 00:05:55,158 --> 00:05:57,470 So, for Eigen-decomposition to, 91 00:05:57,470 --> 00:06:02,380 to even exist what we have to do is first A has to be symmetric which means that 92 00:06:02,380 --> 00:06:07,210 the values above the diagonal have to be the same as the values below the diagonal. 93 00:06:07,210 --> 00:06:10,608 While, for example, in SVD we did not have this constraint. 94 00:06:10,608 --> 00:06:11,470 And then ce, 95 00:06:11,470 --> 00:06:16,600 both in svd and Eigen value decomposition, all the matrices are columnar phenomena, 96 00:06:16,600 --> 00:06:21,220 which means the columns are orthonormal to each other and have unit length. 97 00:06:21,220 --> 00:06:27,800 And in both cases, you sigma and lambda are diagonal matrices. 98 00:06:27,800 --> 00:06:30,850 So, now the question is, what is the corres, corresponding, 99 00:06:30,850 --> 00:06:35,190 correspondence between singular value decomposition and Eigen-decomposition? 100 00:06:35,190 --> 00:06:37,470 So, let's consider this simple case. 101 00:06:37,470 --> 00:06:41,020 Let's consider what is A times A transposed? 102 00:06:41,020 --> 00:06:43,250 So, we know that we can take the matrix A and 103 00:06:43,250 --> 00:06:45,480 perform singular value decomposition of it. 104 00:06:45,480 --> 00:06:46,310 So, let's do that. 105 00:06:46,310 --> 00:06:51,032 So, what is A times A transposed is the singular val, value decomposition of 106 00:06:51,032 --> 00:06:54,607 A times the singular value decomposition of A transpose. 107 00:06:54,607 --> 00:06:58,447 Which is the same as singular value decomposition of A and 108 00:06:58,447 --> 00:07:01,249 then trans, trans, transposing that. 109 00:07:01,249 --> 00:07:04,729 So, now let's start thinking what do we what do we get next? 110 00:07:05,732 --> 00:07:08,180 All right, what we get next is that because the, 111 00:07:08,180 --> 00:07:12,940 the multiplication is cumulative we can kind of reword reword the terms. 112 00:07:12,940 --> 00:07:13,530 Right? So, for 113 00:07:13,530 --> 00:07:15,790 example we can take the original expression and 114 00:07:15,790 --> 00:07:20,250 now just reword the terms of, or the order of multiplication. 115 00:07:20,250 --> 00:07:26,050 What we notice now is that we get, we get a multiplication of V transposed times V. 116 00:07:26,050 --> 00:07:30,760 And given that our matrices are orthonormal, this means that V, 117 00:07:30,760 --> 00:07:35,770 a matrix multiplied with itself, gives us an identity matrix. 118 00:07:35,770 --> 00:07:40,530 An identity matrix is simply a matrix that has zeros, off the diagonal and 119 00:07:40,530 --> 00:07:43,460 it has values of 1 on the diagonal. 120 00:07:43,460 --> 00:07:46,810 So, what this means is that it's basically an identity matrix, right. 121 00:07:46,810 --> 00:07:49,200 So, what this means is that we can take. 122 00:07:49,200 --> 00:07:54,700 AA transpose and transform is down if you take each SVD and see what happens, 123 00:07:54,700 --> 00:08:03,780 it turns out to become U times sigma, sigma transpose U transpose, okay? 124 00:08:03,780 --> 00:08:08,120 similarly, the same thing happens or a similar thing happens if I ask what is 125 00:08:08,120 --> 00:08:12,400 the singular value decomposition of A of matrix a times a transpose. 126 00:08:12,400 --> 00:08:16,080 I do, I do the same, the same trick as before, and here now, 127 00:08:16,080 --> 00:08:22,492 I obtain that this equals V times sigma times sigma transpose times V transpose. 128 00:08:22,492 --> 00:08:27,160 One thing that I have to remember is that sigma is a diagonal matrix. 129 00:08:27,160 --> 00:08:31,660 So, in some sense sigma times sigma transposed is nothing else than another 130 00:08:31,660 --> 00:08:36,560 diagonal matrix that has the squares of the values on the diagonal, right? 131 00:08:36,560 --> 00:08:37,740 So, what do we learn from this? 132 00:08:37,740 --> 00:08:38,780 Is the following. 133 00:08:38,780 --> 00:08:44,680 So, if I take the A times A transposed, which is a symmetric matrix. 134 00:08:44,680 --> 00:08:47,070 I do a singular value decomposition of it. 135 00:08:47,070 --> 00:08:51,830 What I end up with, is an expression like, like this which basically means that, 136 00:08:51,830 --> 00:08:57,530 in this case, u is a set of I can think of u as a set of item vectors. 137 00:08:57,530 --> 00:09:00,070 Right? So, as a part of the item decomposition. 138 00:09:00,070 --> 00:09:05,090 And I can think of Sigma times Sigma transposed as a set of item values. 139 00:09:05,090 --> 00:09:06,460 So, what this basically means is that 140 00:09:07,810 --> 00:09:11,280 if I have a matrix I can do singular value decomposition of it and 141 00:09:11,280 --> 00:09:15,100 from singular value decomposition of it I can do the Eigen value decomposition. 142 00:09:15,100 --> 00:09:19,000 Where the relationship between Eigen values and the singular values is that, 143 00:09:19,000 --> 00:09:25,260 singular values squared are the Eigen values of the corresponding matrix. 144 00:09:25,260 --> 00:09:29,294 So, that's the co, that's the connection between the Eigen value and 145 00:09:29,294 --> 00:09:31,920 the singular value decomposition. 146 00:09:31,920 --> 00:09:36,770 So, to to finish talking about singular value decomposition, here is, 147 00:09:36,770 --> 00:09:38,220 here is kind of the overview. 148 00:09:38,220 --> 00:09:42,480 So, what is good about singular value decomposition is that it gives, it gives 149 00:09:42,480 --> 00:09:46,740 us the optimal low rank approximation right, in terms of the Frobenius norm. 150 00:09:46,740 --> 00:09:49,690 So, it means that if I allow myself to take my data and 151 00:09:49,690 --> 00:09:52,740 represent it using a small number of dimensions, 152 00:09:52,740 --> 00:09:56,420 then SVD will be able to identify the best possible number of dimensions. 153 00:09:56,420 --> 00:09:59,590 That basically give us the best possible prejection of the data 154 00:09:59,590 --> 00:10:04,770 into some small dimensional space in such a way that if we go from this small 155 00:10:04,770 --> 00:10:08,760 dimensional space back to the original high dimensional space, the sum of 156 00:10:08,760 --> 00:10:13,100 the squares of the reconstructions error, errors, will be as small as possible. 157 00:10:13,100 --> 00:10:13,680 So, that's great. 158 00:10:14,900 --> 00:10:16,850 What is problematic with SVD are two things. 159 00:10:16,850 --> 00:10:20,100 The first one is the interpretation problem. 160 00:10:20,100 --> 00:10:24,620 What this means is that the singular vectors specifies some, 161 00:10:24,620 --> 00:10:27,840 a linear combination of input columns or rows. 162 00:10:27,840 --> 00:10:31,250 Which means that many times singular vectors are very hard to interpret. 163 00:10:31,250 --> 00:10:36,420 When I say singular vectors are hard to interpret in our cases of movies to 164 00:10:36,420 --> 00:10:41,140 users matrix, I was able to interpret the first singular vector to correspond to 165 00:10:41,140 --> 00:10:45,720 the SciFi movies, and the second one to the Romans movies. 166 00:10:45,720 --> 00:10:50,960 Many times, that is hard to do, and the second big drawback 167 00:10:50,960 --> 00:10:55,390 of singular valid decomposition is what is called lack of sparsity. 168 00:10:55,390 --> 00:10:59,610 What this means is that, the input matrix A, is often very sparse which means it, 169 00:10:59,610 --> 00:11:04,020 it is full of zeros, and only has a few non zero elements in it. 170 00:11:04,020 --> 00:11:06,740 But when you, when we do singular value, the composition,. 171 00:11:06,740 --> 00:11:10,650 The matrices U and V transpose, they will be dense. 172 00:11:10,650 --> 00:11:12,270 What I mean by that is all, 173 00:11:12,270 --> 00:11:15,860 basically all the values in this matrix will be non zero. 174 00:11:15,860 --> 00:11:21,220 So, many times, even though U and V have a very small number 175 00:11:21,220 --> 00:11:26,307 of columns or rows, so in some sense in, in terms of the row column or 176 00:11:26,307 --> 00:11:30,860 row, row size, they are much smaller than the matrix say in terms of the data size, 177 00:11:30,860 --> 00:11:35,000 maybe bigger because a has very few non zero elements. 178 00:11:35,000 --> 00:11:40,360 Or values and then matrices u and v have a large number of non zero elements so 179 00:11:40,360 --> 00:11:44,290 what we will do next is we will look at the method that is much easier to 180 00:11:44,290 --> 00:11:48,010 compute much faster to compute then the singular value decomposition. 181 00:11:48,010 --> 00:11:51,470 And also main maintains the sparsity of rows and 182 00:11:51,470 --> 00:11:55,150 columns of U and V and this is what we are going to look at next.