1 00:00:00,680 --> 00:00:02,480 I'm David Thompson and this is the 2 00:00:02,480 --> 00:00:05,750 next lecture in the series on Dimensionality Reduction. 3 00:00:05,750 --> 00:00:10,130 It's part of the JPL-Caltech Virtual Summer School in Big Data Analytics. 4 00:00:10,130 --> 00:00:11,200 This is a fun lecture. 5 00:00:11,200 --> 00:00:14,540 This is where we actually start to get into real dimensionality reduction proper. 6 00:00:14,540 --> 00:00:17,860 So we've kind of danced around it a bit in previous lectures, I've described 7 00:00:17,860 --> 00:00:20,590 the cursive dimensionality, why high dimensional data 8 00:00:20,590 --> 00:00:23,560 sets can be problematic for pattern recognition. 9 00:00:23,560 --> 00:00:26,110 Then I described some feature selection strategies, where you 10 00:00:26,110 --> 00:00:30,330 can reduce dimensionality by selecting subsets of those attributes. 11 00:00:30,330 --> 00:00:33,950 Here we're going to get into the preview of what, what most folks think of, when, 12 00:00:33,950 --> 00:00:36,930 when they think of dimensionality reduction, which is 13 00:00:36,930 --> 00:00:39,340 actually coming up with interesting projections of the 14 00:00:39,340 --> 00:00:42,410 data that utilize all of the attributes but 15 00:00:42,410 --> 00:00:44,690 represent the data in some lower dimensional space 16 00:00:44,690 --> 00:00:47,570 that we can more easily visualize and its 17 00:00:47,570 --> 00:00:51,890 easier for our pattern recognition algorithms to use. 18 00:00:51,890 --> 00:00:54,252 So we're going to be discussing linear methods here. 19 00:00:54,252 --> 00:00:56,290 All right. 20 00:00:56,290 --> 00:00:59,530 The objectives of this talk you should become 21 00:00:59,530 --> 00:01:02,230 familiar with dimensionality reduction and its relationship with 22 00:01:02,230 --> 00:01:06,390 feature selection and understand Linear Dimensionality Reduction your 23 00:01:06,390 --> 00:01:11,380 principal analysis and it's relation to singular value decomposition. 24 00:01:11,380 --> 00:01:13,865 And then finally we'll be talking about eigenface's too. 25 00:01:13,865 --> 00:01:16,476 [BLANK_AUDIO] 26 00:01:16,476 --> 00:01:17,424 All right. 27 00:01:17,424 --> 00:01:21,530 So, di, dimensionality reduction relies on the intuition. 28 00:01:21,530 --> 00:01:25,260 That even though this high dimensional spaces are very difficult to deal with. 29 00:01:25,260 --> 00:01:27,180 It's almost never the case that our 30 00:01:27,180 --> 00:01:30,260 data actually fills the high dimensional space completely. 31 00:01:30,260 --> 00:01:31,920 Real processes aren't like that. 32 00:01:31,920 --> 00:01:34,880 It's very rare that you find a process that, that 33 00:01:34,880 --> 00:01:39,485 actually has a thousand of intrinsic parameters along which it varies. 34 00:01:39,485 --> 00:01:39,618 Right. 35 00:01:39,618 --> 00:01:43,720 More commonly the process that generates our data is some 36 00:01:43,720 --> 00:01:47,590 lower dimensional structure, that's embedded in this high dimensional space. 37 00:01:47,590 --> 00:01:47,770 Right. 38 00:01:47,770 --> 00:01:51,300 So, this is commonly represented as some sort of a manifold 39 00:01:51,300 --> 00:01:54,990 or a subspace that lives in our high dimensional attribute space. 40 00:01:54,990 --> 00:01:57,245 The point of dimensionality reduction is to 41 00:01:57,245 --> 00:02:01,450 revile or uncover, that manifold or that subspace. 42 00:02:01,450 --> 00:02:02,640 Here, we see an example. 43 00:02:02,640 --> 00:02:07,294 So you may recall from earlier lectures where I talked about image analysis 44 00:02:07,294 --> 00:02:11,409 as one area where we have to deal commonly with high dimensional data. 45 00:02:11,409 --> 00:02:11,760 Right? 46 00:02:11,760 --> 00:02:15,782 If you have say, a thumbnail image that's 20 pixels on a side. 47 00:02:15,782 --> 00:02:20,170 That's 20 times 20, 400 different attributes of potential variation. 48 00:02:20,170 --> 00:02:20,320 Right? 49 00:02:20,320 --> 00:02:21,710 It's a very high dimensional space. 50 00:02:21,710 --> 00:02:23,690 But, in practice, many of these data 51 00:02:23,690 --> 00:02:26,840 sets have a much smaller intrinsic dimensionality. 52 00:02:26,840 --> 00:02:31,190 That is they lie in a low dimensional manifold of that 400 dimensional space. 53 00:02:31,190 --> 00:02:32,840 Here's an example from a famous 54 00:02:32,840 --> 00:02:35,970 dimensionality reduction paper showing images of hands. 55 00:02:35,970 --> 00:02:39,790 So we've got probably couple hundred data points here. 56 00:02:39,790 --> 00:02:42,740 These are the blue points that I've plotted in just two dimensions. 57 00:02:42,740 --> 00:02:46,910 And we've come up, we've projected these data points down onto this two-dimensional 58 00:02:46,910 --> 00:02:51,250 plane in such a way that neighboring points are similar to each other. 59 00:02:51,250 --> 00:02:52,910 And distant points are dissimilar. 60 00:02:52,910 --> 00:02:54,880 And you can see that there are actually only 61 00:02:54,880 --> 00:02:59,600 two dimensions of intrinsic variation in these hand images. 62 00:02:59,600 --> 00:02:59,820 Right. 63 00:02:59,820 --> 00:03:02,960 If you know the coordinates in the space, right? 64 00:03:02,960 --> 00:03:06,630 In this 2D space, you can specify exactly what the hand image is going to look like. 65 00:03:06,630 --> 00:03:09,990 The two dimensions that we've labeled are the 66 00:03:09,990 --> 00:03:13,185 wrist, wrist rotation and the extension of the fingers. 67 00:03:13,185 --> 00:03:13,300 Right? 68 00:03:13,300 --> 00:03:15,550 And with those two parameters, you can 69 00:03:15,550 --> 00:03:17,619 adequately describe any one of these images. 70 00:03:19,050 --> 00:03:22,540 So this is a case where there's some lower dimensional manifold we've uncovered. 71 00:03:22,540 --> 00:03:24,160 Here its non linear manifold, right? 72 00:03:24,160 --> 00:03:25,990 We'll get to this in later talks. 73 00:03:25,990 --> 00:03:28,820 But you can imagine that there are linear subspaces that 74 00:03:28,820 --> 00:03:32,070 would describe this, this data set more efficiently as well. 75 00:03:32,070 --> 00:03:35,290 And it's almost always the case, that you can come up with some lower dimensional 76 00:03:35,290 --> 00:03:37,310 projection that preserves all of the data 77 00:03:37,310 --> 00:03:40,110 in your data set, while reducing redundant dimensions. 78 00:03:42,040 --> 00:03:45,030 So, let's start off with some formal definitions before we go any further. 79 00:03:45,030 --> 00:03:48,746 Again, we will be looking at data points which are column vectors. 80 00:03:48,746 --> 00:03:51,830 So here a column vector x has n attributes, 81 00:03:51,830 --> 00:03:54,270 so we're listing these attributes from one to n. 82 00:03:54,270 --> 00:03:58,290 As a column, and you can stack them together in a matrix, row-wise. 83 00:03:58,290 --> 00:04:01,460 So, we have an n by d matrix, where d is the total number 84 00:04:01,460 --> 00:04:04,170 of data points in our, in the data set that we're trying to project. 85 00:04:04,170 --> 00:04:05,250 And what we're aiming to do with 86 00:04:05,250 --> 00:04:08,070 dimensionality reduction, is project these onto new 87 00:04:08,070 --> 00:04:10,380 data points, which I'll here represent as 88 00:04:10,380 --> 00:04:13,990 y, that have some lower dimensional representation. 89 00:04:13,990 --> 00:04:18,400 So here we just have m attributes, where m is considerably less than n. 90 00:04:18,400 --> 00:04:18,580 Right? 91 00:04:18,580 --> 00:04:21,998 So we want to, this is some lower dimensional subspace. 92 00:04:21,998 --> 00:04:23,789 And dimensionality reduction is just this mapping. 93 00:04:23,789 --> 00:04:27,002 [BLANK_AUDIO] 94 00:04:27,002 --> 00:04:27,640 Okay. 95 00:04:27,640 --> 00:04:30,030 So linear, for Linear Dimensionality Reduction, 96 00:04:30,030 --> 00:04:33,350 which is probably the most common form 97 00:04:33,350 --> 00:04:37,170 of this algorithm, we'll define the mapping from x to y to be linear. 98 00:04:37,170 --> 00:04:39,880 That is, you can think of it as just pre multiplication. 99 00:04:40,910 --> 00:04:43,660 A new basis for representing the data that 100 00:04:43,660 --> 00:04:46,860 has a smaller dimensionality than our original basis, right? 101 00:04:46,860 --> 00:04:50,870 So we can represent that as an m by n projection matrix and if we pre 102 00:04:50,870 --> 00:04:53,150 multiply it with the x matrix, then this 103 00:04:53,150 --> 00:04:56,460 gives us the desired projected data matrix y. 104 00:04:56,460 --> 00:04:59,500 So we're finding a subspace that best represents the data. 105 00:04:59,500 --> 00:05:01,370 And the most common approach to doing this, to 106 00:05:01,370 --> 00:05:05,010 finding this subspace, is called Principal Component Analysis, or PCA. 107 00:05:05,010 --> 00:05:09,370 Now PCA is quite common, so you may have come across it in your own disciplines. 108 00:05:09,370 --> 00:05:09,620 Right? 109 00:05:09,620 --> 00:05:11,840 It goes by a variety of different names. 110 00:05:11,840 --> 00:05:14,200 In the earth sciences, it could be the 111 00:05:14,200 --> 00:05:18,010 empirical error function, or the empirical orthogonal function. 112 00:05:18,010 --> 00:05:19,730 in, a lot of times in remote sensing, 113 00:05:19,730 --> 00:05:22,340 it's known as the minimum noise fraction transform. 114 00:05:22,340 --> 00:05:24,850 There are other, it may have other names in other disciplines. 115 00:05:24,850 --> 00:05:26,930 So it's highly likely that you've encountered this before. 116 00:05:26,930 --> 00:05:30,678 But it's, it's good to review, because it's just so darn useful. 117 00:05:30,678 --> 00:05:34,260 And even for a data set that isn't truly 118 00:05:34,260 --> 00:05:36,930 on a linear manifold often, sort of a coarse 119 00:05:36,930 --> 00:05:40,990 PCA reduction of the initial dimensions on some smaller, 120 00:05:40,990 --> 00:05:44,720 linear subspace of the data will still yield benefits. 121 00:05:44,720 --> 00:05:47,370 Even if the, you then go on to subsequently apply some other 122 00:05:47,370 --> 00:05:52,040 sort of analysis, some other nonlinear mapping or pattern recognition after that. 123 00:05:52,040 --> 00:05:55,320 Principal Component Analysis is almost always a good thing to do. 124 00:05:55,320 --> 00:05:57,749 It's a, it's a really fundamental tool in the toolbox. 125 00:06:00,040 --> 00:06:04,120 The goal of Principal Component Analysis or how does it, how it identifies this 126 00:06:04,120 --> 00:06:06,980 basis, is to find the orthogonal directions 127 00:06:06,980 --> 00:06:09,050 that maximize the variance of the data set. 128 00:06:09,050 --> 00:06:11,460 So here's an example of a, a data set in two 129 00:06:11,460 --> 00:06:14,230 dimensions, and you could imagine projecting 130 00:06:14,230 --> 00:06:16,250 this onto a one dimensional subspace. 131 00:06:16,250 --> 00:06:16,450 Right? 132 00:06:16,450 --> 00:06:18,420 So we want to project this onto a line, we 133 00:06:18,420 --> 00:06:20,920 want to draw a line somewhere in this data cloud. 134 00:06:20,920 --> 00:06:24,580 That allows us to optimally reconstruct the dataset 135 00:06:25,670 --> 00:06:29,890 or maximize, equivalently maximize the variance along that projection. 136 00:06:29,890 --> 00:06:31,150 So, how would we do it? 137 00:06:31,150 --> 00:06:33,280 Which, which line would you choose? 138 00:06:33,280 --> 00:06:36,280 If you were to, to analyze this data site and you had to come up 139 00:06:36,280 --> 00:06:40,420 with a single linear direction on to which all of your data would be projected. 140 00:06:40,420 --> 00:06:42,920 Well obviously, you want to follow the, the 141 00:06:42,920 --> 00:06:46,140 direction of, of variation that is this main access. 142 00:06:46,140 --> 00:06:47,780 So, the, and the first principle component is 143 00:06:47,780 --> 00:06:51,490 indeed, aligned with the main access of variation. 144 00:06:51,490 --> 00:06:54,290 So, if you project all of your data points onto that, that red line 145 00:06:54,290 --> 00:06:56,790 or that red direction then that will 146 00:06:56,790 --> 00:06:59,870 maximize the variance of the resulting projection. 147 00:06:59,870 --> 00:07:02,040 And equivalently, if you wanted to reconstruct 148 00:07:02,040 --> 00:07:04,150 a data point from its position along that 149 00:07:04,150 --> 00:07:05,780 line, you'd get pretty close to the 150 00:07:05,780 --> 00:07:10,440 original point if using that direction of variation. 151 00:07:10,440 --> 00:07:13,920 So, one thing to notice about this data set that I'll get 152 00:07:13,920 --> 00:07:16,660 back to in a couple slides is that it's centered at zero. 153 00:07:16,660 --> 00:07:19,950 So this is an important feature of the Principal Component 154 00:07:19,950 --> 00:07:22,590 Analysis is that the data cloud really has to be centered. 155 00:07:22,590 --> 00:07:24,910 Now it's easy to center any data cloud, right? 156 00:07:24,910 --> 00:07:28,570 Before applying PCA, simply subtract of the mean. 157 00:07:28,570 --> 00:07:28,750 Right? 158 00:07:28,750 --> 00:07:29,710 But that's an important step. 159 00:07:29,710 --> 00:07:32,810 And one that will be important as we start looking at nonlinear analogs of PCA. 160 00:07:34,130 --> 00:07:34,320 Okay. 161 00:07:34,320 --> 00:07:37,440 So there's our first principal component it's pretty obvious. 162 00:07:37,440 --> 00:07:39,810 Our second principal component of our data set 163 00:07:39,810 --> 00:07:41,700 would have to be orthogonal to that one, right? 164 00:07:41,700 --> 00:07:47,090 Because again, PCA dimensions are, its an orthogonal basis its an orthanormal basis. 165 00:07:47,090 --> 00:07:50,640 So the second principal component would come out perpendicular to the first. 166 00:07:52,750 --> 00:07:56,450 So note also that these vectors have heavy unit length, our goal here 167 00:07:56,450 --> 00:08:00,320 is to provide a true basis that is a rotation of the data. 168 00:08:00,320 --> 00:08:04,860 In which every thing is, is orthornormalized and sort of independent. 169 00:08:06,350 --> 00:08:07,170 Okay. 170 00:08:07,170 --> 00:08:12,390 So this will require a new a new construction. 171 00:08:12,390 --> 00:08:14,450 Which is that the covariance matrix, that I want 172 00:08:14,450 --> 00:08:16,320 to introduce here, if you're not familiar with it already. 173 00:08:16,320 --> 00:08:19,500 So, covariance matrix it's simply the matrix of all the 174 00:08:19,500 --> 00:08:22,640 covariances between all of the different attributes in your data. 175 00:08:22,640 --> 00:08:24,290 So this is the, the formal definition. 176 00:08:24,290 --> 00:08:26,380 Where you have, the, the covariance matrix, 177 00:08:26,380 --> 00:08:29,190 that we're representing here as sigma sub X. 178 00:08:29,190 --> 00:08:36,070 The sigma sub X for attributes i and j is the expectation of, the, attribute X. 179 00:08:37,100 --> 00:08:41,810 Minus its mean times the attribute j minus its mean. 180 00:08:41,810 --> 00:08:42,340 I'm sorry. 181 00:08:42,340 --> 00:08:46,150 The attribute y minus its mean times the attribute j 182 00:08:46,150 --> 00:08:48,900 minus its mean and you can put all these together 183 00:08:48,900 --> 00:08:51,840 element wise into an m by m matrix, where m 184 00:08:51,840 --> 00:08:55,140 is the total number of attributes in your data set. 185 00:08:55,140 --> 00:08:59,270 You can estimate that using what we call the, the sample covariance matrix. 186 00:08:59,270 --> 00:09:01,840 Which is represented by this expression here and 187 00:09:01,840 --> 00:09:04,820 that the center of the slide take the, the, 188 00:09:04,820 --> 00:09:07,660 essentially the, the data sites cross product and divide 189 00:09:07,660 --> 00:09:11,760 by the total number of data points minus 1. 190 00:09:11,760 --> 00:09:12,490 Okay. 191 00:09:12,490 --> 00:09:14,950 So, the properties of this, this covariance matrix. 192 00:09:14,950 --> 00:09:19,620 Well the diagonal terms have the variance of the different attributes of x. 193 00:09:19,620 --> 00:09:23,670 And the off-diagonal terms, like I said, represent the covariances of x. 194 00:09:23,670 --> 00:09:27,060 The matrix, the matrix itself has some unique and important properties. 195 00:09:27,060 --> 00:09:31,200 In particular, well, it's square, obviously, and it's symmetric. 196 00:09:31,200 --> 00:09:34,770 But it's also a special class of matrixes known as positive semi-definite. 197 00:09:34,770 --> 00:09:37,610 And, every positive semi-definite matrix is 198 00:09:37,610 --> 00:09:39,910 a valid covariance matrix and, and vice-versa. 199 00:09:39,910 --> 00:09:41,420 And it will be important to maintain this 200 00:09:41,420 --> 00:09:44,980 property of positive semi-definiteness, in, in the future. 201 00:09:44,980 --> 00:09:47,090 Particularly, as we look at the nonlinear analogs. 202 00:09:49,580 --> 00:09:50,180 Okay. 203 00:09:50,180 --> 00:09:53,050 So how would this, this work in practice? 204 00:09:53,050 --> 00:09:55,510 How do we, we maximize the variance of a projection? 205 00:09:55,510 --> 00:09:58,280 How do we identify the appropriate projection to use? 206 00:09:58,280 --> 00:10:01,440 Well here on the, the left side you can see. 207 00:10:01,440 --> 00:10:03,500 it, we can rewrite the, the variance of 208 00:10:03,500 --> 00:10:06,300 our projection as the, the expectation of the projection. 209 00:10:06,300 --> 00:10:07,980 Here I've noted the projection itself. 210 00:10:07,980 --> 00:10:13,010 The projection vector as a vector v which I'm multiplying. 211 00:10:13,010 --> 00:10:15,700 I'm basically taken the dot product of that with x. 212 00:10:15,700 --> 00:10:17,430 And that gives me the projected location. 213 00:10:17,430 --> 00:10:23,990 So the projected location data point minus its expectation that quantity squared or 214 00:10:23,990 --> 00:10:26,320 the expectation of that quantity squared is 215 00:10:26,320 --> 00:10:28,040 the, the formal definition of the variance. 216 00:10:28,040 --> 00:10:32,900 And you can through some algebra expand this and get the expression in the center 217 00:10:32,900 --> 00:10:39,548 which is the expression v times the covariance matrix times v. 218 00:10:39,548 --> 00:10:44,790 And then it's basically, it's known for zero-mean covariance matrix, the unit 219 00:10:44,790 --> 00:10:49,768 vector that minimizes this quantity is the top eigenvector of the covariance matrix. 220 00:10:49,768 --> 00:10:52,130 So you it's simply the solution to the Eigen 221 00:10:52,130 --> 00:10:56,000 system that starts with the sample covariance matrix and 222 00:10:56,000 --> 00:11:00,200 then gives you the eigenvectors of that sample covariance 223 00:11:00,200 --> 00:11:03,120 matrix, which is the expression in the lower right. 224 00:11:03,120 --> 00:11:05,790 So it's basically, a straight forward Eigen system. 225 00:11:05,790 --> 00:11:10,990 And there exist lots of numerical packages that will solve this sufficiently mat 226 00:11:10,990 --> 00:11:15,360 lab has a bunch of them that the eye'ds function is particularly useful here. 227 00:11:15,360 --> 00:11:19,650 And another useful property of this whole procedure is that you only need 228 00:11:19,650 --> 00:11:22,147 to calculate as many eigenvectors and 229 00:11:22,147 --> 00:11:24,900 eigenvalues as you want to have components. 230 00:11:24,900 --> 00:11:25,100 Right? 231 00:11:25,100 --> 00:11:29,640 So if you are projecting the data onto the top six principal components, 232 00:11:29,640 --> 00:11:33,590 then you only need to calculate the top six eigenvectors and that that's enough. 233 00:11:33,590 --> 00:11:36,910 So there are efficient, iterative strategies for doing this 234 00:11:36,910 --> 00:11:39,180 and it makes it a pretty straight forward calculation. 235 00:11:40,320 --> 00:11:43,390 So in summary, what's the PCA recipe? 236 00:11:43,390 --> 00:11:44,970 You convert the data to have zero mean. 237 00:11:44,970 --> 00:11:47,240 That is, you subtract off the mean from the dataset. 238 00:11:47,240 --> 00:11:50,500 And then you form the sample covariance matrix or you, I'm sorry. 239 00:11:50,500 --> 00:11:52,730 You form your projection matrix, which in this case is 240 00:11:52,730 --> 00:11:56,620 A, using the top n eigenvectors of the sample covariance matrix. 241 00:11:56,620 --> 00:12:01,230 Or equivalently, and I'll, get into this in greater length later, you, there's a 242 00:12:01,230 --> 00:12:03,150 similar formulation that uses the sim, the 243 00:12:03,150 --> 00:12:06,160 singular value decomposition of the matrix x. 244 00:12:06,160 --> 00:12:06,360 Okay. 245 00:12:06,360 --> 00:12:10,430 So this gives you a matrix A, which is your orthonormal basis. 246 00:12:10,430 --> 00:12:12,580 And then in order to project the data to a lower 247 00:12:12,580 --> 00:12:16,460 dimensional space, you subtract off the mean of a new data point. 248 00:12:16,460 --> 00:12:20,780 And then apply, pre-multiply that, that orthonormal basis 249 00:12:20,780 --> 00:12:23,050 x which gives you the projected data point y. 250 00:12:23,050 --> 00:12:28,530 To reconstruct the original data point from it's projection, you multiply by 251 00:12:28,530 --> 00:12:32,530 the, the transpose of your projection matrix, and add back the mean. 252 00:12:32,530 --> 00:12:35,720 And that gives you a reconstruction which I've here noted X hat. 253 00:12:35,720 --> 00:12:37,610 All right. 254 00:12:37,610 --> 00:12:40,240 So it's, it's a fairly straightforward procedure. 255 00:12:40,240 --> 00:12:44,110 And it's useful for a wide range of different pattern recognition problems. 256 00:12:44,110 --> 00:12:47,460 I'm going to talk now about one canonical example 257 00:12:47,460 --> 00:12:50,660 of Principal Components Analysis, which is called eigenfaces. 258 00:12:50,660 --> 00:12:53,490 And they've been doing this for, for many decades. 259 00:12:53,490 --> 00:12:56,260 Here's an example from Moghaddam et al. 260 00:12:57,500 --> 00:13:01,005 Where they apply this to a, a fairly 261 00:13:01,005 --> 00:13:06,300 well-known dataset called a FERET frontal view image database. 262 00:13:06,300 --> 00:13:10,630 here, we're projecting these data points, where each data points is a face 263 00:13:10,630 --> 00:13:12,820 onto the, the set of basis factors 264 00:13:12,820 --> 00:13:16,190 which best represent variance among different faces. 265 00:13:16,190 --> 00:13:21,346 So, you can use this for face recognition, for detection of faces and new images. 266 00:13:21,346 --> 00:13:23,990 Eigenfaces are sort of universally useful for, 267 00:13:23,990 --> 00:13:26,227 for all sorts of, of face recognition problems. 268 00:13:26,227 --> 00:13:34,030 Here is here are the first top eight principal components of the face data set. 269 00:13:34,030 --> 00:13:35,780 And these are, it's interesting that 270 00:13:35,780 --> 00:13:38,390 these have their own distinctive interpretations. 271 00:13:38,390 --> 00:13:40,710 So starting with the first principal component there in the upper 272 00:13:40,710 --> 00:13:44,050 left, you can see that there's a lot that, that bright patch 273 00:13:44,050 --> 00:13:46,820 on the forehead suggests that maybe this principal component is concerned 274 00:13:46,820 --> 00:13:51,560 mostly with say, features of the hairline or illumination on the forehead. 275 00:13:51,560 --> 00:13:55,290 Perhaps the second principal component right next to it moving right. 276 00:13:55,290 --> 00:13:59,430 It looks like there's some shading there, so perhaps the second axis of 277 00:13:59,430 --> 00:14:00,810 a variation has to do with 278 00:14:00,810 --> 00:14:03,620 say, illumination differences from left to right. 279 00:14:03,620 --> 00:14:06,220 You can see in the third principal component that there's 280 00:14:06,220 --> 00:14:09,730 definitely something to do with the hairline there and the forehead. 281 00:14:09,730 --> 00:14:10,940 And so on and so forth. 282 00:14:10,940 --> 00:14:12,680 You can see different features pop out in the 283 00:14:12,680 --> 00:14:16,660 principal components, such as structure and the face and cheeks. 284 00:14:16,660 --> 00:14:18,728 The position of the eyes and eye sockets. 285 00:14:18,728 --> 00:14:20,720 There's even a, an obvious expression 286 00:14:20,720 --> 00:14:23,150 change in the principal components, and all 287 00:14:23,150 --> 00:14:27,390 of these are sort of distinct axes along which the data can vary. 288 00:14:27,390 --> 00:14:30,290 So that the principal components interestingly enough, are themselves 289 00:14:30,290 --> 00:14:35,330 interpretable as as direction of variances in the data set. 290 00:14:35,330 --> 00:14:36,100 All right. 291 00:14:36,100 --> 00:14:37,660 So they can be informed of in their own right. 292 00:14:39,810 --> 00:14:41,360 You can also interpret the eigenvalues. 293 00:14:41,360 --> 00:14:46,140 So the eigenvalues associated with that eigen system that I showed you before. 294 00:14:46,140 --> 00:14:49,920 In tell you a bit about how many principal components you need to use. 295 00:14:49,920 --> 00:14:54,150 And in particular, here's the, the chart of all n eigenvalues. 296 00:14:54,150 --> 00:14:57,630 There's a dramatic fall off initially after the 297 00:14:57,630 --> 00:15:01,280 first, well, few eigen values of, of the system. 298 00:15:01,280 --> 00:15:01,440 Right? 299 00:15:01,440 --> 00:15:02,500 And what that means is that 300 00:15:02,500 --> 00:15:05,640 the, the intrinsic dimensionality of this eigenfaces 301 00:15:05,640 --> 00:15:09,650 data set is actually much lower than the full number of attributes n. 302 00:15:09,650 --> 00:15:09,820 Right? 303 00:15:09,820 --> 00:15:12,860 That we can capture the ma, majority of the variance just by using a 304 00:15:12,860 --> 00:15:16,150 much smaller set, m, and in fact that's typically what people do, they could use 305 00:15:16,150 --> 00:15:19,910 the top, say, ten or 20 dimensions, which would be much better than using all, 306 00:15:19,910 --> 00:15:21,820 like, hundreds or thousands of dimensions in 307 00:15:21,820 --> 00:15:23,353 the, in the original phase state data set. 308 00:15:23,353 --> 00:15:24,142 Right. 309 00:15:24,142 --> 00:15:28,800 So and the, the eigenvalue plot here gives you some 310 00:15:28,800 --> 00:15:33,030 indication of just, by the, where that fall off starts to 311 00:15:33,030 --> 00:15:36,350 asymptote exactly, how many eigen vectors you need to include in 312 00:15:36,350 --> 00:15:39,239 your orthonormal bases to adequately capture the variants of the data. 313 00:15:41,570 --> 00:15:41,820 All right. 314 00:15:41,820 --> 00:15:44,710 I want to close with a few notes on how to implement 315 00:15:44,710 --> 00:15:49,900 this efficiently for very large dimensions or very large numbers of data points. 316 00:15:49,900 --> 00:15:53,940 So obviously even these calculations onerous for a 317 00:15:53,940 --> 00:15:55,410 very large d or a very large n. 318 00:15:55,410 --> 00:15:57,170 Things like computing the sample covariance 319 00:15:57,170 --> 00:16:00,290 matrix can be challenging for large numbers 320 00:16:00,290 --> 00:16:04,710 of data points computing as inverse can be challenging for very large dimensionality. 321 00:16:04,710 --> 00:16:07,290 There are efficient ways to, to handle this. 322 00:16:07,290 --> 00:16:10,330 One of the common ways is to use singular value decomposition. 323 00:16:10,330 --> 00:16:13,960 So it turns out, that the, solving that eigen system that I showed 324 00:16:13,960 --> 00:16:16,130 you before, is equivalent to performing 325 00:16:16,130 --> 00:16:18,660 singular value decomposition on the data matrix. 326 00:16:18,660 --> 00:16:24,454 And you can simply use the left singular vectors, or the, the left- 327 00:16:24,454 --> 00:16:25,030 Yeah. 328 00:16:25,030 --> 00:16:27,890 The left vector is U, here, which are column 329 00:16:27,890 --> 00:16:31,900 vectors of that, that singular value decomposition matrix, together with 330 00:16:31,900 --> 00:16:36,500 the top singular values in the diagonal matrix D instead 331 00:16:36,500 --> 00:16:39,960 of your eigenvalues and that amounts to the same thing. 332 00:16:39,960 --> 00:16:40,200 Actually. 333 00:16:40,200 --> 00:16:41,560 And so this is, and because there are 334 00:16:41,560 --> 00:16:46,040 efficient singular value decompositions and incremental singular value 335 00:16:46,040 --> 00:16:48,560 decompositions, you can use these to improve the, 336 00:16:48,560 --> 00:16:51,430 the compositional performance on, on very large data sets. 337 00:16:51,430 --> 00:16:54,520 Another approach is to just calculate one principal component at a time. 338 00:16:54,520 --> 00:16:58,980 I alluded before to intertive solutions to the eigan system. 339 00:16:58,980 --> 00:17:01,680 Roweis et al in NIPS provided a method 340 00:17:01,680 --> 00:17:06,130 for calculating one principal component at a time. 341 00:17:06,130 --> 00:17:09,260 Another method would be to use an online learning strategy, where 342 00:17:09,260 --> 00:17:12,410 you train principal components analysis on a subset of the data, 343 00:17:12,410 --> 00:17:15,570 and then iteratively update that or improve it sequentially in sort 344 00:17:15,570 --> 00:17:19,500 of an online fashion so you can use a sequential estimation approach. 345 00:17:19,500 --> 00:17:22,100 There's other literature about how to do that. 346 00:17:22,100 --> 00:17:25,940 So it's not so important that you know, offhand how to do this, 347 00:17:25,940 --> 00:17:29,200 but simply that, you know, where, that these methods exist in the literature 348 00:17:29,200 --> 00:17:33,270 and if you get stuck with a problem that's too large for, naive 349 00:17:33,270 --> 00:17:35,620 principal compare and analysis, that there are 350 00:17:35,620 --> 00:17:39,110 alternatives other for computing solutions more efficiently. 351 00:17:40,430 --> 00:17:40,670 All right. 352 00:17:40,670 --> 00:17:45,870 So to summarize Principal Component Analysis is a 353 00:17:45,870 --> 00:17:47,560 terribly useful tool to have in your toolbox. 354 00:17:47,560 --> 00:17:49,000 It's a reliable, standard method 355 00:17:49,000 --> 00:17:51,850 for dimensionality reduction and visualization. 356 00:17:51,850 --> 00:17:55,870 The objective is to find an orthonormal basis that maximizes the 357 00:17:55,870 --> 00:18:01,700 variance of the projected data in the resulting new feature space. 358 00:18:01,700 --> 00:18:04,820 The basis vectors and eigenvalues can also be 359 00:18:04,820 --> 00:18:07,040 interpreted to provide insight about the data set. 360 00:18:08,330 --> 00:18:11,448 In particular, what the principle axes of variation are. 361 00:18:11,448 --> 00:18:14,080 And also what the intrinsic dimensionality of your 362 00:18:14,080 --> 00:18:17,430 dataset is, which is what the eigenvalue analysis provides.