Войти в систему
Войти с помощью соц. сетей:
I just made the audacious statement that some algorithms reduce accuracy for the sake of increasing speed. In other words, Algorithm A is slower but guaranteed to produce the correct result, while Algorithm B is faster but may not produce the correct result.
Which would you choose?
If you’re a fourth-grade math teacher, this may be nothing short of terrifying. Imagine the following classroom conversation:
You say, “Kids, kids, settle down. Okay, who can tell me the answer to 4 times 6? Wow, Chester, your hand shot up fast! Okay, Chester, what’s the answer?”
Chester blurts out, “18!”
Some of the other children giggle softly. You say, “No, Chester. The answer is 24. Perhaps …”
Chester interrupts you, shouting, “But you gotta be impressed with how fast I gave you the answer!”
Impressive indeed. Do we want the wrong answer fast? This seems like a bad trade-off.
Yet, Monte Carlo algorithms do just this. They sacrifice accuracy for the sake of speed. (You’ll see in Chapter 13, that some Monte Carlo algorithms sacrifice accuracy for the sake of saving space, but in this chapter we’ll focus on speed.) Specifically, Monte Carlo algorithms use randomization to boost speed, albeit with a reduction in accuracy.
The name Monte Carlo comes from the Monte Carlo Casino in Monaco. In truth, though, there’s not much of a connection between the casino and the similarly named class of algorithms other than the fact that both have something to do with random chance. It’s a computer-science naming convention at its best.
Let’s take a look at where and why we’d want to use a Monte Carlo algorithm.
Let’s say we’re a polling agency and we want to predict the outcome of an upcoming mayoral election. If we want to get the most accurate results, we should interview everyone in the city who will be voting. In theory, if we managed to contact everyone who will vote, and everyone told us the truth, we’d identify our city’s next mayor with certainty.
The biggest hurdle preventing us from doing this is simply the fact that we don’t have the time (or staff) to contact everybody who lives in the city. To save time, pollsters only contact a portion of the total population.
This is a classic Monte Carlo algorithm at work. We save time by surveying fewer people. Although this will certainly reduce the accuracy of our poll, it may be accurate enough to get the job done.
Now, this only works if we conduct our poll according to the best practices of statistics. Pollsters are only okay with reducing the accuracy of the poll if statistics demonstrate that their results will likely not be far off from the truth. Accordingly, pollsters have to know how many people to interview. Obviously, interviewing one person will be super fast but will give us worthless data. Knowledge of statistics and probability is used to dictate how to conduct a random sampling so that our findings will likely be close to accurate.
A fundamental point to highlight about random sampling is the fact that it’s, well, random. Let’s say that statisticians determined, based on the size of the city, that we should interview 500 people. We would make a terrible mistake if we interviewed 500 people from the same neighborhood. This is because it’s possible that people living in the same neighborhood have similar political beliefs or have seen the same political billboards, so we wouldn’t be interviewing a group that truly represents the entire city. For sampling to work, we need to choose people at random, in which case it’ll be likely that the people will be from different neighborhoods and have different demographics.
In sum, random sampling is a great example of a Monte Carlo algorithm widely used in practice. And now it makes a lot more sense as to why we’d be willing to use such an algorithm even though we’re reducing accuracy. The key is that although we’re reducing accuracy, we’re following the rules of statistics so that our results will likely be accurate, or accurate enough for our purposes.
How accurate an algorithm needs to be depends entirely on your application. Here are some things to think about:
What is the worst thing that will happen if your results are not correct? Will you lose money? Will someone get hurt? Or is the worst thing that someone will be mildly annoyed?
A second item to figure out is the odds that the results will be correct, and if you’re okay with those odds. For our mayoral poll, is it okay if our results only have a 95 percent chance of predicting the winner? What about 90 percent?
Here’s another example to highlight these points. Let’s say we’re running an algorithm that will help a 10 billion dollar spacecraft land safely on another planet. Obviously, the stakes are high. But do we need an algorithm that is guaranteed to be 100 percent accurate? What if we can produce an algorithm that’s much faster but will only land the spacecraft with 99.99999999 percent probability? A careful analysis must be done to determine if we’re willing to take such a chance.
You’ve seen that a Monte Carlo algorithm can be, say, only 90 percent accurate. I’d like to point out, though, that this can manifest in two possible ways. One way is that an algorithm can be right 90 percent of the time, but the other 10 percent of the time, it’s completely wrong. Suppose that an algorithm is supposed to produce a result of either True or False. For the 10 percent of instances where the algorithm spits out the wrong answer, it couldn’t be more wrong.
However, another way in which an algorithm can be 90 percent accurate is through approximation. For example, suppose that an algorithm predicts tomorrow’s average temperature. If the true temperature is 100 degrees, and our algorithm predicted that it would be 90 degrees, our algorithm was 90 percent accurate.
In theory, certain Monte Carlo algorithms can guarantee to give approximate answers that deviate no more than 10 percent of the correct answer. These “wrong” approximations yield worst-case scenarios that are potentially much less “dangerous” than results that are completely wrong.
Войти с помощью соц. сетей: