# 11. Learning: Identification Trees, Disorder

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=SXBG3RGr_Rc
**Transcript page:** https://www.withtranscript.ai/video/SXBG3RGr_Rc

## Chapters

- 0:09 — Chapter 1 (0:09)
- 3:11 — Chapter 2 (3:11)
- 4:05 — Chapter 3 (4:05)
- 6:41 — Chapter 4 (6:41)
- 12:12 — Chapter 5 (12:12)
- 14:03 — Chapter 6 (14:03)
- 16:43 — Chapter 7 (16:43)
- 18:33 — Chapter 8 (18:33)
- 23:05 — Chapter 9 (23:05)
- 26:01 — Chapter 10 (26:01)
- 32:23 — Chapter 11 (32:23)
- 33:45 — Chapter 12 (33:45)
- 39:48 — Chapter 13 (39:48)
- 47:08 — Chapter 14 (47:08)

## Transcript

**[0:09]:** ladies and gentlemen of the Romanian national anthem I did not ask you to stand because I didn't play it as a symbol of Romanian national identity but rather to celebrate the end of the Cold War which occurred about the time that you were born before that uh no one came to MIT from Eastern Europe but since that time we we've been blessed by having uh in our midst uh lithuanians estonians Poes Czechs slovaks bulgarians Romanians uh slovenians serbs and all sorts of people from regions of the world formerly excluded uh to us believe me you are all welcome in our house almost all that is to say because uh you may recall that Romania is the traditional home of vampires and since the end of the Cold War vampires have had new vectors for emerging from their traditional places and penetrating into the World At Large you may have a vampire in your Suite or

**[1:20]:** on your floor and it uh it's important to know how to uh to recognize them and take the necessary precautions so if uh you uh have a this concern uh I would expect that the first thing you would do would be to look at some data concerning the characteristics uh of

**[1:54]:** vampires so there's a little database of uh samples of individual uals who have been determined to be uh vampires and not vampires and our task today and what you'll understand how to do by the end of the hour is to use data like this to build a recognition mechanism that would help you to identify whether someone is a vampire or an ordinary person so this is a little different uh from uh the kind of problem we worked with uh with neural Nets right so what's what's the most conspicuous difference between this data set and anything you could think to work on with the did I say no nearest neighbors nearest Neighbors which we studied last time Katie do you have any thoughts about why it would be difficult to use nearest neighbors with data like this oh by the way the question mark is there because uh this is MIT and a lot of people

**[2:51]:** are completely nocturnal so you can't tell whether they cast a shadow or not we want to take that into account so what's different about this from the uh electrical cover data

**[3:11]:** set you use if you use the nearest neighbor technique to identify vampires with this

**[3:24]:** data it's so obvious you overlook it it say yes Wana you

**[3:34]:** expert oh that's the problem this is not numerical data this is symbolic so we're not saying that your ability C Shadow is point7 you either cast a shadow don't cast a shadow or we can't tell it's a symbolic result so uh problem number one that we have to face with data of this kind is that it's non-numeric

**[4:05]:** and there are other characteristics as well uh for example it's not clear that all of these characteristics actually matter so some characteristics don't

**[4:25]:** matter and a corlar to that is that some characteristics do matter but they only matter part of the

**[4:51]:** time and finally there's the matter of cost some of these test may be more expensive to perform than others for example if you wanted to determine whether someone cast a shadow you'd have to go to the trouble of getting up during daylight that might be an expensive operation for you you'd have to go find some garlic and ask them to eat it that might be expensive so some of these tests might be expensive relative to other tests but once you realize that we are talking in terms of tests and not a vector of real values then what you do is clear you build yourself a little tree of tests so who knows how this Pro problem will turn out but you can imagine a situation where you have one test up here which might have three outcomes and one of those outcomes might require one but only one of those outcomes might require you to

**[5:57]:** perform another test and only when you've created a tree of tests that look like this are you finished so given a set of tests and a set of samples the question becomes how do you arrange the tests in a tree like that so as to do the identification that you want to do so since we're talking about identification it's not surprising that this kind of tree is called an identification tree

**[6:41]:** and there's a tendency and I may slip into it myself to call this a decision tree but a decision tree is a label for something else this is an identification tree and the task is to create a good one so what is a good one versus a not so good one what characteristic would you like for a decision tree for an identification tree to have if you're going to call it a good identification tree what do you think Krishna what would be a good characteristic minimum number yeah he said minimum number of levels what's another way you could say what a good one is uh each test costs something right so what's another way of thinking about what a good tree would look like the minimum cost and if they all have the same cost that it's the minimum number of tests so overall what you like is a small tree rather than a big

**[7:46]:** one so you might be able to take your sample data and divide it up so that at the bottom of the tree at the leaves all of the sets that are produced by the test are are are uniform homogeneous but you like that tree to be the simplest possible tree that you can find not some big complicated one that also divides up all the data into uniform subsets by uniform subset you know at the bottom of the tree you like have all of have all of the vampires together and all the non vampires together right so you're like a small tree so why not just go all the way and do British Museum and calculate all possible trees well you can do that but it's one of those NP problems and as you know NP problems suck in general and and so you don't want to do that you want have some kind of Uris

**[8:37]:** mechanism for building a small tree and and and we want a small tree because what do we want a small tree oh because of the cost but there's another more important reason why we want a small tree let me give you a hint it's aam's razor the simplest explanation is often the best explanation so if you have a big complicated explanation that's probably probably less good than uh a simple small explanation aam's razor spelled so many ways it doesn't matter how I spell it and that's good because I can't spell so I don't know how are we going to go about finding the best possible arrangement of those four tests in a tree like that well step one uh will be to see what each test does with the data and by the way before I go a step further you know and I know that this is a sample data set that's very small

**[9:40]:** suitable for classroom manipulation you'd never Bet Your Life on a data set that's small we use it only for classroom illustration but imagine that these rows are multiplied by 10 so that instead of 80 samp instead of eight samples you got 80 then you might begin to believe the results that are produced so I'm just going to pretend that each one of those represents um uh 10 other samples that I haven't bothered to show but we can work with this one uh in the classroom because it's pretty small and we can say well what does the shadow test do well the shadow test divides the sample population into three groups there's the I don't know group of people who are nocturnal there are the people who do cast The Shadow the yes people and the people who do not not cast a shadow of the no people so if I look at at those rows

**[10:34]:** up there and see which ones are vampires it looks to me that if they do not cast a shadow there's no shadow cast there's only one that doesn't cast a shadow and and that is a

**[10:50]:** vampire so that's a plus over there vampire now if we look at the ones who who uh do cast a shadow all of those are not vampires they're all

**[11:04]:** okay and now they're eight three are vampires so that means that two of these must be vampires and I've got three four five six so far so there must be two left so that's the way the shadow test divides up the data now let's do

**[11:24]:** garlic vampires traditionally don't eat garlic I don't know why so we look at the garlic test and we see that um all of the nose are there only three yeses and they're all and they all produce a no answer so if they eat if somebody eats garlic they're not vampires that means the three vampires must be over here then there are two left so that's what the garlic test does see what we're trying to do is we're trying to look at all these tests to see which one we like best on on basis how it divides up the the data so now we've got uh I don't know uh

**[12:12]:** complexion and there are three choices for this you can have an average complexion but a lot of vampires in my experience are rather pale so pale is a possibility and then the other option is that just after gorging themselves with blood they tend to get a little red in the face so we'll have a ready over here once again we have to go back to our data set to see how um this test divides things up so there are three re's and one's a no one's a no and one's a yes so two Nos and a yes two Nos and a yes now we can try for pale complexion people there are only two of those a no and a o

**[13:03]:** that must mean that uh there are two pluses over here because there are three vampires Al together 2 4 6 7 8 nine oh eight sorry eight only eight oh just one more to go and that's the accent historically vampires go to Great uh length to uh perfect their uh accent and and not betray their Origins but nevertheless we can expect that uh if they've just arrived if they're just in from Transylvania part of Romania they may still have an accent so there's a normal some still have a heavy accent and some persist in having odd

**[13:49]:** accent so let's see accent uh four of them right at the top have no accent two Nos and a yes

**[14:03]:** heavy Accent three of those a yes and two

**[14:12]:** NOS that means we must have a plus here 3 six plus and a minus so we can look at this uh at this data and say well what would be the best test to use and the best test to use would surely be the one that produces produces subsets or produces sets here at the at the bottom of the of the branches that uh correspond to the outcomes of the test we're looking for a test that produces homogeneous groups so just for the sake of illustration I'm going to suppose that we're going to judge the quality of a test by how many sample individuals it puts into a homogeneous set so we want to we want to ideally would like a test that would put all the vampires in one group and all the Ordinary People in another group right off the bat but there are no such tests but we can add up the

**[15:08]:** number of sample individuals who are put into at least homogeneous sets so when we do that this guy has three in a homogeneous set here a fourth but these are not in a homogeneous set so the overall score for this guy will be four this one one well not quite as good it only puts three individuals in homogeneous

**[15:37]:** set this one here two individuals into a homogeneous set everybody else is uh in all mixed up with some other kind of person and over here how many people are in a how many samples are in a homogeneous set

**[15:54]:** zero so on a basis of this analysis you would conclude that the ordering of the test with respect to their quality is left to right so the best test must be the shadow test so let's pick the shadow test first see what we can do with that if we pick the shadow test first then we have this arrangement we have question mark and we have yes cast a shadow and no doesn't we have three minuses here we have a plus here and unfortunately over here we have plus plus minus minus so we need another test to divide that group up yes

**[16:43]:** didow well if I look at the data and I see who uh we haven't the question is what about that shadow test if you look at the shadow test you say well there are four question marks and if we look at see what kind of people belong to those four question marks there are two vampires and two non vampires that's why it's two pluses and two minuses no I understand that question is how did you get to the score I SC yeah no I'm I'm scoring this the question is how did I get this number four it's not has nothing to do with this because it's a mixed set in fact I've got three guys in a homogeneous set here and one guy in a homogeneous set here and I'm just adding them up okay so very simple classroom illustration wouldn't work in practice yes how do you adjust this for larger data sets where

**[17:27]:** it's un you're going the question is how do I adjust this for larger data sets you're one step ahead okay thank you so um uh I trust me I'll be dealing with large data sets in a moment I just want to get get the get the idea across and I don't want there to be any thought that the method we use for larger data sets got anything magic about it okay so we're off from running and now we have to pick a test that will divide those four guys up so we're going have to work this a little harder and repeat the analysis we did there but at least it'll be simpler because now we're only considering four samples not eight just the four samples that we still have to divide up that have come down that left Branch so we have the shadow

**[18:17]:** test it has three outcomes we have the garlic test it has two outcomes yes and no we have the complex

**[18:33]:** test there three outcomes average pale and Ruddy and we have finally the accent test and that comes out to be either normal heavy or odd and now it's a little awkward to figure out what the results are for the this set data set as shown so let me just um strike out the ones that we're no longer concerned with and limit our analysis to the samples for which the outcome of the Shadow test is a question mark this is exactly the four people we still need to separate all right so switching colors keeping the color the same uh we uh actually don't want to do the shadow test anymore right because we've already done that so there's no point in doing that again we don't have to look at that it's already done all the division of data that it can so the garlic test well let's see garlic two yeses two NOS the yeses

**[19:36]:** produce nose and the nose produce yeses so if the person does eat garlic they're okay and if they don't e garlic bad news they're vampires that looks like a pretty good test but just for the sake of working it all out let's try the others complexion two readies a yes and a no

**[20:05]:** one pale and that's a no one pale and that's a no and we must have one average and sure enough that's a yes now we can do accent the one on the far right and look at how that measures up against the uh people who are still under consideration as samples accent let's see two nuns a yes and a no two heavy or one heavy no Heavies two odds a yes and a no all right so now we can do the same thing we did before and just say for sake of uh classroom illustration how many uh individuals are put into homogeneous sets and here we have four and here we have two and here we have zero so plainly the garlic test is the test of choice so we go back over here and we've completed the work that we needed to do so that's a garlic test and that produces two pluses let's

