1 00:00:01,150 --> 00:00:04,870 I'm David Thompson and this is the next lecture in the series 2 00:00:04,870 --> 00:00:09,250 from the, the JPL Caltech virtual summer school on big data analytics. 3 00:00:09,250 --> 00:00:11,420 We talked previously about different strategies for 4 00:00:11,420 --> 00:00:15,790 dimensionality reduction, including, basic feature selection approaches. 5 00:00:15,790 --> 00:00:18,130 Linear methods, like principle component analysis. 6 00:00:18,130 --> 00:00:22,870 And also, metric learning approaches, which generalize linear dimensionality 7 00:00:22,870 --> 00:00:26,120 reduction to the case where class information is available. 8 00:00:26,120 --> 00:00:30,080 Now we're going to depart from the realm of, of linear projections all together. 9 00:00:30,080 --> 00:00:34,290 And move into a topic known as Nonlinear Dimensionality Reduction. 10 00:00:34,290 --> 00:00:37,480 And in particular, we'll be describing kernel principle component analysis. 11 00:00:37,480 --> 00:00:39,142 Which is a kernelized version of PCA. 12 00:00:39,142 --> 00:00:44,530 All right, the objectives of this talk are to first, just to be able to 13 00:00:44,530 --> 00:00:47,410 distinguish linear from nonlinear dimensionality reduction, and 14 00:00:47,410 --> 00:00:50,160 to know and understand the differences between them. 15 00:00:50,160 --> 00:00:52,160 Kernel PCA is just one of 16 00:00:52,160 --> 00:00:54,920 many different nonlinear dimensionality reduction strategies. 17 00:00:54,920 --> 00:00:57,255 I think it's a particularly useful and widespread 18 00:00:57,255 --> 00:00:59,220 ones, so we're going to talk about that and 19 00:00:59,220 --> 00:01:01,720 focus on that in this talk, and you 20 00:01:01,720 --> 00:01:04,400 should be comfortable with it and it's derivation. 21 00:01:04,400 --> 00:01:09,220 And also, know, have some familiarity with the other methods that are out 22 00:01:09,220 --> 00:01:13,700 there and available to you if you prefer to use those for other applications. 23 00:01:13,700 --> 00:01:17,480 More generally, there are advantages and pitfalls to nonlinear, as opposed to 24 00:01:17,480 --> 00:01:19,110 linear approaches, and we should understand 25 00:01:19,110 --> 00:01:20,180 them, try and understand those too. 26 00:01:23,352 --> 00:01:26,750 All right, so why do we care about nonlinear projections? 27 00:01:26,750 --> 00:01:30,740 Well, there are some cases where linear subspaces just aren't good enough. 28 00:01:30,740 --> 00:01:32,920 I mentioned before that linear subspaces are 29 00:01:32,920 --> 00:01:36,510 almost always useful on any dataset, but they 30 00:01:36,510 --> 00:01:40,170 may not adequately represent the underlying manifold, 31 00:01:40,170 --> 00:01:42,630 which may have some other nonlinear structure, right? 32 00:01:42,630 --> 00:01:46,514 So, even if I start and am able to project my data linearly down to, say, 33 00:01:46,514 --> 00:01:48,999 20 or 40 dimensions, that still, I still 34 00:01:48,999 --> 00:01:52,710 might be able to find a more efficient representation. 35 00:01:52,710 --> 00:01:54,930 That captures the, the models the data 36 00:01:54,930 --> 00:01:58,600 even better using a lower dimensional manifold. 37 00:01:58,600 --> 00:02:01,350 And that's the idea behind nonlinear dimensionality reduction. 38 00:02:01,350 --> 00:02:05,670 So here's an example, here, portrayed in these four image panes. 39 00:02:05,670 --> 00:02:09,700 We have in the upper right, or I'm sorry, the upper left, on this S 40 00:02:09,700 --> 00:02:12,125 curve which is a curved manifold that's a 41 00:02:12,125 --> 00:02:15,730 two-dimensional surface that's embedded in a three-dimensional space. 42 00:02:15,730 --> 00:02:17,620 Now if, if you're to do a linear 43 00:02:17,620 --> 00:02:21,310 dimensionality reduction on this data set, that would amount 44 00:02:21,310 --> 00:02:24,960 to maybe slicing taking hyper-planes somewhere through that, that 45 00:02:24,960 --> 00:02:28,315 data and projecting all the points onto that hyper-plane. 46 00:02:28,315 --> 00:02:30,800 Now, it, try as you might, you're not going to be able to find a 47 00:02:30,800 --> 00:02:33,340 single hyper-plane that would let you recover 48 00:02:33,340 --> 00:02:36,400 the original points of that, of those data. 49 00:02:36,400 --> 00:02:39,630 No matter how you orient that hyper-plane, you're 50 00:02:39,630 --> 00:02:41,310 always going to lose quite a bit of information. 51 00:02:41,310 --> 00:02:44,430 And this is reflected by the, the PCA projection result that 52 00:02:44,430 --> 00:02:47,160 you see there in the, in the upper right, where it tends 53 00:02:47,160 --> 00:02:50,220 to mix a lot of unlike colors together even though the, the 54 00:02:50,220 --> 00:02:53,420 different colors are supposed to be on different sides of the manifold. 55 00:02:53,420 --> 00:02:57,400 So the PCA projection down to 2D is really inadequate. 56 00:02:57,400 --> 00:02:59,670 Even though the, the structure is intrinsically two 57 00:02:59,670 --> 00:03:03,950 dimensional, we can't capture that with the linear projection. 58 00:03:03,950 --> 00:03:05,800 The other two panels in the bottom show 59 00:03:05,800 --> 00:03:09,130 different nonlinear dimensionality reduction methods, and they, actually, 60 00:03:09,130 --> 00:03:12,890 are capable of modeling and unfolding, this manifold 61 00:03:12,890 --> 00:03:16,460 to, in order to, represent the data adequately. 62 00:03:16,460 --> 00:03:19,960 And that's not what nonlinear dimensional introduction strategies are all about. 63 00:03:22,960 --> 00:03:25,010 So, some other examples of that. 64 00:03:25,010 --> 00:03:26,950 Here is a case using image data. 65 00:03:26,950 --> 00:03:29,730 We have just two axis of variation here. 66 00:03:29,730 --> 00:03:31,990 We're looking at a face from different angles. 67 00:03:31,990 --> 00:03:35,080 So the left right pose is one axis of variation. 68 00:03:35,080 --> 00:03:36,770 And the up down pause is another. 69 00:03:36,770 --> 00:03:39,430 Note that any two of these data points that are close to each 70 00:03:39,430 --> 00:03:42,290 other in this manifold are also going to be similar to each other. 71 00:03:42,290 --> 00:03:48,150 So the, this, it captures sort of a local structure around all data points and 72 00:03:48,150 --> 00:03:53,020 also captures the global structure that they're, these two main axis of variation. 73 00:03:53,020 --> 00:03:55,380 But it's a highly nonlinear relationship, naturally. 74 00:03:55,380 --> 00:03:58,710 And if you are to try and embed this in the space of pixel attributes, 75 00:03:58,710 --> 00:04:01,920 you'd get some highly folded structure probably, 76 00:04:01,920 --> 00:04:05,050 even though the manifold itself is continuous, right? 77 00:04:05,050 --> 00:04:08,070 because you could continuously move this camera around and 78 00:04:08,070 --> 00:04:11,250 get practically no change from between neighboring data points. 79 00:04:11,250 --> 00:04:14,100 So the local structure is smooth and continuous. 80 00:04:14,100 --> 00:04:18,710 But of course its a very complicated manifold and this is from early work in 81 00:04:18,710 --> 00:04:24,790 Isomap in order to identify structures using nonlineal dimensionality reduction. 82 00:04:24,790 --> 00:04:26,920 Here's another result from the same paper this is looking at 83 00:04:26,920 --> 00:04:31,360 handwritten digit recognition, so here we have lots of examples of twos. 84 00:04:31,360 --> 00:04:34,670 And you, you can imagine that these twos live on a manifold 85 00:04:34,670 --> 00:04:37,990 of, of different different manifestations of 86 00:04:37,990 --> 00:04:39,420 what a handwritten two should look like. 87 00:04:39,420 --> 00:04:43,000 Right, so if you change any one of these just a little bit, you move along the 88 00:04:43,000 --> 00:04:44,930 manifold to its neighbors, right, you're still on the 89 00:04:44,930 --> 00:04:47,430 manifold as long as it's still a valid two. 90 00:04:47,430 --> 00:04:51,610 And this just emphasizes the fact that these manifolds needn't fill the space. 91 00:04:51,610 --> 00:04:53,220 They aren't always rectangular sheets. 92 00:04:53,220 --> 00:04:57,110 You can have spikes and, and pseudopods that jut out like you see 93 00:04:57,110 --> 00:05:01,090 down there in the lower right, there's sort of a spike in this distribution. 94 00:05:01,090 --> 00:05:04,390 Representing this, the twos of the curly cues on the top. 95 00:05:04,390 --> 00:05:06,610 but, that said we can still sort of 96 00:05:06,610 --> 00:05:11,700 arbitrarily, apply ascribe different English titles to these axis. 97 00:05:11,700 --> 00:05:12,990 Here they've been called bottom loop 98 00:05:12,990 --> 00:05:17,240 articulation, and the top arch articulation axis. 99 00:05:17,240 --> 00:05:19,340 But really all we're trying to do is come up with 100 00:05:19,340 --> 00:05:23,700 some nonlinear structure to describe the universe of possible twos, right? 101 00:05:23,700 --> 00:05:26,580 Which is a highly non linear manifold in the original space. 102 00:05:27,700 --> 00:05:28,870 How do we represent this structure? 103 00:05:28,870 --> 00:05:32,970 Well, this, one way we can do this, there are lots of different 104 00:05:32,970 --> 00:05:34,660 ways, a, a lot of different nonlinear 105 00:05:34,660 --> 00:05:38,050 dimensionality reduction methods involve, looking at graphs, 106 00:05:38,050 --> 00:05:40,370 for instance, to find, local neighborhoods 107 00:05:40,370 --> 00:05:43,060 on graphs, but, kernel principal component analysis, 108 00:05:43,060 --> 00:05:46,140 which is the one we're going to be exploring most deeply in this talk. 109 00:05:46,140 --> 00:05:49,210 Relies on the intuition, that many, data 110 00:05:49,210 --> 00:05:51,540 sets which are not linearly separable in their 111 00:05:51,540 --> 00:05:54,230 original attributes, can be made linearly separable 112 00:05:54,230 --> 00:05:56,500 by projecting them into a higher dimensional space. 113 00:05:56,500 --> 00:05:58,600 That is, we can add attributes, which are 114 00:05:58,600 --> 00:06:01,830 simple arithmetic operations of the original attribute space. 115 00:06:01,830 --> 00:06:06,730 Which caused the data to become linearly separable in that it, new feature space. 116 00:06:06,730 --> 00:06:09,330 So here's an example where we have two, data points. 117 00:06:09,330 --> 00:06:12,990 This bullseye, data cloud has two classes. 118 00:06:12,990 --> 00:06:15,410 The red and the green, which are not linearly separable. 119 00:06:15,410 --> 00:06:18,610 Try as you might, you cannot draw a separating discriminate line, 120 00:06:18,610 --> 00:06:22,510 through that, or separating decision boundary, through that data point cloud. 121 00:06:22,510 --> 00:06:26,220 However when you add a third feature to the dataset which is the sum of 122 00:06:26,220 --> 00:06:30,090 squared attributes, then, the results become linearly separable 123 00:06:30,090 --> 00:06:32,320 as you see here in the three-dimensional portrayals. 124 00:06:32,320 --> 00:06:33,850 So, we're mapping this into a high 125 00:06:33,850 --> 00:06:36,630 dimensional space where linear relationships are sufficient. 126 00:06:36,630 --> 00:06:39,340 If you were to map that decision boundary that you make in this hard 127 00:06:39,340 --> 00:06:41,750 dimensional space back into the lower dimensional 128 00:06:41,750 --> 00:06:44,110 space, you get a nonlinear decision boundary. 129 00:06:44,110 --> 00:06:49,340 So, we can actually use all the tools from our linear analysis toolkit 130 00:06:49,340 --> 00:06:53,100 in the high dimensional space and get non linear results in the original space. 131 00:06:54,200 --> 00:06:58,210 This is an, an important an important insight, an important intuition, 132 00:06:58,210 --> 00:07:01,050 it is really the foundation of our Kernel principle component analysis. 133 00:07:02,150 --> 00:07:04,920 So, what does this look like for KPCA. 134 00:07:04,920 --> 00:07:07,630 Kernal PCA takes our training data, it maps it into some 135 00:07:07,630 --> 00:07:09,110 higher dimensional features based where 136 00:07:09,110 --> 00:07:12,050 we perform principal component analysis, right? 137 00:07:12,050 --> 00:07:15,040 Which in the original data space, it 138 00:07:15,040 --> 00:07:18,215 would represented as a nonlinear projection, right? 139 00:07:18,215 --> 00:07:20,640 A nonlinear transformation of the data. 140 00:07:20,640 --> 00:07:23,030 If we get some new data point then we can similarly 141 00:07:23,030 --> 00:07:26,130 project it into our higher dimensional feature space and find its 142 00:07:26,130 --> 00:07:30,550 low D representation in that new high dimensional feature space that's, 143 00:07:30,550 --> 00:07:34,050 that's, with projections that have been learned from our training data right? 144 00:07:34,050 --> 00:07:35,670 So this is the intuition behind KPCA. 145 00:07:36,940 --> 00:07:39,520 But you might say this is fine but it's 146 00:07:39,520 --> 00:07:43,200 kind of contrary to the whole point of dimensionality reduction right? 147 00:07:43,200 --> 00:07:46,100 If we're creating these arbitrary new high dimensional feature 148 00:07:46,100 --> 00:07:48,970 spaces doesn't that actually increase rather than reduce the dimensions. 149 00:07:48,970 --> 00:07:54,075 It's true it would except we also have the benefit that for 150 00:07:54,075 --> 00:07:59,380 KPCA you don't actually have to do any calculations in the high 151 00:08:02,980 --> 00:08:06,890 dimensional feature space and I will describe that in a moment. 152 00:08:06,890 --> 00:08:07,200 The derivation of Kernel PCA follows our PCA. 153 00:08:07,200 --> 00:08:10,599 So we now take some mapping of the original data set which is Phi. 154 00:08:10,599 --> 00:08:15,570 So Phi of X sub i is the, the mapped data point in this high dimensional space. 155 00:08:15,570 --> 00:08:18,170 And we envision some projection in this high dimensional space. 156 00:08:18,170 --> 00:08:20,040 That's here represented by the set of 157 00:08:20,040 --> 00:08:22,910 orthonormal base inspectors in the matrix U, right? 158 00:08:22,910 --> 00:08:28,200 And the expression here U times U transposed, it times Phi of, of 159 00:08:28,200 --> 00:08:33,360 X sub i, gives us the reconstruction of the data point, Phi of 160 00:08:33,360 --> 00:08:39,070 XLi after, down projecting it through this linear basis, right? 161 00:08:39,070 --> 00:08:44,115 So we subtract the original data points, in the high dimensional feature space from 162 00:08:44,115 --> 00:08:45,990 its reconstruction in that high dimensional feature 163 00:08:45,990 --> 00:08:47,970 space and we get an error score, right? 164 00:08:47,970 --> 00:08:51,560 So we're trying to minimize reconstruction error in this high dimensional space. 165 00:08:52,850 --> 00:08:54,820 Note that for this expression, it's actually 166 00:08:54,820 --> 00:08:57,947 important that the data set Phi be centered. 167 00:08:57,947 --> 00:09:02,070 Similarly to regular PCA, where we're working with zero mean data. 168 00:09:02,070 --> 00:09:04,370 We had to subtract the mean off first. 169 00:09:04,370 --> 00:09:05,640 Here as well we're going to be working with 170 00:09:05,640 --> 00:09:07,680 data that is centered in the high dimensional space. 171 00:09:10,020 --> 00:09:11,690 All right, so, this is equivalent. 172 00:09:11,690 --> 00:09:14,240 I mentioned the, previously the relationship between singular value 173 00:09:14,240 --> 00:09:16,928 decomposition and PCA, so the same thing applies here. 174 00:09:16,928 --> 00:09:18,350 We can actually do a singular value 175 00:09:18,350 --> 00:09:24,280 decomposition, of the, high dimensional features, or, the 176 00:09:24,280 --> 00:09:29,350 high dimensional dataset, Phi sub X, and that gives us our basis vector as U. 177 00:09:29,350 --> 00:09:32,700 So, we define U to be the left singular vectors of Phi sub 178 00:09:32,700 --> 00:09:38,590 X, associated with the highest singular values in this matrix of singular values, 179 00:09:40,690 --> 00:09:41,430 sigma. 180 00:09:41,430 --> 00:09:45,580 All right, so equivalently, right just as in our previous PCA example where there is 181 00:09:45,580 --> 00:09:48,650 an equivalence between SVD and calculating the eigenvectors 182 00:09:48,650 --> 00:09:51,090 of the covariance matrix, the sample covariance matrix. 183 00:09:51,090 --> 00:09:55,290 We can calculate the eigenvectors of the sample covariance matrix of 184 00:09:55,290 --> 00:09:59,340 Phi sub X, which is a bunch of dot products essentially. 185 00:09:59,340 --> 00:10:02,090 And again this has to be the, the eigenvectors 186 00:10:02,090 --> 00:10:04,050 of the, the centered matrix as in, in PCA. 187 00:10:07,440 --> 00:10:10,060 Okay this, this brings me to the kernel trick. 188 00:10:10,060 --> 00:10:15,400 So as before we can work with this, as before P, PCA 189 00:10:15,400 --> 00:10:20,200 relies on the eigenvectors of the sample covariance matrix X times X transpose. 190 00:10:20,200 --> 00:10:25,060 And we can represent that in the projected space by a matrix of dot products, right? 191 00:10:25,060 --> 00:10:26,930 And the expression for that is given here. 192 00:10:26,930 --> 00:10:29,170 So what this means is we can implicitly 193 00:10:29,170 --> 00:10:33,140 model any nonlinear transformation, Phi of, of X. 194 00:10:33,140 --> 00:10:35,790 The only requirement is that have to be able 195 00:10:35,790 --> 00:10:38,670 to calculate dot products between those data points efficiently. 196 00:10:38,670 --> 00:10:39,950 We can, as long as we know the dot 197 00:10:39,950 --> 00:10:43,390 products, we can figure out what the projected representation is. 198 00:10:43,390 --> 00:10:45,760 So we actually never have to calculate the explicit 199 00:10:45,760 --> 00:10:48,810 represent, high dimensional representation of the new feature space. 200 00:10:50,680 --> 00:10:52,240 So that, typically the way this is done 201 00:10:52,240 --> 00:10:54,090 in kernel methods, this is known as the kernel 202 00:10:54,090 --> 00:10:56,630 trick, is to come up with a kernel matrix 203 00:10:56,630 --> 00:10:59,440 of dot products between all the different data points, 204 00:10:59,440 --> 00:11:01,970 and, so we describe here the dot product 205 00:11:01,970 --> 00:11:06,550 using the kernel function K, which represents point similarity, 206 00:11:06,550 --> 00:11:09,990 in this high dimensional space or similarity in the 207 00:11:09,990 --> 00:11:13,760 attribute space, which equates to their dot product, right? 208 00:11:13,760 --> 00:11:18,980 So this is different, this is slightly different than PCA. 209 00:11:18,980 --> 00:11:21,200 Where as PCA has a covariance matrix that's 210 00:11:21,200 --> 00:11:23,540 scaled with the number of input dimensions n. 211 00:11:23,540 --> 00:11:26,420 Here we're working in KPCA with this kernel matrix 212 00:11:26,420 --> 00:11:30,750 that, is, has, dimensions similar, it's dimension according to the 213 00:11:30,750 --> 00:11:32,850 size of our dataset, right, because we're calculating the 214 00:11:32,850 --> 00:11:35,140 dot product of all data points against all the others. 215 00:11:35,140 --> 00:11:38,970 So this scales with D, the number of data points in our training set. 216 00:11:40,760 --> 00:11:42,150 What kernel function should we use? 217 00:11:42,150 --> 00:11:43,780 How do we calculate these dot products? 218 00:11:43,780 --> 00:11:47,620 Well a common method is just to look at a local, some 219 00:11:47,620 --> 00:11:51,260 sort of decreasing function of distance in the original feature space, right? 220 00:11:51,260 --> 00:11:54,700 A typical choice a typical choice is the Gaussian kernel. 221 00:11:54,700 --> 00:11:57,030 We introduced this way back in the first lecture, 222 00:11:57,030 --> 00:11:59,490 right, as, as a way to describe locality between 223 00:11:59,490 --> 00:12:02,410 data points that has a width parameter h that 224 00:12:02,410 --> 00:12:05,420 we can set using cross validation, if we like. 225 00:12:05,420 --> 00:12:08,520 And this falls off rapidly, as distance increases. 226 00:12:08,520 --> 00:12:10,365 So we can apply this to every, to 227 00:12:10,365 --> 00:12:12,110 para-wise to all of the different data points 228 00:12:12,110 --> 00:12:15,210 and figure out what their, it what their 229 00:12:15,210 --> 00:12:17,430 dot products are, in this high dimensional space. 230 00:12:17,430 --> 00:12:19,200 So we're describing a functional form to their 231 00:12:19,200 --> 00:12:22,130 dot products which let's us calculate this nonlinear projection. 232 00:12:24,890 --> 00:12:27,240 Okay so, there's a catch. 233 00:12:27,240 --> 00:12:29,770 I mentioned before that our data set has 234 00:12:29,770 --> 00:12:33,770 to be centered in this high-dimensional feature representation. 235 00:12:33,770 --> 00:12:34,910 That it has to be zero mean. 236 00:12:34,910 --> 00:12:40,230 And this won't be the case for a general kernel matrix that we derive. 237 00:12:40,230 --> 00:12:42,600 What this really means is that we want to come up 238 00:12:42,600 --> 00:12:47,050 with some feature, I'm sorry, some data point, some projected data point. 239 00:12:47,050 --> 00:12:49,850 We'll call this Phi tilde of X sub i. 240 00:12:49,850 --> 00:12:55,210 Which is the original Phi of X sub i minus the mean of all of the fees. 241 00:12:55,210 --> 00:12:58,770 And you can actually push this through some algebra, to figure out 242 00:12:58,770 --> 00:13:01,780 what its implementation, implications will be for the kernel matrix as a whole. 243 00:13:01,780 --> 00:13:05,968 So, with the kernel matrix elements defined as the dot products. 244 00:13:05,968 --> 00:13:08,648 So our Phi, of X sub i and X 245 00:13:08,648 --> 00:13:12,560 sub j, we then perform that substitution from the top 246 00:13:12,560 --> 00:13:16,600 line and it actually works out to some simple arithmetic 247 00:13:16,600 --> 00:13:21,110 operations on the kernel matrix that perform this centering operation. 248 00:13:21,110 --> 00:13:24,830 So sparing, I, I won't walk you through the gory details 249 00:13:24,830 --> 00:13:27,740 but it basically amounts to this, this operation that we have to 250 00:13:27,740 --> 00:13:31,680 perform on the kernel matrix after calculating the kernel function of all 251 00:13:31,680 --> 00:13:34,330 data points in order to center it before we can do STD. 252 00:13:34,330 --> 00:13:34,830 All 253 00:13:37,650 --> 00:13:40,110 right, so here's the from beginning to end, 254 00:13:40,110 --> 00:13:43,450 the, the recipe for Kernel Principle Component Analysis. 255 00:13:43,450 --> 00:13:45,070 First thing to do is pick a kernel function. 256 00:13:45,070 --> 00:13:47,750 I hardly recommend that we start with the Gaussian. 257 00:13:47,750 --> 00:13:49,240 There are lots of other kernel functions and a 258 00:13:49,240 --> 00:13:52,790 whole literature devoted to defining different kernel functions for different 259 00:13:52,790 --> 00:13:55,470 kinds of input spaces so I encourage you to look 260 00:13:55,470 --> 00:13:59,030 into that if, if it's a topic that interests you. 261 00:13:59,030 --> 00:14:02,050 After you have a kernel function, you can calculate the kernel matrix. 262 00:14:02,050 --> 00:14:05,305 And then center it according to that expression that I showed you before. 263 00:14:05,305 --> 00:14:10,340 Here I have written down the matrix notation with, the ones indicating just a 264 00:14:10,340 --> 00:14:14,520 matrix with entries of one over d where d is the number of data points. 265 00:14:14,520 --> 00:14:16,700 All right, so that's it, it fairly straight forward. 266 00:14:16,700 --> 00:14:21,575 Center an operation and then you solve the eigenproblem, which is again this 267 00:14:21,575 --> 00:14:24,280 eigensystem based on the kernel matrix, which 268 00:14:24,280 --> 00:14:27,430 gives us our projections alpha, and then 269 00:14:27,430 --> 00:14:30,410 alpha is of course the size of all of our data points in the 270 00:14:30,410 --> 00:14:34,910 training set so in order to find the projection of a new data point. 271 00:14:34,910 --> 00:14:38,300 We multiply the alpha by its kernel evaluation for all of 272 00:14:38,300 --> 00:14:41,190 the data points in the training data with respect to the 273 00:14:41,190 --> 00:14:43,740 query point that we're trying to project and that gives us 274 00:14:43,740 --> 00:14:49,140 the location along some new dimension for the projected data point. 275 00:14:51,635 --> 00:14:54,000 Okay, so here's an example of what it looks like in practice. 276 00:14:54,000 --> 00:14:58,070 So we've taken the face dataset and down-projected it with PCA first. 277 00:14:58,070 --> 00:15:02,000 So this is a purely linear projection of that, that face dataset before. 278 00:15:02,000 --> 00:15:05,810 This is courtesy of go, Ghodsi, in 2006. 279 00:15:05,810 --> 00:15:09,770 You'll note that there are lots of places where, neighboring faces have 280 00:15:09,770 --> 00:15:12,000 actually, neighboring points in this dataset 281 00:15:12,000 --> 00:15:14,060 have actually very different images right. 282 00:15:14,060 --> 00:15:18,000 So this doesn't necessarily do a good job of, of capturing the underlying structure. 283 00:15:18,000 --> 00:15:19,520 We can do better with KPCA. 284 00:15:19,520 --> 00:15:22,370 Now, this isn't a perfect unfolding of the manifold, right? 285 00:15:22,370 --> 00:15:25,530 It doesn't totally fill the space with a beautiful rectangle, right? 286 00:15:25,530 --> 00:15:29,160 But that's not, that rarely happens in practice actually. 287 00:15:29,160 --> 00:15:33,190 And this is actually pretty, a pretty good result in that neighboring data points 288 00:15:33,190 --> 00:15:36,920 also represent similar images, as you can see from the examples that are plotted. 289 00:15:36,920 --> 00:15:39,390 So this actually does a much better job. 290 00:15:39,390 --> 00:15:42,750 For this, day, face dataset than, than a purely linearly 291 00:15:42,750 --> 00:15:46,170 projection would, as long as we're working with just two dimensions. 292 00:15:46,170 --> 00:15:50,000 So Kernel PCA, nonlinear dimensionality reduction is a more 293 00:15:50,000 --> 00:15:52,610 efficient method in this case of representing the data. 294 00:15:54,990 --> 00:15:59,335 Other methods for nonlinear dimensionality reduction, and indeed there are a bunch. 295 00:15:59,335 --> 00:16:01,140 Kernel PCA is a common one. 296 00:16:01,140 --> 00:16:03,740 But there are lots of others based on graph structure like I mentioned. 297 00:16:03,740 --> 00:16:06,040 Laplacian Eigenmaps are an example of that. 298 00:16:06,040 --> 00:16:10,530 It's a sot of Local Liner Embedding is another case. 299 00:16:10,530 --> 00:16:14,320 Isomap is a, a famous algorithm that has been around for a decade now. 300 00:16:14,320 --> 00:16:16,720 Multidimensional Scaling is a classic algorithm 301 00:16:16,720 --> 00:16:19,110 that takes a, a matrix of affinities 302 00:16:19,110 --> 00:16:22,130 which in some way similar to the kernel matrix that I described before. 303 00:16:22,130 --> 00:16:24,610 And creates a, a low dimensional projection that 304 00:16:24,610 --> 00:16:27,890 preserves those, those offendee values, those distance values. 305 00:16:27,890 --> 00:16:32,470 Feedforward Autoencoders are kind of an exotic approach that's actually gained 306 00:16:32,470 --> 00:16:35,270 a lot of attraction of late in the deep learning community. 307 00:16:35,270 --> 00:16:37,710 So, this is based on neural network modeling. 308 00:16:37,710 --> 00:16:39,900 And, again, that's something that I encourage you to 309 00:16:39,900 --> 00:16:43,570 investigate further if, If neural networks are of interest. 310 00:16:43,570 --> 00:16:47,180 Feedforward Autoencoders can be used to perform Nonlinear Dimensionality Reduction 311 00:16:48,190 --> 00:16:50,040 irrespective of the ultimate classification 312 00:16:50,040 --> 00:16:52,332 goal of the, the neural network. 313 00:16:52,332 --> 00:16:53,480 All right, and of course there are, there 314 00:16:53,480 --> 00:16:55,620 are many more strategies and a huge literature 315 00:16:55,620 --> 00:16:58,140 on nonlinear dimensionality reduction, but I hope I've 316 00:16:58,140 --> 00:16:59,549 given you a pretty good taste with this lecture. 317 00:17:00,820 --> 00:17:05,270 Okay, so one, note in closing, nonlinear dimensionality 318 00:17:05,270 --> 00:17:08,010 reduction doesn't always work better than the linear case. 319 00:17:08,010 --> 00:17:10,180 And it does work well when you have a lot of data, when you 320 00:17:10,180 --> 00:17:15,180 can fill the manifold and, you don't have a lot of gaps or, or outliers. 321 00:17:15,180 --> 00:17:17,710 It works pretty well and the intrinsic dimensionality is relatively 322 00:17:17,710 --> 00:17:20,740 low and your data is pretty evenly distributed on the manifold. 323 00:17:20,740 --> 00:17:22,460 If you don't have a lot of data then 324 00:17:22,460 --> 00:17:26,590 some simpler structure is generally going to give you better results. 325 00:17:26,590 --> 00:17:29,470 Occasionally nonlinear dimensionality reduction strategies can 326 00:17:29,470 --> 00:17:31,900 give you degenerate solutions or they 327 00:17:31,900 --> 00:17:36,040 can be unstable, and, and this is just goes with the territory. 328 00:17:36,040 --> 00:17:38,110 When you have a more flexible model right, you 329 00:17:38,110 --> 00:17:40,530 need more data in order to fit it adequately. 330 00:17:40,530 --> 00:17:43,720 So this is just a general caveat to keep in mind. 331 00:17:43,720 --> 00:17:47,190 I would always start with linear dimensionality reduction strategies to 332 00:17:47,190 --> 00:17:51,030 see if they're sufficient for your classification or visualization task. 333 00:17:51,030 --> 00:17:53,400 And only pull out nonlinear dimensionality reduction 334 00:17:53,400 --> 00:17:55,690 when it turns out to be absolutely necessary. 335 00:17:55,690 --> 00:17:59,610 It's particularly helpful in a lot of cases like image data, where you have 336 00:17:59,610 --> 00:18:03,930 smooth transitions, right, from one frame to the next, or in pose estimation, where 337 00:18:03,930 --> 00:18:06,260 you have like say an articulated body 338 00:18:06,260 --> 00:18:09,570 that's moving and can define relatively simple 339 00:18:09,570 --> 00:18:11,750 low dimensional manifolds in that space consisting 340 00:18:11,750 --> 00:18:14,050 of different poses and joint limb articulations. 341 00:18:14,050 --> 00:18:15,990 So there are some sort of cottage industries 342 00:18:15,990 --> 00:18:19,650 where these nonlinear representations which will become really 343 00:18:19,650 --> 00:18:26,070 useful, but if you have some brand new data set then start with the linear, okay. 344 00:18:26,070 --> 00:18:29,860 So in summary methods like KPCA can find 345 00:18:29,860 --> 00:18:33,760 non linear by projecting data into high dimensional spaces. 346 00:18:33,760 --> 00:18:35,950 And then applying the same linear tool kit 347 00:18:35,950 --> 00:18:41,010 from PCA, in those in, those implicit spaces. 348 00:18:41,010 --> 00:18:43,570 And you can avoid the cost of this calculation with the kernel trick. 349 00:18:43,570 --> 00:18:46,180 That is computations based on dot products which are 350 00:18:46,180 --> 00:18:48,430 represented by a kernel function that you can define.