1 00:00:00,470 --> 00:00:02,738 My name's David Thompson and this is the 2 00:00:02,738 --> 00:00:06,241 second lecture in a series on dimensionality reduction. 3 00:00:06,241 --> 00:00:09,857 In the first lecture I described some local methods for pattern recognition 4 00:00:09,857 --> 00:00:12,343 which include nearest neighbor approaches and 5 00:00:12,343 --> 00:00:14,886 locally linear regression among other things. 6 00:00:14,886 --> 00:00:16,813 This is where,this is the lecture where we 7 00:00:16,813 --> 00:00:19,562 really start to get into dimensionality reduction proper. 8 00:00:19,562 --> 00:00:21,810 I'm going to talk about what happens as 9 00:00:21,810 --> 00:00:24,090 we start going into higher dimensional spaces. 10 00:00:24,090 --> 00:00:28,060 From those simple examples that I showed you before and in 11 00:00:28,060 --> 00:00:31,280 particular I'll introduce a concept known as the curse of dimensionality, 12 00:00:31,280 --> 00:00:34,550 which is a perennial challenge for all sorts of pattern recognition 13 00:00:34,550 --> 00:00:36,510 problems so it's something that you all should be aware of. 14 00:00:36,510 --> 00:00:37,130 And know how to solve. 15 00:00:37,130 --> 00:00:40,430 All right, so the objectives of this lecture are 16 00:00:40,430 --> 00:00:42,910 to, one, know how to find nearest neighbors efficiently. 17 00:00:42,910 --> 00:00:45,740 This is something that I really glossed over in the last slides. 18 00:00:45,740 --> 00:00:47,370 But as we start moving away from toy 19 00:00:47,370 --> 00:00:51,070 examples this question will become more and more important. 20 00:00:51,070 --> 00:00:55,440 The notion of how to, how to perform these calculation in an efficient manner. 21 00:00:55,440 --> 00:00:58,730 At because in, in lotta cases the naive approach really doesn't work very well. 22 00:00:58,730 --> 00:01:01,670 The second objective is to understand the curse of dimensionality. 23 00:01:01,670 --> 00:01:02,000 What is it? 24 00:01:02,000 --> 00:01:05,940 It sounds pretty ominous, and in fact it is of, like I said, it's, it's 25 00:01:05,940 --> 00:01:08,580 a real challenge for a lot of, for 26 00:01:08,580 --> 00:01:11,130 scaling up these approaches to higher dimensional spaces. 27 00:01:11,130 --> 00:01:14,240 So you should know it's implications for pattern recognition. 28 00:01:14,240 --> 00:01:16,754 And I'll also start I'll wet your appetite with some 29 00:01:16,754 --> 00:01:19,641 idea of the general approaches that we'll use in later lectures. 30 00:01:19,641 --> 00:01:22,889 To solve the curse of dimensionality. 31 00:01:22,889 --> 00:01:26,702 Okay, as a review local pattern recognition involves 32 00:01:26,702 --> 00:01:30,191 inferring something about the process that generated the data 33 00:01:30,191 --> 00:01:32,755 or some underlying function of the data by 34 00:01:32,755 --> 00:01:35,728 looking in the local vicinity of your query point. 35 00:01:35,728 --> 00:01:38,870 Examples are K-nearest neighbor classification local 36 00:01:38,870 --> 00:01:41,600 linear regression, and Kernel density estimation. 37 00:01:41,600 --> 00:01:45,680 These all rely on the ability to find these nearest neighbors fairly quickly. 38 00:01:45,680 --> 00:01:50,550 Or maybe, beyond nearest neighbors, the notion of a range query, that is, finding 39 00:01:50,550 --> 00:01:52,930 points within a certain radius of your, 40 00:01:52,930 --> 00:01:55,180 your query point, which is a related problem. 41 00:01:55,180 --> 00:01:58,530 But in general, we're going to have to find a lot of nearest neighbors in data 42 00:01:58,530 --> 00:02:03,522 sets that could be as large as hundreds of thousands or even millions of data points. 43 00:02:03,522 --> 00:02:04,830 All right, so this is the case where we're 44 00:02:04,830 --> 00:02:07,870 looking for nearest neighbors with a one dimensional data site. 45 00:02:07,870 --> 00:02:11,360 Here I've shown you the entire data set X. 46 00:02:11,360 --> 00:02:13,210 Right, which contains just a single attribute. 47 00:02:13,210 --> 00:02:16,520 Right so a single numerical input attribute. 48 00:02:16,520 --> 00:02:19,650 And we have a new data point which is here four. 49 00:02:19,650 --> 00:02:22,400 And we're trying to find its nearest neighbor in this data set. 50 00:02:22,400 --> 00:02:25,750 So the question is how do I do that efficiently? 51 00:02:25,750 --> 00:02:29,620 And the standard sort of naive approach to doing this would simply be to take the 52 00:02:29,620 --> 00:02:35,050 four, and march down this list of data points and compare it to each one in turn. 53 00:02:35,050 --> 00:02:38,420 Keeping track of the closest neighbor that I found so far. 54 00:02:38,420 --> 00:02:42,000 So when I reach the end of the list then I'll 55 00:02:42,000 --> 00:02:45,380 absolutely know with certainty the closest neighbor in the data set. 56 00:02:46,570 --> 00:02:51,640 Unfortunately this this sequential search actually takes linear time to accomplish 57 00:02:51,640 --> 00:02:56,290 which means it's not that tractable computationally for very large data sets. 58 00:02:56,290 --> 00:02:57,770 The, the time required, the number of 59 00:02:57,770 --> 00:03:01,000 comparisons grows proportionally with the number of data 60 00:03:01,000 --> 00:03:05,570 points, so if you get up to data sets containing say a million data points. 61 00:03:05,570 --> 00:03:07,640 This will be pretty onerous to perform. 62 00:03:07,640 --> 00:03:13,550 It'll be particularly challenging if we have to do this as an inside loop in some 63 00:03:13,550 --> 00:03:15,990 of the larger pattern recognition process, like say 64 00:03:15,990 --> 00:03:18,740 cross validation or a change in chrono hits. 65 00:03:18,740 --> 00:03:22,060 We may have to try this once for every data point, in which case 66 00:03:22,060 --> 00:03:23,930 the total complexity of the algodon would 67 00:03:23,930 --> 00:03:27,050 scale polynomially with the number of data points. 68 00:03:27,050 --> 00:03:30,280 So that would be you know, a million times a million, and that's 69 00:03:30,280 --> 00:03:32,670 a, that's a lot of, of calculations that you might have to do. 70 00:03:32,670 --> 00:03:35,570 So this quickly becomes untractable and we need to find some 71 00:03:35,570 --> 00:03:39,740 more efficient way in order to generalize nearest neighbor to higher dimensions. 72 00:03:41,110 --> 00:03:43,940 Or to, or rather to larger numbers of, of data points. 73 00:03:43,940 --> 00:03:45,940 So in the 1D case there's a straight 74 00:03:45,940 --> 00:03:48,290 forward approach which is to sort the list, right? 75 00:03:48,290 --> 00:03:53,030 So, you can presume that we have some sort of strategy, some sorting algorithm, that 76 00:03:53,030 --> 00:03:58,800 will, in sub-linear time, let us sort the list into an ordered set of data points. 77 00:03:58,800 --> 00:04:00,370 And indeed these algorithms exist. 78 00:04:01,400 --> 00:04:04,410 So, after we've sorted the list into our new 79 00:04:04,410 --> 00:04:08,020 representation in our, in the computer memory, X prime,. 80 00:04:08,020 --> 00:04:12,030 Then we can actually search this space more efficiently. 81 00:04:12,030 --> 00:04:15,780 In, in fact the, the standard way of doing this is called a, a binary search. 82 00:04:15,780 --> 00:04:20,310 So we take our, our query point and look at the, the midpoint in the sorted list. 83 00:04:20,310 --> 00:04:22,240 And ask, is it greater than or smaller than this? 84 00:04:22,240 --> 00:04:25,180 And, how close are we to that, to that nearest neighbor? 85 00:04:25,180 --> 00:04:28,560 so, or, to that, to that point in the dataset. 86 00:04:28,560 --> 00:04:33,810 And based on the answer to our query, we can go left or right up and descend 87 00:04:33,810 --> 00:04:36,220 down this, this what amounts to a branching tree 88 00:04:36,220 --> 00:04:39,450 of, of decisions, bifurcating the list at each time. 89 00:04:39,450 --> 00:04:41,800 Until we arrive at a neighborhood of points that are more or 90 00:04:41,800 --> 00:04:45,020 less, in this case, they're more or less equidistant from our, our query. 91 00:04:45,020 --> 00:04:47,120 Note that in just three comparisons here, we've, 92 00:04:47,120 --> 00:04:49,430 we've already established the nearest neighbors of this point. 93 00:04:49,430 --> 00:04:53,390 There are, that is equidistant from between points three and five. 94 00:04:53,390 --> 00:04:56,750 Whereas before we would've potentially had to make you know, ten 95 00:04:56,750 --> 00:05:00,300 or, or 20 different comparisons, to arrive at that same decision. 96 00:05:00,300 --> 00:05:02,900 The, the real advantage is the, the scaling property. 97 00:05:02,900 --> 00:05:05,510 Because we can eliminate half of the data set. 98 00:05:05,510 --> 00:05:08,570 With every query that we perform, it scales with Lawburn 99 00:05:08,570 --> 00:05:11,140 Neck time which makes it tractable for large data sets. 100 00:05:11,140 --> 00:05:14,870 So it's a more efficient way of, of doing the same, the same operation. 101 00:05:14,870 --> 00:05:16,410 So this is the Wendy case. 102 00:05:16,410 --> 00:05:20,430 So, how would we perform nearest neighbors efficiently in higher dimensional spaces? 103 00:05:20,430 --> 00:05:22,800 Well, it's not immediately obvious what the higher 104 00:05:22,800 --> 00:05:26,310 dimensional analog to the sorted list would be. 105 00:05:26,310 --> 00:05:30,100 But fortunately researchers in the computer [UNKNOWN] literature 106 00:05:30,100 --> 00:05:31,880 have dealt with this problem for a long time. 107 00:05:31,880 --> 00:05:35,210 They've come up with a wide range of data structures that 108 00:05:35,210 --> 00:05:38,600 will help us do efficient nearest neighbor queries in high dimensional cases. 109 00:05:38,600 --> 00:05:41,020 And I'll show you one of the most common ones on the next slide. 110 00:05:41,020 --> 00:05:45,120 All right, so this is the, the, K-D Tree which works pretty 111 00:05:45,120 --> 00:05:48,710 well from anywhere two to eight dimensions of the, of the inputs space. 112 00:05:48,710 --> 00:05:54,126 And the idea is to take your data, to take your data set, and arrange it such that 113 00:05:54,126 --> 00:05:57,000 it's lies in a tree structure, here at left, 114 00:05:57,000 --> 00:06:00,850 where each node splits the space with a hyperplane, right? 115 00:06:00,850 --> 00:06:02,730 And half of the, and the points on one side of the 116 00:06:02,730 --> 00:06:06,400 hyperplane constitute half the data set, and the remaining half of the data 117 00:06:06,400 --> 00:06:09,340 set goes on the other side of the hyperplane, which lets us eliminate 118 00:06:09,340 --> 00:06:13,080 at each step, at each query point, about half of the data set. 119 00:06:14,600 --> 00:06:16,410 now, which hyperplane do you use? 120 00:06:16,410 --> 00:06:18,710 Well, the most common choice to this, is 121 00:06:18,710 --> 00:06:21,160 to cycle through the attributes one at a time. 122 00:06:21,160 --> 00:06:23,050 So you start, and just split the data set 123 00:06:23,050 --> 00:06:25,940 along the first attribute just like a regular sorted list. 124 00:06:25,940 --> 00:06:28,640 And then, in the second level of the tree, the 125 00:06:28,640 --> 00:06:31,558 second tier of the hierarchy, you'd split on the next attribute. 126 00:06:31,558 --> 00:06:33,550 And simply continue cycling through until you reach the 127 00:06:33,550 --> 00:06:35,660 end of the attributes and then start cycling again. 128 00:06:35,660 --> 00:06:38,888 And this it can be depicted graphically here, at 129 00:06:38,888 --> 00:06:41,270 right, we have a data set of 6 points. 130 00:06:41,270 --> 00:06:43,672 And I've shown them, plotted them in 131 00:06:43,672 --> 00:06:46,160 two dimensional space together with the different splits. 132 00:06:46,160 --> 00:06:48,490 So our first split is along that point A, that 133 00:06:48,490 --> 00:06:52,270 bifurcates the data neatly into two halves along the X-axis. 134 00:06:52,270 --> 00:06:57,820 And then the next stage of the tree is the, the B points, right, which 135 00:06:57,820 --> 00:07:02,970 bifurcate the data their respective data sets along the Y-axis and it continues on. 136 00:07:02,970 --> 00:07:07,540 And using the strategy we can perform queries efficiently by eliminating 137 00:07:07,540 --> 00:07:10,560 half the data sets at each stage of, of the tree. 138 00:07:10,560 --> 00:07:14,580 So, exactly the same computation benefits that we get from the sorted list. 139 00:07:14,580 --> 00:07:15,880 But here in, in two dimensions. 140 00:07:15,880 --> 00:07:18,950 So, our typical search is order and log in. 141 00:07:18,950 --> 00:07:22,570 the, the computational properties tend to degrade at around six to eight 142 00:07:22,570 --> 00:07:26,260 dimensions when it starts to look less efficient for newest neighbor queries. 143 00:07:26,260 --> 00:07:29,300 And for that, we'll need more sophisticated algorithms. 144 00:07:29,300 --> 00:07:33,370 But typically, the K-D Trees are the first tool that, in a toolbox that I reach for. 145 00:07:33,370 --> 00:07:36,830 For nearest neighbor queries, in the range of two to eight dimensions. 146 00:07:36,830 --> 00:07:39,460 They can also be used for things like range 147 00:07:39,460 --> 00:07:41,300 queries, if you want to find all of the points in 148 00:07:41,300 --> 00:07:43,680 a data set that are within a certain range 149 00:07:43,680 --> 00:07:46,100 of target points, then they can do that as well. 150 00:07:46,100 --> 00:07:49,430 And there exists lots of good efficient implementations available 151 00:07:49,430 --> 00:07:52,400 that I hardly encourage you to avail yourself of. 152 00:07:52,400 --> 00:07:55,130 All right, so for higher dimensions it, it, one 153 00:07:55,130 --> 00:07:59,240 typically uses an approximate nearest neighbor strategy so this, 154 00:07:59,240 --> 00:08:00,930 this works for as many as a dozen or 155 00:08:00,930 --> 00:08:05,480 more dimensions they base, the basic idea is to leverage 156 00:08:05,480 --> 00:08:07,310 the fact that, well for, for many of these 157 00:08:07,310 --> 00:08:10,220 data sets we're most interested in an approximate nearest 158 00:08:10,220 --> 00:08:12,250 neighbor is almost as good as the actual nearest 159 00:08:12,250 --> 00:08:15,280 neighbor so if we're willing to sacrifice those hard guarantees. 160 00:08:15,280 --> 00:08:19,560 That will find the exact response to our query but are, are okay 161 00:08:19,560 --> 00:08:23,060 with a little bit of error within some epsilon value that we define. 162 00:08:23,060 --> 00:08:25,200 Then an approximate nearest neighbor calculation 163 00:08:25,200 --> 00:08:26,810 can, can get some more results. 164 00:08:26,810 --> 00:08:29,810 And so this, this tends to work better above eight to ten dimensions. 165 00:08:29,810 --> 00:08:33,300 And again many refined implementations exist 166 00:08:33,300 --> 00:08:35,950 in lots of different programming languages. 167 00:08:35,950 --> 00:08:39,320 All right so now I want to go on to to talk about 168 00:08:39,320 --> 00:08:45,840 when some of these methods even failed be, beyond 15 or 20 dimensions. 169 00:08:45,840 --> 00:08:49,230 There are lots of cases where nearest neighbor methods just don't work 170 00:08:49,230 --> 00:08:51,390 for other reasons and that involves 171 00:08:51,390 --> 00:08:53,100 something known as the cursive dimensionality. 172 00:08:55,910 --> 00:08:58,050 A more fundamental problem is, is, when, 173 00:08:58,050 --> 00:09:00,040 when is the nearest neighbor meaningful at all? 174 00:09:00,040 --> 00:09:00,610 Right? 175 00:09:00,610 --> 00:09:04,610 And you can quite easily construct cases where, or data sets, that 176 00:09:04,610 --> 00:09:06,610 are sort of pathological, where nearest 177 00:09:06,610 --> 00:09:08,510 neighbor queries really don't make much sense. 178 00:09:08,510 --> 00:09:09,550 And this is, this is one. 179 00:09:09,550 --> 00:09:12,900 So we have a, a query point X in the center of our data cloud. 180 00:09:12,900 --> 00:09:15,980 Not that the, our training data, which are here represented as Os, 181 00:09:15,980 --> 00:09:20,580 are all more or less equidistant from our query point X right. 182 00:09:20,580 --> 00:09:22,160 So the fact that we go with one 183 00:09:22,160 --> 00:09:25,050 nearest neighbor or another is really sort of arbitrary. 184 00:09:25,050 --> 00:09:27,770 That the structure, whatever structure is present in the 185 00:09:27,770 --> 00:09:30,750 data, really won't be captured by nearest neighbor query. 186 00:09:30,750 --> 00:09:36,020 It will be very sensitive to the precise location of X in the input space. 187 00:09:36,020 --> 00:09:38,900 And you can say, well, this is a strange, crazy example, right? 188 00:09:38,900 --> 00:09:40,360 This would never happen in practice. 189 00:09:40,360 --> 00:09:42,500 But in the next couple of slides, I'm going to 190 00:09:42,500 --> 00:09:45,030 show that for actually, for very high dimensional spaces 191 00:09:45,030 --> 00:09:48,150 that is above a couple of dozen dimensions, every 192 00:09:48,150 --> 00:09:51,110 pattern recognition problems starts to look exactly like this example. 193 00:09:52,400 --> 00:09:52,560 Right. 194 00:09:52,560 --> 00:09:55,390 Which means that the entire toolbox of the local pattern recognition 195 00:09:55,390 --> 00:09:59,010 methods that we've established, won't work for these higher dimensional spaces. 196 00:10:01,760 --> 00:10:04,191 One way to show this is to look at the volume of an N-Ball. 197 00:10:04,191 --> 00:10:06,318 So an N-Ball is just the, the higher 198 00:10:06,318 --> 00:10:09,406 dimension generalization of a circle or a sphere 199 00:10:09,406 --> 00:10:11,671 and it describes all of the, the points 200 00:10:11,671 --> 00:10:14,296 that are a certain distance from our target. 201 00:10:14,296 --> 00:10:17,523 Right, so this would be, so if we were performing a nearest 202 00:10:17,523 --> 00:10:19,913 neighbor based classification or some sort 203 00:10:19,913 --> 00:10:22,497 of local pattern recognition strategy, we'd 204 00:10:22,497 --> 00:10:25,787 want a couple of data points in the local N-Ball, right, in 205 00:10:25,787 --> 00:10:30,712 order to decide what the, the, the appropriate inferences at the query point. 206 00:10:30,712 --> 00:10:35,700 So this is an expression for the volume of an N-ball with a number of dimensions, N. 207 00:10:35,700 --> 00:10:38,160 And note in particular the gamma function in the denominator. 208 00:10:38,160 --> 00:10:41,740 This is the, the real value generalization of the factorial function, right? 209 00:10:41,740 --> 00:10:44,050 And we all know the factorial function goes up, starts 210 00:10:44,050 --> 00:10:48,180 to go up very highly, very quickly for higher values, right? 211 00:10:48,180 --> 00:10:50,920 Beyond about five or six, it really starts to explode. 212 00:10:50,920 --> 00:10:54,088 So, we're getting here is an exploding denominator, right? 213 00:10:54,088 --> 00:10:58,190 So that the volume of the N-ball relative to the 214 00:10:58,190 --> 00:11:03,530 volume of the hypercube that encloses it, is actually decreasing. 215 00:11:03,530 --> 00:11:06,920 Right, so here is the, here's the plot actually of the ratio. 216 00:11:06,920 --> 00:11:09,980 So I plotted here the ratio of the volume of the N-ball that's 217 00:11:09,980 --> 00:11:11,670 described within a hypercube as the number 218 00:11:11,670 --> 00:11:14,570 of dimensions of our input space increases. 219 00:11:14,570 --> 00:11:17,310 You can see just look at the, the Y-axis here. 220 00:11:17,310 --> 00:11:20,780 We're already for say eight or nine 221 00:11:20,780 --> 00:11:22,750 dimensions, we're already up in the hundreds. 222 00:11:22,750 --> 00:11:22,970 All right. 223 00:11:22,970 --> 00:11:23,780 So what does this mean? 224 00:11:23,780 --> 00:11:27,560 This means that our inscribed N-Ball, which I've shown here in two dimensions 225 00:11:27,560 --> 00:11:31,570 at, at right co, comprise the much smaller portion of the input space. 226 00:11:31,570 --> 00:11:31,820 Right? 227 00:11:31,820 --> 00:11:34,720 Most of the volume of these high dimensional spaces 228 00:11:34,720 --> 00:11:38,730 is very far from the, the center of the N-Ball. 229 00:11:38,730 --> 00:11:38,900 Right? 230 00:11:38,900 --> 00:11:42,280 So, if we were to evenly distribute a bunch of points in this high dimensional 231 00:11:42,280 --> 00:11:46,390 space, it'd be very rare that any of them actually fall in the, in the N-Ball. 232 00:11:46,390 --> 00:11:49,580 They almost, all be more or less equidistant from the N-Ball, outside it in 233 00:11:49,580 --> 00:11:51,960 these corners which start to look extremely 234 00:11:51,960 --> 00:11:53,700 long and spiky in high dimensional spaces. 235 00:11:53,700 --> 00:11:55,480 But this, this is kind of non-intuitive, right? 236 00:11:55,480 --> 00:11:57,790 Because we're used to thinking about these well behaved 237 00:11:57,790 --> 00:12:00,470 two and three dimensional volumes, it's what we can visualize. 238 00:12:00,470 --> 00:12:02,190 But in fact, the properties of 239 00:12:02,190 --> 00:12:05,055 these high dimensional spaces, the geometric properties. 240 00:12:05,055 --> 00:12:07,230 are, are not at all amenable to the 241 00:12:07,230 --> 00:12:09,410 sort of nearest neighbor approaches for just this reason. 242 00:12:09,410 --> 00:12:11,800 We've got all of our volume in these long, 243 00:12:11,800 --> 00:12:15,402 spiky structures that, that are far from, from the query. 244 00:12:15,402 --> 00:12:18,530 All right, so everything starts to look like that pathological case that I 245 00:12:18,530 --> 00:12:21,850 showed you before where all of the data is more or less equidistant. 246 00:12:21,850 --> 00:12:25,460 And it's very susceptible to noise in, in 247 00:12:25,460 --> 00:12:28,120 the input space and the, the training data, right. 248 00:12:28,120 --> 00:12:31,080 So evenly distributed data points and high dimensional 249 00:12:31,080 --> 00:12:34,310 spaces are generally a bad thing for pattern recognition. 250 00:12:35,980 --> 00:12:40,430 So, in summary, as dimensions increase, these Euclidean distances, that 251 00:12:40,430 --> 00:12:43,660 is these, these, end balls beco, become less and less meaningful. 252 00:12:43,660 --> 00:12:46,230 You can't interpret Euclidean distances easily. 253 00:12:46,230 --> 00:12:49,130 Uniform di, distributions become harder to sample. 254 00:12:50,430 --> 00:12:52,650 and, it, in a fashion it grows, really 255 00:12:52,650 --> 00:12:56,100 explodes as, as the number of, of dimensions increases. 256 00:12:56,100 --> 00:12:58,530 Many parameters become polynomially harder to 257 00:12:58,530 --> 00:13:00,490 estimate as the number of dimensions increases. 258 00:13:00,490 --> 00:13:03,150 But most importantly perhaps and something that 259 00:13:03,150 --> 00:13:05,500 is often overlooked in the pattern recognition literature. 260 00:13:05,500 --> 00:13:07,990 It's just a lot more difficult to interpret your data 261 00:13:07,990 --> 00:13:10,560 and understand it and visualize it in higher dimensional spaces. 262 00:13:10,560 --> 00:13:15,140 We're restricted to seeing just the tiny subspace slices. 263 00:13:15,140 --> 00:13:16,772 In two or three dimensions of data 264 00:13:16,772 --> 00:13:19,875 sets that actually have much grander structure potentially. 265 00:13:19,875 --> 00:13:22,542 So this, these are all challenges as 266 00:13:22,542 --> 00:13:25,879 the dimensions in the number of data increases. 267 00:13:25,879 --> 00:13:27,585 So are their any real life problems where 268 00:13:27,585 --> 00:13:29,753 you have high dimensional input spaces like this? 269 00:13:29,753 --> 00:13:33,620 Well actually the rule rather than the exception. 270 00:13:33,620 --> 00:13:36,600 So here's one great example so face recognition. 271 00:13:36,600 --> 00:13:39,170 Or any sort of object recognition can 272 00:13:39,170 --> 00:13:41,530 be formulated as pattern recognition where you're 273 00:13:41,530 --> 00:13:44,500 trying to classify images or image frames 274 00:13:44,500 --> 00:13:48,090 that could have many hundreds of pixels, right? 275 00:13:48,090 --> 00:13:50,250 So, here we're looking at templates to try and 276 00:13:50,250 --> 00:13:52,830 decide which one contains a face and which one doesn't. 277 00:13:54,010 --> 00:13:56,060 The most obvious way to formulate this would be 278 00:13:56,060 --> 00:13:58,580 as a 20 pixel by 20 pixel input space right. 279 00:13:58,580 --> 00:14:01,320 That's 400 dimensions in your input space. 280 00:14:01,320 --> 00:14:04,300 So we're well into the range of super high dimensional spaces, 281 00:14:04,300 --> 00:14:08,360 for which local pattern recognition strategies won't work as well right. 282 00:14:08,360 --> 00:14:12,050 And, and face recognition, it's obvious that we, that it works right. 283 00:14:12,050 --> 00:14:16,510 We've got cameras that can do this but in order to actually get Pattern 284 00:14:16,510 --> 00:14:18,100 Recognition to operate, we're going to need some 285 00:14:18,100 --> 00:14:23,180 sophisticated pre-processing strategies to, to reduce the dimensionality. 286 00:14:24,210 --> 00:14:28,040 Another domain where these sorts of higher dimensional input points are 287 00:14:28,040 --> 00:14:31,700 common is in in the science that's more in the, the Earth. 288 00:14:31,700 --> 00:14:34,070 And space sciences realm is in spectroscopy. 289 00:14:34,070 --> 00:14:35,580 Often in spectro, we're describing 290 00:14:35,580 --> 00:14:38,160 individual data points by many wavelengths. 291 00:14:38,160 --> 00:14:40,130 So here we have reflective spectra. 292 00:14:40,130 --> 00:14:42,610 Which are measurements at many wavelengths of 293 00:14:42,610 --> 00:14:46,880 light here from 350 to about 950 nanometers. 294 00:14:46,880 --> 00:14:51,840 these, relfectant spectra can easily be tens or 295 00:14:51,840 --> 00:14:55,940 even hundreds of, of dimensions in, in size. 296 00:14:55,940 --> 00:14:57,610 Right, and yet we need to find a way 297 00:14:57,610 --> 00:14:59,840 to perform pattern recognition on these data sets too 298 00:14:59,840 --> 00:15:03,150 in order to distinguish spectra or classify them and 299 00:15:03,150 --> 00:15:05,160 we're going to need more sophisticated methods to do that. 300 00:15:06,680 --> 00:15:08,760 All right, so I want to close with a couple 301 00:15:08,760 --> 00:15:12,180 of by wetting your appetite with a couple of solutions. 302 00:15:12,180 --> 00:15:16,620 So one solution to the curse of dimensionality would be to rely only 303 00:15:16,620 --> 00:15:18,720 on those pattern recognition methods that 304 00:15:18,720 --> 00:15:21,390 are intrinsically robust to higher dimensional space. 305 00:15:21,390 --> 00:15:24,464 That's right, so we've talked in previous lectures about random force, 306 00:15:24,464 --> 00:15:27,454 for example, which tend to do pretty well in higher dimensional spaces. 307 00:15:27,454 --> 00:15:30,670 So, you could limit yourself to those pattern recognition strategies. 308 00:15:30,670 --> 00:15:34,025 now, that's kind of limiting and there are, there are other ways we can 309 00:15:34,025 --> 00:15:38,000 tackle the problem, and in particular we can try to represent the data differently. 310 00:15:38,000 --> 00:15:41,610 So we can use hand crafted features. 311 00:15:41,610 --> 00:15:43,900 We can use a sub set of the futures and in the next 312 00:15:43,900 --> 00:15:47,960 lecture I'm going to talk about feature sub selections strategies that will let 313 00:15:47,960 --> 00:15:49,590 us reduce the dimensionality by, by 314 00:15:49,590 --> 00:15:52,650 choosing just selecting particular features that are 315 00:15:52,650 --> 00:15:54,240 more informative than the rest, and, 316 00:15:54,240 --> 00:15:56,590 and performing our pattern recognition on those. 317 00:15:56,590 --> 00:16:00,830 We can also come up with linear projections of the, of the input data set. 318 00:16:00,830 --> 00:16:02,930 That will reduce the dimensionality so that it's 319 00:16:02,930 --> 00:16:06,500 more amenable to our, our local pattern recognition approaches. 320 00:16:06,500 --> 00:16:09,380 And then in the, the final lectures I'll describe some nonlinear 321 00:16:09,380 --> 00:16:11,440 projection strategies that will allow us 322 00:16:11,440 --> 00:16:14,020 to reduce dimensionality in non-linear ways. 323 00:16:15,162 --> 00:16:19,460 All right, so in summary I described some ways to find nearest neighbors 324 00:16:19,460 --> 00:16:23,820 in data sets, sorted lists for 1D, K-D Tree for two to eight dimensions. 325 00:16:23,820 --> 00:16:26,260 And above that, you'll want to use approximate nearest neighbors. 326 00:16:26,260 --> 00:16:28,880 But far above that, most of these 327 00:16:28,880 --> 00:16:30,970 local pattern recognition methods will fail because of 328 00:16:30,970 --> 00:16:33,270 the curse of dimensionality and so the, the 329 00:16:33,270 --> 00:16:35,170 coming lectures will provide some solutions to that.