The Gradual Public Awareness of the Might of Algorithms

Soylent Mauve writes "The trend toward data- and algorithm-driven tuning of business operations has gotten a lot of attention recently — check out the recent articles in the New York Times and the Economist. It looks like computer scientists, especially those with machine learning training, are getting their day in the sun. From the NYT piece: 'It was the Internet that stripped the word of its innocence. Algorithms, as closely guarded as state secrets, buy and sell stocks and mortgage-backed securities, sometimes with a dispassionate zeal that crashes markets. Algorithms promise to find the news that fits you, and even your perfect mate. You can't visit Amazon without being confronted with a list of books and other products that the Great Algoritmi recommends. Its intuitions, of course, are just calculations -- given enough time they could be carried out with stones. But when so much data is processed so rapidly, the effect is oracular and almost opaque.'"

Comments

Said one computer scientist

[Nicholas Bishop]

Said one computer scientist getting his day in the sun:

"I'm melting, I'm melting!"

Re:Heuristics ARE algorithms

[pedantic bore]

That's an elegant metaphor, but someone has misled you.

An algorithm is a precise specification of a process whose outcome is defined by the initial conditions. To cite your example, quicksort is an algorithm -- the outcome of the sorting process is well defined, given the inputs.

But typical implementations of quicksort use a heuristic to choose the pivot element -- median of three, media of five, middle element, etc. These are heuristics because their goal is to choose the median value, but they can't make any guarantee that it will find the median. They can't even guarantee that they will find a good value. In fact, they generally don't even consider all of their inputs! They could choose bad values every time... but on average they don't, and quicksort is fast.

Another way of looking at it is that if an algorithm is correct, it will produce a correct answer for all valid inputs. A heuristic might produce incorrect answers for valid inputs, but it's correct often enough so that it might still be worth using -- especially if a correct algorithm is not known.

You may point out that randomized algorithms have a similar property -- but the difference is that with randomized algorithms the probability of error can be made arbitrarily small. With heuristics, there's no telling.