**[21:13]:** see each garlic yes each garlic no I guess the pluses go over here like so and these are the two Ordinary People and we're done with our task and now you can quickly run off and put this into your PD PDA and forever be protected against possibility one of those vampires got out and that flood of people came in from Easter Europe except what do we do with a large data set well trouble is a large data set is not produce put any no no test at the beginning of a large data sets likely to do the do the job for any if you have a large data set no test is likely to put together any homogeneous set right off so you never get started everything would be zero every test would say oh it doesn't put any anybody into homogeneous set So you you're screwed you need some other way you have some

**[22:10]:** other you need some other more sophisticated way of measuring how disordered this data is or how disordered these sets are that you find at the bottom of the tree branches that's what you need you need a way of measuring disorder of these tests you of these sets that you find at the bottom of these branches so you can find a kind of overall quality to the test based on your measurement of disorder now the first aristic of um a good life is when you have a problem to solve ask somebody who knows the answer it's the least amount of work it's not even as hard as going to Google so who would you ask uh about measures ways of measuring disorder in sets there are two possible

**[23:05]:** answers entropy what find the entropy find the entropy what what who who who studies entropy probability what kind of what class of like physics thermodynamics thermodynamics the thermodynamics are good at measuring disorder because that's what thermodynamics is all about entropy increasing over time and all that sort of stuff there's another answer there's another equally good answer statisticians uh statisticians perhaps but it's not the best second best answer it's actually not even the best answer that's the best answer what's your name Leo Leon oh you're Leon yeah I don't know Leonardo has got his finger on it the information theorists are pretty good at measuring disorder because that's what information is all about too so uh we might as as well borrow a mechanism for measuring the disorder of a set from those information Theory guys so what we're going to do is exactly that let's put it over here so we'll have a have it handy when we want to try to measure those things

**[24:14]:** what they say is uh The Gospel According to uh to information theorists is that the disorder D of some set is equal so now let's suppose that this is a set of uh of binary values so we have positives and we have negatives pluses and minuses but pluses they don't go very well in an algebraic equation because you might be confused with adding so I'm going to say p and p and n and then there'll be the total which is p plus n we only have two choices positive and negative so the disorder of a set according to those guys is equal to minus the um number of POS poses over the total number times the log to the base 2 of the positives over the total minus the negatives over the total time the log 2 of the negatives over the total those negatives look a little worrisome because you think well maybe this

**[25:19]:** thing can go negative but that's not going to be true right because these ratios are all less than one and the logarithm of something that's less than one is negative so we're okay so that's a lovely way of measuring uh disorder and maybe we got to draw a graph of what that curve looks

**[25:43]:** like and what we're going to graph it against is the ratio of positives to uh the total number so that's going to be uh an axis where we go from zero to one

**[26:01]:** so uh I don't know uh let's just find a couple of uh useful values and by the way pay P to pay attention to these curves because if you if you pay attention to this stuff you can work the quiz questions on this very rapidly otherwise you you know we see people getting out the calculators and quickly becoming both lost and screwed okay so let's see uh let's suppose that the number of positives is equal to the number of negatives so we got a completely mixed up set it has no bias in either direction so in that case if P of t p over T is equal to 12 then this is equal to - 12 times the logarithm of 12 and I guess since they're both the same we can multiply by two and what's that value

**[27:01]:** minus what is that calculate out to minus log half sign well with a minus sign you just turn the argument upside down so it's log two so what's log two base log logarithm of base two of two one so this whole thing this whole thing is one so manasa in her soft voice says well let's see uh 2 * a half that cancels out the minus that flips the argument so it's log to the base 2 of one of two and that's one so this whole thing it works out you work out the algebra it gives you one so that's cool so right here in the Middle where they're equal we get a value of one next thing we need to do is let's calculate what what happens if um p/ T is equal to one that is to say everything is a positive any guesses maybe 10 20 minus 15 let's work it out

