1 00:00:00,250 --> 00:00:02,200 So we are starting with a new topic. 2 00:00:02,200 --> 00:00:06,370 The topic we will discuss today is, is called dimensionality reduction. 3 00:00:06,370 --> 00:00:09,860 And the idea here is basically that we will learn about techniques that will 4 00:00:09,860 --> 00:00:13,370 later become very handy when we will talk about recommender systems, and 5 00:00:13,370 --> 00:00:16,290 in particular latent factor recommender systems. 6 00:00:16,290 --> 00:00:19,490 So let me give you an idea of what the problem of dimensionality reduction 7 00:00:19,490 --> 00:00:20,540 is all about. 8 00:00:20,540 --> 00:00:24,050 So basically our assumption is that we have a set of data points. 9 00:00:24,050 --> 00:00:27,780 Think of them as points in a plane or points in a three-dimensional space. 10 00:00:27,780 --> 00:00:31,220 And the idea is that these points are not just randomly scattered through the space, 11 00:00:31,220 --> 00:00:33,920 but they, they li, lie in a subspace of it. 12 00:00:33,920 --> 00:00:36,760 So for example, here, here I have two cases of this. 13 00:00:36,760 --> 00:00:40,660 You could imagine that you have a set of data in a two-dimensional plane, but 14 00:00:40,660 --> 00:00:43,830 the data is not only kind of randomly scattered through this plane, 15 00:00:43,830 --> 00:00:48,080 but it it it is only scattered across a small subspace of it. 16 00:00:48,080 --> 00:00:51,730 So for example in the first case, we have our we have the data points that are that 17 00:00:51,730 --> 00:00:56,470 are embedded on this particular line so maybe a more better representation of 18 00:00:56,470 --> 00:01:00,500 this data is not in this two-dimensional space but it's basically just 19 00:01:00,500 --> 00:01:05,360 where where in the length of the line is, is a given data point. 20 00:01:05,360 --> 00:01:09,580 Or, for example, in the second case, we have we, we are drawing a case where we 21 00:01:09,580 --> 00:01:14,050 have points embedded in a three-dimensional space, but again, these 22 00:01:14,050 --> 00:01:18,130 point, points are not randomly scattered through space, but basically, they are, 23 00:01:18,130 --> 00:01:22,690 they are, they all lie on this single plane that is embedded in this space. 24 00:01:22,690 --> 00:01:27,350 So basically the idea for axes can we go and discover such data in presentation. 25 00:01:27,350 --> 00:01:31,420 So if I give you another clear set of data can we go identify what are the main 26 00:01:31,420 --> 00:01:34,900 axes along original data is represented or embedded. 27 00:01:34,900 --> 00:01:37,770 So in particular, in this second case, 28 00:01:37,770 --> 00:01:42,230 we have these 2 are an axis where all the data lies. 29 00:01:42,230 --> 00:01:45,530 So our goal in some sense will be that we want to find a sub space 30 00:01:45,530 --> 00:01:50,690 that effectively represents all the data in that we are given. 31 00:01:50,690 --> 00:01:53,320 So, let me just give you a complete example, right. 32 00:01:53,320 --> 00:01:56,420 So, our goal, in a sense, would be that we want to compress or 33 00:01:56,420 --> 00:01:59,980 reduce the dimensionality or the size of the data representation. 34 00:01:59,980 --> 00:02:05,120 So the way we can think of this is that we are given a big table with a, large number 35 00:02:05,120 --> 00:02:09,190 of rows, let's say millions of rows, and also a large number of, of columns. 36 00:02:09,190 --> 00:02:10,920 And what we can think of, of this, 37 00:02:10,920 --> 00:02:14,830 of this kind of table is that every row represents a different data point. 38 00:02:14,830 --> 00:02:18,790 And every column represents a different coordinate or a dif, different dimension. 39 00:02:18,790 --> 00:02:21,650 And our goal is that we take this set of data and 40 00:02:21,650 --> 00:02:27,980 identify kind of more compact or fewer dimensional representations. 41 00:02:27,980 --> 00:02:30,050 So in a sense, we would like to keep all the rows. 42 00:02:30,050 --> 00:02:32,590 But we would like to shrink the number of columns. 43 00:02:32,590 --> 00:02:36,490 While, while stoll, still preserve the richness of a da, of the data set. 44 00:02:36,490 --> 00:02:40,200 So, for example, let's look at the the table that I have here. 45 00:02:40,200 --> 00:02:44,370 I have, for example, a table where every row is a different customer and 46 00:02:44,370 --> 00:02:50,550 every column is a different time of the day, where every entry stores how many. 47 00:02:50,550 --> 00:02:52,900 But how many of particular transactions or 48 00:02:52,900 --> 00:02:56,840 particular products need a particular customer to buy. 49 00:02:56,840 --> 00:02:59,870 And for example what we see in this particular case is that even though we 50 00:02:59,870 --> 00:03:03,270 have five different days so five different columns, 51 00:03:03,270 --> 00:03:07,270 our data is not really in some sense five dimensional but it's only two dimensional. 52 00:03:07,270 --> 00:03:12,230 What do I mean by this is that for example all the first four rows and 53 00:03:12,230 --> 00:03:17,290 the first three columns, they're basically all multiplications of one another, right? 54 00:03:17,290 --> 00:03:21,100 So since I have a set of customers that all buy products on 55 00:03:21,100 --> 00:03:25,040 the first in the first three columns and they do nothing on the last. 56 00:03:25,040 --> 00:03:27,900 Two and then I have another set of let's say, customers. 57 00:03:27,900 --> 00:03:30,540 That they will make transactions over the weekends. 58 00:03:30,540 --> 00:03:32,660 And they don't do anything over the week. 59 00:03:32,660 --> 00:03:33,930 Right? So, in some sense, 60 00:03:33,930 --> 00:03:38,640 rather than representing every customer now with the with a set of five values. 61 00:03:38,640 --> 00:03:41,840 I can, I can simply represent this data with a. 62 00:03:41,840 --> 00:03:42,690 With a set of. 63 00:03:42,690 --> 00:03:47,550 Two two coordinate vectors, plus a value of which, 64 00:03:47,550 --> 00:03:50,510 in some sense, which dimension or which cluster it belongs to, right? 65 00:03:50,510 --> 00:03:54,940 So for example, this matrix that I showed you is really two dimensional, where every 66 00:03:54,940 --> 00:04:00,600 row is simply a multiplication of one of the, one of the two vectors of 1s and 0s. 67 00:04:00,600 --> 00:04:01,700 So basically the idea for 68 00:04:01,700 --> 00:04:07,410 us will be can we identify this kind of low low level of representation of data. 69 00:04:07,410 --> 00:04:13,070 So let me explain a concept that will be very important for 70 00:04:13,070 --> 00:04:14,200 us to think about this, right? 71 00:04:14,200 --> 00:04:17,600 So we are thinking that our data comes in the form of a matrix right. 72 00:04:17,600 --> 00:04:20,590 So we can think of matrix basically as every line giving us, 73 00:04:20,590 --> 00:04:25,490 giving us coordinates of a point in some d-dimensional space. 74 00:04:25,490 --> 00:04:29,450 So we have our data point, we have some number of data points, and we have some 75 00:04:29,450 --> 00:04:33,120 number of columns which is corresponds to the dimensionality of the data. 76 00:04:33,120 --> 00:04:38,260 And now the question is, what is the real intrinsic dimensionality to that data set? 77 00:04:38,260 --> 00:04:41,890 And the concept we need to explain is the concept of a rank of a matrix. 78 00:04:41,890 --> 00:04:45,750 And we will say that the rank of a matrix A is simply the number of 79 00:04:45,750 --> 00:04:47,980 linearly independent columns of A. 80 00:04:47,980 --> 00:04:51,020 So let me give you an example. 81 00:04:51,020 --> 00:04:53,370 So for, for in, in here is an example. 82 00:04:53,370 --> 00:04:58,350 You can see that the matrix A that has three rows and three columns. 83 00:04:58,350 --> 00:05:01,210 And the rank of this matrix equals 2. 84 00:05:01,210 --> 00:05:03,850 Why's the rank of this matrix equal to 2? 85 00:05:03,850 --> 00:05:08,850 Is because it has 2 linear, linearly independent rows in this case. 86 00:05:08,850 --> 00:05:11,110 What do we notice for example is that, I can, 87 00:05:11,110 --> 00:05:15,110 that the row number 3 is simply the sum of rows one and two. 88 00:05:15,110 --> 00:05:17,730 So the, the third row of this, 89 00:05:17,730 --> 00:05:22,210 of this matrix can be represented as a linear combination of rows one and two. 90 00:05:22,210 --> 00:05:25,570 So in this case our matrix is really two dimensional. 91 00:05:25,570 --> 00:05:29,180 Even I have a, I have data, in three dimensions. 92 00:05:29,180 --> 00:05:32,440 I have three columns, this matrix is really two dimensional. 93 00:05:32,440 --> 00:05:34,810 So how can we think about this is the following? 94 00:05:34,810 --> 00:05:39,080 I can basically think that there are really like two basis vectors or 95 00:05:39,080 --> 00:05:42,480 two coordinate vectors in my in my space first one corresponds to 96 00:05:42,480 --> 00:05:46,890 the first row second one corresponds to the second row and then what I can do 97 00:05:46,890 --> 00:05:51,400 now is I can represent every data point as a linear combination of these two vectors. 98 00:05:51,400 --> 00:05:52,320 So for example, 99 00:05:52,320 --> 00:05:55,830 the first row can simply be represented as a vector of one and zero. 100 00:05:55,830 --> 00:05:57,600 Which means that I only take the, 101 00:05:57,600 --> 00:06:01,810 the first, the first vector and I take zero of the second vector. 102 00:06:01,810 --> 00:06:04,530 For example the, the second row of my matrix say, 103 00:06:04,530 --> 00:06:10,400 can be represented now as a vector of one ze, zero one because I'm only taking the. 104 00:06:10,400 --> 00:06:12,880 The second of my two basis vectors. 105 00:06:12,880 --> 00:06:16,050 And for example the last row which is a sum of the rows one and 106 00:06:16,050 --> 00:06:19,720 two can be simply represented as with a vector one one. 107 00:06:19,720 --> 00:06:22,550 So why is this intuition interesting. 108 00:06:22,550 --> 00:06:25,590 This intuition is important because I could think of 109 00:06:25,590 --> 00:06:29,090 now data as being some points in high dimensional space. 110 00:06:29,090 --> 00:06:33,820 I can think of the data being represented as a matrix where, as I mentioned before, 111 00:06:33,820 --> 00:06:38,320 every data point is a row in this matrix, and every column is a separate dimension. 112 00:06:38,320 --> 00:06:42,220 And what I can do now, I can think of this as doing dimensionality reduction, right? 113 00:06:42,220 --> 00:06:46,520 So for example, if I'm given the matrix, on the top, I can basically take and 114 00:06:46,520 --> 00:06:48,960 rewrite this, the coordinates of these points. 115 00:06:48,960 --> 00:06:52,480 Instead of using three coordinates, using only two coordinates, right? 116 00:06:52,480 --> 00:06:57,580 So if I use my original coordinate space, where basically I have axis aligned. 117 00:06:57,580 --> 00:06:59,600 Vectors that describe coordinates of my space. 118 00:06:59,600 --> 00:07:04,800 So I have a one and then two zeros, and a zero one zero, and zero zero one. 119 00:07:04,800 --> 00:07:06,660 So this is x, y, and z coordinate. 120 00:07:06,660 --> 00:07:08,590 Then every, in this coordinate system, 121 00:07:08,590 --> 00:07:13,450 every data point simply corresponds to the, to the, to the row of my matrix. 122 00:07:13,450 --> 00:07:16,960 But, what I can also do is I can come and invent a new coordinate system. 123 00:07:16,960 --> 00:07:20,270 Imagine I invent the second one, where I only have two, two vectors. 124 00:07:20,270 --> 00:07:22,510 So basically, I want to represent every data point. 125 00:07:22,510 --> 00:07:26,280 With two coordinates and every what is mean this means that I want to 126 00:07:26,280 --> 00:07:30,780 represent every data point as linear combination of the, of the two vectors. 127 00:07:30,780 --> 00:07:34,230 And as I mentioned before now in this new coordinate space I 128 00:07:34,230 --> 00:07:39,120 can represent the coordinates of every point using only, only two values, right? 129 00:07:39,120 --> 00:07:43,060 And I can still reconstruct the or, the original coordinate values. 130 00:07:43,060 --> 00:07:47,190 So what does this mean is in some sense that we, we, reduce the dimensionality or 131 00:07:47,190 --> 00:07:50,970 we compressed the date in a sense that now I need a fewer num, 132 00:07:50,970 --> 00:07:54,490 number of coordinates to describe the location of every point right and 133 00:07:54,490 --> 00:07:58,010 this is what the the role of dimensionality deduction is. 134 00:07:58,010 --> 00:08:01,690 So, really the way we can think of dimensionality deduction is that we have 135 00:08:01,690 --> 00:08:06,962 a set of data points embedded in some some high dimensional space as in this case I 136 00:08:06,962 --> 00:08:12,490 have two dimensional space but clearly the data is in high dimensions but only spends 137 00:08:12,490 --> 00:08:17,830 a small dimensional spart, part of it so as in this case, I have a set of points. 138 00:08:17,830 --> 00:08:23,570 That are, that I, that I'm given in, in two-dimensional space but in reality 139 00:08:23,570 --> 00:08:27,550 these points simply fall on a line and i would like to discover that these points 140 00:08:27,550 --> 00:08:31,910 are imbedded in a small, small subspace and I would like to present now or 141 00:08:31,910 --> 00:08:36,500 compress the dimensionality of every point to this small coordinate subspace. 142 00:08:36,500 --> 00:08:39,940 And what is important here for example in this particular case is that. 143 00:08:39,940 --> 00:08:43,460 I can now think of representing the coordinates of every point, 144 00:08:43,460 --> 00:08:45,020 using kind of two dimensions. 145 00:08:45,020 --> 00:08:49,540 I can represent that position along the, the, the red line. 146 00:08:49,540 --> 00:08:52,510 And I can represent it with the coordinate that tells me how far away 147 00:08:52,510 --> 00:08:55,340 from the red line is a given data point. 148 00:08:55,340 --> 00:08:56,670 And what is interesting now that's, 149 00:08:56,670 --> 00:09:00,760 is that I can say that instead of representing, still using two coordinates. 150 00:09:00,760 --> 00:09:02,650 I can could only represent using one coordinate. 151 00:09:02,650 --> 00:09:07,720 So meaning, I would forget about how far from the red line a point and I would 152 00:09:07,720 --> 00:09:11,350 only care about the location on the red line where the point can be projected. 153 00:09:11,350 --> 00:09:15,120 And this way I would be able to represent every point with a single, 154 00:09:15,120 --> 00:09:19,100 with a single number, basically the position of it along the red line and 155 00:09:19,100 --> 00:09:20,650 I would incur a bit of an error. 156 00:09:20,650 --> 00:09:24,370 Right so what we will be doing is we will be in some sense trying to use a, 157 00:09:24,370 --> 00:09:26,910 a smaller representation of our data as possible. 158 00:09:26,910 --> 00:09:31,110 So as few columns as possible while also including as little error as 159 00:09:31,110 --> 00:09:32,350 possible right so, 160 00:09:32,350 --> 00:09:36,380 what will what will the game we will be playing is between having a smaller data 161 00:09:36,380 --> 00:09:40,160 representation while also trying to incur as little error as possible. 162 00:09:41,270 --> 00:09:45,850 So the way we will do this and why we would want to do this is, is the following 163 00:09:45,850 --> 00:09:49,190 right why would I want to dis, discuss do the dimensionality reduction. 164 00:09:49,190 --> 00:09:50,910 So the first thing is I would want to for 165 00:09:50,910 --> 00:09:53,620 example discover hidden correlations in my data. 166 00:09:53,620 --> 00:09:56,200 And sometimes I would like to discovered really the, 167 00:09:56,200 --> 00:10:00,570 the latent dimensions along the which d, along which the data varies. 168 00:10:00,570 --> 00:10:05,660 So this is particularly useful if I think of my da, data as, as my points. 169 00:10:05,660 --> 00:10:06,910 I think of them as documents. 170 00:10:06,910 --> 00:10:10,210 Right so I can take every document, represent it as a very long vector, 171 00:10:10,210 --> 00:10:15,570 where this vector has only values zero and one where zero means a given word. 172 00:10:15,570 --> 00:10:18,510 You know, the Kth word does not appear in the document, and 173 00:10:18,510 --> 00:10:21,380 one means the word appear, appears in the document. 174 00:10:21,380 --> 00:10:25,370 And my goal, for example, would be to identify what are the axes along. 175 00:10:25,370 --> 00:10:29,430 Which these, the documents, are spread in this, 176 00:10:29,430 --> 00:10:33,290 all possible words kind of space and what we would find out is that here, 177 00:10:33,290 --> 00:10:36,930 documents are basically align themselves along different axes that 178 00:10:36,930 --> 00:10:42,330 correspond to topics like, like sports, politics, technology and so on. 179 00:10:42,330 --> 00:10:46,770 Another in, useful thing that we would want to do is for example many times we 180 00:10:46,770 --> 00:10:50,540 can take a large data set and represent it as a much smaller data set. 181 00:10:50,540 --> 00:10:51,970 In some sense that basically we, 182 00:10:51,970 --> 00:10:57,480 we are able to remove or get rid of noisy features so, or noisy columns because. 183 00:10:57,480 --> 00:11:00,540 There our data is not wearing too much, too much. 184 00:11:00,540 --> 00:11:04,640 So we can kind of get rid of, of that part of the data while still preserving more, 185 00:11:04,640 --> 00:11:06,410 most, most, most of it. 186 00:11:06,410 --> 00:11:10,630 So this is the idea in some sense to do remove, to remove noise from 187 00:11:10,630 --> 00:11:15,900 the data to remove noise and redundant features or noise and redundant columns. 188 00:11:15,900 --> 00:11:18,290 Another way why we, we may want to do this. 189 00:11:18,290 --> 00:11:21,440 Is that we want to, for example, be able to interpret or visualize data. 190 00:11:21,440 --> 00:11:25,180 What this means is that we can have very high dimensional data and 191 00:11:25,180 --> 00:11:29,340 we can reduce the dimensionality of it, maybe just to two or three dimensions. 192 00:11:29,340 --> 00:11:32,430 And plotting two or three dimensions is very easy, right? 193 00:11:32,430 --> 00:11:34,080 We can kind of plot it on the screen. 194 00:11:34,080 --> 00:11:36,120 So, that's another case. 195 00:11:36,120 --> 00:11:40,930 And, of course, one important application is that, many ties, times, we want to 196 00:11:40,930 --> 00:11:44,730 reduce dimensionality of the data so that kind of the data size also shrinks, 197 00:11:44,730 --> 00:11:49,840 which means it's easier to store, process and analyze the data afterwards, right? 198 00:11:49,840 --> 00:11:53,980 So these are all the reasons why I would want to, in some sense, find as low or 199 00:11:53,980 --> 00:11:57,290 dimens, dimension of representation of a given set of data.