Data Science for beginners full course part 2

Um, so really filling out the design space, uh, here since around 2006. And the only other point I make is that these, these quite popular document-oriented data model systems, CouchDB and MongoDB, have actually been around for quite a while. So they've been, you know, they released 2005 and 2007. So sometimes I think they seem like newer systems, but, but they've, they have some maturity. Okay.

So then finally, one, one of the points I want to make is about this column called that I've called joins and analytics. And so one of the distinguishing features of NoSQL systems is that they, they typically don't support any notion of joins. And, you know, many the proponents of these systems would argue that that's okay, that the joins aren't really necessary.

So the argument about why you can get away from joins goes something like this: when you're joining two tables, you sort of have one record and a bunch of corresponding records in another table. Well, if I put all those corresponding records and collocate them with the parent record, right, then I can access everything all at once and I don't actually need to compute the join. Okay. So that works, and it should sound somewhat, sort of familiar because it was part of these Network and hierarchical data models that we talked about in the discussion of how we motivated relational databases. And if you remember that the downside of this was that you had kind of one dominant access path into the data, but any other access path was either not supported at all or was inefficient. Okay. And if you wanted to reorganize your data to support a different access path, or because your, your needs changed, well, a lot of your code might have broken, and you would need to sort of rewrite it. Okay.

And so this tension between buying yourself a little bit of performance by organizing the data in, in a, in a pretty rigid way versus the development time that you save by not having to rewrite your code whenever you want to reorganize the data felt, you know, that, that, that equation sort of balanced a certain way in the early 1970s, and I would claim that it still balances the same way now. Now this is not to say that commercial databases, relational databases as they stand today are necessarily meeting everybody's needs. I think they're clearly not for a variety of reasons. But to sort of throw out what we know and, you know, give up on this flexibility that was earned from the relational data model in favor of kind of upfront decisions about one dominant way of organizing the data, I'm not sure that's the right one either. In order to, so that's one point I want to make.

Another point is that there's not necessarily one right way of decomposing things, or one right way of even evaluating a join, even if you support them. Okay. And this is a point I want maybe before, but I want to bring it up again in the context of NoSQL. So in a, in a pretty classical web application scenario, you, if you want to show all comments by a user named Sue associated with any blog post by a user named Jim, there's a couple different ways you could do this. You could look up all blog posts associated with Jim and then fetch all corresponding comments, filtering for Sue, or you could go the other way. You could find all comments by Sue and then for each of those comments look up all the blog posts by Jim. And one or either one of these ways may or may not be available to you if you've already organized your data a particular way. But even if they are available to you, it's not clear which one's the right one, and there may even be a third method that sounds a little wild, but it's: filter all comments by Sue and then independently filter all posts for Jim, sort them by some sort of blog ID, and then pull one from each list and walk over the data that way. So that sounds a little wacky, but that's just a sort-merge join that you may or may not be familiar with, and if you're not, that's okay. But the point is all three of these are perfectly valid, and the right one depends on the details of the data that you, as a programmer, as an application programmer, may or may not have access to, and that may change from time to time. And so really only the system is equipped to make this, uh, make this decision. And so being, you know, sort of succumbing to the tyranny of the, of the, you know, initial design decision at the time the database was, uh, built or designed is one problem. Another problem is that even if you have some flexibility, leaving it up to the programmer to make the choice over the right way to access the, access the data, uh, is asking them to do, to make a decision for which they aren't equipped, that they aren't equipped to make. Okay. And so this is something that does not happen with relational databases; neither one of these problems exists in the same way. Okay.

So I think trying to inject some of that smarts back into these NoSQL systems is, is a good idea, and we see that trend happening. Okay. So that's maybe the takeaway that I want you to have. Okay. So that's all I want to say about this grid, but let me give you a little bit of a characterization of a response to NoSQL by Mike Stonebraker in Communications of the ACM. And there was a couple of different blog posts here that talked about two different arguments in favor of NoSQL and responded to each one of those arguments. And so I'm mostly going to focus on the second one. So those two, uh, pro-NoSQL arguments are these: he points out that there's two value propositions offered by the NoSQL community: one is performance, and the story, as Mike says, that I more or less agree with, is that, you know, these people started out with a MySQL deployment of some kind, and they had a hard time scaling it out in a distributed environment. And then they had two choices, you know, either they could invest in a, uh, large-scale relational database and pay corresponding license fees, or they could do something different, use one of these NoSQL systems. All right.

And then the flexibility argument is like, well, look, you know, my data doesn't conform to a rigid schema. So in the performance argument, uh, I'm not going to spend too much time on this because we talked about the tradeoffs associated with different choices in transactional guarantees in these various systems. And the other part of the argument that, uh, Mike makes has more to do with database internals that we didn't necessarily cover. So let me focus on the flexibility argument. So an observation that he makes that I think I'd probably agree with is that, you know, who are the customers of these NoSQL systems? And so it's a lot of startups, a lot of web startups, and it's not quite such the same penetration in the Enterprise, okay, at least not yet. So why is this? Well, one argument is that most of the applications in the Enterprise are traditional OLTP, and if you don't know what OLTP means, online transaction processing. And so these are sort of, you know, bank records, right, things where getting the transactions right really matters. Okay. And it's further, it's OLTP on structured, organized data. And so there's a few other applications around the edges, but they're perhaps considered less important. Right, it's okay to take a high-risk system because the application itself is of less interest to, you know, Executives. Okay. And so really, no, no asset compliance, you know, no transactions is equivalent to not much interest in the system. You know, it's not okay to screw up mission-critical data, but for that, you know, for some other application around the edge, maybe it's okay to experiment with a NoSQL system. Okay.

And then another second point he makes is that, you know, relying on these low-level query interfaces is a, a real tough sell. And you, he calls up Quel, which is an early data manipulation language that predated the declarative language that we've been talking about, but we've sort of been down that road, and it's tough, and it's why these higher-level languages were invented. And again, we see the, we see it with MapReduce, which is admittedly analytics as opposed to pure NoSQL, but we see that the value of these higher-level interfaces pays off. Okay. And the third point he makes is that, you know, NoSQL means all bets are off, right? There's, there's no, there's no sort of homogeneity at all between all these different deployments. And so in, in a typical Enterprise, you have, you know, maybe 10,000 databases. You already have enough of a trouble trying to integrate data from these databases because of the heterogeneity within their schemas, but at least you know that you're always working with rows and columns, and at least you have kind of a standard interface to manipulating them. Okay. And so having, you know, the number of design decisions that you have to make to encode your data in one of these NoSQL systems, you know, what becomes the key, what becomes the value, are the blog posts nested under the comments or the comments nested under the blog posts? Right? Do users keep their own wall, or do the, you know, the messages on their, on their front page, or does the person who wrote the message keep access to it, or both? Right? All these different design decisions of nesting layers and so forth, uh, complicate integration and complicate standards. Okay. So it's, it's a, it's a tough sell. You know, the other point that I guess I like to make, this related to this, this third one here, is that, you know, there's no real free lunch, right? Either the complexity is going to be in the system that you use to model the data, or you're going to sort of hand it over to the application, but in some sense, they're always these schemas, right? This, this, uh, application business model is going to be encoded somewhere. So having it centralized in the, in the data system as opposed to, uh, hidden more than once in various applications that access the data system seems like a good idea. [Music] Okay. Okay.

So I want to talk a little bit about the system Pig, and there's a couple of reasons for this: one is it represents, uh, this language layer on top of MapReduce, which I think is pretty important, as I've, as I've mentioned before, and it also represents a more direct interface to relational algebra, uh, which I've argued is really the important abstraction from databases. SQL happens to be sort of intergalactic data speak, uh, and is, you know, the universal language for programming databases and manipulating data in databases, but really the, the secret sauce and the technology that makes it effective is this underlying formalism of relational algebra. And Pig and a few other systems sort of expose this as, as a, as a first-class citizen. And it's not necessarily the only way to do it or necessarily the better way to do it, but it does, but since you can see the relational algebra directly, I think it's a nice thing to be familiar with. Okay. Uh, and it also, I think, makes the point that, you know, you, you can cherry-pick a little bit what features you bring. So while it's very obviously inspired by relational algebra, and of course, you, if you look in the sort of people that developed it, you can see why, it definitely changes some things about the relational model, and I, and I think that's an important point too, is that we can use this relational algebra abstraction, uh, independently of some of the systems that it came from. We can make whatever changes we need and keep, you know, keep what we like and throw out what we don't like. And so I want, you know, I want you to sort of put your relational algebra goggles on and see the world in terms of relational algebra. I think it, it's pretty effective for working with, uh, not just data in general, but especially, uh, big data and reason about very scalable algorithms. Okay.

So fine. So what is Pig? So Pig is an engine for executing programs on top of Hadoop. Okay. So you're going to write a Pig program in Pig, and it's going to generate a sequence of MapReduce jobs that implement that program. Okay. And the language here is called Pig Latin, and it's an Apache open-source project, and you can read more about it. Okay. And so why, why bother doing this? Well, if you're, if coming from, if you're a MapReduce programmer, you're happy with MapReduce, why would you bother doing this? Well, suppose you have data in one file and data from websites in, sorry, user data in one file and website data in another, and you need to find the top most visited sites by user in a particular age range. And so if you're thinking in terms of SQL, you can probably think about how to express this task as a query, uh, and here's a pictorial representation of it that sort of shows a, a data flow here: we're going to load users, we'll load the pages, we'll filter by age, do some kind of join on name, group, count up the clicks, order by clicks, and then take the top five. This may, may not be the way you draw it on the whiteboard if you were to express it yourself, but it's a, but it's a reasonable way of describing the problem. Well, in MapReduce, there's 170 lines of code, and at least in one example coming from the papers here, it took someone four hours to write it. These kind of metrics of how long it, how development time are not, never too compelling because it kind of depends on their background and their skill set and, um, so on, but still a decent amount of time, while the same program in Pig Latin is just nine lines of code and takes, you know, at least in this case, 15 minutes to write. And further, you know, does sort of capture some of this more abstract description of what's going on. Now, this a little bit contrived because these boxes obviously correspond to sort of particular Pig commands, but I'd argue that that this, even non-people that don't know Pig, if they were to ask sort of what the tasks are in evaluating this English question, they might come up with something along these lines; they may, may not say join, but some of these steps would be, would be present. So I think it, you could wave your hands a little bit and say that that it captures a little bit of the natural language description of the task. Okay. You may or may not buy that. Fine.

So here's what it looks like: load the user data according to a particular schema, filter the user data based on the age range, load the pages data, perform join, group, then you say, well, for each, uh, group, count the number of clicks, and we'll talk, this one, this one probably looks the least like relational algebra, and we'll talk about it, and then sort the thing, and then just take the top five and store that result into a new file. Okay. And so the point here is that you can also think, well, boy, I could just write all this in Python, right? That'd be much easier; why do I need to use this new language? Well, the point is that this, each one of these steps, well, not actually, not each one, groups of these steps correspond to individual MapReduce jobs, which mean they scale really, really well, right? Doesn't matter how big your users table is, it doesn't matter how big your pages table is, this program will work. Okay.

So how does the system work? Well, the programmer is going to enter a Pig Latin program by writing these commands, uh, and assigning the results to variables, and then you can refer to the variables in future commands. So this is, you know, we've, we've loaded data into this variable A, loaded into variable B, and, uh, then you can filter by reference to A and store the result in C, and so on. Okay. And then we'll make this point again later, but nothing actually happens, no work is actually done until you try to actually write out the results. So this is sort of what we call lazy, lazy evaluation. All right. So fine. So what happens when you write this program? Well, the Pig parser will turn the syntax of the program into an abstract representation of the, uh, program called an execution plan. And so this is using parlance from databases, and the lead of the Pig project is a, is a great database guy named Chris Olston. Okay. So this abstract representation of the plan, you know, these operators, these operations that I'm going to call operators again using database parlance, are sort of one-to-one with the commands, although they, they need not always be. Okay. But we're not done there; that's just the execution plan; still sort of, we can't actually execute that. What we need to do is compile that down into MapReduce jobs, and the game here is going to sort of be to minimize the number of MapReduce jobs you need because there's a lot of overhead to executing one of these. So you don't want to run a whole MapReduce job just to filter a data set; you might as well lump that in with other work that you're already doing. As long as you're scanning the data and reading off the disk, you might as well do as much as you can with it. And so, for example, in this case, this program can all be implemented as just one single MapReduce job: job one. In the map phase, you load the data, you filter it, and you also load the other data set, and the reduce phase you do the join. Okay. And we'll see another example of this a little later on. And then finally, this, these MapReduce jobs are scheduled on a Hadoop cluster as usual and run, um, as usual. Okay.

These performance results are a, a little funny, but I sort of, I sort of, I still like the argument being made. This is Pig performance versus MapReduce. Okay. So this is a little funny because Pig is built on top of MapReduce, but the point is is that the first version of Pig in September 11th, 2008, was a lot slower than, than just writing the thing raw against MapReduce, but with some various improvements, it got better and better over time until eventually it was just as fast as the handwritten MapReduce, and I think you see this sort of pattern quite a bit that that there is a cost to abstraction, but that you can, you typically can recover a lot of the performance of the hand-coded stuff, meanwhile having gained some measure of programmer productivity by offering a higher-level interface. Okay. And so I just like the fact that they actually just bothered telling the story; they admitted that they were quite slow in the beginning; they got faster over time. Okay.

All right. So, so what's the data model here? So there's four, uh, types involved here: one is the atom, which is just a, a primitive, right, an integer, a string, and so on. And then there's three different collection types: one is a tuple, and these should be familiar from our first assignment; we worked with Python, right? So there's these three, all exist in, well, I shouldn't say that actually, bag is a little funny to think about in terms of Python. Let me just say, right, the first is a tuple, which is a sequence of fields, and every field can be of any type; they need not be atoms. Okay. Then there's a bag, which is a collection of tuples, always tuples, but those tuples need not be the same type. So this is different than a table, different than a relation. Okay. And it's a bag, not a set, and, you know, I guess I'll, I can ask you what's the difference between a bag and a set? Well, a bag allows duplicates. Okay. And then the third type is a map, which is a little bit confusing because we're talking about MapReduce, but this is a dictionary in Python, right? So string literal keys map to any other type. Okay.

So let's look at an example of this. So what is this thing? Well, it depends on my notation, I guess, but assuming that you don't mind my angle brackets referring to tuples, then you can see that this outer thing is a tuple, and it has three fields: it has an integer, which is just an atom, and then it has this thing, which is a bag—the curly braces I'm going to use to indicate bag—and then it's got this thing, excuse me, which is a map, a dictionary that has just one element in it, mapping the key Apache to the value search. Okay. So let's name these guys F1, F2, and F3, and we'll, uh, point out in the couple, in a couple of slides where those names can come from; there's a few different places they can come from, and I'll point out one of those sources soon, but right now, just assume that we…

Have them okay okay. So let's consider these expressions over this type. So we can write dollar sign zero, and what that means is give me the first field in the tuple. All right. So in this case, it's just the number one. We can also access it by name. So if we access F2, it will give us the second field, just because we gave it that explicit name. There's nothing magic about F, nothing magic about two, and that'll give us a bag with these values in it. By the way, we should say what what are the elements of this bag? Well, they're tuples with two integers each. Okay.

Now you can also access F2 to give me—so what does this expression do? Well, F2 gives me the bag, and then you can write dot dollar sign zero. And I don't love this notation; it's a bit of an abusive notation, but what it means is for every element of the bag, project out the first element. And so this will give me another bag, but it only has two and four and five. It has the the the zeroth element of every tuple. Okay. Then you've got this magic hash symbol here, which means find me the value associated with the key I'm about to provide. So look at F3, which is the the third field, and hash into it and give me the key Apache. If it's not a map, you're going to get an error, but in this case it is a map, and so what gets returned is the atom search. Okay.

Then you can also write functions. You can say sum up uh all of these values, and this expression is the same one we saw here, which will be a sequence of integers, and so that'll give you 2 + 4 + 5. Okay. And there's a few different other ways to sort of manipulate these things, but the first thing to note is that this is non-relational. Right? You've got these nested data structures; you've got a few different data types. [Music]

All right. So let's go over some of the commands in Pig. So the first one is load, which is how you get data into the system. And here the, you know, data is on HDFS in a Hadoop cluster. And the logical data model, the the each input data set is assumed to be a bag, which is a sequence of tuples. Okay. So you can specify, you know, you can just say load, but you can also specify the function you're going to use to parse the data uh with this keyword using. And this seems like sort of just a trivial implementation detail, but there's actually kind of an interesting point and really gets to the heart of one of the problems with many database products and one of the advantages of these map-reduce-based systems is that sometimes you're presented with data that's in its raw form, and you need to uh parse it yourself. Okay.

And so the database value proposition is, well, look, you know, design a schema and load all the data into the schema, and after that you'll be able to get all these benefits from querying. Well, look, who's going to do that loading task? Right? That's a big parallel job. If I've got 20 terabytes of text files, somehow I've got to do I've got to manage that computation. And so this is where uh Hadoop and also therefore Pig and Hive come into play. And so a lot of times what you'll see is that the application for a say data science system, you know, data science application will be architected uh where Hadoop and extensions are being used to do the ETL processing, parsing, you know, and loading, and then the result of that is loaded into more conventional databases for kind of ad hoc querying. And we saw this uh in the very very first segment. We talked about the Obama campaign using this architecture as well. They, at least in an article, you can sort of infer that they had used a similar article; they mentioned Hadoop for the ETL workload—extract, transform, load—another piece of jargon—and then they mentioned this Vertica database for the slicing and dicing. Okay. And you see this you see this; it's almost becoming a commit—a standard. I hate to use the word standard, but it's a best practice in designing these kind of data analysis uh architectures at scale. Okay.

So fine. So what's nice about this is that you can specify your own parsing function, so you can work with data in its raw format. All right. And then further, you can specify a schema. If your parsing function is capable of producing lots of different things, you can say here are the names of the columns that I want to apply. So this is one source of where these column names are going to come from, as you specified them right there in the load command. So this is kind of schema on read, if you will. Right? There's no schema associated with the data; it's not self-describing, but you can impose a schema on it as you read it into memory. Okay. Fine. And so maybe this is what we get back; we get back a sequence of tuples, and we'll use this as a running example. All right.

So the next command is filter, which is pretty simple. You just get rid of some of these tuples, and you can have arbitrary Boolean conditions. You can do kind of regular—because everything's very text-based in the Hadoop world, which is in some cases a limitation—and the syntax looks like this: you say filter some big data set by some condition. And so in this case, filter where F1 equals 8, and remember that F1 was the name we we gave it in the load command—the the name we gave to the very first column—and so this finds all the uh tuples where the first position is equal to eight. Fine.

So the next command is group, which is bringing data together. Okay. And so there's a couple different forms of this, uh but we're going to focus on—so this just right now we're just talking about group. Okay. There's a cogroup command that I'm going to talk about in a moment. All right. So group says group this large data set by some sequence of columns. Okay. So this looks a lot like the SQL clause that has that's the same; it's got the same sort of flavor, but it does something pretty different. Okay. So grp, if this is a and we group by F1, well what we get out is tuples, but now the first column is the same because we grouped by F1, but the second column, the second field I should say, is now a bag, a little group representation of all the tuples that were associated with this with this particular key. And so if you look over here, there's only one tuple with with one, and that tuple appears in the group. There's two tuples with F1 equal to four, and so this bag has two tuples in it, and so on. Okay. So this is how you you can start off with something that's kind of a flat structure, and you can build up a nested structure for various reasons, and we'll see why.

Now, the other thing to keep in mind, and this is another thing I don't really love about Pig because they're doing things sort of implicitly rather than explicitly, is that the name of this field—every field ends up having to have a name—and the name of this field is defaulted to the do the name group uh—yeah, sorry, I just lied. The first field is defaulted to the name group, and the second field is defaulted to the name of the original data set. And so I find this a little a little confusing when you're writing Pig yourself, but you can sort of see why they did it. The reason is is that just these bags all together actually have the same information as the original data set, just nested in a certain way. And so calling it a sort of makes sense; it's got all the same information. So, for example, notice that notice that the the value one is now repeated twice, once in the group, and it's still in the tuple. Okay.

So fine. So there's also a command distinct that does just what you might imagine; it gets rid of all duplicates. And just for a simple example here, if you've got two different elements in the bag that have the same value, you'll output will be will be this. Okay. I might make a claim that distinct a is equal to grouping of a by all three columns at once. So first of all, why am I making that claim? Well, remember that the group operator puts out a single tuple for every unique value of the grouping columns, so that sounds about right. Uh, and you can also maybe think from from if you know SQL that this is sort of true there, right? You can use this distinct keyword in in SQL, and you can also group by all the columns, and you'll end up getting the same result. So are these two expressions the same? Do they produce the same output? Well, not quite, because the grouping structure—sorry, the group command—produces a group field, which is now the whole tuple, excuse me, and uh the the a field, which is a bag with a single tuple in it. So you get this sort of repetition of information. So distinct is much more um concise. So you need to be careful and sort of make sure you understand what these things are going to produce.

So how does group work? Well, we already saw, you know, going back to our map-reduce schematic or our parallel processing schematic, we break the data into pieces; we apply a map function that assigns each tuple to its key and groups the tuples to in the value as well. And so here if we group by F1, then F1 becomes the key, and the value is all is all three of the elements in the tuple, and those are shuffled across the network to the reduced side, and the reduced side will construct this bag type out of the set of tuples. Okay. So this is a single map-reduce job. All right.

So the for each command is almost certainly the most complex one. So here you're basically going to manipulate each tuple in a bag. So you write it like this: you'll say for each a generate something, and here we're generating a tuple with two fields; one is F0, and one is the sum of F1 and F2. And here you can call user-defined functions, so you can write other kinds of arithmetic expressions; you can sort of do uh lots of things. Okay. Fine.

Another example is first we group a by F1 just like we did in the previous slide—excuse me, this should be Y—and then for each Y generate group. So what's group? Well, remember that's the magic name assigned given to the group field, and then Y, which is the magic name given to the bag field, dot a list of projection columns. And so this is the second element and the third element from each of those tuples. Okay. So what does this look like? Well, uh X, which is this first element here, well we get the first field from a, which is this column here, and then we get the sum of the second two, so 2 + 3 is equal to 5; 2 + 1 is equal to 3; 3 + 4 is equal to 7, and so on. Okay. Then down here for Z, remember that Y looks just like it did in the previous slide here—oh, well, no, sorry, I didn't actually do I didn't actually do the complete example of Y. So Y is all of a grouped by the first field, uh but then we're going to generate the grouping field, which is the same, and we're going to project out the second two columns; we're going to ignore the first column in each one of the bags. Okay. And so the point here being that you can manipulate these nested objects by writing these kinds of expressions, but I think the other sort of lurking point here is that it's a little bit complicated to think about what's going on because of this extra flexibility you get with the nested data model. Okay. So you'll get a in the assignment you'll get a chance to try some of these out and make sure you understand what they're doing. Okay.

So then there's this keyword flatten, and it's not really its own operator; you use it in the context of for each. And so here, you know, because of the complexity here, what you might really want is look, I just wanted to get rid of the—if you want to recover the flat version of the nested structures uh created and stored in the variable Z, well you can do so like this: for each X generate group, and then the flatten of X. And the result you'll get out here is uh the—regardless what it does is sort of peel out this bag and produce an extra tuple for each. And I don't really like this because it sort of changes—just using the keyword flatten changes the semantics of the for each and generate, and I think it's a very confusing way of doing it. So the idea—it's hard to explain the principle going on here—just sort of memorize what it does; practice with it and memorize what it does. All right. Okay.

So let's take a look at the cogroup command. So we've seen the group command, which we're using a single data set, and the cogroup command does the same thing on multiple data sets, and we've seen this mechanism before when we talked about map-reduce, but here in Pig we make this operation explicit and give it a specific command, and we'll try to see why that is. Okay. So the syntax looks like this: say cogroup data set by some field reference or multiple fields, and here we're referring to a field by name, and here we're referring to a field by position, as we've seen before. And so if this is a a bag of tuples and this is B a bag of tuples, then the cogroup of them looks like this. So now we have a group field, and we have a data set a a a field named a, and we have a field named B. All right. So we still have the same grouping key, but we have two groups associated with it, one from one data set and one from the other. Okay. So a couple things to point out: one is if if there are no tuples from one of the data sets, then it just gets the empty group. Here you see an example from B. And then the other thing to point out is this is a little different than what happens in MapReduce directly, where, you know, you we what we showed with with the uh join operator with map-reduce is that you could um use the join key to sort of cogroup two relations, and then all of these tuples would all sort of appear in the same group in the reducer, but here we sort of make them explicit to make it two separate groups. Okay. Fine.

So I want to come back to cogroup in a second, but first let's talk about another operator, which is just called join. And so it does exactly what you'd expect. So join: you say join a by some set of field references and B by some other set of field references. Okay. And given a and given B, the result will be what we've talked about in the past, which is, you know, you look for the first position of a dollar sign zero and find all the corresponding first positions of B. So here's one one and one, so we have one two from a and one and 313 from B. Okay. So there's nothing stopping you from having multiple data sets out here, as many as you want, and they can all be sort of processed together. So you can think about what's going on here is that this is one map-reduce job underneath the sheets, where in the map phase every tuple from a variety of data sets is all being associated with the join key uh represented by this field reference in the syntax and then shuffled across the network to arrive at the reduce uh phase. Okay.

So here's what it looks like. Well, if we have multiple relations represented by colors here—green, blue, and red—well, they can all be processed by the map phase and associated with keys, shuffled across the network to produce the join tuples here, right? So there's no there's nothing fundamentally binary about this operator, right? It's just processing tuples, associating with the with the respective join keys and shuffling them all across the network. What can go wrong with this basic mechanism of associating tuples with the join key, shuffling them across the network, and then you producing the, you know, computing the join on the reduced side, which is what we did in the assignment as well? Well, so one example might be if if one table is very very large and the other table is very very small. There's an opportunity to do something much much faster, which is replicate the small table across all partitions of the large table, which allows you to do the all the work in the map phase. Okay. The second sort of special case here is a skewed join. What I mean by that is if there are many values in one table that join with many many many values in the second table, then you'll end up with one reducer doing all the most of the work, and the effects of parallelism get sort of washed out. And the third special case algorithm is to do a merge join. So this takes advantage of the fact that you may have already uh grouped two relations in the same way such that the, you know, for sure that on a single machine I've got all the tuples I need from one relation and all the tuples I need from the other relation. Okay. So let me see if I can make this more clear in uh pictures in the next few slides. Okay.

So for a replicated join, the situation is we have one large table broken into pieces and one much smaller table. And so we could do is just uh shuffle all these tuples across the network and do the join in the reduce side as we do normally, but there's an opportunity here that says, well, look, if this thing is small enough to fit in memory on a single machine, why don't we just copy it, send it out there to every, you know, every map function that wakes up; we'll go pull it across the network uh directly. Okay. Then we have all the information we need right here in the map side. Every one of these tuples can be joined with corresponding tuples in this partition; every one of these tuples can be joined with corresponding tuples in this partition, and so on. And so at the end of the map phase, you end up with the right answer, all the join tuples for, you know, this this sort of blue a and this red red B. Okay. And so why is this cheaper? Well, we didn't have to shuffle everything across the network; we did it all in the map phase, and it makes a huge difference. Okay. So you might see this called a broadcast join um as well. So the small relation must fit in memory, uh and the idea is that each mapper in in the map function pulls a copy of the small relation directly out of HDFS. Okay.

All right. So for the skew join, the situation is is as usual; you've got two relations, this sort of blue one and this red one, and the map phase um associates each tuple with its join key, but the problem is that most of the data ends up on a single reducer, and the reason is because maybe most of the data here is associated with a single join key. Okay. So, for example, if you're joining on order ID and line item, you know, you're trying to associate all line items with their corresponding order, it could be that one order had millions of parts, and all the other orders had five parts or so. Okay. So if a if a significant fraction of the overall data set is associated with a single join key, then this reducer will be doing all the work, and there won't be much benefit of parallelism. Okay. So this would work, but there's a problem. So this is from a former student here at UW who did some work on this problem, and this plot shows time in seconds on this x-axis, and this is just a list of all the tasks. And so you see that the reduced tasks here, they aren't they can't start until all the map tasks are finished. Okay. And the map tasks mostly finish quite quickly, sort of maybe 20 seconds, but one or two of these map tasks take a very long time, you know, sort of on the order of 270 seconds or so. Okay. So all this space in here is sort of wasted work. There's a couple of problems here: one is fundamentally a map-reduce in in many applications; you logically actually could start doing some work early based on the based on the uh map output that's already been finished, and that's just not the way map-reduce is designed. Um You can't

Take. It's not designed to be able to take advantage of those applications because you can't guarantee that it's safe to do so. So, for example, if you're adding up numbers, you could start adding up in in the reduced phase; you could start adding up numbers early. But if you're doing something more complicated, you may actually need to wait for all the results to be present in order to get the correct result. And so, since they can't guarantee that it's safe, um, they make you wait. Okay, so fine.

So this skew problem ends up sort of killing parallelism and turns a job that you know could take sort of 50 seconds into one that takes 350 seconds. And it's not even significantly longer than doing this sequentially if you sort added all these pieces up. Well, I shouldn't say that this is so worse than sequential, but you certainly lose a lot of your bandwidth and parallelism. Okay, so one task might take five times as long as the average, and so there's little benefit. And so one takeaway here—so I'll tell you what one way, one way to partially solve this problem on the next slide—but the takeaway here is if someone asks you what the, you know, one of the biggest performance bottlenecks of MapReduce is, you should say stragglers, or skew. Skew is more of a term for this in the database community, but stragglers is maybe a little bit more common. Okay, so this is a straggler task that takes a lot longer.

All right, so what can we do about this? Well, here's the situation where we had a lot of keys that all ended up on the same reducer, and this guy's taking too long. One thing we can do is split this data up into more reducers. So take a, you know, allocate a few more reduced tasks and move that data over here and split it into three more. Now broadcast that little red relation. Right, so I I made it disappear from over here, recognizing that this is perhaps small, and replicate it to all three of these reducers. So sort of a combination of the replicated or broadcast join and the regular, um, reduce-side hash join. Okay, so now you've got three reducers working on this problem as opposed to just one, and you get things a little bit more balanced. And so this skew join is something that Pig can do if you specify it. All right, it won't do it automatically, though. So fine. And so now we get our entire joined relation, which is what we want.

So finally, merge join is the third special case, and this is—let's see—so the first, the first special case was an opportunity to do things much faster if one relation was very large and the other relation was very, was small enough to fit in memory. Uh, skew join is more of a—there's a problem that can occur, and you need a special trick to be able to address the problem. Merge join is more like the former; it's it's looking at an opportunity to use a more higher-performance algorithm uh when certain conditions are met. And so what are those conditions? Well, when you recognize that the red relation and the blue relation are already been co-partitioned on the appropriate join key, right, then the map phase alone has enough information to just compute the join itself; it doesn't actually need to assign it all to a assign tuple to a join key and shuffle it across the network. Right, so you know that all the line items for a particular order, you know, for every order that's here, all of its line items are also here on this machine. If you know that to be true, then you can do it in the map phase.

Okay, so the question may be, when is that true? Well, that's what we go back to the co-group operator. It's possible that you've already partitioned these two tables uh on the appropriate join key because of a previous command in Pig. Okay, and so it can be aware of that and use a merge, merge join—sorry—say be aware of that. It—you still specify explicitly that you want to use a merge join, but so Pig's not doing that automatically, but you can uh take advantage of this situation when it arises. All right, so since each mapper already has local access to the records from both relations, they're already grouped and sorted by the join key, you can just read both relations from disk in order and compute the join.

All right, so we have this co-group operation and we have join operation. Why do we need both? Well, the reason to make co-group explicit is that if you think about it, join is really a two-step process. Right, there's one step to uh create the groups based on the join key, and then a second step to actually produce the join tuples. But that group creation step is useful for a lot of applications, not just producing a join. So, for example, if you want to um co-group and add up all the contributions from each relation, you can do that in a single step. You don't need to sort of join the tuples first, then do another grouping afterward, which is something you would have to do in relational databases. So that's a chance to take what would be two MapReduce jobs and combining into just one. Okay, and so here I guess the example is if you want to just count the tuples. Okay, so but you know what to point out here is that you can express join. Join is essentially just syntactic sugar. You can express a join in terms of co-group. First step is to co-group on the same column on the on the join columns, and the second is to run this for each command that would generate a flat view of results and revenue—sorry, I guess I should say A and B here, that's sloppy, I changed the names. Okay, fine.

So other commands that we're not going to talk about in detail are store, which writes data out to HDFS, available for, you know, future commands; Union, that combines two data sets together and removes duplicates; cross product, which finds all possible pairs between two data sets, which can be useful if you're about to compute some sort of similarity function as we talked about; and then dump, which prints output to the screen; uh, and then order, which sorts, sorts the output.

Okay, so as an example of store here, remember you can also just, just like you can use your own custom function to parse data, you can also use your own custom function to write it out. Okay, which means it allows the data to be more compatible with, say, some other system that you're using, say MapReduce itself or some other application that expects data in a certain way. And so that's—again, I sort of stressed this with with the load command as well—but this is actually pretty powerful and a pretty big difference from this, you know, walled garden approach that relational databases take, where everything sort of goes in and then it's under complete control of the database. This sort of has more permeable boundaries where you can kind of have data lying around in whatever format, and you're still able to process it with Pig, but you can also process it with other, other systems as well. And so the reason this is crucially important is not just sort of a performance optimization for, you know, reduced load time or something, although sometimes that can help as well, is because this data is too big to move nowadays. Right, you can't put it all in the database and then suck it all out and move it over to some other system for for working with; it's just too big. You can't move a petabyte. Right, you have to bring the computation to the data as opposed to bring the data to the computation. Okay, and so these abilities to work with in-situ data, you know, produce sort of in-situ data, uh, is is emerging as a sort of a key requirement in this big data era that was not, not such a key requirement in the sort of era of relational databases. [Music]

Okay, so let's consider an example of a Pig program and see how expressing the program in terms of these high-level operations offers optimization opportunities that the system can uh exercise unilaterally without the programmer having to specify it. Okay, so in this example we're looking at traffic, uh, web, web log traffic data with sort of three columns here: the IP address, uh, the time, and the URL being accessed. Okay, and so in the first step we load the data, and here we don't need to use the USING clause to specify our own parsing function because presumably the traffic.d is in some format that Pig already natively knows how to parse, so some sort of simple delimited format. Okay, so it's expecting to find three columns, uh, and if it doesn't it'll be an error. All right. So the second command is GROUP, so we group A by IP address, and then third we say, well, for each of those grouped tuples, I just want the IP address and I want the number of uh web log entries associated with that IP address. Okay, so this is counting the number of accesses by particular IP address out there on the internet coming in. Okay, and the next step, well, we maybe in this particular task we're only interested in sort of looking at traffic that originated from two particular gateways on our local network, and so we filter for just those IP addresses with the FILTER command, and then we store the result into a file on HDFS. And so the observation here is that, you know, if you look at this carefully, you can see that as written this is somewhat inefficient. Right, we load a very large data set, we apply a grouping operation to a very large data set, we do some manipulation of those groups across the very large data set, and then we filter it down to something that's much smaller because we're only interested in these two IP addresses. Okay, so what would be nice is if we could apply the filter first. And so one thing you could do is just rewrite this program, and in this case that's probably reasonable; you probably notice that this was going on and rewrite it yourself manually, but in a more complicated program you may or may not, and this is not the only example of an optimization that can be done. Okay, and so what Pig will do is actually move the filter automatically um beforehand, before the GROUP, and use—I guess I didn't modify the program here, I modified the abstract plan; it won't actually, it won't actually produce the text here—the ASKY is done. Remember we talk about an execution plan, plan, and then it'll manipulate that, and so it moves the filter beforehand because it knows it's safe to do so. And this is—again, I keep coming back to this—but this is the, you know, the one advantage of a high-level language might be that it's easier to express your program in, but that may or may not be true in many cases; it could be actually harder to express your program in terms of these, you know, limited operators. Um, so you know, you might prefer kind of a general, you know, a Java programmer might prefer a full-width Java interface where they can just write whatever code they want. But the point is that if you can, you know, tie one arm behind your back and express your task in terms of these operations, the system can take over and make manipulations that it would be very difficult for it to do if you wrote in a lower-level language. Okay, fine.

So the other point to make here is that remember this is what we call lazy evaluation. So at when this command is is executed, that's when it makes an opport—that's when it has an opportunity to apply these optimizations. Right, so it did nothing but sort of build up your your execution plan as you were executing these commands; it did actually, it didn't actually do any work. And then finally when you say, okay, now I really want the result, you can say, aha, I've see, I see your list of sequences, or sorry, I see your sequence of commands; I'm going to do some manipulation of those to figure out the right way to execute these these commands before I produce the results. Okay, fine.

So we're not done. We now have to map this abstract execution plan down into a sequence of MapReduce jobs. And so the way it does this is it first identifies all the GROUP and CO-GROUP operators in the plan and assigns an an individual MapReduce job to each one of those operators. And then incrementally what it's going to try to do is walk forward and backward and put as much work as it can into the same MapReduce job. Okay, the GROUP command needs to be its own MapReduce job because it's going to shuffle things across the network, but filtering—I could apply, I could apply the filtering condition as I'm loading data off of disk, or as I process a tuple, I can check a condition to make sure it's from one of these IP addresses before I actually apply the group. So I might as well do that in the same MapReduce job; I don't need a whole independent MapReduce job just to do that. Further, the LOAD command is just reading things off disk; it doesn't actually do anything difficult at all. I can put that on the same MapReduce job as well. And so it ends up with one map function that's going to look something like, you know, as you process a value, it's going to say, you know, parse the data, and then it's going to say, if b.IP equals this or b.IP equals this, then emit IP, val, val.IP, val. Right, so this little program essentially gets generated by the compiler as one, as just one map function and then gets executed. And on the reduce side you can do a couple things: you can create, construct the groups, but you don't actually care about the groups cuz you're immediately going to count the results. And so it's smart enough to see that GROUP plus FOR EACH is really going to uh just produce tuples like this: IP and count, and not, you know, not IP plus some big group. And that's actually pretty significant savings because constructing these objects and sort of passing them around is is is it's pretty expensive, so you don't actually need them; you don't uh want to use them. So there's sort of two levels of optimization here: one is it moves operators around, which I like—you know, they got this algebraic flavor—and two, it compresses logical operations into single physical operations. And the overall name of the game here is is to reduce the total number of MapReduce jobs being executed because they're expensive. Okay, and then finally you can write the things out, and that can also happen in the same reduce phase. So this entire task ends up being just one MapReduce job. In other cases you may need to do sort of multiple groupings, or you may need to sort, or so on, and each one of those requires its own MapReduce job. So, for example, certain commands always require a MapReduce job, like sorting.

