In my last post on heuristics and approximation, I asked the question - *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....* - which leads to further interesting exercises in intellectual masturbation.

Combinational Optimization is about finding the optimal (best/worst) candidate (based on certain acceptable parameters) among all possible options. A large category of problems can be mapped to combinatorial optimization, and most of these are NP-hard. This means that most of them do not have efficient solutions.

But we see humans, with some training and experience, solve many combinatorial optimization problems efficiently using heuristics and instinct. Chess, Go, Sudoku, etc., come into mind. In these games, the human has to search the solution space efficiently to find the correct board/grid position. And we know that humans do not do a brute force search. There is some internal process that short-circuits the search.....somehow.

Now, this somehow-situation could be explained by the following possibilities:

Anti-climax won't do. We need 'em real. That was a long session. Now for the money shot. [insert appropriate onomatopoeia here, in uppercase]

Combinational Optimization is about finding the optimal (best/worst) candidate (based on certain acceptable parameters) among all possible options. A large category of problems can be mapped to combinatorial optimization, and most of these are NP-hard. This means that most of them do not have efficient solutions.

But we see humans, with some training and experience, solve many combinatorial optimization problems efficiently using heuristics and instinct. Chess, Go, Sudoku, etc., come into mind. In these games, the human has to search the solution space efficiently to find the correct board/grid position. And we know that humans do not do a brute force search. There is some internal process that short-circuits the search.....somehow.

Now, this somehow-situation could be explained by the following possibilities:

- The human brain has a clever technique to narrow search space, and come up with exact solutions. This would mean that P==NP, and computer scientists still haven't found a proof for this. A proof of this would simply be an efficient way of solving one of the NP-hard problems (which, according to this bullet, the human brain is doing right now). We just need to know this purported technique formally to claim P==NP. This situation is highly unlikely because computer scientists have been trying since 1960s to find such a procedure in vain. Of course, their fastidious nature is also making them look for a proof that such an efficient procedure cannot exist (P!=NP). Whether the latter will be proven, or whether the question itself is beyond answer - only time will tell. But the former is very unlikely to be true.
- The human brain has come up with incredibly clever heuristics that approximate the search for the exact solution, and give us only approximate solutions. But these are so good, that they look exact almost always. But the fact that Kasparov got defeated by a computer shows that his heuristics used for chess were not infallible, and the computer's brute force search was much better (after all chess is played on a 8X8 board). Go and Bridge players still kick the machine's ass because of their games' bigger search spaces. This seems to be our Winston Wolfe (see Pulp Fiction) for the somehow-situation.
- The outlandish situation that my romantic mind wants to use to model itself is a trifle too....er....outlandish. Let me get there. It is known that Factoring a large number into its factors is a computationally hard problem. Its unlikely that a clever technique exists to find exact factors without going through brute force division. But Peter Shor, in 1994, proved that quantum computers can solve the Factoring problem efficiently! Now, quantum computers are still theoretical models which might never get built. Shor and co. coming up with algorithms that work on them motivates physicists and engineers to hopefully come up with a working model of the quantum computer in the future. Now, my outlandish conjecture is that the human brain already has a quantum computer like mechanism built into it, which enables it to solve certain combinatorial problems quickly. Modern physics accepts the reality of quantum mechanical concepts like superposition, etc. in nature. Why is it not possible that such features already physically exist in our brains, and this quantum computing brain is solving problems using quantum algorithms? Is the human brain a realistic quantum computer? Ummmm.....

Anti-climax won't do. We need 'em real. That was a long session. Now for the money shot. [insert appropriate onomatopoeia here, in uppercase]

Labels: computer science

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

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