Ruby-us Hagrid: Writing Harry Potter with Ruby
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
Title |
| |
Title of Series | ||
Number of Parts | 66 | |
Author | ||
Contributors | ||
License | CC Attribution 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
Identifiers | 10.5446/46611 (DOI) | |
Publisher | ||
Release Date | ||
Language |
Content Metadata
Subject Area | ||
Genre | ||
Abstract |
|
Ruby Conference 201825 / 66
5
10
13
14
17
18
21
22
26
29
37
45
46
48
50
51
53
54
55
59
60
61
63
65
00:00
VideoconferencingAbelian categoryHill differential equationStatisticsDuality (mathematics)Hash functionTelecommunicationMusical ensembleQuicksortCategory of beingKeyboard shortcutNatural languageWordFunction (mathematics)Combinational logicDisk read-and-write headBitMultiplication signComputer-assisted translationType theoryVideoconferencingLevel (video gaming)Semiconductor memoryRegular graphStatisticsAnalytic continuationSoftware testingComputer programmingSlide ruleCodeNP-hardLink (knot theory)Computer fileRight angleInstance (computer science)Hand fanVirtual machineHash functionPerturbation theorySymbol tableProcess (computing)OvalSystem callKey (cryptography)Point (geometry)Parameter (computer programming)Source codeDefault (computer science)SmartphoneCountingOnline helpFile formatWritingJSONXMLComputer animation
10:08
Session Initiation ProtocolWordDynamic random-access memoryLiquidKey (cryptography)Sample (statistics)outputDisk read-and-write headInclusion mapVector potentialNumberWordHand fanMultiplication sign1 (number)Phase transitionSeries (mathematics)Randomized algorithmAnalytic continuationReal numberComputer programmingProcess (computing)Operator (mathematics)AlgorithmGreedy algorithmFlow separationFunction (mathematics)QuicksortOvalUniqueness quantificationSampling (statistics)Type theoryTouchscreen2 (number)Loop (music)Hash functionRight angleFrequencyCASE <Informatik>Disk read-and-write headEqualiser (mathematics)Maxima and minimaDifferent (Kate Ryan album)RandomizationPoint cloudWater vaporVirtual machineKeyboard shortcutCountingEndliche ModelltheorieData miningAxiom of choicePoint (geometry)Computer animation
20:01
Hash functionHill differential equationBlock (periodic table)BuildingMereologyPointer (computer programming)Multiplication signNP-hardDisk read-and-write headForm (programming)Operator (mathematics)PhysicalismElectric generatorGraph (mathematics)Object (grammar)2 (number)Key (cryptography)BitScheduling (computing)Pattern recognitionExecution unitBuildingBlock (periodic table)Function (mathematics)Computer chessStudent's t-testSlide ruleLine (geometry)WordSocial classDifferent (Kate Ryan album)Dot productMereologyEndliche ModelltheorieArithmetic progressionControl flowMappingKeyboard shortcutQuicksortRevision controlDecision theoryGraph coloringCASE <Informatik>Validity (statistics)Series (mathematics)CodePoint (geometry)SurfaceAlgorithmDomain nameMathematicsSet (mathematics)Game theoryFigurate numberSolid geometry
29:53
Coma BerenicesXMLComputer animation
Transcript: English(auto-generated)
00:21
filtering in, but I'll kick off. So hi, everyone. I'm Alex, and I'm really excited to talk to you today about two of probably my favorite things in the world, Ruby and Harry Potter. So the title of the talk is Ruby as Hagrid, writing Harry Potter with Ruby. And this
00:43
whole talk is based around a kind of crazy idea. Can we use Ruby, just the regular Ruby language that we know and love, to write a brand new Harry Potter story automatically? So this immediately raises some other questions. Like probably the first one is why on earth
01:04
would we want to do that? Then, you know, what would that actually look like? What can we actually achieve if we use Ruby to write Harry Potter story? And then the second one obviously is how on earth do we actually do this? So let's start with the
01:21
why, why we might want to do this. And I realize I'm probably talking to two kind of slightly different audiences in the room right now. So first you have people like me, the true blue Harry Potter fans, and for all of us, this is pretty straightforward. To answer this question, just imagine a nice, big, beautiful pile of brand new Harry Potter
01:46
books, which means that we can just stay happily in the wizarding world forever. Now there's also going to be a lot of you who have never caught the Harry Potter bug, a bit baffled by it all. And so for all of you instead, I'd recommend visualizing
02:01
a big beautiful pile of money, because that is what awaits you if you can satiate the rabid hunger of people like me in category A. By the way, if you're not quite sure which category you fit into, there's a little test I've come up with. Just look at this picture, and then based on your reaction, you can sort yourself into the
02:23
appropriate category. Okay. So those are some of the whys. Maybe some slightly more serious reasons why hopefully this is interesting. It's going to give us a nice intro to natural language processing, NLP, which is really a hot topic right now.
02:42
It's also, I think, going to reveal a lot of the simplicity and beauty and elegance of Ruby. We can actually, you know, do this with very little Ruby code. And also, I hope it's going to reveal something more general about tackling seemingly hard problems. And I'll talk a little bit about that at the end.
03:01
Okay. So now what can we achieve? What will this actually look like when it's done? So I'm going to give a bit of a spoiler and show the output of the sort of final program that we'll write. So let's give it a read. Neville, Seamus, and Dean were muttering, but did not speak when Harry told Fudge mere weeks ago that Malfoy
03:20
was crying, actually crying tears streaming down the sides of their heads. They revealed a spell to make your bludger, said Harry, anger rising once more. Okay. So it's definitely not Pulitzer Prize-winning stuff. But, you know, it has, you know, it more or less makes sense. It certainly has the style of a Harry Potter story.
03:41
And hopefully you'll be sort of doubly impressed when you see actually how little code goes into making this. So now the big one is how we actually go about doing this. And on the face of it, this does seem like quite a hard problem, right? To look at even, you know, one sentence from that extract that I just read and think
04:02
about, well, how did we begin writing Ruby code to create a sentence like this? So there are a couple of key ideas that I want to introduce to sort of help get us started. So one is that we want to tell this story word by word. So at any point we just want to be focused on generating the next word in the story.
04:24
And the second key idea is that probably pretty much all of us in this room have a great source of inspiration for this problem in our pockets or in our bags. And those are our smartphones. So why are our smartphones a good way to get started on this problem? So pretty much every modern smartphone has, let's see if I can use
04:46
my laser pointer, has one of these, right? A predictive keyboard. Now usually we use a predictive keyboard as a sort of typing aid, right? To write things faster. But what's kind of interesting is we can actually use this to generate sentences
05:01
basically unsupervised. So here's a video I recorded on my phone. So basically what I'm doing is I'm just hammering this middle suggestion button. And you can see what happens is it starts to generate an English sentence. A sentence that sounds like it's been written by a human. And what else is kind of interesting about this is it's
05:23
not supposed to just be imitating any human. It's supposed to be imitating me. Because, you know, and some of you might know this already, your predictive keyboard adapts to you over time, right? So it sort of learns your style and tries to imitate that. So how does your phone do this? Well, so let's take an example. This is what I get
05:41
as my suggestions when I type birthday into my phone. So the first suggestion is party followed by cake. And then we have wishes as the third suggestion. So somewhere in the memory of my phone, it knows that, you know, out of all the times that I've written birthday, let's say that I've used the word party 30 times to follow on from birthday and cake a little less, 20 times, let's say.
06:02
And so by knowing what words I've used in the past, it can suggest what words I'm likely to want to use in this instance when I've written birthday. So why is this relevant to our problem? Well, we can take that exact same idea and start doing the same thing with the way that JK Rowling uses language in the Harry Potter series.
06:22
So for example, the word golden appears about 200 times in the Harry Potter books. And these are the top continuations that come after golden. So the word egg is the word that follows golden most often. And that comes 13 times after golden. And then snitch is
06:41
the next most common and so on. And a couple of bits of terminology I'll keep using throughout this talk. This initial word that we use to sort of generate the suggestions, we'll call this the head word. And these suggestions, we'll call them continuations. So the third key idea is that we want to break the way we tackle this problem into two phases.
07:05
First, we want to learn the style of JK Rowling, learn the style of the Harry Potter books. And the second step is we want to then use everything we've learned to generate new stories. So let's first look at the learning stage. Now, the learning stage is actually super simple. All we want to do is basically look at every single word that JK Rowling uses in
07:25
the Harry Potter books and just collect these sort of stats. So for each head word, what are the continuations that come after it? And how many times does each continuation appear? So we do it for golden, as we saw, but then for goldfish and golf. And for all the words in the books, that's about 20,000 unique words altogether. So how would we represent
07:47
this in Ruby? Well, you can maybe guess from the way this is laid out, but a nice way to represent it is just as a simple Ruby hash, right? So something like this is what we want to end up with. Okay. So let's look at how we actually do this in code. So the very first thing that
08:02
we're going to need is some copies of the books in machine readable format. So just text format is completely fine. I forgot to mention, by the way, I've put some notes and all the slides and everything online, and you can find links to these kind of text files there. I'll show that
08:21
link again at the end. So we start with those text files, and then we want to start by doing some cleaning. So something called tokenization, which basically means, you know, getting rid of special characters. We'll lowercase everything. We'll turn everything into a symbol as well. That's going to be a lot more memory efficient to work with. So taking a sentence like this,
08:42
we'll end up with some output like this. So once we've tokenized everything, then we're ready to actually build up our hash of the head words and the continuations. And this is a really nice example, I think, of, as I said, how elegant and simple Ruby can make this. So this is all the code that we need to do this. So let's have a look at what's going on
09:03
here. So we start off by using this nice built in method, each cons, which is short for each consecutive. And that's basically going to take each consecutive, in this case because we've passed the argument to, each consecutive pair of words. And so we'll start with the cat,
09:20
and then we'll do cat sat, sat on, and so on. And then for each head word, we're going to say, okay, if we haven't encountered this head word before, let's just initialize a new hash inside. So to go along with, say, our head word, we'd start with a new hash, which will have a default count of zero. And then we'll just say, okay, for this combination
09:43
of head word and continuation, let's increment the count by one. So that's all that's going on here. And the first iteration, you can see we'll get the, and we'll say, okay, cat follows the word the one time. And then on the next iteration, sat followed cat one time. And we'll
10:01
continue iterating through all the words in this example sentence, and we'll eventually end up with something like this. So we do exactly the same procedure, but instead of this example sentence, we do it on that corpus of all the Harry Potter books, and that's our learning phase done. That's all we have to do to learn the style of the Harry Potter books, JK Rowling.
10:23
So now we need to figure out how we use that to generate new stories. And there are a few different approaches. So let's start with the simplest, which is called the greedy algorithm. Okay. So why is it called the greedy algorithm? Well, it's because in each case, it sort of takes the biggest, juiciest option. So what
10:44
that means is it just goes for the most likely continuation, the one that's appeared most often. So in our golden example, remember we said egg appeared more than any other word after golden 13 times. So we would just always pick the word egg after the word golden. Okay. So and then, you know, once we pick egg, well, after egg, the word and is the
11:03
most frequent continuation, so we pick that one next, and we just continue on like that until we have a story. This again is really nice and easy to implement in Ruby. So you can see here what we're doing is we're taking all of our continuations and we've got the word and the
11:21
count, how many times it appears, and then we're just using the max by method to say just give me the continuation with the highest count. And that's all we're doing. Really nice and easy. Okay. So if you've really been paying attention, then you're spotted one other problem, which is, well, what do we do about our very first word in the story, right? Because
11:41
when we're doing our first word, we don't have any previous word to continue from. So we're going to have to do something a little different to start our story. There's a bunch of different approaches, but in this case, we can just start with a completely random word. Yeah, so any random word in our vocabulary, that's what's happening here when I'm using the dot sample method, just pick a random word to start us off. And then in this case,
12:04
I'm going to make a 50-word story, so I'm just going to repeatedly apply the greedy algorithm and then word by word hopefully build up a story. Okay. So how does this work in practice? So I ran this for the first time, and this is what I ended up with.
12:21
Oh, no, said Harry. A few seconds later, they were all the door and the door and the door and the door and the door. Okay. So this is not a great start. But maybe I just got unlucky, right? Remember, we start with a random word. So maybe this is a really bad choice. Let me try it again. So this is my second attempt. Surreptitiously, several of the door and
12:44
the door and the door and the door and the door. Okay. So the good news is we won't struggle to find a title for our new Harry Potter story. The bad news is obviously pretty much everything
13:00
else. So obviously something's gone horribly wrong here. What's going on? So let's look and walk through what's actually happening here as we're running this. Well, so let's say we start with the word several. Well, the word that appears most often after the word several is the word of. The word that appears most often after of is the. And then after the,
13:23
the most common continuation is door. And after door is and. Okay. All good so far. Then the problem is that the most common word that comes after and is the. So you can see what happens is we get stuck in a loop. And you might be wondering, does this always happen?
13:40
And sadly the answer is yes. Weirdly enough, the word that gives us the longest story without going into a loop is actually conference. I can't make these things up sometimes. And this is what we get if we use our greedy algorithm with the start word conference. And this is the best we can do, 20 words, right? So obviously we can rule out our greedy
14:02
algorithm and say this simply doesn't work. Okay. So let's try a completely different approach to generation. And let's go to the opposite end of the scale. And let's just get really random with something called the uniform random algorithm. It's a fancier name than, you know, it's a fancy name for something that's extremely simple.
14:21
Basically what we do is we just look at our potential continuations and we just pick anyone randomly, right? With equal probability, we just draw one out of, out of a hat. So, you know, in this case, if we had three continuations, we pick one of the three with equal probability, one third probability of picking any of them. In reality, we'll probably have a lot of
14:40
continuations. So, in this case, we have 117 potential continuations. After golden, we just pick one of them randomly. Okay. So, again, really nice and easy to do in Ruby. We can just, again, use the dot sample method and that will just pick one of our continuations at random. Okay. So, how does this work in practice? So, here's an example.
15:04
Debris from boys or accompany him bodily from Ron, yelled the waters. Harry laughing together, soon farther, would then bleated the smelly cloud. Okay. So, it's probably better than the greedy algorithm, but it's probably, unless you're really into, you know, avant-garde,
15:23
Harry Foster fan fiction, this is probably like a little bit weird. Why is this? And the other thing I would say as well, apart from the names, this doesn't really seem like Harry Potter, right? If you took the names out, you'd never guess this is a Harry Potter story. So, why is that? Why isn't this working so well? Well, there's a lot of reasons, but
15:45
let's look at one example word here. So, let's look at the word house. So, after the word house in the Harry Potter series, the word Alf appears over 100 times. But it's just one of those 200 potential continuations after house has a one in 200 chance of being picked.
16:03
By the way, a house elf is like our friend Dobby from earlier, if you didn't know. The word prices does appear. The phrase house prices appears in Harry Potter, but only appears once. But this has exactly the same chance of being picked as house elf, right? So, obviously, a program that's as likely to talk about house prices as house elves isn't really doing a
16:25
good job of imitating Harry Potter. So, that gives us some clues about how we can improve this. And so, our final and best algorithm is what we call the weighted random algorithm. So, what we do here is we just solve this problem, right? So, we look at the situation
16:45
here, and the word house appears about 700 times in the series altogether. And 100 of those times, it's followed by elf. So, logically, it feels like, well, this should really be more like a one in seven chance of being picked, right? And this is exactly what this algorithm does.
17:01
So, we just rescale the probabilities. So, it matches how many times the word appears. So, again, this is surprisingly easy. Sorry. So, just to reinforce that point. So, you might end up with a situation like this, where the most frequent continuation would have a higher probability, let's say one half probability of being picked,
17:23
and then one third, one sixth, and so on. So, again, surprisingly easy to implement in Ruby. So, this one's maybe slightly more difficult to understand, but the intuition here is, you know, you can think of this like a raffle, where a word, each word gets an entry equal to the
17:41
number of times it appears. So, in our house elf example, elf gets 100 entries to the raffle, whereas prices only gets one entry to the raffle. That's what this time here is doing.
18:17
So, how do we make that last jump and prove this to Matt, sort of, at the beginning?
18:25
There's one last big idea here on the generation, which is to represent our predictive keyboard. And there's actually something more interesting going on here, because if I just start by typing with an and instead of my phone, I get this kind of post in there, yes, it's you, it's mine. But if I type in something like fish and and, then my phone
18:45
knows to offer update for suggestions, right, so that's the first thing. So, obviously, my phone isn't just looking at the previous word, it's actually looking at more of the history than that. So, the last key idea is that we can prove our output by looking
19:00
more than just the previous word. So, what that means is rather than building up a hash like this with every word and its continuations, now we're going to want to build the hash, sorry, when we do this, we're only thinking about two words, one head word, one continuation, this is what we call a five-gram model. So, instead we're going to want to look at
19:25
every unique pair of words in the book series and all of the continuation. And this is the, in this case, we're thinking about three words at a time, so just the trigram model, we can actually extend this to a four-gram model, five-gram model, and so on.
19:42
Now, obviously, because we're thinking unique pairs of words, there's a lot more, right, so I think we said 10,000 unique words and we have about 300,000 unique pairs of words, a lot bigger than actually we're building, this will still compute in a couple of seconds on a, on a, on a machine. And again, you know, Ruby does an amazing job of
20:03
allowing me to do this without making very specific changes. All we really have done is added a splash operator, and that, that basically just says, hey, rather than taking a single head word, we now allow a set of four of head words here. And so in this case,
20:21
now with this, so at least I add three, trigram model, and now we're going to think about how to make the same whole build-up without having to actually pass the words instead. Okay, so this is the output of the trigram model, as you can look at this. Normally, when Dudley passed his voice fairly loud than before, to then sort of step down the
20:40
whole step lead, he however got back, all this messes must be worthless. Harry looked at him, puts one film into his head, he's like, he's got a solid Harry model, so. And by the way, we can go to five-gram models, six-gram models,
21:06
the problem is, as we go higher and higher, we end up getting closer and closer to see what's actually in the books, until eventually we just cannot take passages from the books. That encourages us to have a think about where that might be. All right, so, so stepping back for a second, we've seen that this problem that,
21:26
the start maybe, that probably some of you have imagined, seems like a quite complicated idea, like it would be quite difficult. We've actually managed to do this in like 20 lines of pretty short pay-free for Ruby code. And I wanted to kind of take this opportunity
21:44
then, to just finish off by talking about, well, I mean, just some broader lessons we can draw from this. Obviously, hopefully this is an interesting and inspiring project, but yeah, how do you actually apply this to your general class as coding? So, on the surface of this, this talk is about Harry Potter.
22:03
The summer point for Harry Potter was that he thought he was also about another PTP, and he was also about hard problems, right? How do you take a problem that looks really hard on the surface, and then, by the time you've finished the solution, you're like, oh, that was Harry Potter. So, I think hard problems are relevant to all of us. So,
22:22
if you're, you know, a new programmer, even if you're a veteran programmer, I think it's really important to reflect on how you solved hard problems, so you can pass your skills on to the next generation. Now, I think there are three lessons, you know, that I
22:41
certainly learned, or reinforced in making this talk, and I just wanted to highlight. So, the three, sort of, tips, I guess, of tackling hard problems that we saw on this talk. The first is to understand how to break down the problem. The second is to really pay attention to your failures as you're tackling hard problems, and the second is to kind of find the
23:01
right answer for your problem. So, let's start with the first one. Understand how to break down the problem. So, there's this problem, how do you even know if it's one bite at a time? And I think this is a really nice philosophy to apply to any hard problem, but often the tricky thing is working out what is a bite, and there's a problem with
23:21
the name. What are those little building blocks that we used to solve them? So, we saw in this talk that for the story time problem, the bite size was a single word, right? We generated a story problem. Now, sometimes for a hard problem, the bite size would be quite obvious. So, let's say we're making a chess game. Well, a little unit of work
23:41
is probably a single move, right? We kind of whacked the chess engine, but it wouldn't move at any time. But sometimes it could be more answering, so let's say we were waiting for Hogwarts or any of us. How would we, you know, this game can seem like
24:01
quite hard intimidating problem. How do we break down and make it more manageable? Well, ultimately a rooting algorithm is just a series of decisions about to go left, go right, go straight. So, we could think of that as one bite, but this problem is a single turning decision. And sometimes it will be really not obvious at all if you
24:21
haven't encountered the problem before. So, let's say we're doing face detection, face recognition. Again, it seems like a really hard problem on the surface. How do we even begin? Well, if any of you have ever encountered this sort of done face detection or recognition, then you'll know that the units in this case are
24:40
what are called facial landmarks, so these little red dots. So, it's all about placing these little facial landmarks and then translating that into, you know, recognition or detection signal. So, the first tip is really, you know, when you're tackling a new hard problem, ask someone familiar with the problem and what are
25:01
the building blocks for solving this problem? How do we tackle this one step at a time? How do we break it down? So, the second lesson to take is that we should really pay attention to our failures. So, obviously we had a bit of a false start when we were telling our stories. Now, we could have just said, oh, you know, that doesn't work, let's throw it away and
25:22
try something different. But what I really had to do is look in detail at the failure, try and figure out, well, why did that fail, you know, map out what was happening at every step and working out where the problem was because that was then what yielded the solution, what yielded the next step. So, you know, it may sound obvious, but anytime
25:41
you're tackling especially a really hard problem, just really pay attention to those failures. And ask, you know, ask someone who knows, again, about the problem, why didn't this work, what specifically about my approach was flawed? And then the last lesson to draw is that finding
26:00
a good metaphor for a problem is actually really, really valuable. So, when I was, you know, wrapping my head around this, I found this metaphor of the predictive keyboard to be really, really helpful in understanding how to go about this. Now, it's really easy to come up with bad metaphors, but coming up with good metaphors is much more tricky. And I think a good metaphor
26:23
has a couple of qualities. So, the first is that it keeps and captures all the essential parts of the problem. So, you can strip out things that aren't, you know, that aren't relevant and you can modify things, but there are certain essential parts of the problem that you just have to keep. And the second thing is that a good metaphor allows you to sort
26:42
of play around with the metaphor and then learn something about the original problem, right? So, it's not just a way of understanding the problem, but it's like you can actually make progress on solving the problem by playing around with the metaphor. So, let's take another example of this that I really, really like. So, let's say I'm Dumbledore
27:01
and I'm trying to schedule the Hogwarts classes. Now, I have to schedule the classes so that there aren't any clashes. So, if, you know, a student is taking two classes, they shouldn't be scheduled at the same time. But I do want my timetable to be efficient. So, if I can schedule two classes at the same time, I want to do it. So, for example, here's a bad
27:22
example of the scheduling. So, in this case, hopefully you can see the colors. I've scheduled arithmancy and ancient ruins at the same time for the same color. But, you know, Hermione's taking both of them. So, this is a failed attempt at scheduling. So, I can definitely look at this in the tabular form and it works okay. There's a sort of nice metaphor,
27:42
a nice different way of thinking about this, which is graph coloring, which some of you might know about. So, basically what I do is I just draw out the classes as dots on a piece of paper or whatever. And then if two students are, oh, sorry, if a student is taking two classes, the same student is taking two classes, I just draw a line between the dots.
28:02
So, for example, remember we said Hermione's taking ancient ruins and arithmancy. So, these two have a line between them. And then, basically, my challenge is I've got a color in the dots so that at the ends of a line, I don't end up with the same color ever. So, for example, this is an example of a valid coloring. And what's
28:25
interesting about this is if I can come up with a valid coloring, I've also come up with a valid timetable. So, it may take some thinking about, but if you reason this through, you realize these are actually equivalent problems. If you can do the coloring with the lines in between them, then you've eliminated all of the conflicts and you have a valid
28:43
timetabling. Now, I absolutely love this metaphor because, yeah, sure, we can look at things in the tabular form, but, you know, having this metaphor to draw on, we can actually start playing around with this. We can get a piece of paper and a pen and some coloring pencils and start making progress on this. And it keeps all the essential
29:00
parts of the original problem. So, everything I learn by playing around with that metaphor, I can apply to that original hard problem. So, again, find somebody who knows about this problem domain and ask them what's a good metaphor for this problem. And, as I said, favor anything where it's something you can physically play around with on pencil,
29:21
something you can play around with pen and paper or a physical object or something like that. It's really, really helpful. Okay. So, yeah, those are the kind of key lessons about hard problems that I think that certainly I learned from doing this talk. So, yeah, thank you for listening. I've put the slides and notes online at this address. And I think
29:43
we're cutting quite short for time. So, I won't take questions now, but feel free to come up to me afterwards if you have any. All right. Thanks very much.