Okay, so what did we talk about in the last several segments? Well, we described NoSQL systems and argue that they're important for a data scientist to understand, in part because you may be using them, but also because you may be asked to weigh in on their relative strengths and weaknesses compared to other systems. And so we talked about NoSQL sort of meaning no schema and no transactions and no language, and maybe less about specifically about SQL. And overall they're kind of a reboot of data systems zeroing in on just high-throughput reads and writes. Okay, right. And so now the the design space of these large-scale data systems is sort of be more fully exploited with different permutations and combinations of particular features, but overall there's there's a clear trend back toward reintroducing schemas and transactions and languages and so on. And so we talked about the Google Spanner system as an example of this uh trend. So the NoSQL is not, you know, it's an evolving sort of concept. The main thing to realize that the entire space of possibilities in large-scale data systems is is being explored, and NoSQL represents one segment, relational databases represent another, and there's new segments emerging. So you might hear the term NewSQL, for example, which is kind of a re-architected database that does try to achieve some of these other features. Okay, fine.

Then we talked about Pig in particular as an example, not so much of a NoSQL system, but as a a analytic system that puts a layer on top of MapReduce. And we chose Pig because it has this relational algebra-like layer on top of Hadoop. And so I want to make the point that relational algebra comes up in a lot of different contexts, you know, and and in this one it's a little bit interesting because although it has a clear relational algebra flavor, it's not actually a pure relational data model; you got these sort of nested structures. And the point here is that you can kind of cherry-pick some of these concepts and techniques pioneered by databases, and you don't necessarily have to use them in the context of databases. So you don't need to sort of throw the baby out with the bath water if a database doesn't appear to be meeting your needs. And these systems are sort of doing that. So as you review different systems emerging as a data scientist, you can uh start to understand the particular set of features they offer and understand the provenance of those features and the history there and the pros and cons there in. Okay. And so Pig also—the, you know, one takeaway of it is that—has this sort of schema-on-read flavor rather than schema-on-write, meaning that you can work with in-situ data. Okay, I mentioned this a couple of times; I just wanted to point out that that's really one of the new requirements associated with maybe NoSQL as well as uh even, even SQL-like systems, is that you have to be able to work with data in its kind of native format. And the reason for that is it's just, it's just too big to transform all over the place. All [Music] right.

All right, so starting a new week, starting a new section of the course. Where are we? We've talked about what I maybe in this slide or they're calling informatics—so the management, manipulation, integration of data—and we had some emphasis on scale, and we had some emphasis on specific tools. Okay, so now we're moving into what I'll call analytics, and so we're going to talk about statistical estimation and prediction. And one of the points I want to make is that this builds on the informatics in that the things you're going to learn you can uh implement using the tools before, and we already saw a piece of this where we did sort of MapReduce, you know, matrix multiplication in various tools and so on. Okay. Okay, the other point, if you remember, we made early on was that, you know, 80% of what people think of as analytics really boils down to the ability to do sums and averages. And so we'll see a little bit of that in here where maybe, you know, understanding the problem and understanding the solution is, you know, hard or easy depending on your maybe your background, but as far as implementing it, it's it's not too bad. Okay, and then we'll move on to the visualization uh in a couple of weeks.

All right, so to get started on this, I want to call your attention to this article in 2010 from The New Yorker, with the caveat that this is far from a research article, uh, and in fact a lot of what the article has to say I'm not sure I'd recommend taking to to heart. But the point, the, you know, topic that they bring up is that, you know, the title is here is the truth wears off, and what they're exploring is this notion that statistical results in the sciences seem to have gotten weaker over time. And so John Ioannidis, you know, a researcher at the University of Illinois who does work on anti-depressants is quoted and and is discussed as talking about how a forthcoming analysis is demonstrating the efficacy of anti-depressants has gone down as much as threefold in recent decades. So this is that the effectiveness, as measured by clinical trials, of these anti-depressants has gotten a lot weaker. The article also talked about Anders Møller, who studied barn swallows and discovered that the females were more likely to mate with males that had long, symmetrical feathers. And these, this finding sort of relied on precise measurements of the symmetry, and so this was a pretty significant discovery, but over the course of the next five or six years the effect size, as discovered by himself and other researchers, shrank by 80%. Okay, a lot of the article talks about Jonathan Schooler in 1990 who made a discovery of a an effect that he called verbal overshadowing, which was counterintuitive because it showed that people who are asked to

Describe a face you know using English. That they've seen were actually less likely to remember it than those who had just seen the face, and so the, you know, talking about the face somehow overshadowed the effect of just seeing it alone. Okay. And once again, this effect seemed to get weaker over time and became increasingly difficult to measure, but including by Jonathan Schoer himself. And in fact, he's quoted as saying this: this frustrated him. Right, he was having trouble replicating it. Okay.

And then they also bring up someone who's a little less respected—well, a fair amount less respect in the scientific community—as an historical example. And is the person who actually coined the term, uh, the decline effect, which is brought up over and over again in the article. So, in the 1930s, Joseph Ryan tested individuals with these card-guessing experiments in an attempt to measure the effect of extrasensory perception, or ESP. And he's the one who actually coined that term. So he had a few students that achieved multiple streaks of very low probability—you know, many, many cards in a row that they guessed right—and so on. But there was a decline effect, and the same, uh, candidates, the same participants couldn't match their earlier performance. Okay.

And so the article touches on what is essentially the correct explanation of this effect, and it also sort of brings up the possibility of a bunch of quasi, you know, mystical, incorrect explanations of this—at least in my opinion. So I want to tell you about—I, I want to, you know, in the next couple of segments, next few segments, I want to sort of explore this as a test case for statistics and statistical estimation. And I want to use this as a vehicle to introduce the fundamental concepts of statistics and also some of the somewhat more advanced concepts of statistics, especially as they relate to Big Data. Okay. So to get started, let's talk about the background here, and then we'll come back to this specific article and explore the reasons for why this—why the truth wears off. Okay.

So this is going to be—this is not going to be a replacement for an introductory college statistics course. This is going to be a quick overview of the terminology and the concepts you should be familiar with. Okay. So we're talking about statistical inference here, and so these are methods for drawing conclusions about a general population from sample data. And there's two key methods that you can use here: hypothesis tests and, uh, confidence intervals. And we're going to bring confidence intervals again a little later on, but I'm not going to talk about them directly right now. All right. So what is hypothesis testing? Well, you're going to be comparing an experimental group to a control group, and there's always going to be a null hypothesis. And the null hypothesis is there's just no difference between these two groups. Right? The one who received the treatment in question are no different than the, uh, ones who did not—uh, you know, the new website generates no more traffic than the old website, than the control website, than the than the default, and so on. Okay. So that's the null hypothesis. The alternative hypothesis is that there is an effect—there's a statistically significant difference between the two. And so here difference is defined in terms of some test statistic, and you can—most of the examples you'll find in an introductory course or really in your course are going to be about comparing the means. Right? So the average effect in the control group was different than the average effect in the experimental group. Okay.

Now a lot of what statistics is about is actually designing the experiment to collect the data, and in a data science regime, in a big data regime, we're actually less—frequently in the in in a in a position to design the experiment in the first place. A lot of times we're dealing with data that we did not necessarily collect. Okay. So that's maybe one difference between classical statistics and, uh, the way I want to present this material for purposes of data science. Okay. That being said, it's important to understand that careful experimental design is really the most important thing there is in all this work. Right? The the the, uh, analysis techniques are second fiddle to the proper collection of data. Okay. So this includes things like randomized trials, blinded and double-blinded. So you know what is blinded? It means that the participants themselves don't know which group they're in, and that's pretty much non-negotiable. Right? You can't tell people that they're getting a placebo drug versus the the actual drug, or or they they'll, you know, the they'll report their symptoms differently as an effect. Randomized is also would be non-negotiable except the fact that it's difficult to achieve in practice in some cases. So randomized would mean, uh, we we draw a sample through some method, and then we assign them to the groups—to the control group and the experimental group—with no process whatsoever. Right? It's just purely random. Okay.

So this framework, expressed in just these sort of few bullets at a high level, is unbelievably powerful. Right? It's completely universal to data analysis, so it's really important to sort of internalize these points, and we'll go into some more detail on some of the, uh, other aspects that aren't included in this slide. So some examples you can dream up: you know, that the measuring the effect of a new ad placement on your website compared to the control group of the existing placement; uh, measuring the effect of a treatment against a sugar pill or the best existing treatment. Okay. And everything else you might imagine. So to summarize hypothesis testing, you can organize this terminology into this grid here where there's two possibilities for this true state of the world: one is that the null hypothesis is true—there is no difference between the control group and the experimental group—and the other is that the null hypothesis is false—that there is an effect that you're measuring. Okay. And so then there's also two possibilities for the outcome of your statistical test. In one case, you do not reject the null hypothesis—right, you find no evidence that there's any difference between the groups—and the other is that you reject the null hypothesis—you do find evidence that there's a difference between the groups. Okay. So if the null hypothesis is true—there is no difference—but you detect a difference, that's a type one error. And the, uh, um, rate at which that happens you can—we we'll refer to as Alpha, and that might come up at times as we may as we have the discussion. Right? And if you make the correct decision, then the probability of that is 1 minus Alpha when the null hypothesis is true. When the null hypothesis is false and you fail to reject it—right, there is an effect and you fail to measure it—that's a type two error, and that's Beta. And when you do reject the null hypothesis when it's false—right, you detect an effect when there is an effect to detect—that's 1 minus Beta. And this is called the the power of the test—the statistical power. [Music]

Okay. So in the last slide, we said that comparing two groups—the control group of the experimental group—is the name of the game, and we said that we're trying to take some test statistic and to measure the difference between those two groups. But how different is different enough to be significant? Okay. So in other words, how do we know that the difference that we saw in the experiment is not attributable to just chance? Well, the answer is we don't, but we can calculate the probability that that that it's attributable to chance, and that's what the P value is. Okay. So the P value is the following: if you would repeat the experiment over and over and over again at the same sample size, what percentage of the time would you see results that were at least as extreme as the ones you got this experiment? And this is all assuming the null hypothesis is true. So let me say that again: assuming that there is no difference between the groups—right, the control group really is the same population as the experimental group—right, the treatment has no effect. If I were to do the same experiment over and over again, what percentage of the time would I would I see a see a difference in the treatment group anyway, just by chance? Okay. And that's what the P value is. Fine. So more terminology: you know, you you need to think about two-sided versus one-sided. So two-sided is if we're measuring something in terms of the absolute value. Right? So the P value is two times the probability that X is greater than the absolute value of the measured value. And if the test is one-sided, it's either greater than or less than. And here the notation that we're using is Mu, which is the mean, and mu—mu sub z—which is the, uh, mean of the population under the null hypothesis. So this screenshot is taken from a nice applet that you can find online, uh, and play with here. But here, if if the null hypothesis is that the mean is 325 and we're doing a, uh, two-sided test where mu is not equal to 325—we're saying it must be something different than that, either higher or lower—right, uh, and the sample size is 10 and the observed sample mean is 328, then when you click the show P button on the applet, what you get is it computes the P value for you and shows this colored region. And so these colored regions—and so these colored regions—the area of that curve is the P value. Okay. So that's the probability that it's at least as extreme as the measured value. Okay. And if you get, you know, here the only change I've made is that the sample mean was 329 instead of 328, which means it's even less likely you would see this by chance, and so the area under those curves is even smaller, and you notice the P value changed—the P value went from 0.574 to 0.0114. Okay. So in order to make some sort of a decision—you know, did this treatment work? Right? Do we invest in this treatment? Do we move on to the next stage of trials?—we need some sort of a threshold, some sort of a cutoff for the P value. So what is that cutoff? Well, it's 0.05. Why? No good reason—it makes the math work out. Okay. So this is a one in 20 chance. If you can show it's more rare than a one in 20 chance, then that's deemed to be good enough. Okay. This is the subject of a lot of controversy, depending on what circles you—what sort of literature you're reading—and we'll talk a little bit more about this in in a few segments, but that's all I'm going to say about it right now. So 0.05 is what people are looking for. All right.

So now that you're armed with a little bit of basic terminology, let's go back to this first slide, uh, from this New York article. And so the question that we raised was: what accounts for this truth wearing off effect? How can we explain what's going on? Okay. So one reason is publication bias. All right. So let me read you a couple of quotes from this article about publication bias. So in the last few years, several meta-analyses—and we'll talk about what a meta-analysis is in a little bit—have reappraised the efficacy and safety of antidepressants, and included the therapeutic value of these drugs may have been significantly overestimated. Okay. Although public—and there's other examples in this article as well. Okay. So go back and review the literature and find out that things have been overstated. Why? So although publication bias has been documented in the literature for decades, and its origins and consequences are debated extensively, there is evidence suggesting that this bias is increasing. All right. So I haven't told you what publication bias is yet, but you may be familiar with the concept, and these are some of the effects. So a case in point in the field of biological research and autism spectrum disorder, which suggests that in some areas negative results are completely absent. All right. So what does that mean? That means that you're only publishing papers that show significant positive gains. Right? If we try several treatments and none of them work except for one—we try 20 treatments and only one works—how many papers do we publish? One, not 20. Okay. So how is this a problem? Okay. So do we have an explanation for this decline effect with publication bias? So how does this actually work? Well, let's make a plot where this study size is on the x-axis, and notice this is log scale. Right? So this is 10, and this is 100, and this is 1,000, and so on. Right? Well, study size meaning the number of patients, say—say that were that are involved in the study. So the bigger the study size, uh, the more statistical power you have, and we'll define what statistical power means precisely in a bit, but the better you are able to determine actual effects. Right? And the assumption here is perhaps that, you know, as time goes on and you see some results, you are able to—you or other researchers are able to garner more money, more funding to do larger and larger studies. Right? So this is maybe phase one, phase two, phase three trials of some new drug—they get bigger and bigger and bigger sets of patients as you get more more momentum behind it. And this this data is not real—this data is simulated—but imagine you see this kind of decline effect where the results—okay, well, the sorry, the y-axis—the y-axis is the effect size, and we'll talk about what the effect size is precisely in a little while, but this is the degree of positive outcome, let's say. Right? Let's say negative is bad and positive is good. So this is, you know, the number of smokers you were able to convince to quit with some intervention counseling method, or the, you know, a number of white blood cells, uh, increased as a result of some treatment, or so on. Okay. Positive is good. Well, this decline effect—let's imagine—shows this sort of a pattern, right? Where the early studies with just—with just, uh, 10 participants is up here, and as the study went up, it sort of got worse and worse and worse. So this is where—this is the effect that we see. How do we explain this? Well, this is directly explainable—this kind of an effect would be directly explainable just by publication bias. Right? Imagine that every dot now is a test that was done by some group somewhere for this phenomenon. What you'd expect is this kind of funnel shape where where the studies get more and more accurate as you get larger and larger and larger. Right? And they will—with the stud—this is—this is you can't get around this. Right? As the study size goes up, you do have more statistical power—you're able to better discriminate real effects from false effects—and so on. But you'll notice that the actual effect that it's regressing to here is 0.0—there is no effect—and yet, of course, you're going to get some just due to variability out here. And so if you only report the positive ones, you'll end up with this mysterious decline effect. Okay. [Music]

Okay. So we talked about publication bias, and on the y-axis of that plot we had effect size. So what is effect size? Well, it—you know, if your P value was just the probability of in repeated experiments getting, uh, an effect of at least that size or more extreme. Okay. And so all it tells you is yes or no whether it was significant according to some threshold—it doesn't tell you how, you know, significant it was or how how how important it was. Okay. And that's what effect size tries to capture. So the effect size in a, uh, situation where you're comparing the means of an experimental group and control group, then the effect size is the mean of the experimental group minus the mean of the control group divided by the standard deviation. And so this tells you not just significant but how significant. And this measure is used prolifically in meta-analysis to combine results from multiple studies, and it's useful to help standardize, uh, across studies with different parameters—different different sample sizes in particular, for example. Okay. And so in general, you got to be careful with this because averaging results from different experiments can produce nonsense if if you sort of violate the assumptions under which the experiments were conducted, but you know it can be done. Okay. And so another caveat here is that there's other definitions of effect size exist—there's odds ratio and correlation coefficient—but we're just going to talk about, uh, this one. Okay. And so there's an argument here that the effect size should always be reported along with the P value, even though this is very rarely done. And that argument is delivered by Robert Coe in this paper presented at the annual conference of the British Educational Research Association in 2002, uh, that's cited here at the bottom of the slide. Okay.

So a little more precisely, the effect size is the standardized mean difference, where the group one—you know, the mean of group one minus the mean of group two—divided by we said the standard deviation, and here I'm writing this as the standard deviation sub pooled. Okay. And there's lots of ways to compute a value for this notion of pooled—one simple way is just to take the standard deviation of the control group, and you know one by one argument here: hey, the variation is supposed to be the same because the sample, uh, you know, your samp—the two groups are drawn from the same population. Okay. Uh, another way is to compute, you know, the actual pooled standard deviation, which is an expression, um, that looks like this. And so we're not going to go into much more detail than that, but just to point out that the overall notion is pretty simple and that it's not unreasonable to use a straightforward definition of the standard deviation. Okay. So what's a what's a big effect size? Well, because it is standardized, you could you can actually reason about what might be big and what might be small. So this is again one of these cases where it's sort of made up on the fly, but you can—one heuristic by, um, Jacob Cohen is a small effect size is 0.2, a medium effect size is 0.5, and a large effect size is 0.8. So for—you know, remember this is dividing by the standard deviation—so this is sort of for every bit of difference in mean, how much variance are you accounting for? Okay.

And then finally, I'm not going to talk too much detail about confidence intervals, but I do want to mention that the confidence interval of the effect size just to give you the intuition for this. So an advantage here is that these are maybe easier to interpret in terms of actual decision-making. So what does a 95% confidence interval of the effect size mean? Well, it means if you repeated the experiment 100 times, we expect that the that interval would include, uh, this particular effect size measured in this experiment 95 out of 100 times. A corollary of this is that if that interval incl—if the 95% cons—include 0.0, that's equivalent to saying that the that the result is not statistically significant—that means that 98% of the time that interval would include no effect whatsoever. Okay. And equivalently, if it if that interval does not include 0.0, then it is statistically significant. Fine. So that's some more terminology here. The other notion we mentioned in talking about publication bias was the idea of a meta-analysis. Okay. So this is looking back over previous studies and combining their results. And so in 1978, Glass sort of statistically aggregated the findings of, uh, 375 psychotherapy studies to disprove a claim that psychotherapy was useless. And this was the coining of the term meta-analysis. And this built on earlier ideas from other statisticians, including Fisher, who has this quote: you know, "When a number of quite independent tests of significance have been made, it sometimes happens that although few or none can be claimed individually as significant, the aggregate gives the impression that the probabilities on the whole would be less likely to have been attained by chance." Okay. So this is individually they look weak, but we can aggregate them to get a more powerful, uh, result. Okay. And so the reason I want to bring this up—this idea of meta-analysis—that becomes even more important in the context of data science because you'll often be working with data that you did not yourself collect. And so, uh, thinking of it as a meta-analysis experiment is potentially useful. And then another point is, you know, that Big Data may have become big because it was combined from multiple different sources. And so understanding when this is okay to do and when this isn't, uh, is important. So how do we do this meta-analysis? Well, you—it's pretty simple—you just want to take a weighted average of the, uh, independent studies. Okay. And you want to—so how do you want to define the weights? Well, you can define…

It's different ways, but you want to give the weight to the more precise studies when possible, the ones that have more power. So a very simple method is just weight by the sample size, right? And so this expression here is the uh number in your group. So the weight for for a group for a study I is the number of samples in study I over the sum of all the samples, the total sample size.

More sophisticated way is to use the inverse variance weight, which is one over uh the standard error squared. And I'm not going to give you the formula for standard error; you can look it up. But there's also but there's lots of variant here. The main idea is to understand why it's called infers variant variance is that if the variance is very very high on a a study, you want to give that lower weight, right? That means it wasn't a very precise study, and this could be because the sample size was low or it could be for other reasons. Okay. And the standard error is is one common method of of associating with the variance in this particular case, but again it's important to understand the intuition rather than just memorizing the formulas. Okay.

And then again, as usual, there's a caveat here. This is this is all for a fixed effect model. It assumes that every individual study is measuring the same true effect, and there's random effects models that help account for the fact when they may not be uh, and we're not going to talk about random effect models. Okay.

So finally, one more term that we talked that was brought up in the context of publication bias was well, sorry, the didn't bring up the term, but one more effect that you saw in the plot was this funnel plot. If you remember the funnel plot was high variance on one side and it went to lower variance on the other, and so the general term for this that I just wanted to introduce you to is called heteroscedasticity. Okay. And so this is when the variance itself uh is not constant. All right. So here as an example, the variance is high, the variance is high over here and low in the middle and high again over here. Now this is not necessarily a problem; there are ways to correct for this, but it's not necessarily a problem because the uh estimates that you'll generate are still unbiased. Okay. But it can increase overall error estimates leading to a reduction in statistical power, right? So you end up with this really high error numbers because all these guys count against you, right? Even though you're actually doing a pretty good job in predictions. So I should say how this how this plot was generated. This was uh again simulated data where you know intentionally sort of varied the variance along the along the x-axis. Okay. So chose chose some X values and then and then sampled y-values According to some distribution that varies in this way. And here I just took the exact same X values but repeated the sampling of the y-values many many many times, so it gave me this clearer spread, but you can see these these solid bars are because the same X values were used across all the experiments. Okay. And the point here is that drawing the regression line over and over again uh it didn't change all that much. Okay. Right, we didn't get anything that looked like this, for example. Fine. So again, if you the problem here is that you might increase the air and you might lose statistical power because it it overlooks a real effect. [Music]

Okay. So what's a second reason for this decline effect, for the truth wearing off? Well, another one is just people make mistakes, and in some cases there's instances of Fraud. And so there's some evidence here that these kinds of things are going up as well uh as measured, you know, one way to measure this is by the number of paper retractions, and the number of retractions has gone up fairly significantly as Nordon pointed out in 20 in an article in Nature. So from the period of time 2001 to 2011, there's been a tfold increase in number of paper attractions but only a 1.44 fold increase in papers themselves. Okay. And so this plot is from two different repositories, PubMed and web of science, neither one of which can include computer science papers by the way, uh but you can see this gone up pretty significantly. Fine. So not going to dive into too much detail into this phenomenon, but I do want to give you one statistical tool that is sometimes used uh to detect fraud, and that's Benford's law. Okay.

So if you're not familiar with Benford's law, it's a fun one to be familiar with. So this law predicts the distribution of the first digit of data. Okay. And if you think about it without think if you think about it without thinking too deeply, you might intuitively think that this would be fairly uniform. If you have random data, you might see an equal number of eights and an equal number of threes, an equal number of twos and so on. But it turns out that the distribution is not random in in some circumstances, in many circumstances, well it's not it's not even I should say it is random; it's just not even. The distribution looks more like this: you will get more ones in the first position then you will twos, and more twos than threes, and so on, and so up to 30% of the numbers you measure are ones. So this should you know blow your mind a little bit. Okay.

So some examples of this before we explain what's going on uh taken from there's a nice website, testingbfrlaw.com, where they pull real data in and and show the plots. This is the number of Twitter users by their F by the number of followers they have, sorry, not the number of Twitter us Twitter users by the number of followers they have. Okay. All right. So the the the list of numbers is just the number of followers the number of Twitter uses to have whose number of followers begins with a digit one is 32.62%, if you can see that, and the Red Dot is the prediction made by Benford's law, so not too bad. The number of instances with that have the two is leading digit is 16.66%, and there's the red line Red Dot predicted by B's law and so on, so not too not too bad. The distance of stars from Earth in light years follows a similar pattern. This is remarkably close to Benford's law prediction. Government spending in the UK between the period of time May through September 2010, again remarkable prediction. Now you might imagine there's some selection bias on this particular website, and I can't guarantee that there's not, but you know with with some reading plus a little bit of trust that I hopefully have built up, I I hope to convince you that this is not uh uh fully explainable by this website choosing particular data sets for which for which this is true. Okay. Uh Google Books, the number of unique one-grams, and we talked about one-grams several a couple weeks ago, terms essentially what one-grams are. Okay, again pretty good prediction.

So before we say before we give the intuition for this, if there the intuition is a little bit tricky, but before we attempt to give the intuition for this, uh you can use it to detect fraud. And so this was attempted in or this was an experiment was done by Degman in 2007 to see if could be used for detecting scientific fraud. And so what he found was the first and second digits of published statistical estimates were approximately Benford distributed in real studies. Okay. Or at the very least they had kind of a monotonically decreasing distribution, so ones more more ones than twos and more twos and threes and so on, if not exactly Benford's law. And then what he did was asked subjects to manufacture regression coefficients, you know, basically fitting a line manually, and found that the first digits were actually hard to detect as anomalous, but that the second and third digits deviated from expected distributions. And so this distribution that I gave you in in the last few slides and and that I gave you in the um actually I guess I didn't give you the uh the actual formula here. Okay. So the distribution that we be discussing is only for the first digit, and the skew in that distribution actually gets suppressed as you go to the second, third digits, but Benford's law can also be used to express different yet still measurable distributions of second and third digits. And so there the second and third digits deviated significantly. And so the conclusion was this is it is potentially potentially useful as a fraud detection tool in scientific data, and act there are instances where Benford's law has been admissible as evidence in court in cases of Fraud, and it's been used um by reporters and so forth to uh argue for evidence of fraud in cases of voting, election, and other kinds of accounting data on the sort of global scene. Okay.

So what's going on here? Well, one way to think about the intuition here is imagine a sequence of cards labeled with a particular number 1, 2, 3, 4, 5 all the way up to you know 999,999. Okay. And so put them one by one in a hat in order, and at each every time you throw a card in measure the probability that a random selection from the hat would produce a card where the first digit is one. Sorry, this isn't very well said; it's not it's not drawing the number one, drawing a card where the first digit is one. Okay. So what does that probability look like? Well, this figure is a little bit misleading because the x-axis is on the log scale, but if you just look at the heights, what's going on here is on the y-axis of the probability of drawing a particular digit, the blue line is associated with the digit one, the green line is a digit two and so on, and this was generated via a simulation where you you know I really did select random numbers from a distribution and then I really did order them in the manner described in the previous slide and put one in and then measure the probability of drawing it value with a number one or where the first digit is one. Okay. And so if you think about this, the numbers you know what what's happened here, this is where one and this is 10 and this is 100 and so on. Well, as soon as I put put a one in the chance of drawing a card with a one in the front is 100%. When I put a two in, it's now 50%. When I put a three in, it's now 33%, and so on. But then as soon as I get to 10, it goes back up to a higher percentage again, and it stays there 10, 10, 11, 12, 13, 14 so on. And then as soon as I get to 20, it drops down a little bit, and so that's why it's climbing here is through the tens, and then it starts dropping again sharply. Okay. And so the point here is that under this model, values where the first digit is one always are in the Hat already by the time you get to the twos, and the twos are always there before you get to the threes, and the threes are always there, the fours and so on, and so you end up with these height these Peaks are led by the ones, and the area under this curve, although remember this is a log plot so the area is not quite right, uh represents the probability of of drawing this, and so the probability does actually get higher. Okay. And there's a few different other models you can you can find when you if you read up on this, and I encourage you to uh there's other ways to sort of think about the probability here, and there is actually closed form expression for Benford's law as as well. Okay.

One of the limitations here, it's not always true, and one of the key or the key uh situation in which it's applicable is the data set has to span many many order well many many orders of magnitude, right? It can't be values between I think about if you have values between 50 and 90 and you select those randomly, well you're not going to get any numbers with the uh first digit is one. Okay. And similarly, if you do from one to 100, well you this you have this effect a little bit but not universally. So you want to span a lot of orders of magnitude, and so uh this is sort of illustrated by this plot here is that the red areas are represent the probability of selecting something where the first digit is one, and the blue areas are where the first digit is eight. Okay. And so as long as you span enough orders of magnitude, you get much more area where the where the first digit is one. Okay. But if you take a narrow case, well then the probability is more defined by the distribution itself, and there's not enough chance for this area under the curve under the digits one to to to get big. Okay. So fine. So I just want to introduce you to that law, mention that it can be used to detect fraud, and then connect the fraud plus chance of mistakes back to this original context we're in of trying to understand the weakness of of of statistical results, the perceived increasing weakness of statistical [Music] results. Okay.

So if third potential explanation of this decline effect is exceedingly simple but exceedingly common, and it's maybe the most important one to uh learn to apply in your own work when you're when you're doing statistical analysis. Okay. And so this is the idea of multiple hypothesis testing. So the problem here is that if you perform experiments over and over and over again, you're bound to find something, right? That's sort of the definition in fact, right? You if you keep keep rolling Dice long enough, you know you can't just keep rolling Dice and then yell YSI, right? You get one shot at it, and the same is true with these uh experimental design. Okay. And so this is related to the publication bias problem in that you're only showing your positive results, but it's a little bit different because here you're talking about the same sample and you're testing different hypotheses over the same data. And so in these situations, either you shouldn't do it at all or or if you do have to do it for various reasons, you need to adjust the significance level down. That means you need to not settle for 0.05 as the threshold; you need to do something much much lower. Okay.

To understand why, you know, consider something pretty basic over completely random data, and we we set the Threshold at 0.05, this Alpha 0.05. So the probability of detecting effect where there is none is 0.05, then the probability of detecting detecting an effect when it exists is 1-us Alpha, then the probability of detecting an effect when it exists on every experiment you do out of K experiments is 1 - Alpha * 1 - Alpha * 1 - Alpha * 1 - Alpha, assuming that they're independent, right? We're it's okay to multiply probabilities together if those probabilities are independent. Okay. Then the probability of finally the probability of detecting an effect where there is none on at least one experiment is one minus that total, right? So first we build up the probability of being perfect, and then one minus that is the probability of not being perfect if making at least one mistake. Okay. So if you plot these numbers, what you get is on the x-axis here is the number of tests, and the y-axis is the probability of at least one spous finding, right, making at least one mistake, well it up like this. So if as you get up to sort of 50 hypothesis tests, you know you're up at the 90% chance of at least one spous finding. Okay. And so controlling this is known as controlling the familywise error rate. This is the familywise error rate of at least one mistake. So this is a pretty stringent. So what do we do about this multiple testing problem? How do we control the familywise error rate? Well, one solution is the Bonferroni correction, which is just to divide by the number of hypotheses. Okay. So if your significance level is Alpha 0.05 and you do 20 experiments, 20 you're testing 20 hypotheses, you just divide 0.05 by 20. So another correction is the Šidák correction, which has this extra condition where the tests are need to be independent. So even though we we talked about in the last slide that uh in order to make that plot we were assuming that they were independent, but the Bonferroni correction in general does not need to assume that. Okay. So if you're doing hypothesis tests that are related to each other, you can still do the Bonferroni correction. However, to derive this Šidák correction, we're going to rely on the fact that we're going to multiply the probabilities together. Whenever you see probabilities being multiplied together, that means that you're assuming that they're independent. Okay. So let's see if we can build this up. So here we're going to derive the individual test the corrected significance level from from the overall significance level. So we're going to set the overall significance level Alpha equal to the probability that at least one of the tests is significant. All right. So at least one is significant. Well, what's that? That's one minus the probability that none of them are significant, and the probability that none of them are significant assuming Independence is the probability that the first one is not significant times the probability the second one isn't sign is not significant and so on. So that's 1 - Alpha C raised to the K experiments, right? 1 - Alpha C * 1 - Alpha C * 1 - Alpha C and so on, and that's what this expression says. So fine. So now we just solve for Alpha C, and we get this expression 1 - 1-us Alpha raised to the 1 over K ra raised to the K Ro the K root of 1 - Alpha. Okay. Okay.

Showing the same plot from before but now zooming the scale in down around 0.05 where the original uh significance level was, you can see the difference between these two Corrections. So the Šidák correction is more conservative than the Bonferroni one uh correction. So Bonferroni evens it out across so instead of instead of increasing the likelihood of making a mistake quickly, which is what the previous plot shows, this is zooming in at 0.05 and showing that the Bonferroni makes it constant across regardless how many tests, which makes sense because you're just dividing it by the number of tests you've done. Okay. And the Šidák correction uh is even more conservative. All right. So that's what to remember. Both of these are considered to be more conservative than is perhaps necessary; you lose too you give up too much statistical power when you use these, and in fact any correction for the it goes back to the actual definition of familywise error rate is is considered to be too conservative. So another way of controlling for multiple hypothesis tests that is less conservative is by considering the false Discovery rate. Okay. And so the false Discovery rate you can understand by going back to our grid and labeling it a slightly different way. Okay. So here the excuse me the pneumonic here is that the total let's see T and f stand for true and false, and d and n stand for Discovery non-discovery. So false Discovery is FD, true Discovery is TD, true non-discovery is TN, and false non-discovery is FN. Okay. With this notation, the false Discovery rate FDR, which is sometimes called Q, is the number of false discoveries over the total number of discoveries. And so here in this notation, by the way, D you know is equal to FD plus TD, so these are counts, these are the number of uh of you know true relationships and false relationships and so on. Okay. So this is the rate you're trying to control for. So the Bonferroni correction and other and other familywise error rate Corrections tend to wipe out evidence of the most interesting effects; we say they suffer from low power. So the false Discovery rate controls offer a way to increase power while maintaining still some principle bound on error. Okay. And so it's more intuitively it's based on the assessment that you know four false discoveries out of 10, you know, if you reject the null hypothesis 10 times, you make you make five just quote quote, you know, discoveries, four having four of those be false is really bad, but it's you know much worse than making 20 false discoveries out of uh 100. The idea here is that you know finding true effects is a good thing, and so even though you're going to make some mistakes, if you can the more the more you find uh the more sort of value you've added. So how can you control the false Discovery rate? Well, the Benjamini-Hochberg procedure gives you a way to do this. And so here's how it works: you compute the P value of your hypotheses, and then you sort them in ascending order such that the ones with the lowest p

Value which are the most likely hypotheses, right, the ones that are best supported by the evidence come first. Okay? And then you apply this condition where the P value is subject to a more stringent condition than just Alpha. Remember, Alpha is your 0.05, your cut off. And what we're trying to do is correct for the multiple hypothesis testing, so we want a much more stringent uh Alpha. And so that more stringent Alpha is this ratio I over M. And so I is just the rank order of the hypothesis you're testing, and M is your total number of hypotheses that you're testing, number of hypotheses. All right.

The procedure says, well, find the highest I for which this condition holds, and then reject the null hypothesis for all I lower than that; accept everything up until that point. Okay. And so here's what it might look like with 50, the first and it's and 0.05. I suppose I should have put that. So the first, your first hypothesis has to, the first hypothesis is compared with a uh pretty stringent condition, zero, you know, one in one in a thousand. And the second one is double that, and the third one is triple that, and so on all the way up to the 50th one, which would be 50 over 50, which is just your original Alpha, 0.05. Okay, so this is a much tighter condition. And so what they're able to prove is that the false, under these conditions, you know, following this procedure, the false discovery rate is less than T over M times Alpha, where if you remember T was the total number of cases where the null hypothesis is true.

Okay, so here's what it looks like graphically. The little X's are me, are above this line, and the dots are below this line. And the x-axis is rank order, and these are all your 50 hypotheses sorted in increasing P value, and the line represents that threshold condition, and it slopes up with rank order as we'd expect. And so here we'd say we'd find the highest I for which this is this condition holds and accept everything lower than this. And here we had a, you know, pretty good run; we accepted sort of 30 out of 50 hypotheses. And notice that these actually are above the line, but we would still accept them. [Music] Okay. Okay.

So where are we now? So we motivated the discussion of statistical inference and estimation by bringing up this so-called decline effect, where the effect size of scientific results seems to be going down over time, and reproducibility is suffering. And so we gave some reasons for this: publication bias, you know, mistakes and fraud, and this multiple hypothesis testing problem. And so we use these motivations, these scenarios, to bring up various topics and techniques. So we talked a little bit about basic statistical inference where I just give you an overview, and that's it. Uh, we talked about effect size; we brought up the specific term heteroscedasticity for fraud detection; we brought up Benford's Law; and then with multiple hypothesis testing, which is perhaps the most important part of the discussion, we talked about the familywise error rate and the false discovery rate and gave correction procedures for both of these. Okay.

And so this hopefully was a tour of not just some basic concepts but also some, if not advanced, uh, at least things that don't necessarily come up in a uh a, you know, stats 101 course, but I think it's pretty important for a data scientist to understand. In fact, as a data scientist, there's a view among statisticians that these topics are not very well understood, and in fact, they'll point to typical machine learning classes where understanding the population, understanding the various biases, understanding how to correct for for the problems that can arise is not taught at all, and it's more of a of a, you know, blind application of algorithms. And so I think it's pretty important to sort of go over this choice of topics now.

So what about Big Data? What changes? Well, so Brad Efron, who's a world-renowned statistician, you know, describes it this way: says classical statistics was fashioned for small problems, a few hundred data points at most, and just a few parameters. And the bottom line is that we've entered into an era of massive scientific data collection with a demand for answers to large-scale inference problems that lie beyond the scope of classical statistics. And so suggest that something is changing in the area of Big Data. Now what can go wrong here? Well, as we talked about, you can find spurious relationships in Big Data. And so this is a picture that I got from a colleague recently that was emailed to him, which is a plot that someone took the time to make, may or may not have been as a joke, but as you can see here, it says Internet Explorer versus the murder rate. Okay. And so this is the murders in the US in blue, along with the market share of Internet Explorer in the green, and the, you know, corresponding discussion that went along with this plot, uh, you know, was was somewhat amusing, right, talking about various theories for why the murder rate might be going up as Internet Explorer market share, or murder rate goes down as as Internet Explorer market share also goes down. But the point here is that without some common sense or without the the application of understanding the scenario of the problem, you can make, you know, discoveries of this form. Okay. All right.

And so other examples that have been talked about in the literature, again brought up a as as, you know, bad examples, uh, you know, the number of police officers and the number of crimes. So why might these two things be correlated? You know, maybe police officers cause crimes? Well, no, probably because there's in in densely populated areas there are both more police officers and there are and there are more crimes. By the way, just to point out again, you know, these these authors here, um, are not authors that claim made these claims; these are authors that brought up the mistake. Okay. Amount of ice cream sold and deaths by drownings. Why would these things be correlated? Well, there's a seasonality, right? In the summertime you sell more ice cream, and more people go swimming. And then one is, you know, sightings and population increase used as, you know, evidence that stores do indeed bring newborns to families. Well, again, in more densely populated areas there's more people to actually see the STS, and so you get an increase in sightings. Okay. So these kind of uh procedures to remove bias and these procedures to understand the population you're sampling from uh and to understand the possibility of spurious correlations, these things are taught in statistics programs but are not typically taught in machine learning classes.

Okay. So what does it have to do with Big Data? Well, it might be a view that there's a, you know, the curse of Big Data, as Vincent Granville put it, is the fact that when you search for patterns in very, very large data sets with billions or trillions of data points and thousands of metrics, you are bound to identify coincidences that have no predictive power. And so the example he gives is to consider stock prices for some large number of companies over a one-month period, and then you check for correlations in all pairs, uh, and actually doesn't stop there because that would be over the exact same one-month period, but you might want to account for lags, you know, perhaps the stock price of Google a few days later affects the stock price of smaller companies that depend on Google. Okay. And so now you're not just comparing every every uh, you know, 500 squared; you're not just checking the pairwise correlation of these time series, but you're also checking the pairwise correlation among the slightly offset ones. Okay. And so these are this cross-correlation procedures. So very basic time series analysis is is just to measure the correlation, and I just want to throw the formulas up here where the covariance of two uh data sets is measured this way. All right. So you take the data point XI and subtract the mean of X and multiply that by Yi minus the mean of Y and add all that up, and that's the covariance. And then you divide the covariance by the standard deviation of each data set multiplied by each other, and so this gives you a correlation. Okay.

So what is this experiment look like? Well, I generated this plot by running random walks for stock prices that start at $10; they all start at the same [Music] same point. And at each step, which is an hour of simulated time, uh, draw a sample from a normal distribution where the mean is the current stock price and the uh standard deviation is 1% of that current stock price. Okay. And this is not especially defensible, but you can see just sort of visually that it does generate stock price-looking things, and you do get some variance here. All right. So clearly this is this is random. This plot uh shows the number of correlations at a level of 0.9, right, that's a pretty strong correlation, as a function of the number of stock prices tracked. So as I went up from 10 to 100, I didn't go all the way up to 500, which is what uh Vincent Granville described in the in the thought experiment; this is the number of spurious correlations I I you find. Okay. And this is also not doing the lagged cross-correlation, right? This is just directly computed the correlation of these two uh time series across this month, and that's a pretty long period too, across a month. So what's the point? Well, Big Data gives more opportunities for spurious findings. Okay. Now it's not all bad news. So how is Big Data different? Well, there's a notion of big p versus big N, where big p is sort of the number of columns and big n is the number of rows. And in this experiment we just did with the time series, this was sort of a big p scenario; we looked at more, you know, an increasing number of companies, and then we looked at all possible correlations between them, so this was growing sort of quadratically. Okay.

So the thing about Big Data though is that the marginal cost of increasing the number of records is essentially zero; it's gotten cheaper and cheaper and cheaper to collect data. Okay, great. Now that's very, very powerful, right? We want to, increasing the number of records adds statistical power and helps us sort of, you know, get lower and lower P values, but it also amplifies bias. If you're collecting the wrong data, if you're looking at the wrong populations, uh, you're going to make, you know, so-called discoveries that are simply false. And so, for example, if you log all the clicks to your website, you have a very, very large data set, and you can very precisely model user behavior, but that would only model your current users when your whole, you know, perhaps the whole point of modeling uh user behaviors is to try to attract new customers. Well, for example, if you have early adopters and your current user base is early adopters, you're only going to be modeling their behavior; you haven't actually sampled the population at large. You know, another example is mobile data, and this comes up in polling for say the presidential election, uh, you know, you're you're only sampling people that have cell phones, and this may or may not be the same population you want you want to be sampling. Okay. So this may ignore lower-income groups or uh different age groups. Okay. Okay. You need to be careful at multiple hypothesis tests as well as we pointed out. So there's a fantastic comic from XKCD that makes this point very, very clear, uh, where they sort of demonstrate that green jelly beans cause acne, right? And the um story here is that there's 20 different colors of jelly beans, and for a P value of 0.05 we do 20 experiments, and sure enough we find one one of the colors indeed causes acne, but that would be expected purely by chance. And so I encourage you to look up that comic. And then the other the other comment I'll make that we we'll probably come back to is Nassim Taleb's Black Swan events. So this is things that are sort of inherently unpredictable, or the distribution of them does not follow a normal distribution, sort of a bell curve distribution where the uh tails of the bell curve mean that extreme values become exponentially more rare; that's the sort of definition of the normal distribution, but in some cases extreme values are not exponentially less common; they they they happen. Okay. And so the example that he uses in this case is that, you know, the if the if a turkey was to model your behavior, it would get increasingly more confident that uh that you mean it it no harm and you you know goodwill, right? Every day you come and feed the turkey, and every day you take care of it, and you look out for its wellbeing, but then on the, you know, day before Thanksgiving it's gets slaughtered, perhaps. Okay. And so that was Taleb's argument for Black Swan, and Black Swan itself refers to the fact that people didn't believe black swans existed and then found out that they did, and so it was an unexpected event. Okay. Fine. And we'll talk more about that in some detail. [Music]

Okay. So so far we've been discussing statistical inference from a particular perspective, which is the frequentist perspective. And so frequentists are concerned with the probability of seeing a particular data sample given the null hypothesis. Okay, that's what the P value gives you. But there's another perspective to statistics called the Bayesian approach, which is concerned with the probability of having a certain outcome given the data that we've already seen. Okay. And so I want to talk a little bit about Bayesian approaches and give an example of their uh power.

What are the differences here? Well, you can think about the differences in terms of what is fixed. So the frequentist perspective is that data are repeatable random samples, right? You're always allowed to go do another experiment the same way, and in fact you need to, at least virtually, to reason about uh the probabilities that get produced by the methods. Okay. So there is some sort of frequency you can reason about; frequency of achieving a certain outcome. Okay. And the underlying parameters of the population remain constant during this repeatable process, right? Your your the population stays fixed, and you run experiments to determine like, you know, likelihoods. Okay. Meanwhile, with a Bayesian approach, the data observed from a realized sample and the parameters of the population are unknown but can be described probabilistically, right? So they're not sort of fixed values. However, the data are fixed, right? You don't you don't think about going back and sampling more data; you just have the observations you have. Okay. And so the Bayesian approach is 100% concerned with the application of Bayes' rule, which is this. Okay. So this, what Thomas Bayes did was relate these conditional probabilities with the prior beliefs. Okay. So it allows you to take your belief about the probabilities of certain events happening and update them when you more data is collected. Okay. And so here's what it says: says the probability of event A happening given that event B has already happened is equal to the probability of B happening given that A has already happened multiplied by the probability of A happening across the board divided by the probability of B happening across the board. And if that's not clear, that's okay; we're going to go into more detail here. So for right now though, recognize that the key benefit here is the ability to incorporate prior knowledge, which is not uh the case with the frequentist approach. Now a key weakness here is that you need to incorporate prior knowledge. So if you, so there's a couple problems with this: one is if you don't know anything about the uh population you're modeling, then there's not much you can do with the prior; there's not there's not a good way to model this uh the the distributions. Now there are some techniques to sort of derive so-called uninformative priors that try not to influence things too much but give you a plugin to be able to apply the rule, but still that is an issue. Uh, fine. Perhaps more insidiously, and the reason why Bayes' uh the Bayesian approach was popular and then fell out of favor in the earlier part of the 20th century was that you can use this rule to kind of do anything you want to confirm or deny the effect of any sort of evidence, right, just by plugging in your own prior beliefs. Okay. So given a fixed set of data, two different people could come up with different conclusions about the data because they had different prior beliefs; they modeled the the the prior distributions differently. Okay. And this was seen as a major flaw and gave rise to the frequentist approach, which looks more or less objectively at the data itself. Okay. Right. And so that's what is spelled out here in a nice essay by uh Matthews, 1988, is that different people could use Bayes' theorem and get different results. And so faced with some some experimental evidence for say ESP, True Believers could use Bayes' theorem to show that the new results confirmed it, while Skeptics could use it to show that that ESP didn't exist. Okay. And both of these are possible because Bayes' theorem only shows how to alter one's prior level of belief, and different people could start out with different opinions. Okay. So that's the issue. However, the frequency-oriented, you know, the frequentist approach, so the frequentist approach laid out by uh Fisher and others, were able to achieve what was thought to be impossible, which is a way of judging the significance of experimental data independent of any prior beliefs. Okay. He had found a way that anyone could use to show that a result was too impressive, was too statistically significant to be dismissed as a fluke, and, you know, all you had to do was convert your raw data into this thing called a P value. All right. Now you still have some sort of a threshold to measure the significance of this P value, and that was written up as 0.05 in by Fisher, you know, in a in a original paper. So what were the insights that led to this particular value of 0.05? Well, Fisher admitted that there weren't any; he simply decided 0.05 because it was mathematically convenient. Okay. And, you know, in the many people have pointed out, say from the 60s on, there's been periods of time where there's been a significant amount of work showing that this approach with these particular thresholds are able to produce a lot of incorrect conclusions. So James Berger, Puro, uh, wrote an entire series of papers warning about the quote astonishing tendency of Fisher P values to exaggerate significance findings; that met the one in 20 standard can actually arise when the data provide little very little or no evidence in favor of an effect. Okay. So that's the problem. So now perhaps the we can say that this the pendulum is in some sense swinging back towards the Bayesian approach. One more problem with the Bayesian approach that I'll bring up that I I I don't necessarily have a slide on is that, which we'll we'll see in a little bit of detail in in in perhaps the next segment, is that these conditional probabilities and these prior probabilities end up forcing you to to model a situation mathematically, and that situation may be very difficult to model mathematically. Okay. So what you do is you get these, what you end up with is these chains of complicated conditional probabilities that need to be integrated in order to apply uh Bayes' Rule. And so this was computationally intractable, and there was an enormous number of tricks and simplifications and and ideas used to uh make this more tractable. Okay. But thanks to the development of methods that allow you to sample these complicated distributions computationally, uh these this approach is becoming increasingly popular. Okay. And there's a lot of thinkers in this space that believe that, you know, for the 21st century a combination of frequentist and Bayesian approaches is going to be uh uh dominant. Okay. So for these reasons, we're going to make sure we talk about the Bayesian approach at a very introductory level and leading up to a machine learning algorithm called naive Bayes. [Music]

All right. So we talked about Bayesian versus frequentist approaches to to statistics, and this cartoon is my attempt at a quick summary. So the frequentist approach is concerned with using the data and only the data to make a decision, while the Bayesian approach uh incorporates prior belief as well as the data. Okay. And that's both a strength and a weakness; strength in that if you have good information you can incorporate it; if the weakness in that you have to actually incorporate information and that it's uh somewhat subjective depending on who you're talking to. Fine. So Bayes' theorem, breaking it down a little more detail, you've got this terminology you can apply to it. So the prior, as we said here in blue, is the probability of the hypothesis being true before you've collected any data, right? So what's the, in the global population, uh how many people are above a certain height? Okay. Then the marginal probability is what is the probability of collecting this data.

This particular data observations under all possible hypothesis, okay? And then the likelihood is the probability of collecting uh this data given that our hypothesis is actually true. And then finally, the posterior is what we're usually trying to compute, which is the probability of our hypothesis being true given the data collected, okay? So let's think about it this way: arrange this into a grid. This is, you know, it's it's actually pretty trivial to derive this theorem if you think carefully about what's going on. So a nice way to explain it is to build a 2 by 2 grid like this, where you have A and B, and not A and not B. And the box here is the probability of A and B happening, okay? Well, A and B is the probability of A given that B has already occurred multiplied by the probability that B occurs, right? And you should take a moment and convince yourself of that. Equivalently, it's the probability that B of B occurring given that A has already occurred multiplied by the probability that A actually occurs. Okay, so so these things are all equivalent. Set these two things equal to each other and just, you know, divide. So set these two things equal to and divide the both sides by probability of B occurring and you have Bayes' rule, all right.

So let's try this out. So there's a question: say you know that 1% of women at age 40 who participate in routine screening have breast cancer. And let's say you know that 80% of women who actually do have breast cancer will get a positive uh result from the test. Further say you know that 99.6% of women who do not have breast cancer will also get positive results. So these are the this is the false positive rate, okay? Now, given that you know that a woman in this age group had a positive test, right, the test came back positive in a routine screening, what is the probability that she actually has breast cancer? And you should take a minute to sort of work this out, all right.

So what sort of remarkable is that this is a fairly straightforward application of Bayes' rule, but intuitively it's easy to make sort of mistakes in in the reasoning. And in fact, when you ask this question, there's there've been some famous studies that are now somewhat out of date where they asked doctors this question and the doctors came up with wildly wrong answers. Only 15% of the uh doctors they asked were able to answer the question correctly, okay? So here's how to break it down again with our 2 by 2 grid. We've got 1% of cases that have cancer, and we've got 99, which means we have 99% of cases that do not have cancer. This is in the global population, right? And let's say we just know this, right? We know that 1% of people all across the board have cancer, or at least in this group that we're studying—shouldn't say across the board, okay? Now we also know that if you have cancer there's an 80% chance that when you take the test it'll come back positive, okay? So the true positive rate is 1% have cancer times 80%. Now we're also given that uh if you do not have cancer and you take the test you'll get a positive result at at a rate of 9.6%, and so the false positive rate is the rate of not having cancer, 99% times 99.6%. Now similarly for the false negative and true negative test: 1% * 20% (1 - 80%) and 99% * (1 - 9.6%) = 90.4%, okay? So we have all the information we need. So going back to actually answering the question, we can uh write down Bayes' rule. So what is the probabilityility of having cancer given that we have a positive test result? Well, that's the probability of getting a positive test result given that we have cancer multiplied by the probability of having cancer overall divided by the probability of a positive test overall, okay? So the only one of these terms so we actually know this term straight out, we're given this one, right, which is 80%, and we're given this one, the probability of cancer overall is is 1%. We don't have this denominator given, so we need to figure that out. Well, that's the chance of a positive test in all other occurrences, the chance of a positive test given that we have cancer and the chance of a positive test given that they don't have cancer in each case multiplied by the probability of that happening, okay? So you can you can decompose this, so that's 0.8 times the 1% probability of of actually having cancer plus 99.6% times 99%, which gives you this number of 10.3%. So that's the overall probability of getting a positive test result, all right? And so now you plug this in, you end up with a number of 7.8% for our for our answer. If we have a positive test result, the chance of actually having cancer is 7.8%. So this is lower than you might come up with if you don't think about it carefully, right? You might think that boy I got a positive test result, there's something there's this 80% number floating around, you know, boy there's probably a 70-80% chance that I that that I have cancer, but because of the uh very low percentage of having cancer in the in the prior probabilities, the actual number is still pretty low, okay? So it's easy to make mistakes with this stuff.

Now this was a remarkably simple case. First of all, we're given all this information. Second of all, there's only two possibilities, these sort of binary variables. So let's think about something a little more complicated, okay? So let's consider a classic application of Bayes' rule to a big data problem, which is spam filtering, okay? So here our task is to determine whether an email message is spam: the probability that an email message is spam given the words in the email message, okay? And and with Bayes' rule you can express that probability as the probability that the email messages spam overall multiplied by the probability of seeing these particular words in the message given that we already know it's spam and all that divided by the probability of seeing these words in the message. Now the interesting one here is this numerator, and the reason is is that the probability of words appearing uh doesn't involve the uh unknown label of whether it's spam or not. And so all we're trying to do is get a relative frequency of spam or not spam, okay? And so just dividing by a constant factor of the probability of seeing these words doesn't actually change our decision at all, so we don't actually care about the actual number, we just care about decision of spam or not spam, okay? So fine. So reexpressing this before we get rid of the denominator, reexpressing this, what do we mean by words? Well, this would you can write this as probability that the email message is spam given that the word Viagra appears in the message, given that the word Rich appears in the message, given the word something more innocuous perhaps like friend appears in the message, so all the words you know in the English language or or all the words of of interest to us in this test, okay? So that's reexpressed that way. Now this numerator uh can be rewritten in the following way: given that it's a conditional probability, we can apply a chain rule, a repeated application of the definition of conditional probability to obtain this: the probability that it's spam multiplied by, so let's see, so this expression rather can be expressed as the probability of seeing the word Viagra given that it's spam multiplied by the probability of seeing all these other words uh given that it's spam and given that it's Viagra, or given that the email message contains Viagra, and you can keep going: this probability times the probability of seeing the word Rich given that it's spam and given it's Viagra multiplied by the probability of all the other words given that it is spam, given that it contains the word Viagra, given that it contains the word Rich, and so on, okay? So this is a long complicated conditional probability, and this is where the naive Bayes assumption comes in. So under the naive assumption we say that the probabilities of these different words appearing in the email message are completely independent, that it's no more likely for you to see the word Rich when you see the word wealth uh than it is you know without the word wealth there, okay? This isn't true, right? Obviously words go go together, there are co-occurrence rates, right? But you just ignore that and just treat everything as completely independent, which allows you to simplify this expression as just a sequence of probabilities: what is the probability of seeing the word Viagra given that it's spam? What is the probability of seeing the word Rich given that it's spam, and so on. Now how do you get these probabilities? Well, you have data, right? You have a set of documents that have been pre-labeled as spam, and you can look at the number of them that contain the word Rich and divide by the total number, okay? And so now you can calculate the probability of of the two classes, spam and not spam, and apply a decision procedure to call it, and in fact a simple one is just uh whichever one is more likely, whichever one has the higher probability, it's called the MAP decision rule, which stands for the maximum a posteriori [Music], okay?

So in the last several segments we covered selected topics in experiment design, hypothesis testing, and statistical estimation, and we motivated these topics by considering the so-called decline effect, where scientific results turn out to be less reproducible over time or their effect size uh diminishes over time under repeated experiments, okay? And we found that things like publication bias and the misapplication of statistical methods can explain a lot of this effect, okay? And then we also talked about the Bayesian perspective uh which allows you to incorporate prior knowledge easier but opens the door to subjectivity leaking into the analysis, which is one of the reasons why it was largely rejected at the beginning of last century uh but it's making a resurgence thanks to computational techniques that allow you to do sampling of complex distributions, you know, at scale. And we didn't go into too much detail there, but I hope to get back to it before the end of the course, okay? So in the next few segments I want to talk about uh more of an algorithmic perspective that is more closely associated with the terms machine learning and data mining, okay? So what is machine learning? So Pedro Domingos here at Udub wrote a fantastic Communications of the ACM article in 2012 that gave an overview of machine learning, and what he said was the machine learning is systems that automatically learn programs from data. So what he means here is that when you write a program by hand you're explicitly stating how to map a set of inputs to some desired output, right? You're giving a recipe for doing that, but the point is that given enough examples of inputs and desired outputs you can infer the program that maps it as opposed to having to write it explicitly, you know? So the joke is why why bother writing programs when you can when you can learn them instead, okay? Maybe another view is, you know, teaching a computer about the world, but I perhaps prefer the first bullet here, okay?

So it's worth maybe a few minutes or just one minute or so talking about what the difference between statistics and machine learning is. It's probably not worth putting a lot of time into this or thought into this because, you know, terms are not necessarily precise and they grew up in some historical context and reflect different cultures rather than being some um well-defined notion that you can reason about. But there's a paper a long pretty long ago now, in 2001, that talked about a certain kind of difference, although they weren't specifically referring to machine learning, it captures what I believe to be the real salient difference here, okay? And so the model here on the left is that everybody involved in the space is trying to do the following, which is, you know, observe that nature is able to map inputs to outputs and we want to be able to predict that, you know, computationally, okay? So the statisticians will attack this problem by, you know, actually trying to model the world through some stochastic process. In the paper they talk about data modeling; they talk about modeling the data. What they mean is modeling the process that gave rise to to the data that you see, okay? And so the idea is that once you have a model of the world you can uh use it to sort of hypothetically draw more samples and reason about the entire population, okay? But another view that's maybe this more algorithmic view is look, you know, we recognize that nature is difficult to model and we don't really care if we have an accurate model of it; all we're trying to do is measure our performance in predicting the outputs that we've seen from given inputs, okay? So it's it's not important that the model that we uh produce, that the program that we generate actually reflects the real process that's going on in nature or not; we don't we don't claim it does, but we but what we do claim is that it does a pretty good job making predictions anyway, okay? And so I think this is the notion that's more associated with the machine learning approach, all right?

So let me give you an example that comes from Witten that's used pretty ubiquitously to explain some of the concepts of machine learning, and we we won't use this example too much but it is useful for a variety of purposes. So imagine you're trying to predict when someone is going to play golf or play tennis or do some other outdoor activity, and we imagine that it's a function of the weather. And so we take in inputs like uh the outlook, whether it's sunny or overcast or rainy, the temperature, whether it's hot, cool, mild, uh the humidity, how windy it is, and we want to learn a function that takes in those inputs and produces a yes or no answer whether or not we play, say, golf, okay? And so the simplest version of this you might do just intuitively is just try to predict it with a a simple rule. So you might say look, maybe we only play when it's sunny. You know, is this true or not? Well, no, it's not true because we find we can find examples where we did indeed play when it was overcast, okay? You might say well maybe we don't play if it's rainy and windy, and that turns out to be true, but there's also other times that we don't play as well. So the pattern that you know if a function exists that can predict this output, well it's perhaps not something that we can express in just one simple rule, which is kind of the limit of what we can do um you know mentally just through intuition. So the idea is we need some principled way of coming up with more complex models when when they're needed, okay? So fine. So this some terminology: this problem is an example of a classification problem where there's a learned attribute and it's categorical; it can take two values in this case, zero or one. Uh if the learned attribute is more of a numeric value, for example what our score at golf was, you know, as a function of the weather if we want to try to predict that uh that would be more of a regression case, okay? And really not just learned attributes, probably when all the attributes are numeric it becomes more of a classical regression case, although there's ways to handle this. And so we've talked about regression in terms of, you know, fitting a curve to data, but when you use that fit curve to actually make predictions uh that's when it sort of you can see that it's analogous to the classification problem over categorical data, okay? So more terminology: the the golf example we just gave is an example of supervised learning where you're given examples of inputs and the desired outputs, and we're trying to learn the relationship between them. So we train a model to do this, and there's also a notion of unsupervised learning which is you're not given any labels whatsoever, you're just given the data and you're trying to understand the underlying structure in that data, okay? So this is things like clustering algorithms or dimension reduction algorithms if if you've heard those terms before. So let me give you an example with that can be sort of cast as either supervised learning or unsupervised learning, but it's instructive as an unsupervised learning case uh for right now. So imagine you're just given a big corpus of documents and you're trying to figure out you want to make a prediction of what uh topic a given document pertains to, and so you know if you see the phrase the Falcons trounced the Saints on Sunday you might guess that this document is about sports, while if you see that the Mars rover discovered organic molecules on Sunday you might guess that this document is about science. And so you know how do you set this problem up as a machine learning problem? You know, what are the rows and columns? We just had an example where there sort of rows and columns and we said for one for one record we're trying to predict the output given the inputs. What are the rows and columns here? Well, this shouldn't be too bad since you've seen this before in a couple of assignments [Music]. Now, okay? So how do we set this up? Imagine you had five documents that were just represented by these simple phrases here, so document one is just the phrase Romeo and Juliet, document two is Juliet, O happy dagger, document three is Romeo died by the dagger, and so on. Well, with some stemming and some normalization of the terms we could uh associate a column of data with each one of these terms, and each document is in a row in this table or matrix, and we put a count in each position for the number of times that term appears in the documents, and again you've seen this in a couple of different assignments now, okay? So given this basic setup you can think about a supervised learning version of the problem or an unsupervised learning problem in different contexts. So the supervised version is, you know, you have a corpus of documents and there a human has assigned a label uh to each document in the corpus, okay? And so you want to come up with some sort of model that can predict that label given the text in the document, okay? An unsupervised learning uh version of this problem is that no labels are given, but you want to discover groups of similar documents. So you want to say that look, all these things have something in common; we don't know, maybe we don't understand that it's about sports, but we know that they all have something in common, and these over here, maybe we don't know it's about science, but we know they all have something in common, okay? And so that would be an unsupervised learning problem, in particular sort of a clustering problem, all right?

So in all these cases there's going to be three core components to think about, and this again comes from Pedro's article, so they are representation, evaluation, and optimization, all right? And so every problem you come into is going to have something to say about all three of these, okay? Representation is, you know, what exactly is your classifier, right? Is it a rule like the ones we saw with the uh golf example, right? A simple hypothesis of uh maybe when it's sunny we always play golf, right? The space of all possible such hypotheses, all possible such rules, is the representation of this of this classifier, okay? Or is it or or each one of those is perhaps a representation uh or you know is it the space of all possible neural networks that map inputs to outputs, right? Or is it a decision tree, which we'll talk about in a little bit, you know? Or or if it's more numerical data, you know, if you've got a a 2D scatter plot and you try to draw a line that precisely separates the data such that all the positive examples are on one side of the line and all the negative examples are on another side of the line, the space of all possible such lines is the representation here, okay? Right, so what what are the what are the what are the nuts and bolts, what are the units that you're talking about, okay? Fine. So once you have that figured out you can think about, well, look, how do I judge whether one particular example of this instance of this representation is effective or not? Is it how how do I know the good ones from the bad ones? So, for example, with the rules when you're trying to play golf, uh I've got a rule that says when it's sunny we play golf and when it's rainy and windy we don't; those are two different rules. How do I judge which one's better? Well, there's different you have to make some sort of a choice about how you're going to evaluate this thing, and it could be just the number of errors it makes on some given

test set, or you could define some notion of precision and recall. Or if it's more of a regression numerical case, you could talk about the um absolute error, the squared error, or other variance, right? You need to make some sort of a decision here. So now we have, you know, if we have the representation, we have a space of possible units, and now we have a valuation method selected where we can take a given instance and determine whether it was any good or not. Fine.

The third piece here is optimization. So how do you search among this potentially massive space of, or potentially infinite space of, uh possible hypotheses? Okay. So in pretty much no case is it going to be feasible to enumerate all possible uh instances and apply your evaluation technique to find the best one. So you're going to have to have some method of searching through this efficiently. Okay.

Now what's useful, I think, about this breakdown is that it helps make sense of the various terms and methods you'll hear if you sort of scan the machine learning literature. Is that many times you'll be, what what what will be being presented is just an optimization technique that can apply to a variety of different representations and even evaluations, and you can plug in your own evaluation and plug in your own representation; it'll still work. Other times you're talking about a representation that is adaptable to a variety of different optimization strategies or particular algorithms. Okay. So it helps to make sense to understand which one of these three things you're talking about, or if you're talking about something that really uh denotes all some some choice about all three. Okay. And so we're, as we talk about methods, we'll try to refer back to these three components and describe what's going on in each case. Okay.

Let's consider some specific algorithmic techniques. Okay. One of the data sets I want to use to illustrate these techniques is the passenger list from the Titanic. And this is a data set that's available out there in the web and has been used for various purposes, but it's also available as a Kaggle competition, and it's one of the competitions you can participate in; it's used for uh getting started, for kind of a training exercise. Okay. So what this is is a one record for each passenger on the Titanic, or in the training set, a subset along with various attributes that describe that passenger and uh whether or not they survive the sinking of the ship. Okay. And so the columns here are survived, which are given as zero or one, zero meaning they did not survive; and Pclass is the uh ship's class, like first class, second class, third class, which sort of deck they were they're they were on; uh gender, age; uh sibsp is the number of siblings they had on the ship; parch is number of parents and children, so number of children if you're a parent, or if you're, well actually either way, so total number of parents and children; uh fare is the fare in dollars that they paid; cabin is an indication of their cabin number, and you can see that there's a lot of missing values here where either wasn't known; and then embarked is a one-letter code indicating where they got on the ship. Okay.

So fine. So the first thing to do probably whenever you're tackling these problems is to inspect the data, right? So if it's sort of telling you something, you shouldn't ignore it; and if, more importantly, if it's not telling you anything, that's maybe a sign that it's going to be tricky to learn a pattern automatically. And so one thing you do is to start plotting scatter plots uh of these various columns. And so one idea you might have is, well, maybe women and children first, right? Maybe the kids tended to survive. So you can plot age, and then maybe you might imagine that people who had paid more for their fare uh sort of had more influence on the ship. And so this is a scatter plot of age versus fare, and you can see there's probably not too much of an obvious pattern there. Does seem, oh, blue here by the way is survived, and red is did not survive. So you can see that there's kind of a cluster of blue around, you know, the the the very young children maybe tend to survive much, but other than that there's not anything really obvious here. Okay, or at least it doesn't seem obvious to me. All right.

Another one you can do uh is age versus sex, and I played a little bit of a trick here here where I'm plotting categorical data as a numeric attribute, um which is a pretty useful trick to do. And you can see that this is also kind of smeared a little bit here, and what I did was add a little bit of a jitter so you could see the values; otherwise, you know, it's not it's not that someone is sort of, you know, 0.1 male and and 0.9 female or anything; it's just that uh if you don't add that jitter, then every all the values end up directly on top of each other, and all you see is the last one plotted. And so if you spread, spread them out a little bit, you can kind of get a sense of how many are red and how many are blue. Okay. And so one thing that does seem pretty obvious here is that, you know, the women and children first did sort of hold up, right? Certainly there's more blue here than there is in here, uh but again the age doesn't necessarily tell you all that much. All right. So fine. So maybe, you know, a very naive classifier, just to sort of illustrate a starting point, is what's called the rote classifier. So this is: look, if I see a new record coming in, I'm going to go look for an exact match in the in the training set, and if I've got something that agrees on every single attribute, then I'm going to assign it to the same class. If I've seen this example before, then, you know, darn it, I know what to do. Okay. And if it doesn't, then you have to just guess. Okay. So this classifier is not particularly useful.

So a minor improvement on this one is, following, you know, given a new passenger that we haven't seen before, uh see if it matches an existing example on some particular attribute, and if it does, then take a vote among people with the same value and see what they say and use that to determine the class. So, for example, you see a new passenger and you notice that it's female, then you can look back at all the other females you have, and if there's more females that survive then who did not survive, then you declare the the new passenger must have survived as well. Okay. But you know there's lots of possible rules like this one, for every value of any attribute, and you know, in particular, an attribute can have more than just two values, male and female, so you need some way of choosing among these. So we have the representation of the hypotheses in in terms of rules, right? Each rule is a hypothesis. Okay. So that's the representation; we now need the evaluation. How do we determine which ones are good and which ones aren't? Well, one thing you can do is construct a confusion matrix, which is a square matrix with a number of rows and columns uh for each unique label, each unique class label, and the diagonal of the confusion matrix will tell you which labels you got right. Okay. So, for example, here using this uh one simple rule that looked pretty good when we drew the scatter plot, if sex equals female, then survive equals yes, otherwise no, we have 468 instances where we classified the passenger as having not survived, and indeed they had not survived. We have 233 cases where we classified them as having survived, and they did indeed survive; and the other values are when we are the mistakes that we made: we classified 109 as having survived who actually did not, and we classified 81 as not having survived who actually did. Okay. So this is actually useful for sort of visual inspection, but it doesn't really give you a single number that you need in order to actually, you know, build a program that would do this automatically. So what you can also do is just measure the accuracy, which is here, you know, 468 plus 233, the number we got right over the total number covered by the rule, and in fact we didn't have any missing values with male and female, so they're all covered by the rule, uh is about 79% correct and 21% incorrect. So this is not too bad given that it's such a simple model. Okay. Fine.

So another scatter plot we could look at, maybe in an attempt to improve upon it, is look at the, you know, whether they were in first class, second class, or third class, and here, you know, we don't have sex on here, which is a pretty strong indicator, but we do see, see some interesting patterns. It looks like people in first class tended to survive more, uh certainly more than people in third class, and then it looks like the kids in second class tended to survive uh more than the adults in second class. Okay. So this suggests a slightly more complicated rule. Okay. But here's just another example of of a simple rule, just for class itself: if if you're in first class, then you survive; if you're in second class, then you survive; but if you're in third, in third class, then you don't. And so now, you know, the confusion matrix we can build again—remember the confusion matrix is just the class label, so it's still just no and yes, and no and yes—and how do we do here? Well, the diagonal tells us 372 plus 2323 over the total number is only 67% correct, so it's a little bit worse. Okay. So we have a representation of hypotheses, and we have an evaluation method, but we need some kind of a search strategy to consider all these rules. And so for the one-rule case, you conceivably could just enumerate all of them. And so one potential search strategy—maybe I hesitate to call it optimization—is just to do so. So the one-rule algorithm is this: for each attribute A and for each value of that attribute, create the rule; count how often each class appears; find the most frequent class; and generate a rule: if A equals V, then class equals C. Okay. And then you can calculate the error rate of of that rule; pick the attribute whose set of rules produces the lowest error rate overall. All right. And now you'll have uh one rule. Now, by the way, one rule again refers to actually an attribute, um so it's an if-then, if-then, if-then, if-then, covering all the values of that attribute, not just, you know, for male and female; that's not two rules, that's just one rule. Okay. So this is kind of an exhaustive search strategy for which to generate these rules.

So how far can we go with this? Well, you can imagine having more complex rules with more conditions in them, and you can also imagine having a whole set of rules, and your classifier now becomes uh checking this whole set of rules to determine the class. Okay. So how do we go about building an appropriate set of rules to come up with a classifier? Well, so one approach is this sequential covering, which looks like this: you start off with a data set D, and you initialize the rule set R to be empty, and you say, for each class—you know, say survived or not survived—you can construct one rule that correctly classifies some instances in D, right? So some you capture some of the people who survived and does not incorrectly classify any of the other classes. Okay. Okay. And then you add that rule to the rule set and remove from D all the instances that were correctly classified by this rule. And so we're going to keep on adding up rules this way. Now that's great, but it doesn't tell you how to actually find that next rule, and so that's what this explains: so come up with a set with with an initial uh rule R that just uh trivially assigns a a class value to every record. Okay. And so while it's in, while it incorrectly classifies some of the non-C instances in D, so write R as the antecedent of R, determine C. And so here the antecedent initially is uh nothing. Okay. And then for each attribute-value pair A equals V, where A is one of the attributes and V is some value of that attribute, figure out the accuracy of that rule, just like females predict survival, and we determine the accuracy there with 79%, or male determines—well, we're just assigning one class right now, so just just survival. Fine. And then figure out the attribute-value pair that has the maximum accuracy over D. Okay. And in case of a tie, choose one that covers more cases. All right. So now update uh the rule R with this new condition A star equals V star, and remove that attribute from consideration uh in the set A. Okay. And then keep going until you are no longer incorrectly classifying some of the non-C attrib instances of D. And now in the next time around the loop, the antecedent of R will be the previous condition, and so that's what this notation is just trying to show: so you can have the prefix of the rule and keep adding one more conjunction, one more condition I should say, one more equality condition uh to the rule one by one. Okay. But the point here is that you're still looking for the um attribute-value pair that has the maximum accuracy. Okay. Okay. So in this case, we started from an empty rule, and we incrementally added constraints until we uh started incorrectly classifying some negative examples, but you can do it both ways. So this top, there's a couple different strategies here: one is to go from general to specific, as we just did, which is start with the empty rule and add constraints to eliminate negative examples and stop only when all you have left are positives, but you could also imagine going specific to general, which is starting with a particular instance and constructing a rule that exactly specifies that particular instance, right? So it has a constraint for every attribute uh and you uniquely describes that that one data point, and then you could remove conditions one by one uh in order to try to cover more positive examples and stop whenever you hit one that covers some negative examples. Okay. And then you move on to the next rule. Okay. So once you have these sets of rules, you need to use them to make predictions, and one thing that can happen is you can have more than one rule triggered for a particular data point, and so you need to have some way of resolving conflicts. So here you might choose the most specific rule, or you might even choose the most general rule, or you could apply some domain knowledge in order to assign a priority to each rule and use that to, you know, break ties. All right.

So recap of this brief introduction to sort of rule-based methods is the representation here is a set of these if-then rules with varying numbers of conditions. Okay. And the evaluation strategy is to come up with the coverage of a rule and and measure the accuracy by the number of correct predictions it makes divided by that coverage, and then the optimization is uh the search strategy is to sort of build rules by finding conditions that maximize accuracy one step at a time, and there you can either go from general to specific or to specific to general, and we didn't discuss sort of the various trade-offs among those choices. And so the maybe takeaway for these rule-based methods, besides using it to build into uh the next segment, is that you know one rule, a few rules, is pretty straightforward and pretty easy to interpret; a big set of rules may not be—the overall properties of a big pile of rules is not immediately obvious. Okay. So again we can consider how far we can go with these sets of rules, and we showed the one big flat list that's gets pretty complex; might be hard to interpret. So one thing we might do is consider grouping redundant conditions, right? And so this starts to look like a program you might write in any language where you say: if the passengers are in first class, then if they're female, then survive equals yes; and if they're male and age less than five, then survive equals uh yes or no or whatever; and if uh they're in second class, then have another nested set of conditions, and so on. And so this starts to look like a a tree, and these decision trees are what we're going to talk about next. All right. So how this looks diagrammatically is this, right? You sort of drop the each patient, each uh passenger down the tree, and each node in the tree makes a decision about where they where they go based on their attributes, and eventually you end up at a particular bucket. Okay. And so you can imagine here that which attributes you start with on top uh allows you to generate a lot of different kinds of trees, and they'll have different properties. Now the relationship between one of these decision trees and the sets of rules is that every path from the root represents one rule. Okay. So you can always turn it, turning a tree into a set of rules is pretty trivial because it just draw, draw a line from the path to the root, uh draw a path from the root to the leaf, and every time you can do that, you end up generating one rule. Going the other direction is not necessarily straightforward, because there's subtrees and so on, so you need to make some decisions about how to handle that. All right.

So switching examples for a second, consider going back to this document classification example. You can build decision trees in this case as well. You can say: look, if the document includes the term Sunday, you either have, you know, yes or no; and if it includes the word Saints, then you have yes or no; and if it does, then it's probably talking about sports, right? And if it includes the word Sunday but includes the word Mars, it's probably talking about science. Okay. And so here Sunday, the the include Sunday yes or no condition being at the top maybe wasn't all that helpful, and we'll make that notion more precise in a moment. Okay.

