1 00:00:00,770 --> 00:00:03,420 The topic of this lecture is metric learning and it's going to be 2 00:00:03,420 --> 00:00:04,850 building on some of the ideas that 3 00:00:04,850 --> 00:00:08,710 we presented earlier, about linear dimensionality reduction. 4 00:00:08,710 --> 00:00:12,120 We're also going to be looking mostly at linear approaches here, but, 5 00:00:12,120 --> 00:00:15,200 we're going to start taking into account class structure as well, so 6 00:00:15,200 --> 00:00:18,350 the actual class of a different data points and this leads 7 00:00:18,350 --> 00:00:21,190 us into a new corner of the field known as metric learning. 8 00:00:23,522 --> 00:00:28,100 All right, the main objectives of this presentation will be to help you 9 00:00:28,100 --> 00:00:31,080 understand the Mahalanobis distance, which is probably 10 00:00:31,080 --> 00:00:34,100 the most important class of distance metrics. 11 00:00:34,100 --> 00:00:36,340 And then we'll know how to apply metric learning 12 00:00:36,340 --> 00:00:39,270 to a classification problem to get a pretty improved performance. 13 00:00:41,480 --> 00:00:44,780 All right, so here's a, I mean, just a real simple example to motivate 14 00:00:44,780 --> 00:00:46,160 why we might be interested in learning 15 00:00:46,160 --> 00:00:49,650 distance metrics and it involves predicting heart attacks. 16 00:00:49,650 --> 00:00:51,770 So here we've got a table of attributes 17 00:00:51,770 --> 00:00:55,550 for different individuals with, with different at numerical 18 00:00:55,550 --> 00:00:58,240 attributes, so we've encoded gender as either zero 19 00:00:58,240 --> 00:01:01,770 or one we've included the age as well, the, 20 00:01:01,770 --> 00:01:04,600 the individual's weight which might be relevant to 21 00:01:04,600 --> 00:01:05,900 whether they're going to have a heart attack 22 00:01:05,900 --> 00:01:07,390 or not and we've also included their, their 23 00:01:07,390 --> 00:01:10,230 income, right, which might or might not be relevant. 24 00:01:10,230 --> 00:01:15,150 So one thing to note about this, this particular formulation is that all of 25 00:01:15,150 --> 00:01:18,140 these different attributes have wildly different scales, 26 00:01:18,140 --> 00:01:22,070 right, so, Income could differ widely by thousands 27 00:01:22,070 --> 00:01:25,930 where as weight is probably going to differ by ten at most, and age maybe by 28 00:01:25,930 --> 00:01:29,450 just ten or so years, gender is never going to differ by very much at all. 29 00:01:29,450 --> 00:01:32,950 So these attributes are all,um, they all have different scalings 30 00:01:32,950 --> 00:01:36,150 in this input space but there's nothing in the data that 31 00:01:36,150 --> 00:01:39,280 would indicate that, right, so if we just throw, our 32 00:01:39,280 --> 00:01:41,070 standard pattern recognition algorithms at 33 00:01:41,070 --> 00:01:43,710 this, our standard dimensionality reduction algorithms. 34 00:01:43,710 --> 00:01:47,440 They might be unduly influenced by a feature like income, right, 35 00:01:47,440 --> 00:01:50,560 which is going to have very high variance relative to the others. 36 00:01:50,560 --> 00:01:53,630 So, an, another related problem is that there may be 37 00:01:53,630 --> 00:01:56,520 correlations you can imagine, as we add more features on 38 00:01:56,520 --> 00:01:58,910 there, there could be spurious correlations in the data set 39 00:01:58,910 --> 00:02:03,240 that make different, attributes totally redundant with each other as well. 40 00:02:03,240 --> 00:02:07,925 So, what particularly for nearest neighbor methods and methods like that that rely 41 00:02:07,925 --> 00:02:10,715 on calculating distances within the attribute space, 42 00:02:10,715 --> 00:02:12,673 those are definitely going to be biased 43 00:02:12,673 --> 00:02:16,349 by the income attribute as opposed to some of the others that might not 44 00:02:16,349 --> 00:02:20,360 actually be relevant to the heart attack problem, so how do we solve this? 45 00:02:20,360 --> 00:02:23,140 Well, a traditional solution to resolving this might be 46 00:02:23,140 --> 00:02:25,550 to apply some sort of preprocessing strategy, we can 47 00:02:25,550 --> 00:02:29,470 do normalization, maybe standardize things, so, they have mean 48 00:02:29,470 --> 00:02:33,100 zero and standard deviation one, that's a fairly common approach. 49 00:02:33,100 --> 00:02:34,780 There's all sorts of preprocessing methods that we 50 00:02:34,780 --> 00:02:38,110 can apply but the intuition behind metric learning 51 00:02:38,110 --> 00:02:39,920 is that maybe if we incorporate some class 52 00:02:39,920 --> 00:02:41,870 information from our training set, we can do 53 00:02:41,870 --> 00:02:44,200 even better and we can define distances into 54 00:02:44,200 --> 00:02:46,540 space, that are actually more relevant to the 55 00:02:46,540 --> 00:02:48,980 task at hand than we would if we 56 00:02:48,980 --> 00:02:51,320 simply relied on intrinsic properties of the data itself. 57 00:02:53,910 --> 00:02:56,810 All right, so to summarize, measuring distance is 58 00:02:56,810 --> 00:02:58,970 a really critical part of pattern recognition, this is 59 00:02:58,970 --> 00:03:00,940 not just for local methods too, this is 60 00:03:00,940 --> 00:03:05,030 for all sorts of parametric methods for classification regression. 61 00:03:05,030 --> 00:03:10,540 Until now, we've sort of been letting the data itself define our, our distances but 62 00:03:10,540 --> 00:03:12,550 there are challenges with this that we noted 63 00:03:12,550 --> 00:03:15,670 before and additionally, recall that Euclidean distances are 64 00:03:15,670 --> 00:03:17,880 less meaningful in high dimensions anyway, so 65 00:03:17,880 --> 00:03:20,112 even if our data is perfectly isotropic and, 66 00:03:20,112 --> 00:03:22,890 and, and uncorrelated with each other and all 67 00:03:22,890 --> 00:03:26,290 distances mean the same thing along all attributes,. 68 00:03:26,290 --> 00:03:29,470 Those Euclidean distances are going to be less, valuable 69 00:03:29,470 --> 00:03:31,770 to us, as we start moving to high dimensions 70 00:03:31,770 --> 00:03:33,920 just because of the curious geometry of these high 71 00:03:33,920 --> 00:03:36,950 dimensional spaces, so, how can we resolve this problem? 72 00:03:36,950 --> 00:03:39,930 Well, metric learning is based on the idea 73 00:03:39,930 --> 00:03:43,310 that we can, define new distance metrics new 74 00:03:43,310 --> 00:03:46,110 rulers for measuring distance in higher dimensional spaces 75 00:03:46,110 --> 00:03:48,146 that are based on properties of the data itself. 76 00:03:48,146 --> 00:03:52,560 These are non-isotropic distances that reflect some intrinsic structure 77 00:03:52,560 --> 00:03:55,200 in the data, right, so this, is a really elegant 78 00:03:55,200 --> 00:03:57,460 depiction of, of what we're talking about that involves 79 00:03:57,460 --> 00:04:01,870 moving from, Euclidean isotropic distances to a Mahalanopi distance metric. 80 00:04:01,870 --> 00:04:05,160 So, on the left side you see a data set of, I 81 00:04:05,160 --> 00:04:09,310 guess, six points they're sure the data's point color represents their class, 82 00:04:09,310 --> 00:04:12,100 so you can see that the, the yellow points are all of 83 00:04:12,100 --> 00:04:15,160 one class, and they're sort of of distributed more or less along a line. 84 00:04:15,160 --> 00:04:17,180 And there also a couple of, of points have 85 00:04:17,180 --> 00:04:20,520 different class values to the north and south of them. 86 00:04:20,520 --> 00:04:22,970 Note that if we're, if we're trying to classify the query point in 87 00:04:22,970 --> 00:04:27,380 the center and we want to enclose the entire training data set of yellow 88 00:04:27,380 --> 00:04:31,100 points, we have to look out far enough that we're actually, the end 89 00:04:31,100 --> 00:04:35,850 ball is encompassing all of our data including the, the blue and the red. 90 00:04:35,850 --> 00:04:40,360 So really what this suggest is that the the, the Euclidean data, or, 91 00:04:40,360 --> 00:04:42,100 I'm sorry, the Euclidean distance metric, which 92 00:04:42,100 --> 00:04:43,410 is the same in all directions, really 93 00:04:43,410 --> 00:04:47,870 doesn't reflect, the class structure in the data, that's, tends to be distributed 94 00:04:47,870 --> 00:04:51,270 along this, this line, so Mahalanobis distance 95 00:04:51,270 --> 00:04:55,323 metric is more akin to, say, ellipsoid. 96 00:04:55,323 --> 00:05:00,378 And that's what's portrayed at the, in the panel at right here we're looking at a, 97 00:05:00,378 --> 00:05:03,636 a Mahalanobis distance, and here it, the, end 98 00:05:03,636 --> 00:05:06,764 ball in this Mahalanobis distance measure encloses all 99 00:05:06,764 --> 00:05:09,424 of the, the yellow points while avoiding the, 100 00:05:09,424 --> 00:05:12,218 the data points of different classes, so, there 101 00:05:12,218 --> 00:05:16,910 now are are a ruler in this space actually reflects the, the structure of the data. 102 00:05:20,120 --> 00:05:22,330 So, how do you calculate a Mahalanobis distance? 103 00:05:22,330 --> 00:05:24,900 Well, we know how to calculate a Euclidean distance, right? 104 00:05:24,900 --> 00:05:30,420 It's just the, squared basically the, the square sum of differences, take 105 00:05:30,420 --> 00:05:33,910 the, the sum of square differences and then take the square root. 106 00:05:33,910 --> 00:05:39,490 The Mahalanobis distance metric is almost the same, except in there, there's a an 107 00:05:39,490 --> 00:05:44,646 inverse positive, semi-definite matrix that I've indicated here with this sigma. 108 00:05:44,646 --> 00:05:48,740 So, the, and you maybe note an analogy with the, the co-variance 109 00:05:48,740 --> 00:05:52,090 matrix from data sets that we've seen before, saying that in the PCA 110 00:05:52,090 --> 00:05:55,780 lecture that preceded this one and that's not an accident, because actually 111 00:05:55,780 --> 00:05:59,530 you can easily use a covariance matrix here to, to whiten your data. 112 00:05:59,530 --> 00:06:03,440 Just take it's inverse and scale all the, the dimensions and correlations 113 00:06:03,440 --> 00:06:07,260 appropriately to basically undo the covariance 114 00:06:07,260 --> 00:06:09,750 properties of the original data set. 115 00:06:09,750 --> 00:06:12,090 And this gives, this whitens the data, it 116 00:06:12,090 --> 00:06:14,310 makes everything isotropic so that the distance we 117 00:06:14,310 --> 00:06:18,280 calculate will be now adequate with, it will 118 00:06:18,280 --> 00:06:21,740 reflect the, the correlations in sigma, the sigma matrix. 119 00:06:24,810 --> 00:06:27,550 It, you, one can easily show that this expression is 120 00:06:27,550 --> 00:06:30,376 actually equivalent to a linear pre transformation of the data. 121 00:06:30,376 --> 00:06:35,910 So here we define the, we define this this 122 00:06:35,910 --> 00:06:41,270 matrix sigma as V transpose V and push it through some algebra, and reveal 123 00:06:41,270 --> 00:06:44,280 on the, the bottom line there the expression that is actually 124 00:06:44,280 --> 00:06:48,590 equivalent to pre-multiplying all of our data by a new basis V. 125 00:06:48,590 --> 00:06:51,260 So really what this means is that in order to calculate 126 00:06:51,260 --> 00:06:54,510 a Mahalanobis distance we can just take some trans, some linear 127 00:06:54,510 --> 00:06:59,010 transformation of the data and then apply our Euclidean distance in 128 00:06:59,010 --> 00:07:03,210 that space and it's the same as the, the Mahalanobis distance metric. 129 00:07:03,210 --> 00:07:04,330 And note that you can calculate 130 00:07:04,330 --> 00:07:08,210 this decomposition for any positive semi-definite matrix, 131 00:07:08,210 --> 00:07:11,550 It's possible to decompose it into the, to the V as we're done here. 132 00:07:11,550 --> 00:07:14,150 So there's a natural relationship between 133 00:07:14,150 --> 00:07:16,590 the Mahalanobis distance metric, or the ellipsoidal 134 00:07:16,590 --> 00:07:19,800 distance and the the linear dimensionality reduction 135 00:07:19,800 --> 00:07:22,140 strategies that we've explored in previous lectures. 136 00:07:24,042 --> 00:07:27,300 All right, this leads me to the wild and woolly topic of 137 00:07:27,300 --> 00:07:30,550 metric learning which is an area of a lot of active research. 138 00:07:30,550 --> 00:07:35,610 Most modern metric learning research that is work to, to learn 139 00:07:35,610 --> 00:07:40,260 these, these distance measures treat it as a convex optimization problem. 140 00:07:40,260 --> 00:07:43,570 So they take a Mahalanobis distance, and then have some 141 00:07:43,570 --> 00:07:47,000 constraints on that based on the class structure in the data, 142 00:07:47,000 --> 00:07:50,120 such as, data points having similar class must be close 143 00:07:50,120 --> 00:07:53,290 together, data points having different class must be far apart, right. 144 00:07:53,290 --> 00:07:56,240 And then treat it as an optimization problem and 145 00:07:56,240 --> 00:08:00,010 apply techniques from operational research and, and other disciplines 146 00:08:00,010 --> 00:08:03,000 in order to tune that Mahalanobis distance metric that 147 00:08:03,000 --> 00:08:08,280 sigma matrix to best, separate the different classes, right. 148 00:08:08,280 --> 00:08:11,897 And there, there are challenges there of course in, keeping the, 149 00:08:11,897 --> 00:08:15,157 the nature positive semi definite which it must be in order to 150 00:08:15,157 --> 00:08:18,595 be a valid Mahalanobis metric but that's the, part of the, the 151 00:08:18,595 --> 00:08:22,540 research that's going on but there are lots of applications of this. 152 00:08:22,540 --> 00:08:25,720 Which include computer vision, information retrieval where 153 00:08:25,720 --> 00:08:27,450 you can be looking in databases, right, 154 00:08:27,450 --> 00:08:29,210 to find something that's similar to your 155 00:08:29,210 --> 00:08:31,810 query, which could be expressed as an image 156 00:08:31,810 --> 00:08:35,600 or a document with a bunch of text, right, which would have potentially thousands of 157 00:08:35,600 --> 00:08:37,900 different word attributes or in biometrics where 158 00:08:37,900 --> 00:08:40,240 you're looking at, at gene expression information, right. 159 00:08:40,240 --> 00:08:42,220 You could easily get data points of 160 00:08:42,220 --> 00:08:44,340 thousands or tens of thousands of attributes there. 161 00:08:44,340 --> 00:08:45,950 So, it becomes important if you're doing 162 00:08:45,950 --> 00:08:48,560 similarity queries in those sorts of settings 163 00:08:48,560 --> 00:08:53,320 that you have an effective distance metric on which to, to do that query. 164 00:08:53,320 --> 00:08:57,660 So yeah, so this is the, the modern topic 165 00:08:57,660 --> 00:08:59,210 of, of metric learning, and here are a couple 166 00:08:59,210 --> 00:09:01,400 of examples of the different methods that have been 167 00:09:01,400 --> 00:09:04,610 proposed in the literature for learning these distance metrics. 168 00:09:04,610 --> 00:09:09,669 Most of this this list are Mahalanobis distance metrics or linear 169 00:09:09,669 --> 00:09:14,234 pre-transformations of the data, this list is formed by Herbert and Saban 170 00:09:14,234 --> 00:09:18,081 et al, and it simply gives you some intuition for the, 171 00:09:18,081 --> 00:09:22,990 the breadth of different algorithms that are available to do metric learning. 172 00:09:22,990 --> 00:09:29,300 Now we're going to do we're going to, put most of this, aside for now and 173 00:09:29,300 --> 00:09:33,570 instead talk about an oldie but a goodie, that is a classical approach for a metric 174 00:09:33,570 --> 00:09:36,880 learning that works in many cases and 175 00:09:36,880 --> 00:09:40,270 has, the additional property that's pretty robust and 176 00:09:40,270 --> 00:09:43,510 reliable and pretty easy and cheap to implement, 177 00:09:43,510 --> 00:09:46,520 that is pretty Is simple to, to implement. 178 00:09:49,250 --> 00:09:50,680 I think I, I mentioned this already 179 00:09:50,680 --> 00:09:53,670 once before, the relationship with linear dimensionality reduction, 180 00:09:54,780 --> 00:09:58,850 that is, if this pre-linear pre-transformation is 181 00:09:58,850 --> 00:10:00,950 it, it represents a subspace of the data. 182 00:10:00,950 --> 00:10:04,998 That is the, the covariance matrix isn't full rank or V has 183 00:10:04,998 --> 00:10:10,430 fewer columns than the, the full space of the data and this 184 00:10:10,430 --> 00:10:14,880 actually equates to a dimensionality reduction and in that case, it's akin 185 00:10:14,880 --> 00:10:18,020 to PCA or some of the other methods that we've shown previously. 186 00:10:18,020 --> 00:10:21,970 The only difference being that here, the, the dimensionality reduction is taking the 187 00:10:21,970 --> 00:10:23,510 class structure into account and trying to 188 00:10:23,510 --> 00:10:25,210 separate the different classes from each other. 189 00:10:27,280 --> 00:10:31,840 Okay, so here's our, our classical approach to metric learning, this is 190 00:10:31,840 --> 00:10:33,810 a method that dates back to 191 00:10:33,810 --> 00:10:36,640 Fisher, I believe, It's multi-class discriminant analysis. 192 00:10:36,640 --> 00:10:40,870 It's a generalization of Fisher's linear discriminant, to the case where we have 193 00:10:40,870 --> 00:10:44,740 different, like many different classes, up to K different classes in this case. 194 00:10:44,740 --> 00:10:46,640 So we start with our data set of, of data 195 00:10:46,640 --> 00:10:50,270 points that's labeled with, with up to K different values the 196 00:10:50,270 --> 00:10:53,020 idea is to learn a Mahalanobis distance metric that best 197 00:10:53,020 --> 00:10:57,200 separates these classes from each other, where we'll define separation, shortly. 198 00:10:58,220 --> 00:11:00,350 the, output of this procedure is a linear 199 00:11:00,350 --> 00:11:04,030 projection of the dimensionality up to K minus 1. 200 00:11:04,030 --> 00:11:06,560 Right, so we'll also reduce the dimensionality of our, 201 00:11:06,560 --> 00:11:10,110 of our input space, and like I said, if we 202 00:11:10,110 --> 00:11:12,500 just use a, a single, a 1-D case with, 203 00:11:12,500 --> 00:11:16,160 with two classes, that's equivalent to Fischer's linear discriminant analysis. 204 00:11:19,202 --> 00:11:21,360 All right, so here are some definitions to get us started first, 205 00:11:21,360 --> 00:11:24,180 I'm going to define the class mean, as the mean of all 206 00:11:24,180 --> 00:11:28,400 the data points having a certain class label ascribed to them, so 207 00:11:28,400 --> 00:11:31,890 we have a class mean for each one of our K different classes. 208 00:11:31,890 --> 00:11:34,740 We're also going to define scatter matrices to represent the 209 00:11:34,740 --> 00:11:37,830 spread of the data here we define the within class 210 00:11:37,830 --> 00:11:41,390 scatter matrix and fashion similar to the, the sample covariance 211 00:11:41,390 --> 00:11:45,110 matrix, so we're just looking at squared distances against the mean. 212 00:11:45,110 --> 00:11:47,840 And we do that for each class independently 213 00:11:47,840 --> 00:11:49,240 if you take the sum of all the 214 00:11:49,240 --> 00:11:51,380 within class scatter matrices then you get the 215 00:11:51,380 --> 00:11:54,340 total within class scatter matrix for that data set. 216 00:11:54,340 --> 00:11:58,450 And here I, I've just represented this graphically on the right side as ellipsoid 217 00:11:58,450 --> 00:12:03,290 so each ellipse here has it's own, it represents data, from a different class in 218 00:12:03,290 --> 00:12:06,210 our data set, and the, within class 219 00:12:06,210 --> 00:12:07,880 scatters are represented by the blue lines, 220 00:12:07,880 --> 00:12:11,010 right, so basically that measures how compact 221 00:12:11,010 --> 00:12:14,660 all of these different class distributions are, right. 222 00:12:14,660 --> 00:12:19,000 We're also going to define cla, matrix known as the between class scatter 223 00:12:19,000 --> 00:12:21,920 matrix, which measures how well these 224 00:12:21,920 --> 00:12:24,660 different ellipses are separated from each other. 225 00:12:24,660 --> 00:12:26,750 So we take the mean of the entire data set, that is 226 00:12:26,750 --> 00:12:30,700 mu, and look at the, the difference between that and the mean of 227 00:12:30,700 --> 00:12:33,850 all of the classes independently, so this is represented in the image 228 00:12:33,850 --> 00:12:35,770 by the green arrows that show 229 00:12:35,770 --> 00:12:37,390 the, the separation between the different ellipsoids. 230 00:12:37,390 --> 00:12:39,440 So we have two measures of scatter here, 231 00:12:39,440 --> 00:12:42,570 the within class scatter and the between class scatter. 232 00:12:42,570 --> 00:12:45,308 So if we want to improve the separation of the classes 233 00:12:45,308 --> 00:12:48,668 in our projective space, the idea is to, come up the projection 234 00:12:48,668 --> 00:12:51,781 that shrinks the within class scatter that is we want all the 235 00:12:51,781 --> 00:12:56,370 class distributions to be as compact as possible, in the projected representation. 236 00:12:56,370 --> 00:12:59,890 The same time we want to increase the between class scatter, we want the classes 237 00:12:59,890 --> 00:13:01,952 to be well separated from each other, right 238 00:13:01,952 --> 00:13:05,160 and so,he said, how do you define this? 239 00:13:05,160 --> 00:13:07,000 Well, we, we measure the determinant of 240 00:13:07,000 --> 00:13:08,620 the scatter matrices, which you can think of 241 00:13:08,620 --> 00:13:10,610 as, sort of a measure of, of volume 242 00:13:10,610 --> 00:13:13,960 in high dimensions for these positive, semi-definite matrices. 243 00:13:16,180 --> 00:13:20,140 So here's our objective, we find the projection V to maximize 244 00:13:20,140 --> 00:13:23,260 the ratio of these determinants, that is the ratio of the between 245 00:13:23,260 --> 00:13:26,410 class scatter over the within class scatter, we're trying to increase the 246 00:13:26,410 --> 00:13:30,490 numerator and decrease the denominator, this is known as the Rayleigh coefficient. 247 00:13:30,490 --> 00:13:32,620 And there exist lots of, of 248 00:13:32,620 --> 00:13:35,220 straightforward ways to calculate this, but the, 249 00:13:35,220 --> 00:13:36,860 probably the most common one is the 250 00:13:36,860 --> 00:13:39,630 to simply solve this generalized eigenvalue problem. 251 00:13:39,630 --> 00:13:42,250 Where you have the within and between class scatter matrices on 252 00:13:42,250 --> 00:13:45,370 either sides of this expression and then the vector of, of 253 00:13:45,370 --> 00:13:48,710 eigenvectors which is or the, I'm sorry, the matrix of eigenvectors 254 00:13:48,710 --> 00:13:54,210 which is the and and then eigenvalues represented here by lambda. 255 00:13:54,210 --> 00:13:57,460 So solving this generalized eigenvalue problem with standard 256 00:13:57,460 --> 00:14:00,180 numerical software will give you the, the projection, 257 00:14:00,180 --> 00:14:02,110 that best separates the classes according to that 258 00:14:02,110 --> 00:14:03,640 criterion that we established in the last slide. 259 00:14:06,472 --> 00:14:09,400 All right, so I want to close the quick example 260 00:14:09,400 --> 00:14:12,270 of how this can actually be used in practice. 261 00:14:12,270 --> 00:14:15,360 so, here we're going to look at application 262 00:14:15,360 --> 00:14:18,020 in automated image analysis, so we're looking at 263 00:14:18,020 --> 00:14:20,900 analysis of geologic images in particular this is 264 00:14:20,900 --> 00:14:24,761 work by Francis et al and ISAIRAS of 2014. 265 00:14:24,761 --> 00:14:29,120 The ideas is to perform segmentation of images, he may, be familiar with 266 00:14:29,120 --> 00:14:31,030 image segmentation problems and here we're 267 00:14:31,030 --> 00:14:33,580 looking at, at basically clustering data points, 268 00:14:33,580 --> 00:14:36,690 but we want to cluster data points in a way that's, that's relevant to 269 00:14:36,690 --> 00:14:40,430 the task at hand, that is, relevant to the Geologic content of the images. 270 00:14:40,430 --> 00:14:43,980 So, then we're going to assume that our data cloud is, made up of points 271 00:14:43,980 --> 00:14:46,690 which are vectors of pixel attributes, which might 272 00:14:46,690 --> 00:14:50,420 include color attributes as well as texture attributes. 273 00:14:50,420 --> 00:14:53,860 And the objective here is to learn a projection that improves the quality 274 00:14:53,860 --> 00:14:58,470 of our image segmentation, that is, we want some distance where er, I'm 275 00:14:58,470 --> 00:15:01,710 sorry, we want some distance matrix, where distance in a, in a productive 276 00:15:01,710 --> 00:15:07,880 space represents a sort of geologic distance in the in the image space. 277 00:15:07,880 --> 00:15:10,580 So here's an example of, what the automated clustering should look like, 278 00:15:10,580 --> 00:15:15,080 so here's an example of our, a k-means clustering, with just two clusters. 279 00:15:15,080 --> 00:15:16,870 You can see, we have a rock outcrop on the, 280 00:15:16,870 --> 00:15:20,610 the left, and we've applied unsupervised clustering to that, and it 281 00:15:20,610 --> 00:15:24,220 nicely splits the image into two different classes, at right, and 282 00:15:24,220 --> 00:15:28,820 this corresponds quite well with the geologist, interpretation of the scene. 283 00:15:28,820 --> 00:15:30,900 And so we'd like to, to do this for, for 284 00:15:30,900 --> 00:15:34,690 all sorts of, of, outcrop images, but it doesn't always work. 285 00:15:34,690 --> 00:15:37,670 You can see that, often the pixel 286 00:15:37,670 --> 00:15:41,150 values themselves don't actually reflect the geologic content. 287 00:15:41,150 --> 00:15:45,400 So this is quite obvious in this image where we have fractures that are a lot 288 00:15:45,400 --> 00:15:47,460 darker than everything else, but they aren't, so 289 00:15:47,460 --> 00:15:49,940 these fractures aren't necessarily geologically interesting and they 290 00:15:49,940 --> 00:15:52,290 don't correspond with the, the composition of the 291 00:15:52,290 --> 00:15:54,820 rock that we're trying to recover, but, k-mean 292 00:15:54,820 --> 00:15:58,180 clustering is biased by the, the, the values 293 00:15:58,180 --> 00:16:00,160 of those, those feat, or of those pixels. 294 00:16:00,160 --> 00:16:02,630 That is, the extreme attributes the extreme, 295 00:16:02,630 --> 00:16:04,880 dark intensity of those pixels, right, which cause 296 00:16:04,880 --> 00:16:06,390 it to be very distant from everything else, 297 00:16:06,390 --> 00:16:08,850 so the fractures appear as their own cluster. 298 00:16:08,850 --> 00:16:12,320 Right, we'd like to avoid that we different distance metric, that will 299 00:16:12,320 --> 00:16:14,540 allow the, the k-mean segmentation to 300 00:16:14,540 --> 00:16:17,210 overlook, some of these incidental features 301 00:16:17,210 --> 00:16:20,260 like fractures and instead focus on the features that are most relevant, 302 00:16:20,260 --> 00:16:24,060 that is the color and texture cues that will tell us, where composition 303 00:16:26,170 --> 00:16:27,280 is actually changing. 304 00:16:27,280 --> 00:16:32,690 So, Francis et al applied, the multi-class discriminant analysis to this problem 305 00:16:32,690 --> 00:16:36,650 and here you see a production of data points from rock outcrops. 306 00:16:36,650 --> 00:16:39,020 This rock outcrop had three different classes and you can see 307 00:16:39,020 --> 00:16:42,580 that they MDA production, that is the multi-class discriminant analysis does 308 00:16:42,580 --> 00:16:46,780 a much better job of project, of separating these classes than 309 00:16:46,780 --> 00:16:51,140 traditional PCA or indeed clustering on the, the raw feature space would. 310 00:16:51,140 --> 00:16:55,640 So by training on, labelled examples from one image, and then applying that distance 311 00:16:55,640 --> 00:16:57,360 metric to another image we can actually 312 00:16:57,360 --> 00:17:00,630 teach the system how to perform clustering better. 313 00:17:00,630 --> 00:17:04,310 In order to recover geologic classes as part of the cluster, so 314 00:17:04,310 --> 00:17:07,370 here's a visual example on that image that I showed you before. 315 00:17:07,370 --> 00:17:10,970 The fractures in, instead of getting their own cluster after 316 00:17:10,970 --> 00:17:14,350 we learn the distance metric appropriately, we can get the 317 00:17:14,350 --> 00:17:19,150 system to, actually recover autonomously recover the, the compositional differences 318 00:17:19,150 --> 00:17:22,230 in the rock and and avoid the, the fracture confusion. 319 00:17:22,230 --> 00:17:25,085 So, this is just one of many examples where a 320 00:17:25,085 --> 00:17:28,330 multi-class discriminant analysis can improve 321 00:17:28,330 --> 00:17:30,115 unsupervised clustering, so, this, this 322 00:17:30,115 --> 00:17:33,250 pre-transformation that we've trained on label data can be used 323 00:17:33,250 --> 00:17:37,120 to improve a totally unsupervised clustering approach on future images. 324 00:17:38,480 --> 00:17:42,050 Okay, so a quick summary of what we've covered in this lecture 325 00:17:42,050 --> 00:17:46,190 we talked about Mahalanobis distance metrics which are sort of an ellipsoidal, 326 00:17:46,190 --> 00:17:48,540 generalization of the Euclidean distance, it, 327 00:17:48,540 --> 00:17:51,460 applying them or measuring Mahalanobis distance 328 00:17:51,460 --> 00:17:54,510 is equivalent to applying a linear transformation on the original data set. 329 00:17:56,010 --> 00:17:58,990 Metric learning can outperform purely unsupervised 330 00:17:58,990 --> 00:18:01,020 dimensionality reduction by accounting for the, the 331 00:18:01,020 --> 00:18:04,006 structure of classes, and we've additionally shown 332 00:18:04,006 --> 00:18:07,560 how multi-class discriminant analysis is a particularly 333 00:18:07,560 --> 00:18:09,800 useful, form of metric learning that 334 00:18:09,800 --> 00:18:11,980 can provide projections of dimensionality up to 335 00:18:11,980 --> 00:18:14,370 k minus 1, where k is the number of classes in your data set.