Given a problem, we can:

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?

- Give efficient methods to find exact solutions. When this is possible, all's well. But alas, this is not possible all the time.
- Give inefficient methods to find exact solutions (brute force), and bemoan that P != NP (mostly).
- 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.
- Prove theoretical approximation guarantees about these heuristics so that even in the worst case, the heuristic won't go bad beyond some known bound.

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: computer science

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.

<< Home

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
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.

<< Home

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