So in order to make a decision about whether a node in the decision tree is helpful or not—which I just claimed that we had an example where one wasn't helpful—we need this notion of entropy. Okay. A way to think about this is consider two different sequences of coin flips. Okay. And we want to figure out how much information do we get after flipping the coin in each sequence once. All right. So the reason I'm talking about two different sequences is we want to have some kind of relationship between these two different coin flips. And so we want what we want to be true is that the probability of it coming up heads on the one hand and the probability coming up heads on the other hand, you know, with these two coins, we know that if those events are independent—which we assume they are, assuming everything's fair about these coins—then you can multiply those probabilities together. And so if we're trying to make up some new function called information, then we want information applied to the uh joint probability of those two events to be the same as the information gain from one of the events plus the information gain from the other event. Okay. So let me just say that again: we're doing an experiment with two different coins simultaneously, and we're trying to design a function that captures our intuition about what information is. Okay. And it must have this property, right? Any sensible definition of this of this information function must have the property that if I have two different separate events, I should be able to add their information together to get my total, uh and I, that should be the same value as applying the information function to to the probability that they both happened. Okay. So with a fair coin flip, it's 0.5 * 0.5, so information of 0.25 ought to be the same as information of 0.5 plus the information of 0.5. Okay. And you know it's here on the slide: the function that gives you that is log base 2. Okay. Fine. So that's the information. Now what's entropy? Well, entropy measures the amount of unpredictability in a set of events, a sequence of events. And so this is the expected value of the information. Okay. An expected value: whenever you see expected value, you should always be thinking about: I'm going to be multiplying a probability by a value gained if if that event occurs. Okay. And so here you're saying, and then adding, adding up all those eventualities. So that's expected value: in every circumstance, it's going to be multiplying probabilities by value, and so here is no different. So we take—I pause because

I see that there's a um, bug on this slide, which is this is negative because log log of a a probability probability is less than one, so that's always going to produce a negative number. And we want information to be a positive number, so we need to reverse the sign, and it's reflected down here, but it wasn't reflected in that definition. Okay, so we understand why information is log is the log function, and we understand that uh, we want the expected value from a whole sequence of events, and so that so the formula falls out of it. It's the probability multiplied by the log of that same probability, and then add all those up. Okay.

And so this guy comes up a lot; we're going to use it in one particular way, but you should keep your eye out for it whenever you see, you know, some value from 0 to 1 multiplied by the logarithm of that same value; you're talking about entropy. So let's look at at an example. So assume you're flipping a coin, and we see the same expression here on this slide that we saw on the last slide, except that this should say x instead of I X, or I is fine; it doesn't make any difference, but they should be the same. Then you expand this expression this way: if it's a fair coin, then you have 0.5 * the log of 0.5 plus 0.5 * the log of 0.5, this representing heads and this representing Tails. Okay.

And if you compute that, the answer is one, and this is appropriate because we imagine that flipping a coin gives us exactly one bit of information. Right, it tells us the result of one 50/50 choice. Okay, things are either on or they're off, and when you tell me the answer, I've learned one bit of information. All right.

So now consider if we're rolling a die. There are six outcomes, each having a probability of 1 over six, and so use the same expression, uh, 1/6 * the log of 1/6 and add all those up, which is just multiply by six in this case, and you get entropy of 2.58. Okay. So what this says is that when I roll a die and get the answer, I've learned more information; this is less predictable, more unpredictable. Right, it's a higher number, more unpredictable than flipping a coin, which agrees with our intuition. All right.

So now imagine rolling a weighted die that had these probabilities, you know, values 1 through 5 were all uh 10% chance, and it had a 50% chance of rolling a six every time. Well, we can do the same thing, and there's that bug again; this could be X, so this is 0, you know, 10% time the log of 10% * 5 plus 0.5 log 0.5, and so here you get 2.16. So here a weighted die is, goodness, less unpredictable than a fair die. Right, which again agrees with our intuition, right? Because we, if you had to bet what was going to come up, you would bet on uh that a six would be rolled. Okay.

So how do you apply entropy to a data set as opposed to a random variable? Well, you can do it with respect to the class labels. So if you have 891 passengers in the Titanic data set and 342 of them survived, then you can compute entropy uh from those two sets. So 342 over 891 log 342 over 891 plus 549 over 891 and so on gives you an entropy of 0.96. So this is almost one bit of information, and this makes sense because 342 is about half of 891. Right, so it's about you you learned a lot by identifying someone as having lived or died. Okay.

But then say there were only 50 survivors. Well, then uh the the data set is inherently more predictable, right, because most people didn't did not survive, and that's reflected in this calculation; you get an entropy value of 0.31, so it's inherently less unpredictable or more predictable. Okay, so fine. So that's entropy. Going back to decision trees now, which attribute do we want to choose at the at each level? Right, we're going to we're going to build a tree, and we have to make a choice of which attribute we're going to use to split on. Okay.

And the one the one we're going to pick is the one with the highest Information Gain, and we're going to use entropy to compute Information Gain, and another way of saying that is it's the one that reduces the unpredictability uh the [Music] most. Okay. So how do we compute this Information Gain and how do we use it to make decisions in building the decision tree? All right. So let's go back to this simpler example of, you know, predicting when we're going to play golf or do some other outdoor activity. Okay.

So before we've made any decision about the decision tree, we've got 14 records, and nine of which are labeled yes; they're positive examples, and so we can compute the unpredictability, the entropy of this data set uh just as we have with the uh Titanic data set, with the die rolls and so on, and we get 0.94. Now if we choose the Outlook attribute to be the root of our tree or to be the next node in the tree, then we see that we'll have four records that are overcast that represent overcast. Right, if we choose the attribute Outlook, then the value overcast has four records, all of which are yes, and so the entropy of that choice is going to be zero. Okay, it's it's entirely it's 100% predictable. Right, it's zero unpredictability. All right.

And the value rainy has two Nos and three yeses. Okay, so five records total; 3 out of 5 log 2 3 out of 5 plus 2 2 over 5 log 2 2 over 5 is 0.97. Okay. And then finally, if it's sunny, then you have three Nos and two yeses, and it's the same value, 0.97. Okay. And so now the expected new entropy if we have chosen Outlook, you compute an expected value; expected value is the probability of making that choice times the value of that choice, and so four out of 14 has a value of zero; 5 out of 14 has a value of 0.97, and 5 out of 14 has 0.97 again. Right. And so compute the total there, and it's 0.69. Now the gain here is the difference between where we started and where we end up. All right.

Considering temperature, well, here we have four records, sorry, for the value cool; we have four records, one, two, three, four, and we have yes, yes, uh, no and yes, and so three of them are yes out of four, and you can compute the formula and you get 0.81, and you can do the same thing for r oh, excuse me, should be um hot, and this should be mild. All right. And so you can compute the same values here, and so with this one, so with hot, we have exactly two records are yes out of four, and so that's 50/50, and remember that that's that's always unpredictability of one. Okay. And then finally, when it's mild, there's six records, four yes, and we get an unpredictability of 0.92, and so then you plug in the formula and and the expected new entropy is 0.91. Okay. And so the gain here is less than it was for Outlook.

And finally, we can finally next we can consider humidity, and here there's only two values; seven records have normal humidity, and six of those are yes, and so the entropy is 0.59 if you plug in the numbers, and if humidity is high, there's seven records there as well, and only two of them are yes, and the entropy here is 0.86, and so the expected new entropy here is 0.725. And finally, windy; there's also two values, only two values here; so if it is windy, there's eight records with windy, six of which indicate we played, and the entropy is 0.81, and the uh when it's not windy, there are five records, three of which we played, and the value is 0.97, and run through the numbers, and you get 0.87. Okay.

So now we have a computation for every possible choice of attribute, and we compute these four gains, and it's really just the minimum of them since we're subtracting the same amount, same value every time, and so Outlook, the first one we did, is indeed the one with the highest gain, and so that's the one we'll pick. And so this sort of makes sense if you think about it; there's a you know, we went through the calculations here just to sort of try to help you internalize what's going on with entropy, but it it does sort of make sense; it's the one that if if you can choose an attribute that tells you exactly what's going on, you know, you want to pick that one. Right. So if you if you always play when it's sunny, all right, that attribute tells you a lot of information by selecting that, so you want that one at the top; you want the most discriminative choices at the top. Okay.

And just like we showed with that document classification example, you know, we put, well, if the document includes the word Sunday, then we go over here, and then we check and see if there's a sports team reference in it and determine of sports, and over here we we'll choose if something related to science is in it. So really, it wasn't much use to pick Sunday at the top, and in fact, I guess I have that on the next slide here. So which of these two has the higher Information Gain? Right, if you include the word Falcons, well, Falcons might appear in some science articles, and they also appear in some sports articles, and so let's say that down the tree about half or Sports and about half or science on both branches. Okay.

And but if it includes the word Mars, it's not too likely to be about sports, and so only about 2% of the articles that include the word Mars will be about sports while 95% will be about science. Let's say let's make sure that adds up to 100. Okay, fine. So which one of these has the higher Information Gain? Well, it's includes Mars, and so that one would be chosen first. All right, fine. So what's the algorithm here? Let me okay.

To summarize this algorithm, which is called the ID3 algorithm, uh, assume all attributes are discrete, and we can discretize continuous attributes by binning them in particular intervals, and I'll give you a method to do that a few slides, and then you're going to choose the attribute with the highest Information Gain and create branches, one for each value of the attribute, and then partition the examples based on the selected attributes so far, and you repeat with the remaining attributes on their remaining set of examples. Okay. And so you sort of recursively apply this, and then the stopping conditions are, well, when there's no more examples uh left or all the examples along a branch are assigned the same label because there's no more decisions to make at that point. Okay. And so this in this way you can apply this algorithm and build up a decision tree on your data set, and as you can see, this isn't too hard to implement; the the maybe trickiest thing if you're not familiar with with it is this notion of Information Gain, which we went through, but other than that, it's you I hope you can imagine trying to write a program that would that would do this; there's a little bit of bookkeeping to do about building up this data structure, but it's not too complicated. All right. Okay.

So what are some problems with this decision tree algorithm? Well, one is that it's expensive to train; you have to sort of keep inspecting these big chunks of the data set when you make every decision, uh, and it's also prone to overfitting, which we haven't drilled into, but this is in general what overfitting means: you do really really well on your training data, but you do poorly on test data, which is to say that the model doesn't generalize. Okay. And so you can imagine that you get these decision trees that are very very good at making very precise decisions about the training set, but you give it one new example that hasn't seen before, and it puts into some bucket that may or may not be right. Okay. And so this so there's ways around this; you can try to prune uh branches of the tree that are over specialized to particular conditions. Okay. And so remove or aggregate subtrees that don't provide much discriminatory power, uh, but there's another way that we're going to talk about in the next segment that's very very powerful. Okay.

Okay. So before we do that, let's talk about how to split continuous attributes uh to make a decision with a reasonable number of branches. Right. So one thing is you could split on every unique value, but given that you know a measurement value, a floating-point number, it's unlikely for there to be too much grouping, in which case you'll have a an individual branch for every possible value in the uh data set, every possible record in the data set, which gives you no Information Gain or sorry, gives you a lot of Information Gain uh but doesn't actually help that much; it sort of instantly overfits. Okay. So you want to sort of bucket these things. So how can you do this?

So imagine with this weather data set, instead of having humidity labels of normal and high, we actually had the percent humidity as a number. Okay. And so one way to bucket this might be that you know we're going to say between 60 and 70 is one bucket and between 70 and 80 is another bucket and so on, but that requires some domain knowledge uh and ends up being sort of an extra decision you have to make when you're modeling this data, and we're trying to avoid decisions when we're applying these these machine learning techniques; we want to we don't want parameters in the system unless we have to. Okay. So what's a way to do this sort of algorithmically? Well, you can imagine that if we sort the data set in increasing order of humidity, point at the wrong screen, that every every point in this humidity data set represents a possible place to split it into two choices, high and low. Okay. And so what we can do is just evaluate each one of those choices uh and measure the Information Gain and choose the point which gives us the highest Information Gain. Okay.

And so here's what that might look like; I haven't actually checked every single one, but I sort of eyeballed it and saw that wow, you know, the first several have solid yeses all the way up to here, so this might be a pretty good candidate to split on because on one branch we know we're going to have nothing but yeses, and that's what we're looking for here; we're looking for reducing unpredictability. Right, Information Gain. Okay. And another good place to split perhaps is uh down here because there's a lot of yeses, all but one above it, and uh Nos above this, which sort of makes sense because as the humidity goes up, we have uh we're less likely to play outside. Okay. So fine. So if you go ahead and compute the entropy here, here is six out of six are all yes, which means it's zero entropy, totally predictable, and here it's 3 out of 8 plus 5 5 out of 8 entropy uh is 0.95, and here 9 out of 10 or 1 out of 10, that means that's a lower number as we'd expect because it's pretty predictable. Right, 90% chance of um being a yes, and here four out of four is 0 point is uh you know zero. Okay. And so now you do the expectation and say add out of 14 cases with times 0.95 plus 6 out of 14 cases uh of of zero is a pretty low number, 0.54, but over here it's an even lower number, and so the right place to split is here, and I didn't check the others, but clearly these are the the only places that that will matter because it didn't it didn't change in between there, which actually suggests an optimization. Okay.

So again, we consider every possible binary partition and choose the partition with the highest gain is a way to turn any continuous variable into a discrete variable so that you can uh work on this, and you could actually do this more with uh instead of just true false or instead of just high low, you could also pick uh more buckets to have even higher fan [Music] out. Okay.

So where are we? We're talking about supervised learning, and we're talking specifically about classification problems where we predict a class label based on the other attributes, and so we gave an example of uh predicting whether or not we play some sport based on a few different attributes representing the weather or predicting whether a passenger aboard the Titanic did or did not survive based on uh things like their gender, their age, the fare they paid, and so on. Okay. And so to get started here, we talked about just you know, manually guessing simple rules that might explain the data, and as you might imagine, uh the relationships between the attributes and the class label are complex, and so you know, your your intuition uh may be wrong, and so you need some way to automate the search for these kinds of rules. Okay.

So we talked about this one-rule algorithm that will uh proceduralize the process of choosing a good rule, uh, and that worked fine, but you know, obviously it's pretty limited. Right, it can it can only find very very simple kinds of relationships, and so we also talked about a sequential cover algorithm that looks for that builds up sets of rules that may have multiple conditions in them. Okay, you know, so great, so a set of rules that are themselves complex are more descriptive of the data and therefore uh have better strength as a classifier, but they're also harder to interpret, and one of the points that we've been making in this class is that you know, communicability of these models, communicability of the results is uh important. Okay. And so a single rule is easy; a set of complex rules is perhaps less so, and for that reason and for other reasons, we can talk about decision trees, and we sort of showed that uh a decision tree uh I was about to say can be constructed from a set of rules, you know, each each path from the root is a is a rule, but that's not quite true; constructing a decision tree from a set of rules is not necessarily trivial; going the other direction is pretty is straightforward as we described; every path from the root is a rule. Okay. But but there is a relationship. Moreover, given a decision tree, it's pretty easy to interpret, I would claim. Right, you just sort of take your data item and look at the root node and answer the question, you know, is is the gender male or female? Female will then go down this branch; male go down this branch, so it's very easy to understand what's what's going on; it's also easy to understand what the most important decisions are because they bubble up to the top. Okay. And so if someone's asking you, well, why you know, how is your model behaving? Why does it make one decision over another? You can sort of answer those questions. Okay.

And so we talked about using how you make the decision of uh which attributes to select at each level, and we talked about entropy being a measure of sort of the purity. Right, the game is to try to make an entire branch uh uh pure with respect to a class label. Right, everyone down this branch survived. Okay. And so entropy gave us a way to do that, and then we talked about a few extensions for numeric attributes where you could split uh based on at a particular level as opposed to uh you know, I said if you don't have gender male and female but rather you have a number like humidity or the fare they paid, you have to be a little more careful; you don't want to have a thousand different branches coming out of a node, one for each unique value; rather, you want to bucket them somehow, and so what's the way to bucket them? Well, one one idea is just to find a split point to splits into two children, so everything below this value goes one way, and everything above this value goes another way, and we talked about how to find that threshold. Okay. So fine. So where we are now is that decision trees are potentially prone to overfitting, and so let's talk about that. This excerpt is from Pedro Domingos' 2012 CACM paper that we've mentioned before. So you know, what if the knowledge and data we have are not sufficient to completely determine the correct classifier? So it could be that we've you know, designed a classifier that is responding to what you know you call random quirks in the data as opposed to sort of uncovering uh some kind of fundamental truth; you know, it doesn't have any predictive power in the real world; it just sort of describes this particular data set, and so the problem here is overfitting, and you know, he says it's the bug bear of machine learning; you know, a lot.

Of machine learning problems are really reduced to how do we avoid overfitting? Right, because you can always train a model on this, on a particular data set, but how do you avoid, uh, specializing it to this data set and making sure it has some, some predictive power in the real world? Okay.

And so, you know, the case to look out for here is when your learner outputs a classifier that is 100% accurate on the training data but only 50% accurate on test data. Uh, when in fact it could have output one that is 75% accurate on both, it has overfit. Okay. And so that I want to call out that this is really the, the definition to think of when you think about overfitting: low error on training data and high error on test data. Okay.

So an image that sometimes is called to mind when you're talking about overfitting, uh, is this one which is, you know, I've I've fit two pols to a, a small set of data points, one with a high degree, I think 10, and the other with a low degree, in this case actually still pretty high, it's five. And you can sort of see that a couple things: one is that the red curve is exactly matching the data. Okay. Um, but you can also see that the sort of what appears to be the trend in the data, uh, probably is better described by the, the green line. And in fact, it was, it was generated by a model that's sort of adding some random noise, uh, to a curve. And so the green one probably does actually reflect the actual, um, underlying data model, you the underlying process which, which generated the data. But you know, the other, the other point to look out for here is it's, um, sensitive to changes to perturbations in the data. If I move one of these points, just one of these points a little bit, how much does that curve change? And the green one would not change much while the red one, uh, might.

Okay. But I actually don't think this curve fitting model is the best image to call up when you think about overfitting because it's, it's in my mind it's a little bit specific to polynomial curves and the, you know, number of degrees of freedom you're, you're, you're working with. Okay. So it's not always clear, at least to me, how to map this image that I call up in my head of overfitting to machine learning problem. So I think a more useful one is one that's actually associated with a Wikipedia page, uh, on an article related overfitting, uh, that's released under Creative Commons, is this: that over time your error, uh, goes down for both your training set and your test set, but at some point it continues to go down for your training set—I'm pointing at the wrong screen—this continues to go down, um, on your training set, but then it starts to creep up on your test set. And so at this point, you know, he's put a little symbol here to indicate that's where overfitting has set in. And so I think this is the image you should call to mind when you're thinking about overfitting problems, is this difference between the error on your training set and the error on a test set.

Now, in some cases it's tough because the test set, you know, may be, um, you know, what, what is the test set? Is it, is it something you actually have your hands on where you can measure this hair, or is it more like predictive power in the real world? But regardless, any kind of estimate you have over, um, the error that you're actually achieving on data that you didn't train on is, is what to look out for. And when these start to diverge, that means you overfit. All right.

So other language to be familiar with around this concept, you know, is the model able to generalize? That's when it's, that's when you're, if it, if it is able to generalize, then you are not overfit. Okay. Can it deal with unseen data, or does it overfit the data test on? So in order to solve for this, you test on hold-out data. Okay. So one way to do this is split the data to be modeled into training and test set, just in a fixed way, train the model in the training set, evaluate the model on the training set, and then evaluate the model on the test set. And the difference between those two again is, is a measure of the ability of the model's ability to generalize, you know, a measure of how overfit it is. Okay. Now, doing this just once, splitting between training and test is, um, not the most powerful mechanism to do this, and a couple of slides give you a better one. All right.

So another image to kind of call to mind when you're thinking about overfitting is also comes from Pedro Domingos's paper, which is this distinction between bias and various variance, excuse me. So in the underfit case, right, you, you're missing the mark, you're not describing the data very well, but you might have, uh, low variance, you know, you're, you're clearly missing the mark. And then, you know, high bias and high variance, well, then you're sort of just way off the mark, you haven't, you know, your learner is not producing anything useful at all. Uh, but in the overfit case, you might have very, very low bias, but you have, uh, high variance. Now, the way to interpret this language I'm using, the high variance is, is variance when you, when you add more data or when you perturb the data or when you evaluate on a different data set, how much, how what's your quality look like? Right, how well do you do? Okay. And so if you have low B, so if you have low bias on your test set but it's sensitive to the data, right, that's where the high variance comes from, then you're in an overfit scenario. Okay. And in the other case, well, you're, you're not very sensitive, uh, to the data, you have low variance, right, but you're bias, but you have high bias, you're wrong, you're getting the wrong answer. So this is like if I just have a model that's always predicting, you know, let's say I have a model that says every, on the, for the Titanic data set, that everybody dies all the time. Well, this is very insensitive to the data, right? It has, uh, low variance, right? No matter what data set I give it, I, it always produces the same answer, but it has high bias, it's wrong, right? The, the error is, is, is high, while overfitting is the other way around. Maybe I get an exact answer on my training set where I have very, very low bias, but as soon as I add one more data point, it, it changes, uh, drastically. Okay. So this is another, um, set of terms and kind of concepts to think about when you think about overfitting. All right. Okay.

So we talked about overfitting, but backing up a step, we need to talk about evaluating a model and seeing how good it is. So we've touched on this when we talked about rules, we touched on this when we talked about decision trees, but I want to go over the main terms you need to be familiar with. Okay.

So maybe the most important thing to take away from this entire segment is about dividing your data into training sets and test sets. And so when you work on Kaggle, you'll be given a training set and a test set, but you should take the training set and split it again. Okay. So, so this may seem somewhat obvious that you can't evaluate on the same data that you're training on because, of course, you'll do well, but this actually wasn't all that, uh, clear to people when they were first exploring some of these machine learning approaches in the 80s. It actually took a little while to sort of align what the statisticians already, you know, would have realized with the sort of algorithmic, uh, approach that the machine learning crowd was exploring. Okay. So this is absolutely critical, right? It means it's, it's meaningless to evaluate a model on the same data you trained it on, absolutely meaningless. Okay.

So how can you do this? Well, one way is to just set aside a certain amount of data, a certain percentage as the test data and leave it at that, and then do all your training on the training data. But a somewhat more aggressive way is to do cross-validation, which is, uh, leave out a certain amount for testing, but then repeat that, right, leave at a different, leave do another random sample, um, and evaluate on that. Okay. So say 10-fold cross-validation would say leave out 10% as test data, train on the remaining 90%, right, evaluate on the set aside data, and then repeat. Now, k-fold tends to mean that you're going to split this into, uh, chunks ahead of time as opposed to actually doing a random sample in each case, but both are valid and they have some, they have somewhat different properties. Okay. And we're not going to go into a lot of, a lot of detail on this. Okay. So, and 10% is a reasonable number to think about. A special case of this method is leave-one-out cross-validation, which is take a single element from your data set, set it aside, train on the remaining, uh, records, the remaining data, and then evaluate on that one set aside data, data point to see if you classify it correctly. Now, repeat that on every single data item in the set, and you'll have a pretty good idea of how well you're doing overall. Okay. And this also has some properties, uh, both, both good and bad that we're not going to go into a lot of detail. And then finally, a related concept that I do want to go into a little bit of detail on, in, in a bit, is, uh, the bootstrap, where you take a data set and you resample from it with replacement, so you may generate duplicates, and this has some very nice properties for statistical analysis in general. So any statistic you derive from this bootstrap set of samples, uh, turns out to be a very good estimator of the actual population statistic. Okay. And we'll go into that detail in a little bit. Now, I have one slide on this leave-one-out cross-validation, uh, just because I want to make a point about where this came up previously in this course. So again, for each training example XY, where Y is the class label and x, x is a set of all the other attributes, right, we just sort of lump them together and assume for notation purposes, train a classifier with all the training data except this one particular value XI, and then test the classifier's accuracy on XI, does it get it right or does it get it wrong? Okay. And then the leave-one-out cross-validation accuracy is the average of all the other, of, of your performance on all the set aside data. Okay. And so the place we saw this before was in the Twitter assignment where one of the recommendations to debug and evaluate your term sentiment model, not the tweet sentiment model, but the term sentiment model, was to, uh, take one of the terms out of the a.txt file and see what sentiment your model predicted for that term, and you could broadly just make sure that it was sort of positive when the a in that it was positive and negative when a in that it was negative. Okay. And of course, this was sensitive to the exact tweet data set you were working with, uh, but it would be a good way to sort of sanity check and make sure that you're producing the right values. And so one of the challenges, if you remember, was, well, the a.txt file covered a lot of obviously positive and obviously negative words, therefore you didn't, didn't leave you a lot to, uh, test with, right, because a.txt was one of the inputs. Well, that's okay, using this leave-one-out cross-validation, it is one of the inputs, but leave something out of the quote training set, even though we didn't think of it as really training a model, but in some sense we were, uh, leave one out and then see what value you predict for that one that you left out. Okay. And you could do this, you could do a k-fold cross-validation as well, but leaving out a whole bunch, but, uh, just one maybe was, was with the recommendation that came up in, in the discussion forums. Okay. Okay.

So what we have talked about is just measuring accuracy, and we mentioned this term confusion matrix before, we showed this when we were looking at, uh, the rule-based models. So going to a little more detail here, if you are looking at a two-class model, you've got predicted positive and predicted negative as columns, and the true positive and the true negative as the rows, then you can put the numbers in this matrix, and the blue numbers are what you got correct, and the red numbers are what you got incorrect. Okay. And so A is the true values that you predicted to be true, and the, uh, D is the, uh, true negatives that you predict to be negative. Okay. And so here accuracy was, well, just add up everything you got correct and divide it by the total. Okay. So this is straightforward. So why not use this all the time? Well, you know, in many cases this isn't necessarily enough to really tell you anything. So, so how do you interpret 90% accuracy? Is that good? Is that bad? You know, what is it? Is 99% accuracy really, really good? Well, it depends, it depends on the problem. And so you need some kind of a baseline to compare this with, at least, or you need to use a different measure. So possible baselines here is a base rate, uh, and you can define this by just trivially predicting the most frequent class. So, for example, in the Titanic data set, this would be, uh, everybody survived or everybody, uh, did not survive, depend on which one was more frequent, and I don't actually remember the top of my head which one was, um, at least in the trainings that we were looking at. Okay. So take the most frequent class and just assume that that applies to everyone, and that's the one you're trying to beat. Okay. Another baseline is just sort of the random rate, which a lot of times you could sort of assume is 50% for a binary class, but you might actually apply prior knowledge, and so you have a little bit more nuanced probability, probability distribution. For example, if you sort of know that, um, 60% of the passengers didn't survive, you could take that as your baseline. Okay. And in some cases may even get complicated, you have some sort of complicated model, you may need to take your prior knowledge and sample from that distribution and so on. But fine, so some sort of randomized, uh, baseline. And another one might be, uh, a naive baseline that's a little bit less naive than the base rate and not necessarily random but uses a little bit of domain knowledge. For example, take some kind of simple default or pre-existing model that you would come up with without having to apply any kind of sophisticated technique. So, for example, all females survived, right? You need some sort of a baseline to compare against, and you're, so you're measuring how well you're doing relative to that, and this comes up actually in the Kaggle competitions because many times they're, you're given a starting point solution. Okay. And so you want to measure accuracy relative to that as opposed to accuracy overall perhaps.

Okay. So there's a few other performance measures that are computable from the confusion matrix, and I just want to flash them up briefly so that they're included in the slides for reference, but I'm not going to spend a lot of time on them. So one is this notion of lift, which you'll see sometimes in the marketing literature. Another is precision and recall, which are concepts borrowed from information retrieval. And the third is the, uh, ROC plots, these receiver operating characteristic plots, which is a historical term. And here they are trying to capture these two notions of sensitivity and specificity. Okay. And so sensitivity is the, is the proportion of true examples you got right, and specificity is the proportion of false examples you got right. Okay, one class and the other, survived and not survived, and each, um, you know, test case generates a single point on this curve, but in many cases there'll be a threshold that you can set to carve out an entire curve as opposed to a single point. So, for example, if you've got a model that says, you know, creatinine levels in the blood determine a diagnosis, well, what should the threshold, how high is too high, how, you know, how, how should the creatinine levels be before you make the certain diagnosis versus the other diagnosis? Okay. And so if you set, if you change that threshold, what you'll do is, uh, carve out a curve here. And so the point here is that there's perfect, is a perfect classifier, excuse me, is up at this point, right? It gets everything right, it makes no mistakes, and a random classifier is this red line in between, and these curves are more often in between these two. Okay. And so you can measure the area under this curve if you want to try to get to a single number. [Music] Okay. Right.

So we talked about cross-validation to break your data set up into pieces in order to validate your model, uh, and in general splitting things into training sets and test sets, which is crucially important to make any sense whatsoever. And a, but a related notion here is, uh, resampling your data set, or maybe more general notion is to resample your data set. And another use of this is the bootstrap, which is a very, very general and very, very powerful technique coming out of the statistics community, uh, in 1979. Um, so here's how it works: given a data set of size n, you draw n samples from that same data set with replacement to create a new data set, then repeat this a whole bunch of times. Now, what you have is a bunch of different sample data sets drawn from the same population, you can compute whatever statistics you're interested in on each one of these, or you can train a model, which is the context we're talking about, uh, and you can interpret each of these as a, a sort of individual experiment. And this is exactly what the frequentist perspective calls for, right? If you remember the definition of a confidence interval, it says that under repeated experiments, 95% of the time this confidence interval will contain the true mean or the true whatever statistic you're interested in. Okay. And so this is giving you a direct simulation of that, uh, interpretation of, of the statistics. Okay. And so this is a fantastic use of computational resources, right? It means you don't have to sort of have this precise analytic model of the world, of what's going on, you can just rerun experiments. And in 1979, this seemed like, wow, this is going to be very computationally intensive, it's not really fusible. Now, for most of these data sets, it's absolutely trivial. And so this is a, a very, very powerful technique. All right.

So here you see an example of this, it's probably pretty clear, but I just want to make sure you see how it works. Imagine that the original data set you're given is just 1, 2, 3, 4, 5, 6. Then you're going to draw multiple samples from this, uh, simple data set with replacement. So you might get 4, 3, 4, 2, 1, 6, and you notice four came twice, 2, 3, 6, 1, 3, 5, and three came twice, and so on. And now for each one of these samples, you can compute the statistic you're interested in, say just the mean, and what you'll get is an unbiased estimate of the true, uh, mean. Okay. So great, so that's a pretty trivial case. If you have a more complicated data set like this and you want to do a slightly more complicated statistic such as fit a regression line, what? Well, same thing, these are all your points, and you can draw bootstrap samples from them, uh, so this is a 100 points, I think I said a thousand, this is just 100 points, draw 100 samples from this data set with replacement, and then refit a regression line to it. And I've done that here 10 times or so, and you see that the, that the line does wiggle because some of these points are missing. So, for example, this, this outlier here may have been missing in some of the samples, some of the bootstrap samples, and therefore didn't influence the line, and so it shimmies around, but it stays sort of confined to the data because you're still drawing from the same sample data set. And so by reasoning about how much that wiggles, you can, uh, compute things like confidence intervals over these statistics. So if you want a 90% confidence interval for the slope of this regression line, just do this a bunch of times, take the fifth percentile, take the 95th percentile, and you've got it. Okay. So this is really, really general, really, really powerful, uh, associated closely with the statistics community as opposed…

To the algorithmic modeling kind of machine learning community, uh, but we're going to see how to use it, uh, for decision trees. Okay.

[Music]

So we talked about resampling, and we talked about the bootstrap, and we talked about cross-validation, where you're splitting your training set into different sets in order to validate your results. So one idea that might occur to you is, well, look, you know, we have all these different subsets of our training set lying around; why don't we train different classifiers on each one and combine their results? Right? So instead of trying to use it to validate one particular classifier, why don't we just make a whole bunch of different classifiers? And so the question that you need to answer is, well, look, can we—does it actually make sense—does it work to take a bunch of not very good classifiers and combine them? You know, will it actually get better? And the answer is not trivial to find out, but it was found out, and the answer is yes. Okay. And so you can average the results of different models, and you get a couple of benefits. One is the strength will go up; the classic classification performance will be, uh, better, and you can drop dve it up by design. But more importantly, perhaps it's more resilience to noise, and so you reduce the chance of overfitting by having a bunch of different classifiers all work in tandem. Okay.

So why wouldn't you do this? Well, there's two reasons: one is it's time-consuming. Right? Obviously, training a bunch of different classifiers is more expensive than training just one. But also, you know, they become—the behavior of your model becomes difficult to explain. Right? When you have a whole bunch of different models all sort of voting on the answer, uh, it's difficult to take some intuition for what, uh, logic is actually being applied. And so remember we said a big—just like one rule was easier to understand than a big set of rules—one decision tree was easy to understand; a big set of decision trees is perhaps not. But that's not going to stop us from doing it. Okay. So the idea here is that there's this wisdom of the crowds model. Well, it works when you're talking about these digital artifacts as well—these, these generated models. All right. All right.

So how do we actually do this? Well, one technique is called bagging, which is a portmanteau of bootstrap and aggregating, uh, and so the idea here is to draw your—in bootstrap samples—retrain the model separately on each sample, just as we described, and then average the results. And so if you're talking about a regression problem that we haven't got a detail yet on, uh, then you would actually literally just average the results. If it's classification where you're only picking a discrete class label, then you do a majority vote. Okay. And so this works really, really well for overfit models; it resists overfitting, uh, because it decreases variance without changing the bias—so without moving the answer around—right? It just shrinks everything to that answer. And if you remember we put up that plot where high variance tended to mean overfit—it means that you're specialized to the training data, and you're very sensitive to the training data. Okay. But it doesn't help much with, uh, models that do have a high bias—with wrong models—and you remember high bias, low variance models are, uh, more or less insensitive to the training data. And so all that you're doing with bagging is taking different permutations of the training data. So if you're not getting a good signal out of the training data at all anyway, this isn't going to help much. Okay.

So another technique is boosting, exemplified by this algorithm, AdaBoost. Okay. So here, instead of selecting data points randomly with the bootstrap, you want to favor the misclassified points on each step. All right. So take a bootstrap sample, retrain a model, see what, uh, exam—inspect the mistakes that the classifier made, okay, and recompute the weights for the next round of bootstrap, giving extra weight to, uh, the example data points that the—your model got wrong. Okay. So let's see what this looks like a little more precisely. Okay. So for each step T, we've got a vector of weights, which represent the probability of selecting example I in the sample. So that's this D. So D at T, D of I is the probability of selecting I in the sample, and these are initialized to equal probability—to uniform probability. Okay. And then X and Y, X sub i and Y sub i are your, um, record and your label. Okay. Been saying data point, example, and record, I think, sort of interchangeably, which probably isn't all that helpful, but bear with me. So H sub t is the trained classifier at step T using the sample drawn according to the weights D. Okay. Now compute the error by adding up all the weights for everything that was misclassified—or this epsilon. I shouldn't say error—compute this epsilon by adding up the weights for everything that was misclassified, and that's what this incantation is down here. Right? So this says for—for the model H sub t, apply it to X sub i where it's not equal to—where the classifier tells you something different than the actual class label, then include it in the set and add up all the—oops, excuse me—add up all the D's for those. Okay. Then compute what's called the odds, which is the odds given a probability is that probability over one minus that probability. Okay. So compute the odds of misclassifying, and then weight those values—those misclassified values—by, uh, the odds. Okay. Oh, excuse me, you're going to—this—that's not quite right. You're going to—this is a—this is a value between zero and one. Right? And so this gives lower weight to D of I, and you're only going to apply this function to the ones that were correctly classified, and all the other weights you just leave alone. And so this isn't—I didn't put that data for in attempt at clarity; I didn't, uh, include the entire expression that may or may not have been a good idea. So this is only applied to the correctly classified examples. Okay. And then there's actually one other step that I also removed in an attempted clarity, which is you need to normalize all these down because what you've done now is taken a set of weights that normalize to probabilities—you know, they add up to one—and you've just adjusted some of them down. Well, now it's not going to add up to one anymore, but that's okay because you know the relative weight. So you need to renormalize all this, uh, and so it's a pretty simple step, but, um, I find when you sort of throw a divide by Z in here it gets confusing, so I just wanted to explain it this way. Okay. And then that gives you your new weights for the next round, and then you repeat this process. Okay.

So a question I want to ask about this, though, given our appreciation for big data and for scale-out solutions, is the difference between bagging and boosting? Well, I guess I should probably promise you—so boosting has a bunch of nice properties, and it's a very, very successful algorithm, um, and one thing that's especially cool about this is that it—it's—it's a meta-algorithm. Right? It works on anything; all it doesn't say anything about what this classifier needs to be; any—could be a decision tree, could be any other method you might come up with. Right? All it does is, uh, affect the data you use to train the classifier at each step. And so this is very, very general and very, very powerful. Okay. And, and you know, because of this weighting it actually does sort of start to, uh, zero in on the mistakes that are made, giving more and more weight to the errors. And so you can sort of imagine intuitively that the strength of the classifier is going to get very much better—better and better over time. So that's well and good, and it works, uh, but it has a disadvantage with respect to really big data relative to a simpler—a simpler approach, just as bagging. And so that is it's inherently sequential. Right? We have this—for each time step, you know, the weights at time t plus one—step t plus one—depend on the weights at step t. With bagging, we can just go wild in parallel and do all of this at the same time. Okay. So that's something to keep in mind that you don't see quite as often in the discussions of these various methods because they tend to focus on the mathematics involved and the sort of performance. But when we keep—in, you know, in a data science context, we need to keep in mind that we're going to be working with very, very large data sets at times, uh, and so a slightly worse performing but easy-to-parallelize method can win all.

[Music]

Right. So we talked about boosting and bagging and ensemble methods and drawing bootstrap samples, and so some of these ideas we can put together and apply them to decision trees in order to create an ensemble method based on decision trees. And one such ensemble method is random forest, due to Breiman in 2001. And so this one is really, really popular and really, really powerful. Okay. So it's a good one to know. So K times you're going to repeat the following procedure, okay, where K is a parameter that you'll specify. You'll draw a bootstrap sample from the data set, and then train your decision tree on that bootstrap sample as follows. So when—tell the tree is some maximum size that is usually set pretty conservatively, you'll choose a leaf node—iterate over all the leaf nodes—and for each leaf node select M attributes at random out of the P that are available. Okay. So you're not going to use all the—you're not going to consider all the attributes, uh, when you're deciding how to split a node; you're just going to select M at random and consider among those. Okay. And then pick the best attribute or split of the attribute as usual using entropy or, uh, other methods, and we'll talk—one more. Okay. So now you have a tree that only involves M of the attributes, and it was derived from only part of the data set. Okay. So now you measure the out-of-bag error. So what's the out-of-bag error? Well, when you draw a bootstrap sample, remember that you might get duplicates. Right? So you have a data set of size N; you're going to draw a bootstrap sample also of size N, but whenever you get a duplicate, that means that some other data item was left out of the sample. Okay. So take all those, uh, data items that were left out of the sample, and that becomes your test set. All right. So now evaluate the error on that test set, and use this for a—you can use this for various purposes. Okay. You don't necessarily need to use it to, uh, make decisions as part of the algorithm, but it's—it's computed on the—on the fly as part of the algorithm, uh, for various other purposes. Okay. So you can do this to estimate the strength, which is, you know, the inverse of the error rate. You can do this to measure the correlation between random trees. Right? So each one of these is sort of a different tree using different—potentially different attributes—and a different subset of the data, but you can imagine that just by chance you might get a bunch of trees that all do the exact same thing and make all the same decisions. Right? This would lower the, uh, power—lower the strength of the overall ensemble classifier, and so you don't want that. And so this gives you a measure of how correlated things are. Okay. And it also gives you a measure of variable importance, which we'll talk about in the next slide. Okay. So finally, at the end of this, you have K trees, uh, that are hopefully more or less independent, and now you can, uh, classify data points coming in by just a majority vote among them all.

