Becky! (![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
code_gorilla) wrote2011-11-07 04:48 pm
code_gorilla) wrote2011-11-07 04:48 pm
Entry tags:
me.geekOut(math);
So as I'm sure many of you know, I am a major math geek. I was very nearly a math major major math geek. (Say that three times fast.) What does that have to do with anything? Well, this is a math post. BEWARE, YE FAINT OF HEART or some such thing. So this stemmed from last Thursday. I've just been too busy (read: easily distracted) to actually write this up until now (office hours give me some decent free time when nobody actually shows up). Details under the cut!
So what happened last Thursday, you might be wondering. Well, the answer is that I went to class (gasp, shock and awe!). Probably a good thing, considering that I hadn't been to class in over a week for my 10:30 class, and I had even missed my noon class on the previous Tuesday. But for whatever reason, there was a bunch of math in my classes that day, and it kind of blew my mind, it was that awesome.
(On an aside, I realize I've yet to do a classes journal post. I'll have to do that, one of these days, and explain my classes this semester. Hopefully before the semester ends.)
So my 10:30 class. We went over random algorithms in class on Thursday. I'll start by saying that the phrase "random algorithm" is something of a misnomer. An algorithm, as defined in Computer Science (or so I've been told) is a finite, describable procedure that is guaranteed to give a correct answer on all inputs, and guaranteed to complete on any (appropriately formatted) input. Typically, this means that there is no randomness in an algorithm, or what randomness there is ends up being largely inconsequential. Neither of the two procedures I am about to describe are algorithms in the strictest sense of the term, but they're close enough that they are typically called algorithms.
First up is the Monte Carlo algorithm. Let's say you have some weird function, f(x), and for whatever reason you want to take a definite integral of it, but you can't, because the function isn't very nice looking. Or maybe you're just too lazy to actually do the integration, because it's particularly complex, and while you could, it would end up being five pages of algebra and calculus. Don't worry, I'm not about to hold it against you; I wouldn't want to do that either. So! You're probably dreading the five pages of math in your future, and you're thinking desperately to yourself "How can I get out of this? I've got other things to do this week!" Have no fear, Monte Carlo is here!
Step one: put your f(x) in a box. You already know the x values of the sides of the box; those are the bounds of the integral you're trying to evaluate. One of the y bounds should be the x-axis, and the other one could be anything, as long as it's bigger than the highest value of f(x) on that interval. Now you've got a box that neatly holds your function, or at least the part that you care about.
Like so.
Step two: throw some darts at the box. Well, figuratively speaking, at least. Basically, generate some random points that are inside the box. How many, you ask? As many as you want! The trick is that the more darts you throw, the longer it will take, but at the same time, the more accurate it will be. Honestly, though, "throwing" a million or a billion darts won't actually take that long, practically speaking, so you might as well make it a big number.
DARTS. DARTS EVERYWHERE. As long as "everywhere" means "inside the box".
Step three: count the darts in the box... and compare to the number of darts underneath the function. As the number of darts thrown increases, the ratio of darts inside both the function and the box to the number of darts in the box total approaches the ratio of the definite integral to the area of the box. Since you know the area of the box, you can multiply it by the ratio you've come up with and get an estimate of the definite integral. And all you had to do was throw some darts! Brilliant, isn't it?
... what? I warned you that I was a huge math geek.
The next one we talked about was the Las Vegas algorithm. It's an algorithm used for breaking symmetry, i.e. a random tiebreaker algorithm. The example problem given is something of an idealized problem. Imagine a city with a bunch of people, say, N of them. Idealville, if you will. Well, guess what? It's election day in Idealville, but they have some interesting elections. Everyone is allowed to run, everyone wants to run, and everyone who is running is allowed to vote for themselves. Unsurprisingly, everyone does votes for him/herself, resulting in an N-way tie. Clearly this will not do.
So what do the fine citizens of Idealville do? They hire an outside, unbiased third party to distribute random number generators to each of the N people in the election. Then RNG CO. tells everyone to generate a random number from 1 to N. They go around and verify that everyone does it correctly, and check each person's number. If that number is 1, then that person gets to stay in the election. Otherwise, that person is eliminated. Now we have a smaller group of people still in the election, let's say N'. If N' = N, then we repeat from the start of this round. If N' = 0, then we throw out the results of this round, and start again from the beginning of the round. Otherwise, we repeat the procedure on the smaller N'. You continue this until there's only one or two people left - if you get to one, that person is the winner. If you get to two, you flip a coin, and the winner of the coin flip is the winner.
Now, admittedly, I still don't have a satisfactory answer as to why you'd use this algorithm instead of just picking one random number from 1 to N and calling that person the winner. (Unless you're RNG CO., in which case you're probably making a hefty sum of cash from Idealville's yearly mayoral election. OCCUPY RNG CO. THEY ARE THE 1%.) That's not the interesting part, though. The interesting part comes when you examine the algorithm's time complexity, i.e. how long it takes to run. These things are usually measured as a function of the size of the problem, in this case N. So the result? Surprisingly, on average it takes less than e (Euler's number, 2.7182818284 and change) rounds to actually finish! In fact, as N approaches infinity, it takes an average of 2.442 rounds for the Las Vegas algorithm to decide a winner. Why is this a big deal? Because very few algorithms in Computer Science have a constant time complexity - something that takes just as long no matter how big the problem is. And it seems a little strange that this algorithm should!
(Actually, writing this, I suspect that this is a little bit BS. You still have to generate N random numbers in the first round. It should be at least N. I think I'm going to go in during office hours to ask about that.)
That was my 10:30 class. My noon class was also mathalicious. (Yes. That's a word. Deal with it.) Like I said, I missed the previous session of that class, so I came into Support Vector Machines, part 2. I'm not going to go into the detail of the actual math involved on this one, since it's a fair bit more complicated, and I'm not certain I understand it myself. But I'll give you the brief run-down, because it is also the best thing ever and I am a huge geek shut up.
So, Support Vector Machines are a technique for classifying sets of data. It is a binary classification technique, meaning it will only give a yes or a no answer. Here's how it works: you give it a bunch of data sets, and whether each one is a yes or a no. When you're done, you might end up with something that looks like this:
If only we could draw a line through thi- oh wait.
The Support Vector Machine will take all of that data, and try to draw a straight line such that all the yes examples fall on one side of the line, and all the no examples fall on the other side of the line. Obviously, this won't always be possible, so it also tries to minimize the amount of error. Now, you may be telling yourself "But that still doesn't work, CG! What if all the yes answers are inside a circle, and all the no answers are outside of the circle? It'll never work!" Okay, so maybe you're not telling yourself that. BUT YOU SHOULD BE.
Not even straight lines can help you now! Mwahahahahahahaha!
Ah, but there's a trick! There's a neat little thing called a kernel. How does it work? ... a little bit of magic, I think, but the point is that it can turn your input data into data in a higher dimension, which means you can then easily draw a plane that separates the data. Going back to the circle example, by using the right kernel, you can turn that into a three-dimensional cone, with the center of the circle being the point of the cone. Then you can easily chop off the cone at a certain height to separate all the yes answers from all the no answers! In fact, with a clever choice of kernels, SVMs can separate pretty much any binary data. It is important to note, though, that this only works on binary data - i.e. questions with a yes or no answer. So it can tell you "will it rain tomorrow?" but not "what will the temperature be tomorrow?". It could, though, tell you whether or not the temperature will be more than 75 degrees tomorrow.
Anyways, I've already tl;dr'd a lot on math in this post, so I'm going to cut this off here. Yep, I'm a total geek. But in a lot of ways, I needed this. I needed a reminder of why I'm in Computer Science - because I absolutely love stuff like this. This is what gets me excited. This is how I know I'm in the right major, even when individual classes have me discouraged.
EDIT: Added some crappy sketches! Yay! Also, a little bit of research on Wikipedia led me to realize that I've been misled, and as such part of the information in this post is wrong. I MUST CORRECT THIS.
'kay, so. What I called the Monte Carlo algorithm and the Las Vegas algorithm are not actually called those. In fact, Monte Carlo and Las Vegas are not actually random algorithms, but rather classes of random algorithms. Monte Carlo refers to all random algorithms that take a finite amount of resources to calculate, but don't always give the same answer. Rather, they give an approximation of the answer. Las Vegas algorithms, on the other hand, always produce the same answer, but randomly vary the amount of resources they need to find the answer. As such, the algorithms that I described here are examples of each kind of algorithm, rather than and algorithm with that name.
/END EDIT.
'til next time.
So what happened last Thursday, you might be wondering. Well, the answer is that I went to class (gasp, shock and awe!). Probably a good thing, considering that I hadn't been to class in over a week for my 10:30 class, and I had even missed my noon class on the previous Tuesday. But for whatever reason, there was a bunch of math in my classes that day, and it kind of blew my mind, it was that awesome.
(On an aside, I realize I've yet to do a classes journal post. I'll have to do that, one of these days, and explain my classes this semester. Hopefully before the semester ends.)
So my 10:30 class. We went over random algorithms in class on Thursday. I'll start by saying that the phrase "random algorithm" is something of a misnomer. An algorithm, as defined in Computer Science (or so I've been told) is a finite, describable procedure that is guaranteed to give a correct answer on all inputs, and guaranteed to complete on any (appropriately formatted) input. Typically, this means that there is no randomness in an algorithm, or what randomness there is ends up being largely inconsequential. Neither of the two procedures I am about to describe are algorithms in the strictest sense of the term, but they're close enough that they are typically called algorithms.
First up is the Monte Carlo algorithm. Let's say you have some weird function, f(x), and for whatever reason you want to take a definite integral of it, but you can't, because the function isn't very nice looking. Or maybe you're just too lazy to actually do the integration, because it's particularly complex, and while you could, it would end up being five pages of algebra and calculus. Don't worry, I'm not about to hold it against you; I wouldn't want to do that either. So! You're probably dreading the five pages of math in your future, and you're thinking desperately to yourself "How can I get out of this? I've got other things to do this week!" Have no fear, Monte Carlo is here!
Step one: put your f(x) in a box. You already know the x values of the sides of the box; those are the bounds of the integral you're trying to evaluate. One of the y bounds should be the x-axis, and the other one could be anything, as long as it's bigger than the highest value of f(x) on that interval. Now you've got a box that neatly holds your function, or at least the part that you care about.
Like so.
Step two: throw some darts at the box. Well, figuratively speaking, at least. Basically, generate some random points that are inside the box. How many, you ask? As many as you want! The trick is that the more darts you throw, the longer it will take, but at the same time, the more accurate it will be. Honestly, though, "throwing" a million or a billion darts won't actually take that long, practically speaking, so you might as well make it a big number.
DARTS. DARTS EVERYWHERE. As long as "everywhere" means "inside the box".
Step three: count the darts in the box... and compare to the number of darts underneath the function. As the number of darts thrown increases, the ratio of darts inside both the function and the box to the number of darts in the box total approaches the ratio of the definite integral to the area of the box. Since you know the area of the box, you can multiply it by the ratio you've come up with and get an estimate of the definite integral. And all you had to do was throw some darts! Brilliant, isn't it?
... what? I warned you that I was a huge math geek.
The next one we talked about was the Las Vegas algorithm. It's an algorithm used for breaking symmetry, i.e. a random tiebreaker algorithm. The example problem given is something of an idealized problem. Imagine a city with a bunch of people, say, N of them. Idealville, if you will. Well, guess what? It's election day in Idealville, but they have some interesting elections. Everyone is allowed to run, everyone wants to run, and everyone who is running is allowed to vote for themselves. Unsurprisingly, everyone does votes for him/herself, resulting in an N-way tie. Clearly this will not do.
So what do the fine citizens of Idealville do? They hire an outside, unbiased third party to distribute random number generators to each of the N people in the election. Then RNG CO. tells everyone to generate a random number from 1 to N. They go around and verify that everyone does it correctly, and check each person's number. If that number is 1, then that person gets to stay in the election. Otherwise, that person is eliminated. Now we have a smaller group of people still in the election, let's say N'. If N' = N, then we repeat from the start of this round. If N' = 0, then we throw out the results of this round, and start again from the beginning of the round. Otherwise, we repeat the procedure on the smaller N'. You continue this until there's only one or two people left - if you get to one, that person is the winner. If you get to two, you flip a coin, and the winner of the coin flip is the winner.
Now, admittedly, I still don't have a satisfactory answer as to why you'd use this algorithm instead of just picking one random number from 1 to N and calling that person the winner. (Unless you're RNG CO., in which case you're probably making a hefty sum of cash from Idealville's yearly mayoral election. OCCUPY RNG CO. THEY ARE THE 1%.) That's not the interesting part, though. The interesting part comes when you examine the algorithm's time complexity, i.e. how long it takes to run. These things are usually measured as a function of the size of the problem, in this case N. So the result? Surprisingly, on average it takes less than e (Euler's number, 2.7182818284 and change) rounds to actually finish! In fact, as N approaches infinity, it takes an average of 2.442 rounds for the Las Vegas algorithm to decide a winner. Why is this a big deal? Because very few algorithms in Computer Science have a constant time complexity - something that takes just as long no matter how big the problem is. And it seems a little strange that this algorithm should!
(Actually, writing this, I suspect that this is a little bit BS. You still have to generate N random numbers in the first round. It should be at least N. I think I'm going to go in during office hours to ask about that.)
That was my 10:30 class. My noon class was also mathalicious. (Yes. That's a word. Deal with it.) Like I said, I missed the previous session of that class, so I came into Support Vector Machines, part 2. I'm not going to go into the detail of the actual math involved on this one, since it's a fair bit more complicated, and I'm not certain I understand it myself. But I'll give you the brief run-down, because it is also the best thing ever and I am a huge geek shut up.
So, Support Vector Machines are a technique for classifying sets of data. It is a binary classification technique, meaning it will only give a yes or a no answer. Here's how it works: you give it a bunch of data sets, and whether each one is a yes or a no. When you're done, you might end up with something that looks like this:
If only we could draw a line through thi- oh wait.
The Support Vector Machine will take all of that data, and try to draw a straight line such that all the yes examples fall on one side of the line, and all the no examples fall on the other side of the line. Obviously, this won't always be possible, so it also tries to minimize the amount of error. Now, you may be telling yourself "But that still doesn't work, CG! What if all the yes answers are inside a circle, and all the no answers are outside of the circle? It'll never work!" Okay, so maybe you're not telling yourself that. BUT YOU SHOULD BE.
Not even straight lines can help you now! Mwahahahahahahaha!
Ah, but there's a trick! There's a neat little thing called a kernel. How does it work? ... a little bit of magic, I think, but the point is that it can turn your input data into data in a higher dimension, which means you can then easily draw a plane that separates the data. Going back to the circle example, by using the right kernel, you can turn that into a three-dimensional cone, with the center of the circle being the point of the cone. Then you can easily chop off the cone at a certain height to separate all the yes answers from all the no answers! In fact, with a clever choice of kernels, SVMs can separate pretty much any binary data. It is important to note, though, that this only works on binary data - i.e. questions with a yes or no answer. So it can tell you "will it rain tomorrow?" but not "what will the temperature be tomorrow?". It could, though, tell you whether or not the temperature will be more than 75 degrees tomorrow.
Anyways, I've already tl;dr'd a lot on math in this post, so I'm going to cut this off here. Yep, I'm a total geek. But in a lot of ways, I needed this. I needed a reminder of why I'm in Computer Science - because I absolutely love stuff like this. This is what gets me excited. This is how I know I'm in the right major, even when individual classes have me discouraged.
EDIT: Added some crappy sketches! Yay! Also, a little bit of research on Wikipedia led me to realize that I've been misled, and as such part of the information in this post is wrong. I MUST CORRECT THIS.
'kay, so. What I called the Monte Carlo algorithm and the Las Vegas algorithm are not actually called those. In fact, Monte Carlo and Las Vegas are not actually random algorithms, but rather classes of random algorithms. Monte Carlo refers to all random algorithms that take a finite amount of resources to calculate, but don't always give the same answer. Rather, they give an approximation of the answer. Las Vegas algorithms, on the other hand, always produce the same answer, but randomly vary the amount of resources they need to find the answer. As such, the algorithms that I described here are examples of each kind of algorithm, rather than and algorithm with that name.
/END EDIT.
'til next time.