Tayzwi

Should be reading more and writing less, but well...

Tuesday, January 03, 2006

 

Heuristics vs. Provability

Given a problem, we can:
  1. Give efficient methods to find exact solutions. When this is possible, all's well. But alas, this is not possible all the time.
  2. Give inefficient methods to find exact solutions (brute force), and bemoan that P != NP (mostly).
  3. Propose intuitively appealing heuristics that are quick, and give "mostly good" results in practice, and hope that the malicious worst case input which can tear the heuristic apart never comes about.
  4. Prove theoretical approximation guarantees about these heuristics so that even in the worst case, the heuristic won't go bad beyond some known bound.
Personally, I am fascinated by #4. Most current large scale problems rely on #3, which hopefully will get elevated to #4 in a few years time, and theoreticians will tell the practitioners - "Yeah, your heuristic will never give a solution that if off the optimal by 200%." As a budding researcher, is it better to build simulations, concrete systems, models, etc., and show empirically that certain heuristics work most of the time? Or is it better to take some small heuristic and prove without doubt its effectiveness under all circumstances?

The latter appeals to me because of its no nonsense, matter of fact, precise nature. But I can also see how we cannot do without the former. The former (heuristics) gets built to tackle real world problems. Theoreticians follow up later by giving provable approximate guarantees for these heuristics. Combinatorial optimization is rife with this pattern. What about other heuristics though?

Take the everyday example of Question Answering. Given a question, and an essay that might contain the answer to the given question, a reasonably educated person can extract an answer without much difficulty. But this simple task is extremely hard for an automated system. It can manage questions of the type: "how much," "what," and "when"; but will get flummoxed by questions of the type: "why" and "how". Practioners in the area of Natural Language Processing come up with heuristics that attempt to answer these tough questions, but there is no provable guarantee that these heuristics can answer all questions correctly all the time.

Can problems from the "Human Domain" be modeled fully as combinatorial problems so that we can hopefully give some approximation guarantee? Given realistic scale and scope, how does the human brain solve such problems (like question-answering)? Does the brain map everything to combinatorial optimization? Can its modus operandi be applied to automated systems so that they solve our problems while we attack other problems that right now are complicated even for the human mind?

Labels:


Comments:
As a budding researcher, is it better to build simulations, concrete systems, models, etc., and show empirically that certain heuristics work most of the time? Or is it better to take some small heuristic and prove without doubt its effectiveness under all circumstances?


I strongly agree with the former. The latter becomes a problem of mathematics and narrows down to only a small number of heuristics.Although "mathematical proof" is something, a simulation is what matters because it is a better approximation of reality than pure maths.Laymen will be more convinced by simulations and reports of input.
 
I am for the latter:
The token ring architecture proposed by IBM, had the advantage of the latter. Deterministic worst case guarantees were what was required. ( Sure there are other examples to the contrary, but interesting example of when mathematical proving can be useful). Same with RTOS I guess. ( I am sure Sudeep can explain it ). You need to prove hard guarantees.
 
Post a Comment

<< Home

Archives

February 2004   July 2004   August 2004   September 2004   October 2004   November 2004   December 2004   January 2005   February 2005   March 2005   April 2005   May 2005   June 2005   July 2005   August 2005   September 2005   October 2005   November 2005   December 2005   January 2006   February 2006   March 2006   April 2006   May 2006   June 2006   July 2006   August 2006   September 2006   October 2006   November 2006   January 2007   April 2007   May 2007   June 2007   November 2007   December 2007   January 2008   March 2008   June 2008   February 2009   June 2009   February 2010   November 2010  

Quick index to blog-posts I like (from my personal website)

This page is powered by Blogger. Isn't yours? Statscounter is generating statistics of this page