**[28:08]:** so that would be if uh P of tal p p p of over t equal 1 that would be -1 * the log to the base 2 of 1 what's that that's zero oh yeah because two raised to the one is Z two rais to the Z is one so this part is zero now what about this other part we have minus if P if everything's a p then nothing's an N so we got zero and we can quit already well not quite we ought to work it out log to the base 2 of zero what's that who minus infinity uhoh 0 * minus INF Infinity is what I didn't get that when I was in high school finally 1801 makes a difference right finally how what's the answer well we're interested in the limit uh as n /t goes to zero right and when you have a deal like this what do you do

**[29:20]:** you use that famous rule that we all mispronounce when we see it written right we use good L hospitals rule okay it's Lile lile's rule you have to differentiate uh the U I guess we differentiate this guy uh as a ratio or something and see what happens when it goes to zero and what we get when we use lal's rule is that oh thank God this is still zero so now we know that we have a point up there and a point down there so now we've got three points on the curve and we can draw it goes like that no it doesn't go like that it's obviously a gaussian right because everything in nature is could you put that laptop away please everything in nature is a gaussian so it looks like

**[30:17]:** this that right no actually not everything in nature is a gaussian and in particular this one isn't a gaussian either it looks more like a one of those metal things I used to call quantit Huts that's what it looks like boom like so so that is the curve of Interest now did God say that using this way of measuring disorder was the best way no God hasn't not has not um has not uh indicated any choice here we use this because it's a convenient mechanism it seems to make sense but in contrast to the it's used information Theory it's not the result of some elegant mathematics it's just a borrowing of something that seems to work pretty well any of those curves would work just about the same because all we're doing with it is measuring how disordered it set is so one thing to note here is that in this situation where we're dealing

**[31:19]:** with two choices p and N positives and negatives we get a curve that maxes out at one and notice that it kind of gets up there there pretty fast in fact if you're down here at 2/3 and you go up here this is about .9 so quite quite a bit of the gives you a large number for quite a bit of that area in the middle so that unfortunately still doesn't tell us everything we need to know that tells us how to measure a disorder in one of these sets but we want to know how to measure the quality of the test overall so we need some mechanism that says okay given that this test produces three different sets and we know how to measure the disorder in each of these sets how do we measure the quality overall quality of the test well you could just add up the disorder let's write that down

**[32:15]:** because that sounds

**[32:23]:** good so you can say that the um we'll call it the quality of a test is equal to some sum over the sets

**[32:40]:** produced and what we're going to do is we're going to add up the disorder of each of those sets and we're almost home except that this means that we're going to give equal weight to a little to to a branch that has almost nothing down it as we do with a for we're going to handle give the same weight to that as a as a branch has almost everything going down it so that doesn't seem to make sense so one one final flourish is we're going to waight this sum according to the fraction of the samples that end up down that Branch so it's as usual easier to write it down and to say it so we're going to multiply that times the number of samples

**[33:33]:** and the set divided by the number of

**[33:45]:** samples

**[33:49]:** handled by a test so if half the samples go down a branch and if that branch has a certain disorder then we're going to multiply that disorder times 1/2 all right so now let's see how it works with our sample problem well here is our sample data and we didn't need anything fancy for it but let's pretend it was a large data set well let's see what will we do we'll go down uh this way uh there four samples down that direction that's half of the total number of samples so whatever we find out down there we're going to multiply by a half this one we're going to multiply by 38 and this one we're going to multiply by 1/8 now what do we actually find at the bottom of these things well here's a homogeneous set everything's the same so if we go to that curve and say what what is the disorder of

**[34:44]:** a homogeneous set is

**[34:49]:** zero oh let's see they're all the same I guess that means it's zero over there so the disorder of this set of three samples is zero the disorder of this set of one sample all the same is zero the disorder of this set well let's see half of the individuals there half of the samples there are plus and half are minus so we go over to our curve and we say what's the disorder of something with the equal mixture of pluses and minus and is and that's one so the disorder of this guy is one so now we've got 1/2 * 1 and 38 * 0 1/8 * 0 so that this order of this particular the quality of this particular test as determined by the disorder of the sets that it produces is 1 12 0.5 all right uh let's do this one so we have 38 coming down this way 58 coming down