All right. So this notion of variable importance. So one of the weaknesses of ensemble methods that we mentioned are perhaps the interpretability of them. Right? So a single decision tree makes a lot of sense. If I have a whole set of decision trees all sort of working in concert, it's a little less clear, uh, what's going on. And so if you're actually trying to use these models to gain some insight about the domain, that may be difficult with a random forest. All you get is sort of the answers out, and they have high accuracy, but you don't really know why it works. Okay. So variable importance is a hedge against this. So the—the idea is that you'll—as an output of running this algorithm—you'll get a measure of how important to the accuracy the various attributes were—or I'm using variable and attribute interchangeably. Okay. So how do you measure this? Well, as you're training each tree, you do this permutation experiment, and we've seen this, um, before—at least I think we have. So you'll scramble the values of that attribute, and what you expect is that once you scramble these, the, um, accuracy—you know, the error rate—it'll—it may change. Okay. And if it's an important attribute, then it'll change a lot, and if it's not a very important attribute, then it doesn't change very much. And so that's the idea. So if you scramble this and the—and the error rate does not change very much, then it must not have been an attribute that was heavily used in the decision tree. Okay. Right. So you measure the error increase after permuting these values, and you can plot for all the attributes in the data set which ones came out to be most important by aggregating these across all the—all the trees. Okay. And so this helps with interpretability of the overall random forest because you get a sense of which ones are really helping to make all the decisions. All right. And so some applications—particular a few places mentioned—the medical applications need to eventually get down to root causes, uh, rather than sort of doing fire-and-forget treatments. All right. Fine.

So one other difference is the, uh, Gini coefficient is often used, and this actually comes up not just in random forests; it comes up in, uh, variations on decision tree algorithms. And so we talked about entropy as a measure of impurity when you're making a decision on each node. Right? You need to decide, uh, which attribute to split on that'll give you the most, uh, reduction in uncertainty. Okay. And so you're looking for choices that'll give you very pure choices to the left and very pure choices to the right. Right? Where if I select, uh, female and male, then I get 100% of the records when I go down the female branch—all survive in the Titanic data set. Okay. So somewhere—somewhere down the decision tree—this—this may turn out to be the case, in which case that would be a—a strong indication to use the gender attribute to make the split. Okay. And so we measured this—precise—we counted out this—this measure of intuitive notion of impurity using entropy. Another way of—another calculation of—of the intuitive notion of—of impurity is the Gini coefficient. Okay. And so this, uh, looks like this. And so if you think about what this is doing, right, you can think about how this behaves—we're not—we're not going to derive this—and there's actually varying notions of how to compute, uh, the Gini coefficient in general—but you think about what—how this is behaving—that if you have probability 0.5, then square that and it'll be plus 0.5 on the other side—say we have a binary class—this would just survive and not survive—then this will be 0.25 plus, uh, 0.25, which is 0.5. Okay. But if you have 0.1—2 + 0.9—well, that's going to be a lot smaller. Okay. So one minus that will be much bigger. Okay. And this makes sense because if 90% of the values are the same—or you know, if—if 90% of the values are one value and only 10% of the other—then this is—this attribute is more pure than something that is evenly split. And so you still got this function that's ranging from 0 to 1 capturing, uh, some notion of purity, and this has the same properties that—has that same property as entropy did. Okay. All right. So now you know both of those methods for—for measuring this—this impurity, and you'll see both of them in—in practice and decision trees and the libraries that—that implement them. All right.

So just a couple of comments about these random forests. You know, one is these are—this is easy to parallelize. Right? All—all that requires is being able to take a random bootstrap sample in parallel, which is usually easy for most data sets. If the sets are very, very large, it can be expensive to, uh, take random samples, but it's still a lot cheaper than training models, uh, sequentially. Okay. And so other than that, the training—the training of the trees can all happen in parallel, and so this scales out really, really well. The other nice feature of this is because you're selecting those M attributes at random, where M is often times a lot less than P—you know, there—only—only selecting a few of the attributes—which makes sense, right? Because if you're having—if you're going to have a whole bunch of trees vote, well, you're going to make—make sure that every attribute in the whole data set will be represented enough. You don't necessarily need to have them represented in every single tree. Well, this is nice because it sort of scales to very large numbers of attributes quite well. All right. And then it has these other side effects of—of being able to generate on-the-fly estimates of its own, uh, accuracy and variable importance and so on. Okay. Great. And so just to summarize this, we're going back to this framework of representation, evaluation, and optimization. You know, the representation here is trees or sets of trees, where the majority vote determines the actual classification. The evaluation of these things has to do with just error rates and accuracy, although we talked about some of the other measures that you might use, uh, and then random forests. We have this out-of-bag error, which is, uh, same thing as accuracy, but it's—but it's defining where you get the test set from. Right? It's left—it falls out naturally from the boot—from the fact that you're taking bootstrap samples. All right. So you don't have to make a separate decision about cross-validation and so on, although I—I should say you should still—this is sort of independent of cross-validation; this is—you know, this out-of-bag error is generated on your training set—you should still—before—before you even walk up to the table—consider how you're going to do cross-validation or how you're going to split your training set into test and training. All right. And then finally, optimization, uh, it's not so much an optimization as in we have a naive algorithm; we improved it with some optimization, but we do have this information gain—Gini index approach to constructively build trees that have good predictive power. Right? So we could take—I mean, see, we say random forests, but it's not truly random in the sense that we're just building random trees. Right? Those wouldn't perform very well. We do better than random by making smart decisions about how to split the nodes—which attributes use—to, uh, split. Okay.

[Music]

Okay. So where are we? We're talking about classification problems and supervised learning. We talked about rules; we talked about decision trees. And then we said the challenge of decision trees is that they are prone to overfitting. And so there's methods for avoiding overfitting in individual decision trees that we didn't really talk about, uh, such as you build them, and then you can prune out parts of the tree and aggregate parts of the tree so that they become a little more general, uh, but instead we shifted to another more general and more powerful technique to avoiding overfitting, which is to use ensembles of models. And so within the context of ensembles, we talked about boosting and in particular, uh, mentioned this algorithm AdaBoost, which is a meta-algorithm, meaning that it works on any, uh, machine learning application; it doesn't have to be about trees, but we talked about it in the context of trees. Then we talked about bagging, which is about selecting, uh, subsets of your data to work on, uh, and bagging relies—itself relies on the bootstrap, which is a technique for resampling the same data set in order to derive, um, estimates of important statistics. Okay. And we put some of that together and talked about random forest, which is an ensemble method for decision trees that has a couple of unique characteristics. Now, I—I went through this—rules, and then decision trees, and then ensembles approach, sort of sidestepping the—well, postponing the, um, regression-oriented machine learning models, and there's a couple of reasons for this: one is random forests do turn out to be a pretty powerful method—a pretty general technique for a lot of—

Things and generality, not just in their statistical power and their sort of efficacy and practice, but also the fact that they work on categorical attributes, the fact that they can handle many attributes, so big p smaller n cases, uh, the fact that they can—there's uh different variations of them that you can experiment with, the fact that frankly they're kind of simple to interpret the results of, and also maybe even simple to implement yourself. You know, hopefully you're armed with enough knowledge where you think you could make it go at this. So I think they're they're actually a pretty fantastic general-purpose approach.

All right, so let's consider a different method that's not rule- or tree-based. B. All right, so that's nearest neighbor classification. So here, this is actually one of the simpler ones, and there's a reason. You know, it it would be reasonable to actually present this first, but the reason I didn't do that is that it assumes only numeric attributes. And I think a lot of the intuitive data sets you work with, especially when you're coming from kind of a u uh, you know, maybe data processing background, data science sort of scenarios opposed to a pure machine learning, pure statistical uh, you know, background, uh the categorical data is quite common. And so defining nearest neighbor is sometimes possible, but it's not it's it's not always very natural. Okay. But now that we've sort of covered the more general techniques they can handle categorical data, we can think about these.

So nearest neighbor is dead simple, right? This is to say uh plot your points in a space like this, where the red squares represent one class and the blue squares represent another—you know, maybe survived or not survived in the Titanic example—uh and when you have a new point that you want to classify, just drop it into the space at whatever point it—the attributes tell you where where it should go—and choose the class of the nearest point to it. Okay. So what's the class of this green triangle? Well, the closest point to it is a blue circle, so we call it it blue. And what's the closest point to this green triangle? Well, that one's a red square, so we call it it red. Now, as you can see in the second case, maybe it's not that reasonable to call it red because perhaps the class boundary is sort of something like this, and this one's you know an outlier, this one's a mistake. And so we perhaps would misclassify this second green triangle.

All right, so the intuition here is, you know, going back to this sort of document classification example, well, the last document I saw that mentioned the word Falcons and the word Saints was about sports, so I'm just going to go ahead and assume that this document is also about sports since it has the same terms in it. Okay. And so this is not the most unreasonable method to use, but as we saw, you know, perhaps it's a little bit sensitive to uh noise in the data. And so another, you know, a simple extension of this is to imagine K nearest neighbors as opposed to just one nearest neighbor, right? So you find the K closest points, and then they take a vote on what class it should be. Okay. And this gives you a little more resilience to noise in the data, um at a cost. So you can ask yourself how would you choose K, right? What should K be? Well, the benefits of a small K are that it's uh fast, and there's less of a bias towards popular labels. And what I mean by that is that if you have imbalance in your data, right, so you have say many more people that survived then didn't survive, then there's going to be a lot of those blue circles relative to red squares, let's say, right. And so therefore the odds that you're going to land somewhere near a blue circle, assuming a certain amount of noise in the data, goes up, and so you'll start to misclassify more and more and more um, you know, as a result. And so imbalance in the data translates into higher error rates. Uh, however, you know, the the benefit of of large K, even though it's sensitive to uh imbalance, is that it ignores outliers, right? You're you're insensitive to the outlier. So choosing a k is perhaps problem-specific, and there's been work on on making this more precise.

Okay, so the other decision you need to make is some kind of a similarity function. And so typically you would imagine just Euclidean distance uh in these in these cases, but another one that might make sense is cosine similarity, which is a measure of the angle between the two vectors. So if you have two points in space, this line D is the distance between them, while the cosine similarity is how far apart they are in the angle. So you have to think a little bit about what the tradeoffs are here. So if I was in the classroom, I would ask you guys, I would wait for some answers, but since I'm not, I'll pause dramatically and then just talk about it. So one thing to remember in general is: When anybody asks what is the problem, what is the disadvantage of Euclidean distance, you should always have the same answer in mind, right? There's one big disadvantage of Euclidean distance, and that is that it's uh sensitive to the number of dimensions. So as the number of dimensions goes up, uh the distance between points is sort of hard to interpret, right, because it tends to go up as well for not necessarily any kind of good reason. And remember that a lot of these machine learning applications will have a very large number of dimensions, right? So the all the all the English words, for example, in the document classification case. All right. So so that's fine, that's the disadvantage of Euclidean is that you have this sort of curse of dimensionality problem going on. The disadvantage of cosine is that it kind of favors the dominant components, meaning that uh, you know, if two vectors are are the same in all dimensions except for one where one where that value is much much higher on one vector than the other, then the cosine similarity is affected less by that than the Euclidean distance. Let should try to draw this real quick. So if I've got a point here and here, and then I've got a red point here and way up here, then the angle to the blue is that, while the angle to the red is that, and so this distance is relatively less sensitive to this increase than Euclidean distance, where this point and this point are much further apart—are sort of linearly far apart.

Okay, so what what this translates into is that uh you'll tend to be more similar [Music] to uh neighbors who have a very very large value in one in some dimension. Okay. And that can be a good thing or a bad thing. So in one paper they talk about sort of this being a good thing for image retrieval because if you have very uh striking features in terms of say color composition of the image—so this is like, you know, you've got a query image and you're trying to look for other similar images, and you extract a bunch of features from the image and you try to find similar ones, and then you want you want the K nearest neighbors—then say you have very strong red and brown or red and blue kind of colors in your image, then you're going to find things that have uh red and blue, but perhaps less extreme, right? Okay. So so lower magnitude but still red and blue is uh should be a returning the results, while you know close in magnitude but in a different dimension, you know, so so about the same magnitude intensity but in uh green and yellow is perhaps less similar in that application, but this is all very application-dependent.

Okay, so one final point I want to make about this is this—you this notion of Euclidean distance and sensitivity to the number of dimensions. So this is random data, normally distributed with some variance of I don't know two or one or something like that. I guess a little more than that, probably more like four or five, um and just taking two points in a d-dimensional space where D is going from zero to a thousand. So give me a random point in a in a 500-dimensional space, and give me a random point in a 500-dimensional space and measure their Euclidean distance. Okay. And so you can see the Euclidean distance is sort of going up with respect to the number of dimensions, even though the random distribution from which these points are drawn is the same. And so as the space sort of expands exponentially, uh things get for sort of further and further apart. Okay. And so this may or may not be the effect you want when you're trying to measure similarity in a high-dimensional space. All [Music] right. All right.

So we recap of where we are: We talked about supervised learning, uh talked about deriving rules and arranging them into trees; we talked about how those trees are susceptible to overfitting, and we talked about one way of combating overfitting is to use ensembles of weak learners and combine their results to form a strong learner, and gave one example of this in random forest. We also mentioned that one disadvantage of these ensembles is that they become pretty difficult to interpret, right, because it's a big vote among a bunch of smaller models, and so you're not not quite clear where the decisions are coming from. And random forest had one way of attacking this in that you build the random forest; it was producing an importance measure for the variables, right? So if if particular attributes were more influential in the decision, you would get a measure of this uh as as one of the outputs. And then we talked about K nearest neighbors, which was a change in that it used numeric attributes, and continuing that we're going to talk about uh gradient descent and some applications of it. Okay. So this—if you remember the three components of a machine learning solution—is the representation of the uh model, the evaluation of that model—how you tell how well it's doing—and then how you optimize the process. And so the gradient descent is an optimization method that's applicable in a lot of different contexts that we'll touch on at the end.

Okay, so in a nutshell, what you're doing here is expressing your learning problem in terms of some kind of a cost function that you want minimized, and starting at some initial point, you're going to, you know, roll the ball downhill until it settles in uh a trough. And so this process describes how to walk downhill; it's not really a roll, right? You're going to take steps, and that turns out to be one of the difficulties with with gradient descent. Okay. And so some situations you can sort of design—offer a guarantee that the minimum you find will be the global minimum; other times you don't. And so getting trapped in local minima for more complex problems that we won't go into too much detail on um is is another potential weakness of this method.

Okay, so the problem we're going to be thinking about here is no longer classification, although we'll mention how you can use this for classification uh at the end, but we're going to think about just regression. Okay. And so regression can still be used as a prediction task, and we think about sort of fitting a line to uh data, but the point is you might use that line in order to make predictions of the outcome value—you know, the response variable—given the inputs uh down the road. Okay. Regression line is a predictor. Okay. So rather than a rather than a discrete class variable, we maybe talking about a response variable that's continuous. Fine. So in this case we'll take the—you know—very simple case of just a single input variable, but in in in throughout this we're going to be thinking about an entire vector of input variables, and that vector you can think of it as a row in a database. Okay.

All right, so imagine we have these points scattered this way, and you can see that this is a pretty cleanly produced data set where there is kind of a regression line that exists that that probably describes the data pretty well. And in fact, that's not a surprise because it's sort of generated to have that effect for illustrative purposes. So the process here is we're going to imagine that there is uh that we split the data first into uh a training set and a test set, and that's always the first thing you want to do if it hasn't been done for you already. And here we just split them half and half, and we we talked a a couple of segments ago about various ways to do this, but here we're just going to train on one half and test on the other. And further, I've scaled the data uh so that the original domain here of you know -10 to 60 or really 0 to 60 and some some kind of range of 0 to 600 is scaled down to uh variation around zero. Uh this is actually a little suspect what I did here because I scaled the data all at once and then split it into training and test data, and so the test data sort of influenced how the training data was scaled, which is typically a no-no. Okay. So you may want to scale them sort of separately.

So how does this gradient descent work? In this plot, what we have is the two parameters for the regression line, which are Theta 0 and Theta 1, and it's the Y intercept and the slope essentially, right? These are the two parameters for a single line. This is the equation down here. I refers to the iteration number. Okay. So this is really iteration zero that we're looking at, or really difference iteration 0 and 1. So we started this process off at this point, and we picked that point randomly. All right. And there's various deterministic ways to choose a starting point, but in general the fact that you have to decide a starting point is one of the weaknesses of gradient descent. Okay. So we start off at a single point, and then we found the direction of steepest descent and took a step in that direction. So the cost function here that we're trying to minimize—this says that the response variable y minus the function applied to the input variable, and here the function is just a linear regression of intercept plus slope—take that difference and square it, and add them all up for all the data points, right? That's the total amount of error that you received by trying to by trying to explain all the data with this with with this particular regression line that we started off this first starting point. And so we compute that gradient, and I haven't shown on this slide how to do that, but you complete that gradient and jump down quite a bit, right? The error goes down a lot in this first step as we as we walk from here to here in this parameter space. So now we've gone from one regression line to another regression line. Here's the first regression line that we started with, and we just kind of got lucky that it already is kind of in the right direction; we may not have—it could have gone this way. All right. So the next slide, we take another step, and the air goes down a little bit more, and we take another step towards this the minimum over here toward the center, and we've got another regression line that has rotated slightly, so it's closer to what we intuitively think will be describing the data, and we can keep going with this and keep stepping down, and the regression line gets better and better and better; the error goes down, right? We're finding a local minimum in that error until it—we decide that it converges when the the difference between the uh error in iteration I and the error in iteration I plus one is less than some threshold. Okay. Then we decide that it's converged. And in fact, in this case, it looks like it did pretty well and that it got what we is sort of the minimum here, and this line looks like it describes the data pretty well, which we can see on the next slide. So again, you know, each one of these lines—this line is perhaps the slope and intercept, right? These two parameters Theta 1 Theta 0 and Theta 1 from iteration one, while this next line is the Theta 0 and Theta 1 from iteration two. Okay. So at each step we form a new line, test how well it describes the data, and proceed. But what I haven't said is how we figure out what direction to walk in nor how far to walk. All right. So let's think about [Music] that.

So how does this work? So each parameter is going to be updated with a new value derived from its old value plus taking a step in the direction of the gradient. Okay. And so in these plots, you know, remember this is the coordinate pair Theta 0 Theta 1, right? That's the space we're in, and at iteration one the point is here, and at iteration two the point is here, and iteration three and so on. Okay. So in order to get iteration I plus one, we're going to take iter—the same value—the value of the parameter iteration I and add this offset term. Okay. So what's going on with this offset term? So this is the learning rate, which is just the step size—how far are we going to go in that direction? Okay. And this is usually a small value, you know, maybe 0.001 or something. Okay. But it's really—it's application-specific; it's it's a bit silly to even state what it should be. However, I didn't notice that in this example I did scale everything down to a value, so 0.001 on scaled data may not be an unreasonable thing to use as a default. And so this operator is the partial derivative with respect to Theta 1, and if you remember, you know, a little bit of college calculus, the sum of these partial derivatives is the gradient, and so we're just doing one of these partial derivatives with respect to one particular variable. Okay. And then J is our cost function that I haven't shown yet, and J will be a function of these parameters as well as a function of our data set, right? We're going to take these parameters plus all the data set and compute some new cost. So blowing up J: So this is our model at iteration I, right? Remember we're trying to compute the new value of the parameter i+1, apply that model to the data instance X, subtract the—you know—the true value, the correct value Y, and that's our error; square that, and then add it all up for all possible values in the data set, which is what K is, right? So we're going to run over all of our data points, check the difference, square it, add it all up, and—well—the value and actually divide by two here, but that's more just to make things work out. So you'll see that u a lot—it's divided by a constant factor, so it doesn't actually change the um direction at all. Okay. And so now we just need to differentiate this with respect to uh the parameter that that we're updating—in this case Theta 0 or okay. So this is, you know, elementary college calculus, but just to show the steps on one slide uh, you know, push the partial derivative through the sum, and then apply the chain rule to get this two factors, and then remember that H—our model—is actually just a linear model, so we're multiplying the x value times the slope parameter, adding in the Y intercept, and the only term in here that involves Theta 1 is this Theta 1 * XK, so the other ones don't involve Theta 1 at all, so we can just drop them; their derivative is zero. And so this just simplifies to XK itself. And so h of XK minus YK * XK is the uh update rule that we're looking at. So this is just sort of putting the starting point and the final point together on on one slide. So the overall update rule looks like Theta I + 1—al Theta I plus the learning rate times the sum of the value that we predict for XK minus the true value times XK. And so overall what you say here is: While not converged, apply these update rules; update Theta 0 and then update Theta 1. Okay. And then check for convergence. And so that's the program that you that you could write if you were going to implement this uh by hand. So one one detail here: Why is Theta 0 for this—Thea Z—why don't we have this multiplied by XK? Well, the reason is is that because it's the Y intercept, there's not an x value to multiply by, so it's actually just assumed to be 1.0. And in fact, you can think of this as adding an X3 if you've got a single attribute, right? Our X—our X—our X values—we're trying to predict y from X—we can think of there actually being two attributes, one our…

X values and the other one being a constant attribute where every single instance in our data is just the value 1.0, so it has no effect on uh the learning, but it allows us to have, you know, an X variable for every parameter. So there's sort of a trivial x0 right here, and you can assume that x0 is always one. Okay. In which case it would also appear out here.

So some questions that arise here, you know, there are some still some parameters to this process that have kind of leaked in right. There's this initialization step of where we decide to start the process, and we have to choose that point by some mechanism. Okay. So you might have sort of small random values, or you might pick always the same point, and random as usual gives gives you a little bit of robustness. Okay. Then you also need to decide the step size, and this procedure is, you know, notoriously sensitive to choosing a step size. So if it's, you know, we don't really roll we're not doing a kind of a continuous fall down the gradient, we actually have to jump, and so we have to figure out how far to jump. So if you jump too far, you might actually skip over the minimum and come up with a higher function value than a lower one.

And so some of the methods to um decide this learning rate will adapt based on how much of a difference you've what how much of a difference in the air rate you've gotten. So if you're rolling on a relatively flat period, you might take a bigger jump, while if you're going through a regular steep period, you might take a a smaller step. Okay. In order to in order to sort of keep approximately constant the amount of gain you get in in the air. And so that's one trick you can do to sort of avoid this decision about the step size; otherwise, you people sort of tune it an application-specific way. Okay. And if it's too small, then you'll sort of fall in the gradient, but you'll take a very long time uh to get there, and you have to also doctor in the convergence test as well, you know, whe whether it's about the threshold.

Okay. So what's the point of all this? Well, the cost function is actually pretty general; there can be almost anything, and the model parameters can be almost anything uh as long as the cost function can be differentiated, so you don't get sort of stuck in discontinuities as you're rolling down the gradient. You can use this to optimize a lot of different problems. Okay.

So a couple of other examples that you'll see in machine learning contexts are these logistic regression and support vector machines, and you can use gradient descent with these methods. We won't have uh time in this course to go into these in much detail, and there's plenty of great machine learning courses out there, but I do want to give you intuition for these two techniques so that you sort of call it calls to mind, you know, an image in your head when you hear the terms. Okay.

So for both of these these cases, you have our vector of weights like we had before, and we have a vector of instance values from our training data just like we did before, and here we're expressing that as kind of a dot product of two of two vectors, and we in some cases we need to use the trick where you ained a dummy attribute with just constant values of one in order to make this dot product work out, but other than that you've got this kind of setup with with these two, and I won't go through these in detail except to call out this funny term over here; we will we'll talk about what that's what what purpose that serves in a bit. Okay.

So logistic regression, just a quick intuition for what's being accomplished here: if you try to take our regression procedure that we just described and apply it to say the Titanic data set that we were looking at previously, you might end up with something like this. Here I've got the x-axis, which is age, and I've scaled this data down so it ranges between sort of -2 and three as opposed to 0 and 85 or something, which is the ages of uh the passengers, and on the y-axis is just zero if they did not survive and one if they did survive. Okay. And now if you just run regression, you know, maybe we could say, well, hey, look, we're going to we're going to create a line and then use that regression line to predict whether someone lived or died. Well, this is the regression line that the the gradient descent procedure finds. So what does this really mean given this kind of categorical data that's been, you know, embedded in in a in a numerical context? Well, not probably not much, right? It's not clear that we would really use this line to predict anything.

So with categorical variables, even if we kind of give them a numerical interpretation, regression doesn't make necessarily a lot of sense. However, there's a function called the logistic function that is this guy, and it has this nice property that it can map values from negative infinity to infinity onto the range 0 to 1, so it gives them kind of a probability, and you can interpret this like a probability so that very very high values are interpreted as increasingly likely uh events, and so you can use this for classification, right? So now instead of a one or a zero, you get out a probability of it being one or a probability of it being zero. So this has a nice interpretation in terms of probability; it allows you to take a linear combination, well, let's say a linear combination of variables to produce a number and assign that to a class in in in in a reasonable way. Okay. And so the cost function is constructed using the logistic function in such a way as to maximize the probability of a correct classification, and and then given these exponentials, it's sort of an easy function to work with mathematically, and this is what this is what it looks like if you if you plot this. So that's the goal of of logistic regression is to give you a way to uh work with probabilities in this optimization context, and in particular you can think of it as useful when you have a categorical output variable and you still want to use these more numerical techniques.

So what's a quick intuition for support vector machines? So the idea, the context here is finding a line that will separate the two classes. So here we have red dots and blue dots, and this is maybe where passengers survived and when they didn't survive, and we're trying to find a line that separates them. It won't always exist, and we'll handle that case in a second, but imagine for a second that they do that it does exist that there that you can draw a line, a straight line, that will separate the blue ones from the red ones. Okay. And so we want to find this line. Well, there's various techniques that we won't go into that can walk through and find such a line, but you can imagine that the best such line is one that is in the middle, and how do we define the middle? Well, you can define it maybe by maximizing the margin between the blue and the red; it's the one that maximizes that margin, and so you can write that notion of a margin down precisely, and what you come up with is that cost function that we showed for support vector machines.

Okay. That's great. Now what about the case where it's not linearly separable? Well, what you can do is uh try to strike a balance between finding a line that gives you a nice fat margin versus one that perfectly classifies the points, and this allows you to maybe find an alternative to this line. So this line does actually separate them linearly, but the margin here is very very skinny, and so you might imagine that maybe this one's an outlier and should not be considered as part of the, you know, should not be considered a red dot for purposes of classifications; if you should be consider an error, and so maybe that this line separates all the rest, you know, say we have a lot more blue ones and a lot more red ones on either side of this line, maybe it does a pretty good job overall of classifying, and it also has a fatter margin; maybe we take that one. Okay. So how do we add that term in to in order to strike this balance? Well, we'll come back to that in a second, but that's that regularization term.

So for those cases that are not linearly separable, you can also soften the definition of margin to allow for misclassified points using what are called slack variables. So fine. So these techniques handle, you know, sort of the outlier noise cases, but in some cases there might be a pattern to the data where it's not linearly separable, but it's not because of noisy error; why it's not separable is because the pattern is not uh, you know, the the two classes are not defined by a straight line between between them. And so if we don't, you know, we don't think about the 2D case now, think about just the 1D case: if we've got a group of blue points here in 1D and a group of blue points here in 1D and then in between them a group of red points, well, there's no one point I can draw that will separate these guys, but clearly there's kind of a group here. What we want to do is sort of draw a circle around this, and so another capability that the formulation of support vector machines allows fairly naturally is to map the data into a higher dimensional space by applying these kernels. And so for example, here we map all these 1D points into a 2D point onto a parabola, and then we can draw a straight line between them. And so this allows you to turn kind of a nonlinear surface into a linear surface so that we can use the same technique, and again I'm not going to say too much more about the mathematics there; I just want to give you that uh intuition for why these are are are a pretty strong workhorse in machine learning; they're they they they're pretty general. Okay.

And so going back to our Titanic example, we can see some uses of support vector machine. So here is the linear support vector machine learned on this Titanic data with the with where the attributes I've chosen are P class or remember class being first class, second class, third class on the ship and gender, and remember that uh red is is did not survive and blue is survived, and also remember that I that I I added some noise to the data just so you could see the blob of red and the blob of blue; otherwise, the the points would be at exactly one, you know, right here in the middle and right here in the middle and so on. So here it finds the line straight between male and female and decided that that was the best linear classifier, which makes sense, but here learned a more complex surface where it's grouped the first-class females and second-class females and decided that they survive, and then it split the third-class females. Okay. And so if we choose two different attributes in the Titanic data set, but given that those were fairly simple categorical data, here is age and first class, second class, third class, and again with the radial basis functions as a kernel and the support vector machine learns a pretty complex surface, right? It it and everything here in yellow is uh survived and everything in in dark blue is not survived, and so it, you know, kind of found this little patch over here where it seems to think, you know, because of these two blue dots that second class and third class and older people from second class and third class must survive in this little narrow range, and I found this one up here that a very old person from first class did as well, but this sort of should smell like overfitting to you, right? When you get this this complex of a surface in data that, you know, we can sort of look at and see that it doesn't have that much of a pattern going on, this this might suggest that something's something's up. And so, you know, as usual, there's other parameters you can tune on these learning methods to try to avoid uh uh overfitting. Okay. And so in these cases, there's u a way to balance the complexity of the surface versus the number of misclassified points, and so here's a simp here's where we kind of dialed in those parameters in this particular library using which is which is Python's uh scikit-learn. Okay. And so this is a simpler boundary surface between survived and not survived that perhaps has better generalization properties, right? It it'll it'll work better if we were trying to actually predict on the test data. All right. So next we'll talk about regularization, which allows you to B strike this balance between simplicity of the model and the classification error.

All right. So going back to the cost functions, we're now ready to talk about this regularization term, and to motivate why this is needed, you can think about these high-dimensional problems. So image classification would have a separate attribute for every pixel in the image, and so there might be millions of those, or these uh text and analytics problems where documents are represented as vectors of terms; there might be 500,000 different terms that may or may not be in the document, and so each one of those gets its own uh weight. Okay. And so with all these attributes, with all these weights, with all these variables, it's likely that many of them are going to be correlated. So for example, two terms tend to appear together in a document and tend not to appear together in a document, or, you know, as in this example, pixels an image: if you look at a pixel on an image and you look at nearby pixels, they're likely to be the same color, right? If you pick a picture pixel in the green field, the nearby ones are also likely to be green; if you pick a pixel on the black cow, then the nearby pixels also likely to be black. Okay. And so there's a problem here because as we're training the model, one way to change the weights significantly and yet not really improve the error much is to make one of these pixels get a very very high weight and the other nearby pixel will get a very very low weight, and so they'll cancel each other out, and the error doesn't improve much because they're so highly correlated. Okay. And so here in the, you know, what's going on here is the model is becoming more complex in some sense, right? It's getting very specialized to your particular problem, but you haven't actually learned anything, right? It doesn't it does it's not going to generalize well, and so you need to have some sort of a condition on: well, all else being equal, we prefer simple models, and maybe not even all us be equal, even even if it makes us misclassify some um some of the images or some of the documents, we'd really prefer simple models because we know that those tend to generalize better than something that's, you know, over fit over specialize to our particular data sets. And so this regularization term provides this balance.

So let's take a quick digression on norms. So a norm is any function that assigns a positive number to the input with the condition that the the only one that's allowed to have a zero value on the output is zero itself on the input. Okay. And so you've seen these before, right? This is the uh L1 norms and L2 norms that are just, you know, the magnitude of a vector, right? Is it is its L2 norm, right? You add up all the you add up the square of all the values in the vector, and you take the square root of all that; that's a norm, and that assigns a positive number because you've squared it. So L2 norm is perhaps the most common, but L1 norms are perfectly valid as well, and in fact you can generalize this to LP norm, which looks like this: the notation is these pairs of vertical lines, and it means take the sum of all the members of the set from 1 to n, raise them to a power of p, and then take the P root of that sum.

So let's put one more digression on the stack here and talk about cost functions. So we make a prediction, and we have our true known values; we want to uh somehow compute a a single number number that summarizes the mistakes we made, summarizes the amount of error. And so the the simplest one that we don't tend to use might be this, right? Just subtract your value, subtract the true value from your predicted value, and add add those all up. Well, this is not usually what you're going to want because, you know, if you're above the value or below the value, you might get canceled out and look really really good; you might look like you've done a great job. Okay. So that's not a good choice as in as a cost function. Another one that is reasonable as a cost function might be: well, look, let's just solve the problem and take the absolute value of this difference and add those up. Okay. And so this is sort of asserting that, you know, one error of seven units in one on a particular data item is just as bad as seven errors across seven different data items of one unit each, and that may or may not be true in your application. And then the error function that we may be seen more is to square the error, and so this is asserting that one error of seven units is as bad as 49 errors of one unit, except for the fact that perhaps we take the square root. Now a lot of times we don't take the square root, and we just divide by n, or we even divide by two in some cases. Okay. And so this is the average squared error per data point; might be useful in comparing methods that filter the data in different ways so that you get the amount of error per data point as opposed to having the factor of how much data was in there influencing the number, but all of these might be reasonable functions, and want to point out that these in fact are the L1 norm and the L2 norm. Okay. They have sort of a natural interpretation of of why you might want to make things positive because maybe you're adding up the errors is why you might want to want to mapping to strictly positive numbers, and they also point out that this one wasn't very good as error as an error condition, but also it's not a norm because it might produce a negative number. So fine. So this is why these norms come up in different contexts; pop cost functions off the heap and go back to regularization. Well, different uses of these norms to control the complexity of the model correspond to different techniques that you'll see in the machine learning literature, and we're not going to go into a lot of detail here, but it's so what we're doing here is we're coming up with a penalty that adds into our error the absolute value of all the parameters, say in the L in the L1 norm case, and so this means that high values of parameters, positive or negative, will increase the cost, and so the optimization procedure will be incentivized to to keep that down, and same thing with the L2 norm; it's it's also mapping to a positive number, and so it gives this penalty to increase the cost when these parameter values get out of whack, either too high or too low. Okay. In some cases, you'll see the squared L2 norm, which is just the L2, you know, sum of squares without the without the square root, and so there's an enormous amount of work on understanding the properties that these choices have on different types of problems, and we're not going to get into that uh here, but I want to make sure that you walk away with with the intuition for why regularization was important, and which is to avoid overfitting and penalize complex models to get those complex surfaces like we saw with the support vector machine uh and what some of the regularization terms are, which are these L1 and L2 norms.

Okay. So going back to gradient descent and looking at it as an algorithm, you know, we may notice that we process the entire data set on every iteration. In order to estimate a parameter, we use the old value of that parameter, and we modify it by the error estimate computed on the entire training data set. Okay. Use that to estimate the gradient. So a very and this is this is infeasible for large data sets of the variety that we will encounter fairly frequently in a data science context. Okay. So a variation on gradient descent is what is called stochastic gradient descent, and stochastic as usual means probabilistic, means we're going to be selecting something at random, and

So, in this case, we select a single data point from the training set and use that to estimate the gradient, as opposed to the entire data set. All right. And so we just continue on in that iteration as if that one data point was our entire training data set. And on the next iteration, we select another point at random, and so on. Okay.

So, in the what you'll be doing here is your estimate of the direction of the gradient won't be as good because you're only considering one data point, but your uh be able you'll be able to compute that iteration much much faster. And so you'll get through more of them, hopefully. And so I'll compromise between these two extremes: using the entire data set and using just a single value is what some call Mini-batch gradient descent, where at each step you pick a small subset of points as opposed to just a single point, as opposed to using the entire data set. And then just continue on as if that subset was your training data set.

And so I think all three of these methods, when you look at this algorithmically, are really pretty simple, intuitive variations of each other. Now, they do have some different properties mathematically and statistically, which is why there's been a ton of work on them, but just as from a programming perspective, they're pretty minor variants of each other, and they arise in a fairly natural way, just in an interest of almost a performance optimization. Okay. And I'll come back to that point in a moment, but first let's look at what this kind of an effect this change has on the procedure.

So, here's an example of where, you know, I modified this gradient descent program that produced these plots to use stochastic gradient, where we just picked a single value. You can see it kind of as it walks down the gradient; it kind of wanders about a bit more and doesn't always find the exact correct direction. And so it might take more iterations to get there, and also the error is kind of jumping around at each point. Now, I wouldn't read too much into this particular example, and you know, if you run this a bunch of different times, you'll see a bunch of different patterns; some of them will converge in just a few steps, and some of them will take a lot longer, and so on. But it does give you a flavor of the kind of cost to using this method, where it doesn't sort of make a beeline for the low for the optimum point like it did with gradient descent where we use the entire training data. Okay.

An example using mini-batches; this one happened to have sort of a little bit better of an error character, but you can still see some noise here, and this one happened to take many more iterations to get to the middle. Okay. One other factor here is that as you're changing the method—stochastic, mini-batches—changing the size of the mini-batch, and so on, the learning rate may have an effect here too, right? So, here the learning rate is pretty small, so it looks like we're taking very small steps on each iteration, and if it gets too big, it might sort of jump down here to the bottom and then just bounce around for a while, hopping over the minimum and not converging. Okay. And so the choice of method with the learning rate is sort of sensitive here, and you know, in some cases for an application you may be doing a little bit of trial and error, and a lot of the research work goes into trying to understand these tradeoffs more analytically. All right. So fine.

So, if that's that's two different methods for optimizing this optimization procedure for performance, you know, applying performance optimization to this optimization procedure to handle larger data sets, but we made the point several lectures ago, several weeks ago, about you know scalability nowadays is really not about making things a little bit faster here and there; it's really about parallelization, right? Everything has to be parallelized as you scale data up beyond the size that can fit on a single single machine, and everything's going that way. And so if you're not parallel, then you don't scale. So, how would you parallelize this? Well, everything we've talked about is sort of inherently sequential, right? Because you even in stochastic gradient descent, it's very very fast because it's only processing a single data point, but each data point changes the parameters, and then those parameters are used to compute the next data point. So, there's this dependency iteration to iteration. All right.

