fast.ai: Intro to Machine Learning 1 (v1) (2018)
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
Last lesson we looked at what random forests are, and we looked at some of the tweaks that we could use to make them work better. So, in order to actually practice this, we needed to have a Jupiter notebook environment running, so we can either install anaconda on our own computers. We can use AWS or we can use cress or comb that has everything up and running straight away, or else paper. Space comm also works really well, so assuming that you've got all that going, hopefully you had a chance to practice running some random forests. This week, I think one of the things to point out, though, is that before we did any tweets of any type of parameters or any tuning at all, the broad defaults already gave us a very good answer for an actual data set that we want to Carol. So, like the tweets are always you know the main piece there they're just sometimes they're totally necessary, but quite often you can go a long way without doing any food store. So today we're going to look at something I think may be even more important than building a predictive model, that's good at predicting, which is to learn how to interpret that model, to find out what it says about your data. To actually understand your data better by using machine learning - and this is kind of contrary to this - the common refrain that things like random forests are black boxes that hide meaning from us and you'll, see today that the truth is quite the opposite.
The truth is that random forests allow us to understand our data deeper and more quickly than traditional approaches. The other thing we got to learn today is how to look at larger data sets than those which you can import with just the defaults and specifically we're going to look at a data set with over 100 million rows, which is the current kaggle competition for groceries. There anybody had any questions outside of those two areas since we're talking about today or comments Emily yeah. It is this kind of like basic just to make sure I'm understanding the concept. I'm talking here. Sorry um. Can you just talk a little about like in general? I understand the details more now: random florists but like when do you know this is an applicable model to use in general? Be like? Oh, I should try random forests here because that's the part that I'm still like yeah, if I'm told to I, can yeah so the short answer is. I can't really think of anything offhand that it's definitely not going to be at least somewhat useful for so it's always worth trying. I think really, the question is in what situations should I try other things as well, and the short answer to that question is for unstructured data. What I call unstructured data. So, where are all the different data points represent the same kind of thing like a wave form in a sound or speech, or the words and piece of text or the pixels in an image? Are you almost certainly you're going to want to try deep learning and then outside of those two there's a particular type of model? We're going to look at today called a collaborative filtering model where which it so happens that the groceries competition is at that kind.
Where neither of those approaches are quite what you want without some tweaks to them, so that would be the other main one. So you're saying neither using deep learning and neither deep learning or random forests is exactly what you're wanting in to kind of do some quests. Yes, yeah, if anybody thinks of other places where maybe neither of those techniques is the right thing to use, yeah mention it on the forums, even if you're, not sure you know, so we can talk about it, because I think this is one of the more interesting Questions and to some extent it is a case of practice and experience, but I do think there are, you know true main classes. No, no. So last week we at the point where we had kind of done some of the key steps you know like over CSV reading, in particular, which door you know a minute or two at the end of that we saved it to a feather format, file and just To remind you, that's because this is basically almost the same format that it lives in
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
In RAM, so it's like ridiculously fast to read it and write stuff from from feather point. So what we're going to do today is we're going to look at lesson. 2, RF interpretation and the first thing we're going to do is read that feather format file. Now one thing to mention is a couple of you pointed out during the week a really interesting little little bug or little issue, which is in the proc DF function. The proc DF function remember, finds the numeric columns, which have missing values and creates an additional boolean column, as well as replacing the messing with medians and also turns the categorical objects you know into into the integer codes, the main things it does and coming. You pointed out some key points about the missing value handler. The first one is that your test set may have missing values in some columns that weren't in your training set, or vice versa, and if that happens, you're going to get an error when you try to do the random forest, because it's going to say you know, If that is missing, field appeared in your training set, but not in your test set that ended up in the model. It's going to say you can't use that data set with this model, because you're missing one of the columns it requires. That's problem number one problem number two is that the median of the missing belt are the median of the numeric values in the test.
Set may be different for the training set, and so it may actually process it into something which has different semantics. So I thought that was a really interesting point. So what I did was I changed property air. So it returns a third thing na s and the na s thing it returns. It doesn't matter in detail what it is. But I'll tell you to say you know. That's a dictionary that, where the keys are the names of the columns that had missing values and the values of the dictionary are the medians and so then optionally. You can pass n A's as an additional argument to prop D F and it will make sure that it adds those specific columns and it uses those specific medians. Okay. So it kind of it's it's giving you the ability to say, process this test set in exactly the same way as we process this training center. Can you pass? That is a did. It features we just yeah, so I just did that like it's just a good pool, yeah in fact, that's a good point before you start doing work any day. I would start doing it get pull and it something's not working today that was was working yesterday check the forum, where they'll be an explanation of why you know this. This library, in particular, is moving fast, but pretty much all the libraries that we use, including pytorch and particular move fast, and so one of the things to do if you're, watching this on through the MOOC, is to make sure that you go to course doc. Bastard AI and check the links there because they'll be links saying.
Oh, these are the differences from the course so they're kind of kept up to date so that you're never gon na, because I can't edit what I'm saying yeah but yeah. Do it get Paul before you start each day, so I haven't actually updated all of the notebooks to add the extra return value i will over the next couple of days, but if you're using them, you'll just need to put next to a comma, and it is Yeah, otherwise we're going to error them its return through things, and you only have room for two things: okay, what I want to do, I think what I want to do before I talk about interpretation is to show you what the exact same process.
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
Looks like when you're working with a really large data set so and you'll see it's kind of almost the same thing. But there's going to be a few cases where we can't use the defaults, because the default kind of flag just run a little bit too slowly. Right so specifically, I'm going to look at the travel groceries, competition, specific lady. What's a call here, it is compress your favorite grocery sales forecasting. So this competition, Oh who's, who who was entering this competition? Okay, lot of you who would like to have a go at explaining what this competition involves, what what the data is when family, okay, trying to predict the items on the shelf, depending on lots of factors like oil prices, let me say, predicting the items on the Show what do you mean? What are you actually predicting? How much change to help me stop to maximize their? I guess it's not quite what we're predicting, but not trying to fix that yeah and then there's a bunch of different data sets that you can use to do that. There's oil prices there's a stores, there's locations and each of those can be used to try to predicted okay. Does anybody want to have a go at expanding on that all right? So we have a bunch of information on different products, so we have so forth all right so far, every stool for every item.
For every day, we have a lot of related information available like the location where the school was located, the class of the product and units soared and then based on this, we are supposed to forecast in a much shorter timeframe compared to the training data. For every item number how much we think it's going to sell so only the units and nothing else so um. So your ability to explain the problem you're working on is really really important. Okay, so if you don't currently feel confident of your ability to do that, practice right with someone who is not in this competition tell them all about it. So in this case, but or in any case really, the key things to understand a machine learning problem would be to say what are the independent variables and what is the dependent variable. So the dependent variable is the theme that you're trying to predict. The thing you're trying to predict is how many units of each kind of product were sold in each store on each day during the two-week period. So that's the thing that you're trying to predict and the information you have to predict. It is how many units of each product at each store on each day were sold in the last few years and for each store it's a metadata about it like. Where is it located and what classes or is it for each type of product? You have some metadata about it, such as what category of product is it and so forth for each date we have some metadata about it, such as what was the oil price on that date, so this is what we would call a relational data set.
So a relational data set is one where we have a number of different pieces information that we can join together. Specifically, this kind of relational database data set is what we would refer to as a star schema. A star schema is a kind of data, warehousing schema where we basically say there's some central transactions table. Then this place the central transactions table we go in the data section here is train dot, CSV and it contains the event number of units that were sold by date by store ID by item ID okay. So that's the central transaction state, where it's more very simple and then from that we can join various bits of metadata and it's called a standard schema because you can kind of imagine the transactions take on the middle and then all these different metadata tables join onto It giving you more information about the date, the item ID and the store already. Okay, sometimes you'll also see a snowflake schema, which means they might then be additional information joined on to maybe the the items table. That tells you about different item categories and store to the store table coming about the stage that the stores in and so for, wholesomely. Okay. So that's the basic information about this problem, the independent variables, the dependent variable - and you probably also wanting about like things like the time frame. Okay, now we start in exactly the same way as we did before loading in exactly the same spot setting the path.
But when we go to read CSV, if you say limit memory equals false right, then you're, basically saying use as much memory as
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
You like to figure out what kinds of data is here: it's going to run out of memory pretty much regardless of how much memory you have. So what we do in order to limit the amount of space that it takes up and read it in is we create a dictionary for each column, name through the data type of that column right and so for you to create this. It's basically up to you to you, know, run less or head or whatever, on the data set to see what the types are and to figure that out and pass them in. So then you can just pass in D type equals with that dictionary and so check. This out right, we can read in the whole CSV file in one minute and 48 seconds, and there are one hundred and twenty five point: five million roads so like whence people say like pythons, slow, now, pythons, not slow, I think, can be slow. If you don't use it right, but we can actually cause a hundred and twenty-five million CSV records in less than two minutes my language had on for just a moment. Actually, if it's fast almost certainly it's going to see yeah. So Python is a wrapper around a bunch of C code, usually yeah, so yeah, so Python itself isn't actually very fast yeah, so that was Terrence paw, who writes things for writing programming languages for a living so and he's right itself is not fast, but almost everything We want to do in Python, and data science has been written for us in C or actually more often in scythe on which is a like language which compiles to C, and so most of the stuff we run in Python is actually running, not just the C Code, but actually in pandas, a lot of it's written in like assembly language, it's heavily optimized behind the scenes.
A lot of that is going back to actually calling for train back libraries for linear algebra, so there's layers one layer of speeds that actually allow us to spend less than two minutes. Reading that much data yeah. If we wrote our own CSV reader in pure Python, it would take. It takes thousands of times at least thousands of times longer than the optimized versions yeah. So for us, what we care about is the speed we can get in practice, and so this is pretty cool. We, as well as telling it what the different data types were. We also have to tell it as before, which things do you want to pass as as dense? That's I've noticed searching this dictionary of specifying 60 1433 ending date. I was wondering in practice: is it like faster, if you all specify them to endure slower or like any performance consideration, so the key performance consideration here was to use the smallest number of bits that I could to fully represent the column. So if I had used in 8 for item number, there are more than 255 biomass and but the I mean who was specifically the maximum item, number is bigger than 255. So, on the other hand, if I'd used in 64, the score number it's using more, it's necessary, given that the whole purpose here was to avoid running out of RAM, we don't want to be using up eight times more memory than necessary, so the key thing was Really about memory, and in fact, when you're working with large data sets very often you'll find the slope piece is the actually reading and writing program, not the actual CPU operations.
So very often that's the key performance consideration. Also, however, as a rule of thumb, smaller data types often will run faster and particularly if you can use Cindy so there's a single instruction, multiple data, a vectorized code. It can pack more more numbers into a single vector to run at once. Think that was all definitely simplified exactly right, but once you do this, the shuffle thing beforehand, I need anymore. They made assigned a random substitution yeah. So so, although here I've read in the whole thing, when I start, I never start by reading in the whole thing. So if you
shuf
’ to read a sample of large dataset at start(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
Search the forum fish fish off shuf you'll find some tips about how to use this UNIX command to get a random sample of data at the command prompt. And then you can just read that, and the nice thing is that that way, like that's a good way, for example, to find out what data types to use, it is to read in a random sample and let pandas figure it out for you, yeah and in General, I do as much work as possible on a sample until I feel confident that I understand the sample before I move on so yeah. Having said that, what we're about to learn is some techniques for running models on this full data set that I'm actually going to work on arbitrarily large data sets, but also, I specifically wanted to talk about how to really invite analysis. One thing to mention: unpromoted object: objects are like like saying, create a general-purpose Python data type, which is slow and memory heavy, and the reason for that is that this is a boolean which also has missing values, and so we need to deal with this before we Can turn it into a boolean, so you can see after that. I then go ahead and I say, fill in the missing values with false. Now you wouldn't just do this without doing some checking ahead of time, but some exploratory data analysis shows that it seems that this is probably an appropriate thing to do. It seems that missing doesn't mean most.
It objects generally reading the string so replace for Strings. True and false, with actual volumes and then finally convert it to an actual boolean flag. So at this point, when I save this this file now over 123 million records takes up something under two and a half gigabytes of memory. So like that, you can do like run, you know, look at pretty large data sets even on pretty small computers, which is interests so at that point now that it's in a nice fast four-minute, look how fast it is. I can save it to feather format in under five seconds: okay, so that's nice and then because pandas is generally pretty fast. You can do stuff, like summarize, every column of all 125 million records in 20 seconds. Okay. So the first thing I looked at here actually is the dates right generally speaking, dates are just going to be really important and one of the stuff you do, particularly because any model that you put in in in practice you're going to be putting it in at Some note that is later than the date that you trained it by definition right and so, if anything in the world changes, you need to know how your predictive accuracy changes as well, and so what you'll see on cable and what you should always do in your Own projects is make sure that your plates don't overlap. So in this case, the dates that we have in the training set go from 2013 to mid August 2017. Okay, there's our first and last and then in our test set.
They go from one day later right August, the 16th until the end of the month. So this is a key thing that, like you, can't really do any useful machine learning. Until you understand this basic piece here, which is, you've, got four years of data and you're trying to predict the next two weeks. Okay, so that's just a fundamental thing that you're going to need to understand before you can go and do a good job at this, and so as soon as I see that what does that say to you, if you want it to now use a smaller data Set should you use a random sample, or is there something better you do probably from the bottom more recent yeah, okay, the most recent right and and if you ever have trouble answering questions like this just try to make it as physical as possible. So it's like! Okay, I'm going to go to a shop next week, and I am I've got a $ 5 bet with my brother as to whether I can guess how many cans of coke are going to be on the shelf all right. Well, probably, the best way to do that would be to go to the shop same day of the previous week and see how many cans of coke are on the shelf and guess it's going to be the same. You wouldn't go and look at family were there. Four years ago, but couldn't four years ago that same time frame of the year be important, I mean like, for example, how much coke they have in the shop at Christmas time is gon na be way more than so exactly so it's not that. There's no useful information from four years ago, and so we don't want to entirely throw it away, but as a as a first step like what was this? What's the simplest possible thing, it's kind of like submitting the means, I wouldn't submit the mean of 2012 sales.
I would want to probably submit the mean of last month's cents, so yeah we just want to think about like how might we want to kind of create some initial easy models and how and later on like we might want to weight it. So, for example, we might want to wait for recent dates, more highly they're, probably more relevant, but we should do a whole bunch of exploratory data analysis to check that. So here's what the bottom of that data set looks like okay and you can see literally it's got a date, a store, number and item number and give it sales and tells you whether or not that particular item was on sale at that particular store on that Particular day and then there's some Terry ID right, so that's it so now that we have read that in we can do stuff like this is interesting again we have
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
To take the log of the sales and it's the same reason as we looked at last week, right because we're trying to predict something that kind of varies according to ratios. They told us in this in this competition that the root mean squared log error is something they care about, so we take a look they mentioned. Also, if you check the competition details, which should always should read carefully the definition of any project, you do it's, they say that there are some negative sales that represent returns and they tell us that we should consider them to be zero for the purpose of this Competition, so I clip the sales so that they fall between zero and no particular maximum. It's a clip just means cuddle after that point, truncate it and then take the log of that plus one. Why do I do plus one? Because again, if you check the details of the cable competition, that's what they tell you, they're going to use is they're not actually just taking the root mean squared log error, but the root mean squared log plus one there. Okay, because log of zero doesn't make sense. We can add the date part as usual, and you know again it's taking a couple of minutes right, so I would run through all this on a sample first. So everything takes ten seconds to make sure it works just to check everything.
That's reasonable. Before I go back so I don't want to wait two minutes or something I don't know what's going to work, but as you can see all this, all these lines of code are identical to what we saw for the bulldozers competition in this case and all I'm Bringing in is a training set. I didn't need to run trained cats because all of my data types are already numeric. Okay, if they weren't, I would need to call trained cast and then I would need to call the ply cats to apply the same categorical codes that I down from the training set to the validation set. I call prop D F as before, to check
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
The missing values and so forth, so all of those lines of code are identical. These lines of code again are identical because root mean square errors, store we care about, and then I've got two changes. The first is sent our F samples, which we learnt about last week, so we've got 120 something million records. We probably don't want to create a tree from our hundred twenty million, something reckless. I don't even know how long that's going to take. I haven't been. I haven't at the time and patience for wagon see so you know you can start with ten thousand or a hundred thousand, you know maybe runs in a few seconds, make sure it works, and you can kind of figure out how much you can run, and so I found getting it to a million, it runs in under a minute alright, and so the point here is: there's no relationship between the size of the data set and how long it takes to build the random forests. Their relationship is between the number of estimators multiplied by the sample size. Okay, I'm just curious what Angela's cousin has always been negative one yeah, so the number of jobs is the number of cause. Thursdaya news - and I was running this on a computer that has about 60 cause - and I just found if you try to use all of them, had spent so much time spending I've drops, it was doing slower.
So if you've got like lots and lots of cores on your computer, sometimes you want less than negative one means use every single core and there's one more change I made, which is that I converted the data frame into an array of floats and then I fit It on that, why did I do that, because, internally inside the random forest code, they do that anyway, right and so, given that I want to run a few different random forests with a few different hyper crepitus by doing it once myself, I save that minute 37 Seconds right, so if you run a line of code at a text like quite a long time so the first time I ran this random first regressor, a kind of took two or three minutes, and I thought I don't really want to wait to a few minutes. You can always add in front of the line of code: hey run a percent P right and what percent p run does is? It runs something called a profile and what a profiler does is it'll. Tell you which lines of code behind the teens took the most time right, and in this case I noticed that there was a line of code inside scikit-learn. That was this line of code and it was taking all the time the other day. And so I thought. Oh I'll do that first and then I'll pass you the result, and I won't do it again. Okay, so this thing of looking to see which things is taking up the time is called profiling and in software engineering is one of the most important tools you have data scientists really under appreciate this tool that you'll find like amongst conversations on issues or on Twitter Or whatever, I'm at the top data scientists, they're sharing and talking about profilers all the time and that's how easy it is to get a profile so for fun.
You know try running peer on from time to time on stuff, that's taking 10 20 seconds and see if you can learn to interpret and use profile outputs. You know, even though, in this case I didn't write this scikit-learn plus, I was still able to use the profile to figure out how to make it run over twice as fast, by avoiding recalculating this each time. So in this case I build my regressor. I decided to use 20 estimators. Something else that I noticed in the profiler is that I can't use our base, for when I do is set our f samples, because if I do it's going to use the other 124 million rows to calculate the oeob score, which is like again, it's still going To take forever so I may as well have a proper validation set anyway, besides, which I want the validation set. That's the most recent dates, rather than is random. So if you use set RF samples on a large data, set, don't put the low B score parameter in because it takes forever. So that got me a point. Seven six validation root mean squared log error and then I tried like fiddling around a different min samples. So if I decrease the min sample say from 100 to 10, it took a little bit more time to run as we'd expect and the arrow went down from 76 to 71. So that looks pretty good, so I kept decreasing it down to 3 and that brought
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
This arrow down to 0.7, oh and when I decrease it down to 1, we didn't really know so. I kind of had like a reasonable random forest yeah. When I say reasonable, though, it's not reasonable in the sense that it's it's does not give a good result on the way to one, and so this is a very interesting question about. Why is that? And the reason is really coming back to Savannah's question earlier, like where my random forests not work as well. Let's go back and look at the data. Okay, here's the entire data set that we won at the whole data set. Here's all the columns that we used so the columns that we have to predict with are they the date, the store number? The item, number and weather is unpredictable day of week day of month day of year, is corner, start, etc, etc. So if you think about it most of the insight you know around like how much of something you expect to sell tomorrow, it's likely to be very wrapped up in the details about like what, where is that store? What kind of things do they tend to sell at that store for that item? What category of item is, is it you know if it's like fresh bread, they might not sell much of it on Sundays, because on Sundays you know and fresh bread doesn't get made.
It doesn't know which one represents gasoline. It doesn't know which stores are in the center of the city versus which ones are out in the it doesn't know any of these things, so its ability to really understand what's going on is somewhat limited, so we're probably going to need to use the entire four Years of data to even get some useful insights, but then the students beside using the whole four years of data and one of the data we're using, is really old. So, interestingly, there's a cable kernel that points out that what you could do is just take. The last two weeks and take the average sales, the average sales by date by store number by item number and just submit that and if you just submit that you come about 30th, all right. So for those of you in the groceries kind of Terrace. As I come into a question, I think this may have tripped me up. Actually, I think you said dates store item. I think it's actually store item sales and then you mean across date oh yeah, you're right. It's a store item at one promotion. I know promotion, is you know if you do it, if you do it like date as well, you end up, so these each row represents basically like a cross tabulation of all of the sales on that date in that store for the item. So if you put date in there as well, there's only going to be one or two items being averaged in each of those cells, which is you know too much variation basically two spots: it doesn't give you a terrible result, but it's it's not xxx.
So so your job, if you are looking at this competition and we'll talk about this in the in the next class, is how do you start with that model and make it a little bit better all right, because if you can, then by the time we made Up next, hopefully, you'll be above the top 30, because you know CAG will be in Kaggle. Lots of people have now taken this kernel and submitted it and they all have about the same score and the scores are ordered not just by score but by date submitted. So if you now submit this kernel, you're not going to be 30th because you're way down the list when it was submitted all right. But if you could retire a bit better you're going to be better than all of those people. So try and think of how can you make this a tiny bit better? I could you try to capture seasonality and trend effects by creating new columns like these are the average sales in the month of August. These are the average sales for this year yeah. I think that's a great idea, so the thing for you to think about is how to do that right and so like see. If you can see, if you can make it work, because there are details to get right, which I know Terrance has been working on. This for the last week and he's got almost crazy, like the details. Prez here the details are: are difficult, they're not difficult, like intellectually difficult, they're kind of difficult in the way that makes you like, when I head back your desk at to any air and like this is something to mention in general.
Is the coding you do? The machine learning is like it's incredibly frustrating and incredibly difficult, not difficult like technically but difficult like there. If you get a detail wrong much of the time, it's not going to give you an exception, it will just silently be slightly less good than it otherwise would have been right and if your own peril, at least you know, okay, well, I'm not doing as well As other people won't haggle right, but if you're not on cattle, you just don't know like you don't know if your company's model is like half as good as it could be, because you made a little mistake right. So that's why? One of the reasons why practicing on tackle now is great right because you're going to get practice in finding all of the ways in which you can infuriatingly screw things up and you'll. Be amazed like for me there's extraordinary array array of them, but, as you get to know what they are you'll start to know how to check for them as you go right, and so the only way like you should assume every button you press you're, going to Press the wrong button right and that's fine as long as you have a way to find out. Okay, so we'll talk about that more during the course, but unfortunately there isn't like a set of specific things. I can tell you to always: do you just always have to think like okay? What do I know about the results of this thing? I'm about to do I'll. Give you a really simple example: a really simple example: if you've actually created that that basic entry entry, where you do take the mean by date by store number by own promotion, right and you've like submitted it and you've, got a reasonable score.
And then you think you've got something: that's a little bit better and you do predictions for that. How about you don't create a scatter plot, showing the predictions of your average model on one axis versus the predictions of your new model on the other axis. You should see that they just about form a line right and if they don't, then that's a very strong suggestion that you screwed something up alright, so like that, be an example. Okay, can you pass that one to the end of that room possible instance once those? Yes, so your so for a problem like this, unlike the car insurance problem on taggle, where we don't wear, columns are unnamed, we know we know what the columns representing what they are. Do you? How often do you pull in data from other sources? To supplement that I mean you could maybe like weather data, or you know, for example, or how often is that used very often right, and so the whole point of this star schema is that you break the second table and then you've got these other tables coming On third, that provide metadata about it. So, for example, whether it's meditating about a date yeah on cattle, specifically most competitions, have the rule that you can use external data as long as you post on the forum that you're using it and then it's publicly available. But you have to check on a competition by competition basis. They will tell you outside of cattle.
You should always be looking or like what external data could I possible leverage here? Okay, so are we still talking about how to tweak this data set? If you wish? Well, I'm not familiar with the countries here, so maybe he's Ecuador Ecuador. So maybe I would Ecuador largest grocery chain. Ecuador is largest first chain. Maybe I would start looking for Ecuador's holidays and shopping holidays, maybe when they have a three-day weekend, or you know I've, actually that information is provided in this case and so in general. One way of tackling this kind of problem is to create lots and lots of new columns containing things like you know: average number of sales on holidays, average percent change in sale or between January and February, and so on and so forth. And so, if you have a look at there's been a previous competition on cattle Rossman store sales that was
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
Almost identical it was in Germany in this case for a major grocery chain, how many items are sold by day by item type by store and the this case. The person who won quite unusually actually was something of a domain expert in this space they're. Actually, a specialist in doing logistics predictions - and this is basically what they did was professional sales forecast consultant ping. He created just lots and lots and lots of columns based on his experience of what kinds of things can be useful for making predictions to that. But that's an approach that can work. The third-place team did almost no feature engineering, however, and also they had one big oversight which I think they would have won. So you don't necessarily have to use this approach, so we're learning anyway, we'll be learning a lot more about how to win this competition and ones like as we go. They did it to you, the third question, so if you, google, for among cattle rustlin you'll, see it the short answer, is there is a big blow. So what are the things? And these are a couple of charts that so Terrence is actually my teammate on this competition. So parents drew a couple of these charts for us and I want to talk about this, which is, if you don't have a good validation set. It's it's hard, if not impossible, to create a good model, so in other words like if you're trying to predict next month's sales - and you build a bunch, you know you try to build a model and you have no way of really knowing whether the models you've Built are good at predicting sales a month ahead of time.
Then you have no way of knowing, when you put your model in production, whether it's actually going to be any good okay. So so you need a validation set that you know is reliable and telling you whether or not your model is likely to work well when you like, put it into production or use it on the test set. So in this case, what Terrance has plotted here is, and so normally you should not use your test set for anything other than using it right at the end of the competition all right end of the project to find out how you've got. But there's one thing: I'm going to let you use the test set for an addition, and that is to calibrate your validation set. So what Terrance did here was he built four different models right, some which he thought would be better than others, and he submitted each of the four models to cattle to find out its score, and so the x-axis is the score: the cattle produce on the leaderboard. Okay and then on the y-axis he plotted the score on a particular validation set. He was trying out to see whether this validation said look like it was going to be any good. So if your validation set is good, then the relationship between the leaderboards for by the testing score and your validation set score should lie in a straight line. Ideally, it'll actually lie on the y equals x line, but honestly that doesn't matter too much as long as relatively speaking, it tells you which models are better than which other models, then you know which model is the best right, and you know how it's going to Perform on the test set, because you know the linear relationship between two things: okay, so in this case, Terrence has managed to come up with a validation set, which is looking like it's going to predict our tab or leaderboards for pretty well, and that's really cool right.
Because don't even go away and try a hundred different types of models, feature engineering waiting, twigs paper parameters, whatever else see how they go on the validation set and not have to submit to tackle right, so we're going to get a lot more iterations, one more feedback. This is not just true of cattle, but every machine learning project you do yeah, and so, if you find so here's a different one, he tried back where it wasn't as good right. It's like oh these ones that were quite close to each other. It's showing us! The opposite direction: that's a really bad sign. It's like okay, this validation set idea didn't seem like a good idea. This validation set idea did number one good idea. So in general, if your validation set, it's not showing a nice straight line, you need to think carefully. Like okay, how is the test set constructor, why? How is my validation set different in some way, you're constructing images which is different, but I have to draw lots of charts and so forth. So one question is, and I modified two to guess how how you did it so how they actually tried to construct this validation set us close today. So I would try to do is to try to sample points from the training set that are very closer possible to some of the points in the test set. First, in what sense - and I don't know I will have to find any lectures, but in this case for this first room 4030 scrotus.
The last points was trying variations off someplace right, so the most recent you know and what I noticed was so first I looked at the date range of the test set and then I looked at the the kernel that described how he or she here's the date Range of the last two weeks of August 26 - that's right, and then the person who submitted the kernel that said how to get the 0.58 leaderboard position or whatever sport everything. I looked at the date range of that, and that was well. There was actually 14 days and the test set is 16 days, but the interesting thing is the test set, begins on the day after pay day and ends on the pay day, and so these are things I also paid attention to, but - and I think that's one Of the bits of better data that they told us, you know, so these are the kinds of things you just put a like. Try and, like I said, trick plot lots of pictures and like even if you didn't know it was pay day. You know you would want to like draw the time series part of sales, and you would hopefully see that like every two weeks, so it'd be a spike or whatever you'd be like. Oh, I want to make sure that mine, I have the same number of spikes in my validation set that I've had in my test day. Okay, let's take a five-minute break and let's come back at 2:30 to
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
Okay, so um. This is my favorite bit of interpreting machine learning models by the way, if you're looking for my notebook about the groceries competition, you won't find it in github, because I'm not allowed to share code for running competitions with you unless you're on the same team as me, After the competition is finished, it'll be on github. So if you're doing this for the video, you should be able to find it. So, let's start by reading in our feather file. So after the file is exactly the same as our CSV file. This Israel, Blue Book for bulldozers, competition, so we're trying to predict the sale price of every industrial equipment, adoption and so reading. The feather format, by all means that we've already read in the CSV and processed it into categories, and so the next thing we do is to run property F in order to turn the categories into integers deal with the missing values and pull out the hidden variable. Okay, this is exactly the same thing as we used last time to create a validation set where the validation set represents the last couple of weeks, the last twelve thousand records by date - and I discovered thanks to one of your excellent questions on the forum last week. I had a bug here, which is that proc Pierre was shuffling the order, sorry so doc, Proctor, yes, and last week we saw a particular version of property earth where we passed in a subset and when I passed in a subset it was randomly shuffling and so Then i said, split bowels: it wasn't getting the last rose by date, but it was getting a random set of roads.
So I've now fixed that. So if you really run the lesson, 1rf code you'll see slightly different results. Specifically, you'll see in that section that my validation set results, look less good, but that's only for this tiny little bit where I had subset equals. Yes, I'm a little bit confused about the notation here, so only as is most a input variable and this associate variable dysfunction and yeah. Why is thatis the proc DF returns a dictionary telling you, which things were missing, which columns are missing and for each of those columns what the median was. So when you call it on, like the larger data, set the non subset, you want to take that return value, and you don't pass in an energy to that weight. You just want to get back a result later on when he planted into a subset. You want to use to have the same missing columns and the same medians, and so you pass it in and if, like this different subsets like if it was a whole different data set turned out had some different missing columns. It would update that dictionary with some with additional key values as well. So it kind of you can you don't have to pass it in if you don't pass it in, but it just gives you gives you the information about what was missing and the medians. If you do a sit in, it uses that information for any missing columns that that are there and if there are some new missing columns that will update that dictionary with that, so it's like keeping our datasets common information yeah.
It's got a keep track of all any any missing columns that you came across in any of anything. You pass the property yeah. Thank you, okay, so we split it into the training and test set just like we did last week and so to remind you once we've done crop DF. This is what it looks like. This is the log of sale, price, okay. So the first thing to think about is we already know how to get the predictions right, which is we take the average. We take the average value in each leaf node in each tree after running a particular road through each tree. That's how we get them. The prediction, but normally we don't just want a prediction. We also want to know how confident we are of that prediction, and so we would be less confident of a prediction if we haven't seen many examples of roads like this one and if
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
We haven't seen many examples of roads like this one. Then we wouldn't expect any of the trees kind of have a path through which which is really designed to help us predict that road and so conceptually. You would expect, then, that, as you pass this unusual row through different trees, it's going to going to end up in very different places. So in other words, rather than just taking the mean of the predictions of the trees and saying that's a prediction. What if we took the standard deviation of the predictions of the trees, so the standard deviation of the predictions of the trees. If that's high, that means each tree is giving us a very different estimate of this rose prediction. So if this was a really common kind of row right, then the trees follow forward to make good predictions for it, because it's same lots of opportunities to split based on those kinds of roads right. So the standard deviation of the predictions across the trees gives us some kind of at least relative understanding of how confident we are of this prediction. So that is not something which exists in scikit-learn or in any library I know of so we have to create it, but we already have almost the exact code. We need because remember last lesson: we actually manually calculated the averages across different sets of trees, so we can do exactly the same thing. There calculate the standard deviations, so we know I'm doing random forest interpretation.
I pretty much never use the full data set. I always call set our samples because, like we don't need a massively accurate, random forest, we just need one which indicates the nature of relationships involved right, and so I just make sure this number is high enough that if I call the same interpretation commands multiple times, I don't get different results back each time. That's like the rule of thumb about how big does it need to be right, but in practice, like 50,000, is an odd number and most of the time you know it would be surprising if that wasn't enough and it runs in seconds. So I generally start with 50,000. So with my 50,000 samples per tree set, I create 40 estimators. I know from last time that min samples we people three max features. It cost point. Five, isn't bad and again we're not trying to create the world's most predictive tree. Anyway, so that all sounds fine, we get an r-squared on the validation set of 0.89. Again we don't particularly care, but it's long as it's good enough, which it certainly is, and so here's where we can do that exact same list. Comprehension, as last time remember, go through each estimator at each tree. Call drop predict on it, with our validation set, make that a list comprehension and pass that to NP stack, which in catenate s -- everything in that list across a new axis.
Okay. So now our rows are the results of each tree and their columns are the result of each row in the original data set. And then we remember we can calculate the mean right. So here's the prediction for a data set row number one and here's our standard deviation. Okay, so here's kind of do it for just one observation right at the end here, we've calculated for all of them, just pretty nipple one here now this this can take quite a while, and specifically it's not taking advantage of the fact that my computer has lots Of cause in it list comprehensions, this is this is like the list. Comprehension itself is Python code that it's my Python code and python code. Unless you're doing special stuff runs in serial, which means it runs on a single CPU doesn't take advantage of your multi CPU hardware, and so, if I wanted to run this, you know on more trees and more data. You know this. One second is going to go out and you see here the wall time. The amount of actual climate talk is roughly equal to the CPU time. Where else, if it was running on lots of cause, the CPU time would be higher than the war time. So it turns out that scikit-learn provides a handy national circuit load fastai provides a handy function called parallel trees, which pulls some stuff inside cyclone and parallel. Trees takes two things: it takes a random forest model that I train the here.
It is and and some function to call and it calls that function on every tree in parallel, so in other words, rather than calling T, I predict X ballad, let's create a function that calls T dot, predict X, salad, let's use parallel trees to call it on Our model to every tree, okay and it will return a list of the result of applying that function to every tree. And so then we can NP Don stack that so, hopefully you can see that that code and that code are basically the same thing right. But this one is doing it in parallel, and so you can see here now our wall time has gone down to 500 milliseconds, and it's now giving this exactly the same answer. Okay, so a little bit faster time committing we'll talk about more general ways of writing code that runs in parallel. That turns out to be super useful for data science, but here's one that we can use it's very specific to random forests. Okay, so what we can now do is we can always call this to get our predictions for each tree and then we can call standard deviation to then get them for every row, and so let's try using that. So what I could do is, let's carried a copy of our data and, let's add an additional column to it, which is the standard deviation of the predictions across the first axis. Okay and, let's also add in the name so they're the predictions themselves. So we, you might remember from last lesson that one of the predictors we have is called enclosure and we'll see later on.
But this is an important predictor and so, let's start by just doing a histogram. So one of the nice things and panders is: it's got built in body and capabilities. It's well worth googling for pandas plotting to see how yes, Terrence Jeremy. Can you remind me what enclosure is so we don't know what means, and it doesn't matter. You know, like. That's the whole purpose of this process is that we're going to pick it out we're going to learn about what things are, or at least what things are important and what later on figure out what they are and how they're important so we're going to start out. Knowing nothing about this data set all right, so there's something so I'm just going to look at something called enclosure that has something called erupts and something called robots, and I don't even know what this is yet. All I know is that the only three that really appear at any great quantity are over ops erupts, whe and eros, and this is like really common. As a data scientist, you know you often find yourself looking at data that you're not that familiar with and you've got to figure out at baseline, which fits to study more carefully and which gets into matter and so forth. So, in this case at least know that these three groups - I really don't care about because they basically don't exist so given that we're going to ignore those three, so we're going to focus on this one here this one here and this one here, and so here You can see what I've done is I've taken my data frame and I've grouped by enclosure, and I am taking the average of these three fields.
So here you can see here's the average sale price, the average prediction and the standard deviation of prediction. For each of my three groups, so I can already start to learn a bit here, as you would expect the prediction and the sale price are close to each other on average. So that's a good sign and then the standard deviation varies a little bit. It's a little hard to see in a table, so what we could do is we could try to start like printing these things out. So here we've got the sale price or each little of enclosure, and here we've got the prediction: peach level of enclosure and for the error bars I'm using the standard deviation of perdition. Alright, so here you can see the actual and here's, the prediction and here's. My confidence in the world, okay, or at least it's the average of the standard deviation of the random forests. So this tells us it'll tell us if there's some groups or some rows that we're not very confident of it all. So we could do something similar for product size right, so here's different product sizes. We can do exactly the same thing of looking at our predictions under standard deviations. Okay, we could sort by and what we could say is like well. What's the ratio of the standard deviation of the predictions to the predictions and selves right, so you kind of expect on average that when you're predicting something that's a bigger number that your standard deviation would be higher all right.
So you can like sort by that ratio, and what that tells us is that the product size, large and product size, compact, our predictions, are less accurate. You know as relatively speaking as a ratio of the total price, and so then, if we go back and have a look well there you go. That's why, for the histogram, those are the smallest groups. Okay, so, as you would expect in small groups, we're doing the less good job right, so this confidence interval you can really use for two main purposes. One is that you can group it up like this and look at the average confidence interval by group to find out. Are there some groups that you just don't seem to have confidence about about those groups, but perhaps more importantly, you can look at them for specific roads, and so, when you put it in production, you might always want to see the confidence interval. So if you're doing say credit scoring so deciding whether to give somebody alone, you probably want to see not only what's their level of risk. But how confident are we and if they want to borrow lots of money and we're not at all confident or about our ability to predict whether they'll pay it back, we might want to give them a small amount. Okay, so those
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
Are the two ways in which you reduce this? Okay? Let me go to the next one, which is the most important. The most important is feature importance, and the only reason I didn't do this first is because I think the intuitive understanding of how to calculate confidence interval is the easiest one to understand entry. In fact, it's almost identical to something: we've already happened right, but in terms of which one do I look at first in practice, I always look at this in Baptist, so when I'm working on whether it be a candle competition or a real world project, I build A random forest as fast as I can try and get it to the point that it's led, you know significantly better than Brandon, but doesn't actually much better than that, and then the next thing I do is to plot the future importance and the future importance tells Us in this random forest, which columns mattered right, so we had like dozens and dozens but of columns originally in this data set - and here I'm just picking out the top ten, so you can just call our F feature importance again. This is part of the faster and ivory it's leveraging stuff. That's in scikit-learn parse in the model pass in the data frame is getting to know the names of columns right and it'll. Tell you it author, I'll, give you back a pandas data frame showing you in order of importance. How important was each column, and here on this note, pick out the top ten.
So we can then plot that right so fi, because it's a data frame, we can use data frame, plotting mints, so here I've plotted all of the future importances right, and so you can see here like and I haven't been able to write all of the names Of the columns at the bottom, which that's not the important thing, the important thing is to see that some columns are really really important and most columns don't really matter at all and like in nearly every data set you use in real life. This is what your feature importance is going to look like it's going to say: there's like a handful of columns that you care about, and this is why I always start here right because at this point, in terms of like looking into learning about this domain, heavy Industrial equipment options I only got to care about learning about the columns which matter right so are we going to bother learning about enclosure depends whether enclosure is important and there it is it's in the top ten. So we are going to have to learn about enclosure. Okay, so then we could also plot this as a bar plot. All right, so you can hear I've just created a little little tiny little function here, that's going to just plot my bars and I'm just going to do it for the top 30, and so you can see the same basic shape here and I can see there's My enclosure, okay, so we're going to learn about how this is calculated in just a moment, but before you worry about how it's calculated much more important is to know what to do with it.
So the most important thing to do with it is to now sit down with your client or your data dictionary or whatever your source of information is and say to them. Okay, tell me about you made: what does that mean? Where does it come from plot lots of things like histogram Devere made and scatter plots of here made against price and learn everything you can because you're made and cupola system they're the things that matter right and what will often happen in real-world projects? Is that you'll sit with the client and you'll say? Oh it turns out. The capital system is the second most important thing, and then they might say that makes no sense. Now that doesn't mean that there's a problem with your model, it means there's a problem with their understanding of the data that they gave you okay. So let me give you an example: I entered a cattle competition where the goal was to predict which applications for grants at a university would be successful, and I used this exact approach and I discovered a number of columns which were almost entirely predictive of the dependent Variable and specifically when I then looked to see in what way their predictive, it turned out whether they were missing or not, was basically the only thing that mattered in his data set and so later on. So I ended up winning that competition and I think a lot of it was thanks to this insight right and so later on what had happened.
It turns out that at that University there's, you know, there's an administrative burden to fill any other database and so for a lot of the grant applications. They don't fill in the database for the folks whose applications weren't accepted right so in other words, these missing values. In the data set were saying: okay, this grant
(autogenerated subtitles follow, may contain gibberish/bad format - please proofread to improve - remove this note once proofread)
Wasn't accepted because if it was accepted, then you know the admin folks are going to go in and type in that information. So this is what we call data leakage and data leakage means there's information in the data set that I was modeling with which the university wouldn't have had in real life at the point in time they were making a decision right. So when they're deciding you know which grant applications, should I like prioritize, they don't actually know which ones the admin staff or later I'm going to add information to, because it turns out that they've got accepted. I mean right, so one of the key things you'll find here is is data leakage, problems and that's a serious problem. You need to deal with. The other thing that will happen is you'll often find it's signs of collinearity, and I think that's what's happened here with kapwa system. I think Kapler system tells you whether or not a particular kind of heavy industrial equipment has a particular feature on it. But if it's not that kind of industrial equipment at all, it will be empty, they'll be missing, and so capitalist system is really telling you whether or not it's a certain class of heavy industrial equipment. Now this is not linkage. This is actual information you actually have at the right time. It's just that like interpreting it, you have to be careful okay, so I would go through at least the top 10 or like kind of look for where the natural breakpoints are and really study.
These things carefully to make life easier for myself. What I tend to do is I try to throw some data away and see if that matters. So in this case I had a random forest which let's go and see how accurate it was. Point. Eight nine point: eight eight, nine. What I did was I said here: okay, let's go through our feature, importance, data frame and filter out those where the importance is greater than 0.005 thanks. 0.025. Two point: zero five is about here right, it's kind of like where they really flattened off all right. So let's just keep those, and so that gives us a list of 25 column names. And so then I say: okay, let's now create a new data frame view which just contains those 25 columns, Coles flipped bowels on it again decision to test and training set and create a new random forest. And, let's see what happens - and you can see here - the a square basically didn't change. Eight, nine one versus eight, eight nine. So it's actually increased a tiny bit right. I mean, generally speaking, removing redundant columns. Well, you know it shouldn't. Obviously it shouldn't make it worse. If it makes it worse, they weren't redundant after all, it might make it a little better because if you think about how we built these trees, when it's deciding what to split on you know it's, it's got less things to have to worry about trying. It's less often going to like accidentally find a crappy poem. So it's you know.
I've got a slightly better opportunity to create a slightly better tree with slightly less data, but it's still it's not going to change it by much, but it's going to make it a bit faster and it's going to. Let us focus on what matters. So if I rerun feature importance now, I've now got twenty five. Now. The key thing that's happened is that when you remove redundant columns is that you're also removing sources of collinearity right, in other words, two columns that might be related to each other? Now Collini arity doesn't make your random forests less predictive, but if you have two columns that are related to each other, you know this column is a little bit related to this column and this column is a strong driver of the dependent variable. Now, what's going to happen is that the importance is going to end up like kind of split between the two collinear columns, it's going to say like well both of those columns matter so kind of a split between the two. So, by removing some of those columns with very little impact, it makes your feature importance, block clearer, and so you can see here actually year made was pretty close to couple system before, but there must have been a bunch of things that are collinear with year made, Which makes perfect sense right, like old industrial equipment, wouldn't have had a bunch of kind of technical features that new ones would, for example.
So it's actually saying like okay, you made really really matters all right, so I trust this feature importance better. You know the predictive accuracy of the model is a tiny bit better, but this feature importance says a lot less familiarity to confuse us. So let's talk about how this works, it is actually really simple and not only is it really simple, it's a technique. You can use not just for random forests, but for basically any kind of machine learning model. And interestingly, almost no one knows that, like many people will tell you all this particular kind of model there's no way of like interpreting it and the most important interpretation of a model is knowing like which things are important and that's almost certainly not going to be True because there's technique, another teacher, she actually works to any kind of model. So here's what we're going to do we're going to take our data, set the bulldozers right and we've got this column, we're trying to predict right, which is price and then we've got all of our independent variables. Okay, so here's an independent variable here year made right plus a whole bunch of other variables and remember we had after we did a bit of hemming. We have 25 independent variables. Okay, how do we figure out how important year made is well? We've got our whole random first, but and we can find out our predictive accuracy where so we're going to put all of these rows through our random forest and we're going to spit out some predictions right and we're going to compare them to the actual price. You get in this case, for example, our root mean squared error and our R squared, and we're going to call that, like it's a starting point right so now, let's do exactly the same thing, but let's take the year made column and randomly shuffle it so randomly Permute just that column, so now you made has exactly the same, like distribution is to follow same mean, standard deviation, but it's going to have no relationship as a dependent variable at all, because we totally randomly reorder them so before we might have found our R squared With point eight nine right and then after we shuffle ear made we check again and now it's like point eight.
Oh, that's poor got much worse when we destroyed that variable and it's like okay, let's try again, let's put your made back to how it was and this time let's take enclosure and shuttle that right and we find this time an enclosure. It's point at four and we can say okay, so the amount of decrease in our score for year made was 0.09 and the amount of decrease in our score for enclosure was 0.05 right, and this is going to and I'll feature importances for each one of our Columns, yes, wouldn't just excluding, let's say each column, I'm running running the random forests and checking the decay in the perform. Yes, so you could remove the column and train a whole new, random forest, but that's going to be really slow. Where else this way, we can keep our random forest and just test the predictive accuracy of it again alright. So this is nice and fast by comparison. In this case, we just have to rerun every row forward through the forest for each shuffle column, Jason, we're just basically doing predictions of exactly okay question. So if you want to do like multi clone area, would you do two of them and random shuffle? And then three of them ran in trouble. Yes, so I don't think you need multicollinearity. I think you mean looking for interaction effects yeah. So if you want to say which pairs of variables are most important, you could do exactly the same thing each pair in in turn.
In practice, there are better ways to do that because that's obviously computationally pretty expensive and so we're trying to find time to do that again. Okay, so we now have a model which is a little bit more accurate and is we've learned a lot more about it? so we're out of time, and so what I would suggest you try doing now before the next class for this bulldozes data set, it's like go through the top. I don't know five or ten predictors and try and learn what you can about how to draw plots and pandas and try to come back with, like some insights, about like what's the relationship between a year made and the dependent variable.  Is there some noise in that column, which we could fix? There's some weird encodings in that column that we've fixed this idea. I had that maybe a couple system is there entirely because it's collinear with something else johner we might try and figure out, whether that's true or so. How would you do it fi product class desk? That brings alarm bells. For me, it sounds like it might be. A high cardinality, categorical variable: it might be something with lots and lots with levels because it sounds like it's like a model name so like go and have a look at that model name.
Does it have some order into it? Could you make it an ordinal variable to make it better? It doesn't have some kind of hierarchical structure in the stream that we can split it on like to create more sub columns.  Ideally, you've got a better accuracy than what I just showed, because we found some new insights or at least that you can tell the class about some things. You've learnt about how heavy industrial equipment options work in practice. Okay right, so your Tuesday


A micro-plugin for displaying unobtrusive announcements.
These announcements are highly customizable. They ship with very basic styles so you can easily override them or write your own. You can even customize the show/hide animation. Check out the docs to learn more.


| BIND 9 Administrator Reference Manual | ||
|---|---|---|
| Prev |
Although the "official" beginning of the Domain Name System occurred in 1984 with the publication of RFC 920, the core of the new system was described in 1983 in RFCs 882 and 883. From 1984 to 1987, the ARPAnet (the precursor to today's Internet) became a testbed of experimentation for developing the new naming/addressing scheme in an rapidly expanding, operational network environment. New RFCs were written and published in 1987 that modified the original documents to incorporate improvements based on the working model. RFC 1034, "Domain Names-Concepts and Facilities," and RFC 1035, "Domain Names-Implementation and Specification" were published and became the standards upon which all DNS implementations are built.
The first working domain name server, called "Jeeves," was written in 1983-84 by Paul Mockapetris for operation on DEC Tops-20 machines located at the University of Southern California's Information Sciences Institute (USC-ISI) and SRI International's Network Information Center (SRI-NIC). A DNS server for Unix machines, the Berkeley Internet Name Domain (BIND) package, was written soon after by a group of graduate students at the University of California at Berkeley under a grant from the US Defense Advanced Research Projects Administration (DARPA). Versions of BIND through 4.8.3 were maintained by the Computer Systems Research Group (CSRG) at UC Berkeley. Douglas Terry, Mark Painter, David Riggle and Songnian Zhou made up the initial BIND project team. After that, additional work on the software package was done by Ralph Campbell. Kevin Dunlap, a Digital Equipment Corporation employee on loan to the CSRG, worked on BIND for 2 years, from 1985 to 1987. Many other people also contributed to BIND development during that time: Doug Kingston, Craig Partridge, Smoot Carl-Mitchell, Mike Muuss, Jim Bloom and Mike Schwartz. BIND maintenance was subsequently handled by Mike Karels and O. Kure.
BIND versions 4.9 and 4.9.1 were released by Digital Equipment Corporation (now Compaq Computer Corporation). Paul Vixie, then a DEC employee, became BIND's primary caretaker. Paul was assisted by Phil Almquist, Robert Elz, Alan Barrett, Paul Albitz, Bryan Beecher, Andrew Partan, Andy Cherenson, Tom Limoncelli, Berthold Paffrath, Fuat Baran, Anant Kumar, Art Harkin, Win Treese, Don Lewis, Christophe Wolfhugel, and others.
BIND Version 4.9.2 was sponsored by Vixie Enterprises. Paul Vixie became BIND's principal architect/programmer.
BIND versions from 4.9.3 onward have been developed and maintained by the Internet Software Consortium with support being provided by ISC's sponsors. As co-architects/programmers, Bob Halley and Paul Vixie released the first production-ready version of BIND version 8 in May 1997.
BIND development work is made possible today by the sponsorship of several corporations, and by the tireless work efforts of numerous individuals.
The [hesiod] class is an information service developed by MIT's Project Athena. It is used to share information about various systems databases, such as users, groups, printers and so on. The keyword hs is a synonym for hesiod.
The chaos class is used to specify zone data for the MIT-developed CHAOSnet, a LAN protocol created in the mid-1970s.
IPv6 addresses are 128-bit identifiers for interfaces and sets of interfaces which were introduced in the DNS to facilitate scalable Internet routing. There are three types of addresses: Unicast, an identifier for a single interface; Anycast, an identifier for a set of interfaces; and Multicast, an identifier for a set of interfaces. Here we describe the global Unicast address scheme. For more information, see RFC 2374.
The aggregatable global Unicast address format is as follows:
3 | 13 | 8 | 24 | 16 | 64 bits |
FP | TLA ID | RES | NLA ID | SLA ID | Interface ID |
<------ Public Topology ------> | |||||
<-Site Topology-> | |||||
<------ Interface Identifier ------> |
Where
FP | = | Format Prefix (001) |
TLA ID | = | Top-Level Aggregation Identifier |
RES | = | Reserved for future use |
NLA ID | = | Next-Level Aggregation Identifier |
SLA ID | = | Site-Level Aggregation Identifier |
INTERFACE ID | = | Interface Identifier |
The Public Topology is provided by the upstream provider or ISP, and (roughly) corresponds to the IPv4 network section of the address range. The Site Topology is where you can subnet this space, much the same as subnetting an IPv4 /16 network into /24 subnets. The Interface Identifier is the address of an individual interface on a given network. (With IPv6, addresses belong to interfaces rather than machines.)
The subnetting capability of IPv6 is much more flexible than that of IPv4: subnetting can now be carried out on bit boundaries, in much the same way as Classless InterDomain Routing (CIDR).
The internal structure of the Public Topology for an A6 global unicast address consists of:
A 3 bit FP (Format Prefix) of 001 indicates this is a global Unicast address. FP lengths for other types of addresses may vary.
13 TLA (Top Level Aggregator) bits give the prefix of your top-level IP backbone carrier.
8 Reserved bits
24 bits for Next Level Aggregators. This allows organizations with a TLA to hand out portions of their IP space to client organizations, so that the client can then split up the network further by filling in more NLA bits, and hand out IPv6 prefixes to their clients, and so forth.
There is no particular structure for the Site topology section. Organizations can allocate these bits in any way they desire.
The Interface Identifier must be unique on that network. On ethernet networks, one way to ensure this is to set the address to the first three bytes of the hardware address, "FFFE", then the last three bytes of the hardware address. The lowest significant bit of the first byte should then be complemented. Addresses are written as 32-bit blocks separated with a colon, and leading zeros of a block may be omitted, for example:
3ffe:8050:201:9:a00:20ff:fe81:2b32
IPv6 address specifications are likely to contain long strings of zeros, so the architects have included a shorthand for specifying them. The double colon (`::') indicates the longest possible string of zeros that can fit, and can be used only once in an address.
Specification documents for the Internet protocol suite, including the DNS, are published as part of the Request for Comments (RFCs) series of technical notes. The standards themselves are defined by the Internet Engineering Task Force (IETF) and the Internet Engineering Steering Group (IESG). RFCs can be obtained online via FTP at ftp://www.isi.edu/in-notes/RFCxxx.txt (where xxx is the number of the RFC). RFCs are also available via the Web at http://www.ietf.org/rfc/.
[RFC2136] P. Vixie, S. Thomson, Y. Rekhter, and J. Bound, Dynamic Updates in the Domain Name System, April 1997.
[RFC2845] P. Vixie, O. Gudmundsson, D. Eastlake, 3rd, and B. Wellington, Secret Key Transaction Authentication for DNS (TSIG), May 2000.
[RFC1535] E. Gavron, A Security Problem and Proposed Correction With Widely Deployed DNS Software., October 1993.
[RFC1536] A. Kumar, J. Postel, C. Neuman, P. Danzig, and S. Miller, Common DNS Implementation Errors and Suggested Fixes, October 1993.
[RFC1183] C.F. Everhart, L. A. Mamakos, R. Ullmann, and P. Mockapetris, New DNS RR Definitions, October 1990.
[RFC2168] R. Daniel and M. Mealling, Resolution of Uniform Resource Identifiers using the Domain Name System, June 1997.
[RFC1876] C. Davis, P. Vixie, T., and I. Dickinson, A Means for Expressing Location Information in the Domain Name System, January 1996.
[RFC2052] A. Gulbrandsen and P. Vixie, A DNS RR for Specifying the Location of Services., October 1996.
[RFC2163] A. Allocchio, Using the Internet DNS to Distribute MIXER Conformant Global Address Mapping, January 1998.
[RFC1464] R. Rosenbaum, Using the Domain Name System To Store Arbitrary String Attributes, May 1993.
Internet Drafts (IDs) are rough-draft working documents of the Internet Engineering Task Force. They are, in essence, RFCs in the preliminary stages of development. Implementors are cautioned not to regard IDs as archival, and they should not be quoted or cited in any formal documents unless accompanied by the disclaimer that they are "works in progress." IDs have a lifespan of six months after which they are deleted unless updated by their authors.


--- layout: help title: Meld - Help ---
When viewing large folders, you may be interested in only a few files among the thousands in the folder itself. For this reason, Meld includes a flattened view of a folder; only files that have not been filtered out (e.g., by Version control state filtering) are shown, and the folder hierarchy is stripped away, with file paths shown in the Location column.
You can turn this flattened view on or off by unchecking the View ▸ Flatten menu item, or by clicking the corresponding Flatten button on the toolbar.


I originally created this as a short to-do list of study topics for becoming a software engineer, but it grew to the large list you see today. After going through this study plan, I got hired as a Software Development Engineer at Amazon! You probably won’t have to study as much as I did. Anyway, everything you need is here.
The items listed here will prepare you well for a technical interview at just about any software company, including the giants: Amazon, Facebook, Google, and Microsoft.
This is my multi-month study plan for going from web developer (self-taught, no CS degree) to software engineer for a large company.
This is meant for new software engineers or those switching from software/web development to software engineering (where computer science knowledge is required). If you have many years of experience and are claiming many years of software engineering experience, expect a harder interview.
If you have many years of software/web development experience, note that large software companies like Google, Amazon, Facebook and Microsoft view software engineering as different from software/web development, and they require computer science knowledge.
If you want to be a reliability engineer or operations engineer, study more from the optional list (networking, security).
When I started this project, I didn’t know a stack from a heap, didn’t know Big-O anything, anything about trees, or how to traverse a graph. If I had to code a sorting algorithm, I can tell ya it wouldn’t have been very good. Every data structure I’ve ever used was built into the language, and I didn’t know how they worked under the hood at all. I’ve never had to manage memory unless a process I was running would give an “out of memory” error, and then I’d have to find a workaround. I’ve used a few multidimensional arrays in my life and thousands of associative arrays, but I’ve never created data structures from scratch.
It’s a long plan. It may take you months. If you are familiar with a lot of this already it will take you a lot less time.
How to use it
Everything below is an outline, and you should tackle the items in order from top to bottom.
I’m using Github’s special markdown flavor, including tasks lists to check progress.
Create a new branch so you can check items like this, just put an x in the brackets: [x]
Fork a branch and follow the commands below
Fork the GitHub repo https://github.com/jwasham/coding-interview-university by clicking on the Fork button
Some videos are available only by enrolling in a Coursera or EdX class. These are called MOOCs. Sometimes the classes are not in session so you have to wait a couple of months, so you have no access.
I'd appreciate your help to add free and always-available public sources, such as YouTube videos to accompany the online course videos.
I like using university lectures.
Get hands-on practice with over 100 data structures and algorithm exercises and guidance from a dedicated mentor to help prepare you for interviews and on-the-job scenarios.
You need to be very comfortable in the language and be knowledgeable.
Read more about choices: - http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/ - http://blog.codingforinterviews.com/best-programming-language-jobs/
You need to choose a language for the interview (see above).
Here are my recommendations by language. I don’t have resources for all languages. I welcome additions.
If you read through one of these, you should have all the data structures and algorithms knowledge you’ll need to start doing coding problems. You can skip all the video lectures in this project, unless you’d like a review.
This list grew over many months, and yes, it kind of got out of hand.
Here are some mistakes I made so you’ll have a better experience.
1. You Won’t Remember it All
I watched hours of videos and took copious notes, and months later there was much I didn’t remember. I spent 3 days going through my notes and making flashcards, so I could review.
Keep in mind I went overboard and have cards covering everything from assembly language and Python trivia to machine learning and statistics. It’s way too much for what’s required.
Note on flashcards: The first time you recognize you know the answer, don’t mark it as known. You have to see the same card and answer it several times correctly before you really know it. Repetition will put that knowledge deeper in your brain.
An alternative to using my flashcard site is Anki, which has been recommended to me numerous times. It uses a repetition system to help you remember. It’s user-friendly, available on all platforms and has a cloud sync system. It costs $25 on iOS but is free on other platforms.
My flashcard database in Anki format: https://ankiweb.net/shared/info/25173560 (thanks [@xiewenya](https://github.com/xiewenya)).
3. Start doing coding interview questions while you’re learning data structures and algorithms
You need to apply what you’re learning to solving problems, or you’ll forget. I made this mistake. Once you’ve learned a topic, and feel comfortable with it, like linked lists, open one of the coding interview books and do a couple of questions regarding linked lists. Then move on to the next learning topic. Then later, go back and do another linked list problem, or recursion problem, or whatever. But keep doing problems while you’re learning. You’re not being hired for knowledge, but how you apply the knowledge. There are several books and sites I recommend. See here for more: Coding Question Practice.
4. Review, review, review
I keep a set of cheat sheets on ASCII, OSI stack, Big-O notations, and more. I study them when I have some spare time.
Take a break from programming problems for a half hour and go through your flashcards.
5. Focus
There are a lot of distractions that can take up valuable time. Focus and concentration are hard. Turn on some music without lyrics and you’ll be able to focus pretty well.
What you won’t see covered
These are prevalent technologies but not part of this study plan:
SQL
Javascript
HTML, CSS, and other front-end technologies
The Daily Plan
Some subjects take one day, and some will take multiple days. Some are just learning with nothing to implement.
Each day I take one subject from the list below, watch videos about that subject, and write an implementation in: - C - using structs and functions that take a struct * and something else as args - C++ - without using built-in types - C++ - using built-in types, like STL’s std::list for a linked list - Python - using built-in types (to keep practicing Python) - and write tests to ensure I’m doing it right, sometimes just using simple assert() statements - You may do Java or something else, this is just my thing
Why code in all of these? - Practice, practice, practice, until I’m sick of it, and can do it with no problem (some have many edge cases and bookkeeping details to remember) - Work within the raw constraints (allocating/freeing memory without help of garbage collection (except Python or Java)) - Make use of built-in types, so I have experience using the built-in tools for real-world use (not going to write my own linked list implementation in production)
I may not have time to do all of these for every subject, but I’ll try.
This is a short book, but it will give you a great handle on the C language and if you practice it a little you’ll quickly get proficient. Understanding C helps you understand how programs and memory work
[ ] Gotcha: you need pointer to pointer knowledge: (for when you pass a pointer to a function that may change the address where that pointer points) This page is just to get a grasp on ptr to ptr. I don’t recommend this list traversal style. Readability and maintainability suffer due to cleverness.
[ ] Implement using linked-list, with tail pointer:
enqueue(value) - adds value at position at tail
dequeue() - returns value and removes least recently added element (front)
empty()
[ ] Implement using fixed-sized array:
enqueue(value) - adds item at end of available storage
dequeue() - returns value and removes least recently added element
empty()
full()
[ ] Cost:
a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you’d need the next to last element, causing a full traversal each dequeue
enqueue: O(1) (amortized, linked list and array [probing])
You probably won’t see any dynamic programming problems in your interview, but it’s worth being able to recognize a problem as being a candidate for dynamic programming.
This subject can be pretty difficult, as each DP soluble problem must be defined as a recursion relation, and coming up with it can be tricky.
I suggest looking at many examples of DP problems until you have a solid understanding of the pattern involved.
[ ] Videos:
the Skiena videos can be hard to follow since he sometimes uses the whiteboard, which is too small to see
Know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise.
You can expect system design questions if you have 4+ years of experience.
Scalability and System Design are very large topics with many topics and resources, since there is a lot to consider when designing a software/hardware system that can scale. Expect to spend quite a bit of time on this
For even more, see “Mining Massive Datasets” video series in the Video Series section
[ ] Practicing the system design process: Here are some ideas to try working through on paper, each with some documentation on how it was handled in the real world:
This section will have shorter videos that you can watch pretty quickly to review most of the important concepts.
It's nice if you want a refresher often.
[ ] Series of 2-3 minutes short subject videos (23 videos)
Now that you know all the computer science topics above, it’s time to practice answering coding problems.
Coding question practice is not about memorizing answers to programming problems.
Why you need to practice doing programming problems: - Problem recognition, and where the right data structures and algorithms fit in - Gathering requirements for the problem - Talking your way through the problem like you will in the interview - Coding on a whiteboard or paper, not a computer - Coming up with time and space complexity for your solutions - Testing your solutions
There is a great intro for methodical, communicative problem solving in an interview. You’ll get this from the programming interview books, too, but I found this outstanding: Algorithm design canvas
No whiteboard at home? That makes sense. I’m a weirdo and have a big whiteboard. Instead of a whiteboard, pick up a large drawing pad from an art store. You can sit on the couch and practice. This is my “sofa whiteboard”. I added the pen in the photo for scale. If you use a pen, you’ll wish you could erase. Gets messy quick. I use a pencil and eraser.
See Resume prep items in Cracking The Coding Interview and back of Programming Interviews Exposed
Be thinking of for when the interview comes
Think of about 20 interview questions you’ll get, along with the lines of the items below. Have 2-3 answers for each. Have a story, not just data, about something you accomplished.
Why do you want this job?
What’s a tough problem you’ve solved?
Biggest challenges faced?
Best/worst designs seen?
Ideas for improving an existing product
How do you work best, as an individual and as part of a team?
Which of your skills or experiences would be assets in the role and why?
What did you most enjoy at [job x / project y]?
What was the biggest challenge you faced at [job x / project y]?
What was the hardest bug you faced at [job x / project y]?
What did you learn at [job x / project y]?
What would you have done better at [job x / project y]?
Have questions for the interviewer
Some of mine (I already may know answer to but want their opinion or team perspective):
How large is your team?
What does your dev cycle look like? Do you do waterfall/sprints/agile?
Are rushes to deadlines common? Or is there flexibility?
How are decisions made in your team?
How many meetings do you have per week?
Do you feel your work environment helps you concentrate?
What are you working on?
What do you like about it?
What is the work life like?
How is work/life balance?
Once You’ve Got The Job
Congratulations!
Keep learning.
You’re never really done.
*****************************************************************************************************
*****************************************************************************************************
Everything below this point is optional.
By studying these, you'll get greater exposure to more CS concepts, and will be better prepared for
any software engineering job. You'll be a much more well-rounded software engineer.
*****************************************************************************************************
*****************************************************************************************************
Additional Books
These are here so you can dive into a topic you find interesting.
Important: Reading this book will only have limited value. This book is a great review of algorithms and data structures, but won’t teach you how to write good code. You have to be able to code a decent solution efficiently
AKA CLR, sometimes CLRS, because Stein was late to the game
The first couple of chapters present clever solutions to programming problems (some very old using data tape) but that is just an intro. This a guidebook on program design and architecture
Additional Learning
I added them to help you become a well-rounded software engineer, and to be aware of certain
technologies and algorithms, so you'll have a bigger toolbox.
Know at least one type of balanced binary tree (and know how it’s implemented):
“Among balanced search trees, AVL and 2/3 trees are now passé, and red-black trees seem to be more popular. A particularly interesting self-organizing data structure is the splay tree, which uses rotations to move any accessed key to the root.” - Skiena
Of these, I chose to implement a splay tree. From what I’ve read, you won’t implement a balanced search tree in your interview. But I wanted exposure to coding one up and let’s face it, splay trees are the bee’s knees. I did read a lot of red-black tree code
Splay tree: insert, search, delete functions If you end up implementing red/black tree try just these:
Search and insertion functions, skipping delete
I want to learn more about B-Tree since it’s used so widely with very large data sets
In practice: From what I can tell, these aren’t used much in practice, but I could see where they would be: The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidly balanced than red–black trees, leading to slower insertion and removal but faster retrieval. This makes it attractive for data structures that may be built once and loaded without reconstruction, such as language dictionaries (or program dictionaries, such as the opcodes of an assembler or interpreter)
In practice: Splay trees are typically used in the implementation of caches, memory allocators, routers, garbage collectors, data compression, ropes (replacement of string used for long text strings), in Windows NT (in the virtual memory, networking and file system code) etc
These are a translation of a 2-3 tree (see below).
In practice: Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as real-time applications, but it makes them valuable building blocks in other data structures which provide worst-case guarantees; for example, many data structures used in computational geometry can be based on red–black trees, and the Completely Fair Scheduler used in current Linux kernels uses red–black trees. In the version 8 of Java, the Collection HashMap has been modified such that instead of using a LinkedList to store identical elements with poor hashcodes, a Red-Black tree is used
In practice: For every 2-4 tree, there are corresponding red–black trees with data elements in the same order. The insertion and deletion operations on 2-4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2-4 trees an important tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce 2-4 trees just before red–black trees, even though 2-4 trees are not often used in practice.
Fun fact: it’s a mystery, but the B could stand for Boeing, Balanced, or Bayer (co-inventor).
In Practice: B-Trees are widely used in databases. Most modern filesystems use B-trees (or Variants). In addition to its use in databases, the B-tree is also used in filesystems to allow quick random access to an arbitrary block in a particular file. The basic problem is turning the file block i address into a disk block (or perhaps to a cylinder-head-sector) address
MIT 6.851 - Memory Hierarchy Models (video) - covers cache-oblivious B-Trees, very interesting data structures - the first 37 minutes are very technical, may be skipped (B is block size, cache line size)
k-D Trees
Great for finding number of points in a rectangle or higher dimension object
I added these to reinforce some ideas already presented above, but didn't want to include them
above because it's just too much. It's easy to overdo it on a subject.
You want to get hired in this century, right?