Tuesday, March 15, 2005
Heuristics vs. algorithms: A harmful distinction
On page one of many computer science theory texts, the author makes the distinction between algorithms--procedures with formal proofs of convergence--and heuristics--those without. A discussion elsewhere picks up the theme in an otherwise interesting post:
The author seeks a more human-like AI and suggests that GA and GP are qualitatively close in some sense, but then toward the end of the quotation we see how he is brought up short by the algorithm-heuristic categorization of his CS theory prof. Saying that GAs and GP are" really just certain types of heuristics" suggests that they are inferior to full fledged procedures accompanied by proof.
Elsewhere I have blogged on this topic. My main point was and is that in the realm of material machines (airplanes, toasters, automobiles), no such distinction is made, because proofs of convergence do not exist for the mass of things we use in our day to day lives. That is not to say that we don't understand the principles of operation of toasters, airplanes, automobiles and the like. We do, and we study the physics of different facets of their operation more closely as we need to improve their function (see here and here).
Let's bury the heuristic-algorithm distinction, or at the very least, let's acknowledge that the heuristic-algorithm axis is a continuum of mathematical understanding. Heuristics of differing stripes can function quite well, thank you very much, and many of them are backed with a good deal of mathematical understanding if not mathematical proof. Continuing to preface the term "heuristic" with the terms "merely," "just a," "only a," and the like is harmful, especially when it prevents us from grabbing the procedure we need to get the job done.
It's the human input that seems to contain all the "knowledge" an AI system has - something the designers and programmers already knew, and are trying to use the computer's speed and memory to use the concepts well. We're just not there yet with "self-learning" systems. Of course, there are randomness-based techniques to "learn" things (like genetic algorithms and genetic programming) that seem to fly in the face of all of this, but they're really just certain types of heuristics.
The author seeks a more human-like AI and suggests that GA and GP are qualitatively close in some sense, but then toward the end of the quotation we see how he is brought up short by the algorithm-heuristic categorization of his CS theory prof. Saying that GAs and GP are" really just certain types of heuristics" suggests that they are inferior to full fledged procedures accompanied by proof.
Elsewhere I have blogged on this topic. My main point was and is that in the realm of material machines (airplanes, toasters, automobiles), no such distinction is made, because proofs of convergence do not exist for the mass of things we use in our day to day lives. That is not to say that we don't understand the principles of operation of toasters, airplanes, automobiles and the like. We do, and we study the physics of different facets of their operation more closely as we need to improve their function (see here and here).
Let's bury the heuristic-algorithm distinction, or at the very least, let's acknowledge that the heuristic-algorithm axis is a continuum of mathematical understanding. Heuristics of differing stripes can function quite well, thank you very much, and many of them are backed with a good deal of mathematical understanding if not mathematical proof. Continuing to preface the term "heuristic" with the terms "merely," "just a," "only a," and the like is harmful, especially when it prevents us from grabbing the procedure we need to get the job done.
Comments:
<< Home
(I come from theory, so that might explain the direction of some of the following)
1) In the realm of "material machines" there is a lot that cannot be controlled for. For software that is intended for optimisation, sometimes you can know that you can reach the optimum.
2) To, as you say, bury
the distinction would be burying your head in the sand. Do the cost-benefit analysis between the two: balance between knowing that your procedure is always correct, against one that is experimentally fast/easy to code.
Acknowledge a lack of knowledge rather than deny it.
Certainly, heuristics are useful, especially in the absence of an algorithm (or efficient algorithm) for the problem. The markers "just", "merely" etc. just make it obvious that the proposed heuristic will not (or is not known) to always work, and "always working" (correctness) is a primary goal.
So, to be contrary, I would think it harmful to ignore the distinction, because it might lead a user of a heuristic to incorrectly expect it to always work.
1) In the realm of "material machines" there is a lot that cannot be controlled for. For software that is intended for optimisation, sometimes you can know that you can reach the optimum.
2) To, as you say, bury
the distinction would be burying your head in the sand. Do the cost-benefit analysis between the two: balance between knowing that your procedure is always correct, against one that is experimentally fast/easy to code.
Acknowledge a lack of knowledge rather than deny it.
Certainly, heuristics are useful, especially in the absence of an algorithm (or efficient algorithm) for the problem. The markers "just", "merely" etc. just make it obvious that the proposed heuristic will not (or is not known) to always work, and "always working" (correctness) is a primary goal.
So, to be contrary, I would think it harmful to ignore the distinction, because it might lead a user of a heuristic to incorrectly expect it to always work.
# posted by 
: 6:51 AM
: 6:51 AM
Hi,
you really have a very nice blog here! I'm definitely going to bookmark you!
I have a site dealing with seo expert. You are heartly invited to take some really good tips from it.
Come and check it out if you get time :-)
TheSEO-Rank.com
Post a Comment
you really have a very nice blog here! I'm definitely going to bookmark you!
I have a site dealing with seo expert. You are heartly invited to take some really good tips from it.
Come and check it out if you get time :-)
TheSEO-Rank.com
# posted by : 5:33 PM
: 5:33 PM << Home