So, what would happen if you just did this in parallel without worrying too much about making it sequential? So, the result could be nonsense, but it turns out that it's not nonsense, and it could actually converge. And so what some folks have shown—a couple different groups actually, more or less independently—and the paper I've cited here is the one that I'd recommend, has this approach called Hogwild. These authors named their approach Hogwild, which is to parallelize stochastic gradient descent: just take in each of the threads, in each of the independent processes, start trying to update the parameters using a random data point, and you can apply this to mini-batches as well.

Um, now, you know, it's it's unpredictable which order these updates will happen in, and therefore it's unpredictable which values of the parameters you'll use to compute the new value, right? You may have one thread's updates but not have another thread's updates, and so on. But what they were able to show is that you still make progress on this. And so what was kind of fun about this is it came out, you know, very empirically from a student of Chris Ray's working to try to improve performance here and just trying out ideas. And so they said, look, you know, what what might happen if we just remove the concurrency control in this parallel program? We just remove the locks, right? So, we no longer sort of worry about what order things are going in and just let everything update willy-nilly, which is why they kind of called it Hogwild. And so it turned out it kind of worked, and it got, you know, a good answer, and you applied it to other data sets, and it got a good answer still. And so then they went back and looked analytically and sort of studied whether this would actually converge in most cases, and were able to sort of prove that it would. But I think, you know, one thing I like about this is, first of all, it gives you a parallel method for stochastic gradient descent, which is nice, but it also sort of shows that you know the exploration and the empirical kind of trial and error approach, doing intuitively what might make sense in some of these cases, is perfectly reasonable. And then it doesn't necessarily tell you any formal guarantees about what you've done, but it might sort of give you a starting point.

So, how does this actually look like? Well, let's say we have two different threads that are all going to be applying this parallel stochastic gradient to algorithm, and if we sort of say time is increasing going down the slide here, well, in the first step we update parameter Theta 0 from its old values and the and the current, you know, the old value of theta 1 as well, and we happen to randomly pick the third instance, so X3, and we compare it with Y3, and remember we don't need this multiplication by X3 here out here because this is parameter zero, which is the slope, so this is there kind of in times 1.0 here. Okay. And then at time two, a different thread will see these new values created that were updated at time at time zero and use those to compute a new Theta 0 here. And then at time three, we're still using the original zeroth value of theta 1, but we're using the second value of theta 0, and so on. And so it's unpredictable. With only two threads, you could sort of see maybe a pattern here if they're interleaved exactly the way I've shown, although there's no guarantee that they would be interleaved in this way, but you can see they're sort of unpredictable. But the point is, as long as it's generally making progress, it's perhaps the exact ordering, the interleaving, maybe doesn't matter; they're all getting updated, they're all sort of an estimate of the gradient, and they're all getting closer to that to that minimum. [Music]

Okay. So, where are we? We've covered some selected topics in a very very broad field of machine learning, and in particular we've been talking about supervised learning. So, we covered rules and trees as representations of certain kinds of hypotheses; we covered combining a set of weak learners to make a stronger learner with ensembles and boosting; and we talked about this optimization technique of gradient descent along with some applications of it and how to speed it up with stochastic gradient descent and then how to parallelize it. And so now we're going to talk about a few selected topics in unsupervised learning. So, this is a very broad field as well, and we're only going to cover a couple of selected topics that data scientists ought to be familiar with, but it's by no means a coverage of the entire area.

So, what is unsupervised learning? So, if we have these four categories of machine learning that are characterized by where the feedback comes from, then unsupervised learning is perhaps the one that stands out the most. So, we've only we've only talked about supervised learning, but you can think about all four of these. So, in supervised learning, the feedback for the learning comes explicitly in the data; in reinforcement learning, the feedback is supplied by the environment; so this is, you know, control theory, when you're trying to keep a plane in the air, for example; and in game theory, the feedback comes from the other participants in the system, the other players in the game. But in unsupervised learning, there is no feedback. And so here you're just looking for patterns in the data itself and trying to put them to use. Okay. So, maybe all and almost all work in unsupervised learning can be viewed in terms of learning a probabilistic model of the data. Okay.

Applications of unsupervised learning include detecting outliers—um, you know, so is this factory behaving normally or not—classification, which is a little different than classification that we talked about given that there's no class labels, but you might find groups of similar items, and then when you see a new item come in, you can figure out which of among the groups you found previously is this one most similar to, and thereby classify it as within that group. Okay. You can also think about compression and communication. So, instead of sending a sequence of ab ab ab ab pairs, you may say, let's just send the sequence ab and repeat seven times. And so this is a shorter representation of that string. So, in all cases, we're identifying these patterns that describe the data and then putting them to use for various services. Okay.

So, in particular, what I want to do is talk about clustering, and this is by no means the only form of unsupervised learning, but it's the one that you'll bump into quite a bit. Another common one that we're not going to spend much time on is dimension reduction. Okay. So, in clustering, you know, there's perhaps no precise definition of what a cluster is, but the which is one of the reasons why you see all these different algorithms for different scenarios, but the output is usually the same, which is a set of sets of data items. Okay. So, these items may be points in some multi-dimensional space, and your goal is to group them by similarity; or the items may be, say, vertices in a graph, and your goal is to find communities that help that discuss that collaborate more closely than other communities, or that communicate more closely than other communities. Okay. So, here you're looking at the edge structure of the graph to identify the clusters, but the output is still the same: it's a set of sets of items. All right.

So, let me give you an example that comes up in a collaboration we have with some oceanographers here at the University of Washington. So, in this cflow device, they've borrowed techniques from flow cytometry and adapted them for environmental monitoring. So, in flow cytometry, the idea is to take—for it's a diagnostic tool in in medical applications—and the idea is to take particulate matter, blood or plasma from the patient, and put particles in that sample through a capillary, single file, bounce light off of it, and by the absorption and refraction patterns of the particle, you can sort of work out which kind of pathogen it is. And so in these applications, you're typically looking for one of a small set of possible critters, and so you kind of know what you're looking for. Moreover, it's on a lab bench in kind of a controlled environment. What these researchers have done is taken one of these devices—or well, not one of these—developed their own device from scratch, ruggedized it, and turned it upside down and put it on the bottom of an oceangoing vessel in order to, in real time, get a continuous stream of labeled particles representing the microbial populations of the open ocean. And this is completely unknown; there's you can get some information out of satellite images, but there's really nothing that's known below the surface; there's no real ground truth for measuring this besides very sparse data from from direct sampling. Okay.

So, how this works is, you know, so one of the challenges here—why you I said they push them through single file here—they do not; they actually open up the pipe a little bit and allow lots of particles to go through because the engineering is too difficult to get things to go through single file, you know, when you're underwater and the boat's doing this. Okay. So, that's one of the problems you have to save energy in the engineering problem, but you have to make it up in the data analysis because now the data is much noisier. Okay. So, as light shines through this particle stream, it's collected on either side by various detectors, and there's two detectors that work initially to help filter out to help identify which particles are at the center of the stream and which ones are at the edges, so you can filter out the ones at the edges. And then there's other detectors for various wavelengths of light, and what you can do here is first filter the data so that you only are worried about the particles that were in the middle of the stream, and then you can start inspecting the different wavelengths to identify these clusters that represent different microbial populations. So, in this case, we're looking at size: nanoplankton, ultraplankton, and picoplankton, and some of the absorption refraction patterns of these different populations are understood, but in the data stream you still need to figure out what these clusters are. And so they apply a clustering algorithm—a variation on a on a very popular clustering algorithm called K-means—to analyze this data. And so we'll talk about K-means next. [Music]

So, let's talk about the K-means clustering algorithm. This algorithm has some weaknesses, but it's very very very popular, in part because it's so simple to understand. So, it's a really good one to be very familiar with. So, the K in K-means refers to the number of clusters you're looking for, which is the first and perhaps most prominent weakness: you have to know this up front. Okay. So, imagine you had data scattered in two two-dimensional data scattered as in the slide, and you're trying to find two clusters. The way you begin is take the centroid of each cluster and drop it into this space randomly as an initial guess as to where that where that cluster would be centered. Okay. So, maybe we say here and here. Okay. And then the algorithm proceeds as follows: for each point in the data set, figure out which of these two centroids it's closer to. This is closer to this one; this one's about about halfway, but probably this one; and this one's about half, but we'll say it's over here. And then at so this is our initial guess of the clustering; we think that all these points belong to this cluster and all these points belong to this cluster. So, now you take the average of all the positions in that cluster to compute a new centroid value and move the centroid there. So, for example, here this one will shift this way, and this one will shift sort of this way, right? So, in the second iteration, our points our two centroids might look like this, and then we just repeat the process. So, for every data point, figure out which centroid is closer to—about halfway, but let me put it there—and this is our guess at time equals two for the clusters. And now, once again, average all the positions within that cluster to find the new centroid. And so here these two points will pull a little bit in that direction, but most of the most of the points are this way, so it'll probably shift that way a little bit, and similarly with this one, it'll shift this way. And so at time three, we have a centroid there, and we have this centroid here. And now, the closest—once again—assign the points to the closest centroid and recompute the new centroid value. So, this one will finally shift into the middle here, and this one will finally shift perhaps a little bit this way. And then at time equals four, we can repeat once more and find that the centroids in this case don't move that much on the next iteration. And so once the movement of all the centroids is below a certain threshold—they haven't moved much, things don't change much, things have settled down—we stop the algorithm, and that's our that's our clustering. And so in this case, all of these points will be assigned to this cluster, and all these points will be assigned to this cluster.

So, you can parallelize this algorithm by splitting the data items across multiple machines, and one of the key ideas here is that the number of centroids is pretty small, or at least small to fit in memory, right? It's not you're not typically looking for billions of clusters. And so you can broadcast those to every map task in, say, a MapReduce setup. So, in the map phase, the mappers look at each data point, and they have access to all the centroids, and they can figure out which ones each which one each data point is closest to and then send that to the reduce phase according to the cluster that it was assigned to. Okay. So, all that can happen in parallel, and then on the reduced side there's one reduce task per cluster, and it can compute the new centroid value. And so there's a bit of a weakness here because one reduce task could have a lot of work to do because it might have most of the data points, and that could be a that could be a problem, but in principle things are balanced; you might get a pretty good parallel speedup. Then the other weakness with this MapReduce implementation is that there's no direct support for this iterative nature of K-means; we have to repeat this over and over again, and so you have to have some kind of external driver program that will keep kicking off MapReduce jobs one at a time. And we'll talk a little more about this in the final week of lectures.

So, summarizing the weaknesses of K-means, you know, first of all, you have to know the number of clusters up front; you have a fair amount of sensitivity to the initial starting conditions, in that there's no unique solution; depending on the starting conditions, you may get a different answer; and there's also some sensitivity to the stopping threshold. There's, as is always the case, there's been a lot of work on repairing these various problems, but when someone just says K-means unqualified, they're typically talking about the algorithm we just described, which is sensitive to these [Music] issues. Okay.

So, there's one more algorithm I want to talk about that's less well-known than K-means, but it has slightly nicer properties, so it's another good one to be familiar with, and that is DBSCAN. So, how DBSCAN works is, given points, say, in a two-dimensional space, as always, we're going to look for points that are separated by a distance of no more than some epsilon. Okay. And so if you can hop from one point to another by hopping no more than epsilon at each point, then all those points will be considered to be in the same cluster. And so whenever you need to jump a little further than epsilon, you'll be entering a new cluster. Okay. So, in this example, if epsilon is this distance, then we know we can get—is driving—I mean, that's a little bit—these points are within epsilon, these points are within epsilon, and so on. And so you sort of induce this graph over the over the data. And so all of these—A is, you know—B is

reachable from A by hops of no more than Epsilon, so all these are in the same cluster. And actually, C is also reachable from B by hops in the same cluster, but D is not, and so D is in a different cluster. So all the solid points are in one cluster, and all these hollow points are in another one. All right. So there's some advantages here that are kind of illustrated by this picture. So one is it can find nonlinearly separable clusters. So right here, there's no line you can draw to separate these two clusters, and yet clearly there's kind of a dense region and another dense region, and so you want to try to draw a curved line. DBSCAN finds this naturally, but K-means won't. K-means will sort of find a point, you know, depending on, again depending on where you start, you know, maybe here and here or something, in which case you'll get clusters like this. Okay. So there is no dependence on a fixed number of uh starting clusters like K-means was. There's no dependence on starting conditions. You sort of compute this from any of the vertices in the graph and start making hops. There's only two parameters to this: one is this distance threshold Epsilon, and the other is a minimum number of neighbors. And what this controls is like if I find a point way out here in space that doesn't have any neighbors, doesn't, you know, only has a few neighbors, then maybe I just consider that point noise and I ignore it completely. I don't try to I don't try to put it into any cluster whatsoever. And so here, if you if you put Min Neighbors at zero, you'd get this one in its own very own little cluster, this one its very own little cluster, and so on. And so that just keeps it requires extra bit of bookkeeping; it's not necessarily a big flaw on the algorithm. You'll still find the obvious two main clusters, but you can set this uh second Min neighbors parameter to control the extra bookkeeping you have to do to maintain these Singleton clusters. Okay, fine. And then, you know, the the the core primitive here as it's operating is to find me all the neighbors within, find me all the neighbors with an Epsilon. Find me all the neighbors with an Epsilon. And so this operation is amenable to spatial indexing techniques which can be implemented in log N, so that every lookup requires only a logarithmic number of steps. Remember, as we talked about in the scalability lecture. And so the overall runtime of this is in log N. All right. So some disadvantages here is that it's sensitive to Euclidean distance measure problems, and and if you remember a few a few lectures ago, I made a point to say that whenever you see Euclidean distance, you should be thinking about there's there's one big major problem with it, which is the curse of dimensionality, right? So as you get a very very large number of dis of uh Dimensions, Euclidean distance starts to become somewhat meaningless. It starts to get bigger and bigger and bigger, and the data set starts to get sparser and sparser and sparser. The space that it's embedded in is very very sparse. But K-means also has this problem because it also tends to rely on Euclidean distance, and you actually can define other distance measures and have an adapt K-means and DBSCAN both to use them. Okay. And then another problem is that you're kind of making this implicit assumption that the density that defines a cluster is constant throughout the data set. And so this is related to this concept of heteroscedasticity that we talked about that may have seemed a little unusual at the time, but it comes up in various guises in different contexts. I want to make sure that I mentioned it. So, for example, this plot is actually the same one that we generated for to make the point about heteroscedasticity in the statistics segments, but what I've done is just cut out uh some portions of the data here and here, and so now it looks to our eyes like there ought to be three clusters here, right? One here, one here, and one here. But DBSCAN, given its sensitivity to this Epsilon number, do you define Epsilon such that this cluster is easy to detect, you know, a very small Epsilon about this kind of distance, or do you find it a slightly bigger Epsilon so that you can capture these kinds of clusters? And if you're not careful, I suppose here I've actually doctored this one where it's probably okay to use the bigger one, but if you're not careful, you you'll uh, you know, the density region here may be on par with the distance between these two clusters here, in which case with a small change to Epsilon you might all of a sudden put the whole the whole data set into one cluster. Okay. And so adaptive Epsilons depending on which region you're in might be something you could you could think about. All right. And just like with K-means, you can think about how to parallelize DBSCAN, and the the only trick I want to point out here is that you need to worry about this Halo region around each cluster, or rather around each segment. So here we divide up the space into say four different processors, and each processor is going to be responsible for that space. And in the middle, internal to this processor, you can run DBSCAN as usual, but when you get close to the boundary of that of the region uh handled by this processor, you need to be you need to do some careful bookkeeping. Okay. And so all the ones that are within this boundary region need to be sent to this other processor for comparison to see whether you need to relabel C4 and C6 as part of the same cluster, whether those two clusters are connected by a distance of Epsilon or they're not. And so they'll independently find all their clusters, but then you'll merge some clusters when you combine, and you can actually express this in terms of a sequence of map-reduce jobs, which I won't go into the details of, but there's some work done by a student here a few years ago to describe and analyze the the the algorithm here. Okay. So finally, I just want to wrap up with this great picture from the scikit-learn Python Library website, which talks about the differences between various clustering algorithms, and we've only talked about two of these: we talked about K-means, and we talked about DBSCAN. And mini-batch K-means is uh a online version of K-means that uses batch at a time to compute centroids, but you can see some of the some of the strengths and weaknesses here. Uh K-means actually doesn't do that great in any one of these admittedly tricky challenge problems where here you would probably think that you want this internal Circle to be a cluster and this Outer Circle to be a second cluster, and K-means doesn't quite get that right depending on where you have the starting condition. Meanwhile, these two clusters kind of overlap in space as well. And here, if you have a bad starting condition in between these two clusters, you might put them all in the same cluster, or really anything anytime the starting condition is up here, here, and say down here, this one will sort of gravitate towards this cluster and this one will sort of gravitate towards this cluster and end up in the middle and so on. Meanwhile, in DBSCAN, this hop from this cluster to this cluster is greater than Epsilon, and so you'll you'll do the what seems to be the correct thing, which is put the Inner Circle in one cluster and the Outer Circle in another. Similarly here, the distance between these clusters is enough where DBSCAN figures it out, and similarly here, and for the noisy case, DBSCAN puts all of these points all in the same cluster, which, you know, to our eyes that's probably the right thing to do. Okay. So I think the takeaway here is that at least in these four challenge problems, DBSCAN does the right thing in every case, and so it's a good one to be familiar [Music] with.

Hi everyone, my name is Cecilia Aragon, and I'll be your guest lecturer this week. We're going to be talking about about basic principles of information visualization. This is, in my opinion, one of the most important, interesting, and fun components of the data science pipeline. We're going to be talking about how you take the data that you've collected and analyzed and then actually present it in a form that makes sense to the human brain. I'm a professor here at the University of Washington in the department of Human Centered Design and Engineering, and it'll be my pleasure to introduce you to this exciting subject. My research interests lie in the visual presentation of very large scientific and social data sets. So let's start with a few definitions. The word visualization is extremely overloaded; there are many possible meanings of the term. So what are we talking about when we say we're studying information visualization? Well, we want to consider the visual representation of information. The goals of information visualization include the effective communication of information or data with clarity. That means that the information should be presented in a way that's easy to understand by a human, with integrity. You present all the data and nothing but the data, and you want to stimulate viewer engagement with the data. Our focus in this course will be on effectiveness. We're talking about the clear and effective presentation of data to the human mind. Data visualization usually falls into three academic categories: information visualization, scientific visualization, and visual analytics. Information visualization typically involves abstract information that may not have a position in space. For example, on the slide you can see a graph of stock prices around the year 2000. We graph the the price, the dollar amount, on the y-axis and time on the x-axis. Scientific visualization usually involves displaying data that has a physical position in space. For example, here you see a methane combustion data set where each of the data points has a 3D location. Visual analytics is a combination of highly interactive visual interfaces and sophisticated statistical learning algorithms. In this course, we're going to be talking about basic principles of information visualizations. We're not going to be talking about scientific visualization specifically, nor about visual analytics, nor about the artistic field of visual design. The principles, however, of information visualization that we are discussing are applicable to all three domains. We will be discussing specifically this week how to map data variables to visual attributes. So why is visualization important? Say you have a million numbers. What's the best way to communicate that information to the human brain? Well, imagine a table of a million numbers. It seems almost too vast to comprehend, much less to find meaningful Trends or information about it. But on the other hand, if you consider the number of pixels on your computer screen, that's typically around a million, and you have no trouble understanding it very quickly and being able to to act on the information you've gleaned. So the human visual system is is the highest bandwidth channel to the human brain, and it's the most efficient way to present large amounts of information so they make sense. Let's talk about a few examples. So maybe the first use of visualization historically was for eliciting knowledge from data. Let's suppose you have a table of numbers. We'll start with a relatively small table with only 50 rows, one for each state in the Union, three columns in each row: the name of the state, the percentage of college graduates in that state, and the per capita income. So you might have questions about this data such as: which state has the highest income? Is there a relationship between income and education? Finally, are there any outliers? Are there any Trends? Well, obviously all the data is present, and you could take your time looking at this data. You could identify the highest and lowest numbers. You could answer all these questions from the data; everything is presented here, but is is the most efficient way to understand this data? Here's another way of presenting the data: in a scatter plot. We have per capita income on the x-axis and the percentage of college degrees on the y-axis, and as you can see the question of which state has the highest income is instantly answered. We can see that Connecticut has the highest per capita income. Similarly, it's clear there's a trend that there's a there's a correlation between per capita income and the percentage of college degrees, and there's also a couple of interesting outliers. Nevada has a relatively High per capita income but a very low percentage of college graduates. So all the information is presented in in both of these forms, but the the visual representation is is much more efficient at presenting meaning to the human mind. Well, so okay, the first question that might come up is, well, yeah, but all this information could more easily have been accomplished by analyzing the data with a statistical program. You can find the maximum, you can find the minimum, you can find the regression line. However, it turns out the human brain is one of the best pattern-matching tools that we have. Actually, it's we're the human brain so far is still better at detecting patterns in data than any of our most sophisticated machine learning algorithms. So an immediate question that arises is: why not just use a statistical program and identify the minimum, the maximum, the trend lines, and go from there? Why bother with a visual representation? The answer is simply the graphs reveal data that statistics may not. So here's a famous example of Anscombe's quartet. Here you have four small data sets that are quite different, as you can see by looking at them, but they have identical linear models; that is, the identical means and the identical trend lines. Again, you could just present the data in in tabular form, but see how much more information we can learn about these these individual data sets just by looking at the data. So even though we have identical means, identical regression lines, these data sets are quite different. So so statistics may not tell us everything about a particular data set. I hope I've managed to whet your appetite for this coming week's set of slides. I'm going to stop here, and we'll continue on with more examples in the next [Music] lecture.

In this lecture, we're going to talk about the heart of information visualization: data types and visual mappings. So the central problem in order to visualize data is is quite simple: we need to map data sets to visual attributes. This is also known as data encoding, and the process can be described in a very straightforward manner: one, you classify your data types; and two, you determine which visual attributes represent data types most effectively. Of course, the devil is in the details. Let's start with data types. There are three basic data types: nominal, ordinal, and quantitative, which can be further subdivided into interval and ratio. I'm going to explain each of these on the next slide. So nominal data can be thought of as labels or names. An example is fruit: apples, oranges, peaches, pears would be described as nominal data. Ordinal data has an order associated with it. So, for example, the quality of meat might be described as grade A, grade AA, grade AAA. There is an implicit order, so you can clearly say that grade AAA is better than grade AA. The two types of quantitative data: interval data is where the location of zero is arbitrary. So dates are an example: if you're looking at January 5, 2012, or location, for example, latitude 47, longitude 122. And these are like a geometric point; you can't compare them directly, but only differences, that is, intervals can be compared. And then finally, you have ratio data, which is where the zero is fixed, and you can think of this as any physical measurement: length, mass, counts, and amounts. The origin is meaningful. Let's talk a little bit more about the differences between nominal, ordinal, and quantitative data. Sometimes it's not immediately clear, given an example, what data type that it falls into. So one of the best ways to actually identify data as nominal, ordinal, or quantitative is to look at what are the operations that are permitted on this data. So nominal data: there are really only two operations that are permitted: either equals or not equals. For example, with fruit, you can say the oranges are not equal to apples, and apples are equal to apples. There's no other comparison that can be made; you can't say that oranges are somehow better than apples. Ordinal data has additional operations besides equals and not equals. You can now say that one is greater than or less than another, or greater than or equal to, or less than or equal to. So, for example, with the the grade of meat, that you can say that AAA is better than AA, and vice versa: greater than, less than; you can deal with that implicit ordering. Now moving to quantitative data, with interval data, for example dates, now you can subtract. So you can measure distances or spans; you can say that not only is January 6, 2012, after January 5, 2012, but you can say the difference between those two dates is one day. And finally, coming to ratio data, where the zero is fixed, now you can add, division, or ratios. You can measure ratios or proportions. So, for example, if an object weighs 32 grams, you can say that it weighs twice as much as another object that weighs 16 grams. All right. So that's the theory. Now let's put it into practice with an exercise. I'm going to show you a spreadsheet, and I'd like you to think about which of the columns in the spreadsheet are nominal, ordinal, or quantitative. So here we have a set of sepal and petal lengths and widths for three species of Iris. The first column, you have an ID number, then a case number, next a species number, then a species name, the organ, petal or sepal, the width and length of that organ in millimeters. So why don't you take some time and think about which of these are nominal, ordinal, and quantitative? You can see that it's not as straightforward as it might appear in the first place. For example, we have numbers here that fall into the categories nominal, ordinal, and quantitative. So let's explain why each of these is defined the way it is. So the quantitative is probably the easiest: the sepal data, the width and the length of the sepal and petal are quantitative. You can say, for example, that for the first species the length is 7 times the width, so you can perform ratios and proportions, so it's quantitative data. Now the first two, the ID number and the case number, are ordinal. So why are they not quantitative? Well, because it's really not something where you can say the distance between the ID number three and the ID number two has any meaning, but it clearly has an order: the ID numbers were assigned in some particular order, so therefore it's ordinal, and the cases were assigned in a particular order, but there's not necessarily a meaning for the differences between them. So um the ID and the case numbers are ordinal. Now we have the species number, the species and the organ, which are nominal. Well, it's probably pretty clear that the species name and the organ would be nominal because they're names. All you can do is say whether they're equal or not equal to each other. You can't say that the sepal is somehow greater than the petal, so that those are pretty easy, but what about the species numbers? Why isn't that ordinal? And the answer to that is simply because in this case the species number is simply a label; there is no order to it. It was assigned to the species simply as a labeling convention. All right. So hopefully that has been a useful example for you. All right. So moving on, we've now completed step one of the process of information visualization. So now let's describe how to do step two: mapping data types to visual attributes. In 1967, Jacques Bertin, a French cartographer, made the first formalization of visual language and the first attempt at a theoretical foundation for information visualization. He identified seven key visual attributes, illustrated on the right-hand side of the page in zero, one, and two dimensions, and these seven key attributes are position, size, value or lightness, texture, color, orientation, and shape. So this is an important slide; you should probably write down these seven these seven attributes, or at least save the slide. So now that we have taxonomies of both data types and visual attributes, let's talk about how we map one to the other. So Bertin offered the following suggestions: he said there were levels of organization that you could consider. Position can be used for nominal, ordinal, or quantitative data, as can size. Now value or lightness can be used for nominal or ordinal data, and perhaps for quantitative data, although it's not quite as clear. And texture can be used for nominal data, maybe for ordinal data; you could imagine a denser texture might be seen as having some order over a lighter, a less dense texture. And then finally, color, orientation, and shape can really only be used for nominal data. You can't really say that one color is greater than another, or that one orientation is less than another, or that a a

Shape a star, say, is more than or less than a circle. And further work that involves decades of research in psychology and psychophysics have established this hierarchy of perceptual properties: humans can detect differences in position most accurately, then length, then angle and slope, then area, then volume, and least of all color and density. So when you're assigning these attributes to your data, make sure to choose position for your most important quantitative data and save color and density for nominal data.

A final note on color: value can be perceived as ordered, so you can encode ordinal variables. In other words, you see this strip that goes from black to white where value is increasing; you can see that there is an order to these colors. You can also even encode continuous values with a grayscale mapping, although not as well. But hue is normally perceived as unordered, so you always only want to encode nominal variables using color. There's no order to the color on the bottom of the slide.

So this was a very brief lecture on the central important problem of information visualization. In the next lecture, we'll look at exercises where you can actually put this theory into practice.

Last time we talked about the theory behind the central problem in information visualization: mapping data types to visual attributes. In this lecture, we're going to put that theory into practice. So for these exercises, I'm going to show you three visualizations, and in each of them, I'd like you to identify which types of data and mappings are represented.

So here we have a stock chart from around 2000, the year of the dot-com bust. How many data types are represented on this graph? What are they? Are they nominal, ordinal, or quantitative? What are they mapped to? Which visual attributes that is? And is that a good mapping? Why or why not? What is your opinion on the visualization? Take some time to study it and come up with the answers to these questions.

Okay, here are the answers. It's actually quite simple. There are two dimensions of data represented on this chart; they're both quantitative, and they're both mapped to position. You have the time, which is quantitative or interval data, on the x-axis, and then price in dollars is mapped to the y-axis.

All right, let's try another one. This is one of the earliest graphs made in 1786 by William Playfair, a Scottish engineer and the inventor of several common types of diagrams in use today. So on this diagram, how many data types are represented? What are they? Are they nominal, ordinal, or quantitative? Which visual attributes are they mapped to? And is this a good mapping? Why or why not?

There are four dimensions of data represented in this graph: the year, which is quantitative, is mapped to position on the x-axis; imports in pounds, also quantitative, map to position on the y-axis; similarly, exports, which are quantitative, are mapped to position on the y-axis; and then, finally, the balance of trade, which can be considered either nominal or ordinal, is mapped to color and area.

Here we have the US stock market visualized with a version of Ben Shneiderman's treemap, where quantitative data is mapped to a set of space-filling rectangles. In this case, market capitalization is mapped to rectangle area. This was created by Martin Wattenberg in 1998. How many data types are represented? What are they? Are they nominal, ordinal, or quantitative? Which visual attributes are they mapped to? And is this a good mapping? Why or why not?

In this visualization, we have four variables: the market capitalization (quantitative) is mapped to the rectangle area; the market sector (Technology, Energy, capital goods, transport, etc.) is nominal data, and that's mapped to the rectangle position; third, whether there is a gain or loss is represented by the color hue (red or green), so if there's a gain, it's green, and if there's a loss, it's red; this is nominal or perhaps ordinal data; finally, the magnitude of the gain or loss, which is quantitative data, is represented by the color value, so you can see that the brighter the green, the greater the gain; similarly, the brighter the red, the greater the loss.

So this concludes our set of three exercises. I hope you found this illustration useful. Next time we're going to talk about data combinations and dimensions.

In the last lecture, we provided a set of three exercises on mapping data types to visual attributes. In this lecture, we're going to give more examples of data combinations and the mapping of data to visual attributes, and we'll talk about the effects of dimensionality on the visual display.

So if you have a single variable to display, or univariate data, you have a plethora of choices for visualizations: dot plots, line plots, bar graphs, or two-key box plots are but a few of the examples. For bivariate quantitative data, the scatter plot is the most common choice. So here we have two quantitative variables, and the scatter plot describes the information quite clearly.

Moving up to three dimensions now, it's getting a bit more challenging. So we can try a 3D scatter plot, but what are some of the problems? Let's look at the 3D scatter plot on the right with blue cubes: where exactly are E and F in relation to each other? It's a bit of a problem trying to represent three-dimensional information on a two-dimensional surface. A better choice might be to use a two-dimensional scatter plot with a third dimension represented by some other attribute. Here we use area for the red circles for the third quantitative dimension. Area is not perceived as accurately as position, so you want to put the most important dimensions on the x and y axes and save the least important, or perhaps the most easily distinguished, for the third.

Since we already discussed what are the issues in trying to map three variables to a third spatial dimension, let's look at other ways to deal with mapping three variables to a visualization. So we know that two variables on the x and y axes can map to points, so we have scatter plots, maps, etc. Now the third variable must use something like color, size, or shape, and as you can imagine, we have a very large design space, so finding the optimal mapping becomes more challenging as the number of dimensions increases. You can always use shape or different types of marks to represent nominal or categorical data.

Now moving up to multi-dimensional data: how many variables can be depicted in an image? We've talked about one, two, and three dimensions, but what about more? Is there some perceptual limit? Starting in 1967, Bertin and others asked this question, and Bertin stated, "With up to three rows, a data table can be constructed directly as a single image. However, an image has only three dimensions, and that barrier is impassable." We'll look into answering this question in the next lecture.

Last time we talked about data types, dimensions, and how to map data to visual attributes based on the number of data dimensions. Clearly, there's a large design space for this visual encoding. Information visualization is about choosing the most effective visual encoding for a given data set. In this lecture, we're going to describe how to do that. We saw earlier that there are different data types, and those can be mapped to a set of visual attributes, and some mappings are better than others. So now we have a challenge: how do we pick the best mapping of all possibilities?

So in order to do this, we're going to follow three basic principles: importance ordering, expressiveness, and consistency. This was first described by Jock McKinley in 1986. So importance ordering has to do with encoding the most important information in the most perceptually accurate way. Expressiveness has to do with depicting all the data and only the data. And finally, consistency means that the properties of the image, the visual attributes, should match the properties of the data. I'll go into more detail on how to do this on the following slides.

We'll start with importance ordering. We've seen this slide before. Now, as we discussed earlier, decades of research have taught us that certain visual attributes more accurately represent quantitative data to the human brain. McKinley defined expressiveness in the following manner: he said, "A set of facts is expressible in a visual language if the sentences, i.e., the visualizations in the language, express all the facts in the set of data and only the facts in the data." So what does this mean? Well, using color hue, we cannot express the fact that one item is greater than another, so color hue simply can't represent ordinal data. Ordinal or quantitative data; so color hue simply can't represent ordinal or quantitative data; it's best used for nominal data. On the other hand, you don't want to express facts that are not in the data. So a length is interpreted as a quantitative value. In this incorrect use of a bar chart, the length of the bar says something untrue about the data. So on the x-axis, we have the national origin of these cars, and on the y-axis, the make model. Now the length of the bar suggests an ordering on the axis, so it implies that somehow Germany is greater than the USA. So therefore, using bars for nominal data is an incorrect choice.

Number three, we have consistency: the properties of the image, the visual attributes, should match the properties of the data. What this means is you don't want to do something like mapping one-dimensional data to two or three-dimensional visual representations. This diagram represents why that's not a good idea. So here we have the price per barrel of oil represented as the height of a three-dimensional barrel. You can see the obvious problem here. Look at 1974: the price is 10.95, and then for 1979, the price is 133.4. Well, this is less than a 30% increase, and yet the 1979 barrel looks significantly larger than the 1974 barrel. So clearly, this is an inconsistent representation; the three-dimensional representation is implying something false about the underlying data.

Let's move to a data encoding exercise. Here we have a data set of cars: we have the model on the first column, the country of origin, the year, the number of cylinders, the horsepower, the miles per gallon, and finally, the weight in pounds. I would like you to create a visualization that encodes all seven dimensions of this data set. Make the perceptually appropriate choices and be prepared to explain. I'll describe the steps you need to do and show you Bertin's examples once more. So step one: determine which columns represent nominal, ordinal, or quantitative data. Step two: review Bertin's visual attributes on the next slide and assign the most perceptually appropriate choices to each data set. Step three: create a visualization that encodes as many of the seven dimensions as you can. Don't worry if you can't get all of them, but do try to do so. To review, here are Bertin's visual attributes: position, size, value, texture, color, orientation, and shape. Are you done?

Here's one attempt made by one of my students. So this is an attempt at encoding seven variables from the cars' data set in a single visualization. So this student chose to put two of the quantitative variables (horsepower and miles per gallon) on the x and y axes. The third ratio data (weight), he encoded with area of the marks; it's not a bad choice since you can only put two of those ratio variables on axes. He also chose to encode cylinders, which are quantitative interval data, by using the shape of the mark, and then finally, he used color hue for the region (Europe, Japan, or US) and color value or lightness for the year. Additionally, in his visualization, you could mouse over each of the marks, and the name of the model of the car would pop up. So what do you think of this visualization? What works? What doesn't? And what could you do better? I'll leave that critique as an exercise for you.

In this final lecture on effective visual encoding, we're going to start with two quick exercises on effective presentation of data, and then we're going to discuss five key techniques for increasing the amount of information represented by spatial position. So we've already talked about why effective visual encoding is important. Here is an example that I'd like you to consider. So look at these two representations of quantitative data: here we have the top level one where color is used to represent it, and at the bottom, a line graph. Why would the line graph be better to use than the color? By now you should know: it's faster to interpret; this, you take the time to look at it, you can see that there are more distinctions; you can clearly see the quantitative information much more easily with a line graph than with a color, and there are fewer errors of interpretation. Pretty simple. Is this an effective visual representation? Yes or no? If no, what's wrong with it? This visual representation is not expressive because it implies an incorrect ordinal relationship among the countries.

All right, moving on to some new material. We already know from research data in human perception that spatial position is the most accurate representation of quantitative data. So how can we leverage this fact? In 1999, Card, McKinley, and Shneiderman proposed five techniques to increase the amount of information encoded by spatial position: composition, alignment, folding, recursion, and overloading. We're going to go through each of these slide by slide. Composition refers to an orthogonal placement of axes; you create a 2D metric space, and you can line the data up along the x and y axes in multiple different ways. Alignment: this refers to the repetition of an axis at a different position in the space. So here you see we have the same time axis repeated in two places but two different graphs representing different amounts of information on the y-axis. Folding: continuation of an axis in an orthogonal dimension. Recursion: or the repeated subdivision of space. And finally, overloading, where we reuse the same space for different data.

All right, this concludes our set of lectures on visual encoding. The next set of lectures will move to visual perception.

In the previous lectures, we've been discussing data and visual mappings. Now we're going to talk about the other end of the pipeline: how that information is processed by the human brain. This is the first of three lectures on visual perception. Seventy percent of our body's sense receptors reside in our eyes. Our very language resonates with the importance of our eyes: metaphors to describe understanding often refer to vision: "I see," "insight," or "illumination." Colin Ware stated in 2004, "The eye and the visual cortex of the brain form a massively parallel processor that provides the highest bandwidth channel into human cognitive centers." In these three lectures, we're going to describe how it's important to understand how visual perception works in order to effectively design visualizations.

The first key principle to keep in mind is that the eye is not a camera. A better metaphor for vision was given by Christopher Healey in 1995: it's a dynamic and ongoing construction project. And it's important to keep this in mind as you go through the next three lectures, because when you design a visualization, if you think of the eye as a camera, it can lead you to some erroneous conclusions. Attention is selective; we all know that; um, it's filtered to a high degree, and it's really cognitive processes that transform the visual information into something that we can comprehend. The field of psychophysics is concerned with establishing quantitative relationships between physical stimulation and perceptual events. So we're going to be talking about some of the important discoveries made in this field in the next three lectures.

Let's think a little bit about how to use perceptual properties: information visualization should cause what is meaningful to stand out. So what do you see in this image? Can you see the two spots that differ from their surroundings? Why do you see them? We're going to answer that question in the next few slides and lectures.

Some important differences between eyes and cameras: cameras have very good optics; they have a single focus; they maintain a white balance and a single exposure; and they also do what's known as a full image capture; in other words, all the photons coming into the eye are captured with equal importance and at the same time. The eyes, on the other hand, have relatively poor optics; they're constantly scanning; this is known as saccades, the shifting of your eyes to various positions; they're constantly adjusting focus; they're constantly adapting both the white balance and the exposure. What's really going on is a mental reconstruction of the image, sort of as we'll find out; it's not even a complete image that's reconstructed.

