1 00:00:01,390 --> 00:00:03,830 I'm David Thompson, and this is the third lecture in the 2 00:00:03,830 --> 00:00:09,030 series on dimensionality reduction for the Cal Tech Big Data Summer School. 3 00:00:09,030 --> 00:00:11,730 This lecture is going to be on the topic of Feature Selection. 4 00:00:11,730 --> 00:00:16,090 So in, in previous modules I talked about local methods for pattern recognition. 5 00:00:16,090 --> 00:00:18,290 And then described how those methods don't work as 6 00:00:18,290 --> 00:00:20,940 well as you move to higher dimensional input spaces. 7 00:00:20,940 --> 00:00:24,010 So this is I guess the most, the simplest, easiest 8 00:00:24,010 --> 00:00:26,830 way to reduce a high dimensional data set to something more 9 00:00:26,830 --> 00:00:30,150 manageable, and that's just by taking a subsle, subset of the 10 00:00:30,150 --> 00:00:32,770 features, and there are a bunch of ways to do that. 11 00:00:32,770 --> 00:00:34,140 We'll investigate many of them here. 12 00:00:35,320 --> 00:00:38,450 All right, so the objectives of this module are 13 00:00:38,450 --> 00:00:40,360 to be able to first know that and understand 14 00:00:40,360 --> 00:00:43,910 the techniques for combinatorial feature selection and have a 15 00:00:43,910 --> 00:00:47,540 couple tools in your tool kit for finding informative features. 16 00:00:47,540 --> 00:00:50,620 There are two basic kinds of feature selection methods. 17 00:00:50,620 --> 00:00:52,590 There are wrappers and filters, and you should 18 00:00:52,590 --> 00:00:54,360 be able to know the different between them. 19 00:00:54,360 --> 00:00:56,450 And you should also be able to know 20 00:00:56,450 --> 00:00:59,340 different search strategies for searching for subsets of features. 21 00:00:59,340 --> 00:01:03,030 We're going to talk mostly about forward and backwards feature selection. 22 00:01:05,770 --> 00:01:08,740 So, why are we interested in feature selection in the first place? 23 00:01:08,740 --> 00:01:11,400 Well, there are several different reasons why you might want to perform 24 00:01:11,400 --> 00:01:14,420 this as a preprocessing operation, and go through all the trouble. 25 00:01:14,420 --> 00:01:18,380 The first is, of course what I alluded to before, that is that large 26 00:01:18,380 --> 00:01:20,630 dimension, or high dimensional input spaces can 27 00:01:20,630 --> 00:01:23,180 be problematic, because they're difficult to sample from. 28 00:01:23,180 --> 00:01:26,250 They can introduce lots of challenges for, for local methods. 29 00:01:26,250 --> 00:01:28,976 And even parametric methods as well, non-local methods. 30 00:01:28,976 --> 00:01:31,460 So often we like to just reduce the, 31 00:01:31,460 --> 00:01:33,550 the raw numbers of dimensions in our input space. 32 00:01:35,320 --> 00:01:37,370 Another good thing about future selection is that it 33 00:01:37,370 --> 00:01:40,180 provides a way of revealing key relationships in the data. 34 00:01:40,180 --> 00:01:42,470 That is particular attributes that 35 00:01:42,470 --> 00:01:45,230 inform your classification or regression decisions. 36 00:01:45,230 --> 00:01:45,480 Right? 37 00:01:45,480 --> 00:01:48,220 So this is useful from an interpretive perspective. 38 00:01:48,220 --> 00:01:48,400 Right? 39 00:01:48,400 --> 00:01:50,690 If I'm trying to understand what's present in a data 40 00:01:50,690 --> 00:01:56,910 set knowing the informative features might be intrinsically or independently useful. 41 00:01:56,910 --> 00:02:01,590 Finally our goal of all of this would be to preserve the task relevant information. 42 00:02:01,590 --> 00:02:04,770 So even though we're throwing stuff away, we're hoping that the key 43 00:02:04,770 --> 00:02:08,590 relationships will still be captured by the data set after we're done. 44 00:02:08,590 --> 00:02:11,380 We're just changing the representation to make it 45 00:02:11,380 --> 00:02:14,990 more, more comfortable for our pattern recognition methods. 46 00:02:16,180 --> 00:02:22,420 All right, so every feature selection system involves two different parts. 47 00:02:22,420 --> 00:02:24,490 There's an evaluation criterion, that is how 48 00:02:24,490 --> 00:02:26,470 you answer the question whether a feature is 49 00:02:26,470 --> 00:02:29,940 good or not, or if any given set of features is, is good or not. 50 00:02:29,940 --> 00:02:31,100 How it performs. 51 00:02:31,100 --> 00:02:33,530 And then there's a search routine that you use to to explore the 52 00:02:33,530 --> 00:02:35,660 space with different feature combinations, and we'll 53 00:02:35,660 --> 00:02:36,900 talk about each of those in turn. 54 00:02:36,900 --> 00:02:41,260 We're going to start by discussing the evaluation criteria [INAUDIBLE]. 55 00:02:41,260 --> 00:02:44,250 Given some subset of features, how do I score 56 00:02:44,250 --> 00:02:49,505 that subset with respect to my pattern recognition strategy task? 57 00:02:49,505 --> 00:02:50,290 Okay. 58 00:02:50,290 --> 00:02:53,210 And there are two basic different ways of, of doing that. 59 00:02:53,210 --> 00:02:57,230 There are wrapper evaluations and filter evaluation strategies. 60 00:02:57,230 --> 00:03:00,510 So the, the wrapper strategies this is 61 00:03:00,510 --> 00:03:05,300 a general class of of feature selection routines 62 00:03:05,300 --> 00:03:07,130 that use the, they, they sort of 63 00:03:07,130 --> 00:03:09,850 envelope whatever core pattern recognition engineer you're using. 64 00:03:09,850 --> 00:03:12,430 So, same using a K-nearest neighbor approach. 65 00:03:12,430 --> 00:03:15,660 The wrapper would simply push the, the candidate set 66 00:03:15,660 --> 00:03:18,160 of features though that K-nearest neighbor and evaluate the 67 00:03:18,160 --> 00:03:20,630 performance with respect to the task using whatever task 68 00:03:20,630 --> 00:03:24,140 relevent metric we've chosen for our basic pattern recognition engine. 69 00:03:24,140 --> 00:03:25,435 In this case, it could be cra 70 00:03:25,435 --> 00:03:29,116 cross-validation error on held out data points. 71 00:03:29,116 --> 00:03:31,030 So we get our cross-validation error for a 72 00:03:31,030 --> 00:03:33,350 particular feature candidate set, and can then use 73 00:03:33,350 --> 00:03:38,240 that as a score to compare as we change the, the subset of features that we use. 74 00:03:38,240 --> 00:03:40,410 So typically, this amounts to an iterative 75 00:03:40,410 --> 00:03:43,189 approach where we try different candidate feature subsets. 76 00:03:44,220 --> 00:03:46,480 Do the entire training and testing procedure, 77 00:03:46,480 --> 00:03:47,860 with all of the leave one out cross 78 00:03:47,860 --> 00:03:49,690 validation, and all of the unbiased risk 79 00:03:49,690 --> 00:03:53,090 guesstimation that's necessary to do real pattern recognition. 80 00:03:53,090 --> 00:03:55,140 And then we evaluate our performance with those subsets. 81 00:03:55,140 --> 00:03:59,690 And, and iterate again improving our set of, of candidate 82 00:03:59,690 --> 00:04:02,700 attributes to use and until we're finally satisfied with our performance. 83 00:04:02,700 --> 00:04:04,940 And either we've reduced the, the set of 84 00:04:04,940 --> 00:04:07,820 sub, the set of, of attributes sufficiently, right? 85 00:04:07,820 --> 00:04:10,660 To the point where we can it's now tractable or we 86 00:04:10,660 --> 00:04:14,530 start to see some, the, the fall off in our performance. 87 00:04:14,530 --> 00:04:17,780 That is, we've, we've included too many features and are starting to 88 00:04:17,780 --> 00:04:21,610 hit the cursive dimensionality again, so that's the way a wrapper works. 89 00:04:22,710 --> 00:04:26,580 Filters on the other hand operate as a pure preprocessing step. 90 00:04:26,580 --> 00:04:28,480 So they have some measured performance that's 91 00:04:28,480 --> 00:04:31,320 totally different from your pattern recognition performance, right? 92 00:04:31,320 --> 00:04:32,820 It might be some measure of 93 00:04:32,820 --> 00:04:34,999 informativeness with respect to class labels. 94 00:04:36,042 --> 00:04:38,020 By some, measure it by some other model. 95 00:04:38,020 --> 00:04:42,000 And by applying that in advance, you can do the iterative 96 00:04:42,000 --> 00:04:46,120 juggle and figure out what the, the optimal subset of attributes is 97 00:04:46,120 --> 00:04:49,480 before you even bring it to your k nearest neighbors classification or 98 00:04:49,480 --> 00:04:51,130 whatever classification method you're planning on 99 00:04:51,130 --> 00:04:53,900 using ultimately to solve the problem. 100 00:04:53,900 --> 00:04:58,800 So this is basically using the intrinsic properties of the data or critically some 101 00:04:58,800 --> 00:05:02,790 other model than the pattern recognition engine 102 00:05:02,790 --> 00:05:05,439 for, that, that describes performance on the task. 103 00:05:06,660 --> 00:05:08,300 All right so, of these two I'll talk about 104 00:05:08,300 --> 00:05:11,210 error, or I'll talk about error evaluation for wrappers first. 105 00:05:12,390 --> 00:05:18,540 Like I mentioned, wrappers are a typical error analysis with a, a wrapper 106 00:05:18,540 --> 00:05:21,400 based approach would be to look at your performance on held out data. 107 00:05:21,400 --> 00:05:23,150 Leave one out cross validate. 108 00:05:23,150 --> 00:05:25,780 And the advantage of the wrapper method is that it gives 109 00:05:25,780 --> 00:05:29,430 you an accurate indicator of performance on your, your actual tasks. 110 00:05:29,430 --> 00:05:33,320 So you'll know that the, the subset you select is actually the best 111 00:05:33,320 --> 00:05:39,350 performer at the, the ultimate pattern recognition task you, you intend to solve. 112 00:05:39,350 --> 00:05:42,460 however, there are some disadvantages to the wrapper method too. 113 00:05:42,460 --> 00:05:45,560 One major disadvantage is the computational complexity. 114 00:05:45,560 --> 00:05:48,690 And this is especially true if you're, you're 115 00:05:48,690 --> 00:05:52,980 pattern recognition method is really inefficient or computationally expensive. 116 00:05:52,980 --> 00:05:56,350 If your training and test procedure involves weeks of training on a super 117 00:05:56,350 --> 00:06:00,360 computer cluster, you might not be able to try with many combinations of attributes. 118 00:06:00,360 --> 00:06:04,910 It might just not be feasible to from a time and resource 119 00:06:04,910 --> 00:06:10,180 perspective, to do that training, at which point wrappers become less desirable. 120 00:06:10,180 --> 00:06:12,040 Also there's this issue of specificity. 121 00:06:12,040 --> 00:06:15,020 So it could be that because these are very, 122 00:06:15,020 --> 00:06:19,430 finely tuned to the particular pattern recognition method you're using 123 00:06:19,430 --> 00:06:22,040 it could be that they don't reveal anything intrinsic about 124 00:06:22,040 --> 00:06:25,800 the data itself but are you're simply adjusting the attributes 125 00:06:25,800 --> 00:06:29,320 according to the properties of your pattern or recognition engine 126 00:06:29,320 --> 00:06:32,810 rather than the data itself so they're very specific is 127 00:06:32,810 --> 00:06:34,470 another way of saying that and if you change the 128 00:06:34,470 --> 00:06:37,110 underlying classifier you may have to chose a new set 129 00:06:37,110 --> 00:06:39,260 of attributes which involves a new. 130 00:06:40,950 --> 00:06:42,670 Iterative procedure to do that. 131 00:06:42,670 --> 00:06:45,560 So, so wrappers, can be very accurate 132 00:06:45,560 --> 00:06:47,670 but they also come with these important disadvantages. 133 00:06:49,940 --> 00:06:52,850 So, moving now to filters. 134 00:06:52,850 --> 00:06:55,010 So, if you instead use a filter or 135 00:06:55,010 --> 00:06:58,070 a pre-processing approach, they're all sorts of different criteria, 136 00:06:58,070 --> 00:07:01,240 sort of generic criteria that you can use, to 137 00:07:01,240 --> 00:07:04,350 judge whether an attribute or a set of attributes. 138 00:07:04,350 --> 00:07:06,040 Gives you information about the target 139 00:07:06,040 --> 00:07:09,230 class label or, ordinate for regression problem. 140 00:07:09,230 --> 00:07:13,460 And these can be the K-S Test, a traditional, K-S Test. 141 00:07:13,460 --> 00:07:16,120 The Pearson Correlation Score is, is often used. 142 00:07:16,120 --> 00:07:18,860 So you simply find, a, a subset 143 00:07:18,860 --> 00:07:21,830 of features with a, a good Pearson Correlation. 144 00:07:21,830 --> 00:07:24,010 the mutual information is a method basically 145 00:07:25,340 --> 00:07:27,440 a measure from information theory that measures 146 00:07:27,440 --> 00:07:29,560 the amount of bits of information that 147 00:07:29,560 --> 00:07:31,990 some subset of features provides about your 148 00:07:31,990 --> 00:07:37,430 class label or you could use the fisher score all of these are valid 149 00:07:37,430 --> 00:07:39,040 filter criteria that you could apply that 150 00:07:39,040 --> 00:07:41,720 are kind of independent of your classification model. 151 00:07:41,720 --> 00:07:46,030 And advantages to using a filter approach is basically computational. 152 00:07:46,030 --> 00:07:50,120 When you can apply the full pattern recognition method 153 00:07:50,120 --> 00:07:53,990 in its entirety on multiple runs of, through the data. 154 00:07:53,990 --> 00:07:58,210 Then, you can, apply this preprocessing step and reduce the number of 155 00:07:58,210 --> 00:08:00,770 attributes at the outset right, which 156 00:08:00,770 --> 00:08:04,290 saves you from the curse of dimensionality. 157 00:08:04,290 --> 00:08:06,270 The disadvantage of course is that you're sort 158 00:08:06,270 --> 00:08:09,420 of positing some new measure of performance, then diff, 159 00:08:09,420 --> 00:08:11,800 that's different from what you ultimately want to evaluate 160 00:08:11,800 --> 00:08:15,450 so it implies some new potentially redundant model right. 161 00:08:15,450 --> 00:08:18,060 So, which raises the question why are we going through all of 162 00:08:18,060 --> 00:08:21,550 this extra work of building a whole new model for our data. 163 00:08:21,550 --> 00:08:23,400 A whole new performance metric when really what 164 00:08:23,400 --> 00:08:25,639 we're interested in is our [UNKNOWN] nearest neighbor classification. 165 00:08:27,720 --> 00:08:30,510 I want to talk about one other specific filter ap, 166 00:08:30,510 --> 00:08:33,670 approach based on the conditional mutual information because this is 167 00:08:33,670 --> 00:08:37,340 sort of emblematic of, of a bunch of useful filtering 168 00:08:37,340 --> 00:08:41,510 criteria from information theory and it seems to perform pretty well. 169 00:08:41,510 --> 00:08:45,830 So this is flora at all journal and machine research 2004 but then 170 00:08:45,830 --> 00:08:50,210 again like I said it's reminiscent of lots of mach, of information theoretic. 171 00:08:50,210 --> 00:08:52,510 Measures of, of performance that are used 172 00:08:52,510 --> 00:08:55,630 in, in different filtering approaches to feature selection. 173 00:08:55,630 --> 00:08:59,050 So here, we have a score that's defined on the left-hand side of the equation. 174 00:08:59,050 --> 00:09:00,920 And to, it's called the Conditional Mutual 175 00:09:00,920 --> 00:09:03,730 Information which basically measures the amount of 176 00:09:03,730 --> 00:09:08,370 new information that some new attribute A sub I provides about the class liberal Y. 177 00:09:09,500 --> 00:09:12,340 Given the data that we've, or given the attributes 178 00:09:12,340 --> 00:09:14,920 already in the set, that is the attribute set A. 179 00:09:14,920 --> 00:09:19,160 And this is defined as follows on the right side. 180 00:09:19,160 --> 00:09:21,270 So we're actually looking at two different entropies. 181 00:09:21,270 --> 00:09:23,960 The entropy as here written using capital H and the 182 00:09:23,960 --> 00:09:28,510 entropy describes, it's a measure of uncertainty about a distribution. 183 00:09:28,510 --> 00:09:31,430 So we're measuring the uncertainty about the distribution of class 184 00:09:31,430 --> 00:09:36,250 labels y, given our current set a of attributes and then 185 00:09:36,250 --> 00:09:41,350 subtracting the entropy of y given the joint, or rather 186 00:09:41,350 --> 00:09:45,990 the values of the candidate feature in our attribute set together. 187 00:09:45,990 --> 00:09:50,180 And you can expand the conditional entropy in the following way. 188 00:09:50,180 --> 00:09:51,995 it's, this, these are again just 189 00:09:51,995 --> 00:09:55,690 straight-up definitions from the information theory literature. 190 00:09:55,690 --> 00:09:59,470 it, and it gives us basically the number of bits of new 191 00:09:59,470 --> 00:10:02,220 information that this candidate feature will 192 00:10:02,220 --> 00:10:04,640 provide with respect to our class label. 193 00:10:04,640 --> 00:10:08,420 So this is a particularly useful and high performing filter 194 00:10:08,420 --> 00:10:13,410 function that doesn't presume any knowledge of the ultimate classification. 195 00:10:13,410 --> 00:10:15,440 Method that you're going to use of course it requires 196 00:10:15,440 --> 00:10:19,090 that you're able to estimate the probability densities so it does 197 00:10:19,090 --> 00:10:22,670 require some kind of probability modeling there but provided you can 198 00:10:22,670 --> 00:10:26,140 do that then this is a fairly straightforward approach to use 199 00:10:28,180 --> 00:10:29,910 okay so now that i've talked about different 200 00:10:29,910 --> 00:10:32,900 evaluation criterion I want to describe the search routine 201 00:10:32,900 --> 00:10:35,050 you use for exploring different subsets of attributes 202 00:10:35,050 --> 00:10:39,100 different subsets of features probably the most common one. 203 00:10:39,100 --> 00:10:41,100 Is called a greedy forward search. 204 00:10:41,100 --> 00:10:44,380 And this is, you can think of this like a solid bar, where you start off 205 00:10:44,380 --> 00:10:46,070 with an empty plate and just add things 206 00:10:46,070 --> 00:10:47,990 one at a time according to whatever looks best. 207 00:10:47,990 --> 00:10:51,280 So formally speaking, you start with an empty feature set. 208 00:10:51,280 --> 00:10:55,910 This is A starts as an all set, which is, A is our set of attributes here. 209 00:10:55,910 --> 00:10:59,500 And We iterate adding at each step the, 210 00:10:59,500 --> 00:11:01,710 the best performing feature to our data set. 211 00:11:01,710 --> 00:11:03,770 So this, this involves a bunch of nested loops 212 00:11:03,770 --> 00:11:06,360 while our performance is still improving, we look through 213 00:11:06,360 --> 00:11:08,180 all of the candidate features that we have remaining, 214 00:11:08,180 --> 00:11:10,620 that is all of the times on the salad bar. 215 00:11:10,620 --> 00:11:15,160 We add, we, we try adding that candidate, feature to our dataset. 216 00:11:15,160 --> 00:11:16,920 And then evaluate our performance using our 217 00:11:16,920 --> 00:11:19,540 performance criterion that, that I mentioned before. 218 00:11:19,540 --> 00:11:22,240 Either a wrapper or a filter method, and based 219 00:11:22,240 --> 00:11:25,360 on that, we figure out which is our best overall. 220 00:11:25,360 --> 00:11:26,880 Feature to add to the data set. 221 00:11:26,880 --> 00:11:30,700 And we append it to our, our feature set and then continue iterating, looking 222 00:11:30,700 --> 00:11:35,390 for the next best feature to add given the one that we, we've already established. 223 00:11:35,390 --> 00:11:39,480 So this, again, continues as long as we want to. 224 00:11:39,480 --> 00:11:41,460 Until either performance starts to suffer, or 225 00:11:41,460 --> 00:11:44,230 we start encountering the, the curse of dimensionality. 226 00:11:44,230 --> 00:11:47,080 We've grown our attribute set too high. 227 00:11:47,080 --> 00:11:49,320 And the, it's called the greedy method because of [UNKNOWN] 228 00:11:49,320 --> 00:11:52,510 at, at each step we're trying to maximize our performance gain. 229 00:11:52,510 --> 00:11:54,990 So it's not always optimal. 230 00:11:54,990 --> 00:11:56,640 And in particular, if there are pairs of 231 00:11:56,640 --> 00:11:59,690 features that are together very informative but independently not 232 00:11:59,690 --> 00:12:01,940 that informative, we're not going to catch that relationship 233 00:12:01,940 --> 00:12:03,950 here because we're [UNKNOWN] we're just adding the next. 234 00:12:03,950 --> 00:12:06,630 Best feature at every iteration. 235 00:12:06,630 --> 00:12:08,920 That said greedy forward search usually 236 00:12:08,920 --> 00:12:11,350 works pretty well for most practical problems. 237 00:12:11,350 --> 00:12:13,020 And that's a good place to start. 238 00:12:13,020 --> 00:12:16,590 It also has the advantage that's pretty computationally efficient. 239 00:12:16,590 --> 00:12:18,810 Because you're starting with very few attributes right. 240 00:12:18,810 --> 00:12:21,340 So those early computations that you do. 241 00:12:21,340 --> 00:12:25,460 It will be pretty cheap to perform, because, the, the attribute 242 00:12:25,460 --> 00:12:28,920 factor is fairly low, you're working with a very low dimensional problem. 243 00:12:28,920 --> 00:12:31,490 Alright, and you can carry that on for as long as you want. 244 00:12:31,490 --> 00:12:34,040 So that's one example of a simple search strategy. 245 00:12:35,050 --> 00:12:37,650 Here's another search strategy you might want to use. 246 00:12:37,650 --> 00:12:38,390 the. 247 00:12:38,390 --> 00:12:41,970 Obviously, if we, we're starting with forward search, the converse of 248 00:12:41,970 --> 00:12:44,520 that would be a backwards elimination, where we start with a full 249 00:12:44,520 --> 00:12:48,250 set of features, and then at each step, we figure out 250 00:12:48,250 --> 00:12:52,360 which one we want to eliminate in order to best improve performance. 251 00:12:52,360 --> 00:12:59,240 So again, this, this starts off with you can see on the, the formal algorithm 252 00:12:59,240 --> 00:13:00,730 there on the, the left side, we're starting 253 00:13:00,730 --> 00:13:02,300 off with features 1 through a sub n. 254 00:13:02,300 --> 00:13:05,200 Right, so we start off with the full set. 255 00:13:05,200 --> 00:13:08,880 and then if i wait one candidate at a time eliminating 256 00:13:08,880 --> 00:13:12,380 it evaluating our Sarah cross validation arrow or our raptor metric and 257 00:13:12,380 --> 00:13:16,540 then removing it from the data set now this has some disadvantages 258 00:13:16,540 --> 00:13:19,760 because obviously we are susceptible immediately 259 00:13:19,760 --> 00:13:21,580 susceptible to the curse of dimensionality. 260 00:13:22,610 --> 00:13:28,620 It is impractical for many circumstances where it will fail utterly for the full 261 00:13:28,620 --> 00:13:32,810 set of features and it will be impossible to get any meaning full performance. 262 00:13:32,810 --> 00:13:34,290 score out of that. 263 00:13:34,290 --> 00:13:36,420 We will also incur all the computational 264 00:13:36,420 --> 00:13:39,600 cost of working with the full attributes sets. 265 00:13:39,600 --> 00:13:42,250 So that's a major disadvantage the backwards elimination. 266 00:13:42,250 --> 00:13:44,470 But if you can do it, if you can hack it, 267 00:13:44,470 --> 00:13:48,790 backwards elimination can be good because it actually lets you capture 268 00:13:48,790 --> 00:13:52,650 relationships between pairs of features that you might miss if you're 269 00:13:52,650 --> 00:13:56,250 just adding one feature at a time from an empty set. 270 00:13:56,250 --> 00:13:59,450 So their, they each have their own advantages depending on 271 00:13:59,450 --> 00:14:02,290 the computational properties of your algorithm and the data set. 272 00:14:03,880 --> 00:14:04,150 Okay. 273 00:14:04,150 --> 00:14:07,020 I also want to briefly touch on some options for non-greedy search. 274 00:14:07,020 --> 00:14:08,970 There are here just a few but there are 275 00:14:08,970 --> 00:14:12,730 lots more on people of proposed simulated annealing approaches. 276 00:14:12,730 --> 00:14:15,790 You can think of simulated as, annealing as a stochastic search, where 277 00:14:15,790 --> 00:14:19,600 you search randomly throughout the data set and perturb your candidate list. 278 00:14:19,600 --> 00:14:22,540 According to some temperature term that decreases over time. 279 00:14:22,540 --> 00:14:26,080 So very early on you're going to be searching wildly, 280 00:14:26,080 --> 00:14:31,530 right, and jumping through, wildly differing, candidate sets of attributes. 281 00:14:31,530 --> 00:14:34,810 And then as the temperature reduces, you'll settle in to some 282 00:14:34,810 --> 00:14:38,280 local maximum, right, where it has a good combination of features. 283 00:14:38,280 --> 00:14:41,510 And you can think of this as a non-greedy search approach. 284 00:14:41,510 --> 00:14:44,760 People have proposed branch and bound search algr, algorithms, 285 00:14:44,760 --> 00:14:47,480 as well as genetic algorithms for future selection too. 286 00:14:47,480 --> 00:14:53,270 So it's more generally just any non-convex, communitorial, optimization 287 00:14:53,270 --> 00:14:58,350 engine is a candidate for some sort of feature selection algorithm. 288 00:14:58,350 --> 00:15:01,540 And there are lots of non greedy methods to consider. 289 00:15:01,540 --> 00:15:01,730 Okay. 290 00:15:01,730 --> 00:15:06,110 So in summary, every feature selection offered them has a couple parts. 291 00:15:06,110 --> 00:15:07,610 It has an evaluation criterion. 292 00:15:07,610 --> 00:15:10,140 And we've talked about wrapper and filter evaluation methods. 293 00:15:10,140 --> 00:15:12,470 And it also has a search strategy. 294 00:15:12,470 --> 00:15:15,070 And we talked about greedy forward and greedy backwards 295 00:15:15,070 --> 00:15:18,900 elimination as [UNKNOWN] different searches that, that you can try. 296 00:15:18,900 --> 00:15:20,280 So this gives us a, a lot of 297 00:15:20,280 --> 00:15:23,400 options to choose from for our feature selection strategy. 298 00:15:23,400 --> 00:15:25,260 In the next module we'll be talking 299 00:15:25,260 --> 00:15:28,830 about some other methods for dimensionality reduction. 300 00:15:28,830 --> 00:15:31,300 We'll actually use the full set of features but still have 301 00:15:31,300 --> 00:15:34,490 the end, desired result of reducing the total dimensionality of the dataset.