**[35:54]:** this way 38 is multiplied by the disorder of a set of uniform things that's disorder zero so this guy over here let's see that's two fifths and 3 fifths multiply you know this is one of those deals where if you look at the curve you know you're you're pretty close to the middle and that curve goes all the way up to about 0. n there so you can kind of just look at this and Eyeball it and say well uh whatever it is it's going to be the the overall this is this is going to be something multipli time 5/8 something like .9 * 58 so let's just say for the sake of discussion that that's going to be about 6 which is within 100th I think of being right just kind of guessing Okay well now we're on a roll here we have 38 coming down this Branch 38 coming down this Branch one4 coming down this Branch this is zero and this is one of those deals where these two are about 0.9 so it looks like it's going

**[36:59]:** to be 38 + 38 is 34 times about 0.9 so that's going to turn out to be

**[37:12]:** about

**[37:16]:** 7 okay so one last go here 38 38 and 1/4 oh that's that's interesting because these two are what we got contributed up to that 7 this one is4 time this is evenly divided so that's going to have a disorder of of one so that's going to be 2.25 bigger than the number we got over here so that's going to end up being about

**[37:50]:** 0.95 so thanks God our answer is the same as we got with our simple classroom measurement of disorder except this measuring how disorder stuff is so we want the small number not the big number so once again based on this analysis we'll be sure to pick the shadow test because 0.5 is less than 6 Which is less than 7 Which is less than 095 so that accent test is really horrible don't use it just because somebody has a heavy accent doesn't mean they're a vampire in fact most vampires have worked very hard on their accent as I mentioned before all right so now we know that we're still going to pick the shadow test as our first go so that's good now let's see if we can repeat the exercise with our second selection the one that we have to have to pick those guys apart and this is going to be easier because uh

**[38:42]:** there are fewer things to work with and they're oh wow look that's zero that's zero that's 1/2 that's 1/2 so the value so the so the disorder of this guy is 0.0 so this is 1 14 one4 1 12 0 02 * 1 oh that's 0.5 that was easy how about this one oh he says one let's see that's one that's one that's one2 that's 1/2 yeah it is one so sure enough the answer also comes out to be the same as before when we did our just simple intuition exercise so so I don't know Christopher is this all about using information Theory no no no this is about this is about see you it's not about the math it's about the intuition and the intuition is that you want to build a tree that's as simple as possible and you could build a tree that's as simple as possible if you look at the

**[39:48]:** data and say well which which test does the best job of splitting things up which test does the best job of of building subsets underneath it that are is home genius is possible so all this information Theory all this entropy stuff is just a convenient mechanism for doing something that is intuitionally sound okay it's not about information Theory it's about a a sound intuition oh by the way does this kind of stuff ever get used in practice tens of thousands of times this is a winning mechanism it's used over and over again even even when the data is numeric how how would it work if it's numeric data well let's think about that for a little

**[40:40]:** bit so let's suppose that um you know we have an opportunity we have we're an EMT or something we work in the infirmary what do they call it these days something else but anyhow you you work in that kind of area and you have the opportunity to take people's temperature and so you you've uh over over time you accumulated some data on the temperature of people and maybe you found that there's a vampire here at about 102 there's a normal person here about 98.6 but then they're and they're scattered around you know some people have fevers when they come in so the question is is there a way of using numerical data things you can put real on a real real numbers there a way of using that with this mechanism and the answer is yes you just say is the temperat greater than or less than some threshold that gives you a test just

**[41:32]:** a binary test just like any of these other tests right kishna right but where do I put the

**[41:43]:** threshold I suppose I could just put it at the average value but that might not be the test the place that does the best job of splitting the samples into homogeneous groups Christopher so you run this numerical analysis on different places thr so you tried different places he says and he's right because this is a computer this is our slave we don't care how much it works to figure out the right threshold so what we do is we say well maybe the threshold is halfway between those two guys or halfway between those two guys or those two guys or those two guys or those two guys so we can try one less threshold than we have samples and we don't care if there are 10,000 samples because this is a computer and we don't care if it works on right so that's how you find the threshold for a numeric test by the way I

**[42:33]:** asserted earlier on you would never use the same test twice is that true for this yes you would still never use the same test twice but what you might do is you might use a different threshold on the same on the same measurement the next time around so in this when you start having numerical data you may find yourself using the same the same test with it the same the same axis but with a different value all right so now we can say now that we have this then we can go back and compare how this method would uh would uh would look when we put it up against the sort of stuff we were talking about last time with the with the electrical

**[43:19]:** covers so with the electrical covers we had a situation like this I don't know we had samples that were places like this and we had uh a division of the space that looked pretty much like that not quite exactly in the right spots but pretty close so these are the decision boundaries uh for the situation where we are using nearest neighbors to divide up the data what would the decision boundaries look like if these were four different kinds of things and we were using this kind of mechanism and maybe there maybe there's a whole lot of samples all clustered around places like that what would the decision boundaries look like would they be the same as this God I hope not why because what we're going to do is we're going to use a threshold on the on each axis so therefore the decision boundaries are going to be parallel to one Axis or the

**[44:25]:** other so we might side for example oh shoot I think I'll draw it again because it'll get confused if I draw it over the other one so looks like this and that's how nearest neighbors does it but a identification tree approach will pick a threshold and along one Axis or the other let's say it's this axis it it's only got one choice there so it's going to put a line there and now what's the next thing it does well it still has uh these two different kinds of things to separate we're going to assume we've got four different kinds of things so it's going to say ah I've come down the negative side so I need a threshold on the remaining data and these are the only two things that are now remaining so my only choice is to put a a threshold in there now I guarantee this absolutely guaranteed on the quiz somebody

**[45:28]:** presumably somebody who doesn't go to lectures will draw that line all the way across and that's desperately wrong because we've already divided this data set in half now the choice of what we do over here is governed only by the Remain the remaining samples that we see these two and so the threshold is going to go in there like that okay so that's what happens when you go back this is used tens of thousands of times always Ed what are the virtues of it number one you don't use all the tests you use only the tests that seem to be doing some useful work for you so that means that you do a better job because your measurement technique is simpler and it costs less because you're not going to the expense of doing all of the testing so it's a it's a it's a real winner but you know what some classes of people

**[46:26]:** not scientists I mean people like doctors and stuff they don't like uh to look at these trees they're kind of rule oriented so they uh look at a tree like this for determining what kind of thyroid disease you have and it would have maybe 20 or 20 or so tests in it of various kinds of hormones like thyroxin and this and that and they say ah we can't deal with that so we have to we have to we have to work with them so what will we do do is we convert the tree into a set of rules how do we convert the tree into a set of

**[47:08]:** rules oops wrong one go away go away oh here's what I want yeah good how do we convert this tree into a set of rules it's straightforward Christopher what do we do you basically just look down each branch you basically just go down each branch to a leaf so you say for example here's one rule if

**[47:35]:** Shadow equals question mark and garlic equals oh let's which branch do I want to choose no doesn't eat garlic no I I think I'll say yes yes that changes the answer then

**[48:02]:** um then if it eats garlic it's not a vampire right so that's one of four possible rules because there are four leaf nodes now we're almost done and we are done except for one thing we can actually take these four rules and start thinking about how to simplify them you can ask questions like if I have a rule that tests both the shadow and the garlic do I actually need both of those antecedants and the answer is in many cases no and in particular in this case no because if we look at our data set what we discover is that in the event that we're talking about a shadow question mark oh I guess I had a better choice the other way oh no if you look at the garlic all the garlics yes yes and yes it turns out that the answer is no independent of what the shadow condition is so we can

**[49:00]:** look at the rules in some cases we'll discover that our tree is a little bit more complicated they need to be we can actually get rid of some of the Clauses so in the end we can develop a very simple mechanism based on good oldfashioned rule-based behavior like you saw almost in the beginning of the subject that does the job and now you're all free to put this uh without without any royalty you're all free to put this into your PDA and use it to protect yourself in the days to come especially since Halloween is just around the corner