So here's one example: visual perception really isn't just camera work. Looking at this checkerboard, it's pretty clear that square A is darker than square B, right? Turns out, if you gray out the image, you see the truth: square A, square B have identical pixel values. As a matter of fact, when I first saw this image, I didn't believe it; I actually put the image in Photoshop and used the eyedropper tool in order to find out what the RGB values were of those two squares, and yes, indeed, they are identical. So you're welcome to do the same; you can take a screen capture and test it out yourself, but um, it's pretty interesting: the human visual system is so dependent on context and upon reconstructing the image that we see these two squares, which are identical, as quite different. Color is relative, as are many other of our perceptions. If you look at this slide, doesn't it look like the X on the left-hand side is gray and the one on the right-hand side is yellow? But if you go look at where they connect in the center bottom of the slide, you'll see they're identical, and that's again because the eye perceives differences; it does not perceive actual pixel values.

So in conclusion, I hope you've taken away from this lecture that the eye is not a camera. In the next two lectures, we're going to discuss more about how understanding visual perception can help us develop more effective visualizations.

Welcome to our second lecture on visual perception. In this lecture, we'll be discussing a very intriguing property of the visual system: preattentive processing. I'd like you to look at this slide and tell me how many fives there are in this array of numbers. Do you have the answer?

All right, I'd like you to think about how long it took you to find them and what techniques you used to detect these fives. And now I'm going to show you the same array with one small change. Now how many fives? All fives are red, by the way. Notice how easy it was to come to the answer: the color made the fives pop out at you. Psychologists have given this property a name: your immediate detection of the red fives is called preattentive. It turns out that certain basic visual properties are detected immediately by the low-level visual system; it means they pop out at you rather than requiring a visual search through all the elements. In general, if the detection of a target takes less than about 200 to 250 milliseconds, it qualifies as preattentive, and the reason is because eye movements take at least 200 milliseconds, and yet we find that certain processing can be done very quickly, and this implies low-level processing in parallel before the eyes even have a chance to move. In general, if a decision takes a fixed amount of time regardless of the number of distracters, it is considered to be preattentive. Now only a limited set of properties can be perceived preattentively; that means without the need for focusing attention, and you can see why this would be important for designing visualizations: what can be perceived immediately? What properties are good discriminators? What can mislead viewers? How can you use the ability to process information preattentively to strengthen your visualization?

Let's talk about a couple of examples. So looking at these two squares, in which one is there a red circle? Left or right? Pretty obvious, right? You could instantly see that the red circle is visible in that group of blue circles; it jumps out at you; it seems almost ridiculous to think that there might be a question. Detection of the red circle in a sea of blue circles is preattentive. Now which square contains the red circle? Left or right? The form, the curvature, is also preattentive; the curved circle pops out at you. However, you may have noticed that it doesn't seem quite as immediately obvious as the different color. Preattentive processing lies on a spectrum, just like many other such visual features. Now which square contains the red circle? Left or right? So that one required serial search. So this is interesting: so even though form is preattentive and color is preattentive, the conjunction of the two is not. So the red circle in the sea of red squares and blue circle distracters could not be perceived preattentively. This can be used in practice to save lives: detection of a slanted line in a sea of vertical lines is preattentive. In this case, the slanted line in a number of cockpit dials is used to indicate systems failure.

And I'm going to conclude with a list of preattentive visual properties for you to consider. For more detail, please see Christopher Healey's article on the web; the link is given in the lower right-hand corner. I hope that you found this lecture interesting and that you're able to use this information while you're designing your own visualizations.

In our third and final lecture on visual perception, we'll be discussing how humans

Estimate magnitude. If you'll recall from our earlier lectures on mapping quantitative data to visual attributes, you can see how understanding common misperceptions or inaccuracies in the visual system can be very helpful when it comes to designing an effective visualization. We're fortunate in that there is a large body of psychophysics research that we can draw on.

All right, so I'd like you to look at these two circles and tell me what is your impression of the difference in areas between the two circles? I want you to come up with two numbers: first, your first impression, and then what you think it is after considering it more. Write down both numbers—both your first impression and your more detailed analysis. So what did you get? The correct answer is 25.

The idea of a power law for visual perception was first mentioned in the 19th century, but Stanley Steven, in the mid-1950s, came up with a body of work to justify it, and he formalized the power law. His experimental results for perceptual estimation gave an exponent for length of pretty close to one, so, in other words, fairly accurate; but in area, .6 to .9, so you get some underestimation; and in volume, .5 to .8—even more underestimation. So in the previous slide, even though the area differential was 20.5, most people tend to say it's around 16. So how close did you come? And perhaps more importantly, how can you use this for designing visualizations that will be accurate and effective?

It turns out cartographers have already known about this for quite some time. In the 1970s, Jay Flanner, a cartographer, conducted a set of experiments and produced a set of empirical guidelines for how to represent quantitative information using area. So what cartographers do when presenting quantitative data, they'll use apparent magnitude scaling.

Right, let's consider a set of visual attributes and how good humans are at estimating magnitude. This data comes from—again—from many decades of research in psychophysics. It turns out that humans are most accurate at estimating differences in position. If there's a common scale, if the scales are non-aligned, then they're slightly less accurate, but still fairly accurate. Then comes length, slope, and angle; and then much less accurate are area, and even less so volume. Finally, humans are most inaccurate at using color to judge magnitude. So again, we have evidence that the hue, saturation, and value are not very good choices to use when estimating quantitative—when representing quantitative data.

So the conclusion to these three lectures on visual perception is that what is currently known about visual perception can aid the design process. Understanding the low-level mechanisms of the visual processing system and using that knowledge can result in improved displays.

[Music]

In this lecture, we're going to go through the step-by-step process of how to evaluate a visualization. The first step is to consider the purpose of the visualization and who the intended audience is. In other words, is it to educate, to inform, or is it for exploration? Is the audience the general public or a specialized body of scientists, for example? That's very important in deciding what the overall value is of this particular type of visualization. Don't make the mistake of judging a visualization without understanding the intended audience.

Next, determine your initial reaction. Is it generally positive or negative? It's all right to have an emotional reaction to a visualization, but also try to step back and analyze it somewhat dispassionately. Examine the visualization in detail. What works well? What doesn't? And finally, answer questions such as the following: Is the design aesthetically pleasing? Is it immediately understandable? If not, is it understandable after a short period of study? Does it provide insight or understanding that was not obtainable with the original representation—text, table, etc.? This is very important. If the only difference between the visualization is that somebody added color to the design and made a pie chart out of it, that does not necessarily make it valuable. A visualization should add value over a textual representation, or it is not a good visualization.

Fourth, does it provide insight or understanding better than some alternative visualization would, or does it require excessive cognitive effort? What kind of visualization might have been better? For example, if somebody has given you a set of multiple pie charts and you have to compare pie wedges from one to the other, is that really the best way to make those comparisons, or could a bar chart have done the job just as well—maybe better? Does the visualization reveal trends, patterns, gaps, or outliers? Can the viewer make effective comparisons? Does the visualization successfully highlight important information while providing context for that information? Is new information gleaned from the visualization that wouldn't have come from an alternative method? And is the important information highlighted, and is the context not hidden?

Number seven: Does it distort the information if it transforms it in some way? Is this misleading or helpfully simplifying? Does it omit important information? Is it memorable? Does it use visual components properly? That is, does it represent the data using lines, color, position, etc., as we discussed in the earlier lectures? Does it transform nominal, interval, and quantitative information properly? And does it use labels and legends appropriately?

[Music]

So I want to spend some time talking about graphs and graph analytics. So we've encountered these before in the context of the Elastic MapReduce assignment, but we haven't spent too much time in the lectures talking about them, but they're increasingly important in a data science context for reasons we'll talk about.

So what is a graph? A graph is a pair of sets: a set of vertices and a set of edges. Okay, you might also see vertices referred to as nodes, but I'm going to try to avoid that terminology to avoid confusion with clusters of computers, or each computer is referred to as a node. Okay, so V is a set of vertices, and E is a set of edges, and each edge is a pair of vertices: a source and a target. And so edges may be considered directed or undirected, and we'll talk a little bit more about this, but maybe it's an edge from a source to a target, or maybe it's just a pair, and the order doesn't matter.

So these graphs are increasingly common in the wild. Right, the web itself can be modeled quite directly as a graph where every page is a vertex and every link between pages is an edge. The internet underlying the web can be modeled as a graph: every computer is a vertex, and every route is an edge, or maybe even every packet. Uh, social networks, as we've seen in some of the assignments, uh, these are becoming increasingly important as a political driver and as a driver for social change. There, you know, the influence they have is pretty difficult to overstate, and this is very obviously a graph where every uh connection between two people in the social network is an edge. Uh, communication logs can be modeled as a graph: every phone call between two people is an edge. And of course, in the news recently, this is becoming quite important with the PRISM program, uh, and so many more. And so one reason these are so ubiquitous is that it really does kind of get the fundamentals of communication right: you have a big set of actors, and any anytime one actor interacts with another, that can be modeled as an edge. And so this is just a very uh common paradigm to—to, you know—that can capture the behavior of a lot of different kinds of systems.

Okay, the other reason you see this to be so—be ubiquitous in kind of a data modeling aspect is that, you know, objects and relationships between those objects, you can't really get any lower than that, right? So relations—talk about uh, you know, the relational data model talks about tables where you have records and attributes, but even here there's a bit of complexity: you have to sort of think about a schema, and you have to sort of think about every record is going to have the same schema, and so on. Graphs kind of blow up all that and disintegrate everything down to just object in relationships. And so in some sense, it's a lowest common denominator data model. Um, what we'll get into a little bit is my opinion that I think you—you throw out quite a bit when you sort of drop everything down to that level, but we'll talk about that in a bit.

So what do we want to do with these graphs? So Bordar, in 2012, wrote a paper about analyzing analytics. They tried to sort of categorize uh various analytics tasks in very—in a variety of categories, and one of the categories was graph analytics, and he broke it down into these three patterns: structural algorithms, traversal algorithms, and pattern-matching algorithms. And I think this is as good a breakdown as—as any other, so this is the one we'll use in the next several slides.

So you think about just structural tasks—structural algorithms. You know, the first thing to do in encountering a graph that you're expected to work with or understand is just to collect some basic metrics: right, how big is it? How many vertices and how many edges? And one of the takeaways I want you to have is that the number of edges is more relevant than the number of vertices when you're trying to understand the scale of a graph. So you know, many times you'll have a conversation with someone, and they'll say, "Well, I have this really big graph I'm working with." So the next question you should ask is how many edges does it have, not how many bytes, and not how many vertices. And the reason you don't care about the bytes is because there might be all kinds of other information packed into uh the labeling of these things, but that can really be factored out from the graph itself and modeled maybe more traditionally in—in a relational database. And so the performance may not depend so much on exactly number of bytes, but the graph structure—the—is a challenge, as we'll see. Okay, and so the number of vertices is—is one measure, but the number of edges is another.

So why is the number of edges more important than the number of vertices? Well, because it scales quadratically with the number of vertices, right? You can have at most number of vertices squared number of edges, and that's a really, really big number in some cases, right? If there's two billion people using a social network, well, two billion squared is the number of possible friend relationships you have, and if you're expecting to do some analytics on this graph, you're going to be processing all of those edges, perhaps. Okay, and then the second question you should ask after the number of edges is what is the highest in-degree as a proxy for really what is the degree distribution here? So what do—what do I mean by degree? Well, the—the in-degree of a vertex is the number of edges that are coming into it, and the out-degree of a vertex is the number of edges that go out of it. Okay, and so how the edges are distributed among all the vertices tends to be a driver of how difficult the graph is to work with. If they're all pretty evenly distributed, then this isn't much of a problem: you can parallelize things, as we'll see, and everything works out nicely. However, very—almost never do graphs in the wild have this property where things are sort of uh randomly distributed. It tends to be uh very skewed. So there's, you know, in a social network there tends to be a—a person who is friends with everybody in the graph, right? Very, very popular people, or almost everybody in the graph. Okay, uh, in a, you know, on the web there are pages that tend to be linked to by everyone, right? Very, very popular pages. And so this imbalance in the degree distribution is one of the challenges in working with very, very large graphs. And so if you know the number of edges, you've got one indication of sort of graph scale, and then if you know about how high—of how many edges are in the—um, you know, most popular vertex, that gives you some idea of how skewed things are.

Okay, so fine. So when you're working with graphs, these are the things you're going to be able to do: Can you just count the vertices, count the edges? Can you say, given a vertex, can I get the number of in-edges and out-edges for that vertex? And can I maybe do that for every vertex in the graph? Okay, and so if this is hard to work with, you know, this is going to be the basis for—for many other [Music] tasks.

So one structural task you can do that's a little more detailed is to construct the histogram of a graph, and you saw this in the Elastic MapReduce assignment if you completed it. So we saw that the out-degree of a vertex is just the number of outgoing edges. So some notation: Let's say for each integer D, we'll let N of D be the number of vertices with that out-degree D. Okay, so for example, in this graph, we have what is the out-degree of this vertex? It's zero; there are no outgoing edges. The out-degree of this vertex is two; there are two outgoing edges. The out-degree of this vertex is four; there are four outgoing edges. So now we can count them up. We can say, how many vertices in this graph have out-degree zero? Well, there's just one—it's this one. How many vertices in this graph have out-degree one? Well, there are three of them: this one, this one, and this one. And so on. And then you just plot D versus N of D and create this histogram. So we see one vertex at zero, three at one, two at two, and so on.

Okay, so—so why might be—why might this be a good idea to do? Well, it tells us something about the graph we're looking at. So if we see this kind of a pattern—so we might see this kind of a pattern where very few—or sorry—very many uh vertices in the graph have a very small out-degree, and fewer and fewer as you go out the x-axis. Or potentially you could see this other pattern where very few have a small out-degree and many, many more—more have a high out-degree. So this is a much more connected graph, right? Everybody tends to be connected to everybody else in this case; most people have a very high out-degree; people—most vertices have a very high out-degree. And here very few have a very high out-degree. Okay, and it could be sort of more mixed like this; it could be sort of bimodal.

So what's going on here? Well, if we see this pattern, then you can model this as an exponential distribution where D is in the actual exponent. And what this tells you is that it becomes very, very unlikely—the further you go out the x-axis—it becomes exponentially less likely to find a vertex that has that out-degree, right? So most have a small out-degree—one or a few—and as you go further out, it's much, much less likely. Okay, and so you can see this effect very clearly if you plot it with—on a log scale; it becomes linear on a log scale. Now, the thing about this distribution is a random graph has this distribution. So what—what do I mean by a random graph? Well, this is: take a set of vertices, and then choose two vertices at random and connect them with an edge; then choose another two vertices completely at random and connect them with an edge, and so on. If you follow that process, you'll get this kind of a distribution of the connectivity, right? There'll be very, very—it's very, very unlikely to construct a vertex that is connected to lots and lots of other vertices using this process. Okay, so fine. So it turns out that you don't find random graphs in nature very often. Okay, um, that's unfortunate because if it—if—if you did have a random graph, it's actually fairly easy to work with, and by work with I mean uh implement some of the tasks that we'll be talking about, say, in parallel, because you can split the edges up across a bunch of different machines and just work with them all sort of independently. But what you see more often in practice are these power-law distributions—this Zipf distribution—where there's some X that's in the exponent; you're raising the degree D to—to that exponent. And human-generated data tends to have this distribution. And if you think about it, there's at least one way to—to build some intuition for why these come about.

Okay, so instead of choosing two vertices at random and connecting with an edge, instead when you choose a vertex to connect with an edge, favor those ones that are already well-connected. Okay, so why would you bother, or why would this happen sort of naturally? Well, think about it: If you're in a social network and you join—you have someone who joins Facebook for the first time, are they more likely to connect themselves to someone who's already very popular, or are they more likely to connect themselves to a bunch of people who don't already have lots of friends? Well, it's much more likely to connect yourself to someone who's already very popular; that might be who introduced you to Facebook in the first place. Or with Twitter, are you more likely to follow people that already have a lot of followers, or more likely to follow people that do not have a lot of followers? Well, more likely you're going to connect to and follow uh, you know, you join Twitter in order to follow popular people. Okay. You can also think about this in terms of maybe the internet or the web: When you create—when you create a web page and put it on the web, are you more likely to link to sites that already have a lot of links, or not? Okay, and the answer is you're more likely to—you—it's reasonable to say that you're more likely to connect to web pages that already have a lot of links. Okay, so with this preferential attachment model of constructing graphs, you'll generate this Zipf and power-law distribution. These are the distributions you tend to find in—in nature, or on the web, whether you call that nature or not. And they have a distribution like this; they have this fatter tail—this long tail. So now it's not quite so unlikely to find vertices that have a very, very, very high out-degree. Okay, and you can see this effect more clearly on a log-log scale plot where both axes are on a log scale. I think I'm not a huge fan of using log-log scale except very sparingly because lots of things—lots of distributions end up looking linear on a log-log scale, but these are defined to be linear on a log-log scale. So you can do this kind of structural analysis; you can construct this histogram of very large graphs like the web, which Barabási et al. did in 2000, and we're probably overdue for another analysis of this type, but it's become computationally pretty difficult to uh produce these kinds of plots for the current Internet.

Okay, so here's the plot; here's the histogram of the web. And the question is, is this an exponential, or is this a Zipfian power-law distribution? And you can see it's kind of here in the description, but it's pretty clearly a power law. This is a log-scale axis, and this is a log-scale axis, and this looks pretty linear—linear. So what the authors went on to do, which I think is pretty interesting, is produce this kind of schematic of the overall structure of the web. And this circle in the middle here is a big strongly connected component, meaning that uh the pages within that component—if you can reach X from Y, you can reach Y from X for any two pages. Okay, but then there's also an in- and an out-set of vertices—pages that are kind of about the same size as the strongly connected component. So these are things that are, you know, you can reach the strongly connected component from these, but you cannot reach back—back from the strongly connected component, so they link into the main mass of the Internet. Okay, and then similarly on the outside, there are things that link from the strong component, but you can't get back, and it's about these big 3/3. And then they pointed out that there are indeed tubes that connect the in to the out directly—not going through the strongly connected component—and there are these tendrils that sort of go off uh nowhere, but these are minor—perhaps minor components relative to the main three. And then you also have these sort of disconnected components that are smaller, but this is sort of interesting to understand the basic, you know, physiology of the Internet. And it's—again—difficult to produce this [Music] now.

So what are some more sophisticated structural analytics tasks we can do with a graph? Well, one is to find the diameter of the graph. So this is the longest of all the shortest paths in the graph. So what's a shortest path? Well, given an—given a vertex X and a vertex Y, find all the different ways of reaching Y from X and take—

The shortest one of those that's a shortest path. Now do that again for all possible pairs of vertices in the graphs. The longest of all those shortest paths is the diameter. And so, intuitively, what this is measuring is, you know, the width of the graph. What's the longest sort of path you have to take to get from one place to another? Okay. And this gives us a measure of how much work we have to do when we're when we're traversing the graph. Okay. So if everything is very tightly connected, then the diameter will be very short; right, it only takes a few hops to get from anywhere to anywhere. Uh, and if the diameter is much longer, then it could potentially take longer than that. So this gives you kind of the Six Degrees of Separation, you know, Six Degrees of Kevin Bacon sort of sort of measure. Fine.

So what is the diameter of this graph here? Well, we're looking for shortest paths, so so let's look at some possible candidates. Well, things like A to F and A to B and D to C are all going to be shortest path one. So let's look a little closer at ones that's that appear to be far apart on the on the, you know, page here. So A to C, what's the shortest path there? One path is A to B, B to E, E to G, and G to C, and that's path that's a path of length four. But there's a shorter one: there's A to B, B to D, and B and D to C. And so A to C, the shortest path is three. So let's look at other ones. Well, F to anywhere. Well, you can't reach anywhere from F because all the edges point inward, and we're assuming a directed graph for this part particular exercise. Uh, and G similarly, you can't get anywhere; you can get to C, but C you can't get anywhere except back to G. So it looks like starting back from A, A to G, how many hops does it take to get there? One, two, three. So A to G is three, and that should be the longest ones. So the diameter of this graph is three.

So we can also measure the connectivity coefficient of a graph as a structural analysis task. So this is the minimum number of vertices you need to remove that will disconnect the graph. And so this you can think of this intuitively as a sense of the a measure of the fragility of the graph, right? How how much redundancy is built into it? So if you're designing a network and it turns out the connectivity coefficient of the graph is one, that means that if one M potentially if one machine goes down, you could partition the network where nobody can communicate. Okay. So if you're an advertiser, you might be interested in the connectivity coefficient of a graph if you're trying to reach as many people as possible. It could be that if a few people don't pay attention to the ads, then a whole bunch of other people won't send the message if you're sort of in viral advertising or or social media advertising. Okay. And so remember in the CAP theorem that we discussed in the NoSQL lectures, P was partitioning, right? So this was the if your if your uh system becomes partitioned, if your network becomes partitioned, can the systems still function? And so connectivity coefficient could be a measure to help you estimate how likely it is that your network is going to be partitioned. Okay.

So what is the connectivity coefficient of this graph? Well, it depends on exactly what we mean by connectivity first. So we can say that a that two vertices X and Y are strongly connected if X is reachable from Y and Y is reachable from X. Okay. And we might say that they're just connected if X is reachable from Y or Y is reachable from X. And so this is sort of equivalent to ignoring the directionality of the edges. So if we just assume that everything's undirected, then we'll be using the second definition. So let's assume that for a second. Let's assume we just mean connected here. Well, look, if if we don't care about direction of traversing, then if we remove E, is the graph disconnected? No, because you can still reach everything through this other edge up there. And so the only node here that appears to not be redundant here is B. And so if you remove B, though, you'll have two partitions in the in the network: A and F and all the other ones here. So the connectivity coefficient of this graph is is one because we can we could we can find a a vertex that if we remove it, uh it'll be a partition network. Okay. And we already discussed why you might want to compute this.

So the connectivity coefficient is a measure of the graph itself and doesn't really give us an a way to understand the relative importance of an individual vertex. And so for this purpose, there's been various notions of centrality defined. So one is the closeness centrality of a vertex, which is the average length of all the shortest paths that pass through it, it right? So this intuitively this is you can maybe compare this with the diameter of the graph, right? If the diameter is long and the average length of all the shortest paths that go through a particular vertex is short, then it's not part of the diameter of the paths that define the diameter of the graph. And so, some sense, it's maybe less central or less important. Okay. So another is the between maybe more common is the betweenness centrality of a vertex, and this is the fraction of all the shortest paths in the whole graph that pass through this vertex, right? So if you need to if you need to go, you know, all roads lead through Rome, right? If you need to go from Seattle to Atlanta in the US, then perhaps all paths go through one of two different major highways or one or two maybe one or two cities: the northern route and the southern route or something. And so the betweenness centrality of these two intermediate hubs is high. And so if you think about us a a public transportation system where all trains lead into some central hub and then go out again, that central hub will have a high betweenness centrality because the shortest path to get from point A to point B always goes through this one central vertex. Okay.

So what is the betweenness centrality of vertex E in this case? Well, there's a shortest path A to B to D to C that we found; the shortest path from A to C is it goes through there, and the shortest path from A to G, A B E G, is is a three. So if you sort of add all these up, you'll see that E is only involved in A B E G and then a bunch of ones that that are that are rooted in E itself: E to C and E to G. So the the betweenness centrality of E is three or sorry, three divided by the total number of shortest paths in the graph. Okay, it's a fraction.

So we talked about a couple different notions of centrality, and one more is degree centrality, which is just the degree of a vertex divided by the total number of edges, right? So this is the fraction of all the edges that touch me. Okay. And so this so maybe this is a good candidate for our you know, we're seeking some notion of importance of a vertex in a graph. All right. So imagine we have a social network and you know, then the degree of a vertex is the number of friends you might have. While people with more friends are in some some sense more important than people with fewer friends in the context of a social network. Fine. But if you know, say we both have five friends, well then we have the same degree centrality by this definition. But what if your five friends are they themselves much more connected than my five friends? In some sense, you should be more important than I am in the context of this social network, and this notion of degree centrality doesn't capture that. All right. So let's see if we can improve on this. Well, another notion of centrality is eigenvector centrality, which is actually just PageRank. And so if you're are familiar with PageRank or this may be another way of looking at it, and if you're not familiar with PageRank, then this is a great way to uh develop an intuition for it. So the basic idea for computing PageRank is, you know, while things are not converged, for each vertex in the in the graph, compute the rank of that vertex by adding up the ranks of all of its neighbor vertices. Okay, all the incoming edges if we assume a directed graph, right? So this allows you to say, well, look, if Barack Obama, if the president of the United States is connected to you by one hop, is your friend, say follows you on Twitter or something like that, well then you're more important than somebody who doesn't have such a such an influential uh person in the graph. You add up the rank of the president to your rank. Okay. Meanwhile, you distribute rank to all your uh friends, right? So and you do this, you repeat this uh passing of of rank of weight of importance to across the network across the graph until you reach some convergence condition, and then that convergence condition give you a relative score of who's more important than who, perhaps which which vertex is more important than which other vertex. But there's a couple of problems with this approach. So one is, you know, a one page or one person in the social network with with millions of outgoing links, if they link to me, that's somehow less valuable than a page that only links to a few people, right? So if you've got one of these uh crawlers that follows everyone in order to collect as much, you know, follows everyone on Twitter in order to collect as much data as possible, it's not very important that they follow you, right? You don't consider that you don't consider that to be very prestigious that you have some automatic robot crawler following you. Meanwhile, if you have an aggregator page that sort of links out to everyone on the internet, uh similarly, that's not very important that it uh links to you. So somehow you want to make sure that they divide their rank amongst all their outgoing edges as opposed to just give their total rank to each outgoing edge. Fine. So that's easy to fix. You know, another notion here is that well, if I'm if I'm 27 hops away from Barack Obama, that's less important than if I'm one hop away. And so we we we really shouldn't count that as very influential, and so we need some sort of a damping factor that as you get further away, it sort of lowers the importance. Okay. So you combine these two notions together, and you get the definition of PageRank as it was published, and there's a couple of variations on this, but this this is the one to know. Okay. So while not converged, the rank of a ver a vertex A is the sum of all the ranks of the vertices that link to A, but each one is divided by the total number of outgoing edges. So in this notation, we assume that there are edges B linking to A, C linking to A, D linking to A, and PR of A, the PageRank of a node of a vertex X is the is going to be the per PageRank of the vertex X; L of X is the number of outgoing links from X. And so for the page, we take the PageRank of B and divide by the number of outgoing links away from B, take the PageRank of C, divide by the number of outgoing links away from C, and so on, add all that up, and that's all the contribution to A, and then we multiply by a damping factor to make sure that we what we pass on goes diminishes over time as we get further and further away. And then this other term in this expression is just to ensure that all the ranks sum up to one so that we can sort of interpret them as probabilities. And in fact, you can directly interpret this as a probability, uh which is another way of looking at PageRank. And deriving PageRank is to take random walks around the around the internet, around the around the graph, right? So you start on a random vertex and just start walking, make a choice at random among the edges, the outgoing edges, and just traverse around. Well, if you do this a bunch of times, you can derive how likely it is that you'll spend time on some particular vertex versus some other particular vertex, and that will exactly be the PageRank. And so this is sort of, you know, all roads lead back to Wikipedia or CNN or some other very uh uh you know, important vertex in the web graph. So that's PageRank. And what I wanted to point out before we move on is just the relative simplicity of this, right? It really comes out of an intuitive notion of trying to figure out how can we measure the importance of a vertex in the graph. And so, you know, you start from very simple notions of well, maybe important means just the one with the highest number of edges that linked to it. Well, there's some problems with that. So let's see if we can fix it. You know, maybe it's the one with the uh the most number of paths that go through it, and maybe we don't care about all paths; we care about shortest paths. So gives you another notion of importance, and you say, well, that's got some problems too. You know, what are the properties we really want here? Well, maybe it kind of captures, you know, the importance of your friends needs to be added in there somehow. And you can sort of walk through this and come up with where PageRank came from. So the way it's presented, just like a lot of these things are presented in terms of a of a finished formula, and then you kind of have to work out back, you know, reverse engineer where it came from, but a lot of these things are developed very intuitively, and the formula is only used as a notion to express the intuition in a in a precise way.

So we talked about structural analytics tasks as broken down by this paper in 2012. What are some examples of traversal tasks? So one is to find the minimum spanning tree of a graph. And so that is the smallest subset of edges that connect the graph by some no notion of connectivity. So if we ignore directionality, we can talk about weakly connected uh graphs. So what is the minimum spanning tree of this graph? So we're looking for the smallest set of edges; a minimum spanning tree of this graph because there might be many that have the same number of edges in them; a minimum spanning tree of this graph. Well, we can get from A to B, and again we're going to ignore directionality, so there's actually two edges from A to B, so we take one of those, then we can get from B to F, and we get from B to E, and we get to B to D, and we get from D to C, and E to G. And so that's one edge, two edge, three edge, four edge, five edge, six edge. And so the minimum spanning tree, the number of edges in the minimum spanning tree is six. Another way to get six is go from A to B and A to F and then and then the same otherwise: B to D, B to E, D to C, and E to G. Okay. So there's two different minimum spanning trees with the same number of edges in them, and there are fast algorithms to compute this that we're not necessarily going to go into. This is sort of a guided tour of various tasks you might want to compute, but we're not necessarily going to describe the algorithms in every case. All right. So another traversal-oriented task is finding paths and circuits. And so the you know, classic example of this is Euler's bridges of Königsberg problem, where the task is to find a path where we visit every vertex and yet cross every bridge in this graph here in the picture only once. And so the observation that was made here was, well, if you enter by a bridge, you must also leave by a bridge, and you can't leave by the same one you came in on because that's the definition of the problem. So so this suggests that there needs to be an even number of bridges to every vertex, right? You have to have one to come in on and one to go out on, and then you can come back come back to this vertex as many times as you want. And so there's two sort of related results here. If you're going from the bottom one here first, if you actually want to start and end on the same vertex, well, the condition is that every vertex in the graph needs to have an even number of edges so that you can come in by one and you can leave by one, and this allows you to make an entire circuit all all the way around the the the graph. If you don't care where you start and end, you just start start on one and end on another, then it's a little bit softer condition; you can most of the vertices need to have an even number of edges, um but you can have at most two vertices that have an odd degree: the one you start on, the one you end on, because you there you only need to leave by one; you only need to come in by one. And I'm assuming undirected edges here; the definitions get slightly more complex if you talk about directed, but not not much; essentially you need to have a balance, you know, the same number of in-degree edges and out-degree edges. Okay. And so what's nice about this is a very very, you know, this is a great result because it's very easy to check this condition, right? You can just add up the the degrees of all the vertices in the graph, and you can tell whether whether one of these circuits or one of these paths exist. But to sort of demonstrate the subtlety of, you know, some of these graph theoretic problems, if you make a very slight change to the problem statement, the answer becomes a lot harder. So can we create a path that visits every vertex only once as opposed to every edge only once? Well, this is a hell of a lot harder, and the reason is is that intuitively if you think about it, you know, every vertex has lots of edges, and so it's involved in lots of different paths, lots of different possible paths through the graph, and you're trying to find one of these such paths that touches every vertex only once. Well, given that this you this vertex is involved in lots of different paths, you're only allowed to use that vertex one time, and so you can imagine that it's difficult to figure out what is the best way to use this vertex; there's a whole lot of different conditions you have to you have to consider. Okay. A related problem is, you know, assume there's a cost to traversing each edge, right? There's a distance you have to travel, for example. Can we find a path that visits every vertex only once but also has the minimum cost out of all these? And so there's no efficient algorithm that can exist for these problems, and so heuristics and approximations are the best we can do. And this this extension here is the you know, traveling salesman problem. Okay. So might be some of the uh tasks you might want to do; these actually come up, I would argue less often in a big data context, person especially this one, in part because it's such a difficult answer to compute and also it's not clear that it's all that useful, say in a social network context or in a web analytics context; you're not necessarily trying to find paths that touch every single vertex in the entire web. So this is this tends to be, you know, the only times when you're interested in touching every vertex in a graph, I'll claim, is when the graph is in some sense small. Okay. So this is less of a big data problem, but it's something to be familiar with in in if you're thinking about graph analytics. All right. Right. So one more traversal task just to be familiar with is maximum flow problems. So here the input is a graph with labeled edges indicating the capacity at each edge, and then special vertices, sources and sinks, and the idea is to find a subgraph that maximizes flow between sources and sinks. And so the observation here is that for each vertex, incoming flow must equal outgoing flow. Okay. So in this example, if A is a source and F F and G are the sinks, then you can think about a subgraph where you just have A directly to F because it's only one hop away, and so the flow between them is two. But if

You look at a path A to B, and then B to F. You get the flow of four here and flow from, or the capacity of four here, and a capacity of three here. Which means the maximum flow along this is three. Right? There's some unused capacity on on this edge, but three is still higher than two, and so that's we want to include that in the in the subgraph from from A to F. Okay.

And then to get over to G, you can do sort of a similar walk and say, "Well, one path is B to D through a capacity of five, and D to E through capacity of two, and E to G through a capacity of two." And so the maximum flow here is two. While A to B, B to D, D to C, and C to G, the maximum capacity is three. This edge is the is the is the weak link. Okay. So it looks like the max flow subgraph is ABF, DCG, or rather the edge AB, the edge BD, the edge DC, the edge CG, and the edge BF. [Music]

All right. So the final category of graph analytics tasks are these pattern matching tasks, and this is where we want to maybe spend a little bit of time, especially because they're somewhat relevant in the news lately with this prism system, and I'll try to touch on that in a bit. Okay. So here the idea is to find all instances of a particular subgraph pattern. And so a very simple subgraph here is two vertices that both connect to each other. Okay.

And so here you may have conditions on the vertex labels or on the edge labels in order to more precisely specify the exact pattern you're looking for, but you're looking for all instances of this pattern across the graph. Okay. So how many times does this pattern appear in this graph? Or what are all the instances in this graph? How can you instantiate this pattern there? Well, here's one from A to B. You instantiate $x = A and $y = B, and that seems to fit. And then G to C seems to fit, $x = C and $y = G. And then actually, if we're not careful, you have or perhaps this is what you want, but generally you don't, you'll have duplicates of this where $X can be B and $y will be A, oops, A will be A and $X will be G and $y = BC. So there may be four instances of this pattern, only two of which are in some sense unique.

So a popular pattern matching problem is to find the triangles in a graph. And so a triangle is a sequence of three vertices that are connected to each other. So A connects to B, B connects to C, and C connects back to A. And so the total number of triangles is a measure of connectedness. There's lots of algorithms to compute this measure, to count the number of triangles, and it's a popular challenge problem, kind of benchmark for computer scientists to compare different systems and compare different algorithms. Its utility in practice, as far as actually analyzing, you know, getting information out of a graph, is not been made so clear to me when I when I talk to people who compute this. It seems to be more of a again a good benchmark problem for systems as opposed to a actually informative measure for social network analysis, but that doesn't mean that's not to say that it's not used ever. So I'm not going to, for that reason, I'm not going to go into a lot of detail in the algorithms here, but a key idea to remember here is that is that a naive algorithm will actually find the same triangle three times. Right? A connects to B, B connects to C, and C connects back to A. And then BCA, and then CAB. You are all logically the same triangle, and that they involve the same nodes, but if you're not careful, you'll find these all of these. And so this gives an opportunity to come up with much faster algorithms. Um, I think the other reason why it's studied in a lot of detail is that it's the simplest it's perhaps the simplest possible pattern you can find, and so it's a good starting point to do more complicated pattern analysis. And in fact, the pattern analysis problem in general is a very difficult problem, it's a very expensive problem, which leads to a bunch of approximation techniques. And in fact, even for triangles, there's a variety of algorithms that don't count the exact number of triangles but give you a good approximation with certain bounds. Okay.

So this is a very rich area of research, but I I think probably you'd be more interested in the pattern matching problem in general. Okay. And also maybe I'll point out that you can extend this notion to cycles that involve more than four vertices, more than three vertices, uh, and things change a little bit, but some of the techniques stay the same. So let's look at another pattern match example. This one's a simplified version of a real example that comes from work with some of our collaborators. Okay.

So here, you know, given a graph with edge labels, is the extension we're going to make. Instead of just source node, source vertex and target vertex, we're going to assume that there's going to be a label on that edge as well. So a third attribute in this table, if you will, and we're going to be looking at rel, what this label represents is relationships like uh an object, you know, someone knows someone else. And in this case, drug X interferes with drug Y, and so that label is interferes. So you sort of know what the relationship is instead of it being a big anonymous relationship, or say in the case of Twitter where you assume that all the relationship ship are the same, it's just follows, or in Facebook every relationship is just friends, or in the web every relationship is just links to. This one now they're multiple different relationships being coded in the same graph. Okay. And so this is a slightly more realistic case when you're trying to do real data analysis. All right.

So here we might say that drug X interferes with drug Y, and drug Y regulates the expression of gene Z, and gene Z is associated with disease W. And so now maybe a pattern that we want to look for is find all drugs that interfere with some other drug that is involved in the treatment of some disease. Okay. And of course, you can put other restrictions on here too, or maybe you're looking for a specific disease, or you're looking for a specific drug, but now we're just looking for all patterns of this type. Okay.

So pictorially, the query maybe looks like this, where you know we want to find an edge linking two vertices that's labeled with interferes with, that's then connected to, or one of the outgoing edges of that vertex Y is connected to a vertex Z through an edge labeled with regulates, and then that vertex Z is connected with a vertex W that through an edge labeled with associated with. Okay. And we want to find all instantiations of this pattern. All right.

So I'm not going to yet talk about algorithms to do this. I want to talk more about languages to express this pattern, and some of you with a database background may already be thinking about how you might do this in SQL, and that's one of the examples I want to show. So the first pattern language I want to consider is SPARQL, which is a query language, D sort of SQL-like, derived in association with this resource description framework, and you worked with some of this data in the elastic map reduce assignment if you completed it. So resource description framework RDF defines a formal data model around the idea of triples, which are really just edges in a graph, labeled edges in a graph. And so you logically you can think about a table with three columns: subject, predicate, and object. And the subject column refers to vertices in the graph, and the object column refers to vertices in the graph, and the predicate is the edge label. Okay. And so there's a lot of work that went into the formal model to define this, but I think it's most useful just to think of it as a labeled graph. All right.

