Harvard Professor Explains Algorithms in 5 Levels of Difficulty | WIRED

how would you propose verbally to find John in this phone book, or? I would just flip through and just look for the J, I guess. Yeah. so let me propose that we start That way, I could just start at the beginning and step by step, I could just look at each page, looking for john, looking for john. Now, even if you've never seen this here, technology before, it turns out this is exactly what your phone could be doing in software, like someone from Google or Apple or the, like, they could write software that uses a technique in programming, known as a loop, and a loop as the word implies is just sort of do something again, and again, what if, instead of starting from the beginning and going one page at a time? what if I, or what if your phone goes like two pages or two names at a time? would this be correct? Do you think? Well, you could skip over John, I think, in what sense, if he's in one of the middle pages that you skipped over? Yeah, so sort of accidentally, and frankly, with like 50/50 probability, John could get sandwiched in between two pages. But does that mean? I have to throw that algorithm out alt together? Maybe you could use that strategy until you get close to the section, and then switch to going one by one. Okay, that's nice. So you could kind of like go twice as fast, but then kind of pump the brakes as you near your exit. on the highway or in this case near the J section of the book. Exactly. And maybe alternatively if I get to like A, B, C, D, E, F, G, H, I J K, if I get to the K section, then I could just double back like one page just to make sure John didn't get sandwiched between those pages. So the nice thing about that second algorithm is that I'm flying through the phone book like two pages at a time. So 2, 4, 6, 8, 10, 12. It's not perfect. It's not necessarily correct. But it is if I just take like one extra step. So I think it's fixable. But what your phone is probably doing and frankly what I and like my parents and grandparents used to do back in the day is we'd probably go roughly to the middle of the phone book here. And just intuitively, if this is an alphabetized phone book in English, what section am, I probably going to find myself in roughly K. Okay, so I'm in the K section. Is john going to be to the left or to the right, to the left? Yeah. So john is going to be to the left, to the right. And what we can do here, though your phone does something smarter, is tear the problem in half, throw half of the problem away being left with just 500 pages now. But what might I next do? I could sort of naively just start at the beginning again, but we've learned to do better. I can go roughly to the middle here. Do it again. Yeah, exactly. So now maybe I'm in the E section, which is a little to the left. So john is clearly going to be to the right so I can again tear the problem portly in half, throw this half of the problem away. And I claim now that if we started with a th000 pages, now we've gone to 500, 250. Now we're really moving quick. Not on that page. And I can call him roughly how many steps might this third algorithm take? if I started with a th000 pages, then went to 500 250, 125. Like how many times can you divide 1,000 and half? Maybe 10? That's roughly 10 because in the first algorithm looking again for someone like Zoe in the worst case, might have to go all the way through thousand pages. But the second algorithm you said was 500, maybe 500 in1. Essentially the same thing. So twice as fast. But this third and final algorithm is sort of fundamentally faster because you're you're sort of dividing and conquering it in half and half and half, not just taking one or two bites out of it at of a time. So this, of course, is not how we used to use phone books back in the day, since otherwise they'd be single use only. But it is how your phone is actually searching for. zoy for John for anyone else. but it's doing it in software. Oh, that's cool. So here we've This segment demonstrates the creation of a simple algorithm through a practical example. The speaker guides a child through the step-by-step process of making a sandwich, highlighting the importance of precision and detail in algorithmic instructions. The example effectively illustrates the core concept of an algorithm as a set of precise instructions for solving a problem. currently a fourth year Phd student at Nyu. I do robot learning. So that's half and half robotics and mission learning. sounds like you've dabbled with quite a few Algorith. So how does one actually research algorithms or invent algorithms? The most important was just trying to think about inefficiencies and also think about connecting threads. The way I think about it is that algorithm for me is not just about the way of doing something, but it's about doing something efficiently. Learning algorithms are practically everywhere now. Cu Google, I would say, for example, is learning every day about like, oh, what what articles with links might be better than others and reranking them. Um, there are recommender systems all around us, right? Like content feeds and social media or, you know, like Youtube or Netflix. What we see is in a large part determined by this kind of learning algorithms. Nowadays, there's a lot of concerns around some applications of machine learning and like deep fakes where it can kind of learn how I talk and learn how you talk and even how we look and generate videos of us. we're doing this for real. But you could imagine a computer synthesizing this conversation eventually. But how does it even know what I sound like and what I look like and how to replicate that? All of this learning algorithms that we talk about, right? Uh, a lot, like what goes in there is just lots and lots of data. So, data goes in, something else comes out, what comes out is whatever objective function that you optimize for? Like, where is the line between algorithms that like play games with and without AI? I think when I started off my undergrad, the current AI machine learning was not very much synonymous. Okay. And even in my undergraduate in the AI class, they learned a lot of classical GorithMs for game plays, Like, for example, the AaR search, right? That's a very simple example of how you can play a game without having anything learned. This is very much, oh, you are at a game state, you just search down, see what are the possibilities. And then you pick the best possibility that it can see versus what you think about when you think about I gameplay like the alpha zero, for example, or Alpha Star, or there are a lot of, you know, like, fancy new machine learning agents that are, you know, even like learning very difficult games, like Go and those are learned agents as in they are getting better as they play more and more games. And as they get more games, they kind of refine their strategy based on the data that they seen. And once again, this high-level abstraction is still the same, chalkboard with some magnetic numbers on it here. Like, how would you tell a friend to sort these? I think one of the first things we learned was something called bubble sort. It was kind of like focusing on like smaller like bubbles. I guess I would say it like, of the problem, like looking at like smaller segments rather than like the whole thing at once. What is, I think, very true about what you're hinting at is that bubble sort really focuses on like local small problems, rather than taking a step back, trying to fix the whole thing. Let's just fix the obvious problem in front of us. So, for instance, when we're trying to get from smallest to largest, and the first two things we see are eight followed by one. This looks like a problem, cuz, it's out of order. So what would be the simplest fix the least amount of work we can do to at least fix one problem, Just like switch those two numbers, cuz one is obviously smaller than eight. Perfect. So we just swap those two. Then you would switch those again. Yeah. So that further improves the situation. And you can kind of see it that the one and the two are now in place. How about 8 and six, switch it again, Switch those again, 8 and three, switch it again. And conversely, now the one and the two are closer to. And coincidentally, are exactly where we want them to be. So, are we done? No. Okay, so obviously not. But what could we do now to further improve the situation? Go through it again. But like you don't need to check the last one anymore, because we know like that number is bubbled up to the top. Yeah, Because it has indeed bubbled all the way to the top. So one and two. Yeah, Keep it as is okay two and six Keep it as is okay six and three Then you switch it. Okay, we switch or swap those six and four Swap it again. Okay, so four and uh six and seven. Uh, keep it okay seven and five Swap it. Okay, and then I think per your point we're pretty darn close. let's go through once more One and two keep it 2, three keep it 3. four keep it 4. six keep it 6 five and then switch it. All right we'll switch this and now to your point we don't need to bother with the ones that already bubbled their way up. Now we're 100% sure it's sorted. Yeah, and This segment explores the crucial role of algorithms in data science, contrasting their application in academia and industry. It delves into the complexities of modern AI algorithms, particularly large language models, highlighting the gap between their effectiveness and our understanding of their inner workings. The discussion touches upon the implications of this "black box" nature of AI, questioning whether this lack of transparency is inherently good or bad and whether fundamental algorithmic knowledge is becoming less relevant in a world increasingly reliant on high-level tools like ChatGPT. computation is so high level, right? As you, you know, you can import PyiT learn, and you can go from zero to machine learning, and 30 seconds, it's depending on what level you want to understand, the technology, where in the stack, so to speak. Um, it's possible to understand it and make wonderful things and advance the world without understanding it at the particular level of somebody who actually might have originally designed the actual optimization algorithm. I should say, though, for many of the optimization algorithms, there are cases where an algorithm works really well, and we publish a paper, and there's a proof in the paper. And then years later, people realize actually that prove was wrong. And we're really, still not sure why that optimization works, but it works really well, or it inspires people to make new optimization algorithms. So I, I do think that the the goal of understanding algorithms is loosely coupled to our progress in advancing grade algorithms, but they don't always necessarily have to require each other. And for those, students, especially, or even adults who are thinking of now steering into computer science into programming, who were really jazzed about heading in that direction, up until for instance, November of 2022 when all of a sudden, for many people, it looked like the world was now changing. And now, maybe this isn't such a promising path. This isn't such a lucrative path anymore. Are LLMs are tools like chat GPT Reason? not to perhaps steer into the field, Large language models are a particular architecture for predicting, let's say, the next word or a set of tokens. More generally, the algorithm comes in when you think about how is that LLM to be trained, or also how to be fine-tuned. So the P of GPT is a pre-trained algorithm. The idea is that you train a large language model on some corpus of text, could be encyclopedias or textbooks, or what have you, And then you might want to fine-tune that model around some particular task, or some particular subset of