And so the query language ends up looking like this, where you can say select variable names where, and then define these triple patterns. And in this case, all the triple patterns look similar in that they all instantiate the predicate with an actual literal, and all the vertices are variables, but you don't have to do this. You could have a variable in place of the predicate, and you could have literals in the place of the vertex representations as well. Okay. So this says give me all the X's such that X interferes with Y, Y regulates Z, and Z is associated with W. And so if this was actually our data set, then we might return this invented drug named terrazine, because we can trace a path: terrazine interferes with betamin, betamin regulates this gene, and this gene is associated with this disease. Okay. And there might be, you know, billions of these triples. Let me give you another example of a pattern expression language that comes up in database courses in computer science but is less often seen in industry, although it's starting to make a comeback, which is one of the reasons why I want to mention to you, make your make sure you're aware of it. Okay. So it's called Datalog, and it's based on a logic programming sort of paradigm, uh, but simpler than than general-purpose logic programming languages such as Prolog. Okay.

So here to express our query in Datalog, we assume a relation R, which is just the same structure as the triple table we saw for SPARQL. Okay. And I'll show you another formulation in the next slide. So here the pattern, the syntax here looks not all that different than uh SPARQL. For each predicate we have an instance of R, and we are looking for give me all the X's such that X interferes with Y, Y regulates Z, and Z is associated with W. And we use three instances of this relation R, and it's essentially can be interpreted as a join. In fact, that's L that's literally how it's going to be implemented in most Datalog systems. Okay. So you're going to join R on Y = Y, join R again on Z = Z, and then return the uh instantiations of the variable X. Now, so you got a relation R with three attributes, you know, why can't you query this in SQL? And there's no reason you can't query in SQL. So you can imagine loading this table into a database and rewriting this query like this, where you say a three-way join on the relation R, and I've given them aliases here: I for interferes with, R for regulates, and A for associated with. Then for each one of those relations, make sure you filter to the tuples that correspond to the predicate you're interested in. So make sure the I tuple are only those tuples that have the predicate equal to interferes with, and so on for regulates, and so on for associated with. And then you have to add a couple conditions for the join: make sure that the object of the I relation is equal to the subject of the regulates relation, and make sure the object of the regulates relation is equal to the subject of the associated with relation. And then finally just return the subject of the interferes relation. So all these things are equivalent, and that's one of the points I want to make, but I'll come back to that in a [Music] minute.

So we implemented this query in three different pattern languages, and the fact that we could do so suggests that there's something in common between them all, and in fact there is. What it is is the relational algebra, and this is one reason why I've been trying to hit this throughout this quarter is that you know if you put your relational algebra goggles on, the whole world starts to look like relational algebra, and you can start to see that these languages are not really all different, and you can kind of look past the details of the syntax and see that what's actually going on is a relational algebra expression. So in this particular case, that expression might look like this, and I say might because I this is not necessarily a rigorous uh statement here on the slide. So there's two joins, as we saw, three instances of the relation R, and this symbol means a select condition where we're selecting for the P predicate P = regulates, and here the predicate P = associated with, and here the predicate P = interferes with. So now we have just the tuples that have the predicate with interferes with, just the tuples that have the predicate equal to regulates, and just the tuples that have the predicate associated with. And then we just do the join where the object of this one equals the subject of this one, and the object of this one equals the subject of this one. All right. And so this, you know, if you look back on the earlier lectures we talked about relational algebra, hope you can convince yourself that this is will produce an equivalent result. Now, as we said with the relational algebra, this is actually a specification of the order in which the operations should apply, while the other languages was more of a declarative expression of what the result should be, but not necessarily how to get the result. And that's generally a difference between the algebra and these languages. One of the benefits these languages give is they try to put aside any spec any specification of exactly how it should be implemented and just specify the conditions that must be true of the result, and that's what we mean by declarative languages. All right.

So fine, maybe they're all maybe all three of these languages are equivalent, but I'd argue they're not. They're actually there's a benefit to the SQL implementation and the Datalog implementation, which I'll try to motivate by rewriting the query in a slightly different way. So imagine now, instead of having one big table called triples or called R with all the edges in the graph, imagine you had three different tables that came perhaps from different sources or different databases that you would combine together into one database, and each one of these tables represented different parts of the different parts of the original graph. So you had an uh drug interaction database that had a relation interferes with and just T with with two columns in it, you know, where the semantics of each tuple was drug one, the drug in the first column interferes with the drug in the second column. And from a completely different database, you had a uh uh facts about what what drugs regulate what which genes. Perhaps this is mine from the scientific literature, perhaps this is uh drive from one of these public databases where some of this information is tracked, and so on. And then third, you might have a different database associated with or recording what genes are associated with which diseases. And so this is a very likely scenario, I claim, and in fact, again, this is derived from an actual example we have from working with our collaborators, and it's very much true that these different kinds of of relationships came from different sources. And so it's actually more likely for you to have them in this form than it is to for you to have them as one big graph. You actually have to do some pre-processing to merge them in together as one graph, but until you do that, until you do that merging, you can't use that SPARQL language, and in fact, you can't use any graph language, and you can't really use any graph database. Right? They only work on graphs. And so while it's a very general data model for capturing arbitrary relationships, it's not clear that the world is always represented as graphs in its in its source representation. It represents a bunch of tables that happen to have graph edges encoded in them. And so being able to work with them in the original format is a strength, and you can do so in say Datalog. So here the query actually gets a little bit simpler. You have a join between these three separate relations, and you no longer have to sort of query on uh specify the the the predicate that defines each one. Okay. And that's perfectly fine if you have a mix of of graphs and relations. You can handle both with Datalog, and in fact, you can process them the same way as you would any other query with the relational algebra with your implementation of the relational algebra. Similarly, similarly in SQL, you SQL has no problem with expressing this query if it was if the data was represented in this form. You would do a join between these three tables, and you just have the join conditions, and the query actually gets a little bit simpler. So I guess my my what I want to bring home is that a graphs tend to not appear in the wild isolated. Right? They're not sort of free ions. They tend to be uh applications tend to be hybrid. They have some tables, they have some relations, and they have some graphs. And being able to work with both of them uniformly is an important strength. And so I think this emergence of graph-specific systems, uh, it while it does suggest that there's performance issues sometimes with modeling these traditionally as relations, and that's one thing we'll talk about in a in a couple of segments, it's not clear to me that capturing the entire world as a big flat graph is necessarily the right thing to do. It seems like you want a model that can do both relations and graphs and sort of interchange between them. Okay. Make one more point about SPARQL before we move on to some more complicated examples.

So summarizing what we sort of said, while SPARQL is designed for graph query, there's a few problems that I want to point out. One is this notion of algebraic closure that we brought up when we talked about relational algebra. So the input is a graph to SPARQL. You can query a graph, but the output, if you'll if you go back to the slide on SPARQL and you look at the result, it's actually a list of records. It's no longer a graph. It doesn't have to be these triples anymore. And so therefore I can't take the results of one SPARQL query and then again query it with SPARQL. The only thing I can query with SPARQL is a graph. And so one way to say this that maybe is a little bit pedantic but is more technically correct is it's not algebraically closed. It returns a different type of thing than it than it takes as input. But this is a big disadvantage, as we've seen. Right? You want to be able to chain queries together uh whenever possible. This is what gives you the cap a foundation for features like logical data independence, which we argued back in the relational U lectures as a really a really critical feature. Okay.

Second, I'd argue that there's actually limited expressiveness, and we'll see some examples of this in a little bit, but you can't do graph these graph traversal tasks that we talked about. Most of these you can't express in SPARQL. Since version 1.1 in SPARQL, there is support for these path expressions that can that can express some forms of traversal, but it's not clear that all that all the general recursion is supported. Right? And you need general recursion. You need general graph in order to implement these graph traversal tasks. You need some way of sort of walking over the entire graph as a whole, and SPARQL doesn't necessarily provide that. Okay. And then as we just pointed out in the last slide, if your input starts off as tables, before you can even touch it, you have to shred it into triples and model the whole world as a big pile of graph edges, while what's nice about graphs is you can actually do that. There's always there's always a way to sort of shred it into a graph in some form, but the process of doing that might blow it up by a factor of three or a factor of six is what is what we see in practice, depending on how exactly how you model things, depending on what uh your your table structures look like, but this is you know a a tough hill to to climb to try to recover that performance that you give up just by shredding it into a graph. So again, so I think what what this tells me is that we want a system that can handle both graphs, can express graph traversal tasks, which SQL is not great at, and we'll talk about that in a moment, but neither is SPARQL, um, but but can also work with tables in whatever form they they're in. Okay. [Music]

So these graph pattern search problems were in the news in June 2013 pretty heavily associated with this prism system being developed by the NSA. And so an article in Business Week described the kinds of tasks that they're interested in doing. And by the way, the technologies that they're using in this are things you've heard about, or as far as far as we understand. So the system

Acumulo, I mentioned in the new NoSQL lectures, was actually developed by the N-Say and then released open source and then commercialized uh after that. And that's kind of the underlying platform. And then the kinds of applications they want to do using this Cumulo system and other systems uh are of the type that we've been describing in terms of pattern search. So let me give you an example of that.

So in this Business Week article, they talk about, you know, in October a foreign national named so-and-so purchased a one-way plane ticket from Cairo to Miami, where he rented a condo. Then, over the previous few weeks, he had made a number of large withdrawals from a Russian bank account and placed repeated calls to a few people in Syria. More recently, he rented a truck, drove to Orlando, and visited Walt Disney World by himself. The point they wanted to make in the article is that individually none of these activities would raise any flags, but collectively they might. They might be worthy of closer inspection. And whether you agree with this or or not—maybe you'd say that this does not warrant further inspection—but just trying to state the facts of what of what they're doing with the system without putting any judgment on whether it's the right or wrong thing to do.

So you can encode this at—you can encode these facts in this language, say Datalog, although you could also do it in in, you know, as as a graph, as an RDF graph. And in fact, that's actually a little closer to what they're actually doing, but you know, you start off with a database of flights that the government has access to. So you know that they bought a flight from Cairo to Miami, and the last name was this and that it was one way and that it was on this date. And you also know that they made some withdrawals; there's multiple records here uh for various amounts from some bank in Russia and various states. And what I didn't include here was the calls to people in Syria, although I probably should have, because that's perhaps the the biggest flag, but you could write that down too. You could say, "Call from uh this person to some other person where location of the other person is um Syria." So these are a representation of all the facts that they have access to.

And the point I want to make is that the aggregation of these facts into an alert of some kind—into a "this is worthy of further inspection"—can be expressed as a query in these various languages. And in particular, I'm going to talk about Datalog here. So maybe one—you might flag a person, and this number one is just a token to say that this is one flag, and this is a date associated with the time that was flagged. In case you want to do further analysis, this might become clear in a moment. You you raise this flag if a person bought a flight from some origin to a destination where the origin was one of the flagged airports—I'm making this up—and the destination was a US airport and the ticket type was one way. You know, obviously this alone is not necessarily suspicious, but it's perhaps a first step—is that from a, you know, airport that we sometimes monitor more closely to a US destination and it was one way. Okay.

Then, you know, you might build a table of foreign—with—you might express a query producing foreign withdrawal that are the sum total amount withdrawn from a foreign bank where individual amounts were greater than a threshold because maybe you're trying to cut out small small withdrawals. Okay. And so this says, assuming we're building off this withdrawal table, we add up the total for each person coming from a foreign bank. Okay. This could maybe be called "Big foreign withdrawals" instead of just "foreign withdrawals." Okay. And then the flags are perhaps associated—well, when the total amount—all these withdrawals are greater than some fixed threshold. Here I've said 10,000; maybe that represents a flag. And notice that these flags are the same relation as these flags in Datalog. It's okay to have multiple rules like that, and the semantics of them is you're going to union all these results together. So you could imagine expressing this in SQL as well, where I query for a bunch of records and query for another bunch of records and then union the results together. That's what's going on here. All right.

And then we skipped the conditions on the calls to Syria, although again those would be easy to do and probably good examples to include. But maybe we have this database of all the vehicle rentals with attributes, you know, the person who rented it, the vehicle, the origin, the destination, and some kind of a date. And so we write a query producing yet another flag when someone rented a vehicle that—where the destination was some important location. And this one's probably not the greatest example of of something that would generate a a flag, but it's something you could look for, and you can imagine making this making this a little bit more complicated. Okay. And so all these flags together, you can write another query in Datalog, and again I haven't told you too much about the details of Datalog, but what one thing you'll notice here is that I'm using aggregations in the head of the rule, just like you can in SQL. So "select person, sum(flag), min(date), max(date) group by person" is the same is the is the same semantics as what I'm showing you here. So if we add up all the total flags, now we have a relation with people, their total flags, and the date range for which those flags occurred. This won't get you exactly the right results because we didn't really filter much on dates, but you can see the argument I want to make is that it's not too much code, it's not too much work to try to express these English questions you have over this massive graph in terms of a logical language like this. Okay.

And so maybe finally the alerts—things that are that are warrant more human attention by some analyst—are things where the max(date) minus—you know, within the span of just 10 days—the total(flag) is greater than say three. And again, one problem I'm sort of pointing out with this is this is giving you the total across the entire range of time for that person, and so you may want to bucket this by weeks or months, and I haven't expressed that here. Okay. So what I'm hoping to do is wet your appetite that these kind of rule-based logical languages can work with a big graph, can work with a lot of relations, and can express fairly complicated conditions. And they're kind—in some sense—they're all you need if you have a way of implementing this at scale efficiently. This is kind of all you need to do fairly advanced analytics. Okay.

So let me give you one more example of a Datalog query. So we want to know who contacted who and when they contacted them, but we don't really care how they did. And this is a simplification of of a of something we saw in the previous example. So we say, "Person one contacted person two at time at some time" if person one sent an email to person two at some time. We also say, "Person one contacted person two at some time" if person one called person two at some time. And then finally we say, "Person one person contacted person two" if they send a text message at some time. And so the point here is these would most likely come from three very different sources, right, as the government is doing whatever they're doing to get email—again, whether you agree with this or not—that's one company or one source; another source is who called who; and a third source is who sent a text message to who. And so combining all these together doesn't necessarily take a lot of work; you can express these in these high-level languages. And this is, I would argue, the the right way to approach these problems as opposed to a lot of low-level code.

Okay. So let me give you one more example. Who could have known before June 3rd that some event was going to happen? Maybe you know for a fact that someone named Sam knew. Okay. So you're starting from that point. Well, who else could have known? Well, using this same trick we used in the contact to build up a contacted relation, you can do this again. Well, we know person two knew if person one knew and person one emailed person two before June 3rd. Sorry, that's the other condition we're looking for, right? And we can also argue that person two knew—potentially knew—if person one knew and person two met with person one before June 3rd. And so the point I want to make here is that we've referenced the head—the relation that we're creating new—we referenced it in the body of this rule as well. So there's a recursive relationship now, right? It starts with Sam and then basically find all the people that Sam emailed before June 3rd, and they're in the final result; and then all the people that those people emailed before June 3rd, and they're in the final result, and so on. And you can do this with "met," and you can do this with "called," and so on. So this recursive—this recursive relationship—this self-reference is the difference between Datalog and SQL. You actually can express this kind of thing in SQL; there's—Microsoft calls them Common Table expressions, and you can use the WITH clause to do this recursive stuff. But you'll find if you try to do this in practice that the implementation of those features is a little bit poor in many of the commercial databases, and it's—there's various limitations. For example, you can only have a depth of 100 recursive steps, which is sort of arbitrary and and much too small for many of these applications. You also find that the performance of these varies widely and and is not particularly good. So it doesn't—it's not clear that the that the customers of of relational databases have been demanding these features, but I'd argue that increasingly this is what people are interested in. And my evidence is examples like we just saw from the news—the fact that graph-specific database systems are emerging. You know, Neo4j is is getting very very popular; there's various systems for processing graphs on top of MapReduce, and we'll talk about a couple of those uh and so on—RDF systems, you know, these so-called triple stores. So the fact that graphs are becoming more and more important uh suggests that this ability to traverse the graph recursively is becoming more important, which motivates perhaps a move from SQL—relational algebra languages—to this Datalog—relational algebra language. And so I—my prediction is that you're going to see Datalog pop up more and more often uh in industry. [Music]

Okay. So let's take a step back and see where we are. We talked about graph tasks in general, gave an example of constructing these histograms, talked about structural traversal and pattern tasks, gave PageRank as an example of structural—both a structural and a traversal task—and then talked about pattern languages in SPARQL and SQL and Datalog, gave a few more detailed examples of Datalog motivated by uh what's been going on in the news in June 2013 related to the PRISM system. But what we haven't talked about is how to implement much of this, especially at scale. So that's what I want to do next. We're going to stick with Datalog for a moment and think about how to actually implement those kinds of queries in MapReduce and then talk about how to implement PageRank in MapReduce.

So way back towards the beginning of the course, we talked about how to implement relational algebra operations in MapReduce at scale, and we showed the sort of connection, you know, between languages like Pig and the relational algebra. What databases do is obviously the relational algebra, and what you can implement directly in MapReduce. So there seems to be this kind of relational algebra uh DNA in a lot of these large-scale uh uh programming platforms. However, all of those cases we never had anything that had to loop, that had to do recursion, that had to do iteration. And now that we're talking about graphs—as we sort of pointed out—that traversal of these graphs is really the salient feature of working with them. And so it came up in traversal tasks, and it came up in uh pattern languages in Datalog. We saw examples of recursive Datalog programs without talking much about how they would be implemented. So I want to cover that a little bit now.

So given—if you have a recursive Datalog program that looks like this—so you can say this is an edge relation that's just linking an arbitrary vertex x with an arbitrary vertex y. Every pair of edges is stored in a relation called Edge, and I write this program. This program says, "Find me all the edges connected to the vertex label W," and here we have a vertex label W, and put those in a new relation called A. Then also find me additional values of A in this manner: for every vertex that's already in A, go find me an edge that leads out from that vertex and give me a new generation of vertices. So this is now a recursive Datalog program, but what you can think about it intuitively—what it's doing is traversing this graph in kind of a breadth-first way, right? So first we fire this rule, which just says, "Out of all the vertices, select the one with W," and we know how to do this; we could write this in SQL, I would hope, right? We we can write this in MapReduce; we could write this in Python—"Find me all edges where the first position is has a label equal to W and call that A z," or "Find me everything that's connected to W, call all those collectively A z." Next we go to this rule, and now we have to join all the ones we've already found with the edge relation to produce a new generation of vertices. For each node in A z, find all of its neighbors, and then in step two we fire this rule again. In—for each node in A1, find the neighbors, and so on. So we keep finding more and more vertices in this graph as we go one generation away. And that's naively how we would—how we might evaluate this recursive program. That's what this—that's what the meaning of this program is. Okay.

But there's a problem here. What if there's a cycle in the graph? Well, at generation one we'd find Sue; at generation two we'd find Tom; at generation three we'd find Lynn; and then at generation five we'd find Sue again, and so we would just keep going. So we need one more piece, which is to remove all the ones we've already found previously. So let's look at this again. So this is called semi-naive evaluation. So here's this reachability query that we were just looking at—"Find me everybody that's connected to everybody that's in the in the social network of of some vertex labeled A," right—everybody everybody that's reachable from from A. So here's how it would work. We're going to have these Delta relations, which are just the new gener—just everything found in the new generation, right, just like those colored levels were in the previous pictorial representation. So while we're still finding new vertices, we're going to keep going. If if at any point we don't find anything new, then we know we're done, and we can stop, and we can return the result. Okay. So while we're finding new things, let's call A to AI the union of all the delta that we found previously—iteration zero union with iteration one union with iteration two and so on. And if you're not familiar with this notation, this just means think of it as concatenation in a programming language, right, except you're also going to remove duplicates. All right. Then Delta AI is the previous new results joined with the relation R, right? So this gives me one more generation, and I'm expressing this in the relational algebra notation of join. So that's—we showed pictorially a moment ago. However, now what we also want to do is remove any duplicates; we want to subtract out anything we found in any previous generation at all. And this is in order to break cycles. If we've already seen that—if we already found Sue, then we don't want to find her again. All right. And then we increment this counter so that we can keep track of everything. And then our final result, when we're done, is this AI for whatever I is at the end. And so I claim that if we're going to do this in MapReduce, which is what we're trying to build up to, then this line is the important line. This line is actually pretty easy in MapReduce because of an implementation detail—a union of a bunch of different data sets, if they're known to be disjoint, is actually literally just concatenation of the files, which sort of happens implicitly in in MapReduce. And I'm not going to go into much more detail in that, but suffice it to say that this line is—can be arranged so that it's not very expensive; it's essentially free. But this line is where there's a lot of work going on. So let's look at what—let's break this down and pretend like—and show how this is going to be implemented in MapReduce. All right.

So it's actually two different MapReduce jobs—one to do the join and one to do the difference. And we saw this in the lecture on Pig where join was one operation, and we didn't show a Pig operation corresponding to difference, but it's—you can implement it using uh grouping. Okay. But we did see that generally one operation and another operation would turn into two different MapReduce jobs chained together, and that's the same thing that's going on here. So what happens with the join is we have the Delta A from the previous iteration along with the the the very large Edge relation, right? This is billions of edges perhaps spread across all sorts of computers, and we process them all in parallel, spray them across the network, and per—and implement the reduce phase in order to compute the join. Then, do the difference; we find everything—we just see everything we just found from the join, spray it across the network again along with everything uh that we've ever seen before—everything in this AI, everything in the union—and make sure that—make sure we remove duplicates. And you implemented both of these things or specified how to implement both of these things in the MapReduce assignment; you showed how to do a join, and you showed how to do a uh duplicate elimination essentially, which is—which is what this is doing. Okay. And then the only new piece we need, which is where MapReduce gets a little bit of—it becomes a little bit of a poor fit for this task—is that you need some sort of external driver program to control the iteration, to check and see if there's anything new. Okay. MapReduce can't do loops in and of itself, so you have to do something outside of the system. All right. So again, two big steps: compute the next generation of vertices or nodes, and remove the ones we've already seen. All right. So this is fine, and this works, but there's some performance issues that are pretty significant, and we'll talk about that next. [Music] Time. All right.

So if this is the basic idiom for implementing recursive programs in MapReduce, maybe we're done. Well, there's a couple of problems here, and here they are. First, on every iteration, right, we're going to do this over and over and over again as we traverse the graph, and the number of times we're going to traverse the graph is actually the diameter of the graph, which we talked about. Well, on every iteration we're going to process all billion edges in the graph in the map phase and shuffle them across the network to the reduce phase in order to compute this join. This wasn't so bad if you're only going to do this once, but if you're going to do it every time, there's no useful work happening in this map phase; you're just reading the edges off disk, assigning the key to the—you know, assigning the—identifying the join key, emitting the appropriate tuple, and sending across the network to the reduce phase implementing a standard join in MapReduce, which we did as part of the homework. So this is extremely wasteful. The second point, which is a a little bit more subtle, is that the answer set AI is growing at every iteration, right? You find more—you find more and more answers, and as soon as you stop finding answers you're done. Well, this is getting bigger and bigger and bigger over time, so it's not completely static, but all the old values that you've already seen before are read off of disk and shuffled across the network in the same way.

In order to try to remove duplicates, and if you've already done that once, you shouldn't have to do it again. So the solution here is to fill in some sort of a cache on the reducer side of the map reduce program. So instead of shuffling this across the network, we're going to shuffle it once in the first iteration and then read it off of disk in the second iteration. And with a variant of this trick, you can do the same thing here where you'll read it off of disk and then append more new tuples back to back to the same cache right as you're done. And with some careful thought, you can arrange for this to happen within the map reduce framework—sorry, not within, by extending the map reduce framework—uh, and still keep a map reduce programming interface. And this is what we did as part of our research for this system called Haloop, which is to add iterative capabilities to the Hadoop map reduce system. Okay.

And one of the, one of the applications that we did with this was to implement DataLog. All right. And so this makes a pretty big difference. So this is a plot of runtime, and this is iteration number. So this is just the time it takes to do each iteration. And without the cache that we just described, every iteration takes about the same amount of time in this particular data set, which was uh a a variant of the same one you processed in the elastic map reduce assignment. With the cache, the first iteration actually takes a little longer because we have a little bit more work to do; we have to actually have to prepare this cache. But subsequent iterations take far, far less time because you don't have to map and shuffle that huge relation, that huge edge relation, across the network anymore. So this ended up being, well, really arbitrarily faster because the more iterations it takes, the better and better, the more and more difference it gets in the overall run time. With a variant of that trick to also optimize the uh duplicate elimination step, plus another set of optimizations that had to do with using the map reduce framework in sort of an intelligent way, we were able to sort of get this pretty horrible performance for raw vanilla map reduce on iterative programs and get it way down to something that is actually kind of approaching the raw overhead of just running a a Hadoop job; meaning, you know, you don't do no new, no useful work with the Hadoop job, you just launch a task on every on every machine in the cluster and do no useful work and then shut down. Okay. And that's what this bottom line is.

So what I think the takeaway here is: one is I just want you to internalize that trick, but the other thing is if you're using raw Hadoop, if you're using—I shouldn't say raw—if you're using map reduce right out of the box, it's not great for iteration, mainly for this reason. There's actually a few other optimizations we explored in in a couple of papers, but this is the one that makes the most difference: is the fact that you, you there's invari—quite frequently—there's going to be loop invariant data that you need to process, and just to wastefully reprocess it on every iteration uh turns out to be a killer. Okay.

And then one more point I want to make about this before we move on is that the number of new tuples discovered, the new uh results discovered on every iteration tends to have a a pretty standard pattern, which is a result of the degree distribution of common graphs found in practice, which we talked about in this in the histogram segment a little while ago, go. So this plot is on the y-axis is the number of new results discovered, and the x-axis is the iteration number. And what you can see here is that in the first few iterations you quickly start to find an enormous number of new results, right, and notice this is a log scale, so this difference is really, really huge. But then pretty soon it tapers off, and you're just kind of pinging along finding smaller and smaller sets of new results, but you're not done yet either; you're still finding new stuff, but you're not finding much new stuff. So this is really, really rough for map reduce because every one of these iterations way out here in this in this long tail, this endgame as uh Man Fra and Om Man called it in a paper, uh you still have to pay the overhead of launching Hadoop on a huge cluster and sort of processing and checking for things even though you don't actually find that many more results; right, most of the results you've already discovered. So fine, that's one point. The other point here is that this does make sense because what you're doing is you quickly get to this—within a few iterations you're going to get to this middle part of the graph that's connected to everything—and you've—the fan out is huge—and you've discovered everything you're going to hit one of these really popular uh vertices that's connected to everything, and then once you're past that you've pretty much seen everything you're going to see, and you quickly taper off. Okay.

So one thing to think about is what to do about these two different regimes. You're in one regime where you're doing a lot of useful work and one regime in this endgame where you're not doing very much useful work. And there's a couple things you can think about here: one is, you know, it may not be unreasonable to just stop processing when you are no longer producing that many results. This would produce the wrong answer according to the program, but it might be reasonable in a lot of cases if you're if you're mostly looking for an approximation; you can get a pretty good approximation after the first several iterations. This extra work is not doing you that much good. Another approach would be to scrap map reduce and try to find something that had less overhead on a per iteration basis. And so there's a system that, for example, we're working on now that doesn't have this property; right, the the runtime is sort of proportional to the number of tuples discovered as opposed to having this very large fixed cost just to launch a job at all, which is which is a problem with Hadoop. Um, still another way is perhaps to change strategies in this regime; you process it as we've described in this later regime; you actually might try to do more work per iteration; for example, don't bother checking for duplicates because you're only finding, you know, 100, 100 new tuples anyway, why bother even checking for duplicates; just keep going and going and going and going for a while to save the number of map reduce jobs you have to you have to do. And so we've explored uh these various options, and they all work to to varying degrees. Okay. [Music]

All right, I want to give a quick aside on representing graphs. We've sort of been assuming implicitly that we're representing graphs in this way with a table with two columns: one source and one target, maybe some other columns representing, for example, an edge label, but every edge will be explicitly represented. Okay. And so this makes sense because it's easy to to manipulate with a relational language, which is what we've been sort of talking about in terms of pattern matching tasks. And so this is the edge table; we'll call this the edge table representation of this graph here, where A and B is there, and B back to A is there, and so on. Okay. And you can process this as we've seen; we can do pattern matching, but we can also do the structural tasks pretty simply; we can say find the top five highest in-degree vertices using a group by query, right, for from this edge table, for each target count up the number of sources, group by target, and then select the top five from that. And this is using uh the syntax for top five from um the SQL standard as well as Microsoft SQL Server; other commercial databases use—can express this in a slightly different way. Okay. And you have to order by the edge count here, which is why we do this as a nested query. So fine. So this table gives us a lot of flexibility in how to process it, but there's some cost that we bear to do this. And so what you actually see more often in programming language libraries for working with graphs is an adjacency list representation. And so for here, for each source, it's—each source is associated with a list of all the adjacent vertices. So here with A, you'd be associated with a list of the vertices B and F, and B would be associated with the list A, D, E, and F, everything that's one hop away. Okay. And so this o—the overall space required for this representation is less, which can make a pretty big difference in performance. So as an example of how to use this representation, you can think about a map reduce program; it's a little bit harder to think about how to do this in a relational database, for example, because you can't—without directly and naturally—you can't express this list construct; there's various extensions and proposals and so on to do this, but this essentially it breaks first normal form, which I won't go into, but it's no longer really a conventional relation if you if you have this nested collection structure as one of the values. But in map reduce this is perfectly fine; we saw this before, right? There's a key and a value, and the value can be anything; it could be a bag of words; in this case it's a list of neighboring vertices. And in fact, in the libraries for map reduce that work with graphs, this is the most common representation you'll see. And in fact, even in the some of the original work with map reduce to express PageRank, which we'll talk about in a bit, they assume an adjacency list representation there as well. So for this same task of finding the top five highest in-degree vertices, you imagine a map program that takes in a vertex and adjacency list and produces a key of the adjacent vertex along with the key vertex. So you just reverse the direction. Okay. So for for B and F, the output would be B mapping back to A, F mapping back to A, and so on; just reverse the edges. And then on the reduce side it'll receive a list of a vertex along with a list of incoming edges, and then you can just count them up and produce that as your result. Excuse me, you can count them up and produce that as your result. One final step is to take the top five, which would actually be a second map reduce job.

The last representation you'll typically see is an adjacency matrix, and this is really only useful if you have a fast, efficient representation of matrices and you're trying to manipulate the graph as a matrix, but these things exist. And the other nice thing about this is it sort of exposes the equivalence of a graph and a square matrix, right? So a square matrix has all same number of rows in columns, and so how to represent a graph as a square matrix is: for each row, each row corresponds to one vertex, and each column corresponds to one vertex, and you put a one in that cell if vertex row is adjacent to vertex column. Okay. And if you have an undirected graph, then you'll have—then this will be symmetric, and if it's a directed graph then it may not be. So A is adjacent to B, which is why there's a one here, and B is adjacent to A, which is why there's one here, but B is adjacent to D, and D is not adjacent to B. Okay. And you'll also see that this is always going to be pretty much always going to be a sparse graph; lots and lots and lots of zeros; not everything; it's rare for a vertex to be for all vertices to be connected to almost everything. Okay. So you have sparse, and we—if you remember back to the to some of the work we did with relational databases, and we showed how to represent matrices in databases—that once you have a matrix you get access to processing things with linear algebra, and you might get access to fast libraries that already know how to work with matrices and linear algebra operations. But what a lot of those libraries do under the sheets is take a sparse matrix and represent it in a way that doesn't require you to actually materialize all these zeros, and those sparse representations are going to look a lot like the previous two representations we just saw: an adjacency list or an edge relation. So in some sense it's, you know, you're you're you're moving things into matrices in order to get the access to fast libraries for working with matrices, but what the matrices are doing underneath the sheets is to represent things in a sparse way that looks back—that looks more like a relational representation. But be aware of all three of these: an edge table, an adjacency list, and an adjacency matrix. [Music]

So we showed how to implement loops in map reduce and optimize them and use that to implement the DataLog pattern language and recursive programs in that language, and we showed different representations of graphs, and now we're going to show PageRank in a couple of different ways at scale. So remember the context here is that graphs are getting bigger and bigger and bigger. So you can imagine a social-scale graph having about a billion vertices, one per person, with maybe 100 billion edges; a web-scale graph is bigger because there's more web pages than people, so maybe a billion vertices and a trillion edges. But there's, you know, the human connectome, the neural network in your brain, has maybe 100 billion vertices and 100 trillion edges. So we need large-scale systems to process this, and map reduce is one such system; there's more coming down the pipe though. So map reduce is perhaps on the tail end of its utility for these massive, massive scale, but we're going to stick with it for now.

So here's an implementation of PageRank in map reduce. In the map function, we have a node ID and a vertex object; that vertex object has a couple of methods that we use; you can get its current page rank in `.pageRank`, and you can get its adjacency list in `.adjacencyList`. So `.pageRank` divided by the length of the adjacency list gives us the fraction of the rank that we're going to distribute to each of our out—each of our neighbors across each of our out edges. Then we're going to emit a special key value pair with the node ID and the vertex object, and I'll come back to that that in a bit. And then for each of my outgoing neighbors, send that send the appropriate fraction of my page rank, which is the value `p` that we just constructed. Okay.

So now on the reduced side, we've got a node ID `m` and a list of things. Then we initialize a couple of values: this `m` object to null and a new rank to zero. And then for every `p` in this list of `p`s, we're going to check to see if it's a vertex. Now why that's there is that's—if it is a vertex, that means it corresponds to this key value pair that we emitted up there, and all this was was a way to pass that complex vertex object through to the reducer because remember the key here is just a node ID, so we need some way of passing this this more complex object with some internal structure over to the reduced side. And so now we have it, and we assign it to `m`. If it's not a vertex, then it's one of these other page rank values that we computed, and therefore we just add it up. And then finally the new page rank for that vertex `m` is going to be this formula that we saw—well, sorry, sorry, I guess I'm being a little giddy there—this is the damping factor that we mentioned, and this is an equivalent expression to what we showed before. And finally, now that we've constructed the new page rank, we emit a key value pair: the node ID and the vertex object itself, which is the same key value types as we need on the map side to repeat this. So we're going to run this over and over and over again with different—across multiple iterations.

So there's some problems with this implementation; the main one is that the entire state of the graph is shuffled on every iteration; right, that little complex vertex object that includes within it the adjacency list associated with that vertex is sent across the network over to the reduce side and handled by the reducer when all that really needs to be sent is just the new rank contributions. If the vertex state could sort of stay in place, you know, if you could if you could address the neighboring vertices directly and just say, "Hey, here's your new rank contribution," that would be useful; that would save some communication traffic. And then also we have to control the iteration outside of map reduce, including determination conditions and just the logic itself. So for these reasons, and just to explore another programming model, Pregel was suggested um also at Google in 2010. So there's been—since then—there's been open source implementations, just like there was for map reduce: Apache Giraph, Stanford; there's a system called GPS, something called J Pregel, Hama. And this is really designed for batch algorithms on large graphs in particular; so focused on graphs. And so the basic logic looks something like this: it says while any vertex is still active or the max iterations have not been reached, for each vertex process all the messages you get from your neighbors, update your own internal state, and then send messages back out to your neighbors, and then maybe set the active flag appropriately; you know, if you don't get any messages then you're not active, or if your internal state doesn't change enough you're not active. And you can control this logic. And so the point is now you're writing—instead of writing a map function and a reduce function—you're essentially writing just one little function, which is the the the function that I should run on each vertex at every at every time step. Right.

Let's see an example, which is PageRank. Okay. So there's just one method here, `compute`, and this is—this code is a little awkward; this is straight from the Pregel paper; it's a little awkward here because it's um in C, so so bear with me if you're not used to looking at C, but this says if—basically—the iteration number is greater than or equal to one, the superstep, then add up all the messages I get from my neighbors, and then assign my own internal state to this new calcul—to the new rank. Then as long as the superstep is less than 30, which is our, you know, if we go over 30 we're just going to assume that we've converged and just quit, then send the contribution of my rank to all my neighbors, which is my current value divided by `n`, and `n` is just the number of uh number of neighbors; otherwise set myself to inactive, which which is this vote to halt. So you sort of say, "I've got no more work to do; I'm done until somebody wakes me up with a with a with a new value." Okay. And what's not in here in this implementation but is often added in a Pregel implementation is some kind of condition that says, "Well, if the if the internal value hasn't changed by a large enough amount, then vote to halt; then set myself to inactive." All right.

Let's see how this works; I'm not—the code may may not be very clear. So imagine we have a graph like this; we initialize the rank to the total number of vertices divided by the number of—excuse me—the number one divided by the number of vertices. So there's five vertices, so we just divide one by five, which is 0.2. Okay. So that's the initial rank. Then we—each the program, the `compute` program, runs on every vertex simultaneously in parallel, and it sends its rank contribution to all of its neighbors. So this rank contribution of 0.2 divided by two outgoing edges, so that get—each one gets 0.1, and here there's three outgoing edges, so each one gets 0.066, and so on. Then on the next superstep, all those contributions are added up, and so here we add 0.1 and 0.066, multiply by 0.85, and add in 0.03 because that's our formula, and we get 0.172. And we do the same for all the other nodes. Now this one's a little funny: why did 0.0—why did this node and this node get 0.03? Well, that's because they have zero—they have no incoming edges at all, in which case this term in the formula provided nothing; the sum was zero, and so they just get 0.15, I.D. 5, 0.03. Okay. And so that's our new value after that iteration. Then it repeats; this rank is divided in half: 0.015 and 0.015; this rank is divided in thirds: 0.01

0.01 0.01 one and so on, and we see what changes. So we add this up: this plus this times 0.85 plus 0.03 gives us 0.513 and so on.

And then I've marked these vertices as red because their value didn't change from one iteration to the next, and so they're marked as inactive. And that condition actually wasn't in the code that I showed you, but it's typically a condition you add. Okay.

And so then the process continues. Here's the new values for the next iteration. We start over again. Uh, one optimization here is that these messages aren't actually resent again; they can be retained on the receiving side. You know, all all the incoming edges have a value and doesn't necessarily need to be resent across the network; you can just sit there until it's updated. So if if this if this vertex were active, it would be resent with a new value, but since it's not active, you just use the old value from the previous iteration, and nothing needs to be sent. All right.

So we recompute these, but we find out that this top vertex didn't change from one iteration to the other, so it goes red, and then these two values are updated appropriately, and that's our new values for the next iteration.

And then finally, remember all the red nodes don't actually all the red vertices don't actually get executed at all, and so they don't send any messages, and they don't send any messages; nobody needs them. But this vertex still needs to be updated, and so we apply it again.

And then finally, the execution halts when all the vertices are inactive. Now, it's it might take quite a while to to converge, in which case remember there's that superstep less than 30 condition as well, so you don't really need to let in general, PageRank starts to get pretty close to converging after some number of iterations; you don't really need to let it run for for too long.